3. Applicability Statement

The AODVv2 routing protocol is a reactive routing protocol. Certain interactions with the forwarding plane are required, and these are discussed in Section 6.4.

AODVv2 is designed for stub or disconnected mobile ad hoc networks, i.e., non-transit networks or those not connected to the internet. AODVv2 can, however, be configured to perform gateway functions when attached to external networks, as discussed in Section 9.

AODVv2 handles a wide variety of mobility and traffic patterns by determining routes on-demand. In networks with a large number of routers, AODVv2 is best suited for relatively sparse traffic scenarios where each router forwards IP packets to a small percentage of other AODVv2 routers in the network. In this case fewer routes are needed, and therefore less control traffic is produced.

Providing security for a reactive routing protocol can be difficult. AODVv2 provides for message integrity and security against replay attacks by using integrity check values, timestamps and sequence numbers, as described in Section 13. If security associations can be established, encryption can be used for AODVv2 messages to ensure that only trusted routers participate in routing operations.

Since the route discovery process typically results in a route being established in both directions along the same path, uni-directional links are not suitable. AODVv2 will detect and exclude those links from route discovery. The route discovered is optimised for the requesting router, and the return path may not be the optimal route.

AODVv2 is applicable to memory constrained devices, since only a little routing state is maintained in each AODVv2 router. In contrast to proactive routing protocols, which maintain routing information for all destinations within the MANET, AODVv2 routes that are not needed for forwarding data do not need to be maintained. On routers unable to store persistent AODVv2 state, recovery can impose a performance penalty (e.g., in case of AODVv2 router reboot), since if a router loses its sequence number, there is a delay before the router can resume full operations. This is described in Section 6.1.

AODVv2 supports routers with multiple interfaces, as long as each interface configured for AODVv2 has a unicast IP address. A router may use the same IP address on multiple interfaces. Address assignment procedures are out of scope for AODVv2.

AODVv2 supports hosts with multiple interfaces, as long as each interface is configured with its own unicast IP address. Multi-homing of an IP address is not supported by AODVv2, and therefore a Router Client, i.e. an IP Address, SHOULD NOT be served by more than one AODVv2 router at any one time. Appendix A contains some notes on this topic.

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

The routing algorithm in AODVv2 MAY be operated at layers other than the network layer, using layer-appropriate addresses.

4. Data Structures

4.1. Interface List

If multiple interfaces of the AODVv2 router are configured for use by AODVv2, a list of the interfaces SHOULD be configured in the AODVv2_INTERFACES list.

4.2. Router Client Table

An AODVv2 router MUST provide route discovery services for its own local applications and for other non-routing nodes that are reachable without traversing another AODVv2 router. These nodes, and the AODVv2 router itself, are referred to as Router Clients. An AODVv2 router will only originate Route Request and Route Reply messages on behalf of configured Router Clients.

Router Client Table entries MUST contain:

RouterClient.IPAddress

An IP address or the start of an address range that requires route discovery services from the AODVv2 router.

RouterClient.PrefixLength

The length, in bits, of the routing prefix associated with the RouterClient.IPAddress. If a prefix length is included, the AODVv2 router MUST provide connectivity for all addresses within that prefix.

RouterClient.Cost

The cost associated with reaching this Router Client. This cost will also appear as the metric in a route table entry for the Router Client address.

The Router Client Table for an AODVv2 router is never empty, since an AODVv2 router is always its own client. The IP Addresses of the router's interfaces will appear in the Router Client Table.

In the initial state, an AODVv2 router is not required to have information about the Router Clients of any other AODVv2 router.

A Router Client address MUST NOT be served by more than one AODVv2 router at any one time, i.e. a Router Client of one AODVv2 router MUST NOT be configured as a Router Client on another AODVv2 router using the same Router Client IP address. Shifting responsibility for a Router Client to a different AODVv2 router is discussed in Appendix B.

4.3. Neighbor Table

A neighbor table MUST be maintained with information about neighboring AODVv2 routers which are used in discovered routes.

Neighbor Table entries MUST contain:

Neighbor.IPAddress

An IP address of the neighboring router, learned from the source IP address of a received route message.

Neighbor.State

The state of the adjacency with the neighbor (Confirmed, Unknown, or Blacklisted). The Unknown state is the initial state. The Confirmed state indicates that the link to the neighbor has been confirmed as bidirectional. The Blacklisted state indicates that the link to the neighbor is uni-directional. Section 6.2 discusses how to monitor adjacency.

Neighbor.ResetTime

When the State is Blacklisted, this time indicates the point at which the State reverts to Unknown. By default this value is calculated at the time the router is blacklisted and is equal to CurrentTime + MAX_BLACKLIST_TIME. When the neighbor State is not Blacklisted, this time is set to INFINITY_TIME.

4.4. Sequence Numbers

Sequence numbers enable AODVv2 routers to determine the temporal order of route discovery messages, identifying stale routing information so that it can be discarded. The sequence number fulfills the same roles as the "Destination Sequence Number" of DSDV [Perkins94], and the AODV Sequence Number in [RFC3561].

Each AODVv2 router in the network MUST maintain its own sequence number as a 16-bit unsigned integer.

All RREQ and RREP messages created by an AODVv2 router include the router's sequence number. Each AODVv2 router MUST ensure that its sequence number is strictly increasing. It is incremented by one (1) whenever an RREQ or RREP is created, except when the sequence number is 65,535 (the maximum value of a 16-bit unsigned integer), in which case it MUST be reset to one (1). The value zero (0) is reserved to indicate that the sequence number for an address is unknown.

An AODVv2 router can only attach its own sequence number to information about a route to one of its configured router clients. All route messages regenerated by other routers retain the originator's sequence number. Therefore, when two pieces of information about a route are received, they both contain a sequence number from the originating router. Comparing the sequence number will identify which information is stale. The currently stored sequence number is subtracted from the incoming sequence number. The result of the subtraction is to be interpreted as a signed 16-bit integer, and if less than zero, then the information in the AODVv2 message is stale and MUST be discarded.

As a consequence, loop freedom is assured.

An AODVv2 router SHOULD maintain its sequence number in persistent storage. If the sequence number is lost, the router MUST follow the procedure in Section 6.1 to safely resume routing operations with a new sequence number.

4.5. Multicast Route Message Table

A route message (RteMsg) is either a Route Request or Route Reply message. The Multicast Route Message Table is a conceptual table which contains information about previously received multicast route messages, so that when a route message is received, an AODVv2 router can determine if the incoming information is redundant, and avoid unnecessary regeneration of the route message.

A Multicast Route Message Table entry MUST contain the following information:

RteMsg.MessageType

Either RREQ or RREP.

RteMsg.OrigAddr

An IP address of the node which requires the route, i.e., the source address of the IP packet triggering the route request.

RteMsg.OrigPrefixLen

The prefix length associated with OrigAddr.

RteMsg.TargAddr

An IP address of the target, i.e., the destination address of the IP packet triggering the route request.

RteMsg.TargPrefixLen

The prefix length associated with TargAddr.

RteMsg.OrigSeqNum

The sequence number associated with the originator, if present in RteMsg.

RteMsg.TargSeqNum

The sequence number associated with the target, if present in RteMsg.

RteMsg.MetricType

The metric type of the route requested.

RteMsg.Metric

The metric value received in the RteMsg.

RteMsg.Timestamp

The last time this entry was updated.

RteMsg.RemoveTime

The time at which this entry MUST be removed, MAX_SEQNUM_LIFETIME after the last update of RteMsg.OrigSeqNum for an RREQ, or RteMsg.TargSeqNum for an RREP.

The Multicast Route Message Table is maintained so that no two entries have the same MessageType, OrigAddr, TargAddr, and MetricType. See Section 6.8 for details on updating this table.

4.6. Route Table

All AODVv2 routers MUST maintain a route table. The route table entry is a conceptual data structure. Implementations MAY use any internal representation but MUST contain the following information:

Route.Address

An address, which, when combined with Route.PrefixLength, describes the set of destination addresses this route includes.

Route.PrefixLength

The prefix length, in bits, associated with Route.Address.

Route.SeqNum

The sequence number associated with Route.Address, obtained from the last route message that successfully updated this route.

Route.NextHop

The source IP address of the message advertising the route to Route.Address, i.e. an IP address of the AODVv2 router used for the next hop on the path toward Route.Address.

Route.NextHopInterface

The interface used to send IP packets toward Route.Address.

Route.LastUsed

The time this route was last used to forward an IP packet.

Route.LastSeqNumUpdate

The time the sequence number for this route was last updated.

Route.ExpirationTime

The time at which this route must be marked as Invalid.

Route.MetricType

The type of metric associated with this route.

Route.Metric

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

Route.State

The last known state (Active, Idle, Invalid, or Unconfirmed) of the route.

Route.Precursors (optional feature)

A list of upstream neighbors using the route (see Section 10.2).

There are four possible states for an AODVv2 route:

Active

An Active route is in current use for forwarding IP packets.

Idle

An Idle route has not been used in the last ACTIVE_INTERVAL, but can still be used for forwarding IP packets.

Invalid

An Invalid route cannot be used for forwarding IP packets. Invalid routes have sequence number information, which allows incoming information to be assessed for freshness.

Unconfirmed

An Unconfirmed route cannot be used for forwarding IP packets. It is a route learned from a Route Request which has not yet been confirmed as bidirectional.

Route state changes are detailed in Section 6.9.1.

An AODVv2 route MAY be offered for a limited time. In this case, the route is referred to as a timed route. The length of time for which the route is valid is referred to as validity time, and is included in messages which advertise the route. The shortened validity time is reflected in Route.ExpirationTime. If a route is not timed, the ExpirationTime is INFINITY_TIME.

5. Metrics

Metrics measure a cost or quality associated with a route or a link, e.g., latency, delay, financial cost, energy, etc. Metric values are reported in route messages, where the goal is to determine a route between OrigAddr and TargAddr. In Route Request messages, the metric describes the cost of the route from OrigAddr (the router client) to the router sending the Route Request. The receiving router calculates the cost from OrigAddr to itself, combining the metric value from the message with knowledge of the link cost from the sender to the receiver, i.e., the incoming link cost. This updated route cost is included when regenerating the Route Request message. In Route Reply messages, the metric reflects the cost of the route from TargAddr (the router client) to the router sending the Route Reply. Routes to OrigAddr and TargAddr are installed at intermediate routers for the purposes of forwarding a Route Reply message and subsequent data traffic between OrigAddr and TargAddr. Assuming link metrics are symmetric, the cost of the routes to OrigAddr and TargAddr installed at each router will be correct.

AODVv2 enables the use of multiple metric types. Each route discovery attempt indicates the metric type which is requested for the route. Only one metric type may be used in each route discovery attempt. However, routes to a single destination might be requested for different metric types. The decision of which of these routes to use for forwarding is outside the scope of AODVv2.

For each MetricType, AODVv2 requires:

• A MetricType number, to indicate the metric type of a route. MetricType numbers allocated are detailed in Section 11.6.
• A maximum value, denoted MAX_METRIC[MetricType]. If the cost of a route exceeds MAX_METRIC[MetricType], the route is ignored. AODVv2 cannot store routes that cost more than MAX_METRIC[MetricType].
• A function for incoming link cost, denoted Cost(L). Using incoming link costs means that the route learned has a path optimized for the direction from OrigAddr to TargAddr.
• A function for route cost, denoted Cost(R).
• A function to analyze routes for potential loops, denoted LoopFree(R1, R2). LoopFree verifies that a route R2 is not a sub-section of another route R1. An AODVv2 router invokes LoopFree() as part of the process in Section 6.7.1, when an advertised route (R1) and an existing route (R2) have the same destination address, metric type, and sequence number. LoopFree returns FALSE to indicate that an advertised route is not to be used to update a stored route, if it may cause a routing loop. In the case where the existing route is Invalid, it is possible that the advertised route includes the existing route and came from a router which did not yet receive notification of the route becoming Invalid, so the advertised route should not be used in case it forms a loop to a broken route.

AODVv2 currently supports cost metrics where Cost(R) is strictly increasing, by defining:

• Cost(R) := Sum of Cost(L) of each link in the route
• LoopFree(R1, R2) := ( Cost(R1) <= Cost(R2) )

Implementers MAY consider other metric types, but the definitions of Cost and LoopFree functions for such types are undefined, and interoperability issues need to be considered.

6. AODVv2 Protocol Operations

The AODVv2 protocol's operations include managing sequence numbers, monitoring adjacent AODVv2 routers, performing route discovery and dealing with requests from other routers, processing incoming route information and updating the route table, suppressing redundant messages, maintaining the route table and reporting broken routes. These processes are discussed in detail in the following sections.

6.1. Initialization

During initialization where an AODVv2 router does not have information about its previous sequence number, or if its sequence number is lost at any point, the router resets its sequence number to one (1). However, other AODVv2 routers may still hold sequence number information that this router previously issued. Since sequence number information is removed if there has been no update to the sequence number in MAX_SEQNUM_LIFETIME, the initializing router must wait for MAX_SEQNUM_LIFETIME before it creates any messages containing its new sequence number. It can then be sure that the information it sends will not be considered stale.

Until MAX_SEQNUM_LIFETIME after its sequence number is reset, the router SHOULD NOT create RREQ or RREP messages.

During this wait period, the router can do the following:

• Process information in a received RREQ or RREP message to learn a route to the originator or target of that route discovery
• Regenerate a received RREQ or RREP
• Send an RREP_Ack
• Maintain valid routes in order that the forwarding process can forward IP packets to Router Clients and to other routers
• Create, process and regenerate RERR messages

6.2. Adjacency Monitoring

AODVv2 routers MUST NOT establish routes over uni-directional links. Consider the following. An RREQ is forwarded toward TargAddr, and intermediate routers install a route to OrigAddr. If, at one of those routers, the link to the next hop toward OrigAddr was uni-directional, and this route was used to forward data traffic, the data packets would be lost. Further, an RREP sent toward OrigAddr using this link will not reach the next hop, and will therefore not be regenerated, and will never reach RREQ_Gen, so end-to-end route establishment will fail. AODVv2 routers MUST verify that the link to the next hop is bidirectional when establishing a route, and before allowing data traffic to be forwarded on that route. If bidirectionality cannot be verified, this link MUST be excluded from the route discovery procedure.

AODVv2 refers to a bidirectional link with a neighboring router as an adjacency. AODVv2 routers do not need to monitor adjacency to all neighboring AODVv2 routers at all times, but MUST determine if there is an adjacency to the chosen next-hop AODVv2 router during route discovery.

• For the next hop toward OrigAddr, the approach for testing bidirectional connectivity is to request acknowledgement of Route Reply messages. Receipt of an acknowledgement proves that bidirectional connectivity exists. All AODVv2 routers MUST support this process, which is explained in Section 7.2 and Section 7.3. If a link to a neighbor is determined to be unidirectional because a requested acknowledgement is not received within RREP_Ack_SENT_TIMEOUT, the neighbor MUST be marked as blacklisted (see below).
• For the next hop toward TargAddr, receipt of the Route Reply message containing the route to TargAddr is confirmation of bidirectionality, since a Route Reply message is a reply to a Route Request message which previously crossed the link in the opposite direction.

To assist with adjacency monitoring, a Neighbor Table (Section 4.3) is maintained. Each entry contains a neighbor IP address and an indication of the state of the adjacency with that neighbor (Unknown, Blacklisted, or Confirmed). When an RREQ or RREP is received from an IP address which does not already have an entry in the Neighbor Table, a new entry is created as described in Section 6.3. While neighbor state is Unknown, acknowledgement of RREP messages MUST be requested. While neighbor state is Confirmed, the request for an acknowledgement is unnecessary.

When routers perform other operations such as those from the list below, these MAY be used as additional indications of connectivity:

• NHDP HELLO Messages [RFC6130]
• Route timeout
• Lower layer triggers, e.g. message reception or link status notifications
• TCP timeouts
• Promiscuous listening
• Other monitoring mechanisms or heuristics

If such an external process signals that the link is bidirectional, the neighbor state MAY be set to Confirmed. If an external process signals that a link is not bidirectional, the AODVv2 router MAY update the matching Neighbor Table entry by changing the neighbor state to Blacklisted. If an external process signals that the link might not be bidirectional, and the neighbor state is currently Confirmed, the state MAY be set to Unknown.

For example, receipt of a Neighborhood Discovery Protocol HELLO message with the receiving router listed as a neighbor is a signal of bidirectional connectivity. The AODVv2 router MAY update the matching Neighbor Table entry by changing the neighbor state to Confirmed.

Similarly, if AODVv2 receives notification of a timeout, for example, from TCP or some other protocol, this may be due to a disconnection. The AODVv2 router MAY update the matching Neighbor Table entry by resetting the neighbor state to Unknown.

6.3. Neighbor Table Update

On receipt of an RREQ or RREP message, the neighbor table MUST be checked for an entry with Neighbor.IPAddress which matches the source IP address of the message. If no matching entry is found, a new entry is created.

A new Neighbor Table entry is created as follows:

• Neighbor.IPAddress := Source IP address of the message
• Neighbor.State := Unknown
• Neighbor.ResetTime := INFINITY_TIME

When the link to the neighbor is determined to be bidirectional, the Neighbor Table entry is updated as follows:

• Neighbor.State := Confirmed

When the link to the neighbor is determined to be uni-directional, the Neighbor Table entry is updated as follows:

• Neighbor.State := Blacklisted
• Neighbor.ResetTime := CurrentTime + MAX_BLACKLIST_TIME

When the Neighbor.ResetTime is reached, the Neighbor Table entry is updated as follows:

• Neighbor.State := Unknown

When a link to a neighbor is determined to be broken, the Neighbor Table entry SHOULD be removed.

Route requests from neighbors with Neighbor.State set to Blacklisted are ignored to avoid persistent IP packet loss or protocol failures. However, the reset time allows the neighbor to again be allowed to participate in route discoveries after MAX_BLACKLIST_TIME, in case the link between the routers has become bidirectional.

6.4. Interaction with Forwarding Plane

A reactive protocol reacts when a route is needed. A route is requested when an application tries to send a packet. The fundamental concept of reactive routing is to avoid creating routes that are not needed.

AODVv2 requires signals from the forwarding plane:

• A packet cannot be forwarded because a route is unavailable: AODVv2 needs to know the source and destination IP addresses of the packet, to determine whether it should initiate route discovery, and include this information in a Route Request message, or create a Route Error message.
• A packet is to be forwarded: AODVv2 needs to check the state of the route to deal with timeouts. If the implementation uses timers to enforce route timeouts, this signal is unnecessary.
• Packet forwarding failure occurs: AODVv2 needs to initiate route error reports.
• Packet forwarding succeeds: AODVv2 needs to update the record of when a route was last used to forward a packet.

AODVv2 needs to send signals to the forwarding plane:

• A route discovery is in progress: packets awaiting a route may be buffered while route discovery is attempted.
• A route discovery was not attempted: any buffered packets requiring that route should be discarded.
• A route discovery failed: any buffered packets requiring that route should be discarded, and the source of the packet should be notified that the destination is unreachable (using an ICMP Destination Unreachable message).
• A route discovery succeeded: install a route which AODVv2 has determined to be valid and begin transmitting any buffered packets.
• A route has been lost: remove an installed route which AODVv2 has determined to be invalid.
• A route has been updated: update an installed route when AODVv2 receives new information about the route.

These are conceptual signals, and can be implemented in various ways. Conformant implementations of AODVv2 are not mandated to implement the forwarding plane separately from the control plane or data plane; these signals and interactions are identified simply as assistance for implementers who may find them useful.

6.5. Message Transmission

AODVv2 sends [RFC5444] formatted messages using the parameters for port number and IP protocol specified in [RFC5498]. Mapping of AODVv2 Data Elements to [RFC5444] is detailed in Section 8.

Messages may travel a maximum of MAX_HOPCOUNT hops.

Unless otherwise specified, AODVv2 multicast messages are sent to the link-local multicast address LL-MANET-Routers [RFC5498]. All AODVv2 routers MUST subscribe to LL-MANET-Routers [RFC5498] to receive AODVv2 messages.

Note that multicast messages 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.

Implementations MAY choose to employ techniques to reduce the number of multicast messages sent. Use of [RFC6621] in deployments is recommended. Employing [RFC6621] in a subset of the operational AODVv2 routers in a network, or configuring different algorithms on different routers, will not cause interoperability issues, but will reduce the effectiveness of the multicast reduction scheme.

When multiple interfaces are available, an AODVv2 router transmitting a multicast message to LL-MANET-Routers MUST send the message on all interfaces that have been configured for AODVv2 operation, as given in the AODVv2_INTERFACES list (Section 4.1). Similarly, AODVv2 routers MUST subscribe to LL-MANET-Routers on all their AODVv2 interfaces.

To avoid congestion, each AODVv2 router's rate of message generation SHOULD be limited (CONTROL_TRAFFIC_LIMIT) and administratively configurable. To prioritize transmission of AODVv2 control messages in order to respect the CONTROL_TRAFFIC_LIMIT:

• Highest priority SHOULD be given to RREP_Ack messages. This allows learned routes to be confirmed as bidirectional and avoids undesirable blacklisting of next hop routers.
• Second priority SHOULD be given to RERR messages for undeliverable IP packets, so that broken routes that are still being used are reported, and to avoid IP data packets being repeatedly forwarded to AODVv2 routers which cannot forward to their destination.
• Third priority SHOULD be given to RREP messages in order that RREQs do not time out.
• RREQ messages SHOULD be given priority over RERR messages for newly invalidated routes, since the invalidated routes may not still be in use, and if there is an attempt to use the route, a new RERR message will be generated.
• Lowest priority SHOULD be given to RERR messages generated in response to RREP messages which cannot be regenerated. In this case the route request will be retried at a later point.

6.6. Route Discovery, Retries and Buffering

AODVv2's RREQ and RREP messages are used for route discovery. The main difference between the two messages is that, usually, RREQ messages are multicast to solicit an RREP, whereas RREP is unicast as a response to the RREQ. The constants used in this section are defined in Section 11.

When an AODVv2 router needs to forward an IP packet (with source address OrigAddr and destination address TargAddr) from one of its Router Clients, it needs a route to the packet's destination. If no route exists, the AODVv2 router generates and multicasts a Route Request message (RREQ) using OrigAddr and TargAddr. The procedure for this is described in Section 7.1.1. Each new RREQ results in an increment to the sequence number. The AODVv2 router is referred to as RREQ_Gen.

IP packets awaiting a route MAY be buffered by RREQ_Gen. Buffering of IP packets can have both positive and negative effects. Real-time traffic, voice, and scheduled delivery may suffer if packets are buffered and subjected to delays, but TCP connection establishment will benefit if packets are queued while route discovery is performed.

Determining which packets to discard first when the buffer is full is a matter of policy at each AODVv2 router. Routers without sufficient memory available for buffering SHOULD have buffering disabled. This will affect the latency for launching TCP applications to new destinations.

RREQ_Gen awaits reception of a Route Reply message (RREP) containing a route toward TargAddr. An RREQ from TargAddr would also fulfil the request, if adjacency to the next hop is already confirmed. If a route to TargAddr is not learned within RREQ_WAIT_TIME, RREQ_Gen MAY retry the route discovery. To reduce congestion in a network, repeated attempts at route discovery for a particular target address SHOULD utilize a binary exponential backoff: for each additional attempt, the waiting time for receipt of the RREP is multiplied by 2. If the requested route is not learned within the wait period, another RREQ MAY be sent, up to a total of DISCOVERY_ATTEMPTS_MAX. This is the same technique used in AODV [RFC3561].

The RREQ is received by neighboring AODVv2 routers, and processed and regenerated as described in Section 7.1. Intermediate routers learn a potential route to OrigAddr from the RREQ. The router responsible for TargAddr responds by generating a Route Reply message (RREP) and unicasts it back toward RREQ_Gen using the potential route to OrigAddr learned from the RREQ. Each intermediate router regenerates the RREP and unicasts toward OrigAddr.

Links which are not bidirectional cause problems. If a link is unavailable in the direction toward OrigAddr, an RREP is not received at the next hop, so cannot be regenerated, and it will never reach RREQ_Gen. However, since routers monitor adjacencies (Section 6.2), the loss of the RREP will cause the last router which regenerated the RREP to blacklist the router which did not receive it. Later, a timeout occurs at RREQ_Gen, and a new RREQ MAY be regenerated. If the new RREQ arrives via the blacklisted router, it will be ignored, enabling the RREQ to discover a different path toward TargAddr.

Route discovery SHOULD be considered to have failed after DISCOVERY_ATTEMPTS_MAX and the corresponding wait time for an RREP response to the final RREQ, in order to avoid repeatedly generating control traffic that is unlikely to discover a route. 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 avoid generating more multicast messages which are unlikely to discover a route. Any IP packets buffered for TargAddr MUST also be dropped and a Destination Unreachable ICMP message (Type 3) with a code of 1 (Host Unreachable Error) SHOULD be delivered to the source of the packet, so that the application knows about the failure. The source can be an application on RREQ_Gen itself, or on a Router Client with address OrigAddr.

If RREQ_Gen does receive a route message containing a route to TargAddr within the timeout, it MUST process the message according to Section 7. When a valid route is installed, the router can begin sending the buffered IP packets. Any retry timers for the corresponding RREQ MUST be cancelled.

During route discovery, all routers on the path learn a route to both OrigAddr and TargAddr, so that routes are constructed in both directions. The route is optimized for the forward route, and the return route uses the same path in reverse.

6.7. Processing Received Route Information

All AODVv2 route messages contain a route. A Route Request (RREQ) includes a route to OrigAddr, and a Route Reply (RREP) contains a route to TargAddr.

All AODVv2 routers that receive a route message can store the route contained within it. Incoming information is first checked to verify that it is both safe to use and offers an improvement to existing information. This process is explained in Section 6.7.1. The route table MAY then be updated according to Section 6.7.2.

In the processes below, RteMsg is used to denote the route message, AdvRte is used to denote the route contained within it, and Route denotes an existing route which matches AdvRte on address, prefix length, and metric type.

AdvRte has the following properties:

• AdvRte.Address := RteMsg.OrigAddr (in RREQ) or RteMsg.TargAddr (in RREP)
• AdvRte.PrefixLength := RteMsg.OrigPrefixLen (in RREQ) or RteMsg.TargPrefixLen (in RREP) if included, or if no prefix length was included in RteMsg, the address length, in bits, of AdvRte.Address
• AdvRte.SeqNum := RteMsg.OrigSeqNum (in RREQ) or RteMsg.TargSeqNum (in RREP)
• AdvRte.NextHop := RteMsg.IPSourceAddress (an address of the router from which the AdvRte was received)
• AdvRte.MetricType := RteMsg.MetricType
• AdvRte.Metric := RteMsg.Metric
• AdvRte.Cost := Cost(R) using the cost function associated with the route's metric type, i.e. Cost(R) = AdvRte.Metric + Cost(L), as described in Section 5, where L is the link from the advertising router.
• AdvRte.ValidityTime := RteMsg.ValidityTime, if included

6.7.1. Evaluating Route Information

An incoming route advertisement (AdvRte) is compared to existing routes to determine whether the advertised route is to be used to update the routing table. The incoming route information MUST be processed as follows:

1. Search for a route (Route) matching AdvRte's address, prefix length and metric type
   • If no matching route exists, AdvRte MUST be used to update the routing table. Multiple routes to the same destination may exist with different metric types.
   • If all matching routing table entries have State set to Unconfirmed, AdvRte SHOULD be added to the routing table. This may result in multiple Unconfirmed routes to the same address. In this case, the best route from the set of Unconfirmed routes SHOULD be used to forward future RREPs. If the link to the next hop is found to be bidirectional, and the Unconfirmed route becomes valid, any remaining Unconfirmed routes which would not offer improvement MUST be expunged.
   • If a matching route exists with State set to Active, Idle, or Invalid, continue to Step 2.

2. Compare sequence numbers using the technique described in Section 4.4
   • If AdvRte is more recent, AdvRte MUST be used to update the routing table.
   • If AdvRte is stale, AdvRte MUST NOT be used to update the routing table.
   • If the sequence numbers are equal, continue to Step 3.

3. Check that AdvRte is safe against routing loops (see Section 5)
   • If LoopFree(AdvRte, Route) returns FALSE, AdvRte MUST NOT be used to update the routing table because using the incoming information might cause a routing loop.
   • If LoopFree(AdvRte, Route) returns TRUE, continue to Step 4.

4. Compare route costs
   • If AdvRte is better, it SHOULD be used to update the routing table because it offers improvement. If it is not used to update the existing route, the existing non-optimal route will continue to be used, causing data flows to use a route with a worse cost where this could have been avoided.
   • If AdvRte is equal in cost and Route is Valid, AdvRte MAY be used to update the routing table but will offer no improvement.
   • If AdvRte is worse and Route is valid, AdvRte MUST NOT be used to update the routing table because it does not offer any improvement.
   • If AdvRte is not better (i.e., it is worse or equal) but Route is Invalid, AdvRte SHOULD be used to update the routing table because it can safely repair the existing Invalid route.

If the advertised route SHOULD be used to update the routing table, the procedure in Section 6.7.2 MUST be followed. If the route is not used, non-optimal routes will remain in the routing table.

6.7.2. Applying Route Updates

If AdvRte is from an RREQ message, the next hop neighbor may not be confirmed as adjacent (see Section 4.3). If Neighbor.State is Unknown, the route to AdvRte.Address might not be viable, but it MUST be stored to allow a corresponding RREP to be sent. However, the route's State will be set to Unconfirmed to indicate that this route SHOULD NOT yet be used to forward data, since the link may be uni-directional and packet losses may occur. If a valid route already exists for this destination, this Unconfirmed route SHOULD be stored as an additional entry. If the link to the next hop is later confirmed to be bidirectional, the route will offer improvement over the existing valid route.

The route update is applied as follows:

1. If no existing route matches AdvRte on address, prefix length and metric type, continue to Step 3 and create a new route.
2. If a matching route exists:
   • If AdvRte has a different next hop to the existing route (Route), and both AdvRte.NextHop's Neighbor.State is Unknown and Route.State is Active or Idle, the current route is valid but the advertised route may offer improvement, if the next hop can be confirmed as bidirectional. Continue processing from Step 3 to create a new route.
   • If AdvRte.NextHop's Neighbor.State is Unknown and Route.State is Invalid, continue processing from Step 4 to update the existing route (Route).
   • If AdvRte.NextHop's Neighbor.State is Confirmed, continue processing from Step 4 to update the existing route.

3. Create a route and initialize as follows:
   • Route.Address := AdvRte.Address
   • Route.PrefixLength := AdvRte.PrefixLength
   • Route.MetricType := AdvRte.MetricType

4. Update the route as follows:
   • Route.SeqNum := AdvRte.SeqNum
   • Route.NextHop := AdvRte.NextHop
   • Route.NextHopInterface := interface on which RteMsg was received
   • Route.Metric := AdvRte.Cost
   • Route.LastUsed := CurrentTime
   • Route.LastSeqNumUpdate := CurrentTime
   • Route.ExpirationTime := CurrentTime + AdvRte.ValidityTime if a validity time exists, otherwise INFINITY_TIME

5. If a new route was created, or if the existing Route.State is Invalid or Unconfirmed, update the route as follows:
   • Route.State := Unconfirmed (if the next hop's Neighbor.State is Unknown) or Idle (if the next hop's Neighbor.State is Confirmed)

6. If an existing route changed from Invalid or Unconfirmed to become Idle, any matching route table entries with worse metric values SHOULD be expunged.
7. If this update results in a route with Route.State set to Active or Idle, which matches an outstanding route request, the associated route request retry timers can be cancelled and any associated buffered IP packets MUST be forwarded.

6.8. Suppressing Redundant Messages Using the Multicast Route Message Table

When route messages are flooded in a MANET, an AODVv2 router may receive multiple similar messages. Regenerating every one of these gives little additional benefit, and generates unnecessary signaling traffic and interference.

Each AODVv2 router stores information about recently received route messages in the AODVv2 Multicast Route Message Table (Section 4.5).

To create a Multicast Route Message Table Entry:

• RteMsg.MessageType := RREQ or RREP
• RteMsg.OrigAddr := OrigAddr from the message
• RteMsg.OrigPrefixLen := the prefix length associated with OrigAddr
• RteMsg.TargAddr := TargAddr from the message
• RteMsg.TargPrefixLen := the prefix length associated with TargAddr
• RteMsg.OrigSeqNum := the sequence number associated with OrigAddr, if present in the message
• RteMsg.TargSeqNum := the sequence number associated with TargAddr, if present in the message
• RteMsg.MetricType := the metric type of the route requested
• RteMsg.Metric := the metric value associated with OrigAddr in an RREQ or TargAddr in an RREP
• RteMsg.Timestamp := CurrentTime
• RteMsg.RemoveTime := CurrentTime + MAX_SEQNUM_LIFETIME

Entries in the Multicast Route Message Table SHOULD be maintained for at least RteMsg_ENTRY_TIME after the last Timestamp update in order to account for long-lived RREQs traversing the network. An entry MUST be deleted when the sequence number is no longer valid, i.e., after MAX_SEQNUM_LIFETIME. Memory-constrained devices MAY remove the entry before this time.

To update a Multicast Route Message Table Entry, set:

• RteMsg.OrigSeqNum := the sequence number associated with OrigAddr, if present in the message
• RteMsg.TargSeqNum := the sequence number associated with TargAddr, if present in the message
• RteMsg.Metric := the metric value associated with OrigAddr in an RREQ or TargAddr in an RREP
• RteMsg.Timestamp := CurrentTime
• RteMsg.RemoveTime := CurrentTime + MAX_SEQNUM_LIFETIME

Received route messages are tested against previously received route messages, and if determined to be redundant, regeneration or response can be avoided.

To determine if a received message is redundant:

1. Search for an entry in the Multicast Route Message Table with the same MessageType, OrigAddr, TargAddr, and MetricType
   • If there is none, the message is not redundant.
   • If there is an entry, continue to Step 2.

2. Compare sequence numbers using the technique described in Section 4.4
   • For RREQ messages, use OrigSeqNum of the entry for comparison. For RREP messages, use TargSeqNum of the entry for comparison.
   • If the entry has an older sequence number than the received message, the message is not redundant.
   • If the entry has a newer sequence number than the received message, the message is redundant.
   • If the entry has the same sequence number, continue to Step 3.

3. Compare the metric values
   • If the entry has a Metric value that is worse than or equal to the metric in the received message, the message is redundant.
   • If the entry has a Metric value that is better than the metric in the received message, the message is not redundant.

If the message is redundant, update the timestamp on the entry, since matching route messages are still traversing the network and this entry should be maintained. This message SHOULD NOT be regenerated or responded to.

If the message is not redundant, create an entry or update the existing entry. Where the message is determined not redundant before Step 3, it MUST be regenerated or responded to. Where the message is determined not redundant in Step 3, it MAY be suppressed to avoid extra control traffic. However, since the processing of the message will result in an update to the route table, the message SHOULD be regenerated or responded to, to ensure other routers have up-to-date information and the best metrics. If not regenerated, the best route may not be found. Where necessary, regeneration or response is performed using the processes in Section 7.

6.9. Route Maintenance

Route maintenance involves monitoring and updating route state, handling route timeouts and reporting routes that become Invalid.

Before using a route to forward an IP packet, an AODVv2 router MUST check firstly if there is a route, and secondly the status of the route (Section 6.9.1). If the route exists and is valid, it MUST be marked as Active and its LastUsed timestamp MUST be updated, before forwarding the IP packet to the route's next hop. If there is no valid route, and if the source address of the IP packet is a Router Client, the RREQ generation procedure MUST be followed. Otherwise, the absence of a route MUST be reported to the packet's source (see Section 6.9.2).

6.9.1. Route State

During normal operation, AODVv2 does not require any explicit timeouts to manage the lifetime of a route. At any time, any route MAY be examined and updated according to the rules below. If timers are not used to prompt route state updates, route state MUST be checked before IP packet forwarding and before any operation based on route state.

The four possible states for an AODVv2 route are Active, Idle, Invalid, and Unconfirmed:

Active

If Route.State is Active and the route is not timed (i.e., if Route.ExpirationTime is INFINITY_TIME), Route.State MUST become Idle if Route is not used to forward IP packets within ACTIVE_INTERVAL. Route.State for a timed route (i.e., Route.ExpirationTime is not equal to INFINITY_TIME) remains Active until its expiration time, after which it MUST become Invalid.

Idle

If Route.State is Idle, and the route is used to forward an IP packet, Route.State MUST become Active. If the route is not used to forward an IP packet within MAX_IDLETIME, Route.State MUST become Invalid.

Invalid

If Route.State is Invalid, the route SHOULD be maintained until MAX_SEQNUM_LIFETIME after Route.LastSeqNumUpdate, after which it MUST be expunged. Route.SeqNum is used to classify future information about Route.Address as stale or fresh.

Unconfirmed

If Route.State is Unconfirmed, the route MUST become Idle when an adjacency with Route.NextHop is confirmed, or MUST be expunged if the neighbor is blacklisted, or at MAX_SEQNUM_LIFETIME after Route.LastSeqNumUpdate.

In all cases, if the time since Route.LastSeqNumUpdate exceeds MAX_SEQNUM_LIFETIME, Route.SeqNum must be set to zero. This is required to ensure that any AODVv2 routers following the initialization procedure can safely begin routing functions using a new sequence number, and that their messages will not be classified as stale and ignored. A route with Route.State set to Active or Idle can continue to be used to forward IP packets, but if Route.State later becomes Invalid, the route MUST be expunged.

Appendix C.2.1.1 contains an algorithmic representation of this timeout behavior.

Routes can become Invalid before a timeout occurs:

• If a link breaks, all routes using that link for Route.NextHop MUST immediately have Route.State set to Invalid.
• If a Route Error (RERR) message containing the route is received, either from Route.NextHop, or with PktSource set to a Router Client address, Route.State MUST immediately be set to Invalid.

When Route.State changes from Unconfirmed to Idle as a result of the adjacency with Route.NextHop being Confirmed (see Section 4.3), any matching routes with metric values worse than Route.Metric MUST be expunged.

Memory constrained devices MAY choose to expunge routes from the AODVv2 route table before Route.ExpirationTime, but MUST adhere to the following rules:

• An Active route MUST NOT be expunged, as this will result in generation of a Route Error message followed by a necessary Route Request to re-establish the route.
• An Idle route SHOULD NOT be expunged, as the route is still valid for forwarding IP traffic, and if deleted, this could result in dropped IP packets and a Route Request could be generated to re-establish the route.
• Any Invalid route MAY be expunged; least recently used Invalid routes SHOULD be expunged first, since these are less likely to be reused.
• An Unconfirmed route MUST NOT be expunged if it was installed within the last RREQ_WAIT_TIME, because it may correspond to a route discovery in progress. A Route Reply message might be received which needs to use the Route.NextHop information. Otherwise, it MAY be expunged.

Route table entries are updated when Neighbor State is updated:

• While Neighbor.State is set to Unknown, any routes learned through that neighbor are marked as Unconfirmed.
• When Neighbor.State is set to Confirmed, the Unconfirmed routes using the neighbor as a next hop SHOULD be marked as valid (see Section 6.9.1).
• When Neighbor.State is set to Blacklisted, any valid routes installed which use that neighbor for their next hop are marked as Invalid.
• When a Neighbor Table entry is removed, all routes using the neighbor as next hop MUST be marked as Invalid.

6.9.2. Reporting Invalid Routes

When Route.State changes from Active to Invalid as a result of a broken link or a received Route Error (RERR) message, other routers SHOULD be informed by sending an RERR message containing details of the invalidated route.

An RERR message SHOULD also be sent when an AODVv2 router receives an IP packet to forward on behalf of another router but does not have a valid route for the destination of the packet.

An RERR message SHOULD also be sent when an AODVv2 router receives an RREP message to regenerate, but the route to the OrigAddr in the RREP has been lost and is marked as Invalid.

The packet or message triggering the RERR MUST be discarded.

Generation of an RERR message is described in Section 7.4.1.

7. AODVv2 Protocol Messages

AODVv2 defines four message types: Route Request (RREQ), Route Reply (RREP), Route Reply Acknowledgement (RREP_Ack), and Route Error (RERR).

Each AODVv2 message is defined as a set of Data Elements. Rules for the generation, reception and regeneration of each message type are described in the following sections. Section 8 discusses how the Data Elements map to [RFC5444] Message TLVs, Address Blocks, and Address TLVs.

7.1. Route Request (RREQ) Message

Route Request messages are used in route discovery operations to request a route to a specified target address. RREQ messages have the following contents:

+-----------------------------------------------------------------+
|             msg_hop_limit, (optional) msg_hop_count             |
+-----------------------------------------------------------------+
|                           AddressList                           |
+-----------------------------------------------------------------+
|                   PrefixLengthList (optional)                   |
+-----------------------------------------------------------------+
|                OrigSeqNum, (optional) TargSeqNum                |
+-----------------------------------------------------------------+
|                           MetricType                            |
+-----------------------------------------------------------------+
|                           OrigMetric                            |
+-----------------------------------------------------------------+
|                     ValidityTime (optional)                     |
+-----------------------------------------------------------------+

+-----------------------------------------------------------------+
|             msg_hop_limit, (optional) msg_hop_count             |
+-----------------------------------------------------------------+
|                        AckReq (optional)                        |
+-----------------------------------------------------------------+
|                           AddressList                           |
+-----------------------------------------------------------------+
|                   PrefixLengthList (optional)                   |
+-----------------------------------------------------------------+
|                           TargSeqNum                            |
+-----------------------------------------------------------------+
|                           MetricType                            |
+-----------------------------------------------------------------+
|                           TargMetric                            |
+-----------------------------------------------------------------+
|                     ValidityTime (optional)                     |
+-----------------------------------------------------------------+

+-----------------------------------------------------------------+
|                          msg_hop_limit                          |
+-----------------------------------------------------------------+
|                       PktSource (optional)                      |
+-----------------------------------------------------------------+
|                           AddressList                           |
+-----------------------------------------------------------------+
|                   PrefixLengthList (optional)                   |
+-----------------------------------------------------------------+
|                       SeqNumList (optional)                     |
+-----------------------------------------------------------------+
|                          MetricTypeList                         |
+-----------------------------------------------------------------+

  /-------------------------\
 / +----------------+        \
/  |  AODVv2 Router |         \
|  |  191.0.2.2/32  |         |
|  +----------------+         |            Routable
|                       +-----+--------+   Prefix
|                       |     ENAR     |  /191.0.2.0/24
|                       | AODVv2 Router| /
|                       |  191.0.2.1   |/      /---------------\
|                       | serving net  +------+    External     \
|                       | 191.0.2.0/24 |      \     Network     /
|                       +-----+--------+       \---------------/
|         +----------------+  |
|         |  AODVv2 Router |  |
|         |  191.0.2.3/32  |  |
\         +----------------+  /
 \                           /
  \-------------------------/

    /*  Update the state of the route entry based on timeouts. Return 
        whether the route can be used for forwarding a packet. */

    Check_Route_State(route)
    {
        if (CurrentTime > route.ExpirationTime)
            route.State := Invalid;
        if ((CurrentTime - route.LastUsed > ACTIVE_INTERVAL + MAX_IDLETIME)
            AND (route.State != Unconfirmed) 
            AND (route.ExpirationTime == INFINITY_TIME)) //not a timed route
            route.State := Invalid;
        if ((CurrentTime - route.LastUsed > ACTIVE_INTERVAL) 
            AND (route.State != Unconfirmed) 
            AND (route.ExpirationTime == INFINITY_TIME)) //not a timed route
            route.State := Idle;
        if ((CurrentTime - route.LastSeqNumUpdate > MAX_SEQNUM_LIFETIME) 
            AND (route.State == Invalid OR route.State == Unconfirmed))
            /* remove route from route table */
        if ((CurrentTime - route.LastSeqNumUpdate > MAX_SEQNUM_LIFETIME) 
            AND (route.State != Invalid)
            route.SeqNum := 0;

        if (route still exists AND route.State != Invalid 
            AND Route.State != Unconfirmed)
            return TRUE;
        else
            return FALSE;   
    }   

/* Compare incoming route information to stored route, and if better, 
use to update stored route.  */

Process_Routing_Info (advRte)
{
    rte := Fetch_Route_Table_Entry (advRte);
    if (!rte exists)
    {
        rte := Create_Route_Table_Entry(advRte);
        return rte;
    }

    if (AdvRte.SeqNum > Route.SeqNum        /* stored route is stale */
        OR
        (AdvRte.SeqNum == Route.SeqNum                /* same SeqNum */
         AND    
         ((Route.State == Invalid AND LoopFree(advRte, rte))
                                         /* advRte can repair stored */
          OR AdvRte.Cost < Route.Metric)))       /* advRte is better */
    {
        if (advRte is from a RREQ)
            rte := Create_Route_Table_Entry(advRte);
        else
            Update_Route_Table_Entry (rte, advRte);
    }
    return rte;
}

/* Lookup a route table entry matching an advertised route */

Fetch_Route_Table_Entry (advRte)
{
    foreach (rteTableEntry in rteTable)
    {
        if (rteTableEntry.Address == advRte.Address 
            AND rteTableEntry.MetricType == advRte.MetricType)
            return rteTableEntry;
    }
    return null;
}

/* Lookup a route table entry matching address and metric type */

Fetch_Route_Table_Entry (destination, metricType)
{
    foreach (rteTableEntry in rteTable)
    {
        if (rteTableEntry.Address == destination 
            AND rteTableEntry.MetricType == metricType)
            return rteTableEntry;
    }
    return null;
}

/* Update a route table entry using AdvRte in received RteMsg */

Update_Route_Table_Entry (rte, advRte);
{
    rte.SeqNum := advRte.SeqNum;
    rte.NextHop := advRte.NextHopIp;
    rte.NextHopInterface := advRte.NextHopIntf;
    rte.LastUsed := CurrentTime;
    rte.LastSeqNumUpdate := CurrentTime;
    if (validityTime)
        rte.ExpirationTime := CurrentTime + advRte.ValidityTime;
    else
        rte.ExpirationTime := INFINITY_TIME;

    rte.Metric := advRte.Cost;
    if (rte.State == Invalid)
        rte.State := Idle (if advRte is from RREP);
                     or Unconfirmed (if advRte is from RREQ);
}

/* Create a route table entry from address and prefix length */

Create_Route_Table_Entry (address, prefixLength, seqNum, metricType)
{
    rte := allocate_memory();
    rte.Address := address;
    rte.PrefixLength := prefixLength;
    rte.SeqNum := seqNum;
    rte.MetricType := metricType;
}


/* Create a route table entry from the advertised route */

Create_Route_Table_Entry(advRte)
{
    rte := allocate_memory();

    rte.Address := advRte.Address;
    if (advRte.PrefixLength)
        rte.PrefixLength := advRte.PrefixLength;
    else
        rte.PrefixLength := maxPrefixLenForAddressFamily;

    rte.SeqNum := advRte.SeqNum;
    rte.NextHop := advRte.NextHopIp;
    rte.NextHopInterface := advRte.NextHopIntf;
    rte.LastUsed := CurrentTime;
    rte.LastSeqNumUpdate := CurrentTime;
    if (validityTime)
        rte.ExpirationTime := CurrentTime + advRte.ValidityTime;
    else
        rte.ExpirationTime := INFINITY_TIME;
    rte.MetricType := advRte.MetricType;
    rte.Metric := advRte.Metric;
    rte.State := Idle (if advRte is from RREP);
                 or Unconfirmed (if advRte is from RREQ);
}

/* Return TRUE if the route advRte is LoopFree compared to rte */

LoopFree(advRte, rte)
{
    if (advRte.Cost <= rte.Cost)
        return TRUE;
    else
        return FALSE;
}

/* Find an entry in the RteMsg table matching the given 
   message's msg-type, OrigAddr, TargAddr, MetricType   */

Fetch_Rte_Msg_Table_Entry (rteMsg)
{
    foreach (entry in RteMsgTable)
    {
        if (entry.msg-type == rteMsg.msg-type 
            AND entry.OrigAddr == rteMsg.OrigAddr 
            AND entry.TargAddr == rteMsg.TargAddr 
            AND entry.MetricType == rteMsg.MetricType)
                return entry;
    }
    return NULL;
}

/* Update the multicast route message suppression table based on the 
   received RteMsg, return true if it was created or the SeqNum was 
   updated (i.e. it needs to be regenerated) */

Update_Rte_Msg_Table(rteMsg)
{
    /* search for a comparable entry */
    entry := Fetch_Rte_Msg_Table_Entry(rteMsg);

    /* if there is none, create one */
    if (entry does not exist)
    {
        entry.MessageType := rteMsg.msg_type;
        entry.OrigAddr := rteMsg.OrigAddr;
        entry.TargAddr := rteMsg.TargAddr;
        entry.OrigSeqNum := rteMsg.origSeqNum; // (if present)
        entry.TargSeqNum := rteMsg.targSeqNum; // (if present)
        entry.MetricType := rteMsg.MetricType; 
        entry.Metric := rteMsg.OrigMetric; // (for RREQ)
                     or rteMsg.TargMetric; // (for RREP) 
        entry.Timestamp := CurrentTime;
        return TRUE;
    }

    /* if current entry is stale */
    if (
    (rteMsg.msg-type == RREQ AND entry.OrigSeqNum < rteMsg.OrigSeqNum)
    OR
    (rteMsg.msg-type == RREP AND entry.TargSeqNum < rteMsg.TargSeqNum))
    {
        entry.OrigSeqNum := rteMsg.OrigSeqNum; // (if present)
        entry.TargSeqNum := rteMsg.TargSeqNum; // (if present)
        entry.Timestamp := CurrentTime;
        return TRUE;
    }

    /* if received rteMsg is stale */
    if ( 
    (rteMsg.msg-type == RREQ AND entry.OrigSeqNum > rteMsg.OrigSeqNum)
    OR
    (rteMsg.msg-type == RREP AND entry.TargSeqNum > rteMsg.TargSeqNum))
    {
        entry.Timestamp := CurrentTime;
        return FALSE;
    }

    /* if same SeqNum but rteMsg has lower metric */
    if (entry.Metric > rteMsg.Metric)
        entry.Metric := rteMsg.Metric;

    entry.Timestamp := CurrentTime;
    return FALSE;
}

/*  This pseudocode shows possible RFC 5444 actions, and would not 
    be performed by the AODVv2 implementation. It is shown only to 
    provide more understanding about the AODVv2 message that will be 
    constructed by RFC 5444.
    MAL := Message Address Length
    MF  := Message Flags
    Size := number of octets in MsgHdr, AddrBlk, AddrTLVs  */

Build_RFC_5444_Message_Header (msgType, Flags, AddrFamily, Size, 
    hopLimit, hopCount, tlvLength)
{
    /* Build RFC 5444 message header fields */
    msg-type := msgType;
    MF := Flags;
    MAL := 3 or 15;  // for IPv4 or IPv6
    msg-size := Size;
    msg-hop-limit := hopLimit;
    if (hopCount != 0)  /* if hopCount is 0, do not include */
        msg-hop-count := hopCount;
    msg.tlvs-length := tlvLength;
}

/*  Generate a route request message to find a route from OrigAddr
    to TargAddr using the given MetricType
    origAddr   := IP address of Router Client which generated the 
                  packet to be forwarded
    origPrefix := prefix length associated with the Router Client
    targAddr   := destination IP address in the packet to be forwarded
    targSeqNum := sequence number in existing route to targAddr
    mType      := metric type for the requested route   */

Generate_RREQ(origAddr, origPrefix, targAddr, targSeqNum, mType)
{
    /* Increment sequence number in nonvolatile storage */
    mySeqNum := (1 + mySeqNum);

    /* Marshall parameters */
    outRREQ.HopLimit := MAX_HOPCOUNT;
    outRREQ.HopCount := 0;                              // if included 
    outRREQ.MetricType := mType;   //include if not DEFAULT_METRIC_TYPE
    outRREQ.OrigAddr := origAddr; 
    outRREQ.TargAddr := targAddr;
    outRREQ.OrigPrefixLen := origPrefix; //include if not address length
    outRREQ.OrigSeqNum := mySeqNum;
    outRREQ.TargSeqNum := targSeqNum;            //included if available
    outRREQ.OrigMetric := Route[OrigAddr].Metric;       //zero by default
    outRREQ.ValidityTime := limit for route to OrigAddr;   //if required 

    /* Build Address Blk using prefix length information from 
       outRREQ.OrigPrefixLen if necessary */
    AddrBlk := {outRREQ.OrigAddr, outRREQ.TargAddr};

    /* Include sequence numbers in appropriate Address Block TLVs */
    /* OrigSeqNum Address Block TLV */
    origSeqNumAddrBlkTlv.value := outRREQ.OrigSeqNum;
    /* TargSeqNum Address Block TLV */
    if (outRREQ.TargSeqNum is known)
        targSeqNumAddrBlkTlv.value := outRREQ.TargSeqNum;

    /* Build Metric Address Block TLV, include Metric AddrBlkTlv 
       Extension type if a non-default metric */
    metricAddrBlkTlv.value := outRREQ.OrigMetric;
    if (outRREQ.MetricType != DEFAULT_METRIC_TYPE)
        metricAddrBlkTlv.typeExtension := outRREQ.MetricType;
    
    if (outRREQ.ValidityTime is required)
    {
        /* Build VALIDITY_TIME Address Block TLV */
        VALIDITY_TIMEAddrBlkTlv.value := outRREQ.ValidityTime;
    }

    Build_RFC_5444_Message_Header (RREQ, 4, IPv4 or IPv6, NN,
        outRREQ.HopLimit, outRREQ.HopCount, tlvLength);

    /* multicast RFC 5444 message to LL-MANET-Routers */
}

/*  Process a RREQ received on link L */

Receive_RREQ (inRREQ, L)
{
    if (inRREQ.NbrIP present in blacklist) 
    {
        if (blacklist_expiration_time < CurrentTime)
            return; // don't process or regenerate RREQ
        else
            remove nbrIP from blacklist;
    }
    if (inRREQ does not contain msg_hop_limit, OrigAddr,
        TargAddr, OrigSeqNum, OrigMetric)
        return;
    if (msg_hop_count > MAX_HOPCOUNT)
        return;
    if (msg_hop_limit < 0)
        return;
    if (inRREQ.OrigAddr and inRREQ.TargAddr are not valid routable 
        and unicast addresses)
        return;
    if (inRREQ.MetricType is present but an unknown value)
        return;
    if (inRREQ.OrigMetric > MAX_METRIC[inRREQ.MetricType] - Cost(L))
        return;

    /* Extract inRREQ values */
    advRte.Address := inRREQ.OrigAddr;
    advRte.PrefixLength := inRREQ.OrigPrefixLen; (if present)
                        or the address length of advRte.Address;
    advRte.SeqNum := inRREQ.OrigSeqNum;
    advRte.MetricType := inRREQ.MetricType;
    advRte.Metric := inRREQ.OrigMetric;
    advRte.Cost := inRREQ.OrigMetric + Cost(L);
                                //according to the indicated MetricType
    advRte.ValidityTime := inRREQ.ValidityTime; //if present
    advRte.NextHopIP := inRREQ.NbrIP;
    advRte.NextHopIntf := inRREQ.Netif;
    advRte.HopCount := inRREQ.HopCount;
    advRte.HopLimit := inRREQ.HopLimit;

    rte := Process_Routing_Info (advRte);

    /*  Update the RteMsgTable and determine if the RREQ needs
        to be regenerated */
    regenerate := Update_Rte_Msg_Table(inRREQ); 

    if (inRREQ.TargAddr is in Router Client list)
        Generate_RREP(inRREQ, rte);
    else if (regenerate)
        Regenerate_RREQ(inRREQ, rte);
}

/*  Called from receive_RREQ() 
    rte := the route to OrigAddr */

Regenerate_RREQ (inRREQ, rte) 
{
    outRREQ.HopLimit := inRREQ.HopLimit - 1;
    if (outRREQ.HopLimit == 0)
        return; // don't regenerate

    if (inRREQ.HopCount exists)
    {
        if (inRREQ.HopCount >= MAX_HOPCOUNT)
            return; // don't regenerate
        outRREQ.HopCount := inRREQ.HopCount + 1;
    }

    /* Marshall parameters */
    outRREQ.MetricType := rte.MetricType;
    outRREQ.OrigAddr := rte.Address;
    outRREQ.TargAddr := inRREQ.TargAddr;
    /* include prefix length if not equal to address length */
    outRREQ.OrigPrefixLen := rte.PrefixLength; 
    outRREQ.OrigSeqNum := rte.SeqNum;
    outRREQ.TargSeqNum := inRREQ.TargSeqNum; // if present
    outRREQ.OrigMetric := rte.Metric;
    outRREQ.ValidityTime := rte.ValidityTime;
                         or the time limit this router wishes to put on 
                         route to OrigAddr

    /*  Build Address Block using prefix length information from 
        outRREQ.OrigPrefixLen if necessary */
    AddrBlk := {outRREQ.OrigAddr, outRREQ.TargAddr};
    
    /* Include sequence numbers in appropriate Address Block TLVs */
    /* OrigSeqNum Address Block TLV */
    origSeqNumAddrBlkTlv.value := outRREQ.OrigSeqNum;
    /* TargSeqNum Address Block TLV */
    if (outRREQ.TargSeqNum is known) 
        targSeqNumAddrBlkTlv.value := outRREQ.TargSeqNum;

    /* Build Metric Address Block TLV, include Metric AddrBlkTlv 
       Extension type if a non-default metric */
    metricAddrBlkTlv.value := outRREQ.OrigMetric;
    if (outRREQ.MetricType != DEFAULT_METRIC_TYPE)
        metricAddrBlkTlv.typeExtension := outRREQ.MetricType;

    if (outRREQ.ValidityTime is required)
    {
        /* Build VALIDITY_TIME Address Block TLV */
        VALIDITY_TIMEAddrBlkTlv.value := outRREQ.ValidityTime;
    }
    Build_RFC_5444_Message_Header (RREQ, 4, IPv4 or IPv6, NN,
        outRREQ.HopLimit, outRREQ.HopCount, tlvLength);

    /*  Multicast RFC 5444 message to LL-MANET-Routers, or if
        inRREQ was unicast, the message can be unicast to the next
        hop on the route to TargAddr, if known */
}

Generate_RREP(inRREQ, rte)
{
    /* Increment sequence number in nonvolatile storage */
    mySeqNum := (1 + mySeqNum);

    /* Marshall parameters */
    outRREP.HopLimit := inRREQ.HopCount;
    outRREP.HopCount := 0;
    /* Include the AckReq when:
       - previous RREP does not seem to enable any data flow, OR
       - when RREQ is received from same OrigAddr after RREP was
         unicast to rte.NextHop     */
    outRREP.AckReq := TRUE or FALSE; //TRUE if acknowledgement required
    /* if included, set timeout RREP_Ack_SENT_TIMEOUT */

    if (rte.MetricType != DEFAULT_METRIC_TYPE)
        outRREP.MetricType := rte.MetricType;
    outRREP.OrigAddr := inRREQ.Address;
    outRREP.TargAddr := rte.TargAddr;
    outRREP.TargPrefixLen := rte.PrefixLength; //if not address length
    outRREP.TargSeqNum := mySeqNum;
    outRREP.TargMetric := rte.Metric; 
    outRREP.ValidityTime := limit for route to TargAddr;   //if required

    if (outRREP.AckReq == TRUE)
        /* include AckReq Message TLV */

    /*  Build Address Block using prefix length information from 
        outRREP.TargPrefixLen if necessary */
    AddrBlk := {outRREP.OrigAddr, outRREP.TargAddr};

    /* TargSeqNum Address Block TLV */
    targSeqNumAddrBlkTlv.value := outRREP.TargSeqNum;

    /* Build Metric Address Block TLV include Metric AddrBlkTlv 
       Extension type if a non-default metric */
    metricAddrBlkTlv.value := outRREP.TargMetric;
    if (outRREP.MetricType != DEFAULT_METRIC_TYPE)
        metricAddrBlkTlv.typeExtension := outRREP.MetricType;

    if (outRREP.ValidityTime is required)
    {
        /* Build VALIDITY_TIME Address Block TLV */
        VALIDITY_TIMEAddrBlkTlv.value := outRREP.ValidityTime;
    }

    Build_RFC_5444_Message_Header (RREP, 4, IPv4 or IPv6, NN,
        outRREP.HopLimit, outRREQ.HopCount, tlvLength);

    /* unicast RFC 5444 message to rte[OrigAddr].NextHop */
}

/*  Process a RREP received on link L */

Receive_RREP (inRREP, L)
{
    if (inRREP.NbrIP present in blacklist)
    {
        if (blacklist_expiration_time < CurrentTime)
            return;   // don't process or regenerate RREP
        else
            remove NbrIP from blacklist;
    }

    if (inRREP does not contain msg_hop_limit, OrigAddr,
            TargAddr, TargSeqNum, TargMetric)
        return;
    if (msg_hop_count > MAX_HOPCOUNT)
        return;
    if (msg_hop_limit < 0)
        return;
    if (inRREP.OrigAddr and inRREQ.TargAddr are not
        valid routable and unicast addresses)
        return;
    if (inRREP.MetricType is present but an unknown value)
        return;
    if (inRREP.TargMetric > MAX_METRIC[inRREP.MetricType])
        return;

    /* Extract inRREP values */
    advRte.Address := inRREP.TargAddr;
    advRte.PrefixLength := inRREP.TargPrefixLen; //if present
                        or the address length of advRte.Address;
    advRte.SeqNum := inRREP.TargSeqNum;
    advRte.MetricType := inRREP.MetricType;
    advRte.Metric := inRREP.TargMetric;
    advRte.Cost := inRREP.TargMetric + Cost(L);
                        //according to the indicated MetricType
    advRte.ValidityTime := inRREP.ValidityTime; //if present
    advRte.NextHopIP := inRREP.NbrIP;
    advRte.NextHopIntf := inRREP.Netif;
    advRte.HopCount := inRREP.HopCount;
    advRte.HopLimit := inRREP.HopLimit; //if included

    rte := Process_Routing_Info (advRte);

`   if (inRREP includes AckReq data element)
        Generate_RREP_Ack(inRREP);

    /*  Update the RteMsgTable and determine if the RREP needs
        to be regenerated */
    regenerate := Update_Rte_Msg_Table(inRREP);

    if (inRREP.TargAddr is in the Router Client list)
        send_buffered_packets(rte);    /* start to use the route */
    else if (regenerate)
        Regenerate_RREP(inRREP, rte);
}

Regenerate_RREP(inRREP, rte)
{
    if (rte does not exist)
    {
        Generate_RERR(inRREP);
        return;
    }

    outRREP.HopLimit := inRREP.HopLimit - 1;
    if (outRREP.HopLimit == 0) /* don't regenerate */
        return;

    if (inRREP.HopCount exists)
    {
        if (inRREP.HopCount >= MAX_HOPCOUNT)
            return; // don't regenerate the RREP
        outRREP.HopCount := inRREP.HopCount + 1;
    }

    /* Marshall parameters */
    /* Include the AckReq when:
       - previous unicast RREP seems not to enable data flow, OR
       - when RREQ is received from same OrigAddr after RREP
         was unicast to rte.NextHop     */
    outRREP.AckReq := TRUE or FALSE; //TRUE if acknowledgement required
    /* if included, set timeout RREP_Ack_SENT_TIMEOUT */

    if (rte.MetricType != DEFAULT_METRIC_TYPE)
        outRREP.MetricType := rte.MetricType;
    outRREP.OrigAddr := inRREP.OrigAddr;
    outRREP.TargAddr := rte.Address;
    outRREP.TargPrefixLen := rte.PrefixLength; //if not address length
    outRREP.TargSeqNum := rte.SeqNum;
    outRREP.TargMetric := rte.Metric;
    outRREP.ValidityTime := limit for route to TargAddr;   //if required
    outRREP.NextHop := rte.NextHop

    if (outRREP.AckReq == TRUE)
        /* include AckReq Message TLV */

    /*  Build Address Block using prefix length information from
        outRREP.TargPrefixLen if necessary */
    AddrBlk := {outRREP.OrigAddr, outRREP.TargAddr};    

    /* TargSeqNum Address Block TLV */
    targSeqNumAddrBlkTlv.value := outRREP.TargSeqNum;

    /* Build Metric Address Block TLV include Metric AddrBlkTlv 
       Extension type if a non-default metric */
    metricAddrBlkTlv.value := outRREP.TargMetric;
    if (outRREP.MetricType != DEFAULT_METRIC_TYPE)
        metricAddrBlkTlv.typeExtension := outRREP.MetricType;

    if (outRREP.ValidityTime is required)
    {
        /* Build VALIDITY_TIME Address Block TLV */
        VALIDITY_TIMEAddrBlkTlv.value := outRREP.ValidityTime;
    }

    Build_RFC_5444_Message_Header (RREP, 4, IPv4 or IPv6, NN,
        outRREP.HopLimit, 0, tlvLength);
        
    /* unicast RFC 5444 message to rte[OrigAddr].NextHop */ 
}

/* To be sent when a received RREP includes the AckReq data element */

Generate_RREP_Ack(inRREP)
{
    Build_RFC_5444_Message_Header (RREP_Ack, 4, IPv4 or IPv6, NN, 
        1, 0, 0);
    /* unicast RFC 5444 message to inRREP.NbrIP */
}

Receive_RREP_Ack(inRREP_Ack)
{
    /* cancel timeout event for the node sending RREP_Ack */
}

Timeout_RREP_Ack(outRREP)
{
    if (numRetries < RREP_RETRIES)
        /* resend RREP and double the previous timeout */
    else
        /* insert unresponsive node into blacklist */
}

/*  Generate a Route Error message.     
    errorType := undeliverablePacket or brokenLink  */

Generate_RERR(errorType, triggerPkt, brokenLinkNbrIp)
{
    switch (errorType)
    {
    case (brokenLink):
        doGenerate := FALSE;
        num-broken-addr := 0;
        precursors[] := new empty precursor list;
        outRERR.HopLimit := MAX_HOPCOUNT;
        /* find routes which are now Invalid */ 
        foreach (rte in route table)
        {
            if (brokenLinkNbrIp == rte.NextHop 
                AND (rte.State == Active 
                     OR
                     (rte.State == Idle AND ENABLE_IDLE_IN_RERR)))
             {
                if (rte.State == Active)
                    doGenerate := TRUE;
                rte.State := Invalid;
                precursors += rte.Precursors (if any);
                outRERR.AddressList[num-broken-addr] := rte.Address;
                outRERR.PrefixLengthList[num-broken-addr] :=
                                                 rte.PrefixLength;
                outRERR.SeqNumList[num-broken-addr] := rte.SeqNum;
                outRERR.MetricTypeList[num-broken-addr] := rte.MetricType
                num-broken-addr := num-broken-addr + 1;
            }
        }       
    }
    case (undeliverablePacket):
        doGenerate := TRUE;
        num-broken-addr := 1;
        outRERR.HopLimit := MAX_HOPCOUNT;
        outRERR.PktSource := triggerPkt.SrcIP;
                          or triggerPkt.TargAddr; //if pkt was a RREP
        outRERR.AddressList[0] := triggerPkt.DestIP; 
                               or triggerPkt.OrigAddr; //if pkt was RREP
        /* optional to include outRERR.PrefixLengthList, outRERR.SeqNumList
           and outRERR.MetricTypeList */        
    }
    
    if (doGenerate == FALSE)
        return; 
            
    if (triggerPkt exists)
    { 
        /* Build PktSource Message TLV */
        pktSourceMessageTlv.value := outRERR.PktSource;
    }

    /*  The remaining steps add address, prefix length, sequence 
        number and metric type information for each unreachable address, 
        while conforming to the allowed MTU. If the MTU is reached, a new 
        message MUST be created. */
    
    /*  Build Address Block using prefix length information from
        outRERR.PrefixLengthList[] if necessary */
    AddrBlk := outRERR.AddressList[];
    
    /*  Optionally, add SeqNum Address Block TLV, including index values */
    seqNumAddrBlkTLV := outRERR.SeqNumList[]; 
    
    if (outRERR.MetricTypeList contains non-default MetricTypes)
        /* include Metric Address Block TLVs with Type Extension set to 
           MetricType, including index values if necessary */
        metricAddrBlkTlv.typeExtension := outRERR.MetricTypeList[];

    Build_RFC_5444_Message_Header (RERR, 4, IPv4 or IPv6, NN,
        outRERR.HopLimit, 0, tlvLength);

    if (undeliverablePacket)
        /* unicast outRERR to rte[outRERR.PktSource].NextHop */
    else if (brokenLink)
        /* unicast to precursors, or multicast to LL-MANET-Routers */
}

Receive_RERR (inRERR)
{
    if (inRERR does not contain msg_hop_limit and at least
        one unreachable address)
        return;

    /*  Extract inRERR values, copy relevant unreachable addresses,
        their prefix lengths, and sequence numbers to outRERR */
    num-broken-addr := 0;
    precursors[] := new empty precursor list;
    foreach (unreachableAddress in inRERR.AddressList)
    {
        if (unreachableAddress is not valid routable and unicast)
            continue;
        if (unreachableAddress MetricType is present but an unknown value)
            return;
        
        /*  Find a matching route table entry, assume
            DEFAULT_METRIC_TYPE if no MetricType included */
        rte := Fetch_Route_Table_Entry (unreachableAddress,
                                        unreachableAddress MetricType)
        if (rte does not exist)
            continue;
        if (rte.State == Invalid)/* ignore already invalid routes */
            continue;
        if ((rte.NextHop != inRERR.NbrIP 
            OR
            rte.NextHopInterface != inRERR.Netif)
            AND (PktSource is not present OR is not a Router Client))
            continue;
        if (unreachableAddress SeqNum (if known) < rte.SeqNum)
            continue;
        
        /* keep a note of all precursors of newly Invalid routes */
        precursors += rte.Precursors; //if any

        /* assume prefix length is address length if not included */
        if (rte.PrefixLength != unreachableAddress prefixLength)
        {
            /* create new route with unreachableAddress information */
            invalidRte := Create_Route_Table_Entry(unreachableAddress,
                                        unreachableAddress PrefixLength,
                                        unreachableAddress SeqNum, 
                                        unreachableAddress MetricType);
            invalidRte.State := Invalid;

            if (rte.PrefixLength > unreachableAddress prefixLength)
                expunge_route(rte);
            rte := invalidRte;
        }
        else if (rte.PrefixLength == unreachableAddress prefixLength)
            rte.State := Invalid;

        outRERR.AddressList[num-broken-addr] := rte.Address;
        outRERR.PrefixLengthList[num-broken-addr] := rte.PrefixLength;
        outRERR.SeqNumList[num-broken-addr] := rte.SeqNum;
        outRERR.MetricTypeList[num-broken-addr] := rte.MetricType;
        num-broken-addr := num-broken-addr + 1;
    }

    if (num-broken-addr AND (PktSource is not present OR PktSource is not
        a Router Client))
        Regenerate_RERR(outRERR, inRERR, precursors);
}

Regenerate_RERR (outRERR, inRERR, precursors)
{
    /* Marshal parameters */
    outRERR.HopLimit := inRERR.HopLimit - 1;
    if (outRERR.HopLimit == 0) // don't regenerate
        return;

    outRERR.PktSource := inRERR.PktSource; //if included
    /*  AddressList[], SeqNumList[], and PrefixLengthList[] are 
        already up-to-date */

    if (outRERR.PktSource exists)
    {
        /* Build PktSource Message TLV */
        pktSourceMessageTlv.value := outRERR.PktSource;
    }

    /*  Build Address Block using prefix length information from 
        outRERR.PrefixLengthList[] if necessary */
    AddrBlk := outRERR.AddressList[];

    /*  Optionally, add SeqNum Address Block TLV, including index values */
    seqNumAddrBlkTLV := outRERR.SeqNumList[]; 
    
    if (outRERR.MetricTypeList contains non-default MetricTypes)
        /* include Metric Address Block TLVs with Type Extension set to 
           MetricType, including index values if necessary */
        metricAddrBlkTlv.typeExtension := outRERR.MetricTypeList[];

    Build_RFC_5444_Message_Header (RERR, 4, IPv4 or IPv6, NN,
        outRERR.HopLimit, 0, tlvLength);
        
    if (outRERR.PktSource exists)
        /*  unicast RFC 5444 message to next hop towards 
            outRERR.PktSource */
    else if (number of precursors == 1) 
        /*  unicast RFC 5444 message to precursors[0] */
    else if (number of precursors > 1) 
        /*  unicast RFC 5444 message to all precursors, or multicast
            RFC 5444 message to RERR_PRECURSORS if preferable */
    else
        /* multicast RFC 5444 message to LL-MANET-Routers */
}