Stochastic network calculus with martingales.

The practicality of the stochastic network calculus (SNC) is often questioned on grounds of looseness of its performance bounds. The reason for its inaccuracy lies in the usage of too elementary tools from probability theory, such as Boole’s inequality, which is unable to account for correlations and thus inappropriate to properly model arrival flows. In this thesis, we propose an extension of stochastic network calculus that characterizes its main objects, namely arrival and service processes, in terms of martingales. This characterization allows to overcome the shortcomings of the classical SNC by leveraging Doob’s inequality to provide more accurate performance bounds. Additionally, the emerging stochastic network calculus with martingales is quite versatile in the sense that queueing related operations like multiplexing and scheduling directly translate into operations of the corresponding martingales. Concretely, the framework is applied to analyze the per-flow delay of various scheduling policies, the performance of random access protocols, and queueing scenarios with a random number of parallel flows. Moreover, we show our methodology is not only relevant within SNC but can be useful also in related queueing systems. E.g., in the context of multi-server systems, we provide a martingale-based analysis of fork-join queueing systems and systems with replications. Throughout, numerical comparisons against simulations show that the Martingale bounds obtained with Doob’s inequality are not only remarkably accurate, but they also improve the Standard SNC bounds by several orders of magnitude