An Exploration of the Effects of State Granularity through (m, k) Real-Time Streams

• Published in: IEEE transactions on computers 2009-06, Vol.58 (6), p.784-798
• Main Authors: Yingxin Jiang, Striegel, A.
• Format: Article
• Language: English
• Subjects: Agglomeration; Computer simulation; deadline-constraint scheduling; dynamic failure; Dynamic scheduling; k)-firm task scheduling; Markov analysis; Mathematical models; Media; Multiplexing; Quality of service; queue management; Real time; Real time systems; Scalability; Schedules; Scheduling; Servers; Streams; Studies
• ISSN: 0018-9340; 1557-9956
• DOI: 10.1109/TC.2008.225

Real-time media servers are becoming increasingly important as the Internet supports more and more multimedia applications. In order to meet these ever increasing demands, real-time media servers will be responsible for supporting a large number of clients with a wide range of QoS requirements. While techniques to aggregate state information for scalability have been proposed in the literature such as with Differentiated Services; the per-stream effects of such aggregation are poorly understood. Based on the (m,k)-firm model to schedule loss-tolerant streams, we explore the effects of aggregated state information in this paper and describe our scheme, called granularity aware (m,k) queue management (GAQM). GAQM improves control over the tradeoff between scalability and per-stream QoS performance. Specifically, we identify the necessity of balancing aggregation groups according to characteristics such as relative deadlines. Another key finding of this work is that with proper biasing, the inaccuracy of aggregate state lends itself to burst scheduling rather than simply extending traditional scheduling mechanisms. This finding is profound in that the result is counterintuitive: less frequent scheduling leads to increased per-stream performance. We present detailed examples of GAQM and evaluate our work through simulation studies and Markov chain analysis.