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 network is not wavelength limited. We also propose three algorithms that use a partial LP 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.;Second, instead of viewing the network as a flat entity, we further consider networks with hierarchies, where the second level of hierarchy consists of hub nodes, and the first level is formed by the remaining nodes. Hierarchical traffic grooming facilitates the control and management of multigranular WDM networks. We first survey heuristic hierarchical grooming algorithms. We then apply the above decomposition approach onto hierarchical traffic grooming. We define the hierarchical virtual topology and traffic routing (H-VTTR) problem, and we present a suite of ILP formulations to solve it. The formulations represent various tradeoffs between solution quality and running time. We also explore the performance of the formulations under various direct lightpath thresholds, traffic loads, and number of hubs. The formulations are cross-compared with the baseline VTTR formulation.;Finally, we consider the traffic grooming problem with multi-class traffic where traffic classes may be defined across various dimensions, including: (1) quality of Service (QoS) requirements, in which case the network may provision dierent lightpaths to support different levels of QoS; (2) the user or group of users, in which case the network operator may groom traffic of different organizations (e.g., competitors) onto different sets of lighgtpaths; and/or (3) privacy or security considerations. Given such a classification of user traffic, and regardless of how the various classes are defined, we impose the additional constraints that grooming onto a given lightpath is permitted if and only if the traffic to be groomed belongs to the same class. We refer to this new problem as multi-class virtual topology and traffic routing (MC-VTTR). We develop a solution to MC-VTTR and quantify the overhead of supporting multiple classes in terms of solution quality and running time.