Abstract

We address the problem of multicast routing and wavelength assignment (MClowbarRWA) in wavelength-routed WDM optical networks. Multicast requests are facilitated in WDM networks by setting up so-called light trees and assigning wavelengths to them. Objectives of the MClowbarRWA problem include minimizing the number of distinct wavelengths used to establish a set of multicast requests and minimizing the cost of the corresponding light trees. This cost can represent the physical length, delay, or actual cost of a tree. Applications that require quality of service (QoS) multicasting can impose additional constraints on light trees, such as a bounded end-to-end delay. Proposed are heuristic algorithms based on bin packing methods for the general MClowbarRWA problem, which is NP complete. These algorithms can consider unicast, multicast, and broadcast requests with or without QoS demands. Computational tests indicate that these algorithms are efficient, particularly for dense networks.

© 2006 Optical Society of America

PDF Article

References

  • View by:
  • |
  • |
  • |

  1. I. Chlamtac, A. Ganz, and G. Karmi, 'Lightpath communications: an approach to high-bandwidth optical WANs,' IEEE Trans. Commun. 40, 1171-1182 (1992).
  2. N. Skorin-Kapov, 'Routing and wavelength assignment in optical networks using bin packing based algorithms,' Eur. J. Oper. Res. (to be published).
  3. X. Chu and B. Li, 'Dynamic routing and wavelength assignment in the presence of wavelength conversion for all-optical networks,' IEEE/ACM Trans. Netw. 13, 704-715 (2005).
  4. N. Skorin-Kapov, 'Heuristic algorithms for the routing and wavelength assignment of scheduled lightpath demands in optical networks,' IEEE J. Sel. Areas Commun. (to be published).
  5. L. H. Sahasrabuddhe and B. Mukherjee, 'Light trees: optical multicasting for improved performance in wavelength-routed networks,' IEEE Commun. Mag. 37, 67-73 (1999).
  6. A. Ding and G.-S. Poo, 'A survey of optical multicast over WDM networks,' Comput. Commun. 26, 193-200 (2003).
  7. M. Kovacevic and A. S. Acampora, 'Electronic wavelength translation in optical networks,' J. Lightwave Technol. 14, 1161-1169 (1996).
  8. C. A. S. Oliveira, P. M. Pardalos, and M. G. C. Resende, 'Optimization problems in multicast tree construction,' in Handbook of Optimization in Telecommunications (Kluwer, 2005), pp. 701-733.
  9. X.Cheng and D.-Z.Du, eds., Steiner Trees in Industry (Kluwer, 2001).
  10. M. Ali and J. S. Deogun, 'Power-efficient design of multicast wavelength routed networks,' IEEE J. Sel. Areas Commun. 18, 1852-1862 (2000).
  11. M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, 1979).
  12. B. Chen and J. Wang, 'Efficient routing and wavelength assignment for multicast in WDM networks,' IEEE J. Sel. Areas Commun. 20, 97-109 (2002).
  13. R. Hadas and R. Melhem, 'Multicast routing and wavelength assignment in multihop optical networks,' IEEE/ACM Trans. Netw. 10, 621-629 (2002).
  14. X.-D. Hu, T.-P. Shaui, X. Jia, and M.-H. Zhang, 'Multicast routing and wavelength assignment in WDM networks with limited drop-offs,' in Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies, Hong Kong, March 2004 (IEEE, 2004).
  15. X.-H. Jia, D.-Z. Du, X.-D. Hu, M.-K. Lee, and J. Gu, 'Optimization of wavelength assignment for QoS multicast in WDM networks,' IEEE Trans. Commun. 49, 341-350 (2001).
  16. N. K. Singhal and B. Mukherjee, 'Protecting multicast sessions in WDM optical mesh networks,' J. Lightwave Technol. 21, 884-892 (2003).
  17. N. Skorin-Kapov and M. Kos, 'A GRASP heuristic for the delay-constrained multicast routing problem,' Telecommun. Sys. (to be published).
  18. T. Koch, A. Martin, and S. Voß, 'Steinlib: an updated library on Steiner tree problems in graphs' (2001), available at http://elib.zib.de/steinlib.
  19. J. Gu, X.-D. Hu, X. Jia, and M.-H. Zhang, 'Routing algorithm for multicast under multi-tree model in optical networks,' Theor. Comput. Sci. 314, 293-301 (2004).
  20. R. K. Pankaj, 'Wavelength requirements for multicasting in all-optical networks,' IEEE/ACM Trans. Netw. 7, 414-424 (1999).
  21. B. Mukherjee, Optical Communication Networks (McGraw-Hill, 1997).
  22. X. Zhang, J. Y. Wei, and C. Qiao, 'Constrained multicast routing in WDM networks with sparse light splitting,' J. Lightwave Technol. 18, 1917-1927 (2000).
  23. M. Ali and J. S. Deogun, 'Cost-effective implementation of multicasting in wavelength-routed networks,' J. Lightwave Technol. 18, 1628-1638 (2000).
  24. J. E. G. Coffman, R. Garey, and D. S. Johnson, 'Bin packing approximation algorithms: a survey,' in Approximation Algorithms for NP-Hard Problems, D.Hochbaum, ed. (PWS, 1996).
  25. J. E. G. Coffman, J. Csirik, and G. Woeginger, 'Bin packing theory,' in Handbook of Applied Optimization, P.Pardalos and M.Resende, eds. (Oxford U. Press, 2002).
  26. P. Manohar, D. Manjunath, and R. K. Shevgaonkar, 'Routing and wavelength assignment in optical networks from edge disjoint paths algorithms,' IEEE Commun. Lett. 6, 211-213 (2002).

2004 (1)

J. Gu, X.-D. Hu, X. Jia, and M.-H. Zhang, 'Routing algorithm for multicast under multi-tree model in optical networks,' Theor. Comput. Sci. 314, 293-301 (2004).

2003 (2)

A. Ding and G.-S. Poo, 'A survey of optical multicast over WDM networks,' Comput. Commun. 26, 193-200 (2003).

N. K. Singhal and B. Mukherjee, 'Protecting multicast sessions in WDM optical mesh networks,' J. Lightwave Technol. 21, 884-892 (2003).

2002 (3)

P. Manohar, D. Manjunath, and R. K. Shevgaonkar, 'Routing and wavelength assignment in optical networks from edge disjoint paths algorithms,' IEEE Commun. Lett. 6, 211-213 (2002).

B. Chen and J. Wang, 'Efficient routing and wavelength assignment for multicast in WDM networks,' IEEE J. Sel. Areas Commun. 20, 97-109 (2002).

R. Hadas and R. Melhem, 'Multicast routing and wavelength assignment in multihop optical networks,' IEEE/ACM Trans. Netw. 10, 621-629 (2002).

2001 (1)

X.-H. Jia, D.-Z. Du, X.-D. Hu, M.-K. Lee, and J. Gu, 'Optimization of wavelength assignment for QoS multicast in WDM networks,' IEEE Trans. Commun. 49, 341-350 (2001).

2000 (3)

1999 (2)

R. K. Pankaj, 'Wavelength requirements for multicasting in all-optical networks,' IEEE/ACM Trans. Netw. 7, 414-424 (1999).

L. H. Sahasrabuddhe and B. Mukherjee, 'Light trees: optical multicasting for improved performance in wavelength-routed networks,' IEEE Commun. Mag. 37, 67-73 (1999).

1996 (1)

M. Kovacevic and A. S. Acampora, 'Electronic wavelength translation in optical networks,' J. Lightwave Technol. 14, 1161-1169 (1996).

1992 (1)

I. Chlamtac, A. Ganz, and G. Karmi, 'Lightpath communications: an approach to high-bandwidth optical WANs,' IEEE Trans. Commun. 40, 1171-1182 (1992).

Acampora, A. S.

M. Kovacevic and A. S. Acampora, 'Electronic wavelength translation in optical networks,' J. Lightwave Technol. 14, 1161-1169 (1996).

Ali, M.

M. Ali and J. S. Deogun, 'Cost-effective implementation of multicasting in wavelength-routed networks,' J. Lightwave Technol. 18, 1628-1638 (2000).

M. Ali and J. S. Deogun, 'Power-efficient design of multicast wavelength routed networks,' IEEE J. Sel. Areas Commun. 18, 1852-1862 (2000).

Chen, B.

B. Chen and J. Wang, 'Efficient routing and wavelength assignment for multicast in WDM networks,' IEEE J. Sel. Areas Commun. 20, 97-109 (2002).

Chlamtac, I.

I. Chlamtac, A. Ganz, and G. Karmi, 'Lightpath communications: an approach to high-bandwidth optical WANs,' IEEE Trans. Commun. 40, 1171-1182 (1992).

Chu, X.

X. Chu and B. Li, 'Dynamic routing and wavelength assignment in the presence of wavelength conversion for all-optical networks,' IEEE/ACM Trans. Netw. 13, 704-715 (2005).

Coffman, J. E. G.

J. E. G. Coffman, R. Garey, and D. S. Johnson, 'Bin packing approximation algorithms: a survey,' in Approximation Algorithms for NP-Hard Problems, D.Hochbaum, ed. (PWS, 1996).

J. E. G. Coffman, J. Csirik, and G. Woeginger, 'Bin packing theory,' in Handbook of Applied Optimization, P.Pardalos and M.Resende, eds. (Oxford U. Press, 2002).

Csirik, J.

J. E. G. Coffman, J. Csirik, and G. Woeginger, 'Bin packing theory,' in Handbook of Applied Optimization, P.Pardalos and M.Resende, eds. (Oxford U. Press, 2002).

Deogun, J. S.

M. Ali and J. S. Deogun, 'Power-efficient design of multicast wavelength routed networks,' IEEE J. Sel. Areas Commun. 18, 1852-1862 (2000).

M. Ali and J. S. Deogun, 'Cost-effective implementation of multicasting in wavelength-routed networks,' J. Lightwave Technol. 18, 1628-1638 (2000).

Ding, A.

A. Ding and G.-S. Poo, 'A survey of optical multicast over WDM networks,' Comput. Commun. 26, 193-200 (2003).

Du, D.-Z.

X.-H. Jia, D.-Z. Du, X.-D. Hu, M.-K. Lee, and J. Gu, 'Optimization of wavelength assignment for QoS multicast in WDM networks,' IEEE Trans. Commun. 49, 341-350 (2001).

Ganz, A.

I. Chlamtac, A. Ganz, and G. Karmi, 'Lightpath communications: an approach to high-bandwidth optical WANs,' IEEE Trans. Commun. 40, 1171-1182 (1992).

Garey, M. R.

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

Garey, R.

J. E. G. Coffman, R. Garey, and D. S. Johnson, 'Bin packing approximation algorithms: a survey,' in Approximation Algorithms for NP-Hard Problems, D.Hochbaum, ed. (PWS, 1996).

Gu, J.

J. Gu, X.-D. Hu, X. Jia, and M.-H. Zhang, 'Routing algorithm for multicast under multi-tree model in optical networks,' Theor. Comput. Sci. 314, 293-301 (2004).

X.-H. Jia, D.-Z. Du, X.-D. Hu, M.-K. Lee, and J. Gu, 'Optimization of wavelength assignment for QoS multicast in WDM networks,' IEEE Trans. Commun. 49, 341-350 (2001).

Hadas, R.

R. Hadas and R. Melhem, 'Multicast routing and wavelength assignment in multihop optical networks,' IEEE/ACM Trans. Netw. 10, 621-629 (2002).

Hu, X.-D.

J. Gu, X.-D. Hu, X. Jia, and M.-H. Zhang, 'Routing algorithm for multicast under multi-tree model in optical networks,' Theor. Comput. Sci. 314, 293-301 (2004).

X.-H. Jia, D.-Z. Du, X.-D. Hu, M.-K. Lee, and J. Gu, 'Optimization of wavelength assignment for QoS multicast in WDM networks,' IEEE Trans. Commun. 49, 341-350 (2001).

X.-D. Hu, T.-P. Shaui, X. Jia, and M.-H. Zhang, 'Multicast routing and wavelength assignment in WDM networks with limited drop-offs,' in Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies, Hong Kong, March 2004 (IEEE, 2004).

Jia, X.

J. Gu, X.-D. Hu, X. Jia, and M.-H. Zhang, 'Routing algorithm for multicast under multi-tree model in optical networks,' Theor. Comput. Sci. 314, 293-301 (2004).

X.-D. Hu, T.-P. Shaui, X. Jia, and M.-H. Zhang, 'Multicast routing and wavelength assignment in WDM networks with limited drop-offs,' in Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies, Hong Kong, March 2004 (IEEE, 2004).

Jia, X.-H.

X.-H. Jia, D.-Z. Du, X.-D. Hu, M.-K. Lee, and J. Gu, 'Optimization of wavelength assignment for QoS multicast in WDM networks,' IEEE Trans. Commun. 49, 341-350 (2001).

Johnson, D. S.

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

J. E. G. Coffman, R. Garey, and D. S. Johnson, 'Bin packing approximation algorithms: a survey,' in Approximation Algorithms for NP-Hard Problems, D.Hochbaum, ed. (PWS, 1996).

Karmi, G.

I. Chlamtac, A. Ganz, and G. Karmi, 'Lightpath communications: an approach to high-bandwidth optical WANs,' IEEE Trans. Commun. 40, 1171-1182 (1992).

Koch, T.

T. Koch, A. Martin, and S. Voß, 'Steinlib: an updated library on Steiner tree problems in graphs' (2001), available at http://elib.zib.de/steinlib.

Kos, M.

N. Skorin-Kapov and M. Kos, 'A GRASP heuristic for the delay-constrained multicast routing problem,' Telecommun. Sys. (to be published).

Kovacevic, M.

M. Kovacevic and A. S. Acampora, 'Electronic wavelength translation in optical networks,' J. Lightwave Technol. 14, 1161-1169 (1996).

Lee, M.-K.

X.-H. Jia, D.-Z. Du, X.-D. Hu, M.-K. Lee, and J. Gu, 'Optimization of wavelength assignment for QoS multicast in WDM networks,' IEEE Trans. Commun. 49, 341-350 (2001).

Li, B.

X. Chu and B. Li, 'Dynamic routing and wavelength assignment in the presence of wavelength conversion for all-optical networks,' IEEE/ACM Trans. Netw. 13, 704-715 (2005).

Manjunath, D.

P. Manohar, D. Manjunath, and R. K. Shevgaonkar, 'Routing and wavelength assignment in optical networks from edge disjoint paths algorithms,' IEEE Commun. Lett. 6, 211-213 (2002).

Manohar, P.

P. Manohar, D. Manjunath, and R. K. Shevgaonkar, 'Routing and wavelength assignment in optical networks from edge disjoint paths algorithms,' IEEE Commun. Lett. 6, 211-213 (2002).

Martin, A.

T. Koch, A. Martin, and S. Voß, 'Steinlib: an updated library on Steiner tree problems in graphs' (2001), available at http://elib.zib.de/steinlib.

Melhem, R.

R. Hadas and R. Melhem, 'Multicast routing and wavelength assignment in multihop optical networks,' IEEE/ACM Trans. Netw. 10, 621-629 (2002).

Mukherjee, B.

N. K. Singhal and B. Mukherjee, 'Protecting multicast sessions in WDM optical mesh networks,' J. Lightwave Technol. 21, 884-892 (2003).

L. H. Sahasrabuddhe and B. Mukherjee, 'Light trees: optical multicasting for improved performance in wavelength-routed networks,' IEEE Commun. Mag. 37, 67-73 (1999).

B. Mukherjee, Optical Communication Networks (McGraw-Hill, 1997).

Oliveira, C. A. S.

C. A. S. Oliveira, P. M. Pardalos, and M. G. C. Resende, 'Optimization problems in multicast tree construction,' in Handbook of Optimization in Telecommunications (Kluwer, 2005), pp. 701-733.

Pankaj, R. K.

R. K. Pankaj, 'Wavelength requirements for multicasting in all-optical networks,' IEEE/ACM Trans. Netw. 7, 414-424 (1999).

Pardalos, P. M.

C. A. S. Oliveira, P. M. Pardalos, and M. G. C. Resende, 'Optimization problems in multicast tree construction,' in Handbook of Optimization in Telecommunications (Kluwer, 2005), pp. 701-733.

Poo, G.-S.

A. Ding and G.-S. Poo, 'A survey of optical multicast over WDM networks,' Comput. Commun. 26, 193-200 (2003).

Qiao, C.

Resende, M. G. C.

C. A. S. Oliveira, P. M. Pardalos, and M. G. C. Resende, 'Optimization problems in multicast tree construction,' in Handbook of Optimization in Telecommunications (Kluwer, 2005), pp. 701-733.

Sahasrabuddhe, L. H.

L. H. Sahasrabuddhe and B. Mukherjee, 'Light trees: optical multicasting for improved performance in wavelength-routed networks,' IEEE Commun. Mag. 37, 67-73 (1999).

Shaui, T.-P.

X.-D. Hu, T.-P. Shaui, X. Jia, and M.-H. Zhang, 'Multicast routing and wavelength assignment in WDM networks with limited drop-offs,' in Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies, Hong Kong, March 2004 (IEEE, 2004).

Shevgaonkar, R. K.

P. Manohar, D. Manjunath, and R. K. Shevgaonkar, 'Routing and wavelength assignment in optical networks from edge disjoint paths algorithms,' IEEE Commun. Lett. 6, 211-213 (2002).

Singhal, N. K.

Skorin-Kapov, N.

N. Skorin-Kapov, 'Routing and wavelength assignment in optical networks using bin packing based algorithms,' Eur. J. Oper. Res. (to be published).

N. Skorin-Kapov and M. Kos, 'A GRASP heuristic for the delay-constrained multicast routing problem,' Telecommun. Sys. (to be published).

N. Skorin-Kapov, 'Heuristic algorithms for the routing and wavelength assignment of scheduled lightpath demands in optical networks,' IEEE J. Sel. Areas Commun. (to be published).

Voß, S.

T. Koch, A. Martin, and S. Voß, 'Steinlib: an updated library on Steiner tree problems in graphs' (2001), available at http://elib.zib.de/steinlib.

Wang, J.

B. Chen and J. Wang, 'Efficient routing and wavelength assignment for multicast in WDM networks,' IEEE J. Sel. Areas Commun. 20, 97-109 (2002).

Wei, J. Y.

Woeginger, G.

J. E. G. Coffman, J. Csirik, and G. Woeginger, 'Bin packing theory,' in Handbook of Applied Optimization, P.Pardalos and M.Resende, eds. (Oxford U. Press, 2002).

Zhang, M.-H.

J. Gu, X.-D. Hu, X. Jia, and M.-H. Zhang, 'Routing algorithm for multicast under multi-tree model in optical networks,' Theor. Comput. Sci. 314, 293-301 (2004).

X.-D. Hu, T.-P. Shaui, X. Jia, and M.-H. Zhang, 'Multicast routing and wavelength assignment in WDM networks with limited drop-offs,' in Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies, Hong Kong, March 2004 (IEEE, 2004).

Zhang, X.

Comput. Commun. (1)

A. Ding and G.-S. Poo, 'A survey of optical multicast over WDM networks,' Comput. Commun. 26, 193-200 (2003).

Eur. J. Oper. Res. (1)

N. Skorin-Kapov, 'Routing and wavelength assignment in optical networks using bin packing based algorithms,' Eur. J. Oper. Res. (to be published).

IEEE Commun. Lett. (1)

P. Manohar, D. Manjunath, and R. K. Shevgaonkar, 'Routing and wavelength assignment in optical networks from edge disjoint paths algorithms,' IEEE Commun. Lett. 6, 211-213 (2002).

IEEE Commun. Mag. (1)

L. H. Sahasrabuddhe and B. Mukherjee, 'Light trees: optical multicasting for improved performance in wavelength-routed networks,' IEEE Commun. Mag. 37, 67-73 (1999).

IEEE J. Sel. Areas Commun. (3)

M. Ali and J. S. Deogun, 'Power-efficient design of multicast wavelength routed networks,' IEEE J. Sel. Areas Commun. 18, 1852-1862 (2000).

B. Chen and J. Wang, 'Efficient routing and wavelength assignment for multicast in WDM networks,' IEEE J. Sel. Areas Commun. 20, 97-109 (2002).

N. Skorin-Kapov, 'Heuristic algorithms for the routing and wavelength assignment of scheduled lightpath demands in optical networks,' IEEE J. Sel. Areas Commun. (to be published).

IEEE Trans. Commun. (2)

I. Chlamtac, A. Ganz, and G. Karmi, 'Lightpath communications: an approach to high-bandwidth optical WANs,' IEEE Trans. Commun. 40, 1171-1182 (1992).

X.-H. Jia, D.-Z. Du, X.-D. Hu, M.-K. Lee, and J. Gu, 'Optimization of wavelength assignment for QoS multicast in WDM networks,' IEEE Trans. Commun. 49, 341-350 (2001).

IEEE/ACM Trans. Netw. (3)

R. Hadas and R. Melhem, 'Multicast routing and wavelength assignment in multihop optical networks,' IEEE/ACM Trans. Netw. 10, 621-629 (2002).

X. Chu and B. Li, 'Dynamic routing and wavelength assignment in the presence of wavelength conversion for all-optical networks,' IEEE/ACM Trans. Netw. 13, 704-715 (2005).

R. K. Pankaj, 'Wavelength requirements for multicasting in all-optical networks,' IEEE/ACM Trans. Netw. 7, 414-424 (1999).

J. Lightwave Technol. (4)

Telecommun. Sys. (1)

N. Skorin-Kapov and M. Kos, 'A GRASP heuristic for the delay-constrained multicast routing problem,' Telecommun. Sys. (to be published).

Theor. Comput. Sci. (1)

J. Gu, X.-D. Hu, X. Jia, and M.-H. Zhang, 'Routing algorithm for multicast under multi-tree model in optical networks,' Theor. Comput. Sci. 314, 293-301 (2004).

Other (8)

T. Koch, A. Martin, and S. Voß, 'Steinlib: an updated library on Steiner tree problems in graphs' (2001), available at http://elib.zib.de/steinlib.

X.-D. Hu, T.-P. Shaui, X. Jia, and M.-H. Zhang, 'Multicast routing and wavelength assignment in WDM networks with limited drop-offs,' in Twenty-Third Annual Joint Conference of the IEEE Computer and Communications Societies, Hong Kong, March 2004 (IEEE, 2004).

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

C. A. S. Oliveira, P. M. Pardalos, and M. G. C. Resende, 'Optimization problems in multicast tree construction,' in Handbook of Optimization in Telecommunications (Kluwer, 2005), pp. 701-733.

X.Cheng and D.-Z.Du, eds., Steiner Trees in Industry (Kluwer, 2001).

B. Mukherjee, Optical Communication Networks (McGraw-Hill, 1997).

J. E. G. Coffman, R. Garey, and D. S. Johnson, 'Bin packing approximation algorithms: a survey,' in Approximation Algorithms for NP-Hard Problems, D.Hochbaum, ed. (PWS, 1996).

J. E. G. Coffman, J. Csirik, and G. Woeginger, 'Bin packing theory,' in Handbook of Applied Optimization, P.Pardalos and M.Resende, eds. (Oxford U. Press, 2002).

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.