Research

My research is in the area of worst-case analysis of communication systems and my mehtodology of choice is network calculus. This is the Abstract of my thesis:


Accurately bounding worst-case delays and backlog is a fundamental problem in the analysis of communication networks. Such bounds are required for a variety of systems with real-time demands, for instance in avionics, the automotive sector or factory automation. In case of safety-critical systems, delay and backlog bounds are even required for certification.
Network Calculus (NC) provides a mathematical framework to derive deterministic bounds on a flow’s end-to-end delay when crossing a network and the buffer size requirement of the traversed servers, i.e., their backlog bound. NC has been widely adopted in research as well as industry – for example, the switched Ethernet backbone network used in the Airbus A380 has been certified using NC.
The evolution of the NC methodology resulted in two branches that only share the NC system description: On the one hand, there is the algebraic NC (algNC) branch. Its analysis of networks free of cyclic dependencies (feed-forward property) is based on the extension of results for sequences of servers, the so-called tandems. AlgNC established three distinct analyses to compute performance bounds. Each one defines, among other aspects, a specific way to decompose the network into tandems, their order of analysis and the applied operations. Unfortunately, these compositional algNC analyses are not able to derive tight bounds, i.e., the most accurate bounds are known to be out of their reach. In terms of bound accuracy, algNC has been superseded by the optimization-based NC (optNC) branch. While this work started with a compositional analysis as well, the most recent approach abandoned the decomposition procedure. It aims at a network-wide, global optimization: The entire network description is transformed into a set of linear programs to solve. This constitutes the only analysis currently known to achieve tight bounds on end-to-end flow delays and server backlogs in general feed-forward networks. However, the amount of linear programs to solve grows super-exponentially with the network size. The analysis is shown to be NP-hard with no algorithm known to solve the underlying problem e ciently (extension of a partial order to the set of all compatible total orders). Therefore, the optNC branch is commonly represented by an analysis variant circumventing this problem. Tightness is traded against computational feasibility by reducing the amount of linear programs to a single one. Naturally, this optNC analysis does not capture interference patterns of flows as exhaustively as the tight one. It is, however, believed to be both, e cient and accurate. The former is concluded from decades of research on optimization and its tool support, the latter from the attained global view of the optimization. Yet, neither of these assumptions had seen profound evaluation.
This thesis makes several contributions in the area of NC feed-forward analysis: First, the accuracy of current state-of-the-art algebraic NC analysis is improved with two distinct enhancements. In addition to the impact on performance bounds, this contribution also highlights that algNC’s potential has not been fully exploited. Moreover, the algebraic properties accessible during the algNC analysis also allow for features not attainable with optNC. This thesis contributes the extension to a protocol for distributed network calculus analysis that enables for in-network performance bounding. It can be employed for distributed admission control as well as monitoring tasks within self-modeling sensor networks. OptNC’s reliance on optimization software introduces a black-box view on the analysis that prohibits such features. Indeed, we also show that every optNC analysis imposes computational effort on this software that renders its application nearly impossible – even for moderately sized networks as found embedded in current systems like airplanes. These observations reveal that NC analyses can be distinguished regarding their fundamental tradeoff between e ciency and accuracy:
1. AlgNC is computationally e cient and possesses the potential to provide useful features like distributed in-network execution. However, accuracy of attained performance bounds is not competitive with optNC.
2. OptNC, on the other hand, theoretically allows for the derivation of tight bounds. Yet, in practice neither tight nor accurate bounds are computationally feasible to derive.
This thesis contributes a novel NC analysis that is based on algNC but incorporates optimization principles in order to achieve highly accurate bounds. In particular, it exploits the idea to consider the entire feed-forward network instead of focussing on individual tandem solutions only. Thereby, the analysis can make use of a vast search space for performance bounds. Being based on an optimization principle, this new approach imposes computational effort similar to optNC. Yet, in contrast to the back-box view imposed by optimization software, AlgNC grants access to the entire inner workings of the analysis procedure. We show how this knowledge can be used for multiple e ciency improvements, both algebraical and implementation-wise. This enables a fast search for the performance bounds in the search space defined by our new hybrid NC analysis. In an extensive evaluation, we demonstrate that this is the first network calculus analysis to achieve the high degree of accuracy previously exclusively attributed to optNC while demanding computation times that are several orders of magnitude below optNC. This thesis therefore provides the first e cient and accurate network calculus analysis applicable to large-scale feed-forward networks.