Can I read An Online Throughput-competitive Algorithm for Multicast Routing and Admission Control on EtoBox?

An Online Throughput-competitive Algorithm for Multicast Routing and Admission Control by Ashish Goel; Monika R. Henzinger; Serge Plotkin is a Computer Science article available to read on EtoBox.

What is An Online Throughput-competitive Algorithm for Multicast Routing and Admission Control about?

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 dir&t function of the edne load. The new cost definition allows us to decouple the e&cts of routing and admission decisions o

Who reads An Online Throughput-competitive Algorithm for Multicast Routing and Admission Control?

Author

Ashish Goel; Monika R. Henzinger; Serge Plotkin

Publisher

Elsevier Science; Elsevier ; Academic Press; Elsevier BV (ISSN 0196-6774)

Published

2005

Language

EN

Field

Computer Science (Physical Sciences)