杜经纬，张 岳

（1.运城学院 计算机科学与技术系，山西 运城044000；2.中国科学院 数学与系统科学研究院，北京100120）

0 引 言

目前的异构环境下的计算资源共享与聚集系统往往采用集中式的结构，存在着规模小、可扩展性和稳健性差的缺点［1－3］，同时它们能够计算的问题局限在没有数据依赖的主－从 （Master－worker）模型 的 并 行 计 算［4－7］。 最 近 后 续 的非集中式的网络拓扑，例如对等网络结构［8－9］、层次结构［10］、基于组的对等网络、基于代理网络的结构［11］、带超级节点的对等网络等［12］相继被采用，在一定程度上解决了传统的计算平台的不足。

本文提出的基于树型层次结构的计算资源共享与聚集系统 （tree－based layered sharing and aggregation，TLSA）也是一种非集中式的网络拓扑结构。TLSA系统由对等网络环境下的空闲节点组成，形成一个平衡的树型层次结构，节点可以寻找到系统中最近最合适的空闲计算资源来完成大量的子任务。TLSA中子任务是一个很重要的概念，它是由一个大的分布式计算问题所划分后的编程单元，是粗粒度的并行计算的基本单元。TLSA系统中的每个节点都可以请求子任务的执行，该请求过程通过邻居节点和高效的资源发现协议就可以路由到最合适的空闲计算节点。树型结构的网络拓扑通过自组织的可靠性协议来维护，同时保证了系统的比较低的消息通信量和平衡的处理器负载。本文的研究点关注在网络拓扑的构造与维护，最后通过一个简单的资源分配算法对TLSA系统进行了测试与性能分析，测试结果表明对于分布式计算中大量的子任务TLSA可以很快的完成，而且具有比较低的消息通信量。

1 树型拓扑的体系结构

TLSA系统根据网络拓扑结构和资源管理的功能需求，可以划分为3个方面的层次结构，从下层到上层分别是节点连接协议层、资源可用性协议层、计算资源的发现协议层。

节点连接协议层：它定义了对等网络中维护应用层覆盖网络的节点连接协议。它保持了一个类似于B树的拓扑结构［13］，所以它是一种平衡的结构，每个节点具有m到2m个孩子，树的高度不会超过Log（N），N为对等网络的节点总数。该协议还描述了节点加入和退出网络的算法，描述了该树是如何保持平衡及节点异常退出和如何保持这种平衡结构。

资源可用性协议层：描述了空闲计算资源相关的信息，TLSA中的每个节点都会存储其在B树中的全局状态和分支状态，而且可以完成它自己和其双亲节点的更新，重新计算资源的状态。该协议使用验证技术使树的上层节点避免网络消息的洪泛，同时维持精确的可用性信息，使网络的利用率最高。该验证过程技术是稳定的与可靠的。

计算资源发现协议层：它使用了可用性协议中的每个分支的信息，从根节点自上往下来路由空闲的资源。它试图发现最邻近、最合适的空闲计算资源来给子任务。所以该资源搜索过程是通过一系列的网络跳数来完成，网络跳数是依赖于树型结构的高度，它不会超过Log（N）。

在这3个协议层之上，应用开发员可以实现不同的资源分配策略，利用这种三层的平衡树型结构，处理空闲的处理器资源，TLSA系统也可以把网络中的其他资源考虑进去，例如内存资源，网络带宽资源与空闲磁盘空间等，这些都可以在资源可用性协议里面完成验证。

2 树型拓扑的工作机制

2.1 节点的连接协议

应用层覆盖网络是一种树型的层次结构，与分布式哈希表不同的是，分布式哈希表中依赖于统一的资源描述，而且存储的是树的索引的一部分，通常用于范围查询。TLSA的这种平衡树结构使每个节点只需要维护树中的一个节点，更加适合于非统一的资源分配，因为B树在节点加入和退出的时候可以自动的维持平衡，允许节点有多余两个的孩子节点，使树的高度维持在对数函数级别。

树型结构的最要的功能是聚集位置邻近的计算资源。TLSA中一个节点可以与最邻近的通信，因为它们都是节点的兄弟或者子孙节点，而且它可以通过双亲节点达到其他的区域。关于最邻近的节点通信，TLSA使用了一个高效的方式来组织节点，即是通过物理位置邻近，它是通过节点的IP地址来判断的。根据文献 ［14］中的方法，节点可以很快的判断并从树型结构中进行插入，同时保证了低延迟与高带宽。

TLSA中的树与原始的B树有一些区别，在B树中的节点可能维持超过一个值，该值为IP地址。那些B树将转化成一组兄弟，网络中每个节点拥有一个值，通过这种一对一的映射，每个节点完成了树型结构的拓扑管理。而且每个内部节点具有一对值，它表达了节点与子孙节点的IP地址的间隔。这些间隔在树型结构中当节点加入和删除的时候被用来完成路由消息。它们之间的区别见图1。与B树一样，TLSA中也存在一个常量m，节点具有m～2m个兄弟节点。如果这个限制超越了，树型结果必须重新建立平衡。当一组兄弟节点具有超过2m个节点，它必须划分成2组。另外一个方面如果它少于m个节点，它必须寻找一个相邻组并且加入进去。

图1 B树与TLSA的层次网络拓扑结构

考虑到容错的问题，每个节点知道其同一层级的k个前驱和k个后继，当节点异常退出，树型结构将通过这些前驱和后继来完成维护，因为节点的离开会影响到它的兄弟和双亲节点。很明显的是k的设置是一个协议，它考虑到了树型结构管理的负载和容错特性。节点加入与退出的描述如下：

具有两种类型的操作会影响到网络的结构，另外作为一个边界效应，必须有一个重新平衡触发机制。节点加入系统往往是容易的，当一个节点请求加入的时候，请求消息通过树型结构进行路由。

请求过程寻找新节点的IP地址所包含的间隔情况，然后它将达到具有最邻近的IP地址的节点，新节点将成为最邻近的兄弟，新节点更新它的邻居的地址。当双亲节点验证了新节点后，如果双亲节点的孩子超过了2m，就完成组的划分，该规律和B树类似。当一个节点加入一个组之后，每个组内成员检查该组内的数目，计算数目是通过参考节点的前驱和后继节点列表完成的。当一个根节点具有k个前驱和k个后继后，它将寻找一个子孙的叶子节点，然后成为树的新根。这种方式限制了使根不会超过2k个节点。

当节点离开的时候，它必须检查自身的孩子节点情况，如果有孩子节点，它将寻找一个叶子节点使其成为所有孩子的双亲。这个过程就像创建一个新根节点类似。如果节点没有孩子，那么它将验证它的兄弟节点和双亲节点，然后更新它的地址列表。和节点的加入过程一样，如果双亲节点接收到了节点离开消息，它将检查孩子节点数目是否小于m，如果小于m，它将请求前驱节点或后继节点，发送它的孩子直到其达到m。如果所有的孩子都不超过2m，它们将成为一个分支。

2.2 资源可用性协议

为了使用资源发现协议来寻找空闲的计算资源，每个节点内部必须存储它子孙相关的信息，而且更加多的是与分支相关的信息。它描述了分支上大约的空闲处理器的数目，最大计算能力和到达目的节点的最小网络跳数。通过这种方式可用性信息的管理具有可扩展性、因为它不只是依赖于节点的数目。

每个节点的分支上存储的信息必须和它的双亲通信，这样才可以高效的把路由请求传递到空间计算节点。所以每个节点不仅具有分支的信息，而且具有它的子分支的信息。用这种方式信息的发布就是很关键的，因为它保持更新，同时要避免网络洪泛，特别是在根节点附近并且每层上具有很少节点的情况。这种发布的过程是通过资源可用性协议来完成，基本上当一个节点接收到一个改变它的孩子节点的消息通知的时候，它将决定是否通知它的双亲。通过具有最大计算能力 （computing capacity，CC）和到达目的节点的最小网络跳数 （network hop，NH）的限制，这个过程就十分简单。内部节点在它的孩子节点和自身必须分别重新计算新的CC和NH的最大值和最小值。如果这些值改变了，立刻重新路由新的通知消息给它的双亲节点。

这个问题随着TLSA计算资源节点数目的增加而出现，因为当一个节点已经准备好的时候，它的祖先节点也在增加。如果通知验证随着状态改变而发送，根节点将通知所有节点，可能会导致树型结构顶部的高消息通信量。为了解决这个问题，TLSA中在树的顶部设计了一个延缓消息通信机制，减少因为路由到顶部的消息量。

2.3 计算资源的发现协议

正如前面所描述的，当节点有许多子任务需要计算时，它将请求网络发现空闲的计算资源，该过程的完成就是资源的发现协议，它使用资源可用性协议层描述的信息来判断。通过启发式规则，它将试图分配最快，最邻近的空闲节点，使子任务的完成最快和最合适。

当一个节点接收到消息需要计算n个子任务的时候，它首先检测其自身是否已经处于准备状态，如果准备好了，它从消息中获得一个子任务。然后它把剩余的子任务根据每个分支所拥有的空闲计算节点来分配给它的孩子节点，那些具有大的计算能力CC和比较小的网络跳数NH的空闲节点具有优先级。如果所有的孩子节点不能够完成所有的子任务，那么一个带有最后子任务的新的消息将发送到父节点，以便其可以达到其他距离比较远的分支。当这个消息达到了树型结构的根节点时，它将不能发送到其他的分支了，它将返回最原始的初始化节点，这也意味着TLSA中没有空闲的计算资源可以利用。这里每个孩子节点有空闲节点和它的分支节点的空闲域，计算能力域用来描述最大的计算能力max.power，网络跳数域用来描述到达目的节点的最小网络跳数min.hops。空闲资源的发现算法如下所描述。

discover（msg）｛

if i＿am＿ready｛start＿task；msg.num＿tasks－－；

｝

while msg.n＞0or branch＿full｛

for i in children｛

if （i.power ＞ ＝ max.power）and （i.hops ＜min.hops）

max＝i；

｝

add＿task＿to （max）；

msg.num＿tasks－－；

｝

if msg.num＿tasks＞0｛

if i＿have＿father

send＿father （msg）；

else

send＿client＿node（msg）；

｝ ｝

最坏的情况是网络中把子任务分配给叶子节点，这样请求过程必须从树型结构的根部到达终端节点，这个也是消息所经过的最长的路径。在树型结构中每个分支上的空闲计算资源的发现都是并行的进行的，而且从终端节点到树的根部也是执行相同的过程，最坏所有的资源搜索的过程不会超过O（2logm N）步的网络跳数，N为TLSA中的所有节点数，所以这样使网络的资源发现协议具有可扩展性与高效性。

这种网络拓扑是一种比较好的结构，节点之间的相互协同能够使网络上的消息路由到最合适的目的节点，但是当网络中的节点频繁异常失效时，接收方并不是有质量保证的。鉴于这种原因，当使用超时机制来搜索资源的时候，所有的原始节点和目的节点在资源发现阶段必须避免这个问题。

3 系统测试与性能分析

3.1 资源发现时间

TLSA的测试是通过模拟器来完成的，模拟器通过OMNeT＋＋模拟框架［15］。由于TLSA关注的网络拓扑的维护，所以资源分配方式上使用了简单的调度算法，即只要发现了资源，就分配子任务，类似于先来先服务FCFS调度。测试性能指标关注的是空闲计算节点的发现时间、消息的通信量与处理器的负载。每个测试过程都是通过改变TLSA中的节点数目、B树的参数m等来体现网络拓扑的尺寸与协议对系统性能的影响。

模拟器中一共设置了50 000个节点，m的值为从6到10。调整子任务的数目与数据文件的大小来重新设置实验环境。TLSA中有3个约束条件：网络延迟大约为200ms，网络之间的连接速度为1Mb／s，节点的平均计算能力被设置为2000MIPS。

测试的时间体现的是节点数目和孩子节点数目对资源发现速度的影响程度。正如所期望的，在n个请求中到达最后一个空闲计算节点的网络跳数时间复杂度为O（2 logm n）。因为这个原因，当系统中的n增加的时候，TLSA的网络拓扑有比较好的性能。空闲计算资源的发现时间可以通过图2中显示，它是呈对数函数增加趋势。m＝4，TLSA可以在2.5s内完成到大约9600个子任务；m＝10，1.3s内完成到大约9600个子任务。

图2 TLSA中资源发现时间随子任务数的变化

3.2 消息通信量

对于TLSA系统的网络消息通信量和处理器的负载在两个设置环境下进行了测试：节点普通的参入情况和高度活跃的情况。正常的活动意味着系统中有一定的消息请求，并且随机的选择节点，但是网络拓扑并不是非常忙碌。在高活跃情况下，每个节点都是处于繁忙状态，持续的接收到新的消息请求。消息通信量通过每秒钟处理的字节数来体现。处理器的负载在模拟过程中更加难以测试，但是在处理器上的每个消息几乎是常数，所以也是通过每秒钟处理器中处理的数目来体现。表1和表2显示了正常情况和活跃情况下的测试结果。它们显示了m的值与还有树的高度变化情况 （m＝10，网络带宽为1Mb／s），也体现了平均的处理器负载和最大处理器负载情况。在网络中50000的节点数目下从根到叶子的消息通信量。

表1 正常情况下的处理器负载与消息通信量的测试结果

表2 活跃情况下的处理器负载与消息通信量的测试结果

从表1、表2中可以看出，资源发现协议受到m的影响，TLSA系统的整体负载随着网络拓扑树的高度而变化，所以需要在树的高度和m之间进行平衡。除了这些外，通过使用资源的可用性协议，在正常的参入情况下，叶子节点处的网络消息通信量和处理器的负载比根节点处的要大。网络中控制的消息通信量几乎只有1KB／s，它是小于整体网络带宽1Mb／s的1%，这些测试结果是具有重要意义的。在TLSA的高度活跃情况下，节点处的性能因为比较高的处理器负载和网络消息通信量而受到影响。

从表1和表2中看出，TLSA的消息控制负载比较低。在正常的情况下网络消息通信量是1485B／s，处理器的负载只有5.77条／s。在系统活跃的情况下网络的消息通信量为21947B／s，处理器的负载为65.3条／s，这些都是系统活跃比较特殊的实验情形。

4 结束语

本文提出了一个基于树型层次结构的计算资源共享与聚集系统TLSA。通过模拟测试结果表明对于大规模的子任务，TLSA可以在很短的时间内寻找到空闲资源，而且网络消息通信量不超过O （logmN），具有低消息通信量、非集中性、可扩展性、自组织特性。下一步的工作是在真实的环境下测试TLSA的性能，同时把更加多并行计算问题运用到TLSA系统之上。

［1］Anderson D P.BOINC：A system for public－resource computingand storage ［C］.Proceedings of the Fifth International Workshop of Grid Computing.Washington，DC：IEEE Computer Society Press，2004：4－10.

［2］Franck Cappello，Samir Djilali，Gilles Fedak，et al.Computing on largescale distributed systems：Xtrem web architecture programming models security tests and convergence with grid ［J］.Future Generation Computer System，2005，21 （3）：417－437.

［3］Andrade N，Costa L，Germoglio G，et al.Peer－to－peer grid computing with the ourgrid community ［C］.Proceedings of the SBRC－IV Salao De Ferramentas，2005.

［4］Michele Amoretti，Francesco Zanichelli，Gianni Conte.SP2A：A service－oriented framework for P2P－based grids ［C］.New York：Proceedings of 3rd International Workshop on Middleware for Grid Computing，2005：1－6.

［5］Shudo K，Tanaka Y，Sekiguchi S.P3：P2P－based middleware enabling transfer and aggregation of computational resources［C］.Proceedings of the IEEE International Symposium on Cluster Computing and the Grid.Washington，DC：IEEE Computer Society Press，2005：259－266.

［6］Anglano C，Canonico M，Guazzone G，et al.Peer－to－peer desktop grids in the real world：The share grid project ［C］.Proceedings of 8th IEEE International Symposium on Cluster Computing and the Grid，2008：621－626.

［7］BUTT A R，FANG X，HU Y C，et al.Java peer－to－peer and accountability：Building blocks for distributed cycle sharing［C］.Virtual Machine Research and Technology Symposium，2004：163－176.

［8］Merz P，Gorunova K.Efficient broadcast in P2Pgrids ［C］.Proceedings of the IEEE／ACM International Symposium on Cluster Computing and the Grid，2005.

［9］Mason R，Kelly W.G2－p2p：A fully decentralized fault－tolerant cycle－stealing framework［J］.ACSW Frontiers，2005：33－39.

［10］Jerome Verbeke，Neelakanth Nadgir，Greg Ruetsch，et al.Sun microsystems inc framework for peer－to－peer distributed computing in a heterogenuous and decentralized environment［C］.Proc of the Third International Workshop on Grid Computing，2002：1－12.

［11］Neary M O，Phipps A，Richman S，et al.Javelin 2.0：Javabased parallel computing on the internet［G］.LNCS 1900：6th Int’l Euro－Par Conference. Springer Verlag，2000：1231－1238.

［12］YANG B，Garcia－Molina H.Designing a super－peer network［C］.Proceedings of the 19th International Conference on Data Engineering，2003.

［13］Jagadish H V，Ooi B，VU Q，et al.Vbi－tree：A peer topeer framework for supporting multi－dimensional indexing schemes［C］.22nd IEEE International Conference on Data Engineering，2006.

［14］Freedman M，Vutukuru M，Feamster N，et al.Geographic locality of IP prefixes［C］.Berkeley，CA：Internet Measurement Conference，2005.

［15］OMNeT＋＋模拟框架 ［S］.http：／／www.omnetpp.org／，2010.