Abstract

We consider a hierarchical approach for traffic grooming in large multiwavelength networks of a general topology. Inspired by similar concepts in the airline industry, we decompose the network into clusters, and select a hub node in each cluster to groom traffic originating and terminating locally. At the second level of the hierarchy, the hub nodes form a virtual cluster for the purpose of grooming intra-cluster traffic. Clustering and hierarchical grooming enables us to cope with large network sizes and facilitates the control and management of traffic and network resources. Yet, determining the size and composition of clusters so as to yield good grooming solutions is a challenging task. We identify the grooming-specific factors affecting the selection of clusters, and we develop a parameterized clustering algorithm that can achieve a desired trade-off among various goals. We also obtain lower bounds on two important objectives in traffic grooming: the number of lightpaths and wavelengths needed to carry the subwavelength traffic. We demonstrate the effectiveness of clustering and hierarchical grooming by presenting the results of experiments on two network topologies that are substantially larger than those considered in previous traffic grooming studies.

© 2010 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. R. Dutta, G. N. Rouskas, “On optimal traffic grooming in WDM rings,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 110–121, Jan. 2002.
    [CrossRef]
  2. H. Zhu, H. Zang, K. Zhu, 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.
    [CrossRef]
  3. R. Dutta, G. N. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network, vol. 16, no. 6, pp. 46–56, Nov./Dec. 2002.
    [CrossRef]
  4. O. Gerstel, R. Ramaswami, G. Sasaki, “Cost-effective traffic grooming in WDM rings,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 618–630, Oct. 2000.
    [CrossRef]
  5. P.-J. Wan, G. Calinescu, L. Liu, O. Frieder, “Grooming of arbitrary traffic in SONET/WDM BLSRs,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1995–2003, 2000.
    [CrossRef]
  6. V. R. Konda, 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, Dallas, TX, 2001, pp. 218–221.
    [CrossRef]
  7. D. Li, Z. Sun, X. Jia, K. Makki, “Traffic grooming on general topology WDM networks,” IEE Proc.–Commun., vol. 150, no. 3, pp. 197–201, June 2003.
    [CrossRef]
  8. J. Hu, B. Leida, “Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks,” Proc. of the IEEE INFOCOM 2004, the 23rd Annu. Joint Conf. of the IEEE Computer and Communications Societies, Hong Kong, 2004, vol. 1, pp. 495–501.
  9. Z. K. G. Patrocínio, G. R. Mateus, “A Lagrangian-based heuristic for traffic grooming in WDM optical networks,” in IEEE Global Telecommunications Conf., 2003. GLOBECOM '03., 2003, vol. 5, pp. 2767–2771.
    [CrossRef]
  10. C. Lee, E. K. Park, “A genetic algorithm for traffic grooming in all-optical mesh networks,” in 2002 IEEE Int. Conf. on Systems, Man and Cybernetics, 2002, vol. 7.
  11. B. Chen, G. N. Rouskas, R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol. 16, no. 5, pp. 1226–1238, Oct. 2008.
    [CrossRef]
  12. I. Chlamtac, A. Ganz, G. Karmi, “Lightpath communications: an approach to high bandwidth optical WANS,” IEEE Trans. Commun., vol. 40, no. 7, pp. 1171–1182, July 1992.
    [CrossRef]
  13. B. Chen, G. N. Rouskas, R. Dutta, “Traffic grooming in WDM ring networks to minimize the maximum electronic port cost,” Opt. Switching Networking, vol. 2, no. 1, pp. 1–18, May 2005.
    [CrossRef]
  14. B. Chen, “Hierarchical traffic grooming in large-scale WDM networks,” Ph.D. dissertation, North Carolina State University, Raleigh, NC, August 2005.
  15. H. Siregar, H. Takagi, Y. Zhang, “Efficient routing and wavelength assignment in wavelength-routed optical networks,” Proc. 7th Asia-Pacific Network Operations and Management Symp., Fukuoka, Japan, 2003, pp. 116–127.
  16. S. Baroni, P. Bayvel, “Wavelength requirements in arbitrary connected wavelength-routed optical networks,” J. Lightwave Technol, vol. 15, no. 2, pp. 242–251, Feb. 1997.
    [CrossRef]
  17. J. A. Hartigan, Clustering Algorithms, New York: Wiley, 1975.
  18. H. Choi, D. B. Szyld, “Application of threshold partitioning of sparse matrices to Markov chains,” in Proc. of the IEEE Int. Computer Performance and Dependability Symp., 1996, pp. 158–165.
  19. K. Schloegel, G. Karypis, V. Kumar, “A new algorithm for multi-objective graph partitioning,” Department of Computer Science, University of Minnesota, Tech. Rep. 99–003, Sept. 1999.
  20. J. Bar-Ilan, G. Kortsarz, D. Peleg, “How to allocate network centers,” J. Algorithms, vol. 15, pp. 385–415, 1993.
    [CrossRef]
  21. D. Hochbaum, D. Shmoys, “A unified approach to approximation algorithms for bottleneck problems,” J. ACM, vol. 33, pp. 533–550, 1986.
    [CrossRef]
  22. D. B. Shmoys, “Approximation algorithms for facility location problems,” in Approximation Algorithms for Combinatorial Optimization: Proc. Third Int. Workshop, APPROX 2000, Saarbrücken, Germany, 2000, vol. 1913, pp. 27–32.
  23. M. Thorup, “Quick k-median, k-center, and facility location for sparse graphs,” Automata, Languages and Programming: Proc. of the 28th Int. Colloquium, ICALP 2001, Crete, Greece, 2001, vol. 2076, pp. 249–260.
  24. T. Gonzalez, “Clustering to minimize the maximum inter-cluster distance,” Theoret. Comput. Sci., vol. 38, pp. 293–306, 1985.
    [CrossRef]
  25. D. Hochbaum, D. Shmoys, “A best possible heuristic for the k-center problem,” Math. Op. Res., vol. 10, pp. 180–184, 1985.
    [CrossRef]
  26. M. Esfandiari, S. Gloeckle, A. Zolfagheri, G. Clapp, J. Gannett, H. Kobrinski, V. Poudyal, R. Skoog, “Improved metro network design by grooming and aggregation of STS-1 demands into OC-192/OC-48 lightpaths,” in The Nat. Fiber Optic Engineers Conf. (NFOEC) 2003, Orlando, FL, 2003.
  27. Z. Ding, M. Hamdi, “Clustering techniques for traffic grooming in optical WDM mesh networks,” in 2002 IEEE Global Telecommunications Conf., GLOBECOM 2002, vol. 3, 2002, pp. 2711–2715.
  28. B. Hendrickson, R. Leland, “The CHACO user’s guide,” Sandia National Laboratories, Albuquerque, NM, Tech. Rep. SAND95–2344, July 1995.
  29. B. Kernighan, S. Lin, “An efficient heuristic procedure for partitioning graphs,” Bell Syst. Tech. J., vol. 29, pp. 291–307, 1970.
    [CrossRef]
  30. P. Baran, “On distributed communications networks,” IEEE Trans. Commun., vol. 12, no. 1, pp. 1–9, Mar. 1964.
    [CrossRef]

2008 (1)

B. Chen, G. N. Rouskas, R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol. 16, no. 5, pp. 1226–1238, Oct. 2008.
[CrossRef]

2005 (1)

B. Chen, G. N. Rouskas, R. Dutta, “Traffic grooming in WDM ring networks to minimize the maximum electronic port cost,” Opt. Switching Networking, vol. 2, no. 1, pp. 1–18, May 2005.
[CrossRef]

2003 (2)

D. Li, Z. Sun, X. Jia, K. Makki, “Traffic grooming on general topology WDM networks,” IEE Proc.–Commun., vol. 150, no. 3, pp. 197–201, June 2003.
[CrossRef]

H. Zhu, H. Zang, K. Zhu, 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.
[CrossRef]

2002 (2)

R. Dutta, G. N. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network, vol. 16, no. 6, pp. 46–56, Nov./Dec. 2002.
[CrossRef]

R. Dutta, G. N. Rouskas, “On optimal traffic grooming in WDM rings,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 110–121, Jan. 2002.
[CrossRef]

2000 (2)

O. Gerstel, R. Ramaswami, G. Sasaki, “Cost-effective traffic grooming in WDM rings,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 618–630, Oct. 2000.
[CrossRef]

P.-J. Wan, G. Calinescu, L. Liu, O. Frieder, “Grooming of arbitrary traffic in SONET/WDM BLSRs,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1995–2003, 2000.
[CrossRef]

1997 (1)

S. Baroni, P. Bayvel, “Wavelength requirements in arbitrary connected wavelength-routed optical networks,” J. Lightwave Technol, vol. 15, no. 2, pp. 242–251, Feb. 1997.
[CrossRef]

1993 (1)

J. Bar-Ilan, G. Kortsarz, D. Peleg, “How to allocate network centers,” J. Algorithms, vol. 15, pp. 385–415, 1993.
[CrossRef]

1992 (1)

I. Chlamtac, A. Ganz, G. Karmi, “Lightpath communications: an approach to high bandwidth optical WANS,” IEEE Trans. Commun., vol. 40, no. 7, pp. 1171–1182, July 1992.
[CrossRef]

1986 (1)

D. Hochbaum, D. Shmoys, “A unified approach to approximation algorithms for bottleneck problems,” J. ACM, vol. 33, pp. 533–550, 1986.
[CrossRef]

1985 (2)

T. Gonzalez, “Clustering to minimize the maximum inter-cluster distance,” Theoret. Comput. Sci., vol. 38, pp. 293–306, 1985.
[CrossRef]

D. Hochbaum, D. Shmoys, “A best possible heuristic for the k-center problem,” Math. Op. Res., vol. 10, pp. 180–184, 1985.
[CrossRef]

1970 (1)

B. Kernighan, S. Lin, “An efficient heuristic procedure for partitioning graphs,” Bell Syst. Tech. J., vol. 29, pp. 291–307, 1970.
[CrossRef]

1964 (1)

P. Baran, “On distributed communications networks,” IEEE Trans. Commun., vol. 12, no. 1, pp. 1–9, Mar. 1964.
[CrossRef]

Baran, P.

P. Baran, “On distributed communications networks,” IEEE Trans. Commun., vol. 12, no. 1, pp. 1–9, Mar. 1964.
[CrossRef]

Bar-Ilan, J.

J. Bar-Ilan, G. Kortsarz, D. Peleg, “How to allocate network centers,” J. Algorithms, vol. 15, pp. 385–415, 1993.
[CrossRef]

Baroni, S.

S. Baroni, P. Bayvel, “Wavelength requirements in arbitrary connected wavelength-routed optical networks,” J. Lightwave Technol, vol. 15, no. 2, pp. 242–251, Feb. 1997.
[CrossRef]

Bayvel, P.

S. Baroni, P. Bayvel, “Wavelength requirements in arbitrary connected wavelength-routed optical networks,” J. Lightwave Technol, vol. 15, no. 2, pp. 242–251, Feb. 1997.
[CrossRef]

Calinescu, G.

P.-J. Wan, G. Calinescu, L. Liu, O. Frieder, “Grooming of arbitrary traffic in SONET/WDM BLSRs,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1995–2003, 2000.
[CrossRef]

Chen, B.

B. Chen, G. N. Rouskas, R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol. 16, no. 5, pp. 1226–1238, Oct. 2008.
[CrossRef]

B. Chen, G. N. Rouskas, R. Dutta, “Traffic grooming in WDM ring networks to minimize the maximum electronic port cost,” Opt. Switching Networking, vol. 2, no. 1, pp. 1–18, May 2005.
[CrossRef]

B. Chen, “Hierarchical traffic grooming in large-scale WDM networks,” Ph.D. dissertation, North Carolina State University, Raleigh, NC, August 2005.

Chlamtac, I.

I. Chlamtac, A. Ganz, G. Karmi, “Lightpath communications: an approach to high bandwidth optical WANS,” IEEE Trans. Commun., vol. 40, no. 7, pp. 1171–1182, July 1992.
[CrossRef]

Choi, H.

H. Choi, D. B. Szyld, “Application of threshold partitioning of sparse matrices to Markov chains,” in Proc. of the IEEE Int. Computer Performance and Dependability Symp., 1996, pp. 158–165.

Chow, T. Y.

V. R. Konda, 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, Dallas, TX, 2001, pp. 218–221.
[CrossRef]

Clapp, G.

M. Esfandiari, S. Gloeckle, A. Zolfagheri, G. Clapp, J. Gannett, H. Kobrinski, V. Poudyal, R. Skoog, “Improved metro network design by grooming and aggregation of STS-1 demands into OC-192/OC-48 lightpaths,” in The Nat. Fiber Optic Engineers Conf. (NFOEC) 2003, Orlando, FL, 2003.

Ding, Z.

Z. Ding, M. Hamdi, “Clustering techniques for traffic grooming in optical WDM mesh networks,” in 2002 IEEE Global Telecommunications Conf., GLOBECOM 2002, vol. 3, 2002, pp. 2711–2715.

Dutta, R.

B. Chen, G. N. Rouskas, R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol. 16, no. 5, pp. 1226–1238, Oct. 2008.
[CrossRef]

B. Chen, G. N. Rouskas, R. Dutta, “Traffic grooming in WDM ring networks to minimize the maximum electronic port cost,” Opt. Switching Networking, vol. 2, no. 1, pp. 1–18, May 2005.
[CrossRef]

R. Dutta, G. N. Rouskas, “On optimal traffic grooming in WDM rings,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 110–121, Jan. 2002.
[CrossRef]

R. Dutta, G. N. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network, vol. 16, no. 6, pp. 46–56, Nov./Dec. 2002.
[CrossRef]

Esfandiari, M.

M. Esfandiari, S. Gloeckle, A. Zolfagheri, G. Clapp, J. Gannett, H. Kobrinski, V. Poudyal, R. Skoog, “Improved metro network design by grooming and aggregation of STS-1 demands into OC-192/OC-48 lightpaths,” in The Nat. Fiber Optic Engineers Conf. (NFOEC) 2003, Orlando, FL, 2003.

Frieder, O.

P.-J. Wan, G. Calinescu, L. Liu, O. Frieder, “Grooming of arbitrary traffic in SONET/WDM BLSRs,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1995–2003, 2000.
[CrossRef]

Gannett, J.

M. Esfandiari, S. Gloeckle, A. Zolfagheri, G. Clapp, J. Gannett, H. Kobrinski, V. Poudyal, R. Skoog, “Improved metro network design by grooming and aggregation of STS-1 demands into OC-192/OC-48 lightpaths,” in The Nat. Fiber Optic Engineers Conf. (NFOEC) 2003, Orlando, FL, 2003.

Ganz, A.

I. Chlamtac, A. Ganz, G. Karmi, “Lightpath communications: an approach to high bandwidth optical WANS,” IEEE Trans. Commun., vol. 40, no. 7, pp. 1171–1182, July 1992.
[CrossRef]

Gerstel, O.

O. Gerstel, R. Ramaswami, G. Sasaki, “Cost-effective traffic grooming in WDM rings,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 618–630, Oct. 2000.
[CrossRef]

Gloeckle, S.

M. Esfandiari, S. Gloeckle, A. Zolfagheri, G. Clapp, J. Gannett, H. Kobrinski, V. Poudyal, R. Skoog, “Improved metro network design by grooming and aggregation of STS-1 demands into OC-192/OC-48 lightpaths,” in The Nat. Fiber Optic Engineers Conf. (NFOEC) 2003, Orlando, FL, 2003.

Gonzalez, T.

T. Gonzalez, “Clustering to minimize the maximum inter-cluster distance,” Theoret. Comput. Sci., vol. 38, pp. 293–306, 1985.
[CrossRef]

Hamdi, M.

Z. Ding, M. Hamdi, “Clustering techniques for traffic grooming in optical WDM mesh networks,” in 2002 IEEE Global Telecommunications Conf., GLOBECOM 2002, vol. 3, 2002, pp. 2711–2715.

Hartigan, J. A.

J. A. Hartigan, Clustering Algorithms, New York: Wiley, 1975.

Hendrickson, B.

B. Hendrickson, R. Leland, “The CHACO user’s guide,” Sandia National Laboratories, Albuquerque, NM, Tech. Rep. SAND95–2344, July 1995.

Hochbaum, D.

D. Hochbaum, D. Shmoys, “A unified approach to approximation algorithms for bottleneck problems,” J. ACM, vol. 33, pp. 533–550, 1986.
[CrossRef]

D. Hochbaum, D. Shmoys, “A best possible heuristic for the k-center problem,” Math. Op. Res., vol. 10, pp. 180–184, 1985.
[CrossRef]

Hu, J.

J. Hu, B. Leida, “Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks,” Proc. of the IEEE INFOCOM 2004, the 23rd Annu. Joint Conf. of the IEEE Computer and Communications Societies, Hong Kong, 2004, vol. 1, pp. 495–501.

Jia, X.

D. Li, Z. Sun, X. Jia, K. Makki, “Traffic grooming on general topology WDM networks,” IEE Proc.–Commun., vol. 150, no. 3, pp. 197–201, June 2003.
[CrossRef]

Karmi, G.

I. Chlamtac, A. Ganz, G. Karmi, “Lightpath communications: an approach to high bandwidth optical WANS,” IEEE Trans. Commun., vol. 40, no. 7, pp. 1171–1182, July 1992.
[CrossRef]

Karypis, G.

K. Schloegel, G. Karypis, V. Kumar, “A new algorithm for multi-objective graph partitioning,” Department of Computer Science, University of Minnesota, Tech. Rep. 99–003, Sept. 1999.

Kernighan, B.

B. Kernighan, S. Lin, “An efficient heuristic procedure for partitioning graphs,” Bell Syst. Tech. J., vol. 29, pp. 291–307, 1970.
[CrossRef]

Kobrinski, H.

M. Esfandiari, S. Gloeckle, A. Zolfagheri, G. Clapp, J. Gannett, H. Kobrinski, V. Poudyal, R. Skoog, “Improved metro network design by grooming and aggregation of STS-1 demands into OC-192/OC-48 lightpaths,” in The Nat. Fiber Optic Engineers Conf. (NFOEC) 2003, Orlando, FL, 2003.

Konda, V. R.

V. R. Konda, 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, Dallas, TX, 2001, pp. 218–221.
[CrossRef]

Kortsarz, G.

J. Bar-Ilan, G. Kortsarz, D. Peleg, “How to allocate network centers,” J. Algorithms, vol. 15, pp. 385–415, 1993.
[CrossRef]

Kumar, V.

K. Schloegel, G. Karypis, V. Kumar, “A new algorithm for multi-objective graph partitioning,” Department of Computer Science, University of Minnesota, Tech. Rep. 99–003, Sept. 1999.

Lee, C.

C. Lee, E. K. Park, “A genetic algorithm for traffic grooming in all-optical mesh networks,” in 2002 IEEE Int. Conf. on Systems, Man and Cybernetics, 2002, vol. 7.

Leida, B.

J. Hu, B. Leida, “Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks,” Proc. of the IEEE INFOCOM 2004, the 23rd Annu. Joint Conf. of the IEEE Computer and Communications Societies, Hong Kong, 2004, vol. 1, pp. 495–501.

Leland, R.

B. Hendrickson, R. Leland, “The CHACO user’s guide,” Sandia National Laboratories, Albuquerque, NM, Tech. Rep. SAND95–2344, July 1995.

Li, D.

D. Li, Z. Sun, X. Jia, K. Makki, “Traffic grooming on general topology WDM networks,” IEE Proc.–Commun., vol. 150, no. 3, pp. 197–201, June 2003.
[CrossRef]

Lin, S.

B. Kernighan, S. Lin, “An efficient heuristic procedure for partitioning graphs,” Bell Syst. Tech. J., vol. 29, pp. 291–307, 1970.
[CrossRef]

Liu, L.

P.-J. Wan, G. Calinescu, L. Liu, O. Frieder, “Grooming of arbitrary traffic in SONET/WDM BLSRs,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1995–2003, 2000.
[CrossRef]

Makki, K.

D. Li, Z. Sun, X. Jia, K. Makki, “Traffic grooming on general topology WDM networks,” IEE Proc.–Commun., vol. 150, no. 3, pp. 197–201, June 2003.
[CrossRef]

Mateus, G. R.

Z. K. G. Patrocínio, G. R. Mateus, “A Lagrangian-based heuristic for traffic grooming in WDM optical networks,” in IEEE Global Telecommunications Conf., 2003. GLOBECOM '03., 2003, vol. 5, pp. 2767–2771.
[CrossRef]

Mukherjee, B.

H. Zhu, H. Zang, K. Zhu, 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.
[CrossRef]

Park, E. K.

C. Lee, E. K. Park, “A genetic algorithm for traffic grooming in all-optical mesh networks,” in 2002 IEEE Int. Conf. on Systems, Man and Cybernetics, 2002, vol. 7.

Patrocínio, Z. K. G.

Z. K. G. Patrocínio, G. R. Mateus, “A Lagrangian-based heuristic for traffic grooming in WDM optical networks,” in IEEE Global Telecommunications Conf., 2003. GLOBECOM '03., 2003, vol. 5, pp. 2767–2771.
[CrossRef]

Peleg, D.

J. Bar-Ilan, G. Kortsarz, D. Peleg, “How to allocate network centers,” J. Algorithms, vol. 15, pp. 385–415, 1993.
[CrossRef]

Poudyal, V.

M. Esfandiari, S. Gloeckle, A. Zolfagheri, G. Clapp, J. Gannett, H. Kobrinski, V. Poudyal, R. Skoog, “Improved metro network design by grooming and aggregation of STS-1 demands into OC-192/OC-48 lightpaths,” in The Nat. Fiber Optic Engineers Conf. (NFOEC) 2003, Orlando, FL, 2003.

Ramaswami, R.

O. Gerstel, R. Ramaswami, G. Sasaki, “Cost-effective traffic grooming in WDM rings,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 618–630, Oct. 2000.
[CrossRef]

Rouskas, G. N.

B. Chen, G. N. Rouskas, R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol. 16, no. 5, pp. 1226–1238, Oct. 2008.
[CrossRef]

B. Chen, G. N. Rouskas, R. Dutta, “Traffic grooming in WDM ring networks to minimize the maximum electronic port cost,” Opt. Switching Networking, vol. 2, no. 1, pp. 1–18, May 2005.
[CrossRef]

R. Dutta, G. N. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network, vol. 16, no. 6, pp. 46–56, Nov./Dec. 2002.
[CrossRef]

R. Dutta, G. N. Rouskas, “On optimal traffic grooming in WDM rings,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 110–121, Jan. 2002.
[CrossRef]

Sasaki, G.

O. Gerstel, R. Ramaswami, G. Sasaki, “Cost-effective traffic grooming in WDM rings,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 618–630, Oct. 2000.
[CrossRef]

Schloegel, K.

K. Schloegel, G. Karypis, V. Kumar, “A new algorithm for multi-objective graph partitioning,” Department of Computer Science, University of Minnesota, Tech. Rep. 99–003, Sept. 1999.

Shmoys, D.

D. Hochbaum, D. Shmoys, “A unified approach to approximation algorithms for bottleneck problems,” J. ACM, vol. 33, pp. 533–550, 1986.
[CrossRef]

D. Hochbaum, D. Shmoys, “A best possible heuristic for the k-center problem,” Math. Op. Res., vol. 10, pp. 180–184, 1985.
[CrossRef]

Shmoys, D. B.

D. B. Shmoys, “Approximation algorithms for facility location problems,” in Approximation Algorithms for Combinatorial Optimization: Proc. Third Int. Workshop, APPROX 2000, Saarbrücken, Germany, 2000, vol. 1913, pp. 27–32.

Siregar, H.

H. Siregar, H. Takagi, Y. Zhang, “Efficient routing and wavelength assignment in wavelength-routed optical networks,” Proc. 7th Asia-Pacific Network Operations and Management Symp., Fukuoka, Japan, 2003, pp. 116–127.

Skoog, R.

M. Esfandiari, S. Gloeckle, A. Zolfagheri, G. Clapp, J. Gannett, H. Kobrinski, V. Poudyal, R. Skoog, “Improved metro network design by grooming and aggregation of STS-1 demands into OC-192/OC-48 lightpaths,” in The Nat. Fiber Optic Engineers Conf. (NFOEC) 2003, Orlando, FL, 2003.

Sun, Z.

D. Li, Z. Sun, X. Jia, K. Makki, “Traffic grooming on general topology WDM networks,” IEE Proc.–Commun., vol. 150, no. 3, pp. 197–201, June 2003.
[CrossRef]

Szyld, D. B.

H. Choi, D. B. Szyld, “Application of threshold partitioning of sparse matrices to Markov chains,” in Proc. of the IEEE Int. Computer Performance and Dependability Symp., 1996, pp. 158–165.

Takagi, H.

H. Siregar, H. Takagi, Y. Zhang, “Efficient routing and wavelength assignment in wavelength-routed optical networks,” Proc. 7th Asia-Pacific Network Operations and Management Symp., Fukuoka, Japan, 2003, pp. 116–127.

Thorup, M.

M. Thorup, “Quick k-median, k-center, and facility location for sparse graphs,” Automata, Languages and Programming: Proc. of the 28th Int. Colloquium, ICALP 2001, Crete, Greece, 2001, vol. 2076, pp. 249–260.

Wan, P.-J.

P.-J. Wan, G. Calinescu, L. Liu, O. Frieder, “Grooming of arbitrary traffic in SONET/WDM BLSRs,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1995–2003, 2000.
[CrossRef]

Zang, H.

H. Zhu, H. Zang, K. Zhu, 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.
[CrossRef]

Zhang, Y.

H. Siregar, H. Takagi, Y. Zhang, “Efficient routing and wavelength assignment in wavelength-routed optical networks,” Proc. 7th Asia-Pacific Network Operations and Management Symp., Fukuoka, Japan, 2003, pp. 116–127.

Zhu, H.

H. Zhu, H. Zang, K. Zhu, 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.
[CrossRef]

Zhu, K.

H. Zhu, H. Zang, K. Zhu, 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.
[CrossRef]

Zolfagheri, A.

M. Esfandiari, S. Gloeckle, A. Zolfagheri, G. Clapp, J. Gannett, H. Kobrinski, V. Poudyal, R. Skoog, “Improved metro network design by grooming and aggregation of STS-1 demands into OC-192/OC-48 lightpaths,” in The Nat. Fiber Optic Engineers Conf. (NFOEC) 2003, Orlando, FL, 2003.

Bell Syst. Tech. J. (1)

B. Kernighan, S. Lin, “An efficient heuristic procedure for partitioning graphs,” Bell Syst. Tech. J., vol. 29, pp. 291–307, 1970.
[CrossRef]

IEE Proc.–Commun. (1)

D. Li, Z. Sun, X. Jia, K. Makki, “Traffic grooming on general topology WDM networks,” IEE Proc.–Commun., vol. 150, no. 3, pp. 197–201, June 2003.
[CrossRef]

IEEE J. Sel. Areas Commun. (2)

R. Dutta, G. N. Rouskas, “On optimal traffic grooming in WDM rings,” IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 110–121, Jan. 2002.
[CrossRef]

P.-J. Wan, G. Calinescu, L. Liu, O. Frieder, “Grooming of arbitrary traffic in SONET/WDM BLSRs,” IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1995–2003, 2000.
[CrossRef]

IEEE Network (1)

R. Dutta, G. N. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network, vol. 16, no. 6, pp. 46–56, Nov./Dec. 2002.
[CrossRef]

IEEE Trans. Commun. (2)

I. Chlamtac, A. Ganz, G. Karmi, “Lightpath communications: an approach to high bandwidth optical WANS,” IEEE Trans. Commun., vol. 40, no. 7, pp. 1171–1182, July 1992.
[CrossRef]

P. Baran, “On distributed communications networks,” IEEE Trans. Commun., vol. 12, no. 1, pp. 1–9, Mar. 1964.
[CrossRef]

IEEE/ACM Trans. Netw. (3)

B. Chen, G. N. Rouskas, R. Dutta, “On hierarchical traffic grooming in WDM networks,” IEEE/ACM Trans. Netw., vol. 16, no. 5, pp. 1226–1238, Oct. 2008.
[CrossRef]

O. Gerstel, R. Ramaswami, G. Sasaki, “Cost-effective traffic grooming in WDM rings,” IEEE/ACM Trans. Netw., vol. 8, no. 5, pp. 618–630, Oct. 2000.
[CrossRef]

H. Zhu, H. Zang, K. Zhu, 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.
[CrossRef]

J. ACM (1)

D. Hochbaum, D. Shmoys, “A unified approach to approximation algorithms for bottleneck problems,” J. ACM, vol. 33, pp. 533–550, 1986.
[CrossRef]

J. Algorithms (1)

J. Bar-Ilan, G. Kortsarz, D. Peleg, “How to allocate network centers,” J. Algorithms, vol. 15, pp. 385–415, 1993.
[CrossRef]

J. Lightwave Technol (1)

S. Baroni, P. Bayvel, “Wavelength requirements in arbitrary connected wavelength-routed optical networks,” J. Lightwave Technol, vol. 15, no. 2, pp. 242–251, Feb. 1997.
[CrossRef]

Math. Op. Res. (1)

D. Hochbaum, D. Shmoys, “A best possible heuristic for the k-center problem,” Math. Op. Res., vol. 10, pp. 180–184, 1985.
[CrossRef]

Opt. Switching Networking (1)

B. Chen, G. N. Rouskas, R. Dutta, “Traffic grooming in WDM ring networks to minimize the maximum electronic port cost,” Opt. Switching Networking, vol. 2, no. 1, pp. 1–18, May 2005.
[CrossRef]

Theoret. Comput. Sci. (1)

T. Gonzalez, “Clustering to minimize the maximum inter-cluster distance,” Theoret. Comput. Sci., vol. 38, pp. 293–306, 1985.
[CrossRef]

Other (14)

D. B. Shmoys, “Approximation algorithms for facility location problems,” in Approximation Algorithms for Combinatorial Optimization: Proc. Third Int. Workshop, APPROX 2000, Saarbrücken, Germany, 2000, vol. 1913, pp. 27–32.

M. Thorup, “Quick k-median, k-center, and facility location for sparse graphs,” Automata, Languages and Programming: Proc. of the 28th Int. Colloquium, ICALP 2001, Crete, Greece, 2001, vol. 2076, pp. 249–260.

M. Esfandiari, S. Gloeckle, A. Zolfagheri, G. Clapp, J. Gannett, H. Kobrinski, V. Poudyal, R. Skoog, “Improved metro network design by grooming and aggregation of STS-1 demands into OC-192/OC-48 lightpaths,” in The Nat. Fiber Optic Engineers Conf. (NFOEC) 2003, Orlando, FL, 2003.

Z. Ding, M. Hamdi, “Clustering techniques for traffic grooming in optical WDM mesh networks,” in 2002 IEEE Global Telecommunications Conf., GLOBECOM 2002, vol. 3, 2002, pp. 2711–2715.

B. Hendrickson, R. Leland, “The CHACO user’s guide,” Sandia National Laboratories, Albuquerque, NM, Tech. Rep. SAND95–2344, July 1995.

V. R. Konda, 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, Dallas, TX, 2001, pp. 218–221.
[CrossRef]

B. Chen, “Hierarchical traffic grooming in large-scale WDM networks,” Ph.D. dissertation, North Carolina State University, Raleigh, NC, August 2005.

H. Siregar, H. Takagi, Y. Zhang, “Efficient routing and wavelength assignment in wavelength-routed optical networks,” Proc. 7th Asia-Pacific Network Operations and Management Symp., Fukuoka, Japan, 2003, pp. 116–127.

J. A. Hartigan, Clustering Algorithms, New York: Wiley, 1975.

H. Choi, D. B. Szyld, “Application of threshold partitioning of sparse matrices to Markov chains,” in Proc. of the IEEE Int. Computer Performance and Dependability Symp., 1996, pp. 158–165.

K. Schloegel, G. Karypis, V. Kumar, “A new algorithm for multi-objective graph partitioning,” Department of Computer Science, University of Minnesota, Tech. Rep. 99–003, Sept. 1999.

J. Hu, B. Leida, “Traffic grooming, routing, and wavelength assignment in optical WDM mesh networks,” Proc. of the IEEE INFOCOM 2004, the 23rd Annu. Joint Conf. of the IEEE Computer and Communications Societies, Hong Kong, 2004, vol. 1, pp. 495–501.

Z. K. G. Patrocínio, G. R. Mateus, “A Lagrangian-based heuristic for traffic grooming in WDM optical networks,” in IEEE Global Telecommunications Conf., 2003. GLOBECOM '03., 2003, vol. 5, pp. 2767–2771.
[CrossRef]

C. Lee, E. K. Park, “A genetic algorithm for traffic grooming in all-optical mesh networks,” in 2002 IEEE Int. Conf. on Systems, Man and Cybernetics, 2002, vol. 7.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (11)

Fig. 1
Fig. 1

32-node WDM network, partitioned into eight first-level clusters B 1 , , B 8 ; hub nodes are blue squares and form a (logical) second-level cluster with hub 11.

Fig. 2
Fig. 2

Hierarchical logical topology algorithm for mesh networks.

Fig. 3
Fig. 3

Clustering algorithm for mesh networks.

Fig. 4
Fig. 4

Lightpath comparison, falling pattern, 47-node network.

Fig. 5
Fig. 5

Wavelength comparison, falling pattern, 47-node network.

Fig. 6
Fig. 6

Lightpath comparison, rising pattern, 47-node network.

Fig. 7
Fig. 7

Wavelength comparison, rising pattern, 47-node network.

Fig. 8
Fig. 8

Lightpath comparison, random pattern, 128-node network.

Fig. 9
Fig. 9

Wavelength comparison, random pattern, 128-node network.

Fig. 10
Fig. 10

Lightpath comparison, rising pattern, 128-node network.

Fig. 11
Fig. 11

Wavelength comparison, rising pattern, 128-node network.

Equations (5)

Equations on this page are rendered with MathJax. Learn more.

t i ( s d ) = { t r ( s d ) s h i , d h i t r ( s d ) + x B i t r ( s x ) d = h i t r ( s d ) + x B i t r ( x d ) s = h i } .
t inter ( h i h j ) = s B i , d B j t r ( s , d ) , i , j = 1 , , m , i j .
F l = max ( s d t ( s d ) C , d s t ( s d ) C ) .
d b s d C d t ( s d ) s .
s b s d C s t ( s d ) d .