（计算机软件与理论专业论文）基于邻近度的p2p路由算法的设计与实现.pdf

摘要 摘要 p 2 p ( p e e r - t o p e e r ) 网络是近年来网络研究的一个热点。目前绝大多数的p 2 p 网络系统都是以覆盖网络方式构建的。在覆盖网络中相邻的节点在底层网络中可 能并不相邻甚至相隔很远，这样导致覆盖网络中两个节点问会有很大的路由延迟。 只有节点路由表项的内容j 下确地反映节点之间在底层网络中的拓扑关系，才能最 终减少应用层的路由延迟，提高网络应用的性能。 论文首先介绍了几种结构化p 2 p 路由机制：c h o r d ，c a n ，p l a x t o n ，t a p e s t r y ， p a s t r y 和p g f i d ：以及几种非结构化p 2 p 路由机制：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 和f r e e n e t 。重点分析了p g r i d 路由算法。针对p g r i d 路由算法的路由表维护的盲 目性和优化周期长等缺点，本文提出了一种新的基于邻近度选择技术的路由表维 护算法p n s p g r i d ( p r o x i m i t yn e i g h b o rs e l e c t i o np g r i d ) 。p n s p g r i d 是在节点转发一 个查询请求后，触发路由表维护任务，并对本次转发使用的路由表项进行优化， 且优化周期根据路由表项是否达到或接近最优值而进行调整。p n s p g r i d 算法中还 加入了对未报告的节点失效和异常退出的处理机制来对路由表进行维护。最后在 开源软件p g 瑚中实现了p n s p g r i d 算法。测试表明，p n s p g r i d 算法在较少的开 销下使路由表项能动态的有针对性的进行调整，并且快速地达到最优值，最终减 少路由延迟，提高网络性能。 关键词：p 2 p 网络，覆盖网络，p 2 p 路由，邻近度邻居选择 a b s t r a c t a b s t r a c t p 2 p ( p e e r - t o p e e r ) n e t w o r ki s ah o t s p o to ft h en e t w o r kr e s e a r c hi nt h e r e c e n ty e a r s a tp r e s e n t ，m o s to ft h ep 2 pn e t w o r ks y s t e m sa r ec o n s t r u c t e da s o v e r l a yn e t w o r k s n e i g h b o r i n gn o d e si na no v e r l a yn e t w o r ka r en o tn e c e s s a r i l y c l o s et oe a c ho t h e ro rm a ye v e nf a ra w a yf r o me a c ho t h e ri nt h eu n d e r l y i n g n e t w o r k ，w h i c hm a yr e s u l t i n h i g hr o u t i n gd e l a yb e t w e e nt w on o d e si n t h e o v e r l a yn e t w o r k o n l yi ft h ee n t r i e si nt h er o u t i n gt a b l ec o r r e c t l yr e p r e s e n tt h e u n d e r l y i n gn e t w o r kt o p o l o g yc a nt h er o u t i n gd e l a yi n t h ea p p l i c a t i o nl e v e lb e r e d u c e da n dt h er o u t i n ga n dn e t w o r ka p p l i c a t i o np e r f o r m a n c eb ei m p r o v e d t h i st h e s i sf i r s ti n t r o d u c e ss e v e r a ls t r u c t u r e dp 2 pr o u t i n gm e c h a n i s m s ： c h o r d ，c a n ，p l a x t o n ，t a p e s t r y ，p a s t r ya n dp g r i d ，a n ds e v e r a lu n s t r u c t u r e dp 2 p r o u t i n gm e c h a n i s m s ：n a p s t e r , b i t t o r r e n t ，g n u t e l l aa n df r e e n e t ，a n dt h e n f o c u s e so nt h ea n a l y s i so ft h ep g r i dr o u t i n g a l g o r i t h m a i m i n g a tt h e d i s a d v a n t a g eo f b l i n do p t i m i z a t i o n ，l o n go p t i m i z a t i o nc y c l ea n de t c o ft h e m a i n t e n a n c em e t h o du s e di np g r i dw h i c hs e l e c t sr o u t i n gt a b l ee n t r i e st o o p t i m i z ep e r i o d i c a l l ya n dr a n d o m l y , t h i st h e s i sp r e s e n t san e wr o u t i n gt a b l e m a i n t e n a n c ea l g o r i t h mc a l l e dp n s p g r i d ( p r o x i m i t y n e i g h b o rs e l e c t i o np g r i d ) i np n s p g r i d ，t h er o u t i n gt a b l em a i n t e n a n c et a s ki si n v o k e da f t e ran o d eh a s f o r w a r d e dar e q u e s ta n dt h ee n t r yu s e da tt h i st i m ei s o p t i m i z e d t h e o p t i m i z a t i o nc y c l ei sa d j u s t e da c c o r d i n gt ow h e t h e rt h er o u t i n gt a b l ee n t r y r e a c h e so ri sc l o s et ot h eo p t i m i z a t i o nv a l u e ，p n s - p g r i da l s oi n c o r p o r a t e st h e m e c h a n i s mt oh a n d l et h eu n w a r n e dn o d ef a i l u r ea n de x c e p t i o n a ld e p a r t u r et o m a i n t a i n r o u t i n gt a b l e e x p e r i m e n ts h o w st h a tp n s p g r i da l g o r i t h m c a n d y n a m i c a l l ya n dp e r t i n e n t l ya d j u s tt h ee n t r i e si nan o d e sr o u t i n gt a b l eu n d e ra c o m p a r a t i v e l yl o wc o s ta n dc a nr e a c ht h eo p t i m i z a t i o nv a l u ef a s t e r ，w h i c hf i n a l l y r e d u c e sr o u t i n gd e l a ya n di m p r o v e sn e t w o r kp e r f o r m a n c e k e y w o r d s ：p 2 pn e t w o r k ，o v e r l a yn e t w o r k ，p 2 pr o u t i n g ，p r 0 i m i t yn e i g h b o r s e l e c t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：壁3 ：壬聋 日期：年月日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：卫雌导师签名：二蝉 日期：年月日 第一章引言 第一章引言 p 2 p ( p e e r - - t o - - p e e r ) 技术是计算机网络技术研究领域的一个热点“。目前 i n t e m e t 中最常用的数据存储和资源访问模式是客户机朋艮务器( c l i e n t s e r v e r ) 模式。 服务器是拥有强大处理能力和高带宽的计算机，大量的数据集中存放在服务器上， 服务器在集中处理数据的同时可以对互联网上其他p c 进行服务，提供或接收数 据。对于一台与服务器联机并接受服务的p c 机来说，这台p c 机就是客户机。随 着i n t e m e t 技术的不断发展和应用的日渐广泛，越来越丰富的数据来源和越来越广 阔的数据分布范围，传统的客户机朋艮务器互联网架构显示出了一定的局限性，比 如对功能强大的网络计算机的需求，昂贵的带宽开销等等。在用户和应用需求的 推动之下，p 2 p 这场技术的革命被点燃，p 2 p 登上了技术的前台。 p 2 p 技术的本质思想是，整个网络结构中不存在中心节点( 或中心服务器) ，节 点( p e e r ) 与节点之间是平等关系，所拥有的权利和义务都是对等的，每个节点同时 扮演服务器、客户机和路由器三种角色，具有信息提供、信息消费和信息通讯三 方面的功能。简单的说，p 2 p 技术就是网络上的计算机直接进行通信，而不需要服 务器的支持。 事实上，早期的互联网应用方式中，有很多都体现了p 2 p 的思想，例如t e l n e t 、 u s e n e t 等。p 2 p 被认为是若干不同技术以及流行趋势的产物，下面是致使p 2 p 技 术发展的两个最重要的趋势：首先，某些新技术与软件工程的结合形成了一种将 工作分散的趋势。p 2 p 计算正是这种分散工作的趋势的自然结果。其次，从工程的 角度来看，在企业应用集成等因素的驱动下，过去十年渐渐形成了一种从集中的 单机系统转向分布式系统的趋势。在集中式的应用中进行控制是相对容易的，这 一点在一定程度上抑制了分布式潮流的发展。然而随着互联网的发展，以及b 2 b 商务交易方式的日益流行，全面的分布式计算也成为一种商业需求。为了提高网 络信息、带宽和计算资源的利用率，p 2 p 应用技术迅速的发展起来了。除了技术方 面之外的社会因素也是一个重要原因。毫无疑问，人们现在对p 2 p 技术的热切关 注起源于n a p s t e r 、s c o u r 和g n u t e l l a ，以及这些家族的其他成员产品。这些产品提 供了所谓的”k i l l e r a p p s ”功能，能够将p 2 p 技术中的一部分下放到客户端用户的 手中。正是这种第一手的体验，使得人们越来越关注p 2 p 技术的强大功能。 通过使用p 2 p 技术，用户可以轻易地在互联网上发布、查找和获取数据，共 电子科技大学硕七学位论文 享其他用户的文件和数据，也可以共享包括c p u 处理能力在内的其他计算机资源。 随着网络应用的不断丰富和用户需求的不断推动，p 2 p 技术被应用于广泛的技术领 域并极大地提高了因特网中信息、带宽和计算资源的利用率。目前，p 2 p 技术的应 用主要有：( 1 ) 文件共享：文件存储共享是p 2 p 技术在i n t e m e t 中最重要的应用。 p 2 p 技术使得任意两台相连接的计算机直接共享文档、多媒体和其他文件成为可能 p 。p 2 p 文件共享技术投入应用的最典型的例子就是n a p s t e r 和g n u t e l l a 。( 2 ) 分布 式计算：分布式计算是p 2 p 技术的另一个重要特征。最著名的例子是美国加利福 尼亚大学伯克利分校的基于分布式计算的搜索外星文明的s e t i h o m e 科学实验。 ( 3 ) 协同工作：p 2 p 技术的出现，使得互联网上任意两台p c 都可建立实时的连接， 实现一种安全的网上工作及联系的方式。( 4 ) 搜索引擎：能够开发出强大的搜索工 具是p 2 p 技术的又一个优势。它使用户能够深度搜索文档，而且这种搜索无需通 过w e b 服务器，可以不受信息文档格式和宿主设备的限制，达到传统目录式搜索 引擎( 只能搜索到2 0 3 0 的网络资源) 无可比拟的深度。g n u t e l l a 是其中的代 表。 从目前的应用现状来看，p 2 p 技术本身仍面临许多需要克服的困难，比如侵犯 版权问题，缺乏管理机制，安全问题等等。尽管如此，全球有关p 2 p 的研究层出 不穷，人们对p 2 p 寄予厚望的原因正是p 2 p 身后蕴藏着无比的创造力。因此，在 可以预见的未来，随着对p 2 p 研究的进一步深入和关注，p 2 p 必将进入一个飞速 发展的新时期。 对于p 2 p 技术，对象的定位和路由机制是研究中的热点也是核心的问题。目 前绝大多数的p 2 p 网络系统都是以覆盖网络( o v e r l a yn e t w o r k ) 方式构建的。覆 盖网络是基于现存的物理网络构建一个虚拟的层，其基本功能是实现系统中任意 两个节点之间的通信。覆盖网络节点之间的通讯是通过沿着覆盖网络逻辑连接传 递消息实现的，解决或缓解了底层网络的一些问题。覆盖网络实际上是一种分布 式系统的组织形式，构造覆盖网络的目的是为了使上层的分布式系统获得较好的 性能。为实现某一应用目标，若干节点互连形成一个逻辑网络，节点之间以p 2 p 方式交互，这种网络称为p 2 p 覆盖网络，简称p 2 p 网络。覆盖网络需要考虑：对 象定位( 名字_ 地址) 、路由以及网络拓扑三大基本问题。在覆盖网络中相邻的节 点，其在底层网络中可能并不相邻甚至相隔很远，这样导致覆盖网络中两个节点 间的路由延迟与其在底层网络中的路由延迟有很大的差异，在覆盖网络中相邻节 点间的一跳( o n eh o p ) ，可能在底层网络中需要跨越多跳才能到达目的地。如果覆 盖网络中节点路由表的组织不能真实反映节点在底层网络中的位置关系的话，将 第一章引言 最终影响到建立在结构化p 2 p 覆盖网络上的分布式p 2 p 应用的性能。所以，在覆 盖网络中，节点路由表的建立和维护十分关键，只有节点路由表项的内容正确地 反映节点之间在底层网络中的拓扑关系，才能最终减少应用层的路由延迟，提高 路由和网络应用的性能。p 2 p 网络中对底层物理拓扑结构( u n d e r l y i n gn e t w o r k ) s 1 上 层逻辑拓扑结构( o v e r l a y n e t w o r k ) 的匹配性的提高能减小路由延迟，提高网络系统 性能。 本文将在第二章介绍p 2 p 的网络结构，然后对几种典型的结构化p 2 p 路由机 制和非结构化p 2 p 路由机制进行介绍。第三章重点分析p 筛d 路由算法。基于对 p g r i d 算法的深入研究，在第四章提出一种新的基于邻近度的路由表维护算法 p n s p 饼d ，并在p g r i d 系统中实现。第五章给出了在模拟环境下的测试结果。 电子科技大学硕士学位论文 2 1p 2 p 网络结构 第二章p 2 p 路由算法 高度动态的p 2 p 网络有着复杂的拓扑结构，可以按照它们结构化的程度进行 划分。所谓结构化与非结构化的根本区别在于每个节点所维护的邻居是否能够按 照某种全局方式组织起来以利于快速查找。这样，我们可以将p 2 p 网络结构分为 以下三类：非结构化的，结构化的，松散结构化的。 1 非结构化的( u n s t m e t u r e a ) 在这种网络中，数据( 对象) 的存放是与覆盖网络拓扑结构完全无关的。节点在 存取数据的时候，不知道该数据的具体存放位置，只能通过一种“洪泛 ( f l o o d i n g ) 的机制发起随机的搜索请求，同时查询大量的节点，询问它们是否有符合查询条 件的文件。非结构化p 2 p 系统因它们创建o v e r l a y 拓扑结构的方式和在节点间分发 查询请求的方式的不同而不同。代表系统是早期版本的g n u t e l l a 。 这类网络的优点是节点的数量对系统来说完全透明，节点的加入和退出相对 自由，容易的适应高度变化的节点群。缺点是要想获得较高的数据查获率，必须 在系统中尽可能广的散播查询消息。由于这个原因，非结构化p 2 p 系统就要限制 节点的数目，因此系统被认为是不可扩展的。现在也在进行一些工作来增加非结 构化系统的可扩展性。 2 结构化的( s t r u c t u r e d ) 这种网络结构主要是作为解决非结构化系统所面临的不可扩展性问题的一种 尝试而被提出的。对象i d 和对象存放的节点间存在一个映射关系并以分布式路由 表的形式提供，对象的存放位置可以被精确定位。因此查询请求可以被高效的路 由到存放该数据的节点，避免了随机搜索的随意性。代表系统有p a s t r y ”、c h o r d p l 、 c a n 6 】、o c e a n s t o r e l 7 等。 结构化p 2 p 系统有很多优点：( 1 ) 效率高，目标的定位可以在确定的跳数( h o p ) 内完成，节点间通信的平均延迟较小；( 2 ) 流量小，每次路由转发只选取一个节点， 方向性强，不会像“f l o o d i n g 算法一样带来大量的网络流量；( 3 ) 扩展性好，节点 的路由表大小和路由所需的节点跳数随着系统规模的扩大呈对数级增长，通信性 能随着系统规模的扩大优美降级，具有良好的可扩展性；( 4 ) o - - i 靠性好，节点之间 第二章p 2 p 路由算法 不同路径数随系统规模的扩大呈对数级增长，在路由路径中有节点失效( n o d e f a i l u r e ) 的情况下，路由算法也可以绕过失效节点，选择另一条路经，到达目的地， 通信可靠性较高。可以看出，结构化p 2 p 系统综合考虑了系统的可扩展性、通信 的效率和路由可靠性，在三者之间作了有效的折衷，比前面介绍的非结构化p 2 p 网络结构更适合于构造大规模分布式存储系统。 但是，结构化的p 2 p 网络系统也有一些先天的不足之处。首先，由于路由表 被分散到了系统中的所有节点上，每个节点都要参与路由，如果大量节点频繁地 加入和退出，自由度过大的话，在一个高度动态的网络系统中，路由表的维护就 很困难，路由性能将受到很大的影响。所以，在这样的系统中，一般期望节点在 线的时间较长。其次，由于文件是根据f i l e d 来确定存放位置，这使得文件被保存 在系统中固定的几个节点，而不是存放在最需要该文件的节点处，数据的局部性 ( 1 0 c a l i t y ) 受到一定的影响。另外，由于结构化p 2 p 网络系统的设计思想是基于 标识的精确匹配，这使得大范围内的部分查询技术( p a r t i a lq u e r yt e c h n i q u e s ) 尚未 在这种系统中得到很好的实现。 3 松散结构化的( 1 0 0 s e l ys t r u c t u r e d ) 介于结构化和非结构化之间的一类系统。对象的位置是由对象存放时沿途留 下的“线索”( h i n t ) 来指引的。节点根据线索，一步一步尝试找到文件。由于文 件定位采用的是“尽量”( d ob e s t ) 策略，因此有可能找不到系统中存在的文件。 代表系统是f r e e n e t 。 关于非结构化的、结构化的以及松散结构化的网络以及它们分别采用的对象 定位和路由机制的优劣，研究界存在不同看法。我们认为采用何种对象定位和路 由机制要根据p 2 p 网络的应用而定。 2 2 非结构化p 2 p 路由机制 p 2 p 网络中节点间通信是通过在一系列中间节点之间传递消息来实现的。消息 传递路径构成了系统中各节点的连接关系，从而也就确定了p 2 p 网络的拓扑结构。 p 2 p 路由算法就是关于如何确定系统中任意两个节点之间消息传递路径的方法。所 以，非结构化p 2 p 网络系统中的路由机制称为非结构化p 2 p 路由算法。我们将在 下面介绍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 等几种非结构化p 2 p 路由机制。 电子科技大学硕士学位论文 2 2 1n a p s t e r n a p s t e r 采用的是部分集中式的节点组织结构。在n a p s t e r 中，节点在加入系 统时向中心服务器报告自己机器上的共享资源，中心服务器将这些资源的元数据 保存在机器上，并不真正拥有这些文件。当一个客户机想查找某个文件的时候， 向中心服务器发出文件定位请求，中心服务器根据自己掌握的文件元数据，查出 文件所在的节点，将该节点的位置信息返回给客户机。客户机直接与保存文件的 节点建立连接，下载文件。采用中心服务器的方式除了保证文件定位操作的效率 之外，还有一个原因是易于实现服务的商业化：通过控制文件元数据，可以向请 求文件定位服务的用户收取费用。n a p s t e r 是第一个成功实现商业化的p 2 p 软件， 到目前为止，已经拥有了数千万的用户。 图2 1n a p s t e r 系统结构图 其中s e r v e r 集中保存注册了的文件的元数据及文件的索引。c l i e n t 向中心服务 器发出文件定位请求，获得文件位置信息后直接与保存文件的节点建立连接，下 载文件。 2 2 2b i t t o r r e n t b i t t o r r e n t 和n a p s t e r 一样，也是采用的部分集中式的节点组织结构。b i t t o r r e n t 使用离散中心服务器( t r a c k e r ) 型的p 2 p 协议，目的在于高速分享大文件。提供 文件共享的节点制作一个包含文件和节点相关信息的“种子 文件( s e e d ) ，并将 种子上传到一个称为“t r a c k e rs e r v e r ”的中央服务器上。下载文件的节点先从 第二章p 2 p 路由算法 t r a c k e rs e r v e r 上获得所需文件的s e e d ，并向t r a c k e rs e r v e r 报告自己的相关信息( 口 地址、端口等) 。这样，下载上传者的p 将被t r a c k e r 和其他下载上传同一文件 的用户获得，这些节点间建立直接的连接，下载数据。与n a p s t e r 不同的是，一个 节点在下载的同时也为其他下载者提供自己已经下载完成部分数据的上传，节点 间存在一种协作的关系。通过从不同的节点间并行下载不同的文件块，不仅减轻 了提供文件共享的节点的压力，也使得下载速度大大加快。正是由于这个原因， b i t t o r r e n t 成为了现在互联网上最为流行的免费文件分享软件。 图2 2b i t t o r r e n t 系统结构图 提供文件共享的节点的s e e d 被上传到t r a c k e rs e r v e r ，用户c l i e n t 从t r a c k e r s e r v e r 上获得所需文件的s e e d ，节点间建立直接的连接，下载数据。同时自己也为 其他下载者提供自己已经下载完成部分的数据上传。 2 3 3g n u t e l l a 与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 中取消了以中央服务器为核心的目录 式结构，而是采用f l o o d i n g 算法( 广播方式) 按宽度优先原则搜索对象位置。为 了查找某个文件，节点首先向与自己相邻的所有活动节点以广播的方式发送一个 查询请求包。其他节点在接受到查询请求包之后，检查本地是否有符合条件的文 件：如果有，则按查询请求包的路径返回一个查询响应包，响应包中包括响应节 点的m 地址、服务端口等信息；如果没有，则节点再将该查询请求包向自己的邻 居转发，直到查询包的t t l ( t i m et ol i v e ) 计数器减为0 为止。如果发起查询的 电子科技大学硕士学位论文 节点成功地收到返回的响应包，则直接与目标节点建立连接，下载文件。图2 - 3 显示了一个典型的g n u t e l l a 查询过程。 2 3 4f r e e n e t 图2 3g n u t e l l a 查询过程 与g n u t e l l a 广度优先的“f l o o d i n g ”搜索机制不同，f r e e n e t 系统采用了一种深 度优先的“链式 ( c h a i n m o d e ) 文件发现机制。f r e e n e t 中的每个文件有一个全局 唯一的文件标识( f i l ei d ) ，系统中的每个节点维护着一张动态路由表，记录了系 统中部分节点的地址和这些节点上可能保存的文件。当节点收到一个文件查找信 息( 包含文件d ) 的时候，先查看本地是否有这个文件? 如果没有，则从本地路 由表里选取一个邻居节点，这个节点拥有的文件i d 是路由表中最靠近所查询i d 的，并将查询请求转发给那个节点；如果节点本地有所查询的文件，节点将文件 数据返回给向自己查询的节点。这样，文件数据将沿查询消息的来路返回给最初 请求文件的节点，并沿途留下副本。查询请求带有一个t t l 计数器，这使得一个 查询请求有可能找不到所需文件，是一种“尽量 ( d ob e s t ) 的查询方式。中间节 点在返回数据的时候都会宣称自己是数据源，以保持文件属主信息和存放位置的 “匿名性 ，这也是f r e e n e t 区别于其他系统的最大特点。图2 叫是一个典型的 f r e e n e t 文件定位过程。 第二章p 2 p 路由算法 n y 一一 图2 4f r e e n e t 文件定位过程 2 3 结构化p 2 p 路由机制 结构化p 2 p 网络系统中的路由机制称为结构化p 2 p 路由算法。下面我们将介 绍c h o r d 、c a n 、p l a x t o n 等几种典型的结构化p 2 p 路由机制以及他们各自的优缺 点。 2 3 1c h o r d c h o r d h l 是一种最简单的p 2 p 路由算法。它为每一个分布式数据保存一个 k e y v a l u e 对。c h o r d 路由协议仅仅支持一种操作：给定一个k e y ，把它映射到一个 节点上。每个节点和数据对象通过c o n s i s t e n th a s h i n g 方法都被分配给一个m 位的 d ，分别为n i d 和k e y 。k e y 是这样被映射到节点上的：节点按照i d 被排列成以 2 m 为模的环，k e yk 被分配给节点t d ( n t d ) 空间内第一个n i d 等于或者紧接着k e y 的节点。这个节点被称作k 的后继节点。当n 节点加入到网络中时，原来被分配 给n 的后继节点的k e y 将会被分配给1 1 。当节点n 退出网络时，所有分配给它的 k e y 都要被重新分配给它的后继节点。每个节点保存一张指向所有活动节点的 “f i n g e rt a b l e ，i d 为n 的节点的“f i n g e rt a b l e 表中第i 项指向i d 空间中n 之后 至少1 1 + 2 i 1 的节点。当某个客户查找文件k 时，如果n 不知道k 的后继节点，则n 在其f i n g e rt a b l e 中找n i d 最接近于k 的节点，请求该节点查询它的f i n g e rt a b l e 以 找到n i l ) 最接近k 的节点，重复此过程，查询请求沿逻辑环跳跃并传递到存放文 件的节点。为了有效的路由，一个c h o r d 节点大约需要0 0 0 9 n ) 个其他节点的信息。 c h o r d 的优点是简单，可证明的正确性，但是它并不能保证在最差情况下的性 电子科技大学硕士学位论文 能。值得注意的是c h o r d 中o v e r l a y 的名字空间距离与底层的物理网络距离并没有 联系，这样就使逻辑上相邻的一跳在物理网络中有很长的路由距离成为可能。图2 5 是c h o r d 系统中一个节点n 8 的f i n g e r t a b l e 示意图，其中点线表示n 8 查找i d 为5 4 的文件的过程。 f i n g e rt a b l e 口fn b 2 3 2c a n 图2 _ c h o r d 系统f i n g e rt a b l e 示意图 、肆4 g 8 n 8 1 6 n 1 4 n 1 4 n 1 4 n 2 1 n 3 2 n 4 2 c a n ( c o n t e n ta d d r e s s a b l en e t w o r k ) 一是另一个可扩展的，容错的，完全自 适应的p 2 p 结构化路由算法设计。每个对象会被均匀的哈希( h a s h ) 到d 维空间 中的一点。这个d 维的空间完全是逻辑上的，与物理坐标系统没有任何关系。当 一个节点加入时，它会随机的选择d 维空间中的一点，它将会负责它所属的这个 区域的一半，存储所有对象i d 属于这个区域的数据对象。例如，第一个加入的节 点n 1 负责整个空间区域，第二个加入的节点n 2 将整个空间区域分成2 部分，负 责其中的一部分。第三个加入的节点n 3 将把n 1 区域( 如果随机点是在这个区域) 或者n 2 区域分成2 部分，负责其中的一部分。每个c a n 节点维护一个坐标路由 表，里面保存了坐标空间中此节点的邻居的虚拟坐标区域和它们的i p 地址。c a n 第二章p 2 p 路由算法 查询消息中包含了目的地的坐标。消息到达的节点根据节点的邻居坐标集将消息 转发到邻居中坐标离目的地坐标最近的节点。在一个n 等分的d 维空间中，每个 节点维护2 d 个邻居的信息，查询的平均路由路径长度为( d 4 ) ( n l d ) 。c a n 的优 点是具有很好的可扩展性，但是采用c a n 的系统存在安全性问题，并且设计者们 还在考虑扩展算法以适应变化的数据对象。c a n 不仅可用于p 2 p 系统，还可用于 大规模存储管理系统，例如o c e a n s t o r e t j ，f a r s i t el o j ，a n dp u b l i u s ”1 ，这些系统都 要求在大型分布式存储底层设施中能有效的插入和获取数据。c a n 的另一个潜在 应用在于域名解析服务。与d n s 不同，它并不施加任何形式的等级命名结构的限 制来获得可扩展性。 不足的是c a n 中的对象是不可变的，如果它们的值改变了，则必须重新插入 该对象。并且与c h o r d 一样，c a n 也没有考虑o v e r l a y 路由中的实际网络距离，所 以路由中的逻辑距离可能开销很大。c a n 的一个最重要的优点就是，由于节点的 增加算法简单，所以它可以适应动态变化的环境。图2 6 是一个2 维空间分布示 意图；图2 7 、图2 8 分别是2 维空间中节点7 加入前和加入后空间的分布情况。 ， 、 - 疆o 。幽8 s 确r f u a tf o o t 兹韩薅t ：嘲t 图2 62 维空间中的5 个节点 62 卜 jl； 气 ， 一 l 7 一， 岳： 卜 ，1s 一 图2 72 维空间中节点7 加入以前图2 82 维空间中节点7 加入以后 电子科技大学硕士学位论文 2 3 3p l a x t o n n n l 在p l a x t o n w 中，每个节点都扮演相同的角色：服务器( 存储对象) ，路由器( 转 发消息) ，客户( 发出请求) 。系统中每个节点拥有一个全局唯一的节点标识号 n i d ( n o d ei d e n t i f i e r ) ，n i d 是一个b 进制的l 。位整数。p l a x t o n 的每个节点有一个 本地路由表，我们称作邻居节点表( n e i g h b o u rm a p s ) ，依据它递增地路由o v e r l a y 消息到目的节点( 如：宰水宰6 = 宰木9 6 = * 3 9 6 = 4 3 9 6 其中幸表示通配符) 。这种方 法类似于c i d ri p 地址分配体系结构中的最长前缀路由。节点n 的路由表有l n 行， 每一行中有i d 的基数个入口。其中第j 行的第i 个入口存放着以“i ”+ s u f f i x ( n ，i 1 ) 结尾的离该节点最近的节点的i d 和地址。例如，节点3 2 5 a e 路由表中第4 层的 第9 个入口中存放的是离节点3 2 5 a e 最近的且节点i d 是以9 5 a e 结尾的一个节 点通过路由一个消息到对象o 的“根节点( r o o tn o d e ) ”宣布它存储有对象o 。在定 位查询请求时，节点发送消息给对象。目标为对象o 的消息最初是被路由到o 的 根节点。在此过程中的每一步，如果消息遇到了保存了目标对象的地址映射的节 点，则消息被直接重定向到保存对象o 的节点，否则消息被进一步转发。如果消 息到达了此对象的根节点，则能保证找到该对象的地址映射。根节点对保证能找 到对象地址映射进而找到对象有重要作用。这样的定位和路由机制使得p l a x t o n 网 络中的节点能够定位并且发送消息到指定的节点。 p l a x t o n 消息传递如图2 9 所示，消息从4 4 4 4 节点到4 1 5 6 。4 4 4 4 节点在自己 路由表中第一列查找以6 结尾的节点号，选定6 5 3 6 。然后6 5 3 6 节点在其路由表第 二列查找以5 6 结尾的节点号，选定5 4 5 6 。依次类推，路由消息经过路径 4 4 4 4 6 5 3 6 5 4 5 6 0 15 6 415 6 并最终到达根节点。 图2 9t a p e s t r y 路由方法( b = 8 ，l n = 4 ) ( 数字) 第二章p 2 p 路由算法 1 p l a x t o n 的优点 简单错误处理：由于路由仅要求节点i d 匹配一定的后缀，所以当有节点失效 时可以路由到其他具有相同后缀的节点。 可扩展：p l a x t o n 是非集中式的，所有的路由都可以由本地的数据完成。系统 没有一个集中的节点，所以唯一可能的瓶颈在于根节点。 开发局部性：对一个本地对象的查询请求可以根据查询对象的指针很快的被 路由到目的地。 成比例的路由距离：p l a x t o n 证明了整个网络中一个消息定位和路由阶段所穿 过的距离与底层网络中的网络距离是成正比的，保证了p l a x t o no v e r l a y 上的路由 的合理性。 2 p l a x t o n 的缺点 根节点：在定位机制中，由于所有节点都依赖根节点提供对象的位置信息， 所以根节点可能构成单点失效。 全局信息：为了得到一个全局唯一的对象标识符和根节点的映射，p l a x t o n 机 制在构造p l a x t o n 网络时要求知道全局信息。这个全局信息很大程度上复杂化了节 点的加入和离开的过程。 缺乏适应的能力：虽然定位机制开发了很好的局部性，但是p l a x t o n 系统缺乏 适应动态查询模式的能力，比如远距离热点。p l a x t o n 的主要缺点就是它算法的静 态特性。这个静态特性意味着插入必须用全局信息来重新计算对象和其根节点的 映射。 2 3 4t a p e s t r y f 1 1 1 t a p e s t r y t “1 是一个应用极广泛的可扩展、高容错、自适应、自管理的覆盖网络。 t a p e s t r y 的核心定位和路由机制和p l a x t o n 是相似的。在t a p e s t r y 网络中，每个节 点能按照2 3 3 中介绍的路由算法转发消息。节点的每个邻居图被组织成路由层次， 每个层次中的入口存放指向满足前缀要求的并且在物理网络距离上最近的一些节 点的集合。每个节点同时也维护一个指向邻居节点的b a c k p o i n t e rl i s t 。t a p e s t r y 中 节点存储了数据对象的所有副本的位置信息来增加其语义的灵活性。同时t a p e s t r y 机制还允许不同的应用定义自己的操作符，每个对象除了距离度量还可以选择基 于特定应用的度量。t a p e s t r y 节点通过u d p 包来周期性的b a c k p o i n t e r s 指向的其他 邻居节点发送h e a r b e a t s 。这只是一个简单的“h e l l o 消息，用来检测邻居节点表 电子科技大学硕士学位论文 的信息是否依然可用于路由。通过检测消息到达的每一个节点我们可以很快的检 测出错误和失效的邻居节点。t a p e s t r y 通过在一个合理的时间间隔内再次给失效节 点发送探测消息来确定它是否被修复好，这样避免了失效节点再次加入带来的开 销。如果该节点此时没有被修复好，则把它从路由映射中删除，选择一个新的节 点替代它。t a p e s t r y 用给一个对象分配多个根节点来避免p l a x t o n 中单点失效的问 题并集中于支持分布式方式下的动态的操作。 t a p e s t r y 解决了p l a x t o n 算法静态特性所带来的缺陷，支持分布式下的动态操 作。在c h o r d ，p a s t r y ，c a n 几种算法中，t a p e s t r y 是唯一一个允许用户控制原始 数据的位置和一致性，仅允许系统操纵和控制对象的索引的机制。同时t a p e s t r y 提供快速发现环境变化并修改节点的组织以适应的机制。图2 一 1 0 是单个t a p e s t r y 节点的示意图( 注：t a p e s t r y 节点0 6 4 2 作为客户，服务器和路由器的完整组成， 包括：邻居表( n e i g h b o u rm a p ) ，热点监控器( h o t s p o tm o n i t o r ) ，对象定位指针( o b j e c t l o c a t i o np o i n t e r ) ，存储的对象。) 。 i 嘲腿脚盔弱蜘哆 2 翊姆瓒崞出函 。j r 0 弘：x 0 * 2蕊o ：磁c ： 孓 1 6 4 1 ：x i * 2珏l 二：z 赶一： ，一o 。 2 够：垃 !碰二：t g ：l x _ ： 一 3 6 4 1 ：r 3 4 2x x 3 2 ：茁口d ：三，：! ，一j 4 6 4 2 ：饕私：斟： x x - f 1 。 5 6 4 2 ： !卫d ：= 缸：，一一_ ：一。一、 6 6 4 2 ：z 酣!蕊6 2 ：墨& 6 ： 、- ，年 7 6 4 1 ：x 7 4 2z x 7 2 ：工取c，一 一 二oqo 卿 图2 1 0 单个t a p e s t r y 节点的示意图 2 2 5p a s t r y p a s t r y t l 的定位和路由机制和t a p e s t r y 有很多相似之处。它们最主要的区别在 于：第一，p a s t r y 中对象的复制不受所有者的控制，对象的副本放在多个节点号 n i d 与对象号o l d 最相近的节点中。第二，t a p e s t r y 在路由路径上的所有节点上 存放了对象地址的索引，而p a s t r y 则是利用对象的o i d 直接路由到最近的一个副 本处。虽然为一个对象在不同节点保存多个副本能降低定位延迟，但是这是以存 国囡 第二章p 2 p 路由算法 储开销为代价的，并且带来了一系列的安全性、机密性、一致性等方面的问题。 最后，在t a p e s t r y 中，分析证明其路由距离是明确的，保证能找到存在且可获得的 数据对象。而p a s t r y 与t a p e s t r y 的“s u r r o g a t er o u t i n g ”算法的相似性使得p a s t r y 中路由的逻辑跳数的限制更弱。p a s t r y 是广域网中p 2 p 应用的个完全非集中式 的、可扩展的、自适应的分布式对象定位和路由机制。它能自动的适应节点的加