Grooming of arbitrary traffic in SONET/WDM BLSRs

SONET add-drop multiplexers (ADMs) are the dominant cost factor in the SONE T/WDM rings. They can potentially be reduced by optical bypass via optical add-drop multiplexers (OADMs) and traffic grooming. In this paper we study the grooming of arbitrary traffic in WDM bidirectional line-switched rings (BLSRs) so as to minimize the ADM cost, Two versions of the minimum ADM cos t problem are addressed. In the first version, each traffic stream has a pr edetermined routing, In the second version, the routing of each traffic str eam is not given in advance; however, each traffic stream is fully duplex w ith symmetric demands, which must be routed along the same path but in oppo site directions, In both versions, we further consider two variants dependi ng on whether a traffic stream is allowed to be split at intermediate nodes . All the four combinations are NP-hard even for any fixed line-speed. Gene ral lower bounds on the minimum ADM cost are provided. Our traffic grooming follows a two-phased approach. The problem targeted at in each phase is NP -hard itself, except the second phase when the line speed is two. Various a pproximation algorithms are proposed in both phases, and their approximatio n ratios are analyzed.