（计算机软件与理论专业论文）面向覆盖网典型应用的对等计算研究.pdf

复日大学博 学位论文 摘要 建立在覆盖网基础上的对等计算研究不仅是理论研究的一个热点，而且得到 企业界的密切关注，已渗透到多种应用当中，并取得了丰硕成果。覆盖网应用的 深入发展，可以极大提高社会生产力，提高社会生活质量，取得更大的社会进步。 面对研究的深入和应用面的扩大，覆盖网领域出现了许多i p 网中不曾出现 的新问题和新挑战，覆盖网承载了更高的要求。专家学者开始关注这方面的新 应用和理论研究。而针对对等计算核心业务，并结合覆盖网三个热点应用来对 非结构化覆盖网拓扑模型新的发展与应用进行研究就是本文所致力完成的工 作。 本文研究的关键问题主要包括：应用层组通信中具有能力约束的任意源覆 盖多播；共享文件的覆盖搜索主流技术性能提高；w e b 文本信息搜索中搜索负 载与维护负载之问的合理均衡及搜索过程负载的均衡分布等。具体研究内容有： ( 1 ) 讨论在覆盖网基础上进行应用层任意源覆盖多播的方法和相关技术。 本文提出一个任意源覆盖多播服务方案，无须建立显式的多播树。该 方案建立在随机覆盖网和非d h t 覆盖网拓扑模型基础上，具有结点能 力约束性能，同时多播树维护量小，具有动态成员管理能力。本文中 设计了2 个分布式多播算法。我们对搜索跳数和搜索负载进行了均衡 性能的理论分析，模拟实验显示新的任意源多播算法拥有较好的综合 性能。 ( 2 ) 讨论覆盖网共享文件主流搜索工具性能问题及相应解决方法。本文重 点研究了在没有集中索引结构的非结构化覆盖网络中如何改进搜索效 率。文章找出k a z a a 及g n u t e l l a 中影响性能的四个问题，并由此针对 每个问题提出了解决方法。文章的相关理论分析及模拟实验显示这些 方法较好地提高了文件搜索性能。 ( 3 ) 讨论如何有效地结合非结构化覆盖网与结构化覆盖网二者优势来设计 满足w e b 文本信息查询请求的语义网拓扑。本文结合w e b 文本信息 结构特征和语义相似性特征，构造面向文本信息查询的语义网拓扑， 提出一个两层结构的查询路由框架，不存在中央控制结构，实现在语 义网络中的查询路由功能。同时，本文提出了兴趣圈的概念，有效地 对w e b 文本数据源进行组织。实验显示建立在该语义网拓扑结构上的 文本信息查询能获得较好的查询准确性和查询有效性。 复口大学博十学位论文 关键词：覆盖多播，能力，非d h t 环，跳数复杂性，通信复杂性，分布式文件 共享，票据，搜索负载，搜索时间，非流行共享文件，随机邻居，w e b 文本信息，语义网，核心路由，边界路由 i 复日犬学博b 学位论文 a b s t r a c t o v e r l a yn e t w o r kt h e o r ya n dt e c h n o l o g yh a v en o to n l yb e e nah o t s p o ti nt h e o r y r e s e a r c hf i e l d ，b u ta l s oc a u g h tt h ei n t e n s i v ea t t e n t i o no fb u s i n e s sc i r c l e s t h e yh a v e b e e na p p l i e di nm a n yf i e l d s ，a n dh a v ea c h i e v e ds u b s t a n t i a lr e s u l t sm a i n l yi nt h ef i e l d s o fd i s t r i b u t e dc o m p u t i n g , f i l es h a r i n g , c o l l a b o r a t i v ec o m p u t i n ga n ds oo n t h ef u r t h e r d e v e l o p m e n to ft h ea p p l i c a t i o no ft h eo v e r l a yn e t w o r kc o u l dg r e a t l ye n h a n c et h e s o c i a lp r o d u c t i v i t y , i m p r o v et h es o c i a ll i v i n gq u a l i t ya n dt h e r e f o r em a k e b i g g e rs o e i a l p r o g r e s s a l o n ew i t ht h ed e e p e n i n go ft h er e s e a r c ha n dt h ee x t e n s i o no ft h ea p p l i c a t i o n ， m a n yn e wp r o b l e m sa n dc h a l l e n g e s ，w h i c hh a v en e v e ra r i s e ni ni pn e t w o r k , h a v e e m e r g e di nt h ef i e l do fo v e r l a yn e t w o r k ，c a u s i n gh i g h e rr e q u i r e m e n t so ft h eo v e r l a y n e t w o r k e x p e r t sn o wb e g i nt op a ya t t e n t i o nt ot h en e wa p p l i c a t i o na n dt h e o r y r e s e a r c hi nt h i sp a r t i c u l a rf i e l d t h i sa r t i c l ei ss u p p o s e dt od ot h er e s e a r c ho nt h en e w d e v e l o p m e n ta n da p p l i c a t i o no ft h eu n s t r u c t u r e do v e r l a yn e t w o r kt o p o l o g ym o d e lw i t h t h er e f e r e n c eo f t h r e eh o t s p o ta p p l i c a t i o n s t h ek e yi s s u e st h i sp a p e rw a n tt od i s c u s si n c l u d e ：a n y - s o u r c eo v e r h ym u l t i c a s ti n t h ea p p l i c a t i o nl a y e rc o m m u n i c a t i o ng r o u pt h a th a st h e c a p a b i l i t yc o n s t r a i n i n g f u n c t i o n ；i m p r o v e m e n to ft h ep e r f o r m a n c eo ft h eo v e r l a ys e a r c ht e c h n o l o g yo fs h a r e d f i l e s ；b a l a n c e dd i s t r i b u t i o no fs e a r c ho v e r h e a da n dr e a s o n a b l eb a l a n c eb e t w e e ns e a r c h o v e r h e a da n dm a i n t e n a n c eo v e r h e a di nw e bt e x ti n f o r m a t i o ns e a r c h , a n de t c t h e r e s e a r c hd e t a i l si n e l u d e ： ( 1 ) d i s c u s st h ea n y s o u r c eo v e r l a ym u l t i c a s tt e c h n i q u ea n dr e l a t e dt e c h n o l o g yo n a p p l i c a t i o nl a y e rb a s e do nt h eo v e r l a yn e t w o r k t h i sp a p e rp u tf o r w a r da n a n y - s o u r c eo v e r l a ym u l t i c a s ts e r v i c es o l u t i o nw i t h o u tt h en e e dt oe s t a b l i s ha v i s i b l em u l t i c a s tt r e e t h i ss o l u t i o ni sb a s e do nt h er a n d o mo v e r l a yn e t w o r k a n dn o n - d h to v e r l a yn e t w o r k t o p o l o g ym o d e lh a v i n g t h en o d e c a p a b i l i t y - c o n s t r a i n e df u n c t i o na sw e l la sl o wm a i n t e n a n c ec o s to fm u l t i c a s t t r e ea n dd y n a m i cm e m b e r m a n a g e m e n ta b i l i t y i nt h i sp a p e rt w od i s t r i b u t e d m u l t i c a s ta l g o r i t h m sa r ed e s i g n e d w eh a v em a d et h e o r e t i ca n a l y s i so n b a l a n c e dp e r f o r m a n c eo fs e a r c hh o p sa n ds e a r c h o v e r h e a d ， o b t a i n e d r e s u l t st h a tt h ee x p e c t e dh o p sw h i c hw i l lt r a n s f e ra n y - s o u r c em u l t i c a s t i n f o r m a t i o nt oa l ln o d e si s o ( i o g cn ) ，t h es e a r c ho v e r h e a di sn + o ( 1 0 9 。，1 ) ， 复日大学博卜学位论文 i nw h i c hei st h ea v e r a g en o d ec a p a b i l i t y , ni st h en u m b e ro ft h en o d e si n t h em u l t i c a s tg r o u p s i m u l a t e de x p e r i m e n ts h o w st h a tn e wa n y s o u r c e m u l t i c a s ta l g o r i t h m sh a v eb e t t e ri n t e g r a t i v ep e r f o r m a n c e ( 2 ) d i s c u s st h ep e r f o r m a n c ep r o b l e mo fs h a r e df i l e s e a r c ht o o li l i o v e r l a y n e t w o r ka n di t sr e l e v a n ts o l u t i o n t h i sp a p e rp a i dm o s ta t t e n t i o no nt h e r e s e a r c ho ft h ei m p r o v e m e n to fs e a r c he f f i c i e n c yw i t h i nt h eu n s t r u c t u r e d o v e r l a yn e t w o r kw h i c hh a sn oc e n t r a l i z e di n d e xs t r u c t u r e t h i sp a p e rf o u n d o u tf o u rp r o b l e m sf r o mk a z a aa n dg n u t e l l at h a ta f f e c tt h ep e r f o r m a n c e ，a n d f u r t h e r m o r eg a v eas o l u t i o nf o re v e r yp r o b l e m t h i sp a p e rb r i n g sf o r w a r da s e a r c ha l g o r i t h mb a s e do nt h et i c k e ti no r d e rt od e c r e a s ee x c e s s i v es e a r c h o v e r h e a d ；t h ep r o p o s e dr a n d o ms a m p l i n gs o l u t i o nr e d u c e st h es e a r c hl a t e n c y c a u s e db yt i m e o u tb e t w e e nc o n s e c u t i v et r l - c o n s t r a i n e df l o o d i n g # a n dt h e r a n d o ma n c h o rs o l u t i o ni su s e dt or e d u c et h er e p e a t e dv i s i tt oas a m en o d e b e s i d e s ，t h i sp a p e r ，b a s e do nt h er a n d o mo v e r l a yn e t w o r ka n dn o n - s t r i c tl o o p ， p u t sf o r w a r da no v e r l a ys e a r c hs e r v i c ed e a l i n gw i t hn o n - p o p u l a rs h a r e df i l e q u e r yr e q u e s t s r e l a t e dt h e o r ya n a l y s i sa n ds i m u l a t e de x p e r i m e n ti nt h i s p a p e rs h o w e dt h e s es o l u t i o n sc o u l dp r e f e r a b l yi m p r o v et h ef i l e s e a r c h p e r f o r m a n c e ( 3 ) d i s c u s st h ew a yt oe f f i c i e n t l yc o m b i n et h ea d v a n t a g e s o fu n s t r u c t u r e d o v e r l a yn e t w o r ka n ds t r u c t u r e do v e r l a yn e t w o r kf o rt h ep u r p o s eo fd e s i g n i n g s e m a n t i cn e t w o r kt o p o l o g yt h a tc o u l dm e e tt h ew e bt e x ti n f o r m a t i o nq u e r y r e q u i r e m e n t t h i sp a p e rc o m b i n e st h ec h a r a c t e r i s t i c so fw e bt e x ti n f o r m a t i o n s t r u c t u r ea n ds e m a n t i cs i m i l a r i t y t o g e t h e rt ob u i l dat e x ti n f o r m a t i o n q u e r y - o r i e n t e ds e m a n t i cn e t w o r kt o p o l o g y b yr e f e r r i n gt ot h ei pr o u t i n g t e c h n i q u e , t h i sp a p e rp u t sf o r w a r dat w o l a y e rq u e r yr o u t i n ga r c h i t e c t u r e t h i sa r c h i t e c t u r ec o n s i s t so fc o r er o u t i n gl a y e ra n dc d g er o u t i n gl a y e r r o u t i n gi n f o r m a t i o ni se n t i r e l yd i s t r i b u t e do nt h en o d e so v e rt h et w ol a y e r s ， a n dt h e r ei sn oc e n t r a li n f r a s t r u c t u r e i tc o u l db cu s e di n l a r g e - s c a l e d i s t r i b u t e ds y s t e mt od e c i d ew h i c hn o d e ss h o u l da c c e p tq u e r y , a n dt h e r e f o r e r e a l i z et h eq u e r yr o u t i n gf u n c t i o ni ns e m a n t i cn e t w o r k m e a n w h i l e ，t h i sp a p e r a d v a n c e dac o n c e p to fp r e f e r e n c e c o m m u n i t y , w h i c hc o u l de f f e c t i v e l y o r g a n i z et h ew e b t e x td a t as o u r c et os i m p l i f yt h eq u e r yr o u t i n gi n f o r m a t i o n ， e a s et h eo r g a n i z a t i o na n dm a i n t e n a n c ea n di m p r o v et h eq u e r yr o u t i n g e f f i c i e n c y a n a l y s i so nt h et i m ec o m p l e x i t yo ft h ea l g o r i t h ms h o w si th a s 复日大学博 学位论文 g o o ds c a l a b i l i t y t h er e s u l to ft h ew e bt e x ti n f o r m a t i o nq u e r yi so b t a i n e dw i t h h i g he f f i c i e n c yu s i n gt h ed i s t r i b u t e dd a t af i l t e ra l g o r i t h m t o p na l g o r i t h m i na d d i t i o n ，r e l e v a n tt e c h n o l o g yc o u l ds h o wi t sa d v a n t a g ei nt h ef i e l do f o v e r h e a db a l a n c e ，i n t e g r a l i t yo fq u e r yr e s u l t sa n de t c k e y w o r d s ：o v e r l a ym u l t i c a s t ；c a p a c i t y ；n o n d h tr i n g ；h o pc o m p l e x i t y ； c o m m u n i c a t i o nc o m p l e x i t y ；d i s t r i b u t e df i l e s h a r i n g ；t i c k e t ；s e a r c h o v e r h e a d ；s e a r c ht i m e ；u n p o p u l a rs h a r e df i l e ；r a n d o mn e i g h b o r s ；w e b t e x ti n f o r m a t i o n ；s e m a n t i cn e t w o r k ；c o r er o u t i n g ；e d g er o u t i n g 第一章绪论 1 1 引言 第一章绪论 自2 0 世纪9 0 年代以来，c s 计算模型及随之而来的b s 、b ，s ，s 计算模型 得到快速发展，但两大制约因素限制了它们的进一步发展：( 1 ) 可扩展性。当 用户数增加，将对服务器端的计算能力、存储空间、带宽等提出越来越大的要 求；( 2 ) 可靠性。网络上所有客户端工作的正常进行均完全取决于处于高负载 状态的服务器能否正常工作。显然，这种计算模型在面对不断增长的用户群时 会面临越来越大的压力。而随之而来的两大新的趋势带来了对等计算( 也称p 2 p 计算) 模型的发展。 首先，新的相关技术与软件工程的结合，形成了一种将工作分散的趋势。 对等计算是这种分散工作趋势的自然结果。随下一代互联网( n g d 的快速发展， i p v 6 技术也得到空前重视，该技术的推广可提供足够的地址空间，消除n a t ， 并且针对q o s 、安全性i p s c c 等提供了一个解决框架，有助于开展新的应用。 诸如分布式游戏、电信会议、虚拟教室、信息检索等经常性的网络应用会得到 更大的发展，并将拥有巨大的用户群体。如何提供更高质量、更实时快捷的信 息服务也变得越来越重要。显然，这给覆盖网技术提供了发展机遇，覆盖网符 合n g i 无所不在的分布优势，并拥有资源优势，有广阔的发展前景。 其次，从工程的角度来看，在企业应用集成等因素的驱动下，过去十年渐 渐形成了一种从集中的单机系统转向分布式系统的趋势。在集中式的应用中进 行控制是相对容易的，这一点在一定程度上抑制了分布式潮流的发展。然而， 随着互联网的发展，以及b 2 b 商务交易方式的日益流行，全面的分布式计算也 就成为一种商业需求。近几年来，对等计算引起了信息产业界的极大关注，主 要原因就是覆盖网有了适合其应用发展的土壤。而对功能强大的网络计算机的 需求以及昂贵的带宽开销是促进其成长的最大动力。事实上，覆盖网在有争议 的音乐共享服务系统n a p s t c r 刺激下得到较快发展。 实际上，互联网上有三大有价值的基础财富：( 1 ) 信息；( 2 ) 计算资源； ( 3 ) 带宽。而所有这些财富并没有得到良好的使用，部分的原因就是源于传统 的c s 计算模型。因为( 1 ) 不可能有单个的搜索引擎或门户能对互联网上不断 增加的w e b 信息进行定位和提供目录服务。况且，大量的信息是短暂存在的， 并不能被w e b 信息找寻过程( 如w e bc r a w l i n g ) 所收集。而且，许多信息也不 第一章绪论 能被找寻出来。实时地发现有用信息变得越来越难。比如，世界每年产生 2 1 0 ”b y t e s 的信息，发布的信息远小于产生的信息。( 2 ) 虽然互联网新增光纤 里程在不断增加，但如果大家都是到y a h o o 、g o o g l e 上获取信息，那么，这些 新带宽就不能充分发挥作用。因为，热点网站在不断升温，而“冷点”网站依 然是“冷”的。这也就是虽然新的带宽不断成倍增加，而多数人仍然感觉互联 网拥挤的原因。( 3 ) 网上新的高速处理器和大容量的存储器不断涌现，但计算 仍然聚集在数据中心，这使得其空间和计算能力上仍然承受巨大的压力。 覆盖网提供了解决这些问题的希望：( 1 ) 建立在其基础上的对等计算结束 了单个资源( 数据源或计算源) 瓶颈；( 2 ) 理论上它可以将数据、控制、负载 均衡分布到整个网络中去；( 3 ) 在覆盖网基础上的系统理论上不会出现网络系 统的单点故障；( 4 ) 覆盖网基础架构允许直接访问和共享空间，而这也使得远 程维护能力成为可能。 由此总结出对等计算模型优势在于：( 1 ) 该模型建立在覆盖网络中结点的 直接连接基础上；( 2 ) 完全不依赖中心基础设施和资源；( 3 ) 该模型可以容忍 网络组成发生的巨大变化；( 4 ) p 2 p 系统成长于一个异构环境之中，有适应异 构系统的能力；( 5 ) 计算模型具有高度的可扩展性。 总之，建立在覆盖网基础上的对等计算取代了集中式互联网数据服务的方 式，使得理论上可以对连接上互联网的每一台计算机上的数据和文件进行访问。 1 2 覆盖网相关基本概念 对等计算的一种定义是“一种充分利用i n t e r n c t 边界资源的应用，这些资源 包括存储、内容等”。可以看出对等计算是研究让网络上应用设备可以向其他设 备提供服务的技术。其核心思想是所有参与系统的结点( 一般指互联网上某个 计算机) 处于完全对等的地位，也可以理解为在覆盖网络中的每一个结点都 同时扮演传统的c s 结构中的服务器和客户端角色，在向其他结点提供服务的 同时，也接受来自其他结点的服务。 一 建立在互联网基础上的覆盖网( 也称p 2 p 网) 也有自己的网络协议，覆盖 网协议主要完成：( 1 ) 寻找到网络上其他的结点；( 2 ) 发现一个结点提供何种 服务：( 3 ) 从一个结点获取状态信息；( 4 ) 触发一个结点的一个服务；( 5 ) 创 建、加入或离开覆盖网：( 6 ) 创建结点问的数据联接；( 7 ) 实施到其他结点的 路由。 理论上，实现对等计算必须完成三项工作：资源存放、资源定位、资源获 取。在p 2 p 系统中，每个人的资源可能放在各自机器e ，也可能各人数据放在 2 第一章绪论 他人机器上，于是如何进行资源存放就成为第一个需要回答的问题。当某用户 需要获得数据时，他首先需要找到数据，当然这与资源存放方法有直接关系。 对于以分布式h a s h 方式存放的数据，可以直接定位。但在多数文件共享系统中， 用户的文件都是放在各自的机器上，那么，特定用户如何知道哪些机器存有他 需要的数据就成为一个关键问题，常常需要较大规模的搜索才可以完成。资源 定位就是研究如何更有效率地找到所需资源所处的位置，尤其是一些覆盖网络 中的“非流行”数据。当找到资源的位置后就需要获取资源，对于有些资源来 说，这并不是很直接的事情，比如获取远程音视频资源。这里的问题主要在于 如何才能更高效地获取资源，或者说，如何让热点资源能够为更多用户服务， 如何让“能力”强的结点发挥更多的网络传输作用等等。通常这就需要尽量发 挥p 2 p 系统中所有参与者的能力，如充分利用所有结点的带宽资源。 本文试图对对等计算进行有价值的研究，但对等计算研究领域相当宽泛， 本文希望能对一些重点问题进行探讨，如上所述，对等计算的研究从根本上是 要解决资源存放、资源定位、资源获取等问题，所以，本文针对这三个问题， 结合热点应用，做了相关研究工作：在资源存放问题上，结合共享文件搜索这 个近年最突出的应用方向进行探讨，研究语义覆盖网的构造及覆盖网查询路由 协议；在资源定位方面，通过介绍现在最有代表性的p 2 p 系统k a 7 _ c a 的工作机 制，研究其存在的问题，并尝试提出改进方案；针对资源获取问题，结合当前 应用层覆盖多播这个热点，探讨结点如何有效获取多播资源。需要说明的是， 由于以上所结合应用的一些现实特点，本文将重点在非结构化覆盖网基础上展 开讨论。可以设想，有效的覆盖网拓扑结构研究仍然会是本文工作的基础。 1 3 覆盖网应用的几个问题 随着对等计算研究工作的不断深入，覆盖网应用的一些问题逐渐暴露出来， 其中一些已成为该研究领域进一步发展的障碍。不过，这些问题也昭示了我们 进一步工作的方向。本文将针对以下几个主要问题做探讨： ( 1 )多播组组通信问题。多播是一个重要研究方向。从i p 多播转向 应用层多播是国际上近年来的一个热点工作。但应用层多播遇到 几个需要重点考虑的关键因素，如，如何在多播过程中考虑结点 能力约束因素、如何对多播树实施优化、如何对组通信中动态成 员进行管理、如何实施避免单点故障的完全分布式服务、如何从 理论和实验角度分析并解决多播信息传输路径长度和通信流量 之间的均衡关系等等。虽然现在存在一些较成功的度约束最小延 3 第一章绪论 ( 2 ) ( 3 ) 迟多播树等，但并不适合于应用面很广的任意源多播应用，目前 尚没有同时兼顾以上几个关键因素的多播方案。 共享文件搜索技术性能问题。覆盖网大量现实应用中，共享文件 搜索是主流应用之一，由于非结构化覆盖网络没有固定的索引存 储结构，其网络维护量小。目前实际使用的主流搜索技术大多建 立在非结构化覆盖网络基础上，其文件定位由洪泛算法及相关变 种算法完成。而洪泛算法本身存在严重的可扩展性问题。典型的 k a z a a 虽然使用了超级结点及t r l 约束洪泛吼c o n s t r a i n e d f l o o d i n g ) 等技术，网络流量仍然很高，覆盖网络流量甚至已成为 超过w e b 流量的主导性网络流量。显然，为了维护互联网正常 运作，进一步改善非结构覆盖网络文件搜索性能以支持今后覆盖 网应用发展变得非常重要了。 适应信息查询请求的语义网拓扑构造问题。p 2 p 系统已经证明是 共享文件的有效方法，有很多协议可用于将一个信息路由到一个 指定的覆盖网结点。但无论基于结构化覆盖网还是非结构化覆盖 网，相关路由策略均存在严重问题。结构化覆盖网的路由策略强 调搜索负载的降低，但覆盖网维护负载很大，且查询路由过程中 存在严重的因大量查询请求导致的局部负荷失衡问题。而非结构 化覆盖网情况则正好相反，其覆盖网维护负载小，但路由过程搜 索负载大。显然，改善覆盖网的查询路由问题是一件有价值的事 情。另外，建立在语义、结构等信息基础上的语义拓扑模型的建 立对共享文件的有效搜索同样至关重要，它将有助于建立在查询 与覆盖网结点目录内容之间的语义相似基础上的路由策略，以尽 可能只使能提供结果的覆盖网结点参与计算。 1 4 本文的工作 针对以上几个问题，我们做了研究工作： ( 1 ) 建立高效的任意源多播机制。主要成果如下： 建立隐式多播树； 任意源多播算法l ； 任意源多播算法2 。 ( 2 )改善共享文件主流搜索工具性能。主要成果如下： 针对过量搜索负载问题，提出基于票据的搜索解决方法； 4 第一章绪论 针对搜索延时问题，提出随机采样解决方法； 针对重复搜索问题，提出随机锚点解决方法； 针对非流行共享文件搜索问题，提出覆盖广播搜索算法。 ( 3 ) 加快查询路由效率，降低覆盖网维护负载。主要成果如下： 建立基于特征项的语义相似兴趣圈； 建立包含核心路由层和边界路由层的2 层路由结构体系。 本文第二章将提出一个任意源覆盖多播服务方案，讨论在覆盖网基础上进 行应用层任意源覆盖多播的方法和相关技术。由于针对每个源建立一个树代价 高昂，近年提出的许多面向单个数据源设计的多播树并不能简单扩展到任意源 多播系统中。而已存在的一些允许多数据源的多播系统的维护量大，在体现结 点能力差异等方面缺少灵活性。本文提出一个任意源覆盖多播服务方案，无须 建立显式的多播树。该方案建立在随机覆盖网和非d h t 覆盖网拓扑模型基础 上，具有结点能力约束性能，同时，多播树维护量小，具有动态成员管理能力。 本文中设计了2 个分布式多播算法。我们对搜索跳数和搜索负载进行了均衡性 能的理论分析，得出的结论是：算法将任意源的多播信息传送到所有结点的期 望跳数是o ( 1 0 9 。n ) ，搜索负载为拜+ o ( 1 0 9 。玎) ，其中，c 是平均结点能力，n 是多 播组中的结点个数。模拟实验显示新的任意源多播算法拥有较好的综合性能。 第三章重点研究了在没有集中索引结构的非结构化覆盖网网络中如何改进 共享文件搜索效率，讨论覆盖网共享文件主流搜索工具性能问题及相应解决方 法。现有的文件搜索工具主要建立在非结构化覆盖网基础上。虽然非结构化覆 盖网络由于其较小的维护负载而在实际应用中占主导地位，但是，其过量的搜 索流量将制约其进一步发展。本文重点研究了在没有集中索引结构的非结构化 覆盖网络中如何改进搜索效率。文章找出k a z a a 及g n u t e l l a 中影响性能的四个 问题，并由此针对每个问题提出了解决方法。文章提出一个基于票据的搜索算法 以减少过量的搜索负载；提出的随机采样方法，减少了连续2 轮搜索间由超时 时限造成的搜索延时问题；而随机锚点方法被用于减少对同一结点的重复访问。 另外，本文在随机覆盖网和非严格环基础上，提出了一种面向非流行性共享文 件查询请求的覆盖广播搜索服务。文章的相关理论分析及模拟实验显示这些方 法较好地提高了文件搜索性能。 第四章研究面向w e b 文本信息查询的语义网构造及查询路由优化问题，讨 论如何有效地结合非结构化覆盖网与结构化覆盖网二者优势来设计满足w e b 文 本信息查询请求的语义网拓扑。本文结合w e b 文本信息结构特征和语义相似性 特征，构造面向文本信息查询的语义网拓扑。借鉴口路由的思路，提出一个两 层结构的查询路南框架，该椎架f h 核心路南层和边界路由层组成，路南信息完 第一章绪论 全分布于两层结点上，不存在中央控制结构，可用于在大型分布式系统中来决 定那些结点应接受查询，实现在语义网络中的查询路由功能。同时，本文提出 了兴趣圈的概念，有效地对w e b 文本数据源进行组织，使查询路由信息简单、 易于组织和维护，提高了查询路由的效率。对算法的时间复杂性分析表明其有 良好的可扩展性。w e b 文本信息查询结果最后采用分布式环境数据过滤算法 t o p n 算法来高效获取。另外，相关技术可以在负载均衡、查询结果的完整性 等方面体现出优势。 实际上，我们的研究成果并不仅仅只限于以上经常提及的应用，也可以为 其他基于p 2 p 的应用所借鉴 上述各章均以引言和目前研究现状的综述开始，并以该章小结作为结尾。 本文第五章将简单概括本文的工作，并给出该领域可以进一步开展工作的前景。 最后，本文附录部分对本人在攻读博士学位期间参与的科研项目情况、论 文发表情况进行了总结。 6 第二章应用层任意源覆盖多播机制及算法 第二章应用层任意源覆盖多播机制及算法 2 1 引言 多播( m u l t i c a s t ) 又称组播，是指从发送方将同一个数据包一次传输给 厅o ，d 个接收者集合的通信方式。目前，在互联网上的多播协议可分为基于网 络层( 或称m 层) 的多播和基于应用层的多播。基干网络层的多播协议的多播功 能实现是在传统的口层添加必要的多播机制，如扩展网络层中主机的现有分组 收发功能，支持收发多目标分组；扩展网络层中路由器的现有分组转发功能，添 加群组通信路由算法，支持多目标分组的转发。基干网络层的多播需要增加路由 器的处理负载和网络层协议设计的复杂性，并且目前并不是所有的i s p 服务商的 路由器都支持多播功能对于多播传输的的服务质量( q o s ) 问题，虽然目前已 有一些多播可靠性传输协议( 如s r m 和r m t p ) 和拥塞控制协议( 如m t c p 和 p g m c c ) ，但是在i n t e m e t 环境中多播传输的服务质量仍然得不到较好的保证。 因此，近年来，多播的研究开始重新评估网络层是否是最佳的多播功能的实现层， 并且提出了基于应用层来实现多播的思想。 2 1 1 应用层多播的定义 应用层多播( a p p l i c a t i o nl a y e rm u l f i c a s t ) 是指多播功能是实现在终端主机 的应用层而不是网络层路由器上。这主要体现在以下两个方面： ( 1 )对同一个数据包向多个接收者的发送是由应用层根据某种应用层的多 播路由协议，利用网络的u d p 或t c p 协议提供的单播服务分别单播 给多个接收者。 ( 2 ) 在应用层实现多播组的创建、组成员的加入和退出及安全认证等所 有关于多播组的管理与维护功能。 这虽然是将网络层协议的复杂性和处理负载转移到了应用层，并且不可避免 地造成数据包的传输效率要低于基干网络层的多播。但是这一思想具有更好的伸 缩性和对下层网络服务的无关性，它能够在任何仅支持理数据包转发的网络上 实现各种不同服务质量，如可靠不可靠和实时非实时的多播传输，而不用要 扩展任何现有底层网络的通信协议同时这也更加符合c l a r k 等提出的a l f ( a p p l i c a t i o nl a y e rf r a m i n g i n g ，应用层组帧) 的现代网络通信协议设计原则 【d l 9 0 】。 7 第二章应川层任意源覆盖多插机制及算法 2 1 2 应用层多播的策略 为了提高多播数据包的高效率传输和多播组成员的管理，应用层多播协议都 将多播成员按照某种逻辑拓扑组织以进行数据的多播传输。为识别和控制多播组 成员的动态改变，在每个多播组成员之间要维持一张多播组成员信息表。 由于应用层多播不像网络层多播那样在网络层( 路由器) 上实现数据包的 复制，而是在应用层主机上完成复制，这就不可避免会在同一条链路上形成多个 同样的数据包的传输的现象，这会造成较大的传输负载，另外，多播数据包转发 在应用层也会形成比网络层多播更高的传输延迟。因此，应用层多播的关键是如 何构建和维护一个高效的应用层数据传输拓扑。在多播的过程中，针对网络服务 状态的变化，如带宽、延迟抖动；多播组成员状态的改变，如成员的正常或异常 退出、新成员的加入等情况，应用层多播应自适应地对多播数据的传输拓扑和路 由做出相应的改变以保证多播传输的正常和高效性。总的说来，应用层的多播协 议要求具有以下特点： ( 1 ) 自组织性：多播所基于的逻辑拓扑结构的构建应该是分布式的自组织 方式。参与多播的成员可能分布在极广的地理位置范围内。地理位置相 近( 如处于同一个局域网中) 的成员应能先自组织成一个逻辑子拓扑结 构来联入整个多播逻辑拓扑中。 ( 2 ) 自适应性；多播所基于的数据逻辑拓扑在构建后要能自适应地根据网络 服务状态和多播组成员变化做出改变和优化，以便可选择更佳的多播传 输路径。 ( 3 ) 高效性：多播构建的数据传输拓扑结构必须尽量使得在同一条逻辑传输 路径上的冗余数据传输( 同一数据包的多份传输) 最低。但针对不同的 应用要求，多播的高效性也具有不同的侧重含义。如对于视频会议的应 用，多播的有效性是指传输的实时性，而对于白板的应用则既要求实时 性也要求传输的可靠性。 2 1 3 应用层多播协议 根据构建应用层多播的数据传输逻辑拓扑和控制逻辑拓扑的先后顺序，我们 可以将目前的应用层多播协议划分为网优先( m e s h f i r s t ) 多播、树优先( t r e e f i r s t ) 多播和隐含多播三类 s b 0 2 。 网优先多播协议中，多播组成员首先分布式地自组织形成一个网状型的控制 8 4 嬲 勿 第二章应用层任意源覆盖多插机制及算法 拓扑，在某一对多播组成员之间可能存在多条的连接路径。基于这个网型的拓扑， 每一个多播组成员根据某种路由协议分布式地计算出自己到每一个其它多播组 成员的数据传输路径。然后可借助许多网络层多播协议如d v m r p 使用的转发逆 向路径( r e v e r s ep a t hf o r w a r d i n g ) 算法可构造出基于任一多播组成员为树根的 树型多播传输拓扑。n a r a d a y g 0 0 是属于该类型的一种应用层多播协议，也是最 早提出的应用层多播协议之一。 相反地在树优先多播协议中，首先构建的是一个所有多播组成员共享的树型 多播数据传输拓扑。接着，每个多播组成员寻找发现那些树型拓扑中与其不相邻 的多播组成员，并分别建立连接路径到这些成员，这样在树型拓扑基础上再加入 这些新添的连接路径构成网型的控制拓扑。目前的y o i d y 9 9 1 和h m t p b s l 0 2 】 都是属于这类应用层的多播协议。 隐含多播协议里，控制拓扑是由协议使用一定的算法将多播组成员事先组织 成某种逻辑结构。基于这个逻辑结构，分别按照某种数据的转发算法来定义形成 协议的数据传输拓扑。这样控制拓扑和数据传输拓扑都是在协议事先基于的逻辑 结构中被定义，而不需要像前面提到的两类多播协议一样，基于其中之一构建形 成另一者。并且协议只需维护多播组成员事先组织成的逻辑结构，不需要去直接 维护协议的控制拓扑与数据传输拓扑。这类应用层多播协议由于不需要在多播组 成员之间进行频繁的状态信息的通信交互，从而避免了除数据传输之