4. Applicability Statement

The AODVv2 routing protocol is a reactive routing protocol designed for stub (i.e., non-transit) or disconnected (i.e., from the Internet) mobile ad hoc networks (MANETs). AODVv2 handles a wide variety of mobility patterns by determining routes on-demand. AODVv2 also handles a wide variety of traffic patterns. In networks with a large number of routers, AODVv2 is best suited for relatively sparse traffic scenarios where any particular router forwards packets to only a small percentage of the AODVv2 routers in the network, due to the on-demand nature of route discovery and route maintenance. AODVv2 supports routers with multiple interfaces, as long as each interface has its own (unicast routeable) IP address; the set of all network interfaces supporting AODVv2 is administratively configured in a list (namely, AODVv2_INTERFACES).

Although AODVv2 is closely related to AODV [RFC3561], and shares some features of DSR [RFC4728], AODVv2 is not interoperable with either of those other two protocols.

AODVv2 is applicable to memory constrained devices, since only a little routing state is maintained in each AODVv2 router. Routes that are not needed for forwarding data do not have to be maintained, in contrast to proactive routing protocols that require routing information to all routers within the MANET be maintained.

In addition to routing for its own local applications, each AODVv2 router can also route on behalf of other non-routing nodes (in this document, "Router Clients"), reachable via Client Interfaces. Each AODVv2 router, if serving router clients other than itself, SHOULD be configured with information about the IP addresses of its clients, using any suitable method. In the initial state, no AODVv2 router is required to have information about the relationship between any other AODVv2 router and its Router Clients (see Section 6.3).

The coordination among multiple AODVv2 routers to distribute routing information correctly for a shared address (i.e. an address that is advertised and can be reached via multiple AODVv2 routers) is not described in this document. The AODVv2 router operation of shifting responsibility for a routing client from one AODVv2 router to another is described in Appendix H. Address assignment procedures are entirely out of scope for AODVv2. A Router Client SHOULD NOT be served by more than one AODVv2 router at any one time.

AODVv2 routers perform route discovery to find a route toward a particular destination. AODVv2 routers MUST must be configured to respond to RREQs for themselves and their clients. When AODVv2 is the only protocol interacting with the forwarding table, AODVv2 MAY be configured to perform route discovery for all unknown unicast destinations.

AODVv2 only supports bidirectional links. In the case of possible unidirectional links, blacklists (see Section 6.2) SHOULD be used, or other means (e.g. adjacency establishment with only neighboring routers that have bidirectional communication as indicated by NHDP [RFC6130]) of assuring and monitoring bi-directionality are recommended. Otherwise, persistent packet loss or persistent protocol failures could occur. The cost of bidirectional link L (denoted Cost(L)) may depend upon the direction across the link for which the cost is measured. If received over a link that is unidirectional, metric information from incoming AODVv2 messages MUST NOT be used for route table updates.

The routing algorithm in AODVv2 may be operated at layers other than the network layer, using layer-appropriate addresses. The routing algorithm makes use of some persistent state; if there is no persistent storage available for this state, recovery can impose a performance penalty (e.g., in case of AODVv2 router reboots).

5. AODVv2 Message Transmission

In its default mode of operation, AODVv2 sends messages using the parameters for port number and IP protocol specified in [RFC5498]. By default, AODVv2 messages are sent with the IP destination address set to the link-local multicast address LL-MANET-Routers [RFC5498] unless otherwise specified. Therefore, all AODVv2 routers MUST subscribe to LL-MANET-Routers [RFC5498] to receive AODVv2 messages. In order to reduce multicast overhead, regenerated multicast packets in MANETs SHOULD be done according to methods specified in [RFC6621]. AODVv2 does not specify which method should be used to restrict the set of AODVv2 routers that have the responsibility to regenerate multicast packets. Note that multicast packets MAY be sent via unicast. For example, this may occur for certain link-types (non-broadcast media), for manually configured router adjacencies, or in order to improve robustness.

The IPv4 TTL (IPv6 Hop Limit) field for all packets containing AODVv2 messages is set to 255. If a packet is received with a value other than 255, any AODVv2 message contained in the packet MUST be disregarded by AODVv2. This mechanism, known as "The Generalized TTL Security Mechanism" (GTSM) [RFC5082] helps to assure that packets have not traversed any intermediate routers.

IP packets containing AODVv2 protocol messages SHOULD be given priority queuing and channel access.

6. Data Structures

6.1. Route Table Entry

The route table entry is a conceptual data structure. Implementations MAY use any internal representation so long as it provides access to the information specified below.

A route table entry has the following fields:

Route.Address

An address or address prefix of a node

Route.PrefixLength

The length of the address or prefix. If the value of Route.PrefixLength is less than the length of addresses in the address family used by the AODVv2 routers, the associated address is a routing prefix, rather than an address. A PrefixLength is stored for every route in the route table.

Route.SeqNum

The Sequence Number associated with Route.Address, as obtained from the last packet that successfully updated this route table entry.

Route.NextHopAddress

The IP address of the adjacent AODVv2 router used for the path toward the Route.Address

Route.NextHopInterface

The interface used to send packets toward Route.Address

Route.LastUsed

The time that this route was last used

Route.ExpirationTime

The time at which this route must expire

Route.MetricType

The type of the metric for the route towards Route.Address

Route.Metric

The cost of the route towards Route.Address expressed in units consistent with Route.MetricType

Route.State

The last *known* state of the route. Route.State is one of the following: Active, Idle, Expired, or Broken.

Route.Timed

The Route.Timed flag is true if the route was specified to have a specific lifetime for use.

Route.Precursors (optional)

A list of upstream nodes using the route.

A route table entry (i.e., a route) is in one of the following states:

Active

An Active route is in current use for forwarding packets. An Active route is maintained continuously by AODVv2 and is considered to remain active as long as it is used at least once during every ACTIVE_INTERVAL, or if the Route.Timed flag is true. When a route that is not a timed route is no longer active the route becomes an Idle route.

Idle

An Idle route can be used for forwarding packets, even though it is not in current use. If an Idle route is used to forward a packet, it becomes an Active route once again. After an Idle route remains idle for MAX_IDLETIME, it becomes an Expired route.

Expired

After a route has been idle for too long, it expires, and may no longer be used for forwarding packets. An Expired route is not used for forwarding, but the sequence number information can be maintained until the destination sequence number has had no updates for MAX_SEQNUM_LIFETIME; after that time, old sequence number information is considered no longer valuable and the Expired route MUST BE expunged.

Broken

A route marked as Broken cannot be used for forwarding packets but still has valid destination sequence number information. When the link to a route's next hop is broken, the route is marked as being Broken, and afterwards the route MAY NOT be used.

Timed

The expiration of a Timed route is controlled by the Route.ExpirationTime time of the route table entry (instead of MAX_IDLETIME). Until that time, a Timed route can be used for forwarding packets. A route is indicated to be a Timed route by the setting of the Route.Timed flag in the route table entry. Afterwards, the route MAY be expunged; otherwise the route must be must be marked as Expired.

MAX_SEQNUM_LIFETIME is the time after a reboot during which an AODVv2 router MUST NOT transmit any routing messages. Thus, if all other AODVv2 routers expunge routes to the rebooted router after that time interval, the rebooted AODVv2 router's sequence number will not be considered stale by any other AODVv2 router in the MANET.

6.2. Bidirectional Connectivity and Blacklists

To avoid repeated failure of Route Discovery, an AODVv2 router (HandlingRtr) handling a RREP message MUST attempt to verify connectivity towards RREQ_Gen. This MAY be done by including the Acknowledgement Request (AckReq) data element in the RREP. In reply to an AckReq, an RREP_ACK message message MUST be sent. If the verification is not received within UNICAST_MESSAGE_SENT_TIMEOUT, HandlingRtr MUST put the upstream neighbor in the blacklist. RREQs received from a blacklisted router, or any router over a link that is known to be incoming-only, MUST NOT be regenerated by HandlingRtr. However, the upstream neighbor SHOULD NOT be permanently blacklisted; after a certain time (MAX_BLACKLIST_TIME), it SHOULD once again be considered as a viable upstream neighbor for route discovery operations.

For this purpose, a list of blacklisted routers along with their time of removal SHOULD be maintained:

Blacklist.Router

An IP address of the router that did not verify bidirectional connectivity.

Blacklist.RemoveTime

The time at which Blacklist.Router MAY be removed from the blacklist.

6.3. Router Clients and Client Networks

An AODVv2 router may offer routing services to other nodes that are not AODVv2 routers; such nodes are defined as Router Clients in this document.

For this purpose, CLIENT_ADDRESSES must be configured on each AODVv2 router with the following information:

Client IP address

The IP address of the node that requires routing service from the AODVv2 router.

Client Prefix Length

The length of the routing prefix associated with the client IP address.

If the Client Prefix Length is not the full length of the Client IP address, then the prefix defines a Client Network. If an AODVv2 router is configured to serve a Client Network, then the AODVv2 router MUST serve every node that has an address within the range defined by the routing prefix of the Client Network. The list of Routing Clients for an AODVv2 router is never empty, since an AODVv2 router is always its own client as well.

6.4. Sequence Numbers

Sequence Numbers allow AODVv2 routers to evaluate the freshness of routing information. Each AODVv2 router in the network MUST maintain its own sequence number. Each RREQ and RREP generated by an AODVv2 router includes that sequence number. Each AODVv2 router MUST make sure that its sequence number is unique and monotonically increasing. This can be achieved by incrementing it with every RREQ or RREP it generates.

Every router receiving a RREQ or RREP can thus use the Sequence Number of a RREQ or RREP as information concerning the freshness of the packet's route update: if the new packet's Sequence Number is lower than the one already stored in the route table, its information is considered stale.

As a consequence, loop freedom is assured.

If the router has multiple network interfaces, it can use the same SeqNum for the IP addresses of all of them, or it can assign different SeqNums for use with different IP addresses. However, the router MUST NOT use multiple SeqNums for any particular IP address. A Router Client has the same SeqNum as the IP address of the network interface that the AODVv2 router uses to forward packets to that Router Client. Similarly, a route to a subnet has the same SeqNum as the IP address of the network interface that the AODVv2 router uses to forward packets to that subnet. The Sequence Number guarantees the temporal order of routing information to maintain loop-free routes, and fulfills the same role as the "Destination Sequence Number" of DSDV [Perkins94], and as the AODV Sequence Number in RFC 3561[RFC3561].

An AODVv2 router increments its SeqNum as follows. Most of the time, SeqNum is incremented by simply adding one (1). But when the SeqNum has the value of the largest possible number representable as a 16-bit unsigned integer (i.e., 65,535), it MUST be incremented by setting to one (1). In other words, the sequence number after 65,535 is 1.

An AODVv2 router SHOULD maintain its SeqNum in persistent storage. If an AODVv2 router's SeqNum is lost, it MUST take the following actions to avoid the danger of routing loops. First, the AODVv2 router MUST set Route.State = Broken for each entry. Furthermore the AODVv2 router MUST wait for at least MAX_SEQNUM_LIFETIME before transmitting or regenerating any AODVv2 RREQ or RREP messages. If an AODVv2 protocol message is received during this waiting period, the AODVv2 router SHOULD perform normal route table entry updates, but not forward the message to other nodes. If a data packet is received for forwarding to another destination during this waiting period, the AODVv2 router MUST transmit a RERR message indicating that no route is available. At the end of the waiting period the AODVv2 router sets its SeqNum to one (1) and begins performing AODVv2 protocol operations again.

6.5. Metrics

Metrics describe the quality of a route or a link. They can take various aspects into account, such as latency, delay, financial, energy, etc. Whenever an AODV router receives metric information in an incoming message, the value of the metric is as measured by the transmitting router, and does not reflect the cost of traversing the incoming link.

Each routing table entry is associated with metric information. When presented with information which may update a route, deciding whether to use the information involves evaluating the metric. For some metrics, a maximum value is defined, namely MAX_METRIC[i] where 'i' is the Metric Type. AODVv2 does not store routes in its route table that cost more than MAX_METRIC[i].

Each metric has to have a Metric Type, and the Metric Type is allocated by IANA as specified in [RFC6551]. Apart from its default metric type, which is detailed in Section 6.5.3, AODVv2 enables the use of generic metrics, whose data type depends on the metric used. The Metric Type is specified by the MetricType TLV of each RteMsg. As a natural result of the way routes are looked up according to conformant metric type, all intermediate routers handling a RteMsg will assign the same metric type to all metric information in the RteMsg.

6.5.1. The Cost() function

In order to simplify the description of storing accumulated route costs in the route table, a Cost() function is defined. This function returns the Cost of traversing a Route ('Cost(R)') or a Link ('Cost(L)'). The specification of Cost(L) for metric types other than DEFAULT_METRIC_TYPE is beyond the scope of this document.

6.5.2. The LoopFree() function

Since determining loop freedom is known to depend on comparing the Cost(R) of route update information to the Cost(R) of an existing stored route using the same metric, AODVv2 must also be able to invoke an abstract routine which in this document is called "LoopFree(R1, R2)". LoopFree(R1, R2) returns TRUE when, (under the assumption of nondecreasing SeqNum during Route Discovery) given that R2 is loop-free and Cost(R2) is the cost of route R2, Cost(R1) is known to guarantee loop freedom of the route R1. In this document, an AODVv2 router will only invoke LoopFree (AdvRte, Route), for routes AdvRte and Route which use the same metric to the same destination. AdvRte is the route advertised in an incoming RREQ or RREP, and is used as parameter R1 for LoopFree. Route is a route already existing in the AODVv2 router's route table, and is used as parameter R2 for LoopFree.

6.5.3. Default Metric type

HopCount is still the default metric for use in MANETs, notwithstanding the above objections. Therefore, the default Metric Type DEFAULT_METRIC_TYPE is Hop Count. It is also the only metric described in detail by this protocol. With this metric, Cost(L) is always 1, and Cost(R) is simply the hop count between the router and the destination.

MAX_METRIC[DEFAULT_METRIC_TYPE] is defined to be MAX_HOPCOUNT. MAX_HOPCOUNT MUST be larger than the AODVv2 network diameter. Otherwise, AODVv2 protocol messages may not reach their intended destinations.

Using Metric Type DEFAULT_METRIC_TYPE, LoopFree (AdvRte, Route) is TRUE when Cost(AdvRte) ≤ Cost(Route). The specification of Cost(R) and LoopFree(AdvRte, Route) for metric types other than DEFAULT_METRIC_TYPE is beyond the scope of this document.

6.5.4. Alternate Metrics

Some applications may require metric information other than Hop Count, which has traditionally been the default metric associated with routes in MANET. It is well known that reliance on Hop Count can cause selection of the worst possible route in many situations. For this reason, it is important to enable route selection based on metric information other than Hop Count -- in other words, based on "alternate metrics".

The range and data type of each such alternate metric may be different. For instance, the data type might be integers, or floating point numbers, or restricted subsets thereof. It is out of the scope of this document to specify for alternate metrics the Cost(L) and Cost(R) functions, or their return type.

6.6. RREQ Table: Received RREQ Messages

Two incoming RREQ messages are considered to be "comparable" if they were generated by the same AODVv2 router in order to discover a route for the same destination with the same metric type. According to that notion of comparability, when RREQ messages are flooded in a MANET, an AODVv2 router may well receive comparable RREQ messages from more than one of its neighbors. A router, after receiving an RREQ message, MUST check against previous RREQs to assure that its response message would contain information that is not redundant (see Section 8.6 regarding suppression of redundant RREQ messages). Otherwise, multicast RREQs are likely to be regenerated again and again with almost no additional benefit, but generating a great deal of unnecessary signaling traffic and interference.

To avoid transmission of redundant RREQ messages, while still enabling the proper handling of earlier RREQ messages that may have somehow been delayed in the network, it is needed for each AODVv2 router to keep a list of the certain information about RREQ messages which it has recently received.

This list is called the AODVv2 Received RREQ Table -- or, more briefly, the RREQ Table. Two AODVv2 RREQ messages are comparable if:

• they have the same metric type
• they have the same OrigAddr and TargAddr

Each entry in the RREQ Table has the following fields:

• OrigAddr
• TargAddr
• OrigNode Sequence Number
• TargNode Sequence Number (if present in RREQ)
• Metric Type
• Metric
• Timestamp

The RREQ Table is maintained so that no two entries in the RREQ Table are comparable -- that is, all RREQs represented in the RREQ Table either have a different OrigAddr, different TargAddr, or different metric types. If two RREQs have the same metric type, OrigAddr, and TargAddr, the information from the one with the older Sequence Number is not needed in the table; in case they have the same Sequence Number, the one with the greater Metric value is not needed; in case they have the same Metric as well, it does not matter which table entry is maintained. Whenever a RREQ Table entry is updated, its Timestamp field should also be updated to reflect the Current_Time.

When optional multicast RREP (see Section 14.4) is used to enable selection from among multiple possible return routes, an AODVv2 router can eliminate redundant RREP messages using the analogous mechanism along with a RREP Table. The description in this section only refers to RREQ multicast messages.

Protocol handling of RERR messages eliminates the need for tracking RERR messages, since the rules for RERR regeneration prevent the phenomenon of redundant retansmission that affects RREQ and RREP multicast.

7. AODVv2 Operations on Route Table Entries

In this section, operations are specified for updating the route table due to timeouts and route updates within AODVv2 messages. Route update information in AODVv2 messages includes IP addresses, along with the SeqNum and prefix length associated with each IP address, and including the Metric measured from the node transmitting the AODVv2 message to the IP address in the route update. A RREQ message advertises a route to OrigAddr, and a RREP message analogously advertises a route to TargAddr. In this section, RteMsg is either RREQ or RREP, and AdvRte is the route advertised by the RteMsg. All SeqNum comparisons use signed 16-bit arithmetic.

7.1. Evaluating Incoming Routing Information

If the incoming RteMsg does not have a Metric Type data element, then the metric information contained by AdvRte is considered to be of type DEFAULT_METRIC_TYPE -- in other words, 3 (for HopCount) unless changed by administrative action. The AODVv2 router (HandlingRtr) checks the advertised route (AdvRte) to see whether the AdvRte should be used to update an existing route table entry. HandlingRtr searches its route table to see if there is a route table entry with the same Metric Type as the AdvRte, matching AdvRte.Address. If not, HandlingRtr creates a route table entry for AdvRte.Address as described in Section 7.2. Otherwise, HandlingRtr compares the incoming routing information for AdvRte against the already stored routing information in the route table entry (Route) for AdvRte.Address, as described next.

   (AdvRte.SeqNum > Route.SeqNum) OR
       ((AdvRte.SeqNum == Route.SeqNum) AND
                [(AdvRte.Cost < Route.Metric) OR
                 ((Route.State == Broken) && LoopFree (AdvRte, Route))])
     

Route[AdvRte.Address] uses the same metric type as the incoming routing information, and the route entry contains Route.SeqNum, Route.Metric, and Route.State. Define AdvRte.SeqNum and AdvRte.Metric to be the corresponding routing information for Route.Address in the incoming RteMsg. Define AdvRte.Cost to be (AdvRte.Metric + Cost(L)), where L is the link from which the incoming message was received. The incoming routing information is classified as follows:

1. Stale::

AdvRte.SeqNum < Route.SeqNum :
If AdvRte.SeqNum < Route.SeqNum the incoming information is stale. Using stale routing information is not allowed, since that might result in routing loops. In this case, HandlingRtr MUST NOT update the route table entry using the routing information for AdvRte.Address.

2. Unsafe against loops::

(TRUE != LoopFree (AdvRte, Route)) :
If AdvRte is not Stale (as in (1) above), AdvRte.Cost is next considered to insure loop freedom. If (TRUE != LoopFree (AdvRte, Route)) (see Section 6.5), then the incoming AdvRte information is not guaranteed to prevent routing loops, and it MUST NOT be used to update any route table entry.

3. More costly::

(AdvRte.Cost >= Route.Metric) && (Route.State != Broken)
When AdvRte.SeqNum is the same as in a valid route table entry, and LoopFree (AdvRte, Route) assures loop freedom, incoming information still does not offer any improvement over the existing route table information if AdvRte.Cost ≥ Route.Metric. Using such incoming routing information to update a route table entry is not recommended.

4. Offers improvement::

Advertised routing information that does not match any of the above criteria is better than existing route table information and SHOULD be used to improve the route table. The following pseudo-code illustrates whether advertised routing information should be used to update an existing route table entry as described in Section 7.2.

• it is more recent, or
• it is not stale and is less costly, or
• it can safely repair a broken route.

7.2. Applying Route Updates To Route Table Entries

To apply the route update, a route table entry for AdvRte.Address is either found to already exist in the route table, or else a new route table entry for AdvRte.Address is created and inserted into the route table. If the route table entry already exists, and the state is Expired or Broken, then the state is reset to be Idle. If the route table entry had to be created, the state is set to be Active. The route table entry is populated with the following information:

• If AdvRte.PrefixLength exists, then Route.PrefixLength := AdvRte.PrefixLength. Otherwise, Route.PrefixLength := maximum length for address family (either 32 or 128).
• Route.SeqNum := AdvRte.SeqNum
• Route.NextHopAddress := IP.SourceAddress (i.e., an address of the node from which the RteMsg was received)
• Route.NextHopInterface is set to the interface on which RteMsg was received
• Route.MetricType := AdvRte.MetricType
• Route.Metric := AdvRte.Cost
• Route.LastUsed := Current_Time
• If RteMsg.VALIDITY_TIME is included, then
  Route.Timed := TRUE and Route.ExpirationTime := Current_Time + RteMsg.VALIDITY_TIME. Otherwise, Route.ExpirationTime := Current_Time + (ACTIVE_INTERVAL + MAX_IDLETIME).

With these assignments to the route table entry, a route has been made available, and the route can be used to send any buffered data packets and subsequently to forward any incoming data packets for Route.Address. An updated route entry also fulfills any outstanding route discovery (RREQ) attempts for Route.Address.

7.3. Route Table Entry Timeouts

During normal operation, AODVv2 does not require any explicit timeouts to manage the lifetime of a route. However, the route table entry MUST be examined before using it to forward a packet, as discussed in Section 9.1. Any required expiry or deletion can occur at that time. Alternatively, timers and timeouts MAY be implemented to achieve the same effect.

At any time, the route table can be examined and route table entries can be expunged according to their current state at the time of examination, as follows. Section 14.3) then the precursor lists must also be expunged at the same time that the route itself is expunged.

• An Active route MUST NOT be expunged.
• An Idle route SHOULD NOT be expunged.
• An Expired route MAY be expunged (least recently used first).
• A route MUST be expunged if (Current_Time - Route.LastUsed) >= MAX_SEQNUM_LIFETIME.
• A route MUST be expunged if Current_Time >= Route.ExpirationTime

If precursor lists are maintained for the route (as described in

8. Routing Messages RREQ and RREP (RteMsgs)

AODVv2 message types RREQ and RREP are together known as Routing Messages (RteMsgs) and are used to discover a route between an Originating and Target Addr, denoted by OrigAddr and TargAddr. The constructed route is bidirectional, enabling packets to flow between OrigAddr and TargAddr. RREQ and RREP have similar information and function, but have some differences in their rules for handling. When a node receives a RREQ or a RREP, the node then creates or updates a route to the OrigAddr or the TargAddr respectively. The main difference between the two messages is that RREQ messages are typically multicast to solicit a RREP, whereas RREP is typically unicast as a response to RREQ.

When an AODVv2 router needs to forward a data packet from a node (with IP address OrigAddr) in its set of router clients, and it does not have a forwarding route toward the packet's IP destination address (TargAddr), the AODVv2 router (RREQ_Gen) generates a RREQ (as described in Section 8.3) to discover a route toward TargAddr. Subsequently RREQ_Gen awaits reception of an RREP message (see Section 8.4) or other route table update (see Section 7.2) to establish a route toward TargAddr. The RREQ message contains routing information to enable RREQ recipients to route packets back to OrigAddr, and the RREP message contains routing information enabling RREP recipients to route packets to TargAddr.

8.1. Route Discovery Retries and Buffering

After issuing a RREQ, as described above RREQ_Gen awaits a RREP providing a bidirectional route toward the Target Address. If the RREP is not received within RREQ_WAIT_TIME, RREQ_Gen MAY retry the Route Discovery by generating another RREQ. Route Discovery SHOULD be considered to have failed after DISCOVERY_ATTEMPTS_MAX and the corresponding wait time for a RREP response to the final RREQ. After the attempted Route Discovery has failed, RREQ_Gen MUST wait at least RREQ_HOLDDOWN_TIME before attempting another Route Discovery to the same destination.

To reduce congestion in a network, repeated attempts at route discovery for a particular Target Address SHOULD utilize a binary exponential backoff.

Data packets awaiting a route SHOULD be buffered by RREQ_Gen. This buffer SHOULD have a fixed limited size (BUFFER_SIZE_PACKETS or BUFFER_SIZE_BYTES). Determining which packets to discard first is a matter of policy at each AODVv2 router; in the absence of policy constraints, by default older data packets SHOULD be discarded first. Buffering of data packets can have both positive and negative effects (albeit usually positive). Nodes without sufficient memory available for buffering SHOULD be configured to disable buffering by configuring BUFFER_SIZE_PACKETS == 0 and BUFFER_SIZE_BYTES == 0. Doing so will affect the latency required for launching TCP applications to new destinations.

If a route discovery attempt has failed (i.e., DISCOVERY_ATTEMPTS_MAX attempts have been made without receiving a RREP) to find a route toward the Target Address, any data packets buffered for the corresponding Target Address MUST BE dropped and a Destination Unreachable ICMP message (Type 3) SHOULD be delivered to the source of the data packet. The code for the ICMP message is 1 (Host unreachable error). If RREQ_Gen is not the source (OrigNode), then the ICMP is sent to OrigAddr.

8.2. RteMsg Structure

RteMsgs have the following general format:

    +---------------------------------------------------------------+
    |                  msg_hop_limit, msg_hop_count                 |
    +---------------------------------------------------------------+
    |                      AckReq, MetricType                       |
    +---------------------------------------------------------------+
    |               AddressList := {OrigAddr,TargAddr}              |
    +---------------------------------------------------------------+
    |         Address Prefix Length for OrigAddr OR TargAddr        |
    +---------------------------------------------------------------+
    |           SeqNumList (OrigSeqNum AND/OR TargSeqNum)           |
    +---------------------------------------------------------------+
    |         MetricList (Metric for OrigAddr OR TargAddr)         |
    +---------------------------------------------------------------+

    +---------------------------------------------------------------+
    |                  msg_hop_limit, msg_hop_count                 |
    +---------------------------------------------------------------+
    |                     PktSource, MetricType                     |
    +---------------------------------------------------------------+
    |                   Unreachable Address List                    |
    +---------------------------------------------------------------+
    |             Unreachable Address PrefixLength List             |
    +---------------------------------------------------------------+
    |            Unreachable Address Sequence Number List           |
    +---------------------------------------------------------------+

     /-------------------------\
    / +----------------+        \
   /  |  AODVv2 Router |         \
   |  |  191.0.2.2/32  |         |
   |  +----------------+         |            Routable
   |                       +-----+--------+   Prefix
   |                       |   Internet   |  /191.0.2/24
   |                       | AODVv2 Router| /
   |                       |  191.0.2.1   |/      /---------------\
   |                       | serving net  +------+    Internet     \
   |                       |  191.0.2/24  |      \                 /
   |                       +-----+--------+       \---------------/
   |         +----------------+  |
   |         |  AODVv2 Router |  |
   |         |  191.0.2.3/32  |  |
   \         +----------------+  /
    \                           /
     \-------------------------/

    /* Compare incoming route information to current route, maybe use */
    Process_Routing_Info (dest, seq#, metric_type, metric,
                                                       last_hop_metric)
      /* last_hop_metric: either Cost(inRREQ.netif) or (inRREP.netif) */
    {
  new_metric := metric + last_hop_metric;
  rte := Fetch_Route_Table_Entry (dest, seq#, metric_type);
  if (NULL == rte) {
      rte := Create_Route_Table_Entry
        (dest, seq#, metric_type, new_metric);
  } else if (seq# > rte.seq#) { /* stale rte route entry */
      Update_Route_Table_Entry (rte, seq#, metric_type, new_metric);
  } else if (seq# < rte.seq#) { /* stale incoming route infor */
      return(NULL);
  } else if (rte.state == broken) {  /* when (seq# == rte.seq#) */
      Update_Route_Table_Entry (rte, seq#, metric_type, new_metric);
  } else if (rte.metric > (new_metric) { /* and (seq# == rte.seq#) */
      Update_Route_Table_Entry (rte, seq#, metric_type, new_metric);
  } else {  /* incoming route information is not useful */
      return(NULL);
  }
  return (rte);
    }

    Generate_RREQ {
  /* Marshall parameters */
  outRREQ.origIP := IP address used by application
  outRREQ.origSeq := originating router's sequence #
  outRREQ.metType := (if included) metric type needed by application
  outRREQ.origMet := 0 (default) or MIN_METRIC(Metric_type)
  outRREQ.targIP := target IP address
  outRREQ.targSeq := target sequence # /* if known from route table */
  outRREQ.hopLim := msg-hop-limit   /* RFC 5444 */

  /* build RFC 5444 message header fields */
  {
    msg-type=RREQ (message is of type RREQ)
    MF=4 (Message Flags = 4 [only msg-hop-limit field is present])
    MAL=3 or 15 (Message Address Length [3 for IPv4, 15 for IPv6])
    msg-size=NN (octets -- counting MsgHdr, AddrBlk, and AddrTLVs)
    msg-hop-limit := MAX_HOPCOUNT
    if (Metric_type == DEFAULT) {
      msg.tlvs-length=0
    } else { /* Metric_type != HopCount */
      /* Build Metric_type Message TLV */
    }
  }

  /* build AddrBlk */
  num-addr := 2
  AddrBlk := {outRREQ.origIP and outRREQ.targIP addresses}

  /* Include each available Sequence Number in appropriate AddrTLV */
    /* put outRREQ.origSeq in OrigSeqNum AddrTLV */
    if (NULL != targSeq) {
      /* put outRREQ.targSeq in TargSeqNum AddrTLV */
    }

  /* Build Metric AddrTLV containing OrigAddr metric */
    /* use MIN_METRIC(metric type) [==0 for default metric type */
    }

    Receive_RREQ (inRREQ) {
  /* Extract inRREQ values */
  origRTE = Process_Routing_Info (inRREQ.origIP, inRREQ.origSeq, ...)
  if (inRREQ.targIP belongs to me or my client subnet) {
    Generate_RREP()
  } else if (inRREQ present in RREQ_table) {
    return;   /* don't regenerate RREQ... */
  } else if (inRREQ.nbrIP not present in blacklist) {
    Regenerate_RREQ(origRTE, inRREQ)
  } else if (blacklist_expiration_time > current_time) {
    return;   /* don't regenerate RREQ... */
  } else {
    Remove nbrIP from blacklist;
    Regenerate_RREQ(origRTE, inRREQ)
  }
    }

    Regenerate_RREQ (origRTE, inRREQ) { /* called from receive_RREQ() */
  outRREQ.hopLim := inRREQ.hopLim - 1
  if (outRREQ.hopLim == 0) {  /* don't regenerate */
    return()
  }
  /* Marshall parameters */
  outRREQ.origIP := origRTE.origIP
  outRREQ.origSeq := origRTE.origSeq
  outRREQ.origMet := origRTE.origMet
  outRREQ.metType := origRTE.metType
  outRREQ.targIP := inRREQ.targIP
  outRREQ.targSeq := inRREQ.targSeq /* if present */

  /* build RFC 5444 message header fields */
  {
    msg-type=RREQ (message is of type RREQ)
    MF=4 (Message Flags = 4 [only msg-hop-limit field is present])
    MAL=3 or 15 (Message Address Length [3 for IPv4, 15 for IPv6])
    msg-size=NN (octets -- counting MsgHdr, AddrBlk, and AddrTLVs)
    msg-hop-limit := MAX_METRIC(Metric Type) (default, MAX_HOPCOUNT)
    if (Metric_type == DEFAULT) {
      msg.tlvs-length=0
    } else { /* Metric_type != HopCount */
      /* Build Metric_type Message TLV */
    }
  }

  /* build AddrBlk */
  num-addr := 2
  AddrBlk := {outRREQ.origIP and outRREQ.targIP addresses}

  /* Include each available Sequence Number in its proper AddrTLV */
  /* put outRREQ.origSeq in OrigSeqNum AddrTLV */
  if (NULL != targSeq) {
    /* put outRREQ.targSeq in TargSeqNum AddrTLV */
  }

  /* Build Metric AddrTLV to contain outRREQ.origMet */

    }

    Generate_RREP {
  /* Marshall parameters */
  outRREP.origIP := origRTE.origIP
  metric_type := origRTE.metType  /* if not default */
  if (DEFAULT != metric_type)
    outRREP.metType := metric_type
  outRREP.targIP := inRREQ.targIP
  outRREP.targMet := MIN_METRIC(outRREP.metType) (0  by default)
  my_sequence_# := (1 + my_sequence_#) /* from nonvolatile storage */
  outRREP.targSeq := my_sequence_#

  /* build RFC 5444 message header fields */
  {
    msg-type=RREP
    MF=4 (Message Flags = 4 [only msg-hop-limit field is present])
    MAL=3 or 15 (Message Address Length [3 for IPv4, 15 for IPv6])
    msg-size=NN (octets -- counting MsgHdr, AddrBlk, and AddrTLVs)
    msg-hop-limit := MAX_HOPCOUNT
    /* Include the AckReq TLV when:
       - previous RREP does not seem to enable any data flow, OR
       - when RREQ is received from same OrigAddr after RREP was
         unicast to targRTE.nextHop
     */
    if (DEFAULT != metric_type) {
      msg.tlvs-length=0
    } else { /* Metric_type != HopCount */
      /* Build Metric_type Message TLV */
    }
  }

  /* build AddrBlk */
  num-addr := 2
  AddrBlk := {outRREQ.origIP and outRREQ.targIP addresses}

  /* put outRREP.TargSeq in TargSeqNum AddrTLV */

  /* Build Metric AddrTLV containing TargAddr metric */
  /* use MIN_METRIC(origRTE.metType) */
    }

    Receive_RREP (inRREP)
    {
  If (RREP includes AckReq data element) {
    Generate_RREP_Ack()
  }
  /* Extract inRREP values */
  targRTE := Process_Routing_Info (inRREP.targIP, inRREP.targSeq, ...)
  if (inRREP.targIP belongs to me, a client, or a client subnet) {
    Consume_RREP(inRREP)
  } else {
    Regenerate_RREP(targRTE, inRREP)
  }
    }

    Regenerate_RREP(targRTE, inRREP) {
  outRREP.hopLim := inRREP.hopLim - 1
  if (outRREP.hopLim == 0) {  /* don't regenerate */
    return()
  }
  /* Marshall parameters */
  outRREP.targIP := targRTE.targIP
  outRREP.targSeq := targRTE.targSeq
  outRREP.targMet := targRTE.targMet
  metric_type := origRTE.metType  /* if not default */
  if (DEFAULT != metric_type)
    outRREP.metType := metric_type
  outRREP.origIP := inRREP.origIP
  outRREP.nextHop := targRTE.nextHop

  /* build RFC 5444 message header fields */
  {
    msg-type=RREP (message is of type RREP)
    MF=4 (Message Flags = 4 [only msg-hop-limit field is present])
    MAL=3 or 15 (Message Address Length [3 for IPv4, 15 for IPv6])
    msg-size=NN (octets -- counting MsgHdr, AddrBlk, and AddrTLVs)
    /* Include the AckReq data element when:
       - previous RREP does not seem to enable any data flow, OR
       - when RREQ is received from same OrigAddr after RREP was
         unicast to targRTE.nextHop
     */
    msg-hop-limit := outRREP.hopLim;
    if (metric_type == DEFAULT) {
      msg.tlvs-length=0
    } else { /* Metric_type != HopCount */
      /* Build Metric_type Message TLV */
    }
  }

  /* build AddrBlk */
  num-addr := 2
  AddrBlk := {outRREQ.origIP and outRREQ.targIP addresses}

  /* put outRREP.targSeq in TargSeqNum AddrTLV */

  /* Build Metric AddrTLV containing TargAddr metric */
    }

  /* executed by RREQ_Gen */
  /* TargAddr route table entry was updated by Receive_RREP() */
  Consume_RREP() {
    /* Transmit buffered packet(s) (if any) to TargAddr */
  }

    Generate_RERR()
    {
  metric_type := DEFAULT;
  switch (error_type) in {
  case (broken_link):
    num-broken-addr=0
    /* find unreachable destinations, seqNums, prefixes */
    for (every rte (route table entry) in route table) {
        if (broken_link == rte.next_hop) {
      rte.state := broken;
      outRERR.LostDest[num-broken-addr] := rte.dest
      outRERR.LostSeq[num-broken-addr] := rte.seq#
      outRERR.PfxLen[num-broken-addr] := rte.pfx
      metric_type := rte.metType
      num-broken-addr := (num-broken-addr+1)
        }
    }
    /* No offending-src for this case */
  case (undeliverable packet):
    offending-src := undeliverable_packet.srcIP
    outRERR.LostDest[] := undeliverable_packet.destIP
    outRERR.LostPfxSiz[] := MAX_PFX_SIZE   /* 31 or 127 */
    num-broken-addr=1
  }

  /* build RFC 5444 message header fields */
  {
    msg-type=RERR (message is of type RERR)
    MF=4 (Message Flags = 4 [only msg-hop-limit field is present])
    MAL=3 or 15 (Message Address Length [3 for IPv4, 15 for IPv6])
    msg-size=NN (octets -- counting MsgHdr, AddrBlk, and AddrTLVs)
    msg-hop-limit := outRERR.hopLim;
    if (NULL != offending-src) {
      /* Build PktSource Message TLV */
    }
    if (metric_type != DEFAULT) { /* Metric_type != HopCount */
      /* Build Metric_type Message TLV */
    }
  }

  /* build AddrBlk */
  num-addr := num-broken-addr;
  AddrBlk := outRERR.LostDest[];

  /* Add AddrBlk Seq# TLV */
  Seq#TLV := outRERR.LostSeq[]

  /* only add AddrBlk PfxSiz TLV if prefixes are nondefault */
  for (pfx in outRERR.LostPfx[]) {
    if (pfx != Max_Prefix_Size) { /* 31 for IPv4, 127 for IPv6 */
      PfxSizTLV := outRERR.LostPfx[]
      return;
    }
  }
    }

    Receive_RERR (inERR)
    {
  /* Extract inERR values */
  next_hop := inRERR.nbrIP
  offending-src := inRERR.offending-src;  /* NULL if not present */

  precursors[] := NULL;
  num-broken-addr := 0;
  in-broken-addr := 0;
  for (IPaddr := inRERR.LostDest[in-broken-addr]) {
    rte := Fetch_Route_Table_Entry (dest, metric_type);
    if (NULL == rte) {
      continue;
    } else if (rte.nextHop != inRERR.fromIP) {
      continue;
    } else if (NULL != rte.precursors) {
      /* add rte.precursors to precursors */
    } else if (rte.PfxSiz < inRERR.PfxSiz) {
    /***********************************************************
     If the reported prefix from the incoming RERR is *longer*
       than the prefix from Route Table, then create a new route
       with the longer prefix.
       The newly created route will be marked as broken, and used
       to regenerate RERR, NOT using shorter the routing prefix.
       This avoids unnecessarily invalidating the larger subnet.
     **********************************************************/
      rte := Create_Route_Table_Entry (IPaddr, seq#,
        metric_type, new_metric, inRERR.PfxSiz);
    }
    LostDest[num-broken-addr] := rte.Dest;
    Seq#[num-broken-addr] := rte.Seq#;
    PfxSiz[num-broken-addr] := rte.PfxSiz;
    rte.state = broken;
    num-broken-addr := (num-broken-addr + 1);
    in-broken-addr := (in-broken-addr + 1);
  }
  if (num-broken-addr > 0) {
    Regenerate_RERR (offending-src, precursors,
      LostDest[], Seq#[], PfxSiz[])
  }
    }

    Regenerate_RERR (offending-src, precursors,
    LostDest[], LostSeq#[], PfxSiz[])
    {
  /* build RFC 5444 message header fields */
  {
      msg-type=RERR (message is of type RERR)
      MF=4 (Message Flags = 4 [only msg-hop-limit field is present])
      MAL=3 or 15 (Message Address Length [3 for IPv4, 15 for IPv6])
      msg-size=NN (octets -- counting MsgHdr, AddrBlk, and AddrTLVs)
      outRERR.hopLim := inRERR.hopLim - 1
      msg-hop-limit := outRERR.hopLim;

      if (NULL != offending-src) {
      /* Build PktSource Message TLV */
      }
      if (metric_type != DEFAULT) { /* Metric_type != HopCount */
      /* Build Metric_type Message TLV */
      }
  }

  /* build AddrBlk */
  num-addr := num-broken-addr;
  AddrBlk := LostDest[];

  /* Add AddrBlk Seq# TLV */
  Seq#TLV := LostSeq[]

  /* only add AddrBlk PfxSiz TLV if prefixes are nondefault */
  for (pfx in PfxSiz[]) {
    if (pfx != Max_Prefix_Size) { /* 31 for IPv4, 127 for IPv6 */
      PfxSizTLV := PfxSiz[]
    }
  } /* If all are default, don't include PfxSize AddrTLV */

  if (#precursors == 1) {
    unicast RERR to precursor[0];
  } else if (#precursors > 1) {
    multicast RERR to RERR_PRECURSORS;
  } else if (offending-src != NULL) {
    unicast RERR to offending-src;
  } else {
    multicast RERR to RERR_PRECURSORS;
  }
    }

    /* To be sent when RREP includes the AckReq TLV */
    Generate_RREP_Ack()
    {
  /* assign RFC 5444 fields */
  msgtype := RREPAck
  MF := 0
  MAL := 3
  msg-size := 4
    }

    Consume_RREP_Ack()
    {
  /* turn off timeout event for the node sending RREP_Ack */
    }

    Timeout_RREP_Ack()
    {
  /* insert unresponsive node into blacklist */
    }

     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
    +-+-+-+-+-+-+-+-+
    | PV=0 |  PF=0  |
    +-+-+-+-+-+-+-+-+

     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
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | msg-type=RREQ | MF=4  | MAL=3 |          msg-size=28          |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | msg-hop-limit |      msg.tlvs-length=0        |   num-addr=2  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |1|0|0|0|0| Rsv | head-length=3 | Head (bytes for Orig & Target):
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    :Head(Orig&Targ)|   Orig.Mid    |  Target.Mid   |addr.TLV.len=11:
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    :addr.TLV.len=11|type=OrigSeqNum|0|1|0|1|0|0|Rsv| Index-start=0 |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | tlv-length=2  |     Orig.Node Sequence #      |  type=Metric  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |0|1|0|1|0|0|Rsv| Index-start=0 | tlv-length=1  | OrigAddrHopCt |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

     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
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | msg-type=RREP | MF=4  | MAL=3 |          msg-size=28          |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | msg-hop-limit |      msg.tlvs-length=0        |   num-addr=2  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |1|0|0|0|0| Rsv | head-length=3 | Head (bytes for Orig & Target):
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    :Head(Orig&Targ)|   Orig.Mid    |  Target.Mid   |addr.TLV.len=11:
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    :addr.TLV.len=11|type=TargSeqNum|0|1|0|1|0|0|Rsv| Index-start=1 |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | tlv-length=2  |     Targ.Node Sequence #      |  type=Metric  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |0|1|0|1|0|0|Rsv| Index-start=1 | tlv-length=1  | TargAddrHopCt |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

     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
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | msg-type=RERR | MF=4  | MAL=3 |          msg-size=24          |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    | msg-hop-limit |      msg.tlvs-length=0        |   num-addr=2  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |1|0|0|0|0| Rsv | head-length=3 | Head (for both destinations)  :
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    :Head (3rd byte)|  Mid (Dest_1) | Mid (Dest_2)  | addr.TLV.len=7:
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    :addr.TLV.len=7 |  type=SeqNum  |0|0|1|1|0|1|Rsv| tlv-length=4  |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |        Dest_1 Sequence #      |        Dest_2 Sequence #      |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

     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
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |msgtype=RREPAck| MF=0  | MAL=3 |          msg-size=4           |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+