Using directionality in wireless routing

The increased usage of directional methods of communications (e.g. directional smart antennas, Free-Space-Optical transceivers, and sector antennas) has prompted research into leveraging directionality in every layer of the network stack. In this thesis, we seek to investigate how the concept of directionality can be used in layer 3 to facilitate routing under contexts of (1) wireless mesh networks, (2) highly mobile environments, and (3) overlay networks through virtual directions.;In the context of wireless mesh networks, we introduce Orthogonal Rendezvous Routing Protocol (ORRP), a lightweight-but-scalable routing protocol utilizing the inherent nature of directional communications to relax information requirements such as coordinate space embedding and node localization. The ORRP source and ORRP destination send route discovery and route dissemination packets respectively in locally-chosen orthogonal directions. Connectivity happens when these paths intersect (i.e. rendezvous). We show that ORRP achieves connectivity with high probability even in sparse networks with voids. ORRP scales well without imposing DHT-like graph structures (eg: trees, rings, torus etc.). The total state information required is O(N 3/2) for N-node networks, and the state is uniformly distributed. ORRP does not resort to flooding either in route discovery or dissemination. The price paid by ORRP is suboptimality in terms of path stretch compared to the shortest path. However, we characterize the average penalty and find that it is not severe.;In the context of mobile adhoc networks, we introduce Mobile Orthogonal Rendezvous Routing Protocol (MORRP) for mobile ad-hoc networks (MANETs) which tracks node movements based on local information through a novel concept called the directional routing table (DRT) which maps interface directions to a set-of-IDs to provide probabilistic routing information based on interface direction. We show that MORRP achieves connectivity with high probability even in highly mobile environments while maintaining only probabilistic information about destinations. MORRP scales well without imposing DHT-like graph structures (eg: trees, rings, torus etc.). We will also show that high connectivity can be achieved without the need to frequently disseminate node position resulting increased scalability even in highly mobile environments.;In the context of overlay networks, we introduce Virtual Direction Routing (VDR) which takes concepts introduced in the wireless realm and adapts them to scale flat, unstructured overlay networks. VDR is a scalable overlay network routing protocol that uses the concept of virtual directions to efficiently perform information seeding and lookup. State information is replicated at nodes along virtual orthogonal lines originating from each node and periodically updated. When a path lookup is initiated, instead of flooding the network, query packets are also forwarded along virtual orthogonal lines until an intersection with the seeded state occurs. We show that VDR achieves path search success with high probability even with relatively low seed and search packet TTL even under high network churn. We also show that VDR scales well without imposing DHT-like graph structures (eg: trees, rings, torus, coordinate-space, etc.) and the path stretch compared to random-walk protocols (the traditional method to route in unstructured overlay networks) is very good.;In summary, we provide a framework for utilizing directionality , to solve issues resulting from scalability and high mobility in wireless environments. We show that directional can not only be leveraged to provide adequate routing, but can provide dramatic gains in goodput, end-to-end delay, and network reach. We then take this framework and adapt it to the wired environment to scale overlay networks.1.;1This material is based upon work supported by the National Science Foundation under Grant Nos. IGERT 0333314, ITR 0313095, and STI 0230787. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.