An approximate analysis of waiting time in multi-class M/G/1/./EDF queues

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²) algorithm to get the solution. Simulation suggests that the theoretical approximation we made is quite acceptable.