一种基于周期合并策略的流调度算法Patch算法可以通过少数有序生成.PDFVIP

JourⅡa1of ⑥200l software软件学报 vol_12，No．8 一种基于周期合并策略的流调度算法’ 向 哲， 钟玉琢， 冼伟铨 (清华大学计算机科学与技术系，北京 100084) E—mail：{xla“gzhe，zbo“g，xlaⅡ}@medla．cs．tslnghua．edu．cn http：／／www．tsl“ghua．edu．cn 摘要：在视频点播系统中流调度算法通过降低服务延迟和提高服务效率等措施，可显著提高系统服务能力．提 出了一种新的流调度算法 Ldeo_0n 算法还保证系统在资源耗尽的情况下，可烈提供高效、可预测的Nv()D(nearVdemand)级服务．仿真结 果表明，PeriodPatch算法在TVOD服务下的系统资源消耗程度和在有限资源下的平均用户等待时间均优于其 他算法．总之，PerlodPatch是一种高效、经济的流调度算法 美键词：流调度；周期；补丁流；vOD(vLdeo—ond蚰1and) 中躅法分类号：TP316 文献标识码：A 网络多媒体是计算机科学技术发展的重要发展方向，流调度策略及其算法是网络多媒体的组 织管理核心．在VOD(video on—demand)系统中，流调度算法主要解决合理调度视频服务器和网 络资源、优化资源配置、实现服务能力最大化的问题．在大型VoI)系统中，合适的流调度算法能够 带来服务能力数量级的提高．因此，它具有非常明显的经济价值． videoon in 典型的TVOD(truedemand)基于FIFO(firstmstout)策略，典型的Nv()D (nearvideo—on demand)则基于周期播放策略．上述策略均为固定策略．与之对应的}动策略包括 Batch策略一…、客户端缓冲策略o]、adaptive piggybacki“g策略。朝等．基于主动策略，Yu提出了前向 源，显著提高r系统性能，但它们仍有缺陷．本文结合Batch、客户端缓冲等主动策略，同时还吸收 了回定策略中的周期调度思想，提出了PerlodPatch算法．基丁该算法的大型V01)系统，性能和服 务能力明显优于已知其他算法．同时，该算法还使系统随外部条件的变化而在TvOD和NvOD两 种服务模式之间进行切换．PeriodPatch算法是一种高性能的自适应流调度算法． 本文第1节介绍流调度算法的系统模型．第2节描述PeriodPatch算法的流程，并介绍算法的 特点．第3节对PerlodPatch算法进行性能分析．最后对算法作出总结和评价． 1流调度算法的系统模型 在VoD系统中，用户向视频服务器发出命令，服务器接收命令后根据一定的规则作出应答 service 这一过程我们称之为一次系统服务操作SSO(systemoperatiorl)，如图1所示． t收稿日期：2000O卜2l}修改日期：2000()406 基金项目：国家自然科学基金资助项目；国家重点基础研究发展规划973资助项目(Gl999032700) 作者简介：向哲(197j)，男．湖北剂州』、，博士牛，牛要研究领域为刈络多媒体，多媒体系统；钟玉琢(1938)，男，辽宁沈 954 用人·教授．博上生导师一主要研究领域为多媒体计算机，多媒体通信；冼伟铨(1 )，男，广西南宁^．副敷授，主要研究领域为 多蝶恽应用系统 万方数据 1184 山“r”“0，S咖wP软件学报2001Il2(8) ◇∈《薹