Automated and Precise Deterministic NetCal Calculations from Models to Bounds

Pesotsky, Wlad; Hermsen, Eric; Bondorf, Steffen

doi:10.4230/LIPIcs.ECRTS.2026.6

Automated and Precise Deterministic NetCal Calculations from Models to Bounds

Wlad Pesotsky

Distributed and Networked Systems, Ruhr University Bochum, Germany Eric Hermsen Distributed and Networked Systems, Ruhr University Bochum, Germany Steffen Bondorf

Distributed and Networked Systems, Ruhr University Bochum, Germany

Abstract

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, a tool for Deterministic Network Calculus 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 NetworkCalculus.org Deterministic Network Calculator offers automated conversion to its Deterministic Network Calculus model as well as application of state-of-the-research Deterministic Network Calculus 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 NetworkCalculus.org Deterministic Network Calculator provides a more versatile and extensible foundation for deterministic performance analysis in modern networked systems.

Keywords and phrases:

Network Calculus, Real-Time Systems

Copyright and License:

2012 ACM Subject Classification:

Networks

\rightarrow

Network performance evaluation ; Networks

\rightarrow

Network performance analysis ; Networks

\rightarrow

Network performance modeling ; Computing methodologies

\rightarrow

Symbolic and algebraic algorithms ; Computing methodologies

\rightarrow

Symbolic calculus algorithms ; Computing methodologies

\rightarrow

Optimization algorithms

Supplementary Material:

Software (Source Code): https://github.com/NetCal/DNC [23]

Software (Source Code and Raw Data): https://github.com/wlad-p/ECRTS2026-NCorgDNC-v3 [22]

Acknowledgements:

We would like to thank Niels Magnus Buttler, Jannis Garske, and Dan Ciubuc for their code contributions that made this tool possible.

DOI:

10.4230/LIPIcs.ECRTS.2026.6

Event:

38th European Conference on Real-Time Systems (ECRTS 2026)

Editor:

Angeliki Kritikakou

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

Deterministic Network Calculus, the deterministic variant of Network Calculus, is a mathematical framework for worst-case performance bounds analysis in resource sharing systems. With emerging requirements for real-time guarantees, Deterministic Network Calculus has found its way to various real-world applications, such as Ethernet-based solutions for avionics networks called Avionics Full-DupleX Ethernet [13, 14, 10], Time-Sensitive Networking based on Ethernet [35, 20], or data center networks [37]. Over the years, the growing complexity of modern communication and computing systems has motivated the development of software tools that automate DNC-based analyses and make them accessible to practitioners [33, 36]. These tools provide support for modeling network elements, composing service and arrival curves, and deriving performance bounds such as delay and backlog. However, existing tools often face limitations in terms of modeling flexibility and the range of supported analyses, which can hinder their applicability to emerging system architectures and use cases.

In this work, we build upon an existing DNC tool, the Disco Deterministic Network Calculator [7], and significantly extend its capabilities by introducing new analysis methods and replacing core components with newer, more feature-rich alternatives – a goal laid out before but not yet achieved [24]. The provided feature extensions enhance modeling capabilities, enable for more accurate performance guarantees, and address several practical limitations identified in previous versions of that tool. By doing so, the NetworkCalculus.org Deterministic Network Calculator tool becomes better suited for analyzing complex systems and network topologies, that arise in real-world applications¹¹1both tools, Disco Deterministic Network Calculator and NetworkCalculus.org Deterministic Network Calculator, are available at dnc.networkcalculus.org (https://github.com/NetCal/DNC). For simplicity, we denote major versions 2.x as Disco Deterministic Network Calculator [7] and the new major versions $\geq 3.0$ as NetworkCalculus.org Deterministic Network Calculator even though the name changed during v2.x development..
The main contributions of this paper are:

(i)

introducing the graph of network devices as a new starting point for models over the previous graph of contention locations,
(ii)

design and integration of new functions that broaden the scope of supported DNC analyses,
(iii)

improvements to existing functionalities that increase usability and modeling, and
(iv)

an evaluation laying out changes in computational efficiency and delay bound accuracy.

The remainder of the paper is organized as follows: Section 2 briefly recalls the fundamental mathematical background of Deterministic Network Calculus. In Section 3 we outline and relate to other implementations. Section 4 presents our proposed practical implementation of the Deterministic Network Calculus theory, i.e., our extensions and improvements. In Section 5 we provide code examples for use of the NetworkCalculus.org Deterministic Network Calculator, followed by a more comprehensive numerical evaluation in Section 6 that showcases runtime changes and potential performance bounding improvement after broadening the tool capabilities. Finally, Section 7 concludes the paper and outlines directions for future work.

2 Background

In this section, we provide an overview of the Deterministic Network Calculus framework, as well as its analysis methods.

For direct application of the Deterministic Network Calculus theory presented in this section, we assume that the “network” is modeled as an acyclic directed graph of contention locations. At these locations, data is queued to be served. We call this network model server graph. Figure 1 shows an example of a feed-forward network with three servers in tandem, one flow of interest and three cross-flows.

Figure 1: Server graph consisting of three servers, one analyzed flow of interest (foi) and three cross-flows (figure adapted from [18]).

For the extended modeling capabilities of the NetworkCalculus.org Deterministic Network Calculator, we refer the reader to Section 4.1. There, the newly added input alternative – a potentially cyclic, undirected graph of networking devices – is presented.

2.1 Data Arrivals and Forwarding Service

Definition 1 (Data Flow).

A data flow (short: flow) crosses the graph $\mathcal{G}=(S,E)$ from a source server to a given number of destination servers, both in S. Its unicast or multicast flow path is a connected subgraph of $\mathcal{G}$ .

The data a flow can put into the network is upper bounded by a function of its sending duration.

This traffic regulation of data flows w.r.t. sending data into the network is modeled by non-negative, non-decreasing functions:

Definition 2.

\mathcal{F}_{0}=\{f:\mathbb{R}^{+}\rightarrow\mathbb{R}^{+}|f(0)=0,\forall s% \leq t:f(s)\leq f(t)\}

(1)

The aforementioned constraint for deterministic analysis is assumed to be known at the flow’s source. Deterministic Network Calculus models it as a so-called arrival curve:

Definition 3 (Arrival Curve).

Let data flow f send data into a network. Assume the cumulative amount of data sent by f up until (absolute) time t is described by the function $A\in\mathcal{F}_{0}^{+}$ . Then, a function $\alpha\in\mathcal{F}_{0}$ is an arrival curve (in interval time) for $f$ iff for all time intervals of length $s\geq 0$ it holds that

\forall 0\leq s\leq t:A(t)-A(t-s)\leq\alpha(s)

(2)

I.e., in no interval of any duration $s$ , the data flow $f$ will send more data than specified by $\alpha(s)$ .

The simplest shape for an arrival curve is the so-called token-bucket curve. The Disco Deterministic Network Calculator tool is basically constrained to this curve shape:

Definition 4 (Token-bucket Curve).

\displaystyle\gamma_{r,b}(t):=\begin{cases}0,&\text{if }t=0\\ b+r\cdot t,&\text{otherwise}\end{cases}

(3)

The forwarding guarantee at a queueing location (i.e., at a server in the server graph) is called service curve:

Definition 5 (Service Curve).

If the service provided by a server for any given cumulative input over time, $A(t)$ results in an output, $A^{\prime}(t)$ , then the server is said to offer a service curve $\beta\in\mathcal{F}_{0}$ iff

\forall t:A^{\prime}(t)\geq\inf_{0\leq s\leq t}\{A(t-s)+\beta(s)\}

(4)

A number of servers fulfill a stricter definition of service curves that guarantees a higher output during periods of queued data, the so-called backlogged periods of a server.

Definition 6 (Strict Service Curve).

Assume a system produces a cumulative amount of output up until time $t$ from the data arriving at it. Let the output be denoted by function $D(t)$ . The system is said to offer a strict service curve $\beta$ to a flow if, during any (continuously) backlogged period $(s,t]$ , the difference of output is at least equal to $\beta(t-s)$ :

\displaystyle D(t)-D(s)\geq\beta(t-s)

(5)

This stronger guarantee is required for some calculations in Deterministic Network Calculus. The NetworkCalculus.org Deterministic Network Calculator takes care of these details when computing a performance bound.
The (strict) service curve is often expressed via a so-called rate-latency curve:

Definition 7 (Rate-latency Curve).

\displaystyle\beta_{R,T}(t):=R\cdot[t-T]^{+}=\begin{cases}R\cdot(t-T),&\text{% if }t>T,\\ 0,&\text{otherwise}\end{cases}

(6)

with $[x]^{+}:=\max(0,x)$ ,

i.e., the strictness property cannot be inferred from the shape. Note, that the Disco Deterministic Network Calculator tool is basically constrained to this service curve shape.

2.2 (min,plus)-Operations

Analysis of interaction between these network entities bounded by the above curves, on resource demand and supply, is captured by a set of (min,plus)-algebraic operations.

Definition 8 (Convolution).

The (min,plus)-algebraic convolution and deconvolution of two functions $f,g\in\mathcal{F}_{0}$ are defined as:

	Convolution:		$\displaystyle\hskip-17.07164pt(f\otimes g)(t)=\inf_{0\leq s\leq t}\{f(t-s)+g(s% )\}\,\forall t\geq 0\text{ and }(f\otimes g)(t)=0\,\forall t<0$		(7)
	Deconvolution:		$\displaystyle\hskip-17.07164pt(f\oslash g)(t)=\sup_{u\geq 0}\{f(t+u)-g(u)\}\,\forall t$		(8)

Theorem 9 (Performance Bounds).

Consider a system S that offers a service curve $\beta$ . Assume a flow $f$ traversing the system which has an arrival curve $\alpha$ . Then we obtain the following performance bounds:

Backlog:	$\displaystyle v(\alpha,\beta)=\sup_{s\geq 0}\{\alpha(s)-\beta(s)\}$	(9)
Delay:	$\displaystyle h(\alpha,\beta):=\inf\{d\geq 0\|(\alpha\oslash\beta)(-d)\leq 0\}$	(10)
Output:	$\displaystyle\alpha^{\prime}(t)=\begin{cases}(\alpha\oslash\beta)(t),&\text{if% }t>0\\ 0,&\text{otherwise}\\ \end{cases}$	(11)

For some analysis methods, a procedure is needed to extract a flow of interest from the remaining flows crossing the same server. For that, a left-over Service Curve is introduced:

Theorem 10 (Left-over Service Curve).

Consider a system $S$ that offers a strict service curve $\beta$ and that serves two input flows, $f_{1}$ and $f_{2}$ with arrival curves $\alpha^{f_{1}}$ and $\alpha^{f_{2}}$ , respectively. The minimum service offered to $f_{1}$ is lower bounded by the so-called left-over service curve $\beta^{l.o.f_{1}}$
In case of arbitrary multiplexing of flows crossing $S$ , it holds that

\displaystyle\beta^{l.o.f_{1}}=\beta\ominus^{ARB}\alpha^{f_{2}}

(12)

with $(\beta\ominus^{ARB}\alpha)(t)=\sup_{0\leq s\leq t}\{\beta-\alpha\}(s)$ being the non-decreasing upper closure of $(\beta-\alpha)(t)$ .

In case of FIFO multiplexing, the left-over service curve is

\displaystyle\beta^{l.o.f_{1}}=\beta\ominus^{FIFO}\alpha^{f_{2}}

(13)

where $\ominus^{FIFO}$ computes left-over service curve with the smallest latency $\theta$ in a worst-case FIFO multiplexing scenario. $\theta$ is defined as the first time instance when $\alpha$ ’s burst is worked off and its arrival rate is smaller than $\beta$ ’s service rate. At this time it can be safely assumed that the system has spare capacity that, in the FIFO multiplexing scheme, will be used to serve $f_{1}$ ’s data that arrived in the meantime. Last, we assume all curves to be non-negative.

One of the strongest results of Deterministic Network Calculus is the concatenation theorem that enables us to investigate tandems of systems as if they were single systems:

Theorem 11 (Concatenation Theorem).

Consider a flow $f$ that traverses a tandem of systems $S_{i},i=1,...,n$ . and that $S_{i}$ offers a service curve $\beta_{S_{i}}$ to $f$ . Then the concatenation of the $n$ systems offers a service curve $\bigotimes_{i=1}^{n}\beta_{S_{i}}$ to the flow.

2.3 Deterministic Network Calculus Analysis

A network calculus analysis takes the above model and combines the operations in order to compute bounds on end-to-end delays of flows and their maximum backlog along their path. Yet, there are different ways for this combination, leading to multiple established analysis methods: The Total Flow Analysis, the Separate Flow Analysis and the Pay Multiplexing Only Once analysis.

Total Flow Analysis (TFA)

Total Flow Analysis is historically the oldest method to provide performance bounds. It bounds the totality (aggregate) of flows at each server s on the flow of interest’s path $\mathcal{P}$ and derives backlog B and delay D locally. The calculations are repeated, hop by hop, from the flows start to end. The backlog and delay bounds are computed from the server-local bounds:

\displaystyle B=\max_{s\in\mathcal{P}}B_{s}\text{ , }D=\sum_{s\in\mathcal{P}}D% _{s}

Separate Flow Analysis (SFA)

Separate Flow Analysis computes a per-node left-over service curve for the flow of interest. Then, the service curves can be convolved using Theorem 11 before bounding the end-to-end delay. The analysis consists of two steps:

$\blacksquare$

Left-over Service Derivation: First, the network is abstracted to the flow of interest’s view. To achieve this, the cross-traffic arrival bounds are used to derive the left-over service curve $\beta^{l.o.}_{S}$ for every server $s\in\mathcal{P}$ . They are combined to the end-to-end service curve $\beta^{l.o.}_{e2e}$ using Theorem 11.
$\blacksquare$

Bound Computation: Secondly, the performance bounds are derived end-to-end by using a single Left-over Service Curve.

The server-local derivation of $\beta^{l.o.}_{S}$ allows to mix FIFO multiplexing and arbitrarily multiplexing servers in the Separate Flow Analysis. The biggest advantage of this method is the use of a phenomenon called Pay Bursts Only Once, leading to tighter performance bounds by avoiding accumulation of initial bursts. This property is not applicable to Total Flow Analysis.

Pay Multiplexing Only Once (PMOO)

The Pay Multiplexing Only Once analysis [28] proceeds along the lines of Separate Flow Analysis, i.e., it bounds cross-traffic only, derives an end-to-end left-over service curve for the flow of interest and computes the bounds based on this information. Thus, the Pay Multiplexing Only Once analysis possesses the Pay Bursts Only Once property as well. Yet, it changes the order during the derivation of $\beta^{l.o.}_{e2e}$ , it concatenates before subtracting cross-traffic arrivals. Pay Multiplexing Only Once does not apply the Concatenation Theorem 11 and it is only proven to be correct for arbitrary multiplexing servers whose service is given as a piecewise linear curve. In a Pay Multiplexing Only Once analysis, the end-to-end semantic is established first and cross-traffic arrival bounding also differs from SFA’s. In order to correctly account for demultiplexing on the flow of interest’s path, cross traffic needs to be grouped accordingly.

Latest research has extended this list with methods that are further discussed in Section 4.

3 Related Work

Over the past years, the field of Deterministic Network Calculus has produced a variety of analytical tools and libraries aimed at deriving deterministic performance bounds for models of communication networks. They share the Deterministic Network Calculus background with the tool proposed in this paper, i.e., the use of arrival curves, service curves, and algebraic formulations for delay and backlog analysis. In this section, we review the most relevant existing tools and surveys that are closely related to our approach.

Nancy

is an open-source Deterministic Network Calculus library developed by Zippo and Stea [39] implemented in the C# language. Similar to our new tool, curve modeling is implemented with ultimately pseudo-periodic curves. As inout, Nancy uses so-called “Nancy Expressions” [32] – i.e., the (min,plus)-algebraic term derived with Deterministic Network Calculus. This approach still allows for optimization of computational performance and analysis results by manipulating the terms. For example, the authors of Nancy developed and implemented a method for taking advantage of the connection between (min,plus) and (max,plus) algebras to speed up computations even further [38]. This is in contrast to the NetworkCalculus.org Deterministic Network Calculator approach to run a different analysis on a graph, i.e., using a graph as an earlier entry point that will eventually result in an expression. Notably, the Nancy library also implements the dual (max,plus) calculus [19].

Real-Time Calculus Toolbox

[34] is an analysis tool for Real-Time Calculus, an extension of Deterministic Network Calculus. Put simple, Real-Time Calculus uses the same mathematical background, including (max,plus) calculus, to derive bounds. With its focus on embedded systems, the Real-Time Calculus toolbox was developed in two parts. There is a library implementing (min,plus) and (max,plus) calculus on ultimately pseudo-periodic curves, written in Java. A Matlab interface to model the system to be analyzed as a network of components. While neither of these two parts is open source, there were efforts to let the Disco Deterministic Network Calculator use the interface of the Java-implementations of the Real-Time Calculus toolbox [24]. There efforts did not come to fruition and are entirely superseded by our proposed tool.

Saihu

[33] is an approach to combine multiple solutions into one single tool. The observed tools are: Disco Deterministic Network Calculator (called DiscoDNC [7]), Panco [8], a Python program proposed by Bouillard using linear programming, and xTFA [31] a solution focusing on Total Flow Analysis. Saihu works by creating a network via xml (device graph) or JSON (server graph), calling the three analysis tools and extracting the computational results. Given either of these graphs as entry point, Saihu does not integrate Nancy as it relies on the respective tools to derive the expression.

For a broader overview on DNC tools, we refer to the survey of Zhou et al. [36] that compares twelve existing solutions for computing performance bounds in networks – including the Real-Time Calculus Toolbox and the precursor of the NetworkCalculus.org Deterministic Network Calculator, Disco Deterministic Network Calculator.

4 NetworkCalculus.org Deterministic Network Calculator Tool Implementations

The NetworkCalculus.org Deterministic Network Calculator Tool is a Java-based approach to model networks and automate derivation of Deterministic Network Calculus bounds, mainly deterministic bounds on a server’s backlog as well as flow’s end-to-end delay. Fundamentally, the user is enabled to create a directed graph of servers (server graph) and the flows crossing these servers – manually or derived from a device graph. Furthermore, the NetworkCalculus.org Deterministic Network Calculator tool offers sophisticated analysis methods, such as FIFO tandem analysis, Pay Multiplexing Only Once analysis, Separate Flow Analysis (SFA), Total Flow Analysis (TFA) and Tandem Matching Analysis (TMA), resulting in even tighter performance bounds.

The NetworkCalculus.org Deterministic Network Calculator Tool originated from Disco Deterministic Network Calculator [7]. Since the publication of Disco Deterministic Network Calculator, research evolved, producing more sophisticated modeling methods and performance bounds calculations. In this section, we present our improvement and feature extensions, resulting in a state-of-the-art DNC analysis tool.

4.1 Network Modeling

Figure 2: Device graph converted to a feed-forward server graph with TP starting with Device 1. The turn from Device 2 over Device 1 to Device 3 is explicitly shown.

To apply Deterministic Network Calculus, a network of full-duplex Ethernet devices must be modeled as a directed graph consisting of servers and links (server graph). For performance analysis, such networks are required to satisfy the feed-forward property [17], meaning that the graph must be acyclic. In other words, the network must not contain any cycles, which prevents flows from forming cyclic dependencies [12].

In practice, however, real-world networks are usually represented as undirected graphs that represent the connection between devices (device graph). This representation is more intuitive, since network links are typically full-duplex. For instance, modern Ethernet standards support only full-duplex communication [1, 2]. To analyze these networks using Deterministic Network Calculus, they must first be transformed into directed feed-forward networks, where servers correspond to queues and edges represent the links between those queues.

A first commonly found convention for the required conversion from a device graph to a network graph is that of output queueing only. I.e., it is assumed that the input queues are served at line speed and the switching fabrics responsible for the “turns” connecting input and output is zero. These assumptions lead to the output queue being the only parts of devices to be modeled in the server graph.

Yet, a straightforward conversion from an undirected to a directed graph is likely to introduce cycles. To preserve the feed-forward property required by the Deterministic Network Calculus analyses, the network must be converted using a method that avoids such cycles. We have implemented the following algorithms to transforms device graphs into cycle-free server graphs, as well as algorithms to convert traffic demands defined in the device graph to flows in the server graph.

Spanning Tree Protocol (STP)

The Spanning Tree Protocol is a simple and straightforward algorithm to break cycles, introduced in [21] and standardized by the IEEE in [3]. The algorithm constructs a spanning tree on the device graph and allows traffic to be routed only along the edges of the tree. Every edge not in the tree is discarded during the conversion.

    SpanningTreeProtocol spt = new SpanningTreeProtocol();

Up/Down Routing

Up/Down Routing is an extension to the Spanning Tree Protocol, also taking advantage of a spanning tree. Nodes are assigned with levels, defining the distance to the root and edges are given a direction “up” (toward the root) or “down” (away from the root). Traffic cannot be sent to an “up” link from a “down” link, resulting in an acyclic network [29].

    UpDownRouting udRouting = new UpDownRouting();

Turn Prohibition (TP)

Turn Prohibition is another routing algorithm, proposed in [16]. A turn is represented by a tuple $(a,b,c)$ where a flow can go from node $a$ over node $b$ to node $c$ . Turns can be either allowed or prohibited. The Turn Prohibition algorithm iteratively examines each node for cycles and prohibits turns around that node. An example is shown in Figure 2. The algorithm can be found in Algorithm 1 in Appendix A, exemplifying implementations of the tool.

    TurnProhibition turnProhibition = new TurnProhibition();

After breaking up the cycles, a path routing algorithm is necessary to convert the traffic demands into flows. NetworkCalculus.org Deterministic Network Calculator is capable of using Shortest Path Routing and Greedy Routing.

Shortest Path Routing

The shortest path routing algorithm is the simplest path routing algorithm [11]. It utilizes breadth-first search to find the shortest path between a source and a destination in the server graph. The sources are the servers corresponding to the device the traffic demand originates from and the destinations are the servers corresponding to interfaces sending to the destination of the traffic demand.

    ShortestPath sp = new ShortestPath();

Greedy Routing (GreedySFA)

GreedySFA goes through the list of communication demands iteratively. For each demand, it retrieves all possible paths from its source to destination (or interfaces sending to the destination in the server graph abstraction). Then, the (valid server graph) path with the lowest “congestion” is selected and added to the server graph as a flow with the arrival curve of the traffic demand. While congestion can be defined in a variety of ways, we focus on incorporating DNC and the tool support offered by the NetworkCalculus.org Deterministic Network Calculator. That is, we compute a consequence of “congestion”: delay bounds. Doing so, we can exploit the benefits of Separate Flow Analysis analysis and improve accuracy.

    Greedy SFA gSFA = new GreedySFA();

4.2 Extension of Curve modeling

Figure 3: Approximating a Step Function and a TMDA curve with Token-bucket and Rate-latency, respectively.

Descriptions of data flows and the amount of service a system can process, are modeled via functions. These functions can be either right- or left-continuous and the deconvolution is, for example, not closed in $\mathcal{F}_{0}$ . In practice, assuming left-continuous and enforcing results of operations to be in $\mathcal{F}_{0}$ does not decrease the power of Deterministic Network Calculus. Therefore, we explicitly implement these two assumptions.

Our solution to algorithmic implementations is based on the theoretical work in [9]. Disco Deterministic Network Calculator dealt with curve modeling by using ultimately affine curves, i.e., piecewise linear segments with the last segment being used for extension, yet reliable computations were restricted to token buckets and rate latencies:

Definition 12 (Ultimately affine Curves).

Let $f$ be a function from X into $\mathbb{R}\cup\{-\infty,+\infty\}$ where $X=\mathbb{N}$ or $\mathbb{R}_{+}$ , then: $f$ is ultimately affine if

\exists T\in X,\exists\sigma,\rho\in\mathbb{R},\forall t>T,f(t)=\rho t+\sigma% \text{ or }\forall t>T,f(t)=+\infty\;(\text{resp.}-\infty)

Even though trivial curves shapes like token-bucket and rate-latency are possible, we want to make an effort to allow more complex curve shapes. Most notably, the capability of modeling step functions and Time-Division Multiple Access curves is a useful enhancement. Step functions are a key component of the Deterministic Network Calculus related research field known as Real-Time Calculus. Further, the new curve modeling allows for Time-Division Multiple Access curves which are used in TSN. To highlight the difference, refer to Figure 3. In order to model an arrival curve in the form of a step-function with Disco Deterministic Network Calculator, the user is forced to approximate the function with a token-bucket curve. It is clear that such approximations can result it loss of information and therefore worse performance bounds.

The NetworkCalculus.org Deterministic Network Calculator Tool contains a migration from ultimately affine curves to ultimately pseudo-periodic curves to deal with this issue:

Definition 13 (Ultimately pseudo-periodic Curves).

Let $f$ be a function from X into $\mathbb{R}\cup\{-\infty,+\infty\}$ where $X=\mathbb{N}$ or $\mathbb{R}_{+}$ , then: $f$ is ultimately pseudo-periodic if

\exists T\in X,\exists(c,d)\in\mathbb{R}\times X^{*},\forall t>T,f(t+d)=f(t)+c

In other words, the curves are defined by a list of linear segments and a periodic part. In contrast to the previous definition, the periodic part can be set on multiple segments, hence the periodic extension is not limited to be linear. Going back to the example of the step function in Figure 3, now the step function can be modeled precisely by setting the pseudo-period to the first step.

4.3 Extension of Deterministic Network Calculus Analyses

In Section 2 we have introduced the established DNC analyses: Total Flow Analysis, Separate Flow Analysis and Pay Multiplexing Only Once. Since the release of Disco Deterministic Network Calculator [7], further methods evolved from research. In particular, we are focusing on Tandem Matching Analysis and FIFO Tandem Analysis, both of which we have implemented in our solution.

FIFO Tandem Analysis

Multiplexing using the FIFO scheduler requires setting a latency parameter $\theta$ , which dictates the tightness of performance bounds. A poorly set $\theta$ results in a suboptimal, though valid upper bound. The objective is to derive the least (non-zero) residual forwarding service for a flow of interest, considering the interfering flows. Scheffler and Bondorf tackle the problem in [25] and provide the foundation for the FIFO Tandem Analysis: LUDB-FF, an extension to Least Upper Delay Bound [4, 5] for feed-forward networks.
LUDB-FF works by decomposing the feedforward graph into a sequence of tandems, which are then decomposed into sequences of tandems without overlapping interference by Least Upper Delay Bound. In the end, we are left with nested tandems, i.e., sequences of servers with disjunct paths or a flow path is a subpath of a different flow path.

The FIFO Tandem Analysis can be used in the NetworkCalculus.org Deterministic Network Calculator Tool as follows:

    FIFOTandemAnalysis fta = new FIFOTandemAnalysis();

FIFO Analysis Optimization with NLP Least Upper Delay Bound

The FIFO Tandem Analysis in Section 4.3 changes the network topology in order to be able to find an optimal $\theta$ parameter. Least Upper Delay Bound proposes to use optimization algorithms to find the free $\theta$ values. Herll and Bondorf showed in [18] that the search for the $\theta$ parameter can be modeled as a non-linear programming (NLP) problem. The NLP is then solved with Differential Network Calculus [15]. There exists an open-source extension to NetworkCalculus.org Deterministic Network Calculator²²2https://github.com/Lukasssssssssss/ICPE2025-Non-linear-Programming-for-the-Network-Calculus-Analysis-of-FIFO-Feedforward-Networks with an implementation of NLP Least Upper Delay Bound.

Tandem Matching Analysis (TMA)

Schmitt et al. have shown in [27] that Pay Multiplexing Only Once is not superior for all possible network topologies. On one hand, Separate Flow Analysis has the inherent problem of considering multiplexing more than once if cross-flows share longer (sub-)paths with the flow of interest, which leaves room for improvement that Pay Multiplexing Only Once builds upon. On the other hand, Pay Multiplexing Only Once is solving the problem by convolving sub-tandems before subtracting cross flows but this comes with a problem. The convolution effectively merges multiple nodes together and by that removes information about the network topology. In some cases, this leads to worse performance bounds than Separate Flow Analysis.

In [6] this problem is tackled by breaking down the bounding process into two parts:

$\blacksquare$

Bounding cross-traffic arrivals locally, i.e., at the point of interference with the flow of interest
$\blacksquare$

Tandem analysis using the Concatenation Theorem 11

Essentially, the system is decomposed into the least amount of sub-systems without losing topology information. Separate Flow Analysis corresponds to the maximum amount of sub-systems while Pay Multiplexing Only Once always inspects networks as one single server.
The Tandem Matching Analysis can be used in the NetworkCalculus.org Deterministic Network Calculator Tool as follows:

    TandemMatchingAnalysis tma = new TandemMatchingAnalysis();

5 Examples

In this section, a simple yet fully working example is provided to present the implementation, focusing on the added features since Disco Deterministic Network Calculator. The provided code is an implementation example for the following tasks:

1.

Create a device graph and transform it into a server graph.
2.

Initialize the service curves with step functions using ultimately pseudo-periodic curves.
3.

Derive backlog bound and delay bound using Tandem Matching Analysis and FIFO Tandem Analysis.

Network Creation

The first step is the creation of a network. The code is an implementation of the network shown in Figure 2. For simplicity, we use the same service curve for all devices, in this case a step function. After network definition, the device graph can be transformed into a server graph by choosing a routing algorithm and a path selection algorithm, namely Turn Prohibition and GreedySFA.

⬇

DeviceGraph deviceGraph = new DeviceGraph();

Device device1 = deviceGraph.addDevice("1");

Device device2 = deviceGraph.addDevice("2");

Device device3 = deviceGraph.addDevice("3");

Device device4 = deviceGraph.addDevice("4");

Curve arrivals =

CurveFactory.createStepFunctionArrival (1.0 ,1.0 ,2.0);

Curve service =

CurveFactory.createStepFunctionService (1.0 ,2.0 ,2.0);

deviceGraph.addLink(device1, device2, service);

deviceGraph.addLink(device2, device4, service);

deviceGraph.addLink(device4, device3, service);

deviceGraph.addLink(device3, device1, service);

deviceGraph.addTrafficDemand(device1, device2, arrivals);

deviceGraph.addTrafficDemand(device2, device3, arrivals);

deviceGraph.addTrafficDemand(device3, device4, arrivals);

TurnProhibition turnProhibition = new TurnProhibition();

GreedySFA greedySFA = new GreedySFA(0,0);

ServerGraph sg =

deviceGraph.convertToServerGraph(turnProhibition, greedySFA);

Performance Bounds and Analysis

After network initialization, we can proceed with the computation of the performance bounds backlog and delay. For that, an analysis method has to be chosen. In this example, Tandem Matching Analysis and FIFO Tandem Analysis are shown.

⬇

for(Flow foi : sg.getFlows()) {

// TFA

TotalFlowAnalysis tfa = new TotalFlowAnalysis(sg);

tfa.performAnalysis(foi);

Number delayTFA = tfa.getDelayBound();

Number backlogTFA = tfa.getBacklogBound();

// SFA

SeparateFlowAnalysis sfa = new SeparateFlowAnalysis(sg);

sfa.performAnalysis(foi);

Number delaySFA = sfa.getDelayBound();

Number backlogSFA = sfa.getBacklogBound();

// TMA

TandemMatchingAnalysis tma = new TandemMatchingAnalysis(sg);

tma.performAnalysis(foi);

Number delayTMA = tma.getDelayBound();

Number backlogTMA = tma.getBacklogBound();

// FIFO Tandem Analysis

FIFOTandemAnalysis fta = new FIFOTandemAnalysis(sg);

fta.performAnalysis(foi);

Number delayFTA = fta.getDelayBound();

Number backlogFTA = fta.getBacklogBound();

}

6 Performance Evaluation

This section evaluates the impact of the modifications introduced in Section 4.2. As our contribution primarily consists of functional enhancements to an existing implementation, the evaluation focuses on three key aspects: correctness, computational performance and improved accuracy.

First, we conducted a series of sanity checks to ensure that the migration from affine curves, i.e., ultimately affine curves with $T=0$ , to ultimately pseudo-periodic curves preserves the performance bounds. Our checks verify that the migration does not introduce unintended deviations³³3Source code and raw data are available at https://github.com/wlad-p/ECRTS2026-NCorgDNC-v3.

Second, we analyze changes in the non-functional behavior of the updated tool. To this end, we provide two experiments in this section:

The goal of the first experiment is to investigate the computational time difference between the old and the new curve representation under same conditions. For that, we run a sample of calculations with NetworkCalculus.org Deterministic Network Calculator with equal affine curves (token buckets and rate latencies) with the Disco Deterministic Network Calculator and the NetworkCalculus.org Deterministic Network Calculator. Note again, that these are stored as ultimately pseudo-periodic curves in the latter.

The goal of the second experiment is to show the potential benefits in delay bounding tightness when taking advantage of the new curve modeling. To that end, we compare model the strict service curves with Time-Division Multiple Access curves and the arrival curves with step-functions. I.e., with the tightest ones that can be abstracted as affine curves, as shown in Figure 3. These computations are subject to hyperperiod explosion as well as growing computational demand by the arbitrary-precision rational number representation introduced in the NetworkCalculus.org Deterministic Network Calculator.

6.1 Experiment Setup

For our evaluation, we took a sample of the networks created in [26]. As they were created randomly for computations with Disco Deterministic Network Calculator’s real-based number backend, we shortened to two decimals to allow for a smaller input representation to the NetworkCalculus.org Deterministic Network Calculator and set latencies to $0$ . The network characteristics are presented in Table 1.

Table 1: Properties of networks used in the performance evaluation. Showing number of servers, number of (directed) edges and number of flows for each network.

Method	Net 1	Net 2	Net 3	Net 4	Net 5	Net 6	Net 7	Net 8
Servers	14	20	50	14	18	6	24	56
Edges	14	26	90	14	20	4	28	84
Flows	17	33	230	17	27	4	47	244

We created step functions and TDMA functions from token-bucket arrival curves and rate-latency service curves in these networks, respectively. Step functions are such that the burst matches the given one, step width are $1$ and step hight calculated according to the arrival rate. TDMA curves are ultimately pseudo-periodic, too, with a latency of $0.5$ followed by twice the original rate-latency curve’s rate for another $0.5$ time units.

Experiments were conducted on a Dell Latitude 7350 laptop with an Intel Core Ultra 7165U CPU, 32GB RAM, running Ubuntu 22.04 LTS. Due to the computational demand, we capped to a max of $20$ flows to be analyzed per network. Further, to ensure fairness, a warm-up is enforced to reduce noise from JVM optimization processes (e.g., on-demand loading of libraries) before conducting the measurements.

We focus on Total Flow Analysis and Separate Flow Analysis for the analysis method and Arbitrary Multiplexing. On the one hand, these are the most common analyses in the literature and implemented in other tools as well. On the other hand, the theory behind Pay Multiplexing Only Once, Tandem Matching Analysis and Least Upper Delay Bound restricts them to (a combination of) affine curves as input. That is, only Total Flow Analysis and Separate Flow Analysis allow us to run all experiments under equal setting.

6.2 Results and Evaluation

Figure 4: Mean delay bounds in different Networks using a combination of step-functions and Time-Division Multiple Access curves versus a combination of token-bucket and rate-latency approximations in time units.

Figure 5: Mean Execution Times of Total Flow Analysis (TFA) and Separate Flow Analysis (SFA) in different Networks in milliseconds.

Table 2: Mean Execution Times of Total Flow Analysis (TFA) and Separate Flow Analysis (SFA) in different Networks in milliseconds.

Method	Net 1	Net 2	Net 3	Net 4	Net 5	Net 6	Net 7	Net 8
DiscoDNC TFA	0.1325	0.1390	0.7304	0.1273	0.1945	0.1547	0.2329	0.6312
NCorgDNC TFA	0.4851	1.6143	3.4757	1.1540	1.2496	0.4973	2.3563	3.8973
DiscoDNC SFA	0.3202	0.5063	7.4838	0.2317	0.6177	0.3334	0.9569	10.0847
NCorgDNC SFA	2.1244	6.5166	18.7477	4.5612	5.2179	1.9350	11.2209	24.2629

Table 2 depicts the outcome of the first experiment. In Figure 5 the experiment is presented visually. Overall, the results indicate that the migration to ultimately pseudo-periodic curves causes based on a arbitrary precision number representation (rationals based on Java’s BigInteger implementation) a noticeable computational overhead compared to the previous version. Across all scenarios, execution times increase on average by a factor of $7.8190$ . The results of the second experiment are presented in Figure 4. In our case, every analysis returned tighter delay bounds.

On average the delay bounds decrease by $47.5\%$ using the sophisticated curve shapes. While the increase in runtime is non-negligible, it must be considered in the context of the substantially enhanced modeling capabilities provided by the updated tool.

The new curve shapes expand the range of precisely analyzable scenarios and enable analyses that were not supported in Disco Deterministic Network Calculator. The observed computational overhead represents a trade-off between computational efficiency and expressive power. For many practical use cases, the increased flexibility, functionality and better performance bounds outweigh the additional execution time.

7 Conclusion

In this paper, we presented the NetworkCalculus.org Deterministic Network Calculator Tool, a Java-written toolbox for Deterministic Network Calculus, evolved from Disco Deterministic Network Calculator. As discussed, we extended the capabilities by new analysis methods: Tandem Matching Analysis and FIFO Tandem Analysis, alongside with a FIFO $\theta$ parameter optimizer via an external module. We implemented routing algorithms tailored to full-duplex systems, which are commonly encountered in practical real-world network application, including Time-Sensitive Networking. Further, we improved the curve modeling by switching to ultimately pseudo periodic curves, extending possible curve shapes, especially with step function and Time-Division Multiple Access and presented via experiments the trade-off between computational efficiency and the broader modeling capabilities.

Future Work

The presented extensions, in particular on regarding modeling power, naturally introduce complexity and are thus a trade-off with computational performance. A natural future work item is thus to tackle the performance overhead while keeping the new variety of possible curve shapes. It may be possible to leverage the Nancy tool, i.e., interface with it by using Deterministic Network Calculus expressions. This approach seems less complex than the integration of an entirely new backend, as was attempted with the Real-Time Calculus toolbox. Last, (max,plus) calculus is dual to (min,plus) calculus with the pseudo-inversion of curves allowing to switch between both. I.e., implementing the pseudo-inverse immediately allows (max,plus) derivations with our tool. Coupled with an interpreter of Real-Time Calculus MatLab models, our tool could provide an open-source alternative to the Real-Time Calculus toolbox.

References

[1] IEEE standard for Ethernet, amendment 10: Media access control parameters, physical layers, and management parameters for 200 Gb/s and 400 Gb/s operation.
[2] IEEE standard for Ethernet, amendment 7: Media access control parameters, physical layers, and management parameters for 2.5 Gb/s and 5 Gb/s operation, types 2.5 GBASE-T and 5 GBASE-T.
[3] IEEE standard for local area network mac (media access control) bridges. ANSI/IEEE Std 802.1D, 1998 Edition, pages 1–373, 1998. doi:10.1109/IEEESTD.1998.95619.
[4] Luca Bisti, Luciano Lenzini, Enzo Mingozzi, and Giovanni Stea. Estimating the worst-case delay in FIFO tandems using network calculus. In 3rd International ICST Conference on Performance Evaluation Methodologies and Tools, ValueTools ’08, Brussels, BEL, 2008. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering). doi:10.4108/ICST.VALUETOOLS2008.4388.
[5] Luca Bisti, Luciano Lenzini, Enzo Mingozzi, and Giovanni Stea. Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks. Real-Time Syst., 48(5):527–569, September 2012. doi:10.1007/s11241-012-9153-1.
[6] Steffen Bondorf, Paul Nikolaus, and Jens B. Schmitt. Quality and cost of deterministic network calculus: Design and evaluation of an accurate and fast analysis. In Bruce E. Hajek, Sewoong Oh, Augustin Chaintreau, Leana Golubchik, and Zhi-Li Zhang, editors, Proceedings of the 2017 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, Urbana-Champaign, IL, USA, June 05 - 09, 2017, page 65. ACM, 2017. doi:10.1145/3078505.3078594.
[7] Steffen Bondorf and Jens B. Schmitt. The DiscoDNC v2 – a comprehensive tool for deterministic network calculus. In Proc. of the International Conference on Performance Evaluation Methodologies and Tools, ValueTools ’14, pages 44–49, December 2014. URL: https://dl.acm.org/citation.cfm?id=2747659.
[8] Anne Bouillard. Trade-off between accuracy and tractability of network calculus in FIFO networks. Performance Evaluation, 153:102250, 2022. doi:10.1016/j.peva.2021.102250.
[9] Anne Bouillard and Éric Thierry. An Algorithmic Toolbox for Network Calculus. Discrete Event Dynamic Systems, 18, March 2008. Publisher: Springer Science and Business Media LLC. doi:10.1007/s10626-007-0028-x.
[10] Marc Boyer and Christian Fraboul. Tightening end to end delay upper bound for afdx network calculus with rate latency FIFO servers using network calculus. In 2008 IEEE International Workshop on Factory Communication Systems, pages 11–20, 2008. doi:10.1109/WFCS.2008.4638728.
[11] Bruno Cattelan and Steffen Bondorf. Iterative design space exploration for networks requiring performance guarantees. In 2017 IEEE/AIAA 36th Digital Avionics Systems Conference (DASC), pages 1–10, 2017. doi:10.1109/DASC.2017.8102106.
[12] Cheng-Shang Chang. Performance Guarantees in Communication Networks. Telecommunication Networks and Computer Systems. Springer London, 2000. ISBN: 978-1-4471-1147-4 978-1-4471-0459-9. Accessed Feb. 25, 2026. doi:10.1007/978-1-4471-0459-9.
[13] H. Charara, J.-L. Scharbarg, J. Ermont, and C. Fraboul. Methods for bounding end-to-end delays on an afdx network. In 18th Euromicro Conference on Real-Time Systems (ECRTS’06), pages 10 pp.–202, 2006. doi:10.1109/ECRTS.2006.15.
[14] A. FINZI, A. MIFDAOUI, F. FRANCES, and E. LOCHIN. Network calculus-based timing analysis of afdx networks with strict priority and tsn/bls shapers. In 2018 IEEE 13th International Symposium on Industrial Embedded Systems (SIES), pages 1–10, 2018. doi:10.1109/SIES.2018.8442080.
[15] Fabien Geyer and Steffen Bondorf. Differentiable programming & network calculus: Configuration synthesis under delay constraints, 2023. doi:10.48550/arXiv.2307.14280.
[16] C.J. Glass and L.M. Ni. The turn model for adaptive routing. In Proceedings the 19th Annual International Symposium on Computer Architecture, pages 278–287, 1992. doi:10.1109/ISCA.1992.753324.
[17] Boudewihn R. Haverkort. Performance of Computer Communication Systems: A Model-Based Approach. Wiley, 2001. ISBN: 978-0-471-97228-0 978-0-470-84192-1. Accessed: Feb 25. 2026 [Online]. doi:10.1002/0470841923.
[18] Lukas Herll and Steffen Bondorf. Non-linear programming for the network calculus analysis of FIFO feedforward networks. In Proceedings of the 16th ACM/SPEC International Conference on Performance Engineering, ICPE ’25, pages 266–279, New York, NY, USA, 2025. Association for Computing Machinery. doi:10.1145/3676151.3719360.
[19] Jörg Liebeherr. Duality of the max-plus and min-plus network calculus. Found. Trends Netw., 11(3-4):139–282, 2017. doi:10.1561/1300000059.
[20] Lisa Maile, Kai-Steffen Hielscher, and Reinhard German. Network calculus results for tsn: An introduction. In 2020 Information Communication Technologies Conference (ICTC), pages 131–140, 2020. doi:10.1109/ICTC49638.2020.9123308.
[21] Radia Perlman. An algorithm for distributed computation of a spanning tree in an extended lan. Computer Communication Review - CCR, 15:44–53, September 1985. doi:10.1145/318951.319004.
[22] Wlad Pesotsky. NCorg DNC v3 Evaluations. Software (visited on 2026-06-19). URL: https://github.com/wlad-p/ECRTS2026-NCorgDNC-v3, doi:10.4230/artifacts.26766.
[23] Wlad Pesotsky and Steffen Bondorf. NetworkCalculus.org Deterministic Network Calculator (NCorg DNC). Software, version 3.0.0. (visited on 2026-06-19). URL: https://dnc.networkcalculus.org, doi:10.4230/artifacts.26764.
[24] Steffen Bondorf Philipp Schon. Towards unified tool support for real-time calculus and deterministic network calculus, 2017. URL: https://api.semanticscholar.org/CorpusID:3818901.
[25] Alexander Scheffler and Steffen Bondorf. Network calculus for bounding delays in feedforward networks of FIFO queueing systems. In Proc. of the 18th International Conference on Quantitative Evaluation of Systems, QEST ’21, pages 149–167, August 2021. doi:10.1007/978-3-030-85172-9_8.
[26] Alexander Scheffler, Jens B. Schmitt, and Steffen Bondorf. Searching for upper delay bounds in FIFO multiplexing feedforward networks. In the 30th International Conference on Real-Time Networks and Systems (RTNS 2022), June 2022.
[27] J. B. Schmitt, F. A. Zdarsky, and M. Fidler. Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch.. In IEEE INFOCOM 2008 - The 27th Conference on Computer Communications, pages 1669–1677, 2008. doi:10.1109/INFOCOM.2008.228.
[28] Jens B. Schmitt, Frank A. Zdarsky, and Ivan Martinovic. Improving performance bounds in feed-forward networks by paying multiplexing only once. In 14th GI/ITG Conference - Measurement, Modelling and Evalutation of Computer and Communication Systems, pages 1–15, 2008.
[29] M.D. Schroeder, A.D. Birrell, M. Burrows, H. Murray, R.M. Needham, T.L. Rodeheffer, E.H. Satterthwaite, and C.P. Thacker. Autonet: a high-speed, self-configuring local area network using point-to-point links. IEEE Journal on Selected Areas in Communications, 9(8):1318–1335, 1991. doi:10.1109/49.105178.
[30] D. Starobinski, M. Karpovsky, and L.A. Zakrevski. Application of network calculus to general topologies using turn-prohibition. IEEE/ACM Transactions on Networking, 11(3):411–421, 2003. doi:10.1109/TNET.2003.813040.
[31] Ludovic Thomas. Analysis of the side-effects on latency bounds of combinations of scheduling, redundancy and synchronization mechanisms in time-sensitive networks [ph.d. thesis]. l’Institut Supérieur de l’Aéronautique et de l’Espace, 2022. URL: https://theses.fr/2022ESAE0041.
[32] Andrea Trasacco, Raffaele Zippo, and Giovanni Stea. Nancy.expressions: Towards a computer algebra system for deterministic network calculus. In Marco Gribaudo, Mauro Iacono, and Sahra Sedigh Sarvestani, editors, Performance Evaluation Methodologies and Tools, pages 425–436, Cham, 2026. Springer Nature Switzerland.
[33] Chun-Tso Tsai, Seyed Mohammadhossein Tabatabaee, Stéphan Plassart, and Jean-Yves Le Boudec. Saihu: A common interface of worst-case delay analysis tools for time-sensitive networks. SoftwareX, 27:101882, 2024. doi:10.1016/j.softx.2024.101882.
[34] E. Wandler and L. Thiele. Real-time calculus (RTC) toolbox. Accessed: Feb 20. 2026 [Online]. URL: http://www.mpa.ethz.ch/Rtctoolbox.
[35] Luxi Zhao, Paul Pop, and Silviu S. Craciunas. Worst-case latency analysis for ieee 802.1qbv time sensitive networks using network calculus. IEEE Access, 6:41803–41815, 2018. doi:10.1109/ACCESS.2018.2858767.
[36] Boyang Zhou, Isaac Howenstine, Siraphob Limprapaipong, and Liang Cheng. A survey on network calculus tools for network infrastructure in real-time systems. IEEE Access, 8:223588–223605, 2020. doi:10.1109/ACCESS.2020.3043600.
[37] Timothy Zhu, Alexey Tumanov, Michael A. Kozuch, Mor Harchol-Balter, and Gregory R. Ganger. Prioritymeister: Tail latency qos for shared networked storage. In Proceedings of the ACM Symposium on Cloud Computing, SOCC ’14, pages 1–14, New York, NY, USA, 2014. Association for Computing Machinery. doi:10.1145/2670979.2671008.
[38] Raffaele Zippo, Paul Nikolaus, and Giovanni Stea. Isospeed: Improving (min,+) Convolution by Exploiting (min,+)/(max,+) Isomorphism. In Alessandro V. Papadopoulos, editor, 35th Euromicro Conference on Real-Time Systems (ECRTS 2023), volume 262 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:24, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ECRTS.2023.12.
[39] Raffaele Zippo and Giovanni Stea. Nancy: An efficient parallel network calculus library. SoftwareX, 19:101178, 2022. doi:10.1016/j.softx.2022.101178.

Appendix A Appendix

Algorithm 1 TurnProhibition by Starobinski et al. [30].

[bib.bib1] [1] IEEE standard for Ethernet, amendment 10: Media access control parameters, physical layers, and management parameters for 200 Gb/s and 400 Gb/s operation.

[bib.bib2] [2] IEEE standard for Ethernet, amendment 7: Media access control parameters, physical layers, and management parameters for 2.5 Gb/s and 5 Gb/s operation, types 2.5 GBASE-T and 5 GBASE-T.

[bib.bib3] [3] IEEE standard for local area network mac (media access control) bridges. ANSI/IEEE Std 802.1D, 1998 Edition, pages 1–373, 1998. doi:10.1109/IEEESTD.1998.95619.

[bib.bib4] [4] Luca Bisti, Luciano Lenzini, Enzo Mingozzi, and Giovanni Stea. Estimating the worst-case delay in FIFO tandems using network calculus. In 3rd International ICST Conference on Performance Evaluation Methodologies and Tools, ValueTools ’08, Brussels, BEL, 2008. ICST (Institute for Computer Sciences, Social-Informatics and Telecommunications Engineering). doi:10.4108/ICST.VALUETOOLS2008.4388.

[bib.bib5] [5] Luca Bisti, Luciano Lenzini, Enzo Mingozzi, and Giovanni Stea. Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks. Real-Time Syst., 48(5):527–569, September 2012. doi:10.1007/s11241-012-9153-1.

[bib.bib6] [6] Steffen Bondorf, Paul Nikolaus, and Jens B. Schmitt. Quality and cost of deterministic network calculus: Design and evaluation of an accurate and fast analysis. In Bruce E. Hajek, Sewoong Oh, Augustin Chaintreau, Leana Golubchik, and Zhi-Li Zhang, editors, Proceedings of the 2017 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems, Urbana-Champaign, IL, USA, June 05 - 09, 2017, page 65. ACM, 2017. doi:10.1145/3078505.3078594.

[bib.bib7] [7] Steffen Bondorf and Jens B. Schmitt. The DiscoDNC v2 – a comprehensive tool for deterministic network calculus. In Proc. of the International Conference on Performance Evaluation Methodologies and Tools, ValueTools ’14, pages 44–49, December 2014. URL: https://dl.acm.org/citation.cfm?id=2747659.

[bib.bib8] [8] Anne Bouillard. Trade-off between accuracy and tractability of network calculus in FIFO networks. Performance Evaluation, 153:102250, 2022. doi:10.1016/j.peva.2021.102250.

[bib.bib9] [9] Anne Bouillard and Éric Thierry. An Algorithmic Toolbox for Network Calculus. Discrete Event Dynamic Systems, 18, March 2008. Publisher: Springer Science and Business Media LLC. doi:10.1007/s10626-007-0028-x.

[bib.bib10] [10] Marc Boyer and Christian Fraboul. Tightening end to end delay upper bound for afdx network calculus with rate latency FIFO servers using network calculus. In 2008 IEEE International Workshop on Factory Communication Systems, pages 11–20, 2008. doi:10.1109/WFCS.2008.4638728.

[bib.bib11] [11] Bruno Cattelan and Steffen Bondorf. Iterative design space exploration for networks requiring performance guarantees. In 2017 IEEE/AIAA 36th Digital Avionics Systems Conference (DASC), pages 1–10, 2017. doi:10.1109/DASC.2017.8102106.

[bib.bib12] [12] Cheng-Shang Chang. Performance Guarantees in Communication Networks. Telecommunication Networks and Computer Systems. Springer London, 2000. ISBN: 978-1-4471-1147-4 978-1-4471-0459-9. Accessed Feb. 25, 2026. doi:10.1007/978-1-4471-0459-9.

[bib.bib13] [13] H. Charara, J.-L. Scharbarg, J. Ermont, and C. Fraboul. Methods for bounding end-to-end delays on an afdx network. In 18th Euromicro Conference on Real-Time Systems (ECRTS’06), pages 10 pp.–202, 2006. doi:10.1109/ECRTS.2006.15.

[bib.bib14] [14] A. FINZI, A. MIFDAOUI, F. FRANCES, and E. LOCHIN. Network calculus-based timing analysis of afdx networks with strict priority and tsn/bls shapers. In 2018 IEEE 13th International Symposium on Industrial Embedded Systems (SIES), pages 1–10, 2018. doi:10.1109/SIES.2018.8442080.

[bib.bib15] [15] Fabien Geyer and Steffen Bondorf. Differentiable programming & network calculus: Configuration synthesis under delay constraints, 2023. doi:10.48550/arXiv.2307.14280.

[bib.bib16] [16] C.J. Glass and L.M. Ni. The turn model for adaptive routing. In Proceedings the 19th Annual International Symposium on Computer Architecture, pages 278–287, 1992. doi:10.1109/ISCA.1992.753324.

[bib.bib17] [17] Boudewihn R. Haverkort. Performance of Computer Communication Systems: A Model-Based Approach. Wiley, 2001. ISBN: 978-0-471-97228-0 978-0-470-84192-1. Accessed: Feb 25. 2026 [Online]. doi:10.1002/0470841923.

[bib.bib18] [18] Lukas Herll and Steffen Bondorf. Non-linear programming for the network calculus analysis of FIFO feedforward networks. In Proceedings of the 16th ACM/SPEC International Conference on Performance Engineering, ICPE ’25, pages 266–279, New York, NY, USA, 2025. Association for Computing Machinery. doi:10.1145/3676151.3719360.

[bib.bib19] [19] Jörg Liebeherr. Duality of the max-plus and min-plus network calculus. Found. Trends Netw., 11(3-4):139–282, 2017. doi:10.1561/1300000059.

[bib.bib20] [20] Lisa Maile, Kai-Steffen Hielscher, and Reinhard German. Network calculus results for tsn: An introduction. In 2020 Information Communication Technologies Conference (ICTC), pages 131–140, 2020. doi:10.1109/ICTC49638.2020.9123308.

[bib.bib21] [21] Radia Perlman. An algorithm for distributed computation of a spanning tree in an extended lan. Computer Communication Review - CCR, 15:44–53, September 1985. doi:10.1145/318951.319004.

[bib.bib22] [22] Wlad Pesotsky. NCorg DNC v3 Evaluations. Software (visited on 2026-06-19). URL: https://github.com/wlad-p/ECRTS2026-NCorgDNC-v3, doi:10.4230/artifacts.26766.

[bib.bib23] [23] Wlad Pesotsky and Steffen Bondorf. NetworkCalculus.org Deterministic Network Calculator (NCorg DNC). Software, version 3.0.0. (visited on 2026-06-19). URL: https://dnc.networkcalculus.org, doi:10.4230/artifacts.26764.

[bib.bib24] [24] Steffen Bondorf Philipp Schon. Towards unified tool support for real-time calculus and deterministic network calculus, 2017. URL: https://api.semanticscholar.org/CorpusID:3818901.

[bib.bib25] [25] Alexander Scheffler and Steffen Bondorf. Network calculus for bounding delays in feedforward networks of FIFO queueing systems. In Proc. of the 18th International Conference on Quantitative Evaluation of Systems, QEST ’21, pages 149–167, August 2021. doi:10.1007/978-3-030-85172-9_8.

[bib.bib26] [26] Alexander Scheffler, Jens B. Schmitt, and Steffen Bondorf. Searching for upper delay bounds in FIFO multiplexing feedforward networks. In the 30th International Conference on Real-Time Networks and Systems (RTNS 2022), June 2022.

[bib.bib27] [27] J. B. Schmitt, F. A. Zdarsky, and M. Fidler. Delay bounds under arbitrary multiplexing: When network calculus leaves you in the lurch.. In IEEE INFOCOM 2008 - The 27th Conference on Computer Communications, pages 1669–1677, 2008. doi:10.1109/INFOCOM.2008.228.

[bib.bib28] [28] Jens B. Schmitt, Frank A. Zdarsky, and Ivan Martinovic. Improving performance bounds in feed-forward networks by paying multiplexing only once. In 14th GI/ITG Conference - Measurement, Modelling and Evalutation of Computer and Communication Systems, pages 1–15, 2008.

[bib.bib29] [29] M.D. Schroeder, A.D. Birrell, M. Burrows, H. Murray, R.M. Needham, T.L. Rodeheffer, E.H. Satterthwaite, and C.P. Thacker. Autonet: a high-speed, self-configuring local area network using point-to-point links. IEEE Journal on Selected Areas in Communications, 9(8):1318–1335, 1991. doi:10.1109/49.105178.

[bib.bib30] [30] D. Starobinski, M. Karpovsky, and L.A. Zakrevski. Application of network calculus to general topologies using turn-prohibition. IEEE/ACM Transactions on Networking, 11(3):411–421, 2003. doi:10.1109/TNET.2003.813040.

[bib.bib31] [31] Ludovic Thomas. Analysis of the side-effects on latency bounds of combinations of scheduling, redundancy and synchronization mechanisms in time-sensitive networks [ph.d. thesis]. l’Institut Supérieur de l’Aéronautique et de l’Espace, 2022. URL: https://theses.fr/2022ESAE0041.

[bib.bib32] [32] Andrea Trasacco, Raffaele Zippo, and Giovanni Stea. Nancy.expressions: Towards a computer algebra system for deterministic network calculus. In Marco Gribaudo, Mauro Iacono, and Sahra Sedigh Sarvestani, editors, Performance Evaluation Methodologies and Tools, pages 425–436, Cham, 2026. Springer Nature Switzerland.

[bib.bib33] [33] Chun-Tso Tsai, Seyed Mohammadhossein Tabatabaee, Stéphan Plassart, and Jean-Yves Le Boudec. Saihu: A common interface of worst-case delay analysis tools for time-sensitive networks. SoftwareX, 27:101882, 2024. doi:10.1016/j.softx.2024.101882.

[bib.bib34] [34] E. Wandler and L. Thiele. Real-time calculus (RTC) toolbox. Accessed: Feb 20. 2026 [Online]. URL: http://www.mpa.ethz.ch/Rtctoolbox.

[bib.bib35] [35] Luxi Zhao, Paul Pop, and Silviu S. Craciunas. Worst-case latency analysis for ieee 802.1qbv time sensitive networks using network calculus. IEEE Access, 6:41803–41815, 2018. doi:10.1109/ACCESS.2018.2858767.

[bib.bib36] [36] Boyang Zhou, Isaac Howenstine, Siraphob Limprapaipong, and Liang Cheng. A survey on network calculus tools for network infrastructure in real-time systems. IEEE Access, 8:223588–223605, 2020. doi:10.1109/ACCESS.2020.3043600.

[bib.bib37] [37] Timothy Zhu, Alexey Tumanov, Michael A. Kozuch, Mor Harchol-Balter, and Gregory R. Ganger. Prioritymeister: Tail latency qos for shared networked storage. In Proceedings of the ACM Symposium on Cloud Computing, SOCC ’14, pages 1–14, New York, NY, USA, 2014. Association for Computing Machinery. doi:10.1145/2670979.2671008.

[bib.bib38] [38] Raffaele Zippo, Paul Nikolaus, and Giovanni Stea. Isospeed: Improving (min,+) Convolution by Exploiting (min,+)/(max,+) Isomorphism. In Alessandro V. Papadopoulos, editor, 35th Euromicro Conference on Real-Time Systems (ECRTS 2023), volume 262 of Leibniz International Proceedings in Informatics (LIPIcs), pages 12:1–12:24, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ECRTS.2023.12.

[bib.bib39] [39] Raffaele Zippo and Giovanni Stea. Nancy: An efficient parallel network calculus library. SoftwareX, 19:101178, 2022. doi:10.1016/j.softx.2022.101178.