Practical traffic grooming scheme for single-hub SONET/WDM rings

In SONET/WDM networks, one fiber supports multiple wavelengths and each wavelength supports several low rate tributary streams. Traffic grooming is then defined as properly using SONET Add/Drop Multiplexer (ADM) to electronically multiplex and demultiplex required tributary traffic patterns with minimal resource cost (wavelengths and ADMs). This paper studies the traffic-grooming problem in single hub SONET/WDM networks and extends existing results. We analyze the real deployments, generalize their results, and study the practical special cases. We prove that BLSR/2 would never be more expensive than UPSR under any traffic pattern. We present the exact minimum costs of uniform traffic in both UPSR and BLSR/2. We also give approximation algorithms for optimal grooming of non-uniform traffic after showing that this problem is NP-complete. Finally, we consider how to select the line speeds if there are two different line speeds available. Keyword: Traffic grooming, SONET/WDM ring, UPSR, BLSR/2, single-hub, bin packing