Approximation Algorithms for Grooming in Optical Network Design

We study traffic grooming in optical network design. The goal is to aggregate low-bandwidth traffic streams to efficiently utilize high-bandwidth media such as wavelength channels. More precisely, given traffic demands to be routed in a network, the design problem is to define a collection of light paths such that each demand can follow a sequence of consecutive light paths. Each light path has unit-wavelength bandwidth, and multiple sub-wavelength demands may share a common light path. Traffic must enter and depart from a light path at its two endpoints only. Most previous work on grooming focused on the ring topology and typically dealt only with uniform bandwidth demands, whereas we consider more general settings. We study two objectives. One is to minimize total equipment cost necessary to support the light paths; the other is simply to minimize the number of light paths. Even for the extremely restricted special case of a line topology and traffic demands that request half-wavelength bandwidth, we show that both objectives are APX-hard to optimize, which means we cannot approximate the optimum arbitrarily closely. On the other extreme of generality, for arbitrary network topologies and traffic demands that request arbitrary amounts of bandwidth, we show a logarithmic approximation for cost minimization and a 2-approximation for minimizing light path counts. Furthermore, we discover that the special case of half-wavelength demands has rich combinatorial properties, closely related to graph problems such as cycle packing and pattern matching problems such as interchange distance in strings. We show how to approximate both objectives up to small constant factors in this case, while similarly improving the approximation and hardness of the interchange distance problem as well.