Buy-at-bulk network design with protection

We consider approximation algorithms for buy-at-bulk network design, with the additional constraint that demand pairs be protected against a single edge or node failure in the network. In practice, the most popular model used in high speed telecommunication networks for protection against failures, is the so-called 1+1 model. In this model, two edge or node-disjoint paths are provisioned for each demand pair. We obtain the first non-trivial approximation algorithms for buy-at-bulk network design in the 1+1 model for both edge and node-disjoint protection requirements. Our results are for the single-cable cost model, which is prevalent in optical networks. More specifically, we present a constant-factor approximation for the single-sink case, and an O log3 n approximation for the multi-commodity case. These results are of interest for practical applications and also suggest several new challenging theoretical problems. Key words: Buy-at-bulk; network design; 1+1 protection; approximation algorithm