Detailed Consideration of Graphical Calculation of Min-Plus Convolution in Deterministic Network Calculus

Andrzej Marek Borys


The convolution operation used in deterministic network calculus differs from its counterpart known from the classic systems theory. A reason for this lies in the fact that the former is defined in terms of the so-called min-plus algebra. Therefore, it is oft difficult to realize how it really works. In these cases, its graphical interpretation can be very helpful. This paper is devoted to a topic of construction of the min-plus convolution curve. This is done here in a systematic way to avoid arriving at non-transparent figures that are presented in publications. Contrary to this, our procedure is very transparent and removes shortcomings of constructions known in the literature. Some examples illustrate its usefulness.

Full Text:



R. Cruz, “A calculus for network delay, Part I: Network elements in isolation”, IEEE Transactions on Information Theory, vol. 37, pp. 114-131, 1991.

R. Cruz, “A calculus for network delay, Part II: Network analysis”, IEEE Transactions on Information Theory, vol. 37, pp. 132-141, 1991.

J.-Y. Le Boudec and P. Thiran, Network Calculus. A Theory of Deterministic Queuing Systems for the Internet. Berlin: Springer Verlag, 2004.

A. Borys, “Operacja splotu w rachunku sieciowym - interpretacja graficzna”, Przegląd Telekomunikacyjny i Wiadomości Telekomuni-kacyjne, vol. 8- 9, pp. 800-803, 2017 (in Polish).

F. M. Callier and Ch. A. Desoer, Linear System Theory. Berlin: Springer Verlag, 1991.

E. A. Lee and P. Varaiya, Structure and Interpretation of Signals and Systems. UC Berkeley:, 2011.

R. Agrawal, R. L. Cruz, C. M. Okino, and R. Rajan, “Performance bounds for flow control protocols”, IEEE/ACM Trans. Networking, vol. 7, pp. 310-323, 1999.

S. W. Smith, The Scientist and Engineer's Guide to Digital Signal Processing (Second Edition). San Diego: California Technical Publishing, 1999.

M. Fidler, “A survey of deterministic and stochastic service curve models in the network calculus”, IEEE Communications Surveys & Tutorials, vol. 12, pp. 59-86, 2010.

A. Van Bemten and W. Kellerer, Network Calculus: A Comprehensive Guide. Munich: Technical Report, Chair of Communication Networks, Technical University of Munich, 2016.


  • There are currently no refbacks.

International Journal of Electronics and Telecommunications
is a periodical of Electronics and Telecommunications Committee
of Polish Academy of Sciences

eISSN: 2300-1933