WDIFF

draft-ietf-manet-dsr-07.txt --> draft-ietf-manet-dsr-08.txt

IETF MANET Working Group David B. Johnson, Rice University
INTERNET-DRAFT David A. Maltz, AON Networks
21 Carnegie Mellon University
24 February 2002 2003 Yih-Chun Hu, Rice University
Jorjeta G. Jetcheva, Carnegie Mellon University

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

<draft-ietf-manet-dsr-07.txt>

<draft-ietf-manet-dsr-08.txt>

Status of This Memo

This document is an Internet-Draft and is subject to all provisions
of Section 10 of RFC 2026.

Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note
that other groups may also distribute working documents as
Internet-Drafts.

Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at
any time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress".

The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt

The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.

This Internet-Draft is a submission to the IETF Mobile Ad Hoc
Networks (MANET) Working Group. Comments on this draft may be sent
to the Working Group at manet@itd.nrl.navy.mil, or may be sent
directly to the authors.

Johnson, et al Expires 21 24 August 2002 2003 [Page i]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002 2003

Abstract

The Dynamic Source Routing protocol (DSR) is a simple and efficient
routing protocol designed specifically for use in multi-hop wireless
ad hoc networks of mobile nodes. DSR allows the network to be
completely self-organizing and self-configuring, without the need
for any existing network infrastructure or administration. The
protocol is composed of the two main mechanisms of "Route Discovery"
and "Route Maintenance", which work together to allow nodes to
discover and maintain source routes to arbitrary destinations in the ad hoc
network. The use of source routing allows packet routing
to be trivially loop-free, avoids the need for up-to-date routing
information in the intermediate nodes through which packets are
forwarded, and allows nodes forwarding or overhearing packets to
cache the routing information in them for their own future use. All aspects of the protocol operate entirely on-demand,
allowing the routing packet overhead of DSR to scale automatically
to only that needed to react to changes in the routes currently in
use. This
document specifies The protocol allows multiple routes to any destination and
allows each sender to select and control the operation routes used in routing
its packets, for example for use in load balancing or for increased
robustness. Other advantages of the DSR protocol include easily
guaranteed loop-free routing, support for routing
unicast IPv4 packets use in multi-hop wireless ad hoc networks. networks containing
unidirectional links, use of only "soft state" in routing, and very
rapid recovery when routes in the network change. The DSR protocol
is designed mainly for mobile ad hoc networks with of up to
around about two
hundred nodes, and is designed to cope work well with relatively even very high
rates of mobility. This document specifies the operation of the DSR
protocol for routing unicast IPv4 packets.

Johnson, et al Expires 21 24 August 2002 2003 [Page ii]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002 2003

Contents

Status of This Memo i

Abstract ii

1. Introduction 1

2. Assumptions 3

3. DSR Protocol Overview 5

3.1. Basic DSR Route Discovery . . . . . . . . . . . . . . . . 5
3.2. Basic DSR Route Maintenance . . . . . . . . . . . . . . . 7 8
3.3. Additional Route Discovery Features . . . . . . . . . . . 9 10
3.3.1. Caching Overheard Routing Information . . . . . . 9 10
3.3.2. Replying to Route Requests using Cached Routes . 10 11
3.3.3. Preventing Route Reply Storms . . . . . . . . . . 11 12
3.3.4. Route Request Hop Limits . . . . . . . . . . . . 13 14
3.4. Additional Route Maintenance Features . . . . . . . . . . 14 15
3.4.1. Packet Salvaging . . . . . . . . . . . . . . . . 14 15
3.4.2. Queued Packets Destined over a Broken Link . . . 14 15
3.4.3. Automatic Route Shortening . . . . . . . . . . . 15 16
3.4.4. Increased Spreading of Route Error Messages . . . 16

4. Conceptual Data Structures 17

4.1. Route Cache .
3.5. Optional DSR Flow State Extension . . . . . . . . . . . . 17
3.5.1. Flow Establishment . . . . . . . . . . 17
4.2. Send Buffer . . . . . 18
3.5.2. Receiving and Forwarding Establishment Packets . 19
3.5.3. Sending Packets Along Established Flows . . . . . 19
3.5.4. Receiving and Forwarding Packets Sent Along
Established Flows . . . . . . . . . . . . 20
4.3.
3.5.5. Processing Route Request Table Errors . . . . . . . . . . . . . 21
3.5.6. Interaction with Automatic Route Shortening . . . 21
3.5.7. Loop Detection . . . 21
4.4. Gratuitous Route Reply Table . . . . . . . . . . . . . . 22
4.5. Network Interface Queue and Maintenance Buffer
3.5.8. Acknowledgement Destination . . . . . 23
4.6. Blacklist . . . . . . 22
3.5.9. Crash Recovery . . . . . . . . . . . . . . . . . 22
3.5.10. Rate Limiting . 24

5. DSR Header Format 25

5.1. Fixed Portion of DSR Header . . . . . . . . . . . . . . . 26
5.2. Route Request Option . . 22
3.5.11. Interaction with Packet Salvaging . . . . . . . . 23

4. Conceptual Data Structures 24

4.1. Route Cache . . . . . . . . 28
5.3. Route Reply Option . . . . . . . . . . . . . . . 24
4.2. Send Buffer . . . . 30
5.4. Route Error Option . . . . . . . . . . . . . . . . . . . 32
5.5. Acknowledgment 27
4.3. Route Request Option . . Table . . . . . . . . . . . . 35
5.6. Acknowledgment Option . . . . . . . 28
4.4. Gratuitous Route Reply Table . . . . . . . . . . . 36
5.7. DSR Source Route Option . . . 29
4.5. Network Interface Queue and Maintenance Buffer . . . . . 30

Johnson, et al Expires 24 August 2003 [Page iii]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

4.6. Blacklist . . . . . . . . . 37
5.8. Pad1 Option . . . . . . . . . . . . . . . 31

5. Additional Conceptual Data Structures for Flow State Extension 32

5.1. Flow Table . . . . . . . . 39
5.9. PadN Option . . . . . . . . . . . . . . . 32
5.2. Automatic Route Shortening Table . . . . . . . . 40

Johnson, et al Expires 21 August 2002 [Page iii]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 February 2002

6. Detailed Operation 41

6.1. General Packet Processing . . . . 33
5.3. Default Flow ID Table . . . . . . . . . . . . 41
6.1.1. Originating a Packet . . . . . . 33

6. DSR Options Header Format 35

6.1. Fixed Portion of DSR Options Header . . . . . . . . 41
6.1.2. Adding a DSR Header to a Packet . . . 36
6.2. Route Request Option . . . . . . 41
6.1.3. Adding a DSR Source Route Option to a Packet . . 42
6.1.4. Processing a Received Packet . . . . . . . . . . 43
6.1.5. Processing a Received DSR Source 39
6.3. Route Reply Option . . 45
6.2. Route Discovery Processing . . . . . . . . . . . . . . . 48
6.2.1. Originating a Route Request . . . . 41
6.4. Route Error Option . . . . . . . 48
6.2.2. Processing a Received Route Request Option . . . 50
6.2.3. Generating a Route Reply using the Route Cache . 52
6.2.4. Originating a Route Reply . . . . . . . . 43
6.4.1. Node Unreachable Type-Specific Information . . . 45
6.4.2. Flow State Not Supported Type-Specific Information 45
6.4.3. Option Not Supported Type-Specific Information . 54
6.2.5. Processing a Received Route Reply 45
6.5. Acknowledgement Request Option . . . . 56
6.3. Route Maintenance Processing . . . . . . . . . 46
6.6. Acknowledgement Option . . . . . 57
6.3.1. Using Link-Layer Acknowledgments . . . . . . . . 57
6.3.2. Using Passive Acknowledgments . . . . 47
6.7. DSR Source Route Option . . . . . . 58
6.3.3. Using Network-Layer Acknowledgments . . . . . . . 59
6.3.4. Originating a Route Error . . . . 48
6.8. Pad1 Option . . . . . . . . 62
6.3.5. Processing a Received Route Error Option . . . . 63
6.3.6. Salvaging a Packet . . . . . . . . . . . 50
6.9. PadN Option . . . . 64 . . . . . . . . . . . . . . . . . . . 51

7. Multiple Interface Support 66

8. Fragmentation and Reassembly 67

9. Protocol Constants Additional Header Formats and Configuration Variables 68

10. IANA Considerations 69

11. Security Considerations 70

Appendix A. Link-MaxLife Cache Description 71

Appendix B. Location of Options for Flow State Extension 52

7.1. DSR Flow State Header . . . . . . . . . . . . . . . . . . 53
7.2. Options and Extensions in the ISO Network Reference Model 73

Appendix C. Implementation DSR Options Header . . . . . . 54
7.2.1. Timeout Option . . . . . . . . . . . . . . . . . 54
7.2.2. Destination and Evaluation Status 74

Changes from Flow ID Option . . . . . . . . . 55
7.2.3. New Error Type Value for Unknown Flow . . . . . . 56
7.2.4. New Error Type Value for Default Flow Unknown . . 57
7.2.5. Acknowledgement Request Option
Previous Version of the Draft 75

Acknowledgements 76

References 77

Chair's Hop Address 80

Authors' Addresses 81

Johnson, et al Expires 21 August 2002 [Page iv]

INTERNET-DRAFT The Dynamic Extension . . . . . . 58

8. Detailed Operation 59

8.1. General Packet Processing . . . . . . . . . . . . . . . . 59
8.1.1. Originating a Packet . . . . . . . . . . . . . . 59
8.1.2. Adding a DSR Options Header to a Packet . . . . . 59
8.1.3. Adding a DSR Source Routing Protocol 21 February 2002

1. Introduction Route Option to a Packet . . 60
8.1.4. Processing a Received Packet . . . . . . . . . . 61
8.1.5. Processing a Received DSR Source Route Option . . 63
8.1.6. Handling an Unknown DSR Option . . . . . . . . . 65
8.2. Route Discovery Processing . . . . . . . . . . . . . . . 67
8.2.1. Originating a Route Request . . . . . . . . . . . 67
8.2.2. Processing a Received Route Request Option . . . 69
8.2.3. Generating a Route Reply using the Route Cache . 71
8.2.4. Originating a Route Reply . . . . . . . . . . . . 73
8.2.5. Processing a Received Route Reply Option . . . . 75
8.3. Route Maintenance Processing . . . . . . . . . . . . . . 76

Johnson, et al Expires 24 August 2003 [Page iv]

INTERNET-DRAFT The Dynamic Source Routing protocol (DSR) [13, 14] Protocol 24 February 2003

8.3.1. Using Link-Layer Acknowledgements . . . . . . . . 76
8.3.2. Using Passive Acknowledgements . . . . . . . . . 77
8.3.3. Using Network-Layer Acknowledgements . . . . . . 78
8.3.4. Originating a Route Error . . . . . . . . . . . . 81
8.3.5. Processing a Received Route Error Option . . . . 82
8.3.6. Salvaging a Packet . . . . . . . . . . . . . . . 83
8.4. Multiple Interface Support . . . . . . . . . . . . . . . 85
8.5. Fragmentation and Reassembly . . . . . . . . . . . . . . 86
8.6. Flow State Processing . . . . . . . . . . . . . . . . . . 87
8.6.1. Originating a Packet . . . . . . . . . . . . . . 87
8.6.2. Inserting a DSR Flow State Header . . . . . . . . 89
8.6.3. Receiving a Packet . . . . . . . . . . . . . . . 89
8.6.4. Forwarding a Packet Using Flow IDs . . . . . . . 94
8.6.5. Promiscuously Receiving a Packet . . . . . . . . 94
8.6.6. Operation where the Layer below DSR Decreases
the IP TTL Non-Uniformly . . . . . . . . . 95
8.6.7. Salvage Interactions with DSR . . . . . . . . . . 95

9. Protocol Constants and Configuration Variables 96

10. IANA Considerations 97

11. Security Considerations 98

Appendix A. Link-MaxLife Cache Description 99

Appendix B. Location of DSR in the ISO Network Reference Model 101

Appendix C. Implementation and Evaluation Status 102

Changes from Previous Version of the Draft 104

Acknowledgements 105

References 106

Chair's Address 110

Authors' Addresses 111

Johnson, et al Expires 24 August 2003 [Page v]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

1. Introduction

The Dynamic Source Routing protocol (DSR) [15, 16] is a simple and
efficient routing protocol designed specifically for use in multi-hop
wireless ad hoc networks of mobile nodes. Using DSR, the network
is completely self-organizing and self-configuring, requiring no
existing network infrastructure or administration. Network nodes
cooperate to forward packets for each other to allow communication
over multiple "hops" between nodes not directly within wireless
transmission range of one another. As nodes in the network move
about or join or leave the network, and as wireless transmission
conditions such as sources of interference change, all routing is
automatically determined and maintained by the DSR routing protocol.
Since the number or sequence of intermediate hops needed to reach any
destination may change at any time, the resulting network topology
may be quite rich and rapidly changing.

In designing DSR, we sought to create a routing protocol that had
very low overhead yet was able to react very quickly to changes in
the network. The DSR protocol provides highly reactive service in
order to help ensure successful delivery of data packets in spite of
node movement or other changes in network conditions.

The DSR protocol is composed of two main mechanisms that work
together to allow the discovery and maintenance of source routes in
the ad hoc network:

- 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 is used only when S attempts to send a
packet to D and does not already know a route to D.

- Route Maintenance is the mechanism by which node S is able
to detect, while using a source route to 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 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.

Johnson, et al Expires 24 August 2003 [Page 1]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

down to zero, when all nodes are approximately stationary with
respect to each other and all routes needed for current communication
have already been discovered. As nodes begin to move more or
as communication patterns change, the routing packet overhead of
DSR automatically scales to only that needed to track the routes
currently in use. Network topology changes not affecting routes
currently in use are ignored and do not cause reaction from the
protocol.

All state maintained by DSR is "soft state" [6], in that the loss
of any state will not interfere with the correct operation of the
protocol; all state is discovered as needed and can easily and
quickly be rediscovered if needed after a failure without significant
impact on the protocol. This use of only soft state allows the
routing protocol to be very robust to problems such as dropped or
delayed routing packets or node failures. In particular, a node in
DSR that fails and reboots can easily rejoin the network immediately
after rebooting; if the failed node was involved in forwarding
packets for other nodes as an intermediate hop along one or more
routes, it can also resume this forwarding quickly after rebooting,
with no or minimal interruption to the routing protocol.

In response to a single Route Discovery (as well as through routing
information from other packets overheard), a node may learn and
cache multiple routes to any destination. This support for multiple
routes allows the reaction to 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 has been using should fail. This caching
of multiple routes also avoids the overhead of needing to perform a
new Route Discovery each time a route in use breaks. The sender of
a packet selects and controls the route used for its own packets,
which together with support for multiple routes also allows features
such as load balancing to be defined. In addition, all routes used
are easily guaranteed to be loop-free, since the sender can avoid
duplicate hops in the routes selected.

The operation of both Route Discovery and Route Maintenance in DSR
are designed to allow unidirectional links and asymmetric routes
to be easily supported. In particular, as noted in Section 2, in
wireless networks, it is possible that a link between two nodes may
not work equally well in both directions, due to differing antenna
or propagation patterns or sources of interference. DSR allows such
unidirectional links to be used when necessary, improving overall
performance and network connectivity in the system.

This document specifies the operation of the DSR protocol for
routing unicast IPv4 packets in multi-hop wireless ad hoc networks.
Advanced, optional features, such as Quality of Service (QoS) support
and efficient multicast routing, and operation of DSR with IPv6 [7],
are covered in other documents. The specification of DSR in this

Johnson, et al Expires 24 August 2003 [Page 2]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

document provides a compatible base on which such features can be
added, either independently or by integration with the DSR operation
specified here.

The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [4].

2. Assumptions

The DSR protocol as described here is designed mainly for mobile
ad hoc networks of up to about two hundred nodes, and is designed
to work well with even very high rates of mobility. Other protocol
features and enhancements that may allow DSR to scale to larger
networks are outside the scope of this document.

We assume in this document that all nodes wishing to communicate with
other nodes within the ad hoc network are willing to participate
fully in the protocols of the network. In particular, each node
participating in the ad hoc network SHOULD also be willing to forward
packets for other nodes in the network.

The diameter of an ad hoc network is the minimum number of hops
necessary for a packet to reach from any node located at one extreme
edge of the ad hoc network to another node located at the opposite
extreme. We assume that this diameter will often be small (e.g.,
perhaps 5 or 10 hops), but may often be greater than 1.

Packets may be lost or corrupted in transmission on the wireless
network. We assume that a node receiving a corrupted packet can
detect the error and discard the packet.

Nodes within the ad hoc network MAY move at any time without notice,
and MAY even move continuously, but we assume that the speed with
which nodes move is moderate with respect to the packet transmission
latency and wireless transmission range of the particular underlying
network hardware in use. In particular, DSR can support very
rapid rates of arbitrary node mobility, but we assume that nodes do
not continuously move so rapidly as to make the flooding of every
individual data packet the only possible routing protocol.

A common feature of many network interfaces, including most current
LAN hardware for broadcast media such as wireless, is the ability
to operate the network interface in "promiscuous" receive mode.
This mode causes the hardware to deliver every received packet to
the network driver software without filtering based on link-layer
destination address. Although we do not require this facility, some
of our optimizations can take advantage of its availability. Use
of promiscuous mode does increase the software overhead on the CPU,

Johnson, et al Expires 24 August 2003 [Page 3]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

but we believe that wireless network speeds are more the inherent
limiting factor to performance in current and future systems; we also
believe that portions of the protocol are suitable for implementation
directly within a programmable network interface unit to avoid this
overhead on the CPU [16]. Use of promiscuous mode may also increase
the power consumption of the network interface hardware, depending
on the design of the receiver hardware, and in such cases, DSR can
easily be used without the optimizations that depend on promiscuous
receive mode, or can be programmed to only periodically switch the
interface into promiscuous mode. Use of promiscuous receive mode is
entirely optional.

Wireless communication ability between any pair of nodes may at
times not work equally well in both directions, due for example to
differing antenna or propagation patterns or sources of interference
around the two nodes [1, 20]. That is, wireless communications
between each pair of nodes will in many cases be able to operate
bidirectionally, but at times the wireless link between two nodes
may be only unidirectional, allowing one node to successfully send
packets to the other while no communication is possible in the
reverse direction. Although many routing protocols operate correctly
only over bidirectional links, DSR can successfully discover and
forward packets over paths that contain unidirectional links. Some
MAC protocols, however, such as MACA [19], MACAW [2], or IEEE
802.11 [13], limit unicast data packet transmission to bidirectional
links, due to the required bidirectional exchange of RTS and CTS
packets in these protocols and due to the link-layer acknowledgement
feature in IEEE 802.11; when used on top of MAC protocols 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
origin of the original route.

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
assignment [8]), although the method of such assignment is outside
the scope of this specification.

Johnson, et al Expires 24 August 2003 [Page 4]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

3. DSR Protocol Overview

This section provides an overview of the operation of the DSR
protocol. The basic version of DSR uses explicit "source routing",
in which each data packet sent carries in its header the complete,
ordered list of nodes through which the packet will pass. This use
of explicit source routing allows the sender to select and control
the routes used for its own packets, supports the use of multiple
routes to any destination (for example, for load balancing), and
allows a simple guarantee that the routes used are loop-free; by
including this source route in the header of each data packet, other
nodes forwarding or overhearing any of these packets can also easily
cache this routing information for future use. Section 3.1 describes
this basic operation of Route Discovery, Section 3.2 describes basic
Route Maintenance, and Sections 3.3 and 3.4 describe additional
features of these two parts of DSR's operation. Section 3.5 then
describes an optional, compatible extension to DSR, known as "flow
state", that allows the routing of most packets without an explicit
source route header in the packet, while still preserves the
fundamental properties of DSR's operation.

3.1. Basic DSR Route Discovery

When some source node originates a new packet addressed to some
destination node, the source node places in the header of the packet
a "source route" giving the sequence of hops that the packet is to
follow on its way to the destination. Normally, the sender will
obtain a suitable source route by searching its "Route Cache" of
routes previously learned; if no route is found in its cache, it will
initiate the Route Discovery protocol to dynamically find a new route
to this destination node. In this case, we call the source node
the "initiator" and the destination node the "target" of the Route
Discovery.

For example, suppose a node A is attempting to discover a route to
node E. The Route Discovery initiated by node A in this example
would proceed as follows:

^ "A" ^ "A,B" ^ "A,B,C" ^ "A,B,C,D"
| id=2 | id=2 | id=2 | id=2
+-----+ +-----+ +-----+ +-----+ +-----+
| A |---->| B |---->| C |---->| D |---->| E |
+-----+ +-----+ +-----+ +-----+ +-----+
| | | |
v v v v

To initiate the Route Discovery, node A transmits a "Route
Request" as a single local broadcast packet, which is received by
(approximately) all nodes currently within wireless transmission

Johnson, et al Expires 24 August 2003 [Page 5]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

range of A, including node B in this example. Each Route Request
identifies the initiator and target of the Route Discovery, and
also contains a unique request identification (2, in this example),
determined by the initiator of the Request. Each Route Request also
contains a record listing the address of each intermediate node
through which this particular copy of the Route Request has been
forwarded. This route record is initialized to an empty list by the
initiator of the Route Discovery. In this example, the route record
initially lists only node A.

When another node receives this Route Request (such as node B in this
example), if it is the target of the Route Discovery, it returns
a "Route Reply" to the initiator of the Route Discovery, giving
a copy of the accumulated route record from the Route Request;
when the initiator receives this Route Reply, it caches this route
in its Route Cache for use in sending subsequent packets to this
destination.

Otherwise, if this node receiving the Route Request has recently seen
another Route Request message from this initiator bearing this same
request identification and target address, or if this node's own
address is already listed in the route record in the Route Request,
this node discards the Request. Otherwise, this node appends its
own address to the route record in the Route Request and propagates
it by transmitting it as a local broadcast packet (with the same
request identification). In this example, node B broadcast the Route
Request, which is received by node C; nodes C and D each also, in
turn, broadcast the Request, resulting in a copy of the Request being
received by node E.

In returning the Route Reply to the initiator of the Route Discovery,
such as in this example, node E replying back to node A, node E will
typically examine its own Route Cache for a route back to A, and if
found, will use it for the source route for delivery of the packet
containing the Route Reply. Otherwise, E SHOULD perform its own
Route Discovery for target node A, but to avoid possible infinite
recursion of Route Discoveries, it MUST piggyback this Route Reply
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
packet [31], on a Route Request using this same mechanism.

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
the source route on the packet carrying the Route Reply itself. For
MAC protocols such as IEEE 802.11 that require a bidirectional frame
exchange as part of the MAC protocol [13], the discovered source
route MUST be reversed in this way to return the Route Reply since it
tests the discovered route to ensure it is bidirectional before the
Route Discovery initiator begins using the route; this route reversal
also avoids the overhead of a possible second Route Discovery.

Johnson, et al Expires 24 August 2003 [Page 6]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

However, this route reversal technique will prevent the discovery of
routes using unidirectional links, and in wireless environments where
the use of unidirectional links is permitted, such routes may in some
cases be more efficient than those with only bidirectional links, or
they may be the only way to achieve connectivity to the target node.

When initiating a Route Discovery, the sending node saves a copy of
the original packet (that triggered the Discovery) in a local buffer
called the "Send Buffer". The Send Buffer contains a copy of each
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
the Send Buffer is logically associated with the time that it was
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 from overflowing, a FIFO or other replacement strategy
MAY also be used to evict packets even before they expire.

While a packet remains in the Send Buffer, the node SHOULD
occasionally initiate a new Route Discovery for the packet's
destination address. However, the node MUST limit the rate at which
such new Route Discoveries for the same address are initiated, since
it is possible that the destination node is not currently reachable.
In particular, due to the limited wireless transmission range and the
movement of the nodes in the network, the network may at times become
partitioned, meaning that there is currently no sequence of nodes
through which a packet could be forwarded to reach the destination.
Depending on the movement pattern and the density of nodes in the
network, such network partitions may be rare or may be common.

If a new Route Discovery was initiated for each packet sent by a
node in such a partitioned network, a large number of unproductive
Route Request packets would be propagated throughout the subset
of the ad hoc network reachable from this node. In order to
reduce the overhead from such Route Discoveries, a node SHOULD use
an exponential back-off algorithm to limit the rate at which it
initiates new Route Discoveries for the same target, doubling the
timeout between each successive Discovery initiated for the same
target. If the node attempts to send additional data packets to this
same destination node more frequently than this limit, the subsequent
packets SHOULD be buffered in the Send Buffer until a Route Reply is
received giving a route to this destination, but the node MUST NOT
initiate a new Route Discovery until the minimum allowable interval
between new Route Discoveries for this target has been reached. This
limitation on the maximum rate of Route Discoveries for the same
target is similar to the mechanism required by Internet nodes to
limit the rate at which ARP Requests are sent for any single target
IP address [3].

Johnson, et al Expires 24 August 2003 [Page 7]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

3.2. Basic DSR Route Maintenance

When originating or forwarding a packet using a source route, each
node transmitting the packet is responsible for confirming that data
can flow over the link from that node to the next hop. For example,
in the 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 |
+-----+ +-----+ +-----+ +-----+ +-----+

In this case, node A is responsible for the link from A to B, node B
is responsible for the link from B to C, node C is responsible for
the link from C to D, node D is responsible for the link from D to E.

An acknowledgement can provide confirmation that a link is capable of
carrying data, and in wireless networks, acknowledgements are often
provided at no cost, either as an existing standard part of the MAC
protocol in use (such as the link-layer acknowledgement frame defined
by IEEE 802.11 [13]), or by a "passive acknowledgement" [18] (in
which, for example, B confirms receipt at C by overhearing C transmit
the packet when forwarding it on to D).

If a built-in acknowledgement mechanism is not available, the
node transmitting the 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 unidirectional, this software acknowledgement could travel over a
different, multi-hop path.

After an acknowledgement has been received from some neighbor, a node
MAY choose to not require acknowledgements from that neighbor for a
brief period of time, unless the network interface connecting a node
to that neighbor always receives an acknowledgement in response to
unicast traffic.

When a software acknowledgement is used, the acknowledgement
request SHOULD be retransmitted up to a maximum number of times.
A retransmission of the acknowledgement request can be sent as a
separate packet, piggybacked on a retransmission of the original
data packet, or piggybacked on any packet with the same next-hop
destination that does not also contain a software acknowledgement.

After the acknowledgement request has been retransmitted the maximum
number of times, if no acknowledgement has been received, then the
sender treats the link to this next-hop destination as currently
"broken". It SHOULD remove this link from its Route Cache and
SHOULD return a "Route Error" to each node that has sent a packet

Johnson, et al Expires 24 August 2003 [Page 8]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

routed over that link since an acknowledgement was last received.
For example, in the situation shown above, if C does not receive
an acknowledgement 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 acknowledgement
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).

Johnson, et al Expires 24 August 2003 [Page 9]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

3.3. Additional Route Discovery Features

3.3.1. Caching Overheard Routing Information

A node forwarding or otherwise overhearing any packet SHOULD add all
usable routing information from that packet to its own Route Cache.
The usefulness of routing information in a packet depends on the
directionality characteristics of the physical medium (Section 2), as
well as the MAC protocol being used. Specifically, three distinct
cases are possible:

- Links in the network frequently are capable of operating only
unidirectionally (not bidirectionally), and the MAC protocol in
use in the network is capable of transmitting unicast packets
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
transmitting unicast packets over unidirectional links;
only bidirectional links can be used by the MAC protocol for
transmitting unicast packets. For example, the IEEE 802.11
Distributed Coordination Function (DCF) MAC protocol [13]
is capable of transmitting a unicast packet only over a
bidirectional link, since the MAC protocol requires the return of
a link-level acknowledgement packet from the receiver and also
optionally requires the bidirectional exchange of an RTS and CTS
packet between the transmitter and receiver nodes.

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
being returned in a Route Reply SHOULD all be cached by any node in
the "forward" direction; any node SHOULD cache this information from
any such packet received, whether the packet was addressed to this
node, sent to a broadcast (or multicast) MAC address, or overheard
while the node's network interface is in promiscuous mode. However,
the "reverse" direction of the links identified in such packet
headers SHOULD NOT be cached.

Johnson, et al Expires 24 August 2003 [Page 10]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

For example, in the situation shown below, node A is using a source
route to communicate with node E:

+-----+ +-----+ +-----+ +-----+ +-----+
| A |---->| B |---->| C |---->| D |---->| E |
+-----+ +-----+ +-----+ +-----+ +-----+

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
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
"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
unidirectional.

In the second case above, in which links may occasionally operate
unidirectionally, the links described above SHOULD be cached in both
directions. Furthermore, in this case, if node X overhears (e.g.,
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
these links as well, also including the link from C to X over which
it overheard the packet.

In the final case, in which the MAC protocol requires physical
bidirectionality for unicast operation, links from a source route
SHOULD be cached in both directions, except when the packet also
contains a Route Reply, in which case only the links already
traversed in this source route SHOULD be cached, but the links not
yet traversed in this route SHOULD NOT be cached.

3.3.2. Replying to Route Requests using Cached Routes

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
Request. If found, the node generally returns a Route Reply to the
initiator itself rather than forwarding the Route Request. In the
Route Reply, this node sets the route record to list the sequence of
hops over which this copy of the Route Request was forwarded to it,
concatenated with the source route to this target obtained from its
own Route Cache.

However, before transmitting a Route Reply packet that was generated
using information from its Route Cache in this way, a node MUST
verify that the resulting route being returned in the Route Reply,
after this concatenation, contains no duplicate nodes listed in the
route record. For example, the figure below illustrates a case in

Johnson, et al Expires 24 August 2003 [Page 11]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

which a Route Request for target E has been received by node F, and
node F already has in its Route Cache a route from itself to E:

+-----+ +-----+ +-----+ +-----+
| A |---->| B |- >| D |---->| E |
+-----+ +-----+ \ / +-----+ +-----+
\ /
\ +-----+ /
>| C |-
+-----+
| ^
v |
Route Request +-----+
Route: A - B - C - F | F | Cache: C - D - E
+-----+

The concatenation of the accumulated route record from the Route
Request and the cached route from F's Route Cache would include a
duplicate node in passing from C to F and back to C.

Node F in this case could attempt to edit the route to eliminate the
duplication, resulting in a route from A to B to C to D and on to E,
but in this case, node F would not be on the route that it returned
in its own Route Reply. DSR Route Discovery prohibits node F
from returning such a Route Reply from its cache; this prohibition
increases the probability that the resulting route is valid, since
node F in this case should have received a Route Error if the route
had previously stopped working. Furthermore, this prohibition
means that a future Route Error traversing the route is very likely
to pass through any node that sent the Route Reply for the route
(including node F), which helps to ensure that stale data is removed
from caches (such as at F) in a timely manner; otherwise, the next
Route Discovery initiated by A might also be contaminated by a Route
Reply from F containing the same stale route. If node F, due to this
restriction on returning a Route Reply based on information from its
Route Cache, does not return such a Route Reply, node F propagates
the Route Request normally.

3.3.3. Preventing Route Reply Storms

The ability for nodes to reply to a Route Request based on
information in their Route Caches, as described in Section 3.3.2,
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.

Johnson, et al Expires 24 August 2003 [Page 12]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

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 sending their Replies after this node.

Johnson, et al Expires 24 August 2003 [Page 13]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

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

3.3.4. Route Request Hop Limits

Each Route Request message contains a "hop limit" that may be used
to limit the number of intermediate nodes allowed to forward that
copy of the Route Request. This hop limit is implemented using the
Time-to-Live (TTL) field in the IP header of the packet carrying
the Route Request. As the Request is forwarded, this limit is
decremented, and the Request packet is discarded if the limit reaches
zero before finding the target. This Route Request hop limit can be
used to implement a variety of algorithms for controlling the spread
of a Route Request during a Route Discovery attempt.

For example, a node MAY use this hop limit to implement a
"non-propagating" Route Request as an initial phase of a Route
Discovery. A node using this technique sends its first Route Request
attempt for some target node using a hop limit of 1, such that any
node receiving the initial transmission of the Route Request will
not forward the Request to other nodes by re-broadcasting it. This
form of Route Request is called a "non-propagating" Route Request;
it provides an inexpensive method for determining if the target is
currently a neighbor of the initiator or if a neighbor node has a
route to the target cached (effectively using the neighbors' Route
Caches as an extension of the initiator's own Route Cache). If no
Route Reply is received after a simple and
efficient routing protocol designed specifically short timeout, then the node sends a
"propagating" Route Request (i.e., with no hop limit) for the target
node.

As another example, a node MAY use in multi-hop
wireless ad hoc networks of mobile nodes. Using DSR, this hop limit to implement an
"expanding ring" search for the network target [16]. A node using this
technique sends an initial non-propagating Route Request as described
above; if no Route Reply is completely self-organizing and self-configuring, requiring received for it, the node originates
another Route Request with a hop limit of 2. For each Route Request
originated, if no
existing network infrastructure or administration. Network nodes
cooperate Route Reply is received for it, the node doubles
the hop limit used on the previous attempt, to forward packets progressively explore
for each other the target node without allowing the Route Request to allow communication propagate
over multiple "hops" between nodes not directly within wireless
transmission range of one another. As nodes in the network move
about or join or leave entire network. However, this expanding ring search
approach could have the network, and as wireless transmission
conditions such as sources effect of interference change, all routing is
automatically determined and maintained by the DSR routing protocol.
Since increasing the number or sequence average latency of intermediate hops needed to reach any
destination may change at any time, the resulting network topology
may be quite rich
Route Discovery, since multiple Discovery attempts and rapidly changing.

The DSR protocol allows nodes to dynamically discover timeouts may
be needed before discovering a source route across multiple network hops to any destination in the ad hoc
network. Each data target node.

Johnson, et al Expires 24 August 2003 [Page 14]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

3.4. Additional Route Maintenance Features

3.4.1. Packet Salvaging

When an intermediate node forwarding a packet sent then carries in its header the
complete, ordered list of nodes detects through which Route
Maintenance that the next hop along the route for that packet will pass,
allowing packet routing is
broken, if the node has another route to be trivially loop-free and avoiding the
need for up-to-date routing information packet's destination in
its Route Cache, the intermediate nodes
through which node SHOULD "salvage" the packet is forwarded. By including this rather than
discarding it. To salvage a packet, the node replaces the original
source route in on the header of each data packet, other nodes forwarding or
overhearing any of these packets can also easily cache this routing
information for future use.

In designing DSR, we sought to create a routing protocol that had
very low overhead yet was able to react very quickly to changes in packet with the network. route from its Route Cache. The DSR protocol provides highly reactive service in
order
node then forwards the packet to help ensure successful delivery of data packets in spite of the next node movement or other changes indicated along this
source route. For example, in network conditions.

The DSR protocol is composed the situation shown in the example of two main mechanisms that work
together
Section 3.2, if node C has another route cached to allow node E, it can
salvage the packet by replacing the discovery and maintenance of source routes original route in the ad hoc network:

- packet with
this new route from its own Route Discovery is Cache, rather than discarding the mechanism by which
packet.

When salvaging a node S wishing to
send packet, a count is maintained in the packet of the
number of times that it has been salvaged, to prevent a destination node D obtains a source route
to D. Route Discovery is used only when S attempts single packet
from being salvaged endlessly. Otherwise, it could be possible for
the packet to send enter a routing loop, as different nodes repeatedly
salvage the packet to D and does not already know a replace the source route on the packet with
routes to D.

- each other.

As described in Section 3.2, an intermediate node, such as in this
case, that detects through Route Maintenance that the next hop along
the route for a packet that it is forwarding is broken, the mechanism by which node S is able
to detect, while using also
SHOULD return a source route Route Error to D, if the network
topology has changed such that it can no longer use its route
to D because a original sender of the packet,
identifying the link along over which the route no longer works. packet could not be forwarded.
If the node sends this Route Error, it SHOULD originate the Route
Error before salvaging the packet.

3.4.2. Queued Packets Destined over a Broken Link

When an intermediate node forwarding a packet detects through Route
Maintenance indicates a source route is broken, S can attempt to
use any other route it happens to know that the next-hop link along the route for that packet
is broken, in addition to D, or can invoke handling that packet as defined for Route
Discovery again to find
Maintenance, the node SHOULD also handle in a similar way any pending
packets that it has queued that are destined over this new route broken
link. Specifically, the node SHOULD search its Network Interface
Queue and Maintenance Buffer (Section 4.5) for subsequent packets to D. for which
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
follows:

- Remove the packet from the node's Network Interface Queue and
Maintenance Buffer.

Johnson, et al Expires 21 24 August 2002 2003 [Page 1] 15]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002 2003

- Originate a Route Maintenance Error for this route is used only when S is actually
sending packets packet to D.

In DSR, Route Discovery and Route Maintenance each operate entirely
"on demand". In particular, unlike other protocols, DSR requires no
periodic packets of any kind at any layer within the network. For
example, DSR does not use any periodic routing advertisement, link
status sensing, or neighbor detection packets, and does not rely on
these functions from any underlying protocols in the network. This
entirely on-demand behavior and lack original sender of periodic activity allows
the number of overhead packets caused by DSR to scale all packet, using the way
down to zero, when all nodes are approximately stationary with
respect to each other and all routes needed for current communication
have already been discovered. As nodes begin to move more or procedure described in Section 8.3.4, as communication patterns change, if
the node had already reached the routing packet overhead maximum number of
DSR automatically scales to only retransmission
attempts for that needed to track the routes
currently packet for Route Maintenance. However, in use. Network topology changes not affecting routes
currently
sending such Route Errors for queued packets in use are ignored and do not cause reaction from the
protocol.

In response to a
single Route Discovery (as well as through routing
information from other packets overheard), a new broken link detected, the node may learn and cache
multiple routes SHOULD send no more
than one Route Error to each original sender of any destination. This allows of these
packets.

- If the reaction to
routing changes to be much more rapid, since a node with multiple
routes to a destination can try has another cached route if the one it
has been using should fail. This caching of multiple routes also
avoids the overhead of needing to perform a new Route Discovery each
time a route the packet's IP
Destination Address in use breaks.

The operation of both Route Discovery and its Route Maintenance in DSR
are designed to allow unidirectional links and asymmetric routes
to be easily supported. In particular, Cache, the node SHOULD
salvage the packet as noted described in Section 2, 8.3.6. Otherwise, the
node SHOULD discard the packet.

3.4.3. Automatic Route Shortening

Source routes in
wireless networks, it is possible that a link between two use MAY be automatically shortened if one or more
intermediate nodes may
not work equally well in both directions, due the route become no longer necessary. This
mechanism of automatically shortening routes in use is somewhat
similar to differing antenna
or propagation patterns or sources the use of interference. DSR allows such
unidirectional links passive acknowledgements [18]. In particular,
if a node is able to be used when necessary, improving overall
performance and overhear a packet carrying a source route (e.g.,
by operating its network connectivity interface in promiscuous receive mode), then
this node examines the system.

This document specifies the operation unexpended portion of that source route. If
this node is not the DSR protocol intended next-hop destination for
routing unicast IPv4 packets the packet
but is named in multi-hop wireless ad hoc networks.
Advanced, optional features, such as Quality of Service (QoS) support
and efficient multicast routing, and operation the later unexpended portion of DSR with IPv6 [6], the packet's source
route, then it can infer that the intermediate nodes before itself in
the source route are covered no longer needed in other documents. The specification of DSR the route. For example, the
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
and to E:

+-----+ +-----+ +-----+ +-----+ +-----+
| A |---->| B |---->| C | | D | | E |
+-----+ +-----+ +-----+ +-----+ +-----+
\ ^
\ /
---------------------

In this
document provides case, this node (node D) SHOULD return a compatible base on which such features can be
added, either independently or by integration "gratuitous" Route
Reply to the original sender of the packet (node A). The Route
Reply gives the shorter route as the concatenation of the portion of
the original source route up through the node that transmitted the
overheard packet (node B), plus the suffix of the original source
route beginning with the DSR operation
specified here.

The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in node returning the gratuitous Route Reply
(node D). In this
document are example, the route returned in the gratuitous Route
Reply message sent from D to be interpreted A gives the new route as described in RFC 2119 [4]. the sequence of
hops from A to B to D to E.

Johnson, et al Expires 21 24 August 2002 2003 [Page 2] 16]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

2. Assumptions

When deciding whether to forward
packets for other nodes in the network.

The diameter of an ad hoc network is the minimum number of hops
necessary for return a packet to reach from any node located at one extreme
edge of the ad hoc network to another node located at the opposite
extreme. We assume that this diameter will often be small (e.g.,
perhaps 5 or 10 hops), but may often be greater than 1.

Packets may be lost or corrupted gratuitous Route Reply in transmission on the wireless
network. We assume that this way,
a node receiving a corrupted packet can
detect the error and discard the packet.

Nodes within the ad hoc network MAY move at any time without notice,
and MAY even move continuously, but we assume factor in additional information beyond the fact that it
was able to overhear the speed with
which nodes move is moderate with respect packet. For example, the node MAY decide to
return the packet transmission
latency and wireless transmission range of gratuitous Route Reply only when the particular underlying
network hardware in use. overheard packet is
received with a signal strenth or signal-to-noise ratio above some
specific threshold. In particular, DSR can support very
rapid rates of arbitrary addition, each node mobility, but we assume that nodes do
not continuously move so rapidly maintains a Gratuitous
Route Reply Table, as described in Section 4.4, to make limit the flooding rate at
which it originates gratuitous Route Replies for the same returned
route.

3.4.4. Increased Spreading of every
individual Route Error Messages

When a source node receives a Route Error for a data packet that
it originated, this source node propagates this Route Error to its
neighbors by piggybacking it on its next Route Request. In this way,
stale information in the only possible routing protocol.

A common feature caches of many network interfaces, including most current
LAN hardware nodes around this source node will
not generate Route Replies that contain the same invalid link for broadcast media such as wireless, is
which this source node received the ability
to operate Route Error.

For example, in the network interface situation shown in "promiscuous" receive mode.
This mode causes the hardware example of Section 3.2,
node A learns from the Route Error message from C, that the link
from C to deliver every received packet D is currently broken. It thus removes this link from
its own Route Cache and initiates a new Route Discovery (if it has
no other route to E in its Route Cache). On the network driver software without filtering based on link-layer
destination address. Although we do not require Route Request
packet initiating this facility, some
of our optimizations can take advantage of its availability. Use Route Discovery, node A piggybacks a copy
of promiscuous mode does increase the software overhead on the CPU,
but we believe this Route Error, ensuring that wireless network speeds are more the inherent
limiting factor Route Error spreads well to performance in current
other nodes, and future systems; we also
believe guaranteeing that portions of the protocol are suitable for implementation
directly within a programmable network interface unit any Route Reply that it receives
(including those from other node's Route Caches) in response to avoid this
overhead on
Route Request does not contain a route that assumes the CPU [14]. Use existence of promiscuous mode may also increase
this broken link.

3.5. Optional DSR Flow State Extension

This section describes an optional, compatible extension to the power consumption DSR
protocol, known as "flow state", that allows the routing of most
packets without an explicit source route header in the network interface hardware, depending
on packet. The
DSR flow state extension further reduces the design overhead of the receiver hardware, and in protocol
yet still preserves the fundamental properties of DSR's operation.
Once a sending node has discovered a source route such cases, DSR can
easily be used without as through
DSR's Route Discovery mechanism, the optimizations that depend flow state mechanism allows the
sending node to establish hop-by-hop forwarding state within the
network, based on promiscuous
receive mode, or can be programmed this source route, to enable each node along the
route to forward the packet to only periodically switch the
interface into promiscuous mode. Use next hop based on the node's own
local knowledge of promiscuous receive mode the flow along which this packet is
entirely optional.

Wireless communication ability between any pair of nodes may at
times not work equally well in both directions, due for example being routed.
Flow state is dynamically initialized by the first packet using a
source route and is then able to
differing antenna or propagation patterns or sources route subsequent packets along
the same flow without use of interference a source route header in the packet.
The state established at each hop along a flow is "soft state" and

Johnson, et al Expires 21 24 August 2002 2003 [Page 3] 17]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

around the two nodes [1, 18]. That is, wireless communications
between each pair of nodes will in many cases be able to operate
bidirectionally, but at times the wireless link between two nodes
may be only unidirectional, allowing one node to successfully send
packets to the other while 2003

thus automatically expires when no communication is possible in the
reverse direction. Although many routing protocols operate correctly
only over bidirectional links, DSR can successfully discover longer needed and
forward packets over paths that contain unidirectional links. Some
MAC protocols, however, such can be quickly
recreated as MACA [17], MACAW [2], or IEEE
802.11 [11], limit unicast data necessary. Extending DSR's basic operation based on an
explicit source route in the header of each packet transmission to bidirectional
links, due to routed, the required bidirectional exchange flow
state extension operates as a form of RTS and CTS "implicit source routing" by
preserving DSR's basic operation but removing the explicit source
route from packets.

3.5.1. Flow Establishment

A source node sending packets in these protocols and due to some destination node MAY use the link-layer acknowledgment
feature in IEEE 802.11; when used on top of MAC protocols such as
these,
DSR can take advantage of additional optimizations, such as
the ability flow state extension described here to reverse establish a source route to obtain
that destination as a flow. A "flow" is a route back from the source to
the
origin of destination represented by hop-by-hop forwarding state within
the nodes along the original route.

The IP address used Each flow is uniquely identified by a
combination of the source node address, the destination node address,
and a flow identifier (flow ID) chosen by the source node.

Each flow ID is a 16-bit unsigned integer. Comparison between
different flow IDs MUST be performed modulo 2**16. For example,
using an implementation in the C programming language, a
flow ID value (a) is greater than another flow ID value (b) if
((short)((a) - (b)) > 0), if a C language "short" data type is
implemented as a 16-bit signed integer.

A DSR protocol MAY Flow State header in a packet identifies the flow ID to
be assigned
by followed in forwarding that packet. From a given source to
some destination, any mechanism (e.g., static assignment or use number of DHCP different flows MAY exist and
be in use, for dynamic
assignment [7]), although the method example following different sequences of such assignment is outside hops to
reach the scope destination. One of this specification.

Johnson, et al Expires 21 August 2002 [Page 4]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 February 2002

3. DSR Protocol Overview

3.1. Basic DSR Route Discovery

When some source node originates a new packet addressed these flows may be considered to some
destination node, be
the "default" flow from that source to that destination. A node places in the
receiving a packet with neither a DSR Options header of specifying the packet
a source
route giving to be taken (with a Source Route option in the sequence of hops that DSR Options
header) nor a DSR Flow State header specifying the packet is to
follow on its way flow ID to be
followed, is forwarded along the destination. Normally, default flow for the sender will
obtain a suitable source route by searching its "Route Cache" of
routes previously learned; if no route is found and
destination addresses specified in its cache, it will
initiate the Route Discovery protocol to dynamically find packet's IP header.

In establishing a new route
to this destination node. In this case, we call flow, the source node generates a nonzero
16-bit flow ID greater than any unexpired flow IDs for this
(source, destination) pair. If the "initiator" and source wishes for this flow to
become the destination node default flow, the "target" low bit of the Route
Discovery.

For example, suppose a node A flow ID MUST be set (the
flow ID is attempting to discover a route to
node E. an odd number); otherwise, the low bit MUST NOT be set
(the flow ID is an even number).

The Route Discovery initiated by source node A in this example
would proceed as follows:

To initiate establishing the Route Discovery, node A new flow then transmits a "Route
Request" as packet
containing a single local broadcast packet, which is received by
(approximately) all nodes currently within wireless transmission
range of A, including DSR Options header with a Source Route option; to
establish the flow, the source node B also MUST include in this example. Each Route Request
identifies the initiator and target of packet
a DSR Flow State header, with the Route Discovery, Flow ID field set to the chosen
flow ID for the new flow, and
also contains MUST include a unique request identification (2, Timeout option in the
DSR Options header, giving the lifetime after which state information

Johnson, et al Expires 24 August 2003 [Page 18]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

about this example),
determined by flow is to expire. This packet will generally be a normal
data packet being sent from this sender to the initiator of receiver (for example,
the Request. Each Route Request first packet sent after discovering the new route) but is also
contains
treated as a record listing the address of each intermediate "flow establishment" packet.

The source node
through which records this particular copy of flow in its Flow Table for future use,
setting the Route Request has been
forwarded. This route record is initialized TTL in this Flow Table entry to an empty list by be the
initiator of value used in the Route Discovery. In this example,
TTL field in the route record
initially lists only node A.

When another node receives packet's IP header and setting the Lifetime in this Route Request (such as node B
entry to be the lifetime specified in the Timeout option in the DSR
Options header.

Any further packets sent with this
example), if it is flow ID before the target of timeout that
also contain a DSR Options header with a Source Route option MUST use
this same source route in the Source Route Discovery, it returns option.

3.5.2. Receiving and Forwarding Establishment Packets

Packets intended to establish a flow, as described in Section 3.5.1,
contain a DSR Options header with a "Route Reply" to the initiator of the Source Route Discovery, giving
a copy of option, and are
forwarded along the accumulated route record from indicated route. A node implementing the Route Request; DSR
flow state extension, when the initiator receives this Route Reply, it caches this route receiving and forwarding such a DSR
packet, also keeps some state in its Route Cache for use in sending subsequent packets own Flow Table to enable it
to forward future packets that are sent along this
destination.

Otherwise, flow with only
the flow ID specified. Specifically, if this node receiving the Route Request has recently seen
another Route Request message from packet also contains
a DSR Flow State header, this initiator bearing packet SHOULD cause an entry to be
established for this same

Johnson, et al Expires 21 August 2002 [Page 5]

INTERNET-DRAFT flow in the Flow Table of each node along the
packet's route.

The Dynamic Source Routing Protocol 21 February 2002

request identification and target address, or if this node's own
address Hop Count field of the DSR Flow State header is already listed also stored in
the route record Flow Table, as is Lifetime option specified in the Route Request,
this node discards the Request. Otherwise, this node appends its
own address to DSR Options
header.

If the route record Flow ID is odd and there is no flow in the Route Request and propagates
it by transmitting it as a local broadcast packet (with Flow Table with
Flow ID greater than the same
request identification). In received Flow ID, set the default Flow ID
for this example, node B broadcast (IP Source Address, IP Destination Address) pair to the Route
Request, which is
received by node C; nodes C Flow ID, and D each also, in
turn, broadcast the Request, resulting in a copy TTL of the Request being
received by packet is recorded.

The Flow ID option is removed before final delivery of the packet.

3.5.3. Sending Packets Along Established Flows

When a flow is established as described in Section 3.5.1, a packet
is sent which establishes state in each node E.

In returning along the Route Reply to route.
This state is soft; that is, the initiator protocol contains mechanisms for
recovering from the loss of this state. However, the Route Discovery,
such as use of these
mechanisms may result in this example, node E replying back to node A, node E will
typically examine its own Route Cache reduced performance for packets sent
along flows with forgotten state. As a route back to A, and if
found, will use result, it for the source route for delivery of is desirable
to differentiate behavior based on whether or not the packet
containing sender is

Johnson, et al Expires 24 August 2003 [Page 19]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

reasonably certain that the Route Reply. Otherwise, E SHOULD perform its own
Route Discovery for target flow state exists on each node A, but along
the route. We define a flow's state to avoid possible infinite
recursion be "established end-to-end"
if the Flow Tables of Route Discoveries, it MUST piggyback this Route Reply all nodes on the packet containing its own Route Request route contains forwarding
information for A. It that flow. While it is also
possible impossible to piggyback other small data packets, such as a TCP SYN
packet [28], on detect whether
or not a Route Request using this same mechanism.

Node E could instead simply reverse flow's state has been established end-to-end without sending
packets, implementations may make reasonable assumptions about the sequence
retention of hops in flow state and the route
record probability that it is trying an establishment
packet has been seen by all nodes on the route.

A source wishing to send in a packet along an established flow
determines if the flow state has been established end-to-end. If
it has not, a DSR Options header with Source Route Reply, and use option with this as
the source
flow's route on is added to the packet carrying packet. The source SHOULD set the Route Reply itself. For
MAC protocols such as IEEE 802.11 that require a bidirectional frame
exchange as part
Flow ID field of the MAC protocol [11], DSR Flow State header either to the discovered source
route MUST be reversed in flow ID
previously associated with this way flow's route or to return the Route Reply since zero. If it
tests sets
the discovered route Flow ID field to ensure any other value, it is bidirectional before the
Route Discovery initiator begins using MUST follow the route; this route reversal
also avoids processing
steps in Section 3.5.1 for establishing a new flow ID. If it sets the overhead of
Flow ID field to a possible second Route Discovery.
However, this route reversal technique will prevent nonzero value, it MUST include a Timeout option
with a value not greater than the discovery of
routes using unidirectional links, and timeout remaining in wireless environments where the use of unidirectional links node's
Flow Table, and if its TTL is permitted, such routes may not equal to that specified in some
cases be more efficient than those with only bidirectional links, or
they may the Flow
Table, the flow MUST NOT be used as a default flow in the future.

Once flow state has been established end-to-end for non-default
flows, a source adds a DSR Flow State header to each packet it wishes
to send along that flow, setting the only way to achieve connectivity Flow ID field to the target node.

When initiating a flow ID of
that flow. A Source Route Discovery, option SHOULD NOT be added to the sending node saves a copy of packet,
though if one is, then the original packet (that triggered steps for processing flows that have not
been established end to end MUST be followed.

Once flow state has been established end-to-end for default flows,
sources sending packets with IP TTL equal to the Discovery) TTL value in a the
local buffer
called Flow Table entry for this flow then transmit the "Send Buffer". The Send Buffer contains a copy of each packet that cannot be transmitted by to the
next hop. In this node because it does not
yet have case, a source route DSR Flow State header SHOULD NOT be added
to the packet's destination. Each packet in and a DSR Options header likewise SHOULD NOT be added
to the Send Buffer is logically associated with packet; though if one is, the time that it was
placed into steps for sending packets along
non-default flows MUST be followed. If the Send Buffer and IP TTL is discarded after residing not equal to
the TTL value in the
Send Buffer for some timeout period; if necessary for preventing local Flow Table, then the
Send Buffer from overflowing, steps for processing
a FIFO or other replacement strategy
MAY also non-default flow MUST be used followed.

3.5.4. Receiving and Forwarding Packets Sent Along Established Flows

The handling of packets containing a DSR Options header with
both a nonzero Flow ID and a Source Route option is described in
Section 3.5.2. The Flow ID is ignored when it is equal to evict zero.
This section only describes handling of packets even before they expire.

While without a Source
Route option.

If a node receives a packet remains in the Send Buffer, the node SHOULD
occasionally initiate with a new Route Discovery for the packet's
destination address. However, Flow ID in the node MUST limit DSR Options
header that indicates an unexpired flow in the rate at which node's Flow Table, it

Johnson, et al Expires 21 24 August 2002 2003 [Page 6] 20]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

such new Route Discoveries for 2003

increments the same address are initiated, since
it is possible that Hop Count in the destination DSR Options header and forwards the
packet to the next hop indicated in the Flow Table.

If a node is receives a packet with a Flow ID that indicates a flow not
currently reachable.
In particular, due to in the limited wireless transmission range node's Flow Table, it returns a Route Error of type
UNKNOWN_FLOW with Error Destination and IP Destination addresses
copied from the
movement IP Source of the nodes in the network, packet triggering the network may at times become
partitioned, meaning that there is currently no sequence of nodes
through which a error. This
error packet could SHOULD be forwarded MAC-destined to reach the destination.
Depending on node from which it was
received; if it cannot confirm reachability of the movement pattern and previous node
using Route Maintenance, it MUST send the density of nodes error as described in
Section 8.1.1. The node sending the error SHOULD attempt to salvage
the
network, such network partitions may be rare or may be common.

If a new Route Discovery was initiated for each packet sent by triggering the Route Error. If it does salvage the
packet, it MUST zero the Flow ID.

If a node receives a packet with no DSR Options header and no DSR
Flow State header, it checks the Default Flow Table. If there is
an entry, it forwards to the next hop indicated in such a partitioned network, the Flow Table
for the default flow. Otherwise, it returns a large number of unproductive Route Request packets would be propagated throughout Error of type
DEFAULT_FLOW_UNKNOWN with Error Destination and IP Destination
addresses copied from the subset IP Source of the ad hoc network reachable from this node. In order to
reduce packet triggering the overhead from such Route Discoveries, a node
error. This error packet SHOULD use
an exponential back-off algorithm be MAC-destined to limit the rate at node from
which it
initiates new Route Discoveries for the same target, doubling the
timeout between each successive Discovery initiated for the same
target. If was received; if it cannot confirm reachability of the
previous node attempts to using Route Maintenance, it MUST send additional data packets to this
same destination node more frequently than this limit, the subsequent
packets SHOULD be buffered error as
described in Section 8.1.1. The node sending the Send Buffer until a Route Reply is
received giving a route error SHOULD
attempt to this destination, but the node MUST NOT
initiate a new Route Discovery until salvage the minimum allowable interval
between new Route Discoveries for this target has been reached. This
limitation on packet triggering the maximum rate of Route Discoveries for the same
target is similar to Error. If it does
salvage the mechanism required by Internet nodes to
limit packet, it MUST zero the rate at which ARP Requests are sent for any single target
IP address [3].

3.2. Basic DSR Flow ID.

3.5.5. Processing Route Maintenance Errors

When originating or forwarding a packet using a source route, each node transmitting receives a Route Error of type Unknown Flow, it marks
the packet is responsible for confirming that data
can flow over the link from that node to the next hop. For example,
in the situation shown below, node A indicate that it has originated not been established end-to-end.
When a packet for node E using receives a Route Error of type Default Flow Unknown, it
marks the default flow to indicate that it has not been established
end-to-end.

3.5.6. Interaction with Automatic Route Shortening

Because a full source route through intermediate nodes B, C, and D:

+-----+ +-----+ +-----+ +-----+ +-----+
| A |---->| B |---->| C |-->? | D | | E |
+-----+ +-----+ +-----+ +-----+ +-----+

In this case, node A is responsible not carried in every packet, an
alternative method for the link from A to B, node B performing automatic route shortening is responsible
necessary for packets using the link from B flow state extension. Instead, nodes
promiscuously listen to C, packets, and if a node C receives a packet
with (IP Source, IP Destination, Flow ID) found in the Flow Table
but the MAC-layer (next hop) destination address of the packet is responsible for
not this node, the link from C to D, node D is responsible for determines whether the link from D to E.

An acknowledgment can provide confirmation that a link is capable of
carrying data, and in wireless networks, acknowledgments are often
provided at no cost, either as packet was sent by
an existing standard part of upstream or downstream node by examining the MAC
protocol Hop Count field in use (such as
the link-layer acknowledgment frame defined
by IEEE 802.11 [11]), or DSR Flow State header. If the Hop Count field is less than the
expected Hop Count at this node, the node assumes that the packet
was sent by a "passive acknowledgment" [16] (in an upstream node, and adds an entry for the packet to

Johnson, et al Expires 21 24 August 2002 2003 [Page 7] 21]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

which, 2003

its Automatic Route Shortening Table, possibly evicting an earlier
entry added to this table. When the packet is then sent to that node
for example, B confirms receipt at C forwarding, the node finds that it has previously received the
packet by overhearing C transmit checking its Automatic Route Shortening Table, and returns
a gratuitous Route Reply to the source of the packet.

3.5.7. Loop Detection

If a node receives a packet when for forwarding with adjusted TTL lower
than expected and default flow forwarding is being used, it on sends
a Route Error of type Default Flow Unknown back to D).

If the IP source.
It can attempt delivery of the packet by normal salvaging (subject
to constraints described in Section 8.6.7) or by inserting a built-in acknowledgment mechanism
Flow ID option with Special TTL extension based on what that node's
understanding of the default Flow ID and TTL.

3.5.8. Acknowledgement Destination

In packets sent using Flow State, the previous hop is not available, necessarily
known. In order to allow nodes that have lost flow state to
determine the node
transmitting previous hop, the packet address of the previous hop can explicitly request a DSR-specific
software acknowledgment
optionally be returned by the next node along stored in the route;
this software acknowledgment will normally Acknowledgement Request. This extension
SHOULD NOT be transmitted directly
to the sending node, but if used when a Source Route option is present, MAY be used
when flow state routing is used without a Source Route option, and
SHOULD be used before Route Maintenance determines that the link between these two nodes next-hop
destination is
unidirectional, this software acknowledgment could travel over unreachable.

3.5.9. Crash Recovery

Each node has a maximum Timeout value that it can possibly generate.
This can be based on the largest number that can be set in a
different, multi-hop path.

After an acknowledgment has been received from some neighbor, timeout
option (2**16 - 1 seconds) or set in system software. When a node
MAY choose to
crashes, it does not require acknowledgments from that neighbor establish new flows for a
brief period of time, unless the network interface connecting a node equal to that neighbor always receives an acknowledgment this
maximum Timeout value, in response to
unicast traffic.

When a software acknowledgment is used, the acknowledgment request
SHOULD be retransmitted up order to a maximum number of times. A
retransmission of the acknowledgment request avoid colliding with its old
Flow IDs.

3.5.10. Rate Limiting

Flow IDs can be sent as assigned with a
separate packet, piggybacked on counter. More specifically, the
"Current Flow ID" is kept. When a retransmission of new default Flow ID needs to be
assigned, if the original
data packet, or piggybacked on any packet with Current Flow ID is odd, the same next-hop
destination that does not also contain a software acknowledgment.

After Current Flow ID is
assigned as the acknowledgment request has been retransmitted Flow ID and the maximum
number of times, Current Flow ID is incremented by
one; if no acknowledgment has been received, then the
sender treats Current Flow ID is even, one plus the link to this next-hop destination Current Flow ID is
assigned as currently
"broken". It SHOULD remove this link from its Route Cache the Flow ID 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 Current Flow ID is incremented by
two.

Johnson, et al Expires 24 August 2003 [Page 22]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

If Flow IDs are assigned in this way, one algorithm for avoiding
duplicate, unexpired Flow IDs is to A, as well as any other node that may have
used the link from C rate limit new Flow IDs to D since C last received an acknowledgment
from D. Node A then removes this broken link from its cache; any
retransmission
average rate of n assignments per second, where n is 2**15 divided by
the original packet maximum Timeout value. This can be performed by upper
layer protocols such as TCP, if necessary. For sending such a
retransmission or other packets averaged over any period not
exceeding the maximum Timeout value.

3.5.11. Interaction with Packet Salvaging

Salvaging is modified to zero the Flow ID field. Also, any time the
this same destination E, if A has
in its Route Cache another route document refers 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 Salvage field in the new route immediately. Otherwise, it
SHOULD perform Source Route option
in a new DSR Options header, packets without a Source Route Discovery for this target (subject option are
considered to have the
back-off described value zero in Section 3.1). the Salvage field.

Johnson, et al Expires 21 24 August 2002 2003 [Page 8] 23]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

3.3. Additional Route Discovery Features

3.3.1. Caching Overheard Routing Information

- Links in 2003

4. Conceptual Data Structures

This document describes the network frequently are capable operation of operating only
unidirectionally (not bidirectionally), and the MAC DSR protocol in terms
of a number of conceptual data structures. This section describes
each of these data structures and provides an overview of its use
in the network is capable protocol. In an implementation of transmitting unicast packets
over unidirectional links.

- Links in the network occasionally are capable of operating only
unidirectionally (not bidirectionally), but this unidirectional
restriction on protocol, these data
structures MAY be implemented in any link is not persistent, almost all links
are physically bidirectional, and manner consistent with the MAC protocol in use
external behavior described in
the this document.

4.1. Route Cache

All ad hoc network routing information needed by a node implementing
DSR is capable of transmitting unicast packets over
unidirectional links.

- The MAC protocol stored in use that node's Route Cache. Each node in the network is not capable
maintains its own Route Cache. A node adds information to its
Route Cache as it learns of
transmitting unicast packets over unidirectional links;
only bidirectional new links can be used by between nodes in the MAC protocol ad hoc
network; for
transmitting unicast packets. For example, the IEEE 802.11
Distributed Coordination Function (DCF) MAC protocol [11]
is capable a node may learn of transmitting new links when it receives
a unicast packet only over carrying a
bidirectional link, since the MAC protocol requires the return
of Route Request, Route Reply, or DSR source route.
Likewise, a link-level acknowledgment packet node removes information from its Route Cache as it
learns that existing links in the receiver and also
optionally requires the bidirectional exchange of an RTS and CTS
packet between the transmitter and receiver nodes.

In the first case above, ad hoc network have broken; for
example, the source route used in a data
packet, the accumulated route record in node may learn of a broken link when it receives a packet
carrying a Route Request, Error or through the route
being returned in link-layer retransmission
mechanism reporting a Route Reply SHOULD all be cached by any node failure in
the "forward" direction; any node SHOULD cache this information from
any such packet received, whether the forwarding a packet was addressed to this
node, sent to its next-hop
destination.

Anytime a broadcast (or multicast) MAC address, or overheard
while the node's network interface is in promiscuous mode. However,
the "reverse" direction of node adds new information to its Route Cache, the links identified in such packet
headers node
SHOULD NOT be cached.

Johnson, et al Expires 21 August 2002 [Page 9]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 February 2002

For example, check each packet in the situation shown below, node A is using a source
route its own Send Buffer (Section 4.2) to communicate with node E:

+-----+ +-----+ +-----+ +-----+ +-----+
| A |---->| B |---->| C |---->| D |---->| E |
+-----+ +-----+ +-----+ +-----+ +-----+

As node C forwards
determine whether a data packet along the route from A to E, it
SHOULD add to its cache the presence of the "forward" direction
links that it learns from packet's IP Destination Address
now exists in the headers of these packets, from itself
to D and from D node's Route Cache (including the information just
added to E. Node C SHOULD NOT, in this case, cache the
"reverse" direction of Cache). If so, the links identified in these packet headers,
from itself back to B SHOULD then be sent using
that route and removed from B the Send Buffer.

It is possible to A, since these links might interface a DSR network with other networks,
external to this DSR network. Such external networks may, for
example, be
unidirectional.

In the second case above, in which links Internet, or may occasionally operate
unidirectionally, the links described above SHOULD be cached in both
directions. Furthermore, in this case, if node X overhears (e.g.,
through promiscuous mode) other ad hoc networks routed
with a packet transmitted by node C routing protocol other than DSR. Such external networks may
also be other DSR networks that is
using a source route from node A are treated as external networks
in order to E, node X SHOULD cache all improve scalability. The complete handling of
these links as well, also including such
external networks is beyond the link from C scope of this document. However,
this document specifies a minimal set of requirements and features
necessary to X over which
it overheard the packet.

In allow nodes only implementing this specification to
interoperate correctly with nodes implementing interfaces to such
external networks. This minimal set of requirements and features
involve the final case, First Hop External (F) and Last Hop External (L) bits
in which the MAC protocol requires physical
bidirectionality for unicast operation, links from a source route
SHOULD be cached DSR Source Route option (Section 6.7) and a Route Reply option
(Section 6.3) in a packet's DSR Options header (Section 6). These
requirements also include the addition of an External flag bit
tagging each link in both directions, except when the packet also
contains a Route Reply, in which case only Cache, copied from the links already
traversed First Hop
External (F) and Last Hop External (L) bits in the DSR Source Route
option or Route Reply option from which this source route link was learned.

Johnson, et al Expires 24 August 2003 [Page 24]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

The Route Cache SHOULD be cached, but support storing more than one route to each
destination. In searching the links not
yet traversed in this Route Cache for a route SHOULD NOT be cached.

3.3.2. Replying to some
destination node, the Route Requests using Cached Routes

A Cache is indexed by destination node receiving
address. The following properties describe this searching function
on a Route Request Cache:

- Each implementation of DSR at any node MAY choose any appropriate
strategy and algorithm for which it is not the target,
searches searching its own Route Cache for and
selecting a "best" route to the target of the
Request. If found, the node generally returns destination from among those
found. For example, a Route Reply to the
initiator itself rather than forwarding the Route Request. In the
Route Reply, this node sets MAY choose to select the shortest
route record to list the destination (the shortest sequence of
hops over which this copy hops), or it
MAY use an alternate metric to select the route from the Cache.

- However, if there are multiple cached routes to a destination,
the selection of routes when searching the Route Request was forwarded Cache MUST
prefer routes that do not have the External flag set on any link.
This preference will select routes that lead directly to it,
concatenated with the source route to this
target obtained from its
own Route Cache.

However, before transmitting a Route Reply packet that was generated
using information from its Route Cache in this way, a node MUST
verify over routes that attempt to reach the resulting target via any
external networks connected to the DSR ad hoc network.

- In addition, any route being returned in selected when searching the Route Reply,
after this concatenation, contains no duplicate nodes listed in Cache
MUST NOT have the
route record. For example, External bit set for any links other than
possibly the figure below illustrates a case in

Johnson, et al Expires 21 August 2002 [Page 10]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 February 2002

which a Route Request first link, the last link, or both; the External bit
MUST NOT be set for target E has been received by node F, and
node F already has any intermediate hops in its the route selected.

An implementation of a Route Cache MAY provide a route from itself to E:

+-----+ +-----+ +-----+ +-----+
| A |---->| B |- >| D |---->| E |
+-----+ +-----+ \ / +-----+ +-----+
\ /
\ +-----+ /
>| C |-
+-----+
| ^
v | fixed capacity
for the cache, or the cache size MAY be variable. The following
properties describe the management of available space within a node's
Route Request +-----+
Route: A - B - C - F | F | Cache: C - D

- E
+-----+

The concatenation Each implementation of DSR at each node MAY choose any
appropriate policy for managing the accumulated route record from the entries in its Route
Request and Cache,
such as when limited cache capacity requires a choice of which
entries to retain in the cached route from F's Route Cache would include Cache. For example, a
duplicate node MAY chose a
"least recently used" (LRU) cache replacement policy, in passing which
the entry last used longest ago is discarded from C the cache if a
decision needs to F and back be made to C.

Node F allow space in this case could attempt to edit the route to eliminate cache for some
new entry being added.

- However, the
duplication, resulting in a route from A to B to C Route Cache replacement policy SHOULD allow routes
to D and on be categorized based upon "preference", where routes with a
higher preferences are less likely to E,
but in this case, node F would not be on removed from the route that it returned
in its own Route Reply. DSR Route Discovery prohibits cache.
For example, a node F
from returning such could prefer routes for which it initiated
a Route Reply from its cache; this prohibition
increases the probability Discovery over routes that it learned as the resulting route is valid, since
node F in this case should have received result of
promiscuous snooping on other packets. In particular, a Route Error if the route
had previously stopped working. Furthermore, this prohibition
means node
SHOULD prefer routes that a future Route Error traversing the route it is very likely presently using over those that
it is not.

Johnson, et al Expires 24 August 2003 [Page 25]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

Any suitable data structure organization, consistent with this
specification, MAY be used to pass through implement the Route Cache in any node that sent node.
For example, the following two types of organization are possible:

- In DSR, the route returned in each Route Reply for that is received
by the route
(including node F), which helps to ensure initiator of a Route Discovery (or that stale data is removed learned from caches (such
the header of overhead packets, as at F) described in Section 8.1.4)
represents a timely manner; otherwise, complete path (a sequence of links) leading to the next
Route Discovery initiated by A might also be contaminated by
destination node. By caching each of these paths separately,
a Route
Reply from F containing "path cache" organization for the same stale route. If node F, due to this
restriction on returning a Route Reply based on information Cache can be formed.
A path cache is very simple to implement and easily guarantees
that all routes are loop-free, since each individual route from its
Route Cache, does not return such
a Route Reply, node F propagates
the Reply or Route Request normally.

3.3.3. Preventing Route Reply Storms

The ability or used in a packet is loop-free.
To search for nodes to reply to a Route Request based on
information route in their a path cache data structure, the sending
node can simply search its Route Caches, as described in Section 3.3.2,
could result in Cache for any path (or prefix of
a possible path) that leads to the intended destination node.

This type of organization for the Route Reply "storm" Cache in DSR has been
extensively studied through simulation [5, 10, 14, 21] and
through implementation of DSR in some cases. In
particular, if a node broadcasts a Route Request for mobile outdoor testbed under
significant workload [22, 23, 24].

- Alternatively, a target node "link cache" organization could be used for the
Route Cache, in which each individual link (hop) in the node's neighbors have a route routes
returned in their Route Caches,
each neighbor may attempt Reply packets (or otherwise learned from the
header of overhead packets) is added to send a Route Reply, thereby wasting
bandwidth and possibly increasing the number unified graph data
structure of this node's current view of the network collisions topology.
To search for a route in link cache, the area.

Johnson, et al Expires 21 August 2002 [Page 11]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 February 2002

For example, the figure below shows sending node must use
a situation in which nodes B, C,
D, E, and F all receive A's Route Request for target G, and each has more complex graph search algorithm, such as the indicated route cached for this target:

Normally, each of these nodes would attempt well-known
Dijkstra's shortest-path algorithm, to find the current best path
through the graph to the destination node. Such an algorithm is
more difficult to implement and may require significantly more
CPU time to reply from execute.

However, a link cache organization is more powerful than a path
cache organization, in its own
Route Cache, and they would thus all send their Route Replies at
about the same time, since they ability to effectively utilize all received of
the broadcast Route
Request at potential information that a node might learn about the same time. Such simultaneous Route Replies state
of the network. In particular, links learned from different nodes all receiving the
Route Request may cause local
congestion in the wireless network and may create packet collisions
among some Discoveries or all of these Replies if from the MAC protocol header of any overheard packets can
be merged together to form new routes in use does the network, but this
is not provide sufficient collision avoidance for these packets. In
addition, it will often be possible in a path cache due to the case that separation of each
individual path in the different replies will
indicate routes cache.

This type of different lengths, as shown organization for the Route Cache in this example.

In order DSR, including
the effect of a range of implementation choices, has been studied
through detailed simulation [10].

The choice of data structure organization to reduce these effects, if use for the Route Cache
in any DSR implementation is a local matter for each node can put its network
interface into promiscuous receive mode, it MAY delay sending its
own and affects

Johnson, et al Expires 24 August 2003 [Page 26]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

only performance; any reasonable choice of organization for the Route
Cache does not affect either correctness or interoperability.

Each entry in the Route Reply for Cache SHOULD have a short period, while listening timeout associated
with it, to see allow that entry to be deleted if not used within some
time. The particular choice of algorithm and data structure used
to implement the
initiating node begins using a shorter route first. Specifically,
this node MAY delay sending its own Route Reply Cache SHOULD be considered in choosing the
timeout for a random period

d = H * (h - 1 + r)

where h is entries in the length Route Cache. The configuration variable
RouteCacheTimeout defined in number of network hops for Section 9 specifies the route timeout to be
returned
applied to entries in this node's the Route Reply, r Cache, although it is also possible
to instead use an adaptive policy in choosing timeout values rather
than using a random floating point
number between 0 and 1, single timeout setting for all entries; for example, the
Link-MaxLife cache design (below) uses an adaptive timeout algorithm
and H is a small constant delay (at least
twice does not use the maximum wireless RouteCacheTimeout configuration variable.

As guidance to implementors, Appendix A describes a type of link propagation delay)
cache known as "Link-MaxLife" that has been shown to be introduced
per hop. This delay effectively randomizes the time at outperform
other types of link caches and path caches studied in detailed
simulation [10]. Link-MaxLife is an adaptive link cache in which
each link in the cache has a timeout that is determined dynamically
by the caching node sends its Route Reply, with all nodes sending Route Replies
giving routes according to its observed past behavior of length less than h sending their Replies before this
node, and all the
two nodes sending Route Replies giving at the ends of the link; in addition, when selecting a
route for a packet being sent to some destination, among cached
routes of equal length
greater than h sending their Replies after this node.

Johnson, et al Expires 21 August 2002 [Page 12]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 February 2002

Within (number of hops) to that destination,
Link-MaxLife selects the delay period, this node promiscuously receives all
packets, looking for data packets from route with the initiator longest expected lifetime
(highest minimum timeout of this Route
Discovery destined for any link in the target route). Use of
the Discovery. If such Link-MaxLife design for the Route Cache is recommended in
implementations of DSR.

4.2. Send Buffer

The Send Buffer of a data
packet received node implementing DSR is a queue of packets that
cannot be sent by this that node during the delay period uses because it does not yet have a source
route of length less than or equal to h, this node may infer each such packet's destination. Each packet in the Send
Buffer is logically associated with the time that it was placed into
the Buffer, and SHOULD be removed from the Send Buffer and silently
discarded after a period of SendBufferTimeout after initially being
placed in the Buffer. If necessary, a FIFO strategy SHOULD be used
to evict packets before they timeout to prevent the buffer from
overflowing.

Subject to the rate limiting defined in Section 8.2, a Route
Discovery SHOULD be initiated as often as possible for the
initiator
destination address of any packets residing in the Send Buffer.

Johnson, et al Expires 24 August 2003 [Page 27]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

4.3. Route Discovery has already received a Request Table

The Route Reply
giving an equally good or better route. In this case, this Request Table of a node
SHOULD cancel its delay timer and SHOULD NOT send its implementing DSR records
information about Route Reply for Requests that have been recently originated
or forwarded by this Route Discovery.

3.3.4. Route Request Hop Limits

Each node. The table is indexed by IP address.

The Route Request message contains Table on a "hop limit" that may be used
to limit node records the number of intermediate following information
about nodes allowed to forward that
copy of the which this node has initiated a Route Request. This hop limit is implemented using the Request:

- The Time-to-Live (TTL) field used in the IP header of the packet carrying
the Route Request. As the
Request is forwarded, this limit is
decremented, and the Request packet is discarded if the limit reaches
zero before finding for the target. This last Route Request hop limit can be
used 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 a its Route
Request during a on each Route Discovery attempt.

For example, a node MAY use this hop limit to implement a
"non-propagating" Route Request as an initial phase of a Route
Discovery. A node using this technique sends its first Route Request
attempt initiated for some target node using a hop limit target. As
examples, two possible algorithms for this use of 1, such the TTL field
are described in Section 3.3.4.

- The time that any this node receiving the initial transmission of the last originated a Route Request will
not forward the Request to other nodes by re-broadcasting it. This
form for that
target node.

- The number of consecutive Route Request is called a "non-propagating" Route Request;
it provides an inexpensive method Discoveries initiated for determining if the this
target is
currently a neighbor of the initiator or if since receiving a neighbor node has valid Route Reply giving a route to the that
target cached (effectively using the neighbors' Route
Caches as an extension node.

- The remaining amount of the initiator's own Route Cache). If no
Route Reply is received after time before which this node MAY next
attempt at a short timeout, then Route Discovery for that target node. When the
node sends initiates a
"propagating" new Route Request (i.e., with no hop limit) Discovery for this target node, this
field in the Route Request Table entry for that target
node.

As another example, a node MAY use this hop limit is
initialized to implement an
"expanding ring" search the timeout for that Route Discovery, after which
the target [14]. A node using this
technique sends an initial non-propagating Route Request as described
above; if no MAY initiate a new Discovery for that target. Until
a valid Route Reply is received for it, the this target node originates
another Route Request with address,
a hop limit of 2. For node MUST implement a back-off algorithm in determining this
timeout value for each successive Route Request
originated, if no Route Reply is received Discovery initiated
for it, this target using the node doubles same Time-to-Live (TTL) value in the
IP header of the Route Request packet. The timeout between
such consecutive Route Discovery initiations SHOULD increase by
doubling the hop limit used timeout value on the previous attempt, to progressively explore
for the target node without allowing each new initiation.

In addition, the Route Request to propagate
over Table on a node also records the entire network. However,
following information about initiator nodes from which this expanding ring search
approach could have the effect node has
received a Route Request:

- A FIFO cache of increasing size RequestTableIds entries containing the average latency of
Route Discovery, since multiple Discovery attempts
Identification value and timeouts may
be needed before discovering a route to the target address from the most recent
Route Requests received by this node from that initiator node.

Nodes SHOULD use an LRU policy to manage the entries in their Route
Request Table.

Johnson, et al Expires 21 24 August 2002 2003 [Page 13] 28]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

3.4. Additional 2003

The number of Identification values to retain in each Route
Request Table entry, RequestTableIds, MUST NOT be unlimited, since,
in the worst case, when a node crashes and reboots, the first
RequestTableIds Route Discoveries it initiates after rebooting
could appear to be duplicates to the other nodes in the network.
In addition, a node SHOULD base its initial Identification value,
used for Route Discoveries after rebooting, on a battery backed-up
clock or other persistent memory device, in order to help avoid
any possible such delay in successfully discovering new routes
after rebooting; if no such source of initial Identification
value is available, a node after rebooting SHOULD base its initial
Identification value on a random number.

4.4. Gratuitous Route Reply Table

The Gratuitous Route Reply Table of a node implementing DSR records
information about "gratuitous" Route Maintenance Features

3.4.1. Packet Salvaging

When an intermediate Replies sent by this node forwarding as
part of automatic route shortening. As described in Section 3.4.3,
a packet detects through node returns a gratuitous Route
Maintenance that Reply when it overhears a packet
transmitted by some node, for which the next hop along node overhearing the route for that
packet is
broken, if was not the intended next-hop node has another route to but was named later in
the packet's destination unexpended hops of the source route in
its Route Cache, that packet; the node SHOULD "salvage"
overhearing the packet rather than
discarding it. To salvage returns a packet, the node replaces gratuitous Route Reply to the
original
source sender of the packet, listing the shorter route on (not
including the packet with hops of the source route from "skipped over" by this
packet). A node uses its Gratuitous Route Cache. The
node then forwards Reply Table to limit the packet
rate at which it originates gratuitous Route Replies to the next same
original sender for the same node indicated along this
source route. For example, in from which it overheard a packet to
trigger the situation shown gratuitous Route Reply.

Each entry in the example Gratuitous Route Reply Table of
Section 3.2, if a node contains the
following fields:

- The address of the node C has another route cached to which this node E, it can
salvage the packet by replacing originated a
gratuitous Route Reply.

- The address of the original route in node from which this node overheard the packet with
triggering that gratuitous Route Reply.

- The remaining time before which this new route from its own entry in the Gratuitous
Route Cache, rather than discarding Reply Table expires and SHOULD be deleted by the
packet. node.
When salvaging a packet, node creates a count is maintained new entry in its Gratuitous Route Reply
Table, the packet of the
number of times timeout value for that it has been salvaged, to prevent a single packet
from being salvaged endlessly. Otherwise, it could entry should be possible for
the packet initialized to enter a routing loop, as different nodes repeatedly
salvage the packet and replace the source route on
the value GratReplyHoldoff.

When a node overhears a packet with
routes to each other.

As described in Section 3.2, an intermediate node, such as in this
case, that detects through would trigger a gratuitous
Route Maintenance that Reply, if a corresponding entry already exists in the next hop along node's
Gratuitous Route Reply Table, then the route for node SHOULD NOT send a packet
gratuitous Route Reply for that it is forwarding is broken, packet. Otherwise (no corresponding

Johnson, et al Expires 24 August 2003 [Page 29]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

entry already exists), the node also SHOULD return create a new entry in its
Gratuitous Route Error Reply Table to the original sender record that gratuitous Route Reply,
with a timeout value of GratReplyHoldoff.

4.5. Network Interface Queue and Maintenance Buffer

Depending on factors such as the packet,
identifying the link over which structure and organization of
the operating system, protocol stack implementation, network
interface device driver, and network interface hardware, a packet
being transmitted could not be forwarded.
If the node sends this Route Error, it SHOULD originate the Route
Error before salvaging the packet.

3.4.2. Queued Packets Destined over a Broken Link

When an intermediate node forwarding queued in a packet detects through Route
Maintenance that variety of ways. For
example, outgoing packets from the next-hop network protocol stack might be
queued at the operating system or link along layer, before transmission
by the route network interface. The network interface might also
provide a retransmission mechanism for that packet
is broken, packets, such as occurs in addition to handling that packet
IEEE 802.11 [13]; the DSR protocol, as defined for part of Route Maintenance, the node SHOULD also handle in a similar way any pending
requires limited buffering of packets that it already transmitted for
which the reachability of the next-hop destination has queued not yet been
determined. The operation of DSR is defined here in terms of two
conceptual data structures that are destined over together incorporate this new broken
link. Specifically, the node SHOULD search its queuing
behavior.

The Network Interface Queue and Maintenance Buffer (Section 4.5) for of a node implementing DSR is an output
queue of packets from the network protocol stack waiting to be
transmitted by the network interface; for which example, in the next-hop link 4.4BSD
Unix network protocol stack implementation, this queue for a network
interface is represented as a "struct ifqueue" [36]. This queue is
used to hold packets while the network interface is in the process of
transmitting another packet.

The Maintenance Buffer of a node implementing DSR is a queue of
packets sent by this new broken link. node that are awaiting next-hop reachability
confirmation as part of Route Maintenance. For each such packet
currently queued at this node, in
the Maintenance Buffer, a node SHOULD process that packet as
follows:

- Remove maintains a count of the number
of retransmissions and the packet from time of the node's Network Interface Queue and
Maintenance Buffer.

Johnson, et al Expires 21 August 2002 [Page 14]

INTERNET-DRAFT last retransmission. The Dynamic Source Routing Protocol 21 February 2002

- Originate
Maintenance Buffer MAY be of limited size; when adding a Route Error for this new packet
to the original sender of
the packet, using the procedure described in Section 6.3.4, as Maintenance Buffer, if the node had already reached buffer size is insufficient to hold
the maximum number of retransmission
attempts for that new packet, the new packet for Route Maintenance. However, in
sending such Route Errors for queued SHOULD be silently discarded. If,
after MaxMaintRexmt attempts to confirm next-hop reachability of
some node, no confirmation is received, all packets in response to a
single new broken link detected, this node's
Maintenance Buffer with this next-hop destination SHOULD be removed
from the Maintenance Buffer; in this case, the node also SHOULD send no more
than one
originate a Route Error for this packet to each original sender of any source of these
packets.

- If the node
a packet removed in this way (Section 8.3) and SHOULD salvage each
packet removed in this way (Section 8.3.6) if it has another route
to the that packet's IP Destination Address in its Route Cache, the node SHOULD
salvage the Cache. The
definition of MaxMaintRexmt conceptually includes any retransmissions
that might be attempted for a packet as described in Section 6.3.6. Otherwise, the
node SHOULD discard at the packet.

3.4.3. Automatic Route Shortening

Source routes in use MAY be automatically shortened if one link layer or more
intermediate nodes in within
the route become no longer necessary. This
mechanism of automatically shortening routes in use is somewhat
similar network interface hardware. The timeout value to use for each
transmission attempt for an acknowledgement request depends on the use

Johnson, et al Expires 24 August 2003 [Page 30]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

type of passive acknowledgments [16]. In particular,
if acknowledgement mechanism used by Route Maintenance for that
attempt, as described in Section 8.3.

4.6. Blacklist

When a node using the DSR protocol is able to overhear connected through an
interface that requires physically bidirectional links for unicast
transmission, it MUST maintain a packet carrying blacklist. A Blacklist is a source route (e.g., table,
indexed by operating its network interface in promiscuous receive mode), then
this node examines the unexpended portion of neighbor address, that source route. If indicates that the link between
this node is not the intended next-hop destination for and the packet
but is named specified neighbor may not be bidirectional. A
node places another node's address in the later unexpended portion of the packet's source
route, then this list when it can infer believes that
broadcast packets from that other node reach this node, but that
unicast transmission between the intermediate two nodes before itself in
the source route are no longer needed in the route. is not possible. For
example, the
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
and to E:

+-----+ +-----+ +-----+ +-----+ +-----+
| A |---->| B |---->| C | | D | | E |
+-----+ +-----+ +-----+ +-----+ +-----+
\ ^
\ /
---------------------

In this case, this node (node D) SHOULD return if a node forwarding a "gratuitous" Route
Reply to the original sender of the packet (node A). The Route Reply gives the shorter route as the concatenation of the portion of discovers that the original source route up through next
hop is unreachable, it places that next hop in the node's blacklist.

Once a node discovers that transmitted the
overheard packet (node B), plus the suffix it can communicate bidirectionally with
one of the original source
route beginning with nodes listed in the blacklist, it SHOULD remove that
node returning from the gratuitous Route Reply
(node D). In this blacklist. For example, the route returned if node A has node B in the gratuitous Route
Reply message sent from D to its
blacklist, but A gives the new route as hears B forward a Route Request with a hop list
indicating that the sequence of
hops broadcast from A to B was successful, then 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 D "probable". After the
unreachability has not been positively determined for some amount of
time, the state should revert to E. "questionable". A node MAY expire
nodes from its blacklist after a reasonable amount of time.

Johnson, et al Expires 21 24 August 2002 2003 [Page 15] 31]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

When deciding whether to return a gratuitous Route Reply in this way,
a node MAY factor in 2003

5. Additional Conceptual Data Structures for Flow State Extension

This section defines additional information beyond conceptual data structures used by
the fact that it
was able optional "flow state" extension to overhear DSR. In an implementation of
the packet. For example, protocol, these data structures MAY be implemented in any manner
consistent with the external behavior described in this document.

5.1. Flow Table

A node MAY decide to
return the gratuitous Route Reply only when implementing the overheard packet is
received with flow state extension MUST implement a signal strenth Flow
Table or signal-to-noise ratio above some
specific threshold. In addition, each other data structure consistent with the external behavior
described in this section. A node maintains not implementing the flow state
extension SHOULD NOT implement a Gratuitous
Route Reply Table, Flow Table.

The Flow Table records information about flows from which packets
recently have been sent or forwarded by this node. The table is
indexed by a triple (IP Source Address, IP Destination Address,
Flow ID), where Flow ID is a 16-bit token assigned by the source as
described in Section 4.4, to limit 3.5.1. Each entry in the rate at
which it originates gratuitous Route Replies for Flow Table contains
the same returned
route.

3.4.4. Increased Spreading following fields:

- The MAC address of Route Error Messages

When a source node receives a Route Error for a data packet that
it originated, this source the next-hop node propagates this Route Error to its
neighbors by piggybacking it on its next Route Request. In along this way,
stale information in the caches flow.

- An indication of nodes around this source node will
not generate Route Replies that contain the same invalid link for
which outgoing network interface on this source node received the Route Error.

For example, in the situation shown to
be used in the example transmitting packets along this flow.

- The MAC address of Section 3.2, the previous-hop node along this flow.

- An indication of the network interface on this node A learns from the Route Error message which
packets from C, that the link
from C to D is currently broken. It thus removes previous-hop node are received.

- A timeout after which this link from
its own Route Cache and initiates a new Route Discovery (if it has
no other route to E entry in its Route Cache). On the Route Request
packet initiating Flow Table MUST be
deleted.

- The expected value of the Hop Count field in the DSR Flow State
header for packets received for forwarding along this Route Discovery, node A piggybacks field (for
use with packets containing a copy DSR Flow State header).

- An indication of whether or not this Route Error, ensuring that flow can be used as a
default flow for packets originated by this node (the flow IP
MUST be odd).

- The entry SHOULD record the Route Error spreads well to
other nodes, and guaranteeing that any Route Reply that it receives
(including those from other node's Route Caches) complete source route for the flow.
(Nodes not recording the complete source route cannot participate
in response to this Automatic Route Request does not Shortening.)

- The entry MAY contain a route that assumes field recording the existence of time this broken link. entry was
last used.

Johnson, et al Expires 21 24 August 2002 2003 [Page 16] 32]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

4. Conceptual Data Structures

This document describes the operation of the DSR protocol in terms
of a number of conceptual data structures. This section describes
each of these data structures and provides an overview of 2003

The entry MUST be deleted when its use
in the protocol. In an implementation of timeout expires.

5.2. Automatic Route Shortening Table

A node implementing the protocol, these flow state extension SHOULD implement an
Automatic Route Shortening Table or other data
structures MAY be implemented in any manner structure consistent
with the external behavior described in this document.

4.1. Route Cache

All ad hoc network routing information needed by a section. A node
not implementing
DSR is stored in that node's Route Cache. Each node in the network
maintains its own flow state extension SHOULD NOT implement an
Automatic Route Cache. A node adds information to its Shortening Table.

The Automatic Route Cache as it learns of new links between nodes in the ad hoc
network; Shortening Table records information about
received packets for example, a node which Automatic Route Shortening may learn of new links when it receives
a packet carrying be
possible. The table is indexed by a triple (IP Source Address, IP
Destination Address, Flow ID). Each entry in the Automatic Route Request, Route Reply, or DSR source route.
Likewise,
Shortening Table contains a node removes information from its Route Cache as it
learns list of (packet identifier, Hop Count)
pairs for that existing links flow. The packet identifier in the ad hoc network have broken; list may be any
unique identifier for the received packet; for example, a node may learn for IPv4
packets, the combination of a broken link when it receives a packet
carrying a Route Error or through the link-layer retransmission
mechanism reporting a failure in forwarding a packet to its next-hop
destination.

Anytime a node adds new information to its Route Cache, following fields from the node
SHOULD check each packet in its own Send Buffer (Section 4.2) to
determine whether a route to that packet's
IP header MAY be used as a unique identifier for the packet: Source
Address, Destination Address
now exists Address, Identification, Protocol, Fragment,
and Total Length. The Hop Count in the node's Route Cache (including list in the information just
added to entry is copied
from the Cache). If so, Hop Count field in the DSR Flow State header of the received
packet for which this table entry was created. Any packet identifier
SHOULD then be sent using
that route appear at most once in the list in an entry, and removed from this list
item SHOULD record the Send Buffer.

It is possible to interface minimum Hop Count value received for that
packet (if the wireless signal strength or signal-to-noise ratio at
which a DSR network with other networks,
external packet is received is available to this the DSR network. Such external networks may, implementation
in a node, the node MAY, for example, be remember instead in this list
the Internet, minimum Hop Count value for which the received packet's signal
strength or may be other ad hoc networks routed
with signal-to-noise ratio exceeded some threshold).

Space in the Automatic Route Shortening Table of a routing protocol other than DSR. Such external networks may
also node MAY be other DSR networks that are treated as external networks
dynamically managed by any local algorithm at the node. For example,
in order to improve scalability. The complete handling limit the amount of such
external networks is beyond memory used to store the scope table, any
existing entry MAY be deleted at any time, and the number of this document. packets
listed in each entry MAY be limited. However,
this document specifies a minimal set of requirements and features
necessary to allow nodes only implementing this specification to
interoperate correctly with when reclaiming space
in the table, nodes implementing interfaces to such
external networks. This minimal set of requirements and features
involve SHOULD favor retaining information about more
flows in the First Hop External (F) and Last Hop External (L)
bits table rather than more packets listed in a DSR Source Route option (Section 5.7) and a Route Reply
option (Section 5.3) each entry
in a packet's DSR header (Section 5). These
requirements also include the addition table, as long as at least the listing of an External flag bit
tagging each link some small number
of packets (e.g., 3) can be retained in each entry. In addition,
subject to any implementation limit on the Route Cache, copied from number of packets listed
in each entry in the First Hop
External (F) and Last Hop External (L) bits table, information about a packet listed in an
entry SHOULD be retained until the DSR Source Route
option expiration of the packet's IP TTL.

5.3. Default Flow ID Table

A node implementing the flow state extension MUST implement a Default
Flow Table or Route Reply option from which this link was learned. other data structure consistent with the external

Johnson, et al Expires 21 24 August 2002 2003 [Page 17] 33]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

The Route Cache 2003

behavior described in this section. A node not implementing the flow
state extension SHOULD support storing more than one route to NOT implement a Default Flow Table.

For each
destination. In searching the Route Cache (source, destination) pair for which a route to some
destination node, node forwards
packets, the Route Cache is indexed by destination node
address. The following properties describe this searching function
on a Route Cache: MUST record:

- Each implementation of DSR the largest odd Flow ID value seen

- the time at any which all of this (source, destination) pair's flows
that are forwarded by this node MAY choose any appropriate
strategy and algorithm for searching its Route Cache and
selecting expire

- the current default Flow ID

- a "best" route to flag indicating whether or not the destination from among those
found. For example, current default Flow ID is
valid

If a node MAY choose to select the shortest
route to the destination (the shortest sequence of hops), or deletes this record for a (source, destination) pair,
it
MAY use an alternate metric to select the route from the Cache.

- However, MUST also delete all Flow Table entries for that (source,
destination) pair. Nodes MUST delete table entries if there all of this
(source, destination) pair's flows that are multiple cached routes to a destination,
the selection forwarded by this node
expire.

Johnson, et al Expires 24 August 2003 [Page 34]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

6. DSR Options Header Format

The Dynamic Source Routing protocol makes use of routes when searching the Route Cache MUST
prefer routes a special header
carrying control information that do not have the External flag set on can be included in any link. existing
IP packet. This preference will select routes that lead directly to DSR Options header in a packet contains a small
fixed-sized, 4-octet portion, followed by a sequence of zero or more
DSR options carrying optional information. The end of the
target node over routes that attempt to reach sequence
of DSR options in the target via any
external networks connected to DSR Options header is implied by total length
of the DSR ad hoc network.

- In addition, any route selected when searching Options header.

For IPv4, the Route Cache DSR Options header MUST NOT have immediately follow the External bit set IP
header in the packet. (If a Hop-by-Hop Options extension header, as
defined in IPv6 [7], becomes defined for any links other than
possibly IPv4, the first link, DSR Options header
MUST immediately follow the last link, or both; Hop-by-Hop Options extension header, if
one is present in the External bit packet, and MUST NOT be set for any intermediate hops in otherwise immediately follow
the route selected.

An implementation of IP header.)

To add a Route Cache MAY provide DSR Options header to a fixed capacity
for the cache, or packet, the cache size MAY be variable. The DSR Options header is
inserted following
properties describe the management of available space within a node's
Route Cache:

- Each implementation of DSR at each node MAY choose packet's IP header, before any
appropriate policy for managing the entries in its Route Cache, following
header such as when limited cache capacity requires a choice of which
entries to retain in traditional (e.g., TCP or UDP) transport layer
header. Specifically, the Cache. For example, a node MAY chose a
"least recently used" (LRU) cache replacement policy, Protocol field in which the entry last used longest ago IP header is discarded from the cache if a
decision needs to be made used
to allow space in indicate that a DSR Options header follows the cache for some
new entry being added.

- However, IP header, and the Route Cache replacement policy SHOULD allow routes
to be categorized based upon "preference", where routes with a
higher preferences are less likely
Next Header field in the DSR Options header is used to be removed from indicate the cache.
For example, a node could prefer routes for which it initiated
a Route Discovery over routes that it learned
type of protocol header (such as a transport layer header) following
the result DSR Options header.

If any headers follow the DSR Options header in a packet, the total
length of
promiscuous snooping on other packets. In particular, the DSR Options header (and thus the total, combined length
of all DSR options present) MUST be a node
SHOULD prefer routes that it is presently using over those that
it is not. multiple of 4 octets. This
requirement preserves the alignment of these following headers in the
packet.

Johnson, et al Expires 21 24 August 2002 2003 [Page 18] 35]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

Any suitable data structure organization, consistent with this
specification, MAY be 2003

6.1. Fixed Portion of DSR Options Header

The fixed portion of the DSR Options header is used to implement carry
information that must be present in any DSR Options header. This
fixed portion of the DSR Options header has the following format:

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| Reserved | Payload Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. .
. Options .
. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Next Header

8-bit selector. Identifies the type of header immediately
following the DSR Options header. Uses the same values as the
IPv4 Protocol field [32].

Flow State Header (F)

Flag bit. MUST be set to 0. This bit is set in a DSR Flow
State header (Section 7.1) and clear in a DSR Options header.

Reserved

MUST be sent as 0 and ignored on reception.

Payload Length

The length of the Route Cache in any node.
For example, DSR Options header, excluding the following two types 4-octet
fixed portion. The value of organization are possible:

- In DSR, the route returned Payload Length field defines
the total length of all options carried in each Route Reply that the DSR Options
header.

Options

Variable-length field; the length of the Options field is received
specified by the initiator Payload Length field in this DSR Options
header. Contains one or more pieces of a Route Discovery (or that is learned from optional information
(DSR options), encoded in type-length-value (TLV) format (with
the header exception of overhead packets, as the Pad1 option, described in Section 6.1.4)
represents a complete path (a sequence 6.8).

The placement of links) leading to DSR options following the
destination node. By caching each fixed portion of these paths separately,
a "path cache" organization for the Route Cache can DSR
Options header MAY be formed.
A path cache is very simple to implement and easily guarantees
that all routes are loop-free, since each individual route from
a Route Reply or Route Request or used in a packet is loop-free.
To search for a route in a path cache data structure, the sending
node can simply search its Route Cache padded for any path (or prefix of
a path) that leads alignment. However, due to the intended destination node.

This type of organization for the Route Cache
typically limited available wireless bandwidth in DSR has been
extensively studied through simulation [5, 9, 12, 19] ad hoc networks,

Johnson, et al Expires 24 August 2003 [Page 36]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

this padding is not required, and
through implementation of receiving nodes MUST NOT expect
options within a DSR in Options header to be aligned.

Each DSR option is assigned a mobile outdoor testbed under unique Option Type code. The most
significant workload [20, 21, 22].

- Alternatively, 3 bits (that is, Option Type & 0xE0) allow a "link cache" organization could be used node not
implementing processing for the
Route Cache, in which each individual link (hop) this Option Type value to behave in the routes
returned
manner closest to correct for that type:

- The most significant bit in Route Reply packets (or otherwise learned from the
header of overhead packets) is added to Option Type value (that is,
Option Type & 0x80) represents whether or not a unified graph data
structure of node receiving
this node's current view Option Type SHOULD respond to such a DSR option with a Route
Error of the network topology.
To search for type OPTION_NOT_SUPPORTED, except that such a route Route
Error SHOULD never be sent in response to a packet containing a
Route Request option.

- The two follow bits in link cache, the sending node must use Option Type value (that is,
Option Type & 0x60) are a more complex graph search algorithm, two-bit field indicating how such as the well-known
Dijkstra's shortest-path algorithm, to find the current best path
through the graph to the destination node. Such an algorithm is
more difficult to implement and may require significantly more
CPU time to execute.

However, a link cache organization is more powerful than
node that does not support this Option Type MUST process the
packet:

00 = Ignore Option
01 = Remove Option
10 = Mark Option
11 = Drop Packet

When these two bits are zero (that is, Option Type & 0x60 == 0),
a path
cache organization, in its ability node not implementing processing for that Option Type
MUST use the Opt Data Len field to effectively utilize all of skip over the potential information that option and
continue processing. When these two bits are 01 (that is,
Option Type & 0x60 == 0x20), a node might learn about not implementing processing
for that Option Type MUST use the state
of Opt Data Len field to remove
the network. In particular, links learned from different
Route Discoveries or option from the header of any overheard packets can
be merged together to form new routes in packet and continue processing as if the network, but this
is
option had not possible been included in the received packet. When these
two bits are 10 (that is, Option Type & 0x60 == 0x40), a path cache due to node not
implementing processing for that Option Type MUST set the separation of each
individual path in most
significant bit following the cache.

This type Opt Data Len field, MUST ignore the
contents of organization for the Route Cache in DSR, including option using the effect of Opt Data Len field, and MUST
continue processing the packet. Finally, when these two bits are
11 (that is, Option Type & 0x60 == 0x60), a range of implementation choices, has been studied
through detailed simulation [9]. node not implementing
processing for that Option Type MUST drop the packet.

Johnson, et al Expires 24 August 2003 [Page 37]

INTERNET-DRAFT The choice Dynamic Source Routing Protocol 24 February 2003

The following types of data structure organization to use DSR options are defined in this document for the
use within a DSR Options header:

- Route Cache
in any Request option (Section 6.2)

- Route Reply option (Section 6.3)

- Route Error option (Section 6.4)

- Acknowledgement Request option (Section 6.5)

- Acknowledgement option (Section 6.6)

- DSR implementation is a local matter for each node and affects Source Route option (Section 6.7)

- Pad1 option (Section 6.8)

- PadN option (Section 6.9)

Johnson, et al Expires 21 24 August 2002 2003 [Page 19] 38]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

only performance; any reasonable choice of organization for the Route
Cache does not affect either correctness or interoperability.

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
time. The particular choice of algorithm and data structure used
to implement the Route Cache SHOULD be considered in choosing the
timeout for entries in the 2003

6.2. Route Cache. Request Option

The configuration variable
RouteCacheTimeout defined in Section 9 specifies the timeout to be
applied to entries in the Route Cache, although it is also possible
to instead use an adaptive policy Request option in choosing timeout values rather
than using a single timeout setting for all entries; for example, the
Link-MaxLife cache design (below) uses an adaptive timeout algorithm
and does not use the RouteCacheTimeout configuration variable.

As guidance to implementors, Appendix A describes a type of link
cache known DSR Options header is encoded as "Link-MaxLife" that has been shown
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 | Identification |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Target Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[2] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[n] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

IP fields:

Source Address

MUST be set to outperform
other types the address of link caches and path caches studied in detailed
simulation [9]. Link-MaxLife is an adaptive link cache in which each
link in the cache has a timeout node originating this packet.
Intermediate nodes that is determined dynamically by retransmit the
caching node according packet to its observed past behavior of propagate the two nodes
at
Route Request MUST NOT change this field.

Destination Address

MUST be set to the ends IP limited broadcast address
(255.255.255.255).

Hop Limit (TTL)

MAY be varied from 1 to 255, for example to implement
non-propagating Route Requests and Route Request expanding-ring
searches (Section 3.3.4).

Route Request fields:

Option Type

Opt Data Len

8-bit unsigned integer. Length of the link; option, in addition, when selecting octets,
excluding the Option Type and Opt Data Len fields.

Johnson, et al Expires 24 August 2003 [Page 39]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

Identification

A unique value generated by the initiator (original sender) of
the Route Request. Nodes initiating a route Route Request generate
a new Identification value for each Route Request, for example
based on a
packet being sent to some destination, among cached routes of equal
length (number sequence number counter of hops) to that destination, Link-MaxLife selects the
route with all Route Requests
initiated by the longest expected lifetime (highest minimum timeout node.

This value allows a receiving node to determine whether it
has recently seen a copy of
any link this Route Request: if this
Identification value is found by this receiving node in its
Route Request Table (in the route). Use cache of Identification values
in the Link-MaxLife design entry there for this initiating node), this receiving
node MUST discard the Route
Cache is recommended in implementations Request. When propagating a Route
Request, this field MUST be copied from the received copy of DSR.

4.2. Send Buffer
the Route Request being propagated.

Target Address

The Send Buffer address of a the node implementing DSR that is a queue the target of packets that
cannot be sent by that the Route
Request.

Address[1..n]

Address[i] is the address of the i-th node because it does not yet have a source
route to each such packet's destination. Each packet recorded in the Send
Buffer
Route Request option. The address given in the Source Address
field in the IP header is logically associated with the time that it was placed into address of the Buffer, initiator of
the Route Discovery and SHOULD MUST NOT be removed from listed in the Send Buffer and silently
discarded after a period Address[i]
fields; the address given in Address[1] is thus the address
of SendBufferTimeout the first node on the path after initially being
placed the initiator. The
number of addresses present in this field is indicated by the Buffer. If necessary, a FIFO strategy SHOULD be used
to evict packets before they timeout to prevent
Opt Data Len field in the buffer from
overflowing.

Subject to option (n = (Opt Data Len - 6) / 4).
Each node propagating the rate limiting defined in Section 6.2, a Route
Discovery SHOULD be initiated as often as possible for the
destination Request adds its own address of any packets residing in to
this list, increasing the Send Buffer. Opt Data Len value by 4 octets.

The Route Request option MUST NOT appear more than once within a DSR
Options header.

Johnson, et al Expires 21 24 August 2002 2003 [Page 20] 40]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

4.3. 2003

6.3. Route Request Table Reply Option

The Route Request Table of Reply option in a node implementing DSR records
information about Route Requests that have been recently originated
or forwarded by this node. The table Options header is indexed by 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len |L| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[2] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[n] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

IP address.

The fields:

Source Address

Set to the address of the node sending the Route Request Table on Reply.
In the case of a node records sending a reply from its Route
Cache (Section 3.3.2) or sending a gratuitous Route Reply
(Section 3.4.3), this address can differ from the following information
about nodes address that
was the target of the Route Discovery.

Destination Address

MUST be set to which this the address of the source node has initiated of the route
being returned. Copied from the Source Address field of the
Route Request generating the Route Reply, or in the case of a
gratuitous Route Request:

- The Time-to-Live (TTL) Reply, copied from the Source Address field used in of
the IP header data packet triggering the gratuitous Reply.

Route Reply fields:

Option Type

1. Nodes not understanding this option will ignore this
option.

Opt Data Len

8-bit unsigned integer. Length of the Route
Request for option, in octets,
excluding the Option Type and Opt Data Len fields.

Johnson, et al Expires 24 August 2003 [Page 41]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

Last Hop External (L)

Set to indicate that the last Route Discovery initiated hop given by this node for
that target node. This value allows the node Route Reply
(the link from Address[n-1] to implement Address[n]) is actually an
arbitrary path in a
variety of algorithms for controlling network external to the DSR network; the
exact route outside the DSR network is not represented in the spread of its Route
Request on each
Route Discovery initiated for a target. As
examples, two possible algorithms for Reply. Nodes caching this use of hop in their Route Cache MUST
flag the TTL field
are described cached hop with the External flag. Such hops MUST NOT
be returned in Section 3.3.4.

- The time that this node last originated a cached Route Request for that
target node.

- The number of consecutive Route Discoveries initiated for Reply generated from this
target since receiving a valid Route Reply giving a route
Cache entry, and selection of routes from the Route Cache to
route a packet being sent MUST prefer routes that
target node.

- contain no
hops flagged as External.

Reserved

MUST be sent as 0 and ignored on reception.

Address[1..n]

The remaining amount source route being returned by the Route Reply. The route
indicates a sequence of time before which this node MAY next
attempt hops, originating at a Route Discovery for that target node. When the
node initiates a new source node
specified in the Destination Address field of the IP header
of the packet carrying the Route Discovery for this target node, this
field Reply, through each of the
Address[i] nodes in the order listed in the Route Request Table entry for that target Reply,
ending with the destination node indicated by Address[n].
The number of addresses present in the Address[1..n]
field is
initialized to indicated by the timeout for that Route Discovery, after which Opt Data Len field in the node option
(n = (Opt Data Len - 1) / 4).

A Route Reply option MAY initiate a new Discovery for that target. Until appear one or more times within a valid DSR
Options header.

Johnson, et al Expires 24 August 2003 [Page 42]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

6.4. Route Reply Error Option

The Route Error option in a DSR Options header is received for 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len | Error Type |Reservd|Salvage|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Error Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Error Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. .
. Type-Specific Information .
. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Option Type

2. Nodes not understanding this target node address,
a node MUST implement a back-off algorithm in determining option will ignore this
timeout value for each successive
option.

Opt Data Len

8-bit unsigned integer. Length of the option, in octets,
excluding the Option Type and Opt Data Len fields.

For the current definition of the Route Discovery initiated
for Error option,
this target using field MUST be set to 10, plus the same Time-to-Live (TTL) value size of any
Type-Specific Information present in the
IP header Route Error. Further
extensions to the Route Error option format may also be
included after the Type-Specific Information portion of the
Route Request packet. Error option specified above. The timeout between presence of such consecutive Route Discovery initiations SHOULD increase
extensions will be indicated by
doubling the timeout value on each new initiation.

In addition, Opt Data Len field.
When the Route Request Table on a node also records Opt Data Len is greater than that required for
the
following information about initiator nodes from which this node has
received a Route Request:

- A FIFO cache fixed portion of size RequestTableIds entries containing the
Identification value and target address from the most recent Route Requests received Error plus the necessary
Type-Specific Information as indicated by this node from that initiator node.

Nodes SHOULD use an LRU policy to manage the entries Option Type
value in their Route
Request Table. the option, the remaining octets are interpreted as
extensions. Currently, no such further extensions have been
defined.

Error Type

The type of error encountered. Currently, the following type
values are defined:

1 = NODE_UNREACHABLE
2 = FLOW_STATE_NOT_SUPPORTED
3 = OPTION_NOT_SUPPORTED

Johnson, et al Expires 21 24 August 2002 2003 [Page 21] 43]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

The number of Identification 2003

Other values to retain in each Route
Request Table entry, RequestTableIds, of the Error Type field are reserved for future
use.

Reservd

Reserved. MUST NOT be unlimited, since, sent as 0 and ignored on reception.

Salvage

A 4-bit unsigned integer. Copied from the Salvage field in
the worst case, when a node crashes and reboots, DSR Source Route option of the packet triggering the first
RequestTableIds Route Discoveries it initiates after rebooting
could appear to be duplicates to
Error.

The "total salvage count" of the other nodes Route Error option is derived
from the value in the network.
In addition, a node SHOULD base its initial Identification value,
used for Salvage field of this Route Discoveries after rebooting, on a battery backed-up
clock or other persistent memory device, Error option
and all preceding Route Error options in order to help avoid
any possible the packet as follows:
the total salvage count is the sum of, for each such delay Route
Error option, one plus the value in successfully discovering new routes
after rebooting; if no such source the Salvage field of initial Identification
value is available, a node after rebooting SHOULD base its initial
Identification value on a random number.

4.4. Gratuitous that
Route Reply Table Error option.

Error Source Address

The Gratuitous Route Reply Table address of a the node implementing DSR records
information about "gratuitous" originating the Route Replies sent by this node as
part of automatic route shortening. As described in Section 3.4.3,
a Error (e.g., the
node returns a gratuitous Route Reply when it overhears that attempted to forward a packet
transmitted by some node, for which the node overhearing and discovered the
packet was not link
failure).

Error Destination Address

The address of the intended next-hop node but was named later in to which the unexpended hops of Route Error must be
delivered For example, when the source route in that packet; Error Type field is set to
NODE_UNREACHABLE, this field will be set to the address of the
node
overhearing that generated the packet returns a gratuitous Route Reply to routing information claiming that the
original sender of
hop from the packet, listing Error Source Address to Unreachable Node Address
(specified in the shorter route (not
including Type-Specific Information) was a valid hop.

Type-Specific Information

Information specific to the hops Error Type of the source route "skipped over" by this
packet). Route Error
message.

A node uses its Gratuitous Route Reply Table to limit Error option MAY appear one or more times within a DSR
Options header.

Johnson, et al Expires 24 August 2003 [Page 44]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

6.4.1. Node Unreachable Type-Specific Information

When the
rate at which it originates gratuitous Route Replies to Error is of type NODE_UNREACHABLE, the same
original sender for
Type-Specific Information field is defined 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unreachable Node Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Unreachable Node Address

The address of the same node from that was found to be unreachable
(the next-hop neighbor to which it overheard a packet the node with address
Error Source Address was attempting to
trigger transmit the packet).

6.4.2. Flow State Not Supported Type-Specific Information

When the gratuitous Route Reply.

Each entry in Error is of type FLOW_STATE_NOT_SUPPORTED, the
Type-Specific Information field is empty.

6.4.3. Option Not Supported Type-Specific Information

When the Gratuitous Route Reply Table Error is of a node contains type OPTION_NOT_SUPPORTED, the
following fields:

-
Type-Specific Information field is defined as follows:

0 1 2 3 4 5 6 7
+-+-+-+-+-+-+-+-+
|Unsupported Opt|
+-+-+-+-+-+-+-+-+

Unsupported Opt

The address type of option triggering the node to which this node originated a
gratuitous Route Reply.

- Error.

Johnson, et al Expires 24 August 2003 [Page 45]

INTERNET-DRAFT The address of the node from which this node overheard the packet
triggering that gratuitous Route Reply.

- Dynamic Source Routing Protocol 24 February 2003

6.5. Acknowledgement Request Option

The remaining time before which this entry Acknowledgement Request option in a DSR Options header is encoded
as follows:

Option Type

160. Nodes not understanding this option will remove the Gratuitous
Route Reply Table expires
option and SHOULD be deleted by the node.
When a node creates return a new entry in its Gratuitous Route Reply
Table, Error.

Opt Data Len

8-bit unsigned integer. Length of the timeout value for that entry should be initialized to option, in octets,
excluding the value GratReplyHoldoff.

When a node overhears a packet that would trigger a gratuitous
Route Reply, if Option Type and Opt Data Len fields.

Identification

The Identification field is set to a corresponding entry already exists in unique value and is copied
into the node's
Gratuitous Route Reply Table, then Identification field of the Acknowledgement option
when returned by the node SHOULD receiving the packet over this hop.

An Acknowledgement Request option MUST NOT send appear more than once
within a
gratuitous Route Reply for that packet. Otherwise (no corresponding DSR Options header.

Johnson, et al Expires 21 24 August 2002 2003 [Page 22] 46]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

entry already exists), the node SHOULD create a new entry 2003

6.6. Acknowledgement Option

The Acknowledgement option in its
Gratuitous Route Reply Table to record that gratuitous Route Reply,
with a timeout value of GratReplyHoldoff.

4.5. Network Interface Queue and Maintenance Buffer

Depending on factors such DSR Options header is encoded as
follows:

Option Type

32. Nodes not understanding this option will remove the structure and organization
option.

Opt Data Len

8-bit unsigned integer. Length of the operating system, protocol stack implementation, network
interface device driver, and network interface hardware, a packet
being transmitted could be queued option, in a variety of ways. For
example, outgoing packets from the network protocol stack might be
queued at the operating system or link layer, before transmission
by octets,
excluding the network interface. The network interface might also
provide a retransmission mechanism for packets, such as occurs in
IEEE 802.11 [11]; Option Type and Opt Data Len fields.

Identification

Copied from the DSR protocol, as part of Route Maintenance,
requires limited buffering Identification field of packets already transmitted for
which the reachability Acknowledgement
Request option of the next-hop destination has not yet been
determined. The operation of DSR is defined here in terms of two
conceptual data structures that together incorporate this queueing
behavior. packet being acknowledged.

ACK Source Address

The Network Interface Queue address of a the node implementing DSR is an output
queue originating the acknowledgement.

ACK Destination Address

The address of packets from the network protocol stack waiting node to be
transmitted by the network interface; for example, in which the 4.4BSD
Unix network protocol stack implementation, this queue for a network
interface is represented as a "struct ifqueue" [33]. This queue acknowledgement is
used to hold packets while the network interface is in the process of
transmitting another packet. be
delivered.

An Acknowledgement option MAY appear one or more times within a DSR
Options header.

Johnson, et al Expires 24 August 2003 [Page 47]

INTERNET-DRAFT The Maintenance Buffer of Dynamic Source Routing Protocol 24 February 2003

6.7. DSR Source Route Option

The DSR Source Route option in a node implementing DSR Options header is a queue of
packets sent by this node that are awaiting next-hop reachability
confirmation encoded as part
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 |F|L|Reservd|Salvage| Segs Left |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[2] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[n] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Option Type

96. Nodes not understanding this option will drop the packet.

Opt Data Len

8-bit unsigned integer. Length of Route Maintenance. For each packet the option, in octets,
excluding the Maintenance Buffer, a node maintains a count Option Type and Opt Data Len fields. For the
format of the number
of retransmissions and DSR Source Route option defined here, this field
MUST be set to the value (n * 4) + 2, where n is the time number of
addresses present in the last retransmission. The
Maintenance Buffer MAY be of limited size; when adding a new packet Address[i] fields.

First Hop External (F)

Set to indicate that the Maintenance Buffer, if first hop indicated by the buffer size DSR
Source Route option is insufficient actually an arbitrary path in a network
external to hold the new packet, DSR network; the new packet SHOULD be silently discarded. If,
after MaxMaintRexmt attempts to confirm next-hop reachability of
some node, no confirmation exact route outside the DSR
network is received, all packets not represented in the DSR Source Route option.
Nodes caching this node's
Maintenance Buffer hop in their Route Cache MUST flag the
cached hop with this next-hop destination SHOULD be removed
from the Maintenance Buffer; External flag. Such hops MUST NOT be
returned in this case, the node also SHOULD
originate a Route Error for Reply generated from this packet to each original source Route Cache
entry, and selection of routes from the Route Cache to route
a packet removed in this way (Section 6.3) and SHOULD salvage each
packet removed in this way (Section 6.3.6) if it has another route being sent MUST prefer routes that contain no hops
flagged as External.

Last Hop External (L)

Set to indicate that packet's IP Destination Address in its the last hop indicated by the DSR Source
Route Cache. The
definition of MaxMaintRexmt conceptually includes any retransmissions
that might be attempted for option is actually an arbitrary path in a packet at network
external to the link layer or within DSR network; the exact route outside the DSR
network interface hardware. The timeout value to use for each
transmission attempt for an acknowledgment request depends on is not represented in the DSR Source Route option.

Johnson, et al Expires 21 24 August 2002 2003 [Page 23] 48]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

type of acknowledgment mechanism used for Route Maintenance for that
attempt, as described 2003

Nodes caching this hop 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 their Route Cache MUST keep a blacklist. A Blacklist is a table,
indexed by neighbor address, that indicates that flag the link between
this node and
cached hop with the specified neighbor may not External flag. Such hops MUST NOT be bidirectional. A
node places another node's address
returned in this list when it believes that
broadcast packets a Route Reply generated from that other node reach this node, but that
unicast transmission between Route Cache
entry, and selection of routes from the two nodes is not possible. For
example, if a node forwarding a Route Reply discovers Cache to route
a packet being sent MUST prefer routes that the next
hop is unreachable, it places contain no hops
flagged as External.

Reserved

MUST be sent as 0 and ignored on reception.

Salvage

A 4-bit unsigned integer. Count of number of times that next hop in the node's blacklist.

Once
this packet has been salvaged as a node discovers that it can communicate bidirectionally with
one part of DSR routing
(Section 3.4.1).

Segments Left (Segs Left)

Number of route segments remaining, i.e., number of explicitly
listed intermediate nodes still to be visited before reaching
the final destination.

Address[1..n]

The sequence of addresses of the nodes listed source route. In routing
and forwarding the packet, the source route is processed as
described in Sections 8.1.3 and 8.1.5. The number of addresses
present in the blacklist, it SHOULD remove that node
from Address[1..n] field is indicated by the blacklist. For example, if A has B
Opt Data Len field in its blacklist, but
A hears B forward the option (n = (Opt Data Len - 2) / 4).

When forwarding a Route Request with packet along a hop list indicating that
the broadcast from A to B was successful, A SHOULD remove B from its
blacklist.

A node MUST associate DSR source route using a state with each node DSR Source
Route option in the blacklist,
specifying whether packet's DSR Options header, the unidirectionality is "questionable" or
"probable." Each time Destination
Address field in the unreachability packet's IP header is positively determined,
the node SHOULD always set the state to "probable." After the unreachability
has not been positively determined for some amount address
of time, the state
should revert to "questionable." packet's ultimate destination. A node MAY expire nodes from its
blacklist after receiving a reasonable amount of time. packet
containing a DSR Options header with a DSR Source Route option MUST
examine the indicated source route to determine if it is the intended
next-hop node for the packet and determine how to forward the packet,
as defined in Sections 8.1.4 and 8.1.5.

Johnson, et al Expires 21 24 August 2002 2003 [Page 24] 49]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

5. DSR Header Format 2003

6.8. Pad1 Option

The Dynamic Source Routing protocol makes use of Pad1 option in a DSR Options header is encoded as follows:

+-+-+-+-+-+-+-+-+
| Option Type |
+-+-+-+-+-+-+-+-+

Option Type

224. Nodes not understanding this option will drop the packet
and return a special header
carrying control information that can Route Error.

A Pad1 option MAY be included in any existing IP
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
carrying optional information. The end of the sequence Options field of a DSR
options Options
header in the order to align subsequent DSR header options, but such alignment
is implied not required and MUST NOT be expected by total length of the a node receiving a packet
containing a DSR Options header.

For IPv4, the DSR header MUST immediately

If any headers follow the IP DSR Options header in a packet, the
packet. (If total
length of a Hop-by-Hop DSR Options extension header, as defined indicated by the Payload Length field
in
IPv6 [6], becomes defined for IPv4, the DSR header MUST immediately
follow the Hop-by-Hop Options extension header, if one is present in
the packet, and header MUST otherwise immediately follow the IP header.)

To add be a DSR header to multiple of 4 octets. In this
case, when building a packet, the DSR Options header is inserted following
the packet's IP header, before any following header such as in a
traditional (e.g., TCP packet, sufficient Pad1
or UDP) transport layer header. Specifically,
the Protocol field PadN options MUST be included in the IP header is used to indicate that a DSR
header follows the IP header, and the Next Header Options field in of the DSR
Options header is used to indicate make the type of protocol header (such as total length a
transport layer header) following the DSR header. multiple of 4 octets.

If any headers follow the DSR header more than one consecutive octet of padding is being inserted in a packet,
the total length Options field of the a DSR header (and thus Options header, the total, combined length of all DSR
options present) MUST PadN option, described
next, SHOULD be a used, rather than multiple of 4 octets. This requirement
preserves Pad1 options.

Note that the alignment format of these following headers in the packet. Pad1 option is a special case; it does
not have an Opt Data Len or Option Data field.

Johnson, et al Expires 21 24 August 2002 2003 [Page 25] 50]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

5.1. Fixed Portion of DSR Header 2003

6.9. PadN Option

The fixed portion of the DSR header is used to carry information that
must be present PadN option in any DSR header. This fixed portion of the a DSR Options header has the following format:

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 is encoded as follows:

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - -
| Reserved Option Type | Payload Length Opt Data Len |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. .
. Options .
. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Next Header Option Data
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - -

Option Type

0. Nodes not understanding this option will ignore this
option.

Opt Data Len

8-bit selector. Identifies the type unsigned integer. Length of header immediately
following the DSR header. Uses the same values as option, in octets,
excluding the IPv4
Protocol field [29].

Reserved

MUST be sent as 0 Option Type and ignored on reception.

Payload Length

The length Opt Data Len fields.

Option Data

A number of zero-valued octets equal to the DSR header, excluding the 4-octet fixed
portion. The value of Opt Data Len.

A PadN option MAY be included in the Payload Length Options field defines the
total length of all options carried a DSR Options
header in the order to align subsequent DSR options, but such alignment
is not required and MUST NOT be expected by a node receiving a packet
containing a DSR Options header.

If any headers follow the DSR Options

Variable-length field; header in a packet, the total
length of the a DSR Options field is
specified header, indicated by the Payload Length field
in this the DSR header.
Contains one or more pieces Options header MUST be a multiple of optional information (DSR
options), encoded 4 octets. In this
case, when building a DSR Options header in type-length-value (TLV) format (with the
exception of the a packet, sufficient Pad1 option, described in Section 5.8).

The placement of DSR
or PadN options following MUST be included in the fixed portion Options field of the DSR
Options header MAY be padded for alignment. However, due to make the typically
limited available wireless bandwidth in ad hoc networks, this padding
is not required, and receiving nodes MUST NOT expect options within a
DSR header to be aligned.

Johnson, et al Expires 21 August 2002 [Page 26]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 February 2002

The following types of DSR options are defined in this document for
use within total length a DSR header:

- Route Request option (Section 5.2)

- Route Reply option (Section 5.3)

- Route Error option (Section 5.4)

- Acknowledgment Request option (Section 5.5)

- Acknowledgment option (Section 5.6)

- DSR Source Route option (Section 5.7)

- Pad1 option (Section 5.8)

- PadN option (Section 5.9) multiple of 4 octets.

Johnson, et al Expires 21 24 August 2002 2003 [Page 27] 51]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

5.2. Route Request Option 2003

7. Additional Header Formats and Options for Flow State Extension

The Route Request option in a optional DSR flow state extension requires a new header is encoded as follows:

IP fields:

Source Address

MUST be set to type, the address of
DSR Flow State header.

In addition, the node originating this packet.
Intermediate nodes that retransmit DSR flow state extension adds the packet to propagate following options
for the
Route Request MUST NOT change this field. DSR Options header defined in Section 6:

- Timeout option

- Destination Address

MUST be set to the IP limited broadcast address
(255.255.255.255).

Hop Limit (TTL)

MAY be varied from 1 to 255, for example to implement
non-propagating Route Requests and Route Request expanding-ring
searches (Section 3.3.4).

Route Request fields:

Option Flow ID option

Two new Error Type

Opt Data Len

8-bit unsigned integer. Length of values are also defined for use in the option, Route Error
option in octets,
excluding a DSR Options header:

- Unknown Flow

- Default Flow Unknown

Finally, an extension to the Option Type and Opt Data Len fields. Acknowledgement Request option in a DSR
Options header is also defined:

- Previous Hop Address

This section defines each of these new header or option formats.

Johnson, et al Expires 21 24 August 2002 2003 [Page 28] 52]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

Identification

A unique value generated by the initiator (original sender) of
the Route Request. Nodes initiating a Route Request generate
a new Identification value for each Route Request, for example
based on a sequence number counter of all Route Requests
initiated by the node.

This value allows 2003

7.1. DSR Flow State Header

The DSR Flow State header is a receiving node small 4-byte header optionally used
to determine whether it
has recently seen a copy of this Route Request: if this
Identification value is found by this receiving node in its
Route Request Table (in the cache of Identification values
in carry the entry there flow ID and hop count for this initiating node), this receiving
node MUST discard the Route Request. When propagating a Route
Request, this field MUST be copied from the received copy of
the Route Request packet being propagated.

Target Address

The address of the node that sent along a
DSR flow. It is distinguished from the target of fixed DSR Options header
(Section 6.1) in that the Route
Request.

Address[1..n]

Address[i] Flow State Header (F) bit is the address of the i-th node recorded set in the
Route Request option. The address given DSR
Flow State header and is clear in the Source Address
field in 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 IP type of header is immediately
following the address of DSR Flow State header. Uses the initiator of same values as
the Route Discovery and IPv4 Protocol field [32].

Flow State Header (F)

Flag bit. MUST NOT be listed set to 1. This bit is set in the Address[i]
fields; the address given a DSR Flow
State header and clear in Address[1] 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.

Johnson, et al Expires 24 August 2003 [Page 53]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

7.2. Options and Extensions in DSR Options Header

7.2.1. Timeout Option

The Timeout option is thus defined for use in a DSR Options header to
indicate the address amount of time before the first node on expiration of the path after flow ID
along which the initiator. The
number of addresses present in this field packet is indicated by 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 | Option Length | Timeout |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Option Type

128. Nodes not understanding this option will ignore the
option and return a Route Error.

Opt Data Len field

8-bit unsigned integer. Length of the option, in octets,
excluding the option (n = (Opt Option Type and Opt Data Len - 6) / 4).
Each node propagating fields.

When no extensions are present, the Route Request adds its own address Opt Data Len of a Timeout
option is 2. Further extensions to
this list, increasing the DSR may include additional
data in a Timeout option. The presence of such extensions is
indicated by an Opt Data Len value by 4 octets. greater than 2. Currently, no
such extensions have been defined.

Timeout

The Route Request number of seconds for which this flow remains valid.

The Timeout option MUST NOT appear more than once within a DSR
Options header.

Johnson, et al Expires 21 24 August 2002 2003 [Page 29] 54]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

5.3. Route Reply 2003

7.2.2. Destination and Flow ID Option

The Route Reply Destination and Flow ID option is defined for use in a DSR
Options header is encoded as follows: 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 |L| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[2] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Option Length | ... New Flow Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[n] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ New IP fields:

Source Destination Address

Set to |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Option Type

129. Nodes not understanding this option will ignore the address
option and return a Route Error.

Opt Data Len

8-bit unsigned integer. Length of the node sending option, in octets,
excluding the Route Reply.
In Option Type and Opt Data Len fields.

When no extensions are present, the case Opt Data Len of a node sending a reply from its Route
Cache (Section 3.3.2) or sending a gratuitous Route Reply
(Section 3.4.3), this address can differ from the address that
was the target of the Route Discovery.
Destination Address

MUST be set and Flow ID option is 6. Further extensions to the address of the source node
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 route
being returned. Copied from next identifier to store in the Source Address Flow ID field of
the
Route Request generating DSR Options header.

New IP Destination Address

Indicates the Route Reply, or next address to store in the case of a
gratuitous Route Reply, copied from the Source Destination Address
field of the data packet triggering the gratuitous Reply.

Route Reply fields:

Option Type

Opt Data Len

8-bit unsigned integer. Length of the option, in octets,
excluding the Option Type IP header.

The Destination and Opt Data Len fields. Flow ID option MAY appear one or more times
within a DSR Options header.

Johnson, et al Expires 21 24 August 2002 2003 [Page 30] 55]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

Last Hop External (L)

Set to indicate that the last hop given by the Route Reply
(the link from Address[n-1] to Address[n]) 2003

7.2.3. New Error Type Value for Unknown Flow

A new Error Type value of 129 (Unknown Flow) is actually an
arbitrary path defined for use in
a network external to the DSR network; the
exact route outside the DSR network is not represented in the
Route Reply. Nodes caching this hop in their Route Cache MUST
flag the cached hop with the External flag. Such hops MUST NOT
be returned Error option in a cached Route Reply generated from this Route
Cache entry, and selection DSR Options header. The Type-Specific
Information for errors of routes from the Route Cache to
route a packet being sent MUST prefer routes that contain no
hops flagged as External.

Reserved

MUST be sent 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 and ignored on reception.

Address[1..n]

The source route being returned by the Route Reply. The route
indicates a sequence of hops, originating at the source node
specified in the 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Original IP Destination Address field of the |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Flow ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Original IP header Destination Address

The IP Destination Address of the packet carrying the Route Reply, through each of the
Address[i] nodes in that caused the order listed error.

Flow ID

The Flow ID contained in the Route Reply,
ending with DSR Flow ID option that caused the destination node indicated by Address[n].
error.

Johnson, et al Expires 24 August 2003 [Page 56]

INTERNET-DRAFT The number Dynamic Source Routing Protocol 24 February 2003

7.2.4. New Error Type Value for Default Flow Unknown

A new Error Type value of addresses present in the Address[1..n]
field 130 (Default Flow Unknown) is indicated by the Opt Data Len field defined
for use in the option
(n = (Opt Data Len - 1) / 4).

A a Route Reply Error option MAY appear one or more times within 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.

Johnson, et al Expires 21 24 August 2002 2003 [Page 31] 57]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

5.4. Route Error 2003

7.2.5. Acknowledgement Request Option Previous Hop Address Extension

When the Option Length field of an Acknowledgement Request option
in a DSR Options header is greater than or equal to 6, a Previous
Hop Address Extension is present. The Route Error option in a DSR header is encoded 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 | Error Type |Reservd|Salvage|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Option Length | Error Source Address Packet Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Error Destination ACK Request Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. .
. Type-Specific Information .
. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Option Type

Opt Data Len

Option Length

8-bit unsigned integer. Length of the option, in octets,
excluding octets,
excluding the Option Type and Option Length fields.

When no extensions are presents, the Option Length of a
Acknowledgement Request option is 2. Further extensions to
DSR may include additional data in a 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
Option Length is at least 6, then a 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.

Johnson, et al Expires 24 August 2003 [Page 58]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

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 Option Type 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 Opt Data Len fields.

For initiating the current definition of Route
Discovery by sending a separate packet containing such a Route
Request option. If the node chooses to initiate the Route Error option,
Discovery by adding the Route Request option to this existing
packet, it will replace the IP Destination Address field MUST be set with the
IP "limited broadcast" address (255.255.255.255) [3], copying the
original IP Destination Address to 10, plus the size Target Address field of any
Type-Specific Information present in
the new Route Error. Further
extensions Request option added to the packet, as described in
Section 8.2.1.

- If the packet now does not contain a Route Error option format may also be
included after Request option,
then this node must have a route to the Type-Specific Information portion Destination Address
of the
Route Error option specified above. The presence of such
extensions will be indicated by packet; if the Opt Data Len field.
When node has more than one route to this
Destination Address, the Opt Data Len 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 required for 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 fixed portion selected route
to the Destination Address of the Route Error plus packet.

- Transmit the necessary
Type-Specific Information as indicated by packet to the Option Type
value first-hop node address given in
selected source route, using Route Maintenance to determine the option,
reachability of the remaining octets are interpreted next hop, as
extensions. Currently, no such further extensions have been
defined.

Error Type

The type of error encountered. Currently, 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 following type
value 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 defined:

1 = NODE_UNREACHABLE

Other values of added to a packet by performing the Error Type field are reserved for future
use. following

Johnson, et al Expires 21 24 August 2002 2003 [Page 32] 59]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

Reservd

Reserved. MUST be sent as 0 and ignored on reception.

Salvage

A 4-bit unsigned integer. Copied from the Salvage field in
the DSR Source Route option 2003

sequence of steps (these steps assume that the packet triggering the Route
Error.

The "total salvage count" of the Route Error option is derived
from the value in the Salvage field of this Route Error option
and all preceding Route Error options contains no
other headers that MUST be located in the packet as follows:
the total salvage count is before the sum of, for each such Route
Error option, one plus DSR
Options header):

- Insert a DSR Options header after the value in IP header but before any
other header that may be present.

- Set the Salvage Next Header field of that
Route Error option.

Error Source Address

The address of the node originating DSR Options header to the Route Error (e.g.,
Protocol number field of the
node that attempted to forward a packet and discovered packet's IP header.

- Set the link
failure).

Error Destination Address

The address Protocol field of the node packet's IP header to which the Protocol
number assigned for a DSR Options header (TBA???).

8.1.3. Adding a DSR Source Route Error must be
delivered For example, when Option to a Packet

A node originating a packet adds a DSR Source Route option to the Error Type field is set
packet, if necessary, in order to
NODE_UNREACHABLE, carry the source route from this field will be set
originating node to the final destination address of the
node that generated packet.
Specifically, the routing information claiming that node adding the
hop from DSR Source Route option constructs
the Error DSR Source Address to Unreachable Node Address
(specified in Route option and modifies the Type-Specific Information) was a valid hop.

Type-Specific Information

Information specific IP packet according to
the Error Type following sequence of this Route Error
message.

Currently, the Type-Specific Information field is defined only for steps:

- The node creates a DSR Source Route Error messages of type NODE_UNREACHABLE. In this case, the
Type-Specific Information field is defined as follows:

Johnson, et al Expires 21 August 2002 [Page 33]

INTERNET-DRAFT 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 Dynamic number of Address[i] fields to include in the DSR Source Routing Protocol 21 February 2002

Unreachable Node Address

The
Route option (n) is the number of intermediate nodes in the
source route for the packet (i.e., excluding address of the
originating node that was found to be unreachable
(the next-hop neighbor to which and the node with final destination address
Error Source Address was attempting to transmit of the
packet).

A The Segments Left field in the DSR Source Route Error option MAY appear one or more times
is initialized equal to n.

- The addresses within a the source route for the packet are copied
into sequential Address[i] fields in the DSR
header.

Johnson, et al Expires 21 August 2002 [Page 34]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 February 2002

5.5. Acknowledgment Request Option Route option,
for i = 1, 2, ..., n.

- The Acknowledgment Request option First Hop External (F) bit in a the DSR header Source Route option is encoded
copied from the External bit flagging the first hop in the source
route for the packet, as
follows:

Option Type

Opt Data Len

8-bit unsigned integer. Length of indicated in the option, Route Cache.

- The Last Hop External (L) bit in octets,
excluding the Option Type and Opt Data Len fields.

Identification

The Identification field is set to a unique value and DSR Source Route option is
copied
into from the Identification field of External bit flagging the Acknowledgment option when
returned by last hop in the node receiving source
route for the packet, as indicated in the Route Cache.

- The Salvage field in the packet over this hop.

An Acknowledgment Request option MUST NOT appear more than once
within a DSR header. Source Route option is
initialized to 0.

Johnson, et al Expires 21 24 August 2002 2003 [Page 35] 60]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

5.6. Acknowledgment Option

The Acknowledgment option in 2003

8.1.4. Processing a DSR header is encoded Received Packet

When a node receives any packet (whether for forwarding, overheard,
or as follows:

Option Type

Opt Data Len

8-bit unsigned integer. Length the final destination of the option, packet), if that packet contains
a DSR Options header, then that node MUST process any options
contained in that DSR Options header, in octets,
excluding the Option Type 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 Opt Data Len fields.

Identification

Copied
add this routing information to its Route Cache, subject to the
conditions identified in Section 3.3.1. The routing information
from the Identification field Route Request is the sequence of hop addresses

initiator, Address[1], Address[2], ..., Address[n]

where initiator is the Acknowledgment
Request option value of the packet being acknowledged.

ACK Source Address

The address field in
the IP header of the node originating packet carrying the acknowledgment.

ACK Destination Address

The Route Request (the
address of the node to which initiator of the acknowledgment Route Discovery), and each
Address[i] is to be
delivered.

An Acknowledgment option MAY appear one or more times within a DSR
header.

Johnson, et al Expires 21 August 2002 [Page 36]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 February 2002

5.7. DSR Source Route Option

The DSR Source node through which this Route option Request has passed,
in a DSR header turn, during this Route Discovery. The value n here is encoded as follows:

Option Type

Opt the
number of addresses recorded in the Route Request option, or
(Opt Data Len

8-bit unsigned integer. Length of - 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 octets,
excluding
Section 8.2.2.

- If the Option Type and Opt Data Len fields. For DSR Options header contains a Route Reply option, the
format of node
SHOULD extract the source route from the DSR Source Route option defined here, Reply and add this field
MUST be set
routing information to its Route Cache, subject to the value (n * 4) + 2, where n conditions
identified in Section 3.3.1. The source route from the Route
Reply is the number sequence of hop addresses present

initiator, Address[1], Address[2], ..., Address[n]

where initiator is the value of the Destination Address field in
the Address[i] fields.

First Hop External (F)

Set to indicate that IP header of the first hop indicated by packet carrying the DSR
Source Route option Reply (the address
of the initiator of the Route Discovery), and each Address[i]
is actually an arbitrary path in a network
external to node through which the DSR network; source route passes, in turn, on
the exact route outside to the DSR
network is not represented in target of the DSR Source Route option.
Nodes caching this hop Discovery. Address[n] is
the address of the target. If the Last Hop External (L) bit is
set in their the Route Cache Reply, the node MUST flag the
cached last hop with from
the External flag. Such hops MUST NOT be
returned in a Route Reply generated from this Route Cache
entry, and selection of routes (the link from the Address[n-1] to Address[n]) in
its Route Cache to route
a packet being sent MUST prefer routes that contain no hops
flagged as External.

Last Hop External (L)

Set to indicate that the last hop indicated by the DSR Source
Route option The value n here is actually an arbitrary path in a network
external to the DSR network; number of
addresses in the exact source route outside the DSR
network is not represented being returned in the DSR Source Route option.
Nodes caching this hop in their Route Cache MUST flag the Reply
option, or (Opt Data Len - 1) / 4.

Johnson, et al Expires 21 24 August 2002 2003 [Page 37] 61]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

cached hop with 2003

After possibly updating the External flag. Such hops MUST NOT be
returned in a Route Reply generated from this node's Route Cache
entry, and selection of routes from in response to
the routing information in the Route Cache to route
a packet being sent MUST prefer routes that contain no hops
flagged as External.

Reserved

MUST be sent as 0 and ignored on reception.

Salvage

A 4-bit unsigned integer. Count of number Reply option, then if the
packet's IP Destination Address matches one of times that this packet has been salvaged node's IP
addresses, the node MUST then process the Route Reply option as a part of
described in Section 8.2.5.

- If the DSR routing
(Section 3.4.1).

Segments Left (Segs Left)

Number of route segments remaining, i.e., number of explicitly
listed intermediate nodes still to be visited before reaching Options header contains a Route Error option,
the final destination.

Address[1..n]

The sequence of addresses of node MUST process the source route. In routing
and forwarding Route Error option as described in
Section 8.3.5.

- If the packet, DSR Options header contains an Acknowledgement Request
option, the source route is processed node MUST process the Acknowledgement Request option
as described in Sections 6.1.3 and 6.1.5. The number of addresses
present 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 Address[1..n] field is indicated by
node SHOULD add to its Route Cache the single link from the
Opt Data Len field in node
identified by the option (n = (Opt Data Len - 2) / 4).

When forwarding a packet along a DSR source route using a DSR ACK Source
Route option in Address field to the packet's DSR header, node identified
by the ACK Destination Address
field in field.

After possibly updating the packet's IP header is always set node's Route Cache in response to
the address of routing information in the Acknowledgement option, the
packet's ultimate destination. A node receiving a packet containing
a
MUST then process the Acknowledgement option as described in
Section 8.3.3.

- If the DSR Options header with contains a DSR Source Route option MUST examine option, the
node SHOULD extract the
indicated source route to determine if it is the intended next-hop
node for from the packet DSR Source Route
and determine how add this routing information to its Route Cache, subject to forward
the packet, as
defined conditions identified in Sections 6.1.4 and 6.1.5.

Johnson, et al Expires 21 August 2002 [Page 38]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 February 2002

5.8. Pad1 Option

The Pad1 option Section 3.3.1. If the value of the
Salvage field in a the DSR header is encoded as follows:

+-+-+-+-+-+-+-+-+
| Option Type |
+-+-+-+-+-+-+-+-+

Option Type

A Pad1 Source Route option MAY be included in is zero, then the
routing information from the Options field of a DSR header
in order to align subsequent DSR options, but such alignment Source Route is
not required the sequence of
hop addresses

source, Address[1], Address[2], ..., Address[n], destination

and MUST NOT be expected by a node receiving a packet
containing a otherwise (Salvage is nonzero), the routing information from
the DSR header.

If any headers follow Source Route is the DSR header in a packet, sequence of hop addresses

Address[1], Address[2], ..., Address[n], destination

where source is the total length value of
a DSR header, indicated by the Payload Length Source Address field in the DSR IP
header
MUST be a multiple of 4 octets. In this case, when building a the packet carrying the DSR
header in a packet, sufficient Pad1 or PadN options MUST be included Source Route option (the
original sender of the packet), each Address[i] is the value in
the Options Address[i] field of in the DSR header to make Source Route, and destination is
the total length a
multiple of 4 octets.

If more than one consecutive octet value of padding is being inserted in the Options Destination Address field in the packet's IP
header (the last-hop address of a DSR header, the PadN option, described next,
SHOULD be used, rather than multiple Pad1 options.

Note that source route). The value n
here is the format number of addresses in source route in the Pad1 option is a special case; it does
not have an Opt Data Len DSR Source
Route option, or Option (Opt Data field. Len - 2) / 4.

Johnson, et al Expires 21 24 August 2002 2003 [Page 39] 62]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

5.9. PadN Option

The PadN option in a DSR header is encoded as follows:

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - -
| Option Type | Opt Data Len | Option Data
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - - -

Option Type

Opt Data Len

8-bit unsigned integer. Length of the option, in octets,
excluding 2003

After possibly updating the Option Type and Opt Data Len fields.

Option Data

A number of zero-valued octets equal node's Route Cache in response to
the Opt Data Len.

A PadN option MAY be included routing information in the Options field of a DSR header
in order to align subsequent DSR options, but such alignment is
not required and MUST NOT be expected by a Source Route option, the node receiving a packet
containing a DSR header.

If any headers follow
MUST then process the DSR header Source Route option as described in
Section 8.1.5.

- Any Pad1 or PadN options in a packet, the total length of
a DSR header, indicated by Options header are ignored.

Finally, if the Payload Length field Destination Address in the DSR packet's IP header
MUST be a multiple matches
one of 4 octets. In this case, when building a receiving node's own IP address(es), remove the DSR
Options header in a packet, sufficient Pad1 or PadN options MUST be and all the included DSR options in the Options field header, and
pass the rest of the DSR header packet to make the total length a
multiple of 4 octets.

Johnson, et al Expires 21 August 2002 [Page 40]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 February 2002

6. Detailed Operation

6.1. General Packet network layer.

8.1.5. Processing

6.1.1. Originating a Packet Received DSR Source Route Option

When originating any packet, a node using receives a packet containing a DSR routing MUST perform Source Route option
(whether for forwarding, overheard, or as the following sequence final destination of steps:

- Search
the node's Route Cache for a route packet), that node SHOULD examine the packet to determine if
the address given 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 IP Destination Address field intended next-hop destination for the packet
but is named in the packet's header.

- If no such later unexpended portion of the source route is found in
the packet's DSR Source Route Cache, option, then perform
Route Discovery this packet indicates an
opportunity for automatic route shortening: the Destination Address, as described in
Section 6.2. Initiating a Route Discovery for intermediate nodes
after the node from which this target node
address results in overheard the packet and before
this node adding a Route Request option in
a DSR header itself, are no longer necessary in the source route. In
this existing packet, or saving case, this existing
packet to its Send Buffer and initiating node SHOULD perform the following sequence of steps
as part of automatic route shortening:

- The node searches its Gratuitous Route Discovery
by sending a separate packet containing such Reply Table for an entry
describing a gratuitous Route Request
option. If the node chooses to initiate the Route Discovery Reply earlier sent 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) [3], copying node,
for which the original IP Destination Address to the Target Address field sender of the new Route Request option added to the packet, as described in
Section 6.2.1.

- If the packet now does not contain a triggering the
gratuitous Route Request option,
then Reply and the transmitting node from which this
node must have a route overheard that packet in order to trigger the Destination Address
of the packet; if gratuitous
Route Reply, both match the respective node has more than one route to addresses for this
Destination Address,
new received packet. If such an entry is found in the node's
Gratuitous Route Reply Table, the node selects one SHOULD NOT perform
automatic route shortening in response to use for this packet.
If the length receipt of this route is greater than 1 hop, or if the
node determines to request a DSR network-layer acknowledgment
from
packet.

- Otherwise, the first-hop node creates an entry for this overheard packet in that route, then insert a DSR header
into the packet, as described in Section 6.1.2, and insert a DSR
Source
its Gratuitous Route option, as described in Section 6.1.3. Reply Table. The source
route in the packet is timeout value for this new
entry SHOULD be initialized from the selected route to the
Destination Address of value GratReplyHoldoff. After
this timeout has expired, the packet. node SHOULD delete this entry from
its Gratuitous Route Reply Table.

- Transmit After creating the packet to new Gratuitous Route Reply Table entry
above, the first-hop node address given in
selected source route, using originates a gratuitous Route Maintenance Reply to determine the
reachability
IP Source Address of the next hop, this overheard packet, as described in
Section 6.3.

6.1.2. Adding a DSR Header to a Packet

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

Johnson, et al Expires 21 24 August 2002 2003 [Page 41] 63]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

(these steps assume that 2003

If the packet contains no other headers that
MUST be located MAC protocol in use in the packet before the DSR header):

- Insert 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 DSR header after source route for routing the IP header but before any other
header Route Reply
packet that may be present.

- Set the Next Header field of the DSR header to is obtained by reversing the Protocol
number field sequence of hops over
which the packet's IP header.

- Set packet triggering the Protocol field gratuitous Route Reply was routed
in reaching and being overheard by this node; this reversing of
the packet's IP header to route uses the Protocol
number assigned for a DSR header (TBA???).

6.1.3. Adding a DSR Source Route Option to a Packet

A node originating a packet adds a DSR Source gratuitous Route option to the
packet, if necessary, in order Reply to carry test this sequence
of hops for bidirectionality, preventing the source route gratuitous Route
Reply from this
originating node to being received by the final destination address initiator of the packet.
Specifically, Route Discovery
unless each of the node adding hops over which the DSR Source gratuitous Route option constructs Reply is
returned is bidirectional.

- Discard the DSR Source Route option and modifies overheard packet, since the IP packet according to
the following sequence has been received
before its normal traversal of steps:

- The node creates a DSR Source Route option, as described in
Section 5.7, and appends the packet's source route would
have caused it to reach this receiving node. Another copy of
the DSR header in the packet.
(A DSR header is added, packet will normally arrive at this node as described indicated in Section 6.1.2, if not
already present.)

- The number
the packet's source route; discarding this initial copy of Address[i] fields to include in the DSR Source
packet, which triggered the gratuitous Route option (n) is Reply, will prevent
the number duplication of intermediate nodes in the
source route for this packet that would otherwise occur.

If the packet (i.e., excluding address is not discarded as part of automatic route shortening
above, then the
originating node and MUST process the final destination address option according to the
following sequence of steps:

- If the value 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 equals 0, then remove 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.
DSR Options header.

- The Last Hop External (L) bit Else, let n equal (Opt Data Len - 2) / 4. This is the number of
addresses in the DSR Source Route option is
copied from the External bit flagging the last hop in the source
route for option.

- If the packet, as indicated in value of the Route Cache.

- The Salvage Segments Left field in the DSR Source Route option is
initialized greater than n, then
send an ICMP Parameter Problem, Code 0, message [29] to 0.

Johnson, et al Expires 21 August 2002 [Page 42]

INTERNET-DRAFT The Dynamic the IP
Source Routing Protocol 21 February 2002

6.1.4. Processing a Received Packet

When a node receives any packet (whether for forwarding, overheard,
or as Address, pointing to the Segments Left field, and discard
the packet. Do not process the DSR Source Route option further.

- Else, decrement the final destination value of the packet), if that packet contains a
DSR header, then that node MUST process any options contained in that
DSR header, 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 order contained there. Specifically: Address vector.

- If Address[i] or the DSR header contains IP Destination Address is a Route Request option, the node
SHOULD extract multicast
address, then discard the source route from packet. Do not process the DSR Source
Route Request and add option further.

- If the MTU of the link over which this routing information node would transmit
the packet to its Route Cache, subject forward it to the
conditions identified in Section 3.3.1. The routing information
from the Route Request node Address[i] is less than
the sequence size of hop addresses

initiator, Address[1], Address[2], ..., Address[n]

where initiator is the value of packet, the node MUST either discard the
packet and send an ICMP Packet Too Big message to the packet's
Source Address field [29] or fragment it as specified in
the IP header of Section 8.5.

Johnson, et al Expires 24 August 2003 [Page 64]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

- Forward the packet carrying to the Route Request (the IP address of the initiator of the Route Discovery), and each
Address[i] is a node through which this Route Request has passed, specified in turn, during this Route Discovery. The value n here is the
number Address[i]
field of addresses recorded in the Route Request option, or
(Opt Data Len - 6) / 4.

After possibly updating IP header, following normal IP forwarding
procedures, including checking and decrementing the node's Route Cache Time-to-Live
(TTL) field in response to the routing information in packet's IP header [30, 3]. In this
forwarding of the Route Request option, packet, the next-hop node (identified by
Address[i]) MUST then process the Route Request option be treated as described in
Section 6.2.2.

- If the DSR header contains a Route Reply option, direct neighbor node: the
transmission to that next node SHOULD
extract the source route from the MUST be done in a single IP
forwarding hop, without Route Reply Discovery and add this
routing information to its Route Cache, subject to without searching the conditions
identified in Section 3.3.1. The source route from
Route Cache.

- In forwarding the packet, perform Route
Reply is Maintenance for the sequence of
next hop addresses

initiator, Address[1], Address[2], ..., Address[n]

where initiator is the value of the Destination Address field 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 header Destination Address field of the a packet carrying the Route Reply (the address
of the initiator of the a DSR Source
Route Discovery), and each Address[i]
is option in a node through which the source route passes, DSR Options header.

8.1.6. Handling an Unknown DSR Option

Nodes implementing DSR MUST handle all options specified in turn, on
the route this
document, except those options pertaining to the target 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 Route Discovery. Address[n] is DSR specification.
In DSR, Option Type codes encode required behavior for nodes not
implementing that type of option. These behaviors are included in
the address most significant three bits of the target. Option Type.

If the Last Hop External (L) 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 Route Reply, Error Type MUST be set to OPTION_NOT_SUPPORTED and
the node Unsupported Opt field MUST flag be set to the last hop from Option Type triggering
the Route Reply (the link from Address[n-1] to Address[n]) in
its Error.

Whether or not a Route Cache as External. The value n here Error is the number of
addresses sent in response to this DSR option,
as described above, the source route being returned in node also MUST examine the Route Reply
option, or (Opt next two most
significant bits (that is, Option Type & 0x60):

- When these two bits are zero (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.

- 1) / 4.

After possibly updating When these two bits are 01 (that is, Option Type & 0x60 == 0x20),
a node not implementing processing for that Option Type MUST use
the node's Route Cache in response Opt Data Len field to remove the option from the packet and

Johnson, et al Expires 24 August 2003 [Page 65]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

continue processing as if the option had not been included in the
received packet.

- When these two bits are 10 (that is, Option Type & 0x60 == 0x40),
a node not implementing processing for that Option Type MUST set
the routing information most significant bit following the Opt Data Len field; in
addition, the Route Reply option, node MUST then if ignore the contents of the option
using the Opt Data Len field, and MUST continue processing the
packet.

- Finally, when these two bits are 11 (that is,
Option Type & 0x60 == 0x60), a node not implementing processing
for that Option Type MUST drop the packet.

Johnson, et al Expires 21 24 August 2002 2003 [Page 43] 66]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

packet's IP Destination Address matches one of this node's IP
addresses, 2003

8.2. Route Discovery Processing

Route Discovery is the mechanism by which a node MUST then process the S wishing to send a
packet to a destination node D obtains a source route to D. Route Reply option
Discovery is 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
described in Section 6.2.5.

- If the DSR header contains a "initiator" of the Route Error option, Discovery, and the
destination node MUST
process for which the Route Error option Discovery is initiated is known
as described in Section 6.3.5.

- If the DSR header contains an Acknowledgment Request option, "target" of the Route Discovery.

Route Discovery operates entirely on demand, with a node MUST process the Acknowledgment Request option as described
in Section 6.3.3.

- If the DSR header contains an Acknowledgment option, then subject initiating
Route Discovery based on its own origination of new packets for
some destination address to the conditions identified 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 Section 3.3.1, the node SHOULD
add to its network protocol stack at any node.

The Route Cache the single link from the node identified
by the ACK Source Address field Discovery procedure utilizes two types of messages, a Route
Request (Section 6.2) and a Route Reply (Section 6.3), to actively
search the node identified by the
ACK Destination Address field.

After possibly updating the node's Route Cache in response ad hoc network for a route to the routing information desired destination.
These DSR messages MAY be carried in any type of IP packet, through
use of the Acknowledgment option, the node
MUST then process the Acknowledgment option DSR Options header as described in Section 6.3.3.

- If the DSR header contains 6.

Except as discussed in Section 8.3.5, a DSR Source Route option, the node Discovery for a
destination address SHOULD extract the source route from NOT be initiated unless the DSR Source Route and
add this routing information to initiating
node has a packet in its Route Cache, subject Send Buffer requiring delivery to the
conditions identified in Section 3.3.1. If the value of the
Salvage field in the DSR Source that
destination. A Route option is zero, then Discovery for a given target node MUST NOT be
initiated unless permitted by the
routing rate-limiting information from contained
in the DSR Source Route is the sequence of
hop addresses

source, Address[1], Address[2], ..., Address[n], destination

and otherwise (Salvage is nonzero), the routing information from
the DSR Source Request Table. After each Route is Discovery attempt, the sequence
interval between successive Route Discoveries for this target SHOULD
be doubled, up to a maximum of hop addresses

Address[1], Address[2], ..., Address[n], destination

where source MaxRequestPeriod, until a valid Route
Reply is the value of the Source Address field 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 the IP a DSR Options header of in some
IP packet. This MAY be a separate IP packet, used only to carry
this Route Request option, or the packet carrying node MAY include the DSR Source Route Request
option (the
original sender of the packet), each Address[i] is the value in
the Address[i] field in some existing packet that it needs to send to the DSR Source Route, and destination is target
node (e.g., the value of IP packet originated by this node, that caused the Destination Address field in
node to attempt Route Discovery for the packet's IP
header (the last-hop destination address of the source route).
packet). The value n
here is the number of addresses in source route Route Request option MUST be included in the a DSR Source
Route option, or (Opt Data Len - 2) / 4.

After possibly updating the node's Route Cache Options
header in response to the routing information in packet. To initialize the DSR Source Route Request option, the
node
MUST then process performs the DSR Source Route option as described following sequence of steps:

- The Option Type in
Section 6.1.5. the option MUST be set to the value 2.

Johnson, et al Expires 21 24 August 2002 2003 [Page 44] 67]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 February 2002

- Any Pad1 or PadN options in the DSR 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
header and all the included DSR options Routing Protocol 24 February 2003

- The Opt Data Len field in the header, and pass option MUST be set to the
rest value 6.
The total size of the packet to the network layer.

6.1.5. Processing a Received DSR Source Route Option

When a node receives a packet containing a DSR Source Route Request option
(whether for forwarding, overheard, or as when initiated
is 8 octets; the final destination Opt Data Len field excludes the size of the packet), that node SHOULD examine
Option Type and Opt Data Len fields themselves.

- The Identification field in the packet option MUST be set to determine if
the receipt of a new
value, different from that packet indicates an opportunity used for automatic
route shortening, as described in Section 3.4.3. Specifically, if other Route Requests recently
initiated by this node is not the intended next-hop destination 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 packet
but option MUST be set to the IP
address that is named in the later unexpended portion target of the source route this Route Discovery.

The Source Address in the packet's DSR Source Route option, then IP header of this packet indicates an
opportunity for automatic route shortening: MUST be the intermediate nodes
after node's
own IP address. The Destination Address in the node from which IP header of this node overheard the
packet and before
this MUST be the IP "limited broadcast" address (255.255.255.255).

A node itself, are no longer necessary MUST maintain in its Route Request Table, information about
Route Requests that it initiates. When initiating a new Route
Request, the source route. In
this case, this node SHOULD perform MUST use the information recorded in the following sequence of steps
as part of automatic route shortening:

- The node searches its Gratuitous Route Reply
Request Table for an entry
describing a gratuitous Route Reply earlier sent by this node, for which the original sender target of the packet triggering the
gratuitous that Route Reply Request, and the transmitting node from which this
node overheard it MUST
update that packet information in order to trigger the gratuitous
Route Reply, both match the respective node addresses for this
new received packet. If such an table entry is found for use in the node's
Gratuitous next Route Reply Table, the node SHOULD NOT perform
automatic route shortening in response to this receipt of
Request initiated for this
packet. target. In particular:

- Otherwise, the node creates an The Route Request Table entry for this overheard packet a target node records the
Time-to-Live (TTL) field used in
its Gratuitous the IP header of the Route Reply Table. The timeout value
Request for this new
entry SHOULD be initialized to the value GratReplyHoldoff. After last Route Discovery initiated by this timeout has expired, node for
that target node. This value allows the node SHOULD delete this entry from to implement a
variety of algorithms for controlling the spread of its Gratuitous Route Reply Table.

- After creating
Request on each Route Discovery initiated for a target. As
examples, two possible algorithms for this use of the new Gratuitous TTL field
are described in Section 3.3.4.

- The Route Reply Request Table entry
above, the for a target node originates records the
number of consecutive Route Requests initiated for this target
since receiving a gratuitous valid Route Reply giving a route to that target
node, and 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 remaining amount of
transmitting unicast packets over unidirectional links, as
discussed in Section 3.3.1, then in originating time before which this node MAY
next attempt at a Route Reply,
the Discovery for that target node.

A node MUST use these values to implement a source route back-off algorithm to
limit the rate at which this node initiates new Route Discoveries
for routing 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.

Johnson, et al Expires 21 24 August 2002 2003 [Page 45] 68]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

packet that is obtained by reversing the sequence 2003

The behavior of hops over
which the a node processing a packet triggering the gratuitous containing DSR Options
header with both a DSR Source Route Reply was routed
in reaching option and being overheard 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 node; this reversing
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 route uses Target Address field in the gratuitous Route Reply to test Request matches this sequence
of hops for bidirectionality, preventing
node's own IP address, then the gratuitous node SHOULD return a Route Reply from being received by
to the initiator of the Route Discovery
unless each of the hops over which the gratuitous this Route Reply is
returned is bidirectional.

- Discard the overheard packet, since Request (the Source Address in the packet has been received
before its normal traversal
IP header of the packet's packet), as described in Section 8.2.4. The
source route would
have caused it to reach for this receiving node. Another copy of Reply is the packet will normally arrive at this node as indicated in sequence of hop addresses

initiator, Address[1], Address[2], ..., Address[n], target

where initiator is the packet's source route; discarding this initial copy address of the
packet, which triggered initiator of this
Route Request, each Address[i] is an address from the gratuitous Route Reply, will prevent
Request, and target is the duplication target of this packet that would otherwise occur.

If the packet Route Request (the
Target Address field in the Route Request). The value n here
is not discarded as part the number of automatic route shortening
above, then addresses recorded in the Route Request, or
(Opt Data Len - 6) / 4.

The node then MUST process replace the option according to Destination Address field in
the
following sequence of steps:

- If Route Request packet's IP header with the value of in the Segments Left
Target Address field in the DSR Source Route Request option, and continue
processing the rest of the Route Request packet normally. The
node MUST NOT process the Route Request option equals 0, then remove further and MUST
NOT retransmit the DSR Source Route option from Request to propagate it to other nodes
as part of the
DSR header. Route Discovery.

- Else, let n equal (Opt Data Len - 2) / 4. This is the number of
addresses node MUST examine the route recorded in the DSR Source Route option.

- If
Request option (the IP Source Address field and the value sequence of the Segments Left field is greater than n, then
send an ICMP Parameter Problem, Code 0, message [26]
Address[i] fields) to the determine if this node's own IP
Source Address, pointing to address
already appears in this list of addresses. If so, the Segments Left field, and node MUST
discard the packet. Do not process entire packet carrying the DSR Source Route option further. Request option.

- Else, decrement if the value of Route Request was received through a network
interface that requires physically bidirectional links for

Johnson, et al Expires 24 August 2003 [Page 69]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

unicast transmission, the Segments Left field node MUST check if the Request was last
forwarded by 1. Let i
equal n minus Segments Left. This a node on its blacklist. If such an entry is found,
and the index state of the next
address to be visited in unidirectional link is "probable", then the Address vector.
Request MUST be silently discarded.

- If Address[i] or Else, if the IP Destination Address is Route Request was received through a multicast
address, then discard network
interface that requires physically bidirectional links for
unicast transmission, the packet. Do not process node MUST check if the DSR Source
Route option further.

- Request was last
forwarded by a node on its blacklist. If such an entry is found,
and the MTU state of the unidirectional link over which this node would transmit is "questionable",
then the node MUST create and unicast a Route Request packet to forward it
that previous node, setting the IP Time-To-Live (TTL) to 1 to
prevent the Request from being propagated. If the node Address[i] is less than receives
a Route Reply in response to the size of new Request, it MUST remove the packet,
blacklist entry for that node, and SHOULD continue processing.
If the node does not receive a Route Reply within some reasonable
amount of time, MUST either silently discard the
packet and send Route Request packet.

- Else, the node MUST search its Route Request Table for an ICMP Packet Too Big message to entry
for the packet's initiator of this Route Request (the IP Source Address [26] or fragment it as specified
field). If such an entry is found in Section 8.

- Forward the packet to table, the IP address specified in node MUST
search the Address[i]
field cache of Identification values of recently received
Route Requests in that table entry, to determine if an entry
is present in the IP header, following normal IP forwarding
procedures, including checking and decrementing cache matching the Time-to-Live

Johnson, et al Expires 21 August 2002 [Page 46]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 February 2002

(TTL) field Identification value
and target node address in the packet's IP header [27, 3]. In this
forwarding of the packet, Route Request. If such an
(Identification, target address) entry is found in this cache in
this entry in the next-hop node (identified by
Address[i]) MUST be treated as a direct neighbor node: Route Request Table, then the
transmission to that next node MUST be done in a single IP
forwarding hop, without Route Discovery and without searching discard
the entire packet carrying the Route Cache. Request option.

- In forwarding Else, this node SHOULD further process the packet, perform Route Maintenance 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
next hop following steps on the copy of the packet, by verifying that packet.

o Append this node's own IP address to the next-hop node is
reachable, as described in Section 6.3.

Multicast addresses MUST NOT appear list of Address[i]
values in a DSR Source the Route option or Request, and increase the value of the
Opt Data Len field in the Route Request by 4 (the size of an
IP Destination Address field address).

o This node SHOULD search its own Route Cache for a route
(from itself, as if it were the source of a packet carrying packet) to the
target of this Route Request. If such a DSR Source route is found in
its Route option Cache, then this node SHOULD follow the procedure
outlined in Section 8.2.3 to return a DSR header. "cached Route Reply"

Johnson, et al Expires 21 24 August 2002 2003 [Page 47]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 February 2002

6.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 is used only when S attempts to send a packet 70]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

to D and the initiator of this Route Request, if permitted by the
restrictions specified there.

o If the node does not already know return a route to D. The cached Route Reply, then this
node initiating SHOULD link-layer re-broadcast this copy of the packet,
with a Route
Discovery short jitter delay before the broadcast is known sent. The
jitter period SHOULD be chosen as the "initiator" of the Route Discovery, a random period, uniformly
distributed between 0 and BroadcastJitter.

8.2.3. Generating a Route Reply using the
destination node Route Cache

As described in Section 3.3.2, it is possible for which a node processing a
received Route Request to avoid propagating the Route Discovery is initiated is known
as Request further
toward the "target" target of the Request, if this node has in its Route Discovery. Cache
a route from itself to this target. Such a Route Discovery operates entirely on demand, with Reply generated by
a node initiating
Route Discovery based on from its own origination of new packets for
some destination address cached route 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 target of messages, a Route Request (Section 5.2) and is
called a "cached Route Reply (Section 5.3), to actively
search Reply", and this mechanism can greatly reduce
the overall overhead of Route Discovery on the ad hoc network for a route to by reducing
the desired destination.
These DSR messages MAY be carried in any type flood of IP packet, through
use Route Requests. The general processing of the DSR header as a received
Route Request is described in Section 5.

Except as discussed in Section 6.3.5, 8.2.2; this section specifies
the additional requirements that MUST be met before a cached Route Discovery for a
destination address SHOULD NOT
Reply may be initiated unless generated and returned and specifies the initiating
node has procedure for
returning such a packet in its Send Buffer requiring delivery to that
destination. A cached Route Discovery Reply.

While processing a received Route Request, for a given target node to possibly
return a cached Route Reply, it MUST NOT be
initiated unless permitted by the rate-limiting information contained have in the Route Request Table. After each its Route Discovery attempt, Cache a route
from itself to the
interval between successive Route Discoveries for this target SHOULD
be doubled, up to a maximum of MaxRequestPeriod, until this Route Request. However, before
generating a valid cached Route Reply is received for this target.

6.2.1. Originating a Route Request

A Request, the node initiating a Route Discovery for some target creates and
initializes a Route Request option MUST
verify that there are no duplicate addresses listed in a DSR header the route
accumulated in some IP packet.
This MAY the Route Request together with the route from this
node's Route Cache. Specifically, there MUST be a separate no duplicates among
the following addresses:

- The IP packet, used only to carry 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 option, or and the node MAY include route obtained from the Route Request option
in some existing packet that it needs to send to Cache).

If any duplicates exist among these addresses, then the target node
(e.g., the IP packet originated by this node, that caused the MUST NOT
send a cached Route Reply. The node SHOULD continue to
attempt Route Discovery for the destination address of process the packet).
The
Route Request option MUST be included in a DSR header as described in the
packet. To initialize Section 8.2.2.

If the Route Request option, and the node performs route from the following sequence of steps:

- The Option Type in Route Cache meet the option MUST be set to
restriction above, then the value 2. node SHOULD construct and return a cached
Route Reply as follows:

Johnson, et al Expires 21 24 August 2002 2003 [Page 48] 71]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002 2003

- The Opt Data Len field in the option MUST be set to source route for this reply is the value 6.
The total size sequence of the Route Request option when initiated hop addresses

initiator, Address[1], Address[2], ..., Address[n], c-route

where initiator is 8 octets; the Opt Data Len field excludes the size address 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 initiator of 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
Request, each Address[i] is an address that from the Route Request,
and c-route is the target sequence of hop addresses in the source route
to this target node, obtained from the node's Route Discovery.

The Source Address in Cache. In
appending this cached route to the IP header source route for the reply,
the address of this packet node itself MUST be excluded, since it is
already listed as Address[n].

- Send a Route Reply to the node's
own IP address. initiator of the Route Request, using
the procedure defined in Section 8.2.4. The Destination initiator of the
Route Request is indicated in the Source Address field in the
packet's IP header of this
packet MUST be header.

If the node returns a cached Route Reply as described above,
then the IP "limited broadcast" address (255.255.255.255).

A node MUST maintain in its NOT propagate the Route Request Table, information about
Route Requests that it initiates. When initiating a new Route
Request, further (i.e.,
the node MUST use NOT rebroadcast the information recorded in 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 Table entry for 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 that the Route Request, and Request. Specifically, if the node does so, it MUST
update that information in the table entry for use in
the next Route
Request initiated for this target. In particular: following steps:

- The Copy the Target Address from the Route Request Table entry for a target node records option in the
Time-to-Live (TTL) DSR
Options header to the Destination Address field used in the packet's
IP header of header.

- Remove the Route Request for option from the last DSR Options header in
the packet, and add a DSR Source Route Discovery initiated by this node for
that target node. This value allows option to the node packet's DSR
Options header.

- In the DSR Source Route option, set the Address[i] fields
to implement a
variety of algorithms for controlling represent the spread of its source route found in this node's Route
Request on each
Cache to the original target of the Route Discovery initiated for a target. As
examples, two possible algorithms for this use (the
new IP Destination Address of the TTL field
are described in Section 3.3.4.

- The Route Request Table entry for a target packet). Specifically,
the node records copies the
number hop addresses of consecutive the source route into
sequential Address[i] fields in the DSR Source Route Requests initiated option,
for this target
since receiving a valid Route Reply giving a route to that target
node, and i = 1, 2, ..., n. Address[1] here is the remaining amount address 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 itself (the first address in the rate at which source route found from
this node initiates new Route Discoveries
for to the same original target address. In particular, until a valid of the Route
Reply Discovery). The
value n here is received for this target node address, the timeout
between consecutive Route Discovery initiations for number of hop addresses in this target
node with source route,
excluding the same hop limit SHOULD increase by doubling destination of the
timeout value on each new initiation. packet (which is instead already
represented in the Destination Address field in the packet's IP
header).

Johnson, et al Expires 21 24 August 2002 2003 [Page 49] 72]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

The behavior of a node processing a packet containing DSR header
with both a 2003

- Initialize the Segments Left field in the DSR Source Route option and a Route Request option is
unspecified. Packets SHOULD NOT contain both a
to n as defined above.

- The First Hop External (F) bit in the DSR Source Route option and a Route Request option.

Packets containing a is
copied from the External bit flagging the first hop in the source
route for the packet, as indicated in the Route Request option SHOULD NOT include
an Acknowledgment Request option, SHOULD NOT expect link-layer
acknowledgment or passive acknowledgment, and SHOULD NOT be
retransmitted. Cache.

- The retransmission of packets containing a Last Hop External (L) bit in the DSR Source Route
Request option is controlled solely by
copied from the logic described External bit flagging the last hop in this
section.

6.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 source
route for the following sequence of
steps:

- If packet, as indicated in the Target Address Route Cache.

- The Salvage field in the DSR Source Route Request matches this
node's own IP address, then option MUST be
initialized to some nonzero value; the node particular nonzero value
used SHOULD return be MAX_SALVAGE_COUNT. By initializing this field to
a nonzero value, nodes forwarding or overhearing this packet will
not consider a Route Reply link to exist between the initiator of this Route Request (the IP Source Address in the
IP header of the packet), as described in Section 6.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
packet and the Address[1] address of in the initiator of DSR Source Route option
(e.g., they will not attempt to add this to their Route Request, each Address[i] is an address from Cache as
a link). By choosing MAX_SALVAGE_COUNT as the Route
Request, and target is nonzero value to
which the target of node initializes this field, nodes furthermore will not
attempt to salvage this packet.

- Transmit the Route Request (the
Target Address field in packet to the Route Request). The value n here
is next-hop node on the number of addresses recorded new source route
in the packet, using the forwarding procedure described in
Section 8.1.5.

8.2.4. Originating a Route Request, or
(Opt Data Len - 6) / 4.

The Reply

A node then MUST replace the Destination Address field originates a Route Reply in
the order to reply to a received and
processed Route Request packet's IP header with Request, according to the value procedures described in the
Target Address field
Sections 8.2.2 and 8.2.3. The Route Reply is returned in the a Route Request option, and continue
processing
Reply option (Section 6.3). The Route Reply option MAY be returned
to the rest 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 normally. being sent to this address.

The
node MUST NOT process the Route Request Reply option further and MUST
NOT retransmit be included in a DSR Options header in
the Route Request to propagate it packet returned to other nodes
as part of the initiator. To initialize the Route Discovery.

- Else, Reply
option, the node MUST examine performs the route recorded following sequence of steps:

- The Option Type in the Route
Request option (the IP Source Address field and the sequence of
Address[i] fields) MUST be set to determine if this node's own IP address
already appears the value 3.

- The Opt Data Len field in this list of addresses. If so, the node option MUST
discard be set to the entire packet carrying value
(n * 4) + 3, where n is the number of addresses in the source
route being returned (excluding the Route Request option. Discovery initiator
node's address).

- Else, if The Last Hop External (L) bit in the Route Request through a network interface that
requires physically bidirectional links for unicast transmission, option MUST be
initialized to 0.

Johnson, et al Expires 21 24 August 2002 2003 [Page 50] 73]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002 2003

- The Reserved field in the node option MUST check if be initialized to 0.

- The Route Request Identifier MUST be initialized to the
Identifier field of the Route Request was last forwarded by a node
on its blacklist. If such an entry that this reply is found, and sent in
response to.

- The sequence of hop addresses in the state source route are copied into
the Address[i] fields of the unidirectional link is "probable," then option. Address[1] MUST be set to
the Request 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
silently discarded.

- Else, if the Route Request through a network interface that
requires physically bidirectional links for unicast transmission, set to the node MUST check if next address in sequence in
the Request was last forwarded by a node
on its blacklist. If such an entry is found, and source route being returned.

The Destination Address field in the state IP header of the unidirectional link is "questionable," then packet carrying
the node MUST
create and unicast a Route Request packet Reply option MUST be set to that previous node,
setting the IP Time-To-Live (TTL) to 1 to prevent address of the Request
from being propagated. If initiator
of the node receives Route Discovery (i.e., for a Route Reply being returned in
response to the new some Route Request, it MUST remove the blacklist entry
for that node, IP Source Address of the Route
Request).

After creating and SHOULD continue processing. If initializing the node does
not receive a Route Reply within some reasonable amount of time, MUST
silently discard option and the IP
packet containing it, send the Route Request packet.

- Else, Reply. In sending the node MUST search its Route Request Table for an entry
for
Reply from this node (but not from nodes forwarding the initiator of Route Reply),
this node SHOULD delay the Reply by a small jitter period chosen
randomly between 0 and BroadcastJitter.

When returning any Route Request (the IP Source Address
field). If such an entry is found Reply in the table, case in which the node 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
search be obtained by reversing the cache of Identification values sequence of recently received
Route Requests
hops in the Route Request packet (the source route that table entry, to determine if an entry is present then
returned in the cache matching Route Reply). This restriction on returning a Route
Reply enables the Identification value
and target node address in this Route Request. If such an
(Identification, target address) entry is found in this cache in Reply to test this entry in sequence of hops for
bidirectionality, preventing the Route Request Table, then Reply from being received by
the node MUST discard initiator of the entire packet carrying Route Discovery unless each of the hops over
which the Route Request option.

- Else, this node SHOULD further process Reply is returned (and thus each of the hops in the
source route being returned in the Reply) is bidirectional.

If sending a Route Request
according Reply to the following sequence initiator of steps:

o Add an entry for this the Route Request in its cache of
(Identification, target address) values of recently received
Route Requests.

o Conceptually create
requires performing a copy of this entire packet and perform Route Discovery, the following steps Route Reply option MUST
be piggybacked on the copy of packet that contains the packet.

o Append this node's own IP address to Route Request. This
piggybacking prevents a loop wherein the list target of Address[i]
values in the new Route Request, and increase
Request (which was itself the value initiator of the
Opt Data Len field in the original Route
Request) must do another Route Request by 4 (the size of an
IP address).

o This node SHOULD search in order to return its own Route Cache for a route
(from itself, as if it were
Route Reply.

If sending the source of a packet) Route Reply to the
target initiator of this the Route Request. If such Request
does not require performing a route is found in
its Route Cache, then this Discovery, a node SHOULD follow the procedure
outlined send a
unicast Route Reply in Section 6.2.3 response to return a "cached every Route Reply" Request it receives
for which it is the target node.

Johnson, et al Expires 21 24 August 2002 2003 [Page 51] 74]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

to 2003

8.2.5. Processing a Received Route Reply Option

Section 8.1.4 describes the initiator general processing for a received packet,
including the addition of this Route Request, if permitted by routing information from options in the
restrictions specified there.

o
packet's DSR Options header to the receiving node's Route Cache.

If the node does not return received packet contains a cached Route Reply, then this
node SHOULD link-layer re-broadcast this copy no additional special
processing of the packet,
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.

6.2.3. Generating a Route Reply using the Route Cache option is required beyond what is
described there. As described in Section 3.3.2, it is possible for 4.1 anytime a node processing a
received Route Request adds
new information to avoid propagating the Route Request further
toward the target of the Request, if this node has in its Route Cache
a route (including the information added
from itself to this target. Such a Route Reply generated by
a option), the node from SHOULD check each packet in
its own cached route Send Buffer (Section 4.2) to the target of a Route Request is
called determine whether a "cached Route Reply", and this mechanism can greatly reduce route to
that packet's IP Destination Address now exists in the overall overhead of node's Route Discovery on
Cache (including the network by reducing information just added to the flood of Route Requests. The general processing of a received
Route Request is described in Section 6.2.2; this section specifies Cache). If so,
the additional requirements that MUST be met before a cached Route
Reply may packet SHOULD then be generated and returned sent using that route and specifies removed from the
Send Buffer. This general procedure for
returning such a cached Route Reply.

While handles all processing required
for a received Route Request, for a node to possibly
return Reply option.

When a cached Route Reply, it MUST have in its Route Cache MAC protocol requires bidirectional links for unicast
transmission, a route
from itself to unidirectional link may be discovered by the target
propagation of this the Route Request. However, before
generating a cached When the Route Reply for 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.

Johnson, et al Expires 24 August 2003 [Page 75]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

8.3. Route Request, Maintenance Processing

Route Maintenance is the mechanism by which a source node MUST
verify S is able
to detect, while using a source route to some destination node D,
if the network topology has changed such that there are it can no duplicate addresses listed in the longer use
its route
accumulated in 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 Request together with the Discovery again to find a new route from this
node's for subsequent packets
to D. Route Cache. Maintenance for this route is used only when S is
actually sending packets to D.

Specifically, there when forwarding a packet, a node MUST be no duplicates among attempt
to confirm the following addresses:

- The IP Source Address reachability of the packet containing the Route Request,

- The Address[i] fields in the Route Request, and

- The nodes listed next-hop node, unless such
confirmation had been received in the route obtained from this node's Route
Cache, excluding the address last MaintHoldoffTime.
Individual implementations MAY choose to bypass such confirmation
for some limited number of this node itself (this node
itself packets, as long as those packets all
fall within MaintHoldoffTime within the last confirmation. If no
confirmation is received after the common point between retransmission of MaxMaintRexmt
acknowledgement requests, after the route accumulated in initial transmission of the
Route Request
packet, and conceptually including all retransmissions provided
by the route obtained from the Route Cache).

If any duplicates exist among these addresses, then MAC layer, the node MUST NOT
send a cached Route Reply. The node SHOULD continue to process the
Route Request as described in Section 6.2.2.

If determines that the Route Request and link for this
next-hop node of the source route is "broken". This confirmation
from the next-hop node for Route Cache meet Maintenance can be implemented
using a link-layer acknowledgement (Section 8.3.1), using a
"passive acknowledgement" (Section 8.3.2), or using a network-layer
acknowledgement (Section 8.3.3); the
restriction above, then particular strategy for
retransmission timing depends on the type of acknowledgement
mechanism used. When passive acknowledgements are being used, each
retransmitted acknowledgement request SHOULD be explicit software
acknowledgement requests. If no acknowledgement is received after
MaxMaintRexmt retransmissions (if necessary), the node SHOULD construct and return
originate a cached Route Reply as follows:

Johnson, et al Expires 21 August 2002 [Page 52]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 February 2002

- The source route for this reply is the sequence of hop addresses

initiator, Address[1], Address[2], ..., Address[n], c-route

where initiator is Error to the address original sender of the initiator of this packet, as
described in Section 8.3.4.

In deciding whether or not to send a Route
Request, each Address[i] is an address Error in response to
attempting to forward a packet from some sender over a broken link,
a node MUST limit the Route Request,
and c-route is the sequence number of hop addresses in consecutive packets from a single
sender that the source route node attempts to forward over this target node, obtained from same broken
link for which the node's node chooses not to return a Route Cache. In
appending Error; this cached route to the source route
requirement MAY be satisfied by returning a Route Error for each
packet that the reply,
the address of this node itself MUST be excluded, since it is
already listed as Address[n].

- Send attempts to forward over a Route Reply broken link.

8.3.1. Using Link-Layer Acknowledgements

If the MAC protocol in use provides feedback as to the initiator successful
delivery of a data packet (such as is provided by the Route Request, using
the procedure link-layer
acknowledgement frame defined in Section 6.2.4. The initiator by IEEE 802.11 [13]), then the use
of the
Route DSR Acknowledgement Request is indicated in the Source Address field in the
packet's IP header. and Acknowledgement options

Johnson, et al Expires 24 August 2003 [Page 76]

INTERNET-DRAFT The Dynamic Source Routing Protocol 24 February 2003

is not necessary. If the node returns a cached such link-layer feedback is available, it
SHOULD be used instead of any other acknowledgement mechanism
for Route Reply as described above, then Maintenance, and the node MUST SHOULD NOT propagate the use either passive
acknowledgements or network-layer acknowledgements for Route Request further (i.e., the
node MUST NOT rebroadcast the
Maintenance.

When using link-layer acknowledgements for Route Request). In this case, instead,
if Maintenance, the packet contains no other DSR options
retransmission timing and contains no payload
after the DSR header (e.g., timing at which retransmission attempts
are scheduled are generally controlled by the Route Request is not piggybacked
on a TCP or UDP packet), then particular link layer
implementation in use in the node SHOULD simply discard network. For example, in IEEE 802.11,
the
packet. Otherwise (if link-layer acknowledgement is returned after the data packet contains other DSR options or
contains any payload after as
a part of the DSR header), basic access method of of the node SHOULD forward IEEE 802.11 Distributed
Coordination Function (DCF) MAC protocol; the packet along time at which the cached route
acknowledgement is expected to arrive and the target of time at which the Route Request.
Specifically, if next
retransmission attempt (if necessary) will occur are controlled by
the MAC protocol implementation.

When a node does so, it MUST use the following
steps:

- Copy receives a link-layer acknowledgement for any packet in
its Maintenance Buffer, that node SHOULD remove that packet, as well
as any other packets in its Maintenance Buffer with the Target Address same next-hop
destination, from the its Maintenance Buffer.

8.3.2. Using Passive Acknowledgements

When link-layer acknowledgements are not available, but passive
acknowledgements [18] are available, passive acknowledgements SHOULD
be used for Route Request option in Maintenance when originating or forwarding a packet
along any hop other than the
DSR header last hop (the hop leading to the IP
Destination Address field in the packet's IP
header.

- Remove node of the packet). In particular, passive
acknowledgements SHOULD be used for Route Request option from the DSR header Maintenance in such cases
if the
packet, node can place its network interface into "promiscuous"
receive mode, and add a DSR Source Route option to the packet's DSR
header.

- In the DSR Source Route option, set the Address[i] fields network links used for data packets generally
operate bidirectionally.

A node MUST NOT attempt to represent the source route found in this node's use passive acknowledgements for Route
Cache
Maintenance for a packet originated or forwarded over its last hop
(the hop leading 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 packet),
since the address of this receiving node itself (the first address in will not be forwarding the source route found from packet and thus
no passive acknowledgement will be available to be heard by this
node. Beyond this restriction, a node to the original target MAY utilize a variety of the
strategies in using passive acknowledgements for Route Discovery). The
value n here is the number Maintenance of hop addresses in this source route,
excluding
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 (which without requesting a network-layer acknowledgement
for it. If no passive acknowledgement is instead already
represented in the Destination Address field in the packet's IP
header). received within

Johnson, et al Expires 21 24 August 2002 2003 [Page 53] 77]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002

- 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 is
copied from the External bit flagging the first hop in 2003

PassiveAckTimeout after this transmission, the source
route for node retransmits
the packet, as indicated in the Route Cache.

- The Last Hop External (L) bit in again without requesting a network-layer
acknowledgement for it; the DSR Source Route option same PassiveAckTimeout timeout value
is
copied from the External bit flagging the last hop in the source
route used for each such attempt. If no acknowledgement has been
received after a total of TryPassiveAcks retransmissions of
the packet, as indicated network-layer acknowledgements (as described in the Route Cache.
Section 8.3.3) are used for all remaining attempts for that
packet.

- The Salvage field in the DSR Source Route option MUST Each node maintains a table of possible next-hop destination
nodes, noting whether or not passive acknowledgements can
typically be
initialized expected from transmission to some nonzero value; that node, and the particular nonzero value
used SHOULD be MAX_SALVAGE_COUNT. By initializing this field to
expected latency and jitter of a nonzero value, nodes forwarding or overhearing this packet will
not consider passive acknowledgement from
that node. Each time a node receives 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 be forwarded
to their Route Cache as a link). By choosing MAX_SALVAGE_COUNT as node other than the nonzero value to
which IP Destination Address, the node initializes this field, checks
its table of next-hop destination nodes furthermore will not
attempt to salvage determine whether to
use a passive acknowledgement or a network-layer acknowledgement
for that transmission to that node. The timeout for this packet.

- Transmit the packet to the next-hop
can also be derived from this table. A node on the new source route
in the packet, using the forwarding procedure described in
Section 6.1.5.

6.2.4. Originating this method
SHOULD prefer using passive acknowledgements to network-layer
acknowledgements.

In using passive acknowledgements for a Route Reply

A node packet that it originates or
forwards, a Route Reply in order to reply to node considers the later receipt of a received and
processed Route Request, according new packet (e.g.,
with promiscuous receive mode enabled on its network interface) to be
an acknowledgement of this first packet if both of the procedures described in
Sections 6.2.2 and 6.2.3. following two
tests succeed:

- The Route Reply is returned Source Address, Destination Address, Protocol,
Identification, and Fragment Offset fields in a Route
Reply option (Section 5.3). The Route Reply option MAY be returned
to the initiator IP header
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 two packets MUST be included in match [30], and

- If either packet contains a DSR header in Source Route header, both packets
MUST contain one, and the packet
returned to value in the initiator. To initialize Segments Left field in the
DSR Source Route Reply option, the
node performs the following sequence header of steps:

- The Option Type in the option new packet MUST be set to less than that
in the value 3.

- The Opt Data Len field first packet.

When a node hears such a passive acknowledgement for any packet in
its Maintenance Buffer, that node SHOULD remove that packet, as well
as any other packets in its Maintenance Buffer with the option MUST be set same next-hop
destination, from its Maintenance Buffer.

8.3.3. Using Network-Layer Acknowledgements

When a node originates or forwards a packet and has no other
mechanism of acknowledgement available to the value
(n * 4) + 3, where n is the number determine reachability
of addresses the next-hop node in the source route being returned (excluding the for Route Discovery initiator
node's address).

- The Last Hop External (L) bit in Maintenance,
that node SHOULD request a network-layer acknowledgement from that
next-hop node. To do so, the option MUST be
initialized to 0. node inserts an Acknowledgement Request

Johnson, et al Expires 21 24 August 2002 2003 [Page 54] 78]

INTERNET-DRAFT The Dynamic Source Routing Protocol 21 24 February 2002 2003

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 transmitted by this node to the same next-hop
node that are either unacknowledged or recently ack