draft-ietf-manet-aodv-10.txt

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

   is less than zero, then the information related to that destination
   in the AODV message MUST be discarded, since that information is
   stale compared to the node's currently stored information.

   The only other circumstance in which a node may change the
   destination sequence number in one of its route table entries is in
   response to a broken or expired link to the next hop towards that
   destination.  The node determines which destinations use a broken
   next hop by consulting its routing table.  In this case, for each
   destination that uses the next hop, the node increments the sequence
   number and puts the Hop Count to be "infinity" (for the case of
   broken links, see also see sections 6.11, 6.12).

   A node may change the sequence number in the routing table entry of a
   destination only if:

    -  it is itself the destination node, and offers a new route to
       itself, or

    -  it receives an AODV message with new information about the
       sequence number for a destination node, or

    -  the path towards the destination node expires or breaks.







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


6.2. Maintaining Route Table Entries and Precursor Lists

   For each valid route maintained by a node (containing a finite Hop
   Count metric) as a routing table entry, the node also maintains a
   list of precursors that may be forwarding packets on this route.
   These precursors will receive notifications from the node in the
   event of detection of the loss of the next hop link.  The list of
   precursors in a routing table entry contains those neighboring nodes
   to which a route reply was generated or forwarded.

   When a node receives an AODV control packet from a neighbor, it
   checks its route table for an entry for that neighbor.  In the event
   that there is no corresponding entry for that neighbor, an entry
   is created.  The sequence number is either determined from the
   information contained in the control packet (i.e., the neighbor is
   the originator of a RREQ), or else it is initialized to zero if the
   sequence number for that node can not be determined.  The Lifetime
   field of the routing table entry is either determined from the
   control packet (i.e., the neighbor is the originator of a RREP for
   itself), or it is initialized to ALLOWED_HELLO_LOSS * HELLO_INTERVAL.
   In other words, the reception of a control packet has the same
   meaning as the reception of an explicit Hello message, in that it
   signifies an active connection to that neighbor.  The hop count to
   the neighbor is set to one.

   Each time a route is used to forward a data packet, its Active Route
   Lifetime field of both the destination and the next hop on the path
   to the destination is updated to be no less than the current time
   plus ACTIVE_ROUTE_TIMEOUT. Since the route between each originator
   and destination pair are expected to be symmetric, the Active Route
   Lifetime for the previous hop, along the reverse path back to the
   IP source, is also updated to be no less than the current time plus
   ACTIVE_ROUTE_TIMEOUT.


6.3. Generating Route Requests

   A node broadcasts a RREQ when it determines that it needs a route
   to a destination and does not have one available.  This can happen

   if the destination is previously unknown to the node, or if a
   previously valid route to the destination expires or

   is broken
   (i.e., an infinite metric is associated with the route).

   The   Destination Sequence Number field in the RREQ message is the last
   known destination sequence number for this destination and is copied
   from the Destination Sequence Number field in the routing table.

   If no sequence number is known, a sequence number of zero is used.  The
   Originator Sequence Number in the RREQ message is the node's own
   sequence number.  The RREQ ID field is incremented by one from the




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

Internet Draft                   AODV                    19 January 2002


   last RREQ ID used by the current node.  Each node maintains only one
   RREQ ID. The Hop Count field is set to zero.

   Before broadcasting the RREQ, the originating node buffers the RREQ
   ID and the Originator IP address (its own address) of the RREQ
   for PATH_TRAVERSAL_TIME milliseconds.  In this way, when the node
   receives the packet again from its neighbors, it will not reprocess
   and re-forward the packet.

   An originating node often expects to have bidirectional
   communications with a destination node.  In such cases, it is
   not sufficient for the originating node to have a route to the
   destination node; the destination must also have a route back to
   the originating node.  In order for this to happen as efficiently
   as possible, any generation of a RREP by an intermediate node (as
   in section 6.6) for delivery to the originating node SHOULD be
   accompanied by some action that notifies the destination about a
   route back to the originating node.  The originating node selects
   this mode of operation in the intermediate nodes by setting the `G'
   flag.  See section 6.6.3 for details about actions taken by 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
   not received within NET_TRAVERSAL_TIME milliseconds, the node MAY try
   again to discover a route by broadcasting a RREQ, up to a maximum
   of RREQ_RETRIES times.  Each new attempt MUST increment the RREQ ID
   field.

   Data packets waiting for a route (i.e., waiting for a RREP after a
   RREQ has been sent) SHOULD be buffered.  The buffering SHOULD be
   "first-in, first-out" (FIFO). If a route discovery has been attempted
   RREQ_RETRIES times without receiving any RREP, all data packets
   destined for the corresponding destination SHOULD be dropped from
   the buffer and a Destination Unreachable message delivered to the
   application.


6.4. Controlling Dissemination of Route Request Messages

   To prevent unnecessary network-wide dissemination of RREQs, the
   originating node SHOULD use an expanding ring search technique as
   an optimization.  In an expanding ring search, the originating
   node initially uses a TTL = TTL_START in the RREQ packet IP
   header and sets the timeout for receiving a RREP to 2 * TTL *
   NODE_TRAVERSAL_TIME milliseconds.  If the RREQ times out without a
   corresponding RREP, the originator broadcasts the RREQ again with the
   TTL incremented by TTL_INCREMENT. This continues until the TTL set
   in the RREQ reaches TTL_THRESHOLD, beyond which a TTL = NET_DIAMETER
   is used for each attempt.  Each time, the timeout for receiving a



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

Internet Draft                   AODV                    19 January 2002


   RREP is calculated as before.  Each attempt increments the RREQ ID
   field in the RREQ packet.  The RREQ can be broadcast with TTL =
   NET_DIAMETER up to a maximum of RREQ_RETRIES times.

   When a RREP is received, the Hop Count indicated in the RREP packet
   is stored as the Last Hop Count in the routing table.  When a new
   route to the same destination is required at a later time (e.g., upon
   route loss), the TTL in the RREQ IP header is initially set to this
   Last Hop Count plus TTL_INCREMENT. Thereafter, following each timeout
   the TTL is incremented by TTL_INCREMENT until TTL = TTL_THRESHOLD is
   reached.  Beyond this TTL = NET_DIAMETER is used as before.

   Timeouts MAY be more accurately determined dynamically via
   measurement, instead of using a statically configured value related
   to NODE_TRAVERSAL_TIME. To accomplish this, the RREQ may carry the
   timestamp via an extension field as defined in Section 9.2 to be
   carried back by the RREP packet (again via an extension field).  The
   difference between the current time and this timestamp determines the
   route discovery latency.  The timeout may be set to be a small factor
   times the average of the last few route discovery latencies for the
   concerned destination.  These latencies may be recorded as additional
   fields in the routing table.

   An expired routing table entry SHOULD NOT be expunged before
   (current_time + DELETE_PERIOD) (see section 6.11).  Otherwise, the
   soft state corresponding to the route (e.g., Last Hop Count) will be
   lost.  Furthermore, a longer routing table entry expunge time MAY be
   configured.  Any routing table entry waiting for a RREP SHOULD NOT be
   expunged before (current_time + PATH_TRAVERSAL_TIME).


6.5. Processing and Forwarding Route Requests

   When a node receives a RREQ, it first checks to determine whether it
   has received a RREQ with the same Originator IP Address and RREQ ID
   within at least the last PATH_TRAVERSAL_TIME milliseconds.  If such a
   RREQ has been received, the node silently discards the newly received
   RREQ. The rest of this subsection describes actions taken for RREQs
   that are not discarded.

   The node always creates a reverse route to the Originator IP Address
   in its routing table if one does not already exist.  If a route to
   the Originator IP Address already exists, it is updated only if
   either

      (i)       the Originator Sequence Number in the RREQ is higher
                than the destination sequence number of the Originator
                IP Address in the route table, or




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

Internet Draft                   AODV                    19 January 2002


      (ii)      the sequence numbers are equal, but the hop count as
                specified by the RREQ, plus one, is now smaller than the
                existing hop count in the routing table.

   This reverse route will be needed if the node receives a RREP back
   to the node that originated the RREQ (identified by the Originator
   IP Address).  When the reverse route is created or updated, the
   following actions are carried out:

    1. the Originator Sequence Number from the RREQ is copied to the
       corresponding destination sequence number in the route table
       entry;

    2. the next hop in the routing table becomes the node from which the
       RREQ was received (it is obtained from the source IP address in
       the IP header and is often not equal to the Originator IP Address
       field in the RREQ message);

    3. the hop count is copied from the Hop Count in the RREQ message
       and incremented by one;

   Whenever a RREQ message is received, the Lifetime of the reverse
   route entry for the Originator IP address is set to be the maximum of
   (ExistingLifetime, MinimalLifetime), where

      MinimalLifetime =    (current time + PATH_TRAVERSAL_TIME -
                           2*HopCount*NODE_TRAVERSAL_TIME).

   The node generates a RREP (as discussed further in section 6.6) if
   either:

      (i)       it is itself the destination (see section 6.6.1), or

      (ii)      it has an active route to the destination, and the
                destination sequence number in the node's existing
                route table entry for the destination is greater than
                or equal to the Destination Sequence Number of the
                RREQ (comparison using signed 32-bit arithmetic).  See
                section 6.6.2 for further information about generating
                the RREP in this case.

   When either of these conditions is satisfied, the node does not
   rebroadcast the RREQ.

   Otherwise, if the incoming IP header has TTL larger than 1, the node
   updates and broadcasts the RREQ to address 255.255.255.255 on all of
   its configured interface(s) (see section 6.14).  To update the RREQ,
   the TTL or hop limit field in the outgoing IP header is decreased by




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

Internet Draft                   AODV                    19 January 2002


   one, and the Hop Count field in the RREQ message is incremented by
   one, to account for the new hop through the intermediate node.


6.6. Generating Route Replies

   If a node receives a route request for a destination, and either
   has a fresh enough route to satisfy the request or is itself the
   destination, the node generates a RREP message.  This node copies
   the Destination IP Address and the Originator Sequence Number in
   RREQ message into the corresponding fields in the RREP message.
   Processing is slightly different, depending on whether the node is
   itself the requested destination, or instead if it is an intermediate
   node with an admissible route to the destination.  These scenarios
   are described in the sections below.

   Once created, the RREP is unicast to the next hop toward the
   originator of the RREQ, as indicated by the route table entry for
   that originator.  As the RREP is forwarded back towards the node
   which originated the RREQ message, the Hop Count field is incremented
   by one at each hop.  Thus, when the RREP reaches the originator, the
   Hop Count represents the distance, in hops, of the destination from
   the originator.


6.6.1. Route Reply Generation by the Destination

   If the generating node is the destination itself, it MUST update its
   own sequence number to the maximum of its current sequence number and
   the destination sequence number in the RREQ packet.  The destination