Earlier Version

An online throughput-competitive algorithm for multicast routing and admission control

Goel A, Henzinger MH, Plotkin S. 1998. An online throughput-competitive algorithm for multicast routing and admission control. 9th Annual ACM SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 97–106.

Download
No fulltext has been uploaded. References only!
Conference Paper | Published | English

Scopus indexed
Author
Goel, Ashish; Henzinger, MonikaISTA ; Plotkin, Serge
Abstract
We present the first polylog-competitive online algorithm for the general multicast problem in the throughput model. The ratio of the number of requests accepted by the optimum offline alaorithm to the exoected number of reauests accepted by our algorithm is O(jlog n + log log M)(log n + log M) log n), where M is the number of multicast groups and n is the number of nodes in the nraoh. We show that this is close to optimum by presenting-an*R(log nlog M) lower bound on this ratio for anv randomized online algorithm against an oblivious adversary, when M is much lar&r than the link capacities. Our lower bound applies even in the restricted case where the link capacities are much larger than bandwidth requested by a single multicast. We also present a simple proof showing that it is impossible to be competitive against an adaptive online adversary. As in the previous online routing algorithms, our algorithm uses edge-costs when deciding on which is the best path to use. In contrast to the nrevious comnetitive aleorithms in the throughput modei, our cost is-not a direct function of the edne load. The new cost definition allows us to decouple the effects of routing and admission decisions of different multicast groups.
Publishing Year
Date Published
1998-01-01
Proceedings Title
9th Annual ACM SIAM Symposium on Discrete Algorithms
Publisher
Society for Industrial and Applied Mathematics
Page
97-106
Conference
SODA: Symposium on Discrete Algorithms
Conference Location
San Francisco, CA, United States
Conference Date
1998-01-25 – 1998-01-27
ISBN
IST-REx-ID

Cite this

Goel A, Henzinger MH, Plotkin S. An online throughput-competitive algorithm for multicast routing and admission control. In: 9th Annual ACM SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 1998:97-106.
Goel, A., Henzinger, M. H., & Plotkin, S. (1998). An online throughput-competitive algorithm for multicast routing and admission control. In 9th Annual ACM SIAM Symposium on Discrete Algorithms (pp. 97–106). San Francisco, CA, United States: Society for Industrial and Applied Mathematics.
Goel, Ashish, Monika H Henzinger, and Serge Plotkin. “An Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control.” In 9th Annual ACM SIAM Symposium on Discrete Algorithms, 97–106. Society for Industrial and Applied Mathematics, 1998.
A. Goel, M. H. Henzinger, and S. Plotkin, “An online throughput-competitive algorithm for multicast routing and admission control,” in 9th Annual ACM SIAM Symposium on Discrete Algorithms, San Francisco, CA, United States, 1998, pp. 97–106.
Goel A, Henzinger MH, Plotkin S. 1998. An online throughput-competitive algorithm for multicast routing and admission control. 9th Annual ACM SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 97–106.
Goel, Ashish, et al. “An Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control.” 9th Annual ACM SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 1998, pp. 97–106.

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar
ISBN Search