Routing and Mobility

Author

Henri Dubois-Ferrière

Introduction

Current routing protocols use a spatial metric as they construct a route in order to advance to their destination. This spatial metric is typically counted as ‘number of hops’, and the routing process always moves closer, in hops, to the destination. This approach has been proven wired networks, such as the internet, where topology changes are atypical events. In networks where topology changes continuously, such as mobile ad hoc networks, spatial distance alone is not as relevant to guide routing decisions. Indeed when the network topology is changing, the age of routing information becomes an equally important criterion. For example, a 5-hop route which was just established may well be a better choice than a 4-hop route which has been inactive for some amount of time, and has higher probability of being broken.

Main contributions

We have proposed FResher Encounter SearcH (FRESH), a simple algorithm for efficient route discovery in mobile ad hoc networks. Nodes keep a record of their most recent encounter times with all other nodes. Instead of searching for the destination, the source node searches for any intermediate node that encountered the destination (more recently than did the source node itself). The intermediate node then searches for a node that encountered the destination yet more recently, and the procedure iterates until the destination is reached. Therefore, FRESH replaces the single network-wide search of current proposals with a succession of smaller searches, resulting in a cheaper route discovery. Routes obtained are loop-free. The fundamental difference between FRESH and current proposals is that it uses a temporal metric to construct routes, rather than a spatial metric.

Current and Future Research

Having established a routing algorithm which works exclusively in the temporal domain, we have now proposed GREP (Generalized Route Establishment Protocol), an algorithm which jointly makes use of spatial and temporal metrics. GREP is in fact a generalization of both FRESH and AODV (an established distance-vector routing protocol). All of our current routing work has been geared toward node-centric communications. Our next step will be to explore data-centric modes of routing, that is when the primary targets being routed toward are data rather than nodes. Data-centric routing is particularly relevant in the space of sensor-networks, as well as for multicast communication.

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]