（计算机应用技术专业论文）chordbased+p2p网络路由定位策略研究.pdf

中山大学硕士学位论文 竺! 坐! 型! 望塑竺堕虫塞堡丝堕竺壅 摘要 相对于i n t e m e t 传统的客户端服务器模式来说，p 2 p 是一种完全的分布式 计算模型，它在系统的负载均衡性、健壮性、可扩展性及高性价比等方面具有无 可比拟的优势，故成为分布式网络领域的研究热点之一。p 2 p 按照拓扑构造总体 上可分为非结构化p 2 p 与结构化p 2 p 两类，结构化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 路由阶段，由于原路由算法仅考虑了逻辑距离，且通过f i n g e r 表特性分析，当它沿着c h o r d 环顺时针单向转发至下一跳时所覆盖的逻 辑距离不一定最大，故对路由表进行扩展，增加一个r f m g e r 表，支持双 向交替逼近目标，于此同时，定义节点下一跳度量值计算的数学模型， 它为节点至下一跳的逻辑距离与物理距离的一个均衡值，进而可在 f i n g e r 与r f i n g e r 表中选择最佳下一跳转发 在c h o r d 动态维护阶段，节点必须周期性执行f i x f m g e r s 0 过程，不管路 由表正确与否，故产生巨大网络开销，我们利用节点的在线时间的异构 性，构造一个双层的c h o r d 环，当有节点加入或失效被探测到时，便通 知相对稳定的f i x c h o r d 环来修复“扰动”现象引发的路由表错误，故 n o r m a l - c h o r d 中节点路由表由先前的主动更新方式转变为一种触发式更 新的方式，极大的消减了系统的开销与增强了系统的抗“扰动”能力。 最后，通过覆盖网仿真器p 2 p s i m 的实验验证，改进的算法在路由跳数，路 由时延，查询失败率，系统开销均优于原c h o r d 算法。 关键词：下一跳度量，异构性，双层c h o r d ，p 2 p s i m 中山大学硕士学位论文 c i i o f d - b a s e dp 2 p 网络路由定位策略研究 a b s tr a c t c o m p a r e dw i mt h et r a d i t i o n a lc l i e n t s e r v e rm o d e lo fi n t e r n e t p 2 p h a st h eg r e a t a d v a n t a g e si nl o a db a l a n c i n g , r o b u s t n e s s ，s e a l a b i l i t ya n dh i g hc o s t p e r f o r m a n c ea n d o t h e ra s p e c t sw h i c hi saf u l l yd i s t r i b u t e dc o m p u t i n gm o d e l ，s oi th a sb e c o m e sah o t t o p i co fr e s e a r c hi nt h ea r e ao fd i s t r i b u t e dn e t w o r k s , p 2 pc a l lb ed i v i d e di n t ot w o c a t e g o r i e si nt e r m so ft h ec o n s t r u c t i o no fo v e r l a yt o p o l o g y ：u n s t r u c t u r e dp 2 pa n d s t r u c t u r e dp 2 p , n 地s t r u c t u r e dp 2 ph a sb e c o m eam a i n s t r e a ma sar e s u l to fi t s o u t s t a n d i n gc a p a b i l i t yo f a l a b m 哪 p 2 p r o u t i n gi sak e yi s s u ei np 2 p , a f t e ra ni n - d e p t hr e s e a r c ho nt h ec h o r dp r o t o c o l ， w ef i n dt h a tt h e r ea r et w os e r i o u sf l a w sw h i c ha l el o n gd e l a yc a u s e db yt h es e p a r a t i o n b e t w e e nl o g i c a lt o p o l o g ya n dl o g i c a lt o p o l o g ya n di n e f f i c i e n tr o u t i n gt o g e t h e rw i t h t o om a n yo v e r h e a d sr e s u l t e df r o mc h u mp r o b l e m t h er e s e a r c hi nm yp a p e rm a i n l y i m p r o v e dt h eo r i g i n a la l g o r i t h m si nt w oa s p e c t s ： i nt h ep r o c e d u r eo fm u t i n g , s i n c et h eo r i g i n a lr o u t i n ga l g o d t h r u so n l yt h i n k a b o u tt h el o g i cd i s t a n c ec o m b i n a t i o nw i t ha n a l y s i so ft h et r a i to ff i n g e rt a b l e t h ec o v e r a g em a yn o ta c h i e v et h eg r e a t e s td i s t a n c ew h e ni ti st r a n s m i t t e dt ot h e n e x th o pa l o n gt h ec h o r dr i n gi nac l o c k w i s ea n du n i d i r e c t i o n a lw a y , s ow e e x t e n dt h ei o 砸i 培t a b l e si ns u p p o r to fa p p r o a c h i n gt h eo b j e c tb i d i r e c t i o n a lb y a d d i n gar f i n g e rt a b l e , b e s i d e sw ep u tf o r w a r dt h ec o n c e p to ft h em e t r i co f t h e n e x th o pw h i c hl e v e r a g e * t h el o g i c a ld i s t a n c ea n dt h ep h y s i c a ld i s t a n c em a d t h e nd e 丘n ei t sm a t h e m a t i cm o d e la sar e s u l t , w ec o u l dc h o o s et h eo p t i m a ln e x t h o pi nb o n it a b l e s i nt h ep r o c e d u r eo fd y n a m i cm a i n t e n a n c e ，n o d em u s te x e c u t et h ef u n c t i o no f f i x f i n g e r s op e r i o d i c a l l yw h i c hl e a d st om a n yo v e r h e a d s ，w ec o n s t r u c ta t w o - t i e rc h o r dv i ah e t e r o g e n e i t yo fo n l i n et i m e , w h e nn o d ej o i n so rd i s a b l e s , t h es t a b l ef i x - c h o r dc o u l dd e t e c ti ta n dt r i g g e rt h ea f f e c t e dn e d e st ou p d a t et l l e i r r o u t i n gt a b l e s ，o b v i o u s l y , t h en o d e sc o r r e c tt h e i fr o u t i n gt a b l e sf r o ma c t i v e l yt o 中山大学硕士学位论文c h o r d - b a s e dp 2 p 网络路由定位策略研究 p a s s i v e l y , w h i c hr e d u c e st h eo v e r h e a d sg r e a t l y f i n a l l y , w eu s et h eo v e r l a ys i m u l a t o rp 2 p s i mt op r o v et h er a t i o n a l i t yo ft h e i m p r o v e da l g o r i t h m s ；w ec o u l ds o et h a tt h en u m b e ro fr o u t i n gh o p ，t h er o u t i n gd e l a y , t h ef a i l u r er a t ea n ds y s t e mo v e r h e a da r em u c hb e t t e rt h a nt h eo r i g i n a lc h o r dt h r o u g h t h ee x p e r i m e n t a lr e s u l t k e y w o r d ：t h em e t r i co f n e x th o p ，h e t e r o g e n e i t y ，t w 0 4 i e rc h o r d ，p 2 p s i m u i 中山大学硕士学位论文 c h o r d - b a s e d p 2 p 网络路由定位策略研究 1 1 引言 第1 章绪论 当前，互联网最普遍的计算模型是c l i e n t s e r v e r ( c s ) 模型，在这种集中式的 体系结构中，客户机请求服务，服务器提供内容服务并响应客户机请求，在整个 系统中，服务器是中心节点，随着互联网用户数量的激增，客户端交多，使服务 器的压力相应的增加，它将成为计算的瓶颈和网络带宽的瓶颈，从而导致系统的 瘫痪，其次它也容易成为黑客等恶意破坏者进行拒绝服务攻击的目标，安全成为 一个隐患点，这对高可靠的系统来说也一个致命的打击；同时对于一些热门网站， 会造成网络流量的汇聚现象，引起局部区域内的网络负载不平衡；另外c 幅模式 的覆盖面比较狭窄，即使借助强大的搜索引擎也难以到达网络的边缘。 如何消除c s 这种计算模式自身的限制，网络研究者们将视线转移到了p 2 p 新的应用模式。首开p 2 p 之风的当属u cb e r k e l e y 大学最著名的s e t i h o m e 1 】 研究计划，1 9 9 9 年s e t i h o m e 开始使用p 2 p 共享计算方法来分析星际间无线 信号，寻找宇宙中的可能存在的其他外星文明的证据，它将分布式于世界各地的 2 0 0 多万台个人电脑组成的计算机阵列，项目组称，在不到两年的时间里，这种 计算方法已经完成了单台计算机3 4 万多年的计算量；2 0 0 0 年用于共享m p 3 的 软件n a p s t e r 【2 j 在不到一年的时间内吸引了数以万计的用户，随后各种p 2 p 的应 用层出不穷，大家熟悉的b i t t o r r e n t ，e m u l e ，f a s t t r a e k ，f r e e n e t 等等都是p 2 p 在文件共享领域的良好范例。同时它在即时通信、b i p 、在线游戏，分布式存储 系统、流媒体、域名系统、w e b c a c h e 、应用层组播、搜索引擎、协同工作领域 内广泛应用，据统计现有网络中有超过7 0 以上的流量被p 2 p 通信占据着，故 p 2 p 技术逐渐成为国际计算机网络技术领域的一个研究的热点，并且还被财富 杂志誉为改变互联网未来的四大新技术之一【3 】。 在p 2 p 网络的各种应用中，它弱化或者摈弃了服务器的概念，系统中各个 节点不在区分服务器和客户机的角色，所有节点是对等的，不存在c s 模式中的 服务器专门提供资源发现服务的角色，因此如何高效可靠的实现p 2 p 网中资源 中山大学硕士学位论文c h o r d - b e dp 2 p 网络路由定位策略研究 的路由查找无疑是对等网必须解决的核心问题之一。 1 2 研究现状 现有的p 2 p 路由查找算法研究经历了以下发展过程：以n a p s t e r 为典型代表 的集中索引非结构化路由查找算法，以g n u t e l l a l 4 1 为代表的分布式非结构化洪泛 路由查找算法，以k a z a a ( 习为代表的混合式非结构化路由查找算法，以c h o r d t 6 1 t 7 1 为代表的基于d h t 的结构化分布式路由查找算法。由于分布式的路由查找算法 消除了中心索引服务器的存在，解决了单点故障问题，而基于d h t 的结构化分 布式路由查找算法又克服非结构化分布式洪泛路由查找引起的网络拥塞的弊病， 解决了p 2 p 网络可扩展性的问题，适应于大规模对等网的应用，因此结构化p 2 p 成为对等研究和应用的主流和热点。 目前最新的研究成果大都是基于d h t ( d i s t r i b u t e dh a s ht a b l e ) 的分布式路 由查找算法，它具有扩展性好、路有效率高、自适应强等特点，其中著名d h t 路由算法包括：p a s t r 9 1 2 1 、c a n t h i 、t a p e s t r y _ 【1 7 1 、c h o r d 。四者当中，c h o r d 具 有相对的结构简单、路由查找速度快、负载均衡与健壮性好等优点而备受关注， 故本文研究课题为c h o r d 路由算法。 m 1 t 提出的c h o r d 把所有的节点通过相容哈希( c o n s i s t e n th 懿i i l g ) 映射为一 个n l 位的二进制标识i d ，节点按照顺时针升序排序构成一个环。资源同样也被 映射为一个资源标识i d ，均匀的分布在环中节点上，环中每个节点维护一个 f i n g e r i 表( i 【1 ，m 】) ，资源的p 2 p 路由查找是通过f i n g e r 表来进行下一跳转发来实 现的，通过分析可以发现c h o r d 路由查找的过程近似于一个二分搜索的过程。由 于p 2 p 节点的动态性，各节点需要一个动态维护的过程来保证f i n g e r 表的正确性。 由于终端节点通过哈希函数映射到统一的逻辑空间，节点实际物理拓扑位置 信息丢失，造成同自治域内节点标识d 相去甚远，使得路由查询时延大，这成 为了结构化p 2 p 的一大缺陷。 为此，研究者们使用基于局部兴趣度的邻近度路f t ( p r o x i m i t y r o u t i n g ) 技术来 减少路由查找时延，如在拓扑感知t a c h o r d 3 川方案中，节点增加r o u t i n g t a b l e ( 物 理拓扑邻居表) 和l o c a ln o d et a b l e ( 本地节点表) 两个表来进行邻近路由选择，文 献 8 】提出了基于位置信息的节点d 方案，将节点的位置如所处的州、市等信息 2 中山大学硕士学位论文 c h o r d - b a s e lp 2 p 网络路由定位策略研究 体现在节点d 中，h z h a n g 等人针对c h o r d 提出了l p r s l 2 3 l ( 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 ) 的邻近路由选择技术。在原c h o r d 中的n f i n g e r i ，它为n + 2 的后继节点，而在l p r s 中丘i l g c r i 】被修改为在【i l 斗_ 2 l - 1 皿趔) 内物理拓扑距离距节 点n 最近的节点d ，故在p 2 p 路由中每次选择物理距离最近的下一跳进行转发 来改善路由查找时延。但是采用p r 技术在结构化p 2 p 的动态维护阶段中需要增 加了较大的开销。 1 3 作者的研究工作 本论文致力于提高结构化c h o r d 网的p 2 p 路由的平均路由跳数、路由延时、 抗“扰动”能力、网络开销等性能问题，主要研究内容如下： a ) 研究了p 2 p 的概念、优缺点、基于拓扑构造的p 2 p 分类及其p 2 p 路由机 制，重点研究了基于d h t 的结构化路由算法。 b ) 在重点研究c h o r d 的基础上，分析了原算法两大缺陷： 路由查找阶段，基于f i n g e r 表的单向路由转发逼近所覆盖距离不一定 最大，平均路由跳数欠佳，且原算法仅考虑逻辑距离，路由时延大； 动态维护阶段，各节点周期性执行f i x f i n g e r s 0 修复f i n g e r 表，加上“扰 动”现象，网络开销大，而事实上一个节点加入或退出平均只需要 0 0 0 9 n ) + 节点更新f i n g e r 表 c ) l 是出了改进的i c h o r d 算法，在算法第一个阶段，通过扩展路由表，支持双 向路由逼近，同时设计了下一跳度量值，综合考虑物理距离与逻辑距离，实现最 佳下一跳路由；在算法第二个阶段，利用节点在线时间的异构性构造双层c h o r d ， 把f i x f i n g e r s 0 过程转移到相对稳定的f i x - c h o r d 中，n o r m a l - c h o r d 中节点路由表更 新由主动方式转变为被动方式，从而增加系统的抗扰动；【降低网络开销。 d ) 采用覆盖网仿真工具p 2 p s i m 进行仿真实验，对比了i c h o r d 算法与c h o r d 算法实验效果，证验证了算法的合理性。 1 4 论文的结构 第一章：绪论概述论文研究背景及目前的研究现状。 第二章：p 2 p 与c h o r d 技术背景，介绍了p 2 p 定义、特点与应用的背景知识， 中山大学硕士学位论文 c h o r d - b a s e dp 2 p 网络路由定位策略研究 然后论述了非结构化与结构化p 2 p 的拓扑模型及其路由查找的机制，重点阐述 了c h o r d 算法。 第三章：改进了c h o r d 路由查找算法，首先分析了现有c h o r d 在平均路由跳 数和延时方面的缺陷，随后确定f i n g e r 表中最接近目标节点的f i n g e r i ，最后对节 点在线时间异构性进行了详细的分析。最后设计了基于双层c h o r d 的i c h o r d 算法， 第四章：仿真实验，介绍了网络仿真与覆盖网仿真的区别，随后阐述了 p 2 p s i m 主要框架，重点是如何扩展p 2 p s i m ，实现改进算法的仿真实验，最后对 比分析了c h o r d 与i c h o r d 在四个性能指标方面的开销。 第五章：总结与展望，总结了所作的工作与进一步需要解决的问题。 4 中山大学硕士学位论文 c h o r d - b a s e dp 2 p 网络路由定位策略研究 2 1p 2 p 概述 第2 章p 2 p 与c h o r d 技术背景 2 1 1p 2 p 定义 p 2 p 是p e e r - t o - p e e r 的缩写，中文译名是对等网或对等计算，目前计算机 学术界和工业界还没有一个统一的定义，常见的定义如下： 定义一f 9 】：i n t e lp 2 p 工作组指出p 2 p 是一种分布式网络，网络的参与者共 享他们的所拥有的部分硬件资源，诸如，c p u 计算能力、存储空间能力、网络连 接能力、打印机能力，这些共享资源需要由网络提供服务和内容，无需经过任何 中间节点，能被其他对等节点访问到，在此网络中的参与者既是资源的提供者。 又是资源的参与者。 定义二【l o l ：惠普p a l oa l t o 实验室提出的p 2 p 是无中心的方式利用分布式 的资源完成关键任务的系统。 定义三：i b m 赋予了p 2 p 系统更广阔的定义，它由若干互相协作的计算机构 成，系统依存于边缘化设备的主动协作，每个成员是从其他成员而不是从服务器 的参与中收益，系统中的用户能够意识到彼此的存在，构成一个虚拟的或实际的 群体。 尽管还有很多表述，但是他们共同点就是打破了传统的c s 模式，网络中的 每个节点都是对等的，无服务器和客户机之分，每个节点扮演着两种角色，既充 当服务器，为其他节点提供服务，又享有其他节点的服务，实现了客户机的功能， 可见，p 2 p 网络的核心特征是分布性、对等性、自治性。 2 i 2p 2 p 优缺点 目前互联网广泛使用集中式，层次式的拓扑结构，由于p 2 p 技术的发展，互 联网的存储模式将有目前“内容位于中心”的模式转变成“内容位于边缘”模式。 与传统c s 模式比较，p 2 p 明显具有如下优点：a ) 去中心点，避免了网络瓶颈， 5 中山大学硕士学位论文 c h o r d - b e dp 2 p 网络路由定位策略研究 提高网络的鲁棒性和可扩展性；b ) 鲁棒性，节点的分散、对等特性，部分节点或 网络的失效对其他影响较小，有效克服单故障问题；c ) 可扩展性，随着用户的增 加，系统资源和服务增加；d ) 负载均衡，无中心服务器，网络带宽充分利用，流 量分布较均匀，e ) 高性价比，服务器特别是超级计算机的软硬件的成本和其维护 费用还是比较昂贵的，而采用p 2 p 架构可以以更低的成本有效利用互联网中闲置 大量的普通节点，将计算任务和存储任务分布到所有节点上，利用其计算能力和 存储空间，达到高性能计算和海量存储的目的。 同时p 2 p 又面临着很多在传统的c s 模式模式中没有的问题【1 0 1 ： 节点动态性高，节点在进入系统，查找并获得资源，到离开系统这一过程中 通常时间不是很长，故节点高动态性使得维护数据可用性的工作变的困难： 节点异构性强，p 2 p 系统的节点，如普通p c ，p d a ，c e l l ，s e r v e r 等，在计算 能力，存贮能力，带宽能力等方面差异大，可能造成部分节点的瓶颈 节点具有自私性，即搭便车问题，试验表明g n u t e l l a 中有2 5 的节点从不共 享数据，只从别人那里下载数据，因而如何激励用户多贡献自己的资源，保 证交换的公平性受到很多研究者关注 节点不互信，p 2 p 节点来自不同的组织，节点之间天然没有信任感，因而安 全和隐私保密工作十分重要。 2 1 3p 2 p 应用现状 p 2 p 技术因具有诸多无可比拟的优势，具有广阔的前景，按照具体的应用的 不用，可分为以下类型： 分布式计算，这类应用研究采用并行技术和分布式技术把网络中的计算单元 和存储单元充分利用起来，完成只有超级计算机才能完成的大规模计算任 务，如天气预报，基因组的研究等，目前这类研究的代表有s e t i h o m e 。 文件交换，n a p s t e r 的i d p 3 文件交换应用引发了网络的p 2 p 技术革命，现在 网上最普遍最成熟的文件交换应用软件有b i t t o r r e n t ，e m u l e ，迅雷，m a z e ， 揭开了丰富的p 2 p 文件资源 协同工作它是指使用p 2 p 技术建立一个安全，虚拟的协同应用平台来完成 共享信息资源、完成计算任务，如协同协作，共享白板，g r o o v e 是知名的协 6 中山大学硕士学位论文 c h o r d - b a s e dp 2 p 网络路由定位策略研究 作工作平台 分布式存储传统的局域网范围内的分布式存储系统和分布式数据库可以借 助于p 2 p 技术拓展成广域网内的分布式存储系统和数据库。 2 2p 2 p 分类及其路由查找机制 现有p 2 p 根据覆盖网拓扑关系与集中化程度细分为四类：分布式结构化p 2 p 、 分布式非结构化p 2 p ，集中式非结构化p 2 p 与混合式非结构化p 2 p 。 2 2 1 集中式非结构化拓扑及路由查找机制 在以n a p s t e r ( 如图2 1 ) 为代表的中心拓扑p 2 p 中，文件共享服务使用一台 大型中心服务器，也称为目录服务器，运行在对等方中的应用程序将其m 地址 及本地磁盘上可供共享所有文件的元数据信息( 文件目录的索引) 通知目录服务 器，目录服务器从每个活动的对等方收集这些信息，建立一个一个集中索引的动 态的数据库，提供文件索引到i p 地址集合的映射，为了保证它的数据库信息是 最新的，跟踪对方是否在线的一种办法是周期性的向对方法发送报文，看他们是 否响应，如果确定对等方断开连接，这索引服务器从它的数据库中删除该对等方 的m 地址。它与c s 最大的区别是数据资料存储在各个节点中，而不是中心服 务器上，其最大的优点就是易于实现和资源查找效率高，客户只要将查找请求发 给中心即可并且可以支持多关键字和模糊查询，但它不是彻底的p 2 p 网，资源 定位内容的过程是高度集中的，容易形成热点，发生单点故障，系统的可扩展性 受到了制约，同时涉及到版权等法律问题。 n a t m w o o m t 目t m r q 嗍 固蝴r 岬 df i gd o w n l o a d 图2 一ln a p s t e r 系统结构 乍 中山大学硕士学位论文 c h o r d - b a s e dp 2 p 网络路由定位策略研究 2 2 2 分布式非结构化拓扑及路由查找机制 分布式非结构p 2 p 典型案例是g n u t e u a ( 如图2 一1 ) ，它是一个纯粹的p 2 p 系 统，解决了n a p s t e r 存在的一些问题，它没有目录服务器协助活动，节点以随机 图方式加入网络组织成覆盖网，节点度数服从幂律规律，该方式能够较快的发现 目标节点，在动态的网络环境中有着较好的容错能力，支持多关键字和复杂的模 糊查询，在该网中，各个节点维护一个记录所有邻居节点的路由表，它采用洪泛 ( f l o o d i n g ) 发现和随机转发( r a n d o mw a l k e r ) 或有选择的机制搜索网络资源，它实 质上就是图的广度优先搜索，其查找算法的具体步骤如下 1 1 j ： 节点发送一个p i n g 消息给它直接相连的任何节点，相连节点发送p o n g 消息 响应，表示它的加入，并同时洪泛p i n g 消息给它的邻居，p o n g 消息只沿进 入的p i n g 消息路径发送，即一个节点收到一个d e s c r i f i t o r _ i d i 的p o n g 消息， 却没有收到d e s c r i p t o r _ i d = i 的p i n g 消息，则p o n g 消息从网络中删除，该方 法用来避免检测和丢弃重复的消息，避免环路。 查找文件的节点随机的给一个节点发送q u e r y 消息，每个接受到的q u e r y 消 息的节点洪泛至所有的邻居，同时为了限制广播风暴，采用t t l 来控制路 由的转发的跳数，每转发一次，t t l 减一，如为零，则丢弃消息，一旦发现 q u e r y 匹配的搜索数据，发送q u e r y h i t 返回，同理，q u e r y h i t 仅沿着转发输 入的q u e r y 路径发送。 随着网络规模的扩大，这种洪泛广播定位资源的方法，将导致指数级的网络 流量，导致严重的网络拥塞，系统的性能急降，因而g n u t e l l a 的可扩展性不好， 适合规模比较小的网络，不适合大规模的p 2 p ，加之没有确定拓扑结构的支持， 它无法保证资源发现的效率。分布式非结构化的另一种典型代表为f r e e n e t 与 g n u t e l l a 的主要区别是基于深度优先的图搜索。当然该p 2 p 的覆盖网是一个完全 的随机图，整个系统具有较高的容错性，节点频繁的加入和退出对系统的影响小。 8 中山大学硕士学位论文c h o r d - b a s e d p 2 p 网络路由定位策略研究 畔q 删 r 阳印。黼 of b 幽嘲t 翻u t e l l a 图2 2g - n u t e l l a 系统结构 2 2 3 混合式非结构化拓扑及路由查找机制 混合式p 2 p 在分布式拓扑的基础上引入了超级节点的概念，综合了集中式 p 2 p 快速查找与分布式p 2 p 去中心化的优点，混合式p 2 p 考虑了网络中节点异构 性( 即网络中的节点在运算能力，存储能力，带宽等方面有差异) ，利用数据的局 部性原理或s m a l lw o r l d 原理，将网络节点分为超级节点与普通节点，选择性能 高的节点作为超级节点，超级节点成为地理邻近中其他普通节点的索引服务器， 即成为簇，簇内的普通节点使用类似于n a p s t e r 的集中式目录查找算法，在查询 失败的情况下，在转发到超级节点进行查询。整个p 2 p 中性能更优的超节点可 以在成簇，从而构造一种分层的簇结构，最后超级节点采用随即图的方式构造 g n u t e l l a 的结构，超级节点间使用泛洪查找算法。该p 2 p 网络成功应用代表为 k a z a a ，截至2 0 0 3 年8 月3 0 日，a z a a 拥有四百五十万用户，七千兆字节的 共享数据。 2 2 4 分布式结构化拓扑及基于d h t 的路由查找机制1 1 s l 为了克服非结构化中存在的两大重大的缺陷，学术界把研究的焦点转向了结 构化的p 2 p 网络，它通常用于内容寻址的应用中，具体的工作机制是：在p 2 p 网络 中他由一个唯一的标识( 如主机名、p 地址存放信息的哈希值) ，节点加入网时按 照已经约定的互联准则找到相应的位置，在与位置相邻的建立连接关系，所以它 的覆盖网拓扑结构是严格控制的，资源不是随机分布存储在节点上，而是使用一 种使查询更加高效的的机制来存储的。最新的研究成果采用分布式哈希h d 构 9 中山大学硕士学位论文c h o r d b a s e d p 2 p 网络路由定位策略研究 建的分布式查找算法，分布式哈希表实际上是一个由广域氛围内大量节点公共维 护的巨大散列表。散列表被分割成不连续的块，每个节点被分配给一个属于自己 散列空间，成为这个空间的管理者。在d h t 由于采用哈希表分片策略不同，结 构型p 2 p 网络形成了不同的网络拓扑形状，目前主要有三类：环状结构，如c h o r d 、 p 船耐1 2 】：树形结构，如t a p e s t r y i ”】；多维立方体结构，如内容访问网络【1 4 j ( c a n ，c o n t e n ta d d r c s s a b l en e t w o r k ) 。 2 2 4 1p a s t r y p a s t r y 是微软研究院和r i c o 大学共同提出的可扩展的分布式路由的p 2 p 系 统，其中每个节点( 其口地址或者公钥) 通过哈希函数映射为一个1 2 8 位的节点号， 用于在节点环状空间中标识节点位置，节点号是在节点加入系统时随机均匀分布 的，给定任一消息及其关键字，节点可以将消息路由到节点号最接近关键字的那 个节点。系统中节点号d 和关键字d 是以b = 2 b 为基的数。 p a s t r y 中每个节点维护一个叶子节点集合，一个邻居节点集合和一张路由 表。路由表每行( 从第0 行开始) 包括l o g b n ( n 为空间大小) 上取整行组成， 每行 包括b 1 个表项，第i 行所有列与当前节点号的前i 个数位相同，且当前节点与 第i 行所有项的第i + 1 位取遍o b 1 ，例如，图2 3 ，b = 2 ，当前节点i d = 1 0 2 3 3 1 0 2 ，第3 行都有相同的3 位前缀1 0 2 ，阴影部分表示当前结点共同前缀下 一位相对应的位；叶子节点集表示和当前节点数值上最接近的节点集，其中一半 大于当前节点值，一半小于当前节点值；由于网络物理拓扑和逻辑拓扑不一致， 邻居节点集存放的是距离当前结点物理拓扑距离近的节点集，用作路由的启发式 搜索，来减少路由查找的时延。 p a s t r y 路由查找过程如下： a )收到一条查询消息，检查关键字d 是否位于叶子集合中，如果是， 转发给对应节点m ，否则转b ) ； b )从路由表中选择一个比现有节点d 具有更多共同前缀的节点d ，查 询转发给该节点，并转a ) ，如果对应路由表项为空或者该节点d 不可达，则转c ) ： c )在叶子集中，转发给前缀长度相同但数值更接近关键字的节点d ，并 中山大学硕士学位论文c h o r d o b a s c dp 2 p 网络路由定位策略研究 转a ) 。 依次进行，直到找到目的节点，显然路由每一步比上一步向目标至少迈 进一步，路由过程是收敛的，其路由跳数为o ( 1 0 9 。n ) 关于节点的加入和 推出具体的算法参考 1 2 1 。 2 2 4 2t a p e s t r y 图2 3p a s m j 节点的数据结构 t a p e s t r y 是u cb e k e l e yo c e a n s t o r e t l 7 】项目组设计，提供一个大规模分布式可 容错的路由定位基础架构，在此基础上可以开发各种p 2 p 的应用，它基于 p l a x t o n 1 6 】搜索定位和路由技术，复用了p l a x t o n 提出的一种分布式数据结构一 p l a x t o n - m e s h ( 图2 - 4 0 , ) ) ，这种结构中，关键字和和节点号和它们的位置和具体的 内容无关，通过s h a - 1 哈希运算映射为m 位的二进制值，用固定的数值b 为基 的位串表示，均匀分布在整个散列空间中。 t a p e s t r y 中每个节点维护一个路由表( 邻居映射表) ，方向指针列表，和对象 定位指针等。路由表把消息按照目的地址从右到左一位一位的向前匹配，如图 2 - 4 ( a ) 所示，+ 8 - ：一+ 9 8 * 5 9 8 - 4 5 9 8 ，这种方式类似于疋分组转发过程中的最 长前缀匹配。路由表分多个层，它的层数为节点标识的长度1 0 9 ，路由表第 i 层节点标识号的后i 1 位与本节点标识号后的i 1 相同，如图2 - 4 ( b ) 所示，每层 共有b 项，每层的数值遍布o b 1 。t a p e s t r y 中，方向指针列表指向把自己作为 邻居的那些节点，在节点加入时，用来辅助构造自己的路由表；对象位置指针采 中山大学硕士学位论文 c 1 1 0 r d b 躯c dp 2 p 网络路由定位策略研究 用拓扑形式 ，用于在对象向服务器发送路由请求时提供帮助； 热点监视信息就是路由查找结果的一些缓存。 t a p e s t r y 路由查找的算法：节点将路由消息采用后缀匹配进位增加的方式， 即当前节点计算自己的d 和目的d 的相同后缀数目n ，然后在n + 1 层选择一中 间节点进行转发，它与目的d 同后缀数至少n + l ，如果系统中右多个节点标识 符满足路由表某一条件，则选择延迟最小的节点，使得物理拓扑和逻辑拓扑取得 一定的吻合，这个过程递归进行，直到查找成功。路由跳数最多l o g 。t a p e s t r y 、 p a s t r y 思想都继承自p l a x t o n ，在路由定位机制上都是基于标识符匹配进行路由， 仅路由表结构和维护及节点加入和离开算法不同。 一、 溯。厶、 旃由豪豹黎弦 姗日啦蝴 ，、 蛾斓翮椰 f v 一u 一稻稳触_ 砬m 正 罱o 笱- u 黾曼乏 ( a ) 节点路由过程 ( b ) 节点0 6 4 2 的路由表 图2 4t a p e s t r y 架构 2 2 4 3c a n c 鲥的设计思想是构造一个虚拟的d 维笛卡尔坐标空间，整个坐标空间动 态地分布给系统中所有的节点，每个节点分别根据其口地址由哈希函数映射到 空间中独立的互不相交的一个区域，图2 - 5 ( a ) 给出了一个【0 ，1 x 【0 ，l 】坐标空 间划为成5 个节点区域的情况。每个资源使用统一的哈希函数映射到坐标空间某 一节点负责的区域中。在d 维坐标空间中，两个节点互为邻接点定义为：它们维 护的区域只有一维相互邻接，而其余的d _ 1 维上相等。图2 5 ( a ) 中，a 与b ，c 互为邻接点，与d 就不是邻接点。c a n 中每个节点维护一个路由表，由于坐标 空间是d 维的，路由表有2 d 个邻接点表项。 c a n 的路由查找算法非常简单，知道目标结点坐标后，朝着目标结点方向 气剜“ 誓 中山大学硕士学位论文 c h o r d - b a s e dp 2 p 网络路由定位策略研究 就将请求转发给自己的邻接点就可以了，c a n 的可扩展性很好，节点数目的增 加，每个节点只需维护2 d 个邻接点表项，同时c a n 的容错性很好，两点问有 许多路径。c a b l 的平均路由跳数为( 舭) ( n 1 ，d ) 。节点加入和退出，由相关节点负 责的区间进行拆分和合并，具体参考 1 4 】。 捧 筏氛善l l 鹰 。：。：曩：r 撇蚋一；l 。 l - - i - - ： 触鼻姻：秘l 鱼她拜 糊瓤钏辟 a ) 二维笛卡尔坐标空间b ) c a n 路由查找 图2 5c a n 架构 2 2 4 4c h o r d c h o r d 是m i t 提出的一个p 2 p 分布式资源发现服务的协议，给定一个关键 字，c h o r d 就可以有效的把关键字映射到网络中的某个节点，c h o r d 的突出优点 是算法简约，路由表只须维护l 0 9 2 n 长度的路由表，查找性能优于c a n ，节点 加入和离开开销都优于t a p e s t r y 和p a s t r y ，详细情况见2 3 节c h o r d 协议。 2 3c h o r d 协议嘲 c h o r d 协议为高效的定位资源问题提供了一种新的方法，阐述了怎样将给定 的关键字映射到某个节点，构造一维环形的拓扑结构，怎样构造路由表，使节点 存贮空间和算法的时间复杂度得到一个很好的折衷，怎样定位资源的存储位置， 节点如何加入系统，如何退出系统，节点失效如何处理：与其他结构化p 2 p 协 议相比，c h o r d 协议直观，可确保的性能和准确性。 2 3 1 拓扑构造 c h o r d 协议使用s h a - 1 1 9 1 ( 美国国家标准与技术研究所1 9 9 5 年公布的哈希散 1 3 中山大学硕士学位论文c h o r d - b a s e d p 2 p 网络路由定位策略研究 列函数标准) 作为相容哈希函数来为每个节点和关键字分配一个m 位的二进制 标识符d ，标识符长度m ，必须足够长，这样可保证两节点或关键字哈希到同 一个标识符上概率小到可以忽略。节点i d ( 用n i d 表示) 一般使用节点的p 地址或 者在加上端口号哈希运算出，关键字i d ( 用k i d 表示) 通过资源名称哈希运算出， m 值域范围为【o ，2 m - 1 】。并且将从0 到2 m - l 的数排列成一个圆圈，称为c h o r d 环。 在相容哈希中，每个关键字k 保存在它的后继节点s u c c e s s o r ( k ) q 。，后继节 点是关键字大于或等于关键字k 的第一个节点，在c h o r d 环中就是顺时针方向从 k 数起的第一个节点；由于对关键字集合中的任一关键字，经哈希函数映射到地 址集合中任何一个地址是等概率的，即在p 2 p 结构化网络中，映射值k 甜均匀的 分布在所有的节点中，使c h o r d 协议具有自然的负载均衡性，当第n 个节点加 入或者离开网络时，只有1 n 的关键字需要移动到另外的节点上，言下之意就是 当节点加入或者离开网络时给c h o r d 网带来的冲击达到最小，为保持相容哈希映 射，当节点n 加入网络时，原来分配给n 的后继的关键字且其值大于或等于n 将分配给n ，当节点n 离开网络时，原来给n 的关键字将分配给s u c c e s s o r ( n ) 。 图2 - 6 是一个m = 6 的c h o r d 环，具有7 个关键字和l o 个节点，n 5 6 是c h o r d 环中k 5 4 顺时针方向数起的第一个节点，所以s u c c e s s o r ( k 5 4 ) = n 5 6 ，关键字k 5 4 代表的资源对象存贮在n 5 6 节点中，当n 5 6 实效时，k 5 4 将分配给它的n i ；当 ， n 5 5 节点加入时，k 5 4 将分配给n 5 5 。 图2 6 c