Skip to main content
Log in

Optimal multicast routing with quality of service constraints

  • Papers
  • Published:
Journal of Network and Systems Management Aims and scope Submit manuscript

Abstract

We consider the problem of optimal multicast routing with Quality of Service constraints motivated by the requirements of interactive continuous media communication, e.g., real-time teleconferencing. We concentrate on distributed algorithms for determining a tree over the network topology, rooted at the source and spanning the intended destinations. Quality of Service requirements for interactive continuous media typically impose constraints on some metric over the individual paths from the source to each destination, usually in the form of an upper bound on the delay. Thus, we focus on the problem of minimizing the cost of the tree while at the same time satisfying a common constraint over individual source-destination paths. We have shown that this problem is intractable, but have also devised centralized polynomial time heuristics that perform well. Here we present distributed algorithms to minimize tree cost while satisfying the constraints on the paths from the source to each destination.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. Sabri and B. Prasada, Video conferencing systems,Proc. of the IEEE, Vol. 73, No. 4, pp. 671–688, April 1985.

    Google Scholar 

  2. S. Casner, K. Seo, W. Edmond, and C. Topolcic,N-way conferencing with packet video,Third International Workshop on Packet Video, March 1990.

  3. W. D. Sincoskie, System architecture for a large scale video on demand service,Computer Networks and ISDN Systems, North-Holland, Vol. 22, No. 2, pp 155–162, 1991.

    Google Scholar 

  4. J. Sutherland and L. Litteral, Residential Video Services,IEEE Comm. Mag., Vol. 30, No. 7, pp. 36–41, July 1992.

    Google Scholar 

  5. B. Leiner, Ed., Critical issues in high-speed networking, RFC1077, Network Information Center, SRI International, Menlo Park, California, November 1988.

    Google Scholar 

  6. C. Partridge, Workshop Report, Internet research steering group workshop on very-high-speed networks, RFC1152, Network Information Center, SRI International, Menlo Park, California, April 1990.

    Google Scholar 

  7. AT&T Bell Laboratories, Engineering and Operations in the Bell System, 1984.

  8. D. Ferrari, Client requirements for real-time communication services,IEEE Communications Magazine, Vol. 28, No. 11, pp. 65–72, November 1990.

    Google Scholar 

  9. D. C. Verma, H. Zhang, and D. Ferrari, Delay jitter control for real-time communication in a packet switching network,Proc. TriComm '91, pp. 35–43, April 1991.

  10. A. J. Frank, L. D. Wittie and A. J. Bernstein, Multicast communication on network computers,IEEE Software, Vol. 2, No. 3, pp. 49–61, 1985.

    Google Scholar 

  11. M. Ahamad, (ed.),Multicast Communication in Distributed Systems, IEEE Computer Society Press, Technology Series, 1990

  12. S. Deering and D. Cheriton, Multicast routing in Internetworks and extended LANs,ACM Trans. on Computer Systems, Vol. 8, No. 2, pp. 85–110, May 1990.

    Google Scholar 

  13. M. R. Macedonia and D. P. Brutzman, MBone provides audio and video across the Internet,IEEE Computer, Vol. 27, No. 4, pp. 30–36, April 1994.

    Google Scholar 

  14. L. Zhang, S. Deering, D. Estrin, S. Shenker, and D. Zappala, RSVP: A new resource ReSerVation protocol,IEEE Network, Vol. 7, No. 5, pp. 8–18, September 1993.

    Google Scholar 

  15. T. Ballardie, P. Francis, and J. Crowcroft, Core Based Trees (CBT): An architecture for scalable inter-domain multicast routing,Proc. ACM SIGCOMM'93, San Francisco California, pp. 85–95, September, 1993.

  16. K. Y. Eng, M. G. Hluchyj, and Y. S. Yeh, Multicast and broadcast services in a knockout packet switch,Proc. IEEE INFOCOM'88, pp. 29–34 March 1988.

  17. J. S. Turner, Design of a broadcast packet switching network,IEEE Trans. on Comm., Vol. 36, No. 6, pp. 734–743, June 1988.

    Google Scholar 

  18. T. T. Lee, Nonblocking copy networks for multicast packet switching,IEEE Journal Selected Areas in Communications, Vol. 6, No. 9, pp. 1455–1467, December 1988.

    Google Scholar 

  19. D. C. Verma and P. M. Gopal, Routing reserved bandwidth multi-point connections,Proc. ACM SIGCOMM'93, San Francisco, California, pp. 96–105, September 1993.

  20. W. Yen and I. Akyildiz, Hierarchical Multicast Routing Protocol,9th IEEE Workshop on Computer Comm. Marathon, Florida, October 1994.

  21. E. W. Dijkstra, A note on two problems in connexion with graphs,Numerische Mathematik, Vol. 1, pp. 269–271, 1959.

    Google Scholar 

  22. S. L. Hakimi, Steiner's problem in graphs and its implications,Networks, Vol. 1, pp. 113–133, 1971.

    Google Scholar 

  23. R. M. Karp, Reducibility among combinatorial problems, In R. E. Miller and J. W. Thatcher, (eds.),Complexity of Computer Computations, pp. 85–103, Plenum Press, New York, 1972.

    Google Scholar 

  24. C.-H. Chow, On multicast path finding algorithms,Proc. IEEE INFOCOM'91, New York, pp. 1274–1283, 1991.

  25. B. K. Kadaba and J. M. Jaffe, Routing to multiple destinations in computer networks,IEEE Trans. on Comm., Vol. 31, No. 3, pp. 343–351, March 1983.

    Google Scholar 

  26. D. W. Wall, Mechanisms for broadcast and selective broadcast, Ph.D. Thesis, Electrical Engineering Department, Stanford University, June 1980.

  27. B. M. Waxman, Routing of multipoint connections,IEEE J. on Selected Areas in Comm., Vol. 6, No. 9, pp. 1617–1622, December 1988.

    Google Scholar 

  28. L. Kou, G. Markowsky, and L. Berman, A fast algorithm for Steiner trees,Acta Informatica, Vol. 15, pp. 141–145, 1981.

    Google Scholar 

  29. V. J. Rayward-Smith, The computation of nearly minimal Steiner trees in graphs,Intl. J. Math. Educ. Sci. Tech., Vol. 14, No. 1, pp. 15–23, 1983.

    Google Scholar 

  30. H. Takahashi and A. Matsuyama, An approximate solution for the Steiner problem in graphs,Math. Japonica, Vol. 6, pp. 573–577, 1980.

    Google Scholar 

  31. V. P. Kompella, J. C. Pasquale, and G. C. Polyzos, Multicasting for multimedia applications,Proc. IEEE INFOCOM'92, Florence, Italy, pp. 2078–2085, May 1992.

  32. V. P. Kompella, J. C. Pasquale, and G. C. Polyzos, Multicast routing for multimedia communication,IEEE/ACM Trans. on Networking, Vol. 1, No. 3, pp. 286–292, June 1993.

    Google Scholar 

  33. R. E. Bellman,Dynamic Programming, Princeton University Press, Princeton, New Jersey, 1957.

    Google Scholar 

  34. R. G. Gallager, P. A. Humblett, and P. M. Spira, A distributed algorithm for minimum-weight spanning trees,ACM Trans. on Prog. Lang. Syst., Vol. 5, pp. 66–77, 1983.

    Google Scholar 

  35. L. Aguilar, J. J. Garcia-Luna-Aceves, D. Moran, E. J. Craighill, and R. Brungardt, Architecture for a multimedia teleconferencing system,Proc. ACM SIGCOMM'86, pp. 126–136, August 1986.

Download references

Author information

Authors and Affiliations

Authors

Rights and permissions

Reprints and permissions

About this article

Cite this article

Kompella, V.P., Pasquale, J.C. & Polyzos, G.C. Optimal multicast routing with quality of service constraints. J Netw Syst Manage 4, 107–131 (1996). https://doi.org/10.1007/BF02139130

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02139130

Key Words

Navigation