（计算机应用技术专业论文）基于广义peterson图的p2p覆盖网设计与分析.pdf

基于广义p e t e r s o n 图的p 2 p 覆盖网设计与分析 摘要 结构化p 2 p 系统使用分布式哈希表( d h t ) 将数据映射到相应的节点上，从而得到了高 效的路由算法。设计新型结构化p 2 p 覆盖网络，必须关注的研究技术有：一：覆盖网络拓 扑结构的设计。当前，结构化p 2 p 系统中面临的重要问题之一就是如何处理资源问题。而 覆盖网络拓扑结构的设计则是解决这一问题的重要途径。因此，为网络设计合适的拓扑结 构是很重要的。二：结构化p 2 p 覆盖网络的路由和定位问题。路由和定位的方式通常取决 于两个因素：首先是网络拓扑结构，其次是路由表的结构。三：结构化p 2 p 覆盖网络的自 适应性问题。p 2 p 网络的最大特点之一就是在于它极大的动态性：不断有新节点加入、旧 节点离开、节点失效等情况发生。在动态环境里，p 2 p 网络需要建立一套健全、可行的方 法来处理各种动态问题，在新节点加入时通知其他节点新成员的到来，在旧节点离开时通 知其他节点老成员的离去。四：一些经典的p 2 p 系统中都必须维护o ( 1 0 9 n ) 邻居，节点维 护的邻居数量代表了网络拓扑维护的代价。即：随着网络规模的增大，每个节点的路由表 会对数增加，导致开销很大。因此p 2 p 网络的设计和实现要求有尽量小的直径和固定度的 拓扑结构。 本文主要研究新型结构化p 2 p 覆盖网络的设计和分析，论文的创新之处在于设计了一 个基于广义p e t e r s o n 图的结构化p 2 p 覆盖网g p n e t 。论文共分五章。 第一章给出了问题的研究背景及论文的组织结构；第二章对结构化p 2 p 覆盖网络设计 的关键技术和一些经典的p 2 p 覆盖网络进行了分析研究；第三章基于广义p e t e r s o n 图设计 了一种新型的结构化p 2 p 覆盖网络g p n e t ，对g p n e t 的拓扑结构：广义的p e t e r s o n 图进行 了研究，对其性质进行了分析；给出并分析了g p n e t 的键值分配情况；分析了g p n e t 的路 由情况，给出了设计的路由表，路由表的构造实例和具体路由算法；对g p n e t 的自组织性 和自适应性如：节点的加入和离开，进行了分析。同时给出了节点加入过程的实例，并给 出了节点加入的算法；第四章对设计的g p n e t 进行了仿真分析，给出了平均路径长度，拓 扑鲁棒性和负载分配的仿真实验的结果。实验结果表明，g p n e t 不仅具有良好的抗微扰能 力还具有负载平衡的特性。同时，在有相同度的大规模p 2 p 网络中，g p n e t 的路由长度比 c h o r d 和c a n 更短。第五章对论文进行了总结并对下一步要做的工作进行了展望。 关键词：p 2 p ，覆盖网络，分布式哈希表( d h t ) ，拓扑结构，广义p e t e r s o n 图，路由，自组织性，自适应性 基于广义p e t e r s o n 图的p 2 p 覆盖网设计与分析 a b s t r a c t s t r u c t u r e dp 2 ps y s t e m su s et h ed i s t r i b u t e dh a s ht a b l e ( d h t ) t om a pd a t ai n t o t h e c o r r e s p o n d i n gn o d e a sar e s u l t ，s t r u c t u r e dp 2 ps y s t e m sh a v ee f f i c i e n tr o u t i n ga l g o r i t h m s i n o r d e rt od e s i g nn e wt y p e so fs t r u c t u r e dp 2 po v e r l a yn e t w o r k s ，t h ef o l l o w i n gt e c h n o l o g i e sm u s t b ec o n c e m e d 1 ：d e s i g ns u i t a b l et o p o l o g i e sf o rp 2 po v e r l a yn e t w o r k s t h ec u r r e n tw o r kd e a l s w i t ht h ep r o b l e mo fr e s o u r c em a n a g e m e n ti ns t r u c t u r e dp 2 ps y s t e m s t h et o p o l o g i c a lp r o p e r t i e s o ft h eo v e r l a yn e t w o r k sa r ec r i t i c a lf a c t o r st h a td o m i n a t et h ep e r f o r m a n c eo fs t r u c t u r e dp 2 p s y s t e m s t h e r e f o r e ，i ti sv e r yi m p o r t a n tt od e s i g ns u i t a b l et o p o l o g i e sf o r n e t w o r k s 2 ：t h er o u t i n g a n dl o c a t i o np r o b l e m so ft h es t r u c t u r e dp 2 po v e r l a yn e t w o r k s w h i l et h ew a y o ft h er o u t i n ga n d l o c a t i o nu s u a l l yd e p e n d so nt h et w of o l l o w i n gf a c t o r s ：t h et o p o l o g ys t r u c t u r eo ft h en e t w o r k sa n d t h ed e s i g no fr o u t i n gt a b l e 3 ：u n c o n t r o l l e dd y n a m i co p e r a t i o n so fn o d e s d y n a m i ci so n eo f t h e m o s ti m p o r t a n tc h a r a c t e r i s t i c so ft h ep 2 pn e t w o r k s ，n o d e sj o i n i n g ，d e p a r t i n ga n dl e a v i n gt u r no u t c o n t i n u o u s l y i nt h i sd y n a m i cc i r c u m s t a n c e ，p 2 pn e t w o r km u s te s t a b l i s has e to ff e a s i b l ea n d e f f e c t i v em e t h o dt op r o c e s sv a r i o u sk i n d so fd y n a m i cp r o b l e m s w h e nan e wm e m b e ri sj o i n i n g ， n o t i f yt h eo t h e rn o d e si t sa r r i v a l ，w h e nan o d ei sl e a v i n g ，n o t i f yt h eo t h e r si t sd e p a r t u r e 4 ：s o m e c l a s s i cs t r u c t u r e dp 2 ps y s t e m sm u s tm a i n t a i no ( 1 0 9 n ) n e i g h b o r s ，t h en u m b e ro fn e i g h b o r s ， w h i c hn o d e sm a i n t a i n d e n o t em a i n t e n a n c ec o s t so fn e t w o r kt o p o l o g y ，t h a ti st os a y , “t ht h es i z e i n c r e a s i n go ft h en e t w o r k 。t h er o u t i n gt a b l eo fe a c hn o d ew i l li n c r e a s e ，w h i c hl e a dt oe x p e n s i v e i n c r e a s e 。t h e r e f o r e ，p 2 pn e t w o r k sa t t e m p tt od e s i g na n di m p l e m e n tat o p o l o g ys t r u c t u r ew i t ha s m i n i m u md i a m e t e ra sp o s s i b l e t h i st h e s i sm a i n l ys t u d i e st h ed e s i g na n da n a l y s e si ns t r u c t u r e dp 2 pn e t w o r k sa n dd e s i g n sa n e ws t r u c t u r e dp 2 po v e r l a yn e t w o r kw h i c hb a s e do nt h eg e n e r a l i z e dp e t e r s o ng r a p h t h et h e s i s i sd i v i d e di n t of i v ec h a p t e r s i nc h a p t e ro n e ，w ei l l u m i n a t eb a c k g r o u n do fo u rs t u d ya n dp u tf o r w a r do ft h ep r o b l e m s ，t h e w o r kw ed oi nt h i sp a p e ra n dt h es t r u c t u r eo ft h ep a p e r i nc h a p t e rt w o ，a n a l y s i ss o m ec r u c i a l t e c h n i q u e sf o rd e s i g n i n gan e ws t r u c t u r e dp 2 po v e r l a yn e t w o r ka n dd os o m er e s e a r c ha b o u tt h e c l a s s i cp 2 po v e r l a yn e t w o r k s i nc h a p t e rt h r e e ，w ed e s i g nan e ws t r u c t u r e dp 2 po v e r l a yn e t w o r k g p n e ta n dd os o m er e s e a r c ha b o u tt h et o p o l o g ys t r u c t u r e - - - g e n e r a l i z e dp e t e r s o ng r a p h s ， a n a l y s i si t sc h a r a c t e r i s t i c ss i m u l t a n e o u s l y a f t e rt h a t ，w ed e f i n et h ek e yv a l u ea s s i g n m e n ti n g p n e t ，a n a l y s i st h er o u t i n gc i r c u m s t a n c e so ft h i sp 2 pn e t w o r ka n dd e t a i lt h er o u t i n gt a b l e ，t h e r o u t i n ga l g o r i t h ma n dt h er o u t i n gt a b l ee x a m p l e s a tt h es a m et i m e ，w ed os o m er e s e a r c ha b o u t t h es e l f - o r g a n i z a t i o na n ds e l f - a d a p t a t i o ns u c ha st h en o d ej o i n i n g ，d e p a r t i n ga n dl e a v i n g ，a l s o a n a l y s i st h ee x a m p l e so ft h en o d ej o i n i n g i nt h ef o u r t hc h a p t e r , s h o wt h e r e s u l t so ft h e s i m u l a t i o ne x p e r i m e n t s ，s u c ha st h ea v e r a g er o u t i n gl e n g t h ，t o p o l o g i c a lr o b u s t n e s sa n dl o a d i n g 基于广义p e t e r s o n 图的p 2 p 覆盖网设计与分析 b a l a n c e t h ee x p e r i m e n tr e s u l t si n d i c a t et h a tg p n e th a san i c ep e r f o r m a n c ei nr o b u s t n e s sa n d l o a d i n gb a l a n c e ，m e a n w h i l e ，i th a sas h o r tm u t i n gl e n g t hc o m p a r e dt oc h o r da n dc a nw i t ht h e s a m ed e g r e ei nl a r g es c a l e so fp 2 pn e t w o r k s i nt h ef i f t hc h a p t e r , w eg i v eac o n c l u s i o no ft h i s p a p e ra n dm a i n l yp r e s e mt h ef o l l o w i n gp r o b l e m sf o rf u t u r er e s e a r c h k e y w o r d s ：p 2 p ，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 ) ，t o p o l o g y s t r u c t u r e ，g e n e r a l i z e dp e t e r s o ng r a p h ，r o u t i n g ，s e l f - o r g a n i z a t i o n ，s e l f - a d a p t a t i o n i i i 曲阜师范大学博士硕士学位论文原创性说明 ( 在口划“4 ) 本人郑重声明：此处所提交的博士口硕士论文基于广义p e t e r s o n 图的p 2 p 覆盖网设计与分析，是本人在导师指导下，在曲阜师范大学攻读 ， 博士口硕士酣学位期间独立进行研究工作所取得的成果。论文中除注明部 分外不包含他人已经发表或撰写的研究成果。对本文的研究工作做出重要贡 献的个人和集体，均已在文中已明确的方式注明。本声明的法律结果将完全 由本人承担。 作者签名：侗正怒日期：2 唧参乡 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“4 ) 基于广义p e t e r s o n 图的p 2 p 覆盖网设计与分析系本人在曲阜师范大学攻 读博士口硕士船车位期间，在导师指导下完成的博士口硕士概论文。 本论文的研究成果归曲阜师范大学所有，本论文的研究内容不得以其他单位 的名义发表。本人完全了解曲阜师范大学关于保存、使用学位论文的规定， 同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅 和借阅。本人授权曲阜师范大学，可以采用影印或其他复制手段保存论文， 可以公开发表论文的全部或部分内容。 作者签名：侗屋起日期：力哆石3 导师签名：曳乏私参日期：j 叼干6 、) 基于广义p e t e r s o n 图的p 2 p 覆盖网设计与分析 1 1 研究背景和问题的提出 第一章绪论 对等网络( p 2 p ：p e e r - t o p e e r ) t l 】是分布式系统与计算机网络相结合的产物，也是采用对等 模式工作的计算机网络。在对等网络中，每个网络节点都是自由平等的，所有的节点分布 式地自组织成一个整体网络，因此它能极大程度的提高网络效率，充分的利用网络带宽， 开发每个网络节点的潜力。 p 2 p 技术的最初应用代表是n a p s t e r 2 1 ，它创造了在半年内拥有5 0 0 0 万用户的网络奇 迹，向世界展示了p 2 p 的优异性能和巨大潜力。n a p s t e r 的目的是为了实现资源文件的交换。 文件存放在任意一台安装了同类软件的计算机上，是一个无结构的p 2 p 系统，可以实现文 件共享功能。在国内，天网m a z e i 3 j 是北京大学网络实验室开发的一个中心控制与对等连接 相融合的对等计算文件共享系统，每个节点可以将自己的一个或多个目录下的文件共享给 网络中的其他成员，也可以分享其他成员所共享的资源，软件可以自动最新的文件列表， 发布者无需担心发布问题。 设计在应用层的逻辑上的覆盖网络( o v e r l a yn e t w o r k ) t 4 】是p 2 p 技术的核心机制。其封装 了t c p i p 模型中的下面三层，让p 2 p 网络的研究者和开发者不必关心它们是如何工作， 而仅仅去考虑应用层覆盖网络的工作情况，从而将精力集中在覆盖网络的设计和优化上。 对于p 2 p 覆盖网络的网络模型，按照节点信息存储与搜索方式的不同，可以分为两类： 无结构的p 2 p 系统和结构化的p 2 p 系统。典型的无结构p 2 p 系统有c h o r d t 引、c a n l6 。、p a s t r y 7 】 等。无结构p 2 p 系统的缺点之一就是，查询过程中采取盲目的方式，比如泛洪( f l o o d i n g ) 等，不仅查询效率低，还会导致网络中出现大量的数据包，影响整个网络的性能。结构化 p 2 p 系统的出现，将文件的存放与覆盖网络的拓扑关联起来，很好的弥补了这个不足。 在结构化p 2 p 系统中，每个节点只需要存储某些信息或其索引：当用户需要获取信息 时，需要知道这些信息可能存在哪些节点中。由于用户预先知道应该搜索哪些节点，从而 提高了信息搜索的效率。结构化p 2 p 系统依靠分布式哈希表d h t t 引，来准确、高效地路由 消息和定位数据对象。d h t 将信息分布存储在覆盖网络的节点上并在节点动态地加入和离 丌覆盖网络时，将拓扑的更新信息通知其它节点。而网络拓扑的特性常受限于其所基于的 基本拓扑图，与已知的拓扑图相比较，广义p e t e r s o n 图p 4 】有着一些更好的特性，如常量度 和最优网络直径。但目前还没有基于广义p e t e r s o n 的覆盖网络，因此本文对广义p e t e r s o n 图进行了研究，然后设计了基于广义p e t e r s o n 图的新型p 2 p 覆盖网络。 基于广义p e t e r s o n 图的p 2 p 覆盖网设计与分析 1 2p 2 p 基本概念和特点 p 2 p ( p e e r - t o p e e r ) 系统1 4 】由一组地位相等的节点构成，节点间可以直接通信，无需第三 方参与。p 2 p 网络是建立在i n t e r n e t 之上的覆盖( o v e r l a y ) 网络t 4 1 ，是一个逻辑网络。p 2 p 网络的出现改变了传统的处理资源的方法，将网络边缘计算机上的资源有效地利用起来， 为所有网络用户提供更强大而且更可靠的服务。p 2 p 网络的出现，呈现出一系列不同于c s 模型的新特点，也出现了一些在传统的分布式网络中没有的新问题，主要体现在以下几个 方面f 9 】= ( 1 ) 分散性( 非中心化) 分散性是p 2 p 系统最基本的特点之一。整个p 2 p 系统中的服务和资源分散在每个节点 上，所有服务的实现和资源的共享并不需要服务器而是在节点之间直接进行。p 2 p 系统的 分散性的特点，使其在整个系统的扩展性方面具有很好的优势。但由于不存在特定的设备 或软件来随时加入系统的每个节点，因此也带来了维护方面的问题。 ( 2 ) 动态性 每个节点都可以随时加入和退出p 2 p 系统。由于每个节点加入系统的最终目的都是从 其它p 2 p 节点中获得自己所需要的资源。因此，从节点加入直到退出p 2 p 系统所经历的时 间不会很长。有实验测算，在n a p s t e r 和g n u t e l l a 系统中，节点的平均在线时间仅为2 个 多小时【2 ，1 1 】，节点的高度动态性使得维护数据可用性的工作相当困难。 ( 3 ) 可扩展性 p 2 p 的分散性同时也使系统的可扩展性得到了提高。很多因素都可以影响可扩展性：例 如同步与合作的数目，应用所展现出来的固有并行性，需要保存维护的状态数目，以及用 来实现计算的程序模型等。获得好的扩展性不应当以牺牲其他必要特征为代价。为了解决 这类问题，可以保留一定数目集中化的操作和文件。 假设p 2 p 系统只有两个节点，一个节点只能从另一个节点上下载所需数据，则与简单 的c s 模式类似；假如p 2 p 系统有更多节点，那么就可以同时从不同的节点上下载数据， 从而具有更高的传输效率。因此，p 2 p 系统在大规模的网络中会有更好的性能优势。然而， 大多数p 2 p 节点都是试图从其他节点下载数据，自己共享的数据往往比较少，这对于整个 p 2 p 系统性能有一定的影响。 目前已经出现了很多的p 2 p 应用系统，并且应用在大规模的网络中。在这种情况下， 对于p 2 p 系统的网络拓扑结构的研究就具有很高的研究价值。如何实现每个节点能够维护 有限的节点信息，但却能够获得更多节点的信息和保证任意两个节点能够通信，这成为了 一个重要的研究方向。 ( 4 ) 隐私性 中继服务器一般用来解决因特网中的隐私泄露问题。在p 2 p 系统中所有p 2 p 节点都可 以提供中继转发的功能，从而大大提高了匿名的可靠性，为用户的隐私提供了更好的保护。 2 基于广义p e t e r s o n 图的p 2 p 覆盖网设计与分析 同时这个优点其实也是p 2 p 系统的一个缺点，这使得p 2 p 系统上一些非法信息来源不清楚， 导致了非法信息的增多，出现了信息管理困难等问题。p 2 p 系统的每个节点都是匿名登陆 到系统中的，并且数据信息的传输在各个节点之间直接进行而无需经过服务器，从而使得 用户的隐私信息泄漏的可能性大大减少。 ( 5 ) 健壮性和容错性 p 2 p 系统是以自组织的方式建立起来的，并允许节点自由地加入和退出这个系统。不 同的p 2 p 系统具有不同的网络拓扑构造方法，可以根据网络带宽、负载变化情况等不断自 适应地调整拓扑结构，具有很好的健壮性。由于p 2 p 系统节点分布广，服务分散在各个节 点上，某些节点或网络遭到破坏时对其它节点的影响很小或几乎没有。然而同时某些节点 之间的连通性会出现问题，但是p 2 p 系统都具有自动调整机制，即便是某些节点失效了， 仍可以重构整体拓扑，保持与其它节点的连通性，具有较好的自适应性。 1 3 论文的组织结构 第一章的绪论简要介绍了p 2 p 网络的发展状况、问题提出的原因、文章的工作及组织 结构。 第二章分析了结构化p 2 p 覆盖网络设计时的一些关键技术并对一些经典的p 2 p 覆盖网 络进行了研究。 第三章构造了一个基于广义p e t e r s o n 图的p 2 p 覆盖网络g p n e t 。第一节t 对g p n e t 的 拓扑结构：广义的p e t e r s o n 图进行了研究，对其性质进行了分析；第二节：定义了g p n e t 中键值的分配，并给出了键值分配的例子；第三节：分析了这个新型p 2 p 覆盖网络g p n e t 的路由情况，给出了设计的路由表，路由表具体实例和具体路由算法；第四节：对g p n e t 的自组织性和自适应性如t 节点的加入和离开，进行了分析，同时给出了节点加入过程的 一个例子，并给出了节点加入的算法。 第四章对设计的g p n e t 进行仿真试验分析。第一节是仿真实验的方案；第二节给出了 平均路径长度，拓扑鲁棒性和负载分配的仿真实验的结果。 第五章是总结和展望部分，对全文进行总结并展望下一步的研究工作。 基于广义p e t e r s o n 图的p 2 p 覆盖网设计与分析 第二章结构化p 2 p 覆盖网络关键技术 本章详细论述了p 2 p 覆盖网络的关键技术和研究现状。这一内容的研究是下一步提出 新型p 2 p 覆盖网络的重要理论基础。 2 1 结构化p 2 p 覆盖网拓扑结构 2 1 1 分布式哈希表d h t 在p 2 p 系统中使用d h t i j s 最为关键的问题是：设计出的d h t 能够适应高度动态变化 的p 2 p 系统，能够将关键字均匀分布到各个节点上；使得关键字k e y 查询请求能够准确快 速地转发到目标节点上，并且整个网络维护起来要简单，维护开销小，稳定性要好。分布 式哈希表( d h t , d i s t r i b u t e dh a s ht a b l e ) 是p 2 p 网络的一个核心设施，它基于一致性散列函 数，提供对于任何一个节点、数据对象在覆盖网中的位置映射。这在结构化p 2 p 网络中尤 其重要，其不仅保证了能够准确地定位到某个节点或某个数据对象同时还提供p 2 p 网络的 匿名性。d h t 采用一致性散列函数h ( ) ，对于某个网络节点( i p ，p o r t ) ，该节点在覆盖网上将 有唯一对应的标识n o d e l d = h ( i p ，p o r t ，) ，i p 为节点i p 地址，p o r t 为端口号，表示其他属 性；对于某个数据对象( k e y , ) ，它在覆盖网上也有唯一的标识o b j e c t l d = h ( k e y ，) ，k e y 为对象的关键码表示其他属性。对节点而言，n o d e l d 确定了它的覆盖网位置；对数据 对象而言，o b j e c ti d 确定了它的索引信息在覆盖网上的存放位置。 图2 1 【l l 】所示的p 2 p 体系架构反映了d h t 在p 2 p 网络中的地位。分布式散列表位于结 构化p 2 p 应用和p 2 p 覆盖网之间，它组织覆盖网中的节点，向上层提供三个最基本的接口： ( 1 ) p u t ( k e y ，v a l u e ) ：向网络中存储具有标识k e y 的数据v a l u e 。 ( 2 ) r e m o v e ( k e y ) ：在网络中删除具有标识k e y 的数据对象。 ( 3 ) v a l u e = g e t ( k e y ) ：从网络中获取具有标识k e y 的数据保存在v a l u e 中。 p i j l i i 江jv ；o l t l z g e t j ( p = 。1 ) ( p e c i ，) ( p e e l ， )f 。f e l j 、 、，。 、一 、- 、一 图2 1p 2 p 体系架构及其应用接口 4 e = | ；i 、 e k 亡 = = 0 rt 毗睁a、 射卜i 蚶k 时 n 基于广义p e t e r s o n 图的p 2 p 覆盖网设计与分析 2 1 2 结构化p 2 p 覆盖网拓扑结构 结构化p 2 p 网络最大的特点在于它们都有一个严格的覆盖网络拓扑结构，这也是其区 别于混合式p 2 p 和无结构p 2 p 的主要特征。 下面是当前结构化p 2 p 网络主要使用的几种拓扑结构： ( 1 ) 环结构( 带弦环) 所有节点被组织在一个环上，环只提供两种功能取得当前节点的前驱和后继( 如果 是单向环只提供后继) ，只要后继关系正确，它就能够保证正确的定位。为了加速定位，往 往在环上加入弦，即每个节点维护一个路由表，指向环中离自己很远的节点。采用环形结 构的p 2 p 网络有p a s t r y 7 1 、c y c l o i d l l7 1 、c h o r d t l9 1 、k a d e m l i a l 2 0 1 、等，其中c h o r d 是最纯粹 的带弦环，其弦是指数间隔的，下标越大的弦指向越远；p a s t r y 混合了环形和超立方体， 其叶集反映了环属性，同时，p a s t r y 的路由表也可以理解成一种弦；k a d e m l i a 是基于异或 度量的带弦环，其中的弦也是指数间隔的，但其指向很松散，没有c h o r d 那样严格的要求： c y c l o i d 是带环的立方体结构( c c c ) ，首先每个节点都在一个小环上，通过内叶集来维护， 其次每个小环有其前驱、后继环，从而将小环串成了一个大环，并通过外叶集来维护。 2 2 4 1 t j _ 驯，j 路挺 n o d es u c c 56 66 81 3 1 21 3 2 02 4 图2 2c h o r d 环n = 2 5 ( 2 ) 基于网格的d h t ( 多维空间) 所有节点被组织在一个多维笛卡尔空间里，每个节点有自己在空间中的邻居。采用多 维空问的p 2 p 网络是c a n l 酬，多维空间结构更严格的说是多维环面( t o m s ) 结构。也就 是基于网格的结构。c a n 使用了一张大的散列表，由大量的节点组成。c a n 使用基于虚 拟的d 维笛卡儿坐标空间来实现其数据组织和路由查找功能。每个节点保存散列表中的一 些节点信息，称为一个区域，并且每个节点维护的邻居就是与这个区域相邻的其它d 个区 域中的节点。路由表的大小是2 d 项，即d ( d ) 。在路由查找过程中，只需将查询请求发送 到离k e y 值更近的邻居，其平均路由长度为o ( d n n ) ，是节点规模大小，d 是维数。当 基于广义p e t e r s o n 图的p 2 p 覆盖网设计与分析 d = l o g n 时，路由表的大小为l o g n ，平均路由长度为l o g n ，与其它几个路由算法的性能 相同。c a n 的设计思想是完全分布式的，它不需要其它任何的中介，具有很好的扩展性， 节点只需维护部分其它节点的状态信息，而且这部分节点状态信息独立于整个网络规模。 ( 3 ) 超立方体 所有节点被组织在一个超立方体中，采用此结构的有t a p e s t r y 、p a s t r y 和它们的前驱 p l a x t o n 。但是，这三种结构化p 2 p 网络都不能算作严格的超立方体结构，因为它们的覆盖 网络采用了p l a x t o nm e s h 的拓扑结构，每层维护匹配n o d e l d 不同长度前缀( 或后缀) 的节 点。p a s t r y t 7 j 使用一个近似的超立方体结构，网络中的每个节点都有一个唯一的节点仍。 每个节点维护一个m 行疗列的路由表，其中，第f 行第，列的项是从第f 一1 位数字与当前节 点相同，第f 位为，一1 的任意一个节点。在路由查找时，节点会将查询请求转发到路由表 项中所有节点中与关键字最接近的那个节点。p a s t r y 平均路由长度为o ( 1 0 9 n ) ，这罩是 整个网络的规模。在p a s t r y 系统中，考虑了网络的位置信息，目的是使消息传递的距离最 短，这里的距离类似于i p 路由中的跳数。p a s t r y 具有较好的容错性，适用于高动态性的网 络。 ( 4 ) 蝶形网 蝶形网【2 2 1 中，每个节点有它的层( l e v e l ) ，每层的节点通常维护两个下边，一个上边 以及两个同层边。采用蝴蝶结构的p 2 p 网络有v i c e r o y 等，不过每个v i c e r o y 节点还保存一 个前驱，一个后继，从而又组织成了一个全局的环结构。v i c e r o y 系统中每个节点有两个值： 仍和b u t t e r f l y 层号，记作( i d ，l e v e l ) 。节点的i d 独立一致地从【o ，l 】上产生，层号l e v e l 从 【1 ，l o gn 】上随机选择，这里是网络规模。节点的i d 值是不定不变的，但l e v e l 值是动态 变化的。v i c e r o y 系统中，数据存放在后继节点中，与k o o r d e 系统相同，而c y c l o i d i l 系统 中是将数据存放在最接近的节点上的。 ( 5 ) d eb r u i j n 图 d eb r u i j n 图【2 3 】中，每个节点m 有两条出边：一条指向节点2 m ( m o d2 6 ) ，另一条指向节 点2 m + l ( m o d2 6 ) ，其中b 为仍位数。k o o r d e 将d eb r u i j n 图嵌入到了c h o r d 环中，提高了 路由效率。 d b r ( d eb r u i j nr i n g ) 图是将上面重新定义的d eb r u i j n 图和r i n g 加以组合。在 d b r ( k ，m ) 图中，无论k 和m 取任何值，即不管图中节点数目有多少，节点均保持入度、 出度为2 不变( 包括指向自身的边) 。 ( 6 ) c c c 一个d 维的c c c l 2 5 1 图指的是在一个d 维的超立方体上将各个节点替换成含有d 个节 点的环而构成的图。每个点的度数都相同，均为3 。因此，利用这种图作为网络拓扑结构 得到的p 2 p 系统即可视为一个常量度p 2 p 系统。c y c l o i d 是基于c c c 结构的常量度p 2 p 模 型。 6 基于广义p e t e r s o n 图的p 2 p 覆盖网设计与分析 2 2 结构化p 2 p 覆盖网的路由和定位 对p 2 p 而言，定位是指确定位置的过程，它包括两种情况 2 6 j ：( 1 ) 节点a 想确定节点b 的位置；( 2 ) 节点a 想确定数据对象o 的位置。不管哪种情况，p 2 p 网络定位都是通过一步 一步的路由来完成的。路由的作用在于将消息送给离目的地更近的节点，而这里的近有多 个角度的衡量，因此也就有了各种的p 2 p 路由方法。 结构化p 2 p 覆盖网络的路由和定位方式通常取决于两个因素：( 1 ) 覆盖网络的拓扑结 构；( 2 ) 路由表的结构。基于这两个因素，结构化p 2 p 网络通常都维护一个比较小的路由表 ( 可变长度或者常量度) 。采用分布式、局部性的贪心路由算法，逐步缩小当前节点与目的 节点之间的i d 差异。通常定位效率为o ( 1 0 9 ) 跳，并且能够保证定位成功，单就覆盖网而 言，此定位效率接近最优。本节中主要研究结构化p 2 p 网络中主要的几种路由方式。 2 2 1 数值临近路由 这罩的数值通常是指节点i d 值。在路由过程中每一步，当前节点都从自己的路由表 中选择与目的i d 最邻近的节点作为下一跳。因此，路由路径中每一跳的节点i d 与目的i d 的差距会越来越小，直至最接近目的i d 的节点为止。广义上，几乎所有的结构化p 2 p 路 由算法，都可以算是数值邻近路由，只不过路由表的构造不同( 比如c h o r d 使用指数间隔 的f i n g e rt a b l e1 1 9 】，而t a p e s t r y 使用来自p l a x t o n 的层次化路由表2 1 1 ) ；或者是对于邻近的 度量不同( c a n 的邻近是指空间位置的邻近，而k a d e m l i a 则是基于异或值来度量距离。) 2 2 2 逐位匹配路由 逐位匹配路由出自p l a x t o n ，其后t a p e s t r y 、p a s t r y 继承并扩展，分别采用后缀匹配路 由和前缀匹配路由。基于层次化的路由表，每一步通常都能和目的i d 多匹配至少一位， 因此逐位匹配路由的效率等价于i d 的位数也就是o ( 1 0 9n ) 。 2 2 3 位置邻近路由 c a n 是最典型的位置邻近路由，每个节点的路由表记录自己在多维空间中的邻居。每 次选择离目的节点最近的邻居作为下一跳，其定位效率等价于多维空间的直径d ( d 瓶) ， 如果取d = l o g n ，d ( d 河) 电就是o ( 1 0 9 n ) 。可以看出c a n 与其他结构化p 2 p 网络路由方 法是类似的。 7 基于广义p e t e r s o n 图的p 2 p 覆盖网设计与分析 2 2 4 层次路由 bxf 卜一 n i 一 ， 图2 6c a n 路由图 p 2 p 网络如果将节点组织到多个层次上，路由过程通常是先从底层爬到高层，再从高 层爬到底层。v i c e r o y 采用了蝶形网层次路由，通过其路由表中的上边、下边，首先沿着上 边走到根也就是一层节点，然后从一层节点出发沿下左边或者下右边往下一层走。s k i p n e t 的n u m e r i c i d 路由也是层次化进行的：首先查找根环，直到发现一个节点与目的节点的 n u m e r i c i d 匹配第一位，再通过这个节点爬升到它的1 层环，在l 层环上查找与目的节点 n u m e r i c i d 匹配的前两位的节点。依次如此，每次上升一层多匹配一位，直到不能匹配更 多位，又找不到n u m e r i c i d 更接近的节点为止。并且，节点都被组织到l o g n 个层次上， 所有路由效率都是o ( 1 0 9 n ) 跳。 v i c e r o y 的路由过程包括三个阶段： ( 1 ) 上升阶段：沿着路由表中最后一项指向上层节点的指针，一直往上，上升到第一层 的某一个节点，这个节点成为根节点( r o o t ) 。 ( 2 ) 下降阶段：沿着路由表中指向下层节点的指针，一直往下，直到没有向下连接的节 点。 ( 3 ) 横向阶段：在同层连接上达到目标节点。 2 2 5 混合式路由 大多数结构化p 2 p 网络的路由方式都不是单一的，如c h o r d 、p a s t r y 、v i c e r o y 、k o o r d 、 c y c l o i d 中都使用了环形路由作为基础，但又结合了各自独特的路由方式。c y c l o i d 使用了 类似p a s t r y 的超立方体路由( 属于逐位匹配路由) ，又结合了两种不同的环形路由【1 7 1 ：一 是主坏上的环形路由；二是每个小环上的环行路由。而结构化p 2 p 网络的路由效率始终在 基于广义p e t e r s o n 图的p 2 p 覆盖网设计与分析 o ( 1 0 9 ) 跳不变。 c y c l o i d 系统中，节点总数为n = d 水2 d ，节点i d 采用二维结构( 七，a d - l ，a a 口a o ) 。这罩， k 表示环标号，0 k d l 。二进制数嘞一l _ 2 表示立方体标号，0 a a ，l a a 2 a o 2 d - 1 。 具有相同立方体标号的节点按k 值组织成的一个环称为局部环( 1 0 c a lc y c l e ) ，局部环中环标 号最大的节点称为主节点。具有不同立方体标号的局部环互为远环( r e m o t ec y c l e ) 。所有的 局部环按立方体标号组成一个大环( 1 a r g ec y c l e ) 。 对于给定的一个数据( 关键字为k e y ) ，该数据的存放节点的环标号为k e y m o d d ，立方 体标号是姊d ，如果该节点在线，则将数据存放在该节点上；如果该节点不在网络中， 则首先选择与该数据立方体最接近的节点存放，然后选择与环索引最接近的节点存放。 2 3 动态节点算法 p 2 p 网络的最大特点就是在于它极大的动态性：不断有新节点加入、旧节点离开、节 点失效等情况发生。在动态环境里。p 2 p 网络需要建立一套健全、可行的方法来处理各种 动态问题，在新节点加入时通知其他节点新成员的到来，在旧节点离开时通知其他节点老 成员的离去，而最难的是需要高效、合理的检测到节点失效并及时的修复p 2 p 网络【2 引。这 就是动态节点算法需要研究的内容，也就是p 2 p 覆盖网络的自组织性和自适应性。 2 3 1 节点的加入 新节点n 加入结构化p 2 p 网络通常需要做下列工作：第一，初始化自己的路由表：第 二，告诉其他节点自己的到来，更新它们的路由表；第三，应由新节点n 负责的对象索引 必须从现存节点移交给n 。 第一步：初始化路由表。首先通过某种方式链接到一个入口节点g ，通常这个节点是 众所周知的。通过g 发送消息给离n 最近的节点( 也就是n o d e l d 最近) 。此后有两种方式 得到n 的路由表： ( 1 )直接从离n 最近的节点那里获得路由表，如c h o r d 。这也是本论文在第三章中 构造的新型p 2 p 覆盖网络g p n e t 所采用的获得路由表的方法。 ( 2 ) 从路由过程中走过的每一跳的节点那罩获取自身路由表的信息，如t a