（计算机应用技术专业论文）基于p2p信息共享模式的研究与实现.pdf

中文摘要 摘要 最近几年，对等计算( p e e r - t o p e e r ，简称p 2 p ) 迅速成为计算机界关注的热门 话题之一，p 2 p 模型与传统的c s 模型相比，其优势在于降低了对服务器的依赖和 它的分散控制。一些p 2 p 模型甚至不需要服务器，用户可以不经过服务器和其他 用户进行链接。纯p 2 p 系统与c s 系统不同，它没有单点失效的问题。一些模型 中，p 2 p 把服务器放到适合的位置，使服务器的作用被限制到最小，为信息共享提 供了很大的空间。 随着p 2 p 技术的广泛应用，各种p 2 p 软件在网络上盛行，从g n u t e l l a ，k a z a a 的资源搜索工具，到b t 资源下载技术，从q q 、流媒体播放等即时通信工具，到 网络游戏，都应用了p 2 p 技术。p 2 p 软件逐渐走向平台化、综合化，各种p 2 p 技 术的综合应用已经是一个p 2 p 软件发展的趋势。 本文首先分析了p 2 p 发展的各种模型，从各种集中目录式到泛式搜索结构， 从非结构化到结构化的各种模型，通过对模型的分析针对校园网选择了适当的模 型，并对模型提出了一定的改进，搭建了一个基于p 2 p 技术的信息共享平台。综 合应用p 2 p 技术，为使用者提供更大的方便。为进一步研究p 2 p 技术提供了一个 平台。 关键词：客户机i l l 务器；对等网；终端；信息共享 英文摘要 t h er e s e a r c ha n d i m p l e m e n t a t i o nb a s e d o np 2 pi n f o r m a t i o ns h a r e m o d e l a b s t r a c t p e e r - t o - p e e r ( p 2 ni so n eo ft h em o s tp o p u l a rc o m p u t e rs c h e m e si nr e c e n ty e a r s a sa g a i n s tt h ec l i e n t s e r v e ra r c h i t e c t u r e t h eg r e a t e s ts t r e n g t ho fp 2 p b a s e dm o d e l s a r et h e i rd e c r e a s e dd e p e n d e n c yo nt h es e t v e ra n dt h e i rd e c e n t r a l i z a t i o no fc o n t r o l f r o ms e r v e r w h i c hu s e dt ob ew o r k s t a t i o nt op e e r s s o m ep 2 pm o d e l sd on or e q u i r e s e r v e r e n du s e r sc a r td i r e c t l ye s t a b l i s hc o n n e c t i o n sw i t ho t h e ru s e r sw i t h o u t i n v o l v i n gs e r v e r u n l i k ei nt h ec ss y s t e m , t h e r ei sn os i n g l ep o i n to ff a i l u r ei np 2 p ； i ns o m em o d e l s ，i nw h i c hp 2 pp u t st h es e r v e ri np l a c e ，t h er o l eo ft h es e r v e ri s r e s t r i c t e dt oab a r em i n i m u m t os h a r ei n f o r m a t i o n , h a v em o r ed e v e l o p m e n t i nr e c e n ty e a r s p 2 pt e c h n o l o g yi s 谢d e l yu s e di nf i l e s h a r i n ga p p l i c a t i o n s i n t e r n e t h a sf i l l e do ft h ev a r i o u sp 2 p s o f t s i n c l u d eg n u t e l l a ，k s z a ar e s e a r c ht o o l s a l s o i n c l u d eb td o w n l o a dt o o l s ，q qc o m m u n i c a t i o nt o o l sa n dn e tg a m e s t h a ti st h e t r e n do f t h ep 2 pd e v e l o p m e n t t h i sp a p e ra c c o r d i n gt 0d i f f e r e n tt y p e so fp 2 pn e t w o r k s t h i sp a p e rd i s c u s st h e d i f f e r e n tm o d e l s c h o s et h ef i tm o d e l sa c c o r d i n gt ot h ec a m p u sn e t , a n dd e v e l o pt h e f i l e s h a r i n ga p p l i c a t i o n st 0a n a l y z et h ep 2 pt e c h n o l o g y k e yw o r d s ：c l i e n t s e r v e r ；p 2 p ；p e e r ；i n f o r m a t i o ns h a r i n g 大连海事大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：本论文是在导师的指导下，独立进行研究工作所取得的成果， 撰写成硕士学位论文 ：基王2 焦皇基皇搓式的班究生塞理：。除论文中已经 注明引用的内容外，对论文的研究做出重要贡献的个人和集体，均己在文中以明 确方式标明。本论文中不包含任何未加明确注明的其他个人或集体已经公开发表 或未公开发表的成果。 本声明的法律责任由本人承担。 论文作者签名：名友选弘0 7 年弓月? 日 学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连海事大学研究生学位论文提交、 版权使用管理办法”，同意大连海事大学保留并向国家有关部门或机构送交学位 论文的复印件和电子版，允许论文被查阅和借阅。本人授权大连海事大学可以将 本学位论文的全部或部分内容编入有关数据库进行检索，也可采用影印、缩印或 扫描等复制手段保存和汇编学位论文。 保密口，在年解密后适用本授权书。 本学位论文属于：保密口 不保密9 请在以上方框内打“”) 论文作者签名：专级翅导师签名：怒1 了 日期：力口7 年；月叫日 基于p 2 p 信息共享模式的研究与实现 第1 章绪论 1 1 引言 起初，i n t e r a c t 只是一个由几台计算机组成的小型网络，它允许通过任何终端 访问数据。逐渐，i n t e m e t 形成了一个超级网络一网络中的网络一遍及全球。 i n t e m e t 发展至今，根本原因在于其布建的任何一根网线都是为人与人之间的 交流而设置的。能够引起互联网震动的，也只有交流方式的变革本身。如今恐怕 只有很少人不知道p 2 p 的概念了，即便没有深入探究，但在互联网间进行的活动 几乎没有不沾p 2 p 技术的【1 1 。作为一种新的网络计算技术，受到工业界和学术界的 普遍关注【2 l 【3 j 。一个简单的例子，在使用q q 尽情聊天之时，实际上就享受着p 2 p 技术带来的方便和愉快。 根据被引用比较多的c l a ys h i r k y l 4 】的定义，p 2 p 技术是在i n t e m e t 现有资源组 织和查找形式之外研究新的资源组织与发现方法，p 2 p 技术最大的意义在于不依赖 中心结点而依靠网络边缘结点自组织对等协作的资源发现( d i s c o v e r y ，l o o k u p ) 形式【1 】。顾名思义，对等网络打破了传统的c l i e n t s e r v e r 模式，对等网络中的每个 结点的地位都是对等的。每个结点既充当服务器，为其他结点提供服务，同时也 享用其他结点提供的服务。虽然近年来网络带宽成倍增加，但是热门站点仍然不 堪重负。而空闲的链路带宽却被白白浪费。利用p 2 p 提供的分布式结构的目的则 是有效的均衡负载，充分利用带宽。此外，计算机的计算能力按照摩尔定律在飞 速增加，但增加的计算能力并未被充分挖掘，p 2 p 为充分挖掘计算机空闲计算能力 提供了可能。 1 2 选题意义和价值 伴随着p 2 p 技术及其商业应用的发展，p 2 p 技术对于未来网络传播可能产生 的影响也成为一个令人关注的问题。从目前来看，p 2 p 技术对于网络传播的影响主 要包括以下几方面：网络信息共享、利用方式和程度将进一步改变；围绕p 2 p 技 术思想展开的软件与信息产品开发，将在一定程度上改变媒体网络的未来面貌： 第1 章绪论 p 2 p 带来的去中心化特点将使互联网管理的难度迸一步增加；p 2 p 可能成为媒体同 的交流与合作的新平台，也可能加速媒体形态的演化。而从总体看，p 2 p 技术对未 来的社会影响程度，取决于政治、经济等各种力量的博弈结果，而这也将最终影 响着互联网的未来f 4 1 。 所以搭建一个有效的信息共享平台对于合理分配网络资源，加速资源定位， 提高资源下载速度，充分利用网络资源都有巨大的意义。 1 3 本文研究的主要内容 当访问服务器时经常碰到这样的情况，提示连接人数过多，请稍后尝试。由 于资源有限不可能为每一个人提供服务，如资源的持有者能将资源共享，这将大 大提高资源的有效利用率。所以需要这样一个信息共享的平台。本文研究的主要 内容就是基于p 2 p 信息共享模式的研究与应用，搭建一个基于p 2 p 技术的校园信 息共享平台。利用现有的p 2 p 技术为校园网提供一个有效的信息共享平台。系统 主要利用改进后的集中模式的p 2 p 模型建立这样一个平台，服务器为用户提供一 个网内共享信息的资源列表，而具体的资源怎么存放在不同的p e e r 上，服务器则 不用存储这些文件，文件只需在用户之间传输即可，而在文件下载过程中则利用 p 2 p 技术中的m f t p ( 以b t ( b i t t o r r e n t ) 【5 】为代表) 技术实现多对多的传输模式提 高用户的下载效率，从而减轻服务器负担，减少网络负载。 这个工作的主要贡献： l - 分析了p 2 p 技术的发展和应用。 2 从p 2 p 技术的资源放置，资源定位，资源传输三个方面介绍了目前p 2 p 技 术的各种算法和模型。 3 根据需求搭建一个基于p 2 p 的信息共享平台。 分析和利用现有的p 2 p 技术，根据应用环境来搭建一个综合的信息共享平台 是本文所要完成的主要工作。 1 4 本文的组织结构 本文各章节安排如下： 基于p 2 p 信息共享模式的研究与实现 第一章引言部分，介绍了本文所要研究和将要实现的系统。 第二章介绍了p 2 p 技术的定义，发展和应用。 第三章介绍了将要实现的共享平台的基本模型以及模型与其它模型相比的优 缺点。 第四章介绍了平台的具体实现。 第五章是结论和下一步将要完成的工作。 第2 章p 2 p 技术综述 第2 章p 2 p 技术综述 本章首先介绍p 2 p 的定义以及发展历程。接着从p 2 p 技术的资源存放，资源 定位以及资源下载三大方面来介绍p 2 p 技术。 2 1p 2 p 定义 最近几年，对等计算( p e e r t o p e e r ，简称p 2 p ) 迅速成为计算机界关注的热门 话题之一。p 2 p 即对等计算。通常称之为p 2 p 协议，但是事实上p 2 p 并不是一个 网络协议，没有必要遵守的接口规则，而是一种网络应用模式。目前p 2 p 技术在 学术界，工业界对于p 2 p 没有一个统一的定义，但是以下的特性使其明显的区别 于其他的技术【2 j 【3 i 。 i p 2 p 系统是自组织和非集中式的，各接点( p e e r ) 是动态的和自治的。 2 接点( p e e r ) 同时承担客户机、服务器、路由器三重角色。 3 各个接点的职能相同，他们之间的交互直接而且对等。 4 纯粹的p 2 p 系统不存在集中机制。 p 2 p 打破了传统的c l i e n t s e r v e r ( c s ) 模式1 2 4 1 ，在网络中的每个结点的地位都 是对等的。每个结点既充当服务器，为其他结点提供服务，同时也享用其他结点 提供的服务6 1 1 7 1 。p 2 p 与c s 模式的对比如下图2 1 所示： c l i e n t sc l i e n t s 图2 1c sp 2 p 模型 f i g 2 im o d e lc sp 2 p c l i e m s 基于p 2 p 信息共享模式的研究与实现 p 2 p 技术与c s 模式相比其优点体现在以下几个方面： 非中心化：网络中的资源和服务分散在所有结点上，信息的传输和服务的实现 都直接在结点之间进行，可以无需中间环节和服务器的介入，避免了可能的瓶 颈。同时也为资源的共享提供了更多的渠道。p 2 p 的非中心化基本特点，带来 了其在可扩展性、健壮性等方面的优势【8 】。 可扩展性：在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了，系统整 体的资源和服务能力也在同步地扩充，始终能较容易地满足用户的需要。整个 体系是全分布的，不存在瓶颈。理论上其可扩展性几乎可以认为是无限的【砌。 健壮性：p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散在各个结 点之间进行的，部分结点或网络遭到破坏对其它部分的影响很小。p 2 p 网络一 般在部分结点失效时能够自动调整整体拓扑，保持其它结点的连通性。p 2 p 网 络通常都是以自组织的方式建立起来的，并允许结点自由地加入和离开。p 2 p 网络还能够根据网络带宽、结点数、负载等变化不断地做自适应式的调整【8 】。 高性能价格比：性能优势是p 2 p 被广泛关注的一个重要原因。随着硬件技术 的发展，个人计算机的计算和存储能力以及网络带宽等性能依照摩尔定理高速 增长。采用p 2 p 架构可以有效地利用互联网中散布的大量普通结点，将计算任 务或存储资料分布到所有结点上。利用其中闲置的计算能力或存储空间，达到 高性能计算和海量存储的目的。通过利用网络中的大量空闲资源，可以用更低 的成本提供更高的计算和存储能力【8 】。 隐私保护：在p 2 p 网络中，由于信息的传输分散在各接点之间进行而无需经过 某个集中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。此外，目前 解决i n t e m e t 隐私问题主要采用中继转发的技术方法，从而将通信的参与者隐 藏在众多的网络实体之中。在传统的一些匿名通信系统中，实现这一机制依赖 于某些中继服务器接点。而在p 2 p 中，所有参与者都可以提供中继转发的功能， 因而大大提高了匿名通讯的灵活性和可靠性，能够为用户提供更好的隐私保护 【羽。 第2 章p 2 p 技术综述 负载均衡：p 2 p 网络环境下由于每个接点既是服务器又是客户机，减少了对传 统c s 结构服务器计算能力、存储能力的要求，同时因为资源分布在多个接点， 更好的实现了整个网络的负载均衡f 8 】。 2 2p 2 p 文件共享系统的发展 p 2 p 本身的基本技术的存在时间和曾经熟悉的u s e n e t 、f i d o n e t 这两种非常 成功的分布式对等网络技术几乎是一样的，甚至更长些。翻翻资料就可以知道， u s e n e t 产生于1 9 7 9 年，f i d o n e t 创建1 9 8 4 年，它们都是一个分散、分布的信息 交换系统 9 1 。在最初的p 2 p 应用出现时，许多使用该技术的人们甚至不会使用计算 机。然而f 是这种孕育着思想的网络技术为p 2 p 的出现搭建了温床。 p 2 pi f 式步入发展的历史可以追溯到1 9 9 7 年7 月，那几乎就是互联网在中国 起步的阶段。在一段介绍此时p 2 p 技术的时间表中这样写着：”h o t l i n e c o m m u n i c a t i o n si sf o u n d e d ，g i v i n gc o n s u m e r ss o t t w a r et h a tl e t st h e mo f f e rf i l e sf o r d o w n l o a df r o mt h e i ro w l lc o m p u t e r s ”( 1 9 9 7 年7 月，h o t l i n ec o r n m u n i c a t i o n s 公司成 立，并且研制了一种可以使其用户从别人电脑中直接下载东西的软件) 1 9 1 。 早在1 9 9 8 年，美国东北波士顿大学的一年级新生、1 8 岁的肖恩范宁为了能 够解决如何在网上找到音乐而编写的一个简单的程序，这个程序能够搜索音乐文 件并提供检索，把所有的音乐文件地址存放在一个集中的服务器中，这样使用者 就能够方便地过滤上百的地址而找到自己需要的m p 3 文件。到了1 9 9 9 年，令他 们没有想到的是，这个叫做n a p s t e r 加】的程序成为了人们争相转告的”杀手程序 ”它令无数散白在互联网上的音乐爱好者美梦成真，无数人在一夜之内开始使 用n a p s t e r 。在最高峰时n a p s t e r 网络有8 0 0 0 万的注册用户，这是一个让其他所有 网络望尘莫及的数字。这大概可以作为p 2 p 软件成功进入人们生活的一个标志。 时间表中这样记录着这一段历史如图2 2 所示： 2 3p 2 p 文件共享系统的分类和研究的三个方面 目前，p 2 p 技术的主要研究体现在拓扑结构、基于不同拓扑结构的发现算法和 基于不同发现算法的应用以及传输的技术，体现出研究的层次性。 基于p 2 p 信息共享模式的研究与实现 本文主要从这3 个层次进行综述，以期比较全面了解p 2 p 发现技术的研究现 状。如图2 3 所示： 1 9 9 92 0 0 02 0 0 1 现在 团圈 图2 2p 2 p 发展历程 f i g 2 2p 2 pd e v e l o p i n g 图2 3p 2 p 的三个研究方向 f i g 2 3t h r e ep a r t so f p 2 p - 7 - 第2 章p 2 p 技术综述 2 3 1p 2 p 网络的拓扑结构研究 拓扑结构是指分钿式系统中各个计算单元之间的物理或逻辑的互联关系，结 点之j b j 的拓扑结构一直是确定系统类型的重要依据。目前互联网络中广泛使用集 中式、层次式等拓扑结构，i n t e r a c t 本身是世界上最大的非集中式的互联网络，但 是九十年代所建立的一些网络应用系统却是完全的集中式的系统，很多w e b 应用 都是运行在集中式的服务器系统上。集中式拓扑结构系统目前面临着过量存储负 载、d o s 攻击等一些难以解决的问题。层次式拓扑结构是一种应用比较广泛的分布 式拓扑结构，d n s 系统是其最典型的应用【l l 】【1 2 1 1 3 1 。 耦合度是用来衡量p 2 p 系统的拓扑构造过程是受某种机制严格控制，还是动 态非决定性的。根据祸合度，p 2 p 系统可分为两大类：( 1 ) 非结构化拓扑； ( 2 ) 结构化拓扑。而根据分散度又可以划分为：( 1 ) 集中式拓扑；( 2 ) 部分分布式 拓扑；( 3 ) 全分布式拓扑【l l l 【1 2 1 。目前集中p 2 p 软件的结构如表2 1 所示： 表2 1p 2 p 软件的分类 t a b 2 1k i n do f p 2 ps o f t w a r e 覆盖网络 结构化 非结构化 中心服务器模式n a p s t e r m a z e 混合型 k a z a a f a s t t r a c k 集 中 e d o n k e y 剧 b i t t o m j 豆 完全无中心服务器k a d e m l i a ( o v e r n 鳓 g n u t e l l a c h o r d l i m e w i r e p a s t r y ( p a s t )m o r p h a s t a p e s t r y ( o c e a n s t o r e ) n a p s r y 根据以上拓扑结构的关系可以将p 2 p 研究分为4 种形式：中心化拓扑 基于p 2 p 信息共享模式的研究与实现 ( c e n t r a l i z e dt o p o l o g y ) ；全分布式非结构化拓扑( d e c e n t r a l i z e du n s t r u c t u r e d t o p o l o g y ) ；全分布式结构化拓扑( d e c e n t r a l i z e ds t r u c t u r e dt o p o l o g y ) 和半分布 式拓扑( p a r t i a l l yd e c e n t r a l i z e dt o p o l o g y ) 0 3 1 。 其中，中心化结构最大的优点是维护简单，发现效率高。由于资源的发现依 赖中心化的目录系统，发现算法灵活高效并能够实现复杂查询。最大的问题与传 统客户机月最务器结构类似，容易造成单点故障，访问的“热点”现象和法律等相 关问题。 全分1 1 】非结构化网络在重叠网络( o v e r l a y ) 采用了随机图的组织方式，结点 度数服从“p o w e rl a w ”规律，从而能够较快发现目的结点，面对网络的动态变化 体现了较好的容错能力，因此具有较好的可用性。同时可以支持复杂查询，如带 有规则表达式的多关键词查询，模糊查询等【8 】。 由于没有确定拓扑结构的支持，非结构化网络无法保证资源发现的效率。即 使需要查找的目的结点存在发现也有可能失败。由于采用t t l ( t i m e - t o l i v e ) 广 播洪泛、随机漫步或有选择转发算法，因此直径不可控，可扩展性较差嘲。 因此发现的准确性和可扩展性是非结构化网络面临的两个重要问题。目前对 此类结构的研究主要集中于改进发现算法和复制策略以提高发现的准确率和性 能。 最新的研究成果体现在采用分布式散列表( d h t ) 0 6 1 1 刀的完全分布式结构化 拓扑和发现算法。d h t 类结构能够自适应结点的动态加入退出，有着良好的可扩 展性、鲁棒性、结点i d 分配的均匀性和自组织能力。由于重叠网络采用了确定性 拓扑结构，d h t 可以提供精确的发现。只要目的结点存在于网络中d h t 总能发现 它，发现的准确性得到了保证【引。 d h t 类结构最大的问题是d h t 的维护机制较为复杂，尤其是结点频繁加入退 出造成的网络波动( c h u m ) 会极大增加d h t 的维护代价 s l 。d h t 所面临的另外 一个问题是d h t 仅支持精确关键词匹配查询，无法支持内容语义等复杂查询。 半分布式结构吸取了中心化结构和全分布式非结构化拓扑的优点，选择性能 较高( 处理、存储、带宽等方面性能) 的结点作为超级点( s u p e r n o d e s ，h u b s ， 第2 章p 2 p 技术综述 u l t r a p e e r s ， r e f l e c t o r s ，s u p e r p e e r ，r e n d e z v o u s ) ，在各个超级点上存储了系统中 其他部分结点的信息，发现算法仅在超级点之间转发，超级点再将查询请求转发 给适当的叶子结点。半分布式结构也是一个层次式结构，超级点之问构成一个高 速转发层，超级点和所负责的普通结点构成若干层次【8 】o 半分布式结构的优点是性能、可扩展性较好。较容易管理，但对超级点依赖 性大，易于受到攻击，容错性也受到影响。研列”1 比较了4 种结构的综合性能， 比较结果如表2 ，2 所示。 表2 24 种结构得性能比较 t a b 2 2c a p a b i l i t yo f f o u rf l a m e s 中心化拓扑 全分布式非结构全分布式结构化半分布式拓扑 化拓扑拓扑 可扩展性 碧 差好中 可靠性 差 好好中 可维护性最好最好好中 发现算法效率 晟高 中 高 中 复杂查询支持 支持不支持支持 2 3 2p 2 p 文件系统查找技术 重叠网络( o v e r l a y ) 实际是对p 2 p 系统运行的实际网络的一个抽象反映。对 实际网络的不同认识，分为截然不同的2 种流派：认为重叠网络是一个完全随机 图的全分布式非结构化拓扑；认为重叠网络存在确定性拓扑结构的全分布式结构 化拓扑。 对重叠网络完全不同的认识，也导致了不同的p 2 p 发现算法的出现。 非结构化p 2 p 发现技术 非结构化p 2 p 系统主要有三个，n a p s t e r l l 0 1 ，c m u t e l l a 1 4 1 和f r e e n e t 1 5 1 。 n a p s t e r 是最早出现的p 2 p 系统之一，并在短期内迅速成长起来。n a p s t e r 墓丁p 2 p 信息共享模式的研究与实现 实质上并非是纯粹的p 2 p 系统，它通过一个中央服务器保存所有n a p s t e r 用户 上传的音乐文件索弓1 和存放位置的信息。当某个用户需要某个音乐文件时，首 先连接到n a p s t e r 服务器，在服务器进行检索，并由服务器返回存有该文件的 用户信息；再由请求者直接连到文件的所有者传输文伊1 0 l 。 n a p s t e r 首先实现了文件查询与文件传输的分离，有效地节省了中央服务器 的带宽消耗，减少了系统的文件传输延时。这种方式最大的隐患在中央服务器 上，如果该服务器失效，整个系统都会瘫痪。当用户数量不断增加到一定数量 时，n a p s t e r 的系统性能会大大下降。 g n u t e u a 也是一个p 2 p 文件共享系统，它和n a p s t e r 最大的区别在于g n u t e l l a 是纯粹的p 2 p 系统，采用了基于完全随机图的洪泛( f l o o d i n g ) 发现和随机转 发( r a n d o mw a l k e r ) 机制。 所有的查询都通过在网络中以有限的洪泛方式进行，这种方式虽然可以有 效地找到需要的信息，但却会在网络中产生大量的流量。另外c m u t e l l a 也没有 提供足够的安全机制。g n u t e l l a 采用广度优先的广播机制查询所需文件，并采 用t t l 机制限定查询消息的存活期【1 4 1 。 f r e e n e t 和g n u t e l l a 类似，也采用了完全分布式的模型而且增加了一些改进 措施。f r e e n e t 结点可以通过指定本地的共享目录来共享自己的存储( 而不仅仅 是共享文件或者对象) ，任何其他结点都可以向这个共享目录中写入文件。每 个文件都通过一个反映文件内容的关键字( 并不要求全局唯一) 进行标识，关 键字也可以包括访问权限等其他信息。每个结点都使用一个最近最少使用的缓 冲区保存本地存储文件的信息，使用另一个最近最少使用缓冲区保存本地文件 和某些远程文件的元数据信息。 当结点收到查找请求时，将使用元数据信息有效地把查找定位到最可能保 存该文件的结点。如果收到查找请求的结点在本地元数据中找不到任何匹配， 它将把请求发送到关键字比较接近于查找关键字的结点，这一过程将重复进行 直到达到预先确定传播层次数，如果仍然没有找到匹配则返回一个错误指示。 第2 章p 2 p 技术综述 如果找到了一个匹配，请求的对象将按照查找路径返回( 这一点和g n u t e l l a 不同) 。在f r e e n e t t ”1 中，查找路径中的每个结点都将缓存返回的文件数据以备 将来使用。对象的插入过程和查找过程类似，在本地插入一个对象之后，本地 结点将向邻居结点传播该对象的信息，直到达到事先确定的传播层次。 基于d h t 的发现技术 由于非结构化网络将重叠网络认为是一个完全随机图，结点之间的链路没 有遵循某些预先定义的拓扑来构建。这些系统一般不提供性能保证，但容错性 好，支持复杂的查询，并受结点频繁加入和退出系统的影响小。但是查询的结 果可能不完全，查询速度较慢，采用广播查询的系统对网络带宽的消耗非常大， 并由此带来可扩展性差等问题。 由于非结构化系统中的随机搜索造成的不可扩展性，大量的研究集中在如 何构造一个高度结构化的系统。目前研究的重点放在了如何有效地查找信息 上，最新的成果都是基于d h t 的分布式发现和路由算法。这些算法都避免了 类似n a p s t e r 的中央服务器，也不是像g n u t e l l a 那样基于广播进行查找，而是 通过分布式散列函数，将输入的关键字惟一映射到某个结点上，然后通过某些 路由算法同该结点建立连接。 首先采用d h t 组织重叠网络的p 2 p 系统主要有4 个。 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 o n 。在p l a x t o n 中，结点使用自己所知道的邻 近结点表，按照目的i d 来逐步传递消息。t a p e s t r y 基于p l a x t i o n 的思想，加入 了容错机制，从而可适应p 2 p 的动态变化的特点。o e e a n s t o r c l 2 1 1 是以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 可提高查找的效 率。 基于p 2 p 信息共享模式的研究与实现 t a p s t r y 为适应p 2 p 网络的动态特性，作了很多改进，增加了额外的机制 实现了网络的软状态( s o f ts t a t e ) ，并提供了自组织、鲁棒性、可扩展性和动 态适应性，当网络高负载且有失效结点时候性能有限降低，消除了对全局信息 的依赖、根结点易失效和弹性( r e s i l i e n c e ) 差的问题。 p a s t r y 是微软研究院提出的可扩展的分布式对象定位和路由协议，可用于 构建大规模的p 2 p 系统。在p a s t r y 中，每个结点分配一个1 2 8 位的结点标识符 号( n o d e l d ) ，所有的结点标识符形成了一个环形的n o d e l d 空间，范围从0 到 2 1 2 8 一，结点加入系统时通过散列结点口地址在1 2 8 位n o d c l d 空间中随机分 配。 在m i t ，开展了多个与p 2 p 相关的研究项目：c h o r d 1 8 1 ，g r i d 1 8 1 和r o n 1 引。 c h o r d 项目的目标是提供一个适合于p 2 p 环境的分布式资源发现服务，它通过 使用d h t 技术使得发现指定对象只需要维护o o o g , , o 长度的路由表。 在d h t 技术中，网络结点按照一定的方式分配一个唯一结点标识符 ( n o d e l d ) ，资源对象通过散列运算产生一个唯一的资源标识符( o b j e c ti d ) 且 该资源将存储在结点i d 与之相等或者相近的结点上。需要查找该资源时，采 用同样的方法可定位到存储该资源的结点。因此，c h o r d 的主要贡献是提出了 一个分布式查找协议，该协议可将指定的关键字( k e y ) 映射到对应的结点 ( n o d e ) 。从算法来看，c h o r d 是相容散列算法的变体。m i t 的g r i d 和r o n 项目则提出了在分布式广域网中实施查找资源的系统框架。 a t & ta c i r i 中心的c a n ( c o n t e n ta d d r e s s a b l en e t w o r k s ) 1 2 0 l j 页目独特之处 在于采用多维的标识符空间来实现分布式散列算法。c a n 将所有结点映射到一 个n 维的笛卡尔空间中，并为每个结点尽可能均匀的分配一块区域。c a n 采用 的散列函数通过对( k e y ，v a l u e ) 对中的k e y 进行散列运算，得到笛卡尔空间中的 一个点，并将( k e y ，v a l u e ) 对存储在拥有该点所在区域的结点内。c a n 采用的 路由算法相当直接和简单，知道目标点的坐标后，就将请求传给当前结点四邻 中坐标最接近目标点的结点。c a n 是一个具有良好可扩展性的系统，给定n 第2 章p 2 p 技术综述 个结点，系统维数为d ，则路由路径长度为o ( n 1 ，d ) ，每结点维护的路由表信息 和网络规模无关为o ( d ) 。 23 3p 2 p 文件系统资源的传输技术 现在的传输技术可以分为：m - f t p ；多点下载；单点下载。这里本文将介绍 一下以b i t t o r r e n t 为代表的m f t p 模型，b i t t o r r e n t ( b t ) 是目前比较流行，而且应 用比较广泛的p 2 p 技术，下面就来了解一下b i t t o r r e n t 的工作原理。以下本文简称 b t 。 传统的模式：更多的用户需要更多的带宽，b t 的解决方法：使用用户相互传 递信息，见图2 4 和图2 5 。 使用b i t t o r r e n t ，当多个人同时下载同一个文件的时候，他们之间也相互为对 方提供文件的部分片段的下载。这样，就把上载的开销分摊到每个下载者那里， 也就可以在理论上支持无限多个下载者来下载同一个文件。 b i t t o r r e n t 下载部署 b i t t o r r e n t 完成一次下载部署，至少需要一个t r a c k e r 和一个s e e d 。所谓t r a c k e r ， 是一个服务器，负责帮助p e e r s 之间相互建立连接。p e e r ，是要求下载文件的用户。 而s e e d ，被称为“种子”，是被下载文件的拥有者 2 2 2 3 1 。如图2 6 所示 图2 4 传统的文件传输模式 f i g 2 4o l dm o d e lo f t h ef i l ee x c h a n g e 基tp 2 p 信息共享模式的研究与实现 图2 5p 2 p 的文件传输模式 f i g 2 5p 2 pm o d e lo f t h ef i l ee x c h a n g e 图2 6b t 的下载部署 f i g 2 6a r r a n g eo f b td o w n l o a d b i t t o r r e n t 是通过一个扩展名为t o r r e n t 的文件进行下载部署的，t o r r e n t 的文 件放在一个普通的w e b 服务器上。t o r r e n t 文件包含了要共享的文件的信息，包括 文件名、大小、文件的散列信息和一个指向t r a c k e r 的u d 。下载者通过使用b i t t o r r e n t 客户端打丌t o r r e n t 文件同t r a c k e r 进行联系。 第2 章p 2 p 技术综述 b i t t o r r e n t 完成一次下载部署的过程是： ( 1 ) 第一个s e e d 向t r a c k e r 注册，等待为别人提供文件； ( 2 ) 第一个p e e r 向t r a c k e r 注册，并取得s e e d 的信息； ( 3 ) p e e r 与s e e d 建立连接，告诉t r a c k e r 自己要下载的文件、自己使用的端口以 及类似的信息，并从s e e d 处读取文件；由于原始的文件，只有s e e d 拥有，所 以晚，s e e d 至少要上传原始文件的一份完整拷贝； ( 4 ) 另外一个p e e r 加入进来，t r a c k e r 负责帮助p e e r 获取s e e d 和其它p e e r s 的信 息，p e e r 利用这些信息和s e e d 以及前一个p e e r 建立连接，然后从这两者处获 取文件，并上传自己拥有的文件片段。 b i t t o r r e n t 工作原理 b i t t o r r e n t 中文件下载相关的逻辑问题，通过p e e r s 之间的交互来解决。 盛对等发布 b i t t o r r e n t 下载部署过程中，一些关于下载和上传的速率的信息被发送给 t r a c k e r 。t r a c k e r 的职责被严格限定为“帮助p e e r s 相互发现对方”。b i t t o r r e n t 将 文件切割为固定大小的片段( 典型的大小是2 5 6 k ) 。p e e r s 只有在检查了片段的完 整性之后，j 会通知其它p e e r s 它拥有这个片段。 流水作业 b i t t o r r e n t 协议，很重要的一点是同时发送多个请求，以避免单个请求的两个 片段发送之间的延迟。b i t t o r r e n t 协议将每个片段又进一步分为子片段，每个子片 段的大小一般是1 6 k ，同时，它一直保持几个请求被同时发送。流水作业选择同时 发送的请求数目的依据是能使得大多数连接变得饱和。 矗片段选择 选择一个好的顺序来下载片段，对提高性能非常重要。一个差的片段选择算 法可能导致所有的片段都处于下载中，或者另一种情况，没有任何片段被上载给 其它p e e r s 。 ( 1 ) 严格的优先级 基于p 2 p 信息共享模式的研究与实现 片段选择的第一个策略是：一旦请求了某个片段的子片段，那么该片段剩下 的子片段优先被请求。这样，可以尽可能快的获得一个完整的片段。 ( 2 ) 最少优先 对一个下载者来说，在选择下一个被下载的片段时，通常选择的是它的p e e r s 们所拥有的最少的那个片段，也就是所谓的“最少优先”。这种技术，确保了每 个p e e r 都拥有其它的p e e r s 们最希望得到的那些片段，从而一旦有需要，上载就可 以开始。 ( 3 ) 随机的第一个片段 “最少优先”的一个例外是在刚开始下载的时候。此时，下载者没有任何片 段可供上传，所以，需要尽快的获取一个完整的片段。因此，第一个片段是随机 选择的，直到第一个片段下载完成，才切换到“最少优先”的策略。 ( 4 ) 最后阶段模式 有时候，p e e r s 可能从一个速率很慢的p e e r 那里请求一个片段。为了防止这种 情况，在最后阶段，p e e r 向所有的p e e r s 都发送某片段的子片段的请求，一旦某些 子片段到了，那么就会向其它p e e r s 发送“取消”消息，取消对这些子片段的请求， 以避免带宽的浪费【2 5 1 1 2 6 。 b i t t o r r e n t 的应用 b i t t o r r e n t 已经被广泛的使用，它为许多并发的下载者提供成百兆的文件下载。 但是，由于涉及到版权等法律和道德领域的问题，b i t t o r r e n t 技术的进一步发展和 应用尚需要规范化。 2 3 4p 2 p 系统的其他应用 除了上述的文件共享系统是p 2 p 的主要应用以外，p 2 p 系统在多个领域都有 广泛的应用和研究。 ( 1 ) 广域分布计算和协同工作 采用p 2 p 计算技术，充分利用网络上大量的闲置计算资源，将复杂的计算任 务分割成小的子任务包，分配到参与p 2 p 计算的各个结点上，由各个结点来完成 子任务并将得到的结果进行综合。通常比较适于并行的应用，如天文数据分析， 第2 章p 2 p 技术综述 基因组分析和密码破译等，典型的项目如s e t i h o m e l 2 7 1 ，g e n o m e h o m e 等。目 前的一些公司也从事相关的工作，如e n t r o p i a 和p o p u l a rp o w e r 等。 ( 2 ) 分布式存储 利用p 2 p 计算技术构建大规模分布式存储系统，也是当前p 2 p 计算研究和应 用的重要热点。传统分布式文件系统能够支持用户在一定网络范围内，对一定数 量的分布文件进行透明访问。但他们在可扩展性，易用性及性能等诸多方面，都 难以满足用户需求。p 2 p 分布式存储系统采用新的p 2 p 结构，通过分布在网络上 的大量结点的协作，使得分布式存储系统可扩展性和自组性大大增强。支持海量 用户和海量数掘的存储需求。典型的系统包括o c e a n s t o r e l 2 ”，c f s l 2 s 和p a s t l 2 9 1 等。 ( 3 ) 即时通信和应用层组播 即时通信是非常流行的一种p 2 p 应用，即时通信系统为大量的互联网用户提 供了实时交流的虚拟平台。目前的即时通讯通常采用一个( 或者多个) 中心服务 器来维护用户的身份认证等基本信息，而接点之间的即时语音或者数据通信一般 是以p 2 p 的方式直接进行的。典型的即时通信包括i c q ，o i c q 等聊天工具。以及 利用应用层组播实现在线流媒体播放等通信技术。大多数结点可以从应用层组播 树上的父结点获得视频，而无需访问视频服务器。典型系统包括b