Report ID
2006-13
Report Authors
Chiranjeeb Buragohain, Subhash Suri, Csaba D. Toth and
Yunhong Zhou
Report Date
Abstract

We propose new algorithms and improved bounds for interference-aware routing in wireless networks. First, we prove that $n$ emph{arbitrarily matched} source-destinations pairs with average distance $d$, for any $1 leq d leq sqrt{n}$, in an $O(n)$ size grid network achieve throughput capacity $Omega(n/d)$. By a simple packing argument, this is also an upper bound in the worst-case. We show that, interestingly, the $Omega (n/d)$ throughput can be achieved with emph{single path} routing, and present a simple distributed algorithm to compute these routes. For arbitrary networks, we propose a new emph{node-based} linear-programming (LP) formulation that leads to an improved worst-case throughput bound. Specifically, we show that the throughput delivered by our algorithm is at least $1/3$ of the optimal, improving the previous best of $1/8$. In addition, we show that for certain special topologies, such as tree-structured networks, our linear program yields optimal throughput.

The LP-based methods split flows along multiple paths, which can be undesirable in some settings. The multipath routes produced by our linear program can be replaced by single paths using randomized rounding, at a loss of $O(log n)$ factor in the throughput. Achieving a constant factor throughput approximation using single path routes in arbitrary networks seems difficult, and we prove that several natural candidates for single path routing fail to achieve a constant factor throughput and, in fact, do arbitrarily poorly.

Finally, we report on the experimental evaluation of our algorithms. Most significantly, we observe that the node-based LP routing not only has the best known theoretical guarantee, but in simulations it also yields significantly higher (almost twice) throughput than the previous edge-based LP formulations.

Document
2006-13.pdf180.51 KB