Space-Time Routing in Ad Hoc Networks.

Author:

Henri Dubois-Ferrière

Introduction

Routing in ad hoc networks is a well studied topic, with a number of proposed algorithms like AODV and DSR, as well as simulation studies. A common point of these algorithms is that they are designed to use only recent and valid routing state. Stale, broken route entries are not taken into consideration to build a new route or repair a broken one. This is typically achieved by means of fairly aggressive timeouts: for example in AODV, the default timeout for a route is 3 seconds, after which an unused route is considered invalid and discarded (some fields may still be used at a later point, e.g. to initialize the radius of a route request search, but the state is never used for routing purposes per se).

In previous work, we showed that very old, invalid routing state can in fact be highly valuable in an ad hoc network where topology changes constantly due to node mobility. Specifically, we introduced FRESH (FResher Encounter SearcH), a route establishment algorithm which makes use only of each node’s last encounter time with the destination. FRESH delivers a packet to a destination through a sequence of localized searches, whose goal is to always find a node that has encountered the destination more recently than in the preceding search. In a sense, these searches walk down an age gradient that has formed around the destination as a result of node mobility. It was shown that such a sequence of localized floods is significantly more efficient than a single flood directly locating the destination.

FRESH takes the extreme approach of using only temporal information concerning one-hop routes, in order to demonstrate the value of such information for routing in highly mobile ad hoc networks. However, other information is available in the network, and may be helpful in establishing and repairing routes. For example a node may have an old {\em two}-hop route entry indicating that it was within two hops of the destination at a certain time in the past, or it might have another {\em 8}-hop entry pointing to a longer, but more recent route. Therefore, we can expect that an approach ignoring all spatial information (such as FRESH) should not be optimal.

Main contributions

We have proposed a distance-vector routing algorithm called Space-Time Routing (STR) which generalizes and unifies the (seemingly opposed) algorithms behind FRESH and AODV.Space-Time Routing exploits all available routing state, including old, invalid routing state, in order to build new routes more efficiently. It uses a binding space-time metric which takes into account both the age and the distance to destination of a (possibly invalid) routing entry in order to allow meaningful comparisons of routes with different age/distance tradeoffs. By suitable choice of metric, one can specialize STR to become an AODV-like protocol (purely spatial), a FRESH-like protocol (purely temporal), or an intermediate form taking equally into account distance and age. Packets are forwarded along an valid route when one is available. When there is no valid route, or if a previously valid route breaks, prior, invalid routes may be used to repair the route or construct a new one. Some other characteristics of STR are: 1) STR uses two-dimensional routing tables, allowing each node to store multiple entries to a destination, each with a different space-time tradeoff. 2) STR uses hop-by-hop routing, and does not require to have a converged end-to-end route between source and destination in order to start sending packets. 3) STR is provably loop-free.

Current and Future Research

We are currently evaluating the performance of STR under different instanciations (e.g., with different binding metrics), and with varying mobility and traffic processes. For this task, we are using NAB (Network in a Box, see http://nab.epfl.ch), a simulator for wireless ad hoc networks developped over the past 2 years at LCAV.

Other future plans include the extension of STR concepts to more general classes of time-varying graphs, where topology changes are modeled as a random process operating directly on the graph (rather than nodes moving in a plane).

Collaborations

Matthias Grossglauser, Martin Vetterli (EPFL).

Funding

Swiss National Competence Center in Research for Mobile Information and Communication Systems.

Major publications

H. Dubois-Ferrière, M. Grossglauser and M. Vetterli, Age Matters: Efficient Route Discovery in Mobile Ad Hoc Networks Using Encounter Ages, Proc ACM International Symposium on Mobile Ad Hoc Networking and Computing (MobiHOC), pp. 257-266, 2003.
[detailed record] [bibtex]

H. Dubois-Ferrière, M. Grossglauser and M. Vetterli, Space-Time Routing in Ad Hoc Networks, Proc. 2nd International Conference on AD-HOC Networks and Wireless (also app. in Lecture Notes in Computer Science, Nr. 2865), 2003.
[detailed record] [bibtex]