（计算机应用技术专业论文）pastry网络模型的路由机制及改进.pdf

西华大学硕士学位论文 p a s t r y 网络模型的路由机制及改进 计算机应用技术专业 研究生于忠涛指导教师刘兴伟 摘要 今天p 2 p 应用的带宽已经超过w w w ，成为占有互联网带宽最多的部分。 对等计算在产业界迅速普及的同时，研究界也及时跟进，在p 2 p 系统的设 计方法和发展方面进行了广泛而深入的研究。由于完全分布式系统中的随机 搜索造成扩展性差的缺陷，所以目前大量的研究集中在如何构造结构化的 p 2 p 系统上，其中典型的是p a s t r y 网络模型。它是微软研究院提出的可扩展 的分布式对象定位和路由协议，采用基于d h t 的路由机制，由p a s t r y 节点 组成的自组织的结构化覆盖网络( o v e r l a yn e t w o r k ) 。p a s u y 路由算法能有效 地检索到结果，同时保证搜索步数在0 0 0 9 n ) l 拘范$ 内( n 为节点总数) ，实 现了可扩展性搜索。由于它是架设在结构化p 2 p 网络上，所以p a s t r y 搜索 算法对节点的限制条件过多，需要严格控制网络拓扑和文件存储位置。因此 可以对p a s t r y 的路由机制进行改进，以进一步提高其路由和搜索能力。 本论文主要研究内容和特色如下： ( 1 ) 通过对国内外相关文献资料分析，以及对基于d h t 的路由机制特 别是传统p a s t r y 路由算法迸行了深入的研究，提出一种改进的p a s t r y 路由算 法。 西华大学硕士学位论文 ( 2 ) 对改进算法的网络拓扑结构、节点的加入和失效处理方式、改进 p a s t r y 的路由和搜索机制以及s u p e r 节点的应用和备份方法都进行研究。 ( 3 ) 在j x t a 平台上实现本文的改进算法，同时对本文设计的算法进 行性能分析和实验，结果表明：较好地解决了负载平衡问题；通过索引节点 的引入，提高了查准率和查全率：提高了查找速率：减少网络上的消息量； 减少节点加入时的复杂度。 关键字：p 2 p ：d h t ：p a s t r y ：路由算法：j x t a 西华大学硕士学位论文 r e s e a r c ho ns e m a n t i cw e bs e r v i c ed i s c o v e r y s p e c i a l i t yc o m p u t e ra p p l i c a t i o nt e c h n o l o g y m a s t e rc a n d i d a t ey uz h o n g t a o a b s t r a c t i nt h ec i ：l r r e n ti n t e r a c t , t h ep 2 pa p p f i c a t i o nt i e s 印t h em o s tn e t w o r kr e s o u l s e ， w h i c hi sm o r et h a nw wt h ep 2 pd e v e l o p m e n td o e s n 、o n l yi nb u s i n e s sb u ta l s o i ns c i e n t i f i cr e s e a r c h b e c a u s et h er a n d o ms e a r c he x i s t st h el i m i t a t i o no fe x t e n d i n g c h a r a c t e r i s t i ci nt h ec o m p l e t e n e s sd s t r i b m n gn e t w o r k s ，t h em o s to f r e s e a r c hf o c u s o i lh o wt ob u i l ds t r u c t u r a lp 2 ps y s t e m , t h e r e p r e s e n t a t i v e s t o n ei sp a s t r y t h e r e i n t o p a s t r yi sad h tr o u n d i n gp r o t o c o lw h i c ha c h i e v e se x t e n d i n gd i s t r i b u t i n g l o c a l i z a t i o n t h ep a s t r yr o u n d i n ga r i t h m e t i ct h a ts e a r c b st h ei n f o r m a t i o nr c s o u r c e c a na s s u i ct h e r o u n d i n gh o p s i sl e s st h a no ( i o g n ) ( ni st h en u m b e ro f n o d e s ) p a s t r yi si nc o m p l e t e n e s ss t r u c t u r a lp 2 pn e t w o r k s 。s ot h el i m i t i n gc o n d i t i o n i sv e r ys t r i c t w ec h o o s ei m p r o v i n gt h et r a d i t i o n a lp a s t r yr o u n d i n ga r i t h m e t i ct o a d v a n c et h ec a p a c i t yo fr o u n d i n ga n ds e a r c h i n g t h em a i nr e s e a r c hc o n t e n t sa n df e a t u r eo ft h i sp a p e ra r ea sf o l l o w ： ( 1 ) t h i sp a p e ri n t r o d u c e s t h ec o r r e l a t i v ep 2 pk n o w l e d g e ，a n d g e t st h e c h a r a c t e ro fe v e r yp 2 pn e t w o r km o d e lb o r nc o m p a _ d n gt oe a c ho t h e r a tt h es a m e t i m ee v e r yd h t r o u n d i n gm e c h a n i s m i sr e s e a r c h e d ( 2 ) i nt h i sp a p e r , an e wr o u t i n ga l g o r i t h mi sp r o p o s e 垃, b a s e do nu n s t r u c t u r e d h y b r i dn e t w o r k i tu s e si n d e xn o d ea n ds e a r c hn o d e ，a n dr e a l i z e saw e l l * o r d e r e d s e a r c hf x o ma # o b a lv i e w t h en e t w o r k sm o d e lo ft h en 哪r o u t i n ga l g o r i t h m ；t h e m e t h o dh o wt od e a lw i t hn o d e sa d d i n ga n dl a p s i n gi si n t r o d u c e di nd e t a i l m 西华大学硕士学位论文 ( 3 ) t h ep a p e ri n t r o d u c e s t h ep r o c e s sh o wt oa c t u a l i z et h e i m p r o v i n g a l g o r i t h ma n dl i s t ss o m ep r o g r a mp a r a g r a p ha n ds o m eu i ( u s e ri n t e r f a c e ) w h i c h 锄r e p r e s e n tt h ee h a r a c t e r i s t i co fi m p r o v i n ga l g o r i t h m t h ep a p e ri n d i c a t e st h a tt h e n e wr o u t i n ga l g o r i t h mi sm o l r ge f f e c t i v ef o r mt w om e t h o d sw h i c ha r ei nt h e a b s t r a c ta n di nt h ee x p e r i m e n t k e y w o r d s ：p a s t r y ；p 2 p ；r o u t i n ga l g o r i t h m 0 x t a 西华大学硕士学位论文 申明 本人申明所呈交的学位论文是本人在导师指导下进行的研究工作及取 得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得西华大学或其他教育机构 的学位或证书而使用过的材料。与我同工作的同志对本研究所做的任何贡 献均己在论文中作了明确的说明并表示谢意。 本学位论文成果是本人在西华大学读书期间在导师指导下取得的，论文 成果归西华大学所有，特此申明。 作者签名：奇专1 醑，7 年午月计日 翩签名壶降酽毕月扩日 西华大学硕士学位论文 1绪论 1 1p 2 p 技术 p 2 p 是p e e r - t o p e e r 的缩写。p e e r 在英语里有“( 地位、能力等) 同等者”、 “同事”和“伙伴”等意义。因此，p 2 p 也就可以理解为“伙伴对伙伴”盼意思， 或称为对等联网。目前，业界对p 2 p 的定义还没有一个标准的说法，i n t e l 将p 2 p 技术定义为“通过系统间的直接交换达成计算机资源与信息的共享”， 这些资源与服务包括信息交换、处理器时钟、缓存和磁盘空间等。m m 则 对p 2 p 赋予了更广阔的定义，把它看成是由若干互联协作的计算机构成的 系统并具备如下若干特性之一：系统依存于边缘化( 非中央式服务器) 设备的 主动协作，每个成员直接从其他成员而不是从服务器的参与中受益；系统中 成员同时扮演服务器与客户端的角色：系统应用的用户能够意识到彼此的存 在而构成一个虚拟或实际的群体1 1 1 【2 l 。 互联网系统的计算模式正在从客户服务器向对等模式( p a p ) 转变。对等 计算的核心思想是所有参与系统的节点处于完全对等的地位，没有客户端和 服务器之分，也可以说每个节点既是客户端又是服务器端；既向别人提供服 务，也从别人那里享受服务。实际上对等计算的概念很早以前就有入提出， 但是一直没有受到广泛重视。主要原因是没有实际运行的系统作为背景，产 业界和研究界都普遍认为在大多数情况下，还是客户服务器模式更为合理。 1 9 9 9 年n a p s t e r 推出后迅速普及，后来又出现了g n u t e l l a 、f r e e n e t 、k a t _ a a 、 b i t t o r r e n t 和s k y p e 等。今天f 2 f 应用的带宽已经超过w w w 。成为占有互 联网带宽最多的部分。对等计算在产业界迅速普及的同时，研究界也及时跟 进，在p 2 p 系统的设计方法和发展方面进行了广泛而深入的研究，诞生了2 个专门的国际会议：i p t p s ( i n t e m a t i o n a lw o r k s h o po np e e r - t o p e e rs y s t e m s ) 和瑶e ep 2 p 。其他相关国际会议：u s e n i xo s d i 、a c ms o s p 、a 例 s i g c o m m 、u s e n i xn s d i 、a c me u r o s y s 等。因此可以说p 2 p 是目前网 络和分布式计算机领域乃至整个计算机系统研究领域关注的焦点。 1 2p 2 p 资源发现与路由机制 在p 2 p 的环境下进行资源定位是p 2 p 相关研究中的热点也是核，t l , 的问 西华大学硕士学位论文 题。目前已有的p 2 p 资源定位的方法如下： ( 1 ) 完全分布式p 2 p 网络的搜索技术。完全分布式p 2 p 网络指的是这样 一类网络：节点采用随机的方法或采用启发策略加入网络，网络拓扑随着节 点的变迁和网络通信的进行而发生演变，c , n u t e u a 、k a z a a 、f r e e n e t 等属于这 类网络。在完全分布式p 2 p 网络内进行搜索分为两类： _ 盲目法搜索( b l i n ds e a r c h ) 。这类搜索就是从一个随机节点出发定位目标 节点，根据遍历方法的不同，搜索方式又分为宽度优先遍历( b f s ) 和深 度优先遍历( d f s ) 。其中最具有典型代表意义的是g n u t e l l a 的宽度优先 遍历搜索，但是b f s 的扩散性寻址导致消息数量呈指数增加，而d f s 的回溯性导致耗时过长，并且两者都缺乏全局视角。 根据搜索历史对索引记录进行适应性调整如k a i o g e r a k 提出各个节点记 录以前接受的请求和应答，并根据这种对应的关系作为对后来的路由过 程的启发 2 1 。c u e n c a 给出一莉定期交换路由表的方法使得每个节点都获 知网络内部的一个子集的文档分布情况，从而达到迅速定位目标资源的 目的脚。c r e s p o 通过记录邻居的文档信息来尽量将查询路由到相关的节 点，而减少不必要的通信量。但是这些方法都缺乏全局视角，为了覆盖 更多的节点，牺牲较大的通信代价和主机计算代价，对于稀疏资源的定 位更是如此。 ( 2 ) 结构化p 2 p 网络中的搜索技术。它是通过严格控制网络拓扑和文件 存储位置，能有效的检索到结果同时保证搜索步骤在0 0 0 9 n ) 地范围内( n 是 节点总数1 ，实现了可扩展性搜索，但搜索算法对节点地限制条件过多，需 要严格控制网络拓扑和文件存储位置，它适用运行于企业内部网。在结构化 p 2 p 网络中，每个节点被动态的分配一个虚拟地址，同时用一个关键 字( k e y ) 来表示其可提供的共享内容。取一个哈希函数h c k e y , u r l ) ，网络 中节点相邻的定义是哈希值相邻发布信息的时候就把 - - 元组 发布到具有和h ( k e y , u r l ) 相近地址的节点上去，其中u r l 指出了文档的 存储位置，资源定位的时候就可以快速根据h ( k e y ，o r l ) 到相近的节点上 获取二元组。这就像我们平时在哈希表中查找数据一样，索引称为分布式的 哈希表( d h t , d i s t r i b u t e dh a s ht a b l e ) 。此类搜索方式典型的技术有内容访问 2 西华大学硕士学位论文 网络( c a n ，c o n t c n t - a d d r e s s a b l cn e t w o r k ) 、相容哈希( c h o r d ，c o n s i s t e n t h a s h i n g ) 、p a s t n r 和t a p e s t r y 。由于给定存储信息的索引k e y ，d h t 能高效 定位到该索引的信息。但是它面临本身固有的问题一负载均衡不易、网络拓 扑维护代价大、k e y 的同步维护困难等【i 。这些问题在设计d h t 文件共享 系统的时候都是无法避免的 ( 3 ) 混合式p 2 p 网络中基于兴趣( 地域) 局部性优化的p 2 p 搜索技术。因 为它是基于这样的原则：每个节点都表现出某些可以捕捉到的兴趣，相近兴 趣的节点保存的内容和提交的查询也援近。通过挖掘每个节点的兴趣，把节 点按照兴趣关系组成网络，使得兴趣相近的节点在网络中比较近。目前主要 的研究是按照用户提交的检索行为来划分用户的兴趣的。这种按兴趣组成的 网络表现出和社会网络相近的所谓“小世界( s m a l l w o r l d ) ”特性。这些特性用 于提高捡索效率证明是有效的；但是这类研究没有充分地挖掘节点共享的内 容所体现地节点的兴趣，用户提交的查询只是反映用户共享兴趣的一个部 分，尤其对于提供大量信息的节点，所产生的查询只是反映其存储内容的一 个很小的子集，因此需要去挖掘其共享内容所反映的兴趣，从而使得网络中 的其他节点在需要时能够高效地检索这些内容嘲。b a w a 提出通过节点共享 的内容来挖掘节点的兴趣。它使用类似于分布式检索的方法，由代理节点定 期采集各个共享节点共享的内容索引，然后通过聚类的方法把这些索引分成 若干话题区域( c o p i cs e g m e n t a t i o n ) ，每个节点属于一个或两个区域。对每次 查询，也通过计算查询和各个话题区域中心的距离来判断该查询所属的区 域，路由查询时先路由到该哈希所属的目标区域，然后再在目标区域中进行 广播1 6 。这种方法的不足之处在于代理节点负担重，而且共享的内容很难确 定地划分为独立的区域，往往每个节点属于多个t o p i c s 。此外s c h m i t z 按照 预先指定的分类标准对用户进行分类，并使用这些分类来启发路由，把查询 传递到相同别的节点中去，从而减少传输代价 7 1 。但是这类的标准需要预先 定义，不够灵活，同时也无法动态地反映p 2 f 共享网络中的内容更替。 1 2 1c h o r d 麻省理工学院设计了一种分布式的可扩展的查找和路由协议c h o r d ， 3 西华大学硕士学位论文 c h o r d 实现了这样一种操作；给定一个关键字( k e y ) ，将k e y 映射到某个结点。 如果给对等网络应用的每个数据都分配一个k e y ，那么对等网络中的数据查 找问题就可以用a m r d 很容易地解决了。 c h o r d 采用了相容哈希【1 0 1 的一种变体为结点分配关键字。相容哈希有几 个很好的特点，首先是哈希函数可以做到负载平衡，也就是说所有的结点可 以接收到基本相同数量的关键字。另外，当第n 个结点加入或者离开网络时， 只有1 n 的关键字需要移动到另外的位置。 c h o r d 迸一步改善了相容哈希的可扩展性。在c h o r d 中，结点并不需要知 道所有其他结点的信息。每个q 旧r d 结点只需要知道关于其他结点的少量的 “路由”信息。在由n 个结点组成的网络中，每个结点只需要维护其他o o o g r ) 个结点的信息，同样，每次查找只需要0 0 0 9 条消息。当结点加入或者离 开网络时，c h o r d 需要更新路由信息，每次加入或者离开需要传递o ( 1 0 9 条消息。 下面我们看看c h o r d 如何进行关键字查找。在c h o r d 中，每个结点维护少 量的路由信息，通过这些路由信息，可以提高查询的效率。如果b 是关键字 和结点标识符的位数( 采用二迸制表示) ，那么每个结点只需要维护一张最多 b 个表项的路由表，我们称之为指针表( f i n g e rt a b l e ) 。结点n 的查找表的第i 个 表项包括的是s = s u c e e s s ( n + 2 6 ) ( b = “1 ) 这里l = i - - m 并且所有的计算都要 进行m o d2 b ，s 称为结点n 的第i 个指针，我们用n f i n g e r i n o d e 表示，指针表 中的其他项的含义如表1 1 所示。 表1 1c h o r d 符号介绍 符号 定义 k 1 f i n g e q k i s t a r t ( n + 2 ) r o o d2 6 1 = k - b 缸t e r v a l f i n g e r t k l s t a n , 丘n g e r k + 1 1 s t a 矗】 n o d e 第一个大于等于n f i n g e r k 1 s t a r t s u c a e s s o r 标识符环中的下一个节点；f i n g e r i n o d e p r e d e c e s s o r 标识符环中的前一个节点 4 西华大学硕士学位论文 以图1 3 为例，结点1 的指针表的表项应该分别指向标识符2 、3 、5 。而标 识符2 的后继是结点3 ，因为它是2 之后的第一个结点，标识符3 的后继是结点 3 ，而标识符5 的后继是结点0 。 f i g 1 3t h ep 镕o f ( 1 0 r dr o u t i n g 图1 3 c h o r d 路由过程 这一方案有两个重要的特性：首先，每个结点都只需要知道一部分结点 的信息，而且离它越近的结点，它就知道越多的信息。其次，每个结点的指 针表通常并不包括足够的信息可以确定任意一个关键字的位置。例如，图1 3 中的结点3 就不知道关键字1 的位置，因为1 的后继结点信息并没有包含在结 点3 的指针表中。 当结点n 不知道关键字k 的后继结点时怎么办? 如果n 能够找到一个络 点，这个结点的标识符更接近k ，那么这个结点将会知道该关键字的更多信 息。根据这一特性，n 将查找它的指针表，找到结点标识符大于k 的第一个结 点j ，并询问结点j ，看j 是否知道哪个结点更靠近k 。通过重复这个过程，n 5 西华大学硕士学位论文 最终将会知道k 的后继结点。 仍然考虑m 1 4 q ，的例子，结点3 需要查找关键字1 的后继结点。由于1 属 于循环区间【7 ，3 】，属于3 f i n g e r 3 i n t e r v a l ，因此结点3 查找其指针表的第3 项， 返回0 。由于0 在l 之前，因此结点3 将要求0 去寻找关键字1 的后继结点。依此 类推结点0 将查找它的指针表并发现1 的后继结点是1 本身，于是结点o 将告 诉结点3 结点1 是它要找的结 点。 下面介绍 c h o r d 节点的 加入：( 1 ) 初始 化新结点的指 针表。假设结， 点n 在加入网 络之前通过某 种机制知道网 f i g1 4t h ep a r t i t i o no f d e s c a r t e sc o o r d i n a t er o o m a g e 图1 4 笛卡儿坐标空间的区域划分 络中的某个结点1 1 。这时，为了初始化n 的指针表，n 将要求结点n 为它查找 指针表中的其他表项。 佗) 更新现有其他结点的指针表。结点加入网络后将调用其他结点的更新函 数，让其他结点更新其指针表。( 3 ) 从后继结点把关键字传递到结点n 。这 一步是把所有后继结点是n 的关键字转移到n 上。整个加入操作的时间复杂度 是0 0 0 9 2 n ) ，如果采用更复杂的算法【1 l l ，可以把复杂度降低到o ( 1 0 9 n ) 。 下面介绍c h o r d 节点失效处理，在对等网络中，某个对等结点随时可能退 出系统或者发生失效，因此处理结点失效是一个重要的问题。在c h o r d 中， 当结点n 失效时，所以在指针表中包括n 的结点都必须把n 替换成n 的后继结 点。另外，结点n 的失效不能影响系统中正在进行的查询过程。 在失效处理中最关键的步骤是维护正确的后继指针。为了保证这一点， 每个c h o r d 结点都维护一张包括r 个最近后继的后继列表。如果结点n 注意到 它的后继结点失效了，它就用后继列表中第一个正常结点替换失效结点。 6 西华大学硕士学位论文 1 2 2内容访问网绍f c a n ，c o n t e n t - a d d r e s s a b l en e t w o r k ) 伯克立和a t & t 设计了另外一种基于d h t 的路由算法c a n 。c a n 可 以在i n t e r a c t 规模的大型对等网络上提供类似哈希表的功能。c a n 具有可扩 展、容错和完全自组织等特点。 c a n 类似于一张大哈希表，c a n 的基本操作包括插入、查找和删除( 关 键字。值1 对。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 维笛卡儿坐标空 间实现其数据组织和查找功能。整个坐标空间动态地分配给系统中的所有结 点，每个结点都拥有独立的互不相交的一块区域。图1 4 给出了一个2 维的 f o ，1 】x 【o ，1 1 的笛卡儿坐标空间划分成三个结点区域的情况。虚拟坐标空间采 用下面的方法保存( 关键字，值) 对。当保存( k 1 ，v 1 ) 时，使用统 一的哈希函数把关键字k 1 映射 成坐标空间中的点p 。那么这个 值将被保存在该点所在区域的 结点中。当需要查询关键字k 1 对应的值时，任何结点都可以使 用同样的哈希函数找到k 1 对应 的点p ，然后从该点对应的结点 取出相应的值。如果此结点不是 发起查询请求的结点，c a n 将 负责将此查询请求转发到对应 ( - b ) j t f - 一 x h ，y ) f i g 1 - 5a ne x a m p l e o fc a n s e a r c h i n g 图1 - 5 c a n 查找实例 的结点。因此，有效的路由机制是c a n 中的一个关键问题 7 西华大学硕士学位论文 下面介绍c a n 中的路由机制，c a n 中的路由机制非常简单，只需要计 算目的点的坐标，然后寻找从发起请求的点到目的点的一条路径就可以。首 先我们需要给出两个结点区域邻接的含义，在d 维坐标空间中，当两个区域 在d 一1 维上都覆盖相同的跨度而在另一维上相互邻接，则称这两个区域邻 接。例如，图1 4 中a 、b 、c 是相邻节点，但是将区域c 上下平分，多出 的区域设为d ，则a 与d ，b 与d 就不是相邻节点。 每个c a n 结点都保存一张坐标路由表，其中包括它的邻接结点的口地 址和虚拟坐标区域。每条c a n 消息都包括目的点坐标。路由时结点只要朝 着目标结点的方向把请求转发给自己的邻接结点就可以了。图1 5 给出了查 找过程的一个简单的例子。如果一个d 维空间划分成n 个相等的区域，那么 平均路由长度是( d 4 x n l d ) ，每个结点只需要维护2 d 的邻接结点信息。这个 结果表明c a n 的可扩展性很好，结点数增加时每个结点维护的信息不变， 而且路由长度只是以o ( n l d ) 的数量级增长。我们可以看到，在坐标空间中， 两点之间可以有许多条不同的路径。因此，单个结点的失效对c a n 基本上 没有太大的影响。遇到失效结点时，c a n 结点会自动沿着其他的路径进行 路由。 下面介绍c a n 节点加入和退出。c a n 是一种动态网络，当一个新的结 点加入网络时必须得到自己的块坐标空间。c a n 通过分裂现有的结点区 域实现这一过程。它把某个现有结点的区域分裂成同样大小的两块，把其中 一块分给新加入的结点。整个过程分为以下三步：( 1 ) 新结点必须首先找到 一个已经在c a n 中的结点。( 2 ) 新结点使用c a n 的路由机制找到一个区域 将要被分隔的结点。( 3 ) 执行分裂操作，然后原有区域的邻接区域必须被告 知发生了分裂，这样新结点才能被别的结点路由到。当结点离开c a n 时， 必须保证它的区域被c a n 系统收回，也就是分配给其他仍然在系统中的结 点。一般过程是由某个结点来接管这个区域和所有的( 关键字，值) 数据库 如果这个区域可以和相邻区域合并形成一个大的区域，那么c a n 将执行合 并操作。如果合并不能进行，那么该区域将交给其邻接结点中区域最小的结 点。也就是说，这个结点将临时负责两个区域。在正常情况下，c a n 的相 邻结点之间将交换周期性的更新消息。如果多次没有接收到某个结点的更新 8 西华大学硕士学位论文 消息，那么相邻结点就认为这个结点失效了。这时，相邻结点将启动取代操 作，并启动一个时钟。失效结点的每个相邻结点相互独立地执行该过程。如 果时钟超时，结点将向失效结点的所有相邻结点发送取代消息，该消息中包 括它自己的区域面积信息。当某个结点接收到取代消息后，如果它的区域面 积比发出消息的结点大，则它将取消取代操作。否则它将发出自己豹取代消 息。采用这种机制可以保证选择面积最小的结点取代失效结点。当然，在某 种特殊情况下，还有可能出现多个相邻的结点同时失效的情况，这时如果让 某个结点取代某个失效结点，就有可能导致c a n 出现不一致。在这种情况 下，c a n 将首先执行修复操作，通过查找更远的邻接区域以获得足够的邻 接状态来保证取代操作的一致性。 1 2 3 t a p e s t r y t a p s t r y 源于p l a x t o n 路由机制一种优化，它是用于覆盖网络的定位和路由 机制，它可以对消息进行位置无关的路由，把消息传递到最近的存放所要求 的对象拷贝的结点。t a p e s t r y 的路由机制完全是基于软状态的并且易于修复。 t a p e s t r y 具有自我管理、容错和灵活平衡负载等特点。t a p e s t r y 采用的基本定 位和路由机制和【捌很类似。t a p e s t r y q a 的每个结点都可以用中描述的算法转 发消息。每张邻居映射表都按照路由层次组织，每个层次都包括匹配该层 次对应的前缀并离该结点最近的一组结点。每个结点还维护一张后向指针 0 , a c k p o i n t = ) 列表指向把自己作为邻居的那些结点。在缩点加入算法中会用 到这些指针。 t a p e s t r y 的定位机制 g 和也和p l a x t o n 类似。在p l a x t o n 中，如果数据对象 存在多份拷贝，那么对象的根结点只保存离它最近的那份拷贝的位置。而 t a p e s t r y j j 保存了所有拷贝的位置信息以增加灵活性。t a p e s t r y 以允许应用 来决定如何在这多份数据拷贝中进行选择t a p e s t r y 结点的数据结构包括：邻 居映射表、热区( h o t s p o t ) 监视器、对象定位指针和对象存储。 在t a p e s t r y 厩j 络中，如果当节点检测正常操作过程中发现链路和服务器 失效，可以使用t c p 连接超时机制。除此之外，每个t a p e s t r y 结点都使用后 向指针周期性的发送“心跳 u d p 分组给把自己加入邻居映射表的结点。每个 9 西华大学硕士学位论文 结点都可以根据自己收到的心跳分组来决定自己的邻居映射表中是否有结 点失效。在邻居结点表中，除了主邻居结点( 最近的邻居) 之外，每个路由项 还保存了两个备份的邻居结点，当检测到主邻居结点失效后，邻居结点表将 顺序选择备份邻居结点。 在p l a x t o n 中，每个对象的根结点是一个单一故障点。在t a p e s t r y 中， 通过为每个对象分配多个根结点来修正这个问题。具体的做法是在每个对象 后面分别加一个小的后缀( 比如，1 ，2 ，3 ) ，然后对这些结果进行哈希得到 多个根结点。在定位对象时，执行同样的哈希操作以生成这组根结点。 t a p e s t r y 的结点加入算法和p a s t r y 很类似。结点n 在加入t a p e s t r y 网络 之前，也需要已知一个已经在网络中的结点g 。然后n 通过g 发出路由自 己的结点m 的请求，根据经过的结点的对应的邻居结点表构造自己的邻居 结点表。构造过程中还需要进行一些优化工作。构造完自己的数据结构后， 结点n 将通知网络中的其他结点自己已经加入网络。通知只针对在n 的邻 居映射表中的主邻居结点和二级邻居结点进行。 t a p e s t r y 采用两种机制处理结点的退出。一种情况是结点从网络中自行 消失( 主要原因是结点失效) ，在这种情况下。它的邻居可以检测到它已经退 出网络并可以相应的调整路由表。另一种机制是结点在退出系统之前通过后 向指针通知所有把它作为邻居的结点，这些结点会相应调整路由表并通知对 象服务器该结点已经退出网络。 1 2 4 路由机制的比较 以上介绍了四种用于对等网络的查找系统，从介绍中可以看出，它们具 有很多相似的特点，比如都采用了s h a - 1 哈希函数来获得标识符，都采用了 路由表机制进行路由转发，在处理结点的加入和退出时都采取了相似的步 骤，等等。表1 2 给出了上述几种路由查找系统的比较。从表中可以看出， 它们具有基本类似的性能； 表1 2 路由机制比较 t a b l e1 2c o m p a r e ro f t h er o u n d i n g 1 名称 i 加入复杂l 空同复杂度i 查找复杂度i 是否支持i 1 0 西华大学硕士学位论文 度 负载平衡 p a s t r y o ( n l o gn 、o ( n l o gn )o ( n l o gn 、 支持 c h o r d 同上 。 同上 0 0 0 9 n ) 支持 t a p e s t r y 同上同上同上支持 c a n o ( ) n r支持 1 2 5d i i t 算法存在的问题 d h t 算法虽然在很大程度上解决了系 统查找的可扩展性问题，同时带来了新的 问题，现有的d l 玎算法在路由时基本没有 考虑实际网络拓扑和节点资源( 带宽、存储 空间和处理器能力) 的不同，使用节点的逻 辑跳衡量路由性能，而真正有效的衡量时 端到端延迟。一个节点的单个逻辑跳可能 跨越多个自治域( a s ) ，导致了高延迟的路 由。p a s t r y , s 4 t a p s t r y 虽然在这方面做了一 些工作，但还远不能解决问题。 f i g l 6 t h ep r i n c i p l eo fu i a n g l e 图1 6 三角原理 其中c h o r d 和c a n 目前还完全没有考 虑网络物理拓扑信息，这样尽管c h o r d 只维护轻量级的“叠加”网络协议，但 每次逻辑路由转发可能造成在i u t e r n e t 路由较长的物理延迟，得到节点在 i n t e m e t 上的相对位置信息，从而构造“意识”到物理拓扑的“叠加”网络。 t a p e s t r y 和p a s t r y 通过测量节点之闻度量值大小得到租粒度物理拓扑信 息，并且在路由表中包括了物理邻居节点信息，仿真表明有效利用物理拓扑 信息对提高系统性能非常有用，如这两个系统中的平均信息移动距离时实际 底层物理网络距离的较小常数因子倍数；但是，与c h o r d 相比，需要较为昂 贵的“叠加”维护信息，此外，基于邻近信息的路由会降低系统的负载平衡能 力，而且由于位置属性的复杂性、动态性和非均匀拓扑原因，还不清楚位置 属性在实际i n t e m e t 中会产生什么成都的影响。以p a s t r y 为例，p a s t r y 是使 用三角原理定位节点在网络中的物理位置，如图1 6 节点a 初始化时只知道 1 l 西华大学硕士学位论文 节点b ，而当节点a 判断与节点c 的距离时，会得出a c a b + b c 。这样将 不法准确定位a c 的距离。因此，p 2 p 叠加网络中基于邻近信息的路由的效 率和开销代价还不是非常清楚，而目前还没有一个研究项目对此开展研究。 1 3本文主要工作 本文研究的内容主要包括： ( 1 ) 通过对国内外相关文献资料分析，以及对传统p a s t r y 路由算法进 行深入细致的研究，提出一种改进的p a s t r y 路由算法。 ( 2 ) 对改进算法的网络拓扑结构、节点的加入和失效处理方式、改进 p a s t r y 的路由和搜索机制以及s u p e r 节点的应用和备份方法都进行研究。 ( 3 ) 在j x t a 平台上实现本文的改进算法。同时对本文设计的算法进 行性能分析和实验。 西华大学硕士学位论文 2 p a s t r y 网络模型的路由机制 由于完全分布式系统中的随机搜索造成不可扩展性的缺陷，所以目前大 量的研究集中在如何构造一个高度结构化的系统。在这些结构化的系统中， “叠加”拓扑被严格控制，文件( 或者文件指针) 存放在确定的位置上。系统提 供从文件标志符到存放该文件的节点标志映射服务，然后查询请求路由到该 节点。通过以上方法系统提供了一个可扩展的方案实现了文件的“精确匹配” 查询。目前人们把研究的重点放在了如何有效地查找信息上，最具代表性的 都是基于d h t 地分布式查找和路由计算。 2 1 p a s t r y 网络模型 p a s t r y 是d h t 路由机制的一种，它是微软研究院提出的可扩展的分布式 对象定位和路由协议，它是由p a s t r y 节点组成的自组织的结构化覆盖网络 ( o v e r l a yn e t w o r k ) 。p a s t r y 路由算法能有效地检索到结果，同时保证搜索步 数在0 0 0 9 n _ ) 的范围内( n 为节点总数) ，实现了可扩展性搜索。由于它是架 设在严格结构化p 2 p 网络上，所以p a s t r y 搜索算法对节点的限制条件过多， 需要严格控制网络拓扑和文件存储位 置【1 4 】。 2 1 1p a s t r y 网络拓扑结构 p a s t r y 网络中每个节点既是客户端 又是服务器，节点在加入网络时被随机 分配一个1 2 8 位的节点号n o d e l d ，用 于在节点空间中标识节点的位置。节点 号可以通过计算节点公钥或者璎地址 的哈希函数值来获得。节点需要维护3 种数据结构，如图2 1 所示： ( 1 ) 路由表( r o u t i n gt a b l e ) 。假定网 络由n 个节点组成，它有l l o gn i 行， n o d e i d1 0 2 3 3 1 0 2 l e a f s d l 自“m “& g e rfi l l 1 0 2 3 3 0 3 3l | 0 2 3 3 0 2 1 1 0 2 3 3 1 2 0 1 0 2 3 3 1 2 2 i i 1 0 2 3 3 0 0 01 0 2 3 3 2 3 01 0 2 3 3 2 3 20 r o u t u 砬ta b l e 3 - 1 2 0 3 2 0 3 l 1 0 2 2 2 轴2 1 0 2 3 3 2 3 2 j0 2 3 3 i - 2 - 0 i n e t 霉1 1 ) o r h o o ds d f i g 2 1d a t ac o n f i g u r a t i o no fp a s 仃y 图2 1p a s t r y 节点数据结构 每行有2 6 1 ( b 是一个配置参数，典型取值是l ，2 ，3 ，4 ) 个入口的表项组成。行 西华大学硕士学位论文 n 的2 6 一1 个入口指向其n o d e i d 和当前节点的n o d e l d 共享前1 1 位但第n + 1 位不同的妒- - 1 个表项。值b 的选择考虑了路由表的长度和路由跳数的权 衡，b 越大则路由跳数越小，但需要维护的路由信息越多。路由表中每行的 阴影项表示当前节点号对应的位。 ( 2 ) 叶子集( l e a f s e t ) 。叶子节点集合中存放的是和当前节点的标识符从 数值上看最接近的节点，叶子节点集合在消息路由时需要用到。它是l i j 2 的下取整0 l i 是配置参数值为尹) 个其n o d e i d 最接近且大于本地节点 n o d e i d 的节点和i l i 2 的下取整个其n o d e i d 最接近且小于本地节点的 n o d e i d 的节点集合。 ( 3 ) 邻居集( n e i g h b o r h o o ds e t ) 。它包含同本地节点最接近的i m l ( 1 m 悖配 置参数，值为2 2 - 1 个节点，不用于路由转发而是用于保证路由的位置，即 保证路由表中每个表项指向的节点都是离当前节点最近的节点，保证的前提 是网络距离度量满足欧氏空间的三角不等式。当前节点周期性地和邻居节点 集合中的节点交换信息以验证这些节点是否仍在p a s t r y 系统中，如果某个节 点失效，那么当前节点将要求其他邻居节点把自己的邻居节点集合发送过来 并从中选择一个新的邻居节点来替换失效节点旧。 2 1 2p a s t r y 节点加入 当一个新节点加入时，它需要初始化它的状态表( 叶子表、路由表、邻 居表1 ，然后通知和它临近的节点。假设新节点知道一个和它临近的p a s t r y 节点a ，然后根据三角原理定位自己在p a s 仃y 网络中的位置。并将加入信息 发送给节点a ，节点a 以新节点的球和k e y 为参数通过s h a 方法计算出 新节点的n o d e i d ，a 将生成的n o d e l d 发送给新节点 假设新节点的n o d e l d 是x ，节点x 将一则w = x 的加入消息发送给 节点a ，节点a 通过p a s t r y 网络路由该则消息到最匹配的节点z 上，在路 由过程中得到该消息的节点会将自己的状态表发送给节点x ，节点x 根据 节点a 的邻居表初始化自己的邻居表，根据节点z 的叶子表初始化自己的 叶子表，假设此加入消息路经i 个节点