非结构的 P 2P 网络拓扑模型

《非结构的 P 2P 网络拓扑模型》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、非结构的P2P网络拓扑模型曹佳张国清鲁士文(中国科学院计算技术研究所,北京100080)E-mail:jiacao@ict.ac.cn摘要在P2P系统中,物理主机的组网比较灵活。由于网络拓扑直接影响了网络的性能,所以构建什么样的对等网络拓扑一直备受关注。论文讨论几种常用的非结构对等网络拓扑模型。非结构型的对等网络适合信息发布类型的应用,其组网和维护相对简单。研究发现,虽然目前有很多构建非结构型的对等网络的方案,但是这些方案最终构建的对等网络基本可以归为三种类型的拓扑模型,随机图论模型(Erd5s-Rényi),k规则随机图和随机有向图。论文分别描述了这三种拓扑模型的度分布、

2、连通性和直径,以及一些相关的典型应用。关键词对等网络随机图直径文章编号1002-8331-(2006)05-0023-03文献标识码A中图分类号TP393UnstructureP2PNetworkTopologyModelsCaoJiaZhangGuoqingLuShiwen(InstituteofComputingTechnology,ChineseAcademyofSciences,Beijing100080)Abstract:P2Pnetworkisaflexiblenetwork.Asweknow,thenetworktopologyinfluencestheper

3、formanceofthenet-workdirectly,sotheP2Pnetworktopologyisveryimportantforthequalityofthenetwork.Inthisarticlewedescribeunstructuredmodels.WefindthatthoughtherearevariouskindsofpoliciestobuildunstructuredP2Pnetworks,thesenetworkscanbeclassifyintothreemodelswhichareErd5s-Rényimodel,k-regularra

4、ndomgraphandrandomdirectedgraph.Thedistributionofthenodaldegree,connectivityanddiameterisourmainconcern.Andsometypicalapplicationsarementionedwithrespecttoeachmodel.Keywords:P2Pnetwork,randomgraph,diameter1引言k来表示;D表示图的直径。本文主要关注度分布、连通性和直在P2P系统中,设计者可以根据不同的应用需求组建不径三个几何特征。(1)度分布:每个结点都有一些邻接边,邻接

5、同拓扑的对等网络(P2P网络)。一个“合适”的网络拓扑可以为边个数等于这个结点的度。度分布用来描述具有相同度的结点应用提供更好的支持,例如规则的拓扑结构有利于根据主机在的数目的分布。结点的度与结点的传输负载和存储负载等工作拓扑网络中的位置进行基于内容的索引;而非结构的随机网络负荷成正比;(2)连通性:如果一个对等网络连通,那么说明网的构建比较简单随意,所以适合于信息发布、即时通讯等主机络中的任意两个结点可以相互通讯。(3)直径:表示图中任意两随时加入退出的情况。因此理解对等网络的拓扑对P2P系统个结点之间距离的最大值,描述网络的传输时间,这对即时通的研究有重要的意义。讯和信

6、息的快速发布具有很重要的意义,对网络的吞吐量也有参与P2P通讯的主机通常不太稳定,研究人员发现在大的影响。Gnutella和Napster中,大约一半的参与者会在一个小时内随时可能加入或者退出通讯[7]。为此,人们通常采用简单的组网策2Erd5s-Rényi模型略来适应动态情况,那么这是否意味着形成的网络拓扑也不稳几乎没有任何P2P系统可以直接采用Erd5sRényi模型,定?我们发现无论采用何种策略,最终都会保证网络的一些静但是Erd5sRényi模型是最基础的随机图模型,因此我们还是态几何特征相对稳定,例如,结点度浮动在某个小范围内,网络对其进行一些阐述。在Erd5sR

7、ényi模型中,主要有两种生成的连通性不变,网络直径被约束在一定的范围内。这些方案最方案Gn,p和GM.Gn,p表示把n个孤立的结点组成n(n-1)/2对终构建的对等网络基本可以归为三种类型的拓扑模型:随机图结点对,以概率p来随机选择每对结点,选中的结点对需要互论模型(Erd5s-Rényi)、k规则随机图和随机有向图。本文主要连;GM表示随机地从这些结点对中选M对结点进行互连。在讨论这三类模型。P2P应用中通常希望每个结点可以尽可能独立地选取其他结我们通过简单的映射将对等网络抽象成一个图论模型G点,因此下面主要阐