（计算机应用技术专业论文）p2p覆盖网关键技术研究.pdf

摘要 p 2 p 的关键技术之一是在物理网络之上构建一层覆盖网络，根据覆 盖网的拓扑结构，分为结构化( s t r u c t u r e d ) 和非结构化( u n s t r u c t u r e d ) 。结 构化系统对象定位需要知道确切的名字或关键字，所以搜索算法无法 真正适应节点的动态加入退出，缺乏适应性和容错性。非结构化系统 可很好地适应现实网络的异构环境，然而信息洪泛造成的大数量级查 询流量限制了可扩展性和效率。超节点( s u p e m o d e ，s n ) 覆盖网结构 能有效应对上述问题，既具有自治性和对动态环境的适应性，同时具 备集中式搜索的效率。 本文详细分析和比较了不同拓扑结构p 2 p 覆盖网的特点和典型系 统，介绍了超节点结构p 2 p 覆盖网原理、优点和存在问题。针对超节 点覆盖网存在的问题，提出一种基于信息交互的超节点选择机制s s b i e ( s u p e m o d es e l e c t i o nb a s e do ni n f o r m a t i o ne x c h a n g e ) ，对p 2 p 覆盖网 拓扑特性与搜索性能通过实验进行了具体比较。本文主要工作如下： ( 1 ) 针对超节点p 2 p 覆盖网中拓扑不匹配问题，提出了一种在经典 拓扑( t o p o l o g y ) 和地理( g e o g r a p h y ) 位置相结合的基础上划分自治域 ( a u t o n o m i cs y s t e m ，a s ) 的方法，按照节点物理距离远近而形成a s ， 物理距离相近的节点划分为一个a s ，物理距离相近的a s 彼此邻接， 在各a s 内选择本a s 内的s n ，保证了物理网络与覆盖网的一致。 ( 2 ) 针对超节点选择不合理问题和搭便车( f r e e r i d i n g ) 现象，本文 充分考虑节点间延时、距离、信息交互频率和时间以及内容相似度等， 提出一种基于信息交互的超节点选择方法( s s b i e ) ，按节点分值( s c o r e ) 值选择超节点和识别f r e e r i d i n g 节点。通过模拟实验，分析实验结果表 明s s b i e 较之按节点能力选择的方法使p 2 p 系统性能明显提高，可提 高文件查询成功率，减少平均查询跳数，降低查询延时。 ( 3 ) 针对传统的解决单点失效问题的超节点冗余机制以系统消耗 为代价来获取系统的可靠性问题，提出一种三信息中心的策略来解决 了单点失效问题，通过模拟实验总结出此策略增加了系统的可靠性， 而没有引起更多的系统消耗。 ( 4 ) 通过在不同拓扑结构上实现f l o o d i n g 搜索策略，总结出搜索算 法的性能受p 2 p 覆盖网拓扑结构的影响，并进一步验证了我们提出的 三信息中心超节点结构覆盖网的较好性能。 关键词p 2 p 覆盖网，搜索机制，超节点，信息交互 a b s t r a c t b u i l d i n ga no v e r l a yb a s e do nt h ep h y s i c a ln e t w o ki so n eo ft h em o s t p o p u l a rt e c h n o l o g i e si np 2 ps y s t e m t h e r ea r et w ot y p e so fp 2 ps y s t e m s r e s p e c t i v e l yc a l l e ds t r u c t u r e da n du n s t r u c t u r e dp 2 ps y s t e m t h el o c a t i n g a l g o r i t h m si ns t r u c t u r e ds y s t e m sf a 订t oa d a p tt h ed y n a m i cio i n i n ga n d l e a v i n go fn o d e s b e c a u s et h es p e c i f i cn a m ea n dk e yw o r d sa r en e c e s s a r y f o r l o c a t i n go b j e c t a n dr e s u l ti nt h ea b s e n c eo fa d a p t a b i l i t ya n d f a u l t t o l e r a n t u n s t r u c t u r e ds y s t e m sa r es u i t a b l et ot h eh e t e r o g e n e o u s e n v i r o n m e n ti nr e a l l yn e t w o r k b u tt h em e s s a g ef l o o d i n g g e n e r a t e s l a r g e s c a l eq u e r y i n g f l o w st ol i m i tt h e s c a l a b i l i t y a n d e f f i c i e n c y s u p e r n o d e b a s e do v e r l a yc a nc o p ew i t ht h ea b o v ep r o b l e m s n o to n l yd o e s i th a v ee f j f i c i e n c yo ft h ec e n t r a l i z e ds e a r c h b u ta l s ou s et h ed i s t r i b u t e d s e a r c hm e t h o dt oa t t a i nt h ea u t o n o m i cn a t u r ea n dt h ea d a p t a b i l i t yt ot h e d y n a m i ce n v i r o n m e n t t h ep a p e ra n a l y s e si nd e t a i la n dc o m p a r e st h ec h a r a c t e r i s t i ca n d t y p i c a ls y s t e mo fd if f e r e n tt o p o l o g ys t r u c t u r ei np 2 po v e r l a yn e t w o r k t h e p r i n c i p l e ，a d v a n t a g ea n dd i s a d v a n t a g eo ft h es u o e m o d e b a s e dp 2 po v e r l a y a r es p e c i a l l yd i s c u s s e di nt h ep a p e r as u p e m o d es e l e c t i o nm e c h a n i s m b a s e do ni n f o r m a t i o ne x c h a n g e ( s s b i e ) i sp r o p o s e da i m i n ga tt h e p r o b l e m si ns u p e m o d e b a s e dp 2 po v e r l a y a n dt h ep 2 po v e r l a yt o p o l o g y c h a r a c t e r i s t i ca n dt h es e a r c hp e r f o r m a n c ea r ea n a l y s e db ys o m es i m u l a t i o n s t h em a i na c h i e v e m e n t so b t a i n e da r ep r e s e n t e db e l o w ： ( 1 ) a p a r t i t i o no f a sb a s e do nt h ec o o p e r a t i n go f t y p i c a lt o p o l o g ya n d g e o g r a p h y i s p r e s e n t e da c c o u n t i n g f o rt h e u n m a t c h i n gt o p o l o g y i n s u p e m o d e b a s e dp 2 po v e r l a y i tf o r m si n t o t h ea sb yt h ep h y s i c a l d i s t a n c e t h ec l o s e dn o d e si np h y s i c a lg r o u paa s a n dt h ec l o s e da s e si n p h y s i c a la r ea d j o i n i n ge a c ho t h e r s e l e c t i n gn o d ew i t h i ne a c ha sa st h e o w ns u p e m o d eg u a r a n t e e st h em a t c h i n gb e t w e e nt h ep h y s i c a ln e t w o r ka n d o v e l a y ( 2 ) a i m i n ga tt h eu n r e a s o n a b l es u p e m o d es e l e c t i o na n df r e e r i d i n g p r o b l e m s s u p e r n o d es e l e c t i o nb a s e do ni n f o r m a t i o ne x c h a n g e ( s s b i e ) i s p r e s e n t e d i n p a p e rc o n s i d e r i n gd e l a y , p h y s i c a ld i s t a n c e ， i n f o r m a t i o n e x c h a n g ef r e q u e n c y , i n f o r m a t i o ne x c h a n g et i m ea n dd e g r e eo fc o n t e n t s i m i l a r i t y s s b i es e l e c t st h es u p e m o d ea n di d e n t i r y e st h ef r e e r i d i n gn o d e s b ye a c hn o d e ss c o r e t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h ess b i e i m p r o v e st h et i l eq u e r y m gs u c c e s sr a t e ，d e c r e a s e st h ea v e r a g eq u e r y l n g h o p sa n dq u e r y i n gd e l a yi ns u p e r n o d e b a s e dp 2 po v e r l a y ( 3 ) at h r e ei n f o r r n a t i o nc e n t r em e c h a n i s mi sp r o p o s e dt os o l v es i n g l e n o d e f a i l t u r ei n s t e a do ft h e t h et r a d i t i n a l s u p e r n o d er e d u n d a n c yw h i c h a t t a i n sr e l i a b i l i t yb yu s i n gm o r ec o s to fs y s t e m i tr e c e i v e sm o r er e l i a b i l i t y b u tn o tb r i n g sm o r ec o s to fs y s t e m ( 4 ) t h ep a p e rc o n c l u d e st h a tt h et h ep e r f o r m a n c eo fs e a r c h i n g a l g o r i t h m i sa f f e c t e do nt h et o p o l o g ys t r u c t u r e o fp 2 po v e r l a yb y i m p l e m e n t i n gf l o o d i n g s e a r c h s t r a t e g y i nd i f f e r e n tt o p o l o g y t h e e x p e r i m e n t a lr e s u l t ss h o wt h a tt h et h r e ei n f o r m a t i o n c e n t r eo v e r l a yh a s b e t t e rp e r f o r m a n c e k e yw o r d s ：p e e r - t o p e e ro v e r l a y , s e a r c hm e c h a n i s m ，i n f o r m a t i o n e x c h a n g e ，s u p e m o d e i ! i 插图索引 图2 1n a p s t e r 系统图，6 图2 2g n u t e l l a 系统。7 图2 3f a s t t r a c k 系统9 图2 4c h o r d 方法13 图2 5t a p e s t r y 方法结点0 6 4 2 的邻居表1 4 图2 - 6 二维坐标空间中的c a n 结点1 4 图3 1 超节点覆盖网结构17 图3 2k a z a a 的双层覆盖网19 图3 3 拓扑不匹配示意图2 0 图3 _ 4 超节点结构p 2 p 覆盖网拓扑不匹配示意图2 0 图3 5 带有2 冗余的超节点覆盖网2 l 图4 1 自治域的划分2 4 图4 2 节点的位置对s c o r e 值的影响2 6 图4 3 查询成功率v s 时间2 9 图4 4 查询成功率v st t l 一3 0 图4 5 平均查询跳数v s 时间3 0 图4 6 每次查询实时延时3 l 图4 7 平均查询延时v s 时间3 1 图5 1 三信息中心的超节点结构覆盖网3 4 图5 2 线性坐标系下的节点度比较一3 6 图5 3 线性坐标系下的最短路径比较3 8 图5 4f l o o d i n g 搜索寻找源节点s 与目标节点t 之间的路径( t t l = 4 ) 3 9 图5 5 搜索步数与节点发现概率4 0 图5 6 不同规模网络文件搜索成功率比较4 1 图5 7 搜索产生消息数4 2 图5 8 不同规模网络搜索成功时平均跳数比较4 3 图5 - 9 文件查询成功率比较4 4 v i 图5 1 0 文件查询产生消息数比较4 4 图5 - 11 成功查询文件平均跳数比较4 5 附表索引 表2 1 典型p 2 p 系统文件搜索技术的性比较表1 5 表4 1 模拟实验中的参数设置2 9 表5 1 不同节点规模的度的统计3 7 v l i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的 地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包 含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共 同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名： 刻5 坌盗 日期：兰! ! 墨年月日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校有 权保留学位论文并根据国家或湖南省有关部门规定送交学位论文，允 许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内容， 可以采用复印、缩印或其它手段保存学位论文。同时授权中国科学技 术信息研究所将本学位论文收录到中国学位论文全文数据库，并通 过网络向社会公众提供信息服务。 日期：丛曼年扛日 硕士学位论文第一章绪论 第一章绪论 本章综述了p 2 p 的定义、特点和研究现状及涉及的关键技术和热点问题，简 述了本文的主要研究内容及其贡献，并概括了全文的组织结构和各章节的分工情 况。 1 1 研究的背景 1 1 1p 2 p 的定义及特点 p 2 p ( p e e r - t o p e e r ) 本身不是一种全新的概念，最初p 2 p 的概念是用于( 通 过与电话交谈方式的类l k ) 描述两个对等体之间的通信【l l ，在这种通信模式中，每 一个部分具有相同的功能，任意一个部分都可以开始一次通信。由此，p 2 p 的最 初含义就是在两个平等的参与者之间进行点对点通信。但是现在对p 2 p 赋予了新 的含义，i n t e l 工作组把p 2 p 定义为“通过系统间的直接交换所达成的计算机资源 与信息的共享 【2 】，这些资源与服务包括信息交换、处理器时钟、缓存和磁盘空 间等。i b m 则给p 2 p 赋予了更广阔的定义：系统依存于边缘化非中央式服务器设 备的主动协作，每个成员直接从其他成员而不是从服务器的参与中受益；系统中 成员同时扮演服务器与客户端的角色；系统应用的用户能够意识到彼此的存在， 构成一个虚拟或实际的群体【3 】。还有一种常用的定义：p 2 p 是一种分布式网络，网 络的参与者共享他们所拥有的一部分硬件资源( 处理能力、存储能力、网络连接 能力、打印机等) ，这些共享资源需要由网络提供服务和内容，能被其它对等节 点( p e e r ) 直接访问而无需经过中间实体。在此网络中的参与者既是资源( 服务和内 容) 提供者( s e r v e r ) ，又是资源( 服务和内容) 获取者( c l i e n t ) 。 虽然目前在学术界、工业界对于p 2 p 没有一个统一的定义，但从已有的研究 和实践中来看，p 2 p 具有这样的特点： 1 p 2 p 模式有别于传统的客户机j j 艮务器( c l i e n t s e r v e r ) 模式，网络中的资 源和服务分散在所有节点上。而且节点处于平等的地位，具有相同的能力，它们 既是服务器，又是客户机；既是服务的消费者，又是服务的提供者。 2 在p 2 p 网络中，资源和服务的提供者和使用者之间的是直接进行交互的。 p 2 p 充分利用终端设备的处理能力，用户可以直接共享和交互而不必借助中间媒 介，不用像过去那样必须连接到服务器才能浏览与下载，它使得主机间的沟通变 得更容易。 3 p 2 p 网络中的节点是自治的，它可以自主地加入和退出p 2 p 网络。因此， p 2 p 网络表现出极强的动态性。 硕士学位论文第一章绪论 4 这些自治的节点依靠相互间的协作来实现获取资源、转发消息、计算等服 务。 1 1 2p 2 p 的研究现状 从研究现状来看，欧美等西方国家对p 2 p 技术的研究开展较好，国内研究工 作处于跟进阶段。 国外开展p 2 p 研究较为著名的大学和科研机构主要包括u cb e r k e l e y ，m i t 和a t & t 互联网研究中心。在u cb e r k e l e y 大学，t a p e s t r y 项目和o c e a n s t o r e 项 目1 4 1 是p 2 p 技术相关项目。t a p e s t r y 提供了一个分布式容错查找和路由基础平台， 在此平台基础之上，可开发各种p 2 p 应用( o c e a n s t o r e 是此平台上的一个应用) ，t a p e s t r y 基于p l a x t i o n 5 】的思想，加入了容错机制，从而可适应p 2 p 的动态变化特点。 o c e a n s t o r e 是以t a p e s t r y 为路由和查找基础设施的p 2 p 平台。它是一个适合于全 球数据存储的p 2 p 应用系统。任何用户均可以加入o c e a n s t o r e 系统，或者共享自 己的存储空间，或者使用该系统中的资源。通过使用复制和缓存技术，可大大提 高o c e a n s t o r e 的查找效率。在m i t ，开展了多个与p 2 p 相关的研究项目：c h o r d 、 g r i d 和r o n 酬。c h o r d 项目的目标是提供一个适合于p 2 p 环境的分布式资源发现 服务，它通过使用分布式哈希路由表技术使查找指定对象只需要维护l o g n 长度的 路由表。其主要贡献在于提出了一个分布式查找协议，该协议可将指定的关键字( k e y ) 映射到对应的节点( n o d e ) 。从算法来看，c h o r d 是一致性哈希算法的变体。m i t 的g r i d 和r o n 项目提出了在分布式广域网中实施查找资源的系统框架( r o n 注重小规模的网络环境) 。a t & t 互联网研究中心的c a n 项目独特之处在于采用多 维标识符空间来实现分布式哈希算法。此外，斯坦福大学的对等网项目组【7 】也开展 了许多针对p 2 p 的研究工作。 国外开展p 2 p 研究的学术团体主要包括p 2 p 工作组( p e e r t o p e e rw o r k i n gg r o u p ，p 2 p w g ) t 8 1 、全球网格论坛( g l o b a lg r i df o r u m ，g g f ) i 9 1 。p 2 p 工作组成立的主 要目的是希望加速p 2 p 计算基础设施的建立和推进p 2 p 标准化工作。p 2 p w g 成立 之后，对p 2 p 计算中的术语进行了统一，也形成了相关草案，但是在标准化方面 工作却进展缓慢。目前p 2 p w g 己经合并到g g f ，由该论坛管理与p 2 p 计算相关 的工作。 从国外公司对p 2 p 计算的支持力度来看，m i c r o s o f t 公司，s u n 公司和i n t e l 公 司1 1 0 1 投入较大。m i c r o s o f t 公司成立了p a s t r y 项目组，主要负责p 2 p 计算技术的研 究和开发工作。目前m i c r o s o f t 公司已经发布了基于p a s t r y 的软件包s i m p a s t r y v i s p a s t r y ，r i c e 大学也在p a s t r y 的基础之上发布了f r e e p a s t r y 软件包。s u n 公司以j a v f l 技术为背景，开展了j x t a 项目。j x t a 是基于j a v a 的开源p 2 p 平台，任何个 人和组织均可以加入该项目。除了大学、学术团体和i t 公司积极参与p 2 p 研究之 2 硕士学位论文 第一章绪论 外，许多个人和开源爱好者也积极开展p 2 p 的研究工作，其中较为知名的是f r e e n e t 系统和g n u t e l l a 系统。f r e e n e t 1 1 j 的研究始于1 9 9 9 年，i a nc l a r c k 在爱丁堡大学 设计和开发了f r e e n e t 系统。f r e e n e t 是文件共享p 2 p 系统，其主要目的是充分利用 匿名通信系统的特点，即用户可以匿名访问系统中共享文件，也就是由于f r e e n e t 主要关注的是通信的匿名性，因而难以大规模应用。a o l 公司的两位职员在2 0 0 0 年3 月发布了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 兼容系统的 开发。寻求全分布式特征是g n u t e l l a 的主要目标，因此其匿名性好，但可靠性不 能保证。从设计角度来看，g n u t e l l a 不是一个实际的p 2 p 系统，而是一个p 2 p 协议。 系统开发者必须实现该协议才能进行文件共享，也因此被认为是目前p 2 p 资源共 享领域的“企业标准 。由于g n u t e l l a 采用“泛洪 方式进行资源发现，网络带 宽浪费极为严重，因此从理论上看，g n u t e l l a 扩展性差。 从目前国内研究现状来看，一些大学和公司成立了对p 2 p 的研究课题组和部 门。从2 0 0 3 年开始，国家8 6 3 计划和自然科学基金计划资助一些关于p 2 p 技术的 项目。目前在中国核心期刊上发表的有关p 2 p 的文章逐渐增多，文献 1 2 ，1 3 各自 综述不同的p 2 p 领域，文献 1 4 ，1 5 提出了对p 2 p 系统进行改进的方案，以及文献 1 6 ，1 7 提出新的系统和模型。文献 1 8 ，1 9 是相关的对p 2 p 领域和技术的博士论文， 可见p 2 p 也开始受到高校和研究机构的关注。因此，国内关于p 2 p 的研究仅处于 起步阶段，这就为技术创新提供了有利契机。 m a z e l 2 0 1 是北京大学网络实验室开发的一个中心控制与对等连接相融合的对 等计算文件共享系统，在结构上类似n a p s t e r ，对等计算搜索方法类似于g n u t e l l a 。 网络上的一台计算机，不论是在内网还是外网，可以通过安装运行m a z e 的客户端 软件自由加入和退出m a z e 系统。每个节点可以将自己的一个或多个目录下的文件 共享给系统的其他成员，也可以分享其他成员的资源。m a z e 支持基于关键字的资 源检索，也可以通过好友关系直接获得。g r a n a r y t 2 1 l 是清华大学自主开发的对等计 算存储服务系统。它以对象格式存储数据。另外，g r a n a r y 设计了专门的节点信息 收集算法p e e r w i n d o w 的结构化覆盖网络路由协议t o “2 2 1 。a n y s e e t 2 3 1 是华中科 技大学设计研发的视频直播系统。它采用了一对多的服务模式，支持部分n a t 和 防火墙的穿越，提高了视频直播系统的可扩展性；同时，它利用近播原则、分域 调度的思想，使用l a n d m a r k 路标算法直接建树的方式构建应用层上的组播树，克 服了e s m 等一对多模式系统由联接图的构造和维护带来的负载影响。 1 1 3p 2 p 研究热点 硕士学位论文 第一章绪论 随着n a p s t e r t 2 4 1 ，g n u t e l l a 2 s 1 等p 2 p 应用系统的出现，p 2 p 技术在文件共享和 信息搜索等方面的优势受到了广泛的关注，当前对p 2 p 技术的研究热点，主要集 中在以下几方面： 1 p 2 p 覆盖网的研究。主要有两个问题，一个是覆盖网的组织结构问题，另 一个是如何在覆盖网中进行路由的问题。p 2 p 网络的路由问题从理论上可以看作是 加权图中的最短路径问题，对于n 个节点的网络，如果每个节点都知道整个图的 拓扑结构，那么对于每个节点来说，路由的空间复杂度为o ，n 为图中的节点 总数。从一个节点到达另一个节点的路径寻找过程只需要在节点自身执行路由算 法，如果忽略网络传输所用的时间，则路由的时间复杂度为o ( 1 ) 。但实际的网络 都是高度动态的，因此只能使用拓扑结构未知的或是局部己知的算法。在这些算 法中，每个节点只知道自己的一些邻居。在现在基于d h t 的p 2 p 网络中基本可达 到两个极端：一种是空间复杂度为o ( 1 ) ，只存储常数个的邻居表；而时间复杂度 为0 0 0 9 n ) ，需要跳跃o ( 1 0 9 n ) 次才能到达目的节点，如v i c e r o y 、k o o r d e 等。另 一种是空间复杂度为o ( n ) 。邻居表中包含了所有的节点；而时间复杂度为o ( 1 ) ， 这种覆盖网也被称为“一跳式网络( o n e h o po v e r l a yn e t w o r k ) ”。 在经历了关于覆盖网络的时间复杂度和空间复杂度的两个极端之后，现在的 研究更趋向于修改基本假设，进行更接近网络实际环境的研究，如研究如何利用 异构性、本地性，如何穿透f i r e w a l l 、n a t 等。 2 数据搜索技术。随着越来越多的数据存储到p 2 p 系统中，上层应用就需要 底层架构提供数据定位与搜索能力。p 2 p 系统一般有两种搜索方式：数据定位和关 键词搜索。数据定位是指以对象i d 作为输入，得到对应的数据或存储这些数据的 节点。关键词搜索是指输入一个或多个关键词，得到包含这些关键词的数据。非 结构化网络基于泛洪( f l o o d i n g ) 或随机漫步( r a n d o m w a l k ) 处理查询，在这样的系统 中这两种搜索几乎没有区别。而结构化由于建立在d h t 的基础上，能够很自然的 实现数据定位，但对关键词搜索无法提供直接的支持，现有的搜索协议大多使用 倒排索引。如何优化和创新搜索技术，是p 2 p 的重要研究热点之一。 3 系统安全性。p 2 p 的安全性有三个方面的含义：一是系统对抗恶意攻击的 能力，二是系统对抗非授权侵入的能力，三是p 2 p 网络中的信任关系问题。尽管p 2 p 技术能克服客户服务器的单点故障的缺陷，但是p 2 p 世界同样会存在网络攻击 行为。例如，针对p 2 p 共享存储网络的典型攻击行为就是使用大量无用信息塞满 存储网络的存储空间，还有针对g n u t e l l a 的q u e r yf l o o d 试图耗尽系统的带宽，导 致网络被肢解，以及其他多种形式的攻击方式。 4 硕士学位论文 第一章绪论 1 2 本文研究内容及贡献 覆盖网络( o v e r l a yn e t w o r k ) 是在物理网络之上搭建一层逻辑网络。覆盖网络 的存在，使得我们可以屏蔽底层细节，我们面对的不再是一个个的物理计算机， 而是节点i d 和已经绑定通讯方式的通信管道。这就意味着我们可以在覆盖网络上 按照既有的规则发现节点、在任意的两个或多个节点间发送信息，而g n u t e l l a 、 c h o r d 等都只是以不同的方式来构建这个覆盖网而已。因此本文首先深入分析p 2 p 的拓扑结构及其研究现状和存在问题，在分析当前众多研究者针对p 2 p 的非结构 化拓扑存在的问题所提出的一些改进的基础上，认真研究了基于超节点结构的p 2 p 覆盖网网络，分析其存在的问题，针对超节点覆盖网中的拓扑不匹配问题、超节 点选择不合理和p 2 p 系统中普遍存在的搭便车( f r e e r i d i n g ) 问题，提出一种有效 应对上述问题的基于信息交互的超节点选择机制。鉴于超节点结构的p 2 p 系统在 文件共享等方面越来越广泛的应用，本文的研究对于提高p 2 p 系统性能等具有一 定的贡献，主要体现在以下几方面：( 1 ) 解决了p 2 p 覆盖网中物理结构和逻辑结构 拓扑不匹配问题，从而能节省文件查找、传输时间等；( 2 ) 在超节点结构的p 2 p 覆 盖网中更加合理地选择超节点可以使超节点发挥更强大的作用，可以提高系统性 能；( 3 ) 提出一种三信息中心策略来解决超节点单点失效问题，克服了超节点冗余 机制解决单点失效问题所带来的大量系统消耗的缺陷。( 4 ) 通过在不同拓扑结构上 实现f l o o d i n g 搜索策略来研究和分析了p 2 p 覆盖网拓扑结构对搜索算法性能的影 响，并进一步验证了我们提出的三信息中心超节点结构覆盖网的较好性能。 1 3 本文组织安排 本论文分为五大部分。第一部分为绪论，主要介绍p 2 p 技术的研究背景，分 析国内外研究现状及研究热点。第二章为相关研究，详细介绍p 2 p 覆盖网拓扑结 构及p 2 p 典型系统和研究进展等。第三章介绍基于超节点结构的p 2 p 覆盖网工作 原理和优点及存在的问题等。第四章将针对基于超节点结构的p 2 p 覆盖网遇到的 问题提出本文的基于信息交互的超节点选择策略。第五章介绍了我们提出的三信 息中心超节点结构覆盖网的拓扑结构，分析了拓扑结构的特性，并同其他拓扑结 构进行比较，通过在不同拓扑中实现f l o o d i n g 搜索策略，分析p 2 p 覆盖网拓扑结 构对搜索性能的影响。最后第六章是本文的工作总结以及一些研究展望。 硕士学位论文第二章p 2 p 覆盖网相关研究 第二章p 2 p 覆盖网相关研究 p 2 p 系统一般都具有内在的动态性，p e e r 可以动态地加入和离开网络【2 6 ，2 7 ，2 蜘， p 2 p 系统的运作依赖于p e e r 之间的直接连接。各个p e e r 和系统中其它p e e r 在网络 体系结构的应用层中建立虚拟连接，从而整个系统中的所有p e e r 互连组成了一个 逻辑上的虚拟网络。这一网络构建于底层物理网络之上，依赖于底层物理网络的 支持( 比如底层i p 网络的路由等) ，并且它的构建独立于底层物理网络，所以我们 把它称作覆盖网( o v e r l a y ) 网络1 2 9 , 3 0 。根据覆盖网的拓扑结构，我们可以把p 2 p 系统划分为结构化( g t m c t u 】e d ) 和非结构化( u n s n l l c t l 玳d ) 两种【3 l 3 2 1 。 2 1 非结构化p 2 p 系统 本节首先介绍非结构化拓扑的典型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 和f a s t t r a c k 等，简要分析这些系统中文件搜索技术的原理和特点，然后从泛洪优 化、随机搜索、提示性搜索、复制和缓存以及拓扑优化等五个方面来综述非结构 化拓扑下p 2 p 文件搜索技术的相关工作和研究进展。 2 1 1 典型系统 1 n a p s t e r 系统【2 4 】 n a p s l e r 是最著名的p 2 p 文件共享系统之一，n a p s t e r 采用了集中式非结构化拓 扑，使用专门的索引服务器来存放系统中各结点共享的资源对象( 文件) 的索引 信息，如图2 1 所示。新结点加入时，都需到索引服务器上注册所共享的资源对象 的索引信息。资源搜索时，发起搜索的结点直接将搜索请求提交给索引服务器， 由索引服务器返回保存了相关资源对象的结点列表。发起搜索的结点从结点列表 中选择某一结点，从该结点上直接下载需要的文件( 不再通过索引服务器) 。 图2 1n a p s t e r 系统图 以n a p s t e r 为代表的集中式非结构化拓扑的优点是文件搜索快且准确，文件搜 索开销为o ( 1 ) ，实现和维护较为简单，可以支持灵活的搜索条件。但集中式非结 6 硕士学位论文 第二章p 2 p 覆盖网相关研究 构化拓扑的缺点也是明显的，集中式索引服务器可能会带来可扩展性和单点失效 等诸多问题。由于集中式非结构化拓扑p 2 p 系统相对简单，文件搜索技术相关研 究较少。 2 g n u t e l l a 系统【2 5 1 g n u t e l l a 是一种文件共享协议，g n u t e l l a 协议有很多不同版本，本文介绍的是 得到广泛应用的0 4 版本。 g n u t e l l a 采取了典型的全分布式非结构化拓扑，如图2 2 所示。g n u t e l l a 中没 有索引服务器，每个结点都是平等的，没有s e r v e l 和c l i e n t 之分，每个结点都称为 s e r v e n t 。新结点加入时，通过一些“带外 方法( 如通过一些公用w e b 站点等) 获知已在g n u t e l l a 系统中的几个结点，然后通过这几个结点得到g n u t e l l a 系统中更 多结点的列表，从中选择某几个作为邻居。各个结点上的资源对象( 文件) 只保 存在本地，不发布到其它结点上。g n u t e l l a 采用受限t t l ( t i m et ol i v e ) 的泛洪 ( f l o o d i n g ) 技术来进行文件搜索，每个结点都将接收到的搜索请求广播给所有的 邻居结点，同时搜索请求的1 几值减1 ，直到t t l 的值为0 。如果某结点发现本 地有符合搜索条件的文件对象，该结点会沿着搜索路径反向传播q u e r y h i t 消息到 发起搜索的结点，然后两个结点通过h t t p 协议直接传输文件。g n u t e l l a 系统的维 护简单，全分布式结构，具有良好的容错性，能够支持灵活的搜索条件，并且搜 索的命中率通常较高。但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 系统的评测表吲3 3 】一次搜索在g n u t e l l a 系统中 会消耗3 5 m b p s 的带宽。g n t i t e l l a “的受限泛洪技术能够搜索的范围有限，只能搜索 结点几( t t l ) 跳之内的资源对象。 图2 2g n u t e l l a 系统 3 f r e e n e t l l 1 】 f r e e n e t 是能够提供匿名性的p 2 p 文件共享系统，可以保证文件的发布者、查 询者和存储者的匿名性。f r e e n e t 中对数据文件进行加密存储，每个文件在系统中 硕士学位论文第二章p 2 p 覆盖网相关研究 大量复制。在f r e e n e t 中，文件发布时，首先计算文件的二进制关键字k e y ( 根据 文件名通过s h a - i 算法【3 4 】计算得到) ，并产生一个h t l ( h o p st ol i v e ) 值。h t l 值决定该文件在多少个结点上复制。发布结点首先查看自己“路由表中与k e y 最相近的关键字，将数据发布到对应的结点上去，并且被发布的文件会在从初始 结点到目的结点的路径上进行沿路复制。 在f r e e n e t 中，搜索时首先获取需搜索文件的k e y ，然后发出搜索消息。当任 一结点接收到搜索消息时，首先进行本地匹配，若匹配成功则返回搜索结果；否 则将搜索消息转发到本地“路由表”中与k e y 最相近的关键字对应的结点上。搜 索消息会一直转发下去，直到搜索成功或者h t l 变为0 。如果搜索成功，则在搜 索路径中的各结点上复制该数据，并在各结点的路由表中建立数据源和k e y 的映 射。如果搜索消息转发后出现了路由环或结点失效，则根据路由表中次相近的关 键字进行转发。f r e e n e t 中同一结点会存储较多的k e y 相近的文件，同时其路由表 中也是相近k e y 的聚集。每个结点使用l r u 算法来替换文件，很久没有被访问过 的文件会被自动淘汰。 f r e e n e t 对文件进行了大量复制，搜索只需搜索到文件的任一个副本，但f r e e n e t 不能保证搜索的效率和准确性。模拟显剥3 5 】，f r e e n e t 系统的拓扑结构会不断演 变，在经过较长时间后，f r e e n e t 会形成类“s m a l lw o r l d ”拓扑【3 6 】，搜索性能有所 提高。 4 f a s t t r a c k 【3 7 】 f a s t t r a c k 采取了典型的部分分布式非结构化拓扑，f a s t t r a c k 协议目前在k a z a a 和m o r p h e u s 文件共享系统中得到应用。f a s t t r a c k 根据网络带宽等特性将系统中的 结点分为两类：超级结点( s u p e r p e e r ) 和普通结点。超级结点通常是通过高速链路 ( c a b l e x d s l 或更快等) 连接到网络上的结点，而普通结点是通过慢速链路 ( m o d e m 或更慢等) 连接到网络上的结点。每个超级结点都是系统中部分普通结 点的目录服