draft-ietf-manet-aodv-07.txt   draft-ietf-manet-aodv-08.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
24 November 2000 Elizabeth M. Royer 2 March 2001 Elizabeth M. 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-07.txt draft-ietf-manet-aodv-08.txt
Status of This Memo Status of This Memo
This document is a submission by the Mobile Ad Hoc Networking Working
Group of the Internet Engineering Task Force (IETF). Comments should
be submitted to the manet@itd.nrl.navy.mil mailing list.
Distribution of this memo is unlimited.
This document is an Internet-Draft and is in full conformance with This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026. Internet-Drafts are working all provisions of Section 10 of RFC2026. Internet-Drafts are working
documents of the Internet Engineering Task Force (IETF), its areas, documents of the Internet Engineering Task Force (IETF), its areas,
and its working groups. Note that other groups may also distribute and its working groups. Note that other groups may also distribute
working documents as Internet-Drafts. working documents as Internet-Drafts.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at and may be updated, replaced, or obsoleted by other documents at
any time. It is inappropriate to use Internet-Drafts as reference any time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at: The list of current Internet-Drafts can be accessed at:
http://www.ietf.org/ietf/1id-abstracts.txt http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at: The list of Internet-Draft Shadow Directories can be accessed at:
http://www.ietf.org/shadow.html. http://www.ietf.org/shadow.html.
This document is a submission by the Mobile Ad Hoc Networking Working
Group of the Internet Engineering Task Force (IETF). Comments should
be submitted to the manet@itd.nrl.navy.mil mailing list.
Distribution of this memo is unlimited.
Abstract Abstract
The Ad Hoc On-Demand Distance Vector (AODV) routing protocol is The Ad Hoc On-Demand Distance Vector (AODV) routing protocol is
intended for use by mobile nodes in an ad hoc network. It offers intended for use by mobile nodes in an ad hoc network. It offers
quick adaptation to dynamic link conditions, low processing and quick adaptation to dynamic link conditions, low processing and
memory overhead, low network utilization, and determines unicast memory overhead, low network utilization, and determines unicast
between sources and destinations. It uses destination sequence between sources and destinations. It uses destination sequence
numbers to ensure loop freedom at all times (even in the face of numbers to ensure loop freedom at all times (even in the face of
anomalous delivery of routing control messages), solving problems anomalous delivery of routing control messages), solving problems
(such as ``counting to infinity'') associated with classical distance (such as ``counting to infinity'') associated with classical distance
skipping to change at page 1, line 49 skipping to change at page 1, line 50
intended for use by mobile nodes in an ad hoc network. It offers intended for use by mobile nodes in an ad hoc network. It offers
quick adaptation to dynamic link conditions, low processing and quick adaptation to dynamic link conditions, low processing and
memory overhead, low network utilization, and determines unicast memory overhead, low network utilization, and determines unicast
between sources and destinations. It uses destination sequence between sources and destinations. It uses destination sequence
numbers to ensure loop freedom at all times (even in the face of numbers to ensure loop freedom at all times (even in the face of
anomalous delivery of routing control messages), solving problems anomalous delivery of routing control messages), solving problems
(such as ``counting to infinity'') associated with classical distance (such as ``counting to infinity'') associated with classical distance
vector protocols. vector protocols.
Contents Contents
Status of This Memo i Status of This Memo i
Abstract i Abstract i
1. Introduction 1 1. Introduction 1
2. Overview 2 2. Overview 1
3. AODV Terminology 3 3. AODV Terminology 2
4. Route Request (RREQ) Message Format 4 4. Route Request (RREQ) Message Format 3
5. Route Reply (RREP) Message Format 5 5. Route Reply (RREP) Message Format 4
6. Route Error (RERR) Message Format 7 6. Route Error (RERR) Message Format 6
7. Route Reply Acknowledgment (RREP-ACK) Message Format 8 7. Route Reply Acknowledgment (RREP-ACK) Message Format 7
8. AODV Operation 8 8. AODV Operation 7
8.1. Maintaining Route Utilization Records . . . . . . . . . . 8 8.1. Maintaining Route Utilization Records . . . . . . . . . . 7
8.2. Generating Route Requests . . . . . . . . . . . . . . . . 9 8.2. Generating Route Requests . . . . . . . . . . . . . . . . 7
8.2.1. Controlling Route Request broadcasts . . . . . . 10 8.2.1. Controlling Route Request broadcasts . . . . . . 8
8.3. Forwarding Route Requests . . . . . . . . . . . . . . . . 11 8.3. Forwarding Route Requests . . . . . . . . . . . . . . . . 9
8.3.1. Processing Route Requests . . . . . . . . . . . . 11 8.3.1. Processing Route Requests . . . . . . . . . . . . 9
8.4. Generating Route Replies . . . . . . . . . . . . . . . . 13 8.4. Generating Route Replies . . . . . . . . . . . . . . . . 11
8.4.1. Route Reply Generation by the Destination . . . 13 8.4.1. Route Reply Generation by the Destination . . . 11
8.4.2. Route Reply Generation by an Intermediate Node . 14 8.4.2. Route Reply Generation by an Intermediate Node . 11
8.5. Generating Gratuitous RREPs . . . . . . . . . . . . . . . 14 8.4.3. Generating Gratuitous RREPs . . . . . . . . . . . 12
8.6. Forwarding Route Replies . . . . . . . . . . . . . . . . 15 8.5. Forwarding Route Replies . . . . . . . . . . . . . . . . 13
8.7. Hello Messages . . . . . . . . . . . . . . . . . . . . . 16 8.6. Operation over Unidirectional Links . . . . . . . . . . . 14
8.8. Maintaining Local Connectivity . . . . . . . . . . . . . 17 8.7. Hello Messages . . . . . . . . . . . . . . . . . . . . . 14
8.9. Route Error Messages . . . . . . . . . . . . . . . . . . 18 8.8. Maintaining Local Connectivity . . . . . . . . . . . . . 15
8.9.1. Local Repair . . . . . . . . . . . . . . . . . . 19 8.9. Route Error Messages . . . . . . . . . . . . . . . . . . 16
8.10. Route Expiry and Deletion . . . . . . . . . . . . . . . . 21 8.9.1. Local Repair . . . . . . . . . . . . . . . . . . 17
8.11. Actions After Reboot . . . . . . . . . . . . . . . . . . 21 8.10. Route Expiry and Deletion . . . . . . . . . . . . . . . . 18
8.12. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 22 8.11. Actions After Reboot . . . . . . . . . . . . . . . . . . 19
9. AODV and Aggregated Networks 22 8.12. Interfaces . . . . . . . . . . . . . . . . . . . . . . . 19
10. Using AODV with Other Networks 23 9. AODV and Aggregated Networks 20
11. Extensions 24 10. Using AODV with Other Networks 20
11.1. Hello Interval Extension Format . . . . . . . . . . . . . 24
12. Configuration Parameters 25 11. Extensions 20
11.1. Hello Interval Extension Format . . . . . . . . . . . . . 21
13. Security Considerations 26 12. Configuration Parameters 21
14. Acknowledgments 27 13. Security Considerations 23
14. Acknowledgments 23
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 2, line 46 skipping to change at page 2, line 28
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 subsection 8.2.1)
- Next Hop - Next Hop
- List of Precursors (described in Section 8.1) - List of Precursors (described in Section 8.1)
- Lifetime (expiration or deletion time of the route) - Lifetime (expiration or deletion time of the route)
- Routing Flags - Routing Flags
3. AODV Terminology 3. AODV Terminology
This protocol specification uses conventional meanings [1] for This protocol specification uses conventional meanings [1] 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
skipping to change at page 4, line 40 skipping to change at page 4, line 8
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.5) sections 8.2, 8.4.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 Broadcast 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.
skipping to change at page 6, line 11 skipping to change at page 5, line 11
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 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.6. A Acknowledgment required; see sections 7 and 8.5.
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 8, line 24 skipping to change at page 7, line 17
0 1 0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type | Reserved | | Type | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Type 4 Type 4
Reserved Sent as 0; ignored on reception. Reserved Sent as 0; ignored on reception.
The RREP-ACK message is 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
RREQs, RREPs and RERRs for unicast communication, and how the message RREQs, RREPs and RERRs for unicast communication, and how the message
data are handled. data are handled.
8.1. Maintaining Route Utilization Records 8.1. Maintaining Route Utilization Records
skipping to change at page 9, line 29 skipping to change at page 8, line 13
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 Broadcast ID field is incremented by one from the last
broadcast ID used by the current node. Each node maintains only one broadcast ID used by the current node. Each node maintains only one
broadcast ID. The Hop Count field is set to zero. broadcast ID. The Hop Count field is set to zero.
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 to cause must also have a route back to the source node. In order for this
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.4) 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.5 for details about actions taken by the the `G' flag. See section 8.4.3 for details about actions taken by
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
rebroadcast the RREQ, up to a maximum of RREQ_RETRIES times. Each rebroadcast the RREQ, up to a maximum of RREQ_RETRIES times. Each
rebroadcast MUST increment the Broadcast ID field. rebroadcast MUST increment the Broadcast 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. If
a RREQ has been rebroadcast RREQ_RETRIES times without receiving any a RREQ has been rebroadcast RREQ_RETRIES times without receiving any
RREP, all data packets destined for the corresponding destination RREP, all data packets destined for the corresponding destination
skipping to change at page 11, line 35 skipping to change at page 10, line 5
an active route, it rebroadcasts the RREQ from its interface(s) but 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 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 Destination Sequence Number in the RREQ is updated to the maximum
of the existing Destination Sequence Number in the RREQ and the of the existing Destination Sequence Number in the RREQ and the
destination sequence number in the routing table (if an entry exists) 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 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 header is decreased by one. The Hop Count field in the broadcast
RREQ message is incremented by one, to account for the new hop RREQ message is incremented by one, to account for the new hop
through the intermediate node. through the intermediate node.
If the node, on the other hand, does has an active route for the If the node, on the other hand, does have an active route for the
destination, it compares the destination sequence number for that destination, it compares the destination sequence number for that
route with the Destination Sequence Number field of the incoming route with the Destination Sequence Number field of the incoming
RREQ. If the existing destination sequence number is smaller than RREQ. If the existing destination sequence number is smaller than
the Destination Sequence Number field of the RREQ, the node again 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 rebroadcasts the RREQ just as if it did not have an active route to
the destination. the destination.
The node generates a RREP (as discussed further in section 8.4) if The node generates a RREP (as discussed further in section 8.4) if
either: either:
skipping to change at page 14, line 13 skipping to change at page 12, line 8
determination about its value MY_ROUTE_TIMEOUT. determination about its value MY_ROUTE_TIMEOUT.
8.4.2. Route Reply Generation by an Intermediate Node 8.4.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 The intermediate node places its distance in hops from the
destination (indicated by the hop count in the routing table) in the destination (indicated by the hop count in the routing table) plus
Hop Count field in the RREP. 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 calculates the Lifetime field of the RREP by
subtracting the current time from the expiration time in its route subtracting the current time from the expiration time in its route
table entry. table entry.
8.5. Generating Gratuitous RREPs 8.4.3. Generating Gratuitous RREPs
When a node receives a RREQ and responds with a RREP, it does not When a node receives a RREQ and responds with a RREP, it does not
forward the RREQ any further. If all incarnations of a single forward the RREQ any further. If all incarnations of a single
RREQ are replied to by intermediate nodes, the destination does RREQ are replied to by intermediate nodes, the destination does
not receive any copies of the RREQ. Hence, it does not learn of a not receive any copies of the RREQ. Hence, it does not learn of a
route to the source node. This can be problematic if the source is route to the source node. This can be problematic if the source is
attempting to establish a TCP session. In order that the destination attempting to establish a TCP session. In order that the destination
learn of routes to the source node, the source node SHOULD set the learn of routes to the source node, the source node SHOULD set the
gratuitous RREP ('G') flag in the RREQ if the session is going to be gratuitous RREP ('G') flag in the RREQ if the session is going to be
run over TCP, or if the destination should receive the gratuitous run over TCP, or if the destination should receive the gratuitous
skipping to change at page 15, line 16 skipping to change at page 13, line 4
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 generated 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
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.6. Forwarding Route Replies 8.5. Forwarding Route Replies
When a node receives a RREP message, it first compares the When a node receives a RREP message, it first compares the
Destination Sequence Number in the message with its own copy of Destination Sequence Number in the message with its own copy of
destination sequence number for the Destination IP Address. The destination sequence number for the Destination IP Address in the
forward route for this destination is created or updated only if RREP message. The forward route for this destination is created or
(i) the Destination Sequence Number in the RREP is greater than the updated only if (i) the Destination Sequence Number in the RREP is
node's copy of the destination sequence number, or (ii) the sequence greater than the node's copy of the destination sequence number, or
numbers are the same, but the route is no longer active or the Hop (ii) the sequence numbers are the same, but the route is no longer
Count in RREP is smaller than the hop count in route table entry. If active or the Hop Count in RREP is smaller than the hop count in
a new route is created or the old route is updated, the next hop is route table entry. If a new route is created or the old route is
the node from which the RREP is received, which is indicated by the updated, the next hop is the node from which the RREP is received,
source IP address field in the IP header; the hop count is the Hop which is indicated by the source IP address field in the IP header;
Count in the RREP message plus one; the expiry time is the current the hop count is the Hop Count in the RREP message plus one; the
time plus the Lifetime in the RREP message; the destination sequence expiry time is the current time plus the Lifetime in the RREP
number is the Destination Sequence Number in the RREP message. 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 send data packets
to the destination. 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
the node MAY set the `A' flag to require that the recipient of the or be unidirectional, the node MAY set the `A' flag to require that
RREP acknowledge receipt of the RREP by sending a RREP-ACK message the recipient of the RREP acknowledge receipt of the RREP by sending
back. a RREP-ACK message back.
8.6. Operation over Unidirectional Links
When unidirectional links are present, it is possible that a RREP
transmission may fail. Such failure can be detected via the absence
of a link-layer or network-layer acknowledgment (e.g., RREP-ACK). If
no other RREP generated from the same route request broadcast reaches
the source, the source will redo the broadcast after a timeout (see
section 8.2). However, the same scenario will repeat, and no route
will be discovered even after repeated retries. This is possible
even when bidirectional routes between source and destination do
exist. This happens because a RREQ transmission may occur over a
unidirectional link. Link layers using broadcast transmissions for
RREQ will not be able to detect the presence of such unidirectional
links. Also, in AODV any node acts on only the first RREQ with
the same broadcast ID and ignores any subsequent RREQs. It is
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
remembers the next-hop of the failed RREP in a ``blacklist'' set. A
node ignores all RREQs received from any node in its blacklist set.
Nodes are removed from the blacklist set after a BLACKLIST_TIMEOUT
period. This period should be set to the upper bound of the time it
takes to perform the allowed number of route request retry attempts
as described in section 8.2.
8.7. Hello Messages 8.7. 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 it
has not, it MAY generate a broadcast RREP with TTL = 1, called a has not, it MAY generate a broadcast RREP with TTL = 1, called a
Hello message, with the message fields set as follows: Hello message, with the message fields set as follows:
skipping to change at page 18, line 28 skipping to change at page 16, line 24
(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 For cases (i) and (ii), the destination sequence numbers in the
routing table for the unreachable destination(s) are incremented by routing table for the unreachable destination(s) are incremented by
one. Then RERR is broadcast with the unreachable destination(s) and one. Then RERR is broadcast with the unreachable destination(s) and
their incremented destination sequence number(s) included in the their incremented destination sequence number(s) included in the
packet. For case (i), the unreachable destinations are the broken packet. For case (i), the unreachable destinations are the broken
next hop, and any additional destinations which are now unreachable 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 due to the loss of this next hop link. These additional destinations
one unreachable destination, which is the destination of the data are those that also use the lost link as next hop in the routing
packet that cannot be delivered. The DestCount field of the RERR table. For case (ii), there is only one unreachable destination,
packet indicates the number of unreachable destinations included in which is the destination of the data packet that cannot be delivered.
the packet. 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 (iii) when a node receives a RERR message, for each
unreachable destination included in the packet, the node determines unreachable destination included in the packet, the node determines
whether the source node (as indicated by the source IP address in the whether the source node (as indicated by the source IP address in the
IP header) forwarding the RERR packet is its own next hop used to IP header) forwarding the RERR packet is its own next hop used to
reach this destination. If so, the node takes the following actions: reach this destination. If so, the node takes the following actions:
(a) updates the corresponding destination sequence number (a) updates the corresponding destination sequence number
with the Destination Sequence Number in the packet, and with the Destination Sequence Number in the packet, and
(b) marks the Hop Count for this destination as infinity, (b) marks the Hop Count for this destination as infinity,
and thus invalidates the route. and thus invalidates the route. The old value of Hop
Count is copied into the Last Hop Count field.
(c) checks the precursor list for this destination. If one (c) checks the precursor list for this destination for
or more of these precursor lists are non-empty, the node emptiness. If one or more of the precursor lists for
the unreachable destinations are non-empty, the node
creates a RERR message, including as unreachable each creates a RERR message, including as unreachable each
destination with a non-empty precursor list. It also destination with a non-empty precursor list. It also
includes their destination sequence numbers, and then includes their destination sequence numbers, and then
broadcasts this RERR message. broadcasts this RERR message.
When a node receives a RERR message, it always updates its When a node broadcasts a RERR message, it always deletes the
destination sequence number(s) for the unreachable destination(s) precursor list of each unreachable destination included in the
included in the packet using the corresponding sequence numbers message.
included in the message. When a node broadcasts a RERR message, it
always deletes the precursor list of each unreachable destination
included in the message.
When a node invalidates a route to a neighboring node, it must also When a node invalidates a route to a neighboring node, it must also
delete that neighbor from any precursor lists for routes to other delete that neighbor from any precursor lists for routes to other
nodes. This prevents precursor lists from containing stale entries nodes. This prevents precursor lists from containing stale entries
of neighbors with which the node is no longer able to communicate. of neighbors with which the node is no longer able to communicate.
The node should inspect the precursor list of each destination entry The node should inspect the precursor list of each destination entry
in its routing table, and delete the lost neighbor from any list in in its routing table, and delete the lost neighbor from any list in
which it appears. which it appears.
8.9.1. Local Repair 8.9.1. 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 broadcasts a RREQ for that destination. The TTL of the RREQ
should initially be set to the following value: should initially be set to the following value:
max(MIN_REPAIR_TTL, 0.5 TTL 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.9 by creating a
RERR message for that destination. 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 during
the discovery period, the node proceeds as described in Section 8.6, the discovery period, the node proceeds as described in Section 8.5,
creating a route table entry for that destination. It then compares creating a route table entry for that destination. It then compares
the hop count of the new route with the value in the last hop count the hop count of the new route with the value in the last hop count
route table entry for that destination. If the hop count of the route table entry for that destination. If the hop count of the
newly determined route to the destination is greater than the hop newly determined route to the destination is greater than the hop
count of the previously known route, as recorded in the last hop count of the previously known route, as recorded in the last hop
count field, the node MAY create a RERR message for the destination count field, the node MAY create a RERR message for the destination
and send this message to the source node. The node sets the 'N' flag and send this message to the source node. The node sets the 'N' flag
of the RERR, and then broadcasts this message if it has one or more of the RERR, and then broadcasts this message if it has one or more
precursor nodes for this route table entry. precursor nodes for this route table entry.
skipping to change at page 21, line 41 skipping to change at page 19, line 15
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.11. 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 after reboot as it will have lost its prior sequence actions after reboot as it will have lost its prior sequence number
number and as well as its last known sequence numbers for various and as well as its last known sequence numbers for various other
other destinations. However, there may be neighboring nodes which destinations. However, there may be neighboring nodes which are
are using this node as an active next hop. This can potentially using this node as an active next hop. This can potentially create
create routing loops. To prevent this possibility, each node on routing loops. To prevent this possibility, each node on reboot
reboot waits for DELETE_PERIOD. In this time, it does not respond waits for DELETE_PERIOD. In this time, it does not respond to
to any routing packets. However, if it receives a data packet, any routing packets. However, if it receives a data packet, it
it broadcasts a RERR as described in subsection 8.9 and resets broadcasts a RERR as described in subsection 8.9 and resets the
the waiting timer (Lifetime) to expire after current time plus waiting timer to expire after current time plus DELETE_PERIOD.
DELETE_PERIOD.
It can be shown that by the time the rebooted node comes out of It can be shown 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.12. Interfaces
skipping to change at page 22, line 35 skipping to change at page 19, line 48
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 receiving and
rebroadcasting a RREQ message rebroadcasts that message on all rebroadcasting a RREQ message rebroadcasts that message on all
interfaces. Similarly, when a node needs to transmit a RERR, it interfaces. When a node needs to transmit a RERR, it should only
should only broadcast it on those interfaces which have precursor broadcast it on those interfaces which have precursor nodes for that
nodes for that route. 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 25, line 26 skipping to change at page 22, line 14
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.
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
BROADCAST_RECORD_TIME 2 * NET_TRAVERSAL_TIME BROADCAST_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
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
NET_TRAVERSAL_TIME 3 * NODE_TRAVERSAL_TIME * NET_DIAMETER / 2 NET_TRAVERSAL_TIME 3 * NODE_TRAVERSAL_TIME * NET_DIAMETER / 2
RREQ_RETRIES 2 RREQ_RETRIES 2
TTL_START 1 TTL_START 1
TTL_INCREMENT 2 TTL_INCREMENT 2
TTL_THRESHOLD 7 TTL_THRESHOLD 7
DELETE_PERIOD should be an upper bound on the time for which
an upstream node A can have a neighbor B to be an active next The MIN_REPAIR_TTL should be the last known hop count to the
hop for destination D, while B has invalidated the route to D. destination.
Beyond this time B can delete the route to D. The determination
of the upper bound somewhat depends on the characteristics of DELETE_PERIOD should be an upper bound on the time for which an
the underlying link layer. For example, if the link layer upstream node A can have a neighbor B as an active next hop for
feedback is used to detect loss of link DELETE_PERIOD must be destination D, while B has invalidated the route to D. Beyond this
at least ACTIVE_ROUTE_TIMEOUT. If there is no feedback and hello time B can delete the route to D. The determination of the upper
messages must be used, DELETE_PERIOD must be at least maximum of bound somewhat depends on the characteristics of the underlying link
ACTIVE_ROUTE_TIMEOUT and ALLOWED_HELLO_LOSS * HELLO_INTERVAL. If layer. For example, if the link layer feedback is used to detect
hello messages are received from a neighbor but data packets to that loss of link DELETE_PERIOD must be at least ACTIVE_ROUTE_TIMEOUT.
neighbor are lost, (due to temporary link asymmetry, e.g.) we have If there is no feedback and hello messages must be used,
to make more concrete assumptions about the underlying link layer. DELETE_PERIOD must be at least maximum of ACTIVE_ROUTE_TIMEOUT
We assume that such asymmetry cannot persist beyond a certain certain and ALLOWED_HELLO_LOSS * HELLO_INTERVAL. If hello messages are
time, say, a multiple K of ALLOWED_HELLO_LOSS * HELLO_INTERVAL. received from a neighbor but data packets to that neighbor are
In other words, it cannot not be the case that a node receives K lost, (due to temporary link asymmetry, e.g.) we have to make more
subsequent hello messages from a neighbor, while that same neighbor concrete assumptions about the underlying link layer. We assume
fails to receive any data packet from the node in this period. This that such asymmetry cannot persist beyond a certain certain time,
is a reasonable assumption as this AODV specification works only with say, a multiple K of ALLOWED_HELLO_LOSS * HELLO_INTERVAL. In other
symmetric links. Covering all possibilities, words, it cannot not be the case that a node receives K subsequent
hello messages from a neighbor, while that same neighbor fails to
receive any data packet from the node in this period. Covering all
possibilities,
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 [2] 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. technologies etc. BLACKLIST_TIMEOUT should be suitably increased
if expanding ring search is used. In such cases, it should be
(TTL_THRESHOLD - TTL_START)/TTL_INCREMENT + 1 + RREQ_RETRIES. This is
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, and must be protected by use of authentication techniques
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. It is expected that, in
environments where security is an issue, that IPSec authentication environments where security is an issue, that IPSec authentication
headers will be deployed along with the necessary key management to headers will be deployed along with the necessary key management to
skipping to change at page 27, line 23 skipping to change at page 24, line 7
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 Lee
(especially regarding local repair) and Mahesh Marina. (especially regarding local repair) and Mahesh Marina.
References References
[1] S. Bradner. Key words to use in RFCs to indicate requirement [1] S. Bradner. Key words for use in RFCs to Indicate Requirement
levels. RFC 2119, March 1997. Levels. Request for Comments (Best Current Practice) 2119,
Internet Engineering Task Force, March 1997.
[2] IEEE Standards Department. Wireless LAN medium access control [2] IEEE 802.11 Committee, AlphaGraphics #35, 10201 N.35th Avenue,
(MAC) and physical layer (PHY) specifications, IEEE standard Phoenix AZ 85051. Wireless LAN Medium Access Control MAC and
802.11--1997, 1997. Physical Layer PHY Specifications, June 1997. IEEE Standard
802.11-97.
[3] C. E. Perkins. Mobile ad hoc networking terminology. IETF [3] Charles E. Perkins. Terminology for Ad-Hoc Networking (work in
Internet Draft, draft-ietf-manet-term-00.txt (Work in Progress), progress). draft-ietf-manet-terms-00.txt, November 1997.
October 1997.
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. Royer
Dept. of Electrical and Computer Engineering 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 7788 +1 805 893 3411
+1 805 893 3262 (fax) +1 805 893 8553 (fax)
eroyer@alpha.ece.ucsb.edu eroyer@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/