Exact Worst-Case Delay in FIFO-Multiplexing Feed-Forward Networks
Exact Worst-Case Delay in FIFO-Multiplexing Feed-Forward Networks
复制标题
FIFO 复用前馈网络中精确的最坏情况延迟
DOI：
10.1109/tnet.2014.2332071
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
G. Stea
中科院分区：
文献类型：
--
作者：
Anne Bouillard;G. Stea
在本文中，我们计算了一个由先进先出(FIFO)复用服务曲线节点组成的前馈网络中的流的实际最坏情况的端到端延迟，其中流是由分段仿射凹到达曲线整形的，服务曲线是分段仿射凸形的。我们证明了最坏情况下的时延问题可以被描述为一个混合整数线性规划问题，其规模随着所涉及的节点数目的增加而指数增长。此外，我们还给出了求最坏情况下延迟的上下界的近似解决方案。这两种方法都只需要解决一个线性规划问题，并且产生界通常比以前的工作更准确，后者是在更具限制性的假设下计算的。
In this paper, we compute the actual worst-case end-to-end delay for a flow in a feed-forward network of first-in-first-out (FIFO)-multiplexing service curve nodes, where flows are shaped by piecewise-affine concave arrival curves, and service curves are piecewise affine and convex. We show that the worst-case delay problem can be formulated as a mixed integer linear programming problem, whose size grows exponentially with the number of nodes involved. Furthermore, we present approximate solution schemes to find upper and lower delay bounds on the worst-case delay. Both only require to solve just one linear programming problem and yield bounds that are generally more accurate than those found in the previous work, which are computed under more restrictive assumptions.