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).