高阶Chord：一种新型P2P查找策略

摘要

P2P提供无穷的存储空间以及不受限制的传输容量，这是传统中央服务器所无可企及的。P2P网络中的节点既是服务使用者，也是服务提供者。整个网络应用的核心从中央服务器向网络边缘的终端设备扩散。目前因特网以网站为中心的状态终将彻底改变，人们将会以更主动的方式参与到网络活动中去。从C/S模式到P2P模式的发展，Internet上的共享行为被提升到了一个更高的层次。　　所有这些P2P应用面临的最核心问题就是如何在没有中心节点的情况下完成资源的查找，并且能保证查找过程的高效性、可靠性、可伸缩性。目前很多研究都集中在基于DHT的方法上。利用DHT实现的查找算法比较多，比较知名的包括最早的Plaxton算法及其变种Tapstry，微软提出的Pastry，伯克立和AT&T提出的CAN等等。特别是MIT提出的Chord算法在网络节点变化剧烈的环境中仍然具有较好的性能。这一点非常重要，因为现实中P2P网络的节点自治性必然导致网络结构频繁变动。在这些恶劣条件下能保持较高的查询效率才是最重要的。　　本文在此基础上提出Chord中“阶”的概念。指出经典Chord算法相当于2阶的Chord，并讨论了一种更为一般化的资源查找策略：高阶Chord。根据高阶Chord的结构我们可以构造出阶数大于2的任何阶Chord。高阶Chord将会使查询请求更快地转发到目标节点。但是为此节点必须维护更大的路由表。可以预见相比于减少转发次数带来的收益，维护路由表的代价是比较低的。因此可以通过高阶Chord的算法为P2P网络提供一种更为有效的查询策略。　　为了验证在节点频繁变化的实际网络环境中高阶Chord的实际性能表现，本文在p2psim的基础上实现了高阶Chord算法的仿真系统。通过仿真验证了理论分析的正确性——高阶Chord在P2P网络中的查询性能更加优良。

目录

文摘

英文文摘

第1章绪论

1.1背景

1.1.1 P2P网络的发展

1.1.2 P2P网络的现状

1.2 P2P网络中的资源查找

1.3本文所作的工作

第2章P2P网络中的资源定位

2.1洪泛算法

2.1.1 Gnutella

2.2基于DHT的算法

2.2.1 Tapestry

2.2.2 Pastry

2.2.3 CAN

2.2.4 Chord

2.3本章小结

第3章新的资源查找策略：高阶Chord

3.1 Chord的性能瓶颈

3.2对Chord的查询消息路由的分析

3.2.1节点饱和假设

3.2.2路由表结构

3.2.3未取模前的successor序列

3.2.4取模后的环形结构

3.2.5 Chord的路由效率

3.3新的查找策略

3.3.1三阶Chord路由表结构

3.3.2三阶Chord的路由表指针模型

3.3.3三阶Chord的性能

3.3.4 k阶Chord的性能

3.4本章小结

第4章新算法的仿真

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高阶Chord仿真程序

4.4仿真条件设置

第5章结果分析

5.1模拟查询次数和成功率

5.2平均查询时间

5.3 10％分位时间

5.4中位线时间

5.5 90％分位时间

5.6小结

第6章结论和展望

参考文献

攻读学位期间发表的学术论文

声明

致谢