On failure tolerant networks: efficiency and approximation of multiroute and stochastic flow

Speaker: Jean-François Baffier, JFLI & The University of Tokyo

Date: 19th April 2013 

Time: 14:00

Place: room 202, Faculty of Science Bldg. 7, Hongo Campus, The University of Tokyo

A k-route channel is a communication path that goes through k edge-disjoints paths, providing a resistance up to k-1 edge failures. A k-route flow (a multiroute flow of routes) is sum of k-route channels according to the network capacities constraint. It provides a lower bound of the max-flow value in case of k-1 edge failures. A max-flow/min-cut duality theorem in the k-route context has been proven by Kishimoto and Takeuchi (93). This result can be easily extended to include node failures orr other variants of the multiroute flow problem. Given a network with one variable edge, we study the impact of the variation of the capacity of this edge on the multiroute flow in a general case (previous work has 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 piecewise linear function (with at most k+1 breaking points). We provide a polynomial algorithm which us all the breaking points for a given source/sink pair. We also extend our approach to the case with any number of variable edges. Another approach, introduced by Lin (99), is to handle those failures by using stochastic-flow networks (with a probability of failure at nodes and arcs). To give efficient lower bounds and expected values of the flows, we will compare and combine parametric, multiroute, and stochastic flows.




Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *