rfc3561.txt

路有算法aodv的linux下的版本

Network Working Group                                         C. Perkins
Request for Comments: 3561                         Nokia Research Center
Category: Experimental                                  E. Belding-Royer
                                 University of California, Santa Barbara
                                                                  S. Das
                                                University of Cincinnati
                                                               July 2003


            Ad hoc On-Demand Distance Vector (AODV) Routing

Status of this Memo

   This memo defines an Experimental Protocol for the Internet
   community.  It does not specify an Internet standard of any kind.
   Discussion and suggestions for improvement are requested.
   Distribution of this memo is unlimited.

Copyright Notice

   Copyright (C) The Internet Society (2003).  All Rights Reserved.

Abstract

   The Ad hoc On-Demand Distance Vector (AODV) routing protocol is
   intended for use by mobile nodes in an ad hoc network.  It offers
   quick adaptation to dynamic link conditions, low processing and
   memory overhead, low network utilization, and determines unicast
   routes to destinations within the ad hoc network.  It uses
   destination sequence numbers to ensure loop freedom at all times
   (even in the face of anomalous delivery of routing control messages),
   avoiding problems (such as "counting to infinity") associated with
   classical distance vector protocols.

Table of Contents

   1.  Introduction ...............................................  2
   2.  Overview  ..................................................  3
   3.  AODV Terminology ...........................................  4
   4.  Applicability Statement ....................................  6
   5.  Message Formats ............................................  7
       5.1. Route Request (RREQ) Message Format ...................  7
       5.2. Route Reply (RREP) Message Format .....................  8
       5.3. Route Error (RERR) Message Format ..................... 10
       5.4. Route Reply Acknowledgment (RREP-ACK) Message Format .. 11
   6.  AODV Operation ............................................. 11
       6.1. Maintaining Sequence Numbers .......................... 11
       6.2. Route Table Entries and Precursor Lists ............... 13



Perkins, et. al.              Experimental                      [Page 1]

RFC 3561                      AODV Routing                     July 2003


       6.3. Generating Route Requests ............................. 14
       6.4. Controlling Dissemination of Route Request Messages ... 15
       6.5. Processing and Forwarding Route Requests .............. 16
       6.6. Generating Route Replies .............................. 18
            6.6.1. Route Reply Generation by the Destination ...... 18
            6.6.2. Route Reply Generation by an Intermediate
                   Node ........................................... 19
            6.6.3. Generating Gratuitous RREPs .................... 19
       6.7. Receiving and Forwarding Route Replies ................ 20
       6.8. Operation over Unidirectional Links ................... 21
       6.9. Hello Messages ........................................ 22
       6.10 Maintaining Local Connectivity ........................ 23
       6.11 Route Error (RERR) Messages, Route Expiry and Route
            Deletion .............................................. 24
       6.12 Local Repair .......................................... 26
       6.13 Actions After Reboot  ................................. 27
       6.14 Interfaces ............................................ 28
   7.  AODV and Aggregated Networks ............................... 28
   8.  Using AODV with Other Networks ............................. 29
   9.  Extensions ................................................. 30
       9.1. Hello Interval Extension Format ....................... 30
   10. Configuration Parameters ................................... 31
   11. Security Considerations .................................... 33
   12. IANA Considerations ........................................ 34
   13. IPv6 Considerations ........................................ 34
   14. Acknowledgments ............................................ 34
   15. Normative References ....................................... 35
   16. Informative References ..................................... 35
   17. Authors' Addresses ......................................... 36
   18. Full Copyright Statement ................................... 37

1. Introduction

   The Ad hoc On-Demand Distance Vector (AODV) algorithm enables
   dynamic, self-starting, multihop routing between participating mobile
   nodes wishing to establish and maintain an ad hoc network.  AODV
   allows mobile nodes to obtain routes quickly for new destinations,
   and does not require nodes to maintain routes to destinations that
   are not in active communication.  AODV allows mobile nodes to respond
   to link breakages and changes in network topology in a timely manner.
   The operation of AODV is loop-free, and by avoiding the Bellman-Ford
   "counting to infinity" problem offers quick convergence when the ad
   hoc network topology changes (typically, when a node moves in the
   network).  When links break, AODV causes the affected set of nodes to
   be notified so that they are able to invalidate the routes using the
   lost link.





Perkins, et. al.              Experimental                      [Page 2]

RFC 3561                      AODV Routing                     July 2003


   One distinguishing feature of AODV is its use of a destination
   sequence number for each route entry.  The destination sequence
   number is created by the destination to be included along with any
   route information it sends to requesting nodes.  Using destination
   sequence numbers ensures loop freedom and is simple to program.
   Given the choice between two routes to a destination, a requesting
   node is required to select the one with the greatest sequence number.

2. Overview

   Route Requests (RREQs), Route Replies (RREPs), and Route Errors
   (RERRs) are the message types defined by AODV.  These message types
   are received via UDP, and normal IP header processing applies. So,
   for instance, the requesting node is expected to use its IP address
   as the Originator IP address for the messages.  For broadcast
   messages, the IP limited broadcast address (255.255.255.255) is used.
   This means that such messages are not blindly forwarded.  However,
   AODV operation does require certain messages (e.g., RREQ) to be
   disseminated widely, perhaps throughout the ad hoc network.  The
   range of dissemination of such RREQs is indicated by the TTL in the
   IP header.  Fragmentation is typically not required.

   As long as the endpoints of a communication connection have valid
   routes to each other, AODV does not play any role.  When a route to a
   new destination is needed, the node broadcasts a RREQ to find a route
   to the destination.  A route can be determined when the RREQ reaches
   either the destination itself, or an intermediate node with a 'fresh
   enough' route to the destination.  A 'fresh enough' route is a valid
   route entry for the destination whose associated 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 origination of the RREQ.
   Each node receiving the request caches a route back to the originator
   of the request, so that the RREP can be unicast from the destination
   along a path to that originator, or likewise from any intermediate
   node that is able to satisfy the request.

   Nodes monitor the link status of next hops in active routes.  When a
   link break in an active route is detected, a RERR message is used to
   notify other nodes that the loss of that link has occurred.  The RERR
   message indicates those destinations (possibly subnets) which are no
   longer reachable by way of the broken 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 each destination.  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 6.6).  If the RREP has a nonzero prefix




Perkins, et. al.              Experimental                      [Page 3]

RFC 3561                      AODV Routing                     July 2003


   length, then the originator of the RREQ which solicited the RREP
   information is included among the precursors for the subnet route
   (not specifically for the particular destination).

   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 originator of such a 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 originating 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.
   Route table information must be kept even for short-lived routes,
   such as are created to temporarily store reverse paths towards nodes
   originating RREQs.  AODV uses the following fields with each route
   table entry:

   -  Destination IP Address
   -  Destination Sequence Number
   -  Valid Destination Sequence Number flag
   -  Other state and routing flags (e.g., valid, invalid, repairable,
      being repaired)
   -  Network Interface
   -  Hop Count (number of hops needed to reach destination)
   -  Next Hop
   -  List of Precursors (described in Section 6.2)
   -  Lifetime (expiration or deletion time of the route)

   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 route is invalidated by operations involving
   the sequence number and marking the route table entry state as
   invalid.  See section 6.1 for details.

3. AODV Terminology

   This protocol specification uses conventional meanings [1] for
   capitalized words such as MUST, SHOULD, etc., to indicate requirement
   levels for various protocol features.  This section defines other
   terminology used with AODV that is not already defined in [3].





Perkins, et. al.              Experimental                      [Page 4]

RFC 3561                      AODV Routing                     July 2003


      active route

         A route towards a destination that has a routing table entry
         that is marked as valid.  Only active routes can be used to
         forward data packets.

      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
         dissemination of AODV messages throughout the ad hoc network.

      destination

         An IP address to which data packets are to be transmitted.
         Same as "destination node".  A node knows it is the destination
         node for a typical data packet when its address appears in the
         appropriate field of the IP header.  Routes for destination
         nodes are supplied by action of the AODV protocol, which
         carries the IP address of the desired destination node in route
         discovery messages.

      forwarding node

         A node that agrees to forward packets destined for another
         node, by retransmitting them to a next hop that is closer to
         the unicast destination along a path that has been set up using
         routing control messages.

      forward route

         A route set up to send data packets from a node originating a
         Route Discovery operation towards its desired destination.

      invalid route

         A route that has expired, denoted by a state of invalid in the
         routing table entry.  An invalid route is used to store
         previously valid route information for an extended period of
         time.  An invalid route cannot be used to forward data packets,
         but it can provide information useful for route repairs, and
         also for future RREQ messages.








Perkins, et. al.              Experimental                      [Page 5]

RFC 3561                      AODV Routing                     July 2003


      originating node

         A node that initiates an AODV route discovery message to be
         processed and possibly retransmitted by other nodes in the ad
         hoc network.  For instance, the node initiating a Route
         Discovery process and broadcasting the RREQ message is called