A Schedulability Condition for Deadline-Ordered Service Disciplines

Norival Figueira and Joseph Pasquale

IEEE/ACM Transactions on Networking, Vol. 5, No. 2, April 1997.


In a deadline-ordered service discipline, packets are assigned transmission deadlines and eligibility times and are transmitted in increasing order of deadlines. Different deadline-ordered service disciplines are distinguished by how they calculate deadlines and eligibility times. One of the more difficult analytical problems one faces when designing a new deadline-ordered service discipline is to prove that one can bound the end of transmission times of packets relative to their assigned deadlines, which we call schedulability. We show that, no matter how one calculates deadlines, there is a simple schedulability condition for deadline-ordered service disciplines. This schedulability condition is necessary and sufficient for preemptive deadline-ordered service disciplines and, for a server that allows the presence of non real-time packets (i.e., packets with no deadlines), it is also necessary and sufficient for non-preemptive deadline-ordered service disciplines. We also address the schedulability problem for service disciplines in general, and show the optimality of deadline-ordered service disciplines. To demonstrate how our results simplify schedulability determination, we use them to prove the known schedulability conditions of VirtualClock, PGPS, Stop-and-Go, and Delay-EDD, and to prove a new result, the necessary schedulability condition of VirtualClock.

Last updated: Fri Sep 12 10:41:01 1997