## Multicast routing and wavelength assignment in WDM networks: a bin packing approach

Journal of Optical Networking, Vol. 5, Issue 4, pp. 266-279 (2006)

http://dx.doi.org/10.1364/JON.5.000266

Acrobat PDF (164 KB)

### 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

**OCIS Codes**

(060.4250) Fiber optics and optical communications : Networks

(060.4510) Fiber optics and optical communications : Optical communications

**ToC Category:**

RESEARCH PAPERS

**History**

Original Manuscript: December 7, 2005

Revised Manuscript: February 13, 2006

Manuscript Accepted: March 6, 2006

Published: March 29, 2006

**Citation**

Nina Skorin-Kapov, "Multicast routing and wavelength assignment in WDM networks: a bin
packing approach," J. Opt. Netw. **5**, 266-279 (2006)

http://www.opticsinfobase.org/jocn/abstract.cfm?URI=jon-5-4-266

Sort: Year | Journal | Reset

### References

- I. Chlamtac, A. Ganz, and G. Karmi, 'Lightpath communications: an approach to high-bandwidth optical WANs,' IEEE Trans. Commun. 40, 1171-1182 (1992).
- N. Skorin-Kapov, 'Routing and wavelength assignment in optical networks using bin packing based algorithms,' Eur. J. Oper. Res. (to be published).
- 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).
- 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).
- L. H. Sahasrabuddhe and B. Mukherjee, 'Light trees: optical multicasting for improved performance in wavelength-routed networks,' IEEE Commun. Mag. 37, 67-73 (1999).
- A. Ding and G.-S. Poo, 'A survey of optical multicast over WDM networks,' Comput. Commun. 26, 193-200 (2003).
- M. Kovacevic and A. S. Acampora, 'Electronic wavelength translation in optical networks,' J. Lightwave Technol. 14, 1161-1169 (1996).
- 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).
- M. Ali and J. S. Deogun, 'Power-efficient design of multicast wavelength routed networks,' IEEE J. Sel. Areas Commun. 18, 1852-1862 (2000).
- M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, 1979).
- 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).
- 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).
- 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).
- N. K. Singhal and B. Mukherjee, 'Protecting multicast sessions in WDM optical mesh networks,' J. Lightwave Technol. 21, 884-892 (2003).
- N. Skorin-Kapov and M. Kos, 'A GRASP heuristic for the delay-constrained multicast routing problem,' Telecommun. Sys. (to be published).
- 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.
- 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).
- R. K. Pankaj, 'Wavelength requirements for multicasting in all-optical networks,' IEEE/ACM Trans. Netw. 7, 414-424 (1999).
- B. Mukherjee, Optical Communication Networks (McGraw-Hill, 1997).
- 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).
- M. Ali and J. S. Deogun, 'Cost-effective implementation of multicasting in wavelength-routed networks,' J. Lightwave Technol. 18, 1628-1638 (2000).
- 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).
- 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).

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