Abstract

Feature Issue on Transmission in Optically Transparent Core Networks

The problem of efficiently designing lightpaths and routing traffic on them in hybrid electro-optic data communication networks so that optical pass-through is maximized and the electronic switching cost is minimized is known as traffic grooming and has been studied extensively. Traffic grooming is known to be an inherently difficult problem. It has been shown to be NP-complete even for path networks, a simple topology in which lightpath wavelength assignment is tractable. In this paper, we explore the borderline between tractability and intractability by considering grooming in unidirectional path networks in which all traffic requests are destined for a single egress node. Whether the complete grooming problem is NP-hard with this restriction is an open question. We show that at least the problem of routing traffic on a given virtual topology to minimize electronic switching (NP-hard for path networks with arbitrary traffic matrices) becomes polynomial on the egress model. We also show that in the egress model, if the capacity constraint is relaxed, the entire problem becomes polynomial. If, in addition, traffic requests are uniform, we provide an explicit combinatorial formula for the optimum solution as well as an algorithm that constructs a routing that achieves this optimum. For the case of finite capacity and unit traffic requests, we show how to polynomially find a feasible solution that is optimal under reasonable assumptions.

© 2007 Optical Society of America

PDF Article

References

  • View by:
  • |
  • |
  • |

  1. O. Gerstel, R. Ramaswami, and G. Sasaki, "Cost effective traffic grooming in WDM rings," IEEE/ACM Trans. Netw. 8, 618-630 (2000).
    [Crossref]
  2. R. Dutta and G. N. Rouskas, "On optimal traffic grooming in WDM rings," IEEE J. Sel. Areas Commun. 20, 110-121 (2002).
  3. K. Zhu and B. Mukherjee, "Traffic grooming in optical WDM mesh networks," IEEE J. Sel. Areas Commun. 20, 122-133 (2002).
  4. X.-Y. Li, L. Liu, P.-J. Wan, and O. Frieder, "Practical traffic grooming scheme for single hub SONET/WDM rings," in Proceedings of 25th Annual IEEE Conference on Local Computer Networks (IEEE, 2000), pp. 556- 564.
  5. O. Gerstel, P. Lin, and G. Sasaki, "Wavelength assignment in WDM rings to minimize system cost instead of number of wavelengths," in INFOCOM '98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE, 1998), Vol. 1, pp. 94-101.
  6. 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]
  7. P. Iyer, "The complexity of traffic grooming in optical path networks with egress traffic," Master's thesis (North Carolina State University, 2003).
  8. E. Modiano and P. Lin, "Traffic grooming in WDM networks," IEEE Commun. Mag. 39, 124-129 (2001).
    [Crossref]
  9. K. Zhu and B. Mukherjee, "A review of traffic grooming in WDM optical networks: architectures and challenges," Opt. Netw. Mag. 4, 55-64 (2003).
  10. R. Dutta and G. Rouskas, "Traffic grooming in WDM networks: past and future," IEEE Netw. 16, 46-56 (2002).
  11. S. Huang and R. Dutta, "Dynamic traffic grooming: the changing role of traffic grooming," IEEE Commun. Surveys Tutorials 9, 32-49 (2007).
  12. R. Dutta, S. Huang, and G. Rouskas, "On optimal traffic grooming in elemental network topologies," in Proceedings of OPTICOMM (2003), pp. 13-24.
  13. P.-J. Wan, G. Calinescu, L. Liu, and O. Frieder, "Grooming of arbitrary traffic in SONET WDM BLSRs," IEEE J. Sel. Areas Commun. 18, 1995-2003 (2000).
    [Crossref]
  14. V. R. Konda and T. Y. Chow, "Algorithm for traffic grooming in optical network to minimize the number of transceivers," in 2001 IEEE Workshop on High Performance Switching and Routing (IEEE, 2001), pp. 218-221.
  15. A. Chiu and E. Modiano, "Reducing electronic multiplexing costs in unidirectional SONET/WDM rings via efficient traffic grooming," in GLOBECOM 98: Global Telecommunications Conference (IEEE, 1998), Vol. 1, pp. 322-327.
  16. P. C. Fishburn, "Interval graphs and interval orders," Discrete Math. 55, 135-149 (1985).
  17. É. Tardos, "A strongly polynomial minimum cost circulation algorithm," Combinatorica 5, 247-255 (1985).
    [Crossref]
  18. R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, 1993).

2007 (1)

S. Huang and R. Dutta, "Dynamic traffic grooming: the changing role of traffic grooming," IEEE Commun. Surveys Tutorials 9, 32-49 (2007).

2003 (1)

K. Zhu and B. Mukherjee, "A review of traffic grooming in WDM optical networks: architectures and challenges," Opt. Netw. Mag. 4, 55-64 (2003).

2002 (3)

R. Dutta and G. Rouskas, "Traffic grooming in WDM networks: past and future," IEEE Netw. 16, 46-56 (2002).

R. Dutta and G. N. Rouskas, "On optimal traffic grooming in WDM rings," IEEE J. Sel. Areas Commun. 20, 110-121 (2002).

K. Zhu and B. Mukherjee, "Traffic grooming in optical WDM mesh networks," IEEE J. Sel. Areas Commun. 20, 122-133 (2002).

2001 (1)

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

2000 (3)

O. Gerstel, R. Ramaswami, and G. Sasaki, "Cost effective traffic grooming in WDM rings," IEEE/ACM Trans. Netw. 8, 618-630 (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]

P.-J. Wan, G. Calinescu, L. Liu, and O. Frieder, "Grooming of arbitrary traffic in SONET WDM BLSRs," IEEE J. Sel. Areas Commun. 18, 1995-2003 (2000).
[Crossref]

1985 (2)

P. C. Fishburn, "Interval graphs and interval orders," Discrete Math. 55, 135-149 (1985).

É. Tardos, "A strongly polynomial minimum cost circulation algorithm," Combinatorica 5, 247-255 (1985).
[Crossref]

Ahuja, R. K.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, 1993).

Calinescu, G.

P.-J. Wan, G. Calinescu, L. Liu, and O. Frieder, "Grooming of arbitrary traffic in SONET WDM BLSRs," IEEE J. Sel. Areas Commun. 18, 1995-2003 (2000).
[Crossref]

Chiu, A.

A. Chiu and E. Modiano, "Reducing electronic multiplexing costs in unidirectional SONET/WDM rings via efficient traffic grooming," in GLOBECOM 98: Global Telecommunications Conference (IEEE, 1998), Vol. 1, pp. 322-327.

Chow, T. Y.

V. R. Konda and T. Y. Chow, "Algorithm for traffic grooming in optical network to minimize the number of transceivers," in 2001 IEEE Workshop on High Performance Switching and Routing (IEEE, 2001), pp. 218-221.

Dutta, R.

S. Huang and R. Dutta, "Dynamic traffic grooming: the changing role of traffic grooming," IEEE Commun. Surveys Tutorials 9, 32-49 (2007).

R. Dutta and G. Rouskas, "Traffic grooming in WDM networks: past and future," IEEE Netw. 16, 46-56 (2002).

R. Dutta and G. N. Rouskas, "On optimal traffic grooming in WDM rings," IEEE J. Sel. Areas Commun. 20, 110-121 (2002).

R. Dutta, S. Huang, and G. Rouskas, "On optimal traffic grooming in elemental network topologies," in Proceedings of OPTICOMM (2003), pp. 13-24.

Fishburn, P. C.

P. C. Fishburn, "Interval graphs and interval orders," Discrete Math. 55, 135-149 (1985).

Frieder, O.

P.-J. Wan, G. Calinescu, L. Liu, and O. Frieder, "Grooming of arbitrary traffic in SONET WDM BLSRs," IEEE J. Sel. Areas Commun. 18, 1995-2003 (2000).
[Crossref]

X.-Y. Li, L. Liu, P.-J. Wan, and O. Frieder, "Practical traffic grooming scheme for single hub SONET/WDM rings," in Proceedings of 25th Annual IEEE Conference on Local Computer Networks (IEEE, 2000), pp. 556- 564.

Gerstel, O.

O. Gerstel, R. Ramaswami, and G. Sasaki, "Cost effective traffic grooming in WDM rings," IEEE/ACM Trans. Netw. 8, 618-630 (2000).
[Crossref]

O. Gerstel, P. Lin, and G. Sasaki, "Wavelength assignment in WDM rings to minimize system cost instead of number of wavelengths," in INFOCOM '98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE, 1998), Vol. 1, pp. 94-101.

Huang, S.

S. Huang and R. Dutta, "Dynamic traffic grooming: the changing role of traffic grooming," IEEE Commun. Surveys Tutorials 9, 32-49 (2007).

R. Dutta, S. Huang, and G. Rouskas, "On optimal traffic grooming in elemental network topologies," in Proceedings of OPTICOMM (2003), pp. 13-24.

Iyer, P.

P. Iyer, "The complexity of traffic grooming in optical path networks with egress traffic," Master's thesis (North Carolina State University, 2003).

Konda, V. R.

V. R. Konda and T. Y. Chow, "Algorithm for traffic grooming in optical network to minimize the number of transceivers," in 2001 IEEE Workshop on High Performance Switching and Routing (IEEE, 2001), pp. 218-221.

Li, X.-Y.

X.-Y. Li, L. Liu, P.-J. Wan, and O. Frieder, "Practical traffic grooming scheme for single hub SONET/WDM rings," in Proceedings of 25th Annual IEEE Conference on Local Computer Networks (IEEE, 2000), pp. 556- 564.

Lin, P.

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

O. Gerstel, P. Lin, and G. Sasaki, "Wavelength assignment in WDM rings to minimize system cost instead of number of wavelengths," in INFOCOM '98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE, 1998), Vol. 1, pp. 94-101.

Liu, L.

P.-J. Wan, G. Calinescu, L. Liu, and O. Frieder, "Grooming of arbitrary traffic in SONET WDM BLSRs," IEEE J. Sel. Areas Commun. 18, 1995-2003 (2000).
[Crossref]

X.-Y. Li, L. Liu, P.-J. Wan, and O. Frieder, "Practical traffic grooming scheme for single hub SONET/WDM rings," in Proceedings of 25th Annual IEEE Conference on Local Computer Networks (IEEE, 2000), pp. 556- 564.

Magnanti, T. L.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, 1993).

Modiano, E.

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

A. Chiu and E. Modiano, "Reducing electronic multiplexing costs in unidirectional SONET/WDM rings via efficient traffic grooming," in GLOBECOM 98: Global Telecommunications Conference (IEEE, 1998), Vol. 1, pp. 322-327.

Mukherjee, B.

K. Zhu and B. Mukherjee, "A review of traffic grooming in WDM optical networks: architectures and challenges," Opt. Netw. Mag. 4, 55-64 (2003).

K. Zhu and B. Mukherjee, "Traffic grooming in optical WDM mesh networks," IEEE J. Sel. Areas Commun. 20, 122-133 (2002).

Orlin, J. B.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, 1993).

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]

Ramaswami, R.

O. Gerstel, R. Ramaswami, and G. Sasaki, "Cost effective traffic grooming in WDM rings," IEEE/ACM Trans. Netw. 8, 618-630 (2000).
[Crossref]

Rouskas, G.

R. Dutta and G. Rouskas, "Traffic grooming in WDM networks: past and future," IEEE Netw. 16, 46-56 (2002).

R. Dutta, S. Huang, and G. Rouskas, "On optimal traffic grooming in elemental network topologies," in Proceedings of OPTICOMM (2003), pp. 13-24.

Rouskas, G. N.

R. Dutta and G. N. Rouskas, "On optimal traffic grooming in WDM rings," IEEE J. Sel. Areas Commun. 20, 110-121 (2002).

Sasaki, G.

O. Gerstel, R. Ramaswami, and G. Sasaki, "Cost effective traffic grooming in WDM rings," IEEE/ACM Trans. Netw. 8, 618-630 (2000).
[Crossref]

O. Gerstel, P. Lin, and G. Sasaki, "Wavelength assignment in WDM rings to minimize system cost instead of number of wavelengths," in INFOCOM '98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE, 1998), Vol. 1, pp. 94-101.

Tardos, É.

É. Tardos, "A strongly polynomial minimum cost circulation algorithm," Combinatorica 5, 247-255 (1985).
[Crossref]

Wan, P.-J.

P.-J. Wan, G. Calinescu, L. Liu, and O. Frieder, "Grooming of arbitrary traffic in SONET WDM BLSRs," IEEE J. Sel. Areas Commun. 18, 1995-2003 (2000).
[Crossref]

X.-Y. Li, L. Liu, P.-J. Wan, and O. Frieder, "Practical traffic grooming scheme for single hub SONET/WDM rings," in Proceedings of 25th Annual IEEE Conference on Local Computer Networks (IEEE, 2000), pp. 556- 564.

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. Netw. Mag. 4, 55-64 (2003).

K. Zhu and B. Mukherjee, "Traffic grooming in optical WDM mesh networks," IEEE J. Sel. Areas Commun. 20, 122-133 (2002).

Combinatorica (1)

É. Tardos, "A strongly polynomial minimum cost circulation algorithm," Combinatorica 5, 247-255 (1985).
[Crossref]

Discrete Math. (1)

P. C. Fishburn, "Interval graphs and interval orders," Discrete Math. 55, 135-149 (1985).

IEEE Commun. Mag. (1)

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

IEEE Commun. Surveys Tutorials (1)

S. Huang and R. Dutta, "Dynamic traffic grooming: the changing role of traffic grooming," IEEE Commun. Surveys Tutorials 9, 32-49 (2007).

IEEE J. Sel. Areas Commun. (3)

P.-J. Wan, G. Calinescu, L. Liu, and O. Frieder, "Grooming of arbitrary traffic in SONET WDM BLSRs," IEEE J. Sel. Areas Commun. 18, 1995-2003 (2000).
[Crossref]

R. Dutta and G. N. Rouskas, "On optimal traffic grooming in WDM rings," IEEE J. Sel. Areas Commun. 20, 110-121 (2002).

K. Zhu and B. Mukherjee, "Traffic grooming in optical WDM mesh networks," IEEE J. Sel. Areas Commun. 20, 122-133 (2002).

IEEE Netw. (1)

R. Dutta and G. Rouskas, "Traffic grooming in WDM networks: past and future," IEEE Netw. 16, 46-56 (2002).

IEEE/ACM Trans. Netw. (2)

O. Gerstel, R. Ramaswami, and G. Sasaki, "Cost effective traffic grooming in WDM rings," IEEE/ACM Trans. Netw. 8, 618-630 (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]

Opt. Netw. Mag. (1)

K. Zhu and B. Mukherjee, "A review of traffic grooming in WDM optical networks: architectures and challenges," Opt. Netw. Mag. 4, 55-64 (2003).

Other (7)

P. Iyer, "The complexity of traffic grooming in optical path networks with egress traffic," Master's thesis (North Carolina State University, 2003).

X.-Y. Li, L. Liu, P.-J. Wan, and O. Frieder, "Practical traffic grooming scheme for single hub SONET/WDM rings," in Proceedings of 25th Annual IEEE Conference on Local Computer Networks (IEEE, 2000), pp. 556- 564.

O. Gerstel, P. Lin, and G. Sasaki, "Wavelength assignment in WDM rings to minimize system cost instead of number of wavelengths," in INFOCOM '98. Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE, 1998), Vol. 1, pp. 94-101.

R. Dutta, S. Huang, and G. Rouskas, "On optimal traffic grooming in elemental network topologies," in Proceedings of OPTICOMM (2003), pp. 13-24.

V. R. Konda and T. Y. Chow, "Algorithm for traffic grooming in optical network to minimize the number of transceivers," in 2001 IEEE Workshop on High Performance Switching and Routing (IEEE, 2001), pp. 218-221.

A. Chiu and E. Modiano, "Reducing electronic multiplexing costs in unidirectional SONET/WDM rings via efficient traffic grooming," in GLOBECOM 98: Global Telecommunications Conference (IEEE, 1998), Vol. 1, pp. 322-327.

R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications (Prentice-Hall, 1993).

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.