（计算机应用技术专业论文）p2p文件共享网络中的可扩展性问题的研究.pdf

摘要 摘要 在过去的几年里，以g n u t e l l a 和k a z a a 为代表的文件共享网络已经成为 i n t e m e t 上增长最迅速的应用。这种运行于多个对等结点之上的逻辑网络被称为 对等网络( p 2 p 网络) 。在这样的网络里，数据在结点之间直接传递，所有的结 点在功能上是对等的，既可以是客户机又可以是服务器。随着p 2 p 网络规模的 增长，可扩展性不仅成为了研究的热点，也成为了迫切需要解决的问题。为改 善p 2 p 网络的可扩展性，本文提出了两种有效的机制，分别是感知拓扑的聚类 覆盖网络( t c o ) 和多重小洪泛( m s f ) 机制。 t c o 机制主要有两方面的特点。第一，为了缓和p 2 p 覆盖网络与i p 层物 理网络两者间拓扑结构的不匹配问题，t c o 将结点按照在i n t e m e t 中的地理位 置自动聚集成类，并将所有的类合理的组织起来使得类间路由可以迅速的完成。 第二，为进一步改善网络的可扩展性，t c o 采用两种索引技术，分别是类索引 技术和主题索引技术，以提高搜索效率。在两种索引技术能够高效的应用于不 同的领域中。 m s f 机制使用多个小范围的洪泛来查询文件，它能够解决传统的p 2 p 搜索 机制中缺乏动态控制的不足。m s f 使用了三种策略来决定多个小洪泛的顺序： 同步策略、顺序策略和并行策略。同步策略的目的是最小化响应时间；顺序策 略的特点是在获取合适命中数目的基础上搜索尽可能少的结点，使得查询消息 的数量最小化，以减少网络流量；并行策略则是折中考虑了响应时间和网络流 量这两个方面。 作者对这两种机制进行了细致的研究、修改和仿真实验，得出的结论是这 两种机制都能大幅度的减少网络流量，提高搜索效率，从而改善了p 2 p 网络的 可扩展性。 关键词：对等网络，可扩展性，感知拓扑，聚类覆盖网络，多重小洪泛 a b s t r a c t a b s t 陷c t i nr e c e m y e a r s ，f i l e s h a r i n gn e t w o r k ss u c ha sg n u t e l l aa i l dk a z a a h a v eb e c o m e t l l em o s tp o p u l a ra p p l i c a t i o n si ni n t e m e t t h i sk i n do fl o g i c a ln e t w o r kt 1 1 a tw a s c o m p o s e do fm a | l yp e e rn o d e sw a sn 锄e dp e e r t o - p e e r ( p 2 p ) n e t w o r k t h em o s t d i s t i n c tc h a r a c t e r i s t i co fp 2 pn e t w o r k si st 1 1 a tt h e r ei ss y m m e 砸cc o m m u n i c a t i o n b e t w e e np e e r s ；e a c hp e e rh a sb o mac l i e n ta n das e “e rr 0 1 e a sp 2 pn e t w o r ks c a l e i n c r e a s i n g ，s c a l a b i l i t yh a sb e c o m eh o tr e s e a r c ha r e aa i l du r g e mp r o b l e mn e e dt o s o l v e i no r d e rt oi m p m v e s c a l a b i l i t yo f p 2 pn e t w o r k s ，t 1 1 i sm e s i sp r o p o s e st w on o v e 】 m e c h a l l i s m s ，n 锄e l yt o p o l o g y - a w a r ec l u s t e 咖go v e r l a y ( t c o ) a i l dm u l t i p i e s m a l l s c a l ef 1 0 0 d s ( m s f ) t h em a i nc o n m b u t i o n so ft c 0a r et w o f o l d f i r s t ，a i m i n ga ta l l e v i a t i n gt 1 1 e t o p o 】o g ym i s m a t c hp m b 】e mb e h v e e nt l l ep 2 p1 0 9 j c a ln e t 、v o r ka 1 1 dt 1 1 ep h y s i c a l u n d e r l y i n gn e “o r k ，t a 3o r g 柚i z e sp e e r si n t oc l u s t e r sb a s e do nn e t w o r k1 0 c a l i t y s e c o n d ，i no r d e rt of u n h e ri m p m v es c a l a b i l i t ya 1 1 ds e a r c he m c i e n c yo ft m o a r c h i t e c t l l r e ，w ep r e s e n tt w on o v e li n d e xt e c h n i q u e s ，n a m e l y ，c l u s t e r - i n d e xt e c h n i q u e a n dt o p i c i n d e xt e c l l l 】j q u e n en v od i m r e n tt e c l l l l i q u e sa r eh i 曲1 ye 虢c t i v ei n d i 矗e r e n ta p p l i c a t i o nd o m a i n si nw h i c ht h et m oa r c h i t e c t u r ei sd e p l o y e d m s fm e c h a i l i s mi sa i le 伍c i e ms e a r c hm e c h a i l i s mu s i n gm u l t i p l es m a l l s c a l e f 1 0 0 d s 谢t l ld i 虢r e 】1 tn o o ds o l l r c e sf o re a c hq u e r y i ti sa b l et oi m p m v es c a l a b i t yo f p 2 pn e t v v o r k sb y m a k i n gq u e r i e sd y n 锄i c b a s e do nm s s fm e c h a l l j 蛐，t 1 1 r e e p 0 1 i c i e sa r ei n t r o d u c e di nd e t e m l i n i n gt h eo r d e ro ff l o o d si n i t i a t e d ：s y n c ，s e q u e n c e a 1 1 dp a r a l l e i t h es y n cp o i i c yt r i e st oe 丘，e c tt h er e s p o n s et i m ef o raq u e r y ，t 1 1 e s e q u e n c ep o l i c yi sd e s i g n e dt om i n i m i z et h en u l t l b e ro fm e s s a g e sb ys e e k i n gt o p r o b et h em i n i m u mn 啪b e ro fp e e r sn e c e s s a r yt oo b t a i nm ed e s i r e dn 啪b e ro f r e s u l t s ，a i 】dt b ep a 脚1 e 1p 0 1 j c yc 鲫s i d e r sa 仃a d e o f r b e t w e e nr e s p o n s et i m ea 1 1 dq u e r y t r a 衢c a1 0 to fs i m u l a t i o ne x p e r i m e n t sh a v eb e e nd o n et oe x a m i n et h ep e r f o n n a n c eo f t h et w om e c h a n i s m s t h es i m u l a t i o nr e s u l t ss h o wt l l a tb o t ho ft h et 、v om e c h a n s i m s s i g n 墒c a l l t l yr e d u c en e t w o r kt r a 墒cc o s t ，t 1 1 e r e f o r ee n h a l l c et 1 1 es c a l a b i 】t yo fp 2 p a b s t r a c t n e t w o r l ( s k e yw b r d s ：p e e r - t o - p e e r ，p 2 p ，s c a l a b i l j t y ，t o p o 】o g y - a 啪r ec 1 u s l e r i n go v e r l a y t c o ，m u l t i p l es m a l l 一s c a l ef l o o d s ，m s f j i 】 第一章引言 第一章引言 第一节课题背景 在过去的几年中，采用p 2 p ( p e e r _ t o p e e r ) 技术的应用在i n t e m e t 上迅速传 播，用户数量急剧增长。在这样的应用中，数据保存在用户的计算机中( 通常 称之为对等结点，p e e r ) ，而不像以往的客户服务器( c s ) 模式那样把数据存 放在集中的服务器上。现在，由于计算机和网络的性能都出现了飞跃性的提高， 同时由于c s 模式自身的不足，人们都越来越重视和关注p 2 p 技术。一项统计 表明，p 2 p 的应用已经超过w 曲应用，成为占用i n t e m e t 带宽最多的网络应用。 p 2 p 网络中不存在中心服务器，所有的结点既是客户机，享用其它结点提 供的服务，同时又充当服务器，为其它结点提供服务。数据在对等结点之间直 接传递。p 2 p 模式能让i n t e m e t 上的闲散资源得到充分的利用，提高了网络的容 错性能，加快了信息的传播速度，同时也优化了网络的带宽利用情况。 事实上，p 2 p 并非新技术，而是旧有技术新的应用模式。自i m e m e t 诞生之 日起，p 2 p 技术就已经存在，它是i n t e m e t 框架的基础。i n t e m e t 上最基本的t c m p 协议也是对等的。在t c p i p 协议中，并没有客户端和服务器的概念，在通讯过 程中，所有的设备都是平等的。但是，限于当时p c 机的性能，后来发展的、 架构在t c p i p 之上的软件大多采用了c s 模式的结构。上个世纪9 0 年代后期， 随着w 曲服务的增长，人们感到有必要直接控制、改变和共享资源，再加上p c 机的性能在速度和处理能力方面有了突飞猛进的发展，人们开始意识到可以把 服务器软件放在单独的p c 上，而且可以在p c 间初始化全双工的信息流，这就 导致了p 2 p 技术的复兴。 由于p 2 p 模式具有的技术特点，很多计算机公司、研究部门都认为该技术 蕴涵着巨大的商业价值和技术价值，并从不同的角度应用和研究该技术。到目 前为止，p 2 p 技术主要有以下几个发展方向1 2 j 。 1 ) 文件共享服务：用户利用基于p 2 p 的网络协议，直接从含有所需文件的 对等结点下载该文件。应用实例包括n a p s t e r l 3 j g n u t e l l a 【4 j 和k a z a a 【5 】等。 2 ) 分布式计算：把网络中的众多计算机暂时不用的计算能力连接起来，使 第一章引言 用积累的能力执行超级计算机的任务。任何需要大量数据处理的行业都可从分 布式计算中获利，如天气预报、动画制作、基因组的研究等。应用实例包括 s e t i 囝h o m e 州和x e n o s e r v e r s i7 等。 3 ) 网络存储：随着网络规模的扩大，人们开始将传统的局域存储技术向基 于i n t e m e t 的数据存储系统发展。一些研究项目开始采用p 2 p 技术来组织和存 储数据，这些项目的目标都是提供面向全球的数据存储服务。应用实例包括 o c e a l l s t o r e 嘲、p a s t 【9 】和c f s f l 0 】等。 4 ) 即时通讯：在基于p 2 p 技术的通信中，通讯双方的交流完全是点对点进 行，不依赖服务器的性能和带宽。尽管目前的即时通讯技术一般都带有中心服 务器，但中心服务器仅仅是用来控制用户的认证信息等基本信息，帮助完成节 点之间的初始连接工作。应用实例包括i cq 【1 1 】、s k y p e 【1 2 】等等。 5 ) 应用层组播：利用p 2 p 技术可以在应用层实现组播功能而不需要i p 层 的支持。这样就可以避免出现由于i p 层迟迟不能部署对组播的支持而使组播应 用难以进行的情况。应用实例包括n a r a d a 【1 3 】，a l m i 和s c r j be 【15 1 等。 当然，这5 种类型的应用绝不是p 2 p 仅有的应用，有人预计p 2 p 的应用可 达一百种以上，其巨大的开发空间将成为未来i t 界关注的焦点。p 2 p 是技术， 更是技术思想的革命，它将实现i n t e m e t 的大部分潜力，将i n t e m e t 从一个基于 网页和电子邮箱的网络转变成为一个动态的、颗粒状网络。 第二节论文的选题及研究意义 文件共享服务不仅是p 2 p 技术最热门的研究领域之一，也是占用网络带宽 最多的应用。当前的p 2 p 文件共享网络中同时在线人数已达数百万，其流量已 占据整个i n t e m e t 流量的4 0 以上。本文的主要研究内容就是提高p 2 p 文件共 享网络的可扩展性。这里的可扩展性指的是在p 2 p 网络规模发生变化的情况下， 网络的性能对此变化的响应。 p 2 p 文件共享网络的主要目的就是提供各种共享文件，帮助人们方便的搜 索资源，从而实现跨越地理位置障碍的资源共享。然而，p 2 p 网络中的资源具 有极大的分散性，资源分布在许多结点上，每个结点上的资源往往并不多。同 时，由于结点自由的加入或退出，使得p 2 p 网络的资源还处于不断的动态变化 之中。这种独特的资源存在形式决定了p 2 p 网络特有的搜索技术。当网络规模 2 第一章引言 较小时，p 2 p 系统的性能还比较高，然而随着网络规模的逐渐增大，系统的可 扩展性已成为制约p 2 p 系统进一步发展的瓶颈。 导致当前的p 2 p 文件共享网络的可扩展性不高的原因是p 2 p 结点之间的通 信消耗了大量的网络资源，这主要是由以下三个因素造成的。 1 ) 低效的资源搜索机制。现在的p 2 p 文件共享网络通常采用洪泛( f l o o d i n g ) 机制进行资源搜索，例如最具代表性的g n u t e l l a 【4 】和k a z a a 系统1 5 j o 在洪泛机 制中，发起搜索的源结点向所有邻居结点广播查询消息，邻居结点再向自己的 所有邻居结点广播查询消息，直到达到预定的层次为止。这种机制，可以让查 询消息覆盖p 2 p 网络中的绝大部分结点，具有实现简单和响应时间短的优点， 但也会产生大量的冗余查询消息，浪费了大量的网络流量。 2 ) 不匹配的拓扑结构。p 2 p 网络是建立在应用层上的逻辑网络，并不是一 个真实的物理网络。每个p 2 p 结点都和它的邻居结点在逻辑上相连以形成一个 覆盖网络( o v e r l a yn e t w o r k ) 。两个邻居结点之间都相距个应用层的跳步 ( h o p ) ，然而，一个应用层的跳步可能会包含多个i p 层的跳步。实际上，目前 的p 2 p 网络在建立时大都没有考虑到i p 层的拓扑信息，仅仅是在应用层随机建 立一个覆盖网络，这会导致低效的路由。例如，在p 2 p 网络中，一个位于南开 大学的结点向一个位于天津大学的结点发送的消息可能会先经过一个位于欧洲 的结点。这种拓扑结构的不匹配会浪费不少网络资源。 3 ) 搜索过程缺少动态控制。p 2 p 网络中使用的洪泛机制采用完全相同的方 式处理每次搜索过程。例如，一次关键字为“m p 3 ”的搜索和一次关键字为“南 开大学高科楼”的搜索，洪泛机制都会把查询消息广播到相等数目的结点上。 事实上，关键字为“南开大学高科楼”的搜索可能无法返回足够多的命中结果， 而关键字为“m p 3 ”的搜索会产生过多的查询消息，返回过多的命中结果，很 可能用户并不需要这么多的结果，因此也浪费了不少网络流量。 由于p 2 p 文件共享网络消耗了大量的网络资源，这成为了制约其可扩展性 的瓶颈。p 2 p 文件共享网络的可扩展性已成为迫切需要解决的问题，也成为了 当前研究的热点。目前，研究人员提出了不少提高p 2 p 网络的可扩展性的改进 机制，例如r a l l d o mw 出k s 【1 6 】，e x p a i l d i n gm n g 【1 6 】，l o c a li n d i c e s 机制等等。 绝大多数的改进机制能够减少网络流量，提高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 机制，分别是感知拓扑的聚类覆盖 网络( t o p o l o g y a w a r ec 1 u s t e r i n go v e r l a y ，t c 0 ) 和多重小洪泛( m u l t i p l e s m a l l s c a l ef l o o d s ，m s f ) 机制。作者对这两种机制进行了细致的研究、修改 和仿真实验，得出的结论是这两种机制都能大幅度的减少网络资源的消耗，因 而改善了p 2 p 网络的可扩展性。 第三节论文结构 本文在第二章中阐述了p 2 p 网络的一些基本概念和基础知识，p 2 p 模式与 现在的c s 模式的优缺点分析、以及常见p 2 p 文件共享系统。 第三章介绍当前p 2 p 采用的洪泛搜索机制和其他学者提出的几种改进方 法，并对这些改进方法进行归类总结。 第四章介绍t c 0 机制的基本思想，并通过仿真实验检验了这个协议的性 能。 第五章介绍m s f 机制的基本思想，并通过仿真实验检验了这个协议的性 能。 第六章对论文进行了简要的总结，并提出了今后的研究方向。 4 第二章p 2 p 的相关知识 第二章p 2 p 的相关知识 第一节p 2 p 的定义 在本文中，p 2 p 是英文p e e r - t o p e e r 的简称，其中p e e r 是“同等的人、伙伴” 的意思。国内的媒体一般将p 2 p 翻译成“端对端”或者“对等”，p 2 p 的实质是 代表了信息和服务在一个对等结点( 通常是一台主机) 与另一个对等结点间的 流动。 p 2 p 技术主要指由硬件形成网络连接后的信息控制技术，主要代表形式是 在应用层上的基于p 2 p 网络协议的客户端软件。一种常见的p 2 p 的定义是： p 2 p 是一种分布式网络，网络的参与者共享他们所拥有的一部分硬件资源( 处 理能力、存储能力、网络连接能力、打印机等) ，这些共享资源需要由网络来提 供服务和内容，能被其它对等结点( p e e r ) 直接访问而无需经过中间实体。在 此网络中的参与者既是资源( 服务和内容) 提供者，又是资源( 服务和内容) 获取者。 正是p 2 p 技术的迅猛发展，使得网络“内容”改变了原本所在的位置，从 “中心”走向“边缘”，也就是说内容不再存在于大型的服务器上，而是存在于 所有用户的p c 机上。p 2 p 使得p c 机重新焕发活力，使它们不再是被动的客户 端，而成为具有服务器和客户端双重特征的设备。 第二节p 2 p 模式和c ，s 模式的比较 p 2 p 模式和大家所熟知的c s 模式有着本质上的区别。在c s 模式中，当 用户间要进行信息资源的传输活动时，首先要构建一个有一定资源的服务器， 然后在其它地方( 大多数为在个人计算机上) 创建信息并“发布”到服务器上。 这些信息在服务器上等待请求。接收到请求之后，服务器将信息传递给请求者。 整个过程需要三步，即创建信息一发布信息一查看信息。图2 1 是一个典型的 c s 模式的体系结构。c s 模式具有以下特点i j 。 1 ) 集中计算方式，信息和数据都保存在服务器端，每台服务器所能提供的 5 第二章p 2 p 的相关知识 信息数量受到自身存储空间的限制。客户端基本上只是一个高性能的i o 设备， 上面大量的资源和服务被闲置。 2 ) 服务器及网络的带宽决定了整个网络的性能，任意时刻它所能支持的客 户端访问数量受到自身处理能力以及网络吞吐能力的限制。随着客户端的增加， 服务器的负载就越来越重，成为系统的瓶颈。一旦服务器崩溃，整个网络也随 之瘫痪。 3 ) 被发布的信息的分布与生存期十分稳定。通常，发布的信息将会在服务 器上稳定的保存较长的一段时间，并且该服务器也不间断地运行在网络上。 4 ) 被发布的信息的存储与管理比较集中，服务器根据适当的算法和规则管 理本地信息，应答客户端的访问请求或进行计算。 图2 1c ，s 模式的网络结构 同样是进行信息资源的传输，在p 2 p 模式下则有很大不同。处于对等地位 的结点( 如个人计算机) 可以直接向存储源信息的对等结点发送请求。而接收 到请求的结点可以直接将需要的信息发送给对方。整个过程只需两步，即创建 信息一查看信息。图2 2 是一个典型的p 2 p 模式的体系结构。p 2 p 模式具有以 下特点【l 】o 1 ) 每个结点具有相同的地位，既可以请求服务也可以提供服务，同时扮演 着c s 模式中的服务器和客户端两个角色。这是和传统的c s 模式最大的差别。 2 ) p 2 p 网络的规模随着加入结点的数量的增长而增长，新结点的加入会给 系统增加新的资源。从理论上看，p 2 p 网络的可扩展性几乎是无限的，可以达 到现有的i m e m e t 规模。 6 第二章p 2 p 的相关知识 3 ) p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散在各个结点 之间进行的，部分结点或网络遭到破坏对其它部分的影响很小。p 2 p 网络一般 在部分结点失效时能够自动调整整体拓扑，保持其它结点的连通性。p 2 p 网络 通常都是以自组织的方式建立起来的，并允许结点自由地加入和离开。 图2 2 p 2 p 模式的网络结构 4 ) 每一个结点都可以随意的发布信息，缺乏集中管理，因此信息的获取比 较困难。 5 ) p 2 p 减少了对传统c s 结构服务器计算能力、存储能力的要求，同时因 为资源分布在多个结点，更好的实现了整个网络的负载均衡。 6 ) p 2 p 模式允许更多的用户参与信息交换，因而不易管理。 表2 1 中列出了p 2 p 和c s 模式各自的优缺点。 表2 】c s 模式和p 2 p 模式的比较 7 第二章p 2 p 的相关知识 第三节当前的p 2 p 文件共享应用 当前存在的p 2 p 文件共享软件至少有数十种之多，常见的包括n 印s t e r 、 g n u t e l l a 、k a z a a 、b i t t o 玎e n t 、c h o r d 、p a s 仃y 等等。 2 3 1n a p s t e r n a p s t e r 【3 】是p 2 p 文件共享软件的开山鼻祖，这是一个供大家交换m p 3 音乐 的p 2 p 软件平台。用户可以免费下载并安装该软件，使用该软件的用户可以很 方便地搜索到其他用户的计算机里存储的m p 3 文件，并可以免费下载到自己的 电脑中，当然也可以将自己拥有的m p 3 文件共享给其他用户。该网站于1 9 9 9 年投入运行，鼎盛时期达到5 0 0 0 多万用户，可以共享近2 0 0 万首免费的m p 3 音乐文件。 在n a p s t e r 系统内，每一个用户都称为结点，在各自的本地磁盘上存储m p 3 文件。n a p s t e r 采用了集中式的目录服务器机制，但目录服务器并不存储m p 3 文件，只存储用户共享的m p 3 文件索引。为下载需要的音乐文件，用户需要向 目录服务器发出基于关键字的查询并获取拥有该文件的结点的i p 地址，用户可 以从获得的多个结点中选择其中之一，直接下载该文件。实际的文件传输在请 求结点和目的结点之间通过t c p 连接直接进行。 2 3 2g n u t e l l a 继n a p s t e r 之后，各种基于p 2 p 技术的文件共享服务可谓是风起云涌，其 中最具有代表性的是g n u t e l l a 【4 】。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 仰连接。 每个g n u t e l l a 结点都定义了本地的共享文件夹，它们可以根据文件名的部分或 者完全匹配进行搜索。搜索方式按照洪泛的广播机制进行。用户可以基于搜索 结果，选择合适的文件进行下载，并可以和每个文件所有者结点建立类似h t t p 的连接。g n u t e l j a 是完全分布式的、无结构的对等网络，它采用的洪泛式的消 息广播机制使网络具有高鲁棒性和高动态性的同时，也使网络产生了呈指数级 增长的查询消息，因此，g n u t e l l a 网络的可扩展性较差。 r 第二章p 2 p 的相关知识 2 3 3k a z a a k a z a a 【5 】是现在全世界最流行的几款p 2 p 软件之，采用了超级结点 ( s u p e r n o d e ) 的概念，吸取了中心化结构和全分布式无结构型拓扑的优点。在 k a z a a 中，所有的超级结点连接成一个类似g n u t e l l 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 6 o 版本也采用了超级结点的技术1 1 刿) ，这样可以使系统更好的扩展， 因为它无需中央索引服务器存储文件名，自动把性能较好的主机选为超级结点， 超级结点存储着属于它的叶子结点的文件信息。由于超级结点的索引功能，搜 索效率和系统的可扩展性都得以大大提高。 2 3 4b i t 7 n r 他n t b i f r o n 即t 【2 0 】的特点是强调了多点对多点的传输，充分利用了用户在下载时 没用上的上载带宽，在下载的同时也能进行上传。换句话说，同一时间的下载 者越多，上传者也越多。这种多点对多点的传输方式，大大提高了传输效率和 对带宽的利用率，因此最常被用来下载大容量的电影、游戏和软件等。b j t t o n c n t 把提供完整文件的主机称为种子，正在下载的主机称为客户，某一个文件现在 有多少种子和多少客户是可以看到的，只要有一个种子，就可以放心的下载。 当然，种子越多、客户越多的文件下载起来的速度会越快。 b i 仃b n e n t 中恢复了服务器的参与，这是因为多点对多点的传输需要通过服 务器进行调度，但服务器中依然没有存储实际文件，这一点和n a p s t e r 非常接近。 虽然在b i t t o 玎e n t 里面有服务器的概念，但使用b i t t o r r e m 的人并不需要关心服 务器在哪里。b i t t o r r e n t 的服务器称为t r a c k e r ，起资源定位的作用，为客户指 明种子的位置，只有用b i t t o r r e n t 发布文件的人才需要知道服务器的具体地址。 9 第二章p 2 p 的相关知识 2 3 5e d o n k e y ，e m u i e 和b i t t o r r e m 类似，e d o l l l ( e y e m u l e 【2 1 1 也是建立于多点文件传输协议之上。 一个e d o i l l ( e y 网络由服务器网络和客户端网络两部分组成。在客户端的软件上， 服务器列表像电话本一样排列，客户通过浏览服务器列表而获取它需要的文件 所有者的信息。每一个客户端连接到一个服务器作为它的主服务器。在连接时， 由客户端告诉主服务器它的共享文件、i p 地址、通信端口号等信息。 搜索过程可分为主服务器搜索和扩展搜索。在主服务器搜索时，主服务器 会通过匹配己记录的信息把查找结果反馈给搜索的客户端。当使用扩展搜索时， 搜索请求和应答结果通过发送限制带宽的u d p 包连接到其它服务器上。 在下载过程中，当客户端想下载某个文件时，它首先需要收集到一个拥有 该文件的客户端列表。它会先行询问主服务器，是否有用户拥有该文件，然后 再连接和询问其它服务器。一旦它找到拥有该文件的其它客户端，它将请求每 个客户端发送这个文件的不同片。最后，这些不同的片会组装成一个完整的文 件。在查找到下载源后，下载就是客户端和客户端通过p 2 p 进行直接对话，期 间没有数据流通过服务器。 2 3 6c h o r d c h o r d 【2 2 】是麻省理工学院的一个研究项目，采用了分布式哈希表( d i s t m u t e d h a s ht a b l e ，d h t ) 技术来实现消息传递机制和根据关键字进行查找的定位机制。 c h o r d 利用相容哈西函数为每个结点和关键字分配标志符。在c h o r d 中，结点 并不需要知道所有其它结点的信息。每个结点只需要知道少数其他结点的路由 信息即可。例如，在由个结点组成的c h o r d 网络中，结点a 只需要维护其他 0 ( f o g ) 个结点的信息，其中标志符仅大于结点a 的第一个结点称为结点a 的 后继结点。同样，每次查找只需要d ( ，昭) 条消息。当结点a 加入网络时，为 了保持相容哈希映射，某些原来分配给a 的后继结点的关键字将分配给a 。当 结点a 离开网络时，所有分配给它的关键字将重新分配给a 的后继结点。而无 论当结点a 加入或者离开网络时，c h o r d 需要更新其它结点的路由表信息，每 次加入或者离开需要传递d ( f d 矿) 条消息。 2 3 7 c a n c a n ( c o n t e m a d d r e s s a b l en e t 、v o r k ) 【2 3 】是加州大学伯克利分校的一个研究 1 0 第二章p 2 p 的相关知识 项目，可以在i n t e m e t 规模的大型对等网络上提供分布式哈西表的功能。c a n 类似于一张大哈希表，其基本操作包括插入、查找和删除 二元组。 c a n 由大量的自治结点组成，每个结点保存哈希表的一部分，称为一个区。此 外，每个结点还保存少量的邻接区的信息。对每个特定关键字的插入请求、查 找请求或删除请求将由中间的c a n 结点进行路由直至到达包含该关键字的 c a n 结点所在的区。c a n 是基于虚拟的d 维笛卡儿坐标空间来实现数据组织 和查找功能的。整个坐标空间动态地分配给系统中的所有结点，每个结点都拥 有独立的互不相交的一块区。c a n 中的路由机制非常简单，只需要计算目的点 的坐标，然后寻找从发起请求的结点到目的结点的一条路径就可以。在由个 结点组成的c a n 网络中，平均路由长度是( d 留) ( ”“) ，每个结点只需要维护埘 个的邻接结点信息。结点数增加时每个结点维护的信息不变，而且路由长度只 是以d f 胛 的数量级增长。 2 3 8p a s t r y p a s 时f 2 4 j 网络中的每个结点都有一个唯一的结点号。当给定一条消息和一个 关键字时，p a s 廿y 结点将会把这条消息路由到在当前所有的p a s t r y 结点中结点 号和关键字最接近的那个结点。为了进行路由，p a s 时把结点号和关键字表示 为一串以2 6 为基的数。在每个路由步骤中，当前结点将把消息路由给结点号和 消息关键字的共同前缀长度至少比当前值长一个数位( 也就是b 个二进制位) 的结点。如果不存在这样的结点，消息将传递给前缀长度相同但是结点号数值 更接近关键字的结点。因此，路由过程的复杂度是d ( o g b ) ，这里表示网络 中p a s 仃y 结点的总数。每个p a s t r y 结点记录在结点空间中和它直接相连的邻居 结点。由于结点号是随机分配的，那么在结点空间中的相邻结点很可能在i p 层 网络的地理位置上是分散的。p a s t r y 利用了i p 层网络的拓扑信息，因为p a s t r y 可以把关键字路由到和它最接近的多个结点中的任何一个。 2 3 9t a p 豁t r y 1 a p e s 廿y 【2 5 】和p a s 仃y 的工作原理非常接近，都是采用d h t 技术把p 2 p 结点 在逻辑上组成一个超立方体结构。t a p e s 订y 中的每个结点都保存了邻居映射表， 邻居映射表可以用于把消息按照目的地址一位一位地向前传递，比如从一+ 8 到 t + 9 8 到+ 5 9 8 到目的结点4 5 9 8 ( 这里表示通配符) 。在t a p e s 时中，匹配从右 第二章p 2 p 的相关知识 到左进行。结点的邻居映射表分为多个级别，每个级别表示的前缀长度对应于 该级别在标识符中的位置，而每个级别包含的项的数量则等于标识符表示法的 基数。比如，结点3 2 5 a e 的邻居映射表中第四级第九项是网络中以9 5 a e 结尾 的离3 2 5 a e 最近的结点的标识符。由上面的描述可知，当一条消息到达传递过 程中的第n 个结点时，该结点和目的结点的共同前缀长度至少大于n 。为了进 行转发，该结点将查找邻居映射表的第n + 1 级并选择其中和目的结点标识符的 下一位对应的项。转发过程将在每个结点中依次进行直到到达目的结点。从转 发过程中，可以知道，只要各个结点的邻居映射表是一致的，那么转发过程至 多只经过o ( f 0 9 6 ) 个结点就可以到达目的结点，这里的是结点标识符名字空 间的大小，而b 是表示标识符时使用的基数。同样可知，由于每个结点的邻居 映射表的每个级别只需要保存b 个表项，因此，邻居映射表的空间为o ( 6 + l o g b n 、。 第四节无结构型p 2 p 网络与结构型陀p 网络的比较 p 2 p 网络有无结构型和结构型之分。无结构型网络的特点就是网络中的资 源分布和网络拓扑几乎没有关系，要进行资源的搜索和定位，要么进行中央目 录索引，要么采用洪泛的广播机制。前面提到的n a p s t e r 、g n u t e l l a 、k a z a a 、 b i f r o r r e m 和e d o l l k e v ，都属于无结构型p 2 p 网络。而在结构型网络中，网络中 的资源分布与网络拓扑存在着严格的对应关系，需要利用d h t 技术来进行消息 传递和关键字查找，c h o r d 、c a n 、p a t r y 和t a p e s 仃y 都属于结构型p 2 p 网络。 p 2 p 文件系统的主要目的是就是大规模的文件共享，大规模文件共享的一 个重要前提是有效的搜索机制。无结构型p 2 p 的搜索机制的优势在于能很好的 支持模糊匹配、文本匹配和范围匹配等复杂的文件查询方式，从而为用户带来 有益的可选择性。所谓可选择性搜索，指以文件共享为代表的应用中，一个搜 索请求可能产生多个匹配结果，使用户可以基于结果的质量( 如匹配度) 进行 有选择性的下载。无结构型p 2 p 网络的主要缺点是其可扩展性较差。可扩展性 的研究是当前无结构型p 2 p 网络的一个研究重点。 结构型p 2 p 网络的优势在于其搜索机制只需要较小的通讯开销，因而在理 论上有更好的可扩展性，但其最大的弱点是不支持模糊匹配和文本匹配等复杂 的文件查询方式。另外，基于d h t 的拓扑维护和修复算法也比g n u t e l l a 模型和 1 2 第二章p 2 p 的相关知识 k a z a a 模型等无结构的系统要复杂得多。目前，结构型p 2 p 的文件共享系统缺 乏在i n t e m e t 中大规模真实部署的实例，鲜有成功应用的案例。即使是c h o r d 、 c a n 、p a s t r y 等项目也更多的用于动态性更低的大规模网络存储应用上。 事实上，目前已投入实际应用的p 2 p 文件共享服务大都是基于无结构型的 p 2 p 网络的，不少学者也指出无结构型的p 2 p 网络更适合于文件共享系统 【2 6 】。 本文的研究主要是针对基于洪泛搜索的无结构型p 2 p 网络的。本文提出的 两种改进机制都可以运用在类似g n u t e l l a 的完全分布式、无结构型p 2 p 网络中， 也可以运用在k a z a a 系统中由超级结点组成的上层覆盖网络中( 因为k a z a a 中超级结点组成的覆盖网络可以看作是一个类似g n u t e l 】a 的完全分布式网络) 。 第五节p 2 p 网络的行为和拓扑特征 p 2 p 网络在行为和拓扑方面有以下几个特征。 1 ) 规模大。很多p 2 p 网络已经达到数百万结点同时在线的规模，这样大的 规模导致的一个直接后果就是不可能使用全连接的拓扑结构。这样一来，如何 让结点知道更多其它结点的信息并保证任意两个结点之间能够通信就成为一个 棘手的问题。因此，p 2 p 网络中的资源搜索就成为一个重要的研究方向。 2 ) 动态性。由于结点频繁的加入或退出，p 2 p 网络呈现出高度的动态性。 一份研究报告【2 8 l 指出，在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 个结点加入或者退出网络。 3 ) 异构性。p 2 p 网络中结点的硬件能力和入网方式的不同，造成了参与 p 2 p 系统的结点在存储能力、计算能力和带宽能力上都有着很大差异( “。如何 利用这种异构性把所有结点的可用资源都充分利用起来以提高网络性能是p 2 p 系统必须仔细研究的问题。 4 ) 资源分布的不合理性。很多理性用户总是试图多使用别人的资源，少贡 献自己的资源。研究报告口8 】指出，在g n u t e l l a 中有2 5 的结点从不共享文件给 别人，只从别人那里下载文件，这种结点被成为f r e e r i d e r 。另外有7 的结点贡 献了超过5 0 的文件。使用激励机制阻止舶e r i d e r 的出现是p 2 p 研究的重点之 1 3 第二章p 2 p 的相关知识 5 ) 不匹配的拓扑结构。p 2 p 是建立在应用层的覆盖网络，在拓扑结构上与 下面的i p 层的物理网络并不匹配。一份研究报告俐指出，在g n u t e l l a 网络中， 尽管有超过4 0 的结点位于最大的1 0 个自治系统中，但只有2 5 的应用层 连接所相连的两个相邻结点是位于同一个自治系统内的。因此，g n u t e l l a 网络 产生的消息大都要跨越自治系统的边界，这会产生较多的网络流量。 6 ) 结点度数的幂( p o w e rl a w ) 分布和小世界( s m a l l w o r l d ) 特性。结点 的度数指的就是该结点的邻居数目。研究报告例指出，p 2 p 网络和i n t e m e t 骨干 网类似，其结点度数的分布都呈现幂分布( 也称为z i p f 分布) ，即度数为k 的 结点的分布概率满足公式：p ( k l o c l ，其中t 随网络的不同而不同。其中，i n t e m e t 骨干网的t 。2 2 ，g n u t e j l a 网络的t 一2 3 。幂分布的含义可以简单解释为在网 络中少数结点有较高的度数，绝大多数结点的度数很低。度数较高的结点与其 他结点的联系比较多，通过它找到待查信息的概率较高。p 2 p 网络同时还具有 小世界的特征，即网络拓扑具有高聚集度和平均路径短的特性。在符合小世界 特性的网络模型中，可以根据结点的聚集度将结点划分为若干个簇，在每个簇 中有一个度数最高的结点为中心结点。由于网络中存在着这些高度数结点，导 致网络拓扑出现平均路径短的现象。报告【2 9 j 也指出在由大约5 万个结点组成的 g n u t a l l e 网络中，9 5 的结点