## 2 Background on Network Calculus
### Network Calculus Performance Analysis  
Network calculus operates on bounding functions for flow arrivals. These are derived from the above input functions; yet, they are not defined over the time \(t\) that passed until the observation of the flow. Instead, they are defined over the duration of an observation \(d\). These bounding functions are called arrival curves. (Arrival curve) Given a flow with input function \(R\), a function \(\alpha\in\mathcal{F}_{0}\) is an arrival curve for \(R\) iff:  
\[\forall\,0\leq d\leq t\,:\,R(t)-R(t-d)\leq\alpha(d)\]  
SensorNC often restricts the set of arrival curves to token-bucket-shaped traffic:  
\[\mathcal{F}_{TB}= \left\{\gamma_{r,b}\colon\mathbb{R}^{+}\to\mathbb{R}^{+}\,|\, \gamma_{r,b}\,(0)=0,\,\underset{d>0}{\forall}\gamma_{r,b}(d)=b+r\cdot d \right\}\subseteq\mathcal{F}_{0},\,r,b\geq 0.\]  
Curves of \(\mathcal{F}_{\text{TB}}\) can easily be applied to bound the typical behavior of wireless sensor nodes. Assume a node periodically measuring its environment to report data. The maximum size of a measurement translates to parameter \(b\) that bounds the flow's burstiness. The bound on the subsequent data reporting rate is \(r=\frac{b}{p}\) where \(p\) denotes the sensing period. Analyzing a network requires transformations of the bounding functions of (sensor) network calculus. Operations in \((\wedge,+)\)-algebra have been established; see [5; 6; 7], respectively. The most important operations of this \((\wedge,+)\)-algebraic framework over \(\mathcal{F}_{0}\) are presented in the following. (\(\wedge,+)\)-operations) The \((\wedge,+)\)-algebraic aggregation, convolution and deconvolution of two functions \(f,g\in\mathcal{F}_{0}\) are defined as:  
\[\text{aggregation:}\ \ (f+g)\,(d) =\ f\,(d)+g\,(d)\,,\] \[\text{convolution:}\ \ (f\otimes g)\,(d) =\,\underset{0\leq s\leq d}{\inf}\left\{f(d-s)+g(s)\right\},\] \[\text{deconvolution:}\ \ (f\oslash g)\,(d) =\,\underset{u\geq 0}{\sup}\ \left\{f(d+u)-g(u)\right\}.\]  
Note that deconvolution is not exactly dual to convolution [6]. Aggregation of flows that cross a common system requires aggregating their arrival curves. In SensorNC, the flow aggregate's arrival curve can be computed easily if each individual flow is constrained by a token-bucket arrival curve. (Arrival curve aggregation in SensorNC) For the aggregation of \(n\) arrival curves of \(\mathcal{F}_{\text{TB}}\), it holds that:  
\[\sum_{i=1}^{n}\gamma_{r_{i},b_{i}}=\gamma_{\sum_{i=1}^{n}r_{i},\sum_{i=1}^{n} b_{i}}.\]  
In addition to flows, network calculus also operates on functions bounding the service capabilities of a system \(\mathcal{S}\). These so-called service curves are defined over the duration of observation, as well. They bound the worst-case transformation of an input function to an output function. (Service curve) If the service provided by a system \(\mathcal{S}\) for a given input function \(R\) results in an output function \(R^{*}\), we say that \(\mathcal{S}\) offers a service curve \(\beta\) iff:  
\[R^{*}\geq R\otimes\beta.\]  
In SensorNC, service is often characterized by rate-latency functions from:  
\[\mathcal{F}_{RL}=\left\{\beta_{R,T}:\mathbb{R}^{+}\to\mathbb{R}^{+}\,|\,\beta _{R,T}\,(d)=\max\{0,R\cdot(d-T)\}\right\}\subseteq\,\mathcal{F}_{0},\,T\geq 0, \,R>0.\]Rate-latency functions \(\beta_{R,T}\in\mathcal{F}_{\text{RL}}\) can model TDMA channel access [8] and duty cycling [9] in wireless sensor networks. When data are queued to be forwarded and service capacity is available, many systems guarantee a greater amount of service than the one of Definition 4. Thus, they fulfil a stricter definition of service curves. These service curves allow for some computations that those from the general service curve model of Definition 4 do not. Definition 5: (Strict service curve) Let \(\beta\in\mathcal{F}_{0}\). System \(\mathcal{S}\) offers a strict service curve \(\beta\) to a flow if, during any backlogged period of duration \(d\), the output of the flow is at least equal to \(\beta(d)\).