Wardrop Routing in Wireless Networks

Routing protocols for multihop wireless networks have traditionally used shortest path routing to obtain paths to destinations and do not consider traffic load or delay as an explicit factor in the choice of routes. We focus on static mesh networks and formally establish that if the number of sources is not too large, then it is possible to construct a perfect flow-avoiding routing, which can boost the throughput provided to each user over that of the shortest path routing by a factor of four when carrier sensing can be disabled or a factor of 3.2 otherwise. So motivated, we address the issue of designing a multipath, load adaptive routing protocol that is generally applicable even when there are more sources. We develop a protocol that adaptively equalizes the mean delay along all utilized routes from a source to destination and does not utilize any routes that have greater mean delay. This is the property satisfied by a system in Wardrop equilibrium. We also address the architectural challenges confronted in the software implementation of a multipath, delay-feedback-based, probabilistic routing algorithm. Our routing protocol is 1) completely distributed, 2) automatically load balances flows, 3) uses multiple paths whenever beneficial, 4) guarantees loop-free paths at every time instant even while the algorithm is suntil converging, and 5) amenable to clean implementation. An ns-2 simulation study indicates that the protocol is able to automatically route flows to "avoid" each other, consistently out-performing shortest path protocols in a variety of scenarios. The protocol has been implemented in user space with a small amount of forwarding mechanism in a modified Linux 2.4.20 kernel. Finally, we discuss a proof-of-concept measurement study of the implementation on a six node testbed.