The deterministic variant of Network Calculus (NetCal, NC) enables for calculating worst-case performance guarantees in communication networks. We present the NetworkCalculus.org Deterministic Network Calculator (NCorg DNC), a tool for Deterministic Network Calculus (DNC) that extends the previous DiscoDNC by significantly enhancing its capabilities for modeling and analysis of real-world applications. The tool offers a new end-to-end solution: Starting from the prevalent model of a full-duplex Ethernet-like networks with output queueing, the NCorg DNC offers automated conversion to its DNC model as well as application of state-of-the-research DNC analysis methods to derive worst-case delay bounds. Another significant step forward are new numerical capabilities that can model and analyze, among others, discrete data arrivals as well as service. While we enhance features and capabilities, we keep the cost in terms of tool runtimes at bay. Our numerical evaluation showcases improved performance bounding w.r.t to previous DiscoDNC results and a comparative experimental tool performance study quantifying the computational impact of the added functionality. Overall, the NCorgDNC provides a more versatile and extensible foundation for deterministic performance analysis in modern networked systems.

Interconnected hard real-time systems require worst-case bounds on their communication to guarantee for correct behavior. Formal derivation of such bounds is a difficult task by itself, yet, certain system characteristics are known to pose further challenges. One of these is the presence of cyclic dependencies as – in the worst-case modeling of formal verification techniques – data flows may mutually deprive each other of any remaining data forwarding service. Network Calculus (NC) is one of the formal techniques for delay bounding. On the one hand, it offers analyses that closely model system behavior, yet often restricted to networks without cyclic dependencies. On the other hand, it offers analyses that can bound delays in case of cyclic dependencies, but suffers from untight worst-case system modeling. A recent idea is to leverage scheduling capabilities. That is, separately allocating resources at locations of interference such that cyclic dependencies are broken. Previous fundamental work was able to illustrate the beneficial applicability of this idea to ring network topologies, leaving the question of generalizability open. In this paper, we provide algorithms to generalize to generic networks and explore the tradeoff between quality and cost of breaking cycles by scheduling.

System designs for bounded communication latencies often employ a rather basic concept at their core: First-In First-Out (FIFO) queueing. Network Calculus (NC) can compute delay bounds for the end-to-end communication of data flows crossing potentially large feedforward networks of such First-In First-Out (FIFO) systems. Analysis complexity stems from the need to keep track of the interactions between flows when they compete for resources, i.e., multiplex in shared queues.

The derivation of upper bounds on data flows’ worst-case traversal times is an important task in many application areas. For accurate bounds, model simplifications should be avoided even in large networks. Network Calculus (NC) provides a modeling framework and different analyses for delay bounding. We investigate the analysis of feedforward networks where all queues implement First-In First-Out (FIFO) service. Correctly considering the effect of data flows onto each other under FIFO is already a challenging task. Yet, the fastest available NC FIFO analysis (called LUDB) suffers from limitations resulting in unnecessarily loose bounds. A feature called Flow Prolongation (FP) has been shown to improve delay bound accuracy significantly. Unfortunately, FP needs to be executed within this NC FIFO analysis very often and each time it creates an exponentially growing set of alternative networks with prolongations. FP therefore does not scale and has been out of reach for the exhaustive analysis of large networks. We introduce DeepFP, an approach to make FP scale by predicting prolongations using machine learning. In our evaluation, we show that DeepFP can improve results in FIFO networks considerably. Compared to the aforementioned LUDB analysis, DeepFP reduces delay bounds by$12.1 \;\%$on average at negligible additional computational cost.

Recently, there has been an interest from the automotive industry in a novel single-pair, half-duplex Ethernet multidrop provision (i.e., 10BASE-T1S), which relies on a coordinated channel access method provided by Physical Layer Collision Avoidance (PLCA). PLCA avoids frame collisions and provides bounded latency, while guaranteeing fairness among nodes and optimal bandwidth utilization. However, despite these advantageous features, PLCA is not aware of flow priorities and, consequently, does not provide priority-based Quality of Service (QoS). Thus, there is an opportunity for integrating QoS-aware schemes, such as the Time-Sensitive Networking (TSN)-based Time-Aware Shaper (TAS) algorithm, into PLCA. In this paper, we present modeling and analysis strategies using Network Calculus for integrating TAS with PLCA to support scheduled traffic, and we compare our modeling and analysis with a baseline work which previously modeled TAS for full-duplex point-to-point Ethernet only. We show that replacing full-duplex point-to-point links with half-duplex PLCA multidrop links still complies with end-to-end delay deadlines, while leading to a reduction of system costs due to the fewer number of Ethernet transceivers in a PLCA multidrop. Moreover, we also show that our results for TAS, when applied only on full-duplex point-to-point links, outperform the results of the baseline work in most use cases.

With the advent of standards for deterministic network behavior, synthesizing network designs under delay constraints becomes the natural next task to tackle. Network Calculus (NC) has become a key method for validating industrial networks, as it computes formally verified end-to-end delay bounds. However, analyses from the NC framework were thus far designed to bound one flow’s delay at a time. Attempts to use classical analyses for derivation of a network configuration revealed this approach to be poorly fitted for practical use cases. Take finding a delay-optimal routing configuration: One model for each routing alternative had to be created, then each flow delay had to be bounded, then the bounds were compared to the given constraints. To overcome this three-step procedure, we introduce Differential Network Calculus. We extend NC to allow for differentiation of delay bounds w.r.t. to a wide range of network parameters – such as flow routes. This opens up NC to a class of efficient nonlinear optimization techniques taking advantage of the delay bound computation’s gradient. Our numerical evaluation on the routing problem shows that our novel method can synthesize flow path in a matter of seconds, outperforming existing methods by multiple orders of magnitude.

A Peer-to-Peer (P2P) network consists of a large number of nodes, where each node may have different capabilities and properties. Finding peers with specific capabilities and properties is challenging. Thus, we propose a practical solution to the problem of peer discovery, which is finding peers in the network according to a specified query. We contribute a peer discovery for an m-ary tree-structured P2P network by utilizing a connected dominating set (CDS), a technique that is typically used in unstructured networks. Our approach of constructing the CDS requires no additional communication cost, while nodes can insert, update and remove data within ${\mathcal{O}}(1)$. Each node of the CDS – a dominating set node – maintains only a limited number of nodes. We confirm the properties of our proposed solution by using the ns-3 discrete-event simulator. This includes, besides the degree of decentralism of the peer discovery, also the heterogeneity of peers.

Peer-to-Peer (P2P) networks are one way to create large-scale distributed systems. A single peer has only a limited view on other peers. Thus, efficient searching for other peers or their content is a key performance indicator. In this paper, we investigate the search efficiency in an m-ary tree-structured P2P overlay. While previous work aimed for balancing the maximum height of a node's sub-trees, we show that keeping the height balanced throughout the overall network – a property called null-balance – will increase search performance considerably. Simulations using the ns-3 discrete-event simulator show 50% better performance w.r.t. required routing hops in these null-balanced trees. Therefore, we develop algorithms that keep a tree null-balanced if a node joins or departures. I.e., we prevent the need for restructuring. As we show, the cost of our efficient structure-preserving algorithms is easily set off by a relatively small number of search operations.

Network calculus offers the means to compute worst-case traversal times based on interpreting a system as a queueing network. A major strength of network calculus is its strict separation of modeling and analysis frameworks. That is, a model is purely descriptive and can be put into multiple different analyses to derive a data flow's worst-case traversal time bound. One of the recent results in this category is the so-called flow prolongation. Flow prolongation actively manipulates the internal model of the analysis by virtually extending the path of flows, i.e., by deliberately creating a more pessimistic setting of resource contention between flows. It was shown that flow prolongation can theoretically decrease worst-case traversal time bounds under certain assumptions. Yet, due to its exhaustive search, it was also shown that flow prolongation does not scale and it might not even have an impact in larger queueing networks. In this paper we introduce DeepFP, an approach to make the analysis scale by predicting flow prolongations using a graph neural network. In our evaluation, we show that DeepFP can improve results in networks of FIFO queues considerably, where the delay bound can be reduced by 13.7% in large FIFO networks at negligible additional cost on the execution time of the analysis.

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.

In many application domains such as the automotive and the avionics sector, networks need to fulfill different non-functional requirements. Among them is the strict demand to provide predictable and deterministic worst-case communication performance. Without formal verification of this property, an entire system embedding the network may not be certified and thus not be operated. A methodology for formal verification of communication performance is the Deterministic Network Calculus (DNC). DNC is under active development to better model real systems and to reduce pessimism required to provide verifiably correct bounds on communication delays. This previous work is mostly of theoretical nature. In our paper, we aim at providing a testbed design to benchmark bounds against measurements. Our design is composed of off-the-shelf components that we accompany with a custom software stack for taking measurements (network configuration and time stamping) as well as deriving delay bounds with DNC (system modeling and analysis). We also provide lessons-learned as well as first results that compare delay measurements and DNC-derived bounds.

The network calculus (NC) analysis takes a simple model consisting of a network of schedulers and data flows crossing them. A number of analysis "building blocks" can then be applied to capture the model without imposing pessimistic assumptions like self-contention on tandems of servers. Yet, adding pessimism cannot always be avoided. To compute the best bound on a single flow’s end-to-end delay thus boils down to finding the least pessimistic contention models for all tandems of schedulers in the network – and an exhaustive search can easily become a very resource intensive task. The literature proposes a promising solution to this dilemma: a heuristic making use of machine learning (ML) predictions inside the NC analysis.While results of this work were promising in terms of delay bound quality and computational effort, there is little to no insight on when a prediction is made or if the trained algorithm can achieve similarly striking results in networks vastly differing from its training data. In this paper, we address these pending questions. We evaluate the influence of the training data and its features on accuracy, impact and scalability. Additionally, we contribute an extension of the method by predicting the best n contention model alternatives in order to achieve increased robustness for its application outside the training data. Our numerical evaluation shows that good accuracy can still be achieved on large networks although we restrict the training to networks that are two orders of magnitude smaller.

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.

Scheduling to avoid packet collisions is a long-standing challenge in networking, and has become even trickier in wireless networks with multiple senders and multiple receivers. In fact, researchers have proved that even perfect scheduling can only achieve R = O(1/lnN). Here N is the number of nodes in the network, and R is the medium utilization rate.

Safety-critical systems require certification in order to attain permission to operate. Nowadays, these systems routinely embed a communication sub-systems whose performance must be formally verified for certification. Deterministic Network Calculus (DNC) can be employed for this task. It provides a mathematical framework to derive worst-case bounds on the delay of data flows, i.e., deterministic delivery guarantees. Their accuracy is decisive as even small improvements can change the outcome of certification. In general, delay bound accuracy depends on the accuracy of the network model. While previous work assumed that a more accurate model will invariantly yield more accurate delay bounds, we show that the opposite can actually be true. In this paper, we examine a specific weakness of DNC network analysis that leads to this counter-intuitive result. We make use of this insight in a mitigation strategy called flow prolongation. By prolonging the paths of flows, we let them interfere with more other flows but may still get better results. An evaluation in differently sized networks gives information about its impact on delay bound accuracy as well as analysis effort.

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.

Messages traversing a network commonly experience waiting times due to sharing the forwarding resources. During those times, the crossed systems must provide sufficient buffer space for queueing messages. Network Calculus (NC) is a mathematical methodology for bounding flow delays and system buffer requirements. The accuracy of these performance bounds depends mainly on two factors: the principles manifesting in the NC flow equation and the functions describing the system. We focus on the latter aspect. Common implementations of NC overapproximate these functions in order to keep the analysis computationally feasible. However, overapproximation often results in a loss of accuracy of the performance bounds. In this paper, we make such compromising tradeoffs between model accuracy and computational effort obsolete. We limit the accurate system description to functions of a compact domain, such that the accuracy of the NC analysis is preserved. Tying the domain bound to the algebraic operators of NC instead of the operational semantics of components, allows us to directly apply our solution to algebraic NC analyses that implement principles such as pay burst only once and pay multiplexing only once.

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.

Non-FIFO processing of flows by network nodes is not a rare phenomenon. Unfortunately, the state-of-the-art analytical tool for the computation of performance bounds in packet-switched networks, network calculus, cannot deal well with non-FIFO systems. The problem lies in its conventional service curve definitions. Either the definition is too strict to allow for a concatenation and consequent beneficial end-to-end analysis, or it is too loose and results in infinite delay bounds. Hence, in this paper, we propose a new service curve definition and demonstrate its strength with respect to achieving both finite delay bounds and a concatenation of systems resulting in a favorable end-to-end delay analysis. In particular, we show that the celebrated pay bursts only once phenomenon is retained even without any assumptions on the processing order of packets. This seems to contradict previous work [15]; the reasons for this are discussed.

Response time bounds are important for many application scenarios of wireless sensor networks (WSN). Often, during the planning phase of a WSN its topology is not known. It rather results from a deployment process. This makes the provision of deterministic response time bounds difficult. In this paper, we strive for statistical response time bounds in WSNs that take the stochastic nature of the deployment process into account. Based on a Monte Carlo method we derive estimates for quantiles of the maximum response time distribution under uncertainty about the topology. In numerical experiments we show that the long but light tail of this distribution causes considerably lower bounds compared to the deterministic one even under small violation probabilities and, yet, on the other hand compare favourably with the median of the distribution.