（计算机系统结构专业论文）dht覆盖网若干基础性问题研究.pdf

摘要 摘要 分布式哈希表( d h t ) 是一种新的p 2 p 网络组网方式，具有高效、易扩展、低成 本等优点，广泛应用于各种大规模分布式系统，如文件共享、内容分发、流媒体、 v 0 口等。在这些系统中，由d h t 形成的覆盖网扮演着重要角色，支撑着上层各种 应用。因此，它引起了研究人员的广泛关注，已成为当前的研究热点。 论文对d h t 覆盖网在应用中亟待解决的一些基础性问题进行了深入的研究， 从分析d h t 网络的基本模型入手，研究了d h t 网络的管理范围( z o n e ) 均衡问题， 深入探讨了如何在d h t 网络中防御s y b i l 攻击，并对网络规模估计问题进行了建 模分析，提出了高效的随机节点选择算法。 论文的创新点及其贡献在于： 1 研究了线段随机分割问题，得出两个基本结论：在c h o r d 网络中，节点间 距近似服从指数分布，一段地址空间上出现的节点个数近似服从泊松分布。理论 分析和仿真数据表明，这两个结论的近似程度非常高，误差很小。这两个结论不 仅适用于c h o r d 网络，还适用于所有满足节点d 在网络中均匀分布假设的d h t 网络。它们是全文分析与建模工作的基础。 2 提出基于静态副本z o n e 均衡策略，推导出c h o r d 和p a s t r y 网络、虚拟服 务器( v s ) 和基于静态副本的z o n e 均衡策略下节点的负载分布。分析表明：c h o r d 、 p a s t r y 和v s 的z o n e 负载分布服从参数形式相似的伽马分布；在c h o r d 网络中k 个 后继节点上放置副本，节点z o n e 负载服从参数为( 七，刀) 的伽马分布。与v s 和基于 平衡树的z o n e 均衡策略相比，基于静态副本的均衡策略除了使节点z o n e 负载均 衡外，还具有使系统更鲁棒的优势。 3 提出一种d 自检验的安全框架( i s ，并结合洗牌策略高效抵御s y b i l 攻 击0 c s ) 。i s v 引入显式证书分发服务器( c d ) 对i d 申请进行审计，分发节点签名； 而身份验证工作由节点根据签名自行完成；有效降低了c d 服务器的开销。i c s 利 用c d 签发的票据记录节点加入过程，保证三轮替换规则强制实施；利用票据的替 换区间和发布时戳来判定i d 是否过期，防止敌手积累d 。论文对节点需要保存的 票据数量进行了定量分析，得出问题的近似闭合解；理论分析表明平均每个节点 上保存的票据数是o ( 1 0 9 2 力) ；仿真数据表明，该近似解具有很高的精度，说明了 理论分析的正确性。 摘要 4 指出在d h t 网络中估计网络规模等同于指数分布或泊松分布的参数估计 问题，提出基于平均f a - i 三( a i e ) 和基于节点密度( n d e ) 两种网络规模估计算法。论 文推导出a l e 和n d e 算法中网络规模估计值的概率分布，讨论了如何选择n d e 测量范围和测量位置等问题。分析表明：a l e 的测量精度只与测量间距个数相关， 与网络规模本身无关，具有自适应网络规模变化的特点。仿真实验证明a i e 算法 的测量误差完全符合理论分析结果。 5 提出一种基于取舍原则的d h t 网络随机节点抽样算法( r p s ) ，分析了单点 启发式算法( h u r ) 和多点启发式算法( h u r k ) 的抽样概率以及抽样间距的概率分 布，构造了一种服从倒数分布的取舍算法( p d r p ) 。分析表明：r p s 以等概率抽样 在线节点，抽样间距服从指数分布；r p s 的时间复杂度与网络规模无关，其复杂 度不随网络规模的增加而增加：网络规模估计误差给r p s 造成的影响与网络规模 本身无关；当网络规模估计值偏小时，会在一定程度上削弱r p s 的随机性。论文 采用统计检验和经验检验两类方法对相关分析做出了严格检验，结果表明r p s 对 于网络规模估计误差具有很好的容忍性，同时也证实r p s 是一种高效的随机节点 抽样算法。 关键词：p 2 p 网络、分布式哈希表( d h t ) 、系统建模、s y b i l 攻击、负载均衡、随 机节点抽样、网络规模估计 a b s t r a c t a b s t r a c t d i s t r i b u t e dh a s ht a b l e ( d h t ) i san e wp e e r - t o - p e e r ( p 2 p ) n e t w o r k i n gp a t t e r n , w h i c hh a sm a n ya d v a n t a g e s ，s u c h 鹊e f f i c i e n c y , s c a l a b i l i wa n dl o wc o s t , a n dh a sb e e n w i d e l yd e p l o y e di nv a r i o u sl a r g e s c a l e dd i s t r i b u t e ds y s t e m s ，r a n g i n gf r o mf i l es h a r i n g , c o n t e n t sd i s t r i b u t i o n , s t r e a m i n gm e d i at ov o mi ns u c hs y s t e m s ，t h eo v e r l a yf o r m e dw i 也 d h t p l a y sa ni m p o r t a n tr o l ei ns u p p o r t i n gt h eu p p e rl a y e ra p p l i c a t i o n s a sar e s u l t ，i t h a sd r a w nt h ea t t e n t i o no f m a n yr e s e a r c h e r s ，a n db e c o m e st h ec u r r e n tr e s e a r c hh o t s p o t t h i sd i s s e r t a t i o nm a i n l yf o c u s e so ns o m ef u n d a m e n t a lp r o b l e m st ob es o l v e di nt h e a p p l i c a t i o no fd h t s t a r t i n gf r o ma n a l y z i n gt h eb a s i cm o d e lo fd h tn e t w o r k , t h e d i s s e r t a t i o ni n v e s t i g a t e st h ez o n eb a l a n c ei nd h to v e r l a y , e x p l o r e sh o wt or e s i s tt h e s y b i la t t a c k sd e e p l y , m o d e l st h ep r o b l e mo fe s t i m a t i n gn e t w o r ks i z e ，a n dp r o p o s e s 肌 e f f i c i e n tr a n d o mn o d e s s a m p l i n ga l g o r i t h mo fd h to v e r l a y t h em a j o rc o n t r i b u t i o n so f t h i sd i s s e r t a t i o na r ea sb e l o w ： 1 田1 cd i s s e r t a t i o ni n v e s t i g a t e st h ep r o b l e mo fd i v i d i n gal i n er a n d o m l y , a n d d e d u c e st w ob a s i cc o n c l u s i o n s ：i nc h o r dn e t w o r k , t h ei n t e r v a lb e t w e e nn o d e so b e y st h e e x p o n e n t i a ld i s t r i b u t i o na s y m p t o t i c a l l y , a n dt h en u m b e ro fn o d e sa p p e a r i n gi nas e c t i o n o fa d d r e s ss p a c eo b e y st h ep o i s s o nd i s t r i b u t i o na s y m p t o t i c a l l y t h ea n a l y s i sa n d s i m u l a t i o ns h o w st h a tt h ea s y m p t o t i ca c c u r a c yo ft h e s et w ob a s i cc o n c l u s i o n si sv e r y h i 出a n dt h ee r r o ri sv e r yl i t t l e t h ec o n c l u s i o n sa r ea p p l i c a b l en o to n l yt oc h o r d ，b u t a l s ot oo t h e rt y p e so fd h tw h i c hs a t i s f i e st h ea s s u m e dc o n d i t i o nt h a tt h ei d e n t i f i e r sa r e d i s t r i b u t e du n i f o r m l yi nt h ea d d r e s ss p a c e t h e ya r et h eb a s i so fa n a l y s i sa n dm o d e l i n g o f t h et o t a ld i s s e r t a t i o n 2 t h ed i s s e r t a t i o np r o p o s e st h ez o n eb a l a n c i n gs c h e m eb a s e do ns t a t i cr e p l i c a , a n d d e d u c e st h ez o n el o a dd i s t r i b u t i o no fn o d e si nc h o r da n dp a s t r yn e t w o r k ，t h ev i r t u a l s e r v e r s s ) a n dt h es t a t i c - r e p l i c a - b a s e db a l a n c i n gs c h e m e t h ea n a l y s i ss h o w st h a tt h e z o n e1 0 a dd i s t r i b u t i o no fc h o r d ，p a s t r ya n dv so b e y st h eg a m m ad i s t r i b u t i o nw i t h s i m i l a rt y p eo fp a r a m e t e r s ，a n di fp u t t i n gr e p l i c ao nks u c c e e d i n gn o d e si nc h o r d ，t h e z o n el o a dd i s t r i b u t i o no b e y st h eg a m m ad i s t r i b u t i o nw i t hp a r a m e t e r ( k ，刀) c o m p a r e d i i i a b s t r a c t w i t hv sa n dt h et r i e - b a s e dz o n eb a l a n c i n gs c h e m e ，t h es t a t i c - r e p l i c a - b a s e ds c h e m ec a i l n o to n l ya c h i e v et h eb a l a n c eo fz o n ei o a d ，b u ta l s om a k et h es y s t e mr o b u s t e r 3 1 1 1 ed i s s e r t a t i o np r e s e n t sa ni d e n t i t ys e l f - v e r i f i e ds e c u r ef r a m e w o r k ( i s v ) ，w h i c h i sc o m b i n e dw i t hc a r d s s h u f f l i n gs c h e m e ( i c s ) t or e s i s ts y b i la t t a c k se f f i c i e n t l y a n e x p l i c i tc e r t i f i c a t ed i s t r i b u t o r ( c d ) i si n t r o d u c e di n t oi s v t oa u d i tt h er e q u i r i n gf o rn e w i d e n t i f i e r s ，a n dd i s t r i b u t es i g n a t u r e st on o d e s ，w h e r e a st h ev e r i f y i n go fi d e n t i t yi s c a r r i e do u tb yn o d e st h e m s e l v e s ，w h i c hr e d u c e st h eo v e r h e a do fc ds e r v e rg r e a t l y i c s m a k e su s eo ft h et i c k e t ss i g n e db yc dt or e c o r dt h ej o i n i n gp r o c e s so fn o d e st o g u a r a n t e et h ec o m p u l s i v ee x e c u t i o no fk - r o t a t i o nr u l e t op r e v e n tt h ee n e m yf r o m a c c u m u l a t i n gi d e n t i f i e r s ，i c su t i l i z e st h es u b s t i t u t i n gs e c t i o n sa n dp u b l i s ht i m e s t a m p s t od e t e r m i n ew h e t h e rt h ei d e n t i f i e ri so v e r d u e t h ed i s s e r t a t i o na n a l y z e sq u a n t i t a t i v e l y t h en u m b e ro ft i c k e t ss t o r e do nt h en o d e s ，a n dg i v e st h ea s y m p t o t i cc l o s e d - f o r m s o l u t i o no f t h ep r o b l e m t h ea n a l y s i ss h o w st h a tt h ea v e r a g en u m b e ro ft i c k e t ss t o r e do n e a c hn o d ei s o ( 1 0 9 2 疗) ，a n dt h es i m u l a t i o nd e m o n s t r a t e st h a tt h ea s y m p t o t i cs o l u t i o ni s v e r ya c c u r a t e , w h i c hi l l u s t r a t i n gt h ec o r r e c t n e s so ft h ea n a l y s i s 4 t h ed i s s e r t a t i o nc l a i m st h a tt h ep r o b l e mt oe s t i m a t et h en e t w o r ks i z ei si d e n t i c a l t ot h ep a r a m e t e re s t i m a t i o no ft h ee x p o n e n t i a lo rp o i s s o nd i s t r i b u t i o ni nd h t , a n d p r o p o s e st h ea v e r a g e - i n t e r v a l - b a s e de s 血n a t o r ( a i e ) a n dt h en o d e - d e n s i t y - b a s e d e s t i m a t o r ( n d e ) t h ed i s s e r t a t i o nd e d u c e st h ep r o b a b i l i s t i cd i s t r i b u t i o no ft h en e t w o r k s i z ee s t i m a t i o ni na l ea n dn d e ，a n dd i s c u s s e sh o wt os e l e c tt h et e s t i n gs c o p ea n d p o s i t i o no fn d e t h ea n a l y s i ss h o w st h a tt h ee s t i m a t i n ga c c u r a c yo fa i e i so n l yr e l a t e d t ot h en u m b e ro fi n t e r v a l sm e a s u r e d ，a n di si r r e l e v a n tt ot h en e t w o r ks i z e t h i ss h o w s t h a ta i ec a na d a p tt h ev a r i a t i o no f n e t w o r ks i z e t h es i m u l a t i o np r o v e st h a tt h em e a s u r e e r r o ri si nl i n ew i n lt h et h e o r e t i c a la n a l y s i se n t i r e l y 5 t h ed i s s e r t a t i o np r o p o s e sar a n d o mn o d es a m p l i n gs c h e m eb a s e do n 岣e c t i o n p r i n c i p l e ( r p s ) t h ep r o b a b i l i s t i cd i s t r i b u t i o u so ft h es a m p l e dp r o b a b i l i t ya n ds a m p l e d i n t e r v a la r ea n a l y z e da g a i n s tt h es i n g l ep o 砬h e u r i s t i cs a m p l i n ga l g o r i t h m ( h u r ) a n d t h em u l t i p o i n t sh e u r i s t i c s a m p l i n ga l g o r i t h m ( m i n k ) a n dar c j e c t i o na l g o r i t h m o b e y i n gt h er e c i p r o c a ld i s t r i b u t i o n ( r d r p ) i sc o n s t r u c t e d t h ea n a l y s i ss h o w st h a tr p s s a m p l e so n l i n en o d e sw i t he q u a lp r o b a b i l i t ya n dt h ei n t e r v a lb e t w e e nn o d e ss a m p l e d o b e y st h ee x p o n e n t i a ld i s t r i b u t i o n ；i t sc o m p l e x i t yr e m a i n sc o n s t a n tw h i l et h en e t w o r k s i z ei n c r e a s e s ；t h ei m p a c to f e s t i m a t i n ge r r o ro fn e t w o r ks i z eo nr p s i si r r e l e v a n tt ot h e i v n e t w o r ks i z ei t s e l f ；i ft h ee s t i m a t i o ni sl e s st h a na c c u r a t en e t w o r ks i z e ，r p sw i l ll o s e r a n d o m n e s st oac e r t a i nd e g r e e f i n a l l y , t h ed i s s e r t a t i o nu t i l i z e st h es t a t i s t i c a lt e s t i n g a n de m p i r i c a lt e s t i n gm e t h o d st ov e n f yt h ea n a l y s i ss t r i c t l y t h er e s u l ts h o w st h a tr p s i st o l e r a n tt ot h ee s t i m a t i n ga t o ro fn e t w o r ks i z ev e r ym u c h t h i sp r o v e st h a tl i p si sa n e f f i c i e n ts a m p l i n ga l g o r i t h m k e y w o r d s ：p 2 pn 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 ) ，s y s t e mm o d e l i n g , s y b i la t t a c k , l 0 a db a l a n c e ，r a n d o ms a m p l i n g ，e s t i m a t i o no fn e t w o r ks i z e v 部分术语和符号表 部分术语和符号表 术语名解释出现页码 d h i o v e r l a y 非结构化覆盖网 结构化覆盖网 z o n e s y b i l 攻击 路由表沾染度 c n s r n s p n s l n s b a s d i n e 资源的根节点 根节点失效检测 贪婪路由策略 r e c u r s i v er o u t i n g i t e r a t i v er o u t i n g m c h u m 叶集 会话时间 工作时间 停工期 s t a t i cr e s i l i e n c e 伸展度 v s d i s t r i b u t e dh a s ht a b l e ，分布式哈希表 1 4 覆盖网1 ，3 5 u n s t r u c t u r e do v e r l a y ，一类p 2 p 网络组成方式2 s t r u c t u r e do v e r l a y ，一类p 2 p 网络组成方式3 节点管理范围4 ，2 l ，3 5 利用d 来攻击p 2 p 网络的方案7 ，5 0 攻击节点在诚实节点的路由表项中所占比例 7 c o n s t r a i n e dn e i g h b o rs e l e c t i o n ，受限邻居选择8 , 5 5 r a n d o mn e i g h b o rs e l e c t i o n ，随机邻居选择8 , 5 5 p r o x i m i t yn e i g h b o rs e l e c t i o n ，物理邻近选择 8 l o n g - l i f en e i g h b o rs e l e c t i o n ，长寿邻居选择8 一种路由邻居更新策略8 ，5 5 管理资源发布信息的节点9 ，2 1 ，3 5 f a i l u r et e s t ，检验消息的目的地是否是资源根节点 9 始终选取与目的地最接近的节点作为下跳的路9 ，2 2 由策略 递归路由 9 迭代路由 9 n o n - t r a n s i t i v ec o n n e c t i v i t y ，非传递性连通 l l 由于节点加入退出而造成的p 2 p 网络动态性 1 l l e a f s e t ，p a s t r y 网络中节点的邻近邻居集合 l l 节点加入与退出之间的时间间隔 1 2 节点已在线时间 1 2 节点退出到下一次重新加入网络的时间间隔 1 2 静态容忍度 1 2 覆盖网与底层网络之间的匹配程度 1 3 v i r t u a ls e r v e r s ，虚拟服务器平衡方案 1 4 ，3 6 部分术语和符号表 搭便车 公共悲剧 t f r j “c p r e f i n g e r 表 s t a b i l i z e 后继指针列表 线段随机分割 p d f c d f m g f 自适应加入攻击 路由表沾染攻击 e c l i p s e 攻击 自举攻击 索引沾染攻击 d d o s 攻击 反射攻击 c a k 轮替换规则 i s v c d 仲裁集 i k e 自举服务节点 签名 加密摘要 a u d i t o 驱逐令 资源发布证书 节点只享受服务却很少提供服务的现象 网络资源被无节制的使用的现象 t i t - f o r - t a t ，一报还一报 c h o r d 网络中后继运算 c h o r d 网络中前驱运算 c h o r d 网络贪婪路由表 c h o r d 网络拓扑维护算法 存储多个连续后继指针的数组 以肛个均匀分布的点随机分割一条线段的问题 p r o b a b i l i t yd e n s i t yf u n c t i o n ，概率密度函数 o m a u l a t i v ed i s t r i b u t i o nf u n c t i o n ，累积分布函数 m o m e n tg e n e r a t i n gf u n c t i o n ，矩母函数 对d h t 的一种攻击方式 对d h t 的一种攻击方式 对d h t 的一种攻击方式 对d h t 的一种攻击方式 对d h t 的一种攻击方式 对d h t 的一种攻击方式 对d h t 的一种攻击方式 c e r t i f i c a t ea u t h o r i t y ，认证中心 即本文所称的洗牌策略 i d e n t i f ys e l f - v e r i f i e d $ e c u r ef r a m e w o r k ，i d 自验证 安全框架 c e r t i f i c a t ed i s t r i b u t o r ，证书发布服务器 对某个节点行为做出决议的节点集合 密钥交换协议 帮助节点加入网络的诚实节点 由c d 发布的节点m 身份认证信息 使用私钥对消息的哈希值加密的函数 审计操作 c d 发布的节点失效的签名 节点对它所发布资源的认证 x 1 4 1 4 1 5 2 1 2 4 2 2 2 4 2 4 2 6 2 6 2 6 4 2 5 0 5 0 5 0 5 0 5 0 5 0 5 1 5 2 5 2 ，6 l 5 3 5 5 5 7 ，5 9 5 6 5 6 5 7 ，6 3 5 7 5 8 5 9 6 0 部分术语和符号表 x i 插图索弓 插图索引 图1 1 n a p s t e r 网络拓扑2 图1 2 g n u t e l l a 的洪泛查询机制3 图1 3 d h t 算法原理4 图1 4 节点会话时间、工作时间、停工期1 2 图2 1 c h o r d 网络拓扑结构2 1 图2 2 c h o r d 网络单跳路由2 2 图2 3 c h o r d 网络f i n g e r 表与贪婪路由2 3 图2 - 4 刀一1 个点分割一条线段2 6 图2 5 ( 2 5 ) 式与指数分布函数的近似度2 8 图2 - 6 在不同网络规模下节点间距分布3 2 图2 7 在不同地址空间长度下，节点出现个数分布图3 4 图3 1 c h o r d 网络的z o n e 负载分布3 7 图3 2 在c h o r d 网络后继列表的节点上放置副本4 4 图3 3c h o r d 和p a s t r y 网络z o n e 负载对比4 6 图3 - 4 在不同k 值下v s c 中z o n e 负载分布。4 7 图4 1 三轮石子替换游戏6 3 图4 2 节点三轮替换加入过程6 3 图4 3 i d 过期判定示意图6 5 图4 4 初始分布求解6 7 图4 5 在不同网络规模下，随着覆盖圆弧数量( 五) 的增加，覆盖概率的变化7 0 图4 - 6 ( 4 - 2 5 ) 式的p d f 7 1 图4 7 在不同网络规模下e 6 】的计算值7 1 图4 8 网络规模为刀= 1 0 0 0 0 时，平均每个节点需要保存的票据数万= 2 刀的分布 7 2 图4 - 9 在不同网络规模( ，? ) 下，平均每个节点保存的票据数( 万：名刀) 7 3 图5 一1 等分圆周联合测量8 l 图5 2 n d e 算法中等分位置上的测量范围8 4 x i l 插图索弓 图5 3 邻居节点个数为s = 1 6 或s = 3 2 ，a i e 算法估计值的分布一8 6 图5 4 动态网络下的a i e 算法8 7 图6 1 随机节点抽样过程9 l 图6 2 当网络规模为，z = 1 0 4 ，s t d 与h u r 抽样几率的概率分布对比9 3 图6 3 h u r 算法抽样示意图9 4 图6 4 当网络规模为n = 1 0 4 ，h u r 与s t d 算法抽样间距分布对比9 4 图6 5 当网络规模为n = 1 0 4 ，h u r k 算法在线节点抽样几率的概率分布9 6 图6 - 6 h u r k 算法随机抽样示意图9 6 图6 7 h u r k 算法的抽样间距分布9 7 图6 8 r p s 抽样效率( 甩，。k ) 曲面1 0 1 图6 - 9 r p s 时i 日j 复杂度k 2 ( n l 。) 1 0 2 图6 1 0 网络规模估计误差( 万) 以及参数k 对，。配置概率的影响1 0 3 图6 1 1 s t s 1 8 参数配置1 0 5 图6 1 2 h u r 与s t d 抽样间距分布1 0 6 图6 1 3 。h u r k 抽样间距分布1 0 7 图6 1 4 r p s 算法时间复杂度1 1 0 图6 1 5 r p s 与p c 、a l 算法复杂度实测对比1 1 1 图a - 1 积分限的确定1 1 8 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：磊批签名：丛! = 二： 日期： 口听年6 月p 日 i 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：焉帆导师签名 日期：垆口1 1 年【月杪e l 第一章绪论 第一章绪论 对等网( p e e r - t o p e e r , p 2 p ) 技术兴起于本世纪初1 ，它是一种不同于c l i e n t s e r v e 模式的、全新的通信模型和应用模型。基于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 ) 作为新一代p 2 p 组网技术，具有广阔的应用前景，它 已逐渐渗透到各种p 2 p 应用中，对d h t 算法的研究是当前一个热点。 本章首先阐述p 2 p 技术的发展和演变，接着综述d h t 算法的研究现状，然后 说明本文选题依据和研究内容、以及本文贡献，最后列出全文章节安排。 i ip 2 p 技术发展 互联网自诞生以来，其网络规模一直在不断快速增长；据统计，目前接入互联 网的个人计算机( p c ) 数量已经达到六十多亿【l 】。同时，各种丰富多彩的应用层出不 穷，人们的生活和工作己与互联网紧密地联系在一起。 然而，面对互联网范围的大规模应用，传统的c l i e n v se ：r v e r 计算模式却越来越 难以提供有效技术支撑。在c l i e n t s e r v e r 模式下，服务器上存放着业务数据，处于 网络中心位置。应用规模的扩大使得服务器必须不断加大计算容量和网络带宽， 但是互联网的爆炸式增长使得这种扩容方式难以追上业务增长的需要，并且这种 模式也无法避免所固有的单点失效等问题。另一方面，p c 机技术按照摩尔定律在 飞速发展。今天的p c 机在计算能力和存储容量上与往日的服务器相比并不逊色， 甚至有过之而无不及；但是在c l i e l l t s e r v e r 模式下，这些p c 机的海量资源却由于 位于网络边缘而无法得到利用。呈现在人们面前的是一幅极不平衡的应用场景。 大规模互联网应用在技术上提出了可扩展性、鲁棒性、均衡性等要求，传统 c l i e n t s e r v e r 模式对此却显得无能为力，p 2 p 技术正是为解决这些问题应运而生。 在p 2 p 计算模式下，所有计算参与者组成一个网络，称为覆盖网j ( o v e r l a y ) ，这些 参与者之间地位平等，既是资源( 或者文件和数据) 的提供者，又是资源的获取者， 体现了一种“人人为我，我为人人的思想。 n a p s t e r 作为p 2 p 技术的开启者，产生于上个世纪末，它是一个m p 3 文件下载 1 实际上，早期i b m 的s n a 就属于对等网络，虽然与现在讨论的p 2 p 网络研究的技术有所不同 1 电子科技大学博士学位论文 程序。m p 3 文件分布在网络中参与者的机器上，n a p s t e r 服务器本身并不提供这些 m p 3 文件的下载，它提供的是m p 3 文件检索服务。当某个用户需要下载m p 3 文 件时，他先在n a p s t e r 服务器上检索拥有该文件的机器，然后直接从对应的机器下 载。n a p s t e r 程序一经发布以来，其应用规模在短时间内获得了爆炸似的增长。虽 然n a p s t e r 公司最终由于版权方面的原因而倒闭，但是一个小公司能在短时间内取 得如此巨大的成功，其原因却发人深省。 随之，n a p s t e r 程序背后隐藏的p 2 p 思想被发掘出来。商业上渴望复制n a p s t e r 成功经验的冲动、技术上相对于c l i e n t s e r v e r 的优势，这些因素驱使着p 2 p 技术 飞速发展；短短数年，p 2 p 技术就经历了几代变化： 9 图1 - 1 n a p s t e r 网络拓扑 1 集中式模式 其代表程序为n a p s t e r 。如图1 1 ，在这种模式下，系统设置一个中心服务器， 它维护整个网络中资源的目录。资源的查找由中心服务器负责，而资源的传输则 在节点之间直接完成。这种模式的优点是维护简单、资源发现效率高、检索方案 比较灵活。但是，在这种模式下，中心服务器的瘫痪容易导致整个网络的崩溃， 因此可靠性和安全性较低。并且随着网络规模的扩大，中心服务器的维护和更新 开销将急剧增加。 从原理上讲，由于有中心服务器的存在，集中式模式并非纯粹的p 2 p 系统；但 它实现了资源查询与传输的分离，节省了中心服务器的带宽消耗，减少了资源的 传输时延，因而成为p 2 p 技术初期应用的典范。 2 非结构化覆盖网( u n s t r u c t u r e do v e r l a y ) 其代表应用有c m u t e l l a 2 , 3 】和f r e e n e t 【4 】等。在这种模式下，系统不再设置中心服 2 第一章绪论 务器，每个节点随机选择其它节点作为邻居，所有节点构成了一个覆盖网。由于 节点之间的链路没有遵循特定拓扑结构，整个网络按照随机图组织，所以称为非 结构化覆盖网。 在非结构化网络发展初期，资源查询主要采用洪泛( f l o o d i n g ) 方式，图1 2 展 示了其工作流程。为查找某个文件，节点首先以广播方式向所有相邻活动节点发 送查询请求。邻居节点收到查询请求后，检查本地是否有符合条件的文件：如果 有，则沿该查询请求的逆向路径返回一个查询响应；如果没有，则将该查询请求 向自己的邻居转发，直到查询的t t l ( t i m et ol i v e ) 计数器减到0 为止。如果发起 查询的节点成功收到返回的响应，则直接与目标节点建立连接，下载文件。 非结构化网络面对网络的动态变化具有较好的容错能力，因而可用性比较好； 同时，它支持复杂查询，如带有正则表达式的多关键词查询、模糊查询等。与n a p s t e r 相比，g n u t e l l a 是更加纯粹的p 2 p 系统，它没有中心服务器；节点在c m u t e l l a 网络 中是真正的对等关系，既是客户机同时又是服务器，所以被称为s e r v e n t ( s e r v e r + c l i e n t ) 。但是，随着网络规模的增大，f l o o d i n g 查询方式将造成网络流 量急剧增加，使部分低带宽节点因过载而失效，导致网络的可扩展性不好【5 6 】。 图1 - 2 g n u t e l l a 的洪泛查询机制 d 3 结构化覆