OSA's Digital Library

Journal of Optical Communications and Networking

Journal of Optical Communications and Networking

  • Editors: K. Bergman and V. Chan
  • Vol. 3, Iss. 4 — Apr. 1, 2011
  • pp: 323–334

Cost Bounds and Approximation Ratios of Multicast Light-Trees in WDM Networks

Fen Zhou, Miklós Molnár, Bernard Cousin, and Chunming Qiao  »View Author Affiliations


Journal of Optical Communications and Networking, Vol. 3, Issue 4, pp. 323-334 (2011)
http://dx.doi.org/10.1364/JOCN.3.000323


View Full Text Article

Enhanced HTML    Acrobat PDF (425 KB)





Browse Journals / Lookup Meetings

Browse by Journal and Year


   


Lookup Conference Papers

Close Browse Journals / Lookup Meetings

Article Tools

Share
Citations

Abstract

The construction of light-trees is one of the principal subproblems for all-optical multicast routing in sparse splitting wavelength division multiplexing (WDM) networks. Due to the light splitting constraint and the absence of wavelength converters, several light-trees may be required to establish a multicast session. However, the computation of the cost-optimal multicast light-trees is NP-hard. In this paper, first we study the cost bounds of the light-trees built for a multicast session in unweighted WDM networks. Then, partially based on this result, the approximation ratios of some classical multicast light-tree computation algorithms, i.e., the reroute-to-source (R2S) and member-only (MO) algorithms, are derived in both unweighted and non-equally-weighted WDM networks. Moreover, integer linear programming formulations are introduced and carried out to search the optimal light-trees for multicast routing. The cost bounds and approximation ratios of the R2S and MO algorithms in some candidate WDM backbone networks are examined through simulations.

© 2011 OSA

OCIS Codes
(060.4251) Fiber optics and optical communications : Networks, assignment and routing algorithms
(060.4255) Fiber optics and optical communications : Networks, multicast

ToC Category:
Research Papers

History
Original Manuscript: August 24, 2010
Revised Manuscript: January 18, 2011
Manuscript Accepted: January 28, 2011
Published: March 31, 2011

Citation
Fen Zhou, Miklós Molnár, Bernard Cousin, and Chunming Qiao, "Cost Bounds and Approximation Ratios of Multicast Light-Trees in WDM Networks," J. Opt. Commun. Netw. 3, 323-334 (2011)
http://www.opticsinfobase.org/jocn/abstract.cfm?URI=jocn-3-4-323


Sort:  Author  |  Year  |  Journal  |  Reset  

References

  1. A. Hamad, T. Wu, A. E. Kamal, and A. K. Somani, "On multicasting in wavelength-routing mesh networks," Comput. Netw. 50, (15), 3105‒3164 (2006). [CrossRef]
  2. L. H. Sahasrabuddhe and B. Mukherjee, "Light-trees: optical multicasting for improved performance in wavelength-routed networks," IEEE Commun. Mag. 37, (2), 67‒73 (1999). [CrossRef]
  3. R. Malli, X. Zhang, and C. Qiao, "Benefit of multicasting in all-optical networks," Proc. SPIE 3531, 209‒220 (1998).
  4. M. Ali and J. S. Deogun, "Cost-effective implementation of multicasting in wavelength-routed networks," J. Lightwave Technol. 18, (12), 1628‒1638 (2000). [CrossRef]
  5. X. Jia, D. Du, X. Hu, M. Lee, and J. Gu, "Optimization of wavelength assignment for QoS multicast in WDM networks," IEEE Trans. Commun. 49, (2), 341‒350 (2001). [CrossRef]
  6. B. Mukherjee, "WDM optical communication networks: progress and challenges," IEEE J. Sel. Areas Commun. 18, (10), 1810‒1824 (2000). [CrossRef]
  7. X. Zhang, J. Wei, and C. Qiao, "Constrained multicast routing in WDM networks with sparse splitting," J. Lightwave Technol. 18, (12), 1917‒1927 (2000). [CrossRef]
  8. F. Zhou, M. Molnár, and B. Cousin, "Avoidance of multicast incapable branching nodes in WDM netwoks," Photonic Network Commun. 18, (3), 378‒392 (2009). [CrossRef]
  9. F. Zhou, M. Molnár, and B. Cousin, "Is light-tree structure optimal for multicast routing in sparse light splitting WDM networks?," 18th Int. Conf. on Computer Communications and Networks (IC3N’09), 2009, San Francisco, CA, pp. 1‒7.
  10. C.-Y. Hsieh and W. Liao, "All-optical multicast routing in sparse splitting WDM networks," IEEE J. Sel. Areas Commun. 25, (6), 51‒62 (2007). [CrossRef]
  11. H. Lin and S. Wang, "Splitter placement in all-optical WDM networks," IEEE Global Communications Conf. (GLOBECOM05), 2005, St. Louis, MO, pp. 306‒310.
  12. F. Zhou, M. Molnár, B. Cousin, and C. Qiao, "Cost bounds of multicast light-trees in WDM networks," 9th IFIP Int. Conf. on Networking (Networking 10), 2010, Chennai, India, pp. 94‒105.
  13. H. Takahashi and A. Matsuyama, "An approximate solution for the Steiner problem in graphs," Math. Japonica 24, (6), 573‒577 (1980).
  14. P. Winter, "Steiner problem in networks: a survey," Networks 17, (2), 129‒167 (1987). [CrossRef]
  15. F. Zhou, M. Molnár, B. Cousin, and C. Qiao, "Approximation ratios of multicast light-trees in WDM networks," IEEE Global Communications Conf. (GLOBECOM10), 2010, Miami, FL, pp. 1‒6.
  16. L. Kou, G. Markowsky, and L. Berman, "A fast algorithm for Steiner trees," Acta Inf. 15, (2), 141‒145 (1981). [CrossRef]
  17. M. Scheutzow, P. Seeling, M. Maier, and M. Reisslein, "Multicasting in a WDM-upgraded resilient packet ring," J. Opt. Netw. 6, (5), 415‒421 (2006). [CrossRef]
  18. M. Scheutzow, P. Seeling, M. Maier, and M. Reisslein, "Shortest path routing in optical WDM ring networks under multicast traffic," IEEE Commun. Lett. 10, (7), 564‒566 (2006).
  19. O. Yu and Y. Cao, "Mathematical formulation of optical multicast with loss-balanced light-forest," IEEE Global Communications Conf. (GLOBECOM05), 2005, St. Louis, MO, pp. 1788‒1792.
  20. M.-T. Chen, B. M. T. Lin, and S.-S. Tseng, "Multicast routing and wavelength assignment with delay constraints in WDM networks with heterogeneous capabilities," J. Netw. Comput. Appl. 31, (1), 47‒65 (2008). [CrossRef]
  21. http://www.ilog.com/products/cplex/
  22. http://www.algorithmic-solutions.com/leda/index.htm

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.

CrossCheck Deposited