Ad Hoc Routing

Highly Dynamic Destination Sequence Distance Vector Routing (DSDV) for Mobile Computers - Charlie E. Perkins and Pravin Bhagwat

(see paper for abstract)

Presenter: Prashanth Bungale

Preparation Date: Wednesday February 25th

Presentation Date: Wednesday February 25th

Ad hoc On-demand Distance Vector Routing - Charlie E. Perkins and Elizabeth M. Royer

(see paper for abstract)

Presenter: Swaroop Sridhar

Preparation Date: Wednesday February 25th

Presentation Date: Monday March 1st

DSR: The Dynamic Source Routing Protocol for Multi-hop Wireless Ad hoc Networks - David B. Johnson and David A. Maltz and Josh Broch

(see paper for abstract)

Presenter: Saroja Gundala

Optimized Link State Routing Protocol for Ad hoc Networks - P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti, A. Qayyum, L. Viennot

(see paper for abstract)

Presenter: Budirijanto Purnomo

Preparation Date: Tuesday March 2nd

Presentation Date: Wednesday March 3rd

A Reliable, Efficient Topology Broadcast Protocol for Dynamic Networks (TBRPF) - Bhargav Bellur Richard G. Ogier

We present, prove correctness for, and evaluate a protocol for the reliable broadcast of topology and link-state information in a multihop communication network with a dynamic topology, such as a wireless network with mobile nodes. The protocol is called Topology Broadcast based on Reverse Path Forwarding (TBRPF), and uses the concept of reverse-path forwarding (RPF) to broadcast link-state updates in the reverse direction along the spanning tree formed by the minimum-hop paths from all nodes to the source of the update. TBRPF uses the topology information received along the broadcast trees to compute the minimum-hop paths that form the trees themselves, and is the first topology broadcast protocol based on RPF with this property. The use of minimum-hop trees instead of shortest-path trees (based on link costs) results in less frequent changes to the broadcast trees and therefore less communication cost to maintain the trees. Simulations show that TBRPF achieves up to a 98% reduction in communication cost compared to flooding in a 20-node network.

Presenter: Pavan Piratla

Wireless Physical Based Routing

Coping with Communication Gray Zones in IEEE 802.11b based Ad hoc Networks - Henrik Lundgren Erik Nordström Christian Tschudin

Our experiments with IEEE 802.11b based wireless ad hoc networks show that neighbor sensing with broadcast mes- sages introduces \communication gray zones": in such zones data messages cannot be exchanged although the HELLO mes- sages indicate neighbor reachability. This leads to a system- atic mismatch between the route state and the real world connectivity, resulting in disruptive behavior for multi-media data transfer over ad hoc routing protocols. Concentrating on AODV we explore this issue and evaluate three dierent techniques to overcome the gray zone problem. We present quantitative measurements of these improvements and dis- cuss the consequences for ad hoc routing protocols and their implementations.

Presenter: Nadia Farooqi

Preparation Date: Monday March 1st

Presentation Date: Tuesday March 2nd

A High Throughput Path Metric for MultiHop Wireless Routing - Douglas S. J. De Couto Daniel Aguayo John Bicket Robert Morris

This paper presents the expected transmission count metric (ETX), which finds high-throughput paths on multi-hop wireless networks. ETX minimizes the expected total number of packet transmissions (including retransmissions) required to successfully deliver a packet to the ultimate destination. The ETX metric incorporates the effects of link loss ratios, asymmetry in the loss ratios between the two directions of each link, and interference among the successive links of a path. In contrast, the minimum hop-count metric chooses arbitrarily among the different paths of the same minimum length, regardless of the often large differences in throughput among those paths, and ignoring the possibility that a longer path might offer higher throughput. This paper describes the design and implementation of ETX as a metric for the DSDV and DSR routing protocols, as well as modifications to DSDV and DSR which allow them to use ETX. Measurements taken from a 29- node 802.11b test-bed demonstrate the poor performance of minimum hopcount, illustrate the causes of that poor performance, and confirm that ETX improves performance. For long paths the throughput improvement is often a factor of two or more, suggesting that ETX will become more useful as networks grow larger and paths become longer.

Presenter: Borga Can Aymutlu

High Throughput Route Selection in Multi-rate Ad Hoc Wireless Networks - Baruch Awerbuch, David Holmer, and Herbert Rubens

Modern wireless devices, such as those that implement the 802.11b standard, utilize multiple transmission rates in order to accom- modate a wide range of channel conditions. Traditional ad hoc routing protocols typically use minimum hop paths. These paths tend to contain long range links that have low e®ective throughput and reduced reliabil- ity in multi-rate networks. In this work, we present the Medium Time Metric (MTM), which is derived from a general theoretical model of the attainable throughput in multi-rate ad hoc wireless networks. MTM avoids using the long range links favored by shortest path routing in fa- vor of shorter, higher throughput, more reliable links. We present NS2 simulations that show that using MTM yields an average total network throughput increase of 20% to 60%, depending on network density. In addition, by combining the MTM with a medium time fair MAC pro- tocol, average total network throughput increases of 100% to 200% are obtained over traditional route selection and packet fairness techniques.

Presenter: David Lee

Security

ODSBR: An On-Demand Secure Byzantine Routing Protocol - Baruch Awerbuch, Reza Curtmola, David Holmer, Cristina Nita-Rotaru, and Herbert Rubens

A common technique used by routing protocols for ad hoc wireless networks is to establish the routing paths on-demand, as opposed to continually maintaining a complete routing table. Since in an ad hoc network nodes not in direct range communicate via intermediate nodes, a significant concern is the ability to route in the presence of Byzantine failures which include nodes that drop, fabricate, modify, or mis-route packets in an attempt to disrupt the routing service. We propose the first on-demand routing protocol for ad hoc wireless networks that provides resilience to Byzantine failures caused by individual or colluding nodes. The protocol relies on an adaptive probing technique that detects a malicious link after log n faults have occurred, where n is the length of the path. Problematic links are avoided by using a weight-based mechanism that multiplicatively increases their weights and by using an on- demand route discovery protocol that finds a least weight path to the destination. Our protocol bounds the amount of damage that an attacker or a group of colluding attackers can cause to the network.

Presenter: Maneesh Dewan

SEAD: Secure Efficient Distance Vector Routing for Mobile Wireless Ad Hoc Networks - Yih-Chun Hu, Adrian Perrig, David B. Johnson

An ad hoc network is a collection of wireless computers (nodes), communicating among themselves over possibly multihop paths, without the help of any infrastructure such as base stations or access points. Although many previous ad hoc network routing protocols have been based in part on distance vector approaches, they have generally assumed a trusted environment. In this paper, we design and evaluate the Secure Efficient Ad hoc Distance vector routing protocol (SEAD), a secure ad hoc network routing protocol based on the design of the Destination-Sequenced Distance-Vector routing protocol (DSDV). In order to support use with nodes of limited CPU processing capability, and to guard against Denial-of-Service (DoS) attacks in which an attacker attempts to cause other nodes to consume excess network bandwidth or processing time, we use effi- cient one-way hash functions and do not use asymmetric cryptographic operations in the protocol. SEAD performs well over the range of scenarios we tested, and is robust against multiple uncoordinated attackers creating incorrect routing state in any other node, even in spite of any active attackers or compromised nodes in the network.

Presenter: Alex Maestretti

Ariadne: A secure On-Demand Routing Protocol for Ad hoc Networks - Yih-Chun Hu, Adrian Perrig, David B. Johnson

An ad hoc network is a group of wireless mobile computers (or nodes), in which individual nodes cooperate by forwarding packets for each other to allow nodes to communicate beyond direct wireless transmission range. Prior research in ad hoc networking has generally studied the routing problem in a non- adversarial setting, assuming a trusted environment. In this paper, we present attacks against routing in ad hoc networks, and we present the design and performance evaluation of a new secure on-demand ad hoc network routing protocol, called Ariadne. Ariadne prevents attackers or compromised nodes from tampering with uncompromised routes consisting of uncompromised nodes, and also prevents a large number of types of Denial-of-Service attacks. In addition, Ariadne is efficient, using only highly efficient symmetric cryptographic primitives.

Presenter: Joe G.

Using Directional Antennas to Prevent Wormhole Attacks - Lingxuan Hu and David Evans

Wormhole attacks enable an attacker with limited resources and no cryptographic material to wreak havoc on wireless networks. To date, no general defenses against wormhole attacks have been proposed. This paper presents an analysis of wormhole attacks and proposes a countermeasure using directional antennas. We present a cooperative protocol whereby nodes share directional information to prevent wormhole endpoints from masquerading as false neighbors. Our defense greatly diminishes the threat of wormhole attacks and requires no location information or clock synchronization.

Presenter: Ryan Caudy

Secure Data Transmission in Mobile Ad Hoc Networks - Panagiotis Papadimitratos and Zygmunt J. Haas

The vision of nomadic computing with its ubiquitous access has stimulated much interest in the Mobile Ad Hoc Networking (MANET) technology. However, its proliferation strongly depends on the availability of security provisions, among other factors. In the open, collaborative MANET environment practically any node can maliciously or selfishly disrupt and deny communication. In this paper, we propose the Secure Message Transmission (SMT) protocol to safeguard the data transmission against any arbitrary malicious behavior. SMT is a lightweight yet very effective protocol that can operate solely in an end-to-end manner. The protocol exploits the redundancy of multi-path routing and it adapts its operation in order to remain effective and efficient in highly adverse environments, so that the communication is not disrupted. SMT is capable of delivering up to 250% more data messages than a protocol that does not secure data transmission. Moreover, SMT improves up to 22% when compared to a single path secure data transmission protocol. Most importantly, SMT achieves end-to-end delays that are up to 94% lower than those of the single path, and with a similar decrease in the routing overhead. Thus, the protocol can serve to support QoS for real-time communications in the ad hoc networking environment. Such improvements are achieved without restrictive assumptions on the network nodes. trust and network membership, without the use of intrusion detection schemes, and at the expense of moderate transmission overhead due to the use of multiple paths. Additionally, our results show that SMT can counter attacks from a significant number of adversaries and remains effective even when 50% of the network nodes are actively disrupting the data transmission.

Presenter: Chris Niski

802.11 Denial-of-Service Attacks: Real Vulnerabilities and Practical Solutions - John Bellardo and Stefan Savage

The convenience of 802.11-based wireless access networks has led to widespread deployment in the consumer, industrial and military sectors. However, this use is predicated on an implicit assumption of confidentiality and availability. While the security flaws in 802.11.s basic confidentially mechanisms have been widely publicized, the threats to network availability are far less widely appreciated. In fact, it has been suggested that 802.11 is highly susceptible to malicious denial-of-service (DoS) attacks targeting its management and media access protocols. This paper provides an experimental analysis of such 802.11-specific attacks - their practicality, their efficacy and potential low-overhead implementation changes to mitigate the underlying vulnerabilities.

Presenter: Christopher Soghoian

Packet Leashes: A Defense against Wormhole Attacks in Wireless Networks - Yih-Chun Hu, Adrian Perrig, and David B. Johnson

As mobile ad hoc network applications are deployed, security emerges as a central requirement. In this paper, we introduce the wormhole attack, a severe attack in ad hoc networks that is particularly challenging to defend against. The wormhole attack is possible even if the attacker has not compromised any hosts, and even if all communication provides authenticity and confidentiality. In the wormhole attack, an attacker records packets (or bits) at one location in the network, tunnels them (possibly selectively) to another location, and retransmits them there into the network. The wormhole attack can form a serious threat in wireless networks, especially against many ad hoc network routing protocols and location-based wireless security systems. For example, most existing ad hoc network routing protocols, without some mechanism to defend against the wormhole attack, would be unable to find routes longer than one or two hops, severely disrupting communication. We present a new, general mechanism, called packet leashes, for detecting and thus defending against wormhole attacks, and we present a specific protocol, called TIK, that implements leashes.

Presenter: Stephen Bono

Secure Routing in Wireless Sensor Networks: Attacks and Countermeasures - Chris Karlof and David Wagner

We consider routing security in wireless sensor networks. Many sensor network routing protocols have been proposed, but none of them have been designed with security as a goal. We propose security goals for routing in sensor networks, show how attacks against ad-hoc and peer-to-peer networks can be adapted into powerful attacks against sensor networks, introduce two classes of novel attacks against sensor networks sinkholes and HELLO floods, and analyze the security of all the major sensor network routing protocols. We describe crippling attacks against all of them and suggest countermeasures and design considerations. This is the first such analysis of secure routing in sensor networks.

Presenter: Janani Venkateswaran

Energy Efficiency

Asynchronous Wakeup for Ad Hoc Networks - Rong Zheng, Jennifer C. Hou and Lui Sha

Due to the slow advancement of battery technology, power management in wireless networks remains to be a critical issue. Asynchronous wakeup has the merits of not requiring global clock synchronization and being resilient to network dynamics. This paper presents a systematic approach to designing and implementing asynchronous wakeup mechanisms in ad hoc networks. The optimal wakeup schedule design can be formulated as a block design problem in combinatorics. We propose a neighbor discovery and schedule bookkeeping protocol that can operate on the optimal wakeup schedule derived. Two power management policies, i.e. slot-based power management and on-demand power management, are studied to overlay desirable communication schedule over the wakeup schedule mandated by the asynchronous wakeup mechanism. Simulation studies indicate that the proposed asynchronous wakeup protocol is quite effective under various traffic characteristics and loads: energy saving can be as high as 70%, while the packet delivery ratio is comparable to that without power management.

Presenter: Samuel Small

On-demand Power Management for Ad Hoc Networks - Rong Zheng, Robin Kravets

Battery power is an important resource in ad hoc networks. It has been observed that in ad hoc networks, energy consumption does not reflect the communication activities in the network. Many existing energy conservation protocols based on electing a routing backbone for global connectivity are oblivious to traffic characteristics. In this paper, we propose an extensible on-demand power management framework for ad hoc networks that adapts to traffic load. Nodes maintain soft-state timers that determine power management transitions. By monitoring routing control messages and data transmission, these timers are set and refreshed on-demand. Nodes that are not involved in data delivery may go to sleep as supported by the MAC protocol. This soft state is aggregated across multiple flows and its maintenance requires no additional out-of-band messages. We implement a prototype of our framework in the ns-2 simulator that uses the IEEE 802.11 MAC protocol. Simulation studies using our scheme with the Dynamic Source Routing protocol show a reduction in energy consumption near 50% when compared to a network without power management under both long-lived CBR traffic and on- off traffic loads, with comparable throughput and latency. Preliminary results also show that it outperforms existing routing backbone election approaches.

Presenter: Kapil Sharma

The Pulse Protocol: Energy Efficient Infrastructure Access - Baruch Awerbuch, David Holmer, and Herbert Rubens

We present the Pulse protocol which is designed for multi-hop wireless infrastructure access. While similar to the more traditional access point model, it is extended to operate across multiple hops. This is particularly useful for conference, airport, or large corporate deployments. In these types of environments where users are highly mobile, energy efficiency becomes of great importance. The Pulse protocol utilizes a periodic flood initiated at the network gateways which provides both routing and synchronization to the network. This synchronization is used to allow idle nodes to power off their radios for a large percentage of the time when they are not needed for packet forwarding. This results in substantial energy savings. Through simulation we validate the performance of the routing protocol with respect to both packet delivery and energy savings.

The Pulse Protocol: Mobile Ad hoc Network Performance Evaluation - Baruch Awerbuch, David Holmer, and Herbert Rubens

We present a performance evaluation of the Pulse protocol operating in a peer-to-peer mobile ad hoc network environment. The Pulse protocol utilizes a periodic flood (the pulse) initiated by a single node (the pulse source) to provide both routing and synchronization to the network. This periodic pulse forms a pro-actively updated spanning tree rooted at the pulse source. Nodes communicate by forwarding packets through through this tree. In addition, nodes are able to synchronize with the periodic pulse, allowing idle nodes to power off their radios a large percentage of the time when they are not required for packet forwarding. This results in substantial energy savings. Through simulation we explore the performance of the protocol with respect to packet delivery ratio, delay, and energy efficiency.

Span: An Energy-Efficient Coordination Algorithm for Topology Maintenance in Ad Hoc Wireless Networks - Benjie Chen, Kyle Jamieson, Hari Balakrishnan, and Robert Morris

(see paper for abstract)

Minimizing Energy for Wireless Web Access with Bounded Slowdown - Ronny Krashinsky and Hari Balakrishnan

On many battery-powered mobile computing devices, the wireless network is a signcant contributor to the total energy consumption. In this paper, we investigate the interaction between energy-saving protocols and TCP performance for Web-like transfers. We show that the popular IEEE 802.11 power-saving mode (PSM), a "static" protocol, can harm performance by increasing fast round trip times (RTTs) to 100 ms; and that under typicalWeb browsing workloads, current implementations will unnecessarily spend energy waking up during long idle periods. To overcome these problems, we present the Bounded- Slowdown (BSD) protocol, a PSM that dynamically adapts to network activity. BSD is an optimal solution to the problem of minimizing energy consumption while guaranteeing that a connection's RTT does not increase by more than a factor p over its base RTT, where p is a protocol parameter that exposes the trade-off between minimizing energy and reducing latency. We present several trace-driven simulation results that show that, compared to a static PSM, the Bounded-Slowdown protocol reduces average Web page retrieval times by 5-64%, while simultaneously reducing energy consumption by 1-14% (and by 13x compared to no power management).

Presenter: Yuki Nagase

Auto Rate Selection

A Rate Adaptive MAC Protocol for MultiHop Wireless Networks - Gavin Holland, Nitin Vaidya, and Paramvir Bahl

(see paper for abstract)

Presenter: Toliy Gliberman

OAR: An Opportunistic Autorate Media Access Protocol for Ad Hoc Networks - B. Sadeghi, V. Kanodia, A. Sabharwal, and E. Knightly

The IEEE 802.11 wireless media access standard supports multiple data rates at the physical layer. Moreover, vari- ous auto rate adaptation mechanisms at the medium access layer have been proposed to utilize this multi-rate capabil- ity by automatically adapting the transmission rate to best match the channel conditions. In this paper, we introduce the Opportunistic Auto Rate (OAR) protocol to better ex- ploit durations of high-quality channels conditions. The key mechanism of the OAR protocol is to opportunistically send multiple back-to-back data packets whenever the channel quality is good. As channel coherence times typically exceed multiple packet transmission times for both mobile and non- mobile users, OAR achieves significant throughput gains as compared to state-of-the-art auto-rate adaptation mecha- nisms. Moreover, over longer time scales, OAR ensures that all nodes are granted channel access for the same time-shares as achieved by single-rate IEEE 802.11. We describe mech- anisms to implement OAR on top of any existing auto-rate adaptation scheme in a nearly IEEE 802.11 compliant man- ner. We also analytically study OAR and characterize the delay jitter and the gains in throughput as a function of the channel conditions. Finally, we perform an extensive set of ns-2 simulations to study the impact of such factors as node velocity, channel conditions, and topology on the throughput of OAR.

Medium Access Control

CDMA-Based MAC Protocol for Wireless Ad Hoc Networks - Alaa Muqattash and Marwan Krunz

We propose a CDMA-based power controlled medium access protocol for mobile ad hoc networks (MANETs). Unlike previously proposed protocols, ours accounts for the multiple access interference (MAI), thereby addressing the notorious near-far problem that undermines the throughput performance in MANETs. Channel-gain information obtained from overheard RTS and CTS packets over an outof- band control channel is used to dynamically bound the transmission power of mobile terminals in the vicinity of a receiver. By properly estimating the required transmission power for data packets, the proposed protocol allows for interference-limited simultaneous transmissions to take place in the neighborhood of a receiving terminal. Simulation results indicate that compared to the IEEE 802.11 approach, the proposed protocol achieves a significant increase in network throughput at no additional cost in energy consumption.

Presenter: Moheeb Abu Rajab

Achieving MAC Layer Fairness in Wireless Packet Networks - Thyagarajan Nandagopal and Tae-Eun Kim and Xia Gao and Vaduvur Bharghavan

(see paper for abstract)

Dual Busy Tone Multiple Access (DBTMA):A New Medium Access Control for Packet Radio Networks - Jing Deng and Zygmunt J. Hass

(see paper for abstract)

Presenter: Michael Hilsdale

Real-Time Traffic over the IEEE 802.11 Medium Access Control Layer - Joao L. Sobrinho and A. S. Krishnakumar

(see paper for abstract)

Broadcast

Comparison of Broadcasting Techniques for Mobile Ad Hoc Networks - Brad Williams, Tracy Camp

Network wide broadcasting in Mobile Ad Hoc Networks provides important control and route establishment functionality for a number of unicast and multicast protocols. Considering its wide use as a building block for other network layer protocols, the MANET community needs to standardize a single methodology that efficiently delivers a packet from one node to all other network nodes. Despite a considerable number of proposed broadcasting schemes, no comprehensive comparative analysis has been previously done. This paper provides such analysis by classifying existing broadcasting schemes into categories and simulating a subset of each category, thus supplying a condensed but comprehensive side by side comparison. The simulations are designed to pinpoint, in each category, specific failures to network conditions that are relevant to MANETs, e.g., bandwidth congestion and dynamic topologies. In addition, protocol extensions using adaptive responses to network conditions are proposed, implemented and analyzed for one broadcasting scheme that performs well in the comparative study.

Presenter: Leonard Onyiah