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