（计算机科学与技术专业论文）对等网络chord查找算法改进方案的研究与应用.pdf

l 一 一- 对等网络c h o r d 查找算法改进方案的研究与应用 摘要 随着计算机处理能力的不断增强和网络技术的迅速发展，越来 越多的计算机连接到了i n t e m e t 上，如何有效的利用这些计算资源成 为一个热点问题。在传统的i n t e m e t 中央服务器模式中，服务器端承 受着巨大的负载，而客户端却基本闲置，网络中大量的计算资源都没 有得到有效利用。对等网络( p 2 p ) 作为一种完全分布的计算模型，可 以脱离中央服务器实现对等节点间的直接通信，从而充分利用每个网 络节点自身的资源，实现整个网络计算资源的充分利用和信息资源的 高效共享。 在对等网络的众多研究领域中，关于查找算法的研究具有核心地 位。现有对等网络查找算法基本可归为四类，分别是以n 印s t e r 为代 表的集中式查找算法，以g n u t e l l a 为代表的非结构化分布式查找算 法，以c h o r d 为代表的结构化分布式查找算法和以k a z a a 为代表的 混合式查找算法。本文首先分析比较了这些算法的各自特点，然后在 建立c h o r d 数学模型的基础上，根据应用场景的不同，提出了c h o r d 查找算法的三种改进方案，并通过模拟实验验证了改进方案的合理 性。最后设计实现了基于c h o r d 查找算法第一种改进方案的对等网络 模块，并将其运用到c e p m s ( c o m m u n i c a t i o na n de x c h a n g ep 1 a t f o r n l b a s e do nm a ps e i c e ，基于地理信息服务的信息交流平台) 原型系统 中。 本文的主要贡献在于： 1 提出了三种适用于不同网络环境的c h o r d 查找算法改进方案，并 通过数学分析和实验验证论证了改进方案的合理性，在理论上对 现有结构化分布式查找算法进行了有益的补充。 2 通过设计实现基于c h o r d 查找算法第一种改进方案的对等网络模 块并应用到c e p m s 原型系统中，在应用上为对等网络软件的开 发提供了一种新的底层实现方案，有助于对等网络软件的发展和 进步。 关键词：对等网络，p 2 p ，查找算法，c h o r d ，- 1 叫 k 爹 r e s e a r c han da p p l i c a t i o no f t h ei 阳r o v e m e n t0 fc h o r d a bs t r a c t w i t ht h ed e v e l o p m e n to ft h ep r o c e s s o rs p e e do fc o m p u t e ra n d n e t w o r kt e c n o l o g y ，m o r ea n dm o r ec o m p u t e r sh a v eb e e nc o n n e c t e d t ot h en e 饥o r k h o wt om a k eg o o du s eo ft h e s ec o m l ) u t i n gr e s o u r c e s h a sb e c o m eap o p u l a rt o p i c i nt h et r a d i o n a lc l i e n t s e e rn e t w o r k a r c h t e c t u r e ，t h em a io r i t yo fc o n t e n ti ss t o r e do nt h ec e n t r a ls e r v e ra n d t h ec l i e n to n l ya c c e s si t ，al a r g en u m b e ro f c o m p u t i n g r e s o u r c e si nt h e n e t w o r ka r en o tu s e de 珩c i e n t l v p e e 卜t o p e e r 伊2 p ) n e t w o r kc o m e s i n t ob e i n ga sa 如1 ld i s t r i b u t e dc o m p u t i n gm o d e l t h e r ei sn os p e c i a l s e r v e ri np 2 pn e t w o r ka n dn o d e sa r ea b l et oc o m u n i c a t ed i r e c t l vw i t h e a c ho t h e r p 2 pm a k eg o o du s eo fc o m p u t i n gr e s o u r c ei nn e 饥o r ka n d i sp r o m i s e dt ob eu s e df o rs h a r i n gr e s o u r c ee m c i e n t l v r e s e a r c ho n1 0 c a t i o na l g o r i t h mi st h ec o r ee l e m e n ta m o n gm a r l v p 2 pr e s e a r c hf i e l d s e x i s t i n gl o c a t i o na l g o r i t h mc a nb ed i v i d e di n t o f o u rk i n d s ：c e n t r a l i z e d1 0 c a t i o na l g o r i t h m ，s u c ha sn a p s t e r ；u n s t r u c t e d d i s t r i b u t e d1 0 c a t i o na l g o r i t h m ，s u c ha sg n u t e l l a ：s t r u c t e dd i s t r i b u t e d 1 0 c a t i o na l g o r i t h m ，s u c ha sc h o r d ；m i x e d1 0 c a t i o na l g o r i t h m ，s u c ha s k a z a a t h em a t h e m a t i c a lm o d e lo fc h o r di se s t a b l i s h e di nt h i s p 印e ra r e rt h e s ea l g o r i t h m sw e r ea n a l y z e d t h e nt h r e ei m p r o v e m e n t s o fc h o r dt h a ta r es u i t a b l ef o rd i 船r e n ta p p l i c a t i o nb a c k g r o u n da r e p r o p o s e db a s e do nt h em a t h e m a t i c a lm o d e lo fc h o r d w h a t sm o r e ， w ep e r f o me x p e r i m e n t so nt h ep e r f o 衄a n c eo ft h e s ei m p r o v e m e n t s o fc h o r d ，a n da n a l y z et h ee x p e r i m e n t r e s u l t s f i n a u y ，t h ep r o g r a mo f t h ef l r s ti m p r o v e m e n to fc h o r di sd e s i g n e da n di m p l e m e n t e d ，i ti s u s e di nc e p m s ( c o m m u n i c a t i o na n de x c h a n g ep 1 a t f o r mb a s e do n m a ps e r v i c e ) p r o t y p es y s t e m i naw o r d ，t h em a i nc o n t r i b u t i o no ft h i sp a p e rc a nb es u m m a r i z e d a s 士o 儿o w s ： 1 b a s e do nt h em a t h e m a t i c a lm o d e lo fc h o r d ，t h r e ei m p r o v e m e n t so f c h o r dt h a ta r es u i t a b l ef o rd i f - f e r e n ta p p l i c a t i o nb a c k g r o u n da r e p r o p o s e di nt h i sp a p e r i tc a r r y so nt h eb e n e f l c i a ls u p p l e m e n t t om e e x i s t i n gs t r u c t e dd i s t r i b u t e dl o c a t i o na l g o r i t h m 2 t h ep r o g r a mo ft h e6 r s ti m p r o v e m e n to fc h o r di sd e s i g n e d 。赫d i m p l e m e n t e d i nc e p m sp r o t y p es y s t e m i ti sh e l p 如l i nt h e d e v e l o p m e n to fp e e r - t o p e e rs o r w a r e k e yw o r ds ：p 2 p l o c a t i o na l g o r i t h m ，c h o r d o h k i 一 篡 ， ， h 眨、 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：塑型鱼 日期：丝51 ；：堑 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位论文不属于保密范围，适用本授权书。 本人虢鲻一一 导师签名：垒4 及 导师签名： 丝l 纽 日期：坦签：呈：塑 日期：2 竺! ! ! 皇! 兰里 北京邮电大学硕士学位论文对等网络c h o r d 查找算法改进方案的研究与应用 1 1 论文背景 第一章绪论 对等网络( p e e r t o - p e e rn e t w o r k ，简称p 2 p ) 是一种用于不同计算机之间，不经 过中继设备直接交换数据或服务的技术。在对等网络中，每个节点的地位都是相 同的，具备客户机和服务器双重特性，可以同时作为服务使用者和服务提供者。 对等网络并不是一个全新的概念，早在2 0 世纪7 0 年代，源于局域网中文件 共享的对等网络技术就开始出现，其典型代表是u s e n e t 和f i d o n e t 两个分散、 分布的信息交换系统。实际上，互联网存在的基石t c p i p 协议本身并没有 客户机和服务器的概念，参与通信的设备处于平等地位。只是由于互联网发展初 期，p c 设备性能有限，并出于对网络的易管理性和安全性的考虑，c s 模式才 得到了广泛应用并逐渐发展成了互联网中最流行的计算模式。但到了2 0 世纪9 0 年代末期，随着互连网技术的飞速发展和网络用户的急剧增加，c s 模式的弊端 越来越明显的显现出来：服务器要同时为网络中的众多客户机提供服务，极易成 为性能瓶颈；服务器的处理能力决定了系统的最大负载，可扩展性差；服务器的 单点故障会导致系统瘫痪，容错性差。与此同时，p c 机的性能按照摩尔定律飞 速发展，现在充当客户机的p c 性能已经达到甚至超过了早期的大型主机，客户 机在请求其它机器服务的同时也具备了向其它机器提供服务的能力。于是人们意 识到是否可以通过发掘客户机的计算能力，充分利用整个网络的计算资源；通过 弱化甚至取消服务器，消除系统瓶颈，改善系统性能。这就导致了对等网络技术 的复兴。 近年来，随着对等网络技术被越来越广泛的运用到包括文件交换，对等计算， 协同工作，实时通信，信息检索，广域网络存储等多个领域，关于对等网络的理 论研究也成为了国内外计算机学术界关注的一个热点问题。在众多研究领域中， 针对查找算法的研究具有非常重要的意义。因为在对等网络环境中，所有的节点 都是平等的，不存在像c s 模式中的服务器这样专门提供发现服务的角色，所以 如何高效准确的实现网络资源的查找无疑是对等网络理论研究必须解决的核心 问题。针对查找算法的现有研究成果基本可归为四类，分别是以n a p s t e r 【lj 为代 表的集中式查找算法，以g n u t e l l a 【2 j 为代表的非结构化分布式查找算法，以c h o r d 【3 】 为代表的结构化分布式查找算法和以k a z 啦【4 1 为代表的混合式查找算法。其中， 与集中式查找算法相比，分布式查找算法彻底消除了服务器的存在，更符合对等 网络的需求。而结构化分布式查找算法克服了非结构化分布式查找算法使用泛洪 北京邮电大学硕士学位论文对等网络c h o r d 查找算法改进方案的研究与应用 机制查找导致网络可扩展性差的弊端，具有更好的发展潜力和研究价值。 c h o r d 是m i t 提出的一种基于d h t 的结构化分布式查找算法，它具有简单 性，可验证性，可扩展性等优点，是一种较为成功的对等网络查找算法。但这并 不意味着该算法已完美无暇。实际上，c h o r d 查找算法依然存在不足之处，主要 表现在以下方面： 1 ) c h o r d 算法的查找效率依然不够高。现有c h o r d 在n 个节点的网络中完成查 找操作平均需要去l o g ，n 跳，最多需要l o g ：n 跳a 例如，当网络中存在1 0 2 4 z 一 个节点时，c h o r d 平均需要5 个路由跳，最多需要1 0 个路由跳才能完成查找。 这种查找效率在实时性要求较高的场合是无法满足需求的。 2 ) 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 查找算法改进方案的探讨展开。 1 2 论文目的和意义 本文的研究目的是在建立并分析c h o r d 数学模型的基础上，提出c h o r d 查找 算法的改进方案，并通过模拟实验验证改进方案的合理性；实现根据c h o r d 改进 方案设计的对等网络模块并应用到c e p m s 原型系统中。 本文的理论意义在于提出了三种适用于不同网络环境的c h o r d 查找算法改 进方案并验证了方案的合理性，对现有结构化分布式对等网络查找算法进行了有 益的补充：现实意义在于通过设计实现基于c h o r d 查找算法第一种改进方案的对 等网络模块并应用到c e p m s 原型系统中，为对等网络软件的开发提供了一种新 的底层实现方案，有助于对等网络软件的发展和进步。 1 3 论文内容 本文主要包括以下内容： 1 介绍了对等网络的基本知识，包括对等网络的概念和特点。 2 介绍了对等网络查找算法的研究现状，重点阐述了结构化分布式查找算 法中的c h o r d 算法，并对现有查找算法进行了分析和比较。 3 为c h o r d 建立数学模型，为论文研究c h o r d 算法改进方案提供理论分析 的平台。 4 在分析c h o r d 数学模型的基础上，根据应用场景的不同，提出了c h o r d 北京邮电大学硕士学位论文对等网络c h o r d 查找算法改进方案的研究与应用 查找算法的三种改进方案。 5 通过模拟实验，验证了改进方案比c h o r d 具有更好查找效率的结论，并 初步探讨了各种改进方案的效果。 6 实现根据c h o r d 查找算法第一种改进方案设计的对等网络模块并应用到 c e p m s 原型系统中。 北京邮电火学硕+ 学位论文对等网络c h o r d 商找算法改进方案的研究与应用 第二章对等网络查找算法研究现状 正如上一章1 1 节所述，查找算法是对等网络的核心基础问题。鉴于查找算 法在对等网络中的重要地位，国内外相关研究机构对其进行了大量的研究工作， 并取得了丰硕的成果。现有研究成果基本可归为集中式，分布式和混合式三类， 下文将分别予以介绍，重点介绍结构化分布式查找算法以及本文将要改进的 c h o r d 查找算法。 2 1 集中式查找算法 集中式查找算法运用一个或多个目录服务器存放网络中各节点共享资源信 息的索引。节点加入对等网络后，需要登录到目录服务器发布自己想要在网络中 共享的资源描述信息( 例如文件名等) 。传输资源时，节点首先要向服务器查询 自己所需资源在网络中的位置，然后爿+ 能绕开服务器与存放资源的节点直接通 信。运用这种查找算法构建的对等网络中存在目录服务器这样的中心节点，网络 中节点的作用和地位不完全对等，只有节点间端到端的连接是对等网络方式，而 节点与目录服务器间仍然是传统的c s 模式。这种算法的优点是查找效率高且易 于管理，但目录服务器容易成为网络中的单一失效点和性能瓶颈，系统的可跨展 性也受到了限制。此类查找算法最有代表性的应用是n a p s t c r 。 n a p s t e r 是一种用于音乐文件交换的对等网络应用软件，它采用集中式查找 算法，具有一个中央服务器保存所有注册过的音乐文件。用户需要下载音乐文件 时，首先连接到中央服务器，在服务器进行检索，并由服务器返回存有该音乐文 件的用户位置信息，然后，请求者使用点对点的方式直接从该文件所有者处下载 文件。n a p s t e r 所有查找工作都由中央服务器完成，因此中央服务器很有可能成 为单点失效点，系统的可扩展性也受到了严重的制约。同时，n a p s t e r 引起的版 权诉讼表明集中式查找算法还存在版权管理问题这一致命弱点。 2 2 分布式查找算法 与集中式查找算法不同，分布式查找算法是一种纯粹的对等网络查找算法， 系统中没有任何中央服务器的存在，查找工作完全依靠各个对等节点的协作完 成。现有的分布式查找算法基本可归为结构化分布式查找算法和非结构化分布式 查找算法两类。 北京邮电大学硕士学位论文对等网络c h o r d 查找算法改进方案的研究与应用 2 2 1 非结构化分布式查找算法 非结构化分布式查找算法中对等节点连接任意其它节点构成对等网络，数据 放置与对等网络拓扑无关。此类算法的优点是由于逻辑网络拓扑采用随机图的组 织方式，结点度数服从”p o w e r 1 a w ”规律，因而能够较快发现目的结点，并具有较 好的容错性。同时可以支持复杂查询，如带有规则表达式的多关键词查询，模糊 查询等。缺点是由于没有确定拓扑结构的支持，非结构化网络无法保证资源发现 的效率和准确性。同时，随着网络规模不断增大，此类算法采用的洪泛发现机制 将造成网络流量急剧增加，从而导致网络中部分低带宽节点因网络资源过载而失 效。因此，可扩展性差同样是此类算法的重大缺陷。此类查找算法最有代表性的 应用是g n u t e l l a 。 g n u t e l l a 【2 】是一种对等网络文件共享系统，它采用非结构化分布式查找算法。 g n u t e l l a 中不存在中央服务器，它采用基于完全随机图的洪泛( f 1 0 0 d i n g ) 发现 和随机转发( r a j l d o mw a l k e r ) 机制，并通过t t l ( t i m et 0l i v e ) 的减值来控制 查找消息的传输。g n u t e l l a 中每个节点维护一些随机邻居节点的位置信息，用户 需要查找某个文件时，首先向邻居节点广播查找消息，邻居节点收到查找消息后， 再中转给自己的邻居节点，直到找到目标文件或超过t t l 的限制。观察g n l i t e l l a 的查找过程，我们可以发现，虽然g n u t e l l a 通过完全分布式的查找方法有效避免 了单点失效问题，但它的查找范围被局限在了以查找起点为半径的特定范围内， 无法保证查找的有效性，同时，它采用的广播查找机制导致了系统可扩展性不佳。 2 2 2 结构化分布式查找算法 由于非结构化分布式查找算法使用的随机搜索机制造成查找效率和准确性 的不可控制以及系统可扩展性差的重大缺陷，如何构建高度结构化的分布式查找 算法成为了学术界的研究热点。目前最新的研究成果体现在基于d h t ( d i s t r i b u t e dh a s ht a b l e ，分布式哈希表) 构建的结构化分布式查找算法。 分布式哈希表( d h t ) 实际上是一个由广域范围大量结点共同维护的巨大哈 希表。哈希表被分割成不连续的块，每个节点被分配给一个属于自己的哈希块， 并成为这个哈希块的管理者。 基于d h t 的结构化分布式查找算法能够自适应节点的动态加入和退出，有 着良好的可扩展性、容错性、负载平衡性和自组织能力。由于采用了确定性逻辑 拓扑结构，查找的准确性和查找效率得到了保证。此类查找算法较有代表性的应 用有c h o r d ，c a n ，p a s t r y 和1 a p e s t r y 。 北京邮电人学硕士! 学位论文对等网络c h o r d 奇找算法改进方案的研究与应用 2 2 2 1c h o r d c h o r d 口1 是m i t 提出的一种结构化分布式查找算法。该算法的核心在于提供 查找资源在对等网络中存储位置的服务。算法阐述了怎样找到给定资源的存储位 置，新结点怎样加入系统，现有节点怎样退出系统以及系统怎样从现有结点的失j 效中恢复。i 1 逻辑拓扑结构 c h o r d 通过一致性哈希函数为网络中的所有节点和资源赋予d 位的标识号。 其中，节点的标识号一般是通过对节点i p 地址的哈希运算得出，资源的标识号 一般是通过对资源名称( 网络中资源名称应唯一) 的哈希运算得出。所有可能的 n = 2 6 个节点标识根据其数值由小到大按顺时针方向相连，并且最大值和最小值 相连，最终构成一个标识环。对于一个标识号k ，标识环中顺时针方向第一个物 理节点称作k 的后继节点，记做s u c c e s s o r ( k ) ；逆时针方向第一个物理节点称作k 的前驱节点，记做p r e d e c e s s o r ( k ) 。c h o r d 规定标识号为k 的资源存储在k 的后继， 即s u c c e s s o “k ) 上。如图2 1 所示是一个d = 6 的c h o r d 环，环中最大可能拥有 n - 2 6 = 6 4 个节点，现有1 0 个节点。s u c c e s s o r ( 1 0 ) = 1 4 ，s u c c e s s o r ( 2 4 ) = 3 2 ， s u c c e s s o r ( 3 0 ) = 3 2 ，s u c c e s s o 3 8 ) = 3 8 ，s u c c e s s o r ( 5 2 ) = 5 6 ，因此，k l o 存储在n 1 4 上， k 2 4 存储在n 3 2 上，k 3 0 存储在n 3 2 上，k 3 8 存储在n 3 8 上，k 5 2 存储在n 5 6 e 。 图2 一lc h o r d 逻辑拓扑图 北京邮电大学硕士学位论文对等网络c h o r d 查找算法改进方案的研究与应用 2 数据结构 在标识空间的大小为n ( d = l 0 9 2 n ) 的c h o r d 环中，每个节点维护的内部数 据结构包括：前驱节点，后继节点，拥有d 个表项的路由表( 称为f i n g e r 表) ，连 续d 个后继节点的列表，前d 个节点存储资源备份列表。其中前三项是基本c h o r d 算法所规定的必备数据结构，后两项是c h o r d 算法考虑系统容错性和数据可靠性 而提出的附加数据结构。c h o r d 路由表每一项的结构如下所示： 表2 一lc h o r d 路由表( f i n g e r 表) 标记含义 f i n g e r k s t a r t( n + 2 一1 ) m o d 2 “，1 = k k n o w n n o d e i d s e a r c h n o d e i d o ：i 一一) ( i f ( k n o w n n o d e f i n g e r i s u c c e s s o r i d s e a r c h n o d e i d ) r e t u r nk n o w n n o d e f i n g e r i s u c c e s s o r ： ) r e tu r nk n o w n n o d e ： 4 节点加入算法 节点加入c h o r d 网络的过程分为三个步骤完成： 首先，新节点n 必须找到c h o r d 网络中的一个现有节点n ，并利用该节点使 用查找算法，得到n 的后继s 。 然后，n 构造自己的数据结构，包括构造前驱，后继，后继节点列表，路由表。 构造过程如下：填写后继为s ：获取后继s 的前驱作为自己的前驱；向s 请求它 的后继列表，以s 后继列表的前d 1 项和s 构成本节点的后继列表；利用n 分别 查找n + 2 m ( m = 0 ，l ，d 。1 ) 的后继，填写路由表。 最后，n 通知所有相关的节点更新其数据结构以便反应n 的加入。相关节点 包括n 的前驱，后继，前d 个前驱和那些当n 加入时必须改变其路由表的节点。 更新n 的前驱，后继的过程如下：修改n 的后继的前驱为n ；修改n 的前驱的后继 为n 。更新n 的前d 个前驱的过程如下：将n 作为后继列表中的一项，将原后继列 表中的最后一项从后继列表中删除；更新当n 加入时必须改变其路由表的节点的 过程比较复杂，伪码如下： v o i du p d a t e o t h e r s r o u ti n g t a b l e ( n b d ek n o w n n o d e ，n o d ej o i n n o d e ) n o d ep ： f o r ( i n ti = 0 ：i = p i d & j o i n n o d e i d c z ，并通过目 的节点z 返回给a ，则z 变为a 的根节点，a 从访问过程中的第f 个节点可构 造其路由表的第f 列条目；然后发送“h e l l o ”报文给其新的邻居，其它节点根 据a 的标识号和邻近性调整它们的节点状态。节点定期地测试邻居的连接性， 失效的邻居得到第二次更新机会，如果在第二机会期间内，它们正常反应，将被 标注为有效，一个节点在邻居失效后使用后备邻居。 系统使用回溯优化法来调整网络性能，它努力尝试使用统计数据适应变化的 网络环境。例如节点使用p i n g 来更新到邻居的延迟，如果延迟变化超过一个阈 值( 比如4 0 ) ，它们就优化路由表。节点也监视请求对象的频率和建议缓冲决 策( 称作热点缓冲) 。 2 2 2 4c a n c a n 【8 1 是b e r k e l e y 提出的一种结构化分布式查找算法。该算法构造一个虚拟 的d 维笛卡儿坐标空间，每个机器或数据根据其i p 地址或关键字k ，由哈希函 数映射到该d 维空间中的一点。参与网络的物理节点动态划分该d 维空间，拥有 某块虚拟坐标区域的物理节点对由哈希函数映射到该区域中的数据负责。 1 逻辑拓扑结构 图2 3 显示了一个2 维的c a n 网络的拓扑结构。这是一个2 维的笛卡儿坐 标空间，整个虚拟坐标空间被划分为许多小的2 维区域，每个物理节点对应一个 区域，维护由哈希函数映射到该区域的数据。比如节点a 对应( 0 一o 5 ，0 - o 5 ) 区 域，b 对应( 0 5 1 0 ，0 一o 5 ) 区域。在d 维空间中，如果两点有d 1 维坐标相同，并 且剩下的维坐标相邻( 如在图x 中，e 和b ，d 都相邻，e 和a ，c 不相邻) ， 则它们互为邻居。 北京邮电大学硕士学位论文对等网络c h o r d 查找算法改进方案的研究与应用 2 数据结构 1 0 ：、 ， ，i o 如8 _ y f r “j a j o l _ c ，f ，l a f pz o ”o 图2 3c a n 逻辑拓辛p 图 8 l c a n 中每个节点需要维护一个协作式的路由表，路由表中包含邻居节点( 每 维有2 个，共2 d 个) 以及相应的拥有空间。 3 查找算法 c a n 进行查找操作时，首先将要查询的目标的关键字由哈希函数映射到d 维空间中的一点( x ，y ) ，每一步从路由表中选取与( x ，y ) 笛卡儿距离最近的邻居节点 转发查找消息，这样一步步的将查找消息路由到目的节点。例如，在图2 5 中， 如果从e 节点开始查找某数据k ，假定数据k 属于c 管辖范围内，则可能的查 找路由过程为：e 一 d 一 c 或e 一 b 一 a 一 c 等。 4 节点加入和退出算法 节点a 加入c a n 时首先需要知道一个已知节点b ，然后节点a 随机选取一 个空间坐标点( x ，y ) ，通过b 在c a n 中路由到负责( x ，y ) 的节点c ，然后将c 负责 的区域均分，其中的一半给节点a ：与此同时，节点a 加入将导致节点c 及其邻 居节点的路由表发生变化，节点a 通知节点c 并由节点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 3 混合式查找算法 混合式查找算法可以看作集中式查找算法和分布式查找算法之间的一种折 北京邮电火! 学硕士：学位论文 对等网络c 1 1 0 r d 查找算法改进方案的研究与应用 衷。 如上文所述，集中式查找算法的查找效率通常很好，但是往往有单点失效问 题，而且可扩展性不好；而分布式查找算法能够很好地避免单点失效问题，可扩 展性好，容错性强，但是查找效率难以跟集中式查找算法相媲美。混合式查找算 法就是研究人员试图将这两种查找方式结合起来，取长补短而产生的。 i 在混合式查找算法中，节点按地理邻近性划分为聚类，每一聚类内选择性能 较高( 处理能力、存储能力、带宽等方面性能) 的一个或多个节点作为超级节点。 超级节点作为聚类内其他节点的目录服务器，聚类内的其他节点称为客户节点。 同一聚类中的客户节点和超级节点之间采用集中式查找算法，不同聚类中的超级 节点之间采用分布式查找算法。查找资源时，客户节点将查找请求提交给超级节 点并从超级节点接收查找结果，超级节点接收客户节点提交的查找请求并代表客 户节点在不同聚类问路由该查找请求。 此类查找算法最有代表性的应用是k a z a a 。 k a z a a 4 l 是现在全世界最流行的几款对等网络软件之一。根据c a 公司统计， 全球k a z a a 的下载量超过2 5 亿次，使用k a z 啦软件进行文件传输消耗了互联 网4 0 的带宽。k a z a a 之所以取得如此的成功，很重要的一个原因是它使用的 混合式查找算法结合了集中式查找算法和分布式查找算法的优点。总体上看；它 无需中央服务器存储文件索引，具有分布式查找算法的可扩展性和容错性。同时， 它自动的把性能好的机器推选为超级节点，通过使用超级节点的索引功能，使查 找效率大大提高，接近集中式查找算法的查找速度。 2 4 现有查找算法的分析比较 通过上文对现有的集中式，分布式和混合式三类查找算法的介绍，我们不难 发现，现有的三类查找算法各有利弊。 以n a p s t e r 为代表的集中式查找算法具有查找效率高且易于管理的优点，但 目录服务器可能会成为网络中的单一失效点和性能瓶颈，系统的容错性和可跨展 性也随之受到了影响。 以g n u t e l l a 为代表的非结构化分布式查找算法通过取消目录服务器有效避 免了单点失效问题，具有较好的容错性，但它无法保证查找效率和查找有效性， 并且由于查找消息使用广播机制导致系统可扩展性同样很差。 以c h o r d 为代表的结构化分布式查找算法在继承非结构化分布式查找算法 优点的同时，通过确定的逻辑拓扑结构保证了查找的准确性和查找效率，通过确 定的查找消息路由路径保证了系统的可扩展性，从而较好的解决了后者存在的缺 陷。但同时，现有的几种结构化分布式查找算法( c h o r d ，c a n ，p a s 乜y ，t a p e s t 巧) 也都在不同程度上存在着缺点。 北京邮电大学硕士学位论文 对等网络c h o r d 查找算法改进方案的研究与应用 c h o r d 的缺点是： 1 ) c h o r d 算法的查找效率依然不够高。现有c h o r d 在n 个节点的网络中完成查 1 找操作平均需要去l o g ，n 跳，最多需要l o g ，n 跳。例如，当网络中存在1 0 2 4 z 一 。 个节点时，c h o r d 平均需要5 个路由跳，最多需要1 0 个路由跳才能完成查找。 这种查找效率在实时性要求较高的场合是无法满足需求的。 2 ) c h o r d 算法构造的逻辑覆盖网与底层实际的物理网络拓扑完全脱离，地理位 置上相近的两个节点在c h o r d 生成的逻辑环上的对应节点标识号可能会相差 很远，这就导致了c h o r d 算法扩展到存在地理异构性的大规模广域网环境时 查找效率低下。 c a n 的缺点与c h o r d 类似： 1 ) c a n 算法的查找效率依然不够高。c a n 算法的时间复杂度为o ( n l ，d ) ，低于 同类算法0 ( 1 0 9n ) 的时间复杂度。虽然理论上讲当d = ( 1 0 9 2 n ) 2 时，算法可以 达到o ( 1 0 9n ) 的标准，但是实际应用中