Abstract

In this paper, we investigate approaches and algorithms for establishing a multicast session in a mesh network while protecting the session against any single link failure, e.g., a fiber cut in an optical network. First, we study these approaches and algorithms to protect a single multicast tree in a mesh network and then extend it to dynamically provision survivable multicast connections (where connections come and go) in an optical wavelength-division multipexing (WDM) network. We propose two new and efficient approaches for protecting a multicast session: 1) segment protection in which we protect each segment in the primary tree separately (rather than the entire tree) and allow these backup segments to share edges with the other existing primary and backup segments and 2) the path-pair protection in which we find a path-pair (disjoint primary and backup paths) to each destination and allow a new path pair to share edges with already-found path pairs. Unlike previous schemes,such as finding link-disjoint trees and arc-disjoint trees, our new schemes 1) guarantee a solution where previous schemes fail and 2) find an efficient solution requiring less network resources. We study these approaches and algorithms systematically, starting with the existing approaches such as fully link-disjoint and arc-disjoint trees and then presenting our new and efficient proposed approaches, such as segment-disjoint and path-disjoint schemes for protecting multicast connections. Our most efficient algorithm, based on the path-pair protection scheme, called optimal path-pair-based shared disjoint paths (OPP-SDP) algorithm, finds a solution if such a solution exists and outperforms all the other schemes in terms of network cost. We also show that OPP-SDP performs close to the optimal solution obtained by solving a mathematical formulation of the problem expressed as an integer linear program. Building upon the study on protecting a single tree, we perform simulations,employing the above protection schemes, to study dynamic provisioning of survivable multicast sessions (where sessions come and go) in a WDM mesh network. Our simulations show that the most efficient scheme, OPP-SDP, has minimum blocking probability.

© 2003 IEEE

PDF Article

References

  • View by:
  • |

  1. N. Singhal, L. H. Sahasrabuddhe and B. Mukherjee, "Protecting a multicast session against single link failures in a mesh network", presented at the IEEE Int. Conf. Communications , Anchorage, AK, May 2003.
  2. N. Singhal, L. H. Sahasrabuddhe and B. Mukherjee, "Dynamic provisioning of survivable multicast sessions in optical WDM mesh networks", in Tech. Dig., Optical Fiber Communications, Atlanta, GA, Mar. 2003,Paper TuI5.
  3. B. Mukherjee, Optical Communication Networks, New York: McGraw-Hill, 1997.
  4. S. Paul, Multicasting on the Internet and Its Applications, Boston, MA: Kluwer, 1998.
  5. C. K. Miller, Multicast Networking and Applications, Reading, MA: Addison-Wesley, 1999.
  6. R. Malli, X. Zhang and C. Qiao, "Benefit of multicasting in all-optical networks", in Proc. SPIE Conf. All-Optical Networking, vol. 2531, Nov. 1998, pp. 209-220.
  7. Y. Sun, J. Gu and D. H. K. Tsang, "Multicast routing in all-optical wavelength routed networks", Optical Networks Mag., pp. 101-109, July/Aug. 2001.
  8. T. Znati, T. Alrabiah and R. Melhem, "Point-to-multi-point path establishment schemes to support multicasting in WDM networks", presented at the 3rd IFIP Working Conf. Optical Network Design Modeling (ONDM'98), Paris, France,1999.
  9. L. H. Sahasrabuddhe and B. Mukherjee, "Light-trees: Optical multicasting for improved performance in wavelength-routed networks", IEEE Commun. Mag. , vol. 37, pp. 67-73, Feb. 1999.
  10. N. Singhal and B. Mukherjee, "Architectures and algorithm for multicasting in WDM optical mesh netwoks using opaque and transparent optical cross-connects", in Tech. Dig., Optical Fiber Communications, Anaheim, CA, Mar. 2001,paper TuG8.
  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, Devices (ICCCD), IIT, vol. 2, Kharagpur, India,Dec. 2000, pp. 561-564.
  12. B. V. Caenegem, N. Wauters and P. Demeester, "Spare capacity assignment for different restoration strategies in mesh survivable networks", in Proc. Int. Conf. Communications , vol. 1, Montreal, QC, Canada, June 1997, pp. 288-292.
  13. B. V. Caenegem, W. V. Parys, F. D. Turck and P. M. Demeester, "Dimensioning of survivable WDM networks", IEEE J. Select. Areas Commun., vol. 16, pp. 1146-1157, Sept. 1998.
  14. O. Crochat and J. Y. Le Boudec, "Design protection for WDM optical networks", IEEE J. Select. Areas Commun., vol. 16, pp. 1158-1165, Sept. 1998.
  15. G. Ellinas, A. Hailemariam and T. E. Stern, "Protection cycles in mesh WDM networks", IEEE J. Select. Areas Commun., vol. 18, pp. 1924-1937, Oct. 2001.
  16. S. Ramamurthy and B. Mukherjee, "Survivable WDM mesh networks, part I-Protection", in Proc. IEEE INFOCOM, vol. 2, Mar. 2003, pp. 744-751.
  17. M. Medard, S. Finn, R. Barry and R. Gallager, "Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs", IEEE/ACM Trans. Networking , vol. 7, pp. 641-652, Oct. 1999.
  18. M. Medard, S. Finn and R. Barry, "Automatic protection switching for multicasting in optical mesh networks", in Proc. Optical Fiber Communications, 1997, Paper Th03,. pp. 314- 315.
  19. N. Singhal and B. Mukherjee, "Protecting multicast sessions in WDM optical mesh networks", J. Lightwave Technol., vol. 21, pp. 884-892, Apr. 2003.
  20. X. Zhang, J. Wei and C. Qiao, "Constrained multicast routing in WDM networks with sparse light splitting", in Proc. IEEE INFOCOM 2000, vol. 3, Tel Aviv, Israel,Mar. 2000, pp. 1781-1790.
  21. S. L. Hakimi, "Steiner's problem in graphs and its implications", Networks, vol. 1, no. 2, pp. 113-133, 1971.
  22. T. H. Corman, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, 2nd ed. Cambridge, MA: MIT Press, 2001.
  23. H. Takahashi and A. Matsuyama, "An approximate solution for the steiner problem in graphs", Math. Japonica, pp. 573-577, 1980.
  24. J. W. Suurballe, "Disjoint paths in a network", Networks , vol. 4, pp. 125-145, 1974.

J. Lightwave Technol. (1)

Other (23)

N. Singhal, L. H. Sahasrabuddhe and B. Mukherjee, "Protecting a multicast session against single link failures in a mesh network", presented at the IEEE Int. Conf. Communications , Anchorage, AK, May 2003.

N. Singhal, L. H. Sahasrabuddhe and B. Mukherjee, "Dynamic provisioning of survivable multicast sessions in optical WDM mesh networks", in Tech. Dig., Optical Fiber Communications, Atlanta, GA, Mar. 2003,Paper TuI5.

B. Mukherjee, Optical Communication Networks, New York: McGraw-Hill, 1997.

S. Paul, Multicasting on the Internet and Its Applications, Boston, MA: Kluwer, 1998.

C. K. Miller, Multicast Networking and Applications, Reading, MA: Addison-Wesley, 1999.

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

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

T. Znati, T. Alrabiah and R. Melhem, "Point-to-multi-point path establishment schemes to support multicasting in WDM networks", presented at the 3rd IFIP Working Conf. Optical Network Design Modeling (ONDM'98), Paris, France,1999.

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

N. Singhal and B. Mukherjee, "Architectures and algorithm for multicasting in WDM optical mesh netwoks using opaque and transparent optical cross-connects", in Tech. Dig., Optical Fiber Communications, Anaheim, CA, Mar. 2001,paper TuG8.

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, Devices (ICCCD), IIT, vol. 2, Kharagpur, India,Dec. 2000, pp. 561-564.

B. V. Caenegem, N. Wauters and P. Demeester, "Spare capacity assignment for different restoration strategies in mesh survivable networks", in Proc. Int. Conf. Communications , vol. 1, Montreal, QC, Canada, June 1997, pp. 288-292.

B. V. Caenegem, W. V. Parys, F. D. Turck and P. M. Demeester, "Dimensioning of survivable WDM networks", IEEE J. Select. Areas Commun., vol. 16, pp. 1146-1157, Sept. 1998.

O. Crochat and J. Y. Le Boudec, "Design protection for WDM optical networks", IEEE J. Select. Areas Commun., vol. 16, pp. 1158-1165, Sept. 1998.

G. Ellinas, A. Hailemariam and T. E. Stern, "Protection cycles in mesh WDM networks", IEEE J. Select. Areas Commun., vol. 18, pp. 1924-1937, Oct. 2001.

S. Ramamurthy and B. Mukherjee, "Survivable WDM mesh networks, part I-Protection", in Proc. IEEE INFOCOM, vol. 2, Mar. 2003, pp. 744-751.

M. Medard, S. Finn, R. Barry and R. Gallager, "Redundant trees for preplanned recovery in arbitrary vertex-redundant or edge-redundant graphs", IEEE/ACM Trans. Networking , vol. 7, pp. 641-652, Oct. 1999.

M. Medard, S. Finn and R. Barry, "Automatic protection switching for multicasting in optical mesh networks", in Proc. Optical Fiber Communications, 1997, Paper Th03,. pp. 314- 315.

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

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

T. H. Corman, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, 2nd ed. Cambridge, MA: MIT Press, 2001.

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

J. W. Suurballe, "Disjoint paths in a network", Networks , vol. 4, pp. 125-145, 1974.

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.