数事执术与盛州
结构化p2p路由协议的改进
原虹
(晋中学院计算科学与技术学院山西晋中030600)
学术论坛
摘要：上世纪90)年代以来，P2p的研究在我国不断深入，和传统的c/s网络技术相比，对等网络具有它对特的优势，即具有很高的拓展性，建壮性，负载均衡性，这转性都有很高的研究价值，
关键词：P2p结构化路由改进
中图分类号：TP393.0
文献标识码：A
文章编号：1007-9416(2011)10-0191-0
(1)P2p的分类P2p网络拓扑结构按照节点信息储存和搜索方式的不同可以分为：1)可以运用特殊节点存储所有资源的索引信息、有发现率高、维护简单等优点，不过很容易发生单点故障，这一类是以Napster作为代表的中心索引拓扑。2)具有相当不错的容错性，采用随机泛洪转发的机制，节点的任何子集从节点中移除都不会对网络本身造成影响，可是网络的规模日益增大，泛洪可能会造成网络流量的急别增加，可拓展性非常差。这-一类是以Gnutella，FreeNet为代表的非结构话拓扑。3)主要思想是每一个节点和每个资源都使用相回的哈希类方法账予一个全局唯一的D，把资源地址通过某种算法定位到资源地址，具有可拓展，可管理的优点。即结构化拓扑。
(2)P2p的间题以及解决的办法P2p网络的主要间题之一就是通过某一种方式来实现资源的定位。现如今，针对单点崩溃、可拓展性不高、消息泛滥等问题提出了许多算法，就好比说CAN，Pastry、 Chord，Tapestry。相比较而言，Chord的可靠，简单，高效查找等特点是DHT所不具备的。通过研究，Chord算法主要由路由的Finger table决定，正因如此，其必然会存在一定的局限性。有部分研究结构化路由的有关专家通过更加深一步的研究发现如果全体节点的信息都能够靠每个节点来共同维护，那么所有的查找工作仅需要跳跃一次就能够完成，但具有维护节点需要很大开销的缺点；同时超级节点也有可能会成为Chord中的通信瓶颈。假如只扩展路由表，就-定会产生一个全新的计算方法，产生的这个全新的计算方法是通过增加原有的路由表指针密度，使Chord的查找方式由以前的单向变为双向，令路由表中的垃圾信息被清除，缩短路径长度，提高搜系效率，缩短延退，并且伤真其性能。Chord在麻省理工学院于2001年
个节点和关键字全都拥有一个属于自己的m
被提出，Chord中每--
比特的标识符，在Chord中关键字的标识符key是通过哈希关键字本身来得到的，可是Chord中的节点标识符id是通过哈希节点的IP 地址所得到的。SHA-1或MD5适用于哈希函数，所有的节点都按照 Chord的节点标识符以顺时针从小到大的顺序排列在一个退辑的标识环上面，这样的环叫被微Chord环。其中关键字中的标识为 value或key则要在这样的节点上储存。而节点标识等于或仅次于 key后面的节点就叫做key的后继节点，用successor表示，以key点为起始点，在顺时针的方向上距离key点最近的节点，一张含有m个表项的finger表要有每个节点的共同维护，举个例子说明，一个节点是n，在Finger表中位于第项，是例环上标识不小于n+2i-1的第1个节点，我们把这个节点叫做s，那么对每--次的资源请求，Chord都会利用finger表，在此表中最多查找m次就一定能够定位环上数据资源。单向Chord查找算法因为是单向，所以查找效率不高，试想-下，如果把传统的单向顺时针查找变为双向查找，必然会提高查..上接第190页
新设置填充额色，确认无误且已完全达到设计要求即可输出示意
图。所绘制的图如图1所示 3、结语
通过利用ConelDraw软件绘制如本例这样的地面气象观测场内仪器布置示意图，不仅图像质量好，面且可以精确表达示意图中地物间的相对距离，为开展地面气象观测奠定基础。当然，对 CorelDraw所绘制的示意图方面的应用远不止这些，待挖掘的功能
找效率。于是就产生了R_Finger表(一张由双向Chord定义的路由表）这张表是Chord协议中一张逆时针的表，是finger表翻转后得到的。因此，在任一节点上可以回时在顺时针和逆时针两个方向同时进行搜索，让查找有机会在两个方向上获得一个最佳的路由。如果想要提高Chord路由的性能，可以相应的减少转发的次数同时还根据实际的情况增加路由表本身的密度，路由表的指针指向目标节点的速度大小是通过密集程度决定的。这样一来，节点需要维护的路由表长度会比经典的Chord有所增加，其长度从原来的1bN增加到21og3N，应用三阶Chord后可以得出三阶Chord的最大转发次数是log3N次。在此基础上还能够将单向改变为双向同时又结合三阶 Chord的思想，把双向Chord的算法路由改成三阶。当Chord改进以后，拥有了全新的算法，下面举例说明，某个节点（将之为称为P节
时针方向查找所需资源，在查找的时候一共找到4个节点，这些节点就可以作为下--个节点的跳点，换句话.也就是说就是有两个节点可以在Finger和R_Finger表中获得，关键字的Hash值是被其标识的Hash值夹在其间的，离关键字Hash值最近的可能全部存在，把关键字的Hash值设为k，P1和P2是从finger表中所获得的节点，P1是在表中最接近于k且小于k的节点，在表中位于p1后面的第一个节点是P2。P3和P4从R_Finnger中取出的两个节点。表中最接近k且大于k的那个节点在finger表中我们称为P3，R_Finger表中位于p3 后的第1个节点就是D4。详细算法；1)如果是存储在本地的关键字，就返回本地地址，结束查找。2通过顺时针的方向，假如k点落在口点和的后节点中间，就姚转回后节点，结束查询，相反，就转到下一步。3)计算pl，p2，p3和p4与k的距离，距离最近的那个节点就成为下-跳的节点。转到1).查找继续。L2=1/21og83NL1=1/21og2N假设Chord环节中有节点N=212，则改进后的平均路径长度为 Lavg2=4.24,标准Chord的平均路径长度为Lavg1=6，查询率提高
了26%。结语
从整体上来看，这种新型算法是在原有的Chord基础上讨论的一-种路由的比较先进的算法，这个算法是通过令2阶路由表转改为 3阶路由表，通过此方法使路由表的指针密度增加，是查找目标节点的效率提高，增加了一个逆时针方向的路由表，从面达到双向查找，
比较当前的所有路径，从而选出最佳的路径。参考文献
[1]王新生，梁平，张云超,王伟杰，丁学永,结构化P2P路由协议的改进.20100520.
还很多，需要在实践应用中不断开发，创新。参考文献
[1]周淑贞.气象学与气候学实习[M].高等教育出版社,1990
[2]张琳等.基于AutoCAD和CoreIDraw的土范利用现状图制作[J]
测绘,2011(4):60-62. 基金项目
云南曲靖师范学院2010年实验教学研究项目，典靖师范学院 2010年重点课程研究项目。
91