skip to main content
article

On hierarchical traffic grooming in WDM networks

Published: 01 October 2008 Publication History

Abstract

The traffic grooming problem is of high practical importance in emerging wide-area wavelength division multiplexing (WDM) optical networks, yet it is intractable for any but trivial network topologies. In this work, we present an effective and efficient hierarchical traffic grooming framework for WDM networks of general topology, with the objective of minimizing the total number of electronic ports. At the first level of hierarchy, we decompose the network into clusters and designate one node in each cluster as the hub for grooming traffic. At the second level, the hubs form another cluster for grooming intercluster traffic. We view each (first-or second-level) cluster as a virtual star, and we present an efficient near-optimal algorithm for determining the logical topology of lightpaths to carry the traffic within each cluster. Routing and wavelength assignment is then performed directly on the underlying physical topology. We demonstrate the effectiveness of our approach by applying it to two networks of realistic size, a 32-node, 53-link topology and a 47-node, 96-link network. Comparisons to lower bounds indicate that hierarchical grooming is efficient in its use of the network resources of interest, namely, electronic ports and wavelengths. In addition to scaling to large network sizes, our hierarchical approach also facilitates the control and management of multigranular networks.

References

[1]
J. Bar-Ilan, G. Kortsarz, and D. Peleg, "How to allocate network centers," J. Alg., vol. 15, pp. 385-415, 1993.
[2]
P. Baran, "On distributed communications networks," IEEE Trans. Commun., vol. COM-12, no. 1, pp. 1-9, Mar. 1964.
[3]
S. Baroni and P. Bayvel, "Wavelength requirements in arbitrary connected wavelength-routed optical networks," J. Lightw. Technol., vol. 15, no. 2, pp. 242-251, Feb. 1997.
[4]
B. Chen, "Hierarchical traffic grooming in large-scale WDM networks" Ph.D. dissertation, North Carolina State Univ., Raleigh, NC, 2005.
[5]
I. Chlamtac, A. Ganz, and G. Karmi, "Lightpath communications: An approach to high bandwidth optical WAN's," IEEE Trans. Commun., vol. 40, no. 7, pp. 1171-1182, Jul. 1992.
[6]
H. Choi and D. B. Szyld, "Application of threshold partitioning of sparse matrices to Markov chains," in Proc. IEEE Int. Comput. Performance and Dependability Symp. (IPDS), 1996.
[7]
Z. Ding and M. Hamdi, "Clustering techniques for traffic grooming in optical WDM mesh networks," in IEEE GLOBECOM 2002, Nov. 2002, vol. 3, 17-21, pp. 2711-2715.
[8]
R. Dutta, S. Huang, and G. N. Rouskas, "Traffic grooming in path, star, and tree networks: Complexity, bounds, and algorithms," IEEE J. Sel. Areas Commun., vol. 24, no. 4, pp. 66-82, Apr. 2006.
[9]
R. Dutta and G. N. Rouskas, "On optimal traffic grooming in WDM rings," IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 110-121, Jan. 2002.
[10]
R. Dutta and G. N. Rouskas, "Traffic grooming in WDM networks: Past and future," IEEE Netw., vol. 16, no. 6, pp. 46-56, Nov./Dec. 2002.
[11]
M. Esfandiari, S. Gloeckle, A. Zolfagheri, G. Clapp, J. Gannett, H. Kobrinski, V. Poudyal, and R. Skoog, "Improved metro network design by grooming and aggregation of STS-1 demands into OC-192/OC-48 lightpaths," in Proc. NFOEC 2003, Sep. 2003.
[12]
O. Gerstel, R. Ramaswami, and G. Sasaki, "Cost-effective traffic grooming in WDM rings," IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 618-630, Oct. 2000.
[13]
T. Gonzalez, "Clustering to minimize the maximum inter-cluster distance," Theoret. Comput. Sci., vol. 38, pp. 293-306, 1985.
[14]
A. H. John, Clustering Algorithms. Hoboken, NJ: Wiley, 1975.
[15]
D. Hochbaum and D. B. Shmoys, "A best possible heuristic for the k-center problem," Math. Oper. Res., vol. 10, pp. 180-184, 1985.
[16]
D. Hochbaum and D. B. Shmoys, "A unified apporach to approximation algorithms for bottleneck problems," J. ACM, vol. 33, pp. 533-550, 1986.
[17]
J. Q. Hu and B. Leida, "Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks," in Proc. IEEE INFOCOM, 2004, vol. 23, pp. 495-501.
[18]
Z. K. G. Patrocínio, Jr. and G. R. Mateus, "A Lagrangian-based heuristic for traffic grooming in WDM optical networks," in IEEE GLOBECOM, 2003, pp. 2767-2771.
[19]
G. Karypis and V. Kumar, "A fast and highly quality multilevel scheme for partitioning irregular graphs," SIAM J. Sci. Comput., 1998.
[20]
V. R. Konda and T. Y. Chow, "Algorithm for traffic grooming in optical networks to minimize the number of transceivers," in IEEE Workshop on High Performance Switching and Routing, 2001, pp. 218-221.
[21]
C. Lee and E. K. Park, "A genetic algorithm for traffic grooming in all-optical mesh networks," in IEEE Int. Conf. Systems, Man, and Cybernetics , Oct. 2002, vol. 7, pp. 6-9.
[22]
D. Li, Z. Sun, X. Jia, and K. Makki, "Traffic grooming on general topology WDM networks," Proc. Inst. Electr. Eng.--Commun., vol. 150, no. 3, pp. 197-201, Jun. 2003.
[23]
K. Schloegel, G. Karypis, and V. Kumar, "A new algorithm for multi-objective graph partitioning," Dept. Comput. Sci., Univ. of Minnesota, Duluth, MN, Tech. Rep. 99-003, 1999.
[24]
D. B. Shmoys, "Approximation algorithms for facility location problems," in Proc. APPROX 2000, Lecture Notes in Computer Science vol. 1913, pp. 27-32.
[25]
J. Simmons, E. Goldstein, and A. Saleh, "Quantifying the benefit of wavelength add-drop in WDM rings with distance-independent and dependent traffic," J. Lightw. Technol., vol. 17, no. 1, pp. 48-57, Jan. 1999.
[26]
H. Siregar, H. Takagi, and Y. Zhang, "Efficient routing and wavelength assignment in wavelength-routed optical networks," in Proc. 7th Asia-Pacific Network Operations and Management Symp., Oct. 2003, pp. 116-127.
[27]
M. Thorup, "Quick k-median, k-center, and facility location for sparse graphs," in Proc. ICALP 2001, Lecture Notes in Computer Science vol. 2076, pp. 249-260.
[28]
P.-J. Wan, G. Calinescu, L. Liu, and O. Frieder, "Grooming of arbitrary traffic in SONET/WDM BLSRS," IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1995-2003, Oct. 2000.
[29]
D. West, Introduction to Graph Theory. Upper Saddle River, NJ: Prentice-Hall, 1996.
[30]
H. Zhu, H. Zang, K. Zhu, and B. Mukherjee, "A novel generic graph model for traffic grooming in heterogeneous WDM mesh networks," IEEE/ACM Trans. Netw., vol. 11, no. 2, pp. 285-299, Apr. 2003.
[31]
K. Zhu and B. Mukherjee, "Traffic grooming in an optical WDM mesh network," IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 122-133, Jan. 2002.

Cited By

View all
  • (2021)Scalable Computing System with Two-Level Reconfiguration of Multi-channel Inter-Node CommunicationComputational Science – ICCS 202110.1007/978-3-030-77970-2_41(540-553)Online publication date: 16-Jun-2021
  • (2017)QoT-aware elastic bandwidth allocation and spare capacity assignment in flexible island-based optical transport networks under shared risk link group constraintsComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2017.02.005116:C(111-140)Online publication date: 7-Apr-2017
  • (2016)Multicast protection and grooming scheme in survivable WDM optical networksOptical Switching and Networking10.1016/j.osn.2015.06.00319:P2(42-57)Online publication date: 1-Jan-2016
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking
IEEE/ACM Transactions on Networking  Volume 16, Issue 5
October 2008
238 pages

Publisher

IEEE Press

Publication History

Published: 01 October 2008
Revised: 21 September 2006
Received: 23 August 2005
Published in TON Volume 16, Issue 5

Author Tags

  1. hierarchical traffic grooming
  2. k-center
  3. optical networks
  4. wavelength division multiplexing (WDM)

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 20 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2021)Scalable Computing System with Two-Level Reconfiguration of Multi-channel Inter-Node CommunicationComputational Science – ICCS 202110.1007/978-3-030-77970-2_41(540-553)Online publication date: 16-Jun-2021
  • (2017)QoT-aware elastic bandwidth allocation and spare capacity assignment in flexible island-based optical transport networks under shared risk link group constraintsComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2017.02.005116:C(111-140)Online publication date: 7-Apr-2017
  • (2016)Multicast protection and grooming scheme in survivable WDM optical networksOptical Switching and Networking10.1016/j.osn.2015.06.00319:P2(42-57)Online publication date: 1-Jan-2016
  • (2015)GRASP for traffic grooming and routing with simple path constraints in WDM mesh networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.04.01386:C(27-39)Online publication date: 5-Jul-2015
  • (2015)Two-level iterated local search for WDM network design problem with traffic groomingApplied Soft Computing10.1016/j.asoc.2015.08.04437:C(715-724)Online publication date: 1-Dec-2015
  • (2012)Approximation algorithms for many-to-many traffic grooming in optical WDM networksIEEE/ACM Transactions on Networking10.5555/2428696.242871220:5(1527-1540)Online publication date: 1-Oct-2012
  • (2010)Approximation algorithms for many-to-many traffic grooming in WDM mesh networksProceedings of the 29th conference on Information communications10.5555/1833515.1833626(579-587)Online publication date: 14-Mar-2010
  • (2010)Effect of sparse grooming on power consumption of optical networksProceedings of the 1st Workshop on Green Computing10.1145/1925013.1925018(27-32)Online publication date: 29-Nov-2010
  • (2010)Design and provisioning of WDM networks with many-to-many traffic groomingIEEE/ACM Transactions on Networking10.1109/TNET.2010.205123418:6(1869-1882)Online publication date: 1-Dec-2010
  • (2009)WDM network traffic grooming using clustersProceedings of the 6th international conference on High capacity optical networks and enabling technologies10.5555/1812482.1812518(208-215)Online publication date: 28-Dec-2009

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media