Scheduling and fairness in multi-hop wireless networks

Multi-hop wireless networks have been a subject of research for many years now. But recently, availability of inexpensive hardware has spurred interest in a new class of applications called mesh networks where multi-hop wireless routing is used to avoid the cost of deploying a wired backbone. However, both simulations and deployments based on the current generation of hardware (based mostly on the 802.11 standard) show very poor fairness between competing flows. In fact, the imbalance in throughput can be so severe that some nodes are completely shut out from sending any data at all. Some of this unfairness can be attributed to the lack of flexibility in the 802.11 Medium Access Control (MAC) layer to provide control over resource allocation. Recent work also suggests that Carrier-Sense Multiple Access (CSMA) based MAC protocols suffer from a more fundamental limitation due to problems caused by hidden terminals and asymmetric links. In this work, we address this problem by making the following three contributions. Firstly, we build an Overlay MAC Layer (OML) that implements a time-slot based scheduler that works on top of inexpensive 802.11 based hardware without any changes to the standard. The overlay approach also provides a lot of flexibility and can easily be adapted to specific applications and networks through simple software modifications. Secondly, we have developed a distributed algorithm that can efficiently detect interference by using passive measurements. While we use the inferred interference pattern to improve scheduling under OML, our algorithm can also be used in a number of other applications such as channel assignment, resource allocation and admission control. Thirdly, we have designed a transport layer algorithm called End-to-end Fairness using Local Weights (EFLoW) for providing global Max-Min Fairness. EFLoW uses an iterative additive-increase multiplicative-decrease (AIMD) based approach using only state from within a given node's contention region in each iteration. It can automatically adapt to changes in traffic demands and network conditions. We have evaluated our system by conducting experiments in both ns-2 and a 30-node testbed built using commodity hardware. We show that our algorithms can improve fairness by over 90% with only a small cost (typically less than 10%) in efficiency for a wide variety of traffic patterns and network conditions.