Compact Multicast Routing

ittai abraham, dahlia Malkhi, and David Ratajczak


In a distributed network, a 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 space used to

store the routing table on each node and the 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: labeled --

in which the designer can choose polylogarithmic node names,

name-independent – in which nodes have arbitrarily chosen

names, 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.


Publication typeInproceedings
Published in23rd International Symposium on Distributed Computing (DISC 2009)
PublisherSpringer Verlag
> Publications > Compact Multicast Routing