Algorithms and efficiency of Network calculus

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 offeredby 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 typesof service curves and the relation between them are clarified; a new operator of packet curves introduced, in order to describe the packetsizes 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 inthe 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