（计算机应用技术专业论文）结构化p2p网络路由机制的研究.pdf

哈尔滨_ 程大学硕士学位论文 摘要 随着i n t e m e t 的飞速发展，网络带宽的成倍增加以及计算机计算能力的 大大提高，对等网络技术( p 2 p ) 迅速成为计算机领域内的热门课题。基于 分布式哈希表( d h t ) 的结构化p 2 p 网络为非中心化存储和内容发布等大规 模分布式应用提供了可扩展的、健壮的资源定位和路由服务。结构化p 2 p 网 络的路由机制决定了它的查询效率和网络应用。 本文首先介绍p 2 p 网络技术的现状和研究热点。在介绍了d h t 技术后， 对几种典型的结构化p 2 p 网络进行了分析比较。在给出了节点能力计算公式 后，按照所提出的超级节点选择机制对结构化p 2 p 网络进行层次化。通过对 小世界理论的分析，提出了双向路由的路由算法。 通过对c h o r d 协议进行改进，设计实现了层次化双向路由的路由算法的 h c h o r d 网络模型。详细阐述h c h o r d 网络的生成过程、节点路由表结构、查 询机制。并给出了h c h o r d 网络模型中的簇的维护管理方法，讨论了簇分裂 和簇合并过程中网络的维护。 最后用c 牟语言实现了h c h o r d 网络模型的模拟仿真，并详细给出了模型 实现过程中各个实体的设计和代码实现。对层次化双向路由的路由算法进行 模拟，通过与c h o r d 协议试验数据的比较分析，表明采用双向路由的层次化 的h c h o r d 协议，具有更高的路由和查询效率，同时减少了维护路由表所需的 系统开销。 关键词：覆盖网络；结构化p 2 p 网络；分布式哈希表；c h o r d 协议 哈尔滨工程大学硕士学位论文 a b s t r a c t w i t ht h er a p i dg r o w t ho fi n t e m e ta n dc o m p u t i n gp o w e r , p e e r - t o - p e e r ( p 2 p ) n e t w o r k sh a v eg a i n e dm u c ha t t e n t i o nf r o mb o t hi n d u s t r i a la n da c a d e m i cf i e l d s t h es 觚c t u r e dp 2 pn e t w o r k sw h i c hb a s eo nd i s t r i b u t eh a s ht a b l e ( d h t ) p r o v e t h es c a l a b i l i t yf l e x i b i l i t yr e s o u r c e sd i r e c t i n ga n dr o u t i n gs e r v e r sf o rt h ed i s t r i b u t e d a p p l i c a t i o nt h a ti n c l u d e sc e n t r es t o r ea n dc o n t e n tp u b l i cs y s t e m t h em u t i n g m e c h a n i s mo fp 2 pn e t w o r kh a sd e c i d e di t s i n q u i r ye f f i c i e n c ya n dn e t w o r k a p p l i c a t i o n s p 2 pn e t w o r kt e c h n o l o g yc u r r e n ts i t u a t i o na n dh o ts p o ts t u d y i n gi si n t r o d u c e d f i r s t l y a f t e ri n t r o d u c i n gt h ed h tt e c h n o l o g y , s e v e r a lc l a s s i cs t r u c t u r e dp 2 p n e t w o r ki si n t r o d u c e da n dc a r r i e do u ta n a l y t i c a lc o m p a r i s o n a f t e rh a v i n gg i v e n t h ef o r m u l at oc o m p u t et h ea b i l i t yo fan o d e ，c a r r i e so u tt h el a y e r i n go ft h e s t r u c t u r e dp 2 pn e t w o r kb yt h ec h o s em e c h a n i s mo fs u p e rn o d e s b yt h ea n a l y s i s t os m a l lw o r l dt h e o r y , h a v eb r o u g h tf o r w a r dt w o w a yr o u t em u t i n ga l g o r i t h m h a v ei m p r o v i n gt h ec h o r dp r o t o c o l ；t h eh c h o r dn e t w o r km o d e lw h i c h r e a l i z e st h el a y e r i n gt w o w a yr o u t ea l g o r i t h mi sd e s i g n e d t h e nt h eg e n e r a t e p r o c e s so ft h eh c h o r dn e t w o r km o d el ，t h en o d e s s t r u c t u r eo fr o u t i n gt a b l ea n d t h ei n q u i r em e c h a n i s ma r ei n t r o d u c e d a f t e rg i v i n go u tt h em a i n t a i n e dm e t h o d o fc l u s t e r si nt h eh c h o r d ，t h ep r o c e s so fc l u s t e rs p l i tu pa n dt h a to fc l u s t e r c o m b i n ei sd i s c u s s e d f i n a l l yh c h o r dn e t w o r km o d e ls i m u l a t i o nh a sb e e nr e a l i z e di nu s i n gc 样 l a n g u a g ea n dt h ee n t i t yd e s i g na n dc o d ei nt h em o d e lp r o c e s sh a sb e e nd e t a il e d g i v e no u t c a r r yo u ta na n a l o g u et e s to nl a y e r i n gt w o - w a yr o u t er o u t i n ga l g o r i t h m ， a f t e rt h ec o m p a r i s o n 埘t hc h o r d ，h a v ei n d i c a t e dt h a tt h el a y e r i n gh c h o r da d o p t t h et w o - w a yr o u t eh a sh i g h e rr o u t i n ga n dq u e r y i n ge f f i c i e n c yt h a nc h o r d ，a n d d e c r e a s e st h es y s t e mc o s to fm a i n t e n a n c eo ft h er o u t i n gt a b l e k e y w o r d s ：o v e r l a y ；g t n l c n 鹏dp e e r - t o p e e r ；d i s t r i b u t e dh a s ht a b l e ；c h o r d 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下， 由作者本人独立完成的。有关观点、方法、数据和文献的引用 已在文中指出，并与参考文献相对应。除了文中已注明引用的 内容外，本论文不包换任何其它个人或者集体已经公开发表的 作品成果。对本文的研究做出重要贡献的个人和集体，均已在 文中以明确的方式注明。本人完全意识到本声明的法律结果由 本人承担。 作者( 签字) ：丛! 垒】 日期：2 9 年月io 日 哈尔滨 二程大学硕士学位论文 第1 章绪论 1 1 课题的研究背景 p 2 p 网络技术自出现以来就一直受到广泛的关注。特别是最近几年，p 2 p 技术更是发展迅速，成为计算机领域的一个热门课题，有许多大学、研究机 构和公司如：m i t 、u cb e r k e l e y 、i n t e l 和m i c r o s o f t 等都投入到p 2 p 技术 的研究中来，因此不断有新的路由协议和网络模型出现。 结构化p 2 p 网络，如c h o r d t , l 、c a n t 2 1 、p a s t r y l 3 1 、t a p e s t r y t 4 l 和v i c e r o y t 5 j 等，为非中心化存储和内容发布等大规模分布式应用提供了可扩展的、健壮 的资源定位和路由服务。这些覆盖网络利用分布式哈希表把关键字映射到覆 盖网络的节点中。 尽管基于d h t f 6 1 的结构化p 2 p 网络的路由和查询效率较高，但是其本身 也存在一定的缺点。首先，结构化p 2 p 网络路由和查询的高效性及准确性都 依赖于网络中每个节点所维护的路由表的正确性和一致性，而大多数的结构 化p 2 p 网络都没有高效的路由表维护算法，例如c h o r d 为了维护路由表的正 确性，每个节点每个周期需要发送o ( 1 0 9 2n ) 个消息。网络的波动越大，刷新 路由表的周期越短，网络的维护开销越大。其次，大多数的结构化p 2 p 网络 将加入到网络中的节点都看作是性能相等的，而实际上这些节点的性能是不 同的。这就造成了表面上看结构化p 2 p 网络是负载均衡的，但在某些性能较 差的节点上造成系统瓶颈。通过超级节点可以避免系统瓶颈的产生，但是路 由协议需要极其复杂的算法来实现对超级节点的选取和维护，并且当超级节 点失效时，它的孩子节点将不能进行有效的工作，而必须等到新的超级节点 的形成。由于节点的加入和退出极其频繁，动态性是p 2 p 网络的一大特点。 如何在结构化p 2 p 网络中实现对超级节点的快速选取和维护成为p 2 p 网络路 由协议的关键【7 s l 。 同时结构化p 2 p 网络路由算法作为一种资源组织与发现技术必然要支持 复杂的查询，如关键词查询、内容查询、范围查询等。尽管信息检索和数据 挖掘领域提供了大量成熟的语义查询技术，由于d h t 精确关键词映射的特性 阻碍了d h t 在复杂查询里面的应用1 9 1 。此外p 2 p 共享软件产品普遍存在知识 哈尔滨下程大学硕士学位论文 产权保护问题【1 0 1 。而信任机制对于p 2 p 共享软件来说也是一个严峻问题。如 果没有对共享内容的完整性和同一性的保证，一个p 2 p 应用就会引入许多安 全漏洞的风险1 。同时出于安全考虑，由于防火墙和n a t ( n e t w o r ka d d r e s s t r a n s l a t i o n ) 的存在，严重地降低了i n t e m e t 的透明性。如果不进行处理，许多 p 2 p 系统传输的数据包就不能通过这些设备。这就要求基于p 2 p 网络的应用 系统要进行n a t 的穿透通信【i 2 j 。 结构化p 2 p 网络路由机制的研究，对进一步完善结构化p 2 p 网络，促进 结构化p 2 p 网络的实际应用具有重要作用。 1 2p 2 p 网络技术研究现状 p 2 p 网络( p e e r - t o p e e rn e t w o r k ，即对等网络) 是近几年出现的热门网络 技术，它改变了人们使用网络的方式，也为未来网络的发展提供了新方向， 财富杂志更是将其列为影响i n t e m e t 未来发展的四项技术之一。但p 2 p 技术 却非是一种全新的技术，它可追溯到i n t e r n e t 应用的早期，网络新闻组 u s e n e t 以及f i d o n e t 这两种非常成功的分布式网络都可以被看作是p 2 p 网 络【1 3 】。 p 2 p 网络打破了传统的客户机服务器模式，其中的每个节点的地位都是 对等的，都具有同等的能力和责任。网络中的参与者既是资源( 服务和内容) 提供者，又是资源( 服务和内容) 获取者，在其中每个节点，它们共享它们 所拥有的一部分硬件资源( 处理能力、存储能力、网络连接能力、打印机等) ， 这些共享资源需要由网络提供服务和内容，能被其它对等节点直接访问而无 需经过中间实体。 p 2 p 网络最为人们所熟知的应用在于文件共享，如著名的n a p s t e r l l 4 l 、 k a z a a t 1 、g n u t e l l a u 6 l 、b i t t o r r e n t ( m 等都是利用p 2 p 网络为用户提供文件和其 他内容共享服务。但是p 2 p 网络的概念并不局限于文件的共享，也包括共享 存储资源、计算资源，即时通讯，以及协同处理与服务共享等。 1 2 1p 2 p 网络的优点 p 2 p 网络技术的主要特点在于，它充分利用了分布在各个终端节点上边 缘性的网络资源，其中包括计算资源、带宽资源、内容资源等，以降低对中 2 哈尔滨工程大学硕士学位论文 央服务器资源的消耗需求。与传统的c s 模式相比，p 2 p 网络技术主要有以下 几种特崩埘： ( 1 ) 非中心化：网络中的资源和服务分散在所有节点上，信息的传输和 服务的实现都直接在节点之间进行，可以无需中间环节和服务器的介入，避 免了可能的瓶颈。p 2 p 的非中心化基本特点，带来了其在可扩展性、健壮性 等方面的优势。 ( 2 ) 可扩展性：在p 2 p 网络中，随着节点的加入，不仅服务的需求增加 了，系统整体的资源和服务能力也在同步地扩充，始终能较容易地满足节点 的需要。整个体系是全分布的，不存在扩展瓶颈。理论上其可扩展性几乎可 以认为是无限的。 ( 3 ) 健壮性：p 2 p 结构具有耐攻击、高容错的优点。由于服务是分散在 各个节点之间进行的，部分节点或网络遭到破坏对其它部分的影响很小。p 2 p 网络一般在部分节点失效时能够自动调整整体拓扑，保持其它节点的连通性。 p 2 p 网络通常都是以自组织的方式建立起来的，并允许节点自由地加入和离 开。p 2 p 网络还能够根据网络带宽、节点数、负载等的变化不断地做自适应 式的调整。 ( 4 ) 高性能价格比：性能优势是p 2 p 被广泛关注的一个重要原因。随着 硬件技术的发展，个人计算机的计算和存储能力以及网络带宽等性能依照摩 尔定理高速增长。采用p 2 p 架构可以有效地利用i n t e m e t 中散布的大量普通节 点，将计算任务或存储资料分布到所有节点上。利用其中闲置的计算能力或 存储空间，达到高性能计算和海量存储的目的。通过利用网络中的大量空闲 资源，可以用更低的成本提供更高的计算和存储能力。 ( 5 ) 隐私保护：在p 2 p 网络中，由于信息的传输分散在各节点之间进行 而无需经过某个集中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。 此外，目前解决i n t e m e t 隐私问题主要采用中继转发的技术方法，从而将通信 的参与者隐藏在众多的网络实体之中。在传统的一些匿名通信系统中，实现 这一机制依赖于某些中继服务器节点。而在p 2 p 中，所有参与者都可以提供 中继转发的功能，因而大大提高了匿名通讯的灵活性和可靠性，能够为用户 提供更好的隐私保护。 ( 6 ) 负载均衡：p 2 p 网络环境下由于每个节点既是服务器又是客户端， 哈尔滨工程大学硕士学位论文 减少了对传统c s 结构服务器计算能力、存储能力的要求，同时因为资源分布 在多个节点，更好的实现了整个网络的负载均衡。 1 2 2p 2 p 网络的应用领域 p 2 p 网络引导网络计算模式从集中式向分布式偏移，也就是说网络应用 的核心从中央服务器向网络边缘的终端设备扩散。从当前应用来看，p 2 p 的 应用还主要体现在大范围的共享、搜索的优势上。其中主要更好地解决网络 上四类应用：对等计算、协同工作、搜索引擎、文件交换，此外p 2 p 网络技 术还有许多其他的应用。 ( 1 ) 对等计算：对等网络运算可以帮助企业拥有强大的运算能力。通过 网络连接在一起的包括网络计算机、个人计算机在内的空闲c p u 时间及存储 空间皆可充分利用。利用p 2 p 网络技术来充分整合这些闲置的计算机资源， 不但可以为商业公司节省大项目的运算成本，同时也节省了为此大项目而额 外添置机器设备等硬件产品花费的支出。采用p 2 p 技术的对等计算【1 9 】，正是 把网络中的众多计算机暂时不用的计算能力联结起来，使用积累的能力执行 超级计算机的任务。任何需要大量数据处理的行业都可从对等计算中获利， 如天气预报、动画制作、基因组的研究、新药的研发等。 ( 2 ) 协同工作：商业公司机构的日益分散，给员工和客户提供轻松、方 便的消息和协作的工具，变得日益重要。网络的出现，使协同工作成为可能。 但传统的v j e b 方式实现，给服务器带来了极大的负担，造成了昂贵的成本 支出。p 2 p 网络可以让一个工作小组建立和管理同步及非同步的协同合作， 并提高他们的效率。利用p 2 p 网络技术，可以增进成员间的合作效率和促进 生产力，减少在多个项目间再评估和协调的时间，每个成员都可以访问最新 的数据、充分分享彼此的资源。 ( 3 ) 搜索引擎：p 2 p 技术的另一个优势是开发出强大的搜索工具【2 0 】。p 2 p 技术使用户能够深度搜索文档，而且这种搜索无需通过w e b 服务器，也可以 不受信息文档格式和宿主设备的限制，可达到传统目录式搜索引擎( 只能搜 索到2 0 3 0 的网络资源) 无可比拟的深度。可以说，p 2 p 为i n t e r n e t 的信 息搜索提供了全新的解决方案，g o o g l e 已宣布要采用p 2 p 技术来改进其搜索 引擎。 4 哈尔滨工程大学硕士学位论文 ( 4 ) 文件交互：可以说文件交换的需求直接引发了p 2 p 技术热潮 2 1 1 。在 传统的w e b 方式中，要实现文件交换需要服务器的大力参与，通过将文件上 传到某个特定的网站，用户再到某个网站搜索需要的文件，然后下载。这种 方式的不便之处在于：成本高；参与人数受到网络传输条件限制太大。电子 邮件方便了个人间文件传递，却无法解决大范围的文件交换。这也是w e b 式 文件交换的重要缺陷。如果这种p 2 p 的文件交换方式被推广，那么其将会替 代一切中介网站。 ( 5 ) 其他应用：网络社区，任何有共同兴趣的群体，包括家庭或计算机 业余爱好者，可利用列表和一个网站来创建其自己的互联空间：电子商务， p 2 p 可增加新的功能，包括分布式连接和开通供应链链路，分发信息、内容 或软件，并利用中心目录或搜索功能使信息仍保留在原来的节点上；网络游 戏 2 2 1 ，p 2 p 方式可为开发非集中控制的在线社区游戏提供一个自然平台。开 发人员可将重点放在游戏功能上，而不是与通信协议的接口上。制定游戏规 则的服务商由台前引向幕后，把游戏的控制权完全交给普通用户，这样网民 与网民之间实现了真正直接、简单、自由的沟通。 随着i n t e m e t 上各种p 2 p 应用软件层出不穷，用户数量急剧增加。p 2 p 技术正不断应用到军事领域、商业领域、政府信息、通讯等领域。p 2 p 技术 对目前广泛应用的c s 模式的i n t e m e t 基本构架、人们的上网习惯、企业的 运作方式、相关法律等诸多方面都提出了全新的挑战，有人甚至预言p 2 p 网 络可能会成为未来i n t e m e t 的基础。 1 2 3p 2 p 网络的研究趋势 随着p 2 p 网络技术应用的蓬勃发展，p 2 p 网络的研究也受到了来自其他相 关技术研究的影响。于此同时，p 2 p 网络技术也正在影响着其他的技术，或 者与其他的技术相结合，应用到更多的实际网络应用中去。 1 、网络拓扑结构的研究 基于d h t 技术的p 2 p 网络完全建立在确定性拓扑结构的基础上，从而表 现出对网络中路由的指导性和网络中节点与数据管理的较强控制力。但是， 对确定性结构的认识又限制了路由算法效率的提升。所以网络拓扑结构的研 究是p 2 p 网络研究的一个重要方向。 哈尔滨工程大学硕士学位论文 研究者在分析了目前基于d h t 的发现算法后，发现衡量路由算法的两个 重要参数度数( 表示邻居关系数、路由表的容量) 和链路长度( 路由算法的 平均路径长度) 之间存在渐进曲线的关系。用图论中度数( d e g r e e ) 和直径 ( d i a m e t e r ) 两个参数研究d h t 路由算法，发现这些d h t 路由算法在度数和 直径之间存在渐进曲线关系，如图1 1 所示。在n 个节点网络中，图中直观地 显示出当度数为n 时，路由算法的直径为p ( 1 ) ；当每个节点仅维护一个邻居 时，路由算法的直径为o ( n ) ，这是度数和直径关系的两种极端情况。同时研 究以图论的理论分析o ( a ) 的度和o ( a ) 的直径的算法是不可能的。 维护邻居数( 度) 链路 径) 0 ( 1 )o ( i o g n ) o ( n o ) o ( n ) o ( i o g n i o g l o g n ) 图1 1 度数与直径的渐进关系 如图1 1 所示，渐进曲线关系可以看出，如果想获得更短的路径长度，必 然导致度数的增加；而网络实际连接状态的变化造成大度数邻居关系的维护 复杂程度增加。另外，研究者证明d ( 1 0 9 ) 甚至d ( 1 0 9 l o g l o g ) 的平均路 径长度也不能满足状态变化剧烈的网络应用的需求。新的路由算法受到这种 折衷关系制约的根本原因在于d h t 对网络拓扑结构的确定性n d 认识。 在网络拓扑结构的最新研究中，从提高路由算法的可靠性和寻找随机图 中的最短路径两个方面展开。也就是对覆盖网络的重新认识。其中，s m a l l w o r l d 特征和幂规律证明实际网络的拓扑结构f 2 3 】，不是非结构化系统所认识的 一个完全随机图，也不是d h t 路由算法采用的确定性拓扑结构。幂规律分布 6 哈尔滨工程大学硕士学位论文 的含义可以简单解释为在网络中有少数节点有较高的“度 ，多数节点的“度” 较低。“度较高的节点同其他节点的联系比较多，通过它找到待查信息的 概率较高。s m a l lw o r l d 模型的特性是指网络拓扑具有高聚集度和短链的特 性。在符合s m a l lw o r l d 特性的网络模型中，可以根据节点的聚集度将节点划 分为若干簇( c l u s t e r ) ，在每个簇中至少存在一个度最高的节点为中心节点。大 量研究证明符合s m a l lw o r l d 特征p 2 p 网络中存在大量高连通节点，部分节点 之间存在“短链”现象。 因此，p 2 p 路由算法中如何缩短路径长度的问题变成了如何找到这些“短 链”的问题。尤其是在d h t 路由算法中，如何产生和找到“短链是路由算 法设计的一个新的思路。s m a l lw o r l d 特征的引入会对p 2 p 路由算法产生重大 影响。 2 、搜索查询技术的研究 现有d h t 算法由于采用分布式哈希函数，所以只适合于准确的查找，如 果要支持目前w e b 上搜索引擎具有的多关键字查找的功能，还要引入新的方 法。主要的原因在于d h t 的工作方式【2 4 l 。 基于d h t 的p 2 p 系统采用相容哈希函数根据精确关键词进行对象的定位 与发现。哈希函数总是试图保证生成的哈希值均匀随机分布，结果两个内容 相似度很高但不完全相同的对象被生成了完全不同的哈希值，存放到了完全 随机的两个节点上。因此，d h t 可以提供精确匹配查询，但是支持语义是非 常困难的。 目前在d h t 基础上开展带有语义的资源管理技术的研究还非常少。由于 d h t 的精确关键词映射的特性决定了它无法和信息检索等领域的研究成果结 合，阻碍了基于d h t 的p 2 p 系统的大规模应用。正因为如此，基于d h t 的搜 索查询技术的研究具有重要实际意义。 3 、与其他技术结合的研究 随着p 2 p 网络技术研究的不断深入和应用的日益广泛，p 2 p 技术正在于其 他计算机技术不断地结合。其中p 2 p 技术与组播技术相结合，实现了实时的 视频数据的传播和播放，很好地解决了系统规模的限制和传输的延时问题。 与此同时p 2 p 技术也可以与其他的网络传播技术相结合，如i p t v 技术等，这 将成为未来网络应用的一个主要方向。 7 哈尔滨工程大学硕士学位论文 研究者还发现p 2 p 网络的一些研究方法和规律可以很好地应用到无线传 感器网络的研究中，许多结构化p 2 p 网络协议在改进后都可以很好地解决无 线传感器网络中的问题。同时在无线传感器网络中发现的技术，也可以很好 地促进p 2 p 技术的完善。因此p 2 p 技术将会被应用更多的领域中去，同时与其 他的技术相结合，得到更深入的研究。 1 3 本文的构思及主要工作 本文通过对c h o r d 协议进行改进，提出一种层次化双向路由的结构化p 2 p 网络路由协议h c h o r d ，它采用d h t 技术解决了低效路由的缺陷，通过超级 节点机制避免了由网络中节点的异质性所造成的网络系统瓶颈，使得覆盖网 络可以根据实际物理网络生成层次化的网络结构。超级节点的选择是根据网 络中节点的能力值( 通过对节点的c p u 运算能力、存储能力、n a t 类型以 及带宽等因素综合考虑得出) 。通过对小世界理论的研究，在网络中的节点 建立双向的路由表，实现了消息的双向转发，同时利用转发消息的附加信息 来快速更新节点的路由表，提高网络结构的正确性和一致性。 同时，在v i s u a ls t u d i o2 0 0 5 下用c 拌语言对h c h o r d 网络协议进行模拟。 通过对节点、路由表、关键字、路由消息等实体的实现，模拟现实了物理网 络传输层、覆盖层以及时间驱动层；同时为了方便试验数据的记录整理，设 计实现了命令行层。通过对h c h o r d 网络模型的上进行消息转发，节点加入 退出的模拟试验。在与c h o r d 协议进行多方面的比较分析，验证了h c h o r d 可以提高路由的效率，减少消息查询的跳数，同时较少了为维护路由表所花 费的系统开销。 1 4 本文的内容及组织结构 本文主要讨论层次化双向路由的结构化p 2 p 网络路由机制的相关技术， 在结构上本文主要分为5 个章节，各个章节的主要内容如下： 第1 章为绪论，简要介绍p 2 p 网络技术的现状，以及课题的研究背景和 本文的相关工作。 第2 章，根据对p 2 p 网络的分类，对现有的几种典型的结构化p 2 p 网络 的路由协议进行了分析和比较，其中详细地论述c h o r d 协议。 哈尔滨t 程大学硕士学位论文 第3 章，提出层次化双向路由的路由算法。给出一种节点能力的计算方 法，根据超级节点选择机制实现层次化路由。通过对小世界理论的分析研究， 通过对超级节点建立双向路由表，实现了双向路由。 第4 章，给出一种实现了层次化双向路由的结构化p 2 p 网络协议h c h o r d 协议，并详细阐述h c h o r d 网络的网络结构、超级节点选择、路由表结构以 及h c h o r d 网络动态维护过程。 第5 章，使用c 样语言设计实现了h c h o r d 网络的模型。在实现的h c h o r d 模型上进行了路由算法的模拟仿真试验，通过与c h o r d 协议试验数据的对比 分析，验证h c h o r d 协议，即层次化双向路由路由机制的有效性和正确性。 最后对全文作了一个总结，并说明了课题今后还需要进一步研究的问题 和改进提高的方向。 9 哈尔滨- 下程大学硕士学位论文 第2 章基于分布式哈希表的结构化p 2 p 网络 2 1 p 2 p 网络的分类 由于p 2 p 网络应用各不相同，造成了p 2 p 网络底层拓扑结构的不同。拓扑 结构是指分布式系统中各个计算单元之间的物理或逻辑的互联关系，节点之 间的拓扑结构一直是确定系统类型的重要依据。目前i n t e r n e t 中广泛使用集中 式、层次式等拓扑结构。而i n t e m e t 本身是最大的非集中式的互联网络，但是 2 0 世纪9 0 年代所建立的一些网络应用系统却是完全的集中式的系统、很多 w e b 应用都是运行在集中式的服务器系统上。集中式拓扑结构系统目前面临 着过量存储负载、d o s 攻击等一些难以解决的问题。这时，人们开始关注p 2 p 网络的研究，尤其开始关注p 2 p 网络拓扑结构的研究。根据网络拓扑结构的 不同，主要分为中心化p 2 p 网络、非结构化p 2 p 网络、结构化p 2 p 网络和混合 式p 2 p 网络。 ( 1 ) 中心化p 2 p 网络，拓扑结构以n a p s t e r ，g n u t e l l a 和f r e e n e t t 2 5 i 为代 表，它们采取比较直观的方式实现系统的分布式存储、分布式管理和自组织 的文件存储系统。该拓扑结构由一个中心服务器来负责记录共享信息以及反 馈对这些信息的查询；每一个对等实体要对它所需共享的信息以及进行的通 信负责，根据需要下载它所需要的其他对等实体上的信息。中, c , , j e 务器上只 保留索引信息，此外服务器与对等实体以及对等实体之间都具有交互能力。 中心化p 2 p 网络拓扑结构还存在很多问题，主要表现在中央服务器的瘫痪容 易导致整个网络的崩溃，可靠性和安全性较低；随着网络规模的扩大，中央 目录服务器维护和更新的费用将急剧增加，所需成本过高；中央服务器的存 在引起共享资源在版权问题上的纠纷。对小型网络而言在管理和控制方面占 有一定的优势，但对大型网络应用并不适合。 ( 2 ) 非结构化p 2 p 网络，系统采用完全分布式的拓扑结构，每个节点 之间是比较松散的关系，节点的加入和离开仅需遵循一些简单的规则。非结 构化p 2 p 网络中每个节点保存各自共享的文档，由于不再存在中央目录服务 器，每个节点对本地保存的文档进行索引，并转发或应答其他节点的搜索请 求。在非结构化p 2 p 网络中，资源查找最基本的方式是泛洪( f l o o d i n g ) 或 1 0 哈尔滨工程大学硕士学位论文 类似泛洪的盲目搜索1 2 6 1 。每个节点都将接到的搜索请求转发给所有的邻居节 点，并由邻居节点进一步转发给更多的邻居节点，直至找到期望的文档或达 到系统允许的最大查找跳数后搜索失败。如果成功找到所需的文档，那么搜 索请求的发起节点直接从期望文档的保存节点那里下载所需文档。由于没有 确定拓扑结构的支持，非结构化p 2 p 网络无法保证资源发现的效率。即使需 要查找的目标节点存在，发现也有可能失败。由于采用t t l 、泛洪和随机转 发机制，因此路由直径不可控，可扩展性较差。从而发现的准确性和可扩展 性是非结构化p 2 p 网络面临的两个重要问题。 ( 3 ) 结构化p 2 p 网络，具有全分布式拓扑结构，通常采用的是分布式 哈希表的结构，因此也称为d h t 网络。和非结构p 2 p 网络相比，结构化p 2 p 网络对文档在系统中的存放位置有严格的控制并且节点之间的关系比较紧 凑。结构化p 2 p 网络的最大优点在于，它可以在o ( 1 0 9 n ) ( 其中n 是系统中 节点的数目) 跳数之内完成文档的路由和定位。结构化p 2 p 网络的主要特点 是自组织、可扩展、负载均衡、以及较好的容错性。和非结构p 2 p 网络下要 用于文件共享领域不同，结构化p 2 p 网络的这些优良特性使得它可以应用在 对可靠性和扩展性要求比较高的场合。 ( 4 ) 混合式p 2 p 网络，吸取了中心化结构和全分布式非结构化拓扑的 优点，选择性能较高( 处理、存储、带宽等方面性能) 的节点作为超级节点 ( s u p e r n o d e ) 在各个超级节点上存储了系统中其他部分节点的信息，路由算法 仅在超级点之间转发，超级点再将查询请求转发给适当的叶子节点。混合式 结构也是一个层次式结构，超级点之间构成一个高速转发层，超级节点和所 负责的普通节点构成若干层次，k a z a a 软件就是最典型的实际应用案例。 2 2 结构化p 2 p 网络的基础d h t 技术 在前面章节的介绍中，可以发现结构化p 2 p 网络路由算法的基础是d h t 技术，即分布式哈希表技术。在p 2 p 通信中引入d h t ，是为了在实际网络之 上建立一层结构化的o v e r l a y 层( 即逻辑层或者覆盖层) ，以便于信息的查找， 而不需要像g n u t e l l a 那样每次查找信息都要进行泛洪查找。基于这种思想产 生了各种结构不同的基于d h t 的结构化p 2 p 网络，这些结构化p 2 p 网络协 议的主要不同是对于p 2 p 网络中节点的组织方式，但不论使用哪种模型，在 哈尔滨工程大学硕士学位论文 节点加入d h t 网络时都需要为节点哈希产生一个标识节点的n o d e l d ，从而 决定它在d h t 网络中的位置，以及它在逻辑网络中的邻居表( 路由表) 。每 个节点要维护一些资源信息，艮p ( k e y ，v a l u e ) 对，k e y 决定存储的目标节点， v a l u e 则是存储在目标节点的信息，该信息可以是内容的索引，也可能是内容 本身。节点进行信息的插入和查找时，同样也是对关键字k e y 进行哈希，产 生一个i d ，找到节点n o d e l d 与此i d 最接近的节点，进行操作。 d h t 的基本思想就是在文件与节点之间建立一定的关系，即文件信息按 照一定的规则存储在节点上。在结构化的p 2 p 系统中，一个文件与一个k e y 值 相对应( 一般通过对文件进行哈希得到) ，系统中的每个节点负责保存一定 范围的k e y 值。无论内部的搜索算法如何，应用接口均由p u t ( k e y ，v a l u e ) 和 g e t ( k e y ) i s 两个函数组成，其中p u t ( k e y ，v a l u e ) 的功能是进行节点的信息发布， g e t ( k e y ) 的功能是进行信息查询。 2 3 典型的结构化p 2 p 网络 结构化p 2 p 网络都采用d h t 结构，它能够自适应节点的动态加入退出， 具有良好的可扩展性、鲁棒性、节点i d 分配的均匀性和自组织能力。由于覆 盖网络采用了确定性拓扑结构，d h t 可以提供精确的发现。只要目的节点存 在于网络中d h t 总能发现它，发现的准确性得到了保证。 目前国内外基于结构化p 2 p 网络的研究主要有c h o r d ，c a n ，t a p e s t r y ， p a s t r y ，k a d e m l i a t ：n ，v i c e r o y 和k o o r d e t 2 8 1 等。本节将详细介绍前5 种结构化 p 2 p 网络，并在性能上对它们进行比较分析。 2 3 1c h o r d c h o r d 是u cb e r k e l e y 和m i t 共同提出的一种分布式查找算法，目的是 为了能在p 2 p 网络中查找数据。如果给定一个关键字，c h o r d 可以有效地把 该关键字映射到网络中某个节点上。因而在p 2 p 网络中只要给每个数据v 都 赋予一个关键字k ，就可以利用c h o r d 在该关键字映射的节点上存储或提取 相应的( k ，v ) 对。c h o r d 的突出特点是算法简单，而且可扩展一查询过程的通 信开销和节点维护的状态随着系统总节点数增加成指数关系。c h o r d 的路由 性能优于c a n ，而节点加入过程和维护开销又优于t a p e s t r y 和p a s t r y 。 1 2 哈尔滨工程大学硕十学位论文 1 、c h o r d 的设计 c h o r d 中每个关键字和节点都分别拥有一个m 比特的标识符。关键字标 识符k 通过哈希关键字本身得到，而节点标识符n 则通过哈希节点的i p 地 址得到。哈希函数可以选用s h a 1 。所有节点按照其节点标识符从小到大( 取 模2 m 后) 沿着顺时针方向排列在一个逻辑的标识圆环上( 称为c h o r d 环) 。 c h o r d 的映射规则是：关键字标识为k 的，v ) 对存储在这样的节点上，该 节点的节点标识等于k 或者在c h o r d 环上紧跟在k 之后，这个节点被称为k 的后继节点，表示为s u c c e s s o r ( k ) 。因为标识符采用m 位二进制数表示，并 且从0 到2 m 一1 顺序排列成一个圆圈，s u c c e s s o r ( k ) 就是从k 开始顺时针方向 距离k 最近的节点。图2 1 给出了一个具有6 比特标识符的c h o r d 环。 n l 图2 1 一个具有6 比特标识符的c h o r d 环 图2 1 给出了一个m = 6 的c h o r d 环，环中分布了1 0 个节点，存储5 个 关键字，节点标识前加上n 而关键字前加上k 以示区别。因为 s u c c e s s o r ( 1 0 ) = 1 4 ，所以关键字1 0 存储到节点1 4 上。同理，关键字2 4 和3 0 存储到节点3 2 上，关键字3 8 存储到节点3 8 上，而关键字5 4 则存储到节点 5 6 上。当网络中的节点发生变动时，上面的映射规则仍然要成立。为此，当 某节点n 加入网络时，某些原来分配给n 的后继节点的关键字将分配给n 。 当节点n 离开网络时，所有分配给它的关键字将重新分配给n 的后继节点。 哈尔滨1 二程大学硕士学位论文 除此之外，网络中不会发生其他的变化。以图2 1 为例，当标识为2 6 的节点 接入时，原有标识为3 2 的节点负责的标识为2 4 的关键字将转由新节点存储。 显然，为了能在系统中转发查询报文，每个节点要了解并维护c h o r d 环上相 邻节点的标识和i p 地址，并用这些信息构成自身的路由表。有了这张表， c h o r d 就可以在环上任意两点间进行寻路。 2 、c h o r d 的路由 一 c h o r d 中每个节点只要维护它在环上的后继节点的标识和i p 地址就可以 完成简单的查询过程。对特定关键字的查询报文可以通过后继节点指针在圆 环上传递，直到到达这样一个节点：关键字的标识落在该节点标识和它的后 继节点标识之间，这里的后继节点就是存储目标( k ，v ) 对的节点。 如图2 2 所示给出了一个示例，节点8 发起的查找关键字5 4 的请求，通 过后继节点依次传递，最后定位到存储有关键字5 4 的节点5 6 。在这种简单 查询方式中，每个节点需要维护的状态信息很少，但查询速度太慢。若网络 中有n 个节点，查询的代价就为o ( u ) 数量级。因而在网络规模很大时，这 样的速度是不能接受的。 n 1 图2 2c h o r d 换上的查询请求 为了加快查询的速度，c h o r d 使用扩展的查询算法。为此，每个节点需 要维护一个路由表，称为指针表( f i n g e rt a b l e ) 。如果关键字和节点标识符 用r l l 位二进制位数表示，那么指针表中最多含有m 个表项。节点n 的指针表 中第i 项是圆环上标识大于或等于n + 2 的第一个节点( 比较计算以2 m 为模 1 4 哈尔滨工程大学硕+ 学位论文 进行) 。例如若s = s u c c e s s o r ( n + 2 i q ) ，1 4 2 a = 目的 节点4 2 a d ( 这里幸表示通配符) 。这种方式类似于i p 分组转发过程中的最 长前缀匹配。节点n 的邻居映射表分为多个级别，每个级别包含的邻居节点 的数量等于标识符表示法的基数，而每个级别中邻居节点标识符和本节点标 1 9 哈尔滨_ 下程大学硕十学位论文 识符的相同前缀都比前一级别多一个数位。也就是说，第j 级邻居表的第i 项是标识符以p r e f i x ( n ，j 1 ) + “i ”为前缀且距离当前节点最近的邻居节点。例 如，节点3 2 5 a e 的邻居映射表中第4 级第9 项是系统中标识符以 3 2 5 + “9 ”= 3 2 5 9 为前缀的某个节点。 3 、t a p e s t r y 的路由机制 当一条查找消息到达传递过程中的第1 3 个节点时，该节点和目的节点的 共同前缀长度至少大于n 。为了进行转发，该节点将查找邻居映射表的第n + l 级中和目的标识符下一数位相匹配的邻居节点。转发过程将在每个节点中依 次进行直到到达目的节点。这种方法可以保证路由至多经过l o g 。n 个节点就 可以到达目的节点，这里是节点标识符名字空间的大小，而b 是标识符使 用的基数。同样，由于每个节点的邻居映射表的每个级别只需要保存b 个表 项，因此，邻居映射表的空间为b l o g 。n 。 t a p e s t r y 中的节点在共享数据时被称为服务器，请求数据时被称为客户， 转发消息时被称为路由器。也就是说每个节点可以同时具有客户、服务器和 路由器的功能。 服务器s 通过向对象o ( g u i d 为) 的根节点d 。定期的发送消息来 报告s 保存有对象d 。在这条发布路径上的每个节点都保存关于