Probabilistic end-to-end delay bounds for earliest deadline first scheduling
Author:
- 7 November 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2 (0743166X) , 603-612
Abstract
We analyze the earliest-deadline-first (EDF) scheduling discipline within the framework of statistical multiplexing. We derive techniques for bounding the probability of delay violations when the session injections are independent. This enables us to determine whether a given set of sessions can all meet their delay bounds with the required violation probability. These techniques can be used by a connection admission control (CAC) scheme to decide whether to admit a new session. Our analysis applies to both the single node problem and the network problem in which the sessions have multiple hops. We also give extensive numerical results to illustrate how our bounds may be calculated and to compare the results with estimates that have been derived for generalized processor sharing (GPS). In addition we show that by altering the deadlines for EDF we can match the desired violation probabilities more closely.Keywords
This publication has 19 references indexed in Scilit:
- Workconserving vs. non-workconserving packet scheduling: an issue revisited2003
- Efficient network QoS provisioning based on per node traffic shaping2002
- Novel techniques for the design and control of generalized processor sharing schedulers for multiple QoS classes2002
- Statistical analysis of delay bound violations at an earliest deadline first (EDF) schedulerPerformance Evaluation, 1999
- Regulation of a connection admission control algorithm1999
- Guaranteeing statistical QoS to regulated traffic: the single node case1999
- Optimal multiplexing on a single link: delay and buffer requirementsIEEE Transactions on Information Theory, 1997
- Exact admission control for networks with a bounded delay serviceIEEE/ACM Transactions on Networking, 1996
- A generalized processor sharing approach to flow control in integrated services networks: the multiple node caseIEEE/ACM Transactions on Networking, 1994
- Optimal scheduling with strict deadlinesIEEE Transactions on Automatic Control, 1989