DocumentCode :
964128
Title :
Dynamic window-constrained scheduling of real-time streams in media servers
Author :
West, Richard ; Zhang, Yuting ; Schwan, Karsten ; Poellabauer, Christian
Volume :
53
Issue :
6
fYear :
2004
fDate :
6/1/2004 12:00:00 AM
Firstpage :
744
Lastpage :
759
Abstract :
We describe an algorithm for scheduling packets in real-time multimedia data streams. Common to these classes of data streams are service constraints in terms of bandwidth and delay. However, it is typical for real-time multimedia streams to tolerate bounded delay variations and, in some cases, finite losses of packets. We have therefore developed a scheduling algorithm that assumes streams have window-constraints on groups of consecutive packet deadlines. A window-constraint defines the number of packet deadlines that can be missed (or, equivalently, \´must be met) in a window of deadlines for consecutive packets in a stream. Our algorithm, called dynamic window-constrained scheduling (DWCS), attempts to guarantee no more than re out of a window of y deadlines are missed for consecutive packets in real-time and multimedia streams. Using DWCS, the delay of service to real-time streams is bounded, even when the scheduler is overloaded. Moreover, DWCS is capable of ensuring independent delay bounds on streams, while, at the same time, guaranteeing minimum bandwidth utilizations over tunable and finite windows of time. We show the conditions under which the total demand for bandwidth by a set of window-constrained streams can exceed 100 percent and still ensure all window-constraints are met. In fact, we show how it is possible to strategically skip certain deadlines in overload conditions, yet fully utilize all available link capacity and guarantee worst-case per-stream bandwidth and delay constraints. Finally, we compare DWCS to the "distance-based" priority (DBP) algorithm, emphasizing the trade-offs of both approaches.
Keywords :
delays; multimedia servers; operating systems (computers); real-time systems; scheduling; bandwidth; distance-based priority algorithm; dynamic window-constrained scheduling; multimedia server; packet scheduling; real-time system; window-constraint; Bandwidth; Delay; Dynamic scheduling; Heuristic algorithms; Loss measurement; Performance loss; Personal digital assistants; Scheduling algorithm; Sensor systems and applications; Streaming media; 65; Real-time systems; multimedia; scheduling.; window-constraints;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/TC.2004.10
Filename :
1288549
Link To Document :
بازگشت