Flooding the Network: Multipoint Relays versus Network Coding

Flooding is an elementary tool for information dissemination in a wide range of network scenarios, such as link state advertisements in wireless multi-hop networks and query propagation in peer-to-peer networks. Using random graph models, we compare two competing flooding techniques: multipoint relays and network coding. Our analytical results show that in the case of network coding, the number of transmissions per source message is asymptotically independent of the number of nodes. Simulation results yield further insights on the impact of topology on the performance of each flooding technique, more specifically on the required number of transmissions and the resulting end-to-end delay.