Numerical analysis of worst-case end-to-end delay bounds in FIFO tandem networks

This paper addresses the problem of computing end-to-end delay bounds for a traffic flow traversing a tandem of FIFO multiplexing network nodes using Network Calculus. Numerical solution methods are required, as closed-form delay bound expressions are unknown except for few specific cases. For the methodology called the Least Upper Delay Bound, the most accurate among those based on Network Calculus, exact and approximate solution algorithms are presented, and their accuracy and computation cost are discussed. The algorithms are inherently exponential, yet affordable for tandems of up to few tens of nodes, and amenable to online execution in cases of practical significance. This complexity is, however, required to compute accurate bounds. As the LUDB may actually be larger than the worst-case delay, we assess how close the former is to the latter by computing lower bounds on the worst-case delay and measuring the gap between the lower and upper bound.