Network calculus computes end-to-end delay bounds for individual data flows in networks of aggregate schedulers. It searches for the best model bounding resource contention between these flows at each scheduler. Analyzing networks, this leads to complex dependency structures and finding the tightest delay bounds becomes a resource intensive task. The exhaustive search for the best combination of contention models is known as Tandem Matching Analysis (TMA). The challenge TMA overcomes is that a contention model in one location of the network can have huge impact on one in another location. These locations can, however, be many analysis steps apart from each other. TMA can derive delay bounds with high degree of tightness but needs several hours of computations to do so. We avoid the effort of exhaustive search altogether by predicting the best contention models for each location in the network. For effective predictions, our main contribution in this paper is a novel framework combining graph-based deep learning and Network Calculus (NC) models. The framework learns from NC, predicts best NC models and feeds them back to NC. Deriving a first heuristic from this framework, called DeepTMA, we achieve provably valid bounds that are very competitive with TMA. We observe a maximum relative error below 6%, while execution times remain nearly constant and outperform TMA in moderately sized networks by several orders of magnitude.

The group testing problem consists of determining a small set of defective items from a larger set of items based on tests on groups of items, and is relevant in applications such as medical testing, communication protocols, pattern matching, and many more. While rigorous group testing algorithms have long been known with runtime at least linear in the number of items, a recent line of works has sought to reduce the runtime to poly(k log n), where n is the number of items and k is the number of defectives. In this paper, we present such an algorithm for non-adaptive group testing termed bit mixing coding (BMC), which builds on techniques that encode item indices in the test matrix, while incorporating novel ideas based on erasure-correction coding. We show that BMC achieves asymptotically vanishing error probability with O(k log n) tests and O(k2 · log k · log n) runtime, in the limit as n → ∞ (with k having an arbitrary dependence on n). This closes an open problem of simultaneously achieving poly(k log n) decoding time using O(k log n) tests without any assumptions on k. In addition, we show that the same scaling laws can be attained in a commonly-considered noisy setting, in which each test outcome is flipped with constant probability.

Networks are integral parts of modern safety-critical systems and certification demands the provision of guarantees for data transmissions. Deterministic Network Calculus (DNC) can compute a worst-case bound on a data flow's end-to-end delay. Accuracy of DNC results has been improved steadily, resulting in two DNC branches: the classical algebraic analysis and the more recent optimization-based analysis. The optimization-based branch provides a theoretical solution for tight bounds. Its computational cost grows, however, (possibly super-)exponentially with the network size. Consequently, a heuristic optimization formulation trading accuracy against computational costs was proposed. In this article, we challenge optimization-based DNC with a new algebraic DNC algorithm. We show that: no current optimization formulation scales well with the network size and algebraic DNC can be considerably improved in both aspects, accuracy and computational cost. To that end, we contribute a novel DNC algorithm that transfers the optimization's search for best attainable delay bounds to algebraic DNC. It achieves a high degree of accuracy and our novel efficiency improvements reduce the cost of the analysis dramatically. In extensive numerical experiments, we observe that our delay bounds deviate from the optimization-based ones by only 1.142% on average while computation times simultaneously decrease by several orders of magnitude.

In this paper, we present the Disco Deterministic Network Calculator v2 – our continuation in the effort to provide open-source tool support for worst-case performance analysis. The major achievement of this release is the provision of a well-documented network calculus implementation that enables for straight-forward application as well as easy extensibility. Apart from a fair amount of bug fixes that improve the tightness of the derived bounds, our efforts resulted in two main differences to the previous versions: the first is the rigorous modularization of network calculus analyses into their distinct components and the second is a comprehensive set of functional tests for our tool.

Real-time Calculus (RTC) is a non-stochastic queuing theory to the worst-case performance analysis of distributed real-time systems. Workload as well as resources are modelled as piece-wise linear, pseudo-periodic curves and the system under investigation is modelled as a sequence of algebraic operations over these curves. The memory footprint of computed curves increases exponentially with the sequence of operations and RTC may become computationally infeasible fast. Recently, Finitary RTC has been proposed to counteract this problem. Finitary RTC restricts curves to finite input domains and thereby counteracts the memory demand explosion seen with pseudo periodic curves of common RTC implementations. However, the proof to the correctness of Finitary RTC specifically exploits the operational semantic of the greed processing component (GPC) model and is tied to the maximum busy window size. This is an inherent limitation, which prevents a straight-forward generalization. In this paper, we provide a generalized Finitary RTC that abstracts from the operational semantic of a specific component model and reduces the finite input domains of curves even further. The novel approach allows for faster computations and the extension of the Finitary RTC idea to a much wider range of RTC models.

Sensor Network Calculus (SensorNC) provides a framework for worst-case analysis of wireless sensor networks. The analysis proceeds in two steps: For a given flow, (1) the network is reduced to a tandem of nodes by computing the arrival bounds of cross-traffic; (2) the flow is separated from the cross-traffic by subtracting cross-flows and concatenating nodes on its path. While the second step has seen much treatment, the first step has not at all. This is in sharp contrast to the fact that arrival bounding takes roughly 80% of the total analysis time and is equally crucial for the tightness of the bounds. Therefore, we turn our attention to this first SensorNC analysis step with the goal to boost the performance and applicability of the overall framework. The main technical contribution is a generalized version of the concatenation theorem within the SensorNC setting. This generalization is instrumental in simplifying and streamlining the cross-traffic arrival bound computations such that run times can be reduced by more than a factor of 5. Even more important, it enables a localization of the information necessary to execute the calculations at the node level, thus enabling a distribution of the SensorNC analysis within a self-modeling WSN.