Improving (min,+) convolutions by heuristic operation reordering

—Deterministic Network Calculus (DNC) is a math ematical framework for the worst-case analysis of networked systems. In less-than-trivial cases, pen-and-paper computation of DNC expressions is not viable, and the support of a software library for the automated computation is instead required. In particular, the (min,+) convolution operation can be very time consuming, and several works have focused on optimizing its algorithms. Since the operation is commutative and associative, the convolution of multiple curves can be performed in several ways. In this paper, we compared the runtime performance of different permutations, observing up to an order of magnitude of difference between the worst and best permutations, which highlights an opportunity for optimization. We devised several heuristics based on runtime prediction, to reorder the operations and take advantage of this optimization, obtaining on average an improvement of 30% over the average of all permutations. In this paper, we describe the runtime prediction heuristic approach and its results, highlighting paths for future research.