（计算机软件与理论专业论文）hp2p网络中chord层的研究与设计.pdf

摘要 摘要 随着对等计算( p 2 p ) 技术和理论的发展，基于它的分布式应用也已渗透到很 多领域。基于分布式哈希表( d h t ) 的结构化p 2 p 网络是目前的研究热点，但是， 基于d h t 的应用并没有流行起来，原因首先是d h t 机制实现比较复杂，更重要 的是结点频繁的加入或退出所造成的网络动荡会对系统的维护造成巨大的压力， 网络系统的稳定性很差。我们提出了种混合层次化p 2 p ( h p 2 p ) 网络，网络分 两层，其中上层是结构化c h o r d 网络，下层是非结构化的洪泛网络。h p 2 p 结合了 结构化和非结构化p 2 p 网络的优点，弱化或克服了两者的缺点。本文主要介绍了 h p 2 p 网络中的上层c h o r d 的算法以及其数据结构，同时介绍结点的加入、退出、 路由表的稳固和查找服务等操作。为了进一步提高查找的效率，我们引入了路由 和关键字缓存机制。通过对h p 2 p 系统的复杂度性能分析，我们得出该网络在稳定 性、可扩展性和查询效率等方面的性能相对c h o r d 和r o o d i n g 网络都有一定的提 高。最后我们给出了c h o r d 层网络的程序设计，并介绍了一款基于h p 2 p 网络的文 件共享软件。 关键词：对等计算p 2 p 混合层次化分布式哈希表c h o r d 洪泛网络 a b s t r a c t a l o n gw i t ht h et e c h n i c a ld e v e l o p m e n to fp e e r t o p e e r ( p 2 p ) ，t h e d i s t r i b u t e d a p p l i c a t i o n sb u i l to i li t h a v e b e e nu s e di nm a n yf i e l d s d i s t r i b u t e dh a s ht a b l e ( d i n 3 ， w h i c hi st h ef o u n d a t i o no fs t r u c t u r e dp 2 pn e t w o r k , i sn o wa na c t i v er e s e a r c ha r e a h o w e v e r , t h ea p p l i c a t i o n sb a s e do nd h ta r en o tp o p u l a rs i n c ed h tm a i n t e n a n c e m e c h a n i s mi sc o m p l i c a t e da n dt h en e t w o r kc h u r nc a u s e db yt h ef r e q u e n tj o i n i n go r l e a v i n go fp e e r sc a l le n o r m o u s l yi n e a s ed h tm a i n t e n a n c ec o s t s w ep r o p o s e da h y b r i dh i e r a r c h i c a lp 2 pn e t w o r k ( h p 2 p ) t h en e t w o r kh a st w ol a y e r s ，i nw h i c ht h e u p p e rl a y e ri ss t r u c t u r e dc h o r dn e t w o r k , a n dt h el o w e rl a y e ri su n s t r u c t u r e df l o o d i n g n e t w o r k h p 2 pb e n e f i t sf r o mt h ea d v a n t a g e so fb o t hs t r u c t u r e da n du n s t r u c t u r e d n e t w o r k sa n ds i g n i f i c a n t l yi m p r o v e st h ep e r f o r m a n c es u c ha ss t a b i l i t y , s c a l a b i l i t ya n d l o o k u pl a t e n c yo ft h en e t w o r k i nt h i sp a p e r , t h ec h o r do v e d a ya l g o r i t h mi sf o r m a l i z e d t h ed a t as t r u c t u r e ，n o d ej o i n i n g , n o d el e a v i n g , r o u t i n gt a b l es t a b i l i z i n ga n dl o o k u p s e r v i c e sa r ei n t r o d u c e di nd e t a i l f u r t h e rt h ec a c h i n gm e c h a n i s mi se m p l o y e dt o a c c e l e r a t el o o k u ps e r v i c e s i np a r t i c u l a r ，t h ea n a l y s i ss h o w st h a tt h es t a b i l i t yo fc h o r d o v e r l a yi nh p 2 pn e t w o r kh a sb e e ne n h a n c e di n d e e d f i n a l l y w ep r e s e n tt h ep r o g r a m d e s i g no fc h o r do v e r l a yn e t w o r ka n ds h o waf i l es h a r es y s t e mb a s e do nh p 2 pn e t w o r k k e y w o r d ：p e e r - t o p e e r ( p 2 p ) h y b r i d h i e r a r c h i c a ld h tc h o r d f l o o d i n g 创新性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其它人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名耻 日期泣卑! i ! ：2 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密，在- 年解密后适用本授权书。 本人签名：粒 导师签名： 日期翅：! ：兰 日期洫2 ! ：厂 第一章绪论 第一章绪论 1 1 研究背景 近几年来，对等网络计算( p e e r - t o p e e r ，简称p 2 p ) 迅速成为计算机界关注的 热门话题之一。随着p 2 p 技术从第一代的中心化索引服务模式发展到第三代的基 于分布式哈希表( d i s t r i b u t e dh a s ht a b l e ，简称d h t ) 的模式，业界对p 2 p 的基础 理论研究也更加深入广泛，同时，基于p 2 p 技术的应用也迅速普及，已经渗透到 诸多领域，并逐渐影响着传统互联网的格局。i m e l 公司还发起成立了包括微软、 s l i n 和h p 等大公司在内的p 2 p - 1 - 作组，以推动p 2 p 进一步发展，财富杂志更将 p 2 p 列为影响i n t e m e t 未来的四项科技之一，被认为是代表无线宽带互联网未来的 关键技术。 随着互联网用户和数据量的急剧增长，主要用来提供数据集中存储和计算能力 的服务器端己不堪重负，而以视频为主的多媒体数据服务以及大型文件传输的流 行更突显了这一问题，为解决此类问题，p 2 p 技术应运而生。有别于传统的客户端 服务器( c l i e n t s e r v e r ，简称c s ) 模式网络，p 2 p 网络中的每个结点( p e e r ) 的 地位是对等的，即每个结点既充当服务器，为其他结点提供服务，同时也享用其 他结点提供的服务。c s 和p 2 p 网络结构如图i 1 ： c i l e n l ， s e e a e tn e t w o r kp e e l 4 0 ，e e rn e l w o f k 图1 1 1 ( s 和p 2 p 网络结构图 通过这种对等的服务，服务器的作用被淡化和减弱了，结点间通过分布、对等 的算法实现协作和共享，所有数据可以分布存储在p 2 p 网络内的各个结点上( 边缘 h p 2 p 网络中c h o r d 层的研究与设计 化) ，网络的资源被极大化的利用，整个网络的负载也可以达到均衡。 p 2 p 系统的负载均衡策略让系统中的结点均衡地承担系统负载；它的自组织的 系统维护策略，能够及时准确地探测到动态网络中的变化，并进行相应路由信息 的调整和上层应用程序相关数据的调整。因此，p 2 p 系统是一种可扩展、自组织的 分布式系统。最重要的是p 2 p 系统通过科学地组织路由信息，使结点在掌握局部路 由信息的情况下就能够取得高效的全局路由的功能。这一点对p 2 p 系统的可扩展性 做出了决定性的影响。由以上内容可以看出，p 2 p 网络的核心特征就是结点之间的 分布性、对称性、负载均衡性和自治性。 1 2 研究现状 p 2 p 技术的主要研究体现在拓扑结构、基于不同拓扑结构的发现算法以及基于 不同发现算法的应用。拓扑结构是指分布式系统中各个计算单元之间的物理或逻 辑的互联关系，根据拓扑结构的不同，可以将p 2 p 分为四种形式：中心化拓扑， 非结构化拓扑，结构化拓扑和混合化拓扑结构。 中心化拓扑网络有中央索引服务器，用来存储资源的索引信息，资源的发现依 赖于该索引系统，而数据资源在对等结点间直接传递，第一代m p 3 共享软件 n a p s t e r t l 】是一个中心化拓扑网络的典型应用。中心化结构最大的优点是维护简单发 现效率高。由于资源的发现依赖中心化的目录系统。发现算法灵活高效并能够实 现复杂查询。最大的问题与传统客户机服务器结构类似，容易造成单点故障，访 问的“热点”现象和法律等相关问题。 非结构化拓扑网络主要采用随机图的组织方式，没有中心服务器，各结点完全 平等。各结点间采用r r l ( t i m e t o l i v e ) 广播洪泛( f l o o d i n g ) 、随机漫步或有 选择转发算法等机制建立通讯，提供资源发现方法，典型的应用有c s n u t e l l a 2 】和 f r e e n e t 3 1 。网络中结点度数服从。p o w e rl a w 【4 】”规律，从而能够较快发现目的结点， 在面对网络的动态变化时，体现了较好的稳定性和容错能力，因此具有较好的可 用性。同时可以支持复杂查询，如带有规则表达式的多关键词查询，模糊查询等。 由于没有确定拓扑结构的支持，非结构化网络无法保证资源发现的效率，可扩展 性较差，即使需要查找的目的结点存在发现也有可能失败。由于采用洪泛等方式 作为查找算法i 埘，在查找的过程中网络的负载很重，可能一个查询请求会被发放到 整个网络，造成了网络资源很大的浪费，并且可能产生网络的广播风暴，造成网 络瘫痪。 以基于d h t 的定位和路由机制为核心的结构化拓扑p 2 p 已成为最新的研究热 点，这种网络系统能够自适应结点的动态加入退出，有着良好的可扩展性、鲁棒 性、负载均衡性和自组织能力。d h t 使用分布式哈希算法来解决结构化的分布式 第一章绪论 3 存储问题。分布式哈希算法的核心思想是通过将存储对象的特征( 关键字) 经过哈希 运算，得到键值( h a s hk e 订，对象的分布存储依据键值来进行。采用d h t 的p 2 p 路由协议主要有：c h o r d 6 1 ，c a n o n ，p a s t r y i 科，t a p e s t r y i 9 1 。由于采用了确定性拓扑 结构，d h t 可以提供精确的发现。只要目的结点存在于网络中d h t 总能发现它， 发现的准确性得到了保证，而且在每个结点维护少量的路由信息的情况下，资源 可以在有限的步骤内被定位到；以c h o r d 协议为例【6 】，n 个结点的p 2 p 网络。每个 结点只需要维护0 0 0 9 n ) 项路由信息，即可在0 ( 1 0 9 n ) 跳内定位到资源。目前基于 它们的应用主要集中在数据和文件共享系统上，主要有：协作文件系统c f s ( c o o p e r a t i v ef i l es y s t e m ) l t o l ，p a s t l l ”，o c e a n s t o r e l l 2 1 。d h t 结构最大的问题是 d h t 的维护机制较为复杂，尤其是结点频繁加入退出造成的网络波动( c h u m ) 会 极大增加d h t 的维护代价，从而影响其稳定性。 现今网络上流行的p 2 p 应用系统主要还是基于前两种拓扑结构，或结合这两种 结构而形成的混合p 2 p 网络，风靡全球的文件共享软件勋鼬u 1 3 】、b i t t o r r e n t 1 4 1 、 语音通讯软件s k y p e ”】以及国内流行的p 2 p 流媒体直播软件p p l i v e l l 6 1 ，都是混合 结构p 2 p 网络的应用，在面对纷繁复杂的网络环境，混合p 2 p 网络能结合两种结 构的优点，很好的适应了环境，并可以根据具体环境适时调整部分结构。该结构 的特点是在性能、可控性、扩展性都达到一种折衷。【1 刀提出基于d h t 的c l u s t e r 群组概念，在d h t 结构网络上把通信延时较短的结点分类组合成一个个c l u s t e r ， 结点间的查找和通信可以通过该c l u s t e r 建立快速通信，d h t 的查询性能得以提高。 l 墙】给出了一种层次化树形的p 2 p 网络结构设计，把很多个小的d h t 网络组织成多 层的树状网络，从外面看来是这些小d h t 网络合并而成的一个大的d h t 网络， 有结点的层次化控制及网络结点的组织适应底层物理网络等优点。 1 3 本文研究内容及意义 作者及p 2 p 研究组其他同学结合了基于d h t 的结构化p 2 p 和基于f l o o d i n g 的 非结构化p 2 p 网络的优点，提出了一种混合层次化p 2 p 网络1 1 9 l ( h y b r i dh i e r a r c h i c a l p 2 pn e t w o r k ，简称h p 2 p ) 。该网络分为两层，其中下层为按f l o o d i n g 方式组织 成的群( c l u s t e r ) 网络，每个结点都作为群结点加入到不同的群中：上层为结构化 p 2 p 网络，采用c h o r d 路由协议维护该层网络，群作为虚拟结点加入到c h o r d 网络 中。其中，超级结点是网络中选拔出来的能力较强的结点，负责管理群网络及维 护c h o r d 层的路由信息。h p 2 p 中下层f l o o d i n g 的研究和设计由小组另一位同学完 成p 3 1 。作者主要负责对c h o r d 层的研究和设计，本文主要介绍h p 2 p 网络中c h o r d 层的设计及实现，给出了相应的算法、数据结构以及过程的描述【捌。 h p 2 p 网络的提出具有如下意义： 4 h p 2 p 网络中c h o r d 屡的研究与设计 ( 1 ) 结合了结构化和非结构化p 2 p 网络的优点，弱化或克服了部分缺点； ( 2 ) 提高了d h t 结构的p 2 p 网络在现实网络中的稳定性及应用性： ( 3 ) 引入群的概念，控制群内洪泛网络的大小，减少网络资源的浪费，可避免 广播风暴； ( 4 ) 两层网络协同工作，充分继承了c h o r d 网络的高效查找特点，具有快速高 效的查找定位能力； ( 5 ) 增强了整个网络的扩展能力和负载均衡能力。 1 4 论文结构 本文共分五章： 第一章是绪论，主要介绍了p 2 p 研究的背景、现状及领域，介绍了本文研究的 内容、目的及意义。 第二章是p 2 p 技术概述，介绍p 2 p 的概念、特点及应用，介绍了p 2 p 的几种 网络结构模型，并分析其优缺点，最后给出了p 2 p 领域目前待解决的问题及面l 临 的挑战。 第三章介绍h p 2 p 网络系统框架，以及c h o r d 层网络的详细设计，给出c h o r d 层相关的数据结构和操作。 第四章详细给出了c h o r d 层网络在h p 2 p 网络系统中实现，并介绍了个基于 h p 2 p 网络的文件共享系统。 第六章是本文总结及对未来展望。 第二章p 2 p 技术 2 1 ip 2 p 的概念 第二章p 2 p 技术 2 1p 2 p 的概念及特点 5 p 2 p 目前还没有统一的定义，根据引用比较多的c l a ys h i r k y 的定义：p 2 p 技术 是在i n t e r n e t 现有资源组织和查找形式之外研究新的资源组织与发现方法，p 2 p 技 术最大的意义在于不依赖中心结点而依靠网络边缘结点自组织对等协作的资源发 现( d i s c o v e r y ，l o o k u p ) 形式。 简单的说，p 2 p 直接将人们联系起来，让人们通过互联网直接交互。p 2 p 使得 网络上的沟通变得容易、更直接共享和交互，真正地消除中间商。p 2 p 就是人们可 以直接连接到其他用户的计算机、交换文件，而不是像过去那样连接到服务器去 浏览与下载。p 2 p 另一个重要特点是改变互联网现在的以大网站为中心的状态、重 返“非中心化”，并把权力交还给用户。p 2 p 看起来似乎很新，但是正如b 2 c 、 b 2 b 是将现实世界中很平常的东西移植到互联网上一样，p 2 p 并不是什么新东西。 在现实生活中我们每天都按照p 2 p 模式面对面地或者通过电话交流和沟通。而建 立和维护这种对等联系的方法是p 2 p 技术的核心。 2 1 2p 2 p 的特点 与其它网络模型相比，p 2 p 具有以下特点： ( 1 ) 大规模性( l a r g e s c a l e ) ，p 2 p 网络内结点越多越能体现出其优势：资源 更多、计算能力更强等，同时随着p 2 p 网络规模的扩大，也会吸引更多的结点加入， 整个网络趋向大规模发展。截至到目前，s k y p e 的全球注册用户超过1 3 亿，同时在 线数量峰值已超过8 0 0 万，每天还在以2 5 万新注册用户的速度增长i ”】，p 2 p 技术在 其中的应用使对如此大规模的用户提供高效的服务的同时极大的减少运营成本。 ( 2 ) 非中心化( d e c e n t r a l i z a t i o n ) ，网络中的资源和服务分散在所有结点上， 信息的传输和服务的实现都直接在结点之间进行，可以无需中间环节和服务器的 介入，避免了可能的瓶颈。即使是在混合p 2 p 中，虽然在查找资源、定位服务或 安全检验等环节需要集中式服务器的参与，但主要的信息交换最终仍然在结点中 间直接完成。这样就大大降低了对集中式服务器的资源和性能要求。分散化是p 2 p 的基本特点，由此带来了其在可扩展性、健壮性等方面的优势。 6 h p 2 p 网络中c h o r d 层的研究与设计 ( 3 ) 可扩展性( s c a l a b i l i t y ) ，在传统的c s 架构中，系统能够容纳的用户数量 和提供服务的能力主要受服务器的资源限制。为支持互联网上的大量用户，需要 在服务器端使用大量高性能的计算机，铺设大带宽的网络。为此机群、c l u s t e r 等技 术纷纷上阵。在此结构下，集中式服务器之间的同步、协同等处理产生了大量的 开销，限制了系统规模的扩展。 而在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了，系统整体的资源 和服务能力也在同步地扩充，始终能较容易地满足用户的需要。即使在诸如n a p s t e r 等混合型架构中，由于大部分处理直接在结点之间进行，大大减少了对服务器的 依赖，因而能够方便地扩展到数百万个以上的用户。而对于纯p 2 p 来说，整个体系 是全分布的，不存在瓶颈。理论上其可扩展性几乎可以认为是无限的。 ( 4 ) 健壮性( r o b u s t n e s s ) ，在互联网上随时可能出现异常情况，网络中断、 网络拥塞、结点失效等各种异常事件都会给系统的稳定性和服务持续性带来影响。 在传统的集中式服务模式中，集中式服务器成为整个系统的要害所在，一旦发生 异常就会影响到所有用户的使用。 而p 2 p 架构则天生具有耐攻击、高容错的优点。由于服务是分散在各个结点之 间进行的，部分结点或网络遭到破坏对其它部分的影响很小。而且p 2 p 模型一般在 部分结点失效时能够自动调整整体拓扑，保持其它结点的连通性。事实上，p 2 p 网 络通常都是以自组织的方式建立起来的，并允许结点自由地加入和离开。一些p 2 p 模型还能够根据网络带宽、结点数、负载等变化不断地做自适应式的调整。 ( 5 ) 隐私性( p r i v a c y ) ，随着互联网的普及，计算和存储能力飞速增长，收集 隐私信息正在变得越来越容易。隐私的保护作为网络安全性的一个方面越来越被 大家所关注。目前的i n t e r n e t 通用协议不支持隐藏通信端地址的功能。攻击者可以 监控用户的流量特征，获得口地址。甚至可以使用一些跟踪软件直接从口地址追踪 到个人用户。 在p 2 p 网络中，由于信息的传输分散在各结点之间进行而无需经过某个集中环 节，用户的隐私信息被窃听和泄漏的可能性大大缩小。此外，目前解决i n t e r a c t 隐 私问题主要采用中继转发的技术方法，从而将通信的参与者隐藏在众多的网络实 体之中。在传统的一些匿名通信系统中，实现这一机制依赖于某些中继服务器结 点。而在p 2 p 中，所有参与者都可以提供中继转发的功能，因而大大提高了匿名通 讯的灵活性和可靠性，能够为用户提供更好的隐私保护。 ( 6 ) 高性能( h i g hp e r f o r m a n c e ) ，性能优势是p 2 p 被广泛关注的一个重要原 因。随着硬件技术的发展，个人计算机的计算和存储能力以及网络带宽等性能依 照摩尔定理高速增长。而在目前的互联网上，这些普通用户拥有的结点只是以客 户机的方式连接到网络中，仅仅作为信息和服务的消费者，游离于互联网的边缘。 对于这些边际结点的能力来说，存在极大的浪费。 第= 章p 2 p 技术 7 采用p 2 p 架构可以有效地利用互联网中散布的大量普通结点，将计算任务或存 储资料分布到所有结点上。利用其中闲置的计算能力或存储空间，达到高性能计 算和海量存储的目的。这与当前高性能计算机中普遍采用的分布式计算的思想是 一致的。但通过利用网络中的大量空闲资源，可以用更低的成本提供更高的计算 和存储能力。 2 2p 2 p 技术的应用 p 2 p 技术是一个典型的由应用推动的研究领域。n a p s t e r 和g n u t e l l a 的迅猛发 展使得众多的研究人员开始关注并投身于这个领域。目前基于p 2 p 技术的网络应 用软件也层出不穷，用户数量急剧增加，并已经渗透到诸多领域，正逐渐改变着 互联网原有的服务模式，给广大用户带来了前所未有的体验。p 2 p 技术拥有着广阔 的应用前景。 惠普实验室的一篇技术报告【2 1 】中提到了一种针对p 2 p 应用体系的分类方法，具 体如下图： c o m m u n l c m l o n 霉脚 c o i l l 臼n r z l l o n 图2 1p 2 p 应用分类体系图 本文总结了当前p 2 p 技术主要应用领域，具体如下； ( 1 ) 提供文件和其它内容共享，应用软件有：n a p s t e r 、g n u t e l l a 、f r c c n e t 、k a z a a 、 e d o n k e y 、b i t t o r r e n t 、迅雷等。 内容共享和文件交换是到目前为止最引人注目的p 2 p 应用。从第一代的中心索 引模式的n a p s t c r 软件开始，到目前流行的混合p 2 p 模式的k a z a a 、b i t t o r r e n t 等 软件普遍的应用，高效的大规模内容共享直接推动了p 2 p 技术研究的热潮，为多 媒体文件如音乐、电影的传输共享的普及提供了优秀的平台，促使了网络从以文 本为中心模式逐渐转向立体化全方位的服务模式。基于p 2 p 的内容共享包括p 2 p 文件共享与检索、高速下载、p 2 p 存储等。 8h p 2 p 网络中c h o r d 层的研究与设计 ( 2 ) 对等计算能力，其应用有s e t i h o m e 、a v a k i 、p o p u l a rp o w e r 等。 对等计算是分布式计算的思想在广域网上的延伸，目的是将网络上的c p u 资 源共享，把网络中众多的普通计算机中暂时不用的计算能力累计起来，用以执行 以往需要超级计算机来完成的任务。 在对等计算中，大型的计算任务被分解成很多个小的分片，分别分配给网络中 的结点独立执行。实际上可以将p 2 p 看作一个松耦合的分布式计算系统，可以有 集中控制结点，也可以是纯p 2 p 架构。受互联网的限制，其子任务之间的同步和 数据交换比较少，基本是相互独立的。因而对于那些可以分解的计算密集性任务 来说。对等计算是再适合不过的了。在2 0 0 2 年9 月破解了r s a 公司悬赏的r c 5 6 4 密码的组织，正是利用对等计算技术集合了互联网上的3 3 1 2 5 2 台计算机才完成了 这一巨大的计算量。对等计算的威力由此可见一斑。 许多需要大量数据处理的行业都可以从对等计算中获利，如天气预报、动画 制作、基因组的研究等。有了对等计算之后，很多时候就不再需要配备专门的超 级计算机了，可以大大降低计算成本。i n t d 也采用对等计算技术、利用其办公室 内的数百台p c 机来完成c p u 设计的工作，节省了大量的费用。同时对等计算的 发展是以p c 机资源的有效利用为出发点，自然也受到i n t e l 的极力推崇。 s e t i h o m e ! 矧利用对等计算技术完成天文方面的运算，也是一个成功的范例。 ( 3 ) 协同处理与服务共享平台，应用有j x t a 、g r o o v e 、m a g i 、n e tm ys e r v i c e 等。 协同工作依托在网络之上。但以传统的w e b 方式实现，往往给服务器带来极 大的负担，并造成了昂贵的成本支出。而采用p 2 p 技术，可以在互联网上任意两 个用户之间建立实时的联系和信息传输，避免了中央服务器产生的网络和处理延 迟及性能瓶颈，因而能够更方便、高效地实现用户之间的协同。 j x t a l 2 3 1 是s u n 微系统公司建立的p 2 p 通用技术基础开源技术，它是网络编程 和计算的平台，用以解决现代分布计算尤其是点对点( p 2 p ) 计算中出现的问题。 j x t a 建立起核心的网络计算技术，提供支持在任何平台、任何地方以及任何时间 实现p 2 p 计算的一整套简单、小巧和灵活的机制。 g r o o v e 【2 4 1 是一款优秀的协作办公软件，它的工作原理就是基于p 2 p 来实现协 作，其方法就是在项目内各个团队成员的计算机上创建一个完全同步的区域，在 这个区域内所有的讨论、文件、事件、表格、日历将完全自动与项目其他成员同 步，而且还提供了类似即时通讯的功能。g r o o v e 还可扩展提供到后台s p s 的链接， 适应性极强。g r o o v e 己被微软以1 2 亿美元收购，并入o f f i c cs y s t e m2 0 0 7 。 ( 4 ) 即时、语音通信交流，应用软件包括i c q 、q q 、m s n 、y a h o om e s s e n g e r 、 s k y p e 等。 即时通信( i n s t a n tm e s s a g e ，简称i m ) ，是指能够即时发送和接受互联网消息 第二章p 2 p 技术 9 等相关的业务。利用i mt 具，网民可以进行沟通交流、结识新朋友、实现异地文 字、语音、视频的实时互通交流，其中利用p 2 p 技术，用户可以直接和对方建立 通信：同时，i m 工具也能够为企业带来极高的生产力，如今，很多企事业单位就 已借助i m 工具来提高业务协同性及反馈的敏感度和快捷度。作为使用频率最高的 网络软件，即时通信已经突破了技术上的种种局限，加强了系统的稳定性，被认 为是现代交流方式的薪象征。除此之外它还逐步整合其他的通信方式，如e - m a i l 和手机短信功能，使其逐渐成为一个强大的个人网上通信交流平台。目前几乎每 位能上网的用户都在使用不同的即时通信软件在网络上和其他用户进行交流。 ( 5 ) p 2 p 网络游戏，目前许多互联网游戏都是通过对等网络方式实现的。通过 p 2 p 技术，游戏服务器的负载压力和运营成本极大的减小，而游戏整体的性能得到 很大的提升。 ( 6 ) 搜索引擎技术，应用有p a n d a n g o 、s k y r i d e r 等。 p 2 p 搜索技术使用户能够深度搜索文档。而且这种搜索无需通过w c b 服务器， 也可以不受信息文档格式和宿主设备的限制，可达到传统目录式搜索引擎( 只能 搜索到2 0 一3 0 的网络资源) 无可比拟的深度( 理论上将包括网络上的所有开 放的信息资源) 。 1 5d i g i t a l 公司开发的搜索引擎p a n d a n g o i 矧作为第三代搜索引擎的代表，运用 了p 2 p 网络的架构特性，把搜索引擎技术带入了更高层次：p a n d a n g o 动态地将当 前p 2 p 网络中各个r e f e r r e r 的内容进行收集，用户下载完p a n d a n g o 后再输入欲搜 索的关键字，就能和1 0 0 名r e f e r r e r 组成的网络相连，然后进入他们的电脑搜索其 上网历史及标示的书签，再通过这1 0 0 人的电脑与另外一万名r e f e r r e r 的电脑相连， 再去搜索。也就是说，每次搜索就可涵盖1 0 0 万笔相关资料。当然实际环境中还 需要考虑网络带宽以及路由优化方面的问题，p 2 p 为互联网的信息搜索提供了一个 全新的解决之道。著名的搜索引擎公司g o o g l e 也宣称要采用p 2 p 技术来改进其搜 索引擎。 ( 7 ) 电子商务应用，p 2 p 技术在金融服务、购物行为分析、电子商务集市、广 告行销等电子商务服务上有很大的应用前景。 金融服务：由于p 2 p 的沟通只单纯涉及沟通的双方，不会有第三者知道双方沟 通的信息，所以p 2 p 非常适合发展在线金融服务。美国的b i l l p o i n t 公司已将p 2 p 技术应用于电子商务的付费机制，在e b a y 上，就向全球3 5 个国家的使用者提供 了这种技术，他们可直接用彼此的信用卡进行交易。 购物行为分析：p 2 p 的“合作过滤”功能可以帮助商务网站分析消费者行为。 a m a z o n 就常用合作过滤功能来分析网民的购物行为，然后据此推测他们的好恶并 向他们推荐合适的商品。 电子商务集市：利用p 2 p 把庞大的文件交换社群转化为另类的电子商务集市。 1 0 t w 2 p 网络中c h o r d 层的研究与设计 一家名为l i g h t s h a r e 的公司己推出一种服务，让电脑使用者直接通过其电脑销售数 字产品，而不用经由e b a y 或亚马逊的中央服务器。这种服务从e b a y 脱胎，转化 成点对点模式。任何交换的内容其实都不在我们的电脑内，我们做的只是加速资 料的交换过程而已。 ( 8 ) 流媒体直播和点播系统，目前流行的应用软件有p p l i v e ，p p s t r e a m 、 g r i d c a s t 等。 基于i n t e m e t 的直播和点播系统很早就有了，但由于采用的是c s 的结构，对 服务器网络的负载压力很大，需要服务商花费巨大的财力在计算机设备和网络带 宽上，而且图象质量也得不到有效的保证，并未流行起来。随着p 2 p 技术的引入 和网络带宽的逐步提高，最近两年网络电视开始迅速升温，成为互联网的新宠。 p 2 p 流媒体传输系统将p 2 p 对等网络技术和流媒体技术完美的结合在一起。改变 了传统多媒体服务系统中客户端被动的局面，使得用户可以在观看影音文件的同 时，利用自身的空闲资源为系统中的其它用户服务。 此外，还有诸如边缘服务、智能代理、实时通信技术和广域网络存储系统等其 它几种应用方式。另外，美国c y b i k o 及瑞典p o c i tl a b sa b 等公司正试图将p 2 p 技 术应用到无线通信中，使得不必经过基站就可连接具有无线通信功能的移动终端， 实验性p 2 p 产品己经问世。 2 3p 2 p 网络结构模型分析 根据拓扑结构的不同，可以将p 2 p 分为四种形式：中心化拓扑，非结构化拓扑， 结构化拓扑和混合化拓扑结构。 表2 1p 2 p 网络系统结构 中心化拓扑非结构化拓扑结构化拓扑 混合化拓扑 纯分布 g n u t e l l a 、f r e e n e tc h o r d 、c a n 、 式 p a s t r y 、t a p e s t r y 部分分 n a p s t e rk a z a a 、s k y p e 、 布式 m o r p h e u s 、p p l i v e 、 b j t t b r r e n t 表2 1 是p 2 p 网络应用系统的分类，从中可以看出目前流行的软件基本都是非 结构化p 2 p 和部分分布式混合化p 2 p ，而目前基于纯分布式的混合化拓扑结构并 未有成熟的应用。 第二章p 2 p 技术 2 3 1n a p s t e r 图2 2n a p s t e r 网络结构图 n a p s t e r t m 属于部分分布式的中心化p 2 p 网络，是最为典型的集中目录式对等网 络模型。n a p s t e r 的工作原理如图2 2 所示。 在n a p s t e r 模型中，群高性能的中央服务器保存着网络中所有活动对等计算 机共享资源的目录信息。当需要查询某个文件时，对等机会向一台中央服务器发 出文件查询请求。中央服务器进行相应的检索和查询后，会返回符合查询要求的 对等机地址信息列表。查询发起对等机接收到应答后，会根据网络流量和延迟等 信息进行选择，和合适的对等机建立连接，并开始文件传输。这种方式最大的隐 患在中央服务器上，如果该服务器失效，整个系统都会瘫痪。另一个问题在安全 性上，n a p s t e r 并没有提供有效的安全机制。同时随着网络规模的扩大，对中央索 引服务器进行维护和更新的费用将急剧增加，所需成本过高。 2 3 2g n u t e l l a g - n u t e l l a t z l 是基于f l o o d i n g 的分布式索引算法的p 2 p 文件共享系统，图2 3 为 g n u t e l l a 的结构图。它和n a p s t e r 最大的区别在于c m u t e l l a 是纯粹的p 2 p ，在g n u t e l l a 中没有类似n a p s t e r 的中央服务器。 对等结点a 在初始化时知道已经在g n u t d l a 系统中的对等结点b 的i p 地址， 当a 和b 连接后，a 可以获得b 所知道的所有系统结点信息，这样a 就可以和它 所感兴趣的结点建立直接的t c p i p 连接。每个g n u t e l l a 结点都定义了本地的共享 文件夹，它们可以根据文件名的部分或者完全匹配进行查找。查找按照简单洪泛 ( f l o o d i n g ) 的方式进行，首先传播到所有相邻结点，然后再传播到相邻结点的相 h p 2 p 网络中c h o r d 层的研究与设计 邻结点，直到达到预先确定的层次为止。每条查找消息都带有全局唯一的标识符， 防止对同样的查找消息进行多次响应。用户可以基于查找结果，选择合适的文件 进行下载并可以和每个文件所有者结点建立类似肌甲的连接。 图2 3g n u t e l l a 网络结构图 这种结构的优势就在于没有中央服务器，能较好的处理动态结点加入和退出， 以及结点故障问题。但是这种f l o o d i n g 的方法产生了大量的消息，占用了大量的 网络带宽，影响了系统的性能。本文使用了类似g n u t e l l a 的f l o o d i n g 方法来组织 下层c l u s t e r 网络，并实现对该网络的可控及管理，有效的避免了f l o o d i n g 方法的 缺点。 2 3 3k a z a a k a z a a 【1 3 j 是现在全世界最流行的p 2 p 文件共享软件。使用k a z a a 软件进行文 件传输消耗了互联网4 0 的带宽。之所以它如此的成功，是因为它结合了n a p s t e r 耳目 严弋 f 直鱼 图2 4k a t _ a a 网络结构图 从结构上来说，它使用了g n u t e l l a 的全分布式的结构，这样可以是系统更好的 扩展，因为它无需中央索引服务器存储文件名，它是自动的把性能好的机器成为 s u p e r n o d e ，它存储着离它最近的叶子结点的文件信息，这些s u p e r n o d e ，再连通起 第二章p 2 p 技术 来形成一个o v e r l a yn e t w o r k 。由于s u p e r n o d e 的索引功能，使搜索效率大大提高。 如图2 4 所示，当n o d e 2 需要查询文件，它首先从它连接的s u p e r n o d e 的索引 中寻找，如果找到了文件，则直接根据文件所存储的机器的口地址建立连接，如 果没有找到，则s u p e r n o d e 把这个查询请求发给它连接的其他超级结点，直到得 到想要的资源。 2 3 4c h o r d c h o r d 协议是h p 2 p 网络中所用到的d h t 技术，下面详细给出c h o r d 的协议设 计【2 9 】。 2 3 4 1c h o r d 介绍 c h o r d 是由i o ns t o i c a 等人设计的一种较简单的结构化p 2 p 搜索策略。它的设 计目标是提供一个分布式、负载均衡的、可扩展的p 2 p 搜索策略，解决目前由中 心控制的搜索策略带来的扩展性差、负载均衡差等限制问题。 c h o r d 系统内，每一个结点通过某种哈希函数( 通常是s h a - 1 ) 计算出唯一的m 位的标示符偿 点t o ) ，标识该结点在c h o r d 系统中的位置。当c h o r d 需要路由某 一消息时，该消息也用哈希函数计算出消息k e y 值。消息的目标结点就是结点i d 大于或者等于消息k e y 值的结点中结点i d 最小的一个，此结点称为这个消息的后 继结点( s u c c e s s 0 0 。 在d h t 技术中，网络结点按照一定的方式分配一个唯一结点d ，资源对象通 过散列运算产生一个唯一的资源标识符( o b j e c t l d1 ，且该资源将存储在结点i d 与 之相等或者相近的结点上。需要查找该资源时，采用同样的方法可定位到存储该 资源的结点。因此，c h o r d 的主要贡献是提出了一个分布式查找协议，该协议可将 指定的关键字( k e y ) 映射到对应的结点。从算法来看，c h o r d 是相容散列算法的变 体。 2 3 4 2 相容哈希 c h o r d 采用了相容哈希【2 8 j 的一种变体为结点分配关键字。相容哈希有几个很好 的特点，首先是哈希函数可以做到负载平衡，也就是说所有的结点可以接收到基 本相同数量的关键字。另外，当第n 个结点加入或者离开网络时，只有1 n 的关 键字需要移动到另外的位置。 c h o r d 进一步改善了相容哈希的可扩展性。在c h o r d 中，结点并不需要知道所 有其他结点的信息。每个c h o r d 结点只需要知道关于其他结点的少量的“路由” 信息。在由n 个结点组成的网络中，每个结点只需要维护其他o ( 1 0 9 n ) 个结点 1 4 i f i a 2 p 网络中c h o r d 层的研究与设计 的信息，同样，每次查找只需要o ( 1 0 9 n ) 条消息。当结点加入或者离开网络时， c h o r d 需要更新路由信息，每次加入或者离开需要传递o ( 1 0 9 2 n ) 条消息。 相容哈希函数为每个结点和关键字分配m 位的标识符，此标识符可以用s h a 一1 等哈希函数产生。结点的标识符可以通过哈希结点的口地址产生，而关键字的标 识符可以直接哈希此关键字。比如口地址为1 9 8 0 0 1 的结点经过s h a - 1 哈希之 后得到的标识符为1 2 3 ，而关键字“l e t l t b e ”哈希之后的关键字为6 0 。标识符长度m 必须足够长