（计算机软件与理论专业论文）网格环境中资源发现模型及资源发现算法研究.pdf

华南师范人学硕士毕业论文 摘要 网格环境中资源发现模型及资源发现算法研究 专业：计算机软件与理论 申请人：罗兰花 导师：刘波副教授 网格技术是新兴的i n t e r n e t 信息技术，是下一代互联网技术研究与应用的重 要领域之一。资源是网格中的主要对象，网格是协调管理地理上分布的各种资源， 并为用户提供透明一致的访问接口，实现资源的全面共享的系统。 网格资源发现是网格资源共享的基础，能否在网格环境下高效发现资源，已 经成为衡量网格系统好坏的一个重要标准，直接影响网格的利用率和友好程度。 随着网格技术的不断发展，对网格资源发现提出了新的需求，如实现高效查找、 基于属性查找、范围查找等。 根据网格资源发现的新需求，本文首先对现有网格资源发现模型进行了深入 分析，然后结合目前成熟的p 2 p 技术，引入虚拟组织的概念，设计了一个分布式、 可扩展、自组织的动态资源发现模型基于p 2 p 的分层分布式网格资源发现模 型。该模型是c s 模式和p 2 p 模式并存的系统，充分考虑网格资源的特点，结合 利用p 2 p 网络的高效资源搜索技术，从而更好地实现了资源的共享。其次，对现 有资源发现算法进行了详细的分析，根据提出的网格资源模型，提出了一种基于 c h o r d 的改进的资源搜索算法，使其适用于该资源模型并能获得更好的搜索效率。 网格资源发现还涉及到资源描述、资源注册和注销、资源更新、资源请求处理、 资源选择等几个方面，本文对这几个方面也进行了相关的设计及有益的探讨。另 外根据局部性原理，在模型中采用缓存机制，在一定程度上提高了资源搜索效率。 本文最后对提出的模型及算法进行了相关的模拟实验，进行了相关的分析比较， 验证了研究结论。 关键字：网格资源资源描述资源发现g r i d s i mp 2 pc h o r d 罗兰花：网格环境中资源发现模型及资源发现算法研究 a b s t r a c t r e s e a r c ht or e s o u r c e d i s c o v e r ym o d e la n da l g o r l t h m i ng r l de n v i r o n m e n t m a j o r ：c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：l u ol a n h u a s u p e r v i s o r ：l i ub o g r i di sa l le m e r g i n gt e c h n o l o g yi nt h ei n t e r n e ti n f o r m a t i o nt e c h n o l o g i e s i t i so n eo ft h ei m p o r t a n ta r e a so ft h er e s e a r c ha n da p p l i c a t i o no ft h en e x tg e n e r a t i o n i n t e r a c tt e c h n o l o g y r e s o u r c e sa r et h em a j o rs t u d y i n go b j e c t so f t h eg r i ds y s t e m ，t h e a i mo ft h eg r i di st oc o o r d i n a t ea n dm a n a g ea l lk i n d so fr e s o u r c e sw h i c ha r e g e o g r a p h i c a l l yd i s t r i b u t e d ，a n dt op r o v i d et r a n s p a r e n ta n dc o h e r e n ta c c e s si n t e r f a c e s f o ru s e r s ，i no r d e rt os h a r et h er e s o u r c e sw h o l l y g r i dr e s o u r c ed i s c o v e r yi st h eb a s eo fg r i dr e s o u r c es h a r i n g ，w h e t h e ro rn o t t h eg a dd i s c o v e rt h er e s o u r c ee f f i c i e n t l yi so n eo ft h ei m p o r t a n ts t a n d a r d st ov a l u et h e g a ds y s t e m ，a n di t sw i l ld i r e c t l yd e t e r m i n et h eu t i l i z a t i o na n df r i e n d l yd e g r e eo fg r i d w i t ht h ec o n t i n u o u sd e v e l o p m e n to fg r i dt e c h n o l o g y , t h eg r i ds y s t e mp u tf o r w a r d a d v a n c e dr e q u e s t so ng r i dr e s o u r c e sd i s c o v e r y , f o re x a m p l e ，e f f i c i e n tq u e r y 、q u e r y b a s e do na t t r i b u t e s 、r a n g eq u e r ya n ds oo n a c c o r d i n gt ot h en e wd e m a n d so fg r i dr e s o u r c e sd i s c o v e r y , t h i sp a p e r f i r s t l yi n t r o d u c ee x i s t i n gg r i dr e s o u r c ed i s c o v e r ym o d e lw i t hi n d e p t ha n a l y s i s ，t h e n c o m b i n e dw i t hc u r r e n tm a t u r i t yp 2 pt e c h n o l o g y , a d o p t e dt h ec o n c e p to fv i r t u a l i i 华南师范大学硕士毕业论文 o r g a n i z a t i o n ，h a sd e s i g n e dad i s t r i b u t e d 、s c a l a b l e 、s e l f - o r g a n i z a t i o nd y n a m i cr e s o u r c e d i s c o v e r ym o d e l - - b a s e do nt h eh i e r a r c h i c a ld i s t r i b u t e dp 2 pg r i dr e s o u r c e d i s c o v e r ym o d e l t h em o d e lm a d ec sm o d ea n dp 2 pm o d ec o e x i s t e n c ei no n e s y s t e m ，i tg i v e sf u l lc o n s i d e r a t i o nt ot h ec h a r a c t e r i s t i c so f 酊dr e s o u r c e s ，a n dw i t h e f f i c i e n tr e s o u r c es e a r c h i n gt e c h n o l o g yi np 2 p n e t w o r k s ，t h e na c h i e v e dab e t t e r s h a r i n go fr e s o u r c e s s e c o n d l y ，i th a sc a r r i e dad e t a i l e da n a l y s i sf o re x i s t i n gr e s o u r c e s d i s c o v e r ya l g o r i t h m a c c o r d i n gt ot h eg r i dr e s o u r c em o d e l ，t h i sp a p e rp r o p o s e dt h e i m p r o v e ds e a r c ha l g o r i t h mt h a tb a s e do nt h ec h o r da l g o r i t h m ，m a k ei ta p p l i c a b l et o t h em o d e la n dc a no b t a i nb e t t e rs e a r c h i n ge f f i c i e n c y g r i dr e s o u r c ed i s c o v e r yt h a ta l s o i n v o l v e ss e v e r a lo t h e rr e s p e c t s ，i n c l u d i n gt h er e s o u r c ed e s c r i p t i o n 、r e s o u r c e r e g i s t r a t i o na n dc a n c e l l a t i o n 、r e s o u r c eu p d a t i n g 、r e s o u r c er e q u e s t e dt r e a t m e n t 、 r e s o u r c es e l e c t i o na n ds oo n , t h ep a p e ra l s oc a r r i e do u tr e l a t e dd e s i g na n ds o m e b e n e f i c i a le x p l o r a t i o ni nt h o s er e s p e c t s i na d d i t i o n ，w eu s ec a c h em e c h a n i s mi nt h e m o d e la c c o r d i n gt ot h el o c a l i t yp r i n c i p l e i tc a ni m p r o v er e s o u r c es e a r c h i n ge f f i c i e n c y t oac e r t a i ne x t e n t f i n a l l y , w ec a r r i e do u tr e l e v a n ts i m u l a t i o ne x p e r i m e n t sa b o u tt h e m o d e la n dt h ea l g o r i t h m ，a n dm a d ed e t a i la n a l y s i sa n dc o m p a r i s o nf o rt h e m ，i t v e r i f i e dt h ec o n c l u s i o no ft h es t u d y k e y w o r d s ：g r i dr e s o u r c e ，r e s o u r c ed e s c r i p t i o n ，r e s o u r c ed i s c o v e r y ，g r i d s i m ，p 2 p ， c h o r d 华南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的研究成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确的方式标明。 本人完全意识到此声明的法律结果由本人承担。 论文作者签名：罗哆执 日期：泖年上月刁日 学位论文使用授权声明 本人完全了解华南师范大学有关收集、保留和使用学位论文的规 定，即：研究生在校攻读学位期间论文工作的知识产权单位属华南师 范大学。学校有权保留并向国家主管部门或其指定机构送交论文的电 子版和纸质版，允许学位论文被检索、查阅和借阅。学校可以公布学 位论文的全部或部分内容，可以允许采用影印、缩印、数字化或其他 复制手段保存、汇编学位论文。( 保密的论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密范围，在年后解密适用 本授权书。非保密论文注释：本学位论文不属于保密范围，适用本授权 书。 论文作者签名：零叻v 咖捌年上月刁日 导师签名：毒叫习分 导师签名：伊、f 刁 日期渺，归f 月垆 华南师范人学硕士毕业论文 第一章绪论 1 1 课题的研究背景及意义 网格是9 0 年代人们针对当时的一些科学计算难题而提出的概念，它的最初 目的是为了解决科学研究中的大规模计算问题。随着互联网技术的迅速发展和应 用以及高性能计算技术的不断发展，单台高性能计算机系统己经难以胜任某些超 大规模计算问题的求解，而互联网上各种计算资源的利用率极低。综合这两个方 面的问题，有人提出，把大量的处理器资源联合起来使用，鼓励人们在互联网技 术的基础上把现有的利用率不高的分散在不同地理位置的、异构的、动态的各种 资源通过高速网络连接在一起、整合，这就需要将地理上广域分布、系统异构的 多种计算资源通过高性能网络互连起来，共同求解大型应用问题，即广域高性能 元计算技术( m e t ac o m p u t i n g ) ，办称网格计算【i 】技术。 现今网格己不仅仅局限于计算领域，出现了在各个领域适用的网格技术，如 数据网格、信息网格、知识网格、语义网格和商业应用网格等。网格作为当前兴 起的一种重要信息技术，被誉为继传统i n t e r n e t 和w e b 之后的第三次信息技术浪 潮。网格主要研究在分布、异构、自治的网络资源环境上动态构建虚拟组织并实 现跨自治域的资源共享与协同工作。资源的汇聚和共享是网格最重要的特征，共 享与协作是网格的基本理念，而资源发现则是资源共享的重要基础。 随着网格技术的不断发展，网格规模越来越大，网格资源的种类越来越多， 网络结构也越来越复杂，使得网格资源查找变得异常复杂，很难准确快速地找到 符合用户需求的资源。网格资源发现作为网格系统中一项非常关键的技术，对网 格系统的资源共享起到至关重要的作用，因而资源发现技术面临着越来越大的研 究挑战。网格资源发现研究的意义【2 】主要体现在： 1 、资源发现是资源共享的基础，对后续使用共享资源以及整个系统性能有 重大的影响。 随着网络规模的扩大，应用的增多，资源种类和数量的急剧增长，网络上资 罗兰花：网格环境中资源发现模型及资源发现算法研究 源的状态也在不断变化，用户在使用共享资源之前很有可能不知道资源的确切位 置，或者用户希望选择在当前环境下最优的、最适合自己的资源，这就需要动态 的根据当时的系统状况进行资源查找。快速的找到满足用户需求的资源，是用户 能够直接感知的系统体验。而为用户找到最优的满足条件的资源，对用户及后续 资源的使用有很大的影响。所以，无论是从性能上，还是功能上，资源发现都是 用户非常关注的服务。 2 、资源发现是众多应用的基石。 网络越来越成为人们生活的一部分，各种应用也层出不穷。而资源发现是一 个基础，能够为很多上层的应用提供服务，是众多上层应用的基石。 3 、资源发现可以为资源调度，资源使用收费等提供实现的手段和有力的支 持。 因为网络规模很大，系统中的资源数量巨大，或是其他一些原因，使得资源 发现过程很难遍历整个系统，搜寻所有的满足条件的资源，因此资源系统默认的 包含了一个对资源的初步筛选过程。如果资源发现服务总是返回负载最轻，使用 最少的资源，这样的话就有助于实现资源的合理调度及使用。而如果有些资源提 供者向资源发现系统支付了广告费用，那么资源发现系统就可能会向用户优先返 回这些资源提供者提供的资源。这样的做法可以作为一种新的广告模式，产生实 际的价值。 1 2 论文主要内容、设计目标及挑战 网格资源发现就是在网格环境中查找与应用程序需求匹配的可用资源，网格 资源发现服务是网格系统的一个基本服务，是把资源和资源请求者联系起来的重 要环节，有了资源发现机制资源请求者就能方便地使用自己请求的资源，否则， 大量的资源放在网格上，请求者不知道自己能够使用哪些资源【3 1 。j 下因为网格资 源发现模型及发现算法是网格资源发现中的关键技术，所以网格资源发现模型及 发现算法的研究非常重要，对资源发现的整个过程起着决定性作用。目前对网格 资源发现模型的研究普遍采用层次模型，但这类模型中还存在一些不足，使得资 源发现扩展性不好、查找效率不高，难以满足实际网格系统用户的要求，所以需 要综合考虑多方面的因素，进行进一步的改进；另外现有的专用于网格资源的发 现算法不多，且普遍存在查询效率和网络性能方面的不足，如何选择合适的发现 2 华南师范大学硕士毕业论文 算法以及如何改进算法以获得较高的查询效率和准确率是急待解决的难题。上述 两个问题j 下是本文的主要研究内容，也是本文的设计目标和挑战所在，所以本文 主要围绕这两个问题进行讨论和研究。 1 3 论文的组织结构 本文的总体结构大体分为四个部分：第一部分为理论研究，主要包括第一、 二章；第二部分网格发现模型及算法设计实现，主要为第三章至第四章；第三部 分实验模拟及实验结果分析，包括第五章；最后总结全文及展望。具体的内容安 排如下： 第一章介绍了网格资源发现的研究背景，资源发现研究的理论和实际应用意 义，及本文组织方式； 第二章阐述网格相关技术以及p 2 p 技术的特点； 第三章主要介绍现有的网格资源发现模型，并对这些模型进行分析比较。另 外还介绍了目前常用的几种资源发现算法，对它们进行了评价和分析； 第四章在现有资源发现模型的基础上设计了一种新的网格资源发现模型，并 对该模型中的资源描述、资源请求处理、资源选择、资源注册和注销、资源信息 更新等做了详细的设计。同时对资源发现算法进行改进，使之可以基于属性进行 查询并提高查找效率； 第五章针对提出的模型和采用的算法进行了相关的模拟实验，对实验结果进 行了分析和评价； 最后对整篇文章的进行总结并提出了进一步工作展望。 罗兰花：网格环境中资源发现模型及资源发现算法研究 第二章网格及p 2 p 技术综述 2 1网格技术综述 2 1 1 网格的概念、需求及特点 网格的概念最初是从电力网( e l e c t r i cp o w e rg r i d ) 借鉴而来的，因为网格的 资源与电力网中电力的使用非常相似，因此人们提出了这个概念。网格界的权威 i a nf o s t e r 在网格：一种未来基础设施蓝图中给出了网格的描述性定义：“网 格是构筑在互联网上的一组新兴技术，它将高速互联网、计算机、大型数据库、 传感器、远程设备等融为一体，为科技人员和普通老百姓提供更多的资源、功能 和服务。互联网主要为人们提供电子邮件、网页浏览等通信功能，而网格则能提 供更多更强的功能，它能让人们共享计算资源、存储资源和其它资源。” 4 1 因为 当时人们就什么是网格争论不休，为此，i a nf o s t e r 曾于2 0 0 2 年7 月在什么是 网格? 判断是否为网格的三个标准t s l q b 提出了判定网格的三个标准，为别为： ( 1 ) 在非集中控制的环境中协同使用资源；( 2 ) 使用标准的、开放的和通用的 协议和接口；( 3 ) 提供非平凡的服务。 网格不仅要实现资源在物理层面上的互联，更要提供资源在逻辑层面上的共 享和协同，即网格目标就是要对遍布世界各地的资源提供一种“即插即用 的新 型资源方式。 如今，人们已对网格的认识达成了共识，网格就是把整个i n t e m e t 的各种资 源进行整合，并将它们转化成一种有效的、可靠的、标准的资源共享方式，实现 全面共享和协同，为人们提供方便高效的资源服务。 网格的需求如同其他新事物的出现一样具有必然性，网格出现的必然性主要 体现在以下几个方面： ( 1 ) 超大规模计算问题：现在高科技领域的超大规模计算问题需要网格， 因为现有的高性能计算机已不能满足需求，只能寻求其他解决办法，同时科学家 4 华南师范大学硕士毕业论文 们需要利用分布在世界各地的计算机等资源，而网格提供分布式计算能力奠定了 基础； ( 2 ) 资源利用率低：曾有调查报道互联网中计算机资源的平均利用率不足 1 0 ，计算机的利用率低已是一个不争的事实。互联网上有大量的剩余资源没有 得到充分利用，充分利用这些闲散资源实际意义重大。无论在哪一个领域，资源 都是弥足珍贵的，因此资源利用率低也是促使网格技术出现的一大原因； ( 3 ) 现有技术基础的支撑：网络及计算机分布式技术的发展为网格的出现 奠定了基础，不论是计算机的普及程度、计算机的性能的提高，以及网络通信速 度的提高和带宽的增长等都为网格出现做好了准备； ( 4 ) 资源共享的广度和深度有限：尽管传统互联网实现计算机硬件的连通， w e b 实现了网页的连通，然而人们可用的资源无论从种类还是数量上还非常有 限。网格的目的就是要实现整个网络上各种各样的资源全面连通与共享，而不仅 仅是网页资源的共享。网格用户只需遵守网格的相关规范，就可以方便的使用网 络上的任何资源； ( 5 ) 计算机相关资源升级频繁，资源浪费严重：由于计算机等电子类产品 更新换代太快，产品的性能似乎总是赶不上各种应用需求的增长，因此用户不得 不经常地升级软硬件或者干脆购买新的产品。无论个人还是社会都把大量的资金 浪费在购买各种软硬件设备上，网格的出现就是为了使用尽可能少的资金，能够 节约资源、从而真正意义上实现资源的可持续利用； ( 6 ) 资源共享方式复杂：传统互联网出现的目的是为方便人们共享网络资 源，它主要通过w e b 等网页方式实现共享，在传统的网络环境下加入到网络中 的新资源需要较复杂的设置，而人们希望通过一种简单的共享方式，而网格提供 了这样一种方式，即新资源只需通过接入网络的标准接口即可成为网络一部分， 直接被网络其他用户使用，即实现“即插即用”的资源共享方式。 网格是一种新型的基础设施，为用户、资源提供畅通的共享渠道，提供安全、 高效、高质量的服务，它的主要特点简单介绍如下： ( 1 ) 分布性分布性是网格的一个最主要的特点。网格的分布性是指网格资 源是分布在地理位置不同的多个地方。分布性是网格在硬件方面的物理特征； ( 2 ) 共享性共享也是网格的一个基本特征。网格的资源虽然是分布的，但 罗兰花：网格环境中资源发现模型及资源发现算法研究 是它们却可以充分共享。共享是网格的目的，解决分布资源的共享问题是网格的 核心内容。共享是在网格软件支持下实现的逻辑特征； ( 3 ) 自相似性自相似性在许多自然和社会现象中大量存在，一些复杂系统 都具有这种特征。网格的局部和整体之间也存在一定的自相似性，如局部某些特 征在整体有所体现，而整体的某些特征也在局部中有体现； ( 4 ) 动态性和多样性动态性主要指网格资源及其状态并不是成不变的， 而是在不断的变化。原来拥有的资源在下一时刻可能会出现故障无法使用；而原 来没有的资源，可能随着时间的推移会不断的加入网格。多样性是指网格资源是 异构和多样的，在网格环境中可以有不同体系结构的计算机系统和不同类别的资 源； ( 5 ) 虚拟性虚拟化是网格中实现资源描述和访问的一种方式。网格中的资 源和用户都要经过抽象，把实际的用户和资源虚拟化为网格用户和网格资源。网 格用户使用标准、开放、通用的协议和界面，可以访问网格中的各种资源，但实 际的用户和物理资源是相互不可见的，即资源对外提供的只是一个虚拟化的接 口。 2 1 2 网格需要解决的问题 尽管网格技术己得到了很多应用和研究，但仍存在一些问题需要进一步解 决，如缺乏一种有效的资源查找与任务调度机制；没有一个可以对现有软件工具 统一封装的机制；现有的网格并行编程方式还不够灵活，在网格上细粒度并行运 算不够成熟：现有网格还不能很好地支持已有软件的协同使用。具体可分为以下 几个方面： ( 1 ) 网格安全问题安全问题一直是业界非常关注的问题，虽然它不是什 么新问题，因为在任何系统中都需要考虑安全问题，都要进行相关的安全性设计。 一个网格系统的网格安全体系在考虑i n t e m e t 安全问题之外，还要考虑到网格系 统本身的特殊性，网格面临的安全问题大致可分为3 类1 6 1 ：将现有技术和安全 协议进行集成和扩展；不同主机坏境之问协同工作的能力；相互影响的主机环境 之间的信任关系。 ( 2 ) 协同问题网格的特征决定了网格节点的体系结构可能不同，资源分 配和作业迁移等都涉及到异构问题，所以如何实现异构资源之间的协同工作和转 6 华南师范大学硕士毕业论文 换是首要问题： ( 3 ) 可扩展性在网格资源和用户规模不断扩大、应用不断增长的情况下， 要实现网格的方便扩展，且不降低性能； ( 4 ) 动态自适应性因为网格是个庞大的系统，其中的资源出现故障的可 能性较高，因而要有相应的自适应机制从可利用的资源中选取最佳资源来提供服 务，如目前通常采用副本技术等提高冗余程度来保证资源的可用； ( 5 ) 协议和服务标准迄今为止，网格计算还没有正式的标准。在核心技 术上，现在普遍采用由美国a r g o n n e 国家实验室与南加州大学信息科学学院合作 开发的g l o b u st o o l k i t ，g l o b u st o o l k i t 是一种开放架构和开放标准基础设施，它 提供了构建网格应用所需的很多基本服务，如资源发现、资源管理、数据访问、 安全等。i b m 、微软、s u n 等厂商已宣布将支持g l o b u st o o l k i t ； ( 6 ) 知识产权问题在网格中很多被共享的数据都存在知识产权问题，如 何保护知识产权也是一个需要解决的问题； ( 7 ) 资源发现和任务调度资源发现和任务调度是网格系统的两项关键技 术，但是目前网格系统还缺乏高效的资源查找与任务调度机制，正因为如此，这 两项技术成为网格领域研究的热点问题。 2 1 3 网格的关键技术 网格技术就是在网格中用于实现大规模、大粒度、大范围的资源的方便、灵 活、高效的共享而出现的各种技术。换句话说，网格技术就是为了解决上一个小 节中提到的问题。人们对网络的广泛应用及新的需求推动了网格技术的发展，网 格技术大致可分为网格应用技术、网格核心服务技术以及构建网格基础的网格底 层支撑技术。 网格关键技术主要包括以下几个方面： ( 1 ) 资源管理技术 资源管理技术是指如何对网格环境中的资源进行管理的技术。目前网格系统 有很多种体系结构模型，各种模型所采用的资源管理实现各不相同。即使采用的 是相同的体系结构模型，具体的资源管理实现和任务调度方式也不一定相同。所 以网格资源管理技术主要集中在如何实现各资源管理系统之间的互操作性、不同 的资源使用不同的管理策略、实现系统的负载平衡以及防止网格系统节点故障措 罗兰花：网格环境中资源发现模型及资源发现算法研究 施等方面； ( 2 ) 资源发现技术 资源发现是在网格资源管理基础上提出的，两者息息相关，合理高效的资源 管理能为资源发现奠定好的技术基础。资源发现技术就是在有效组织资源的基础 上，根据网格用户的需求找到相关可用资源的过程并把用户和用户请求的资源联 系起来的一项技术。资源发现性能的好坏直接决定了网格资源使用的效率，是网 格环境中非常关键的技术之一； ( 3 ) 资源调度技术 网格资源是由多个资源提供者提供的，资源调度是指如何从资源发现服务中 查找到的可用资源列表中选择最合适的资源。一个好的资源调度策略将在很大程 度上提高网格资源的利用率。 目前的调度算法主要分为静态算法和动态算法，静态调度算法是指所有的机 器任务映射策略都是事先确定好的，经典的网格资源静态调度算法有：o l b 、 m e t 、m c t 、m i nm i n 和m a xm i n 等。动态调度算法是指机器任务映射策略 在执行资源调度期间根据实际情况进行确定，现有的网格资源动态调度算法又可 分为在线模式( o n l i n em o d e ) 和批模式( b m c hm o d e ) 两种。在线模式指任务到 来就立刻启用资源调度模块将其映射到机器，该模式对每一个任务的映射只考虑 一次。批模式下，任务到达后并不是立即映射到机器，而是把任务收集起来组成 一个任务集合，等映射事件到来后才启用资源调度模块对该集合中的任务进行集 中映身； ( 4 ) 资源监控技术 资源监控是指为特定任务选定资源后，负责监控从任务提交到远程的资源并 执行到任务完成的整个过程。通过监控技术可以及时发现故障节点，分析异常现 象，监控数据还可用来预测系统的运行轨迹，为动态负载均衡策略提供可靠的依 据。在监视的过程中还可能出现在调度问题，这主要是指在任务的执行过程中， 如果出现远程机器出现故障、远程资源执行的效果和预期不服、或者任务出现后 又出现了更合适的资源等情况时，就会发生再调度。 目前网格系统中典型的监控系统有g r a m ( g r i dr e s o u r c ea l l o c a t i o n m a n a g e m e n t ) ，它是g t 中的资源管理组建，提供对任务提交和监视支持，包括远 8 华南师范大学硕十毕业论文 程提交任务、任务执行状态查询、以及状态的预测等。 全球网格论坛( g g f ) 在1 9 9 9 年成了一个专门的工作组，该工作组定义了一 个可扩展的网格监控体系结构，主要撰写了一组网格监控需求和一个高层次的网 格监控规范g m a ，可见在网格系统中资源监控的重要地位。 2 1 4 网格技术的研究现状和发展趋势 国外研究现状： 网格技术源于美国，目前比较有影响力的有美国科学网格项目，它的目标是 建立基于网格中问件( g r i d w a r e ) 和系统工具的高级分布式计算基础设施( a d c i ) 使能源部科学计算体系的可伸缩性满足能源部内部科学研究任务要求。远程分布 式计算与通信项目的目标是创建一个用于访问美国能源部三个武器实验室的具 有可操作性的网格，以支持国防计划中远程计算和分布式计算这两个关键战略领 域复杂的分析、设计、制造、认证功能。地球系统网格( e a r t hs y s t e mg r i di i ， e s g ) 项目由阿贡国家实验室( a r g o n n en a t i o n a ll a b o r a t o r y ) 等五个国家实验室 的科学家联合承担。主要目标是解决从全球地球系统模型分析和发现知识所面临 的巨大挑战，为下一代气候研究提供一个无缝的强大的虚拟协同环境。国家地震 工程仿真网格的目标是使地震研究人员能够进行各种地震工程实验数据分析的 大规模计算任务。 此外，美国正在进行的网格项目还包括g l o b u s 、美国航空航天局( n a s a ) 的信息动力网格( i n f o r m a t i o np o w e rg r i d ，i p g ) 、美国国家技术网格( n a t i o n a l t e c h n o l o g yg r i d ) 、虚拟实验室项目( v i r t u a ll a b o r a t o r yp r o j e c t ) 、天体物理仿真 合作实验室( a s t r o p h y s i c ss i m u l a t i o nc o l l a b o r a t o r y ，a s c ) 、国际虚拟数据网格实 验室( i n t e r n a t i o n a lv i r t u a ld a t ag r i dl a b o r a t o r y ，i v d g l ) 等等，其中g l o b u s 是 目前全球最有影响的网格研究计划之一。 欧洲的网格研究也非常活跃，有影响的项目主要有欧洲数据网格( e u r o p e a n d a t ag r i d ，简称e d g ) 、英国国家网格( u kn a t i o n a lg r i d ，简称u l ( n g ) 等。 亚洲地区有影响的项目有日本实施的全球计算基础设施项目n i n f , 韩国的 n g r i d 项目、印度的i - g r i d 网格等。 国内研究现状： 我国从9 0 年代末开始，网格也进入了大力发展的研究阶段，如清华大学网 9 罗兰花：网格环境中资源发现模型及资源发现算法研究 格研究组的先进计算基础设施a c i ( a d v a n c e dc o m p u t a t i o n a li n f r a s t r u c t u r e ) 的研 究；中科院等十几个科研单位承担的8 6 3 重点项目“国家高性能计算环境 ( n h p c e ) ”，并在这之后将其网格研究称为“织女星网格( v e g ag r i d ) ”：8 6 3 支持的项目“中国国家网格”( c h i n an a t i o n a lg r i d ，简称c n g r i d ；教育部与i b m 合作的“中国教育科研网格项目( c h i n a g r i d ) ”等等。 2 2p 2 p 技术综述 2 2 1 对等网络p 2 p 简介 i b m 对p 2 p 络( p e e r - t o - p e e r n e t w o r k ，即对等网络) 的定义【7 1 是：p 2 p 系统由 若干互联协作的计算机构成，且至少具有如下特征之一：系统依存于边缘化设备 的主动协作，每个成员直接从其它成员而不是从服务器的参与中受益；系统中成 员同时扮演服务器与客户端两种角色；系统应用的用户能够意识到彼此的存在， 构成一个虚拟网络。 p 2 p 是分散化的、自组织的完全分布式系统，具有如下特点【8 1 ： 分散化( d e c e n t r a l i z a t i o n ) ：分散化是指系统中的数据和资源分散在参与的节 点中。在对等计算模型中，每个节点具有对数据和资源的拥有和控制权，在功能 上是等同的。 自治。| 生( a u t o n o m y ) ：许多情况下，分布式系统中的用户希望在本地处理数据， 而不情愿依赖于第三方服务供应商。p 2 p 网络支持自治性，是一种自治性网络。 系统中所有或大部分结点在功能上是等同的，既可作为客户( c l i e n t ) 又可作服务器 ( s e r v e r ) ； 动态性( d y n a m i c ) ：由于p 2 p 网络是以自组织( s e l f - o r g a n i z a t i o n ) 方式建立 起来的，节点可以自由地加入或退出网络，这也就决定了p 2 p 网络不可能用单一 的全局机构来管理大规模的动态系统，这种管理应该分布在参与的各个节点上； 异质性( h e t e r o g e n e i t ) ，) ：系统中各个节点的c p u 处理能力、存储能力、带宽、 以及他们在系统中的滞留时间都有很大的不同。 隐私性( i n t i m a c y ) ：作为网络安全的一个方面得到越来越多的关注，p 2 p 网 络中信息传输分散在各节点之间进行而无需经过集中环节，用户的隐私信息被窃 听和泄漏的可能性大大缩小。另外目前i n t e m e t 隐私问题主要采用中继转发来解 1 0 华南师范大学硕士毕业论文 决，而p 2 p 网络中所有的参与者都可以提供中继转发的功能，提高了匿名通信的 灵活性，为用户提供更好的隐私保护； 健壮性( r o b u s t n e s s ) ：p 2 p 网络中服务是分散在各个节点上的，部分节点或 网络出现故障对其它部分的影响很小。而且p 2 p 网络中具有自动调整整体拓扑即 具有自维护和自修复能力，从而保持其它节点的连通性。 覆盖网络( o v e r l a yn e t w o r k s ) ：对等网络是一种覆盖网络，对等网结点间的连 接关系和路由是应用层意义上的，在对等网上路由一跳( o n eh o p ) 对应于在i p 层 上路由一跳或几跳。 2 2 2p 2 p 的网络模型分类 业界对p 2 p 网络模型分类没有完全统一，有学者认为带有服务器的网络结 构不属于p 2 p 网络；另外一些学者则认为虽然有些网络带有服务器，但是弱化了 服务器的功能，而且客户端的连接方式符合分散式拓扑结构，因此可将其认为是 广义的p 2 p 网络【9 】。 根据目前p 2 p 的应用及研究发展，比较统一的观点是将p 2 p 网络划分为集 中式p 2 p 网络模型、纯分布式p 2 p 网络模型、混合式p 2 p 网络模型和结构化p 2 p 网络模型四大类。 集中式p 2 p 网络模型 集中式p 2 p 网络不是一种严格的p 2 p 网络，在网络中有一个或多个节点的 服务器用于为对等节点提供目录服务，即采用的是集中目录管理。这种模型的典 型代表是n a p s t e r 。下图是典型n a p s t e r 拓扑结构模型图如图2 1 ： 图2 1n a p s t e r 拓扑结果图 集中式p 2 p 网络具有一下特点： 罗兰花：网格环境中资源发现模型及资源发现算法研究 ( 1 ) 易于管理，资源的发现依赖于中心目录服务器，查询效率高； ( 2 ) 只需接受返回结果，对等节点负载低； ( 3 ) 系统过多依赖目录服务器，容易造成单点故障，可靠性和安全性较低； ( 4 ) 对目录服务器的性能和网络带宽要求高，因而可扩展性差。 上述特点决定了集中式p 2 p 拓扑结构不适合大型网络。 纯分布式p 2 p 网络模型 纯分布式p 2 p 网络属于非结构化p 2 p 网络，没有固定的拓扑结构，此种类 型的p 2 p 网络代表有：g n u t e l l a l l o l ( g n u t e l l a 是纯粹的p 2 p 文件共享系统) 和 g o s s i p 1 。 纯分布式p 2 p 网络具有以下特点： ( 1 ) 网络中没有专门的服务器，完全依赖于网络中的对等节点； ( 2 ) 允许用户设定自己的规则进行通信，而不是像c s 模型中基于服务器 设定的模式通信，同时对等节点在任何时候既是查询的发起者，又是搜索处理的 执行者； ( 3 ) 网络的拓扑结构图是一个完全随机图，节点之间的链路不用遵循任何 预先设定，受节点加入和退出系统的影响小，网络的容错性好； ( 4 ) 纯分布式p 2 p 网络通常采用泛洪算法搜索资源，广播查询消耗大量网 络带宽，而且随着对等节点的增多，查询速度会变慢，从来带来扩展性差的问题。 混合式p 2 p 网络模型 混合式p 2 p 网络目标是吸取集中式p 2 p 方便维护和管理、查找算法简单及 效率高等特点和纯分布式p 2 p 扩展方便、容错性好等特点，这种模型中通常在分 布式模式的基础上，将节点进行分类，选择其中某些性能较高的节点作为超级节 点( s u p e r n o d e ) ，在各超级节点上存储了系统中其他部分节点的信息，发现过 程主要在超级节点之间进行，然后再转发给适当的叶子节点。所以混合式p 2 p 是一种层次式结构，此种网络的典型代表是k a z a a 网络和j x t a 网络。 1 2 华南师范大学硕士毕业论文 图2 - 2k a z a a 网络拓扑结构图 混合式p 2 p 网络的特点： ( 1 ) 与集中式p 2 p 相比，降低了单点崩溃的可能性。与分柿式p 2 p 相比， 减少了查询消息的传播数量以及对等节点的负担； ( 2 ) 可扩展性较好、比较容易管理； ( 3 ) 对超级节点的依赖性较大，容错性也比纯分布式要差。 结构化p 2 p 网络模型 结构化p 2 p 网络模型的根本不同之处在于每个节点维护的邻居是按照某种 全局特定的规则组织起来的，结构化模型的组织方式决定了节点之间可以采用比 较简单地查找算法快速地查找。按照这种方式组织的网络模型代表有 c h o r d 1 2 】【i3 1 、c a n 1 4 】【1 5 1 t a p e s t r y t l 6 1 和p a s t r y 1 7 1 等。 结构化p 2 p 网络模型的特点： ( 1 ) 所有的节点采用相对稳定并紧致的拓扑结构，维护简单； ( 2 ) 查找效率高、速度快，而且减少了节点信息的发送数量； ( 3 ) 具有较好的扩展性； ( 4 ) 避免了单点失效问题，但是节点需要维护一定的冗余信息，维护代价 较高。 2 2 3 现有p 2 p 技术研究与比较 p 2 p 技术包含的方面很多，如p 2 p 安全技术、对等节点的缓存技术、节点存 储系统设计、文件传输服务、协同计算以及资源搜索等等，这里我们主要介绍几 种经典p 2 p 资源搜索机制，并做了比较详细的比较。 罗兰花：网格环境中资源发现模型及资源发现算法研究 2 2 3 1 泛洪( f l o o d i n g ) 搜索机制( 广播搜索) 上一小节己提到g n u t e l l a 网络中不设置中心服务器，因而可以避免了因中 心服务器故障而导致的单点实效问题。但是存在一个明显的缺点就是用户不知道 节点的位置信息。所以在纯分稚式网络中常采用泛洪( f l o o d i n g ) 搜索，泛洪搜索 通过广播的方式来进行资源查找。基本思想是当某个节点要查找资源时，首先把 请求信息传播到所有相邻结点，这些邻居节点再将请求传播给它自己的邻居，依 次类推，直到找到所需要资源或者达到预先设定的条件为止。通常在设计上每条 查找消息都带有全局唯一的标识符，防止对相同查询请求进行多次响应。用户可 以基于查找结果，选择使用一个最合适的资源，并可以和资源结点建立类似h t t p 的连接。 如图2 3 所示，节点a 向所有的邻居节点b ，c ，d ，e ，g 发送查询请求，然后 其各个邻居继续向自己的邻居发送