Metric Types

Name of MetricType	Type	Metric Size
Unallocated	0 -- 2	TBD
Hop Count	3 - TBD	1 octet
Unallocated	4 -- 254	TBD
Reserved	255	Undefined

15. Security Considerations

The objective of the AODVv2 protocol is for each router to communicate reachability information about addresses for which it is responsible. Positive routing information (i.e. a route exists) is distributed via RREQ and RREP messages. Negative routing information (i.e. a route does not exist) is distributed via RERRs. AODVv2 routers store the information contained in these messages in order to properly forward data packets, and they generally provide this information to other AODVv2 routers.

This section does not mandate any specific security measures. Instead, this section describes various security considerations and potential avenues to secure AODVv2 routing. Security for authentication of AODVv2 routers, and/or encryption of traffic is dealt with by the underlying transport mechanism (e.g., by using the techniques for Authentication, Integrity, and Confidentiality documented in [RFC5444]). The most important security mechanisms for AODVv2 routing are integrity/authentication and confidentiality.

In situations where routing information or router identity are suspect, integrity and authentication techniques SHOULD be applied to AODVv2 messages. In these situations, routing information that is distributed over multiple hops SHOULD also verify the integrity and identity of information based on originator of the routing information.

A digital signature could be used to identify the source of AODVv2 messages and information, along with its authenticity. A nonce or timestamp SHOULD also be used to protect against replay attacks. S/MIME and OpenPGP are two authentication/integrity protocols that could be adapted for this purpose.

In situations where confidentiality of AODVv2 messages is important, cryptographic techniques can be applied.

In certain situations, for example sending a RREP or RERR, an AODVv2 router could include proof that it has previously received valid routing information to reach the destination, at one point of time in the past. In situations where routers are suspected of transmitting maliciously erroneous information, the original routing information along with its security credentials SHOULD be included.

Note that if multicast is used, any confidentiality and integrity algorithms used MUST permit multiple receivers to handle the message.

Routing protocols, however, are prime targets for impersonation attacks. In networks where the node membership is not known, it is difficult to determine the occurrence of impersonation attacks, and security prevention techniques are difficult at best. However, when the network membership is known and there is a danger of such attacks, AODVv2 messages must be protected by the use of authentication techniques, such as those involving generation of unforgeable and cryptographically strong message digests or digital signatures. While AODVv2 does not place restrictions on the authentication mechanism used for this purpose, IPsec Authentication Message (AH) is an appropriate choice for cases where the nodes share an appropriate security association that enables the use of AH.

In particular, routing messages SHOULD be authenticated to avoid creation of spurious routes to a destination. Otherwise, an attacker could masquerade as that destination and maliciously deny service to the destination and/or maliciously inspect and consume traffic intended for delivery to the destination. RERR messages SHOULD be authenticated in order to prevent malicious nodes from disrupting routes between communicating nodes.

If the mobile nodes in the ad hoc network have pre-established security associations, the purposes for which the security associations are created should include that of authorizing the processing of AODVv2 control packets. Given this understanding, the mobile nodes should be able to use the same authentication mechanisms based on their IP addresses as they would have used otherwise.

Most AODVv2 messages are transmitted to the multicast address LL-MANET-Routers [RFC5498]. It is therefore required for security that AODVv2 neighbors exchange security information that can be used to insert an ICV [RFC6621] into the AODVv2 message block [RFC5444]. This enables hop-by-hop security. For destination-only RREP discovery procedures, AODVv2 routers that share a security association SHOULD use the appropriate mechanisms as specified in RFC 6621. The establishment of these security associations is out of scope for this document.

16. Acknowledgments

AODVv2 is a descendant of the design of previous MANET on-demand protocols, especially AODV [RFC3561] and DSR [RFC4728]. Changes to previous MANET on-demand protocols stem from research and implementation experiences. Thanks to Elizabeth Belding and Ian Chakeres for their long time authorship of AODV. Additional thanks to Derek Atkins, Emmanuel Baccelli, Abdussalam Baryun, Ramon Caceres, Thomas Clausen, Christopher Dearlove, Ulrich Herberg, Henner Jakob, Luke Klein-Berndt, Lars Kristensen, Tronje Krop, Koojana Kuladinithi, Kedar Namjoshi, Alexandru Petrescu, Henning Rogge, Fransisco Ros, Pedro Ruiz, Christoph Sommer, Lotte Steenbrink, Romain Thouvenin, Richard Trefler, Jiazi Yi, Seung Yi, and Cong Yuan, for their reviews AODVv2 and DYMO, as well as numerous specification suggestions.

17. References

17.1. Normative References

[RFC2119]	Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
[RFC4291]	Hinden, R. and S. Deering, "IP Version 6 Addressing Architecture", RFC 4291, February 2006.
[RFC5082]	Gill, V., Heasley, J., Meyer, D., Savola, P. and C. Pignataro, "The Generalized TTL Security Mechanism (GTSM)", RFC 5082, October 2007.
[RFC5444]	Clausen, T., Dearlove, C., Dean, J. and C. Adjih, "Generalized Mobile Ad Hoc Network (MANET) Packet/Message Format", RFC 5444, February 2009.
[RFC5497]	Clausen, T. and C. Dearlove, "Representing Multi-Value Time in Mobile Ad Hoc Networks (MANETs)", RFC 5497, March 2009.
[RFC5498]	Chakeres, I., "IANA Allocations for Mobile Ad Hoc Network (MANET) Protocols", RFC 5498, March 2009.
[RFC6551]	Vasseur, JP., Kim, M., Pister, K., Dejean, N. and D. Barthel, "Routing Metrics Used for Path Calculation in Low-Power and Lossy Networks", RFC 6551, March 2012.

17.2. Informative References

[I-D.perkins-irrep]	Perkins, C. and I. Chakeres, "Intermediate RREP for dynamic MANET On-demand (AODVv2) Routing", Internet-Draft draft-perkins-irrep-02, November 2012.
[Perkins94]	Perkins, C. and P. Bhagwat, "Highly Dynamic Destination-Sequenced Distance-Vector Routing (DSDV) for Mobile Computers", Proceedings of the ACM SIGCOMM '94 Conference on Communications Architectures, Protocols and Applications, London, UK, pp. 234-244, August 1994.
[Perkins99]	Perkins, C. and E. Royer, "Ad hoc On-Demand Distance Vector (AODV) Routing", Proceedings of the 2nd IEEE Workshop on Mobile Computing Systems and Applications, New Orleans, LA, pp. 90-100, February 1999.
[RFC2501]	Corson, M. and J. Macker, "Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations", RFC 2501, January 1999.
[RFC3561]	Perkins, C., Belding-Royer, E. and S. Das, "Ad hoc On-Demand Distance Vector (AODV) Routing", RFC 3561, July 2003.
[RFC4193]	Hinden, R. and B. Haberman, "Unique Local IPv6 Unicast Addresses", RFC 4193, October 2005.
[RFC4728]	Johnson, D., Hu, Y. and D. Maltz, "The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4", RFC 4728, February 2007.
[RFC4861]	Narten, T., Nordmark, E., Simpson, W. and H. Soliman, "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, September 2007.
[RFC5148]	Clausen, T., Dearlove, C. and B. Adamson, "Jitter Considerations in Mobile Ad Hoc Networks (MANETs)", RFC 5148, February 2008.
[RFC6130]	Clausen, T., Dearlove, C. and J. Dean, "Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)", RFC 6130, April 2011.
[RFC6621]	Macker, J., "Simplified Multicast Forwarding", RFC 6621, May 2012.

Appendix A. Example Algorithms for AODVv2 Protocol Operations

The following subsections show example algorithms for protocol operations required by AODVv2, including RREQ, RREP, RERR, and RREP_Ack.

Processing for RREQ, RREP, and RERR messages follows the following general outline:

1. Receive incoming message.
2. Update route table as appropriate.
3. Respond as needed, often regenerating the incoming message with updated information.

Once the route table has been updated, the information contained there is known to be the most recent available information for any fields in the outgoing message. For this reason, the algorithms are written as if outgoing message field values are assigned from the route table information, even though it is often equally appropriate to use fields from the incoming message.

AODVv2_algorithms:

• Process_Routing_Info
• Fetch_Route_Table_Entry
• Update_Route_Table_Entry
• Create_Route_Table_Entry
• LoopFree
• Update_Rte_Msg_Table
• Generate_RREQ
• Receive_RREQ
• Regenerate_RREQ
• Generate_RREP
• Receive_RREP
• Regenerate_RREP
• Generate_RERR
• Receive_RERR
• Regenerate_RERR
• Generate_RREP_Ack
• Receive_RREP_Ack
• Timeout RREP_Ack

The following lists indicate the meaning of the field names used in subsequent sections to describe message processing for the above algorithms.

RteMsg parameters, where rteMsg can be inRREQ, outRREQ, inRREP or outRREP:

• rteMsg.hopLimit
• rteMsg.hopCount
• rteMsg.ackReq (RREP only, optional)
• rteMsg.metricType (optional)
• rteMsg.origAddr
• rteMsg.targAddr
• rteMsg.origPrefixLen (optional)
• rteMsg.targPrefixLen (optional)
• rteMsg.origSeqNum (RREQ only)
• rteMsg.targSeqNum (optional in RREQ)
• rteMsg.origAddrMetric (RREQ only)
• rteMsg.targAddrMetric (RREP only)
• rteMsg.validityTime
• rteMsg.nbrIP

AdvRte has the following properties as described in Section 8.1:

• AdvRte.Address = OrigAddr (in a RREQ) or TargAddr (in a RREP)
• AdvRte.PrefixLength = PrefixLength for OrigAddr (in a RREQ) or TargAddr (in a RREP), or if not present, the maximum address length for the address family of AdvRte.Address
• AdvRte.SeqNum = SeqNum for OrigAddr (in a RREQ) or for TargAddr (in a RREP)
• AdvRte.MetricType = RteMsg.MetricType, if present, else DEFAULT_METRIC_TYPE
• AdvRte.Metric = RteMsg.Metric
• AdvRte.Cost = AdvRte.Metric + Cost(L) according to the indicated
• MetricType, where L is the link from the advertising router
• AdvRte.ValidityTime = ValidityTime in the RteMsg, if present
• AdvRte.NextHopIP = IP source of the RteMsg
• AdvRte.NextHopIntf = interface the RteMsg was received on
• AdvRte.HopCount = value from RteMsg header
• AdvRte.HopLimit = value from RteMsg header
• AdvRte.AckReq = true/false whether present in RteMsg (optional in RREP)

A route table entry has properties as described in Section 6.1:

• Route.Address
• Route.PrefixLength
• Route.SeqNum
• Route.NextHop
• Route.NextHopInterface
• Route.LastUsed
• Route.LastSeqNum
• Route.ExpirationTime
• Route.MetricType
• Route.Metric
• Route.State
• Route.Timed
• Route.Precursors (optional)

A.1. Subroutines for AODVv2 Operations

A.1.1. Process_Routing_Info

  /* Compare incoming route information to stored route, maybe use
     linkMetric: either Cost(inRREQ.netif) or (inRREP.netif) */
  Process_Routing_Info (advRte)
  {
    rte := Fetch_Route_Table_Entry (advRte);
    if (rte exists)
    {
      rte := Create_Route_Table_Entry(advRte);
      return rte;
    }

    if (!LoopFree(advRte, rte))
    {  /* incoming route cannot be guaranteed loop free */
       return null;
    }

    /* rule from 8.1 */
    if (
         (AdvRte.SeqNum > Route.SeqNum)  /* stored route is stale */
           OR
          ((AdvRte.SeqNum == Route.SeqNum)  /* same SeqNum */
            AND
          [((Route.State == Invalid))  /* advRte can repair stored */
            OR
       (AdvRte.Cost < Route.Metric)])) /* advRte is better */
    {
      Update_Route_Table_Entry (rte, advRte);
    }
    return rte;
  }

A.1.2. Fetch_Route_Table_Entry

    /* 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;
    }

A.1.3. Update_Route_Table_Entry

    /* 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 := Current_Time;
      rte.LastSeqNum := Current_Time;
      if (validityTime)
      {
         rte.ExpirationTime := Current_Time + advRte.validityTime;
         rte.Timed := true;
      }
      else
      {
         rte.Timed := false;
         rte.ExpirationTime := MAXTIME;
      }

      rte.Metric := advRte.Cost;
      if (rte.State == Invalid)
        rte.State := Idle;
    }

A.1.4. Create_Route_Table_Entry

  /* 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 := Current_Time
    rte.LastSeqnum := Current_Time
    if (validityTime)
    {
      rte.ExpirationTime := Current_Time + advRte.ValidityTime;
      rte.Timed := true;
    }
    else
    {
      rte.Timed := false;
      rte.ExpirationTime := MAXTIME;
    }
    rte.MetricType := advRte.MetricType;
    rte.Metric := advRte.Metric;
    rte.State := Idle;
  }

A.1.5. LoopFree

    /* return TRUE if the route R2 is LoopFree compared to R1 */
    LoopFree(advRte, rte)
    {
      if (advRte.Cost < rte.Cost)
         return true;
      else
         return false;
    }

A.1.6. Fetch_Rte_Msg_Table_Entry

    /* 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;
    }

A.1.7. Update_Rte_Msg_Table

    /* 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 (see 6.5 and 8.6) */
      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 (if present) or
                              DEFAULT_METRIC_TYPE
        entry.Timestamp := Current_Time
        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 := Current_Time
        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 := Current_Time
        return false;
      }

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

      entry.Timestamp := Current_Time
      return false;
    }

A.1.8. Build_RFC_5444_message_header

   /* 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 */
   Build_RFC_5444_message_header (msgType, Flags,
                 AddrFamily, Size, hopLimit, hopCount, tlvLength)
   {
      /* Build RFC 5444 message header fields */
      msg-type := msgType
      MF (Message Flags) := Flags
      MAL (Message Address Length) := 3 for IPv4, 15 for IPv6
      msg-size := Size (octets - counting MsgHdr, AddrBlk, AddrTLVs)
      msg-hop-limit := hopLimit
      if (hopCount != 0)    /* hopCount == 0 means do not include */
        msg-hop-count := hopCount
      msg.tlvs-length := tlvLength
   }

A.2. Example Algorithms for AODVv2 RREQ Operations

A.2.1. Generate_RREQ

    Generate_RREQ
    {
      /* Increment sequence number */
      mySeqNum := (1 + mySeqNum) /* from nonvolatile storage */

      /* Marshall parameters */
      outRREQ.hopLimit := MAX_HOPCOUNT   /* RFC 5444 */
      outRREQ.hopCount := (if included) 0
      outRREQ.metricType := if not DEFAULT_METRIC_TYPE,
                              metric type needed by application
      outRREQ.origAddr := IP address of Router Client which generated
                              the packet to be forwarded
      outRREQ.targAddr := destination IP address in
                              the packet to be forwarded
      outRREQ.origPrefixLen := if included, the prefix length
                              associated with the Router Client
      outRREQ.origSeqNum := mySeqNum
      outRREQ.targSeqNum := if known from route table,
                              target sequence number
      outRREQ.origAddrMetric := 0 (default) or
                                    MIN_METRIC(outRREQ.metricType)
      outRREQ.validityTime := if included, the validity time
                              for route to OrigAddr

      if (outRREQ.metricType != DEFAULT_METRIC_TYPE)
      { /* Build MetricType Message TLV */
        metricMsgTlv.value := outRREQ.metricType
      }

      /* Build Address Blk */
      AddrBlk := outRREQ.origAddr and outRREQ.targAddr addresses
            /* using prefix length information from
               outRREQ.origPrefixLen if necessary */

      /* Include each available Sequence Number in appropriate
         Address Block TLV */
      /* 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 */
      metricAddrBlkTlv.value := outRREQ.origAddrMetric

      if (outRREQ.validityTime is required)
      {
        /* Build VALIDITY_TIME Address Block TLV */
        VALIDITY_TIMEAddrBlkTlv.value := outRREQ.validityTime
      }

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

A.2.2. Receive_RREQ

   Receive_RREQ (inRREQ)
   {
     if (inRREQ.nbrIP present in blacklist) {
          if (blacklist_expiration_time < current_time)
             return;   /* don't process or regenerate RREQ... */
          else
            remove nbrIP from blacklist;
        }
     if (inRREQ does not contain msg_hop_limit, OrigAddr,
                             TargAddr, OrigSeqNum, OrigAddrMetric)
          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.origAddrMetric >
                       MAX_METRIC[inRREQ.metricType] - Cost(Link)
          return;

     /* Extract inRREQ values */
     advRte.Address = inRREQ.origAddr
     advRte.PrefixLength = inRREQ.origPrefixLen (if present),
                             or the maximum address length for the
                             address family of advRte.Address
     advRte.SeqNum = inRREQ.origSeqNum
     advRte.MetricType = inRREQ.metricType (if present),
                               else DEFAULT_METRIC_TYPE
     advRte.Metric = inRREQ.origAddrMetric
     advRte.Cost = inRREQ.origAddrMetric + Cost(L)
                    according to the indicated MetricType, where
                    L is the link from the advertising router
     advRte.ValidityTime = inRREQ.validityTime (if present)
     advRte.NextHopIP = inRREQ.nbrIP
     advRte.NextHopIntf = interface the RteMsg was received on
     advRte.HopCount = inRREQ.hopCount
     advRte.HopLimit = inRREQ.hopLimit

     rte = Process_Routing_Info (advRte)

     /* update the RteMsgTableand 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)
    }

A.2.3. Regenerate_RREQ

    Regenerate_RREQ (inRREQ, rte) /* called from receive_RREQ(),
                                rte is the route to OrigAddr */
    {
      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
      outRREQ.origPrefixLen := rte.PrefixLength
                              (if not equal to address length)
      outRREQ.origSeqNum := rte.SeqNum
      outRREQ.targSeqNum := inRREQ.targSeqNum /* if present */
      outRREQ.origAddrMetric := rte.Metric
      outRREQ.validityTime := rte.ValidityTime or length of time
                 HandlingRtr wishes to advertise route to OrigAddr

      if (outRREQ.metricType != DEFAULT_METRIC_TYPE)
      { /* Build MetricType Message TLV */
        metricMsgTlv.value := outRREQ.metricType
      }

      /* Build Address Block */
      AddrBlk := outRREQ.origAddr and outRREQ.targAddr addresses
           using prefix length information from outRREQ.origPrefixLen
           if necessary

      /* Include available Sequence Numbers in Address Block TLV */
      /* 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 */
      metricAddrBlkTlv.value = outRREQ.origAddrMetric

      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 */
    }

A.3. Example Algorithms for AODVv2 RREP Operations

A.3.1. Generate_RREP

    Generate_RREP(inRREQ, rte)
    {
      /* Increment Sequence Number */
      mySeqNum := (1 + mySeqNum) /* from nonvolatile storage */

      /* 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 := if included, TRUE otherwise FALSE

      if (rte.metricType != DEFAULT_METRIC_TYPE)
           outRREP.metricType := rte.metricType
      outRREP.origAddr := rte.Address
      outRREP.targAddr := inRREQ.targAddr
      outRREP.targPrefixLen := rte.PrefixLength
                             (if not equal to address length)
      outRREP.targSeqNum := mySeqNum
      outRREP.targAddrMetric := 0 (default) or
                                MIN_METRIC(rte.metricType)
      outRREP.validityTime := (if included) the validity time
                             for route to TargAddr

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

      if (outRREP.metricType != DEFAULT_METRIC_TYPE)
      { /* Build MetricType Message TLV */
        metricMsgTlv.value := outRREP.metricType
      }

      /* Build Address Block */
      AddrBlk := outRREP.origAddr and outRREP.targAddr addresses
           using prefix length information from outRREP.targPrefixLen
           if necessary

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

      /* Build Metric Address Block TLV containing TargAddr metric */
      metricAddrBlkTlv.value := outRREP.targAddrMetric

      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 */
    }

A.3.2. Receive_RREP

    Receive_RREP (inRREP)
    {
      if (inRREP.nbrIP present in blacklist) {
        if (blacklist_expiration_time < current_time)
           return;   /* don't process or regenerate RREQ... */
        else
           remove nbrIP from blacklist;
        }

      if (inRREP does not contain msg_hop_limit, OrigAddr,
                        TargAddr, TargSeqNum, TargAddrMetric)
        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.targAddrMetric >
                            MAX_METRIC[MetricType] - Cost(Link)
        return;

      /* Extract inRREP values */
      advRte.Address := inRREP.targAddr
      advRte.PrefixLength := inRREP.targPrefixLen f present), or the
        maximum address length for address family of advRte.Address
      advRte.SeqNum := inRREP.targSeqNum
      advRte.MetricType := inRREP.metricType (if present),
              else DEFAULT_METRIC_TYPE
      advRte.Metric := inRREP.targAddrMetric
      advRte.Cost := inRREP.targAddrMetric + Cost(L) according to
       inRREP's MetricType. L is the link from the advertising router
      advRte.ValidityTime := inRREP.validityTime (if present)
      advRte.NextHopIP := inRREP.nbrIP
      advRte.NextHopIntf := interface the RteMsg was received on
      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)
    }

A.3.3. Regenerate_RREP

    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 */
        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 whether to include
      if (rte.metricType != DEFAULT_METRIC_TYPE)
           outRREP.metricType := rte.metricType
      outRREP.origAddr := inRREP.origAddr
      outRREP.targAddr := rte.Address
      outRREP.targPrefixLen := rte.PrefixLength
                             (if not equal to address length)
      outRREP.targSeqNum := rte.SeqNum
      outRREP.targAddrMetric := rte.Metric
      outRREP.validityTime := (if included) the validity time
                             for route to TargAddr

      outRREP.nextHop := rte.nextHop

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

      if (outRREP.metricType != DEFAULT_METRIC_TYPE)
      { /* Build MetricType Message TLV */
        metricMsgTlv.value := outRREP.metricType
      }

      /* Build Address Block */
      AddrBlk := {outRREP.origAddr and outRREP.targAddr}
             using prefix length information from
             outRREP.targPrefixLen if necessary

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

      /* Build Metric Address Block TLV containing TargAddrMetric*/
      metricAddrBlkTlv.value := outRREP.targAddrMetric
      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 */
    }

A.4. Example Algorithms for AODVv2 RERR Operations

RERR message parameters, where RERR can be inRERR or outRERR:

• RERR.hopLimit := the maximum number of hops this RERR can traverse
• RERR.pktSource := source IP of unforwardable packet (if present)
• RERR.metricType := metric type for routes to unreachable destinations
• RERR.unreachableAddressList[] := addresses of unreachable destinations
• RERR.prefixLengthList[] := prefix lengths of unreachable destinations
• RERR.seqNumList[] := sequence numbers for unreachable destinations
• RERR.intf := the interface on which the RERR was received

A.4.1. Generate_RERR

    Generate_RERR(error_type, triggerPkt, brokenLinkNbrIp)
       /* error_type is either undeliverable_packet or broken_link */
    {
      switch (error_type)
      {
        case (broken_link):
             /* a RERR will be required for each MetricType */
        foreach metric type in use
        {
          num-broken-addr := 0
          precursors[] := new empty precursor list
          outRERR.hopLimit := MAX_HOPCOUNT
          outRERR.metricType := the metric type for this loop
          /* find routes which are now Invalid */
          foreach (rte in route table)
          {
            if (brokenLinkNbrIp == rte.nextHop AND
                          rte.MetricType == outRERR.metricType AND
               (rte.State == Active OR
               (rte.State == Idle AND ENABLE_IDLE_IN_RERR)))
            {
               rte.State := Invalid;
               precursors += rte.Precursors (if any)
               outRERR.unreachableAddressList[num-broken-addr] :=
                                                  rte.Address
               outRERR.prefixLengthList[num-broken-addr] :=
                                                  rte.PrefixLength
               outRERR.seqNumList[num-broken-addr] := rte.SeqNum
               num-broken-addr := num-broken-addr + 1
            }
          }
          if (0 != num-broken-addr)
          { /* build and send RFC5444 message as below, then
               repeat loop for other MetricTypes */           }
        }
        case (undeliverable_packet):
          num-broken-addr=1
          outRERR.hopLimit := MAX_HOPCOUNT
          outRERR.pktSource := triggerPkt.srcIP or
                        triggerPkt.targAddr if packet was a RREP
          /* optional to include outRERR.metricType */
          outRERR.unreachableAddressList[0] := triggerPkt.destIP or
                        triggerPkt.origAddr if packet was a RREP
      }
      if (triggerPkt exists)
      { /* Build PktSource Message TLV */
        pktSourceMessageTlv.value := outRERR.pktSource
      }
      if (outRERR.metricType != DEFAULT_METRIC_TYPE)
      { /* Build MetricType Message TLV */
        metricMsgTlv.value := outRERR.metricType
      }

      /* The remaining steps add address, prefix length
         and sequence number information for each
         UnreachableAddress, while conforming to the allowed MTU.
         If the MTU is reached, a new message MUST be created. */
      /* Build Address Block */
      AddrBlk := outRERR.unreachableAddressList[]
               using prefix length information from
               outRERR.prefixLengthList[] if necessary

      /* Add SeqNum Address Block TLV including index values */
      seqNumAddrBlkTLV := outRERR.seqNumList[]

      Build_RFC_5444_message_header (RERR, 4, IPv4 or IPv6, NN,
                outRERR.hopLimit, 0, tlvLength)
      if (undeliverable_packet)
        /* unicast outRERR to rte[outRERR.pktSource].NextHop */
      else if (broken_link)
        /* unicast to precursors, or multicast to LL-MANET-Routers */
    }

There are two parts to this function, based on whether it was triggered by an undeliverable packet or a broken link to neighboring AODVv2 router.

A.4.2. Receive_RERR

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

      if (inRERR.metricType is present but an unknown value)
        return;

      /* Extract inRERR values, copy relevant UnreachableAddresses,
         their prefix lengths, and sequence numbers to outRERR */
      num-broken-addr := 0;
      precursors[] := new empty list of type precursors/;

      foreach (unreachableAddress in inRERR.unreachableAddressList)
      {
        if (unreachableAddress is not valid routable
                                                and unicast address)
          continue;
        /* find a matching route table entry, assume
                   DEFAULT_METRIC_TYPE if no MetricType included */
        rte := Fetch_Route_Table_Entry (unreachableAddress,
                                           inRERR.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.intf)
          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, inRERR.metricType)
          invalidRte.State := Invalid

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

        outRERR.unreachableAddressList[num-broken-addr] :=rte.Address
        outRERR.prefixLengthList[num-broken-addr] := rte.PrefixLength
        outRERR.seqNumList[num-broken-addr] := rte.SeqNum
        num-broken-addr := num-broken-addr + 1
      }

      if (num-broken-addr)
        Regenerate_RERR(outRERR, inRERR, precursors)
    }

A.4.3. Regenerate_RERR

    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)
      outRERR.metricType := inRERR.MetricType (if included)
                           or DEFAULT_METRIC_TYPE
      /* UnreachableAddressList[], SeqNumList[], and
         PrefixLengthList[] are already up-to-date */

      if (outRERR.pktSource exists)
      {
        /* Build PktSource Message TLV */
        pktSourceMessageTlv.value := outRERR.pktSource
      }
      if (outRERR.metricType != DEFAULT_METRIC_TYPE)
      {
        /* Build MetricType Message TLV */
        metricMsgTlv.value := outRERR.metricType
      }

      /* Build Address Block */
      
      AddrBlk := outRERR.unreachableAddressList[] using prefix length
            information from outRERR.prefixLengthList[] if necessary

      /* Add SeqNum AddressBlock TLV including index values */
      seqNumAddrTLV := outRERR.seqNumList[]

      Build_RFC_5444_message_header (RERR, 4, IPv4 or IPv6, NN,
                outRERR.hopLimit, 0, tlvLength)
      if (outRERR.pktSource exists) {
        /* unicast RFC 5444 message to 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 */
      }
    }

A.5. Example Algorithms for AODVv2 RREP_Ack Operations

A.5.1. Generate_RREP_Ack

    /* To be sent when 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 */
    }

A.5.2. Receive_RREP_Ack

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

A.5.3. Timeout_RREP_Ack

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

Appendix B. Changes since revision ...-06.txt

This section lists the changes since AODVv2 revision ...-06.txt

• Added Victoria Mercieca as co-author.
• Reorganized protocol message descriptions into major subsections for each protocol message. For protocol messages, organized processing into Generation, Reception, and Regeneration subsections.
• Separated RREQ and RREP message processing description into separate major subsection which had previously been combined into RteMsg description.
• Enlarged RREQ Table function to include similar processing for optional flooded RREP messages. The table name has been correspondingly been changed to be the Table for Multicast RteMsgs.
• Moved sections for Multiple Interfaces and AODVv2 Control Message Generation Limits to be major subsections of the AODVv2 Protocol Operations section.
• Reorganized the protocol message processing steps into the subsections as previously described, adopting a more step-by-step presentation.
• Coalesced the router states Broken and Expired into a new combined state named the Invalid state. No changes in processing are required for this.
• Merged the sections describing Next-hop Router Adjacency Monitoring and Blacklists.
• Specified that routes created during Route Discovery are marked as Idle routes. If they are used for carrying data they become Active routes.
• Added Route.LastSeqnum information to route table, so that route activity and sequence number validity can be tracked separately. An active route can still forward traffic even if the sequence number has not been refreshed within MAX_SEQNUM_LIFETIME.
• Mandated implementation of RREP_Ack as response to AckReq Message TLV in RREP messages. Added field to RREP_Ack to ensure correspondence to the correct AckReq message.
• Added explanations for what happens if protocol constants are given different values on different AODVv2 routers.
• Specified that AODVv2 implementations are free to choose their own heuristics for reducing multicast overhead, including RFC 6621.
• Added appendix to identify AODVv2 requirements from OS implementation of IP and ICMP.
• Deleted appendix showing example RFC 5444 packet formats.
• Clarification on the use of RFC 5497 VALIDITY_TIME.
• In Terminology, deleted superfluous definitions, added missing definitions.
• Numerous editorial improvements and clarifications.

Appendix C. Changes between revisions 5 and 6

This section lists the changes between AODVv2 revisions ...-05.txt and ...-06.txt.

• Added Lotte Steenbrink as co-author.
• Reorganized section on Metrics to improve readability by putting specific topics into subsections.
• Introduced concept of data element, which is used to clarify the method of enabling RFC 5444 representation for AODVv2 data elements. A list of Data Elements was introduced in section 3, which provides a better understanding of their role than was previously supplied by the table of notational devices.
• Replaced instances of OrigNode by OrigAddr whenever the more specific meaning is appropriate. Similarly for instances of other node versus address terminology.
• Introduced concepts of PrefixLengthList and MetricList in order to avoid use of index-based terminology such as OrigNdx and TargNdx.
• Added section 5, "AODVv2 Message Transmission", describing the intended interface to RFC 5444.
• Included within the main body of the specification the mandatory setting of the TLV flag thassingleindex for TLVs OrigSeqNum and TargSeqNum.
• Removed the Route.Timed state. Created a new flag for route table entries known as Route.Timed. This flag can be set when the route is in the active state. Previous description would require that the route table entry be in two states at the same time, which seems to be misleading. The new flag is used to clarify other specification details for Timed routes.
• Created table 3 to show the correspondence between AODVv2 data elements and RFC 5444 message components.
• Replaced "invalid" terminology by the more specific terms "broken" or "expired" where appropriate.
• Eliminated the instance of duplicate specification for inclusion of OrigNode (now, OrigAddr) in the message.
• Corrected the terminology to be Mid instead of Tail for the trailing address bits of OrigAddr and TargAddr for the example message formats in the appendices.
• Repaired remaining instances of phraseology that could be construed as indicating that AODV only supports a single network interface.
• Numerous editorial improvements and clarifications.

Appendix D. Changes from revision ...-04.txt

This section lists the changes between AODVv2 revisions ...-04.txt and ...-05.txt.

• Normative text moved out of definitions into the relevant section of the body of the specification.
• Editorial improvements and improvements to consistent terminology were made. Replaced "retransmit" by the slightly more accurate term "regenerate".
• Issues were resolved as discussed on the mailing list.
• Changed definition of LoopFree as suggested by Kedar Namjoshi and Richard Trefler to avoid the failure condition that they have described. In order to make understanding easier, replaced abstract parameters R1 by RteMsg and R2 by Route to reduce the level of abstraction when the function LoopFree is discussed.
• Added text to clarify that different metrics may have different data types and different ranges of acceptable values.
• Added text to section "RteMsg Structure" to emphasize the proper use of RFC 5444.
• Included within the main body of the specification the mandatory setting of the TLV flag thassingleindex for TLVs OrigSeqNum and TargSeqNum.
• Made more extensive use of the AdvRte terminology, in order to better distinguish between the incoming RREQ or RREP message (i.e., RteMsg) versus the route advertised by the RteMsg (i.e., AdvRte).

Appendix E. Changes from revision ...-03.txt

This section lists the changes between AODVv2 revisions ...-03.txt and ...-04.txt.

• An appendix was added to exhibit algorithmic code for implementation of AODVv2 functions.
• Numerous editorial improvements and improvements to consistent terminology were made. Terminology related to prefix lengths was made consistent. Some items listed in "Notational Conventions" were no longer used, and so deleted.
• Issues were resolved as discussed on the mailing list.
• Appropriate instances of "may" were changed to "MAY".
• Definition inserted for "upstream".
• Route.Precursors included as an *optional* route table field
• Reworded text to avoid use of "relevant".
• Deleted references to "DestOnly" flag.
• Refined statements about MetricType TLV to allow for omission when MetricType == HopCount.
• Bulletized list in section 8.1
• ENABLE_IDLE_UNREACHABLE renamed to be ENABLE_IDLE_IN_RERR
• Transmission and subscription to LL-MANET-Routers converted to MUST from SHOULD.

Appendix F. Changes from revision ...-02.txt

This section lists the changes between AODVv2 revisions ...-02.txt and ...-03.txt.

• The "Added Node" feature was removed. This feature was intended to enable additional routing information to be carried within a RREQ or a RREP message, thus increasing the amount of topological information available to nodes along a routing path. However, enlarging the packet size to include information which might never be used can increase congestion of the wireless medium. The feature can be included as an optional feature at a later date when better algorithms are understood for determining when the inclusion of additional routing information might be worthwhile.
• Numerous editorial improvements and improvements to consistent terminology were made. Instances of OrigNodeNdx and TargNodeNdx were replaced by OrigNdx and TargNdx, to be consistent with the terminology shown in Table 2.
• Example RREQ and RREP message formats shown in the Appendices were changed to use OrigSeqNum and TargSeqNum message TLVs instead of using the SeqNum message TLV.
• Inclusion of the OrigNode's SeqNum in the RREP message is not specified. The processing rules for the OrigNode's SeqNum were incompletely specified in previous versions of the draft, and very little benefit is foreseen for including that information, since reverse path forwarding is used for the RREP.
• Additional acknowledgements were included, and contributors names were alphabetized.
• Definitions in the Terminology section capitalize the term to be defined.
• Uncited bibliographic entries deleted.
• Ancient "Changes" sections were deleted.

Appendix G. Features of IP needed by AODVv2

AODVv2 needs the following:

• information that IP routes are requested
• information that packets are flowing
• the ability to queue packets.

A reactive protocol reacts when a route is needed. One might say that 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, and the way that has been used to know whether a route is needed is when an application tries to send a packet.

If an application tries to send a packet, and the route is not available, the packet has to wait until the route is available.

Appendix H. Multi-homing Considerations

This non-normative information is provided simply to document the results of previous efforts to enable multi-homing. The intention is to simplify the task of future specification if multihoming becomes needed for reactive protocol operation.

Multi-homing is not supported by the AODVv2 specification. There has been previous work indicating that it can be supported by expanding the sequence number to include the AODVv2 router's IP address as a parsable field of the SeqNum. Otherwise, comparing sequence numbers would not work to evaluate freshness. Even when the IP address is included, there isn't a good way to compare sequence numbers from different IP addresses, but at least a handling node can determine whether the two given sequence numbers are comparable. If the route table can store multiple routes for the same destination, then multi-homing can work with sequence numbers augmented by IP addresses.

This non-normative information is provided simply to document the results of previous efforts to enable multi-homing. The intention is to simplify the task of future specification if multihoming becomes needed for reactive protocol operation.

Appendix I. Shifting Network Prefix Advertisement Between AODVv2 Routers

Only one AODVv2 router within a MANET SHOULD be responsible for a particular address at any time. If two AODVv2 routers dynamically shift the advertisement of a network prefix, correct AODVv2 routing behavior must be observed. The AODVv2 router adding the new network prefix must wait for any existing routing information about this network prefix to be purged from the network. Therefore, it must wait at least ROUTER_SEQNUM_AGE_MAX_TIMEOUT after the previous AODVv2 router for this address stopped advertising routing information on its behalf.

Authors' Addresses