article

Optimal multicasting of multiple light-trees of different bandwidth granularities in a WDM mesh network with sparse splitting capabilities

Authors:

Narendra K. Singhal,

Laxman H. Sahasrabuddhe,

Biswanath MukherjeeAuthors Info & Claims

IEEE/ACM Transactions on Networking (TON), Volume 14, Issue 5

Pages 1104 - 1117

https://doi.org/10.1109/TNET.2006.882840

Published: 01 October 2006 Publication History

Abstract

With the advent of next-generation, bandwidth-intensive multimedia applications such as HDTV, interactive distance learning, and movie broadcasts from studios, it is becoming imperative to exploit the enormous bandwidth promised by the rapidly growing wavelength-division-multiplexing (WDM) technology. These applications require multicasting of information from a source to several destination nodes which should be performed judiciously to conserve expensive network resources. In this study, we investigate two switch architectures to support multicasting in a WDM network: one using an opaque (optical-electronic-optical approach and the other using a transparent (all-optical) approach. For both these switch architectures, we present mathematical formulations for routing and wavelength assignment of several light-tree-based multicast sessions on a given network topology at a globally optimal cost. We expand our work to also accommodate: 1) fractional-capacity sessions (where a session's capacity is a fraction of a wavelength channel's bandwidth, thereby leading to "traffic-groomed" multicast sessions) and 2) sparse splitting constraints, i.e., limited fanout of optical splitters and limited number of such splitters at each node. We illustrate the solutions obtained on different networks by solving these optimization problems, which turn out to be mixed integer linear programs (MILPs). Because the MILP is computationally intensive and does not scale well for large problem sizes, we also propose fast heuristics for establishing a set of multicast sessions in a network with or without wavelength converters and with fractional-capacity sessions. We find that, for all scenarios, the heuristics which arrange the sessions in ascending order with respect to destination set size and/or cost perform better in terms of network resource usage than the heuristics which arrange the sessions in descending order.

References

[1]

{1} B. Mukherjee, Optical WDM Networks. Berlin, Germany: Springer-Verlag, 2006.

[2]

{2} R. Ramaswami and K. Sivarajan, Optical Networks - A Practical Perspective , 2nd ed. San Mateo, CA: Morgan Kaufmann, 2001.

[3]

{3} L. H. Sahasrabuddhe and B. Mukherjee, "Light-trees: Optical multicasting for improved performance in wavelength-routed networks," IEEE Commun. Mag., vol. 37, no. 2, pp. 67-73, Feb. 1999.

[4]

{4} X. Zhang, J. Wei, and C. Qiao, "Constrained multicast routing in WDM networks with sparse light splitting," in Proc. IEEE INFOCOM, Tel Aviv, Israel, Mar. 2000, vol. 3, pp. 1781-1790.

[5]

{5} R. Malli, X. Zhang, and C. Qiao, "Benefit of multicasting in all-optical networks," in Proc. SPIE Conf. All-Optical Networks, Nov. 1998, vol. 2531, pp. 209-220.

[6]

{6} L. H. Sahasrabuddhe and B. Mukherjee, "Multicast routing algorithms and protocols: A tutorial," IEEE Network, vol. 14, no. 1, pp. 90-102, Jan./Feb. 2000.

[7]

{7} G. N. Rouskas, "Optical layer multicast: Rationale, building blocks, and challenges," IEEE Network, vol. 17, no. 1, pp. 60-65, Jan./Feb. 2003.

[8]

{8} S. Sankaranarayanan and S. Subramaniam, "Comprehensive performance modeling and analysis of multicasting in optical networks," IEEE J. Sel. Areas Commun., vol. 21, no. 11, pp. 1399-1413, Nov. 2003.

[9]

{9} I. Chlamtac, A. Ganz, and G. Karmi, "Lightpath communications: An approach to high bandwidth optical WAN's," IEEE Trans. Commun., vol. 40, no. 7, pp. 1171-1182, Jul. 1992.

[10]

{10} N. Singhal and B. Mukherjee, "Architectures and algorithm for multicasting in WDM optical mesh networks using opaque and transparent optical cross-connects," in OFC Tech. Dig., Anaheim, CA, Mar. 2001, paper TuG8.

[11]

{11} L. H. Sahasrabuddhe, N. Singhal, and B. Mukherjee, "Light-trees for optical networks: Optimization problem formulation for unicast and broadcast traffic," in Proc. Int. Conf. Communications, Computers, and Devices (ICCCD), Kharagpur, India, Dec. 2000, vol. 2, pp. 561-564.

[12]

{12} V. Kompella, J. Pasquale, and G. Polyzos, "Multicast routing for multimedia communications," IEEE/ACM Trans. Netw., vol. 1, no. 3, pp. 286-292, Jun. 1993.

[13]

{13} J. He, S. H. Chan, and D. H. K. Tsang, "Routing and wavelength assignment for WDM multicast networks," in Proc. IEEE GLOBECOM, San Antonio, TX, Nov. 2001, vol. 3, pp. 1536-1540.

[14]

{14} R. K. Pankaj, "Wavelength requirements for multicasting in all-optical networks," IEEE/ACM Trans. Netw., vol. 7, no. 3, pp. 414-424, Jun. 1999.

[15]

{15} H. Takahashi and A. Matsuyama, "An approximate solution for the Steiner problem in graphs," Math. Japonica, vol. 24, pp. 573-577, 1980.

[16]

{16} F. K. Hwang and D. S. Richards, "Steiner tree problems," Networks, vol. 22, no. 1, pp. 55-89, 1992.

[17]

{17} S. L. Hakimi, "Steiner's problem in graphs and its implications," Networks , vol. 1, no. 2, pp. 113-133, 1971.

[18]

{18} M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. San Francisco, CA: Freeman, 1979.

[19]

{19} S. Ramanathan, "Multicast tree generation in networks with asymmetric links," IEEE/ACM Trans. Netw., vol. 4, no. 4, pp. 558-568, Aug. 1996.

[20]

{20} B. Chen and J. Wang, "Efficient routing and wavelength assignment for multicast in WDM network," IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 97-109, Jan. 2002.

[21]

{21} D. Hoffman, G. Fernando, V. Goyal, and M. Civanlar, "RTP payload format for MPEG1/MPEG2 video," RFC 2250, 1998.

[22]

{22} S. Ramesh, G. N. Rouskas, and H. G. Perros, "Computing blocking probabilities in multiclass wavelength-routing networks with multicast calls," IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 89-96, Jan. 2002.

[23]

{23} Y. Sun, J. Gu, and D. H. K. Tsang, "Multicast routing in all-optical wavelength routed networks," Opt. Networks Mag., pp. 101-109, Jul./ Aug. 2001.

[24]

{24} N. Sreenath and C. S. R. Murthy, "Virtual source based multicast routing in WDM optical networks," Photon. Network Commun., vol. 3, no. 3, pp. 213-226, 2001.

[25]

{25} X. Jia, D. Du, X. Hu, M. Lee, and J. Gu, "Optimization of wavelength assignment for QoS multicast in WDM networks," IEEE Trans. Commun., vol. 49, no. 2, pp. 341-350, Feb. 2001.

[26]

{26} N. K. Singhal, L. H. Sahasrabuddhe, and B. Mukherjee, "Provisioning of survivable multicast sessions against single link failures in optical WDM mesh network," J. Lightwave Technol., vol. 21, no. 11, pp. 2587-2594, Nov. 2003.

[27]

{27} N. K. Singhal, C. Ou, and B. Mukherjee, "Cross-sharing versus self-sharing trees for protecting multicast sessions in mesh networks," J. Comput. Networks, vol. 50, no. 2, pp. 200-206, Feb. 2006.

[28]

{28} M. Ali and J. Deogun, "Power-efficient design of multicast wavelength-routed networks," IEEE J. Sel. Areas Commun., vol. 18, no. 10, pp. 1852-1862, Oct. 2000.

[29]

{29} R. Libeskind-Hadas, "Efficient collective communication in WDM networks with a power budget," in Proc. 9th IEEE Int. Conf. Computer Communications and Networks (ICCCN), Las Vegas, NV, Oct. 2000, pp. 612-616.

[30]

{30} F. Bauer and A. Varma, "Degree-constrained multicasting in point-to-point networks," in Proc. IEEE INFOCOM, Apr. 1995, vol. 4, pp. 369-376.

[31]

{31} S. Voss, "Steiner-probleme in graphen," Frankfurt/Main: Hain, pp. 179-184, 1990.

[32]

{32} R. Ramaswami and K. Sivarajan, "Optimal routing and wavelength assignment in all-optical networks," in Proc. IEEE INFOCOM, Toronto, ON, Canada, Jun. 1994, vol. 1, pp. 110-119.

[33]

{33} G. Sahin and M. Azizoglu, "Multicast routing and wavelength assignment in wide area networks," in Proc. SPIE Conf. All-Optical Networks , Oct. 1998, vol. 3531, pp. 196-208.

[34]

{34} B. Ramamurthy and B. Mukherjee, "Wavelength conversion in optical networks: Progress and challenges," IEEE J. Sel. Areas Commun., vol. 16, no. 9, pp. 1040-1050, Sep. 1998.

[35]

{35} J. Iness and B. Mukherjee, "Sparse wavelength conversion in wavelength-routed WDM networks," Photon. Network Commun. J., vol. 1, no. 3, pp. 183-205, Nov. 1999.

[36]

{36} H. Shen and W. Liang, "Efficient multiple multicast in WDM networks," in Proc. Int. Conf. Parallel and Distributed Processing Techniques and Applications, Jul. 1998, vol. 2, pp. 1028-1033.

[37]

{37} B. Ma and L. Wang, "On the inapproximability of disjoint paths and minimum Steiner forest with bandwidth constraints," J. Comput. Syst. Sci., vol. 60, pp. 1-12, 2000.

[38]

{38} K. Zhu and B. Mukherjee, "Traffic grooming in an optical WDM mesh network," IEEE J. Sel. Areas Commun., vol. 20, no. 1, pp. 122-133, Jan. 2002.

[39]

{39} M. Ali, "Optimization of splitting node placement in wavelength-routed optical networks," IEEE J. Sel. Areas Commun., vol. 20, no. 10, pp. 1571-1578, Oct. 2002.

[40]

{40} H. Takahashi and A. Matsuyama, "An approximate solution for the Steiner problem in graphs," Math. Japonica, pp. 573-577, 1980.

[41]

{41} C. Chen and S. Banerjee, "A new model for optimal routing and wavelength assignment in wavelength division multiplexed optical networks," in Proc. IEEE INFOCOM, Mar. 1996, vol. 1, pp. 164-171.

[42]

{42} H. Zang, J. P. Jue, and B. Mukherjee, "A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks," Opt. Networks Mag., vol. 1, no. 1, pp. 47-60, Jan. 2000.

Cited By

Zakouni ALuo JKharroubi F(2017)Genetic algorithm and tabu search algorithm for solving the static manycast RWA problem in optical networksJournal of Combinatorial Optimization10.1007/s10878-016-0002-333:2(726-741)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1007/s10878-016-0002-3
Yang WYang CHuang Y(2016)Optimal and heuristic algorithms for all-optical group multicast in resource-constrained WDM networksInternational Journal of Communication Systems10.1002/dac.316529:15(2292-2312)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1002/dac.3165
Panayiotou TEllinas GAntoniades NHadjiantonis A(2015)Impairment-aware multicast session provisioning in metro optical networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.09.00491:C(675-688)Online publication date: 14-Nov-2015
https://dl.acm.org/doi/10.1016/j.comnet.2015.09.004
Show More Cited By

Index Terms

Optimal multicasting of multiple light-trees of different bandwidth granularities in a WDM mesh network with sparse splitting capabilities

Recommendations

Design methodology for WDM backbone networks using FWM-aware heuristic algorithm

The problem of lightpath topology design (LTD) and traffic routing over the lightpaths for wavelength-routed optical backbone networks has been investigated extensively in the past using heuristic as well as linear-programming based approaches. ...
Light-tree configuration for multicast traffic grooming in WDM mesh networks

Recent advances in wavelength-division multiplexing (WDM) technology will provide bandwidth intensive multicast applications with large transmit capacities. This article provides two new grooming schemes that lead to efficient resource utilization in ...
Resource efficient multicast traffic grooming in WDM mesh networks

In this paper, we have considered an optimal design and provisioning of WDM networks for the grooming of sub-wavelengths traffic requests. As higher layer electronic ports, such as transceivers and optical splitters are dominant cost factors of an optical ...

Comments

Information & Contributors

Information

Published In

cover image IEEE/ACM Transactions on Networking

IEEE/ACM Transactions on Networking Volume 14, Issue 5

October 2006

226 pages

ISSN:1063-6692

Issue’s Table of Contents

Publisher

IEEE Press

Publication History

Published: 01 October 2006

Published in TON Volume 14, Issue 5

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
528
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zakouni ALuo JKharroubi F(2017)Genetic algorithm and tabu search algorithm for solving the static manycast RWA problem in optical networksJournal of Combinatorial Optimization10.1007/s10878-016-0002-333:2(726-741)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1007/s10878-016-0002-3
Yang WYang CHuang Y(2016)Optimal and heuristic algorithms for all-optical group multicast in resource-constrained WDM networksInternational Journal of Communication Systems10.1002/dac.316529:15(2292-2312)Online publication date: 1-Oct-2016
https://dl.acm.org/doi/10.1002/dac.3165
Panayiotou TEllinas GAntoniades NHadjiantonis A(2015)Impairment-aware multicast session provisioning in metro optical networksComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2015.09.00491:C(675-688)Online publication date: 14-Nov-2015
https://dl.acm.org/doi/10.1016/j.comnet.2015.09.004
Lin HZhuang YLin M(2015)Bandwidth-ratio-based light-tree selection in dynamic multicast traffic grooming for optical WDM mesh networksPhotonic Network Communications10.1007/s11107-014-0480-029:2(164-182)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1007/s11107-014-0480-0
Sierra JCaro LMarzo JFabregat RSolano FDonoso Y(2010)Impact of the number of SAB on architectures that support unicast/multicast traffic in WDM networksInternational Journal of Communication Networks and Distributed Systems10.1504/IJCNDS.2010.0297394:1(90-107)Online publication date: 1-Dec-2010
https://dl.acm.org/doi/10.1504/IJCNDS.2010.029739
Lin RZhong WBose SZukerman M(2010)Light-tree configuration for multicast traffic grooming in WDM mesh networksPhotonic Network Communications10.1007/s11107-010-0255-120:2(151-164)Online publication date: 1-Oct-2010
https://dl.acm.org/doi/10.1007/s11107-010-0255-1
Pedroso PPedrola OPapadimitriou DKlinkowski MCareglio D(2009)Anytraffic routing algorithm for label-based forwardingProceedings of the 28th IEEE conference on Global telecommunications10.5555/1811982.1812236(5158-5165)Online publication date: 30-Nov-2009
https://dl.acm.org/doi/10.5555/1811982.1812236
Andrei DTornatore MMartel CMukherjee B(2009)Flexible scheduling of multicast sessions with different granularities for large data distribution over WDM networksProceedings of the 28th IEEE conference on Global telecommunications10.5555/1811681.1811808(2576-2581)Online publication date: 30-Nov-2009
https://dl.acm.org/doi/10.5555/1811681.1811808
Yan FHu WSun WHe H(2009)Wavelength assignment algorithm in optical multicast networks with multi-wavelength conversionProceedings of the 15th Asia-Pacific conference on Communications10.5555/1803074.1803201(516-519)Online publication date: 8-Oct-2009
https://dl.acm.org/doi/10.5555/1803074.1803201
Cha MArt Chaovalitwongse WYates JShaikh AMoon S(2009)Efficient and scalable provisioning of always-on multicast streaming servicesComputer Networks: The International Journal of Computer and Telecommunications Networking10.1016/j.comnet.2009.07.00553:16(2825-2839)Online publication date: 1-Nov-2009
https://dl.acm.org/doi/10.1016/j.comnet.2009.07.005

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents