（计算机应用技术专业论文）基于特殊图类的p2p覆盖网络设计与分析.pdf

基于特殊图类的p 2 p 覆盖网络设计与分析 摘要 结构化p 2 p 系统中资源处理是当前面临的重要问题，覆盖网络的拓扑结构是解决这 一问题的重要途径。因此，为网络设计合适的拓扑结构是非常重要的。众所周知，构造 p 2 p 网络拓扑有两个重要的必要条件：第一，为了处理节点的自由动态操作，p 2 p 网络 总是追求任意规模和任意度的拓扑，如节点的加入和离开；第二，p 2 p 网络尝试着设计 和实现有最小直径和固定度的拓扑。k a u t z 有向图对网络设计具有一些良好性能，如常 量度和最优直径但目前还没有基于k a u t z 图的覆盖网络，因此本文对k a u t z 图进行了 研究，并在第三章设计了一个基于k a u t z 有向图的内容寻址网络。 然而，k a u t z 有向图的阶是一系列不连续整数，在给定度d 的情况下不能包含所有 整数为了实现一个具有任意规模和度的覆盖网络，第四章构造了一个基于广义k a u t z 有向图和环的p 2 p 网络( b g k r ) p 2 p 中b y z a n t i n e 错误是由对抗的矛盾节点行为形成的，b y z a n t i n e 攻击者互相联 合能使整个p 2 p 网络操作瘫痪第五章讨论基于d h t 具有b y z a n t i n e 容错的覆盖网络 ( r e i k ) 为满足多条路由路径，我们构造以嵌入逆k a u t z 有向图的环作为拓扑结构，因 为逆k a u t z 网络提供了多个入口节点和多条路由路径。r e i k 是第一个具有b y z a n t i n e 容 错的常量度、对数性直径和常量拥塞的结构化p 2 p 覆盖网。对于大型d 2 ，r e i k 覆 盖网有效地处理了随机错误和b y z a n t i n e 错误，此性能比c h o r d 和c a n 的更强。 大型p 2 p 系统典型的特点是具有千百万频繁动态行为的节点当前的结构化覆盖 网络在动态活动中确定好的节奏，这产生了高的维护开销研究已证明p 2 p 系统中参 与节点不是对等的，一些称为超节点的节点比其它节点更强更稳定，这种异构性已用在 p 2 p 系统的设计中在第六章中，我们采用超节点设计一种新型的层次r e i k 覆盖网络 ( h r e i k ) ，它降低了r e i k 系统的维护开销并提供了高质量路由服务。结果证明了与当 前结构化p 2 p 系统比较，传递更好路由性能时h r e i k 降低了维护开销。 本文主要研究结构化p 2 p 网络的设计和分析，共分为七章。 本文的第一章绪论说明了研究的背景和问题的提出、论文的工作及组织结构；第二 章是优化d 2 b 覆盖网络的路由和负载均衡；第三章是构造基于k a u t z 有向图的c a n 网 络( k z c a n ) ；第四章设计基于广义k a u t z 有向图和环的p 2 p 覆盖网络( b g k r ) ；第五章 利用逆k a u t z 有向图解决p 2 p 网络中的b y z a n t i n e 错误( r e i k ) ；第六章采用层次化结构 降低r e i k 网络的维护开销；第七章给出总结并展望下一步要做的工作 关键词：p e e r - t o - p e e r ，覆盖网络，分布式哈希表( d h t ) ，k a u t z 有向图，常量 度数，拥塞，b y z a n t i n e 容错，层次化 a b s t r a c t t h ec u r r e n tw o r kd e a l sw 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 so 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 e o fs t r u c t u r e dp 2 ps 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 nas u i t a b l e t o p o l o g yf o r n e t w o r k s i ti sw e l lk n o w nt h a tt h e r ea r et w oi m p o r t a n tr e q u i r e m e n t sf o rp 2 pn e t w o r kt o p o l o g i e s f i r s t ，p 2 pn e t w o r k sa l w a y sp u r s u eat o p o l o g yw i t ha r b i t r a r ys i z ea n dd e g r e ei no r d e rt od e a lw i t h t h eu 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 ，s u c ha sj o i n i n g ，d e p a r t i n ga n df a i l i n g s e c o n d ，p 2 p n 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 yw i t ha sm i n i m u md i a m e t e ra sp o s s i b l eg i v e n nn o d e sa n df i x e dd e g r e ed t h ek a u t zd i g r a p hh a ss o m ei n t e r e s t i n gp r o p e r t i e sf o r t h ed e s i g n i nn e t w o r k s ，e g ，c o n s t a n td e g r e ea n do p t i m a ld i a m e t e r i nt h et h i r dc h a p t e rw ed e s i g nac a n n e t w o r kb a s e do nt h ek a u t zd i g r a p h h o w e v e r ，t h eo r d e r so fk a u t zd i 暮r a p ha r eas e r i e so fd i s c r e t ei n t e g e r sb u tc a n n o tc o v e rg l l i n t e g e r su n d e rag i v e nd e g r e ed t oa c h i e v ea l lo v e r l a yn e t w o r kw i t ha r b i t r a r ys i z ea n dd e g r e e ，w e s t r u c t u r ean 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 dk a u t z d i g r a p ha n dr i n g s ( b g k r ) i n h ef o u r t h c h a p t e r b y z a n t i n ef a u l t si nap e e r - t o - p e e r ( p 2 p ) s y s t e ma r er e s u l t e df r o ma d v e r s a r i a la n di n c o n s i s t e n t n o d eb e h a v i o r s f a u l t yn o d e sc a nd i s r u p tt h er o u t i n gf u n c t i o n si nt h en o d ej o i n i n ga n dl o o k u p s c h e m e s b y z a n t i n ea t t a c k e r sm a yc o l l u d ew i t he a c ho t h e rt op a r a l y z et h ee n t i r ep 2 pn e t w o r ko p - e r a t i o n s w ed i s c o v e ran o v e ld h t b a s e do v e r l a yn e t w o r k s ( r e i k ) w i t hb y z a n t i n ef a u l tt o l e r a n c e i nt h ef i f t hc h a p t e r r e i kb a s e do nar i n gw h i c he m b e d sa ni n v e r s ek a u t zd i g r a p hi k ( d ，m ) ，t o e n a b l em u l t i - p a t hp 2 pr o u t i n g t h ei n v e r s ek a u t zn e t w o r kp r o v i d e sm u l t i p l ee n t r yp o i n t sa n d m u l t i p l er o u t e sb e t w e e nn o d ep a i r t h er e i ko v e r l a yi st h ef i r s tc o n s t a n td e g r e ea n do ( 1 0 gn 1 d i a m e t e rd h ts c h e m ew i t hc o n s t a n tc o n g e s t i o na n db y z a n t i n ef a u l tt o l e r a n c e f o rl a r g ed 2 。 t h er e i ko v e r l a y sh a n d l er a n d o ma n db y z a n t i n ef a u l t se f f e c t i v e l y , f a rb e y o n dt h ec a p a b i l i t yo f c h o r da n dc a n l a r g e - s c a l ep 2 ps y s t e m st y p i c a l l yh a v eh u n d r e d so ft h o u s a n d so fp e e r st h a ti n v o l v ef r e q u e n t d y n a m i ca c t i v i t i e s c u r r e n ts t r u c t u r e do v e r l a y sd on o ti d e n t i f yw e l lt h er h y t h mi nt h ed y n a m i c a c t i v i t i e s ，t h u sr e s u l t i n gi nh i g hm a i n t e n a n c eo v e r h e a d e m p i r i c a ls t u d i e sh a v es h o w nt h a tp a r - t i c i p a t i n gn o d e si np 2 ps y s t e m sa r en o te q u i v a l e n t s o m en o d e s ，k n o w na ss u p e rp e e r s ，a r em o r e p o w e r f u la n ds t a b l et h a nt h eo t h e r s s u c hh e t e r o g e n e i t yh a sb e e nt a k e ni n t oa c c o u n ti nt h ed e s i g n o fp 2 ps y s t e m s i nt h es i x t h c h a p t e r ，w ed e s i g nan o v e lh i e r a r c h i c a lr e i ko v e r l a yn e t w o r kb y e x p l o i t i n gs u p e rp e e r s ，h r e i k i tr e d u c e sr e i ks y s t e mm a i n t e n a n c eo v e r h e a da n dp r o v i d e sh i g h q u a l i t yr o u t i n gs e r v i c e t h er e s u l t ss h o wt h a th r e i kr e d u c e st h em a i n t e n a n c eo v e r h e a dw h i l e d e l i v e r i n gm u c hb e t t e rr o u t i n gp e r f o r m a n c e ，a sc o m p a r e dt oc u r r e n ts t r u c t u r e dp 2 ps y s t e m s 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 n sa 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 s ，a n di sd i v i d e d l l 基于特殊图类的p 2 p 覆盖网络设计与分析 i n t os e v e nc h a p t e r s i nt h ef i r s tc h a p t e rw 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 ew o r kw ed oi nt h ep a p e ra n dt h es t r u c t u r eo ft h ep a p e r t h es e c o n dc h a p t e ro p t i m a lr o u t i n ga n d l o a db a l a n c ef o rd 2 b i nt h et h i r dc h a p t e rw es t r u c t u r eak a u t zb a s e dc o n t e n t a d d r e s s a b l en e t w o r k ( k z c a n ) i nt h ef o u r t hc h a p t e rw ed e s i g nap 2 pn e t w o r kb a s e do ng e n e r a l i z e dk a u t za n dr i n g w i t hc o n s t a n tc o n g e s t i o n i nt h ef i f t hc h a p t e rw eu s ei n v e r s ek a u t zd i g r a p ht oh a n d l eb y z a n t i n e f a u l t s i nt h es i x t hc h a p t e rw ea d o p th i e r a r c h i c a ls t r u c t u r et or e d u c er e i ks y s t e mm a i n t e n a n c e o v e r h e a d t h es e v e n t hc h a p t e rm a i n l yp r e s e n tt 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 yw o r d s ：p e e r - t o - p e e r ，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 ) ，k a u t zd i g r a p h ，c o n s t a n t d e g r e e ，c o n g e s t i o n ，b y z a n t i n ef a u l tt o l e r a n c e ，h i b e r a r c h y 曲阜师范大学博士硕士学位论文原创，陛说明 ( 在口划“”) 本人郑重声明：此处所提交的博士口硕士留论文基于特殊 图类的p 2 p 覆盖网络设计与分析，是本人在导师指导下，在曲阜师 范大学攻读博士口硕士囵学位期间独立进行研究工作所取得的成 果。论文中除注明部分外不包含他人已经发表或撰写的研究成果。对 本文的研究工作做出重要贡献的个人和集体，均已在文中已明确的方 式注明。本声明的法律结果将完全由本人承担。 作者签名：前 日期：7 , 0 0 8 彩6 曲阜师范大学博士硕士学位论文使用授权书 ( 在口划“”) 基于特殊图类的p 2 p 覆盖网络设计与分析系本人在曲阜师范大学 |f 攻读博士口硕士回学位期间，在导师指导下完成的博士口硕士留 学位论文。本论文的研究成果归曲阜师范大学所有，本论文的研究内 容不得以其他单位的名义发表。本人完全了解曲阜师范大学关于保 存、使用学位论文的规定，同意学校保留并向有关部门送交论文的复 印件和电子版本，允许论文被查阅和借阅。本人授权曲阜师范大学， 可以采用影印或其他复制手段保存论文，可以公开发表论文的全部或 部分内容。 作者签名：1 袋前静 导师签名：螽务勃虱 日期：舢孑幺占 日期：加易， 基于特殊图类的p 2 p 覆盖网络设计与分析 背景和问题的提出 第一章绪论 最近几年，p e e r t o - p e e r ( 简称p 2 p ) 1 】迅速成为计算机界关注的热门话题之一，财富 杂志更将p 2 p 列为影响i n t e r n e t 未来的四项科技之一 2 , 3 】p e e r t o - p e e r 即对等计算或对 等网络，通常简称为p 2 p ，它可以定义为：网络的参与者共享他们所拥有的一部分硬件 资源( 处理能力、存储能力、网络连接能力、打印机等) ，这些共享资源通过网络提供服务 和内容，能被其它对等节点( p e e r ) 直接访问而无需经过中间实体在此网络中的参与者 既是资源( 服务和内容) 提供者( s e r v e r ) ，又是资源获取者( c l i e n t ) 从计算模式上来说， p 2 p 打破了传统的c l i e n t s e r v e r ( c s ) 模式，在网络中的每个节点的地位都是对等的。每 个节点既充当服务器，为其他节点提供服务，同时也享用其他结点提供的服务除此之 外，节点可以在任意时刻加入或离开网络，并能路由到目的节点，节点动态地加入和离 开网络时，维护网络的结构和功能成为设计的主要目的 p 2 p 系统最大的特点就是用户之间直接共享资源，其核心技术就是分布式对象的定 位机制，这也是提高网络可扩展性、解决网络带宽被吞噬的关键所在迄今为止，p 2 p 网 络已经历了不同网络模型，各种模型各有优缺点，有的还存在着本身难以克服的缺陷 因此在目前p 2 p 技术还远未成熟的阶段，各种网络结构依然能够共存，甚至呈现相互借 鉴的形式 按照节点信息存储与搜索方式的不同，p 2 p 系统可分为两大类：非结构化( u n s t r u c - t u r e d ) 系统和结构化( s t r u c t u r e d ) 系统在非结构化系统中，每个节点存储自身的信息 或信息的索引当用户需要在p 2 p 系统中获取信息时，它们预先并不知道这些信息会 在哪个节点上存储。因此，非结构化p 2 p 系统中信息搜索的算法难免带有一定的盲目 性，如简单的泛洪式查找( f l o o d i n g ) j 4 一一将查询传播到所有相邻的节点和随机步行方法 ( r a n d o m w a l k e r s ) 5 】一一将查询传播到随机选择的一些邻节点上，直到目标找到为止此 系统的优点在于实现结构简单，无需中央服务器，节点之间完全平等，网络的层次是单一 的，而且节点之间无需维护拓扑信息g n u t e l l a 6 和f r e e n e t 7 ，8 ，9 是典型的非结构化p 2 p 系统，它们虽然支持分布式的查找策略，但是它们都采用的是类似于o s p f 路由协议【1 0 】 的洪泛机制，这种机制一方面造成网络通信负担较大，另一方面可扩展性也较差随着 对等网络系统规模的增长，系统的可扩展性成为迫切需要解决的问题，也成了研究的热 点近年来许多研究小组在设计可扩展的查找机制方面做了大量的研究工作 1 1 ，1 2 】，提 出了多种具有良好可扩展性的分布式哈希查找系统并基于这些分布式哈希表( d i s t r i b u t e d h a s ht a b l e ，d h t ) 1 3 ，1 4 构造了新一代的结构化p 2 p 系统 在结构化p 2 p 系统中，每个节点只存储特定的信息或特定信息的索引当用户需要 在p 2 p 系统中获取信息时，它们必须知道这些信息可能存在哪些节点中由于用户预先 知道应该搜索哪些节点，这就避免了非结构化p 2 p 系统中使用的泛洪式查找，因此提高 基于特殊图类的p 2 p 覆盖网络设计与分析 了信息搜索的效率但是，结构化p 2 p 系统也引入了新的问题：首先，既然信息是分布 存储的，那么如何将信息分布存储在覆盖网络的节点上；其次，由于节点动态地加入和 离开覆盖网络，如何将拓扑的更新信息通知其它节点分布式哈希表的引入基本解决了 上面的问题，因此自从d h t 出现后，结构化p 2 p 的应用得到了快速的发展。典型的d h t 包括t a p e s t r y 1 5 】，c h o r d 1 6 】，p a s t r y 1 7 ，c a n 1 8 】和k a d e m l i a 1 9 】为了进一步提高系 统性能已出现了一些常量度p 2 p 系统，如c y c l o i d 2 0 】和h y p e r c u p 2 1 】它们以各自不同的 方式将节点组织起来，以便于数据的高效定位，同时还支持大规模的节点和数据，并能 适应p 2 p 系统中节点和网络的动态变化 d h t 是结构化p 2 p 网络中的关键技术，它的特性直接决定着p 2 p 网络及应用的性能 和可扩展性等对基于d h t 网络的研究是当前国际学术界的热点问题，有着重要的学术 价值和广阔的应用前景。结构化p 2 p 覆盖网络性能评价的重要参数有节点度数、网络直 径和拥塞特性等。很多研究 2 2 ，2 3 ，2 4 都在寻求常量度数且具有较小网络直径和较小拥塞 的覆盖网络。现有的大多数覆盖网络是基于一些传统的多机互联网络拓扑扩展而来的， 如c h o r d 1 6 、t a p e s t r y 1 5 和p a s t r y 1 6 】是基于h y p e r c u b e 拓扑 2 5 ，c a n 1 8 基于d 维的 t o r u s 拓扑，k o o r d e 2 6 和d 2 b 2 7 基于d eb r u i j n 图 2 8 ，2 9 ，3 0 】，v i c e r o y 3 1 基于b u t t e r f l y 拓 扑覆盖网络的特性常受限于所基于的基本拓扑图与上面使用的拓扑图相比较，k a u t z 图 3 2 ，3 3 】有着一些更好的特性，如常量度和最优网络直径但目前还没有基于k a u t z 图 的覆盖网络，因此本文对k a u t z 图进行了研究，然后分别设计了基于k a u t z 有向图、广义 k a u t z 有向图和逆k a u t z 有向图的的p 2 p 覆盖网络 p 2 p 应用非常广泛，但是有些性能得不到实现除非证明它有很好的鲁棒性 3 4 ，3 5 】 因此，路由和查找机制已成为p 2 p 系统的挑战性问题【3 6 ，3 7 ，3 8 ，3 9 】。在p 2 p 网络中路由 容错分为两大类：f a i l - s t o p 错误和b y z a n t i n e 错误 4 0 ，4 1 ，4 2 f a i l - s t o p 错误是节点或链接 失败产生的，在节点间可检查出此错误，失效的节点不需停止工作并且从系统中自动消 失。换句话说，p 2 p 网络利用简单的分离失效节点容纳f a i l - s h o p 错误。而b y z a n t i n e 错误 在p 2 p 网络中已被攻破，因为失效节点没有停止操作且很难检测这种错误。在节点加入 和查找中攻击者破坏了路由功能，如果得不到合理的控制，b y z a n t i n e 错误可能使得整 个p 2 p 网络操作瘫痪，l a m p o r t 等 4 3 对分布式计算阐明了b y z a n t i n e 问题在p 2 p 容 错方面现存的系统多数解决了随机进攻，每个节点仅遭到独立失效。然而，这些系统不 能有效地处理节点勾结 4 4 】因此，f i a t 和s a i a 在【4 5 】中利用增强图( e x p a n d e rg r a p h s ) 和蝶形( b u t t e r f l y ) 网络建立的d h t 攻破了节点勾结情况；n a o r 和w i e d e r 采用非常简单 的完全动态d h t 解决了随机b y z a n t i o n 攻击 4 6 。最近，在 4 7 中s c h e i d e l e r 证明了p 2 p 系统怎样抵挡多数b y z a n t i o n 节点加入网络，它主要关注了系统加入操作一个方面，而怎 样实现扩展查找没有讨论并且d h t 请求的加入和离开操作也没有详细说明。为了解决 p 2 p 网络的b y z a n t i n e 错误实现可扩展查找机制，我们采用多条路径路由，设计一个基于 逆k a u t z 有向图具有常量阻塞的新颖p 2 p 覆盖网( r e i k ) 在b y z a n t i n e 破坏了节点勾结 下，r e i k 保证了关键的路由功能本文讨论失效节点在加入或查找操作中能提供正确 的路由信息 2 基于特殊图类的p 2 p 覆盖网络设计与分析 动态性是p 2 p 系统非常普通的特征 4 8 】。当前p 2 p 系统主要考虑的动态性包括： 节点加入、离开和失败频繁的动态行为能导致自组织无效并有较高的维护开销，降 低了p 2 p 系统的总体性能。p 2 p 覆盖网络保证了当节点加入、离开和失败时系统能适 当工作因此，怎样降低维护开销并提供连续的高质量路由问题仍没有解决。本文中我 们采用超节点的层次化结构【4 9 】来降低维护成本，超节点是比其它节点更强更稳定的 节点研究已证明在p 2 p 网络中节点存在异构性，s a r o i u 5 0 】等证明了g n u t e l l a 系统的 5 0 左右的节点通话时间少于6 0 s ，大约1 0 的节点相对较稳定目前出现的系统b r o - c a d e 5 1 、e x p r e s s w a y 5 2 】和h o n e t 5 3 】采用超节点作为有利于路由的网络访问点，系统非 常稳定还提高了网络带宽。我们用r e i k 作为实例，它的主要维护成本是由于路由表的 周期更新，每次更新每个节点需要o ( 1 0 9 2n ) 个消息。网络的稳定性决定更新频率。如果 节点相对稳定，则刷新频率小，因此维护成本低；否则，节点更新较频繁，产生较高的成 一本为了不让节点周期性更新路由表，我们提出了层次结构化p 2 p 覆盖网络h r e i k 。 底层是普通的r e i k 环，而上层是维护环和r e i k 一样，我们令普通环的节点周期性 地探测后继节点，每次需要o ( 1 ) 个消息当检查到有变化时，通知某个超节点更新受到 影响的节点路由表，因此将普通环的维护成本降到了o ( 1 0 9 n ) 。维护层也是作为r e i k 环实现然而，由于用超节点构造维护环，因此它的成本比具有不同特征的相同结构环低 1 2 论文组织结构 第一章绪论中简要介绍了p 2 p 网络的发展状况、问题提出的原因、文章的工作及 组织结构。 第二章优化d 2 b 覆盖网络路由和负载均衡 第三章构造以k a u t z 有向图为拓扑结构的覆盖网络，即k z c a n ：基于k a u t z 有向 图的内容寻址网络 第四章设计拓扑结构为广义k a u t z 有向图的覆盖网络，即b g k r ：新颖的基于广 义k a u t z 和环的结构化p 2 p 覆盖网络。 第五章利用逆k a u t z 有向图解决p 2 p 网络中的b y z a n t i n e 错误，即r e i k ：具有 b y z a n t i n e 容错的新颖结构化p 2 p 覆盖网络 第六章采用层次化结构降低系统的维护开销，即h r e i k ：新颖的层次结构化p 2 p 覆盖网络 3 基于特殊图类的p 2 p 覆盖网络设计与分析 第二章优化d 2 b 覆盖网络路由和负载均衡 d 2 b 2 7 是基于d eb r u i j n 图的内容寻址网络它利用分布式哈希表( d r t ) 1 3 ，1 4 实现 了文件消息和存储位置的有效映射。d 2 b 具有良好的容错性和可扩展性，是完全自组织 的覆盖网络然而，它没有有效地解决系统的路由和负载均衡本章我们对d 2 b 的路由 和负载均衡提出了一些改进措施：通过增强的d eb r u i j n ( e b ) 优化路由链接和负载；利用 最短标识符优化路由；并且用最短标识符扩展优化负载均衡。标准的d 2 b 路由算法是利 用d eb r u i j n 图完成的，而我们的算法( e d 2 b ) 利用增强的d eb r u i j n ( e b ) 图实现。我们通 过使用e b 可得到，当节点数达到2 ( t 是非负整数) 且系统中所有节点的标识符长度相等 时，所有节点的度数相同因此利用e d 2 b 算法的系统达到了较好的负载均衡 2 1d 2 b d - 维d 2 b 潜在的静态拓扑是d eb r u i j n 图b ( d ，k ) ，d 2 且k 1 。b ( d ，k ) 是顶点为 字母表 o ，1 ，d 一1 ) 上长度为k 的所有字符串的有向图，且从任意节点x l x k 到d 个 节点x 2 z 南a 有边，其中a = 0 ，1 ，d 一1 如图2 1 所示b ( 2 ，3 ) 图2 1 d eb r u i j n 图b ( 2 ，3 ) 注意：所有节点o l q 都有圈，其中q o ，1 ，d 一1 ) b ( d ，k ) 是d 知个顶点，泸+ 1 条边的出正则简单有向图，且图的出度和入度均为d ，直径为k 为了简单起见，在文献 27 】中主要描述了2 维的d 2 b 网络它利用集合i t = 0 ，2 m 1 ) 作为键空间【5 4 1 ，也可以认为是长度为m 的二进制串集。d 2 b 所有参与者都用相同 的函数危在键空间瓦中查找资源d 2 b 的节点也用二进制字符串来表示，但是长度不能 超过m ，且最多有2 m 个节点函数h 7 将标记赋给节点。 在任意时刻，节点z 1 钒要么有唯一的孩子节点z 2 z j ，其中j k ，要么有多 个孩子节点z 2 x k y l y t ，其中1 z m k + 1 且可1 y t 形成一个字符串前缀全 集特殊地，如果z 2 x k y ，y t 是x ，x k 的一个孩子节点，则当前系统不会有标识为 z 2 z 七y 1 y t 的节点同样地，在给定的任意时刻，标识为z 1 z 知节点的父节点形式 要么是o z x l ，其中q o ，1 】且j k ，要么是触1 x k y l y t ，其中p o ，1 ) 且 1 z m k + 1 注意，这两种形式可以同时存在，但n p 在d 2 b 的路由链接中，因为节点0 0 和1 1 有自环，所以它们的孩子和父链接 与其它节点不同标记为o t q 的节点牡，它的孩子节点标记为a a 可1 y t ，2 1 ， 4 基于特殊图类的p 2 p 覆盖网络设计与分析 这里y 1 = 西，y 2 们是一个前缀全集节点u 的父节点要么是融a ，具有j k 个 q ，要么是否q q 可1 y l ，这里有k 个。并且l 1 在后面的情况中，y 1 y z 是一个 前缀全集 在d 2 b 中，路由操作和d eb r u i j n 图相同更确切地说，令x l z 惫是系统中节点让 的标识符，且k = k l 是任意键令s 是x l 孤的后缀和七l 的前缀形成的最 长二进制串，s 可能为空。如果s = z 1 z l | c ，则札管理键k 否则，如果札有唯一的标 识为z 2 z f 的孩子节点v ，则向此孩子节点继续查找键k 如果u 有多个孩子节点，则 向标识为z 2 x k y l y z 的孩子节点v 查找键k ，其中s y l 们是七l 的一个前缀 通过前缀全集的性质知道，存在这样的孩子节点并且唯一 新节点u 加入系统时，令v 是它的入口节点，节点钍随机选择一个临时标识符然 后，节点札接触v ，且通过网络从口发送一个加入消息此消息作为查找消息路由，而 临时标识符起到了键的作用因此，加入消息最终到达标识为z t x k 且与键对应的节 点w 通过标识符扩展，节点让获得标识符为x 1 z 七1 ，而节点w 扩展它的标识符为 z x k o 。然后，在存储w 的查找表中，将以x x k l 为前缀的所有键从w 传递给u 下一步是更新系统的链接，如孩子链接、父链接和兄弟链接 当已存在节点u 离开系统时，用兄弟链接为每个离开系统的节点找关键对由于兄弟 链接是有限制的，所以最终会找到关键对关键对的其中一个节点将代替离开节点u ， 且此关键对被另一个节点代替很显然，如果节点受损，离开过程不可能完全执行，甚 至根本不执行 由此可见，d 2 b 的节点加入并不能达到均衡的标识符长度，即没有实现空间的均衡 划分，因此我们提出了相应的改进优化措施，使得负载能得到有效的均衡，同时提高路 由效率 2 2 优化d 2 b 前面介绍了d 2 b 的基本结构，主要分析了d 2 b 的基本操作，如节点加入、离开和路 由本节提出了几种对d 2 b 的改进措施：利用增强的d eb r u i j n 图优化路由链接；通过采 用最短标识符提高路由效率；并且应用最短标识符扩展均衡负载 2 2 1 利用增强的d eb r u i j n 图优化路由链接和负载( e d 2 b ) 从图2 1 中看到节点( 0 0 0 ) 和( 1 1 1 ) 自链接实际上，形式为q q 的节点都有自链 接。由于它们的出度和入度均为k 一1 ，所以这些节点负载小，在文献【5 5 】中用仿真实验 证明了此结论为了减少较小度的节点，提出了增强的d eb r u i j n 图( e b ) 它消除了具有 自链接的节点，并使它们相互链接。图2 2 是修改图2 1 得到的增强d eb r u i j n 图e b ( 2 ，3 ) 我们利用e b 优化路由链接可提高系统的负载均衡。在e b 中消除了所有标记为 q q ，o l o ，d 1 ) 的节点的自环，所以它们对应的孩子节点和父节点发生了变 5 基于特殊图类的p 2 p 覆盖网络设计与分析 化标记为q q 的节点珏的孩子节点是西西( _ 的个数歹k ) 和q q 可1 y t ，z 1 ， 这里y 1 = 石y 2 y l 是一个前缀全集节点u 的父节点要么是西瓦( 的个数jsk ) 和 融q ，具有j k 个q ，要么是瓦石( _ 的个数j k ) 和砸q 可1 y l ，这里有k 个 n 并且z 1 在后面的情况中，可1 y t 是一个前缀全集 图2 2 增强的d eb r u i j n 图e b ( 2 ，3 ) 同样地，在加入过程中，标记为q a 的节点w 的链接更新也发生了改变下面我 们分别考虑它的孩子链接和父链接：( 新节点u 加入系统后，通过标记扩展节点w 得到 的标记是a q q ，节点u 得到的标记是q q 瓦) ( 1 ) 节点w 的孩子链接： w 的孩子节点标记为西石( - 的个数j k ) 和q o t y l 轨，f 1 ，且y l = 西。则 u 加入后，w 的孩子节点变成石石( _ 的个数j k ) 和q a 西而标识为o t q 石的节 点u 的孩子节点变成a q 动2 犰如下图2 3 所示 图2 3 ( 2 ) 节点w 的父链接分两种情况考虑： ( a ) 如果w 的父节点是西西( 瓦的个数j k ) 和融n ，具有j k 个a ，则u 加入后，w 的父节点仍是西石和西0 1 o l ，而u 的父节点变为w 和融a 如图2 4 所示 图2 4 ( b ) 如果w 的父节点是瓦石 的个数j k ) 和融q 可1 玑，这里有k 个a 并且 l 1 y 1 y t 是一个前缀全集则u 加入后，w 的父节点变成瓦西和满足1 = q 的 节点，而u 的父节点变成w 和满足可1 = 西的节点如图2 5 所示 图2 5 e d 2 b 继承了d 2 b 路由简单、高效及开销少的优点，它是在d 2 b 的路由链接上的改 进，在某种程度上提高了覆盖网络的可靠性由于d 2 b 中节点的标记是随机选择，标记 6 基于特殊图类的p 2 p 覆盖网络设计与分析 的长度也不固定，这样可以使网络具有高动态性，同时网络的可靠性没有得到很好的保 障网络的可靠性跟节点的度数是相关的。一个节点的度是该节点与其它节点相关联的 边数，度是衡量覆盖网可靠性的重要参数网络中并不是所有节点都具有相同的度，当系 统中的节点数达到2 并且具有相同长度的标识符时，e d 2 b 中所有节点的度是相等的， 这时e d 2 b 的稳定性比d 2 b 的更强，使得系统达到了相对较稳定的状态同时，e d 2 b 对于节点的路由也有了进一步的提高例如，在d 2 b 中从节点q o 到节点石西的路 由是最长的，即路由长度是它的拓扑结构d eb r u i j n 图的直径k 而在改进的网络e d 2 b 中将这两个节点直接连接起来使它的路由长度变成了1 这是最明显的提高，相应地， 其它节点间的路由也得到了进一步的提高 2 2 2 利用最短标识符提高路由效率 d - 维的d 2 b 系统中节点的标识符是基为d 的d eb r u i j n 串，且根据标识符和d eb r u i j n 图的链接规则组织节点节点的标识符也是其所占区域的标识，标识符越长，节点所占 的区域越小在d 2 b 系统中的路由策略和d eb r u i j n 图相似，路由到目的地s 在唯一的 节点u 处停止，此节点的标识符是s 的前缀。我们提出一种利用最短标识符的新路由算 法。也就是说，当节点路由消息时，它们选择一个具有最短标识符的邻居节点这样做 的理论依据是：在系统中，节点拥有的标识符越长则其所占的区域越小所以按节点最 短标识符路由经过的节点数必然减少 令l e n g t h m i n 是具有最短标识符的邻节点拥有的标识符长度路由操作如下： s e tl e n g t h m i 佗= 0 ； f o r ( 所有邻节点) i f ( 第i 个邻节点的标识符长度 l e n g t h m 讥) s e tl e n g t h m i n = 第i 个邻节点的标识符长度且向它发送请求； 2 2 3 利用最短标识符扩展均衡负载 由于在d 2 b 中节点的负载可通过标识符的长度来表示，因此，我们提出一种最短标 识符扩展的方法均衡负载。下面我们简单地介绍利用最短标识符扩展均衡负载的措施 当新节点加入系统时，加入消息发送给一些随机的没有失效的节点在d 2 b 系统 中，已存在节点不仅知道自己的标识符，还知道其邻节点的标识符。因此，新节点最终找 到一个节点u ，此时并不是直接扩展节点u 的标识符，而是比较节点u 和其各邻节点的 标识符长度，然后选出一个标识符最短的节点进行扩展这样就可获得更好的均衡性 当节点离开系统时，需要为离开的节点找取代点这将引起标识符的合并为了有更 好的负载均衡，d 2 b 试图合并具有最短标识符的节点离开节点产生一个离开消息从 7 基于特殊图类的p 2 p 覆盖网络设计与分析 此节点开始向具有较短标识符的邻节点发