Tech-invite3GPPspaceIETF RFCsSIP
93929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 4728

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

Pages: 107
Experimental
Errata
Part 4 of 4 – Pages 84 to 107
First   Prev   None

Top   ToC   RFC4728 - Page 84   prevText

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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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   ToC   RFC4728 - 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.