对等网中Chord协议及算法的研究及改进

论文摘要

对等网应用所面临的一个关键问题是如何有效定位存储特定资源的结点。不同的对等网查找算法采用不同的策略，其查询效率也有所不同。本文分析了一种分布式查找算法Chord。Chord作为第二代对等网算法，以分布式散列表为查找策略。Chord算法是可改进的，并且每个结点只需维持对数级的Chord环上结点数的结点，便可完成通信任务，而且需要传递的信息量也是对数级的。Chord算法具有负载平衡、可靠性、可扩展性等优点，但是它的查询效率比较低。针对Chord算法的不足，本文提出了Full-Chord算法。Full-Chord算法主要改进了Chord算法的指针表，将原来计算指针表的公式扩展为两个，这样可以在顺时针和逆时针两个方向上同时进行。Full-Chord算法在查询开始时，就能将查询限制在半个Chord环上，这样便能更接近目标结点，提高查询效率。通过理论分析，Full-Chord算法的查询效率明显优于Chord算法。对等网中结点加入和离开是很平常的，因此必需考虑对等网的自适应性。关于这个方面，本文做了大量研究，提出了为每个结点再建立一张拥有r个后继结点的后继列表的设想，很好地解决了这个问题。本文还借鉴了small-world领域的研究成果，扩展了Chord算法。通过对结点度数的分析，提出“超级结点”的概念。并且参考Google的网页搜索技术PageRank，给出了计算结点级别的公式noderange，从而能很好地确定超级结点。通过超级结点，可以更加有效地定位资源，提高查询效率。最后，通过仿真测试表明，Full-Chord算法在平均查找路径长度和平均查询时间这两个方面的性能明显优于原始Chord算法。

论文目录

• 摘要
• Abstract
• 第1章 绪论
• 1.1 引言
• 1.2 Chord算法概述及其优缺点
• 1.3 Chord算法的研究及改进现状
• 1.4 论文的研究目的和意义
• 1.5 论文的组织结构
• 第2章 对等网相关技术介绍
• 2.1 分布对象的定位机制
• 2.2 对等网技术的概述
• 2.2.1 对等网的定义
• 2.2.2 对等网技术的特点
• 2.2.3 对等网的应用
• 2.2.4 对等网技术所面临的典型问题
• 2.3 对等网中拓扑结构研究
• 2.3.1 中心化拓扑
• 2.3.2 全分布式非结构化拓扑
• 2.3.3 全分布式结构化拓扑
• 2.3.4 半分布式结构
• 2.4 各主流DHT协议比较分析
• 2.4.1 Chord协议
• 2.4.2 内容寻址网络（CAN）
• 2.4.3 Pastry
• 2.5 本章小结
• 第3章 Chord路由协议分析
• 3.1 散列函数
• 3.1.1 散列函数的性质
• 3.1.2 几种常见的散列函数
• 3.2 动态散列表简介
• 3.3 Chord路由协议
• 3.3.1 概述
• 3.3.2 相容散列（Consistent Hashing）
• 3.3.3 简单的关键字查找
• 3.3.4 可扩展的关键字查找
• 3.4 本章小结
• 第4章 Chord路由算法的改进
• 4.1 Full-Chord算法的提出
• 4.2 Full-Chord算法理论分析
• 4.3 结点的加入和稳定
• 4.4 结点加入对查询的影响
• 4.4.1 Chord环正确性的影响
• 4.4.2 执行查询性能的影响
• 4.5 失效和容错
• 4.6 本章小结
• 第5章 基于small-world理论改进Chord
• 5.1 small-world模型
• 5.2 small-world在对等网中的应用
• 5.3 改进的原理
• 5.4 本章小结
• 第6章 算法仿真与分析
• 6.1 仿真软件介绍
• 6.1.1 P2Psim的结构
• 6.1.2 P2Psim的特点
• 6.2 仿真的实现
• 6.2.1 使用P2Psim仿真与分析
• 6.2.2 仿真环境
• 6.3 仿真结果分析
• 6.4 本章小结
• 结论
• 参考文献
• 攻读硕士学位期间发表的论文和取得的科研成果
• 致谢