结构化P2P网络性能分析与搜索算法研究

论文摘要

近年来,对等网络（P2P）日益成为Internet上的一个重要应用。P2P网络中的每个节点既是内容提供者,又是内容消费者。结构化对等网络是扩展性高、容错性好的P2P网络,是当前的研究热点。基于分布式哈希表的结构化P2P网络利用DHT进行资源定位,它将网络中每个资源和节点哈希到同一个值空间,每个共享资源被发布到和自己资源标识符最接近的节点上。这种定位机制虽然有效地解决了非结构化对等网络中洪泛机制所带来的不可扩展问题,却不可避免地带来了另外的一些问题。这些问题主要是:（1）由于节点的频繁加入和离开所引起的路由表更新代价非常大;（2）哈希过程丢失了节点的物理位置信息,使得重叠网络中的邻居物理上可能相距很远,从而使得结构化P2P网络中的查找延迟增大;（3）在抖动率很高时,某些结构化P2P网络随着网络规模的扩大而性能急剧下降;（4）只支持从key到value的精确匹配,不支持多关键字搜索,搜索效率不高。当前,结构化P2P网络的研究主要集中在对现有的DHT协议的直接改进上,很少通过对网络的性能进行分析而提出改进方案。这种方法存在着两个缺点,一是这种改进只针对某种DHT协议,如Tapestry,没有普遍意义;二是容易造成顾此失彼,如常量度数的DHT算法虽然降低了查询跳数,但对于节点的异常离开的处理能力较差,容错性能大大降低。为了更有效解决上述问题,有必要从路由表更新代价、查找延迟和抖动环境下的可扩展性等网络性能指标对典型结构化P2P网络的性能进行整体分析,进而提出改进算法和方案。从而提高结构化P2P网络的整体性能。为了找出影响网络抖动的关键因素,首次提出了反向邻居节点的概念,即把自己作为邻居节点的节点,在此基础上,计算了六种DHT网络的反向邻居节点数。分析了影响抖动的路由方式、邻居选择、节点加入和节点离开以及并行查找等策略因素。发现对任意两种DHT网络,它们分别采用的五种策略都至少有两种不同,于是,对两种DHT网络直接进行比较就很难确定哪些策略能更有效地降低抖动。因此,提出在同一网络内,用不同的单个策略对网络抖动进行比较和分析的方法,称之为CSP。对现有的Pastry算法进行改进,构造了使用快速加入策略的FPastry算法和周期性恢复策略的PPastry算法。并分别把FPastry、PPastry和原有版本的慢速加入、反应性恢复算法进行了比较。还把使用迭代路由的Chord协议和使用递归路由的Chord协议进行了比较,得出以下结论:迭代路由、快速加入和周期性恢复策略和有效的邻居选择算法能更有效地降低网络的抖动。研究发现,数据存放机制、路由方式、邻居选择和服务选择方式等,是影响结构化P2P网络查找延迟的关键因素。通过对一些典型结构化P2P网络查找延迟的比较和分析,提出了降低内容寻址网络节点间延迟的DCAN算法。该算法将内容寻址网络中的节点抽象成一个无向带权图,在此基础上,把Dijkstra算法求得的源节点到目的节点的最短路径作为路由。仿真实验表明,和路由过程中每次选择最小的下一跳的算法相比,DCAN算法能更有效地降低从源节点到目的节点的总延迟。为了研究抖动环境下各种结构化P2P网络的可扩展性,提出了LBE评价方法。该方法把成功查找的时间延迟和查找失败率随网络规模的变化作为衡量可扩展性好坏的标准。随机改变DHT的各种参数,得到一系列查找延迟时间,把它们形成的最低线作为网络的整体性能指标。固定某一参数,但随机改变其它参数再进行仿真,从而得到最佳网络整体性能条件下的参数值。用上述方法对三种DHT协议的可扩展性进行了综合分析,并得出了相应的结论。通过分析现有多关键字搜索算法的缺点,提出了ICCCS搜索算法,该算法在DHT协议层之上建立逻辑的关键字搜索层,搜索层采用改进的超立方体互联圈（Improved Cube-Connected Cycle）结构。通过向量空间模型选择每个对象的重要关键字,并将其映射到ICCC节点的环号,然后将描述对象的整个关键字集映射到ICCC节点的立方体标号。基于反向文档索引技术建立了索引算法,并使用生成树建立了搜索算法。实验结果表明,该算法对于关键字较少的查询有较高的查找精度和较低的查找延迟。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 结构化 P2P网络概述
• 1.2 国内外研究现状
• 1.3 主要创新和研究内容
• 1.4 论文组织结构
• 2 典型结构化 P2P网络及其性能指标
• 2.1 典型结构化 P2P网络
• 2.2 结构化 P2P网络的主要性能指标
• 2.3 本章小结
• 3 结构化 P2P网络的抖动分析
• 3.1 引言
• 3.2 抖动描述
• 3.3 抖动对结构化 P2P网络的影响
• 3.4 反向邻居节点
• 3.5 影响抖动的相关因素
• 3.6 典型结构化网络的抖动仿真分析
• 3.7 本章小结
• 4 结构化 P2P网络的延迟分析
• 4.1 引言
• 4.2 影响网络延迟的几个因素
• 4.3 典型结构化 P2P网络的延迟分析
• 4.4 典型的降低延迟算法分析
• 4.5 降低 CAN延迟的DCAN算法
• 4.6 本章小结
• 5 可扩展性分析
• 5.1 引言
• 5.2 LBE评价方法
• 5.3 典型结构化 P2P网络的可扩展性分析
• 5.4 本章小结
• 6 基于改进的超立方体互联圈的搜索算法 ICCCS
• 6.1 引言
• 6.2 典型结构化 P2P网络的搜索算法分析
• 6.3 ICCCS系统结构
• 6.4 ICCC的结构
• 6.5 对象重要关键字选择
• 6.6 映射文档到 ICCC节点
• 6.7 在 ICCC中搜索文档
• 6.8 使用自动查询扩展提高查询性能
• 6.9 实验结果与分析
• 6.10 本章小结
• 7 结论和展望
• 7.1 本文的主要贡献
• 7.2 进一步的工作
• 致谢
• 参考文献
• 附录 1 攻读博士学位期间发表论文目录
• 附录 2 攻读博士学位期间参加研究的科研项目