硕士论文-一种新型的基于P2P网络的混合组播树的流媒体直播模.pdf

复旦大学 硕士学位论文 一种新型的基于P2P网络的混合组播树的流媒体直播模型研究 姓名：林庆 申请学位级别：硕士 专业：计算机应用 指导教师：李松年 20070516 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名 论文使用授权声明 日期：! ! 望 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名导师签名：嘲巫7 复旦人学颀士学位论文 摘要 本文主要研究了基于P 2 P 网络建立混合的应用层多播树森林用于实现大规模 用户的流媒体直播的问题。而传统的基于组播树的应用解决方案对于在网络上各 节点合作的情况下流媒体应用有着天生的弊端。原因是对于传统的解决方案，每 一棵组播树的大量的复制和转发负载都集中于很少的一部分中间节点，而大量叶 子节点只能被动的接受数据从而浪费了大量的网络资源。 本文首先对流媒体直播应用的相关现状作了分析，并且简要介绍了P 2 P 网络 及流媒体直播的关键技术，同时在第三章分析了目前几个成熟的应用层组播协议 为第四章作者提出自己的新型基于P 2 P 网络的混合组播树流媒体直播模型作了 理论准备。 本文通过设计一种新的基于P 2 P 网络的混合组播树的流媒体模型，物理层采 用P a s t r y 的拓扑结构，自动发现与增加节点，中间层采用成熟的S c r i b e 协议管 理单棵组播树。作者通过在每个单独的组播树的根节点加入管理本组播树节点信 息表，并且与S e r v e r 动态交换信息，达到了既减轻S e r v e r 负载，又利用已有的 成熟的应用层组播树协议，从而保证整个系统的实用性和鲁棒性。作者打破原有 模型大量叶子节点只能成为组播树底端被动接收数据，而不能主动参与到转发过 程中从而浪费了大量可用资源的弊端，通过共享不同的组播树，并且与M D C 编码 结合起来，即某个节点在某个组播树中既是中间节点，参与某一道编码流的复制 与转发，在其他的组播树中又是叶子节点，接收剩余的数据流。 本文的提出的模型不是对原有c s 体系的替代，而是一种补充，充分利用P 2 P 资源共享及自治的理念减轻服务器的负担又保持了传统c s 结构易于管理的特 点。通过合理地使用用户计算机空闲的资源提供部分服务，使得整个系统的能力 得到极大的提高。 关键词：P 2 P ，应用层组播树，S c r i b e ，流媒体直播，M M T 复日| 大学硕士学位论文 A b s t r a c t T h i s p a p e rm a i n l yi n t r o d u c e s t h er e a l i z a t i o n o fl i v i n gs t r e a mm e d i af o r l a r g e s c a l e du s e r st h a tr e s u l t e df r o mm i x e da p p l i c a t i o n l e v e lm u l t i c a s tt r e eb a s e do n P 2 Pn e t w o r k F o rs t r e a mm e d i aa p p l i c a t i o nc o m b i n e dw i t hv a r i o u sc o o p e r a t i n gn o d e s o nt h en e t w o r k , t h et r a d i t i o n a la p p l i c a t i o ns o l u t i o nb a s e do nm u l t i c a s tt r e es h o w si t s i n h e r e n ts h o r t f a l l s T h er e a s o ni sd u et ot h et r a d i t i o n a ls o l u t i o n e v e r ym u l t i c a s tn s c o p ya n df o r w a r dl o a dh a v e b e e nf o c u s e do nf e w e ri n t e r i o rn o d e s T h u s ，t h em a j o r i t y o fp e e r sa r el e a fn o d e sc a no n l yr e c e i v ed a t ap a s s i v e l ya n dc o n t r i b u t en or e s o u r c e s F i r s t l y , t h i sp a p e rd o e st h ea n a l y s i so nr e l e v a n ts i t u a t i o nf o rs t r e a mm e d i al i v e b r o a d c a s t i n ga p p l i c a t i o na n di n t r o d u c e s t h ek e yt e c h n o l o g yf o rP 2 Pn e t w o r ka n d s t r e a mm e d i al i v eb r o a d c a s t i n gc o n c i s e l y , a sw e l l , i nC h a p t e r3 ，t h ea n a l y s i so fc u r r e n t s e v e r a lm a t u r ea p p l i c a t i o nl a y e rm u l t i c a s tp r o t o c o l sh a v ed ot h e o r yp r e p a r a t i v ew o r k f o ra n t h o t sn e wi d e ao fan e wl i v es t r e a mm o d e lr e s e a r c hb a s e do nP 2 Pn e t w o r ka n d m i x e dm u l t i c a s tt r e e I tm a n a g e st h es i n g l eb r o a d c a s t i n gt r e et h r o u g hd e s i g n i n gan e wm u l t i c a s tt r e e s t r e a mm e d i am o d e lb a s e do nP 2 P n e t w o r k , a d o p t i n g t h eP a s t r yt o p o l o g ys t r u c t u r eo n p h y s i c a ll a y e rt oa u t o m a t i c a l l yi n s p e c ta n di n c r e a s en o d e sa sw e l la st h em a m r e S c r i b e p r o t o c o lo nm i d d l el a y e r s I n s e r tt h em a n a g i n gg r o u pb r o a d c a s t i n gn o d ei n f o r m a t i o n s h e e t si n l 0t h er o o tn o d eo fe v e r ys i n g l eg r o u pb r o a d c a s t i n gt r e ea n de x c h a n g et h e i n f o r m a t i o nw i t hS e r v e rd y n a m i c a l l yc a nd e c r e a s et h eS e r v e rl o a dw h i l em a k eg o o d u s eo fc u r r e n tm a t l l r ea p p l i c a t i o n l a y e rm u l t i c a s tt r e ep r o t o c o l s ，s ot h a t , t h eo v e r a l l s y s t e mc 锄k e e pt h ep r a c t i c a b i l i t ya n dr o b u s t A u t h o rb r e a k st h ew a s t eo fm o s t a v a i l a b l er e s o u r c e ss h o r t f a l lt h a tt h em o s tl e a fn o d e si no l dm o d e lc a l lo n l yr e c e i v e d a t ap a s s i v e l yw i t h o u tt h ef u n c t i o no f p a r t i c i p a t i n ga c t i v e l yi nt h et r a n s f e r r i n gc o u r s e V i as h a r i n gd i f f e r e n tm u l t i c a s tt r e e sa n dc o m b i n e dw i t hM D Cc o d e s ，t h a ti s ，c e r t a i n n o d ei nc e r t a i nm u l t i c a s tt r e ei sa l s oc o n s i d e r e da si n t e r i o rn o d ef o rt a k i n gp a r ti n t o t h ec o p ya n df o r w a r dc o u r s eo fs o m ec o d es t r e a mw h i l ea tt h es a m et i m e ，i tf u n c t i o n s a tt h el e a fn o d e st oa l lo t h e rm u l t i c a s tt r e e sf o rr e c e i v i n gr e s td a t as t r e a m s 2 塞昱| 大兰堡主竺垡丝奎 T h em o d e lp r o p o s e di nt h i sp a p e ri sn o tt h es u b s t i t u t ef o rp r e v i o u sC Ss t r u c t u r e ， i ti st h ec o m p l e m e n tt h a tm a k e sf u l lu s eo fP 2 Pr e s o u r c es h a r i n ga n ds e l f - m a n a g i n g i d e at od e c r e a s et h el o a do fS e r v e rw h i l ek e e p st h et r a d i t i o n a lm e r i to f9 0 0 de a s i l y m a n a g e m e n tf o rC Ss t r u c t u r e T h eo v e r a l ls y s t e ma b i l i t yh a sb e e ng r e a t l yi m p r o v e d t h r o u g ha p p r o p r i a t e l ym a k i n gs p a r er M ) u r c c so fu s c rc o m p u t e rf o rs c P c i c cp r o v i d i n g p a r t l y K e y w o r d s ：p 2 p ，a p p l i c a t i o n - l e v e lm u l t i c a s tt r e e ，S c r i b e ，l i v es t r e a m i n g , M M T 3 复旦大学硕士学位论文 第一章绪论 1 1 课题研究的背景及面临的挑战 随着I n t e r n e t 在全世界范围内的迅速普及和发展，人们希望互联网不仅仅 只提供网页浏览、文件下载等等简单业务，并且能提供“边下载边播放视、音频 等信息”，这种“边下载边播放”的应用就是大家所熟知的流媒体应用。近几年 来，P P L i v e ，P P S t r e a m ，C o o l S t r e a m 这样的网络电视软件在网络中的空前盛行， 引发了人们对流媒体新技术的极大关注。剖析这些软件所采用的技术，发现它们 有一个共同的特征，都是基于P 2 P 技术的流媒体直播软件，能够为宽带用户提供 稳定和流畅的视频直播节目。可见，P 2 P 流媒体技术的引进创造了一种全新的商 业模式，在互联网的世界引入了一场风暴。 对比于传统的集中式的c s 模型，P 2 P 流媒体不依靠于一个强大的中央服务 器向所有的客户端提供服务，相反的，分布式的流媒体应用要求所有参与节点的 共同合作。每一个参与的节点都需要负责转发流媒体数据到其它节点。不同于 P 2 P 文件共享，P 2 P 流媒体服务对实时性有着天生的要求。 P 2 P ( P e e r t o P e e r ) 是一种网络模型，即对等网络，可以简单地定义为通过 直接交换共享计算机资源和服务，对等计算机兼有客户机和服务器的功能。在这 种网络中所有的节点是对等的( 称为对等点) ，各节点具有相同的责任与能力并协 同完成任务。对等点之间通过直接互连实现信息资源、处理器资源、存储资源甚 至高速缓存资源等的全面共享，无需依赖集中式服务器支持，消除信息孤岛和资 源孤岛。 P 2 P 模式的流媒体服务技术是相对于目前客户端服务器( c s ) 结构的流媒体 服务技术而言的。传统的流媒体系统结构仍然是c s 模式，其流媒体服务器实体 可以是一个服务器、一组服务器、一个服务器和缓存或者一组服务器和代理。服 务器以单播的方式和每个客户建立连接，负责为所有客户提供请求的媒体文件。 由于流媒体服务具有高带宽、持续时间长等特点，随着客户数目的快速增加，服 务器的资源，如带宽、内存大小很快就会被消耗完，成为系统瓶颈所在，导致系 统的可扩展性极差。为了解决系统的可扩展性问题，许多研究都提出了相应的解 4 复旦大学顾上学位论文 决办法。如I P 组播技术，它实现了I n t e r n e t 上高效的一对多通信，提高了系统 的可扩展性。但由于I P 组播也存在种种限制，并没有取得预期的成功。一方面， 因特网中的网络极少开放I P 组播业务，至今还没有大范围内的因特网组播业务； 另一方面，基于I P 组播的上层应用也屈指可数，相对于硎w 等新的体系结构， I P 组播的发展非常缓慢。另一种解决系统可扩展性方案是在网络边缘部署代理 缓存( P r o x yC a c h i n g ) 或内容分发网络( C D N C o n t e n tD e l i v e r yN e t w o r k s ) ，媒 体服务器将媒体内容以推( P u s h ) 的方式存放在代理缓存或C D N 服务器上，客户请 求媒体服务器时，可从代理缓存或C D N 服务器获得服务，而不必消耗服务器的资 源。但这种方案只是部分地解决了可扩展性问题，因为此时代理缓存或C D N 服务 器很有可能成为系统瓶颈。 采用P 2 P 模式的流媒体服务系统能较好地解决以上存在的种种问题，它并不 改变现有的流媒体传输协议和流媒体服务器系统的架构，只是在现有系统的基础 上，改变传统模式下的服务方式和数据传输路径，就能实现系统的可扩展性、可 靠性，为流媒体技术提供了未来的发展方向。 文本提出的M M T 模型，并不是完全取代传统的c s 结构的流媒体直播模型， 在其中仍然需要重要服务器提供流媒体源以及对整个系统的拓扑进行一定的管 理。本文所作的工作，只是尽量减低中央服务器的负担，并且让所有的节点都参 与到流媒体内容的复制与转发当中去，从而提高整个流媒体直播系统的效率。 1 2 相关研究现状 P 2 P 作为一种应用技术是上世纪9 0 年代末提出的，它能利用I n t e r n e t 中的 各个节点进行对等计算，充分挖掘了I n t e r n e t 上空闲资源，在利用率、扩展性、 容错等方面具有潜在的巨大优势，并在文件共享、分布式计算、协同工作、 I n t e r n e t 存储等方面己经取得了初步的良好应用。 由于P 2 P 技术蕴涵着巨大的技术潜力和商业价值，国内外许多科研机构、大 公司致身投入到P 2 P 网络的研究中。从国外公司对P 2 P 计算的支持力度上看， M i c r o s o f t 公司、S u n 公司和I n t e l 公司投入较大 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 的软件包 5 复旦大学颀士学位论文 S i m P a s t r y v is P a s t r y 。 I n t e l 公司一直都是P 2 P 技术的鼓吹者。在2 0 0 0 年8 月，I n t e l 公司宣布成 立P 2 P 工作组，正式开展P 2 P 的研究。工作组成立以后，积极与应用开发商合作， 开发P 2 P 应用平台。2 0 0 2 年I n t e l 发布了N e t 基础架构之上的A c c e l e r a t o rK i t ( P 2 P 加速工具包) 和P 2 P 安全A P I 软件包，从而使得微软N E T 开发人员能够迅速 地建立P 2 P 安全W e b 应用程序。 S u n 公司以J a v a 技术为背景，开展了J X T A 项目。J X T A 是基于J a v a 的开源 P 2 P 平台，任何个人和组织均可以加入该项目。因此，该项目不仅吸引了大批P 2 P 研究人员和开发人员，而且已经发布了基于J X T A 的即时聊天软件包。J X T A 定义 了一组核心业务：认证、资源发现和管理。在安全方面，J x T A 加入了加密软件 包，允许使用该加密包进行数据加密，从而保证消息的隐私、可认证性和完整性。 在J X T A 核心之上，还定义了包括内容管理、信息搜索以及服务管理在内的各种 其它可选J ) ( T A 服务。在核心服务和可选服务基础上，用户可以开发各种J X T A 平 台上的P 2 P 应用。 而将P 2 P 网络与流媒体直播系统联系起来，现有的流媒体直播系统主要采用 集中式P 2 P 架构，即中央服务器即是所有流媒体内容的源节点，又管理整个流媒 体直播系统的拓扑结构，包括节点的加入，离开以及管理。这极易成为系统瓶颈。 1 3 论文研究内容 本文的研究目标就是要在互联网上实现基于P 2 P 的混合组播树的流媒体直播 系统，P 2 P 模式的流媒体服务技术可以解决服务器自身资源的限制。通过合理地 使用用户计算机空闲的资源提供部分服务，使得整个系统的能力得到极大的提 高。 作者查阅了大量的文献资料，借鉴和比较目前网上流行的几种流媒体播放技 术以及P 2 P 网络中成熟的拓扑结构以及组播树管理协议，基于S c r i b e 协议以及 M D C 编码技术，提出了一种新型的基于P 2 P 网络的混合组播树的流媒体直播模型。 有效的综合传统C S 架构易于管理和P 2 P 网络资源共享的特点，使得系统中的每 个节点既是数据的接受者，也是数据的提供者。同时在健壮性、容错性和鲁棒性 上做了一定的研究。 复旦大学硕上学位论文 1 4 论文主要贡献 本文作者通过把现有的基于c s 的流媒体直播技术与P 2 P 网络结合起来，构 成了一个混合式的多组播树森林的流媒体直播模型，对现有c s 模型做了较小的 改动，保持了其易部署易管理的特点，又加入了P 2 P 网络的特性，使所有节点都 参与到流媒体数据的复制与转发当中去，大大减轻了中央服务器的负担。可以为 今后的相关研究者这提供一定的借鉴。 1 5 论文组织结构 本文是根据作者所做的工作进行组织安排的，具体组织方式如下： 第一章作者简单介绍了课题的研究背景、目的和意义，介绍了当前P 2 P 网络 和流媒体应用的研究现状以及作者的工作内容和论文的组织。 第二章主要是对当前P 2 P 网络及流媒体直播的相关技术进行了阐述，其中， 流媒体直播的相关技术包括媒体编码技术、视频服务器技术、媒体同步技术、流 媒体传输协议，而对P 2 P 网络的介绍则主要分为P 2 P 网络分类以其关键技术两方 面。 第三章主要是对现有几个主要的应用层组播协议进行了简要的分析，其中包 括S p r e a d l t 协议，N i c e 协议，Z I G Z A G 协议以及G o s s i p 协议。 第四章作者提出了一种新型的基于P 2 P 网络的混合组播树的流媒体直播模 型：M M T ，并且就其关键的模块进行了系统的阐述，包括基本架构，新节点的加 入与退出，数据传输同步管理等。 第五章是对新模型的分析以及与现有模型的比较。 最后一章是本文作者对所做的研究工作加以总结，并提出了下一步的研究方 向。 7 复旦人学硕l ：学位论文 第二章P 2 P 网络及流媒体直播的相关技术 2 1 概述 本章简单阐述了P 2 P 网络及流媒体直播的相关技术，包括P 2 P 网络的分类及 关键技术，流媒体直播的概念及相关媒体编码、媒体同步等技术。为作者在第四 章提出新模型的做了基本概念的铺垫。 2 2P 2 P 网络分类 P 2 P 网络属于叠加在底层通信网络基础设施之上的重叠网络，是一个分布式 的、具有互操作性的自组织系统。P 2 P 面临的最大的挑战之一是如何在没有中心 服务器的模式下维护网络拓扑结构，以及实现内容搜索。因此，根据网络拓扑组 织形式可以将P 2 P 网络分为四种类型：集中式P 2 P 网络、全分布非结构化P 2 P 网 络、全分布结构化P 2 P 网络( 也称作D H T 网络) 和混合式P 2 P 网络 2 。 2 2 1 集中式P 2 P 网络 以N a p s t e r 3 为代表的第一代P 2 P 系统采用集中式网络架构，要求各对等端 ( p e e r ) 都登录到中心服务器上，通过中心服务器保存并维护所有对等端的共享文 件目录信息。当某个用户需要某个文件时，首先连接到N a p s t e r 服务器，在服务 器进行检索，并由服务器返回存有该文件的用户信息；再由请求者直接连到文件 的所有者传输文件。N a p s t e r 首先实现了文件查询与文件传输的分离，有效地节 省了中央服务器的带宽消耗，减少了系统的文件传输延时。这种方式最大的隐患 在中央服务器上，如果该服务器失效，整个系统都会瘫痪。当用户数量增加N 1 0 5 或者更高时，N a p s t e r 的系统性能会大大下降。在N a p s t e r 之后的P 2 P 系统都在 这一点上进行了重点改进，系统基本上都采用无中心结构，鲁棒性和可扩展性都 得到大幅度提高。 8 复旦大学硕士学位论文 2 2 2 全分布式非结构化P 2 P 网络 第二代P 2 P 网络采用了随机图的组织方式，利用T T L ( T i m e - t o - L i v e ) ，洪泛 ( F l o o d i n g ) ，随机漫步或有选择转发等方式搜索网络资源。当结点度数服从幂率 ( p o w e r l a w ) 规律时，该方式同样能够较快发现月标结点，而且面对网络的动态 变化体现了较好的容错能力。代表性网络是G n u t e l l a 4 和F r e e n e t 5 。 G n u t e l l a 系统采用了基于完全随机图的洪泛( F l o o d i n g ) 发现和随机转发 ( R a n d o mW a l k e r ) 机制。为了控制搜索消息的传输，G n u t e l l a 通过T T L ( T i m eT o L i v e ) 的减值来实现。该系统既没有集中式服务器也不对网络拓扑结构或者文件 存储位置做硬性规定和强制管理。节点松散地加入网络并组织网络。在搜索时， 节点以洪泛的方式向自己的所有邻居节点发起查询，收到该查询消息的节点无论 是否拥有查询的文件都将查询消息继续转发给自己的所有邻居节点，直至查询消 息中的T T L ( T i m et oL i f e ) 属性值递减为0 为止。这种机制对节点的加入和离 开不敏感，当一部分节点离开网络时，网络并不会因此中断。随着联网节点的不 断增多，网络规模不断扩大，通过这种洪泛方式定位对等点的方法将造成网络流 量急剧增加，从而导致网络中部分低带宽节点因网络资源过载而失效。所以在初 期的G n u t e l l a 网络中，存在比较严重的分区、断链现象。也就是说，一个查询 访问只能在网络的很小一部分进行，因此网络的可扩展性不好。 F r e e n e t 是一个基于J a v a 的跨平台分布式文件存储系统。F r e e n e t 结点可以 通过指定本地的共享目录来共享自己的存储( 而不仅仅是共享文件或者对象) ，任 何其他结点都可以向这个共享目录中写入文件。每个文件都通过一个反映文件内 容的关键字( 并不要求全局唯一) 进行标识，关键字也可以包括访问权限等其他信 息。每个结点都使用一个最近最少使用的缓冲区保存本地存储文件的信息，使用 另一个最近最少使用缓冲区保存本地文件和某些远程文件的元数据信息。当结点 收到查找请求时，将使用元数据信息有效地把查找定位到最可能保存该文件的结 点。如果收到查找请求的结点在本地元数据中找不到任何匹配，它将把请求发送 到关键字比较接近于查找关键字的结点，这一过程将重复进行直到达到预先确定 传播层次数，如果仍然没有找到匹配则返回一个错误指示。如果找到了一个匹配， 请求的对象将按照查找路径返回( 这一点和G n u t e l l a 不同) 。在F r e e n e t 中，查 找路径中的每个结点都将缓存返回的文件数据以备将来使用。对象的插入过程和 9 复日1 人学顾士学位论文 查找过程类似，在本地插入一个对象之后，本地结点将向邻居结点传播该对象的 信息，直到达到事先确定的传播层次。 非结构化分布式P 2 P 网络存在以下缺点：查询消息占用大量带宽，花费时间 长；网络的规模扩展性差，随着网络规模的扩大，查询消息的数量急剧增加。因 此准确性和可扩展性是非结构化网络面临的两个重要问题。 2 2 3 全分布式结构化P 2 P 网络 结构化指的是P 2 P 网络叠加层的拓扑结构是严格控制的，资源并不是随机分 散存储在节点上，而是以一种使得查询更加高效的方式来存储的。网络中的共享 内容用关键字( K e y ) 来表示。通常使用分布式哈希表( D i s t r i b u t e dH a s hT a b l e D H T ) ，如S H A I 等，为节点和关键字各分配m 位的标识符，从而将存储数据的位 置信息相应地部署在确定的节点上。节点标识符( N o d e l D ) 可以通过哈希节点的 I P 地址产生，而关键字标识符可以哈希文件名或者文件内容来产生。标识符的 位数m 必须足够大，才能保证两个节点或者关键字被哈希到同一个标识符上的概 率可以忽略不计。通常由N o d e I D 与关键字标志符数值最接近的节点保存数据的 存储位置信息。每个节点维护一个很小的路由表，只存储邻居节点的N o d e l D 和 I P 地址。查询消息被节点步进式的转发给N o d e I D 与关键字标志符接近的节点。 为了在有限逻辑跳内查找定位资源，节点之间连接都是参考特定网络拓扑结构， 典型结构化对等网络代表有C h o r d 6 ，P a s t r y 7 ，T a p e s t r y 8 9 和C A N 1 0 等。 2 2 3 1C h o r d C h o r d 是一个使用环状标识空间的系统。针对一个标识的路由目标就是在数 值上最接近该标识的N o d e I D 的结点，并称为针对该标识的承接点。在C h o r d 中， 每一个结点都维护着两套邻居。其中一套为在标识空间中紧接着该结点的k 个结 点，另一套为指向在整个标识环中以该结点为基准依次折半的结点的指针。其中， 第一套邻居是确保路由正确的关键。C h o r d 可以确保路由在标识空间中单向靠近 目标结点而且不会越过，并且可以保证路由在O ( 1 0 9N ) 步内完成。 1 0 复旦大学硕士学位论文 2 2 3 2P a s t r y P a s t r y 是微软研究院提出的可扩展的分布式对象定位和路由的P 2 P 系统。在 P a s t r y 中，每一个结点都被分配了一个1 2 8 位的结点标识( N o d e I D ) ；用于确定 该结点在环状标识空间中的位置。每一个结点的结点标识是在结点加入系统时随 机分配的。新节点加入网络时，通过计算节点公钥或者对I P 地址进行H a s h 运算 获得节点I D 。节点I D 和关键字是以B 为基的数字( Bt 2 6 ) 。P a s t r y 的路由过程 如下；收到一条查询消息，节点首先检查要查询的关键字I D 是否落在叶子集合 中。如果是，则直接把消息转发给节点I D 和关键字I D 最接近的节点。如果没有， 就将根据路由表进行转发。在某些情况下，会出现路由表对应表项为空或者路由 表表项对应的节点不可到达的状况。这时候消息将会被转发给有着同等长度的匹 配前缀的节点，但是该节点的I D 和当前节点相比从数值上更接近关键字I D 。这 样的节点一定位于叶子集合中。因此，只要叶子集合中不出现一半以上的节点同 时失效的情况，路由过程就可以继续。在查找关键字时，节点将查询消息转发给 节点I D 与关键字至少比当前节点I D 多匹配1 个数位( b 个2 进制位) 前缀的节点。 在有a 个节点的网络中，查询一个关键字通常可以在l o g 。n 跳之内完成。 2 Z 3 3T a p e s t r y T a p e s t r y 的架构是基于P l a x t o n 的搜索定位和路由技术。P l a x t o n 等人提出 了一种分布式数据结构P l a x t o nm e s h 。这种结构中，关键字I D 、节点I D 和 它们的位置以及具体内容无关，通过s H A I 哈希运算来生成。s m 1 函数决定了 I D 在整个名字空间中均匀分布。每个节点采用本地路由映射，将路由消息采用 后缀匹配进位增加的方式转发给目标I D ，例如：料半7 = 料9 7 = * 2 9 7 = 3 2 9 7 ( “木” 是通配符) 。节点本地路由映射有多个等级，每个等级代表I D 后缀匹配度 ( ( S u f f i xm a t c h i n g ) 。当消息到达第i 个节点时，该节点至少匹配目标I D 的i 位后缀。要定位下一条路由时，第i + 1 级映射将计算出下一位应匹配的后缀数 字。这种路由机制保证任何查询都可以在l o g 。，l 跳内就能定位( n 为节点数，B 为 节点I D 长度) 。由于节点本地路由映射假定前面的数字完全匹配当前的节点后 缀，因此节点每一级映射只保存一个常量B 的映射表，整个路由映射表的大小是 1 1 复旦大学硕士学位论文 B x l o g 。栉。另一方面，在T a p e s t r y 网络中每一个数据对象都连接到多个根节点， 以避免单点失败问题。在P l a x t o n 网络中，如果数据对象存在多份拷贝，那么对 象的根结点只保存离它最近的那份拷贝的位置。与之不同，T a p e s t r y 则保存了 所有拷贝的位置信息以增加灵活性。这是P a s t r y 和T a p e s t r y 的主要不同之处。 T a p e s t r y ，P a s t r y 思想都继承自P l a x t o n ，两者在路由定位机制上都是基于标识 符的匹配进行路由，但对节点的加入和离去、路由表结构和维护上稍有区别。 2 2 3 4C A N ( C o n t e n t A d d r e s s a b l eN e t w o r k ) A 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 ) 项目采用多维的标识符 空间来实现分布式散列算法。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 节点都保存一张坐标路由表，其中包 括邻居节点的I P 地址和虚拟坐标区域。邻居节点是指两个节点的区域在d 维坐 标空间中的d - 1 维上具有相同的覆盖跨度而在另一维上相互邻接。C A N 采用的路 由算法相当直接和简单，知道目标点的坐标后，就将请求传给当前结点四邻中坐 标最接近目标点的结点。当新节点加入C A N 网络时，必须拥有自己的坐标空间。 C A N 拥有一个D N S 域名，该域名可以解析为一个或多个C A N 引导节点( 引导节点 始终维护一部分C A N 节点列表) 的I P 地址。当新节点加入C A N 时，首先通过域名 解析获得引导节点的地址，从引导节点处获得系统中一些节点的I P 地址，然后 新节点随机向一个节点发送J O I N 请求，之后获得该节点拥有的一半区域空间。 当节点任意离开C A N 网络时，接管算法保证了当节点发现邻居节点失效时，立即 接管那部分区域。系统中每个节点定期发送s o f t - s t a t e 消息，以通知邻居节点 自己的存在。C A N 是一个具有良好可扩展性的系统，给定N 个结点，系统维数为 d ，则路由路径长度为D b “4 ，每个结点维护的路由表信息和网络规模无关为 0 ( d ) 。 复旦大学硕士学位论文 2 2 4 混合式P 2 P 网络 混合式P 2 P 网络吸取了中心化结构和全分布式拓扑的优点，选择性能较高( 处 理、存储、带宽等方面性能) 的结点作为超级点( S u p e r N o d e ) ，在各个超级点上存 储了系统中其他部分结点的信息，发现算法仅在超级点之间转发，超级点再将查 询请求转发给适当的叶子结点。如图2 - 1 所示，混合式P 2 P 网络构成了一个层次 式结构，超级点之间构成一个高速转发层，可采用D H T 方式组织，超级点和所负 责的普通结点构成若干层次。混合式P 2 P 网络结合了集中式拓扑的易管理性与分 布式拓扑的可扩展性，在异构的P 2 P 网络环境下是一种较好的模式选择。其中最 典型的案例就是F a s t T r a c k 1 1 K a Z a h 1 2 。 P ：对等点 S ：超级对等点R ：中继代理 图2 - 1 典型混合式P 2 P 网络结构图 F a s t T r a c k 是非集中式的文件共享系统，支持元数据( m e t a - d a t a ) 搜索。但与 非结构化的完全分布式P 2 P 网络不同，会选取一些拥有较大带宽、磁盘空间和较 高处理能力的节点做为超级节点。超级节点会缓存元数据信息，提供搜索功能。 普通节点将其共享的数据文件的元数据发送给超级节点。查询时，所有节点都发 送查询信息到超级节点。而后，仅在超级节点之间使用洪泛方式来转发查询消息。 系统也可以在没有超级节点的情况下运行，但查询花费的时间将增大，这样的架 构提高了搜索效率。K a Z a h 是采用了F a s t T r a c k 协议的一个成功应用。2 0 0 3 年8 月3 0 日，K a Z a A 网络拥有4 5 百万用户，7 千兆兆字节的共享数据。节点每次启 动时先到服务器上注册，并获得2 0 0 个超级节点的列表。然后，自动检查本机是 复巨大学硕士学位论文 否为超级节点，如果是，就连到其它超级节点；如果不是，就选择一个超级节点 作为父节点连接。建立节点连接时，先使用U D P 包来探测超级节点列表中的可 用连接，然后根据策略选择其中的一个作为父节点，上传自己的共享文件信息。 选择父节点的参数通常是超级节点的负载和实际网络位置。网络位置的判断可以 依据I P 地址的前缀、网络往返时间等。 本文第四章提出的基于P 2 P 网络的流媒体直播模型就采用了混合式P 2 P 网络 模式。 2 3P 2 P 网络关键技术 2 3 1 资源搜索 由于P 2 P 系统的资源存储在各个节点中，而不是像c s 模式和B S 模式中将 内容集中存储在服务器上，因此需要为各个节点提供一种从其他节点中找到所需 资源的方法，即资源搜索机制。资源搜索机制不仅要保证用户能够迅速找到所需 信息，而且要尽可能提高带宽的利用率。 从目前的研究现状来看，主要存在三种文件搜索的算法： ( 1 ) 集中索引算法，对应于集中式系统，其特点是集中式的文件查询、分散 式的文件传输，如N a p s t e r 系统。当某个用户需要某个文件时，首先向服务器发 出查询请求，服务器检索其维护的文件索引，并将拥有该文件的用户信息返回给 用户。然后用户直接连到文件所有者，开始点对点的传输文件。这种搜索方式的 优点在于查询需要的时间比较短，缺点是整个系统对中央服务器的依赖性强，如 果中央服务器失效，整个系统都会瘫痪。 ( 2 ) 洪泛消息算法，对应于分布式系统，如G n u t e l l a 系统。各个节点完全是 分布式的，当用户需要某个文件时，采取洪泛的方式向网络中的其他节点发送查 询消息。这种搜索方式缺点是需要很长时间才能返回结果，而且大量的广播信息 降低了网络带宽的利用率。 ( 3 ) 基于D H T ( D i s t r i b u t e dH a s hT a b l e ，分布式哈希表) 的分布式查找和消 息路由算法，特点是采用基于哈希函数的映射。D H T 网络不需要中心服务器，而 是由每个节点负责一个小范围的路由，并存储一小部分数据，从而实现整个D H T 复且大学硕士学位论文 网络的寻址和存储。每一份资源都由一组关键字进行标识，D H T 系统根据资源的 关键字，通过算法计算出它所对应的哈希值，根据哈希值决定此关键字对应的资 源由哪个节点负责储存。用户搜索资源的时候，用同样的算法计算出每个关键字 的哈希值，再根据哈希值获得该关键字对应资源的储存位置，从而迅速定位资源 的位置。为了减小查询资源所需的时间，很多P 2 P 系统采用了缓存技术。缓存可 以减少查询资源所需经过的路径长度，从而减少消息传播的数量，降低通信延迟。 2 3 2 多源传输 传统的文件下载大多使用F T P 等协议进行c s 方式的下载。这样，对于一些 热点文件就会有很多用户同时需要下载，由于服务器端的带宽有限，就会有很多 用户请求得不到满足，从整体上看，下载效率很低。为了提高文件传输速率，P 2 P 网络普遍采用多源传输策略( F T P 协议，全称是M u l t i s o u r c eF i l eT r a n s f e r P r o t o c 0 1 ) 。M F T P 协议定义了一系列传输、压缩和打包的标准，甚至还定义了 一套积分的标准，上传的数据量越大，积分越高，下载的速度也越快。M F T P 协 议允许用户之间多点下载文件，也就是说，一个文件可以从多个用户处下载，同 时，已下载的部分也能被其它用户下载。多用户同时下载一个文件时，将该文件 分段，每个用户下载其中的一部分。P 2 P 客户端软件在网络上搜索下载同一个文 件的用户，然后从这些用户那里下载该文件不同的块，用M D 4 算法检查每一块是 否收到破坏，以保证传输的正确性，最后将所有的块组合成原来的文件。M F T P 充分利用下载用户之间的带宽进行数据传输，从而减轻服务器负担，提高下载速 度和系统的可扩展性( 指同时下载人数) 。 多源传输机制的出现使得P 2 P 技术在信息传输方面拥有网络层传输无法比 拟的优势，正是由于P 2 P 网络可以获取应用层信息，使得对等点可以通过增加连 接的方式提高业务的应用层传输性能。 2 3 3P 2 P 网络监控 面对大规模出现的P 2 P 虚拟网络，如何有效的监测与评估P 2 P 网络性能已经 变得越来越重要。由于缺乏集中式的监控功能，当前大多P 2 P 系统无法提供网络 运行状况的信息，无法提供网络调整及优化的手段，所以在应用中难以受到企业 复旦大学硕t 学位论文 的青睐，难以真正实现赢利目标。P 2 P 服务提供者需要通过测量P 2 P 的网络性能， 监测其业务运行状况，从而合理、有效地部署和规划网络资源，使之提供更优的 服务质量；P 2 P 用户需要利用P 2 P 的网络性能测量数据选择服务质量最佳的P 2 P 服务网络：企业级P 2 P 应用需要一个可控制、可管理、可运营并且具有一定Q o s 保障能力的P 2 P 网络。因此，如何利用P 2 P 网络资源，低成本地为分布式对等网 络提供集中式的信息监控服务成为P 2 P 网络研究的重点问题。P 2 P 网络监测的基 本功能是连续收集P 2 P 网络中拓扑变化、资源利用、网络性能、网络流量及业务 质量相关参数，监测目的是提供网络营运状况分析报告、评估P 2 P 网络的运行效 率及P 2 P 业务的服务