Effective Traffic Grooming Algorithms in SONET/WDM Ring Networks
Tóm tắt
Much work has focused on traffic grooming in SONET/WDM ring networks. Previous work has considered many aspects of traffic grooming, including minimizing the number of ADMs, minimizing the number of wavelengths, considering different traffic models, using different network architectures, incorporating switching capability and so on. In this work, we study traffic grooming in unidirectional ring networks with no switching capability under both uniform traffic and non-uniform traffic models to reduce electronic multiplexing costs. Based on the clustering notion, we derive a general and tighter lower bound for the number of ADMs required in traffic grooming under the uniform all-to-all traffic model. This bound reduces to special cases obtained in previous work. We also derive general, tighter, and closed form lower bounds for the number of ADMs required under two non-uniform traffic models: the distance-dependent traffic model and the non-uniform symmetric traffic model. Cost-effective multi-phase algorithms that exploit traffic characteristics are then designed and studied to efficiently groom traffic streams under different traffic models. Our numerical and simulation results show that the proposed multi-phase algorithms outperform existing traffic grooming algorithms by using a fewer number of ADMs. Our algorithms in several cases also achieve the lower bounds derived.
Tài liệu tham khảo
R. Ramaswami, K. N. Sivarajan, Optical networks: A practical perspective, second edition (Morgan Kaufmann Publisher, 2002).
C. S. R. Murthy, M. Gurusamy, WDM optical networks: Concepts, design, and algorithms (Prentice Hall PTR, 2002).
B. Mukherjee, WDM optical networks: Progress and challenges, IEEE Journal of Selected Areas in Communications, vol. 18,no. 10, (Oct. 2000), pp. 1810–1824.
U. Black, Optical networks: Third generation transport systems (Prentice Hall PTR, 2002).
S. Thiagarajan, A. K. Somani, Traffic grooming for survivable WDM mesh networks, Proceedings of OptiComm, Denver CO, USA (Aug. 2001), pp. 54–65.
J. Simmons, E. L. Goldstein, A. Saleh, On the value of wavelength add/drop in WDM rings with uniform traffic, Proceedings of OFC'98, San Jose CA, USA (Feb. 1998).
O. Gerstel, P. Lin, G. Sasaki, Wavelength assignment in a WDM ring to minimize the cost of embedded SONET rings, Proceedings of INFOCOM San Francisco, CA, USA (March 1998), pp. 94–101.
O. Gerstel, P. Lin, G. Sasaki, Combined WDM and SONET network design, Proceedings of INFOCOM, New York, NY, USA (March 1999), pp. 734–743.
J. Simmons, A. Saleh, Quantifying the benefit of wavelength add-drop in WDM rings with distance-independent and dependent traffic, IEEE Journal on Light-wave Technology, vol. 17,no. 1, (Jan. 1999), pp. 48–57.
R. Ramaswami, O. Gerstel, H. Sasaki, Cost effective grooming in WDM rings, IEEE/ACM Transactions on Networking, vol. 8,no. 5, (Oct. 2000), pp. 618–630.
E. Modiano, A. Chiu, Traffic grooming algorithms for minimizing electronic multiplexing costs in WDM ring networks, IEEE Journal of Light-wave Technology, vol. 18,no. 1, (Jan. 2000), pp. 2–12.
X. Zhang, C. Qiao, An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings, IEEE/ACM Transactions on Networking, vol. 8,no. 5, (Oct. 2000), pp. 608–617.
R. Berry, E. Modiano, Reducing electronic multiplexing costs in SONET/WDM rings, IEEE Journal on Selected Areas in Communications, vol. 18,no. 10, (Oct. 2000), pp. 1961–1971.
X.-Y. Li, L. Liu, P.-J. Wan, O. Frieder, Practical Traffic Grooming for Single Hub SONET/WDM Rings, IEEE Conference on Local Computer Networks, Tampa FL, USA (Nov. 2000), pp. 556–564.
L. Liu, X.-Y. Li, P.-J. Wan, O. Frieder, Wavelength Assignment in WDM ring to Minimize SONET ADMs, IEEE INFOCOM'2000, Tel-Aviv, Israel (March 2000).
X.-Y. Li, P.-J. Wan, L. Liu, Select line speeds for single hub SONET/WDM ring networks, International Conference on Communications, New Orleans LA, USA (June 2000), pp. 495–499.
P. J. Wan, G. Ginescu, L. Liu, O. Frieder, Grooming of arbitrary traffic in SONET/WDM BLSRs, IEEE Journal on Selected Areas in Communications, vol. 18,no. 10, (Oct. 2000), pp. 1995–2003.
E. Modiano, R. Berry, The role of switching in reducing network port counts. Proceedings of the 39th Annual Allerton Conference on Communication, Control, and Computing, Allerton IL, USA (Sept. 2001).
J. Wang, V. R. Vemuri, W. Cho, B. Mukherjee, Improved approaches for cost-effective traffic grooming in WDM ring networks: ILP formulation and single-hop and multihop connections, IEEE/OSA Journal of Lightwave Technology, vol. 19,no. 11, (Nov. 2001), pp. 1645–1653.
W. Cho, J. Wang, B. Mukherjee, Improved approaches for cost-effective traffic grooming in WDM ring networks: Uniform-traffic case, Photonic Network Communications, vol. 3,no. 3, (2001), pp. 245–254.
T. Chow, P. J. Lin, The ring grooming problem. Discrete Applied Math., submitted, (2002).
C. J. Colbourn, A. Ling, Wavelength add-drop multiplexing and minimizing SONETADMs, Discrete Mathematics (Oct. 2001).
E. Modiano, R. Berry, Switching and traffic grooming in WDM networks, Joint Conference on Information Sciences (JCIS), Durham, North Carolina (March 2002).
R. Dutta, G. N. Rouskas, On optimal traffic grooming in WDM rings, IEEE Journal on Selected Areas in Communications, vol. 20,no. 1, (Jan. 2002), pp. 110–121.
G. Li, R. Simha, An efficient algorithm for reducing the number of add-drop multiplexers in SONET/WDM rings, Journal of High Speed Networks, vol. 11,no. 1, (2002), pp. 67–77.
K. Zhu, B. Mukherjee, Traffic grooming in an optical WDM mesh network, IEEE Journal on Selected Areas in Communications, vol. 20,no. 1, (Jan. 2002), pp. 122–133.
J. Q. Hu, Optimal traffic grooming for wavelength-division-multiplexing rings with all-to-all uniform traffic, Journal of Optical Networking, vol. 1,no. 1, (2002), pp. 32–42.
R. Dutta, G. N. Rouskas, Bounds on traffic grooming in star and tree networks, Proceedings of the 2001 Allerton Conference on Communication, Control, and Computing, Monticello IL, USA (Oct. 2001).
X. Zhang, C. Qiao, An effective and comprehensive approach to traffic grooming and wavelength assignment in SONET/WDM rings, SPIE Proceedings of Conf. All-optical Networking, vol. 3531, (Sept. 1998), pp. 221–232.
O. Gerstel, R. Ramaswami, Cost effective grooming in WDM rings, Proceedings of INFOCOM, San Francisco CA, USA (March 1998).
V. R. Konda, T. Y. Chow, Algorithm for traffic grooming in optical networks to minimize the number of transceivers, IEEE Workshop on High Performance Switching and Routing, Dallas TX, USA (May 2001).
R. Srinivasan, Dynamic routing in WDM grooming networks. Iowa State University, Dept. of Electrical and Computer Engineering, DCNL Technical Report: DCNL-ON-2001-001 (2001).
M. Brunato, R. Battiti, A multistart randomized greedy algorithm for traffic grooming on mesh logical topologies, Proceedings of IFIP Working Conference on Optical Network Design and Modeling, Torino, Italy (Dec. 2002).
R. Srinivasan, A. K. Somani, Request-specific routing in WDM grooming networks, Proceedings of IEEE International Conference on Communications, New York, NY, USA (April–May 2002).
G. Huiban, S. Perennes, M. Syska, Traffic grooming in WDM networks with multi-layer switches. Proceedings of IEEE International Conference on Communications, New York NY, USA (April–May 2002).
J. Q. Hu, B. Leida, Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks, Sixth INFORMS Telecommunications Conference, Boca Raton, FL, USA (March 2002).
K. Zhu, B. Mukherjee, Traffic grooming in an optical WDM mesh network. IEEE Journal on Selected Areas in Communications, vol. 20,no. 1, (Jan. 2002), pp. 122–133.
R. Dutta, G. N. Rouskas, Traffic grooming in WDM networks: Past and future, NCSU CSC Technical Report TR-2002-02 (2002).
K. Zhu, B. Mukherjee, A review of traffic grooming in WDM optical networks: Architectures and Challenges, Optical Network Magazine, March/April (2003), pp. 55–64.