We consider the problem of traffic grooming in wavelength-division-multiplexing (WDM) rings. Our objective is to minimize the required number of electronic add–drop multiplexers. We first formulate the problem as an integer linear programming (ILP) problem, and we then show that this ILP problem can be converted into an equivalent mixed ILP (MILP) problem in which a large number of integer variables in the original ILP can be relaxed to continuous variables. The resulting MILP problem is much easier to solve. For ring networks found in most applications (e.g., access and interoffice rings), which typically have less than 20 nodes, it can produce optimal or near-optimal solutions in a few seconds or minutes by use of commercially available linear programming software, such as CPLEX, on a PC. We also discuss how our ILP formulation can be extended to more-general traffic grooming problems, such as networks with dynamic traffic and how to take the number of wavelengths into consideration. Finally, numerical examples are presented.
© 2002 Optical Society of America
Original Manuscript: May 2, 2002
Revised Manuscript: May 2, 2002
Published: October 15, 2002
Jian-Qiang Hu, "Traffic grooming in wavelength-division-multiplexing ring networks: a linear programming solution," J. Opt. Netw. 1, 397-408 (2002)