内容寻址网络中路径缓存定向多播路由算法

张伟哲，张宏莉，许 笑，吴太康

(哈尔滨工业大学计算机科学与技术学院，哈尔滨150001，zwz@pact518.hit.edu.cn)

内容寻址网络(Content Addressable Network，CAN)是基于多维空间结构的P2P网络［1］，利用分布式哈希表将数据和结点映射为键值，完成多维笛卡尔空间中数据存储与查询.与基于带弦环结构Chord网络、基于异或距离度量的Kademlia和机遇跳表的SkipNet等［2-4］结构相比较，基于多维空间的CAN网络可以结合网络测量信息和地域信息，有助于解决P2P覆盖网络的拓扑不匹配问题［5］.内容寻址网络上的路由策略是当前的研究热点.高效的路由机制可以快速地进行资源定位，降低资源加入和退出的带宽消耗.传统的路由方法主要包括:1)广播.当结点接收到查询消息的时候，将其转发到路由表中的每一项.这种方法缺点是网络中转发了大量无用消息，消耗了网络带宽，给系统引入了巨大的负担［6-7］.2)定向路由.根据网络延迟或邻居位置来选择一个转发目的地，通过贪心的方法逐渐接近目的结点［8-9］.此种方法虽然效果不错，但当被选中路径上出现结点失效时，必须通过回退的方法重新探测一条新的路径.回退再探测的过程非常消耗时间，难以做到快速路由响应和定位.此外，Wu等［10-11］提出通过增加路由表项来提高路由效率:每个结点在路由表中除包含自己的邻居外，还包含邻居的邻居，每个结点负责维护的路由表项数急剧增加;而且当网络中结点状态变化频繁时，结点更新各自路由表系统开销增大.

本文结合定向路由与广播路由的优势，阐述了内容寻址网络中定向多播路由算法的基本原理.考虑内容寻址网络的动态性与失效问题，引入扩展系数对定向多播路由算法进行空间维度扩展，降低集体失效的概率并避免路由失效发生.此外，为提高系统的可靠性和查询效率，将路径缓存技术与定向多播路由算法结合，进一步保证系统容错性并提升寻址效率.

1 定向多播路由策略

定向多播路由策略建立在内容寻址网络之上.其路由方法以多维空间逻辑结构为基础.假设多维空间的维度为d，那么逻辑空间中每个结点的路由表的项数至少有2d项(空间边界结点除外).在d维逻辑空间中，两个结点的位置关系在d维的坐标上存在偏序关系.因此，在转发消息的时候，如果目标在第i维度上的坐标值大于当前结点坐标的第i维，则向第i维正向邻居转发消息即可，不需要向负方向的邻居发送消息.图1是在二维逻辑空间下定向多播路由方法示意图.图1中的路由起始点为结点3，路由的目标结点为结点14.箭头为路由消息的流向.由图1可见，路由消息将流经结点3和结点14两个结点之间的所有结点.形成一个矩形路由区域.由于查询者和查询目标都是随机的分布在多维空间中，因此查询结点和目标结点的距离统计平均值应该接近于逻辑空间对角线长度的1/2.而查询结点和目标结点之间包含的区域统计均值将接近(其中，d为空间维度，Size为逻辑空间整体的大小).假设空间中有N个结点，那么查询结点和目标结点之间包含的结点数统计平均值为所以，定向多播路由给系统带来的消息负载应该是级别.相对于广播模式的O(N)有了明显的性能提升.当结点数量巨大(N值大)并且逻辑空间维度高(d值大)的情况下，定向多播路由方法相比广播模式降低了系统开销.

相对于定向路由的方法，定向多播路由方法对于结点失效具备更强的容错性，能够容忍路由过程中结点失效的情况.假设图1中结点12，结点9均失效.定向路由算出来的最佳路径为3—8—12—13—14.当按照定向路由的方法转发消息时，结点8转发消息到结点12.遇到结点12失效的时候，结点8将进行重新探测，并将消息由结点8转发到结点9.然而结点9也失效，因此将进行路由回退重新探测的过程.路由路径回退到结点3，而结点3重新选择将路由消息发给结点5.结点5收到消息后，计算的下一跳路由又为失效结点9，因此当结点5发现转发向结点9不可行时将再次选择将消息转发给结点6.最后通过路径3—5—6—10—14将消息送达目的.上述过程中，需要探测等待3次，路径回退1次.这4个过程将会降低系统的响应速度.而按照定向多播的方式当结点3要寻找结点14时，由于结点14在x，y坐标上的值都大于结点13，因此结点13会向x，y正方向上的邻居(结点5和结点8)发送路由消息.后面每个结点都通过这种坐标比较的方法来确定发送方向，并把消息转发到确定方向上的所有邻居.形成消息的流如图1中箭头所示的情况.当结点9和结点12失效的时候，仅打断了其中两条路径，而路由消息会通过路径3—5—6—10—14到达目的.因此结点的失效并没有影响路由查询的效率和结果.

图1 定向多播路由消息流向示意图

然而，在二维的情况下如果结点10和结点13都失效，那么定向多播路由方法同样不可行.对此，通过增加维度d来提升系统可靠性.在路由过程中比较坐标大小时，如果当前结点在第i维坐标已经大于目标结点，仍然向该方向转发路由消息，但需要将这样的消息进行标识.最多允许超过坐标区域转发k次，k值可以根据网络的动态情况来设定.所形成的路由消息覆盖区域将包含原来的定向多播路由方式所覆盖的区域.除非目标结点所有的邻居都已经失效，否则路由消息一定能到达目的区域.图2中短箭头为原始的定向多播路由消息的流向图，长箭头是在k=1的情况下，扩展定向多播路由方法下路由消息的流向图(数据流将覆盖图2中所示的灰色区域).通过图2可以看出原始方法的路径流向区域包含在扩展定向多播路由方法所覆盖的区域中.因此，如果出现访问结点14失效的情况那么只能是结点14的邻居均已经失效.这种情况下，结点14无法访问到的情况是不可避免的.

图2 扩展定向多播路由消息流向示意图

扩展的定向多播路由算法:

上述扩展定向多播路由算法中，设定扩展系数k=0则算法描述就是定向多播路由算法.

2 定向多播和路径冗余的结合

数据的冗余将增加数据在网络中的副本.有助于提高数据的查询效率.而在传统的冗余方法中，冗余的路径单一，冗余具有明显的偏向性——即对热点数据的冗余备份数较多，而对于较少访问的数据备份数量较少.为了解决这个问题，将路径冗余方法和本文的定向多播路由方法相结合起来，形成了等概率路径缓存定向多播算法.规定为:

1)数据加入网络时，加入消息的转发路径按照定向多播路由策略提出的定向多播方式进行转发;

2)数据查询消息的路由转发过程，也按照定向多播的方式进行转发;

3)数据在加入网络的过程中，按照概率p进行复制备份.

按照上述规则进行数据备份，冗余数据在数据加入起始结点和数据加入目的结点这两个结点坐标所包围的一个d维矩形区域内都存在冗余数据.如图3所示，数据资源从结点5开始，加入到网络中，并最终将数据索引存放到结点20处.按照定向多播路由方法，消息将流经结点5—6—10—13—14—15—18—22所围区域.在数据经过上述区域中的每一个结点的时候，按照一定的概率p确定是否要进行数据冗余备份.最后，在此区域中将会散布着结点5处加入的数据的副本(图2中的结点5，结点19，结点20，结点21所形成的方块).

图3 定向多播方式下路径冗余方法效果示意图

当另外的结点要访问结点20上的数据时，按照规则2，查询消息也按照定向路由的方式进行发送查询消息，那么查询消息过程如图4所示.

结点8发出查询结点20上数据的查询消息.结点8—10—12—13—14—15—17—18—22所围成区域为查询消息按照定向多播方法转发消息时覆盖的逻辑区域.箭头为查询消息的流动情况.由于结点20上的数据在加入过程中，按照路径冗余方法在结点9和结点18上保存了数据副本.因此当查询消息由结点8发送出来时，仅需要通过一次消息发送就可以到达结点9，从而获取到结点20保存的数据.而正常通过结点8—12—13—14—15—20这条查询路径所需的路由跳数为5次，是具备路径冗余机制的系统中数据查询路由跳数的5倍.

图4 数据查询示意图

3 实验与结果分析

以PlanetSim［12］作为仿真实验平台，首先测试了支持路径缓存的定向多播路由策略与Sylvia等［13］提出的定向路由方法间的性能差异，然后通过查询过程中路由跳数统计体现路由策略定位效率的高低.

3.1 定向多播路由与传统方法性能比较

仿真实验基于PlanetSim 3.0，加入系统的结点数为100结点，向系统中添加的数据资源对象为2 000个资源，CAN逻辑空间设置为2维，逻辑空间的区域范围为0～220.

图5中0%重复率为采用传统的定向路由方法(无多播无冗余);20%、50%、70%和90%重复率分别为在资源加入路径上以概率0.3、0.5、0.7和0.9进行资源冗余(定向多播概率冗余).

图5 定向多播路由与传统方法查询开销关系对比图

随着资源冗余的程度加强，寻找资源所需的跳数减少，0，1，2跳就能到达的资源数量随着冗余的概率增长迅速，而通过多跳才能到达的资源的数量相应的减少.在资源不冗余的情况下，寻找资源所需的跳数主要集中在3～8跳区域.以0.5的概率进行冗余时，寻找资源所需的跳数集中在0～6跳区域，而以0.9的概率进行冗余时，寻找资源所需的跳数集中在0～4跳区域.说明了数据冗余的方法相比于传统的路由定位方法对于系统中的资源查询效率有很大的提高.试验证明系统中存储多个数据备份，可以用来提高查询效率，降低查询开销.通过与传统的无冗余方法进行比较，可以得出本文提出的定向多播和路径冗余相结合的方法在定位效率和查询负载上比其他的传统方法有更优秀的表现.

3.2 资源查询的路径长度统计

系统查询开销所需要的路由跳数可以体现系统的开销，也直接体现了定位效率的高低.内容寻址网络中每个结点包含了2×d个方向的邻居表.从一个结点转发消息到目的过程中，转发路径的下一跳最多有d个选择，因此，路由跳数应该是.其中，N为结点数，d为维度.试验中采用了2维空间，加入的结点数为100，因此维度d= 2，结点数N=100，资源查询过程中的查询消息的转发次数应该在=10跳左右.试验中随机选择结点访问每一个资源，最终统计随机访问所有资源的过程中查询消息被的转发次数.通过图6可以看出，绝大部分资源的访问消息转发跳数集中在2～8跳，具有较好的分布情况，符合理论预期值.

图6 资源查询路由跳数统计图

4 结论

1)提出基于CAN模型定向多播路由方法改善了传统的P2P系统中路由效率低下，路由开销大的问题.

2)提出定向多播路由和路径冗余相结合的方法，明显提高了系统的查询效率.

［1］RATHASAMY S，FRANCIS P，HANDLEY M.A scalable content-addressable network［C］//Proceedings of the 2001 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communication. New York，NY:ACM，2001:161-172.

［2］STOICA I，MORRIS R，KARGER D，et al.Chord:A scalable peer-to-peer lookup service for internet applications［C］//Proceedings of the 2001 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications.New York，NY:ACM，2001:149-160.

［3］MAYMOUNKOV P，MAZIERES D.Kademlia:A peerto-peer information system based on the XOR metric［C］//Revised Papers from the First International Workshop on Peer-to-Peer Systems.London，UK:Springer-Verlag，2002:53-65.

［4］NICHOLAS J A，HARVEY N，JONES M B，et al. SkipNet:A scalable overlay network with practical locality properties［C］//Proceedings of the 4th Conference on USENIX Symposium on Internet Technologies and Systems.Berkeley，CA:USENIX Association，2003: 29-38.

［5］REN S S，GUO L，JIANG S，et al.SAT-match:A selfadaptive topology matching method to achieve low lookup latency in structured P2P overlay networks［C］//Proceedings of the 18th International Parallel and Distributed Processing Symposium.New York:IEEE Press，2004:83-91.

［6］RATNASAMY S，STOICA I，SHENKER S.Routing algorithms for DHTs:Some open questions［C］//Revised Papers from the First International Workshop on Peer-to-Peer Systems.London，UK:Springer-Verlag，2002: 45-52.

［7］ROWSTRON A，DRUSCHEL P.Pastry:Scalable，distributed object location and routing for large scale peerto-peer systems［C］//Proceedings of the 18th IFIP/ ACM International Conference on Distributed System Platforms.New York:IEEE，2001:329-350.

［8］ZHAO B Y，KUBIATOWICZ J D，JOSE A D.Tapestry:An Infrastructure for Fault-tolerant Wide-area Location and Routing［D］.Berkeley，CA:University of California at Berkeley，2001.

［9］WU Z D，RAO W X，MA F Y.Efficient topology-aware routing in peer-to-peer network［C］//Proceedings of the GCC2002.New York:IEEE，2002:172-185.

［10］陈贵海，李振华.对等网络:结构、应用与设计［M］.北京:清华大学出版社.2007:159-165.

［11］齐庆虎，李津生，洪佩琳，等.内容寻址网络中内容的有效定位［J］.电路与系统学报，2004，9(5): 67-71.

［12］Jordi Pujol Ahulló，Marc Sánchez Artigas，Pedro García López.PlanetSim User and developer tutorial［EB/ OL］.［2008-10-20］.http://ants.etse.urv.es/ planetsim.

［13］RATHASAMY S，FRANCIS P，HANDLEY M，et al.A scalable content-addressable network［C］//Proceedings of the 2001 Conference on Applications，Technologies，Architectures，and Protocols for Computer Communications.New York，NY:ACM，2001:161-172.