（通信与信息系统专业论文）基于对等网络的有效路由研究.pdf

摘要 摘要 目前，互联网系统的模式正在发生从传统的客户机朋鼹务器( c l i e n t s e r v e r ) 模式到对等计算( p e e r - t o - p e e r ，亦简称p 2 p ) 模式的转交。p 2 p 的核心思想是所 有参与系统的节点( 指互联网上的计算机) 处于完全对等的地位，没有客户机和 服务器之分，也可以说每个节点既是客户机，也是服务器；既向别人提供服务， 也享受来自别人的服务。实际上，对等计算的概念在很早以前就已提出，但一直 没有受到广泛的重视，主要是因为没有实际运行的系统作为背景。产业界和研究 界都普遍认为在大多数情况下还是客户机服务器模式更为合理。然而，随着p c 技术和互联网( i n t e m e t ) 的发展，个人电脑的计算能力越来越强，接入带宽也逐 渐增大，如何更好地利用所有节点( 尤其是原先处于服务器地位的节点) 的能力 搭建更好的分布式系统自然而然地成为人们关注的问题。 事实上，p 2 p 已逐渐成为一种将来社会不可避免的计算模式，即：人人贡献 出自己的资源、人人享受他人提供的资源。或许这种模式将遇到网格模式( 即所 有资源和服务由某大型提供商提供，用户付费以获得资源并保证服务质量) 的竞 争，但是由于对等计算具有良好的可扩展性，可以对资源进行充分利用等优点， 必然会长期存在下去，会得到更广泛的应用空间。 因此，国际上各国研究小组对p 2 p 系统及如何增强p 2 p 系统的各种性能开 展了深入研究，并且产生很多成果。如：1 9 9 9 年推出并迅速得到普及的n a p s t e r ， 它采用了集中式的目录服务器机制，目录服务器中存放对等节点的地址信息和所 保存的数据的信息。而非结构的p 2 p 网络模型c m u t l l a 则采用完全分布式的策略 来实现数据放置和资源定位。2 0 0 1 年提出了以c h o r d 、c a n 、p a s t r y 和t a p e s t r y 等为代表的结构化覆盖网( s t r u c t u r e do 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 ht a b l e ，d h t ) 系统。这些系统的应用范围包括存储系统、d n s 系统、在线游戏、网页缓存、新闻组等等。 然而，p 2 p 台匀发展中也有许多关键技术有待解决和改善，如拓扑一致性与资 源定位、互操作性、安全加密、q o s 阀题等，其中用户如何在大量分散的节点中 找到需要的资源和服务即资源的查找与定位机制是关键技术的关键，也是研究的 一个热点。n a p s t e r 采用了集中式的目录服务器机制，目录服务器中存放对等节 点的地址信息和所保存的数据的信息。但随着用户数的增加，服务器仍将是系统 基于对等网络的有效路由研究 中的瓶颈和单一的故障点。非结构的p 2 p 网络模型g n u t l l a 采用完全分布式的策 略来实现数据放置和资源定位。但采用类似o s p f 的路由协议的泛洪机制，这种 协议的一方面造成的网络通信负担较大，另一方面，网络的可扩展性也较差。同 样d h t 也面i 临许多问题，s y l v i ar a t n a s a m y 等人在总结现有的d h t 路由算法的 基础之上提出了结构化对等网络面临着十五个主要问题。其中指出提高d h t 路 由效率是基于d h t 的p 2 p 研究的重点，而p 2 p 路由性能直接影响p 2 p 应用的推 广。由上可以看出，在p 2 p 的算法中，路由和数据定位方面也都存在明显的不足 和缺陷。因此本文从资源的定位和查找入手分别对非结构化的p 2 p 网络和结构化 的p 2 p 网络进行深入研究，提出改进方案，通过仿真验证改进前后的路由查找效 果。 本文的主要工作和创新点如下： 1 、将拓扑信息引入非结构化p 2 p 网络中，并利用非结构化p 2 p 网络的自身 特点对网络进行域的划分和超级节点的选择，从而提高查询的效率和成 功率，减轻网络的负担。在研究过程中，我们注意到，非结构p 2 p 网络 具有“幂规律”和“小世界”特征，因此网络有很高的聚合性，而现有 的非结构p 2 p 网络利用泛洪机制进行数据查询具有盲目性和随机性。因 此，利用聚合性对网络进行区域划分并按区域进行数据的查询是一个新 的尝试。 2 、提出了基于c h o r d 系统的双向资源放置和查询方法。在c h o r d 算法中， 数据只是存储于后继节点中，因此查询的过程也只能按顺时针方向进行。 即使数据的哈希值逻辑上离查询节点很近，只是因为在逆时针方向上， 所以查询可能要完成整个环的查询后才能查询到数据，而将数据和资源 进行双向存储和查询将能有效的减少查询的跳数和延迟。 3 、构建p 2 p 网络仿真系统，对改进后方案进行模拟和仿真，并给出仿真结 果和分析。 关键字：p 2 p 、c h o r d 、c m u t c u a 、超级节点、分布式哈希表 i i a b s t r a c t a b s t r a c t n o w a d a y s ，i n t e m e ts y s t e mi st r a n s f o r m i n gf r o mt h et r a d i t i o n a lm o d eo fc l i e n t $ e r v e ri n t op e e r 4 0 - p e e r ( p 2 pf o rs h o r t ) s y s t e m t h ec o r eo fp 2 pi st h a ta l lp a r t i c i p a n t c o m p u t e rp e e r s ( c e r t a i nc o m p u t e ra c c e s st oi n t e m e t1a r ee q u a lt oe a c ho t h e rw i mb o d i f f e r e n c eb e t w e e nc l i e n ta n ds e r v e r t h a ti s e v e r yp e e ri sb o t hc l i e n ta n ds e r v e r , t h e r e f o r ei to f f e r ss e r v i c et oo t h e rc o m p u t e r sa n dm e a n w h i l es h a r es e r v i c ew i t ho t h e r s t h ec o n c e p to fp 2 pw a sb r o u g h tf o r w a r de a r l i e r , b u tp e o p l eh a v ep a i dl i t t l ea t t e n t i o n t oi t ，m a i n l yb e c a u s et h e r ei sn op r a c t i c a ls y s t e ma sb a c k g r o u n d i t sp e r v a s i v e l y a c c e p t e db yi n d u s t r ya n dr e s e a r c hs c h o l a r st h a ts u c hm o d eo fc l i e n t s e r v e ri sm o r e r e a s o n a b l ei nm o s tc a s e s w i t ht h ed e v e l o p m e n to fp cs k i l l sa n di n t e m e t , t h e c o m p u t i n gp o w e ra n db a n d w i d t ho f p ci se n h a n c e dg r a d u a l l y , a c c o r d i n g l yi ta t t r a c t s t h em o s ta t t e n t i o nh o wt ob u i l dab e t t e rd i s t r i b u t e ds y s t e mb yf u l l yu t i l i z i n ga l lp e e r s ( e s p e c i a l l yt h o s ep e e r sw h i c ha 聆f o r m e rs c t v e c s ) p 2 pw i l lb e c o m ea l li n e v i t a b l ec o m p u t i n gm o d ei nt h ef u t u r e ，t h a ti s ，e v e r y p e r s o nc o n t r i b u t e sh i so w nr e s o u r c e s ，a n ds h a r e so t h e r s r e s o u r c e sm e a n w h i l e p 2 p m o d em a yb ec h a l l e n g e db ya n o t h e r 蓼i dm o d e ( a l lr e $ o b r c e sa n ds e r v i c ea r eo f f e r e d b yc e r t a i nm i g h t yp r o v i d e r , a n dc o u s u r f l e r $ h a v et op a yt oo b t a i ns u c hr e s o u r c e sw i t h r e a s s u r i n gs e r v i c eq u a l i t y ) d u et oi t sf i n ee x p a n s i b i l i t ya n dt a k i n gf u l la d v a n t a g eo f r e s o u r c e s p 2 pw i l le x i s ti n e v i t a b l yf o rl o n ga n db ea p p l i e dm o r ee x t e n s i v e l y i n t e r n a t i o n a l l y t h er e s e a r c h e rt e a n l sh a v em a d eg r e a ta c h i e v e m e n t sa r e r p e n e t r a t i n gi n t op 2 ps y s t e mt os t u d yh o wt oe n h a n c ev a r i o u sf u n c t i o n so fi t f o r e x a m p l en a p s t e r , d e v e l o p e di n1 9 9 9a n dt h e nw i d e s p r e a d ，a d o p t s ac e n t r a l i z e d d i r e c t o r y 截州e rw h e r et h ea d d r e s s si n f o r m a t i o no fe v e r ye q u a lp e e ra n ds a v e dd a t a i n f o r m a t i o na r es t o r i n g b u tc m u t u a , u n s t r u c t u r a lp 2 pn e t w o r kw h i c hs t o r e sd a t aa n d l o c a t ef i l e si nad i s t r i b u t e dw a y , d e v e l o p e ds t r u c t u r e do v e r l a yn e t w o r ki n2 0 0 1s u c ha s c h o r d ，c a n ，p a s t r ya n dt a p e s t r y , a n dd i s t r i b u t e dh a s ht a b l es y s t e m t h es y s t e mi s a p p l i e dt os t o r i n gs y s t e ma n dd n ss y s t e m ，o n l i n eg a m e ，w e b s i t eb u f f e r a n d n e w s g r o u pe r e h o w e v e rm a n y p i v o t a ls k i l l so f p 2 p a r es t i l la w a i t i n gs o l u t i o n sa n di m p r o v e m e n t , i l i 基于对等网络的有效路由研究 s u c h 豳t o p o l o g yc o n s i s t e n c y a n dr e s o l l r c 君s l o c a t i n g i n t e r o p e r a t i o n , s e c u r i t y e n c r y p t i o n , q o sa n do t h e rp r o b l e m s h e r e i n t or e s o u r c e ss e a r c h i n ga n dl o c a t i n g r e m a i n st ob et h ec r b xo f t h e n m t t e r , i e ，h o wt of i n do u tn e e d e dr e s o u r c e sa n ds e r v i c e a m o n gp l e n t i f u ls e a r e r e dp e e r sf o rc o r i s u l n e r s n a p s t e ra d o p t sae e n ：t r a l i z e dd i r e c t o r y s e r v e l fw h e r et h ea d d r e s s si n f o r m a t i o no f e v c r y e q u a lp e e ra n ds a v e dd a t ai n f o r m a t i o n a r es t o r i n g s e r v e rw i l lr e m a i nt h eb a r r i e ro fs y s t e mw i t hm o r ea n dm o r ec o n s u m e r s g n u t l l a m ，u n s t r u c t u r a lp 2 pn e t w o r km o d e la d o p t sat o t a l l yd i s t r i b u t e ds t r a t e g yt o i m p l e m e n td a t as t o r i n ga n dr e s o u r c e sl o c a t i n gb a s e do nf l o o d i n gs c h e m a , w h i c h r e s e m b l e so s p fr o u t i n gp r o t o c 0 1 t h i sp r o t o c o l b r i n g sa b o u tab i g g e rb u r d e no n n e t w o r kc o m m u n i c a t i o n ，a n daw o r s en e t w o r ke x p a n s i b i l i t yo nt h eo t h e rh a n d d h t a l s of a c e ss e r i e so fp r o b l e m s b a s e do rc u r r e n td h t r o u t i n ga l g o r i t h m , s y l v i a r a t n a s a m yp o i n t e do u t15 研m a r yi s s u e sf a c i n gs t r u c t u r a lp 2 pn e t w o r k h ei n d i c a t e d i n c r e a s i n gd h tr o u t i n ge f f i c i e n c yi st h ek e y s t o n eo fp 2 pr e s e a r c h , a n dp 2 pr o u t i n g c a p a b i l i t ya f f e c t sh o ww e l lp 2 pi sa p p l i e d t h ea b o v e m e n t i o n e dp a r ts h o w st h e r e e x i s t ss o m ed e f i c i e n ta n di m p e r f e c tp o i n t sc o n c e r n i n gp 2 pa l g o r i t h m t h e r e f o r et h i s p a p e rb e g i n n i n gw i t hr e s o u r c a 。sl o c a t i n ga n ds e a r c h i n gp e n e t r a t e si n t ou n s t r u c t u r a l p 2 pn e t w o r ka n ds t r u c t u r a lp 2 pn e t w o r k , a n ds u g g e s t s i m p r o v e dm e t h o d s t o a m e l i o r a t es e a r c h i n gb yt h ew a yo f e m u l a t ea n dv e r i f i c a t i o n t h em a i ni n n o v a t i o n so f t h i sp a p e ra r ea sf o l l o w s ： 1 w ea t t e m p tt oi n t r o d u c et o p o l o g ys k i l li n t ou n s t r u c t u r a lp 2 pn e t w o r k , a n dd i v i d e n e t w o r ki n t oc l u s t e r sa n dc h o o s es u p e rp e e r sa c c o r d i n gt oi t so w nc h a r a c t e r i s t i c s f o rm o r ee f f i c i e n ts e a r c h i n ga n dm u c hl i g h t e tb u r d e no nw e b s i t e w ef i n d u n s t r u c t u r a lp 2 pn e t w o r kp o s s e s s e st h ec h a r a c t e r i s t i c so f p o w e rl a w a n d “s m a l l w o r l d ，i e n e t w o r ko fh i g ha g g r e g a t i o n c u r r e n t l yi nu n s t r u c t u r a ln e t w o r kd a t a s e a r c h i n gb a s e d o nf l o o d i n gi sa i m l e s sa n dr a n d o m t h e r e f o r ei t san e w a t t e m p tt o d i v i d en e t w o r ki n t oc l u s t e r sf o rd a t as e a r c h i n gb a s e do na g g r e g a t i o n 2 w ei n t r o d u c eb i d i r e c t i o n a ls t o r i n ga n dd a t as e a c h i n gi nc h o r ds y s t e mb a s e do n d h t i nc h o r da l g o r i t h mp e o p l eh a v et os e a r c hd a t ac l o c k w i s es i n c ed a t aa r e s t o r e di ns u c c e s s i v ep e e r s l o g i c a l l yh a s hv a l u e sa r ec l o s et os e a r c hp e e r s ，b u t a n t i c l o c k w i s e ，s od a t ac a n n o tb ef o u n du n t i lt h ew h o l ep e e r sa r es e a r c h e d i v a b s t r a c t t h e r e f o r eb i d i r e c t i o n a ls t o r i n ga n dd a t as e a r c h i n gw i l le n a b l et ol e s ss e a r c hh o p s a n dd e l a y 3 w ec o n s t r u c tt h ee m u l a t i o ns y s t e mo fp 2 pn e t w o r kt oi m i t a t ea n de m u l a t et h e i m p r o v e ds c h e m aa n d t h e nc o m et ot h ee m u l a t i o nr e s u l t k e yw o r d s ：p 2 p , c h o r d ，c m u t e u a , s u p e rp e e r s ，d i s t r i b u t e dh a s ht a b l e v 基于对等网络的有效路由研究 p 2 p ： c ，s ： d h t o s p f t t l u 玎) p i d c a n g u d w w w b f s r t t 符号说明 p e e r t op e e r c l i e n t s e r v e r d i s t r i b u t e dh a s hm l b l e o p e ns h o r t e s tp a t hf i r s t t i i n et ol i v e u n i q u em e s s a g ei d e n t i f i c a t i o n p a t hi d e n t i f i c a t i o n c o n t e n ta d d r e s s a b l en e b o r k g l o b a l l yu n i q u ei d e n t i f i e r w o r i dw i d cw e b b r e a d t hf i r s ts e a r c h r o u n dt r i pt m a e v i 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得寄铛友友参或其他教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示谢意。 学位论文作者签名：易庳瑰 签字日期： 夕哆7 年午月，夕日 学位论文版权使用授权书 本学位论文作者完全了解砖狗敬欠学名关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和 借阅。本人授权摩旅大蘑封以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：饬囝绝 导师签名： 专了 签字日期：7 形7 年严月节日 签字日期：p “刁年崞月l 彳日 学位论文作者毕业去向： 工作单位：，留笨畎劳 电话： 口7 欲r 严 通讯地址：留承灭学柏扮教皆猡，邮编：列弦孑7 序论 第一章序论 1 1p 2 p 的概述 1 1 1 传统的网络模型 在p 2 p 网络模型使用之前，网络上广泛使用客户机服务器( c s ) 模型。这 种客户机和服务器模型是一种非对称式网络模式。该模式的基本思想是把集中在 一起的应用划分成为功能不同的两个部分，分别在不同的计算机上运行，通过它 们之间的分工合作来实现一个完整的功能。对于这种模式而言其中一部分需要作 为服务器，用来响应并为客户提供固定的服务；另部分则作为客户机程序用来 向服务器提出请求或要求某种服务。图1 1 为传统的客户机朋艮务器模型图。 图1 1c s 网络模型 客户机服务器系统相比文件服务器系统能提供更高的性能，因为客户端和 服务器端将应用的处理要求分开，同时又共同实现其处理要求，对客户端程序的 请求实现“分布式应用处理”。服务器为多个客户端应用程序管理数据，而客户 端程序发送、请求和分析从服务器接收的数据。相对于文件服务器而言，这是一 种“胖客户机( f a tc l i e n t ) ”，“瘦服务器( t h i ：ns e r w r ) ”的网络计算模式。在_ 个 客户机服务器应用中，客户端应用程序是针对一个小的、特定的数据集，如针 对一个表的行来进行操作的，而不是像文件服务器那样针对整个文件进行，对某 一条记录进行封锁，而不是对整个文件进行封锁，因此保证了系统的并发性，并 使网络上传输的数据量减到最少，从而改善了系统的性能。 客户机，服务器模型的优点主要在于： 1 、系统的客户端应用程序和服务器部件分别运行在不同的计算机上，系统 基于对等网络的有效路由研究 中每台服务器都可以适合各部件的要求，这对于硬件和软件的变化显示出极大的 适应性和灵活性，而且易于对系统进行扩充和缩小。 2 、在客户机服务器模型中，系统中的功能部件充分隔离，客户端的程序开 发集中于数据的显示和分析，而服务器的开发则集中于数据的管理。 3 、将大的应用处理任务分布到网络上许多低成本计算机上，带来费用上的 极大节约。 4 、发布信息的分布与生存期十分稳定。服务器只发布机器所有者想公之于 众的信息，这些信息将会在该服务器上稳定地保存一段时间，并且该服务器通常 也不间断地运行在网络上。 1 1 2 p 2 p 定义1 p 2 p 即p e e r - t o - p e e r ，通常又称对等网。p 2 p 由于允许网络中任一台计算机 可以喜接连接到网络中其他计算机，并与之进行数据交换，这样既消除了中间环 节，也使得网络上的沟通变得更容易、更直接。它其实是实现网络上不同计算机 之间，不经过中继设备直接交换数据或服务的一种技术。 图1 2 p 2 p 网络模型 p 2 p 作为一种网络的模型，它有别于传统的客户机服务器模型。客户机服 务器模型一般都有预定义的客户机和服务器。而在p 2 p 模型中并没有明确的客户 端和服务器，每一台计算机既可以看成是服务器，也可以看成是客户机；计算机 不仅接收数据，而且发送数据，不仅提出服务请求，而且接收对方的服务请求。 图1 2 为p 2 p 的网络模型。 p 2 p 并非新技术，而是旧技术新的应用模式。2 0 世纪7 0 年代中期，源于局 2 序论 域网中文件共享的p 2 p 技术就开始流行起来。w i n d o w s 中的网络邻居就是基于 p 2 p 技术的，通过网络邻居用户可以在局域网上共享伙伴机器中的文件内容，甚 至硬件设施，互联网最基本的t c p i p 协议也是对等的。在t c p i p 协议中，并没 有客户机和服务器的概念，在通讯过程中，所有的设备都是平等的一端。但是限 于当时p c 机性能，并基于易管理性和安全性的考虑，后来发展的架构在t c p i p 之上的软件大多采用了c s 模式的结构。但随着近年来计算机通信技术的飞速发 展，大量的个人计算机接入i n t e m e t ，从而导致i n t e r n e t 规模不断扩大，i n t e r n e t 入网的主机数、上两的人数都在飞速增长。另外，接入i n t c r n e t 的设备也变的多 样化，不仅有大型机、p c 机，而且出现越来越多的像手机和p d a 这样具有计算 能力的手持终端设备。很明显，网络边缘分布着大量的计算和存储资源。但是， 在传统的客户机服务器模式下，这些资源没有能够得到很好的开发和利用。因 而，如何有效地利用这些计算和存储资源也随之成为研究的热点，这也直接导致 p 2 p 研究的兴起。 1 1 3p 2 p 的特点 p 2 p 网络模型的引入和传统的客户机服务器的网络模型是分不开的，它具 有的独特优势，可以利用它来解决传统c s 模式存在的弊端，如服务器负担太重、 难以管理大量的客户机、系统性能容易不稳定、网络流量增加容易在服务器处产 生瓶颈、客户端对服务器程序依赖性强、只有少数服务器被使用，其他大量计算 机的存储、带宽等资源都被浪费了。 p 2 p 改变了网络“内容”所在的位置，使其从“中心”走向“边缘”，也就 是说内容不再存在于主要的服务器上，而是存在于所有用户的p c 机上。p 2 p 使 得p c 重新焕发活力，不再是被动的客户端，而是成为具有服务器和客户端双重 特征的设备。因此，p 2 p 技术避免了c s 结构带来的单点失效和性能瓶颈等问题， 它不依赖或尽可能不依赖中央服务器，使得每个参与节点既能作为服务器，也可 成为客户机。与c s 模式相比，p 2 p 模式有以下一些主要优点： 1 负载均衡。p 2 p 网络环境下可以根据策略灵活分布信息。负载均衡模块可 以监控各种信息的流量和请求率，然后重新分布这些信息以减轻单个节点 的负载。这种负载平衡策略可以提供分布式缓存才能实现的功能，且具备 简单和低价的特点。 基于对等网络的有效路由研究 2 信息资源丰富。任何p 2 p 网络用户能够扫描活动节点并搜索需要的信息， 然后直接从这个节点上下载信息。用户可以在他们的机器上把下载的信息 共享出来，这样，请求率高的文件能够很快的在许多节点上扩展开来。在 一个开放网络的环境下，p 2 p 网络能够很快积累相当丰富的信息。 3 信息在用户节点间直接流动，高速、及时、方便，降低了中转服务成本。 4 冗余和容错。p 2 p 网络的多个节点间的信息复制导致高度冗余，其直接结 果是提高了信息的可用性，使之为更多的用户提供服务。另外，冗余使得 网络不会产生“单点失效”问题，所以分散式的p 2 p 网络提高了网络的容 错和安全。 5 基于内容的寻址。在w e b 上，u r l 地址并不能反映它们的内容。但是p 2 f 网络上，存储特定信息的节点地址对用户是透明的，用户向网络提交查询 请求时，请求信息中便包括需要查询的信息，p 2 p 软件把请求转换成存放 这些信息的节点地址，所以把信息按照内容分类后再分布在网络上，这更 易于信息资源的查找。基于内容的寻址方式处于一个更高的语义层次，用 户在搜索时只需指定具有实际意义的信息标识而不是物理地址，这将创造 一个更加精炼的信息仓库和一个更加统一的资源标识方法。 6 有效的搜索。w e b 搜索的路由表存在一些问题，因为这些路由表依赖执行 程序在i n t e m e t 上进行搜索，相当于必须到信息存储巨大的、可扩展的数据 库中查找。这些路由表信息仅仅包括开放的服务器，并且数据库不会随着 网络状态动态更新而更新。但是在p 2 p 网络中，任何节点的信息只有当节 点在线时候才会被路由，因此路由表信息和网络状态是同步。p 2 p 网络不 依赖搜索程序重新访问链接来修改数据库路由表信息，这种动态信息路由 表和对信息的有效搜索使得p 2 p 具有显著的优势。 7 c s 模式下的互联网是完全依赖于中心点一服务器的。没有服务器，网 络就没有任何意义。而p 2 p 网络中，即使只有一个对等点存在，网络也是 活动的，节点可以随意地将自己的信息发布到网络上。 1 1 4p 2 p 的分类 p 2 p 的分类通常有两个划分标准：按集成度来划分和按p 2 p 网络结构的具体 实现方法来划分。 4 序论 1 、按集成度来划分川 按集成度划分，即按系统如何使用服务器在各个节点之问的相互交互来划 分。实际上，p 2 p 模式也不一定是完全无中心的，它可分为纯粹的p 2 p 和混合的 p 2 p 两类。纯粹的p 2 p 是指所有参与的计算机都是对等点，各对等点之间直接通 信，自始至终都没有中心服务器对对等点之间的信息交换进行控制、协调或处理。 混合式p 2 p 则依赖中心服务器执行一些功能。 ( 1 ) 纯粹式p 2 p 网络 弼络中没有专门的服务器。链状的节点构成一个分散的网络。通过基于对等 网协议的客户端软件搜索网络中存在的对等节点，节点之间不必通过服务器，可 以直接建立连接。这种p 2 p 网络模式的优点在于允许用户设定自己的规则和建立 自己的网络环境；不仅能够在i n t e m e t 下工作，而且对于l a n 和i n t r a n e t 也很有 用。但同时纯粹式p 2 p 网络也存在的一定的问题：由于没有中心管理者，网络节 点难以发现；不易管理和网络的安全性较差。此种类型的网络如：g n u t d l a 脚、 f r e e n e l o 等。 图1 3 纯粹式p 2 p 网络模型 图1 4 混合式p 2 p 网络模型 ( 2 ) 混合式p 2 p 网络 各个节点之间直接建立连接，但网络的构建需要服务器，通过集中认证，建 立索引机制。然而这里的服务器仅仅用于辅助对等节点之间建立连接，一旦连接 成功，服务器不再起作用，对等节点之间直接进行通信。这不同于c s 模式的服 务器，也弱化了服务器的作用。这种p 2 p 网络模式和纯粹式p 2 p 网络相比，更 易于发现网络节点，易于管理且安全性较好，但也有类似c s 模式的缺陷，容错 性较差等较为典型的有n a p s t e r “等。 2 、按p 2 p 网络结构的实现来划分 p 2 p 网络结构韵实现是指网络中的节点通过何种机制组成一个p 2 p 网络，以 基于对等吼络的有效路由研究 及在这个网络模型基础上文件的检索模型和机制。依据这种定义对现有的p 2 p 网络进行划分可以分为：非结构化p 2 p 网络和结构化p 2 p 网络。 ( 1 ) 非结构化p 2 p 网络 非结构化p 2 p 系统中，文件索引信息不再由集中式的目录服务器存储和管 理，而是分散到网络中，由节点自己保存。该类系统采用分布式的索引查找策略。 由于节点没有相关的文件定位，所以要查询网络中每个节点看是否有相匹配的文 件信息。为了查找网络中的文件，节点要随机地维护网络中的其他一些节点作为 邻居，以便通过邻居节点广播查询报文。另外非结构化p 2 p 网络中存在大量的数 据冗余，因而可以通过限制查询报文的t t l 值来使得泛洪仅仅发生在p 2 p 网络 的局部。 非结构化p 2 p 网络的优点是网络具有很强的动态性，节点可以随时离开和加 入网络，缺点是查找到理想的文件需要进行大范围的搜索。正因为如此，非结构 化的p 2 p 系统的可扩展性通常较差。典型的系统如g - n u t e l l a 2 、f r e c n e t 嵋1 等。 ( 2 ) 结构化p 2 p 网络 结构化的p 2 p 网络系统的出现主要是解决非结构网络可扩张性差的问题。这 些系统是由带有复杂拓扑结构的高度动态的网络节点组成，它是一个与连接不同 节点的物理网络无关覆盖网络。目前，比较典型的结构化p 2 p 网络系统主要是分 布式哈希表系统( 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 、p a s t r y 、c a n 和t a l 毙s t r y 等。d h t 的主要思想是：首先，每条文件索引被表示成一个( kv ) 对，k 称为关 键字，可以是文件名( 或文件的其他描述信息) 的哈希值，v 是实际存储文件的 节点的口地址( 或节点的其他描述信息) 。所有的文件索引条目( 即所有的( k ，v ) 对) 组成一张大的文件索引哈希表，只要输入目标文件的k 值，就可以从这张表 中查出所有存储该文件的节点地址。然后，再将上面的大文件哈希表分割成很多 局部小块，按照特定的规则把这些小块的局部哈希表分布到系统中的所有参与节 点上，使得每个节点负责维护其中的一块。这样，节点查询文件时，只要把查询 报文路由到相应的节点即可( 该节点维护的哈希表分块中含有要查找的假，v ) 对) 。这里面有个很重要的问题，就是节点要按照一定的规则来分割整体的哈希 表，进而也就决定了节点要维护特定的邻居节点，以便路由能顺利进行。这个规 则因具体系统的不同而不同，c a n 哪，c h o r d 嘟，p a s t r y 7 1 和t a p e s t r y 都有自 6 序论 己的规则，也就呈现出不同的特性。 图1 5 给出了一个分布式哈希表的示意图，可以看到每个节点都维护了哈希 表的一部分。d h t 实际上是把网络中所有的参与节点按特定的规则在应用层重 新进行组织，形成了一个结构化的逻辑的重叠网络( o v e r l a y ) 。这类系统不存在 单点瓶颈问题，因为每个节点除了既是客户又是数据服务器外，还提供目录服务 器的功能。又因为邻居节点是有目的有规则建立的，所以d h t 不需要在网络中 泛洪查询报文，而是按照相应的路由规则在系统中转发报文。d h t 在节点失效、 遭受攻击和突发性高负载面前都能表现出很好的健壮性；它具有良好的可扩展 性，能以较低系统开销获得较大的系统规模；可以自我配置，不需要手工干预就 可以自动把新加入节点合并到系统中；能提供简单灵活的接口，可以为多个应用 同时使用。 图1 5 分布式哈希表 但是目前d h t 还面临许多问题，s y l v i a r a t n a s a m y 等人在总结现有的d h t 路由算法的基础之上提出了结构化对等网络面临着十五个主要问题9 1 。其中指出 提高d h t 路由效率是基于d h t 的p 2 p 研究的重点，而p 2 p 路由性能直接影响 p 2 p 应用的推广。 1 1 5p 2 p 的应用领域“o “2 0 1 p 2 p 模式具有的独特技术特点使得这种模型在许多领域都得到广泛的应用。 7 基于对等网络的有效路由研究 目前p 2 p 主要应用范围分为三大类：通信协作、内容共享和分布式计算。具体的 应用领域包括：文件交换、对等计算、协同工作、搜索引擎、即时通讯和网络存 储等。 ( 1 ) 文件交换 传统的w e b 方式中，要实现文件的交换需要w e b 服务器的大力参与，通 过将文件上传到某个特定的网站，用户再到该网站搜索需要的文件，然后下载。 这就要求w e b 服务器能够对大量用户访问提供有效的服务，也成为w e b 应用 的瓶颈之一。而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 n e t 等。 ( 2 ) 对等计算 通过众多计算机来完成超级计算机的功能，这是科学家梦寐以求的事情。采 用p 2 p 技术的对等计算，是把网络中的众多计算机暂时不用的计算能力连接起 来，积累计算能力执行超级计算机的任务。任何需要大量数据处理的行业都可以 从对等计算中获利，如天气预报、动画制作、基因组的研究等，有了对等计算之 后，就无需昂贵的超级计算机了。应用实例有：d i s t r i b u t e 。n e t 和s e t i h o m e 等。 ( 3 ) 协同工作 协同工作是指多个用户之间利用网络中的协同计算平台来共同完成某项任 务，共享信息资源等。协同工作是w e b 更具人性化的特征，使用户可以按自己 的方式来和其他人共享信息，同时使得在不同地点的参与者可以在一起工作，因 为采用文件直接共享的方式可以保证系统中的每个人所获得的信息总是最新的， 同时节省了采用单独服务器时对该服务器存储以及性能的要求。g r o o v e 是基于 i n t e m e t 的p 2 p 协同应用软件的典型代表，其用户可以直接进行实时的协同工作。 ( 4 ) 搜索引擎 搜索引擎是目前人们在网络中检索信息资源的主要工具，目前的搜索引擎 如：g o o g l e 、天网等都是集中式的搜索引擎，人们在需要搜索信息的时候要向服 务器发出指令，由服务器把检索出来的相关目录通过一定的排序法则呈现在用户 面前，这就会不可避免的带来一些问题，比如：如果服务器信息更新周期长，将 有大量过时的信息产生；如果服务器不加鉴别，只是一味的搜集信息，将带来许 0 序论 多无价值的垃圾信息；受设备条件影响，服务器收集的信息有限；受服务器制约， 存在单点失效的问题等。 而p 2 p 将以用户为中心，所有的用户都是平等的伙伴。所有人都共享了他们 认为最有价值的东西，这将使互联网上信息的价值得到极大的提升。j x t as e a r c h 就是采用p