Bounds on fiber minimization in optical networks with fixed fiber capacity

We consider the problem of minimizing the amount of deployed fiber in optical networks in which each fiber carries a fixed number of wavelengths. We are given a network of general topology to carry a set of demands. For each demand we wish to choose a route and a wavelength. Since only distinct wavelengths can be carried on the same fiber, each link e requires maxλ Fe(λ) fibers where Fe(λ) is the number of demands along e that are assigned wavelength λ. We wish to minimize the total amount of fiber deployed in order to carry all the demands. Most past work either assumed an unlimited number of wavelengths or else was restricted to specific topologies such as lines, rings and trees. We show that for general topologies the problem is hard to approximate. In particular, for a family of networks of size N, we show that there is no O(log¹4-ε/N) approximation algorithm for any ε > 0 unless all problems in NP can be solved by randomized algorithms with expected running time O(n^{polylog n}). On the positive side we describe methods to choose routes and wavelengths in order to obtain a logarithmic approximation ratio. Lastly we present heuristics that have close-to-optimal performance on example problems on several US backbone networks.