Mobile Ad Hoc Networking Working Group Charles Perkins
INTERNET DRAFT Sun Microsystems
20 November 1997
Ad Hoc On Demand Distance Vector (AODV) Routing
draft-ietf-manet-aodv-00.txt
Status of This Memo
This document is a submission by the Mobile Ad Hoc Networking Working
Group of the Internet Engineering Task Force (IETF). Comments should
be submitted to the manet@itd.nrl.navy.mil mailing list.
Distribution of this memo is unlimited.
This document is an Internet-Draft. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at
any time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as ``work in progress.''
To learn the current status of any Internet-Draft, please check
the ``1id-abstracts.txt'' listing contained in the Internet-Drafts
Shadow Directories on ftp.is.co.za (Africa), nic.nordu.net (North
Europe), ftp.nis.garr.it (South Europe), munnari.oz.au (Pacific Rim),
ds.internic.net (US East Coast), or ftp.isi.edu (US West Coast).
Abstract
The Ad Hoc On-Demand Distance Vector (AODV) routing protocol is
intended for use by mobile nodes in an ad hoc network characterized
by frequent changes in link connectivity to each other caused
by relative movement. It offers quick adaptation to dynamic
link conditions, low processing and memory overhead, low network
utilization, and establishment of routes between sources and
destination which are loop free at all times. It makes use of
destination sequence numbers, which are a novel means of ensuring
loop freedom even in the face of anomalous delivery of routing
control messages, and which solve classical problems associated with
distance vector protocols, including the problem of ''counting to
infinity''.
Perkins Expires 20 May 1998 [Page i]
Internet Draft AODV 20 November 1997
Contents
Status of This Memo i
Abstract i
1. Introduction 1
2. Overview 2
3. AODV Terminology 3
4. Route Request Message Format 4
5. Route Reply Message Format 5
6. Node Operation 5
6.1. Maintaining Route Utilization Records . . . . . . . . . . 5
6.2. Generating Route Requests . . . . . . . . . . . . . . . . 6
6.3. Forwarding Route Requests . . . . . . . . . . . . . . . . 6
6.4. Generating Route Replies . . . . . . . . . . . . . . . . 7
6.5. Generating Hello Messages . . . . . . . . . . . . . . . . 8
6.6. Initiating Triggered Route Replies . . . . . . . . . . . 8
6.7. Detecting Link Breakage . . . . . . . . . . . . . . . . . 9
7. Configuration Parameters 9
8. Extensions 10
9. Security Considerations 10
1. Introduction
The Ad-Hoc On-Demand Distance Vector (AODV) algorithm enables
dynamic, self-starting, multihop routing between participating mobile
nodes wishing to establish and maintain an ad-hoc network. AODV
allows mobile nodes to obtain routes quickly for new destinations,
and does not require nodes to maintain routes to destinations that
are not in active communication. AODV also defines timely responses
to link breakages. The operation of AODV is loop free, and by
avoiding the Bellman-Ford "counting to infinity" problem offers quick
convergence when the ad-hoc network topology changes (typically, when
a node moves in the network).
Perkins Expires 20 May 1998 [Page 1]
Internet Draft AODV 20 November 1997
One distinguishing feature of AODV is its use of a destination
sequence number for each route entry. The destination sequence
number is created by the destination itself for any usable route
information it sends to requesting nodes. Using destination sequence
numbers ensures loop freedom, and is simple to program. Given the
choice between two routes to a destination, a requesting node always
selects one with the greatest sequence number.
Another feature of AODV is that link breakages cause immediate
notifications to be sent to the affected set of nodes, but only that
set.
2. Overview
Route Requests (RREQs) and Route Replies (RREPs) are the two message
types defined by AODV. These message types are handled by UDP,
and normal IP header processing applies. So, for instance, the
requesting node is expected to use its IP address as the source IP
address for the messages. The range of dissemination of broadcast
RREQs can be indicated by the TTL in the IP header. Fragmentation is
typically not required.
As long as the endpoints of a communication connection have valid
routes to each other, AODV does not play any role. When a route to a
new destination is needed, the node uses a broadcast RREQ to find a
route to the destination. A route can be determined when the request
reaches either the destination itself, or an intermediate node with a
fresh enough route to the destination. The route is made available
by unicasting a RREP back to the source of the RREQ. Since each node
receiving the request keeps track of a route back to the source of
the request, the RREP Reply can be unicast back from the destination
to the source, or from any intermediate node that is able to satisfy
the request back to the source.
If a RREP is broadcast to the limited broadcast address
(255.255.255.255), and has a TTL of one, and a destination address of
the node itself with metric 0, then it is received by all the node's
neighbors, and treated by them as a "hello" message. This hello
message is a local advertisement for the continued presence of the
node. Neighbors that are using routes through the broadcasting node
will continue to mark the routes as valid. If hello messages from a
particular node stop coming, the neighbor can assume that the node
has moved away. When that happens, the neighbor will mark the link
to the node as broken, and may trigger a notification to some of its
other neighbors that the link has broken.
Perkins Expires 20 May 1998 [Page 2]
Internet Draft AODV 20 November 1997
Since AODV is a routing protocol, it deals with route table
management. AODV assumes the following fields exist in each route
table entry:
- Destination IP Address
- Destination Sequence Number
- Hop Count
- Next Hop
- Lifetime
This information must be kept even for ephemeral routes, such as are
created to temporarily keep track of reverse paths towards nodes
originating RREQs.
3. AODV Terminology
This section defines terminology used with AODV that is not alre