End-to-End Worst-Case Analysis of Non-FIFO Systems

In this paper, delay bounds in data flow systems with non-FIFO service disciplines are explored. It is shown that conventional network calculus definitions of a service curve are not satisfying under the assumption of non-FIFO service. Either the definition is too strict to allow for a concatenation and consequent beneficial end-to-end analysis, or it is too loose and thus results in infinite delay bounds. Hence, a new definition is proposed and demonstrated to achieve both finite delay bounds and a concatenation of systems resulting in a favorable end-to-end analysis. In particular, the authors show that the celebrated pay bursts only once phenomenon is retained under non-FIFO service.