Design and Evaluation of Primitives for Passive Link Assessment and Route Selection in Static Wireless Networks
Knightly, Edward W.
Doctor of Philosophy thesis
Communication in wireless networks elementally comprises of packet exchanges over individual wireless links and routes formed by these links. To this end, two problems are fundamental: assessment of link quality and identification of the least-cost (optimal) routes. However, little is known about achieving these goals without incurring additional overhead to IEEE 802.11 networks. In this thesis, I design and experimentally evaluate two frameworks that enable individual 802.11 nodes to characterize their wireless links and routes by employing only local and passively collected information. First, I enable 802.11 nodes to assess their links by characterizing packet delivery failures and failure causes. The key problem is that nodes cannot individually observe many factors that affect the packet delivery at both ends of their links and in both directions of 802.11 communication. To this end, instead of relying on the assistance of other nodes, I design the first practical framework that extrapolates the missing information locally from the nodes' overhearing, the observable causal relationships of 802.11 operation and characterization of the corrupted and undecodable packets. The proposed framework employs only packet-level information generally reported by commodity 802.11 wireless cards. Next, I design and evaluate routing primitives that enable individual nodes to suppress their poor route selections. I refer to a route selection as poor whenever the employed routing protocol fails to establish the existing least-cost path according to an employed routing metric. This thesis shows that an entire family of the state-of-the art on-demand distance-vector routing protocols, including the standards-proposed protocol for IEEE 802.11s mesh networks, suffers from frequent and long-term poor selections having arbitrary path costs. Consequently, such selections generally induce severe throughput degradations for network users. To address this problem, I design mechanisms that identify optimal paths locally by employing only the information readily available to the affected nodes. The proposed mechanisms largely suppress occurrence of inferior routes. Even when such routes are selected their durations are reduced by several orders of magnitude, often to sub-second time scales. My work has implications on several key areas of wireless networking: It removes systematic failures from wireless routing and serves as a source of information for a wide range of protocols including the protocols for network management and diagnostics.