（通信与信息系统专业论文）vbr视频流的调度和传输.pdf

v b r 视频流的调度和传输 摘要 连续媒体的存储和传输是多媒体点播系统的关键技术，在一定的 服务质量要求下提供大量的、并发的连续媒体流是设计该系统的主要 目标。连续媒体的播放具有严格的连续性、实时性和时序性等特点， 而有限的系统资源，如磁盘带宽、磁盘缓存和网络带宽往往成为改进 系统综合性能的瓶颈，再加之v b r 视频流的大量应用更是给有限资源 和连续播放带来了挑战。因此，本文主要针对变比特率视频流的磁盘 i o 调度、网络传输以及流本身的预测等几方面进行研究。 v b r 视频流的突发性和白相似性，给视频服务器系统有限资 源一一磁盘i o 带宽和缓存容量的分配带来很大的挑战。数据从 磁盘到缓存的调度方式将在很大程度上影响服务器系统整体性能的 提高。为此，本文通过建立过程周期模型和即时周期模型，对v b r 视 频流分别进行了基于在线测量和基于等效带宽的调度与接纳研究。算 法以提高服务器的磁盘i 0 带宽和缓存的综合利用率为目的，以在线 测量剩余系统资源和周期容限为依据，对调度周期进行动态调整，使 得系统所剩资源处于一种动态的平衡过程，避免了单一资源持续成为 瓶颈而浪费其它系统资源，从而大大提高了有限资源的利用率、并发 流数和算法的可实现性。 网络带宽的有限性也给v b r 视频流的传输带来了不容忽视的挑 战。本文从两方面研究了v b r 视频流在有限带宽网络的传输问题。一 是通过对视频内容的运动复杂度和人眼对视频内容的惰性的分析，根 据视频流本身的特性和丢帧历史实时调整各流的丢帧优先级，在网络 负载加重时适当丢弃一些b 帧，以提高网络的利用率和接纳率。另一 方面，通过对v b r 视频的编码结构、内容相关性、码流统计特性以及 镜头切换的分析，研究了i 帧、p 帧、b 帧各自的相关性以及它们之 间比例的统计性、跟踪性，提出了针对不同类帧的基于帧间比例的预 测( i f p p ) 算法，并以预测结果为依据为视频流动态分配网络带宽， 仿真结果表明，该算法不但大大改进了基于g o p 问参考的预测( i g r p ) 算法的性能，而且明显降低了v b r 视频流的突发性和自相似性对网络 缓存和排队性能所造成的影响。 接下来，研究了变比特率数据流在w e b 服务器的接纳过程。通过 对w e b 服务器的负载特点、到达率以及文件大小分布的分析，提出了 基于在线测量的w e b 服务器接纳控制算法。该算法在接纳过程中以负 载及其变化率为依据，利用模糊逻辑在线调整测量窗口的大小，从而 最大限度地提高w e b 服务器资源的利用率。 在论文的最后，简要介绍了我们实验室开发的宽带多媒体应用平 台。 关键词：接纳控制v b r 动态调度周期在线测量自相似预测 s c h e d u l i n ga n dt r a n s p o r t o fv b r d e os t r e a m s a b s t r a c t s t o r a g ea n dt r a n s p o r to fc o n t i 肌o u sm e d i a a r em ek e yt e c h n i q u e so f am u l t i m e d i ao nd e m a n d ( m o d ) s y s t e m t h ed e s i g no b j e c t i v eo fa n m o ds y s t e mi st op r o v i d eal a 唱ec o n c l j r r e n tm e d i as t r e 锄su n d e ra r e q u i r e dq o s s t r i c t c o n t m u o u s ， r e a l t i m ea n dt e m p o r a lc o n s 仃a i n t c h a l l e n g e st h ep l a y b a c ko fc o n t i m l o u sm e d i au n d e r1 i n l i t e dr e s o u r c e s ， e 8 p e c i a l l yf o rl a r g e 印p l i c a t i o n so fv b rv i d e o h o w e v e r ，l i m i t e ds y g t e m r e s o u r c e ss u c ha sd i s kb a n d w i d t h m e m o a n dr l e t w o r kb a n d w i d 也 s o m e t i m e sc a l l s eb o t t l e n e c k d u r i n gi m p r o v i n gs y s t e mi n t e g r a t e d p e r f i o r m a n c e t h e r e f o r e ，d i s k i o s c h e d u l i n g ，n e t w o r k 打a n s p o r ta n d s 订e 锄p r e d i c t i o nf o rv b rv i d e os 仃e a m sa r em a i na s p e c t so fr e s e a r c h e s i n t l l i s p a p e r b u r s 恤e s sa j l ds e l f s i m i l a r i t yo fv b rv i d e os t r e a m si n l p o s eg r e a t c h a l l e n g e s o nt h ea l l o c a t i o no fl i m i t e dr e s o u r c e ss u c ha sd i s ki o b a n d 埘d t ha n dm e m o q t h es c h e d u l i n gm e t l l o do fd a t af r o md i s kt o m e m o r y w i l l h e a v i l y a 舭c t sm ei m p r o v e m e n to f 、v h 0 1 e s y s t e m p e r f b r n l a n c e s o ，b yc o n s 虹u c t i n gp r o c e s s p e r i o dm o d e la n di n s t a n tp e r i o d m o d e l ，w ep r o p 0 8 e do n l i n em e a s u r e m e n tb a s e da 1 1 de f f e c t i v eb a l l d 晰d 血 b a s e ds c h e d u l i n ga n da d m i s s i o na l g o r i t h m sf o rv b rv i d e os t r e a m s f o r t h ep u r p o s eo f e 1 1 1 1 a n c i n gi n t e g r a t e du t i l i z a t i o no fd i s ki 0b a n d w i d ma 1 1 d m e m o r yo ft h es e r v e r ，s c h e d u l m gp e r i o d sa r ea d j u s t e dd y n 锄i c a l l yb y o n l i n em e a s u r e m e n to nr e s i d u a ls y s t e mr e s o u r c e sa n dp e r i o dt o l e r a n c e ， a sar e s u l t ，r e s i d u a ls y s t e mr e s o u r c e sa r ei nas t a t eo fb a l a n c ea n do n e r e s o u r c es e j d o mk e 印sb o 仕l e n e c ka n o t h e rk e 印s s u 叩i u sa l la l o n g i n w o r d s ，m eu t i l i z a t i o no fl i m i t e ds y s t e mr e s o u r c e sa n dt h en u m b e ro f c o n c u r r e n tc i i e n t sa r el a r g e l ye n h a n c e d ，a l s ot h er e a l i z a b i l i t yo fa l g o r i t i so b v i o u s l ym a d ei no u rs i m u l a t i o n l l m l t e dn e t 、v o r kb a n d w l d t ha l s oc a u s e si m p o r t a n tc h a l l e n g eo n t r a n s p o r to fv b r v i d e o i n 血i sp a p e rt w oa s p e c t so ft r a n s p o r tp r o b l e m s f o rv b rv i d e oa r es t u d i e du n d e r l i m i t e dn e t w o r kb a l l d w i d 廿1 0 nt 1 1 eo n e h a n d ，o nt h ea n a l y s i so ft h em o t i o nc o m p l e x i t yo ft h ev i d e oc o n t e n ta 1 1 d v i s u a l 抽e r t i ao fm a n se y e s ，t h ep r i o r i 够o fd r o p p i n g 丘锄e sf o re a c h s t r e a mi sa d j u s t e da c c o r d i n gt oi t so w nc h a r a c t e r i s t i ca n dd r o p p i n gf r 锄e s h i s t or y w h e nn e t w o r kl o a dg e t sh e a v i e rs o m eb 行a m e sa r ed r o p p e ds oa s t oe n h a n c et h eu t i l i z a t i o na n da d r l l i s s i o nr a t eo ft h em u l t i m e d i an e t w o r k o nm eo t h e rh a n d ，b yt h ea n a l y s i so ft l e c o d i n gs t m c t u r e ，c o n t e n t c o r r e l a t i o n ，s t a t i s t i c a lc h a r a c t e r i s t i c sa 1 1 ds h o ts w i t c h i n go fv b rv i d e o ， t h ec o r r e l a t i o no fi ，pa n db a m e s ，s t a t i s t i c a la n dt r a c i n gp r o p e r t ya b o u t p r o p o r t i o n 啪o n gt h e ma r es t u d i e d ，r e s p e c t i v e ly t h e r e f o r e ，i n t e r f r a m e p r o p o r t i o np r e d i c t i o n ( i f p p ) a l g o r i t h mi sp r o p o s e d t 町e t w o i kb a n d 、v i d m i sd y n a m i c a l l ya l l o c a t e df o rv i d e os t r e a m sa c c o r d i n gt ot h er e s u l to ft 1 1 e p r e d i c t i o n ，i ti sp r o v e db yt h es i m u i a t i o nt h a tt 王1 ea l g o r j m mn o to n l y i m p r o v e sl 嘴e l yi n t e 卜g o pr e f e r e n c ep r e d i c t i o n ( i g r p ) b a s e da l g o r i t b u ta 1 8 0r e d u c e st h en e g 撕v ee f f e c t so nb u r s t n e s sa 1 1 ds e l f s i m i l 赫哪o f v b rv i d e os t r e a n l st on e t w o r km e m o r y 甜l dq u e u i n gp e r f o m a 工1 c e s e q u e n t i a l l y t h ea d r n i s s i o np r o c e s sa b o u tv a r i a b l e _ b i t r a t es t r e a m s o nw e bs e r v e ri ss t u d i e d o nt h ea l l a l y s i so fl o a dc h a r a c t e r i s t i c ，州v a l s r a t ea n d 靠1 es i z ed i s t r i b u t i o n ，o n _ l i n em e a s u r e m e n tb a s e da d m i s s i o n c o n 订0 1a l g o r i t h mo nw e bs e r v e ri sp r o p o s e d i nm ep r o c e s so fa d m i s s i o n c o n t r o i ，t h es i z eo fm e a s u r e m e n tw i n d o w si so n 一1 i n ea 哇i u s t e da c c o r d i n g t o 如z 纠1 0 9 i c ，w h o s et w ov a r i a b l e s a r em es i z eo f1 0 a da n dl o a d d e r i v a t i v e ，r e s p e c t i v e l y a s ar e s u l t ，r e s o u r c e su t i l i z a t i o ni s l a r g e l y i r l c r e a s e di n 、v e bs e r v e r a tt l ee n do ft h ep a p e r ，b r o a d b a f l dm u l t i m e d i a 印p l i c a t i o nw o r k s h o p i no u rl a bi sb 1 i e f l yi n t r o d u c e d yw o r d s ：a d m i s s i o nc o n t r o lv b r d y n a m i cs c h e d u l i n gp e r i o d o n - 1 i n em e a s u r e m e n ts e l f s i m i l a r p r e d i c t i o n 声明 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在年解密后适用本授权书。非保密论 文注释：本学位 本人签名： 导师签名： 适鬻权，箩日期：兰! j 二生 日期 叶k 北京邮电大学博上学位论文 第一章绪论 1 1 多媒体技术 以因特网和多媒体技术为代表的信息化浪潮正席卷全球，已经演变为一场深 刻的产业革命和社会革命。人类正在进入以信息技术为主要驱动力的“新经济” 阶段。一个国家的信息化程度，日益成为评估其综合国力和国际竞争力的标志。 早在半个世纪前，通信、广播电视和计算机还是3 个独立的技术领域，因此各具 有相应的业务范围。多媒体技术则是通信、广播电视和计算机技术的相互融合、 相互渗透的结果。进入上世纪八、九十年代，网络技术的发展和特别是i m e m e t 的爆炸式增长又给多媒体技术增添了新的生机和活力。进入2 1 世纪，随着移动 技术和网络技术的飞速发展，第三代网络技术特别是3 g 业务的即将运营和下一 代接入网和无线局域网广泛使用，将给多媒体技术的应用注入前所未有的活力， 多媒体技术的发展无疑将极大地促进社会的信息化。 多媒体技术的出现，在世界范围内引起了强烈的反响，因为它清楚地展现出 信息处理和通信技术的革命性发展方向。一方面，计算机技术已经不但具备数学 运算、文字处理、图形和动画的功能，而且还支持包括伴音在内的活动图像的存 储、处理和显示；另一方面，新的数字图像压缩技术能够将数字电视信号出原来 的2 1 6 m b s 的比特率压缩到3m b ，s 或更低。这样，包括数字电视图像信号在内 的电话、传真、图文电视、可视电话、网络流媒体等媒体业务都可以在一台终端 上得以实现，从而将通信、广播电视、计算机和网络技术领域融合到了一起，充 分体现了“多”的含义。多媒体数据是由内容文本、图形、图像、声音、动画、 活动图像等媒体数据所形成的复合数据。如果将对时间敏感的声音、活动图像的 数据称为实时数据，其它类型的数据为非实时数据，那么，多媒体数据当中至少 得包含有一种实时数据和一种非实时数据。 人与媒体之间的交互是多媒体技术最基本的特征。例如视频点播，观众可以 直接选择自己喜欢的广播电视节目，并可随意快进、快倒、慢放以及暂停等待。 而对传统的广播电视观众就没有这么方便了。而多媒体技术的出现改变了这种人 与系统之间的非交互性操作，使之能够对包括伴音在内的电视图像进行交互式的 调取、处理与操作。例如，观众可以通过指令任意地调出存在图像数据库中的电 视节目，还可以从节目中的指定位置开始播放，观看存储在远距离以外系统上的 节目如同操作录像机一样方便。 早期的通信技术主要应用于电话、电报业务，后来发展了传真、数据业务、 以及电视信号的远距离传输。它们的特点是每种业务是相互独立的。而多媒体技 术则能将各种业务进行综合。例如，传统的电视会议系统只能实现实时的声音和 活动图像信息的传输，缺乏人机交互和对会议的管理。在整个会议过程中只用于 北京邮电大学博士学位论文 传输现场情况，其他的事物如会议的组织、安排、记录等与普通会议没有什么区 别。而多媒体电视会议系统则具有交互操作能力和管理能力。在会议发起时，会 议系统负责会议的联络工作，如发送邀请、处理回执等；在会议中，不但可以实 时传输与会者的音容笑貌，使入会者具有同在一个会议室的感觉，而且可以将会 议讨论的内容和传输的信息有机结合并做处理，大大减轻了与会者的负担。 近年来，随着宽带网络的发展和用户需求的驱动，流媒体技术和数字电视技 术的应用得到越来越多的关注，被认为是未来高速网络的主流应用之一，这将成 为多媒体通信技术的又一个值得关注的应用。因此，现阶段的多媒体通信系统大 致可以分为以下5 类，即多媒体信息检索与查询系统、视频点播系统、网络流媒 体系统、多媒体电子邮件系统、多媒体合作工作系统。 ( 1 ) 多媒体信息检索与查询系统 具体的应用如电子图书馆、电子购物、导游系统等。这类系统以多媒体数据 库为核心。人们可以通过多媒体终端来查找有关的多媒体信息。比如通过多媒体 查询系统，人们可以足不出户地选购超级商场的各种物品。在这种系统中，有关 商品的各种信息被存储在商场的多媒体数据库中，人们可以利用家中的多媒体终 端，根据菜单调出他们需要的商品的有关信息，从各个角度拍摄的包括解说词( 使 用说明、价格等) 的静止或活动图像。 ( 2 ) 视频点播系统 人们日常欣赏电视节目的方式是一种被动的方式，节目的播放时间是预定好 的，观众也不可能改变节目的播放过程。而视频点播系统中，所有的电视节目都 被数字化压缩后存入视频库当中。观众可以在家里通过多媒体终端查找和观看视 频库中自己喜爱的节目或其中的某个片段，还可以任意快进、快倒、慢动作和观 看静止画面。现阶段互联网上视频点播业务已经比较流行，但如果要给用户提供 活动的、高图像质量的电视图像，则需要较高的传输带宽。因此，真正能替代传 统电视的视频点播系统必定是基于宽带通信网的，需要通过宽带接入设备将用户 的终端与通信网络相接。目前，解决宽带按入问题的现实方案主要有两种，其一 是非对称数字用户线路( a d s l ) ，其二是光纤同轴电缆混合方式( i 口c ) 。这 两种方式分别是以电话网和有线电视网为基础而研究的。未来的用户接入方式将 是光纤直接铺设到用户家中。到那时，光纤的巨大通信能力将会促进多媒体应用 的飞速发展。 ( 3 ) 网络流媒体系统 流媒体( s t r e a m i n gm e d i a ) 指在数据网络上按时间先后次序传输和播放的 连续音视频数据流。以前人们在网络上观看电影或收听音乐时，必须先将整个 影音文件下载并存储在本地计算机上，然后才可以观看。与传统的播放方式不同， 北京邮电大学博士学位论文 流媒体在播放前并不下载整个文件，只将部分内容缓存，使媒体数据流边传送边 播放，这样就节省了下载等待时间和存储空间。随着流媒体一系列相关技术，包 括音视频编解码技术、媒体传输质量控制技术等的逐渐成熟，以及宽带网络的 兴起，制约流媒体发展的主要障碍逐渐被打破，基于宽带网络的流媒体技术得到 了迅速的发展，并得到了越来越多的重视。宽带流媒体应用被一致认为是未来高 速宽带网络的主流应用之一。各国在相应的高速网络研究计划中都把流媒体技术 作为一个重要的研究内容，例如i n t e r n e t 2 ( 1 2 ) 的应用研究组认为未来1 2 网络 的杀手应用应该包括几个基本的属性：交互式合作环境；对远程资源的公共访问； 构建网络计算和数据服务的支撑平台；用虚拟现实显示信息。在所有的这些应用 中，1 2 的应用开发组认为数字视频能带来最广泛利益并能最广泛地应用1 2 能力， 它可以覆盖从点播到远程的资源控制。数字视频可以看作是宽带流媒体应用的一 个基本类型。我国的8 6 3 高科技研究计划“高性能信息示范网络3 t n e t ”中，也 明确提出要从宽带流媒体等典型业务入手，建立一个能适应i n t e r n e tt v 等媒体 流实时传输的高性能、广域( 城域) 宽带演示验证网络3 t n e t 。 除了宽带网络外，流媒体技术还可以广泛地应用于其它网络，例如无线流媒 体传输是3 g 网络的主要应用之一。在n g n 网络中，流媒体也扮演重要的角色。 ( 4 ) 多媒体电子邮件系统 具有图像和声音表现能力的多媒体电子邮件系统在使用上与人们已经熟悉 的基于报文处理的电子邮件系统类似。基于报文的电子邮件系统只能传送文本信 息。而多媒体电子邮件系统可以处理文本、声音、图像等多种信息。比如，通过 多媒体电子邮件系统，远在国外读书的学生，可以将自己的学习生活片段用录像 机录下来，输入计算机，作为电子邮件发送给远方的亲人，家人通过多媒体终端 打开该电子邮件，就可以看到这些生活片段的录像。多媒体邮件系统是一种非实 时的存储转发系统，不需要很高的通信带宽。 ( 5 ) 多媒体合作工作系统。 多媒体远程教学、多媒体电视会议、多媒体远程医疗、多媒体协作工程设计 系统等在原理上同属于这一范畴。这类系统对通信系统的要求最高。它们要求点 对点、点对多点、或多点对多点的实时、不间断的多媒体信息传输，有严格的同 步要求。在这类系统中，地处不同物理位置的合作各方除了可以互相看得见和听 得见外，还共享了一个虚拟的工作空间。这个虚拟空间可以是一个简单的“白板”， 合作各方可以在上面显示图片、表格和输入文字、画画等；更复杂些的工作空间 允许合作各方共同使用同一应用软件和相关数据，如使用同一c a d 软件来修改 同一工程设计图纸。 1 2 视频点播系统 北京邮电大学博j 二学位论文 视频点播系统的基本组成部分是：多媒体服务器、宽带通信网络和用户点播 终端。视频点播系统的主要功能是应用户的请求输出相应的视( 音) 频节目。与 传统的广播方式不同，多媒体点播系统提供的是一种交互式的服务。用户可以在 任何时候，调取系统中的任意节目，并可以象控制录像机或c d 机一样控制节目 的播放。视频点播系统可以和视频编辑系统一起构成多媒体综合服务系统，适用 娱乐、教育、新闻、购物等不同的应用范围。视频点播结构示意图如图1 1 所示。 图1 1 视频点播系统 多媒体服务器是系统的核心，通常也称为视频服务器。它存储和管理着大 量的多媒体数据，如电视、电影和音乐节目等，并为众多网络用户提供多媒体点 播服务。多个用户可以同时向视频服务器请求他们喜爱的节目，视频服务器从磁 盘阵列中同时读取视( 音) 频流，并通过网络发送到相应的用户终端。这些同时 被读出和传送的视( 音) 频数据流通常称为并发的视( 音) 频流。出于视频服务 器中存储和传输的是视频或音频数据，这一方面需要巨大的系统资源，如存储空 间、i 0 带宽、网络带宽，另一方面，这些媒体的播放有严格的时域约束，即播 放时要求连续。由于要为几百甚至更多的用户提供并发的视频流，因此对视频服 务器的处理能力、总线带宽、i o 能力、缓存大小、网络接口及系统的伸缩性等 都有很高的要求。视频服务器的设计目标是在确保一定的服务质量( q o s ) 下， 提高系统资源的利用率，为更多的并发用户服务。因此，如何有效地利用系统资 源，是多媒体点播系统的关键。从功能上看，视频服务器可分为三部分，存储子 系统、控制子系统和通信子系统。从服务的内容看，目前c b r 视频和r 视频 是视频点播系统中两种主要的业务，尽管c b r 业务由于其恒定的比特率可以大 大减小传输的复杂性，但其质量的不均匀不能满足人们对服务质量需求的进一步 提高。为此，v b r 视频将成为未来多媒体网络的首选内容，而v b r 视频的突发 性和自相似特性将给其存储、调度和传输带来一系列难题，成为研究视频点播系 统的一大热点。 宽带通信网是连接多媒体服务器和用户的枢纽。通常情况下，多媒体宽带通 北京邮电火学博士学位论文 信网包括主干网和接入网。a t m 是一种理想的主干网络，它具有确保q o s 的机 制，支持c b r 和v b r 业务等多种业务。目前的接入网是多种多样的，有基于 a t m 或i p 的l a n 接入，有基于a d s l 和h f c 网的按入等等。视频点播用户终 端也可以有多种，最常用的一种是机顶盒连接电视，另外也可以用计算机作终端。 机顶盒是用户显示设备、外围设备以及传输网络之间的桥梁。简单的机顶盒只需 要解码显示功能和个反向信道，但是随着业务的发展，许多新业务的提供者都 认为机顶盒涉及到新业务的引入方式，从而使机顶盒的结构趋于多功能化。从硬 件结构上看，s t b 可分成网络接口单元n i u 烈e t w o r ki n t e r f a c eu i l i t ) 和机顶单元 s t u ( s e tt o p u n i t ) 两部分。采用n i u 和s t u 分开这种结构的目的是使s t b 能 不作大的改动就可接入到不同的网络中，从而厂家无需为各种网络单独设计 s t b 。 综上所述，一个好的视频点播系统应该具有以下特征：服务器的吞吐能力能 够模块化地扩展；能够从多种信源向系统输入信号；具备层次化存储结构；与多 媒体信息检索和查询业务相结合：对不同终端的兼容性。 1 3 相关研究状况 视频点播系统是一种典型的交互式多媒体信息系统，数字视频压缩技术、组 网技术、控制协议是点播系统的三大关键技术。其中影响多媒体视频服务器性能 的主要因素有视频服务器的体系结构、服务器与客户端之间的数据传送方式、媒 体数据在视频服务器存储子系统中的分布与放置方式、对磁盘访问请求的调度、 单服务器中的缓存及多服务器间协同缓存的管理、接入控制策略、流调度策略等。 而本文主要围绕视频服务器关键技术中一些具体的热点问题进行研究，包括视频 服务器的i o 调度、v b r 视频流的传输、v b r 视频流的预测以及v b r 流的接纳控 制。 ( 1 ) 视频服务器的i 0 调度 近年来，c p u 的计算能力、系统内部总线的传输速度、内存的访问速度都有 显著提高，与服务器的i 0 能力的缓慢提高形成了一种不和谐的局面，大大制约 了客户端一服务器模式下的应用。视频服务器的i 0 调度的难点来自于其高的并 发性要求和磁盘读写受本身的机电特性限制形成的矛盾。视频服务器需要为众多 用户提供并发的服务，并具有时域约束，而磁盘的读写操作受其本身的机电特性， 如寻找延时、旋转延时等的影响，使用传统的i 0 方案，带宽的利用率很低且无 质量的保障。因此，需要适当的调度策略来提高视频服务器的磁盘带宽利用率和 服务质量。在文献 1 】- 【8 主要研究了以降低磁盘寻找延时、旋转延时来提高磁盘 的数据吞吐率的磁盘o 调度算法，通过优化磁盘的数据放置、访问方式以及内 存管理来提高系统的服务能力。文献 1 通过将视频文件做交织存储来提高系统 北京邮电大学博士学位论文 的i 0 性能。文献 2 设计了一个基于s c a n 磁盘调度算法的多媒体存储服务器， s c a n 算法可以减少磁盘m d 的开销。文献 3 】和【4 几乎同时提出了一种相同的磁 盘调度算法，在文献 3 中称为g s s 算法，是s c a n 算法和f c f s ( 先来先服务) 算法的结合，它将请求分组，在组内使用s c a n ，组间使用f c f s 。由于f c f s 服务机制允许重用部分内存，因此这种结合在一定程度上可以减少内存的需求。 文献 5 介绍了一种基于r a i d 的视频文件管理系统，对共享内存和起始延时做 了讨论。文献 6 】提出了一种成批处理式的磁盘调度算法。该算法中将同一个视 频文件的数据块互相靠近来存放，在读取数据时，对不同的视频流的请求以 s c a n 算法来调度，而对同一视频流的请求则做批处理。算法中利用了对同一个 视频流的各个请求中可能存在重复的数据来减少的要求和缓存需要。在双向扫 描调度算法b i s c a n 中1 7 】，文件被分割为大小等于一个磁道数据量的数据块， 这样可以利用分切存取来优化磁盘的旋转延时。同一个文件的不同数据块可以存 放在位置不连续的磁道上。数据搜索的顺序是双向的，即先里到外，然后从外到 里依次交替，b i s c a n 算法能大大提高存储系统的i ，o 性能。文献 8 通过分析 s c a n ，c s c a n 0 1 算法，提出了针对s c a n c s c a n 算法的改进的l o o k c l 0 0 k 算法， 该算法不是将磁头总是从最内外的磁道移向最外内的磁道，而是将磁头从有请 求存在的最内外磁道移向有请求存在的最外内的磁道，从而提高了并发请求的 用户数。 也有学者提出将满足请求的最终时限和降低磁盘的寻找延时、旋转延时结合 起来的调度算法，如s c a n e df 【l0 1 、g s s 1 1 】、m s e d f 等。算法s c a n e d f 【1 0 】 结合了s c a n 算法和e d f 算法二者的优势，它的调度机制是：首先按照e d f 策略 为那些具有最早完成时限的读，写请求提供服务。当若干读写请求具有相同的时 限时，调度机制将以s c a n 方式为这些请求提供服务。在降低平均寻找时间方面， 该算法对e d f 的改进程度依赖于具有相同时限的请求数目，这个数目越大，改进 程度也就越大，磁盘的吞吐率也就越高。g s s 】算法的出发点是为了能在同时服 务的用户数和用户等待时间及缓存大小之问取得某种折中。首先依据完成时限的 近似程度将各请求分组并为每组规定一个统一的时限，随后g s s 根据组时限依次 为各组请求提供服务。对组内各请求，g s s 采用s c a n 方式进行磁盘调度。由于 较多的请求具有了相同的时限且以s c a n 方式进行调度，所以磁盘吞吐率会有较 大改善，所能服务的用户数也将增长。m s e d f i l 列算法不但能满足所有请求的最 终期限，而且也可以提供最优的寻找延时。该算法采用接纳控制机制( a c m ) 和磁盘调度机制( d s m ) ，a c m 负责考察系统现有资源以决定是否对新请求进 行接纳；d s m 作为磁盘调度的核心，根据所有请求的最终期限和磁道信息确定 一种能最小化寻找延时的算法。实验表明m s e d f 算法在性能上优于c s c a n 、 e d f 、s c a n e d f 、g s s 等算法。s h a h r a m 等人提出一种新的多优先级请求环境 北京邮电大学博士学位论文 下基于成本驱动的磁盘调度算法。该算法通过单排队的方式和对请求的智能管 理，来尽可能多地满足较低优先级请求的最终时限，同时使满足最终时限的较高 优先级请求数最大化。在以上这部分研究中，本论文将主要涉及数据的放置方式、 存取方式以及调度顺序等方面。 ( 2 ) v b r 视频流的传输 v b r 流和c b r 流相比，其典型的特性是速率的猝发性( b l 】r s n n e s s ) 和多变性 ( v a r i a b i l i t y ) 【1 4 】，这对传输系统的q o s 提出了挑战，这种挑战集中体现在带宽资 源f 包括网络带宽和存储系统的i 0 带宽) 的分配和利用、传输效率以及接纳控制 策略等。同时v b r 视频的自相似性口5 ，1 6 1 又给系统缓存、排队性能和网络带宽分 配带来了各种影响。因此，随着v b r 业务的大量应用，解决与其特性相适应的 上述问题，成为一大研究热点。传输v b r 流的方法很多，下面是与本文密切相 关v b r 视频流的几类传输方法。 基于等效带宽的传输方法c o u r c o u b e t i s 等人【1 7 】运用等效带宽理论对各种 具有突发特性的静态源进行了深入的研究，进而为此类业务的有效传输和带宽分 配提供了很好的数学模型。n a g a 蛹a 1 1 呱1 9 1 与n o d s 【2 0 川等人运用等效带宽理论 对兼有长相关与短时相关特性的v b r 视频流进行了实时的带宽资源分配，使得 系统性能在满足指定q o s 的同时，也提高了资源利用率，并且，也对v b r 视频 流的变比特率特性带来的复杂性进行了简化。 基于r 视频流本身特性的传输方法这类方法又可根据提供的q o s 类型 分为两种，其一是能提供确定性q o s 的方法，如d b n d 2 2 ，2 3 ，2 4 ，2 劐，这类方法 根据最坏情况分配网络资源，其资源利用率较低；另一类是提供统计q o s 的方 法，如文献 2 6 ，2 7 ，2 8 ，2 9 ，这些方法通过统计复用来提高网络资源的利用率， 大大增加了系统能服务的并发客户数，但带来的是系统q o s 性能的降低。为此， 不少学者在寻求最好的折中方法，以尽可能获得最优的系统性能。s a t o s h 等人 3 0 j 提出了种在综合分组网上用于弹性会话的显式速率控制算法，会话可以得 到最小保证的速率分配，还可使会话获得最大，最小的公平速率。b i e r s a c k 等人【3 1 】 在v b r 视频服务器中使用了统计复用的方法，提出了基于二项分布接纳控制方 法。虽然其使用的二项分布并不能很好地描述v b r 视频流的统计特性，但其使 用的统计复用方法却很有参考价值。 基于磁盘i ，o 调度的方法d e e p a k 等人1 3 2 l 将文献 3 3 中的g s s 磁盘调度算法 应用到v b r 视频的i o 调度中，并提出统计等效带宽保留的i o 方法。c h e n 等 人【3 4 】通过详细分析磁盘的物理结构和存取特性f 3 5 】，对c b r 流的传输提出了满足 磁盘i ，o 带宽和缓存约束的动态调度周期接纳控制算法。l e e 等人【3 6 通过分析文 献 3 4 】提出的有限系统资源对调度周期的约束关系，对v b r 流进行了满足磁盘 i o 带宽和缓存有限情况下的传输调度，极大地提高系统资源的综合利用率。 北京邮电大学博 学位论文 基于w e b 的变比特率数据流的传输在、v e b 服务器众多的负载类型中， h t m l 页面和图像文件一起约占所有w e b 请求文件的9 0 【3 7 】；h t m l 文件和图 像文件相对于视频点播流来说，到达率频繁而文件较小，多为1 0 0 1 0 0 ，0 0 0 比特 之间1 3 8 】。目前关于w e b 服务器性能的研究，主要集中于负载特性、o o s 指标( 如 响应时涮、吞吐量、拒绝率) 以及接纳控制等。m e n a s c e 通过评测w e b 服务器的 负载特性，对q o s 指标进行了深入的研究【3 9 ，4 。c h e n 等人详细研究了采用区别 服务的w c b 服务器性能，通过实际的流量跟踪评估了接纳控制、任务调度及其 分配等对区别服务的w e b 服务器性能的影响【4 1 】。c h e r k a s o v a 等人为了改进商业 w e b 服务器的性能，引入了基于会话的接纳控制来防止服务器过载，以确保较长 的会话得以完成【4 ”。h 等人采用基于测量的接纳控制，在a p a c h ew e b 服务器的 基础上按固定比例对异构的并发客户请求分配服务器带宽，从而使w e b 服务器 具备了对不同带宽要求的请求分配以不同带宽的区别服务1 4 3 】。 基于v b r 流预测的传输方法这将在下一部分介绍。在以上这部分研究中， 本论文几乎都有涉及，并着重探索基于磁盘i o 调度的传输和基于预测的传输。 ( 3 ) v b r 视频流的预测 可变比特率视频业务将是未来宽带网中的主要业务。为了更好地进行传输控 制和保证服务质量，准确把握业务流的特性成为解决这一问题的关键。由于v b r 视频流的数据量大、突发性强、非平稳性、自相似性等特点，动态地给予带宽预 留是解决这一类业务服务质量问题的合理选择。对业务流的预测足实现动态带宽 预留的有效途径之，尤其对于实时v b r 视频业务，采用预测方法将更能显示 它的不可替代性。文献 4 4 俐用l m s 算法，文献 4 5 ，4 6 利用a r 模型分别对视频 流进行线性预测，文献【4 7 ，4 8 】将预测问题放在小波域里进行处理。这些工作虽然 通过预测使网络的利用率得到了提高，但是它们预测的延迟性或算法的复杂度在 一定程度上降低了它们的性能，无法准确地进行后续处理。文献 4 9 】针对以上问 题就v b r 视频流的自适应流量预测、动态预留带宽及其缓冲中视频流的排队等 性能进行分析研究。通过统计和分析，提出了基于编码结构的可变步长自适应 l m s 预测算法，它能够快速、无延迟地对视频流进行预测，并且通过动态带宽 分配后，网络缓存中视频流表现出了良好的排队性能。文献 5 0 提出了为m p e g 编码的视频源进行业务预测和建模的自适应神经网络构架，该方法基于一个高效 的递归加权估计算法，使网络能适应当前的状况，并且算法复杂性低，在追踪业 务速率方面比传统的反复训练具有更高的效率。文献 5 l 】系统地研究了具有长 期、在线、实时特性的v b r 视频业务的预测，通过多分辨率学习的神经网络业 务预测器，预测性能和鲁棒性的到了显著的改进，可以成功预测各种现实世界的 v b r 视频业务达几百帧，这将给动态带宽分配提供可靠的保障。本论文将通过 分析视频的编码结构、数据统计特性以及各类帧之间数据的比例特性来探索更准 北京邮电大学博士学位论文 确的预测算法。 ( 4 ) 、，b r 流的接纳控制 影响视频服务器性能的关键因素有多种，其中，接纳控制是相当重要的。这 是因为，在视频服务系统中，视频数据作为连续媒体，有一些显著特点。首先， 视频对象的数据量较大，在存储和传输过程中需要较大的磁盘i ，o 带宽与网络带 宽。其次，视频对象的播放具有连续性和实时性的要求，而服务器端的磁盘带宽、 缓冲容量、网络带宽等资源又是有限的，因此，系统可支持的最大并发用户数是 有限的。所以，研究如何通过接入控制来既提升服务器的吞吐率、资源利用率， 接入尽可能多的用户，又能较好地满足用户的q o s 要求，就显得很有必要了。 另外，其它实时业务如变比特率w 曲业务口7 1 、非实时业务也存在接纳控制问题， 因此，研究v b r 数据流的接纳控制成为众多学者的研究课题之一。下面将分类 介绍几种常见的接纳控制方法。 确定