Date : Jan. 22, 2015, 2 p.m. - Room :Salle du conseil

Multicommodity flow problems in open queuing networks.

Prof. Mauricio CARDOSO DE SOUZA - UFMG Belo Horizonte

Possibilité de visio-conférence @IP : Nom du correspondant technique : Nicolas CHAMPEIL Tél correspondant technique : 04 73 40 50 15 / 06 78 34 55 26 Mail : Tél salle de visio : 04 73 40 50 47 Multicommodity flow problems subject to queuing effects appear frequently when dealing with the operation of communication or transportation networks. Commodities enter the network, receive service at one or more arcs and then leave the network. Average delay has been extensively used as a major system performance measure, leading to nonlinear problems. Exact performance evaluation is possible for the analysis of Jackson open queuing networks (OQN), where the arrival and service processes of the commodities are assumed to be Poisson. In this case the resulting multicommodity flow problem is convex. In this context we first review the cycle cancelling method for the convex multicommodity flow problem. Then, we address capacity expansion resulting in a piece-wise convex multicommodity flow problem. On the other hand, exact performance evaluation is not available when the Poisson processes’ hypotheses are not an acceptable assumption for the analysis of generalised OQN. So, in this case we have to cope with network routing decisions and approximate performance evaluation approaches for generalised OQN. Our aim here is to merge routing algorithms and approximate performance evaluation methods to solve difficult nonlinear multicommodity flow problems arising in generalised OQN.