（应用数学专业论文）基于jxta的p2p路由定位和资源搜索研究.pdf

河南大学研究生硕士学位论文 第1 页 摘要 对等网络被称为改变i n t e m e t 的新一代网络技术。计算机网络不断向异构、分 布式、动态性、自治性方向发展，对等网络模型正是适应此趋势而发展起来的， 对等网络可以极大程度上提高网络效率，充分开发每个网络结点的潜力。但是， 对等网络的研究和发展也面临一些巨大的挑战，特别是在资源搜索和路由定位方 面，需要平衡路由的高效性和灵活性，保证可扩展性和稳定性。j x t a 是s u n 提 出的开源p 2 p 通信网络平台规范，实现了一种混合式架构的对等网络。 本文在对各种对等网络结构的路由和搜索技术进行分析的基础上，对j x t a 的 路由定位和资源搜索机制进行分析和评价，指出其中的不足和缺陷。同时结合无 结构化对等网络和结构化d h t 网络技术，提出了一种新的双层结构化网络系统， 能实现高效的路由效率，同时较好的处理结点的异构性和适应高度动态网络。最 后作者利用c h o r d 协议，扩展j x t a 协议规范，整合结构化d h t 技术，实现了一 个系统原型。实验结果表明了系统在动态网络环境中改善了路由定位效率并提高 了系统的可扩展性。 关键词：对等网络；j x t a ；c h o r d ；分布式散列表 第1 i 页河南大学研究生硕士学位论文 a b s t r a c t p e e r - t o - p e e r ( p 2 p ) n e t w o r k i n gi sg e n e r a l l y s e e na san e wt e c h n o l o g y 谢t l la s i g n i f i c a n ti m p a c t o nt h ei n t e m e t i n t e m e th a sb e e n b e c o m i n g m o r ea n dm o r e h e t e r o g e n e o u s ，d i s t r i b u t e da n dd y n a m i c c o m p a r e dw i t ht h et r a d i t i o n a lc sp a t t e r n ，p 2 p p a r e mh a sl o t so fi n c o m p a r a b l es u p e r i o r i t i e ss u c ha se x p a n s i b i l i t y , r o b u s t n e s s ，h i g h c o s tp e r f o r m a n c ea n dl o a db a l a n c i n g h o w e v e r ，p 2 pi sa l s of a c i n gs o m ec h a l l e n g e s ， e s p e c i a l l yi n r e s o u r c el o c a t i o na n d r o u t i n g i t sa l w a y sd i f f i c u l t t oa c h i e v e h i g h s c a l a b i l i t ya n ds t a b i l i t ya n dg e ta nb a l a n c eb e t e e w nt h er o u t i n ge f f i c i e n c ya n df l e x i b i l i t y t h eo p e n - s o u r c ep r o j e c tj x t ai sap e e r - t o p e e rp l a t f o r mo r i g i n a l l yc o n c e i v e db ys u n m i c r o s y s t e m si n c i tt r i e st o b u i l da e f f i c i e n t ，o p e na n dg o o d o p e r a t i o np 2 pp l a t f o r m t h i s p a p e ra n a l y z e v a r i o u s r o u t i n ga n dl o c a t i o n m e c h a n i s m so fd i f f e r e n t p e e r - t o - p e e rs t r u c t u r e ，a n dt h e nf o c u so nj x t al o c a t i o nm e c h a n i s m ，p o i n t i n go u tt h e s h o r t c o m i n g sa n dd e f i c i e n c i e so ft h e m i no r d e rt oi m p r o v et h ed i s a d v a n t a g e s ，an e w j x t a b a s e d l o c a t i o n s o l u t i o nm o d e lc o m b i n e dt h es t r u c t u r e da n du n - s t r u c t u r e d n e t w o r kl o c a t i o nm e c h a n i s mi s p u tf o r w a r d a n dt h e nt h ea u t h o ri m p l e m e n tas y s t e m p r o t o t y p eb a s e do nt h em e c h a n i s m t h es y s t e mr e p l a c et h ei n c o n s i s t e n td h tl o c a t i o n p o l i c yw i 也c h o r da n dc h a n g et h es e r v i c en a m e ds h a r e dr e s o u r c ed i s t r i b u t e di n d e x w h i l er e t a i n i n gt h es u p e r - n o d es t r u c t u r e a tl a s t ，aj x t as h e l li se x p a n d e da n ds o m e e v a l u a t i o ne x p e r i m e n t sa r ep r e c e d e d t h et e s td e m o n s t r a t ei tc a n i m p r o v et h ec o s t p e r f o r m a n c eo n l o c a t i o na n dr o u t i n ga n di ti sm o r ea d a p t a b l e t ot h eh i g h l yd y n a m i c a n dl a r g e - s c a l en e t w o r k k e yw o r d s ：p e e v t o p e e rn e t w o r k ；j x t a ；c h o r d ；d h t 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发袁或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过的材料。与我一同工作的同事对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学位串请久一c 学位论文作者) 鍪名_ ，荤乏j = 毒 i 2 0p 年岁月p 日 关于学位论文著作权使用授权书 本人经河南大学审核批准授予硕士学位。作为学位论文的作者，本人完全 了解并同意河南大学有关保留、使用学位论文的要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学住论文( 纸质文 本和电子文本) 以供公众检索、查阅。本人授权河南大学出于宣扬、展览学校 学术发展和进行学术交流等目的。可以采取影印、缩印、扫描乖拷贝等复制手 段保存、汇编学住论文( 纸质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 签名： 聋芝2 难 2 0 如年孓i j l1 2b 学住论文指导教师釜名： 2 0 河南大学研究生硕士学位论文第1 页 第1 章引言 1 1 研究背景和意义 1 1 1 研究背景 从n a p s t e r 的商业成功开始，对等网络开始活跃于商业应用和学术研究领域中。 对等网络被称为“改变i n t e m e t 的新一代网络技术”。对等网络能有效地利用网络 的异构性，充分开发每个结点的潜能，避免了中心化服务器带来的性能瓶颈、单 点失效等。对等网络的巨大优势使它至今被应用于信息共享、协同工作、数据存 储、分布式计算等多方面。国内外的学者也对对等网络有不同层次和不同程度的 研究，其中最重要的一项研究工作就是路由定位、资源搜索方面的探索。非中心 化的结构给网络组织和数据管理带来了巨大挑战。人们相继提出和发展了非结构 化和结构化网络两种方法，但它们都有各自的优点和缺陷。 另外，对等应用间的协作和通信协议的不统一也是应用中的另一问题。s u n 为此提出了开源的p 2 p 通信平台规范j x t a ，试图构建跨平台、语言无关、互操作 性的对等网络，允许计算机、移动设备、各种数字设施共同组成一个对等网络。 不过在高动态性、大规模环境下的性能欠缺是其发展的一个阻碍。 本文从对等网络中各种路由技术出发，分析评价j x t a 网络的路由实现，并探 索实现一个适合于现实动态网络的双层结构化网络结构模型。 1 1 2 当前国内外研究进展 当前对p 2 p 网络的研究可以分为三个阶段【1 】：( 1 ) 无结构p 2 p 网络；( 2 ) 结 构化p 2 p 网络；( 3 ) 混合式p 2 p 网络。主要是两种体系的研究，包括非结构化对 等网络和结构化对等网络。 第2 页河南大学研究生硕士学位论文 一、非结构化对等网络的研究进展 非结构化对等网络通常见诸于商业应用或通信系统平台。 n a p s t e r 【2 1 作为对等网络的先驱，也是非结构化网络的典型代表。它作为较早的 p 2 p 应用，结合了c s 和对等模式，由一些中心服务器保存用户的共享文件索引信 息，同时跟踪用户状态，提供音乐文件的共享服务。它在一定程度上缓解了服务 器的压力，路由定位方面能达到c s 模式的跳数o ( 1 ) ，但未摆脱服务器模式的 单点失效和性能瓶颈，同时未很好的利用用户的异构性。 n a p s t e r 之后兴起了包括b i t t o r r e n t ，g n u t e l l a ，k a z a a ，f r e e n e t 等著名的p 2 p 应用。 b t 增加了一种t r a c k e r 机制用于对等端间的发现，所以该网络依然依赖于服 务器的维护和监控，导致对等网络应用的可用性低。g n u t e l l av 0 4 作为纯分布式 p 2 p 网络，采用广播洪泛法和生存时间t t l 实现路由，能防止单点故障，但是系 统开销较大且成功率没有保障。f r e e n e t 试图构建自由、安全、匿名的信息发布和 获取平台，更加注重信息的隐蔽性，消息查询通过一种“隧道路由的机制实现， 并且实现了存储临近性，有相对较好的扩展性但查询成功率上仍不能保证。 非结构化对等网络结构简单，但其依赖于服务器的索引机制或路由效率较低， 可靠性和可扩展性低。 二、结构化对等网络的研究进展 结构化对等网络通常应用分布式散列函数d h t 在存储内容和存储位置之间直 接建立映射关系，能较大提高定位的准确性和路由的效率。常见的结构化对等网 络包括c h o r d ，c a n ，p a s t r y ，t a p e s t r y ，v i c e r o y 等。 c h o r d 3 】是由s t o i c a 等人于2 0 0 1 年提出，它基于一致性散列函数将对象和结点 映射到c h o r d 环中，在n 个结点的系统中，每个结点维护长度为l o g n 的路由表， 能实现o ( 1 0 9 n ) 的路由效率，具有较优的查询效率、负载均衡及良好的容错和 自适应性。 河南大学研究生硕士学位论文第3 页 2 0 0 1 年r a t n a s a m y 等人提出了内容可寻址网络( c a n ) 【4 1 。在c a n 中，关键 字和值可以映射到数值临近的结点，并且引入了多维标识符空间的概念，极大地 提高了路由效率。 t a p s t r y 5 】是一个面向广域分布式数据存取、容错的超立方体结构的p 2 p 模型， 其路由和定位来源于p l a x t o n ，采用逐位匹配的后缀路由，每个结点维护一个路由 表，其中第i 层第j 项表示与当前i d 后缀匹配i 一1 位并以j 开头的结点，实现了o ( 1 0 9 n ) 跳的路由效率。 结构化对等网络对结点和数据进行有规律、有组织的映射和管理，采用数值 临近路由、位置临近路由、后缀匹配路由等技术，对路由定位有很大提高，但在 网络动态变化时面对数据或索引重新分发的问题，以及较大的维护开销。 三、j x t a 的研究进展 j x t a 6 1 是s u n 于2 0 0 1 年提出的对等网络通信平台规范，它并没有对特定的 应用策略和机制作出限定，提供p 2 p 网络最基础的关键技术，具有互操作性和平 台独立性等优点。在2 0 0 3 年j x t a 规范推出2 0 版本，2 0 后的版本中j x t a 引入 了松散一致的d h t 和有限范围遍历的路由定位和资源搜索方法【7 】，大幅度提高了 j x t a 的路由效率，不过其d h t 方法和遍历机制仍有较大缺陷，j x t a 的相关机制 将在本文第三章详细分析。 j x t a 中的一个开源项目m e t e o r 5 1 提出了一个基于j x t a 的资源搜索和定位的 改进应用，该项目在j x t a 中引入了分布式散列函数，在资源搜索层加入了结构化 d h t 算法( 包括c h o r d ，c a n ) ，但底层覆盖网络仍然是原j x t a 实现，只是在上 层加入了d h t 服务，形成了三层结构：物理层、j x t a 路由层、资源d h t 搜索层， 底层路由机制没有任何改变。 武汉科技大学张智在2 0 0 7 年发表文章提出基于小世界的j x t a 改进方案【8 】， 将j x t a 中的汇聚结点视图r p v 依据概率分解为本地短链和本地长链，提高搜索 的精准性和可靠性，但是没有改变r p v 中全局视图的缺陷，在大规模动态环境下 第4 页河南大学研究生硕士学位论文 维护开销较大，同时定位不准确，在概率设置上也有较大主观因素。 大连理工大学曹玉琳提出了多层次的j x t a 架构【9 】引入c h o r d 协议，同时增 加多个超结点结构，每一层次均可采用不同的路由策略，使得系统的路由灵活性 增强，不过与m e t e o r 项目类似，c h o r d 协议只是作为资源搜索的上层服务定义的， 并未整合到底层覆盖网络路由当中实现，并且多层次带来的维护开销也不可忽视。 1 。2 研究内容 由上述国内外研究表明： ( 1 ) 无结构化网络结构简单，易于实现。数据内容和存储没有映射关系，路 由和定位方法往往采用洪泛方法，开销大、路由效率不高、数据无法精确定位。 但是由于结点间关系的松散性使网络具有较好的自适应性和容错性，实现匿名性 和安全保障。 ( 2 ) 结构化对等网络引入分布式散列表将结点和数据映射到覆盖网中，采用 数值临近路由、逐位匹配路由、位置临近路由等路由策略实现了高效的路由定位， 每个结点只需维护有限个邻居信息，自适应性和扩展性较好，不过由于需要维护 网络的结构性，结构化网络带来较大的维护消耗，数据必须周期性的进行重新分 发。并且其未考虑到结点的异构特征。 ( 3 ) j x t a v 2 0 后的版本引入了d h t 策略，一定程度上提高了路由和资源搜 索效率，但仍不适合在高动态性和自组织性的网络中。目前国内外对其的研究主 要集中于应用层的开发或上层引入资源搜索的新机制，其本质的路由定位机制并 未触及。 本文将从非结构化网络和结构化网络分析，结合j x t a 的混合式结构，引入结 构化c h o r d 算法，扩展和修改原j x t a 的实现，构建一个新的双层结构化的对等网 络通信平台。具体内容包括： ；- 7 南大学研究生硕士学位论文第5 页 ( 1 ) 对等网络路由技术分析。对各种对等网络结构的路由和定位机制进行分 析和总结，作为系统方案设计的基础。 ( 2 ) j x t a 协议及其实现分析。详细分析和评价j x t a 协议的路由定位和资 源搜索策略和机制，作为系统方案的依据。 ( 3 ) 设计结合结构化网络技术的混合式网络。在j x t a 中引入c h o r d 改变其 d h t 和遍历机制，更改汇聚层服务和s r d i 服务，形成适应实际应用的通用对等 网络通信平台。 1 3 本文的内容及组织结构 本文基于路由技术的研究和j x t a 的缺陷，对j x t a 路由定位机制进行改进， 提出了结合c h o r d 的混合式结构网络。本论文拟分为以下6 个部分： 第1 章引言主要介绍本文的选题背景、研究现状及存在的问题，讨论了本 文的研究目标和研究内容，并简要论述了设计思路，最后确定了论文的组织结构。 第2 章p 2 p 路由定位技术研究主要介绍当今对等网络中经典和重要的路由 定位机制，分析其中的优缺点，得出结论，作为设计基础。 第3 章j x t a 协议及路由定位的分析研究主要介绍j x t a 协议，并详细分析 了j x t a 实现的路由定位机制，作为本文提出设计方案的依据。 第4 章系统方案设计和实现是在基于上述几章的论述下结合非结构化网络 和结构化网络的优势提出的一种混合式架构，并通过在3 x t a 上的改进实现一个通 用的对等网络平台。 第5 章系统原型应用及测试首先完成了基于原型系统的s h e l l 程序，同时在 实际的网络平台之上测试其各种性能指标，并同原j x t a 进行对比，分析实验结果。 第6 章结论和展望对本文研究内容进行了总结，并对未来的工作做出了展 望，最后提出一些具有进一步研究价值的问题。 第6 页河南大学研究生硕士学位论文 第2 章p 2 p 路由定位技术研究 本章首先从p 2 p 的定义出发，分析其特性，指出p 2 p 网络路由定位和资源搜 索的挑战，然后从分析重叠网路由的关键因素入手分别详细分析了非结构化网络 和结构化网络的各种路由定位方法，最后从多个方面对每种路由定位技术进行评 价并总结。 2 1p 2 p 技术概述 r s t e i n m e t z 等对p 2 p 的定义为【1o 】：一个对等端到对等端系统( p 2 p ) 是等同 的、自治的实体构成的一个自组织的系统，它的目的是在一个联网的环境中共享 分布式的资源，避免中心化的服务。m i l e r 对p 2 p 定义了五个关键特性 1 1 】：( 1 ) 网 络提供结点间实时的数据传输或消息传递；( 2 ) 结点既是客户端又是服务器；( 3 ) 网络的内容由分布的结点提供；( 4 ) 结点具有网络控制权和自治权；( 5 ) 网络允 许不总是连接的结点和可能没有永久i p 地址的结点参与。由上述定义可知对等网 络系统是与中心化系统有很大区别的一种模式，可以实现去中心化的自组织和资 源共享及利用，可以充分利用网络中各结点的带宽和潜力，能够防止中心化服务 中的单点失效，增加可用性和健壮性。 p 2 p 系统面临的挑战之一在于如何在非中心化服务情况下实现系统的有效组 织、数据的有效管理、数据的高效定位和查找服务l l 引。p 2 p 对等网络并不局限于 计算机桌面应用，同时包括各种数字移动设备，同时网络面对的是大规模的结点 和未知的加入失效行为，p 2 p 网络中存在的高动态性、异构性、分布性等特征，给 路由定位和资源搜索带来巨大挑战。 河南大学研究生硕士学位论文第7 页 ( 1 ) p 2 p 系统通常规模巨大。p 2 p 系统通常用于分布式计算，分布式存储和 流媒体分发等应用，往往面向巨大的用户群体和海量资源。p 2 p 路由必须拥有良好 的可扩展性和在巨大的异构网络拓扑中保持高性能。 ( 2 ) p 2 p 系统的强分布性。各个对等端和资源对象在物理空间中分布广泛， 给资源组织和路由定位产生较大困难。 ( 3 ) p 2 p 系统的高度动态性。各个对等端的加入和退出都是无法预料的，路 由失效的频率较高，p 2 p 系统必须具有较强的自适应性和鲁棒性。 ( 4 ) p 2 p 系统的异构性。各个对等端所处的网络环境有可能有巨大差别，甚 至采用不同的通信协议或者位于防火墙的保护和n a t 之后，如何兼容各种网络结 构，穿越防火墙和n a t 也是其中的一个困难。 2 2 路由定位技术研究 2 2 1 重叠网 重叠网( o v e r l a y ) 是一层独立于底层物理拓扑结构的逻辑结构，它在物理层 之上被创建，本文认为它是研究p 2 p 网络的基础。 对等网络重叠网是由对等端的分布式系统或数字设备组成，在本文中对等端 亦称为结点。每个对等端在重叠网中负责消息路由和共享信息。重叠网中的关键 评价特征包括【1 4 】：自组织性、角色划分、资源共享、扩展性、匿名性和稳定性。 在本文中我们关心涉及路由技术的角色划分、资源共享、扩展性和稳定性等特征。 一、形式定义 重叠网可以看作是一个有向图g ( v ，e ) ，其中v 指网络中结点的集合，e 指结点间的联系。结点p 拥有重叠网唯一标识符和物理层的地址，而边( p ，q ) 第8 页河南大学研究生硕士学位论文 指结点p ，q 直接在物理层可以直接相互通信。在重叠网中这种通信是以重叠网标 识符作为通信地址。 路。 如图2 1 所示为一重叠网示意图，其中大圆圈表示结点，虚线代表结点间的链 a b 图2 1重叠网 二、重叠网上的路由 每个结点在重叠网中都是动态的，可以随时退出和加入。在结点退出和加入 过程中将影响网络中周边结点的状态，从而重叠网的重要作用之一在于维护结点 间的状态，保证每个结点对周边及整个网络中的视图。 假设网络全局各结点间的路由视图为g ，为了保证资源搜索和路由定位，每 个结点必须保存一个本地视图p v ，其中本地视图p v 必须是g 的子集既p v ( g ) 。 每个视图p v 必须包括路由定位时必须含有的信息，包括该结点可以直接联系或路 由需要的结点信息及相应的通信信息( 比如i p 地址) 。 d ， ) )j 一 、一 河南大学研究生硕士学位论文第9 页 假设结点p 需向结点q 发送信息，在重叠网中的路由定位过程可以简化为以 下步骤： ( 1 ) 检查在本地视图p v 中是否包含边( p ，q ) ，若包含则直接利用底层物理 网络通信。 ( 2 ) 否则利用某种机制或策略，在本地视图中寻找与结点q 接近的结点t ， 并向t 转发信息。 从上可以总结出重叠网中路由的几个关键问题： ( 1 ) 各个结点的本地视图之间的一致性问题。因为每个结点只知道局部信息， 当有新结点加入或退出时，全局视图从g 变为g ，而每个局部视图变化在一定时 间内有时并不能同步改变，出现某结点i 的视图p v i g ，而另结点j 的视图p 、7 ：i g ， 从而在路由定位中出现差错。 ( 2 ) 重叠网的分裂问题。随着结点的加入和退出，有可能重叠网会被分裂为 几个独立的部分，此时需要确保结点之间的发现策略使重叠网中的结点之间一定 可以相互到达。并能在产生分裂后的短时间内重新组合成一个整体。 ( 3 ) 路由定位机制的确定。需要确定路由路径和方法，由局部本地视图可以 逐步到达目的地。 以上几个关键问题在一些现有的算法和系统中都有相应的解决办法，但仍然 是棘手的难题。 2 2 2 路由定位技术研究 p 2 p 系统主要可以分为非结构化网络和结构化网络，本文分别从这两类分析相 第1 0 页河南大学研究生硕士学位论文 应的路由技术。 一、非结构化网络路由 在非结构化网络中，p 2 p 重叠网并没有特定的组织形式和结构。每个结点间可 能只保存相邻结点或特定结点的信息，数据和存储位置没有特定的映射关系。结 点传输信息无法直接准确定位，往往采用的路由方式包括：服务器路由和洪泛路 由。 ( 1 ) 服务器路由。网络中存在专门的服务器用于保存各个结点的信息以及它 们发布的信息索引，在查找资源时用户先向服务器请求，服务器查找保存的资源 索引信息，若包含要查找资源则返回资源所在结点的信息，再由请求者直接和资 源所有者联系进行信息查找。典型的系统包括n a p s t e r 、b i t t o r r e n t 等。如图2 2 所 示为服务器路由方式。服务器路由只需向服务器请求即可得到目标结点，路由跳 数可达到o ( 1 ) 。 缀笏貉结也 p 1 、 i ， 7 1 p 2 图2 2服务器路由 ( 2 ) 洪泛路由。结点以洪泛方式或相似改进方式向自己所知的所有邻居结点 河南大学研究生硕士学位论文第1 1 页 发送请求，邻居结点接收到请求后再以相同的方式转发直至消息定位成功。在洪 泛路由中必须保证两个条件：( a ) 防止重复和循环发送。每个结点必须记住自己 处理过的请求，以防止发送给邻居后再由邻居发送回来的重复过程或循环，浪费 带宽和加大开销。( b ) 防止无限制转发。每个请求需设置生存时间t t l ，以控制 洪泛范围，在t t l 等于0 时就应当丢弃而不转发，响应查找失败信息。洪泛法的 路由跳数是o ( t t l ) 。洪泛路由算法可以如下描述： 图2 3 洪泛路由算法 第1 2 页河南大学研究生硕士学位论文 露溺谪承 图2 4t t l = 3 的洪泛路由 ( 3 ) 超结点路由。通过引入“超结点，重叠网中的所有结点进行聚类成簇， 在同一簇中由一超结点管理本簇的发布信息，查询时先由超结点在组内查询后通 常采用洪泛在超结点层遍历。此种方式下使洪泛的范围局限于超结点层，减少了 系统开销同时加速了同簇内的路由定位。本文中我们将采用超结点路由方法，改 变超结点层的洪泛策略，结合d h t 路由方式，实现灵活高效的路由。 由上述可分析得出如下结论： ( 1 ) 服务器路由结构简单，路由跳数o ( 1 ) 数量级，但是可扩展性和可用 性差，中心服务器成为网络性能的瓶颈，容易造成单点失效且负载过重。 ( 2 ) 洪泛法中每个结点只需保存自己的资源和部分邻居结点信息，不用维护 网络中的更新和变化，但查找开销较大且成功率没有任何保证，查询寿命局限于 t t l 范围之内。 河南大学研究生硕士学位论文第1 3 页 ( 3 ) 非结构化网络将重叠网络认为是一个完全随机图，结点之间的链路没有 遵循某些预先定义的拓扑来构建。它们一般不提供性能保证，但容错性好，支持 复杂的查询，并受结点频繁加入和退出系统的影响小。但是查询的结果可能不完 全，查询速度较慢，采用广播查询的系统对网络带宽的消耗非常大，并由此带来 可扩展性差等问题。 二、结构化网络路由 结构化网络路由通常在信息内容和存储位置上存在映射关系，从而增加路由 定位的准确性。 ( 1 ) d h t 路由 分散式哈希表( d i s t r i b u t e dh a s ht a b l e ) 用来将一个关键值的集合映射到所有 在分布式系统中的结点，它提供了一种机制实现各个结点的总体视图，使路由定 位和资源检索的效率大大提高【1 5 】。 d h t 将资源和结点散列到一个映射空间中，每个结点依据d h t 方法管理一定 资源信息或索引，并且保存有路由所需的相关其它结点信息即路由表，在每次转 发请求时首先从自己路由表中查找与管理该请求资源相近的结点，并转发请求。 其最关键的就是结点查找下一步路由的过程，这一机制的不同构成了不同的结构 化路由方法。 引入分布式散列表的结构化网络的新特征包括f 16 】：( a ) 每个结点需维护少量 重叠网中的其他结点的信息；( b ) 数据内容和存储结点间存在映射空间，映射在 一个常规地址空间中；( c ) 分布式散列表可以提高路由定位的准确性，若网络中 存在要查找的数据可以保证能查找到并路由跳数一般可以达到o ( 1 0 9 n ) 。 ( 2 ) 路由定位技术 p 2 p 系统的d h t 路由方法包括以下几种【l 】： 数值邻近路由：路由过程的每一步中当前结点都可以在路由表中选择与目的 i d 最邻近的结点作为下一跳。如c h o r d ，k a d e m l i z ，s k i p n e t 。c h o r d 被喻为简单 第1 4 页河南大学研究生硕士学位论文 优美的一种d h t 算法。它利用一致性散列函数散列关键字到相应的结点中，标识 符是由l 位组成，散列空间是一个2 l 的标识符环。每个结点管理o ( 1 0 - g n ) 个数 据信息，而由一致性散列函数可以实现加入退出过程只涉及到o ( 1 0 9 n ) 个数据 的转移，只有一个结点受此波动影响。因此可以达到负载均衡和即使在高波动性 情况下的路由高效和准确。本文将在第四章继续探讨c h o r d 并结合超结点路由形 成灵活高效的层次结构化网络。 逐位匹配路由：与数值邻近路由相似，不过是以匹配的位数作为距离的度量 尺度。 位置邻近路由：每个结点的路由表记录自己在多维空间中的邻居，每次选择 离目的结点最近的邻居作为下一跳。如t a p e s t r y ，p a s t r y ，k o o r d e 。p a s t r y 与c h o r d 相似结点和数据都与1 位的标识符联系，但并不依靠像c h o r d 一样的环结构而是基 于标识符的数值临近性。每个结点保存有路由表、叶子集合、邻居集合。查找关 键字时先从叶子集合中查找邻近结点，若不在叶子集合范围之内则在路由表中查 找。p a s t r y 引入临近性度量还可以实现网络局部性提高路由效率。 当然，还包括一些结合以上路由的层次路由和混合式路由形成一些更加灵活 的路由方式。以上方式主要的关键之处就是路由度量的选择上。 三、路由定位技术评价和比较 对路由技术的性能评价标准一般包括以下几个因素： ( 1 ) 路由跳数。发送一个查询请求所需要的路由跳数，包括平均路由跳数和 最坏情况下的路由跳数。 ( 2 ) 维护开销。当结点加入和退出时即在一定的网络波动性情况下对网络的 影响程度和维持网络状态的开销。 ( 3 ) 容错性。结点意外退出或失效时网络中保存的数据失效的程度和查询请 求丢弃的概率。 ( 4 ) 负载平衡。每个结点管理的数据量的差异及处理的消息请求的差异。 河南大学研究生硕士学位论文第1 5 页 下面本文分别对三种路由方式的典型代表进行分析，其中n 表示网络的结点 个数。 ( 1 ) c h o r d 。c h o r d 中每个结点保存有o ( 1 0 9 n ) 个其它结点的路由信息，每 个结点保持相距2 的指数次方，平均管理c h o r d 环中长度为o ( 1 0 9 n ) 的空间区 间。每步路由选择一个与目的i d 最近的结点，至少减少2 的指数次的距离，所以 平均路由跳数可以达到o ( 1 0 9 y ) 。当一个结点加入网络时，影响网络中的数据信 息为该结点后继保存的部分信息，平均为o ( 1 0 9 n ) 。另外平均有o ( 1 0 9 n ) 个结 点的路由表应包含有加入结点信息，每次改变需经过o ( 1 0 9 n ) 跳路由，从而加 入网络的影响达到o ( 1 0 9 2 n ) 。在数据随机的情况下，每个结点管理的数据和处 理的消息请求相同，达到负载平衡。为了保持容错性，每个结点必须额外保存一 部分后继信息，避免单后继的脆弱，i o ns t o i e a 等认为保存o ( 1 0 9 n ) 个后继即能 保证高容错性【12 1 ，所以容错的开销为o ( 1 0 9 n ) 。 ( 2 ) p a s t r y 1 3 1 。p a s t r y 中包括路由表、叶子集和邻居集。需保存的结点项数 = l + b 木l o g b n + m ，其中b 为路由表中采取的进制，l 为叶子集项数，m 为邻居集 项数。在消息路由中有很大概率每次至少多匹配一位，从而找到更加接近的结点， 当然在一定情况下也有可能只是转发给相同前缀匹配的结点中，不过概率很小， 当l 达到2 * b 时小于0 6 ，所以路由跳数为o ( i o g b n ) 。新结点加入或退出时需 修正路由表、叶子集和邻居集，时间复杂度为o ( 1 0 9 2 b n ) 。叶子集、邻居集的存 在可以提高p a s t r y 的自适应性效果，当有结点失效的情况下及时地修复路由表。 ( 3 ) c a n 1 7 】。c a n 需维护一个多维空间中的邻居信息。对于d 维c a n ，每 个结点需保存有2 d 个邻居结点信息。假设c a n 中划分成全部相同的区域，则平 均定位跳数= l 2 * n l d 幸1 2 d = 1 4 * n l d 幸d 。一般情况下路由跳数为o ( d 幸n l d ) ， 当d = l o g n 时跳数变为o ( 1 0 9 n ) 。结点插入的时间复杂度依然是o ( d 宰n l d ) 。 从以上分析可以得出表2 1 的分析结果，另外可以得到各种路由定位方法中结 点度和路由跳数之间的关系如图2 5 。 第1 6 页河南大学研究生硕士学位论文 表2 1路由定位性能分析 路由定位路由跳数结点度结点加入开销 数值邻近路由 c h o r d o ( 1 0 9 n )0 0 0 9 n )o ( 1 0 9 2 n ) 位置邻近路由 p a s t r yo ( 1 0 9 b n )o ( 1 0 9 b n )o ( 1 0 9 2 b n ) 逐位匹配路由c a n o ( d 木n 1 d )2 d o ( d 木n l d ) 爨渤凌毅 c l k x j n o ( ) o ( o i o g n o ( n 缀点夜 图2 - 5 结点度和路由跳数的关系 河南大学研究生硕士学位论文第1 7 页 第3 章j x t a 协议及路由定位的分析和研究 本章对j x t a 的路由定位机制进行讨论和分析。j x t a 采用双层超结点路由适 应现实应用需求，同时维护一种松散一致d h t 以减少对动态网络结点状态的维护 开销。本文通过对j x t a 实现原理和关键技术的分析，并与其他路由定位方式进行 对比得出其机制的缺陷，同时据此提出一种新的路由机制。 3 1j x t a 概述 j x t a e l 9 1 项目由s u n 在2 0 0 1 年提出，由s u n 开发人员和j x t a 社区人员共同 维护，旨在构建通用对等网络通信平台【1 8 】。s u n 于同年提出l 钾1 o 协议，并于 2 0 0 3 年更新为v 2 o 版本至今。j x t a 被设计成独立于语言、系统平台、网络平台 且被设计成能在任何数字设备上实现，包括传感器、消费电子产品、桌面电脑、 服务器和存储设备。j x t a 定义了一类用于自治、普遍、对等计算的标准协议，它 并没有对特定的应用机制作出限定，只提供p 2 p 网络最基础的关键技术规范和实 现。 j x t a 由六个协议组成，通过这六个协议来完成对等体之间的路由、发现、组 织、通信和控制。这六个协议可以分为两类【2 0 】： ( 1 ) 核心规范协议： 核心规范协议定义了系统必需的少量组件和行为，是j x t a 的基础规范同时是 每个i x t a 实现必需完成的协议。包括两种协议： ( a ) 对等体端点协议 对等体端点协议定义了j x t a 中的消息路由机制，通过该协议对等体可以通过 一定物理路由跳数后到达目的结点【7 1 。该协议利用保存的路由信息进行通信，当原 第1 8 页河南大学研究生硕士学位论文 路由失效时，则通过在网络中寻找路由通告获得。需注意的是这里指的路由与本 文其它地方的路由并不一致，此特指实际物理层的通信。 ( b ) 对等体解析协议 该协议用于对等体发送请求和接受响应，并把响应传送给上层【刀。该协议实现 的方法是在每个请求中附加处理该请求服务名称和参数，相应的处理名称和参数 由上层处理服务进行注册，当接收到请求或得到响应时根据注册信息发送给与该 请求或响应相关联的服务。 ( 2 ) 标准服务协议 标准服务协议是构成一个完整的应用所需要的除核心规范协议外的组件和行 为。 ( a ) 汇聚对等体协议 该协议为整个路由定位中最重要的协议。它提供了j x t a 双层结构中超结点层 的行为。该协议包括了边缘结点和超结点间的租赁协议、有限范围遍历机制、松 散一致d h t 等。我们将在第二节和第三节进行详细分析。 ( b ) 对等体发现协议 对等体发现协议为对等体提供了一种机制来发布自己的资源和发现其他对等 体的资源。 ( c ) 对等体信息协议 该协议为对等体提供了一种机制来获取其他对等体的状态和监视其他对等体 的信息，如状态、正常运行时间、流量负荷、容量等。 ( d ) 对等体绑定协议 该协议为对等体提供了一种机制来与一个或多个对等体建立虚拟通信管道。 对等体可使用管道绑定协议去绑定物理端口。 河南大学研究生硕士学位论文第1 9 页 标准服务协议 三三困 三三固 三三困 三三困 核心规范协议 3 2j x t a 超结点重叠网 图3 - 1j x t a 协议 j x t a 组建了个与物理层相隔离的逻辑虚拟网络，以屏蔽底层复杂物理网络 ( 如防火墙、n a t 等) 。它通过对每个资源和对等体赋予一个唯一i d 以形成一个 重叠网，在重叠网中j x t a 把对等体分为两类【2 1 1 ，一类是普通结点被称为边缘结 点( e d g ep e e r s ) ，另一类为超结点，超结点包括汇聚结点( r e n d e z v o u sp e e r s ) 和中 继结点。汇聚结点用于消息的传递和路由，中继结点用于穿透防火墙和n a t 等无 法直接路由的对等体。因此j x t a 是典型的层次超结点路由结构。 j x t a 把重叠网中的对等体分成多个对等组，对等组代表一些拥有共同需求的 对等体的集合，它们共同遵循一些机制和提供共同的服务，对等体可以按照需要 创建或加入一个组，对等体间的消息传递和发布都局限于一个对等组中。对等组 的引入为网络划分了一个虚拟的逻辑边界，限制了服务范围和消息路由区域，形 成了很好的组织结构。对等组的作用包括【7 _ l ： ( 1 ) 对等组可以增强网络的安全性，只有相同组内用户才可以相互之间通信 并使用和提供相应服务。对等组与物理网络无关，对来自各个网络的结点划分为 各个逻辑区域。 ( 2 ) 限制消息传递范围和边界。 ( 3 ) 对等组内可以对组内成员进行监控和了解各个对等体情况。 j x t a 的重叠网如图3 2 所示，对等体间划分成层级的边缘结点和超结点，同 第2 0 页；- 7 南大学研究生硕士学位论文 时一部分对等体组成一个对等组，对等组内提供各类服务包括j x t a 的标准服务和 高层应用扩展服务，各种服务被局限于一个对等组内，相同组内共享数据和服务。 图3 2 t a 重叠网 3 1 3 j x t a 的路由定位和资源搜索机制的研究 3 3 1j x t a 通信机制 一、通告和消息 j x t a 把所有的资源包括对等体、对等组、路由信息和服务描述成通告。通告 是由平台无关的结构化语言x m l 组成的文档。j x t a 中的任何消息都是用通告来 描述。开发者可以自定义通告或扩展已有的通告。j x t a 中的任何行为都可以归结 为获取通告再根据通告做出相应行为。 对等体之间的通信交互采用的是消息机制。对等体之间通过发送消息来发送 和响应请求，消息由元素和元素值组成，通信层可以采用合适的方式发送消息， 包括x m l 方式或二进制数据。 河南大学研究生硕士学位论文第2 1 页 二、绑定服务 由于重叠网中每个资源和对等体都是由逻辑上的唯一d 作为标识符，所以在 通信时需有i d 到通信地址的转换以及资源i d 到存储或管理结点的转换绑定过程。 所有的这种绑定服务都是由通过查找上述提到的一个或多个通告所实现。通告的 发布、传递和维护将在4 2 小节进行论述。 3 3 2j x t a 路由定位机制 由以上内容可知j x t a 中最重要的就是发布和查找通告。j x t a 查找和发布通 告是以汇聚结点为基础。结点发布通告是由汇聚结点保存通告的索引并对索引在 汇聚层进行分发，而查找通告是由汇聚结点查找通告索引并获取发布通告结点后 由发布者响应通告。 一、汇聚结点视图 由第二章关于重叠网路由的研究和各种路由定位技术的分析可得，对等结点 必需保存一部分路由定位必须的其他结点信息形成本地视图以作为路由定位的已 知条件，并且必须满足本地视图与全局网络视图的一致性才能保证定位的准确性。 j x t a 中汇聚结点保存有网络中尽可能多的其他汇聚结点信息形成汇聚结点视图。 视图中保存的每个汇聚结点按照i d 大小形成有序环形排列如r p v ( r 1 ，r 2 ，r 3 ，r 4 ) 。对r p v 中的每个础结点，鼬1 被称为上结点，r i + l 被称为 下结点，用于一种有限范围遍历算法。在路由时从环形对列r p v 中按照一种被称 为松散一致的d h t 算法查找对应结点。在j x t a 中并不要求每个结点的视图是完 全一致的，而是一种松散状态。路由的可达性由d h t 和有限范围遍历结合来保证。 通过分析j x s ev 2 5 源代码得出j x t a 维持的d h t 算法。其中r p v 为本地视 图，保存有