（通信与信息系统专业论文）chord网络模型的研究和改进.pdf

i i iiiii tir i rl firi iiil y 17 5 9 6 4 7 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均己在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 。 本人签名： 酗胆毋1 1 日期：2 皇 曼：墨：! 兰 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人签名： 翅毽囱! l 同期：2 壁l 殳：苎，! 互 导师签名：j 秀卜彳卜 日期：麦寸扣_ 铲 c h o r d 网络模型的研究与改进 摘要 随着p 2 p ( p e e r - t o p e e r ) 技术的网络应用迅速发展，p 2 p 技术也受 到越来越多的关注。近期，基于分布式哈希表( d h t ) 技术的结构化 p 2 p 网络逐渐成为p 2 p 技术的研究重点。作为结构化p 2 p 网络的典型 代表，由m i t 提出的c h o r d 网络模型具有良好的可验证性、可扩展 性及负载平衡性等特点。但是由于节点异构性、动态节点造成的大量 的扰动以及有限的查询效率，c h o r d 模型并没有在实际中广泛应用。 为了解决这几个方面的问题，本文在c h o r d 的基础上提出了一种 改进算法h t c c h o r d ( t o p i c c l u s t e ra n dh i e r a r c h i cl a y e rb a s e d c h o r dm o d e l ) 。h t c 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 网络。大部分的查询和节点的动态调整都会发生在簇内。这样 就减少了资源定位的开销，也减少了节点加入和离开时对系统造成的 扰动。部分的簇间查找借助于高性能的节点组成的上层c h o r d 网络完 成，也充分发挥了节点的作用。 在详细介绍了h t c c h o r d 的体系结构和实现方式之后，本文通 过理论分析和仿真实验两种方法，从查询效率和抗干扰能力两方面对 两个模型进行了对比分析。结果显示h t c c h o r d 在这些方面均有所 提高。 关键词：对等网络c h o r d 分簇层次式 i 己e s e a r c ha n di m p r o v e m e n t o fc h o r dm o d e l a b s t r a c t 晰t ht h e p 2 p ( p e e r - t o p e e r ) t e c h n o l o g yw i d e l yu s e d i ni n t e m e t a p p l i c a t i o n ，p 2 pt e c h n o l o g yi sa t t r a c t i n gm o r ea n dm o r ea t t e n t i o n r e c e n t l y , t h es t r u c t u r e dp 2 pn e t w o r kb a s e do nd h t ( d i s t r i b u t e dh a s ht a b l e ) h a s b e c o m er e s e a r c hf o c u s a sac l a s s i c a ls t r u c t u r e dp 2 pn e t w o r k , c h o r dm o d e l p r o p o s e db ym i th a sm a n ya d v a n t a g e ss u c ha sd e c e n t r a l i z a t i o n ，s c a l a b i l i t y , l o a db a l a n c e h o w e v e r , d u et ot h eh e t e r o g e n e i t yo fn o d e s s om u c hc h u m c a u s e db yd y n a m i cn o d e sa n dt h el i m i t e de f f i c i e n c yo ft h eq u e r y , c h o r d m o d e li sn o tw i d e l yu s e di np r a c t i c e i no r d e rt od e a lw i t ht h e s ep r o b l e m s ah t c c h o r d ( t o p i c c l u s t e ra n d h i e r a r c h i cl a y e rb a s e dc h o r dm o d e l ) i sp r o p o s e di nt h i sp a p e r c o m p a r e d w i t ho r i g i n a lc h o r dm o d e l ，t w oc o r ec o n c e p t sa r ei n t e g r a t e di n t ot h es y s t e m a r c h i t e c t u r e ：t o p i c - c l u s t e r a n dh i e r a r c h i c l a y e r ，c h a n g i n gc h o r di n t o a t w o d i m e n s i o n a ls t r u c t u r ew i t hu p p e ra n dl o w e rl e v e l s i nt h em o d e l t h e n o d e sa r ed i v i d e di n t od i f f e r e n tc l u s t e r sa c c o r d i n gt h e i ri n t e r e s t s w h i c ha r e o r g a n i z e di n t ol o w e rc h o r dn e t w o r k a tt h es a m et i m e a st h er e p r e s e n to ft h e c l u s t e rt h en o d e sw i t ht h eb e s tp e r f o r m a n c ei nt h ec l u s t e rc o m p o s e do ft h e u p p e rc h o r dn e t w o r k m o s tq u e r i e sa n dd y n a m i ca d j u s t m e n tw i l lo c c u rw i t h i n t h el o w e rc h o r dn e t w o r k , w h i c hr e d u c et h ec o s to fq u e r ya n dt h ec h u m a r o u s e db yt h ea d d i n ga n dd e p a r t m e n to ft h en o d e s a n dt h ei n t e r - c l u s t e r q u e r i e sa r er e s o l v e db yt h eu p p e rc h o r dn e t w o r kc o n s i s to fh i g h - p e r f o r m a n c e n o d e s w h i c hm a k e sf u l lu s eo ft h en o d e s a f t e ri n t r o d u c i n gt h ea r c h i t e c t u r ea n dt h ei m p l e m e n t a t i o no fh t c c h o r d i nd e t a i l ，t h eq u e r ye f f i c i e n c ya n ds t a b i l i t yo ft h et w om o d e l sa r ec o m p a r e d t h r o u g ht h e o r e t i c a la n a l y s i sa n ds i m u l a t i o na n dt h er e s u l to ft w ow a y sa l s o s h o w st h a th t c c h o r dh a sb e t t e rp e r f o r m a n c e 摘要 a b s t r a c t 目录 第一章绪论 目录 l 1 1 研究背景1 1 2 国内外研究现状1 1 3 课题研究意义3 1 4 论文主要研究内容组织结构3 第二章p 2 p 网络概述。 2 1p 2 p 网络的概念5 2 2p 2 p 网络的特点及应用一5 2 3p 2 p 网络结构7 2 3 1 集中目录式网络7 2 3 2 纯分布式网络8 2 4 结构化网络模型9 2 4 1c a l 、i 9 2 4 2t a p e s t r y 10 2 4 3p a s t r y 1l 2 4 4c h o r d 1 ：； 第三章基于分类和分层的改进c h o r d 模型h t c c h o r d 2 l 3 1h t c - c h o r d 总体设计思想和结构21 3 1 1 总体设计思想2 1 3 1 2h t c c h o r d 系统结构2l 3 2 节点标识符和资源标识符2 3 3 3 节点能力评估及分类2 4 3 4 节点数据结构2 5 3 4 1 超级节点数据结构2 5 3 4 2 普通节点和备份：宵点数据据结构2 8 3 5 资源查询算法一2 9 3 5 1 查询过程2 9 3 5 2 缓存策略2 9 3 6 网络动态维护3 2 3 6 1 节点加入3 2 3 6 2 节点离开3 3 3 6 3 节点身份调整3 5 3 7 负载均衡3 5 第四章h t c c h o r d 性能分析和仿真3 8 l v 日录 4 1 性能分析3 8 4 1 1 查询效率分析3 8 4 1 2 稳定性分析4 0 4 2 仿真实验4 l 1 1 研究背景 第一章绪论 近几年来，基于p 2 p 技术的网络应用迅速发展起来。最初，以b t 、e m u l e 等为 代表的p 2 p 网络下载软件，创造了飞速下载的记录，较之以往的网络下载技术有了巨 大的飞跃。之后，以p p l i v e 等为代表的基于p 2 p 技术的网络视频应用也飞速发展起 来。许多调查显示，在英特网的流量中，有超过5 0 的流量来自于p 2 p 软件应用。 这些应用使得p 2 p 技术在普通的英特网用户中引起了极大的反响，从而为其带来了广 泛的关注。然而，p 2 p 技术的应用决不仅局限于此。研究人员认为p 2 p 技术的应用将 使网络上的资源得到充分利用和最大化的共享。p 2 p 技术在实时通信、协同工作、内 容分发以及分布式计算等多个领域得到了应用。 p 2 p 网络不同于c l i e n t s e r v e r ，b r o w s e r s e r v e r 等传统模式，它抛开了应用服务器 的束缚，使得网络中的节点以一种对等的方式共享这些节点的存储空间、处理器计算 能力、网络带宽等资源。一方面节点间可以直接进行交互，不再需要服务器作为媒介 来进行中转，从而使交流更直接，效率更高；另一方面节点不再依赖中央服务器，从 而解决了因服务器能力不足而引起的性能瓶颈问题，增强了系统的可伸缩性，同时也 避免了因中央服务器的失败而导致的整个系统无法工作的可能性，使得系统的可靠性 更强。 p 2 p 不仅仅是单一的网络技术，更是一种思想，它是具有改变整个因特网基础的 潜能的思想。虽然从纯技术角度而言，并未激发任何重大的创新，而更多的是改变了 人们对因特网的理解和认识。正是由于这个原因，有些人认为p 2 p 不是一个技术概念， 而是一个社会和经济现象。 1 2 国内外研究现状 欧美等西方国家对技术的研究势头强劲，国内研究工作处于跟进阶段。国外开展 技术研究的组织和机构主要包括大学、公司和国际学术团体。大学侧重于此领域的理 论研究，高新技术公司侧重于技术的应用开发和产品化，而国际学术团体主要从事标 c h o r d 网络模型分析与改进 准化工作。 在u cb e r k e l e y 大学，t a p e s t r y t i 】项目和o c e a n s t o r e 项目是p 2 p 技术相关项目。 t a p e s t r y 提供了一个分布式容错查询和路由基础平台。o c e a n s t o r e 是以t a p e s t r y 为平 台的适合于全球数据存储的p 2 p 应用系统。p a s t 2 】是微软研究院和r i c e 大学在2 0 0 1 年提出的完全分布式的、可扩展的、自组织的对象定位和路由算法，可用于构建大规 模的p 2 p 系统。目前微软公司已经发布了基于p a s t r y 的软件包s i m p a s t r y v i s p a s t r y 。 r i c e 大学也在此基础之上发布了f r e e p a s t r y 软件包。m i t 也开展了多个与p 2 p 相关的 研究项目：c h o r d 3 , 4 】和r o n 副。c h o r d 项目的目标是提供一个适合于p 2 p 环境的分布 式资源发现服务。r o n 项目提出了在分布式广域网中实施查询资源的系统框架。 a t & t 的c a n 【6 】项目独特之处在于采用多维标识符空间来实现分布式哈希算法。 2 0 0 2 年i n t e l 发布了基础n e t 架构之上的a c c e l e r a t o rk i t ( p 2 p 加速工具包) 和p 2 p 安全 a p i 软件包，从而使得微软n e t 开发人员能够迅速地建立p 2 p 安全w e b 应用程序。 s u n 公司以j a v a 技术为背景，开展了j x t a 7 】项目。j x t a 是基于j a v a 的开源p 2 p 平台。定义了一组核心业务和可选服务，在这些服务的基础上，用户可以开发各种 j x t a 平台上的p 2 p 应用。 国内一些高校、科研组织从2 0 0 3 年前后开始了研究开发工作。下面列举在国内 有影响的一些产品：北京大学网格实验室开发的“m a z e 网络文件系统“、华中科技 大学集群与网格计算实验室开发的“a n y s e e 视频直播系统”、清华大学高性能计算研 究所开发的“g r a n a r y 广域网分布式存储系统。国内商业领域最近几年也出现了很多 国产p 2 p 应用软件，其中不少具有相当的流行性，如p o c o 、o p 、p p l i v e 等。 就本文研究的重点c h o r d 模型而言，国内外学者已经从各个方面开展了一些 相关的理论研究工作。文献【8 】在网络直径和路由表长度的关系上做了理论分析，指出 了如何在二者之间求得平衡。其结论显示出，现有的p 2 p 结构化网络模型在二者之间 不能够得到最优的曲线。该文献同时提出了一个新的协议，将网络直径和路由表的长 度降低到2 1 4 ，然而查询的平均路径长度却增加了2 2 7 。f - c h o r d 9 】基于斐波那契 数列提出一系列的c h o r d 算法，其网络直径为0 7 2 1 0 n ，平均的路径长度为 0 3 9 8 l o g a n ，但是它的路由表长度达到1 4 4 l o g a n 2 。n e t w o r k a w a r e 协议可以达到较 好的查询性能，但是该协议只能应用到特定的底层网络。文献川从信息安全的角度对 c h o r d 模型的相关算法进行了研究，提出对中间转发节点藏匿消息内容及消息头的方 法来保证p 2 p 网络中信息的安全。文献【l l 】分析了网络中影响抖动的三个因素，通过 实验证明标准c h o r d 中采用的技术不能够解决类似k a z a a 1 2 】系统的抖动问题，提出采 用称之为b a m b o o 的d h t 技术来解决网络中的抖动问题。文献【l l 】就负载均衡方面进 2 第一章绪论 行了研究，用动态哈希函数代替静态哈希函数来获得更好的负载均衡。 1 3 课题研究意义 结构化网络模型具有良好的路由效率、确定性的资源查询、负载均衡、高扩展性 以及良好的容错性和自适应性等优点。目前，结构化的模型己经逐渐成为研究热点【1 3 】。 其中采用分布式哈希表( d h t ) 技术进行资源查询的c h o r d 网络模型，以它的无中心控 制、可扩展强、负载平衡、高容错和使查询具有方向性使得p 2 p 的优势更为突出。尽 管c h o r d 网络模型具有很多的优势，但其目前并没有很普遍地应用到真实的网络中， 原因主要包括以下几个方面： 1 c h o r d 是一维扁平的环状d h t 网络，网络中各节点完全对等，但现实环境中， c h o r d 网络上的节点之间存在很大差异性，有很多能力较弱的节点在c h o r d 中作为独立节点的时候，也要负责系统中大量的查询和下载工作，由于自身 资源的限制，它们必然会引起系统响应时间增加等问题，可能成为系统的瓶 颈。 2 节点频繁加入和退出造成的网络波动会极大增加维护的代价。每次节点的加 入和退出都要求做繁琐的处理，如果由于某种不可预知的原因有节点出现故 障，那么维护的代价更为高昂，所有结构化的系统不适用于高动态性的网络 环境。 3 虽然c h o r d 模型中资源查询效率控制在l 0 9 2 n 的范围内，但在大规模的p 2 p 网络中，这个数值还是比较大的，同时，查询机制没有考虑到节点之间查询 的语义共同性。查询的效率有进一步提高的需求和潜力。 为了解决以上的几个问题，提高系统的抗扰动性和查询效率，本文在c h o r d 网络 模型的基础上加入了按照节点兴趣爱好分类以及按照节点性能分层的两个概念，提出 了一种改进的c h o r d 网络模型，h t c c h o r d ( t o p i c c l u s t e ra n dh i e r a r c h i cl a y e rb a s e d c h o r dm o d e l ) 。 1 4 论文主要研究内容组织结构 本文首先对p 2 p 技术进行了探讨，其中重点研究和分析了c h o r d 网络模型。在此 基础上针对c h o r d 模型中存在的节点性能异构性、抗扰动性能差、查询没有考虑节点 的语义异构性的不足提出了一种改进的c h o r d 模型，叫做h t c c h o r d ( t o p i c c l u s t e r 3 c h o r d 网络模型分析与改进 a n dh i e r a r c h i cl a y e rb a s e dc h o r d m o d e l ) 。 和原来的c h o r d 模型相比，h t c c h o r d 加入了按照节点兴趣爱好分簇和按照节点 的性能大小分层的概念。在h t c c h o r d 中，所有的节点被分到了若干个簇中，而每 个簇中的节点有相似的爱好。由于查询请求和节点的爱好有很大的相关性，这样以来 很多查找在簇内进行，就减少了资源定位的开销，提高了查询效率。同时针对节点性 能的异构性，采用混合模型，选取簇内性能最好的节点代表本簇组成上层c h o r d 网络， 以把不同的簇联系起来。这样充分发挥了节点的能力，而且缓解了节点退出和加入对 系统造成的巨大的扰动。 本文组成结构如下： 第一章为绪论，介绍了论文的背景，对等网络当前的研究现状以及论文的目的及 其意义。 第二章为p 2 p 网络介绍，介绍了p 2 p 网络的特点及前景，介绍了p 2 p 的网络结 构以及当前几个典型的分布式结构化算法。 第三章对c h o r d 基本协议进行了分析，并总结了c h o r d 模型中的不足。 第四章详细介绍了h t c c h o r d 模型，主要包括系统结构、改进的节点和资源标 识符、资源查找算法、网络的动态维护等内容。 第五章用理论分析和仿真实验两种方法，从查询效率和抗扰动能力两个方面对改 进后的模型和原始的c h o r d 模型进行对比分析。 第六章是全文总结，在简要回顾论文研究工作的基础上，指出了论文需要进一步 研究的方向。 4 2 1p 2 p 网络的概念 第二章p 2 p 网络概述 p 2 p t l 4 】的英文全称是“p e e r - t o p e e r ，p e e r 有“对等、同等者、伙伴”等的意思， 可以理解为“端对端，点对点”的意思，通常译为对等网络技术。网络中每个节点的 地位都是相同的，每个节点既充当服务器，为其他节点提供服务，同时也充当客户机， 享用其他节点提供的服务，打破了传统的模式【1 5 】。 到目前为止对于p 2 p 还没有统一的定义，有公司将其定义为使个人与个人之间直 接通信成为可能且更便捷的网络结构；i n t e r l 将其定义为通过系统间直接交换所达成 的计算机资源与信息( 包括信息交换、处理器时钟、缓存和磁盘空问等) 的共享；，i b m 将其定义为系统由若干互联协作的计算器构成，系统依存于边缘化设备的主动协作， 每个成员直接从其它成员而不是服务器的参与中受益，系统中的成员同时扮演服务器 与客户机角色，能相互意识到彼此的存在，构成一个群体。 ， 2 2p 2 p 网络的特点及应用 p 2 p 网络受到广泛关注，归根结底是因为p 2 p 技术具有以下特点： 1 ) 非中心化：网络中的资源和服务分散在所有节点上，信息的传输和服务的实 现都直接在节点之间进行，可以无需中间环节和服务器的介入，避免了可能 的瓶颈。p 2 p 非中心化的基本特点，决定了其在可扩展性、健壮性等方面的 优势。 2 ) 可扩展性：在p 2 p 网络中，随着用户的加入，不仅服务的要求增加了，系统 整体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。 整个系统是分布的，不存在瓶颈，理论上可以实现无限的系统可扩展性。 3 ) 健壮性：由于服务是分散在各个节点之间进行的，部分节点的失效或受到攻 击对其他部分的影响很小，另外，p 2 p 网络在部分节点失效时能够自动调整 整体拓扑，保持其他节点的连通性。所以p 2 p 网络具有耐攻击、高容错的优 点。 4 ) 高性能价格比：采用p 2 p 可以有效地利用互联网边缘的大量普通节点中闲置 s c h o r d 网络模型分析与改进 的计算资源或存储资源，以更低的成本提供更高的性能。 5 ) 隐私保护：在p 2 p 网络中，所有节点都可以提供中继转发的功能，使得信息 的传输分散在各节点之问进行，无需经过某个集中环节，用户的隐私信息被 窃听和泄漏的可能性大大缩小，为用户提供更好的隐私保护。 6 ) 负载均衡：p 2 p 网络中每个节点既是服务器又是客户机，消除了传统模式中 对服务器性能的依赖，同时因为资源分布在多个节点，更好的实现了整个网 络的负载均衡。p 2 p 应用可以根据所需策略进行灵活地发布信息。 7 ) 信息资源更丰富：任何p 2 p 节点能够发现活动节点并搜索所需的信息，然后 直接与目标节点通讯。每个节点都可以将其拥有的资源共享出来，请求率高 的资源能够很快地在系统中扩散开来，这样系统能够很快积累相当丰富的信 息。 8 ) 有效的搜索：w e b 搜索引擎只是从开放的服务器处得到巨大的搜索结果，并 且不会随着网络状态动态更新。而在p 2 p 系统中只有当节点在线时节点的信 息才被加入路由表，因此路由表与网络状态同步，这种动态性保证了查询的 有效性。 随着国内外对p 2 p 技术的深入研究和不断实践，p 2 p 技术正越来越多的应用到互 联网中，主要体现在以下几个方面： 1 ) 文件共享：基于p 2 p 技术的文件共享系统将共享信息文件存储在网络边缘节 点上，节点之间可以直接共享和传输文件而不需要通过中央服务器。这样不 仅节约了资源，还提高了系统的可扩展性、鲁棒性。 2 ) 对等计算：对等计算是分布式计算的思想在广域网上的延伸，目的是将网络 上的c p u 资源共享，把网络中众多的普通计算机中暂时不用的计算能力累 计起来，用以执行以往需要超级计算机来完成的任务。 3 ) 分布式存储：p 2 p 技术允许数据分散存放在多个节点上，而不是存放于专用 服务器。以满足在信息爆炸时代，信息存储所需要的海量存储空间。 4 ) 搜索引擎：p 2 p 技术使用户能够深度搜索文档，而且这种搜索无需通过服务 器，也可以不受信息文档格式和宿主设备的限制，可达到传统目录式搜索引 擎( 只能搜索到2 0 3 0 的网络资源) 无可比拟的深度( 理论上将包括网络上 的所有开放的信息资源1 。 5 ) 流媒体视频：在基于p 2 p 结构的视频组播系统中，只有少数节点从服务器 直接获取数据，更多的节点一方面从其它节点处获得数据，一方面也向其它 节点提供数据。这种以对等方式构建的视频组播系统充分利用了节点之间的 6 第二二章p 2 p 网络概述 可用带宽，很好的解决了传统流媒体带宽不足的问题使得系统的可扩展性大 为提高。 6 ) 即时通讯：即时消息是对等网络的重要应用之一，在当前己经得到相当普遍 的应用。基于p 2 p 技术的即时通讯软件不仅可以随时知晓对方是否在线，而 且交流双方的通讯完全是点对点进行，不依赖服务器的性能和网络带宽。 2 3p 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 网络和混合式p 2 p 网 络。 2 3 1 集中目录式网络 图2 1p 2 p 网络结构分类 在集中目录服务模型中，一台或者多台有特殊用途的服务器为对等点提供目录服 务，对等点向目录服务器注册自身的信息( 如名称标志，地址，资源和元数据) ，并通 过对目录服务器的查询获得所需要交互的对等点。为了尽量提高扩展性，必须考虑如 何以少量的目录就可以管理众多的对等点。目录服务期本身可以使对等点，或者只是 担当目录而没有其他功能。每个对等点都将自己注册到目录服务器中。当一个对等点 需要请求其他对等点的时候，可以向目录服务器进行查询，服务器返回符合条件的对 等点的位置。用于共享m p 3 音乐文件的n a p s t e r 1 6 】是其中最典型的代表。结构图如图 2 2 所示： 7 c h o r d 网络模型分析j 改进 c l i e 2 3 2 纯分布式网络 i n d c l i e n t 图2 - 2 集中目录式网络 c l i e n t 非结构网络也被称之为广播式的网络。它取消了集中的中央服务器，每个用户随 机接入网络，并与自己相邻的节点进行连接，从而构成一个逻辑覆盖的网络。节点是 相互平等的，其资源搜索和共享都是通过在相邻节点间进行广播完成的。每个节点记 录下搜索轨迹，防止环路的产生。 g n u t e l l a 1 7 1 模型是目前应用最广泛的非结构化网络，它具有扩展性和容错性较好 的特点，克服了集中目录式结构的缺点。但是它的搜索算法采用泛洪的方式进行，这 需要消耗大量的带宽，并且很容易造成网络拥塞甚至网络不稳定。为了解决消息的无 限制扩散，使用值加以控制，这样查询过程只能在有限的网络区域内进行。其结构可 用图2 3 表示。 8 p 图2 - 3 纯分布式p 2 p 网络 第二章p 2 p 网络概述 2 4 结构化网络模型 由于本文是对结构化网络中的c h o r d 模型进行研究改进，因此有必要简单介绍一 下当今主流的结构化p 2 p 网络模型。本节将简单介绍c a n ，t a p e s t r y 和p a s t r y 网络 模型，c h o r d 网络模型是研究重点，相关内容将在下一章说明。 2 4 1c a n c a n 6 】是b e r k e l e y 提出的一种结构化分布式查询算法。该算法构造一个虚拟的d 维笛卡儿坐标空间，每个机器或数据根据其i p 地址或关键字k ，由哈希函数映射到 该维空间中的一点。参与网络的物理节点动态划分该d 维空间，拥有某块虚拟坐标区 域的物理节点对由哈希函数映射到该区域中的数据负责。 1 逻辑拓扑结构 图2 _ 4 显示了一个2 维的网络的拓扑结构。这是一个2 维的笛卡儿坐标空间，整 个虚拟坐标空间被划分为许多小的2 维区域，每个物理节点对应一个区域，维护由哈 希函数映射到该区域的数据。比如节点a 对应( 0 0 5 ，o o 5 ) 区域，b 对应( o 5 1 ，0 - 0 5 ) 区域。在d 维空i 、丑j 中，如果两点有d 1 维坐标相同，并且剩下的一维坐标相邻( 如在 图中，e 和b ，d 都相邻，e 和a ，c 不相邻) ，则它们互为邻居。 ( 0 5 - 0 7 5 ，0 5 1 o ) ( 0 7 5 - 1 0 ，0 5 - 1 0 ) 0 0 1 u 图2 5 有5 个节点的二维c a n 网络图 2 数据结构 c a n 中每个节点需要维护一个协作式的路由表，路由表中包含邻居节点( 每维有 2 个，共有2 d 个) 以及相应的拥有空间。 3 查询算法 9 c h o r d 网络模型分析j 改进 c a n 进行查询操作时，首先将要查询的目标的关键字由哈希函数映射到d 维空 间中的一点( x ，y ) ，每一步从路由表中选取与( x ，y ) 笛卡儿距离最近的邻居节点转 发查询消息，这样一步步的将查询消息路由到目的节点。例如，在图2 4 中，如果从 节点开始查询某数据k ，假定k 数据属于管辖范围内，则可能的查询路由过程为： e d c 或e b a c 等。 4 节点的加入和退出算法 节点a 加入c a n 时首先需要知道一个已知节点b ，然后节点a 随机选取一个空 间坐标点( x ，通过b 在c a n 中路由到负责( x ，y ) 的节点c ，然后将c 负责的区 域均分，其中的一半给节点a ；与此同时，节点a 加入将导致节点c 及其邻居节点 的路由表发生变化，节点通知节点并由节点通知其邻居节点进行路由表的更新，此外， 每个节点还周期性地通知其邻居节点自己所负责的区域以便路由表的更新。 c a n 中节点正常退出时会运行接管算法( t a k e o v e ra l g o r i t h m ) ，发送t a k e o v e r 消息 给其直接邻居，并由某个邻居接管该节点留下的区域。 2 4 2t a p e s t r y t a p e s t r y i 是b e r k e l e y 提出的一种面向广域网分布式应用的可容错的路由和定位 基础结构。 1 逻辑拓扑结构 t a p e s t r y 的拓扑结构被称为p l a x t o nm e s h ，如图2 - 5 所示。每个对象( o b j e c t ) 和节 点以一个随机的定长、具有同一基的位序列作为标识号，与p a s t r y 中的标识号类似， 图2 5 中给出的是基为1 6 长度为4 的标识号。 2 数据结构 图2 - 6t a p e s t r y 逻辑拓s s bl 壅t 第二章p 2 p 网络概述 t a p e s t r y 中每个节点需要维护一个路由表、反向指针列表、对象位置指针和一些 热点监视信息。 路由表大小为b l o g b n ( b 行，l o 曲n 列) 每一项包含了网络中与当前节点最近的那 些节点，而且这些节点标识号中与列数相应数目的后缀也要与当前节点相同( 即第i 列需要有个后缀相同) 。 反向指针x 表主要用于生成节点的路由表。对象位置指针采用拓扑形式( 对象i d ， 节点i d ) ，用于在对象向服务器发送路由请求时提供帮助。热点监视信息是采用型如 ( 对象i d ，节点i d ) ，频率的拓扑集合，这些信息用帮助缓冲决定路由。 3 查询算法 。 t a p e s t r y 进行查询操作时，首先，当前节点计算自己的i d 与目的i d 的相同后缀 数目j ；然后，从路由表中选择一个中间节点( 一般在j + l 列) ，使得中间节点的i d 与 目的d 节点的的相同后缀数目大于等于j + l 。再把查询任务转交给这个中间节点继 续查询。这个过程递归进行，直到找到目的i d 。 4 节点的加入和退出算法 节点a 要加入网络时首先需要知道一个己知节点b ，然后通过发送消息来查询 它自己( a ) 的标识号。假设消息的路过程为b c z ，并通过目的节点z 返回给 a ，则z 变为a 的根节点，a 从访问过程中的第i 个节点可构造其路由表的第i 列条 目然后发送“h e l l o “报文给其新的邻居，其它节点根据a 的标识号和邻近性调整它 们的节点状态。节点定期地测试邻居的连接性，失效的邻居得到第二次更新机会，如 果在第二机会期间内，它们正常反应，将被标注为有效，一个节点在邻居失效后使用 后备邻居。 系统使用回溯优化法来调整网络性能，它努力尝试使用统计数据适应变化的网络 环境。例如节点使用p i n g 来更新到邻居的延迟，如果延迟变化超过一个阀值( 比如 4 0 ) ，它们就优化路由表。节点也监视请求对象的频率和建议缓冲决策( 称作热点缓 冲) 。 2 4 3p a s t r y p a s t r y 2 】是由剑桥微软研究所和r i c e 大学共同提出的一种用于在对等网络中进行 内容查询和路由的结构化分布式查询算法。p a s t r y 中每个节点或数据通过哈希函数映 射得到唯一1 2 8 比特的标识号，给定任一消息及其关键字，节点可以将消息路由到数 值上距离关键字最接近的目标节点。 c h o r d 网络模型分析与改进 1 逻辑拓扑结构 p a s t r y 中所有的节点也构成一个环形的拓扑结构，名字空间为( o ，2 1 2 8 - 1 ) 。 2 数据结构 p a s t r y 中每个节点维护一个路由表，一个叶子集和一个邻居集。 路由表最多包含1 2 8 2 b 行，2 b 列，其中第n 行记录了一部分节点的标识号及其 i p 地址，这部分节点的标识号的前位与本地节点相同且“距离接近；第n 行m 列 则是标识号的第n + l 位等于m 的节点的标识号和i p 地址；此外，与本地节点第n + l 位相同的那一表项保持为空，若没有符合条件的节点，也保持为空。 叶子集中节点的标识号在数值上最接近于本地节点标识号，可以取环上的本地节 点前i _ , 2 个和后l 2 节点的一前个和后个节点构成叶节点集，l 通常为2 b 。邻居集含 有m 项f 通常m = 2 * 2 b ) ，邻居集中是m 个离本地节点“距离 最近的节点邻居集并 不用于路由转发，而是为了维护p a s t r y 中节点的物理位置特性。 其节点维护的数据如图2 - 6 所示。 b = 2 ，因此节点i d 的 基数为4 ( 1 6b i t s ) 第m 列表项的 下一数位为m 当前苇点酌第n 个敲位 第n 行的前n 个数 位与本节点相同 i 相同静缀下- 敦位其它l 没有合适节点 的表项为空 图2 7p a s t r y 节点数据集 3 查询算法 p a s t r y 进行查询操作时，首先在叶子集中查询是否存在目的数据，如果关键字落 入叶子集中的i d 范围内，查询信息就转交给节点标识在数值上与被查询数据i d 值最 接近的那个节点，否则，从路由表中选择一个比现有节点有更多共同前缀的节点号， 把查询转交给这个节点以便进一步查询，如果仍然找不到这种节点，则在叶子集中寻 找与其i d 具有相同前缀长度但数值更接近的关键字的节点。依此进行，直到找到目 第一二章p 2 p 网络概述 的节点。 4 节点加入和退出算法 一个标识号为x 的新节点要加入p a s t r y ，必须首先知道一个现存的节点a ，通过 在p a s t r y 中对一个以x 为关键字的消息进行路由。在节点a 路由x 的过程中，每经 过路由路径中的一个节点，新节点x 便拷贝该节点的路由表中的第n 行，作为自己 路由表的第n 行( 因为该节点的标识号的前n 1 位与x 相同) ；初始化路由表之后，节 点x 便将自己路由表中的第n 行发送给该行中出现的每一个节点，通知其它节点x 的出现，其它节点便检查路由表中相应的行，并进行必要的路由表更新。 为了防止节点加入或失效导致路由表项的过期，从而造成路由质量的下降，p a s t r y 周期性地运行后台进程维护并更新路山表，根据路由表节点之间相互通知网络的最新 变。 2 4 4c h o r d 2 4 4 1c h o r d 介绍 c h o r d t 3 】是由m i t 设计的一种较简单的结构化p 2 p 模型。它的目标是提供一个分 布式、负载均衡的、可扩展的搜索策略，解决中心化搜索带来的可扩展性差、负载均 衡差等缺陷。 c h o r d 采用相容哈希把对象空间映射到它所依附的位逻辑环状结构的节点标识 空间通常称为环。每个节点通过相容哈希生成唯一m 的位标识符n o d e l d ，标识该节 点在c h o r d 环中的位置。所有节点的标识符按从d , n 大的顺序顺时针排列在环上。每 个资源同样具有唯一的m 位标识符。资源被分配给在环上以其k e y l d 开始顺时钟方 向的第一个节点，也就是n o d e l d 大于等于但最接近此k e y l d 值的节点，该节点称为 这个资源的后继节点，它将负责存储该资源的索引。这样节点和资源都被映射到了同 一个值域为 o 2 m 1 的环上。所以资源定位就变成了简单的对其后继节点的定位。 模型具有如下优点： 1 ) 负载平衡：所有的节点以同等的概率分担系统负荷，从而可以避免某些节点 负载过大的情况。 2 ) 分布性：c h o r d 是纯分布式系统，节点之间完全平等并完成同样的工作。这 使得具有很高的鲁棒性，可有效的抵御攻击。 3 ) 可扩展性：c h o r d 协议的开销随着系统规模一节点总数n 的增加而按照 0 ( 1 0 9 2 n ) 的规模增加。因此可以用于大规模的系统。 c h o r d 网络模型分析与改进 4 ) 可靠性：c h o r d 协议要求节点根据网络的变化动态的更新查询表因此能够及 时恢复路由关系，使得查询可以可靠地进行。 5 ) 命名的灵活性：c h o r d 并未限制查询内容的结构