## Clustering Methods for Hierarchical Traffic Grooming in Large-Scale Mesh WDM Networks

Journal of Optical Communications and Networking, Vol. 2, Issue 8, pp. 502-514 (2010)

http://dx.doi.org/10.1364/JOCN.2.000502

Enhanced HTML Acrobat PDF (687 KB)

### 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

**OCIS Codes**

(060.1155) Fiber optics and optical communications : All-optical networks

(060.4251) Fiber optics and optical communications : Networks, assignment and routing algorithms

(060.4254) Fiber optics and optical communications : Networks, combinatorial network design

(060.4256) Fiber optics and optical communications : Networks, network optimization

(060.4264) Fiber optics and optical communications : Networks, wavelength assignment

**ToC Category:**

Research Papers

**History**

Original Manuscript: January 21, 2010

Manuscript Accepted: April 2, 2010

Published: July 9, 2010

**Citation**

Bensong Chen, George N. Rouskas, and Rudra Dutta, "Clustering Methods for Hierarchical Traffic Grooming in Large-Scale Mesh WDM Networks," J. Opt. Commun. Netw. **2**, 502-514 (2010)

http://www.opticsinfobase.org/jocn/abstract.cfm?URI=jocn-2-8-502

Sort: Year | Journal | Reset

### References

- 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]
- 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]
- 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]
- 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]
- 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]
- 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]
- 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.
- 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]
- 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]
- 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.
- 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.
- 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]
- 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. Bar-Ilan, G. Kortsarz, D. Peleg, “How to allocate network centers,” J. Algorithms, vol. 15, pp. 385–415, 1993. [CrossRef]
- D. Hochbaum, D. Shmoys, “A unified approach to approximation algorithms for bottleneck problems,” J. ACM, vol. 33, pp. 533–550, 1986. [CrossRef]
- 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.
- 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]
- 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.
- B. Kernighan, S. Lin, “An efficient heuristic procedure for partitioning graphs,” Bell Syst. Tech. J., vol. 29, pp. 291–307, 1970. [CrossRef]
- P. Baran, “On distributed communications networks,” IEEE Trans. Commun., vol. 12, no. 1, pp. 1–9, Mar. 1964. [CrossRef]

## Cited By |
Alert me when this paper is cited |

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

« Previous Article | Next Article »

OSA is a member of CrossRef.