Exact Worst-case Delay for FIFO-multiplexing Tandems

This paper computes the actual worst-case end-to-end delay for a flow in a tandem of FIFO multiplexing service curve nodes, where flows are shaped by concave, piecewise linear arrival curves, and service curves are convex and piecewise linear. Previous works only computed bounds on the above quantity, which are not always tight. We show that the solution entails taking the maximum among the optimal solution of a number of Linear Programming problems. However, the number and size of LP problems grows exponentially with the tandem length. Furthermore, we present approximate solution schemes to find both upper and lower delay bounds on the worst-case delay. Both of them only require to solve just one LP problem, and they produce bounds which are generally more accurate than those found in the previous work. Finally, we elaborate on how the worst-case scenario should be constructed.