On parameterized Multiroute-Flow : an efficient tool to manage failures resistance in a network
Jean-François BAFFIER

09 March 2012, 10h30 - 09 March 2012, 11h30 Salle/Bat : 455/PCRI-N
Contact :

Activités de recherche :

Résumé :

A K-route channel is a communication path that goes through K edge-disjoint paths, providing a resistance up to K-1 edge failures. A K-route-flow (a multiroute flow of K routes) is a sum of K-route channels respecting the network capacities constraint. It provides a lower bound of the max-flow value in a case of K-1 edges failures. A max-flow/min-cut theorem in the K-route context has been proved by Kishimoto and Takeuchi. This results can be easily extended to include node failures.

Given a network with one variable edge, we study the impact of the variation of this edge's capacity on the multiroute flow in a general case (previous work already treated the case of 1-route-flow and 2-route- flow). For any integer K, we show that a max-K-flow solution is a piecewise linear function (with at most K +1 changes of slope that we call critical points). We provide a polynomial algorithm which gives us all the critical points for a given source/sink pair. We also extend the function analysis to the case with any number of variable edges.