RFC 4728
The Dynamic Source Routing Protocol (DSR) for Mobile Ad Hoc Networks for IPv4
7. Additional Header Formats and Options for Flow State Extension
The optional DSR flow state extension requires a new header type, the DSR Flow State header. In addition, the DSR flow state extension adds the following options for the DSR Options header defined in Section 6: - Timeout option (Section 7.2.1) - Destination and Flow ID option (Section 7.2.2) Two new Error Type values are also defined for use in the Route Error option in a DSR Options header: - UNKNOWN_FLOW - DEFAULT_FLOW_UNKNOWN Finally, an extension to the Acknowledgement Request option in a DSR Options header is also defined:
- Previous Hop Address This section defines each of these new header, option, or extension formats.7.1. DSR Flow State Header
The DSR Flow State header is a small 4-byte header optionally used to carry the flow ID and hop count for a packet being sent along a DSR flow. It is distinguished from the fixed DSR Options header (Section 6.1) in that the Flow State Header (F) bit is set in the DSR Flow State header and is clear in the fixed DSR Options header. 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Next Header |F| Hop Count | Flow Identifier | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Next Header 8-bit selector. Identifies the type of header immediately following the DSR Flow State header. Uses the same values as the IPv4 Protocol field [RFC1700]. Flow State Header (F) Flag bit. MUST be set to 1. This bit is set in a DSR Flow State header and clear in a DSR Options header (Section 6.1). Hop Count 7-bit unsigned integer. The number of hops through which this packet has been forwarded. Flow Identification The flow ID for this flow, as described in Section 3.5.1.7.2. New Options and Extensions in DSR Options Header
7.2.1. Timeout Option
The Timeout option is defined for use in a DSR Options header to indicate the amount of time before the expiration of the flow ID along which the packet is being sent.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len | Timeout |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type
128. Nodes not understanding this option will ignore the
option and return a Route Error.
Opt Data Len
8-bit unsigned integer. Length of the option, in octets,
excluding the Option Type and Opt Data Len fields.
When no extensions are present, the Opt Data Len of a Timeout
option is 2. Further extensions to DSR may include additional
data in a Timeout option. The presence of such extensions is
indicated by an Opt Data Len greater than 2. Currently, no
such extensions have been defined.
Timeout
The number of seconds for which this flow remains valid.
The Timeout option MUST NOT appear more than once within a DSR
Options header.
7.2.2. Destination and Flow ID Option
The Destination and Flow ID option is defined for use in a DSR
Options header to send a packet to an intermediate host along one
flow, for eventual forwarding to the final destination along a
different flow. This option enables the aggregation of the state of
multiple flows.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len | New Flow Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| New IP Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type
129. Nodes not understanding this option will ignore the
option and return a Route Error.
Opt Data Len
8-bit unsigned integer. Length of the option, in octets,
excluding the Option Type and Opt Data Len fields.
When no extensions are present, the Opt Data Len of a
Destination and Flow ID option is 6. Further extensions to DSR
may include additional data in a Destination and Flow ID
option. The presence of such extensions is indicated by an Opt
Data Len greater than 6. Currently, no such extensions have
been defined.
New Flow Identifier
Indicates the next identifier to store in the Flow ID field of
the DSR Options header.
New IP Destination Address
Indicates the next address to store in the Destination Address
field of the IP header.
The Destination and Flow ID option MAY appear one or more times
within a DSR Options header.
7.3. New Error Types for Route Error Option
7.3.1. Unknown Flow Type-Specific Information
A new Error Type value of 129 (UNKNOWN_FLOW) is defined for use in a
Route Error option in a DSR Options header. The Type-Specific
Information for errors of this type is encoded as follows:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Original IP Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Flow ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Original IP Destination Address
The IP Destination Address of the packet that caused the error.
Flow ID
The Flow ID contained in the DSR Flow ID option that caused the
error.
7.3.2. Default Flow Unknown Type-Specific Information
A new Error Type value of 130 (DEFAULT_FLOW_UNKNOWN) is defined
for use in a Route Error option in a DSR Options header. The
Type-Specific Information for errors of this type is encoded as
follows:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Original IP Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Original IP Destination Address
The IP Destination Address of the packet that caused the error.
7.4. New Acknowledgement Request Option Extension
7.4.1. Previous Hop Address Extension
When the Opt Data Len field of an Acknowledgement Request option
in a DSR Options header is greater than or equal to 6, the
ACK Request Source Address field is present. The option is then
formatted as follows:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len | Packet Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ACK Request Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type
160. Nodes not understanding this option will remove the
option and return a Route Error.
Opt Data Len
8-bit unsigned integer. Length of the option, in octets,
excluding the Option Type and Opt Data Len fields.
When no extensions are presents, the Opt Data Len of an
Acknowledgement Request option is 2. Further extensions to DSR
may include additional data in an Acknowledgement Request
option. The presence of such extensions is indicated by an Opt
Data Len greater than 2.
Currently, one such extension has been defined. If the Opt
Data Len is at least 6, then an ACK Request Source Address is
present.
Packet Identifier
The Packet Identifier field is set to a unique number and is
copied into the Identification field of the DSR Acknowledgement
option when returned by the node receiving the packet over this
hop.
ACK Request Source Address
The address of the node requesting the DSR Acknowledgement.
8. Detailed Operation
8.1. General Packet Processing
8.1.1. Originating a Packet
When originating any packet, a node using DSR routing MUST perform
the following sequence of steps:
- Search the node's Route Cache for a route to the address given in
the IP Destination Address field in the packet's header.
- If no such route is found in the Route Cache, then perform Route
Discovery for the Destination Address, as described in Section
8.2. Initiating a Route Discovery for this target node address
results in the node adding a Route Request option in a DSR Options
header in this existing packet, or saving this existing packet to
its Send Buffer and initiating the Route Discovery by sending a
separate packet containing such a Route Request option. If the
node chooses to initiate the Route Discovery by adding the Route
Request option to this existing packet, it will replace the IP
Destination Address field with the IP "limited broadcast" address
(255.255.255.255) [RFC1122], copying the original IP Destination
Address to the Target Address field of the new Route Request
option added to the packet, as described in Section 8.2.1.
- If the packet now does not contain a Route Request option, then
this node must have a route to the Destination Address of the
packet; if the node has more than one route to this Destination
Address, the node selects one to use for this packet. If the
length of this route is greater than 1 hop, or if the node
determines to request a DSR network-layer acknowledgement from the
first-hop node in that route, then insert a DSR Options header
into the packet, as described in Section 8.1.2, and insert a DSR
Source Route option, as described in Section 8.1.3. The source
route in the packet is initialized from the selected route to the
Destination Address of the packet.
- Transmit the packet to the first-hop node address given in
selected source route, using Route Maintenance to determine the
reachability of the next hop, as described in Section 8.3.
8.1.2. Adding a DSR Options Header to a Packet
A node originating a packet adds a DSR Options header to the packet,
if necessary, to carry information needed by the routing protocol. A
packet MUST NOT contain more than one DSR Options header. A DSR
Options header is added to a packet by performing the following
sequence of steps (these steps assume that the packet contains no
other headers that MUST be located in the packet before the DSR
Options header):
- Insert a DSR Options header after the IP header but before any
other header that may be present.
- Set the Next Header field of the DSR Options header to the
Protocol number field of the packet's IP header.
- Set the Protocol field of the packet's IP header to the protocol
number assigned for DSR (48).
8.1.3. Adding a DSR Source Route Option to a Packet
A node originating a packet adds a DSR Source Route option to the
packet, if necessary, in order to carry the source route from this
originating node to the final destination address of the packet.
Specifically, the node adding the DSR Source Route option constructs
the DSR Source Route option and modifies the IP packet according to
the following sequence of steps:
- The node creates a DSR Source Route option, as described in
Section 6.7, and appends it to the DSR Options header in the
packet. (A DSR Options header is added, as described in Section
8.1.2, if not already present.)
- The number of Address[i] fields to include in the DSR Source Route
option (n) is the number of intermediate nodes in the source route
for the packet (i.e., excluding the address of the originating
node and the final destination address of the packet). The
Segments Left field in the DSR Source Route option is initialized
equal to n.
- The addresses within the source route for the packet are copied
into sequential Address[i] fields in the DSR Source Route option,
for i = 1, 2, ..., n.
- The First Hop External (F) bit in the DSR Source Route option is
copied from the External bit flagging the first hop in the source
route for the packet, as indicated in the Route Cache.
- The Last Hop External (L) bit in the DSR Source Route option is
copied from the External bit flagging the last hop in the source
route for the packet, as indicated in the Route Cache.
- The Salvage field in the DSR Source Route option is initialized to
0.
8.1.4. Processing a Received Packet
When a node receives any packet (whether for forwarding, overheard,
or the final destination of the packet), if that packet contains a
DSR Options header, then that node MUST process any options contained
in that DSR Options header, in the order contained there.
Specifically:
- If the DSR Options header contains a Route Request option, the
node SHOULD extract the source route from the Route Request and
add this routing information to its Route Cache, subject to the
conditions identified in Section 3.3.1. The routing information
from the Route Request is the sequence of hop addresses
initiator, Address[1], Address[2], ..., Address[n]
where initiator is the value of the Source Address field in the IP
header of the packet carrying the Route Request (the address of
the initiator of the Route Discovery), and each Address[i] is a
node through which this Route Request has passed, in turn, during
this Route Discovery. The value n, here, is the number of
addresses recorded in the Route Request option, or
(Opt Data Len - 6) / 4.
After possibly updating the node's Route Cache in response to the
routing information in the Route Request option, the node MUST
then process the Route Request option as described in Section
8.2.2.
- If the DSR Options header contains a Route Reply option, the node
SHOULD extract the source route from the Route Reply and add this
routing information to its Route Cache, subject to the conditions
identified in Section 3.3.1. The source route from the Route
Reply is the sequence of hop addresses
initiator, Address[1], Address[2], ..., Address[n]
where initiator is the value of the Destination Address field in
the IP header of the packet carrying the Route Reply (the address
of the initiator of the Route Discovery), and each Address[i] is a
node through which the source route passes, in turn, on the route
to the target of the Route Discovery. Address[n] is the address
of the target. If the Last Hop External (L) bit is set in the
Route Reply, the node MUST flag the last hop from the Route Reply
(the link from Address[n-1] to Address[n]) in its Route Cache as
External. The value n here is the number of addresses in the
source route being returned in the Route Reply option, or
(Opt Data Len - 1) / 4.
After possibly updating the node's Route Cache in response to the
routing information in the Route Reply option, then if the
packet's IP Destination Address matches one of this node's IP
addresses, the node MUST then process the Route Reply option as
described in Section 8.2.6.
- If the DSR Options header contains a Route Error option, the node
MUST process the Route Error option as described in Section 8.3.5.
- If the DSR Options header contains an Acknowledgement Request
option, the node MUST process the Acknowledgement Request option
as described in Section 8.3.3.
- If the DSR Options header contains an Acknowledgement option, then
subject to the conditions identified in Section 3.3.1, the node
SHOULD add to its Route Cache the single link from the node
identified by the ACK Source Address field to the node identified
by the ACK Destination Address field.
After possibly updating the node's Route Cache in response to the
routing information in the Acknowledgement option, the node MUST
then process the Acknowledgement option as described in Section
8.3.3.
- If the DSR Options header contains a DSR Source Route option, the
node SHOULD extract the source route from the DSR Source Route
option and add this routing information to its Route Cache,
subject to the conditions identified in Section 3.3.1. If the
value of the Salvage field in the DSR Source Route option is zero,
then the routing information from the DSR Source Route is the
sequence of hop addresses
source, Address[1], Address[2], ..., Address[n], destination
Otherwise (i.e., if Salvage is nonzero), the routing information
from the DSR Source Route is the sequence of hop addresses
Address[1], Address[2], ..., Address[n], destination
where source is the value of the Source Address field in the IP
header of the packet carrying the DSR Source Route option (the
original sender of the packet), each Address[i] is the value in
the Address[i] field in the DSR Source Route option, and
destination is the value of the Destination Address field in the
packet's IP header (the last-hop address of the source route).
The value n here is the number of addresses in source route in the
DSR Source Route option, or (Opt Data Len - 2) / 4.
After possibly updating the node's Route Cache in response to the
routing information in the DSR Source Route option, the node MUST
then process the DSR Source Route option as described in Section
8.1.5.
- Any Pad1 or PadN options in the DSR Options header are ignored.
- Finally, if the Destination Address in the packet's IP header
matches one of this receiving node's own IP address(es), remove
the DSR Options header and all the included DSR options in the
header, and pass the rest of the packet to the network layer.
8.1.5. Processing a Received DSR Source Route Option
When a node receives a packet containing a DSR Source Route option
(whether for forwarding, overheard, or the final destination of the
packet), that node SHOULD examine the packet to determine if the
receipt of that packet indicates an opportunity for automatic route
shortening, as described in Section 3.4.3. Specifically, if this
node is not the intended next-hop destination for the packet but is
named in the later unexpended portion of the source route in the
packet's DSR Source Route option, then this packet indicates an
opportunity for automatic route shortening: the intermediate nodes
after the node from which this node overheard the packet and before
this node itself are no longer necessary in the source route. In
this case, this node SHOULD perform the following sequence of steps
as part of automatic route shortening:
- The node searches its Gratuitous Route Reply Table for an entry
describing a gratuitous Route Reply earlier sent by this node, for
which the original sender (of the packet triggering the gratuitous
Route Reply) and the transmitting node (from which this node
overheard that packet in order to trigger the gratuitous Route
Reply) both match the respective node addresses for this new
received packet. If such an entry is found in the node's
Gratuitous Route Reply Table, the node SHOULD NOT perform
automatic route shortening in response to this receipt of this
packet.
- Otherwise, the node creates an entry for this overheard packet in
its Gratuitous Route Reply Table. The timeout value for this new
entry SHOULD be initialized to the value GratReplyHoldoff. After
this timeout has expired, the node SHOULD delete this entry from
its Gratuitous Route Reply Table.
- After creating the new Gratuitous Route Reply Table entry above,
the node originates a gratuitous Route Reply to the IP Source
Address of this overheard packet, as described in Section 3.4.3.
If the MAC protocol in use in the network is not capable of
transmitting unicast packets over unidirectional links, as
discussed in Section 3.3.1, then in originating this Route Reply,
the node MUST use a source route for routing the Route Reply
packet that is obtained by reversing the sequence of hops over
which the packet triggering the gratuitous Route Reply was routed
in reaching and being overheard by this node. This reversing of
the route uses the gratuitous Route Reply to test this sequence of
hops for bidirectionality, preventing the gratuitous Route Reply
from being received by the initiator of the Route Discovery unless
each of the hops over which the gratuitous Route Reply is returned
is bidirectional.
- Discard the overheard packet, since the packet has been received
before its normal traversal of the packet's source route would
have caused it to reach this receiving node. Another copy of the
packet will normally arrive at this node as indicated in the
packet's source route; discarding this initial copy of the packet,
which triggered the gratuitous Route Reply, will prevent the
duplication of this packet that would otherwise occur.
If the packet is not discarded as part of automatic route shortening
above, then the node MUST process the Source Route option according
to the following sequence of steps:
- If the value of the Segments Left field in the DSR Source Route
option equals 0, then remove the DSR Source Route option from the
DSR Options header.
- Else, let n equal (Opt Data Len - 2) / 4. This is the number of
addresses in the DSR Source Route option.
- If the value of the Segments Left field is greater than n, then
send an ICMP Parameter Problem, Code 0, message [RFC792] to the IP
Source Address, pointing to the Segments Left field, and discard
the packet. Do not process the DSR Source Route option further.
- Else, decrement the value of the Segments Left field by 1. Let i
equal n minus Segments Left. This is the index of the next
address to be visited in the Address vector.
- If Address[i] or the IP Destination Address is a multicast
address, then discard the packet. Do not process the DSR Source
Route option further.
- If this node has more than one network interface and if Address[i]
is the address of one this node's network interfaces, then this
indicates a change in the network interface to use in forwarding
the packet, as described in Section 8.4. In this case, decrement
the value of the Segments Left field by 1 to skip over this
address (that indicated the change of network interface) and go to
the first step above (checking the value of the Segments Left
field) to continue processing this Source Route option; in further
processing of this Source Route option, the indicated new network
interface MUST be used in forwarding the packet.
- If the MTU of the link over which this node would transmit the
packet to forward it to the node Address[i] is less than the size
of the packet, the node MUST either discard the packet and send an
ICMP Packet Too Big message to the packet's Source Address
[RFC792] or fragment it as specified in Section 8.5.
- Forward the packet to the IP address specified in the Address[i]
field of the IP header, following normal IP forwarding procedures,
including checking and decrementing the Time-to-Live (TTL) field
in the packet's IP header [RFC791, RFC1122]. In this forwarding
of the packet, the next-hop node (identified by Address[i]) MUST
be treated as a direct neighbor node: the transmission to that
next node MUST be done in a single IP forwarding hop, without
Route Discovery and without searching the Route Cache.
- In forwarding the packet, perform Route Maintenance for the next
hop of the packet, by verifying that the next-hop node is
reachable, as described in Section 8.3.
Multicast addresses MUST NOT appear in a DSR Source Route option or
in the IP Destination Address field of a packet carrying a DSR Source
Route option in a DSR Options header.
8.1.6. Handling an Unknown DSR Option
Nodes implementing DSR MUST handle all options specified in this
document, except those options pertaining to the optional flow state
extension (Section 7). However, further extensions to DSR may
include other option types that may not be understood by
implementations conforming to this version of the DSR specification.
In DSR, Option Type codes encode required behavior for nodes not
implementing that type of option. These behaviors are included in
the most significant 3 bits of the Option Type.
If the most significant bit of the Option Type is set (that is,
Option Type & 0x80 is nonzero), and this packet does not contain a
Route Request option, a node SHOULD return a Route Error to the IP
Source Address, following the steps described in Section 8.3.4,
except that the Error Type MUST be set to OPTION_NOT_SUPPORTED and
the Unsupported Opt field MUST be set to the Option Type triggering
the Route Error.
Whether or not a Route Error is sent in response to this DSR option,
as described above, the node also MUST examine the next 2 most
significant bits (that is, Option Type & 0x60):
- When these 2 bits are 00 (that is, Option Type & 0x60 == 0), a
node not implementing processing for that Option Type MUST use the
Opt Data Len field to skip over the option and continue
processing.
- When these 2 bits are 01 (that is, Option Type & 0x60 == 0x20), a
node not implementing processing for that Option Type MUST use the
Opt Data Len field to remove the option from the packet and
continue processing as if the option had not been included in the
received packet.
- When these 2 bits are 10 (that is, Option Type & 0x60 == 0x40), a
node not implementing processing for that Option Type MUST set the
most significant bit following the Opt Data Len field. In
addition, the node MUST then ignore and skip over the contents of
the option using the Opt Data Len field and MUST continue
processing the packet.
- Finally, when these 2 bits are 11 (that is,
Option Type & 0x60 == 0x60), a node not implementing processing
for that Option Type MUST drop the packet.
8.2. Route Discovery Processing
Route Discovery is the mechanism by which a node S wishing to send a
packet to a destination node D obtains a source route to D. Route
Discovery SHOULD be used only when S attempts to send a packet to D
and does not already know a route to D. The node initiating a Route
Discovery is known as the "initiator" of the Route Discovery, and the
destination node for which the Route Discovery is initiated is known
as the "target" of the Route Discovery.
Route Discovery operates entirely on demand; a node initiates Route
Discovery based on its own origination of new packets for some
destination address to which it does not currently know a route.
Route Discovery does not depend on any periodic or background
exchange of routing information or neighbor node detection at any
layer in the network protocol stack at any node.
The Route Discovery procedure utilizes two types of messages, a Route
Request (Section 6.2) and a Route Reply (Section 6.3), to actively
search the ad hoc network for a route to the desired target
destination. These DSR messages MAY be carried in any type of IP
packet, through use of the DSR Options header as described in Section
6.
Except as discussed in Section 8.3.5, a Route Discovery for a
destination address SHOULD NOT be initiated unless the initiating
node has a packet in its Send Buffer requiring delivery to that
destination. A Route Discovery for a given target node MUST NOT be
initiated unless permitted by the rate-limiting information contained
in the Route Request Table. After each Route Discovery attempt, the
interval between successive Route Discoveries for this target SHOULD
be doubled, up to a maximum of MaxRequestPeriod, until a valid Route
Reply is received for this target.
8.2.1. Originating a Route Request
A node initiating a Route Discovery for some target creates and initializes a Route Request option in a DSR Options header in some IP packet. This MAY be a separate IP packet, used only to carry this Route Request option, or the node MAY include the Route Request option in some existing packet that it needs to send to the target node (e.g., the IP packet originated by this node that caused the node to attempt Route Discovery for the destination address of the packet). The Route Request option MUST be included in a DSR Options header in the packet. To initialize the Route Request option, the node performs the following sequence of steps: - The Option Type in the option MUST be set to the value 2. - The Opt Data Len field in the option MUST be set to the value 6. The total size of the Route Request option, when initiated, is 8 octets; the Opt Data Len field excludes the size of the Option Type and Opt Data Len fields themselves. - The Identification field in the option MUST be set to a new value, different from that used for other Route Requests recently initiated by this node for this same target address. For example, each node MAY maintain a single counter value for generating a new Identification value for each Route Request it initiates. - The Target Address field in the option MUST be set to the IP address that is the target of this Route Discovery. The Source Address in the IP header of this packet MUST be the node's own IP address. The Destination Address in the IP header of this packet MUST be the IP "limited broadcast" address (255.255.255.255). A node MUST maintain, in its Route Request Table, information about Route Requests that it initiates. When initiating a new Route Request, the node MUST use the information recorded in the Route Request Table entry for the target of that Route Request, and it MUST update that information in the table entry for use in the next Route Request initiated for this target. In particular: - The Route Request Table entry for a target node records the Time- to-Live (TTL) field used in the IP header of the Route Request for the last Route Discovery initiated by this node for that target node. This value allows the node to implement a variety of algorithms for controlling the spread of its Route Request on each Route Discovery initiated for a target. As examples, two possible algorithms for this use of the TTL field are described in Section 3.3.3.
- The Route Request Table entry for a target node records the number
of consecutive Route Requests initiated for this target since
receiving a valid Route Reply giving a route to that target node,
and the remaining amount of time before which this node MAY next
attempt at a Route Discovery for that target node.
A node MUST use these values to implement a back-off algorithm to
limit the rate at which this node initiates new Route Discoveries
for the same target address. In particular, until a valid Route
Reply is received for this target node address, the timeout
between consecutive Route Discovery initiations for this target
node with the same hop limit SHOULD increase by doubling the
timeout value on each new initiation.
The behavior of a node processing a packet containing DSR Options
header with both a DSR Source Route option and a Route Request option
is unspecified. Packets SHOULD NOT contain both a DSR Source Route
option and a Route Request option.
Packets containing a Route Request option SHOULD NOT include an
Acknowledgement Request option, SHOULD NOT expect link-layer
acknowledgement or passive acknowledgement, and SHOULD NOT be
retransmitted. The retransmission of packets containing a Route
Request option is controlled solely by the logic described in this
section.
8.2.2. Processing a Received Route Request Option
When a node receives a packet containing a Route Request option, that
node MUST process the option according to the following sequence of
steps:
- If the Target Address field in the Route Request matches this
node's own IP address, then the node SHOULD return a Route Reply
to the initiator of this Route Request (the Source Address in the
IP header of the packet), as described in Section 8.2.4. The
source route for this Reply is the sequence of hop addresses
initiator, Address[1], Address[2], ..., Address[n], target
where initiator is the address of the initiator of this Route
Request, each Address[i] is an address from the Route Request, and
target is the target of the Route Request (the Target Address
field in the Route Request). The value n here is the number of
addresses recorded in the Route Request, or
(Opt Data Len - 6) / 4.
The node then MUST replace the Destination Address field in the
Route Request packet's IP header with the value in the Target
Address field in the Route Request option, and continue processing
the rest of the Route Request packet normally. The node MUST NOT
process the Route Request option further and MUST NOT retransmit
the Route Request to propagate it to other nodes as part of the
Route Discovery.
- Else, the node MUST examine the route recorded in the Route
Request option (the IP Source Address field and the sequence of
Address[i] fields) to determine if this node's own IP address
already appears in this list of addresses. If so, the node MUST
discard the entire packet carrying the Route Request option.
- Else, if the Route Request was received through a network
interface that requires physically bidirectional links for unicast
transmission, the node MUST check if the Route Request was last
forwarded by a node on its blacklist (Section 4.6). If such an
entry is found in the blacklist, and the state of the
unidirectional link is "probable", then the Request MUST be
silently discarded.
- Else, if the Route Request was received through a network
interface that requires physically bidirectional links for unicast
transmission, the node MUST check if the Route Request was last
forwarded by a node on its blacklist. If such an entry is found
in the blacklist, and the state of the unidirectional link is
"questionable", then the node MUST create and unicast a Route
Request packet to that previous node, setting the IP Time-To-Live
(TTL) to 1 to prevent the Request from being propagated. If the
node receives a Route Reply in response to the new Request, it
MUST remove the blacklist entry for that node, and SHOULD continue
processing. If the node does not receive a Route Reply within
some reasonable amount of time, the node MUST silently discard the
Route Request packet.
- Else, the node MUST search its Route Request Table for an entry
for the initiator of this Route Request (the IP Source Address
field). If such an entry is found in the table, the node MUST
search the cache of Identification values of recently received
Route Requests in that table entry, to determine if an entry is
present in the cache matching the Identification value and target
node address in this Route Request. If such an (Identification,
target address) entry is found in this cache in this entry in the
Route Request Table, then the node MUST discard the entire packet
carrying the Route Request option.
- Else, this node SHOULD further process the Route Request according
to the following sequence of steps:
o Add an entry for this Route Request in its cache of
(Identification, target address) values of recently received
Route Requests.
o Conceptually create a copy of this entire packet and perform
the following steps on the copy of the packet.
o Append this node's own IP address to the list of Address[i]
values in the Route Request and increase the value of the Opt
Data Len field in the Route Request by 4 (the size of an IP
address). However, if the node has multiple network
interfaces, this step MUST be modified by the special
processing specified in Section 8.4.
o This node SHOULD search its own Route Cache for a route (from
itself, as if it were the source of a packet) to the target of
this Route Request. If such a route is found in its Route
Cache, then this node SHOULD follow the procedure outlined in
Section 8.2.3 to return a "cached Route Reply" to the initiator
of this Route Request, if permitted by the restrictions
specified there.
o If the node does not return a cached Route Reply, then this
node SHOULD transmit this copy of the packet as a link-layer
broadcast, with a short jitter delay before the broadcast is
sent. The jitter period SHOULD be chosen as a random period,
uniformly distributed between 0 and BroadcastJitter.
8.2.3. Generating a Route Reply Using the Route Cache
As described in Section 3.3.2, it is possible for a node processing a
received Route Request to avoid propagating the Route Request further
toward the target of the Request, if this node has in its Route Cache
a route from itself to this target. Such a Route Reply generated by
a node from its own cached route to the target of a Route Request is
called a "cached Route Reply", and this mechanism can greatly reduce
the overall overhead of Route Discovery on the network by reducing
the flood of Route Requests. The general processing of a received
Route Request is described in Section 8.2.2; this section specifies
the additional requirements that MUST be met before a cached Route
Reply may be generated and returned and specifies the procedure for
returning such a cached Route Reply.
While processing a received Route Request, for a node to possibly
return a cached Route Reply, it MUST have in its Route Cache a route
from itself to the target of this Route Request. However, before
generating a cached Route Reply for this Route Request, the node MUST
verify that there are no duplicate addresses listed in the route
accumulated in the Route Request together with the route from this
node's Route Cache. Specifically, there MUST be no duplicates among
the following addresses:
- The IP Source Address of the packet containing the Route Request,
- The Address[i] fields in the Route Request, and
- The nodes listed in the route obtained from this node's Route
Cache, excluding the address of this node itself (this node itself
is the common point between the route accumulated in the Route
Request and the route obtained from the Route Cache).
If any duplicates exist among these addresses, then the node MUST NOT
send a cached Route Reply using this route from the Route Cache (it
is possible that this node has another route in its Route Cache for
which the above restriction on duplicate addresses is met, allowing
the node to send a cached Route Reply based on that cached route,
instead). The node SHOULD continue to process the Route Request as
described in Section 8.2.2 if it does not send a cached Route Reply.
If the Route Request and the route from the Route Cache meet the
restriction above, then the node SHOULD construct and return a cached
Route Reply as follows:
- The source route for this Route Reply is the sequence of hop
addresses
initiator, Address[1], Address[2], ..., Address[n], c-route
where initiator is the address of the initiator of this Route
Request, each Address[i] is an address from the Route Request, and
c-route is the sequence of hop addresses in the source route to
this target node, obtained from the node's Route Cache. In
appending this cached route to the source route for the reply, the
address of this node itself MUST be excluded, since it is already
listed as Address[n].
- Send a Route Reply to the initiator of the Route Request, using
the procedure defined in Section 8.2.4. The initiator of the
Route Request is indicated in the Source Address field in the
packet's IP header.
Before sending the cached Route Reply, however, the node MAY delay the Reply in order to help prevent a possible Route Reply "storm", as described in Section 8.2.5. If the node returns a cached Route Reply as described above, then the node MUST NOT propagate the Route Request further (i.e., the node MUST NOT rebroadcast the Route Request). In this case, instead, if the packet contains no other DSR options and contains no payload after the DSR Options header (e.g., the Route Request is not piggybacked on a TCP or UDP packet), then the node SHOULD simply discard the packet. Otherwise (if the packet contains other DSR options or contains any payload after the DSR Options header), the node SHOULD forward the packet along the cached route to the target of the Route Request. Specifically, if the node does so, it MUST use the following steps: - Copy the Target Address from the Route Request option in the DSR Options header to the Destination Address field in the packet's IP header. - Remove the Route Request option from the DSR Options header in the packet, and add a DSR Source Route option to the packet's DSR Options header. - In the DSR Source Route option, set the Address[i] fields to represent the source route found in this node's Route Cache to the original target of the Route Discovery (the new IP Destination Address of the packet). Specifically, the node copies the hop addresses of the source route into sequential Address[i] fields in the DSR Source Route option, for i = 1, 2, ..., n. Address[1], here, is the address of this node itself (the first address in the source route found from this node to the original target of the Route Discovery). The value n, here, is the number of hop addresses in this source route, excluding the destination of the packet (which is instead already represented in the Destination Address field in the packet's IP header). - Initialize the Segments Left field in the DSR Source Route option to n as defined above. - The First Hop External (F) bit in the DSR Source Route option MUST be set to 0. - The Last Hop External (L) bit in the DSR Source Route option is copied from the External bit flagging the last hop in the source route for the packet, as indicated in the Route Cache.
- The Salvage field in the DSR Source Route option MUST be
initialized to some nonzero value; the particular nonzero value
used SHOULD be MAX_SALVAGE_COUNT. By initializing this field to a
nonzero value, nodes forwarding or overhearing this packet will
not consider a link to exist between the IP Source Address of the
packet and the Address[1] address in the DSR Source Route option
(e.g., they will not attempt to add this to their Route Cache as a
link). By choosing MAX_SALVAGE_COUNT as the nonzero value to
which the node initializes this field, nodes furthermore will not
attempt to salvage this packet.
- Transmit the packet to the next-hop node on the new source route
in the packet, using the forwarding procedure described in Section
8.1.5.
8.2.4. Originating a Route Reply
A node originates a Route Reply in order to reply to a received and
processed Route Request, according to the procedures described in
Sections 8.2.2 and 8.2.3. The Route Reply is returned in a Route
Reply option (Section 6.3). The Route Reply option MAY be returned
to the initiator of the Route Request in a separate IP packet, used
only to carry this Route Reply option, or it MAY be included in any
other IP packet being sent to this address.
The Route Reply option MUST be included in a DSR Options header in
the packet returned to the initiator. To initialize the Route Reply
option, the node performs the following sequence of steps:
- The Option Type in the option MUST be set to the value 3.
- The Opt Data Len field in the option MUST be set to the value
(n * 4) + 3, where n is the number of addresses in the source
route being returned (excluding the Route Discovery initiator
node's address).
- If this node is the target of the Route Request, the Last Hop
External (L) bit in the option MUST be initialized to 0.
- The Reserved field in the option MUST be initialized to 0.
- The Route Request Identifier MUST be initialized to the Identifier
field of the Route Request to which this Route Reply is sent in
response.
- The sequence of hop addresses in the source route are copied into
the Address[i] fields of the option. Address[1] MUST be set to
the first-hop address of the route after the initiator of the
Route Discovery, Address[n] MUST be set to the last-hop address of
the source route (the address of the target node), and each other
Address[i] MUST be set to the next address in sequence in the
source route being returned.
The Destination Address field in the IP header of the packet carrying
the Route Reply option MUST be set to the address of the initiator of
the Route Discovery (i.e., for a Route Reply being returned in
response to some Route Request, the IP Source Address of the Route
Request).
After creating and initializing the Route Reply option and the IP
packet containing it, send the Route Reply. In sending the Route
Reply from this node (but not from nodes forwarding the Route Reply),
this node SHOULD delay the Reply by a small jitter period chosen
randomly between 0 and BroadcastJitter.
When returning any Route Reply in the case in which the MAC protocol
in use in the network is not capable of transmitting unicast packets
over unidirectional links, the source route used for routing the
Route Reply packet MUST be obtained by reversing the sequence of hops
in the Route Request packet (the source route that is then returned
in the Route Reply). This restriction on returning a Route Reply
enables the Route Reply to test this sequence of hops for
bidirectionality, preventing the Route Reply from being received by
the initiator of the Route Discovery unless each of the hops over
which the Route Reply is returned (and thus each of the hops in the
source route being returned in the Reply) is bidirectional.
If sending a Route Reply to the initiator of the Route Request
requires performing a Route Discovery, the Route Reply option MUST be
piggybacked on the packet that contains the Route Request. This
piggybacking prevents a recursive dependency wherein the target of
the new Route Request (which was itself the initiator of the original
Route Request) must do another Route Request in order to return its
Route Reply.
If sending the Route Reply to the initiator of the Route Request does
not require performing a Route Discovery, a node SHOULD send a
unicast Route Reply in response to every Route Request it receives
for which it is the target node.
8.2.5. Preventing Route Reply Storms
The ability for nodes to reply to a Route Request based on
information in their Route Caches, as described in Sections 3.3.2 and
8.2.3, could result in a possible Route Reply "storm" in some cases.
In particular, if a node broadcasts a Route Request for a target node
for which the node's neighbors have a route in their Route Caches,
each neighbor may attempt to send a Route Reply, thereby wasting
bandwidth and possibly increasing the number of network collisions in
the area.
For example, the figure below shows a situation in which nodes B, C,
D, E, and F all receive A's Route Request for target G, and each has
the indicated route cached for this target:
+-----+ +-----+
| D |< >| C |
+-----+ \ / +-----+
Cache: C - B - G \ / Cache: B - G
\ +-----+ /
-| A |-
+-----+\ +-----+ +-----+
| | \--->| B | | G |
/ \ +-----+ +-----+
/ \ Cache: G
v v
+-----+ +-----+
| E | | F |
+-----+ +-----+
Cache: F - B - G Cache: B - G
Normally, each of these nodes would attempt to reply from its own
Route Cache, and they would thus all send their Route Replies at
about the same time, since they all received the broadcast Route
Request at about the same time. Such simultaneous Route Replies from
different nodes all receiving the Route Request may cause local
congestion in the wireless network and may create packet collisions
among some or all of these Replies if the MAC protocol in use does
not provide sufficient collision avoidance for these packets. In
addition, it will often be the case that the different replies will
indicate routes of different lengths, as shown in this example.
In order to reduce these effects, if a node can put its network
interface into promiscuous receive mode, it MAY delay sending its own
Route Reply for a short period, while listening to see if the
initiating node begins using a shorter route first. Specifically,
this node MAY delay sending its own Route Reply for a random period
d = H * (h - 1 + r)
where h is the length in number of network hops for the route to be
returned in this node's Route Reply, r is a random floating point
number between 0 and 1, and H is a small constant delay (at least
twice the maximum wireless link propagation delay) to be introduced
per hop. This delay effectively randomizes the time at which each node sends its Route Reply, with all nodes sending Route Replies giving routes of length less than h sending their Replies before this node, and all nodes sending Route Replies giving routes of length greater than h send their Replies after this node. Within the delay period, this node promiscuously receives all packets, looking for data packets from the initiator of this Route Discovery destined for the target of the Route Discovery. If such a data packet received by this node during the delay period uses a source route of length less than or equal to h, this node may infer that the initiator of the Route Discovery has already received a Route Reply giving an equally good or better route. In this case, this node SHOULD cancel its delay timer and SHOULD NOT send its Route Reply for this Route Discovery.8.2.6. Processing a Received Route Reply Option
Section 8.1.4 describes the general processing for a received packet, including the addition of routing information from options in the packet's DSR Options header to the receiving node's Route Cache. If the received packet contains a Route Reply, no additional special processing of the Route Reply option is required beyond what is described there. As described in Section 4.1, anytime a node adds new information to its Route Cache (including the information added from this Route Reply option), the node SHOULD check each packet in its own Send Buffer (Section 4.2) to determine whether a route to that packet's IP Destination Address now exists in the node's Route Cache (including the information just added to the Cache). If so, the packet SHOULD then be sent using that route and removed from the Send Buffer. This general procedure handles all processing required for a received Route Reply option. When using a MAC protocol that requires bidirectional links for unicast transmission, a unidirectional link may be discovered by the propagation of the Route Request. When the Route Reply is sent over the reverse path, a forwarding node may discover that the next-hop is unreachable. In this case, it MUST add the next-hop address to its blacklist (Section 4.6).8.3. Route Maintenance Processing
Route Maintenance is the mechanism by which a source node S is able to detect, while using a source route to some destination node D, if the network topology has changed such that it can no longer use its route to D because a link along the route no longer works. When Route Maintenance indicates that a source route is broken, S can
attempt to use any other route it happens to know to D or can invoke Route Discovery again to find a new route for subsequent packets to D. Route Maintenance for this route is used only when S is actually sending packets to D. Specifically, when forwarding a packet, a node MUST attempt to confirm the reachability of the next-hop node, unless such confirmation had been received in the last MaintHoldoffTime period. Individual implementations MAY choose to bypass such confirmation for some limited number of packets, as long as those packets all fall within MaintHoldoffTime since the last confirmation. If no confirmation is received after the retransmission of MaxMaintRexmt acknowledgement requests, after the initial transmission of the packet, and conceptually including all retransmissions provided by the MAC layer, the node determines that the link for this next-hop node of the source route is "broken". This confirmation from the next-hop node for Route Maintenance can be implemented using a link- layer acknowledgement (Section 8.3.1), a "passive acknowledgement" (Section 8.3.2), or a network-layer acknowledgement (Section 8.3.3); the particular strategy for retransmission timing depends on the type of acknowledgement mechanism used. When not using link-layer acknowledgements for Route Maintenance, nodes SHOULD use passive acknowledgements when possible but SHOULD try requesting a network- layer acknowledgement one or more times before deciding that the link has failed and originating a Route Error to the original sender of the packet, as described in Section 8.3.4. In deciding whether or not to send a Route Error in response to attempting to forward a packet from some sender over a broken link, a node MUST limit the number of consecutive packets from a single sender that the node attempts to forward over this same broken link for which the node chooses not to return a Route Error. This requirement MAY be satisfied by returning a Route Error for each packet that the node attempts to forward over a broken link.8.3.1. Using Link-Layer Acknowledgements
If the MAC protocol in use provides feedback as to the successful delivery of a data packet (such as is provided for unicast packets by the link-layer acknowledgement frame defined by IEEE 802.11 [IEEE80211]), then the use of the DSR Acknowledgement Request and Acknowledgement options is not necessary. If such link-layer feedback is available, it SHOULD be used instead of any other acknowledgement mechanism for Route Maintenance, and the node SHOULD NOT use either passive acknowledgements or network-layer acknowledgements for Route Maintenance.
When using link-layer acknowledgements for Route Maintenance, the retransmission timing and the timing at which retransmission attempts are scheduled are generally controlled by the particular link layer implementation in use in the network. For example, in IEEE 802.11, the link-layer acknowledgement is returned after a unicast packet as a part of the basic access method of the IEEE 802.11 Distributed Coordination Function (DCF) MAC protocol; the time at which the acknowledgement is expected to arrive and the time at which the next retransmission attempt (if necessary) will occur are controlled by the MAC protocol implementation. When a node receives a link-layer acknowledgement for any packet in its Maintenance Buffer, that node SHOULD remove from its Maintenance Buffer that packet, as well as any other packets in its Maintenance Buffer with the same next-hop destination.8.3.2. Using Passive Acknowledgements
When link-layer acknowledgements are not available, but passive acknowledgements [JUBIN87] are available, passive acknowledgements SHOULD be used for Route Maintenance when originating or forwarding a packet along any hop other than the last hop (the hop leading to the IP Destination Address node of the packet). In particular, passive acknowledgements SHOULD be used for Route Maintenance in such cases if the node can place its network interface into "promiscuous" receive mode, and if network links used for data packets generally operate bidirectionally. A node MUST NOT attempt to use passive acknowledgements for Route Maintenance for a packet originated or forwarded over its last hop (the hop leading to the IP Destination Address node of the packet), since the receiving node will not be forwarding the packet and thus no passive acknowledgement will be available to be heard by this node. Beyond this restriction, a node MAY utilize a variety of strategies in using passive acknowledgements for Route Maintenance of a packet that it originates or forwards. For example, the following two strategies are possible: - Each time a node receives a packet to be forwarded to a node other than the final destination (the IP Destination Address of the packet), that node sends the original transmission of that packet without requesting a network-layer acknowledgement for it. If no passive acknowledgement is received within PassiveAckTimeout after this transmission, the node retransmits the packet, again without requesting a network-layer acknowledgement for it; the same PassiveAckTimeout timeout value is used for each such attempt. If no acknowledgement has been received after a total of TryPassiveAcks retransmissions of the packet, network-layer
acknowledgements (as described in Section 8.3.3) are requested for
all remaining attempts for that packet.
- Each node maintains a table of possible next-hop destination
nodes, noting whether or not passive acknowledgements can
typically be expected from transmission to that node, and the
expected latency and jitter of a passive acknowledgement from that
node. Each time a node receives a packet to be forwarded to a
node other than the IP Destination Address, the node checks its
table of next-hop destination nodes to determine whether to use a
passive acknowledgement or a network-layer acknowledgement for
that transmission to that node. The timeout for this packet can
also be derived from this table. A node using this method SHOULD
prefer using passive acknowledgements to network-layer
acknowledgements.
In using passive acknowledgements for a packet that it originates or
forwards, a node considers the later receipt of a new packet (e.g.,
with promiscuous receive mode enabled on its network interface) an
acknowledgement of this first packet if both of the following two
tests succeed:
- The Source Address, Destination Address, Protocol, Identification,
and Fragment Offset fields in the IP header of the two packets
MUST match [RFC791].
- If either packet contains a DSR Source Route header, both packets
MUST contain one, and the value in the Segments Left field in the
DSR Source Route header of the new packet MUST be less than that
in the first packet.
When a node hears such a passive acknowledgement for any packet in
its Maintenance Buffer, that node SHOULD remove from its Maintenance
Buffer that packet, as well as any other packets in its Maintenance
Buffer with the same next-hop destination.
8.3.3. Using Network-Layer Acknowledgements
When a node originates or forwards a packet and has no other
mechanism of acknowledgement available to determine reachability of
the next-hop node in the source route for Route Maintenance, that
node SHOULD request a network-layer acknowledgement from that next-
hop node. To do so, the node inserts an Acknowledgement Request
option in the DSR Options header in the packet. The Identification
field in that Acknowledgement Request option MUST be set to a value
unique over all packets recently transmitted by this node to the same
next-hop node.
When a node receives a packet containing an Acknowledgement Request
option, that node performs the following tests on the packet:
- If the indicated next-hop node address for this packet does not
match any of this node's own IP addresses, then this node MUST NOT
process the Acknowledgement Request option. The indicated next-
hop node address is the next Address[i] field in the DSR Source
Route option in the DSR Options header in the packet, or the IP
Destination Address in the packet if the packet does not contain a
DSR Source Route option or the Segments Left there is zero.
- If the packet contains an Acknowledgement option, then this node
MUST NOT process the Acknowledgement Request option.
If neither of the tests above fails, then this node MUST process the
Acknowledgement Request option by sending an Acknowledgement option
to the previous-hop node; to do so, the node performs the following
sequence of steps:
- Create a packet and set the IP Protocol field to the protocol
number assigned for DSR (48).
- Set the IP Source Address field in this packet to the IP address
of this node, copied from the source route in the DSR Source Route
option in that packet (or from the IP Destination Address field of
the packet, if the packet does not contain a DSR Source Route
option).
- Set the IP Destination Address field in this packet to the IP
address of the previous-hop node, copied from the source route in
the DSR Source Route option in that packet (or from the IP Source
Address field of the packet, if the packet does not contain a DSR
Source Route option).
- Add a DSR Options header to the packet. Set the Next Header field
in the DSR Options header to the value 59, "No Next Header"
[RFC2460].
- Add an Acknowledgement option to the DSR Options header in the
packet; set the Acknowledgement option's Option Type field to 6
and the Opt Data Len field to 10.
- Copy the Identification field from the received Acknowledgement
Request option into the Identification field in the
Acknowledgement option.
- Set the ACK Source Address field in the Acknowledgement option to
be the IP Source Address of this new packet (set above to be the
IP address of this node).
- Set the ACK Destination Address field in the Acknowledgement
option to be the IP Destination Address of this new packet (set
above to be the IP address of the previous-hop node).
- Send the packet as described in Section 8.1.1.
Packets containing an Acknowledgement option SHOULD NOT be placed in
the Maintenance Buffer.
When a node receives a packet with both an Acknowledgement option and
an Acknowledgement Request option, if that node is not the
destination of the Acknowledgement option (the IP Destination Address
of the packet), then the Acknowledgement Request option MUST be
ignored. Otherwise (that node is the destination of the
Acknowledgement option), that node MUST process the Acknowledgement
Request option by returning an Acknowledgement option according to
the following sequence of steps:
- Create a packet and set the IP Protocol field to the protocol
number assigned for DSR (48).
- Set the IP Source Address field in this packet to the IP address
of this node, copied from the source route in the DSR Source Route
option in that packet (or from the IP Destination Address field of
the packet, if the packet does not contain a DSR Source Route
option).
- Set the IP Destination Address field in this packet to the IP
address of the node originating the Acknowledgement option.
- Add a DSR Options header to the packet, and set the DSR Options
header's Next Header field to the value 59, "No Next Header"
[RFC2460].
- Add an Acknowledgement option to the DSR Options header in this
packet; set the Acknowledgement option's Option Type field to 6
and the Opt Data Len field to 10.
- Copy the Identification field from the received Acknowledgement
Request option into the Identification field in the
Acknowledgement option.
- Set the ACK Source Address field in the option to the IP Source
Address of this new packet (set above to be the IP address of this
node).
- Set the ACK Destination Address field in the option to the IP
Destination Address of this new packet (set above to be the IP
address of the node originating the Acknowledgement option).
- Send the packet directly to the destination. The IP Destination
Address MUST be treated as a direct neighbor node: the
transmission to that node MUST be done in a single IP forwarding
hop, without Route Discovery and without searching the Route
Cache. In addition, this packet MUST NOT contain a DSR
Acknowledgement Request, MUST NOT be retransmitted for Route
Maintenance, and MUST NOT expect a link-layer acknowledgement or
passive acknowledgement.
When using network-layer acknowledgements for Route Maintenance, a
node SHOULD use an adaptive algorithm in determining the
retransmission timeout for each transmission attempt of an
acknowledgement request. For example, a node SHOULD maintain a
separate round-trip time (RTT) estimate for each node to which it has
recently attempted to transmit packets, and it SHOULD use this RTT
estimate in setting the timeout for each retransmission attempt for
Route Maintenance. The TCP RTT estimation algorithm has been shown
to work well for this purpose in implementation and testbed
experiments with DSR [MALTZ99b, MALTZ01].
8.3.4. Originating a Route Error
When a node is unable to verify reachability of a next-hop node after
reaching a maximum number of retransmission attempts, it SHOULD send
a Route Error to the IP Source Address of the packet. When sending a
Route Error for a packet containing either a Route Error option or an
Acknowledgement option, a node SHOULD add these existing options to
its Route Error, subject to the limit described below.
A node transmitting a Route Error MUST perform the following steps:
- Create an IP packet and set the IP Protocol field to the protocol
number assigned for DSR (48). Set the Source Address field in
this packet's IP header to the address of this node.
- If the Salvage field in the DSR Source Route option in the packet
triggering the Route Error is zero, then copy the Source Address
field of the packet triggering the Route Error into the
Destination Address field in the new packet's IP header;
otherwise, copy the Address[1] field from the DSR Source Route
option of the packet triggering the Route Error into the
Destination Address field in the new packet's IP header
- Insert a DSR Options header into the new packet.
- Add a Route Error Option to the new packet, setting the Error Type
to NODE_UNREACHABLE, the Salvage value to the Salvage value from
the DSR Source Route option of the packet triggering the Route
Error, and the Unreachable Node Address field to the address of
the next-hop node from the original source route. Set the Error
Source Address field to this node's IP address, and the Error
Destination field to the new packet's IP Destination Address.
- If the packet triggering the Route Error contains any Route Error
or Acknowledgement options, the node MAY append to its Route Error
each of these options, with the following constraints:
o The node MUST NOT include any Route Error option from the
packet triggering the new Route Error, for which the total
Salvage count (Section 6.4) of that included Route Error would
be greater than MAX_SALVAGE_COUNT in the new packet.
o If any Route Error option from the packet triggering the new
Route Error is not included in the packet, the node MUST NOT
include any following Route Error or Acknowledgement options
from the packet triggering the new Route Error.
o Any appended options from the packet triggering the Route Error
MUST follow the new Route Error in the packet.
o In appending these options to the new Route Error, the order of
these options from the packet triggering the Route Error MUST
be preserved.
- Send the packet as described in Section 8.1.1.
8.3.5. Processing a Received Route Error Option
When a node receives a packet containing a Route Error option, that
node MUST process the Route Error option according to the following
sequence of steps:
- The node MUST remove from its Route Cache the link from the node
identified by the Error Source Address field to the node
identified by the Unreachable Node Address field (if this link is
present in its Route Cache). If the node implements its Route
Cache as a link cache, as described in Section 4.1, only this
single link is removed; if the node implements its Route Cache as
a path cache, however, all routes (paths) that use this link are
either truncated before the link or removed completely.
- If the option following the Route Error is an Acknowledgement or
Route Error option sent by this node (that is, with
Acknowledgement or Error Source Address equal to this node's
address), copy the DSR options following the current Route Error
into a new packet with IP Source Address equal to this node's own
IP address and IP Destination Address equal to the Acknowledgement
or Error Destination Address. Transmit this packet as described
in Section 8.1.1, with the Salvage count in the DSR Source Route
option set to the Salvage value of the Route Error.
In addition, after processing the Route Error as described above, the
node MAY initiate a new Route Discovery for any destination node for
which it then has no route in its Route Cache as a result of
processing this Route Error, if the node has indication that a route
to that destination is needed. For example, if the node has an open
TCP connection to some destination node, then if the processing of
this Route Error removed the only route to that destination from this
node's Route Cache, then this node MAY initiate a new Route Discovery
for that destination node. Any node, however, MUST limit the rate at
which it initiates new Route Discoveries for any single destination
address, and any new Route Discovery initiated in this way as part of
processing this Route Error MUST conform as a part of this limit.
8.3.6. Salvaging a Packet
When an intermediate node forwarding a packet detects through Route
Maintenance that the next-hop link along the route for that packet is
broken (Section 8.3), if the node has another route to the packet's
IP Destination Address in its Route Cache, the node SHOULD "salvage"
the packet rather than discard it. To do so using the route found in
its Route Cache, this node processes the packet as follows:
- If the MAC protocol in use in the network is not capable of
transmitting unicast packets over unidirectional links, as
discussed in Section 3.3.1, then if this packet contains a Route
Reply option, remove and discard the Route Reply option in the
packet; if the DSR Options header in the packet then contains no
DSR options or only a DSR Source Route Option, remove the DSR
Options header from the packet. If the resulting packet then
contains only an IP header (e.g., no transport layer header or
payload), the node SHOULD NOT salvage the packet and instead
SHOULD discard the entire packet.
- Modify the existing DSR Source Route option in the packet so that
the Address[i] fields represent the source route found in this
node's Route Cache to this packet's IP Destination Address.
Specifically, the node copies the hop addresses of the source
route into sequential Address[i] fields in the DSR Source Route
option, for i = 1, 2, ..., n. Address[1], here, is the address of
the salvaging node itself (the first address in the source route
found from this node to the IP Destination Address of the packet).
The value n, here, is the number of hop addresses in this source
route, excluding the destination of the packet (which is instead
already represented in the Destination Address field in the
packet's IP header).
- Initialize the Segments Left field in the DSR Source Route option
to n as defined above.
- The First Hop External (F) bit in the DSR Source Route option MUST
be set to 0.
- The Last Hop External (L) bit in the DSR Source Route option is
copied from the External bit flagging the last hop in the source
route for the packet, as indicated in the Route Cache.
- The Salvage field in the DSR Source Route option is set to 1 plus
the value of the Salvage field in the DSR Source Route option of
the packet that caused the error.
- Transmit the packet to the next-hop node on the new source route
in the packet, using the forwarding procedure described in Section
8.1.5.
As described in Section 8.3.4, the node in this case also SHOULD
return a Route Error to the original sender of the packet. If the
node chooses to salvage the packet, it SHOULD do so after originating
the Route Error.
When returning any Route Reply in the case in which the MAC protocol
in use in the network is not capable of transmitting unicast packets
over unidirectional links, the source route used for routing the
Route Reply packet MUST be obtained by reversing the sequence of hops
in the Route Request packet (the source route that is then returned
in the Route Reply). This restriction on returning a Route Reply and
on salvaging a packet that contains a Route Reply option enables the
Route Reply to test this sequence of hops for bidirectionality,
preventing the Route Reply from being received by the initiator of
the Route Discovery unless each of the hops over which the Route
Reply is returned (and thus each of the hops in the source route
being returned in the Reply) is bidirectional.
(next page on part 4)
