论文部分内容阅读
近年来随着Internet的飞速发展、网络带宽的成倍增加以及计算机计算能力的大大提高,对等网络(Peer-to-Peer,简称P2P)成为了计算机网络技术研究领域的一个热点。P2P网络通过对等和分布式的方式,在网络中不同节点间提供空闲的CPU处理能力,磁盘空间以及网络带宽的共享。P2P网络中的节点既是服务使用者,也是服务提供者。从C/S模式到P2P模式的发展,Internet上的共享行为被提升到了一个更高的层次,P2P网络在分布式计算、协同工作、搜索引擎、文件交换等方面有着广泛的应用前景。对等网络系统的成功与否不仅仅在于其网络结构的合理和有效,很大程度上取决于其资源搜索机制的灵活性和可扩展性。除了采用中央目录服务器的集中式对等网络外,从网络拓扑上对等网络大致可以分为无结构对等网络和基于分布式哈希表(DHT)的结构化对等网络。无结构对等网络采用类似泛洪(Flooding)的盲目搜索机制,虽然可以支持灵活的查询,但搜索的效率和可扩展性都较低。Flooding算法以Gnutella为代表。DHT方法的可扩展性和查找效率都较高。利用DHT实现的算法比较多,比较知名的包括最早的Plaxton算法及其变种Tapestry,微软提出的Pastry,伯克立和AT&T提出的CAN ,MIT提出的Chord等等。Chord是一种环形拓扑的结构化对等网络结构,因其结构简洁,具有可扩展性而被广泛采用。本文在对经典的Chord算法深入分析的基础上,通过扩展Chord的路由表,提出了双向三阶Chord(Dual Order-Three Chord ,DOTChord)算法,此算法主要在以下两个方面对Chord进行了改进:(1)增加Chord原有路由表的指针密度,即把Chord的Finger表由2阶变为3阶,这样增加了每个节点维护的路由表的长度,使得每个节点指向的后继节点个数增加,增大了找到目标节点的概率。(2)变Chord的单向查找为双向查找,即在Finger表的基础上增加一个R_Finger表,R_Finger表实际上是Finger表的一个反转,是一个逆向的路由表,这样Chord在选择下一跳的节点的时候就有顺时针和逆时针两个方向,使得查找能更快的接近目标节点。此算法结合了三阶Chord和双向Chord的优点,使得系统的查找策略可以根据关键字在Chord环上的位置离当前节点的远近来确定查找方向,减少了转发次数,缩短了搜索路径的长度,缩小了搜索延迟,提高了搜索效率。最后通过模拟实验证明双向三阶Chord算法继承了Chord算法简单、高效、可靠、负载平衡及开销少的优点,与经典的Chord算法相比,极大地提高了Chord的查找效率。