Skip to Main content Skip to Navigation
Habilitation à diriger des recherches

Algorithms and efficiency of Network calculus

Anne Bouillard 1, 2, 3
2 DYOGENE - Dynamics of Geometric Networks
DI-ENS - Département d'informatique - ENS 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.
Complete list of metadata

Cited literature [104 references]  Display  Hide  Download
Contributor : Anne Bouillard Connect in order to contact the contributor
Submitted on : Tuesday, January 20, 2015 - 4:00:03 PM
Last modification on : Friday, January 21, 2022 - 3:16:17 AM
Long-term archiving on: : Tuesday, April 21, 2015 - 11:36:00 AM



  • 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⟩



Les métriques sont temporairement indisponibles