（计算机系统结构专业论文）基于复杂网络理论的对等计算系统关键技术研究.pdf

基于复杂网络理论的对等计算系统关键技术研究 摘要 随着对等计算( p e e r - t o p e e r ，p 2 p ) 技术的迅猛发展、需求与应用的不断拓展、 用户数量的急剧增加以及交互方式的日益多样化，p 2 p 系统本身及其所处的网络环 境均呈现出爆炸式的复杂性增长( c o m p l e x i t ye x p l o s i o n ) 趋势。面对这种情形，当前 用于构造p 2 p 系统的思想、方法和技术正面临着严峻的挑战，p 2 p 系统中的安全问 题也愈加突出，亟需从新的角度理解网络的结构与网络的行为之间的关系，进而考 虑改善网络的行为，使之一方面能够真实反映和正确利用网络的结构特征，另一方 面能够更好地适应这种爆炸式的复杂性增长趋势。 从本质上看，具有上述高度动态性和复杂性的p 2 p 系统是一个典型的复杂网 络，其网络拓扑已被证实具有复杂网络的诸多基本特征。然而，该研究领域当前普 遍存在的问题是，在设计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 网络拓扑生成器：f i t g n u f i t g n u 通过以下几项改进措施来构造和生成拓扑：( 1 ) 显式地保持节点连接度 的幂律分布并支持幂指数的参数可控性；( 2 ) 引入竞争因素，采用基于广义适应 度的优先连接；( 3 ) 利用地理邻近信息构造局域世界连接和全局世界连接：( 4 ) 支持网络的增长( 新节点加入，老节点消亡) 和演化( 拓扑特钲指标的演变) 。 理论分析与实证研究表明，相对于b a 、m l w 等拓扑生成器，由f i t g n u 生 一i 一 上海交通大学博士学位论文 成的拓扑图能够更为准确和完整地再现g n u t e l l a 类型p 2 p 网络的无标度、小世 界、度度关联、聚类等高级拓扑特征，并具有更好的应用针对性和可操作性。 2 针对p 2 p 网络的行为控制与性能改善问题，提出了一种基于拓扑特征的可扩 展p 2 p 文件共享系统：t o a s t o a a 分别从以下几个方面对现有算法和协议实施改进：( i ) 针对资源放置问 题，提出了一种动态拓扑适应与演化算法d y t o p a ，使得网络拓扑能够主动地 适应网络中资源的分布状况和使用情况，并实现底层物理网络拓扑意识；( 2 ) 针 对资源定位问题，提出了种高效率的数据搜索算法s m a r t s e a r c h ，使得搜 索操作尽可能地仅在- - d , 部分“正确”节点上进行：( 3 ) 针对负载均衡问题， 提出了一种热点资源复制策略h o t r e p l i c a t i o n ，根据热点资源的实际使用情 况，自动执行数据复制和载荷迁移；( 4 ) 针对资源获取问题，提出了一种大尺寸 文件下载策略b i g d o w n l o a d ，实现基于软状态的主动接纳控制和资源预留， 以尽可能发挥p 2 p 系统的最大潜能，并提供一定程度上的q o s 保证。实验结果 表明，相对于b f s 、r w 、m r p 等系统，t o a a 在搜索效率、负载分布、对底 层物理网络的利用、以及拓扑演化质量等性能测度上均取得了明显的改善。 3 针对p 2 p 网络中蓄意攻击行为的安全保护问题，提出了一种基于拓扑特征的 分散式目标免疫策略：d e e p c u r e ；作为对d e e p c u r e 的功能扩充和性能 增强，还提出了一种基于本地h u b 的扼流机制：l h r t d e e p c u r e 在免疫目标的定义、免疫目标选取范围的确定、免疫方法的设计 等方面区别于现有的其它策略，使得其能够仅利用本地知识和仅免疫少量 关键节点，即可大幅度提高p 2 p 网络的抗蓄意攻击能力。实验结果表明，与 k 一、s a i 、l o c a l 三种免疫策略相比，d e e p c u r e 在免疫成本、免疫效率、可 扩展性、鲁棒性等多个测度上均获得了明显的性能增益。配合l h r t 扼流机 制，经适当延迟的d e e p c u r e 免疫策略能够有效应对网络中瞬时间大规模爆发 的病毒感染或恶意攻击，并有助于实现“主动免疫”的网络安全保护新理念。 对该领域研究进展的长期跟踪结果显示，专门从网络拓扑特征的角度，基于复 杂网络理论，集中地和系统地对p 2 p 系统中的上述关键问题展开研究，目前尚未见 有类似报道。从这个意义上讲，本文的研究：1 ：作具有一定的前瞻性和理论意义。 关键词：对等计算系统，拓扑特征，复杂网络，拓扑生成，拓扑适应，目标免疫 s t u d yo nk e yt e c h n o l o g i e so fp e e r - t o - p e e rc o m p u t i n g s y s t e m sb a s e d o nt h e o r i e so fc o m p l e xn e t w o r k s a b s t r a c t d u et oc x i l c m ed y n a m i c sa n dc o m p l e x i t y , p e e r - t o - p e e r ( r r 2 a ) c o m p u t i n gs y s t e m sc a n b e v i e w e da sr e p r e s e n t a t i v ec o m p l e xn e t w o r k s 。a n ds o m eo ft h e i rt o p o l o g i e sh a v eb e e np r o v e d t oe x h i b i ts t r o n gp o w e r - l a wd e g r e ed i s t r i b u t i o n sa n ds m a l l - w o r l dp h e n o m e n af o u n di nm a n y o t h e rc o m p l e xn e t w o r k s h o w e v e r , t h em a i nd i f f i c u l t yi nd e s i g n i n gs u c hs y s t e m si st h a tc u r - r e n t l y , v e r yl i t t l ei sk n o w na b o u tt h en a t u r eo ft o p o l o g i e so nw h i c ht h e yw o u l d b eo p e r a t i n g t h ee n dr e s u l ti st h a te v e ns i m p l ea l g o r i t h m so rp r o t o c o l s ，a si nt h ec a s eo fo n u t e l l a ，c o u l d r e s u l ti nc o m p l e xi n t e r a c t i o n st h a tc a na d v e r s e l ya f f e c ts y s t e mp e r f o r m a n c e i nt h i st h e s i s ，w ee y eo u rv i e w p o i n tu p o nt h e s et o p o l o g i c a lp r o p e r t i e sa n dc o n d u c ta l l e x t e n s i v es t u d yo nk e yt e c h n o l o g i e so fp 2 pn e t w o r k s ，b ym a n a g i n gt oa n s w e rt h ef o l l o w i n g q u e s t i o n so n eb yo n e ： h o wt oc h a r a c t e r i z et h e s et o p o l o g i c a lp r o p e r t i e sf o u n di nr e a l - w o r l dp 2 pn e t w o r k s a n d t h e nh o wt og e n e r a t et o p o l o g i e st h a tt r u l yp o s s e s ss u c hp r o p e r t i e s ? h o wt ob e t t e ru t i l i z et h e s ep r o p e r t i e st oi m p r o v et h ep e r f o r m a n c eo fp 2 pn e t w o r k s ? a n d h o wt of l l r t h e ru t i l i z et h e s ep r o p e r t i e st oe n h a n c ea t t a c k - s u r v i v a b i l i t yo fp 2 pn e t w o r k s i nc a s eo fv i r u ss p r e a d i n ga n dm a l i c i o u sa t t a c k s ? t h em a i nc o n t r i b u t i o n so ft h i st h e s i sa r e ： t oa n s w e rt h ef i r s tq u e s t i o n ，w ep r o p o s ef i t g n u ，an o v e lt o p o l o g yg e n e r a t o r , b yi n - t r o d u c i n gt e c h n i q u e sl i k e ( 1 ) e x p l i c i t l ys e l f - s u s t a i n i n gp o w e r - l a wd e g r e ed i s t r i b u t i o n sd u r i n g t o p o l o g ye v o l u t i o n ，( 2 ) f i t n e s s b a s e dp r e f e r e n t i a la t t a c h m e n t ，( 3 ) u t i l i z a t i o no fs e m a n t i cc l u s t e r i n ga n dd e g r e e - d e g r e ec o r r e l a t i o n ，( 4 ) c o n s i d e r a t i o no f b o t hl o c a ll i n k i n ga n dg l o b a ll i n k - i n gb a s e do ng e o g r a p h i c a lp r o x i m i t yb e t w e e nn o d e s ，a n d ( 5 ) a l l o w i n gn o d e s j o i n i n g o e a v i n g t h en e t w o r kd y n a m i c a l l y t h ef i t g n ut o p o l o g yg e n e r a t o rh a sb e e nv e r i f i e d ，t h e o r e t i c a l l y a n de x p e r i m e n t a l l y , t ob ea b l et og e n e r a t et o p o l o g i e st h a tc a ng i v eam o r ec o m p r e h e n s i v e a n dp r e c i s ec h a r a c t e r i z a t i o no ft o p o l o g i e so fr e a l w o r l dg n u t e l l a l i k ep 2 pn e t w o r k s 一i i i 上海交通大学博士学位论文 a s a r e s p o n s e t o t h es e c o n d q u e s t i o n ，w e p r o p o s e t o a a 。a n e w s c a l a b l e p 2 p f i l e - s h a r i n g s y s t e m t ot a c k l es e r i o u ss c a l i n gp r o b l e m so f c u r r e n tu n s t r u c t u r e dp 2 pn e t w o r k s t h e k e yi d e a o ft o a 3i st op r o d u c ea l lo v e r l a yt o p o l o g yw i t hd e s i r a b l ep r o p e r t i e s ，a d a p tp e e r st o w a r d s b e t t e rn e i g h b o r sa n dd i r e c tq u e r i e st or i g h tn e x th o p s ，w i t ha sf e wd u p l i c a t e dm e s s a g e s a sp o s s i b l e t oa c h i e v et h i sg o a l ，s e v e r a li n n o v a t i v et e c h n i q u e sa r ci n t r o d u c e di n t ot o a 3 ： ( 1 ) d y t o p a ad y n a m i ct o p o l o g ya d a p t a t i o na l g o r i t h m , ( 2 ) s m a r t s e a r c h ah i g h - p e r f o r m a n c es e a r c ha l g o r i t h ms p e c i a l l y - d e s i g n e df o rd y t o p a 。( 3 ) h o t r e p l i c a t i o n a h o t - d a t ar e p l i c a t i o ns t r a t e g yd e s i g n e df o rb e t t e rl o a db a l a n c i n g ，a n d ( 4 ) b i g d o w n l o a d a l le f f i c i e n tq o s - p r o v i s i o n i n gs t r a t e g yf o rl a r g e s i z e df i l ed o w n l o a di np 2 pe n v i x o n n w m 蕊l w e d e p l o ya n dc o m p a r et o a aw i t ht h eo t h e r t h r e ee x i s t i n gp 2 ps y s t e m so v e rb o t hs t a t i ca n d d y n a m i ce n v i r o n m e n t s ，a n dt h er e s u l t sp r o v es i g n i f i c a n tp e r f o r m a n c eg a i n so ft o a s t oa n s w e rt h el a s tq u e s t i o n , w ep r o p o s ed e e p c u r e ，an o v e lt a r g e t e db u td e c e n t r a l i z e d i m m u n i z a t i o ns t r a t e g y , t od e f e n s ei n t e n t i o n a la t t a c k si ns c a l e - f r e ep 2 pn e t w o r k s d i f f e r e n t f r o me x i s t i n gs t r a t e g i e s ，d e e p c u r ei d e n t i f i e si m m u n i z a t i o nt a r g e t sa sn o to n l yt h em o s t h i g h l y - c o n n e c t e dn o d e s b u ta l s ot h en o d e sw i t hh i g h e s ta v a i l a b i l i t ya n d o rh i g h e s tl i n kl o a d , w i t ht h ea i mo fi n j e c t i n gi m m u n i z a t i o ni n f o r m a t i o ni n t oj u s t 哟h tt a r g e t st oc u r e t ob e t t e r t r a d eo f f t h ec o s ta n dt h ee f f i c i e n c y , d e e p c u r ed e l i b e r a t e l ys e l e c tt h e s et a r g e t sf r o m2 - l o c a l n e i g h b o r h o o d , a sw e l la st o p o l o g i c a l l y - r e m o t eb u ts e m a n t i c a l l y c l o s ef r i e n d si fn e e d e d t o r e m e d yt h ew e a k n e s so fe x i s t i n gs t r a t e g i e si nc a s eo fs u d d e ne p i d e m i co u t b r e a k , d e e p c u r e i sa l s oc o u p l e dw i t hl h r t ，al o c a l h u bo r i e n t e dr a t et h r o t t l i n gm e c h a n i s m ，t oe n f o r c ep r o a c - f i v er a t ec o n t r 0 1 e x t e n s i v es i m u l a t i o nr e s u l t ss h o wt h a td e e p c u r eo u t p e r f o r m si t sc o m p e t i - t o t s ，p r o d u c i n ga na r r e s t i n gi n c r e a s eo ft h en e t w o r ka t t a c kt o l e r a n c e ，a tal o w e rp r i c eo f e l i m i n a t i n gv i r u s e so rm a l i c i o u sa t t a c k s t h e w o r kc o n d u c t e di nt h i st h e s i si s ，t oo u rb e s tk n o w l e d g e ，t h ef i r s ts t u d yi nt h i sa r e a t oa p p l yt h el a t e s tt h e o r i e so fc o m p l e xn e t w o r k st oa l lo ft h ea b o v ef i e l d s ，a n dt oi n v e s t i - g a t ei n t r i n s i cm a t t e r st h a th i n d e rt h ei m p r o v e m e n to ft h ef u n c t i o n a l i t ya n dp e r f o r m a n c eo f g n u t e l l a l i k ep 2 ps y s t e m sw i t hav i e w p o i n to ft o p o l o g i c a lp r o p e r t i e st h r o u g h o u tt h et h e s i s k e yw o r d s ：p e e r - t o p e e rc o m p u t i n gs y s t e m s ，t o p o l o g i c a lp r o p e r t i e s ，c o m p l e xn e t - w o r k s ，t o p o l o g yg e n e r a t i n g ，t o p o l o g ya d a p t a t i o n ，t a r g e t e di m m u n i z a t i o n i v 插图索引 图1 1 应用层覆盖网络及其路由过程示意图 图1 2 客户机，服务器计算模式与对等计算模式对比 图1 3 对等计算系统网络分层通信架构 图1 4 n a p s t c r 体系结构示例 图1 5g n u t e l l a 的资源定位和获取方式 图1 6 f r e e n e t 中典型的文件搜索过程， 图1 7f a s t t r a c k 的文件查找过程 图1 8 基于分布式哈希表机制的结构化p 2 p 系统应用程序接口示意图 图1 9 一个拥有5 个节点的2 维空间c a n 拓扑 图1 1 0 在一个拥有6 个节点的2 维c a n 网络中新节点7 的加入过程 图1 - 1 1 在拥有1 0 个节点、5 个数据项k e y 的c h o r d 环中的一个查找过程 图1 1 2p r r 路由示例：节点0 3 2 5 到节点4 5 9 8 的路由过程如图中粗线所示 图1 1 3p a s t r y 网络中节点的路由表、路由状态以及路由过程示意 图1 1 4k a d e m l i a 二叉树构造及路由查找过程 图1 1 5 在一个简化的v i c e r o y 网络中节点a 查找节点b 的过程 图1 1 6p 2 p 系统路由表尺寸与网络直径权衡渐进曲线 图1 1 7 随机故障和蓄意攻击对g n u t e l l a 网络拓扑连通性的影响 图2 1 不同类型网络的例子：( a ) 无向网络，( b ) 有向网络，( c ) 加权网络。 图2 2 两类小世界模型示意图：( a ) 随机化重连( w s 模型) ，c o ) 随机化加 边( n w 模型) 图2 3b a 无标度网络的演化( m = m o = 2 ) 图2 4 g n u t e l l a 网络的社团结构示意图 图2 5 b a 、m l w 、f i f g n u 和真实g n u t e l l a 拓扑的c c d f 曲线 图2 6b a 、m l w 、同g n u 和真实g n u t e l l a 拓扑的特征路径长度比较 图2 7 b a 、m l w 、雕g n u 和真实g n u t e l l a 拓扑的聚类系数比较， 图2 8b a 、m l w 、雕g n u 和真实g n u t e l l a 拓扑的度一度关联特性比较 一t x 一 2 2 6 8 8 9 m 挖 b m 塔 垢 侉 筋 撕 鲫仉钙矾贷 上海交通大学博士学位论文 图3 1t o a 3 系统的网络节点在动态拓扑演化过程中保持节点出度不变性的 方式示意图。 7 5 图3 2 平均随机搜索时间f 随地理邻近因子p 的变化关系 8 l 图3 3h o t r e p l i c a t i o n 复制策略的参考网络模型 8 6 图3 a h o t r e p l i c a t i o n 策略的数据复制过程示意图8 7 图3 5b f s 、r w 、m r p 、t o a 3 四个系统的平均查找成功率比较 9 4 图3 6b f s 、r w 、m r p 、t o a 3 四个系统搜索效率比较：( a ) 查全率；( b ) 产 生的消息量 9 5 图3 7h o t r e p l i c a t i o n 热点资源复制策略对网络中负载分布的影响9 6 图3 8 查询结果的平均物理延迟p h y s i c a ll a t e n c y 与该结果的p o p u l a r i t y 水平 之间的变动关系。 9 7 图3 9 四个系统分别对应的稳态网络拓扑的m e a ns t r e s s 随网络规模的变化 曲线9 8 图3 1 0 t o a 3 网络拓扑的小世界特性验证 9 9 图4 1 落在d 跳范围内节点的平均数目j 占网络总节点数的比例( n ) 与 d 、n 之间的关系1 1 l 图4 2 感染比例i 和易染比例s 的时间演化曲线1 1 4 图4 3 四种策略的免疫成本曲线与免疫临界值实验结果比较1 1 9 图4 4 四种策略的免疫效率实验结果对比1 2 0 图4 5 四种策略的可扩展性实验结果对比1 2 1 图4 ，6 四种策略的可扩展性实验结果对比+ 1 2 1 图4 7d e e p c u r e 免疫策略对免疫节点初始选取比例p 取值的敏感性 1 2 2 图4 8 针对特定免疫日标节点的蓄意攻击对网络级联故障发生概率和扩散 速度的影响。1 2 3 图4 9 三类免疫目标对d e e p c u r e 免疫策略性能的贡献( w i t h n o n 和 w i t h o u t n o n ) 1 2 4 图4 1 0 远程朋友节点对d e e p c u r e 免疫策略性能的贡献1 2 4 图4 1 1 基于本地h u b 的扼流机制l h r t 的作用验证1 2 5 一x 一 表格索引 表1 1p 2 p 计算系统综合比较1 8 表3 1t o a 3 仿真模拟实验中所使用的缺省参数值9 1 表3 2 t o a 3 仿真模拟实验中初始网络的存储内容及其分布 9 2 表4 1 免疫策略仿真模拟实验中所使用的缺省参数值1 1 6 上海交通大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集 体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个人和集体，均已 在文中以明确方式标明。本文完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期： 上海交通大学学位论文版权使用授权书 本学位论文作者完全了解上海交通大学有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 ( 保密的论文在解密后应遵守此规定) 学位论文作者签名：撕 日期2 珥年阜月他日 指导教师签名：爱馥 日期：啤年单月且日 第一章绪论 对等计算( p e e r - t o - p e e r ，亦简称p 2 p ) 系统是构筑在现有网络之上，由节点和逻 辑链路组成的一种虚拟的覆盖网络( o v e r l a yn e t w o r k s ) 。建立覆盖网络的目的是为 了屏蔽物理网络的结构差异和功能限制，以一定的资源开销为代价，实现现有网络 基础设施目前尚不能提供的某些网络服务和应用需求。 覆盖网络的概念并非最近才出现，早期的广域计算机数据网络就是建立在公众 电话网( p s t n ) 之上的一种覆盖网络。后来，为了实现局域网络互联，在数据链路 层的数据帧中增加协议头，就构筑了现在的基于网络层的覆盖网络：i n t e r n e t 。本 文下面所要研究的对等计算系统则是指建立在i n t e m e t 传输网络基础之上，由端主机 节点和应用层逻辑链路构成的完全位于应用层的覆盖网络系统。 1 1 研究背景与课题意义 i n t e m e t 的“边缘论”原则( e n d - t o - e n da r g u m e n t s ) 【l 】认为，某项功能除非在 底层实现可以获得性能上的极大收益，超过了因为底层复杂性增加而形成的开 销，否则就应该将该功能提升到更高层来实现。概括地讲，即“简单网络，智能边 缘( s i m p l en e t w o r k s m a r te d g e ) ”。这个原则就是( 而且现在依然是) 现代互联网 络的基本设计思想。近年来，随着网络技术的成熟以及计算机处理能力和网络带 宽的快速提升，基于这一设计思想的覆盖网络应运而生。其中，应用层覆盖网络 ( a p p l i c a t i o n l a y e r o v e r l a y n e t w o r k s ，a l o n ) 是目前研究的热点，它是建立在i p 网络之上的虚拟网络，具有独立的网络地址和路由协议。a l o n 的拓扑与其底层网 络的拓扑一般来说都是不同的，但是其任意节点必然与底层网络的某个节点一一对 应。虽然a l o n 有自己的网络路由器，但使用的是逻辑意义上的网络地址( 通常 为节点标识n o d e _ i d ) 。在实际的路由中，它必须借助于底层网络的网络地址才 能到达下一跳节点处，这样a l o n 上的一跳体现在底层网络上可能经过了多跳。 图1 1 中给出了a l o n 网络及其节点路由过程的一个例子：a l o n 网络上的节点 ，b ，c ，d 7 分别对应于底层i p 网络上的a ，b ，c ，d 节点，节点a 7 的路由 表中有指向b 7 的表项，当a 7 路由至b 时，在底层网络看来，实际卜是经过了 a c d b 这样的路由过程。 一l 一 上海交通大学博士学位论文 图1 1应用层覆盖网络及其路由过程示意图 f i g 1 1 i l l u s t r a t i o n o f a n a l o n n e t w o r k a n da r o u t i n g p r o c e s s o v e r i t a l o n 网络技术和应用的迅速发展使得“简单网络，智能边缘”这一设计思想更 好地得以实现，体现在：i n t e m e t 核心网络的功能正日益延伸到位于网络边缘的端 系统上：i n t e r n e t 的存储方式正从“内容位于中心”转变为“内容位于边缘”。 相应地，网络技术研究与应用的热点也正从核心网络延伸到边缘网络。这一趋 势带来的一个直接的、深刻的变化就是网络计算模式正在历经客户机，服务器模式向 对等计算模式的演变过程。如图1 2 所示【2 】，根本上区别于客户机，服务器模式，对 等计算模式将计算从中心推向了边缘，所有参与系统的节点处于完全对等的地位， 没有客户机和服务器之分，也可以说每个节点既是客户机，又是服务器；既向别 人提供服务，也享受来自别人的服务。p 2 p 网络是基于对等计算模式系统的典型代 表，也是最常见的应用层覆盖网络。 图1 2客户机服务器计算模式与对等计算模式对比 f i g 1 2c o m p a r i s o nb e t w e e nt h ec l i e n t s e r v e ra n dt h ep 2 pc o m p u t i n gm o d e l s 过去几年见证了i n t e m e t 上涌现出的大量分布式应用，其中最为流行、也最具 一2 一 第一章绪论 影响力的应用就是基于p 2 p 系统的大规模、广域、分散式文件共享。诞生于1 9 9 9 年的n a p s t e r 【3 】是第一个公共可用的m p 3 音乐文件共享系统，在自发布之后很短 的时间内获得了巨大的成功。尽管由于其违反版权法遭到起诉并最终于2 0 0 1 年3 月被迫关闭，但这并不意味着p 2 p 文件共享的结束，以g n u t e l l a 【4 】为代表的分布 式p 2 p 系统持续高速发展并不断壮大。新系统如f r e e n e t 【5 】、k a t _ a a 【6 】、l i m e w h r e 【7 】、b i t t o r r e n t 【8 】、m o r p h e u s 9 】等相继问世，p 2 p 用户的数量始终保持快速的增 长，一步步验证了对等计算思想的成功。今天，基于p 2 p 系统的应用已经超过了传 统的w e b 应用，成为占用互联网带宽最多的网络应用【1 0 ，1 1 】，其代表系统k a t _ a a 的同时在线用户已超过3 0 0 万【1 2 。此外，基于p 2 p 的应用也不再局限于文件共 享，出现了如s e t i h o m e 【1 3 】等利用系统参与者的空闲处理能力的新型应用。 目前，p 2 p 系统已经在数据存储【1 4 _ 1 6 】、内容发布与分组订阅【1 7 、页面缓存服 务【1 8 、组通信【1 9 ，2 0 1 、消息系统【2 l ，2 2 】等多方面得到了广泛应用。值得关注的 是，p 2 p 用户数量激增的同时，p 2 p 用户与用户之间的交互方式也在发生深刻变化， 各种复杂的、非线性的交互方式层出不穷。基于p 2 p 系统的分布式应用发展如火如 荼，成为产业界持续关注与探讨的话题。 与p 2 p 计算在产业界迅速普及的同时，学术界也始终在保持高度关注，对于 p 2 p 计算系统的设计方法和发展方向进行了广泛而深入的研究。今天，p 2 p 计算仍 是分布式计算领域关注的焦点，受到该领域几乎所有知名大学、重要国际学术机 构和国际会议的重视。2 0 0 1 年提出的结构化覆盖网络( s t r u c t u r e d 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 ht a b l e ，d h t ) 技术，更是引发了p 2 p 计算研究的 热潮，在此基础上提出了各种大规模、高性能分布式系统，包括c a n 【2 3 、c h o r d 【2 4 】、p a s t r y 【2 5 、t a p s t r y 【2 6 1 、s y m p h o n y 【2 7 、v i c e o r y 【2 8 、k a d e m l i a 【2 9 、k o o r d e 【3 0 1 、p - g r i d 【3 1 】等。同时，对于如何增强p 2 p 计算系统的各种性能，如安全性、隐 私性、公平性、可扩展性、系统开销、访问性能等，也开展了深入研究。 技术的迅猛发展、需求与应用的不断拓展、用户数量的剧增与交互方式的多样 化等日益突现的情形使得p 2 p 计算系统本身及其所处的网络环境呈现出爆炸式的复 杂性增长( c o m p l e x i t ye x p l o s i o n ) 趋势，集中体现在： 极端庞大的网络规模与地理范围( e x t r e m e l y l a r g es i z e a n ds c a l e ) ：p 2 p 系统 的规模日益增加，拥有动辄数以百万计或更多的互连的设备和用户，分布于 一3 一 上海交通大学博士学位论文 广域的地理范围，并受限于认知的( c o g n i t i v e ) 、时间的( t e m p o f a l ) 、空间的 ( p h y s i c s ) 和组织的( i n s f i s u f i o n a l ) 等多方面的约束【3 2 1 。 极端复杂的交互方式( e x t r e m e 耖c o m p l e xi n t e r a c t i o n s ) ：系统组件间存在大量 的、复杂的、非线性的交互，对于系统的一个微小的扰动( 例如软件的更新、 失效等) 就有可能导致不可预见的结果，有时甚至造成全局崩溃的灾难性后果 【3 3 。这种情况使得即使对于中等规模的系统，问题也难以得到有效的解决。 极端高度的动态性( e x w e m e 耖h i g hd y n a m o s ) ：p 2 p 系统环境存在极端的动态 性，例如，p 2 p 系统在拓扑结构( t o p o l o g y ) 、负载( 1 0 a d ) 与内容( c o n t e n t ) 等均呈现出极端动态性：节点的随意加入或离开，或者诸如系统崩溃或网络 重新划分等事件，都可能造成网络拓扑的迅速改变；系统也可能会由于对热 点节点或热点文档的频繁访问，或者网络中某个节点对计算资源需求的突然增 加，造成负载在网络中集中高度或迅速迁移；此外，网络节点所拥有的资源 的类型、构造方式等也在时时更新，从而造成网络内容的高度动态性【3 4 。 面对上述日益加剧的复杂性爆炸问题，当前用于构造p 2 p 计算系统的思想， 方法与技术正面临着严峻挑战。因此，十分有必要对p 2 p 计算的本质问题进行重 新审视，对p 2 p 计算系统涉及到的关键技术进行深入剖析，设法改进和提出能够 更好地适应上述复杂性需求的方案和措施。基于这一动机，本文试图从复杂网络 ( c o m p l e xn e t w o r k s ) 【3 5 ，3 6 的角度，借助于该领域的相关理论成果，对p 2 p 计算 系统中诸如网络拓扑生成、拓扑适应、资源放置，定位，获取、网络安全与免疫等关键 技术展开深入研究，以期获得关于p 2 p 计算领域有价值的研究成果。下面我们首先 简要介绍最具代表性的p 2 p 计算系统及其涉及到的若干关键技术，指出其中存在的 问题和相关的研究方向，在此基础上给出本文的研究内容和研究方法。 1 2 对等计算系统概述 1 2 1 对等计算系统的定义 对等计算系统正处于不断发展的阶段，因而并不存在一个全面的和精确的定 义。当前给出的许多定义都是从不同的侧而试图反映对等计算系统发展过程中的某 个阶段的新特征。下面几组广为接受的关于对等计算系统的定义取自于该领域具有 重要参考价值的相关文献，它们分别从不同角度刻画了对等计算系统的本质属性： 4 第一章绪论 p 2 p 是一种利用位于i n t e r a c t 边缘的各种可用资源( 如存储空间、计算能力、媒 体内容) 的应用。访问这些分散的资源，就意味着要在连接不稳定和m 地址不 可预见的环境里工作。由于网络上大量的节点工作在d n s 系统之外，这些分散 的资源具有不稳定的连通性和未知的地址。因此，p 2 p 节点必须能够独立于 d n s 系统工作且高度自治【3 7 】。 p 2 p 是一种具有如下五个关键特性的网络体系：网络提供节点间实时的数据 传输或消息传递，节点即是客户端又是服务器，网络的内容由地理上大范 围分散的节点提供，节点具有网络控制权和自治权，网络允许并不总是连 接的( t r a n s i e n t ) 节点和可能没有永久口地址的节点参与【3 8 。 p 2 p 是通过在系统之间直接交换数据来共享计算机资源和服务。这些资源和服 务