draft-ietf-manet-aodv-10.txt

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

   destinations in the local routing table that use the unreachable
   neighbor as the next hop. 
   
   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.



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


   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 to that destination.  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 entry is invalidated by copying the Hop Count to the Last Hop
       Count field and then making the Hop Count infinity.

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

    3. The Lifetime field is updated to current time plus DELETE_PERIOD.
       Before this time, the entry MUST 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.


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 to originator) +
      LOCAL_ADD_TTL.

   Thus, local repair attempts should never be visible to the
   originating node, and will always have TTL >= MIN_REPAIR_TTL
   + LOCAL_ADD_TTL. The node initiating the repair then waits the



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


   discovery period to receive RREPs in response to the RREQ. If, at
   the end of the discovery period, it has not received a RREP 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 during the
   discovery period, it proceeds as described in Section 6.7, updating
   its route table entry for that destination.  It then compares the hop
   count of the new route with the value in the last hop count 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, as recorded in the last hop count field,
   the node SHOULD create a RERR message for the destination, with the
   'N' bit set.

   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 active 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 originating node after locally repairing the link break
   may allow the originator to find a fresh route to the destination
   that is better, based on current node positions.  However, it
   does not require the originating node to rebuild the route, as the
   originator may be done, or nearly done, with the data session.

   When a link breaks along an active route, there are often multiple
   destinations that become unreachable.  The node that is upstream of
   the broken link tries an immediate local repair for only the one
   destination towards which the data packet was traveling.  Other
   routes using the same link MUST be marked as broken, but the node
   handling the local repair MAY flag each such newly broken route as
   locally repairable; this local repair flag in the route table MUST be
   reset when the route times out (e.g., after the route has been not
   been active for ACTIVE_ROUTE_TIMEOUT). Before the timeout occurs,
   these other routes will be repaired as needed when packets arrive
   for the other destinations.  Alternatively, depending upon local
   congestion, the node MAY begin the process of establishing local




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


   repairs for the other routes, without waiting for new packets to
   arrive.


6.13. Actions After Reboot

   A node participating in the ad hoc network must take certain actions
   after reboot as it might lose all sequence number records for all
   destinations, including its own sequence number.  However, there
   may be neighboring nodes that are using this node as an active next
   hop.  This can potentially create routing loops.  To prevent this
   possibility, each node on reboot waits for DELETE_PERIOD. During
   this time, the node does not transmit any RREP messages.  If the
   node receives a RREQ, RREP, or RERR control packet, it SHOULD create
   route entries as appropriate given the sequence number information
   in the control packets.  If the node receives a data packet for
   some other destination, it MUST broadcast a RERR as described in
   subsection 6.11 and reset the waiting timer to expire after current
   time plus DELETE_PERIOD.

   It can be shown [1] that by the time the rebooted node comes out of
   the waiting phase and becomes an active router again, none of its
   neighbors will be using it as an active next hop any more.  Its own
   sequence number gets updated once it receives a RREQ from any other
   node, as the RREQ always carries the maximum destination sequence
   number seen en route.


6.14. Interfaces

   Because AODV should operate smoothly over wired, as well as wireless,
   networks, and because it is likely that AODV will also be used with
   multi-homed radios, the interface over which packets arrive must
   be known to AODV whenever a packet is received.  This includes the
   reception of RREQ, RREP, and RERR messages.  Whenever a packet is
   received from a new neighbor, the interface on which that packet was
   received is recorded into the route table entry for that neighbor,
   along with all the other appropriate routing information.  Similarly,
   whenever a route to a new destination is learned, the interface
   through which the destination can be reached is also recorded into
   the destination's route table entry.

   When multiple interfaces are available, a node retransmitting a RREQ
   message rebroadcasts that message on all interfaces that have been
   configured for operation in the ad-hoc network, except those on which
   it is known that all of the nodes neighbors have already received
   the RREQ For instance, for some broadcast media (e.g., Ethernet) it
   may be presumed that all nodes on the same link receive a brodacast
   message at the same time.  When a node needs to transmit a RERR, it



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


   should only transmit it on those interfaces that have precursor nodes
   for that route.


7. AODV and Aggregated Networks

   AODV has been designed for use by mobile nodes with IP addresses
   that are not necessarily related to each other, to create an ad hoc
   network.  However, in some cases a collection of mobile nodes MAY
   operate in a fixed relationship to each other and share a common
   subnet prefix, moving together within an area where an ad hoc network
   has formed.  Call such a collection of nodes a ``subnet''.  In this
   case, it is possible for a single node within the subnet to advertise
   reachability for all other nodes on the subnet, by responding with
   a RREP message to any RREQ message requesting a route to any node
   with the subnet routing prefix.  Call the single node the ``subnet
   router''.  In order for a subnet router to operate the AODV protocol
   for the whole subnet, it has to maintain a destination sequence
   number for the entire subnet.  In any such RREP message sent by the
   subnet router, the Prefix Size field of the RREP message MUST be
   set to the length of the subnet prefix.  Other nodes sharing the
   subnet prefix SHOULD NOT issue RREP messages, and SHOULD forward RREQ
   messages to the subnet leader.


8. Using AODV with Other Networks

   In some configurations, an ad hoc network may be able to provide
   connectivity between external routing domains that do not use AODV.
   If the points of contact to the other networks can act as subnet
   routers (see Section 7) for any relevant networks within the external
   routing domains, then the ad hoc network can maintain connectivity to
   the external routing domains.  Indeed, the external routing networks
   can use the ad hoc network defined by AODV as a transit network.

   In order to provide this feature, a point of contact to an external
   network (call it an Infrastructure Router) has to act as the subnet
   router for every subnet of interest within the external network for
   which the Infrastructure Router can provide reachability.  This
   includes the need for maintaining a destination sequence number for
   that external subnet.

   If multiple Infrastructure Routers offer reachability to the same
   external subnet, those Infrastructure Routers have to cooperate (by
   means outside the scope of this specification) to provide consistent
   AODV semantics for ad hoc access to those subnets.






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


9. Extensions

   RREQ and RREP messages have extensions defined in the following
   format:

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Type      |    Length     |     type-specific data ...
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   where:

      Type     1

      Length   The length of the type-specific data, not including the
               Type and Length fields of the extension.

   Extensions with types between 128 and 255 may NOT be skipped.  The
   rules for extensions will be spelled out more fully, and conform to
   the rules for handling IPv6 options.


9.1. Hello Interval Extension Format

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |     Type      |    Length     |       Hello Interval ...      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   | ... Hello Interval, continued |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      Type     2

      Length   4

      Hello Interval
               The number of milliseconds between successive
               transmissions of a Hello message.

   The Hello Interval extension MAY be a