Calculating Accurate End-to-End Delay Bounds - You Better Know Your Cross-Traffic

Bounds on the end-to-end delay of data flows play a crucial role in different areas, ranging from certification of hard real-time communication capabilities to quality of experience assurance for end users. Deterministic Network Calculus (DNC) allows to derive worst-case delay bounds; for instance, DNC is applied by the avionics industry to formally verify aircraft networks against strict delay requirements. Calculating tight end-to-end delays, however, was proven to be NP-hard. As a result, analyses focus on deriving fairly accurate bounds with feasible effort. Previous work constantly improved on capturing flow scheduling and cross-traffic multiplexing effects on the analyzed flow's path. In contrast, we present an enhanced analysis of the cross-traffic itself to decrease the bound on its worst-case data arrivals that interfere with the analyzed flow. This improvement is beneficial for both of effects, scheduling and multiplexing. By replacing the currently used procedure to bound cross-traffic arrivals with our new method, we can improve network calculus accuracy considerably - we demonstrate improvements that reduce the worst-case delay bound by more than factor 6.