（计算机软件与理论专业论文）对等网络中pastry网络模型的研究.pdf

、 、 对等网络中p a s t r y 网络模型的研究 摘要 p 2 p f p e e r - t o p e e r ) 是一种分布式计算模式，通过节点之间的直接交换实现资 源和服务的共享。p 2 p 网络分为非结构化p 2 p 网络、结构化p 2 p 网络和松散结构 化p 2 p 网络。由于非结构化p 2 p 网络和松散化p 2 p 网络中节点自由连接的随意 性，使得数据查询必须依靠洪泛来完成，网络开销大，可扩展性差。于是，扩展 性强的结构化p 2 p 网络成为现在研究的2 个热点。 但是，现存的结构化p 2 p 网络算法的节点问通信效率及带宽利用率并不高， 而且每个节点都要花费很大的开销来存储路由表及其他表项，节点负担重。为了 解决这些问题，在分析前人工作的基础上，本文提出了。一个s m a r t p a 算法，该算 法结合了p a s t r y 和全连通结构化覆盖网算法，各节点根据自身的带宽能力决定 其路由表大小，充分利用所有节点的可用带宽，可以运行于任何环境，不受限于 系统规模的大小、结点能力的强弱、强弱结点的比例、节点出入的频率，并通过 动态调节保证路由效率，适用于各种广域分布式系统。经过实验表明，该算法使 得网络中节点间通信效率及带宽利用率比其他都高，而且节点开销较小。 关键词：p 2 p 系统；结构化覆盖网：p a s t r y ；路由算法 对等网络中p 田嗣络模型的研究 a b s t r a c t p 2 p ( p e e r t o - p e e r ) i so n ek i n do fd i s t r i b u t e dc a l c u l a t i o nm o d e l ，w h i c hr e a l i z e s s h a r i n go fr c s o u r c ca i l d s e r v i c ct h m u g he x c h a n 西n g 眦o n gn o d e sd i r e c t i y p 2 p i n c l u d e su n s t j l l c t u r e dp 2 p ，s t 】1 l c t i l r e dp 2 pa n d 心l a x e ds t m c t u r e dp 2 p i nu n s t m c t u r e d p 2 p 柚dr e l a x c ds t n l c t u r e dp 2 p ，n o d e s n n e c te a c ho t h e ra t 啪d o m ，w h i c hl e a d st o d a t aq u e r yt ob ef i n i s h e dd e p e n d i n go nn o o d i n g ，r e s u l t si nh i 曲c o s ti nt h en e t w o r k a n dl o ws c a l a b i l i t y s os t n i c t u r e dp 2 pw i t hh i 曲s c a l a b i l 王t yb e c o m e sah o t s p o to f r e s e a r c hn o w b u tc o m m u i c a t i o ne f f i c j e n c ya l l du t i l i z er a t eo fb 锄d w i d t h ，a m o n gc u n n t s t m c t u r c dp 2 pr o u t i n ga i g o 血l l i i l s ，a f cn o t h i 曲，卸di ts p c n d se v e r yn o d eh i 班c o s t s t o r i n gr o u t et a b l ea n do t h e ri t e m s ，a n de v e r yn o d eh a sh e a v yb u r d e n i no r d e rt o r e s o l v et h e s ep m b l 咖s ，t h et h e s i sp r e s e n t ss m a n p a ， b a s i n go nr c s e a r c hb e f o r e t h e a l g o r i t h mc o m b i n e sp a s t r ya l l df i l l l _ j o j n e ds t m c t u r e do v e d a yn e t w o f ka l g o r i t l m 1 t m a k e su s eo fu s a b l eb a n “i d t ho fe v e r yn o d e ，c a nb ed e p l o y e di na n ye n v i r o n m e n t s ， n o tm a t t e rw h a tt h es y s t e ms i z ei s ，h o wd y n a m i ct h en o d e sa r e ，a n dw h a tt h e n o d e - c a p a c i t yd i s t 抽u t i o i sl i k e i te n s u r c sr o u t e e f f i c i e n c yt h o u g hd y n 蜘i c a d j u s t m e n t ，a n dc a nb eu s ei na nk i n d so fw i d ea r e ad i s t r i b u t e ds y s t e m t h r o u 曲 e x p c r i m e n t s ，w ec a i ls e et h a ts m a n p am a l 【e st h a tc o m m u n i c a t i o ne 艏c i e n c ya m o n g n o d e si nt h en e t 、v o r ka du t i l i z er a t eo fb a i l d w i d t ha f eh 蟾h e rt h a no t h e ra l g o r i t h m s ， a n di th a sl o wn o d ec o s t k e yw o r d s ：p e e r - t o p e e rs y s t e m ；s t m c t l l r e do v e r l a yn e t w o r k ；p a s t r y ；r o u t i n g a l g o r i t h m 郑重声明 本人的学位论文是在导师指导下独立撰写并完成的，学位论文没有剽 窃、抄袭等违反学术道德、学术规范的侵权行为，否则，本人愿意承担由 此产生的一切法律责任和法律后果，特此郑莺声明。 学位论文作者( 签名) ：l 司饮 p f 年月t 日 对等网络中p a s l i y 网络模型的研究 1 1 研究背景 第一章绪论 随着网络技术的飞速发展和网络规模的不断扩大，接入网络的主机增加，可 用资源丰富，然而目前的互联网仍然是以c s 模式为主，尤其是w e b 技术的发展 使得许多w e b 服务器成为信息的主要提供源，整个i n t e r n e t 系统依附于这些少 量的服务器节点，而大量的个人主机中的资源却成了网络中的信息孤岛，无法得 到充分利用，能否发挥这些闲散资源的使用效率( 或者作用) 构成了人们关注 p 2 p 的理由。 p 2 p 是p e e rt op e e r 的缩写，是指通过使用分布资源，借助于分稚计算技 术来完成关键任务的系统和应用的总称。这里的分布式资源包括计算能力、数据 ( 包括存储介质和内容) 、网络带宽和其它资源( 如计算机、人力资源等) ：分布 计算包括算法、数据、元数据等，或者是三者总体；关键任务包括分布计算、数 据( 或内容) 共享、通信与协作，或者是平台服务等。 p 2 p 技术的主要特征是弱化服务器作用，甚至取消服务器，使分布式系统中 的各个节点逻辑对等，这种技术出现的目的就是希望能够充分利用网络中所蕴含 的潜在资源。与c s 模型不同，p 2 p 模型中每个节点既可以是服务( 或者资源) 的提供者，也可以是使用者，充其量就是提供的服务( 或资源) 的类型不同。 为了提高p 2 p 技术在网络中的高效性，很多研究者进行了深入研究，提出了 很多方案，本文也是通过对p 2 p 网络进行研究，提出了对p 2 p 网络中p a s t r y 网 络模型的改进路由算法。 1 2 研究现状 在最近几年中，基于p 2 p 的网络结构的变革浪潮席卷了整个世界，对p 2 p 网络的研究有不同的侧重点，文件共享无疑是p 2 p 网络最重要的应用领域之一， p 2 p 技术使得用户易于实现资源的共享、搜索和交换。短短数年，p 2 p 网络的发 展经历了一系列的重大变化，从最早基于中心索引服务器的n a p s t e r ，完全无 对等网络中p a s 田网络模型的研究 中心的g n u t e l l a 。1 ，到今天互连网上异常火爆的b t 。“，到结构化的p 2 p 网络模型 p a s t r y ”。等。目前对p 2 p 网络的应用和研究，倾向于技术的综合化。首先，从严 格意义上讲，n a p s t e r 作为第一个成形的商业应用，并取得成功( 当然指的是技 术方面) 的p 2 p 产品，并不是真正意义上的完全的p 2 p 。p 2 p 应该是一个没有中 心，网络中的每个节点完全平等的网络。n a p s t e r 显然不具备这一要求。同样， b t 也是需要中心的索引服务来完成下载定位。 p 2 p 网络的关键问题是对象的定位和路由。这方面的研究工作主要分为两类 非结构化路由和结构化路由。非结构化路由如g n u t e l l a 、f r e e n e t 。3 等，每个节 点仅维护邻居路由信息，搜索采用洪泛方法，搜索范围用t t l 参数控制，很显然 搜索在超出一定范围后不能进一步扩展；结构化路由，如t a p e s t r y ”3 、p a s t r y 、 c h o r 等，它们都是基于d h t ( d i s t r i b u t e dh a s ht a b l e ) 技术，路由表具有良 好的结构性，查找具有确定性，也具有较好的可扩展性能，但缺乏整体观念。d h t 技术的共同特征是将对象空间映射到虚拟名字空问，在虚拟名字空间中均匀分配 映射对象，从而方便地实现对象到节点的映射。结构化路由中每个节点维护一个 按一定方法构造的节点列表，用来改进路由效率。 1 3 研究内容 当前，p 2 p 协议产生的i n t e m e t 流量已经超过h t t p 访问产生的网络流量，成 为占据i n t e m e t 带宽的首要应用。p 2 p 系统的体系结构也发生了由n a 口s t e r 的集中 查询到g n u t e l l a 自由连接( 吼s t m c t u r e d0 v e d a yn e t w o r k ) ，再到k i z a a 的偏向于强 结点的自由连接的逐步演变。但是，由于自由连接的随意性，使得数据查询必须 依靠洪泛( n o o d i n 曲或者随机走步的搜索来完成，耗费大量的网络开销，因此，系 统的可扩展性受到严重限制。于是，近年来提出的结构化覆盖网以及基于结构化 覆盖网的分布式哈希表算法成为研究领域的热点。p a s t r y 是一种结构化覆盖网 算法，系统开销小，路由效率高，易于维护，扩展性好，但是这种算法是结点只 知道局部信息，相对全连通的o n e _ h o po v e r l a y 算法来说缺乏整体观念。通过研 究，本文提出一种结构化p 2 p 网络算法s m a r t p a 。它结合p a s t r y 和o n e h o p o v e r l a y 算法的优点，各结点根据自身的带宽能力决定其路由表的大小，有较好 的可扩展性，结点根据系统环境的变化动态地调节自身级别，能够适于各种系统 对等网络中p 勰t r y 网络模型的研究 环境和网络规模。 1 4 论文组织 本文结构安排如下： 第一章：绪论。 第二章：本章作为技术背景，论述了p 2 p 的概念、特点、发展，分析了p 2 p 模式与c s 模式的区别，对p 2 p 技术的应用领域和关键技术进行了分析，最后作总 结。 第三章：讲述了p 2 p 的网络模型，对目前p 2 p 网络的结构分类进行了介绍， 另外对几种结构化p 2 p 算法进行了分析和比较。 第四章：本章是本文的核心。结合p a s t r y 和全连通的o n e 咱o po v e r l a y 算法 提出了带宽自适应的p 2 p 网络算法s m a r t p a 。 第五章：工作总结和展望。本章对论文的内容进行了总结，并展望了今后 需要进一步完善和开展的工作。 对等网络中p a s 田网络模型的研究 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 使 得网络上的沟通变得容易、更直接共享和交互，真f 地消除中间商。p 2 p 就是人 可以直接连接到其他用户的计算机、交换文件，而不是像过去那样连接到服务器 去浏览与下载。p 2 p 另一个重要特点是改变互联网现在的以大网站为中心的状 态、“重返非中心化”，并把权力交还给用户。p 2 p 看起来似乎很新，但是正如 b 2 c 、b 2 b 是将现实世界中很平常的东西移植到互联网上一样，p 2 p 并不是什么新 东西。在现实生活中我们每天都按照p 2 p 模式面对面地或者通过电话交流和沟 通。 即使从网络看，p 2 p 也不是新概念，p 2 p 是互联网整体架构的基础。互联网 最基本的协议t c p i p 并没有客户机和服务器的概念，所有的设备都是通讯的平 等的一端。在十年之前，所有的互联网上的系统都同时具有服务器和客户机的功 能。当然，后来发展的那些架构在t c p i p 之上的软件的确采用了客户机服务器 的结构：浏览器和w e b 服务器，邮件客户端和邮件服务器。但是，对于服务器来 说，它们之间仍然是对等联网的。以e m a i l 为例，互联网上并没有一个巨大的、 唯一的邮件服务器来处理所有的e m a i l ，而是对等联网的邮件服务器相互协作把 e m a i l 传送到相应的服务器上去。另外用户之问e l i l a i l 则一直对等的联络渠道。 事实上，网络上现有的许多服务可以归入p 2 p 的行列。即时讯息系统譬如 i c q 、a o i 。i n s t a n t i e s s e n g e r 、y a h o op a g e r 、微软的m s n f e s s e n g e r 以及国内 的腾讯q q 是最流行的p 2 p 应用。它们允许用户互相沟通和交换信息、交换文件。 对等网络中p 烈r y 嘲络模型的研究 用户之问的信息交流不是直接的，需要有位于中心的服务器来协调。但这些系统 并没有诸如搜索这种对于大量信息共享非常重要的功能，这个特征的缺乏可能正 为什么即时讯息出现很久但是并没有能够产生如n a p s t e r 这样的影响的原因之 2 2p 2 p 的特点 p 2 p ( p e e r t o p e e r ，即对等网络) 是近年来广受i t 业界关注的一个概念。 由于广大的网络终端节点( 普通用户拥有的节点，即通常意义上的终端设备) 的计算和存储能力以及连接带宽随着摩尔定理不断地增长，使用p 2 p 技术将大 大提高这些节点的利用率，从而进一步提升网络、设备和信息服务的效能。 对等网络( p e e r _ t o p e e r ，p 2 p ) ，是由若干分散的互联协作的对等节点( 计 算机或其它终端设备) 构成，节点问通过直接交互共享资源和服务。它具有以下 三个显著的特点： 信息分散：在位置上对等实体完全不局限于地域，在信息的使用上它将 网络信息分散化，这样相同信息的p 2 p 设备可以构成存在于互联网这张大网中的 子网，使信息按新方式又一次集中重组。 关系平等：每个对等网节点既是服务器又是客户端，如何表现取决于用 户的需求，这样的平等关系使得它们之间功能互补、各取所需，具有协调互助的 能力。并且对等网的网络应用由使用者自由驱动。 结构灵活：p 2 p 网络有它的自组织性和节点动态加入、离开的灵活性， 是构架在现有网络之上的一个逻辑实体群。它不依赖于现存的网络拓扑结构，它 强调的仅仅是节点互联、网络互连，结构相对灵活。 2 3p 2 p 的发展 p 2 p 的发展可分为以下三个阶段： 第一代的文件交换服务以n a p s t e r 和b t 独领风骚，其技术是建立一个大型 的集中化索引，对网络上所有的可用资源进行追踪。这种方法虽然相! 均有效率， 对等网络中p 矧r y 网络模型的研究 让使用者可以存取到庞大的资源，但同时发生了最著名的官司：美国唱片业协会 ( r i a a ) 代表环宇音乐、索尼音乐、华纳音乐、百代唱片、b m g 等七大唱片公司 以违反版权保护法为由把n a p s t e r 公司推上法庭，历时三年最终将n a p s t e r 告倒， 法院最终判定n a p s t e r 侵权。 第二代分散式服务以国外的k a z a a 和国内迅速崛起的p o c 0 为代表。它们改 为在电脑间发送搜索请求，一直到找到文件为止，然后再将信息传回搜索者的电 脑。这种技术一开始相当不便，特别是数以百万计的搜索要求在网络上的每一台 电脑问来回发送时，在高峰时段往往造成网络大塞车。后来通过随机方式选出品 质较优的用户来作为节点服务器，用户可从节点服务器上获得p e e r l i s t ，下载 方法也越来越进步。但与第一p 2 p 软件命运截然不同的是，美国法院最近宣判， 这种分散式的p 2 p 应用是合法的，这种软件的散播者并未直接控制网络上所出现 的行为。 第三代的p 2 p 网络则是以e d o n k e y 、e m u l e 、m o r p h e u s 为代表，比以前更为分 散化。它采用“分散式杂凑表”的方法，基本上是对网络上某一特定时刻的文件 进行快照( s n a p s h o t ) ，然后将这些信息分散到整个网络里。为了找到特定的文 件，搜索的要求先到达网络上的任何一台电脑，然后这台电脑就会再将它转到另 一台有更多文件信息的电脑，第三台电脑可能就拥有文件本身，或者也可能再继 续转到其他有正确信息的电脑。整个过程有点像依照线索循序问路而找到正确方 向，而不是路上随便抓人问路。每个网络相关信息，会随电脑及文件的加入而持 续更新。s t r e a m c a s t 2 0 0 4 年向哈佛学生b e n w i l k i n 及f r a n c i s c r i c k 买下这项技术。 这两位前哈佛学生表示，他们的技术只要跳三至四次就可以在几百万台电脑的网 络里找到任何文件，不管这个文件多么稀有。这种技术也让一些应用有了新的前 景，例如网络电话。n e o n e t 与e d o n k e y 专注的都是文件交换，但s k y p e 专注于网络 电话。这种有效率的网络路由技术可用于快速连接网络电话，但也给传统电信运 营商带来了冲击。 2 4p 2 p 与传统c s 模型的对比 目前占据互联网主导地位的计算模式是c s 模式，图2 1 是一个典型的c s 模 对等网络中p 勰t f y 网络模型的研究 式的体系结构。在这种架构下，采用集中计算方式，客户端和服务器存在着明显 的主从关系，具体来说c s 结构有如下特点： ( 图2 1 ：c s 模式) ( 图2 2 ：p 2 p 模式) ( 1 ) 该结构模型以服务器为中心的，各种各样的资源、信息和数据等都存 放在服务器的硬盘上，客户端通过网络连到服务器上检索、下载、上传资料或请 求运算，只有服务器端具有控制能力，客户端基本上充当了一个高性能的i o 设备。 ( 2 ) 服务器性能决定了网络的性能，每台服务器所能提供的信息数量受到 自身存储空间的限制，而任意时刻它所能支持的客户端访问数量则既受到自身处 理能力的限制也受到服务器所在网络吞吐能力的限制。 翌竺堕堑主型翌塑垒堡型塑坚窒 ( 3 ) 被发布信息的分布与生存期十分稳定。服务器只发布机器所有者想公 布于众的信息，这些信息将会在该服务器上稳定地保存一段时间，并且该服务器 通常也不问断地运行在网络上。 ( 4 ) 该结构的优点是被发布信息的存贮与管理比较集中、规范，网络安全 性较高。 p 2 p 模式与c s 模式相比较，它是非中心化的结构，如图2 2 所示。它有如下 特点： ( 1 ) 每一个对等点具有对等的地位。既可以请求服务也可以提供服务，同时 扮演着c s 模式中的服务器和客户端两个角色，还可以具有路由器和高速缓冲存 储器的功能。从而弱化了服务器的功能，甚至取消了服务器。 ( 2 ) 节点加入更方便。在p 2 p 的计算环境中从大型机到移动电话，甚至是传呼 机均可以在任何地点方便地加入进来。p 2 p 技术不仅可以应用于目前有线的互联 网络，同时该技术还可应用于无线计算技术。 ( 3 ) 在p 2 p 模式下，每一个对等体可以充分利用网络上其他对等体的各种信息 资源和软硬件资源。 ( 4 ) 与c s 用u r l 来表示信息资源的地址不同，p 2 p 是基于内容的寻址方式。这 里的内容不仅包括信息的内容，还包括空闲机时、存储空间等。p 2 p 网络中，用 户直接输入要索取的信息的内容而不是信息的地址，p 2 p 软件将会把用户的请求 翻泽成包含此信息的节点的实际地址，而这个地址对用户来说是透明的。 ( 5 ) p 2 p 中的每一个对等体通常没有固定的l p 地址，并且可常常从网络上断 开。 ( 6 ) 信息的存储及发布具有随意性，缺乏集中管理，安全性不高。 通过上面的比较，可以看出p 2 p 模式相对于c s 模式的一些主要优点： 首先，体现在p 2 p 模式所具有的资源高度利用率。在p 2 p 网络上，许多闲散的 资源将有机会被利用起来，众多节点的资源总和构成了整个网络的资源，这样就 使得整个网络的存储能力得到最大限度的发挥，从而使其相当于具有巨大计算处 理能力的超级计算机。而在c s 模式下，这些众多的客户端闲置资源则无法得到 利用。 其次，传统c s 模式下，随着节点的不断增加，服务器的负载就越来越重， 对等网络中舻s 竹网络模型的研究 很容易形成系统的瓶颈，在这种情况下，一旦服务器崩溃，那么整个网络也将随 之瘫痪，从而造成很大的损失。但这种情况在p 2 p 网络中就可以避免，因为该网 络中，每个对等体都是一个活动的参与者，每个对等点都在向网络贡献存储空间、 c p u 周期等一些资源，所以对等点越多，网络的性能就会越好，网络会随着规模 的不断扩大而更加稳固。这种优越性是c s 模式所无法比拟的。 再次，c s 模式下的互联网完全依赖于中心点，即服务器，如果没有服务器， 网络就失去了意义。在p 2 p 网络中，即使只有一个对等点存在，网络也是活动的， 节点所有者可以随意地将自己的信息发布到网络上供他人共享。 此外，在p 2 p 网络中，由于信息在网络设备间直接流动，快速、及时，有利 于降低中转服务的成本。p 2 p 与c s 模式在若干方面的比较见下表2 1 。 p 2 pc s 数据发布好差 数据接收 【b 好 数据安全性 d 好 数据更新好差 数据质量 中 好 数据覆盖和数量 差好 数据成本控制好 差 数据管理方便性 差好 表2 1p 2 p 与c s 模式在若干方面的比较 2 5p 2 p 技术的应用 p 2 p 计算技术的应用主要包括：文件交换、信息资源共享、对等计算、协同 工作、实时通信技术、信息检索技术、网络游戏、基于i n t e r n e t 存储系统和操 作系统以及对p 2 p 开发平台的研究和p 2 p 安全框架的构建等。 1 信息资源共享 信息资源共享一直是网络技术发展的重要推动力，也是p 2 p 技术中最典型的 应用。目前人们主要采用w e b 技术来实现信息资源共享，在基于w e b 方式进行信 息资源共享时，w e bs e r v e r 需要能够对大量用户的访问提供有效的服务，w e b s e r v e r 经常成为这类系统的性能瓶颈。p 2 p 实现信息共享的主要目的是全面实现 数据共享，使用者可以直接从任意一台p c 上检索、共享资源，而不是从服务器； 对等网络中p 勰仃y 网络模型的研究 用户自动发现最新的文件列表，而不需担心发布的问题。如典型的n a p s t e r 系统， 就是提供给用户在互联网上共享m p 3 音乐文件的p 2 p 应用，n a p s t e r 把音乐文件 存储在客户节点上而不是在服务器节点上，中心服务器上仅存储文件的索引信息 用户之阐可以直接共享、传输音乐文件。采用这种方式来共享信息资源可以更充 分地利用网络中的带宽资源，提高系统数据通信的效率。如f r e e n e t 、n a p s t e r 、 g n u t e l l a 等，这些研究均从不同的角度尝试解决目前网络中的信息资源共享所 存在的一些问题。 2 对等计算 人们一直在尝试通过并行技术、分布式技术将多个网络节点联合起来，利用 闲散计算资源来完成大规模的计算任务。p 2 p 计算技术研究的目的之一就是如何 充分利用网络中各种各样的计算单元来共同完成大规模的计算任务。单一计算单 元的计算能力总是有限的，而网络中计算机的计算能力一直未充分利用，人们期 望能够充分利用网络中的闲散计算能力来完成大规模的计算任务，这样将会使得 网络中所蕴含的海量计算能力得到更加充分的利用。 在p 2 p 系统中，每个对等点不再只是单纯地接收计算任务，它还可以根据自 己的情况( 比如分到的任务太多) 再搜索其他空闲节点把收到的任务分发下去。计 算的中间结果层层上传，最后到达任务分发节点，对等点之间可以直接交换中间 结果，协作计算”。就本质而言，对等计算即是实现网络上c p u 资源共享。如 b e r k e l e y 大学启动的对等计算的研究项目s e t i h o m e ”1 ，有一百万台计算机参与 分析在外星系文明研究。 3 协同工作 协同： 作是指多个用户之间利用网络中的协同计算平台互相协同来共同完 成计算任务，共享信息资源等”。协同应用包括：实时通信、文件共享、聊天室、 好友列表等基本功能，用户可共享白板、协同设计、进行视频会议等。g r o o v e 是基于i n t e r n e t 的p 2 p 协同应用软件的典型代表。 企业通过运用p 2 p 计算技术，在没有中心服务器的环境下建造一个包含项目 管理、协同设计和制造等功能的协同应用平台，使个人和动态联盟组织可以随时 建立在线、非在线的协同应用环境。协同系统使得在不同地点的参与者可以在一 对等网络中p a s t r y 网络模型的研究 起工作，文件直接共享的方式可以保证系统中的每个人所获得的信息总是最新 的，降低了对服务器存储及性能的要求，网络的吞吐量和快速反应得到大幅度提 高，节约了成本，提高了效率，使低成本的协同工作成为可能。因此基于p 2 p 技术的协同工作已受到大型企业的极大重视。 4 实时通信技术 实时通信技术是网络中重要的通信技术，如典型的i c q 、0 i c q 等。从某种意 义上说，实时通讯应用将超过文件共享应用，成为p 2 p 网络技术的第一大应用。 与i r c ( i n t e r n e tr e l a yc h a t t i n g i n t e r n e t ) 、b b s 、w 阴聊天室相比，p 2 p 的实 时通讯软件不仅可以随时知晓对方是否在线，而且交流双方的通讯完全是点对点 进行，不依赖服务器的性能和网络带宽，节点之间直接进行数据通信。尽管目前 的即时通讯技术一般都具有中心服务器，但中心服务器仅是用来控制用户的认证 信息，帮助完成节点之间的初始连接。j a b b e r ”“是一个开放源码的实时通信平台， j a b b e r 提出了一个采用x m l ( e x t e n s i b l em a r k u pl a n g u a g e ) 表示的在不兼容的各 种实时通信平台之问进行消息交换的协议。 5 信息检索技术 搜索引擎是目前人们在网络中检索信息资源的主要工具”1 ，目前的搜索引擎 如：g o o g l e 、b a i d u 等都是集中式的搜索引擎，搜索模式是由一个机群在互联网 上盲目读取信息，然后按照某种算法根据关键字将信息保存在一个海量数据库 内。用户提交的搜索请求，实际上是在海量数据库内部进行搜索。这种机制虽然 能尽快获得搜索结果，但不能保证搜索范围的深度和结果的时效性。即使是 g 0 0 9 l e 这个目前最出色的全中文搜索引擎也只能搜索到2 0 3 0 的网络资源。 在j x t as e a r c h “中认为采用p 2 p 的搜索技术可以有效地跟踪数据的更新速度、 提高访问的有效性以及检索的效率。 p 2 p 网络模式中节点之间的动态而又对等的互联关系使得搜索可以在对等 点之间直接、实时地进行，既可以保证搜索的实时性，又可以达到传统目录式搜 索引擎无可比拟的深度( 理论上将包括网络上所有开放的信息资源) 。以基于p 2 p 技术的g n u t e l l a 进行的搜索为例：一台p c 上的g n u t e l l a 软件可将用户的搜索 请求同时发给网络上另外1 0 台p c ，如果搜索请求未得到满足，这l o 台p c 中的 对等网络中p 础i y 网络模型的研究 每一台都会把该搜索请求转发给另外1 0 台p c ，这样，搜索范围将在几秒钟内以 几何级数增长，几分钟内就可搜遍几百万台p c 上的信息资源。可以说，p 2 p 为 互联网的信息搜索提供了全新的解决之道。 6 广域网络存储系统 存储技术一直是人们所关注的一项技术，s a n 、n a s 是目前广泛应用于局域 网络的存储技术。分布式文件系统也是广泛使用分布式文件存储技术，典型的分 布式文件包括n f s 、a f s 、c o d a 等。由于网络规模的扩大，人们对网络的使用 也变得十分灵活，开始将传统的分布式操作系统、局域存储技术向基于i n t e r n e t 的文件存储系统发展。一些研究项目开始使用p 2 p 技术来组织和存储文件，典型 的系统包括：o c e a n s t o r e 、f a r s it e 等。这些项目的目标都是提供面向全球规模 的文件存储服务。 7 、智能代理 智能代理是i n t e r n e t 的一个重要技术。p 2 p 同样允许计算网络通过智能代 理动念地与其他网络的计算机联接，代理服务位于对等计算机和与之进行信息交 互的其他点上。代理服务在综合考虑其他对等点的情况下进行任务分配。如根据 网络状况进行任务均衡，改变信息的传输路径，定位搜索文件的位置，拒绝非法 对等点的请求，如病毒等。 8 、网络游戏 很多基于广域网络的游戏也是基于p 2 p 技术的，例如：2 a m 、c e b t e r s p a n 等。 采用p 2 p 技术建立起来的分布式小组服务模型，配以动态分配的技术，每个服务 器的承载人数将在数量级上超过传统的服务器模式，这将大大提高目前多人在线 交互游戏的性能。同时每个游戏用户成为一个对等节点，各个节点可以进行大量 的点对点通讯，从而减少服务器的通讯任务，提高性能。 2 6p 2 p 网络的关键技术 p 2 p 是一种基于互联网环境的新的应用型技术，主要为软件技术。 ( 1 ) 对于互联网上众多计算机，p 2 p 应用应更多考虑那些低端p c 的互联，它们 不具备服务器那样强的联网能力，且现在的硬件环境已更为复杂，这样p 2 p 必须 提供在现有硬件逻辑和底层通信协议上的端到端定位( 寻址) 和握手技术，建立稳 对等网络中p 勰l r y 嘲络模型的研究 定的连接。涉及的技术有i p 地址解析、n a t 路由及防火墙。 ( 2 ) 在应用层面上，如果对等点已通过互联网建立连接，那么一方的信息就 必须为另方所识别。所以当前互联网上关于数据描述和交换的协议，如x m l 、 s o a p 、u d d i 等都是一个完善的p 2 p 软件所要考虑的。 ( 3 ) 如何设置中心目录服务器，控制网络规模和保证网络的鲁棒性等；为保 障信息的安全，必须要考虑加密技术。 ( 4 ) p 2 p 网络的强动态性决定了难以实现对等点间的相互快速准确定位，即发 现对方。目前的主要发现机制有：基于本地缓存的发现、通过集合点或不通过集 合点的本地发现、穿越防火墙的发现、基于集中点的传布方式发现等。 ( 5 ) 高效的搜索策略。一是应尽量减少搜索时经过的节点数，以直接减少请 求消息和处理时间；二是数据应倾向流向对其感兴趣的区域，即数据活跃区。快 速搜索感兴趣的资料，与其他的对等点共享资源和服务。 面临的挑战： ( 1 ) 如何构造一个数据与地域无关的网络环境，数据不再是属于某些特定的 服务器。 ( 2 ) 如何构造一个网络拓扑结构，使p 2 p 网络能自适应最佳的互联网络物理网 络并快速准确地发现对等点；建立数据向请求活跃区移动：有选择性地返回数据 文件或请求响应包的机制。 ( 3 ) 如何建立一个管理机制，预防由恶意请求引发的拒绝服务而导致的系统 崩溃：对等点的互信机制和身份鉴别机制。 ( 4 ) 如何建立一个交互式、协同工作平台，实现数据更新、恢复、版本的配 置管理，保证数据的一致性。 2 7 小结 本章详细论述了p 2 p 的概念、特征、发展及其与c s 模型的比较，对p 2 p 技术的应用领域和关键技术进行了分析。下一章将讲述p 2 p 网络模型及分类，对 几种结构化p 2 p 算法避行分析。 对等网络中p a s t r y 陶络模型的研究 3 1 p 2 p 网络模型 第三章对等网络模型及分类 p 2 p 网络是一种具有较高扩展性的分布式系统结构，其对等概念是指网络中 的物理节点在逻辑上具有相同的地位，而并非处理能力的对等。以n a p s t e r 软件 为代表的p 2 p 技术其实质在于将互联网的集中管理模式引向分散管理模式，将内 容从中央单一节点引向网络的边缘，从而充分利用互联网中众多终端节点所蕴涵 的处理能力和潜在资源。相对于传统的集中式客户服务器( c s ) 模型，p 2 p 弱化 了服务器的概念，系统中的各个节点不再区分服务器和客户端的角色关系，每个 节点既可请求服务，也可提供服务、节点之间可以直接交换资源和服务而不必通 过服务器。 p 2 p 系统最大的特点就是用户之间直接共享资源，其核，心技术就是分布式对 象的定位机制，这也是提高网络可扩展性、解决网络带宽被吞噬的关键所在。迄 今为止，p 2 p 网络已经历了三代不同网络模型，各种模型各有优缺点，有的还存 在着本身难以克服的缺陷，因此在目前p 2 p 技术还远未成熟的阶段，各种网络结 构依然能够共存，甚至呈现相互借鉴的形式。 1 集中目录式结构 集中目录式p 2 p 结构是最早出现的p 2 p 应用模式，因为仍然具有中心化的 特点也被称为非纯粹的p 2 p 结构。用于共享m p 3 音乐文件的n 即s t e r 是其中最典 型的代表( 见图3 1 ) ，其用户注册与文件检索过程类似于传统的c s 模式，区别 在于所有资料并非存储在服务器上，而是存贮在各个节点中。查询节点根据网络 流量和延迟等信息选择合适的节点建立直接连接，而不必经过中央服务器进行。 这种网络结构非常简单，但是它显示了p 2 p 系统信息量巨大的优势和吸引力，同 时也揭示了p 2 p 系统本质上所不可避免的两个问题：法律版权和资源浪费的问 题。 对等网络中p 矧r y 网络模型的研究 2 纯p 2 p 网络模型 图3 1n a p s t e r 集中式目录p 2 p 网络模型 纯p 2 p 模式也被称作洪泛式的p 2 p 模型。它取消了集中的中央服务器，每个 用户随机接入网络，并与自己相邻的一组邻居节点通过端到端连接构成一个逻辑 覆盖的网络。对等节点之间的内容查询和内容共享都是直接通过相邻节点洪泛接 力传递，同时每个节点还会记录搜索轨迹，以防止搜索环路的产生。 g n u t e n a 模型是现在应用最广泛的纯p 2 p 非结构化拓扑结构( 见图3 2 ) ，它 解决了网络结构中心化的问题，扩展性和容错性较好，但是g n u t e l l a 网络中的 搜索算法以泛洪的方式进行，控制信息的泛滥消耗了大量带宽并很快造成网络拥 塞甚至网络的不稳定。同时，局部性能较差的节点可能会导致g n u t e l l a 网络被 分片，从而导致整个网络的可用性较差，另外这类系统更容易受到垃圾信息，甚 至是病毒的恶意攻击。 对等刚络中p 硒l r y 网络模型的研究 3 混合式网络模型 图3 2g n u t e l l a 纯p 2 p 网络模型 k a z a a 模型是p 2 p 混合模型的典型代表( 见图3 3 ) ，它在纯p 2 p 分布式模型 基础上引入了超级节点的概念，综合了集中式p 2 p 快速查找和纯p 2 p 去中心化的 优势。k a z a a 模型将节点按能力不同( 计算能力、内存大小、连接带宽、网络滞 留时间等) 区分为普通节点和搜索节点两类( 也有的进一步分为三类节点，其思想 本质相同) 。其中搜索节点与其临近的若干普通节点之间构成一个自治的簇，簇 内采用基于集中目录式的p 2 p 模式，而整个p 2 p 网络中各个不同的簇之间再通过 纯p 2 p 的模式将搜索节点相连起来，甚至也可以在各个搜索节点之间再次选取性 能最优的节点，或者另外引入一新的性能最优的节点作为索引节点来保存整个网 络中可以利用的搜索节点信息，并且负责维护整个网络的结构。 图3 3 超级节点的混合式p 2 p 网络模型 对等网络中p 矧f ) ，网络模型的研究 由于普通节点的文件搜索先在本地所属的簇内进行，只有查询结果不充分的 时候，再通过搜索节点之间进行有限的洪泛。这样就极为有效地消除纯p 2 p 结构 中使用洪泛算法带来的网络拥塞、搜索迟缓等不利影响。同时，由于每个簇中的 搜索节点监控着所有普通节点的行为，这也能确保一些恶意的攻击行为能在网络 局部得到控制，并且超级节点的存在也能在一定程度上提高整个网络的负载平 衡。 总的来说，基于超级节点的混合式p 2 p 网络结构比以往有较大程度的改进。 然而，由于超级节点本身的脆弱性也可能导致其簇内的结点处于孤立状态，因此 这种局部索引的方法仍然存在一定的局限性。这导致了结构化的p 2 p 网络模型的 出现。 3 2p 2 p 结构分类 按照系统是否建立覆盖网络结构来区分：结构化的p 2 p 系统由带有复杂拓扑 结构的高度动念的网络节点组成。这个拓扑结构建立了一个覆盖网络，它与连接 不同节点的物理网络无关，网络中的共享文件可以根据网络的拓扑结构进行定 位。p 2 p 系统根据是否建立了结构化或特殊的覆盖网来区分，可分为三类。 3 2 1 非结构化p 2 p 系统 这类系统的特点是文件的发布和网络拓扑松散相关。该类方法包括 n a p s t e r ，k a z a a ，m o r p h e u s ，g n u t e l l a 。n a p s t e r 是包含有中心索引服务器的最 早的p 2 p 文件共享系统，存在扩展性和单点失败问题。g n u t e l l a 、m o r p h e u s 是 纯p 2 p 文件共享系统，后者如今并入前者中；k a z a a 是包含有超级节点的混合型 p 2 p 文件共享系统。k a z a a 、m o r p h e u s 、g n u t e h a 等系统采用洪泛或者受限洪泛 来进行资源定位，具有较好的自组织性和扩展性，适用于互联网个人信息共享。 缺点是稀疏资源的召回率低。 塾竺塑塑! ! ! 壁坚垒堡型塑坚塞 3 2 2 结构化p 2 p 系统 所滑结构化与非结构化模型的根本区别在于每个节点所维护的邻居是否能 够按照某种全局方式组织起来以利于快速查找。结构化p 2 p 模式是一种采用纯分 布式的消息传递机制和根据关键字进行查找的定位服务，目前的主流方法是采用 分布式哈希表( d h t ) 技术，这也是目前扩展性最好的p 2 p 路由方式之一。由于d h t 各节点并不需要维护整个网络的信息，只在节点中存储其临近的后继节点信息， 因此较少的路由信息就可以有效地实现到达目标节点，同时又取消了洪泛算法。 该模型有效地减少了节点信息的发送数量，从而增强了p 2 p 网络的扩展性。同时， 出于冗余度以及延时的考虑，大部分d h t 总是在节点的虚拟标识与关键字最接近 的节点上复制备份冗余信息，这样也避免了单一节点失效的问题。 目前基于d h t 的代表性的研究项目主要包括加州大学伯克利分校的c a n 项目 和t a p e s t r y 项目，麻省理工学院的c h o r d “3 项目、i r i s 项目，以及微软研究院 的p a s t r y 项目等。这些系统一般都假定节点具有相同的能力，这对于规模较小 的系统较为有效。但这种假设并不适合大规模的i n t e r n e t 部署。同时基于d h t 的拓扑维护和修复算法也比g n u t e l l a 模型和k a z a a 模型等无结构的系统要复杂 得多，甚至在c h o r d 项目中产生了“绕路”的问题。事实上，目前大量实际应用 还大都是基于无结构的拓扑和洪泛机制，现在大多采用d h t 方式的p 2 p 系统缺乏 在i n t e r n e t 中大规模真实