（计算机应用技术专业论文）基于p2p覆盖网的路由算法研究.pdf

摘要 对等网应用在近几年内己得到突飞猛进的发展。资源共享系统 是对等网最重要的应用之一。资源系统的性能极大地取决于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 路由效率。 j x t a 是s u n 公司提出的一个构建p 2 p 环境的平台，提供在任何平 台、任何地方以及任何时间实现p 2 p 计算的一整套简单、小巧和灵活 的机制。但是随着网络节点的不断增多，网络规模的不断扩大，其所 采用的“洪泛”路由机制造成网络流量急剧增加，从而导致网络中部 分低宽带节点因网络资源过载而失效，致使路由效率低下。本文找出 使用了汇集节点视图是导致效率低下的原因，提出了将d h t 引入j x t a 的方案，最后给出了方案的设计与实现。 关键词对等网，覆盖网，路由算法，分布式哈希表 a b s t r a c t a p p l i c a t i o no fp 2 p ( p e e r - t o - p e e r ) n e t w o r kh a sd e v e l o p e dr a p i d l yi n r e c e n ty e a r s r e s o u r c es h a r i n gs y s t e mi sa l li m p o r t a n ta p p l i c a t i o no fp 2 p t h ep e r f o r m a n c eo fs u c hs y s t e md e p e n d so nt h ek e r n e lp r o b l e m so fp 2 p ： h o wt ol o c a t et h en e e d e dr e s o u r c ee f f e c t i v e l y , t h a ti s ，r o u t i n ga l g o r i t h m p 2 po v e r l a yn e t w o r ko f f e r san o v e lp l a t f o r mf o rav a r i e t yo fs c a l a b l e a n dd e c e n t r a l i z e d ，d i s t r i b u t e da p p l i c a t i o n s i nas t r u c t u r e dp 2 pn e t w o r k , t h eo n l yr e l a t i o nb e t w e e np h y s i c a ll a y e ra n do v e r l a yn e t w o r ki sd h ta n d n o d e sd on o tc o n t a i na n yi n f o r m a t i o na b o u tt h e i rp h y s i c a ll o c a t i o n s u c h p 2 po v e r l a yn e t w o r kd o e sn o tt a k ei n t oa c c o u n tp h y s i c a ln e t w o r k t o p o l o g ya n dr e s u l t si nh i g hr o u t i n gl a t e n c ya n dl o we f f i c i e n c y f o c u s i n g o ni m p r o v i n gr o u t i n ge n h a n c e m e n t ，t h et h e s i sc o n d u c t sa ni n d e p t h r e s e a r c ho nh o wt oe x t r a c tt o p o l o g yi n f o r m a t i o na n dh o wt ou t i l i z et h e i n f o r m a t i o nt oc o n s t r u c t t o p o l o g y - a w a r e p 2 p s y s t e m s t h e t h e s i s p r o p o s e st h es o l u t i o ne x p l o i t i n gt h en e t w o r kt o p o l o g ya n dp r o v e st h e s o l u t i o nc a n g r e a t l yi m p r o v er o u t i n ge f f i c i e n c yi nc h o r d j x t ai sap l a t f o r mp r o p o s e db ys u nt oc o n s t r u c tp 2 pe n v i r o n m e n t ， a n dp r o v i d e sas i m p l e ，s m a l la n df l e x i b l em e c h a n i c st or e a l i z ep 2 p c o m p u t i n ga ta n yp l a t f o r m , a n yp l a c ea n da n yt i m e h o w e v e r , w i t ht h e i n c r e a s eo fn e t w o r kn o d e sa n de n l a r g e m e n to fn e t w o r ks c a l e ，i t s f l o o d i n g ”r o u t i n ga l g o r i t h ml e a d st or a p i da u g m e n t a t i o no fn e t w o r kf l o w , a n dr e s u l t si nt h el o wl a t e n c y t h et h e s i sf i n d so u tt h a t e m p l o y i n g r e n d e z v o u sp e e rv i e wi st h er e a s o no ft h a t ，a n dp r o p o s e st h es o l u t i o nt o i n t r o d u c et h ed h ti n t oj x t a t h ed e s i g na n di m p l e m e n t a t i o no ft h e s o l u t i o na r eg i v e na tl a s t k e yw o r d s p e e r - t o - p e e rn e t w o r k , o v e r l a yn e t w o r k ，r o u t i n g a l g o r i t h m ，d i s t r i b u t e dh a s ht a b l e h 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学 位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在论文 中作了明确的说明。 作者签名盗室垫作者签名：宦旦：型 日期：加d 7 年耳月尹日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校有权保留学位 论文，允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容， 可以采用复印、缩印或其它手段保存学位论文；学校可根据国家或湖南省有关部 门规定送交学位论文。 名：逝翩签名蝴帆冰川日 硕十学位论文第一章绪论 1 1 研究背景 第一章绪论 最初开发p 2 p 网络来实现基于有线t c p i p 网络的文件共享。自1 9 9 9 年开始， 分布式信息共享系统的意义被像g n u t e l l a 1 和n a p s t e r 2 】这样的p 2 p 应用所证实。 最近，其它方面的应用也开始利用p 2 p 网络的优点，如p 2 p 流媒体，p 2 p 语音， 以及移动a dh o e 两潞中基于位置的服务p 】。这些应用进一步验证了对等计算思想 的成功。今天，对等计算应用已经超过w e b 应用，成为占用互联网带宽最多的 网络应用，其发展之势愈演愈烈，成为业界持续关注与探讨的热点。 p 2 p ( p e e r t o p e e r ) 计算技术之所以出现，其目的就是希望能够充分利用 互联网中所蕴含的潜在计算资源。p 2 p 中文称为对等网络，是指分布式系统中的 各个节点是逻辑对等的，与目前互连网上比较流行的c s 计算模型不同的是：p 2 p 计算模型中不再区别服务器以及客户端，系统中的各个节点之间可以直接进行数 据通信而不需要通过中间的服务器。 对于对等计算系统而言，能够适应的网络规模是项非常重要的指标。然而， 早期设计的系统，比如g n u t e l l a 和n a p s t e r ，在这方面都有一定的缺陷。前者使 用的是不适合大规模系统的洪泛策略，后者引入了集中式的目录管理。在这样的 背景下，一批基于分布式哈希表的系统应时而生，包括t a p e s t r y n 、p a s t r y f ”、 c h o r d l 6 和c o n t e n t - a d d r e s s a b l e n e t w o r k s ( c a n ) 】。在这些系统中，文件被赋予由 系统生成的标识( d ) ，这仲标识通常是文件名经过哈希计算得到。系统中的每一 个节点都和一个特定区段内的标识关联，并保存相关联标识对应的文件的信息。 当分布式哈希表系统对标识进行查询时，相应的节点便会返回对应的信息。分布 式哈希表系统的核心是路由协议。系统中的分布式哈希表节点构成一个覆盖网， 每一个查询操作都是通过这个覆盖网来找到目标节点。所以，基于分布式哈希表 p 2 p 系统的性能就取决于其所采用的路由协议的效率。 1 2 国内外研究动态 起源于2 0 世纪末的对等计算技术，是有别于客户，服务器计算模式的全分布 式计算模型。从研究现状来看，欧美等西方国家对p 2 p 技术的研究开展较好， 国内研究工作处于跟进阶段。 国外开展p 2 p 技术研究的组织和机构主要包括大学、i t 公司和国际学术团 硕十学位论文第一章绪论 体。大学侧重于p 2 p 领域的理论研究，高新技术公司侧重于p 2 p 技术的应用开 发和产品化，而国际学术团体主要从事p 2 p 标准化工作。 国外开展p 2 p 研究较为著名的大学和科研机构主要包括u cb e r k e l e y ，m i t 和a t & t 劂研究中心。在u cb e r k e l e y 大学，t a p e s t r y 项目和o c e a n s t o r e 项 目【8 】是p 2 p 技术相关项目。t a p e s t r y 提供了一个分布式容错查找和路由基础平 台，在此平台基础之上，可开发各种p 2 p 应用( o c e a n s t o r e 是此平台上的一个应 用) 。t a p e s t r y 的思想源于p l a x t o n 9 1 。在p i a x t o n 中，节点使用自己所知道的 邻居节点表，按照目的m 来逐步传递消息。如一条消息传递路径可能 是：料木4 * * 3 4 - 2 3 4 - - 1 2 3 4 ，其中斗：号表示通配符。该路径从右向左解析，即消 息首先传递到节点i d 为4 的节点，再分别依次传递到节点3 ，2 和l 。t a p e s t r y 基于p l a x t i o n 的思想，加入了容错机制，从而可适应p 2 p 的动态变化特点。 o c e a n s t o r e 是以t a p e s t r y 为路由和查找基础设施的p 2 p 平台。它是一个适合于 全球数据存储的p 2 p 应用系统。任何用户均可以加入o c e a n s t o r e 系统，或者共 享自己的存储空间，或者使用该系统中的资源。通过使用复制和缓存技术，可大 大提高o c e a n s t o r e 的查找效率。 在m i t ，开展了多个与p 2 p 相关的研究项目：c h o r d ，g r i d 和r o n 1 0 1 。c h o r d 项目的目标是提供一个适合于p 2 p 环境的分布式资源发现服务，它通过使用分布 式哈希路由表技术使查找指定对象只需要维护l o g n 长度的路由表。在分布式哈 希技术中，网络节点按照一定的方式分配一个唯一节点标识符( n o d ei d ) ，资源对 象通过哈希运算产生一个唯一资源标识符( o b j e c ti d ) ，且将该资源存储在节点 i d 与之相等或者相近的节点之上。需要查找该资源时，采用同样的方法可定位 到存储该资源的节点。因此，其主要贡献在于提出了一个分布式查找协议，该协 议可将指定的关键字( k e y ) 映射到对应的节点( n o d e ) 。从算法来看，c h o r d 是一 致性哈希算法的变体。m i t 的g r i d 和r o n 项目提出了在分布式广域网中实施查 找资源的系统框架( r o n 注重小规模的网络环境) 。 a t & t 互联网研究中心的c a n 项目独特之处在于采用多维标识符空间来实现 分布式哈希算法。网络中每一个节点在每一维标识符空间中均保存与自己( 逻辑 上或者物理上) 相连节点的信息。标识符空间中的每一个i d 代表一个节点，该节 点存储相应的一对( k e y ，v a l u e ) ，其中k e y 通过哈希运算映射为节点对应的i d ( n o d ei d ) 。当需要查询时，只需采用相同的方法对查询的关键字k e y 进行哈希 运算，得到一个节点i d ( n o d ei d ) ，从该节点即可找到与关键字对应的内容 ( v a l u e ) 。 此外，斯坦福大学的对等网项目组【1 1 1 也开展了许多针对p 2 p 的研究工作。但 是，这些p 2 p 研究项目，其路由算法均假设存在一个互连互通的对等网络，并以 2 硕十学位论文第一章绪论 此为基础来讨论消息路由问题。而对如何构建这样的互连互通对等网络较少论 及。此外，这些研究多注重理论探讨，甚少考虑实际应用，因此目前未见有关大 规模应用的相关报道。 国外开展p 2 p 研究的学术团体主要包括p 2 p 工作组( p e e r - t o p e e rw o r k i n g g r o u p ，p 2 p w g ) 1 2 , 1 3 、全球网格论坛( g l o b a lg r i df o r u m ，g g f ) u 4 。p 2 p 工作组成 立的主要目的是希望加速p 2 p 计算基础设施的建立和推进p 2 p 标准化工作。p 2 p w g 成立之后，对p 2 p 计算中的术语进行了统一，也形成了相关草案，但是在标准化 方面工作却进展缓慢。目前p 2 p w g 己经合并到g g f ，由该论坛管理与p 2 p 计算相 关的工作。 从国外公司对p 2 p 计算的支持力度来看，m i c r o s o f t 公司【1 5 】，s u n 公司【16 】和 i n t e l 公司f l7 】投入较大。m i c r o s o f t 公司成立了p a s t r y 项目组，主要负责p 2 p 计 算技术的研究和开发工作。目前m i c r o s o f t 公司已经发布了基于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 大学也在p a s t r y 的基础之上发布了f r e e p a s t r y 软件包。 在2 0 0 0 年8 月，i n t e l 公司宣布成立p 2 p 工作组，正式开展p 2 p 的研究。工 作组成立以后，积极与应用开发商合作，开发p 2 p 应用平台。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 加速工具包1 和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 项目。j x t a 是基于j a v a 的开源 p 2 p 平台，任何个人和组织均可以加入该项目。因此，该项目不仅吸引了大批 p 2 p 研究人员和开发人员，而且已经发布了基于j x t a 的即时聊天软件包。j x t a 定义了一组核心业务：认证、资源发现和管理。在安全方面，j x t a 加入了加密 软件包，允许使用该加密包进行数据加密，从而保证消息的隐私、可认证性和完 整性。在j x t a 核心之上，还定义了包括内容管理、信息搜索以及服务管理在内 的各种其它可选j x t a 服务。在核心服务和可选服务基础上，用户可以开发各种 j x t a 平台上的p 2 p 应用。 除了大学，学术团体和i t 公司积极参与p 2 p 研究之外，许多个人和开源爱好 者也积极开展p 2 p 的研究工作，其中较为知名的是f r e e n e t 系统和g n u t e l l a 系 统。 f r e e n e t i $ 1 的研究始于1 9 9 9 年，i a nc 1 a r c k 在爱丁堡大学设计和开发了 f r e e n e t 系统。f r e e n e t 是文件共享p 2 p 系统，其主要目的是充分利用匿名通信 系统的特点，即用户可以匿名访问系统中共享文件。从逻辑上看，f r e e n e t 主要 由五部分组成：关键字生成与查找、数据获取、数据存储、数据管理和节点管理。 由于f r e e n e t 主要关注通信的匿名性，因而难以大规模应用。 a o l 公司的两位职员在2 0 0 0 年3 月发布了g n u t e l l a 系统，随后因为法律问 3 硕士学位论文 第一章绪论 题，g n u t e l l a 关闭了官方网站。但是，由于该协议使用广泛，因而许多厂商和 p 2 p 爱好者继续进行g n u t e l l a 兼容系统的开发。寻求全分布式特征是g n u t e l l a 的主要目标，因此其匿名性好，但可靠性不能保证。从设计角度来看，g n u t e l l a 不是一个实际的p 2 p 系统，而是一个p 2 p 协议。系统开发者必须实现该协议才能 进行文件共享，也因此被认为是目前p 2 p 资源共享领域的“企业标准”。由于 g n u t e l l a 采用“泛洪”方式进行资源发现，网络带宽浪费极为严重，因此从理 论上看，g n u t e l l a 扩展性差。 从目前国内研究现状来看，一些大学和公司成立了对p 2 p 的研究课题组和部 门。从2 0 0 3 年开始，国家8 6 3 计划和自然科学基金计划资助一些关于p 2 p 技术 的项目。目前在中国核心期刊上发表的有关p 2 p 的文章逐渐增多，文献 1 9 ，2 0 各自综述不同的p 2 p 领域，文献 2 1 ，2 2 提出了对p 2 p 系统进行改进的方案，以 及文献 2 3 ，2 4 提出新的系统和模型。文献 2 5 ，2 6 是相关的对p 2 p 领域和技术 的博士论文，可见p 2 p 也开始受到高校和研究机构的关注。因此，国内关于p 2 p 的研究仅处于起步阶段，这就为技术创新提供了有利契机。 m a z e 2 7 】是北京大学网络实验室开发的一个中心控制与对等连接相融合的对 等计算文件共享系统，在结构上类似n a p s t e r ，对等计算搜索方法类似于 g n u t e l l a 。网络上的一台计算机，不论是在内网还是外网，可以通过安装运行 m a z e 的客户端软件自由加入和退出m a z e 系统。每个节点可以将自己的一个或多 个目录下的文件共享给系统的其他成员，也可以分享其他成员的资源。m a z e 支 持基于关键字的资源检索，也可以通过好友关系直接获得。 g r a n a r y 冽是清华大学自主开发的对等计算存储服务系统。它以对象格式存 储数据。另外，g r a n a r y 设计了专门的节点信息收集算法p e e r w i n d o w 的结构化 覆盖网络路由协议t o u r i s t ”。 一 a n y s e e 3 0 堤华中科技大学设计研发的视频直播系统。它采用了一对多的服务 模式，支持部分n a t 和防火墙的穿越，提高了视频直播系统的可扩展性；同时， 它利用近播原则、分域调度的思想，使用l a n d m a r k 路标算法直接建树的方式构 建应用层上的组播树，克服了e s m 等一对多模式系统由联接图的构造和维护带来 的负载影响。 1 3 研究内容及研究意义 p 2 p 系统的路由性能往往直接关系到系统的性能。结构化p 2 p 中主要采用分 布式哈希表( d i s t r i b u t e dh a s h t a b l e ，d h t ) 形成的覆盖网的路由方式，很多经典的 路由算法，如文献 4 ，5 ，6 ，7 】都基于这种方法。而d h t 类结构最大的问题是 形成路由表时没有考虑物理网络的拓扑结构。本文的目的主要在于如何利用物理 4 硕 ：学位论文第一章绪论 网络的拓扑提高覆盖网路由的效率，以及提出改进现有p 2 p 系统的路由算法及 其设计实现。 开展p 2 p 技术及其路由技术的研究，其重要的理论意义在于可推动分布式 计算技术在下一代互联网中的应用【3 l 】。下一代互联网是个高速网络通信平台， 如何开展基于这一平台的应用，始终是科研工作者和工程技术人员面临的主要问 题。客户服务器计算模型在目前网络环境中己经出现了许多难以解决的问题， 分布式计算则被认为是下一代网络应用的主要技术之一。与集中式应用相比，分 布式环境中资源的有教利用显得尤为重要。从本质来看，p 2 p 是一种特殊的分布 式计算模型，因此研究p 2 p 的路由技术，有助于从理论上探讨分布式计算技术。 1 4 内容组织与安排 本论文分为五大部分。第一部分为绪论，主要介绍工作的研究背景和国内外 研究现状分析。第二章将详细介绍p 2 p 系统及其路由系统。第三章将介绍利用网 络拓扑的结构化p 2 p 系统。第四章将介绍j x t a 路由改进算法的研究与实现。最 后是本文的工作总结以及一些研究展望。 5 硕七学位论文第二章p 2 p 覆盖网及其路由系统 第二章p 2 p 覆盖网及其路由机制 p 2 p 与传统网络的相比，有了巨大的变化。对等网络有以下特点： ( 1 ) 没有服务器。这是和以前的客户机服务器网络的最大的区别。在对等 网络中，没有服务器的概念，所以的对等节点都是客户机，也都是服务器。 ( 2 ) 可扩展性好。对等网络的规模随着加入节点的数量的增长而增长，新 节点的加入会给系统增加新的资源，这种可扩展性几乎是无限的，理论上限是现 有的i n t e r n e t 的规模。 ( 3 ) 完全对称。在对等网络中，所以的节点都是对称的，运行完全相同的 软件，完成完全相同的功能，这也是对等网络名称的由来。 下面从p 2 p 系统，p 2 p 覆盖网以及几个经典的路由系统三个方面来认识p 2 p ， 也为下面两章做好知识准备。 2 1p 2 p 系统的划分 当| ；i 有从多的p 2 p 网络并且每种p 2 p 网络有着不同的特性，所以不存在唯一 的划分标准。为了更好地了解p 2 p 网络，以下从两个不同的角度来划分。 根据对象请求机制和p 2 p 逻辑拓扑的不同，当前p 2 p 体系结构可以分为三种 【3 2 】：1 ) 集中式p 2 p 网络：所有对象索引用( o b j e c t k e y ，n o d e a d d r e s s 的形式 保存在一台集中的服务器上。每个新加入的节点需要通知服务器它说保存的对象 信息，以后其它节点只要从服务器查询它所要对象所在节点的地址。这种p 2 p 结构简单易部署。尽管有多个并行服务器，但它有单节点失效的问题。n a p s t e r 是此种结构的例子。2 ) 非集中式非结构化p 2 p 网络：对象请求是分布的，逻辑 p 2 p 拓扑通常是随机的无结构网络。请求一步一步地在网络中执行直到请求成 功，失败或超时。g n u t e l l a 就是这种的类型p 2 p ，没有单点失效但是请求效率可 能很低。3 ) 分布式结构化p 2 p 网络：对象请求也是分布的并且p 2 p 的逻辑拓扑 是某种结构的拓扑，如：网孔状( m e s h ) 1 3 3 ，环状( r i n g ) 【3 4 1 ，d 维圆环面 ( d d i m e n s i o nt o r u s ) 阅和蝴蝶状( b u t t e r f l y ) 【3 6 1 。这些结构化的拓扑通常用 分布式哈希表( d is t r i b u t e dh a s h i n gt a b l e ，d h t ) 构建。对象请求也是在结构 化拓扑上逐跳执行，在理想情况下，能保证在有限跳后执行成功。 根据时间顺序和目的，当前的p 2 p 网络能分为三代：1 1 第一代：早期的p 2 p 网络，如n a p s t e r 和g n u t e l l a ，以容易且快速部署为目的。这代网络简单，而且 其可展性差或请求效率低。2 ) 第二代：第二代p 2 p 网络常利用d h t 技术来实 现更好的扩展性和更高的请求效率，并提供负载平衡和确定性查询保证。尽管如 硕十学位论文第二章p 2 p 覆盖网及其路由系统 此，弹性或容错性并不是很好，特别是在恶意攻击的情况下。3 ) 第三代：新近 提出的p 2 p 网络在假设节点以一定的失效概率离开的前提下，目的在于提供高 弹性。产生弹性的常用方法有：复制，扩展节点之间的连接数以及一些特别的结 构化拓扑。第二代和第三代p 2 p 网络通常是分布的结构化覆盖网络。 2 2 覆盖网的分类 先来看看互联网通信结构的几个问题：广域网路由协议b g p 对聚合和失效反 应都很缓慢：端主机传统地由口地址命名，所以当主机移动时由i p 决定的层次 寻址成了问题。故覆盖网路由的出现顺其自然。覆盖网路由是在坤层的通讯抽 象。口通过多条链路和多台路由器路由数据从而使得两台主机会话。而覆盖网 路由考虑两台m 端主机在覆盖网路径中通过一条链路会话。根据覆盖网路由在 互联网的目的，覆盖网可分为两种：通讯覆盖网和数据覆盖网，图2 1 总结了这 种分类。下面对这两种覆盖网详细介绍。 图2 - 1 覆盖网的分类 2 2 1 通讯覆盖网 尽管口体系结构为主机提供了适度的可靠性通讯的能力以及b g p 是能扩展 到成千上万个网络的动态路由协议，但是体系结构并不能迅速地从链路和路由等 错误中恢复做出反应。以前的研究表吲3 7 】：当错误发生时，b g p 要用大概1 5 分 钟来聚合。另外，b g p 在设计时并没有考虑应用敏感的度量，如高丢失率或延 时，拥塞链路中路由等等。由于这些性能的缺陷，端主机可预沿着不同互联网路 径，如周期性的高拥塞或高丢失率，甚至长期的停机，其性能一定低下。因此， 在通讯覆盖网中，两台主机之间的路径包含多个m 会话跳，如图2 - 2 。在图2 中，覆盖网路由用m 路由当作逐跳的抽象。相比口会话包含数据通过多口级 跳的路径在两台主机之间传输，覆盖网会话把一条用m 会话作为抽象的路径， 作为覆盖网会话的一跳。 7 硕十学位论文第二章p 2 p 覆盖网及其路由系统 置 a w l 掣c o e m d 图2 - 2i p 会话和通讯覆盖网会话 假设覆盖网典型地由小团加入节点组成，那么覆盖网的设计能达到比现存i p 体系结构更好的失效恢复特性。另外，不同的应用有不同的性能度量。例如，网 络音频对延时会很敏感，甚至在一定的丢失率下，不能很好的播放；再如，视频 寻求是可察觉到的抖动最小化。另外，块传输软件对可接受的丢失率和延迟有着 不同的定义。所以，通讯覆盖网应当与各种应用结合来允许应用定义自己合适的 度量。 r e s i l i e n to v e r l a y 网络( r o n ) 是通讯覆盖网的一个实例。这种网络用看似 在覆盖网中的一条连通路径散播有关性能的链路状态信息，从而使得通讯在较少 的主机之间进行。要注意的是，相关的信息只在r o n 上传播，以保证在路径失 效时路由信息仍能转发。r o n 实现策略把路由策略分成两个阶段：分类和路由 表信息。在r o n 传输的每个包都给定了特别的策略标签，来决定哪个路由表可 用来转发包。每个策略的路由表构建时考虑到了针对当前拓扑的最短路径，仅仅 包含了那些满足策略的链路。所有这些步骤由“策略满足器”完成，这就使得覆 盖网实现诸如团的策略。 2 2 2 数据覆盖网 c h o r d 是数据覆盖网的典型实现之一。c h o r d 先通过在描述最近后继的f i n g e r 表中定位节点来查询数据，在路由数据。这种覆盖网具有了内容寻址能力，这使 得主机a 根据它想查询的内容来指定目的端主机。一次会话包含o ( 1 0 9n ) 覆 盖跳。当然这会在口底层导致不好的性能，特别是在没有很好地了解底层口网 络时。在数据覆盖网中，选择最近节点仅能保证逐跳的性能，而不能保证在底层 网络的全局优化路径。 基于分布式哈希表的p 2 p 系统形成了一个基于“p u t ”和“科”操作的数据 硕士学位论文第一二章p 2 p 覆盖网及其路由系统 集中抽象层，数据能以独立于指定特定节点的口层的方式传递给节点。这样一 台主机对数据实行p u t 操作，而另外一台主机对相关的数据实行g e t 操作。这 就实现了一定程度的间接性，那么两台主机之问的路径可包含多条覆盖网路径。 这种间接性使得提供诸如移动性的服务更加容易，因为指定端点的观念可以 抽象出来。增加一定由数据覆盖网提供的间接性使得主机能有效地汇集起来通 讯。两台主机之自j 的通讯能不需要任何指定的一端而存在，所以移动性是个容易 解决的问题：端主机能改变它在i p 底层中的“名字”( 如i p 地址) ，而发送数据 的主机不需要知道任何m 地址的改变，因为通讯抽象是基于不要改变的汇聚点。 命名抽象也可在其它许多环境中来达到移动性的目的。有两种可相互替代的 方法：第一种方法是，用d n s 来绑定一个新地址到一个地址的m i g r a t e 结构h ”， 使得主机的d n s 名字成为主机用以通讯的端点。移动i p 是第二种方法。这种方 法用外地代理的观念来实现移动性。通讯主机与其它主机本地代理通讯，而本地 代理知道该主机的位置。但是，这两种方法只对移动性问题有效。 用d h t 作为名字抽象的结构更加广泛，这种结构把移动性当作可通过建立 会话能解决的问题之一。正因为数据覆盖网能根据网络标识数据包路由，相互通 讯就不再需要点到点了。许多主机端在网络标识的另一边( 多播) ，或响应最长 匹配触发器的主机端能够变化( 负载平衡) 。许多像描述特定应用的操作能实现， 如编码变换，通过覆盖网发送数据包到特别的路径即可。更好的是，能选择接受 者，这是因为接受者能把插入描述其它中间触发器( 如操作) 的信息。 2 3 基于覆盖网的经典路由机制 2 3 1c h o r d 一、相容性哈希( c o n s i s t e n th a s h ；n g ) c h o r d 实现了一种操作：给定一个关键字( k e y ) ，将k e y 映射到某个节点。 如果给对等网络应用的每个数据都分配一个k e y ，那么对等网络中的数据查找问 题就可以用c h o r d 很容易地解决了。 c h o r d 采用了相容哈希【3 9 】的一种变体为节点分配关键字。相容哈希有几个很 好的特点，首先是哈希函数可以做到负载平衡，也就是说所有的节点可以接收到 基本相同数量的关键字。另外，当第n 个节点加入或者离开网络时，只有1 n 的关键字需要移动到另外的位置。 c h o r d 进一步改善了相容哈希的可扩展性。在c h o r d 中，节点并不需要知道 所有其他节点的信息。每个c h o r d 节点只需要知道关于其他节点的少量的“路由” 信息。在由n 个节点组成的网络中，每个节点只需要维护其他o ( 1 0 9 n ) 个节点的 信息，同样，每次查找只需要o ( 1 0 9 n ) 条消息。当节点加入或者离开网络时，c h o r d 9 硕士学位论文第二章p 2 p 覆盖网及其路由系统 需要更新路由信息，每次加入或者离开需要传递o ( i 0 9 2 n ) 条消息。 相容哈希函数为每个节点和关键字分配m 位的标识符，此标识符可以用 s h a 1 【4 0 】等哈希函数产生。节点的标识符可以通过哈希节点的i p 地址产生，而 关键字的标识符可以直接哈希此关键字。比如i p 地址为 1 9 8 1 0 1 0 1 的节点经过 s h a 1 哈希之后得到的标识符为1 2 3 ，而关键字“f i n d m e 哈希之后的关键字为 6 0 。标识符长度m 必须足够长，这样才能保证两个节点或者关键字哈希到同一 个标识符上的概率小到可以忽略不计。 在相容哈希中，每个关键字都保存在它的后继( s u c c e s s o r ) 节点中，后继节 点是节点标识符大于等于关键字k 标识符的第一个节点，将其记为s u c c e s s o r ( k ) 。 由于关键字“f i n d m e ”的标识符为6 0 ，因此它被保存在5 0 节点中。如果标识符采 用n l 位二进制数表示，并且将从0 到2 ”一1 的数排列成一个圆圈，那么s u c c c s o r ( k ) 就是从k 开始顺时针方向距离最近的节点。这一点，可以从图2 3 中很清楚地得 出。 图2 - 3 相客哈希实例 f i n d m c 。 相容哈希的一个特点就是当节点加入或者离开网络时对网络带来的冲击可 以达到最小。当节点n 加入网络时，为了保持相容哈希映射，某些原来分配给n 的后继节点的关键字将分配给n 。当节点n 离开网络时，所有分配给它的关键字 将重新分配给n 的后继节点。除此之外，网络中不会发生其他的变化。以图2 - 3 为例，当节点n s 0 离开网络时，关键字“f i n d m e ”将被分配给节点n 1 2 3 。 二、关键宇查找 下面看看c h o r d 如何进行关键字查找。 首先考虑最简单的情况，假设每个节点都知道整个网络中的节点和关键字的 信息，也就是说，每个节点都维护0 ( n ) 大小的路由表。当网络规模很大时，这 种策略是不可行的。当然，这种策略的优点也很明显，它只需要进行一次路由表 查找就可以找到关键字所在的节点。 1 0 硕十学位论文第一二章p 2 p 覆盖网及其路由系统 再看图2 - 4 中的方案。图中每个节点只知道其后继节点的信息。这样当进行 查找时，节点将依次查询其后继节点，直到找到关键字或者遍历完整个网络为止。 这种方式的优点是可扩展性好，每个节点需要知道的信息很少，缺点是查询速度 比较慢，为o ( n ) 数量级，当网络规模很大时，这样的速度是不能接受的。 k 6 0 图2 - 4 一种关键字查找方案 c h o r d 采用了上述两种方案的折衷方案。在c h o r d 中，每个节点维护少量的 路由信息，通过这些路由信息，可以提高查询的效率。 如果m 是关键字和节点标识符的位数( 采用二进制表示) ，那么每个节点只 需要维护一张最多m 个表项的路由表，被称之为指针表( f i n g e rt a b l e ) 。节点n 的查找表的第i 个表项包括的是s = s u c c e s s ( n + 2 1 1 ，这里1 = i = m 并且所有的计 算都要进行m o d2 “，s 称为节点n 的第i 个指针，用n f i n g e r i n o d e 表示，指针 表中的其他项的含义如表2 1 所示。 表2 - 1c h o r d 指针表结构 符号定义 f i n g e r k s t a r t( n + 2 “) m o d2 ，l = k ( = m i n t e r v a l f i n g e r k s t a r t ，f i n g e r k + 1 s t a r t n o d e 第一个大于或等于n f i n g e r k s t a r t 的节点 s u c c e s s 0 r 标识符环中的下一个节点：f i n g e r i n o d e p r e d e c e s s o r标识符环中的前一个节点 以图2 - 5 为例，节点1 的指针表的表项应该分别指向标识符( 1 + 2 0 ) r o o d2 3 = 2 ， ( 1 + 2 1 ) m o d 2 3 = 3 ，( 1 + 2 2 ) r o o d2 3 = 5 。而标识符2 的后继是节点3 ，因为它是2 之后的第一个节点，标识符3 的后继是节点3 ，而标识符5 的后继是节点0 。 这一方案有两个重要的特性：首先，每个节点都只需要知道一部分节点的信 息，而且离它越近的节点，它就知道越多的信息。其次，每个节点的指针表通常 硕士学位论文第二章p 2 p 覆盖网及其路由系统 并不包括足够的信息可以确定任意一个关键字的位置。例如，图2 5 中的节点3 就不知道关键字1 的位置，因为1 的后继节点信息并没有包含在节点3 的指针表 中。 当节点n 不知道关键字k 的后继节点时怎么办? 如果n 能够找到一个节点， 这个节点的标识符更接近k ，那么这个节点将会知道该关键字的更多信息。根据这 一特性，n 将查找它的指针表，找到节点标识符大于k 的第一个节点j ，并询问节 点j ，看j 是否知道哪个节点更靠近k 。通过重复这个过程，n 最终将会知道k 的后 继节点。 仍然考虑图2 5 中的例子，节点3 需要查找关键字1 的后继节点。由于l 属于 循环区间【7 ，3 】，它属于3 f i n g e r 3 i n t e r v a l ，因此节点3 查找其指针表的第3 项，返 回0 。由于0 在1 之前，因此节点3 将要求0 去寻找关键字1 的后继节点。依此类 推，节点0 将查找它的指针表并发现1 的后继节点是l 本身，于是节点0 将告诉 节点3 节点1 是它要找的节点。 7 i + ( 。1 c6 | f l n 雪棒t a b l o轴p s t a r t a t $ u t ：c 丁可可1 6 2 1 2 ” 3 “ 4 h ，o o 图2 - 5c h o r d 路由实例 2 3 2 内容访问网络( c a n ) c a n 可以在i n t e r n e t 规模的大型对等网络上提供类似哈希表的功能。c a n 具有可扩展、容错和完全自组织等特点。 一、c a n 的组成 。 一 4 u ；|；一 、 、一 硕士学位论文 第二章p 2 p 覆盖网及其路由系统 c a n 类似于一张大哈希表，c a n 的基本操作包括插入、查找和删除( 关键 字，值) 对。c a n 由大量自治的节点组成。每个节点保存哈希表的一部分，称 为一个区( z o n e ) 。此外，每个节点还保存少量的邻接区的信息。对每个特定关 键字的插入( 或者查找、删除) 请求由中间的c a n 节点进行路由直到到达包括 该关键字的c a n 节点所在的区。c a n 的设计完全是分布式的，它不需要任何形 式的中央控制点。c a n 具有很好的可扩展性，节点只需要维护少量的控制状态 而且状态数量独立于系统中的节点数量。c a n 支持容错特性，节点可以绕过错 误节点进行路由。 c a n 基于虚拟的d 维笛卡儿坐标空间实现其数据组织和查找功能。整个坐 标空间动态地分配给系统中的所有节点，每个节点都拥有独立的互不相交的一块 区域。图2 - 6 给出了一个2 维的【o ，1 】 o ，1 】的笛卡儿坐标空间划分成五个节点区 域的情况。 图2 - 6 笛卡尔坐标空间的区域划分 虚拟坐标空间采用下面的方法保存( 关键字，值) 对。当保存( k 1 v 1 ) 时， 使用统一的哈希函数把关键字k 1 映射成坐标空间中的点p 。那么这个值将被保 存在该点所在区域的节点中。当需要查询关键字k 1 对应的值时，任何节点都可 以使用同样的哈希函数找到k l 对应的点p ，然后从该点对应的节点取出相应的 值。如果此节点不是发起查询请求的节点，c a n 将负责将此查询请求转发到对 应的节点。因此，有效的路由机制是c a n 中的一个关键问题。 二、0 a n 中的路由机制 c a n 中的路由机制非常简单，只需要计算目的点的坐标，然后寻找从发起 请求的点到目的点的一条路径就可以。首先需要给出两个节点区域邻接的含义， 在d 维坐标空间中，当两个区域在d 1 维上都覆盖相同的跨度而在另一维上相互 硕士学位论文第二章p 2 p 覆盖网及其路由系统 邻接，则称这两个区域邻接。例如，图5 中d 和e 是邻接节点，而d 和a 就不 是邻接节点。每个c a n 节点都保存一张坐标路由表，其中包括它的邻接节点的 i p 地