基于 OMNET 的结构化 P2P 算法分析.doc

《基于 OMNET 的结构化 P2P 算法分析.doc》由会员分享，可在线阅读，更多相关《基于 OMNET 的结构化 P2P 算法分析.doc（10页珍藏版）》请在三一文库上搜索。

1、精品论文基于 OMNET 的结构化 P2P 算法分析董丽华，卢美莲（北京邮电大学网络技术研究院，北京 100876）5摘要：由于结构化 P2P 网络存在潜在的高效性、高鲁棒性、可扩展性及位置数据的确定性， 因此近些年来人们对结构化 P2P 算法进行了不断深入的研究。本文首先介绍了广泛用于科 学研究中模拟实际网络场景的仿真软件 OMNET，之后通过该软件对结构化 P2P 算法 Chord、 Pastry 及 Kademlia 的性能做出了详细的分析与对比。 关键词：P2P；OMNET；Chord；Pastry；Kademlia10中图分类号：TP393.0Structured P2P Algor

2、ithm Analysis Based on OMNETDong Lihua, Lu Meilian(Institute of Network Technology,Beijing University of Posts and Telecommunications,15Beijing 100876)Abstract: Structured P2P network has potential efficiency,high robustness,scalability,data ofcertainty location, so in recent years, people on the st

3、ructured P2P algorithms continue in-depth study. This paper firstly describes the widely used simulation software OMNET in scientific research to simulate the actual network scene ,then make a detailed analysis and comparison20between different structured P2P algorithm ,for example,Chord, Pastry and

4、 Kademlia .Keywords: P2P; OMNET; Chord; Pastry; Kademlia0引言在互联网领域，P2P（Peer to Peer，对等端到对等端）模式是作为 C/S（客户端/服务器）25模式的对立面出现的，P2P 技术以其特有的自组织性、分布性，在互联网上迅速发展，已成 为互联网网络不可分割的一部分，节点之间可以直接相连进行资源的共享，不仅能使网络上 的资源得到充分的利用，也能使网络的稳定性及容错能力大大提高1。随着硬件设备和网络 性能的快速发展，P2P 技术得到越来越多的关注，已广泛的应用于文件共享、分布式计算、 即时通讯等领域2。30为了更好地支持对 P

5、2P 网络的扩展，更好地管理和维护在 P2P 网络中各个节点的信息， 提供更高效和快捷的查询下载服务，P2P 网络由无序向有序发展，由非结构化向结构化发展， 近年来许多研究小组在设计可扩展的查找机制方面做了大量的研究工作，提出了 Chord、 Pastry、Kademlia 等用于构建结构化 P2P 的 DHT 算法3 4。而这些 DHT 算法的核心思想就 是要解决在 P2P 应用中遇到的基本问题-如何在 P2P 网络中高效地定位存储特定资源的节35点。研究 P2P 结构化算法在构建网络以及资源定位方面的性能非常有必要5 6。本文通过 OMNET 仿真软件对结构化 P2P 算法 Chord、P

6、astry、Kademlia 的性能做出进 一步的分析与对比，通过对比了解不同结构化 P2P 算法的优势与缺陷。1OMNET 介绍OMNET 是基于组件的模块化网络仿真平台，具备强大完善的图形界面接口和可嵌入式40仿真内核，它为仿真提供了一套基本环境和机制，包括编写组件的 NED 语言、仿真内核和作者简介：董丽华，（1987-），女，硕士研究生，主要研究方向：网络融合与业务融合。 通信联系人：卢美莲，(1968-)，女，副教授，主要研究方向:移动互联网业务和体系结构、分布式与个性化 信息服务、网络融合与业务融合。E-mail: - 10 -一些用来创建仿真组件的工具类、以及对外用户接口，但本身

7、并不提供用于特定计算机网络、系统架构和其它领域仿真的组件。INET 框架基于 OMNET 完整实现了 TCP/IP 协议栈，可 用于 TCP/IP 协议的仿真，并为 OverSim 提供了支撑。OverSim 是开源的 P2P 网络仿真框架， 可工作在 OMNET 仿真环境下，它包含了多个 P2P 网络协议，包括 Chord、Kad、Pastry、45Broose 等。OverSim 是基于 INET 和 OMNET 之上的仿真框架。在 OverSim 里，每个节点 被分为三层，Underlay，Overlay，和 application，application 里面又分为多层。Underla

8、y 为 底层物理网络的模拟仿真层，Overlay 为覆盖网层的模拟仿真层，而 application 为应用层的 模拟仿真层。仿真平台配置步骤如下：50（1）omnetpp.ini 文件的配置：omnetpp.ini 中定义运行的参数，如需要调整 P2P 覆 盖网的网络规模，则需要修改文件中的 targetoverlayTerminalNum 参数。点击 omnetpp.ini 文 件，选择 parameters 选项，在右边的 configuration 中选择将要进行配置的算法，之后选择需 要配置的参数，如图 1 所示。55图 1 omnetpp.ini 文件的配置Fig.1 Config

9、uration of the omnetpp.ini file（2）run configurations 的配置：对仿真算法、界面、数据等进行配置。Config name选择要配置的算法；User interface 指用户交流界面，可选 Tkenv 进行图形化界面的输出；60Tkenv 中有 Step、 Run 、Fast run、 Express run 几个选项，表示系统运行速度，可以选取 不同的速度来运行仿真；Record eventing 表示是否记录仿真过程中的信息，选择 yes 以记录 过程；选择 Apply 保存配置信息，选择 run 运行仿真程序。运行结束后，工程视图文件夹下

10、出现名称为 result 的文件夹，里面生成了本次模拟的结 果文件。其中 vec 和 sca 文件是模拟的统计信息，elog 文件存储了每个 message 的发送情65况、文本信息等等，并且可以在序列图中可视化。为了进行结果分析，首先要新建一个.anf 的 分析文件，将.vec 和.sca 的信息导入.anf 中。在每个仿真运行时都会得到一个唯一的 run ID， 包含了配置、运行编号、数据、时间等信息。打开导入信息的.anf，在 data 视图里面，第一 个表(by file and run)显示了某个文件是运行哪个仿真产生的；第二个表(by run and file)显示了 某个仿真运行

11、产生了哪个文件；第三个表是逻辑运行关系。每个 experience 里面都包含若干70个测量，通常是一个同样的仿真模型使用不同参数运行得到的。每次测量都可以用不同的seeds 重复去做，从几个 replications 中来得到可靠的统计结果。.anf 打开结果如图 2 所示。图 2 仿真结果.anfFig.2 The result of simulation752结构化 P2P 算法仿真结果及对比三种算法理论上性能对比分析如表 1 所示。表 1 Chord、Pastry、Kademelia 算法对比80Tab.1 Chord, Pastry, Kademelia algorithm comp

12、arisonChord Pastry Kademlia拓扑结构 节点 ID 分布在单向环形 空间存储 存储在 K 的后继节点即 节点 ID 大于 K 的第一个节点上路由查询消息通过后继节点指针或者 指针表找到 K 的后继节点节点维护状态后继节点指针或者指针 表：O(logN)节点 ID 分布在单向环形 空间，并且表示为以 2b 为基的数存储在节点 ID 与 K 最接 近的节点上比较 K 和节点 ID 的前 缀，下一跳节点的 ID 具 有更长的前缀或者在数 值上更接近 K 叶子节点集、邻居节点 集：2b 或者 2*2b同 Chord 类似通过在每一维对 K 进行 Hash 运算将 K 映射到坐

13、标空间中的一点，存储在 维护该点所在区域的节 点上 下一跳节点在坐标空间 上距离目标节点更近K 桶路由表：log b N2*(2b-1)路由性能 O(logN) O( log b N ) O(logN)2稳健性 维护 r 个最近的后继节点只有在|L|/2 个叶子节点 完全失效时才会路由失败随时更新节点信息，稳定 性高通过仿真软件 OMNET+INET+OVERSIM 中 Chord、Pastry、Kademlia 三种结构化 P2P算法在不同场景下的运行结果，对比分析三种算法的性能。仿真中设置三种网络规模，即节 点数量为 10、20 和 100。852.1同一算法不同规模结果分析2.1.1Ch

14、ord 算法的跳数和时延图 3 节点数为 10 时 Chord 算法跳数90Fig.3 Chord hops when the number of peers are 10图 4 节点数为 20 时 Chord 算法跳数Fig.4 Chord hops when the number of peers are 2095图 5 节点数为 100 时 Chord 算法跳数Fig.5 Chord hops when the number of peers are 100100105110115图 6 节点数为 10 时 Chord 算法时延Fig.6 Chord delay when the num

15、ber of peers are 10图 7 节点数为 20 时 Chord 算法时延Fig.7 Chord delay when the number of peers are 20图 8 节点数为 100 时 Chord 算法时延Fig.8 Chord delay when the number of peers are 100由上面的数据对比可以看出，Chord 算法构建的网络中，当网络规模小幅度增加的时候， 性能稳定，当网络规模大幅度增加的时候性能明显变差。原因是 Chord 算法中节点的查找与 节点的指针表大小有关，当网络规模变大的时候指针表也随之变大，由于 Chord 算法的特性，

16、 忽略了网络中节点的物理特性，使得定位过程中绕路现象时有发生，性能会比较受影响。2.1.2Pastry 算法的跳数和时延精品论文120125130图 9 节点数为 10 时 Pastry 算法跳数Fig.9 Pastry hops when the number of peers are 10图 10 节点数为 20 时 Pastry 算法跳数Fig.10 Pastry hops when the number of peers are 20图 11 节点数为 100 时 Pastry 算法跳数Fig.11 Pastry hops when the number of peers are 10

17、0图 12 节点数为 10 时 Pastry 算法时延Fig.12 Pastry delay when the number of peers are 10精品论文135140145图 13 节点数为 20 时 Pastry 算法时延Fig.13 Pastry delay when the number of peers are 20图 14 节点数为 100 时 Pastry 算法时延Fig.14 Pastry delay when the number of peers are 100随着网络规模的增大，Pastry 算法的性能较稳定，跳数和时延变化较小。原因是 pastry 算法是根据节

18、点 ID 的相似程度结合自身的路由表定位节点，当这个路由表足够大并结合自 身的叶子节点表，就可以快速的定位节点。不足之处为节点的开销增大，需要存储大量的表 项。2.1.3Kademelia 算法的跳数和时延图 15 节点数为 10 时 Kademelia 算法跳数Fig.15 Kademelia hops when the number of peers are 10150155160图 16 节点数为 20 时 Kademelia 算法跳数Fig.16 Kademelia hops when the number of peers are 20图 17 节点数为 100 时 Kademeli

19、a 算法跳数Fig.17 Kademelia hops when the number of peers are 100图 18 节点数为 10 时 Kademelia 算法时延Fig.18 Kademelia delay when the number of peers are 10图 19 节点数为 20 时 Kademelia 算法时延Fig.19 Kademelia delay when the number of peers are 20165170175180185图 20 节点数为 100 时 Kademelia 算法时延Fig.20 Kademelia delay when t

20、he number of peers are 100当网络规模较小变化时，Kademlia 网络的性能几乎不变，当网络规模显著增加时，网 络性能也随之变化增加。原因是 kademlia 采用异或运算计算节点距离并通过 K 桶方法定位 节点，在查找过程中会更新节点信息，保证了网络的动态稳定。2.2网络规模相同时不同算法对比对比相同规模时三种算法的性能。 Chord 与 Pastry、Kademelia 相比，在构建网络是没 有考虑节点的实际物理拓扑结构，忽视了逻辑覆盖网络与底层物理网络之间的差异，可能导 致在实际网络中距离很近的两个节点通过散列函数之后映射在覆盖网络上的距离很远，出现 网络的绕路

21、。由于 Chord 构造指针表的构造方法，使得信息冗余在指针表中不可避免。Pastry 与 Chord 和 Kademlia 相比，Pastry 引入了叶子节点和邻居节点集合的概念。在应 用层能够及时准确地获得这两个集合的节点信息时，可以大大加快路由查找的速度，同时降 低因路由引起的网络传输开销，不过在动态变化的 P2P 网络中如何理想地做到这一点的确 有很大的难度。Kademlia 算法采用异或运算作为距离度量的基础，构建了一种新颖的网络拓扑结构， 简化了节点的定位算法。通过同步信息的发送，使得系统能够灵活的处理查询信息，提高了 查询速度，节点对接收消息的随时更新，保证了系统在复杂网络，特别

22、是节点频繁变化的环 境中的高稳定性。基于这些优点，Kademlia 在现实环境中比其他的结构化模型得到了更广 泛的应用。1901953结论本文给出了 OMNET 仿真软件的介绍与操作间接，通过 OMNET 仿真软件对当前比较 热门的结构化 P2P 算法 Chord、Pastry、Kademelia 做出对比分析，主要从跳数与时延两方面 说明算法资源定位的效率。从结论上可以看出，Kademlia 能较好的适应网络的动态变化， 在网络规模不断扩大时资源定位时间有较好的收敛性，有更好的应用前景。Chord 在构建网 络是没有考虑节点的实际物理拓扑结构，忽视了逻辑覆盖网络与底层物理网络之间的差异， 可

23、能出现网络的绕路现象，Chord 构造指针表的构造方法使得信息冗余在指针表中不可避 免，因此该算法有待进一步提高其性能。Pastry 能够及时准确地获得节点信息时，加快路由 查找的速度，同时降低因路由引起的网络传输开销，但其对网络的动态变化适应性不佳，有 待于进一步完善和提高。参考文献 (References)2002051 Zhu Y,Hu Y.Efficient,proximity-aware load balancing for DHT-based P2P systemsJ.IEEE TransactionsParallel and Distributed Systems,2005,16

24、(4):349-361.2 Wang Zhi,Chen Qi,Gao Chuanshan.A Proactive ServiRequest Broker for PC-based Grid ComputingJ.Proc. of Intemational Multi Symposiums on Computer and Computational Sciences,2006,3(2):603-610.3 Castro M, Costa M, Rowstron A. Debunking Some Myths About Structured and UnstructuredOverlaysA.P

25、roc. of NOSD05C.USA:Berkely.4 Baset S A, Schulzrinne H. An Ana1ysis of the Skype Peer-to-Peer Internet Telephony ProtocolA.Proc. ofIEEE INFOCOM06C. Spain:Barcelona.5 张春红.P2P 技术全面解析M. 北京：人民邮电出版社,2010.6 Han D.Keyword Search in Unstructured Peer-to-Peer Networks A.Andbook of Peer-to-PeerNetworkingC.USA:New York.