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 4 of 4, p. 84 to 107
Prev RFC Part

 


prevText      Top      Up      ToC       Page 84 
8.4.  Multiple Network Interface Support

   A node using DSR MAY have multiple network interfaces that support
   DSR ad hoc network routing.  This section describes special packet
   processing at such nodes.

   A node with multiple network interfaces that support DSR ad hoc
   network routing MUST have some policy for determining which Route
   Request packets are forwarded using which network interfaces.  For
   example, a node MAY choose to forward all Route Requests over all
   network interfaces.

   When a node with multiple network interfaces that support DSR
   propagates a Route Request on a network interface other than the one
   on which it received the Route Request, it MUST in this special case
   modify the Address list in the Route Request as follows:

   -  Append the node's IP address for the incoming network interface.

   -  Append the node's IP address for the outgoing network interface.

   When a node forwards a packet containing a source route, it MUST
   assume that the next-hop node is reachable on the incoming network
   interface, unless the next hop is the address of one of this node's
   network interfaces, in which case this node MUST skip over this
   address in the source route and process the packet in the same way as
   if it had just received it from that network interface, as described
   in Section 8.1.5.

   If a node that previously had multiple network interfaces that
   support DSR receives a packet sent with a source route specifying a
   change to a network interface, as described above, that is no longer
   available, it MAY send a Route Error to the source of the packet
   without attempting to forward the packet on the incoming network
   interface, unless the network uses an autoconfiguration mechanism
   that may have allowed another node to acquire the now unused address
   of the unavailable network interface.

8.5.  IP Fragmentation and Reassembly

   When a node using DSR wishes to fragment a packet that contains a DSR
   header not containing a Route Request option, it MUST perform the
   following sequence of steps:

   -  Remove the DSR Options header from the packet.

Top      Up      ToC       Page 85 
   -  Fragment the packet using normal IP fragmentation processing
      [RFC791].  However, when determining the size of each fragment to
      create from the original packet, the fragment size MUST be reduced
      by the size of the DSR Options header from the original packet.

   -  IP-in-IP encapsulate each fragment [RFC2003].  The IP Destination
      address of the outer (encapsulating) packet MUST be set equal to
      the IP Destination address of the original packet.

   -  Add the DSR Options header from the original packet to each
      resulting encapsulating packet.  If a Source Route header is
      present in the DSR Options header, increment the Salvage field.

   When a node using the DSR protocol receives an IP-in-IP encapsulated
   packet destined to itself, it SHOULD decapsulate the packet [RFC2003]
   and then process the inner packet according to standard IP reassembly
   processing [RFC791].

8.6.  Flow State Processing

   A node implementing the optional DSR flow state extension MUST follow
   these additional processing steps.

8.6.1.  Originating a Packet

   When originating any packet to be routed using flow state, a node
   using DSR flow state MUST do the following:

   -  If the route to be used for this packet has never had a DSR flow
      state established along it (or the existing flow state has
      expired):

      o  Generate a 16-bit Flow ID larger than any unexpired Flow IDs
         used by this node for this destination.  Odd Flow IDs MUST be
         chosen for "default" flows; even Flow IDs MUST be chosen for
         non-default flows.

      o  Add a DSR Options header, as described in Section 8.1.2.

      o  Add a DSR Flow State header, as described in Section 8.6.2.

      o  Initialize the Hop Count field in the DSR Flow State header to
         0.

      o  Set the Flow ID field in the DSR Flow State header to the Flow
         ID generated in the first step.

      o  Add a Timeout option to the DSR Options header.

Top      Up      ToC       Page 86 
      o  Add a Source Route option after the Timeout option with the
         route to be used, as described in Section 8.1.3.

      o  The source node SHOULD record this flow in its Flow Table.

      o  If this flow is recorded in the Flow Table, the TTL in this
         Flow Table entry MUST be set to be the TTL of this flow
         establishment packet.

      o  If this flow is recorded in the Flow Table, the timeout in this
         Flow Table entry MUST be set to a value no less than the value
         specified in the Timeout option.

   -  If the route to be used for this packet has had DSR flow state
      established along it, but has not been established end-to-end:

      o  Add a DSR Options header, as described in Section 8.1.2.

      o  Add a DSR Flow State header, as described in Section 8.6.2.

      o  Initialize the Hop Count field in the DSR Flow State header to
         0.

      o  The Flow ID field of the DSR Flow State header SHOULD be the
         Flow ID previously used for this route.  If it is not, the
         steps for sending packets along never-before-established routes
         above MUST be followed in place of these.

      o  Add a Timeout option to the DSR Options header, setting the
         Timeout to a value not greater than the timeout remaining for
         this flow in the Flow Table.

      o  Add a Source Route option after the Timeout option with the
         route to be used, as described in Section 8.1.3.

      o  If the IP TTL is not equal to the TTL specified in the Flow
         Table, the source node MUST set a flag to indicate that this
         flow cannot be used as default.

   -  If the route the node wishes to use for this packet has been
      established as a flow end-to-end and is not the default flow:

      o  Add a DSR Flow State header, as described in Section 8.6.2.

      o  Initialize the Hop Count field in the DSR Flow State header to
         0.

Top      Up      ToC       Page 87 
      o  The Flow ID field of the DSR Flow State header SHOULD be set to
         the Flow ID previously used for this route.  If it is not, the
         steps for sending packets along never-before-established routes
         above MUST be followed in place of these.

      o  If the next hop requires a network-layer acknowledgement for
         Route Maintenance, add a DSR Options header, as described in
         Section 8.1.2, and an Acknowledgement Request option, as
         described in Section 8.3.3.

      o  A DSR Options header SHOULD NOT be added to a packet, unless it
         is added to carry an Acknowledgement Request option, in which
         case:

         +  A Source Route option in the DSR Options header SHOULD NOT
            be added.

         +  If a Source Route option in the DSR Options header is added,
            the steps for sending packets along flows not yet
            established end-to-end MUST be followed in place of these.

         +  A Timeout option SHOULD NOT be added.

         +  If a Timeout option is added, it MUST specify a timeout not
            greater than the timeout remaining for this flow in the Flow
            Table.

   -  If the route the node wishes to use for this packet has been
      established as a flow end-to-end and is the current default flow:

      o  If the IP TTL is not equal to the TTL specified in the Flow
         Table, the source node MUST follow the steps above for sending
         a packet along a non-default flow that has been established
         end-to-end in place of these steps.

      o  If the next hop requires a network-layer acknowledgement for
         Route Maintenance, the sending node MUST add a DSR Options
         header and an Acknowledgement Request option, as described in
         Section 8.3.3.  The sending node MUST NOT add any additional
         options to this header.

      o  A DSR Options header SHOULD NOT be added, except as specified
         in the previous step.  If one is added in a way inconsistent
         with the previous step, the source node MUST follow the steps
         above for sending a packet along a non-default flow that has
         been established end-to-end in place of these steps.

Top      Up      ToC       Page 88 
8.6.2.  Inserting a DSR Flow State Header

   A node originating a packet adds a DSR Flow State header to the
   packet, if necessary, to carry information needed by the routing
   protocol.  A packet MUST NOT contain more than one DSR Flow State
   header.  A DSR Flow State header is added to a packet by performing
   the following sequence of steps:

   -  Insert a DSR Flow State header after the IP header and any Hop-
      by-Hop Options header that may already be in the packet, but
      before any other header that may be present.

   -  Set the Next Header field of the DSR Flow State header to the Next
      Header field of the previous header (either an IP header or a
      Hop-by-Hop Options header).

   -  Set the Flow (F) bit in the DSR Flow State header to 1.

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

8.6.3.  Receiving a Packet

   This section describes processing only for packets that are sent to
   this processing node as the next-hop node; that is, when the MAC-
   layer destination address is the MAC address of this node.
   Otherwise, the process described in Sections 8.6.5 should be
   followed.

   The flow along which a packet is being sent is considered to be in
   the Flow Table if the triple (IP Source Address, IP Destination
   Address, Flow ID) has an unexpired entry in this node's Flow Table.

   When a node using DSR flow state receives a packet, it MUST follow
   the following steps for processing:

   -  If a DSR Flow State header is present, increment the Hop Count
      field.

   -  In addition, if a DSR Flow State header is present, then if the
      triple (IP Source Address, IP Destination Address, Flow ID) is in
      this node's Automatic Route Shortening Table and the packet is
      listed in the entry, then the node MAY send a gratuitous Route
      Reply as described in Section 4.4, subject to the rate limiting
      specified therein.  This gratuitous Route Reply gives the route by
      which the packet originally reached this node.  Specifically, the
      node sending the gratuitous Route Reply constructs the route to
      return in the Route Reply as follows:

Top      Up      ToC       Page 89 
      o  Let k = (packet Hop Count) - (table Hop Count), where packet
         Hop Count is the value of the Hop Count field in this received
         packet, and table Hop Count is the Hop Count value stored for
         this packet in the corresponding entry in this node's Automatic
         Route Shortening Table.

      o  Copy the complete source route for this flow from the
         corresponding entry in the node's Flow Table.

      o  Remove from this route the k hops immediately preceding this
         node in the route, since these are the hops "skipped over" by
         the packet as recorded in the Automatic Route Shortening Table
         entry.

   -  Process each of the DSR options within the DSR Options header in
      order:

      o  On receiving a Pad1 or PadN option, skip over the option.

      o  On receiving a Route Request for which this node is the
         destination, remove the option and return a Route Reply as
         specified in Section 8.2.2.

      o  On receiving a broadcast Route Request that this node has not
         previously seen for which this node is not the destination,
         append this node's incoming interface address to the Route
         Request, continue propagating the Route Request as specified in
         Section 8.2.2, pass the payload, if any, to the network layer,
         and stop processing.

      o  On receiving a Route Request that this node has previously seen
         for which this node is not the destination, discard the packet
         and stop processing.

      o  On receiving any Route Request, add appropriate links to the
         Route Cache, as specified in Section 8.2.2.

      o  On receiving a Route Reply for which this node is the
         initiator, remove the Route Reply from the packet and process
         it as specified in Section 8.2.6.

      o  On receiving any Route Reply, add appropriate links to the
         Route Cache, as specified in Section 8.2.6.

      o  On receiving any Route Error of type NODE_UNREACHABLE, remove
         appropriate links to the Route Cache, as specified in Section
         8.3.5.

Top      Up      ToC       Page 90 
      o  On receiving a Route Error of type NODE_UNREACHABLE that this
         node is the Error Destination Address of, remove the Route
         Error from the packet and process it as specified in Section
         8.3.5.  It also MUST stop originating packets along any flows
         using the link from Error Source Address to Unreachable Node,
         and it MAY remove from its Flow Table any flows using the link
         from Error Source Address to Unreachable Node.

      o  On receiving a Route Error of type UNKNOWN_FLOW that this node
         is not the Error Destination Address of, the node checks if the
         Route Error corresponds to a flow in its Flow Table.  If it
         does not, the node silently discards the Route Error;
         otherwise, it forwards the packet to the expected previous hop
         of the corresponding flow.  If Route Maintenance cannot confirm
         the reachability of the previous hop, the node checks if the
         network interface requires bidirectional links for operation.
         If it does, the node silently discards the Route Error;
         otherwise, it sends the Error as if it were originating it, as
         described in Section 8.1.1.

      o  On receiving a Route Error of type UNKNOWN_FLOW that this node
         is the Error Destination Address of, remove the Route Error
         from the packet and mark the flow specified by the triple
         (Error Destination Address, Original IP Destination Address,
         Flow ID) as not having been established end-to-end.

      o  On receiving a Route Error of type DEFAULT_FLOW_UNKNOWN that
         this node is not the Error Destination Address of, the node
         checks if the Route Error corresponds to a flow in its Default
         Flow Table.  If it does not, the node silently discards the
         Route Error; otherwise, it forwards the packet to the expected
         previous hop of the corresponding flow.  If Route Maintenance
         cannot confirm the reachability of the previous hop, the node
         checks if the network interface requires bidirectional links
         for operation.  If it does, the node silently discards the
         Route Error; otherwise, it sends the Error as if it were
         originating it, as described in Section 8.1.1.

      o  On receiving a Route Error of type DEFAULT_FLOW_UNKNOWN that
         this node is the Error Destination Address of, remove the Route
         Error from the packet and mark the default flow between the
         Error Destination Address and the Original IP Destination
         Address as not having been established end-to-end.

Top      Up      ToC       Page 91 
      o  On receiving an Acknowledgement Request option, the receiving
         node removes the Acknowledgement Request option and replies to
         the previous hop with an Acknowledgement option.  If the
         previous hop cannot be determined, the Acknowledgement Request
         option is discarded, and processing continues.

      o  On receiving an Acknowledgement option, the receiving node
         removes the Acknowledgement option and processes it.

      o  On receiving any Acknowledgement option, add the appropriate
         link to the Route Cache, as specified in Section 8.1.4.

      o  On receiving any Source Route option, add appropriate links to
         the Route Cache, as specified in Section 8.1.4.

      o  On receiving a Source Route option, if no DSR Flow State header
         is present, if the flow this packet is being sent along is in
         the Flow Table, or if no Timeout option preceded the Source
         Route option in this DSR Options header, process it as
         specified in Section 8.1.4.  Stop processing this packet unless
         the last address in the Source Route option is an address of
         this node.

      o  On receiving a Source Route option in a packet with a DSR Flow
         State header, if the Flow ID specified in the DSR Flow State
         header is not in the Flow Table, add the flow to the Flow
         Table, setting the Timeout value to a value not greater than
         the Timeout field of the Timeout option in this header.  If no
         Timeout option preceded the Source Route option in this header,
         the flow MUST NOT be added to the Flow Table.

         If the Flow ID is odd and larger than any unexpired, odd Flow
         IDs for this (IP Source Address, IP Destination Address), it is
         set to be default in the Default Flow ID Table.

         Then process the Route option as specified in Section 8.1.4.
         Stop processing this packet unless the last address in the
         Source Route option is an address of this node.

      o  On receiving a Timeout option, check if this packet contains a
         DSR Flow State header.  If this packet does not contain a DSR
         Flow State header, discard the DSR option.  Otherwise, record
         the Timeout value in the option for future reference.  The
         value recorded SHOULD be discarded when the node has finished
         processing this DSR Options header.  If the flow that this
         packet is being sent along is in the Flow Table, it MAY set the
         flow to time out no more than Timeout seconds in the future.

Top      Up      ToC       Page 92 
      o  On receiving a Destination and Flow ID option, if the IP
         Destination Address is not an address of this node, forward the
         packet according to the Flow ID, as described in Section 8.6.4,
         and stop processing this packet.

      o  On receiving a Destination and Flow ID option, if the IP
         Destination Address is an address of this node, set the IP
         Destination Address to the New IP Destination Address specified
         in the option and set the Flow ID to the New Flow Identifier.
         Then remove the Destination and Flow ID option from the packet
         and continue processing.

   -  If the IP Destination Address is an address of this node, remove
      the DSR Options header, if any, pass the packet up the network
      stack, and stop processing.

   -  If there is still a DSR Options header containing no options,
      remove the DSR Options header.

   -  If there is still a DSR Flow State header, forward the packet
      according to the Flow ID, as described in Section 8.6.4.

   -  If there is neither a DSR Options header nor a DSR Flow State
      header, but there is an entry in the Default Flow Table for the
      (IP Source Address, IP Destination Address) pair:

      o  If the IP TTL is not equal to the TTL expected in the Flow
         Table, insert a DSR Flow State header, setting the Hop Count
         equal to the Hop Count of this node, and the Flow ID equal to
         the default Flow ID found in the Default Flow Table, and
         forward this packet according to the Flow ID, as described in
         Section 8.6.4.

      o  Otherwise, follow the steps for forwarding the packet using
         Flow IDs described in Section 8.6.4, but taking the Flow ID to
         be the default Flow ID found in the Default Flow Table.

   -  If there is no DSR Options header and no DSR Flow State header and
      no default flow can be found, the node returns a Route Error of
      type DEFAULT_FLOW_UNKNOWN to the IP Source Address, specifying the
      IP Destination Address as the Original IP Destination in the
      type-specific field.

Top      Up      ToC       Page 93 
8.6.4.  Forwarding a Packet Using Flow IDs

   To forward a packet using Flow IDs, a node MUST follow the following
   sequence of steps:

   -  If the triple (IP Source Address, IP Destination Address, Flow ID)
      is not in the Flow Table, return a Route Error of type
      UNKNOWN_FLOW.

   -  If a network-layer acknowledgement is required for Route
      Maintenance for the next hop, the node MUST include an
      Acknowledgement Request option as specified in Section 8.3.3.  If
      no DSR Options header is in the packet in which the
      Acknowledgement Request option is to be added, it MUST be
      included, as described in Section 8.1.2, except that it MUST be
      added after the DSR Flow State header, if one is present.

   -  Attempt to transmit this packet to the next hop as specified in
      the Flow Table, performing Route Maintenance to detect broken
      routes.

8.6.5.  Promiscuously Receiving a Packet

   This section describes processing only for packets that have MAC
   destinations other than this processing node.  Otherwise, the process
   described in Section 8.6.3 should be followed.

   When a node using DSR flow state promiscuously overhears a packet, it
   SHOULD follow the following steps for processing:

   -  If the packet contains a DSR Flow State header, and if the triple
      (IP Source Address, IP Destination Address, Flow ID) is in the
      Flow Table and the Hop Count is less than the Hop Count in the
      flow's entry, the node MAY retain the packet in the Automatic
      Route Shortening Table.  If it can be determined that this Flow ID
      has been recently used, the node SHOULD retain the packet in the
      Automatic Route Shortening Table.

   -  If the packet contains neither a DSR Flow State header nor a
      Source Route option and a Default Flow ID can be found in the
      Default Flow Table for the (IP Source Address, IP Destination
      Address), and if the IP TTL is greater than the TTL in the Flow
      Table for the default flow, the node MAY retain the packet in the
      Automatic Route Shortening Table.  If it can be determined that
      this Flow ID has been used recently, the node SHOULD retain the
      packet in the Automatic Route Shortening Table.

Top      Up      ToC       Page 94 
8.6.6.  Operation Where the Layer below DSR Decreases the IP TTL
        Non-uniformly

   Some nodes may use an IP tunnel as a DSR hop.  If different packets
   sent along this IP tunnel can take different routes, the reduction in
   IP TTL across this link may be different for different packets.  This
   prevents the Automatic Route Shortening and Loop Detection
   functionality from working properly when used in conjunction with
   default routes.

   Nodes forwarding packets without a Source Route option onto a link
   with unpredictable TTL changes MUST ensure that a DSR Flow State
   header is present, indicating the correct Hop Count and Flow ID.

8.6.7.  Salvage Interactions with DSR

   Nodes salvaging packets MUST remove the DSR Flow State header, if
   present.

   Anytime this document refers to the Salvage field in the Source Route
   option, packets without a Source Route option are considered to have
   the value zero in the Salvage field.

Top      Up      ToC       Page 95 
9.  Protocol Constants and Configuration Variables

   Any DSR implementation MUST support the following configuration
   variables and MUST support a mechanism enabling the value of these
   variables to be modified by system management.  The specific variable
   names are used for demonstration purposes only, and an implementation
   is not required to use these names for the configuration variables,
   so long as the external behavior of the implementation is consistent
   with that described in this document.

   For each configuration variable below, the default value is specified
   to simplify configuration.  In particular, the default values given
   below are chosen for a DSR network running over 2 Mbps IEEE 802.11
   network interfaces using the Distributed Coordination Function (DCF)
   MAC protocol with RTS and CTS [IEEE80211, BROCH98].

      DiscoveryHopLimit                  255   hops

      BroadcastJitter                     10   milliseconds

      RouteCacheTimeout                  300   seconds

      SendBufferTimeout                   30   seconds

      RequestTableSize                    64   nodes
      RequestTableIds                     16   identifiers
      MaxRequestRexmt                     16   retransmissions
      MaxRequestPeriod                    10   seconds
      RequestPeriod                      500   milliseconds
      NonpropRequestTimeout               30   milliseconds

      RexmtBufferSize                     50   packets

      MaintHoldoffTime                   250   milliseconds

      MaxMaintRexmt                        2   retransmissions

      TryPassiveAcks                       1   attempt
      PassiveAckTimeout                  100   milliseconds

      GratReplyHoldoff                     1   second

   In addition, the following protocol constant MUST be supported by any
   implementation of the DSR protocol:

      MAX_SALVAGE_COUNT                   15   salvages

Top      Up      ToC       Page 96 
10.  IANA Considerations

   This document specifies the DSR Options header and DSR Flow State
   header, for which the IP protocol number 48 has been assigned.  A
   single IP protocol number can be used for both header types, since
   they can be distinguished by the Flow State Header (F) bit in each
   header.

   In addition, this document proposes use of the value "No Next Header"
   (originally defined for use in IPv6 [RFC2460]) within an IPv4 packet,
   to indicate that no further header follows a DSR Options header.

   Finally, this document introduces a number of DSR options for use in
   the DSR Options header, and additional new DSR options may be defined
   in the future.  Each of these options requires a unique Option Type
   value, the most significant 3 bits (that is, Option Type & 0xE0)
   encoded as defined in Section 6.1.  It is necessary only that each
   Option Type value be unique, not that they be unique in the remaining
   5 bits of the value after these 3 most significant bits.

   Two registries (DSR Protocol Options and DSR Protocol Route Error
   Types) have been created and contain the initial registrations.
   Assignment of new values for DSR options will be by Expert Review
   [RFC2434], with the authors of this document serving as the
   Designated Experts.

11.  Security Considerations

   This document does not specifically address security concerns.  This
   document does assume that all nodes participating in the DSR protocol
   do so in good faith and without malicious intent to corrupt the
   routing ability of the network.

   Depending on the threat model, a number of different mechanisms can
   be used to secure DSR.  For example, in an environment where node
   compromise is unrealistic and where all the nodes participating in
   the DSR protocol share a common goal that motivates their
   participation in the protocol, the communications between the nodes
   can be encrypted at the physical channel or link layer to prevent
   attack by outsiders.  Cryptographic approaches, such as that provided
   by Ariadne [HU02] or Secure Routing Protocol (SRP)
   [PAPADIMITRATOS02], can resist stronger attacks.

Top      Up      ToC       Page 97 
Appendix A.  Link-MaxLife Cache Description

   As guidance to implementers of DSR, the description below outlines
   the operation of a possible implementation of a Route Cache for DSR
   that has been shown to outperform other caches studied in detailed
   simulations.  Use of this design for the Route Cache is recommended
   in implementations of DSR.

   This cache, called "Link-MaxLife" [HU00], is a link cache, in that
   each individual link (hop) in the routes returned in Route Reply
   packets (or otherwise learned from the header of overhead packets) is
   added to a unified graph data structure of this node's current view
   of the network topology, as described in Section 4.1.  To search for
   a route in this cache to some destination node, the sending node uses
   a graph search algorithm, such as the well-known Dijkstra's
   shortest-path algorithm, to find the current best path through the
   graph to the destination node.

   The Link-MaxLife form of link cache is adaptive in that each link in
   the cache has a timeout that is determined dynamically by the caching
   node according to its observed past behavior of the two nodes at the
   ends of the link; in addition, when selecting a route for a packet
   being sent to some destination, among cached routes of equal length
   (number of hops) to that destination, Link-MaxLife selects the route
   with the longest expected lifetime (highest minimum timeout of any
   link in the route).

   Specifically, in Link-MaxLife, a link's timeout in the Route Cache is
   chosen according to a "Stability Table" maintained by the caching
   node.  Each entry in a node's Stability Table records the address of
   another node and a factor representing the perceived "stability" of
   this node.  The stability of each other node in a node's Stability
   Table is initialized to InitStability.  When a link from the Route
   Cache is used in routing a packet originated or salvaged by that
   node, the stability metric for each of the two endpoint nodes of that
   link is incremented by the amount of time since that link was last
   used, multiplied by StabilityIncrFactor (StabilityIncrFactor >= 1);
   when a link is observed to break and the link is thus removed from
   the Route Cache, the stability metric for each of the two endpoint
   nodes of that link is multiplied by StabilityDecrFactor
   (StabilityDecrFactor < 1).

   When a node adds a new link to its Route Cache, the node assigns a
   lifetime for that link in the Cache equal to the stability of the
   less "stable" of the two endpoint nodes for the link, except that a
   link is not allowed to be given a lifetime less than MinLifetime.
   When a link is used in a route chosen for a packet originated or
   salvaged by this node, the link's lifetime is set to be at least

Top      Up      ToC       Page 98 
   UseExtends into the future; if the lifetime of that link in the Route
   Cache is already further into the future, the lifetime remains
   unchanged.

   When a node using Link-MaxLife selects a route from its Route Cache
   for a packet being originated or salvaged by this node, it selects
   the shortest-length route that has the longest expected lifetime
   (highest minimum timeout of any link in the route), as opposed to
   simply selecting an arbitrary route of shortest length.

   The following configuration variables are used in the description of
   Link-MaxLife above.  The specific variable names are used for
   demonstration purposes only, and an implementation is not required to
   use these names for these configuration variables.  For each
   configuration variable below, the default value is specified to
   simplify configuration.  In particular, the default values given
   below are chosen for a DSR network where nodes move at relative
   velocities between 12 and 25 seconds per wireless transmission
   radius.

      InitStability                       25   seconds
      StabilityIncrFactor                  4
      StabilityDecrFactor                0.5

      MinLifetime                          1   second
      UseExtends                         120   seconds

Top      Up      ToC       Page 99 
Appendix B.  Location of DSR in the ISO Network Reference Model

   When designing DSR, we had to determine at what layer within the
   protocol hierarchy to implement ad hoc network routing.  We
   considered two different options: routing at the link layer (ISO
   layer 2) and routing at the network layer (ISO layer 3).  Originally,
   we opted to route at the link layer for several reasons:

   -  Pragmatically, running the DSR protocol at the link layer
      maximizes the number of mobile nodes that can participate in ad
      hoc networks.  For example, the protocol can route equally well
      between IPv4 [RFC791], IPv6 [RFC2460], and IPX [TURNER90] nodes.

   -  Historically [JOHNSON94, JOHNSON96a], DSR grew from our
      contemplation of a multi-hop propagating version of the Internet's
      Address Resolution Protocol (ARP) [RFC826], as well as from the
      routing mechanism used in IEEE 802 source routing bridges
      [PERLMAN92].  These are layer 2 protocols.

   -  Technically, we designed DSR to be simple enough that it could be
      implemented directly in the firmware inside wireless network
      interface cards [JOHNSON94, JOHNSON96a], well below the layer 3
      software within a mobile node.  We see great potential in this for
      DSR running inside a cloud of mobile nodes around a fixed base
      station, where DSR would act to transparently extend the coverage
      range to these nodes.  Mobile nodes that would otherwise be unable
      to communicate with the base station due to factors such as
      distance, fading, or local interference sources could then reach
      the base station through their peers.

   Ultimately, however, we decided to specify and to implement
   [MALTZ99b] DSR as a layer 3 protocol, since this is the only layer at
   which we could realistically support nodes with multiple network
   interfaces of different types forming an ad hoc network.

Top      Up      ToC       Page 100 
Appendix C.  Implementation and Evaluation Status

   The initial design of the DSR protocol, including DSR's basic Route
   Discovery and Route Maintenance mechanisms, was first published in
   December 1994 [JOHNSON94]; significant additional design details and
   initial simulation results were published in early 1996 [JOHNSON96a].

   The DSR protocol has been extensively studied since then through
   additional detailed simulations.  In particular, we have implemented
   DSR in the ns-2 network simulator [NS-2, BROCH98] and performed
   extensive simulations of DSR using ns-2 (e.g., [BROCH98, MALTZ99a]).
   We have also conducted evaluations of the different caching
   strategies in this document [HU00].

   We have also implemented the DSR protocol under the FreeBSD 2.2.7
   operating system running on Intel x86 platforms.  FreeBSD [FREEBSD]
   is based on a variety of free software, including 4.4 BSD Lite, from
   the University of California, Berkeley.  For the environments in
   which we used it, this implementation is functionally equivalent to
   the version of the DSR protocol specified in this document.

   During the 7 months from August 1998 to February 1999, we designed
   and implemented a full-scale physical testbed to enable the
   evaluation of ad hoc network performance in the field, in an actively
   mobile ad hoc network under realistic communication workloads.  The
   last week of February and the first week of March of 1999 included
   demonstrations of this testbed to a number of our sponsors and
   partners, including Lucent Technologies, Bell Atlantic, and the
   Defense Advanced Research Projects Agency (DARPA).  A complete
   description of the testbed is available [MALTZ99b, MALTZ00, MALTZ01].

   We have since ported this implementation of DSR to FreeBSD 3.3, and
   we have also added a preliminary version of Quality of Service (QoS)
   support for DSR.  A demonstration of this modified version of DSR was
   presented in July 2000.  These QoS features are not included in this
   document and will be added later in a separate document on top of the
   base protocol specified here.

   DSR has also been implemented under Linux by Alex Song at the
   University of Queensland, Australia [SONG01].  This implementation
   supports the Intel x86 PC platform and the Compaq iPAQ.

   The Network and Telecommunications Research Group at Trinity College,
   Dublin, have implemented a version of DSR on Windows CE.

   Microsoft Research has implemented a version of DSR on Windows XP and
   has used it in testbeds of over 15 nodes.  Several machines use this
   implementation as their primary means of accessing the Internet.

Top      Up      ToC       Page 101 
   Several other independent groups have also used DSR as a platform for
   their own research, or as a basis of comparison between ad hoc
   network routing protocols.

   A preliminary version of the optional DSR flow state extension was
   implemented in FreeBSD 3.3.  A demonstration of this modified version
   of DSR was presented in July 2000.  The DSR flow state extension has
   also been extensively evaluated using simulation [HU01].

Acknowledgements

   The protocol described in this document has been designed and
   developed within the Monarch Project, a long-term research project at
   Rice University (previously at Carnegie Mellon University) that is
   developing adaptive networking protocols and protocol interfaces to
   allow truly seamless wireless and mobile node networking [JOHNSON96b,
   MONARCH].

   The authors would like to acknowledge the substantial contributions
   of Josh Broch in helping to design, simulate, and implement the DSR
   protocol.  We thank him for his contributions to earlier versions of
   this document.

   We would also like to acknowledge the assistance of Robert V. Barron
   at Carnegie Mellon University.  Bob ported our DSR implementation
   from FreeBSD 2.2.7 into FreeBSD 3.3.

   Many valuable suggestions came from participants in the IETF process.
   We would particularly like to acknowledge Fred Baker, who provided
   extensive feedback on a previous version of this document, as well as
   the working group chairs, for their suggestions of previous versions
   of the document.

Top      Up      ToC       Page 102 
Normative References

   [RFC791]       Postel, J., "Internet Protocol", STD 5, RFC 791,
                  September 1981.

   [RFC792]       Postel, J., "Internet Control Message Protocol", STD
                  5, RFC 792, September 1981.

   [RFC826]       Plummer, David C., "Ethernet Address Resolution
                  Protocol: Or converting network protocol addresses to
                  48.bit Ethernet address for transmission on Ethernet
                  hardware", STD 37, RFC 826, November 1982.

   [RFC1122]      Braden, R., "Requirements for Internet Hosts -
                  Communication Layers", STD 3, RFC 1122, October 1989.

   [RFC1700]      Reynolds, J. and J. Postel, "Assigned Numbers", STD 2,
                  RFC 1700, October 1994.  See also
                  http://www.iana.org/numbers.html.

   [RFC2003]      Perkins, C., "IP Encapsulation within IP", RFC 2003,
                  October 1996.  RFC 2003, October 1996.

   [RFC2119]      Bradner, S., "Key words for use in RFCs to Indicate
                  Requirement Levels", BCP 14, RFC 2119, March 1997.

   [RFC2434]      Narten, T. and H. Alvestrand, "Guidelines for Writing
                  an IANA Considerations Section in RFCs", BCP 26, RFC
                  2434, October 1998.

Informative References

   [BANTZ94]      David F. Bantz and Frederic J. Bauchot.  Wireless LAN
                  Design Alternatives.  IEEE Network, 8(2):43-53,
                  March/April 1994.

   [BHARGHAVAN94] Vaduvur Bharghavan, Alan Demers, Scott Shenker, and
                  Lixia Zhang.  MACAW: A Media Access Protocol for
                  Wireless LAN's.  In Proceedings of the ACM SIGCOMM '94
                  Conference, pages 212-225. ACM, August 1994.

   [BROCH98]      Josh Broch, David A. Maltz, David B. Johnson, Yih-Chun
                  Hu, and Jorjeta Jetcheva.  A Performance Comparison of
                  Multi-Hop Wireless Ad Hoc Network Routing Protocols.
                  In Proceedings of the Fourth Annual ACM/IEEE
                  International Conference on Mobile Computing and
                  Networking, pages 85-97.  ACM/IEEE, October 1998.

Top      Up      ToC       Page 103 
   [CLARK88]      David D. Clark.  The Design Philosophy of the DARPA
                  Internet Protocols.  In Proceedings of the ACM SIGCOMM
                  '88 Conference, pages 106-114. ACM, August 1988.

   [FREEBSD]      The FreeBSD Project.  Project web page available at
                  http://www.freebsd.org/.

   [HU00]         Yih-Chun Hu and David B. Johnson.  Caching Strategies
                  in On-Demand Routing Protocols for Wireless Ad Hoc
                  Networks.  In Proceedings of the Sixth Annual ACM
                  International Conference on Mobile Computing and
                  Networking. ACM, August 2000.

   [HU01]         Yih-Chun Hu and David B. Johnson.  Implicit Source
                  Routing in On-Demand Ad Hoc Network Routing.  In
                  Proceedings of the Second Symposium on Mobile Ad Hoc
                  Networking and Computing (MobiHoc 2001), pages 1-10,
                  October 2001.

   [HU02]         Yih-Chun Hu, Adrian Perrig, and David B. Johnson.
                  Ariadne:  A Secure On-Demand Routing Protocol for Ad
                  Hoc Networks.  In Proceedings of the Eighth Annual
                  International Conference on Mobile Computing and
                  Networking (MobiCom 2002), pages 12-23, September
                  2002.

   [IEEE80211]    IEEE Computer Society LAN MAN Standards Committee.
                  Wireless LAN Medium Access Control (MAC) and Physical
                  Layer (PHY) Specifications, IEEE Std 802.11-1997.  The
                  Institute of Electrical and Electronics Engineers, New
                  York, New York, 1997.

   [JOHANSSON99]  Per Johansson, Tony Larsson, Nicklas Hedman, Bartosz
                  Mielczarek, and Mikael Degermark.  Scenario-based
                  Performance Analysis of Routing Protocols for Mobile
                  Ad-hoc Networks.  In Proceedings of the Fifth Annual
                  ACM/IEEE International Conference on Mobile Computing
                  and Networking, pages 195-206. ACM/IEEE, August 1999.

   [JOHNSON94]    David B. Johnson.  Routing in Ad Hoc Networks of
                  Mobile Hosts.  In Proceedings of the IEEE Workshop on
                  Mobile Computing Systems and Applications, pages 158-
                  163. IEEE Computer Society, December 1994.

Top      Up      ToC       Page 104 
   [JOHNSON96a]   David B. Johnson and David A. Maltz.  Dynamic Source
                  Routing in Ad Hoc Wireless Networks.  In Mobile
                  Computing, edited by Tomasz Imielinski and Hank Korth,
                  chapter 5, pages 153-181. Kluwer Academic Publishers,
                  1996.

   [JOHNSON96b]   David B. Johnson and David A. Maltz.  Protocols for
                  Adaptive Wireless and Mobile Networking.  IEEE
                  Personal Communications, 3(1):34-42, February 1996.

   [JUBIN87]      John Jubin and Janet D. Tornow.  The DARPA Packet
                  Radio Network Protocols.  Proceedings of the IEEE,
                  75(1):21-32, January 1987.

   [KARN90]       Phil Karn.  MACA---A New Channel Access Method for
                  Packet Radio.  In ARRL/CRRL Amateur Radio 9th Computer
                  Networking Conference, pages 134-140. American Radio
                  Relay League, September 1990.

   [LAUER95]      Gregory S. Lauer.  Packet-Radio Routing.  In Routing
                  in Communications Networks, edited by Martha E.
                  Steenstrup, chapter 11, pages 351-396. Prentice-Hall,
                  Englewood Cliffs, New Jersey, 1995.

   [MALTZ99a]     David A. Maltz, Josh Broch, Jorjeta Jetcheva, and
                  David B. Johnson.  The Effects of On-Demand Behavior
                  in Routing Protocols for Multi-Hop Wireless Ad Hoc
                  Networks.  IEEE Journal on Selected Areas of
                  Communications, 17(8):1439-1453, August 1999.

   [MALTZ99b]     David A. Maltz, Josh Broch, and David B. Johnson.
                  Experiences Designing and Building a Multi-Hop
                  Wireless Ad Hoc Network Testbed.  Technical Report
                  CMU-CS-99-116, School of Computer Science, Carnegie
                  Mellon University, Pittsburgh, Pennsylvania, March
                  1999.

   [MALTZ00]      David A. Maltz, Josh Broch, and David B. Johnson.
                  Quantitative Lessons From a Full-Scale Multi-Hop
                  Wireless Ad Hoc Network Testbed.  In Proceedings of
                  the IEEE Wireless Communications and Networking
                  Conference. IEEE, September 2000.

   [MALTZ01]      David A. Maltz, Josh Broch, and David B. Johnson.
                  Lessons From a Full-Scale MultiHop Wireless Ad Hoc
                  Network Testbed.  IEEE Personal Communications,
                  8(1):8-15, February 2001.

Top      Up      ToC       Page 105 
   [MONARCH]      Rice University Monarch Project.  Monarch Project Home
                  Page.  Available at http://www.monarch.cs.rice.edu/.

   [NS-2]         The Network Simulator -- ns-2.  Project web page
                  available at http://www.isi.edu/nsnam/ns/.

   [PAPADIMITRATOS02]
                  Panagiotis Papadimitratos and Zygmunt J. Haas.  Secure
                  Routing for Mobile Ad Hoc Networks.  In SCS
                  Communication Networks and Distributed Systems
                  Modeling and Simulation Conference (CNDS 2002),
                  January 2002.

   [PERLMAN92]    Radia Perlman.  Interconnections:  Bridges and
                  Routers.  Addison-Wesley, Reading, Massachusetts,
                  1992.

   [RFC793]       Postel, J., "Transmission Control Protocol", STD 7,
                  RFC 793, September 1981.

   [RFC2131]      Droms, R., "Dynamic Host Configuration Protocol", RFC
                  2131, March 1997.

   [RFC2460]      Deering, S. and R. Hinden, "Internet Protocol, Version
                  6 (IPv6) Specification", RFC 2460, December 1998.

   [SONG01]       Alex Song.  picoNet II: A Wireless Ad Hoc Network for
                  Mobile Handheld Devices.  Submitted for the degree of
                  Bachelor of Engineering (Honours) in the division of
                  Electrical Engineering, Department of Information
                  Technology and Electrical Engineering, University of
                  Queensland, Australia, October 2001.  Available at
                  http://piconet.sourceforge.net/thesis/index.html.

   [TURNER90]     Paul Turner.  NetWare Communications Processes.
                  NetWare Application Notes, Novell Research, pages 25-
                  91, September 1990.

   [WRIGHT95]     Gary R. Wright and W. Richard Stevens.  TCP/IP
                  Illustrated, Volume 2:  The Implementation.  Addison-
                  Wesley, Reading, Massachusetts, 1995.

Top      Up      ToC       Page 106 
Authors' Addresses

   David B. Johnson
   Rice University
   Computer Science Department, MS 132
   6100 Main Street
   Houston, TX 77005-1892
   USA

   Phone: +1 713 348-3063
   Fax:   +1 713 348-5930
   EMail: dbj@cs.rice.edu


   David A. Maltz
   Microsoft Research
   One Microsoft Way
   Redmond, WA 98052
   USA

   Phone: +1 425 706-7785
   Fax:   +1 425 936-7329
   EMail: dmaltz@microsoft.com


   Yih-Chun Hu
   University of Illinois at Urbana-Champaign
   Coordinated Science Lab
   1308 West Main St, MC 228
   Urbana, IL 61801
   USA

   Phone: +1 217 333-4220
   EMail: yihchun@uiuc.edu

Top      Up      ToC       Page 107 
Full Copyright Statement

   Copyright (C) The IETF Trust (2007).

   This document is subject to the rights, licenses and restrictions
   contained in BCP 78, and except as set forth therein, the authors
   retain all their rights.

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Intellectual Property

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at
   ietf-ipr@ietf.org.

Acknowledgement

   Funding for the RFC Editor function is currently provided by the
   Internet Society.