rfc3561.txt

Ad-hoc的路由协议

   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





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


   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.

   Note that the RREP-ACK packet does not contain any information about
   which RREP it is acknowledging.  The time at which the RREP-ACK is
   received will likely come just after the time when the RREP was sent
   with the 'A' bit.  This information is expected to be sufficient to
   provide assurance to the sender of the RREP that the link is
   currently bidirectional, without any real dependence on the
   particular RREP message being acknowledged.  However, that assurance
   typically cannot be expected to remain in force permanently.

6.9. Hello Messages

   A node MAY offer connectivity information by broadcasting local Hello
   messages.  A node SHOULD only use hello messages if it is part of an
   active route.  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

   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






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


   ALLOWED_HELLO_LOSS * HELLO_INTERVAL milliseconds, the node SHOULD
   assume that the link to this neighbor is currently lost.  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.  The current node
   can now begin using this route to forward data packets.  Routes that
   are created by hello messages and not used by any other active routes
   will have empty precursor lists and would not trigger a RERR message
   if the neighbor moves away and a neighbor timeout occurs.

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 layer-2 notification is not available, 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 not supposed to forward the packet) one of the following
      methods SHOULD be used to determine connectivity:

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

      *  A RREQ unicast to the next hop, asking for a route to the next
         hop.




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


      *  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 lost, and take
   corrective action by following the methods specified in Section 6.11.

6.11. Route Error (RERR) Messages, Route Expiry and Route Deletion

   Generally, route error and link breakage processing requires the
   following steps:

   -  Invalidating existing routes

   -  Listing affected destinations

   -  Determining which, if any, neighbors may be affected

   -  Delivering an appropriate RERR to such neighbors

   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.  With
   that understanding, a node SHOULD NOT generate more than
   RERR_RATELIMIT RERR messages per second.

   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 while transmitting data (and
             route repair, if attempted, was unsuccessful), or

   (ii)      if it gets a data packet destined to a node for which it
             does not have an active route and is not repairing (if
             using local repair), 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
   destinations (or subnets, see section 7) in the local routing table
   that use the unreachable neighbor as the next hop.  In this case, if
   a subnet route is found to be newly unreachable, an IP destination
   address for the subnet is constructed by appending zeroes to the




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


   subnet prefix as shown in the route table entry.  This is
   unambiguous, since the precursor is known to have route table
   information with a compatible prefix length for that subnet.

   For case (ii), there is only one unreachable destination, which is
   the destination of the data packet that cannot be delivered.  For
   case (iii), the list should consist of those destinations in the RERR
   for which there exists a corresponding entry in the local routing
   table that has the transmitter of the received RERR as the next hop.

   Some of the unreachable destinations in the list could be used by
   neighboring nodes, and it may therefore be necessary to send a (new)
   RERR.  The RERR should contain those destinations that are part of
   the created list of unreachable destinations and have a non-empty
   precursor list.

   The neighboring node(s) that should receive the RERR are all those
   that belong to a precursor list of at least one of the unreachable
   destination(s) in the newly created RERR.  In case there is only one
   unique neighbor that needs to receive the RERR, the RERR SHOULD be
   unicast toward that neighbor.  Otherwise the RERR is typically sent
   to the local broadcast address (Destination IP == 255.255.255.255,
   TTL == 1) with the unreachable destinations, and their corresponding
   destination sequence numbers, included in the packet.  The DestCount
   field of the RERR packet indicates the number of unreachable
   destinations included in the packet.

   Just before transmitting the RERR, certain updates are made on the
   routing table that may affect the destination sequence numbers for
   the unreachable destinations.  For each one of these destinations,
   the corresponding routing table entry is updated as follows:

   1. The destination sequence number of this routing entry, if it
      exists and is valid, is incremented for cases (i) and (ii) above,
      and copied from the incoming RERR in case (iii) above.

   2. The entry is invalidated by marking the route entry as invalid

   3. The Lifetime field is updated to current time plus DELETE_PERIOD.
      Before this time, the entry SHOULD NOT be deleted.

   Note that the Lifetime field in the routing table plays dual role --
   for an active route it is the expiry time, and for an invalid route
   it is the deletion time.  If a data packet is received for an invalid
   route, the Lifetime field is updated to current time plus
   DELETE_PERIOD.  The determination of DELETE_PERIOD is discussed in
   Section 10.




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


6.12. Local Repair

   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
   was no farther than MAX_REPAIR_TTL hops away.  To repair the link
   break, the node increments the sequence number for the destination
   and then broadcasts a RREQ for that destination.  The TTL of the RREQ
   should initially be set to the following value:

      max(MIN_REPAIR_TTL, 0.5 * #hops) + LOCAL_ADD_TTL,

   where #hops is the number of hops to the sender (originator) of the
   currently undeliverable packet.  Thus, local repair attempts will
   often be invisible to the originating node, and will always have TTL
   >= MIN_REPAIR_TTL + LOCAL_ADD_TTL.  The node initiating the repair
   then waits the discovery period to receive RREPs in response to the
   RREQ.  During local repair data packets SHOULD be buffered.  If, at
   the end of the discovery period, the repairing node has not received
   a RREP (or other control message creating or updating the route) for
   that destination, it proceeds as described in Section 6.11 by
   transmitting a RERR message for that destination.

   On the other hand, if the node receives one or more RREPs (or other
   control message creating or updating the route to the desired
   destination) during the discovery period, it first compares the hop
   count of the new route with the value in the hop count field of the
   invalid route table entry for that destination.  If the hop count of
   the newly determined route to the destination is greater than the hop
   count of the previously known route the node SHOULD issue a RERR
   message for the destination, with the 'N' bit set.  Then it proceeds
   as described in Section 6.7, updating its route table entry for that
   destination.

   A node that receives a RERR message with the 'N' flag set MUST NOT
   delete the route to that destination.  The only action taken should
   be the retransmission of the message, if the RERR arrived from the
   next hop along that route, and if there are one or more precursor
   nodes for that route to the destination.  When the originating node
   receives a RERR message with the 'N' flag set, if this message came
   from its next hop along its route to the destination then the
   originating node MAY choose to reinitiate route discovery, as
   described in Section 6.3.

   Local repair of link breaks in routes sometimes results in increased
   path lengths to those destinations.  Repairing the link locally is
   likely to increase the number of data packets that are able to be
   delivered to the destinations, since data packets will not be dropped
   as the RERR travels to the originating node.  Sending a RERR to the



Perkins, et. al.              Experimental                     [Page 26]

RFC 3561