Partitioning Considerations for Quantized EDF Scheduling

Abstract

In this paper, the e.ects of quantization on EDF (Earliest Deadline .rst) queues with a stochastic tra.c model are presented. In a quantized EDF queue, jobs have limited .delity in representing their relative deadlines. It is shown that most of the bene.ts of full EDF can be achieved with relative deadlines expressed in as little as three bits. The implications of this are that QoS networking technologies such as Di.Serv can be used to implement near EDF performance while still using no more than the standard set of bits in DS/TOS .eld.