UFlood: Flooding Protocol for Wireless Mesh Networks

UFlood is an efficient protocol for flooding large amounts of data over multi-hop wireless networks; it is intended for applications such as video distribution and software updates, where throughput (the transfer size divided by the time it takes until all the nodes have received the whole transfer) and efficient use of the wireless channel are both important. Achieving both goals is a challenge. UFlood's key new idea is a distributed heuristic that takes into account, which data nearby receivers already have as well as inter-node channel quality. The mechanism includes a novel bit-rate selection algorithm that trades off the speed of high bit-rates against the larger number of nodes likely to receive low bit-rates. Unusually, UFlood uses both random network coding to increase the usefulness of each transmission and detailed feedback about what data each receiver already has; the feedback is critical in deciding which node's coded transmission will have the most benefit to receivers. The required feedback is potentially voluminous, but UFlood includes novel techniques to reduce its cost. Experimental results on a 25-node wireless test-bed demonstrate that UFlood improves throughput by 2.5-4 times using 65% lower airtime consumption than existing flooding protocols. Tools used: Click Modular Router, python, MATLAB. OS used: Linux. Hardware: Wireless nodes with 500 MHz AMD Geode LX800 CPU and a radio based on the Atheros 5212 chip-set.