（无线电物理专业论文）p2p对等网络中资源定位的研究与改进.pdf

摘要 最近几年，p 2 p 技术成为了计算机网络技术研究的热点之一。p 2 p 对等网络的出现打破了传统的c s 架构，对等网络中的每个节点既充 当服务器，为其他节点服务，同时也充当客户机，享用其他节点提供 的服务。p 2 p 对等网络是对现有的c s 架构有效的补充，未来的 i n t e r n e t 必然是c s 技术架构与p 2 p 技术架构并存，各有自己的适 用范围。 p 2 p 系统中的一个核心问题是如何高效的定位到所需要的资源。 目前，p 2 p 对等网络中进行资源定位主要有三种方式：集中目录索引、 泛洪请求模型和d h t 算法。由于d h t 具有健壮性、可扩展性和负载平 衡等优点，所以人们普遍看好d h t 方法。 本文第一部分首先叙述了各种类型的p 2 p 系统，并分析和比较它 们各自的优缺点，第二都分是文章的核心内容，详细地阐述了c h o r d 路由协议：用标准的哈希函数把关键字和节点影射到标识符空间，相 容哈希函数完成关键字到节点的映射。并在此基础上改进了原c h o r d 路由协议，接下来对节点加入和离去的情况作了讨论，并对协议在稳 定的状态下系统的性能作了理论上的分析。最后根据s m a l l w o r l d 原 理提出了改进c h o r d 的设想。 模拟测试表明，修改后的c h o r d 路由协议在平均路径长度和平均 查询延迟方面的性能优于原c h o r d 路由协议。 关键字：p 2 p ，c h o r d ，资源定位，分布式哈希表( d h t ) ，模拟 a b s t r a c t i nr e s e n ty e a r s ，p 2 pt e c h n o l o g yh a sb e c o m eo n eo ft h eis s u e s o ft h ec o m p u t e rn e t w o r k i n gt e c h n o l o g ys t u d y t h ea p p e a r a n c eo f p 2 pn e t w o r kh a sb r o k e nt h et r a d i t i o n e lc ss t r u c t u r ei nt h ep a s t e v e r yn o d ei np 2 pn e t w o r kc a n s e r v ea st h es e r v e rt h a tw o r k s f o rt h eo t h e rn o d e s ，a sw e l l a sac l i e n t ，w h i c hs h a r e st h e s e r v i c e st h a tt h eo t h e rn o d e so f f e r p 2 pn e t w o r kc a ns o l v et h e p r o b le m s ，w h ic ht h ee x is t e n tc s s t r u c t u r ec a n t h o w e v e r ，i n t h ef u t u r e ，c st e c h n o l o g i cs t r u c t u r ea n dp 2 pm u s t e x is t s i m t l l t a n e o u s l y i nt h e i n t e r n e t t h e y c a nb ea p p t i e dt o d i f f e r e n ts i t u a t i o n ac o r ep r o b t e mi np e e r t o p e e rs y s t e m si st h ee f f i c i e n t 1 0 c a t i o no ft h en o d et h a ts t o r e sd e s i r e dr e s o u r c e a tp r e s e n t ， t h e r ea r et h r e ew a y si nt h er e s o u r c eo f1 0 c a t i n gi np 2 ps y s t e m ： c e n t r a li n d e xs e r v e r ，f 1 0 0 d i n gr e q u e s tm o d e la n dd h ta l g e r i t h m s t h ea d v a n t a g e so fd h ta r er o b u s t ，s c a l a b i l i t ya n d1 0 a db a l a n c e e t c m o s to ft h ep e o p l et h i n kt h a tt h ed h ta l g o r i t h mi sag o o d w a y i nt h isp a p e r ，f i r s t l yd i f f e r e n tk i n d so fp 2 ps y s t e ma r e s u m m a r i z e d t h e i ra d v a n t a g e so rs h o r t c o m i n g sa r ea n a l y z e da n d c o m p a r e d s e c o n d l y ，i t ist h ec o r ep a r to ft h ep a p e r ，w h i c h e x p o u n d sc h o r dr o u t i n gp r o t o c e la tg r e a t1 e n g t h c h o r dr o u t i n g p r o t o c o l ：i n n u e n d ot h ek e y sa n dn o d e st o i d e n t i f i e rs p a c eb y u s i n gs t a n d a r dh a s hf u n c t i o na n dk e y sa r em a p p e dt 0n o d e sb y u s i n gc o n s is t e n th a s h i n g ie x p l a i n e dc h o r dr o u t i n gp r o t o c o l i nd e t a i l ，a n dh a si m p r o v e do r i g i n a lc h o r dr o u t i n gp r o t o c 0 1o n t h isb a s iso fc h o r d ，d is c u s s e dt h ei m p a c to fn o d ej o i i s o d l o o k u p sa n dv o l u n t a r yn o d ed e p a r t u r e sa n d s oo n a ls oc h o r d p r o t o c o l sp e r f o r m a n c eisa n a l y z e dint h e o r ya ts t a b i l iz a t i o n f i h a l l y ，ii n t r e d u c et h en e wi d e na b o u tc h o r dp r o t o c 0 1w h ic h isb a s e do ns m a l l w o r l dt h e o r y s i m u l a t i o nt e s t ss h o wt h a tt h en e wp r o t o c 0 1iss u p e r io rt o o r i g i n a lc h a r dr o u t i n gp r o t o c o l a t a v e r a g ep a t h1 e n g t ha n d a v e r a g e1 0 0 k u p1 a t e n c y k e y w o r d ：p 2 p ，c h o r d ，r e s o u r c e1 0 c a t i n g ，d i s t r i h u t e dh a s ht a b l e ( d h t ) ，s i m u l a t i o n h 一 主坐查堂堡圭堂竺堡塞 一 第一章引言 1 1论文选题背景 2 0 世纪7 0 年代i n t e r n e t 的出现初期，由于大多数连接到互联 网上的普通用户受计算机性能、资源等因素的限制，并没有能力提供 网络服务，从而逐步形成了以少数服务器为中心的客户机服务器 ( c 1 ie n t s e r v e r ) 架构，这就导致了资源的流向趋于集中化，大量公 开的资源以s e r v e r 形式在i n t e r n e 上提供，网络应用也多以集中化 方式提供服务，比如：w e b 、f t p 等。在c s 架构下，对客户机的资 源要求非常少，因而可以使用户以非常低廉的成本方便地连接互联 网，推动了i n t e r n e t 的普及与应用。 然而，c s 架构的服务方式存在许多技术弊端。一个最主要的问 题就是资源无法得到充分利用。有统计资料显示，全球s e r v e r 提供 的资源加在一起还不足i n t e r n e t 资源总量的1 。也就是说最多最好 的资源实际上是存在于我们每一个人的p c 中。随着硬件水平的发展， 现在的p c 无论是性能还是功能都已经远远超越了原先对p c 的定义。 许多p c 都具有大容量的存储能力和高速的计算能力。虽然近年来网 络带宽成倍增长，但热门站点仍然不堪重负，而空闲的链路带宽却被 白白浪费掉。利用p 2 p 提供的分布式结构则能有效均衡负载，充分利 用带宽。另一方面，计算机的计算能力按照摩尔定律在飞速增长，但 增加的计算能力并未被充分挖掘，p 2 p 为充分挖掘计算机空闲的计算 能力提供了可能。人们迫切希望能打破s e r v e r 的垄断，在i n t e r n e t 上拥有属于自己的空间。p 2 p 技术正是基于这个目标丽诞生的。 p 2 p 最根本的思想，同时也是它与c s 最显著的区别在于网络中 的节点既可以获取其它节点的资源或服务同时又是资源或服务的提 供者，即兼具c 1 i e n t 和s e r v e r 的双重身份。控制流和数据流都在对 等点之间交互，而没有服务器这个角色。一般p 2 p 网络中每一个节点 所拥有的权利和义务都是对等的，包括通讯、服务和资源消费。而 第一章引言 c s 架构是过去几十年来最流行的网络架构。所有的功能和信息都 集中在服务器上，而客户端都通过直接与服务器相连来传送和接收信 息，所有的控制流和数据流的传输都要经过服务器。表卜l 是p 2 p 与 c s 方式的一些比较。 表1 1p 2 p 与c s 的比较 比较项目p 2 p c s 数据发布好差 数据接收 中 好 数据的互动性 好差 数据的传输速度 好 差 数据的安全性差好 数据更新好差 数据的成本控制好差 数据管理的方便性差好 c l a ys h i r k e y ( t h ea c c e l e r a t o rg r o u p ) 给p 2 p 下的定义是： “p 2 p 是一种利用位于i n t e r n e t 边缘的各种可用资源( 如存储空间、 计算能力、媒体内容) 的应用。访问这些分散的资源，就意味着要在 连接不稳定和i p 地址不可预见的环境里工作，网络上大量的节点工 作在d n s 系统之外，这些分散的资源具有不稳定的连通性和未知的 i p 地址，因此p 2 p 节点不能在使用d n s 来进行访问，并且节点从中 央服务器中获得极大的自主权。”【1 】 国外开展p 2 p 技术研究的组织和机构主要包括大学、著名的i t 公司。大学的研究工作侧重于p 2 p 理论研究，而高新技术公司则侧重 于p 2 p 技术的应用开发和产品化。 国外开展p 2 p 研究较为著名的大学和科研机构主要包括u c b e r k e l e y 、m i t 和a t & t 互联网研究中心( a c i r i ) 。在u c b e r k e l e y 大 学，t a p e s t r y 2 l 项目与p 2 p 技术直接相关；在m i t ，开展了多个与p 2 p 相关的研究项日：c h o r d 3 i ，g r i d 和r o n 。a t & ta c i r i 中心的 c a n ( c o n t e n th d d r e s s a b l en e t w o r k s ) 项目 4 1 独特之处在于采用多维 的标识符空间来实现分布式h a s h 算法。 2 中山大学硕士学位论文 从国外公司对p 2 p 计算的支持力度来看，m i c r o s o f t 公司、s u n 公司和i n t e l 公司投入较大，它们各自成立了p 2 p 研究小组，他们致 力于对对等网络架构和编程的研究。m ic r o s o f t 公司成立了p a s t r y 项目组【”，主要负责p 2 p 计算技术的研究和开发工作。s u n 公司以 j a v a 技术为背景，开展了j x t a 项目【6 】。j x t a 是基于j a v a 的开源p 2 p 平台，任何个人和组织均可以加入该项目。因此，该项目不仅吸引了大 批p 2 p 研究人员和开发人员。而且已经发布了基于j x t a 的即时聊天 软件包。在2 0 0 0 年8 月，i n t e l 公司宣布成立p 2 p 工作组，正式开 展p 2 p 的研究。工作组成立以后，积极与应用开发商合作，开发p 2 p 应用平台。2 0 0 2 年i n t e l 发布了n e t 基础架构之上的 a c c e l e r a t o rk i t ( p 2 p 加速工具包) 和p 2 p 安全a p i 软件包。从而 使得微软n e t 开发人员能够迅速地建立点对点安全w e b 应用程序。 现今网络中也有几款比较流行的p 2 p 系统，如g n u t e l l a 7 l 和 f r e e n e tis 】等，在这些系统中所有的节点都要扮演资源查找和下载的 角色。另外如集中式p 2 p 系统n a p s t e r l 9 1 ，它的搜索功能在集中的目 录服务器中实现，而下载仍然是以点对点的方式进行。更进步的还 有基于超级点的网络架构系统k a z a a | 1 0 】( 现今最流行的文件共享系统 之一) 。美国旧金山的软件工程师布莱姆科亨( b r a mc o h e n ) 开发 的b t ( b i t t o r r e n t ，比特涡流) 系统在2 0 0 3 年一经推出就产生了很 大影响。有人预言b t 将领导p 2 p 资源共享的新潮流。 1 2论文的内容与组织结构 本文主要对c h o r d 路由算法做了详细的分析与研究，并在此基础 上对c h o r d 路由算法进行了改进，在结构上本文共分为下面的五个章 节，各个章节的内容组织如下： 第一章介绍p 2 p 的技术背景和当前国内外的研究现状。 第二章简单介绍了p 2 p 的特点、应用及面临的问题，并重点阐述 了各种类型的p 2 p 系统。 第三章详细讲述了c h o r d 协议的相关内容，包括关键字的查找、 3 第一章引言 节点的加入和稳定、节点加入对查询的影响等各方面的内容，并提出 了对c h o r d 路由协议的改进方法。 第四章利用m i t 的p 2 p s i m 模拟器实现了本文提出了改进方法的 性能模拟。并给出了实验结果和评价。 第五章对全文进行了总结，并叙述了论文需要进行的下一步工 作。 4 一一一 生坐查兰堡主兰竺堡壅 第二章p 2 p 简介 2 1p 2 p 技术的概述 2 1 1p 2 p 技术的特点 与其它网络模型相比，p 2 p 具有以下特点 1 分散化( d e c e n t r a liz a t i o n ) 网络中的资源和服务分散在所有节点上，信息的传输和服务的实 现都直接在节点之间进行，可以无需中间环节和服务器的介入，避免 了可熊的瓶颈。即使是在集中式p 2 p 系统中，虽然在查找资源、定位 服务或安全检验等环节需要集中式服务器的参与，但主要的信息交换 最终仍然在节点中间直接完成。这样就大大降低了对集中式服务器的 资源和性能要求。 分散化是p 2 p 的基本特点，由此带来了其在可扩展性、健壮性等 方面的优势。 2 可扩展性 在传统的c s 架构中，系统能够容纳的用户数量和提供服务的能 力主要受服务器的资源限制。为支持互联网上的大量用户，需要在服 务器端使用大量高性能的计算机，并要求网络带宽足够大。在此架构 下，集中式服务器之间的同步、协同等处理产生了大量的开销，限制 了系统规模的扩展。 而在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了，系 统整体的资源和服务能力也得到了扩充，始终能较容易地满足用户的 需要。即使在诸如n a p s t e r 等集中式p 2 p 系统架构中，由于大部分处 第三章c h o r d 协议的分析与改进 理直接在节点之间进行，大大减少了对服务器的依赖，因而能够方便 地扩展到数百万个以上的用户。而对于其他p 2 p 系统架构来说，整个 体系是全分布的，不存在瓶颈。理论上其可扩展性几乎可以认为是无 限的。 p 2 p 可扩展性好这一优点已经在一些得到应用的实例中得以证 明，如n a p s t e r ，g n u t e l l a ，f r e e i e t 等。 3 健壮性 在互联网上随时可能出现异常情况，网络中断、网络拥塞、节点 失效等各种异常事件都会给系统的稳定性和服务持续性带来影响。在 传统的集中式服务模式中，集中式服务器成为整个系统的要害所在， 一旦发生异常就会影响到所有用户的使用。而p 2 p 架构则具有耐攻 击、高容错的优点。由于服务是分散在各个节点之间进行的，部分节 点或网络遭到破坏对其它部分的影响很小。而且p 2 p 模型一般在部分 节点失效时能够自动调整整体拓扑，保持其它节点的连通性。事实上， p 2 p 网络通常都是以自组织的方式建立起来的，并允许节点自由地加 入和离开。一些p 2 p 模型还能够根据网络带宽、节点数、负载等变化 不断地做自适应式的调整。 4 隐私性 随着互联网的普及和计算存储能力飞速增长，收集隐私信息正 在变得越来越容易。隐私的保护作为网络安全性的一个方面越来越被 大家所关注。目前的i n t e r n e t 通用协议不支持隐藏通信端地址的功 能。攻击者可以监控用户的流量特征，获得i p 地址。甚至可以使用 一些跟踪软件直接从i p 地址追踪到个人用户。 在p 2 p 网络中，由于信息的传输分散在各节点之闯进行而无需经 过某个集中环节，用户的隐私信息被窃听和泄漏韵可能性大大缩小 6 中山大学硕士学位论文 此外，目前解决i n t e r n e t 隐私问题主要采用中继转发的技术方法， 从而将通信的参与者隐藏在众多的网络实体之中。在传统的一些匿名 通信系统中，实现这一机制依赖于某些中继服务器节点。而在p 2 p 中， 所有参与者都可以提供中继转发的功能，因而大大提高了匿名通讯的 灵活性和可靠性，能够为用户提供更好的隐私保护。 5 高性能 性能优势是p 2 p 被广泛关注的一个重要原因。随着硬件技术的发 展，个人计算机的计算和存储能力以及网络带宽等性能依照摩尔定理 高速增长。而在目前的互联网上，这些普通用户拥有的节点只是以客 户机的方式连接到网络中，仅仅作为信息和服务的消费者，游离于互 联网的边缘。对于这些边际节点的能力来说，存在极大的浪费。 采用p 2 p 架构可以有效地利用互联网中散布的大量普通节点，将 计算任务或存储资料分布到所有节点上。利用其中闲置的计算能力或 存储空间，达到高性能计算和海薰存储的目的。这与当前高性能计算 机中普遍采用的分布式计算的思想是一致的。通过利用网络中的大量 空闲资源，可以用更低的成本提供更高的计算和存储能力。 2 1 2 p 2 p 的应用 p 2 p 的特点充分显示出了其强大的技术优势。从应用角度来看， 目前p 2 p 技术研究主要涉及到以下几个领域；文件交换、对等计算、 搜索引擎、协同工作、实时通信。 1 文件交换 在传统的w e b 方式中，要实现文件交换离不开服务器的参与，通 过将文件上传到某个特定的网站，用户再到该网站上搜索需要的文 7 第三章c h o r d 协议的分析与改进 件，然后下载，这种方式对用户而言非常不方便。p 2 p 技术使在 i n t e r n e t 上的任意两台计算机之间直接共享文档、多媒体和其它文 件成为了可能，利用p 2 p 技术进行文件交换时，客户不再需要将文件 先传到服务器，而只需在自己的硬盘上开辟共享区，就可以在客户间 进行交换。n a p s t e r 就是一个很好的文件交换软件，它提供给用户在 互联网上共享u p 3 音乐文件的p 2 p 应用，n a p s t e r 把音乐文件存储在 客户节点上，中心服务器上存储的仅仅是文件的索引信息，用户之间 可以直接共享、传输音乐文件而不需要通过中心索引服务器。 2 对等计算 由于般的家庭计算机很多都只是用来处理文字，上网浏览等应 用，真正做的事情很少，为了能充分利用这些闲置的中央处理器、内 存以及磁盘空间等，科学家提出了对等计算。采用p 2 p 技术的对等计 算，就是把网络中的众多计算机暂时不用的计算能力连结起来，使用 积累的能力执行超级计算枫的任务，通过众多计算机来完成超级计算 机的功能。在对等计算中，大型的计算任务被分解成很多个小的工作 单元，分别分配给网络中的节点独立执行。当节点完成了工作之后就 将结果传送给服务器，然后进行下一个工作单元。其典型代表是 s e t i o h o m e 系统，s e t i h o m e 是旨在利用连入i n t e r n e t 的成千上万台 计算机的闲置能力搜寻外星文明的巨大试验。它可以将连入i n t e r n e t 的计算机在闲置时的处理运算能力整合起来，形成一个超级计算机， 并且通过这个超级计算机对由巨型hr e c i b o 望远镜收集的来自外太 空的无线电磁波数据进行分析。据统计，在不到两年的时间里，这种 计算方法已经完成了单台计算机3 4 5 0 0 0 年的计算量。 3 搜索引擎 p 2 p 文件共享首先要解决文件定位的问题。但是无论是现在的目 b 生生查兰堡圭堂焦丝皇 一 录式搜索引擎还是l y c o s 和国内百度的智能搜索引擎，其搜索都要依 靠服务器来完成，而利用p 2 p 搜索技术的搜索引擎，则完全不需要服 务器，就能使用户能够深度搜索文档，可达到传统目录式搜索引擎( 只 能搜索到2 0 一3 0 的网络资源) 无可比拟的深度( 理论上将包括 网络上的所有开放的信息资源) 。以g n u t e l l a 进行的搜索为例：一台 p c 上的g n u t e l l a 软件可将用户的搜索请求同时发给网络上另外多台 p c 。如果搜索请求未得到满足，这多台p c 中的每一台都会把该搜索 请求转发给另外多台p c 。理论上，搜索范围将在几秒钟内以几何级 数增长，几分钟内就可搜遍几百万台p c 上的信息资源。当然实际环 境中还需要考虑网络带宽以及路由优化方面的问题。p 2 p 为互联网的 信息搜索提供了一个全新的解决之道。 4 协同工作 p 2 p 技术一旦用于协同工作，可以使企业内部分散的各部门之间、 企业和关键客户以及合作伙伴之间，建立起安全的网上工作和联系得 环境。g r o o v e 是协作p 2 p 计算的一个例子，它是一个平台，软件开 发商可以剩甩该平台构建协作环境。g r o o v e 演示了一种p 2 p 的“协 作空间”，当用户及其小组成员在p c 上安装了g r o o v e 后，该小组就 创建了一个“虚拟空间”。在这个虚拟空间中，用户可以实时地与小 组成员交互并进行项目协作。除此以外，g r o o v e 还提供了添加新工 具和管理小组的规范。 5 实时通信 目前的实时通信技术一般采用一个中心服务器控制着用户的认 证等基本的信息，节点之闻直接进行数据通信。i c o 、0 i c q 、a i m 等 是典型的实时通信系统。j a b b e r 是下一代的实时通信平台，在该平 台上可以创建许多应用程序，包括那些人与人，或人与应用程序通信 9 第三章c h o r d 协议的分析与改进 的程序，或者是应用程序之间的通信程序。 2 2 p 2 p 网络的分类 目前p 2 p 系统基本上可以分成三种类型：集中式( c e n t r a l iz e d ) 、 完全分散式且非结构化( d e c e n t r a l iz e da n du n s t r u c t u r e d ) 以及完 全分散式且结构化( d e c e n t r a l i z e da n ds t r u c t u r e d ) ，根据l ve t a 1 i “】的定义，结构化必须符合以下两点需求： i 网络的拓扑被严谨的控制而形成某种特定结构的覆盖网络， 覆盖网络是架构在网络层之上的虚拟拓扑，且节点与节点在覆盖网络 的距离为一个节点的距离，但在实际的网络中实际的距离是多个节 点。 2 资源的位置信息并不是随便放置在任一个节点上，而是经过 计算后决定放置资源信息的节点位鼍。 如果满足其中一个需求称之为松散结构化( l o o s e ly s t r u c t u r e d ) p 2 p 系统，如果完全满足以上两点需求的p 2 p 系统称之 为严谨结构化( h i g h l ys t r u c t u r e d ) p 2 p 系统。以下根据分类方式的 不同分别介绍每种类型的p 2 p 系统。 2 2 1 集中式p 2 p 系统 集中式p 2 p 系统最具代表性的例子是n a p s t e r ，它实质上并非是 纯粹的p 2 p 系统。在n a p s t e r 中，一群高性能的中央服务器保存着 网络中所有活动对等机地址信息及其共享资源的目录信息。每个对等 机和其中一个服务器保持连接。当对等机共享资源时，需向索引服务 器进行资源注册。当需要查询某个文件时，对等机会向一台中央服务 器发出文件查询请求。中央服务器进行相应的检索和查询后，会返回 符合查询要求的对等机地址信息列表。查询发起对等机接收到应答 后，会根据网络流量和延迟等信息进行选择，和合适的对等机直接建 立连接，并开始文件传输，文件传输的过程不再需要索引服务器的参 主些奎堂堡主堂垡堡塞 与1 12 1 。n a p s t e r 网络的文件查询机制如图2 - 1 所示： p e e r qq u e r y s e e rrr e s p o n s e dd o w n l o a d 图2 - 1n a p s t e r 网络的信息查询路由机制 由于文件目录被集中管理，所以使得发现和更新节点的信息变得 容易，但是因此也导致了单点故障的问题，比如说，如果某个服务器 失效，在这台服务器上登记的节点就不能和其它节点进行连接。同时 这种模式还存在了可扩展性差、带宽瓶颈等c s 架构中常见的问题。 对小型网络而言，用集中目录的模型在管理和控制方面占一定优势， 但对于大型网络并不适合。 2 2 2分散式且无结构的p 2 p 系统 g n u t e l l a 是一个分散式且无结构的p 2 p 文件共享系统，它和 n a p s t e r 最大的区别在于g n u t e l l a 是纯粹的p 2 p 系统，没有类似 n a p s t e r 韵中央服务器，通过与相邻对等机之润的连接遍历整个网 络。g n u t e l l a 协议定义了网络中对等机间通信的方式，它是工作于 t c p 协议之上的应用层协议。该协议包括在对等机间通信描述符集( 服 务原语集) 和相应的通信规则集。对等机间通信描述符集如表2 1 所 示： 第三章c h o r d 协议的分析与改进 表2 - 1g n u t l l a 协议通信描述符 描述符 描述 p i n g用于在g n u t e l l a 网络中主动发现对等机。一个收到 p i n g 描述符的对等机会向发送方响应一个或多个 p o n g 描述符。 p o n g用于对p i n g 响应的描述符。它包括了一个相连的 g n u t e l l a 对等机的地址和有关该节点能提供给网络 共享的信息。 q u e r y是搜索g n u t e l l a 分布式网络共享信息的主要机制， 一个收到q u e r y 描述符的对等机，如果其本地共享信 息与q u e r y 搜索的内容匹配，将会响应一个q u e r y h i t 给q u e r y 的发起者。 q u e r y h i t用于对q u e r y 响应的描述符。它包括匹配q u e r y 搜索 数据的对等机i p 地址及端口号、传输速度及结果集、 对等机标识等。 p u s h 提供一种机制允许一台处于防火墙后的对等机向网 络提供基于文件的数据 g n u t e l l a 网络节点的信息查询的原理如下： 通过“主机缓存服务”。某对等机首先找到一台活动对等机并与 之相连，从而将自己接入g n u t e l l a 网络。接着，该新对等机使用p i n g 描述符来主动探查网络中的其它对等机，找到与之相邻的对等机节 点。收到p i n g 描述符的对等机顺原路响应一个p o n g 描述符，它将包 含其地址和共享于网络的数据的相关信息，这样新对等机即可确定自 己的相邻对等机，同时。又会用同样的方法继续路由转发该p i n g 描 述符，直至p i n g 包的t t l 属性值递减为0 。接下来，为了查找某个 文件，首先向与之相邻的所有活动对等点发送一个查询描述符q u e r y 。 其他对等机在接收到该查询描述符后，检查本地是否有符合查询请求 的文件内容，如果有，则按查询描述符的发送路径返回一个查询响应 中山大学硕士学位论文 描述符q u e r y f l i t 。无论本地是否存在符合查询请求的文件内容，其 他对等机都会将该查询包通过扩散方式继续在网络中传递，直至查询 包中t t l 属性值递减为0 时停止继续转发。为了减少广播带来的网络 带宽浪费，一般将广播传递限制在7 8 跳以内，即如果请求在经过 有限的循环广播之后，仍不能得到响应，则发送请求的节点将得到一 个错误信息。一旦定位了响应它查询共享文件的对等机之后，就与响 应对等机建立t c p 连接，通过h t t p 协议从响应对等机中下载自己查 询的文件。文件的传输不再经过g n u t e l l a 网络进行。1 1 3 】 g n u t e l l a 网络的信息查询路由机制如图2 2 所示。节点搜索路 由机制与之类似。 p e e rr r e 8 p o n s e dd o w n l o a d qq u e f y c m u t e l | a 图2 2g n u t e l l a 网络的的信息查询路由机制 g n u t e l l a 网络也存在很多弊端，主要表现在以下方面：随着网 络规模的扩大，通过扩散方式定位对等点及查询信息的方法将造成网 络流量急剧增加，从而导致网络拥塞。因此，网络的可扩展性不好， 对于大型网络也不适合。但是，如果在该网络中存在一些所谓的超级 实体( 即该实体拥有大量的资源信息) ，则可以显著减少带宽的浪费。 另外，其安全性也不高，易遭受恶意攻击，如攻击者发送垃圾查询信 息，会造成网络拥塞等。 1 4 1 2 2 3分散式且松散结构化的p 2 p 系统 此类型最具代表性的p 2 p 系统是f r e e n e t l 8 】h ”。f r e e n e t 的研究 第三章c h o r d 协议的分析与改进 始予1 9 9 9 年，f a nc l a r c k 在e d i n b u r g h 大学设计和开发了f r e e n e t 系统，其主要目的是充分利用匿名通信系统的特点，即用户可以匿名 访问系统中共享的文件。同样，如果用户需要在本地存储文件，则其身 份也不可识别。 f r e e n e t 是一种基于关键字路由的p 2 p 系统，它将每一个被共享 的资源都使用单向的哈希函数来产生唯一的资源标识符，如图2 3 所 示，节点a 共享的资源标识符为3 7 5 ，并且每个节点会建立资源标识 符和节点地址的映射表，当节点a 要查询资源标识符为3 4 2 的资源的 时候，节点a 会先使用产生的标识符查询自己所拥有的资源是否存 在，如果找不到则寻找最接近标识符的那个对应的记录。节点a 寻找 到最接近的记录为5 2 7 一b ，因此节点a 会先设定t t l 值后再将查询信 息传到节点b ，节点b 也执行相同的步骤一直找到资源标识符3 4 2 的 资源位于节点c ，这时节点c 会将资源依照查询所建立的路由路径回 传给节点a ，并且将资源备份到回传路径上的每一个节点。如果超过 t t l 值还没有找到资源则会回传失败信息，并且等待执行下一次查询。 - _ - _ _ 一 r 哪矾甜2 图2 - 3f r e e n e t 的系统架构图 f r e e n e t 的方法有点类似于深度优先搜寻的查询方式，所以能够 解决传输过载的问题。不过f r e e n e t 的方式无法在还没有查询时就知 道该往哪个节点查询资源，而当节点数量越多，查询的时间会越长。 1 4 生坐查堂塑主堂堡堡皇 一 2 2 4分散式且严谨结构化的p 2 p 系统 由于非结构化系统中的随机搜索造成的不可扩展性，大量的研究 集中在如何构造一个高度结构化的系统。在这些结构化的系统中， “叠盘”拓扑被严格控制，文件( 或者文件指针) 存放在确定的位置 上。系统提供从文件标识符到存放该文件的节点标识的映射服务，然 后把查询请求路由到该节点。通过以上方法系统提供了一个可扩展的 方案实现了文件的“精确匹配”查询。目前人们把研究的重点放在了 如何有效地查找信息上，最新的成果都是基于d h t ( d is t r i h u t e dh a s h t a b le ) 【”】的分布式查找和路由算法。 1 、内容访问网络( c o n t e n t h d d r e s s a b l en e t w o r k ，c a n ) 协议 伯克立和a t & t 设计的c h n 的独特之处就在于采用了多维的坐标 空间来实现分布式的哈希算法。c a n 类似于一张大散列表，它由许多 单独的节点组成。每个c h n 节点保存散列表的一部分，称为一个区域 ( z o n e ) 。此外，每个节点还保存了表中少量的邻接区的信息。对每个 特定关键字的插入( 或者查找、删除) 请求由中间的c a n 节点进行路 由直到到达包括该关键字的c a n 节点所在的区域。c a n 基于虚拟的d 维笛卡儿坐标空间实现其数据组织和查找功能。这个坐标空间是完全 逻辑的，与物理的对等系统是没有关系的。这个完整的坐标空问是被 所有在系统中的节点动态的分割的，以至于在整个坐标空间中的每个 节点都拥有它自己的、不同于其它节点的区域。例如，图2 4 ( a ) 显示了一个2 维的7 o ，1 x o ，1 坐标空间，这个空间被6 个节点 分为了6 个区域。 第三章c h o r d 协议的分析与改进 ( o ，1 ) ( 1 ，1 )( 0 ，1 ) ( 1 ，1 ) ( 0 ，05 ，0 5 ，1 ) ( o 5 , o 5 1 1 ) ( 0 暴2 垒箜，q 勤 ( o 0 o 5 ，0 5 ) ( o ! ! 1 0 ( 07 5 ，0 ， 1 , 05 、 17 5 o 2 5 ) ( 0 ，0 ) r r f j j ? ( 1 o )( o o ) ( b ) 2 维笛卡儿空间的区域划分 c a n 网络的查询信息的路由机制 图2 4 虚拟坐标空间采用下面的方法保存( 关键字。值) 对；当保存( k l ， v 1 ) 时，使用一个统一的哈希函数把关键字k 1 确定地映射成坐标空 间中的某一个节点。那么这个值将被保存在该点所在区域的节点中。 当需要查询关键字k l 对应的值时，任何节点都可以使用同样的哈希 函数找到k l 对应的该节点，然后从该点对应的节点取出相应的值。 如果此节点不是属予请求节点区域，或者是不属于请求节点的直接的 邻居，c a n 将负责将此查询请求转发到对应的节点。图2 - 4 ( b ) 显示 了这个路由过程。 一个c a n 节点维护了一个路由表，这个表保存了在坐标空间中的 这个节点所有直接邻居节点的i p 地址和虚拟的坐标空闯。在一个d 维的坐标空间中，如果两个节点的d l 维相同，有维不同，那么这 两个节点相邻。根据当地的邻居状态足以在空间中的两个任意的节点 间进行路由。 如果一个d 维空间划分成i 1 个相等的区域，那么平均路由长度是 ( d 4 x n “) ，每个节点只需要维护2 d 的邻接节点信息。这个结果表明 中山大学硕士学位论文 c a n 的可扩展性很好，节点数增加时每个节点维护的信息不变，而且 路由长度只是以0 ( n “。) 的数量级增长。我们可以看到，在坐标空间中， 两点之间可以有许多条不同的路径。因此，单个节点的失效对c a n 基 本上没有太大的影响。遇到失效节点时，c a n 节点会自动沿着其他的 路径进行路由。 c a n 设计完全是分布式的，它不需要任何形式的中央控制点。c a n 具有很好的可扩展性，节点只需要维护少量的控制状态而且状态数量 独立于系统中的节点数量。 2 、p a s t r y 协议1 5 1 p a s t r y 是微软研究院提出的可扩展的分布式对象定位和路由协 议，可用于构建大规模的p 2 p 系统。在p a s t r y 中，每个节点分配一个 1 2 8 位的节点标识符号( n o d e i d ) ，所有的节点标识符形成了个环 形的n o d e i d 空间，范围从0 到2 1 2 81 ，节点加入系统时通过哈希节 点i p 地址在1 2 8 位n o d e i d 空间中随机分配。 p a s t r y 提供了下面的功能。p a s t r y 网络中的每个节点都有一个 唯一的节点号( n o d e l d ) 。当给定条消息和一个关键字时，p a s t r y 节点将会把这条消息路由到在当前所有的p a s t r y 节点中n o d e i d 和关 键字最接近韵那个节点。路由过程的复杂度是0 ( 1 0 9 n ) ，这里n 表 示网络中p a s t r y 节点的总数。p a s t r y 考虑了网络的位置信息，它的 目标是使消息传遴的距离最短。距离采用类似于i p 路由的h o p 数的 标量距离度量。每个p a s t r y 节点记录在节点空间中和它直接相邻的 邻居节点，当新节点加入、原有节点失效和恢复时通知上层应用。由 于节点号是随机分配的，那么在节点空间中相邻的节点很可能在地理 位置上是分散的，或者根本就属于不同的组织。应用可以利用这一点， 因为p a s t r y 可以把关键字路由到和它最接近的k 个节点的任何一个， p a s t r y 采用了启发式算法可以使关键字首先路由到在节点空问中和 消息产生的节点距离最近的包括查找关键字的节点。 1 7 第三章c h o r d 协议的分析与改进 p a s t r y 系统是由独立的p a s t r y 节点组成的自组织的重叠网络 ( o v e r l a vn e t w o r k ) ，每个节点都可以路由客户请求并和应用程序 ( 可以是多个) 的本地实例进行交互。任何一台连接到i n t e r n e t 的 计算机只要运行p a s t r y 节点软件就可以称为p a s t r y 节点，当然，它 需要满足应用定义的安全策略。 p a s t r y 系统中的每个节点都被分配一个l2 8 位的节点号。节点 号用于在节点空间中标识节点的位置。节点号是在节点加入系统时随 机分配的。分配策略是在节点空间中均匀分布。节点号可以通过计算 节点公钥或者i p 地址的啥希函数值来获得。由于采用了均匀分布， 因此节点标识相邻的节点处于不同的地理位置的概率很大。 假定网络由n 个节点组成，p a s t r y 可以把个给定的关键字路 由到从标识符来看最接近的节点，在正常操作条件下，路由的步数小 于l o g 。n 的上取整t 这里b 是一个配置参数，典型取值是4 。即使同 时发生节点失效的情况，也可以保证关键字送达目标节点，除非相邻 节点中有ll 2 的下取整个节点同时失效。同样，这里fl 1 是配置参 数，通常取值是1 6 或者3 2 。 为了进行路由，我们把节点号和关键字表示为一串以2 6 为基的 数。p a s t r y 把消息路由到节点号从数值上最接近关键字的节点。具 体过程如下：在每个路由步骤中，当前节点将把消息路由给节点号和 消息关键字的共闻前缀长度至少比当前值长一个数位( 也就是b 个二 进制位) 的节点。如果不存在这样的节点消息将传递给前缀长度相 同但是节点号数值更接近关键字的节点。为了支持这样的路由过程， 每个节点必须维护一定的路由状态。 每个p a s t r y 节点都需要维护一张路由表，个邻居节点集合和 一个叶子节点集合。路由表由l o g n 的上取整行组成，每彳亍包括2 l 1 个表项。第n 行的2 b 一1 个表项分别指向前n 个数位和当前节点的前n 个数位相同，而第1 1 + 1 个数位取遍2 b - l 的可能的值( 要除掉当前节 点第n + l 的值) 。b 的大小的选择反映了在路由表大小和任意两点问 拈 中山大学硕士学位论文 路由需要的最大的步数之间的折衷。当b 取4 ，而网络中有1 0 6 个节点 时，每个节点的