Tighness and optimisation issues in Network calculus


Dr. Anne Bouillard (École normale supérieure Paris, France)


Network calculus is a theory based on the (min,plus) algebra for computing deterministic performance guaranties in networks. In this talk, I will deal with two problems related to Network calculus. 1) the tighness issue: the algebraic framework enables to easily combine network elements, and the algorithmic cost of this is very low. But the bounds that are computed may be very high compared to the actual worst case performances. We show under some assumptions how to compute the worst-case delays using linear programming. We also show that the problem is NP-hard. 2) optimisation issue: We solve the following simple problem. Given one flow and one network, what is the path going to one source to one destination that guaranties the shortest end-to-end delay.


Dr. Anne Bouillard is an assistant professor at ENS Paris since September 2010, working in Francois Baccelli's group. Before that she was at ENS Cachan (since 2006). She also studied at ENS and obtained her PhD from ENS Lyon in 2005, followed by a postdoctoral stay at the National Tsing Hua University of Taiwan in 2006.