## 2 Background on Network Calculus
### Network Calculus Performance Analysis
Network calculus often computes results for one specific flow. In cases where this flow competes for a system's resources with other flows, a bound on its resource share needs to be derived. This left-over service curve can only be computed from a strict service curve. Theorem 1: (Left-over service curve) _Consider a system \(\mathcal{S}\) that offers a strict service curve \(\beta\). Let \(\mathcal{S}\) be crossed by two flows \(R_{1},R_{2}\) with arrival curves \(\alpha_{1}\) and \(\alpha_{2}\), respectively. Then, \(R_{1}\)'s worst-case residual service share under arbitrary multiplexing at system \(\mathcal{S}\), i.e., the left-over service curve for the flow of interest, is:_  
\[\beta^{l,\alpha}=\beta\ominus\alpha_{1}:=\sup_{0\leq u\leq d}\left\{\left( \beta-\alpha\right)\left(u\right)\right\}.\]  
As stated above, service curves bound the transformation of an input function \(R(t)\) to an output function \(R^{*}(t)\). Given an arrival curve for \(R(t)\), they can also be applied to compute an arrival curve for \(R^{*}(t)\), a so-called output arrival curve:  
Theorem 2: (Output arrival curve) _Assume a flow \(f\) has an arrival curve \(\alpha\), and consider \(f\) traversing the system \(\mathcal{S}\) offering a service curve \(\beta\). After being transformed by \(\mathcal{S}\), i.e., at the system's output, \(f\) is bounded by the arrival curve:_  
\[\alpha^{*}(d) = \left(\alpha\oslash\beta\right)(d).\] \[= \begin{cases}0&\text{if }d=0\\ \left(\alpha\oslash\beta\right)(d)&\text{otherwise}\end{cases} .\]  
Note that deconvolution is not closed in \(\mathcal{F}_{0}\) as \(\left(\alpha\oslash\beta\right)(0)\geq 0\). Therefore, we slightly augmented the operation such that its result is guaranteed to pass through the origin. Other performance bound computations are not affected by this adaptation. Theorem 3: (Performance bounds) _Consider a system \(\mathcal{S}\) that offers a service curve \(\beta\). Assume a flow \(f\) with arrival curve \(\alpha\) traverses the system. Then, we obtain the following performance bounds for \(f\):_  
\[\text{backlog:}\ \ \forall t\in\mathbb{R}^{+}:\ B\left(t\right)\leq \left(\alpha\oslash\beta\right)(0),\] \[\text{delay:}\ \ \forall t\in\mathbb{R}^{+}:\ D\left(t\right)\leq \inf\left\{d\geq 0\mid\ \left(\alpha\oslash\beta\right)(-d)\leq 0\right\}.\]  
Last, we present a central result of network calculus: the concatenation theorem. Concatenation allows one to logically transform a tandem of systems into a single system whose capabilities are bounded by a single service curve. Theorem 4: (Concatenation theorem for tandem systems) _Consider a flow that traverses a tandem of systems \(\mathcal{S}_{i}\), \(i=1,\ldots,n\). Each \(\mathcal{S}_{i}\) offers a service curve \(\beta_{\mathcal{S}_{i}}\) to the flow. Then, the concatenation of the \(n\) systems offers a service curve \(\underset{i=1}{\overset{n}{\otimes}}\beta_{\mathcal{S}_{i}}\) to the flow._A system-by-system analysis of delay and backlog bounds that applies Theorems 2 and 3 does not guarantee tight results. In contrast, the concatenation theorem facilitates tightness of bounds by deriving the tandem's end-to-end service curve for the flow crossing it. In particular, bounds scale linearly in the number of crossed systems. This phenomenon is known as pay bursts only once [6]. An overview of the network calculus notation is provided in Table 1.