Disjoint-Path
Facility Location: Theory and Practice
Lee Breslau, Ilias Diakonikolas, Nicholas Duffield, Yu Gu, MohammadTaghi Hajiaghayi, David S. Johnson, Howard Karloff, Mauricio Resende, Subhabrata Sen
Manuscript, 2010.
Abstract:
This paper is a theoretical and experimental study of a facility location problem that emanated from networking. Suppose we are given a network modeled as a directed graph G = (V , A), together with (not-necessarily-disjoint) subsets C and F of V, where C is a set of customer locations and F is a set of potential facility locations. Our goal is to find a minimum sized subset F' of F such that for every customer c in C there are two locations f1, f2 in F' such that traffic from c to f1 and to f2 is routed on disjoint paths (usually shortest paths) under the network's routing protocols. This problem might arise in a variety of scenarios. We concentrate on two here. In the first, which is the primary motivation for this paper, special hardware will be installed at the chosen locations and used in a monitoring scheme proposed by Gu et al. for doing end-to-end traffic measurement. The second scenario relates to content distribution, in which the facility locations are sites from which time-sensitive content (television shows, etc.) will be distributed to the customer sites.
Although we prove that this problem is impossible to approximate in the worst case even to within a factor of 2^[(log n)^(1-eps)] for any eps> 0 (assuming no NP-complete language can be solved in quasi-polynomial time), we show that the situation is much better in practice. We propose a collection of algorithms that build solutions and determine lower bounds on the optimum solution, and evaluate them on several large real ISP topologies and on synthetic networks designed to reflect real-world network structure. One of these algorithms was quite practical and found solutions averaging within 2% of optimal for the synthetic instances and 6% for the real-world instances. Indeed, it found provably optimal solutions on over 80% of our synthetic instances and over 50% of our real-world instances. These solutions yielded facility location sets F' that were substantially smaller, typically at least 80% smaller for our real-world instances, than a naive solution.
Full version: to be posted