Should Network Calculus Relocate? An Assessment of Current Algebraic and Optimization-Based Analyses
Should Network Calculus Relocate? An Assessment of Current Algebraic and Optimization-Based Analyses
复制标题
网络演算应该迁移吗？
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
J. Schmitt
中科院分区：
文献类型：
--
作者：
Steffen Bondorf;J. Schmitt
网络演算（NC）提供了一个框架的最坏情况下分析的网络。它使流延迟和服务器积压的确定性界限。NC的不断发展导致了一系列不同的分析。事实上，它甚至导致了方法论的两个完全不同的分支。两者都从基于流到达和转发服务的边界函数的共同网络描述开始。接下来的任何事情，即，导致最坏情况性能界限的实际分析有很大不同。长期以来，只有代数NC，作为通信网络的系统理论而创建的形式主义。它逐渐成熟，最终似乎在界限的准确性上达到了极限。前馈网络中的问题，防止它达到严格的界限，克服了基于优化的分析。然而，这种方法被证明是NP难的，没有一个有效的分析算法。因此，它被建议限制在一个不太复杂的基于优化的分析。像代数NC分析，它推导出严格的界限，为某些网络和有效的界限不同的精度为其他网络。在本文中，我们调查这种权衡的后果，并确定了一个新的和关键的分析原则，使我们能够更全面地比较两个NC分支比简单的排名延迟界限。
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.