Network Calculus for Bounding Delays in Feedforward Networks of FIFO Queueing Systems

Networks for safety-critical operation must guarantee deterministic bounds on the end-to-end delay of data transmission despite the usually many data flows that all share the available data forwarding resources. Queueing is inevitable and the queueing delay becomes the important impact factor for communication delays. Network Calculus can calculate verifiable delay bounds in networks of such queues and the tighter the bounds are, the less over-provisioning is required when they are used for the design of safety-critical networked systems. Tightening delay bounds is an important objective of Network Calculus research. In this paper, we focus on the improvement of the overall analysis algorithm bounding delays in feedforward networks. FIFO queueing is widespread in practice, yet, considering it to model the fraction any data flow gets of the forwarding resource turned out to be complex with Network Calculus. The currently only analysis with practically usable performance was developed for tandem topologies. On the other hand, there are sophisticated algorithms for the feedforward analysis without considering the FIFO property. Here, big gains in tightness were achieved by properly extending the algorithms for tandem topologies. We aim at bringing these gains to the FIFO analysis - and the FIFO analysis to feedforward networks. We provide a thorough integration of both - theoretically and with novel tool support. Our new analysis shows a considerable tightness improvement over the feedforward analysis without FIFO considerations as well as a straightforward extension of the FIFO analysis.