一种基于ＤＨＴ混合型对等发现服务的算法设计.doc

一种基于混合型对等发现服务的算法设计基于DHT(Distributed Hash Table)的分布式资源组织、管理与发现服务目前已被应用于网格1、Web服务2、对等计算等分布式环境中，成为构建大规模分布式应用的基础结构。然而不同网络场景下节点和网络连接的动态性不同，要求资源组织、管理与发现服务能够适应系统的不同变化程度，保证部分节点或网络失效时服务的可用性3。例如，Internet环境下一个10万节点的Gnutella系统每秒钟仅有19个成员关系变化4；而移动Ad hoc网络的变化则相对较快5，尤其是未来P2P技术的重要应用场景、军事战术通信系统的变化程度更难以确定。 现有发现服务都有自己特有的网络应用场景。其性能在某一种场景下运行良好，但可能会在另一种场景中下降。影响发现服务的因素包括网络的波动（包括节点的加入、退出、失败、迁移、并发加入过程、网络分割等）、网络延迟、传输带宽和对等点的计算能力等4。目前，还没有一种方法能够适应不同的网络环境和动态变化程度。 1 相关工作 目前大部分研究均采用DHT进行资源组织、管理与发现，如CAN、Chord6、Pastry、Tapestry、Koorde、Viceroy采用多跳路由算法进行发现服务，即路由表仅需要维护O(logN)或O(1)个节点状态，发现服务仅需要O(logN)跳路由。某一个节点加入或退出网络时，最少需要O(logN)或O(log2N)条消息维护路由表的一致性。每个节点维护有限的成员关系信息，有效地解决较大网络波动问题，但它是以增加延时为代价的。由于它不必维护去往所有节点的路由，仅在没有去往目的节点路由时才按需进行路由发现，可将这种发现服务称为按需发现服务。 另外一种是Kelips系统7。A.T.Mizrak等人8及A.Gupta等人9采用基于超级点结构的单跳路由算法的发现服务，每个超级点路由表维护全局路由状态，路由表开销为O(N)或O（N），但每个发现服务仅需要O(1)跳。其发现速度快、延时小，但维护代价高，受网络波动的影响大，称之为主动发现服务。 在变化速度慢的网络环境下主动路由的等待延时最小，且其查找速度快。随着网络波动加快，为了保持查找率，主动路由必须减少路由表的维护周期。由此它不仅加剧了维护开销，使性能下降；而且其更新速度也无法跟上网络波动速度。按需路由只需维护正确的邻居关系，则可以保持查找率不变或平稳下降，但这是以增大延时为代价的。研究4 也发现Chord算法应用在DNS服务时，最差需要20跳才能解析DNS。导致跳数增大的主要因素是路由节点的失败概率。只要选择可靠性高的路由节点就可以大大减少路由链路长度。 因此，网络波动速度处于静止或缓慢时，可选择主动发现服务的路由策略来提供快速准确的查找，获得较小的延时；当网络波动增大，则可选择按需发现服务且通过选择多条路由路径来保持查找率不变或平稳下降；当网络波动快速且剧烈时，只有选择洪泛算法，因为也只有洪泛算法才能适应这种变化。 2 ROAD设计 选择主动路由和按需路由构成一个新的混合路由算法ROAD（Routing On Active and Demand）。它主要是在不同的波动情况下保持路由的效率，同时使请求的路由路径尽量短，以此来获得系统对波动程度高效率的反应。 2.1ROAD结构 如图1所示，ROAD结构主要包括两个部分，即主动路由和按需路由。对于一个有N个节点的P2P网络，通过DHT算法使所有节点分布在一个环上（称之为外环）。DHT算法为每个节点分配一个ID。环采用Chord路由算法，同时选择M个超级点构成一个内环，内环采用主动路由算法。所有点采用同一种DHT算法分配ID。 2.2 ROAD路由 2.2.1 加速路由表构造算法 在路由信息的处理方式上，继承了Chord对路由信息的划分，即前驱（Predecessor）、后继列表（Successor List）和Finger表。其中，把Finger表改造成了加速路由表（Qfinger）。令节点ID号的长度为m位，每个节点的Qfinger表最多包含m条记录。Qfinger算法如下： 除了需要构建Qfinger表以外，超级点还要维护超级点表和负责的弧内普通点的索引表。一个超级点表和索引表如图1(b)所示。 2.2.2 混合路由策略 如何在多种路由策略之间进行自适应的、平滑的切换是混合路由的关键5。ROAD采用了一种自动的切换机制，即当超级点表出现如下两种状态之一时，可以自动切换到按需路由策略：没有去往目的节点的超级点（可能是由于节点加入信息还没有及时扩散）；访问负责目的节点的超级点失败（可能是由于网络波动速度加快导致查找失败）。 大部分发现服务的路由算法都通过设定等待周期来判断超级点访问失败。然而由于不同的网络应用场景，很难找到一个通用的等待周期。可以通过借鉴工作5中的QoS度量方法来自适应地计算等待周期。 2.2.3 ROAD路由算法 基于加速路由表和切换机制，本文给出了ROAD路由算法。以下为超级点Si路由算法的伪代码（其中n为超级点数量，k为Qfinger表记录数，src为前一跳的节点ID）： 此算法与Chord算法比较可以看出，(6)(15)增加了主动路由功能，并根据网络状态自适应地调整等待周期，在获得较快路由的同时没有增加任何多余的网络负载。算法的复杂度与Chord相同。 2.3路由恢复 节点加入或失败的事件会导致路由表失效，从而降低路由的效率，因此需要恢复算法来定期更新路由表。 2.3.1 普通节点恢复 ROAD恢复算法类似Chord，即通过周期性地运行n.find_successor(n+2i-1)来访问Finger表每一条记录内的节点。Finger表中有log2N条记录，每条记录的更新跳数为O(log N)，Chord恢复算法复杂度为log2N×O(log N)=O(log2N)6。 为了减少恢复算法带来的开销，ROAD在更新Finger表时不是访问所有Finger节点，而是通过访问一次所在弧的超级点表，即可更新Finger表内所有超级点的记录。如果合适地选择超级点的数量，可以获得比按需路由低的维护代价。 命题1 ROAD中加速路由表的维护代价低于按需路由。 2.3.2 超级点恢复算法 主动路由对超级点依赖性大的主要原因是需要维护全局一致的超级点表。当出现节点加入或失败时，必须更新所有超级点，因此维护代价远高于按需路由。通过改进研究10的Chord广播系统，本文提出了一种幂次序组播算法。与Gnutella采用的类似洪泛算法和主动路由7,8以及网格11采用的Gossip算法相比，幂次序组播算法不会产生重复消息，所有节点获得消息的概率高，并且每级消息扩散数量k和扩算轮次i为最低。工作11证明Gossip算法在k=log M+c时，消息覆盖所有节点的概率较高；并且当i>6时，转发消息失败的次数会明显增加，即在107的网络规模下无法正常工作。本文算法k=log M，i=log M/（log log M），并且延时最低。 命题2 ROAD中幂次序组播算法消息扩散轮次和相对延时为O(log M/（log log M）)。 证明 根据算法可知k=log M，即每轮消息扩散到log M个点。令扩算轮次为i，则有 3 结束语 基于混合策略的思想，本文提出了一种动态环境中的P2P发现服务算法，可以根据波动程度在不同的路由策略之间切换以适应不同的网络场景。下一步的工作是以ROAD为基础，研究基于最小延时的超级点选择算法，使最小延时的超级点尽可能多地出现在路由路径上，从而提供最短延时的发现服务。如果ROAD采用不同服务质量的超级点选择算法，则可以扩展为面向不同服务的发现机制。 本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。