基于DHT的结构化P2P路由协议研究

罗樵 陈靖 郭一辰 黄聪慧 空军工程大学电讯工程学院， 陕西 西安 710077

基于DHT的结构化P2P路由协议研究

罗樵 陈靖 郭一辰 黄聪慧 空军工程大学电讯工程学院， 陕西 西安 710077

本文研究了P2P的发展历程，系统地论述了P2P发展过程中不同代的路由协议之间的联系与区别，重点介绍了应用最为广泛的基于DHT的结构化P2P路由协议的核心思想。设计了实现了基于DHT的结构化P2P路由模型中的关键算法，最后简单介绍了DHT在实际中的应用等方面。

DHT；P2P；Chord

引言

P2P (Peer - to Peer Network，简称P2P)是一种新型的网络技术，从它出现开始就迅速成为计算机界关注的热门话题之一，对P2P网络技术的研究也逐渐得到国内外研究者的广泛关注，成为计算机网络技术研究领域发展最快的应用型技术之一。在P2P路由模型研究方向，基于DHT的结构化P2P路由协议研究是其中的热点。

1 P2P网络路由模型的发展历程

1.1 集中目录式P2P网络路由模型

图1 集中目录式P2P路由模型

图1中的模型属于第一代P2P路由模型，主要采用目录查询的方法。它的结构与ClientServer模型的结构相似[1]。它的缺点是：随着网络规模的扩大，共享资源迅速增加，对中央目录服务器进行维护和更新的费用将急剧增加，所需成本很高。

1.2 非结构化P2P网络路由模型

图2 非结构化P2P网络路由模型

图2中的模型属于第二代P2P路由模型，主要采用洪泛法查询方法。它针对由于网络规模的扩大，共享资源迅速增加，对中央目录服务器进行维护和更新的费用将急剧增加，成本很高的特点提出来的。它的缺点是：首先，对等点的查找和定位通过扩散方法来实现，对等点定位过程复杂。其次，随着网络规模的扩大，通过扩散方式定位对等点的方法将造成网络流量急剧增加，从而导致网络拥塞。最后，对等用户的活动都是自发行为，在网络中没有设置任何机制和环节对这些活动进行统计和管理，因此整个系统都处于一种无政府状态。

1.3 结构化P2P网络路由模型[2]

模型继承了集中目录式路由模型中资源目录的做法，又结合分散处理的思量，将庞大的资源路由信息分割成小的块，分别放于每个节点中，即动态哈希表（Distributed Hash Table, DHT），这样每一个节点都相当于一个小的独立的目录服务器，节点中存储周围一定范围的资源的信息，可以单独处理资源请求，这样将数量巨大的资源请求处理工作分散了开来，提高了整个系统的资源共享能力及查询的效率；当用户需要在P2P系统中获取信息时，由于用户预先知道应该搜索哪些节点，避免了非结构化P2P系统中使用的泛洪式查找。因此自从DHT协议出现以后，结构化P2P的应用得到了快速的发展。目前已经有很多较为成熟的DHT协议被提出并且得到了应用。下面我们就重点介绍一下DTH协议。

2 DHT路由协议

2.1 DHT的核心思想及创建方法[3]

结构化P2P网络路由模型的关键性技术为 DHT（Distributed Hash Table）。分布式哈希算法的核心思想是：将存储对象的特征(关键字)经过哈希运算，得到键值(Hash Key)，对象的分布存储依据键值来进行。创建哈希表的C++程序的见表1。

哈希方法具体来讲，大致有以下步骤，如图3。

1）对存储对象的关键字进行哈希运算，得到键值。可以称其为哈希化这样就将所有的对象映射到了一个具体的数值范围中。重叠网中的每个节点负责数值范围中的特定段落。例如，节点A负责存储键值从8000到8999的对象；而节点B负责7000～7999的对象。这样就将对象集合分布地存储在所有的节点中。

2）给哈希化后的值添加相应的本地ID，上一跳的IP，以及离他最近的有相关资源的下一跳IP（这个IP的获取过程是：每个节点都有距离自己较近的一定范围内所有节点的资源信息（DHT），以后在找到资源之后可以通过本地ID的值找到资源所在节点。

2.2 DHT的路由问题[4]

结构化的分布式存储问题解决后，剩下的问题就是用户如何才能找到存储着目标信息的节点。在有着大量节点(如100万基金项目：国家军口863创新基金项目（2009AAJ131）；陕西省自然科学基金（SJ08-ZT15）；空军武器装备军内科研资助项目（KJ09130）；空军工程大学博士启动基金项目（KDYBSJJ08403）资助课题个)的P2P系统中，任何节点都不可能拥有全部的节点（键值）内容的对应关系；因此用户获得了键值之后，如何找到该键值对应的节点就被称为DHT的路由问题。总体来说：依照自身查询，与邻近询问相结合的方法将资源的查询广泛地分布到网络空间的每个节点。总的路由结构如下如图：

图4 DHT节点模式示意图

具体的每一个节点的查找(路由)算法各不相同，如可以用哈希表中常用的线性探测再散列的哈希表，随机探测再散列、二次探测再散列和再哈希表和链地址法处理冲突的哈希表进行查找，这主要受到哈希表的生成机理以及处理冲突的方式不同的影响。但如果将具体的技术层面透明化后，DHT节点查询的思想相同，单个节点哈希查找的C++程序见表2。.

表2 单个节点哈希查找的C++程序

2.3 DHT的动态更新问题

在现实的网络中，计算机节点是处于动态的变化当中的，而存在于节点中的路由信息是网络资源查询的关键，若不能及时的自动维护，将使资源查询的效率降低。即在节点加入/退出分布式系统时，相邻的节点必须及时更新路由信息。这就要求节点不仅存储直接相连的下行节点位置信息、资源信息，还要知道一定深度(n跳)的间接下行节点的相关信息，并且动态地维护节点列表[5]。

2.4 主流DHT路由协议简介

目前国外研究者们提出了多种不同的结构化P2P网络路由模型[6,7]，主要有Chord、CAN、Tapestry和Pastry。这些路由模型设计思想基本相同，但由于这些路由模型是针对不同的逻辑拓扑结构，因此应用不同的DHT算法，比如CAN就是一个N维向量空间，而Chord是一个环形拓扑结构，Tapestry和Pastry则是一个网状的拓扑结构。另外还有缓冲阵列路由协议(CARP，Cache ArrayRouting Protocol)、一致性哈希等。

3 总结

本文阐述了基于DHT的结构化P2P路由协议的核心思想。设计了实现了基于DHT的结构化P2P路由模型中的关键算法，为结构化P2P路由模型的研究提供了参考。

[1] 李祖鹏,黄建华,唐辉. 基于P2P计算模式的自组织网络路由模型. 软件学报.2005

[2] 李振武, 杨舰, 白英彩. 对等网络研究及其挑战. 计算机应用与软件.2004年2月,第21 卷第2 期

[3] 于守健, 朱勤, 乐嘉锦. 一种基于分布式哈希表的Web服务目录系统. 计算机工程. 2007.1

[4] H. BALAKRISHNAN and D. KARGER,Analysis of the evolution of peer-to-peer systems. In proceedings Symp. on the Principles of Distributed Computing,CA, July, 2002.

[5] Ilya Zaihrayeu, Data-Sharing p2p systems:Open Problems, UNITN, June,2003.

[6] Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan. Chord: A Scalable Peertopeer Lookup Service for Internet Applications. http://pdos.lcs.mit.edu/chord/.

[7] P2P的概念与思想. http://blog.csdn.net/crfoxzl/archive/2009/04/29/4135611.aspx.

The Study of Structured P2P Routing Protocol Based on DHT

Luo Qiao Chen Jing Guo Yichen Huang Conghui
Telecommunication Engineering Institute, Air Force Engineering University, Xi'an 710077, China

This paper researches the development of P2P,describes the connection and difference of P2P routing protocols, introduces structured P2P routing protocol based on DHT which is the most widely used. It designs the key algorithm of structured P2P routing protocol based on DHT, introduces the application of DHT on practical aspects in the end.Key words DHT；P2P；Chord

TP391

10.3969/j.issn.1001-8972.2011.08.077

罗樵（1978-），男，四川成都人，博士研究生，研究方向为分布式系统理论与技术;

陈靖（1963-），女，山西洪桐人，教授，博导，研究方向为分布式系统理论与技术；

郭一辰（1988-），男，北京人，硕士研究生，研究方向为分布式系统理论与技术；

黄聪慧（1985-），男，湖南衡阳人，博士研究生，研究方向为分布式系统理论与技术。