基于Gnutella的P2P网络路由改进算法

洪泛算法是无结构P2P网络的基本路由算法,但产生的巨大冗余信息严重降低了该算法的效率。结合洪泛搜索算法和随机走动算法的优点,在维持了洪泛算法响应时间短、稳定性高、结构简单的基础上大大减少了冗余信息的产生,实现了一种改进的路由搜索算法：跳跃随机式洪泛算法。实验结果显示,在保持理想的节点覆盖率的情况下大大减少了冗余信息,提高了搜索效率,改善了网络运行环境。

第3 O卷增刊 121 0 0年 6月

计算机应用J un lo o ue piain o r a fC mp trAp l t s c o

Vo . 0 S p 1 1 13 u p.

J n 0 0 u e2 1

文章编号：0 1 9 8 (0 0 S 0 2—0 1 0— 0 1 2 1 ) 1— 0 1 3

基于 G ue a的 P P网络路由改进算法 ntl l 2李杰，邓亚平(重庆邮电大学计算机科学与技术学院，重庆 4 0 6 ) 0 0 5( l e 20@ 13 cm 1o r 0 8 6 .o ) jv _

摘

要：洪泛算法是无结构 P P网络的基本路由算法， 2但产生的巨大冗余信息严重降低了该算法的效率。结合

洪泛搜索算法和随机走动算法的优点，维持了洪泛算法响应时间短、定性高、构简单的基础上大大减少了冗余在稳结

信息的产生，实现了一种改进的路由搜索算法：跳跃随机式洪泛算法。实验结果显示，保持理想的节点覆盖率的情在况下大大减少了冗余信息，高了搜索效率，提改善了网络运行环境。 关键词：对等网络；洪泛算法；随机走动； n t a网络 G ue n中图分类号： P 9 .2 T 3 3 0文献标志码： A

I p o e e fr u e a g rt m o P e wo k ba e n n el m r v m nto o t l o ih f r P2 n t r s d o G ut l aL i, DE — ig IJe NG Yap n( ol eo o p t c nead Tcn l y h nqn n e i P s n e cm nct n,C og ig4 0 6,C/ ) C lg e fC m ue Si c n e oo,C og i U ir t o ot ad Tl o mu i i s hn q 0 0 5 hn r e h g g v syf s e ao n aAb t a t h u e r d n a tme s g s g n r td b o d n i h i h a i o t g ag r h o n t c u e 2 s r c:T eh g e u d n s a e e e ae y f o i g wh c s te b sc r u i l oi m fu sr t r d P P l n t u

n t o k s v r l e u e t e e ii n y o e ag r h e w r, e e ey r d c h f ce c ft oi m. C mb n n h d a t e ff o i g s a c

g r h a d r n o h l t o i i g t e a v n a s o o d n e r h a o t m a d m g l l i n

w l grh,sc ssotep net,h曲 s bi,s pes ut,t ged euet eu dnyo s gs a a ot kl im uha h rrso s me i t it i l t c r o ra yr c er n ac f s e, i a ly m r u e d h d me ati a e rp sd a mpo e o t erh ag rh: J mp n o f o . T e smuain rsl h w ta eag rh hsp p rpo o e i rv d rues ac lo t n im u Ra d m- od l h i lt eut s o tt oi m o s h h l tc l r d c h d d tme s g s i ce s e e ce c fs a c,a d i r v ewok e vr n n i i ti i g a u et e r u a s a e, n r a et f i n yo e r h n mp o e t n t r n i me t le e n n h i e h o wh l ma n an n eh e ie o e a ae o o e . te d srd c v r e r t fn d s g

Ke od:Pe— -er( 2 ) l o iga o tm;rn o a;G ue antok yw r s er oP e P P;f dn grh t o l i ad m w l k ntl ew r l

对等网络( eroP e,2 ) P e— -erP P飞速发展， t已经成为现代网络的重要组成部分。P P网络主要分为结构化和非结构化两 2种，对于结构化网络，目前最大的难点在于网络节点动态性太

间。本地索引 ( oa Idcs“, L cl nie) J每个节点维护离自己的距离

不超过 r步的节点的数据索引，当该节点收到查询信息时，它可以为离自己半径为 r围内的所有节点处理查询。典型的范

高，维护开销过大，以商业应用绝大部分是非结构化的 P P所 2网络。洪泛 ( odn ) l f ig算法是非结构化 P P网络中的基本算 2

算法有 L C, H J缓存自己邻居的资源索引，自己邻居的邻向居发送查询信息。但每个节点除了维护开销外，向邻居的还邻居发送查询信息，发送数量接近于节点度数的平方，

下层产

法，有结构简单易实现、稳定性强易维护、覆盖面广等优点；但

缺点也很明显，产生了过多的冗余信息，加重了网络负担，扩展性差。因此非结构化 P P网络的路由算法，为研究的热 2成门，针对洪泛的各种改进算法也应运而生。

生的冗余信息仍然庞大。3基于拓扑结构优化的。超节点结构， )利用超节点来提

供局部的索引查询，使用这结构 P P系统有 K Z A; 2 aa生成树结构是在 P P网络中建立一种类似于树型的拓扑结构，表性 2代的有 Lgtl d。该算法中， ih o F上层网络采用 f oig l dn算法， o到达第 5层后，每个对等节点向它的直接逻辑邻居节点发送自

1非结构化 P P网络路由算法及其改进 2非结构化 P P网络路由算法大致可以归为三类：于改 2基

进转发机制的、于缓存的，基以及拓扑结构优化的。1基于改进转发机制的。文献[ ) 1—2]中的 Moie df d iB S Drc dB S Itl etB S以及 I F - D 都是以特 F, i t F,n lgn F, ee ei B SH I

己的连接度，节点得到自己所有邻居的连接度后选出度数最大的节点作为自己的父节点。Loa ed算法通过知道两 okh a跳内的邻居信息，从而消除两跳范围内的环路。拓扑结构优化虽然大大减低了冗余信息的产生，是维护拓扑结构所带但来的资源开销也是不容忽视的一个问题，并且这种网络拓扑的改进同时也可能带来单点失效问题。

定的策略选择一部分邻居进行转发，虽然达到了减少冗余信息的目的，但效率有待提高；文献[] 4中提到的随机走动和扩展环，中随机走动 ( adm l )型能将查询信息数量其 R n o Wa类 k减低一个数量级，同时其响应时间也增加一个数量级。扩但展环( x ad gRn )质仍然是 f oig算法，不同在于 E p i ig本 n n l d o n其这种机制解决了， L的适当选择问题。 I . r< …… 此处隐藏：1604字，全部文档内容请下载后查看。喜欢就下载吧 ……