Mobile Ad Hoc Networking Working Group Charles E. Perkins
INTERNET DRAFT Nokia Research Center
26 Jan 2004 Elizabeth M. Belding-Royer
University of California, Santa Barbara
Ian D. Chakeres
University of California, Santa Barbara
Ad hoc On-Demand Distance Vector (AODV) Routing
<draft-perkins-manet-aodvbis-01.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@ietf.org mailing list.
Distribution of this memo is unlimited.
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026. 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."
The list of current Internet-Drafts can be accessed at:
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at:
http://www.ietf.org/shadow.html.
Abstract
The Ad hoc On-Demand Distance Vector (AODV) routing protocol
is intended for use by mobile nodes in an ad hoc network. It
offers quick adaptation to dynamic link conditions, low processing
and memory overhead, low network utilization, and unicast route
determination to destinations within the ad hoc network. It uses
destination sequence numbers to ensure loop freedom at all times
(even in the face of anomalous delivery of routing control messages),
avoiding problems (such as ``counting to infinity'') associated with
classical distance vector protocols.
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page i]
Internet Draft AODV 26 Jan 2004
Contents
Status of This Memo i
Abstract i
1. Introduction 1
2. Overview 2
3. AODV Terminology 3
4. Applicability Statement 4
5. Message Formats 4
5.1. Route Request (RREQ) Message Format . . . . . . . . . . . 5
5.2. Route Reply (RREP) Message Format . . . . . . . . . . . . 6
5.3. Route Error (RERR) Message Format . . . . . . . . . . . . 8
5.4. Route Reply Acknowledgment (RREP-ACK) Message Format . . 8
6. AODV Operation 9
6.1. Maintaining Sequence Numbers . . . . . . . . . . . . . . 9
6.2. Creating and Updating Route Table Entries . . . . . . . . 10
6.3. Generating Route Requests . . . . . . . . . . . . . . . . 12
6.4. Receiving Route Requests . . . . . . . . . . . . . . . . 13
6.5. Generating Route Replies . . . . . . . . . . . . . . . . 13
6.6. Receiving Route Replies . . . . . . . . . . . . . . . . . 14
6.7. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 14
7. Performance Improvements 15
7.1. Operation over Unidirectional Links . . . . . . . . . . . 15
7.2. Hello Messages . . . . . . . . . . . . . . . . . . . . . 16
7.3. Maintaining Local Connectivity . . . . . . . . . . . . . 17
7.4. Generating Route Error Messages . . . . . . . . . . . . . 18
7.5. Receiving Route Error Messages . . . . . . . . . . . . . 18
7.6. Intermediate Node Route Replies . . . . . . . . . . . . . 19
7.6.1. Generating Gratuitous Route Replies . . . . . . . 20
7.7. Actions After Reboot . . . . . . . . . . . . . . . . . . 20
8. AODV and Aggregated Networks 21
9. IPv6 Operation 22
10. Extensions 22
10.1. Lifetime Extension Format . . . . . . . . . . . . . . . . 23
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page ii]
Internet Draft AODV 26 Jan 2004
11. Configuration Parameters 23
12. Security Considerations 24
13. IANA Considerations 26
14. Acknowledgments 26
A. Draft Modifications 28
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 allows mobile nodes to respond to
link breakages and changes in network topology in a timely manner.
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). When links break, AODV causes the affected set of nodes to
be notified so that they are able to invalidate the routes using the
lost link.
One distinguishing feature of AODV is its use of a destination
sequence number for each routing table entry. The destination
sequence number is maintained by each node and is included along
with any 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 is required to select the one with the greatest
sequence number.
This revised version of AODV incorporates some new performance
enhancements and simplifies the requirements for implementations
based on experience gained during the development of RFC 3561 [3].
In this document, AODV always refers to the protocol being specified
in this document, not the Experimental Protocol as specified in RFC
3561. Of course, there is a great deal of similarity between RFC
3561 and this revised version of AODV. Unfortunately, there are also
certain points of incompatibility which became necessary so that AODV
could operate in a network where some nodes do not implement all the
performance enhancing (but still optional) features.
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 1]
Internet Draft AODV 26 Jan 2004
2. Overview
Route Requests (RREQs), Route Replies (RREPs) and Route Errors
(RERRs) are message types defined by AODV. These message types are
received via UDP (on port 654), and normal IP header processing
applies. So, for instance, the requesting node is expected
to use its IP address as the Originator IP address for the
messages. For broadcast messages, the IP limited broadcast address
(255.255.255.255) is used. This means that such messages are not
blindly forwarded. However, AODV operation does require certain
messages (e.g., RREQ) to be disseminated widely, perhaps throughout
the ad hoc network. Fragmentation is typically not required.
When a route to a new destination is needed, the node broadcasts a
RREQ to find a route to the destination. Each node receiving the
request caches a route back to the originator of the request, so that
the RREP can be unicast from the destination along a path to that
originator. A route can be determined when the RREQ reaches a node
that offers reachability to the destination (e.g., the destination
itself). The route is made available by unicasting a RREP back to
the origination of the RREQ.
For nodes monitoring the link status of next hops for active routes,
when a link break in an active route is detected, the broken link is
invalidated and a RERR message is typically transmitted to notify
other nodes that the loss of that link has occurred. The RERR
message indicates the destination that is no longer reachable by way
of the broken link.
AODV is a routing protocol, and hence it deals with routing table
management. Routing table information must be kept for all known
routes. AODV uses the following fields with each routing table
entry:
- Destination IP Address
- Hostid Size
- Destination Sequence Number
- Next Hop IP Address
- Lifetime (expiration or deletion time of the route)
- Hop Count (number of hops to reach the destination)
- Network Interface
- Other state and routing flags (e.g., active, inactive)
Managing the sequence number is crucial to avoiding routing loops.
A destination becomes unreachable when a link breaks or it is
deactivated. When these conditions occur, the route is invalidated
by operations involving the sequence number and marking the routing
table entry state as inactive. See Section 6.1 for details.
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 2]
Internet Draft AODV 26 Jan 2004
3. AODV Terminology
This protocol specification uses conventional meanings [1] for
capitalized words such as MUST, SHOULD, etc., to indicate requirement
levels for various protocol features. This section defines other
terminology used with AODV that is not already defined in [4].
active route
A route towards a destination that has a routing table entry
that is marked as active. Only active routes can be used to
forward data packets.
broadcast
Transmitting to the IP Limited Broadcast address,
255.255.255.255.
destination
An IP address to which data packets are to be transmitted. The
IP address of the destination node for a typical data packet
appears in the designated field of the IP header.
forwarding node
A node that agrees to forward packets destined for another
node. The node retransmits the packets to a next hop that
is closer to the unicast destination along a path previously
established by AODV that has been set up using control
messages.
inactive route
A route that has expired, denoted by a state of inactive in
the routing table entry. An inactive route is used to store
previously active route information, such as the sequence
number, for an extended period of time. An inactive route
cannot be used to forward data packets, but it can provide
information useful when processing other control messages (e.g.
future RREQ messages).
originating node
A node that initiates an AODV route request message. For
instance, the node that initiates a Route Discovery process and
first broadcasts the RREQ message is called the originating
node of the RREQ message.
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 3]
Internet Draft AODV 26 Jan 2004
sequence number
A monotonically increasing number that is maintained by each
node. It is used by other nodes to determine the freshness of
routing information obtained from AODV protocol messages about
the originating node. The sequence number zero (0) is reserved
and represents an unknown sequence number.
4. Applicability Statement
The AODV routing protocol is designed for mobile ad hoc networks
with populations of tens to thousands of mobile nodes. AODV can
handle low, moderate, and high mobility rates, as well as a variety
of data traffic levels. AODV is designed for use in networks where
the nodes can all trust each other, either by use of preconfigured
keys or because it is known that there are no malicious nodes. AODV
has been designed to reduce the dissemination of control traffic and
eliminate overhead on data traffic in order to improve scalability
and performance.
A recent study [5] has indicated that, for networks of limited size,
reliable communication can be managed by nodes that implement only
a very limited number of AODV features. For instance, in networks
of 50 nodes, the performance does not suffer very much even if nodes
only implement RREQ and RREP, without any RREPs from intermediate
nodes. Thus, we have revised the original AODV specification so
that many features are no longer mandated, even if they are strongly
recommended for all general purpose ad hoc network nodes. Networks
of nodes that only implement the mandated specification may not be
useful except for certain limited scenarios, and may even effectively
consume more power than when the nodes contain the congestion control
and latency reduction features recommended in Section 7.
5. Message Formats
In this section, the formats for the basic AODV messages are
specified. RREQ and RREP messages MUST be implemented by all AODV
nodes. RERR and RREP-ACK messages SHOULD be implemented, but there
may be cases where nodes can be built for certain limited deployments
that do not need to have the features enabled by those messages.
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 4]
Internet Draft AODV 26 Jan 2004
5.1. Route Request (RREQ) Message Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type |D|G| Reserved | Hop Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RREQ~ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Path Node IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Path Node Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (additional path node IP address and sequence number pairs) ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The format of the Route Request message is illustrated above, and
contains the following fields:
Type 1
D Destination-only flag. If set a intermediate node
may not respond to this RREQ (see Section 7.6).
G Gratuitous Route Reply flag. Indicates whether a
gratuitous RREP should be sent to the destination
(see Section 7.6). This flag should be set for
bi-directional traffic, such as TCP.
Reserved Sent as 0; ignored on reception.
Hop Count The number of hops from the originating node to
the node handling the request. This field also
indicates the number of accumulated path node IP
addresses and sequence numbers in the RREQ.
RREQ ID A sequence number uniquely identifying the
particular RREQ when taken in conjunction with the
originating node's IP address.
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 5]
Internet Draft AODV 26 Jan 2004
Destination IP Address
The IP address of the destination for which a route
is desired.
Destination Sequence Number
The latest sequence number received by the
originator for any route towards the destination.
Originator IP Address
The IP address of the originating node that issued
the Route Request.
Originator Sequence Number
The current sequence number of the originating
node.
Path Node IP Address
The IP address of the first node along the path
from the Originator to the Destination.
Path Node Sequence Number
The Sequence Number of the first node along the
path from the Originator to the Destination.
5.2. Route Reply (RREP) Message Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type |A|Reserved | APN Cnt |Hostid Sz| Hop Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination IP address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator IP address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Originator Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Path Node IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Path Node Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (additional path node IP address and sequence number pairs) ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The format of the Route Reply message is illustrated above, and
contains the following fields:
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 6]
Internet Draft AODV 26 Jan 2004
Type 2
A RREP Acknowledgment required. See Section 7.1.
Reserved Sent as 0; ignored on reception.
APN Count The number of accumulated path nodes appended to the
RREP.
Hostid Size The Hostid Size field supplies information that
is needed to determine those nodes within a
destination's subnet that are reachable via the same
route. For example, a Hostid Size of eight (8) is
equivalent to a subnet prefix of 255.255.255.0.
For a host route, the Hostid Size is set to zero
(0), which is equivalent to a subnet mask of
255.255.255.255.
Hop Count The number of hops from the originating node to the
destination node.
Destination IP Address
The IP address of the destination node.
Destination Sequence Number
The sequence number associated with the destination
node.
Originator IP Address
The IP address of the node that originated the RREQ
for which the route is supplied.
Originator Sequence Number
The current sequence number of the originating node.
Path Node IP Address
The IP address of the first node along the path from
the Originator to the Destination.
Path Node Sequence Number
The Sequence Number of the first node along the path
from the Originator to the Destination.
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 7]
Internet Draft AODV 26 Jan 2004
5.3. Route Error (RERR) Message Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Reserved | DestCount |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unreachable Destination IP Address (1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unreachable Destination Sequence Number (1) |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-|
| (more node IP address and sequence number pairs as needed) ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The format of the Route Error message is illustrated above, and
contains the following fields:
Type 3
Reserved Sent as 0; ignored on reception.
DestCount The number of unreachable destinations included in the
message; MUST be at least 1.
Unreachable Destination IP Address
The IP address of the destination that has become
unreachable due to a broken link.
Unreachable Destination Sequence Number
The sequence number in the route table entry for
the destination listed in the previous Unreachable
Destination IP Address field.
5.4. Route Reply Acknowledgment (RREP-ACK) Message Format
0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type 4
Reserved Sent as 0; ignored on reception.
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 8]
Internet Draft AODV 26 Jan 2004
6. AODV Operation
This section describes the scenarios during which nodes generate
Route Request (RREQ) and Route Reply (RREP) for unicast communication
to a destination node and how the message fields are handled. In
order to process the messages correctly, certain state information
has to be maintained in the routing table for destinations of
interest.
All AODV messages are sent to port 654 using UDP.
6.1. Maintaining Sequence Numbers
AODV requires each node in the network to own and maintain its
destination sequence number in order to guarantee the loop-freedom
of all routes towards that node. A node increments its own sequence
number in two circumstances:
- Immediately before a node initiates a route discovery, it MUST
increment its own sequence number. This prevents conflicts with
previously established reverse routes towards the originator of a
RREQ.
- Immediately before a node issues a RREP in response to a RREQ, it
MUST update its own sequence number to the maximum of its current
sequence number and the destination sequence number in the RREQ
packet plus one (1). SeqNum=Max(SeqNum,RREQSeqNum+1)
When a node increments a sequence number, it MUST do so by treating
the sequence number value as if it were an unsigned number.
Additionally the sequence number zero (0) is reserved and MUST never
be used. To accomplish sequence number rollover, if the sequence
number has already been assigned to be the largest possible number
representable as a 32-bit unsigned integer (i.e., 4294967295), then
it MUST then have a value of one (1) when it is incremented. This is
in contrast to the manner in which the result of comparing two AODV
sequence numbers is to be treated (see below).
Every routing table at every node MUST include the latest information
available about the sequence number for the IP address of each
destination for which a routing table entry is maintained. This
sequence number is called the "destination sequence number". It is
updated whenever a node receives new (i.e., not stale) information
about the sequence number from RREQ, RREP, or RERR messages that may
be received related to that destination.
In order to ascertain that information about a destination is not
stale, the node compares its current numerical value for the sequence
number in its routing table with that obtained from the incoming AODV
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 9]
Internet Draft AODV 26 Jan 2004
message. In AODV, the sequence number zero (0) has special meaning
and represents an unknown sequence number. Any known sequence number
is considered higher than an unknown sequence number. Given a known
sequence number in an AODV message, this comparison MUST be done
using signed 32-bit arithmetic. This is necessary to accomplish
sequence number rollover. If the result of subtracting the currently
stored sequence number from the value of the incoming sequence
number is less than zero, or a sequence number is known and the
incoming sequence number is unknown, then the information related
to that destination in the AODV message MUST be discarded, since
that information is stale compared to the node's currently stored
information.
The only other circumstance in which a node may change the
destination sequence number in one of its routing table entries is
in response to a lost or expired link to the next hop towards that
destination. The node determines which destinations use a particular
next hop by consulting its routing table. For each destination
that uses the next hop, the node increments the sequence number and
marks the route as inactive. Whenever any fresh (i.e., containing
a sequence number at least equal to the recorded sequence number)
routing information for an affected destination is received, the
node SHOULD update its route table information according to the
information contained in the update.
A node may change the sequence number in the routing table entry of a
destination only if:
- it is itself the destination node, and it offers a new route to
itself, or
- it receives an AODV message with new information about the
sequence number for a destination node, or
- the path towards the destination node expires or breaks.
6.2. Creating and Updating Route Table Entries
When a node receives an AODV control packet from a neighbor
or creates or updates a route for a particular destination, it
checks its routing table for an entry to the destination using
longest-prefix matching. In the event that there is no corresponding
entry for that destination, an entry is created. The ``new''
sequence number is either determined from the information contained
in the control packet or set to zero (0), representing an unknown
sequence number. A route is only updated if one of the following
conditions is met:
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 10]
Internet Draft AODV 26 Jan 2004
(i) the new sequence number is higher than the destination
sequence number in the route table, or
(ii) the new sequence number is the same as the destination
sequence number in the route table and the route is
marked as inactive, or
(iii) the sequence number in the routing table is unknown.
In addition, a route MAY be updated if the new sequence number is the
same as the destination sequence number in the route table, and the
new route is favorable for some reason, such as reduced hop count.
If the route table entry to this destination is created or updated,
then the following actions occur:
- the route is marked as active,
- the Next Hop IP Address in the routing table entry for the
destination is assigned to be that of the node from which
the control packet was received, which is indicated by the
source IP address field in the IP header, or by examining the
accumulated path list,
- the Hop Count is set to the number of hops to this
destination,
- the Hostid Size is set to the value from the control packet
or zero,
- the Lifetime field is set to the current time plus the value
of ACTIVE_ROUTE_TIMEOUT,
- and the Destination Sequence Number is set to the sequence
number for this destination from the control packet or zero
(0) for an unknown sequence number.
After updating a route, if it is active it may now be used to
send any queued data packets and to fulfill any outstanding route
requests.
Each time a route is used to forward a data packet, the Lifetime
field of the routing table entry for the IP destination is updated to
be no less than the current time plus ACTIVE_ROUTE_TIMEOUT.
Note that the Lifetime field in the routing table plays a dual role
-- for an active route it is the expiry time, and for an inactive
route it is the deletion time. If a data packet is received for an
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 11]
Internet Draft AODV 26 Jan 2004
inactive route, the Lifetime field is updated to current time plus
DELETE_PERIOD.
6.3. Generating Route Requests
A node generates a RREQ when it determines that it needs a route to
a destination and does not have one available. This can happen if
the destination is previously unknown to the node or if a previously
active route to the destination has expired or been marked as
inactive. The Destination Sequence Number field in the RREQ message
is the last known destination sequence number for this destination
and is copied from the Destination Sequence Number field in the
pertinent routing table entry. If no sequence number is known,
the sequence number field MUST be set to zero (0). The Originator
Sequence Number in the RREQ message is the node's own sequence
number, which is incremented prior to insertion in a RREQ. The
RREQ ID field is incremented by one from the last RREQ ID used by the
current node. Each node maintains only one RREQ ID. The Hop Count
field is set to zero. The RREQ TTL value is set to NET_DIAMETER.
Before broadcasting the RREQ, the originating node buffers the
RREQ ID and the Originator IP address (its own address) of the RREQ
for PATH_DISCOVERY_TIME. By doing so, the node will not reprocess
or re-forward the packet when it receives the packet again from its
neighbors. The originating node then broadcasts the RREQ. A node
SHOULD NOT originate more than RREQ_RATELIMIT RREQ messages per
second.
After broadcasting a RREQ, a node waits for a RREP or other control
message with current information regarding the destination. If a
route is not received within NET_TRAVERSAL_TIME milliseconds, the
node MAY again try to discover a route by broadcasting another RREQ,
up to a maximum of RREQ_TRIES times. Each new attempt MUST increment
and update the RREQ ID.
To reduce congestion in a network, repeated attempts by a source
node at route discovery for a single destination MUST utilize a
binary exponential backoff. The first time a source node broadcasts
a RREQ, it waits NET_TRAVERSAL_TIME milliseconds for the reception
of a RREP. If a RREP is not received within that time, the source
node sends a new RREQ. When calculating the time to wait for
the RREP after sending the second RREQ, the source node MUST use
a binary exponential backoff. Hence, the waiting time for the
RREP corresponding to the second RREQ is 2 * NET_TRAVERSAL_TIME
milliseconds. If a RREP is not received within this time period,
another RREQ may be sent, up to RREQ_TRIES additional attempts after
the first RREQ. For each additional attempt, the waiting time for
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 12]
Internet Draft AODV 26 Jan 2004
the RREP is multiplied by 2 so that the time conforms to a binary
exponential backoff.
Data packets waiting for a route (i.e., waiting for a RREP after a
RREQ has been sent) SHOULD be buffered. The buffering SHOULD be
"first-in, first-out" (FIFO). If a route discovery has been attempted
RREQ_TRIES times at the maximum TTL without receiving any RREP, all
data packets destined for the corresponding destination SHOULD be
dropped from the buffer and a Destination Unreachable ICMP message
SHOULD be delivered to the application.
6.4. Receiving Route Requests
When a node receives a RREQ, the node increments the Hop Count field
in the RREQ by one, to account for the previous hop. Then it MAY
create or update route to any destination listed in the accumulated
path list as specified in Section 6.2. The node can use any active
route to forward data packets.
Next it checks to determine whether it has received a RREQ with the
same Originator IP Address and RREQ ID within PATH_DISCOVERY_TIME. If
such a RREQ has been received, the node SHOULD silently discard the
newly received RREQ. The rest of this subsection describes actions
taken for RREQs that are not discarded.
If this intermediate node does not generate a RREP (following the
rules in Section 7.6) and if the incoming IP header has a TTL larger
than 1, then the RREQ is updated. The TTL field in the outgoing
IP header is decreased by one. The Destination Sequence number in
the RREQ for the requested destination is set to the maximum of the
original value received in the RREQ message and the destination
sequence value currently maintained by the node for the requested
destination. However, the forwarding node MUST NOT modify the
maintained value in its routing table for the destination sequence
number, even if the value received in the incoming RREQ is larger
than the value currently maintained by the forwarding node. Finally,
the current host appends its sequence number and IP address to the
accumulated path list. After updating the RREQ, it broadcasts the
RREQ to address 255.255.255.255 on each of its configured interfaces
(see Section 6.7).
6.5. Generating Route Replies
Upon reception of a RREQ, a node MUST generate a RREP if it is the
destination. When generating a RREP message, a node copies the
Destination IP Address, Originator IP Address and Originator Sequence
Number from the RREQ message into the corresponding fields of the
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 13]
Internet Draft AODV 26 Jan 2004
RREP message. In addition, the accumulated path list from the RREQ
is appended to the RREP in the same order as listed in the RREQ. The
APN Count field is set to the length of accumulated path node list.
If the destination generates a response, it MUST increment its own
sequence number to be at least one greater than the Destination
Sequence Number in the RREQ. If this condition is already satisfied
the destination does not change its sequence number before generating
the RREP message. The destination node places its (perhaps newly
changed) sequence number into the Destination Sequence Number field
of the RREP, and enters the value zero into the Hop Count field of
the RREP.
Once created, the RREP is unicast to the next hop toward the
originator of the RREQ, indicated by the last entry in the
accumulated path list.
Intermediate nodes MAY generate RREP under certain conditions.
Intermediate node route replies are described in Section 7.6.
6.6. Receiving Route Replies
When a node receives a RREP message, it increments the Hop Count
field in the RREP by one to account for the new hop through the
previous node. Next, a route MAY be created for the source and each
destination listed in the accumulated path list. Then a route to the
destination is updated or created by way of the procedure specified
in Section 6.2. Subsequently, the node can use any of its active
routes to forward data packets to the destination.
If the current node is not the node indicated by the Originator IP
Address in the RREP message, AND after an active route has been
created or updated to the destination, the node SHOULD send the RREP
to the IP address previous to its own IP address in the accumulated
path list. If there are no nodes listed in the accumulated path
list, denoted by zero (0) in APN Count, the RREP is sent to the Next
Hop IP Address in the active routing table entry for the Originator
IP Address. A node may send the RREP via an active route to the
Originator IP address via a route different from the accumulated path
list, but it MUST remove the accumulated path information and set the
APN Count to zero (0).
6.7. Interfaces
Because AODV should operate smoothly over heterogeneous networks
(wired, as well as wireless) and it is likely that AODV will also
be used with multiple wireless devices, the particular interface
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 14]
Internet Draft AODV 26 Jan 2004
over which packets arrive must be known to AODV whenever a packet
is received. This includes the reception of RREQ, RREP, and RERR
messages. Whenever a packet is received from a new neighbor, the
interface on which that packet was received is recorded into the
routing table entry for that neighbor along with all the other
appropriate routing information. Similarly, whenever a route to
a new destination is discovered, the interface through which the
destination can be reached is also recorded into the destination's
route table entry.
When multiple interfaces are available, a node transmitting a
broadcast control message SHOULD broadcast the message on all
interfaces that have been configured for operation in the ad hoc
network.
7. Performance Improvements
Nodes that implement only the basic AODV features do not economize
the use of the physical network medium, and thus are more likely to
contribute to the overall congestion in the network. This is not
a problem, as long as the medium utilization is low. However, if
network capacity limits applications, it is more important for the
AODV nodes to implement more features in order to reduce network
congestion.
Another way that performance can be improved in an ad hoc network
is to reduce the time duration of communications disruptions caused
by node movement. This can be done in several ways, notably by
the transmission of the RERR message to trigger route repair and
update mechanisms. Without RERR, the robustness of the communication
between the application endpoints becomes dependent upon recovery
methods that are been built into the application. There are
applications that have no such recover mechanisms, and those
applications, hosted on nodes that do not attempt any routing
repairs, would be adversely affected by node mobility. If any node
in the network depends on RERR messages to detect route breaks, all
nodes SHOULD support it.
Each of the performance improvements in this section SHOULD be
implemented by every AODV node, so that the network as a whole runs
in a way more responsive to application needs, and creates less
network congestion.
7.1. Operation over Unidirectional Links
It is possible that a RREP transmission may fail, especially if the
RREQ transmission triggering the RREP occurs over a unidirectional
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 15]
Internet Draft AODV 26 Jan 2004
link. If no other RREP generated from the same route discovery
attempt reaches the node which originated the RREQ message, the
originator will reattempt route discovery after a timeout (see
section 6.3). However, the same scenario might well be repeated
without any improvement, and no route would be discovered even after
repeated retries. Unless corrective action is taken, this can happen
even when bidirectional routes between originator and destination
do exist. Link layers using broadcast transmissions for the RREQ
will not be able to detect the presence of such unidirectional links.
In AODV, any node acts on only the first RREQ with the same RREQ ID
and ignores any subsequent RREQs. Suppose, for example, that the
first RREQ arrives along a path that has one or more unidirectional
link(s). A subsequent RREQ may arrive via a bidirectional path
(assuming such paths exist), but it will be ignored.
To prevent this problem, when a node detects that its transmission of
a RREP message has failed, it remembers the next-hop of the failed
RREP in a ``blacklist'' set. Such failures can be detected via
the absence of a link-layer or network-layer acknowledgment (e.g.,
RREP-ACK). A node ignores all RREQs received from any node in its
blacklist set. Nodes are removed from the blacklist set after a
BLACKLIST_TIMEOUT period. This period should be set to the upper
bound of the time it takes to perform the allowed number of route
request retry attempts as described in section 6.3.
Note that the RREP-ACK packet does not contain any information about
which RREP it is acknowledging. The time at which the RREP-ACK
is received will likely come just after the time when the RREP
was sent with the 'A' bit. This information is expected to be
sufficient to provide assurance to the sender of the RREP that the
link is currently bidirectional, without any real dependence on the
particular RREP message being acknowledged. However, that assurance
typically cannot be expected to remain in force permanently.
If unidirectional links are likely to occur the 'A' bit in RREPs
SHOULD be set.
7.2. Hello Messages
A node MAY offer connectivity information by broadcasting local
Hello messages. A node SHOULD only use hello messages if it is
participating in routing of data packets. Every HELLO_INTERVAL
milliseconds, the node checks whether it has sent a broadcast control
message (e.g., a RREQ). If it has not, it SHOULD broadcast a RREP
with TTL = 1, called a Hello message, where the RREP message fields
are set as follows:
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 16]
Internet Draft AODV 26 Jan 2004
Destination IP Address
The node's IP address.
Destination Sequence Number
The node's sequence number.
Hop Count 0
Whenever a node receives a Hello message from a neighbor, the node
SHOULD process it as a normal RREP, as specified in Section 6.6.
Additionally, a neighboring node MAY determine connectivity by
listening for packets from its set of neighbors. If an active
route to a neighbor exists but no packets from that neighbor
(Hello messages or otherwise) have been received for more than
(ALLOWED_HELLO_LOSS * HELLO_INTERVAL) milliseconds, the node SHOULD
assume that the link to this neighbor is currently lost. When this
happens, the node SHOULD invalidate the route to that neighbor and
increase the sequence number stored in the routing table by one.
Additionally, each active route in the routing table that lists this
neighbor as the next hop should be invalidated and its corresponding
sequence number incremented.
7.3. Maintaining Local Connectivity
Each forwarding node SHOULD keep track of its continued connectivity
to its active next hops as well as neighbors that have transmitted
Hello messages during the last (ALLOWED_HELLO_LOSS * HELLO_INTERVAL).
A node can maintain accurate information about its continued
connectivity to these active next hops using one or more of the
available link or network layer mechanisms, as described below.
- Any suitable link layer notification can be used to determine
connectivity each time a packet is transmitted to an active next
hop. For example, failure to transmit a packet after the maximum
number of retransmission attempts in IEEE 802.11 results in an
indicator signifying a failed transmission. This indicator can
be understood as loss of the link to the active next hop when the
network utilization is low.
- If layer-2 notification is not available, passive acknowledgment
MAY be used, when the next hop is expected to forward the packet,
by listening to the channel for a transmission attempt made by
the next hop.
- If transmission is not detected within NEXT_HOP_WAIT milliseconds
or the next hop is the destination (and thus is not likely to
forward the packet), the node may signal the next hop to cause it
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 17]
Internet Draft AODV 26 Jan 2004
to transmit a packet in return. Many methods may be used. For
example, sending an ICMP Echo Request message to the next hop
should cause the next hop to send an Echo Reply.
- Use of Hello messages.
If a link to the next hop cannot be detected by any of these
methods, the node SHOULD assume that the link is lost after
(ALLOWED_HELLO_LOSS * HELLO_INTERVAL) milliseconds. It should
invalidate the route to the next hop and increase the destination
sequence number by one. Additionally, for all active routes that
utilize the lost link as the next hop, these routes should be
invalidated and their sequence numbers incremented by one.
7.4. Generating Route Error Messages
When a data packet for an inactive route or unknown destination is
received, a Route Error (RERR) message is generated. The Unreachable
Destination field is the IP address of the inactive or unknown
destination. If an inactive route exists in the routing table, the
Unreachable Destination Sequence Number field of the RERR is filled
with the value in the routing table; otherwise zero (0) is placed
in the Unreachable Destination Sequence Number field of the RERR.
All unreachable destinations, with the same next hop, and their
corresponding sequence numbers SHOULD be placed in the same RERR
message. Then the RERR message is broadcast to all neighbors. A
node SHOULD NOT generate more than RERR_RATELIMIT RERR messages per
second.
The RERR is sent to the local broadcast address (Destination IP
== 255.255.255.255, TTL == 1) with the unreachable destinations,
and their corresponding sequence numbers included in the packet.
The DestCount field of the RERR packet indicates the number of
unreachable destinations included in the packet.
7.5. Receiving Route Error Messages
When a node receives a RERR message, and a route to the next hop
does not already exist, a route MAY be created for the previous
hop without a valid sequence number and a hop count of one (1)
(see Section 6.2). Then the node compares the first unreachable
destination listed in the RERR to the routes in its routing table.
If a route to the unreachable destination exists and the next hop
listed in the routing table entry is the node that sent this RERR
(indicated by the source IP address field in the IP header), and
either:
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 18]
Internet Draft AODV 26 Jan 2004
(i) the Unreachable Destination Sequence Number in the RERR
is zero (0), or
(ii) the Unreachable Destination Sequence Number in the RERR
is higher than the destination sequence number listed in
the routing table for the unreachable destination
then the route is invalidated and the destination sequence number
for the unreachable destination is updated to be the maximum of the
sequence number listed in the routing table entry and the Unreachable
Destination Sequence number from the RERR. If a route is invalidated
then a RERR message is created to be broadcast with the unreachable
destination.
If additional unreachable destinations are listed in the RERR they
MAY be used to invalidate other unreachable destinations as described
above.
Any additional destinations that became unreachable due to the
processing of this RERR SHOULD be added to the new RERR message sent
by this node.
7.6. Intermediate Node Route Replies
An intermediate node MAY generate a RREP if it has an active route
to the destination and the destination-only flag is not set. If
an intermediate node generates the response, it places the known
destination sequence number from the routing table entry for the
destination into the Destination Sequence Number field of the RREP,
and places the known hop count from the routing table entry into the
Hop Count field in the RREP.
When generating a RREP message, a node copies the Destination IP
Address, Originator IP Address and Originator Sequence Number from
the RREQ message into the corresponding fields of the RREP message.
In addition, the accumulated path list from the RREQ is appended to
the RREP in the same order as listed in the RREQ. The APN Count field
is set to the length of the accumulated path node list.
Once created, the RREP is unicast to the next hop toward the
originator of the RREQ, indicated by the last entry in the
accumulated path list.
If the Gratuitous Route Reply flag is set, the intermediate node MUST
generate a Gratuitous Route Reply.
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 19]
Internet Draft AODV 26 Jan 2004
7.6.1. Generating Gratuitous Route Replies
After an intermediate node receives a RREQ and responds with a RREP,
it discards the RREQ. If the RREQ has the 'G' flag set, and the
intermediate node returns a RREP to the originating node, it MUST
also send a gratuitous RREP to the destination node. The gratuitous
RREP that is to be sent to the desired destination contains the
following values in the RREP message fields:
APN Count 0
Hop Count The Hop Count as indicated in the
node's route table entry for the
originator
Destination IP Address
The IP address of the node that
originated the RREQ
Destination Sequence Number
The Originator Sequence Number from
the RREQ
Originator IP Address
The IP address of the Destination
node in the RREQ
Originator Sequence Number
The Sequence Number of the
Destination node in the RREQ
The gratuitous RREP is then sent to the next hop along the path to
the destination node, just as if the destination node had already
issued a RREQ for the originating node and this RREP was produced
in response to that (fictitious) RREQ. The RREP that is sent to the
originator of the RREQ is the same whether or not the 'G' bit is set.
7.7. Actions After Reboot
Transient routing loops SHOULD be protected against in an ad hoc
network, because whenever the transient condition occurs, there is
a lot of unnecessary routing and energy expenditure by the nodes
creating the loop. For this reason, AODV nodes SHOULD implement the
simple protective measures specified in this section.
A node participating in the ad hoc network must take certain actions
after reboot if it loses its own sequence number. Otherwise, if
neighboring nodes are using this node as an active next hop, there
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 20]
Internet Draft AODV 26 Jan 2004
would be a potential for routing loops. To prevent this possibility,
each node (if it has lost its sequence number) on reboot waits for
DELETE_PERIOD before transmitting any route discovery messages.
During this time, if the node receives a RREQ, RREP, or RERR control
packet, it SHOULD create route entries as appropriate given the
sequence number information in the control packets, but it MUST not
forward any control packets. If the node receives a data packet for
some unicast destination, it SHOULD broadcast a RERR as described in
Section 7.4 and MUST reset the reboot waiting timer to expire after
current time plus DELETE_PERIOD.
It can be shown [6] that by the time the rebooted node comes out of
the waiting phase and resumes routing again, its neighbors will no
longer be using it as an active next hop. Its own sequence number
is updated once it receives a RREQ from any other node, as the RREQ
always carries the maximum destination sequence number seen en route.
If no such RREQ arrives, the node may initialize its own sequence
number to any allowable value other than zero (0) (for example, (1)).
8. AODV and Aggregated Networks
AODV has been designed for use by mobile nodes with IP addresses that
are not necessarily related to each other. However, in some cases
a collection of mobile nodes MAY operate in a fixed relationship to
each other and share a common subnet prefix, moving together within
the ad hoc network. Call such a collection of nodes a ``subnet''.
In this case, it is possible for a single node within the subnet
to advertise reachability for all other nodes in the subnet, by
responding with an appropriate RREP message to any RREQ message
requesting a route to any node sharing the subnet routing prefix.
Call this single node the ``subnet router''. In order for a subnet
router to operate the AODV protocol for the whole subnet, it has to
maintain a destination sequence number for the entire subnet. In
any RREP message sent by the subnet router, the Hostid Size field of
the RREP message MUST be set to the number of bits of the IP address
that remain, after subtracting the bits that are used for the subnet
prefix. Other nodes sharing the subnet prefix SHOULD NOT issue RREP
messages, and SHOULD forward RREQ messages to the subnet router. The
router supplies data to indicate the number of bits in the Hostid,
instead of the number of bits in the subnet prefix, in order to
maintain compatibility with hosts in the ad hoc network that ignore
nonzero Hostid Size fields. When the Hostid Size field is zero (or
ignored), the recipient of the RREP treats the information in that
message as if there were no subnet routers.
The processing of RREPs that give routes to subnets (i.e.,
have nonzero Hostid Size fields) is the same as processing for
host-specific RREP messages. Every node that receives the RREP with
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 21]
Internet Draft AODV 26 Jan 2004
Hostid Size information SHOULD create or update the route table entry
for the subnet. Then, in the future nodes with this subnet route can
use the information to avoid sending RREQs for other nodes in the
same subnet.
When a node uses a subnet route it may be that a packet is routed
to an IP address on the subnet that is not assigned to any existing
node in the ad hoc network. When that happens, the subnet router
MUST return ICMP Host Unreachable message to the sending node.
Upstream nodes receiving such an ICMP message SHOULD record the
information that the particular IP address is unreachable, but MUST
NOT invalidate the route entry for any matching subnet prefix.
If several nodes in the subnet advertise reachability to the subnet
defined by the subnet prefix, the node with the lowest IP address
is elected to be the subnet router, and all other nodes MUST stop
advertising reachability.
The behavior of default routes (i.e., routes with routing prefix
length 0) is not defined in this specification. Selection of routes
sharing prefix bits should be according to longest match first.
9. IPv6 Operation
For operation in IPv6 networks the IP addresses in AODV control
messages are 128 bits (instead of 32 bits). When AODV recognizes
that a control message was delivered using an IPv6 packet header,
then all IP address fields are expected to contain 128 bit addresses.
Besides the change in IP address length, all other protocol message
fields and functionality remain unchanged.
10. Extensions
In this section, the format of extensions to the RREQ and RREP
messages is specified. All such extensions appear after the message
data, and have the following format:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | type-specific data ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
where:
Type 1-255
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 22]
Internet Draft AODV 26 Jan 2004
Length The length of the type-specific data, not including the
Type and Length fields of the extension in bytes.
Extensions with types between 128 and 255 may NOT be skipped. The
rules for extensions conform to the rules for handling IPv6 options.
10.1. Lifetime Extension Format
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Length | Lifetime ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... Lifetime, continued |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type 2
Length 4
Lifetime The number of milliseconds to be added to the lifetime
field for this route entry.
The Lifetime extension MAY be appended to a RREQ or RREP. If this
field is used the Lifetime value from the extension SHOULD be used to
update the lifetime field in the routing table for this active route
entry instead of ACTIVE_ROUTE_TIMEOUT.
11. Configuration Parameters
This section gives default values for some important parameters
associated with AODV protocol operations.
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 23]
Internet Draft AODV 26 Jan 2004
Parameter Name Value
---------------------- -----
NODE_TRAVERSAL_TIME 10 milliseconds
NET_DIAMETER 20
NET_TRAVERSAL_TIME 2 * NODE_TRAVERSAL_TIME * NET_DIAMETER
PATH_DISCOVERY_TIME 2 * NET_TRAVERSAL_TIME
ACTIVE_ROUTE_TIMEOUT 2 * NET_TRAVERSAL_TIME
DELETE_PERIOD 5 * NET_TRAVERSAL_TIME
RREQ_TRIES 3
RREQ_RATELIMIT 10
RERR_RATELIMIT 10
HELLO_INTERVAL 1,000 milliseconds
ALLOWED_HELLO_LOSS 2
NEXT_HOP_WAIT 2 * NODE_TRAVERSAL_TIME
BLACKLIST_TIMEOUT RREQ_RETRIES * NET_TRAVERSAL_TIME
For correct operation ACTIVE_ROUTE_TIMEOUT MUST be greater than
both (ALLOWED_HELLO_LOSS * HELLO_INTERVAL) and NET_TRAVERSAL_TIME.
Likewise, DELETE_PERIOD MUST be greater than ACTIVE_ROUTE_TIMEOUT.
12. Security Considerations
Currently, AODV does not specify any special security measures.
Routing protocols, however, are prime targets for impersonation
attacks. In networks where the node membership is not known, it
is difficult to determine the occurrence of impersonation attacks,
and security prevention techniques are difficult at best. However,
when the network membership is known and there is a danger of
such attacks, AODV control messages must be protected by the use
of authentication techniques, such as those involving generation
of unforgeable and cryptographically strong message digests or
digital signatures. While AODV does not place restrictions on the
authentication mechanism used for this purpose, IPsec Authentication
Header (AH) is an appropriate choice for cases where the nodes share
an appropriate security association that enables the use of AH.
In particular, RREP messages SHOULD be authenticated to avoid
creation of spurious routes to a destination. Otherwise, an attacker
could masquerade as that destination, and maliciously deny service
to the destination and/or maliciously inspect and consume traffic
intended for delivery to the destination. RERR messages, while less
dangerous, SHOULD be authenticated in order to prevent malicious
nodes from disrupting active routes between communicating nodes.
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 24]
Internet Draft AODV 26 Jan 2004
AODV does not make any assumption about the method by which addresses
are assigned to the mobile nodes except that they are presumed to
have unique IP addresses. Therefore, no special consideration, other
than what is natural because of the general protocol specifications,
can be made about the applicability of IPsec authentication headers
or key exchange mechanisms. However, if the mobile nodes in the ad
hoc network have preestablished security associations, it is presumed
that the purposes for which the security associations are created
include that of authorizing the processing of AODV control messages.
Given this understanding, the mobile nodes should be able to use the
same authentication mechanisms based on their IP addresses as they
would have used otherwise.
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 25]
Internet Draft AODV 26 Jan 2004
13. IANA Considerations
AODV defines a "Type" field for messages sent to port 654. A new
registry is to be created for the values for this Type field, and the
following values assigned:
Message Type Value
--------------------------- -----
Route Request (RREQ) 1
Route Reply (RREP) 2
Route Error (RERR) 3
Route-Reply Ack (RREP-ACK) 4
AODV control messages can have extensions. Currently, only one
extension is defined. A new registry is to be created for the Type
field of the extensions:
Extension Type Value
--------------------------- -----
Lifetime 1
Future values of the Message Type or Extension Type can be allocated
using standards action [2].
14. Acknowledgments
Special thanks to Samir Das, University of Cincinnati, for his
extensive contributions to prior revisions.
We acknowledge with gratitude the work done at University of
Pennsylvania within Carl Gunter's group, as well as at Stanford and
CMU, to determine some conditions (especially involving reboots and
lost RERRs) under which previous versions of AODV could suffer from
routing loops. Contributors to those efforts include Karthikeyan
Bhargavan, Joshua Broch, Dave Maltz, Madanlal Musuvathi, and
Davor Obradovic. The idea of a DELETE_PERIOD, for which expired
routes (and, in particular, the sequence numbers) to a particular
destination must be maintained, was also suggested by them.
We also acknowledge the comments and improvements suggested by
Sung-Ju Lee, Mahesh Marina, Erik Nordstrom, Yves Prelot, Marc Mosko,
Manel Guerrero Zapata, Philippe Jacquet, Fred Baker, and Chris
Shiflet.
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 26]
Internet Draft AODV 26 Jan 2004
We also acknowledge David Johnson, David Maltz and Yih-Chun Hu for
presenting path accumulation, part of the DSR protocol [7]. AODVbis
uses path accumulation to disseminate routing information during
route discovery and reduce the number of route requests.
References
[1] S. Bradner. Key words for use in RFCs to Indicate Requirement
Levels. Request for Comments (Best Current Practice) 2119,
Internet Engineering Task Force, March 1997.
[2] T. Narten and H. Alvestrand. Guidelines for Writing an IANA
Considerations Section in RFCs. Request for Comments (Best
Current Practice) 2434, Internet Engineering Task Force, October
1998.
[3] C. Perkins, E. Belding-Royer, and S. Das. Ad hoc on demand
distance vector (AODV) routing (work in progress). Request for
Comments (Experimental Standard) 3561, Internet Engineering Task
Force, July 2003.
[4] J. Manner et al. Mobility Related Terminology (work in
progress). Internet Draft, Internet Engineering Task Force,
November 2003.
[5] Ian D. Chakeres and Luke Klein-Berndt. AODVjr: AODV Simplified.
In ACM SIGMOBILE Mobile Computing and Communications Review,
pages 100--101, July 2002.
[6] Karthikeyan Bhargavan, Carl A. Gunter, and Davor Obradovic.
Fault Origin Adjudication. In Proceedings of the Workshop on
Formal Methods in Software Practice, Portland, OR, August 2000.
[7] D. Johnson and D. Maltz. Dynamic source routing in ad-hoc
wireless networks. In Computer Communications Review --
Proceedings of SIGCOMM '96, August 1996.
References [1], [2] and [3] are normative; all others are
informative.
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 27]
Internet Draft AODV 26 Jan 2004
A. Draft Modifications
The following are major changes between this version (01) of the AODV
draft and previous versions:
- Removed valid/invalid route definition in favor of
active/inactive route.
- Allow and specified operation for nodes that forward RREP using
active route information instead of accumulated path information.
- Clarified Sequence Number handling upon RREP receipt.
- Clarified Hostid Size field meaning.
- Reduced the strict dependence on hop count during route update
decision.
- Added IPv6 Operation Section.
Author's Addresses
Questions about this memo can be directed to:
Charles E. Perkins
Communications Systems Laboratory
Nokia Research Center
313 Fairchild Drive
Mountain View, CA 94303
USA
+1 650 625 2986
+1 650 691 2170 (fax)
charles.perkins@nokia.com
Elizabeth M. Belding-Royer
Department of Computer Science
University of California, Santa Barbara
Santa Barbara, CA 93106
+1 805 893 3411
+1 805 893 8553 (fax)
ebelding@cs.ucsb.edu
Ian D. Chakeres
Department of Electrical and Computer Engineering
University of California, Santa Barbara
Santa Barbara, CA 93106
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 28]
Internet Draft AODV 26 Jan 2004
+1 805 893 8981
+1 805 893 8553 (fax)
idc@engineering.ucsb.edu
Perkins, Belding-Royer, Chakeres Expires 26 July 2004 [Page 29]