An Empirical Study of Flooding in Mesh Networks

MSR-TR-2009-37 |

Flooding in wireless mesh networks is a fundamental operation to many network-level and application-level protocols. Therefore, efficient flooding is important. Prior work has shown that naive flooding can generate broadcast storms. This has inspired much research on optimized flooding, most of which has been based on analysis and simulation.

In this paper, we measure the performance of flooding protocols on a large-scale office 802.11a mesh network of 110 nodes distributed across four floors. We compare three protocols: naive flooding and two optimized flooding protocols. In naive flooding, all nodes rebroadcast received flood messages once. The other two protocols are inspired by the multi-point relay algorithm, which selects subsets of the nodes to rebroadcast.

To understand the scalability of each protocol, we examine its performance with and without background traffic. For the flood protocols, we measure the delivery ratios and packet overhead. All perform well without background traffic. However, contrary to common opinion, with background traffic the optimized flooding protocols perform sufficiently poorly to seriously question their viability in 802.11-based mesh networks. Thus, as a different point in the design space, we also compare implementing discovery, often implemented using flooding, using key-based routing which does not rely on flooding.