（通信与信息系统专业论文）vod覆盖网络组播媒体流调度策略研究.pdf

摘要 y8 7 8 s 乏3 v o d ( v j d e o o n d e m a n d ) 技术在娱乐，远程教育和视频会 议等方面有着广泛的应用，为了节省带宽资源和视频服务器压力， 将v o d 技术与组播技术相结合来实现大范围视频点播，目前主 要采用i p 组播实现小范围视频点播，随着覆盖网络组播的提出和 发展，以往媒体流调度策略均不能完全适应覆盖网络组播环境。 本文论述了v o d 系统中几种主要的组播媒体流调度策略和 v c r 实现方法，分析其优缺点，进一步针对覆盖网络组播技术， 设计一种适应覆盖网络组播环境的媒体流调度策略，实现算法有 用户加入过程和用户离开过程两大部分，对于调度策略中最关键 的计算播放延迟部分的实现，提出根据概率计算的算法，之后， 针对现有系统提供v c r 操作的缺陷，提出用组播实现v c r 操作， 进一步提高v o d 系统的整体性能。最后对所设计算法进行分析， 并提出提高算法效率的方法。 本文研究的视频点播媒体流调度方案在覆盖网络组播环境下 应用于v o d 系统中，可以加入最优化的用户等待时间，使用户 平均等待时间最短，同时使用较少流数目和用户缓冲区逻辑分块， 有效保证v o d 系统服务用户的播放连续性；组播v c r 操作可以 大大减少用单播实现v c r 时所需流的数目，提供有效的暂停， 快进，快退，重新定位操作，有利于网络中对大量用户提供v c r 功能。这种实现方法还适用于i p 组播与覆盖网络组播结合的情 况，尤其是小范围使用i p 组播，无法提供l p 组播支持的用户之 问使用覆盖网络组播的情况，算法可以给用户提供连续稳定的播 放和v c r 功能，甚至可以比单纯覆盖网络组播卜- 体现出更好的 性能。 关键词：媒体流调度策略v 0 d v c r覆盖网络组播 c o m p a r e d t on o n i l a lv c r t h ea p p m a c hc a na l s ob eu s e di n c o m b i n e de n v i r o n m e n to fi pm u l t i c a s ta n do v er l a ym u l t j c a s t ，s u c ha s i pm u l t i c a s ti ns m a na r e a sa n do v e r l a ym u l t i c a s ti nh o s t sb e t w e e n w h i c hi pm u l t i c a s tc a n n o tb e p r o v i d e d i tc a n a l w a y sp r o v i d e c o n t i n u o u sa n ds t e a d yp l a y ，a sw e l la sv c rf 、u n c t j o nw j t hi m p r o v e d p e r f b m a n c e k e yw o r d s ：m e d i a s t r e a m s c h e d u l i n gp o c i e s ， v o d ，v c r o v e r l a ym u l t i c a s l 北京交通大学硕士论文v o d 覆盖网络组捕媒体流调度策略研究 1 1v o d 背景知识 第一章绪论 随着网络技术发展，主干网的宽带接入技术日趋成熟，人们 可以在任何网络连通的地方实现资源共享。从网上浏览多媒体内 容，己成为因特网应用的重要组成部分。而在网络上进行视频点 播( v o d ) 作为一种新兴的传媒方式，可以满足人们工作娱乐上的 多种需求，越来越受到业界的关注。 常有人将v o d 业务与录像带或光盘出租相比，这是对v o d 的 片面理解。实际上，v o d 泛指对各种视频信息的点播，它的交互 能力远远超越了控制影碟机的快进、快退等简单的动作，它所提 供的信息也远远超过了录像带或光盘的内容。v o d 己经发展成了 一大类交互式业务的总称，在世界各地开展的v o d 实验中包括了 各种多媒体业务。比如：电影点播m o d ( m o v i e so nd e m a n d ) 、远程 购物( t e l e s h o p p i n g ) 等等。在这些领域中，v o d 有着巨大的应用 前景和商业价值。目前，它是世界各国软件研发人员近年来重点 研究的应用领域。 1 1 1v o d 系统组成及关键技术 v o d ( v i d e o o n d e m a n d ) 是一种实时宽带多媒体信息服务， 可以根据用户的要求，从信息源筛选出用户选择的节目，通过通信 网的传输，分发到用户终端设备上，供用户观看。这种服务是实时 的，具有交互性。在i p 网络上实现的视频点播( v o d ) 有着数据 笫l 撕 北京交通大学硕士论文v o d 覆盏网络组遵坚堡堕塑堕箜堕堕塞 共享率和减小用户缓存要求。但是其性能仍一定程度上取决于时间槽的选择。 为了提高灵活性，有多种a d a p t i v eb a t c h i n g ，可以根据平 均请求到达率，流行度等参数动态决定对不同视频文件采用不同 b a t c h i n g 时间槽，最小化所需流的数目。在d r b a t c h i n g 前提下提出自适应机制，使系统自己选择 b a t c h i n g 时问，可以通过算法使资源共享与实时性这对矛盾得到 较好的折中，提高系统性能，但系统复杂性也进一步提高。 b a t c h i n g 与a d a p t i v ep i g g y b a c k i n g 结合，在延迟和减少所 需带宽之间取得折衷，最小化所需流的数目，但播放质量的变化 仍不易解决。 对不同节目的请求，提出p a t c h i n gf i r s t 策略，对所需 p a t c h i n g 时问最短的流优先调度，以免错过允许p a t c h i n g 的时 间，导致要建立开销更大的新的组播流。 d o u b l ep a t c h i n g 提出s h o np a t c h i n g 流和l o n gp a t c h i n g 流。在时间槽内用s h o r tp a t c h i n g ，下一个时间槽开始时到达的 新请求，对其前一个时间槽末端的p a t c h i n g 流加长，使两个请求 可以共享一个p a t c h i n g 流，为1 0 n gp a t c h i n g 流，减少服务器资 源访问次数，延长可p a t c h i n g 的时间，使需要的新组播流减少， 但是会使组播组中有些用户所需缓存增加。 b a t c hp a t c h i n g 将时间槽内的用户请求适当延迟，批处理加 入合适组播流及组播p a t c h in g 流，这样在延迟和带宽利用问取得 一个折衷，获得较好性能。 第1 5 负 北京交通大学硕士论文v o d 覆盖网络组播媒体流调度策略研究 媒体流调度策略的实现一般是通过软件实现。是视频服务器 的一个进程，指挥视频服务器的工作。 作为一种算法，对于单播操作，媒体流调度策略仅仅是简单 的“先到先分配”原则，复杂性最小。而对于组播操作，媒体流 调度策略决定用户如何分组，对请求队列如何排队成为服务队列， 对用户组采用何种方式传送视频流等，是v o d 系统的重要组成部 分。 v c r 的实现也是一种算法，是媒体流调度策略的一部分，对 于原先不提供v c r 操作的v o d 系统来说，可以使用v o d 系统所用 媒体流调度方法中媒体流发起部分实现，或者使用单独的媒体流 调度方法，不过一般都是在原有媒体流调度策略基础上对相应操 作添加相应的调度策略。然而，大部分v o d 系统不提供这种交互 操作，但随着流媒体技术和网络技术的发展，v c r 操作将是v c d 系统不可缺少的一部分。 1 2 覆盖网络组播技术 组播是一到多或多到多的多方通信方式，现代通信用组播技 术达到节省带宽，资源共享的目的。 目前，现有i p 网络上的v o d 系统多数都是基于单播，广播显 然无法在i n t e r n e t 上实现，效果也不理想。而理论上，i p 组播 是发送大数据量，大用户量流数据的最好办法。i p 组播已经发展 多年，将用户分为组播组，用i p 组播地址标识，利用路由器完成 数据寻址和转发控制。但i p 组播要求网络中每台节点路由器都具 有组播功能，但由于目前对组播业务的管理缺乏有效解决方案， 第5 负 北京交通大学硕士论文v o d 覆盖网络组播媒体流调度策略研究 务能力最大化的问题。在中大型v o d 系统中，合适的媒体流调度 算法能够带来服务能力数量级的提高。 1 3 1v 0 d 系统应用前景 v o d 系统作为一种新兴的交互式视频业务，其应用前景广阔。 目前主要的应用方向有：电影点播服务、卡拉o k 点播系统、远程 教学、远程购物、交互式电视、新闻服务、交互式广告服务和交 互式电子游戏服务等。 目前，国内出现的商业软件主要集中在前3 种应用，其成品 有待进一步完善，其应用广度有待进一步发掘。v 0 d 技术虽然日 趋成熟，但其在具体应用环境中仍有需要不断改进成熟的地方， 而且v o d 系统的应用环境本身也在不断起变化，v o d 技术也要适 应其环境做出适当的修改。 v o d 系统结合组播技术，将对一段时间内( 时间槽) 点播同 一节目的用户请求批处理，则在正常播放期间，服务器只需分配 一块以前为一个用户服务分配的资源，就可以为多个用户服务。 这样有效利用了资源，却使v o d 系统复杂性随系统服务的用户数 增加而增加，不仅要有对点播同一视频节目请求的调度，还有点 播不同节目的先后处理问题，因此媒体流调度策略的合理与否， 成为 x 北京交通大学硕士论文v 0 d 覆盖网络组插媒体流调度策略研究 评价。由摩尔定律，服务器的性能不断提高，其容量亦不断提高。 在服务器性能和容量不断提高的今天，带宽越来越成为v 系统 的瓶颈。但实际上带宽不可能无限的扩大，因此提高带宽的利用 率是解决这个问题的关键，另一方面由于信息量的急剧扩大和人 们对服务信息需求量的不断扩大，使得资源节目数量的增多远超 服务器容量的增加，特别是相对于高速存储介质的增加，资源的 调度策略能很好的解决这个问题。一般视频服务器性能和容量的 提高，是从硬件性能的提高角度来说，资源调度策略从非硬件性 能的手段来提高服务器的性能，采用合理的资源调度策略有利于 提高系统的性价比。现在，国内的大多数的v o d 系统，大都只注 重其服务器硬件性能的提高上，忽略了从其它非硬件的技术手段 来提高v o d 系统的性能。 1 3 2v o d 覆盖网络组播下媒体流调度策略的现状 现有媒体流调度策略几乎都是在单播或i p 组播基础上发展 起来的，不能完全适应覆盖网络组播环境，实时性不是很好，也 无法体现它的优势。 已有覆盖网络组播下媒体流调度策略，都是将现有组播下媒 体流调度策略针对覆盖网络组播的特点进行了组合或者改进，主 要是在如何利用客户端的资源上，从而减轻服务器压力和网络丌 销。一般的思想都是利用用户的缓冲区缓存大量数据，以做为分 散的数据源，并且保证播放连续性，这样需要合理的覆盖网络组 播协议支持，因此目前还处于实验阶段，并且倾向于应用在实况 转播这种短期内点播率很高的应用中。实况转播这种环境和v o d 第8 负 北京交递大学硕士论文v o d 覆盖嗣络维播媒体流调度策略研宠 有一定相似之处，但也有很大不同，不仅不能提供v c r 操作，而 且短期内很高的点播率必然只能说是v o d 应用的某一特定时期， 人们向往的是大范围的，更自由，交互性强的v o d 应用，所以对 于覆盖网络下v o d 系统媒体流调度策略的研究一直是研究人员感 兴趣的课题。 1 3 3 覆盖网络组播与v o d 系统结合的优势 覆盖网络组播应用于v o d 的优势在于：不存在路由器不具有 组播功能的限制，而且用户端系统在缓存一段数据的同时，也可 以分散存储数据作为数据源，充分利用这个特性，如果数据可以 一级级存储，必然可以减少所需组播流数目，简化媒体流调度策 略。减轻服务器压力和网络开销。并且覆盖网络组播技术实现比 i p 组播相对简单，不用改变底层网络结构，更便于v o d 系统大面 积服务的实现。 1 3 4 研究v o d 覆盖网络组播下媒体流调度策略的意义 覆盖网络组播与v o d 系统的结合，需要以用户主机构造组播 树，作为数据存储和转发的节点，将时间槽内，对同一视频节目 提出播放请求的用户分为一组，构建组播树，用户在接收数据后， 播放自己要观看的部分，并由服务器分配，暂时存储一部分数据。 当有用户点播同一视频节目，服务器根据点播点通知他连入合适 的用户主机获取数据。结合覆盖网络组播技术，但主机的不确定 性造成组播树中的节点随时可能离丌组播组，尤其对于每个非叶 子节点的离开，使其下面的节点暂时失去数据源，而用户组重新 第9 北京交通丈学硕：t 论文v 0 d 覆盖网络纽插媒体流调度策略研究 连接合适的节点所需的时间，都有可能造成受影响节点播放的中 断，而以往媒体流调度方法都没有对此做出有效地保护，导致覆 盖网络组播下的v o d 系统一直很不稳定，无法进行实际应用。所 以需要有具体措施保证用户端视频播放的连续性。针对覆盖网络 组播环境，改进媒体流调度策略，将有效提高v o d 系统的性能， 进一步使实现大范围实时的视频点播服务成为可能。 1 4 论文所研究内容及文章结构 本文在分析比较现有组播下v o d 系统媒体流调度策略，并结 合覆盖网络组播技术的基础上，整合多种流调度策略的优势，提 出一种覆盖网络组播环境下的媒体流调度策略，解决覆盖网络组 播下组播树节点不稳定对v 0 d 带来的问题。并针对v o d 系统中的 v c r 操作的特点和现有实现方法，提出组播v c r 操作，实现v 0 d 系统的交互性，进一步提高v 系统的整体性能，得到优化的完 整媒体流调度策略。并且，为了充分利用现有i p 组播的某些优势， 我们的研究不仅要可以应用于覆盖网络组播环境，还可以应用于 现有i p 组播环境，尤其对于覆盖网络组播和i p 组播结台的业务 环境可以发挥更大的效果，最有效的利用网络资源和缓解服务器 压力。具有良好的实时性和交互性。为在现有i p 网络上实现稳定、 高效的视频点播业务，提供完整的解决方案，并指出的合理的发 展方向。 本文第一章简单介绍了v o d 系统与覆盖网络组播技术，并分 析了选题背景和意义，提出论文研究内容；第二章分析了现有的 主要媒体流调度策略和v c r 操作的实现方法，并描述了v o d 系统 第1 0 页 北京交通大学硕士论文v 0 d 覆盖网络组播媒体流调度策略研究 用户请求规律；第三章分析了现有覆盖网络组播技术及其应用： 第四章详细描述了v o d 系统覆盖网络组播下媒体流调度策略的设 计，组播v c r 实现方法的设计，以及两者结合，并对各算法进行 了分析；第五章对该媒体流调度策略实现提出了优化方法，第六 章总结了论文的研究成果并提出下一步工作计划。 第1 1 页 北京交通大学硕士论文v o d 覆盖闷络组播媒体漉调度策略研究 第二章v o d 媒体流调度策略及分析 2 1 媒体流调度策略概述 目前，结合组播实现的媒体流调度方法主要有：a d a p t i v e p i g g y b a c k i n g ，分层传输技术，b a t c h i n g ，p a t c h i n g 等。现有 的研究也都是在考虑视频服务器性能要求，网络资源和用户缓冲 区容量限制的基础上，对这几种技术或加入自适应机制以提高灵 活性，或倍速传输提高效率，或相互结合，以及流分离合并技术 及其协议( s p l i ta n dm e r g ep r o t o c 0 1 ) 减少流数目，使性能得 到综合性提高。 2 1 1a d a p t i v ep i g g y b a c k i n g 策略及优缺点分析 a d a p t i v ep i g g y b a c k i n g 策略是对每个到来的用户请求立刻 建立一个单播流。在一段时间内，相同点播请求的每个流传输不 同帧率的所需视频节目，各个流问相互侦听传输情况后到达的 请求所建立传输的文件帧率较低，则播放的视频质量比最先建立 的流较低，之后将后到达的请求和先到达的请求的两个视频流， 在接收到的播放点相同时，以最先建立的流为主流进行合并，得 到一个组播流。这种调度策略保持了实时性，在不影响q o s 的情 况下减少了信道需求，但是当点播请求密集到达时将可能造成视 频服务器负荷过重，他还要求视频服务或者预先存储一个视频文 件不同帧率的多个副本，或者可以实时改变视频文件的帧率，前 者占用大量服务器硬盘空问，可以只对某几个热门节目使用，后 北京交通大学硕士论文v o d 覆盖刷络组插媒体流调度策略研究 者对服务器要求较高。并且两个流合并时，容易产生视频质量突 变，在客户端需要相应的缓冲平滑处理。 分层传输技术可以认为是a d a p t i v ep i g g y b a c k i n g 思想的改 进，但相比较而言，实现更加简单一些。对于一个视频节目，分 层传输技术要求在服务器处保存的是一个基础流文件( 包含保证 基本播放质量所需信息) 和一系列增强流文件。传输时，在基础 流上用插帧技术叠加不同级别的增强流，得到相应不同级别的视 频播放效果，可以由服务器或者下面的某些有此能力的节点决定 需要或丢弃哪些流。当用户逐渐离开组播组，组播组成员为0 后， 释放组播流。这种方法要求多占视频服务器存储空间，并且在不 同级别视频流的交界处，也会产生播放质量突变，需要相应的缓 冲平滑处理。 2 1 ，2b a t c h i n g 策略及优缺点分析 b a t c h i n g 就是批处理，是以一段时间( 称为时间槽) 为界， 对这段时间内到达的请求，延迟先到的用户请求，不建立任何流， 而是将界限内到达的所有请求分为一组，在时间界限终点处建立 并发送一个组播流。这样由时间槽长短来决定系统b a t c h i n g 性 能。对于多个不同请求组优先处理哪个，可以采取策略：先来先 服务( f c f s ) 、最大队列长度( m q l ) 、最大加权队列长度( m f q l ) 和 最大撤销概率( m d p ) 等。这种调度方法简单，但是引入了一定延 迟，系统性能优劣主要由时间槽及其采用的组处理策略决定。 第1 3 负 北京交通大学硕士论文v o d 覆盏网络组遵坚堡堕塑堕箜堕堕塞 共享率和减小用户缓存要求。但是其性能仍一定程度上取决于时间槽的选择。 为了提高灵活性，有多种a d a p t i v eb a t c h i n g ，可以根据平 均请求到达率，流行度等参数动态决定对不同视频文件采用不同 b a t c h i n g 时间槽，最小化所需流的数目。在d r b a t c h i n g 前提下提出自适应机制，使系统自己选择 b a t c h i n g 时问，可以通过算法使资源共享与实时性这对矛盾得到 较好的折中，提高系统性能，但系统复杂性也进一步提高。 b a t c h i n g 与a d a p t i v ep i g g y b a c k i n g 结合，在延迟和减少所 需带宽之间取得折衷，最小化所需流的数目，但播放质量的变化 仍不易解决。 对不同节目的请求，提出p a t c h i n gf i r s t 策略，对所需 p a t c h i n g 时问最短的流优先调度，以免错过允许p a t c h i n g 的时 间，导致要建立开销更大的新的组播流。 d o u b l ep a t c h i n g 提出s h o np a t c h i n g 流和l o n gp a t c h i n g 流。在时间槽内用s h o r tp a t c h i n g ，下一个时间槽开始时到达的 新请求，对其前一个时间槽末端的p a t c h i n g 流加长，使两个请求 可以共享一个p a t c h i n g 流，为1 0 n gp a t c h i n g 流，减少服务器资 源访问次数，延长可p a t c h i n g 的时间，使需要的新组播流减少， 但是会使组播组中有些用户所需缓存增加。 b a t c hp a t c h i n g 将时间槽内的用户请求适当延迟，批处理加 入合适组播流及组播p a t c h in g 流，这样在延迟和带宽利用问取得 一个折衷，获得较好性能。 第1 5 负 北京交通犬学硕士论文v 0 d 覆盖网络组播媒体流调度策略研究 应组播环境，造成如果v o d 系统提供v c r 操作，就导致总体性能 严重下降。 将来网络的发展必然要求v c r 这种交互性操作的参与，越来 越多的v o d 系统希望可以加入v c r 功能，然而效果都不理想，所 以对于这一方面的研究一直是v o d 领域的不足。 2 2 3v c r 操作实现 v c r 操作的实现分两个部分，v c r 过程的进行和恢复j 下常播 放。前者一般需要在专用信道提供一个单播，为了处理随时可能 发生的恢复播放操作，采用s p l i ta n dm e r g e ( s a m ) 协议，并引入 一些控制；后者等同于点播，可以采用点播节目的流调度策略， 此时实时性和连续性显得更重要一些。并且由于常常要从视频文 件中间开始传送，必然受媒体流文件在服务器处存储方式的限制， 比如文件分割粒度等。 暂停操作开始时，因为用户缓冲区有恢复播放需要的数据， 只要侦听相邻组播流的情况，准备随时加入最近的组播流，如果 没有合适的，建立一个新的组播流。 快进操作有多种方法，可以利用缓冲区数据进行有限快进； 可以建立专门的单播流，发送所需文件或已处理过的快进文件。 而快退只能建立单播流发送所需文件或已处理过的快退文件。处 理过的快进、快退文件一般是将原文件抽取某些帧的复本，可在 正常帧率播放时达到快进效果，以减少带宽消耗，但会额外占用 l 3 服务器硬盘空间，所以只对热门影片或v c r 操作频繁的视频 才使用。快进和快退恢复播放时，要尽快并入合适的组播流，可 北京交通大学硕士论文 v o d 覆盖同络组播媒体流调度策略研究 第三章覆盖网络组播技术 3 1 覆盖网络组播概述 覆盖网络组播的基本思想是：保持互联网原有的简单、不可 靠、单播的转发模型，然而，它有一些假设： ( 1 ) 网络的带宽和转发资源相对丰富，服务器能力是主要瓶 颈： ( 2 ) 组播组成员可贡献资源用于转发； ( 3 ) 应用对性能要求并不苛刻，可容忍报文丢失和较大延迟。 因此，覆盖网络组播并不像i p 组播那样，数据报在路由器进 行复制转发，由端系统( e n ds y s t e m ) 实现组播转发功能，数据在 端系统上复制并转发，同时端系统也负责组播组成员的管理。端 系统在逻辑上组成了一个叠加网络拓扑。一般来讲，端系统就是 用户主机。 覆盖网络组播中，当有一个节点加入，有可能加入组播树本 身的叶子节点，也有可能加入中间某个节点，同时，可能就这一一 个节点加入，还可能这个节点是一组节点的根节点。各个加入组 播树的节点由服务器根据其主机性能和网络情况分配存储一部分 数据；来有效利用用户资源，缓解服务器压力和网络开销。当有 一个节点离开，若由他通知服务器自己的离开，服务器立刻将受 影响的用户组连入合适的节点继续接受数据；若是出于突发状况 或网络中断导致离丌，则服务器在一个询问周期内没得到应答， 才改变受影响用户组的接入节点，后者很有可能使网络通信产生 中断。可见，任何一个节点的加入和离丌都可能造成网络拓扑结 笫2 0 负 北京交通大学硕士论文v o d 覆盖网络组撬媒体流调度策略研究 构的改变。 3 2 与以往组播的比较 i p 组播同覆盖网络组播组播树的不同如图3 一l 所示： 图3 1i p 组播树与覆盖网络组播树的不同 在网络资源占用上，对简单单播、i p 组播和覆盖网络组播进 行比较。假设s 为服务器，现在有三个用户c 。c 。，c 。，和两个路 由器r 。r 2 ，链路连接如图3 2 ( a ) 所示，r ，r ：之间的链路花费 较高为5 ，其他链路上的花费均为l 。 ( b ) 第2 1 负 北京交通大学硕士论文 v o d 覆盖网络组插煤体流调度策略研究 ( d ) 图3 2 简单单播、i p 组播和覆盖网络组播比较 图3 2 ( b ) 描述了简单的单播传输。可以看出在靠近服务器的 链路上出现了非常大的数据传输冗余，即链路s r 上有三份相同 的数据传输，尤其是在链路花费高的链路( r 。一r ：) 上也出现重复的 数据传输，造成整个链路花费太高。 图3 2 ( c ) 描述了用d v m r p ( d i s t a n c ev e c t o rm u l t i c a s tr o u t i n gp r o t o c 0 1 ) 协议构造的一个i p 组播树。可以看到i p 组播有效 地避免了冗余的数据传输，并且在每一个物理链接上仅有一个数 据传输。同时也使每个接j | 曼者获得了和单播同样的低延时。 图3 2 ( d ) 描述了用覆盖网络组播协议构成的一个叠加组播 树。和图3 2 ( b ) 使用的简单单播技术相比较，在临近服务器的链 路s r 上只出现了2 次相同的数据传输，同时在花费较高的链路 r 一r 。上并没有出现数据传输冗余，并且可以看出不需要任何的网 络底层改变，也可以实现比较有效的组播传输。 第2 2 负 北京交通大学硕士论文v o d 覆盖同络纰捅媒体流调度策略研究 可见简单单播是最耗费网络资源的，而i p 组播是实现大数据 量传输的最好方法，然而对路由器的要求使得这种方法局限性太 大，覆盖网络组播对网络资源的消耗介于两者之间，但实现比i p 组播灵活，也更简单的特点使其受到相当的重视。 比较之下，覆盖网络组播的优点有：只需改变端系统，便于 实现和推广；便于针对特定应用优化。它的缺点为：一般比i p 组播使用更多网络资源；端系统可能不稳定，导致组播的可靠性 受影响；端系统性能无法保证，可能导致延迟、转发速率等性能 的下降。 3 3 覆盖网络组播的实现 由各种覆盖网络组播协议来构建不同的组播树，实现覆盖网 络组播传输。 覆盖网络组播协议通常把组成员组织成两个逻辑拓扑：控制 拓扑和数据传输拓扑。拓扑上的每条边都相当于一条单播连线。 控制拓扑主要用来在端系统问周期性的交换控制信息，以便发现 和恢复由于一些成员的非法离开而造成的拓扑破坏。数据拓扑通 常是控制拓扑的一个子集，主要用来表明数据包的传输路径，实 际上。数据拓扑一般是树形结构，而控制拓扑要求有更多的连接， 则通常时一个网状拓扑结构。因此，根据构建控制拓扑和数据传 输拓扑的顺序，可以将目前网络层组播协议的实现方法分为：网 状拓扑优先方法、树状拓扑优先方法以及隐式方法三大类。 第2 3 负 北京交通人学硕l j 论文v o d 覆盖网络组播媒体流调度策略研爨 3 3 1 网状拓扑优先方法 在此类方案中，组成员首先自己组织成一个网状的拓扑，即 控制拓扑，每两个成员之间有多条路径。在这个网状拓扑中，每 个成员都会保存这个组中其他所用成员的状态信息，而这个信息 将会得到周期性的更新。 目前较成熟的此类协议有n a r a d a ，是由c m u 组播通信组开发 的最早的覆盖网络组播协议之一。 3 3 2 树状拓扑优先方法 与网状拓扑优先不同的是，基于树状拓扑优先的端系统，组 播协议会首先建立起一个共享的数据传输树拓扑，然后根据这个 树状拓扑增加一些成员间的连接，便可以形成控制网络拓扑。 此类比较有代表意义的挤议有y o i d 和h m t p 等，其中y o i d 也是一个出现的较早的覆盖网络组播涛议。 3 3 3 隐式方法 这类方法目前还没有严格的定义，虽然出现了一些基于隐式 方法的组播方案，但是都还处于研究和发展阶段，不太成熟。因 此，这里主要介绍一种相对有代表性的方法：基于层次结构的覆 盖网络组播。 此方案把所有用户主机组织到一个层次拓扑结构中，所有成 员节点都以簇的形式组织到第o 层( 1 a y e r0 ) 中。每个簇包翕一 组互相距离相近的点( 根据不同的实际需要。距离可以有不同定 第2 4 _ ! i f 北京交通人学硕士论文v 0 d 覆盖网络组播媒体流调度策略研究 义，例如：带宽、延时等) 。每个簇都会有一个中心( 即图论中的 中心，这个中心具有最小的到簇内其他节点的最大距离) 。这个中 心点非常重要，能保证新加入节点在通过最少的查询后，找到合 适自己的簇。将这个中心选出，让每个簇中的中心组成第一层 ( 1 a y e r1 ) 。以此类推，最高层则只有一个成员。归纳以上，可 以简单的用以下几条性质来描述： ( 1 ) 一个成员在每一层只能属于一个簇； ( 2 ) 如果某个成员出现在了l 层，那么它也一定出现在 l 。，l 0 层。实际上，它也是这些层所在簇的中心点； ( 3 )如果某成员没有出现在l 层，那么它也不会出现在 l j 层，其中j i ； ( 4 )每个簇的大小都限制在( k ，3 k 1 ) ，k 为常数。其中 中心正是簇在图论中的中心点； ( 5 ) 整个层次结构最多有l o g 。n 层，且最高层只有一个成 员。 3 4 覆盖网络组播研究应用 树状拓扑实现简单，维护开销小，扩展性好，但可靠性较差。 网状拓扑可靠性较高，但维护歼销较大，扩展性较差。一般大组 播组中使用树状拓扑优先，在中小组播组中使用网状拓扑优先。 如何结合树状拓扑和网状拓扑的优点值得研究。 覆盖网络组播应用中的安全性问题也是一个值得深入研究的 问题。i p 组播中安全就十分重要，覆盖网络组播中数据通过可信 度不高的主机转发，安全更为重要。覆盖网络组播中的安全包括： 第2 5 负 北京交通大学硕士论文v 0 d 覆盖网络组捅媒体流调度策略研究 加入组播组控制；对读取组播组内传递的数据控制；避免转发数 据被篡改。前两个问题可通过在r p 增加机制解决，解决第三个 问题比较困难，还在研究之中。 目前覆盖网络组播研究集中于视频会议系统、媒体流的分发 系统( 如视频广播) 和订阅分发系统( p u b l i s h s u b s c r i b e s y s t e m ) 等。它主要用于实时的多媒体传输，这利用了多媒体信 息的性质，即在传输链路质量下降时，用户仍可利用收到的低速 率或者不完整的信息；也发挥了组播“时问上集中、空间上分布” 的特点。 第2 6 页 北京交通大学硕士论文v 0 d 覆盖刚络组捕媒体流调度策略研究 4 2 3 用户加入过程 用户搔放请求获准后，媒体调度策略为该用户或组播组调度 媒体流。单个用户的加入和组播组的加入是类似的。 节点加入过程中，根据事件发生的概率我们知道，越是靠近 根节点的节点，能对其产生离开影响的节点越少，而叶子节点， 其到根节点路径上任意节点离开都会对其产生影响，所以对于不 同深度的节点不应该采用相同的延迟播放时间。靠近根节点的播 放延迟可以较小，逐级增大播放延迟，而叶子节点的播放延迟最 大o v o d 系统中己建立组播树如图4 2 所示： 众 a o 图4 2 用户加入过程一覆盖网络组播树 此时有用户x 和y 请求一段视频播放，请求发到视频服务器 s 处，x 所需数据在a 上可以得到，y 需要数据在d 上可以得到， s 根据他们需要的数据，令x 连接用户a 获取数据，y 连接用户d 获取数据。 第3 0 负 北京交通大学硕j 论文 v o d 覆盖网络组播雉体流调度策略研究 图4 5 用户离开过程覆盖网络组播树 不妨设定t ( t ) 为： c 】：t i ( t ) c 2 ：t i ( t ) c 3 ：t l + t ? ( t l + t 2 ) c d ：t l + t 2 ( t 【+ t 2 ) c s ：t i + t ? ( tj + t = ) c 6 ： t l + t 2 + t3 ( t 1 + t2 + t 3 ) c 7 ： t l 十t 2 + t i ( t 1 + t2 + t j ) c 8 ：t l + t z + t3 + t 4 ( t 1 + t 2 + t 3 + t ，) c 9 ：t l + t 2 + t 3 + t 4 ( t 1 + t2 + t 3 + t d ) 假设节点c ；由于某种原因突然离开，受影响的节点都是他的 下级节点c 。、c i 、c 。和c 。，如图4 6 ： 第3 5 负 北京交通人学硕： ! 论文v o d 覆盖刚络纽播媒体施调度镱略研究 图4 6 用户离开过程受影响节点 节点c 。离开的瞬间，各节点的t ( t ) 不变。 重建组播树需要时间t ，这段时间，受影响节点接收不到新 媒体流数据，只能播放自己缓冲区中的数据。则导致用户缓冲区 中存储的数据减少。缓冲区中媒体数据缺少从节点c 。离开时起， 缺少的数据量为播放时间为t 的一段。 重建组播树。假设根据一定的构建组播树的法则，与c 。播放 最相近的播放数据可以从c ，上得到，与c 。播放最相近的播放数据 可以从c 。上得到，而c ，下连接的c 。和c 。将以c ? 为根节点，跟随 c ，接入新的数据源，如图4 7 ： 第3 6 负 北京交通大学硕士论文v 0 d 覆盖网络纽播媒体流调度策略研究 图4 7 重建组播树过程 受影响节点接入新连接的瞬间，t ( t ) 为 c i ：t l ( t i ) c 2 ：t l ( t 1 ) c ： ：t l + t 2 ( t i 十t 2 ) c 5 ：t l + t2 ( t l + t2 ) c t ：t l + t 2 + t ，( t l + t 2 + t ：l t ) c 9 ：t l + t 2 + t t 1 ( t t + t2 + t 3 + t 1 一t ) 组播树稳定后，如图4 8 第3 7 虹 北京交通大学硕士论文v o d 覆盖网络组插媒体流调度策略研究 图4 8 新建的组播树( 方式1 ) 此时t ( t ) 为： c l ：t l ( t 1 ) c 2 ：t i ( t 1 ) c 3 ：t l + t 2 ( t i + t2 ) c ；：t l + t 2 ( t l + t2 ) c 6 ：t 】+ t ? + t3 ( t l + l 2 + t 3 ) c 7 ：t i + t 2 + t3 ( t l + t 2 + t i ) c 8 ：t i + t2 + t 3 + t 4 ( t l + t2 + t3 + t4 ) c 9 ：t l + t 2 + t 3 + t ( t i + t2 + t 3 + t 4 ) g e 、c i 、c s 、c 。很难能遇到接入的节点所接收的媒体流正好是 c 。离开时传输的媒体流，有两种情况： ( 1 ) 如果接入的节点中的媒体流包括c 。离开时的媒体流， 也就是说接入节点正播放的视频是c 。离开前播放过的，那么出接 入的节点直接对受影响节点组播媒体流，即c j 对g 、c i 、c 。、c 。 组播相应的媒体流，为了保证播放连续性，样需要在缓冲区存 第3 8 负 北京交通大学硕士论文v o d 覆盏剜络组播媒体流调度策略研究 储响应量的数据。 ( 2 ) 如果接入的节点中的媒体流不包括c 。离开时的媒体流， 也就是说接入节点正播放的视频是c 。还没播放过的，那么受影响 节点的缓冲区直接接收新数据源的媒体流的话，缓冲区中的数据 一定无法保证视频的完整性，会出现片断的丢失。如果仅用 p a t c h i n g 流补充，这样用户主机需要三个逻辑分割的缓存区，一 块存储正在播放的数据，一块接收组播流，一块接收组播的 p a t c h i n g 流，补充完成后再将组播流和p a t c h i n g 流中的数据排 序重组。从减少流数目方面考虑，我们结合分层传输技术重建组 播流。步骤如下： 重建组播树后，将原先的组播流释放： 向上级节点寻找包括c 。离开时的媒体流的节点，从该节点 新建一个从节点c 。离开时正传输的媒体流为起点的组播流，成员 是该节点之下级，至新建的组播树中所有受影响节点，新组播流 的组织和调度由服务器或者有能力构建组播树的节点来计算完 成。可以单独设计一个模块来执行计算； 为了补上对问差，假设根据带宽需要时间t ”长时间传输播 放t + t ”长时问的数据，如果拥有数据的节点具有对数据流的处 理能力，例如视频服务器或者是聚合点，在原有带宽基础上，用 质量较低的基础流组播一段时间，直到所有受影响节点缓冲区中 数据达到保证其播放连续性所需的播放时间的数据量，如图4 8 中t 值，则新建的组播流由t ”长时间的基础流和衔接基础流尾部 数据的币常质量的媒体流组成；如果拥有数据的节点不具有对数 据流的处理能力，采用a d a p ti v ep i g g y b a c k i n g 策略快速补充失 去的数据，直到所有受影响节点缓冲区中数据达到保证其播放连 鹅3 9 砸 北京交通大学硕士论文v 0 d 覆盖网络组播媒体流调度策略研究 续性所需的播放时间的数据量，同样如图4 8 中的t 值，则新建 的组播流传输速率是正常传输速率的( t + t ”) t ”倍，传输时间 为t ”之后用j 下常速率传输视频流。在补充失去数据的这段期间， 新数据源下没有受影响的节点，将新建组播流中自己已有的播放 数据丢弃，播放自己缓冲区中的数据。 这样所有用户主机从加入组播树稳定后起，链路上只有一个 流，并且一个节点只接收一个组播流，用户缓冲区只需要两块逻 辑分块，一块存储正播放的数据，一块接收组播流。 但是，如果重建组播树的方法不同，t ( t ) 有可能不同。例 如用图4 9 方式重建连接， 图4 9 新建的组播树( 方式2 ) 这时，根据节点所处位置，t ( t ) 为： c ，：t ，( t ；) c 2 ： tj ( t i ) c 虻t + t 2 ( t + t 2 ) c j ：t l + t 2 ( t i + tz ) c 6 ：t i + t 2 + t 3 ( t l + t2 + t ：1 ) 第4 0 负 北京交通大学硕： 二论文 v 0 d 覆盖网络纽播媒体流调度策略研究 j 非叶子结点离开 皇 确定离开l 结点位置 - - - - - - - - - - - - r - - - - - - - - - - ，j l 离开结点 位置信息 鬯 组播组 成员信息l 计算播放 延迟模块 播放延迟 重建组播流 分层传输技术补充失去数据 未受影响用户丢弃重复数据 正常传输 图4 l o 非叶子节点离开过程流稗圈 用户离开过程完整流程图如图4 一l l ： 第4 2 仉 结点离开时正传输的数据点 北京交通大学硕士论文v o d 覆盖网络纰橘媒体流调度策略研究 图4 1 l _ i = i j 户离开过程完整流程图 4 2 5 计算播放延迟 前面提到，计算播放延迟是一个递增的收敛的数列 t 。，t + t ：，t - + t z + t ”，t l + t ：+ t 。+ + t 。 ，我们称为播放延 迟数列，这个数列中t 。的值是最后得到用户播放延迟的关键，由 数列收敛可知，存在整数n ，当i n 时，t ，= 0 。 计算t 涉及到多方面因素： ( 1 ) 构建组播树的方法。一般构建组播树的方法决定后，组 织组播树的个体( 服务器或者构建组播树的节点) 决定不同个数 的非叶子节点离丌时，重建组播树需要的时问，可以用t 表示有i 第4 3 贝 北京交通大学硕士论文v 0 d 覆盖网络组播媒体流调度策略研究 个非叶子节点同时离开时，重建组播树的时间，i 总是小于组播树 所有节点总数。这些值在不同组播树中是不同的。 ( 2 ) 用户主机状况和用户所处位置到组播树根节点路径上的 网络状况。 在用户加入组播树时，将提供自己的缓存，处理能力等情况。 根据网络v o d 系统运行期问的先验数据来估计网络状况，并周 期性更新。例如：某段网络上频繁出现断线，那么这段网络上 的多个用户同时断线的概率高，否则，概率低。 用一系列概率值来表示用户突然离开的可能性大小。用户所 处于组播树的根节点将对组播树中用户主机状况，和所处位置的 网络状况进行综合评估，得到出现突发状况导致用户突然离开的 概率值，用p 。表示，c 表示组播树中某个用户。 对于用户节点c ，其到组播树根节点之间路径上的节点数在其 加入组播树时已经决定，设为m ，这m 个节点离开的概率不同，根 据m 个点的p c ，我们可以得到多个节点同时离开的概率的平均值， 设为q ，( j 为自然数，且0 j m ) ，这一系列值存储在根节点中，维 系一个概率表，包括每个节点的q ，定期更新，并且当组播树成员 改变时也进行更新。与其具有相同父节点的用户节点有相同的q 值。 由以上数据将可以得到t 的值如下： t = ( 1 一i 1 ) q ，( 其中i ，j 为自然数，j i ) ( 公式4 1 ) 最后，将由t ，得到所求播放延迟数列，这个数列在用户加入 时计算得到，并随组播树的改变而不断更新。 往往用户加入时，如果已有兄弟节点的存在，则根据自己的 笫4 4 负 北京交通大学硕士论文 v o d 覆盖网络组插媒体漉调度策疃! ! 塑 位置信息就可以查找到所需的播放延迟，而不需要计算，只有在 没有作为叶子节点加入时才需要计算，并且只需要计算自己所处w 位置的深度i 的t 即可，所需的播放延迟就是其父节点的播放延迟 与t 。的和。 计算播放延迟的结构图如图4 一1 2 ： 结点位置 1r 结点离开 i 播纛迟罔鬈鬻巽 1播放延迟 4 2 6 算法评价 图4 1 2 计算播放延迟结构图 采用这种调度方法，减少了用户平均等待时间，并且所有用 户从加入组播树稳定后起，自始至终只需要两块逻辑缓冲区就可 以了。一块存储证搔放的数据，一块接收组播流，并且一个节点 只接收一个组播流。 计算播放延迟增加了系统的复杂性，对服务器或者组播树构 造节点的计算能力有一定要求。 以上媒体流调度策略尤其符合