Algorithms and efficiency of Network calculus

Anne Bouillard 1, 2, 3
2 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique de l'École normale supérieure, ENS Paris - École normale supérieure - Paris, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR8548
Abstract : This document presents some results obtained in the field of network calculus, a theory based on the (min,plus) algebra and whose aim is to compute worst-case performance bounds in communication networks. This theory models flows circulating in a network and the service offered by the network elements by cumulative functions and those functions are abstracted by enveloped on which the computations are performed. Several aspects are addressed. A first part is devoted to the clarification and the improvements of the performance bounds computed using this theory: the different types of service curves and the relation between them are clarified; a new operator of packet curves introduced, in order to describe the packet sizes the same way as the flows; and we improve the way of computing worst-case performance bounds, that is classically based on the (min,plus) operators, by introducing linear programs that compute the exact worst-case performances in some cases and improve the bounds in the other cases. The second part presents some examples other application of the results first developed for networks calculus: algorithms of convolution of (min,plus) functions have received a lot of attention by the network calculus community in order to compute bounds efficiently. We show here an example of use for approximating the numerical solution of the Hamilton-Jacobi equation. Another example is to use the concept of arrival curve to supervise a flow. This is done with simple algorithm that can follow the evolution of the behavior of a flow.
Type de document :
Discrete Mathematics [cs.DM]. Ecole Normale Supérieure (Paris), 2014
Liste complète des métadonnées

Littérature citée [104 références]  Voir  Masquer  Télécharger
Contributeur : Anne Bouillard <>
Soumis le : mardi 20 janvier 2015 - 16:00:03
Dernière modification le : mercredi 21 mars 2018 - 18:57:46
Document(s) archivé(s) le : mardi 21 avril 2015 - 11:36:00



  • HAL Id : tel-01107384, version 1



Anne Bouillard. Algorithms and efficiency of Network calculus. Discrete Mathematics [cs.DM]. Ecole Normale Supérieure (Paris), 2014. 〈tel-01107384〉



Consultations de la notice


Téléchargements de fichiers