Grooming of arbitrary traffic in SONET/WDM rings

SONET add-drop multiplexers (ADMs) are the dominant cost in SONET/WDM rings. They can potentially be reduced by optical bypass via wavelength add-drop multiplexers (WADMs) and traffic grooming. While many works have been done on the grooming of all-to-all uniform traffic and one-to-all traffic, the grooming of arbitrary traffic have not been studied yet. We first prove the NP-hardness of this problem. We then presents two general lower bounds on the minimum ADM cost. After that we propose a two-phased algorithm. The two subproblems in these two phases are both NP-hard. Various approximation algorithms are proposed to each subproblem, and their performances are discussed.