draft-ietf-manet-aodv-10.txt

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

   node places its sequence number into the Destination Sequence Number
   field of the RREP, and enters the value zero in the Hop Count field
   of the RREP.

   The destination node copies the value MY_ROUTE_TIMEOUT (see
   section 10) into the Lifetime field of the RREP. Each node MAY
   reconfigure its value for MY_ROUTE_TIMEOUT, within mild constraints
   (see section 10).


6.6.2. Route Reply Generation by an Intermediate Node

   If the node generating the RREP is not the destination node, but
   instead is an intermediate hop along the path from the originator to
   the destination, it copies its last known sequence number for the
   destination into the Destination Sequence Number field in the RREP
   message.





Perkins, Belding-Royer, Das        Expires 19 July 2002        [Page 14]

Internet Draft                   AODV                    19 January 2002


   The intermediate node updates the forward path route entry by placing
   the last hop node (from which it received the 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 entry for the
   Destination IP Address.  The intermediate node also updates its route
   table entry for the node originating the RREQ by placing the next hop
   towards the destination in the precursor list for the reverse route
   entry -- i.e., the entry for the Originator IP Address field of the
   RREQ message data.

   The intermediate node places its distance in hops from the
   destination (indicated by the hop count in the routing table) in
   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.


6.6.3. Generating Gratuitous RREPs

   After a node receives a RREQ and responds with a RREP, it discards
   the RREQ. If intermediate nodes reply to every transmission of a
   given RREQ, the destination does not receive any copies of it.  In
   this situation, it does not learn of a route to the originating node.
   This could cause the destination to initiate a network-wide route
   discovery (for example, if the originator is attempting to establish
   a TCP session).  In order that the destination learn of routes to the
   originating node, the originating node SHOULD set the ``gratuitous
   RREP'' ('G') flag in the RREQ if for any reason the destination is
   likely to need a route to the originating node.  If, in response to a
   RREQ with the 'G' flag set, an intermediate node returns a RREP, it
   MUST also unicast a gratuitous RREP to the destination node.

   The RREP that is sent to the originator of the RREQ is the same
   as before.  The gratuitous RREP that is to be sent to the desired
   destination contains the following values in the RREP message fields:

      Hop Count  The Hop Count as indicated in the node's route table
                 entry for the originator

      Destination IP Address
                 The IP address of the node that originated the RREQ

      Destination Sequence Number
                 The Originator Sequence Number from the RREQ

      Originator IP Address
                 The IP address of the Destination node in the RREQ





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


      Lifetime   The remaining lifetime of the route towards the
                 originator of the RREQ, as known by the intermediate
                 node.

   The gratuitous RREP is then sent to the next hop along the path to
   the destination node, just as if the destination node had already
   issued a RREQ for the originating node and this RREP was produced in
   response to that (fictitious) RREQ.


6.7. Receiving and Forwarding Route Replies

   When a node receives a RREP message, it compares the Destination
   Sequence Number in the message with its own copy of destination
   sequence number for the Destination IP Address in the RREP message.
   The forward route for this destination is created if it does not
   already exist, or it is updated only if (i) the Destination Sequence
   Number in the RREP is greater than the node's copy of the destination
   sequence number, or (ii) the sequence numbers are the same, but the
   route is no longer active, or (iii) the sequence numbers are the
   same, and the Hop Count in the RREP is smaller than the hop count
   in route table entry.  In either of these cases, the next hop in
   the route entry is assigned to be the node from which the RREP is
   received, which is indicated by the source IP address field in the
   IP header; the hop count is the Hop Count in the RREP message plus
   one; the expiry time is the current time plus the Lifetime in the
   RREP message; and the destination sequence number is the Destination
   Sequence Number in the RREP message.  The current node can now begin
   using this route to forward data packets to the destination.

   If the current node is not the node indicated by the Originator IP
   Address in the RREP message AND a forward route has been created or
   updated as described above, the node consults its route table entry
   for the originating node to determine the next hop for the RREP
   packet, and then forwards the RREP towards the originator using the
   information in the route table entry.

   When any node transmits a RREP, the precursor list for 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 (reverse) route used to forward a RREP has its lifetime
   changed to be the maximum of (existing-lifetime, (current time +
   ACTIVE_ROUTE_TIMEOUT)).

   If a node forwards a RREP over a link that is likely to have errors
   or be unidirectional, the node SHOULD set the `A' flag to require
   that the recipient of the RREP acknowledge receipt of the RREP by
   sending a RREP-ACK message back (see section 6.8).




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


6.8. Operation over Unidirectional Links

   It is possible that a RREP transmission may fail, especially if the
   RREQ transmission triggering the RREP occurs over a unidirectional
   link.  If no other RREP generated from the same route discovery
   attempt reaches the node which originated the RREQ message, the
   originator will reattempt network-wide route discovery after a
   timeout (see section 6.3).  However, the same scenario might well
   be repeated, and no route would be discovered even after repeated
   retries.  Unless corrective action is taken, this can happen even
   when bidirectional routes between originator and destination do
   exist.  Link layers using broadcast transmissions for the RREQ will
   not be able to detect the presence of such unidirectional links.  In
   AODV, any node acts on only the first RREQ with the same RREQ ID
   and ignores any subsequent RREQs.  Suppose, for example, that the
   first RREQ arrives along a path that has one or more unidirectional
   link(s).  A subsequent RREQ may arrive via a bidirectional path
   (assuming such paths exist), but it will be ignored.

   To prevent this problem, when a node detects that its transmission of
   a RREP message has failed, it remembers the next-hop of the failed
   RREP in a ``blacklist'' set.  Such failures can be detected via
   the absence of a link-layer or network-layer acknowledgment (e.g.,
   RREP-ACK). A node ignores all RREQs received from any node in its
   blacklist set.  Nodes are removed from the blacklist set after a
   BLACKLIST_TIMEOUT period (see section 10).  This period should be set
   to the upper bound of the time it takes to perform the allowed number
   of route request retry attempts as described in section 6.3.


6.9. Hello Messages

   A node MAY offer connectivity information by broadcasting local
   Hello messages as follows.  Every HELLO_INTERVAL milliseconds, the
   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 has not, it MAY broadcast a RREP with TTL = 1, called a Hello
   message, with the RREP message fields set as follows:

      Destination IP Address
                  The node's IP address.

      Destination Sequence Number
                  The node's latest sequence number.

      Hop Count   0

      Lifetime    ALLOWED_HELLO_LOSS * HELLO_INTERVAL




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


   A node MAY determine connectivity by listening for packets from its
   set of neighbors.  If, within the past DELETE_PERIOD, it has received
   a Hello message from a neighbor, and then for that neighbor does
   not receive any packets (Hello messages or otherwise) for more than
   ALLOWED_HELLO_LOSS * HELLO_INTERVAL milliseconds, the node SHOULD
   assume that the link to this neighbor is currently broken.  When this
   happens, the node SHOULD proceed as in Section 6.11.

   Whenever a node receives a Hello message 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 ALLOWED_HELLO_LOSS * HELLO_INTERVAL. 
   
   The route to the neighbor,
   if it exists, MUST subsequently contain the latest Destination
   Sequence Number from the Hello message.  
   
   Routes that are newly
   created from the reception of Hello messages might have empty
   precursor lists, and in that case would not trigger RERR messages
   when the neighbor moves away and the neighbor route expires.


6.10. Maintaining Local Connectivity

   Each forwarding node SHOULD keep track of its continued connectivity
   to its active next hops (i.e., which next hops or precursors have
   forwarded packets to or from the forwarding node during the last
   ACTIVE_ROUTE_TIMEOUT), as well as neighbors that have transmitted
   Hello messages during the last (ALLOWED_HELLO_LOSS * HELLO_INTERVAL).
   A node can maintain accurate information about its continued
   connectivity to these active next hops, using one or more of the
   available link or network layer mechanisms, as described below.

    -  Any suitable link layer notification, such as those provided by
       IEEE 802.11, can be used to determine connectivity, each time
       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
       RTS, even after the maximum number of retransmission attempts,
       indicates loss of the link to this active next hop.

    -  If possible, passive acknowledgment SHOULD be used when the
       next hop is expected to forward the packet, by listening to the
       channel for a transmission attempt made by the next hop.  If
       transmission is not detected within NEXT_HOP_WAIT milliseconds or
       the next hop is the destination (and thus is never supposed to
       transmit the packet) one of the following methods should be used
       to determine connectivity.

        *  Receiving any packet (including a Hello message) from the
           next hop.




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


        *  A RREQ unicast to the next hop, asking for a route 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,
   the forwarding node SHOULD assume that the link is broken, and take
   corrective action by following the methods specified in Section 6.11.

qua
6.11.  Route Error Messages, Route Expiry and Route Deletion

   A Route Error (RERR) message MAY be either broadcast (if there
   are many precursors), unicast (if there is only 1 precursor),
   or iteratively unicast to all precursors (if broadcast is
   inappropriate).  Even when the RERR message is iteratively unicast to
   several precursors, it is considered to be a single control message
   for the purposes of the description in the text that follows.

   A node initiates processing for a RERR message in three situations:

      (i)       if it detects a link break for the next hop of an active
                route in its routing table, or if the routing table
                entry for the next hop expires (also see section 6.1),
                or

      (ii)      if it gets a data packet destined to a node for which it
                does not have an active route, and has already made an
                attempt at local repair (if local repair is being used),
                or

      (iii)     if it receives a RERR from a neighbor for one or more
                active routes.

   For case 
   (i), the node first makes a list of unreachable destinations
   consisting of the unreachable neighbor and any additional