一种chord路由表的改进方法

《一种chord路由表的改进方法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、工程科技《白订陡院霉粕>2olo年第3期一种Chord路由表硇改进方法王必晴(铜陵学院，安徽铜陵244000)摘要：资源的高效查找是P2P网络研究中一个核心问题。针对P2P资源查找协议Chord的路由表信息冗余、查找效率不高的问题．提出了一种Chord路由表的改进方法。在不增加路由表长度的前提下，将路由表中的重复表项删除，进而增加经过科学定义且具较大覆盖面的有效路由信息。实验结果表明，该方法减少了平均查找跳数，提高了查找效率，使提高查找效率和控制路由表长度得到较好的统一。关键词：对等网络：Chord；路由表

2、；查找；分布式哈希表中图分类号：TP393．02文献标识码：A文章编号：1672—0547(2010)03—0069—02目前，许多基于分布式哈希表(DHT)的P2P网络，如其后继节点间的间距就大于1，则该节点的路由表必然会出现Chordeal，Tapestry日，CAN~3)，和Pastryf41等，由于有着良好的健壮冗余信息。性和可扩展性，正日益成为P2P网络研究和应用的热点。Chor由MIT提出。对于一个有N：2n个节点的Chord网曰络，每个节点要维护一张有in个表项的路由表fingertable)

3、，平均查找跳数Y~(1ogN。但是该系统路由表中有近1左右的重复表项l图1)，查找效率不高，因此有一些文献tsqq~rj-Chord做了进一步的研究。文献f51提出了双向路由Chord的思想，使平均查找跳数减小到(1ogNy3，然而其路由表长度是原始Chord的两倍。文献f6提出了One—Hop的算法，使所有的查找有可能只需要一跳完成，但是每个节点的路由表需要维护全体节点的信息。图1节点8的路由表本文在Chord的基础上，提出了一种Chord路由表的改进2．Chord路由表改进方法方法。在不增加路由表长度的

4、前提下，将路由表中的重复表项如果我们把重复的路由信息删除，在路由表的多出空间中删除，进而增加有效的路由信息。该方法较科学地定义了需要添加其他节点的信息，则必然可以提高查找效率。补充的路由，而且补充的路由具有较大的覆盖面。这样，可以消从图1可看出标准Chord的路由表只能覆盖『n0，NO+2这除路由表信息冗余，减少平均查找跳数，提高查找效率，使提高半个环的区域，而没有保存(nn+2一这另一半空间上任何查找效率和控制路由表长度得到较好的统一。节点的信息。因此，如果我们在因为删除重复路由信息而腾出1．Chord路

5、由表研究的路由表空间中增添(n一，n区域中的节点，就增加了以每个Chord节点都需要维护一张路由表。节点n。的路由前Chord中所没有的信息，加快了查找的速度，提高了查找的表中的第i(1≤i≤m)项是Chord环上标识符等于或大于(n_卜1)效率。mod2m的第～个节点，即(nrood2m的后继节点，用successor假设Chord环的大小为2m，节点数为2n，且所有节点平均((rn10d2n1表示。路由表中的每一项既包含相关节点，又包分布。则两个节点间的平均间隔是2-／2~，每个节点路由表中的含该节点的

6、IP地址。如果关键字和节点用m位二进制数表示，需要删除的冗余信息数量为log2(2"／2")--m-n条。相应地，需要补那么路由表中就有ii1个表项。显然，这样的路由表只能覆盖，充的路由也是瑚_n条。no+2-~a]这半个环的区域。节点no的路由表中的补充路由条目按以下方法建立：任何一个节点收到查找关键宇k的请求时，首先检查自身(1)建立节点nn十2的路由表，将最后一项用no的前驱节节点是否等于k，如果是的话，就直接回应查找节点。否则，检查点替代。k是否落在该节点和它的后继节点之间，如果是的话，这个后(21

7、当1≤m时，从节点n卜2一的路由表中由上到下依次继节点就是存储k的节点。否则，节点将查找它的路由表，找到选取不重复的且与节点no的路由表项不相同的n个表项当表中最大但不超过k的第一个节点，并将这个查找请求转发给n>m／2时，从节点n2的路由表中由上到下依次选取不重复该节点。通过重复这个过程，最终可以定位到k的后继节点，即的且与节点n的路由表项不相同的mr-n个表项。存储有k的节点。图1是一个m=6的Chord环，节点8查找关(3每上一步所选取的表项添加到节点NO的路由表的尾部。键宇56，经过3次转发，最终找

8、到56的后继节点56。f41删除节点n盯}2一的路由表。显然，节点8的路由表中第2条和第3条路由信息都是需要说明的是，为了定义需要补充的路由，即使标识符n冗余的，冗余度达到了33％，势必对查找效率造成影响。造成2处没有节点，也不妨假设其存在。同时，由于节点n2一的冗余的原因是相对于2m的标识符空间来说，节点的数目太过路由表的最后一项就是n。本身，所以用的前驱节点替代，可稀少。实际上，如果假设节点平均分布，只要n<