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: 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 (number of bits for example) send 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. formula_1 formula_2 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. formula_3 formula_4 formula_5 formula_6 In  general, the flows are not exactly known, and only some constraints on flows and servers are known (like the maximal number of packet sent on some period, the maximal size of packets, the minimal link bandwidth). 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 algebra. In filter theory and linear systems theory the convolution of two functions formula_7 and formula_8 is defined as formula_9 In min-plus algebra 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 formula_7 and formula_8 becomes formula_12 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 formula_13 e.g. as used in the definition of traffic envelopes. The vertical and horizontal deviations can be expressed in terms of min-plus operators. formula_14 formula_15 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 (or arrival curve) , if for all it holds that formula_16 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 (depending on  reservations in the network, or scheduling policy, etc.). 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 formula_17 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, formula_18, such that formula_19, if formula_20 is a backlog period, then formula_21. If a server offers a strict minimal service of curve , it also offers a simple minimal service of curve . 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: formula_22 formula_23 Moreover, the departure curve has envelope formula_24. Moreover, these bounds are "tight" i.e. given some , and , one may build an arrival and departure such that 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 (resp. second) server offers a simple minimal service formula_25 (resp. formula_26), then, the concatenation of both offers a simple minimal service formula_27. The proof does iterative application of the definition of service curves formula_28, formula_29 and some properties of convolution, isotonicity (formula_30), and associativity (formula_31). The interest of this result is that the end-to-end delay bound is not greater than the sum of local delays: formula_32. This result is known as "Pay burst only once" (PBOO). Tools. There are several tools based on network calculus. A comparison can be found in. Events. WoNeCa workshop 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. In 2018, International Workshop on Network Calculus and Applications (NetCal 2018) was held in Vienna, Austria as a part of the 30th International Teletraffic Congress (ITC 30).