Delay Bounds for Random Linear Coding in Parallel Relay Networks

We consider the problem of transmitting a collection of packets from a source node to a destination node across a relaynetwork. We analyze a simple random network coding scheme where each node transmits a random linear combination of packets each time it has an opportunity to transmit. The main result of this paper is an upper bound on the expected time to transmit ageneration of packets across the network. We show that the expected time is bounded by the generation size divided by the capacityof the minimum cut separating the source from the destination, plus a term that grows as the square root of the generation size. We then use this bound to provide a queueing analysis of a strategy that dynamically creates generations as packets arrive in a queue at the network’s source node. To facilitate our analysis, we model the relay network by a continuous-time Markov chain. Our primaryanalytical tool is a general method for computing upper bounds on hitting times associated with continuous-time Markov chains. We believe that this approach also provides a method for analyzing transmission times associated with more general network topologies.