（计算机应用技术专业论文）无结构p2p网络中基于文件流行度的搜索机制研究.pdf

摘要 摘要 近年来以g n u t e l l a 为代表的文件共享已经成为i n t e r n e t 上增长最迅速的应 用。p 2 p 网络具有容错性好、共享信息可扩展性好、自主性强、负载平衡、匿名 等优点，但是在无结构p 2 p 文件共享系统中，文件的流行度呈现不均衡分布， 导致搜索流行文件时获得过多结果，造成大量网络资源的浪费，而搜索稀缺文 件时失败的可能性较大。针对稀缺文件搜索成功率低和大量带宽浪费的问题， 本文提出了基于范围扩张的蚁群更新预算( e x p a n d i n gr i n g 研t ha n t b u d g e t ， e r a b ) 机制和基于探求的蚁群更新预算( d e t e c t i v ed i f f u s i o nw i t ha n t b u d g e t ， d d a b ) 机制。 针对稀缺文件搜索成功率低的问题，本文提出的e r a b 机制采用预算思想 代替传统的t t l ，利用信息素更新策略对查询进行指导，范围扩张策略根据查 询文件流行度进行查询规模调整，解决了预算的适当选择问题，提高对稀缺文 件的搜索成功率和满意度。实验数据表明，对于同样的测试集，与g n u t e l l a 洪泛 相比，带宽消耗降低7 1 的同时，文件搜索的成功率可以达到1 0 0 ，满意度最 大可以提高4 5 。 针对传统搜索机制忽略文件流行度从而导致大量带宽浪费的问题，d d a b 机制通过探求查询结果选择预算，更加灵活地结合文件流行度，定位搜索深度， 调控搜索范围。实验数据表明，与g n u t e l l a 洪泛相比，在保证成功率基本相同的 情况下，带宽可以节省8 9 。 关键词：无结构p 2 p ，搜索机制，预算，稀缺文件 a b s t r a c t ab s t r a c t f i l e s h a r i n gs y s t e m , s u c ha sg n u t e l l a ，i st h em o s tp r e v a l e n tp 2 pa p p l i c a t i o n ， b e c a u s eo fi t sa d v a n t a g e si n c l u d i n gr o b u s t n e s si nf a i l u r e s ，e x t e n s i v er e s o u r c e 。s h a r i n g ， s e l f - o r g a n i z a t i o n ，l o a d b a l a n c i n g ，a n o n y m i t y , e t c h o w e v e r , i n u n s t r u c t u r e dp 2 p f i l e s h a r i n gs y s t e m st h ep o p u l a r i t i e s o fv a r i o u so b j e c t sa r ev e r ys k e w e d t h e i m b a l a n c eo fo b j e c tp o p u l a r i t yd i s t r i b u t i o nl e a d st ot w op r o b l e m s f i r s t , q u e r i e sf o r p o p u l a ro b j e c t sm a yr e t u r nf a rm o r et h a nt h e yn e e d ，c a u s i n gal a r g ev o l u m e o f u n n e c e s s a r yt r a f f i c s e c o n d ，q u e r i e sf o rr a r eo b j e c t su s u a l l yd on o tr e c e i v et h ed e s i r e d n u m b e ro fr e s u l t so re v e nf a i l t oi m p r o v es e a r c hp e r f o r m a n c ei nu n s t r u c t u r e dp 2 p f i l e s h a r i n gs y s t e m s ，t h i st h e s i sp r o p o s e st w on o v e ls e a r c hm e c h a n i s mb a s e d 0 1 1 g n u t e l l ap r o t o c o l ，w h i c ha r en a m e de x p a n d i n gr i n gw i t ha n t b u d g e t ( e r a b ) a n d d e t e c t i v ed i f f u s i o nw i t ha n t b u d g e t ( d d a b ) a i m i n ga ti m p r o v i n gt h es u c c e s sr a t ef o rr a r eo b j e c t s ，e r a ba d o p t sb u d g e ti n s t e a d o ft t lt ot r a n s m i tq u e r ym e s s a g e s ，a n da c h i e v e sag u i d e ds e a r c hb yc r e a t i n ga p h e r o m o n ei n d e xt a b l ei ne a c hp e e ra n du p d a t i n gt h e i n f o r m a t i o no ft h et a b l e s a c c o r d i n gt ot h eo b j e c tp o p u l a r i t y , e r a ba d j u s t st h es e a r c hs c a l e ，s o l v e st h ep r o b l e m o fb u d g e ts e l e c t i o na n dg r e a t l yi m p r o v e st h es u c c e s sr a t ea n dt h es a t i s f i e dr a t ef o r r a r e o b je c t s t h es i m u l a t i o nr e s u l t ss h o wt h a tc o m p a r e dw i t hs t a n d a r df l o o d i n g ，i ne r a b t h es u c c e s sr a t ec a l lb e1 0 0 a n dt h es a t i s f i e dr a t ei si n c r e a s e db y u pt o4 5 w h i l e t h ea v e r a g eq u e r yt r a f f i cc o s ti sr e d u c e db yu pt o71 t or e d u c eal a r g ev o l u m eo fu n n e c e s s a r yt r a f f i cc o s t ，d d a bi sa ni m p r o v e ds e a r c h m e c h a n i s mt h a tc o n s i d e r st h ei m b a l a n c eo fo b j e c tp o p u l a r i t yd i s t r i b u t i o n a c c o r d i n g t ot h er e s u l t so ft h ed e t e c t i v eq u e r y , d d a be a t i m a t e st h eo b j e c tp o p u l a r i t yt os e l e c t t h ev a l u eo fb u d g e ta n dc o n t r o l st h ed e p t ha n ds c o p eo fs e a r c h t h es i m u l a t i o nr e s u l t s s h o wt h a tc o m p a r e dw i t hs t a n d a r df l o o d i n g ，d d a bc a nr e d u c et h et h ea v e r a g eq u e r y t r a f f i cc o s tb yu pt o8 9 w h i l ea c h i e v i n gt h ec o m p a r a b l es u c c e s sr a t e k e yw o r d s ：u n s t r u c t u r e dp 2 p n e t w o r k s ，s e a r c hm e c h a n i s m ，b u d g e t ，r a r eo b j e c t s i i 南开大学学位论文使用授权书 根据南开大学关于研究生学位论文收藏和利用管理办法，我校的博士、硕士学位获 得者均须向南开大学提交本人的学位论文纸质本及相应电子版。 本人完全了解南开大学有关研究生学位论文收藏和利用的管理规定。南开大学拥有在 著作权法规定范围内的学位论文使用权，即：( 1 ) 学位获得者必须按规定提交学位论文( 包 括纸质印刷本及电子版) ，学校可以采用影印、缩印或其他复制手段保存研究生学位论文， 并编入南开大学博硕士学位论文全文数据库；( 2 ) 为教学和科研目的，学校可以将公开 的学位论文作为资料在图书馆等场所提供校内师生阅读，在校园网上提供论文目录检索、文 摘以及论文全文浏览、下载等免费信息服务；( 3 ) 根据教育部有关规定，南开大学向教育部 指定单位提交公开的学位论文；( 4 ) 学位论文作者授权学校向中国科技信息研究所和中国学 术期刊( 光盘) 电子出版社提交规定范围的学位论文及其电子版并收入相应学位论文数据库， 通过其相关网站对外进行信息服务。同时本人保留在其他媒体发表论文的权利。 非公开学位论文，保密期限内不向外提交和提供服务，解密后提交和服务同公开论文。 论文电子版提交至校图书馆网站：h t t p ：2 0 2 1 1 3 2 0 1 6 1 ：8 0 0 1 i n d e x h t m 。 本人承诺：本人的学位论文是在南开大学学习期间创作完成的作品，并已通过论文答辩； 提交的学位论文电子版与纸质本论文的内容一致，如因不同造成不良后果由本人自负。 本人同意遵守上述规定。本授权书签署一式两份，由研究生院和图书馆留存。 作者暨授权人签字： 2 0年 月 日 南开大学研究生学位论文作者信息 论文题目 姓名学号答辩日期年月日 论文类别博士口学历硕士口硕士专业学位口高校教师口同等学力硕士口 院系所专业 联系电话 e m a i l 通信地址( 邮编) ： 备注： 是否批准为非公开论文 注：本授权书适用我校授予的所有博士、硕士的学位论文。由作者填写( 一式两份) 签字后交校图书 馆，非公开学位论文须附南开大学研究生申请非公开学位论文审批表。 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行 研究工作所取得的成果。除文中已经注明引用的内容外，本学位论文 的研究成果不包含任何他人创作的、已公开发表或者没有公开发表的 作品的内容。对本论文所涉及的研究工作做出贡献的其他个人和集 体，均已在文中以明确方式标明。本学位论文原创性声明的法律责任 由本人承担。 学位论文作者签名： 年月日 第一章引言 第一章引言 第一节课题背景 在过去的几年中，采用p 2 p ( p e e r - t o p e e r ) 技术的应用在i n t e r n e t 上迅速传播， 用户数量急剧增长。客户月艮务器( c l i e n t s e r v e r ) 模式把数据存放在集中的服务 器上，而在p 2 p 应用中数据保存在对等节点上。现在，由于计算机和网络的性能 都出现了飞跃性的提高，随着用户对于网络应用的需求和使用方式的改变，人 们都越来越重视和关注p 2 p 技术【1 j 。 p 2 p 网络中不存在中心服务器，所有的节点既是客户机，享用其它节点提供 的服务，同时又充当服务器，为其它节点提供服务。数据在对等节点之间直接 传递。p 2 p 模式能让互联网上的闲散资源得到充分的利用，提高了网络的容错性 能，加快了信息的传播速度，同时也优化了网络的带宽利用情况。 由于p 2 p 模式具有的技术特点，文件共享服务1 2 j 成为p 2 p 最为成功的用途之 一。用户利用基于p 2 p 的网络协议，直接从含有所需文件的对等节点下载该文件， 从而摆脱了对特定服务器的依赖。应用实例包括第一代的n a p s t e r 【3 】，第二代的 g n u t e l l a 4 1 和k a z a a 5 1 等。在分布式计算中，s e t i h o m e t 6 l 和x e n o s e r v e r s 7 】等使 用积累的能力执行超级计算机的任务。此外，随着网络规模的扩大，研究项目 开始采用p 2 p 技术来组织和存储数据，例如o c e a n s t o r e 引，p a s t 9 1 和c f s 1 0 l 等提 供面向全球的数据存储服务。i c q t l l l ，m s n 1 2 和s k y p e t l 3 】等不依赖服务器的性能 和带宽，实现点对点的通信。n a r a d a 1 4 1 ，a l m i 1 5 】和s c r i b e t l 6 】等利用p 2 p 技术在 应用层实现组播功能，从而避免出现由于i p 层迟迟不能部署对组播的支持而使组 播应用难以进行的情况。另外，p 2 p 技术可以帮助企业和客户间建立一种安全的 网上协同工作方式，应用实例包括g r o o v e 1 7 】等。s q u i r r e l 1 8 】等利用对等计算的技 术优势，很好地解决传统的w e b 缓存系统不能避免的硬件开销，缓存有限以及维 护和运营成本指数级递增等问题。i n f r a s e a r c h 1 9 1 ，p a n d a n g o 2 0 l ；j f f i g o o g l e 2 1 】等p 2 p 搜索引擎与传统搜索方式相比，利用p 2 p 可以充分检索网络上的所有节点，并且 可以通过检测网站的变化，提高搜索引擎的可达范围和数据的刷新率。 以上是p 2 p 技术主要的几个发展方向。很多计算机公司、研究部门都认为 第一章引言 该技术蕴涵着巨大的商业价值和技术价值，其巨大的开发空间将成为未来i t 界 关注的焦点。 第二节论文的选题及研究意义 p 2 p 文件共享系统具有分散化、自主性强、容错性好、信息量大等优势，因 而得到了快速发展。以g n u t e l l a 、k a z a a 、b i t t o r r e n t 等为代表的一批无结构型 p 2 p 文件共享系统，已经成为当前i n t e r n e t 中最重要的应用之一。在这些文件共 享系统中，各种文件的分布具有很大的差异性。如果以整个系统中某个文件的 副本数作为判断该文件流行度的依据，就会发现文件的流行度呈现出幂律分布 【2 2 1 1 2 3 】：约5 0 的文件拥有不到2 0 个副本，而最流行的文件却拥有上千个副本。 文件分布严重影响系统性能的表现。一方面，对于流行文件的查询，系统 能够以较短的响应时间搜索到大量的结果，但结果可能远远超出需求，造成大 量网络资源的浪费，导致系统的可扩展性不高；另一方面，对于稀缺文件的查 询，系统在经过较长的响应时间后，可能仍难以搜索到足够多的结果，甚至搜 索不到结果造成查询的失败。 实际上，无论是系统可扩展性不高还是稀缺文件搜索成功率较低，都是可 以得到改善的。文章 2 4 1 提出的d q 方法和b t l o o 等在文章 2 5 1 1 2 6 1 q b 提出的 方法，分别从这两种情况着手，进行了证实。 目前，针对提高系统性能的研究方法，大致可以归为以下几类： 1 ) 文件流行度判定。利用探测、采样等策略，通过查询消息和返回结果的 数据集合，判定要查询的文件的流行度调整查询规模。文章 2 6 】介绍了根据查询 结果数、关键字频率、关键字对频率和采样结果来判定文件流行度的策略。 g a b t 2 7 】是一种基于g o s s i p 协议的文件流行度判定方法，其中每个节点通过 r a n d o m i z e dg o s s i p 方式与其它节点交互信息。 2 ) 搜索机制改进。r a n d o mw a l k s 2 引，e x p a n d i n gr i n 9 1 2 引，r o u t i n gi n d i c e s t 2 9 】 等改进g n u t e l l a 协议的机制，能够减少网络流量，提高p 2 p 系统的可扩展性，但 往往又导致节点覆盖率低、响应时间增大等不足。 3 ) 索引缓存机制。节点通过索引其它节点的信息、缓存流经的查询结果， 提高搜索性能。文章 3 0 1 提出了一种在g o s s i p 协议上的基于概率的文件索引和搜 2 第一章引言 索方案。 4 ) 拓扑结构优化。文章【3 1 】提出的t c o 将相似属性的节点聚类成d h t 结构， 从而提高查询成功率并减少查询转发的数量。但是，分类信息的维护会占用大 量网络资源。 5 ) 数据信息备份。文章 3 2 】 3 3 】提出让节点退出前将自己的文件复制至其 它节点备份，延长了文件在网络中的存活时间，但也使网络开销大大增加。 以上的这几类研究方法，基本以提高p 2 p 系统的可扩展性为主，往往不能克 服稀缺文件的查询成功率较低这一难题。因此，很有必要将它们选择性地结合。 天津市应用基础研究计划项目“无结构p 2 p 文件共享系统中稀缺文件查询机制研 究( 0 7 j c y b j c l 4 2 0 0 ) ”就是将判定、搜索、索引信息发布等机制选择性地结合， 构建一个无结构p 2 p 文件共享系统的查询体系，以改善稀缺文件的查询性能。在 整个体系中，搜索机制是核心。本文依托于这个项目，研究重点是在分析以往 搜索机制的基础上，提出一种更高效的搜索机制，在减少网络资源消耗的同时， 提升稀缺文件的查询成功率。 第三节本文研究内容 本文的研究重点就是无结构p 2 p 网络中进行文件搜索时由于文件分布不均 衡性所带来的问题。作者查阅了大量的文献资料，比较全面地学习了p 2 p 网络 的相关知识，包括p 2 p 网络的定义、p 2 p 的特点、p 2 p 的应用以及新提出的各种 p 2 p 搜索技术等。本文提出两种全新的p 2 p 搜索技术，分别是e r a b 搜索机制 和d d a b 搜索机制。作者对这两种机制进行了细致的研究、修改和仿真实验， 得出的结论是这两种机制都能大幅度的减少网络资源的消耗，提高了对目标文 件查询的成功率和满意度。 第四节论文结构 本文在第一章阐述了课题背景，论文选题的研究意义以及研究内容。第二 章阐述了p 2 p 网络的基本概念和p 2 p 文件共享系统的相关知识。第三章中阐述 了g n u t e l l a 网络的基本协议和几种改进方法。第四章讨论了应用于g n u t e l l a 网络 3 第一章引言 中的一种新的查询机制- e r a b 查询机制。第五章讨论了d d a b 查询机制。 第六章通过仿真实验验证了e r a b 机制和d d a b 机制的性能。第七章对论文进 行了总结，并提出了今后的研究方向。 4 第二章p 2 p 概要简介 第二章p 2 p 网络概述 第一节p 2 p 概念 从不同角度，存在几种对等网络的定义和诠释。对等计算工作组定义p 2 p 为“通过直接交换共享计算机资源和服务 【3 4 1 ；a l e xw e y t s e l 将之定义为“以非 客户的能力使用因特网外围设备 3 5 】；c l a ys t d r k y 则给出了下面的定义【3 6 1 ：“对 等网络是利用因特网边缘设备资源，如存储、c p u 周期、内容等的一类应用。 因为访问这些分散化的资源意味着在一个连通性不稳定和不可预测i p 地址的环 境中进行，p 2 p 节点必须能够独立于d n s 系统运行，并且具有独立于集中服务 器的大部分的或完全的自治性。 p 2 p 系统是分散化的、自组织的分布式系统。以下几个特征使它明显区别于 其他计算模式【l 】：节点对等性、资源分散性、节点自治性、节点动态性、缺乏集 中管理、系统自组织性、节点异构性、覆盖网络。 第二节p 2 p 特点 p 2 p 模式和c s 模式有着本质上的区别。在c s 模式中，当用户间要进行信 息资源的传输活动时，首先要构建一个有一定资源的服务器，然后在其它地方 创建信息并“发布”到服务器上。这些信息在服务器上等待请求。接收到请求 之后，服务器将信息传递给请求者。整个过程需要三步，即创建信息一发布信 息一查看信息。图2 1 是一个典型的c s 模式的体系结构。c s 模式具有以下特 占 3 7 1 ，、 1 ) 集中计算方式，信息和数据都保存在服务器端，每台服务器所能提供信 息数量受到自身存储空间的限制。客户端基本上只是一个高性能的i 0 设备，上 面大量的资源和服务被闲置。 2 ) 服务器及网络的带宽决定了整个网络的性能，任意时刻它所能支持的客 户端访问数量受到自身处理能力以及网络吞吐能力的限制。随着客户端的增加， 服务器的负载就越来越重，成为系统的瓶颈。一旦服务器崩溃，整个网络也随 5 第二章p 2 p 概要简介 珏 新轴曼虱 翘昌_ 图2 2p 2 p 模式的体系结构 在p 2 p 模式下，处于对等地位的节点可以直接向存储源信息的对等节点发 送请求。而接收到请求的节点可以直接将需要的信息发送给对方。整个过程只 需两步，a p e d 建信息一查看信息。图2 2 是个典型的p 2 p 模式的体系结构。p 2 p 模式具有以下特点【i 】： i ) 每个节点具有相同的地位，既可以请求服务也可以提供服务，同时扮演 第二章p 2 p 概要简介 着c s 模式中的服务器和客户端两个角色。这是和传统的c s 模式最大的差别。 2 ) p 2 p 网络的规模随着加入节点的数量的增长而增长，新节点的加入会给 系统增加新的资源。从理论上看，p 2 p 网络的可扩展性几乎是无限的，可以达到 现有的i n t e r n e t 规模。 3 ) p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散在各个节点 之间进行的，部分节点或网络遭到破坏对其它部分的影响很小。p 2 p 网络一般在 部分节点失效时能够自动调整整体拓扑，保持其它节点的连通性。p 2 p 网络通常 都是以自组织的方式建立起来的，并允许节点自由地加入和离开。 4 ) 每一个节点都可以随意的发布信息，缺乏集中管理，因此信息的获取比 较困难。 5 ) p 2 p 减少了对传统c s 结构服务器计算能力、存储能力的要求，同时因 为资源分布在多个节点，更好的实现了整个网络的负载均衡。 6 ) p 2 p 模式允许更多的用户参与信息交换，因而不易管理。 表2 1 f 3 7 】列出了p 2 p 模式和c s 模式的比较。 表2 1p 2 p 模式和c s 模式的比较 第三节p 2 p 文件共享系统 当前的p 2 p 文件共享网络中同时在线人数已达数百万，其流量已占据整个 互联网流量的4 0 以上【3 8 】。现有的p 2 p 文件共享系统可以分为集中式、分布式 非结构化型和分布式结构化型。本节将对这三种类型的p 2 p 文件共享系统进行 介绍。 7 第二章p 2 p 概要简介 2 3 1 集中式p 2 p 文件共享系统 n a p s t e r 是这种系统的实例，采用了集中式的目录服务器机制，但目录服务 器并不存储m p 3 文件，只存储用户共享的m p 3 文件索引。用户在各自的本地磁 盘上存储m p 3 文件。为下载需要的音乐文件，用户需要向目录服务器发出基于 关键字的查询并获取拥有该文件的节点的i p 地址。文件传输在请求节点和目的 节点间通过t c p 连接进行。 2 3 2 分布式无结构化p 2 p 文件共享系统 n a p s t e r 之后最具有代表性的p 2 p 文件共享系统就是g n u t e l l a 和k a z a a 。他 们之所以被称作无结构化p 2 p 就是因为文件随机地分布在节点中间，文件分布 和网络拓扑之间没有关联。 g n u t e l l a 采用了完全分布式的策略，可以把它看成是一组对等节点之间的自 组网络。在g n u t e l l a 系统里，一个对等节点a 在初始化时知道已经在g n u t e l l a 系统中的另一个对等节点b 的i p 地址，当a 和b 连接后，a 可以获得b 所知 道的其它节点的信息，这样a 就可以和它所感兴趣的节点建立直接的t c p i p 连 接。每个g n u t e l l a 节点都定义了本地的共享文件夹，用来共享文件供其它节点下 载。查询机制按照洪泛方式进行。与被查询文件名完全或部分匹配的文件都被 列入搜索结果。用户可以根据搜索结果，选择合适的文件所有者节点建立类似 h t t p 的连接并下载文件。 k a z a a 是现在全世界最流行的几款p 2 p 软件之一，采用了超级节点的概念， 吸取了n a p s t e r 和g n u t e l l a 的优点。在k a z a a 中，所有的超级节点连接成一个 覆盖网络，而普通节点( 或称为叶子节点) 则连接到一个或多个超级节点上。 超级节点通常具有较强的处理能力，足以包含、维护所有与其连接的叶子节点 的信息索引。洪泛搜索机制仅在超级节点之间转发，超级节点再将查询结果转 发给提交该查询请求的叶子节点。 根据c a 公司统计，全球k a z a a 的下载次数超过2 5 亿次，同时在线用户 已超过3 0 0 万。之所以它会如此成功，是因为它结合了n a p s t e r 和g n u t e l l a 共同 的优点。从结构上来说，它使用了g n u t e l l a 的全分布式的结构( 注：最新的g n u t e l l a v 0 6 版本也采用了超级节点的技术【3 9 】) ，这样可以使系统更好地扩展，因为它无 需中央索引服务器存储文件名，自动把性能较好的主机选为超级节点，超级节 8 第二章p 2 p 概要简介 点存储着属于它的叶子节点的文件信息。由于超级节点的索引功能，搜索效率 和系统的可扩展性都得以大大提高。 新的无结构p 2 p 文件共享系统，如b i t t o r r e n t 4 0 】和e d o n k e y t 4 1 】的特点是强调 了多点对多点的传输。系统充分利用了用户在下载时没用上的上载带宽，用户 在下载的同时也能进行上传。换句话说，同一时间的下载者越多，上传者也越 多。一旦某个用户找到拥有该文件的其它客户端，它将请求每个客户端发送这 个文件的不同片。下载结束后，这些不同的片会组装成一个完整的文件。 2 3 3 分布式结构化p 2 p 文件共享系统 c h o r d 4 2 1 、c a n 4 3 1 、p a s t r y 4 4 并f lt a p e s t r y 4 5 1 是这类系统的代表，他们是建立 在分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，简称d h t ) 之上的。在这些系统中， 文件根据系统生成的标识排列。这种标识通常是文件名经过哈希计算的结果。 系统中的每一个节点都和一个特定区段内的标识关联，并保存相关联标识对应 的文件的信息。当分布式哈希表系统对标识进行查询时，相应的节点便会返回 对应的信息。 分布式哈希表系统的核心是路由协议。系统中的分布式哈希表节点构成一 个覆盖网，每一个查询操作都是通过这个覆盖网找到目标节点。所以，分布式 哈希表系统的性能就取决于其所采用的路由协议的效率。虽然各种分布式哈希 表系统的路由协议都不相同，但它们都具有一个共同的特点，就是每一个节点 在覆盖网中拥有的邻居数目为o ( l o g n ) ，完成每一次路由所需步数都会在 o ( l o g n ) 内，其中为系统总节点数。 这些协议都是根据接收到的标识( 一般是一定长度的数字串) ，把信息路由 到相应的节点。每个节点也具有一个标识符。而且，这个标识符通常是和它对 应的文件的标识相同( 当一个节点对应一个区间内的文件标识时，节点标识符 一定位于这个区间之内，一般是区间的中点) 。同时，每一个节点都维护一张路 由表，记录其它一些节点的信息。当一个节点收到一个查询操作时，如果它发 现所查询的标识不在自己关联的区间内，那么该节点将会把该查询发送给其路 由表中它认为最靠近目标的邻居。各种算法中，对“最靠近目标”的定义不尽 相同，但是通常都是根据节点标识符和目标标识进行定义。c h o r d 采用d h t 技 术把p 2 p 节点在逻辑上组成一个环形结构；c a n 则将p 2 p 节点在逻辑上组成一 9 第二章p 2 p 概要简介 个t o r u s 结构：t a p e s t r y 和p a s t r y 的工作原理非常接近，节点在逻辑上组成一个 超立方体结构。 2 3 4 三类p 2 p 文件共享系统比较 p 2 p 文件共享系统正是按照集中式、分布式无结构化和分布式结构化的顺序 发展起来的。因此这三类系统也被称作p 2 p 文件共享系统的三代。每一代系统 都是建立在对上一代系统的改进基础上的，但每一代系统都具备自身的优势， 同时也都具备改进空间。因此无论在学术界或是工业界，这三代p 2 p 文件共享 系统都依然具备市场。 第一代系统的优点是维护简单且查询效率高。由于文件的发现依赖中心化 的目录系统，发现算法灵活高效并能够实现复杂查询。最大的问题与传统客户 栅服务器结构类似，容易造成单点故障。 第二代系统的特点是没有遵循某些预先定义的规则来构建拓扑。这些系统 的缺点是不提供性能保证、查询结果可能不完全、查询速度较慢、采用广播查 询对网络带宽消耗很大，并由此带来可扩展性差等问题。这些系统的优点是容 错性好和支持复杂查询。 第三代系统的优点是有着良好的可扩展性、节点i d 分配的均匀性和自组织 能力。由于覆盖网络采用了确定性拓扑结构，d h t 可以提供精确的发现。只要 目的节点存在于网络中，d h t 总能发现它。这类系统最大的问题是d h t 的维护 机制较为复杂，尤其是节点频繁加入退出造成的网络波动( c h u m ) 会极大增加 d h t 的维护代价。d h t 所面临的另外一个问题是d h t 仅支持精确关键词匹配 查询，很难支持内容语义等复杂查询。 表2 2 三代p 2 p 文件共享系统的对比结果 对三类p 2 p 文件共享系统在可扩展性、可靠性、可维护性、查询算法效率 以及是否支持复杂查询等方面的比较结果如表2 2 所示。该表说明第二代和第三 l o 第二章p 2 p 概要简介 代p 2 p 文件共享系统具备较好的性能。 第四节p 2 p 网络行为特征 p 2 p 网络在行为及拓扑方面有以下几个特征： 1 ) 节点的对等性、动态性和异构性。p 2 p 网络中的节点是对等的，但由于 节点频繁的加入或退出，p 2 p 网络呈现出高度的动态性。研究报告【4 9 指出，在 n a p s t e r 和g n u t e l l a 网络中，节点的平均在线时间是6 0 分钟。也就是说，对于一 个有1 0 0 万个节点的大型p 2 p 网络，每分钟会有超过1 6 0 0 0 个节点加入或者退 出网络。p 2 p 网络中节点的硬件能力和入网方式的不同，造成了参与p 2 p 系统的 节点在存储能力、计算能力和带宽能力上都有着很大差异【4 9 1 。如何利用这种异 构性把所有节点的可用资源都充分利用起来以提高网络性能是p 2 p 系统必须仔 细研究的问题。 2 ) 资源分布的不合理性。很多理性用户总是试图多使用别人的资源，少贡 献自己的资源。研究报告【4 9 指出，在g n u t e l l a 中有2 5 的节点从不共享文件给 别人，只从别人那里下载文件，这种节点被成为f r e e r i d e r 。另外有7 的节点贡 献了超过5 0 的文件。使用激励机制阻止f r e e r i d e r 的出现是p 2 p 研究的重点之 一o 3 ) 拓扑结构的不匹配性。研究报告【4 6 】指出，在g n u t e l l a 网络中，尽管有超 过4 0 的节点位于最大的1 0 个自治系统中，但只有2 5 的应用层连接所相连 的两个相邻节点是位于同一个自治系统内的。因此，g n u t e l l a 网络产生的消息大 都要跨越自治系统的边界，这会产生较多的网络流量。 4 ) 节点度数的幂律分布和小世界特性。研究报告 4 6 】指出，p 2 p 网络和 i n t e m e t 骨干网类似，其节点度数的分布呈现幂律分布( 也称为z i p f 分布) ，即 度数为k 的节点的分布概率满足公式： p ( 尼) k 吖( 2 1 ) 其中，f 随着网络的不同而不同，i n t e m e t 骨干网的f 2 2 ，g n u t e l l a 网络的r 2 3 。 节点度数幂律分布的含义可以解释为网络中少数节点有较高的度数，绝大多数 节点的度数很低。度数较高的节点与其它节点的联系比较多，通过它找到待查 信息的概率较高。p 2 p 网络同时还具有小世界特性，即网络拓扑的聚集度高，平 第二章p 2 p 概要简介 均路径短。在符合小世界特性的网络模型中，往往根据节点的聚集度将节点划 分为若干个簇，在每个簇中有一个度数最高的节点为中心节点。由于网络中存 在着这些高度数节点，导致网络拓扑出现平均路径短的现象。报告【4 6 】指出在由 大约5 万个节点组成的g n u t a l l e 网络中，9 5 的节点之间的距离不超过7 步。 5 ) 查询关键字的流行度和文件的流行度都呈现幂分布【2 2 1 1 2 3 1 。查询关键字的 流行度反映了包含某个关键字的查询出现的频率高低，而文件的流行度则反映 了某个文件的副本数。由公式( 2 1 ) 可知在用户递交查询请求时，少数流行的关键 字频繁出现，而大多数关键字出现的次数很少。同样可知，少数流行文件在p 2 p 网络中存在着大量的副本，但大多数文件都是稀缺文件，只存在很少的副本。 1 2 第三章改进的g n u t e l l a 文件搜索机制 第三章改进的g n u t e l l a 文件搜索机制 g n u t e l l a 是无结构p 2 p 网络最具代表性的应用。而g n u t e l l a 洪泛搜索机制一 直存在着可扩展性和搜索的完整性之间的矛盾，其对稀缺文件的查询成功率较 低，严重影响了系统的查询性能。解决这些问题，对p 2 p 网络的进一步发展至 关重要。本章将主要介绍g n u t e l l a 洪泛搜索机制，并对学术界提出的几种改进机 制进行了归纳和总结。 第一节g n u t e l l a 协议简介 3 1 1g n u t e l l a 系统特性 研究报告 4 6 】 4 7 4 8 】表明，g n u t e l l a 系统除了具有小世界特性、节点度数和 文件流行度的幂律分布特性外，还具有拓扑的弹性。随机删除网络中8 5 的节 点，剩余节点中的9 0 仍保持连通；优先删除具有高连通度的5 0 的节点，剩 余节点中仍有7 5 保持连通。这证明在g n u t e l l a 网络中存在着一部分节点，对 于网络连通程度起着比其它节点更为重要的作用。 在g n u t e l l a 网络中，尽管有超过4 0 的节点位于最大的1 0 个自治系统内， 但只有2 5 的应用层连接所相连的两个相邻节点是位于同一个自治系统内 的。因此，g n u t e l l a 网络产生的消息大都要跨越自治系统的边界，这会产生较多 的网络流量。 研究报告 4 9 】指出，在g n u t e l l a 网络中，节点的平均在线时间是6 0 分钟。 也就是说，对于一个有1 0 0 万个节点的大型p 2 p 网络，每分钟会有超过1 6 0 0 0 个节点加入或者退出网络。g n u t e l l a 网络呈现出很高的动态性。 此外，文件在节点问的分布也非常不平衡。某些节点提供了大量的文件， 而大部分节点只提供了极少量的文件。s e n 等人对g n u t e l l a 等p 2 p 应用进行了系 统的测量与分析，他们的研究结果1 5 0 】表明：p 2 p 流量在不同节点之间的分布极不 均匀，1 0 的节点提供了9 9 的流量。 g n u t e l l a 系统在拓扑结构、节点动态性、资源分布和查询分布等方面的特性 1 3 第三章改进的g n u t e l l a 文件搜索机制 对于文件搜索机制的设计具有重要的参考作用。 3 1 2g n u t e l l a 协议定义 g n u t e l l a 协议是工作在t c p i p 协议之上的应用层协议。在最新版本的g n u t e l l a v 0 6 版本1 3 9 1 d l 口定义了六种在对等节点之间通信的消息类型。这些消息类型如表 3 1 所示。 表3 1g n u t e l l a 协议的消息类型 消息类型说明 p i n g p o n g q u e r y 用于在网络中主动发现其它节点。一个收至1 p i n g 消息的节点 会向发送方响应一个或多个p o n g 消息。 用于对p i n g 响应的消息。它包括某个节点的i p 地址、端口号 和能提供给g n u t e l l a 网络的共享文件数量。 用于查询。一个收至l j q u e r y 消息的节点如果含有与查询内容 相匹配的本地共享文件，则会响应一个q u e r y h i t 给发起q u e r y 查询的源节点( 即查询发起节点) 。 用于响应收到的q u e r y 消息。它包括l 兀配q u e r y 查询关键字的 q u e r y h i t节点的i p 地址、端口号、传输速度以及结果集和节点标识等 信息。 p u s h b y e 用于实现一种机制，允许一台处于防火墙内部的对等节点向 网络提供基于文件的数据。 为可选消息。用于通知远程主机当前连接即将关闭，并附上 连接关闭的原因。 g n u t e l l a 通过以上这六种消息实现了节点建立连接的过程、文件的搜索过程 和传输过程。消息类型的标识是通过在每个消息前面附加前导头来实现的。 3 。1 3g n u t e l l a 消息格式 本小节将介绍前导头以及六种消息的格式： 1 ) 前导头( d e s c r i p t o rh e a d e r ) 1 4 第三章改进的g n u t e l l a 文件搜索机制 1 6 bi bl bi b4 b 前导头匝堕卫巫丑三 三匝 图3 1 前导头的格式 如图3 1 所示，前导头由五部分组成。标志符i d 字段是一个1 6 字节的字符串， 用来在网络中唯一确定一次消息；消息类型字段为1 个字节，标识着这条消息的 类型，其中0 x 0 0 = p i n g ，0 x 01 = p o n g ，0 x 0 2 = b y e ，0 x 4 0 = p u s h ，0 x 8 0 = q u e r y ， 0 x 8 l = q u e r y h i t ；t t l ( t i m e t ol i v e ) 字段为1 个字节，标识这条消息在被从网络 中移出之前，能被节点转发的跳步数，当t t l 值为o 时该消息会从网络中删除； h o p s 字段为1 个字节，标识这条消息已经被节点转发的跳步数，每经过一个节点， 1 v r l 值减1 ，h o p s 值加1 ，满足等式t t l ( 0 ) = t t l ( ) + h o p s ( 0 ，其中f 0 ；负载长度 字段是发现消息体的开始的唯一、可靠的方法，g n u t e l l a 协议不提供任何别的消 息同步化方法，因此节点在收到一条消息后应该严格确认它的负载长度。 2 ) p i n g 消息 p i n g 消息体的负载为0 。节点通常主动地用p i n g 消息在网络中探测其它节点。 当某节点收至l j p i n g 消息后，会决定是否响应一个p o n g 消息。 3 ) p o n g i f i 息 2 b4 b4 b6 b p o n g 端口号i p 地址 i 共享文件数i 共享文件量l 图3 2p o n g 消息体的格式 在g n u t e l l a ，可以同时回应多个p o n g 消息给一个p i n g 消息。p o n g 消息体的 格式如图3 2 所示，其反馈的信息包括节点能够进行对等连接的端口号、i p 地址、 共享的文件个数以及共享的所有文件所占据的存储量( 以k b 计算) 。 4 ) q u e r y 消息 2 b 可变 q u e r y l 最低网速i 搜索条件l 图3 3q u e r y 消息体的格式 q u e r y 消息体的格式如图3 3 所示，包括两部分，即最低网速和搜索条件。最 1 5 第三章改进的g n u t e l l a 文件搜索机制 低网速的单位为k b s ，如果一个节点收到一条q u e r y n 息，其最低网速为nk b s ， 那么它能够应答一个q u e r y h i t 消息先决条件是通信速度不低于刀k b s 。搜索条件 是指搜索的关键字字符串，