（计算机科学与技术专业论文）信任敏感的p2p拓扑构造及其相关技术研究.pdf

国防科学技术大学研究生院学位论文 摘要 心卵一t o - p e e r 计算是近年来开始出现的一种基于 n t e r n e t 的计算模式，其目标 是充分利用i n t e r n e t 环境中各种可能的端计算设备进行大规模协作计算和资源共 享。在理想的p 2 p 拓扑模型中，节点在拓扑中的位置没有优劣之分，其地位是完 全平等的，其拓扑是对称的。 与理想的情况不同，实际的大规模p 2 p 网络除具有明显的动态特征 ( d y n a m i c i t y ) 外，节点在计算能力、存储能力、网络带宽等特性上往往存在较 大的异构性( h e t e r o g e n e i t y ) ，无视网络的动态性和节点异构性的拓扑构造不利于 拓扑的稳定性以及网络的公平和有效性。 研究表明，p 2 p 网络的动态性和节点异构性强烈受制于节点的主观因素。因 此，一个充分顾及网络动态性和节点异构性的p 2 p 网络，必须考虑节点的自主性， 即= 青点在网络参与策略( p a r t i c i p a n ts t r a t e g y ) 等主观因素上的差异。 可信度本质上是一个节点诸多主、客观特性的综合，因此体现节点参与策略 差异的一个合理的尺度是其在朋尸网络中所表现出的可信任程度。本文把节点在 可信度上存在差异的现象称为节点的可信度异构。同时，把考虑可信度异构的p 2 p 拓扑称为信任敏感的拓扑( t r u s t a w a r et o p o l o g i e s ) 。 构造信任敏感的拓扑有利于公平、有效、优化地使用p 2 p 资源，同时，在拓 扑构造中充分考虑节点的可信度也有利于拓扑的稳定性和可用性。 围绕上述可信度敏感的拓扑构造思路，本文分析和研究了基于节点可信度的 结构化和无结构拓扑构造及其相关关键技术，工作主要在以下诸方面展开： ( 1 ) 结构化拓扑的非对称构造。传统结构化拓扑中对节点不加区分的对称构造 方法不利于有效利用拓扑中的可信节点，引入非对称的结构化拓扑有利于提高拓 扑的稳定性和效率； ( 2 ) 结构化拓扑中的选择性搜索机制。影响节点可信度在结构化拓扑中使用的 另一个主要因素在于其基于分布h a s h i n g 的精确对象定位机制缺乏可选择性，引 入选择性搜索机制一方面有利于在多个搜索结果中依据节点差异( 如可信度) 作 出有效选择，另一方面，引入选择性搜索机制本身也有利于结构化拓扑应用范围 的进一步扩展： ( 3 ) 基于p 2 p 环境的分布信任模型。p 2 p 环境中的节点可信度求解依赖有效的 信任模型和信任管理机制，已有的信任模型和管理机制在模型的完备性和管理的 安全性等方面存在诸多问题，因此，有必要构造新的信任模型和相应的信任管理 机制； ( 4 ) 基于节点信任的动态拓扑构造。在目前无结构拓扑的p 2 p ( 文件共享) 应 用中缺乏有效的激励机制，已有的激励机制往往依赖中心节点，仅限于共享激励， 缺乏网络公平性和拓扑优化的考虑。引入节点可信度和拓扑进化方法避免了激励 机制的集中式结构，同时，不仅可以有效达成共享激励的效果，而且具有拓扑优 国防科学技术大学研究生院学位论文 化和促进网络公平性的作用。 其中，( 3 ) 是本文其它工作的基础，同时其信任管理机制又建立在( 1 ) 和( 2 ) 的工作的基础上。( 4 ) 本质上是可信度敏感的拓扑构造思想在无结构拓扑构造中 的应用，它主要建立在( 1 ) 和( 3 ) 的工作基础之上。 本文在上述工作中的主要贡献如下： 提出了一种可信度敏感的非对称结构化拓扑t e r r a c e ，该拓扑在保留d h t 拓 扑的良好特征的同时，充分考虑节点可信度差异，即，相对于低可信节点，高可 信节点占据拓扑中更重要位置，从而增强拓扑的可靠和稳定性。分析和实验表明， t e r r a c e 一方面保留了现有d h t 拓扑已有的良好特性，如可扩展性和可维护性等， 另一方面较传统对称的d h t 拓扑具有更好的动态适应性和容错能力。 基于t e r r a c e 拓扑，通过引入两种选择性搜索和定位机制( 即，基于二阶段混 合搜索的d h t - s s m 机制和基于向量空间模型的d h t - v s m 机制) ，在接近原先d h t 定位开销o ( 1 0 9 n ) 的前提下，较好解决了在结构化p 2 p 网络中的选择性搜索和定 位问题，从而为在结构化拓扑中基于节点可信度的搜索打下了基础，并为结构化 拓扑的进一步广泛应用提供了一个新的思路和手段。 在节点推荐的基础上提出了一种基于p e e r t o p e e r 环境的信任模型，并给出 了该模型的数学分析和分布式实现方法。分析及仿真表明，本文提出的信任模型 较已有模型在完备性、模型的安全性等问题上有较大改进。 提出了基于节点可信度的动态拓扑模型t t e 和可信度敏感的搜索机制t b s ， 动态拓扑进化和基于节点可信度的搜索机制保证了所构造的无结构网络同时满 足三个要求，即：共享激励、网络的公平性和对t r a g e 咖o f c o m m o n 问题的抑制， 而这是现有的激励机制所难以达到的。 关键字：对等网，信任，拓扑，结构化拓扑，无结构拓扑，选择性搜索，激励 拓扑进化 a b s t r a c t p e e r _ t o 。p e e rc o m p u t i n gi san o v e li n t e r n e t - b a s e dc o m p u t i n gp a r a d i g mw h i c hi s b e i n gs t u d i e dw i d e l y i nr e c e n t y e a r s t h e f i n a l g o a l o fp 2 p s y s t e m s i st o p o o l e n d 。s y s t e m si ni n t e m e t s c a l ea sm o r ea sp o s s i b l et oc o n s t r u c tl a r g e s c a l ec o o p e r a t i n g a n d r e s o u r c e - s h a r i n ge n v i r o n m e n t s ，i na ni d e a lp 2 pn e t w o r km o d e l ，t h es i g n i f i c a n c eo f a l lp e e r si se q u a l ，a n dt h en e t w o r k t o p o l o g yi ss y m m e t r i c a l d i f f e r e n tw i t hi d e a lc a s e ，t h ea c t u a lp 2 ps y s t e m sa r e u s u a l l ya d h o c ，a n dt h e h e t e r o g e n e o u sn a t u r eo fi n t e r n e tm a k ep e e r si nl a r g e s c a l ep 2 pe n v i r o m e n t sb e i n g q u i t ed i f f e r e n t i nc h a r a c t e r i s t i c ss u c ha sc o m p u t a t i o np o w e r ，s t o r a g ec a p a b l i t ya n d n e t w o r kb a n d w i t he t c ，i ti sh a r dt og e tas t a b l e ，e f f i c e n ta n df a l m e s sp 2 pn e t w o r ki fw e n e g l e c tt h ed y n a m i c i t ya n d t h eh e t e r o g e n e i t y o f p 2 ps y s t e mi ni t sc o n s t r u c t i o n s o m ep r a c t i c e sa n dr e s e a r c h e sh a v e p r o v e dt h a t ，t h ed y n a m i c i t y a n dt h e h e t e r o g e n e i t yo fp 2 ps y s t e ma r eh e a v i l ys u b j e c t e d t ot h ep a r t i c i p a n ts t r a t e g i e so f p e e r s i np 2 pe n v i r o n m e n t a tt h i sp o i n t ，t h ep 2 ps y s t e md e s i g n e rm u s tt a k et h ea u t o n o m yo f p e e r si n t oh i s ( h e r ) a c c o u n t i nt h ep 2 p s y s t e md e s i g n p e e rt r u s t w o r t h i n e s si np 2 ps y s t e mi se s s e n t i a las y n t h e s i so f p e e r ss u b j e c t i v e a n do b j e c t i v ec h a r a c t e r i s t i c s ，a n di sar e a s o n a b l em e t r i cw h i c hc o u l db eu s e dt o e v a l u a t et h ep e e r sp a r t i c i p a n ts 似e g y ，i nt h i sp a p e r ，t h es i t u a t i o ni nw h i c h p e e r sh a v e d i f f e r e n td e g r e ei nt r u s t w o r t h i n e s si sc a l l e dt r u s t w o r t h i n e s sh e t e r o g e n e i t y ，a n dt h ep 2 p t o p o l o g i e s w h i c hc o n s i d e rt h et r u s t w o r t h i n e s s h e t e r o g e n e i t yp h e n o m e n o n i ni t s c o n s t r u c t i o ni sc a l l e dt r u s t a w a r ep 2 p t o p o l o g i e s t r u s t - a w a r e p 2 p c o n s t r u c t i o nm a k e s p 2 ps y s t e m m o r ef a i m e s s ，e f f i c i e n t ， o p t i m i z e d ，s t a b l ea n d u s a b l e f o c u s i n g o nt r u s t a w a r e p 2 pc o n s t r u c t i o n ，t h e d e s t i n a t i o no ft h i s p a p e r i s r e s t r i c t e di nf o l l o w e ds u bd o m a i n sa n dr e l a t e dt e c h o n o l o g i e s ： ( 1 ) t h e c o n s t r u c t i o no f u n s y m m e t r i c a ls t r u c t u r e dp 2 pt o p o l o g i e s t h es y m m e t r i c a l c o n s t r u c t i o na p p r o a c hi nt r a d i t i o n a lp 2 ps y s t e m sm a k e s i td i f f i c u l tt ou t i l i z et h e c a p a b l i t y o ft r u s t e d p e e r sa d e q u a t e l y ，o n t h e c o n t r a r y ，t h eu n s y m m e t r i c a l c o n s t r u c t i o nl e n d sas p a c et ol e v e r a g et h et r u s t e dp e e r st og e tam o r er o b u s t a n de f f i c i e n tp 2 pn e t w o r k ( 2 ) t h e s e l e c t i v es e a r c h i n gm e c h a n i s mi ns t r u c t u r e dp 2 pt o p o l o g i e s a no b s t a c l e w h i c ha f f e c tt h eu s eo ft r u s ti ns t r u c t u r e dp 2 pn e t w o r ki st h el a c ko fs e l e c t i v i t y f o ri t so r i g i n a ld h ta c c u r a t eo b j e c tl o c a t i n gm e c h a n i s m ，i m p o r t i n gs e l e c t i v e s e a r c h i n gm e c h a n i s mo no n eh a n dm a k e sp e e rh a v es e l e c t i v ec h o i c e so ni t s s e a r c h i n gr e s u l t sa c c o r d i n g t ot h e i rt r u s t w o r t h i n e s s ，o nt h eo t h e rh a n d ，s e l e c t i v e s e a r c h i n gm e c h a n i s ma l s oe n l a r g e st h ea p p l i c a b l ed o m a i n so f s t r u c t u r e dp 2 p t o p o l o g i e s ， ( 3 ) d i s t r i b u t e d t r u s tm o d e lf o r p 2 p e n v i r o n m e n t s t h e q u a n t i t y o f p e e r t r u s t w o r t h i n e s s r e l y o nae f f i c i e n t t r u s tm o d e la n dt r u s t m a n a g e m e n t m e c h a n i s m ，c u r r e n tt r u s tm o d e la n dt r u s tm a n a g e m e n tm e c h a n i s mo fp 2 p s y s t e m sh a v es o m el i m i t a t i o n s i nt h em o d e li n t e g r a l i t ya n ds e c u r i t y ，w h i c h m a k ei t n e c e s s a r y t ob u i l dan e wt r u s tm o d e la n dr e l a t e d m a n a g e m e n t m e c h a n i s mf o ro n rw o r ki nt h i sp a p e r ( 4 ) a d y n a m i c a lt o p o l o g yc o n s t r u c t i o nb a s e d o np e e rt r u s t w o r t h i n e s s t h e r ea r en o e f f i c i e n ti n c e n t i v em e c h a n i s m si nc u r r e n tu n s t r u c t u r e d p 2 p ( s u c h a s f i l e s h a r i n g ) a p p l i c a t i o n s ，a n dt h ea r c h i t e c t u r eo fk n o w ni n c e n t i v em e c h a n i s m s a r e u s u a l l y c e n t r a l i z e d ，a n d i sl i m i t e di n s h a r i n gi n c e n t i n g ，w i t h o u t c o n s i d e r a t i o no nt h en e t w o r kf a i r n e s sa n dt o p o l o g yo p t i m i z a t i o n a c t u a l l y ， l e v e r a g i n gd i s t r i b u t e d t r u s tm e c h a n i s ma n d t o p o l o g i e se v o l u t i o nc o u l d n o to n l y e l e g a n t l y a v o i dt h ec e n t r a l i z e da r c h i t e c t u r ew h i c he x i s t e di nc u r r e n tp 2 p i n c e n t i v es y s t e m s ，b u ta l s oc o u l dc o m et ot h ei n c e n t i v ee f f e c to ff i l es h a r i n g a n dn e t w o r kf a i m e s s t h e ( 3 ) i st h ef u n d m e n t a l o fo t h e rw o r ko ft h i s p a p e r ，b u ti t s t r u s tm a n a g e m e n t m e c h a n i s mi sa l s ob u i l to nt h ew o r ko f ( 1 ) a n d ( 2 ) t h e ( 4 ) i se s s e n t i a l l ya na p p l i c a t i o n w h i c h l e v e r a g e st h ew o r ko f ( 1 ) a n d ( 3 ) t h i st h e s i sa i m sa tm a k i n gf o u rm a j o rc o n t r i b u t i o n s ： p r o m p t e dad - t r e e b a s e dt r u s t - a w a r ea n du n s y m m e t r i c a lp 2 pt o p o l o g y 。t e r r a c e s a m ea st h et r a d i t i o n a ls t r u c t u r e dd h tn e t w o r k t h el o c a t i n gc o s ti nt e r r a c ei s o ( 1 0 9 n ) a n dt h em a i n t a i n i n gc o s ti so ( d ) t e r r a c ep r o m p t sac l u s t e rm e c h a n i s m a n dan o d e - p r e e m p t i n gp o l i c y ，w h i c hm a k ei t f a u l t t o l e r a n c e a n a l y z i n g a n d s i m u l a t i o ns h o wt h ec o n c l u s i o nt h a tt e r r a c e i s s c a l a b l e ，m a i n t a i n a b l e a n d f a u l t t o l e r a n c e t h em o s ti m p o r t a n tc h a r a c t e r i s t i co ft e r r a c et o p o l o g yi s t h a tt e r r a c ei s t r u s t a w a r ea n du n s y m m e t r i c a l ，w h i c hm e a n st h em o r et r u s t e dp e e ri nt o p o l o g yg e t m o r ei m p o r t a n tt o p o l o g yp o s i t i o n ，a n dc o u l dm a k em o r ec o n t r i b u t i o n s t ot o p o l o g y s t a b i l i t ya n du s a b l i t y p r o m p t e d t w on o v e ls e l e c t i v es e a r c h i n gm e c h a n i s m sf o rs t r u c t u r e dp 2 pn e t w o r k ， t h ef i r s t ，d h t s s m ，i sa2 - p h a s eh y b r i dl o c a t i n ga n ds e a r c h i n gm e c h a n i s m ，a n d t h es e c o n d ，d h t - v s m ，i sb a s e do nv e c t o rs p a c em o d e l b o t h t h et w oa p p r o a c h e s c o u l de l e g a n t l ym a k ed h tt o p o l o g i e sg a i ns e l e c t i v es e a r c h i n gc a p a b i l i t yo nt h e m e s s a g ec o m p l e x i t y o f a p p r o x i m a t i v eo ( 1 0 9 n ) p r o m p t e d an o v e lr e c o m m e n d a t i o n - b a s e dg l o b a l t r u s tm o d e la n dg i v e s i t s d i s t r i b u t e di m p l e m e n t a t i o nm e t h o d m a t h e m a t i ca n a l y z i n ga n ds i m u l a t i o n ss h o w t h a t ，c o m p a r e dt oc u r r e n tg l o b a lt r u s tm o d e l ，t h ep r o m p t e d m o d e li sm o r er o b u s t o nt r u s ts e c u r i t yp r o b l e m sa n dm o r ep r o v a b l eo n m o d e li n t e g r a l i t y - 国防科学技术火学研究生院学位论文 p r o m p t e d a p e e rt r u s t b a s e dp 2 pd y n a m i ct o p o l o g ym o d e lt t e a n dat r u s t a w a r e s e a r c h i n gm e c h a n i s mt b s f o ru n s t r u c t u r e dn e t w o r k t h e d y n a m i ct o p o l o g y e v o l u t i o na n dt h et r u s t b a s e ds e a r c h i n gm c c h a n i s ms o l v e dt h r e ep r o b l e mw h i c h e x i s t e di nc u r r e n tu n s t r u c t u r e dp 2 ps y s t e m ：l a c ko fe f f i c i e n ti n c e n t i v em e c h a n i s m t o e n c o u r a g e ( f i l e ) s h a r i n g ，i e ，t h ef r e e r i d i n gp r o b l e m ；t r a g e d y o fc o m m o n p h e n o m e n o n ，w h i c h m e a n st h ea l lm o s tn o d e si np 2 ps y s t e ms e n dt h e i rm e s s a g e w i t h o u tc o n t r o l ，a n dg i v et h ei n t e r n e tb a c k b o n eah e a v yc o m m u n i c a t i o n p r e s s u r e ； t o p o l o g yo p t i m i z i n ga n d n e t w o r kf a i r n e s s k e y w o r d s ：p e e r - t o - p e e r ，t r u s t ，t o p o l o g y ，s t r u c t u r e dt o p o l o g y ，u n s t r u c t u r e d t o p o l o g y ，s e l e c t i v es e a r c h i n g ，i n c e n t i v e ，t o p o l o g ye v o l u t i o n 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：焦堡筮壁的1 2 1 堑盐垫堂区基担差筮盔丛壅 ，! ， 学位论文作者签名：盆叁日期：z 卯当年夕月加日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目 学位论文作者 作者指导教师 国防科学技术大学研究生院学位论文 图表目录 图11 列p 2 p 文件共事应用e m u l e 跟踪所反映的节点连接的频繁变化1 图1 2 两种无结构p 2 p 文件共享刚络k a z a n 和g n u t e l l a 与w w w 和内容分发网 a k a m a i 对内容请求的成功响应比铡2 隧l3g n u t e i l a 恻终中节点所表现出的连接能力的p o w e r - l a w 分布一2 踅1 4e m u l e 的设鼹界断 一3 嘲1 5 ( a ) 对称拓扑，6 闰1 ，5 ( b ) 非对称拓扑 一一 一 6 隧1 6 第二至第五章润的关联。1 3 图2 1n a p s t e r 拓扑结丰勾一 1 5 阁2 2c m u t e l l a 拓扑结构，1 6 图23c h o r d 拓扑结构：c h o r d 的逻辑环及其f i n g e r 表指针t 7 围24 p g r i d 的虚拟= 义树拓羚结构，1 9 圈2 , 5 t o r n a d o 搏逻辑地址空闻划分成多个子空间2 0 图2 , 6 t e r r a c e 与几种典型结构化拓扑的比较。2 1 图2 ，7 扇出为8 的t e r r a c e 树( 部分) 2 2 圈28t e r r a c e 的拓手 构造算法2 3 圈2 9 地址空间上限为2 2 2 ( 三进制) 的3 叉t e r r a c e 树的拓扑构造一2 4 图2 1 0 基于3 度t e r r a c e 拓扑的剥象索引插入一2 5 圈2 1 1 慕于t e r r a c e 拓扑的对象索引插入算法一 2 6 囤2 1 2 基于3 度t e r r a c e 拓朴的对象定位。2 6 图21 3 基于t e r r a c e 拓扑的对象定位算法2 7 图2 1 4 引入c l u s t e r 扩展的3 度t e r r a c e 拓扑，2 7 图2 ，15 改进_ f i j 的t e r r a c e 拓扑构造算法一一2 8 图21 6 虔3 的t e r r a c e 通过在子树闻建立蕊机连接缓解上层节点的负载。2 9 星2 1 73 度t e r r a c e 中c l u s t e r 成员节点失效的修补3 0 图21 8 貉予叶节点抢占的t e r r a c e 拓扑维护算法3 0 图2 1 9 t e r r a c e 与c h o r d 定位开销的对比测试结巢一一3 3 图2 2 0 t e r r a c e 与c h o r d 容锖对阮测试结果3 3 幽2 2 1 引入节点可信度差异盾，t e r r a c e 与c h o r d 容错对比鞭4 试结果3 4 图22 2 e f f a c e 负载均衡测试结果3 5 图22 3t e r r a c e 各层的平均可信度，3 5 图2 2 4 t e r r a c e 在不同失效规模下，各层的平均可信度一3 6 图31t e r r a c e 中的广播搜索，4 1 圈32 使用e m u l e 对关键宇m a t r i x 进行搜索的返回结果的快照4 2 图3 , 3 通过广播搜索的结果在d h t s 上构造相似关键字对应索引节点的一个关联 环， 4 4 图3 4 在以三个关键字a p p l i e d 、l i n e a r 和a l g e b r a 为坐标的三维向量空闯中，向量 国防科学技术大学研究生院学位论文 0 5 ，2 5 ，5 唯一标识了文档d 4 6 图3 5 由文档的v s m 向量组成的矩阵4 6 图3 6 节点a 发起一次f i r e w o r k 定位，到达目的节点b 后，由b 产生一次半径 为1 的爆炸( 局部广播) 4 9 图3 7 随机拓扑与t e r r a c e 广播搜索效率对比5 1 图3 8 随机拓扑、t e r r a c e 广播搜索与d h t - s s m 搜索的效率对比5 1 图3 9d h t - v s m 与d h t - s s m 搜索的效率对比5 2 图4 1 三阶t e r r a c e 树( 部分) 逻辑空间( 三进制) 6 1 图4 2 档案点d 的数据结构6 1 图4 3 节点u 作为一般用户节点的算法6 2 图4 4 节点u 作为档案点的算法6 3 图4 5 不同规模e e 类恶意节点下，与理想情况的成功交易比6 7 图4 6 不同规模e e 类节点下( 改变策略后) ，与理想情况的成功交易比6 8 图4 7 不同规模e d 类节点下，与理想情况的成功交易比6 8 图4 8 不同规模e k 类节点下，与理想情况的成功交易比6 9 图4 9 不同规模e m 类节点下，e i g e n r e p 与理想情况的成功交易比7 0 图5 1f r e e r i d e r 问题的战略博弈式7 2 图5 2t r a g e d yo f c o m m o n 问题的战略博弈式7 2 图5 3t b s 算法7 8 图5 4 对应公式5 5 中节点在t + l 时刻可能的效用变化所采取的战略8 0 图5 5 随机拓扑和均衡拓扑8 2 图5 6 高可信节点的邻居选择算法8 3 图5 7 低可信节点的邻居选择算法8 3 图5 8 基于t t e 模型的拓扑进化8 4 图5 91 0 类不同可信度节点集合的平均地位随拓扑进化的变化情况8 5 图5 1 01 0 类不同可信度节点集合的平均搜索效率随拓扑进化的变化情 7 兄，8 6 国防科学技术大学研究生院学位论文 1 11 应用需求 第一章绪论 1 ，1 问题的提出 自1 9 9 9 年以来，p e e r t o p e e r ( p 2 p ) 重叠( o v e r l a y ) 网络【1 】模式正在逐渐成为 研究和应用的热点，p 2 p 网络应用模式的兴起得益于i n t e r n e t 的广泛普及、网络 带宽的大幅增加以及基于i n t e r n e t 的端系统计算能力的迅速增强。上述因素促使 原先在其它网络计算模式中通常被忽视且广泛存在的端用户设备成为一种宝贵 的计算资源( 与之形成对比的是，在c l i n e t s e r v e r 计算模式中，通常只有s e r v e l 节 点的资源得到利用) 。因此，“h a r n e s st h ee 咖o f i n t e r n e t ”成为当前一个新的研 究和应用目标。这里，“e d g eo f - i n t e r n e t ”即是指的那些在传统的应用模式中作 为客户端而往往被忽略的计算设备。到目前为止，p 2 p 研究已经涉及非常广泛的 方面，主要包括：网络拓扑构造【2 j 、安全与可靠性队分布式数据存储【4 j 、大规模 并行计算【5 1 等。p 卯的应用更是涵盖诸多领域，如：商业和民用领域的文件和数 据共享和存储【6 】、科研领域的协同和并行计算口j 、军事领域的士兵协作和战场网 络( b a t t l e - f i e m n e t w o r k ) 构造等惮，一1 。 p 2 p 网络通常具有较大的规模例如，用于太空射电信号分析的大规模计算 网络s e t i h o m e t ”l 声称其目前拥有1 0 0 0 0 0 0 自愿者( 计算节点) 。在大规模的 p 2 p 网络环境中，动态性( d y n a m i c i t y ) 难以避免，有研究指m , t “1 ，具有i n t e r n e t 连接的计算机的平均无故障时间( m t b f ) 为3 个小时左右，也就是说，在规模为 1 0 0 0 0 的配置下，平均每2 分钟就有至少一个节点失效。 造成( p 2 p ) 网络的动态性的原因除o v e r l a y 底层( i n t e r n e t ) 基础设施所提 供的不可靠的服务外，另一个更主要的因素在于p 2 p 环境高度的自治性 ( a u t o n o m y ) 【2 1 。图1 1 为文件共享应用e “拈节点的连接变化情况的跟踪结果。 可以看出，其连接变化的频度相当惊人。通过分析绷“k 的日志可以发现，造成 这种连接性动态变化的一个主要因素是大量节点随机离开网络。 1 口0 5 0 0 0 时间f m 删 图11 对p 2 p 文件共享应用e m u l e 跟踪所反映的节点连接的频繁变化 5 0 第l 页 国防科学技术大学研究生院学位论文 图1 2 给出了两种无结构p 2 p 文件共享网络k a z a a 和g n u t e l l a 与w w w 等其 它中心依赖的应用网络对内容请求的成功响应比例【1 3 1 。可以看出，基于p 2 p 的文 件共享网络的服务质量难以保证。由于该实验基于同样的底层基础设施一 i n t e r n e t ，因此，由基础设施服务质量带来的失效影响可以相对忽略，上述试验结 果说明，造成尸2 尸失效响应比例远大于渺矿渺的主要原因在于被请求端系统不受 控制的主观行为。 图1 2 两种无结构p 2 p 文件共享网络k a z a a 和g n u t e ii a 与w w w 和内容分发网 络a k a m a i 对内容请求的成功响应比例。 p 2 p 网络高度的动态特性决定了其目前难以保证拓扑的稳定性以及难以提供 完全可靠的服务。也正因为如此，相对有效的拓扑稳定技术和服务保障方法对门p 技术的发展和进一步应用有着非常重要的意义【1 4 ”】。 另一个对服务质量有着较大影响的因素是节点的异构性( h e 招r o g e n e i t y ) ， 造成节点异构的原因在于节点间广泛存在的计算、存储能力和网络带宽等因素的 差别。例如，有研究指出，目前存在于i n t e r n e t 上的计算设备的网络连接能力呈 p o 。阱缸w 分布【1 7 】。忽视节点的异构性往往会造成低效的网络，反之，一个能够 充分利用节点间差异构造的p 2 p 系统可以更好地和有效地利用节点资源和增加 拓扑的稳定性。 图1 3 是c 坳公司2 0 0 1 统计的g n u t e l l a 网络中，节点所表现出的连接能力 的差异。 ； 屯 c o 甚 j 色 2 n 0 乳f i i l i k s ( 1 0 ss c a l e ) 1 0 0 图1 3g n u t e il a 网络中节点所表现出的连接能力的p o w e r l a w 分布 国防科学技术火学研究生院学位论文 综上所述，p 2 p 网络的动态性和节点间的异构性是在p 2 p 应用实施中需要考 虑的两个重要问题，这两个问题解决的好坏直接影响p 2 p 应用的有效性。 l1 2 研究背景 本文研究的起点是考察p 2 p 的拓扑构造与节点异构和网络动态性的关系。从 上面的分析可以看出，由于p ”环境下节点的高度自治，把握节点真实的客观能 力差异和网络动态性很难通过直接的方法，例如测量和询问( q u e r y i n g ) ，因而引 入一种间接的衡量尺度是十分必须的。现有的异构敏感的拓扑构造往往忽略了 p 2 p 环境下节点的自主性，其构造方法所基于的尺度通常仅仅基于直接的测量和 询问因而其得到的结果常常是不准确、片面甚至不真实的【2 0 2 1 1 。如s e t l f l - l o m e 基于运行在每个v o l u n t e e rp c 上的一个m i c r ob e n c h m a r k 例程的测试结果来区分 节点的计算能力，而与预期结果相反的是，最多高达5 0 的节点通过欺诈手段改 变了测试结果的真实性，以期获得更多的奖励1 2 ”。 如1 1 i 小节所述，造成p 2