draft-ietf-manet-dsr-06.txt   draft-ietf-manet-dsr-07.txt 
IETF MANET Working Group David B. Johnson, Rice University IETF MANET Working Group David B. Johnson, Rice University
INTERNET-DRAFT David A. Maltz, AON Networks INTERNET-DRAFT David A. Maltz, AON Networks
21 November 2001 Yih-Chun Hu, Rice University 21 February 2002 Yih-Chun Hu, Rice University
Jorjeta G. Jetcheva, Carnegie Mellon University Jorjeta G. Jetcheva, Carnegie Mellon University
The Dynamic Source Routing Protocol The Dynamic Source Routing Protocol
for Mobile Ad Hoc Networks (DSR) for Mobile Ad Hoc Networks (DSR)
<draft-ietf-manet-dsr-06.txt> <draft-ietf-manet-dsr-07.txt>
Status of This Memo Status of This Memo
This document is an Internet-Draft and is subject to all provisions This document is an Internet-Draft and is subject to all provisions
of Section 10 of RFC 2026. of Section 10 of RFC 2026.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note Task Force (IETF), its areas, and its working groups. Note
that other groups may also distribute working documents as that other groups may also distribute working documents as
Internet-Drafts. Internet-Drafts.
skipping to change at page 1, line 60 skipping to change at page 1, line 60
to be trivially loop-free, avoids the need for up-to-date routing to be trivially loop-free, avoids the need for up-to-date routing
information in the intermediate nodes through which packets are information in the intermediate nodes through which packets are
forwarded, and allows nodes forwarding or overhearing packets to forwarded, and allows nodes forwarding or overhearing packets to
cache the routing information in them for their own future use. All cache the routing information in them for their own future use. All
aspects of the protocol operate entirely on-demand, allowing the aspects of the protocol operate entirely on-demand, allowing the
routing packet overhead of DSR to scale automatically to only that routing packet overhead of DSR to scale automatically to only that
needed to react to changes in the routes currently in use. This needed to react to changes in the routes currently in use. This
document specifies the operation of the DSR protocol for routing document specifies the operation of the DSR protocol for routing
unicast IPv4 packets in multi-hop wireless ad hoc networks. unicast IPv4 packets in multi-hop wireless ad hoc networks.
The DSR protocol is designed for mobile ad hoc networks with up to
around two hundred nodes, and is designed to cope with relatively
high rates of mobility.
Contents Contents
Status of This Memo i Status of This Memo i
Abstract ii Abstract ii
1. Introduction 1 1. Introduction 1
2. Assumptions 3 2. Assumptions 3
skipping to change at page 1, line 91 skipping to change at page 1, line 95
3.4.2. Queued Packets Destined over a Broken Link . . . 14 3.4.2. Queued Packets Destined over a Broken Link . . . 14
3.4.3. Automatic Route Shortening . . . . . . . . . . . 15 3.4.3. Automatic Route Shortening . . . . . . . . . . . 15
3.4.4. Increased Spreading of Route Error Messages . . . 16 3.4.4. Increased Spreading of Route Error Messages . . . 16
4. Conceptual Data Structures 17 4. Conceptual Data Structures 17
4.1. Route Cache . . . . . . . . . . . . . . . . . . . . . . . 17 4.1. Route Cache . . . . . . . . . . . . . . . . . . . . . . . 17
4.2. Send Buffer . . . . . . . . . . . . . . . . . . . . . . . 20 4.2. Send Buffer . . . . . . . . . . . . . . . . . . . . . . . 20
4.3. Route Request Table . . . . . . . . . . . . . . . . . . . 21 4.3. Route Request Table . . . . . . . . . . . . . . . . . . . 21
4.4. Gratuitous Route Reply Table . . . . . . . . . . . . . . 22 4.4. Gratuitous Route Reply Table . . . . . . . . . . . . . . 22
4.5. Network Interface Queue and Retransmission Buffer . . . . 23 4.5. Network Interface Queue and Maintenance Buffer . . . . . 23
4.6. Blacklist . . . . . . . . . . . . . . . . . . . . . . . . 24
5. DSR Header Format 25 5. DSR Header Format 25
5.1. Fixed Portion of DSR Header . . . . . . . . . . . . . . . 26 5.1. Fixed Portion of DSR Header . . . . . . . . . . . . . . . 26
5.2. Route Request Option . . . . . . . . . . . . . . . . . . 28 5.2. Route Request Option . . . . . . . . . . . . . . . . . . 28
5.3. Route Reply Option . . . . . . . . . . . . . . . . . . . 30 5.3. Route Reply Option . . . . . . . . . . . . . . . . . . . 30
5.4. Route Error Option . . . . . . . . . . . . . . . . . . . 32 5.4. Route Error Option . . . . . . . . . . . . . . . . . . . 32
5.5. Acknowledgment Request Option . . . . . . . . . . . . . . 35 5.5. Acknowledgment Request Option . . . . . . . . . . . . . . 35
5.6. Acknowledgment Option . . . . . . . . . . . . . . . . . . 36 5.6. Acknowledgment Option . . . . . . . . . . . . . . . . . . 36
5.7. DSR Source Route Option . . . . . . . . . . . . . . . . . 37 5.7. DSR Source Route Option . . . . . . . . . . . . . . . . . 37
skipping to change at page 1, line 115 skipping to change at page 1, line 120
6.1. General Packet Processing . . . . . . . . . . . . . . . . 41 6.1. General Packet Processing . . . . . . . . . . . . . . . . 41
6.1.1. Originating a Packet . . . . . . . . . . . . . . 41 6.1.1. Originating a Packet . . . . . . . . . . . . . . 41
6.1.2. Adding a DSR Header to a Packet . . . . . . . . . 41 6.1.2. Adding a DSR Header to a Packet . . . . . . . . . 41
6.1.3. Adding a DSR Source Route Option to a Packet . . 42 6.1.3. Adding a DSR Source Route Option to a Packet . . 42
6.1.4. Processing a Received Packet . . . . . . . . . . 43 6.1.4. Processing a Received Packet . . . . . . . . . . 43
6.1.5. Processing a Received DSR Source Route Option . . 45 6.1.5. Processing a Received DSR Source Route Option . . 45
6.2. Route Discovery Processing . . . . . . . . . . . . . . . 48 6.2. Route Discovery Processing . . . . . . . . . . . . . . . 48
6.2.1. Originating a Route Request . . . . . . . . . . . 48 6.2.1. Originating a Route Request . . . . . . . . . . . 48
6.2.2. Processing a Received Route Request Option . . . 50 6.2.2. Processing a Received Route Request Option . . . 50
6.2.3. Generating a Route Reply using the Route Cache . 51 6.2.3. Generating a Route Reply using the Route Cache . 52
6.2.4. Originating a Route Reply . . . . . . . . . . . . 54 6.2.4. Originating a Route Reply . . . . . . . . . . . . 54
6.2.5. Processing a Received Route Reply Option . . . . 55 6.2.5. Processing a Received Route Reply Option . . . . 56
6.3. Route Maintenance Processing . . . . . . . . . . . . . . 57 6.3. Route Maintenance Processing . . . . . . . . . . . . . . 57
6.3.1. Using Link-Layer Acknowledgments . . . . . . . . 57 6.3.1. Using Link-Layer Acknowledgments . . . . . . . . 57
6.3.2. Using Passive Acknowledgments . . . . . . . . . . 58 6.3.2. Using Passive Acknowledgments . . . . . . . . . . 58
6.3.3. Using Network-Layer Acknowledgments . . . . . . . 59 6.3.3. Using Network-Layer Acknowledgments . . . . . . . 59
6.3.4. Originating a Route Error . . . . . . . . . . . . 62 6.3.4. Originating a Route Error . . . . . . . . . . . . 62
6.3.5. Processing a Received Route Error Option . . . . 63 6.3.5. Processing a Received Route Error Option . . . . 63
6.3.6. Salvaging a Packet . . . . . . . . . . . . . . . 64 6.3.6. Salvaging a Packet . . . . . . . . . . . . . . . 64
7. Protocol Constants and Configuration Variables 66 7. Multiple Interface Support 66
8. IANA Considerations 67 8. Fragmentation and Reassembly 67
9. Security Considerations 68 9. Protocol Constants and Configuration Variables 68
Appendix A. Link-MaxLife Cache Description 69 10. IANA Considerations 69
Appendix B. Location of DSR in the ISO Network Reference Model 71 11. Security Considerations 70
Appendix C. Implementation and Evaluation Status 72 Appendix A. Link-MaxLife Cache Description 71
Changes from Previous Version of the Draft 73 Appendix B. Location of DSR in the ISO Network Reference Model 73
Appendix C. Implementation and Evaluation Status 74
Changes from Previous Version of the Draft 75
Acknowledgements 76 Acknowledgements 76
References 77 References 77
Chair's Address 80 Chair's Address 80
Authors' Addresses 81 Authors' Addresses 81
1. Introduction 1. Introduction
skipping to change at page 2, line 35 skipping to change at page 2, line 35
In response to a single Route Discovery (as well as through routing In response to a single Route Discovery (as well as through routing
information from other packets overheard), a node may learn and cache information from other packets overheard), a node may learn and cache
multiple routes to any destination. This allows the reaction to multiple routes to any destination. This allows the reaction to
routing changes to be much more rapid, since a node with multiple routing changes to be much more rapid, since a node with multiple
routes to a destination can try another cached route if the one it routes to a destination can try another cached route if the one it
has been using should fail. This caching of multiple routes also has been using should fail. This caching of multiple routes also
avoids the overhead of needing to perform a new Route Discovery each avoids the overhead of needing to perform a new Route Discovery each
time a route in use breaks. time a route in use breaks.
The operation of both Route Discovery and Route Maintenance in DSR The operation of both Route Discovery and Route Maintenance in DSR
are designed to allow uni-directional links and asymmetric routes are designed to allow unidirectional links and asymmetric routes
to be easily supported. In particular, as noted in Section 2, in to be easily supported. In particular, as noted in Section 2, in
wireless networks, it is possible that a link between two nodes may wireless networks, it is possible that a link between two nodes may
not work equally well in both directions, due to differing antenna not work equally well in both directions, due to differing antenna
or propagation patterns or sources of interference. DSR allows such or propagation patterns or sources of interference. DSR allows such
uni-directional links to be used when necessary, improving overall unidirectional links to be used when necessary, improving overall
performance and network connectivity in the system. performance and network connectivity in the system.
This document specifies the operation of the DSR protocol for This document specifies the operation of the DSR protocol for
routing unicast IPv4 packets in multi-hop wireless ad hoc networks. routing unicast IPv4 packets in multi-hop wireless ad hoc networks.
Advanced, optional features, such as Quality of Service (QoS) support Advanced, optional features, such as Quality of Service (QoS) support
and efficient multicast routing, and operation of DSR with IPv6 [6], and efficient multicast routing, and operation of DSR with IPv6 [6],
are covered in other documents. The specification of DSR in this are covered in other documents. The specification of DSR in this
document provides a compatible base on which such features can be document provides a compatible base on which such features can be
added, either independently or by integration with the DSR operation added, either independently or by integration with the DSR operation
specified here. specified here.
skipping to change at page 4, line 6 skipping to change at page 4, line 6
easily be used without the optimizations that depend on promiscuous easily be used without the optimizations that depend on promiscuous
receive mode, or can be programmed to only periodically switch the receive mode, or can be programmed to only periodically switch the
interface into promiscuous mode. Use of promiscuous receive mode is interface into promiscuous mode. Use of promiscuous receive mode is
entirely optional. entirely optional.
Wireless communication ability between any pair of nodes may at Wireless communication ability between any pair of nodes may at
times not work equally well in both directions, due for example to times not work equally well in both directions, due for example to
differing antenna or propagation patterns or sources of interference differing antenna or propagation patterns or sources of interference
around the two nodes [1, 18]. That is, wireless communications around the two nodes [1, 18]. That is, wireless communications
between each pair of nodes will in many cases be able to operate between each pair of nodes will in many cases be able to operate
bi-directionally, but at times the wireless link between two nodes bidirectionally, but at times the wireless link between two nodes
may be only uni-directional, allowing one node to successfully send may be only unidirectional, allowing one node to successfully send
packets to the other while no communication is possible in the packets to the other while no communication is possible in the
reverse direction. Although many routing protocols operate correctly reverse direction. Although many routing protocols operate correctly
only over bi-directional links, DSR can successfully discover and only over bidirectional links, DSR can successfully discover and
forward packets over paths that contain uni-directional links. forward packets over paths that contain unidirectional links. Some
Some MAC protocols, however, such as MACA [17], MACAW [2], or IEEE MAC protocols, however, such as MACA [17], MACAW [2], or IEEE
802.11 [11], limit unicast data packet transmission to bi-directional 802.11 [11], limit unicast data packet transmission to bidirectional
links, due to the required bi-directional exchange of RTS and CTS links, due to the required bidirectional exchange of RTS and CTS
packets in these protocols and due to the link-layer acknowledgement packets in these protocols and due to the link-layer acknowledgment
feature in IEEE 802.11; when used on top of MAC protocols such as feature in IEEE 802.11; when used on top of MAC protocols such as
these, DSR can take advantage of additional optimizations, such as these, DSR can take advantage of additional optimizations, such as
the ability to reverse a source route to obtain a route back to the the ability to reverse a source route to obtain a route back to the
origin of the original route. origin of the original route.
The IP address used by a node using the DSR protocol MAY be assigned The IP address used by a node using the DSR protocol MAY be assigned
by any mechanism (e.g., static assignment or use of DHCP for dynamic by any mechanism (e.g., static assignment or use of DHCP for dynamic
assignment [7]), although the method of such assignment is outside assignment [7]), although the method of such assignment is outside
the scope of this specification. the scope of this specification.
skipping to change at page 6, line 28 skipping to change at page 6, line 28
containing the Route Reply. Otherwise, E SHOULD perform its own containing the Route Reply. Otherwise, E SHOULD perform its own
Route Discovery for target node A, but to avoid possible infinite Route Discovery for target node A, but to avoid possible infinite
recursion of Route Discoveries, it MUST piggyback this Route Reply recursion of Route Discoveries, it MUST piggyback this Route Reply
on the packet containing its own Route Request for A. It is also on the packet containing its own Route Request for A. It is also
possible to piggyback other small data packets, such as a TCP SYN possible to piggyback other small data packets, such as a TCP SYN
packet [28], on a Route Request using this same mechanism. packet [28], on a Route Request using this same mechanism.
Node E could instead simply reverse the sequence of hops in the route Node E could instead simply reverse the sequence of hops in the route
record that it is trying to send in the Route Reply, and use this as record that it is trying to send in the Route Reply, and use this as
the source route on the packet carrying the Route Reply itself. For the source route on the packet carrying the Route Reply itself. For
MAC protocols such as IEEE 802.11 that require a bi-directional frame MAC protocols such as IEEE 802.11 that require a bidirectional frame
exchange as part of the MAC protocol [11], the discovered source exchange as part of the MAC protocol [11], the discovered source
route MUST be reversed in this way to return the Route Reply since it route MUST be reversed in this way to return the Route Reply since it
tests the discovered route to ensure it is bi-directional before the tests the discovered route to ensure it is bidirectional before the
Route Discovery initiator begins using the route; this route reversal Route Discovery initiator begins using the route; this route reversal
also avoids the overhead of a possible second Route Discovery. also avoids the overhead of a possible second Route Discovery.
However, this route reversal technique will prevent the discovery However, this route reversal technique will prevent the discovery of
of routes using uni-directional links, and in wireless environments routes using unidirectional links, and in wireless environments where
where the use of uni-directional links is permitted, such routes may the use of unidirectional links is permitted, such routes may in some
in some cases be more efficient than those with only bi-directional cases be more efficient than those with only bidirectional links, or
links, or they may be the only way to achieve connectivity to the they may be the only way to achieve connectivity to the target node.
target node.
When initiating a Route Discovery, the sending node saves a copy of When initiating a Route Discovery, the sending node saves a copy of
the original packet (that triggered the Discovery) in a local buffer the original packet (that triggered the Discovery) in a local buffer
called the "Send Buffer". The Send Buffer contains a copy of each called the "Send Buffer". The Send Buffer contains a copy of each
packet that cannot be transmitted by this node because it does not packet that cannot be transmitted by this node because it does not
yet have a source route to the packet's destination. Each packet in yet have a source route to the packet's destination. Each packet in
the Send Buffer is logically associated with the time that it was the Send Buffer is logically associated with the time that it was
placed into the Send Buffer and is discarded after residing in the placed into the Send Buffer and is discarded after residing in the
Send Buffer for some timeout period; if necessary for preventing the Send Buffer for some timeout period; if necessary for preventing the
Send Buffer from overflowing, a FIFO or other replacement strategy Send Buffer from overflowing, a FIFO or other replacement strategy
skipping to change at page 7, line 36 skipping to change at page 7, line 35
initiate a new Route Discovery until the minimum allowable interval initiate a new Route Discovery until the minimum allowable interval
between new Route Discoveries for this target has been reached. This between new Route Discoveries for this target has been reached. This
limitation on the maximum rate of Route Discoveries for the same limitation on the maximum rate of Route Discoveries for the same
target is similar to the mechanism required by Internet nodes to target is similar to the mechanism required by Internet nodes to
limit the rate at which ARP Requests are sent for any single target limit the rate at which ARP Requests are sent for any single target
IP address [3]. IP address [3].
3.2. Basic DSR Route Maintenance 3.2. Basic DSR Route Maintenance
When originating or forwarding a packet using a source route, each When originating or forwarding a packet using a source route, each
node transmitting the packet is responsible for confirming that the node transmitting the packet is responsible for confirming that data
packet has been received by the next node along the source route; the can flow over the link from that node to the next hop. For example,
packet SHOULD be retransmitted (up to a maximum number of attempts) in the situation shown below, node A has originated a packet for
until this confirmation of receipt is received. For example, in the node E using a source route through intermediate nodes B, C, and D:
situation shown below, node A has originated a packet for node E
using a source route through intermediate nodes B, C, and D:
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
| A |---->| B |---->| C |-->? | D | | E | | A |---->| B |---->| C |-->? | D | | E |
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
In this case, node A is responsible for receipt of the packet at B, In this case, node A is responsible for the link from A to B, node B
node B is responsible for receipt at C, node C is responsible for is responsible for the link from B to C, node C is responsible for
receipt at D, and node D is responsible for receipt finally at the the link from C to D, node D is responsible for the link from D to E.
destination E.
This confirmation of receipt in many cases may be provided at no cost An acknowledgment can provide confirmation that a link is capable of
to DSR, either as an existing standard part of the MAC protocol in carrying data, and in wireless networks, acknowledgments are often
use (such as the link-layer acknowledgement frame defined by IEEE provided at no cost, either as an existing standard part of the MAC
802.11 [11]), or by a "passive acknowledgement" [16] (in which, protocol in use (such as the link-layer acknowledgment frame defined
for example, B confirms receipt at C by overhearing C transmit by IEEE 802.11 [11]), or by a "passive acknowledgment" [16] (in
the packet when forwarding it on to D). If neither of these which, for example, B confirms receipt at C by overhearing C transmit
confirmation mechanisms are available, the node transmitting the the packet when forwarding it on to D).
packet can explicitly request a DSR-specific software acknowledgement
be returned by the next node along the route; this software
acknowledgement will normally be transmitted directly to the sending
node, but if the link between these two nodes is uni-directional,
this software acknowledgement could travel over a different,
multi-hop path.
At the original sender of a packet if no receipt confirmation is If a built-in acknowledgment mechanism is not available, the node
received after the sender has retransmitted the packet the maximum transmitting the packet can explicitly request a DSR-specific
number of attempts to the first intermediate node on the source software acknowledgment be returned by the next node along the route;
route, then the sender determines that this first hop of the route this software acknowledgment will normally be transmitted directly
is currently "broken". For example, in the situation shown above, to the sending node, but if the link between these two nodes is
if the sender, node A, is unable to deliver the packet to the next unidirectional, this software acknowledgment could travel over a
node B, then A determines that the hop from A to B is broken. In different, multi-hop path.
this case, node A removes this link from its Route Cache and removes
the DSR routing information that it had previously added to the
packet. Node A then again searches its Route Cache for a route to
the destination node, and if no route is found in the cache, uses the
Route Discovery protocol again to dynamically discover a new route
for the packet.
At an intermediate node forwarding a packet, if no receipt After an acknowledgment has been received from some neighbor, a node
confirmation is received after the node has retransmitted the packet MAY choose to not require acknowledgments from that neighbor for a
the maximum number of attempts, this node SHOULD return a "Route brief period of time, unless the network interface connecting a node
Error" to the original sender of the packet, identifying the link to that neighbor always receives an acknowledgment in response to
over which the packet could not be forwarded. For example, in the unicast traffic.
situation shown above, if C is unable to deliver the packet to the
next node D, then C returns a Route Error to A, stating that the link When a software acknowledgment is used, the acknowledgment request
from C to D is currently "broken". Node A then removes this broken SHOULD be retransmitted up to a maximum number of times. A
link from its cache; any retransmission of the original packet can retransmission of the acknowledgment request can be sent as a
be performed by upper layer protocols such as TCP, if necessary. separate packet, piggybacked on a retransmission of the original
For sending such a retransmission or other packets to this same data packet, or piggybacked on any packet with the same next-hop
destination E, if A has in its Route Cache another route to E destination that does not also contain a software acknowledgment.
(for example, from additional Route Replies from its earlier Route
Discovery, or from having overheard sufficient routing information After the acknowledgment request has been retransmitted the maximum
from other packets), it can send the packet using the new route number of times, if no acknowledgment has been received, then the
immediately. Otherwise, it SHOULD perform a new Route Discovery for sender treats the link to this next-hop destination as currently
this target (subject to the back-off described in Section 3.1). "broken". It SHOULD remove this link from its Route Cache and
SHOULD return a "Route Error" to each node that has sent a packet
routed over that link since an acknowledgment was last received.
For example, in the situation shown above, if C does not receive
an acknowledgment from D after some number of requests, it would
return a Route Error to A, as well as any other node that may have
used the link from C to D since C last received an acknowledgment
from D. Node A then removes this broken link from its cache; any
retransmission of the original packet can be performed by upper
layer protocols such as TCP, if necessary. For sending such a
retransmission or other packets to this same destination E, if A has
in its Route Cache another route to E (for example, from additional
Route Replies from its earlier Route Discovery, or from having
overheard sufficient routing information from other packets), it
can send the packet using the new route immediately. Otherwise, it
SHOULD perform a new Route Discovery for this target (subject to the
back-off described in Section 3.1).
3.3. Additional Route Discovery Features 3.3. Additional Route Discovery Features
3.3.1. Caching Overheard Routing Information 3.3.1. Caching Overheard Routing Information
A node forwarding or otherwise overhearing any packet SHOULD add all A node forwarding or otherwise overhearing any packet SHOULD add all
usable routing information from that packet to its own Route Cache. usable routing information from that packet to its own Route Cache.
The usefulness of routing information in a packet depends on the The usefulness of routing information in a packet depends on the
directionality characteristics of the physical medium (Section 2), as directionality characteristics of the physical medium (Section 2), as
well as the MAC protocol being used. Specifically, three distinct well as the MAC protocol being used. Specifically, three distinct
cases are possible: cases are possible:
- Links in the network frequently are capable of operating only - Links in the network frequently are capable of operating only
uni-directionally (not bi-directionally), and the MAC protocol unidirectionally (not bidirectionally), and the MAC protocol in
in use in the network is capable of transmitting unicast packets
over uni-directional links.
- Links in the network occasionally are capable of operating
only uni-directionally (not bi-directionally), but this
uni-directional restriction on any link is not persistent, almost
all links are physically bi-directional, and the MAC protocol in
use in the network is capable of transmitting unicast packets use in the network is capable of transmitting unicast packets
over uni-directional links. over unidirectional links.
- Links in the network occasionally are capable of operating only
unidirectionally (not bidirectionally), but this unidirectional
restriction on any link is not persistent, almost all links
are physically bidirectional, and the MAC protocol in use in
the network is capable of transmitting unicast packets over
unidirectional links.
- The MAC protocol in use in the network is not capable of - The MAC protocol in use in the network is not capable of
transmitting unicast packets over uni-directional links; transmitting unicast packets over unidirectional links;
only bi-directional links can be used by the MAC protocol for only bidirectional links can be used by the MAC protocol for
transmitting unicast packets. For example, the IEEE 802.11 transmitting unicast packets. For example, the IEEE 802.11
Distributed Coordination Function (DCF) MAC protocol [11] Distributed Coordination Function (DCF) MAC protocol [11]
is capable of transmitting a unicast packet only over a is capable of transmitting a unicast packet only over a
bi-directional link, since the MAC protocol requires the return bidirectional link, since the MAC protocol requires the return
of a link-level acknowledgement packet from the receiver and also of a link-level acknowledgment packet from the receiver and also
optionally requires the bi-directional exchange of an RTS and CTS optionally requires the bidirectional exchange of an RTS and CTS
packet between the transmitter and receiver nodes. packet between the transmitter and receiver nodes.
In the first case above, for example, the source route used in a data In the first case above, for example, the source route used in a data
packet, the accumulated route record in a Route Request, or the route packet, the accumulated route record in a Route Request, or the route
being returned in a Route Reply SHOULD all be cached by any node in being returned in a Route Reply SHOULD all be cached by any node in
the "forward" direction; any node SHOULD cache this information from the "forward" direction; any node SHOULD cache this information from
any such packet received, whether the packet was addressed to this any such packet received, whether the packet was addressed to this
node, sent to a broadcast (or multicast) MAC address, or overheard node, sent to a broadcast (or multicast) MAC address, or overheard
while the node's network interface is in promiscuous mode. However, while the node's network interface is in promiscuous mode. However,
the "reverse" direction of the links identified in such packet the "reverse" direction of the links identified in such packet
skipping to change at page 10, line 18 skipping to change at page 10, line 18
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
| A |---->| B |---->| C |---->| D |---->| E | | A |---->| B |---->| C |---->| D |---->| E |
+-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+ +-----+
As node C forwards a data packet along the route from A to E, it As node C forwards a data packet along the route from A to E, it
SHOULD add to its cache the presence of the "forward" direction SHOULD add to its cache the presence of the "forward" direction
links that it learns from the headers of these packets, from itself links that it learns from the headers of these packets, from itself
to D and from D to E. Node C SHOULD NOT, in this case, cache the to D and from D to E. Node C SHOULD NOT, in this case, cache the
"reverse" direction of the links identified in these packet headers, "reverse" direction of the links identified in these packet headers,
from itself back to B and from B to A, since these links might be from itself back to B and from B to A, since these links might be
uni-directional. unidirectional.
In the second case above, in which links may occasionally operate In the second case above, in which links may occasionally operate
uni-directionally, the links described above SHOULD be cached in both unidirectionally, the links described above SHOULD be cached in both
directions. Furthermore, in this case, if node X overhears (e.g., directions. Furthermore, in this case, if node X overhears (e.g.,
through promiscuous mode) a packet transmitted by node C that is through promiscuous mode) a packet transmitted by node C that is
using a source route from node A to E, node X SHOULD cache all of using a source route from node A to E, node X SHOULD cache all of
these links as well, also including the link from C to X over which these links as well, also including the link from C to X over which
it overheard the packet. it overheard the packet.
In the final case, in which the MAC protocol requires physical In the final case, in which the MAC protocol requires physical
bi-directionality for unicast operation, links from a source bidirectionality for unicast operation, links from a source route
route SHOULD be cached in both directions, except when the packet SHOULD be cached in both directions, except when the packet also
also contains a Route Reply, in which case only the links already contains a Route Reply, in which case only the links already
traversed in this source route SHOULD be cached, but the links not traversed in this source route SHOULD be cached, but the links not
yet traversed in this route SHOULD NOT be cached. yet traversed in this route SHOULD NOT be cached.
3.3.2. Replying to Route Requests using Cached Routes 3.3.2. Replying to Route Requests using Cached Routes
A node receiving a Route Request for which it is not the target, A node receiving a Route Request for which it is not the target,
searches its own Route Cache for a route to the target of the searches its own Route Cache for a route to the target of the
Request. If found, the node generally returns a Route Reply to the Request. If found, the node generally returns a Route Reply to the
initiator itself rather than forwarding the Route Request. In the initiator itself rather than forwarding the Route Request. In the
Route Reply, this node sets the route record to list the sequence of Route Reply, this node sets the route record to list the sequence of
skipping to change at page 14, line 45 skipping to change at page 14, line 45
Error before salvaging the packet. Error before salvaging the packet.
3.4.2. Queued Packets Destined over a Broken Link 3.4.2. Queued Packets Destined over a Broken Link
When an intermediate node forwarding a packet detects through Route When an intermediate node forwarding a packet detects through Route
Maintenance that the next-hop link along the route for that packet Maintenance that the next-hop link along the route for that packet
is broken, in addition to handling that packet as defined for Route is broken, in addition to handling that packet as defined for Route
Maintenance, the node SHOULD also handle in a similar way any pending Maintenance, the node SHOULD also handle in a similar way any pending
packets that it has queued that are destined over this new broken packets that it has queued that are destined over this new broken
link. Specifically, the node SHOULD search its Network Interface link. Specifically, the node SHOULD search its Network Interface
Queue and Retransmission Buffer (Section 4.5) for packets for which Queue and Maintenance Buffer (Section 4.5) for packets for which
the next-hop link is this new broken link. For each such packet the next-hop link is this new broken link. For each such packet
currently queued at this node, the node SHOULD process that packet as currently queued at this node, the node SHOULD process that packet as
follows: follows:
- Remove the packet from the node's Network Interface Queue and - Remove the packet from the node's Network Interface Queue and
Retransmission Buffer and stop any retransmission activity for Maintenance Buffer.
the packet.
- Originate a Route Error for this packet to the original sender of - Originate a Route Error for this packet to the original sender of
the packet, using the procedure described in Section 6.3.4, as if the packet, using the procedure described in Section 6.3.4, as if
the node had already reached the maximum number of retransmission the node had already reached the maximum number of retransmission
attempts for that packet for Route Maintenance. However, in attempts for that packet for Route Maintenance. However, in
sending such Route Errors for queued packets in response to a sending such Route Errors for queued packets in response to a
single new broken link detected, the node SHOULD send no more single new broken link detected, the node SHOULD send no more
than one Route Error to each original sender of any of these than one Route Error to each original sender of any of these
packets. packets.
- If the node has another route to the packet's IP - If the node has another route to the packet's IP
Destination Address in its Route Cache, the node SHOULD Destination Address in its Route Cache, the node SHOULD
salvage the packet as described in Section 6.3.6. Otherwise, the salvage the packet as described in Section 6.3.6. Otherwise, the
node SHOULD discard the packet. node SHOULD discard the packet.
3.4.3. Automatic Route Shortening 3.4.3. Automatic Route Shortening
Source routes in use MAY be automatically shortened if one or more Source routes in use MAY be automatically shortened if one or more
intermediate nodes in the route become no longer necessary. This intermediate nodes in the route become no longer necessary. This
mechanism of automatically shortening routes in use is somewhat mechanism of automatically shortening routes in use is somewhat
similar to the use of passive acknowledgements [16]. In particular, similar to the use of passive acknowledgments [16]. In particular,
if a node is able to overhear a packet carrying a source route (e.g., if a node is able to overhear a packet carrying a source route (e.g.,
by operating its network interface in promiscuous receive mode), then by operating its network interface in promiscuous receive mode), then
this node examines the unexpended portion of that source route. If this node examines the unexpended portion of that source route. If
this node is not the intended next-hop destination for the packet this node is not the intended next-hop destination for the packet
but is named in the later unexpended portion of the packet's source but is named in the later unexpended portion of the packet's source
route, then it can infer that the intermediate nodes before itself in route, then it can infer that the intermediate nodes before itself in
the source route are no longer needed in the route. For example, the the source route are no longer needed in the route. For example, the
figure below illustrates an example in which node D has overheard a figure below illustrates an example in which node D has overheard a
data packet being transmitted from B to C, for later forwarding to D data packet being transmitted from B to C, for later forwarding to D
and to E: and to E:
skipping to change at page 20, line 12 skipping to change at page 20, line 12
The choice of data structure organization to use for the Route Cache The choice of data structure organization to use for the Route Cache
in any DSR implementation is a local matter for each node and affects in any DSR implementation is a local matter for each node and affects
only performance; any reasonable choice of organization for the Route only performance; any reasonable choice of organization for the Route
Cache does not affect either correctness or interoperability. Cache does not affect either correctness or interoperability.
Each entry in the Route Cache SHOULD have a timeout associated Each entry in the Route Cache SHOULD have a timeout associated
with it, to allow that entry to be deleted if not used within some with it, to allow that entry to be deleted if not used within some
time. The particular choice of algorithm and data structure used time. The particular choice of algorithm and data structure used
to implement the Route Cache SHOULD be considered in choosing the to implement the Route Cache SHOULD be considered in choosing the
timeout for entries in the Route Cache. The configuration variable timeout for entries in the Route Cache. The configuration variable
RouteCacheTimeout defined in Section 7 specifies the timeout to be RouteCacheTimeout defined in Section 9 specifies the timeout to be
applied to entries in the Route Cache, although it is also possible applied to entries in the Route Cache, although it is also possible
to instead use an adaptive policy in choosing timeout values rather to instead use an adaptive policy in choosing timeout values rather
than using a single timeout setting for all entries; for example, the than using a single timeout setting for all entries; for example, the
Link-MaxLife cache design (below) uses an adaptive timeout algorithm Link-MaxLife cache design (below) uses an adaptive timeout algorithm
and does not use the RouteCacheTimeout configuration variable. and does not use the RouteCacheTimeout configuration variable.
As guidance to implementors, Appendix A describes a type of link As guidance to implementors, Appendix A describes a type of link
cache known as "Link-MaxLife" that has been shown to outperform cache known as "Link-MaxLife" that has been shown to outperform
other types of link caches and path caches studied in detailed other types of link caches and path caches studied in detailed
simulation [9]. Link-MaxLife is an adaptive link cache in which each simulation [9]. Link-MaxLife is an adaptive link cache in which each
skipping to change at page 23, line 8 skipping to change at page 23, line 8
the value GratReplyHoldoff. the value GratReplyHoldoff.
When a node overhears a packet that would trigger a gratuitous When a node overhears a packet that would trigger a gratuitous
Route Reply, if a corresponding entry already exists in the node's Route Reply, if a corresponding entry already exists in the node's
Gratuitous Route Reply Table, then the node SHOULD NOT send a Gratuitous Route Reply Table, then the node SHOULD NOT send a
gratuitous Route Reply for that packet. Otherwise (no corresponding gratuitous Route Reply for that packet. Otherwise (no corresponding
entry already exists), the node SHOULD create a new entry in its entry already exists), the node SHOULD create a new entry in its
Gratuitous Route Reply Table to record that gratuitous Route Reply, Gratuitous Route Reply Table to record that gratuitous Route Reply,
with a timeout value of GratReplyHoldoff. with a timeout value of GratReplyHoldoff.
4.5. Network Interface Queue and Retransmission Buffer 4.5. Network Interface Queue and Maintenance Buffer
Depending on factors such as the structure and organization of Depending on factors such as the structure and organization of
the operating system, protocol stack implementation, network the operating system, protocol stack implementation, network
interface device driver, and network interface hardware, a interface device driver, and network interface hardware, a packet
packet being transmitted could be queued in a variety of ways. being transmitted could be queued in a variety of ways. For
For example, outgoing packets from the network protocol stack example, outgoing packets from the network protocol stack might be
might be queued at the operating system or link layer, before queued at the operating system or link layer, before transmission
transmission by the network interface. The network interface by the network interface. The network interface might also
might also provide a retransmission mechanism for packets, such provide a retransmission mechanism for packets, such as occurs in
as occurs in IEEE 802.11 [11]; the DSR protocol also requires IEEE 802.11 [11]; the DSR protocol, as part of Route Maintenance,
limited retransmission of packets as part of Route Maintenance. The requires limited buffering of packets already transmitted for
operation of DSR is defined here in terms of two conceptual data which the reachability of the next-hop destination has not yet been
structures that together incorporate this queueing and retransmission determined. The operation of DSR is defined here in terms of two
conceptual data structures that together incorporate this queueing
behavior. behavior.
The Network Interface Queue of a node implementing DSR is an output The Network Interface Queue of a node implementing DSR is an output
queue of packets from the network protocol stack waiting to be queue of packets from the network protocol stack waiting to be
transmitted by the network interface; for example, in the 4.4BSD transmitted by the network interface; for example, in the 4.4BSD
Unix network protocol stack implementation, this queue for a network Unix network protocol stack implementation, this queue for a network
interface is represented as a "struct ifqueue" [33]. This queue is interface is represented as a "struct ifqueue" [33]. This queue is
used to hold packets while the network interface is in the process of used to hold packets while the network interface is in the process of
transmitting another packet. transmitting another packet.
The Retransmission Buffer of a node implementing DSR is a queue of The Maintenance Buffer of a node implementing DSR is a queue of
packets sent by this node that are awaiting retransmission as part packets sent by this node that are awaiting next-hop reachability
of Route Maintenance. For each packet in the Retransmission Buffer, confirmation as part of Route Maintenance. For each packet in
a node maintains a count of the number of retransmissions and the the Maintenance Buffer, a node maintains a count of the number
time of the last retransmission. The Retransmission Buffer MAY be of retransmissions and the time of the last retransmission. The
of limited size; when adding a new packet to the Retransmission Maintenance Buffer MAY be of limited size; when adding a new packet
Buffer, if the buffer size is insufficient to hold the new packet, to the Maintenance Buffer, if the buffer size is insufficient to hold
the new packet SHOULD be silently discarded. The maximum number of the new packet, the new packet SHOULD be silently discarded. If,
retransmission attempts for a packet for Route Maintenance (after the after MaxMaintRexmt attempts to confirm next-hop reachability of
initial transmission of the packet) is MaxMaintRexmt. After this some node, no confirmation is received, all packets in this node's
time, if Route Maintenance for a packet has not been satisfied, the Maintenance Buffer with this next-hop destination SHOULD be removed
packet SHOULD be removed from the Retransmission Buffer, stopping from the Maintenance Buffer; in this case, the node also SHOULD
retransmissions for that packet; in this case, the node also SHOULD originate a Route Error for this packet to each original source of
originate a Route Error for this packet to the original source of the a packet removed in this way (Section 6.3) and SHOULD salvage each
packet (Section 6.3) and SHOULD salvage the packet (Section 6.3.6) if packet removed in this way (Section 6.3.6) if it has another route
it has another route to the packet's IP Destination Address in its to that packet's IP Destination Address in its Route Cache. The
Route Cache. The definition of MaxMaintRexmt conceptually includes definition of MaxMaintRexmt conceptually includes any retransmissions
any retransmissions that might be attempted for a packet at the link that might be attempted for a packet at the link layer or within
layer or within the network interface hardware. The retransmission the network interface hardware. The timeout value to use for each
timeout value to use for each transmission attempt for a packet transmission attempt for an acknowledgment request depends on the
depends on the type of acknowledgement mechanism used for Route type of acknowledgment mechanism used for Route Maintenance for that
Maintenance for that attempt, as described in Section 6.3. attempt, as described in Section 6.3.
4.6. Blacklist
When a node using the DSR protocol is connected through an
interface that requires physically bidirectional links for unicast
transmission, it MUST keep a blacklist. A Blacklist is a table,
indexed by neighbor address, that indicates that the link between
this node and the specified neighbor may not be bidirectional. A
node places another node's address in this list when it believes that
broadcast packets from that other node reach this node, but that
unicast transmission between the two nodes is not possible. For
example, if a node forwarding a Route Reply discovers that the next
hop is unreachable, it places that next hop in the node's blacklist.
Once a node discovers that it can communicate bidirectionally with
one of the nodes listed in the blacklist, it SHOULD remove that node
from the blacklist. For example, if A has B in its blacklist, but
A hears B forward a Route Request with a hop list indicating that
the broadcast from A to B was successful, A SHOULD remove B from its
blacklist.
A node MUST associate a state with each node in the blacklist,
specifying whether the unidirectionality is "questionable" or
"probable." Each time the unreachability is positively determined,
the node SHOULD set the state to "probable." After the unreachability
has not been positively determined for some amount of time, the state
should revert to "questionable." A node MAY expire nodes from its
blacklist after a reasonable amount of time.
5. DSR Header Format 5. DSR Header Format
The Dynamic Source Routing protocol makes use of a special header The Dynamic Source Routing protocol makes use of a special header
carrying control information that can be included in any existing IP carrying control information that can be included in any existing IP
packet. This DSR header in a packet contains a small fixed-sized, packet. This DSR header in a packet contains a small fixed-sized,
4-octet portion, followed by a sequence of zero or more DSR options 4-octet portion, followed by a sequence of zero or more DSR options
carrying optional information. The end of the sequence of DSR carrying optional information. The end of the sequence of DSR
options in the DSR header is implied by total length of the DSR options in the DSR header is implied by total length of the DSR
header. header.
skipping to change at page 26, line 51 skipping to change at page 27, line 5
Contains one or more pieces of optional information (DSR Contains one or more pieces of optional information (DSR
options), encoded in type-length-value (TLV) format (with the options), encoded in type-length-value (TLV) format (with the
exception of the Pad1 option, described in Section 5.8). exception of the Pad1 option, described in Section 5.8).
The placement of DSR options following the fixed portion of the DSR The placement of DSR options following the fixed portion of the DSR
header MAY be padded for alignment. However, due to the typically header MAY be padded for alignment. However, due to the typically
limited available wireless bandwidth in ad hoc networks, this padding limited available wireless bandwidth in ad hoc networks, this padding
is not required, and receiving nodes MUST NOT expect options within a is not required, and receiving nodes MUST NOT expect options within a
DSR header to be aligned. DSR header to be aligned.
A node inserting a DSR header into a packet MUST set the Don't
Fragment (DF) bit in the packet's IP header.
The following types of DSR options are defined in this document for The following types of DSR options are defined in this document for
use within a DSR header: use within a DSR header:
- Route Request option (Section 5.2) - Route Request option (Section 5.2)
- Route Reply option (Section 5.3) - Route Reply option (Section 5.3)
- Route Error option (Section 5.4) - Route Error option (Section 5.4)
- Acknowledgement Request option (Section 5.5) - Acknowledgment Request option (Section 5.5)
- Acknowledgement option (Section 5.6) - Acknowledgment option (Section 5.6)
- DSR Source Route option (Section 5.7) - DSR Source Route option (Section 5.7)
- Pad1 option (Section 5.8) - Pad1 option (Section 5.8)
- PadN option (Section 5.9) - PadN option (Section 5.9)
5.2. Route Request Option 5.2. Route Request Option
The Route Request option in a DSR header is encoded as follows: The Route Request option in a DSR header is encoded as follows:
skipping to change at page 35, line 28 skipping to change at page 35, line 28
5 5
Opt Data Len Opt Data Len
8-bit unsigned integer. Length of the option, in octets, 8-bit unsigned integer. Length of the option, in octets,
excluding the Option Type and Opt Data Len fields. excluding the Option Type and Opt Data Len fields.
Identification Identification
The Identification field is set to a unique value and is copied The Identification field is set to a unique value and is copied
into the Identification field of the Acknowledgement option into the Identification field of the Acknowledgment option when
when returned by the node receiving the packet over this hop. returned by the node receiving the packet over this hop.
An Acknowledgement Request option MUST NOT appear more than once An Acknowledgment Request option MUST NOT appear more than once
within a DSR header. within a DSR header.
5.6. Acknowledgment Option 5.6. Acknowledgment Option
The Acknowledgment option in a DSR header is encoded as follows: The Acknowledgment option in a DSR header is encoded as follows:
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len | Identification | | Option Type | Opt Data Len | Identification |
skipping to change at page 36, line 30 skipping to change at page 36, line 30
6 6
Opt Data Len Opt Data Len
8-bit unsigned integer. Length of the option, in octets, 8-bit unsigned integer. Length of the option, in octets,
excluding the Option Type and Opt Data Len fields. excluding the Option Type and Opt Data Len fields.
Identification Identification
Copied from the Identification field of the Acknowledgement Copied from the Identification field of the Acknowledgment
Request option of the packet being acknowledged. Request option of the packet being acknowledged.
ACK Source Address ACK Source Address
The address of the node originating the acknowledgment. The address of the node originating the acknowledgment.
ACK Destination Address ACK Destination Address
The address of the node to which the acknowledgment is to be The address of the node to which the acknowledgment is to be
delivered. delivered.
An Acknowledgement option MAY appear one or more times within a DSR An Acknowledgment option MAY appear one or more times within a DSR
header. header.
5.7. DSR Source Route Option 5.7. DSR Source Route Option
The DSR Source Route option in a DSR header is encoded as follows: The DSR Source Route option in a DSR header is encoded as follows:
0 1 2 3 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len |F|L|Reservd|Salvage| Segs Left | | Option Type | Opt Data Len |F|L|Reservd|Salvage| Segs Left |
skipping to change at page 41, line 37 skipping to change at page 41, line 37
"limited broadcast" address (255.255.255.255) [3], copying the "limited broadcast" address (255.255.255.255) [3], copying the
original IP Destination Address to the Target Address field of original IP Destination Address to the Target Address field of
the new Route Request option added to the packet, as described in the new Route Request option added to the packet, as described in
Section 6.2.1. Section 6.2.1.
- If the packet now does not contain a Route Request option, - If the packet now does not contain a Route Request option,
then this node must have a route to the Destination Address then this node must have a route to the Destination Address
of the packet; if the node has more than one route to this of the packet; if the node has more than one route to this
Destination Address, the node selects one to use for this packet. Destination Address, the node selects one to use for this packet.
If the length of this route is greater than 1 hop, or if the If the length of this route is greater than 1 hop, or if the
node determines to request a DSR network-layer acknowledgement node determines to request a DSR network-layer acknowledgment
from the first-hop node in that route, then insert a DSR header from the first-hop node in that route, then insert a DSR header
into the packet, as described in Section 6.1.2, and insert a DSR into the packet, as described in Section 6.1.2, and insert a DSR
Source Route option, as described in Section 6.1.3. The source Source Route option, as described in Section 6.1.3. The source
route in the packet is initialized from the selected route to the route in the packet is initialized from the selected route to the
Destination Address of the packet. Destination Address of the packet.
- Transmit the packet to the first-hop node address given in - Transmit the packet to the first-hop node address given in
selected source route, using Route Maintenance to retransmit the selected source route, using Route Maintenance to determine the
packet if necessary, as described in Section 6.3. reachability of the next hop, as described in Section 6.3.
6.1.2. Adding a DSR Header to a Packet 6.1.2. Adding a DSR Header to a Packet
A node originating a packet adds a DSR header to the packet, if A node originating a packet adds a DSR header to the packet, if
necessary, to carry information needed by the routing protocol. A necessary, to carry information needed by the routing protocol. A
packet MUST NOT contain more than one DSR header. A DSR header is packet MUST NOT contain more than one DSR header. A DSR header is
added to a packet by performing the following sequence of steps added to a packet by performing the following sequence of steps
(these steps assume that the packet contains no other headers that (these steps assume that the packet contains no other headers that
MUST be located in the packet before the DSR header): MUST be located in the packet before the DSR header):
skipping to change at page 44, line 11 skipping to change at page 44, line 11
After possibly updating the node's Route Cache in response to After possibly updating the node's Route Cache in response to
the routing information in the Route Reply option, then if the the routing information in the Route Reply option, then if the
packet's IP Destination Address matches one of this node's IP packet's IP Destination Address matches one of this node's IP
addresses, the node MUST then process the Route Reply option as addresses, the node MUST then process the Route Reply option as
described in Section 6.2.5. described in Section 6.2.5.
- If the DSR header contains a Route Error option, the node MUST - If the DSR header contains a Route Error option, the node MUST
process the Route Error option as described in Section 6.3.5. process the Route Error option as described in Section 6.3.5.
- If the DSR header contains an Acknowledgement Request option, the - If the DSR header contains an Acknowledgment Request option, the
node MUST process the Acknowledgement Request option as described node MUST process the Acknowledgment Request option as described
in Section 6.3.3. in Section 6.3.3.
- If the DSR header contains an Acknowledgement option, then - If the DSR header contains an Acknowledgment option, then subject
subject to the conditions identified in Section 3.3.1, the node to the conditions identified in Section 3.3.1, the node SHOULD
SHOULD add to its Route Cache the single link from the node add to its Route Cache the single link from the node identified
identified by the ACK Source Address field to the node identified by the ACK Source Address field to the node identified by the
by the ACK Destination Address field. ACK Destination Address field.
After possibly updating the node's Route Cache in response to After possibly updating the node's Route Cache in response to
the routing information in the Acknowledgement option, the node the routing information in the Acknowledgment option, the node
MUST then process the Acknowledgement option as described in MUST then process the Acknowledgment option as described in
Section 6.3.3. Section 6.3.3.
- If the DSR header contains a DSR Source Route option, the node - If the DSR header contains a DSR Source Route option, the node
SHOULD extract the source route from the DSR Source Route and SHOULD extract the source route from the DSR Source Route and
add this routing information to its Route Cache, subject to the add this routing information to its Route Cache, subject to the
conditions identified in Section 3.3.1. If the value of the conditions identified in Section 3.3.1. If the value of the
Salvage field in the DSR Source Route option is zero, then the Salvage field in the DSR Source Route option is zero, then the
routing information from the DSR Source Route is the sequence of routing information from the DSR Source Route is the sequence of
hop addresses hop addresses
skipping to change at page 45, line 51 skipping to change at page 45, line 51
entry SHOULD be initialized to the value GratReplyHoldoff. After entry SHOULD be initialized to the value GratReplyHoldoff. After
this timeout has expired, the node SHOULD delete this entry from this timeout has expired, the node SHOULD delete this entry from
its Gratuitous Route Reply Table. its Gratuitous Route Reply Table.
- After creating the new Gratuitous Route Reply Table entry - After creating the new Gratuitous Route Reply Table entry
above, the node originates a gratuitous Route Reply to the above, the node originates a gratuitous Route Reply to the
IP Source Address of this overheard packet, as described in IP Source Address of this overheard packet, as described in
Section 3.4.3. Section 3.4.3.
If the MAC protocol in use in the network is not capable of If the MAC protocol in use in the network is not capable of
transmitting unicast packets over uni-directional links, as transmitting unicast packets over unidirectional links, as
discussed in Section 3.3.1, then in originating this Route Reply, discussed in Section 3.3.1, then in originating this Route Reply,
the node MUST use a source route for routing the Route Reply the node MUST use a source route for routing the Route Reply
packet that is obtained by reversing the sequence of hops over packet that is obtained by reversing the sequence of hops over
which the packet triggering the gratuitous Route Reply was routed which the packet triggering the gratuitous Route Reply was routed
in reaching and being overheard by this node; this reversing of in reaching and being overheard by this node; this reversing of
the route uses the gratuitous Route Reply to test this sequence the route uses the gratuitous Route Reply to test this sequence
of hops for bi-directionality, preventing the gratuitous Route of hops for bidirectionality, preventing the gratuitous Route
Reply from being received by the initiator of the Route Discovery Reply from being received by the initiator of the Route Discovery
unless each of the hops over which the gratuitous Route Reply is unless each of the hops over which the gratuitous Route Reply is
returned is bi-directional. returned is bidirectional.
- Discard the overheard packet, since the packet has been received - Discard the overheard packet, since the packet has been received
before its normal traversal of the packet's source route would before its normal traversal of the packet's source route would
have caused it to reach this receiving node. Another copy of have caused it to reach this receiving node. Another copy of
the packet will normally arrive at this node as indicated in the packet will normally arrive at this node as indicated in
the packet's source route; discarding this initial copy of the the packet's source route; discarding this initial copy of the
packet, which triggered the gratuitous Route Reply, will prevent packet, which triggered the gratuitous Route Reply, will prevent
the duplication of this packet that would otherwise occur. the duplication of this packet that would otherwise occur.
If the packet is not discarded as part of automatic route shortening If the packet is not discarded as part of automatic route shortening
skipping to change at page 46, line 45 skipping to change at page 46, line 45
the packet. Do not process the DSR Source Route option further. the packet. Do not process the DSR Source Route option further.
- Else, decrement the value of the Segments Left field by 1. Let i - Else, decrement the value of the Segments Left field by 1. Let i
equal n minus Segments Left. This is the index of the next equal n minus Segments Left. This is the index of the next
address to be visited in the Address vector. address to be visited in the Address vector.
- If Address[i] or the IP Destination Address is a multicast - If Address[i] or the IP Destination Address is a multicast
address, then discard the packet. Do not process the DSR Source address, then discard the packet. Do not process the DSR Source
Route option further. Route option further.
- If the MTU of the link over which this node would transmit the - If the MTU of the link over which this node would transmit
packet to forward it to the node Address[i] is less than the size the packet to forward it to the node Address[i] is less than
of the packet, the node MUST discard the packet and send an ICMP the size of the packet, the node MUST either discard the
Packet Too Big message to the packet's Source Address [26]. packet and send an ICMP Packet Too Big message to the packet's
Source Address [26] or fragment it as specified in Section 8.
- Forward the packet to the IP address specified in the Address[i] - Forward the packet to the IP address specified in the Address[i]
field of the IP header, following normal IP forwarding field of the IP header, following normal IP forwarding
procedures, including checking and decrementing the Time-to-Live procedures, including checking and decrementing the Time-to-Live
(TTL) field in the packet's IP header [27, 3]. In this (TTL) field in the packet's IP header [27, 3]. In this
forwarding of the packet, the next-hop node (identified by forwarding of the packet, the next-hop node (identified by
Address[i]) MUST be treated as a direct neighbor node: the Address[i]) MUST be treated as a direct neighbor node: the
transmission to that next node MUST be done in a single IP transmission to that next node MUST be done in a single IP
forwarding hop, without Route Discovery and without searching the forwarding hop, without Route Discovery and without searching the
Route Cache. Route Cache.
- In forwarding the packet, perform Route Maintenance for the next - In forwarding the packet, perform Route Maintenance for the
hop of the packet, by verifying that the packet was received by next hop of the packet, by verifying that the next-hop node is
that next-hop node, as described in Section 6.3. reachable, as described in Section 6.3.
Multicast addresses MUST NOT appear in a DSR Source Route option or Multicast addresses MUST NOT appear in a DSR Source Route option or
in the IP Destination Address field of a packet carrying a DSR Source in the IP Destination Address field of a packet carrying a DSR Source
Route option in a DSR header. Route option in a DSR header.
6.2. Route Discovery Processing 6.2. Route Discovery Processing
Route Discovery is the mechanism by which a node S wishing to send a Route Discovery is the mechanism by which a node S wishing to send a
packet to a destination node D obtains a source route to D. Route packet to a destination node D obtains a source route to D. Route
Discovery is used only when S attempts to send a packet to D and Discovery is used only when S attempts to send a packet to D and
skipping to change at page 50, line 11 skipping to change at page 50, line 11
between consecutive Route Discovery initiations for this target between consecutive Route Discovery initiations for this target
node with the same hop limit SHOULD increase by doubling the node with the same hop limit SHOULD increase by doubling the
timeout value on each new initiation. timeout value on each new initiation.
The behavior of a node processing a packet containing DSR header The behavior of a node processing a packet containing DSR header
with both a DSR Source Route option and a Route Request option is with both a DSR Source Route option and a Route Request option is
unspecified. Packets SHOULD NOT contain both a DSR Source Route unspecified. Packets SHOULD NOT contain both a DSR Source Route
option and a Route Request option. option and a Route Request option.
Packets containing a Route Request option SHOULD NOT include Packets containing a Route Request option SHOULD NOT include
an Acknowledgement Request option, SHOULD NOT expect link-layer an Acknowledgment Request option, SHOULD NOT expect link-layer
acknowledgement or passive acknowledgment, and SHOULD NOT be acknowledgment or passive acknowledgment, and SHOULD NOT be
retransmitted. The retransmission of packets containing a Route retransmitted. The retransmission of packets containing a Route
Request option is controlled solely by the logic described in this Request option is controlled solely by the logic described in this
section. section.
6.2.2. Processing a Received Route Request Option 6.2.2. Processing a Received Route Request Option
When a node receives a packet containing a Route Request option, that When a node receives a packet containing a Route Request option, that
node MUST process the option according to the following sequence of node MUST process the option according to the following sequence of
steps: steps:
skipping to change at page 50, line 52 skipping to change at page 50, line 52
node MUST NOT process the Route Request option further and MUST node MUST NOT process the Route Request option further and MUST
NOT retransmit the Route Request to propagate it to other nodes NOT retransmit the Route Request to propagate it to other nodes
as part of the Route Discovery. as part of the Route Discovery.
- Else, the node MUST examine the route recorded in the Route - Else, the node MUST examine the route recorded in the Route
Request option (the IP Source Address field and the sequence of Request option (the IP Source Address field and the sequence of
Address[i] fields) to determine if this node's own IP address Address[i] fields) to determine if this node's own IP address
already appears in this list of addresses. If so, the node MUST already appears in this list of addresses. If so, the node MUST
discard the entire packet carrying the Route Request option. discard the entire packet carrying the Route Request option.
- Else, if the Route Request through a network interface that
requires physically bidirectional links for unicast transmission,
the node MUST check if the Request was last forwarded by a node
on its blacklist. If such an entry is found, and the state of
the unidirectional link is "probable," then the Request MUST be
silently discarded.
- Else, if the Route Request through a network interface that
requires physically bidirectional links for unicast transmission,
the node MUST check if the Request was last forwarded by a node
on its blacklist. If such an entry is found, and the state of
the unidirectional link is "questionable," then the node MUST
create and unicast a Route Request packet to that previous node,
setting the IP Time-To-Live (TTL) to 1 to prevent the Request
from being propagated. If the node receives a Route Reply in
response to the new Request, it MUST remove the blacklist entry
for that node, and SHOULD continue processing. If the node does
not receive a Reply within some reasonable amount of time, MUST
silently discard the Route Request packet.
- Else, the node MUST search its Route Request Table for an entry - Else, the node MUST search its Route Request Table for an entry
for the initiator of this Route Request (the IP Source Address for the initiator of this Route Request (the IP Source Address
field). If such an entry is found in the table, the node MUST field). If such an entry is found in the table, the node MUST
search the cache of Identification values of recently received search the cache of Identification values of recently received
Route Requests in that table entry, to determine if an entry Route Requests in that table entry, to determine if an entry
is present in the cache matching the Identification value is present in the cache matching the Identification value
and target node address in this Route Request. If such an and target node address in this Route Request. If such an
(Identification, target address) entry is found in this cache in (Identification, target address) entry is found in this cache in
this entry in the Route Request Table, then the node MUST discard this entry in the Route Request Table, then the node MUST discard
the entire packet carrying the Route Request option. the entire packet carrying the Route Request option.
skipping to change at page 55, line 15 skipping to change at page 55, line 33
Request). Request).
After creating and initializing the Route Reply option and the IP After creating and initializing the Route Reply option and the IP
packet containing it, send the Route Reply. In sending the Route packet containing it, send the Route Reply. In sending the Route
Reply from this node (but not from nodes forwarding the Route Reply), Reply from this node (but not from nodes forwarding the Route Reply),
this node SHOULD delay the Reply by a small jitter period chosen this node SHOULD delay the Reply by a small jitter period chosen
randomly between 0 and BroadcastJitter. randomly between 0 and BroadcastJitter.
When returning any Route Reply in the case in which the MAC protocol When returning any Route Reply in the case in which the MAC protocol
in use in the network is not capable of transmitting unicast packets in use in the network is not capable of transmitting unicast packets
over uni-directional links, the source route used for routing over unidirectional links, the source route used for routing the
the Route Reply packet MUST be obtained by reversing the sequence Route Reply packet MUST be obtained by reversing the sequence
of hops in the Route Request packet (the source route that is of hops in the Route Request packet (the source route that is
then returned in the Route Reply). This restriction on returning then returned in the Route Reply). This restriction on returning
a Route Reply enables the Route Reply to test this sequence of a Route Reply enables the Route Reply to test this sequence of
hops for bi-directionality, preventing the Route Reply from being hops for bidirectionality, preventing the Route Reply from being
received by the initiator of the Route Discovery unless each of received by the initiator of the Route Discovery unless each of
the hops over which the Route Reply is returned (and thus each the hops over which the Route Reply is returned (and thus each
of the hops in the source route being returned in the Reply) is of the hops in the source route being returned in the Reply) is
bi-directional. bidirectional.
If sending a Route Reply to the initiator of the Route Request If sending a Route Reply to the initiator of the Route Request
requires performing a Route Discovery, the Route Reply Option MUST requires performing a Route Discovery, the Route Reply Option MUST
be piggybacked on the packet that contains the Route Request. This be piggybacked on the packet that contains the Route Request. This
piggybacking prevents a loop wherein the target of the new Route piggybacking prevents a loop wherein the target of the new Route
Request (which was itself the initiator of the original Route Request (which was itself the initiator of the original Route
Request) must do another Route Request in order to return its Request) must do another Route Request in order to return its
Route Reply. Route Reply.
If sending the Route Reply to the initiator of the Route Request If sending the Route Reply to the initiator of the Route Request
skipping to change at page 57, line 5 skipping to change at page 56, line 25
described there. As described in Section 4.1 anytime a node adds described there. As described in Section 4.1 anytime a node adds
new information to its Route Cache (including the information added new information to its Route Cache (including the information added
from this Route Reply option), the node SHOULD check each packet in from this Route Reply option), the node SHOULD check each packet in
its own Send Buffer (Section 4.2) to determine whether a route to its own Send Buffer (Section 4.2) to determine whether a route to
that packet's IP Destination Address now exists in the node's Route that packet's IP Destination Address now exists in the node's Route
Cache (including the information just added to the Cache). If so, Cache (including the information just added to the Cache). If so,
the packet SHOULD then be sent using that route and removed from the the packet SHOULD then be sent using that route and removed from the
Send Buffer. This general procedure handles all processing required Send Buffer. This general procedure handles all processing required
for a received Route Reply option. for a received Route Reply option.
When a MAC protocol requires bidirectional links for unicast
transmission, a unidirectional link may be discovered by the
propagation of the Route Request. When the Route Reply is sent over
the reverse path, a forwarding node may discover that the next-hop is
unreachable. In this case, it MUST add the next-hop address to its
blacklist.
6.3. Route Maintenance Processing 6.3. Route Maintenance Processing
Route Maintenance is the mechanism by which a source node S is able Route Maintenance is the mechanism by which a source node S is able
to detect, while using a source route to some destination node D, to detect, while using a source route to some destination node D,
if the network topology has changed such that it can no longer use if the network topology has changed such that it can no longer use
its route to D because a link along the route no longer works. When its route to D because a link along the route no longer works. When
Route Maintenance indicates that a source route is broken, S can Route Maintenance indicates that a source route is broken, S can
attempt to use any other route it happens to know to D, or can invoke attempt to use any other route it happens to know to D, or can invoke
Route Discovery again to find a new route for subsequent packets Route Discovery again to find a new route for subsequent packets
to D. Route Maintenance for this route is used only when S is to D. Route Maintenance for this route is used only when S is
actually sending packets to D. actually sending packets to D.
Specifically, when forwarding a packet, a node MUST attempt to Specifically, when forwarding a packet, a node MUST attempt
receive an acknowledgement for the packet from the next-hop node. If to confirm the reachability of the next-hop node, unless such
no acknowledgement is received after MaxMaintRexmt retransmissions of confirmation had been received in the last MaintHoldoffTime.
the packet (after the initial transmission of the packet), the node Individual implementations MAY choose to bypass such confirmation
determines that the link for this next-hop node of the source route for some limited number of packets, as long as those packets
is "broken". This acknowledgement from the next-hop node for Route all fall within MaintHoldoffTime within the last confirmation.
Maintenance can be implemented using a link-layer acknowledgement If no confirmation is received after the retransmission of
(Section 6.3.1), using a "passive acknowledgement" (Section 6.3.2), MaxMaintRexmt acknowledgment requests, after the initial transmission
or using a network-layer acknowledgement (Section 6.3.3); the of the packet, and conceptually including all retransmissions
particular strategy for retransmission timing depends on the type of provided by the MAC layer, the node determines that the link
acknowledgement mechanism used. If no acknowledgment is received for this next-hop node of the source route is "broken". This
after MaxMaintRexmt retransmissions (if necessary), the node SHOULD confirmation from the next-hop node for Route Maintenance can be
implemented using a link-layer acknowledgment (Section 6.3.1),
using a "passive acknowledgment" (Section 6.3.2), or using a
network-layer acknowledgment (Section 6.3.3); the particular strategy
for retransmission timing depends on the type of acknowledgment
mechanism used. When passive acknowledgments are being used, each
retransmitted acknowledgment request SHOULD be explicit software
acknowledgment requests. If no acknowledgment is received after
MaxMaintRexmt retransmissions (if necessary), the node SHOULD
originate a Route Error to the original sender of the packet, as originate a Route Error to the original sender of the packet, as
described in Section 6.3.4. described in Section 6.3.4.
In deciding whether or not to send a Route Error in response to In deciding whether or not to send a Route Error in response to
attempting to forward a packet from some sender over a broken link, attempting to forward a packet from some sender over a broken link,
a node MUST limit the number of consecutive packets from a single a node MUST limit the number of consecutive packets from a single
sender that the node attempts to forward over this same broken sender that the node attempts to forward over this same broken
link for which the node chooses not to return a Route Error; this link for which the node chooses not to return a Route Error; this
requirement MAY be satisfied by returning a Route Error for each requirement MAY be satisfied by returning a Route Error for each
packet that the node attempts to forward over a broken link. packet that the node attempts to forward over a broken link.
6.3.1. Using Link-Layer Acknowledgments 6.3.1. Using Link-Layer Acknowledgments
If the MAC protocol in use provides feedback as to the successful If the MAC protocol in use provides feedback as to the successful
delivery of a data packet (such as is provided by the link-layer delivery of a data packet (such as is provided by the link-layer
acknowledgement frame defined by IEEE 802.11 [11]), then the use acknowledgment frame defined by IEEE 802.11 [11]), then the use
of the DSR Acknowledgement Request and Acknowledgement options of the DSR Acknowledgment Request and Acknowledgment options
is not necessary. If such link-layer feedback is available, it is not necessary. If such link-layer feedback is available, it
SHOULD be used instead of any other acknowledgement mechanism SHOULD be used instead of any other acknowledgment mechanism for
for Route Maintenance, and the node SHOULD NOT use either passive Route Maintenance, and the node SHOULD NOT use either passive
acknowledgements or network-layer acknowledgements for Route acknowledgments or network-layer acknowledgments for Route
Maintenance. Maintenance.
When using link-layer acknowledgements for Route Maintenance, the When using link-layer acknowledgments for Route Maintenance, the
retransmission timing and the timing at which retransmission attempts retransmission timing and the timing at which retransmission attempts
are scheduled are generally controlled by the particular link layer are scheduled are generally controlled by the particular link layer
implementation in use in the network. For example, in IEEE 802.11, implementation in use in the network. For example, in IEEE 802.11,
the link-layer acknowledgement is returned after the data packet as the link-layer acknowledgment is returned after the data packet as
a part of the basic access method of of the IEEE 802.11 Distributed a part of the basic access method of of the IEEE 802.11 Distributed
Coordination Function (DCF) MAC protocol; the time at which the Coordination Function (DCF) MAC protocol; the time at which the
acknowledgement is expected to arrive and the time at which the next acknowledgment is expected to arrive and the time at which the next
retransmission attempt (if necessary) will occur are controlled by retransmission attempt (if necessary) will occur are controlled by
the MAC protocol implementation. the MAC protocol implementation.
When a node receives a link-layer acknowledgement for any packet in When a node receives a link-layer acknowledgment for any packet in
its Retransmission Buffer, that node SHOULD remove that packet from its Maintenance Buffer, that node SHOULD remove that packet, as well
its Retransmission Buffer, stopping Route Maintenance retransmissions as any other packets in its Maintenance Buffer with the same next-hop
for that packet. destination, from its Maintenance Buffer.
6.3.2. Using Passive Acknowledgments 6.3.2. Using Passive Acknowledgments
When link-layer acknowledgements are not available, but passive When link-layer acknowledgments are not available, but passive
acknowledgements [16] are available, passive acknowledgements SHOULD acknowledgments [16] are available, passive acknowledgments SHOULD be
be used for Route Maintenance when originating or forwarding a packet used for Route Maintenance when originating or forwarding a packet
along any hop other than the last hop (the hop leading to the IP along any hop other than the last hop (the hop leading to the IP
Destination Address node of the packet). In particular, passive Destination Address node of the packet). In particular, passive
acknowledgements SHOULD be used for Route Maintenance in such cases acknowledgments SHOULD be used for Route Maintenance in such cases if
if the node can place its network interface into "promiscuous" the node can place its network interface into "promiscuous" receive
receive mode, and network links used for data packets generally mode, and network links used for data packets generally operate
operate bi-directionally (such as when the MAC protocol requires bidirectionally.
this, as with IEEE 802.11).
A node MUST NOT attempt to use passive acknowledgements for Route A node MUST NOT attempt to use passive acknowledgments for Route
Maintenance for a packet originated or forwarded over its last hop Maintenance for a packet originated or forwarded over its last hop
(the hop leading to the IP Destination Address node of the packet), (the hop leading to the IP Destination Address node of the packet),
since the receiving node will not be forwarding the packet and thus since the receiving node will not be forwarding the packet and thus
no passive acknowledgement will be available to be heard by this no passive acknowledgment will be available to be heard by this node.
node. Beyond this restriction, a node MAY utilize a variety of Beyond this restriction, a node MAY utilize a variety of strategies
strategies in using passive acknowledgements for Route Maintenance of in using passive acknowledgments for Route Maintenance of a packet
a packet that it originates or forwards. For example, the following that it originates or forwards. For example, the following two
two strategies are possible: strategies are possible:
- Each time a node receives a packet to be forwarded to a node - Each time a node receives a packet to be forwarded to a node
other than the final destination (the IP Destination Address other than the final destination (the IP Destination Address of
of the packet), that node sends the original transmission of the packet), that node sends the original transmission of that
that packet without requesting a network-layer acknowledgement packet without requesting a network-layer acknowledgment for it.
for it. If no passive acknowledgement is received within If no passive acknowledgment is received within PassiveAckTimeout
PassiveAckTimeout after this transmission, the node retransmits after this transmission, the node retransmits the packet, again
the packet, again without requesting a network-layer without requesting a network-layer acknowledgment for it; the
acknowledgement for it; the same PassiveAckTimeout timeout value same PassiveAckTimeout timeout value is used for each such
is used for each such attempt. If no acknowledgement has been attempt. If no acknowledgment has been received after a total
received after a total of TryPassiveAcks retransmissions of of TryPassiveAcks retransmissions of the packet, network-layer
the packet, network-layer acknowledgements (as described in acknowledgments (as described in Section 6.3.3) are used for all
Section 6.3.3) are used for all remaining attempts for that remaining attempts for that packet.
packet.
- Each node keeps a table of possible next-hop destination nodes, - Each node keeps a table of possible next-hop destination nodes,
noting whether or not passive acknowledgements can typically noting whether or not passive acknowledgments can typically
be expected from transmission to that node, and the expected be expected from transmission to that node, and the expected
latency and jitter of a passive acknowledgement from that node. latency and jitter of a passive acknowledgment from that node.
Each time a node receives a packet to be forwarded to a node Each time a node receives a packet to be forwarded to a node
other than the IP Destination Address, the node checks its table other than the IP Destination Address, the node checks its table
of next-hop destination nodes to determine whether to use a of next-hop destination nodes to determine whether to use a
passive acknowledgement or a network-layer acknowledgement for passive acknowledgment or a network-layer acknowledgment for
that transmission to that node. The timeout for this packet that transmission to that node. The timeout for this packet
can also be derived from this table. A node using this method can also be derived from this table. A node using this method
SHOULD prefer using passive acknowledgements to network-layer SHOULD prefer using passive acknowledgments to network-layer
acknowledgements. acknowledgments.
In using passive acknowledgements for a packet that it originates or In using passive acknowledgments for a packet that it originates or
forwards, a node considers the later receipt of a new packet (e.g., forwards, a node considers the later receipt of a new packet (e.g.,
with promiscuous receive mode enabled on its network interface) to be with promiscuous receive mode enabled on its network interface) to be
an acknowledgement of this first packet if both of the following two an acknowledgment of this first packet if both of the following two
tests succeed: tests succeed:
- The Source Address, Destination Address, Protocol, - The Source Address, Destination Address, Protocol,
Identification, and Fragment Offset fields in the IP header Identification, and Fragment Offset fields in the IP header
of the two packets MUST match [27], and of the two packets MUST match [27], and
- If either packet contains a DSR Source Route header, both packets - If either packet contains a DSR Source Route header, both packets
MUST contain one, and the value in the Segments Left field in the MUST contain one, and the value in the Segments Left field in the
DSR Source Route header of the new packet MUST be less than that DSR Source Route header of the new packet MUST be less than that
in the first packet. in the first packet.
When a node hears such a passive acknowledgement for any packet in When a node hears such a passive acknowledgment for any packet in its
its Retransmission Buffer, that node SHOULD remove that packet from Maintenance Buffer, that node SHOULD remove that packet, as well as
its Retransmission Buffer, stopping Route Maintenance retransmissions any other packets in its Maintenance Buffer with the same next-hop
for that packet. destination, from its Maintenance Buffer.
6.3.3. Using Network-Layer Acknowledgments 6.3.3. Using Network-Layer Acknowledgments
When a node originates or forwards a packet and has no other When a node originates or forwards a packet and has no other
mechanism of acknowledgement available to determine successful mechanism of acknowledgment available to determine reachability of
delivery of the packet to the next-hop node in the source route the next-hop node in the source route for Route Maintenance, that
for Route Maintenance, that node SHOULD request a network-layer node SHOULD request a network-layer acknowledgment from that next-hop
acknowledgement from that next-hop node. To do so, the node inserts node. To do so, the node inserts an Acknowledgment Request option
an Acknowledgement Request option in the DSR header in the packet. in the DSR header in the packet. The Identification field in that
The Identification field in that Acknowledgement Request option MUST Acknowledgment Request option MUST be set to a value unique over all
be set to a value unique over all packets transmitted by this node packets transmitted by this node to the same next-hop node that are
to the same next-hop node that are either unacknowledged or recently either unacknowledged or recently acknowledged.
acknowledged.
When a node receives a packet containing an Acknowledgement Request When a node receives a packet containing an Acknowledgment Request
option, then that node performs the following tests on the packet: option, then that node performs the following tests on the packet:
- If the indicated next-hop node address for this packet does not - If the indicated next-hop node address for this packet does not
match any of this node's own IP addresses, then this node MUST match any of this node's own IP addresses, then this node MUST
NOT process the Acknowledgement Request option. The indicated NOT process the Acknowledgment Request option. The indicated
next-hop node address is the next Address[i] field in the DSR next-hop node address is the next Address[i] field in the DSR
Source Route option in the DSR header in the packet, or is the IP Source Route option in the DSR header in the packet, or is the IP
Destination Address in the packet if the packet does not contain Destination Address in the packet if the packet does not contain
a DSR Source Route option or the Segments Left there is zero. a DSR Source Route option or the Segments Left there is zero.
- If the packet contains an Acknowledgement option, then this node - If the packet contains an Acknowledgment option, then this node
MUST NOT process the Acknowledgement Request option. MUST NOT process the Acknowledgment Request option.
If neither of the tests above fails, then this node MUST process the If neither of the tests above fails, then this node MUST process the
Acknowledgement Request option by sending an Acknowledgement option Acknowledgment Request option by sending an Acknowledgment option
to the previous-hop node; to do so, the node performs the following to the previous-hop node; to do so, the node performs the following
sequence of steps: sequence of steps:
- Create a packet and set the IP Protocol field to the protocol - Create a packet and set the IP Protocol field to the protocol
number assigned for a DSR header (TBA???). number assigned for a DSR header (TBA???).
- Set the IP Source Address field in this packet to the IP address - Set the IP Source Address field in this packet to the IP address
of this node, copied from the source route in the DSR Source of this node, copied from the source route in the DSR Source
Route option in that packet (or from the IP Destination Address Route option in that packet (or from the IP Destination Address
field of the packet, if the packet does not contain a DSR Source field of the packet, if the packet does not contain a DSR Source
skipping to change at page 60, line 42 skipping to change at page 60, line 45
- Set the IP Destination Address field in this packet to the IP - Set the IP Destination Address field in this packet to the IP
address of the previous-hop node, copied from the source route address of the previous-hop node, copied from the source route
in the DSR Source Route option in that packet (or from the IP in the DSR Source Route option in that packet (or from the IP
Source Address field of the packet, if the packet does not Source Address field of the packet, if the packet does not
contain a DSR Source Route option). contain a DSR Source Route option).
- Add a DSR header to the packet, and set the DSR header's - Add a DSR header to the packet, and set the DSR header's
Next Header field to the "No Next Header" value. Next Header field to the "No Next Header" value.
- Add an Acknowledgement option to the DSR header in the packet; - Add an Acknowledgment option to the DSR header in the packet;
set the Acknowledgement option's Option Type field to 6 and the set the Acknowledgment option's Option Type field to 6 and the
Opt Data Len field to 10. Opt Data Len field to 10.
- Copy the Identification field from the received Acknowledgement - Copy the Identification field from the received Acknowledgment
Request option into the Identification field in the Request option into the Identification field in the
Acknowledgement option. Acknowledgment option.
- Set the ACK Source Address field in the Acknowledgement option to - Set the ACK Source Address field in the Acknowledgment option to
be the IP Source Address of this new packet (set above to be the be the IP Source Address of this new packet (set above to be the
IP address of this node). IP address of this node).
- Set the ACK Destination Address field in the Acknowledgement - Set the ACK Destination Address field in the Acknowledgment
option to be the IP Destination Address of this new packet (set option to be the IP Destination Address of this new packet (set
above to be the IP address of the previous-hop node). above to be the IP address of the previous-hop node).
- Send the packet as described in Section 6.1.1. - Send the packet as described in Section 6.1.1.
Packets containing an Acknowledgement option SHOULD NOT be Packets containing an Acknowledgment option SHOULD NOT be placed in
retransmitted by intermediate nodes for Route Maintenance, and SHOULD the Maintenance Buffer.
NOT expect a link-layer acknowledgement or passive acknowledgment.
When a node receives a packet with both an Acknowledgement option When a node receives a packet with both an Acknowledgment option and
and an Acknowledgement Request option, if that node is not the an Acknowledgment Request option, if that node is not the destination
destination of the Acknowledgement option (the IP Destination Address of the Acknowledgment option (the IP Destination Address of the
of the packet), then the Acknowledgement Request option MUST packet), then the Acknowledgment Request option MUST be ignored.
be ignored. Otherwise (that node is the destination of the Otherwise (that node is the destination of the Acknowledgment
Acknowledgement option), that node MUST process the Acknowledgement option), that node MUST process the Acknowledgment Request option
Request option by returning an Acknowledgement option according to by returning an Acknowledgment option according to the following
the following sequence of steps: sequence of steps:
- Create a packet and set the IP Protocol field to the protocol - Create a packet and set the IP Protocol field to the protocol
number assigned for a DSR header (TBA???). number assigned for a DSR header (TBA???).
- Set the IP Source Address field in this packet to the IP address - Set the IP Source Address field in this packet to the IP address
of this node, copied from the source route in the DSR Source of this node, copied from the source route in the DSR Source
Route option in that packet (or from the IP Destination Address Route option in that packet (or from the IP Destination Address
field of the packet, if the packet does not contain a DSR Source field of the packet, if the packet does not contain a DSR Source
Route option). Route option).
- Set the IP Destination Address field in this packet to the IP - Set the IP Destination Address field in this packet to the IP
address of the node originating the Acknowledgement option. address of the node originating the Acknowledgment option.
- Add a DSR header to the packet, and set the DSR header's - Add a DSR header to the packet, and set the DSR header's
Next Header field to the "No Next Header" value. Next Header field to the "No Next Header" value.
- Add an Acknowledgement option to the DSR header in this packet; - Add an Acknowledgment option to the DSR header in this packet;
set the Acknowledgement option's Option Type field to 6 and the set the Acknowledgment option's Option Type field to 6 and the
Opt Data Len field to 10. Opt Data Len field to 10.
- Copy the Identification field from the received Acknowledgement - Copy the Identification field from the received Acknowledgment
Request option into the Identification field in the Request option into the Identification field in the
Acknowledgement option. Acknowledgment option.
- Set the ACK Source Address field in the option to be the IP - Set the ACK Source Address field in the option to be the IP
Source Address of this new packet (set above to be the IP address Source Address of this new packet (set above to be the IP address
of this node). of this node).
- Set the ACK Destination Address field in the option to be the IP - Set the ACK Destination Address field in the option to be the IP
Destination Address of this new packet (set above to be the IP Destination Address of this new packet (set above to be the IP
address of the node originating the Acknowledgement option.) address of the node originating the Acknowledgment option.)
- Send the packet directly to the destination. The IP - Send the packet directly to the destination. The IP
Destination Address MUST be treated as a direct neighbor node: Destination Address MUST be treated as a direct neighbor node:
the transmission to that node MUST be done in a single IP the transmission to that node MUST be done in a single IP
forwarding hop, without Route Discovery and without searching forwarding hop, without Route Discovery and without searching
the Route Cache. In addition, this packet MUST NOT contain a the Route Cache. In addition, this packet MUST NOT contain a
DSR Acknowledgement Request, MUST NOT be retransmitted for Route DSR Acknowledgment Request, MUST NOT be retransmitted for Route
Maintenance, and MUST NOT expect a link-layer acknowledgement or Maintenance, and MUST NOT expect a link-layer acknowledgment or
passive acknowledgment. passive acknowledgment.
When using network-layer acknowledgements for Route Maintenance, When using network-layer acknowledgments for Route Maintenance,
a node SHOULD use an adaptive algorithm in determining the a node SHOULD use an adaptive algorithm in determining the
retransmission timeout for each transmission attempt of a packet. retransmission timeout for each transmission attempt of an
For example, a node SHOULD maintain a separate round-trip time (RTT) acknowledgment request. For example, a node SHOULD maintain a
estimate for each to which it has recently attempted to transmit separate round-trip time (RTT) estimate for each to which it has
packets, and it SHOULD use this RTT estimate in setting the timeout recently attempted to transmit packets, and it SHOULD use this RTT
for each retransmission attempt for Route Maintenance. The TCP RTT estimate in setting the timeout for each retransmission attempt
estimation algorithm has been shown to work well for this purpose in for Route Maintenance. The TCP RTT estimation algorithm has been
implementation and testbed experiments with DSR [20, 22]. shown to work well for this purpose in implementation and testbed
experiments with DSR [20, 22].
6.3.4. Originating a Route Error 6.3.4. Originating a Route Error
When a node is unable to verify successful delivery of a packet to When a node is unable to verify reachability of a next-hop node after
the next-hop node after reaching a maximum number of retransmission reaching a maximum number of retransmission attempts, a node SHOULD
attempts, a node SHOULD send a Route Error to the IP Source Address send a Route Error to the IP Source Address of the packet. When
of the packet. When sending a Route Error for a packet containing sending a Route Error for a packet containing either a Route Error
either a Route Error option or an Acknowledgement option, a node option or an Acknowledgment option, a node SHOULD add these existing
SHOULD add these existing options to its Route Error, subject to the options to its Route Error, subject to the limit described below.
limit described below.
A node transmitting a Route Error MUST perform the following steps: A node transmitting a Route Error MUST perform the following steps:
- Create an IP packet and set the Source Address field in this - Create an IP packet and set the Source Address field in this
packet's IP header to the address of this node. packet's IP header to the address of this node.
- If the Salvage field in the DSR Source Route option in the - If the Salvage field in the DSR Source Route option in the
packet triggering the Route Error is zero, then copy the packet triggering the Route Error is zero, then copy the
Source Address field of the packet triggering the Route Error Source Address field of the packet triggering the Route Error
into the Destination Address field in the new packet's IP into the Destination Address field in the new packet's IP
skipping to change at page 63, line 9 skipping to change at page 63, line 15
- Add a Route Error Option to the new packet, setting the Error - Add a Route Error Option to the new packet, setting the Error
Type to NODE_UNREACHABLE, the Salvage value to the Salvage Type to NODE_UNREACHABLE, the Salvage value to the Salvage
value from the DSR Source Route option of the packet triggering value from the DSR Source Route option of the packet triggering
the Route Error, and the Unreachable Node Address field to the Route Error, and the Unreachable Node Address field to
the address of the next-hop node from the original source the address of the next-hop node from the original source
route. Set the Error Source Address field to this node's IP route. Set the Error Source Address field to this node's IP
address, and the Error Destination field to the new packet's IP address, and the Error Destination field to the new packet's IP
Destination Address. Destination Address.
- If the packet triggering the Route Error contains any Route Error - If the packet triggering the Route Error contains any Route Error
or Acknowledgement options, the node MAY append to its Route or Acknowledgment options, the node MAY append to its Route Error
Error each of these options, with the following constraints: each of these options, with the following constraints:
o The node MUST NOT include any Route Error option from the o The node MUST NOT include any Route Error option from the
packet triggering the new Route Error, for which the total packet triggering the new Route Error, for which the total
salvage count (Section 5.4) of that included Route Error salvage count (Section 5.4) of that included Route Error
would be greater than MAX_SALVAGE_COUNT in the new packet. would be greater than MAX_SALVAGE_COUNT in the new packet.
o If any Route Error option from the packet triggering the new o If any Route Error option from the packet triggering the new
Route Error is not included in the packet, the node MUST NOT Route Error is not included in the packet, the node MUST NOT
include any following Route Error or Acknowledgement options include any following Route Error or Acknowledgment options
from the packet triggering the new Route Error. from the packet triggering the new Route Error.
o Any appended options from the packet triggering the Route o Any appended options from the packet triggering the Route
Error MUST follow the new Route Error in the packet. Error MUST follow the new Route Error in the packet.
o In appending these options to the new Route Error, the order o In appending these options to the new Route Error, the order
of these options from the packet triggering the Route Error of these options from the packet triggering the Route Error
MUST be preserved. MUST be preserved.
- Send the packet as described in Section 6.1.1. - Send the packet as described in Section 6.1.1.
skipping to change at page 63, line 46 skipping to change at page 63, line 52
- The node MUST remove from its Route Cache the link from the - The node MUST remove from its Route Cache the link from the
node identified by the Error Source Address field to the node node identified by the Error Source Address field to the node
identified by the Unreachable Node Address field (if this link is identified by the Unreachable Node Address field (if this link is
present in its Route Cache). If the node implements its Route present in its Route Cache). If the node implements its Route
Cache as a link cache, as described in Section 4.1, only this Cache as a link cache, as described in Section 4.1, only this
single link is removed; if the node implements its Route Cache as single link is removed; if the node implements its Route Cache as
a path cache, however, all routes (paths) that use this link are a path cache, however, all routes (paths) that use this link are
removed. removed.
- If the option following the Route Error is an Acknowledgement - If the option following the Route Error is an Acknowledgment
or Route Error option sent by this node (that is, with or Route Error option sent by this node (that is, with
Acknowledgement or Error Source Address equal to this node's Acknowledgment or Error Source Address equal to this node's
address), copy the DSR options following the current Route address), copy the DSR options following the current Route Error
Error into a new packet with IP Source Address equal to this into a new packet with IP Source Address equal to this node's own
node's own IP address and IP Destination Address equal to the IP address and IP Destination Address equal to the Acknowledgment
Acknowledgement or Error Destination Address. Transmit this or Error Destination Address. Transmit this packet as described
packet as described in Section 6.1.1, with the salvage count in Section 6.1.1, with the salvage count in the DSR Source Route
in the DSR Source Route option set to the Salvage value of the option set to the Salvage value of the Route Error.
Route Error.
In addition, after processing the Route Error as described above, In addition, after processing the Route Error as described above,
the node MAY initiate a new Route Discovery for any destination node the node MAY initiate a new Route Discovery for any destination node
for which it then has no route in its Route Cache as a result of for which it then has no route in its Route Cache as a result of
processing this Route Error, if the node has indication that a route processing this Route Error, if the node has indication that a route
to that destination is needed. For example, if the node has an open to that destination is needed. For example, if the node has an open
TCP connection to some destination node, then if the processing of TCP connection to some destination node, then if the processing of
this Route Error removed the only route to that destination from this this Route Error removed the only route to that destination from this
node's Route Cache, then this node MAY initiate a new Route Discovery node's Route Cache, then this node MAY initiate a new Route Discovery
for that destination node. Any node, however, MUST limit the rate at for that destination node. Any node, however, MUST limit the rate at
skipping to change at page 64, line 31 skipping to change at page 64, line 35
6.3.6. Salvaging a Packet 6.3.6. Salvaging a Packet
When an intermediate node forwarding a packet detects through Route When an intermediate node forwarding a packet detects through Route
Maintenance that the next-hop link along the route for that packet is Maintenance that the next-hop link along the route for that packet is
broken (Section 6.3), if the node has another route to the packet's broken (Section 6.3), if the node has another route to the packet's
IP Destination Address in its Route Cache, the node SHOULD "salvage" IP Destination Address in its Route Cache, the node SHOULD "salvage"
the packet rather than discarding it. To do so using the route found the packet rather than discarding it. To do so using the route found
in its Route Cache, this node processes the packet as follows: in its Route Cache, this node processes the packet as follows:
- If the MAC protocol in use in the network is not capable of - If the MAC protocol in use in the network is not capable of
transmitting unicast packets over uni-directional links, as transmitting unicast packets over unidirectional links, as
discussed in Section 3.3.1, then if this packet contains a Route discussed in Section 3.3.1, then if this packet contains a Route
Reply option, remove and discard the Route Reply option in the Reply option, remove and discard the Route Reply option in the
packet; if the DSR header in the packet then contains no DSR packet; if the DSR header in the packet then contains no DSR
options, remove the DSR header from the packet. If the resulting options, remove the DSR header from the packet. If the resulting
packet then contains only an IP header, the node SHOULD NOT packet then contains only an IP header, the node SHOULD NOT
salvage the packet and instead SHOULD discard the entire packet. salvage the packet and instead SHOULD discard the entire packet.
When returning any Route Reply in the case in which the MAC When returning any Route Reply in the case in which the MAC
protocol in use in the network is not capable of transmitting protocol in use in the network is not capable of transmitting
unicast packets over uni-directional links, the source route unicast packets over unidirectional links, the source route
used for routing the Route Reply packet MUST be obtained by used for routing the Route Reply packet MUST be obtained by
reversing the sequence of hops in the Route Request packet (the reversing the sequence of hops in the Route Request packet (the
source route that is then returned in the Route Reply). This source route that is then returned in the Route Reply). This
restriction on returning a Route Reply and on salvaging a packet restriction on returning a Route Reply and on salvaging a packet
that contains a Route Reply option enables the Route Reply to that contains a Route Reply option enables the Route Reply to
test this sequence of hops for bi-directionality, preventing the test this sequence of hops for bidirectionality, preventing the
Route Reply from being received by the initiator of the Route Route Reply from being received by the initiator of the Route
Discovery unless each of the hops over which the Route Reply is Discovery unless each of the hops over which the Route Reply is
returned (and thus each of the hops in the source route being returned (and thus each of the hops in the source route being
returned in the Reply) is bi-directional. returned in the Reply) is bidirectional.
- Modify the existing DSR Source Route option in the packet so - Modify the existing DSR Source Route option in the packet so
that the Address[i] fields represent the source route found in that the Address[i] fields represent the source route found in
this node's Route Cache to this packet's IP Destination Address. this node's Route Cache to this packet's IP Destination Address.
Specifically, the node copies the hop addresses of the source Specifically, the node copies the hop addresses of the source
route into sequential Address[i] fields in the DSR Source Route route into sequential Address[i] fields in the DSR Source Route
option, for i = 1, 2, ..., n. Address[1] here is the address option, for i = 1, 2, ..., n. Address[1] here is the address
of the salvaging node itself (the first address in the source of the salvaging node itself (the first address in the source
route found from this node to the IP Destination Address of the route found from this node to the IP Destination Address of the
packet). The value n here is the number of hop addresses in this packet). The value n here is the number of hop addresses in this
skipping to change at page 66, line 5 skipping to change at page 66, line 5
- Transmit the packet to the next-hop node on the new source route - Transmit the packet to the next-hop node on the new source route
in the packet, using the forwarding procedure described in in the packet, using the forwarding procedure described in
Section 6.1.5. Section 6.1.5.
As described in Section 6.3.4, the node in this case also SHOULD As described in Section 6.3.4, the node in this case also SHOULD
return a Route Error to the original sender of the packet. If the return a Route Error to the original sender of the packet. If the
node chooses to salvage the packet, it SHOULD do so after originating node chooses to salvage the packet, it SHOULD do so after originating
the Route Error. the Route Error.
7. Protocol Constants and Configuration Variables 7. Multiple Interface Support
A node in DSR MAY have multiple network interfaces that support
ad hoc network routing. This section describes special packet
processing at such nodes.
A node with multiple network interfaces MUST have some policy for
determining which Request packets are forwarded out which network
interfaces. For example, a node MAY choose to forward all Requests
out all network interfaces.
When a node with multiple network interfaces propagates a Route
Request on an network interface other than the one it received the
Request on, it MUST modify the address list between receipt and
re-propagation as follows:
- Append the address of the incoming interface
- If the incoming interface and outgoing interface differ in
whether or not they require bidirectionality for unicast
transmission, append the address 127.0.0.1
- If the incoming interface and outgoing interface differ in
whether or not unidirectional links are common, append the
address 127.0.0.2
- Append the address of the outgoing interface
When a node forwards a packet containing a source route, it MUST
assume that the next hop is reachable on the incoming interface,
unless the next hop is the address of one of this node's interfaces,
in which case this node MUST process the packet in the same way as if
the node had just received it from that interface.
If a node which previously had multiple network interfaces receives a
packet sent with a source route specifying an interface change to an
interface 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 interface, unless the network uses an autoconfiguration
mechanism that may have allowed another node to acquire the now
unused address of the unavailable interface.
Source routes MUST never contain the special addresses 127.0.0.1 and
127.0.0.2.
8. 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 header from the packet.
- Fragment the packet.
- IP-in-IP encapsulate each fragment.
- Add the DSR header to each fragment. If a Source Route header is
present in the DSR 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 and
reassemble any fragments contained inside, in accordance with
RFC 791 [27].
9. Protocol Constants and Configuration Variables
Any DSR implementation MUST support the following configuration Any DSR implementation MUST support the following configuration
variables and MUST support a mechanism enabling the value of these variables and MUST support a mechanism enabling the value of these
variables to be modified by system management. The specific variable variables to be modified by system management. The specific variable
names are used for demonstration purposes only, and an implementation names are used for demonstration purposes only, and an implementation
is not required to use these names for the configuration variables, is not required to use these names for the configuration variables,
so long as the external behavior of the implementation is consistent so long as the external behavior of the implementation is consistent
with that described in this document. with that described in this document.
For each configuration variable below, the default value is specified For each configuration variable below, the default value is specified
to simplify configuration. In particular, the default values given to simplify configuration. In particular, the default values given
below are chosen for a DSR network running over 2 Mbps IEEE 802.11 below are chosen for a DSR network running over 2 Mbps IEEE 802.11
network network interfaces using the Distributed Coordination network interfaces using the Distributed Coordination Function (DCF)
Function (DCF) MAC with RTS and CTS [11, 5]. MAC with RTS and CTS [11, 5].
BroadcastJitter 10 milliseconds BroadcastJitter 10 milliseconds
RouteCacheTimeout 300 seconds RouteCacheTimeout 300 seconds
SendBufferTimeout 30 seconds SendBufferTimeout 30 seconds
RequestTableSize 64 nodes RequestTableSize 64 nodes
RequestTableIds 16 identifiers RequestTableIds 16 identifiers
MaxRequestRexmt 16 retransmissions MaxRequestRexmt 16 retransmissions
MaxRequestPeriod 10 seconds MaxRequestPeriod 10 seconds
RequestPeriod 500 milliseconds RequestPeriod 500 milliseconds
NonpropRequestTimeout 30 milliseconds NonpropRequestTimeout 30 milliseconds
RexmtBufferSize 50 packets RexmtBufferSize 50 packets
MaintHoldoffTime 250 milliseconds
MaxMaintRexmt 2 retransmissions MaxMaintRexmt 2 retransmissions
TryPassiveAcks 1 attempt TryPassiveAcks 1 attempt
PassiveAckTimeout 100 milliseconds PassiveAckTimeout 100 milliseconds
GratReplyHoldoff 1 second GratReplyHoldoff 1 second
In addition, the following protocol constant MUST be supported by any In addition, the following protocol constant MUST be supported by any
implementation of the DSR protocol: implementation of the DSR protocol:
MAX_SALVAGE_COUNT 15 salvages MAX_SALVAGE_COUNT 15 salvages
8. IANA Considerations 10. IANA Considerations
This document proposes the use of a DSR header, which requires an IP This document proposes the use of a DSR header, which requires an IP
Protocol number. Protocol number.
In addition, this document proposes use of the value "No Next Header" In addition, this document proposes use of the value "No Next Header"
(originally defined for use in IPv6) within an IPv4 packet, to (originally defined for use in IPv6) within an IPv4 packet, to
indicate that no further header follows a DSR header. indicate that no further header follows a DSR header.
9. Security Considerations 11. Security Considerations
This document does not specifically address security concerns. This This document does not specifically address security concerns. This
document does assume that all nodes participating in the DSR protocol document does assume that all nodes participating in the DSR protocol
do so in good faith and without malicious intent to corrupt the do so in good faith and without malicious intent to corrupt the
routing ability of the network. In mission-oriented environments routing ability of the network. In mission-oriented environments
where all the nodes participating in the DSR protocol share a where all the nodes participating in the DSR protocol share a
common goal that motivates their participation in the protocol, the common goal that motivates their participation in the protocol, the
communications between the nodes can be encrypted at the physical communications between the nodes can be encrypted at the physical
channel or link layer to prevent attack by outsiders. channel or link layer to prevent attack by outsiders.
skipping to change at page 69, line 43 skipping to change at page 71, line 43
is chosen according to a "Stability Table" maintained by the caching is chosen according to a "Stability Table" maintained by the caching
node. Each entry in a node's Stability Table records the address of node. Each entry in a node's Stability Table records the address of
another node and a factor representing the perceived "stability" of another node and a factor representing the perceived "stability" of
this node. The stability of each other node in a node's Stability this node. The stability of each other node in a node's Stability
Table is initialized to InitStability. When a link from the Route Table is initialized to InitStability. When a link from the Route
Cache is used in routing a packet originated or salvaged by that 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 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 link is incremented by the amount of time since that link was last
used, multiplied by StabilityIncrFactor (StabilityIncrFactor >= 1); used, multiplied by StabilityIncrFactor (StabilityIncrFactor >= 1);
when a link is observed to break and the link is thus removed when a link is observed to break and the link is thus removed
from the Route Cache (either due the receipt of a Route Error for from the Route Cache, the stability metric for each of the two
this link or due to exceeding the maximum number of retransmission
attempts for Route Maintenance for a packet being originated or
forwarded by this node), the stability metric for each of the two
endpoint nodes of that link is multiplied by StabilityDecrFactor endpoint nodes of that link is multiplied by StabilityDecrFactor
(StabilityDecrFactor < 1). (StabilityDecrFactor < 1).
When a node adds a new link to its Route Cache, the node assigns a 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 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 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. 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 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 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 UseExtends into the future; if the lifetime of that link in the
skipping to change at page 72, line 47 skipping to change at page 74, line 47
we have also added a preliminary version of Quality of Service (QoS) we have also added a preliminary version of Quality of Service (QoS)
support for DSR. A demonstration of this modified version of DSR was support for DSR. A demonstration of this modified version of DSR was
presented in July 2000. These QoS features are not included in this presented in July 2000. These QoS features are not included in this
draft, and will be added later in a separate draft on top of the base draft, and will be added later in a separate draft on top of the base
protocol specified here. protocol specified here.
DSR has also been implemented under Linux by Alex Song at the DSR has also been implemented under Linux by Alex Song at the
University of Queensland, Australia [31]. This implementation University of Queensland, Australia [31]. This implementation
supports the Intel x86 PC platform and the Compaq iPAQ. 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.
Several other independent groups have also used DSR as a platform for Several other independent groups have also used DSR as a platform for
their own research, or and as a basis of comparison between ad hoc their own research, or and as a basis of comparison between ad hoc
network routing protocols. network routing protocols.
Changes from Previous Version of the Draft Changes from Previous Version of the Draft
This appendix briefly lists some of the major changes in this This appendix briefly lists some of the major changes in this
draft relative to the previous version of this same draft, draft relative to the previous version of this same draft,
draft-ietf-manet-dsr-05.txt: draft-ietf-manet-dsr-06.txt:
- Clarified how to handle Route Maintenance at the original sender
of a packet, which is slightly different than at an intermediate
node forwarding the packet.
- In the definition of the Route Cache in Section 4.1, if there
are multiple cached routes to a destination, a node MUST prefer
routes that do not have the External flag set on any link; this
restriction was previously specified as a "SHOULD". This change
does not affect the operation of DSR with respect to this draft,
since the use of external links is outside the scope of this
draft.
- Clarified that the Retransmission Buffer MAY be of limited size,
and that when adding a new packet to the Retransmission Buffer,
if the buffer size is insufficient to hold the new packet, the
new packet SHOULD be silently discarded.
- Changed the calculation of the Salvage field in a Route
Error option and the total salvage count of an option to not
explicitely increment the count when the count is copied from a
DSR Source Route option into a new Route Error option. Instead,
the increment is implicit in the value of the Salvage field
and is added in when the total salvage count of an option is
calculated.
- In Section 5.2, corrected the specification of the number of
Address[i] fields present in a Route Request option. The number
of addresses present is indicated by the Opt Data Len field in
the option as n = (Opt Data Len - 6) / 4.
- In Section 6.1.3, corrected the specification of the steps for
adding a DSR Source Route option to a packet. As described
elsewhere in the draft, the entire source route (excluding the
address of the originating node and the final destination address
of the packet) is copied into the DSR Source Route option, and
the IP Destination Address of the packet is not changed when
inserting the source route.
- Added a specific statement in the abstract and introduction
that this document specifies the operation of DSR only for
IPv4. Operation of DSR with IPv6 [6] will be covered in other
documents.
- Removed the ACK Request Source Address field from the
Acknowledgement Request option, as this field was not used in
standard DSR; instead, the address of the node requesting a DSR
Acknowledgement is obtained as the previous-hop address of the
source route in the packet. This field is, however, used in the
"flow state" enhancement to DSR [10] and will be specified in
that draft.
- The DSR header was previously specified to always be a multiple
of 4 octet in size; this is now only required if any other
headers follow the DSR header in the packet.
- Clarified the definition of salvaging to be a "SHOULD" rather
than a "MAY".
- Added the definition of the Gratuitous Route Reply Table as a new
conceptual data structure in Section 4.4, and added corresponding
uses of it in the detailed operation. This data structure and
its use have always been a part of the DSR simulation but had not
previously been documented in the draft.
- Removed the Identification field from the definition of a Route
Reply option since it was not used in the protocol.
- Removed the restriction that the value of the Identification
field in an Acknowledgement Request option needed to be nonzero;
the value zero at one time had a special meaning in the protocol
but no longer is used for this purpose.
- Added a description of a specific possible implementation of the
Route Cache data structure, called "Link-MaxLife", in Appendix A.
The actual choice of data structure implementation to use for
the Route Cache in any DSR implementation is a local matter
for each node and affects only performance, not correctness or
interoperability; the Link-MaxLife cache, however, has been
studied extensively and been shown to outperform other types of
cache implementations studied in detailed simulation [9], and its
use in DSR implementations is recommended.
- Changed most of the protocol constants to now be configuration
variables, which MUST support a mechanism enabling the value of
these variables to be modified by system management. Also, to
be clear in the specification which values are variables now and
which are constants, changed the names of all variables to be in
MixedCase instead of ALL_CAPS.
- Changed name of the constant MAX_SALVAGE_TIMES to
MAX_SALVAGE_COUNT.
- Changed the name of the variable DsrMaxRxtShift to now
be MaxMaintRexmt. Also changed the name of the variable
DsrRxmtBufferSize to now be RexmtBufferSize.
- Clarified the description of what to add to a node's Route Cache
in response to different options in the DSR header of a received
packet, and coalesced this description into Section 6.1.4.
- In Section 6.3.5, added a suggestion that a node, after - Added a blacklist mechanism for handling unidirectional links
processing a Route Error, MAY initiate a new Route Discovery for when the network interface requires bidirectionality.
any destination node for which it then has no route in its Route
Cache as a result of processing this Route Error, if the node has
indication that a route to that destination is needed (e.g., an
open TCP connection). Such Route Discoveries MUST conform to the
standard rate limiting for Route Discoveries.
- Clarified the retransmission timing for Route Maintenance - Added language describing multiple interface support.
retransmissions, in Section 6.3.
- Updated the implementation and evaluation description in - Described fragmentation and reassembly processing.
Appendix C to include mention of the implementation of DSR under
Linux by Alex Song at the University of Queensland, Australia.
This implementation supports the Intel x86 PC platform and the
Compaq iPAQ.
- Changed the status of the document to indicate full conformance - Updated the implementation and evaluation list.
with all provisions of Section 10 of RFC 2026.
Acknowledgements Acknowledgements
The protocol described in this draft has been designed and developed The protocol described in this draft has been designed and developed
within the Monarch Project, a research project at Rice University within the Monarch Project, a research project at Rice University
(previously at Carnegie Mellon University) that is developing (previously at Carnegie Mellon University) that is developing
adaptive networking protocols and protocol interfaces to allow truly adaptive networking protocols and protocol interfaces to allow truly
seamless wireless and mobile node networking [15, 30]. seamless wireless and mobile node networking [15, 30].
The authors would like to acknowledge the substantial contributions The authors would like to acknowledge the substantial contributions
of Josh Broch in helping to design, simulate, and implement the DSR of Josh Broch in helping to design, simulate, and implement the DSR
protocol. Josh is currently on leave of absence from Carnegie Mellon protocol. Josh is currently on leave of absence from Carnegie Mellon
University at AON Networks. We thank him for his contributions to University at AON Networks. We thank him for his contributions to
earlier versions of this draft. earlier versions of this draft.
We would also like to acknowledge the assistance of Robert V. Barron We would also like to acknowledge the assistance of Robert V. Barron
at Carnegie Mellon University. Bob ported our DSR implementation at Carnegie Mellon University. Bob ported our DSR implementation
from FreeBSD 2.2.7 into FreeBSD 3.3. from FreeBSD 2.2.7 into FreeBSD 3.3.
Many valuable suggestions came from participants in the IETF process.
We would like to acknowledge Fred Baker, who provided extensive
feedback on our previous draft, as well as the working group chairs,
for their suggestions of previous versions of the draft.
References References
[1] David F. Bantz and Frederic J. Bauchot. Wireless LAN Design [1] David F. Bantz and Frederic J. Bauchot. Wireless LAN Design
Alternatives. IEEE Network, 8(2):43--53, March/April 1994. Alternatives. IEEE Network, 8(2):43--53, March/April 1994.
[2] Vaduvur Bharghavan, Alan Demers, Scott Shenker, and Lixia [2] Vaduvur Bharghavan, Alan Demers, Scott Shenker, and Lixia
Zhang. MACAW: A Media Access Protocol for Wireless LAN's. In Zhang. MACAW: A Media Access Protocol for Wireless LAN's. In
Proceedings of the ACM SIGCOMM '94 Conference, pages 212--225, Proceedings of the ACM SIGCOMM '94 Conference, pages 212--225,
August 1994. August 1994.
 End of changes. 

This html diff was produced by rfcdiff 1.23, available from http://www.levkowetz.com/ietf/tools/rfcdiff/