draft-ietf-manet-aodv-08.txt   draft-ietf-manet-aodv-09.txt 
Mobile Ad Hoc Networking Working Group Charles E. Perkins Mobile Ad Hoc Networking Working Group Charles E. Perkins
INTERNET DRAFT Nokia Research Center INTERNET DRAFT Nokia Research Center
2 March 2001 Elizabeth M. Royer 9 November 2001 Elizabeth M. Belding-Royer
University of California, Santa Barbara University of California, Santa Barbara
Samir R. Das Samir R. Das
University of Cincinnati University of Cincinnati
Ad hoc On-Demand Distance Vector (AODV) Routing Ad hoc On-Demand Distance Vector (AODV) Routing
draft-ietf-manet-aodv-08.txt draft-ietf-manet-aodv-09.txt
Status of This Memo Status of This Memo
This document is a submission by the Mobile Ad Hoc Networking Working This document is a submission by the Mobile Ad Hoc Networking Working
Group of the Internet Engineering Task Force (IETF). Comments should Group of the Internet Engineering Task Force (IETF). Comments should
be submitted to the manet@itd.nrl.navy.mil mailing list. be submitted to the manet@itd.nrl.navy.mil mailing list.
Distribution of this memo is unlimited. Distribution of this memo is unlimited.
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is in full conformance with
skipping to change at page 1, line 59 skipping to change at page 1, line 59
Contents Contents
Status of This Memo i Status of This Memo i
Abstract i Abstract i
1. Introduction 1 1. Introduction 1
2. Overview 1 2. Overview 1
3. AODV Terminology 2 3. AODV Terminology 3
4. Route Request (RREQ) Message Format 3 4. Route Request (RREQ) Message Format 4
5. Route Reply (RREP) Message Format 4 5. Route Reply (RREP) Message Format 6
6. Route Error (RERR) Message Format 6 6. Route Error (RERR) Message Format 7
7. Route Reply Acknowledgment (RREP-ACK) Message Format 7 7. Route Reply Acknowledgment (RREP-ACK) Message Format 8
8. AODV Operation 7 8. AODV Operation 8
8.1. Maintaining Route Utilization Records . . . . . . . . . . 7 8.1. Maintaining Sequence Numbers . . . . . . . . . . . . . . 8
8.2. Generating Route Requests . . . . . . . . . . . . . . . . 7 8.2. Maintaining Route Table Entries and Route Utilization
8.2.1. Controlling Route Request broadcasts . . . . . . 8 Records . . . . . . . . . . . . . . . . . . . . . . . 9
8.3. Forwarding Route Requests . . . . . . . . . . . . . . . . 9 8.3. Generating Route Requests . . . . . . . . . . . . . . . . 10
8.3.1. Processing Route Requests . . . . . . . . . . . . 9 8.4. Controlling Dissemination of Route Request Messages . . . 11
8.4. Generating Route Replies . . . . . . . . . . . . . . . . 11 8.5. Processing and Forwarding Route Requests . . . . . . . . 12
8.4.1. Route Reply Generation by the Destination . . . 11 8.6. Generating Route Replies . . . . . . . . . . . . . . . . 13
8.4.2. Route Reply Generation by an Intermediate Node . 11 8.6.1. Route Reply Generation by the Destination . . . . 14
8.4.3. Generating Gratuitous RREPs . . . . . . . . . . . 12 8.6.2. Route Reply Generation by an Intermediate Node . 14
8.5. Forwarding Route Replies . . . . . . . . . . . . . . . . 13 8.6.3. Generating Gratuitous RREPs . . . . . . . . . . . 15
8.6. Operation over Unidirectional Links . . . . . . . . . . . 14 8.7. Forwarding Route Replies . . . . . . . . . . . . . . . . 15
8.7. Hello Messages . . . . . . . . . . . . . . . . . . . . . 14 8.8. Operation over Unidirectional Links . . . . . . . . . . . 16
8.8. Maintaining Local Connectivity . . . . . . . . . . . . . 15 8.9. Hello Messages . . . . . . . . . . . . . . . . . . . . . 17
8.9. Route Error Messages . . . . . . . . . . . . . . . . . . 16 8.10. Maintaining Local Connectivity . . . . . . . . . . . . . 18
8.9.1. Local Repair . . . . . . . . . . . . . . . . . . 17 8.11. Route Error Messages . . . . . . . . . . . . . . . . . . 18
8.10. Route Expiry and Deletion . . . . . . . . . . . . . . . . 18 8.12. Local Repair . . . . . . . . . . . . . . . . . . . . . . 20
8.11. Actions After Reboot . . . . . . . . . . . . . . . . . . 19 8.13. Route Expiry and Deletion . . . . . . . . . . . . . . . . 21
8.12. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 19 8.14. Actions After Reboot . . . . . . . . . . . . . . . . . . 22
8.15. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 22
9. AODV and Aggregated Networks 20 9. AODV and Aggregated Networks 23
10. Using AODV with Other Networks 20 10. Using AODV with Other Networks 23
11. Extensions 20 11. Extensions 24
11.1. Hello Interval Extension Format . . . . . . . . . . . . . 21 11.1. Hello Interval Extension Format . . . . . . . . . . . . . 24
12. Configuration Parameters 21 12. Configuration Parameters 25
13. Security Considerations 23 13. Security Considerations 26
14. Acknowledgments 23 14. Acknowledgments 27
A. Draft Modifications 28
1. Introduction 1. Introduction
The Ad Hoc On-Demand Distance Vector (AODV) algorithm enables The Ad Hoc On-Demand Distance Vector (AODV) algorithm enables
dynamic, self-starting, multihop routing between participating mobile dynamic, self-starting, multihop routing between participating mobile
nodes wishing to establish and maintain an ad hoc network. AODV nodes wishing to establish and maintain an ad hoc network. AODV
allows mobile nodes to obtain routes quickly for new destinations, allows mobile nodes to obtain routes quickly for new destinations,
and does not require nodes to maintain routes to destinations that and does not require nodes to maintain routes to destinations that
are not in active communication. AODV allows mobile nodes to respond are not in active communication. AODV allows mobile nodes to respond
quickly to link breakages and changes in network topology. The quickly to link breakages and changes in network topology. The
skipping to change at page 1, line 129 skipping to change at page 1, line 132
sequence number for each route entry. The destination sequence sequence number for each route entry. The destination sequence
number is created by the destination for any route information it number is created by the destination for any route information it
sends to requesting nodes. Using destination sequence numbers sends to requesting nodes. Using destination sequence numbers
ensures loop freedom and is simple to program. Given the choice ensures loop freedom and is simple to program. Given the choice
between two routes to a destination, a requesting node always selects between two routes to a destination, a requesting node always selects
the one with the greatest sequence number. the one with the greatest sequence number.
2. Overview 2. Overview
Route Requests (RREQs), Route Replies (RREPs), and Route Errors Route Requests (RREQs), Route Replies (RREPs), and Route Errors
(RERRs) are the message types defined by AODV. These message types (RERRs) are the message types defined by AODV. These message
are handled by UDP, and normal IP header processing applies. So, for types are received at port 654, over UDP, and normal IP header
instance, the requesting node is expected to use its IP address as processing applies. So, for instance, the requesting node is
the source IP address for the messages. The range of dissemination expected to use its IP address as the source IP address for the
of broadcast RREQs can be indicated by the TTL in the IP header. 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 that
certain messages (e.g., RREQ) have to be disseminated widely,
perhaps throughout the ad hoc network. The range of dissemination
of such flooded RREQs is indicated by the TTL in the IP header.
Fragmentation is typically not required. Fragmentation is typically not required.
As long as the endpoints of a communication connection have valid 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 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 new destination is needed, the node uses a broadcast RREQ to find
a route to the destination. A route can be determined when the RREQ a route to the destination. A route can be determined when the RREQ
reaches either the destination itself, or an intermediate node with reaches either the destination itself, or an intermediate node with
a 'fresh enough' route to the destination. A 'fresh enough' route a 'fresh enough' route to the destination. A 'fresh enough' route
is an unexpired route entry for the destination whose associated is an unexpired route entry for the destination whose associated
sequence number is at least as great as that contained in the RREQ. sequence number is at least as great as that contained in the RREQ.
The route is made available by unicasting a RREP back to the source The route is made available by unicasting a RREP back to the source
of the RREQ. Since each node receiving the request caches a route of the RREQ. Each node receiving the request caches a route back to
back to the source of the request, the RREP can be unicast back from the originator of the request, so that the the RREP can be unicast
the destination to the source, or from any intermediate node that from the destination along a path to that originator, or likewise
is able to satisfy the request back to the source. A RREQ can be from any intermediate node that is able to satisfy the request.
conditioned by requirements on the path to the destination, namely
bandwidth or delay bounds.
Nodes monitor the link status of next hops in active routes. When a Nodes monitor the link status of next hops in active routes. When
link break in an active route is detected, a RERR message is used to a link break in an active route is detected, a RERR message is used
notify other nodes that the loss of that link has occurred. The RERR to notify other nodes that the loss of that link has occurred. The
message indicates which destinations are now unreachable due to the RERR message indicates which destinations are now unreachable due to
loss of the link. the loss of the link. In order to enable this reporting mechanism,
each node keeps a ``precursor list'', containing the IP address for
each its neighbors that are likely to use it as a next hop towards
the destination which is now unreachable. The information in the
precursor lists is most easily acquired during the processing for
generation of a RREP message, which by definition has to be sent to a
node in a precursor list (see section 8.6).
A RREQ may also be received for a multicast IP address. In this
document, full processing for such messages is not specified. For
example, the source of such an RREQ for a multicast IP address may
have to follow special rules. However, it is important to enable
correct multicast operation by intermediate nodes that are not
enabled as source or destination nodes for IP multicast addresses,
and likewise are not equipped for any special multicast protocol
processing. For such multicast-unaware nodes, processing for a
multicast IP address as a destination IP address MUST be carried out
in the same way as for any other destination IP address.
AODV is a routing protocol, and it deals with route table management. AODV is a routing protocol, and it deals with route table management.
Route table information must be kept even for ephemeral routes, such Route table information must be kept even for ephemeral routes, such
as are created to temporarily store reverse paths towards nodes as are created to temporarily store reverse paths towards nodes
originating RREQs. AODV uses the following fields with each route originating RREQs. AODV uses the following fields with each route
table entry: table entry:
- Destination IP Address - Destination IP Address
- Destination Sequence Number - Destination Sequence Number
- Interface - Interface
- Hop Count (number of hops needed to reach destination) - Hop Count (number of hops needed to reach destination)
- Last Hop Count (described in subsection 8.2.1) - Last Hop Count (described in subsections 8.4 and 8.11)
- Next Hop - Next Hop
- List of Precursors (described in Section 8.1) - List of Precursors (described in Section 8.2)
- Lifetime (expiration or deletion time of the route) - Lifetime (expiration or deletion time of the route)
- Routing Flags - Routing Flags
Managing the sequence number is crucial to avoiding routing loops,
even when links break and a node is no longer reachable to supply
its own information about its sequence number. A destination
becomes unreachable when a link breaks or is deactivated. When these
conditions occur, the node detecting the condition increments the
destination's sequence number and the metric in the route table entry
is assigned to be infinite. See section 8.1 for details.
3. AODV Terminology 3. AODV Terminology
This protocol specification uses conventional meanings [1] for This protocol specification uses conventional meanings [2] for
capitalized words such as MUST, SHOULD, etc., to indicate requirement capitalized words such as MUST, SHOULD, etc., to indicate requirement
levels for various protocol features. This section defines other levels for various protocol features. This section defines other
terminology used with AODV that is not already defined in [3]. terminology used with AODV that is not already defined in [3].
active route active route
A routing table entry with a finite metric in the Hop Count A routing table entry with a finite metric in the Hop Count
field. A routing table may contain entries that are not active field. A routing table may contain entries that are not active
(invalid routes or entries). They have an infinite metric (invalid routes or entries). They have an infinite metric
in the Hop Count field. Only active entries can be used to in the Hop Count field. Only active entries can be used to
forward data packets. Invalid entries are eventually deleted. forward data packets. Invalid entries are eventually deleted.
broadcast
Broadcasting means transmitting to the IP Limited Broadcast
address, 255.255.255.255. A broadcast packet may not be
blindly forwarded, but broadcasting is useful to enable
flooding.
flood
Flooding means to send a message to every node of the ad hoc
network, or to every node in an region of the ad hoc network.
In AODV, a message is flooded by iterated use of broadcast, for
which receivers must also rebroadcast after their processing
steps have been completed for that message.
forwarding node forwarding node
A node which agrees to forward packets destined for another A node which agrees to forward packets destined for another
destination node, by retransmitting them to a next hop which is destination node, by retransmitting them to a next hop which is
closer to the unicast destination along a path which has been closer to the unicast destination along a path which has been
set up using routing control messages. set up using routing control messages.
forward route forward route
A route set up to send data packets from a source to a A route set up to send data packets from a source to a
destination. destination.
originating node
A node which initiates an AODV message which is the processed
and possibly retransmitted by other nodes in the ad hoc
network. For instance, the node initiating a Route Discovery
process and flooding the RREQ message is called the originating
node of the RREQ message.
reverse route reverse route
A route set up to forward a reply (RREP) packet back to the A route set up to forward a reply (RREP) packet back to the
source from the destination or from an intermediate node having source from the destination or from an intermediate node having
a route to the destination. a route to the destination.
4. Route Request (RREQ) Message Format 4. Route Request (RREQ) Message Format
0 1 2 3 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 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 |J|R|G| Reserved | Hop Count | | Type |J|R|G| Reserved | Hop Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Broadcast ID | | Flooding ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination IP Address | | Destination IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Sequence Number | | Destination Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source IP Address | | Source IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Sequence Number | | Source Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at page 3, line 47 skipping to change at page 5, line 4
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source IP Address | | Source IP Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source Sequence Number | | Source Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The format of the Route Request message is illustrated above, and The format of the Route Request message is illustrated above, and
contains the following fields: contains the following fields:
Type 1 Type 1
J Join flag; reserved for multicast. J Join flag; reserved for multicast.
R Repair flag; reserved for multicast. R Repair flag; reserved for multicast.
G Gratuitous RREP flag; indicates whether a G Gratuitous RREP flag; indicates whether a
gratuitous RREP should be unicast to the node gratuitous RREP should be unicast to the node
specified in the Destination IP Address field (see specified in the Destination IP Address field (see
sections 8.2, 8.4.3) sections 8.3, 8.6.3)
Reserved Sent as 0; ignored on reception. Reserved Sent as 0; ignored on reception.
Hop Count The number of hops from the Source IP Address to Hop Count The number of hops from the Source IP Address to
the node handling the request. the node handling the request.
Broadcast ID A sequence number uniquely identifying the Flooding ID A sequence number uniquely identifying the
particular RREQ when taken in conjunction with the particular RREQ when taken in conjunction with the
source node's IP address. source node's IP address.
Destination IP Address Destination IP Address
The IP address of destination for which a route is The IP address of destination for which a route is
desired. desired.
Destination Sequence Number Destination Sequence Number
The last sequence number received in the past by The last sequence number received in the past by
the source for any route towards the destination. the source for any route towards the destination.
skipping to change at page 5, line 4 skipping to change at page 6, line 20
| Type |R|A| Reserved |Prefix Sz| Hop Count | | Type |R|A| Reserved |Prefix Sz| Hop Count |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination IP address | | Destination IP address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Destination Sequence Number | | Destination Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Source IP address | | Source IP address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Lifetime | | Lifetime |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
The format of the Route Reply message is illustrated above, and The format of the Route Reply message is illustrated above, and
contains the following fields: contains the following fields:
Type 2 Type 2
R Repair flag; used for multicast. R Repair flag; used for multicast.
A Acknowledgment required; see sections 7 and 8.5. A Acknowledgment required; see sections 7 and 8.7.
Reserved Sent as 0; ignored on reception. Reserved Sent as 0; ignored on reception.
Prefix Size If nonzero, the 5-bit Prefix Size specifies that the Prefix Size If nonzero, the 5-bit Prefix Size specifies that the
indicated next hop may be used for any nodes with indicated next hop may be used for any nodes with
the same routing prefix (as defined by the Prefix the same routing prefix (as defined by the Prefix
Size) as the requested destination. Size) as the requested destination.
Hop Count The number of hops from the Source IP Address to Hop Count The number of hops from the Source IP Address to
the Destination IP Address. For multicast route the Destination IP Address. For multicast route
skipping to change at page 7, line 23 skipping to change at page 8, line 30
Type 4 Type 4
Reserved Sent as 0; ignored on reception. Reserved Sent as 0; ignored on reception.
The RREP-ACK message may be used to acknowledge receipt of a RREP The RREP-ACK message may be used to acknowledge receipt of a RREP
message. It is used in cases where the link over which the RREP message. It is used in cases where the link over which the RREP
message is sent may be unreliable. message is sent may be unreliable.
8. AODV Operation 8. AODV Operation
This section describes the scenarios under which nodes generate This section describes the scenarios under which nodes generate Route
RREQs, RREPs and RERRs for unicast communication, and how the message Request (RREQ), Route Replie (RREP) and Route Error (RERR) messages
data are handled. for unicast communication towards a destination, and how the message
data are handled. In order to process the messages correctly,
certain state information has to be maintained for the route table
entries for the destinations of interest.
8.1. Maintaining Route Utilization Records All AODV messages are sent to port 654 using UDP.
8.1. Maintaining Sequence Numbers
AODV depends on each node in the network to own and maintain a
sequence number 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 originates a RREQ flood, it MUST
increment its own sequence number. This prevents problems with
deleted reverse routes to the originator of a RREQ.
- Immediately before a destination node orginates 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.
Every route table entry at every node MUST include the latest
information available about the sequence number for the IP address of
the destination node for which the route table entry is maintained.
This sequence number is called the "destination sequence number".
It is updated whenever a node receives new information about the
sequence number from RREQ, RREP, or RERR messages that may be
received related to that destination.
The only other circumstance in which a node may change the
destination sequence number in one of its route table entries is
in response to a broken or expired link to the next hop towards
that destination. The node can easily determine which destinations
use a broken next hop by consulting its precursor lists for the
next hop. In this case, for each destination which uses the next
hop, the node increments the sequence number and puts the Hop
Count to be "infinity" (for the case of broken links, see also see
sections 8.11, 8.12).
In summary, a node may change the sequence number for a particular
destination only if:
- it is itself the destination node, and offers a new route to
itself
- it receives an AODV message with new information about the
sequence number for some other destination node
- the path towards the destination node expires or breaks.
8.2. Maintaining Route Table Entries and Route Utilization Records
For each valid route maintained by a node (containing a finite Hop For each valid route maintained by a node (containing a finite Hop
Count metric) as a routing table entry, the node also maintains a Count metric) as a routing table entry, the node also maintains a
list of precursors that may be forwarding packets on this route. list of precursors that may be forwarding packets on this route.
These precursors will receive notifications from the node in the These precursors will receive notifications from the node in the
event of detection of the loss of the next hop link. The list of event of detection of the loss of the next hop link. The list of
precursors in a routing table entry contains those neighboring nodes precursors in a routing table entry contains those neighboring nodes
to which a route reply was generated or forwarded. to which a route reply was generated or forwarded.
When a node receives an AODV control packet from a neighbor, it
checks its route table for an entry for that neighbor. In the
event that there is no corresponding entry for that neighbor, an
entry is created. The sequence number is either determined from
the information contained in the control packet (i.e., the neighbor
is the source of a RREQ), or else it is initialized to zero if the
sequence number for that node can not be determined. The lifetime
for the routing table entry is either determined from the control
packet (i.e., the neighbor is the originator of a RREP for itself),
or it is initialized to MY_ROUTE_TIMEOUT. The hopcount to the
neighbor is set to one.
Each time a route is used to forward a data packet, its Lifetime Each time a route is used to forward a data packet, its Lifetime
field is updated to be current time plus ACTIVE_ROUTE_TIMEOUT. field is updated to be no less than the current time plus
ACTIVE_ROUTE_TIMEOUT. Since the route between each source and
destination pair are expected to be symmetric, the Lifetime
for the previous hop, along the reverse path back to the IP
source, is also updated to be no less than the current time plus
ACTIVE_ROUTE_TIMEOUT.
8.2. Generating Route Requests 8.3. Generating Route Requests
A node broadcasts a RREQ when it determines that it needs a route A node floods a RREQ when it determines that it needs a route to
to a destination and does not have one available. This can happen a destination and does not have one available. This can happen
if the destination is previously unknown to the node, or if a if the destination is previously unknown to the node, or if a
previously valid route to the destination expires or is broken previously valid route to the destination expires or is broken
(i.e., an infinite metric is associated with the route). The (i.e., an infinite metric is associated with the route). The
Destination Sequence Number field in the RREQ message is the last Destination Sequence Number field in the RREQ message is the last
known destination sequence number for this destination and is copied known destination sequence number for this destination and is copied
from the Destination Sequence Number field in the routing table. If from the Destination Sequence Number field in the routing table. If
no sequence number is known, a sequence number of zero is used. The no sequence number is known, a sequence number of zero is used. The
Source Sequence Number in the RREQ message is the node's own sequence Source Sequence Number in the RREQ message is the node's own sequence
number. The Broadcast ID field is incremented by one from the last number. The Flooding ID field is incremented by one from the last
broadcast ID used by the current node. Each node maintains only one Flooding ID used by the current node. Each node maintains only one
broadcast ID. The Hop Count field is set to zero. Flooding ID. The Hop Count field is set to zero.
Before flooding the RREQ, the source node buffers the Flooding
ID and the Source IP address (its own address) of the RREQ for
FLOOD_RECORD_TIME milliseconds. In this way, when the node receives
the packet again as it is flooded by its neighbors, it will not
reprocess and re-forward the packet.
A source node often expects to have bidirectional communications with A source node often expects to have bidirectional communications with
a destination node. In such cases, it is not sufficient for the a destination node. In such cases, it is not sufficient for the
source node to have a route to the destination node; the destination source node to have a route to the destination node; the destination
must also have a route back to the source node. In order for this must also have a route back to the source node. In order for this
to happen as efficiently as possible, any generation of an RREP to happen as efficiently as possible, any generation of an RREP
by an intermediate node (as in section 8.4) for delivery to the by an intermediate node (as in section 8.6) for delivery to the
source node, should be accompanied by some action which notifies the source node, should be accompanied by some action which notifies the
destination about a route back to the source node. The source node destination about a route back to the source node. The source node
selects this mode of operation in the intermediate nodes by setting selects this mode of operation in the intermediate nodes by setting
the `G' flag. See section 8.4.3 for details about actions taken by the `G' flag. See section 8.6.3 for details about actions taken by
the intermediate node in response to a RREQ with the `G' flag set. the intermediate node in response to a RREQ with the `G' flag set.
After broadcasting a RREQ, a node waits for a RREP. If the RREP is After broadcasting a RREQ, a node waits for a RREP. If the RREP is
not received within NET_TRAVERSAL_TIME milliseconds, the node MAY not received within NET_TRAVERSAL_TIME milliseconds, the node MAY try
rebroadcast the RREQ, up to a maximum of RREQ_RETRIES times. Each again to flood the RREQ, up to a maximum of RREQ_RETRIES times. Each
rebroadcast MUST increment the Broadcast ID field. new attempt MUST increment the Flooding ID field.
Data packets waiting for a route (i.e., waiting for a RREP after RREQ Data packets waiting for a route (i.e., waiting for a RREP after RREQ
has been sent) SHOULD be buffered. The buffering SHOULD be FIFO. If has been sent) SHOULD be buffered. The buffering SHOULD be FIFO.
a RREQ has been rebroadcast RREQ_RETRIES times without receiving any If a RREQ has been flooded RREQ_RETRIES times without receiving any
RREP, all data packets destined for the corresponding destination RREP, all data packets destined for the corresponding destination
SHOULD be dropped from the buffer and a Destination Unreachable SHOULD be dropped from the buffer and a Destination Unreachable
message delivered to the application. message delivered to the application.
8.2.1. Controlling Route Request broadcasts 8.4. Controlling Dissemination of Route Request Messages
To prevent unnecessary network-wide broadcasts of RREQs, the To prevent unnecessary network-wide floods of RREQs, the source node
source node SHOULD use an expanding ring search technique as an SHOULD use an expanding ring search technique as an optimization.
optimization. In an expanding ring search, the source node initially In an expanding ring search, the source node initially uses a TTL
uses a TTL = TTL_START in the RREQ packet IP header and sets the = TTL_START in the RREQ packet IP header and sets the timeout for
timeout for receiving a RREP to 2 * TTL * NODE_TRAVERSAL_TIME receiving a RREP to 2 * TTL * NODE_TRAVERSAL_TIME milliseconds. If
milliseconds. Upon timeout, the source rebroadcasts the RREQ with the RREQ times out without a corresponding RREP, the source floods
the TTL incremented by TTL_INCREMENT. This continues until the the RREQ again with the TTL incremented by TTL_INCREMENT. This
TTL set in the RREQ reaches TTL_THRESHOLD, beyond which a TTL = continues until the TTL set in the RREQ reaches TTL_THRESHOLD, beyond
NET_DIAMETER is used for each rebroadcast. Each time, the timeout which a TTL = NET_DIAMETER is used for each flood. Each time, the
for receiving a RREP is calculated as before. Each rebroadcast timeout for receiving a RREP is calculated as before. Each attempt
increments the Broadcast ID field in the RREQ packet. The RREQ increments the Flooding ID field in the RREQ packet. The RREQ can
can be rebroadcast with TTL = NET_DIAMETER up to a maximum of be flooded with TTL = NET_DIAMETER up to a maximum of RREQ_RETRIES
RREQ_RETRIES times. times.
When a RREP is received, the Hop Count used in the RREP packet is When a RREP is received, the Hop Count used in the RREP packet is
remembered as Last Hop Count in the routing table. When a new route stored as the Last Hop Count in the routing table. When a new route
to the same destination is required at a later time (e.g., upon route to the same destination is required at a later time (e.g., upon route
loss), the TTL in the RREQ IP header is initially set to this Last loss), the TTL in the RREQ IP header is initially set to this Last
Hop Count plus TTL_INCREMENT. Thereafter, following each timeout the Hop Count plus TTL_INCREMENT. Thereafter, following each timeout the
TTL is incremented by TTL_INCREMENT until TTL = TTL_THRESHOLD is TTL is incremented by TTL_INCREMENT until TTL = TTL_THRESHOLD is
reached. Beyond this TTL = NET_DIAMETER is used as before. reached. Beyond this TTL = NET_DIAMETER is used as before.
As a further optimization, timeouts MAY be determined dynamically via Timeouts MAY be more accurately determined dynamically via
measurements, instead of using a statically configured value related measurements, instead of using a statically configured value related
to NODE_TRAVERSAL_TIME. To accomplish this, the RREQ may carry the to NODE_TRAVERSAL_TIME. To accomplish this, the RREQ may carry the
timestamp via an extension field as defined in Section 11 to be timestamp via an extension field as defined in Section 11 to be
carried back by the RREP packet (again via an extension field). The carried back by the RREP packet (again via an extension field). The
difference between the current time and this timestamp will determine difference between the current time and this timestamp will determine
the route discovery latency. The timeout may be set to be a small the route discovery latency. The timeout may be set to be a small
factor times the average of the last few route discovery latencies factor times the average of the last few route discovery latencies
for the concerned destination. These latencies may be recorded as for the concerned destination. These latencies may be recorded as
additional fields in the routing table. additional fields in the routing table.
If the optimizations described in this section are used, an expired An expired routing table entry SHOULD NOT be expunged before
routing table entry SHOULD NOT be expunged before DELETE_PERIOD. (current_time + DELETE_PERIOD) (see section 8.13). Otherwise, the
Otherwise, the soft state corresponding to the route (e.g., Last Hop soft state corresponding to the route (e.g., Last Hop Count) will be
Count) will be lost. In such cases, a longer routing table entry lost. Furthermore, a longer routing table entry expunge time MAY be
expunge time may be specified. Any routing table entry waiting for a configured. Any routing table entry waiting for a RREP SHOULD NOT be
RREP should not be expunged before RREP_WAIT_TIME. expunged before (current_time + RREP_WAIT_TIME).
8.3. Forwarding Route Requests
When a node receives a broadcast RREQ, it first checks to determine
whether it has received a RREQ with the same Source IP Address
and Broadcast ID within at least the last BROADCAST_RECORD_TIME
milliseconds. If such a RREQ has been received, the node silently
discards the newly received RREQ. The rest of this subsection
describes actions taken for RREQs that are not discarded.
8.3.1. Processing Route Requests
When a node receives a RREQ, the node checks to determine whether it
has an active route to the destination. If the node does not have
an active route, it rebroadcasts the RREQ from its interface(s) but
using its own IP address in the IP header of the outgoing RREQ. The
Destination Sequence Number in the RREQ is updated to the maximum
of the existing Destination Sequence Number in the RREQ and the
destination sequence number in the routing table (if an entry exists)
of the current node. The TTL or hop limit field in the outgoing IP
header is decreased by one. The Hop Count field in the broadcast
RREQ message is incremented by one, to account for the new hop
through the intermediate node.
If the node, on the other hand, does have an active route for the
destination, it compares the destination sequence number for that
route with the Destination Sequence Number field of the incoming
RREQ. If the existing destination sequence number is smaller than
the Destination Sequence Number field of the RREQ, the node again
rebroadcasts the RREQ just as if it did not have an active route to
the destination.
The node generates a RREP (as discussed further in section 8.4) if
either:
(i) it has an active route to the destination, and the 8.5. Processing and Forwarding Route Requests
node's existing destination sequence number is greater
than or equal to the Destination Sequence Number of the
RREQ, or
(ii) it is itself the destination. When a node receives a flooded RREQ, it first checks to determine
whether it has received a RREQ with the same Source IP Address and
Flooding ID within at least the last FLOOD_RECORD_TIME milliseconds.
If such a RREQ has been received, the node silently discards the
newly received RREQ. The rest of this subsection describes actions
taken for RREQs that are not discarded.
The node always creates or updates a reverse route to the Source IP The node always creates or updates a reverse route to the Source IP
Address in its routing table. If a route to the Source IP Address Address in its routing table. If a route to the Source IP Address
already exists, it is updated only if either already exists, it is updated only if either
(i) the Source Sequence Number in the RREQ is higher than (i) the Source Sequence Number in the RREQ is higher than
the destination sequence number of the Source IP Address the destination sequence number of the Source IP Address
in the route table, or in the route table, or
(ii) the sequence numbers are equal, but the hop count as (ii) the sequence numbers are equal, but the hop count as
specified by the RREQ is now smaller than the existing specified by the RREQ, plus one, is now smaller than the
hop count in the routing table. existing hop count in the routing table.
When a reverse route is created or updated, the following actions are This reverse route would be needed in case the node receives an
carried out: eventual RREP back to the node which originated the RREQ (identified
by the Source IP Address). When the reverse route is created or
updated, the following actions are carried out:
1. the Source Sequence Number from the RREQ is copied to the 1. the Source Sequence Number from the RREQ is copied to the
corresponding destination sequence number; corresponding destination sequence number;
2. the next hop in the routing table becomes the node broadcasting 2. the next hop in the routing table becomes the node transmitting
the RREQ (it is obtained from the source IP address in the IP the RREQ (it is obtained from the source IP address in the IP
header and is often not equal to the Source IP Address field in header and is often not equal to the Source IP Address field in
the RREQ message); the RREQ message);
3. the hop count is copied from the Hop Count in the RREQ message; 3. the hop count is copied from the Hop Count in the RREQ message
and incremented by one;
Under all circumstances whenever a RREQ message is received, the
Lifetime of the reverse route entry for the source IP address is set
to be the maximum of (ExistingLifetime, MinimalLifetime), where
4. the lifetime of the route is the higher of its current lifetime MinimalLifetime = (current time + REV_ROUTE_LIFE -
(for an active route) and current time plus REV_ROUTE_LIFE. HopCount*NODE_TRAVERSAL_TIME).
Even if the route is not updated because the existing route has a After updating the reverse route, the node checks to determine
higher destination sequence number, but if it is scheduled to expire whether it has an active route to the destination. If the node
before REV_ROUTE_LIFE, its lifetime is still updated to be current does not have an active route, and the incoming IP header has TTL
time plus REV_ROUTE_LIFE. larger than 1, it broadcasts the RREQ from all of its configured
interface(s) (see section 8.15). The Destination Sequence Number
in the RREQ is updated to the maximum of the existing Destination
Sequence Number in the RREQ and the destination sequence number in
the routing table (if an entry exists) of the current node. The TTL
or hop limit field in the outgoing IP header is decreased by one.
The Hop Count field in the broadcast RREQ message is incremented by
one, to account for the new hop through the intermediate node.
This reverse route would be needed in case the node receives an If the node, on the other hand, does have an active route for the
eventual RREP back to the node which originated the RREQ (identified destination, it compares the destination sequence number for that
by the Source IP Address). route with the Destination Sequence Number field of the incoming
RREQ. If the existing destination sequence number is smaller than
the Destination Sequence Number field of the RREQ, the node again
retransmits the RREQ just as if it did not have an active route to
the destination.
8.4. Generating Route Replies The node generates a RREP (as discussed further in section 8.6) if
either:
(i) it has an active route to the destination, and the
node's existing destination sequence number is greater
than or equal to the Destination Sequence Number of the
RREQ, or
(ii) it is itself the destination.
When either of these conditions are satisfied, the node does not
rebroadcast the RREQ.
8.6. Generating Route Replies
If a node receives a route request for a destination, and either If a node receives a route request for a destination, and either
has a fresh enough route to satisfy the request or is itself the has a fresh enough route to satisfy the request or is itself the
destination, the node generates a RREP message and unicasts it back destination, the node generates a RREP message. This node copies
to the node indicated by the Source IP Address field of the received the Source and Destination IP Addresses in RREQ message into the
RREQ. The node generating the RREP message copies the Source and corresponding fields in the RREP message which is to be sent back
Destination IP Addresses in RREQ message into the corresponding toward the source of the RREQ. Additional operations are slightly
fields in the RREP message which is to be sent back toward the different, depending on whether the node is itself the requested
source of the RREQ. Additional operations are slightly different, destination, or instead if it is an intermediate node with an
depending on whether the node is itself the requested destination, or admissible route to the destination. These scenarios are described
instead if it is an intermediate node with an admissible route to the below. In either case, the RREP is unicast to the node's next hop en
destination. route to the originating node.
As the RREP is forwarded to the source, the Hop Count field is As the RREP is forwarded to the source, the Hop Count field is
incremented by one at each hop. Thus, when the RREP reaches the incremented by one at each hop. Thus, when the RREP reaches the
source, the Hop Count represents the distance, in hops, of the source, the Hop Count represents the distance, in hops, of the
destination from the source. destination from the source.
8.4.1. Route Reply Generation by the Destination 8.6.1. Route Reply Generation by the Destination
If the generating node is the destination itself, it uses a If the generating node is the destination itself, it MUST update its
destination sequence number at least equal to a sequence number own sequence number to the maximum of its current sequence number and
generated after the last detected change in its neighbor set and at the destination sequence number in the RREQ packet. The destination
least equal to the destination sequence number in the RREQ. If the node places the value zero in the Hop Count field of the RREP.
destination node has not detected any change in its set of neighbors
since it last incremented its destination sequence number, it MAY use
the same destination sequence number. The destination node places
the value zero in the Hop Count field of the RREP.
The destination node copies the value MY_ROUTE_TIMEOUT into The destination node copies the value MY_ROUTE_TIMEOUT (see
the Lifetime field of the RREP. Each node MAY make a separate section 12) into the Lifetime field of the RREP. Each node MAY
determination about its value MY_ROUTE_TIMEOUT. reconfigure its value for MY_ROUTE_TIMEOUT, within mild constraints
(see section 12).
8.4.2. Route Reply Generation by an Intermediate Node 8.6.2. Route Reply Generation by an Intermediate Node
If node generating the RREP is not the destination node, but If node generating the RREP is not the destination node, but
instead is an intermediate hop along the path from the source to the instead is an intermediate hop along the path from the source to the
destination, it copies the last known destination sequence number in destination, it copies the last known destination sequence number in
the Destination Sequence Number field in the RREP message. the Destination Sequence Number field in the RREP message.
The intermediate node places its distance in hops from the
destination (indicated by the hop count in the routing table) plus
one in the Hop Count field in the RREP.
When the intermediate node updates its route table for the source When the intermediate node updates its route table for the source
of the RREQ, it puts the last hop node (from which it received the of the RREQ, it puts the last hop node (from which it received the
RREQ, as indicated by the source IP address field in the IP header) RREQ, as indicated by the source IP address field in the IP header)
into the precursor list for the forward path route entry -- i.e., the into the precursor list for the forward path route entry -- i.e., the
entry for the Destination IP Address. Furthermore, the intermediate entry for the Destination IP Address. Furthermore, the intermediate
node puts the next hop towards the destination in the precursor list node puts the next hop towards the destination in the precursor list
for the reverse route entry -- i.e., the entry for the Source IP for the reverse route entry -- i.e., the entry for the Source IP
Address field of the RREQ message data. Address field of the RREQ message data.
The intermediate node calculates the Lifetime field of the RREP by The intermediate node places its distance in hops from the
subtracting the current time from the expiration time in its route destination (indicated by the hop count in the routing table) in
table entry. the Hop Count field in the RREP. The Lifetime field of the RREP is
calculated by subtracting the current time from the expiration time
in its route table entry.
8.4.3. Generating Gratuitous RREPs 8.6.3. Generating Gratuitous RREPs
When a node receives a RREQ and responds with a RREP, it does not After a node receives a RREQ and responds with a RREP, it discards
forward the RREQ any further. If all incarnations of a single the RREQ. If all incarnations of a single RREQ are replied to by
RREQ are replied to by intermediate nodes, the destination does intermediate nodes, the destination does not receive any copies of
not receive any copies of the RREQ. Hence, it does not learn of a the RREQ. Hence, it does not learn of a route to the source node.
route to the source node. This can be problematic if the source is This would cause the destination to initiate a route discovery flood,
attempting to establish a TCP session. In order that the destination if for example the source is attempting to establish a TCP session.
learn of routes to the source node, the source node SHOULD set the In order that the destination learn of routes to the originating
gratuitous RREP ('G') flag in the RREQ if the session is going to be node, the originating node SHOULD set the ``gratuitous RREP'' ('G')
run over TCP, or if the destination should receive the gratuitous flag in the RREQ if the session is going to be run over TCP, or if
RREP for any other reason. Intermediate nodes receiving a RREQ the destination should receive the gratuitous RREP for any other
with the 'G' flag set and responding with a RREP SHOULD unicast a reason. If an intermediate node returns a RREP in response to a RREQ
gratuitous RREP to the destination node. with the 'G' flag set, it MUST also unicast a gratuitous RREP to the
destination node.
The RREP that is sent to the source of the RREQ is the same as The RREP that is sent to the source of the RREQ is the same as
before. The gratuitous RREP that is to be sent to the desired before. The gratuitous RREP that is to be sent to the desired
destination contains the following values in the RREP message fields: destination contains the following values in the RREP message fields:
Hop Count The Hop Count as received in the RREQ Hop Count The Hop Count as received in the RREQ
Destination IP Address Destination IP Address
The IP address of the node that generated the RREQ The IP address of the node that originated the RREQ
Destination Sequence Number Destination Sequence Number
The Source Sequence Number from the RREQ The Source Sequence Number from the RREQ
Source IP Address Source IP Address
The IP address of the destination node The IP address of the destination node in the RREQ
Lifetime The remaining lifetime of the route towards the Lifetime The remaining lifetime of the route towards the
destination node, as known by the intermediate node. destination node, as known by the intermediate node.
The gratuitous RREP is then sent to the next hop along the path to The gratuitous RREP is then sent to the next hop along the path to
the destination node. the destination node.
8.5. Forwarding Route Replies 8.7. Forwarding Route Replies
When a node receives a RREP message, it first compares the When a node receives a RREP message, it first increments the hop
Destination Sequence Number in the message with its own copy of count value in the RREP by one, to account for the new hop through
destination sequence number for the Destination IP Address in the the intermediate node. It then compares the Destination Sequence
RREP message. The forward route for this destination is created or Number in the message with its own copy of destination sequence
updated only if (i) the Destination Sequence Number in the RREP is number for the Destination IP Address in the RREP message. The
greater than the node's copy of the destination sequence number, or forward route for this destination is created or updated only if
(ii) the sequence numbers are the same, but the route is no longer (i) the Destination Sequence Number in the RREP is greater than the
active or the Hop Count in RREP is smaller than the hop count in node's copy of the destination sequence number, or (ii) the sequence
route table entry. If a new route is created or the old route is numbers are the same, but the route is no longer active or the
updated, the next hop is the node from which the RREP is received, incremented Hop Count in RREP is smaller than the hop count in route
which is indicated by the source IP address field in the IP header; table entry. If a new route is created or the old route is updated,
the hop count is the Hop Count in the RREP message plus one; the the next hop is the node from which the RREP is received, which is
expiry time is the current time plus the Lifetime in the RREP indicated by the source IP address field in the IP header; the hop
message; the destination sequence number is the Destination Sequence count is the Hop Count in the RREP message plus one; the expiry
Number in the RREP message. time is the current time plus the Lifetime in the RREP message; the
destination sequence number is the Destination Sequence Number in the
RREP message.
The current node can now begin using this route to send data packets The current node can now begin using this route to forward data
to the destination. packets to the destination.
If the current node is not the source node as indicated by the Source If the current node is not the source node as indicated by the Source
IP Address in the RREP message AND a forward route has been created IP Address in the RREP message AND a forward route has been created
or updated as described before, the node consults its route table or updated as described before, the node consults its route table
entry for the source node to determine the next hop for the RREP entry for the source node to determine the next hop for the RREP
packet, and then forwards the RREP towards the source with its Hop packet, and then forwards the RREP towards the source with its Hop
Count incremented by one. Count incremented by one.
When any node generates or forwards a RREP, the precursor list for When any node generates or forwards a RREP, the precursor list for
the corresponding destination node is updated by adding to it the the corresponding destination node is updated by adding to it the
next hop node to which the RREP is forwarded. Also, at each node the next hop node to which the RREP is forwarded. Also, at each node the
(reverse) route used to forward a RREP has its lifetime changed to (reverse) route used to forward a RREP has its lifetime changed to
current time plus ACTIVE_ROUTE_TIMEOUT. current time plus ACTIVE_ROUTE_TIMEOUT.
If a node forwards a RREP over a link that is likely to have errors If a node forwards a RREP over a link that is likely to have errors
or be unidirectional, the node MAY set the `A' flag to require that or be unidirectional, the node SHOULD set the `A' flag to require
the recipient of the RREP acknowledge receipt of the RREP by sending that the recipient of the RREP acknowledge receipt of the RREP by
a RREP-ACK message back. sending a RREP-ACK message back (see section 8.8).
8.6. Operation over Unidirectional Links 8.8. Operation over Unidirectional Links
When unidirectional links are present, it is possible that a RREP It is possible that a RREP transmission may fail if a RREQ
transmission may fail. Such failure can be detected via the absence transmission may occur over a unidirectional link. If no other RREP
of a link-layer or network-layer acknowledgment (e.g., RREP-ACK). If generated from the same RREQ flood reaches the source, the source
no other RREP generated from the same route request broadcast reaches will attempt to flood the RREQ after a timeout (see section 8.3).
the source, the source will redo the broadcast after a timeout (see However, the same scenario might well be repeated, and no route would
section 8.2). However, the same scenario will repeat, and no route be discovered even after repeated retries. Unless corrective action
will be discovered even after repeated retries. This is possible is taken, this can happen even when bidirectional routes between
even when bidirectional routes between source and destination do source and destination do exist. In AODV, any node acts on only
exist. This happens because a RREQ transmission may occur over a the first RREQ with the same Flooding ID and ignores any subsequent
unidirectional link. Link layers using broadcast transmissions for RREQs. Suppose, for example, that the first RREQ arrives along a
RREQ will not be able to detect the presence of such unidirectional path that has one or more unidirectional link(s). A subsequent RREQ
links. Also, in AODV any node acts on only the first RREQ with may arrive via a bidirectional path (assuming such paths exist), but
the same broadcast ID and ignores any subsequent RREQs. It is it will be ignored.
possible that the first RREQ arrives along a path that has one or
more unidirectional link(s). However, a subsequent RREQ may arrive
via a bidirectional path (assuming such paths exist), but it will be
ignored.
To prevent this problem, a node that fails to transmit a RREP To prevent this problem, when a node detects that its transmission of
remembers the next-hop of the failed RREP in a ``blacklist'' set. A an RREP message has failed, it remembers the next-hop of the failed
node ignores all RREQs received from any node in its blacklist set. RREP in a ``blacklist'' set. A node ignores all RREQs received from
Nodes are removed from the blacklist set after a BLACKLIST_TIMEOUT any node in its blacklist set. Nodes are removed from the blacklist
period. This period should be set to the upper bound of the time it set after a BLACKLIST_TIMEOUT period. This period should be set to
takes to perform the allowed number of route request retry attempts the upper bound of the time it takes to perform the allowed number of
as described in section 8.2. route request retry attempts as described in section 8.3.
8.7. Hello Messages Link layers using broadcast transmissions for RREQ will not be able
to detect the presence of such unidirectional links. Such failure
can be detected via the absence of a link-layer or network-layer
acknowledgment (e.g., RREP-ACK).
8.9. Hello Messages
A node MAY offer connectivity information by broadcasting local A node MAY offer connectivity information by broadcasting local
Hello messages as follows. Every HELLO_INTERVAL milliseconds, the Hello messages as follows. Every HELLO_INTERVAL milliseconds, the
node checks whether it has sent a broadcast (e.g., a RREQ or an node checks whether it has sent a broadcast (e.g., a RREQ or an
appropriate layer 2 message) within the last HELLO_INTERVAL. If it appropriate layer 2 message) within the last HELLO_INTERVAL. If
has not, it MAY generate a broadcast RREP with TTL = 1, called a it has not, it MAY broadcast a RREP with TTL = 1, called a Hello
Hello message, with the message fields set as follows: message, with the RREP message fields set as follows:
Destination IP Address Destination IP Address
The node's IP address. The node's IP address.
Destination Sequence Number Destination Sequence Number
The node's latest sequence number. The node's latest sequence number.
Hop Count 0 Hop Count 0
Lifetime ALLOWED_HELLO_LOSS * HELLO_INTERVAL Lifetime ALLOWED_HELLO_LOSS * HELLO_INTERVAL
skipping to change at page 15, line 4 skipping to change at page 17, line 33
Destination IP Address Destination IP Address
The node's IP address. The node's IP address.
Destination Sequence Number Destination Sequence Number
The node's latest sequence number. The node's latest sequence number.
Hop Count 0 Hop Count 0
Lifetime ALLOWED_HELLO_LOSS * HELLO_INTERVAL Lifetime ALLOWED_HELLO_LOSS * HELLO_INTERVAL
A node MAY determine connectivity by listening for packets from A node MAY determine connectivity by listening for packets from
its set of neighbors. If it receives no packets for more than its set of neighbors. If it receives no packets for more than
ALLOWED_HELLO_LOSS * HELLO_INTERVAL milliseconds, the node SHOULD ALLOWED_HELLO_LOSS * HELLO_INTERVAL milliseconds, the node SHOULD
assume that the link to this neighbor is currently broken. When this assume that the link to this neighbor is currently broken. When this
happens, the node SHOULD proceed as in Section 8.9. happens, the node SHOULD proceed as in Section 8.11.
8.8. Maintaining Local Connectivity Whenever a node receives a HELLO packet from a neighbor, the node
SHOULD make sure that it has an active route to the neighbor,
and create one if necessary. If a route already exists, then the
Lifetime for the route should be increased if necessary to be at
least ACTIVE_ROUTE_TIMEOUT. In any case, the route to the neighbor
should be updated to contain the latest Destination Sequence Number
from the HELLO message. Routes which are newly created from the
reception of HELLO messages have empty precursor lists, and so
typically do not trigger RERR messages when the neighbor moves away
and the neighbor route expires.
Each forwarding node SHOULD keep track of its active next hops (i.e., 8.10. Maintaining Local Connectivity
which next hops have been used to forward packets towards some
destination within the last ACTIVE_ROUTE_TIMEOUT milliseconds). This Each forwarding node SHOULD keep track of its continued connectivity
is done by updating the Lifetime field of a routing table entry used to its active next hops (i.e. which next hops have forwarded,
to forward data packets to current time plus ACTIVE_ROUTE_TIMEOUT or used to forward packets, within the last ACTIVE_ROUTE_TIMEOUT
milliseconds. For purposes of efficiency, each node may try to learn milliseconds, as well as neighbors that have transmitted HELLO
which of these active next hops are really in the neighborhood at the messages within the last (ALLOWED_HELLO_LOSS * HELLO_INTERVAL).
current time using one or more of the available link or network layer A node can maintain accurate information about its continued
mechanisms, as described below. 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, such as those provided by - Any suitable link layer notification, such as those provided by
IEEE 802.11, can be used to determine connectivity, each time IEEE 802.11, can be used to determine connectivity, each time
a packet is transmitted to an active next hop. For example, a packet is transmitted to an active next hop. For example,
absence of a link layer ACK or failure to get a CTS after sending absence of a link layer ACK or failure to get a CTS after sending
RTS, even after the maximum number of retransmission attempts, RTS, even after the maximum number of retransmission attempts,
will indicate loss of the link to this active next hop. indicates loss of the link to this active next hop.
- Passive acknowledgment can be used when the next hop is expected - If possible, passive acknowledgment SHOULD be used when the
to forward the packet, by listening to the channel for a next hop is expected to forward the packet, by listening to the
transmission attempt made by the next hop. If transmission is channel for a transmission attempt made by the next hop. If
not detected within NEXT_HOP_WAIT milliseconds or the next hop is transmission is not detected within NEXT_HOP_WAIT milliseconds or
not a forwarding node (and thus is never supposed to transmit the the next hop is the destination (and thus is never supposed to
packet) one of the following methods should be used to determine transmit the packet) one of the following methods should be used
connectivity. to determine connectivity.
* Receiving an ICMP ACK message from the next hop. The ICMP * Receiving any packet (including a HELLO message) from the
ACK message SHOULD be sent to a forwarding node by a next hop next hop.
which is also the destination as in the in the IP header of
the packet. This should be done only when this destination
has not sent any packets to the concerned forwarding node
within the last HELLO_INTERVAL milliseconds.
* A RREQ unicast to the next hop, asking for a route to the * A RREQ unicast to the next hop, asking for a route to the
next hop. next hop.
* An ICMP Echo Request message unicast to the next hop. * An ICMP Echo Request message unicast to the next hop.
If a link to the next hop cannot be detected by any of these methods, If a link to the next hop cannot be detected by any of these methods,
the forwarding node SHOULD assume that the link is broken, and take the forwarding node SHOULD assume that the link is broken, and take
corrective action by following the methods specified in Section 8.9. corrective action by following the methods specified in Section 8.11.
8.9. Route Error Messages 8.11. Route Error Messages
A node initiates a RERR message in three situations: A node initiates a RERR message in three situations:
(i) if it detects a link break for the next hop of an active (i) if it detects a link break for the next hop of an active
route in its routing table, or route in its routing table (also see section 8.1), or
(ii) if it gets a data packet destined to a node for which it (ii) if it gets a data packet destined to a node for which it
does not have an active route, or does not have an active route, and has already made an
attempt at local repair, or
(iii) if it receives a RERR from a neighbor for one or more (iii) if it receives a RERR from a neighbor for one or more
active routes. active routes.
For cases (i) and (ii), the destination sequence numbers in the
routing table for the unreachable destination(s) are incremented by
one. Then RERR is broadcast with the unreachable destination(s) and
their incremented destination sequence number(s) included in the
packet. For case (i), the unreachable destinations are the broken
next hop, and any additional destinations which are now unreachable
due to the loss of this next hop link. These additional destinations
are those that also use the lost link as next hop in the routing
table. For case (ii), there is only one unreachable destination,
which is the destination of the data packet that cannot be delivered.
The DestCount field of the RERR packet indicates the number of
unreachable destinations included in the packet.
For cases (i) and (ii), for each unreachable destination the node For cases (i) and (ii), for each unreachable destination the node
copies the value in the Hop Count route table field into the Last copies the value in the Hop Count route table field into the Last
Hop Count field, and marks the Hop Count for this destination as Hop Count field, and marks the Hop Count for this destination as
infinity, and thus invalidates the route. infinity, and thus invalidates the route.
For case (iii) when a node receives a RERR message, for each For case (i), the node first makes a list of destinations which use
unreachable destination included in the packet, the node determines the next hop which has been detected to be broken. For case (iii),
whether the source node (as indicated by the source IP address in the the node instead makes the list of affected destinations which use
IP header) forwarding the RERR packet is its own next hop used to the transmitter of the received RERR as the next hop, from among
reach this destination. If so, the node takes the following actions: those destinations listed in the received RERR message. Then, in
either case (i) or (iii), the the node uses the constructed list of
affected destinations to disseminate information about the broken
route to the appropriate other nodes; if there are no affected
destinations, the node does not disseminate the RERR message
(a) updates the corresponding destination sequence number For each one of the affected destinations, the node takes the
with the Destination Sequence Number in the packet, and following actions:
(b) marks the Hop Count for this destination as infinity, (a) updates the corresponding destination sequence number(s)
and thus invalidates the route. The old value of Hop with the Destination Sequence Number(s) in the packet
Count is copied into the Last Hop Count field.
(c) checks the precursor list for this destination for (b) copies the old value of Hop Count into the Last Hop
emptiness. If one or more of the precursor lists for Count field.
the unreachable destinations are non-empty, the node
creates a RERR message, including as unreachable each
destination with a non-empty precursor list. It also
includes their destination sequence numbers, and then
broadcasts this RERR message.
When a node broadcasts a RERR message, it always deletes the (c) marks the Hop Count for this destination as infinity,
precursor list of each unreachable destination included in the and thus invalidates the route.
message.
When a node invalidates a route to a neighboring node, it must also (d) checks the precursor list for each destination for
delete that neighbor from any precursor lists for routes to other emptiness. If the list is empty, don't follow steps (e)
nodes. This prevents precursor lists from containing stale entries -- (g)
of neighbors with which the node is no longer able to communicate.
The node should inspect the precursor list of each destination entry
in its routing table, and delete the lost neighbor from any list in
which it appears.
8.9.1. Local Repair (e) Otherwise, the node creates or updates the data in a
RERR message to be transmitted. Each destination with
a non-empty precursor list is included as unreachable
along with its destination sequence numbers
(f) transmit the RERR message. If there is only one
previous hop that needs to receive the RERR, the node
SHOULD unicast the RERR to the previous hop. Otherwise,
the node SHOULD transmit the RERR message to the IP
broadcast address.
(g) delete the precursor list of each unreachable
destination
The RERR is locally broadcast (Destination IP == 255.255.255.255,
TTL == 1) with the unreachable destination(s) and the destination
sequence number for each one included in the packet. For case
(i), the unreachable destinations are the broken next hop, and any
additional destinations which are now unreachable due to the loss of
this next hop link. For case (ii), there is only one unreachable
destination, which is the destination of the data packet that cannot
be delivered. The DestCount field of the RERR packet indicates the
number of unreachable destinations included in the packet.
When a node invalidates a route to a neighboring node, it MUST
also delete that neighbor from any precursor lists for routes to
other nodes. This prevents precursor lists from containing stale
entries of neighbors with which the node is no longer able to
communicate. The node does this by inspecting the precursor list of
each destination entry in its routing table, and deleting the lost
neighbor from any list in which it appears.
8.12. Local Repair
When a link break in an active route occurs, the node upstream of When a link break in an active route occurs, the node upstream of
that break MAY choose to repair the link locally if the destination that break MAY choose to repair the link locally if the destination
is no farther than MAX_REPAIR_TTL hops away. To repair the link is no farther than MAX_REPAIR_TTL hops away. To repair the link
break itself, it increments the sequence number for the destination break itself, it increments the sequence number for the destination
and then broadcasts a RREQ for that destination. The TTL of the RREQ and then floods a RREQ for that destination. The TTL of the
should initially be set to the following value: broadcast RREQ should initially be set to the following value:
max(MIN_REPAIR_TTL, 0.5 distance to source) + LOCAL_ADD_TTL . max(MIN_REPAIR_TTL, 0.5 distance to source) + LOCAL_ADD_TTL .
Thus, local repair attempts should never be visible to the source Thus, local repair attempts should never be visible to the source
node, and will always have minimum TTL equal to MIN_REPAIR_TTL node, and will always have minimum TTL equal to MIN_REPAIR_TTL
+ LOCAL_ADD_TTL. The node initiating the repair then waits the + LOCAL_ADD_TTL. The node initiating the repair then waits the
discovery period to receive RREPs in response to the RREQ. If, at discovery period to receive RREPs in response to the RREQ. If, at
the end of the discovery period, it has not received a RREP for that the end of the discovery period, it has not received a RREP for that
destination, it proceeds as described in Section 8.9 by creating a destination, it proceeds as described in Section 8.11 by transmitting
RERR message for that destination. a RERR message for that destination.
On the other hand, if the nodes does receive one or more RREPs during On the other hand, if the nodes does receive one or more RREPs
the discovery period, the node proceeds as described in Section 8.5, during the discovery period, the node proceeds as described in
creating a route table entry for that destination. It then compares Section 8.7, updating its route table entry for that destination. It
the hop count of the new route with the value in the last hop count then compares the hop count of the new route with the value in the
route table entry for that destination. If the hop count of the last hop count route table entry for that destination. If the hop
newly determined route to the destination is greater than the hop count of the newly determined route to the destination is greater
count of the previously known route, as recorded in the last hop than the hop count of the previously known route, as recorded in the
count field, the node MAY create a RERR message for the destination last hop count field, the node SHOULD create a RERR message for the
and send this message to the source node. The node sets the 'N' flag destination, with the 'N' bit set.
of the RERR, and then broadcasts this message if it has one or more
precursor nodes for this route table entry.
A node which receives a RERR message with the 'N' flag set MUST A node which receives a RERR message with the 'N' flag set MUST
NOT delete the route to that destination. The only action taken NOT delete the route to that destination. The only action taken
should be the retransmission of the message, if the RERR arrived should be the retransmission of the message, if the RERR arrived
from the next hop along that route, and if there are one or more from the next hop along that route, and if there are one or more
precursor nodes for that route to the destination. When the source precursor nodes for that route to the destination. When the source
node receives a RERR message with the 'N' flag set, if this message node receives a RERR message with the 'N' flag set, if this message
came from its next hop along its route to the destination then the came from its next hop along its route to the destination then the
source node MAY choose to reinitiate route discovery, as described in source node MAY choose to reinitiate route discovery, as described in
Section 8.2. Section 8.3.
Local repair of link breaks in active routes sometimes results in Local repair of link breaks in active routes sometimes results in
increased path lengths to those destinations. Repairing the link increased path lengths to those destinations. Repairing the link
locally is likely to increase the number of data packets which are locally is likely to increase the number of data packets which are
able to be delivered to the destinations, since data packets will not able to be delivered to the destinations, since data packets will not
be dropped as the RERR travels to the source node. Sending a RERR be dropped as the RERR travels to the source node. Sending a RERR to
to the source node after locally repairing the link break allows the the source node after locally repairing the link break may allow the
source to find a fresh route to the destination which is more optimal source to find a fresh route to the destination which is better based
based on current node positions. However, it does not require the on current node positions. However, it does not require the source
source node to rebuild the route, as the source may be done, or node to rebuild the route, as the source may be done, or nearly done,
nearly done, with the data session. with the data session.
When a link breaks along an active route, there are often multiple When a link breaks along an active route, there are often multiple
destinations which become unreachable. The node which is upstream destinations which become unreachable. The node which is upstream
of the broken link tries an immediate local repair for only the one of the broken link tries an immediate local repair for only the one
destination towards which the packet was traveling. Other routes destination towards which the packet was traveling. Other routes
using the same link MUST be marked as broken, but the node handling using the same link MUST be marked as broken, but the node handling
the local repair MAY flag each such newly broken route as locally the local repair MAY flag each such newly broken route as locally
repairable; this local repair flag in the route table MUST be reset repairable; this local repair flag in the route table MUST be reset
when the route times out (i.e., after the route has been not been when the route times out (i.e., after the route has been not been
active for ACTIVE_ROUTE_TIMEOUT). Before the timeout occurs, these active for ACTIVE_ROUTE_TIMEOUT). Before the timeout occurs, these
other routes will be repaired as needed when packets arrive for the other routes will be repaired as needed when packets arrive for the
other destinations. Alternatively, depending upon local congestion, other destinations. Alternatively, depending upon local congestion,
the node MAY begin the process of establishing local repairs for the the node MAY begin the process of establishing local repairs for the
other routes, without waiting for new packets to arrive. other routes, without waiting for new packets to arrive.
8.10. Route Expiry and Deletion 8.13. Route Expiry and Deletion
If the Lifetime of an active routing entry expires, the following If the Lifetime of an active routing entry expires, the following
actions are taken. actions are taken.
1. The entry is invalidated by copying the Hop Count to the Last Hop 1. The entry is invalidated by copying the Hop Count to the Last Hop
Count field and then making the Hop Count infinity. Count field and then making the Hop Count infinity.
2. The destination sequence number of this routing entry is 2. The destination sequence number of this routing entry is
incremented by one. incremented by one.
skipping to change at page 19, line 10 skipping to change at page 22, line 14
Note that the Lifetime field plays dual role -- for an active route Note that the Lifetime field plays dual role -- for an active route
it is the expiry time, and for an invalid route it is the deletion it is the expiry time, and for an invalid route it is the deletion
time. time.
These actions are also taken whenever a route entry is invalidated These actions are also taken whenever a route entry is invalidated
for any reason, for example, for link breakage or receiving a RERR. for any reason, for example, for link breakage or receiving a RERR.
If a data packet is received for an invalid route, the Lifetime If a data packet is received for an invalid route, the Lifetime
field is always updated to current time plus DELETE_PERIOD. The field is always updated to current time plus DELETE_PERIOD. The
determination of DELETE_PERIOD is discussed in Section 12 determination of DELETE_PERIOD is discussed in Section 12.
8.11. Actions After Reboot 8.14. Actions After Reboot
A node participating in the ad hoc network must take certain A node participating in the ad hoc network must take certain actions
actions after reboot as it will have lost its prior sequence number after reboot as it might lose all sequence number records for all
and as well as its last known sequence numbers for various other destinations, including its own sequence number. However, there may
destinations. However, there may be neighboring nodes which are be neighboring nodes which are using this node as an active next
using this node as an active next hop. This can potentially create hop. This can potentially create routing loops. To prevent this
routing loops. To prevent this possibility, each node on reboot possibility, each node on reboot waits for DELETE_PERIOD. During this
waits for DELETE_PERIOD. In this time, it does not respond to time, the node does not transmit any RREP messages. If the node
any routing packets. However, if it receives a data packet, it receives a RREQ, RREP, or RERR control packets, it SHOULD create
broadcasts a RERR as described in subsection 8.9 and resets the route entries as appropriate given the sequence number information
waiting timer to expire after current time plus DELETE_PERIOD. in the control packets. If the node receives a data packet for
some other destination, it MUST broadcast a RERR as described in
subsection 8.11 and reset the waiting timer to expire after current
time plus DELETE_PERIOD.
It can be shown that by the time the rebooted node comes out of It can be shown [1] that by the time the rebooted node comes out of
the waiting phase and becomes an active router again, none of its the waiting phase and becomes an active router again, none of its
neighbors will be using it as an active next hop any more. Its own neighbors will be using it as an active next hop any more. Its own
sequence number gets updated once it receives a RREQ from any other sequence number gets updated once it receives a RREQ from any other
node, as the RREQ always carries the maximum destination sequence node, as the RREQ always carries the maximum destination sequence
number seen en route. number seen en route.
8.12. Interfaces 8.15. Interfaces
Because AODV should operate smoothly over wired, as well as wireless, Because AODV should operate smoothly over wired, as well as wireless,
networks, and because it is likely that AODV will also be used with networks, and because it is likely that AODV will also be used with
multi-homed radios, the interface over which packets arrive must multi-homed radios, the interface over which packets arrive must
be known to AODV whenever a packet is received. This includes the be known to AODV whenever a packet is received. This includes the
reception of RREQ, RREP, and RERR messages. Whenever a packet is reception of RREQ, RREP, and RERR messages. Whenever a packet is
received from a new neighbor, the interface on which that packet was received from a new neighbor, the interface on which that packet was
received is recorded into the route table entry for that neighbor, received is recorded into the route table entry for that neighbor,
along with all the other appropriate routing information. Similarly, along with all the other appropriate routing information. Similarly,
whenever a route to a new destination is learned, the interface whenever a route to a new destination is learned, the interface
through which the destination can be reached is also recorded into through which the destination can be reached is also recorded into
the destination's route table entry. the destination's route table entry.
When multiple interfaces are available, a node receiving and When multiple interfaces are available, a node retransmitting a RREQ
rebroadcasting a RREQ message rebroadcasts that message on all message rebroadcasts that message on all interfaces which have been
interfaces. When a node needs to transmit a RERR, it should only configured for operation in the ad-hoc network. When a node needs to
broadcast it on those interfaces which have precursor nodes for that transmit a RERR, it should only transmit it on those interfaces which
route. have precursor nodes for that route.
9. AODV and Aggregated Networks 9. AODV and Aggregated Networks
AODV has been designed for use by mobile nodes with IP addresses AODV has been designed for use by mobile nodes with IP addresses
that are not necessarily related to each other, to create an ad hoc that are not necessarily related to each other, to create an ad hoc
network. However, in some cases a collection of mobile nodes MAY network. However, in some cases a collection of mobile nodes MAY
operate in a fixed relationship to each other and share a common operate in a fixed relationship to each other and share a common
subnet prefix, moving together within an area where an ad hoc network subnet prefix, moving together within an area where an ad hoc network
has formed. Call such a collection of nodes a ``subnet''. In this has formed. Call such a collection of nodes a ``subnet''. In this
case, it is possible for a single node within the subnet to advertise case, it is possible for a single node within the subnet to advertise
skipping to change at page 21, line 43 skipping to change at page 24, line 48
Length 4 Length 4
Hello Interval Hello Interval
The number of milliseconds between successive The number of milliseconds between successive
transmissions of a Hello message. transmissions of a Hello message.
The Hello Interval extension MAY be appended to a RREP message with The Hello Interval extension MAY be appended to a RREP message with
TTL == 1, to be used by a neighboring receiver in determine how long TTL == 1, to be used by a neighboring receiver in determine how long
to wait for subsequent such RREP messages (i.e., Hello messages; see to wait for subsequent such RREP messages (i.e., Hello messages; see
section 8.7). section 8.9).
12. Configuration Parameters 12. Configuration Parameters
This section gives default values for some important values This section gives default values for some important values
associated with AODV protocol operations. A particular mobile associated with AODV protocol operations. A particular mobile
node may wish to change certain of the parameters, in particular node may wish to change certain of the parameters, in particular
the NET_DIAMETER, NODE_TRAVERSAL_TIME, MY_ROUTE_TIMEOUT, the NET_DIAMETER, NODE_TRAVERSAL_TIME, MY_ROUTE_TIMEOUT,
ALLOWED_HELLO_LOSS, RREQ_RETRIES, and possibly the HELLO_INTERVAL. In ALLOWED_HELLO_LOSS, RREQ_RETRIES, and possibly the HELLO_INTERVAL. In
the latter case, the node should advertise the HELLO_INTERVAL in its the latter case, the node should advertise the HELLO_INTERVAL in its
Hello messages, by appending a Hello Interval Extension to the RREP Hello messages, by appending a Hello Interval Extension to the RREP
message. Choice of these parameters may affect the performance of message. Choice of these parameters may affect the performance of
the protocol. the protocol. The configured value for MY_ROUTE_TIMEOUT MUST be at
least 2 * REV_ROUTE_LIFE.
Parameter Name Value Parameter Name Value
---------------------- ----- ---------------------- -----
ACTIVE_ROUTE_TIMEOUT 3,000 Milliseconds ACTIVE_ROUTE_TIMEOUT 3,000 Milliseconds
ALLOWED_HELLO_LOSS 2 ALLOWED_HELLO_LOSS 2
BLACKLIST_TIMEOUT RREQ_RETRIES * NET_TRAVERSAL_TIME BLACKLIST_TIMEOUT RREQ_RETRIES * NET_TRAVERSAL_TIME
BROADCAST_RECORD_TIME 2 * NET_TRAVERSAL_TIME FLOOD_RECORD_TIME 2 * NET_TRAVERSAL_TIME
DELETE_PERIOD see note below DELETE_PERIOD see note below
HELLO_INTERVAL 1,000 Milliseconds HELLO_INTERVAL 1,000 Milliseconds
LOCAL_ADD_TTL 2 LOCAL_ADD_TTL 2
MAX_REPAIR_TTL 0.3 * NET_DIAMETER MAX_REPAIR_TTL 0.3 * NET_DIAMETER
MIN_REPAIR_TTL see note below MIN_REPAIR_TTL see note below
MY_ROUTE_TIMEOUT 2 * ACTIVE_ROUTE_TIMEOUT MY_ROUTE_TIMEOUT 2 * ACTIVE_ROUTE_TIMEOUT
NET_DIAMETER 35 NET_DIAMETER 35
NEXT_HOP_WAIT NODE_TRAVERSAL_TIME + 10 NEXT_HOP_WAIT NODE_TRAVERSAL_TIME + 10
NODE_TRAVERSAL_TIME 40 NODE_TRAVERSAL_TIME 40
REV_ROUTE_LIFE NET_TRAVERSAL_TIME REV_ROUTE_LIFE NET_TRAVERSAL_TIME
skipping to change at page 23, line 17 skipping to change at page 26, line 23
DELETE_PERIOD = K * max (ACTIVE_ROUTE_TIMEOUT, DELETE_PERIOD = K * max (ACTIVE_ROUTE_TIMEOUT,
ALLOWED_HELLO_LOSS * HELLO_INTERVAL) (K = 5 is recommended). ALLOWED_HELLO_LOSS * HELLO_INTERVAL) (K = 5 is recommended).
NET_DIAMETER measures the maximum possible number of hops between NET_DIAMETER measures the maximum possible number of hops between
two nodes in the network. NODE_TRAVERSAL_TIME is a conservative two nodes in the network. NODE_TRAVERSAL_TIME is a conservative
estimate of the average one hop traversal time for packets and should estimate of the average one hop traversal time for packets and should
include queueing delays, interrupt processing times and transfer include queueing delays, interrupt processing times and transfer
times. ACTIVE_ROUTE_TIMEOUT SHOULD be set to a longer value (at times. ACTIVE_ROUTE_TIMEOUT SHOULD be set to a longer value (at
least 10,000 milliseconds) if link-layer indications are used to least 10,000 milliseconds) if link-layer indications are used to
detect link breakages such as in IEEE 802.11 [2] standard. TTL_START detect link breakages such as in IEEE 802.11 [4] standard. TTL_START
should be set to at least 2 if Hello messages are used for local should be set to at least 2 if Hello messages are used for local
connectivity information. Performance of the AODV protocol is connectivity information. Performance of the AODV protocol is
sensitive to the chosen values of these constants, which often depend sensitive to the chosen values of these constants, which often depend
on the characteristics of the underlying link layer protocol, radio on the characteristics of the underlying link layer protocol, radio
technologies etc. BLACKLIST_TIMEOUT should be suitably increased technologies etc. BLACKLIST_TIMEOUT should be suitably increased
if expanding ring search is used. In such cases, it should be if expanding ring search is used. In such cases, it should be
(TTL_THRESHOLD - TTL_START)/TTL_INCREMENT + 1 + RREQ_RETRIES. This is (TTL_THRESHOLD - TTL_START)/TTL_INCREMENT + 1 + RREQ_RETRIES. This is
to account for possible additional route discovery attempts. to account for possible additional route discovery attempts.
13. Security Considerations 13. Security Considerations
Currently, AODV does not specify any special security measures. Currently, AODV does not specify any special security measures.
Route protocols, however, are prime targets for impersonation Route protocols, however, are prime targets for impersonation
attacks, and must be protected by use of authentication techniques attacks. If there is danger of such attacks, AODV control messages
must be protected by use of authentication techniques, such as those
involving generation of unforgeable and cryptographically strong involving generation of unforgeable and cryptographically strong
message digests or digital signatures. It is expected that, in message digests or digital signatures. In particular, RREP messages
environments where security is an issue, that IPSec authentication SHOULD be authenticated to avoid creation of spurious routes to a
headers will be deployed along with the necessary key management to desired destination. Otherwise, an attacker could masquerade as the
distribute keys to the members of the ad hoc network using AODV. desired 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
valid routes between nodes which are communication partners.
Since AODV does not make any assumption about the nature of the
address assignment to the mobile nodes except that they are presumed
to have unique IP addresses, no definite statements 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
pre-established security associations, they should be able to use the
same authentication mechanisms based on their IP addresses as they
would have used otherwise.
14. Acknowledgments 14. Acknowledgments
We acknowledge with gratitude the work done at University of We acknowledge with gratitude the work done at University of
Pennsylvania within Carl Gunter's group, as well as at Stanford and Pennsylvania within Carl Gunter's group, as well as at Stanford and
CMU, to determine some conditions (especially involving reboots and CMU, to determine some conditions (especially involving reboots and
lost RERRs) under which previous versions of AODV could suffer from lost RERRs) under which previous versions of AODV could suffer from
routing loops. Contributors to those efforts include Karthikeyan routing loops. Contributors to those efforts include Karthikeyan
Bhargavan, Joshua Broch, Dave Maltz, Madanlal Musuvathi, and Bhargavan, Joshua Broch, Dave Maltz, Madanlal Musuvathi, and
Davor Obradovic. The idea of a DELETE_PERIOD, for which expired Davor Obradovic. The idea of a DELETE_PERIOD, for which expired
routes (and, in particular, the sequence numbers) to a particular routes (and, in particular, the sequence numbers) to a particular
destination must be maintained, was also suggested by them. destination must be maintained, was also suggested by them.
We also acknowledge the comments and improvements suggested by SJ Lee We also acknowledge the comments and improvements suggested by SJ
(especially regarding local repair) and Mahesh Marina. Lee (especially regarding local repair), Mahesh Marina, Yves Prelot,
Manel Guerrero Zapata, and Philippe Jacquet.
References References
[1] S. Bradner. Key words for use in RFCs to Indicate Requirement [1] 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.
[2] S. Bradner. Key words for use in RFCs to Indicate Requirement
Levels. Request for Comments (Best Current Practice) 2119, Levels. Request for Comments (Best Current Practice) 2119,
Internet Engineering Task Force, March 1997. Internet Engineering Task Force, March 1997.
[2] IEEE 802.11 Committee, AlphaGraphics #35, 10201 N.35th Avenue, [3] J. Manner et al. Mobility Related Terminology (work in
progress). draft-manner-seamoby-terms-02.txt, July 2001.
[4] IEEE 802.11 Committee, AlphaGraphics #35, 10201 N.35th Avenue,
Phoenix AZ 85051. Wireless LAN Medium Access Control MAC and Phoenix AZ 85051. Wireless LAN Medium Access Control MAC and
Physical Layer PHY Specifications, June 1997. IEEE Standard Physical Layer PHY Specifications, June 1997. IEEE Standard
802.11-97. 802.11-97.
[3] Charles E. Perkins. Terminology for Ad-Hoc Networking (work in A. Draft Modifications
progress). draft-ietf-manet-terms-00.txt, November 1997.
The following are major changes between this version (09) of the AODV
draft and the previous version (08):
- Added section specifically about sequence number management.
- Added the port number 654 to the specification, since it has
already been allocated.
- Rewrote the Security Considerations section to include more
details about the specific exposures relevant to AODV instead of
only for routing protocols in general.
- Clarified that nodes increment the sequence number for a
destination on the other side of a broken link at the time the
link breaks, and not as part of any later message processing.
- Clarified that "broadcast" means transmission to 255.255.255.255,
and "flooding" means iterated broadcast by each node in turn
until every node in the network has received the message.
- Promoted former section 8.2.1 ("Controlling Route Request
broadcasts") to be its own major section.
- Fine-tuned specification for lifetime for reverse routes.
- Removed references to unused, nonexistent, and unspecified ICMP
ACK message.
- Added paragraph about creating/updating routes to neighbors when
receive control packets from them (section 8.3).
- Added action for a source initiating a RREQ - it records the
Flooding ID and source IP address of the RREQ so that it will
not reprocess the packet as it receives it from its neighbors
(section 8.5).
- Clarified when to increment the sequence number in a RREQ in
section 8.6.1.
- Reordered the paragraphs in section 8.6.1 so that they follow
temporal order.
- Clarified that RREPs are unicast to the next hop en route to the
source, not to the actual source node, so that the intermediate
nodes can process the RREP (section 8.7)
- Made terminology changes so that routes to neighbors advertising
HELLO messages are considered active routes (section 8.9).
Author's Addresses Author's Addresses
Questions about this memo can be directed to: Questions about this memo can be directed to:
Charles E. Perkins Charles E. Perkins
Communications Systems Laboratory Communications Systems Laboratory
Nokia Research Center Nokia Research Center
313 Fairchild Drive 313 Fairchild Drive
Mountain View, CA 94303 Mountain View, CA 94303
USA USA
+1 650 625 2986 +1 650 625 2986
+1 650 691 2170 (fax) +1 650 691 2170 (fax)
charliep@iprg.nokia.com charliep@iprg.nokia.com
Elizabeth M. Royer Elizabeth M. Belding-Royer
Dept. of Computer Science Dept. of Computer Science
University of California, Santa Barbara University of California, Santa Barbara
Santa Barbara, CA 93106 Santa Barbara, CA 93106
+1 805 893 3411 +1 805 893 3411
+1 805 893 8553 (fax) +1 805 893 8553 (fax)
eroyer@cs.ucsb.edu ebelding@cs.ucsb.edu
Samir R. Das Samir R. Das
Department of Electrical and Computer Engineering Department of Electrical and Computer Engineering
& Computer Science & Computer Science
University of Cincinnati University of Cincinnati
Cincinnati, OH 45221-0030 Cincinnati, OH 45221-0030
+1 513 556 2594 +1 513 556 2594
+1 513 556 7326 (fax) +1 513 556 7326 (fax)
sdas@ececs.uc.edu sdas@ececs.uc.edu
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/