（计算机应用技术专业论文）结构化对等网络路由机制关键技术研究.pdf

博 ：学位论文 摘要 结构化对等网络是一种采用纯分布式的消息传递机制和根据关键字进行查找 的定位服务模型，目前在分布式存储、应用层多播、文件共享等领域已经得到广 泛应用。结构化对等网络路由算法研究面临许多问题，例如状态和效率的折衷、 拓扑失配、查询热点、结点异构等，如何解决这些问题具有重要意义。本文针对 结点异构、查询热点、降低系统负载等关键技术问题进行了较为深入的研究，论 文主要包括以下工作： ( 1 ) 普遍认为在结构化p 2 p 协议中实现能力感知会增加网络丌销，如何建立 高效、低开销的能力感知协议具有重要意义。分析了传统的结点通过周期性交换 路由表信息实现能力感知的算法，该算法收敛时间长且不可避免增大网络开销。 提出一种高效的能力感知协议h e t e r o c h o r d ，h e t e r o c h o r d 协议在结点的路由表建 立算法、更新算法、路由表维护算法中实现能力感知。h e t e r o c h o r d 协议在新结点 加入时即可计算出需要更新的其他结点，能力感知速度快、效率高。实验结果表 明，建立同样大小的网络，h e t e r o c h o r d 中结点更新算法产生的总开销远小于 c h o r d ；在动态环境下，h e t e r o c h o r d 具有比c h o r d 更小的维护丌销。 ( 2 ) 以h e t e r o c h o r d 为基础建立了一种虚拟双层结构化模型v r i n g ，v r i n g 的外 层是由所有结点组建的结构化h e t e r o c h o r d 网络，内层是由超级结点组建的c h o r d 网络。v r i n g 与目前典型的双层结构化网络模型不同的是：超级结点具有和普通结 点相同的路由表大小，仅比普通结点多维护一个超级叶子结点集，超级结点路由 表维护简单；单个超级结点失败不会造成其他结点脱离网络，不存在单点故障。 建立了三种v r i n g 的简单应用系统，通过实验测试了基于本地索引的非d h t 查找 方式的数据共享系统的查询特征。 ( 3 ) p 2 p 系统是一种分布式系统，降低系统负载对提高p 2 p 系统的扩展性具有 重要意义。目前结构化p 2 p 协议主要利用缓存方法解决查询热点问题，这些缓存 方法对数据缓存后的收益无法预测，是一种较盲目的缓存，往往导致系统负载加 重。提出一种结构化p 2 p 协议中的缓存计算模型，该模型以降低系统负载为目标， 结点采用一种文件访问统计方法跟踪查询本地文件的消息途经邻居结点的历史次 数，根据文件访问历史统计记录预测缓存该文件到邻居结点可能减少的查询负载， 然后与缓存后可能产生的更新开销对比，进而确定是否缓存文件到相应的邻居结 点。实验表明，该缓存计算模型可以有效降低系统负载。 ( 4 ) 仅采用虚拟服务器、多h a s h 技术或复制不能解决z i p f 查询环境下的负载 均衡问题。提出一种自适应负载均衡方法，方法采用一种被动式结点负载统计方 结构化对等网络路由机制关键技术研究 法生成局部负载视图；采用一种文件访问统计方法生成局部文件访问视图：当系 统内结点负载存在差异，重载结点把指向自身的逻辑链路迁移至指向局部负载视 图中的轻载结点，通过减小重载结点入度和增加轻载结点入度来减小结点间负载 差异；当结点的请求负载较高时，通过局部文件访问视图计算需要缓存的热点文 件及目标结点，降低承载热点文件的结点的请求负载。实验表明，在用户查询服 从z i p f 分布的环境下，自适应负载均衡方法可使结点负载达到较好的均衡。 ( 5 ) 分析了z i p f 查询下无状态限制的结构化p 2 p 协议的结点负载不平衡的形 成因素，提出一种适合于该类结构化p 2 p 协议的p l c 负载均衡方法，该方法采用 负载感知的被动式路由表维护算法和基于概率的路由算法提高轻载结点作为路由 中继结点的概率，并通过一种缓存机制来降低承载热点文件的结点的请求负载。 实验表明，在用户查询服从z i p f 分布的环境下，p l c 负载均衡方法可使系统达到 较好的负载均衡。 关键词：对等网络；分布式哈希表；异构；负载均衡；路由算法；负载感知；能 力感知 博 j 学位论文 a b s t r a c t s t r u c t u r e dp e e rt op e e rn e t w o r k sa r es e r v i c ed i s c o v e r ym o d e l st h a tu t i l i z ep u r e d i s t r i b u t e dr o u t i n gm e c h a n i s m sa n dd i s c o v e r yt h es e r v i c e sb yk e y , a n dt h e r ea r eal o t o fa p p l i c a t i o n sb u i l to nt h e m ，f o re x a m p l e ，d i s t r i b u t e ds t o r a g es y s t e m s ，a p p l i c a t i o n l a y e rm u l t i c a s ts y s t e m sa n df i l es h a r i n gs y s t e m s m a n yi s s u e sr e l a t i v e t or o u t i n g a l g o r i t h m sh a v eb e e nr a i s e di n s t r u c t u r e d p e e rt op e e rp r o t o c o l s ，f o re x a m p l e ， s t a t e - e f f i c i e n c yt r a d e o f f , q u e r yh o t s p o t s ，t o p o l o g ym i s m a t c h ，a n dh e t e r o g e n e i t y t h i s d i s s e r t a t i o nm a i n l yf o c u s e so nh e t e r o g e n e i t y , q u e r yh o t s p o t s ，a n dh o wt od e c r e a s e s y s t e ml o a di ns t r u c t u r e dp e e rt op e e rn e t w o r k s ，t h em a i nw o r k sa r ea sf o l l o w s ： ( 1 ) i ti sc o m m o n l yb e l i e v e dt h a te x t e n d i n gs t r u c t u r e dp e e rt op e e ro v e r l a y st ob e c a p a c i t y a w a r ew i l li n c r e a s em a i n t e n a n c eo v e r h e a d ，a n di t i si m p o r t a n tt ob u i l da c a p a c i t ya w a r ep r o t o c o lt h a ti se f f e c t i v ea n dh a sl o wm a i n t e n a n c eo v e r h e a d t h i sp a p e r a n a l y z e st h er e a s o nw h yt h et r a d i t i o n a lc a p a c i t ya w a r em e c h a n i s m si m p l e m e n t e db y e x c h a n g i n gr o u t i n gs t a t e sb e t w e e np e e r sh a v el o n gc o n v e r g e n c et i m ea n di n c r e a s e m a i n t e n a n c eo v e r h e a di n e v i t a b l y , a n dt h e n p r e s e n t sa n e f f e c t i v ec a p a c i t y a w a r e s t r u c t u r e dp e e rt op e e rp r o t o c o l - - h e t e r o c h o r d h e t e r o c h o r di m p l e m e n t st h ec a p a c i t y a w a r em e c h a n i s m si nt h e p e e r sj o i n i n ga l g o r i t h m ，u p d a t i n ga l g o r i t h m a n d m a i n t e n a n c ea l g o r i t h m s i nh e t e r o c h o r d ，t h ep e e r sw h o s er o u t i n gt a b l e ss h o u l db e u p d a t e dc a nb ec a l c u l a t e dw h e nan e wp e e rj o i n st h es y s t e m ，s ot h ec a p a c i t ya w a r e m e c h a n i s m sa r ee f f i c i e n t s i m u l a t i o nr e s u l t si n d i c a t et h a tt h eo v e r h e a do ft h eu p d a t i n g a l g o r i t h mt ob u i l da s a m es i z en e t w o r ki nh e t e r o c h o r di sf a rl e s st h a nt h eo v e r h e a do f t h eu p d a t i n ga l g o r i t h mi nc h o r d ，a n dt h em a i n t e n a n c eo v e r h e a do fh e t e r o c h o r di sl e s s t h a nt h a to fc h o r du n d e rc h u m 。 ( 2 ) t h i sp a p e rp r e s e n t sav i r t u a ld o u b l el a y e rs t r u c t u r e dp e e rt op e e rm o d e lc a l l e d v r i n gb a s e do nh e t e r o c h o r d t h eo u t e rl a y e rs t r u c t u r eo fv r i n gi sh e t e r o c h o r dw h i c h i n c l u d e sa l lp e e r s ，a n dt h ei n n e rl a y e rs t r u c t u r ei sc h o r dw h i c ho n l yi n c l u d e ss u p e r p e e r s t h e r ea r em a n yd i f f e r e n c e sb e t w e e nv r i n g a n do t h e rs u p e r p e e r - b a s e ds t r u c t u r e d m o d e l s i nv r i n g ，t h er o u t i n gt a b l e so fa l lp e e r sa r et h es a m es i z e ，a n dt h es u p e r p e e r s o n l ym a i n t a i nas u p e rl e a f s e tm o r et h a nc o m m o np e e r s ，s ot h em a i n t e n a n c ea l g o r i t h m o fs u p e r p e e r si ss i m p l e ，a n dt h e r ei sn os i n g l ep o i n to ff a i l u r e l a s t l yt h i sp a p e r p r o p o s e st h r e ea p p l i c a t i o nm o d e l sb a s e do i lv r i n g ，a n dt e s t st h ec h a r a c t e r i s t i c so fl o c a l i n d i e s - b a s e dd a t as h a r i n gs y s t e mb ys i m u l a t i o n i i i 结构化对等网络路由机制关键技术研究 ( 3 ) p e e rt op e e rs y s t e m sa r ed i s t r i b u t e ds y s t e m s ，a n dd e c r e a s i n gs y s t e ml o a di s i m p o r t a n tf o ri m p r o v i n gt h es c a l a b i l i t yo ft h es y s t e m s c a c h i n gi sa l w a y su s e dt o a c h i e v el o a db a l a n c ei ns t r u c t u r e dp 2 ps y s t e m sc u r r e n t l y , b u tn o n eo ft h ec u r r e n t c a c h i n ga l g o r i t h m sh a v em e c h a n i s m st oc o m p u t ew h e t h e rac a c h i n gi sw o r t h w h i l e ，s o t h ec u r r e n tc a c h i n ga l g o r i t h m sa r eb l i n d n e s sa n da l w a y si n c r e a s es y s t e ml o a d t h i s p a p e rp r e s e n t sac a c h i n gm o d e li ns t r u c t u r e dp e e rt op e e rs y s t e m s i no r d e rt or e d u c e s y s t e ml o a d ，t h i sc a c h i n gm o d e lu s e sap a s s i v ef i l er e q u e s t e ds t a t i s t i cm e t h o dw h i c h r e c o r d st h ec u r r e n ta c c e s s i n gt i m e so fe a c hn e ig h b o r ，a n dt h e ne s t i m a t e st h er e d u c i b l e q u e r yl o a do nt h ea s s u m p t i o nt h a tw ec a c h et h ef i l et oe a c hn e i g h b o r t h er e d u c i b l e q u e r yl o a da n dt h eo v e r h e a dc a u s e db yc a c h i n gd e t e r m i n ew h e t h e ri ti sw o r t h w h i l et o c a c h et h ef i l et oan e i g h b o r s i m u l a t i o nr e s u l t si n d i c a t et h ec a c h i n gm o d e lc a nr e d u c e s y s t e ml o a de f f e c t i v e l y ( 4 ) a l g o r i t h m su s i n gv i r t u a ls e r v e r , p o w e r 矽t w oc h o i c e s ，o rr e p l i c a t i o nc a i ln o t b a l a n c et h el o a do fp e e r su n d e rz i p f - l i k er e q u e s t sd i s t r i b u t i o n t h i sp a p e rp r e s e n t sa s e l f - a d a p t i v el o a db a l a n c i n ga l g o r i t h m ，i nw h i c he a c hp e e rc r e a t e sal o c a ll o a d d i s t r i b u t i o nv i e wu s i n gap a s s i v el o a ds t a t i s t i cm e t h o da n dal o c a lf i l er e q u e s t e dv i e w u s i n gf i l er e q u e s t e ds t a t i s t i cm e t h o d w h e nl o a di m b a l a n c ee x i s t si nt h es y s t e m ，t h e h e a v yl o a d e dp e e rw i l lm a k et h el o g i c a ll i n k sw h i c hp o i n tt oi t s e l ft op o i n tt oal i g h t l o a d e dp e e ri ni t sl o c a ll o a dd i s t r i b u t i o nv i e w , w i t ht h ei n d e g r e eo ft h eh e a v yl o a d e d p e e rd e c r e a s i n ga n dt h ei n d e g r e eo ft h el i g h tl o a d e dp e e ri n c r e a s i n g ，t h el o a d i m b a l a n c em a g n i t u d ew i l ld e c r e a s e w h e nt h er e q u e s tl o a do ft h eh e a v yl o a d e dp e e ri s h i g h ，t h ep e e rw i l lu s ei t sl o c a lf i l er e q u e s tv i e wt og e tt h ep o p u l a rf i l ea n dc a c h et h e f i l et oc o r r e s p o n d i n gt a r g e tp e e r s i m u l a t i o nr e s u l t si n d i c a t et h a tt h es y s t e mh a sag o o d l o a db a l a n c eu n d e rz i p f - l i k er e q u e s t sd i s t r i b u t i o ni fi tr u n st h eb a l a n c i n ga l g o r i t h m ( 5 ) t h i sp a p e ra n a l y z e st h er e a s o nf o rl o a di m b a l a n c eu n d e rz i p f - l i k er e q u e s t s d i s t r i b u t i o ni nu n l i m i t e d s t a t e p e r - n o d ea r c h i t e c t u r e ，a n dp r e s e n t sal o a d b a l a n c i n g a l g o r i t h mc a l l e dp l cf o rt h i sk i n do fs t r u c t u r e do v e r l a y s p l cu s e sl o a da w a r e r e a c t i v er o u t i n gs t a t em a i n t e n a n c es t r a t e g ya n dp r o b a b i l i t y b a s e dr o u t i n ga l g o r i t h mt o i m p r o v et h ep r o b a b i l i t yo ft h el i g h tl o a d e dp e e r sa st h ei n t e r m e d i a t ep e e r sf o r w a r d i n g m e s s a g e s ，a n du s e sac a c h i n gm e c h a n i s mt od e c r e a s et h er e q u e s tl o a do ft h eh e a v y l o a d e dp e e r st h a ts t o r e p o p u l a ro b je c t s r e s u l t sf r o mt h es i m u l a t i o ne x p e r i m e n t s i n d i c a t et h a tt h es y s t e mh a sag o o dl o a db a l a n c eu n d e r z i p f - l i k er e q u e s t sd i s t r i b u t i o ni f i tr u n spl ca l g o r i t h m k e y w o r d s ：p e e rt op e e r ；d i s t r i b u t e dh a s ht a b l e ；h e t e r o g e n e i t y ；l o a db a l a n c e ；r o u t i n g a l g o r i t h m ；l o a da w a r e ；c a p a c i t ya w a r e i v 结构化对等刚络路f 1 机制关键技术研究 插图索引 图1 1客户机服务器模式2 图1 2 对等计算模式2 图1 3p 2 p 网络层次划分4 图1 4p 2 p 协议分类图6 图1 5查询路径长度与路由表大小关系曲线9 图2 1c h o r d 路由表及路由机制示意图1 5 图2 2p l a x t o nm e s h 路由示意图18 图2 3p a s t r y 结点路由表示例2 0 图2 4k a d 路由表结构2 3 图3 1 h e t e r o p a s t r y 路由表学习示意图一2 7 图3 2h e t e r o c h o r d 拓扑结构2 9 图3 3结点加入算法伪代码3 0 图3 4 更新算法伪代码3 2 图3 5h e t e r o c h o r d 与c h o r d 的更新算法丌销对比3 6 图3 6h e t e r o c h o r d 与c h o r d 维护开销对比3 7 图3 7h e t e r o c h o r d 各类结点的维护丌销3 7 图3 8h e t e r o c h o r d 各类结点平均入度3 7 图4 1第一类典型的双层结构化模型4 0 图4 2 第二类典型的双层结构化模型4 0 图4 3h e t e r o c h o r d 结构图4 l 图4 4v r i n g 路由表稳定算法4 2 图4 5 漫步查找算法一4 4 图4 6 广播算法4 5 图4 7 漫步查找特征曲线4 6 图4 8 查询成功率4 6 图4 9 查询消息平均跳计数4 7 图4 1 0查询消息平均延迟4 7 图5 1查询消息路由特征示意图5 1 图5 2 文件部分成员5 3 图5 3反向结点访问文件的统计示意图5 3 图5 4 缓存示例5 4 博f j 学位论文 图5 5 图5 6 图5 7 图5 8 图5 9 图5 1 0 图5 1 1 图5 1 2 图5 1 3 图6 1 图6 2 图6 3 图6 4 图6 5 图6 6 图6 7 图6 8 图6 9 图6 1 0 图6 1 l 图6 1 2 图6 1 3 图6 1 4 图6 15 图7 1 图7 2 图7 3 图7 4 图7 5 图7 6 图7 7 图7 8 图7 9 图7 1 0 图7 1 1 拉模式缓存更新算法5 4 拉模式更新示例5 6 系统负载变化过程( n = 6 0 0 0 ，= 2 ) 5 7 系统平均负载( ，= 2 ) 5 7 跳计数( y = 2 ) 5 7 延迟( ，= 2 ) 5 7 跳计数( n = 6 0 0 0 ) 5 8 延迟( n = 6 0 0 0 ) 5 8 系统平均负载( n = 6 0 0 0 ) 5 8 最大负载结点与最小负载结点的请求负载和路由负载似= 0 ) 6 6 最大负载结点与最小负载结点的负载( 口= o ) 6 6 最大负载结点与最小负载结点的请求负载和路由负载( 撂= 1 ) 6 7 最大负载结点与最小负载结点的负载变化图( 口= 1 ) 6 7 自适应负载均衡方法示意图6 8 l o a d 数据结构6 9 结点数据结构6 9 逻辑链路迁移算法伪代码7 0 文件信息数据结构及部分成员函数7 l 结点文件表成员7 2 缓存算法7 3 结点平均负载分布7 4 结点负载最大值与最小值变化图7 4 平衡后最大负载结点与最小负载结点的负载变化图7 5 与缓存相关的各类消息的速率图7 5 b i c h o r d 路由示意图8 0 u n i f o r m 与z i p f 查询下平均负载分布对比( n = 1 0 0 0 ) 8 0 u n i f o r m 与z i p f 查询下最大负载结点的负载变化图( n = 1 0 0 0 萨1 ) 8 1 u n i f o r m 与z i p f 查询下的平均跳计数对比图8 l 基于概率的路由算法伪代码8 4 基于概率的路由示例8 5 文件访问统计示意图8 6 g r 和p r 算法下平均负载分布对比( _ 1 0 0 0w d w r = 2 ) 8 7 g r 和p r 算法下查询性能比较8 7 g r 和p r 算法下平均负载分布对 = l ( n = 1 0 0 0w d w ，= 1 0 ) 8 8 不同结点数量下最大负载与最小负载比值8 8 i x 结构化对等网络路由机制关键技术研究 图7 1 2 图7 1 3 图7 1 4 图7 15 不同权值下的最大负载和最小负载比值( n = 1 0 0 0 ) 8 8 p r 与b r 算法下平均负载分布对l 匕( n = 2 0 0 0 ) 8 8 p r 与b r 算法下查询性能比较8 9 p r 与b r 算法下的最大负载结点的负载变化图( n = 2 0 0 0 ) 8 9 x 博l j 学位论文 附表索引 表2 1c h o r d 结点路由表项1 5 表3 1 h e t e r o c h o r d 结点路由表和l e a f s e t 2 8 表3 2 实验参数设置3 5 表3 3结点能力分布3 5 表6 1基本实验参数设置6 5 表6 2 均衡算法实验参数设置7 3 表6 - 3 结点数不同的实验结果7 5 表6 4 缓存系数k 取不同值的实验结果7 6 表6 5 分布参数不同的实验结果7 6 表6 6 消息权值不同的实验结果7 6 博l ：学f 节论史 湖南大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其 他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果 由本人承担。 作者签名： 7 名伟 、，1 日期：7 - 口o g 年，7 月1 7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查 阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密毗 ( 请在以上相应方框内打“”) 作者签名： 导师签名： 梯 日期：2 纩占年j1 月夕日 日期：舻8 年i i 月f o - 昨l 么， 、， 博 j 学位论文 第1 章绪论 本章介绍了计算模式发展过程，概述了p 2 p 计算模式的定义、分类和应用， 概述了结构化对等网络路由算法研究面临的问题及目前的研究工作，最后简述了 本文主要研究工作及论文章节安排。 1 1 计算模式演变 1 1 1 大型机模式 从1 9 6 9 年计算机网络诞生到上个世纪8 0 年代个人台式机产生前，大型计算 机占据主导地位，但是数目有限并且价格非常昂贵，人们可以通过多终端连接共 享使用这些大型机，终端没有处理能力，只能用于输入数据和显示信息。为了尽 可能地利用大型机系统资源，一般采用多个作业集中到一台大型机上集中处理， 这种计算模式称为大型机模式，具有以下缺点：( 1 ) 单点故障。终端没有处理能力， 一旦主机出现故障，则系统停止运行；( 2 ) 主机价格昂贵；( 3 ) 扩展能力差；( 4 ) 可靠 性和可用性差。 1 1 2 客户机服务器模式 随着制造工艺技术不断进步，微型计算机的性能得到了进一步的提高，价格 也得到了逐步下降，用户的任务可以在不同的计算机上分布进行并统一管理。上 世纪八十年代，客户机月艮务器模式开始发展。在这种计算模式中，系统分成两 大部分：即服务器( s e r v e r ) 和客户机( c l i e n t ) ，服务器是功能强大、可靠的数据源， 客户机则一般为普通的、具有一定处理能力的计算机。c s 的基本工作方式是： 客户机发出请求，服务器接收请求并进行分析处理，然后将处理结果返回给客户 机。从上世纪9 0 年代开始，客户机服务器模式开始流行，到目前为止，这种计 算模式仍然是市场上的主流，例如w w w ( h t t p t 2 1 ) ，f t p 3 1 ，、e bs e r v i c e s 4 1 等均属 于这种计算模式。在该模式中，客户机具备一定的计算能力，但主要工作还是依 赖于服务器来完成。由于客户机n 务器模式将任务分布在多台机器上并行执行， 因此系统有更好的性能，但是客户机n 务器模式仍存在以下缺点：( 1 ) 服务器同时 为多台客户机提供服务并处理客户机的请求，因此服务器仍可能是性能瓶颈；( 2 ) 可扩展性不好。服务器的处理能力决定了系统的最大工作负载，而服务器的处理 能力很难有效伸缩；( 3 ) 单点故障。服务器易成为单点故障点；( 4 ) 需要管理。为使 服务器能够j l 顶, n 运行，服务器需要专业人员进行集中式维护、管理；( 5 ) n 络边缘 资源利用率低。c s 模式可以充分利用服务器资源，但客户机的资源没有得到充 结构化对等网络路由机制关键技术研究 分利用。图1 1 为客户机与服务器计算模式示意图，客户机发起请求，服务器响 应，操作均为单向。 客户机( c l i e n t ) 图1 1客户机服务器模式 服务器( s e r v e r ) 1 1 3 对等计算模式 近年来，不同资源的发展速度出现了以下特点：网络的流量以每6 个月翻倍 的速度增长，网络带宽以每7 个月翻倍的速度增长，计算资源近似依照摩尔定律 速度增长( 1 8 个月翻倍) ，而存储能力每年仅提升7 。因此在诸多资源中，计算和 存储资源可能逐渐变为“瓶颈”。在客户机服务器的计算模式下，处于体系架构 的中心服务器有可能成为性能的“瓶颈”，一旦中心服务器崩溃将造成整个服务系 统崩溃。目前，个人计算机已经得到较为充分的发展，接入带宽逐渐增大，这些 个人计算机在处理一般用户作业下，大部分计算、存储和带宽等资源都是闲置， 如何更好地利用所有结点( 尤其是原先处于服务器地位的结点) 的能力搭建更好的 分布式系统自然而然地成为人们关注的问题，在这样的背景下，人们引入了对等 计算模式。对等计算采用处于网络边缘的终端的协作来弥补和解决集中式架构导 致的性能“瓶颈，其核心思想是所有参与系统的结点( 指互联网上的计算机) 处于 完全对等的地位，没有客户机和服务器之分，也可以说每个结点既是客户机，也 是服务器，既向别人提供服务，也享受来自别人的服务。在对等计算模式中，资 源分布在各个结点中，不是集中在一个服务器中进行管理，结点之间通过直接交 互分享资源，结点可能随时加入网络和退出网络，具有良好的自治性。与客户机 服务器模式相比，对等计算模式可以是无中心服务器，具有更好的自组织性、扩 展性、容错性，并且能充分利用结点资源。对等计算模式可以理解为以前的无线 电通讯模式，从某种意义上来讲，对等计算模式并不是一种新的计算模式，早期 的a r p a n e t 也可以理解为对等网络【5 1 ，t c p i p 协议在设计时也没有客户机服务器 之分。图1 2 为对等计算模式示意图，与图1 1 不同的是，所有操作都可以是双向 的。 对等机( s e r v e n t ) 对等机( s e r v e n t l 图1 2 对等计算模式 对等网络( p 2 p ) 被美国财富杂志称为改变因特网发展的四大新技术之一。 博f j 学位论文 自1 9 9 9 年n a p s t e r f 6 j 推出后迅速普及，越来越多的p 2 p 软件发布和流行( 例如 g n u t e l l a 7 1 、k a z a a 8 】等) ，步步验证了对等计算思想的成功。据德国互联网调研 机构i p o q u e 称，p 2 p 已经彻底统治了当今的互联网，其中5 0 9 0 的总流量都来自 p 2 p 程序。事实上，对等计算已成为一种将来社会不可避免的计算模式，即：人 人贡献出自己的资源、人人享受他人提供的资源。或许这种方式将遇到网格( g r i d ) 方式( 所有资源和服务由某大型提供商提供，用户付费以获得资源并保证服务质量) 的竞争，但是由于对等计算具有良好的可扩展性，可以对资源进行充分利用等优 点，必然会长期存在下去，获得更广泛的应用空间。 目前，对于对等计算系统的设计方法和发展方向进行了广泛而深入的研究， 但由于人们对p 2 p 网络特征还认识不全、实验手段存在局限f 9 】，仍有很多的关键 问题并没有得到完善解决，对p 2 p 网络的研究必将长期进行下去。 1 2p 2 p 技术 1 2 1p 2 p 定义与特点 目前，在学术界、工业界对于p 2 p 没有一个统一的定义，下面列举几个常用 的定义供参考： c l a ys h i r k y ：p 2 p 是一类有效利用互联网边缘资源的分布式应用，这些资源包 括存储、计算、内容、服务等。访问这些分散的资源，就意味着要在连接不稳定 和i p 地址不可预见的环境里工作。由于网络上大量的结点工作在d n s 系统之外， 这些分散的资源具有不稳定的连通性和未知的i p 地址。因此，p 2 p 结点必须能够 独立于d n s 系统且高度自治【10 1 。 惠普实验室：p 2 p 为一类采取分布式方式利用分布式资源的应用【1 1 】。分布式 资源包括计算能力、存储、数据、网络带宽以及各种存在的可用资源。关键功能 可以是分布式计算、数据共享、通信与协作、平台服务。分布式的方式可以应用 到算法、数据、元数据或所有其他方面，但并不排除在系统或应用程序的某些部 分保留集中式的方式，典型的p 2 p 系统主要应用在互联网边缘或自助网络。 m i c h a e lm i l l e r ：p 2 p 是一个网络体系，每个结点具有同等的能力和责任【1 2 】。 m i l e r 定义了p 2 p 网络的五个关键特性： ( 1 ) 网络提供结点问实时的数据传输或者消息传递； ( 2 ) 结点即是客户端又是服务器； ( 3 ) 网络的内容是由分布的结点提供； ( 4 ) 结点具有网络控制权和自治权； ( 5 ) 网络允许不总是连接的结点和可能没有永久i p 地址的结点参与。 文献 1 3 ，1 4 概括了p 2 p 网络的三个主要特征：共享分布式资源和服务、无中 结构化对等网络路r f l 机制父键技术研究 心化、自治。 ( 1 ) 共享分布式资源和服务：每个结点既作为服务器为其他结点提供资源和服 务，也作为客户机向其他结点请求并获得资源和服务。这些资源可以为文件、信 息、带宽、存储、c p u 运行时间等任何东西。 ( 2 ) 无中心化( d e c e n t r a l i z a t i o n ) ：网络组织结构和结点通信、资源使用均没有 统一的中心协调权威机构，结点问通信直接进行。随着网络结点数量增多，服务 的需求和提供服务的能力同步得到了扩充，因此扩展性好；服务分散在各个结点 之间进行，部分结点加入、离开网络，结点均可以相互协作并保持结点的连通性， 具有良好的容错性能。 ( 3 ) 自治( a u t o n o m y ) ：每个结点自主决定共享的资源。 除了以上几个特点外，采用p 2 p 架构可以有效地利用互联网中散布的大量普 通结点，将计算任