A revolution has occurred in wireless communications over the last decade. Advances in processing power have enabled widespread deployment of radio networks as well as portable devices that can make use of such networks. Wireless networks have become more convenient and affordable and have spread to even fairly stationary applications, such as home networking and community networking. Ad hoc networks can extend the range of such wireless networks; in an ad hoc network, nodes cooperate to dynamically establish routing among themselves, a packet sent by one node may be forwarded in turn by a sequence of other nodes, allowing the packet to reach a destination beyond the sender's wireless transmission range.

This thesis discusses improvements to service in ad hoc network routing. Since different networks require different types of service, I propose several mechanisms to improve service in various network conditions. One example of service is Quality-of-Service (QoS), since certain networks may desire some flows to have priority over other flows. Many of the mechanisms presented here make no distinction between lower and higher priority traffic, and in my evaluation, I only examine performance metrics aggregated over all flows, rather than the performance of a few select flows.

Another area encompassed by service is security. In particular, when an attacker is present in the network, a protocol that provides security against such an attacker should provide better service than one that does not. For example, a secure protocol should deliver more packets, incur less overhead, or conserve overall network power usage better than in insecure protocol when the network is under attack. As a network experiences attack, a secure network routing protocol may continue to provide some level of service, whereas a traditional network routing protocol may fail completely.

This thesis presents a number of contributions to the area of improving service in on-demand protocols for wireless ad hoc network routing. For scenarios without attackers and without real-time requirements, I present the mechanism of link-state caching, which improves the ability of source-routed on-demand routing protocols to retain much of the information useful for routing while discarding potentially stale information. I show that this can be done in an adaptive manner, and that an adaptive cache can often outperform a statically parameterized cache. I also contribute implicit source routes, which improve performance by removing a major disadvantage of source routing (in particular, the per-hop overhead of carrying source routes) while retaining the advantages of source routing.

This thesis also presents contributions to the area of providing real-time services in networks that are not under attack. I contribute the use of implicit source routing for packet classification, allowing the selection of per-hop behavior based on which flow to which a packet belongs. I also contribute a technique that uses physical layer information (specifically, the Signal-to-Noise Ratio) to choose routes, allowing the protocol to choose longer-lived routes, and also enabling the routing protocol to find new routes before old ones break. Finally, I show how MAC layer utilization information can be used to choose less congested paths, thus enabling higher network-wide throughput and providing significantly improved TCP fairness.

Finally, I provide contributions to secure ad hoc network routing which allow improved service in hostile environments. These contributions include SEAD and Ariadne, two routing protocols resiliant to a wide variety of attacks. I also contribute general mechanisms for efficiently securing distance-vector routing and Quality-of-Service routing, and mechansisms for resisting the tunneling and rushing attacks. In addition, I contribute skiplists, an alternative to very long hash chains, which significantly reduces the computational cost of following a long hash chain at the cost of increased storage overhead.

177 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu