Traffic grooming in optical networks: Decomposition and partial linear programming (LP) relaxation

We consider the traffic grooming problem, a fundamental network design problem in optical networks. We review a typical integer linear program formulation considered in the literature, and we identify two challenges related to this formulation in terms of scalability and wavelength fragmentation. We then propose a new (to our knowledge) solution approach that decomposes the traffic grooming problem into two subproblems that are solved sequentially: 1) the virtual topology and traffic routing (VTTR) subproblem, which does not take into account physical topology constraints, and 2) the routing and wavelength assignment subproblem, which reconciles the virtual topology determined by VTTR with the physical topology. The decomposition is exact when the network is not wavelength limited. We also propose an algorithm that uses a partial linear programming relaxation technique driven by lightpath utilization information to solve the VTTR subproblem efficiently. Our approach delivers a desirable tradeoff between running time and quality of the final solution.