Institution: Stanford University, Department of Computer Science

Title: Online Throughput-Competitive Algorithm for Multicast Routing and Admission Control

Author: Goel, Ashish

Author: Henzinger, Monika R.

Author: Plotkin, Serge

Date: July 1997

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 algorithm to the expected number of requests accepted by our algorithm is polylogarithmic in M and 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 Omega(log n log M) lower bound on this ratio for any randomized online algorithm against an oblivious adversary. We also show 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 new cost definition allows us to decouple the effects of routing and admission decisions of different multicast groups.

http://i.stanford.edu/pub/cstr/reports/cs/tr/97/1592/CS-TR-97-1592.pdf