Designing Edge-Failure Resilient Networks in the Hose Model
ANUPAM GUPTA
Network design in the "hose model" involves specifying, for each
terminal in the proposed network, upper bounds on the traffic that
terminal takes part in. Given these thresholds, the objective is
to design a network such that _any_ traffic pattern between the
terminals that respects the given thresholds can be routed.
We study how to design such networks that are resilient under a
bounded number of edge failures. In particular, our goal is not
only to design a "base" network, but also extra "backup" capacity;
in the event of an edge failing in the base network, this backup
capacity can be used to reroute the traffic between the ends of
the failed edge.
Since the problem is NP-hard, we give the first heuristics for the
problem with provable guarantees on the cost of the solutions obtained.
While designing the base network can be done by a simple randomized
algorithm, finding good backup networks involves solving a linear
programming relaxation of the problem, and the rounding the solution
iteratively.
The talk is based on joint work with Chandra Chekuri (Bell Labs),
Amit Kumar (IIT Delhi), Seffi Naor and Danny Raz (Technion), and
Tim Roughgarden (UC Berkeley).