Rainbow: A wireless medium access control using network coding for multi-hop content distribution

We consider the problem of multi-hop content distribution over a wireless ad-hoc network. Such mechanisms are relevant to a broad spectrum of applications, but are particularly important to data broadcast in wireless distributed computing where speedy I/O is critical to overall performance. In this paper, we present Rainbow, a content distribution protocol for multi-hop wireless ad-hoc networks. The protocol uses a content-directed medium access control (MAC), through which transmission priority is given to those nodes most capable of delivering useful content to their neighbors. We describe an efficient implementation of Rainbow based on network coding. Specifically, Rainbow uses a MAC priority scheme, where the priority of packet transmission from a node depends on the rank of the coefficient matrix associated with the coded content the node holds. We demonstrate that Rainbow achieves a 1.3-to 1.9-fold improvement in content distribution time over other flooding protocols, as measured on a testbed of 29 wireless nodes. We attribute this performance gain in part to Rainbow's ability to address a MAC-level bottleneck in multi-hop wireless networks, which we refer to as the "bridge lock-out problem".