draft-ietf-manet-aodv-10.txt

OMNET++仿真三色算法的源码,三色算法是无线传感器中一个典型的分簇算法

Mobile Ad Hoc Networking Working Group                Charles E. Perkins
INTERNET DRAFT                                     Nokia Research Center
19 January 2002                               Elizabeth M. Belding-Royer
                                 University of California, Santa Barbara
                                                            Samir R. Das
                                                University of Cincinnati

            Ad hoc On-Demand Distance Vector (AODV) Routing
                      draft-ietf-manet-aodv-10.txt


Status of This Memo

   This document is a submission by the Mobile Ad Hoc Networking Working
   Group of the Internet Engineering Task Force (IETF).  Comments should
   be submitted to the [e-mail] mailing list.

   Distribution of this memo is unlimited.

   This document is an Internet-Draft and is in full conformance with
   all provisions of Section 10 of RFC2026.  Internet-Drafts are working
   documents of the Internet Engineering Task Force (IETF), its areas,
   and its working groups.  Note that other groups may also distribute
   working documents as Internet-Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at
   any time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at:
        http://www.ietf.org/ietf/1id-abstracts.txt
   The list of Internet-Draft Shadow Directories can be accessed at:
        http://www.ietf.org/shadow.html.


Abstract

   The Ad hoc On-Demand Distance Vector (AODV) routing protocol
   is intended for use by mobile nodes in an ad hoc network.  It
   offers quick adaptation to dynamic link conditions, low processing
   and memory overhead, low network utilization, and 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.








Perkins, Belding-Royer, Das        Expires 19 July 2002         [Page i]

Internet Draft                   AODV                    19 January 2002




                                Contents


Status of This Memo                                                    i

Abstract                                                               i

 1. Introduction                                                       1

 2. Overview                                                           1

 3. AODV Terminology                                                   3

 4. Message Formats                                                    4
     4.1. Route Request (RREQ) Message Format . . . . . . . . . . .    4
     4.2. Route Reply (RREP) Message Format . . . . . . . . . . . .    5
     4.3. Route Error (RERR) Message Format . . . . . . . . . . . .    7

 5. Route Reply Acknowledgment (RREP-ACK) Message Format               8

 6. AODV Operation                                                     8
     6.1. Maintaining Sequence Numbers  . . . . . . . . . . . . . .    8
     6.2. Maintaining Route Table Entries and Precursor Lists . . .   10
     6.3. Generating Route Requests . . . . . . . . . . . . . . . .   10
     6.4. Controlling Dissemination of Route Request Messages . . .   11
     6.5. Processing and Forwarding Route Requests  . . . . . . . .   12
     6.6. Generating Route Replies  . . . . . . . . . . . . . . . .   14
           6.6.1. Route Reply Generation by the Destination . . . .   14
           6.6.2. Route Reply Generation by an Intermediate Node  .   14
           6.6.3. Generating Gratuitous RREPs . . . . . . . . . . .   15
     6.7. Receiving and Forwarding Route Replies  . . . . . . . . .   16
     6.8. Operation over Unidirectional Links . . . . . . . . . . .   17
     6.9. Hello Messages  . . . . . . . . . . . . . . . . . . . . .   17
    6.10. Maintaining Local Connectivity  . . . . . . . . . . . . .   18
    6.11.  Route Error Messages, Route Expiry and Route Deletion  .   19
    6.12. Local Repair  . . . . . . . . . . . . . . . . . . . . . .   20
    6.13. Actions After Reboot  . . . . . . . . . . . . . . . . . .   22
    6.14. Interfaces  . . . . . . . . . . . . . . . . . . . . . . .   22

 7. AODV and Aggregated Networks                                      23

 8. Using AODV with Other Networks                                    23

 9. Extensions                                                        24
     9.1. Hello Interval Extension Format . . . . . . . . . . . . .   24
     9.2. Timestamp Extension Format  . . . . . . . . . . . . . . .   25




Perkins, Belding-Royer, Das        Expires 19 July 2002        [Page ii]

Internet Draft                   AODV                    19 January 2002


10. Configuration Parameters                                          25

11. Security Considerations                                           27

12. Acknowledgments                                                   28

 A. Draft Modifications                                               29


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
   broken link.

   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 for 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 always selects
   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 at port 654, over 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.




Perkins, Belding-Royer, Das        Expires 19 July 2002         [Page 1]

Internet Draft                   AODV                    19 January 2002


   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 an
   unexpired 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 which are now unreachable due to
   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 that 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 6.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 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 ephemeral routes, such as are created to temporarily
   store reverse paths towards nodes originating RREQs.  AODV











Perkins, Belding-Royer, Das        Expires 19 July 2002         [Page 2]

Internet Draft                   AODV                    19 January 2002


   uses the following fields with each route table entry:

       -  Destination IP Address
       -  Destination Sequence Number
       -  Interface
       -  Hop Count (number of hops needed to reach destination)
       -  Last Hop Count (described in subsections 6.4 and 6.11)
       -  Next Hop
       -  List of Precursors (described in Section 6.2)
       -  Lifetime (expiration or deletion time of the route)
       -  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 route is invalidated by operations involving
   the sequence number and metric (hop count).  See section 6.1 for
   details.


3. AODV Terminology

   This protocol specification uses conventional meanings [2] 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].

      active route

         A routing table entry with a finite metric in the Hop Count
         field.  A routing table may contain entries that are not active
         (invalid routes or entries).  They have an infinite metric
         in the Hop Count field.  Only active entries can be used to
         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
         dissemination of AODV messages throughout the ad hoc network.

      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.



Perkins, Belding-Royer, Das        Expires 19 July 2002         [Page 3]

Internet Draft                   AODV                    19 January 2002


      forward route

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

      originating node

         A node that initiates an AODV message to be processed and
         possibly retransmitted by other nodes in the ad hoc network.