Optimization of the Min-plus Convolution Computation under Network Calculus Constraints
Key: PKSS04-1
Author: Krishna Pandit, Claus Kirchner, Jens Schmitt, Ralf Steinmetz
Date: June 2004
Kind: @techreport
Abstract: Network Calculus is a system theory for deterministic queueing systems. The min-plus convolution is an operation that is used for computations in Network Calculus. But until now there are few results on computing this convolution efficiently. Being able to do this is of great importance in order to make the application of Network Calculus more widespread. Therefore, this issue is targeted in this report. We give a brief overview over the basics of Network Calculus, introducing some basic operations in the min-plus algebra. Then transforms used to compute the classical convolution in the usual algebra are reviewed and basic results are listed. In the following we attempt to derive similar results for the min-plus convolution. We make use of the Fenchel transform, a tool used in convex analysis. Finally, we make use of the property, that in Network Calculus one usually deals with piecewise linear functions. For convex functions good results exist. Since there are very few results in the nonconvex case, we first analyse these by a brute force method, before pointing out the general equation for a certain type of functions, which are often encountered in Network Calculus.
View Full paper (PDF) | Download Full paper (PDF)

The documents distributed by this server have been provided by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a non-commercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, not withstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.