（信号与信息处理专业论文）分布式视频转码服务调度算法研究.pdf

南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 本人学位论文及涉及相关资料若有不实，愿意承担一切相关的法律责任。 南京邮电大学学位论文使用授权声明 本人授权南京邮电大学可以保留并向国家有关部门或机构送交论文的复印件和电子文档； 允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据库进行检索；可以 采用影印、缩印或扫描等复制手段保存、汇编本学位论文。本文电子文档的内容和纸质论文 的内容相一致。论文的公布（包括刊登）授权南京邮电大学研究生院（筹）办理。 涉密学位论文在解密后适用本授权书。 研究生签名：_ 日期：_ 研究生签名：_ 导师签名：_ 日期：_ 南南 京京 邮邮 电电 大大 学学 硕士学位论文摘要硕士学位论文摘要 学科、专业：工学工学 信号与信息处理信号与信息处理 研 究 方 向：图像处理与多媒体通信图像处理与多媒体通信 作 者：2009 级研究生 谭智一谭智一 指 导 教 师：宋建新宋建新 题 目：分布式视频转码服务调度算法研究 英 文 题 目：the research on scheduling algorithms for distributed video transcoding service 主 题 词： 分布式 视频转码 任务选择 任务分配 keywords: distributed，video transcoding，task selection, task assignment 南京邮电大学硕士学位论文 摘要 i 摘摘 要要 随着分布式网络技术及其扩展形式云技术的不断发展和成熟，分布式环境下更加多元化 的服务逐渐变为现实。分布式服务系统以其组成灵活、成本低廉和不受物理地域限制等优点 逐渐成为当今网络技术中最具开发潜力的领域之一。视频服务一直是多媒体服务中最重要的 内容之一，因此，如何在分布式的环境下实现流式视频服务成为目前具有重要意义的研究课 题之一。 分布式视频服务实现的难点不在于视频的自身处理，而在于如何在分布式系统中合理的 调度和控制视频任务的处理。常见的动态实时调度算法使用的“调度反馈调整”的工作 模式可以较为有效地应对分布式环境中节点组成不稳定和节点资源分布不均匀的特点和缺陷。 本文首先描述了分布式系统及其服务实现方式，以及当前分布式环境下的实时调度所面临的 问题与挑战。然后，以分布式视频转码任务为研究对象，通过分析分布式视频转码任务对计 算机资源的占用特点提出了全新的节点资源计算方法，并以此方法获取的节点资源信息为基 础，结合经典的背包问题选择算法和贪心分配思想，提出了用于分布式环境下视频任务选择 接入的双重权值背包选择算法和用于任务 close-gop 级分配的基于资源信息的负载平衡贪心 算法。同时，通过分析实现流畅的流式视频服务实现对视频数据分段传输需要满足的条件， 提出了在视频转码任务的分布式处理完成后用于向客户提供流畅服务的视频分段传输控制算 法。 最后通过实验证明，任务的选择算法可以让分布式系统在资源有限的条件下，选择请求 总人数最多的任务请求集合接入系统，是系统对客户的支持能力得到提升；任务分配算法能 够在保证系统所有处理节点的平均资源利用率最优的同时有效降低节点的平均节点负担溢出 率；视频的分段传输控制算法能够在不影响任务生存周期的前提下，最大程度上降低视频的 close-gop 分段间的播放间隔，较为有效地提高流式视频服务的用户观看流畅性。 关键字：关键字：分布式，视频转码，任务选择，任务分配 南京邮电大学硕士学位论文 摘要 ii abstract by the continue developing of distributed network technology and its expansion form the cloud technique, diversification service based on distributed mode has become more and more popular. with the advantages of low-cost、good flexibility of foundation and independent from physical area, the distributed service system has become the most potential researching area among todays network technology study. so that how to work out the stream video service under distributed mode is a significant issue to research. the difficulty of distributed video service is not on the video operation itself but how can we give out a rational control to the whole process of distributed video service. the common “schedulingfeedbackmodification” for dynamic real-time scheduling algorithms is quite suitable and effective to solve the problem of unstable and un-uniform of node resource build up in distributed networks. this passage first give a description of distributed system and the principle of its service implement, while also show the problem and challenge of real-time distributed scheduling. then use distributed video transcoding service as a study object, through analyzing the figure of pc resource occupy of video transcoding, we proposed a novel node resource computing method. based on the node resource information obtained through this method, combine the classical knapsack-approx problem and greedy assignment ideology, we give the double-priority knapsack-approx(dpka) algorithm for task requirement selection and resource information based greedy-loadbance algorithm for close-gop level task assignment. meanwhile，by analyzing the condition which segment data transmission should satisfied for fluency stream video service, we proposed the video segment transmission control algorithm the implement of fluency stream video service for the client. finally, we proved the effective of our algorithms through s series of experiment. the experiment result showed that the dpka algorithm will make the system access more clients under the same limited resource condition and the ribgl algorithm can lower the overflow rate of node payload according to its available resource when it hold the average usage of resource of all the nodes. video segment transmission algorithm can give a good effect to reduce the interval of close-gop playing and give a better video watching quality to the client with an acceptable 南京邮电大学硕士学位论文 摘要 iii additional delay. key words: distributed, video transcoding, task selection, task assignment. 南京邮电大学硕士学位论文 目录 iv 目目 录录 摘要.i abstract.ii 目录.iv 缩略语.viii 第一章 引言.1 1.1 课题研究背景.1 1.2 分布式视频任务调度面临的挑战与现有解决方法.3 1.2.1 分布式视频任务调度面临的挑战.3 1.2.2 现有解决方法.4 1.3 论文结构与贡献.6 第二章 分布式系统及其调度算法.8 2.1 分布式服务的实现.8 2.2 分布式环境下的实时调度算法及其反馈.9 2.2.1 实时调度算法主要类型.9 2.2.2 常见反馈方式.11 2.3 视频服务常用反馈信息.15 2.3.1 峰值信噪比.15 2.3.2 均方误差.16 2.3.3 视频流畅性.17 2.4 本章小结.18 第三章 分布式视频转码服务的调度.19 南京邮电大学硕士学位论文 目录 v 3.1 总体思路.19 3.2 节点资源的计算.21 3.2.1 视频转码任务对硬件资源的占用特点.21 3.2.2 节点资源的计算.22 3.3 信道质量的反馈.24 3.3.1 流式视频服务对数据传输的要求.24 3.3.2 信道质量的反馈信息.25 3.4 任务接收策略.25 3.4.1 视频服务系统中客户请求的到达规律.25 3.4.2 基于反馈的自适应任务接收控制策略.26 3.5 本章小结.28 第四章 任务选择算法.29 4.1 分布式环境下任务选择的必要性.29 4.2 背包问题和背包选择算法.29 4.2.1 背包问题原型.29 4.2.2 背包选择算法思想.30 4.2.2 背包选择算法.32 4.3 双重权值背包选择算法.34 4.3.1 背包原型的引入依据.34 4.3.2 双重权值背包选择算法.35 4.4 本章小结.40 第五章 任务分配算法.41 南京邮电大学硕士学位论文 目录 vi 5.1 任务分配的目标.41 5.2 贪心算法.41 5.2.1 算法中的贪心思想.41 5.2.2 具有贪心思想的算法实例.42 5.3 基于资源信息的负载平衡贪心算法.44 5.3.1 贪心算法的引入依据.44 5.3.2 基于资源信息的负载平衡贪心算法.44 5.4 本章小结.46 第六章 视频分段传输控制算法.48 6.1 流畅视频服务的传输要求.48 6.2 视频分段传输控制算法的设计思路.48 6.3 视频分段传输控制算法49 6.4 本章小结.50 第七章 实验与算法性能分析.51 7.1 系统与实验平台.51 7.2 实验模拟环境.53 7.3 实验结果与分析.54 7.3.1 dpka 算法性能评估实验.54 7.3.2 ribgl 算法性能评估实验.59 7.3.3 视频分段传输控制算法性能评估实验.61 7.4 本章小结63 第八章 总结与展望.64 南京邮电大学硕士学位论文 目录 vii 8.1 论文总结.64 8.2 未来工作展望.64 参考文献.66 致谢.70 南京邮电大学硕士学位论文 缩略语 viii 缩略语缩略语 bw bandwidth 带宽 edf earliest deadline first 最小生存周期有限 fcfs first come first serve 先到先服务 dpka double priority knapsack-approx 双重权值背包选择 ribgl resource information based greedy loadbalancce 基于资源信息的负 载平衡贪心分配 rtt round transmission time 往返传输时间 et execution time 运行时间 psnr peak signal-noise ratio 峰值信噪比 cpna classified processing node assignment 分类节点调度 南京邮电大学硕士学位论文 缩略语 1 第一章第一章 引言引言 1.1 课题研究背景课题研究背景 1.1.1 分布式服务系统 分布式网络及分布式服务系统已成为未来计算机网络和多媒体应用发展主要的平台和趋 势，其拓展形式云网络和云服务更是未来网络服务和多媒体应用的主要发展方向之一。分布 式网络提供服务的特点是通过网络连接位于不同物理位置上的节点，充分利用这些节点上可 用于当前服务器接受的任务处理的资源，将一个完整的任务分散到庞大的网络中进行处理， 再把这些分散处理后的结果转变成最后客户需要的服务数据。 相比于常见的专用服务器集群模式的网络服务系统，分布式网络在服务网络的搭建上更 加灵活，由于不需要大量昂贵的高性能服务器，因而具有比大规模服务器集群构成的系统更 加低廉的成本。 早期的分布式网络和系统以及最早出现的云平台，通常具有较为明显的实验性质，其应 用也多用于一些简单的数据计算和存贮，如图 1-1（a）所示，这实际上是一种对本地计算机 简单的负担分担。 cloudcloud serverserverlocal pclocal pc storagestorage caculatingcaculating using using resultresult/ /serviceservice 图 1-1（a） ：简单的云存储/计算服务示意图 南京邮电大学硕士学位论文 缩略语 2 citycity officialofficial jobjob businessbusiness 2 yacine antif and babak hamidzadeh， “a scalable scheduling algorithm for real-time distributed systems” proceedings of 18th international conference on distributed computing system. amsterdam,netherlands:1998.352-359; 3 maoyuan zhang and ruixuan li， “ an ecg parallel scheduling algorithm for the distributed systems” ieee computer society 2006; 4 chenyang lu and jhon a. stancovic， “design and evaluation of a feedback control edf scheduling algorithm” ieee real-time system symposium 1999 20th page 56-67; 5 paolo bizzarri and andrea bondavalli， “a schedulin algorithm for aperiodic groups of tasks in disributed real-time system” ieee 1997 1071-0485/97; 6 zaharia. m and borthakur. d， “job scheduling for multi-user map-reduce cluster” technical report eecs-2009-55，uc berkeley report（2009） ； 7 dongsong zhang and shiyao jin， “feedback-based energy-aware scheduling algorithm for hard real-time tasks” ieee international conference on networking, architecture and storage 2009; 8 chenyang lu and xiaorui wang， “ feedback utilization control in distributed real-time systems eith end-to-end tasks” ieee transactions on parallel and distributed system vol.16 no.6 june 2005; 9 christian poellabauer and leo singleton， “ feedback-based dynamic voltage and frequency scaling for memory-bound real-time applications” ieee computer society 2005; 10 c. l. liu and james w. layland， “ scheduling algorithms for multiprogramming in a hard-real-time enviroment” journal of association for computer machinery vol.20 no.1 january 1973 page 46-61; 11 chenghan tsai and taiyi huan， “ an efficient real-time disk-scheduling framework with adaptive quality guarantee” ieee transaction on computers vol.57 no.5 may 2008; 南京邮电大学硕士学位论文 参考文献 66 12 lee breslao and pei cao， “web caching and zipf-like distributions-evidence and implications” 18th annual joint conference of ieee computer and communications society mar 1999; 13 wang chenjun， “the research on real-time scheduling algorithm in distributed system” pacific-asia conference on knowledge engineering and software engineering 2009; 14马丹，张薇，李肯立， “并行任务调度算法研究” 计算机应用研究 2003 年第 11 期； 15 yunpeng chai and zhihui du，“a new scheduling algorithm for distributed streaming media system based on multicast” the 28th international conference on distributed computing systems workshops ieee computer society 2008; 16 libing jiang and devarat shah， “distributed random access algorithm-scheduling and congestion control” ieee transactions on information theory vol.56 no.12 december 2010; 17 li jie， “the research of scheduling algorithms in real-time system” international conference on computer and communication technologies in agriculture engineering 2010; 18 xiaozhou wu and r. srikant， “scheduling efficiency of distributed greedy scheduling algorithms in wireless networks” ieee transactions on mobile computer vol.6 no.6 june 2007; 19 sven gestegard robertz and dan heriksson，“memory-aware feedback scheduling of control tasks” ieee 2006 1-4244-0681-1/06. 20 stephen.g.bastell and j.eric.krinker， “the implications of a distributed computingparadigm on multicast routing” ieee 1995 0-7803-2489-7/95 21 haiyan luo and song ci，“a cross-layer optimized distributed scheduling algorithm for peer-to-peer video streaming over multi-hop wireless mesh networks” ieee communication society 2009 secon 22 andrea.bianco and elisabetta,carta，“a distributed scheduling algorithm for an optical switching fabric” ieee communication society 2008 23 sonia.nazari and hamid.beigy，“a new distributed uplink packet scheduling algorithm in wimax newtorks” ieee 2010 978-1-4244-5824-0 24 yao nan lee and jung chieh-chen，“a novel distributed scheduling algorithm for downlink relay networks” ieee transactions on wireless communication vol.6 no.6 june 2007 南京邮电大学硕士学位论文 参考文献 67 25 yun hou and kin k.leung， “a novel distributed scheduling algorithm for wireless mesh networks” ieee 2007 1930-529x/07 26 luca.abeni and luigi.palopoli，“adaptive real-time scheduling for legacy applications” ieee 2008 1-4244-1506-3/08 27 xiaojun lin and shazahda， “constant-time distributed scheduling policies for ad hoc wireless networks” proceedings of the 45th ieee conference on decision & control 2006 28 lotfi.mhamdi and mounir hamdi， “distributed parallel scheduling algorithms for high-speed virtual output queuing switches” ieee 2009 978-1-4244-4671-1/09 29 liang zhou and xin bing wang， “distributed scheduling scheme for video streaming over multi-channel multi-radio multi-hop wireless networks ” ieee journal on selected areas in communications, vol. 28, no. 3, april 2010 30 wei luo and xiao qin，“exploiting redundancies to enhance schedulability in fault-tolerant and real-time distributed systems ” ieee transactions on systems, man, and cyberneticspart a: systems and humans, vol. 39, no. 3, may 2009 31 peng li， “fast, best-effort real-time scheduling algorithms” ieee transactions on computers, vol. 53, no. 9, september 2004 32 joel.wolf and deepak rajan， “flex: a slot allocation scheduling optimizer for mapreduce workloads” middleware 2010, lncs 6452, pp. 120, 2010. 33 jiani guo， “load balancing in a cluster-based web server for multimedia applications” ieee transactions on parallel and distributed systems, vol. 17, no. 11, november 2006 34 emna bouazizi and claude duvallet， “management of qos and data freshness in rtdbs using feedback control scheduling and data versions” proceedings of the eighth ieee international symposium on object-oriented real-time distributed computing (isorc05) 35 hsien-po shiang and mihaela van der schaar，“multi-user video streaming over multi-hop wireless networks: a distributed, cross-layer approach based on priority queuing” ieee journal on selected areas in communications, vol. 25, no. 4, may 2007 南京邮电大学硕士学位论文 参考文献 68 36 can zhao and xiaojun lin， “on the queue-overflow probabilities of distributed scheduling algorithms” joint 48th ieee conference on decision and control and 28th chinese control conference shanghai, p.r. china, december 16-18, 2009 37 sekhar darbha “ optimal scheduling algorithm for distributed-memory machines ” ieee transactions on parallel and distributed systems, vol. 9, no. 1, january 1998 38 kien.a.hua and ying cai， “patching: a multicast technnique for true video-on demond service” national science fundation ani-9714591 39 p.m perry leung and jaideep srivastava， “performance evaluation of distributed real-time scheduling algorithms” ieee 1990 th0309-5/90/0752$01(9. 40 tan yu-bo and wu jian-jun， “qfec:a real-time scheduling algorithm based on stream media” ieee 2009 978-1-4244-3930-0/09 41 xiaofei wang and ming fang， “two post-sc