In a distributed network, a \emph{compact multicast scheme} is a

routing scheme that allows any source to send messages to any set of

targets. We study the trade-off between the \emph{space} used to

store the routing table on each node and the \emph{stretch} factor

of the multicast scheme -- the maximum ratio over all sets of nodes

between the cost of the multicast route induced by the scheme and

the cost of a steiner tree between the same set of target nodes. We

obtain results in several variants of the problem: \emph{labeled} --

in which the designer can choose polylogarithmic node names,

\emph{name-independent} -- in which nodes have arbitrarily chosen

names, \emph{dynamic} -- an online version of the problem in which

nodes dynamically join and leave the multicast service and the goal

is to minimize both the cost of the multicast tree at each stage and

the total cost of control messages needed to update the tree.

PDF file

In  23rd International Symposium on Distributed Computing (DISC 2009)

Publisher  Springer Verlag
All copyrights reserved by Springer 2007.

Details