Probabilistic End-to-End Delay Bounds for Earliest Deadline First Scheduling

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 GPS. In addition we show that by altering the deadlines for EDF, we can match the desired violation probabilities more closely.