|
Abstract : |
On-line multicasting has received a lot of attention lately, because of its great practical importance. However, most research assumes undirected graphs, which fail to model the directivity of real networks. In this paper, we fill this gap by offering upper and lower bounds for the on-line directed multicast problem in a worst case analysis. We examine two types of on-line problems: the join-only problem where destinations join arbitrarily but stay till the end of the session, and the join-leave problem, where destinations can join and leave arbitrarily. We define the asymmetry of a graph to be the maximum ratio of opposite directed edges between a pair of nodes for all node-pairs. For the join-only on-line problem, we prove that a greedy on-line algorithm is log(A + 1)-competitive compared to any on-line algorithm. For the join-leave problem on both undirected and directed graphs, we prove a new lower bound, which is exponential in the previous undirected bound (the number of joins requests). We, then, show that, for highly asymmetric graphs, the inefficiency is proportional to the asymmetry, i.e., arbitrarily larger than the number of join requests. Keywords: On-line multicast directed bounds, |
