Advances in Theory and Applicability of Stochastic Network Calculus

  • Stochastic Network Calculus (SNC) emerged from two branches in the late 90s: the theory of effective bandwidths and its predecessor the Deterministic Network Calculus (DNC). As such SNC’s goal is to analyze queueing networks and support their design and control. In contrast to queueing theory, which strives for similar goals, SNC uses in- equalities to circumvent complex situations, such as stochastic dependencies or non-Poisson arrivals. Leaving the objective to compute exact distributions behind, SNC derives stochastic performance bounds. Such a bound would, for example, guarantee a system’s maximal queue length that is violated by a known small prob- ability only. This work includes several contributions towards the theory of SNC. They are sorted into four main contributions: (1) The first chapters give a self-contained introduction to deterministic net- work calculus and its two branches of stochastic extensions. The focus lies on the notion of network operations. They allow to derive the performance bounds and simplifying complex scenarios. (2) The author created the first open-source tool to automate the steps of cal- culating and optimizing MGF-based performance bounds. The tool automatically calculates end-to-end performance bounds, via a symbolic approach. In a second step, this solution is numerically optimized. A modular design allows the user to implement their own functions, like traffic models or analysis methods. (3) The problem of the initial modeling step is addressed with the development of a statistical network calculus. In many applications the properties of included elements are mostly unknown. To that end, assumptions about the underlying processes are made and backed by measurement-based statistical methods. This thesis presents a way to integrate possible modeling errors into the bounds of SNC. As a byproduct a dynamic view on the system is obtained that allows SNC to adapt to non-stationarities. (4) Probabilistic bounds are fundamentally different from deterministic bounds: While deterministic bounds hold for all times of the analyzed system, this is not true for probabilistic bounds. Stochastic bounds, although still valid for every time t, only hold for one time instance at once. Sample path bounds are only achieved by using Boole’s inequality. This thesis presents an alternative method, by adapting the theory of extreme values. (5) A long standing problem of SNC is the construction of stochastic bounds for a window flow controller. The corresponding problem for DNC had been solved over a decade ago, but remained an open problem for SNC. This thesis presents two methods for a successful application of SNC to the window flow controller.

Download full text files

Export metadata

Author:Michael Beck
URN (permanent link):urn:nbn:de:hbz:386-kluedo-44970
Advisor:Jens Schmitt
Document Type:Doctoral Thesis
Language of publication:English
Publication Date:2016/11/21
Year of Publication:2016
Publishing Institute:Technische Universität Kaiserslautern
Granting Institute:Technische Universität Kaiserslautern
Acceptance Date of the Thesis:2016/10/24
Date of the Publication (Server):2016/11/23
Number of page:XII, 131
Faculties / Organisational entities:Fachbereich Informatik
DDC-Cassification:0 Allgemeines, Informatik, Informationswissenschaft / 004 Informatik
Licence (German):Standard gemäß KLUEDO-Leitlinien vom 30.07.2015