RFC 4728
The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4
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.
- 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.
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.
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.
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:
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.
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.
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.
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.
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.
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.
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
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.
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
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
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.
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.
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.
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.
[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.
[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.
[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.
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
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.