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

Goel A, Henzinger MH, Plotkin S. 2005. An online throughput-competitive algorithm for multicast routing and admission control. Journal of Algorithms. 55(1), 1–20.

Download (ext.)

Journal Article | Published | English

Scopus indexed
Author
Goel, Ashish; Henzinger, MonikaISTA ; Plotkin, Serge
Abstract
We present the first polylog-competitive online algorithm for the general multicast admission control and routing problem in the throughput model. The ratio of the number of requests accepted by the optimum offline algorithm to the expected number of requests accepted by our algorithm is O((log 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 graph. We show that this is close to optimum by presenting an Ω(log n log M) lower bound on this ratio for any randomized online algorithm against an oblivious adversary, when M is much larger 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 previous competitive algorithms in the throughput model, our cost is not a direct function of the edge load. The new cost definition allows us to decouple the effects of routing and admission decisions of different multicast groups.
Publishing Year
Date Published
2005-04-01
Journal Title
Journal of Algorithms
Publisher
Elsevier
Volume
55
Issue
1
Page
1-20
ISSN
IST-REx-ID

Cite this

Goel A, Henzinger MH, Plotkin S. An online throughput-competitive algorithm for multicast routing and admission control. Journal of Algorithms. 2005;55(1):1-20. doi:10.1016/j.jalgor.2004.11.001
Goel, A., Henzinger, M. H., & Plotkin, S. (2005). An online throughput-competitive algorithm for multicast routing and admission control. Journal of Algorithms. Elsevier. https://doi.org/10.1016/j.jalgor.2004.11.001
Goel, Ashish, Monika H Henzinger, and Serge Plotkin. “An Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control.” Journal of Algorithms. Elsevier, 2005. https://doi.org/10.1016/j.jalgor.2004.11.001.
A. Goel, M. H. Henzinger, and S. Plotkin, “An online throughput-competitive algorithm for multicast routing and admission control,” Journal of Algorithms, vol. 55, no. 1. Elsevier, pp. 1–20, 2005.
Goel A, Henzinger MH, Plotkin S. 2005. An online throughput-competitive algorithm for multicast routing and admission control. Journal of Algorithms. 55(1), 1–20.
Goel, Ashish, et al. “An Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control.” Journal of Algorithms, vol. 55, no. 1, Elsevier, 2005, pp. 1–20, doi:10.1016/j.jalgor.2004.11.001.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data ISTA Research Explorer

Search this title in

Google Scholar