Report Number: CS-TR-97-1592
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