Abstract

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

PDF Article

References

  • View by:
  • |
  • |
  • |

  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).

2007 (1)

S. Sankaranarayanan, S. Subramaniam, H. Choi, and H.-A. Choi, “Survivable traffic grooming in WDM optical networks,” J. Commun. Network 9, 93-104 (2007).

2004 (1)

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]

2003 (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).

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).

O. Goldschmidt, D. S. Hochbaum, A. Levin, and E. V. Olinick, “The SONET edge-partition problem,” Networks 41, 13-23 (2003).

J.-C. Bermond and S. Ceroi, “Minimizing SONET ADMs in unidirectional WDM rings with grooming ratio 3,” Networks 41, 83-86 (2003).

2002 (2)

R. Dutta and G. N. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network 16(6), 46-56 (2002).

J. Q. Hu, “Optimal traffic grooming for wavelength-division-multiplexing rings with all-to-all uniform traffic,” J. Opt. Netw. 1, 32-42 (2002).

2001 (1)

E. Modiano and P. Lin, “Traffic grooming in WDM networks,” IEEE Commun. Mag. 39(7), 124-129 (2001).
[CrossRef]

2000 (2)

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]

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]

1986 (1)

S. L. Hakimi and O. Kariv, “On a generalization of edge-coloring in graphs,” J. Graph Theory 10, 139-154 (1986).
[CrossRef]

1981 (1)

I. Holyer, “The NP-completeness of some edge-partition problems,” SIAM J. Comput. 10, 713-717 (1981).
[CrossRef]

Bermond, J.-C.

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]

J.-C. Bermond and S. Ceroi, “Minimizing SONET ADMs in unidirectional WDM rings with grooming ratio 3,” Networks 41, 83-86 (2003).

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.

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.

Brauner, N.

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).

Ceroi, S.

J.-C. Bermond and S. Ceroi, “Minimizing SONET ADMs in unidirectional WDM rings with grooming ratio 3,” Networks 41, 83-86 (2003).

Chiu, A.

Choi, H.

S. Sankaranarayanan, S. Subramaniam, H. Choi, and H.-A. Choi, “Survivable traffic grooming in WDM optical networks,” J. Commun. Network 9, 93-104 (2007).

Choi, H.-A.

S. Sankaranarayanan, S. Subramaniam, H. Choi, and H.-A. Choi, “Survivable traffic grooming in WDM optical networks,” J. Commun. Network 9, 93-104 (2007).

Colbourn, C. J.

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]

Cormen, T.

T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms (McGraw-Hill, 1990).

Coudert, D.

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.

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.

Crama, Y.

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).

Dutta, R.

R. Dutta and G. N. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network 16(6), 46-56 (2002).

Finke, G.

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).

Fiorini, S.

S. Fiorini and R. J. Wilson, Edge-colourings of Graphs, Vol. 16 of Research Notes in Mathematics (Pitman, 1977).

Gabow, H. N.

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.

Gerstel, O.

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.

Goldschmidt, O.

O. Goldschmidt, D. S. Hochbaum, A. Levin, and E. V. Olinick, “The SONET edge-partition problem,” Networks 41, 13-23 (2003).

Gu, Q.-P.

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.

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.

Hakimi, S. L.

S. L. Hakimi and O. Kariv, “On a generalization of edge-coloring in graphs,” J. Graph Theory 10, 139-154 (1986).
[CrossRef]

Hochbaum, D. S.

O. Goldschmidt, D. S. Hochbaum, A. Levin, and E. V. Olinick, “The SONET edge-partition problem,” Networks 41, 13-23 (2003).

Holyer, I.

I. Holyer, “The NP-completeness of some edge-partition problems,” SIAM J. Comput. 10, 713-717 (1981).
[CrossRef]

Hu, J. Q.

Kariv, O.

S. L. Hakimi and O. Kariv, “On a generalization of edge-coloring in graphs,” J. Graph Theory 10, 139-154 (1986).
[CrossRef]

Leiserson, C.

T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms (McGraw-Hill, 1990).

Lemaire, P.

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).

Levin, A.

O. Goldschmidt, D. S. Hochbaum, A. Levin, and E. V. Olinick, “The SONET edge-partition problem,” Networks 41, 13-23 (2003).

Lin, P.

E. Modiano and P. Lin, “Traffic grooming in WDM networks,” IEEE Commun. Mag. 39(7), 124-129 (2001).
[CrossRef]

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.

Ling, A.

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]

Modiano, E.

Mukherjee, B.

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).

Muñoz, X.

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.

Olinick, E. V.

O. Goldschmidt, D. S. Hochbaum, A. Levin, and E. V. Olinick, “The SONET edge-partition problem,” Networks 41, 13-23 (2003).

Qiao, C.

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]

Rivest, R.

T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms (McGraw-Hill, 1990).

Rouskas, G. N.

R. Dutta and G. N. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network 16(6), 46-56 (2002).

Sankaranarayanan, S.

S. Sankaranarayanan, S. Subramaniam, H. Choi, and H.-A. Choi, “Survivable traffic grooming in WDM optical networks,” J. Commun. Network 9, 93-104 (2007).

Sasaki, G.

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.

Somani, A. K.

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.

Subramaniam, S.

S. Sankaranarayanan, S. Subramaniam, H. Choi, and H.-A. Choi, “Survivable traffic grooming in WDM optical networks,” J. Commun. Network 9, 93-104 (2007).

Wang, Y.

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.

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.

West, D. B.

D. B. West, Introduction to Graph Theory (Prentice Hall, 1996).

Wilson, R. J.

S. Fiorini and R. J. Wilson, Edge-colourings of Graphs, Vol. 16 of Research Notes in Mathematics (Pitman, 1977).

Wynants, C.

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).

Yu, M.-L.

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]

Zhang, X.

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]

Zhu, K.

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).

Discrete Math. (1)

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]

IEEE Commun. Mag. (1)

E. Modiano and P. Lin, “Traffic grooming in WDM networks,” IEEE Commun. Mag. 39(7), 124-129 (2001).
[CrossRef]

IEEE Network (1)

R. Dutta and G. N. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network 16(6), 46-56 (2002).

IEEE/ACM Trans. Netw. (1)

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]

J. Commun. Network (1)

S. Sankaranarayanan, S. Subramaniam, H. Choi, and H.-A. Choi, “Survivable traffic grooming in WDM optical networks,” J. Commun. Network 9, 93-104 (2007).

J. Graph Theory (1)

S. L. Hakimi and O. Kariv, “On a generalization of edge-coloring in graphs,” J. Graph Theory 10, 139-154 (1986).
[CrossRef]

J. Lightwave Technol. (1)

J. Opt. Netw. (1)

Networks (2)

J.-C. Bermond and S. Ceroi, “Minimizing SONET ADMs in unidirectional WDM rings with grooming ratio 3,” Networks 41, 83-86 (2003).

O. Goldschmidt, D. S. Hochbaum, A. Levin, and E. V. Olinick, “The SONET edge-partition problem,” Networks 41, 13-23 (2003).

Opt. Networks Mag. (1)

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).

RAIRO Oper. Res. (1)

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).

SIAM J. Comput. (1)

I. Holyer, “The NP-completeness of some edge-partition problems,” SIAM J. Comput. 10, 713-717 (1981).
[CrossRef]

Other (10)

S. Fiorini and R. J. Wilson, Edge-colourings of Graphs, Vol. 16 of Research Notes in Mathematics (Pitman, 1977).

T. Cormen, C. Leiserson, and R. Rivest, Introduction to Algorithms (McGraw-Hill, 1990).

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.

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.

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.

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.

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.

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.

D. B. West, Introduction to Graph Theory (Prentice Hall, 1996).

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.

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.