Probabilistic analysis of admission control policies for deadline-driven service disciplines

In a communication network, deadline-driven packet scheduling policies provide real-time performance guarantees by associating a deadline with each packet and then transmitting packets according to increasing orders of deadlines. New connections must undergo an admission control test before they are accepted for service. This paper develops a probabilistic model to analyze admission control methods for the general class of non-preemptive deadline-oriented packet scheduling policies. We present a general-purpose schedulability theorem for non-preemptive Earliest Deadline First packet scheduling. We then show how to use a stochastic knapsack to compute acceptance probabilities. A large-scale simulation study demonstrates that our method provides highly accurate predictions of acceptance rates for multiple types of traffic requests.