Large Deviations and Optimality of a Scheduling Discipline
Kavita Ramanan, Lucent Technologies, Bell Labs

Abstract:
An important problem in the design of high-speed communication networks is that of providing Quality of Service (QoS) guarantees, often specified in terms of loss probabilities or delays of packets in the network. The control of delays is often of crucial importance, especially for real-time applications like streaming audio. A natural question to ask in this context is how one should optimally schedule heterogeneous users in order to meet the stipulated QoS requirements for each class, specified in terms of a deadline and an allowed violation probability. We reformulate this question in terms of a large deviations problem, explain why the existing large deviations theory was inadequate to solve it, briefly describe the new techniques that had to be developed and provide intuition into the identification of the optimal scheduling discipline. If time permits, we will also discuss some extensions motivated by wireless networks.

Host: Mor Harchol-Balter