Network Calculus (NC) is an algebraic theory that represents traffic and service guarantees as curves in a Cartesian plane, in order to compute performance guarantees for flows traversing a network. NC uses transformation operations, e.g., min-plus convolution of two curves, to model how the traffic profile changes with the traversal of network nodes. Such operations, while mathematically well-defined, can quickly become unmanageable to compute using simple pen and paper for any non-trivial case, hence the need for algorithmic descriptions. Previous work identified the class of piecewise affine functions which are ultimately pseudo-periodic (UPP) as being closed under the main NC operations and able to be described finitely. Algorithms that embody NC operations taking as operands UPP curves have been defined and proved correct, thus enabling software implementations of these operations. However, recent advancements in NC make use of operations, namely the lower pseudo-inverse, upper pseudo-inverse, and composition, that are well defined from an algebraic standpoint, but whose algorithmic aspects have not been addressed yet. In this paper, we introduce algorithms for the above operations when operands are UPP curves, thus extending the available algorithmic toolbox for NC. We discuss the algorithmic properties of these operations, providing formal proofs of correctness.
翻译:网络计算(NC) 是一种代数理论,它代表了交通和服务保障,作为卡尔提斯飞机的曲线,以计算流量跨网络的运行保证。 NC 使用变换操作,例如微增两个曲线的组合,以模型显示流量配置如何随着网络节点的穿行而变化。这种操作虽然在数学上定义得很清楚,但很快变得无法用简单的笔和纸来计算任何非三进制案例,从而需要算法描述。以前的工作确定成片断函数的类别,这些功能最终是伪周期(UPP),在主要 NC 操作下关闭,可以有限定性地描述。 将 NC 操作体现为操作操作的变形曲线已经定义并被证明正确, 从而使得这些操作的软件得以实施。 然而, NC 的最近进步利用了操作, 即低伪反、 高级伪反和构成, 并且从正反向角度的角度来定义, 其算算法的算法操作已经被我们引入了。