VBR流式视频I%2fO调度与平滑传输模型及算法优化的研究

中南大学

博士学位论文

VBR流式视频I/O调度与平滑传输模型及算法优化的研究

姓名：谢建国

申请学位级别：博士

专业：计算机应用技术

指导教师：陈松乔;陈建二

20020301

中南大学博士学位论文

摘要

随着网络带宽的迅速增加，网络流媒体日将成为网络应用的主流，网络流媒体的相关技术成为计算机领域内的重要研究热点。ＶＢＲ方式压缩的视频是网络流媒体的主要数据源，像ＶｏＤ、网络视频会议、远程教育等都需要这种视频的实时传输和传播。而ＶＢＲ方式压缩的视频和ＣＢＲ方式压缩的视频相比，在相同资源许可下能得到更好的服务质量保证，但不足的是，由于它的ＶＢＲ特性，复杂了网络的管理，如接纳控制、带宽分配等。本论文针对ＶＢＲ流式视频（简称ＶＢＲ视频流）重点研究了两方面问题，一是ＶＢＲ视频流的Ｉ／Ｏ调度，二是ＶＢＲ视频流的平滑传输。

论文首先提出了一个基于多处理机多任务调度原理的带缓冲箱多实时流调度模型及相应的接纳控制算法，讨论在多网络Ｉ／Ｏ通道独立并行输出情况下，其最大网络输出流的有效调度问题。提出了另一个针对存储ＶＢＲ视频的最短路径平滑算法，讨论如何利用前端缓冲技术，研究ＶＢＲ视频流在传输过程中其峰值位率最大可能缩减问题。文中给出了两算法优化性能的分析，实验结果也显示这些算法的效果是明显而有效的。

其次在基于最短路径平滑算法下，考虑不同网络段之间的异质传输特性，提出了异步平滑调度算法，考虑残余带宽利用率问题，提出了残余带宽下视频服务协议算法，以及针对强实时ＶＢＲ视频流，提出了实时平滑传输算法。实验显示这些算法在各自的应用背景下都较好地解决相关问题。

最后，论文在讨论一个视频比例安置算法后，着重研究了以优化磁盘Ｉ／Ｏ为目的，结合平滑技术、视频安置技术及ＭＺ特性的磁盘技术，提出了磁盘Ｉ／Ｏ平滑检索模型、平滑检索算法及相应的视频安置模式。模拟实验显示下，对于给定目标参数这些算法有好的性能结果。

关键词：变位率视频，多网络Ｉ／Ｏ，平滑，视频安置，多磁盘Ｉ／Ｏ。

中南大学博士学位论文

Ａｂｓｔｒａｃｔ

Ｗｉｔｈｔｈｅｉｎｃｒｅａｓｉｎｇｏｆｎｅｔｗｏｒｋｂａｎｄｗｉｄｔｈ，ａｐｐｌｉｃａｔｉｏｎｓｏｆｎｅｔｗｏｒｋ

ｓｔｒｅａｍｉｎｇｍｅｄｉａｈａｖｅｂｅｅｎｍａｉｎｓｔｒｅａｍｓｏｎｎｅｔｗｏｒｋ．Ｔｅｃｈｎｉｑｕｅｒｅｌａｔｉｏｎｓｔｏｎｅｔｗｏｒｋｓｔｒｅａｍｉｎｇｍｅｄｉａｈａｖｅ

ｂｅｅｎｓｔｕｄｉｅｄｂｙｍａｎｙｒｅｓｅａｒｃｈｅｒｓｉｎｃｏｍｐｕｔｅｒｓｃｉｅｎｃｅ．Ｖｉｄｅｏｓａｒｅｍａｉｎｄａｔａｓｏｕｒｃｅｏｆｎｅｔｗｏｒｋｓｔｒｅａｍｉｎｇｍｅｄｉａ，ＦｏｒｅｘａｍｐｌｅＶｏＤ，ｎｅｔｗｏｒｋｖｉｄｅｏｃｏｎｆｅｒｅｎｃｅ，ａｎｄｔｅｌｅ—ｌｅａｒｎｉｎｇｎｅｅｄｒｅａｌｔｒａｎｓｍｉｓｓｉｏｎａｎｄｔｒａｎｓｍｉｔｔｉｎｇｏｆｖｉｄｅｏｓ．ＣｏｍｐａｒｅｄｔｏｔｈｅＣＢＲｃｏｍｐｒｅｓｓｅｄｖｉｄｅｏ．ｔｈｅＶＢＲｃｏｍｐｒｅｓｓｅｄｖｉｄｅｏＣａｎａｃｈｉｅｖｅｍｏｒｅｓａｒｉｓｆｙｉｎｇＱｏＳｕｎｄｅｒｔｈｅｓａｍｅｒｅｓｏｕｒｃｅｃｏｎｓｔｒａｉｎｔｓ．ＴｈｅｄｉｓａｄｖａｎｔａｇｅｉｓｔｈａｔｔｈｅＶＢＲｃｈａｒａｃｔｅｒｉｓｔｉｃｏｆｔｈｅＶＢＲｃｏｍｐｒｅｓｓｅｄｖｉｄｅｏ

ｎｅｔｗｏｒｋｍａｎａｇｅｍｅｎｔｔｅｃｈｎｉｑｕｅｓ．Ｔｈｉｓｄｉｓｓｅｒｔａｔｉｏｎｆｏｃｕｓｅｓｏｎｔｗｏｍａｉｎｃｏｍｐｌｅｘｅｓ

ｓｔｒｅａｍ．

ｐｒｏｂｌｅｍｓ：ｔｈｅＦＯｓｃｈｅｄｕｌｉｎｇａｎｄｓｍｏｏｔｈｉｎｇｔｒａｎｓｍｉｓｓｉｏｎｏｆｔｈｅＶＢＲｖｉｄｅｏ

Ｔｈｅｄｉｓｓｅｒｔａｔｉｏｎｆｉｒｓｔａｄｄｒｅｓｓｅｓｔｗｏｐｒｏｂｌｅｍｓ：ｏｎｅｉｓｔｈｅｍａｘｉｍｕｍ

ｏｕｔｐｕｔｏｆｖｉｄｅｏｓｔｒｅａｍｓｗｉｔｈｍｕｌｔｉ—ｎｅｔｗｏｒｋＩ／Ｏｃｈａｎｎｅｌｓ，ａｎｄｐｒｏｐｏｓｅｓａｒｅａｌｓｔｒｅａｍｓｓｃｈｅｄｕｌｉｎｇｍｏｄｅｌｗｉｍｂｕｆｆｅｒｂｏｘ．ａｎｄｄｅｖｅｌｏｐｓａｎａｄｍｉｓｓｉｏｎｃｏｎｔｒｏｌａｌｇｏｒｉｔｈｍｂａｓｅｏｎｔｈｉｓｍｏｄｅｌ．ＡｎｏｔｈｅｒｉｓｔｈｅｓｔｕｄｙｏｆｔｈｅｇｒｅａｔｅｓｔｐｏｓｓｉｂｌｅｒｅｄｕｃｔｉｏｎｔｏＶＢＲｖｉｄｅｏｗｈｅｎｔｒａｎｓｍｉｔｔｉｎｇｓｔｏｒｅｄｖｉｄｅｏａｃｒｏｓｓａｎｅｔｗｏｒｋｔｏａｃｌｉｅｎｔｗｉｔｈｇｉｖｅｎｂｕｆｆｅｒｓｉｚｅ，ａｎｄｄｅｖｅｌｏｐｓａｓｈｏｒｔｅｓｔｐａｔｈｓｍｏｏｔｈｉｎｇａｌｇｏｒｉｔｈｍ．Ｆｏｒｔｈｅｓｅｔｗｏａｌｇｏｒｉｔｈｍｓ，ｗｅｐｒｅｓｅｎｔｆｏｒｍａｌａｎａｌｙｓｉｓｏｆｏｐｔｉｍａｌｉｔｙ，ａｎｄｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅａｌｇｏｒｉｔｈｍｓａｒｅｅｆｆｉｃｉｅｎｔ．

Ｂａｓｅｏｎｔｈｅｓｈｏｒｔｅｓｔｐａｔｈｓｍｏｏｔｈｉｎｇａｌｇｏｒｉｔｈｍ，ｔｈｅｄｉｓｓｅｒｔａｔｉｏｎｐｒｏｐｏｓｅｓａｎａｓｙｎｃｈｒｏｎｉｓｍｓｍｏｏｔｈｓｃｈｅｄｕｌｉｎｇ，ｗｈｉｃｈｃｏｎｓｉｄｅｒｓｔｈｅｈｅｔｅｒｏｇｅｎｅｉｔｙｔｒａｎｓｐｏｒｔｃｈａｒａｃｔｅｒｉｓｔｉｃｂｅｔｗｅｅｎｔｗｏｎｅｔｗｏｒｋｓ，ａｎｄａｔｒａｎｓｍｉｓｓｉｏｎｓｅｒｖｉｃｅｐｒｏｔｏｃｏｌ，ｗｈｉｃｈＣａｎ

ｂａｎｄｗｉｄｔｈｒｅｓｏｕｒｃｅ，ａｎｄａｒｅａｌ—ｔｉｍｅｐｒｏｖｉｄｅｒｅａｌ—ｔｉｍｅｖｉｄｅｏｓｅｒｖｉｃｅｕｎｄｅｒｔｈｅｒｅｓｉｄｕａｌ

ｓｍｏｏｔｈｉｎｇａｌｇｏｒｉｔｈｍ，ｗｈｉｃｈｃｏｎｓｉｄｅｒｓｔｈｅｄｅｌａｙｃｈａｒａｃｔｅｒｏｆｔｈｅｓｔｒｏｎｇｒｅａｌ—ｔｉｍｅｖｉｄｅｏ．Ｅｘｐｅｒｉｍｅｎｔａｌｒｅｓｕｌｔｓｓｈｏｗｔｈａｔｔｈｅｓｅａｌｇｏｒｉｔｈｍｓｗｏｒｋｖｅｒｙｗｅｌｌ．

Ａｆｔｅｒｄｉｓｃｕｓｓｉｎｇａｖｉｄｅｏｓｃａｌｉｎｇｐｌａｅｅｍａｎｔａｌｇｏｒｉｔｈｍ，ｔｈｅｄｉｓｓｅｒｔａｔｉｏｎｐｒｅｓｅｎｔｓｓｏｍｅｄｉｓｋｒｅｔｒｉｅｖａｌａｌｇｏｒｉｔｈｍｓａｎｄｖｉｄｅｏｄｉｖｉｄｅｄｓｃｈｅｍｅｓａｉｍｉｎｇｔｏｏｐｔｉｍｉｚｅｐｅｒｆｏｒｍａｎｃｅｏｆｔｈｅｄｉｓｋＩ／Ｏ，ａｎｄｔｏｉｎｔｅｇｒａｔｅｔｈｅｆｏｌｌｏｗｉｎｇｔｅｃｈｎｉｑｕｅｓ：ｓｍｏｏｔｈｉｎｇ，ｖｉｄｅｏｐｌａｃｅｍｅｎｔａｎｄｄｉｓｋｍｕｌｔｉ—ｒａｔｅｓ．ＴｈｅｓｉｍｕｌａｔｉｏｎｒｅｓｕｌｔｓｓｈｏＷｔｈａｔｔｈｅｓｅａｌｇｏｒｉｔｈｍｓａｒｅｅ街ｃｉｅｎｔ．

Ｋｅｙｗｏｒｄｓ：ＶＢＲｖｉｄｅｏ，ｍｕｌｔｉ—ｎｅｔｗｏｒｋｓＩ／Ｏ，ｓｍｏｏｔｈｉｎｇ，ｖｉｄｅｏｐｌａｃｅｍｅｎｔ，ｍｕｌｔｉ—ｄｉｓｋｓＩ／Ｏ

第１章绪论

第１章绪论

１．１引言

自九十年代初期，流式媒体（简称流媒体）技术一直得到研究者的重视。早期一些代表性文献的工作主要集中在视频存储、单流缓冲计算及磁盘调度策略【ｆ。”。这些研究涉及的问题虽然相对简单，而且问题的应用背景规模小，但做了很有益的开创性工作，文献［６］对这一段时期的工作进行了全面的综述。近期的文献从不同的应用背景研究了流媒体理论及其相关的技术，主要包括变位率视频流的平滑与控制技术“２。”、磁盘调度与接纳控制［ｓ４’６２Ｊ、视频Ｍｕｌｔｉｅａｓｔ技术和视频ＱｏＳｌ６３－７２１、视频安置技术＂３４５１及视频服务系统的资源管理和相关的技术【ｌ“州等，这些研究在各自的应用领域内取得了全面发展。ＶｏＤ系统的研究与应用［９５“９７１、视频会议系统的研究与应用及远距离学习系统的研究与应用陬”１等，这些与流媒体技术息息相关的分布式多媒体应用系统的研究，取得了实际应用效果。但由于网络带宽资源的限制，特别是因ＶＢＲ（ｖａｒｉａｂｌｅｂｉｔｒａｔｅ）视频高带宽的长时占用和峰值位率的突发性，复杂了网络及Ｉ／Ｏ的管理，如带宽的分配及利用率、接纳控制等问题，再加上一些相关网络技术有待进一步发展，因而Ｉｎｔｅｒｎｅｔ上大规模分布式多媒体应用技术的研究大多尚处于实验室阶段。本论文针对目前ＶＢＲ流式视频在传输过程中存在的问题，对下列问题进行了研究：视频服务器的网络ＶＯ调度、ＶＢＲ流式视频的平滑传输规划、ＶＢＲ视频磁盘上的安置以及磁盘Ｉ／Ｏ调度等。

在视频服务器的网络输出方面，文献［６０］提出了连续媒体流理论模型，做了较好的研究工作。由于网络出口带宽和磁盘入口带宽相比相对富裕，很少有研究者专门研究最大输出流的计算，特别是当网络输出成为瓶颈、多网络ＦＯ引入时，这种计算必不可少。

在ＶＢＲ视频流的平滑传输方面，得到了众多研究者的关注。ＶＢＲ视频流的平滑研究分存储视频的离线平滑传输、弱实时视频的在线平滑传输和强实时视频的实时平滑传输等方面。对于存储视频因在传输前可以知道数据帧尺寸的全部信息，因而可以在传输前根据给定的条件计算平滑传输计划，称这种平婿为离线平滑佃ｍｉｎｅｓｍｏｏｔｈｉｎｇ）“２“】，相反，实时视频因不知道将来数据帧尺寸信息，所以这种平滑传输计划只能实时计算，称这种平滑为在线平滑（ｏｎｌｉｎｅｓｍｏｏｔｈｉｎｇ）田“∞１或实时平滑ｐ””】。在存储视频平滑方面文献［１４】雇用了一个ＣＲＴＴ算法，讨论在用单一的位率传递整个ＶＢＲ视频情况下，如何极小化带宽或缓冲的需求。文献【１５，１６】首先提出了ＣＢＡ算法，后来文献［１７】提出的ＭＣＢＡ算法是对ＣＢＡ算法的扩充，算法的结果能产生最小的峰值位率、能极小化传输位率的改变次数。文献【１２】提出的ＭＶＢＡ算法，能极小化峰值位率，和极小化位率的变化量，而且算法的结果在Ｍａｊｏｒｉｚａｔｉｏａｆ…１性能上是平

中南大学博士学位论文

滑最优的。文献【１８］对这些算法的平滑性能在实验上进行了一定的比较与总结。而文献［１９，２０］提出的ＭＰＳ算法和ＭＣＢＡ有异曲同工之效，如最小的峰值位率、极小化传输位率的改变次数，但它对这一结果给出了理论证明和其它性能标准的进一步讨论。与上述风格不同的是文献［２０，２２，２４】等提出用固定不变的带宽传输ＶＢＲ视频流的ｏｎ—ｏｆｆ平滑算法，Ｏｎ表示以固定速率传输视频数据，ｏｆｆ表示不传输任何视频数据，整个传输过程由０１１段和ｏｆｆ段交替进行，并建立了固定传输位率和缓冲尺寸的对应关系。在弱实时视频方面，如电视新闻、实况转播等，这类视频对于一定的较长延迟是可以接受的，以延时缓冲一定的数据来进行平滑，这方面的算法主要将一些离线平滑技术应用于一个给定的窗口内，进行有限地平滑【２９Ｉ”】，由于可以有较长的延时，这类算法关键技术仍然是缓冲与平滑。在强实时视频方面，如远程学习、视频会议等这类具有交互特性的视频，它们要求延迟时间短，延迟敏感强，传输这类视频以满足给定的延迟界限为目标，这类算法的关键问题是延迟受限、帧尺寸预测与变位率平滑［３５－３ｓ］等。离线平滑技术的研究在理论上虽能取得最优效果，但仍存在一些问题，如没有考虑网络传输特性、算法的运行效率问题、实际应用的评价等。实时平滑技术方面还需要更多的发展，如更有效算法的提出、算法实际运行的性能稳定性等问题。

在视频安置技术方面，由于应用背景相对简单，得到了较为成熟的发展。在早期的一些研究工作中文献【６１对此作了综述。在９０年代中后期，视频安置的研究取得了长足进展，其中文献ｆ１０］就大规模媒体流的存储方面比较了磁盘农场（ｄｉｓｋｆａｒｍ）和磁盘阵列（ｄｉｓｋａｒｒａｙ）存储方式的各自性能。文献『１．２，５５］就存储块的安置、内存开销及接纳控制等方面进行了研究。文献［７，７５～８５】就视频文件的拆分、存储块在多磁盘上安置对支持并发存取的最大流数进行了比较。文献［９５，９６］实现了一个ＶｏＤ存储方面的应用系统。目前视频安置方面的研究主要集中在多磁盘、多视频文件等大规模有效安置方面，另外由于磁盘技术的发展如ＭＺ磁盘技术，一些文献［８１～８３］专门研究视频在ＭＺ磁盘上的安置问题。但综合考虑磁盘技术、ＶＢＲ视频特性及流行视频的影响，以优化磁盘Ｉ／Ｏ的研究不足。

在磁盘Ｉ／Ｏ方面的研究主要考虑磁盘存取策略及接纳控制问题。仅考虑调度特性的算法有：ＲＲ算法以给定的逻辑服务顺序作为实际检索存储块的顺序１６１；ＥＤＦ算法规定有最早截止时间的存储块优先被调度吲：ＳＣＡＮ算法是对于给定位置的一组存储块寻找有最小的磁头开销，包括Ｂｉ—ＳＣＡＮ算法１５９１和ＢＳＣＡＮ（Ｂａｔｃｈｅｄ—ＳＣＡＮ）算法１５４１；ＳＣＡＮ—ＥＤＦ算法是ＳＣＡＮ和ＥＤＦ的综合ＩＳ６］，先应用ＥＤＦ算法，若有相同的截止时间则使用ＳＣＡＮ策略：另外一个综合算法是ＧＳＳ算法｜９】，将要服务的一组存储块进行分组，组内采用ＳＣＡＮ技术，组间应用ＲＲ策略。另外，考虑ＶＢＲ视频数据特性的算法有：比例服务策略算法［５７，５８】、ＲＴＬ算法‘”１等。但如何结合平滑技术、减弱视频的ＶＢＲ性质，提高磁盘Ｉ／０利用率的磁盘策略研究不足。

第１章绪论

１．２视频的ＶＢＲ特性

视频数据是网络流式媒体主要来源，要研究流式视频在网络上的传输与传播，就必须先要了解流式视频数据源本身的特性。本节粗略地分析了流式视频的ＶＢＲ特性、特性来源，并给出了一些视频数据实例描述，以供后面各章实验分析之用。

１．２．１ＭＰＥＧ视频

一幅含６４０＊４８０个像素、每一个像素用２４位表示图像，在未压缩的情况下该图像有９２１Ｋｂ，对于３０ｆｐｓ的视频帧率需要大约２２１Ｍｂｐｓ的传输带宽，可以看出在目前的广域网络上传送这样未经压缩的视频数据是不现实的。

目前有许多可用的数字视频压缩技术，但只有ＭＰＥＧ（ｍｏｖｉｎｇｐｉｃｔｕｒｅｅｘｐｅｒｔｇｒｏｕｐ）系列压缩技术成为目前广泛使用的事实上的标准【ｌｏＩ】，其流行的家族成员有ＭＰＥＧｌ、２、４。而ＭＰＥＧ７目前正在发展和完善。ＭＰＥＧ是一个活动图像压缩标准［１０２’１０３１，目的应用于视频邮件（Ｖｉｄｅｏｍａｉｌ）、视频会议（ｖｉｄｅｏｃｏｎｆｅｒｅｎｃｉｎｇ）、电子出版（ｅｌｅｃｔｒｏｎｉｃｐｕｂｌｉｓｈｉｎｇ）、视频点播（ｒｏＤ：Ｖｉｄｅｏｏｎｄｅｍａｎｄ）及远距离学习（ｄｉｓｔａｎｃｅｌｅａｒｎｉｎｇ）等。

一个ＭＰＥＧ技术压缩的视频位流由序列（ｓｅｑｕｅｎｃｅ）元素组成，序列由多个图像组ＧＯＰ（ＧｒｏｕｐｏｆＰｉｃｔｕｒｅ）组成，一个组ＧＯＰ由帧（ｆｒａｍｅ）或图像（ｐｉｃｔｕｒｅ）构成，一帧由一个或多个片（ｓｌｉｃｅ）构成，片由宏块（ｍａｃｒｏｂｌｏｃｋ）组成（详细的介绍见文献［３６，１０２］及相关ＩＳＯ标准）。

ＭＰＥＧ中的ＧＯＰ由三种帧构成：Ｉ（ｉｎｔｒａｃｏｄｅｄ）帧、Ｐ（ｐｒｅｄｉｃｔｅｄ）帧和Ｂ（ｂｉｄｉｒｅｃｔｏｎａｌ）帧，从尺寸上相比Ｉ帧大于Ｐ帧，Ｐ帧大于Ｂ帧。编码的图像序列由两个参数Ｍ和Ｎ说明：Ｍ表示Ｉ或Ｐ帧之间的间距，Ｎ表示两个Ｉ帧之间的距离。如Ｍ＝３和Ｎ＝９，则编码序列为：ＩＢＢＰＢＢＰＢＢＩＢＢＰＢＢＰ，ＧＯＰ的尺寸为９。

考虑到Ｂ是双向预测，所以在编码Ｂ帧时要等到后面的Ｉ或Ｐ帧被编码，通过引入一个延时实现；在解码Ｂ帧时要等到相邻后面的Ｉ或Ｐ帧被送到，若一个视频编码器产生的帧序列为：ｍＢＰＢＢＰＢＢＩＢＢＰ…，则传输顺序应改为：ＩＰＢＢＰＢＢＩＢＢＰＢＢ…，可以看出除了最初几个帧的顺序不同外，后面帧的传输模式同产生模式。

ＭＰＥＧ．１标准［ＩＳ０９３］压，缩的目的是产生位率不大于１．５Ｍｂｐｓ的视频流，目前被广泛地用于ＶＣＤ格式。ＭＰＥＧ－２［ＩＳ０９４］标准提供了伸缩性很强的压缩技术，能满足更高视觉质量的视频图像，压缩视频的位率在２～８０Ｍｂｐｓ之间，广泛地用于目前的高清晰度电视和ＤＶＤ格式。ＭＰＥＧ．１和ＭＰＥＧ－２的本质区别是前者单层，后者将压缩的视频分成两种层次：一种是基层位流（ｂａｓｅｌａｙｅｒｂｉｔｓｔｒｅａｍ），含最重要的图像信息；另一种是一个或多个增强层（ｅｎｈａｎｃｅｍｅｎｔｌａｙｅｒ），含增强图像质量的附加信息。正是这种分层技术提高了压缩的伸缩性（ｓｃａｌａｂｌｅ），同时为应用也带来了可塑性，即可满足不同用户服务质量的要求。

ＭＰＥＧ－４［Ｉｏｌｊ０４Ｉ压缩标准起始于１９９３，完成于１９９９，其目的是为著作者、服务提供者和用户提供一组不同需要的技术，和以前家族成员不同的是引入了媒体对象

中南大学博士学位论文

（ｍｅｄｉａｏｂｊｅｃｔｓ）和ＱｏＳ描述符，一组媒体对象构成一帧图象，同时和ＭＰＥＧ－２技术一样具有伸缩性。正是这种媒体对象的引入和伸缩性，使得ＭＰＥＧ．４技术正在获得广泛地应用，成为网络流媒体的一种主要格式。

ＭＰＥＧ－７””。”１的主要目的不在编码的压缩上面，而在如何描述这些多媒体材料，提供一通用的接口，以便检索或查询，其新增的特性对数据传输影响不大。１．２．２视频ⅦＲ特性的来源

视频的ＭＰＥＧ压缩有ＶＢＲ压缩和ＣＢＲ（ｃｏｎｓｔａｎｔｂｉｔｒａｔｅ）压缩两种。在同样资源（如带宽、存储等）许可下，ＶＢＲ方式压缩的视频和ＣＢＲ方式压缩的视频相比能取得更好的服务质量、能得到更好的ＱｏＳ（ｑｕａｌｉｔｙｏｆｓｅｒｖｉｃｅ）保证，由于这样的优越性，所以网上视频服务一般以ＶＢＲ方式压缩的视频作视频数据源进行存储、传输。

视频的变位率来自下面三个方面：某一帧内部的一块到下一块的变化、一帧到下一帧的变化、一景到下一景的变化。帧内变位率的影响可以忽视，极小量的缓冲便可以消除它的影响，主要的来源发生在帧到帧之间，因为景到景之间的变化也是通过帧到帧的变化反映出来的［３６，１０９－１１３］，经统计通常Ｉ帧的平均帧尺寸是Ｂ帧或Ｐ帧的１０倍以上，由于每一帧均维持相同的播放时间，为保证连续无抖动回放，这样传输的位流就是变化而波动的。

１．２．３视频ＶＢＲ特性的分析

论文实验中用到的一些视频源数据的名称、内容及节目性质描述见表１．１和１．２，其中个别视频的数据分布特性见图１．１～１．５。图１．１给出了视频Ｐａｃｅ中一段帧尺寸分布，最大帧尺寸为２１２９６Ｂ，最小的为１００２Ｂ，极大极小比例约２０倍。图１．２给出了视频Ｔｅｒｍ中一段帧尺寸分布，最大帧尺寸为７９４９Ｂ，最小的为４０Ｂ，极大极小比例约２００倍，位率改变明显。其它视频的变位率特性可从表１．２中略知一二。

图１．３中给出了视频Ｒａｃｅ中一段ＧＯＰ尺寸分布，图１．４给出该视频相应的一段位率分布情况，从中可见该视频的ＶＢＲ特性。

表１．１视频节目内容描述

视频节目性质视频节目名称（简称）视频节目名称描述

卡通片ＡｓｔｅｆｉｘＡｓｔｅｒ／ｘ

卡通片ＳｉｍｏＳｉｍｐｓｏｎｓ

网球比赛＾：ＴＰＡＴＰＴｅｎｎｉｓＦｉｎａｌ

１９９４：Ｂｅｅｋｅｒ－Ｓａｍｐｒａｓ

汽车比赛ＲａｃｅＦｏｒｍｕｌａｌｃａｒａｔＨｏｃｋｅｎｈｅｉｍ１９９４

足球赛ＳｏｃｃｅｒＳｏｃｃｅｒＷｏｒｌｄＣｕｐ１９９４：Ｂｒａｚｉｌ－Ｉｔａｌｙ

电影Ｊ－ＰａｒｋＪｕｒａｓｓｉｃＰａｒｋ

第ｌ章绪论

电影ＬａｍｂｓＴｈｅＳｉｌｅｎｃｅｏｆｔｈｅＬａｍｂｓ

电影ＳｔａｒｗａｒｓＳｔａｒｗａｒｓ

电视录像ＴｅｎｎＴｅｒｍｉｎａｔｏｒ２

电视录像１翻ｋＴ址ｋ＿—Ｐｏｌｉｔｉｃａｌｄｉｓｃｕｓｓｉｏｎ

电视录像Ｓｌａｐｓｔｉｃｋｎｌｒ∞ｓｌａｐｓｔｉｃｋｅｐｉｓｏｄｅｓ

电视录像ＮｅｗｓＮｅｗｓ

电视录像ＭｔｖＭ“—Ｍｕｓｉｃｃｌｉｐｓ

视频会议ＳｅｔｔｏｐＳｅｔｔｏｐ

歌曲年轻的朋友来相会卡拉ｏＫ带

歌曲父老乡亲卡拉ＯＫ带

表１．１－１．２中的视频源数据除最后两个其余来自站点［１１４］，其中的块尺寸不包含音频块，仅含视频块，前１４个节目，每一个节目含４００００帧，其中视频会议为５００帧，共计１１５５ＭＢ，ＧＯＰ（ｇｒｏｕｐｏｆｐｉｃｔｕｒｅ）模式为ＩＢＢＰＢＢＰＢＢＰＢＢ（１２帧）。后２个节目帧率３０ｆｐｓ，其余数据统计见表６．１。视频数据按ＭＰＥＧ－ｌ、２标准编码。

表１．２ＶＢＲ视频统计特性

帧（Ｆｒａｍｅｓ）图片组（ＧＯＰｓ）位率（Ｂｉｔｒａｔｅ）节目名压缩比

平均（ｂｉｔ）峰值，平均平均（ｂｉｔ）峰值，平均平均（Ｍｂｐｓ）峰值（Ｍｂｐｓ’Ａｓｔｅｒｉｘ１１９２２３４８６．６２６８２８２４．０Ｏ．５９１－８５

Ｓｉｍｐ１４３１８５７６１２．９２２２８４ｌ３．８０．４６１．４９

ＡＴＰ１２１２１８９０８．７２６２６４８３．０Ｏ．５５１．５８

Ｒａｃｅ８６３０７４９６．６３６９０６０３．６Ｏ．７７３．２４

Ｓｏｃｃｅｒ１０６２５１１０７．６３０１２０１３．９Ｏ．６３２．２９

Ｊ．Ｐａｒｋ２０３１３０７８９．１１５６９２８４．ＯＯ．３３１．０１

Ｌａｍｂｓ３６３７３１２１８．４８７６３４５．３Ｏ．１８Ｏ．８５

Ｓｔａｒｗａｒｓ１３０１５５９９１１．９１８７１８５５．ＯＯ＿３６４．２４

ＴｅｌＴｌｌ２４３１０９０４７．３１３０８６５３．１０．２７０．７４

Ｔｍｋ１８３１４５３７７．３１７４２７８２．７Ｏ＿３６１．００

Ｓｌａｐｓｔｉｃｋ１５０１７６４７１３．Ｏ２１１３６８４．１０．４４１．７６

Ｎｅｗｓ１７３１５３５８１２．４１８４２９９６．ＯＯ．３８２．２３

Ｍｔｖ１３４１９７８０１２．７２３７３７８６．１０．４９２．７１

ＳｃＯｏｐ３０５６０３ｌ７．７７２３７９２．０Ｏ．１５０．２７

中南大学博士学位论文

图１．１视频Ｒａｃｅ中一段帧尺寸分布示意图

图１．１、１．２中最高的线代表Ｉ帧，两Ｉ帧之间的３根中长线为Ｐ帧，两Ｐ帧之间的２根短线代表Ｂ帧，明显地可以看出３种帧之间的尺寸有较大的差别。图１．１中各Ｐ帧之间有较大的起伏，但极大极小比不如图１．２。

图１．２视频Ｔｅｒｍ中一段帧尺寸分布示意图

第１章绪论

图１．３视频Ｒａｃｅ中一段ＧＯＰ尺寸分布示意图

图１．４视频Ｒ卫ｃｅ中一段位率分布示意图

图１．３、１．４给出了视频Ｒａｃｅ中一段ＧＯＰ尺寸及相应的位率分布图，从图可以看出位率的跳变性即ＶＢＲ（变位率）特性，这种特性复杂了带宽分配和网络其它管理技术。

还有一个来自站点［１１５］的全长视频数据ｓｔａｒｗａｒｓ，ＭＰＥＧ．１标准压缩共１７４６５３帧，约２小时。

图１．５、１．６和１．７显示了其中３个视频数据源中各ＣｒＯＰ尺寸段所占的比例关系。

中南大学博士学位论文

从图中看出，大量的ＧＯＰ尺寸分布在比平均尺寸小的一侧，极大尺寸的ＧＯＰ块占极小数量，但在确保性ＱｏＳ的接纳模式…５１中，不得不考虑它们的影响。

＃

嚣

茁

Ｓ

训

珀

蛙

似

器

冒

Ｊｂ

轼匿丑ｇ例啦蛙机鬟鸟如

ｇｏＰＸＢ

图１．５视频ｓｔａｒａ．ｖａｒｓＧＯＰ统计分布图图１．６视频ａｆｐＧＯＰ统计分布图

图１．７视频ｖｉｄｅｏｃｏｎｆｅｒｅｎｃｅＧＯＰ统计分布图

第ｌ章绪论

１．３全文预览

本文由一组论文构成，全文围绕ＶＢＲ流式视频在网络传输过程中所涉及的问题而展开讨论，主要内容包括：ＶＢＲ流式视频的网络Ｉ／Ｏ调度与缓冲、ＶＢＲ流式视频传输中的平滑规划、ＶＢＲ视频的磁盘安置及ＶＢＲ流式视频磁盘Ｉ／Ｏ与平滑检索等。

在第２章中讨论ＶＢＲ流式视频的多网络Ｉ／Ｏ通道并行输出调度、缓冲及接纳控制策略。问题的背景建立在当有多磁盘Ｉ／Ｏ并行输入和多网络Ｉ／Ｏ并行输出，如何计算最大化输出视频流数及相关的接纳控制算法。由于目前网络Ｉ／Ｏ带宽相比磁盘Ｉ／Ｏ带宽要富裕，很少有文献涉及此问题，本章首次对此进行了专门的研究，文中就单网络Ｉ／Ｏ通道、多网络Ｉ／Ｏ独立通道等情况下，展开了分析，提出了不同的解决方案，特别是一个在基于多处理机多任务调度的原理下而提出的带缓冲箱的多实时流并行调度模型及相应的接纳控制算法，能极大化输出流数同时也有其它好的性能，文中给出该算法的优化论证和仿真实验验证。

在第３章中讨论预存储ＶＢＲ视频的平滑传输问题。本章首先全面综述了预存储视频平滑传输的有关算法与技术，包括ＭＶＢＡ算法０２１、ＭＣＢＡ算法［１５－１７１、ＭＰＳ算法［１９－２０】、ＣＲＴＴ算法【１４１和另一类风格的Ｏｎ．Ｏｆｆ传输算法［２０，２２，２４ｌ。然后提出了本章的主要算法一最短路径平滑算法，引入平面规划设计中最短路经的概念，得出对于给定的缓冲区，计算存储视频的平滑传输计划就是在一个简单直线多边形内寻找最短路径问题，并证明这一最短路径具有优化的平滑性能，即极小化峰值位率、极小化位率的变化量和尽可能小的位率改变次数。紧接着的两节，在基于最短路径平滑思想的基础上，进一步扩充这一平滑技术到一些特殊的应用环境。一个是异步传输平滑算法，主要考虑两个异质网络段之间如何进行ＶＢＲ视频流的传输问题，因在异质网络段之间存在支持不同包长协议和不同步传输等可能性问题。另一个是残余带宽下的存储视频亚实时服务协议算法，主要考虑对于有大量磁盘Ｉ／Ｏ通道的存储子系统，每一个Ｉ／Ｏ通道可能残余～些带宽，而这一部分带宽不足以支持一个实时视频流服务，常常被闲置，不能参与接纳控制计算。大量磁盘Ｉ／Ｏ通道可能残余许多这样的带宽，这样浪费是巨大的。服务协议算法专门讨论了这些带宽的利用问题，并研究了如何有效地分配这些带宽，提出了最短包迹等概念。

在第４章讨论了强实时视频的实时平滑问题。强实时视频（如视频会议、远程学习等具有交互特性的视频）跟预存储视频和弱实时视频（如电视新闻、实况转播等节目）不同，它要求有短的延迟，而且在平滑发送计划计算过程中其将来帧尺寸信息是不可精确知道的，但可以根据视频帧之间的自相关特性进行预测。这类视频的平滑和预存储平滑中的缓冲与预取技术有着本质的不同，平滑技术中主要关心在满足给定延迟条件下，加上非精确的帧预测技术，来尽可能缩减峰值位率和发送位率的改变次数。文中基于最短路径平滑技术而提出的实时最短路径平滑算法和实时ＭＶＢＡ平滑算法在基于精确帧预测情况下能证明它们能最优化上述两个性能指标，在非精确的帧预测情况下的实际模拟中和其它现存算法相比也显示出好的性能。

Ｏ中南大学博士学位论文

在第５章讨论了ＶＢＲ视频磁盘上的安置问题。综合考虑视频的ＶＢＲ特性、ＭＺ磁盘的多率性质【ｌ”’１”１和视频节目在一定的时间段内具有流行性问题１１１８１，针对提高磁盘Ｉ／Ｏ效率，分别就单个磁盘和多个独立磁盘构成的组而提出了各自的比例安置算法，这一算法在理想的统计接纳模式下和其它现存算法相比具有良好的性能即能同时服务更多的视频流。

在第６章里专门讨论磁盘的高效率检索问题。集平滑技术和特殊的视频安置技术于一体，给出了几个特殊的磁盘Ｉ／Ｏ调度算法，它们包括：二次平滑算法，以最小的内存缓冲规划磁盘存取流，从而达到协调网络输出流：整数块平滑算法，利用平滑技术，结合磁盘块输入输出特性，提出整数块调度策略，这样可以提高单流的磁盘Ｉ，Ｏ带宽利用率：Ｏｎ－Ｏｆｆ磁盘Ｉ／Ｏ调度算法，将网络上的Ｏｎ．Ｏｆｆ传输原理引入磁盘Ｉ／Ｏ调度中，可以简化磁盘管理；检索平滑算法，以最小的缓冲区、尽可能平滑的磁盘Ｉ／Ｏ调度来规划视频文件的拆分和安置模式，最后得到尽可能高的磁盘Ｉ／Ｏ利用率，从而能服务更多的视频流数。其中检索平滑算法具有最好优化性能，以较小的系统内存资源可以获得ＶＢＲ流的近ＣＢＲ方式传输。

在第７章里对上述的工作进行了总结，并提出了进一步工作方向。最后用图１．８来描述各部分研究内容之间的关系，其中平滑技术贯穿于整个传输与调度过程。

图１．８研究内容之间的关系图

第２章视频服务器中网络Ｉ／Ｏ的调度

第２章视频服务器中网络Ｉ／Ｏ的调度

连续媒体（ＣｏｎｔｉｎｕｏｕｓＭｅｄｉａ简称ＣＭ）或流媒体（Ｓｕ＇ｅａｍＭｅｄｉａ）是指数字视频、声音和动画等这类对延时敏感的数据媒体。储存和管理这类媒体的服务器叫连续媒体服务器（即通常意义上的视频服务器），其主要功能是媒体文件的存储管理、磁盘Ｉ／Ｏ、缓冲及网口Ｉ／Ｏ调度等，为用户提供ＶｏＤ服务。

本章主要研究视频服务器的网络Ｉ／Ｏ与缓冲调度问题，具体讨论流媒体数据从内存经网卡向网络输出，问题的背景是在多网卡或多网络Ｉ／Ｏ并行运行及轮转法服务调度的机制下，基于多任务调度原理和流媒体的实时特性，解决如何进行数据块输出调度、新流接纳及优化问题。以往的工作主要考虑缓冲区尺寸的计算和磁盘缓冲调度，而网络Ｉ／Ｏ调度和磁盘Ｉ／Ｏ调度相比，由于其在视频系统中资源相对丰富而被研究者所忽视，本章在这方面作了详细的探讨。

本章的以下部分是这样组织的：在第ｌ节描述了具有多网络ＹＯ和多磁盘Ｉ／Ｏ的ＣＭ服务器的工作模型，并提出要解决的问题；第２节讨论了单网口时的输出量化计算与接纳控制；第３节详细地讨论了多网络Ｉ／Ｏ并行工作模型、随机调度方法及接纳控制；第４节研究了优化的调度方法和接纳计算问题，即带缓冲箱的多流多Ｉ／Ｏ并行调度算法。最后对３种调度策略进行了仿真模拟，得出带缓冲箱的调度具有较低的时间复杂度和高的带宽利用率。

２．１多网络Ｉ／Ｏ系统模型

一个能在Ｉｎｔｅｍｃｔ上提供大规模ＶｏＤ服务的视频系统由三个基本部分组成：流媒体服务器、通讯子网和客户端。流媒体服务器的基本功能模块分为：流媒体文件的组织与存储、检索、和缓冲调度，本章着重于缓冲调度。对于具有磁盘Ｉ／Ｏ多路并行输入和网络多端口并行输出的计算机而言其缓冲调度的工作模型如图２．１所示。

网口７主存主存哕ｈ存／－嘻仨多磁盘Ｉ，０输入

多冈掰，０输出

｛、卜

图２．１缓冲调度工作模型图

２中南大学博士学位论文

图中的存储视频数据经磁盘Ｉ／Ｏ多路并行输入，预先置入缓冲区，后经缓冲区由网口／／Ｏ多路并行输出、或直接由专用数据通道传经网口并行输出到通讯子网。为更加清晰地描述工作模型，先定义几个概念：

定义１（数据块）：在这里是最小的、不可分割的调度单位。它可以是文献［５５】中ＣＴＬ（ｃｏｎｓｔａｎｔｔｉｍｅｌｅｎｇｔｈ）块、ＣＤＬ（ｃｏｎｓｔａｎｔｄａｔａｌｅｎｇｔｈ）块、ＲＴＬ（ｒｏｕｎｄｔｉｍｅｌｅｎｇｔｈ）块１７７】或ＰＬ块（见第５章）。用，标识它的长度，ｚ的取值和调度周期时长有关，在这里不妨假设它正比于周期时长。（这里的数据块概念类似于第５章中的存储块概念）定义２（流）：是数据块的序列。流在服务器端是数据块周期性地被调度输出，在客户端是数据的连续消耗，如视频中的帧率。用ｉ标识某一路流，流中每一块的长度是可知的，流的其它参数见表２．１。

表２．１流参数表

ｌ流标识符晟小块长晟大块长平均块长—般块长

ｌｉｌ●ｌ”！？ｂ

定义３（调度周期Ｔ）：是一个固定的、重复被执行的时间片段。规定在一个调度周期内要为每一路流调度一个数据块，块长是可变的。如采用轮转法调度，则令轮转法的调度周期时长为７１，用，表示调度周期的顺序号，Ｊ∈｛１，２…）。

若服务器在第，个调度周期正在为糟路流提供数据块调度服务，假定磁盘端口给出的块是及时的（假定磁盘Ｉ／０带宽是无限的，传输瓶颈在网络输出端。磁盘带宽的无限可以从两个方面来理解：一是具有独立存取能力的磁盘组数不断增加；二是单个磁盘输入流可以对应无数个面向用户的不同输出流，见第３章）。按照要求，在每一个调度周期，内必须完成相应ｎｊ个数据块的输出调度任务，由于三个方面的原因：在同一调度周期内各流之间的数据块长是不同的、在不同的调度周期内同一流的块长是变化的、网口输出带宽资源是有限的。为确保每一调度周期的完成，应仔细规划。下面就单网络Ｉ／Ｏ接口和多网络Ｉ／Ｏ接口两种情况下，讨论数据块的优化调度和新流接纳条件。

２．２单网络Ｉ『ｏ调度

在单网络Ｉ／Ｏ情况下，所有的数据块从一个通道中输出，在第，个调度周期，设ＣＭ服务器的调度管理区正在为ｎｊ路视频流进行调度，在丁内对崎个流分别进行一次调度服务，对于同一流在不同的调度周期内，其被服务的相对顺序可以不同，如第ｆ路流在前一周期被首次调度，在下一周期可以被最后调度（这要求客户缓冲区有足够两个周期内消耗的预缓冲数据）。令单个网络Ｉ／Ｏ的数据传输率是Ｒ，对于只有一个网络Ｉ／Ｏ出口的ＣＭ服务器来说，在第，个调度周期内其服务的流数砖（考虑ＣＰＵ的处理速度很快，不影响数据传输）理论上应满足公式（１）。

第２章视颁服务器中网络Ｉ］Ｏ的调度

妻Ｉｕ＋６≤Ｒ×ｒ，Ｊ∈｛１，２…）（１）

其中ｓ表示ＣＭ服务器和客户之间的控制信息所占用的带宽之和，是一个小量。对＃有两种处理方法：一是在近似计算中忽略它；二是在实际应用中控制信息和数据信息往往分道传输。以下基于后者来处理的。

当在第＾个调度周期有新流Ｓ加入时，确保服务模式下的接纳条件是（２）式成立，其中Ｍ表示最后一个流被服务完所需的周期数。

上二

∑五＋幻≤Ｒ×Ｔ，，∈协，声＋１，－?’乒＋鹏（２）计算（２）式的时间复杂度为Ｏ（Ｍ．ｎ），其中聆＝ｍａｘ协｝。一步电影按２小时计

，ｑｐ，ｊｓ＋Ｍｊ

算，调度周期为１秒，对于能支持上千路流的服务器，其接纳计算量在百万次，在实时环境下是可以接受的。在通常的情况下，取各流中最大的块来计算，（２）式改写成（３）式，只有当（３）式不成立时才用（２）式去计算。各流中的最长块可从流的属性中得到，因而计算（３）式的时间复杂度为Ｏ（ｎ）。

ｎ＋ｌ

∑甲“≤Ｒ×Ｔ（３）２．３多网络Ｉ，ｏ调度

若ＣＭ服务器具有Ｐ个并行的网络Ｉ］Ｏ，每一个网络Ｉ／Ｏ具有独立处理数据块的能力，一种情况是规定同一路流内的所有数据块只能从一个预先被分配的同一个通道输出，这种模型等同于单个多通道，接纳计算除了增加一个通道选择策略外，其余和单通道情况一样处理。在这里主要考虑另外一个情况，将流选择通道的方法由数据块来完成，即任意一流的每一个数据块可被调度到任意一个网络Ｉ／Ｏ通道输出，（ＣＰＵ负责块调度，而网络Ｉ／Ｏ通道处理数据打包等问题）。

令Ｐ个网络Ｉ／Ｏ具有相同的数据传输率Ｒ，则每一个网络Ｉ／ｏ通道在Ｔ内能输出的数据块长度为Ｌ＝ＲＸＴ。假定多磁盘Ｉ］Ｏ能及时地给出数据块，在第，个调度周期内只要直观地考虑ｎｊ个长度分别为矗的数据块，能全部装入长度为三的Ｐ个箱中，则说明冶个数据块能在，时间内能顺利从网络Ｉ／Ｏ端输出。这种情况等同于多个处理器中“一工作一处理器”的调度问题，每一个通道可看作一个处理器，每一个长度为ｌａ的数据块可看作是一个执行时间为矗的工作，其目的是决定是否所给工作能在时间三内完成。这个问题在文献【１１９】中称为Ｍａｋｅｓｐａｎ问题，它是一个ＮＰ难闯题。

中南大学博士学位论文

２．３．１ＬＳ算法及数学描述

在１３．个数据块无序的情况下，采用文献［１２０］的ＧｒａｈａｍＬＳ非空闲处理算法，新来的块总是被放入最空闲的通道中。为明确起见，在这里我们给出Ｇｒａｈａｍ算法。

Ｇｒａｈａｍ，ｓＬＳ算法

给定：ｎ个数据块。长度分别为九，２，…，，ｎ。

结果：１１个数据块在Ｐ个通道的分配结果。

１．ｆｏｒｋ＝１ｔｏＰｄｏＭ＝０；｛将所有通道中数据重设为０｝。

２．ｆｏｒｉ＝１ｔｏｎｄｏ｛将各数据块分配到各通道中去｝。

选择通道ｋ其数据量＾靠最小：

Ｍｋ＝Ｍｋ＋＾：ｆ将数据块放于通道｝

３．ｉｆｓｏｍｅＭｋ＞Ｌ

ｔｈｅｎｓｔｏｐ；ｆｎ个数据块不能在Ｐ个通道中在Ｌ时间完成｝

ｅｌｓｅｌｅｔ日＝ｍａｘ｛Ｍｋ｝；｛分配成功｝

令数据块ｒ为Ｌｓ算法最后完成的数据块（即数据块ｒ的完成时间是Ｈ），并假设数据块，的长度为ｈ。Ｇｒａｈａｍ’ｓＬＳ算法的调度结果如图２．２所示。

■

＿

Ｉ‘一

睁

＿＿——

图２．２Ｇｒａｈａｍ’ｓＬＳ算法结果图

由算法或图２．２看出，时间Ｈ—ｆ，以内为非空闲，在ｆ，以后被调度的块其开始时间都比ｈ的要晚，用数学公式表示有：

Ｈ－ｌ，－＜！霎厶；Ⅳ≤一１刍ｎ厶＋＾一１萎ｎＰＰＰ厶，

鲁等等

令翮川＝古塾Ｅｒ（Ｍ）＝吉喜厶则腿Ｅｒ（ｎ）＋ｆ，一Ｅｒ（Ｍ）。

其中牙（１，ｎ）表示通道的平均工作时间，只要Ｈ≤Ｌ，所有的块都能在Ｌ时间内被处

第２章视频朋务器中网络Ｉ／Ｏ的调度

理。公式（４）说明了如果Ｈ的上限小于三，则所有的块在给定的时间内都能被处理。

Ｈ（Ｉ，门）一．Ｈ（‘”）＋厶≤Ｌ（４）从图２．２可以得出下列一个事实。

事实１：如果一个数据块是厶，则说明在它后面被处理的所有块其长度都比ｆ，小，而且有，，≥（∑：。ｌ—ｒ）／（ｐ－１）。ｚ表示调度的顺序数，ｘ∈｛１，２，…，ｒ，…ｎ）。

２．３．２随机调度及新流接纳

假定服务器正在为崎路流提供调度任务，用ｚ≯＝ｍａｘ｛埘表示第，个周期中最大

。１日Ｊ州＋ｌｌ

的块，当在第五个调度周期有新流Ｊ加入时，在ＬＳ策略下，其最坏的调度结果是厶取７尹，且在调度周期内最后被调度，此时可（ｒ，琦＋１）。吉７严。确保服务模式下新流接纳的条件由（４）式得到（５）式，其中Ｍ表示协个流中最后被服务完所需的周期数（包括新流），接纳算法为Ａ１。

厨（１，吩＋１）＋型ｚ？ａｘｓＬ，＿，∈｛乒，声＋１，…，＾＋Ｍ）（５）

可（１，吩＋１）中的下标表示第．，个调度周期中所有数据块之和对通道数求平均。若（５）式成立，就可以接纳新流，而与它在一个调度周期内被调度的次序无关。（５）式的时间复杂度同样为Ｏ（Ｍ－疗）。

随机调度算法Ａ１

给定：Ｍ个调度周期及每一个周期的所有数据块。

结果：分配的结果。

Ｆｏｒｊ＝１ｔｏＭ

Ｈｆｎｏｔ（５））

ＲｅｔｕｒｎＮｏ：

ＥｎｄＦｏｒ；ＲｅｔｕｒｎＯＫ；

２．４优化的调度及新流接纳

条件（４）式有两个可变参数ｎ和厶。为提高ｎ的值，优化的原则是厶越小越好，尽可能让较小的块成为厶。一个视频服务器可采用两种缓冲策略：一是采用双缓冲结构；另一个是采用单缓冲结构。在不同的策略下可对调度和新流的接纳算法进行一定的优化，以下分别讨论。

６中南大学博士学位论文

２．４．１双缓冲机制下的调度及新流接纳算法

对于具有双缓冲区的ＣＭ服务器：一个缓冲区存放输出数据，另～个缓冲区存放输入数据。这样的话，在调度之前ｎ个数据块就已预置入缓冲区，有条件实现先排序、后调度。在ｎ个数据块是排序的情况下，有ｈ≥１２≥ｈ≥……≥，。，采用Ｇｒａｈａｍ的ＬＰＴ【１２”算法，即按照先大后小非空闲策略，可以获得好而稳定的调度结果，而随机调度的结果是不稳定。在这种情况下确保服务的接纳算法是Ａ２。算法Ａ２时间复杂度在Ｏ（Ｍ．１＂ｌ２）。根据上面提供的数字，算法Ａ２的计算量达Ｇ的数量级。若有ｍ个新流同时提出申请的话，这在实时环境下，要在一个调度周期内完成，将耗掉过多的ＣＰＵ资源。

排宇调度算法Ａ２

给定：Ｍ个调度周期及每一个周期的所有数据块。

结果：分配的结果。

Ｆｏｒ．－１ｔｏＭｆＭ表示ｎ＋１个流被调度完的绝对周期数｝

Ｓｏｒｔ（）；｛在第ｊ个周期对ｎ＋１个数据块排序，

Ｕ（ＬＳ（）＞Ｌ）ｆ调用Ｌｓ算法，若大于Ｌ）

ＲｅｔｕｒｎＮｏｌ

ＥｎｄＦｏｒ：ＲｅｔｕｒｎＯＫ：

２．４．２单缓冲机制下的调度及新流接纳算法

单缓冲机制下，磁盘输入的数据和等待网络输出的数据共享一个缓冲区，这种情况下数据块的到达是实时的、随机的。我们假定磁盘能及时给出数据块，且在共享缓冲区存在一块尺寸至少为口的数据滞留区（这可通过一定的延时，错开磁盘Ｉ／Ｏ调度周期和网络Ｉ／Ｏ调度周期），用来存放本调度周期无须立即发送的数据块。我们叫它为缓冲箱Ｂ，在这里叫缓冲箱是为了区别缓冲区。在上面提到，优化的方法就是让较小的块成为ｆ，。从公式（５）看出，每次计算总是取本调度周期中最长的数据块作为矗且最后被调度。若在本调度周期将一些较短的块先放入缓冲箱Ｂ中，而在本调度周期末被调度，不让长数据块成为ｆ，，这样可以减少Ｍａｋｅｓｐａｎ的值，增加输出流量。

假定缓冲箱Ｂ能容纳ｍ个数据块，其中ｏ，／是一个变量，应满足条件了？。厶≤Ｂ茎＞？厶。对于缓冲箱Ｂ设定一个阈值ｚ；“，规定只有不大于阈值，≯的数据块才能进入Ｂ中。同样令ｆ●＝ｍａｘ｛埘表示第＿，个周期中最大的块。由事实１知，当

。

ｉｔｉ［１＃／＊ｌＪ

目≥（ｐ—１）×，●且填满数据块时，那么厶一定是缓冲箱内的某一块，若旦中的块采用Ｊ

随机调度时，在最坏的’隋况下取ｆ，＝，≯且是最后被处理。那么确保服务的新流接纳公式由（６）式表示：

第２章视频服务器中网络１１０的调度

可（１，悖＋１）＋掣曙“≤三，＿，∈执ｆｉ＋ｌ，…，ｆｌ＋Ｍ｝（６）

，

当Ｂ中的块排序调度时，采用ＬＰＴ算法时，其实际结果比（６）式要好。

现在来讨论占和？≯的取值问题。各调度周期的Ｂ可能不相同，为确保起见，Ｂ应按（７）式计算，取它的下限值，Ｂ值越大时，排序调度结果越好，但对（６）式的算法没有提高。

Ｂ

２（ｐ一１）。ＩＥ。．１．１￥ＣｍｌＹＩ。衅。，Ｔｅａｍ｛ｆ』ｍ“｝（７），尹的取值由（８）式确定，其中比例因子乃为小于１的正实数，如兄＝０．５等，力的具体取值可以由经验估计（如小数据块所占的比例）和实时计算得到，见算法Ａ３。

ｌ。ｍ“＝力×Ｐ“，乃∈（ｏ，１）（８）（６）式的前提是Ｂ被填满，但当没有足够的小块填充口时，如何计算接纳条件？用盯表示填充系数，Ｂ严表示第Ｊ个周期中数据块尺寸不大于，尹的所有块之和，取矿＝（ｐ一１）×，，“，有矽。＝∞产。在垆＜掣“情况下，那么成为ｆ，的可能是缓冲箱外的某一块，或箱内的一块，当厶是缓冲箱外的某一块，在最坏的情况下取ｌｒ＝，，，则箱中的ｍ块必在７警之后被调度，那么调度结果的上限值为（９）式，注意（９）中要求Ｂｄ，ａｔａ＜占ｍｌ“。

局ｓ可（１，精＋１）＋，？“一二（口产”＋，严）（９）

Ｐ

当，，是缓冲箱内的某一块时，（６）式仍然成立。在Ｂ不满时，为确保（６）式的结果，要求（９）式的上限小于（６）式的左项，有：

Ｈ—ｊ（１，ｎｖ＋１）＋ｌｊ“一吉（垆＋尹）≤聊Ⅲ１）＋等伊，

得到。君严≥（１一乃）（ｐ一１），≯，

得到盯≥（１一石）（１０）由（１０）知填充系数仃和比例因子丑有着反向关系，力越小即进入缓冲箱的块尺寸小，则缓冲箱越应填满。因此，当乃一定后，盯满足（１０）式时，则新流的接纳可用（１１）式进行计算，确保服务的接纳算法为Ａ３。

、，面（１；崎＋１）＋乃型，Ｐ≤三，，∈｛乒，乒＋１，…，ｆｉ＋Ｍ｝（１１）

中南大学博士学位论文

为算法书写方便，我们引入一个变量ＡＬ：上一【可（１，崎＋１）＋乃旦兰，？“］，若

Ｐ’

ＺｋＬ≥０表示新流可以接受。

带缓冲箱的调度算法Ａ３：

给定：Ｍ个调度周期及每个周期的所有块尺寸。

结果：接纳结果。

１．乃＝Ｚｏ，七一∞＝Ｏ．０５：

｛初始化所有的五，如取２０＝Ｏ．５，及五变化的步长厶”，如取以”＝Ｏ．０５｝２．ＦｏｒＪ＝１ｔｏＭ

３．ｃｏｒｎ呻Ｂ？”；

４．Ｗ｝１ｉｌｅ（１００ｐ＝＝ｃｏｎ曲ｕｅ）

ｃｏｍｐｕｔｅＢ。”．盯：

Ｃａｓｅｌ：（盯≥（１一乃）ａｎｄＡｔ，≥０）Ａｄｍｉｓｓｉｏｎ＝ＯＫ，ｌｏｏｐ＝ｅｘｉｔ；

Ｃａｓｅ２：（仃＞（１一丑）ａｎｄＡＴ．＜０）乃＝乃一九印，ｌｏｏｐ＝ｃｏｎｔｉｎｕｅ

Ｃａｓｅ３：（仃＜（１一乃）ａｎｄＡＴ．＞０）乃＝乃－４－兄＂，ｌｏｏｐ＝ｃｏｎｔｉｎｕｅ：

Ｃａｓｅ４：（仃＜（１一丑）ａｎｄＡＴ．＜０）

Ｃｌｅａｎ（五），Ｒｅｔｕｒｎ（Ａｄｍｉｓｓｉｏｎ＝ＮＯ）；

｛清除本次设置的所有乃，返回接纳被拒绝｝

Ｅｎｄｗｈｉｌｅ：

５．Ｒｅｃｏｒｄ（丑）；｛记住元，以后实际调度时要用到）

６．Ｅｎｄｆｏｒ；

７．Ｒｅｔｕｒｎ（Ａｄｍｉｓｓｉｏｎ＝ｏ】Ｋ）：

Ａ３的算法中有３个循环：一个是Ｆｏｒ循环，循环次数不大于Ｍ（Ｍ的数值在前面己给出）：另一个是Ｗｈｉｌｅ循环，循环次数取决于步长兄印，其循环量是有界的：主要一个是△上的计算，其计算量是ｎ。所以Ａ３的时间复杂度是Ｏ（ｃＭ?押），优于算法Ａ２。

２．５仿真结果及性能评价

数据块特性：若轮转法调度周期的时间取１秒，对于以ＭＰＥＧ－１恒质量压缩的视频流，其数据长度在０－２Ｍｂ之间；以ＭＰＥＧ．２恒质量压缩的视频流，其数据长度在２－８Ｍｂ之间。我们仿真实验中的数据来自［１１４］，ＭＰＥＧＴｒａｃｅ的名字为ａｔｐ（ＡＴＰＴｅｎｍｓＦｉｎａｌ１９９４：Ｂｅｃｋｅｒ－Ｓａｍｐｒａｓ），用的是ＭＰＥＧ－１编码器。

本文来源：https://www.bwwdw.com/article/m1jq.html