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.
Similar content being viewed by others
References
S. Sabri and B. Prasada, Video conferencing systems,Proc. of the IEEE, Vol. 73, No. 4, pp. 671–688, April 1985.
S. Casner, K. Seo, W. Edmond, and C. Topolcic,N-way conferencing with packet video,Third International Workshop on Packet Video, March 1990.
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.
J. Sutherland and L. Litteral, Residential Video Services,IEEE Comm. Mag., Vol. 30, No. 7, pp. 36–41, July 1992.
B. Leiner, Ed., Critical issues in high-speed networking, RFC1077, Network Information Center, SRI International, Menlo Park, California, November 1988.
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.
AT&T Bell Laboratories, Engineering and Operations in the Bell System, 1984.
D. Ferrari, Client requirements for real-time communication services,IEEE Communications Magazine, Vol. 28, No. 11, pp. 65–72, November 1990.
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.
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.
M. Ahamad, (ed.),Multicast Communication in Distributed Systems, IEEE Computer Society Press, Technology Series, 1990
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.
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.
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.
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.
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.
J. S. Turner, Design of a broadcast packet switching network,IEEE Trans. on Comm., Vol. 36, No. 6, pp. 734–743, June 1988.
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.
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.
W. Yen and I. Akyildiz, Hierarchical Multicast Routing Protocol,9th IEEE Workshop on Computer Comm. Marathon, Florida, October 1994.
E. W. Dijkstra, A note on two problems in connexion with graphs,Numerische Mathematik, Vol. 1, pp. 269–271, 1959.
S. L. Hakimi, Steiner's problem in graphs and its implications,Networks, Vol. 1, pp. 113–133, 1971.
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.
C.-H. Chow, On multicast path finding algorithms,Proc. IEEE INFOCOM'91, New York, pp. 1274–1283, 1991.
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.
D. W. Wall, Mechanisms for broadcast and selective broadcast, Ph.D. Thesis, Electrical Engineering Department, Stanford University, June 1980.
B. M. Waxman, Routing of multipoint connections,IEEE J. on Selected Areas in Comm., Vol. 6, No. 9, pp. 1617–1622, December 1988.
L. Kou, G. Markowsky, and L. Berman, A fast algorithm for Steiner trees,Acta Informatica, Vol. 15, pp. 141–145, 1981.
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.
H. Takahashi and A. Matsuyama, An approximate solution for the Steiner problem in graphs,Math. Japonica, Vol. 6, pp. 573–577, 1980.
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.
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.
R. E. Bellman,Dynamic Programming, Princeton University Press, Princeton, New Jersey, 1957.
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.
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.
Author information
Authors and Affiliations
Rights 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
Issue Date:
DOI: https://doi.org/10.1007/BF02139130