Network calculus

Network calculus is "a set of mathematical results which give insights into man-made systems such as concurrent programs, digital circuits and communication networks." Network calculus gives a theoretical framework for analysing performance guarantees in computer networks. As traffic flows through a network it is subject to constraints imposed by the system components, for example:

data link capacity
traffic shapers
congestion control
background traffic

These constraints can be expressed and analysed with network calculus methods. Constraint curves can be combined using convolution under min-plus algebra. Network calculus can also be used to express traffic arrival and departure functions as well as service curves.
The calculus uses "alternate algebras... to transform complex non-linear network systems into analytically tractable linear systems."
Currently, there exists two branches in network calculus: one handling deterministic bounded, and one handling stochastic bounds.

System modelling

Modelling flow and server

In network calculus, a flow is modelled as cumulative functions, where represents the amount of data sent by the flow in the interval. Such functions are non-negative and non-decreasing. The time domain is often the set of non negative reals.
A server can be a link, a scheduler, a traffic shaper, or a whole network. It is simply modelled as a relation between some arrival cumulative curve and some departure cumulative curve. It is required that, to model the fact that the departure of some data can not occur before its arrival.

Modelling backlog and delay

Given some arrival and departure curve and, the backlog at any instant, denoted can be defined as the difference between and. The delay at, is defined as the minimal amount of time such that the departure function reached the arrival function. When considering the whole flows, the supremum of these values is used.
In general, the flows are not exactly known, and only some constraints on flows and servers are known. The aim of network calculus is to compute upper bounds on delay and backlog, based on these constraints. To do so, network calculus uses the min-plus algebra.

Min-plus Semiring

Network calculus makes an intensive use on the min-plus semiring.
In filter theory and linear systems theory the convolution of two functions and is defined as
In min-plus semiring the sum is replaced by the minimum respectively infimum operator and the product is replaced by the sum. So the min-plus convolution of two functions and becomes
e.g. see the definition of service curves. Convolution and min-plus convolution share many algebraic properties. In particular both are commutative and associative.
A so-called min-plus de-convolution operation is defined as
e.g. as used in the definition of traffic envelopes.
The vertical and horizontal deviations can be expressed in terms of min-plus operators.

Traffic envelopes

Cumulative curves are real behaviours, unknown at design time. What is known is some constraint. Network calculus uses the notion of traffic envelope, also known as arrival curves.
A cumulative function is said to conform to an envelope , if for all it holds that
Two equivalent definitions can be given
Thus, places an upper constraint on flow. Such function can be seen as an envelope that specifies an upper bound on the number of bits of flow seen in any interval of length starting at an arbitrary, cf. eq..

Service curves

In order to provide performance guarantees to traffic flows it is necessary to specify some minimal performance of the server. Service curves provide a means of expressing resource availability. Several kinds of service curves exists, like weakly strict, variable capacity node, etc. See
for an overview.

Minimal service

Let be an arrival flow, arriving at the ingress of a server, and be the flow departing at the egress.
The system is said to provide a simple minimal service curve to the pair, if for all it holds that

Strict minimal service

Let be an arrival flow, arriving at the ingress of a server, and be the flow departing at the egress.
A backlog period is an interval such that, on any , .
The system is said to provide a strict minimal service curve to the pair iff,, such that, if is a backlog period, then.
If a server offers a strict minimal service of curve, it also offers a simple minimal service of curve.

Notations

Depending on the authors, on the purpose of the paper, different notations or even names are used for the same notion.

Notions name	Notations	Comments
Cumulative curve		The first papers were using, but is used for Flow, and for Arrival.
Input/output pair of curves	,,	The input/output curve pair was initially denoted. The naming stands for Arrival and Departure. Then naming names input and output flows.
Envelope, Arrival curve		Authors using the term 'Envelope' also use, and conversely with 'Arrival curve' and.
Service curve		Authors in general use either both or both
Delay, Horizontal deviation		The term 'horizontal deviation' emphasizes on the mathematical definition, whereas 'delay' emphasizes on the semantics.
Backlog, vertical deviation		The term 'vertical deviation' emphasizes on the mathematical definition, whereas 'backlog' emphasizes on the semantics.
Convolution
Deconvolution

Basic results: Performance bounds and envelope propagation

From traffic envelope and service curves, some bounds on the delay and backlog, and an envelope on the departure flow can be computed.
Let be an arrival flow, arriving at the ingress of a server, and be the flow departing at the egress. If the flow as a traffic envelope, and the server provides a minimal service of curve, then the backlog and delay can be bounded:
Moreover, the departure curve has envelope.
Moreover, these bounds are tight i.e. given some, and, one may build an arrival and departure such that
= and =.

Concatenation / PBOO

Consider a sequence of two servers, when the output of the first one is the input of the second one. This sequence can be seen as a new server, built as the concatenation of the two other ones.
Then, if the first server offers a simple minimal service , then, the concatenation of both offers a simple minimal service.
The proof does iterative application of the definition of service curves, and some properties of convolution, isotonicity, and associativity .
The interest of this result is that the end-to-end delay bound is not greater than the sum of local delays:
This result is known as Pay burst only once.

Tools

There are several tools based on network calculus. A comparison can be found in.

Min-plus computation

There exist several tools and library devoted to the min-plus algebra.

The is an on-line interpreter.
is a C# library implementing min-plus and max-plus operations.
The MIN-plus ExpRession VErification is a Coq library used to check validity of min-plus operations.

All these tools and library are based on the algorithms presented in.

Network analysis tools

The is an academic Java implementation of the network calculus framework.
The is an academic Java/MATLAB implementation of the Real-Time calculus framework, a theory quasi equivalent to network calculus.
The tool is an academic MATLAB/Symulink toolbox, based on top of the . The tool was developed in 2004-2008 and it is currently used for teaching at Aalborg university.
The is an industrial tool devoted to timing analysis tool of switched Ethernet network, based on network calculus.
is a Python-based academic tool for dynamic flows in Time-Sensitive Networking. It includes offline optimization of the network, as well as online admission control for real-time flows.
The is an academic tool combining network calculus based analysis and optimization analysis.
The DelayLyzer is an industrial tool designed to compute bounds for Profinet networks.
is an academic tool devoted to FIFO networks.
is an academic tool devoted to blind & FIFO tandem networks.
is a network calculus tool in Python, published under BSD 3-Clause License. It considers rate-latency servers and token-bucket arrival curves. It handles any topology, including cyclic ones.
The Siemens Network Planner uses network calculus to help the design of a PROFINET network.
is a Python code, support of the PhD thesis of Ludovic Thomas
is a Python code that computes network calculus bounds with linear programming methods.
is a Python interface that integrates three worst-case network analysis tools: xTFA, DiscoDNC, and .
is an SMT-solver based tool to verify the performance properties of congestion control algorithms using a network-calculus-like model
is a group of tools developed for analysis and optimisation of AFDX network with FIFO, SPQ, DRR and WRR scheduling, written in C++, in support of the PhD thesis of Aakash SONI

Events

is a Workshop on Network Calculus. It is organized every two years to bring together researchers with an interest in the theory of network calculus as well as those who want to apply existing results to new applications. The workshop also serves to promote the network calculus theory to researchers with an interest in applied queueing models.

, was held in Trondheim, Norway as a part of the .
, hosted by EPFL, is scheduled on September 8 and 9th, 2022 in Lausanne, Switzerland. Call for presentation .
was held virtually due to the COVID-19 pandemic on October 9, 2020.
was organized in conjunction with the 19th International GI/ITG Conference on Measurement, Modelling and Evaluation of Computing Systems on February 28, 2018, in Erlangen, Germany.
was held in as a part of the MMB & DFT 2016 conference on April 6, 2016, in Müster, Germany.
was held within the MMB & DFT 2014 conference on March 19, 2014, in Bamberg, Germany.
was hosted by University of Kaiserslautern and was held as a part of MMB2012 on March 21, 2012, in Kaiserslautern, Germany.

In 2018, was held in Vienna, Austria as a part of the 30th .
In 2024, the was held from 1 April to 4 April in Dagstuhl, Germany.