基于超级节点的改进Chord算法的研究

摘要

近年来，对等网络(P2P，Peer-to-Peer)作为一种新型的网络应用模型以其可扩展性、高度容错性等优点变得越来越流行。P2P网络为资源的快速共享提供了良好的平台。P2P网络中资源的查找和定位是其需要解决的关键问题之一。现有的对等网络资源查找模型算法中，Chord模型算法是第二代P2P网络资源查找算法，它是一种基于分布式哈希散列表(DHT)策略的算法，其功能是实现在P2P网络中，关键字以对数倍定位网络资源。然而，现有的Chord算法存在查找效率不高、不能实行查找的并行性等方面存在不足。针对Chord算法的不足，论文提出了一种基于超级节点的Chord(Based SuperNode-Chord)算法，通过改进finger表，缩短路由选择的时间，提高查询效率。此外，在BS-Chord算法的基础上，本文还设计了相应的网络拓扑模型，通过采用二叉树的链式结构表示普通节点的存储和链接方式，从而实现减少网络抖动、负载均衡、解决拓扑失配的目标。
　　 本研究主要内容包括：⑴深入研究P2P网络模型的特点，以及现有Chord算法的实现和性能，着重分析了Chord算法在P2P网络应用中存在的不足。⑵针对Chord算法的不足，提出了改进BS-Chord算法。通过改进Chord算法的finger表，在节点的finger表中增加了路由信息后，对finger表中node域值相等的项进行合并，从而缩短节点对资源查询消息进行路由选择时所花的处理时间，提高查询效率。⑶在BS-Chord算法的基础上，设计了基于链式结构的网络拓扑模型，通过采用二叉树的链式结构表示普通节点的存储和链接方式。并将模型分为inter-Chord和tree-Chord内外两层。根据节点性能不同分为超级节点和普通节点，从而有效定位资源，并提高查找效率。⑷通过仿真实验和分析表明此方案可以显著改善搜索结果的成功率和大大减少搜索所需的路由跳数，减少网络的抖动性，解决网络节点中的负载均衡问题，并且可以较好地解决拓扑失配问题。在目前结构化P2P环境中，该策略有一定的推广利用和研究价值。

目录

声明

摘要

第1章 绪论

1．1 论文的研究背景和意义

1．2 P2P网络资源定位技术的研究现状及趋势

1．3 论文研究的主要内容

1．4 论文的结构安排

第2章 对等网技术

2．1 对等网技术特点

2．1．1 P2P网络模型的特点

2．1．2 P2P网络的分类

2．2 P2P网络的应用

2．2．1 P2P的应用领域

2．2．2 P2P技术面临的相关问题

2．3 本章小结

第3章 Chord算法分析

3．1 Chord协议算法

3．1．1 算法的基本概念

3．1．2 Chord中用于查询消息的数据结构

3．1．3 Chord中的资源搜索过程

3．1．4 节点的加入与失效处理

3．2 标准Chord算法的性能分析

3．2．1 查询消息的平均路由跳数分析

3．2．2 节点路由表(finger表)平均长度分析

3．3 本章小结

第4章 一种基于超级节点的Chord算法

4．1 传统Chord算法存在的问题及对应策略

4．1．1 节点异构性问题及应对策略

4．1．2 网络抖动性问题及解决方法

4．1．3 节点的负载均衡的问题及解决方法

4．1．4 路由表冗余及其解决方案

4．2 层次DHT网络的组织结构

4．3 BS-Chord模型结构

4．4 算法的描述

4．4．1 叶子节点的加入

4．4．2 叶子节点退出

4．4．3 超级节点加入

4．4．4 超级节点退出

4．4．5 资源搜索算法

4．5 本章小结

第5章 性能分析和仿真实验

5．1 算法的性能分析

5．1．1 路由表存储空间分析

5．1．2 平均查找长度的理论分析

5．2 仿真实验

5．2．1 实验环境

5．2．2 Finger表的平均长度

5．2．3 平均路由长度

5．2．4 平均查找延时

5．2．3 维护开销

5．3 本章小结

第6章 结论和展望

参考文献

致谢

攻读学位期间主要的研究成果