（计算机系统结构专业论文）织女星网格中的资源发现机制研究.pdf

织女星网格中的资源发现机制一摘要 摘要 资源发现机制是关系到广域分布式环境中资源共享和协同工作效率的关键问题，在 计算网格、w e b 服务和p 2 p 技术中，都对这个问题进行了广泛的研究。本文全面地讨论 了织女星网格中的资源发现机制。文中分析了网格环境中的资源特点，介绍了相关领域 的研究成果，并结合织女星网格的v e g a 原理，讨论了织女星网格对资源发现机制的要 求。论文的创新点主要包含以下三个方面：1 ) 定义了织女星网格的资源发现机制，并 完善了资源发现机制解的构成，即一个完整的资源发现机制应回答几个关键问题：成员 协议、覆盖构造、信息预处理、请求处理和资源表示。2 ) 给出了这5 个问题在织女旱 嘲格中的解：基于路由转发的资源定位模型和三层资源表示模型；详细地描述了路由转 发的原始模型并讨论了模型的优化；描述了一个形式化三层资源表示的理论模型及其实 现。3 ) 讨论了如何评价一个网格资源发现机制的问题，给出了资源发现机制应该考虑 的因素：资源定位性能，可扩展性，对动态性的适应、负载均衡和好用性，并结合实验 数据，对织女星网格资源发现机制进行了评价。结果证明其具有良好的性能和可扩展性， 能够适用网格的动态变化，并且能够支持解决负载均衡和好用性问题的方法。 关键词：网格，织女星，资源发现，资源路由器，资源表示 织女星嘲格中的资源发现机制一a b s t r a c l 2 r e s e a r c ho nt h er e s o u r c ed i s c o v e r ym e c h a n i s mi nv e g ag r i d d o n gf a n g p e n g ( c o m p u t e rs y s t e m a r c h i t e c t u r e ) d i r e c t e db yx uz h i w e i t h er e s o u r c ed i s c o v e r yi sak e yp r o b l e mi nw i d e a r e ad i s t r i b u t e ds y s t e m s i th a sg r e a t i m p a c to n t h ee f f i c i e n c yt h er e s o u r c es h a r i n ga n d c o l l a b o r a t i n gi ns u c he n v i r o n m e n t s ，a n dh a s g a i n e dm u c ha t t e n t i o n i n c o m p u t a t i o n a lg r i d ，w e bs e r v i c e sa n dp e e r - t o p e e r r e s e a r c h e s b a s e do n p r e v i o u s w o r ko nv e g a g r i d ，t h i sp a p e rg i v e sa f u l ld i s c u s s i o no fv e g a sr e s o u r c e d i s c o v e r ym e c h a n i s m t h er e s o u r c ec h a r a c t e r i s t i c si ng r i de n v i r o n m e n t sa r ea n a l y z e d ；t h e r e l e v a n tr e s e a r c h e si nt h i sa r e aa r es u m m a r i z e d a n dt h ev e g a p r i n c i f l l e i no u rr e s e a r c hi s d i s c u s s e dt og u i d et h er e s o u r c ed i s c o v e r ym e c h a n i s md e s i g ni nv e g ag r i d t h i st h e s i sd o e s o r i g i n a lw o r ki nt h ef o l l o w i n gt h r e ep o i n t s ：1 ) g i v i n gt h ed e f i n i t i o no fr e s o u r c ed i s c o v e r yi n g r i da n dp r o p o s i n gaf i v e a x i ss o l u t i o ns p a c e ，w h i c hi n c l u d e sm e m b e r s h i pp r o t o c o l ，o v e r l a y c o n s t r u c t i o n ，r e s o u r c e i n f o r m a t i o n p r e p r o c e s s i n g , r e q u e s tp r o c e s s i n g a n dr e s o u r c e r e p r e s e n t a t i o n 2 ) d e s c r i b i n gt h es o l u t i o no fv e g a t ot h e s ef i v es u b q u e s t i o n sm a i n l yi nt w o p a r t s ：ar e s o u r c e - l o c a t i n gm o d e lb a s e do nt h er e s o u r c ei n f o r m a t i o nr o u t i n g - t r a n s f e r r i n ga n da t h r e e - l a y e r e dr e s o u r c er e p r e s e n t a t i o ns c h e m e b o t ht h el o c a t i n gm o d e l a n dt h er e p r e s e n t a t i o n s c h e m ea r ed i s c u s s e di nt h e o r e t i cw a y ( a l g o r i t h m so rf o r m a l i z e da ) 【i o m sa n dt h e o r e m s ) a n d i m p l e m e n t a t i o nm e t h o d s 3 ) f u r t h e r , d i s c u s s i n g t h e p r o b l e m o f e v a l u a t i n g ar e s o u r c e d i s c o v e r ym e c h a n i s m i ng r i de n v i r o n m e n ta n dp o i n t i n go u tf i v e k e ye l e m e n t s ：r e s o u r c e l o c a t i n gp e r f o r m a n c e ，s c a l a b i l i t y , a d a p t a t i o nt od y n a m i c ，l o a db a l a n c ea n du s a b i l i t y b a s e do n s i m u l a t i n ge x p e r i m e n tr e s u l t s ，v e g n ss o l u t i o n i se v a l u a t e di nt h e s ef i v e a s p e c t s ，a n d i t s e f f i c i e n c yi sv a l i d a t e d k e y w o r d s ：g r i d ，v e g a ，r e s o u r c ed i s c o v e r y , r e s o u r c er o u t e r , r e s o u r c er e p r e s e n t a t i o n 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得 的研究成果。就我所知，除了文中特别加以标注和致谢的地方外，论文中 不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研 究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 作者签名： 彳鹆 日期：z 。i ，7 关于论文使用授权的说明 中国科学院计算技术研究所有权处理、保留送交论文的复印件，允许 论文被查阅和借阅；并可以公布论文的全部或部分内容，可以采用影印、 缩印或其它复制手段保存该论文。 日期：己弼7 i偈t e 纵” 第毒引； 1 1 研究背景 第一章引言 随着互联网技术的迅速发展和应用，以及对广域分布的资源之间的共享需求的增加， 一些新技术应运而生，如计算网格1 1 ，w e b 服务和p 2 p 等等。其中的网格技术在初期 主要集中在高性能计算领域，现在网格己不再局限于此，而是出现了适用于不同领域的 网格技术，如数据网格、信息网格和商业应用网格等等。中科院计算所正在进行的织女 星网格研究中提出了服务网格的概念：应用和交互采用服务机制；网格及其应用的开发、 构造、部署、运行、使用、管理都采用一种称为“服务”的单一抽象接口；网格的功能 与性能评价将不只是采用传统计算机的评价标准( 如速度、加速比、性价比等) ，而以 用户满意度为目标，用服务质量来衡量【2 】。在体系结构上，织女星把网格看成一台虚拟 的超级计算系统，包括虚拟的网格硬件资源、网格操作系统、网格界面和网格应用等层 次。织女星网格在技术上有自己的鲜明特色，但是作为一个广域环境下的大规模分布式 系统，和其他系统一样，它也面临着以下挑战，解决这些挑战是织女星网格研究的重要 动机和目的： 资源的地理分布极广。资源之间，资源和客户以及客户之间都通过广域网( 如 i n t e r n e t ) 连接。这里的资源是指能被远程用户访问的所有软硬件资源：如网络存储 设备，w e b 服务，文件和数据库等等。在织女星网格中这些资源被封装成服务的形 式，通过特定的接口被网格用户使用。用户可以是使用这些资源的任何人或应用程 序； 资源类型和数量巨大。而且，资源不仅要能被共享，往往还被要求能够进行一定程 度的协同工作，以共同完成一个任务； 资源是动态变化的。这里的动态变化不仅包括资源属性的变化，还包括资源加入、 离开网格，以及在网格中的复制和迁移等； 资源往往是异构的。它们不仅仅运行在不同的平台上，而且由各自不同的所有者控 制，管理这些资源的策略也千差万别。 在i n t e r n e t 中，能被用户直接访问的资源的一般以u r i 3 的形式命名。基于u r i 的 资源命名又可分为位置相关的命名，如u r l 4 1 ，和位置无关的命名，如u r n s 。使用 u r l 的命名方式，实际上已经包含了资源的位置信息，从而省略了资源的发现过程。而 使用u r n 的表示方式，一般需要专门的名字服务( 如d n s ) ，将一个位置无关的标识 符映剞成资源的位置信息。无论使用u r l 还是u r n ，都有如下的问题： 在i n t e r n e t 中，使用u r l 来命名资源，命名规则是全局一致的，其标识符是全局唯 一的。但在织女星网格中，i n t e r n e t 被当成虚拟的物理层( 见1 3 节) ，而在网格用 户层，往往没有类似u r i 的全局命名( 描述) 规则，因此对用户可见的资源的统一 织女星网格中的资源发现机制研究 命名是难以实现的。 由于u r i 通常要经过名字解析的过程，才能定位到物理资源，所以一旦资源使用 u r i 命名并使用该名字发布，名字在资源的部署期间就难以更改，这难以满足资源 状态变化的需求，如属性的改变和位置的迁移等等。 u r l 和u r n 都主要是面向机器的，即如何赋予资源一个全局唯一的标识，命名的 过程( 名字的组成) 也都严格遵循u r i 的规范。而对用户来说，这种表示方式显得 不够友好：首先要访问一个资源，用户必须事先知道其u r i ，这个u r i 往往和资源 的属性没有关系。而资源的属性往往是用户最关心的，也是资源之间协同工作的必 需的信息：其次，u r i 的组成受其规范的限制，难以描述资源复杂的属性。 使用u r i ，可以实现资源的定位，解决了资源之间“物理”上的连通性，但远远不 能满足回格、p 2 p 和w 曲服务等大规模分布式环境对共享和协同工作的要求。也不能实 现织女星网格的设计原则( 见第三章) 。因此，在网格环境中，需要新的机制，使得用 户能够从海量的资源中获得所需的，使得需要协同工作的资源能相互发现。它不仅应考 虑资源的位置信息，而且应更进一步考虑资源的属性等语义信息。这种机制被称为资源 发现机制。 1 2 问题的定义 在织女星网格中，从用户的角度看来，资源发现1 的过程可以定义为：给出一个关于 资源的描述( 如一组资源的属性值) ，由网格的资源发现机制，根据一定的策略。返回 一组能与此描述匹配的资源。相关定义如下： 定义1 1 ：对一个资源描述集d 。和一个资源的属性集a ，若w ；d ，3 a a ，使 得a ，包含d 。，则称资源a 满足请求d ，记作s 似，d ) 。 定义1 1 是不严格的，因为没有精确的定义其中的“包含”。但这并不影响我们后面 的工作，因为这种包含是确实存在的，例如一个主频为1 g h z 的c p u ，可以“包含”一 个c p u ，7 3 3 m h z 的描述。 定义l 2 ：对网格g ，令d 是任一个资源描述集，若存在一个过程p ，和资源集合 ， 使得p q ) = a ，其中v a ，a ，都有s ( a ，d ) n a 。g 。则过程p 被称为网格g 中的一个资 源发现过程，a 称为p 对d 的目标集合。 定义1 - 3 ：在本文中的结点，若非特别说明，是指网格中根据特定策略，存储和交换 资源信息、转发资源请求的服务器( 本文中常用作资源路由器) 。 公理1 1 ：资源的信息是原子性的，不可分割的。 公理l 1 保证，如果某结点拥有某资源的信息，那么该结点拥有该资源的完整信息。 1 注：本文中另一个常用到的词是资源定位( r e s o u r c e l o c a t i o n ) 。在报多相关文献中，资源发现经常和资源定位常常 被不加区别的使用。在本文中资源发现是指从用户描述一个请求开始到用户能够得到一个可用的物理资源的全 过程。而资源定位是指将一个资源表示绑定到一个物理资源的过程。与资源发现过程相比。定位过程不包含对资源 请求中语义信息的处理 第一章引击 公理1 2 ：令月为网格g 中所有资源的集合，d 为g 中所有结点的集合，则 v r r ，3 d d ，使得d 中拥有r 的信息。 根据定义1 3 和公理1 2 ，从资源发现的角度看来，网格成为一个地理e 分布的结点 的集合，结点可随时加入或离开该集合。用户将资源请求发送给某个已知的结点( 如本 地结点) 。如果该结点有可与该请求匹配的资源的信息，则将这些信息返回给用户，否 则将对请求做进一步的处理，如转发到其它结点。 定义1 2 只是说明了资源发现过程的功能，对资源发现机制本身还没有给出更详尽 的描述。要给出一个关于资源发现机制的具有一般性的定义是困难的。【6 】中给出了大规 模分布式环境中资源发现机制应解决的问题。以此为借鉴，本文认为，网格环境中一个 比较完整的资源发现机制，一般应回答以下五个方面的问题： 威费力盯6 1 ：约定资源或结点以何种方式加入网格，如何获取其他结点或资源的信 息，并与之通信。 覆盖c z y , 迸1 6 1 ：一个网格结点如何从它本地可见的其它网格结点中，选取一个活动结 点的子集，使得通过与这个子集中结点的交互，就可获得必要的资源信息。这样， 从网格全局看来，在网格结点构成的图中，只选择部分边，构成一个覆盖，即可在 任一结点，获得整个网格的资源信息。在实际应用中，构造覆盖的策略是多种多样 的，如根据结点问的可用带宽、结点负载、安全性或管理策略以及制定的拓扑结构 等等。 顽始, n 6 1 ：为获得更好的搜索性能而预先采取的措施。这些措施是独立于资源请求 的。因此，对资源信息的缓存不是预处理，而预取是。另一个预处理技术的例子是 资源属性的发布，如将本地资源的情况通告远程的结点，以利于远程请求的快速匹 配。预处理还可以是网络覆盖的重新构造，如根据请求和资源的分布情况，实时地 由覆盖构造功能重新生成结点图的覆盖。 旃菇勉固6 】：包括本地处理和远程处理两个部分： 本地处理包括在本地存储的信息中对请求进行匹配，根据特定策略对请求进 行处理，如丢弃寿命超过t t l 限制的请求，或根据管理规则拒绝来自某些结 点等。 远程处理是指请求转发的规则：根据不同的策略( 如最短距离优先，f l o o d i n g 等) 将请求发送到其他的结点上。 磬掰藉示j 易靠用户如何表达( 描述) 自己的请求；资源以何种格式向网格报告自 己的状态；资源的信息在结点上以何种方式存储。 回答了以上五个问题，就基本上能给出资源发现机制的一个解：资源的表示方式给 出了用，、请求和资源信息的格式；成员协议负责收集和更新资源和网格结点的信息；覆 盖构造负责从已知成员中选取最优的( 根据特定标准) ，并构成结点覆盖网络的拓扑结 构；预处理为更有效地查找资源进行必要的准备；由请求处理完成最终的匹配和定位； 4 织女星网格中的资源发现机制研究 考虑到网格环境的特点，这五个问题本身就具有很大挑战性。比如，网格环境中资 源规模大、具有动态变化和存在错误的可能，使得收集准确的全局信息几乎不可能，而 这对以上四个问题都有影响：对成员协议来说，结点只能获得加入网格的其他结点的部 分信息；在获得的信息不准确并且多交的情况下，难以构造最优覆盖：也难以对预处理 和请求处理过程进行优化。在一个异构的、非集中控制的、资源种类非常庞杂的广域分 布式系统中，也难以实现一个统一的资源描述规则。 对资源发现机制和解空间的定义的完善是本文的创新点之一，后文将结合这五个问 题，讨论本文主要的创新点：资源信息的路由转发模型【7 】和一个三层结构的资源表示模 型f 8 1 。更进一步地，文中不仅将讨论是不是的问题，还将讨论网格资源发现机制的一些 原则和评价标准( 好不好的问题) 。 1 3 研究概述 织女星网格的个重要思想是将网格构造成一台运行在广域环境下的虚拟计算机。 以此为出发点，织女星网格将网格的体系结 勾与传统计算机体系结构之间进行了很多映 射，以此借鉴了很多传统计算机体系结构的思想和成熟技术，如计算机中的地址访问方 式、处理器一总线一设备的硬件结构。因此，虽然织女星的结构较简洁的，但却能有效 地解决资源共享和协同工作等问题。本文中将重点讨论与资源发现机制相关的部分。 为了回答1 2 中给出的资源发现机制中的五个问题，织女星网格的资源发现机制研 究提出了两个模型：路由转发模型试图回答资源发现机制解空间中的前四个问题：成员 协议、覆盖构造、预处理和请求处理；而资源表示模型则试图给出资源的描述方式，从 而构成网格中资源发现机制的一个完整的解。 路由转发模型是建立在织女星网格虚拟计算机模型的基础上的，与虚拟机模型的层 次结构有密切的关系。其基本框架如图1 所示2 1 。 图l ：织女星网格的虚拟计算机体系结构。 第一章引言 厕移雾户端旋各是织女星网格提供给网格用户的客户端平台。它包含组编程接口 和系统工具，构成网格应用服务器的宿主环境( 网格操作系统) 。网格客户端设备是一 个逻辑概念，它可以是个软件，也可以是专门的硬件。该层次也被称作用，o 层。 资脚踏出囊堤网格计算机虚拟总线的核心组成部分。所有的资源和用户都必须与资 源路由器相连才能加入网格。路由器通过彼此间的信息交换和对本地路由表的维护，为 用户提供虚拟的网格全局资源信息，并根据特定策略将来自网格用户的资源请求转发到 町以满足该请求的资源提供者( 网格虚拟设备) 。在本文中，如不加特别说明，资源路 山器等同于结点。 厨磐虚拗掇备是对网格资源提供者的抽象，不同类型的资源被看成不同类型的设备。 虚拟设备封装了网格资源的实现细节，可根据资源拥有者的要求，为用户呈现抽象的服 务访问接口。客户端设备访问某类虚拟设备前，需在其网格操作系统中安装针对该设备 的虚拟设备驱动程序，正如在p c 上安装新的硬件适配器一样。该层次也被称作物理层。 上述虚拟硬件构成了图1 所示的三层结构。这三个层次也分别代表了资源发现过程中 的= _ 个基本角色，即：资源消费者( 网格客户端) 、结点( 路由器) 和资源提供者( 网 格虚拟设备) 。 与此三层的虚拟计算机体系结构相适应，织女星网格中对资源的表示也分成三个层 次。 运行在网格应用服务器上的网格应用程序，在资源的表示方式和使用方式上是千差 别的，如：一个使用g l o b u s 计算网格的应用，是从基于l d a p 的m d s 上获得资源信息 的；而一个w 曲服务用户是从基于x m l 的u d d i 中心获取所需的服务信息。因此，如果 要建立一个通用的服务平台，使原先面向不同系统的应用，都可以在新平台上运行，并 提供无差别的服务，网格用户端设备必须能够支持应用对资源表示的定制，即：客户端 设备向应用提供的资源表示方式不是固定不变的，而是可以根据不同的应用和资源，给 出相应的表示方式。由于该层次上的资源表示主要面向应用，文中称其为用户层表或用 户层命名。 资源路由器是通过彼此间的信息交换和请求转发来实现广域分布式环境中的资源定 位的：路由器必须能够面向所有类型的资源，而不能为特定资源部署专用的路由器。因 此，资源路由器需要一种全局一致的机制，以识别不同类型、不同属性的资源。路由器 层的资源表示应该保证网格资源逻辑上的连通性只有能够被路由器识别的资源，才 被认为是在逻辑上加入了织女星网格。更进一步，考虑到路由器的性能，本层次上的资 源表示应能方便、高效地被路由器存储，发送和识别。路由器层表示也被称为路由器层 命名。 织女星网格体系结构的设备层( 物理层) ，由部署在广域网( 女i i n t e r n e t ) 上的资源 ( 虚拟设备) 构成。对资源发现机制来说，物理层资源表示的任务是保证资源是可以被 定位的，即资源在“物理”2 上加入了网格。因此从资源发现的角度，物理层表示可以 2 沣： 这驰的“物理”特指织史星 【】9 格的物理层，这里“物理”的含义与嘲络坼议以及操作系统中“物理”的古义足 n k 别的，后肯往往与硬件有直接关系，所以文中加了0 l 昔。 6 织女星网格中的资源发现机制研究 是资源的u r l 、( 资源所在结点地址+ 资源在结点内的编号) 等形式的位置信息。另外， 由于在织女星网格中资源以服务的方式封装，资源提供者必须知道资源在网格中的抽象 接口以及在路由器层的表示方式，只有这样才可以正确的向路由器发布可以被路由器识 别的信息，在逻辑上加入网格。因此，资源提供者还需要将资源的内部表示，转换成路 由器层的表示，以封装资源的“物理”实现细节。物理层表示也被称为设备层命名。 上述三个层次上的资源表示，构成了一个栈式结构，该结构可以非常清晰的映射到 现代操作系统中对存储器等资源的访问方式上，如图2 所示f 8 1 。 织女星网格典型操作系统 图2 ：织女星网格的资源表示模型与典型o s 存储模型的对比。 1 4 论文组织 第二章中将介绍广域分布式系统中资源发现机制的一些相关研究工作；第三章将讨 论织女星网格的设计原理在其资源发现机制中的指导作用和体现：第四章将给出资源信 息路由转发模型，包括基本模型及其优化；第五章将描述个形式化的三层的资源表示 模型及其实现：第六章中讨论资源发现机制中涉及的一些关键问题，包括效率与开销、 可扩展性、动态性能和负载均衡等，这些问题关系到一个资源发现机制“好不好”的问 题：最后，第七章将总结全文。 第二章相关研究 第二章相关研究 从传统操作系统中的存储管理、设备管理、文件系统到w e b 中的搜索引擎技术，再 到现在倍受重视的网格技术、p e e r t o p e e r 技术，如何更有效地利用资源，始终是计算机 科学中的一个重要问题。而如何高效地发现和定位资源，是有效利用资源的前提。织女 星网格在对资源发现机制的研究中，借鉴和参考了很多前人的研究成果，尤其是计算网 格，w e b 服务和p 2 p 等方面的研究成就： g l o b u s 利用g o s 9 将网格资源定义成不同的对象类，每个类都有其特定的属性。 信息服务通过目录服务m d s 1 0 1 的形式呈现给用户和信息提供者。对象类的定义和m d s 的配置均呈树状结构。m d s 根据用户请求，在自己维护l d a p 数据库中为其查找能够 匹配的资源，如果本地信息不能满足，可向上层转发。m d s 能够实现基于属性的查询， 但也有以下不足：1 ) 基于g o s 定义的树状资源空间过于单一，不够灵活，难以描述所 有用户的资源需求，而且使得使用其他命名方式的系统很难整合到g l o b u s 中来；2 1 基于 树状结构的m d s 在查找非本地信息时效率较低； 在w e b 服务中，和服务相关的实体信息被发布到u d d i 1 1 1 中心。这些信息可以分 为白页( 提供企业本身的信息) ，黄页( 提供企业分类功能) 和绿页( 包含企业提供的 服务的信息，如接口，访问点等) 。每个实体都有一个全局唯一的主键与其对应。u d d i 提供查找和向下考察的算法，使得客户能够找到自己感兴趣的实体( 企业，服务或接口) 。 u d d i 的最大问题是，它采用集中式的管理，服务的拥有者和用户只能到有限的几个 u d d i 中心注册和查询，因此，u d d i 中心容易成为系统的瓶颈。 不同于g l o b u s 和w e b 服务，在o g s a 1 2 1 中，每一个网格服务在生成一个实例时， 都由一个名为f a c t o r y 的服务赋予一个唯一的h a n d l e ，称为g s h ( g r i d s e r v i c eh a n d l e ) 。 g s h 中并不包含服务的详细信息，用户在调用服务前，一个名为h a n d l e r e s o l v e r 的服务 会对用户提交的g s h 进行解析，使得用户能够绑定到资源。每个网格服务都必须实现 一个名为f i n d s e r v i c e d a t e 的接口，通过该接口，用户可以访问到该服务的详细信息，这 些信息被称为g s r ( g r i ds e r v i c er e f e r e n c e ) 。可见，o g s a 并不直接支持全局的基于属 性的资源发现，用户必须首先提供服务的g s h 。它的重点在于给出一种网格服务的标准 架构，使得它们之间能更好的协同工作。 一些网格和中问件系统中采用了另一种思路来解决广域分布式环境下的资源定位， 本文对其做以下归纳：基于位置无关标识符( l o c a t i o ni n d e p e n d e n ti d e n t i f i e r ) 和定位服 务( l o c a t i n gs e r v i c e ) 的方法。该思路的核心是：为每一个资源生成全局唯一的i d ，这 个i d 通常与资源所在的物理位置无关，以利于资源的复制和迁移，增强系统的可扩展 性：专门部署的定位服务将i d 映射到可以访问物理地址。安全网格命名协议s g n p 1 3 1 给了种与资源位置无关的命名方法。资源名字( l o i d ) 到物理位置的绑定是通过 层次的名字解析完成的。这意味着无论一个资源移动到什么位置，它的名字可以不变( 因 8 织女星网格中的瓷源发现机制研究 此用户也不必修改自己的应用程序) ，但它必须注册到已分配给它的域解析器和绑定解 析器，这些解析器的地址是包含的l o i d 中的。显然，这种静态的注册和解析容易成为 定位的瓶颈。并且不够健壮。另一个类似的系统是g l o b e 项目 1 4 1 。它实现了两个与本 文的相关的机制：一个资源命名服务1 1 5 1 ，可以赋予每个资源一个与其位置无关的标识 符；一个定位服务 1 6 1 ，可以根据一个资源的标识符，得到该资源的物理位置。通过这 两个服务，g l o b e 可以支持资源在系统内的迁移。特别地，在 1 5 1 中，作者指出了现有 通过对象引用和符号名字命名资源存在的可扩展性方面的问题，讨论了g l o b e 中对该问 题的解决方法，并在f 1 7 1 了给出了一个具有可扩展性的、对用户友好的资源命名方法。 在p 2 p 系统中，更多的采用分布式的查寻方式。比较有代表性的方法有p a s t r y 1 8 1 ， c a n l 9 1 ，和c h o r d 2 0 1 。对这些方法可做以下的归纳：由资源的i d 组成一个空间，这 个空问被各个结点分割成若干个子空间，每个结点存储一个予空间，并负责该予空间内 的资源d 到物理位置的映射；结点间通过特定的协议通讯维护状态和转发查寻请求。 它们的不同在于结点间通讯协议，d 空间的组织和划分，结点状态的维护方法等细节。 这类方法的存在的问题有：1 1 资源空间大小虽然和结点的数量无关，但和资源的数量有 直接的关系，当资源数量增多时，整个系统维护资源状态的存储开销也随之增加：2 ) 在 有结点加入、离开或故障时，需要专门的协议和算法对d 空间的分配进行调整，开销 较大：3 1 资源和负责处理该资源的m 所在的子空间的结点间的关系很不确定，比如， 一个资源的d 很可能是由物理上离该资源很远的结点来完成映射的，这就使得通讯的 延迟变大，给定位的性能带有不确定性。 另一个对研究网格资源发现机制很有价值的系统是c o n d o r 的m a t c h m a k e r 2 1 1 。它 是一个典型的不依赖全局命名的资源共享系统。资源描述和请求被发送到一个中央服务 器上，由服务器负责匹配请求和资源信息。c o n d o r 的特点的资源不再由一个唯一的标识 符区分，而完全依赖属性的描述。对用户来说，这个很大的进步。不过c o n d o r 的 m a t c h m a k e r 是集中式的，这在网格这样的环境中是难以做到的。 第二三章资源发现机制的设计原则一v e g a 原理 第三章资源发现机制的设计原则一v e g a 原理 i 叫格环境作为一种大规模、动态的、异构的分布式环境，其资源发现方式和传统方 式有明显的不同。在织女星网格的总体设计中，设计者提出了v e g a 原j 里 2 2 1 ，这些原 理同样体现在资源表示和发现方法中研究中。 锺钶服务( v e r s a t i l es e r v i c e s ) ：织女星网格被设计成一个支持广泛的、多种多样的 软硬件资源的基础设施。这些资源以服务的形式加入织女星网格，在这里服务的定义是： 用户( 通过某种客户端设备) 向网格发出一个服务请求消息，网格接收并处理该请求， 执行服务请求所定义的服务内容所需要的服务操作，并向用户发回一个( 可能包括服务 结果) 的应答消息。这些服务有可能是计算服务( 如g l o b u s ) 、数据服务( 如数据库) 、 w e b 服务或者信息服务等等。这些服务所在的平台的具有多样性，同时这些服务对自身 的描述( 如调用的方式、属性信息的格式等等) 也具有多样性，从而使得这些服务的应 用也具有的多样性。要实现通用服务的原则，应用和资源有如下要求： 用户尽量不必修改自己的应用，就可以使用加入到织女星网格中的资源； 资源提供者尽量不必修改服务的内部资源表示方式，就可以加入织女星网格，并发 布自己的信息，使资源发现机制能够找到该服务。 为满足这些要求，在本文中给出的资源发现机制中： 在用户层，能够支持资源表示的多样性，如支持用不同的语法来描述资源请求( 例 如比较复杂的关系代数的方法和比较简单的属性表的方法) 。以保持原有应用中资源 表示方式的不变。 在物理层能够提供物理资源的抽象接口，使在物理上有不同实现方式的资源能够加 入织女星网格，发布自己的信息，并保证这些信息能够被资源发现机制正确的处理。 本文中给出的资源发现机制的目标是能够至少能够支持w e b 服务、g l o b u s t o o l k i t3 服务【2 3 1 和织女星网格自己定义的服务1 2 2 1 。 辅助智磁( e n a b l i n g i n t e l l i g e n c e ) ：织女星网格的一个目标是比现在的w 曲更具智能 性，比如资源信息的自动获取，聚类和过滤，自我路由，设备的自动接入等。辅助智能 的目的是减少用户使用系统的难度和负担，并在一定条件下，辅助用户决策。辅助智能 原则在本文所讨论的资源发现机制中主要有以下体现： 在资源发现机制中，支持用户使用基于属性集或其它更友好的描述方式，来递交资 源请求，从而屏蔽诸如资源的位置等物理信息，以降低对用户的要求； 考虑到网格中资源数量的庞大以及资源的动态特征，仅依靠传统的w e b 中靠用厂，址 住资源u r i 来实现资源定位的方式显然是远远不能满足需要的，而资源路由器正可 以根据一定的策略，替代用户从海量的资源中，选择能与其请求相匹配的最好的服 务，从而将火的网格“缩小”，将无限变为有限，便于用户使用； 0织女星网格中的资源发现机制研究 资源路由器可以自动的更新、处理、传播资源信息，保证整个网格中资源信息的实 时性，适应网格资源的动态变化： 更进一步地，通过在资源发现机制中加入某些策略( 如负载平衡机制) ，还可以使资 源路由器自主地优化整个网格的性能，减少管理网格的开销。 全局一筋( g l o b a lu n i f o r t u i t y ) ：织女星网格的全局一体有三个含义，即连通性、单 一系统映象、互操作性。本文中的资源发现机制与其中连通性和单一映象相关： 全局一体保证的是网格资源与资源之间、资源与用户之间的物理和逻辑上的连通性， 这是用户使用资源以及资源之间协同工作的基本前提。物理上的连通性在此没有必 要详述，资源发现机制的重点在于保证网格逻辑上的连通性，即资源发现机制应该 能够识别已经在物理上加入网格的各种资源，并为用户与资源以及资源与资源间的 沟通建立途径。因此，尽管网格用户和资源提供者都可能工作在异构的平台上，在 这些平台上难以，也不应该部署单一模式的资源命名和描述方式，但资源发现是一 个与网格全局状态相关的过程。在织女星网格中，这需要资源路由器间的协同工作， 所以各类不同的资源在所有路由器上的表示应遵循某一全局统一的规范，这一规范 所包含的主要是资源描述的结构信息，而不是资源表示的语义信息，从而保持不同 资源在语义上的独立性。 全局一体的另外一层含义是：对网格用户来说，其用户层资源空间是单一系统映象 的，这是资源发现机制在保证连通性的基础上对资源信息进行聚类的结果( 关于资 源信息聚类将在第四、五章中讨论) 。具体到资源路由器来说。就是其路由表中，资 源状态空间的维护。 自主攫哟7 ( a u t o n o m o u sc o n t r 0 1 ) ：在网格这样的广域异构分布式环境中，集中式的 控制应该是尽力避免的。首先，没有任何动机，能够使得某个组织或个人愿意负担维护 一个数量庞大的、行为难以预知的资源管理系统的开销。其次，集中式的管理往往造成 性能、动态变化和可扩展性方面的问题。因此，在本文讨论的资源发现机制中： 在资源发现过程中，应尽可能避免对资源进行集中式的命名和解析，这就要求为资 源的所有者和用户提供自主控制的能力，使其能自主定制资源和描述请求。 在资源非集中控制的前提下，对资源路由器来说，资源状态的动态变化往往是不可 预知的，因此，路由器应能够适应这种动态性，自主的更新资源信息，并根据其他 路由器结点的状态等情况进行自我配置( 如根据延迟情况重构覆盖，删除发生故障 的结点等) ，以降低整个系统的维护开销，提高容错能力和性能。 上述原则归纳起来，可以给出织女星网格对资源发现机制的要求：1 ) 在用户层和设 备层支持友好的、具有多样性的资源描述方式，方便用户对资源的使用，并利于各种资 源和网格应用在织女星网格中的部署，支持通用服务，实现辅助智能；资源的命名和解 第三章资源发现机制的设计原则- - v e g a 原理 析是非集中式，并尽量在本地完成，支持自丰控制。2 ) 在路由器层支持全局一致的资 源表示空间，实现全局一体，并提供有效的资源信息聚类和资源定位算法，实现辅助智 能。在t 述要求中，上层和底层的多样性和中层的+ 致性是有一定冲突的，但这种冲突 足可以克服的。 1 2 织女星嘲格中的资源发现机制研究 第四章资源信息路由转发模型 资源信息路由转发模型是织女星网格资源发现机制的核心内容。该模型主要包括资 源信息和用户请求路由算法、通信协议和状态维护策略等内容。它们试图回答资源发现 机制解空间中的前四个问题：成员协议、覆盖构造、预处理和请求处理。本章将给出该 原始模型的描述及在此基础上的优化。 4 1 基本模型 4 1 1 对资源的抽象 网格环境中的资源是复杂多变的，为了简化模型、方便分析和叙述，有必要对资源 进行定的抽象。 在网格环境下，资源可以根据其动态性来分为静态资源和动态资源。静态资源只有 两个状态：存在与不存在，如操作系统、软件、数据库等等。动态资源的状态是不断变 化的，如可用存储器大小，c p u 的负载和磁盘空间等等。为区别不同种类的资源和其状 态。在本模型中，每个资源都被赋予一个全局唯一的类型码r e s o u r c ei d ( 这个d 在资 源的全生命周期中是不变的) 和一个属性值r e s a 峨v a l u e ( 虽然一个实际的资源可能有 多个属性，但在研究路由转发模型时，用一个属性也就够了，下一章中将详细地讨论资 源的表示问题) 。一个资源的描述包括该资源r e s o u r c ei d 和r e s o u r c ev a l u e 。需要说明的 是这个组合并不能在网格中唯一的确定一个资源，有可能存在多个类型和属性完全相同 的资源，在这种情况下，哪些资源是对用户可见的，是由路由器根据一定的策略来决定 的。 对资源的类型进行编码是一个具有挑战性的问题，因为网格资源的类型非常复杂， 而且是在不断变化的。在本模型中，类型被抽象成一个简单的整数，对资源属性也做同 样处理。静态资源的属性只有两个值：0 或1 ，而实际上状态为0 的资源是不存在于网 格中的，所以不可能被资源发现机制发现。所以，当查找某一类型的静态资源时，如果 有多个同类资源( r e s o u r c ei d 相同) ，我们可以把它们看成同一个。但是，当查找某一 动态资源时，尽管同类的资源可能有很多，但由于它们的属性值不同，就不能简单地将 它们作为一个资源来对待，比如，如果用户想查找一个能提供1 0 g 存储空间的计算机， 那么一个只能提供5 g 空间的机器就不能满足该请求。而一个有2 0 g 空间的机器就可以。 4 1 2 模型框架 织女星网格的资源发现机翻中有三个基本角色：资源请求者( 网格用户) 、资源路由 第四章资源信息路由转发模型 器和资源提供者( 有时，为了简便，资源提供者和资源本身不加区别) 。它们i 者之i h j 有以f 关系：每个资源提供者必须连接到一个资源路由器上；每个资源路由器j 一个或 多个路由器或资源相连，直接相连的路由器互为邻居：每一个网格用户可以连接到个 或多个路由器上。它们的工作过程如下： 用户将自己的资源请求发给直接与自己相连的资源路由器。该请求包含了所需资源 的类型和属性值。路由器维护着记录邻居们( 包括路由器和资源) 的资源状态的路由表。 它总在等待用户请求的到来( 在某一特定端口上) 。当收到一个来自用户的请求时，路 由器检查本地的路由表，找出一个邻居，并将该请求转发给它。一个请求在到达个l 1 j 以满足它的资源或生存期( t t l ) 到期前，可能被多次转发。如果路由器发现个请求 的1 t r l 已经过期，就将该请求丢弃，不再做进一步处理。资源路由器还必须尽量保持 其路由表中资源信息的正确性和实时性；一个路由器将定期地收到它的邻居路由器向其 发送的更新报文，并以此为根据更新本地路由表中的相关内容。相应地，该路由器也应 该周期性的将本地的资源信息报告给它的邻居路由器。如果一个路由器在某一段时间内 没有收到来自某邻居的更新，则认为该邻居发生了故障，路由器不再将请求报文和更 新发送给该邻居，并根据特定策略更新拓扑。 资源提供者必须首先注册到一个路由器，并周期性地向其发送自己最近的状态。当 一个资源提供者收到一个资源请求时，如果本地资源可以满足请求，则向请求者发送相 应消息，否则将该请求丢弃。 图3 给出了路由模型和定位资源的过程f 7 1 。资源提供者竹提供了一个资源r ，而请 求m ，是来自请求者的，的请求。开始时，i n ，被发送至路由器岛，而根据路由表 嘞知道，如果将该请求转发至月，那么请求将最终到达资源r ，于是岛将请求m ，转发 至r j 。类似地，路由器r j 和飓也将为，选择一条可以到达p ，的路径。 ljr e q u e s t o r t 7p r o r i d e r r、r o u t e r 图3 路出表转发模型的结构和资源定位的过程。 4 1 3 资源路由器网络和协议 资源路由器是路由转发模型的核心，路由器构成的网络构成了织女星网格的骨f 。 所有的资源提供者和用户都通过连接到某个路由器来加入织女星网格，而通过路由器之 1 i l j 的互连，也可以实现网格的动态扩展。资源路由器网络中，所有的路由器在逻辑j ：足 织女星网格中的资源发现机制研究 平等的，不存在集中的控制点。在织女星网格的原型中，路由器网络是一个静态配置的 非结构化( u n s t r u c t u r e