Consider a source broadcasting a stream of data packets to a large number, n, of receivers. We assume that channels to distinct receivers are iid erasure channels, with erasure probability 1-p. It can easily be shown that the throughput of ARQ scales as O(1/log n), whereas the information theoretic capacity, for a single user, is p. We show that, using fountain codes, rates arbitrarily close to p are achievable for the broadcast. We also characterise the throughput-delay tradeoff for our scheme. Next, we consider n nodes, each of whom has a single packet to transmit to all the other nodes. The nodes are connected via a random graph with constant edge probability p. Time is split into rounds where, in each round, each node may broadcast a single packet to all its neighbours. We first study a random relaying scheme and show that it terminates in log n rounds (with high probability), with all nodes having all packets. Next we show that, with network coding, allcast can be completed in a constant number of rounds, whp.
A. J. Ganesh graduated from IIT-Madras in 1988, and received his PhD from Cornell University in 1995. He has been at the School of Mathematics, University of Bristol, since 2007, and was at Microsoft Research, Cambridge, before that. His research interests include queueing theory, large deviations, random graphs and stochastic processes, as well as applications to communication networks.