（计算机科学与技术专业论文）基于结构化节点id的chord协议研究及应用.pdf

北京l 吣电大学硕士学位论文 基于结构化节点i d 的c h o r d 协议研究及应用 摘要 结构化对等覆盖网络( o v e r l a yn e t w o r k ) ，如c a n l 2 j ，c h o r d i l j ， p a s t r y 3 】和t a p e s t r y 4 1 ，为非中心化存储和内容发布等大规模分布式应 用提供了可扩展的、健壮的资源定位和路由服务。这些覆盖网络利用 分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，d h t ) 把关键字映射到覆盖 网络的节点中。以c h o r d 【1 】协议为代表的基于d h t 的资源定位算法 因而受到广泛研究。c h o r d 协议为每个节点和数据分配个在名字空 间中唯一的m 位( 二进制) 标识符( 通常采用一致性哈希算法如s h a 一1 来分配) ，所有可能的2 “个标识符构成一个一维的标识符环。根据这 个标识符环，可以在实际物理网络之上构建逻辑覆盖网络。 但是，使用h a s h 函数造成了逻辑覆盖网络与底层物理网络常常 出现较大的不一致。比如，i p 地址为5 9 6 4 1 5 7 3 8 和5 9 6 4 1 5 7 3 9 的 两个节点n 1 和n 2 在实际物理网络中距离很近，一般情况下是在同 一个局域网中，但是，所产生的标识符h a s h ( 5 9 6 4 1 5 7 3 8 ) 和h a s h ( 5 9 6 4 1 5 7 3 8 ) 却差别很大，从而使得两个节点在逻辑覆盖网络中 的距离很大，n i 寻找n 2 的路由过程可能要经过广域网。为此，本 文提出一种使用结构化节点i d 的方法，在原有的节点i d 基础之上附 加一些信息，使物理网络中邻近的节点在逻辑覆盖网络中尽量接近， 上述n 1 寻找n 2 的过程将避免访问广域网，减少资源开销。 本文在对c h o r d 协议进行认真研究的基础上，提出使用结构化节 点i d 的改进方案，并设计实现迭代式c h o r d 模拟器进行实验分析。 实验结果表明，采用结构化节点i d 后，可以提高c h o r d 网络的查询 效率，减少节点加入和退出c h o r d 网络时转移数据的开销。最后，本 文将使用结构化节点i d 的改进方案应用到基于p 2 p 和g i s 的信息交 流系统( p e e r t o p e e ra n dg i sb a s e di n f o r m a t i o ne x c h a n g es y s t e m ，以 下简称p g i e s ) 的原型系统，以改进方案为基础进行底层对等网络通 信模块的设计和实现。 关键字：对等网络覆盖网络分布式哈希表c h o r d 北京邮电大学计算机应用实验室 i i i 鲎些塞坚生奎兰婴主兰堡丝兰 r e s e a r c ha n da p p l i c a t i o no ns t r u c t u r e di db a s e dc h o r dp r o t o c o l a b s t r a c t s t r u c t u r e dp e e r t o p e e ro v e r l a yn e t w o r k ss u c ha sc a n 2 1 ，c h o r d 1 1 ， p a s t r y 。川a n dt a p e s t r y 1 4 1 p r o v i d eas c a l a b l ea n dr o b u s td a t al o c a t i o na n d r e q u e s tr o u t i n gs e r v i c ef o rl a r g e s c a l ed i s t r i b u t e da p p l i c a t i o n ss u c ha s d e c e n t r a l i z e ds t o r a g ea n dc o n t e n td i s t r i b u t i o n t h e yp r o v i d ead i s t r i b u t e d h a s ht a b l e ( d h t ) f u n c t i o nf o rm a p p i n gk e y st oo v e r l a yn o d e s r e s o u r c e l o c a t i n ga r i t h m e t i c s u c ha sc h o r d 1 1 g o tg r e a ta t t e n t i o n a n o d e p a r t i c i p a t i n gi na no v e r l a yi sa s s i g n e dar a n d o mm b i ti d e n t i f i e rf r o ma n u m e r i cs p a c e ，a n dt h ei d e n t i f i e ri su s u a l l ya s s i g n e db yu s i n gc o n s i s t e n t h a s h i n ga r i t h m e t i cs u c ha ss h a 一1 a i lt h o s ep o s s i b l e2 mi d e n t i f i e r sw i l l c o n s t r u c tao n ed i m e n s i o ni d e n t i f i e rr i n g ，a c c o r d i n gt ow h i c ha no v e r l a y n e t w o r ki sf o r m e da b o v et h ep h y s i c a ln e t w o r k a l t h o u g hs t o r a g el o a d i sb a l a n c e db e c a u s eo fh a s hf u n c t i o n s ，t h e o v e r l a yt o p o l o g yi sn o tc o n g r u e n tw i t ht h ep h y s i c a lt o p o l o g ya sw e l l f o r e x a m p l e ，t w on o d e sn ia n dn 2 ，w i t hi pa d d r e s s “5 9 6 4 1 5 7 3 8 ”a n d “5 9 6 4 1 5 7 3 9 ”，t h e ya r ep r o x i m a t ei nt h ep h y s i c a ln e t w o r k a n dg e n e r a l l y s p e a k i n g ，t h e yb e l o n gt ot h es a m el o c a la r e an e t w o r k h o w e v e r , i d e n t i f i e r h a s h ( 5 9 6 4 1 5 7 3 8 1a n dh a s h ( 5 9 6 4 1 5 7 3 9 ) m a yb er a t h e rd i f f e r e n t ，a sa r e s u l t ，t h e s et w on o d e sw i l lb ef a ra w a yf r o me a c ho t h e ri nt h eo v e r l a y n e t w o r k ，a n dc a np o t e n t i a l l yt r a v e r s eal o n g h a u ll i n kw h e nr o u t i n gf o r e a c ho t h e r t oa d d r e s st h i si s s u e ，w ep r o m o t et h eu s eo fl o c a t i o n b a s e d s t r u c t u r e dn o d ei dt oe n c o d ep h y s i c a l t o p o l o g ya n di m p r o v er o u t i n g t h i sh e l p sn o d e sp r o x i m a t et oo n ea n o t h e ri nt h ep h y s i c a lt ob ep r o x i m a t e i nt h eo v e r l a yn e t w o r ka sm u c ha s p o s s i b l e ，a n dw h e nt h et w on o d e s a b o v ew a n tt oa c c e s se a c ho t h e r ，l o n g h a u ll i n k sm a yb ea v o i d e d i nt h i sp a p e r , am e t h o dt a k i n g p r o m o t e db a s e do nt h er e s e a r c ho f c h o r ds i m u l a t o ri s d e s i g n e d a n d a d v a n t a g eo fs t r u c t u r e dn o d ei di s c h o r dp r o t o c o l ，a n di t e r a t i v e s t y l e i m p l e m e n t e d f o r e x p e r i m e n t a n d a n a l y s i s e x p e r i m e n t a lr e s u l t s s h o wt h a ts t r u c t u r e dn o d ei dh e l pt o 北京邮电大学汁算机应用实验室 二篓北京邮电大学硕士学位论文 l m p o v 。o u t i n ga n dl o w e rt h ec o s to ft r a n s f e r r i n gd a t aw h e nn o d e s j o i n i n ga n dl e a v i n gc h o r ds y s t e m f i n a l l y ，t h em e t h o dt a k i n ga d v a n t a g e o fs t r u c t u r e dn o d ei di sa p p l i e dt ot h ep r o t o t y p eo fp e e r t o p e e ra n dg i s b a s e di n f o r m a t i o ne x c h a n g es y s t e m ( p g i e s ) t h e l o w 1 a y e rp e e r ，t o p e e r c o m m u n i c a t i o nm o d u l a ri s d e s i g n e da n di m p l e m e n t e db a s e do nt h e m e “1 0 d k e y w o r d s ：p e e r t o p e e rn e t w o r k ，o v e r l a yn e t w o r k ，d i s t r i b u t e dh a s h t a b l e ，c h o r d 北京邮电大学计算机应用实验室 v 。北京邮电火学硕士学位论文 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：二奠盖勇l 一 日期：j 竺生聋l 一 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阐；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名 互占艮 日期： ”口f 彳q 导师签名：查阜亳l 同期：五业j i 王l 北京i i i b i 电大学计算机应用实验室l i 北京邮电大学硕= b 学位论文 第一章综述 1 1 问题的提出 第一章综述 在大多数的p 2 p 系统中，最为核心的操作就是怎样有效地对所需数据资源 进行定位。关于如何对所需数据资源进行高效、可靠的定位，目前主要有两类方 案：洪泛算法( f l o o d i n g ) 类和基于分布式哈希表( d h t ) 的方法。使用洪泛算 法，随着网络规模的增长，网络带宽会被耗尽。洪泛算法的不可扩展性在 g n u t e l l a 2 3 1 的实践中得到了证实。目前很多研究都集中在基于d h t 的方法上。 著名的基于d h t 的路由算法主要有四种，他们的主要性能指标如表1 1 所 示。其中查找路径长度指的是每个查询定位请求在p 2 p 网络中经历的平均应用 层跳( h o p ) 数，路由表大小指的是每个节点维护的路由表项的数目。根据引文 圳的研究，在节点动态变化频繁的实际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 的稳定性高。而动态环境中的稳定性是p 2 p 网络是否实用 的关键性指标，所以其中c h o r d 算法非常引人注目，本研究课题也是以c h o r d 算法为基础的。 参数查找路径长度路由表大小稳定性 c a n d ：维数 d n l d2 d 好 c h o r d l 0 9 2 nl 0 9 2 n 好 p a s t r y b ：i d 空间的基 l o g b nl o g b n 一般 t a p e s t r y b ：i d 空间的基 l o g b nl o g b n 一般 一 一 表1 1 ：四种d h t 算法性能的比较 c h o r d 协议为加入覆盖网络的每节点分配一个数值形式的标识符作为节点 i d ( 通常采用对节点的i p 地址进行一致性哈希来实现) ，并使节点i d 构成节点 一维的i d 空间，标识符的范围是： 0 ，1 ，2 ，2 m 一1 其中，m 是标识符( 二进制) 的位数。 这2 朋个标识符依次按照顺时针升序排列，构成一个标识符环，在实际物理 网络之上构建了逻辑覆盖网络。m = 3 时的标识符环如下图1 1 所示。 北京邮电大学计算机应用实验室 r 北京邮电大学硕二i ：j 学位论文 第一章综述 在c h o r d 路由算法中，节点基于节点i d 选择下一个路由跳，节点i d 由哈希 算法随机生成。在对c h o r d 协议进行研究的过程中发现，使用一致性h a s h 函数 ( 如s h a 1 ) 造成了逻辑覆盖网络与底层物理网络相当大的不一致。比如，i p 地址为5 9 6 4 15 7 38 和5 9 6 4 15 7 3 9 的两个节点n 1 和n 2 ，在实际物理网络中二 者距离很近，一般情况下处于同一个局域网中，但是，所产生的节点标识符h a s h ( 5 9 6 4 15 7 3 8 ) 和h a s h ( 5 9 6 4 15 7 3 9 ) 却差别很大，示意图如图1 1 所示，从 而使得两个物理距离较近得节点在逻辑覆盖网络中的距离往往很大。 图1 1 ：m = 3 时的c h o r d 网络环形标识符空间示意图，有阴影者为在线节点。 实际上，p 2 p 路由的路径由起始节点与目标节点间的应用级路由跳组成，而 不是由i p 级路由跳组成，实际的p 2 p 路由效率是由端到端的路由时延来衡量的， 由于对等节点在地理上是分布的，有些应用级路由跳穿越了不同的自治系统，而 另一些路由跳则仅仅从一个节点到同一局域网内的另一个节点。因此，逻辑覆盖 网络与底层物理网络之间往往存在相当大的不一致。这就使得实际网络距离较近 的节点之间可能需要按照d h t 算法的要求进行几次的周转才能访问对方。 有些研究人员已经认识到基于分布式哈希表的路由机制也有无法解决的问 题f 】。首先，经过哈希之后，节点的位置信息被破坏了，来自同一个子网的站点 很可能节点号相距甚远，这不利于查询性能的优化。其次，基于哈希表的系统不 能利用应用本身的信息，许多应用( 比如文件系统) 的数据本身是按照层次结构 组织的，而使用哈希函数后，这些层次信息就丢失了。 北京邮电大学计算机应用实验室 北京邮电大学硕：卜学位论文 第一章综述 引文【2 l j 中证明了，如果节点路由表中每个表项都是指向在底层网络中距离自 己最近的节点，那么就可以使得路由延迟最小，且定位到最近的文件副本，这样 即利于保证系统的局部性。 ，本文在对引文提出的c h o r d 协议进行了深入研究之后，提出对c h o r d 协议 中的节点i d 进行改进，亦即使用结构化节点i d 的方案来实现实际网络中的距 离( i p 地址之间的距离) 较近的节点在逻辑覆盖网络同样能够距离较近，探讨 解决原始c h o r d 协议所存在的逻辑覆盖网络与底层物理网络之间往往出现相当 大不一致的问题的方法。 1 2 国内外研究现状 c h o r d 协议【1 j 是m i t ( 麻省理工大学) 计算机科学实验室提出的分布式查询、 路由协议。c h o r d 1 】和c a n 2 1 、p a s t r y 3 】以及t a p e s t r y 4 】一起都属于基于分布式哈 希表d h t 的结构化对等物理路由算法。麻省理工大学一直在进行有关c h o r d 协 议的研究，开发了称为“c h o r dp r o j e c t 的项目。“c h o r dp r o j e c t ”项目的目的是： 以对等通信的理念构建可控展的、健壮的分布式系统。该项目的资料网址是： h t t p ：p d o s c s a i l m i t e d u c h o r d 。 国外开展p 2 p 研究的学术团体主要包括p 2 p 工作组( p 2 p w g ) 、全球网格论 坛( g l o b a lg r i df o r u m ，g g f ) 。p 2 p 工作组成立的主要目的是希望加速p 2 p 计 算基础设施的建立和相应的标准化工作。p 2 p w g 成立之后，对p 2 p 计算中的术 语进行了统一，也形成相关的草案，但是在标准化工作方面工作进展缓慢。目前 p 2 p w g 已经和g g f 合并，由该论坛管理p 2 p 计算相关的工作。g g f 负责网格 计算和p 2 p 计算等相关的标准化工作。【2 8 】 引文【2 】提出分布式哈希表d h t 的路由机制可能将使得逻辑覆盖网络与实际 物理网络存在较大不一致。 在结构化p 2 p 网络中，o v e r l a y 网络中的两个节点根据其在底层网络中的最 小化端到端延迟( e n dt oe n dl a t e n c y ) 进行路由选择的技术称为邻近度路由 ( p r o x i m i t yr o u t i n g ) 。在o v e r l a y 网络中，利用邻近度路由技术进行路由构建和选 择是提高应用性能的重要手段。目前，邻近度路由技术分为两种，一种是节点加 入o v e r l a y 网络时，利用网络测量选择在底层网络中更靠近自己的节点作为邻居 节点，这种方法通常称为邻近度邻居选择p n s ( p r o x i m i t yn e i g h b o rs e l e c t i o n ) ： 另一种邻近度路由技术是邻近度路由选择p r s ( p r o x i m i t yr o u t es e l e c t i o n ) ，节 北京邮r 乜大学计算机应用实验室 北京邮l - 乜大学硕二 ：学位论文 第一爨综述 点在路由表中对每个路由条目维护一个可选邻居集，每次路由时选择一个底层网 络上距离最近的节点进行消息转发。 r a t n a s a m y 等人为c a n 提出了一种“分布式围栏算法 ( d i s t r i b u t e db i n n i n g s c h e m e ) ，试图让p 2 p 的逻辑拓扑结构与底层网络拓扑结构尽可能的匹配 ( m a t c h ) 2 5 】。这种方法需要在整个系统的范围内选取一组地理位置分布均匀的 “地标节点( 1 a n d m a r k ) ，同时将c a n 的整个节点地址空间也分为k ! “栏”， 每一栏对应k 个地标节点一种排列顺序。当一个节点加入系统时，测量自己到k 个地标节点的距离，按这k 个距离排列的顺序确定自己应处的地址空间“栏”， 并从该栏中随机获得一个未使用的节点地址。通过这样的方式，可以使得节点地 址和它在底层网络中的大致位置对应起来。在这种方式中，地标节点的选取很重 要，直接影响到地址空间划分的均匀。该方法对规模固定的系统来说效果较好， 但是如果系统规模处在动态变化之中，地标节点的确定就变得很困难，且对地标 节点的依赖也会给系统带来单点失效的可能。 p r r 2 6 】是最早使用p n s 技术的路由算法。通过为节点构造一张精心设计的 路由表，p r r 可以获得接近最优的路由性能。但是p r r 在构造节点路由表时， 必须预先知道系统中任意两个节点间的距离情况，以便选择距离最近延迟最小的 节点加入节点路由表。对于大规模、高度动态的p 2 p 系统来说，要获得这些信 息的代价十分昂贵，实现的可能性不大。 z h a n g 等人为c h o r d 路由算法引入了一种称为“l o o k u p p a r a s i t i cr a n d o m s a m p l i n g ( l p r s ) 的p n s 技术 2 7 】。在原始的c h o r d 路由算法中，i d 为n 的节点 的f i n g e rt a b l e 中第f 项是指向在i d 空间中最小最接近n + 2 卜1 的节点，而在l p r s 中，这一项被改为指向i d 范围在 n + 2 卜1 ，n + 2 ) 内底层网络距离当前节点最近的 节点。这种方式不需要为节点保存额外的路由信息，并可以使得消息的每一次转 发都是被传递到距离当前节点较近的下一个节点，减少了每一步的路由延迟，提 高了路由性能。 。 引文【6 提出了基于位置信息的节点i d ，提出将节点的位置信息如所处州、市 的信息体现在节点i d 中。给本文的研究提供了一定的借鉴。 1 3 本文的工作及组织 1 3 1 本文的工作和成果 本文首先对c h o r d 仂、议进行了研究，并且按照c h o r d 协议的基本算法实现了 北京邮电大学计算机应用实验室4 北京邮电大学硕= 卜学位论文 第一章综述 迭代式c h o r d 模拟器，然后在此基础上采用结构化节点i d 对c h o r d 协议的节点 i d 进行改进，实现了基于结构化节点i d 的c h o r d 模拟器一- - s c h o r d 模拟器。 使用迭代式c h o r d 模拟器进行实验，得到的实验数据所呈献出来的规律与引 文【l 】中给出的实验数据所呈献的规律非常接近，这就证明了本文所实现的迭代式 c h o r d 模拟器是有效的。 。在实现了迭代式c h o r d 模拟器之后，使用结构化i d 对c h o r d 协议的节点i d 产生方法进行改进，实现了基于结构化i d 的迭代式c h o r d 模拟器一- - s c h o r d 模 拟器。使用s c h o r d 模拟器进行了多次实验，并且将实验数据记录下来。“实验结 果表明，采用结构化节点i d 后，可以减小c h o r d 网络的路由拉伸率( s t r e t c h ， 逻辑覆盖网络的查询长度与源节点和目的节点之间的最短网络距离之间的比例) 提高查询效率。另外，可以减少节点加入和退出c h o r d 网络时转移数据的开销。 最后，本文将使用结构化节点i d 的改进方案应用到基于p 2 p 和g i s 的信息 交流系统( p e e r - t o p e e ra n dg i sb a s e di n f o r m a t i o ne x c h a n g es y s t e m ，以下简称 p g i e s ) 的原型系统，以改进方案为基础进行底层对等网络通信模块的设计和实 现。 本文的主要贡献在于：第一，根据原始c h o r d 协议设计实现了迭代式c h o r d 模拟器，并且验证了引文【1 】分析得出的实验结论；第二，提出了一种使用结构化 i d 改进c h o r d 协议的方法，并且设计实现模拟器进行实验分析，最后用于信息 交流系统的底层通信模块的设计和实现。 1 3 2 本文的组织 本文第一章介绍了对等网络资源查找协议的研究情况，并且提出要研究的课 题。随后第二章介绍了对等网络定义和分类，基于d h t 的资源定位算法，以及 c h o r d 协议的技术背景。第三章着重介绍了本课题的研究内容，也就是结构化节 点i d ，并提出了设计方案。第四章设计实现迭代式c h o r d 模拟器和基于结构化 节点i d 的迭代式c h o r d 模拟器一- - s c h o r d 模拟器，并利用二者进行实验，对改 进方案进行了实验评估，对使用两种模拟器进行实验所得的数据进行了比较分 析。第五章将改进方案应用到p g i e s 系统的底层网络通信模块的设计和实现中。 第六章对课题进行了总结，说明了本课题今后还需要进一步研究的问题和改进提 高的方向。 北京邮电大学计算机应用实验室 北京i i i l 5i ：【! l 大学硕：i ：学位论文 第二章技术背景 第二章技术背景 2 1 对等网络的定义、特点、分类和应用 2 1 1 对等网络的定义和特点 2 1 1 1 对等网络的定义 p 2 p 是p e e r t o p e e r 的缩写，p e e r 在英语里有“( 地位、能力等) 同等者”、“同 事”和“伙伴”等意义，这样一来，p 2 p 也就可以理解为“伙伴对伙伴”的意思， 或称为“对等网络 。当对等计算机在客户机i n 务器模式下作为客户机进行操作 时，它还包含另外一层可使其具有服务器功能的软件，对等计算机可对其他计算 机的要求进行响应，请求和响应范围和方式都根据具体应用程序不同而不同。简 单地说，p 2 p 直接将人们联系起来，让人们通过互联网直接交互。p 2 p 使得网络 上的沟通变得更容易、更直接，真正地消除了中间商。每个人可以直接连接到其 他用户的计算机交换文件，而不是像过去那样连接到服务器去浏览与下载。目前 人们认为p 2 p 在加强网络上人与人之间的交流以及文件交换、分布计算等方面 大有前途。 p 2 p 技术主要指由硬件形成网络连接后的信息控制技术，主要代表形式是在 应用层上基于p 2 p 网络协议的客户端软件。i b m 为p 2 p 下了如下定义：p 2 p 系 统由若干互联协作的计算机构成，且至少具有如下特征之一：系统依存于边缘化 ( 非中央式服务器) 设备的主动协作，每个成员直接从其他成员而不是从服务器 的参与中受益；系统的成员同时扮演服务器与客户端的角色；系统应用的用户能 够意识到彼此的存在，构成一个虚拟或实际的群体。p 2 p 网络是互联网整体架构 的基础，互联网最基本t c p i p 协议并没有客户端和服务器的概念，在通信过程 中，所有的设备都是平等的一端。 总体来讲，p 2 p 计算系统是分布式的，有别于集中式的结构，也有别于基于 服务器的结构。纯粹的p 2 p 计算系统不存在任何不可或缺的服务器( 但某些混 杂式p 2 p 系统存在着中央服务器，比如n a p s t e r ) 。从传统的观点来看，p 2 p 计算 系统中的实体一般同时扮演两种角色：客户机和服务器。 北京邮电大学计算机应用实验室 北京邮电大学硕二l 学位论文第二章技术背景 2 1 1 2 对等网络的优点 和传统的网络应用相比，p 2 p 技术具有下列几个优点： 1 ) 分散化 消除单点错误 集中化系统通常受制于单点错误。网络问题、硬件问题或应用程序误操作都 将导致出现单点错误。为集中化系统的所有部件准备冗余设备不仅费用高昂，而 且在某些情况下甚至是无法实现的。当集中化系统出现故障时，将导致企业动作 的终止。事实证明，即使在不稳定的情况下，p 2 p 系统也不会出现单点错误。 一一减少瓶颈 尽管集中化服务器可以以并行方式处理请求，但每个服务器的负载都是有一 个特定的阀值，超过这个阀值后，服务器的处理速度会非常之慢，甚至会崩溃。 通常情况下，解决集中化系统瓶颈问题的指导思想是“买更大( 性能更好) 的硬 件”。然而，这只是一种权宜之计，而不是长期的解决方案。将负载分布到多台 计算机上( 负载均衡) 是减少瓶颈的流行方法，而p 2 p 的核心思想就是资源的 分散化。 灵活的信息存放位置 分散化系统可将资源放到离其被访问位置更近的地方。这将带来多方面的好 处：因为网络延迟降低甚至完全消除，所以加快了响应速度；可对存储需求进行 分区，并用更有组织的方法分配存储请求。 对称和非对称参与 集中化系统受制于单点通信。绝大多数用户都联接到中心服务器上，并从中 心服务器接收或向中心服务器发送数据。因为集中化服务器的通信通道，所以一 般情况下，集中化系统没有为网络增加任何价值。而p 2 p 系统中建立了一个更 对称化的信息流。这个信息流允许设备与设备之间进行通信，从而提高了网络的 价值。 消除计算孤岛 集中化系统倾向于创建信息孤岛。这些计算孤岛被割断了与其他系统和网络 的联系，从而处于孤立状态。通常情况下，这些信息孤岛都存在冗余信息，这些 信息可能不是最新的并且可能不正确。 北京邮电大学计算机应用实验空 北京邮电大学硕：f ：j 学位论文 第二章技术背景 2 ) 费用和有效的资源分配与利用 客户机i n 务器系统的费用是非常昂贵的。这样的系统需要客户端软硬件， 也需要服务器软硬件，从而导致了过多的存储设备和软件，由此也导致了更多的 维护工作。p 2 p 大大提高了三类昂贵的技术资源的使用率： 存储设备 网络带宽 计算资源 在目前情况下，这些设备都没有得到充分利用，而传统的客户机i n 务器计 算模型正是导致这一结果的部分原因。尽管互联网已经实现了分散化，但客户机 j r 务器模式仍然占着统治地位。分散化和网状网络拓扑结构，将更有效地利用 现有资源。 3 ) 普及应用的计算和边缘服务 非p c 设备，比如p d a ( p e r s o n a ld i g i t a la s s i s t a n t ) 、蜂窝电话等设备，越来 越多。互连设备使新一代通信、信息交换和普及应用的计算成为可能。设备与设 备之间的直接通信( 不是通过作为设备通信媒介的服务器进行通信) 导致了连接 的迅速增长。p 2 p 类型的结构能支持不断增长的连接性。 连接性的提高加速了边缘服务的发展。边缘服务存在于整个互联网上的设备 和普通p c 上。p 2 p 网络能充分利用这些资源。作为一种网络缓冲机制，边缘服 务将数据移动到距离经常使用该数据的节点更近的地方。这既提高了数据访问速 度，又更好地利用了现有存储空间。 2 1 2 对等网络的分类及其比较 2 1 2 1 对等网络的分类 现有的对等网络可按结构特性和集中化程度分类 9 o 按结构特性可分为非结 构化对等网络和结构化对等网络。在非结构化对等网络中( 如g n u t e l l a 1 0 1 ) 中，对 等节点连接任意其他对等节点构成对等网络。数据放置与对等网络拓扑无关网络 拓扑是a dh o c 的。c h o r d 1 1 1 、t a p e s t r y 12 1 、p a s t r y 1 3 1 和c a n 1 4 1 则属于结构化对等 网络。这类网络提供了文件i d 和文件存储位置之间的映射关系，从而保证有效 路由并保证最终找到目标节点。 对等网络按集中化程度可分为纯对等网络和混合对等网络。纯对等网络( 如 北京邮电大学计算机应用实验室 北京邮电大学硕：l 学位论文第二章技术背景 f r e g n e t ) 采用完全分布的对等网络查找过程，网络中每个节点完全对等。节 一点在各方面( 如查询、+ 下载和路由等) 有相同的角色和责任。混合对等网络( 如 n a p s t e r 1 6 1 ) 则采用集中式资源查找方法，网络中节点责任不完全对等，处理z f j 匕l - , 力 强的节点作为其他节点的目录服务器。混合网络的特点是集中式查找，分布式下 载。 综上所述对等网络的分类如图2 1 所示。 图2 1 ：对等网络的分类 2 1 2 2 对等网络的比较 图1 1 所示的各类对等网络都各有优缺点【2 1 1 。混合对等网络采用集中式目录 服务器方式查找信息资源。这种查找方式的优点是查找效率较高且易于管理，但 集中式目录服务器容易成为单点故障和性能瓶颈。 非结构化对等网络的搜索过程类似于随机搜索过程。由于数据的放置与网络 拓扑无关，我们很难期望非结构化对等网络获得较优的查找路线。对等网络的消 息开销较大，女l l g n u t e l l a 3 2 】采用扩散( f l o o d i n g ) 的方式转发查找请求，并通过t t l 控制扩散的深度。非结构化对等网络的优点是对网络的动态性适应能力强；缺点 是当t t l 过小时，很难找到目标文件，而当t t l 过大时，由于消息数量随着路 由的深入呈几何指数增加，又会在网络上生成过多的查找消息。 结构化结等网络的数据放置与网络拓扑相关。结构化对等网络能保证路由有 效进行。但在非常动态的网络环境下，节点的频繁加入与退出需要较大的维护开 销，并且当节点退出以后，路由表没有及时重建也会导致查找失败。 2 1 3 对等网络的应用 对等网络引导网络计算模式从集中式向分布式偏移，也就是说网络应用的核 北京邮电大学计算机应用实验室 9 北京邮i ：【= ! l 大学硕：l 学位论文 第二章技术背景 心从中央服务器向网络边缘的终端设备扩散：服务器到服务器、服务器到p c 机、 p c 机到p c 机，p c 机到w a p 手机，所有网络节点上的设备都可以建立p 2 p 对话。 p 2 p 给互联网的分布、共享精神带来了无限的遐想，有观点认为至少有10 0 种应用能被开发出来，但从目前的应用来看，p 2 p 的威力还主要体现在大范围的 共享、搜索的优势上。在这方面主要引发了，或者是说更好地解决网络上四大类 型韵应用：对等计算| 、协同工作、搜索引擎、文件交换。 2 1 3 1 对等计算 通过众多计算机来完成超级计算机的功能，一直是科学家梦寐以求的事情。 采用p 2 p 技术的对等计算，正是把网络中的众多计算机暂时不用的计算能力连 结起来，使用积累的能力执行超级计算机的任务。任何需要大量数据处理的行业 都可从对等计算中获利，如天气预报、动画制作、基因组的研究等。 对等计算把原来需要超级计算机才能处理的庞大任务分散交给许许多多普 通计算机来执行。而1 9 9 9 年的s e t i h o m e 项目就是最著名、也是最成功的对 等计算项目之一。该项目大致的实现方式是：系统某个成员要运行一个计算任务， 就将它在系统中公告出来，其他成员在认为自身c p u 足够空闲的情况下，与该 成员联系，下载计算代码在自身上运行，计算结果返回给该成员。从本质而言， 对等计算就是网络上c p u 资源的共享。 2 1 3 2 协同工作 公司机构的日益分散，给员工和客户提供轻松、方便的消息和协作的工具， 变得日益重要。网络的出现，使协同工作成为可能。但传统的w e b 方式实现， 给服务器带来了极大的负担，造成了昂贵的成本支出。p 2 p 技术的出现，使得互 联网上任意两台p c 都可建立实时的联系，建立了这样一个安全、共享的虚拟空 间，人们可以进行各种各样的活动，这些活动可以是同时进行，也可以交互进行。 p 2 p 技术可以帮助企业和关键客户，以及合作伙伴之间建立起一种安全的网上工 作联系方式，因此基于p 2 p 技术的协同工作也受到了极大的重视。 。 2 1 3 3 搜索引擎 根据研究，世界每年大致产生2 e ( e ：1 0 1 8 = g g ) 字节的信息，但只有3 0 0 t ( t ：1 0 1 0 = k g ) 字节被发布出来，换句话说，每产生一兆字节的信息，只有 一个字节被发布出来。而g o o g l e 声称它只搜索了1 3 亿网页。因此，在现实的 北京邮电大学计算机应用实验室 1 0 北京邮电大学硕士学位论文 第二章技术背景 时间内找到有用的信息正变得越来越困难。 p 2 p 技术的另一个优势是开发出强大的搜索工具。p 2 p 技术使用户能够深度 搜索文档，而且这种搜索无需通过w e b 服务器，也可以不受信息文档格式和宿 主设备的限制，可达到传统目录式搜索引擎( 只能搜索到2 0 3 0 的网络资源) 无可比拟的深度( 理论上将包括网络上的所有开放的信息资源) 。 以p 2 p 技术发展的先锋g n u t e l a 进行的搜索为例：一台p c 上的g n u t e l l a 软 件可将用户的搜索请求同时发给网络上另外1 0 台p c ，如果搜索请求未得到满足， 这1 0 台p c 中的每一台都会把该搜索请求转发给另外1 0 台p c ，这样，搜索范 围将在几秒钟内以几何级数增长，几分钟内就可搜遍几百万台p c 上的信息资源。 可以说；p 2 p 为互联网的信息搜索提供了全新的解决之道。g o o g l e 己宣称要采用 p 2 p 技术来改进其搜索引擎。 2 1 3 4 文件交换 可以说文件交换的需求直接引发了p 2 p 技术热潮。在传统的w e b 方式中， 要实现文件交换需要服务器的大力参与，通过将文件上传到某个特定的网站，用 户再到某个网站搜索需要的文件，然后下载，这种方式的不便之处在于：一个是 成本高，第二是参与人数受和网络传输条件限制太大。电子邮件是方便了个人间 文件传递，却没法解决大范围的交换。这也是w e b 的重要缺陷。 而最新的p 2 p 软件可以让参与的每个人都成为交换平台，比如说软件 “e d o n k e y ”，当你搜索任何一种需要的计算机软件或者是音乐和视频文件时， 你会发现所搜集的可以支持下载的许多文件只是你所需要的片段，而你也可以同 时从各处下载不同的片段，同时，己经下载完的片段又可以提供他人做下载，这 样，传输的效率和成功率得到极大的提高，文件交换的需求也很轻松地延伸到了 信息的交换，在线拍卖也被赋予了新的形式，人们不必要到拍卖网站登记要卖的 商品了，在自家的硬盘上建个商店就可以了。由此又可以延伸到，一切中介网站 都会被替代。 2 1 3 5 其它应用 网络社区：任何有共同兴趣的群体，包括家庭或计算机业余爱好者，可利用 列表和一个网站来创建他们自己的互联空间。 电子商务：p 2 p 可增加新的功能，包括分布式连接和开通供应链链路，分发 信息、内容或软件，并利用中心目录或搜索功能使信息仍保留在原来的节点上。 北京邮电大学计算机应用实验室 北京邮电大学硕：卜学位论文第二章技术背景 一网络游戏：p 2 p 方式可为开发非集中控制的在线社区游戏提供一个自然平 台。开发人员可将重点放在游戏功能上，而不是与通信协议的接口上。制定游戏 规则的服务商由台前隐向幕后，把游戏的控制权完全交给普通用户，这样网民与 网民之间实现了真正直接、简单、自由的沟通。 2 1 4 对等网技术在应用中所遇到的主要问题 2 1 4 i 管理和版权 p 2 p 将原来的互联网模式完全打破，管理者再也无法对其用户进行必要的管 理，“无法无天”是p 2 p 目前最真实的写照。m p 3 交换仅仅是其最基本应用之一， 但已经给唱片工业带来毁灭性的打击，n a p s t e r 倒下了，可更多更新的m p 3 交换 服务出现了，它们功能更强大，方式更隐蔽。随之而来的是，影片、软件、稞密 数据等等，只要是计算机文件，都可以进行无节制的交换，这将给电影工业、软 件产业以及所有e 化的企业都带来巨大的隐患。对于政府来说，p 2 p 也使其对互 联网进行必要有序的控制管理变得非常困难，目前的技术手段和相关法律法规都 无法对其构成绝对的监督和威慑。 2 14 2 标准通信协议 目前基于p 2 p 技术进行开发的公司多如牛毛，其中不乏i n t e l 、s u n 、微软这 样的世界巨头，庞大商业潜力的诱惑驱使他们为p 2 p 标准进行着无休止的战争。 2 1 4 3 安全性和信任问题 安全是所有计算机系统的基本需求，尤其是基于因特网的系统，包括资源( 软 硬件) 安全、数据安全和通信安全。针对不同的安全机制，需要实现不同的加密、 授权、认证等机制。同时，开放性是p 2 p 最让人激动的地方，但将使黑客f 门得 到更自由、更庞大的施展空间。几乎目前所有的p 2 p 软件都存在安全隐患，而 目前安全厂商还无法对其进行有效的防护