2000 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.

IEEE Journal of Lightwave Technology
Volume 18 Number 1, January 2000

Traffic Grooming Algorithms for Reducing Electronic Multiplexing Costs in WDM Ring Networks

Page 2.

Abstract:

We develop traffic grooming algorithms for unidirectional SONET/WDM ring networks. The objective is to assign calls to wavelengths in a way that minimizes the total cost of electronic equipment [e.g., the number of SONET add/drop multiplexers (ADM's)]. We show that the general traffic grooming problem is NP-complete. However, for some special cases we obtain algorithms that result in a significant reduction in the number of ADM's. When the traffic from all nodes is destined to a single node, and all traffic rates are the same, we obtain a solution that minimizes the number of ADM's. In the more general case of all-to-all uniform traffic we obtain a lower bound on the number of ADM's required, and provide a heuristic algorithm that performs closely to that bound. To account for more realistic traffic scenarios, we also consider distance dependent traffic, where the traffic load between two nodes is inversely proportional to the distance between them, and again provide a nearly optimal heuristic algorithm that results in substantial ADM savings. Finally, we consider the use of a hub node, where traffic can be switched between different wavelength, and obtain an optimal algorithm which minimizes the number of ADM's by efficiently multiplexing and switching the traffic at the hub. Moreover, we show that any solution not using a hub can be transformed into a solution with a hub using fewer or the same number of ADM's.

References

1. O. Gerstel, G. Sasaki and R. Ramaswami, "Dynamic wavelength allocation in WDM ring networks with little or no wavelength conversion", in Proc. 1996 Allerton Conf., Oct. 1996, . 
2. J. Bannister, L. Fratta and M. Gerla, "Topological design of WDM networks", in Proc. INFOCOM'90, . 
3. R. Ramaswami and K. Sivarajan, "Design of logical topologies for wavelength routed optical networks", IEEE J. Select. Areas Commun., vol. 14, pp.  840- 851,  June  1996 .
4. J. M. Simmons, E. L. Goldstein and A. A. M. Saleh, "On the value of wavelength-add/drop in WDM rings with uniform traffic", in Proc. OFC'98, San Jose, CA, Feb. 1998, . 
5. M. R. Garey and D. S. Johnson, Computers and Intractability, New York: W. H. Freeman, 1979 .
6. X. Zhang and C. Qiao, "An effective and comprehensive solution to traffic glooming and wavelength assignment in SONET/WDM rings", in Conf. On All-Optical Networking, SPIE Proc., vol. 3531, Boston, MA, Sept. 1998, .