Overhearing in 802.11 mesh networks

802.11-based mesh networks provide a useful and practical alternative to regular infrastructure-based wireless networks, but they have an intrinsic scaling limit due to their less efficient airtime utilization. Mesh networks forward packets multiple times, increasing airtime utilization and decreasing path throughput and useful channel capacity available to the clients. In this dissertation, we explore ways to optimize forwarding in order to decrease the number of packet transmissions and increase path throughput. The main technique that we explore in this dissertation is a phenomenon called 'overhearing'. Traditional mesh networks use only 'good' links with low packet loss rates in order to forward packets; overhearing allows utilization of the links with high losses in order to reduce the number of transmissions where possible. This dissertation proposes two methods that allow mesh networks to take full advantage of overhearing: 'RTS-id' is a backwards-compatible link-layer modification that allows adding overhearing support to traditional mesh networks without requiring changes to hardware or transport protocols. 'Modrate' is a new rate selection algorithm that can increase the amount of overhearing in bulk transfer systems that are already taking advantage of overhearing opportunities. In order to verify the operation of RTS-id, we implement the algorithm on a software-defined radio. We verify that RTS-id is compatible with existing, unmodified radios. We then develop a probabilistic transmission simulator and use it to quantify the potential gains from deploying RTS-id on existing large-scale wireless mesh networks. In order to verify the operation of modrate, we set up two wireless testbeds: a large, building-wide testbed operating in the 2.4-GHz range, and a smaller testbed operating in the 5- GHz range. We apply modrate to two existing overhearing- aware routing protocols, ExOR and MORE, and use our testbeds to measure the improvement provided by modrate in those systems. Finally, motivated by the somewhat unimpressive performance of modrate, we study the specific reasons for performance improvements in the ExOR and MORE protocols. We measure the performance of each protocol with various pieces of functionality disabled, and come to surprising conclusions: while systems such as ExOR and MORE have significantly better performance than traditional systems, a large fraction of these performance gains is caused not by overhearing, but by simpler protocol aspects like flow control and group acknowledgment