硕士论文-基于DHT的可扩展的流媒体系统研究.pdf

广西师范大学 硕士学位论文 基于DHT的可扩展的流媒体系统研究 姓名：吴绮 申请学位级别：硕士 专业：计算机软件与理论 指导教师：覃少华 20090501 I 基于基于 DHT 的可扩展的流媒体系统研究的可扩展的流媒体系统研究 研究生：吴绮 导师：覃少华 专业：计算机软件与理论 研究方向：计算机网络 年级：2006 级 摘要摘要 传统的网络应用模式中服务性能瓶颈以及单点失效的问题不仅限制了端系统资源的 充分利用，同时越来越无法满足新的分布式应用的需求。Peer-to-Peer(P2P)网络在协同 工作、分布式信息共享、大规模并行计算等方面显示出独特优势，使其成为新的发展热点。 对基于结构化的 Peer-to-Peer 覆盖网络的流媒体服务而言，如何构造一个可扩展的、节 点加入和退出时维护开销较小的流媒体体系是一个关键问题。在流媒体服务体系中 DHT 算 法的最大问题是 DHT 的维护机制较为复杂，尤其是节点频繁加入、退出造成的网络波动会 极大地增加 DHT 的维护代价，此外，使用 DHT 技术会破坏节点的物理拓扑位置信息，导 致节点间产生“路由绕路”问题，针对这些问题，本文对传统 DHT 算法进行改进,采用分 层 DHT 的技术，构造一种可扩展的、维护开销较小的结构化 P2P 系统,并将其应用于流媒 体系统中，以提高流媒体系统的传输效率和服务质量。 本文在深入分析目前存在的各种基于 P2P 架构的流媒体服务系统的基本原理的基础 上，总结了它们的优缺点，并对其分发机理和可扩展性进行了充分地研究。为了更有效地 提高流媒体服务体系的可扩展性和高效性，提出了一种基于 DHT 的可扩展的流媒体服务体 系：DBS-chord（DHT-based scalable streaming system） 。该体系采用两层模型，很好 的解决了节点随意性的问题；通过使用 Vivaldi 方法来计算节点在网络坐标中的位置，使 得媒体数据的传输只需要穿越少量的网络跳数，有效地解决了节点间产生的“路由绕路” 问题，降低了底层网络的负载，使得 DBS-chord 体系具有较高的效率和可扩展性。为了更 有效地快速定位和管理，采用基于 DHT 层次化的消息路由查找机制，从而实现系统中媒体 内容的快速定位和管理。 通过使用基于 C+语言平台上实现课题设计的模型的仿真，仿真实验结果表明： DBS-chord 体系与传统的 Chord 体系和 ML-chord 体系相比较具有更少的平均访问开销， 平 均维护开销和平均节点加入开销，并能够大幅度提高流媒体系统分发服务质量。课题的研 究成果具有良好的应用价值和推广价值。 本论文的研究内容源于广西教育厅基金项目“网格下的流媒体关键技术研究” 。 关键字：可扩展性 对等网络 分布式哈希 超级节点 II Research of Scalable Streaming Service System Based on Hierarchical DHT Candidate ：Qi Wu Supervisor ：Associate Prof. Shaohua Qin Speciality ：Computer Software and Theory Research Direction ：Computer Network Grade ：2006 Abstract The traditional model of network application performance bottlenecks in services, as well as single point of failure not only limits the client full use of system resources, but also increasingly unable to meet the new needs of distributed applications. And Peer-to-Peer (P2P) networks in collaborative work, distributed information sharing, such as large-scale parallel computing show unique advantages, making it a hot new development. Based on Peer-to-Peer overlay network for streaming media services, how to construct a scalable, node joining and maintenance costs less when the streaming media system is a key issue.the biggest problem of DHT algorithmis is the maintenance of complex mechanisms, in particular, frequent node join the network from the fluctuations caused by greatly increased DHT maintenance cost, based on this, the proposed algorithm to improve the traditional DHT, the DHT stratified technology, construction of a scalable, cost less to maintain the structure of P2P systems, and systems used in streaming media, streaming media system to improve transmission efficiency and service quality. Firstly,we introduce the common peer-to-peer systems based DHT in Internet and summarize their advantages and disadvantages. Secondly, a DHT-based scalable streaming media:DBS-chord. The system using the two-layers model, a good solution to the problem of arbitrary nodes; Vivaldi calculated by using the coordinates of nodes in the network location, making data transmission media need only pass through a small number of hops of the network, an effective solution to the node leads to a detour routing problem, reducing the load on the underlying network allows DBS-chord system with high efficiency and scalability. Based on the levels of DHT-based routing to find the information mechanisms for the data section of the media to access information and hold data section of the abstract node positioning across the P2P network into a distributed hash table, in order to achieve system rapid positioning of media content and management. The experimental results show that conventional Chord-based system compared to, DBS-chord system with the III average query costs less, the average maintenance costs, the average overhead and the node to join node failure of a large-scale stability of better. Finally, with C+ language model designed to achieve the subject of the simulation test system. The research work in my paper is affiliated with the GuangXi office of education science foundation project“Research on the P2P Streaming Media Service Architecture and its Key Technology”. Keywords: scalability； peer-to-peer；DHT；super peer 论文独创性声明论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下进行的研究工 作及取得的成果。除文中已经注明引用的内容外，本论文不含其他个人或其 他机构已经发表或撰写过的研究成果。对本文的研究作出重要贡献的个人和 集体，均已在文中以明确方式标明。本人承担本声明的法律责任。 研究生签名： 日期： 论文使用授权声明论文使用授权声明 本人完全了解广西师范大学有关保留、使用学位论文的规定。广西师范 大学、中国科学技术信息研究所、清华大学论文合作部，有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存 论文。本人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密 论文外，允许论文被查阅和借阅，可以公布（包括刊登）论文的全部或部分 内容。论文的公布（包括刊登）授权广西师范大学学位办办理。 研究生签名： 日期： 导 师签名： 日期： 第一章第一章 绪论绪论 1.1 研究背景 1.1 研究背景 随着宽带技术的日趋普及和通讯网络技术的快速发展，在计算机互联网上产生和提供 了大量的网络服务， 网络中的数据信息不断增加， 数据分布由集中向分散发展， 原有的 C/S 架构方式暴露出如负载容量有限，过分依赖中央服务器的正常运作等问题。具有大量信息 资源且少依赖或不依赖中央服务器特性的 Peer-to-Peer(P2P)网络技术应运而生。 1.2 流媒体分发服务研究现状 1.2 流媒体分发服务研究现状 流媒体的分发服务主要有四种类型1：C/S 模式的流媒体分发服务；基于 CDN 的 流媒体分发服务；基于 IP 组播的流媒体分发服务；基于 P2P 的流媒体分发服务。 1.2.1 C/S 模式的流媒体分发服务 1.2.1 C/S 模式的流媒体分发服务 在传统的 C/S 模式的流媒体分发服务中，如图 1-1 所示，服务器是网络的控制核心， 服务器以单播的形式和每个客户建立连接，信息和数据都保存在服务器端，只有服务器端 具有控制能力，客户端基本上是一个高性能的 I/O 设备。由于流媒体服务具有高带宽、持 续时间长等特点, 随着节点的增加，服务器的负载就越来越重，形成了系统的瓶颈，所以 系统服务的可扩展性很差。此外，C/S 模式下的互联网是完全依赖于服务器，没有服务器， 网络就没有任务意义，存在单点失效的问题。 ServerServer ClientClient 图 1-1 传统 C/S 模式 1.2.2 基于 CDN 的流媒体分发服务 1.2.2 基于 CDN 的流媒体分发服务 CDN2即内容分布网络，它的基本思想是内容提供商提供的媒体文件部分或全部缓存 到位于因特网 “边缘”的距离用户较近的缓存代理服务器上， 使客户能从位于本地的缓存代 理服务器上获取流媒体内容。CDN 从技术上全面解决了由于网络带宽窄、用户访问量大、 网点分布不均等问题，提高了用户访问的性能，有效减少了主干网络负担和传输延迟，同 2 时也增加了系统容量。但是，基于 CDN 的体系与存在明显的不足，由于客户端的动态性， 很难确定需要部署多少边缘服务器； 其高昂的成本， 始终是阻碍其大规模部署的主要因素。 源服务器内容分发服务器 图 1-2 CDN 体系结构 1.2.3 基于 IP 组播的流媒体分发服务 1.2.3 基于 IP 组播的流媒体分发服务 IP 组播3-5：目前基于 TCP/IP 的 Internet 网络主要有三种传输方式：单播、广播和组 播。 单播技术是一种单点到单点的数据传输方式，如图 1-3 所示，发送端向每个接收端都 发送单播分组，路由器只转发分组。缺点是如果多个用户同时请求同一个数据，服务器必 须通过网络给每个用户发送一份相同的数据。随着客户端数目的增加，很容易造成服务器 端的网络拥塞。 R1R1R2R2 R4R4R3R3 R5R5 P1P1 P2P2 P4P4 P3P3 图 1-3 单播 广播技术是一点到所有点的数据传输方式，采用这种方式，服务器只需要发送一次 数据，数据就会扩散到所有用户，效率很高。但是由于发送模式的盲目性，数据会扩散到 所有的网段而不关心网段中的主机是否需要接受。如果多媒体通信采用广播发送方式，则 大量的数据将造成 “广播风暴”，使网络通信处于瘫痪。 组播技术融合了以上两种传输模式的特点，如图 1-4 所示，发送端只发送一份分组， 3 路由器根据需要复制并向接受端转发分组，避免了数据的冗余又不会盲目地造成网络带宽 的浪费，有效地降低了网络负载，目前很多的流媒体应用都采用这种传输模式。 R1R1R2R2 R4R4R3R3 R5R5 P1P1 P2P2 P4P4 P3P3 图 1-4 IP 组播 IP 组播方式在网络上只有唯一的数据包在进行传输，每个客户端都能接收到这个数据 包，这极大地减轻了服务器的带宽需求，并且减轻了整个网络的负担。 理论上 IP 组播是一种高效的数据分发方案，但也存在以下问题6：路由器必须为每 个组播组保存状态（即路由项） ，这样带来了巨大的复杂性，同时也限制了系统的可扩展 性；IP 组播缺乏有效的组管理，导致任一用户可以加入某特定的组会话接收数据；缺 乏灵活、可扩展的地址分配机制，每个组播会话都要求有一个全球唯一的组地址，组地址 的缺乏也会导致组播会话冲突；IP 组播需要路由器的支持，需要路由器维持每个组播组 的状态信息，这有可能增加整个网络的复杂性和扩展性；缺乏有效的计费模型。因此大 规模地部署 IP 组播仍然困难且缓慢。 1.2.4 基于 P2P 的流媒体分发服务 1.2.4 基于 P2P 的流媒体分发服务 随着各种新兴的具有一对多、多对多通信特点的应用的出现，对组播提出了更高的要 求，而 IP 组播由于种种原因没有实现大规模的部署。同时 Internet 的端用户的计算能力不 断增强，而端用户的计算资源常常处于闲置状态，为了有效地利用这些资源，基于 P2P 技 术的流媒体系统应运而生，在应用层实现组播功能而不需要网络层的支持，这样就可以避 免出现由于网路层迟迟不能部署对组播的支持而使组播应用难以进行的情况，有效地提高 了服务的可扩展性，大大缓解了服务器的压力。 应用层组播78的基本思想是屏蔽底层物理网路的拓扑细节，将组成员节点直接自组 织成一个逻辑覆盖网络（Overlay Network）,并提供应用层路由协议来构建和维护该组播网 络，摆脱了对网络层的依赖，为数据传输提供更高效、可靠的服务。与 IP 组播相比，应用 层组播主要有以下几点优势9： 应用层组播不需要路由支持，也不需要改变底层网路，组播服务的部署相对容易不 需要在路由器上维护组播组的状态，可以支持大量的组，解决 IP 组播扩展性差的问题。 可以根据网络条件的变化， 动态优化组播树的结构， 同时可以方便的实现拥塞控制、 4 服务定制等 IP 组播很难完成的工作。 应用层组播可以很好的解决组播地址分配不足的问题。 图 1-5 对 IP 组播和应用层组播的数据传输方式进行了比较 R1R1R2R2 R4R4R3R3 R5R5 P1P1 P2P2 P4P4 P3P3 R1R1R2R2 R4R4R3R3 R5R5 P1P1 P2P2 P4P4 P3P3 （a）IP 组播 （b）应用层组播 图 1-5 IP 组播与应用层组播比较 图中，P1、P2、P3、P4、P5 为主机，R1、R2、R3、R4、R5 为路由器，带箭头 的线表示数据包的发送方向。图 1-5（a）为 IP 组播，P1 为发送者，数据包从 P1 到 R1， 再由 R1 复制数据后分别发送给 R2、R4、R5，R2、R4、R5 复制数据后分别发送给 P2、 P4、P3。在 IP 组播中，发送端只发送一份分组，路由器根据需要复制并且向接收端转发 分组。图 1-5（b）为应用层组播，数据包从 P1 通过 R1、R2 发送给 P2，P2 再将数据通过 R2、R3 发送给 P4，最后 P4 通过 R3、R4 将数据发送给 P3。 1.3 本论文的研究内容与创新点 1.3 本论文的研究内容与创新点 本论文的研究受广西教育厅基金项目“网格下的流媒体关键技术研究”的资助。具体 的研究内容及创新点如下： （1）深入分析了目前存在的各种基于 P2P 架构的流媒体服务系统，并总结了它们的 优缺点。 （2）提出了一种可扩展的基于 DHT 的流媒体服务体系：DBS-chord。该体系采用两 层模型， 很好的解决了节点随意性的问题； 通过使用 Vivaldi 来计算节点在网络坐标中的位 置，使得媒体数据的传输只需要穿越少量的网络跳数，有效地解决了节点间产生的“路由 绕路”问题，降低了底层网络的负载，使得 DBS-chord 体系具有较高的效率和可扩展性。 为了更有效地快速定位和管理，采用基于 DHT 层次化的消息路由查找机制，从而实现系 统中媒体内容的快速定位和管理。 （3）最后，使用 C+语言实现课题设计的模型，并对系统进行仿真测试。实验结果 与基于传统的 Chord 体系相比较，DBS -chord 体系具有更少的平均访问开销，平均维护开 销和平均节点加入开销，并能够大幅度提高流媒体系统分发服务质量。 5 1.4 本文的组织 1.4 本文的组织 本文首先在第二章中分析了目前流行的一些 P2P 流媒体系统架构，对它们的优缺点进 行了归纳分析，并介绍了目前应用于 P2P 系统节点组织的一些 DHT 算法；在第三章中提 出了一种基于 DHT 的两层的流媒体服务体系 DBS-chord；在第四章讨论了 DBS-Chord 系 统的设计与实现，并进行了仿真模拟；最后是对本文的总结，并对下一步的工作进行了展 望。 1.5 本章小结 1.5 本章小结 本章介绍了目前流媒体分发服务的主要类型，并对每种类型的优缺点进行了总结；然 后介绍了本论文研究的内容和创新点；最后对本论文的组织进行了简略的介绍。 6 第二章第二章 对等网络中流媒体系统的相关理论对等网络中流媒体系统的相关理论 对等网（Peer-to-Peer,P2P）是一种分布式网络模型，在该模型中所有的节点是对等 的（称为对等点） ，这些对等点既是资源（服务和内容）提供者（Server） ，又是资源（服 务和内容）获取者（Client） 。对等点之间通过直接互连共享资源信息、处理器资源、存 储资源甚至高速缓存资源等，无需依赖集中式服务器或资源就可以完成。 在 P2P 网络中，所有的资源和服务分散在所有的节点上，信息的传输和服务的实现都 直接在节点之间进行，可以无需中间环节和服务器的介入。随着用户的加入，不仅服务器 的需求增加了，系统整体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的 需求，具有很好的可扩展性。由于服务是分散在各个节点之间进行的，部分节点或网络遭 到破坏对其它部分的影响很小，具有很好的健壮性。P2P 网络中每个节点既是服务器又是 客户机，这样就减少了对传统 C/S 结构服务器计算能力、存储能力的要求，同时因为资源 分布在多个节点，因此能更好的实现整个网络的负载均衡。 2.1 用于对等网络的分布式哈希算法 2.1 用于对等网络的分布式哈希算法 随着计算机技术以及网络技术的发展和普及，在计算机互联网上产生和提供了大量的 网络服务，网络中的数据信息不断增加，数据分布由集中向分散发展，原有的 C/S 架构方 式暴露出如负载容量有限，过分依赖中央服务器的正常运作等问题。具有大量信息资源且 少依赖或不依赖中央服务器特性的 Peer-to-Peer(P2P)网络技术应运而生。为了更好的支 持对 P2P 网络的扩展，更好地管理和维护在 P2P 网络中各个节点的信息，提供更高效和快 速的查询下载服务， P2P 网络在节点的组织方式中引入了分布式哈希表 （Distributed Hash Table，DHT)。 分布式哈希表原理15是：首先将每一份资源都由一组关键字进行标识，系统对其中的 每个关键字进行哈希，得到关键字标识符 key；网络中的每个节点对 IP 地址进行哈希得到 节点标识符 ID；关键字标识符和节点标识符都是唯一的；按照某种映射关系，将关键字标 识符映射到节点标识符上，该节点标识符对应的节点就存储此关键字标识符的对应信息。 所有key, value对构成一张很大的文件索引散列表，其中: key 是关键字哈希；value 是要存储的信息地址。散列表被分割成不连续的块，每个节点被分配给一个属于自己的散 列块。每个节点按照某种规则维护散列表的一部分。用户搜索时,用同样的哈希算法计算 出每个关键字的标识符 key,再根据关键字标识符知道其对应信息资源的存储位置,从而能 够快速定位资源的位置。研究人员对对等网络的分布式哈希算法进行了大量卓有成效的研 究， 提出了多种具有良好可扩展性的分布式哈希算法。 比较典型的有方案主要有： Chord10、 CAN11、Pastry12、Tapestry13、Kademelia14等。 7 2.1.1 Chord 2.1.1 Chord Chord10是由美国麻省理工学院提出的一种结构化分布式查找算法。它通过一致性哈 希函数为网络中的所有节点和资源赋予 m 位的标识符。其中，节点的标识符一般通过对节 点 IP 地址的哈希运算得出，资源的标识符一般是通过对资源名称（网络中资源名称应唯 一） 的哈希运算得出。 所有可能的 N=2m个节点标识符从小到大按顺时针方向排列成那个一 个 Chord 环。对于一个标识符 k，标识环中顺时针方向第一个物理节点称作 k 的后继节点， 记做 successor(k)； 逆时针方向第一个物理节点称作 k 的前驱节点， 记做 predecessor(k)。 Chord 规定标识符为 k 的资源存储在 k 的后继，即 successor(k)上。如图 2-2 所示是一个 m=5 的 Chord 环， 环中最大可能拥有 N=25=32 个节点， 现环中有 10 个节点， successor(2)=4， successor(7)=8，successor(14)=16，successor(20)=20，successor(30)=31，因此，K2 存储在 N4 上，K7 存储在 N8 上，K14 存储在 N16 上，K20 存储在 N20 上，K30 存储在 N31 上。 N N1 1 N N4 4 N N8 8 N N20 20 N N16 16 N N13 13 N N10 10 N N23 23 N N29 29 N N31 31 K2K2 K20K20 K30K30 K14K14 K7K7 图 2-2 Chord 逻辑拓扑图 在标识空间的大小为 N （m= 2N） 的 Chord 环中， 每个节点维护的内部数据结构包括： 前驱节点，后继节点，并维护一张最多 m 个表项的路由表（称为 finger 表） （m 是哈希的 比特值） ， 连续 m 个后继点的列表， 前 m 个节点存储资源备份列表。 其中前三项是基本 Chord 算法所规定的必备数据结构，后两项是 Chord 算法考虑系统容错性和数据可靠性而提出的 附加数据结构。为了提高定位资源的效率,每个节点需要保存一个 finger 表,来记录标识 符为(nodekey + 2 k - 1) mod 2m (1 =k =m) 的资源在 Chord 环上的后继节点的信息(其 中 nodekey 为当前节点的标识符)。Chord 路由表每一项的结构如表 2-1 所示： 8 表2-1 fingerk定义及说明 定义 说明 id (nodekey + 2 k - 1) mod 2m (1 =k =m) nodekey (nodekey + 2 k - 1) mod 2m (1 =k =m)的后继节点在Chord环上的标识符 IP (nodekey + 2 k - 1) mod 2m (1 E或C-A-B-E等。 10 图 2-3 2维的的笛卡儿坐标空间划分成五个节点区域的示例11 CAN是一种动态网络，当一个新的节点加入网络时必须得到自己的一块坐标。CAN通过 分裂现有的节点区域实现这个过程，它把某个现有的节点区域分裂成同样大小的两块,自 己保留其中的一块而另一块分给新加入的。整个过程分为以下三步： （1）首先新节点必须找到一个已经在CAN 中存在的节点。 （2）接着使用CAN 的路由机制，找到一个区域将要被分隔的节点。 （3）最后执行分裂操作，告知原有区域的邻居节点发生了分裂，以便新节点能够被别的 节点路由到。 当节点离开CAN时，必须保证它的区域被CAN分配给其他仍然在系统中节点。一般是由 某个节点来接管这个区域和所有的（key,value）数据库。如果这个区域可以和相邻区域 合并成一个大区域，那么CAN将执行合并操作；否则，CAN会将该区域交给其邻近节点中区 域最小的节点。在正常情况下，CAN的相邻节点之间会周期性的更新消息，节点在规定的 时间内如果没有接到邻居节点的更新消息，它会认为此邻居节点失效。这时，该节点将启 动替换操作，并启动一个时钟，失效节点的每个相邻节点会彼此独立地执行该过程。如果 时钟超时，节点将向失效节点的所有邻居发送替换消息，该消息中包括它自己的区域面积 信息。当某个节点接收到替换消息后，如果它的区域面积比发出消息的节点大，那么它将 取消替换操作。否则，它将发出自己的替换信息。该机制保证了面积最小的节点替换失效 节点。 为了避免多个相邻的节点同时失效导致不一致情况出现， CAN将首先执行修复操作， 通过查找更远邻接区域的状态来保证替换操作的一致性。 在CAN中，如果一个d 维空间被等分成n个区域，那么平均路由长度是(d/4)(n1/d)，每 个节点需要维护2d个的邻居节点信息。这表明CAN 的可扩展性很好，节点数增加时每个节 点维护的邻居节点信息不变，而且路由长度也只是以O（n1/d）的数量级增长。另外，CAN 11 还支持容错特性。在坐标空间中，两点之间可以有许多不同的路径，因此，单点失效基本 对CAN没有太大的影响；当遇到节点失效时，CAN节点会自动绕过失效节点进行路由。CAN 算法的路由路径趋于过长,定位内容花费的世纪链路延迟大是它存在的主要问题。 2.1.3 Pastry 2.1.3 Pastry Pastry12 是英国剑桥的微软研究院和莱斯大学提出的可扩展的分布式对象定位和路 由协议，它是由 Pastry 节点组成的自组织的高结构化覆盖网络(Overlay Network)。在 Pastry 中，文件(或者文件指针) 存放在确定的位置上，系统提供从文件标识符到存放该 文件的节点标识的映射服务，通过查询请求路由到该节点。Pastry 路由算法能有效地检索 到结果，同时保证搜索步数在 O(logN) 的范围内(N 为节点总数) ,实现了可扩展性搜索。 Pastry19网络中每个节点或数据通过哈希函数映射得到唯一 128 比特的标识符，用于 在节点空间中标识节点的位置。节点号可以通过计算节点公钥或者 IP 地址的哈希函数值 来获得。Pastry 中每个节点维护一个路由表，一个叶子集和一个邻居集,如图 2-4 所示。 图2-4 Pastry 节点数据结构示意图 (1)路由表(Routing Table)。假定网络由 N 个节点组成，它有|log2b N|行，每行由 2b-1 (b 是一个配置参数，典型取值是 1 ,2 ,3 ,4)个入口的表项组成。行 n 的 2b - 1 个 入口指向其 NodeID，和当前节点的 NodeID 共享前 n 位但第 n+1 位不同的 2b-1 个表项。值 b 的选择考虑了路由表的长度和路由跳数的权衡，b 越大则路由跳数越小，需要维护的路 由信息越多。路由表中每行的阴影项表示当前节点号对应的位。 （2）叶子集(Leaf Set)。叶子节点集合中存放的是和当前节点的标识符从数值上看 12 最接近的节点，可以取环上的本地节点的前 L/2 个和后 L/2 个节点构成叶节点集，L 为 2b。 叶子集主要保证了可靠消息的传递。 （3) 邻居集(Neighborhood Set)。它包含同本地节点最接近的|M|(|M|是配置参数, 值为 22b)个节点， 邻居集中是 M 个离本地节点距离最近的节点，并不用于路由转发， 只是为了保证网络中节点的物理位置特性。 Pastry 进行查找操作时,首先检查找消息的关键字标识 Key 是否落在叶子节点集范围 内。如果是，则直接将消息转发给叶子节点集中节点标识和关键字标识最接近的节点；如 果 Key 没有落在叶子节点集范围内，节点就会将消息转发给路由表中的一个节点。该节点 的标识符和 Key 的相同前缀至少要比当前节点的标识符和 Key 的相同前缀长一个数位。如 果路由表中相应的表项为空，或者表项中对应的节点不可达，这时查询消息将被转发给前 缀长度相同但节点标志符更接近 Key 的节点。依此进行，直到找到目的节点。 假定一个标识符为 X 的新节点要加入 Pastry，X 在加入 Pastry 网络之前，必须首先 要知道一个相邻节点 A 的位置信息，通过 A 在 Pastry 中对一个以 X 为关键字的消息进行 路由。X 首先要求 A 路由一条“加入”消息，消息的关键字就是 X 的节点号。同其他的消 息一样,这条消息最终会到达具有和 X 最接近的节点号的节点 R。作为响应,节点 A 和节点 R,以及从 A 到 R 的路径上的所有其他节点都会把自己的数据结构传给 X。X 利用这些信息 初始化自己的数据结构。初始化完成后，通知其它节点 X 的出现，并进行必要的路由表更 新。 Pastry 网络中当相邻节点不能和某个 Pastry 节点通信时， 就认为该节点发生了失效。 如果是叶子节点集合中 L 的节点失效，则当前节点会要求当前叶子节点集合中最大节点号 或者最小节点号(根据失效节点的节点号决定，如果失效节点号比当前节点号大，则用最 大节点号的节点，反之则用最小节点号的节点)的节点把它的叶子节点集合 L送过来，L 中如存在 L 中没有的节点，当前节点将从中选择一个替代失效节点，在替代之前，需要首 先验证该节点是否还在系统中。如果是路由表中某项对应的节点失效，那么当前节点将从 该项所在的路由表行中选择另一个节点，要求它把自己的路由表中对应位置的项发过来， 如果当前节点的路由表中对应行已经没有可用节点了，那么当前节点将从路由表的下一行 中选择一个节点，这个过程将持续进行直到当前节点能够得到一个替代失效节点的节点 号，或者当前节点遍历了路由表为止。 2.1.4 Tapestry 2.1.4 Tapestry Tapestry13是美国加州大学伯克利分校提出的一种新型的 P2P 网络定位和路由算法。 Tapestry 的思路源于 Plaxton,Rajamaran 以及 Richa 提出的 Plaxton20方案。该算法可以 对消息进行与位置无关的路由，将查询消息传递到最近的存储有目标对象拷贝的节点。 Tapestry 的拓扑结构被称为 Plaexton mesh，每个节点都可以承担服务器、路由器好 客户端的功能。如图 2-5 所示，每个对象和节点以一个随机的定长、具有同一基的位序列 13 作为标识符，与 Pastry 中的标识符类似。 图2-5 Tapestry的逻辑拓扑图 13 Tapestry 中所有的节点依据标识符自组织成一个重叠网络。 每个节点需要维护一个邻 居映射表、热区（hotspot）监视器、对象定位指针和对象存储。 Tapestry 查找步骤如下： （1）当前节点计算自己的 ID 与目的 ID 的相同后缀数目 m。 （2）从路由表中选择一个中间节点（一般在 m+1 列） ，使得中间节点的 ID 与目的节 的 ID 的相同后缀数目大于等于 m+1。 （3）把查找任务转交给这个中间节点继续查找。 这个过程递归进行，直到找到目的 ID。 Tapestry 的节点加入算法和 Pastry 类似。节点 A 在加入 Tapestry 网络之前，首先 需要知道一个已经在网络的节点 B；然后通过 G 发送消息来查找它自己（A）的标识符，根 据经过节点的对应的邻居节点表构造自己的邻居节点表；构造完自己的数据结构后，节点 A 将通知网络中的其他节点自己已经加入网络。 Tapestry 采用两种机制处理节点的退出。一种情况是节点失效，在这种情况下，它 的邻居可以检测到它已经退出网络并相应的调整路由表。另一种机制是节点在退出系统之 前，通过后向指针通知所有把它作为邻居的节点，这些节点会相应调整路由表并通知对象 服务器该节点已经退出网络。 Tapestry 在 Plaxton 的思想上加入了容错机制，当节点失效时，它的邻居节点可以 检测到它失效并对路由表作相应调整，具有自我管理、容错和灵活负载平衡等特点，从而 可适应 P2P 的动态变化特点。 2.1.5 Kademelia 2.1.5 Kademelia Kademelia14 是美国纽约大学在 2002 年提出的。与 Chord、CAN、Pastry、Tapestry 不同，在 Kademlia 网络中，两个节点之间距离并不是依靠物理距离、路由跳数来衡量的， 而是根据两个节点标志的异或(XOR)，建立了一种全新的 DHT 拓扑结构，相比于其他算法， 大大提高了路由查询速度。在 Kademlia 网络中，对信息资源的标识符进行哈希得到一个 14 键值 key。然后，信息的索引被存放到对应键值的节点。两个节点之间的距离 d 定义为它 们的 ID 进行异或运算后的值。假定两个节点标志符分别为 x 与 y，则有 d=xy。每个节 点都可以根据 d 值来判断与其它节点的逻辑距离。 每一个节点均维护了 160 个 list。 其中的每个 list 均被称为一个 K-桶。 在第 i 个 list 中,记录了与当前节点距离为 2i2i+1的一些其他对端节点的网络信息(Node ID、IP 地址、 UDP 端口)。查询关键字 Key 的步骤如下： （1）发起者从自己的 K-桶中筛选出若干距离目标节点最近的节点，并向这些节点同 时发送异步查询请求。 （2） 被查询节点收到请求之后,将从自己的 K-桶中找出自己所知道的距离目标节点最 近的若干个节点，并返回给发起者。 （3）发起者在收到这些返回信息之后，再次从自己目前所有已知的距离目标较近的 节点中挑选出若干没有请求过的。 上述步骤不断重复,直至无法获得比查询者当前已知的 K 个节点更接近目标的活动节 点为止。 2.2 上述分布式哈希算法的比较分析及评价 2.2 上述分布式哈希算法的比较分析及评价 上一节分析了五种常见的分布式哈希算法， 从中可以看出， 各种算法都有自己的特点。 表 2-2 归纳总结了各种算法的拓扑结构、路由表大小、路由复杂度和的存放 位置。下面将从算法的扩展性、容错性、负载平衡性三个方面综合评估各种算法的优劣。 表2-2DHT算法比较图 DHT算法 路由复杂度 路由表大小拓扑结构的存放位置 Chord O(N) O(N) 环行 后继节点 Tapestry O(N) O(N) Plaxton 键值最近的节点 Pastry O(N) O(N) Plaxton 键值最近的节点 CAN O(dN1/d) O(d) D维环行 存储在负责管理key所在空间的节点上 Kademlia O(k) O(k) 覆盖网 距离key最近的k个节点上 2.2.1 算法的可扩展性 2.2.1 算法的可扩展性 Chord、Pastry 协议的开销随着系统规模(节点总数 N)的增加而按照 O( N)的比例 增加，而且新节点加入时需要更新的路由表信息也较少，具有很好的可扩展性，可以用于 大规模的系统。与 Chord 和 CAN 等相比, Tapestry 在建立邻居表时很好地考虑了节点邻接 性问题，它的节点动态加入算法很好地实现了系统的扩展性。 15 2.2.2 算法的容错性 2.2.2 算法的容错性 在 P2P 网络中，节点可以自由地加入或离开系统，一旦如此，查找将终止。Chord 中 节点失效时，每个包含该节点的指针表都要把该节点换成它的后继节点，为此每个 Chord 节点都维护一张包括 r 个最近后继节点的后继列表。如果某个节点注意到它的后继节点失 效了，就可以用其后继列表中第一个正常节点替换失效节点。正常情况下，CAN 中每个节 点向其所有邻居节点发送周期性的更新消息。如果多次没有接收到某个邻居的更新消息， 那么节点就认为这个邻居失效。这时节点将启动替换机制来更新路由表。采用这种机制可 以有效地选择面积最小的邻居节点来接管失效节点。CAN 中一个节点一个或几个邻居节点 失效时，它依然可以沿着有效的路径路由，因此 CAN 算法具有很好的稳健性。Pastry 系统 会让邻近节点启动替换机制，通过某种策略选择一个节点进行替换，因此 Pastry 系统有 很好的容错性。Tapestry 在 Plaxton 的思想上加入了容错机制，当节点失效时，它的邻居 节点可以检测到它失效并对路由表作相应调整， 从而可适应 P2P 的动态变化特点。 Kademlia 要求每个节点必须周期性地发布全部自己存放的key, value对数据，并把这些数据缓 存在自己的 k 个最近邻居处。这样存放在失效节点的数据会很快被更新到其他新节点上， 因此 Kademlia 算法具有很好的容错性。 2.2.3 算法的负责平衡性 2.2.3 算法的负责平衡性 DHT 算法设计的一个重要性能就是平衡查询负载。 Chord、 Tapestry、 Pastry、 Kademlia 所有的节点以同等的概率分担系统负荷，从而可以避免某些节点负载过大的情况，因此负 载平衡性好。每个 CAN 节点都要保存一张坐标路由表,其中包括它的邻居节点(相邻空间区 域中的节点)的 IP 地址和其维护的虚拟坐标区域。当需要查询 key 时,路由的每一步只需 将查询信息发送给离 key 值更近的邻接节点。维护面积大的节点的邻居节点较多,查询时 负载也大。表 2-2 为这些算法从容错性、扩展性、负责平衡性的比较。 表2-2 DHT算法性能比较 DHT算法 容错性（节点失效处理） 扩展性 负载平衡性 Chord 用后继列表中第一个正常点替换失效节 点 扩展性好 负载平衡 Tapestry 邻居节点启动替换机制 路由表或邻居 节点表通过某种策略选择一个节点替换 扩展性好 能够灵活地平衡负载 Pastry 邻居节点启动替换机制 路由表或邻居 节点表通过某种策略选择一个节点替换 扩展性好 能够灵活地平衡负载 CAN 其他有效邻居点路由 扩展性优 维护区域大的节点负载 大 Kademlia 容错性很好 扩展性好 负载平衡 16 它们的共同缺点是只支持精确匹配的查询，无法提供模糊查询，其拓扑结构的组织过 程中容易破坏网络的物理位置信息，有可能导致搜索路由的“绕路”问题。此外，系统的 维护开销较大，尤其是节点的频繁加入、离开。 近几年，出现了一些新的 P2P 研究，它使用一种元数据来描述共享资源，在一定程度 上解决了精确匹配资源的问题。而且，使用这种元数据的 P2P 系统可以提供更好的伸缩性 和更快的数据访问。这种基于语义的 P2P 系统例如有 RDFStore21， Edutella22-24, RDFPeers25-26, Expertise27, ContextPeers28, SCS29, SuperRing30, M-Chord31, 和 R-Chord32。 2.3 本章小结 2.3 本章小结 本章重点分析了当前用于对等网络的分布式哈希查找算法Chord 、 Tapestry、 CAN 、 Kademlia 和 Pastry 算法，并对上述分布式哈希查找算法从容错性、扩展性、负责平衡性 进行了比较。 17 第三章第三章 基于基于 DHT 的可扩展的流媒体体系的可扩展的流媒体体系 在结构化的 P2P 系统中，通常采用分布式哈希表（DHT）来建立节点之间的逻辑拓扑 关系，DHT 算法能够很好地解决 P2P 网络资源定位的问题、自适应节点的动态加入和退出， 不会随着网络规模的扩大而导致维护开销的急速增加，具有良好的可扩展性、容错性、节 点 ID 分配的均匀性和自组织能力。由于采用了确定性逻辑拓扑结构，查找的