tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search

RFC 4728

 
 
 

The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4

Part 3 of 4, p. 51 to 83
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 51 
7.  Additional Header Formats and Options for Flow State Extension

   The optional DSR flow state extension requires a new header type, the
   DSR Flow State header.

   In addition, the DSR flow state extension adds the following options
   for the DSR Options header defined in Section 6:

   -  Timeout option (Section 7.2.1)

   -  Destination and Flow ID option (Section 7.2.2)

   Two new Error Type values are also defined for use in the Route Error
   option in a DSR Options header:

   -  UNKNOWN_FLOW

   -  DEFAULT_FLOW_UNKNOWN

   Finally, an extension to the Acknowledgement Request option in a DSR
   Options header is also defined:

Top      Up      ToC       Page 52 
   -  Previous Hop Address

   This section defines each of these new header, option, or extension
   formats.

7.1.  DSR Flow State Header

   The DSR Flow State header is a small 4-byte header optionally used to
   carry the flow ID and hop count for a packet being sent along a DSR
   flow.  It is distinguished from the fixed DSR Options header (Section
   6.1) in that the Flow State Header (F) bit is set in the DSR Flow
   State header and is clear in the fixed DSR Options header.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Next Header  |F|  Hop Count  |        Flow Identifier        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      Next Header

         8-bit selector.  Identifies the type of header immediately
         following the DSR Flow State header.  Uses the same values as
         the IPv4 Protocol field [RFC1700].

      Flow State Header (F)

         Flag bit.  MUST be set to 1.  This bit is set in a DSR Flow
         State header and clear in a DSR Options header (Section 6.1).

      Hop Count

         7-bit unsigned integer.  The number of hops through which this
         packet has been forwarded.

      Flow Identification

         The flow ID for this flow, as described in Section 3.5.1.

7.2.  New Options and Extensions in DSR Options Header

7.2.1.  Timeout Option

   The Timeout option is defined for use in a DSR Options header to
   indicate the amount of time before the expiration of the flow ID
   along which the packet is being sent.

Top      Up      ToC       Page 53 
    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Option Type  | Opt Data Len  |            Timeout            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      Option Type

         128.  Nodes not understanding this option will ignore the
         option and return a Route Error.

      Opt Data Len

         8-bit unsigned integer.  Length of the option, in octets,
         excluding the Option Type and Opt Data Len fields.

         When no extensions are present, the Opt Data Len of a Timeout
         option is 2.  Further extensions to DSR may include additional
         data in a Timeout option.  The presence of such extensions is
         indicated by an Opt Data Len greater than 2.  Currently, no
         such extensions have been defined.

      Timeout

         The number of seconds for which this flow remains valid.

   The Timeout option MUST NOT appear more than once within a DSR
   Options header.

7.2.2.  Destination and Flow ID Option

   The Destination and Flow ID option is defined for use in a DSR
   Options header to send a packet to an intermediate host along one
   flow, for eventual forwarding to the final destination along a
   different flow.  This option enables the aggregation of the state of
   multiple flows.

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Option Type  | Opt Data Len  |      New Flow Identifier      |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                   New IP Destination Address                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Top      Up      ToC       Page 54 
      Option Type

         129.  Nodes not understanding this option will ignore the
         option and return a Route Error.

      Opt Data Len

         8-bit unsigned integer.  Length of the option, in octets,
         excluding the Option Type and Opt Data Len fields.

         When no extensions are present, the Opt Data Len of a
         Destination and Flow ID option is 6.  Further extensions to DSR
         may include additional data in a Destination and Flow ID
         option.  The presence of such extensions is indicated by an Opt
         Data Len greater than 6.  Currently, no such extensions have
         been defined.

      New Flow Identifier

         Indicates the next identifier to store in the Flow ID field of
         the DSR Options header.

      New IP Destination Address

         Indicates the next address to store in the Destination Address
         field of the IP header.

   The Destination and Flow ID option MAY appear one or more times
   within a DSR Options header.

7.3.  New Error Types for Route Error Option

7.3.1.  Unknown Flow Type-Specific Information

   A new Error Type value of 129 (UNKNOWN_FLOW) is defined for use in a
   Route Error option in a DSR Options header.  The Type-Specific
   Information for errors of this type is encoded as follows:

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                Original IP Destination Address                |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            Flow ID            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Top      Up      ToC       Page 55 
      Original IP Destination Address

         The IP Destination Address of the packet that caused the error.

      Flow ID

         The Flow ID contained in the DSR Flow ID option that caused the
         error.

7.3.2.  Default Flow Unknown Type-Specific Information

   A new Error Type value of 130 (DEFAULT_FLOW_UNKNOWN) is defined
   for use in a Route Error option in a DSR Options header.  The
   Type-Specific Information for errors of this type is encoded as
   follows:

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |               Original IP Destination Address                 |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      Original IP Destination Address

         The IP Destination Address of the packet that caused the error.

7.4.  New Acknowledgement Request Option Extension

7.4.1.  Previous Hop Address Extension

   When the Opt Data Len field of an Acknowledgement Request option
   in a DSR Options header is greater than or equal to 6, the
   ACK Request Source Address field is present.  The option is then
   formatted as follows:

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |  Option Type  | Opt Data Len  |       Packet Identifier       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                   ACK Request Source Address                  |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

      Option Type

         160.  Nodes not understanding this option will remove the
         option and return a Route Error.

Top      Up      ToC       Page 56 
      Opt Data Len

         8-bit unsigned integer.  Length of the option, in octets,
         excluding the Option Type and Opt Data Len fields.

         When no extensions are presents, the Opt Data Len of an
         Acknowledgement Request option is 2.  Further extensions to DSR
         may include additional data in an Acknowledgement Request
         option.  The presence of such extensions is indicated by an Opt
         Data Len greater than 2.

         Currently, one such extension has been defined.  If the Opt
         Data Len is at least 6, then an ACK Request Source Address is
         present.

      Packet Identifier

         The Packet Identifier field is set to a unique number and is
         copied into the Identification field of the DSR Acknowledgement
         option when returned by the node receiving the packet over this
         hop.

      ACK Request Source Address

         The address of the node requesting the DSR Acknowledgement.

8.  Detailed Operation

8.1.  General Packet Processing

8.1.1.  Originating a Packet

   When originating any packet, a node using DSR routing MUST perform
   the following sequence of steps:

   -  Search the node's Route Cache for a route to the address given in
      the IP Destination Address field in the packet's header.

   -  If no such route is found in the Route Cache, then perform Route
      Discovery for the Destination Address, as described in Section
      8.2.  Initiating a Route Discovery for this target node address
      results in the node adding a Route Request option in a DSR Options
      header in this existing packet, or saving this existing packet to
      its Send Buffer and initiating the Route Discovery by sending a
      separate packet containing such a Route Request option.  If the
      node chooses to initiate the Route Discovery by adding the Route
      Request option to this existing packet, it will replace the IP
      Destination Address field with the IP "limited broadcast" address

Top      Up      ToC       Page 57 
      (255.255.255.255) [RFC1122], copying the original IP Destination
      Address to the Target Address field of the new Route Request
      option added to the packet, as described in Section 8.2.1.

   -  If the packet now does not contain a Route Request option, then
      this node must have a route to the Destination Address of the
      packet; if the node has more than one route to this Destination
      Address, the node selects one to use for this packet.  If the
      length of this route is greater than 1 hop, or if the node
      determines to request a DSR network-layer acknowledgement from the
      first-hop node in that route, then insert a DSR Options header
      into the packet, as described in Section 8.1.2, and insert a DSR
      Source Route option, as described in Section 8.1.3.  The source
      route in the packet is initialized from the selected route to the
      Destination Address of the packet.

   -  Transmit the packet to the first-hop node address given in
      selected source route, using Route Maintenance to determine the
      reachability of the next hop, as described in Section 8.3.

8.1.2.  Adding a DSR Options Header to a Packet

   A node originating a packet adds a DSR Options header to the packet,
   if necessary, to carry information needed by the routing protocol.  A
   packet MUST NOT contain more than one DSR Options header.  A DSR
   Options header is added to a packet by performing the following
   sequence of steps (these steps assume that the packet contains no
   other headers that MUST be located in the packet before the DSR
   Options header):

   -  Insert a DSR Options header after the IP header but before any
      other header that may be present.

   -  Set the Next Header field of the DSR Options header to the
      Protocol number field of the packet's IP header.

   -  Set the Protocol field of the packet's IP header to the protocol
      number assigned for DSR (48).

8.1.3.  Adding a DSR Source Route Option to a Packet

   A node originating a packet adds a DSR Source Route option to the
   packet, if necessary, in order to carry the source route from this
   originating node to the final destination address of the packet.
   Specifically, the node adding the DSR Source Route option constructs
   the DSR Source Route option and modifies the IP packet according to
   the following sequence of steps:

Top      Up      ToC       Page 58 
   -  The node creates a DSR Source Route option, as described in
      Section 6.7, and appends it to the DSR Options header in the
      packet.  (A DSR Options header is added, as described in Section
      8.1.2, if not already present.)

   -  The number of Address[i] fields to include in the DSR Source Route
      option (n) is the number of intermediate nodes in the source route
      for the packet (i.e., excluding the address of the originating
      node and the final destination address of the packet).  The
      Segments Left field in the DSR Source Route option is initialized
      equal to n.

   -  The addresses within the source route for the packet are copied
      into sequential Address[i] fields in the DSR Source Route option,
      for i = 1, 2, ..., n.

   -  The First Hop External (F) bit in the DSR Source Route option is
      copied from the External bit flagging the first hop in the source
      route for the packet, as indicated in the Route Cache.

   -  The Last Hop External (L) bit in the DSR Source Route option is
      copied from the External bit flagging the last hop in the source
      route for the packet, as indicated in the Route Cache.

   -  The Salvage field in the DSR Source Route option is initialized to
      0.

8.1.4.  Processing a Received Packet

   When a node receives any packet (whether for forwarding, overheard,
   or the final destination of the packet), if that packet contains a
   DSR Options header, then that node MUST process any options contained
   in that DSR Options header, in the order contained there.
   Specifically:

   -  If the DSR Options header contains a Route Request option, the
      node SHOULD extract the source route from the Route Request and
      add this routing information to its Route Cache, subject to the
      conditions identified in Section 3.3.1.  The routing information
      from the Route Request is the sequence of hop addresses

         initiator, Address[1], Address[2], ..., Address[n]

      where initiator is the value of the Source Address field in the IP
      header of the packet carrying the Route Request (the address of
      the initiator of the Route Discovery), and each Address[i] is a
      node through which this Route Request has passed, in turn, during

Top      Up      ToC       Page 59 
      this Route Discovery.  The value n, here, is the number of
      addresses recorded in the Route Request option, or
      (Opt Data Len - 6) / 4.

      After possibly updating the node's Route Cache in response to the
      routing information in the Route Request option, the node MUST
      then process the Route Request option as described in Section
      8.2.2.

   -  If the DSR Options header contains a Route Reply option, the node
      SHOULD extract the source route from the Route Reply and add this
      routing information to its Route Cache, subject to the conditions
      identified in Section 3.3.1.  The source route from the Route
      Reply is the sequence of hop addresses

         initiator, Address[1], Address[2], ..., Address[n]

      where initiator is the value of the Destination Address field in
      the IP header of the packet carrying the Route Reply (the address
      of the initiator of the Route Discovery), and each Address[i] is a
      node through which the source route passes, in turn, on the route
      to the target of the Route Discovery.  Address[n] is the address
      of the target.  If the Last Hop External (L) bit is set in the
      Route Reply, the node MUST flag the last hop from the Route Reply
      (the link from Address[n-1] to Address[n]) in its Route Cache as
      External.  The value n here is the number of addresses in the
      source route being returned in the Route Reply option, or
      (Opt Data Len - 1) / 4.

      After possibly updating the node's Route Cache in response to the
      routing information in the Route Reply option, then if the
      packet's IP Destination Address matches one of this node's IP
      addresses, the node MUST then process the Route Reply option as
      described in Section 8.2.6.

   -  If the DSR Options header contains a Route Error option, the node
      MUST process the Route Error option as described in Section 8.3.5.

   -  If the DSR Options header contains an Acknowledgement Request
      option, the node MUST process the Acknowledgement Request option
      as described in Section 8.3.3.

   -  If the DSR Options header contains an Acknowledgement option, then
      subject to the conditions identified in Section 3.3.1, the node
      SHOULD add to its Route Cache the single link from the node
      identified by the ACK Source Address field to the node identified
      by the ACK Destination Address field.

Top      Up      ToC       Page 60 
      After possibly updating the node's Route Cache in response to the
      routing information in the Acknowledgement option, the node MUST
      then process the Acknowledgement option as described in Section
      8.3.3.

   -  If the DSR Options header contains a DSR Source Route option, the
      node SHOULD extract the source route from the DSR Source Route
      option and add this routing information to its Route Cache,
      subject to the conditions identified in Section 3.3.1.  If the
      value of the Salvage field in the DSR Source Route option is zero,
      then the routing information from the DSR Source Route is the
      sequence of hop addresses

         source, Address[1], Address[2], ..., Address[n], destination

      Otherwise (i.e., if Salvage is nonzero), the routing information
      from the DSR Source Route is the sequence of hop addresses

         Address[1], Address[2], ..., Address[n], destination

      where source is the value of the Source Address field in the IP
      header of the packet carrying the DSR Source Route option (the
      original sender of the packet), each Address[i] is the value in
      the Address[i] field in the DSR Source Route option, and
      destination is the value of the Destination Address field in the
      packet's IP header (the last-hop address of the source route).
      The value n here is the number of addresses in source route in the
      DSR Source Route option, or (Opt Data Len - 2) / 4.

      After possibly updating the node's Route Cache in response to the
      routing information in the DSR Source Route option, the node MUST
      then process the DSR Source Route option as described in Section
      8.1.5.

   -  Any Pad1 or PadN options in the DSR Options header are ignored.

   -  Finally, if the Destination Address in the packet's IP header
      matches one of this receiving node's own IP address(es), remove
      the DSR Options header and all the included DSR options in the
      header, and pass the rest of the packet to the network layer.

8.1.5.  Processing a Received DSR Source Route Option

   When a node receives a packet containing a DSR Source Route option
   (whether for forwarding, overheard, or the final destination of the
   packet), that node SHOULD examine the packet to determine if the
   receipt of that packet indicates an opportunity for automatic route
   shortening, as described in Section 3.4.3.  Specifically, if this

Top      Up      ToC       Page 61 
   node is not the intended next-hop destination for the packet but is
   named in the later unexpended portion of the source route in the
   packet's DSR Source Route option, then this packet indicates an
   opportunity for automatic route shortening:  the intermediate nodes
   after the node from which this node overheard the packet and before
   this node itself are no longer necessary in the source route.  In
   this case, this node SHOULD perform the following sequence of steps
   as part of automatic route shortening:

   -  The node searches its Gratuitous Route Reply Table for an entry
      describing a gratuitous Route Reply earlier sent by this node, for
      which the original sender (of the packet triggering the gratuitous
      Route Reply) and the transmitting node (from which this node
      overheard that packet in order to trigger the gratuitous Route
      Reply) both match the respective node addresses for this new
      received packet.  If such an entry is found in the node's
      Gratuitous Route Reply Table, the node SHOULD NOT perform
      automatic route shortening in response to this receipt of this
      packet.

   -  Otherwise, the node creates an entry for this overheard packet in
      its Gratuitous Route Reply Table.  The timeout value for this new
      entry SHOULD be initialized to the value GratReplyHoldoff.  After
      this timeout has expired, the node SHOULD delete this entry from
      its Gratuitous Route Reply Table.

   -  After creating the new Gratuitous Route Reply Table entry above,
      the node originates a gratuitous Route Reply to the IP Source
      Address of this overheard packet, as described in Section 3.4.3.

      If the MAC protocol in use in the network is not capable of
      transmitting unicast packets over unidirectional links, as
      discussed in Section 3.3.1, then in originating this Route Reply,
      the node MUST use a source route for routing the Route Reply
      packet that is obtained by reversing the sequence of hops over
      which the packet triggering the gratuitous Route Reply was routed
      in reaching and being overheard by this node.  This reversing of
      the route uses the gratuitous Route Reply to test this sequence of
      hops for bidirectionality, preventing the gratuitous Route Reply
      from being received by the initiator of the Route Discovery unless
      each of the hops over which the gratuitous Route Reply is returned
      is bidirectional.

   -  Discard the overheard packet, since the packet has been received
      before its normal traversal of the packet's source route would
      have caused it to reach this receiving node.  Another copy of the
      packet will normally arrive at this node as indicated in the

Top      Up      ToC       Page 62 
      packet's source route; discarding this initial copy of the packet,
      which triggered the gratuitous Route Reply, will prevent the
      duplication of this packet that would otherwise occur.

   If the packet is not discarded as part of automatic route shortening
   above, then the node MUST process the Source Route option according
   to the following sequence of steps:

   -  If the value of the Segments Left field in the DSR Source Route
      option equals 0, then remove the DSR Source Route option from the
      DSR Options header.

   -  Else, let n equal (Opt Data Len - 2) / 4.  This is the number of
      addresses in the DSR Source Route option.

   -  If the value of the Segments Left field is greater than n, then
      send an ICMP Parameter Problem, Code 0, message [RFC792] to the IP
      Source Address, pointing to the Segments Left field, and discard
      the packet.  Do not process the DSR Source Route option further.

   -  Else, decrement the value of the Segments Left field by 1.  Let i
      equal n minus Segments Left.  This is the index of the next
      address to be visited in the Address vector.

   -  If Address[i] or the IP Destination Address is a multicast
      address, then discard the packet.  Do not process the DSR Source
      Route option further.

   -  If this node has more than one network interface and if Address[i]
      is the address of one this node's network interfaces, then this
      indicates a change in the network interface to use in forwarding
      the packet, as described in Section 8.4.  In this case, decrement
      the value of the Segments Left field by 1 to skip over this
      address (that indicated the change of network interface) and go to
      the first step above (checking the value of the Segments Left
      field) to continue processing this Source Route option; in further
      processing of this Source Route option, the indicated new network
      interface MUST be used in forwarding the packet.

   -  If the MTU of the link over which this node would transmit the
      packet to forward it to the node Address[i] is less than the size
      of the packet, the node MUST either discard the packet and send an
      ICMP Packet Too Big message to the packet's Source Address
      [RFC792] or fragment it as specified in Section 8.5.

   -  Forward the packet to the IP address specified in the Address[i]
      field of the IP header, following normal IP forwarding procedures,
      including checking and decrementing the Time-to-Live (TTL) field

Top      Up      ToC       Page 63 
      in the packet's IP header [RFC791, RFC1122].  In this forwarding
      of the packet, the next-hop node (identified by Address[i]) MUST
      be treated as a direct neighbor node:  the transmission to that
      next node MUST be done in a single IP forwarding hop, without
      Route Discovery and without searching the Route Cache.

   -  In forwarding the packet, perform Route Maintenance for the next
      hop of the packet, by verifying that the next-hop node is
      reachable, as described in Section 8.3.

   Multicast addresses MUST NOT appear in a DSR Source Route option or
   in the IP Destination Address field of a packet carrying a DSR Source
   Route option in a DSR Options header.

8.1.6.  Handling an Unknown DSR Option

   Nodes implementing DSR MUST handle all options specified in this
   document, except those options pertaining to the optional flow state
   extension (Section 7).  However, further extensions to DSR may
   include other option types that may not be understood by
   implementations conforming to this version of the DSR specification.
   In DSR, Option Type codes encode required behavior for nodes not
   implementing that type of option.  These behaviors are included in
   the most significant 3 bits of the Option Type.

   If the most significant bit of the Option Type is set (that is,
   Option Type & 0x80 is nonzero), and this packet does not contain a
   Route Request option, a node SHOULD return a Route Error to the IP
   Source Address, following the steps described in Section 8.3.4,
   except that the Error Type MUST be set to OPTION_NOT_SUPPORTED and
   the Unsupported Opt field MUST be set to the Option Type triggering
   the Route Error.

   Whether or not a Route Error is sent in response to this DSR option,
   as described above, the node also MUST examine the next 2 most
   significant bits (that is, Option Type & 0x60):

   -  When these 2 bits are 00 (that is, Option Type & 0x60 == 0), a
      node not implementing processing for that Option Type MUST use the
      Opt Data Len field to skip over the option and continue
      processing.

   -  When these 2 bits are 01 (that is, Option Type & 0x60 == 0x20), a
      node not implementing processing for that Option Type MUST use the
      Opt Data Len field to remove the option from the packet and
      continue processing as if the option had not been included in the
      received packet.

Top      Up      ToC       Page 64 
   -  When these 2 bits are 10 (that is, Option Type & 0x60 == 0x40), a
      node not implementing processing for that Option Type MUST set the
      most significant bit following the Opt Data Len field.  In
      addition, the node MUST then ignore and skip over the contents of
      the option using the Opt Data Len field and MUST continue
      processing the packet.

   -  Finally, when these 2 bits are 11 (that is,
      Option Type & 0x60 == 0x60), a node not implementing processing
      for that Option Type MUST drop the packet.

8.2.  Route Discovery Processing

   Route Discovery is the mechanism by which a node S wishing to send a
   packet to a destination node D obtains a source route to D.  Route
   Discovery SHOULD be used only when S attempts to send a packet to D
   and does not already know a route to D.  The node initiating a Route
   Discovery is known as the "initiator" of the Route Discovery, and the
   destination node for which the Route Discovery is initiated is known
   as the "target" of the Route Discovery.

   Route Discovery operates entirely on demand; a node initiates Route
   Discovery based on its own origination of new packets for some
   destination address to which it does not currently know a route.
   Route Discovery does not depend on any periodic or background
   exchange of routing information or neighbor node detection at any
   layer in the network protocol stack at any node.

   The Route Discovery procedure utilizes two types of messages, a Route
   Request (Section 6.2) and a Route Reply (Section 6.3), to actively
   search the ad hoc network for a route to the desired target
   destination.  These DSR messages MAY be carried in any type of IP
   packet, through use of the DSR Options header as described in Section
   6.

   Except as discussed in Section 8.3.5, a Route Discovery for a
   destination address SHOULD NOT be initiated unless the initiating
   node has a packet in its Send Buffer requiring delivery to that
   destination.  A Route Discovery for a given target node MUST NOT be
   initiated unless permitted by the rate-limiting information contained
   in the Route Request Table.  After each Route Discovery attempt, the
   interval between successive Route Discoveries for this target SHOULD
   be doubled, up to a maximum of MaxRequestPeriod, until a valid Route
   Reply is received for this target.

Top      Up      ToC       Page 65 
8.2.1.  Originating a Route Request

   A node initiating a Route Discovery for some target creates and
   initializes a Route Request option in a DSR Options header in some IP
   packet.  This MAY be a separate IP packet, used only to carry this
   Route Request option, or the node MAY include the Route Request
   option in some existing packet that it needs to send to the target
   node (e.g., the IP packet originated by this node that caused the
   node to attempt Route Discovery for the destination address of the
   packet).  The Route Request option MUST be included in a DSR Options
   header in the packet.  To initialize the Route Request option, the
   node performs the following sequence of steps:

   -  The Option Type in the option MUST be set to the value 2.

   -  The Opt Data Len field in the option MUST be set to the value 6.
      The total size of the Route Request option, when initiated, is 8
      octets; the Opt Data Len field excludes the size of the Option
      Type and Opt Data Len fields themselves.

   -  The Identification field in the option MUST be set to a new value,
      different from that used for other Route Requests recently
      initiated by this node for this same target address.  For example,
      each node MAY maintain a single counter value for generating a new
      Identification value for each Route Request it initiates.

   -  The Target Address field in the option MUST be set to the IP
      address that is the target of this Route Discovery.

   The Source Address in the IP header of this packet MUST be the node's
   own IP address.  The Destination Address in the IP header of this
   packet MUST be the IP "limited broadcast" address (255.255.255.255).

   A node MUST maintain, in its Route Request Table, information about
   Route Requests that it initiates.  When initiating a new Route
   Request, the node MUST use the information recorded in the Route
   Request Table entry for the target of that Route Request, and it MUST
   update that information in the table entry for use in the next Route
   Request initiated for this target.  In particular:

   -  The Route Request Table entry for a target node records the Time-
      to-Live (TTL) field used in the IP header of the Route Request for
      the last Route Discovery initiated by this node for that target
      node.  This value allows the node to implement a variety of
      algorithms for controlling the spread of its Route Request on each
      Route Discovery initiated for a target.  As examples, two possible
      algorithms for this use of the TTL field are described in Section
      3.3.3.

Top      Up      ToC       Page 66 
   -  The Route Request Table entry for a target node records the number
      of consecutive Route Requests initiated for this target since
      receiving a valid Route Reply giving a route to that target node,
      and the remaining amount of time before which this node MAY next
      attempt at a Route Discovery for that target node.

      A node MUST use these values to implement a back-off algorithm to
      limit the rate at which this node initiates new Route Discoveries
      for the same target address.  In particular, until a valid Route
      Reply is received for this target node address, the timeout
      between consecutive Route Discovery initiations for this target
      node with the same hop limit SHOULD increase by doubling the
      timeout value on each new initiation.

   The behavior of a node processing a packet containing DSR Options
   header with both a DSR Source Route option and a Route Request option
   is unspecified.  Packets SHOULD NOT contain both a DSR Source Route
   option and a Route Request option.

   Packets containing a Route Request option SHOULD NOT include an
   Acknowledgement Request option, SHOULD NOT expect link-layer
   acknowledgement or passive acknowledgement, and SHOULD NOT be
   retransmitted.  The retransmission of packets containing a Route
   Request option is controlled solely by the logic described in this
   section.

8.2.2.  Processing a Received Route Request Option

   When a node receives a packet containing a Route Request option, that
   node MUST process the option according to the following sequence of
   steps:

   -  If the Target Address field in the Route Request matches this
      node's own IP address, then the node SHOULD return a Route Reply
      to the initiator of this Route Request (the Source Address in the
      IP header of the packet), as described in Section 8.2.4.  The
      source route for this Reply is the sequence of hop addresses

         initiator, Address[1], Address[2], ..., Address[n], target

      where initiator is the address of the initiator of this Route
      Request, each Address[i] is an address from the Route Request, and
      target is the target of the Route Request (the Target Address
      field in the Route Request).  The value n here is the number of
      addresses recorded in the Route Request, or
      (Opt Data Len - 6) / 4.

Top      Up      ToC       Page 67 
      The node then MUST replace the Destination Address field in the
      Route Request packet's IP header with the value in the Target
      Address field in the Route Request option, and continue processing
      the rest of the Route Request packet normally.  The node MUST NOT
      process the Route Request option further and MUST NOT retransmit
      the Route Request to propagate it to other nodes as part of the
      Route Discovery.

   -  Else, the node MUST examine the route recorded in the Route
      Request option (the IP Source Address field and the sequence of
      Address[i] fields) to determine if this node's own IP address
      already appears in this list of addresses.  If so, the node MUST
      discard the entire packet carrying the Route Request option.

   -  Else, if the Route Request was received through a network
      interface that requires physically bidirectional links for unicast
      transmission, the node MUST check if the Route Request was last
      forwarded by a node on its blacklist (Section 4.6).  If such an
      entry is found in the blacklist, and the state of the
      unidirectional link is "probable", then the Request MUST be
      silently discarded.

   -  Else, if the Route Request was received through a network
      interface that requires physically bidirectional links for unicast
      transmission, the node MUST check if the Route Request was last
      forwarded by a node on its blacklist.  If such an entry is found
      in the blacklist, and the state of the unidirectional link is
      "questionable", then the node MUST create and unicast a Route
      Request packet to that previous node, setting the IP Time-To-Live
      (TTL) to 1 to prevent the Request from being propagated.  If the
      node receives a Route Reply in response to the new Request, it
      MUST remove the blacklist entry for that node, and SHOULD continue
      processing.  If the node does not receive a Route Reply within
      some reasonable amount of time, the node MUST silently discard the
      Route Request packet.

   -  Else, the node MUST search its Route Request Table for an entry
      for the initiator of this Route Request (the IP Source Address
      field).  If such an entry is found in the table, the node MUST
      search the cache of Identification values of recently received
      Route Requests in that table entry, to determine if an entry is
      present in the cache matching the Identification value and target
      node address in this Route Request.  If such an (Identification,
      target address) entry is found in this cache in this entry in the
      Route Request Table, then the node MUST discard the entire packet
      carrying the Route Request option.

Top      Up      ToC       Page 68 
   -  Else, this node SHOULD further process the Route Request according
      to the following sequence of steps:

      o  Add an entry for this Route Request in its cache of
         (Identification, target address) values of recently received
         Route Requests.

      o  Conceptually create a copy of this entire packet and perform
         the following steps on the copy of the packet.

      o  Append this node's own IP address to the list of Address[i]
         values in the Route Request and increase the value of the Opt
         Data Len field in the Route Request by 4 (the size of an IP
         address).  However, if the node has multiple network
         interfaces, this step MUST be modified by the special
         processing specified in Section 8.4.

      o  This node SHOULD search its own Route Cache for a route (from
         itself, as if it were the source of a packet) to the target of
         this Route Request.  If such a route is found in its Route
         Cache, then this node SHOULD follow the procedure outlined in
         Section 8.2.3 to return a "cached Route Reply" to the initiator
         of this Route Request, if permitted by the restrictions
         specified there.

      o  If the node does not return a cached Route Reply, then this
         node SHOULD transmit this copy of the packet as a link-layer
         broadcast, with a short jitter delay before the broadcast is
         sent.  The jitter period SHOULD be chosen as a random period,
         uniformly distributed between 0 and BroadcastJitter.

8.2.3.  Generating a Route Reply Using the Route Cache

   As described in Section 3.3.2, it is possible for a node processing a
   received Route Request to avoid propagating the Route Request further
   toward the target of the Request, if this node has in its Route Cache
   a route from itself to this target.  Such a Route Reply generated by
   a node from its own cached route to the target of a Route Request is
   called a "cached Route Reply", and this mechanism can greatly reduce
   the overall overhead of Route Discovery on the network by reducing
   the flood of Route Requests.  The general processing of a received
   Route Request is described in Section 8.2.2; this section specifies
   the additional requirements that MUST be met before a cached Route
   Reply may be generated and returned and specifies the procedure for
   returning such a cached Route Reply.

Top      Up      ToC       Page 69 
   While processing a received Route Request, for a node to possibly
   return a cached Route Reply, it MUST have in its Route Cache a route
   from itself to the target of this Route Request.  However, before
   generating a cached Route Reply for this Route Request, the node MUST
   verify that there are no duplicate addresses listed in the route
   accumulated in the Route Request together with the route from this
   node's Route Cache.  Specifically, there MUST be no duplicates among
   the following addresses:

   -  The IP Source Address of the packet containing the Route Request,

   -  The Address[i] fields in the Route Request, and

   -  The nodes listed in the route obtained from this node's Route
      Cache, excluding the address of this node itself (this node itself
      is the common point between the route accumulated in the Route
      Request and the route obtained from the Route Cache).

   If any duplicates exist among these addresses, then the node MUST NOT
   send a cached Route Reply using this route from the Route Cache (it
   is possible that this node has another route in its Route Cache for
   which the above restriction on duplicate addresses is met, allowing
   the node to send a cached Route Reply based on that cached route,
   instead).  The node SHOULD continue to process the Route Request as
   described in Section 8.2.2 if it does not send a cached Route Reply.

   If the Route Request and the route from the Route Cache meet the
   restriction above, then the node SHOULD construct and return a cached
   Route Reply as follows:

   -  The source route for this Route Reply is the sequence of hop
      addresses

         initiator, Address[1], Address[2], ..., Address[n], c-route

      where initiator is the address of the initiator of this Route
      Request, each Address[i] is an address from the Route Request, and
      c-route is the sequence of hop addresses in the source route to
      this target node, obtained from the node's Route Cache.  In
      appending this cached route to the source route for the reply, the
      address of this node itself MUST be excluded, since it is already
      listed as Address[n].

   -  Send a Route Reply to the initiator of the Route Request, using
      the procedure defined in Section 8.2.4.  The initiator of the
      Route Request is indicated in the Source Address field in the
      packet's IP header.

Top      Up      ToC       Page 70 
   Before sending the cached Route Reply, however, the node MAY delay
   the Reply in order to help prevent a possible Route Reply "storm", as
   described in Section 8.2.5.

   If the node returns a cached Route Reply as described above, then the
   node MUST NOT propagate the Route Request further (i.e., the node
   MUST NOT rebroadcast the Route Request).  In this case, instead, if
   the packet contains no other DSR options and contains no payload
   after the DSR Options header (e.g., the Route Request is not
   piggybacked on a TCP or UDP packet), then the node SHOULD simply
   discard the packet.  Otherwise (if the packet contains other DSR
   options or contains any payload after the DSR Options header), the
   node SHOULD forward the packet along the cached route to the target
   of the Route Request.  Specifically, if the node does so, it MUST use
   the following steps:

   -  Copy the Target Address from the Route Request option in the DSR
      Options header to the Destination Address field in the packet's IP
      header.

   -  Remove the Route Request option from the DSR Options header in the
      packet, and add a DSR Source Route option to the packet's DSR
      Options header.

   -  In the DSR Source Route option, set the Address[i] fields to
      represent the source route found in this node's Route Cache to the
      original target of the Route Discovery (the new IP Destination
      Address of the packet).  Specifically, the node copies the hop
      addresses of the source route into sequential Address[i] fields in
      the DSR Source Route option, for i = 1, 2, ..., n.  Address[1],
      here, is the address of this node itself (the first address in the
      source route found from this node to the original target of the
      Route Discovery).  The value n, here, is the number of hop
      addresses in this source route, excluding the destination of the
      packet (which is instead already represented in the Destination
      Address field in the packet's IP header).

   -  Initialize the Segments Left field in the DSR Source Route option
      to n as defined above.

   -  The First Hop External (F) bit in the DSR Source Route option MUST
      be set to 0.

   -  The Last Hop External (L) bit in the DSR Source Route option is
      copied from the External bit flagging the last hop in the source
      route for the packet, as indicated in the Route Cache.

Top      Up      ToC       Page 71 
   -  The Salvage field in the DSR Source Route option MUST be
      initialized to some nonzero value; the particular nonzero value
      used SHOULD be MAX_SALVAGE_COUNT.  By initializing this field to a
      nonzero value, nodes forwarding or overhearing this packet will
      not consider a link to exist between the IP Source Address of the
      packet and the Address[1] address in the DSR Source Route option
      (e.g., they will not attempt to add this to their Route Cache as a
      link).  By choosing MAX_SALVAGE_COUNT as the nonzero value to
      which the node initializes this field, nodes furthermore will not
      attempt to salvage this packet.

   -  Transmit the packet to the next-hop node on the new source route
      in the packet, using the forwarding procedure described in Section
      8.1.5.

8.2.4.  Originating a Route Reply

   A node originates a Route Reply in order to reply to a received and
   processed Route Request, according to the procedures described in
   Sections 8.2.2 and 8.2.3.  The Route Reply is returned in a Route
   Reply option (Section 6.3).  The Route Reply option MAY be returned
   to the initiator of the Route Request in a separate IP packet, used
   only to carry this Route Reply option, or it MAY be included in any
   other IP packet being sent to this address.

   The Route Reply option MUST be included in a DSR Options header in
   the packet returned to the initiator.  To initialize the Route Reply
   option, the node performs the following sequence of steps:

   -  The Option Type in the option MUST be set to the value 3.

   -  The Opt Data Len field in the option MUST be set to the value
      (n * 4) + 3, where n is the number of addresses in the source
      route being returned (excluding the Route Discovery initiator
      node's address).

   -  If this node is the target of the Route Request, the Last Hop
      External (L) bit in the option MUST be initialized to 0.

   -  The Reserved field in the option MUST be initialized to 0.

   -  The Route Request Identifier MUST be initialized to the Identifier
      field of the Route Request to which this Route Reply is sent in
      response.

   -  The sequence of hop addresses in the source route are copied into
      the Address[i] fields of the option.  Address[1] MUST be set to
      the first-hop address of the route after the initiator of the

Top      Up      ToC       Page 72 
      Route Discovery, Address[n] MUST be set to the last-hop address of
      the source route (the address of the target node), and each other
      Address[i] MUST be set to the next address in sequence in the
      source route being returned.

   The Destination Address field in the IP header of the packet carrying
   the Route Reply option MUST be set to the address of the initiator of
   the Route Discovery (i.e., for a Route Reply being returned in
   response to some Route Request, the IP Source Address of the Route
   Request).

   After creating and initializing the Route Reply option and the IP
   packet containing it, send the Route Reply.  In sending the Route
   Reply from this node (but not from nodes forwarding the Route Reply),
   this node SHOULD delay the Reply by a small jitter period chosen
   randomly between 0 and BroadcastJitter.

   When returning any Route Reply in the case in which the MAC protocol
   in use in the network is not capable of transmitting unicast packets
   over unidirectional links, the source route used for routing the
   Route Reply packet MUST be obtained by reversing the sequence of hops
   in the Route Request packet (the source route that is then returned
   in the Route Reply).  This restriction on returning a Route Reply
   enables the Route Reply to test this sequence of hops for
   bidirectionality, preventing the Route Reply from being received by
   the initiator of the Route Discovery unless each of the hops over
   which the Route Reply is returned (and thus each of the hops in the
   source route being returned in the Reply) is bidirectional.

   If sending a Route Reply to the initiator of the Route Request
   requires performing a Route Discovery, the Route Reply option MUST be
   piggybacked on the packet that contains the Route Request.  This
   piggybacking prevents a recursive dependency wherein the target of
   the new Route Request (which was itself the initiator of the original
   Route Request) must do another Route Request in order to return its
   Route Reply.

   If sending the Route Reply to the initiator of the Route Request does
   not require performing a Route Discovery, a node SHOULD send a
   unicast Route Reply in response to every Route Request it receives
   for which it is the target node.

8.2.5.  Preventing Route Reply Storms

   The ability for nodes to reply to a Route Request based on
   information in their Route Caches, as described in Sections 3.3.2 and
   8.2.3, could result in a possible Route Reply "storm" in some cases.
   In particular, if a node broadcasts a Route Request for a target node

Top      Up      ToC       Page 73 
   for which the node's neighbors have a route in their Route Caches,
   each neighbor may attempt to send a Route Reply, thereby wasting
   bandwidth and possibly increasing the number of network collisions in
   the area.

   For example, the figure below shows a situation in which nodes B, C,
   D, E, and F all receive A's Route Request for target G, and each has
   the indicated route cached for this target:

                +-----+                 +-----+
                |  D  |<               >|  C  |
                +-----+ \             / +-----+
      Cache: C - B - G   \           /  Cache: B - G
                          \ +-----+ /
                           -|  A  |-
                            +-----+\     +-----+     +-----+
                             |   |  \--->|  B  |     |  G  |
                            /     \      +-----+     +-----+
                           /       \     Cache: G
                          v         v
                    +-----+         +-----+
                    |  E  |         |  F  |
                    +-----+         +-----+
               Cache: F - B - G     Cache: B - G

   Normally, each of these nodes would attempt to reply from its own
   Route Cache, and they would thus all send their Route Replies at
   about the same time, since they all received the broadcast Route
   Request at about the same time.  Such simultaneous Route Replies from
   different nodes all receiving the Route Request may cause local
   congestion in the wireless network and may create packet collisions
   among some or all of these Replies if the MAC protocol in use does
   not provide sufficient collision avoidance for these packets.  In
   addition, it will often be the case that the different replies will
   indicate routes of different lengths, as shown in this example.

   In order to reduce these effects, if a node can put its network
   interface into promiscuous receive mode, it MAY delay sending its own
   Route Reply for a short period, while listening to see if the
   initiating node begins using a shorter route first.  Specifically,
   this node MAY delay sending its own Route Reply for a random period

      d = H * (h - 1 + r)

   where h is the length in number of network hops for the route to be
   returned in this node's Route Reply, r is a random floating point
   number between 0 and 1, and H is a small constant delay (at least
   twice the maximum wireless link propagation delay) to be introduced

Top      Up      ToC       Page 74 
   per hop.  This delay effectively randomizes the time at which each
   node sends its Route Reply, with all nodes sending Route Replies
   giving routes of length less than h sending their Replies before this
   node, and all nodes sending Route Replies giving routes of length
   greater than h send their Replies after this node.

   Within the delay period, this node promiscuously receives all
   packets, looking for data packets from the initiator of this Route
   Discovery destined for the target of the Route Discovery.  If such a
   data packet received by this node during the delay period uses a
   source route of length less than or equal to h, this node may infer
   that the initiator of the Route Discovery has already received a
   Route Reply giving an equally good or better route.  In this case,
   this node SHOULD cancel its delay timer and SHOULD NOT send its Route
   Reply for this Route Discovery.

8.2.6.  Processing a Received Route Reply Option

   Section 8.1.4 describes the general processing for a received packet,
   including the addition of routing information from options in the
   packet's DSR Options header to the receiving node's Route Cache.

   If the received packet contains a Route Reply, no additional special
   processing of the Route Reply option is required beyond what is
   described there.  As described in Section 4.1, anytime a node adds
   new information to its Route Cache (including the information added
   from this Route Reply option), the node SHOULD check each packet in
   its own Send Buffer (Section 4.2) to determine whether a route to
   that packet's IP Destination Address now exists in the node's Route
   Cache (including the information just added to the Cache).  If so,
   the packet SHOULD then be sent using that route and removed from the
   Send Buffer.  This general procedure handles all processing required
   for a received Route Reply option.

   When using a MAC protocol that requires bidirectional links for
   unicast transmission, a unidirectional link may be discovered by the
   propagation of the Route Request.  When the Route Reply is sent over
   the reverse path, a forwarding node may discover that the next-hop is
   unreachable.  In this case, it MUST add the next-hop address to its
   blacklist (Section 4.6).

8.3.  Route Maintenance Processing

   Route Maintenance is the mechanism by which a source node S is able
   to detect, while using a source route to some destination node D, if
   the network topology has changed such that it can no longer use its
   route to D because a link along the route no longer works.  When
   Route Maintenance indicates that a source route is broken, S can

Top      Up      ToC       Page 75 
   attempt to use any other route it happens to know to D or can invoke
   Route Discovery again to find a new route for subsequent packets to
   D.  Route Maintenance for this route is used only when S is actually
   sending packets to D.

   Specifically, when forwarding a packet, a node MUST attempt to
   confirm the reachability of the next-hop node, unless such
   confirmation had been received in the last MaintHoldoffTime period.
   Individual implementations MAY choose to bypass such confirmation for
   some limited number of packets, as long as those packets all fall
   within MaintHoldoffTime since the last confirmation.  If no
   confirmation is received after the retransmission of MaxMaintRexmt
   acknowledgement requests, after the initial transmission of the
   packet, and conceptually including all retransmissions provided by
   the MAC layer, the node determines that the link for this next-hop
   node of the source route is "broken".  This confirmation from the
   next-hop node for Route Maintenance can be implemented using a link-
   layer acknowledgement (Section 8.3.1), a "passive acknowledgement"
   (Section 8.3.2), or a network-layer acknowledgement (Section 8.3.3);
   the particular strategy for retransmission timing depends on the type
   of acknowledgement mechanism used.  When not using link-layer
   acknowledgements for Route Maintenance, nodes SHOULD use passive
   acknowledgements when possible but SHOULD try requesting a network-
   layer acknowledgement one or more times before deciding that the link
   has failed and originating a Route Error to the original sender of
   the packet, as described in Section 8.3.4.

   In deciding whether or not to send a Route Error in response to
   attempting to forward a packet from some sender over a broken link, a
   node MUST limit the number of consecutive packets from a single
   sender that the node attempts to forward over this same broken link
   for which the node chooses not to return a Route Error.  This
   requirement MAY be satisfied by returning a Route Error for each
   packet that the node attempts to forward over a broken link.

8.3.1.  Using Link-Layer Acknowledgements

   If the MAC protocol in use provides feedback as to the successful
   delivery of a data packet (such as is provided for unicast packets by
   the link-layer acknowledgement frame defined by IEEE 802.11
   [IEEE80211]), then the use of the DSR Acknowledgement Request and
   Acknowledgement options is not necessary.  If such link-layer
   feedback is available, it SHOULD be used instead of any other
   acknowledgement mechanism for Route Maintenance, and the node SHOULD
   NOT use either passive acknowledgements or network-layer
   acknowledgements for Route Maintenance.

Top      Up      ToC       Page 76 
   When using link-layer acknowledgements for Route Maintenance, the
   retransmission timing and the timing at which retransmission attempts
   are scheduled are generally controlled by the particular link layer
   implementation in use in the network.  For example, in IEEE 802.11,
   the link-layer acknowledgement is returned after a unicast packet as
   a part of the basic access method of the IEEE 802.11 Distributed
   Coordination Function (DCF) MAC protocol; the time at which the
   acknowledgement is expected to arrive and the time at which the next
   retransmission attempt (if necessary) will occur are controlled by
   the MAC protocol implementation.

   When a node receives a link-layer acknowledgement for any packet in
   its Maintenance Buffer, that node SHOULD remove from its Maintenance
   Buffer that packet, as well as any other packets in its Maintenance
   Buffer with the same next-hop destination.

8.3.2.  Using Passive Acknowledgements

   When link-layer acknowledgements are not available, but passive
   acknowledgements [JUBIN87] are available, passive acknowledgements
   SHOULD be used for Route Maintenance when originating or forwarding a
   packet along any hop other than the last hop (the hop leading to the
   IP Destination Address node of the packet).  In particular, passive
   acknowledgements SHOULD be used for Route Maintenance in such cases
   if the node can place its network interface into "promiscuous"
   receive mode, and if network links used for data packets generally
   operate bidirectionally.

   A node MUST NOT attempt to use passive acknowledgements for Route
   Maintenance for a packet originated or forwarded over its last hop
   (the hop leading to the IP Destination Address node of the packet),
   since the receiving node will not be forwarding the packet and thus
   no passive acknowledgement will be available to be heard by this
   node.  Beyond this restriction, a node MAY utilize a variety of
   strategies in using passive acknowledgements for Route Maintenance of
   a packet that it originates or forwards.  For example, the following
   two strategies are possible:

   -  Each time a node receives a packet to be forwarded to a node other
      than the final destination (the IP Destination Address of the
      packet), that node sends the original transmission of that packet
      without requesting a network-layer acknowledgement for it.  If no
      passive acknowledgement is received within PassiveAckTimeout after
      this transmission, the node retransmits the packet, again without
      requesting a network-layer acknowledgement for it; the same
      PassiveAckTimeout timeout value is used for each such attempt.  If
      no acknowledgement has been received after a total of
      TryPassiveAcks retransmissions of the packet, network-layer

Top      Up      ToC       Page 77 
      acknowledgements (as described in Section 8.3.3) are requested for
      all remaining attempts for that packet.

   -  Each node maintains a table of possible next-hop destination
      nodes, noting whether or not passive acknowledgements can
      typically be expected from transmission to that node, and the
      expected latency and jitter of a passive acknowledgement from that
      node.  Each time a node receives a packet to be forwarded to a
      node other than the IP Destination Address, the node checks its
      table of next-hop destination nodes to determine whether to use a
      passive acknowledgement or a network-layer acknowledgement for
      that transmission to that node.  The timeout for this packet can
      also be derived from this table.  A node using this method SHOULD
      prefer using passive acknowledgements to network-layer
      acknowledgements.

   In using passive acknowledgements for a packet that it originates or
   forwards, a node considers the later receipt of a new packet (e.g.,
   with promiscuous receive mode enabled on its network interface) an
   acknowledgement of this first packet if both of the following two
   tests succeed:

   -  The Source Address, Destination Address, Protocol, Identification,
      and Fragment Offset fields in the IP header of the two packets
      MUST match [RFC791].

   -  If either packet contains a DSR Source Route header, both packets
      MUST contain one, and the value in the Segments Left field in the
      DSR Source Route header of the new packet MUST be less than that
      in the first packet.

   When a node hears such a passive acknowledgement for any packet in
   its Maintenance Buffer, that node SHOULD remove from its Maintenance
   Buffer that packet, as well as any other packets in its Maintenance
   Buffer with the same next-hop destination.

8.3.3.  Using Network-Layer Acknowledgements

   When a node originates or forwards a packet and has no other
   mechanism of acknowledgement available to determine reachability of
   the next-hop node in the source route for Route Maintenance, that
   node SHOULD request a network-layer acknowledgement from that next-
   hop node.  To do so, the node inserts an Acknowledgement Request
   option in the DSR Options header in the packet.  The Identification
   field in that Acknowledgement Request option MUST be set to a value
   unique over all packets recently transmitted by this node to the same
   next-hop node.

Top      Up      ToC       Page 78 
   When a node receives a packet containing an Acknowledgement Request
   option, that node performs the following tests on the packet:

   -  If the indicated next-hop node address for this packet does not
      match any of this node's own IP addresses, then this node MUST NOT
      process the Acknowledgement Request option.  The indicated next-
      hop node address is the next Address[i] field in the DSR Source
      Route option in the DSR Options header in the packet, or the IP
      Destination Address in the packet if the packet does not contain a
      DSR Source Route option or the Segments Left there is zero.

   -  If the packet contains an Acknowledgement option, then this node
      MUST NOT process the Acknowledgement Request option.

   If neither of the tests above fails, then this node MUST process the
   Acknowledgement Request option by sending an Acknowledgement option
   to the previous-hop node; to do so, the node performs the following
   sequence of steps:

   -  Create a packet and set the IP Protocol field to the protocol
      number assigned for DSR (48).

   -  Set the IP Source Address field in this packet to the IP address
      of this node, copied from the source route in the DSR Source Route
      option in that packet (or from the IP Destination Address field of
      the packet, if the packet does not contain a DSR Source Route
      option).

   -  Set the IP Destination Address field in this packet to the IP
      address of the previous-hop node, copied from the source route in
      the DSR Source Route option in that packet (or from the IP Source
      Address field of the packet, if the packet does not contain a DSR
      Source Route option).

   -  Add a DSR Options header to the packet.  Set the Next Header field
      in the DSR Options header to the value 59, "No Next Header"
      [RFC2460].

   -  Add an Acknowledgement option to the DSR Options header in the
      packet; set the Acknowledgement option's Option Type field to 6
      and the Opt Data Len field to 10.

   -  Copy the Identification field from the received Acknowledgement
      Request option into the Identification field in the
      Acknowledgement option.

Top      Up      ToC       Page 79 
   -  Set the ACK Source Address field in the Acknowledgement option to
      be the IP Source Address of this new packet (set above to be the
      IP address of this node).

   -  Set the ACK Destination Address field in the Acknowledgement
      option to be the IP Destination Address of this new packet (set
      above to be the IP address of the previous-hop node).

   -  Send the packet as described in Section 8.1.1.

   Packets containing an Acknowledgement option SHOULD NOT be placed in
   the Maintenance Buffer.

   When a node receives a packet with both an Acknowledgement option and
   an Acknowledgement Request option, if that node is not the
   destination of the Acknowledgement option (the IP Destination Address
   of the packet), then the Acknowledgement Request option MUST be
   ignored.  Otherwise (that node is the destination of the
   Acknowledgement option), that node MUST process the Acknowledgement
   Request option by returning an Acknowledgement option according to
   the following sequence of steps:

   -  Create a packet and set the IP Protocol field to the protocol
      number assigned for DSR (48).

   -  Set the IP Source Address field in this packet to the IP address
      of this node, copied from the source route in the DSR Source Route
      option in that packet (or from the IP Destination Address field of
      the packet, if the packet does not contain a DSR Source Route
      option).

   -  Set the IP Destination Address field in this packet to the IP
      address of the node originating the Acknowledgement option.

   -  Add a DSR Options header to the packet, and set the DSR Options
      header's Next Header field to the value 59, "No Next Header"
      [RFC2460].

   -  Add an Acknowledgement option to the DSR Options header in this
      packet; set the Acknowledgement option's Option Type field to 6
      and the Opt Data Len field to 10.

   -  Copy the Identification field from the received Acknowledgement
      Request option into the Identification field in the
      Acknowledgement option.

Top      Up      ToC       Page 80 
   -  Set the ACK Source Address field in the option to the IP Source
      Address of this new packet (set above to be the IP address of this
      node).

   -  Set the ACK Destination Address field in the option to the IP
      Destination Address of this new packet (set above to be the IP
      address of the node originating the Acknowledgement option).

   -  Send the packet directly to the destination.  The IP Destination
      Address MUST be treated as a direct neighbor node: the
      transmission to that node MUST be done in a single IP forwarding
      hop, without Route Discovery and without searching the Route
      Cache.  In addition, this packet MUST NOT contain a DSR
      Acknowledgement Request, MUST NOT be retransmitted for Route
      Maintenance, and MUST NOT expect a link-layer acknowledgement or
      passive acknowledgement.

   When using network-layer acknowledgements for Route Maintenance, a
   node SHOULD use an adaptive algorithm in determining the
   retransmission timeout for each transmission attempt of an
   acknowledgement request.  For example, a node SHOULD maintain a
   separate round-trip time (RTT) estimate for each node to which it has
   recently attempted to transmit packets, and it SHOULD use this RTT
   estimate in setting the timeout for each retransmission attempt for
   Route Maintenance.  The TCP RTT estimation algorithm has been shown
   to work well for this purpose in implementation and testbed
   experiments with DSR [MALTZ99b, MALTZ01].

8.3.4.  Originating a Route Error

   When a node is unable to verify reachability of a next-hop node after
   reaching a maximum number of retransmission attempts, it SHOULD send
   a Route Error to the IP Source Address of the packet.  When sending a
   Route Error for a packet containing either a Route Error option or an
   Acknowledgement option, a node SHOULD add these existing options to
   its Route Error, subject to the limit described below.

   A node transmitting a Route Error MUST perform the following steps:

   -  Create an IP packet and set the IP Protocol field to the protocol
      number assigned for DSR (48).  Set the Source Address field in
      this packet's IP header to the address of this node.

   -  If the Salvage field in the DSR Source Route option in the packet
      triggering the Route Error is zero, then copy the Source Address
      field of the packet triggering the Route Error into the
      Destination Address field in the new packet's IP header;

Top      Up      ToC       Page 81 
      otherwise, copy the Address[1] field from the DSR Source Route
      option of the packet triggering the Route Error into the
      Destination Address field in the new packet's IP header

   -  Insert a DSR Options header into the new packet.

   -  Add a Route Error Option to the new packet, setting the Error Type
      to NODE_UNREACHABLE, the Salvage value to the Salvage value from
      the DSR Source Route option of the packet triggering the Route
      Error, and the Unreachable Node Address field to the address of
      the next-hop node from the original source route.  Set the Error
      Source Address field to this node's IP address, and the Error
      Destination field to the new packet's IP Destination Address.

   -  If the packet triggering the Route Error contains any Route Error
      or Acknowledgement options, the node MAY append to its Route Error
      each of these options, with the following constraints:

      o  The node MUST NOT include any Route Error option from the
         packet triggering the new Route Error, for which the total
         Salvage count (Section 6.4) of that included Route Error would
         be greater than MAX_SALVAGE_COUNT in the new packet.

      o  If any Route Error option from the packet triggering the new
         Route Error is not included in the packet, the node MUST NOT
         include any following Route Error or Acknowledgement options
         from the packet triggering the new Route Error.

      o  Any appended options from the packet triggering the Route Error
         MUST follow the new Route Error in the packet.

      o  In appending these options to the new Route Error, the order of
         these options from the packet triggering the Route Error MUST
         be preserved.

   -  Send the packet as described in Section 8.1.1.

8.3.5.  Processing a Received Route Error Option

   When a node receives a packet containing a Route Error option, that
   node MUST process the Route Error option according to the following
   sequence of steps:

   -  The node MUST remove from its Route Cache the link from the node
      identified by the Error Source Address field to the node
      identified by the Unreachable Node Address field (if this link is
      present in its Route Cache).  If the node implements its Route
      Cache as a link cache, as described in Section 4.1, only this

Top      Up      ToC       Page 82 
      single link is removed; if the node implements its Route Cache as
      a path cache, however, all routes (paths) that use this link are
      either truncated before the link or removed completely.

   -  If the option following the Route Error is an Acknowledgement or
      Route Error option sent by this node (that is, with
      Acknowledgement or Error Source Address equal to this node's
      address), copy the DSR options following the current Route Error
      into a new packet with IP Source Address equal to this node's own
      IP address and IP Destination Address equal to the Acknowledgement
      or Error Destination Address.  Transmit this packet as described
      in Section 8.1.1, with the Salvage count in the DSR Source Route
      option set to the Salvage value of the Route Error.

   In addition, after processing the Route Error as described above, the
   node MAY initiate a new Route Discovery for any destination node for
   which it then has no route in its Route Cache as a result of
   processing this Route Error, if the node has indication that a route
   to that destination is needed.  For example, if the node has an open
   TCP connection to some destination node, then if the processing of
   this Route Error removed the only route to that destination from this
   node's Route Cache, then this node MAY initiate a new Route Discovery
   for that destination node.  Any node, however, MUST limit the rate at
   which it initiates new Route Discoveries for any single destination
   address, and any new Route Discovery initiated in this way as part of
   processing this Route Error MUST conform as a part of this limit.

8.3.6.  Salvaging a Packet

   When an intermediate node forwarding a packet detects through Route
   Maintenance that the next-hop link along the route for that packet is
   broken (Section 8.3), if the node has another route to the packet's
   IP Destination Address in its Route Cache, the node SHOULD "salvage"
   the packet rather than discard it.  To do so using the route found in
   its Route Cache, this node processes the packet as follows:

   -  If the MAC protocol in use in the network is not capable of
      transmitting unicast packets over unidirectional links, as
      discussed in Section 3.3.1, then if this packet contains a Route
      Reply option, remove and discard the Route Reply option in the
      packet; if the DSR Options header in the packet then contains no
      DSR options or only a DSR Source Route Option, remove the DSR
      Options header from the packet.  If the resulting packet then
      contains only an IP header (e.g., no transport layer header or
      payload), the node SHOULD NOT salvage the packet and instead
      SHOULD discard the entire packet.

Top      Up      ToC       Page 83 
   -  Modify the existing DSR Source Route option in the packet so that
      the Address[i] fields represent the source route found in this
      node's Route Cache to this packet's IP Destination Address.
      Specifically, the node copies the hop addresses of the source
      route into sequential Address[i] fields in the DSR Source Route
      option, for i = 1, 2, ..., n.  Address[1], here, is the address of
      the salvaging node itself (the first address in the source route
      found from this node to the IP Destination Address of the packet).
      The value n, here, is the number of hop addresses in this source
      route, excluding the destination of the packet (which is instead
      already represented in the Destination Address field in the
      packet's IP header).

   -  Initialize the Segments Left field in the DSR Source Route option
      to n as defined above.

   -  The First Hop External (F) bit in the DSR Source Route option MUST
      be set to 0.

   -  The Last Hop External (L) bit in the DSR Source Route option is
      copied from the External bit flagging the last hop in the source
      route for the packet, as indicated in the Route Cache.

   -  The Salvage field in the DSR Source Route option is set to 1 plus
      the value of the Salvage field in the DSR Source Route option of
      the packet that caused the error.

   -  Transmit the packet to the next-hop node on the new source route
      in the packet, using the forwarding procedure described in Section
      8.1.5.

   As described in Section 8.3.4, the node in this case also SHOULD
   return a Route Error to the original sender of the packet.  If the
   node chooses to salvage the packet, it SHOULD do so after originating
   the Route Error.

   When returning any Route Reply in the case in which the MAC protocol
   in use in the network is not capable of transmitting unicast packets
   over unidirectional links, the source route used for routing the
   Route Reply packet MUST be obtained by reversing the sequence of hops
   in the Route Request packet (the source route that is then returned
   in the Route Reply).  This restriction on returning a Route Reply and
   on salvaging a packet that contains a Route Reply option enables the
   Route Reply to test this sequence of hops for bidirectionality,
   preventing the Route Reply from being received by the initiator of
   the Route Discovery unless each of the hops over which the Route
   Reply is returned (and thus each of the hops in the source route
   being returned in the Reply) is bidirectional.


Next RFC Part