Optimal Multicast Routing with Quality of Service Constraints [Vol. 4, No. 2, 1996]

Optimal Multicast Routing with Quality of Service Constraints

Vachaspathi P. Kompella
IBM Corp.
Networking Systems Laboratory
P.O. Box 12195
Research Triangle Park, North Carolina, 27709
Email: vkompella_AT_vnet.ibm.com

Joseph C. Pasquale
Computer Systems Laboratory
Department of Computer Science and Engineering
University of California, San Diego
La Jolla, California 92093-0014
Email: pasquale_AT_cs.ucsd.edu

George C. Polyzos
Computer Systems Laboratory
Department of Computer Science and Engineering
University of California, San Diego
La Jolla, California 92093-0114
Email: polyzos_AT_cs.ucsd.edu

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 concentrated 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.

Keywords: Multipoint routing; multimedia communications; interactive continuous media; Steiner tree.

JNSM: Vol. 4, No. 2, 1996 Optimal Multicast Routing with Quality of Service Constraints [Vol. 4, No. 2, 1996]

NOTE: only abstract of paper available on-line

Back to JNSM main page