Computation of a (min,+) multi-dimensional convolution for end-to-end performance analyzes
Anne Bouillard, Laurent Jouhet, Éric Thierry · HAL (Le Centre pour la Communication Scientifique Directe) · 2008
We investigate how to compute a (min,+) multi-dimensional convolution with application to the worst-case performance analyzes in "Pay Multiplexing Only Once" scenarios. In such scenarios, a flow encounters some cross-traffic along its path and each cross-traffic flow interfers over a connected subpath. When there is no cross-traffic, the analyzes boils down to classical (min,+) convolutions. We provide three proofs to a well-known lemma describing how to compute the convolution of piecewise affine convex functions.