# Scalable Reliable Multicast Communication using Overlays

##
Francois Baccelli

###

### Résumé:

Reliable multicast overlays use a set of unicast TCP connections
organized in a tree for transferring packets between the source of
the group communication and the end-systems of the group. Two cases
are studied: File-and-Forward, where memory available in end-system is
infinite, and Store-and-Forward in which it is bounded. In the first
case, throughput scalability is hardly an issue, but packet latency
might become large as communication goes on, unless the source is
throttled in an appropriate way. In the second case, a back-pressure
mechanism should be implemented among neighboring nodes to prevent
buffer overflow in end-systems and throughput may be affected by the
size of the group.
We show how to represent such mechanisms in terms of random graphs.
We then use the theory of first passage percolation to show that these
two schemes are scalable in terms of throughput and latency. More
precisely, we show that if the tree has a bounded fan-out degree, and
if the unicast TCP connections between end-systems offer certain
minimal statistical guarantees, then even an infinite tree has a
positive throughput and a latency between nodes that is linear in
the distance between them.

This is joint work with Augustin Chaintreau, INRIA-ENS, Zhen Liu, IBM
T.J. Watson Research Center and Anton Riabov, Columbia University.