基于DHT的P2P研究 硕士学位论文

硕士学位论文

论文题目 研究生姓名 导师姓名 专业 论文完成时间

基于DHT的P2P研究

张有为

李津生 教授

通信与信息系统

2005年5月

中国科学技术大学硕士学位论文 摘 要

摘要

随着个人计算机性能的提高和互连网用户的急剧增长，在网络边缘出现了大量的闲散计算和存储资源，而网络带宽的大幅提高也使得开发和利用这些潜在的计算资源成为可能。如何有效利用这些大量的计算资源已成为一个热点问题，P2P研究正是在这种背景下展开的。 P2P中文称为对等网络，是指分布式系统中的各个节点是逻辑对等的，与目前互连网上比较流行的C/S计算模型不同的是：P2P计算模型中不再区分服务器和客户端，系统中的各个节点之间可以直接进行数据通信而不需要通过中间的服务器。P2P可以解决传统的C/S模型下服务器带来的性能瓶颈和单一故障点等问题，能够充分利用互联网边缘所蕴含的潜在计算和存储资源。

在大规模的P2P系统中，如何高效地查找到指定的数据是一个非常关键的问题。然而第一代的P2P系统都没有很好地解决这个问题。Napster为了查找音乐文件而配置的目录服务器在用户增多时将成为系统的瓶颈和单一故障点。Gnutella所采用的泛洪查询报文的方法在系统规模扩大时会给网络造成较大的负担，因而同样不具有可扩展性。为了解决P2P系统中可扩展的数据检索问题，国际上几个研究小组独立地提出了Chord、CAN、Pastry和Tapestry等基于DHT的结构化P2P系统。

DHT在应用层上把所有的P2P节点组织成一个结构化的重叠网络，文件索引分布其中，查询报文将通过这个重叠网络路由。DHT在节点失效、遭受攻击和突发性高负载面前都能表现出很好的健壮性；它具有良好的可扩展性，能以较低系统开销获得较大的系统规模；可以自我配置，不需要手工干预就可以自动把新加入节点合并到系统中；能提供简单灵活的接口，可以为多个应用同时使用。本文在第2章对DHT系统进行了综述。

但是目前DHT还面临许多问题，最大的问题之一就是DHT在初始设计时忽略了参与节点在物理网络上的邻近性，导致重叠网络和物理网络脱节，即DHT未能充分利用底层物理网络的拓扑信息，从而造成实际的寻路效率低下。因为路由算法是DHT的核心，所以提高DHT寻路效率是当前基于DHT的P2P研究的重点，具有很重要的意义。

本文围绕DHT寻路效率的改善，对如何提取节点在物理网络上的位置信息和如何利用位置信息构造拓扑敏感(topology-aware)的DHT系统进行了深入的研究，提出了具有层次化标识符的DHT、内嵌式DHT和层次化DHT三种利用拓扑信息改进DHT路由性能的方案，本文通过把Chord改造成Chord6、eChord和hChord来分别阐述这几种方案的思路，并通过仿真和分析阐明了这些方案能有效地改善现有DHT寻路效率。本文在第3章详细介绍了我们的研究成果。

DHT具有广阔的应用前景，国际上许多著名的研究机构都在开展基于DHT的大规模P2P系统研制工作。围绕这个方向，在实验室CNGI预研项目《基于IPv6的P2P弹性重叠网络智能节点的研制》中，我们利用自己提出的Chord6，设计了一个IPv6环境下的文件共享系统FSS6。FSS6不仅可以在实践中检验我们提出的DHT改进方案的有效性，而且还可以充分展示IPv6和P2P技术结合的优越性，推动IPv6的普及发展，加速CNGI的顺利演进；同时，FSS6还将给P2P应用探索一个可运营、可管理和可控制的示范模式，进一步推动P2P应用的良性发展，更好地满足用户需求。本文在第4章详细介绍FSS6的设计。

本文的主要工作和创新点如下：

1. 提出了从IPv6地址前缀中提取节点位置信息的方法。我们注意到IPv6地址分配的

层次性，同一自治域内的主机通常具有一定长度的相同的网络前缀，因而DHT系统中的节点可以从自己的IPv6地址前缀中获取位置信息。IPv6以及P2P系统都是下一代网络中重要的发展方向，本文把两者结合在一起是一个重要的尝试。 2. 提出了一种构建层次化节点标识符的方案。我们创造性的提出节点标识符可以分段

I

中国科学技术大学硕士学位论文 摘 要

构造，标识符的前缀可以通过哈希同一个域中节点共同的位置信息得到，从而使得物理网络上临近的节点在重叠网络上也互为近邻。作为示例，本文结合IPv6和Chord，构造了一种改进型的DHT系统－Chord6，仅仅对Chord协议做了很小的改动就取得了很好的寻路性能改善，并通过仿真验证了这种方案的有效性。我们指出构建层次化节点标识符的思想完全可以应用于其他的DHT系统中，如CAN和Pastry等。

3. 提出了一种构造内嵌式DHT的方案，既改进了寻路效率又保持了原有DHT系统

的负载平衡性质。本文创新性的提出把节点的位置信息也存储到DHT系统中，新加入的节点可以通过DHT查询到具有相同位置信息的全部节点列表，从而在物理网络上临近的节点之间构造内嵌于全局DHT中的本地DHT。这样，路由可以先在本地DHT中进行，必要时经由全局DHT，从而避免多次跨域路由。该方案具有完全分布式的特点。作为示例，本文利用这种思想对Chord进行了改进，构造了eChord。仿真的结果证明该方案的有效性。

4. 提出了构造层次化DHT的方案，按物理网络的远近把节点划分为多个组，使得节

点动态加入和退出的影响局限在单个组中；同时也把关键字分层存储以支持部分查询。初步的分析结果证明这种方案具有良好的部分查询性能。

5. 利用我们自己提出的Chord6，设计了一个IPv6环境下的文件共享系统FSS6。

关键字：P2P，DHT，Chord，查找，寻路，IPv6，拓扑，层次化，文件共享

II

中国科学技术大学硕士学位论文 Abstract

Abstract

With the great improvement of PC performance and the fast growth of Internet users, there emerges a vast quantity of computing and storage resources on the Internet edge. P2P (peer-to-peer) technology can be an effective means to harness these resources, which accounts for the fact that P2P applications are becoming more and more popular these days.

In a P2P system, all peers are identical regarding functionality. Unlike the traditional C/S (client/server) model, there are no dedicated servers and peers can directly communicate with each other for data transmission. P2P can solve the problems of single point failure and performance bottle encountered by C/S model.

A fundamental problem that confronts a large-scale P2P system is the efficient location of the node that stores the desired date item. However, the first generation of P2P systems did not address the problem well. Napster has a centralized index server where scalability can be limited by the machine power and the network bandwidth of the central point. Gnutella employs a messaging mechanism that is based on flooding, which can impose heavy burden on networks and thus compromise its scalability. To address the problem, several research groups independently proposed DHT (distributed hash table) systems, which include Chord, CAN, Pastry and Tapestry. DHTs reorganize peers into an overlay in the application level, distribute file indexes into the network, and route queries through the overlay. DHTs are robust in the face of failures, attacks and unexpectedly high loads. They are scalable, achieving large system sizes without incurring undue overhead. They are self-configuring, automatically incorporating new nodes without manual intervention or oversight. They provide a simple and flexible interface and are simultaneously usable by many applications.

However, DHTs are still faced with many problems, one of which is the fact that most DHTs do not take into account physical network topology in their original design, thus resulting in high routing latency and low efficiency. Therefore, to improve routing performance is an important direction for research on DHT-based P2P. While centering on the issue of routing enhancement, the author has conducted an in-depth research on how to extract topology information and how to utilize that information to construct topology-aware DHT systems. In Chapter 3, we propose three solutions, which are called DHT with hierarchical identifiers, embedded DHT and hierarchical DHT. To illustrate our solutions, we build Chord6, eChord and hChord all upon the original Chord system. Analysis and simulation results prove that our solutions can greatly improve routing efficiency in Chord.

Currently, a new generation of applications has been proposed on top of DHTs. In this paper, we also design a wide-area file-sharing system based on Chord6, validating the effectiveness of our research work on DHT routing enhancement.

The major contributions of this paper are listed as follows:

1. Propose a novel method to extract topology information from IPv6 address prefixes. We

notice that IPv6 addresses are assigned in a hierarchical way so that nodes with the same

prefix are in the same autonomous domain. Therefore peers in a DHT system can learn their location information from their own IPv6 addresses.

2. Devise a smart scheme to exploit the IPv6 address hierarchical feature, so as to construct

an efficient version of Chord dubbed Chord6. We propose that node identifiers can be divided into several parts and thus be produced separately. For a node identifier divided

III

中国科学技术大学硕士学位论文 Abstract

into two parts, the higher bits can be obtained by hashing the shared address prefix among all nodes within the same AS, and the lower bits are the hash result of the rest of the IPv6 address. As a result, topologically close peers shall also be adjacent in the overlay. An important advantage of our scheme is that it is very simple and barely modifies the original Chord. Simulation results have shown that our method can significantly reduce inter-domain traffic that causes the long routing latency.

3. Devise a novel scheme to construct embedded DHT, which can not only improve the

routing efficiency, but also inherit the load-balancing feature of the original DHT. First, nodes independently insert their location information into DHT systems as they do with file indexes. Then, a newly joined node can utilize DHT to get a complete list of all nodes that are close to it in the underlying physical networks. Finally, nodes within the same domains are organized into many local DHTs which are then embedded into a global DHT comprised of all nodes. Thus, routing can be conducted in local DHTs first, and pass through each other (if necessary) with the aid of the global DHT, which means that inter-domain traffic can be minimized to the extreme. To illustrate the feasibility and effectiveness of the scheme, we construct eChord upon the original Chord system. Analysis and simulation demonstrate that our scheme is very effective.

4. Propose a new kind of hierarchical DHT dubbed hChord, in which topologically close

nodes are grouped in the overlay and keys are stored in a hierarchical way. Analysis

show that hChord can isolate the effect of dynamic nodes within small groups for better scalability and stability, and show improved performance with partial queries. 5. Present a prototype design of an IPv6-based wide-area file sharing system based on

Chord6.

Keywords：P2P，DHT，Chord，look up, routing，IPv6，topology，hierarchical, file sharing

IV

中国科学技术大学硕士学位论文 目录

目录

摘要..................................................................................................................................I Abstract .......................................................................................................................... III 目录................................................................................................................................ V 第1章 序论 .................................................................................................................. １

1.1 P2P研究背景 ..................................................................................................... １

1.2 什么是P2P ....................................................................................................... ２ 1.3 为什么需要P2P ................................................................................................ ３ 1.4 P2P的应用领域 ................................................................................................. ４

1.4.1 信息共享 ................................................................................................. ４ 1.4.2 实时通信 ................................................................................................. ４ 1.4.3 网络游戏 ................................................................................................. ４ 1.4.4 金融服务 ................................................................................................. ４ 1.4.5 信息检索 ................................................................................................. ５ 1.4.6 协同工作 ................................................................................................. ５ 1.4.7 普及计算 ................................................................................................. ５ 1.4.8 网络存储 ................................................................................................. ５ 1.5 如何实现P2P .................................................................................................... ６

1.5.1 基于目录服务器P2P ................................................................................ ６ 1.5.2 非结构化P2P .......................................................................................... ７

1.5.3 结构化P2P .............................................................................................. ７ 1.6 本章小结 .......................................................................................................... ８ 第2章 DHT基本原理 ................................................................................................... ９

2.1 引言 ................................................................................................................. ９

2.2 Chord................................................................................................................. ９

2.2.1 Chord的设计............................................................................................ ９ 2.2.2 Chord的路由......................................................................................... １０ 2.2.3节点加入和退出 .................................................................................... １２ 2.3 Pastry.............................................................................................................. １３

2.3.1 Pastry的设计......................................................................................... １３ 2.3.2 Pastry的路由......................................................................................... １４ 2.3.3 节点加入和退出 ................................................................................... １４ 2.4 CAN ............................................................................................................... １５

2.4.1 CAN的设计 .......................................................................................... １５ 2.4.2 CAN的路由 .......................................................................................... １６ 2.4.3 节点加入和退出 ................................................................................... １６ 2.5 Tapestry .......................................................................................................... １７

2.5.1 Tapestry的设计 ..................................................................................... １７

2.5.2 Tapestry的路由 ..................................................................................... １８ 2.5.3 节点加入和退出 ................................................................................... １９

2.6 本章小结 ....................................................................................................... ２０ 第3章 利用拓扑信息改进DHT .................................................................................. ２１

3.1 引言 .............................................................................................................. ２１

V

中国科学技术大学硕士学位论文 目录

3.2 获取位置信息 ................................................................................................ ２１ 3.2.1 分布式网络测量技术 ............................................................................ ２１ 3.2.2 IP地址蕴涵拓扑信息............................................................................. ２２ 3.3具有层次化标识符的DHT ............................................................................... ２３

3.3.1 Chord6的设计 ....................................................................................... ２３

3.3.2 分析与仿真 .......................................................................................... ２５ 3.3.3 小结和进一步讨论 ................................................................................ ２７ 3.4 内嵌式DHT ................................................................................................... ２８

3.4.1 eChord的设计 ....................................................................................... ２８

3.4.2 eChord的路由 ....................................................................................... ２９ 3.4.3 节点的加入和退出 ................................................................................ ３０ 3.4.4 分析与仿真 .......................................................................................... ３０ 3.4.5 小结和进一步讨论 ................................................................................ ３２ 3.5层次化DHT .................................................................................................... ３３

3.5.1 hChord的设计 ....................................................................................... ３３ 3.5.2性能评估和进一步的讨论 ...................................................................... ３６

3.5.3 结语和未来工作 ................................................................................... ３７ 3.6 本章小结 ....................................................................................................... ３８ 第4章 基于DHT的P2P系统设计与实现 ................................................................... ３９

4.1 FSS6 ............................................................................................................... ３９

4.1.1 设计目标 .............................................................................................. ３９

4.1.2 系统结构 .............................................................................................. ３９ 4.1.3 Chord6实现 .......................................................................................... ４０ 4.1.4 智能节点设计 ....................................................................................... ４２ 4.1.5 消息处理 .............................................................................................. ４３ 4.2 相关的研究 .................................................................................................... ４４

4.2.1 CFS....................................................................................................... ４４ 4.2.2 PAST..................................................................................................... ４４ 4.2.3 OceanStore ............................................................................................ ４５ 4.3 本章小结 ....................................................................................................... ４５ 第5章 结束语 ............................................................................................................ ４６ 攻读硕士期间发表的论文 ............................................................................................ ４７ 致谢............................................................................................................................ ４８ 缩略语索引 ................................................................................................................. ４９ 参考文献..................................................................................................................... ５０

VI

中国科学技术大学硕士学位论文 第1章 序论

第1章 序论

1.1 P2P研究背景

正如摩尔定律所指，“每十八个月处理器性能提高一倍，而价格降低一半”，在个人计算机的计算性能和存储容量得到极大提高的同时，计算机的低廉价格也让其使用越来越广泛。同时，随着近年来计算机通信技术的飞速发展，大量的个人计算机接入Internet，从而导致Internet规模不断扩大，Internet入网的主机数、上网的人数都在飞速增长。图1.1给出的是从1991年到2004年Internet入网主机数的增长曲线【1】。图1.2给出了在线用户数统计【2】。

图1.1 1991年到2004年Internet主机数增长曲线【1】(单位：百万)

图 1.2 Internet全球在线用户数变化趋势【2】

另外，接入Internet的设备也变的多样化，不仅有大型机、PC机，而且有越来越多的像手机和PDA这样具有计算能力的手持终端设备。很明显，网络边缘分布着大量的计算和存储资源。但是，在传统的C/S (Client/Server, 客户/服务器)模式下，这些资源没有能够得到很好的开发和利用。因而，如何有效地利用这些计算和存储资源也随之成为研究的热点。

１

中国科学技术大学硕士学位论文 第1章 序论

P2P（Peer to Peer，对等网络）技术出现的目的就是希望充分利用互联网中所蕴含的潜在计算和存储资源。

1.2 什么是P2P

P2P中文称为对等网络，是指分布式系统中的各个节点是逻辑对等的，与目前互连网上比较流行的C/S计算模型不同的是：P2P计算模型中不再区别服务器以及客户端，系统中的各个节点之间可以直接进行数据通信而不需要通过中间的服务器。也就是说，对等网络中每个节点的地位是对等的，既可充当服务器为其它节点服务，也可充当客户机消费其它节点提供的服务。如图1.3所示，P2P构建了一种完全分散式的网络结构，不同于C/S的集中模式。

ClientClientServerClient

图1.3(a) C/S模式网络 图1.3(b) P2P模式网络

Client

P2P大体又可分为两种类型。一种是配置了管理服务器的混和型P2P，如图1.4(a)所示。这里的服务器并不提供传统的数据服务，它主要是对节点间的通信进行控制和管理，节点在服务器的帮助下相互之间进行数据通信。目前流行的P2P软件如Napster【3】和BitTorrent【4】等基本上都属于混和型P2P。混合型P2P易于导入用户认证、安全、和计费功能，但是由于管理服务器的存在，仍然面临着单点故障和扩展性问题。另一种则是不引入任何服务器的完全对等的纯P2P结构，如图1.4(b)所示。纯P2P完全是自组织的，节点之间直接进行数据交换。

Directroy serverpeerpeerpeerpeer

图1.4 (a) 混和型P2P架构 图1.4 (b) 纯P2P架构

peerpeer

２

中国科学技术大学硕士学位论文 第1章 序论

1.3 为什么需要P2P

P2P技术引起人们的热切关注起源于Napster，Gnutella【5】等P2P文件共享软件的迅速推广。这些应用在满足人们快速交换大容量数据的需求的同时，也使得研究人员意识到P2P技术具有的独特优势，可以利用它来解决传统C/S模式存在的弊端。在传统的C/S方式下，由服务器向众多的客户机提供服务，这样做的潜在前提是：假定服务器拥有强大的处理能力、高速网络接口和大容量的存储空间；与此对应，客户机的处理能力通常被认为比较弱小，基本上只是一个高性能的I/O设备。然而，今天计算机和网络的飞速发展使得上面的假设出现了问题。

第一，如1.1节指出，作为客户机的联网主机和用户数目都在飞速增长；同时，网络中

18

要存储和处理的数据也极为惊人，例如Internet上每年产生的网页数据高达2×10字节【6】。这两者都服务器提出了巨大的挑战。无论服务器性能多么优越，它的存储容量都是有限的，硬盘读写速度和网络接口都有一定的限制，CPU处理能力也只能满足一定的要求。随着客户机的增多，服务能力和质量必然会下降。因而面对今天数目巨大的用户以及海量信息处理要求，简单的C/S模式已经不能满足需要。也就是说，服务器负载过重，可能会成为瓶颈。

第二，作为客户机的个人计算机存储和计算能力大为增加，例如今天的主流PC机配置，CPU主频大都达到1－2GHZ，内存512M左右，硬盘动辄就是40G或80G，而LAN或宽带网络接口都有10M或100M。用户主机已经不再是一个简单的I/O设备，再加上网络带宽的提高，用户之间完全有能力进行共享和协作。另外，随着社会和网络的发展，人们对数据存储和传输、高性能计算等也有着迫切的需求，用户希望直接交换信息和数据而不必经由特定的服务器中转。然而，C/S模式无法利用客户端的闲置资源，同时也增加了中转服务成本，给用户节点直接通信带来了不便。

P2P技术避免了C/S结构带来的单点失效和性能瓶颈等问题，它不依赖或尽可能不依赖中央服务器，使得每个参与节点既能作为服务器，也可成为客户机。P2P技术的核心思想就是将网络应用的重心从中央服务器向网络边缘的终端设备扩散；这些终端设备可以是高性能计算机，可以是PC机，可以是手机，也可以是PDA等等。与C/S模式相比，P2P模式有以下一些主要优点：

（1） 信息在用户节点间直接流动，高速、及时、方便，降低了中转服务成本。 （2） 资源的高度利用率。在P2P网络上，闲散资源有机会得到利用，所有节点的资源

总和构成了整个网络的资源，整个网络可以被用作具有海量存储能力和巨大计算处理能力的超级计算机。

（3） 随着节点的增加，C/S模式下服务器的负载会越来越重，将成为系统的瓶颈和单一

故障点。也就是说，一旦服务器崩溃，整个网络也随之瘫痪。而在P2P网络中，每个节点都向网络贡献些资源，如存储空间、CPU周期等。所以，对等节点越多，网络的可靠性也就越高。

（4） 基于内容的寻址方式处于一个更高的语义层次，因为用户在搜索时只需指定具有

实际意义的信息标识而不是物理地址。这将创造一个更加精炼的信息仓库和一个

更加统一的资源标识方法。

（5） C/S 模式下的互联网是完全依赖于中心点 — 服务器的。没有服务器，网络就没有任何意义。而P2P 网络中，即使只有一个对等点存在，网络也是活动的，节点可以随意地将自己的信息发布到网络上。

P2P模式的出现也使得Internet恢复了初始设计的面貌：Internet本身是跨越全球的一个非集中式结构的系统，但是上世纪九十年代在Internet上建立的许多应用系统都是完全集中式

３

中国科学技术大学硕士学位论文 第1章 序论

的，从而改变了Internet设计的初衷。网络技术的飞速发展与迅速普及使Internet成为数据通信的重要手段，网络的发展大大超出了网络的提出者以及早期的建立者的构想。网络规模越来越大，连入网络中的设备以及计算单元的数量和种类也越来越多，然而这些设备以及计算单元并没有得到充分的利用，如果能够将这些设备以及计算单元的处理器计算能力、磁盘存储能力以及网络带宽资源等进行充分利用将会有效缓解目前互联网所面临的一些问题。

1.4 P2P的应用领域

P2P计算技术具有广阔的应用前景，主要应用的领域包括：信息共享、实时通信、网络游戏、金融服务、信息检索、协同工作、普及计算和网络存储等。【7】

1.4.1 信息共享

信息共享一直是网络技术发展的重要推动力，也是P2P技术中最典型的应用。目前人们主要采用Web技术来实现信息资源共享，在基于Web的方式进行信息资源共享时，Web 服务器被用来对大量用户的访问提供有效的服务，因而也经常成为这类系统的性能瓶颈所在。采用P2P技术来共享信息资源可以更加充分的利用网络中的带宽资源，从而提高了系统数据通信的效率。目前有很多研究项目和应用软件都是针对P2P的文件共享的，包括Freenet【8】、Gnutella、Free Haven【9】、Ohaha【10】、BitTorrent、Kazza【11】、eDonkey【12】等。

1.4.2 实时通信

实时通信技术是网络中重要的通信技术，成功的实时通信技术吸引了数以万计的在线用户。目前的实时通信技术一般采用一个中心服务器控制用户的认证等基本信息，节点之间直接进行数据通信。ICQ、OICQ、AIM，MSN等是典型的实时通信系统，这些系统也包含好友列表等基本功能。目前流行的Skype是完全采用P2P技术的即时通信工具。Jabber【13】是一个开放源码的实时通信平台。

1.4.3 网络游戏

宽带网络游戏对于带宽的消耗是比较多的，通过P2P技术，一方面是可以下载游戏场景，另一方面可以省却一些昂贵的游戏服务器。游戏用户之间，可以直接通信，而不需要通过游戏服务器进行转发。

1.4.4 金融服务

由于P2P的沟通只单纯涉及沟通的双方，不会有第三者知道双方沟通的信息，所以P2P非常适合发展在线金融服务。美国的Billpoint公司已将P2P技术应用于电子商务的付费机制，通过eBay（一个有名的在线拍卖网站）向全球35个国家的使用者提供了这种技术，他们可直接用彼此的信用卡进行交易；

４

中国科学技术大学硕士学位论文 第1章 序论

1.4.5 信息检索

搜索引擎是目前人们在网络中检索信息资源的主要工具，目前的搜索引擎如：Google【14】、天网【15】等都是集中式的搜索引擎，人们在需要搜索信息的时候要向服务器发出指令，由服务器把检索出来的相关目录通过一定的排序法则呈现在用户面前，这就会不可避免的带来一些问题，比如：如果服务器信息更新周期长，将有大量过时的信息产生；如何服务器不加鉴别、只是一味的搜集信息，将带来许多无价值的垃圾信息；受设备条件影响，服务器收集的信息有限；受服务器制约，存在单点失效的问题等。

而P2P将以用户为中心，所有的用户都是平等的伙伴。所有人都共享了他们认为最有价值的东西，这将使互联网上信息的价值得到极大的提升。JXTA Search【16】采用P2P的搜索技术来有效的跟踪数据的更新速度、提高访问的有效性以及检索的效率。Pandango【17】搜索引擎也利用了P2P的技术。

1.4.6 协同工作

协同工作是指多个用户之间利用网络中的协同计算平台互相协同来共同完成计算任务。通过采用P2P计算技术个人和组织可以随时采用各种方式建立在线、非在线的协同应用环境。同工作使得在不同地点的参与者可以在一起工作，因为采用文件直接共享的方式可以保证系统中的每个人所获得的信息总是最新的，同时节省了采用单独服务器时对该服务器存储以及性能的要求。Groove【18】是基于Internet的P2P协同应用软件的典型代表，其用户可以直接进行实时的协同工作。

1.4.7 普及计算

普及计算技术研究的是如何充分利用网络中各种各样的计算单元来共同完成大规模的计算任务。由于单一计算单元的计算能力总是有限的，因此人们一般采用并行技术、分布式技术将多个计算单元节点联合起来共同完成大规模的计算任务，同时目前网络中的计算机的计算能力一直利用的不是很充分，人们期望能够充分利用网络中的闲散计算能力来完成大规模的计算任务，这样将会使得网络中所蕴含的海量计算能力得到更加充分的利用。P2P计算技术则为普及计算技术的发展提供了新的机遇。SETI@home【19】是UC Berkeley大学启动的普及计算的研究项目，目前大约吸引了一百万台计算机参与研究。GRID【20】是研究普及计算的典型代表。

1.4.8 网络存储

存储技术一直是人们所关注的一项技术。由于网络规模的扩大，人们对网络的使用也变得十分灵活，人们开始将传统的分布式操作系统、局域存储技术向基于Internet的文件存储系统发展。一些研究项目开始使用基于DHT的P2P技术来组织和存储文件，典型的系统包括：Oceanstore【21】、Farsite【22】等。这些项目的目标都是提供面向全球规模的文件存储服务。

５

中国科学技术大学硕士学位论文 第1章 序论

1.5 如何实现P2P

让对等节点之间进行数据通信，本身不是难点，完全可以通过现有的网络编程技术实现，而如何穿越NAT（Network Address Translater）和防火墙也只是一些技术细节问题。P2P实现的难点在于提供一种对网络中的海量数据进行高效并且可扩展的管理和检索机制。也就是说，如何在庞大的共享数据海洋中有效而快速的查找到感兴趣的文件或服务。依据文件的检索模型和机制，现有的P2P实现可以分为三种类型。它们分别是：基于目录服务器P2P，非结构化P2P，和结构化P2P。

1.5.1 基于目录服务器P2P

这一类系统中设置目录服务器，用于保存用户节点的地址信息和该节点上共享文件的描述信息，文件本身是分散存贮在各个节点上的，实际的文件传输也是在对等节点之间进行，目录服务器仅仅起到中介作用，为节点提供发布和查询文件索引服务，是文件索引的集散地，即在请求服务节点和提供服务节点之间进行匹配。

图1.5 Napster系统结构

Napster是该类系统的典型代表，它的工作过程很简单，如图1.5所示：用户连接到Napster服务器，向服务器递交欲查找的音乐信息（如歌曲名）和自己的IP地址；然后由服务器查找其维护的索引信息库，找到后把存有该音乐文件的其他用户节点的IP地址返回给这个用户；用户依据这些IP地址，选择从其中某些用户主机上下载文件。如用户想要共享本机上的某个音乐文件，只需向服务器登记该文件名和自己的IP地址等信息即可。

基于目录服务器的P2P系统在查找目录的时候，简单高效，但由于依赖集中式的目录服务器，随着用户节点数目的增加，服务器将遭遇瓶颈问题，而且会成为系统的单一故障点，系统的可扩展性差。Napster也因为存在目录服务器才卷入了法律纠纷，面临被关闭的处境。

６

中国科学技术大学硕士学位论文 第1章 序论

1.5.2 非结构化P2P

鉴于集中式目录服务器不仅可能成为系统的瓶颈，而且还可能引发法律纠纷。以Gnutella（见图1.6）为代表的非结构化P2P系统中，文件索引信息不再由集中式的目录服务器存储和管理，而是分散到网络中，由节点自己保存。该类系统采用分布式的索引查找策略。为了查找网络中的文件，节点要随机地维护网络中的其他一些节点作为邻居，以便通过邻居节点广播查询报文。由于P2P网络中存在大量的数据冗余，因而可以通过限制查询报文的TTL值来使得泛洪仅仅发生在P2P网络的局部。

图1.6 Gnutella系统结构

非结构化P2P系统中由于不存在目录服务器，所以没有单点瓶颈问题，不存在单一故障点。然而其缺点也是明显的：在网络中广播查询报文加重了网络通信负担，其查询机制在系统规模扩大时不具有可扩展性。另外，由于查询报文被限制在特定的范围内，所以并不能保证一定可以找到网络中存在的目的数据。

1.5.3 结构化P2P

上面介绍的两类P2P系统都缺乏有效的、可扩展的索引查找机制。为此，近年来许多研究小组在设计可扩展的查找机制方面做了大量的研究工作，提出了Chord【23】、Pastry【24】、CAN【25】和Tapestry【26】等用于构建结构化P2P的分布式哈希表系统（Distributed Hash Table，DHT）。DHT的主要思想是：首先，每条文件索引被表示成一个(K, V)对，K称为关键字，可以是文件名（或文件的其他描述信息）的哈希值，V是实际存储文件的节点的IP地址（或节点的其他描述信息）。所有的文件索引条目(即所有的（K, V）对)组成一张大的文件索引哈希表，只要输入目标文件的K值，就可以从这张表中查出所有存储该文件的节点地址。然后，再将上面的大文件哈希表分割成很多局部小块，按照特定的规则把这些小块的局部哈希表分布到系统中的所有参与节点上，使得每个节点负责维护其中的一块。这样，节点查询文件时，只要把查询报文路由到相应的节点即可（该节点维护的哈希表分块中含有要查找的(K,V)对）。这里面有个很重要的问题，就是节点要按照一定的规则来分割整体的哈希表，进而也就决定了节点要维护特定的邻居节点，以便路由能顺利进行。这个规则因具体系统的不同而不同，CAN，Chord，Pastry和Tapestry都有自己的规则，也就呈现出不同的特性。本文将在第二章中介绍这几种DHT系统。

７

中国科学技术大学硕士学位论文 第1章 序论

DHT(Distributed Hash Table)K VK VK VK VK VK VK VK VK VK VK V 图1.7 分布式哈希表

图1.7给出了一个分布式哈希表的示意图，可以看到每个节点都维护了哈希表的一部分。DHT实际上是把网络中所有的参与节点按特定的规则在应用层重新进行组织，形成了一个结构化的逻辑的重叠网络（Overlay）。这类系统不存在单点瓶颈问题，因为每个节点除了既是客户又是数据服务器外，还提供目录服务器的功能。又因为邻居节点是有目的有规则建立的，所以DHT不需要在网络中泛洪查询报文，而是按照相应的路由规则在系统中转发报文。DHT在节点失效、遭受攻击和突发性高负载面前都能表现出很好的健壮性；它具有良好的可扩展性，能以较低系统开销获得较大的系统规模；可以自我配置，不需要手工干预就可以自动把新加入节点合并到系统中；能提供简单灵活的接口，可以为多个应用同时使用。

但是目前DHT还面临许多问题，Sylvia Ratnasamy 等人在总结现有的DHT路由算法的基础之上【27】提出了结构化对等网络面临着十五个主要问题。其中指出提高DHT路由效率是基于DHT的P2P研究的重点，而P2P路由性能直接影响P2P应用的推广。本文将在第三章中介绍作者围绕这个方向所做的工作。

1.6 本章小结

本章首先介绍了P2P研究的背景，即联网的主机数和用户增加使得网络边缘分布了大量的潜在计算和存储资源，P2P研究正是为了开发利用这些资源。接着讨论了P2P的含义以及P2P研究的必要性，然后本章对P2P的主要应用领域做了概要的介绍。最后，本章指出P2P研究的难点在于设计一种高效可扩展的数据检索机制，并据此将现有的P2P实现分为基于目录服务器P2P、非结构化P2P和结构化P2P三种类型进行介绍，并指出前两种类型的查找机制不具有可扩展性，结构化P2P才是发展的方向和当前研究的热点。

８

中国科学技术大学硕士学位论文 第2章 DHT基本原理

第2章 DHT基本原理

2.1 引言

P2P网络的参与节点可以是来自家庭、学校和公司的计算机或其他计算终端设备，同时在线的用户节点数目常常是成千上万。因而，如何把这些分散在各处的廉价且不可靠的用户节点有效地组织起来，设计一个健壮的可扩展的大规模分布式系统就成为P2P研究中最大的挑战之一。在这个大规模的分布式系统中，如何不引入目录服务器就能高效快速地找到指定的数据则是研究中的核心问题。因此，P2P网络数据检索模型和路由算法的研究具有重要的意义，目前国内外很多研究人员围绕这个问题进行了大量的研究，提出的基于分布式哈希表（DHT）的分布式检索和路由算法因为具有查找可确定性、简单性和分布性等优点，正成为国际上结构化P2P网络研究和应用的热点。例如，自2002年起，美国国家科学基金会（NSF）提供了1200万美元的资金启动了一个为期5年的研究项目IRIS【28】，该项目集中了MIT和UC Berkeley等5所著名高等院校的强大科研力量，为下一代大规模分布式应用研制基于DHT的新型基础设施。

哈希表作为一种数据结构，可以在记录的存储位置和它的关键字之间建立一个确定的对应关系，使每个关键字和结构中一个唯一的存储位置相对应。因而在查找时，只要根据这个对应关系就可以找到给定关键字K的存储位置。分布式哈希表，顾名思义就是把哈希表分散到P2P网络的各个节点上，目的是在记录的存储节点和它的关键字之间建立一个确定的对应关系。这里的一条记录就是一个文件索引，抽象成一个(K, V)对。也就是说给定一个K，就可以按照对应关系找到存储有相应(K, V)对的节点。从这个节点上取得文件索引(K, V)对后，再从V中读出真正存储文件的节点IP地址。

分布式哈希表在节点失效、遭受攻击和突发性高负载面前都能表现出很好的健壮性；它具有良好的可扩展性，能以较低系统开销获得较大的系统规模；可以自我配置，不需要手工干预就可以自动把新加入节点合并到系统中；能提供简单灵活的接口，可以为多个P2P应用同时使用。本章将介绍Chord、CAN（Content Addressable Network）、Pastry和Tapestry这几种最为典型的分布式哈希表系统的原理。

2.2 Chord

Chord【23】是UC Berkeley和MIT共同提出的一种分布式查找算法，目的是为了能在P2P网络中查找数据。给定一个关键字，Chord可以有效地把该关键字映射到网络中某个节点上。因而在P2P网络中只要给每个数据V都赋予一个关键字K，就可以利用Chord在该关键字映射的节点上存储或提取相应的(K, V)对。Chord的突出特点是算法简单，而且可扩展 － 查询过程的通信开销和节点维护的状态随着系统总节点数增加成指数关系。Chord的路由性能优于CAN，而节点加入过程和维护开销又优于Tapestry和Pastry。本文在第三章以Chord作为示例，介绍作者在改善DHT路由性能方面所做的工作。

2.2.1 Chord的设计

Chord中每个关键字和节点都分别拥有一个m比特的标识符。关键字标识符K通过哈希关键字本身得到，而节点标识符N则通过哈希节点的IP地址得到。哈希函数可以选用

９

中国科学技术大学硕士学位论文 第2章 DHT基本原理

SHA-1【29】。所有节点按照其节点标识符从小到大（取模2后）沿着顺时针方向排列在一个逻辑的标识圆环上（称为Chord环）。Chord的映射规则是：关键字标识为K的(K, V)对存储在这样的节点上，该节点的节点标识等于K或者在Chord环上紧跟在K之后，这个节点被称为K的后继节点，表示为successor(K)。因为标识符采用m位二进制数表示，并且从0到2－1顺序排列成一个圆圈，succesor(K)就是从K开始顺时针方向距离K最近的节点。

m

m

图2.1 Chord环

图2.1给出了一个m=6的Chord环，环中分布了10个节点，存储了5个关键字，节点标识前加上N而关键字前加上K以示区别。因为successor(10)=14，所以关键字10存储到节点14上。同理，关键字24和30存储到节点32上，关键字38存储到节点38上，而关键字54则存储到节点56上。

当网络中的参与节点发生变动时，上面的映射规则仍然要成立。为此，当某节点n加入网络时，某些原来分配给n的后继节点的关键字将分配给n。当节点n离开网络时，所有分配给它的关键字将重新分配给n的后继节点。除此之外，网络中不会发生其他的变化。以图2.1为例，当标识为26的节点接入时，原有标识为32的节点负责的标识为24的关键字将转由新节点存储。

显然，为了能在系统中转发查询报文，每个节点要了解并维护chord环上相邻节点的标识和IP地址，并用这些信息构成自身的路由表。有了这张表，Chord就可以在环上任意两点间进行寻路。

2.2.2 Chord的路由

Chord中每个节点只要维护它在环上的后继节点的标识和IP地址就可以完成简单的查询过程。对特定关键字的查询报文可以通过后继节点指针在圆环上传递，直到到达这样一个节点：关键字的标识落在该节点标识和它的后继节点标识之间，这里的后继节点就是存储目标(K, V)对的节点。

１０

中国科学技术大学硕士学位论文 第2章 DHT基本原理

图2.2 简单查询过程

图2.2给出了一个示例，节点8发起的查找关键字54的请求，通过后继节点依次传递，最后定位到存储有关键字54的节点56。在这种简单查询方式中，每个节点需要维护的状态信息很少，但查询速度太慢。若网络中有N个节点，查询的代价就为O（N）数量级。因而在网络规模很大时，这样的速度是不能接受的。

为了加快查询的速度，Chord使用扩展的查询算法。为此，每个节点需要维护一个路由表，称为指针表（finger table）。如果关键字和节点标识符用m位二进制位数表示，那么指针表中最多含有m个表项。节点n的指针表中第i项是圆环上标识大于或等于n+2i-1的第一个节点（比较是以2为模进行的）。例如若s=successor(n+2), 1≤i≤m，则称节点s为节点n的第i个指针，记为n.finger[i]。n.finger[1]就是节点n的后继节点。指针表中每一项既包含相关节点的标识，又包含该节点的IP地址（和端口号）。

图2.3给出了节点8的指针表，例如节点14是环上紧接在(8+20) mod 26=9之后的第一个节点，所以节点8的第一个指针是节点14；同理因为节点42是环上紧接在(8+25) mod 26=40之后的第一个节点，所以节点8的第6个指针是节点42。维护指针表使得每个节点只需要知道网络中一小部分节点的信息，而且离它越近的节点，它就知道越多的信息。但是，对于任意一个关键字K，节点通常无法根据自身的指针表确定的K的后继节点。例如，图2.3中的节点8就不能确定关键字34的后继节点，因为环上34的后继节点是38，而节点38并没有出现在节点8的指针表中。

m

i-1

图2.3 指针表示例

１１

中国科学技术大学硕士学位论文 第2章 DHT基本原理

扩展的查询过程是：任何一个节点收到查询关键字K的请求时，首先检查关K是否落在该节点标识和它的后继节点标识之间，如果是的话，这个后继节点就是存储目标(K, V)对的节点。否则，节点将查找它的指针表，找到表中节点标识符最大但不超过K的第一个节点，并将这个查询请求转发给该节点。通过重复这个过程，最终可以定位到K的后继节点，即存储有目标(K, V)对的节点。

图2.4 扩展查询示例

图2.4中给出一个查找过程的示例。节点8需要查找关键字54。节点8首先检查后继节点的标识，发现54并不落在8和它的后继节点标识14之间，因此节点8再检查它的指针表，发现表中不超过54的最大节点标识是42，所以节点8把查询请求转发个节点42。同理节点42也按照这个规则把请求转发给节点51，节点51发现54落在它和它的后继节点标识56之间，因而就把节点56的标识和IP地址等信息返回给节点8。这个查找过程结束后，节点8就可以根据得到的IP地址等信息直接到节点56上存取与关键字54相关的(K, V)对。

2.2.3节点加入和退出

为了应对系统的变化，每个节点都周期性地运行探测协议来检测新加入节点或失效节点，从而更新自己的指针表和指向后继节点的指针。

新节点n加入时，将通过系统中现有的节点来初始化自己的指针表。也就是说，新节点n将要求已知的系统中某节点为它查找指针表中的各个表项。在其他节点运行探测协议后，新节点n将被反映到相关节点的指针表和后继节点指针中。这时，系统中一部分关键字的后继节点也变为新节点n，因而先前的后继节点要将这部分关键字转移到新节点上。

当节点n失效时，所有指针表中包括n的节点都必须把它替换成n的后继节点。为了保证节点n的失效不影响系统中正在进行的查询过程，每个Chord节点都维护一张包括r个最近后继节点的后继列表。如果某个节点注意到它的后继节点失效了，它就用其后继列表中第一个正常节点替换失效节点。

１２

中国科学技术大学硕士学位论文 第2章 DHT基本原理

2.3 Pastry

Microsoft研究院和Rice大学共同提出的Pastry【24】是用于广域P2P应用的分布式查找和路由系统。Pastry系统中的每个节点都有一个唯一的节点号（nodeId），每条消息都有一个关键字。Pastry可以把消息路由到nodeId和关键字在数值上最接近的那个节点。每个Pastry节点维护节点号空间中和它直接相邻的邻居节点信息。当发生新节点加入、已有节点失效或恢复事件时，Pastry节点会通知上层应用。Pastry是完全分布式的、可扩展的和自组织的，它能够自动应对节点加入、离开和失效。

2.3.1 Pastry的设计

Pastry是自组织的重叠网络，每个节点都被分配一个128位的nodeId。nodeId用于在圆形的节点空间中（从0到2128－1）标识节点的位置，它是在节点加入系统时随机分配的，随机分配的结果是使得所有的nodeId在128位的节点号空间中均匀分布。nodeId可以通过计算节点公钥或者IP地址的哈希函数值来获得。

假设网络包含N个节点，Pastry可以把一个给定的关键字路由到nodeId和该关键字最接近的节点。正常情况下，路由不超过??log2Nb?步（b是配置参数，典型取值为4）。即使?同时发生节点失效，Pastry也可以保证关键字送达目标节点，除非nodeId和关键字临近的节点中有?。 ?|L|/2??个同时失效（|L|是配置参数，典型值取16或32）

为了进行路由，Pastry把nodeId和关键字表示为一串以2为基的数，查询消息被路由到nodeId和关键字在数值上最接近的节点。方法是：每个节点把查询消息转发给下一个节点时，要保证这个节点的nodeId和关键字的相同前缀至少要比当前节点的nodeId和关键字的相同前缀长一个数位（即b个比特）。如果找不到这样的邻居节点，消息将转发给前缀长

度相同但是节点号数值更接近关键字的节点。为此，每个Pastry节点都需要维护状态表：一张路由表，一个邻居节点集和一个叶子节点集。

b

图2.5 nodeId为10233102的Pastry节点维护的状态示意图

１３

中国科学技术大学硕士学位论文 第2章 DHT基本原理

图2.5给出了一个节点维护的数据示意图，b取值为2，所有的数均是4进制的。其中路由表的最上面一行是第0行。路由表中每行的阴影项表示当前节点号中相应的数位。路由表中每项节点的nodeId表示格式是“相同前缀 ＋ 下一数位 ＋ nodeId的剩余位”。图中没有列出相关节点的IP地址。

路由表包括?log?N2b每行包括2-1个表项。第n行的2-1个表项中，每个节点nodeId?行，?bb

的前n个数位和当前节点nodeId的前n个数位相同，而第n＋1个数位和当前节点不同。b的取值是路由表大小和任意两节点间需要的最大路由跳数之间的折衷。例如，当b取4而网络中有10个节点时，每个节点的路由表平均包括75个表项，预期的路由跳数是5。如果网络中有10个节点，则路由表平均会有105项，而预期的路由步数也将增加到7。 叶子节点集维护的是nodeId和本节点最接近的节点，其中一半是nodeId大于当前节点的，另一半是nodeId小于当前节点的。叶子节点集在路由时需要用到。邻居节点集维护按给定的评测指标距离本节点最近的节点，正常的路由过程并不使用邻居节点集，它的主要作用是维护路由的本地性。通常这两个集合的大小分别为2或者2×2。

b

b

96

2.3.2 Pastry的路由

Pastry的路由过程是：节点收到一条查询消息时，首先检查该消息的关键字是否落在叶子节点集范围内。如果是，则直接把消息转发给对应的节点，也就是叶子节点集中nodeId和关键字最接近的节点。如果关键字没有落在叶子节点集范围内，节点就会把消息转发给路由表中的一个节点，该节点的nodeId和关键字的相同前缀至少要比当前节点的nodeId和关键字的相同前缀长一个数位。如果路由表中相应的表项为空，或者表项中对应的节点不可达，这时候查询消息将被转发给前缀长度相同但是节点号数值更接近关键字的节点。除非消息已经到达目的节点，否则这样的节点一定位于叶子节点集中。而且，只要叶子节点集中一半以上的节点不同时失效，就一定可以找到满足要求的节点。很明显，路由的每一步都比上一步向目标节点前进了一步，因此路由过程总是收敛的。

2.3.3 节点加入和退出

新节点加入时需要初始化自身的状态表，并通知其他节点自己已经加入系统。假定新加入节点的nodeId为X，同时假定X在加入Pastry之前知道系统中和自己距离相近的节点A。新节点X首先请求A路由一条“加入”消息，消息的关键字就是X。这条消息最终会到达nodeId和X最接近的节点Z。作为应答，节点A、节点Z以及从A到Z的路径上所有经过的节点都会把自己的状态表发送给节点X。节点X利用这些信息初始化自己的状态表，然后节点X再通知其他节点它已经加入了系统。从交换的消息数量上说，节点加入操作的复杂度为O（log2bN）。

Pastry中节点很可能失效或者突然离开系统。若nodeId空间中的相邻节点无法和某个节点通信时，就认为该节点失效了。一旦节点检测出其叶子节点集L中的某个节点失效，它就会请求该集合中nodeId最大或最小的节点把其叶子节点集L’发送过来。（如果失效节点的nodeId比当前节点的nodeId大，则用叶子集中nodeId最大的节点，反之则用nodeId最小的节点。）当前节点将从L’中选择一个L中没有的活动节点来替代失效节点。如果节点检测出

１４

中国科学技术大学硕士学位论文 第2章 DHT基本原理

其路由表中某项对应的节点失效，它将从该项所在的路由表行中选择另一个节点，要求该节点把路由表中对应位置的项发过来。如果当前节点的路由表中对应行已经没有可用节点了，那么当前节点将从路由表的下一行中选择一个节点，这个过程将继续到当前节点能够得到一个替代失效节点的节点号，或者当前节点遍历了路由表为止。节点也会周期性地和邻居节点集中的节点交换信息以检测这些节点是否仍在Pastry系统中，如果节点检测出其邻居节点集中的某个节点失效，它将请求其他邻居节点把其邻居节点集发送过来并从中选择一个新的邻居节点替换失效节点。

2.4 CAN

UC Berkeley提出的CAN（Content Addressable Network，内容寻址网络）【25】实现了文件索引和存放位置的有效映射，不需要任何形式的中央控制点，节点只需要维护少量的控制状态而且状态数量独立于系统中的节点数量，具有完全自组织和分布式的结构，并且有良好的可扩展性和容错性。

2.4.1 CAN的设计

CAN的设计基于虚拟的d维笛卡儿坐标空间，这个坐标空间完全是逻辑的，和任何物理坐标系统都没有关系。在任何时候，整个坐标空间动态地分配给系统中的所有节点，每个节点负责维护独立的互不相交的一块区域。CAN中的节点自组织成一个代表这个虚拟坐标空间的重叠网络（overlay network）。每个节点要了解并维护相邻区域中节点的IP地址,用这些邻居信息构成自身的坐标路由表。有了这张表，CAN可以在坐标空间中任意两点间进行寻路。

图2.6给出了一个2维的[0, 1]×[0, 1]的笛卡儿坐标空间划分成五个节点区域的情况。虚拟坐标空间采用下面的方法保存（K, V）对。当保存（K1, V1）时，使用统一的哈希函数把关键字K1映射成坐标空间中的点P。那么这个值将被保存在该点所在区域的节点中。当需要查询关键字K1对应的值时，任何节点都可以使用同样的哈希函数找到K1对应的点P，然后从该点对应的节点取出相应的值V1。如果此节点不是发起查询请求的节点，CAN将负责将此查询请求转发到P所在区域的节点上。因此，有效的路由机制是CAN中的一个关键问题。

0.0CDE(0-0.5,0.5-1.0)1.0y(0-0.5,0-0.25)(0.25-0.5,0-0.5)A(0.5-1.0,0-0.5)B(0.5-1.0,0.5-1.0)xZone assigned to node A1.0图2.6 五个节点维护的CAN虚平面

１５

中国科学技术大学硕士学位论文 第2章 DHT基本原理

2.4.2 CAN的路由

CAN中的路由很简单，沿着坐标空间中从发起请求的点到目的点之间的一条路径转发即可。为此，每个CAN节点都要保存一张坐标路由表，其中包括它的邻居节点的IP地址和其维护的虚拟坐标区域。两个节点互为邻居是指：在d维坐标空间中，两个节点维护的区域在d－1维的坐标上有重叠而在剩下的一维坐标上相互邻接。例如，图2.6中D和E是邻接节点，而D和B就不是邻接节点, 因为D和B在X轴和Y轴上都邻接。每条CAN消息都包括目的点坐标。路由时节点只要朝着目标节点的方向把消息转发给自己的邻居节点即可。图2.7给出了查找过程的一个简单的例子。

yINode I::lookup(Key,Value)(1) a=Hashx(key);b=Hashy(key)(2) Route(a, b) -> Node J(3) Node J::get(Key, Value)y=bJ(Key,Value)xx=a

图2.7 CAN的查找示例

如果一个d维空间划分成n个相等的区域，那么平均路由长度是(d/4)(n)，每个节点只需要维护2d个邻居节点的信息。这个结果表明CAN的可扩展性很好，节点数增加时每个节点维护的状态信息不变，而路由长度只是以O（n）的数量级增长。因为坐标空间中两点之间可以有许多条不同的路径，所以单个节点的失效对CAN基本上没有太大的影响。遇到失效节点时，CAN会自动沿着其他的路径进行路由。

1/d

1/d

2.4.3 节点加入和退出

因为整个CAN空间要分配给系统中现有的全部节点，当一个新的节点加入网络时必须得到自己的一块坐标空间。CAN通过分割现有的节点区域实现这一过程。它把某个现有节点的区域分裂成同样大小的两块，自己保留其中的一块而另一块分给新加入的节点。整个过程分为以下三步：

1. 新节点首先找到一个已经在CAN中的节点。

１６

中国科学技术大学硕士学位论文 第2章 DHT基本原理

2. 新节点使用CAN的路由机制找到一个区域将要被分割的节点。

3. 执行分割操作，然后原有区域的邻接区域必须被告知发生了分割，这样新节点才能

被别的节点路由到。

当节点离开CAN时，必须保证它的区域被系统中剩余的节点接管，也即分配给其他仍然在系统中的节点。一般是由某个邻居节点来接管这个区域和所有的索引数据（K，V）对。如果某个邻居节点负责的区域可以和离开节点负责的区域合并形成一个大的区域，那么将由这个邻居节点执行合并操作。否则，该区域将交给其邻居节点中区域最小的节点负责。也就是说，这个节点将临时负责两个区域。

正常情况下，每个节点向其所有邻居节点发送周期性的更新消息，消息中包括自身的区域范围、它的邻居列表以及这些邻居节点负责的区域范围。如果多次没有接收到某个邻居的更新消息，那么节点就认为这个邻居失效了。这时，节点将启动接管机制，并启动一个时钟。失效节点的每个邻居节点相互独立地执行该过程，每个时钟大小都和相应节点负责的区域面积成比例。如果时钟超时，节点将向失效节点的所有邻居节点发送接管消息，该消息中包括它自己的区域面积信息。当某个节点接收到接管消息后，如果它的区域面积比发出消息的节点大，那么它将取消接管操作。否则它将发出自己的取代消息。采用这种机制可以有效地选择面积最小的邻居节点来接管失效节点。在特殊情况下，还有可能出现多个相邻的节点同时失效的情况。例如，节点检测到某个节点失效，但是失效节点地邻居中超过一半可能都不可达。这时，如果让该节点接管失效节点地区域，就有可能导致CAN中状态不一致。所以在这种情况下，CAN在执行修复操作之前，会搜索失效区域附近的节点，搜索逐步扩大直至获得足够的邻居状态，以便安全地开始接管过程。

2.5 Tapestry

Tapestry【26】是UC Berkeley提出的一种新型的P2P网络定位和路由算法。该算法可以对消息进行与位置无关的路由，把查询消息传递到最近的存储有目标对象拷贝的节点。Tapestry具有自组织、容错和负载平衡等特点。每个Tapestry 节点只需维护O（log N）大小的路由表信息，路由最多在O（log N）跳数内完成。

2.5.1 Tapestry的设计

Tapestry从一个标识符空间中为每个节点随机分配一个节点标识符nodeID，对象也从同一个标识符空间中分配一个全局唯一标识符GUID（globally unique identifier）。Tapestry使用SHA-1来产生标识符，使得nodeID和GUID均匀分布在标识符空间中。为了讨论问题的方便，用Nid来表示节点N的标识符，用OG表示对象O的标识符。Tapestry目前使用160比特的标识符空间，标识符用一个全局统一的进制表示（例如使用16进制，则标识符是一个40位的数字），所有的节点依据标识符自组织成一个重叠网络。

Tapestry动态地把每个标识符G映射到当前系统中一个节点上，该节点称为G的根节点，表示为GR。如果某节点的Nid＝G，则这个节点就是G的根节点。为了转发查询消息，每个节点需要维护一个邻居映射表，每个表项包括一个邻居节点的标识符和IP地址。往GR路由时，消息将沿着邻居指针向节点标识符在标识符空间中更接近G的节点转发（例如，匹配更大的前缀）。

Tapestry中的每个节点都保存有邻居映射表。邻居映射表可以用于把消息按照目的地址一位一位地向前传递，比如从4***=>42**98=>42A*=>目的节点42AD（这里*表示通配符）。

１７

中国科学技术大学硕士学位论文 第2章 DHT基本原理

这种方式类似于IP分组转发过程中的最长前缀匹配。节点N的邻居映射表分为多个级别，每个级别包含的邻居节点的数量等于标识符表示法的基数，而每个级别中邻居节点标识符和本节点标识符的相同前缀都比前一级别多一个数位。也就是说，第j级邻居表的第i项是标识符以prefix(N, j-1) ＋ “i”为前缀而且离当前节点最近的邻居节点。例如，节点325AE的邻居映射表中第4级第9项是系统中标识符以325 + “9” =3259为前缀的某个节点。

图2.8 Tapestry节点邻居实例

图2.8给出了一个节点的邻居指针实例，从图中可以看到第一级的邻居节点标识和本节点标识没有共同前缀，而第二级的邻居节点标识都以4开头，即和本节点标识具有相同的一个数位的前缀。

2.5.2 Tapestry的路由

Tapestry采用的基本查找和路由机制和【30】很类似。当一条查找消息到达传递过程中的第n个节点时，该节点和目的节点的共同前缀长度至少大于n。为了进行转发，该节点将查找邻居映射表的第n+1级中和目的标识符下一数位相匹配的邻居节点。转发过程将在每个节点中依次进行直到到达目的节点。这种方法可以保证路由至多经过logbN个节点就可以到达目的节点，这里N是节点标识符名字空间的大小，而b是标识符使用的基数。同样，由于每个节点的邻居映射表的每个级别只需要保存b个表项，因此，邻居映射表的空间为blogbN。

图2.9 Tapestry路由实例

图2.9给出了Tapestry中一个查询消息转发的例子。图中节点标识符的基数是4，查询

１８

中国科学技术大学硕士学位论文 第2章 DHT基本原理

消息从5230发出，目的节点是42AD。

Tapestry中的节点在共享数据时被称为服务器，请求数据时被称为客户，转发消息时被称为路由器。也就是说每个节点可以同时具有客户、服务器和路由器的功能。

服务器S通过向对象O（GUID为OG）的根节点OR定期的发送消息来报告S保存有对象O。在这条发布路径上的每个节点都保存关于这个对象O的位置信息指针，这里的位置信息只是一个指向S的指针，而并不是对象O的拷贝。当多个都存有同一对象拷贝的服务器分别向根结点发布消息时，路径上的每个节点按各个服务器离自己的网络时延递增的顺序保存这些位置指针列表。

当需要定位一个对象O时，客户向对象O的根节点发出查询消息，查询消息转发路径上的每个节点都检查自己是否存有对象O的位置指针，如果有，该节点直接把查询消息转发个服务器S，否则，消息将到达O的根节点，然后由根节点把查询消息转发给服务器。 Tapestry有一个重要的特性是：查询消息可以被转发到距离客户最近的存有对象拷贝的服务器上。在Tapestry中，从两个临近节点向同一个目的节点OR发出两条消息时，它们的转发路径很快就会交叉，这是因为路由过程的每一步都是使得下一个节点标识符和OR具有更长的相同前缀；到根结点的路径只是目的标识符的函数，而不是消息发起节点标识符的函数；而且，路由过程中的下一跳邻居节点是根据网络距离选择的，因而客户离服务器越近，那么查询路径碰到发布路径的速度就越快。也就是说，查询消息会被转发到最近的服务器上。

2.5.3 节点加入和退出

Tapestry的节点加入算法和Pastry类似。节点N在加入Tapestry网络之前，也需要知道一个已经在网络中的节点G。然后N通过G发出路由自己的节点ID的请求，根据经过的节点的对应的邻居节点表构造自己的邻居节点表。构造过程中还需要进行一些优化工作。构造完自己的数据结构后，节点N将通知网络中的其他节点自己已经加入网络。通知只针对在N的邻居映射表中的主邻居节点和二级邻居节点进行。

Tapestry采用两种机制处理节点的退出。一种情况是节点从网络中自行消失（主要原因是节点失效），在这种情况下，它的邻居可以检测到它已经退出网络并可以相应的调整路由表。另一种机制是节点在退出系统之前通过后向指针通过所有把它作为邻居的节点，这些节点会相应调整路由表并通知对象服务器该节点已经退出网络。检测正常操作过程中的链路和服务器失效，可以使用TCP连接超时机制。除此之外，每个Tapestry节点都使用后向指针周期性的发送“心跳”(heartbeats)UDP分组给把自己加入邻居映射表的节点。每个节点都可以根据自己收到的心跳分组来决定自己的邻居映射表中是否有节点失效。在邻居节点表中，除了主邻居节点（最近的邻居）之外，每个路由项还保存了两个备份的邻居节点，当检测到主邻居节点失效后，邻居节点表将顺序选择备份邻居节点。

１９

中国科学技术大学硕士学位论文 第2章 DHT基本原理

2.6 本章小结

目前，P2P文件共享系统已经成为Internet上最为流行的应用之一，也是Internet上业务流量的一个重要来源。因而，这些系统是否具有可扩展性是一个很重要的衡量指标，但很遗憾的是，目前流行的P2P系统在最初设计时都没有考虑到可扩展问题。例如Napster引入了集中式的目录服务器，而Gnutella又使用了泛洪式的搜索机制。

为了解决大规模P2P系统中可扩展的数据检索问题，国际上几个研究小组独立地提出了CAN，Pastry，Tapestry和Chord等新一代可扩展的结构化P2P系统，它们都支持分布式哈希表查找功能。本章对这几个系统分别进行了概要的介绍，从介绍中可以看出，它们具有相似的功能：即都把文件索引和关键字（关键字通过哈希文件名获得）绑定在一起，系统中的每个节点负责存储特定范围内的关键字。给定一个关键字，系统可以找到存储该关键字的节点，进而利用取得的索引信息定位到真正存储有目标文件的节点。表2.1给出了几种系统的比较，从表中可以看出，它们具有基本类似的性能。

表2.1 各种DHT系统对比 DHT系统 Chord Pastry d维CAN Tapestry

基于分布式哈希表的路由机制最大的的问题在于：经过哈希之后，节点的位置信息被破坏了，来自同一个子网的节点很可能在重叠网络上相距甚远，这不利于查询性能的优化。Sylvia Ratnasamy 等人在总结现有的DHT路由算法的基础之上【27】提出了结构化对等网络面临着十五个主要问题，其中指出提高DHT路由效率是基于DHT的P2P研究的重点，而P2P路由性能直接影响P2P应用的推广。

邻居数目 logN (b?1)logbN 2d 查询开销 logN logbN 12dN1d虚平面网络拓扑 环形ring 环形ring d维超立方体 环形ring logN logN ２０

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

第3章 利用拓扑信息改进DHT

3.1 引言

DHT目前还不完善，最大的问题在于DHT系统在初始设计时忽略了参与节点在物理网络上的邻近性，导致重叠网络和物理网络脱节，即未能充分利用底层物理网络的拓扑信息，从而造成实际寻路效率低下。

目前的大部分DHT系统中，关键字的查找请求都能够在O(log N)的逻辑跳数内得到满足，其中N是系统中节点个数。但是，这个跳数只是重叠网络上的逻辑跳数，而每一逻辑跳在实际物理网络上可能跨越了多个自治域，甚至是跨越多个国家。DHT根据节点标识符来组织重叠网络，而标识符一般都是通过哈希节点的IP地址产生的，这就使得节点在物理网络上的位置信息遭到破坏，重叠网络上的逻辑相邻节点在实际物理网络上可能相距甚远。例如，来自同一个子网的站点很可能节点号相差很大，而节点号临近的节点则可能分布在世界不同地区的网络中，这样势必导致查找过程的实际时延较大。

对上面的问题，可以分两步考虑来解决：第一，找到提取物理网络的拓扑信息的方法；第二，利用获得的位置信息来构造拓扑敏感（topology-aware）的DHT系统。与其它DHT系统相比，Chord系统尤为简单直观，而且Chord算法的路由逻辑跳数和网络直径优于CAN，节点加入过程和维护开销优于Tapestry和Pastry。但Chord也没有考虑和实际物理网络映射，寻路效率较为低下。本章提出的对DHT的三种改进方案都将用Chord作为示例来说明，这些方案只需做很少的修改可以应用到其他其它DHT系统中。

3.2 获取位置信息

为了获取节点在物理网络上的位置信息，可以从两个角度着手：通过分布式的网络测量技术确定相互之间链路时延较小的邻近节点，或者通过网络层IP地址蕴涵的信息确定处于同一个自治域内的节点。为了讨论问题的方便，下文中提到的“域”是指物理网络上一组临近节点所具有的共同位置信息。位于同一个域内的节点，是指这组节点具有相同的位置信息，例如拥有相同的界标序列（3.2.1节中介绍），或相同的IP地址前缀（3.2.2节中介绍）。

3.2.1 分布式网络测量技术

文献【31】中给出了一种称为“装箱子”（binning）的分布式网络测量方法，让各个节点独立地把自己划分到某个箱子（bin）当中，使处于同一个箱子中的节点之间的网络距离比不同箱子中的节点之间的网络距离相对要小。

这种装箱子机制要求Internent上存在w个分散的机器L1、L2、… Lw充当界标站点，每个节点都测量它到这w个界标站点的RTT，并按照RTT递增的顺序排列这w个界标，这个界标序列就代表了节点所属的箱子，可以看作是这个箱子的标识。这是因为物理网络上相近的节点将具有相同的界标序列，因而相应地会划分到同一个箱子中。

还可以更精细一点，对RTT值的可能范围进行分级，例如规定RTT值在[0, 100]毫秒之间对应0级，在[100, 200]毫秒之间对应1级，RTT值大于200毫秒则对应2级。这样节点不仅按照RTT递增的顺序排列w个界标，还附上这些RTT的等级，从而加大了箱子划分的

２１

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

精度。图3.1给出了这种机制的一个示例，节点A到界标站点L1、L2和 L3的RTT值分别是232ms、51ms和117ms，因而A所属的箱子标识可以表示为“L2L3L1：012”。

图3.1 “binning”机制示意

3.2.2 IP地址蕴涵拓扑信息

由于IPv4地址的分配早期缺乏规划，以及按A、B、C三类地址分类的局限性，这使得实际物理拓扑不能依据网络前缀进行聚集。正是由于这种不匹配性，骨干网上的路由条目膨胀得很厉害，十年的时间就增长了十倍，目前已经达到数百万条，这给路由器以及路由信息更新带来了很大的压力。这也是目前的解决方案都没有讨论从网络层角度进行考虑的原因。但在IPv6最初设计时【32,33,34】，就已经考虑到通过设计层次化地址结构和层次化的地址分配来做到路由聚集。从IPv6核心路由器中的条目仅为800条就可以看出这种地址分配方案的有效性。

APNIC2001:c00::/23Cernet22001:da8::/32Japan NIST2001:da0::/32USTCNNC2001:da8:b2001:da8:a3::/480::/48

图3.2 Internet结构和IPv6地址分配的对应

图3.2给出了Internet层次化结构和IPv6地址层次化分配的对应。从图中可以看到，IPv6网络前缀的分配体现了很强的层次性。由此可见，特定相同前缀长度的节点都处于相同的自

治域内（比如，/48位前缀代表了一个自治域，具有相同此前缀的主机都处于此自治域中）。

２２

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

3.3具有层次化标识符的DHT

为了改善DHT的路由性能，解决重叠网络和物理网络脱节的问题，本节提出了一种具有层次化节点标识符的DHT构建方案。出发点是使处于相同自治域内或互为近邻的节点在重叠网络中也能够彼此邻近。我们利用3.2.2节中提出的从IPv6地址中获取节点位置信息的思路，对Chord进行了改造，构建了一种应用于IPv6环境下的具有层次化标识符的DHT系统，称为Chord6 (Chord in IPv6)。

3.3.1 Chord6的设计

IPv6的IP地址分成表示特定网络的网络前缀和表示主机或服务器的主机地址二部分。如图3.3所示，在128位中高64比特表示网络前缀，低64比特表示主机。

网络部分FP(3比特)主机部分TLA_ID(13比特)RES(8比特)NLA_ID(24比特)SLA_ID(16比特)接口ID(64比特)8192个网络每个TLA有1667万7216个网络每个NLA有6万5536个网络每个SLA64有2 终端IX骨干网ISP地区或中小ISPE51B:6B00::/24的地址块E51B:6B37:ACAC::/48的地址块E51B:6B37:ACAC:1331::/64的地址块. . . . .. . . . .. . . . .细分细分细分IX：Internet互连点RES：reserved for future useFP: format prefixNLA:next-level aggregation1个1个的TLA: top-level aggregationIP地址SLA:site-level aggregation

图3.3 IPv6层次化结构以及层次化分配

在最初的前缀设计中【34】，就考虑了将网络前缀分成多个层次的网络，包括13比特的顶级聚类标识符TLA(top-level aggregation)-ID，24比特的次级聚类标识符NLA(next-level aggregation)-ID和16比特的网点级聚类标识符SLA(site-level aggregation)-ID1。首先，由管理IPv6的组织将某一确定的TLA值分配给某个骨干网的ISP。它拥有104比特这样巨大的地址块。骨干网的ISP再将地址块细分，分配给各个地区/中小ISP。用户从地区/中小ISP分到地址块。

由此可见，在IPv6中，同一自治域内的主机通常具有一定长度的相同的网络前缀，这启发我们从IPv6地址所特有的和网络适配的层次化格式出发，构造具有和地理网络充分耦 1

2003年8月，IETF机构提出的RFC3587更新了全局单播地址的格式，使得网络前缀的分配更具灵活性，并且依然强调层次性的格式以及分配。

２３

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

合的层次化节点标识符的机制，从而达到在逻辑上邻近的节点在地理上亦处于低时延的自治域内的目的。

在本节中，域是指拥有特定IPv6前缀长度的子网集合。提高P2P系统寻路效率，关键是减少传输时延，因此最为有效的方案是从实际的传输时延上入手，实现寻路的本地性的，从而减少跨域的消息量。

在Chord中，节点的标识符通过哈希节点的IP地址获得，而哈希函数的随机性使得物理上邻近的节点在逻辑空间上相隔甚远。为此我们希望IPv6地址的聚类性特点能够反映到逻辑标识符空间中。主要思想就是将IPv6地址分成两部份，通过分别哈希IP地址的前缀和剩余部分来分段构建节点的标识符，这样一来，具有相同前缀部分的节点也被映射到邻近的逻辑空间中，实现逻辑空间和物理拓扑的有效吻合。

针对具体的应用，域的大小可以通过选取的IPv6前缀长度来权衡设定，比如可以用32比特来代表大型ISP，或者48比特代表城域网规模。Chord中标识符空间大小为2

160

，那么

可以用m比特位来标识域，而用剩下的160-m比特位来标识域内的主机。根据IPv6地址的唯一性以及哈希函数的性质，可以保证节点标识符的唯一性。

000111001111000001110010110010101100011101100011

图3.4 (a) Chord 图3.4 (b) Chord6

图3.4给出了节点在逻辑空间分布的例子2。为简单计，所有节点仅分布于两个不同的域中，即所有用黑色填充的主机位于同一个自治域内，而所有未经填充的主机处于另一个自治域中。图3.4 (a)中可以看到，Chord环上逻辑邻居节点通常并不处于同一个域中，而图3.4 (b)中，由于节点标识符的首位是哈希IPv6前缀得到的，因而相同域中的节点标识首位相同。可以看到同一个域内的节点在Chord6中被很好的聚类在一起。

从理论上来看，Chord中平均逻辑跳数为O (log N)，其中N为当前系统中节点个数。从后面的仿真可以看到，在实际物理网络中其中的每一跳都是跨域的。若忽略自治域内的传输时延，Chord6的平均逻辑跳数应为O (log M)，其中M为当前系统中域的个数。这说明Chord6中的时延大小只和域的数量有关，而和系统的节点数目无关，图3.7给出的仿真结果也证实了这一点。

2

简单以及图示直观起见，例子中key空间的大小为23。

２４

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

3.3.2 分析与仿真

仿真实验使用了BRITE【35】网络结构生成器。BRITE生成的网络结构与实际网络结构相似。仿真利用两层拓扑结构。拓扑结构生成的方法是自底向上的。路由结构使用Waxman模式，设定标识符空间为2大小。

表3.1 不同网络链路的时延 链路类型 局域网（LAN） 城域网（MAN） 中美海底光缆 同步卫星链路往返时延

在实际Internet网络中，域内的时延总是远远小于域间时延。通常的链路时延见表3.1。因此在仿真中，我们假定域内每逻辑跳对应的实际时延开销为10ms，而域间每逻辑跳对应的实际时延开销为100ms是比较合理的估计。 3.3.2.1 应用层消息跳数

我们用BRITE生成节点个数为4096、包含100个域的两层网络拓扑结构。首先比较Chord和Chord6在逻辑空间中寻路跳数的概率密度函数（probability density function，PDF）。实验过程中，随机的生成10000个查询关键字的请求，发起查询的节点也随机的从4096个节点中选取。

Chord6 Chord32

估计链路时延 1～10ms 10～100ms 约100ms量级（86km/3^8m） 约540ms 0.250.200.15PDF0.100.050.00024681012Hops

图3.5 逻辑层的跳数概率分布

图3.5给出了实验结果，从图中我们可以看到Chord6和Chord的每个消息的平均跳数基本上一致，产生这种结果的原因在于我们只是修改了节点标识符的生成方式，而保留了

２５

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

Chord节点加入、退出以及寻路等基本机制。从图中还可以看到，大部分消息的平均跳数在6到7跳之间，这和Chord文献中给出的平均消息跳数为1/2Log(N)的实验结果保持一致。 3.3.2.2 端到端时延

3.3.2.1节给出的逻辑跳数仅仅反映了查询过程涉及到的平均节点数，并不能反映实际的查询路径长度。查询过程的平均端到端路由时延（end-to-end latency）才是衡量P2P系统实际寻路性能的重要参数。为此，我们首先测量在系统节点总个数保持为4096，而域的个数从1逐渐增加到4096时的端到端的路由时延。

7006005004096 nodesLatency (ms)40030020010001248163264128256512102420484096 Chord6 ChordNumber of domains

图3.6 域从1到4096时的端到端时延

从图3.6的实验结果可以看到，在域的个数大于Chord的平均逻辑跳数7的情况下（见图3.5），Chord的查询过程平均时延高达700ms，这相当于逻辑层上的每一跳都是跨域进行的。对于Chord6而言，仅在两种情况下它的寻路性能才会退化到和Chord一样。这两种情况是图中曲线的两端，左端对应所有节点处于同一个域中的情况，而右端对应每个域中恰好有一个节点的情况。这两种极端情况在实际网络中不太可能出现，也没有太大的意义。图中其它情况下路由过程的平均时延和域的个数成比例关系，域越少则跨域的消息数越少，由此减少了寻路时延。

此外，我们还对节点个数从64递增到4096，而域的个数保持为64情景进行了仿真。图3.7为仿真结果。从图中我们可以清晰的看到Chord中的端到端路由时延随着节点个数的增加而成对数增加的（横坐标是以2为底的对数）。而Chord6的曲线则保持在一条近似水平的直线上，这说明Chord6系统的时延只和系统中域的个数有关，基本上和系统中节点个数无关。

２６

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

70065060064 domainsLatency (ms)55050045040035064128256512102420484096 Chord6 ChordNumber of nodes

图3.7 节点个数从64增长到4096的端到端时延

3.3.3 小结和进一步讨论

本节从IPv6地址的层次分配所体现出的网络聚类特性出发，创造性地提出了分段构造节点标识符的思想：将节点标识符分成两部份，分别通过哈希IP地址的前缀和剩余部分来获得，这样一来，具有相同标识符前缀的节点也被映射到邻近的逻辑空间中，从而实现了逻辑网络和物理网络的有效吻合。我们对Chord协议只是做了很小的修改，设计了一个比较巧妙的改进系统－Chord6。从分析和仿真的结果可以看出Chord6的寻路性能较Chord有了显著的改善。

本节中，我们将Chord6的节点标识分成两部分来构造，这只是作者的选择。实际上分段构造节点标识符的方法并不限于两级，完全可以推广到多级的情况，以便实现逻辑空间和物理网络更精确的匹配。从图3.3中我们也可以看到IPv6地址本身就分成了多个层次：顶级聚类标识符TLA-ID，次级聚类标识符NLA-ID、网点级聚类标识符SLA-ID和接口ID。因此，节点标识符也可相应地分四段构造，分别是TLA-ID、NLA-ID、SLA-ID和接口ID的哈希值。毫无疑问这样做的结果是使得逻辑网络和物理网络更加匹配，能进一步提高Chord6的寻路效率，只是效率提高的幅度取决于实际IPv6网络中各个层次的时延情况。

还应当指出，构造层次化标识符的方法并非一定要使用IPv6，完全可以通过其他方法获得节点的位置信息，再对这个位置信息进行哈希作为节点标识符的前缀，由于同一个域中的节点具有共同的位置信息，因而它们也会在重叠网络上聚集到一起，互为邻居节点。另外，因为CAN、Pastry和Tapestry中的节点同样被赋予了节点标识符，那么本方案只要稍加修改也就应当可以应用到这些系统当中。这也是作者下一步要做的工作。

本节提出的构建层次化节点标识符的方案，仅仅是修改节点标识符的生成方式，对原有DHT的协议的改动较小，这是该方案一个显著的优点。但是这个方案可能会带来负载不均衡问题。这是因为：哈希函数的随机性使得关键字是均匀分布在Chord环上的，把IPv6地址前缀的哈希值作为节点标识符的前缀，将导致关键字在所有的自治域之间均匀分配，然而各个自治域内所含的节点数目是不同的。这就意味着Chord6不再像Chord那样，关键字在各个节点之间是均匀分配的了。为了解决这个问题，我们在3.4节提出了另一种方案，它可以取得和Chord6基本相同的改善效果，同时还可以避免这个负载不均衡的问题。

２７

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

3.4 内嵌式DHT

为了解决3.3节提出的构造层次化标识符方案可能会带来的负载不均衡问题，作者进一步提出了另一种改进方案－内嵌式DHT。

内嵌式DHT的基本思想是将节点的位置信息也抽象成一个（K, V）对存储到DHT网络中，位置关键字K是节点位置信息的哈希值，V则是节点的标识符和IP地址。按照3.2小节中介绍的提取节点位置信息的方法，处于同一个域中的节点将具有相同的位置关键字K。节点在加入网络时，除了加入全局DHT系统，还注册并查询与自身位置关键字K相关的（K, V）对，从而获得一个临近节点列表，再加入由这些临近的节点组成的本地DHT。

总的看来，整个系统是由许多本地DHT内嵌在一个全局的DHT系统之中，路由可以先在本地DHT中进行，必要时经由全局DHT，从而避免多次跨域路由。这种将节点的自身的位置信息也存储到DHT系统中并利用DHT系统本身来定位临近节点列表信息的聚集策略不依赖集中式服务器，具有完全分布式的特点。下面仍然用Chord作为示例，介绍利用此策略对DHT系统进行减少寻路时延的改造工作。为方便计，下面把构建的新系统称为eChord (embedded Chord)。

3.4.1 eChord的设计

首先，我们来考察一种简单的情况。图3.8中所有节点分别位于两个不同的域中，即所有用黑色填充的主机位于同一个域内，而所有未经填充的主机处于另一个域内。正如本章开始指出，在这些节点共同组建的Chord环（图中用粗线连成的圆环表示）上的逻辑相邻节点并不总属于同一个域，因而一个查询报文的路由过程可能会多次进出同一个域，这显然是低效的。为此我们提出在同一个域内的节点之间构建一个内嵌的本地Chord环。例如，图3.8中处于同一个域内的N8、N21、N38、N48和N51组建一个内嵌的本地Chord环（图中用连在一起的弧线表示），而同处于另一个域内的N1、N14、N32、N42和N56组成另一个内嵌的本地Chord环（图中用连在一起的弧线表示）。另外，所有的节点仍然共同组建一个全局Chord环，我们把整个系统称为eChord。

N1N56N8N51N14N48N21N42N38N32

图3.8 eChord示意

２８

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

为了既能在全局Chord中路由又能在自己所属的本地Chord中路由，eChord中每个节点都必须维护两个路由表，分别称为本地指针表localFinger和全局指针表globalFinger。相应地，其中的表项分别称为本地指针和全局指针，而节点在本地Chord环和全局Chord环上的后继节点也分别称为本地后继节点lsuccessor和全局后继gsuccessor。规定localFinger表是节点在本地Chord环上按照标准的Chord协议构建的表项；而globalFinger表是节点在全局的Chord环上维护的一部分指针表项，即从节点本身到它的lsuccessor之间这段弧上的指针表。节点n的globalFinger表中第i项是全局Chord圆环上标识大于或等于n+2i-1的第一个节点（比较是以2为模进行的）。而且要求n.globalFinger[i]≤lsuccessor，1≤i≤m。假设系统中共有N个节点均匀分布在M个域中，则localFinger表中含有O (log N/M)个表项，而globalFinger表中含有O（log M）个表项。例如图3.8中节点N8的本地后继节点lsuccessor是N21，所以它的globalFinger表只有一项，即globalFinger[0]=N14，这个N14也是节点N8的全局后继节点gsuccessor。本地Chord环和本地指针表仅仅是为了优化查询的路由过程，文件关键字仍然是按照全局Chord环分布存储到系统中，这也正是eChord并不像Chord6那样引入负载不平衡问题的原因所在。

m

3.4.2 eChord的路由

eChord的查询过程是：任何一个节点收到查询关键字K的请求时，首先检查关K是否落在该节点标识和它的全局后继节点标识之间，如果是的话，这个全局后继节点就是存储目标(K, V)对的节点。否则，节点在检查K是否落在该节点标识和它的本地后继节点标识之间，如果是的话，节点将查找它的全局指针表，找到表中节点标识符最大但不超过K的第一个节点，并将这个查询请求转发给该节点。否则，如果K大于本地后继节点标识，节点将查找它的本地指针表，找到表中节点标识符最大但不超过K的第一个节点，并将这个查询请求转发给该节点。通过重复这个过程，最终可以定位到K的全局后继节点，即存储有目标(K, V)对的节点。表3.2给出了寻路过程的伪代码。

表3.2 eChord中的寻路算法

相关说明

n: 发起查询的节点。

key: 被查询的关键字标识符。

n.gsuccessor: 在globalFinger中的后继节点。 n.hashid: 节点n的标识符。

n.lsuccessor: 在localFinger中的后继节点。

lookup_in_globalFinger()：在globalFinger中，按照标准Chord算法查找靠近节点。 lookup_in_localFinger ()：在localFinger中，按照标准Chord算法查找靠近节点。 寻路算法: route(n, key)

if(key == n.hashid) else

if (key > n.hashid && n.lsuccessor > key)

２９

return n;

return n.gsuccessor;

if (key > n.hashid && n.gsuccessor > key)

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

n_1 = lookup_in_globalFinger(n, key); return route(n_1,key);

n_2 = lookup_in_localFinger(n, key);

return route(n_2,key);

else

//在globalFinger表中查找 lookup_in_globalFinger(n, key)

for i=m downto 1

if (n.globalFinger[i]∈(n,key)) return n.globalFinger[i]; return n;

//在localFinger表中查找 lookup_in_localFinger(n, key)

for i=m downto 1

if (n.localFinger [i]∈(n,key)) return n.localFinger [i]; return n;

比较eChord和原始Chord的寻路过程，可以看出eChord的寻路过程具有本地性，也即每次路由都尽量发生在节点所处的域内，只有在找不到的情况下才经由通过全局Chord环跳转到其它的域。

3.4.3 节点的加入和退出

节点n加入对等网络之前，首先通过哈希界标序列或IP地址前缀计算出自己的位置关键字K。然后节点n通过已知的引导节点加入到全局Chord中，同时将自身的位置关键字K存储到系统中。最后节点n通过eChord查询与K相关的所有（K，V）对，V是当前系统中和自己处于相同域中的所有节点IP地址的集合。若此集合不为空，节点n从该集合中随机选择一个节点作为引导节点加入到本地Chord中。

节点的离开相对来说要简单些，除了执行普通的Chord中节点离开时的操作外，还在eChord中删除自己的位置信息（K，V）对。

3.4.4 分析与仿真

和3.3节的仿真类似，实验仍然使用BRITE仿真器生成的两层拓扑结构，每个域由具

32

有相同IPv6网络前缀的节点构成，设定标识符空间为2大小。

首先我们比较Chord和eChord在逻辑空间中寻路跳数的概率密度函数（probability density function，PDF）。仿真实验使用BRITE生成节点个数为4096、包含100个域的网络拓扑结构。随机的生成10000个查询关键字的请求，发起查询的节点也随机的从4096个节点中选取。

３０

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

0.25ChordeChord0.200.15PDF0.100.050.00024681012Hops

图3.9 逻辑层的跳数概率分布

图3.9给出了实验结果，从图中我们可以看到eChord和Chord的每个消息的平均跳数基本上一致，产生这种结果的原因在于eChord的本地指针表和全局指针表的大小之和O (log N/M) + O (log M) = O (log N), 这和Chord中的指针表尺寸是相同的。

同样，我们接着仿真了平均消息跳数的端到端时延（end-to-end latency），仍然假定域内跳数开销为10ms，而域间跳数开销为100ms。

7004096 Nodes600500Latency(ms)400300200100ChordeChord01248163264128256512102420484096Number of AS

图3.10 域从1到4096时的寻路时延对比

图3.10给出了总节点个数为4096，随着自治域的增长，寻路时延的变化规律。从中可以看到，当域的个数大于8后，Chord的寻路时延高于600ms，而从图3.9中我们知道Chord的平均逻辑跳数为6跳，这说明逻辑跳数中的每一条都经历了跨域路由的过程，这个结论和3.3.2.2节中给出的结果吻合。而eChord中寻路时延和Log2M的成线性增长的关系，其中M为域的个数，只有当系统中节点前缀两两不一样时，eChord的寻路效率才退化到Chord中的情况。

３１

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

8700650600550500163264128256512102420484096 Chord AS=2 eChord AS=2 Chord AS=64 eChord AS=64Latency(ms)4504003503002502001501008163264128256512102420484096Number of Nodes

图3.11 节点个数增大的情况下寻路时延对比

图3.11给出了在域的大小固定，而系统中总节点个数增长时的寻路时延的比较。从中我们可以看到Chord的寻路时延和Log2N成线性增长的关系，其中N为节点个数。在相同的自治域的情况下，eChord中的寻路时延也和节点总个数无关，而只和域的个数有关。

3.4.5 小结和进一步讨论

本节提出了构建内嵌式DHT的方案：节点把自身位置信息存储到全局DHT系统中，新加入的节点通过DHT找到和自己处于相同域内的节点集合，从而加入由这些临近的节点组成的本地DHT中。整个系统由许多本地DHT内嵌在一个全局的DHT系统之中，路由可以先在本地DHT中进行，必要时经由全局DHT，从而避免多次跨域路由。本节也给出了针对Chord的改造实例eChord，分析和仿真都证明了eChord可以有效地改善Chord的寻路性能。

和3.3节提出的Chord6相比，eChord保持了原有Chord的负载均衡特性，而不像Chord6那样会引入负载不均衡问题。然而，从实现的复杂程度来看，Chord6更为简单，仅仅修改了节点标识符的生成方式，而对Chord协议几乎未作任何修改。从对Chord寻路效率的改善性能来看，eChord和Chord6取得了几乎相同的效果。这是因为虽然eChord和Chord6采用的技术方案不同，但他们的出发点都是一样的，即都从减少跨域的消息量上入手，实现寻路的本地性。

总的说来，Chord6和eChord各有优缺点。考虑到在Internet这样一个广域范围上，参与节点在各个域中的分布出现显著差异的可能性不大，因此Chord6由于实现简单在应用上具有一定的优势。从第4章可以看到，我们提出的IPv6环境下的大规模文件共享系统就是选用Chord6来构建核心重叠网络的。

３２

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

3.5层次化DHT

我们注意到DHT系统不仅存在重叠网络和物理网络脱节的问题，而且还把所有的查询请求都当作整体查询（找到与给定K相关的所有(K, V)对）来对待，这是因为关联特定K的全部(K, V)对都存储于网络中的某一个节点上。但是，如果DHT像非结构化P2P那样支持部分查询，即用户往往满足于找到网络中与特定K相关的少部分索引，那么由于物理网络上的邻近节点就可能拥有满足要求的文件，就可以避免在全网上路由查询报文从而降低开销。因此本节在Chord的基础上提出了一种层次化分布式哈希表系统hChord (hierachical Chord)，它不仅改善了Chord的路由性能，而且还支持部分查询。从下文可以看到，层次化DHT和上节提出的内嵌式DHT主要的不同在于：层次化DHT改变了关键字在网络中的分布情况。

3.5.1 hChord的设计

在介绍hChord的设计之前，我们先看看在2.2.2节介绍的一个Chord查询实例。为了方便，在图3.12中重新绘出了一个查找过程的示例。节点8查找关键字54过程是：节点8首先按照路由算法把查询请求转发给它的指针表中的节点42。同理节点42也按规则把请求转发给节点51，节点51发现54落在它和它的后继节点标识56之间，因而就把节点56的标识和IP地址等信息返回给节点8。这个查找过程结束后，节点8就可以根据得到的IP地址等信息直接到节点56上存取与关键字54相关的(K, V)对。

图3.12 Chord扩展查询示例

从例子中我们可以看到Chord的缺陷：节点N8查询K54时虽然只经过了3跳，但这正如前面指出的，是应用层跳数而不是网络层跳数，例如发起节点N8和目的节点N56可能位于Cernet的同一网段内，而中间节点N42和N51却可能是分别位于欧洲和美国的两台主机。显然，源节点和目的节点处于同一个网段而查询报文却要在广域范围内路由是不合理的；另外，可能有许多与K54相关联的文件散布于网络的各个局部，即有很多关键字标识为54的(K, V)对。但Chord中这些(K, V)对全部存储于节点N56上，若有大量用户提出针对K54的部分查询请求，即只需找到部分而不是所有的(K, V)对，这些请求仍然被当作整体查询路由到N56。显然，这样做的后果是增加了网络的开销并可能导致N56负载过重。

３３

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

针对Chord的不足，本节提出了hChord。其思想是：把P2P网络中的节点划分为多个组，保证组内节点之间的时延较小。如图3.13所示，在各个组内构造内层DHT(internal DHT: iDHT)，赋予每个节点一个m比特标识n_id，然后在所有组之间构造一个外层DHT（external DHT：eDHT），并赋予每个组一个m比特标识g_id。则网络中的节点可唯一地由g_id.n_id标识。相应地每个关键字是一个2m比特的数值，仍记为K或KhKl。它的高位m比特Kh和低位m比特Kl是通过对文件名或关键字进行两次（不同的）哈希运算产生的。图3.13中的iDHT是根据n_id和Kl组织的Chord，eDHT则是根据g_id和Kh组织的Chord。hChord并不寻求重叠网络和物理网络严格匹配，而是采取把iDHT的覆盖范围控制在一个合适的局部物理网络上，从而有效地降低每逻辑hop所对应的平均物理时延(delay per hop: DPH)。区域划分的可以利用3.2节介绍的方法。

BiDHTACDiDHTEeDHTJiDHTHIFKLG

图3.13 hChord

hChord中(K, V)的插入过程：设(k, v)是节点g1.n1要向系统中插入的一个(K, V)对，k又表示为khkl。这个(k, v)需要插入两次：先在节点所属组g1内根据kl路由到负责kl的节点g1.n2插入一次；再根据 eDHT路由到负责kh的组g2，并在g2中路由到该组负责kl的节点g2.n3插入第二次。从这个过程可以看出，每个关键字都分两次存放到系统中，从而改变了关键字在原来Chord中的分布。这是hChord和eChord的不同所在，也是层次化DHT能支持部分查询的根本原因。

hChord中(K, V)的获取过程：对于整体查询请求，节点先根据eDHT把查询报文路由到负责给定Kh的组，在该组中查找负责Kl的节点。对于部分查询请求，节点先在所属组内查找负责Kl的节点，如果找到满足要求的(K, V)对，则本次查询结束；否则象整体查询那样在eDHT上把查询报文往负责Kh的组路由，期间每经过一个组都要先路由到该组内负责相应Kl的节点，若找到满足要求的(K, V)对，则查询结束，否则由该节点把查询报文转发给后面的组直到取得要求的(K, V)对或者到达负责Kh的组中负责Kl的节点。下面详细给出hChord的操作过程。

3.5.1.1 hChord的查询过程

与Chord相比，为了能在组间和组内寻路，节点需要维护组间路由表fingerG和组内路

３４

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

由表fingerN，他们分别对应于eDHT和iDHT中的finger表。fingerG表和Chord中的finger表不同在于每个表项中维护了相应组中的b个代表节点。表3.3 (a)和3.3 (b)给出了fingerG和fingerN表的示例。gh表示标识为h的组，而h.n1则表示标识为h的组中节点标识为n1的节点。

predecessorG successorG fingerG[k] gh gm h.n1 h.n2 …h.ni… h.nb-1 m.nb-1 h.nb m.nb predecessorN successorN fingerN[k] i.np i.ns i.nk m.n1 m.n2 …m.ni… 属于相应组的b个节点 表3.3(a) 组gi中某节点的fingerG表 表3.3(b) 组gi中某节点的fingerN表

表3.4给出了hChord中整体查询算法的描述。符号(a,b]表示在（组或节点）标识圆环上从a（不包括a）顺时针移动到b(包括b)所获得的标识子空间。hChord的部分查询算法比较简单，只需在路由经过的每个组中都查找该组内负责相应Kl的节点，一旦找到满足要求的的(K, V)对，则查询提前结束。 3.5.1.2 组的加入

假定新加入节点gj.nj已经知道P2P网络中的一个（或多个）引导节点。获得引导节点的方法有很多，例如YOID【36】中就给出了一种机制。本节仅利用已有的方法，并不讨论这方面的内容。如果组gj已经存在于eDHT之中，那么节点gj.nj的加入请求通过eDHT路由到组gj中任何一个节点后，加入的过程同chord基本类似。本文仅讨论组gj需要创建的情况。

为了使组加入的过程平稳，每个节点还需要维护candidate_successorG表。该表维护数个候选组，用来保存那些可能组成新的后继组的节点。gj.nj从引导节点中取得fingerG表后，按eDHT把“组gj要求加入”的报文路由到合适的组gi（gj∈(gi,gm]，其中gm是组gi的后继组），在组gi中广播通知“有节点gj.nj要求加入系统”，gi中所有的节点在自己的candidate_successorG表中的组gj中（若没有gj，则创建该条目）增加nj。然后检查gj中节点数目，若小于b则不把组gj引入到eDHT中，可能属于组gj的节点暂时仅具有提出查询功能，不负责存储(K, V)对。否则若节点数目为b个，组gi中所有节点独立检查自己是否存储kl=gj的(K, V)对，若是则测试所有b个gj中的节点，若均为活动节点，则通知b个节点构建iDHT并初始化其fingerG表：predecessorG=gi，successorG=gi.successorG。并在组gm中广播“新前驱组gj加入”报文，该组所有收到此报文的节点将自己fingerG表中的predecessorG从gi改为gj，然后由gm

//根据fingerG表查找 g.n.find_successorG(khkl){ if (kh∈((predecessorG,g]) return g.n.find_successorN(kl); elseif (kh∈((g,successorR]) 从successorG中随机选择一个节点ni; return successorG.ni.find_successorN(kl); else g’= g.n.closest_preceding_group(kh); 从g’中随机选择一个节点ni; return g’.ni.find_successorG(khkl); } //根据fingerN表查找 g.n.find_successorN(kl){ if(kl∈(n,successorN]) return successorN; else n’= g.n.closest_preceding_node(kl); return g.n’.find_successorN(kl) } g.n.closest_preceding_group(kh){ for i=m downto 1 if(fingerG[i]∈(g,kh)) return fingerG[i]; return g; } g.n.closest_preceding_node(kl){ for i=m downto 1 if(fingerN[i]∈(n,kl)) return fingerN[i]; return n; } 表3.4 StratoNet整体查询算法 ３５

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

中存储kl=gj的(K, V)对的节点在组gi中广播“新后继组gj加入”报文，组gi中所有收到该报文的节点将其fingerG表中successorG用gj置换，并删除candidate_successorG表中的gj。 3.5.1.3 组的退出

Chord的正确性是建立在每个节点都知道其后继节点的基础上的。由于维护iDHT的正确性就是维护Chord的正确性，这在文献【23】中已有详细的讨论。然而在维护eDHT的正确性时，需要特殊的考虑。由第3.5.2节分析知道，上面的组创建过程可以保证，eDHT中一个组内的b个活动节点同时失效的概率很小。即便如此，本节借鉴Chord的做法仍然给出了检测组失效的机制。为此，每个节点可以额外维护紧接其所属组后的c个后继组，一旦检测到最临近的后继组失效，可以用下一个后继组来置换。这样只有当所有c个组同时失效的情况下，eDHT才被破坏。每个组失效是近似独立的（哈希函数的随机性可以保证这一点），设失效概率是p，则c个组同时失效的概率是pc。

如果组gi中某节点ni在进行查询（或插入）操作时，发现fingerG表中successorG内所有b个节点都失效，则在组gi中向所有节点广播“组successorG中是否有活动节点”的询问消息，收到此消息的节点测试其所维护的successorG中b个节点，若发现successorG中有活动节点nj且没有收到其它节点发送的应答消息，则在组gi中广播应答消息“组gj中有活动节点nj”。组gi中的任何节点在收到此报文时，若发现其successorG中有失效节点，可根据nj或其successorG中其它活动节点，进一步更新其successorG中b个节点信息。否则，各节点将组successorG从fingerG表转移到candidate_successorG表中，同时把下一个后继组作为successorG，并通知该组内所有节点将前驱组predecessorG改为组gi。

3.5.2性能评估和进一步的讨论

3.5.2.1 组创建过程中参数b的选取

P2P网络中节点的频繁加入和退出会给系统带来较大的开销，为了解决这个问题，我们在创建组时使用了一个门限参数b，使得hChord中的组的创建过程比较平稳。当某个物理网络局部仅有少数几个节点加入P2P网络时，这几个节点不组成iDHT，即不对外提供检索能力，仅具有提出查询请求的功能。一旦活动节点数目达到系统中设定的门限b并创建组后，那么属于该组的后来节点只需以很小的开销即可加入到hChord中。例如，b=1就等效于不设门限，此时组的创建和退出会比较频繁；而b=2明显就要优于不设门限的情形。可以把潜在的组看作是没有等待时延的一个排队系统。近似认为该组内节点到达（加入P2P网络）是参数为λ的泊松过程，服务时间（节点存在于P2P网络中）是参数为μ的指数分布，该系统的服务员数量是无穷个，即一个M/M/∞排队模型。由于没有等待时延，则节点在系统中的平均时延就是其平均服务时间1/μ。根据Little定理，稳态时iDHT中的平均节点数：N=λ*(1/μ)=λ/μ。使用门限参数b的目的是保证：⑴稳态时节点数N

３６

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

3.5.2.2 hChord对查询和插入操作性能的改善

查询（或插入）一个(K, V)对的平均时延是衡量一个DHT系统性能的重要指标，可以用查询路径包含的跳数乘以每跳所对应的平均物理时延(DPH)来表示。设P2P网络中具有N个节点，无论是整体查询还是部分查询Chord提供的查询性能都是O(log N)×DPH。为了问题的简化，我们假设网络中的链路都是对称的，由于哈希函数的随机均匀性，则DPH应当是P2P网络中所有可能的节点对之间时延的平均。考察Chord中逻辑邻居(a, b)，在P2P网络中这对逻辑邻居对应的实际节点对为(A, B)。而(A, B)的组合数为CN，且每种组合对应于(a, b)的概率可以认为都是均等的，为1/C2N。设(A, B)之间的时延为dAB，G为P2P网络中所有的节点集合,则有：

DPH?2

?A,B?G1CN2*dAB

很明显，因为组内剔除了长时延链路，所以iDHT内每逻辑跳对应的平均物理时延（记为DPHi，而eDHT中的DPH记为DPHe）比在整个网络上构造DHT会有显著的降低。在hChord中，假设有N个节点和M个iDHT，部分查询的性能是：O(log N/M)×DPHi；整体查询的性能是O(log N/M)×DPHi＋O(log M)×DPHe，（1

3.5.3 结语和未来工作

通过把P2P网络中节点划分为多个组，在各个组内构造iDHT并在所有组之间构造eDHT，hChord中各个节点完全对等，避免了单点瓶颈；与节点离开的概率相比，组离开的概率较小，因而系统更平稳。在部分查询时，提供了比简单DHT系统更优越的性能。进一步的工作包括寻找更有效的划分组的机制，和针对不同的应用对hChord进行仿真。

３７

中国科学技术大学硕士学位论文 第3章 利用拓扑信息改进DHT

3.6 本章小结

本章首先指出现有DHT系统存在的最大问题之一，就是重叠网络和物理网络脱节，未能很好地利用节点的位置信息，从而导致路由效率低下。接着从提取节点位置信息的角度简要介绍了一种分布式网络测量技术，同时也创造性的提出了从网络地址前缀中提取位置信息的方法。

本章重点给出了我们提出的利用拓扑信息改进DHT寻路性能的三种方案，分别是具有层次化标识符的DHT、内嵌式DHT和层次化DHT。本章通过把Chord改造成Chord6、eChord和hChord来分别阐述这几种方案的思路，并通过仿真和分析阐明了这些方案能有效地改善现有DHT的寻路效率。

在Chord6中，我们从IPv6地址的层次分配所体现出的网络聚类特性出发，创造性地提出了分段构造节点标识符的思想，使得物理网络中同一个域内的节点具有相同的标识符前缀，因而也就被映射到邻近的逻辑空间中。Chord6的设计比较巧妙，实现了逻辑空间和物理网络的有效吻合，仅对Chord协议做了很小的修改就显著地改善Chord的寻路性能。

本章提出的第二个改进方案eChord，是在全局的Chord环上嵌入许多本地Chord环，路由可以先在本地Chord环上进行，必要时经由全局Chord环，从而避免多次跨域路由。eChord不仅有效地提高了Chord的寻路效率，而且不改变原有Chord的负载平衡特性。eChord节点将自身的位置信息也存储到系统中，并利用eChord本身来定位临近节点列表信息，这种节点聚集策略具有完全分布式的特点。

我们用hChord来说明层次化DHT的构建方案。hChord采用分组的思想，不仅能改善Chord的寻路性能，而且还能像非结构化P2P那样支持部分查询。

虽然Chord6、eChord和hChord都是建立在Chord之上的，但是这些思路完全可以应用到其它结构化P2P系统中，如Pastry、CAN等。

３８

中国科学技术大学硕士学位论文 第4章 基于DHT的P2P系统设计与实现

第4章 基于DHT的P2P系统设计与实现

因为DHT具有良好的可扩展性，在节点失效、遭受攻击和突发性高负载面前都能表现出很好的健壮性，所以DHT具有广阔的应用前景。目前国际上很多著名的研究机构都在积极研究和开发基于DHT的新一代广域大规模P2P应用系统。例如，著名的PlanetLab（全球互联网实验室计划）目前正在运作的一个大项目OceanStore，就是UC Berkeley开发的基于Tapestry的大规模P2P系统，其目标是实现全球范围内持久稳定的数据分布式存储。 目前已经提出的基于DHT的P2P应用主要集中在数据和文件共享系统上，本章重点介绍我们正在开发的IPv6环境下的文件共享系统FSS6（File Sharing System In IPv6）。FSS6是中国科大信息网络实验室和中国科学院声学所共同申请的CNGI（China Next Generation Internet，中国下一代互联网示范工程）项目中《基于IPv6的P2P弹性重叠网络智能节点的研制》分项的一个原型系统。

4.1 FSS6

4.1.1 设计目标

CNGI是我国发展IPv6网络的一项重要举措，但是由于目前的Internet网还基本上都是IPv4网，IPv6上还缺少必要的应用和服务，这就影响了CNGI网络的市场推广，广大用户还不能享受到IPv6方便、快捷的服务。由于应用和用户的缺乏，也影响了对CNGI网的技术研究。宽带网发展的事实已经证明，应用服务和用户群培养是一个相辅相成的过程，但是应用服务先行将可以促使用户群的快速发展。P2P应用无疑是当前互联网上的一个热点，从P2P流量占运营商流量的70％来看，开发CNGI上的P2P应用是一个多快好省的途径。

我们实验室将要承担的CNGI项目《基于IPv6的P2P弹性重叠网络智能节点的研制》就是要为CNGI研制P2P弹性重叠网络智能节点，创造一个有利于P2P各项增值应用服务发展的平台。在项目的前期，我们先开发一个大规模的文件共享系统的原型系统，系统的核心是使用DHT技术构建的一个可管理、可控制和可运营的智能节点弹性重叠网络（Resilient Overlay）。

通过研制基于IPv6的P2P应用，可以在实践中检验我们在第3章提出的DHT改进方案，可以充分展示和运用IPv6的优越性，推动IPv6的普及发展，这必将会加速CNGI的顺利演进；同时，我们的系统还将给P2P应用探索一个可运营、可管理和可控制的示范模式，进一步推动P2P应用的良性发展，更好地满足用户需求。

4.1.2 系统结构

本人所在的P2P研究组正在设计开发的FSS6（File Sharing System In IPv6）是使用DHT技术和IPv6技术为CNGI构建的一个可扩展的大规模P2P文件共享系统，它为用户提供高性能的分布式数据检索服务。

如图4.1所示，整个系统中的节点分为智能节点（Intelligent Node，IN）和客户节点（Client Node，CN）两种类型。客户节点就是网络中的普通用户终端，而智能节点则由运营商提供和维护。与客户节点相比，智能节点较为稳定强大。在FSS6中，智能节点使用我们在第三章提出的Chord6自组织成一个核心的弹性重叠网络，用来存储和查找文件索引，向客户节点提供高性能的分布式数据检索服务，因而每个智能节具有一个与底层IPv6网络适配的层

３９

中国科学技术大学硕士学位论文 第4章 基于DHT的P2P系统设计与实现

次化节点标识符。处于外围的客户节点则是用户的个人计算机，它运行我们开发的客户节点软件，只与某个智能节点有联系。客户节点主要是通过与它有联系的智能节点向核心重叠网络中发出请求，如插入文件索引，查找文件等。换句话说，客户节点并不参与Chord6，因而也就不需要给它分配节点标识符。从系统结构可以看出，FSS6的关键是智能节点之间基于Chord6的结构化重叠网络的实现。

客户节点客户节点客户节点智能节点Chord6客户节点智能节点智能节点智能节点客户节点客户节点客户节点客户节点

图4.1 FSS6系统结构

4.1.3 Chord6实现

我们在第三章提出的Chord6和Chord相比具有优良的寻路性能，而且除了使用新的层次化节点标识符构造方法外，对Chord原有协议未作任何改动。所以，Chord6中节点加入、节点退出、指针表维护和关键字查找等算法的实现与Chord相同，并不需要特别的考虑。

Chord6需要考虑的最大问题是如何把分段构造标识符的思想具体实现并应用到FSS6中。节点的标识符应当分几个部分构造？标识符的各个部分又分别和多少位的IP地址前缀对应？这才是我们在实现Chord6时需要特别注意的问题，因为标识符的层次划分的好坏直接决定了Chord6能在多大程度上匹配底层的IPv6网络。

考虑到FSS6是CNGI上的一个大规模文件共享应用，我们首先要考察IPv6在现实中的分配原则和现状。然后我们根据现实中IPv6地址的分布情况选定FSS6中智能节点标识符的生成策略和方法。

IPv6地址管理采用等级制，而在此等级制中的最高层就是因特网地址分配机构（IANA）。IANA向地区性因特网地址注册处（RIR）或国家互联网注册机构（NIR）分配地址。目前，主要有四个RIR：亚太网络信息中心（APNIC）、北美的ARIN、欧洲的主要有网络IP欧洲网络合作中心（RIPENCC）和南美及加勒比海地区的拉丁美洲及加勒比海地区因特网地址注册处（LACNIC）。RIR或NIR向那些叫做本地因特网注册处（LIR）的组织分配地址。LIR是接受RIR或NIR委派的组织，它们向用户分配地址。通常，LIR是一个服务供应商。LIR将自己所获得的地址分配给终端用户组织或其它的ISP。为了充分实现路由优化，RIR或NIR并不直接将全局IPv6地址分配给终端用户组织。任何终端用户组织想要获得全局IPv6地址，都得由与它们保持直接连接的服务供应商进行分配。如果该用户组织变换了服务供应商，那么全局路由选择前缀也不可避免地要进行变换。图4.2给出了IP6地址分配和

４０

中国科学技术大学硕士学位论文 第4章 基于DHT的P2P系统设计与实现

管理的流程。

图4.2 IPv6地址分配和管理

截至到2005年4月7日，中国从亚太网络信息中心共获得了17个IPv6地址块（见表4.1），其中16个地址块的前缀都是32比特。

表4.1 中国获得的IPv6地址块

次序 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 IPv6地址范围 2001:250::/35 2001:3f8::/32 2001:c68::/32 2001:cc0::/32 2001:d60::/32 2001:da8::/32 2001:251::/32 2001:e08::/32 2001:e18::/32 2001:e80::/32 2001:e88::/32 2001:f38::/32 2001:dc7::/32 2001:f88::/32 2001:da9::/32 2001:daa::/32 2001:dcb::/32 IPv6前缀长度 /35 /32 /32 /32 /32 /32 /32 /32 /32 /32 /32 /32 /32 /32 /32 /32 /32 IPv6来源 apnic apnic apnic apnic apnic apnic apnic apnic apnic apnic apnic apnic apnic apnic apnic apnic apnic 分配日期 20000426 20020704 20020830 20021015 20030616 20031110 20031111 20031121 20031219 20040319 20040323 20040721 20040913 20041011 20050203 20050207 20050407

４１

中国科学技术大学硕士学位论文 第4章 基于DHT的P2P系统设计与实现

而CNNIC（China Internet Network Information Center, 中国互联网络信息中心）对IPV6地址分配的要求是：ISP或提供互联网络服务的单位从APNIC获得前缀是/32的IPv6地址块后，一般向下一级用户提供/48的地址分配。例如分配给华东北三省（江苏，安徽和山东）的IPv6学生试验床地址是3FFE:3216::/32，而中国科技大学从这个地址块中分配到的地址则是3FFE:3216:2101::/48。

从上面介绍的IPv6地址分配原则和现状中我们可以看到，IPv6网络实际上分为多层，目前中国顶级IPv6网络大多具有32位的前缀，这个网络又可细分为许多具有48位前缀的次级网络。通常48位的前缀可以定位到学校或城市级别。有鉴于此，在FSS6中我们决定用160比特的数值来表示智能节点的标识符（称为INid），而且把INid分成三个部分来构造，最高40比特（称为INid-h）是智能节点的IPv6地址前32位前缀的哈希值，中间20比特（称为INid-m）是智能节点IPv6地址前48位前缀的哈希值，剩余的100位是智能节点IPv6地址低80位的哈希值。哈希函数我们采用SHA-1。这样的节点标识符分段构造方式应当可以比较好的匹配底层的IPv6网络。图4.3示意了这种分段方法

INid-hINid-m图 4.3分段的智能节点标识符

INid-l

4.1.4 智能节点设计

图4.4是系统中智能节点的功能模块图。整个模型构建在IPv6网络层之上，从下到上依次是XML消息处理模块，Chord6模块，统一接口平台和应用层。Chord6模块又可分为调度子模块，索引处理子模块，寻路子模块，指针表维护子模块和节点操作子模块。

索引处理子模块应用层统一接口平台调度子模块寻路子模块Chord6模块指针表维护子模块XML消息处理模块图4.4 智能节点结构

节点操作子模块

XML消息处理模块一方面从网络层接收UDP封装的用XML描述的各种消息（例如查询关键字，插入关键字等），提取出其中的消息类型和相关参数，传递给上层Chord6模块。此外，XML消息处理模块还要把来自上层的各种操作要求（如节点加入、节点退出、索引查找等）形成标准的XML消息，并通过UDP发送出去。使用XML是由于它是一种规范的格式，具有很好的扩展性。

Chord6模块中的调度子模块对接收到的消息类型进行判断，然后调用相应的其他几个子模块进行处理。（表4.2给出了这几个子模块的功能和所需相关接口。）统一接口平台为上

４２

中国科学技术大学硕士学位论文 第4章 基于DHT的P2P系统设计与实现

层的应用提供统一的接口，包括索引的相关操作和节点加入退出的相关操作。应用层为用户提供一个文件共享的友好可视化用户界面。

表4.2 Chord6模块中的子模块说明

模块名 索引处理子模块 数据库 寻路子模块 处理消息在对等网络中的寻路 指针表维护子模块 维护节点的指针表信息，定时更新指针表 节点操作子模块 处理来自节点加入、退出请求 功能 维护本节点的文件索引列表提供的接口 为上层提供针对索引的搜索、插入、更新和删除请求的接口 处理寻路请求，返回下一跳地址或者关键字的后继节点地址 智能结点的加入、退出消息激发该模块功能。 给上层提供节点加入、退出等操作统一接口

我们在设计时考虑到FSS6将来的可升级性，用统一接口平台把上层应用和下层的Chord技术分割开来，使得我们以后可以视需要开发其他类型的应用。也就是说，FSS6实际上并不限于文件共享应用，将来完全可以利用统一接口平台在应用层上开发不同的增值应用服务，包括：网络电视服务，软件发布服务，数字媒体发布服务，游戏服务，拍卖服务，交友服务，电子商务应用等等。

4.1.5 消息处理

系统中的消息类型主要包括：查找关键字（Query）、删除关键字（Delete）、插入关键字（Insert）、客户节点加入（CNjoin）、客户节点离开（CNleave）、智能节点加入（INjoin）、智能节点离开（INleave）、在本地索引表中检索关键字（Lookup）。

上一跳智能节点转发过来的查找关键字的消息把查找关键字的消息转发给下一跳智能节点客户节点提交消息远过程调用智能节点接收消息转发调度子模块转发寻路子模块把索引处理子模块的查找结果返回给客户节点字本的节后点继是节关点键索引处理子模块返回下一跳节点的标识和IP地址指针表维护子模块Chord6模块客户节点智能节点 图4.5查找关键字的消息处理流程

４３

本文来源：https://www.bwwdw.com/article/q3jr.html