Wardrop Routing in Wireless Networks

Wireless routing protocols traditionally use shortest-path routing, and ignore traffic load in the choice of routes. In static mesh networks, we formally establish that if the number of sources is not too large, then one can construct a perfect flow-avoiding routing that boosts the throughput provided to each user over that of shortest-path routing by a factor of upto four. So motivated, we design a multi-path, load adaptive routing protocol that is generally applicable even when there are more sources. Our protocol adaptively equalizes the mean delay along all utilized routes from a source to destination, and does not utilize routes with greater mean delay. This is the Wardrop equilibrium property. We also address architectural challenges confronted in software implementation of a multi-path, delay feedback based, probabilistic routing algorithm. Our routing protocol is (i) completely distributed, (ii) automatically load balances flows, (iii) uses multiple paths whenever beneficial, (iv) guarantees loop-free paths at every time instant, and (v) amenable to clean implementation. A simulation study indicates that it is able to automatically route flows to "avoid" each other, consistently out-performing shortest-path protocols. The protocol has been implemented on a modified Linux 2.4.20 kernel. Finally, we discuss a proof-of-concept measurement study on a six node testbed.