（计算机系统结构专业论文）基于p2p的vod系统模型研究及模拟器的设计与实现.pdf

摘要 摘要 随着网络传输设备的不断发展，视频点播( v o d ) 已经成为网络上越来越热 门的网络应用。传统的视频点播服务采用的服务器客户端( c l i e n t s e r v e r ) 集中式 网络模型，面临网络带宽及系统容量受限的问题。这导致服务器负担过重，支持 客户数有限，节目播放效果差。对等网络( p 2 p ) 技术打破了传统c s 模式，在网 络上每个节点都是对等的，既充当服务器提供上传，又充当客户端享受下载。p 2 p 技术很好的解决了网络带宽问题，并减少了服务器负担。p 2 p 技术因其扩展性强， 容错性高，健壮性等特点已经得到了迅猛发展，并逐步应用到视频点播领域。 本文基于北京市科委“基于v 6 的下一代互联网关键技术研发及产业推进 项目课题“口v 6 流媒体分发应用支撑平台的开发的项目成果中的视频点播系统， 提出了基于概率论的视频点播的静态数学模型，并着重研究了流媒体服务器压力 与节点缓存视频文件长度的定量的关系。 本文在研究了现有p 2 p 协议及p 2 p 模拟器后提出了一个通用的p 2 p 框架，并 依此设计并实现了v o d 模拟器。运用v o d 模拟器对不同的v o d 协议进行模拟， 得到了v o d 系统中的协议优化方向。 模拟器采用了消息级模拟机制，使得模拟器可以在一台机器上就可以运行。 模拟器使用了离散事件驱动的思想，将整个视频点播过程分解为若干子过程，每 个子过程都由特定事件触发。模拟器分为事件调度模块，网络拓扑模块，协议处 理模块与输入输出模块。事件调度器是整个系统的核心，它完成各种事件的时间 顺序排序与调度，并驱动整个系统运行。网络模块采用了由b r i t e 得到的g t - i t m 网络拓扑，并考虑到了网络底层带宽与延时因素。协议处理模块完成了对v o d 协 议的模拟，包块o v e f l a y 网络生成与协议交互信息描述，输入输出模块用于指点协 议参数与输出结果。 在模拟器的支持下，本文对v o d 系统进行了模拟，并对b t 协议进行了分析。 在激励机制的情况下设计3 种u n c h o k e 算法，并与现行b t 的u n c h o k e 算法进行比 较分析得出了激励机制的重要性。 关键词：视频点播，数学模型，模拟器，离散事件驱动，u n c h o k e 算法 a b s t r a c t a l o n gw i t ht h ed e v e l o p m e n to fn e t w o r kt r a n s m i s s i o nd e v i c e s ，v i d 。0 o n 以a a n d ( no d ) b e c o m e sm o r ea n dm o r ep o p u l e ro nt h ei n t e r a c t f o r m e rv o ds y s t e m sa l eb a s e d o nc l i e n t s e r v e r ( c s ) c o n c e n t r a t e da r c h i t e c t u r ew h i c hn o to n l yl i m i t e dt h ec a p a b i l i t yo f v o ds y s t e ma n dn e w , y o r kb a n d w i d t h , b u ta l s om a k et h ev o ds y s t e mb u r d e n e dt o o h e a v yw h i c hl e e dt ot h eb a du s e re x p e r i e n c e t h ep e e r - t o - p e e r ( p 2 p ) t e c h n o l o g yi s d i f f e r e n tf r o mc sm o d e , e a c hn o d ei nt h en e ti sp e e rt op o e le a c hn o d ea c t s 弱b o t h s e r 弋，e fa n dc l i e n tt op r o v i d eu p l o a da n dr e g a l eo nd o w n l o a d r e s o r t st oi t se x p a n s i b i l i t y a n dh i 班r e s i l i e n c et of a i l u r ea n dh a l e n e s s ，t h et e c h n o l o g yo fp 2 ph a sd e v e l o p e ds w i f t l y a n d v i o l e n t l y , a n dg r a d u a l l ya p p l i e st ot h ef i e l do fv i d e of i e q u e n c yt e c h n o l o g y t h i st h e s i si sb a s e do nt h ep r o j e c to fp p c d n p p c d ni sas u p p o r t i n gs y s t e mo f v 6s t r e a md i s t r i b u t i o na p p l i c a t i o ns y s t e ma sw e l la sac o n t e n td i s t r i b u t i o ns y s t e m b a s e do np 2 pt e c h n o l o g y , s p o n s o r e db yr e s e a r c ho ft h e 口v 6b a s e dn e x tg e n e r a t i o n i n t e r n e tk e y t e c h n o l o g ya n di n d u s t r i a l i z a t i o np r o m o t i o no fb e i j i n gm u n i c i p a ls c i e n c e a n dt e c h n o l o g yc o m m i s s i o n t h ea u t h o rf o u n d sas t a t i cm a t h e m a t i c sm o d e lo ft h e v o d p r o c e s so fp p c d n b a s eo np r o b a b i l i t yt h e o r y , a n dt h e ns t u d y st h er e l a t i o n s h i p b e t w e e n t v e r sl o a da n dt h el e n g t ho f b u f f e rt h a te a e hp e e rs t o r e s t h i sp a p e rp r o p o s e dag e n e r i ca r c h i t e c t u r eo fp 2 ps i m u l a t o ra f t e re x a m i n i n gt h e f u n d a m e n t a lp 2 pt h e o r ya n do t h e rp 2 ps i m u l a t o r , i no r d e rt oa n a l y s et h ev o d p r o t o c o l a n dt oo p t i m i z et h es y s t e m b a s eo nt h eg e n e t i cs i m u l a t o r , av o d p r o t o c o ls i m u l a t o ri s d e s i g n e da n di m p l e m e n t e d f i n a l l yt h ep r o t o c o lo p t i m i z a t i o nw o r k i sa c c o m p l i s h e d 、历m t h eh e l po f v o ds i m u l a t o r t h ev o ds i m u l a t o ri sd e v e l o p e di nc 抖l a n g u a g ew i t ht h em o d u l a r i z a t i o ni d e a i t c o n s i s t so ff o u rp a r t s ：t h ed i s c r e t ee v e n t d r i v e nm o d u l e , t h et o p o l o g ym o d u l e ，t h e p r o t o c o lm o d u l ea n dt h ei n p u t - o u t p u tm o d u l e t h ed i s c r e t ee v e n t - d r i v e nm o d u l ei st h e k e yp a r to ft h es i m u l a t o r i ts o r t sa n ds c h e d u l e sa l lk i n d so fe v e n t se f f e c t i v e l ya n da l l o t h e rm o d u l e sa r er u n n i n go ni t t h et o p o l o g ym o d u l eu s e st h eg t - i t mn e t w o r k t o p o l o g y , a n dd r i v e st h ew h o l es y s t e m t h ep r o t o c o lm o d u l es i m u l a t e st h ev o d p r o t o c 0 1 t h ei n p u t - o u t p u tm o d u l er e a d st h ec o n f i g u r ef i l e sa n do u t p u t st h eo u t c o m e s t h ea u t h o rh a so p t i m i z e dt h ep p c d n s y s t e mw i t ht h es u p p o r to ft h ev o ds i m u l a t o r f i r s t l y , t h ea u t h o rh a sp r o v e dt h ei m p o r t a n c eo ft h ep u n i s h m e n t a n di n c e n t i v e m e c h a n i s mt ot h ev o ds y s t e ma n dp r o p o s e ds o m ei m p r o v e m e n to fi t su n c h o k e a l g o r i t h m k e y w o r d s ：m a t h e m a t i c sm o d e l ，v o d ，s i m u l a t o r , d i s c r e t ee v e n t d r i v e n ，u n c h o k e a l g o r i t h m 主要符号表 主要符号表 p p c d n -北京市科委“基于v 6 的下一代互联网关键技术研发及产业推进”项 目课题“i p v 6 流媒体分发应用支撑平台的开发”的项目成果p e e r - t o - p e e r c o n t e n td e l i v e rn e t w o r k 的简称 v o d ： 视频点播，v i d e oo nd e m a n d 的简称 p 2 p ： 对等网络，p e e r - t o p e e r 的简称 d h t - 分布式散列表，d i s t r i b u t e dh a s h1 曲l e e s p ：p p c d n 系统中的边缘服务器，e d g es e r v i c ep r o v i d e r c r , p p c d n 系统中的内容路由服务器，c o n t e n tr o u t e r i 独创1 生声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他入已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名： 互龟蝗 日期：年月 日 关于论文使用授权的说明 本学位论文作者完全了解电子科技大学有关保留、使用学位论文 的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁 盘，允许论文被查阅和借阅。本人授权电子科技大学可以将学位论文 的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或 扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后应遵守此规定) 签名：丕筮惶导师签名： 日期：年月日 第一章引言 1 1 研究背景 第一章引言 随着互联网的日益普及，以及互联网技术的发展，互联网中的各种网络应用 也急速发展起来。互联网上传输的信息不再只是文本、图像，各种各样的多媒体 通信( m u l t i m e d i ac o m m u n i c a t i o n ) 服务从技术上和经济上成为可能。多媒体通信可 以集成视频、音频、文本及图像为一体，为用户提供更为丰富的使用体验，因此 得到了越来越为广泛的应用。特别是流媒体技术的出现和普及，使得声音、影像 或动画等媒体可以由音视频服务器向用户计算机的连续、实时传送，用户不必等 到整个文件全部下载完毕就可观看到媒体，从而满足了实时交互的需要，因而视 频点播【1 1 ( v i d e oo nd e m a n d ，v o d ) 技术的出现也就成为了必然。 v o d 技术是二十世纪9 0 年代在国外发展起来的翻，是一种可对视频节目内容 进行自由选择的交互式电视点播系统，现在视频点播已经不在局限于电视点播， 也包括网络点播服务。视频点播的本质是信息的使用者根据自己的需求主动获得 多媒体信息，该双向视频音频信息系统实现了按用户需要播放视频音频节目的功 能。 视频点播技术的出现是视频信息技术领域的场革命，其巨大的潜在市场， 使世界主要发达国家都投入了大量的资金，加速开发和完善这一系统。v o d 技术 的功能远远超出人们的想象。用户可在家中的电视机前，利用遥控器按照自己的 意愿来实现点播电视、信息查询、家庭购物、远程医疗、电视教育、电子函件、 旅游指南、定票预约、股票交易等等流动。这技术的出现，极大地提高和改善 了人们的生活质量和工作效率。 目前v o d 服务主要是基于t c p i p 协议的c s 模式。在传统模式下，内容的 发布由i c p 的应用服务器完成，应用服务器通常处于网络的中心，客户端主机处 于网络的边缘，客户端需要登陆到应用服务器下载或浏览各种内容。在这种发布 模式下数据传输是端到端的模式，一方面造成网络资源利用率低下，另一方面某 段网络的瓶颈会造成整个网络的拥塞，有时还会产生局部热效应等。单纯地提高 单台服务器的性能或采用服务器集群不但价格昂贵，而且不能从根本上解决问题。 为了在网络条件一定的情况下提高网络的利用效率，人们提出了许多解决方案， 电子科技大学硕士学位论文 其中包括内容分发网络( c o n t e n td e l i v e r yn e t w o r k , c d n ) 3 】和点对点传输 ( p e * t o p e p 2 p ) 【4 】技术。 目前广泛采用的解决方法是一种称为内容发布网络( c d n ) 的内容传送体系 结构，通过在现有的i n t e m e t 上增加一层新的网络架构，将i c p 的内容发布到最接 近用户的网络边缘，使用户可以就近取得所需的内容，从而极大的优化了网络结 构，缓解了骨干网压力，提高用户访问的响应速度。 传统的c d n 网络是基于c s 模式的，其应用系统所支撑的用户数量受到服务 器性能的限制：另一方面，网络技术的发展和应用的需求推动了p 2 p 技术的产生。 网络技术的发展主要体现在客户端主机能力的增强和带宽的增加，现在主流的主 机配置可以使处于网络边缘的主机具备小型服务器的能力；宽带接入技术的实现 使主机之问具备直接通信的能力。而传统的c s 应用模式使各种i n t e r n e t 应用必须 通过集中式的服务器，浪费资源且操作复杂。此外，目前i n t e r n e t 主机的数目也在 不断地增加，达到数亿台，而在c s 方式下，主机只能处于c l i e n t 的地位，资源 得不到充分的利用，因此在网络边缘产生了大量的空闲资源，包括存储能力、c p u 计算能力、信息资源。与此同时，处在网络中心的应用服务器随着用户的增加， 负载过重，导致整个网络负载极不平衡，从而产生利用这些空闲资源的需求。在 这样的背景下，p 2 p 技术出现了，目的就是希望能充分利用互联网中所蕴含的潜在 计算资源，尤其是i n t e r n e t 边缘的客户端主机资源。p 2 p 技术应用非常广泛，其中 一个重要的应用领域就是内容共享和发布。p 2 p 内容共享和发布系统可以通过p 2 p 节点间的协作，实现内容的快速分发，大大减轻了应用服务器的负载。 鉴于c d n 与p 2 p 的特点，p p c d n 将两者结合起来，充分利用两者优势，在 降低骨干网络流量的同时，充分利用网络空闲资源，很好的满足了流媒体支撑平 台的需求。但是，好的p 2 p 系统需要高效的p 2 p 协议作支撑，这就需要一个适合 的系统模型以及优秀的模拟器来进行协议优化。协议优化工作成为p p c d n 的一个 重要课题1 5 j 。 为了v o d 协议的的研究与优化，需要一个测试平台。由于实验室条件限制， 大规模模拟并不现实，所以需要用单机模拟器来研究v o d 协议优劣。模拟器将会 记录每个点播用户的行为点播信息，并通过调整系统参数来对系统模型进行验证， 得到最优系统参数配置，系统容量与用户体验值。 本文基于北京市科委“基于口v 6 的下一代互联网关键技术研发及产业推进 项目课题“口v 6 流媒体分发应用支撑平台的开发的项目成果p p c d n 。课题主要 研究如何设计一个能够支撑大规模用户的高性能的内容分发系统。本文主要研究 2 第一章引言 p p c d n 系统中v o d 子系统的模型与模拟器设计与实现，并根据模拟器试验结果 对v o d 协议优化方向提供参考。v o d 模拟器采用离散事件驱动方式，并采用类 似b t 协议的流模型，模拟具有成千上万个节点的v o d 系统。在模拟器的支持下， 本文对p p c d n 系统协议进行了优化。 1 2 国内外研究现状 要研究基于p 2 p 的v o d 系统模拟器，首先要研究p 2 p 模拟器。由于p 2 p 技 术的拓扑结构和应用环境等方面各不相同，而路由、查找和容错等方面又十分复 杂，这导致p 2 p 协议的研究与实践具有很大的困难。由于p 2 p 的开放性，大部分 p 2 p 系统具有很大的规模。例如，一个中等规模的b t 系统，其参与节点数可以达 到数万，在这样的条件下，依赖于实验室环境或通过部署节点对p 2 p 协议进行实 证研究是不可行的【6 j ，因此，p 2 p 研究主要依赖于模拟仿真。目前典型的p 2 p 仿真 软件有p 2 p s i m 、p e z r s i m 、n a r s e s 等，它们有各自的特点和应用范围： 1 d h t s i m 刀 d h t s i m 基于离散事件驱动方式，模拟了d h t 协议。该模拟器主要用于教学 目的，用于研究d h t 的实现机制，不支持节点的动态加入和退出，不支持协议扩 展等。 2 p 2 p s i m 8 l p 2 p s i m 基于离散事件驱动方式，提供了数据包级的模拟，支持结构化网络。 p 2 p s i m 支持6 种p 2 p 协议：c h o r d 、a c c o r d i a n 、t a p e s t r y 等，并且实现了c h o r d 协议。由于采用了数据包级的模拟，该软件模拟效率差，不适合大规模p 2 p 系统 的模拟。 3 p l p 2 p a ! p l p 2 p 基于n s 2 构建p 2 po v e r l a y 网络，提供了数据包级的模拟。它利用n s 2 提供的网络基础设施传输数据，因而模拟了底层网络的细节。p l p 2 p 适于模拟规 模不大、数据交互较少并且对底层网络状况敏感的p 2 p 系统。 4 p e e r s i m 1 0 1 与p l p 2 p 相反，p e e r s i m 高度关注系统的可扩展性，它完全忽略了底层网络细 节，如带宽、时延等。p e e r s i m 使用j a v a 语言编写，支持结构化和非结构化网络， 支持节点的动态加入、退出与失效，并且可以方便地扩展以支持用户协议。程序 的开发者声称该软件能模拟具有1 0 6 个节点的庞大系统，但是，这种高度可扩展性 3 电子科技大学硕士学位论文 是以损失模拟精度为代价的。 5 u a r s e s t l 1 】 n a r s e s 基于离散事件驱动方式，提供了流级的模拟，并提供四种层次的流抽 象：n a i v e 、n a i v e t o p o 、f a i r t o p o 和s a f e f a i r t o p o ，分别代表不同的抽象精度。由 于采用了高层抽象，n a r s e s 具有较好的可扩展性。 6 g p s f l 2 j 与n a r s e s 一样，g p s 基于离散事件驱动方式，提供了流级的模拟，并实现了 b t 协议。g p s 使用公式( b 胍可用带宽，m s s ：t c p 报文最大长度，c ：常数， r t t ：r o u n dt r i pt i m e ，p ：数据包丢失概率) bw - m s s x c = ：； r 1 t x o p 计算可用带宽，由于参数r 刀和p 随着网络状态变化而变化，因而很难用于实 际模拟。此外，g p s 的b t 协议实现采用了j a v a 语言实现。 综上，p 2 p s i m 和p l p s i m 采用数据包级的模拟，可扩展性差，很难用于大规 模p 2 p 系统的模拟；p e e r s i m 强调系统的可扩展性，模拟精度较差；g p s 虽然实现 了对b t 的模拟，但底层拓扑的某些算法不是很合理，协议描述不够简单清晰，并 且很难加入p p c d n 系统的特性，基于j a v a 的实现导致了运行效率的低下。即使 如此，这些模拟软件( 尤其是n a r s e s ) 的抽象和设计思想以及g p s 的程序实现为 本文的b t 模拟器设计与实现提供了很好的参考作用。 可以看出，由于p 2 p 协议的多样性和复杂性，p 2 p 模拟软件的开发与设计工 作具有相当的难度。我们必须根据被仿真的p 2 p 系统的特点，采用适合于该系统 的抽象层次和模拟手段，在模拟的效率和精度之间达到平衡。因此，如何对v o d 协议建模，如何模拟其详细的交互过程，对本课题来说将是一个挑战。 1 3p p c d n 的仿真需求 首先，必须基于一个合理的通用p 2 p 模拟器框架，具有良好的模块化特性。 合理的框架是设计与实现p 2 p 模拟器的前提和基础，它可以使模拟器具有较好的 可扩展性。 其次，必须保持协议描述的准确性。协议交互是一个复杂的过程，我们必须 采用某种简洁的方法以保证协议交互描述的准确性，协议的消息描述很好地满足 了这个要求。 4 第一章引言 最后，必须保持仿真器的模拟效率和精度。协议是一个用于文件共享的p 2 p 协议，不同于d h t 等资源定位协议，也不同于其它及时通讯或对等计算等协议， 系统规模和数据传输量都很大。为此，模拟器需要在较高的层次上对网络传输进 行抽象，以获得较高的模拟效率，但必须保持一定的模拟精度。 1 4 本文创新 本文的工作主要是：以概率论为基础，建立了v o d 系统的静态数学模型，得 到了客户节点缓存视频文件长度与流媒体中心服务器压力间定量的关系。并设计 并实现了一个基于c h 语言的高效的p 2 p 的协议模拟器，以及依赖于模拟器，对 v o d 协议优化提出了优化方向。 在v o d 模拟器的设计与实现方面，本文根据p 2 p 的特点，提出了一个通用 p 2 p 模拟器框架，设计了一个基于离散事件驱动的p 2 p 协议模拟器运行框架，高 效的运行框架奠定了模拟器的运行基础。在模拟器运行框架上，采用模块化和面 向对象的思想设计与实现了整个模拟器。在网络拓扑方面，本文研究了i n t o - n e t 拓 扑结构和拓扑生成算法，并采用了一种简洁的，能反映i n t e r n e t 结构特点的 g t - i t m 1 1 】网络拓扑。根据p 2 p 协议的特点，本文还将消息和流模型引入模拟器， 确保了模拟器的简洁与高效。模拟器模拟p 2 p 协议的真实下载过程，模拟过程简 洁而又清晰。 1 5 本文组织结构 全文共有五章。 第一章是引言，给出了本课题的研究背景、研究内容和文章的结构框架等。 第二章是p 2 p 以及v o d 介绍。 第三章介绍了p p c d n 系统，并提出了v o d 系统的静态数学模型，研究了节 点缓存文件大小与流媒体服务器压力间的关系。 第四章是基于p 2 p 协议的v o d 模拟器的设计与实现：首先提出了一个通用 p 2 p 模拟器框架，然后基于该框架设计与实现了一个v o d 模拟器。 第五章是模拟器的验证与v o d 协议的优化。 第六章是结论，总结全文。 5 电子科技大学硕士学位论文 2 1v o d 介绍 2 。1 1v o d 的概念 第二章p 2 p 与v o d 介绍 视频点播技术是二十世纪九十年代在国外发展起来的【1 3 】，英文名称为“v i d e o o n d e m a n d ( v o d ) 。顾名思义，是根据观众要求播放节目的点播系统，不过近年 来v o d 的外延逐渐扩大【1 4 】【1 5 】。v o d 服务中不仅仅包括视频的点播服务，通常还 包括其它多媒体信息如音频、动画甚至文本信息的点播。在本文中，我们对v o d 作如下定义【1 6 j 【1 7 j ：v o d 是一种多媒体网络服务，它使用户能够在任何时间通过网 络从服务器中访问到任何多媒体数据内容，并能对使用过程施加控制。 根据定义可以得到到v o d 应用的三个特点： 1 v o d 提供的内容是用多媒体数据表示的，并以多媒体信息的点播服务为主。 这一特点使v o d 应用区别于现有的以提供文本图片或其它非连续信息为主的网站 服务。 2 v o d 多媒体数据来自于网络上的服务器，这一点使v o d 区别于本地多媒体 应用。 3 v o d 是一种交互式应用，用户在使用过程中可以施加控制，这一点使v o d 应用区别于下载后播放。 2 1 2v o d 的系统组成 作为一个v o d 系统主要由三部分构成： 1 ) 服务端系统 服务端系统主要由视频服务器、档案管理服务器、内部通讯子系统和网络接 口组成。档案管理服务器主要承担用户信息管理、计费、影视材料的整理和安全 保密等任务。内部通讯子系统主要完成服务器间信息的传递、后台影视材料和数 据的交换。网络接口主要实现与外部网络的数据交换和提供用户访问的接口。视 频服务器主要由存储设备、高速缓存和控制管理单元组成，其目标是实现对媒体 数据的压缩和存储，以及按请求进行媒体信息的检索和传输。视频服务器与传统 6 第二章p 2 p 与v o d 介绍 的数据服务器有许多显著的不同，需要增加许多专用的软硬件功能设备，以支持 该业务的特殊需求。例如：媒体数据检索、信息流的实时传输以及信息的加密和 解密等。对于交互式的v o d 系统来说，服务端系统还需要实现对用户实时请求的 处理、访问许可控制v c r ( v i d e oc a s s e t t er e c o r d e r ) 功能( 如：快进、暂停等) 的模拟。 2 ) 网络系统 网络系统包括主干网络和本地网络两部分。因为它负责视频信息流的实时传 输，所以是影响连续媒体网络服务系统性能极为关键的部分。同时，媒体服务系 统的网络部分投资巨大，故而在设计时不仅要考虑当前的媒体应用对高带宽的需 求，而且还要考虑将来发展的需要向后的兼容性。当前，可用于建立这种服务系 统的网络物理介质主要是：c a t v ( 有线电视) 的同轴电缆、光纤和双绞线。而采用 的网络技术主要是：快速以太网、f d d i 和a t m 技术。 3 ) 客户端系统 目前，根据不同的功能需求和应用场景，主要有三种v o d 客户端系统【1 8 】： n v o d ，t v o d 和o d 。 1 ) n v o d ( n e a r - v i d e o o n - d e m a n d ) ，可称其为就近式点播电视。这种点播电视 的方式是：多个视频流依次间隔一定的时间启动发送同样的内容。比如，十二个 视频流每隔十分钟启动一个发送同样的两小时的电视节目。如果用户想看这个电 视节目可能需要等待，但最长不会超过十分钟，他们会选择距他们最近的某个时 间起点进行收看。在这种方式下，一个视频流可能为许多用户共享。 2 ) t v o d ( t r u ev i d e o - o n - d e m a n d ) ，称其为真实点播电视，它真正支持即点即 放。当用户提出请求时，视频服务器将会立即传送用户所要的视频内容。若有另 一个用户提出同样的需求，视频服务器就会立即为他再启动另一个传输同样内容 的视频流。不过，一旦视频流开始播放，就要连续不断的播放下去，直到结束。 这种方式下，每个视频流转为某个用户服务。 3 ) i v o d ( i n t e r a c t i v ev i d e o 。o n - d e m a n d ) ，称为交互式点播电视。它比前两种方 式有很大程度上的改进。它不仅可以支持即点即放，而且还可以让用户对视频流 进行交互式的控制。这时，用户就可像操作传统的录像机一样，实现节目的播放、 暂停、快进和自动搜索等。 2 1 3v o d 应用现状 大规模超大规模的v o d 应用仍处于实验和探索阶段，在国外已经有了比较 7 电子科技大学硕士学位论文 成熟的研究成果1 9 】【2 0 】【2 1 1 ，但是还在推广之中。以下是一些典型的商业系统。 2 0 0 0 年9 月，d i g i t a li s l a n d 宣布将与康柏、英特尔和微软三家公司合作，在 未来两年内在w e b 上创建一个高容量的流式音频和视频网络。建成后，该网络可 同时传输7 5 0 万个音频及视频流，这将是同类网络中最大的一个。该网络采用机 群式体系结构，计划安装8 0 0 0 台康柏服务器。 2 2p 2 p 介绍 2 2 1p 2 p 的概念 近年来，对等计算( p e e r - t o p e e r ，简称p 2 p ) 迅速成为计算机界关注的热门话 题之一，目前，在学术界，对于p 2 p 没有一个统一的定义，下面列举几个常用的 定义供参考翻： 1 p e e r - t o - p e e ri sat y p eo f i n t e m e tn e t w o r ka l l o w i n gag r o u po fc o m p u t e ru s e r s w i t ht h es a m en e t w o r k i n gp r o g r a mt oc o n n e c tw i t he a c ho t h e rf o rt h ep u r p o s e so f d i r e c t l ya c c e s s i n gf i l e sf r o mo n e a n o t h e r sh a r dd r i v e s 2 p e e r - t o - p e e rn e t w o r k i n g ( p 2 p ) i sa na p p l i c a t i o nt h a tr i m so n ap e r s o n a lc o m p u t e r a n ds h a r e sf i l e sw i t ho t h e ru s e r sa c r o s st h ei n t e m e t p 2 pn e t w o r k sw o r kb yc o n n e c t i n g i n d i v i d u a lc o m p u t e r st o g e t h e rt os h a r ef i l e si n s t e a do f h a v i n gt og ot h r o u g hac e n t r a l s e r y l ：r 3 p 2 p 是一种分布式网络，网络的参与者共享他们所拥有的部分软硬件资源 ( 处理能力、存储能力、网络连接能力、打印机等) ，这些共享资源需要由网络 提供服务和内容，能被其它对等节点( p e e r ) 直接访问而无需经过中间实体。在此 网络中的参与者既是资源( 服务和内容) 提供者( s e r v e r ) ，又是资源( 服务和内 容) 获取者( c l i e n t ) 。 圈圈- 固 国圜囹 8 图2 - 2p e e r t o p e e r 模式 第二章p 2 p 与v o d 介绍 虽然上述定义稍有不同，但共同点都是p 2 p 打破了传统的c l i e n t s e r v e r ( c ，s ) 模式，在网络中的每个结点的地位都是对等的。每个结点既充当服务器，为其他 结点提供服务，同时也享用其他结点提供的服务。p 2 p 与c s 模式的对比如图2 1 和图2 2 所示。 2 2 2p 2 p 的特点 p 2 p 是一种分布式网络，其最本质的特点就是协作与共享，它打破了传统的 c l i e n t s e r v e r 模式，在网络中的每个节点的地位是相等的，每个p e e r 既充当服务端 ( s e r v e r ) 提供资源，又充当客户端获取资源( c l i e n t ) 。 此外，p 2 p 还具有如下特点： 1 非中心化( d e c e n t r a l i z a t i o n ) 网络中的资源和服务分散在所有结点上，信息的传输和服务的实现都直接在 结点之间进行，可以无需中间环节和服务器的介入，避免了可能的瓶颈。p 2 p 的非 中心化基本特点，带来了其在可扩展性、健壮性等方面的优势。 2 健壮性( r o b u s t n e s s ) p 2 p 架构天生具有耐攻击、高容错的优点。由于服务是分散在各个结点之间进 行的，部分结点或网络遭到破坏对其它部分的影响很小。p 2 p 网络一般在部分结点 失效时能够自动调整整体拓扑，保持其它结点的连通性。p 2 p 网络通常都是以自组 织的方式建立起来的，并允许结点自由地加入和离开。p 2 p 网络还能够根据网络带 宽、结点数、负载等变化不断地做自适应式的调整。 3 可扩展性( s c a l a b i l i t y ) 在p 2 p 网络中，随着用户的加入，不仅服务的需求增加了，系统整体的资源 和服务能力也在同步地扩充，始终能较容易地满足用户的需要。整个体系是全分 布的，不存在瓶颈。理论上其可扩展性几乎可以认为是无限的。 4 性能优势但e r f o m 锄c ea d v a n t a g e ) 性能优势是p 2 p 被广泛关注的一个重要原因。随着硬件技术的发展，个人计 算机的计算和存储能力以及网络带宽等性能依照摩尔定理高速增长。采用p 2 p 架 构可以有效地利用互联网中散布的大量普通结点，将计算任务或存储资料分布到 所有结点上。利用其中闲置的计算能力或存储空间，达到高性能计算和海量存储 的目的。通过利用网络中的大量空闲资源，可以用更低的成本提供更高的计算和 存储能力。 9 电子科技大学硕士学位论文 5 负载均衡( l o a ds h a r i n g ) p 2 p 网络环境下由于每个节点既是服务器又是客户机，减少了对传统c s 结 构服务器计算能力、存储能力的要求，同时因为资源分布在多个节点，更好的实 现了整个网络的负载均衡。 6 多样性和大规模( d i v e r s i t ya n dl a r g es c a l e ) 由于应用目的和应用环境的不同，p 2 p 具有天生的多样性，如用于文件下载的 b t 协议，用于资源搜索与定位的d h t 网络等；也由于p 2 p 天生的可扩展性和健 壮性，p 2 p 系统一般具有较大的规模，比如一个中等规模的b t 系统，参与的用户 数可以上千甚至数万。p 2 p 的多样性和大规模为p 2 p 技术的研究和实践带来了困 难和挑战。 由于p 2 p 技术的诸多优点，p 2 p 技术具有传统分布式系统无可比拟的优势。 同时，p 2 p 技术具有广阔的应用前景。i n t e m e t 上各种p 2 p 应用软件层出不穷，用 户数量急剧增加。p 2 p 计算技术正不断应用到军事领域，商业领域，通讯领域等。 2 2 3p 2 p 的分类 目前广泛采用的p 2 p 系统分类标准是p 2 p 网络拓扑结构。拓扑结构是指分布 式系统中各个节点之间的物理或逻辑的互联关系，结点之间的拓扑结构一直是确 定系统类型的重要依据。目前互联网络中广泛使用集中式、层次式等拓扑结构， i n t e m e t 本身是世界上最大的非集中式的互联网络，但是九十年代所建立的一些网 络应用系统却是完全的集中式的系统，例如传统的w e b 服务器、邮件服务器等。 集中式系统目前面临着过量存储负载、d o s 攻击等一些难以解决的问题。 p 2 p 系统一般要构造一个非集中式的拓扑结构，在构造过程中需要解决系统中 所包含的大量结点如何命名、组织以及确定结点的加入离开方式、出错恢复等问 题。根据拓扑结构的关系可以将p 2 p 系统分为4 种形式：中心化拓扑( c e n t r a l i z e d t 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 dt 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 y d e c e n t r a l i z e dt o p o l o g y ) 。 中心化拓扑的特点是资源的发现依赖于中心化的目录系统，这种拓扑的优点 是维护简单并且发现效率高，查询算法灵活并且能实现复杂查询。由于资源索引 位于中心服务器上，与传统的c s 结构类似，容易造成单点故障和访问的热点现 象等。即使如此，中心化拓扑的简单高效是其它拓扑结构不可比拟的，有很多应 1 0 第二章p 2 p 与v o d 介绍 用采用这种拓扑结构，如著名的m p 3 共享软件n a p s t e r t 2 3 1 。 全分布非结构化网络在重叠网络( o v e r l a y ) 上采用了随机图的组织方式，节 点度数服从p o w a - l a w 规律，从而能够较快发现目的节点，面对网络的动态变化 体现了较好的容错能力，因此具有较好的可用性，同时可以支持复杂查询，如带 有正则表达式的多关键字查询，模糊查询等，g n u t e l l a 2 4 1 是其最典型的案例。 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 系统，没有索引服务器，它采用了基于完全随机图的洪泛( f l o o d i n g ) 发现和随机转发( r a n d o mw a l k e r ) 机制。为了控制搜索消息的传输，通过t t l ( t i m e t ol i v e ) 的减值来实现。 全分布非结构化网络存在可扩展性和发现准确性两个方面的重要问题。一方 面，随着联网节点不断增多，网络规模不断扩大，这种通过泛洪方式定位对等点 的方法将造成网络流量急剧增加，从而导致网络中部分低带宽节点因网络资源过 载而失效。另一方面，由于没有确定拓扑结构的支持，非结构化网络无法保证资 源发现的效率，即使需要查找的目的结点存在发现也有可能失败，由于采用t t l ( t i m e - t o 。l i v e ) 、洪泛( f l o o d i n g ) 、随机漫步或有选择转发算法，因此直径不 可控，可扩展性较差。 由于非结构化网络将重叠网络认为是一个完全随机图，结点之间的链路没有 遵循某些预先定义的拓扑来构建，系统中的随机搜索造成的不可扩展性，大量的 研究集中在如何构造一个高度结构化的系统，即全分布结构化网络。目前研究的 重点放在了如何有效地查找信息上，最新的成果都是基于d h t 2 s 】的分布式发现和 路由算法。这些算法都避免了类似n a p s t e r 的中央服务器，也不是像c m u t e l l a 那样 基于广播迸行查找，而是通过分布式散列函数，将输入的关键字惟一映射到某个 结点上，然后通过某些路由算法同该结点建立连接。 分布式散列表( d h t ) 实际上是一