Abstract

The problem of routing traffic on multihop clear optical channels and deciding the virtual topology of optical channels to form on a physical network of fibers to minimize the cost of electronic switching equipment has become known as traffic grooming in optical networks. Traffic grooming is recognized as an important research area, because the joint opto-electric routing problem is a hard one, yet necessary because of the large cost of pure electronic switching. This problem has been shown to be NP-complete (nondeterminstic polynomial complete) even for very simple practical topologies such as a path network. In previous work, we have shown that at least the subproblem of routing traffic on a given virtual topology to minimize electronic switching (NP-hard for path networks with arbitrary traffic matrices) becomes polynomial when the traffic on the path is restricted to be egress traffic, that is, all traffic requests are destined for a single egress node. In that work, the objective was to minimize the raw OEO (opto-electro-optic) metric (number of bits electronically switched per second) totaled over all network nodes. Of late, it has become clear that electronic switching equipment cost is best counted in quantized units, e.g., in the number of transceiver interfaces at network nodes. In this paper, we consider the traffic grooming problem in unidirectional, WDM path networks with the goal of minimizing the number of transceivers. We conclusively show that the problem is NP-hard, even under the restriction of the egress traffic model. In the case of egress traffic, we give a simple heuristic that will never be worse than twice the optimal.

© 2009 Optical Society of America

PDF Article

References

  • View by:
  • |
  • |
  • |

  1. O. Gerstel, G. Sasaki, and R. Ramaswami, “Cost effective traffic grooming in WDM rings,” IEEE/ACM Trans. Netw. 8, 618-630 (2000).
    [CrossRef]
  2. R. Dutta and G. Rouskas, “On optimal traffic grooming in WDM rings,” IEEE J. Sel. Areas Commun. 20, 110-121 (2002).
    [CrossRef]
  3. K. Zhu and B. Mukherjee, “Traffic grooming in optical WDM mesh networks,” IEEE J. Sel. Areas Commun. 20, 122-133 (2002).
    [CrossRef]
  4. X. Li, L. Liu, P. Wan, and O. Frieder, “Practical traffic grooming scheme for single hub SONET/WDM rings,” in Proceedings, 25th Annual IEEE Conference on Local Computer Networks (IEEE, 2000), pp. 556-564.
  5. 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]
  6. P. Iyer, R. Dutta, and C. D. Savage, “Complexity of path traffic grooming,” J. Opt. Netw. 6, 1270-1281 (2007).
    [CrossRef]
  7. M. Brunato and R. Battiti, “A multistart randomized greedy algorithm for traffic grooming on mesh logical topologies,” in Sixth IFIP Working Conference on Optical Network Design and Modeling (ONDM 2002) (Klewer, 2002).
  8. R. Dutta and G. Rouskas, “Traffic grooming in WDM networks: past and future,” IEEE Network 16, 46-56 (2002).
  9. K. Zhu and B. Mukherjee, “A review of traffic grooming in WDM optical networks: architectures and challenges,” Opt. Networks Mag. 4, 55-64 (2003).
  10. E. Modiano and P. Lin, “Traffic grooming in WDM networks,” IEEE Commun. Mag. 39(7), 124-129 (2001).
    [CrossRef]
  11. S. Huang and R. Dutta, “Dynamic traffic grooming: the changing role of traffic grooming,” IEEE Commun. Surv. Tutorials 9, 32-50 (2007).
  12. R. Dutta, A. Kamal, and G. Rouskas, Traffic Grooming for Optical Networks: Foundations, Techniques and Frontiers (Springer, 2008).
  13. S. Huang, R. Dutta, and G. Rouskas, “Traffic grooming in path, star, and tree networks: complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun. 24, 66-82 (2006).
  14. P. 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]
  15. V. Konda and T. 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.
  16. A. Chiu and E. Modiano, “Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks,” J. Lightwave Technol. 18, 2-12 (2000).
    [CrossRef]
  17. M. Vecchi, “Broadband networks and services: architecture and control,” IEEE Commun. Mag. 33(8), 24-32 (1995).
  18. J. Kurose and K. Ross, Computer Networking: A Top Down Approach; Featuring the Internet, 3rd ed. (Addison-Wesley, 2004).
  19. P. Fishburn, “Interval graphs and interval orders,” Discrete Math. 55, 135-149 (1985).
    [CrossRef]
  20. M. Garey and D. Johnson, Computers and Intractability A Guide to the Theory of NP-Completeness (W. H. Freeman, 1979).

2007 (2)

P. Iyer, R. Dutta, and C. D. Savage, “Complexity of path traffic grooming,” J. Opt. Netw. 6, 1270-1281 (2007).
[CrossRef]

S. Huang and R. Dutta, “Dynamic traffic grooming: the changing role of traffic grooming,” IEEE Commun. Surv. Tutorials 9, 32-50 (2007).

2006 (1)

S. Huang, R. Dutta, and G. Rouskas, “Traffic grooming in path, star, and tree networks: complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun. 24, 66-82 (2006).

2003 (1)

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

2002 (3)

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

R. Dutta and G. Rouskas, “On optimal traffic grooming in WDM rings,” IEEE J. Sel. Areas Commun. 20, 110-121 (2002).
[CrossRef]

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

2001 (1)

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

2000 (4)

O. Gerstel, G. Sasaki, and R. Ramaswami, “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. 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]

A. Chiu and E. Modiano, “Traffic grooming algorithms for reducing electronic multiplexing costs in WDM ring networks,” J. Lightwave Technol. 18, 2-12 (2000).
[CrossRef]

1995 (1)

M. Vecchi, “Broadband networks and services: architecture and control,” IEEE Commun. Mag. 33(8), 24-32 (1995).

1985 (1)

P. Fishburn, “Interval graphs and interval orders,” Discrete Math. 55, 135-149 (1985).
[CrossRef]

Battiti, R.

M. Brunato and R. Battiti, “A multistart randomized greedy algorithm for traffic grooming on mesh logical topologies,” in Sixth IFIP Working Conference on Optical Network Design and Modeling (ONDM 2002) (Klewer, 2002).

Brunato, M.

M. Brunato and R. Battiti, “A multistart randomized greedy algorithm for traffic grooming on mesh logical topologies,” in Sixth IFIP Working Conference on Optical Network Design and Modeling (ONDM 2002) (Klewer, 2002).

Calinescu, G.

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

Chow, T.

V. Konda and T. 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.

P. Iyer, R. Dutta, and C. D. Savage, “Complexity of path traffic grooming,” J. Opt. Netw. 6, 1270-1281 (2007).
[CrossRef]

S. Huang and R. Dutta, “Dynamic traffic grooming: the changing role of traffic grooming,” IEEE Commun. Surv. Tutorials 9, 32-50 (2007).

S. Huang, R. Dutta, and G. Rouskas, “Traffic grooming in path, star, and tree networks: complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun. 24, 66-82 (2006).

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

R. Dutta and G. Rouskas, “On optimal traffic grooming in WDM rings,” IEEE J. Sel. Areas Commun. 20, 110-121 (2002).
[CrossRef]

R. Dutta, A. Kamal, and G. Rouskas, Traffic Grooming for Optical Networks: Foundations, Techniques and Frontiers (Springer, 2008).

Fishburn, P.

P. Fishburn, “Interval graphs and interval orders,” Discrete Math. 55, 135-149 (1985).
[CrossRef]

Frieder, O.

P. 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. Li, L. Liu, P. Wan, and O. Frieder, “Practical traffic grooming scheme for single hub SONET/WDM rings,” in Proceedings, 25th Annual IEEE Conference on Local Computer Networks (IEEE, 2000), pp. 556-564.

Garey, M.

M. Garey and D. Johnson, Computers and Intractability A Guide to the Theory of NP-Completeness (W. H. Freeman, 1979).

Gerstel, O.

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

Huang, S.

S. Huang and R. Dutta, “Dynamic traffic grooming: the changing role of traffic grooming,” IEEE Commun. Surv. Tutorials 9, 32-50 (2007).

S. Huang, R. Dutta, and G. Rouskas, “Traffic grooming in path, star, and tree networks: complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun. 24, 66-82 (2006).

Iyer, P.

Johnson, D.

M. Garey and D. Johnson, Computers and Intractability A Guide to the Theory of NP-Completeness (W. H. Freeman, 1979).

Kamal, A.

R. Dutta, A. Kamal, and G. Rouskas, Traffic Grooming for Optical Networks: Foundations, Techniques and Frontiers (Springer, 2008).

Konda, V.

V. Konda and T. 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.

Kurose, J.

J. Kurose and K. Ross, Computer Networking: A Top Down Approach; Featuring the Internet, 3rd ed. (Addison-Wesley, 2004).

Li, X.

X. Li, L. Liu, P. Wan, and O. Frieder, “Practical traffic grooming scheme for single hub SONET/WDM rings,” in Proceedings, 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(7), 124-129 (2001).
[CrossRef]

Liu, L.

P. 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. Li, L. Liu, P. Wan, and O. Frieder, “Practical traffic grooming scheme for single hub SONET/WDM rings,” in Proceedings, 25th Annual IEEE Conference on Local Computer Networks (IEEE, 2000), pp. 556-564.

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

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

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, G. Sasaki, and R. Ramaswami, “Cost effective traffic grooming in WDM rings,” IEEE/ACM Trans. Netw. 8, 618-630 (2000).
[CrossRef]

Ross, K.

J. Kurose and K. Ross, Computer Networking: A Top Down Approach; Featuring the Internet, 3rd ed. (Addison-Wesley, 2004).

Rouskas, G.

S. Huang, R. Dutta, and G. Rouskas, “Traffic grooming in path, star, and tree networks: complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun. 24, 66-82 (2006).

R. Dutta and G. Rouskas, “On optimal traffic grooming in WDM rings,” IEEE J. Sel. Areas Commun. 20, 110-121 (2002).
[CrossRef]

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

R. Dutta, A. Kamal, and G. Rouskas, Traffic Grooming for Optical Networks: Foundations, Techniques and Frontiers (Springer, 2008).

Sasaki, G.

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

Savage, C. D.

Vecchi, M.

M. Vecchi, “Broadband networks and services: architecture and control,” IEEE Commun. Mag. 33(8), 24-32 (1995).

Wan, P.

P. 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. Li, L. Liu, P. Wan, and O. Frieder, “Practical traffic grooming scheme for single hub SONET/WDM rings,” in Proceedings, 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. Networks 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).
[CrossRef]

Discrete Math. (1)

P. Fishburn, “Interval graphs and interval orders,” Discrete Math. 55, 135-149 (1985).
[CrossRef]

IEEE Commun. Mag. (2)

M. Vecchi, “Broadband networks and services: architecture and control,” IEEE Commun. Mag. 33(8), 24-32 (1995).

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

IEEE Commun. Surv. Tutorials (1)

S. Huang and R. Dutta, “Dynamic traffic grooming: the changing role of traffic grooming,” IEEE Commun. Surv. Tutorials 9, 32-50 (2007).

IEEE J. Sel. Areas Commun. (4)

R. Dutta and G. Rouskas, “On optimal traffic grooming in WDM rings,” IEEE J. Sel. Areas Commun. 20, 110-121 (2002).
[CrossRef]

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

S. Huang, R. Dutta, and G. Rouskas, “Traffic grooming in path, star, and tree networks: complexity, bounds, and algorithms,” IEEE J. Sel. Areas Commun. 24, 66-82 (2006).

P. 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]

IEEE Network (1)

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

IEEE/ACM Trans. Netw. (2)

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]

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

J. Lightwave Technol. (1)

J. Opt. Netw. (1)

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

Other (6)

R. Dutta, A. Kamal, and G. Rouskas, Traffic Grooming for Optical Networks: Foundations, Techniques and Frontiers (Springer, 2008).

M. Brunato and R. Battiti, “A multistart randomized greedy algorithm for traffic grooming on mesh logical topologies,” in Sixth IFIP Working Conference on Optical Network Design and Modeling (ONDM 2002) (Klewer, 2002).

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

V. Konda and T. 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.

J. Kurose and K. Ross, Computer Networking: A Top Down Approach; Featuring the Internet, 3rd ed. (Addison-Wesley, 2004).

M. Garey and D. Johnson, Computers and Intractability A Guide to the Theory of NP-Completeness (W. H. Freeman, 1979).

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.