（计算机应用技术专业论文）p2p系统中资源搜索定位机制的研究.pdf

，1 中 j c l a s s i f 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 nm e c h a n i s mo fr e s o u r c e s s e a r c ha n dl o c a t i o ni np 2 ps y s t e m c a n d i d a t e ：z h a n g w e i s u p e r v i s o r ：a s s o c i a t e p r o f g a ow e i 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 p p l i e dt e c h n o l o g y d a t eo fs u b m i s s i o n ：m a r c h ，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 哈尔滨工程大学 学位论文原创性声明 本人郑重声明：本论文的所有工作，是在导师的指导下，由 作者本人独立完成的。有关观点、方法、数据和文献的引用已在 文中指出，并与参考文献相对应。除文中己注明引用的内容外， 本论文不包含任何其他个人或集体已经公开发表的作品成果。对 本文的研究做出重要贡献的个人和集体，均己在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 作者( 签字) ：狨彩 日期：口，d 年3 月罗日 哈尔滨工程大学 学位论文授权使用声明 本人完全了解学校保护知识产权的有关规定，即研究生在校 攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈尔滨 工程大学有权保留并向国家有关部门或机构送交论文的复印件。 本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据 库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本 学位论文，可以公布论文的全部内容。同时本人保证毕业后结合 学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈 尔滨工程大学。涉密学位论文待解密后适用本声明。 本论文( 口在授予学位后即可盹授予学位1 2 个月后口解 密后) 由哈尔滨工程大学送交有关部门进行保存、汇编等。 作者( 签字) ：纸移 导师( 签字) ：戛抓易 日期：函k 年3 月孑日踟o 年3 月方日 f 哈尔滨工程大学硕士学位论文 摘要 随着p 2 p 网络在人们生活中的广泛应用，p 2 p 网络管理技术成为了目前 p 2 p 研究中的热点问题。p 2 p 系统中资源定位机制技术则是p 2 p 管理中的关 键技术。p 2 p 网络资源定位技术涉及到节点的加入、关键字的查询、节点的 稳定及失效管理、节点的退出几个方面的具体内容。 论文对p 2 p 网络的典型算法进行分析研究。p 2 p 网络非结构化的典型算 法主要采用洪泛或漫游的方式，从而造成网络带宽消耗过大或选择邻居的随 机性。p 2 p 网络结构化的典型算法都是基于d h t 的，都采用了s h a 1 哈希 函数来获取标识符，都采用了路由表进行路由转发，从而较非结构化算法具 有更稳定的网络结构和更高的查询效率。为了改善结构化p 2 p 典型算法c h o r d 算法的查询效率，本文提出了b p t c h o r d 模型，该模型的基本思想是先根 据设定的阈值，计算各节点到基点的时延，划定相应的分组域记为o c h o r d 。 在分组域内使用传统的c h o r d 算法，为节点构建路由表。然后在设定阈值的 情况下，每阈值组第一个加入的节点自动成为超级节点。再根据所有超级节 点构建s - c h o r d ，超级节点构建双向索引表。在o c h o r d 中查找资源失败的 情况下，通过超级节点相关标志位返回查找失败的信息，由超级节点通过双 向索引表决定向哪个分组域进行再次查找。从而有效解决了c h o r d 算法中存 在的c h o r d 环中逻辑上d 相邻的两个节点而在物理路径上可能并不相邻， 以及单向查询带来的查询效率低下的问题。 仿真实验表明，改进模型的算法实现了平均查询路径长度、平均查询时 延、平均延展率三个指标的改善，所以有效提高了资源定位的效率。同时可 以为进一步的理论研究提供参考。 关键词：p 2 p 网络；c h o r d ；资源定位；超级节点 a b s 仃a c t a st h ep 2 pn e t w o r k se x t e n s i v ea p p l i c a t i o ni np e o p l e sl i v e s ，p 2 pn e t w o r k m a n a g e m e n tt e c h n o l o g yb e c o m et h ec u r r e n th o ti s s u e si nt h ep 2 pr e s e a r c h t h e m e c b a n i s mo fr e s o u r c e l o c a t i o nt e c h n o l o g yi np 2 ps y s t e mi s t h ec r i t i c a l t e c h n o l o g i e si np 2 pa p p l i c a t i o n s t h em e c h a n i s m o fr e s o u r c el o c a t i o nt e c h n o l o g y i np 2 ps y s t e mr e l a t e dt os e v e r a la s p e c t so fi m p l e m e n t a t i o ns u c ha st h en o d et o j o i n ，k e y w o r dq u e r y , t h en o d e s s t a b i l i t ya n df a i l u r em a n a g e m e n t ，a n dt h e w i t h d r a w a lo ft h en o d e t h et y p i c a la l g o r i t h m so ft h ep 2 pn e t w o r ka r ea n a l y s i s e di nt h i st h e s i s t h e t y p i c a la l g o r i t h m so fu n s t r u c t u r e dp 2 p n e t w o r k sm a i n l yu s ef l o o d i n go rr o a m i n g m o d e ，r e s u l t i n gi ne x c e s s i v ec o n s u m p t i o no fn e t w o r k b a n d w i d t ho rr a n d o m n e s s c h o o s i n gn e i g h b o r s t y p i c a ls t r u c t u r e da l g o r i t h m so f p 2 pn e t w o r ka r ed h t - b a s e d a l g o r i t h m s h a v ea d o p t e dt h es h a 一1h a s hf u n c t i o nt oo b t a i nt h ei d e n t i f i e r s ，a n d a r er o u t e du s i n gt h ef i n g e rt a b l e ，t h e r e f o r ea l em o r es t a b l en e t w o r k s t r u c t u r ea n d h i g h e rt h eq u e r ye f f i c i e n c yt h a nu n s t r u c t u r e da l g o r i t h m i n o r d e rt oi m p r o v eq u e r y e f f i c i e n c yo fc h o r da l g o r i t h mt h a ti sat y p i c a la l g o r i t h mo f t h es t r u c t u r e dp 2 p , t h i s p a p e rp r e s e n t sb p tc h o r dm o d e l ，a n dt h em o d e l sb a s i ci d e ai st of i r s t s e tt h e 也r e s h o l da c c o r d i n gt ot h ec a l c u l a t i o no fn o d e t o - p o i n tl a t e n c y , d e l i n e a t e t h e c o r r e s p o n d i n gd o m a i np a c k e ta n dn a m e d i tt h eo c h o r d w i t h i nt h e0 c h o r du s e t r a d i t i o n a la l g o r i t h m st ob u i l df i n g e r t a b l ef o rt h en o d e s a n dt h e ns e tt h e t h r e s h o l dv a l u e f o rm ef i r s tn o d et oj o i no fe a c hg r o u pa u t o m a t i c a l l yb e c o m ea s u p e rn o d e a 1 lt h es u p e r - n o d e sc o n s i s ts - c h o r d ，a n de v e r ys u p e r - n o d ec o n s t r u c t a b i d i r e c t i o n a lf i n g e rt a b l e i nc a s eo ft h eo c h o r df a i lt of i n dr e s o u r c e ，t h r o u g ht h e s u p e r - n o d er e l e v a n tf l a gr e t u r n e dt h ei n f o r m a t i o no f f a i l u r et of i n dt h er e s o u r c e s ， t h e nt h es u p e r - n o d ed e c i d i e w h i c h g r o u p d o m a i nt ol o o k u pt h r o u g ht h e b i d i r e c t i o n a li r l d e xt a b l e t h u s ，e f f e c t i v e l ys o l v et h ep r o b l e mo ft h ec h o r dr i n g e x i s t st h a ti nal o g i c a li do ft h et w oa d j a c e n tn o d e sm a y n o tb ea d j a c e n ti nt h e ， 哈尔滨工程大学硕士学位论文 p h y s i c a lp a t h ，a sw e l la so n e w a yq u e r yt ob r i n gt h ep r o b l e m o fl o we f f i c i e n c y s i m u l a t i o nr e s u l t ss h o wt h a tt h em o d e la l g o r i t h mt oi m p r o v et h ea v e r a g e q u e r yp a t hl e n g t h ，t h ea v e r a g eq u e r yd e l a y , t h ea v e r a g ee x t e n s i o nr a t e o ft h r e e i n d i c a t o r so fi m p r o v e m e n t ，s oe f f e c t i v e l yi m p r o v et h ee f f i c i e n c yo fr e s o u r c e l o c a t i o n a tt l l es a m et i m ec a np r o v i d ear e f e r e n c ef o rf u r t h e rt h e o r e t i c a lr e s e a r c h p 2 pn e t w o r k s ；c h o r d ；r e s o u r c el o c a t i o n ；s u p e r - n o d e 哈尔滨工程大学硕七学位论文 目录 第1 章绪论l 1 1 研究背景、目的和意义1 1 2 国内外研究现状3 1 3p 2 p 的应用领域4 1 4 论文的研究内容5 1 5 论文组织结构6 第2 章p 2 p 资源定位技术分析8 2 1 对等网络的定义及特点”8 2 1 1 定义8 2 1 2p 2 p 的特点9 2 2p 2 p 的分类1 0 2 3 结构化与非结构化资源定位机制1 1 2 3 1 非结构化资源定位机制1 2 2 3 2 结构化资源定位机制1 3 2 3 3 结构化与非结构化资源定位机制对比1 6 2 4p 2 p 网络管理机制分析1 7 2 5 本章小结18 第3 章c h o r d 算法分析19 3 1c h o r d 算法的基本思想1 9 3 2c h o r d 算法过程分析2 0 3 2 1 一致性哈希算法”2 0 3 2 2 关键字的查找2 1 3 2 3 节点的加入和退出2 3 3 ，2 4 稳定和失效处理2 4 3 3c h o r d 算法优缺点2 5 3 4c h o r d 改进算法分析2 7 哈尔滨工程大学硕士学位论文 3 5 本章小结- 3 0 第4 章基于物理拓扑结构的b p t c h o r d 模型3 l 4 1b p t c h o r d 模型3l 4 1 1 基于基点进行分组3 2 4 1 2 超级节点双向索引表的建立”3 4 4 2b p t c h o r d 节点管理算法3 5 4 2 1 节点加入3 5 4 2 2 关键字定位3 6 4 2 3 稳定及失效处理3 7 4 2 4 节点退出3 8 4 3b p t c h o r d 模型性能分析3 8 4 4 本章小结一3 9 第5 章仿真实验与结果分析4 0 5 1 仿真实验设计4 0 5 1 1 网络仿真工具分析4 0 5 1 2p 2 p s i m 仿真工具4 1 5 1 3 仿真实验设计“4 3 5 2 仿真实验结果与分析4 3 5 3 本章小结4 7 结论4 8 参考文献4 9 攻读硕士学位期间发表的论文和取得的科研成果5 3 致谢5 4 第1 章绪论 随着p 2 p ( p e e r - t o p e e r ) 网络在人们日常生活当中的广泛应用，p 2 p 网 络的研究成为热点问题。p 2 p 网络中资源定位技术的研究广泛开展。建立稳 定的p 2 p 网络的同时，实现在p 2 p 巨大网络资源中快速找到目标资源成为了 迫切需要解决的问题。 1 1 研究背景、目的和意义 传统的因特网应用模式是基于客户机j j 艮务器( c l i e n t s e r v e r ，c s ) 的。 随着因特网的广泛普及和网络应用规模的不断扩大，软件复杂程度的与日俱 增，计算机硬件难以满足越来越庞大的计算需求，尤其是在面临巨大的用户 群的时候，单服务器系统成为了性能瓶颈。c s 模式的缺点逐渐凸显，同时， 人们在性能、容量、可靠性等方面的需求日益增加，c s 很难满足这些要求 和需求： ( 1 ) 网络的大规模扩张需要存储服务器性能不断提高； ( 2 ) 存储容量需求急剧膨胀； ( 3 ) 永久存储的要求； ( 4 ) 对存储的可靠性要求越来越高； ( 5 ) 客户系统资源有效利用的需求； ( 6 ) 平衡网络流量的需求； ( 7 ) 拒绝d o s ( d e n i a lo f s e r v i c e ) 攻击的需求。 c s 结构中，服务器承担了过多的网络负载，而网络边缘的资源却得不 到充分的利用，网络带宽的增长让p c 机之间的直接通信得以实现，用户之 间直接交换和共享资源成为了可能，这直接导致了采用新型应用模式的p 2 p 系统出现。 p 2 p 技术的核心思想是所有参与的节点在地位上是平等的，没有客户机 与服务器之分，每个节点既是客户机又是服务器，即向别人提供服务也享受 来自别人的服务【。这种模式使因特网中的资源被广泛发掘和利用，已经在 哈尔滨工程大学硕士学位论文 文件共享、科学计算与协作、数据存储、数据搜索、实时通讯等各个领域里 得到了广泛应用。第一个p 2 p 文件共享系统是1 9 9 9 年f a n n 开的n a p s t e r ( 2 ， n a p s t e r 迅速获得了广泛的认可，很短时间内就拥有了数以百万计的使用者。 随后的g n u t e l l a 3 1 、f r e en e t 4 1 、b i tt o r r e n t 、k a z a a 5 】等等，使得p 2 p 成为占 用因特网带宽最多的网络应用。 随着p 2 p 技术应用的迅速发展，学术界也展开了对p 2 p 系统的设计方法 和发展方向的深入研究。p 2 p 网络从拓扑结构上大致可以分为两类：一类是非 结构化网络，它的节点之间完全没有任何组织规则、完全随机的连接在一起， 早期的p 2 p 应用系统都是基于此结构开发的。如g n u t e l l a ，它是以洪泛 ( f l o o d i n g ) 的方式对资源进行定位，所谓洪泛是指查询消息像洪水一样传 遍网络中的每个节点，产生了大量的冗余信息，严重浪费了系统的资源，使 系统的性能非常低，严重时还可能导致网络瘫痪；因此另一类结构化的p 2 p 网络模型应运而生，在结构化p 2 p 模型中，节点之间按照某种规则，在实际 的物理网络之上组织成一个虚拟的逻辑覆盖网，所有的查询操作都是在逻辑 覆盖网中进行的，因此便产生了一系列基于d h t ( d i s t r i b u t e dh a s ht a b l e ) 的结构化p 2 p 路由算法，比较典型的有加州大学伯克利分校的c a n 6 算法和 t a p e s t r y ( 7 1 算法，麻省理工学院的c h o r d 8 埠法，以及微软研究院的p a s t r 严】。 其中，m i t 的c h o r d 算法是一种比较成功的算法。本文就是针对c h o r d 算法 中节点物理拓扑结构与逻辑覆盖网络的匹配问题提出新的改进算法，进而达 到提高查询效率的目的。 资源搜索定位是对等网络技术的关键技术，资源搜索定位方法的优劣直 接影响到p 2 p 系统查询性能和可扩展性。不管是非结构化对等网络还是结构 化对等网络，目前使用的资源定位技术都存在各自的不足。如非结构化对等 网络g n u t e l l a ，由于使用了洪泛定位机制，导致网络流量增大，容易造成网 络拥塞。结构化对等网络采用了基于分布式哈希表技术的资源定位机制，因 而具有查找可确定性、简单性和分布性等优点，其可扩展性比较非结构化对 等网络有很大改善，成为目前对等网络研究和应用的焦点。但也正是由于关 键字的唯一性，存在路由热点问题、容错性问题、异构性问题、不支持语义 检索等问题，需要进一步改进和提高。因此对等网络资源搜索定位机制的研 究具有深远意义。 2 哈尔滨工程大学硕士学位论文 1 2 国内外研究现状 p 2 p 技术的研究主要是从应用和理论两个方面展开的，应用方面国外经 历了最初的使用集中式目录定位内容的n a p s t e r 、使用查询洪泛机制的 g u n t e l l a 、到利用不均匀性的k a z a a ，逐步解决了集中式目录的单点故障、 性能瓶颈和版权问题，洪泛机制的效率低下和带宽占用过大问题；以k a z a a 为代表的第二代p 2 p 应用系统开始占据主导地位，它结合了集中目录式p 2 p 结构系统与洪泛机制的优点，选择性能较高( 带宽、存储等) 的节点作为超 节点，在各个超节点上存储了系统中其它部分节点的信息，查询消息在超节 点之间转发，超节点再将查询请求转发给适当的叶子节点，从而实现了定位 效率的提高以及带宽的合理分配。 国内也在开展对p 2 p 项目的广泛研究，比较具有代表性的项目如下：( 1 ) 北京大学的m a z e 系统北京大学网络实验室开发的一个中心控制与对等 连接相融合的p 2 p 文件共享系统；( 2 ) 清华大学的g r a n a r y 系统是自主开发 的对等计算存储服务系统以对象格式存储数据；j 3 ) 华中科技大学的a n y s e e 系统；( 4 ) 中科院的w o n g o op 2 p 技术平台；( 5 ) 上海交通大学的p 2 p 片段 存储系统。但这些项目都还处在p 2 p 技术的研究发展阶段。 p 2 p 路由算法的研究是对p 2 p 技术研究的另一个方面。p 2 p 技术的关键 在于高效的查询和定位关键字。目前p 2 p 路由算法的研究都集中在结构化的 路由算法上，国外已经设计出一些经典的算法，如：c a n 、t a p e s t r y 、c h o r d 、 p a s t r y 等优秀算法。国内的研究多集中在实现逻辑覆盖网络与物理拓扑结构 的结合，进而达到减少查询时间的方向上。如： 由y u n s h u a iy u ，y u b e nm i a o 和c e k u e ns h i e h 在2 0 0 6 年提出来h l c 算法中【l 们，使用l a n d m a r k 定位节点的位置，实现距离最近的节点成为下一跳 的路由节点。 陈贵海教授等开发了一种新的常数度数算法c y c l o i d 1 1 】，模拟立方体互 连圈的拓扑结构。该算法适合网络规模较大、动态性较高的网络，具有较高 的平均查找效率、负载平衡、健壮性等特点。 凌波等人在b e s tp e e r 平台上开发出p e e ri s ，采用基于语义的自配置机 制，可以使p e e r 能够根据信息偏好、行为和查询统计数据综合地确定和调整 哈尔滨工程大学硕士学位论文 自己的重要节点，从而以最小的代价检索到所需数据1 1 2 】。 周晋等利用k e yc l u s t e r i n g 算法将距离相近的键聚集到预先分配的中心结 点上，并根据s m a l lw o r l d 原理在结点之间随机添加快捷连接【1 3 】。 文献 1 4 中给出了一种无结构p 2 p 环境下基于信息的资源发现策 略一一p e e rr a n k ，它依据结点命中查询的历史信息动态地赋予结点相应权 值，并基于权值进行查询消息路由，有效地引导查询接近目标资源。 文献 1 5 中根据有效转发查询的次数赋予结点相应权值作为转发查询消 息的依据。 文献 1 6 1 中以信任思想为基础，设计了一个对文档安全性敏感的查询协 议以及一套旨在提高文档真实性的副本管理算法集，从而建立了一个基于信 任的p 2 p 文档真实性安全模型。 1 3p 2 p f t o 应用领域 p 2 p 的应用软件已经成为人们身边必备的工具。b i t t o r r e n t 、e m a i l 、迅雷、 q q 等等平台，随处可见p 2 p 的身影。除了熟知的这些应用，p 2 p 还有更多 的应用领域： ( 1 ) 分布式计算 分布式计算是指将计算任务分割成若干子任务分发给网络中的若干节点 完成，再将计算结果进行整合。典型的应用如s e t i h o m e 【l 7 | 。 ( 2 ) 文件共享 文件共享是指对等网上的各个节点直接进行资源的传送和共享，直接高 效地实现数据的共享，这是p 2 p 的典型应用之一，也是目前最广泛的应用， 典型的软件如n a p s t e r 、g n u t e l l a 和b i tt o r r e n t 等。 ( 3 ) 分布式存储 p 2 p 的分布式存储是指采用p 2 p 结构，利用因特网上的大量的节点相互 协作，在各个节点上分布式的存储数据，这使得分布式存储系统的扩展性和 自组织性与传统存储方式相比大大增强，分布式存储使得数据存储能适应因 特网的动态环境，并能支持海量用户的海量存储需求，典型的p 2 p 分布式存 储系统包括o c e a ns t o r e 18 1 、c f s 1 9 】和p a s t 2 0 】等。 4 算技术作为视频点播中热门节目的服务策略，可在请求的节点间形成动态的 应用层组播树。大多数节点可从应用层组播树上的父节点获得视频数据而无 需访问视频服务器，从而减轻服务器的负载。典型的应用层组播包括 b a y e u x 2 1 1 、s c r i b e 2 2 】和z i g z a g t 2 3 】等。 ( 5 ) 即时通信 即时通信是目前因特网上非常流行的p 2 p 应用，通过一个或者多个中心 服务器对用户的身份进行认证，而节点之间的数据通信则是以p 2 p 方式进行。 典型即时通讯系统包括i c q 、o i c q 、a i m 、m s n 、s k y p e 和j a b b e r 等。 ( 6 ) 数据管理 数据管理是p 2 p 技术的一种重要应用，p 2 p 数据管理系统将传统的数据 库及w e b 数据库技术与p 2 p 系统相结合，p 2 p 系统的每个节点上维护数据 库中的部分数据记录，数据查询时需要将关系查询请求进行分解，转发到p 2 p 系统中相关的多个节点上，再将查询结果进行整合。典型系统包括l r m e 2 4 1 、 p i e r 2 5 】和p i a z z a 2 6 】等。 ( 7 ) 其他应用领域 除上述的六个应用领域外，p 2 p 计算还在协同工作系统如g r o o v e e 2 7 1 和 m a g i 2 8 1 ，大规模联机游戏如s i mm u d 项目【2 9 】、名字服纠3 0 1 、事件通知框架、 p 2 p 电子邮件、协作式w e b 缓存和分布式搜索引擎等方面有广泛的应用。 1 4 论文的研究内容 p 2 p 网络应用是目前开发的热点，与传统的分布式系统相比，p 2 p 技术 具有无可比拟的优势，目前在各个领域都可以见到p 2 p 应用的范例。按照耦 合度分类，p 2 p 可分为结构化和非结构化两大类，结构化p 2 p 系统比较非结 构化p 2 p 系统而言，在资源定位效率和可扩展性方面有所改善和提高。目前 已存在的优秀结构化p 2 p 系统中，c h o r d 是比较具有代表性的，本文的工作 主要是围绕c h o r d 算法进行的。在对c h o r d 算法深入分析的基础上提出了改 哈尔滨工程大学硕士学位论文 迸模型，具体工作从以下几个方面进行： ( 1 ) 分析p 2 p 资源定位技术，结构化和非结构化p 2 p 网络采用了两种 不同的资源定位技术，分别是基于分布式哈希表技术和洪泛定位机制，结构 化p 2 p 系统改善了非结构化p 2 p 系统的搜索效率低、扩展性差的问题。c h o r d 就是一种典型的结构化p 2 p 系统，但c h o r d 算法存在逻辑路径和物理路径不 匹配，单向查找定位效率低的问题。 ( 2 ) 对于c h o r d 算法中逻辑路径和物理路径不匹配的问题，可以尽可能 让物理位置临近的节点在逻辑上相邻近，因此使用了基点定位方法实现物理 位置邻近的节点在同一分组域内，从而逻辑上邻近。 ( 3 ) 对于c h o r d 算法沿顺时针单向查找所造成的定位效率不高的问题， 通过在分组域中设定超级节点并为超级节点建立双向索引表，来实现从一个 分组域到另外一个合适分组域的快速资源定位，进而最终达到减少查找时间， 提高查询效率。 ( 4 ) 从节点加入、关键字查询、节点的稳定和失效、节点退出四个方面 实现改进算法，并搭建实验仿真环境，验证改进算法在平均查询路径长度、 、 平均查询时延、平均延展率三个指标的改善。 1 5 论文组织结构 本论文主要分为5 个部分，具体安排如下： 第1 章介绍p 2 p 资源定位技术的研究背景，分析了p 2 p 资源定位技术的 国内外研究现状和p 2 p 应用领域。 第2 章详细分析了p 2 p 资源定位技术，有针对性的分析了非结构化网络 和结构化网络两大类资源定位技术。结构化p 2 p 系统改善了非结构化p 2 p 系 统的搜索效率低、扩展性差的问题。 第3 章对结构化p 2 p 典型算法c h o r d 算法进行分析和研究，c h o r d 算法 存在逻辑路径和物理路径不匹配，单向定位效率低的问题。目前主要的四类 改进算法在资源消耗、带宽占用方面仍然存在着改进的空间。 第4 章为了解决c h o r d 算法中存在的逻辑路径和物理路径不匹配，单向 定位效率低的问题提出改进算法b p t c h o r d 模型，该算法采用基点定位、双 6 进算法的有效性。 7 哈尔滨_ t 程大学硕七学位论文 第2 章p 2 p 资源定位技术分析 随着p 2 p 网络应用的普及，虽然对等点既是资源提供者又是资源请求者 使得网络资源的分配相对均衡了，但是，随着网络信息量指数级的增长，如 何在庞大的对等网络资源中快速找到需要的目标资源，成为了研究热点，p 2 p 网络资源定位技术引起了人们最广泛的关注。 2 1 对等网络的定义及特点 对等网络有很多种定义方式，但都有一个共同的特征就是多等网络中的 节点既是资源的提供者也是资源的请求者。 2 1 1 定义 从产生到现在，许多研究人员都试图给出p 2 p 系统的定义，但是无论在 学术界还是在工业界都没有一个统一的定义，下面几个定义是比较常见的。 英特尔公司p 2 p 工作组将p 2 p 系统定义为通过在系统之间直接进行交换 来共享计算机资源和服务的系统。 s c h o l l m e i e r 对p 2 p 系统的定义如下【3 1 ：如果一个系统的参与共享了自己 的硬件资源，这些共享的资源是系统提供服务必需的，且可以被其他参与者 不用通过中介而直接访问；系统的参与者既是资源的提供者也是资源的请求 者，则此系统可以认为是p 2 p 系统。 g r a h a m 通过描述p 2 p 节点所需的三个必备条件来定义p 2 p 系统【3 引。三 个必备条件如下：( 1 ) 具备服务器的能力；( 2 ) 拥有独立于d n s 的寻址系统； ( 3 ) 能够处理可变的连接。 a b e r e r 通过描述p 2 p 系统的特征来定义p 2 p 系统p 引。这些特征如下：( 1 ) 没有集中的协调中心；( 2 ) 没有集中的数据库；( 3 ) p 2 p 节点没有整个系统 的全局视图；( 4 ) 全局的行为依靠局部的相互作用；( 5 ) 所有存在的数据和 服务都是可访问的；( 6 ) p 2 p 节点是自治的；( 7 ) p 2 p 节点及其相互之间的 连接都是不可靠的。 8 散的边缘资源意味着要在连接不稳定和i p 地址不可预见的环境下工作，所以 p 2 p 节点必须能够独立于d n s 系统且拥有独立于集中服务器的完全的自治。 惠普实验室的m i l o j i c i c 将p 2 p 系统定义为一类采取分布式方式利用分布式资 源完成关键功能的系统【3 5 1 。 由于p 2 p 系统采用了新兴网络应用模式，而且正在不断地发展变化，所 以目前学术界仍然没有给出一个权威的定义，但这并没有妨碍p 2 p 系统应用 的迅速增长。 2 1 2p 2 p 的特点 p 2 p 技术的特点体现在以下几个方面【3 6 ： 非中心化：网络中的资源和服务分散在所有节点上，信息的传输和服务 的实现都直接在节点之间进行，可以无需中间环节和服务器的介入，避免了 可能的瓶颈。p 2 p 的非中心化基本特点，带来了其在可扩展性、健壮性等方 面的优势。 可扩展性：在p 2 p 网络中，随着用户的加入，不仅服务的要求增加了， 系统整体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的需 要。整个体系是全分布的，不存在瓶颈，理论上其可扩展性几乎可以认为是 无限的。 健壮性：p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散在 各个节点之间进行的，部分节点或网络遭到破坏对其他部分的影响很小。p 2 p 网络一般在部分节点失效时能够自动调整整体拓扑，保持其他节点的连通性。 p 2 p 网络通常都是以自组织的方式建立起来的，并允许节点自由地加入和离 开。p 2 p 网络还能够根据网络带宽、节点数、负载等变化不断地做自适应的 调整。 高性价比：性能优势是p 2 p 被广泛关注的一个重要原因。随着硬件技术 的发展，个人计算机的计算能力和存储能力以及网络带宽等性能依照摩尔定 理高速增长。采用p 2 p 架构可以有效地利用因特网中散布的大量普通节点， 将计算任务或存储资料分布到所有节点上。利用其中闲置的计算能力或存储 9 哈尔滨1 = = 程大学硕十学位论文 空间，达到高性能计算和海量存储的目的。通过利用网络中的大量空闲资源， 可以用更低的成本提供更高的计算和存储能力。 保护隐私：在p 2 p 网络中，由于信息的传输分散在各节点之间进行而无 需经过某个集中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。此 外，目前解决因特网隐私问题主要采用中继转发的技术方法，从而将通信的 参与者隐藏在众多的网络实体之中。在传统的一些匿名通信系统中，实现这 一机制依赖于某些中继服务器节点。而在p 2 p 中，所有参与者都可以提供中 继转发的功能，因而大大提高了匿名通讯的灵活性和可靠性，能够为用户提 供更好的隐私保护。 负载均衡：p 2 p 网络环境下由于每个节点既是服务器又是客户机，减少 了对传统c s 结构服务器计算能力、存储能力的要求，同时因为资源分布在 多个节点，更好的实现了整个网络的负载均衡。 2 2p 2 p f l c j 分类 p 2 p 目前主要存在两种分类方法：按照分散度和耦合度分类。p 2 p 分类 示意图如图2 1 所示。 图2 1p 2 p 分类示意图 p 2 p 系统中的分散度是指其拓扑结构对中央服务器的依赖程度，按照分 散度，p 2 p 系统可分为如下三类： ( 1 ) 集中式拓扑 集中式拓扑结构中，存在一个或者少数几个目录或者索引服务器用户协 调和控制各个节点之间的交互，其信息交换仍然以p 2 p 模式进行，其典型系 统如n a p s t e r ，b i t t o r r e n t 等。 l o 哈尔滨工程大学硕士学位论文 ( 2 ) 部分分布式拓扑 部分分布式拓扑系统中存在少数“超级节点 充当目录服务器的角色， 在动态p 2 p 系统中，这些“超级节点”是随机选择的，一般不会引起节点失 效。典型的系统如f a s t t r a c k 和b r o c a d e 等。 ( 3 ) 全分布式拓扑 全分布式拓扑系统中，不存在任何服务器，各个节点处于完全平等的地 位，节点之间直接交换信息；节点在系统中同时充当服务器和客户端的角色， 全分布式拓扑又称纯p 2 p ( p u r ep 2 p ) 模式。典型的全分布式p 2 p 系统如 g n u t e l l a 、f r e e n e t 和c h o r d 等。 耦合度是用来衡量p 2 p 系统的拓扑构造过程中受某种机制严格控制还是 非确定性的。根据耦合度，p 2 p 系统可分为结构化p 2 p 系统和非结构化p 2 p 系统两大类： ( 1 ) 非结构化拓扑 非结构化拓扑的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 ，f a s t t r a c k ，f r e e n e t 等等。 ( 2 ) 结构化拓扑 结构化拓扑中，节点之间逻辑拓扑和节点资源的放置通常用确定的算法 严格控制，系统通常采用分布式哈希表技术( d h t ) 构建，由于d h t 提供 了一个良好的扩展性查询机制，故结构化拓扑能保证资源定位的准确且能保 证一定的效率。但结构化拓扑的维护较为复杂，且一般不支持复杂搜索条件 查询，且结构化拓扑的p 2 p 系统一般为全分布式，如：如c h o r d 、t a p e s t r y 、 c a n 和p a s t r y 等：也有少部分是分布式的，如b r o c a d e 。 2 3 结构化与非结构化资源定位机制 非结构化定位机制一般采用洪泛算法，结构化资源定位机制一般采用 d h t 技术。结构化资源定位机制克服了非结构化定位机制定位过程中会产生 大量冗余信息的缺点。 2 3 1 非结构化资源定位机制 ( 1 ) 传统的洪泛机制 传统的资源定位机制大都采用洪泛算法。采用洪泛算法传播消息不需要 节点保存其他节点的信息，实现非常简单，洪泛资源定位机制在p 2 p 系统应 用的初期得到广泛应用。g n u t e l l a 洪泛算法由两部分组成：叠加网络构建和 定位请求处理。 叠加网络构建过程，也就是节点加入的处理过程。当一个节点想要加入 系统时，首先找到一些己知节点，并向已知节点广播发送p i n g 消息。p i n g 消息中携带一个消息生存时间值和全局唯一标识符。当这些节点收到p i n g 消 息时，验证是否接收过相同标识符的消息。若接收过，则该节点无需进行处 理；否则，将信息的消息生存时间值减1 ，并将消息转发给该节点的所有邻 居。同时将包含各个连接节点的响应消息按照原路返回。当请求加入的节点 收到响应消息时，与相应的节点之间建立连接。当网络中所有消息的消息生 存时间值都为0 时，叠加网络构建过程完成。 定位请求处理过程，即资源的搜索定位过程。当用户需要定位某一资源 时，向其所有邻居广播请求消息，消息中包含请求资源的标识。当节点收到 请求消息时，将请求资源标识与本地共享资源索引进行匹配。如果匹配成功， 则向请求节点发送响应消息；否则，将请求消息的消息生存时间值减1 ，并 转发该消息。只要请求消息的消息生存时间值值不为o ，就继续转发消息。 洪泛算法产生的消息的数目随着消息的传播成指数倍增长，并包含大量 冗余消息。g n u t e l l a 协议采用两种方法来控制冗余消息的数量，以减少洪泛 算法占用的带宽。 1 ) 消息生存时间( t i m e t o l i v e ，t t l ) 。t t l 是指消息在网络中传播 时能够生存的时间，它包含在消息头中，在每个消息生成时被赋予一个初始 值。当消息被发送出去后，其他接收到此