（计算机应用技术专业论文）impastry：一种基于pastry系统的改进模型.pdf

中南民族大学硕士学位论文 i 摘 要 p 2 p技术是一种对等计算技术，以 p 2 p技术为基础的网络系统在运行时形成 p 2 p 网络。在 p 2 p 网络中，每个节点同时具有服务器和客户机的双重功能，可同时 作为服务的提供者和使用者，是一种通过直接交换来共享资源的方式，它对计算 机网络的发展产生了重要的影响。本文就 p 2 p系统的定义、体系结构、技术特性 和关键技术等进行了讨论。 作为实现 p 2 p的关键技术，资源定位一直是学术界研究的一个重点。本文对 p 2 p 系统中常用的资源定位方式进行了系统的分类， 针对使用最多的基于 d h t技术 的资源定位方式进行了详细的分析，并对一些有代表性的系统，如 c a n , p a s t r y , t a p e s t r y和 c h o r d系统结构进行研究，重点分析了各个系统关于系统路由、节点 加入和节点退出方面的特性。 通过对现有基于 d h t方式的系统进行分析，我们可以发现这些系统普遍存在 覆盖网络和物理网络不一致的问题。为解决上述问题，提供更高效的资源定位服 务，提高 p 2 p 网络的性能，本文提出了建立在 p a s t r y 基础上的 i m p a s t r y 系统。 通过修改覆盖网络节点标识生成函数，i m p a s t r y系统使覆盖网络节点标识与 物理网络节点 i p之间建立一种映射关系，即物理网络节点间在地域上相互关系， 能够反映到对应覆盖网络节点标识的相互关系上。此外 i m p a s t r y 还根据本系统覆 盖网络的特点，对原有 p a s t r y节点路由表和叶子节点表，及节点加入和退出方式 进行了修改。最后，本文通过分析 i m p a s t r y 系统实现，进一步阐述了系统的设计 思想。 关键词：p 2 p ；d h t ；资源定位；p a s t r y ；覆盖网络 impastry：一种基于 pastry 系统的改进模型 ii abstract in a p2p (peer to peer) network, the peers are computing systems which are connected to each other via the network. files can be shared directly between systems in the network without the need of a central server. each equal peer node in p2p network simultaneously functions as both “ client” and “ server” to other peers in the network. now, the development of peer to peer network has been generating tremendous impact on networks infrastructure itself. as a key aspect of the p2p network, resource locating technology is always being the focus in academic researches. commonly, p2p networks can be classified by using the different locating technology, and dht is one of the most significant methods for locating. in this paper, we discuss the typical p2p systems based on dht, such as can, chord, tapestry and pastry, and then have a deep insight of each system in the system routing, node joining and departing. according to the analysis of the existing dht based p2p network systems, we can conclude that the logical overlay network is inconsistent with the realtime physical networks, which could cause the resource locating inefficiently, and then affect the performance of the p2p network system. to alleviate the symptom mentioned above, we introduce an impastry (identical mapping pastry) p2p system that is based on the pastry system. by adjusting the system for the peer node id generation, impastry can easily build an identical mapping relationship between the overlay network and physical networks. in this relationship, the peer nodes which are near to each other in physical network are still adjacent with each other in overlay network. in addition, impastry has made several modifications to adapte to the identical mapping relationship. key words: p2p；dht；resource locating；pastry；overlay network 中南民族大学中南民族大学 学位论文原创性声明学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 作者签名： 日期： 年 月 日 学位论文版权使用授权书学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权中南民族大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 1、保密，在_年解密后适用本授权书。 2、不保密。 （请在以上相应方框内打“” ） 作者签名： 日期： 年 月 日 导师签名： 日期： 年 月 日 中南民族大学硕士学位论文 1 第 1 章 绪论 近年来，p 2 p 技术发展迅速，在 p 2 p结构的网络中，每个节点（p e e r ）所拥有 的权利和义务都是对等的， p 2 p技术正在改变互联网目前以大型服务器、大型网站 为中心的状态，并逐渐改变着整个互联网的传统结构。在这样的网络中如何快速 地进行对等体、资源的定位愈显困难和重要，定位技术也成为 p 2 p技术体系中的 难点和重点之一。本文着重研究 p 2 p 网络中的定位问题。 1 . 1 p 2 p 网络概述 1 . 1 . 1 p 2 p网络的背景 p 2 p 对等网络（p e e r t o p e e r ） 技术起源于 2 0 世纪 7 0 年代中期，是源 于局域网中的一种对等共享技术。在互联网构架基础的 t c p / i p 协议族设计之初， 协议族本身没有客户、 服务器的概念， 更没有规定客户机/ 服务器( c l i e n t / s e r v e r ) 这种通信交互模型，协议族的初衷是所有的设备在通信中都是相互平等的对 等网络的初始概念。这里，客户机/ 服务器模型是指区分服务的请求者和提供者的 模型，即服务由请求者发起，服务提供者相应并提供服务。该模型中，一般是一 个服务器为多个客户机服务，因此通常服务器的处理能力和占用网络带宽都高于 普通客户机，这种模型在网络带宽和主机处理能力不对等的计算机网络中，该模 型被广泛采用，这也使得在互联网后续的发展过程中对等网络技术没有能够迅速 发展。 随着科技的不断进步，计算机软硬件及计算机网络得到了长足的发展，传统 的客户机和服务器模型仍然占主导地位，但现代客户机通常在大部分时间里是空 闲的，并且有大量的软硬件和网络资源未被使用，实际上导致了资源浪费。另外， 接入网络的计算机数量和种类也在不断扩大，除了包括传统的大型机、p c机，还 包括越来越多的具有一定计算能力的手机和 p d a等移动终端设备。为了最大限度 地使用这些广泛存在的客户机的能力，对等通信和计算的概念又重新引起人们的 关注，对等网络模型也在逐渐成为计算机网络技术发展的主流。 在 p 2 p对等网络模型中，并没有明确的客户机和服务器，每一台计算机都可 以看成是服务器，也可以看成是客户机。计算机不仅接收数据，而且还发送数据。 impastry：一种基于 pastry 系统的改进模型 2 计算机不仅提出服务请求，而且还接收服务请求。图 1 . 1是对普通 p 2 p对等网络 模型的说明。 图 1.1 普通 p2p 对等网络模型 p 2 p对等网络模型不仅可以利用机器空闲的资源，而且具有传统的客户机/ 服 务器模型所不具备的优点。传统的客户机/ 服务器模型存在单点失效和性能瓶颈等 问题。对于单一服务器服务于多个客户机的模型，当客户机数量不断增多时，对 服务器的要求就越高，因此整个网络的性能受限于服务器，服务器有可能成为网 络的性能瓶颈；而且一旦服务器失效，它所提供的服务便终止，整个以它为中心 的网络就会瘫痪，也就是说存在单点失效问题。从图 1 . 1中，我们可以发现对等网 络中每一个节点（p e e r ）的地位都是平等的，信息资源被分布在各个节点上，传 统的服务器不在是网络模型的中心。因此，对等网络模型可以很好的避免客户机/ 服务器模型可能带来的单点失效和性能瓶颈等问题，不依赖或尽可能不依赖传统 的中央服务器，使每个节点都参与服务器和客户机的角色。 1 . 1 . 2 p 2 p网络的发展现状 对于 p 2 p这个古老而又新鲜的技术，因其能够充分利用网络中闲置的资源， 可以为用户提供高速、高可靠性的服务，逐渐吸引了众多高校研究小组，学术团 体和商业公司关注的目光。从目前情况看，p 2 p 实际的应用研究主要体现在以下 几个方面: ( 1 ) p2p 分布式存储系统 p 2 p 分布式存储系统（文件共享与下载）是一个用于对等网络的数据存储系 统，它可以提供高效率的、健壮的和负载平衡的文件存取功能。对于存储系统, 用 户关心数据的定位、搜索以及路由的效率，安全性也是重要的因素。集中方式在 很多情况下不再适用这种大规模数据存储的要求, 这就需要一个新的体系来管理 系统中的数据。p 2 p 分布式存储系统就是解决这样的问题。这些研究包括全分布 中南民族大学硕士学位论文 3 式存储系统: 如 o c e a n s t o r e 1 、p a s t 2 3 和 f r e e h a v e n 4 等。 ( 2 ) p2p 计算能力的共享 加入对等网络的节点除了可以共享存储能力之外， 还可以共享 c p u 处理能力。 很多时候计算机的 c p u处理闲置状态，p 2 p技术能充分地利用闲置的 c p u ，更加充 分地利用计算机的计算能力。目前已经有了一些基于对等网络的计算能力共享系 统, 比如 s e t i h o m e 5 。s e t i h o m e 是由加州伯克利大学开展的寻找外星生命的研 究计划。 它使用 p 2 p 技术串联所有参与研究计划的闲置计算机来执行复杂的运算， 用来分析行星的无线电信号，寻找宇宙可能存在其他外星文明的证据，这些电脑 每天平均发挥的效能超过了全球造价最高，运算最快的超级电脑。这种计算能力 共享系统还可以用于进行基因数据库检索和密码破解等需要大规模计算能力的应 用。 ( 3 ) p2p 协同工作 协同工作是指多用户之间利用网络中的协同计算平台互相协作来共同完成计 算任务，共享信息资源等。通过采用 p 2 p 技术，个人和组织可以随时采用多种方 式建立在线、非在线的协同应用环境。协同应用一般包括: 实时通信、聊天室、 文件共享、语音通信等基本功能。除了这些基本功能，用户之间还可以共享白板、 协同写作、视频会议等。另外，协同有时候还包括工程人员的协作开发软件。如 g r o o v e 6 , m s n ，q q 和 s k y p e 等通信软件。 ( 4 ) p2p 应用层组播 组播技术（m u l t i c a s t ）是一种针对多点传输和多方协作应用的组通信模型, 有高效的数据传输效率, 是下一代 i n t e r n e t 应用的重要支撑技术。早期的组播技 术研究试图在 i p 层提供组播通信功能, 但 i p 组播的实施涉及到对现有网络基础 设施的调整, 因此大规模应用受到限制。随着 p 2 p 研究的兴起, 基于应用层的组播 技术逐渐受到广泛关注。应用层组播协议将组成员节点自组织成重叠网络 ( o v e r l a y n e t w o r k ) ，在主机节点实现组播功能, 为数据多点并发传输提供服务。 应用层组播是在应用层实现组播功能而不需要网络层的支持，这样就可以避免出 现由于网络层迟迟不能部署对组播的支持而使组播应用难以进行的情况。 ( 5 ) p2p 流媒体技术 由于 p 2 p 网络本身的可扩展性，基于 p 2 p 方式的流媒体技术很好地解决了传 统流媒体带宽不足的问题。单源的 p 2 p 流媒体系统建立在应用层组播技术的基础 之上，由一个发送者向多个接收者发送数据，接收者有且只有一个数据源。服务 器和所有客户节点组织成组播树，组播树的中间节点接受来自父节点组播的媒体 数据，同时将数据以组播的方式传送给子节点。而多源的 p 2 p 流媒体传输系统， 则是由多个发送者以单播的方式同时向一个接收者发送媒体数据。如 p p l i v e 就 impastry：一种基于 pastry 系统的改进模型 4 采用了 p 2 p 技术来传输视频流。 ( 6 ) p2p 搜索技术 p 2 p 搜索技术使用户能够深度搜索文档, 这种搜索无需通过 w e b 服务器， 也可 以不受信息文档格式和宿主设备的限制，可达到传统目录式搜索引擎无可比拟的 深度， 并可有效的跟踪数据的更新速度、 提高访问的有效性及检索的效率 7 。 目前， 集中式搜索引擎 g o o g l e 、雅虎、百度是人们在网络中检索信息资源的主要工具， 但这种集中式的搜索引擎远远无法涵盖所有互联网内的共享内容，而 p 2 p 搜索技 术正好是这种集中式检索的一种良性互补。 1 . 2 本文研究背景和意义 p 2 p 这个古老而又新鲜的技术，充分利用网络中闲置的资源，因其可以为用户 提供高速、高可靠性的服务，吸引了众多高校和研发机构关注的目光，许多应用 都采用了 p 2 p技术，如 n a p s t e r 9 、 g n u t e l l a 1 0 、 b i t t o r r e n t 1 1 、e m u l e 1 2 、j x t a 8 、 g r o o v e 6 、p p l i v e 、s k y p e等, 它的应用从文件共享、计算存储能力共享到协同处 理、服务平台处理以及即时通讯工具几乎无所不在。p 2 p通过将网络中的计算机直 接连接起来，打破了传统的 c / s模式，避开发服务器的瓶颈效应，用户与用户之 间直接相联进行文件交换、对等计算或者协同工作等任务，每个用户既是服务器 又是客户机，它们之间是对等的关系，而不像 c / s中有主从关系。因此，p 2 p系统 由大量具有分布特性、异构特性、匿名特性和高度动态特性的对等体组成。 由于 p 2 p系统具有明显的自治性，且网络中的资源具有动态性，不断有结点 加入和退出，因此，在这样的网络中进行对等体、资源的定位愈显困难和重要。 实际上 p 2 p系统的核心就是解决对等体的定位问题，为了确保对等体有能力去定 位、识别其他对等体，并与之进行通信， p 2 p系统需要健壮、高效的定位机制。 目前，p 2 p 系统的定位机制有集中方式、广播方式、混合方式及 d h t ( d i s t r i b u t e d h a s h t a b l e分布式哈希表）方式。在集中方式中，采用目录服务器的配置方式在 用户增多时服务器将成为系统的瓶颈和单一故障点；在广播方式中，采用泛洪查 询报文的方法在系统规模扩大时会给网络造成较大的负担，同样不具有可扩展性， 因此网络的规模都被限制在较小的范围内；在混合方式中，目录服务器和泛洪查 询都有可能因为网络的扩大而造成负担；在这几种方式中 d h t方式最为常用，常 见的 c h o r d 1 3 、c a n 1 4 、p a s t r y 1 5 和 t a p e s t r y 1 6 等系统全部基于 d h t方式，d h t技 术的提出更是引发了对等计算研究的热潮。但是 d h t方式的系统往往物理地域性 和覆盖网络节点资源分布存在很大的异构性，普遍都存在寻路延迟大，路由效率 低下的问题。 中南民族大学硕士学位论文 5 因此，无论从学术界还是产业界来说，研究和发展 p 2 p系统都具有重要的意 义，同时现有的各个系统本身又有许多的缺点。如何克服系统的缺点，优化系统 的结构，提高资源定位和路由效率，则是研究界研究的重点和难点。本文侧重对 d h t 进行研究，在 d h t资源定位和路由方面做了大量深入细致的工作，对 p 2 p网络 中资源定位进行了深入的理论分析，并通过对 p a s t r y进行改进，实现了 i m p a s t r y 模型，该模型能有效的改善 p 2 p 网络中资源定位效率。 1 . 3 本文的主要研究内容 目前主流的基于 d h t技术的 p 2 p系统包括以下几种模型，即 c a n 、p a s t r y 、 t a p e s t r y 和 c h o r d 模型。虽然这些模型都具有基于 d h t技术构建的 p 2 p系统的特 点，但是仍存在某些不足。由于物理节点在上述模型中都具有唯一的系统标识， 我们将该系统标识所构成的网络称为覆盖网络，将实际物理节点网络称为物理网 络。在目前的 d h t技术的 p 2 p系统中，覆盖网络与物理网络不一致的问题广泛存 在：覆盖网络相邻的节点在物理网络上不相邻，甚至相距很远，导致节点舍近求 远，造成不必要的时延，耗费大量骨干网网络带宽。 为了解决上述问题，本文在深入研究 p a s t r y模型的基础上，提出一种覆盖网 络节点 i d与物理网络节点 i p具有一致映射关系的模型 i m p a s t r y 系统，使得在物 理网络节点若在 i p上具有物理相邻特性，在映射成覆盖网络节点后，这种物理相 邻的特性仍然能够体现在覆盖网络节点 i d相邻的关系上。因此，在进行覆盖网络 路由时， 根据 p a s t r y的前缀匹配路由协议， 消息总是被传递给节点标识与消息 k e y 的相同前缀位数比当前节点标识与消息 k e y相同前缀位数多一位的节点。由于覆 盖网络节点标识反映了物理网络节点的在 i p相邻程度， i p相邻程度间接反映了物 理节点在地域上的物理相邻程度，因此在一定程度上，根据相近覆盖网络节点的 前缀匹配路由会映射为相近 i p 前缀路由， 反映出覆盖网络和实际物理网络相关性， 从而解决覆盖网络与物理网络的不一致的问题，提高路由效率，减少不必要的时 延，降低骨干网络使用带宽。 文正文部分为 5 章，结构如下： 第 1章：绪论。概述了 p 2 p网络的背景，发展现状和论文研究的背景、意义， 分析了该课题目前存在的问题和将来的发展方向，介绍了论文所作的研究工作和 取得的成果。 第 2章： p 2 p系统的体系结构。阐述了 p 2 p系统的定义、特点和应用。阐述 了 p 2 p系统的关键技术和结构体系，分析了 p 2 p系统资源定位机制的分类和典型 的资源定位机制。 impastry：一种基于 pastry 系统的改进模型 6 第 3章： d h t系统的四种模型研究。深入研究 d h t资源定位机制，探讨基于 d h t 机制的四种模型 c a n 、p a s t r y 、t a p e s t r y 和 c h o r d ，并分析了各种模型的优点 和存在的问题。 第 4章：研究改进型 p a s t r y模型i m p a s t r y 。提出一种覆盖网络节点 i d与 物理网络节点 i p相互映射的关系。它是建立在传统的 p a s t r y模型的基础上，使 得在物理网络节点在 i p相邻上具有物理相邻特性，在映射成覆盖网络节点后，这 种物理相邻的特性仍然能够体现在覆盖网络节点 i d相邻的关系上，从而使得覆盖 网络与物理网络的接近一致，提高路由效率，减少不必要的时延，降低骨干网络 使用带宽。 第 5章：i m p a s t r y 模型的实现与分析。介绍了覆盖网络节点 i d与物理网络节 点 i p 间相互映射的机制，阐述了改进 p a s t r y 模型的结构，并进行理论分析。 最后，在结论中对研究工作进行了总结，并指出了今后研究的重点和方向。 中南民族大学硕士学位论文 7 第 2 章 p 2 p 系统的体系结构 在第 1章中，本文对 p 2 p网络的背景和发展现状进行了简单的研究，本章将 进一步对 p 2 p 系统的体系结构进行分析说明。 2 . 1 p 2 p 的定义 p 2 p （p e e r - t o - p e e r ） ，p e e r在英语里的含义有： “同等的人” 、 “同事” 、 “伙 伴”等。p 2 p实际上是对等体对对等体，它体现的是对等的思想，所有成员间一种 对等的关系，p 2 p 网络也被称为对等网络。 p 2 p 网络中，所有地机器通过互联网直接交互，不用经过任何中间转接点。它 不同于传统的 c / s网络，所有的实体在 p 2 p网络中是平等的关系，没有主从的概 念，改变目前互联网以少数服务器为中心的结构，重返网络分布式非中心化的初 始面貌。它克服了服务器的瓶颈效应，使得机器间的沟通变得更加直接，有利于 提高相互合作的能力。 p 2 p 并不是一个新的概念，在互联网发展的初期，网 络中所有的机器同时具有 客户机和服务器的功能，所有的设备都是通讯的对等体。人们通过各自的网络链 接进行相互访问。随着网络的不断膨胀，由于受到计算机性能的制约，这种初期 的网络模型越来越难以管理和使用，人们发明了叫作搜索引擎和门户网站的事物， 人们通过这类网站提供的链接实现对网络的访问，形成以少数服务器为中心的客 户机/ 服务器（c / s ）模式，从此网络走进了客户机/ 服务器时代。在 c / s模式中， 客户机只是享受服务器提供的服务，而不会向网络提供服务，众多的互联网用户 通过少量的服务器实现对网络的访问，这些服务器可能是 w e b服务器、邮件服务 器等。c / s 模式取得了巨大的成功，但随着应用的逐渐增多，它的问题也逐渐暴露 出来，如可扩展性差、抗故障能力差、服务器需要专人维护、资源利用率低等。 p 2 p 的技术的回归就是为了解决上述问题，它在近几年逐渐回到了人们的视野，在 p 2 p 网络里，每个机器都处于平等的地位，既是服务器又是客户机，可以实现对目 标机器的直接访问，避免了 c / s模式下的一些问题，极大地提高了网络资源的利 用率，可扩展性好，抗故障能力强。 目前, 在学术界、工业界对于 p 2 p没有一个统一的定义，下面列举几个常用的 定义 2 0 ： 定义 1 ：p 2 p是一种互联网络，它允许一组计算机用户使用同一个网络程序相 impastry：一种基于 pastry 系统的改进模型 8 互联系对方，并直接访问对方机器上存储的文件。 定义 2 ：p 2 p网络是一个允许在个人电脑上运行，并通过互联网将本地文件共 享给他人的应用程序。 p 2 p网络允许各个单独的电脑相互连接并共享文件，而不需 要通过中央服务器来参与这个过程。 定义 3 ：p 2 p是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件 资源（处理能力、存储能力、网络连接能力、打印机等） ，这些共享资源需要由网 络提供服务和内容，能被其它对等节点( p e e r ) 直接访问而无需经过中间实体。在 此网络中的参与者既是资源（服务和内容）提供者（s e r v e r ） ，又是资源（服务和 内容）获取者（c l i e n t ） 。 k e i t h w . r o s s 和 d a n r u b e n s t e i n 在文献 1 8 中提到了对 p 2 p系统的 3个基 本定义： ( 1 ) 相比中央服务器而言有明显的自治性。 ( 1 ) 利用网络边缘的资源，如存储/ 计算能力和信息资源。 ( 1 ) 网络边缘的资源处在动态的变化中( 新的资源加入，已有的资源消失) 。 i b m为 p 2 p的定义为：p 2 p系统由若干互联协作的计算机构成，且至少具有如 下特征之一：系统依存于边缘化（非中央式服务器）设备的主动协作，每个成员 直接从其他成员而不是从服务器的参与中受益；系统中成员同时扮演服务器与客 户端的角色；系统应用的用户能够意识到彼此的存在，构成一个虚拟或实际的群 体。 虽然表述方式各有不同，但体现的中心思想却是一致的，都是打破了传统的 c l i e n t / s e r v e r ( c / s ) 模式，每个节点都处于对等的地位，每个节点在同一时刻既 可充当服务器又是客户机，在获得别人服务的同时也为别人提供服务。对此，一 些文献 1 9 里用一个新的词 s e r v e n t 来描述 p 2 p网络中的节点， s e r v - 表示 s e r v e r 服务器的意思，- e n t 表示 c l i e n t 客户机。 2 . 2 p 2 p 的特点 p 2 p 技术将相互协作的机器联接起来，每个对等节点间都可以直接交互，并为 对方提供服务或享受对方提供的服务，避免了以某个机器为中心的模式，将网络 中的内容从网络的中心转移到了网络系统的边缘，是一种完全分布的体系结构， 其特点体现在 2 0 ： 非中心化：即分布式。网络中的资源和服务分散在所有节点上，信息的传输 和服务的实现都直接在节点之间进行，可以无需中间环节和服务器的介入，避免 了 c / s网络中存在的服务器瓶颈问题。p 2 p的非中心化基本特点，带来了其在可扩 展性、健壮性等方面的优势。 中南民族大学硕士学位论文 9 可扩展性：在 c / s结构的网络中，随着用户的增多，服务的需求量增加，服 务器的服务能力却没有变化，因此为每个用户提供服务的能力下降，导致所有用 户的访问均受到影响。在 p 2 p网络中，随着用户的加入，不仅服务的需求增加了， 某个节点获得自己所需的资源后又可以将其获得的资源共享，系统整体的资源和 服务能力也在同步地扩充，因此理论上始终能较容易地满足用户的需要。 健壮性：p 2 p 架构天生具有耐攻击、冗余、高容错的优点。由于资源、服务是 分散在各个节点上，实现冗余，部分节点或网络遭到破坏对其它部分的影响很小， 提高了系统的容错能力。p 2 p网络一般在部分节点失效时能够自动调整系统拓扑， 保持其它节点的连通性。 p 2 p网络通常都是以自组织的方式建立起来的，并允许节 点自由地加入和离开。p 2 p网络还能够根据网络带宽、节点数、负载等变化不断地 做自适应式的调整。 高性能/ 价格比：性能优势是 p 2 p被广泛关注的一个重要原因。随着硬件技术 的发展，个人计算机的计算和存储能力以及网络带宽等性能依照摩尔定理高速增 长，但增加的计算和存储能力并没有得到充分的利用，网络中存在大量闲置的资 源。采用 p 2 p架构可以有效地利用互联网中散布的大量普通节点，将计算任务或 存储资料分布到所有节点上。利用网络中闲置的计算能力或存储空间，达到高性 能计算和海量存储的目的。通过利用网络中的大量空闲资源，可以用更低的成本 提供更高的计算和存储能力。 隐私保护：在 p 2 p网络中，由于信息的传输分散在各节点之间进行而无需经 过某个集中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。此外，目前 解决 i n t e r n e t 隐私问题主要采用中继转发的技术方法，从而将通信的参与者隐藏 在众多的网络实体之中。在传统的一些匿名通信系统中，实现这一机制依赖于某 些中继服务器节点。而在 p 2 p中，所有参与者都可以提供中继转发的功能，因而 大大提高了匿名通讯的灵活性和可靠性，能够为用户提供更好的隐私保护。 负载均衡：p 2 p 网络环境下由于每个节点既是服务器又是客户机，减少了对 传统 c / s结构服务器计算能力、存储能力的要求，同时因为资源分布在多个节点， 更好的实现了整个网络的负载均衡。 2 . 3 p 2 p 系统分类 在 1 . 2中，我们对 p 2 p系统分类进行了概述，这里进行进一步探讨。目前， p 2 p 的分类方式有很多， 没有唯一的分类标准， 本文根据 p 2 p系统拓扑的建立方式， 资源（对象）的定位方式，将 p 2 p 系统分为如下几类： impastry：一种基于 pastry 系统的改进模型 10 2 . 3 . 1 集中方式 通过集中方式进行对象定位的系统，也可称为集中式结构的 p 2 p系统，它并 不是一种纯 p 2 p系统，它采用中央服务器的方式，用中心服务器保存节点的地址 信息和网络中存储的资源等信息。这些信息用于帮助网络中对等节点建立连接。 对等节点将自身能够提供的对象注册到一个或几个集中式的目录服务器中，而不 是将对象本身存放在服务器中，对象仍然存贮在节点。当节点需要某些资源时， 需要向中心服务器提出申请，通过中心服务器获取相关信息。当连接建立成功后， 对等节点直接进行通信，服务器便不再起作用。这种模式在进行资源搜索建立连 接之前，类似于传统的 c / s结构，连接建立后便转换为 p 2 p的工作模式。集中式 结构易于发现网络中的节点，易于对节点、资源的管理，但其缺点同 c / s模式类 似，可扩展性差，系统规模受到中心服务器能力的限制，可靠性差，存在单点失 效的问题。图 2 . 1 简要描述了集中方式的 p 2 p 系统。 图 2.1 集中方式的 p2p 系统 著名的 m p 3共享软件 n a p s t e r采用的就是这种结构，并取得了巨大的成功。 1 9 9 8 年，美国波士顿大学的一年级学生肖恩. 范宁为了方便和室友共享音乐，开发 了一个局域网音乐共享程序。用户安装这个程序后，可以把自己拥有的音乐相关 信息发布到一个目录服务器上。其他用户可以在目录服务器上搜索自己需要下载 的歌曲，找到提供下载这些歌曲的用户，然后就可以直接到对应用户去下载歌曲。 从结构上看，n a p s t e r 整个系统由目录服务器和客户端构成。目录服务器由一个或 一组高性能的服务器承担，主要负责所有活动客户端共享资源的管理，提供资源 查询服务；客户端安装在个人电脑上，可以动态地加入和离开网络。这种集中方 式使得 n a p s t e r容易部署，而且客户端容易开发。同样，n a p e s t e r也存在集中方 式 p 2 p 系统通常所具有的可扩展性差和单点失效问题。 中南民族大学硕士学位论文 11 2 . 3 . 2 广播方式 通过这种方式进行定位的 p 2 p系统一般是采用的无结构的网络拓扑，网络中 没有中心服务器的存在，不存在单点失效问题，网络的拓扑是随机的，网络中的 信息也是完全分布式在存放在网络中的所有对等节点中，节点之间的任何通信及 连接的建立均不用经过服务器。 在这种系统中，对等节点上对象的定位是直接通过相邻接节点广播查找，一 般采用 f l o o d i n g算法，即泛洪法，节点收到请求消息后，将请求消息转发给它知 道的所有节点，从而保证这个消息最终得到某个节点的响应。同时，参与的节点 会记录搜索轨迹，防止环路产生。图 2 . 2 简要地描述了广播方式 p 2 p 系统模型。 图 2.2 广播方式的 p2p 系统模型 当网络规模不断扩大，这种方法会导致网络中的流量急剧增加，容易占用大 量带宽，出现网络拥塞，某些节点可能会出现过载而失效，整个系统的响应时间 也会增长，可能出现断链现象，从而不能有效定位对象。 g n u t e l l a就是采用这种结构的一个文件共享系统，没有索引服务器，是基于 广播方式的 p 2 p系统。g n u t e l l a的协议非常简单，可以分为消息协议和下载协议。 消息协议是 g n u t e l l a 网络节点之间用来相互发现和搜索资源的， 下载协议是两个 节点之间用来传送文件的。 在 g n u t e l l a 网络中， 每个节点既是服务器又是客户机。 当一个节点需要查询消息时，会采用泛洪广播的查询方式，即先把查询消息发送 到自己的直接邻居节点。邻居节点首先查找自己的数据列表，如果发现要查询的 数据，就回送一条确认信息，否则就把这条信息转发给自己的直接邻居节点。同 样， g n u t e l l 也存在广播方式 p 2 p系统通常所具有的可扩展性差和网络易拥塞的问 impastry：一种基于 pastry 系统的改进模型 12 题。 2 . 3 . 2 混合方式 混合定位方式采用前两种的综合的方式，集成了集中式和广播式的优点，采 用这种方式定位的系统一般其拓扑结构也是混合方式。 在这种系统中，按照节点能力（计算能力、内存大小、连接带宽等） ，将分布 的节点划分为超级节点和普通节点，有的系统可能还会将节点分为用户节点、搜 索节点和索引节点。超级节点及与其临近的一些普通节点共同构成一个自治域， 域内普通节点将对象注册到该域的超级节点，也就是说超级节点上存放了系统中 其他节点的信息，对象的定位信息仅在超级节点间转发，定位算法只在超级节点 上运行。在进行对象定位时，请求节点先在所属域内通过超级节点集中式查找， 若查找不充分，再通过该域的超级节点向相邻域的超级节点进行广播式查找。这 样就极为有效地消除了广播方式中使用泛洪机制带来的网络拥塞，搜索迟缓等不 利影响。同时，由于自治域中的超级节点拥有该域内普通节点的信息，这也有利 于对网络局部的管理和控制，从而能够在一定程度上提高整个网络的负载均衡。 图 2 . 3 简要描述了基于混合方式的 p 2 p 模型。 图 2 . 3 混合方式的 p 2 p 模型 虽然基于混合方式的 p 2 p系统结构比以往有了很大程度的改进。然而，由于 超级节点本身的脆弱性也可能导致其自治域中其他节点处于孤立状态。 当前比较流行的流媒体播放软件 p p l i v e就采用了混合式架构，继承和结合了 客户机/ 服务器和 p 2 p架构各自的优势。位于中心的是视频源和服务器，视频源提 供多种视频服务，服务器负责记录当前用户选择的频道。用户收看的节目被分成 中南民族大学硕士学位论文 13 固定长度的数据帧，可以从网络中其他节点处下载，而且每个节点会缓冲一定时 间内的视频数据，以提供给下一个用户。这种结构使得 p p l i v e具有观看人越多， 播放越流畅的特点。但是，p p l i v e也存在混合方式 p 2 p系统通常所具有的超级节 点脆弱性和自治域中节点易孤立的情况。 2 . 3 . 4 d h t方式 在通过 d h t方式，即分布式哈希表（d i s t r i b u t e d h a s h t a b l e ）方式进行定 位的 p 2 p网络中，信息是分布式存储的，网络拓扑并不是随机的，而是遵循某些 预先定义的 d h t规则来建立，并按照全局方式组织，即基于 d h t建立和发现路由， 因此具有一定的结构。它首先将每一个节点分配唯一的标识（i d ） ，同时用关键字 （k e y ） 来表示存储在该节点上的资源信息。 取一个哈希函数， 这个函数可以将 k e y 转换成哈希值 h ( k e y ) 。发布信息的时候就把（k e y , i d ）二元组发布到和 h ( k e y ) 相同或相近标识的节点上去。资源（对象）定位的时候，就可以根据 h ( k e y ) 快速 到标识与之相同或相近的节点上获取二元组（k e y , i d ）, 从而定位对象所在节点。 这种方法避免了中心服务器的瓶颈问题和完全分布式结构下的泛洪查找，通 过分布式哈希函数，将关键字唯一地映射到某个节点，并通过某些路由算法找到 该节点，建立节点与资源间的映射关系。 目前，基于 d h t方式的模型，主要有 u c b e r k e l e y大学研究组提出的 c a n和 t a p e s t r y系统, 麻省理工大学提出的 c h o r d系统, 微软研究院和 r i c e大学提出 p a s t r y 系统。本文将在第 3 章中对 d h t 方式和上述四种模型进行深入探究。 2 . 4 本章小结 本章探讨了 p 2 p系统的基本概念，包括它的定义、特点、应用和关键技术。 由于各种 p 2 p系统所采用的定位与路由机制的不同，大致可以把 p 2 p系统分成集 中方式，广播方式，混合方式与 d h t方式。本章根据各种定位与路由方式的特点 进行分析，总结出各个系统的优势与不足。其中 d h t方式与其他几种系统相比较， 具有定位高效，系统健壮等特点。 impastry：一种基于 pastry 系统的改进模型 14 第 3 章 基于 d h t 的 p 2 p 系统 在第 2章简要分析了 p 2 p系统的分类， 本章将重点研究上述分类中基于的 d h t 定位机制，并对采用 d h t定位机制的 c a n 、p a s t r y 、t a p e s t r y和 c h o r d等 p 2 p系 统进行深入的分析。 3 . 1 基于 d h t 方式的定位机制 目前，d h t分布式哈希表方式被许多 p 2 p网络系统所采用，以解决结构化的分 布式存储问题。其核心思想是将存储对象的特征，即关系字，经过某种哈希运算 后，以得到的哈希值为依据进行对象的存储和定位。在没有服务器的情况下，网 络中的每个客户端负责一小范围的路由，存储这部分路由信息及数据信息，整个 d h t 网络中的节点路由信息和数据信息分布地存储在各节点中， 从而可根据一定的 规则实现整个网络的寻址，进行对象的定位。网络外的某个节点欲进入网络，只 需要要知道任意一个已经连入该网络的节点，即可通过该节点找到更多的节点， 连入网络。d h t技术相当于在现有物理网络的基础上构建了一层网络，这种网络也 被称为覆盖网络。 通常对存储资源（对象）的关键字 k e y进行哈希运算，得到哈希值 h （k e y ） 作为键值，将所有的对象映射到了一个具体的数值范围中。为了进行拓扑管理和 对象定位，这个数值范围一般与节点标识（i d ）为同一数值范围。资源（对象） 将存储在节点 i d与之相等或者相近的节点上。即在覆盖网中，每个节点负责一定 数值范围内的对象索引信息（如对象所在节点的 i p地址等）的存储，这样便将对 象集合分布地存储在所有的节点中。在完成对象信息的结构化存储后，对象的定 位方式也是 p 2 p系统的一个关键问题。进行对象定位首先应该获得该对象关键字 所以应的哈希值，然后是根据哈希值查找对应节点的过程，即根据 d h t进行路由 的过程。 由于 d h t方式具有上述特性，在其上构建的系统具有很好的健壮性和良好的 可扩展性，能以较低系统开销获得较大的系统规模可以自我配置，不需要手工干 预就可以自动把新加入节点合并到系统中能提供简单灵活的接口，可以为多个应 用同时使用。因此，本章将重点分析 c a n 、c h o r d 、t a p e s t r y和 p a s t r y这几种最 为典型的基于 d h t 方式的系统。 中南民族大学硕士学位论文 15 3 . 2 c a n c a n ( c o n t e n t a d d r e s s a b l e n e t w o r k , 内容寻址网络) 是由 u c b e r k e l e y大学研 究组提出来的一种 d h t实现方式。c a n的邻居表大小是固定的，不会随着系统中节 点个数的增加而增加，在这一点 c a n 与以下将要研究的其它几种常用的基于 d h t 方式的系统不同。由于邻居表是固定的，系统维护开销比较小，动态性和扩展性 很强。但其缺点是路由信息少，需要更多跳才能找到目的节点。 3 . 2 . 1 c a n的设计 c a n 的设计基于虚拟的 d维笛卡儿坐标空间， 整个坐标空间动态分配给系统中 所有的节点，每个节点负责维护独立的互不相交的一块区域。c a n中的节点自组织 成一个表示这个虚拟坐标空间的覆盖网络。每个节点要了解并维护相邻区域中节 点的 i p 地址，用这些相邻节点的信息构成自己的路由表。根据这张路由表，c a n 可以在 d 维空间中的任意两点间进行路由。 图 3 . 1 给出了一个 2 维的 0 , 1 0 , 1 的笛卡儿坐标空间划分的五个节点区 域。 虚拟