Scheduling Analysis with Martingales

This paper proposes a new characterization of queueing systems by bounding a suitable exponential trans-form with a martingale. The constructed martingale is quite versatile in the sense that it captures queueing systems with Markovian and autoregressive arrivals in a unified manner; the second class is particularly relevant due to Wold’s decomposition of stationary processes. Moreover, using the framework of stochas-tic network calculus, the martingales allow for a simple handling of typical queueing operations: 1) flows’ multiplexing translates into multiplying the corresponding martingales, and 2) scheduling translates into time-shifting the martingales. The emerging calculus is applied to estimate the per-flow delay for FIFO, SP, and EDF scheduling. Unlike state-of-the-art results, our bounds capture a fundamental exponential leading constant in the number of multiplexed flows, and additionally are numerically tight. The theory of effective bandwidth emerged in the 1990s as a unified framework to analyze the queueing behavior of broad classes of arrivals (e.g., deterministically regulated, Markovian, long-range dependent); for an excellent overview see Kelly [1]. The effective bandwidth is associated to an arrival flow and is essentially a number between the flow’s average and peak rates, depending on some predefined Quality-of-Service (QoS) constraint (e.g., margins on the buffer overflow probabilities). Effective bandwidths posses