基于DHT的P2P搜索引擎的研究 ——一种Chord改进算法

论文摘要

近几年来对等网络(即P2P网络)得到了飞速发展,它将Internet边缘节点的资源收集起来,提供强大的计算和存储能力。P2P的发展,改变了Internet的共享行为。在分布计算、协同工作、搜索引擎、文件交换等方面有着广泛的应用前景。P2P网络在没有中心节点的情况下,如何进行资源的查找定位是一个很重要的问题,特别是查找的高效性和可靠性。目前的解决方案主要是:增加中心节点完成查找工作形成混合式P2P网络;非结构化P2P网络的泛洪算法和结构化P2P网络的DHT算法。混合式P2P网络以Napster为代表,它的中心节点是整个系统的瓶颈,它的失效将导致查找的完全失效;泛洪算法以Gnutella为代表,解决了中心节点的瓶颈问题,但泛洪算法导致数据报在网络中广播,随着网络规模的增长,四处广播的数据报很快就把网络带宽耗尽;为了避免泛洪式搜索产生的冗余消息,研究人员提出了结构化P2P网络,采用基于分布式哈希表(DHT)的路由算法,DHT路由算法使用分布式哈希函数进行资源定位,快速、可扩展性好;研究人员开发了多个DHT算法,如Tapstry、Pastry、CAN、Kademlia、Chord。其中MIT提出的Chord算法在网络节点变化剧烈的环境中仍然具有较好的性能。本文研究了各种P2P的资源查找算法,特别重点研究了基于DHT的Chord算法,并分析了Chord路由算法的效率,在此基础上,提出了查找内容缓存和三阶Chord相结合的查找方法,查找内容缓存对节点查找成功的内容保存在节点本地,当节点再次查找相同内容时可快速地定位到目标节点,减小了消息转发次数,三阶Chord使每个节点保存了更多节点的路由信息,节点在查找消息转发时,不断对Chord环进行三分,加大了消息转发的路由跨度,查找请求更快地转发到目标节点。通过查找内容缓存和三阶Chord结合,改进了原有Chord的路由效率。最后,本文采用了p2psim仿真系统对改进算法进行仿真,通过仿真测试,验证了改进方法在保证原有Chord的性能提前下,减小了查找消息在网络上的转发次数,也就减小了查找消息的网络延迟,提高了资源查找效率。通过分析和仿真测试,改进算法具有更好的性能,是可靠可行的资源查找算法。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 研究背景
• 1.2 P2P 的概念
• 1.3 P2P 的特点
• 1.4 P2P 的应用
• 1.5 P2P 网络模型
• 1.6 P2P 网络的资源查找
• 1.7 P2P 搜索研究意义
• 1.8 国内外研究动态
• 1.9 本课题的创新点
• 1.10 本文章节安排
• 第二章 P2P 网络中的资源定位
• 2.1 混合式P2P 网络搜索
• 2.2 分布式非结构化P2P 网络搜索
• 2.2.1 基本搜索方法
• 2.2.2 改进的搜索方法
• 2.3 分布式结构化P2P 网络搜索
• 2.3.1 DHT
• 2.3.2 一致性哈希（Consistent Hash）
• 2.3.3 CAN
• 2.3.4 Pastry
• 2.3.5 Tapestry
• 2.3.6 Kademlia
• 2.3.7 Chord
• 2.4 本章小结
• 第三章 Chord 改进算法
• 3.1 Chord 的性能分析
• 3.1.1 Finger table
• 3.1.2 路由效率
• 3.2 Chord 路由表改进
• 3.2.1 三阶Chord 路由表结构
• 3.2.2 三阶Chord 性能分析
• 3.2.3 高阶Chord
• 3.2.4 高阶Chord 的选择
• 3.3 查找缓存策略
• 3.3.1 缓存
• 3.3.2 查询
• 3.3.3 缓存列表维护
• 3.4 Chord 改进算法
• 3.4.1 设计
• 3.4.2 查找
• 3.4.3 分析
• 3.5 本章小结
• 第四章 仿真测试
• 4.1 仿真软件设计原理
• 4.1.1 未来事件列表
• 4.1.2 仿真时钟及其推进机制
• 4.1.3 系统的状态变量
• 4.1.4 事件进程
• 4.1.5 随机数发生器
• 4.1.6 仿真结果的输出和分析
• 4.1.7 系统调度模块
• 4.2 网络仿真的一般步骤
• 4.3 仿真的实现
• 4.3.1 p2psim 的结构
• 4.3.2 改进算法的仿真程序
• 4.4 仿真条件设置
• 4.5 仿真结果
• 4.6 本章小结
• 第五章 结 论
• 5.1 全文总结
• 5.2 未来工作
• 致谢
• 参考文献
• 在学期间研究成果