分布式多媒体任务风车调度延迟问题的研究  

The Research of Delay of Pinwheel Scheduling for Distributed Multimedia Tasks

作　　者：张占军[1] 韩承德[1] 杨学良[2] 

机构地区：[1]中国科学院计算技术研究所,北京100080 [2]中国科学技术大学研究生院,北京100039

出　　处：《计算机学报》2001年第2期191-196,共6页Chinese Journal of Computers

基　　金：国家自然科学基金! (6 99830 0 7);中国博士后科学基金

摘　　要：作者于 1999年提出了一种分布式多媒体任务的风车调度算法 DMSr,它在分布式系统各节点上通过逐步消除候选项 ,计算出各任务的调度周期 ,使多媒体无抖动地传输 .在此基础上 ,作者继续研究了 DMSr风车调度延迟最小化问题 .文章定义了延迟时间和调度启动滞后时间概念 ,分析了调度启动滞后时间、调度周期和延迟时间之间的关系 ,证明了 DMSr调度传输延迟时间是启动滞后时间的周期性函数 ,延迟时间被描述为一组具有固定斜率的锯齿线段 ,并提出了一种启动滞后时间的计算算法 Min Sum ,它能使任务总延迟最小化 .A jitterless pinwheel scheduling algorithm for distributed multimedia tasks with distance constraints, DMSr, that removes candidates step by step to calculate periods in each node of distributed system is presented by Zhang Zhan Jun et al in 1999. This paper continues to study the issue of minimizing the total end to end delay. The concepts of delay and start phase are defined and the relation between delay, start phase and scheduling period is analyzed in this paper. It is proved that if the total delay between nodes has a minimum value, it must be true that there is a delay with zero value, and transmission delay is a periodic function of the start phase with scheduling period. The delay is defined as a serrated line with a constant slope in this paper. To get the minimum delay, we can inspect all line segments in serrated line. But there are many drop points in the serrated line so that the complexity of searching algorithm is very high. In order to reduce the number of drop points searched, we define three operations, SUM, MAX and CUT for delay functions with period. The SUM is the sum of all delay function values. The MAX is the maximum of all delay function values. The CUT is domain size cut to partial size and keeps the minimum values and it not only cuts the domain size of serrated line, but also keeps their minimum values. An algorithm of calculating the start phase for minimizing the total end to end delay between two neighboring nodes, MinSum, is presented by above three operations and the time complexity is discussed in this paper. Next, we extend the MinSum to end to end delay by summing up any two consecutive nodes on router. Finally, we give our some simulation results of experiments near to the results from theory on a 100Mbps Ethernet switch.

关 键 词：分布式多媒体 风车调度栓 延迟时间 任务调度 算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构] TP37[自动化与计算机技术—计算机科学与技术]