Abstract
Network calculus offers powerful tools to analyze the performances in communication networks, in particular to obtain deterministic bounds. This theory is based on a strong mathematical ground, notably by the use of (min,+) algebra. However, the algorithmic aspects of this theory have not been much addressed yet. This paper is an attempt to provide some efficient algorithms implementing network calculus operations for some classical functions. Some functions which are often used are the piecewise affine functions which ultimately have a constant growth. As a first step towards algorithmic design, we present a class containing these functions and closed under the main network calculus operations (min, max, +, −, convolution, subadditive closure, deconvolution): the piecewise affine functions which are ultimately pseudo-periodic. They can be finitely described, which enables us to propose some algorithms for each of the network calculus operations. We finally analyze their computational complexity.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Agarwal PK, Sharir M (1995a) Davenport–Schinzel sequences and their geometric applications. Cambridge Univ. Press
Agarwal PK, Sharir M (1995b) Davenport–Schinzel sequences and their geometric applications, Technical report DUKE-TR-1995-21. Department of Computer Science, Duke University
Attalah MJ (1985) Some dynamic computational geometry problems. Comput Math Appl 11: 1171–1181
Baccelli F, Cohen G, Olsder GJ, Quadrat J-P (1992) Synchronization and linearity. Wiley, Download from http://www.maxplus.org
Boissonat JD, Yvinec M (1998) Algorithmic geometry. Cambridge Univ. Press
Bouillard A (2005) Optimisation et analyse probabiliste de systèmes à événements discrets. PhD thesis, École Normale Supérieure de Lyon (in french)
Bouillard A, Thierry E (2007a) An algorithmic toolbox for network calculus, Technical report 6094. IRISA
Bouillard A, Thierry, E (2007b) Some examples and counterexamples for ( min, + ) filtering operations, Technical report 6095. IRISA
Chang CS (1999) Deterministic traffic specification via projections under the min-plus algebra. In: Proceedings of INFOCOM’99, pp 43–50
Chang CS (2000) Performance guarantees in communication networks. TNCS, Springer
COINC Project, INRIA (2006) COINC—computational issues in network calculus. ARC INRIA Project. http://perso.bretagne.ens-cachan.fr/~bouillar/coinc
Corduneanu C, Bohr H (1961) Almost periodic functions. Wiley
Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms. MIT Press
Cottenceau B, Gruet B, Hardouin L, Lhommeau M (2007) Modèles et systèmes dynamiques, LISA, University of Angers, France. http://www.istia.univ-angers.fr/~hardouin/outils.html
CyNC (2007) A tool for performance analysis of complex real time systems. http://www.control.auc.dk/~henrik/CyNC
DISCO (2006) The DISCO network calculator. http://disco.informatik.uni-kl.de/content/Downloads, last modified: 11-02-2006
Fidler M, Recker S (2006) Conjugate network calculus: a dual approach applying the legendre transform. Elsevier Comput Netw J 50(8):1026–1039
Gaubert S (2007) MaxPlus project, INRIA, Rocquencourt, France. http://amadeus.inria.fr/gaubert/gaubert.html
Gaubert S (1992) Théorie Linéaire des Systèmes dans les Dioïdes. PhD thesis, École des mines de Paris. (in french)
Hershberger J (1989) Finding the upper envelope of n line segments in \(\mathcal{O}(n \log n)\) time. Inf Process Lett 33:169–174
Klazar M (1999) On the maximum lengths of Davenport–Schinzel sequences. In: Contemporary trends in discrete mathematics, AMS, pp 169–178
Le Boudec J-Y, Thiran P (2001) Network calculus: a theory of deterministic queuing systems for the internet, LNCS 2050. Springer-Verlag
Nielsen F, Yvinec M (1998) An output-sensitive convex hull algorithm for planar objects. Int J Comput Geom Appl 8(1):39–66
Oppenheim AV, Willsky AS, Nawab SH (1997) Signals and systems. Prentice-Hall
Pandit K (2006) Quality of service performance analysis based on network calculus. PhD thesis, Technische Universität Darmstadt
Pandit K, Kirchner C, Schmitt J, Steinmetz, R (2004a) Optimization of the min-plus convolution computation under network calculus constraints, Technical report TR-KOM-2004-04. Technische Universität Darmstadt
Pandit K, Schmitt J, Kirchner C, Steinmetz R (2004b) Optimal allocation of service curves by exploiting properties of the min-plus convolution, Technical report TR-KOM-2004-08. Technische Universität Darmstadt
Pandit K, Schmitt J, Kircher C, Steinmetz R (2006) A transform for network calculus and its application to multimedia networking. In: SPIE conference on multimedia computing and networking (MMCN’06)
Ramirez-Alfonsin JL (2005) The diophantine frobenius problem. Oxford Univ. Press
Rockfellar RT (1996) Convex analysis. Princeton Univ. Press
Schmitt JB, Zdarsky FA (2006) The disco network calculator: a toolbox for worst case analysis. In Proceedings of valuetools’06, ACM Press, p 8
Schmitt JB, Zdarsky FA, Martinovic I (2006) Performance bounds in feed-forward networks under blind multiplexing, Technical Report 349/06. University of Kaiserslautern, Germany
Schioler H, Nielsen JD, Larsen KG, Jessen JJ (2005) CyNC - a method for real time analysis of systems with cyclic data flows. In: Proceedings of 13th RTS conference on embedded systems ’05
Sylvester JJ (1884) “question 7382”. Mathematical questions from the educational times, 41:21
Wandeler E, Thiele L (2006) Real-time calculus (RTC) toolbox. http://www.mpa.ethz.ch/Rtctoolbox
Wandeler E (2006) Modular performance analysis and interface-based design for embedded real-time systems. PhD thesis, ETH Zurich, ETH Diss. No. 16819
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Bouillard, A., Thierry, É. An Algorithmic Toolbox for Network Calculus. Discrete Event Dyn Syst 18, 3–49 (2008). https://doi.org/10.1007/s10626-007-0028-x
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10626-007-0028-x