（计算机系统结构专业论文）结构化p2p覆盖网路由算法研究.pdf

c l a s s if i e di n d e x ： u d c ： ad i s s e r t a t i o nf o rt h ed e g r e eo fm e n g r e s e a r c ho n r o u t i n ga l g o r i t h m i n s t r u c t u r e dp e e r - t o p e e ro v e r l a yn e t w o r k s c a n d i d a t e ：w a n g z h e n h u i s u p e r v i s o r ：a s s o c i a t ep r o f iq i a nz h e n a c a d e m i cd e g r e ea p p l i e df o r ：m a s t e ro fe n g i n e e r i n g s p e c i a l i t y ：c o m p u t e ra r c h i t e c t u r e d a t eo fs u b m i s s i o n ：j a n u a r y , 2 010 d a t eo fo r a le x a m i n a t i o n ：m a r c h ，2 010 u n i v e r s i t y ：h a r b i ne n g i n e e r i n gu n i v e r s i t y 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用己在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：孑栅 日期：妒年；月，s 日 哈尔滨工程大学 学位论文授权使用声明、 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文沁佐授予学位后即可口在授予学位1 2 个月后口解 密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等a 作者( 签字) ：讲醑导师( 签字) 鹏 - 日期：i 沙年；月c 歹日 z l ql o 年月才日 k -i 哈尔滨t 程大学硕士学位论文 摘要 结构化p 2 p 覆盖网络是一种维护节点之间在应用层上互联的组织方法， 它按照一定的逻辑拓扑结构将系统中的节点互连起来，并通过路由消息使得 系统中任意两个节点可以互相通信。在p 2 p 网络中，有固定物理线路连接的 节点可以直接传递消息，而彼此非临近的节点则需经过中间节点通信，消息 在传递到目的节点之前要经过一个或者多个中间节点。如何将消息快速可靠 的路由到目的节点或者是目标资源的位置，如何在保证效率的同时降低路由 查找过程中网络带宽的占用率，己成为p 2 p 网络中研究的热点问题。 本文在对p 2 p 路由查找算法p a s t r y 深入研究的基础上，针对路由查找效 率和网络带宽占用率进行优化和改进，论文所做工作和取得的成果如下： 1 、为提高p 2 p 存储节点的路由效率，对原有的p a s t r y 路由算法进行优 化和改进。提出一种基于高频缓存机制的路由查找算法，引入高频缓存节点 集，使得在路由过程中每个节点可以快速查找经过自身而被频繁访问节点的 路由信息，从而提高频繁访问节点的路由效率。 2 、为使p 2 p 网络节点维护高效的路由表，需通过节点探测方法来确定 路由节点的存活状态。针对路由节点存活性，提出了一种能够对过去的连接 信息进行统计并决定是否进行探测的定期探测方法，在保证效率的前提下， 减少探测的次数，从而减少了对网络带宽的占用。 3 、最后本文在p e e r s i m 模拟试验平台上通过对比实验，实验结果验证了 本文所提改进方法的有效性。 关键词：p 2 p 存储系统；高频缓存；节点状态；定期探测 哈尔滨工程大学硕士学位论文 a b s t r a c t s t r u c t u r e dp 2 po v e r l a yn e t w o r kt h a ta c c o r d i n gt oc e r t a i nl o g i c a lt o p o l o g yo f t h en o d e si nt h es y s t e mi n t e r c o n n e c ti st h eo r g a n i z a t i o n a lm e t h o dw h i c hm a i n t a i n 。 b e t w e e nt h en o d e st oi n t e r c o n n e c to nt h ea p p l i c a t i o nl a y e r ，a n dt h r o u g hr o u t i n g m e s s a g e sm a k ea n yt w on o d e sc a nc o m m u n i c a t ew i t he a c ho t h e r i nt h ep 2 p n e t w o r k ，t h en o d ew h i c ht h ef i x e dp h y s i c a lc i r c u i tc o n n e c t st op a s sm e s s a g e s d i r e c t l y ，b u te a c ho t h e rn o n n e i g h b o r i n gn o d e sm u s tg ot h r o u g hi n t e r m e d i a t e n o d e sc o m m u n i c a t i o n , t h em e s s a g eb e f o r ed e l i v e r e dt ot h ed e s t i n a t i o nn o d em u s t p a s st h r o u g ho n eo rm o r ei n t e r m e d i a t en o d e s h o wf a s ta n dr e l i a b l em e s s a g e r o u t i n gt ot h ed e s t i n a t i o nn o d e ，o rt h el o c a t i o no ft h et a r g e tr e s o u r c e s ，h o wt o e n s u r et h ee f f i c i e n c ya n dr e d u c et h er o u t es e a r c hp r o c e s so fn e t w o r kb a n d w i d t h o c c u p a n c yr a t e ，p 2 pn e t w o r k s h a v eb e c o m ea h o ti s s u ei nt h es t u d y i nt h i sp a p e r ，t h er o u t i n go fp 2 ps e a r c ha l g o r i t h m sp a s t r yi n - d e p t hs t u d y ， b a s e do nt h es e a r c hf o r t h er o u t i n ge f f i c i e n c ya n dn e t w o r kb a n d w i d t hu s a g e o p t i m i z a t i o na n di m p r o v e m e n t ，t h ep a p e rw o r k sa n dr e s u l t sa sf o l l o w s ： 1 i no r d e rt oi m p r o v et h ee f f i c i e n c yo fp 2 ps t o r a g en o d ei nt h er o u t i n go ft h e o r i g i n a lp a s t r yr o u t i n ga l g o d t h r ni so p t i m i z e da n di m p r o v e d p r o p o s eac a c h i n g m e c h a n i s mb a s e do nh i g h - f r e q u e n c yr o u t i n gs e a r c ha l g o r i t h m ，t h ei n t r o d u c t i o no f h i g h - f r e q u e n c yc a c h en o d e s e t ，a l l o w i n ge a c hn o d ei nt h er o u t i n gp r o c e s sc a n q u i c k l y s e a r c ht h r o u g ht h e i ro w na n da r ef r e q u e n t l yv i s i t e dn o d er o u t i n g i n f o r m a t i o n ，t h e r e b ye n h a n c i n gt h ee f f i c i e n c yo ff r e q u e n ta c c e s st o t h er o u t i n g n o d e 2 i no r d e rt om a k et h ep 2 pm e m o r ys y s t e mm a i n t a i nh i g he f f i c i e n c yr o u t i n g 1 i s tw h i c hm u s td e t e r m i n et h es u r v i v a lc o n d i t i o no ft h er o u t en o d et h r o u g h d e t e c t i o nm e t h o do ft h en o d e f o rt h es u r v i v a lo ft h er o u t i n gn o d ew ep r o v i d ea r e g u l a rs u r v e ym e t h o dt h a tc a l lc o u n tt h ec o n n e c t i o ni n f o r m a t i o ni nt h ep a s ta n d d e c i d ew h e t h e rt od e t e c to rn o t ，u n d e rt h eg u a r a n t e ee f f i c i e n c y sp r e m i s e ，r e d u c e d t h es u r v e yt h en u m b e ro ft i m e s ，t h u sr e d u c et h en e e df o rn e t w o r kb a n d w i d t h 哈尔滨t 程大学硕士学位论文 u s a g e 3 f i n a l l y ，c o n t r a s tt ot h ee x p e r i m e n tr e s u l tw i t ht h ep e e r s i ms i m u l a t i o n p l a t f o r m ，t h ev a l i d i t yo ft h em e t h o dp r o p o s e db yt h i sp a p e rw a sc o n f o r m e d k e y w o r d s ：p 2 ps t o r a g es y s t e m ；h i g h f r e q u e n c yb u f f e r ；n o d es t a t u s ；r e g u l a r e x p l o r a t i o n 怕 一 _ 哈尔滨工程大学硕士学位论文 目录 第1 章绪论l 1 1 课题背景及意义l 1 2 论文研究内容2 1 3 论文组织结构2 第2 章结构化p 2 p 覆盖网路由算法研究概述”4 2 1 结构化p 2 p 覆盖网概述4 2 1 1p 2 p 覆盖网概念4 2 1 2 原理及发展趋势1 1 2 1 3 主要研究问题“1 3 2 1 4 与非结构化比较“1 4 2 2p 2 p 路由算法研究现状分析16 2 2 1p 2 p 路由算法概述16 2 2 2p 2 p 路由算法主妻研究问题17 2 2 3p 2 p 路由算法国内外研究现状1 8 2 3 本章小结2 l 第3 章基于高频缓存的路由查找2 2 3 1 引言2 2 3 2 典型结构化p 2 p 路由算法及比较”2 3 3 2 1c h o r d 2 3 3 2 2c a n 2 5 3 2 3p a s t r y 2 6 3 2 4t a p e s t r y 2 7 3 3 一种改进的基于高频缓存的路由查找算法3 0 3 3 1 路由表项结构3 0 3 3 2 路由查找过程”3 3 3 3 3 拓扑结构维护一3 5 3 4 本章小结3 6 ；面。赫赫茹茹赢；赫赫蕊南o 高磊_ 赫五磊赫；茹谳而磊晶二嘲赢茹惭唧卵二旰一每蔷一”一；v m - 一一，茹鳓一w 前一w 一品赢 哈尔滨丁程大学硕七学位论文 第4 章基于状态的路由节点定期探测方法3 7 4 1 引言3 7 4 2 一种改进的基于状态的路由节点定期探测方法3 8 4 2 1 路由表项结构一3 8 4 2 2 具体步骤”3 8 4 2 3 探测流程3 9 4 3 本章小结4 2 第5 章模拟实验与结果分析4 3 5 1 设计思想4 3 5 2 实验环境4 3 5 2 1 实验软硬件平台4 3 5 2 2 网络仿真与相关工具“4 4 5 3 仿真过程4 8 5 4 实验结果与分析4 9 5 4 1 基于高频缓存机制的路由查找算法4 9 5 4 2 基于状态的路由节点定期探测方法”5 0 5 4 3 实验结果分析5l 5 5 本章小结51 结论5 2 参考文献5 3 攻读硕士学位期间发表的论文和取得的科研成果5 6 致谢5 7 哈尔滨丁程大学硕士学位论文 1 1 课题背景及意义 第1 章绪论 p 2 p ( p e e r t o p e e r ) 是近年来广受业界关注的一个概念。随着网络环境 的不断改善，网络应用的不断丰富，网络资源的需求和应用的日渐复杂，单 纯依靠传统的客户端n 务器模式的存储体系结构已经难以满足现代社会对 先进网络文件系统的要求。与此同时，广大的网络用户的终端设备的计算和 存储能力以及连接带宽却随着摩尔定理而不断地增长，而p 2 p 存储技术的出 现，大大提高了这些终端节点的利用率，从而进一步提升网络、设备和信息 服务的效能，为实现新一代的海量、可靠、安全、易用的面向i n t e m e t 的高 性能分布式文件存储系统带来了曙光。 当前，p 2 p 系统所产生的网络流量已经超过h t t p 等其它协议所产生的网 络流量，成为占据网络带宽的首要应用。p 2 p 系统的体系结构也发生了由 n a p s t e r t l 】的集中查询到g n u t e l l a 2 的自由连接( u n s t r u c t u r e do v e r l a yn e t w o r k ) 、 再到k a z a a 的偏向于强节点的自由连接的逐步演变。但是，由于自由连接的 随意性，使得数据查询必须依靠广播或者随机走步的搜索来完成，耗费大量 的网络开销，因此，系统的可扩展性受到严重限制。于是，近年来提的结构 化覆盖网( s t r u c t u r e do v e r l a yn e t w o r k ) 以及基于结构化覆盖网的分布式哈希 表( d h t d i s t r i b u t e dh a s ht a b l e ) 算法成为研究领域的热点。 根据节点的互连方式，p 2 p 可以分为无结构p 2 p 和结构化p 2 p 两类。无 结构的p 2 p 主要采用广播方式查询资源，会带来巨大的查询消息开销，造成 网络流量负担。结构化p 2 p 基于d h t 对拓扑结构有很严格的控制，数据存 放的位置和查询算法都有很精确的定义或描述，即使系统的状态在连续变化， 某一数据项所在节点的位置也总是可以被找到的，但如何快速的找到用户所 需的资源就要依靠路由的帮助。 数据路由及定位是p 2 p 系统最基本的功能，研究如何通过节点间的转发 把数据实际传送到特定节点。路由是否高效直接影响到系统服务的性能，因 此路由策略是系统的一个关键问题。 哈尔滨t 程大学硕十学位论文 由于现在p 2 p 网络规模的急剧扩张，现有的p 2 p 路由算法的受到了严峻 的挑战，随之而来的问题也慢慢的体现出来。首先路由算法的好快直接影响 到查询的速度，这是直接关系到服务质量的属性，在以百万计的p 2 p 网络中 找到目标主机上的目标文件并不是一件轻松的事。其次，由于网络资源的不 均衡分配，导致部分网络资源的浪费和部分网络资源的紧张，因此研究和优 化结构化p 2 p 覆盖网路由算法并尽可能降低路由过程中对网络带宽的占用 率，对于推动p 2 p 网络技术的发展和应用，具有重要的理论价值和实际意义。 1 2 论文研究内容 本文深入研究了结构化p 2 p 覆盖网，在对比分析了现有的p 2 p 路由算法 的缺点的基础上，针对p a s t r y 路由算法进行优化和改进。具体研究内容如下： l 、为了提高p 2 p 网络节点的路由查找效率，提出一种基于高频缓存机 制的路由查找算法。该算法在原有p a s t r y 路由算法的基础上通过引入高频缓 存节点集，使得在路由过程中每个节点可以快速查找经过自身而被频繁访问 节点的路由信息，从而提高频繁访问节点的路由效率。 2 、为了降低路由节点存活性探测过程中的网络带宽占用率，提出一种基 于节点状态的定期探测方法。该方法能够对过去的连接信息进行统计并决定 是否进行探测。在保证p 2 p 网络节点维护高效的路由表的前提下，通过节点 探测方法来确定路由节点的存活状态，减少了探测的次数，从而减少了对网 络带宽的占用。 3 、设计模拟试验环境用于验证本文所提算法的可行性和有效性。通过模 拟p 2 p 网络环境，检测算法的可行性，观察系统效率是否有所提高。 1 3 论文组织结构 论文内容组织如下： 第l 章介绍了本课题的研究背景及意义，并指出了本课题的主要研究内 容及组织结构。 第2 章详细介绍了结构化p 2 p 覆盖网及其路由算法并作了总结，介绍p 2 p 覆盖网的概念、原理及应用，分析了主要研究的问题以及与非结构化网络的 哈尔滨工程大学硕十学位论文 对比；介绍了p 2 p 路由算法的研究现状，并由此引入对路由算法设计的分析。 第3 章介绍基于高频缓存机制的路由查找算法，通过对已有结构化路由 算法的比较，根据p a s t r y 路由协议的特点，提出改进目的，然后详细介绍了 本课题的改进方案引入缓存机制。 第4 章介绍了基于状态的路由节点定期探测方法，通过比较现有定期探 测方法，引出本课题研究目的及内容，并详细介绍了算法流程。 第5 章综合了第3 章和第4 章的改进方案，对改进后的路由算法进行了 实验仿真，并根据仿真结果进行路由效率分析和占用带宽分析。 最后对本文进行总结，并对未来将要开展的研究进行展望。 哈尔滨工程大学硕+ 学何论文 第2 章结构化p 2 p 覆盖网路由算法研究概述 2 1 结构化p 2 p 覆盖网概述 2 1 1p 2 p 覆盖网概念 早期的第一代p 2 p 网络如f r e e n e t ，g n u t e l l a t 2 等，用于在互联网上共享 文件，是一种非结构化的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 ) 1 3 】。 在覆盖网中任意两个节点间可以通信，消息通过网络的边进行传播，节点之 间完全平等。 在结构化网络中每个节点存储的信息与网络拓扑结构有关，通过映射完 成，查找采用基于d h t 分布式散列路由搜索算法。而非结构化网络则与网络 拓扑无关，其节点可任意存储信息，查找采用基于广度优先的搜索算法及其 改进算法。这两种不同结构的网络所采取的搜索技术是完全不同的。 p 2 p 网络模型同传统的c s 结构不同，在p 2 p 网络中，没有客户机和 服务器之分，每台p 2 p 网络中的计算机都既是服务器又是客户机，大家之间 是平等的，即对等的，这就是p e e r - t o p e e r 的含义所在。在这种网络模型下， 不需要高性能的计算机充当服务器的角色，来为众多的客户机服务，反而是 4 哈尔滨工程大学硕士学伊论文 加入网络的机器越多整个系统的性能越高，可扩展性非常好，因而这种网络 模型近来成为研究热点，也有一些实用的系统出现。 结构化p 2 p 模式是一种采用纯分布式的消息传递机制和根据关键字进行 查找的定位服务，目前的主流方法是采用分布式哈希表( d h t ) 技术，这也 是目前扩展性最好的p 2 p 路由方式之一。由于d h t 各节点并不需要维护整 个网络的信息，只在节点中存储其临近的后继节点信息，因此较少的路由信 息就可以有效地实现到达目标节点，同时又取消了泛洪算法。该模型有效地 减少了节点信息的发送数量，从而增强了p 2 p 网络的扩展性。同时，出于冗 余度以及延时的考虑，大部分d h t 总是在节点的虚拟标识与关键字最接近 的节点上复制备份冗余信息，这样也避免了单一节点失效的问题。 结构化p 2 p 网络是指像c a n 4 1 、c h o r d 5 1 、p a s t r y 6 1 、t a p e s t r y _ 【7 】之类的点 对点的网络。这类网络中每个节点都有固定的地址，整个网络具有相对稳定 和规则的拓扑结构。依赖拓扑结构，可以给网络的每一个节点指定一个逻辑 地址，并把地址和节点对应起来。动态散列表是大多数结构化p 2 p 网络所采 取的资源定位方式。首先将网络中的每一个节点分配虚拟地址( v i d ) ，同时 用一个关键字( k e y ) 来表示其可提供的共享内容。取一个散列函数，这个 函数可以将k e y 转换成一个散列值h ( k e y ) 。网络中节点相邻的定义是散 列值相邻。发布信息的时候就把( k e y ，v i d ) 二元组发布到具有和h ( k e y ) 相近地址的节点上去，其中v i d 指出了文档的存储位置。资源定位的时候， 就可以快速根据h ( i 江y ) 到相近的节点上获取二元组( k e y ，v i d ) ，从而 获得文档的存储位置【8 1 。不同的d h t 算法决定了p 2 p 网络的逻辑拓扑，比如 c a n 就是一个n 维向量空间，而c h o r d 是一个环形拓扑，t a p e s t r y 则是一个 网状的拓扑。基于d h t 这类结构搜索算法最大的问题是d h t 的维护机制较 为复杂，尤其是节点频繁加入退出造成的网络波动，极大地增加了d h t 的维 护代价。这类搜索算法存在的另外一个问题是d h t 仅支持精确关键词匹配查 询，无法支持内容、语义等复杂查询。这是由于其采用相容散列函数根据精 确关键词进行对象的定位与发现，散列函数总是试图保证生成的散列值均匀 随机分布，结果两个内容相似度很高但不完全相同的对象被生成了完全不同 的散列值，存放到了完全随机的两个节点上。目前在d h t 基础上开展带有语 义的资源管理技术的研究还非常少。也正是由于d h t 的精确关键词映射的特 哈尔滨t 程大学硕士学何论文 性决定了无法和信息检索等领域的研究成果结合，才阻碍了基于d h t 的p 2 p 系统的大规模应用。 结构化p 2 p 覆盖网络是一种维护节点之间在应用层上互联的组织方法。 它按照一定的逻辑拓扑结构将系统中的节点互连起来，并通过路由消息使得 系统中任意两个节点可以互相通信。在有节点动态加入和退出的情况下，结 构化p 2 p 覆盖网络要能够保证节点之间的互连性【9 】。图2 1 中所示为结构化 覆盖网络的名字空间，在整个环形网络中，可定义很多个点。 0 0 1 2 1 2 41 88 图2 1 结构化覆盖网络的名字空间 4 8 图2 2 结构化覆盖网络上的存储操作 p 2 p 网络是一种具有较高扩展性的分布式系统结构，其对等概念是指网 络中的物理节点在逻辑上具有相同的地位，而并非处理能力的对等。以 n a p s t e r 软件为代表的p 2 p 技术其实质在于将互联网的集中管理模式引向分 散管理模式，将内容从中央单一节点引向网络的边缘，从而充分利用互联网 哈尔滨t 程大学硕十学位论文 中众多终端节点所蕴涵的处理能力和潜在资源。相对于传统的集中式客户 服务器( c s ) 模型，p 2 p 弱化了服务器的概念，系统中的各个节点不再区分服 务器和客户端的角色关系，每个节点既可请求服务，也可提供服务，节点之 间可以直接交换资源和服务而不必通过服务器。 p 2 p 系统最大的特点就是用户之间直接共享资源，其核心技术就是分布 式对象的定位机制，这也是提高网络可扩展性、解决网络带宽被吞噬的关键 所在。迄今为止，p 2 p 网络已经历了三代不同网络模型，各种模型各有优缺 点，有的还存在着本身难以克服的缺陷，因此在目前p 2 p 技术还远未成熟的 阶段，各种网络结构依然能够共存，甚至呈现相互借鉴的形式。p 2 p 的控制 层面的实现有不同的方式，据此所有的对等网络的应用可以归结为如下三种 体系结构： 1 、集中目录式结构 集中目录式p 2 p 结构是最早出现的p 2 p 应用模式，因为仍然具有中心化 的特点也被称为非纯粹的p 2 p 结构。用于共享m p 3 音乐文件的n a p s t e r 是其 中最典型的代表，如图2 3 所示。其用户注册与文件检索过程类似于传统的 c s 模式，区别在于所有资料并非存储在服务器上，而是存贮在各个节点中。 查询节点根据网络流量和延迟等信息选择合适的节点建立直接连接，而不必 经过中央服务器进行。这种网络结构非常简单，但是它显示了p 2 p 系统信息 量巨大的优势和吸引力，同时也揭示了p 2 p 系统本质上所不可避免的两个问 题：法律版权和资源浪费的问题。 图2 3 集中目录式p 2 p 模型 对簿节点 o 中刚婚 q ：清求 r ：响应 d ：文件下载 哈尔滨t 程大学硕十学位论文 该体系结构使用了一个中央服务器来进行控制操作，所有的客户机登录 到中央服务器，服务器负责管理所有客户机的文件和用户数据库。文件的搜 索请求发送到服务器，如果找到文件，那么文件就可以从拥有该文件的对等 体上直接下载。在这种情况下，服务器维护一个所有对等体的文件的数据库。 然而这种结构遇到了文件的版权问题，因为服务器要为传播的所有这些文件 的版权负责。这种对等网络结构的特点是有高效的查找过程，查找有较小的 开销，查找经过的路径跳数少。 2 、纯p 2 p 网络模型 纯p 2 p 模式也被称作广播式的p 2 p 模型。它取消了集中的中央服务器， 每个用户随机接入网络，并与自己相邻的一组邻居节点通过端到端连接构成 一个逻辑覆盖的网络。对等节点之间的内容查询和内容共享都是直接通过相 邻节点广播接力传递，同时每个节点还会记录搜索轨迹，以防止搜索环路的 产生。 g n u t e l l a 模型是现在应用最广泛的纯p 2 p 非结构化拓扑结构，如图2 4 所示。它解决了网络结构中心化的问题，扩展性和容错性较好，但是g n u t e l l a 网络中的搜索算法以泛洪的方式进行，控制信息的泛滥消耗了大量带宽并很 快造成网络拥塞甚至网络的不稳定。同时，局部性能较差的节点可能会导致 g n u t e l l a 网络被分片，从而导致整个网络的可用性较差，另外这类系统更容 易受到垃圾信息，甚至是病毒的恶意攻击。 图2 4g n u t e l l a 分布式p 2 p 网络模型 8 ( d 对等节点 q ：蒲求 q h ：请浆禽中 d ：下裁 哈尔滨工程大学硕士学位论文 纯粹分布式对等网络根本不需要中央服务器，查询以泛洪的方式在网络 中传播，收到查询消息的节点再查找本地文件，然后把结果发回给查询节点。 因为这种结构会产生很多的查询流量，使得网络有太多的额外开销，所以该 体系结构并不常用。但f r e e n e t 仍然使用该结构，因为这种结构有较好的匿 名性，也消除了单点失败的问题。 3 、混合式网络模型 k a z a a 模型是p 2 p 混合模型的典型代表，如图2 5 所示。它在纯p 2 p 分 布式模型基础上引入了超级节点的概念，综合了集中式p 2 p 快速查找和纯 p 2 p 去中心化的优势。k a z a a 模型将节点按能力不同( 计算能力、内存大小、 连接带宽、网络滞留时间等) 区分为普通节点和搜索节点两类( 也有的进一 步分为三类节点，其思想本质相同) 。其中搜索节点与其临近的若干普通节 点之间构成一个自治的簇，簇内采用基于集中目录式的p 2 p 模式，而整个p 2 p 网络中各个不同的簇之间再通过纯p 2 p 的模式将搜索节点相连起来，甚至也 可以在各个搜索节点之间再次选取性能最优的节点，或者另外引入一新的性 能最优的节点作为索引节点来保存整个网络中可以利用的搜索节点信息，并 且负责维护整个网络的结构。 图2 5 混合式p 2 p 网络模型 由于普通节点的文件搜索先在本地所属的簇内进行，只有查询结果不充 分的时候，再通过搜索节点之间进行有限的泛洪。这样就极为有效地消除纯 p 2 p 结构中使用泛洪算法带来的网络拥塞、搜索迟缓等不利影响。同时，由 于每个簇中的搜索节点监控着所有普通节点的行为，这也能确保一些恶意的 9 哈尔滨工程大学硕七学位论文 攻击行为能在网络局部得到控制，并且超级节点的存在也能在一定程度上提 高整个网络的负载平衡。 总的来说，基于超级节点的混合式p 2 p 网络结构比以往有较大程度的改 进。 然而，由于超级节点本身的脆弱性也可能导致其簇内的节点处于孤立状 态，因此这种局部索引的方法仍然存在一定的局限性。这导致了结构化的p 2 p 网络模型的出现。 在对等网络的实现上，混合式结构是最新发展的体系结构，该结构的目 标是实现以上两种结构的优点。通过引入超级对等体( u l t r a - p e e r ) ，混合结 构既有集中协调式结构的特点，又有纯粹分布式的特点。超级对等体成为一 部分对等体的服务器，就像集中协调式结构一样，超级节点完成这些对等体 的查询工作。而这些超级节点通过纯粹分布式结构连接起来。所以，混合式 的结构在控制层面引入了两层普通对等体通过客户机朋艮务器模式连接到超 级对等体和这些超级节点通过纯粹分布式结构连接到一起。 4 、结构化网络模型 所谓结构化与非结构化模型的根本区别在于每个节点所维护的邻居是否 能够按照某种全局方式组织起来以利于快速查找。结构化p 2 p 模式是一种采 用纯分布式的消息传递机制和根据关键字进行查找的定位服务，目前的主流 方法是采用分布式哈希表( d h t ) 技术，这也是目前扩展性最好的p 2 p 路由方 式之一。由于d h t 各节点并不需要维护整个网络的信息，只在节点中存储其 临近的后继节点信息，因此较少的路由信息就可以有效地实现到达目标节点， 同时又取消了泛洪算法。该模型有效地减少了节点信息的发送数量，从而增 强了p 2 p 网络的扩展性。同时，出于冗余度以及延时的考虑，大部分d h t 总是在节点的虚拟标识与关键字最接近的节点上复制备份冗余信息，这样也 避免了单一节点失效的问题。 目前基于d h t 的代表性的研究项目主要包括加州大学伯克利分校的 c a n 项目和t a p e s t r y 项目，麻省理工学院的c h o r d 项目、i r i s 项目，以及微 软研究院的p a s t r y 项目等。这些系统一般都假定节点具有相同的能力，这对 于规模较小的系统较为有效。但这种假设并不适合大规模的i n t e m e t 部署。 同时基于d h t 的拓扑维护和修复算法也比g n u t e l l a 模型和k a z a a 模型等无结 l o 哈尔滨工程大学硕士学位论文 构的系统要复杂得多，甚至在c h o r d 项目中产生了“绕路”的问题。事实上， 目前大量实际应用还大都是基于无结构的拓扑和泛洪广播机制，现在大多采 用d h t 方式的p 2 p 系统缺乏在i n t e r n e t 中大规模真实部署的实例，成功应用 还比较少见【l0 1 。 2 1 2 原理及发展趋势 全分布式结构化拓扑的p 2 p 网络主要是采用分布式散列表( d i s t r i b u t e d h a s ht a b l e ，简写成d h t 1 1 】) 技术来组织网络中的节点。d h t 是一个由广域 范围大量节点共同维护的巨大散列表。散列表被分割成不连续的块，每个节 点被分配给一个属于自己的散列块，并成为这个散列块的管理者。通过加密 散列函数，一个对象的名字或关键词被映射为1 2 8 位或1 6 0 位的散列值。它 的核心就是如何将哈希表均匀分布到p 2 p 网络中的所有机器上去，以及查询 时如何能迅速找到负责维护某段哈希表的那台机器，以便查询到所要找的信 息。分布式散列表起源于s d d s ( s c a l a b l ed i s t r i b u t ed a t as t m c t u r e s ) 研究， g r i b b l e 等实现了一个高度可扩展，容错的s d d s 集群。d h t 类结构能够自 适应节点的动态加入退出，有着良好的可扩展性、鲁棒性、节点i d 分配的 均匀性和自组织能力。由于重叠网络采用了确定性拓扑结构，d h t 可以提供 精确的发现。只要目的节点存在于网络中d h t 总能发现它，发现的准确性得 到了保证【l 引。 对于文件共享常见的做法是，每台机器分配一i d ，每个共享的文件通过 散列算法也得到一i d ，这两个i d 的位数是一样的，这样分配机制比较简单， 即令离某一文件i d 数值上最近的那台机器负责维护此文件的信息( 即此文件 在哪此机器上存在，p 2 p 软件得到此信息后即可到相应机器上去下载了) 。当 某用户要查找某文件时，也要先得到此文件的i d ( 可通过对关键字的h a s h 查找或有一个s e r v e r 来查找得到) ，然后通过每个节点中的路由表一步一步 转发此查询信息直至负责的节点，负责节点收到查询信息后，就将自己存储 的关于此文件的相关信息返回到查询节点，查询节点就可根据收到的信息开 始下载文件了。 根据每个节点所维护的路由表的不同，整个p 2 p 网络也就形成了不同的 哈尔滨工程大学硕十学位论文 拓扑结构，据此也可对结构化p 2 p 网络进行分类： 1 、基于环形结构的p 2 p 网络：c h o r & 2 、基于树形结构的p 2 p 网络：k a d e m l i a r l 3 】； 3 、基于超立方体结构的p 2 p 网络：t a p e s t r y 、p a s t r y ： 4 、基于立方体互联圈的p 2 p 网络：c y c l o i d ； 5 、基于d eb r u 讧n 图的p 2 p 网络：k o o r d e ，d 2 b ： 6 、基于蝴蝶网结构的p 2 p 网络：v i c e r o y ，u l y s s e s ； 7 、基于d 维环形结构的p 2 p 网络：c a n ； 8 、基于k a n u t z 图的p 2 p 网络：f i s s i o n e 。 当前出现了许多基于结构化p 2 p 覆盖网的应用，有的是传统应用延伸， 而有的是新型的应用，这也证明了结构化p 2 p 覆盖网可以作为新型分布式应 用支撑平台。一些应用如下： 1 、文件共享：如在e m u l e ，b t 等流行p 2 p 文件共享软件中都集成了 k a d e m l i a 网络，以更有效地进行p 2 p 文件发布与共享。 2 、应用层组播：传统的i n t e m e t 组播技术由于其可扩展性等问题难以实 用，因而出现了一些基于p 2 p 覆盖网的应用层组播技术如c a n m c ( 基于c a n 网络) ，s c r i b e ( p a s t r y ) ，b a y e u x ( t a p e s t r y ) 等。 3 、分布式文件系统：即将文件分块存储到众多p 2 p 网络节点上去，如 c f s ( c h o r d ) ，m n e m o s y n e ( c h o r d ，t a p e s t r y ) ，o c e a n s t o r e ( t a p e s t r y ) 和p a s t ( p a s t r y ) 等。 4 、分布式计算：与网格技术相结合，完成如c p u 、存储等资源的发现 与调度等。 5 、其他新型分布式应用：如反入侵网络、垃圾邮件过滤等。 对等网络系统已成为i n t e m e t 的主要应用之一，当前对等网络的主要应 用领域为：p 2 p 分布式存储系统，p 2 p 计算能力的共享，p 2 p 协同工作环境， p 2 p 应用层组播，i n t e m e t 间接访问基础结构，p 2 p 流媒体技术，p 2 p 搜索技 术等。对等网络要进一步扩大应用领域需要提高对等网络的路由效率，降低 维护开销和查找失败率。进一步工作包括： 1 、安全的p 2 p 路由算法的研究：即带有过滤和身份识别认证、授权、 数据完整性认证管理功能的p 2 p 路由算法的研究。计算机病毒对信息安全的 1 2 哈尔滨工程大学硕士学位论文 i i i 宣置i i i 宣i i i i i i i i i 葺i i i i i 威胁日益增加，特别是在p 2 p 环境下，方便的共享和快速的选路机制，为某 些网络病毒提供了更好的入侵机会。安全的p 2 p 路由算法研究已经迫在眉睫。 2 、统一的路由算法的研究：如何让各种p 2 p 网间资源进行整合、资源 互通、搜索共享。目前有很多种类的p 2 p 应用，如文件存储和共享、电子邮