（计算机应用技术专业论文）p2p网络关键技术研究与应用.pdf

哈尔滨工程大学硕+ 学位论文 摘要 随着互联网的普及和发展，网络已经与人们的生活息息相关。由于接入到 互联网的人数激增，给传统的客户机服务器模式的网络带来了很多新的挑战。 近年来p e e r t o p e e r ( 简称p 2 p ) 技术迅速发展，成为产业界和学术界普遍关 注的话题之一。然而，p 2 p 技术刚刚起步，迄今为止，尚没有统一的标准可循， 还处在逐步的开发与优化阶段。p 2 p 技术取消了中心服务器，所有参与的节点 地位都是同等的，自动构成一个自组织系统。因此，p 2 p 系统的最大挑战就是 在没有中心服务器的情况下，如何查找和定位数据项。在这方面的研究中，已 经有了几种优秀的算法，但都存在着种种不足。 本文针对现有的p 2 p 查找和数据定位算法c h o r d 的缺点，提出一种新的 c h o r d 模型。把原来一个虚拟的c h o r d 环形网络分为i n t e rc h o r d 和i n t r a c h o r d 两部分，节点通过广播的方式选择是加入到i n t r ac h o r d 中还是加入到 i n t e rc h o r d 中，最终把物理邻近的节点组织在一个i n t r ac h o r d 中来提高系 统的查询速度。i n t r ac h o r d 中的节点只需知道其直接前驱节点、直接后继节 点和l e a d e r 节点，而且i n t r ac h o r d 中节点的加入与退出并不影响整个系统， 因此也提高了系统的稳定性。最后，本文通过m i t 推出的开源仿真工具p 2 p s i m 对该c h o r d 模型的算法进行了验证，结果表明新的c h o r d 模型不仅克服了原有 c h o r d 模型的缺点，还保留了原c h o r d 模型的优点，从而优化了c h o r d 模型的 整体性能。 另外，本文还研究了p 2 p 开源技术j x t a 的路由算法。应用j x t a 可以开发 一系列p 2 p 应用系统，但由于j x t a 技术的路由算法采用广播方式，使网络流 量急剧增加，造成极大的信息冗余，且查询存在不确定性，因此使用j x t a 开 发出的应用程序稳定性、可靠性都不高。本文提出的新c h o r d 模型减少了网络 中的信息冗余，查询也可以在有限的时间内完成，并与j x t a 的路由模型有极 大的相似性。因此可以把本文提出的新c h o r d 模型的路由算法应用到j x t a 中 来提高j x t a 的路由效率。在本文的最后还应用j ) ( t a 设计了一个即时通信系统。 关键词：对等网络；i n t e rc h o r d ：i n t r ac h o r d ；路由算法；广播；j x t a 哈尔滨t 程大学硕十学位论文 a b s t r a c t w i t ht h ep o p u l a r i z a t i o na n dd e v e l o p m e n to ft h ei n t e r a c t ，t h ei n t e r a c th a sb e e n c l o s e l yr e l a t e dt op e o p l e sl i v e s a s t h en u m b e ro fp e o p l ea c c e s s i n gt ot h ei n t e r a c t g r e wr a p i d l y ，i tb r o u g h tm a n yn e wc h a l l e n g e s t ot h et r a d i t i o n a lc l i e n t s e r v e r n e t w o r km o d e l i no r d e rt oa d a p tt ot h i sc h a n g i n gi ni n t e m e ta n db e t t e rs a t i s f yt h e i n c r e a s i n gd e m a n d ，p e e r - t o p e e r ( r e f e r r e da sp 2 p ) t e c h n o l o g yh a sb e e nr a p i d l y d e v e l o p e da n dh a sd r a w nm u c ha t t e n t i o na so n eo ft h em o s tp o p u l a rt o p i c s i n i n d u s t r ya n dr e s e a r c hc o m m u n i t yi nr e c e n ty e a r s h o w e v e r ，p 2 pt e c h n o l o g yh a sj u s t b e g u n ，s of a r ，t h e r ei sn ou n i f o r ms t a n d a r dt of o l l o w ，i ti s i nt h ed e v e l o p i n ga n d o p t i m i z i n gs t a g e p 2 pt e c h n o l o g yc a n c e l e dt h ea r c h i t e c t u r eo fc e n t r a l s e r v e ra n da l l n o d e sw h i c hh a v et h es a m es t a t u sc o n s t i t u t eas e l f - o r g a n i z i n gs y s t e ma u t o m a t i c a l l y t h e r e f o r e ，t h eb i g g e s tc h a l l e n g ei np 2 ps y s t e mi sh o wt of i n da n dl o c a t et h ed a t a u n d e rt h ec o n d i t i o no ft h ea b s e n c eo fc e n t r a l - s e r v e r i nt h i sr e s e a r c ha r e a t h e r eh a v e b e e ns e v e r a le x c e l l e n t a l g o r i t h m s ，b u ta t t h es a m et i m e ，t h e r ea l s oh a v es o m e p r o b l e m s i nt h i sd i s s e r t a t i o n ，t os o l v et h es h o r t c o m i n g so ft h ec h o r dw h i c hi sw i d e l yu s e d i np 2 ps y s t e m s ，f ln e wm o d e lo fc h o r di sp r o v i d e di nw h i c ht h eo r i g i n a lc h o r d r i n g i sd i v i d e di n t ot w op a r t s ，i n t e rc h o r da n di n t r ac h o r d e a c hn o d ed e c i d e sw h i c hr i n g t oj o i nb yb r o a d c a s t , t h ei n t r ac h o r do rt h ei n t e rc h o r d , t h ep h y s i c a l l ya d j a c e n t n o d e sa r eo r g a n i z e di no n ei n t r ac h o r dt oe n h a n c et h es y s t e m ss p e e do fq u e r y i n t h e i n t r ac h o r d , e a c hn o d eo n l yn e e d st ok n o wi t sd i r e c tp r e d e c e s s o ra n dd i r e c t s u c c e s s o ra n dl e a d e rn o d e ，a n dn o d e s j o i n i n gi no ro u to ft h ei n t r ac h o r dw i l ln o t a f f e c tt h ew h o l es y s t e m i ta l s oc a ni n c r e a s et h es t a b i l i t yo ft h es y s t e m t h en e w a l g o r i t h mo fc h o r di s v e r i f i e dt h r o u g hm i t so p e ns o u r c es i m u l a t i o nt o o lc a l l e d p 2 p s i n a t h e e x p e r i m e n t a l r e s u l t ss h o wt h a tt h en e wc h o r dm o d e ln o to n l y o v e r c o m et h es h o r t c o m i n g so ft h eo r i g i n a lc h o r dm o d e l ，b u ta l s or e t a i n st h eo r i g i n a l m o d e lc h o r d sm e r i t s ，t h u so p t i m i z et h eo v e r a l lp e r f o r m a n c e 哈尔滨工程大学硕十学位论文 i na d d i t i o n , t h eo p e n - s o u r c ep 2 pt e c h n o l o g yj x t a sr o u t i n ga l g o r i t h mi sa l s o r e s e a r c h e di nt h i sd i s s a t a t i o n t at e c h n o l o g yc a i lb ea p p l i e dt od e v e l o pas e r i e so f p 2 pa p p l i c a t i o n s b u ti t s s t a b i l i t ya n dr e l i a b i l i t ya r el o wb e c a u s e t au s e s b r o a d c a s t i n gi ni t sr o u t i n ga l g o r i t h mw h i c hm a y c a u s eag r e a td e a lo fi n f o r m a t i o n r e d u n d a n c y ，t h es h a r pi n c r e a s i n gi nn e t w o r kt r a f f i c ，u n c e r t a i n t yo ft h eq u e r y t h e n e wm o d e lo ft h ec h o r da l g o r i t h mc a ng r e a t l yr e d u c et h en e t w o r ko fr e d u n d a n t i n f o r m a t i o na n dd e a lw i t hq u e r i e si nl i m i t e dt i m e s ，a n dh a v eg r e a ts i m i l a r i t yw i t h t a r o u t i n gm o d e l s oi tc a l lp u tt h en e w m o d e lo ft h ec h o r d r o u t i n ga l g o r i t h mt o t h e 1 ar o u t i n ga l g o r i t h mt oi m p r o v et h ee f f i c i e n c y f i n a l y ，w i mj x t a ，a r e a l - t i m ec o m m u n i c a t i o ns y s t e mi sd e s i g n e d k e yw o r d s ：p 2 p ；i n t e rc h o r d ；i n t r ac h o r d ；r o u t e ra l g o r i t h m ；b r o a d c a s t ；j x t a 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由作 者本人独立完成的。有关观点、方法、数据和文献的引用已在文中 指出，并与参考文献相对应。除文中已注明引用的内容外，本论文 不包含任何其他个人或集体已经公开发表的作品成果。对本文的研 究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 作者( 签字) ：骅茭铲1 1 日期：讪o1 年乡月6 日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可口在授予学位1 2 个月后 口 解密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：那戋彦p 日期：卅年弓月，占日 导师( 签字) ：幽静冬民 卅年；月t , 日 哈尔滨工程大学硕士学位论文 1 1 研究背景 第1 章绪论 1 9 9 9 年用于音乐和文件共享的应用软件n a p s t e r n l 的推出掀起了p 2 p 的热 潮。用户使用这款软件不仅可以下载内容，还可以把自己硬盘上的内容通过 i n t e r n e t 提供给其它用户下载，这就是第一代p 2 p 网络。这种技术的核心思想 是所有参与的节点在地位上是平等的，没有客户机与服务器之分，每个节点既 是客户机又是服务器，即向别人提供服务也享受来自别人的服务。这种模式使 互联网中的资源被广泛发掘和利用，已经在各个领域里得到了应用。但由于 n a p s t e r 网络中存在大量的非法共享内容，被美国唱片协会告上法庭，最后不 得不被迫关闭。但它开创了应用p 2 p 技术的先河，从此之后，各种p 2 p 软件逐 渐浮出水面，如g n u t e l l a 心3 、f r e e n e t m l 、b i t t o r r e n t 、k a z a a 。等。现在，p 2 p 应用已经超过w e b 应用，成为占用互联网带宽最多的网络应用，其代表系统 k a z a a 的同时在线用户已经超过3 0 0 万，其发展趋势愈演越烈，成为人们持续 关注的焦点。 由于p 2 p 技术应用的迅速发展，学术界也展开了对p 2 p 系统的设计方法和 发展方向的深入研究。p 2 p 技术从拓扑结构上大致可以分为两类：一类是节点 之间完全没有任何组织规则、完全随机的连接在一起的结构，称为非结构化网 络，起初的p 2 p 应用系统的开发都是基于此结构的。如g n u t e l l a ，它是以洪泛 ( f l o o d i n g ) 的方式对资源进行定位，所谓洪泛是指查询消息像洪水一样传遍网 络中的每个节点，产生了大量的冗余信息，严重浪费了系统的资源，使系统的 性能非常低，严重时还可能导致网络瘫痪；因此另一类结构化的p 2 p 网络模型 应运而生。在该模型中，节点之间按照某种规则，在实际的物理网络之上组织 成一个虚拟的逻辑覆盖网，所有的查询操作都是在逻辑覆盖网中进行的，因此 便产生了一系列基于d h t ( d i s t r i b u t eh a s ht a b l e ) 的结构化p 2 p 路由算法，比 较典型的有加州大学伯克利分校的c a n 聆3 和t a p e s t r y 拍3 项目，麻省理工学院的 c h o r d 盯3 项目，以及微软研究院的p a s t r y 啤1 项目。其中，m i t 的c h o r d 算法是一 种比较成功的算法。但由于现在p 2 p 的发展水平有限，难免存在一些弊端，如 哈尔滨t 程大学硕十学位论文 没有考虑底层的拓扑结构等。本文通过对该算法深入的分析和研究提出了一种 新的c h o r d 模型来克服其缺点，保留其优点，进一步提高其性能。 1 2 国内外研究现状 对p 2 p 网络的研究一般分为两个层次：一是企业界对p 2 p 的研究，主要为 利用p 2 p 网络的无中心化和高带宽的特性，开发出高性能的应用程序。第一代 p 2 p 应用程序n a p s t e r 是中心化结构的，依赖于一个中心化查找服务器，保存 资源的存储位置。它的覆盖网络被组织成一个星形结构，每个对等端向服务器 发出查询请求，当服务器把查询结果返回给查询节点后，查询节点和资源所在 节点直接连接进行资源的传输，但最后n a p s t e r 还是以失败收场。由于n a p s t e r 过于依赖中心服务器，以完全随机图组织的p 2 p 应用程序g n u t e ll a 开始了纯 粹的p 2 p 系统时代。它取消了中心服务器，覆盖网络以任意的形式组织，由于 g n u t e l l a 采用基于完全随机图的洪泛( f l o o d i n g ) 发现和随机转发( r a n d o m w a l k e r ) 机制，其准确性和可扩展性很低，在网络中产生了大量的冗余信息， 严重的浪费了带宽。因此以k a z a a 为代表的第二代p 2 p 应用系统开始占据主导 地位，它结合了中心化p 2 p 结构系统的优点，选择性能较高( 带宽、存储等) 的 节点作为超节点，在各个超节点上存储了系统中其它部分节点的信息，查询消 息在超节点之间转发，超节点再将查询请求转发给适当的叶子节点。在国内， 对p 2 p 技术的研究还处于发展阶段。国内有几个著名的p 2 p 研究项目，分别是 北京大学的m a z e 系统、清华大学的g r a n a r y 系统、华中科技大学的a n y s e e 系 统、中科院的w o n g o op 2 p 技术平台和上海交通大学的p 2 p 片段存储系统。 p 2 p 领域研究的另一个层面是研究界对p 2 p 路由算法的研究。p 2 p 技术的 关键在于高效的查询和定位数据项。目前这方面的研究都集中在结构化的路由 算法上，在国外已经设计出很多优秀的算法，如：c a n 、t a p e s t r y 、c h o r d 、 p a s t r y 、k a d e m l i a 阻 、k o o r d e 【1 0 、v i c e r y 3 等，主要解决节点的逻辑位置与物 理位置不匹配的问题；在减少系统消耗的基础上提高查询效率；提高系统的稳 定性等问题。如z h a n g 等人针对c h o r d 算法提出的l p r s ( 1 0 0 k u p p a r a s i t i c r a n d o ms a m p l i n g ) n 2 1 算法在很大程度上提高了c h o r d 的查询效率，使节点的逻 辑位置与物理位置更接近。s h a n s ir e n 等人针对c a n 算法提出的“围栏式 2 哈尔滨 二程大学硕十学何论文 算法解决了节点逻辑位置与物理位置不匹配问题，并取得了一定的效果。相对 于国内来说，这方面的研究还处于发展阶段。南京大学的陈贵海教授等开发了 一种新的常数度数算法c y c l o id n 3 h 1 4 3 ，模拟立方体互连圈的拓扑结构。该算法 适合网络规模较大、动态性较高的网络，具有较高的平均查找效率、负载平衡、 健壮性等特点。 1 3p 2 p 的应用领域 现阶段，已经研究出并使用非常广泛的p 2 p 应用软件主要集中在文件共享 领域，如文件下载软件迅雷、b i t t o r r e n t 、e m u l e 等。但p 2 p 技术除了在文件 共享领域有较多的应用外，在其它的领域也有很好的应用前景，如即时通讯。 典型的即时通讯系统有i c q 、o i c q 、a i m 、m s n 、s k y p e 和j a b b e r 等；在协作方 面，最著名的是g r o o v e 虚拟办公室( g r o o v ev it u a lo f f ic e ) n 酗，这个系统提供 的功能( 即时消息、文件共享、通知、同时浏览、白板、语音会议和具有实时 同步能力的数据库) 类似于广泛使用客户端服务器的应用，如q u i c k p l a c e 和 s a m e t i m e 等。但g r o o v e 不需要有中心服务器的管理，创建的所有数据存储在 每个对等端上，并自动的同步；在分布式存储网络方面也有很多应用程序正在 发挥着巨大的作用，如o c e a n s t o r e n 6 1 是一个基于p 2 p 的全球范围的海量存储 系统，用户可以在任何时候，任何地点，通过任何设备接入i n t e r n e t 访问存 储在o c e a n s t o r e 中的数据。这方面的应用系统还有p a s t n7 1 、c f s 口8 | 、f a r s i t e n 钔 等。在数据管理方面，采用p 2 p 技术构建新型的分布式数据管理系统是当前p 2 p 技术的一个重要应用。p 2 p 数据管理系统是传统数据库及w e b 数据库技术与p 2 p 技术相融合的产物。p 2 p 系统中的每个结点维护数据库中的部分数据记录，数 据查询时需要将关系查询请求分解，转发到p 2 p 系统中相关的多个结点上。典 型的系统包括l r m 、p i e r 和p i a z z a 等。另外，p 2 p 技术在信息扩散、知识管 理、组织机构间信息知识库构建、视频会议、移动自组织网络中对数据的离 线访问等方面也都有广泛的应用。 而在未来的几年里，p 2 p 技术还将在其它方面的应用有所突破，例如p 2 p 计算与分布式计算g r i d 的融合问题，这两方面有许多共性也有许多差异。g r i d 计算的思想起源于科学团体，并由处理资源和存储密集的应用最早驱动啪3 ，g r i d 哈尔滨t 程大学硕十学位论文 计算的主要目标是提供对普遍的、非常巨大的不同资源池的访问，它们支持创 新应用并将其利用心。一个g r i d 系统要满足如下条件蚴： ( 1 ) 协调不受控于中心化控制的资源； ( 2 ) 使用标准的、开放的通用协议和接口； ( 3 ) 分发非平凡的服务质量； 这几点也特别适用于许多p 2 p 系统，甚至在一个系统层中，p 2 p 和g r i d 之 间的差别不是清晰划分的。两者都关注于分布式资源的共享和组织，资源通过 i n t e r n e t 连接到虚拟团体进行共享。他们提供的资源和服务可位于系统中的任 何地方，且对用户是透明可用的。两者在底层通讯上也采用一种类似的结构化 重叠网络。但它们在应用功能和结构层还是有本质上的差异：g r i d 支持的应用 主要是科学的应用，它们用于专业化的、规模适中的且参与机构通常是已知的 场景中。而p 2 p 的应用是面向大量的、参与节点是不可预知的开放性访问，所 以p 2 p 必须处理扩展性和故障问题，这些问题要比g r i d 应用中出现多很多。 因此，研究者们正在向p 2 p 与g r i d 的融合方向努力，即由p 2 p 架构所表现的 大规模分布式系统提供更具灵活性、动态性、鲁棒性、可信赖性和扩展性的服 务。如果这是成功的，且附加的服务特性( 如性能和效率) 能够确保，则p 2 p 机 制能够成为g r i d 的核心部分。另一方面，p 2 p 应用将必须采用一种更加基于平 台的开发思路以在非常动态的环境中提供足够的灵活性。 把p 2 p 组织结构原则应用到普适计算中也是另一个研究方向。在p 2 p 原则 中，对等端自治地活动，但与其它对等端协议交互以提供服务。以一种类似的 风格，普适计算设备自治的活动，但在其活动中相互依赖。普适计算的主要焦 点在于有效的通信架构，这允许不同设备将其服务提供给环境中的其它实体， 这样的通信架构展示出了许多类似p 2 p 的属性。因此，把p 2 p 作为中间件应用 在普适计算中是解决普适计算通信问题的一种令人关注的可能方法。p 2 p 网络 和系统的自组织性、资源共享和设备独立性可以很好的匹配于普适应用的典型 特征，因为在普适计算架构中，存在许多完全自治的设备( 例如传感器、用户 设备等) 散布于环境中，这些设备中的每个设备对其它设备都有某种重要功能， 即每台设备为所有其它设备、服务和应用提供一些资源等。这正与p 2 p 的设计 原则相似口引。 4 哈尔滨工程大学硕士学位论文 1 4 本文的研究内容和组织安排 本文在深入分析和研究c h o r d 算法的基础上，针对c h o r d 查询延时大的缺 点提出了一种新的c h o r d 模型。把c h o r d 环分为两种，一种保留原c h o r d 环的 特性称之为i n t e rc h o r d ；另一种是物理邻近的节点组成的附属于i n t e rc h o r d 中的一个节点，称为i n t r ac h o r d 。节点通过广播的方式探测与其它节点的r t t ( r o u n dt r i pt i m e ) 值，通过比较与各个节点之间的r t t 值来判断是加入到i n t r a c h o r d 中还是加入到i n t e rc h o r d 中。通过此种方式，有些查询在i n t r ac h o r d 中就可以完成而不必查找i n t e rc h o r d ，从而减少了查询时间，提高了系统的 稳定性，同时也使逻辑覆盖网络与物理网络尽可能的匹配。 本文组织结构如下： 第一章绪论介绍课题的研究背景、国内外研究现状和p 2 p 现在及未来 几年的应用领域。 第二章p 2 p 资源定位技术详细介绍了p 2 p 的资源定位技术，p 2 p 系统的 关键在于资源定位。在这一章中，分别针对非结构化网络和结构化网络两大类 介绍了一些主流的资源定位技术。 第三章基于d h t 的c h o r d 算法详细论述及改进在深入的分析和研究 c h o r d 算法的基础上，针对c h o r d 查询延时大的缺点提出一种新的c h o r d 模型 来提高其性能。 第四章仿真与分析通过开源仿真软件p 2 p s i m 对新模型的算法进行仿 真验证。 第五章改进模型算法应用的设计由于j x t a 路由算法的低效性，根据新 c h o r d 模型与j x t a 路由模型的相似性，把本文提出的新c h o r d 模型的路由算法 应用到j ) ( t a 的路由算法中来提高j x t a 的路由效率。最后应用j x t a 开发了一 个即时通信系统。 哈尔滨工程大学硕士学位论文 第2 章p 2 p 资源定位技术 由于p 2 p 系统没有中, d n 务器管理数据，所有的数据都分布在对等端上， 在这个非中心化自组织系统中取得高水平的服务质量，关键的问题在于如何高 效的查找、定位数据项，并管理它们。p 2 p 网络主要以节点的无结构化和节点 的结构化组织来解决这个问题。下面将从非结构化资源定位技术和结构化资源 定位技术两个方面介绍p 2 p 的资源定位技术。 2 1 非结构化资源定位技术 所谓非结构化就是节点之间没有任何的组织规则，完全随机的散布在网络 中。第一代p 2 p 系统n a p s t e r 的资源定位是利用一个中心目录服务器来存储所 有数据项的位置，节点通过中心目录服务器查找到存储该数据项的对等端之 后，数据才在两个对等端之间进行直接传输。但中心服务器极易成为系统的单 点故障和性能瓶颈，为了克服这个缺点，便产生了一种泛洪技术，下面将详细 介绍泛洪算法以及在它基础上的一些改进算法。 2 1 1fio o din g ( 泛洪算法) f l o o d i n g 是一种基于完全随机图的查询算法，该算法实现简单，很早便应 用在p 2 p 系统中。泛洪算法的实现过程是：当一个节点发起一个查询时，会向 它所有的邻居节点发送一个查询请求，并初始化一个较大的t t l ( t i m e t o l i v e ) 值。它的邻居节点收到这个查询请求后，如果自己不是目标点，则把这个查询 消息转发给它的所有邻居节点，但除去给自己发送消息的节点，并把t t l 值减 1 。每个收到该查询消息的节点都会重复这个过程，直到查找到所需的资源或 t t l 值为o 结束查询。这个查询过程象洪水一样经过网络中的每个节点，产生 大量的冗余信息，势必会给网络带来巨大的流量冲击，导致系统性能下降，严 重情况可能使系统崩溃。这种搜索算法是盲目的，因此又称为盲目搜索算法阱3 。 其典型代表是g n u t e ll a 。 6 哈尔滨工程大学硕十学位论文 2 1 2m o difie d - b f s m o d i f i e d - - b f s 是对f l o o d i n g 的优化算法。与f l o o d i n g 算法不同的是， 当节点发送查询消息时，不是向它所有的邻居节点转发查询请求，而是随机的 选取一部分邻居节点( 通常值都很小) 转发查询请求。与f l o o d i n g 算法相比， 这种算法在一定程度上减少了网络流量，但也使查询时间增大而且查询也变得 不可靠2 副。 2 1 3 e x p a n d in g rin g ( 扩展环算法) 扩展环算法是对泛洪算法的一种改进算法。与泛洪算法不同的是它不是初 始化一个较大的t t l 值，而是给t t l 一个较小的值，当t t l 的值为0 时，如果 还没有找到目标节点，就给t t l 重新赋一个更大的值，重新搜索。如果没有找 到目标节点，则重复这个过程，直至t t l 值达到一个t h r e s h o l d 值为止。如果 连续l 次查询都没有找到目标节点，源节点就会向整个网络发送广播。在改算 法中，源节点可以有效的控制查询半径，减少了网络中的消息数量，但同时， 也增大了查询的延迟馏引。 2 1 4r a n d o mw aik e r ( 随机漫步) 在随机漫步算法中，请求者从它的邻居节点中，随机的选择k ( k = l ，2 ) 个节点发出k 个查询请求，这k 个节点称为漫步者。每一个漫步者都初始化一 个t t l 值，用来限制漫步者向前转发的节点个数，每向前转发一个节点，t t l 值减1 ，如果t t l 值不为o ，漫步者就从它的邻居节点中任意的选择一个节点 转发；如果t t l 值为0 ，查询结束；或者找到目标资源，查询结束。该方法很 好的限制了网络中消息的数量，不管网络的拓扑结构如何，都产生k 个消息。 但该算法的性能取决于k 和t t l 值的选择，如果k 值和t t l 值过小，延迟就会 很大；如果k 值和t t l 值过大，则会产生很多的冗余信息瞄1 。 2 2 基于d h t 的结构化资源定位技术 由于非结构化网络的查找效率和准确性低、可扩展性差并且严重浪费带宽 7 哈尔滨t 程大学硕十学位论文 等网络中的宝贵资源。研究人员逐渐将研究的焦点转移到分布式的、内容可寻 址的数据存储方法上，开发了分布式散列表( d h t ) ，以提供分布式索引、可扩 展性、可靠性和容错性。基于d h t 的结构化资源定位技术在效率和其它属性方 面都要优于非结构化资源定位技术。在结构化方法中，底层网络和对等端数量 能够任意增长，而不影响分布式应用的效率。这是与非结构化方法的显著差别。 下面将介绍几种优秀的基于d h t 的结构化资源定位技术。 2 2 1c a n ( c o n t e n t - a d d r e s s a bien e t w o r k ) 内容分布式网络 c a n 是加州大学伯克利分校提出的一种结构化p 2 p 路由算法。它的坐标空 间是虚拟的d 维笛卡尔积。把整个坐标空间分成若干个区域，每个节点都有一 个单独的区域且每个节点维护2 d 个邻居节点的信息，所谓邻居就是在d 一1 维上 都重叠而在d 维上相邻的节点。每个节点的路由表记录它邻居节点的i p 地址 和虚拟坐标空间。关键字k 通过哈希函数映射到坐标空间中的一个点p ，然后 关键字k 就存储在点p 所在的区域中的节点上。图2 1 是2 维f o ，q x o ，1 1 的c a n 笛卡尔坐标空间划分成五个节点区域的情况，其中c 和d 节点是邻居节点，而 a 和d 节点则不是邻居节点。 节点e 的虚拟坐标空 间区域 图2 1c a n 虚拟坐标空间 c a n 是完全分布式的，具有良好的可扩展性和容错性，节点能够绕过错误 节点进行消息转发。在路由的过程中，查询发起点首先计算出目标点的坐标， 哈尔滨t 程大学硕十学位论文 然后把含有目标点坐标的消息发送给它的邻居节点中与目标点坐标最接近的 节点，收到此查询消息的节点如果不是目标点则再向它自己的邻居节点中与目 标点坐标最接近的节点转发查询信息，重复该过程直至找到目标点或查询失败 结束。每个节点有多个邻居节点，因此到达目标点的路径可以有多条。 每一个加入到c a n 网络中的节点都必需有一块属于自己的坐标空间，c a n 通过分裂坐标空间来实现。当有新节点加入时，首先通过某种机制找到已经存 在c a n 网络中的一个节点，再根据c a n 的路由机制找到一个合适的区域分裂成 相等的两部分，一部分给原来区域的节点，另一部分给新加入的节点，新节点 和原来的节点更新他们的邻居信息并通知它们的邻居自身的变化。 当节点离开c a n 网络时，它的空间区域必需被系统收回分配给其他仍在c a n 网络中的节点。如果离开c a n 网络的节点区域能与它的一个邻居节点区域合并 成一个更大的区域，那么这个邻居节点将接管离开c a n 网络节点的区域和它所 负责的数据：如果离开节点的区域不能与它的邻居节点的区域合并成一个区 域，就把离开节点的区域和所负责的数据交给邻接节点中负责的区域最小的节 点接管，也就是邻接节点暂时负责两个区域。在一般情况下，c a n 的相邻节点 之间周期性的交换自己所知道的邻居节点信息，如果多次没有接收到某个节点 的更新消息，那么相邻节点则认为此节点已失效。这时，相邻节点将启动失效 节点区域的接收操作汹儿卿。 2 2 2 p a s t r y 算法 p a s t r y 是微软剑桥研究院和美国r i c e 大学的研究人员提出的结构化覆盖 网模型。p a s t r y 的逻辑结构也是环型的，但路由策略是按照类似于前缀匹配的 原则进行的，它的目标是使消息传递的距离最短。p a s t r y 网络中节点的标识符 同样是利用哈希函数映射得到的1 2 8 b i t s 的标识符，称为n o d e i d 。p a s t r y 网 络中的所有节点形成一个环，每个节点都维护一个叶子结点集( 1 e a fs e t ) 、一 个路由表( r o u t i n gt a b l e ) 、一个邻居结点集( n e i g h b o r h o o ds e t ) ，记录其在 逻辑环形空间中邻居节点的信息，如节点的标识符、i p 、端口号等。 叶子节点集记录着l 个从数值上看与本节点的n o d e i d 最接近的节点的集 i 1ii ，i 合，其中包括lh1 个n o d e i d 最接近且大于当前节点n o d e i d 的节点和lh1 个 9 哈尔滨工程大学硕士学位论文 n o d e i d 最接近且小于当前节点n o d e i d 的节点。叶子节点集在消息路由的时候 使用，其中l 是一个配置参数，通常为2 6 ，b 一般取值为4 ，因此l 通常取值 是1 6 。 路由表记录了与节点有共同前缀的一些节点信息及节点的位置。如果没有 任何一个节点与本节点有共同的前缀，那么这个表就是空的。一般情况下，路 由表由jl o g 廿ni 行组成，每行有2 6 一1 个表项，b 为上面提到的配置参数。第n 行的2 6 1 个表项分别指向前n 个数位和当前节点的前n 个数位相同而第n + 1 个数位取遍2 6 1 可能值的节点，b 的取值大小反映了路由表的长度和任意两 点间路由跳数的折衷。当b 取值越大时，路由表越长，而任意两点间的跳数则 越小；相反，当b 取值越小时，路由表的长度减小，占用的存储空间减少，而 任意两点间的跳数则很大。路由表中的阴影部分为节点n o d e i d 对应的位。 邻居节点集记录着与当前节点从数值上看最近的m 个节点的信息，m 仍为 系统配置参数，一般取2 2 6 。邻居节点集只有在维护节点位置信息时使用， 路由的时候用不到，即保证路由表中维护的每个节点在数值上看都是离当前节 点最近的节点。当前节点周期性的与邻居节点集合中的节点交换信息来检测这 些节点是否存在，如果节点没有反应则表明节点失效，那么当前节点要求其他 节点把自己的邻居节点集合发送过来从中选择一个作为新的邻居节点。 图2 2 是p a s t r y 网络中一个节点的数据结构示意图，节点的n o d e i d 为 1 0 2 3 3 1 0 2 ，b 取值为2 ，所有的数都是4 进制的。路由表从第0 行开始，每行 的阴影部分表示当前节点n o d e i d 对应的位。 当节点收到一条查询消息时，首先查看查询消息的关键字是否在自己的叶子节 点集合中，如果在，则直接把消息转发给叶子节点集合中对应的节点，查询结 束；如果查询目标节点不在叶子节点集合中，则用路由表开始路由，在路由表 中查找与目标节点的n o d e i d 有最长共同前缀的长度至少比与当前节点的共同 前缀大1 的节点进行转发；如果路由表中没有比当前节点与目标点有更长共同 前缀的节点，则在路由表中找一个至少和当前节点与目标节点n o d e i d 具有一 样长度前缀的节点，但标识符上更接近目标点的节点进行转发消息，这样的节 点一定位于叶子节点集合中。因此，只要叶子节点集合中不同时出现一半以上 的节点同时失效的情况，路由便可以正常进行。 1 0 哈尔滨t 程大学硕士学仲论文 n o d e l d1 0 2 3 3 1 0 2 l e a f s e t 10 2 3 3 0 3 31 0 2 3 3 0 2 l1 0 2 3 3 1 2 0 1 0 2 3 3 1 2 2 10 2 3 3 0 0 110 2 3 3 0 0 010 2 3 3 2 3 010 2 3 3 2 3 2 r o u t i n gt a b l e 0 2 2 1 2 10 212 2 3 0 1 2 0 33 1 2 0 3 2 0 3 01 1 3 0 1 2 3 31 2 2 3 0 2 0 31 3 0 2 1 0 2 2 1 0 0 3 1 2 0 31 0 1 3 2 1 0 221o 一3 2 3 3 0 2 0 2 0 0 2 3 01 0 2 1 1 3 0 2】0 2 2 2 3 0 23 0 2 3 0 3 2 21 0 2 3 1 - 0 0 010 2 3 2 1 2 13 10 2 3 3 0 0 1l1 0 2 3 3 1 2 3 2 01 0 2 3 3 1 2 o 2 n e i g h b o o r h o o ds e t 1 3 0 2 1 0 2 210 2 0 0 2 3 01 1 3 0 1 2 3 33 1 3 0 1 2 3 3 0 2 2 1 2 1 0 22 2 3 0 1 2 0 33 1 2 0 3 2 0 3 3 3 2 1 3 3 2 1 图2 2p a s t r y 节点数据结构图 当有一个新节点s 要加入到p a s t r y 网络时，首先要知道一个相邻节点a 的位置信息，通过节点a 进行路由来初始化自己的数据结构和通知其他节点自 己的加入。节点a 把新节点的n o d e i d 作为消息的内容发送出去，利用p a s t r y 的路由机制寻找与节点a 的n o d e i d 最接近的节点x ，作为响应，把节点a 和x 以及从节点a 到节点x 这条路径上的所有节点的数据结构发送给节点s ，节点 s 利用这些数据结构就可以初始化自己的数据结构以及通知其他节点自己的加 入。节点加入的时间复杂度为o ( 1 0 9 。) 。 当相邻节点不能和某个节点通信时，就认为该节点已失效。如果是叶子节 点集合中的节点失效，则当前节点要求它的叶子节点集合中具有最大节点 n o d e i d 或者具有最小节点n o d e i d ( 选择最大或最小节点n o d e i d 由失效节点决 定) 的节点把它的叶子节点集合发送过来，然后从中选择一个本节点的叶子节 点集合中没有的节点来替代失效节点。当然，替代节点首先要是一个存活的节 点。如果失效节点在路由表中，当前节点将从失效节点所在的行中选择另一个 存活节点，要求把它的路由表中对应位置的项发过来替代失效节点，如果当前 节点的路由表中对应的行已经没有可用节点，则从下一行中选择一个节点。这 个过程一直持续到找到一个替代节点或者遍历了路由表为止。 哈尔滨t 程大学硕十学何论文 2 2 3 t a p e s t r y 算法 t a p e s t r y 是由加州伯克