基于DHT的P2P路由算法研究

摘要

科技的进步带来了计算机网络及计算机软硬件正如摩尔定律预测那样的快速发展,个人逐渐依赖于计算机网路这个大群体,很想成为网路中的一员来获取满足自己需求的网路资源。然而传统客户机/服务器模型各种弊端暴露出来了,其中的主要矛盾是服务器不能满足客户机的需求同客户机资源的闲置,这一矛盾将使人们青睐于非中心化的模型,即P2P模型,因为P2P网络是一种平等、自由、互联的网络,将不同地域的人们连接地更紧密、更简单、更方便,它体现一种“我为人人,人人为我”的主人公思想。
　　本文首先介绍了四种不同P2P网络的资源定位方式,特别是针对学者们研究最多的基于DHT的资源定位方式进行了详细的分析,同时选择了一些经典路由算法(Chord、CAN和Pastry)进行研究并分析了节点自组织维护机制、节点间路由、节点加入和退出等方面。本文在分析基于DHT的主流网络模型过程中,发现Pastry路由算法是一个很高效且很强容错性的路由算法,它利用了成熟的最长前缀匹配算法及相应地软硬框架。
　　然后本文在结构化的Pastry路由算法基础上,利用小世界模型的思想与节点之间的异构性,建立了一个高效、动态的、扩展的新分层分簇的网路模型CCPastry(Centernode based Cluster Pastry基于中心节点分簇的Pastry网路模型),CCPastry模型主要是减少路由表的规模与路由表中节点标识符的位数、增加索引机制与可管理性及节点的异构型来改进路由效率,提高该模型的性能。
　　本文对改进后的分层分簇的CCPastry网络模型进行了详细设计及阐述,CCPastry网络是本文的核心部分,包括模型思想的引入、组网机制、节点的加入、节点退出、路由更新维护机制和路由算法等。最后,本文使用通用P2P仿真器PeerSim模拟了CCPastry模型,对该模型的合理性与路由效率做了大量的测试,最终的实验结果验证了该模型的高效性,到达了本文的写作与研究目的。

目录

摘要

Abstract

第1章 绪论

1.1 研究背景

1.2 研究现状

1.2.1 国内研究现状

1.2.2 国外研究现状

1.3 本文研究目的与意义

1.4 本文研究工作

1.5 本文组织结构

第2章 P2P网路概述

2.1 P2P的定义

2.2 P2P模型与C/S模型的比较

2.2.1 C/S模型的优缺点

2.2.2 P2P模型的优缺点

2.3 P2P的应用

2.4 P2P网络的分类

2.5 本章小结

第3章 基于DHT的路由算法

3.1 Hash函数

3.2 DHT介绍

3.3 Chord协议

3.3.1 Chord组网方式

3.4 Pastry协议

3.4.1 Pastry组网方式

3.5 CAN协议

3.5.1 CAN组网方式

3.6 本章小结

第4章 CCPastry模型

4.1 CCPastry模型思想的引入与目的

4.2 CCPastry模型架构

4.2.1 CLayer层(Center node Layer)

4.2.2 CBLLayer层(Center node Backup node,Leaf node Layer)

4.3 节点描述

4.3.1 节点ID

4.3.2 节点分类

4.3.3 节点状态表

4.4 CCPastry组网算法

4.5 CCPastry键值的发布与查询

4.5.1 CCPastry键值的发布

4.5.2 CCPastry键值的查询

4.6 叶子节点的加入与退出

4.6.1 叶子节点加入

4.6.2 叶子节点退出

4.7 中心节点的加入与退出

4.7.1 中心节点的加入

4.7.2 中心节点的退出

4.8 CCPastry与Pastry比较

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

5.1 P2P网络模拟器分类

5.2 PeerSim的介绍

5.3 CCPastry仿真实现

5.3.1 仿真环境

5.3.2 仿真过程

5.3.3 网络性能分析

第6章 总结与展望

6.1 总结

6.2 展望

致谢

参考文献

攻读硕士学位期间发表的论文及参加的科研情况