Analysis of Algorithmic and Computational Aspects of Deterministic Network Calculus

Worst-case analysis of networked systems is gaining importance due to the emergence of safety-critical applications with real-time requirements in many engineering applications, such as factory automation within the Industry 4.0 paradigm, automated or tele-operated driving, coordinated unmanned aerial vehicles, etc. With all these distributed applications, ex-ante certification that the end-to-end network traversal time is always below a known maximum is required to guarantee safety for humans and property. Deterministic Network Calculus (DNC) is a well-known theory that uses (min, +) and (max, +) algebra to infer deterministic worst-case bounds on the delay and backlog of network, representing traffic as a function of time, and network elements (e.g., regulators, schedulers, links) as operations that modify said functions. However, in nontrivial cases, computation of DNC expressions is not viable without mature software support. Furthermore, some types of DNC expressions are well known to be hard to compute, however research in the algorithmic aspects is again impeded without a solid foundation based on extensible software on which improvements may be developed and tested. Existing software does not match the above criteria. In the work presented in this thesis, we filled this gap developing Nancy, a computational library with rich support for DNC operations and designed with an extensible, layered software architecture that implements the state of the art of DNC algorithms, i.e., the framework of Ultimately Pseudo-Periodic functions. Moreover, the library uses software engineering techniques for efficient use of memory and the parallelism available in multicore systems. This architecture enables to specialize algorithms to integrate DNC results for performance improvements, as well as perform new research on the algorithmic aspects of DNC. We show examples of this by discussing our own research on the topic, where we focus on a few practical use cases and provide novel algorithms and optimizations that improve their computation times by orders of magnitude. We also discuss the functional and design differences between Nancy and RTC Toolbox, showing, aided by synthetic benchmarks, the benefits in stability caused by the use of rational numerical types over floating point. Lastly, as Nancy is released as an open-source software, it provides to the research community a solid base for future DNC research, from the implementation of new studies to similar endeavors on the algorithmic aspects.