（计算机软件与理论专业论文）构建感知网络拓扑结构的均衡对等重叠网络.pdf

摘要 对等计算( p e e r - t 0 _ p e e r ) 是指利用分散的资源构建成的具有分布式功能 的一类系统和应用。对等网络是指为了实现对等计算系统而构建的上层重 叠网络。计算机硬件和计算机网络的高速发展，使互联网系统的计算模式正 在发生从客户机服务器( c l i e n t s e r v e r ) 模式到对等计算( p e e r t 0 _ p e e r ，亦简 称p 2 p 模式的转变。因为对等计算模式和传统的客户湍服务器模式相比具 有：可伸缩性，健壮性，分散性等优点，所以对等计算成为研究，应用和投资 的热门领域。 本文首先介绍了对等计算( p e e r t 0 p e e r ) 和对等计算的历史，然后介绍了 对等计算的特点，应用，趋势和概念。我们还介绍了结构化的对等网络重叠网 的构建和主要的d h t 协议。 感知网络拓扑结构的对等网络具有很多优点，例如：使节点之间的连接 局部化和减少资源定位的网络延迟。但是在建立感知网络拓扑的重叠网络 时，可能出现节点区间分布不均衡现象。最近的研究表明，在构建对等计算 网络时感知网络拓扑结构的邻近节点选择方法将会导致对等网络区间分布不 均衡的现象加剧。而网络的不均衡将使p e e r t 0 - p e e r 网络性能减弱，同时会破 坏p e e r _ t o - p e e r 系统的负载均衡性。 我们基于d eb r u q n 图设计了一个感知网络拓扑结构的均衡对等重叠网络， 其中我们设计一个有效的动态区间均衡算法解决其中所产生的重叠网络不均衡 现象。 关键词对等网络；分布式散列表；d eb r u u n ：感知网络拓扑：网络均衡 a b s t r a c t a b s t r a c t t h et e r m “p e e 卜t o - p e e r ”( p 2 p ) r e f e r st oac l 鼬so fs y s t e m sa n d 印p l i c a t i o n s t h a te m p l o yd i s t r i b u t e dr e s o u r c e st op e r f b r maf u n c t i o ni nad e c e n t r 出i z e dm a n n e r w i t ht h ep e r v a s i v ed e p l o y m e n to fc o m p u t e r sa n dt h es p r e a do fi n t e r n e t ，p e e r t o - p e e rc o m p u t i n gi sg o i n gt ob et h em a j n s t r e a mc o m p u t i n gm o d e li n s t e a do f c l i e n t s e r v e rc o m p u t i n gm o d e l s a m eo ft h eb e n e 龀8o fp 2 pa p p r o a c hi n c l u d e ： i m p r 。啊n gs c a l a b i l i t yb ya o i d i n gd e p e n d e n c yo nc e n t r a l i z e dp o i n t s ；e h m i n a t i n g t h en e e df o rc o s t l yi n f r a s t r u c t u r eb ye n a b l i n gd i r e c tc o m m u n i c a t i o n 锄o n gc l i e n t s ； a n de n a b l i n gr e s o u r c ea g g r e g a t i 。n a c c o r d i n gt ol i s t e db e n e a t sa n da d v a n t a g e s ， p 2 pi si n c r e a s i n g l yr e c e i v i n ga t t e n t i o nf r o mr e s e a r c h ，p r o d u c td e v e l o p m e n t ，锄d i n v e s t m e tc l r c l e s f i r s t bw e 丽ui n t r o d u c ep e e r t o _ p e e r 批1 di t sh i s t o ui n t h i st h e s i s s e c o n d l 矾t h j st h e s i sw i l lb r i e a ys u m m a r i z ea d v a n t a g e s ，a p p l i c a t i o n s ，e m e r g i n gt r e n d s a i l dp r o m i s i gc o c e p t s w 毫w i l la n a l y z e 七h es t r u c t u r e dp e e r - t o - p e e rs y s t e ma n d ( 1 i s t r i b u t e dh a s ht a b l ei nt h i st h e s i st o o b u i l d i n gat o p 0 1 0 9 y - a w a r ep e e r - t o - p e e ro v e r l a yn e t w o r kc a nb r i n gm a n ya d v a n t a g e s ，s u c ha sp m v i d i n gl o c a l i t y _ a l w a r ec o n n e c t i v i t ya n dr e d u c i n gr o u t i n gp a t h l e n 时h w h i l ei t sb e n e f i t so np e r f o r m a n c eh a v eb e e nr e c o g n i z e d ，a nu n e v e no v e r _ l a yz o n ed i s t r i b u t i o nh a se m e r g e d f k c e n tw o r kh a ss h o w nt h a tt o p 0 1 0 9 y a w a r e n e 谵h b o r8 e l e c t i o nd u r i n gc o n s t r u c t i o nc a na g g r a v a t et h eu n b a j a n c co fz o n ed i s t r i b u t i o nw h i l ei tr e d u c e sr o u t i n gp a t hl e n g t h t h ei m b 越眦c ei nz o n es i z e sm a y 1 e a dt op e r f o r m a n c ed e c r e a s ea n da nu n f a i r1 0 a dd i s t r i b u t i o n i nt h i st h e s i s ，w ep r e s e n ta ne v e nt o p o l o g y a w a r ep e e r - t o - p e e rn e t 、v o r kb a s e d o nd eb r u 巧ng r a p hb yd e v e l o p i n gan o v e ld y n a m i cz o n e b a l a n c i n ga p p r o a c h k e y w o r d sp e e r - t o - p e e r ；d h t ；d eb n l i j n ；r o p o l o g y - a w a r e ；n e t w o r kb “a n c e 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名： 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 躲墼l 一名：掣丝吼啤镰7 f 4 第1 章绪论 第l 章绪论 1 1 对等计算和对等计算发展历史 计算机硬件和计算机网络的高速发展，使互联网系统的计算模式正在 发生从客户机服务器( c i i e n t s e e r ) 模式到对等计算( p e e r t ( 卜p e e r ，亦简 称p 2 p ) 模式的转变。 对等计算的核心思想是所有参与系统的结点( 指互联网上的某个计算机) 处于完全对等的地位，没有客户机和服务器之分，也可以说每个结点既是客户 机，也是服务器：既向别人提供服务，也亨受来自别人的服务。实际上，对等 计算的概念在很早以前就己提出，但一直没有受到广泛的重视，主要是因为没 有实际运行的系统作为背景。产业界和研究界部普遍认为在大多数情况下还是 客户机服务器模式更为合理。然而，随着p c 技术和互联网( h 止e r n e t ) 的发 展，个人电脑的能力越米越强，接入带宽也逐渐增大，如何更好地利用所有结 点( 尤其是原先处于客户机地位的结点) 的能力，搭建更好的分布式系统自然 而然地成为人们关注的问题。 1 9 9 9 年n 卵s t e r 【1 】推出后迅速普及，成为对等计算的重要实例，从此之 后，越来越多的p 2 p 软件的发布和流行，一步步验证了对等计算思想的成功， 如g n u t e l l a 瞰n e e e t 【= | 】、b l t t o r r e n t 心s k y p e 5 1 等等。今天，对等计算应用 已经超过w e b 应用，成为占用互联网带宽最多的网络应用，其发展之势愈演愈 烈，成为业界持续关注与探讨的话题。与对等计算在产业界迅速普及同时，研 究界也及时跟进，对于对等计算系统的设计方法和发展方向进行了广泛而深入 的研究。 事实上，对等计算已逐渐成为一种将来社会流行的计算模式，即：人人贡 献出自己的资源、人人享受他人提供的资源。 1 2 国内外研究发展现状 今天，对等计算仍是分布式计算领域关注的焦点，受到该领域重要国际会 今天，对等计算仍是分布式计算领域关注的焦点，受到该领域重要国际会 1 一 北京工业大学工学硕士学位沦文 议的重视。2 0 0 1 年提出的结构化重叠覆盖网( s t r u c t u r e do v e r l a yn e t w 。r k ) 及分 布式哈希表( d i s t 曲u t e dh a s ht a b l e ，d h t ) ，更是引发了对等计算研究的热 潮，在此基础上提出了各种大规模分布式系统，包括存储系统、d n s 系统、在 线游戏、网页缓存、新闻组等等。同时，对于如何增强对等计算系统的各种性 能，如：安全性、隐私性、公平性、可扩展性、系统开销、访问性能等等，也 开展了深入研究。 在对等计算领域，我国研究人员近年来开展了广泛的研究工作并取得了 优异成绩，不少论文在重要国际会议上发表，同时，也做出了很多高水平 的实用系统，并获得广泛认可。其中具有代表意义的是北京大学的文件共享 系统m a z e 、清华大学的存储服务系统g r a n a r y 和华中科技大学的视频点播系 统a n v s e e 【q 。 从理论上说，要实现对等计算的计算模式，必须完成三项工作：资源放 置、资源定位和资源获取。在对等计算系统中，由于计算节点分布不均衡，如 何去有效的实现三项上述工作，是国内外研究的重点之一。下面列出对等网络 研究热点： 对等网络路由 在p 2 p 中的各种资源是分散在各个节点之中的，对分散资源的整合过程并 不是一件轻松的工作。对于一个无中心的分布式p 2 p 系统，如何利用有限 的信息从众多的资源中找到所需的结果，将成为系统性能的关键，路由技 术是对等计算模型中的核心技术之一。路由技术是p 2 p 技术的热点，如何 高效迅速的找到有效资源是对等技术的根本问题。 资源访问效率问题 广域范围、海量信息环境下网络传输状况以及服务器i o 结构性能是影响 资源访问效率的重要因素。b i t t 0 r r e r l t 的p 2 p 系统能够同时从不同节点获 取所需要的资源，如c o o l s t r e a m i n g 等p 2 p 视频广播技术，能够从多个节点 实时地获取流媒体资源。 感知网络拓扑结构的重叠网络 2 第1 章绪论 在p e e r t o - p e e r 系统中，有效的资源定位和资源获取，就需要构建感知网络 拓扑结构的重叠网络，从而使资源定位和资源获取时的网络延迟尽可能 小。流行的构建感知拓扑的重叠网络方法有三种，一种是对等网络路由算 法感知网络拓扑，一种是对等网络结构感知网络拓扑，一种是对等网络的 路由表感知网络拓扑。 1 3 课题研究目标和主要工作 建立一个感知网络拓扑结构的p e e r t o - p e e r 重叠网络是有效快速资源定位的 重要手段。但是在建立感知网络拓扑的重叠网络时，所出现的节点在重叠网络 分布不均衡现象会使p e e r - t o _ p e e r 网络性能减弱，同时p e e r t o - p e e r 系统会产生局 部热点。 本课题主要的研究目标就是，研究设计一个感知网络拓扑结构的p e e r - t o - p e e r 重叠网络，同时设计一个有效的算法解决其中所产生的重叠网络不均衡现 象。 一3 第2 章对等网络简介 第2 章对等网络简介 互联网发展一日千里，就如m o o r e 定律揭示的c p u 速度每1 8 月翻一倍，数 据存储容量每1 2 月翻一倍，使用的带宽每9 月翻倍。高速联网的计算机已经进 入了平常百姓家。以前只有少数单位和网站才能拥有高性能高带宽高存储计算 机，所以，只有小部分计算机才是信息的提供者，大多数计算机都只是信息的 使用者。由此产生了客户端服务器( c l i e n t s e r v e r ) 服务架构( 图2 1 ) 。而按 照m o o r e 规律快速发展的计算机技术，高性能计算机成为大众产品。但是这种旧 有客户端服务器( c l i e n t s e r v e r ) 服务模式，却严重制约了信息的产生，信息 的共享。计算能力的平等，从而，就有对信息处理的平等的需求，所以那种集 中式的客户端服务器( c l i e n t s e r v e r ) 服务架构，已经不能再适合于现在的硬 件规模。计算能力的平等，呼唤服务架构的平等。对等的服务体系，对等计算 ( p e e r t o - p e e r ) 技术出现在人们的视野。 2 1p 2 p 简介 p 2 p 技术，也称为对等网络( p e e rt op e e r ) 技术( 图2 2 ) ，这是一 种网络结构的思想。它与目前网络中占据主导地位的客户端服务器 ( c l i e n t s e r v e r ) 结构( 也就是w w w 所采用的结构方式) 的一个本质区别 是，整个网络结构中不存在中心节点( 或中心服务器) 。在p 2 p 结构中，每一 个节点( d e e r ) 大都同时具有信息消费者、信息提供者和信息通讯三方面的功 能。在p 2 p 网络中每一个节点所拥有的权利和义务都是对等的【1 吼 让p 2 p 思想深入人心的是美国的n a p s t e r 公司。这个公司成立于1 9 9 9 年， 它提供的服务是让网民们交流m p 3 文件。但是，在n a p s t e r 的服务器上没有 一首歌曲，它只是提供了一个软件，利用这个软件音乐迷可以在自己的硬 盘上共享音乐文件，搜索和下载其他使用了n a p s t e r 服务的用户共享的音乐文 件。n a p s t e r 在短时间里吸引了几千万用户。最终，它被五大唱片商以侵犯版权 的罪名告上法庭。但是，n a p s t e r 的技术，让人们看到了p 2 p 思想在互联网上应 用的巨大潜力。 5 北京工业大学工学硕士学位论文 图2 1 客户机服务器架构 f i g u r e 2 1c 1 i e n t s e r v e rs t r u c t u r e 图2 - 2 对等网络架构 f i g u r e 二2p c c r t o p e e rs t r u c t u r c 一6 第2 章对等网络简介 网络上现有的许多服务也可以归入p 2 p 的行列，例如即时通信系统 如i c q 、m s nm e s s e n g e r 以及o i c q 等都是很流行的p 2 p 应用。风靡一时的b t 下 载工具，更是一种典型的p 2 p 技术应用。但是，无论是n a p s t e r 、b t 还是即时通 信，都不是p 2 p 应用的全部。它们只是从不同的侧面反映了p 2 p 的潜力。 互联网技术过去的发展轨迹向我们昭示着，p 2 p 这一新的网络技术思想， 最终也会对网络中的传播形态、传播模式、信息流向、信息内容结构及传播控 制等产生重要的影响。 从某种意义来说，p 2 p 计算可以说是一种向传统互联网技术的回归，体现 了互联网的本质，因为互联网最初的设计居标就是让网络上的计算机互相之间 可以直接通信而不需要中介。 2 2p 2 p 架构特点 2 2 1分散化( d e c e n t r a l i z a t i o n ) 网络中的资源和服务分散在所有节点上，信息的传输和服务的实现都直接 在节点之间进行，可以无需中间环节和服务器的介入，避免了可能的瓶颈。 即使是在混合p 2 p ( 服务器客户端模式和对等计算模式的混合) 中，虽 然在查找资源、定位服务或安全检验等环节需要集中式服务器的参与，但主要 的信息交换最终仍然在节点中间直接完成。这样就大大降低了对集中式服务器 的资源和性能要求。 分散化是p 2 p 的基本特点，由此带来了其在可扩展性、健壮性等方面的优 势。 2 2 2可扩展性( s c a l a b i l i t y ) 在传统的c s 架构中，系统能够容纳的用户数量和提供服务的能力主要受服 务器和带宽的资源限制。为支持互联网上的大量用户，需要在服务器端使用大 量高性能的计算机，铺设大带宽的网络。为此机群、c l u s t e r 等技术纷纷上阵。 在此结构下，集中式服务器之间的同步、协同等处理产生了大量的开销，限制 了系统规模的扩展。 7 北京工业大学工学硕士学位论文 而在p 2 p 网络中，用户在使用服务，同时也在提供服务，随着用户的加 入，不仅服务的需求增加了，系统整体的资源和服务能力也在同步地扩充，始 终能较容易地满足用户的需要。即使在诸如n a p s t e r 等混合型架构中，由于大部 分处理直接在节点之间进行，大大减少了对服务器的依赖，因而能够方便地扩 展到数百万个以上的用户。面对于纯p 2 p 来说，整个体系是全分布的，不存在 瓶颈。理论上其可扩展性几乎可以认为是无限的。 2 2 3 健壮性( r e h a b i l 时) 在互联网上随时可能出现异常情况，网络中断、网络拥塞、节点失效等各 种异常事件都会给系统的稳定性和服务持续性带来影响。在传统的集中式服务 模式中，集中式服务器成为整个系统的关键点所在，一旦发生异常就会影响到 所有用户的使用。 而p 2 p 架构则天生具有耐攻击、高容错的优点。由于服务是分散在各个节 点之间进行的，p 2 p 架构还可以在p e e r 之间相互备份，p 2 p 架构还可以在按照地 理位置来分布( d i s t r i b u t e ) 资源，部分节点或网络遭到破坏对其它部分的影响 很小。而且p 2 p 模型一般在部分节点失效时能够自动调整整体拓扑，保持其它 节点的连通性。事实上，p 2 p 网络通常都是以自组织的方式建立起来的，并允 许节点自由地加入和离开。一些p 2 p 模型还能够根据网络带宽、节点数、负载 等变化不断地做自适应式的调整。 2 2 4易管理性( e a s eo fa d m i n i s t r a t i o n ) 在p 2 p 架构中每个p e e r 都是自组织，自适应的个体，所以不需要配置服务器 去管理p 2 p 软件。同时在p 2 p 架构中，可以加入容错处理，相互备份和负载均衡 等机制，那样p 2 p 就成为一个自管理的高可用系统。 2 2 5 隐私性( a n o i l y m i t y ) 随着互联网的普及和计算存储能力飞速增长，收集隐私信息正在变得越 来越容易。隐私的保护作为网络安全性的一个方面越来越被大家所关注。目前 的i n t e m e t 通用协议不支持隐藏通信端地址的功能。攻击者可以监控用户的流 8 一 第2 苹对等网络简介 量特征，获得i p 地址。甚至可以使用一些跟踪软件直接从i p 地址追踪到个人用 户。在传统的c s 架构中，因为存在一个中心服务器，所以服务器就是破坏隐私 的一个隐患。 在p 2 p 网络中，由于信息的传输分散在各节点之间进行而无需经过某个 集中环节，用户的隐私信息被窃听和泄漏的可能性大大缩小。此外，目前解 决i n t e m e t 隐私问题主要采用中继转发的技术方法，从而将通信的参与者隐藏在 众多的网络实体之中。在传统的一些匿名通信系统中，实现这一机制依赖于某 些中继服务器节点。而在f r e e n e t 中，所有参与者都可以提供中继转发的功能， 因而大大提高了匿名通讯的灵活性和可靠性，能够为用户提供更好的隐私保 护。 2 2 ，6 高性能 性能优势是p 2 p 被广泛关注的一个重要原因。随着硬件技术的发展，个人 计算机的计算和存储能力以及网络带宽等性能依照摩尔定理高速增长，而在目 前的互联网上，这些普通用户拥有的节点只是以客户机的方式连接到网络中， 仅仅作为信息和服务的消费者，游离于互联网的边缘。对于这些边际节点的能 力来说，存在极大的浪费。 采用p 2 p 架构可以有效地利用互联网中散布的大量普通节点，将计算任务 或存储资料分布到所有节点上。利用其中闲置的计算能力或存储空间，达到高 性能计算和海量存储的目的。这与当前高性能计算机中普遍采用的分布式计算 的思想是一致的。但通过利用网络中的大量空闲资源，可以用更低的成本提供 更高的计算和存储能力。 2 3p 2 p 应用领域 目前人们从很多不同的角度来应用p 2 p 计算技术，主要应用的角度包括： 信息资源共享、普及计算、协同工作、实时通信技术、信息检索技术、广域网 络存储系统等。下面将从上述这几个角度对p 2 p 计算技术的应用领域分别进行 介绍。 一9 。 北京工业大学工学硕士学位论文 2 3 1 信息资源共享( f i l es h a r i n g ) 信息资源共享一直是网络技术发展的重要推动力，也是p 2 p 技术中最典型 的应用。目前人们主要采用w e b 技术来实现信息资源共享，在基于w e b 的方 式进行信息资源共享时，w 曲s e r v e r 需要能够对大量用户的访问提供有效的服 务，w 曲s e r v e r 经常成为这类系统的性能瓶颈所在。n a p s t e r 是提供给用户在互 联网上共享m p 3 音乐文件的p 2 p 应用，与传统的音乐共享技术不同的是n a p s t e r 把音乐文件存储在客户节点上而不是存储在服务器节点上，中心服务器上存储 的仅仅是文件的索引信息，用户之间可以直接共享、传输音乐文件而不需要通 过中心索引服务器。采用这种方式来共享信息资源可以更加充分的利用网络中 的带宽资源，从而提高了系统数据通信的效率。目前有很多研究项目都是针 对p 2 p 的文件共享的，包括g n u t e l l a 吼b i t t o r r e n t1 4 l 等，这些研究项目均从不 同的角度尝试解决目前网络中的信息资源共享所存在的一些问题。 2 3 ，2 对等网络计算( p e e r - t o - p e e rc o m p u t i n g ) 对等计算技术研究的是如何充分利用网络中各种各样的计算单元来共同完 成大规模的计算任务。由于单一计算单元的计算能力总是有限的，因此人们一 般采用并行技术、分布式技术将多个计算单元节点联合起来共同完成大规模的 计算任务，同时目前网络中的计算机的计算能力一直没有被充分利用，人们期 望能够充分利用网络中的闲散计算能力来完成大规模的计算任务，这样将会使 得网络中所蕴含的海量计算能力得到更加充分的利用。p 2 p 计算技术则为普及 计算技术的发展提供了新的机遇。s e t i h o m e 【9 j 是美国b e r k e l e y 大学启动的普 及计算的研究项目，目前大约吸引了一百万台计算机参与研究。该项目是利用 该大学的空间科学实验室开发的屏幕保护程序来使用计算机的空闲机时，该屏 幕保护程序在运行时分析在外星系文明研究项目中所获得的无线电信号。程序 运行节点从中心服务器节点下载数据后进行计算，然后再将计算结果上载到该 实验室的中心服务器上，因为不是完全的p 2 p 计算模式，所以节点之间不能直 接利用彼此计算的数据。普及计算可以帮助企业完成大规模的数据处理，参与 计算的计算机之间可以直接共享计算中的中间结果。通过整合这些以前尚未使 1 0 第2 章对等网络简介 用的闲散计算能力和资源可以将企业的计算能力相比以前得到很大的提升，同 时因为利用了多个节点上的计算能力使得计算任务可以高效廉价的完成。 2 3 3协同工作( c 0 1 l a b o r a t i o n ) 协同工作是指多个用户之间利用网络中的协同计算平台互相协同来共同 完成计算任务，共享信息资源等，计算机支持的协同工作c s c w ( c o m p u t e r s u p p q r t e dc o l l a b o r a t i v ew o r k ) 是协同工作的典型研究方向之一。通过采用p 2 p 计算技术个人和组织可以随时采用各种方式建立在线、非在线的协同应用环 境。例如目前许多企业都使用协同工具来完成公司内部员工之间的通信。但是 传统的协同应用平台一般都是采用电子邮件方式来完成工作人员之间的协同工 作，而并不能很好的完成企业与合作伙伴、客户、供应商之间的沟通与交流。 下一代的p 2 p 解决方案试图要很好的解决这些问题，通过使用各种形式的个人 对个人，不存在中心服务器的协同工具提供给企业一个包含项目管理等功能的 协同应用平台。协同工作使得在不同地点的参与者可以在一起工作，采用文件 直接共享的方式可以保证系统中的每个人所获得的信息总是最新的，同时节省 了采用单点服务器时对该服务器存储以及性能的要求。一般的协同应用包括： 实时通信、聊天室、好友列表、文件共享、语音通讯等基本的功能，除了这些 基本的功能，用户之间还可以共享白板，协同写作进行视频会议等。由于协同 应用的用户数量一般都比较大，数据量也比较多，采用传统的单一中心节点服 务方式很难满足这种应用，如果采用p 2 p 的计算方式可以不再需要目前协同工 作中的中心服务器，参与协同工作的两台计算机可以直接建立联系进行协同工 作。g r 0 0 v e1 1 0 】是基于i n t e m e t 的p 2 p 协同应用软件的典型代表，其用户可以直接 进行实时的协同工作。 2 3 4 实时通信技术( i n s t a n tm e s s a g i n g ) 实时通信技术是网络中重要的通信技术，成功的实时通信技术吸引了数以 万计的在线用户。目前的实时通信技术一般也采用一个中心服务器控制着用户 的认证等基本信息，节点之间直接进行数据通信。i c q 、q q 、a i m 等是典型的 实时通信系统，这些系统也包含好友列表等基本功能。j a b b e r 1 l 】是一个开放源 北京工业大学工学硕士学位论文 码的实时通信平台，j a b b e r 提出了一个采用x m l 表示的在不兼容的各种实时通 信平台之间进行消息交换的协议。 2 3 5广域网络存储系统( g 1 0 b a l 丘l es y s t e m ) 存储技术一直是人们所关注的一项技术，s a n 、n a s 是目前广泛应用于 局域网络的存储技术。分布式文件系统也是j 1 泛使用着的分布式文件存储技 术，典型的分布式文件包括n f s 、a f s 、c o d a 等。由于网络规模的扩大，以 及p 2 p 网络架构的特点，人们对网络的使用也变得十分灵活，人们开始将传统 的分布式操作系统、局域存储技术向基于i n t e r n e t 的文件存储系统发展。一些 研究项目开始使用p 2 p 技术来组织和存储文件，典型的系统包括：o c e a n s t o r e 【1 2 】、c f s 【1 ：i 】，p a s t 【1 4 1 等，这些项目的目标都是提供面向全球规模的文件存储 服务。 2 3 6开发平台( p l a t f o r m s ) 除了前面介绍的p 2 p 计算技术的几个典型的应用领域，许多公司也从其它 不同角度来应用该技术。n e tm ys e r v i c e 技术是微软公司提出并正在开发的一 个基于i n t e m e t 的操作系统，该技术是围绕着以s o a px m l 通信协议的w e b 服 务为主。j x t a1 1 5 】是s u n 公司提出的一个p 2 p 的网络底层支撑平台，该平台的 目标是允许用户在其上开发各种p 2 p 应用。 我们可以根据p 2 p 系统对互联网资源( 计算，存储，通信) 利用的侧重点 不同，对已有的分类进行一次重新排列【1 6 1 。图2 3 中按照对计算资源利用的重 点将对等计算应用分类。其中开发平台( p l a t f o r m 8 ) 充分利用互联网资源的各 个因素。 2 4 本章小结 p e e r _ t o - p e e r 技术是一种互联网新的服务模式，具有很多适合互联网络的功 能特点，同时也在互联网中得到了广阔的应用。 1 2 - 第2 章对等网络简介 喘篓黜矾 图2 3 对等网络应用分类 f i g u r e2 3c l a s s m c a t i o no fp 2 ps y s t e m s 本章，我们介绍了什么是p e e r - t 0 _ p e e r 技术，以及p e e r t o _ p e e r 架构特点 和p e e r - t o - p e e r 主要的应用领域。 1 3 薹：耋墼篁里丝堡堡 第3 章对等网络架构 根据不同的定位，1 0 0 k u p ) 算法，我们可以将对等网络( p 2 pn e t w o r k ) 分为两种类型。非结构型( u n s t r u c t u r e d ) 和结构型( s t r u c t u r e d ) 。 3 1 资源定位 p 2 p 网络中进行资源定位是首先要解决的问题。一般采用三种方式： 集中索引方式：将资源信息存储在服务器上，通过服务器来实现资源定 位。 广播方式：将资源信息存储在本机，通过向相邻节点直接广播来实现资源 定位。 分布式哈希表的方式 分布式哈希表( d i s t r i b u t e dh a s ht 扎l e ，d h t ) 是 大多数p 2 p 网络所采取的资源定位方式。首先将网络中的每一个节点分配 虚拟地址( d ) ，同时用一个关键字( k e y ) 来表示其可提供的共享内 容。取一个哈希函数，这个函数可以将k e y 转换成一个哈希值h ( k e y ) 。 网络中节点相邻的定义是哈希值相邻。发布信息的时候就把( k e y ， v i d ) 二元组发布到具有和h ( k e y ) 相近地址的节点上去，其中d 指出 了文档的存储位置。资源定位的时候，就可以快速根据h ( k e y ) 到逻辑 相邻的节点上获取二元组( k e y ，v i d ) ，从而获得文档的存储位置。不 同的d h t 算法决定了p 2 p 网络的逻辑拓扑，比如g a n 就是一个n 维向量空 间，而c h o r d 是一个环形拓扑，t a p e s t r y 则是一个网状的拓扑。 上述的资源定位方式可以依据不同的p 2 p 应用环境进行选择，但是人们普遍看 好d h t 方法。基于d h t 的p 2 p 网络在一定程度上可以直接实现内容的定位。一 个矛盾的问题是：如果一个节点提供共享的内容表示越复杂，则哈希函数越不 好选择，相应地，网络的拓扑结构就越复杂。而如果内容表示简单，则又达不 到真正实现依据内容定位的能力。目前大多数d h t 方式的p 2 p 网络对节点所提 供共享内容的表示都很简单，一般仅仅为文件名。 供共享内容的表示都很简单，一般仅仅为文件名。 一】5 一 北京工业大学工学硕士学位论文 在上述三种资源定位方式中，集中索引方式和广播方式是属于非结构型对 等网，而分布式哈希表资源定位方式，是属于结构型对等网。 3 2非结构型( u n s t r u c t u r e d ) 集中索引方式( c e n t r a 】i z e dd i r e c o r ym o d e l ) ：在这种方式下每一个节点将自 身能够提供共享的内容注册到一个或几个集中式的目录服务器中。查找资源时 首先通过服务器定位，然后两个节点之间再直接通讯。例如早期的n a p s t e r 。 这类网络实现简单，但往往需要大的目录服务器的支持，并且系统的健壮性不 好，存在关键错误点。n a p s t e r 主要用于m p 3 文件共享，n a p s t e r 采用了集中式 的目录服务器机制，目录服务器集中存放对等节点的地址信息和所保存数据的 信息。这种集中式的目录服务器可以对请求的数据进行快速查找并能够返回最 合适的目的节点。实际的文件传输将在请求节点和目的节点之间通过t c p 连接 直接进行。每个n a p s t e r 节点登陆网络时连接n a p s t e r 服务器，登记所要共享的 资料。而搜索资源请求( r e q u e s t ) 提交给n a p s t e 胡务器，n a p s t e r 服务器返回 搜索结果给搜索者，其中搜索结果包括满足搜索要求的节点i p 地址。搜索者再 直接从该i p 地址去下载资源。图3 - l 说明了n a p s t e r 集中索引方式的资源定位方 法。 广播方式( f 1 0 0 d e dr e q u e s t sm o d e l ) ：在这种方式下，对等网络节点中没有 任何索引信息，资源的存储和资源定位都通过相邻接节点直接广播进行传 递。例如g n u t e l l a 。一般情况下，采取这种方式的p 2 p 网络对参与节点的带宽 要求比较高。和n a p s t e r 不样，g n u t e l l a 采用了完全分布式的策略。广播方式 的p 2 p 结构是纯粹的，没有任何中间服务器的p 2 p 模式。一个节点的所有定位 请求都是以广播的方式直接的传递给与这个节点直接相邻的节点。下一个节点 也广播传递该定位请求，直到找到查找的信息或者达到最大广播步数。图 3 2 说明了g n u t e l l a 广播方式的资源定位方法。 1 6 第3 章对等网络架构 图3 - 1 集中索引n a p s t e r f 培u r e3 1c e n t r a li n d e xn a p s t e r 图3 2 广播方式g m l t e l l a f i g u r e3 _ 2f l o o ( n n gg n u t e l l a 1 7 北京工业大学工学硕士学位论文 3 3 结构型( s t r u c t u r e dp 2 p ) 节点按照一定规则的相互连接形成一个应用层的覆盖图。而且这个应用 层覆盖图提供个登记查询获取数据的分布式h a s h 表。例如c h o r d ，c a n f 1 目。结构型p 2 p 是第二代p 2 p 体系结构网络。和非结构的p 2 p 架构相比，结构 型的p 2 p 架构具有自组织性，提供了负载均衡和容错处理，具有可扩展性。结 构p 2 p 架构和非结构p 2 p 架构相比，主要的不同是：结构p 2 p 架构是基于分布 式h a s h 表( d i s t r i b u t e dh a s h ，工a b l e ) 【1 9 1 【2 0 | 。 分布式h a s h 表是h a s h 表的分布式版本。h a s h 表存储( k e y ，v a l u e ) 数据 对，然后通过k e y 来定位存储位置。分布式h a s h 将( k e y ，v a l u e ) 分散存储在每 个节点，通过k e y 来定位每个节点。来完成i n s e r t l o o k u p d e l e t e 操作。 d h t ( d i s t r i b u t e dh a s ht a b l e ) 提供通用的程序设计接口f 2 1 j ( 2 2 l ( 2 3 j 1 2 4 】。该接口提供了两个函数，p u t 函数和g e t 函数。p u t ( k e y ，v a l u e ) 存储 ( k e y ，v a l u e ) 到对应于k e y 的节点。v a l u e = g e t ( k e y ) 通过k e y 从网络中找到 对应节点，并取得与k e y 相关联的v m u e 值。 3 4 分布式散列表实现( i m p l e m e n t a t i o no fd i s t r i b u t e dh a s ht a - b l e ) 分布式散列表只提供一个通用的程序设计接口。而具体的实现就可以 有很多种不同的选择。比如c h o r dm i t 】，p a s t r y m i c r 0 8 0 f tr e s e ”c hu k ， m c eu n i v e r s i t y 】，c o n t e n ta d d r e s s a b i en e t w o r k ( c a n ) 【u cb e r k e l e y j ，t a p e s t r y 1 2 6 】。同时这些系统也被归为p 2 p 底层路由结构和p 2 p 上层覆盖网络矧。 3 4 1c h o r d c h o r d 【1 1 通过使用c o n s i 8 t e n th a s h i n g 矧来分布k 净到对应的节点，从而提 供分布式的快速h a s h 功能。 c o 璐j s t e n th a s h j n g 具有很多优点，c o n s i s t e n th a s h i n g 从概率意义提供 的h a s h 函数的负载均衡，即所有节点从概率意义上接收相同个数 1 8 - 第3 章对等网络架构 n 1 图3 3c h o r d i d 空间 f i g u r e3 3c h o r d i dc i r c l e 的k e y 。同时当第n 个节点加入或者离开网络时c o n s i s t e n th a s h i l l g 只需要改 变o ( 1 n ) k e y 的位置。c h o r d 改进了c o n s i s t e n th a s h i n g 的可扩展性，这是因 为c h o r d 中的每个节点只要保存很少的几个路由节点信息，而不是每个节点都 需要保持所有其他节点信息。因为所有信息都是分散存储，所阻一个节点要使 用h a s h 函数就要和几个其它节点通讯。在一个n 节点的c h o r d 网络，每个节点只 要保存o ( 1 0 9 n ) 其它节点的信息，而且同时每次查询只需要o ( 1 0 9 n ) 个消息。 c o n s i s t e n th a s h i n g 使用基础的h a s h 函数例如s h a 1 ，给每个节点和k e y 赋 予m 位的标识符。每个节点的i d 是通过对其i p 地址来取得，而k e y 的标识符通过 散列其k e y 值来获得。从以上机制可知，标识符的长度m 必须足够大，从而使节 点或者k e y 的标识符相撞的概率足够小。 i d 按照次序形成一个模为2 m 的i d 圈，而k e y 存储在i d 圈顺时针的临近的第 一个节点，同时这个节点也成为k e v 的后继节点，标记为s u c c e s s o r ( k ) 。 首先让我们考虑最简单的情况，假设每个结点都知道整个网络中的结点和 关键字的信息，也就是说，每个结点都维护0 ( ) 大小的路由表。当网络规模很 一1 9 北京工业大学工学硕士学位论文 n 1 n 3 2 图3 4c h o r d 路由表 f i g u r e3 4c h o r df 培u r et a b l e 大时，这种策略是不可行的。当然，这种策略的优点也很明显，它只需要进行 一次路由表查找就可以找到关键字所在的结点。 再看图3 3 中的方案。图中每个结点只知道其后继结点的信息。这样当进行 查找时，结点将依次查询其后继结点，直到找到关键字或者遍历完整个网络为 止。这种方式的优点是可扩展性好，每个结点需要知道的信息很少，缺点是查 询速度比较慢，为0 ( ) 数量级，当网络规模很大时，这样的速度是不能接受 的。 c h o r d 采用了上述两种方案的折衷方案。在c h o r d 中，每个结点维护少量 的路由信息，通过这些路由信息，可