Diff-EDF: A Simple Mechanism for Differentiated EDF Service

Many existing and emerging network applications such as voice-over-IP, videoconferencing and online gaming have end-to-end timing requirements. Despite the real-time demands of these applications, they are usually deployed on best-effort networks such as the Internet. This results in unpredictable and often unsatisfactory performance. In this paper we propose a simple and novel task (or packet) scheduling algorithm Diff-EDF (differentiated earliest deadline first) which can meet the real-time needs of these applications while continuing to provide best effort service to nonreal time traffic. In our system we consider each flow as having stochastic traffic characteristics, a stochastic deadline and a maximum allowable miss rate. The Diff-EDF service meets the flow miss rate requirements through the combination of an admission control test and a scheduling algorithm similar to EDF (earliest deadline first). However, unlike standard EDF scheduling each flow receives a deadline bias based on the flow's miss rate requirement. Applying this bias allows the miss rate to be controlled on a flow-by-flow basis. Both the admission control test and the bias selection algorithms can be computed as a linear function of the flow traffic parameters and the logarithms of the miss rate requirements resulting in an efficient implementation. In this paper, we presented the proposed system structure, protocols, algorithms, analysis and experiments. Experiments with randomly generated and real-life data closely match values predicted by the theory.