OSA's Digital Library

Journal of Optical Communications and Networking

Journal of Optical Communications and Networking

  • Editor: Keren Bergman
  • Vol. 7, Iss. 10 — Oct. 1, 2008
  • pp: 895–904

Maximum throughput traffic grooming in optical networks

Yong Wang and Qian-Ping Gu  »View Author Affiliations

Journal of Optical Networking, Vol. 7, Issue 10, pp. 895-904 (2008)

View Full Text Article

Acrobat PDF (143 KB)

Browse Journals / Lookup Meetings

Browse by Journal and Year


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools



In synchronous optical networks (SONETs) and WDM networks, low-rate traffic demands are usually multiplexed to share a high-speed wavelength channel. The multiplexing-demultiplexing is known as traffic grooming and is performed by SONET add-drop multiplexers (SADM). The grooming factor, denoted by k, is the maximum number of low-rate traffic demands that can be multiplexed into one wavelength channel. SADMs are expensive, and thus an important optimization problem for traffic grooming is to maximize the number of accommodated traffic demands subject to a given number of SADMs. We focus on the unidirectional path-switched ring (UPSR) networks with unitary duplex traffic demands. We assume that each network node is equipped with a limited number L of SADMs, and our objective is to maximize the number of accommodated traffic demands in a given set. We prove the NP-hardness of this maximum throughput traffic grooming problem and propose a (k+1)-approximation algorithm. Extensive simulations are conducted to validate the performance of the algorithm. We also study the all-to-all traffic pattern for the maximum throughput traffic grooming problem and propose an algorithm that accommodates at least (nL⌊k⌋)/2 demands for a UPSR with n nodes. We also prove that any optimal solution can accommodate at most (nLk)/2 demands. Thus the solution of our algorithm is at most a constant factor (approximately 2) away from the optimum.

© 2008 Optical Society of America

OCIS Codes
(060.4254) Fiber optics and optical communications : Networks, combinatorial network design
(060.4256) Fiber optics and optical communications : Networks, network optimization

ToC Category:
Research Papers

Original Manuscript: January 8, 2008
Revised Manuscript: July 14, 2008
Manuscript Accepted: September 5, 2008
Published: September 30, 2008

Yong Wang and Qian-Ping Gu, "Maximum throughput traffic grooming in optical networks," J. Opt. Netw. 7, 895-904 (2008)

Sort:  Author  |  Year  |  Journal  |  Reset


  1. R. Dutta and G. N. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network 16(6), 46-56 (2002).
  2. E. Modiano and P. Lin, “Traffic grooming in WDM networks,” IEEE Commun. Mag. 39(7), 124-129 (2001). [CrossRef]
  3. A. K. Somani, “Survivable traffic grooming in WDM networks,” in Proceedings of the International Conference on Broad-Band Optical Fibre Communication Technology (BBOFCT'01) (2001), pp. 17-45.
  4. K. Zhu and B. Mukherjee, “A review of traffic grooming in WDM optical networks: architectures and challenges,” Opt. Networks Mag. 4(2), 55-64 (2003).
  5. O. Gerstel, P. Lin, and G. Sasaki, “Combined WDM and SONET network design,” in INFOCOM '99 Eighteenth Annual Joint Conference of the IEEE Communications Societies (IEEE, 1999), pp. 734-743.
  6. J.-C. Bermond and D. Coudert, “Traffic grooming in unidirectional WDM ring networks using design theory,” in IEEE International Conference on Communications (IEEE, 2003), pp. 1995-2003.
  7. N. Brauner, Y. Crama, G. Finke, P. Lemaire, and C. Wynants, “Approximation algorithms for the design of SDH/SONET networks,” RAIRO Oper. Res. 37, 235-247 (2003).
  8. O. Goldschmidt, D. S. Hochbaum, A. Levin, and E. V. Olinick, “The SONET edge-partition problem,” Networks 41, 13-23 (2003).
  9. Y. Wang and Q.-P. Gu, “Grooming of symmetric traffic in unidirectional SONET/WDM rings,” in IEEE International Conference on Communications (IEEE, 2006), pp. 2407-2414.
  10. Y. Wang and Q.-P. Gu, “Efficient algorithms for traffic grooming in SONET/WDM networks,” in International Conference on Parallel Processing (IEEE, 2006), pp. 355-364.
  11. S. Sankaranarayanan, S. Subramaniam, H. Choi, and H.-A. Choi, “Survivable traffic grooming in WDM optical networks,” J. Commun. Network 9, 93-104 (2007).
  12. J.-C. Bermond and S. Ceroi, “Minimizing SONET ADMs in unidirectional WDM rings with grooming ratio 3,” Networks 41, 83-86 (2003).
  13. J.-C. Bermond, C. J. Colbourn, A. Ling, and M.-L. Yu, “Grooming in unidirectional rings: k4−e designs,” Discrete Math. 284, 57-62 (2004). [CrossRef]
  14. J.-C. Bermond, D. Coudert, and X. Muñoz, “Traffic grooming in unidirectional WDM ring networks: the all-to-all unitary case,” in Proceedings of the 7th IFIP Working Conference on Optical Network Design and Modelling (2003), pp. 1135-1153.
  15. J. Q. Hu, “Optimal traffic grooming for wavelength-division-multiplexing rings with all-to-all uniform traffic,” J. Opt. Netw. 1, 32-42 (2002).
  16. E. Modiano and A. Chiu, “Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks,” J. Lightwave Technol. 18, 2-12 (2000). [CrossRef]
  17. X. Zhang and C. Qiao, “An effective and comprehensive approach for traffic grooming and wavelength assignment in SONET/WDM rings,” IEEE/ACM Trans. Netw. 8, 608-617 (2000). [CrossRef]
  18. D. B. West, Introduction to Graph Theory (Prentice Hall, 1996).
  19. H. N. Gabow, “An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems,” in Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing (Association for Computing Machinery, 1983), pp. 448-456.
  20. S. L. Hakimi and O. Kariv, “On a generalization of edge-coloring in graphs,” J. Graph Theory 10, 139-154 (1986). [CrossRef]
  21. T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms (McGraw-Hill, 1990).
  22. I. Holyer, “The NP-completeness of some edge-partition problems,” SIAM J. Comput. 10, 713-717 (1981). [CrossRef]
  23. S. Fiorini and R. J. Wilson, Edge-colourings of Graphs, Vol. 16 of Research Notes in Mathematics (Pitman, 1977).

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.

CrossCheck Deposited