自治的基于信息汇聚协议的网格体系结构.doc

第2期陈志刚等：自治的基于信息汇聚协议的网格体系结构37自治的基于信息汇聚协议的网格体系结构陈志刚, 李登, 曾志文，刘佳琦（中南大学 信息科学与工程学院，湖南 长沙 410083） 摘 要：提出一种基于信息汇聚协议的网格架构（IPBGA）。将资源与任务间的需求提升为信息服务，使资源分配和任务调度转换成基于信息汇聚协议的信息匹配操作；将虚拟组织分解为信息服务层和协同工作层，有助于构建信息全局视图。实验和理论分析证明其核心的信息汇聚协议具有较高搜索和信息处理效率，较好的容错性且带宽和处理器消耗较少。关键词：网格；结构化覆盖网；面向服务体系结构；信息汇聚协议中图分类号：TP393 文献标识码：A 文章编号：1000-436X(2008)02-0029-08Autonomic grid architecture based on information pool protocolCHEN Zhi-gang, LI Deng, ZENG Zhi-wen, LIU Jia-qi (School of Information Science and Engineering, Central South University, Changsha 410083, China) Abstract: An information pool based grid architecture (IPBGA) was presented. Requests from resources for tasks and appeals from tasks for resources were upgraded as information services by using information pool protocol (IPP). Thus, grid resource management and task scheduling were regarded as information matching by IPP which was adaptive to heterogeneous, dynamic and distributed characteristic of grid system. Dividing virtual organization into information services layer and cooperation layer, it is helpful to build general view of information. Experiments and theory analysis show that information pool protocol of IPBGA is more efficient in searching and dealing with information while bandwidth cost and process cost are less.Key words: grid; structured overlay network; service-oriented architecture; information pool protocol1 引言收稿日期：2006-07-10；修回日期：2007-12-30基金项目：国家自然科学基金资助项目（60573127, 60773012）Foundation Item: The National Natural Science Foundation of China(60573127, 60773012)典型的网格系统Globus1和Web Services2，由于其服务器发布、发现均采用集中式模型，可扩展性差且存在单点失效问题，因此有许多研究者利用P2P技术构建面向服务的Grid架构（SOA）。文献3融合P2P和网格，分布式存储节点定期向SMCS 证明自己的存在和汇报自己的文件列表，但仍采用集中式服务器结构SMCS 维护全局信息。文献4将P2P架构引入知识网格，主要介绍P2P搜索和定位算法。文献5提出P2P-Grid框架，基于五层沙漏模型，服务层构建在连接层和管理层基础上，并未很好结合虚拟组织的概念构建整个架构，使其结构跟服务是松耦合的结合。文献6提出P-Grid结构，融合结构化和非结构化P2P的优点，提出一种自组织的DHT-like的P2P路由组织，但树型索引结构面临的单点失效问题使其容错性较差。文献7在计算网格中使用一种P2P发现引擎SIONet，解决资源发现和将原数据包发送到目的地的工作，引入该引擎应对计算和存储资源改变的动态性。文献8仅将P2P看作一个中间件，且结构中使用管理器，仍采用了集中式架构，并非完全自治。由上所述，大部分P2P-Grid架构，或是为减少中央服务器工作负担7，在结构中使用peer to peer数据传输方式，各个节点在中央服务器注册、交互信息，只在任务传输中应用P2P传输；或如当前大多数研究，使用P2P算法进行资源搜索操作4，仅从体系结构角度，在grid众多模块中的资源管理模块引入P2P。然而其中的P2P算法并不适应网络计算需求，当前有两种典型分布式P2P系统：结构化P2P系统和非结构化P2P系统。结构化系统如Chord9等搜索复杂度与节点总数成对数关系，有很高的可扩展性，但对象定位需要知道确切ID或关键字，所以无法真正适应节点的动态加入退出。虽然有许多研究提出更复杂的搜索算法10,11以增强查全率和查准率，但仍无法较好地适用于具备高度动态性和随机性的网络计算具体应用。现实网络中节点有效性和持续性无法得到保证，在这种情况下，无法控制数据的分布并且向结构化应用所需的严格约束的网络拓扑。非结构化系统可以很好适应现实网络的异构环境。典型的非结构化P2P系统如Gnutella，采用不同的洪泛（flooding）方法在网络中发布查询信息，容错性好、灵活且易支持模糊匹配和关键字查询。然而信息洪泛造成的大数量级流量限制了该方法的可扩展性和效率。为了有效解决上述问题，很多研究者提出超节点结构1214，充分利用网络异构性，有能力的节点承担较多负载，既具有集中式搜索的效率，同时分布式搜索方法也使其具备自治性、负载均衡性和顽健性。然而当前多数超节点算法采用的层次结构（树型）易导致单点失效，而针对其提出的冗余机制造成节点处理和带宽损耗大。与以往研究不同，本文从体系结构角度重点研究和分析了SOA、P2P架构与网格计算的结合机理。首先分析了结合P2P技术的网格资源管理和任务调度研究的现状，然后基于SOA提出一种以信息汇聚为核心，信息服务为基础的网格体系结构(IPBGA, information pool based grid architecture)，将虚拟组织分为信息服务层和协同工作层，信息服务层汇聚资源信息，建立信息的全局视图协调资源共享；协同工作层利用局部自治域优化，在信息服务层全局信息视图基础上协同解决调度问题，重点分析比较信息服务层的P2P架构，提出信息汇聚协议（IPP, information pool protocol），与其他系统比较证明，其具有较好的可扩展性，较小处理和带宽损耗，具备较强容错性。本文主要包括5节，第2节从宏观上介绍基于IPP的网格体系结构（IPBGA）的功能模型，结合SOA和P2P进行详细说明；第3节着重阐述IPP形成及相关核心机制；第4节从效率、损耗和容错几方面使用实验与理论分析相结合的方法对IPP进行验证；第5节是结束语。2 IPBGA网格的功能模型 针对网格资源和节点研究与应用面临的分布性、自治性、动态性和异构性4个基本问题，给出IPBGA功能结构如图1所示。IPBGA包括3个层次：物理层（physical layer）、虚拟组织层（virtual organization layer）和应用层（application layer），同时还包括贯穿各层次的端到端QoS保障机制。主要功能如下。1) 物理层。传统上一般将“资源“这个术语狭义地解释成指代某种物理实体，例如计算机、网络或存储系统。IPBGA强调“广义资源”，表示在网络化环境中可被共享和利用的任何能力，包括物理资源（如计算力、科学仪器等）和逻辑资源（网络带宽、软件、应用服务等）。物理层同时包括各种随机动态任务。与一般网格研究只考虑资源层不同，IPBGA中所有物理形式归纳于物理层，包括资源和任务，既包括主机、存储设备等有形物理资源和逻辑资源，如网络带宽、应用服务等，也包括计算、数据存储、搜索等随机任务。图1 IPBGA网格的功能结构2) 虚拟组织层。网格计算在动态的、多机构的虚拟组织中协调资源共享和协同解决问题。基于此提出将虚拟组织分为信息服务层和协同工作层，采用管理与发现相分离的方法，以解决网格系统分布、动态和自治性等问题。 信息汇聚协议。IPBGA体系结构重点和核心部分，不同种类的资源，抽象出其共享能力等，对于各种动态随机任务，抽象出其对资源的需求，封装为信息服务。在Globus中，资源管理和信息服务处于同一中间件层，资源和任务是动态的，但在IPP中，资源抽象后的资源信息（AR, abstract resource）和任务信息（AT, abstract task）可作为相对静态的文件，从而用文件共享来实现资源共享。节点间以P2P方式交互，通过多自治域自适应处理，有助于在底层网格服务基础上满足不同应用对任务调度和资源分配的差异性。 协同工作层。主要基于IPP所汇聚的信息，进行基于信息的资源分配和任务调度工作，协同工作采用P2P方式，无需调度器，由空闲资源节点自适应索取任务，资源和任务的处理首先建立在信息的交互上，资源分配任务，任务寻找资源的过程转变为信息匹配过程，在信息的基础上构建服务，以低损耗的信息迁移和调动来解决任务颠簸（churn）和资源饥饿现象。3) 应用层。通过借鉴引入类似Globus采用的RSL1，使用抽象描述语言来描述系统中任务对资源的需求（如计算中对于计算力的需求、文件搜索中对于文件类型和内容的要求等）。借助相关编程模型、人机交互机制为系统提供人机界面。4) QoS保障机制。网格计算环境中，服务所指概念更广，包括各种计算资源、存储资源、网络、程序、数据库等，一切都是服务。主要包括安全性、可靠性和性能等方面，为P2P系统提供服务质量保证。3 信息汇聚协议许多研究者基于语义15或内容相似度13进行域划分，然而对于没有集中式管理的松耦合分布式系统，跨域搜索时会遇到困难。逻辑上相邻的节点在物理上可能相隔甚远，使同域内信息交互和资源分配都可能遇到很大网络延时。基于映射代价考虑，IPP中节点按照物理距离远近划分自治域，物理距离相近的节点划分一个自治域，而物理距离相近的自治域彼此邻接。如图2和图3所示，IPP逻辑结构是一个多自治域层级式立体结构，每层包含若干级，每级包含若干自治域，自治域间、层、级间以信息中心方式连接，图2中的表示第i层第j级的第k个域中的节点。每个自治域有3个信息中心分别是：域（local节点）、级（level节点）和层信息中心（layer节点）。如表示第i层第j级第k个域的信息中心level节点。规定信息中心所能处理的最大入度为d，即定义某一自治域达到饱和的情况是：该自治域的layer节点所连接的下层自治域数目、local节点连接的非信息中心节点数和level节点所连接的同层下级自治域数目分别为d。IPP中信息中心之外的节点统称为普通节点（NN），NN向local节点主动汇报其任务、资源、资源使用及任务执行等情况。local、level和layer节点分工不同，与本自治域内所有NN相连并接收它们汇报的任务、资源及使用执行等情况，为新加入节点分配ID并记录，同时将其上所有信息备份在和。IPP中所有信息中心节点除了完成本身的职责，同时会将其职责内所收集信息分别备份在同自治域其他信息中心上。节点负责接收由与之相连的下层的节点汇报的该所在自治域图2 自治的信息汇聚协议图3 i层信息汇聚的ID、IP和SR值等信息。i层的d个自治域向第i+1层layer节点汇聚，目的是当近距离自治域间无法进行信息匹配时，通过该结构访问远距离自治域仍可用较小代价实现信息匹配。如图3所示，同层自治域level节点采用层级索引结构进行信息汇聚，同层第i级节点之间物理距离比之与第i+1级节点间近（），由节点负责向上级的节点汇报本级所在自治域的任务和资源信息。针对自治域划分和信息中心选择提出一种资源级（source rank）机制，自治域中节点通过在线排队函数SR对本域其他节点的任务完成满意度进行排序。选取满意度记录最良好的3个节点作为自治域信息中心。当节点Pi和Pj之间进行信息交互时，假设由节点Pi向节点Pj发出查询，E(Pi, Pj)表示节点Pi对节点Pj完成其查询要求的满足程度的评估(1)其中参数增强了查询符合度权重，越大，对某一查询的内容越匹配的节点，获得的查询满足程度越大。即Pj越能满足Pi的查询，其所获评价越高。函数Qsim: Q2 0, 1（Q为查询空间）用来计算节点对查询反馈时的符合程度。表示节点Pi和Pj信息交互次数，表示节点Pi和Pj通信时间。当不同节点对查询的满足度相同时，IPP更倾向于允许单位通信时间内而非总在线时间内信息交互次数更多的节点加入自治域中，以减少只享受而不贡献本身资源和能力的节点（称为free rider）的百分比，同时防止新加入但积极贡献的节点因在线时长不够导致总信息交互次数较少而被退出系统。L是查询中出现的所有资源或者服务的集合。定义一个维向量空间，其中每个查询是一个向量。举例来说，假如集合L包含资源或者服务需求A, B, C, D，有一查询A, B，则与之相对应的向量是(1, 1, 0, 0)。类似地，与查询B, C相对应的向量是 (0, 1, 1, 0)。查询与节点对查询的满足度sim即两向量夹角的余弦(2)因此，Pj的资源级是(3)其中，是节点Pi和Pj之间距离的反比函数。物理距离越近的节点之间的D值越大。距离近的节点评估的权重更高，鼓励距离近的节点多交互，避免网络拥塞的影响。每一个自治域有一个最低SR值，其中，i, j, k分别表示自治域在IPP中的层号、级数和在该级所处位置。由各自治域内节点根据实时负载和信息交互情况决定。研究显示16典型的纯分布式P2P系统Gnutella和集中式P2P系统Napster中，26%的Gnutella节点不共享数据，20%40%的Napster节点很少或不共享文件。 假如一个域内节点的SR值小于该域的，则认为该节点是一个free rider。新节点x选择其内NN与之共享最长IP地址前缀，同时与其延时在x可接受的最大延时Rx内的自治域加入。当新节点x试图加入一个饱和自治域时，该饱和自治域首先丢弃free rider，使得新节点x可以加入，当没有free rider时，节点x与该完全自治域内与信息中心平均距离最远的节点y比较。1）如果节点x距离该饱和自治域信息中心平均距离较节点y大，则节点x询问与该自治域相邻的域序列号比其大的自治域；2）如果节点x距离该饱和自治域信息中心平均距离较节点y小，则节点x加入该饱和自治域，节点y成为一个新节点，询问与该自治域相邻的域序列号比其大的自治域，重复加入过程，直到所有节点全都加入IPP中。与传统层次混合式P2P覆盖网不同，IPP只在连续的两个级或者层之间进行信息更新和备份。传统层次结构信息更新和备份向更高层递归进行，缺点在于级数越高的节点，备份的信息越多，以致地位越高越重要，将使得级数越高的节点越容易受到攻击，而其崩溃所造成的损耗也更大，降低了系统的容错性。4 IPBGA网格信息汇聚协议性能分析使用GT-ITM17拓扑生成器根据实验需求产生不同数量级节点个数的transit-stub拓扑图。在stub域中随机选择节点作为覆盖网中的普通节点。计算出拓扑图中所有节点对最短路径的延时，将之作为覆盖网中节点间的距离。信息中心基于距离和信息交互频率从transit域中选取。4.1 IPP效率P2P研究中通常根据搜索的查全率和查准率验证系统的搜索效率，但其验证结果跟文件分布方式密切相关。因此，在本文从路由表规模的角度考量。图4比较信息索引（II）和传统层次P2P结构（THP2P）18中优化路由表（OPT）在不同节点规模下随层、级增加产生的信息规模。纵坐标采用对数标度，8条曲线对应从101108的8种不同节点规模。图4(b)可看出，对每一种节点规模，层和级数达到一个固定值Li()后，II大小保持不变。当层和级数小于Li时，一个小范围的L取值使得II的大小随着层和级增加而显著减少，从图4(a)可知，对于THP2P也存在OPT和级数的相类似关系。因为层次结构与单纯的平面结构相比，随层次增加，所涉及信息的条目大大减少。然而，自治域规模也会随层次增加而减小，因而当层次数超过了Li时，图4 不同层次数下OPT与II规模的比较随层次增加，II或者OPT规模都不会有显著变化。比较图4(a)和图4(b)，考虑到y轴是对数标度，显然IPP中II比THP2P中OPT的规模要小很多。图4中的节点规模涉及了很大范围，为了便于比较，图5中显示了2 000个节点的IPP随自治域规模不同，II的规模变化。每条曲线表示系统在不同层次数划分下随自治域规模变化，II的规模变化，图5(a)显示所有范围的自治域规模，图5(b)将自治域规模限定在一个重要范围。H表示系统层次数。从图5可知，M取值范围不同，II规模并不一样。M处于0到某一固定值Mi（i表示层或级的数目）这一区间时，II规模减小得很快，而当M属于Mi到N时，II规模减小得非常缓慢。因此当M有很多选择时，针对不同层次数可以选取大于Mi的最小整数作为M值，从而可以使II规模接近最小值。图5 不同自治域划分下II规模（N=2 000）从图5可以看到当H2时，自治域的划分个数超过一个固定值后，随着H的增加，II的大小并没有很显著地减少，结合图3的结果显示IPP具备良好的可扩展性。因此图6中仅比较当H=2时II和OPT在2000个节点的系统中所需涉及的信息规模。很显然II规模比OPT规模小很多，并且当M值大于Mi(i=2)时，随着M的增大，II规模并无显著变化。4.2 IPP损耗为了分析IPP的运行情况，首先提出一个5 000个节点作为客户的随机系统。设定每个自治域至少有1个节点，最多有11个节点，同时假定IPP中没有非正常退出系统的节点。在模拟实验中，取远小于实际情况的free rider数，假定只有0.758%的节点是free rider。图7显示了5 000个节点加入时IPP和I-ZigZag12的负载情况比较。图7显示，新节点加入覆盖网过程中平均打扰9个节点，比I-Zigzag中平均20个节点的打扰率要低。最坏情况下，一个新加入节点不得不打扰15个（占系统的0.3%）系统节点，少于I-Zigzag中打扰图6 不同自治域划分下II与OPT规模比较（N=2 000）28个（占系统的0.56%）的情况。随加入节点数增加，系统规模进一步扩大，而节点加入负载并未随之显著增加或减少。事实上这些值相当平均的分布（如图7中稠密部分显示）。因为根据IPP的形成和特性，节点加入只需联系有限范围的很少数几个自治域，所以被打扰节点数目很少。我们的实验还发现free rider比例越大，节点加入所打扰的系统中节点越少，因为IPP通过丢弃free rider来减少新节点加入饱和自治域时的波动（churn），free rider越多，则自治域越不可能成为饱和自治域。图7 节点加入负载（IPP vs I-Zigzag）为了分析协议的综合性能，将IPP与混合式P2P路由协议（HP2P）14进行比较，图8给出不同自治域范围下信息交互所占用系统总带宽的比较，并比较了不同自治域范围下IPP中周期性与触发制信息交互策略对系统整体带宽的损耗，采用触发机制时包括信息中心在内的所有节点只在自身状态改变时进行信息交互，节点状态包括空闲、正常和繁忙。图中横坐标表示自治域大小，纵坐标表示总带宽消耗。图8中曲线逐渐下降，因为随着自治域规模增大，信息中心逐渐减少，其间交互信息减少，同时信息交互能在同一自治域完成的几率增加，减少了信息传递频率和跳数，所以系统总体带宽消耗减少。T表示同一时段内触发机制发生的次数。由图8中可以看出触发制的带宽损耗要小于周期性交互，且节点本身能力越强，使触发次数越少，能减少系统带宽损耗，因此如果能较合理的设置节点交互信息触发阈值，则触发机制是较好的信息交互策略。图9给出不同自治域范围下IPP和HP2P总体性能损耗比较，同时反映不同信息更新策略对系统总体性能的影响。从图9可知IPP损耗小得多，因为IPP中查询转发不再是扩散方式，实际上仅向相邻最大聚集度节点转发；同时，充分利用信息中心节点的优势，进一步提高了系统效率；自治域邻居增多，对自治域及其内部节点而言，单跳内可交互节点数成倍增长，可查询到的信息大大增加，而单个节点的处理负担和带宽消耗并无显著增加。图8 IPP与HP2P带宽损耗比较图9 IPP与HP2P处理损耗比较4.3 IPP容错性为了验证IPP的容错性，比较了Chord，Hybrid10和IPP的搜索失效率。将1 000个数据文件分布在1 000个节点中，每个数据有4个备份，比Hybrid中使用的6个备份更少，以比例p（20%50%）的失效率随机选取节点退出系统。执行10 000次随机搜索，每次成功的搜索被记录下来然后进行统计。表1记录了节点失效率从20%50%时3种系统的搜索失效率。表1搜索失效率系统节点失效率 p20%30%40%50%Chord (k = 1, r = 6, d = 20)00.0020.0100.016Hybrid (k = 2, r = 3, d = 20)000.0090.014IPP (H=2, M=10)0000其中，k表示Chord环数目，r表示后继数目，d表示后继列表长度，M表示每个自治域中节点个数，H表示IPP中层和级数目。表1显示，IPP总能找到合适的数据，并且与Chord和Hybrid相比有更好的数据可靠性。图10分析了IPP中自治域内节点个数（M）对数据可靠性的影响。图中显示自治域规模较小时，当节点失效率达到70%以上，IPP才开始出现搜索失效。节点失效率一定时，自治域规模增大，搜索成功率增加。因为：1）自治域规模增大使更多有能力的节点有可能成为信息中心；2）三信息中心承担不同职责，与传统单超节点的负载相比减轻很多；3）三信息中心相互备份，同时上层和上级自治域中有相关备份，与其他P2P系统相比提高了系统容错性。图10 不同节点规模失效率5 结束语本文基于体系结构角度，结合SOA技术、P2P架构和网格技术，提出一种基于虚拟组织的网格体系结构，在网格虚拟化将所有物理资源和任务抽象为信息的基础上，通过提出信息汇聚协议，将资源对任务的需求信息和任务对资源的要求提升为信息服务，从而将资源分配和任务调度转换成基于信息汇聚协议的信息匹配，能较好适应资源和任务的分布性、动态性和异构性，拥有网格系统的高效性兼具P2P系统的可扩展和容错性，采用将虚拟组织分解为信息服务层和协同工作层的方法，有助于构建物理信息的全局视图，是一种较新颖和具有一定理论价值的网格体系结构，实验和理论分析证明其核心的信息汇聚协议具有较高搜索和信息处理效率，且对带宽和处理器的消耗较少。进一步的工作包括基于信息聚类网格体系信息汇聚协议的协同工作研究。参考文献：1FOSTER I, KESSELMAN C. Globus: a metacomputing infrastructure toolkitJ. International Journal of Supercomputer Applications, 1997, 11(2):115,128.2W3C. Web services architectureEB/OL. /TR/ 2003/ WD-ws- arch-20030808/, 2003.3陈明,杨广文,王鼎兴.支持高并发度的大容量媒体库J. 软件学报,2006,17(4):915-924.CHEN M, YANG G W, WANG D X. Large-capacity media library supporting highly simultaneous accessJ. Journal of Software, 2006, 17(4): 915-924.4ZHUGE H, SUN X P, LIU J, et al. A scalable P2P platform for the knowledge gridJ. IEEE Transactions on Knowledge and Data Engineering,2005,17(12):1721 - 1736.5UPPULURI P, JABISETTI N, JOSHI U, et al. P2P grid: service oriented framework for distributed resource managementA. 2005 IEEE International Conference on Services ComputingC. Orlando, USA, 2005 .347-350.6KARL A , MANFRED H, MAGDALENA P, et al. Improving data access in P2P systemsJ. IEEE Internet Computing, 2002,6(1): 58-67.7SUNAGA H, OKA T, UEDA K, et al. P2P-based grid architecture for homology searchingA. Fifth IEEE International Conference on Peer-to-Peer ComputingC. Konstanz, Germany, 2005.148 - 149.8TSAI W T, CHEN Y N, FAN C . PESOI-process embedded service-oriented architectureJ. Journal of Software, 2006,17(6): 1470-1484.9STOICA I, MORRIS R, KARGER D, et al. Chord: a scalable peer-to-peer lookup service for internet applicationsA. ACM SIGCOMMC. San Diego, USA, 2001. 149-160.10FLOCCHINI P, NAYAK A ,XIE M. Enhancing peer-to-peer systems through redundancyJ. IEEE Journal on Selected Areas in Communications, 2007,25(1): 15-24.11PORTMANN M, ARDON S, SENAC P. Peer-to-Peer Networks - Promises and ChallengesM. Book Chapter in Ambient Intelligence, Wireless Networking and Ubiquitous Computing, Artech House, Norwood, MA, USA, 2006. 143-166.12TRAN D A, HUA K A, DO T T. A peer-to-peer architecture for media streamingJ