Alternative Approaches of Convolution within Network Calculus

Ulrich Klehmet^*, Rüdiger Berndt^*

Computer Networks and Communication Systems Friedrich-Alexander-Universit?t, Erlangen, Germany.

DOI: 10.4236/jamp.2014.211112                

Abstract

Network Calculus is a powerful mathematical theory for the performance evaluation of communication systems; among others it allows to determine worst-case performance measures. This is why it is often used to appoint Quality of Service guarantees in packet-switched systems like the internet. The main mathematical operation within this deterministic queuing theory is the min- plus convolution of two functions. For example the convolution of the arrival and service curve of a system which reflects the data’s departure. Considering Quality of Service measures and performance evaluation, the convolution operation plays a considerable important role, similar to classical system theory. Up to the present day, in many cases it is not practical and simple to perform this operation. In this article we describe approaches to simplify the min-plus convolution and, accordingly, facilitate the corresponding calculations.

Keywords

Network Calculus, Min-Plus Convolution, Algebraic Laws, Convex Analysis

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Le Boudec, J.-Y. and Thiran, P. (2001) Network Calculus. Springer Verlag LNCS 2050.
[2]	Cruz, R. (1991) A Calculus for Network Delay, Part I: Network Elements in Isolation. IEEE Transactions on Information Theory, 37, 114-131.
[3]	Cruz, R. (1991) A Calculus for Network Delay, Part Ii: Network Analysis. IEEE Transactions on In-formation Theory, 37, 132-141.
[4]	Parekh, A.K. and Gallager, R.G. (1993) A Generalized Processor Sharing Approach to Flow Control in Integrated Service Networks: The Single-Node Case. IEEE/ACM Transactions on Networking, 1, 344-357. http://dx.doi.org/10.1109/90.234856
[5]	Kerschbaum, S., Hielscher, K., Klehmet, U. and German, R. (2012) Network Calculus: Application to an Industrial Automation Network. In: MMB and DFT 2012 Workshop Proceedings (16th GI/ITG Conference), Kaiserslautern, March 2012.
[6]	Herpel, T., Hielscher, K., Klehmet, U. and German, R. (2009) Stochastic and Deterministic Performance Evaluation of Automotive CAN Communication. Computer Networks, 53, 1171-1185. http://dx.doi.org/10.1016/j.comnet.2009.02.008
[7]	Fidler, M. (2010) A Survey of Deterministic and Stochastic Service Curve Models in the Network Calculus. IEEE Communications Surveys & Tutorials, 12, 59-86.
[8]	Rockafellar, R.T. (1970) Convex Analysis. Princeton University Press.
[9]	Pandit, K., Schmitt, J., Kirchner, C. and Steinmetz, R. (2004) Optimal Allocation of Service Curves by Exploiting Properties of the Min-Plus Convolution. Technical Report.