Dealing with Dependence in the End-to-End Performance Analysis in Stochastic Network Calculus

Communication networks, in particular the Internet, have become a pivotal part of our life. Since their beginnings, a key aspect of their applicability has been the performance. Safety-critical applications, for example, can sometimes only be implemented in a responsible manner if guarantees about their end-to-end delay can be made. A mathematical modeling and performance evaluation of communication networks requires a powerful set of tools that is able to incorporate their increasing complexity. The stochastic network calculus (SNC) is a versatile, mathematical framework that allows for a calculation of probabilistic end-to-end performance bounds of distributed systems. Its flexibility enables to incorporate a large class of different schedulers as well as different models of traffic processes beyond the assumption of Poisson arrivals that is predominant in queueing theory-based analyses. It originates in the so-called deterministic network analysis (DNC) in the 90's of the 20th century that was introduced to provide deterministic, ``hard'' guarantees that are of relevance, e.g., in the context of real-time systems. While the DNC of today can be used to calculate fast and accurate delay bounds of arbitrary feedforward networks, the SNC is still in a significantly earlier stage. In particular, method-pertinent dependencies, i.e., a phenomenon that occurs when independent flows become stochastically dependent after sharing resources in the network, can be considered a major challenge in the SNC with moment-generating functions (MGFs). This thesis argues to contribute to the SNC in several ways. First, we show that the ``pay multiplexing only once'' (PMOO) analysis known from the DNC is also possible in the SNC. Not only does it significantly improve end-to-end delay bounds, it also needs to consider less method-pertinent dependencies. Therefore, complexity and runtimes of the calculation are greatly reduced. Second, we introduce the concept of negative dependence to the SNC with MGFs and give numerical evidence that this can further lead to better performance bounds. Third, for the larger problem of end-to-end performance bounds of tree networks, we introduce so-called ''h-mitigators'', a modification in the calculation of MGF output bounds. It is minimally invasive, all existing results and procedures are still applicable, and improves performance bounds. As a fourth contribution, we conduct extensive numerical evaluations to substantiate our claims. Moreover, we made the respective code, the ''SNC MGF toolbox'', publicly available to ensure that the results are reproducible. At last, we conduct different stochastic analyses of a popular fair scheduler, generalized processor sharing (GPS). We give an overview of the state-of-the-art analyses in the SNC and substantiate the comparison through numerical evaluations