支持多关键字查询的改进Chord算法

论文摘要

P2P网络的应用越来越多地受到了人们的关注。现在，P2P网络面临的关键问题就是如何准确快速并且全面地定位共享资源。不同的P2P网络采用的拓扑结构也各不相同，它们的查询效率也各不一样。本文分析了一种完全分布式结构化拓扑结构网络模型—Chord模型。Chord模型采用了一致性哈希算法，以分布式散列表为查找策略。在Chord模型中，每个节点只需维护O（logN）条节点路由信息便可快速地定位共享资源。Chord算法在很多方面体现出了一定的优势，如：很好的负载均衡、高可靠性、高可扩展性等。但是，由于哈希算法的使用，Chord算法不支持多关键字查询，因此也不能全面地定位到共享资源。针对Chord算法的不足，本文提出了一种改进Chord算法。在改进的Chord算法中，放弃了通过一致性哈希算法得到共享资源标识的机制，采用了Bloom Filter算法来获取资源标识，但是仍然使用一致性哈希函数来获得节点标识。各个节点和资源不是按照各自标识的大小顺时针排列在Chord环上。在本文中，首先把Chord环分段，其次把各个节点和资源根据标识中1bit的个数映射到Chord环中的不同段内，然后按照整数标识的大小，由小到大顺时针地排列在Chord环的段内。当查找共享资源时，首先跳转到对应的Chord环段内，然后根据资源标识的最长后缀匹配进行查找。为了更加快速地定位到共享资源，每个节点存储了更多节点的路由信息。首先，论文假设改进Chord算法中各个节点都存在，不存在的节点标志为虚拟节点，虚拟节点只负责路由信息的转发。各个节点根据自身的二进制向量标识就可推测出自己的路由表信息。路由表信息获取机制是通过自身的二进制向量标识，交换二进制向量标识中高位的0bit和低位的1bit。改进Chord模型不仅仅支持多关键字查询，本文还理论证明了改进Chord算法的最大查询跳数为m–2+1，平均查询跳数为m/2+1，其中m为二进制标识的长度，远远地优于标准Chord算法。最后，对改进Chord算法进行了仿真验证。主要从以下四个方面进行了评估：平均查询跳数、平均查询时延、Bloom Filter错判率和查询时节点的覆盖率。仿真结果与理论相一致，在允许一定错判率的情况下，改进Chord算法明显优于标准Chord算法。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 研究背景
• 1.2 国内外研究现状
• 1.3 研究目的和研究内容
• 1.3.1 研究目的
• 1.3.2 研究内容
• 1.4 论文结构安排
• 2 P2P 系统拓扑结构及搜索算法简介
• 2.1 P2P 系统拓扑结构简介
• 2.2 各种改进 Chord 算法和基于 P2P 复杂查询算法
• 3 DHT 和 Bloom Filter 简介
• 3.1 DHT 简介
• 3.2 Bloom Filter 简介
• 4 Chord 简介
• 5 基于 P2P 多关键字查询的路由算法研究
• 5.1 改进 Chord 模型的构建
• 5.2 改进 Chord 算法 Finger 表的构建及资源查找过程
• 5.2.1 Finger 表构建
• 5.2.2 资源查找过程
• 5.3 改进 Chord 的维护
• 6 仿真实验
• 6.1 仿真工具简介
• 6.2 仿真环境
• 6.3 仿真的实现
• 6.3.1 平均查找跳数
• 6.3.2 平均查找网络时延
• 6.3.3 错判率
• 6.3.4 查询节点覆盖率
• 7 总结与展望
• 致谢
• 参考文献
• 附录
• A 攻读硕士学位期间发表的论文
• B 攻读硕士学位期间参与完成的项目