Efficient Decomposition Techniques for Traffic Grooming Problems in Optical Networks

Traffic grooming refers to a class of optimization problems developed to address the gap between the wavelength capacity and the traffic demands of individual connections in optical WDM networks. In this work, we focus on static traffic grooming problem and its subproblems, with an objective function of minimizing the total number of lightpaths. A lightpath is a path of physical links with a particular wavelength reserved on each link, and it is used as a metric of network cost. We first review the existing work in this area and a typical integer linear program (ILP) formulation in the literature, and we identify two challenges related to this formulation in terms of scalability and wavelengths fragmentation. We then make three contributions that address the scalability challenges. First, we propose a new solution approach that decomposes the traffic grooming problem into two subproblems that are solved sequentially: (1) the virtual topology and traffic routing (VTTR) subproblem, that does not take into account physical topology constraints, and (2) the routing and wavelength assignment (RWA) subproblem, that reconciles the virtual topology determined by VTTR with the physical topology. The decomposition is exact when the networ