## 3 The Sensor Network Calculus
### Calculation of Performance Bounds  
After the arrival curves for network-internal traffic flows are computed, we can also compute performance bounds according to Theorem 3. For instance, the buffer requirements of sensor nodes \(B_{i}\), a performance metric of interest for the bottleneck nodes directly below the sink:  
\[B_{i}=v(\tilde{\alpha}_{i},\beta_{i})=\sup_{s\geq 0}\{\tilde{\alpha}_{i}(s)- \beta_{i}(s)\}, \tag{4}\]  
Similarly, the per-node delay bounds \(D_{i}\) are computed with the given arrival and service curves:  
\[D_{i}=h(\tilde{\alpha}_{i},\beta_{i})=\sup_{s\geq 0}\{\inf\{\tau\geq 0:\tilde{ \alpha}_{i}(s)\leq\beta_{i}(s+\tau)\}\}. \tag{5}\]  
These derivations constitute SensorNC's original node-by-node computation of performance bounds [4]. In order to compute a flow's end-to-end delay bound, the per-node delay bounds along its path are added up. This approach is known as the total flow analysis (TFA) of network calculus. It does not benefit from the pay bursts only once (PBOO) phenomenon. A more sophisticated approach is required to benefit from more advanced network calculus phenomena and thus derive more accurate end-to-end delay bounds. PBOO can be achieved by first computing the left-over service curve for every server on the flow of interest's path (application of Theorem 1). Then, these left-over service curves are concatenated with Theorem 4 before the delay bound is computed. This approach is known as the separated flow analysis (SFA) of network calculus and its application in SensorNC was proposed in [11] where the improvement over TFA is also given. The third phenomenon to tighten end-to-end delay bounds in network calculus is called pay multiplexing only once (PMOO). In case cross-traffic flows are multiplexed with the flow of interest on multiple consecutive nodes (as is common in sink trees), it prevents their burstiness from impacting the derivation multiple times. This is achieved by applying the concatenation theorem as early as possible, i.e., before the application of Theorem 1. We illustrate the impact of advances in the SensorNC analysis by an example. Consider the simple sink tree network depicted in Figure 3. Computing delay bounds proceeds as discussed above: TFA computes an additive end-to-end delay bound; SFA computes per-node left-over service curves; and PMOO concatenates before the left-over computation:  
\[D^{\text{TFA}} = h\left(\alpha_{1}+\alpha_{2},\beta_{1}\right)+h\left(\left( \alpha_{1}+\alpha_{2}\right)\oslash\beta_{1},\beta_{2}\right)\] \[D^{\text{SFA}} = h\left(\alpha_{1},\left[\beta_{1}\odot\alpha_{2}\right]\otimes \left[\beta_{2}\odot\left(\alpha_{2}\oslash\beta_{1}\right)\right]\right)\] \[D^{\text{PMOO}} = h\left(\alpha_{1},\left[\left(\beta_{1}\otimes\beta_{2}\right) \ominus\alpha_{2}\right]\right)\]  
Assume rate-latency service curves \(\beta_{1}=\beta_{2}=\beta_{3,0}\) and token-bucket arrival curves \(\alpha_{1}=\alpha_{2}=\gamma_{1,1}\). Then, we compute the following delay bounds: \(D^{\text{TFA}}=\frac{4}{3}\), \(D^{\text{SFA}}=\frac{3}{2}\), \(D^{\text{PMOO}}=1\). As expected, PMOO results in the most accurate bound. In our example, TFA outperforms SFA, yet only because it implicitly assumes FIFO multiplexing (when computing the horizontal deviation for the total flow aggregate at each node) instead of the more pessimistic arbitrary multiplexing assumption of SFA  
Figure 3: Simple example to illustrate bounding methods. and PMOO. Nevertheless, in larger sink tree networks, application of the SensorNC SFA usually outperforms the TFA [11]. More details about the PMOO analysis for general feed-forward networks, including its relation to other network calculus analyses, as well as an in-depth discussion, can be found in [14; 15]. In sink tree networks, a specialized version can make use of the network structure. Similar to Algorithm 1, perfect knowledge about the locations of aggregation of flows and the lack of demultiplexing due to their common sink are exploited in Algorithm 2. ```
1.