An approximate analysis of waiting time in multi-class M/G /1/./ EDF queues
- 15 May 1996
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 24 (1), 190-199
- https://doi.org/10.1145/233008.233043
Abstract
The Earliest-Deadline-First (EDF) queueing discipline is being more and more widely used for handling time-sensitive applications in computer systems and networks. In this paper, we consider an arbitrary number of traffic classes with class-specific soft-deadline. A soft-deadline is a target waiting-time limit that can be missed. EDF queueing has been proved to minimize the maximum delay overflow related to this limit. We propose a quantitative analysis, through the metric of mean waiting time, on the behavior of EDF queueing. This analysis gives also insight on the correlation between traffic classes with different time-constraints. Technically speaking, we have proven that the mean waiting times for an arbitrary set of N classes of traffic streams with soft deadlines are the unique solution of a system of non-linear equations under the constraint of the Kleinrock's conservation law. We then provide an O ( N 2 ) algorithm to get the solution. Simulation suggests that the theoretical approximation we made is quite acceptable.Keywords
This publication has 7 references indexed in Scilit:
- Providing quality of service in packet switched networksPublished by Springer Science and Business Media LLC ,2005
- Comparison of hybrid minimum laxity/first-in-first-out scheduling policies for real-time multiprocessorsIEEE Transactions on Computers, 1992
- A novel architecture for queue management in the ATM networkIEEE Journal on Selected Areas in Communications, 1991
- Virtual clock: a new traffic control algorithm for packet switching networksPublished by Association for Computing Machinery (ACM) ,1990
- A performance analysis of minimum laxity and earliest deadline scheduling in a real-time systemIEEE Transactions on Computers, 1989
- Optimal scheduling policies for a class of queues with customer deadlines to the beginning of serviceJournal of the ACM, 1988
- Scheduling Algorithms for Multiprogramming in a Hard-Real-Time EnvironmentJournal of the ACM, 1973