Worst-Case Delay Analysis of Time-Sensitive Networks with Network Calculus

Time-sensitive networks, as in the context of IEEE Time-Sensitive Networking (TSN) and IETF Deterministic Networking (DetNet), offer deterministic services with guaranteed bounded latency in order to support safety-critical applications. In this thesis, we focus on the analysis of time-sensitive networks to address an essential requirement, namely, worst-case delay. Finding the exact worst-case delays is an NP-hard problem that is generally not feasible; therefore, we are interested in bounds on the worst-case delays. To this end, a standard approach is network calculus. It abstracts the service offered by a node by means of a service curve. It then uses service-curve characterizations of the network nodes and arrival curves of flows at their sources and obtains end-to-end delay bounds; an arrival curve is a constraint on the amount of data a flow can send, and it is necessary to obtain finite delay bounds. First, service-curve characterizations, in some cases, were too simple or non-existent: Round-robin schedulers are widespread, particularly in request balancing in cloud infrastructures, in the Linux Virtual Server scheduling, and in network on chip, and they are known to have efficient implementations. Also, they can be applied to time-sensitive networks, however, they have not been fully analyzed in this context. Interleaved Weighted Round-Robin (IWRR) is a variant of the classic Weighted Round-Robin (WRR) with a smoother service; no prior literature has obtained delay bounds for IWRR. We find the best obtainable strict service curve for IWRR, and we show that delay bounds derived from it are tight for flows of packets of constant size. With IWRR and WRR, the allocated bandwidth to each flow depends on the packet sizes; Deficit Round-Robin (DRR) is a later variant that solves this and provides fair queuing with variable-length packets. We derive the best obtainable strict service curve for DRR, where delay bounds derived from it dramatically dominate all previous works. So far, we have not considered that DRR automatically allocates unused capacity to improve service for other queues. Hence, we obtain delay bounds that remain valid, even if some traffic classes misbehave, but might be overly pessimistic in cases where interfering traffic is limited and behaves as expected. For such cases, we find novel strict service curves for DRR and show that delay bounds derived from them significantly dominate all previous works. Following our work for DRR, others found similar results for WRR and IWRR. End-to-end delay bounds in a DRR network can be obtained using global network analysis with our DRR strict service curve. For the former, Polynomial-size Linear Programming (PLP) is known to provide better bounds and larger stability region compared to its existing alternatives, but it was never applied to DRR networks. However, this raises dependency loops in networks with cyclic dependencies: On the one hand, our DRR strict service curves rely on traffic characteristics inside the network, which comes as the output of PLP. On the other hand, PLP requires prior knowledge of the DRR service curves. Iterative methods can solve this. However, PLP itself requires making cuts, which imposes other levels of iteration. We propose, PLP-DRR, a generic method for combining all the iterations sequentially or in parallel. We provide the best-known, proven worst-case delay analysis of time-sensitive networks of generic topology with round-robin sc