Should Network Calculus Relocate? An Assessment of Current Algebraic and Optimization-Based Analyses

摘要

Network calculus (NC) offers a framework for worst-case analysis of queueing networks. It enables to derive deterministic bounds on flow delay and server backlog. The continuous evolution of NC led to a set of different analyses. In fact, it even resulted in two entirely different branches of the methodology. Both start with a common network description based on bounding functions on flow arrivals and forwarding service. Anything that follows, i.e., the actual analysis leading to a worst-case performance bound, vastly differs. For long, there was only the algebraic NC, the formalism created as a system theory for communication networks. It matured and eventually seemed to have reached its limits regarding the accuracy of bounds. The problems preventing it from attaining tight bounds in feed-forward networks were overcome with optimization-based analysis. However, this approach was proven NP-hard without an efficient analysis algorithm known for it. Therefore, it was proposed to confine to a less complex optimization-based analysis instead. Like algebraic NC analyses, it derives tight bounds for some networks and valid bounds with varying accuracy for other networks. In this paper, we investigate the consequences of this tradeoff and identify a new and crucial analysis principle that allows us to compare both NC branches more comprehensively than simply ranking delay bounds.