WDIFF

draft-ietf-manet-dsr-03.txt --> draft-ietf-manet-dsr-05.txt

IETF MANET Working Group Josh Broch
INTERNET-DRAFT David B. Johnson Johnson, Rice University
INTERNET-DRAFT David A. Maltz Maltz, AON Networks
2 March 2001 Yih-Chun Hu, Rice University
Jorjeta G. Jetcheva, Carnegie Mellon University
22 October 1999

The Dynamic Source Routing Protocol for Mobile Ad Hoc Networks

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

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

Status of This Memo

This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC 2026 except that the right to
produce derivative works is not granted.

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." 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 2 September 2001 [Page i]

INTERNET-DRAFT The Dynamic Source Routing Protocol 2 March 2001

Abstract

The Dynamic Source Routing protocol (DSR) is a simple and efficient
routing protocol designed specifically for use in mobile multi-hop wireless
ad hoc networks. 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 allows is composed of the two mechanisms of "Route Discovery"
and "Route Maintenance", which work together to allow nodes to dynamically
discover a and maintain source route across multiple network
hops routes to any destination arbitrary destinations in the
ad hoc network. When using The use of source
routing, each routing allows packet routing
to be routed carries trivially loop-free, avoids the need for up-to-date routing
information in its header the complete,
ordered list of intermediate nodes through which the packet must pass. A key
advantage of source routing is that intermediate hops do not need packets are
forwarded, and allows nodes forwarding or overhearing packets to maintain
cache the routing information in order to route the packets they
receive, since the packets themselves already contain all them for their own future use. All
aspects of the
necessary routing information. This, coupled with protocol operate entirely on-demand, allowing the dynamic,
on-demand nature
routing packet overhead of DSR's Route Discovery, completely eliminates DSR to scale automatically to only that
needed to react to changes in the
need for periodic router advertisements and link status packets,
significantly reducing routes currently in use. This
document specifies the overhead operation of DSR, especially during periods
when the network topology is stable and these DSR protocol for routing
unicast IP packets serve only as
keep-alives.

Broch, in multi-hop wireless ad hoc networks.

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page i] ii]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999 2 March 2001

Contents

Status of This Memo i

Abstract i ii

1. Introduction 1

2. Changes 1

3. Assumptions 1

4. Terminology 2
4.1. General Terms 3

3. DSR Protocol Overview 5
3.1. Basic DSR Route Discovery . . . . . . . . . . . . . . . . 5
3.2. Basic DSR Route Maintenance . . . . . . 2
4.2. Specification Language . . . . . . . . . 7
3.3. Additional Route Discovery Features . . . . . . . . 4

5. Protocol Overview 5
5.1. . . . 8
3.3.1. Caching Overheard Routing Information . . . . . . 8
3.3.2. Replying to Route Discovery and Requests using Cached Routes . 9
3.3.3. Preventing Route Maintenance Reply Storms . . . . . . . . . . 5
5.2. Packet Forwarding 10
3.3.4. Route Request Hop Limits . . . . . . . . . . . . 12
3.4. Additional Route Maintenance Features . . . . . . . . . . 6
5.3. Multicast Routing 13
3.4.1. Packet Salvaging . . . . . . . . . . . . . . . . 13
3.4.2. Automatic Route Shortening . . . . 7

6. . . . . . . . 13
3.4.3. Increased Spreading of Route Error Messages . . . 14

4. Conceptual Data Structures 7
6.1. 15
4.1. Route Cache . . . . . . . . . . . . . . . . . . . . . . . 7
6.2. 15
4.2. Route Request Table . . . . . . . . . . . . . . . . . . . 9
6.3. 17
4.3. Send Buffer . . . . . . . . . . . . . . . . . . . . . . . 9
6.4. 18
4.4. Retransmission Buffer . . . . . . . . . . . . . . . . . . 9

7. Packet Formats 11
7.1. Destination Options Headers 19

5. DSR Header Format 20
5.1. Fixed Portion of DSR Header . . . . . . . . . . . . . . . 11
7.1.1. DSR 21
5.2. Route Request Option . . . . . . . . . . . . 12
7.2. Hop-by-Hop Options Headers . . . . . . . . . 23
5.3. Route Reply Option . . . . . . 14
7.2.1. DSR Route Reply Option . . . . . . . . . . . . . 15
7.2.2. DSR 25
5.4. Route Error Option . . . . . . . . . . . . . 17
7.2.3. DSR Acknowledgment Option . . . . . . . 27
5.5. Acknowledgment Request Option . . . . . 18
7.3. DSR Routing Header . . . . . . . . . 29
5.6. Acknowledgment Option . . . . . . . . . . 20

8. Detailed Operation 23
8.1. Originating a Data Packet . . . . . . . . 30
5.7. Source Route Option . . . . . . . . 23
8.2. Originating a Packet with a DSR Routing Header . . . . . 23
8.3. Processing a Routing Header . . . . . . 31
5.8. Pad1 Option . . . . . . . . . 24
8.4. Route Discovery . . . . . . . . . . . . . . 33
5.9. PadN Option . . . . . . . 25
8.4.1. Originating a Route Request . . . . . . . . . . . 25
8.4.2. Processing a Route Request Option . . . . . 34

6. Detailed Operation 35
6.1. General Packet Processing . . . 26
8.4.3. Generating Route Replies using the Route Cache . 27
8.4.4. Originating a Route Reply . . . . . . . . . . . . 28
8.4.5. Processing 35
6.1.1. Originating a Route Reply Option Packet . . . . . . . . . 29

Broch, Johnson, and Maltz Expires 22 April 2000 [Page ii]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

8.5. Route Maintenance . . . . . 35
6.1.2. Adding a DSR Header to a Packet . . . . . . . . . . . . . . . 30
8.5.1. Using Network-Layer Acknowledgments . . . . . . . 30
8.5.2. Using Link Layer Acknowledgments . . . . . . . . 32
8.5.3. Originating a Route Error . . . . . . . . . . . . 32
8.5.4. Processing 35
6.1.3. Adding a Source Route Error Option to a Packet . . . . . . . . . 33
8.5.5. Salvaging 36
6.1.4. Receiving a Packet . . . . . . . . . . . . . . . 33

9. Optimizations 35
9.1. Leveraging the 36

Johnson, et al Expires 2 September 2001 [Page iii]

INTERNET-DRAFT The Dynamic Source Routing Protocol 2 March 2001

6.1.5. Processing a Received Source Route Cache . . Option . . . . 38
6.2. Route Discovery Processing . . . . . . . . . 35
9.1.1. Promiscuous Learning of Source Routes . . . . . . 35
9.2. Preventing 40
6.2.1. Originating a Route Reply Storms . . . Request . . . . . . . . . . . 36
9.3. Piggybacking on 40
6.2.2. Processing a Received Route Discoveries . . . . . . . . . . . . 37
9.4. Discovering Shorter Routes . . . . . . . . . . . . Request Option . . . 37
9.5. Rate Limiting 42
6.2.3. Generating Route Replies using the Route Discovery Process . Cache . 43
6.2.4. Originating a Route Reply . . . . . . 38
9.6. Improved Handling of Route Errors . . . . . . 44
6.2.5. Processing a Route Reply Option . . . . . . 39
9.7. Increasing Scalability . . . 46
6.3. Route Maintenance Processing . . . . . . . . . . . . . . 39

10. Path-State and Flow-State Mechanisms 40
10.1. Overview 47
6.3.1. Using Network-Layer Acknowledgments . . . . . . . 47
6.3.2. Using Link Layer Acknowledgments . . . . . . . . 48
6.3.3. Originating a Route Error . . . . . . . . . 40
10.2. Path-State and Flow-State Identifiers . . . 48
6.3.4. Processing a Route Error Option . . . . . . . 41
10.3. Path-State Creation, Use, and Maintenance . . 49
6.3.5. Salvaging a Packet . . . . . . 42
10.3.1. Creating Path-State for Routing . . . . . . . . . 42
10.3.2. Monitoring Characteristics 49

7. Constants 50

8. IANA Considerations 51

9. Security Considerations 52

Appendix A. Location of DSR in the Path . . . . . 43
10.3.3. Candidate Metrics . . . . . . . . . . . . . . . . 45
10.4. Flow-State Creation, Use, ISO Network Reference Model 53

Appendix B. Implementation and Maintenance . . . . . . . . 46
10.4.1. Requesting Promises along Existing Paths . . . . 46
10.4.2. Requesting Promises as Part of Route Discovery . 48
10.4.3. Providing Notifications of Changing Path Metrics 49
10.5. Expiration of State from Intermediate Nodes . . . . . . . 50
10.6. Packet Formats . . . . . . . . . . . . . . . . . . . . . 51
10.6.1. Identifier Option . . . . . . . . . . . . . . . . 51
10.6.2. Path-Metrics Option . . . . . . . . . . . . . . . 52
10.6.3. Flow Request Option . . . . . . . . . . . . . . . Evaluation Status 54
10.6.4. Encoding Path-Metrics . . . . . . . . . . . . . .

Acknowledgements 55

11. Constants 58

12. IANA Considerations 59

13. Security Considerations 60

Location of DSR Functions in the ISO Model 61

Implementation Status 62

Acknowledgments 63

References 64 56

Chair's Address 66

Broch, Johnson, and Maltz Expires 22 April 2000 [Page iii]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999 59

Authors' Addresses 67

Broch, 60

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page iv]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999 2 March 2001

1. Introduction

This document describes

The Dynamic Source Routing protocol (DSR) [8, 9], [12, 13] is a simple and
efficient routing protocol developed by the Monarch Project [10, 19] at Carnegie Mellon
University designed specifically for routing packets use in a mobile multi-hop
wireless ad hoc network [5].

Source routing is a routing technique in which the sender networks of a packet
determines mobile nodes. Using DSR, the complete sequence of network
is completely self-organizing and self-configuring, requiring no
existing network infrastructure or administration. Network nodes through which
cooperate to forward
the packet; the sender explicitly lists this route in the packet's
header, identifying packets for each forwarding "hop" by the address of the next
node to which to transmit the packet on its way other to the destination
node.

DSR offers a number of potential advantages allow communication
over other routing
protocols for mobile ad hoc networks. First, DSR uses no periodic
routing messages multiple "hops" between nodes not directly within wireless
transmission range of any kind (e.g., no router advertisements and no
link-level neighbor status messages), thereby significantly reducing one another. As nodes in the network bandwidth overhead, conserving battery power, reducing move
about or join or leave the
probability of packet collision, network, and avoiding the propagation of
potentially large routing updates throughout the ad hoc network. Our
Dynamic Source Routing protocol is able to adapt quickly to changes as wireless transmission
conditions such as node movement, yet requires no sources of interference change, all routing protocol overhead
during periods in which no such changes occur.

In addition, is
automatically determined and maintained by the DSR has been designed to compute correct routes in routing protocol.
Since the presence of asymmetric (uni-directional) links. In wireless
networks, links may at times operate asymmetrically due to sources
of interference, differing radio or antenna capabilities, number or the
intentional use sequence of asymmetric communication technology such as
satellites. Due intermediate hops needed to reach any
destination may change at any time, the existence of asymmetric links, traditional
link-state or distance vector protocols resulting network topology
may compute routes that do
not work. DSR, however, will always find be quite rich and rapidly changing.

The DSR protocol allows nodes to dynamically discover a correct source
route even across multiple network hops to any destination in the
presence ad hoc
network. Each data packet sent then carries in its header the
complete, ordered list of asymmetric links.

2. Changes

Changes from version 02 nodes through which the packet will pass,
allowing packet routing to version 03 (10/1999)

- Added description of path-state be trivially loop-free and flow-state maintenance
(Section 10). These extensions remove avoiding the
need for every
data up-to-date routing information in the intermediate nodes
through which the packet to carry a is forwarded. By including this source route, thereby decreasing
route in the byte-overhead header of DSR. They each data packet, other nodes forwarding or
overhearing any of these packets may also provide a framework easily cache this routing
information for
supporting QoS inside DSR networks.

3. Assumptions

We assume future use.

In designing DSR, we sought to create a routing protocol that all nodes wishing had
very low overhead yet was able to communicate with other nodes
within the ad hoc network are willing react quickly to participate fully changes in the

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 1]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

protocols of the
network. In particular, each node participating in
the network should also be willing The DSR protocol provides highly reactive service to forward help
ensure successful delivery of data packets for other nodes in the network.

We refer to the minimum number spite of hops necessary for a packet to
reach from any node located at one extreme edge of the movement
or other changes in network to
another node located at the opposite extreme, as the diameter conditions.

The DSR protocol is composed of the
network. We assume two mechanisms that work together to
allow the diameter discovery and maintenance of an source routes in the ad hoc network will 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
network:

- Route Discovery is the wireless
network. A node receiving mechanism by which a corrupted packet can detect the error
and discard the packet.

We assume that nodes can enable promiscuous receive mode on their
wireless network interface hardware, causing the hardware node S wishing to
deliver every received
send a packet to the network driver software without
filtering based on link-layer a destination address. Although we do
not require this facility, it node D obtains a source route
to D. Route Discovery is for example common in current LAN
hardware for broadcast media including wireless, used only when S attempts to send a
packet to D and some of our
optimizations take advantage of its availability. Use of promiscuous
mode does increase not already know a route to D.

- Route Maintenance is the software overhead on mechanism by which node S is able
to detect, while using a source route to D, if the CPU, but we believe
that wireless network speeds are more the inherent limiting factor
to performance in current and future systems. We also believe
topology has changed such that portions of it can no longer use its route
to D because a link along the protocol are also suitable for implementation
directly within route no longer works. When Route
Maintenance indicates a programmable network interface unit source route is broken, S can attempt to avoid this
overhead on the CPU.

4. Terminology

4.1. General Terms

link

A communication facility
use any other route it happens to know to D, or medium over which nodes can
communicate at the link layer, such as an Ethernet (simple or
bridged). A link is the layer immediately below IP.

interface

A node's attachment invoke Route
Discovery again to find a link.

prefix

A bit string that consists of some number of initial bits of an
address.

Broch, new route for subsequent packets to D.

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 2] 1]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

interface index

An 7-bit quantity which uniquely identifies an interface among
a given node's interfaces. Each node can assign interface
indices to its interfaces using any scheme it wishes.

The index IF_INDEX_MA is reserved 2 March 2001

Route Maintenance for this route is used only when S is actually
sending packets 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 level within the network. For
example, DSR does not use by Mobile IP [14]
mobility agents (home any periodic routing advertisement, link
status sensing, or foreign agents) neighbor detection packets, and does not rely on
these functions from any underlying protocols in the network. This
entirely on-demand behavior and lack of periodic activity allows
the number of overhead packets caused by DSR to indicate that they
believe they can reach a destination via a connected internet
infrastructure. The index IF_INDEX_ROUTER is reserved scale all the way
down to zero, when all nodes are approximately stationary with
respect to each other and all routes needed for
use by routers not acting current communication
have already been discovered. As nodes begin to move more or
as Mobile IP mobility agents communication patterns change, the routing packet overhead of
DSR automatically scales to
indicate only that they believe they can reach the destination via a
connected internet infrastructure.

The distinction between needed to track the index for mobility agents routes
currently in use. Network topology changes not affecting routes
currently in use are ignored and do not cause reaction from the index for routers, allows mobility agents
protocol.

In response to advertise
their existence ``for free''. A node that processes a single Route Discovery (as well as through routing
header listing the interface index IF_INDEX_MA, can then send
information from other packets overheard), a unicast Agent Solicitation node may learn and cache
multiple routes to any destination. This allows the corresponding address in
the reaction to
routing header changes to obtain complete information about be much more rapid, since a node with multiple
routes to a destination can try another cached route if the
mobility services being provided.

link-layer address

A link-layer identifier for an interface, such as IEEE 802
addresses on Ethernet links.

packet

An IP header plus payload.

piggybacking

Including two or more conceptually different types one it
has been using should fail. This caching of data in
the same packet so that all data elements move through multiple routes also
avoids the
network together.

home address

An IP address that is assigned for an extended period of time
to a mobile node. It remains unchanged regardless overhead of where
the node is attached needing to the Internet [14]. If perform a node has more
than one home address, it SHOULD select and use new Route Discovery each
time a single home
address when participating in the ad hoc network.

source route

A source route from a node S to some node D is an ordered list in use breaks.

The operation of home addresses both Route Discovery and interface indexes that contains all the
information that would be needed Route Maintenance in DSR
are designed to forward a packet through

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 3]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

the ad hoc network. For each node that will transmit the
packet, the source route provides the index of the interface
over which the packet should be transmitted, allow uni-directional links and the address of
the node which is intended asymmetric routes
to receive the packet.

DSR Routing Headers be easily supported. In particular, as described noted in Section 7.3 use 2, in
wireless networks, it is possible that a more
compact encoding link between two nodes may
not work equally well in both directions, due to differing antenna
or propagation patterns or sources of the source route interference. DSR allows such
uni-directional links to be used when necessary, improving overall
performance and do not explicitly list
address S network connectivity in the Routing Header`, since it is carried as system.

This document specifies the IP
Source Address operation of the packet.

A source route is described as ``broken'' when the specific
path it describes through the network is not actually viable.

Route Discovery

The method in DSR by which a node S dynamically obtains a
source route to some node D that will be used by S to route protocol for routing
unicast IP packets through the network to D. Performing a Route Discovery
involves sending one or more Route Request packets.

Route Maintenance

The process in DSR multi-hop wireless ad hoc networks. Advanced,
optional features, such as Quality of monitoring the status Service (QoS) support and
efficient multicast routing, are covered in other documents. The
specification of a source route
while DSR in use, so that any link-failures along the source route this document provides a compatible base
on which such features can be detected and added, either independently or by
integration with the broken link removed from use.

4.2. Specification Language 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 [3].

Broch, [4].

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 4] 2]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

5. Protocol Overview

5.1. Route Discovery and Route Maintenance

A source routing protocol must solve two challenges, which DSR terms
Route Discovery and Route Maintenance. Route Discovery is the
mechanism whereby a node S 2 March 2001

2. Assumptions

We assume that all nodes wishing to send a packet to a destination
D obtains a source route to D.

Route Maintenance is the mechanism whereby S is able to detect, while
using a source route to D, if communicate with other nodes
within the ad hoc network topology has changed such
that it can no longer use its route are willing to D because a link along participate fully in the
route no longer works. When Route Maintenance indicates a source
route is broken, S can attempt
protocols of the network. In particular, each node participating in
the network SHOULD also be willing to use any forward packets for other route it happens nodes
in the network.

The diameter of an ad hoc network is the minimum number of hops
necessary for a packet to
know reach from any node located at one extreme
edge of the ad hoc network to D, another node located at the opposite
extreme. We assume that this diameter will often be small (e.g.,
perhaps 5 or can invoke Route Discovery again to find a new route.

To perform Route Discovery, 10 hops), but may often be greater than 1.

Packets may be lost or corrupted in transmission on the source node S link-layer broadcasts wireless
network. We assume that a Route Request packet. Here, node S is termed receiving a corrupted packet can
detect the initiator of error and discard the
Route Discovery, packet.

Nodes within the ad hoc network MAY move at any time without notice,
and MAY even move continuously, but we assume that the node to speed with
which S nodes move is attempting moderate with respect to discover a
source route, say D, is termed the target packet transmission
latency and wireless transmission range of the Discovery.

Each particular underlying
network hardware in use. In particular, DSR can support very
rapid rates of arbitrary node mobility, but we assume that hears nodes do
not continuously move so rapidly as to make the Route Request flooding of every
individual data packet forwards a copy 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
Request, if appropriate, by adding its own address ability
to a source route
being recorded operate the network interface in "promiscuous" receive mode.
This mode causes the Request hardware to deliver every received packet and then rebroadcasting to
the
Route Request.

The forwarding network driver software without filtering based on link-layer
destination address. Although we do not require this facility, some
of Route Requests is constructed so that copies our optimizations can take advantage of its availability. Use
of promiscuous mode does increase the
Request propagate hop-by-hop outward from the node initiating software overhead on the
Route Discovery, until either CPU,
but we believe that wireless network speeds are more the target inherent
limiting factor to performance in current and future systems; we also
believe that portions of the Request is found or
until another node is found that can supply protocol are suitable for implementation
directly within a route programmable network interface unit to avoid this
overhead on the target.

The basic mechanism CPU [13]. Use of forwarding Route Requests forwards the Request
if the node (1) is not promiscuous mode may also increase
the target power consumption of the Request, (2) is not already
listed in network interface hardware, depending
on the recorded source route in this copy design of the Request, receiver hardware, and
(3) has not recently seen another Route Request packet belonging to
this same Route Discovery. A node can determine if it has recently
seen in such a Route Request, since each Route Request packet contains
a unique identifier for this Route Discovery, generated by the
initiator of cases, DSR can
easily be used without the Discovery. Each node maintains an LRU cache of optimizations that depend on promiscuous
receive mode, or can be programmed to only periodically switch the
unique identifier from each recently received Route Request. By not
propagating any copies
interface into promiscuous mode. Use of a Request after the first, the overhead of
forwarding additional copies that reach this node along different
paths promiscuous receive mode is avoided.

In addition, the Time-to-Live field in the IP header
entirely optional.

Wireless communication ability between any pair of the packet
carrying the Route Request MAY be used nodes may at
times not work equally well in both directions, due for example to limit the scope over which
the Request will propagate, using the normal behavior of Time-to-Live
defined by IP [17, 2]. Additional optimizations on the handling and
forwarding
differing antenna or propagation patterns or sources of Route Requests are also used to further reduce the
Route Discovery overhead.

Broch, interference

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 5] 3]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

When 2 March 2001

around the target two nodes [1, 17]. That is, wireless communications
between each pair of nodes will in many cases be able to operate
bi-directionally, but at times the Request (e.g., wireless link between two nodes
may be only uni-directional, allowing one node D) receives the Route
Request, to successfully send
packets to the recorded source route other while no communication is possible in the Request identifies the
sequence of hops
reverse direction. Although many routing protocols operate correctly
only over which this copy of the Request reached D.
Node D copies this recorded source route into a Route Reply packet bi-directional links, DSR can successfully discover and sends this Route Reply back
forward packets over paths that contain uni-directional links.
Some MAC protocols, however, such as MACA [16], MACAW [2], or IEEE
802.11 [10], limit unicast data packet transmission to bi-directional
links, due to the initiator required bi-directional exchange of the Route Request
(e.g., node S).

All source routes learned by a node are kept RTS and CTS
packets in a Route Cache, which
is used these protocols and due to further reduce the cost of Route Discovery. When a node
wishes to send a packet, it examines its own Route Cache and performs
Route Discovery only if no suitable source route is found link-level acknowledgement
feature in its
Cache.

Further, IEEE 802.11; when some intermediate node B receives a Route Request from
S for some target node D, B not equal D, B searches its own Route
Cache for a route to D. If B finds such a route, it might not have
to propagate the Route Request, but instead return a Route Reply to
node S based used on the concatenation top of MAC protocols such as
these, DSR can take advantage of additional optimizations, such as
the recorded easy ability to reverse a source route from
S to B in the Route Request and the cached obtain a route from B back to D. The
details
the origin of replying from a Route Cache in this way are discussed in
Section 9.1.

As a node overhears routes being used by others, either on data
packets or on control packets the original route.

The IP address used by Route Discovery or Route
Maintenance, the a node MAY insert those routes into its Route Cache,
leveraging the Route Discovery operations of the other nodes in using the network. Such route information DSR protocol MAY be learned either assigned
by
promiscuously snooping on packets any mechanism (e.g., static assignment or when forwarding packets.

5.2. Packet Forwarding

To represent a source route within a packet's header, DSR uses a
Routing Header similar to the Routing Header format specified use of DHCP for
IPv6, adapted to dynamic
assignment [8]), although the needs method of DSR and to such assignment is outside
the use scope of DSR in IPv4 (or
in IPv6 in the future). this specification.

Johnson, et al Expires 2 September 2001 [Page 4]

INTERNET-DRAFT The DSR Dynamic Source Routing Header uses a unique Routing
Type field value to distinguish it from the existing Type 0 Routing
Header defined within IPv6 [6].

To forward a packet, a receiving Protocol 2 March 2001

3. DSR Protocol Overview

3.1. Basic DSR Route Discovery

When some source node N simply processes the Routing
Header as specified in Section 8.3 and transmits the packet to
the next hop. If originates a forwarding error occurs along the link new packet addressed to some
destination node, the
next hop in the route, this source node N sends a Route Error back to places in the
originator S header of this the packet informing S that this link is "broken".
If node N's Route Cache contains
a different source route to giving the destination sequence of the original packet, then hops that the packet is salvaged using to
follow on its way to the new destination. Normally, the sender will
obtain a suitable source route (Section 8.5.5). Otherwise, the packet by searching its "Route Cache" of
routes previously learned, but if no route is dropped.

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 6]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

Each node overhearing or forwarding a Route Error packet also
removes from found in its Route Cache the link indicated to be broken, thereby
cleaning the stale cache data from the network.

5.3. Multicast Routing

At this time DSR does not support true multicasting. However, cache, it
does support
will initiate the controlled flooding of Route Discovery protocol to dynamically find a data packet new
route to all nodes in this destination node. In this case, we call the network that are within some number of hops of source
node the originator.
While this mechanism does not support pruning "initiator" and the destination node the "target" of the broadcast
tree
Route Discovery.

For example, suppose a node A is attempting to conserve network resources, it can be used to distribute
information discover a route to nodes
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 network.

When an application on a DSR Route Discovery, node sends a packet to A transmits a multicast
address, DSR piggybacks the data from the packet inside "Route
Request" as a single local broadcast packet, which is received by
(approximately) all nodes currently within wireless transmission
range of A, including node B in this example. Each Route Request packet targeted at
identifies the initiator and target of the multicast address. The normal Route
Request distribution scheme described in Sections 5.1 Discovery, and 8.4.2
will result
also contains a unique request identification (2, in this packet being efficiently distributed to all
nodes in the network within example),
determined by the specified TTL initiator of the originator.
The receiving nodes can then do destination Request. Each Route Request also
contains a record listing the address filtering on of each intermediate node
through which this particular copy of the packet, discarding it if they do not wish to receive multicast
packets destined Route Request has been
forwarded. This route record is initialized to this multicast address.

6. Conceptual Data Structures an empty list by the
initiator of the Route Discovery. In order to participate in this example, the Dynamic Source Routing Protocol, a route record
initially lists only node needs four conceptual data structures: a Route Cache, a A.

When another node receives this Route Request Table, a Send Buffer, and a Retransmission Buffer. These
data structures MAY be implemented in any manner consistent with the
external behavior described (such as node B in this document.

6.1. Route Cache

All routing information needed by a node participating in an ad hoc
network using DSR
example), if it is stored in a Route Cache. Each node in the
network maintains its own target of the Route Cache. The node adds information Discovery, it returns
a "Route Reply" to the Cache as it learns initiator of new links between nodes in the ad hoc
network, for example through packets carrying either a Route Reply or Discovery, giving
a Routing Header. Likewise, copy of the node removes information accumulated route record from the
cache as it learns existing links in the ad hoc network have broken,
for example through packets carrying a Route Error or through Request;
when the
link-layer retransmission mechanism reporting a failure initiator receives this Route Reply, it caches this route
in forwarding
a packet to its next-hop destination. The Route Cache is indexed
logically by destination for use in sending subsequent packets to this
destination.

Otherwise, if this node address, and supports receiving the following
operations:

Broch, Route Request has recently seen
another Route Request message from this initiator bearing this same

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 7] 5]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

void Insert(Route RT)

Inserts information extracted from source 2 March 2001

request identification and target address, or if this node's own
address is already listed in the route RT into record in the Route Cache.

Route Get(Node DEST)

Returns a source route from Request,
this node discards the Request. Otherwise, this node appends its
own address to DEST (if one is
known).

void Delete(Node FROM, Interface INDEX, Node TO)

Removes from the route cache any routes which assume that record in the Route Request and propagates
it by transmitting it as a local broadcast packet transmitted by (with the same
request identification). In this example, node FROM over its interface with B broadcast the
given INDEX will be Route
Request, which is received by node TO.

Each implementation MAY choose the cache replacement C; nodes C and cache search
strategies for 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 that are most appropriate for its
particular network environment. For example, some environments may
choose to return the shortest a route back to a node (the shortest sequence
of hops), while others may select an alternate metric A, and if
found, will use it for the Get()
operation.

The Route Cache SHOULD support storing more than one source route for
each destination.

If there are multiple cached routes to a destination, delivery of the packet
containing the Route Get()
operation Reply. Otherwise, E SHOULD prefer routes that do not traverse a hop with an
interface index of IF_INDEX_MA or IF_INDEX_ROUTER. This will prefer
routes that lead directly to the perform its own
Route Discovery for target node over routes that attempt A, but to reach avoid possible infinite
recursion of Route Discoveries, it MUST piggyback this Route Reply
on the target via any internet infrastructure connected packet containing its own Route Request for A. It is also
possible to the
ad hoc network.

If piggyback other small data packets, such as a node S is using TCP SYN
packet [25], on a source route to some destination D that
includes intermediate node N, S SHOULD shorten Route Request using this same mechanism.

Node E could instead simply reverse the route to
destination D when it learns sequence of a shorter route to node N than hops in the
one route
record that it is listed trying to send in the Route Reply, and use this
as the prefix of its current route to D.

A node S using a source route to destination D through intermediate
node N, MAY shorten on the source packet carrying the Route Reply itself.
For MAC protocols such as IEEE 802.11 that require a bi-directional
frame exchange as part of the MAC protocol [10], this route if reversal
is preferred, as it learns avoids the overhead of a shorter path
from node N possible second
Route Discovery, and it tests the discovered route to node D.

The ensure it is
bi-directional before the Route Cache replacement policy SHOULD allow Discovery initiator begins using the
route. However, this technique will prevent the discovery of routes to be
categorized based upon "preference",
using uni-directional links. In wireless environments where the use
of uni-directional links is permitted, such routes may in some cases
be more efficient than those with a higher
preferences are less likely to only bi-directional links, or they
may be removed from the cache. For
example, a node could prefer routes for which it initiated only way to achieve connectivity to the target node.

When initiating a Route
Discovery over routes that it learned as Discovery, the result sending node saves a copy of promiscuous
snooping on other packets. In particular,
the original packet (that triggered the Discovery) in a node SHOULD prefer
routes that it is presently using over those that it is not.

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 8]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

6.2. Route Request Table local buffer
called the "Send Buffer". The Route Request Table is Send Buffer contains a collection copy of records about Route
Request packets each
packet that were recently originated or forwarded cannot be transmitted by this
node. The table is indexed by the home address of the target of the
route discovery. A record maintained on node S for node D contains
the following:

- The time that S last originated a Route Discovery for D.

- The remaining amount of time that S must wait before the next
attempt at a Route Discovery for D.

- The Time-to-live (TTL) field in the IP header of last Route
Request originated by S for D.

- A FIFO cache of the last ID_FIFO_SIZE Identification values from
Route Request packets targeted at node D that were forwarded by
this node.

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

ID_FIFO_SIZE MUST NOT be set to an unlimited value, since, in the
worst case, when a node crashes and reboots the first ID_FIFO_SIZE
Route Request packets it sends may appear to be duplicates to the
other nodes in the network.

6.3. Send Buffer

The Send Buffer of some node is a queue of packets that cannot be
transmitted by that node because it does not
yet have a source route to each respective the packet's destination. Each packet in
the Send Buffer is stamped logically associated with the time that it is was
placed into the
Buffer, and SHOULD be removed from the Send Buffer and is discarded
SEND_BUFFER_TIMEOUT seconds after initially being placed residing in the
Buffer. If necessary,
Send Buffer for some timeout period; if necessary for preventing the
Send Buffer from overflowing, a FIFO or other replacement strategy SHOULD
MAY also be used to evict packets even before they timeout to prevent expire.

While a packet remains in the buffer from overflowing.

Subject to Send Buffer, the rate limiting defined in Section 8.4, node SHOULD
occasionally initiate a new Route Discovery SHOULD be initiated as often as possible for the packet's
destination address of any packets residing in address. However, the Send Buffer.

6.4. Retransmission Buffer

The Retransmission Buffer of a node is a queue of packets sent by
this node that are awaiting the receipt of an acknowledgment from MUST limit the
next hop in rate at which
such new Route Discoveries for the source route (Section 7.3).

Broch, same address are initiated, since

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 9] 6]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

For each packet in 2 March 2001

it is possible that the Retransmission Buffer, a destination node maintains (1) a
count of is not currently reachable.
In particular, due to the number of retransmissions limited wireless transmission range and (2) the time
movement of the last
retransmission.

Packets are removed from nodes in the buffer when an acknowledgment
is received, or when network, the number network may at times become
partitioned, meaning that there is currently no sequence of retransmissions exceeds
DSR_MAXRXTSHIFT. In the later case, nodes
through which a packet could be forwarded to reach the removal of destination.
Depending on the packet from movement pattern and the Retransmission Buffer SHOULD result density of nodes in the
network, such network partitions may be rare or may be common.

If a new Route Error being
returned to the initial source of the Discovery was initiated for each packet (Section 8.5).

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 10]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

7. Packet Formats

Dynamic Source Routing makes use sent by a
node in such a partitioned network, a large number of four options carrying control
information that can unproductive
Route Request packets would be piggybacked in any existing IP packet.

The mechanism used for these options is based on propagated throughout the design subset of
the
Hop-by-Hop and Destination Options mechanisms in IPv6 [6]. The
ability ad hoc network reachable from this node. In order to generate and process reduce the
overhead from such options must be added to Route Discoveries, a node MUST use an IPv4
protocol stack. Specifically, the Protocol field in exponential
back-off algorithm to limit the IP header
is used rate at which it initiates new Route
Discoveries for the same target. If the node attempts to indicate that a Hop-by-Hop Options or Destination Options
extension header exists between send
additional data packets to this same destination node more frequently
than this limit, the IP header and subsequent packets SHOULD be buffered in the remaining
portion of
Send Buffer until a packet's payload (such as Route Reply is received giving a transport layer header).
The Next Header field in each extension header will then indicate route to this
destination, but the
type of header that follows it in node MUST NOT initiate a packet.

7.1. Destination Options Headers

The Destination Options header 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 used similar to carry optional information
that need be examined only the
mechanism required by Internet nodes to limit the rate at which ARP
Requests are sent for any single target IP address [3].

3.2. Basic DSR Route Maintenance

When originating or forwarding a packet's destination node(s). The
Destination Options header packet using a source route, each
node transmitting the packet is identified responsible for confirming that the
packet has been received by the next hop along the source route; the
packet SHOULD be retransmitted (up to a Next Header (or
Protocol) value maximum number of 60 attempts)
until this confirmation of receipt is received. For example, in the immediately preceding header, and
situation shown below, node A has
the following format:

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next Header | Hdr Ext Len originated a packet for node E
using a source route through intermediate nodes B, C, and D:

+-----+ +-----+ +-----+ +-----+ +-----+
| A |---->| B |---->| C |--x |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
| D |
. .
. Options .
. . | E |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Next Header

8-bit selector. Identifies the type
+-----+ +-----+ +-----+ +-----+ +-----+

In this case, node A is responsible for receipt of header immediately
following the Destination Options header. Uses packet at B,
node B is responsible for receipt at C, node C is responsible for
receipt at D, and node D is responsible for receipt finally at the same values
destination E.

This confirmation of receipt in many cases may be provided at no cost
to DSR, either as the IPv4 Protocol field [20].

Hdr Ext Len

8-bit unsigned integer. Length an existing standard part of the Destination Options
header MAC protocol in 4-octet units, not including
use (such as the link-level acknowledgement frame defined by IEEE
802.11 [10]), or by a "passive acknowledgement" [15] (in which,
for example, B confirms receipt at C by overhearing C transmit the first 8 octets.

Broch,

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 11] 7]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

Options

Variable-length field, 2 March 2001

packet when forwarding it on to D). If neither of length such that these confirmation
mechanisms are available, the complete
Destination Options header is an integer multiple of 4 octets
long. Contains one or more TLV-encoded options.

The following destination option is used node transmitting the packet can
explicitly request a DSR-specific software acknowledgement be
returned by the Dynamic Source
Routing protocol:

- DSR Route Request option (Section 7.1.1)

This destination option MUST NOT appear multiple times within next hop; this software acknowledgement will normally
be transmitted directly to the sending node, but if the link between
these two nodes is uni-directional, this software acknowledgement may
travel over a
single Destination Options header.

7.1.1. DSR Route Request Option

The DSR Route Request destination option different, multi-hop path.

If no receipt confirmation is encoded in
type-length-value (TLV) format 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 | Option Length | Identification |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Target Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|C| IN Index[1] |C| IN Index[2] |C| IN Index[3] |C| IN Index[4] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|C|OUT Index[1] |C|OUT Index[2] |C|OUT Index[3] |C|OUT Index[4] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[2] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[3] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[4] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|C| IN Index[5] |C| IN Index[6] |C| IN Index[7] |C| IN Index[8]|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|C|OUT Index[5] |C|OUT Index[6] |C| OUT Index[7] |C|OUT Index[8]|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[5] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

IP fields:

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 12]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

Source Address

MUST be received after the home address of packet has been
retransmitted the node originating maximum number of attempts by some hop, this packet.
Intermediate nodes that repropagate node
SHOULD return a "Route Error" to the request do original sender of the packet,
identifying the link over which the packet could not change
this field.

Destination Address

MUST be forwarded.
For example, in the limited broadcast address (255.255.255.255).

Hop Limit (TTL)

Can be varied from 1 to 255, for example shown above, if C is unable to implement
expanding-ring searches.

Route Request fields:

Option Type

???. A node that does not understand this option MUST discard deliver
the packet and the Option Data may change en-route (the top
three bits are 011).

Option Length

8-bit unsigned integer. Length of to the option, in octets,
excluding next hop D, then C returns a Route Error to A,
stating that the Option Type and Option Length fields.

Identification link from C to D is currently "broken". Node A unique value generated by
then removes this broken link from its cache; any retransmission of
the initiator (original sender)
of the Route Request. This value allows original packet can be performed by upper layer protocols such
as TCP, if necessary. For sending such a recipient to
determine whether retransmission or not it has recently seen this a copy of other
packets to this Request; 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 has, can send the packet is simply discarded. When
propagating
using the new route immediately. Otherwise, it SHOULD perform a new
Route Request, Discovery for this field MUST be copied from the
received copy of the Request being forwarded.

Target Address

The home address of target (subject to the exponential back-off
described in Section 3.1).

3.3. Additional Route Discovery Features

3.3.1. Caching Overheard Routing Information

A node forwarding or otherwise overhearing any packet MAY add the
routing information from that is packet to its own Route Cache. In
particular, the target of source route used in a data packet, the accumulated
route record in a Route
Request.

Change Interface (C) bit[1..n]

A flag associated with each interface index that indicates
whether Request, or not the corresponding node repropagated route being returned in a
Route Reply MAY all be cached by any node. Routing information from
any of these packets received can be cached, whether the Request
over packet
was addressed to this node, sent to a different physical interface type than over which it broadcast (or multicast)
MAC address, or received while the node's network interface is in
promiscuous mode.

One limitation, however, on caching of such overheard routing
information is the possible presence of uni-directional links in the Request.

Broch,

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 13] 8]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

IN Index[1..n]

IN Index[i] is the index of the interface over which 2 March 2001

ad hoc network (Section 2). For example, in the situation shown
below, node
indicated by Address[i] received the Route Request option.
These are used A is using a source route to record communicate with node E:

+-----+ +-----+ +-----+ +-----+ +-----+
| A |---->| B |---->| C |---->| D |---->| E |
+-----+ +-----+ +-----+ +-----+ +-----+
^
|
+-----+ +-----+ +-----+ +-----+ +-----+
| V |---->| W |---->| X |---->| Y |---->| Z |
+-----+ +-----+ +-----+ +-----+ +-----+

As node C forwards a reverse data packet along the route from the target of
the request A to the originator, over which a Route Reply E, it
MAY be
sent.

OUT Index[1..n]

OUT Index[i] is add to its cache the interface index that presence of the node indicated by
Address[i-1] used when rebroadcasting "forward" direction links
that it learns from the Route Request option.

Address[1..n]

Address[i] is headers of these packets, from itself to D
and from D to E. However, the home address "reverse" direction of the ith hop recorded links
identified in the
Route Request option.

7.2. Hop-by-Hop Options Headers

The Hop-by-Hop Options header is used packet headers, from itself back to carry optional information
that must B and from B
to A, may not work for it since these links might be examined by every uni-directional.
If C knows that the links are in fact bi-directional, for example due
to the MAC protocol in use, it could cache them but otherwise SHOULD
not.

Likewise, node along a packet's delivery path.
The Hop-by-Hop Options header V in the example above is identified by using a Next Header (or
Protocol) value of ??? in different source
route to communicate with node Z. If node C overhears node X
transmitting a data packet to forward it to Y (from V), node C SHOULD
consider whether the IP header, and has links involved can be known to be bi-directional
or not before caching them. If the following
format:

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next Header | Hdr Ext Len | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
| |
. .
. Options .
. .
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Next Header

8-bit selector. Identifies link from X to C (over which this
data packet was received) can be known to be bi-directional, then C
MAY cache the type link from itself to X, the link from X to Y, and the
link from Y to Z. If all links can be assumed to be bi-directional,
C MAY also cache the links from X to W and from W to V. Similar
considerations apply to the routing information that might be learned
from forwarded or otherwise overheard Route Request or Route Reply
packets.

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 header immediately
following the Hop-by-Hop Options header. Uses
Request. If found, the same values
as node generally returns a Route Reply to the IPv4 Protocol field [20].

Hdr Ext Len

8-bit unsigned integer. Length
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 Hop-by-Hop Options
header 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 4-octet units, not including this way, a node MUST
verify that the first 8 octets.

Broch, resulting route being returned in the Route Reply,

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 14] 9]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

Options

Variable-length field, of length such that 2 March 2001

after this concatenation, contains no duplicate nodes listed in the complete
Hop-by-Hop Options header is an integer multiple of 4 octets
long. Contains one or more TLV-encoded options.

The following hop-by-hop options are used by
route record. For example, the Dynamic Source
Routing protocol:

- DSR Route Reply option (Section 7.2.1)

- DSR Route Error option (Section 7.2.2)

- DSR Acknowledgment option (Section 7.2.3)

All of these destination options MAY appear one or more times within figure below illustrates a case in
which a single Hop-by-Hop Options header.

7.2.1. DSR Route Reply Option

The DSR Route Reply hop-by-hop option is encoded Request for target E has been received by node F, and
node F already has in type-length-value
(TLV) format 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 | Option Length | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Target Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|C|OUT Index[1] |C|OUT Index[2] |C|OUT Index[3] |C|OUT Index[4] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[2] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[3] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[4] its Route Cache a route from itself to E:

+-----+ +-----+ +-----+ +-----+
|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|C|OUT Index[5] |C|OUT Index[6] |C|OUT Index[7] |C|OUT Index[8] A |---->| B |- >| D |---->| E |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+-----+ +-----+ \ / +-----+ +-----+
\ /
\ +-----+ /
>| C |-
+-----+
| Address[5] ^
v |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Route Request +-----+
Route: A - B - C - F | ... F |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 15]

INTERNET-DRAFT Cache: C - D - E
+-----+

The Dynamic Source Routing Protocol 22 October 1999

Option Type

???. A node that does not understand this option should ignore
this option and continue processing the packet, and the Option
Data does not change en-route (the top three bits are 000).

Option Length

8-bit unsigned integer. Length concatenation of the option, in octets,
excluding accumulated route record from the Option Type Route
Request and Option Length fields.

Reserved

Sent as 0; ignored on reception.

Target Address

The home address of the cached route from F's Route Cache would include a
duplicate node in passing from C to which F and back to C.

Node F in this case could attempt to edit the Route Reply must be
delivered.

Change Interface (C) bit[1..n]

If route to eliminate the C bit associated with
duplication, resulting in a route from A to B to C to D and on to E,
but in this case, node N is set, it implies N will F would not be forwarding on the packet out route that it returned
in its own Route Reply. DSR Route Discovery prohibits node F from
returning such a different interface than Route Reply from its cache for two reasons. First,
this limitation increases the one
over which it was received (i.e., probability that the resulting route
is valid, since node sending the packet
to N F in this case should not expect have received a passive acknowledgment).

OUT Index[1..n]

OUT Index[i] is Route
Error if the interface index of route had previously stopped working. Second, this
limitation means that a Route Error traversing the ith hop listed in route is very
likely to pass through any node that sent the Route Reply option. It denotes for the interface
route (including node F), which helps to ensure that should 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 used contaminated by Address[i-1] to reach Address[i] when using
a Route Reply from F containing the
specified source same stale route.

Address[1..n]

Address[i] is If the home address of Route
Request does not meet these restrictions, the ith hop listed node (node F in this
example) discards the Route Request rather than replying to it or
propagating it.

3.3.3. Preventing Route Reply option.

Broch, Johnson, and Maltz Expires 22 April 2000 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

Johnson, et al Expires 2 September 2001 [Page 16] 10]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

7.2.2. DSR Route Error Option

The DSR Route Error hop-by-hop option is encoded in type-length-value
(TLV) format 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ March 2001

bandwidth and possibly increasing the number of network collisions in
the area.

For example, the figure below shows a situation in which nodes B, C,
D, E, and F all receive A's Route Request for target G, and each has
the indicated route cached for this target:

+-----+ +-----+
| Option Type D |< >| C | Option Length
+-----+ \ / +-----+
Cache: C - B - G \ / Cache: B - G
\ +-----+ /
-| A |-
+-----+\ +-----+ +-----+
| Index | Error Type \--->| B |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Error Source Address G |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
/ \ +-----+ +-----+
/ \ Cache: G
v v
+-----+ +-----+
| Error Destination Address E |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Unreachable Node Address F |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Option Type

???. A node that does not understand this option should ignore
the option
+-----+ +-----+
Cache: F - B - G Cache: B - G

Normally, these nodes would all attempt to reply from their own
Route Caches, and continue processing would all send their Route Replies at about the packet, and
same time, since they all received the Option
Data does not change en-route (the top three bits are 000).

Option Length

8-bit unsigned integer. Length of broadcast Route Request at
about the option, in octets,
excluding same time. Such simultaneous replies from different nodes
all receiving the Option Type and Option Length fields.

Index

The interface index Route Request may create packet collisions among
some or all of these Replies and may cause local congestion in the network interface over which
wireless network. In addition, it will often be the case that the
different replies will indicate routes of different lengths, as shown
in this example.

If a node designated by Error Source Address tried to forward can put its network interface into promiscuous receive
mode, it SHOULD delay sending its own Route Reply for a
packet short period,
while listening to see if the initiating node designated by Unreachable Node Address.

Error Type

The type of error encountered. Values between 0 and 127
inclusive indicate begins using a hard failure of connectivity between the
Error Source Address and the Unreachable Node Address. Values
between 128 and 255 inclusive indicate shorter
route first. That is, this node SHOULD delay sending its own Route
Reply for a soft failure.

NODE_UNREACHABLE random period

d = H * (h - 1

PATH_STATE_NOT_FOUND 129

Error Source Address

The home address of the node originating + r)

where h is the Route Error (e.g., length in number of network hops for the node that attempted route to forward be
returned in this node's Route Reply, r is a packet random floating point
number between 0 and discovered the
link failure).

Broch, Johnson, 1, and Maltz Expires 22 April 2000 [Page 17]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

Error Destination Address

The home address of H is a small constant delay (at least
twice the node maximum wireless link propagation delay) to which the Route Error must be
delivered (e.g, introduced
per hop. This delay effectively randomizes the time at which each
node that generated 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 2 September 2001 [Page 11]

INTERNET-DRAFT The Dynamic Source Routing Protocol 2 March 2001

Within the routing information
claiming that delay period, this node promiscuously receives all
packets, looking for data packets from the hop Error Source Address to Unreachable Node
Address was initiator of this Route
Discovery destined for the target of the Discovery. If such a valid hop).

Unreachable Node Address

The home address 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 was found to may be unreachable
(the next hop neighbor used
to which limit the node at ``Error Source
Address'' was attempting number of intermediate nodes allowed to transmit forward that
copy of the packet).

7.2.3. DSR Acknowledgment Option

The DSR Acknowledgment hop-by-hop option Route Request. This hop limit is encoded implemented using the
Time-to-Live (TTL) field in
type-length-value (TLV) format 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 | Option Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Identification |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ACK Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ACK Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Data Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Option Type

???. A node that does not understand this option should ignore
the option and continue processing the packet, and the Option
Data does not change en-route (the top three bits are 000).

Option Length

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

Identification

A 32-bit value that when taken in conjunction with Data Source
Address, uniquely identifies Route Request. As the packet being acknowledged.

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 18]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

The Identification value Request is computed as ((ip_id << 16) | ip_off)
where ip_id forwarded, this limit is
decremented, and the value of the 16-bit Identification field in
the IP header of the Request packet being acknowledged, and ip_off is discarded if the value of the 13-bit Fragment Offset field in the IP header
of the packet being acknowledged.

When constructing limit reaches
zero before finding the Identification, ip_id and ip_off MUST be
in host byte-order. The entire Identification value MUST then target.

This Route Request hop limit can be converted used to network byte-order before being placed in the
Acknowledgment option.

ACK Source Address

The home address implement a variety of
algorithms for controlling the spread of a Route Request during a
Route Discovery attempt. For example, a node originating the Acknowledgment.

ACK Destination Address

The home address MAY send its first
Route Request attempt for some target node using a hop limit of the 1,
such that any node to which receiving the Acknowledgment must
be delivered.

Data Source Address

The IP Source Address initial transmission of the packet being acknowledged.

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 19]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

7.3. DSR Routing Header

As specified for IPv6 [6], a Routing header is used by a source to
list one or more intermediate nodes to be ``visited'' on Route
Request will not forward the way Request to
a packet's destination. other nodes by rebroadcasting
it. This function form of Route Request is similar to IPv4's Loose
Source and Record called a "non-propagating"
Route option, but Request. It provides an inexpensive method for determining
if the Routing header does not
record target is currently a neighbor of the initiator or if a
neighbor node has a route taken to the target cached (effectively using the
neighbors' Route Caches as an extension of the packet initiator's own Route
Cache). If no Route Reply is received after a short timeout, then a
"propagating" Route Request (i.e., with no hop limit) MAY be sent.

Another possible use of the hop limit in a Route Request is forwarded. The specific
processing steps required to
implement an "expanding ring" search for the Routing header must be
added to target [13]. For
example, a node could send an IPv4 protocol stack. The Routing header initial non-propagating Route Request
as described above; if no Route Reply is identified by received for it, the node
could initiate another Route Request with a Next Header value hop limit of 43 in 2. For
each Route Request initiated, if no Route Reply is received for it,
the immediately preceding header, and
has node could double the following format:

The type specific data hop limit used on the previous attempt,
to progressively explore for a Routing Header carrying a DSR Source the target node without allowing the
Route is:

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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|R|S| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|C|OUT Index[1] |C|OUT Index[2] |C|OUT Index[3] |C|OUT Index[4] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[2] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[3] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[4] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|C|OUT Index[5] |C|OUT Index[6] |C|OUT Index[7] |C|OUT Index[8] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[5] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Broch, Johnson, Request to propagate over the entire network. However, this
expanding ring search approach could have the effect of increasing
the average latency of Route Discovery, since multiple Discovery
attempts and Maltz timeouts may be needed before discovering a route to the
target node.

Johnson, et al Expires 22 April 2000 2 September 2001 [Page 20] 12]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

Routing Header Fields:

Next Header

8-bit selector. Identifies the type 2 March 2001

3.4. Additional Route Maintenance Features

3.4.1. Packet Salvaging

After sending a Route Error message as part of header immediately
following Route Maintenance
as described in Section 3.2, a node MAY attempt to "salvage" the Routing header.

Hdr Ext Len

8-bit unsigned integer. Length of
data packet that caused the Routing header in
4-octet units, not including Route Error rather than discarding the first 8 octets.

Routing Type

???

Segments Left

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

Type Specific Fields:

Acknowledgment Request (R)

The Acknowledgment Request (R) bit is set node sending a Route
Error searches its own Route Cache for a route from itself to request an
explicit acknowledgment from the next hop. After processing
the Routing Header, The IP Destination Address lists the
address
destination of the next hop.

Salvaged Packet (S)

The Salvaged Packet (S) bit indicates that this packet has been
salvaged by an intermediate node, and thus that this Routing
Header was generated by Address[1] and not causing the IP Source
Address (Section 8.5.5).

Reserved

Sent as 0; ignored on reception.

Change Interface (C) bit[1..n] Error. If the C bit associated with such a node N route is set, it implies N will
be forwarding
found, the node MAY salvage the packet out a different interface than after returning the one
over which it was received (i.e., Route
Error by replacing the node sending original source route on the packet
to N should not expect a passive acknowledgment and MAY wish to
set with the R bit).

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 21]

INTERNET-DRAFT
route from its Route Cache. The Dynamic Source Routing Protocol 22 October 1999

OUT Index[1..n]

Index[i] is the interface index that the node indicated
by Address[i-1] must use when transmitting then forwards the packet to
Address[i]. Index[1] indicates which interface the
next node indicated by the IP Source Address uses to transmit the packet.

Address[1..n]

Address[i] is the home address of along this source route. For example, in the ith hop
situation shown in the Routing
header.

Note that Address[1] is example of Section 3.2, if node C has another
route cached to node E, it can salvage the first intermediate hop along packet by replacing the route.
The address of
original route in the originating node is packet with this new route from its own Route
Cache, rather than discarding the IP Source Address. The
only exception to packet.

When salvaging a packet in this rule way, a count is for packets that are salvaged, as
described maintained in Section 8.5.5. A the
packet of the number of times that it has been salvaged has an
alternate salvaged, to prevent a
single packet from being salvaged endlessly. Otherwise, it could be
possible for the packet to enter a routing loop, as different nodes
repeatedly salvage the packet and replace the source route placed on it by an the
packet with routes to each other.

3.4.2. Automatic Route Shortening

Source routes in use MAY be automatically shortened if one or more
intermediate node hops in the network,
and route become no longer necessary. This
mechanism of automatically shortening routes in this case, use is somewhat
similar to the address use of the originating passive acknowledgements [15]. In particular,
if a node (the salvaging
node) is Address[1]. Salvaged packets are indicated able to overhear a packet carrying a source route (e.g.,
by setting operating its network interface in promiscuous receive mode), then
this node examines the S
bit unused portion of that source route. If this
node is not the intended next hop for the packet but is named in
the DSR Routing header.

Broch, later unused portion of the packet's source route, then it can
infer that the intermediate nodes before itself in the source route
are no longer needed in the route. For example, the figure below

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 22] 13]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

8. Detailed Operation

8.1. Originating a Data Packet

When 2 March 2001

illustrates an example in which node A originates a packet, the following steps MUST be taken
before transmitting the packet:

1. If the destination address is D has overheard a multicast address, piggyback the data packet on
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) returns a "gratuitous" Route Request targeting Reply
to the multicast address. original sender of the packet (node A). The following fields MUST be initialized Route Reply
gives the shorter route as specified:

IP.Source_Address = Home address the concatenation of node A
IP.Destination_Address = 255.255.255.255
Request.Target_Address = Multicast destination address

DONE.

2. Otherwise, call Route_Cache.Get() to determine if there is a
cached source route to the destination.

3. If portion of the cached
original source route indicates that up through the destination is directly
reachable over one hop, no Routing Header should be added to node that transmitted the
packet. Initialize
overheard packet (node B), plus the following fields:

IP.Source_Address = Home address of node A
IP.Destination_Address = Home address suffix of the Destination

DONE.

4. Otherwise, if the cached original source
route indicates that multiple hops are
required to reach beginning with the destination, insert a Routing Header into node returning the gratuitous Route Reply
(node D). In this example, the packet as described in Section 8.2. DONE.

5. Otherwise, if no cached route to returned in the destination is found, insert gratuitous Route
Reply message sent from D to A gives the packet into new route as the Send Buffer and initiate sequence of
hops from A to B to D to E.

3.4.3. Increased Spreading of Route Discovery as
described in Section 8.4.

8.2. Originating a Packet with a DSR Routing Header Error Messages

When a source node originates receives a packet with Route Error for a Routing Header, 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 address caches of nodes around this source node will
not generate Route Replies that contain the first hop in the same invalid link for
which this source route MUST be listed as node received the IP
Destination Address as well as Address[1] Route Error.

For example, in the Routing Header.
The final destination of the packet is listed as the last hop situation shown in the Routing Header (Address[n]). At each intermediate hop i,
Address[i] is copied into example of Section 3.2,
node A learns from the IP Destination Address Route Error message from C, that the link
from C to 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 Route Request
packet
is retransmitted.

Broch, Johnson, initiating this Route Discovery, node A piggybacks a copy
of this Route Error, ensuring that the Route Error spreads well to
other nodes, and Maltz guaranteeing that any Route Reply that it receives
(including those from other node's Route Caches) in response to this
Route Request does not contain a route that assumes the existence of
this broken link.

Johnson, et al Expires 22 April 2000 2 September 2001 [Page 23] 14]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

For example, suppose node A originates a packet destined for node D
that should pass through intermediate hops B and C. The packet MUST
be initialized as follows:

IP.Source_Address = Home address 2 March 2001

4. Conceptual Data Structures

This document describes the operation of node A
IP.Destination_Address = Home address the DSR protocol in terms
of node B
RT.Segments_Left = 2
RT.Out_Index[1] = Interface index used by A to reach B
RT.Out_Index[2] = Interface index used by B to reach C
RT.Out_Index[3] = Interface index used by C to reach D
RT.Address[1] = Home address a number of node B
RT.Address[2] = Home address conceptual data structures. This section describes
each of node C
RT.Address[3] = Home address these data structures and provides an overview of node D

8.3. Processing a Routing Header

Excluding the exceptions listed here, a DSR Routing Header is
processed using its use
in the same rules as outlined for Type 0 Routing Headers protocol. In an implementation of the protocol, these data
structures MAY be implemented in IPv6 [6]. The Routing Header is only processed any manner consistent with the
external behavior described in this document.

4.1. Route Cache

All routing information needed by a node participating in an ad hoc
network using DSR is stored in that node's Route Cache. Each node in
the network maintains its own Route Cache. A node whose
address appears adds information
to its Route Cache as the IP destination it learns of new links between nodes in the packet. The following
additional rules apply to processing the type specific data of
ad hoc network; for example, a DSR
Source Route:

Let

SegLft = the value node may learn of Segments Left new links when the it
receives a packet was received
NumAddrs = the total number of addresses in the carrying either a Route Reply or a DSR Routing Header

1. The address of the next hop, Address[NumAddrs - SegLft + 1],
is copied into the IP.Destination_Address of the packet. The
header. Likewise, a node removes information from its Route Cache as
it learns that existing IP.Destination_Address is NOT copied back into links in the
Address list ad hoc network have broken; for
example, a node may learn of a broken link when it receives a packet
carrying a Route Error or through the Routing Header.

2. The interface used to transmit the link-layer retransmission
mechanism reporting a failure in forwarding a packet to its next hop from
this node MUST be the interface denoted by Index[NumAddrs -
SegLft + 1].

3. If the Acknowledgment Request (R) bit next-hop
destination.

It is set, the node MUST
transmit possible to interface a packet containing the DSR Acknowledgment option network with other networks,
external to this DSR network. Such external networks may, for
example, be the previous hop, Address[NumAddrs - SegLft - 1], performing
Route Discovery if necessary. (Address[0] is taken as the
IP.Source_Address)

4. Perform Route Maintenance by verifying Internet, or may be other ad hoc networks routed
with a routing protocol other than DSR. Such external networks may
also be other DSR networks that the packet was
received by the next hop are treated as described external networks
in Section 8.5.

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 24]

INTERNET-DRAFT order to improve scalability. The Dynamic Source Routing Protocol 22 October 1999

8.4. Route Discovery

Route Discovery complete handling of such
external networks is beyond the on-demand process by which nodes actively
obtain source routes scope of this document. However,
this document specifies a minimal set of requirements and features
necessary to destinations allow nodes only implementing this specification to which they are actively
attempting
interoperate correctly with nodes implementing interfaces to send packets. The destination node for which a
Route Discovery is initiated is known as the "target" such
external networks. This minimal set of requirements and features
involve the First Hop External (F) and Last Hop External (L)
bits in a Source Route
Discovery. A option (Section 5.7) and a Route Discovery for Reply
option (Section 5.3) in a destination SHOULD NOT be
initiated unless packet's DSR header (Section 5). These
requirements also include the initiating addition of an External flag bit
tagging each node has a packet in the Send Buffer
requiring delivery to that destination. A Route Discovery for a
given target node MUST NOT be initiated unless permitted by Cache, copied from the
rate-limiting information contained First Hop
External (F) and Last Hop External (L) bits in the Source Route Request Table.
After each
option or Route Discovery attempt, Reply option from which the interval between successive
Route Discoveries for link to this target must be doubled, up to a maximum of
MAX_REQUEST_PERIOD. node was
learned.

The Route Discoveries for a multicast address SHOULD NOT be rate limited,
and Cache SHOULD always be permitted.

8.4.1. Originating a Route Request

The basic support storing more than one route to each
destination. In searching the Route Discovery algorithm Cache for a unicast route to some
destination is as
follows:

1. Originate a Route Request packet with node, the IP header Time-to-Live
field initialized to 1. This type of Route Request Cache is called indexed by destination node
address. The following properties describe this searching function
on a
non-propagating Route Request and allows the originator of the
Request to inexpensively query the route caches of each Cache:

Johnson, et al Expires 2 September 2001 [Page 15]

INTERNET-DRAFT The Dynamic Source Routing Protocol 2 March 2001

- Each implementation of its
neighbors DSR at any node MAY choose any appropriate
strategy and algorithm for searching its Route Cache and
selecting a "best" route to the destination.

2. If destination from among those
found. For example, a Route Reply is received in response node MAY choose to select the non-propagating
Request, use the returned source shortest
route to transmit all packets
for the destination that are in (the shortest sequence of hops), or it
MAY use an alternate metric to select the Send Buffer. DONE.

3. Otherwise, if no Route Reply is received within
RING0_REQUEST_TIMEOUT seconds, transmit a Route Request
with route from the IP header Time-to-Live field initialized Cache.

- However, if there are multiple cached routes to
MAX_ROUTE_LEN. This type of Route Request is called a propagating
Route Request. Update destination,
the information in selection of routes when searching the Route Request
Table, to double Cache SHOULD
prefer routes that do not have the amount of time before External flag set on any subsequent Route
Discovery attempt node.
This preference will select routes that lead directly to this target.

4. If no Route Reply is received within the time interval indicated
by
target node over routes that attempt to reach the Route Request Table, GOTO step 1.

The Route Request option SHOULD be initialized as follows:

IP.Source_Address = This node's home address
IP.Destination_Address = 255.255.255.255
Request.Target = Home address of intended destination

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 25]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

Request.OUT_Index[1] = Index of interface used target via any
external networks connected to transmit the Request

The behavior of a node processing a packet containing both a Routing
Header and a DSR ad hoc network.

- In addition, any route selected when searching the Route Request Destination option is unspecified.
Packets SHOULD Cache
MUST NOT contain both a Routing Header and a Route Request
Destination option. [This is not exactly true: A Route Request
option appearing in the second Destination Options header that IPv6
allows after the Routing Header would probably do-what-you-mean,
though we have not triple-checked it yet. Namely, it would allow the
originator of a route discovery to unicast the request to some External bit set for any nodes other than
possibly the first node, where it would the last node, or both; the External bit
MUST NOT be released and begin set for any intermediate hops in the flood fill. We call
this route selected.

An implementation of a Route Request Blossom since Cache MAY provide a fixed capacity
for the unicast portion of cache, or the path
looks like a stem on cache size MAY be variable. The following
properties describe the blossoming flood-fill management of the request.]

Packets containing available space within a node's
Route Request Destination option SHOULD NOT be
retransmitted, SHOULD NOT request an explicit Cache:

- Each implementation of DSR Acknowledgment by
setting at each node MAY choose any
appropriate policy for managing the R bit, SHOULD NOT expect a passive acknowledgment, and
SHOULD NOT be placed entries in the Retransmission Buffer. The repeated
transmission of packets containing a its Route Request Destination option
is controlled solely by the logic described in this section.

8.4.2. Processing Cache,
such as when limited cache capacity requires a Route Request Option

When choice of which
entries to retain in the Cache. For example, a node A receives a packet containing MAY chose a Route Request option,
"least recently used" (LRU) cache replacement policy, in which
the Route Request option entry last used longest ago is processed as follows:

1. If Request.Target_Address matches the home address of this node,
then discarded from the Route Request option contains cache if a complete source route
describing the path from
decision needs to be made to allow space in the initiator of cache for some
new entry being added.

- However, the Route Request Cache replacement policy SHOULD allow routes
to
this node.

(a) Send be categorized based upon "preference", where routes with a
higher preferences are less likely to be removed from the cache.
For example, a node could prefer routes for which it initiated
a Route Reply Discovery over routes that it learned as described in Section 8.4.4.

(b) Continue processing the packet in accordance result of
promiscuous snooping on other packets. In particular, a node
SHOULD prefer routes that it is presently using over those that
it is not.

Any suitable data structure organization, consistent with this
specification, MAY be used to implement the Next
Header value contained Route Cache in any node.
For example, the Destination Option extension
header. DONE.

2. Otherwise, if following two types of organization are possible:

- In DSR, the combination (IP.Source_Address,
Request.Identification) is found route returned in the each Route Request
Table, then discard the packet, since this Reply that is a copy received
by the initiator of a
recently seen Route Request. DONE.

3. Otherwise, if Request.Target_Address is a multicast address then:

(a) If node A Discovery (or that is a member of the multicast group indicated by
Request.Target_Address, then create a copy of the packet,
setting IP.Destination_Address = REQUEST.Target_Address, and
continue processing learned from
the copy header of the packet overhead packets, as described in accordance with
the Next Header field Section 6.1.4)
represents a complete path (a sequence of links) leading to the Destination option.

Broch,

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 26] 16]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

(b) If IP.TTL is non-zero, decrement IP.TTL, and retransmit the
packet. DONE.

4. Otherwise, if the home address 2 March 2001

destination node. By caching each of node these paths separately,
a "path cache" organization for the Route Cache can be formed.
A path cache is already listed in
the very simple to implement and easily guarantees
that all routes are loop-free, since each individual route from
a Route Request (IP.Source_Address Reply or Request.Address[]), then
discard the packet. DONE.

5. Let

m = number of addresses currently in the Route Request option
n = m + 1

6. Otherwise, append or used in a packet is loop-free.
To search for a route in a path cache data structure, the home address of sending
node A to the can simply search its Route Request
option (Request.Address[n]).

7. Set Request.IN_Index[n] = index Cache for any path (or prefix of interface packet was received
on.

8. If
a source route path) that leads to Request.Target_Address is found in our the intended destination node.

This type of organization for the Route Cache in DSR has
been extensively studied through simulation [5, 11, 18] and the rules
through implementation of Section 8.4.3 permit it, return DSR in a Cached mobile outdoor testbed under
significant workload [19, 20, 20].

- Alternatively, a "link cache" organization could be used for the
Route Reply as described Cache, in Section 8.4.3. DONE.

9. Otherwise, for each interface on which each individual link (hop) in the node routes
returned in Route Reply packets (or otherwise learned from the
header of overhead packets) is configured added to
participate in a DSR ad hoc network:

(a) Make a copy unified graph data
structure of the packet containing the Route Request.

(b) Set Request.OUT_Index[n+1] = index this node's current view of the interface.

(c) If the outgoing interface is different from network topology.
To search for a route in link cache, the incoming
interface, then set sending node must use
a more complex graph search algorithm, such as the C bit on both Request.OUT_Index[n+1]
and Request.IN_Index[n]

(d) Link-layer re-broadcast well-known
Dijkstra's shortest-path algorithm, to find the packet containing current best path
through the Route
Request on graph to the interface jittered by T milliseconds, where
T destination node. Such an algorithm is a uniformly distributed, random number between 0
more difficult to implement and
BROADCAST_JITTER. DONE.

8.4.3. Generating Route Replies using the Route Cache

A node SHOULD use its Route Cache may require significantly more
CPU time to avoid propagating a Route
Request packet received from another node. In particular, suppose a
node receives execute.

However, a Route Request packet for which it link cache organization is not more powerful than a
path cache organization, in its ability to effectively utilize
all of the target
and which it does not discard based on potential information that a node might learn about
the logic state of Section 8.4.2.
If the node has a network: links learned from different Route Cache entry for
Discoveries or from the target header of the Request,
it SHOULD append this cached route any overheard packets can be
merged together to the accumulated route record form new routes in the packet and return network, but this route
is not possible in a Route Reply packet path cache due to

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 27]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999 the initiator without propagating (re-broadcasting) separation of each
individual path in the Route
Request. Thus, cache.

This type of organization for example, if node F in the example network shown Route Cache in Figure 8.4.3 needs to send a packet to node D, it will initiate DSR, including
the effect of a range of implementation choices, has been studied
through detailed simulation [9].

The choice of data structure organization to use for the Route Discovery and broadcast Cache
in any DSR implementation is a local matter for each node and affects
only performance; any reasonable choice of organization for the Route
Cache does not affect either correctness or interoperability.

4.2. Route Request packet. If Table

The Route Request Table records information about Route Requests that
have been recently originated or forwarded by this
broadcast node. The table
is received indexed by IP address.

Johnson, et al Expires 2 September 2001 [Page 17]

INTERNET-DRAFT The Dynamic Source Routing Protocol 2 March 2001

The Route Request Table on a node A, records the following information
about nodes to which this node A can simply return has initiated a Route
Reply packet to F containing the complete route to D consisting of
the sequence of hops: A, B, C, and D.

Before transmitting Request:

- The time that this node last originated a Route Reply packet Request for that was generated using
information from its
target node.

- The number of consecutive Route Cache, Requests initiated for this
target since receiving a valid Route Reply giving a node MUST verify that:

1. The resulting route contains no loops.

2. to that
target node.

- The remaining amount of time before which this node issuing the MAY next
attempt at a Route Reply is listed in the route Discovery for that it
specifies target node.

- The Time-to-Live (TTL) field used in its Reply. This increases the probability IP header of last Route
Request initiated by this node for that target node.

In addition, the
route is valid, since Route Request Table on a node also records the
following information about initiator nodes from which this node in question should have has
received a Route Error if this route stopped working. Additionally, this
requirement means that a Route Error traversing the route will
pass through the node that issued the Reply based on stale Request:

- A FIFO cache
data, which is critical for ensuring stale data is removed from
caches in a timely manner. Without this requirement, the next
Route Discovery initiated by of size REQUEST_TABLE_IDS entries containing the original requester might also be
contaminated by a Route Reply
Identification value and target address from this node containing the same
stale route.

8.4.4. Originating a most recent
Route Reply

Let REQPacket denote a packet Requests received by this node A from that
contains a Route Request option which lists node A as initiator node.

Nodes SHOULD use an LRU policy to manage the
REQPacket.Request.Target_Address. Let REPPacket be a packet
transmitted by node A that contains a corresponding entries in their Route Reply.
Request Table.

The
Route Reply option transmitted in response number of Identification values to a retain in each Route Request
Table entry, REQUEST_TABLE_IDS, MUST NOT be
initialized as follows:

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

+---+
| F | +---+
+---+ | E |
+---+

Figure 1: An example network where A knows unlimited, since,
in the worst case, when a
route to D via B and C.

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 28]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

1. If REQPacket.Request.Address[] does not contain any hops, then node A is only a single hop from the originator of crashes and reboots, the first
REQUEST_TABLE_IDS Route
Request. Build Discoveries it initiates after rebooting
could appear to be duplicates to the other nodes in the network.
In addition, a Route Reply packet as follows:

REPPacket.IP.Source_Address = REQPacket.Request.Target_Address
REPPacket.Reply.Target = REQPacket.IP.Source_Address
REPPacket.Reply.OUT_Index[1] = REQPacket.Request.OUT_index[1]
REPPacket.Reply.OUT_C_bit[1] = REQPacket.Request.OUT_C_bit[1]
REPPacket.Reply.Address[1] = The home address of node A

GOTO step 3.

2. Otherwise, build a SHOULD base its initial Identification value,
used for Route Reply packet as follows:

REPPacket.IP.Source_Address = The home address of node A
REPPacket.Reply.Target = REQPacket.IP.Source_Address
REPPacket.Reply.OUT_Index[1..n]= REQPacket.Request.OUT_index[1..n]
REPPacket.Reply.OUT_C_bit[1..n]= REQPacket.Request.OUT_C_bit[1..n]
REPPacket.Reply.Address[1..n] = REQPacket.Request.Address[1..n]

3. Send the Route Reply jittered by T milliseconds, where T
is a uniformly distributed random number between 0 and
BROADCAST_JITTER. DONE.

If sending a Route Reply packet to the originator of the Route
Request requires performing a Route Discovery, the Route Reply
hop-by-hop option MUST be piggybacked Discoveries after rebooting, on the packet that contains the
Route Request. This prevents a loop wherein the target of the new
Route Request (which was itself the originator of the original Route
Request) must do another Route Request battery backed-up
clock or other persistent memory device, in order to return its Route
Reply.

If sending the Route Reply to the originator help avoid any
possible such delay in successfully discovering new routes after
rebooting; if no such source of the Route Request
does not require performing Route Discovery, initial Identification value is
available, a node SHOULD send a
unicast Route Reply in response to every Route Request targeted at
it.

8.4.5. Processing base its initial Identification value after
rebooting on a Route Reply Option

Upon receipt random number.

4.3. Send Buffer

The Send Buffer of a Route Reply, node implementing DSR is a queue of packets that
cannot be sent by that node should extract the because it does not yet have a source
route
(Target_Address, OUT_Index[1]:Address[1], .. OUT_Index[n]:Address[n]
) and insert this route into its Route Cache. All the packets to 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 checked to see whether removed from the information Send Buffer and silently
discarded SEND_BUFFER_TIMEOUT seconds after initially being placed in the
Reply allows them to be sent immediately.

Broch,

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 29] 18]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

8.5. Route Maintenance

Route Maintenance requires that whenever a node transmits a data
packet, a Route Reply, or a Route Error, it must verify that the next
hop (indicated by the Destination IP Address) correctly receives 2 March 2001

the
packet. Buffer. If necessary, a FIFO strategy SHOULD be used to evict
packets before they timeout to prevent the sender cannot verify that the next hop received the packet, it
MUST decide that its link buffer from overflowing.

Subject to the next hop is broken and MUST send rate limiting defined in Section 6.2, a Route Error to the node responsible
Discovery SHOULD be initiated as often as possible for generating the Routing Header
that contains the broken link (Section 8.5.3).

The following ways may be used to verify that
destination address of any packets residing in the next hop correctly
received a packet:

- Send Buffer.

4.4. Retransmission Buffer

The receipt Retransmission Buffer of a passive acknowledgment (Section 8.5.1).

- The node implementing DSR is a queue
of packets sent by this node that are awaiting the receipt of an explicitly requested
acknowledgment from the next hop in the source route (Section 8.5.1).

- By 5.7).
For each packet in the presence Retransmission Buffer, a node maintains (1) a
count of the number of retransmissions and (2) the time of positive feedback the last
retransmission.

Packets are removed from the link layer
indicating that Retransmission Buffer when an
acknowledgment is received or when the packet was acknowledged by number of retransmissions
exceeds DSR_MAXRXTSHIFT. In the next hop
(Section 8.5.2).

- By later case, the absence removal of explicit failure notification the
packet from the link
layer that provides reliable hop-by-hop delivery such as MACAW or
802.11 (Section 8.5.2).

Nodes MUST NOT perform Route Maintenance for packets containing Retransmission Buffer SHOULD result in a Route Request option or packets containing only an Acknowledgment
option. Sending Acknowledgments for packets containing only
an Acknowledgment option would create an infinite loop whereby
acknowledgments would be sent for acknowledgments. Acknowledgments
should be always sent for packets containing a Routing Header with
the R bit set (e.g., packets which contain only an Acknowledgment
and a Routing Header for which Error
being returned to the last forwarding hop requires an
explicit acknowledgment original source of receipt by the final destination).

8.5.1. Using Network-Layer Acknowledgments

For link layers that do not provide explicit failure notification,
the following steps SHOULD be used by a node A to perform Route
Maintenance.

When receiving a packet:

- If the packet contains a Routing Header with the R bit set, send
an explicit acknowledgment as described in Section 8.3.

Broch, (Section 6.3).

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 30] 19]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

- If the packet does not contain a 2 March 2001

5. DSR Header Format

The Dynamic Source Routing Header, the node MUST
transmit protocol makes use of a special header
carrying control information that can be included in any existing IP
packet. This DSR header in a packet containing 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 of DSR Acknowledgment option
to
options in the previous hop as indicated DSR header is implied by total length of the IP.Source_Address.
Since the receiving node DSR
header.

The DSR header is inserted in the final destination, there
will be no opportunity for packet following the originator packet's IP
header, before any following header such as a traditional (e.g., TCP
or UDP) transport layer header. Specifically, the Protocol field
in the IP header is used to obtain indicate that a
passive acknowledgment, DSR header follows the
IP header, and the receiving node must infer the
originator's request for an explicit acknowledgment.

When sending a packet:

1. Before sending a packet, insert a copy of the packet into the
Retransmission Buffer and update the information maintained about
this packet Next Header field in the Retransmission Buffer.

2. If after processing the Routing Header, RH.Segments_Left DSR header is equal used to 0, then node A MUST set
indicate the Acknowledgment Request (R) bit in type of protocol header (such as a transport layer
header) following the Routing Header before transmitting DSR header.

The total length of the packet over its final
hop.

3. If after processing DSR header (and thus the Routing Header and copying
RH.Address[n] to IP.Destination_Address, node A determines that
RH.OUT_C_bit[n+1] is set, then node A total, combined
length of all DSR options present) MUST set the Acknowledgment
Request (R) bit in the Routing Header before transmitting the
packet (since the C bit was set during Route Discovery by the
node now listed as the IP.Destination_Address to indicate that
it will propagate the packet out a different interface, and that
node A will not receive be a passive acknowledgment).

4. Set the retransmission timer for multiple of 4 octets.
This requirement preserves the packet alignment of any following headers in
the Retransmission
Buffer.

5. Transmit the packet.

6. If a passive or explicit acknowledgment is received before the
retransmission timer expires, then remove the packet from the
Retransmission Buffer and disable the retransmission timer.
DONE.

7. Otherwise, when the Retransmission Timer expires, remove the
packet from the Retransmission Buffer.

8. If DSR_MAXRXTSHIFT transmissions have been done, then attempt
to salvage the packet (Section 8.5.5). Also, generate a Route
Error. DONE.

9. GOTO step 1.

Broch,

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 31] 20]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

8.5.2. Using Link Layer Acknowledgments

If explicit failure notifications are provided by the link layer,
then all packets are assumed 2 March 2001

5.1. Fixed Portion of DSR Header

The fixed portion of the DSR header is used to carry information that
must be correctly received by present in any DSR header. This fixed portion of the next hop
and a Route Error is sent only when a explicit failure notification
is made from DSR
header has the link layer.

Nodes receiving a packet without a Routing 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 do not need to send
an explicit Acknowledgment to the packet's originator, since | Reserved | Payload Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
. .
. Options .
. .
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Next Header

8-bit selector. Identifies the
link layer will notify type of header immediately
following the originator if DSR header. Uses the packet was not received
properly.

8.5.3. Originating a Route Error

If same values as the next hop of a packet is found to be unreachable IPv4
Protocol field [26].

Reserved

Sent as described
in Section 8.5, a Route Error packet (Section 7.2.2) MUST be returned
to 0; ignored on reception.

Payload Length

The length of the node whose cache generated DSR header, excluding the information used to route 4-octet fixed
portion. The value of the
packet.

When a node A generates a Route Error for packet P, it MUST
initialize Payload Length field defines the fields
total length of all options carried in the Route Error as follows:

Error.Source_Address = Home address of node A
Error.Unreachable_Address = Home address DSR header.

Options

Variable-length field; the length of the unreachable node

- If Options field is
specified by the packet contains a Payload Length field in this DSR Routing Header and header.
Contains one or more pieces of optional information (DSR
options), encoded in type-length-value (TLV) format (with the S bit is NOT
set,
exception of the packet has been forwarded without Pad1 option, described in Section 5.8).

The placement of DSR options following the need for salvaging
up to this point.

Error.Destination_Address = P.IP.Source_Address

- Otherwise, if fixed portion of the packet contains a DSR Routing Header and the S
bit IS set,
header MAY be padded for alignment. However, due to the packet has been salvaged by an intermediate node,
and thus typically
limited available wireless bandwidth in ad hoc networks, this Routing Header was placed there by the salvaging
node.

Error.Destination_Address = P.RoutingHeader.Address[1]

- Otherwise, if the packet does padding
is not contain required, and receiving nodes MUST NOT expect options within
a DSR Routing Header,
the packet must have been originated by this node A.

Error.Destination_Address = Home address of node header to be aligned. A

Send the node inserting a DSR header into
a packet containing MUST set the Route Error to Error.Destination_Address,
performing Route Discovery if necessary.

As an optimization, Route Errors that are discovered by Don't Fragment (DF) bit in the packet's originator (such that Error.Source_Address is equal to
Error.Destination_Address) SHOULD be processed internally. Such

Broch, IP
header.

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

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 32] 21]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

processing should invoke all the steps that would be taken if a 2 March 2001

- Route
Error Request option was created, transmitted, received, and processed,
but an actual packet containing a (Section 5.2)

- Route Error Reply option SHOULD NOT be
transmitted.

8.5.4. Processing a Route Error Option

Upon receipt of a (Section 5.3)

- Route Error via any mechanism, a node
SHOULD remove any route from its Route Cache that uses the hop
(Error.Source_Address, Error.Index to Error.Unreachable_Address).
This includes all option (Section 5.4)

- Acknowledgement Request option (Section 5.5)

- Acknowledgement option (Section 5.6)

- Source Route Errors overheard, and those processed
internally as described in Section 8.5.3.

When the node identified by Error.Destination_Address receives
the option (Section 5.7)

- Pad1 option (Section 5.8)

- PadN option (Section 5.9)

Johnson, et al Expires 2 September 2001 [Page 22]

INTERNET-DRAFT The Dynamic Source Routing Protocol 2 March 2001

5.2. Route Error, it SHOULD verify that the source route
responsible for delivering the Request Option

The Route Error includes the same
hops Request DSR option is encoded as the working prefix of the original packet's source route
(Error.Destination_Address 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 Error.Source_Address). If any
hop listed in the working prefix is not included in address of the Route
Error's source route, then node originating this packet.
Intermediate nodes that retransmit the originator SHOULD forward packet to propagate the
Route
Error back along the working prefix (Error.Destination_Address Request MUST NOT change this field.

Destination Address

MUST be set to
Error.Source_Address) so that each node along the working prefix will
remove the invalid route IP limited broadcast address
(255.255.255.255).

Hop Limit (TTL)

MAY be varied from its 1 to 255, for example to implement
non-propagating Route Cache.

If the node processing a Route Error option discovers its home
address is Error.Destination_Address Requests and the packet contains
additional Route Error option(s) later on the inside Request expanding-ring
searches (Section 3.3.4).

Route Request fields:

Option Type

Opt Data Len

8-bit unsigned integer. Length of the Hop
by Hop options header, we call option, in octets,
excluding the additional Route Errors nested
Route Errors. Option Type and Opt Data Len fields.

Johnson, et al Expires 2 September 2001 [Page 23]

INTERNET-DRAFT The node MUST deliver the first nested Route Error
to Nested_Error.Destination_Address, performing Route Discovery if
needed. It does this Dynamic Source Routing Protocol 2 March 2001

Identification

A unique value generated by removing the Route Error option listing
itself as the Error.Destination_Address, finding initiator (original sender) of
the first nested Route Error option, and originating the remaining packet to
Nested_Error.Destination_Address. This mechanism allows Request. Nodes initiating a Route Request generate
a new Identification value for the
proper handling of each Route Errors that are discovered while delivering Request, for example
based on a sequence number counter of all Route Error.

8.5.5. Salvaging Requests
initiated by the node.

This value allows a Packet

When receiving node A attempts to salvage determine whether it
has recently seen a packet originated at copy of this Route Request: if this
Identification value is found by this receiving node S and
destined in its
Route Request Table (in the cache of Identification values
in the entry there for this initiating node), this receiving
node D, it MUST perform discard the following steps:

1. Generate and send a Route Error to S as explained in
Section 8.5.3.

2. Call Route_Cache.Get() to determine if it has Request. When propagating a cached source
route to Route
Request, this field MUST be copied from the packet's ultimate destination D (which is received copy of
the last Route Request being propagated.

Target Address listed in

The address of the Routing Header).

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 33]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

3. If node A does not have a cached route for node D, it MUST
discard the packet. DONE.

4. Otherwise, let Salvage_Address[1] through Salvage_Address[m] be that is the sequence target of hops returned from the Route Cache. Initialize
the following fields in
Request.

Address[1..n]

Address[i] is the packet's header:

RT.Segments_Left = m - 2;
RT.S = 1
RT.Address[1] = Home address of Node A
RT.Address[2] = Salvage.Address[1]
...
RT.Address[n] = Salvage.Address[m] the i-th hop recorded in the Route
Request option. The IP address given in the Source Address of the packet MUST remain unchanged. When the
Routing Header field
in the outgoing packet IP header is processed, RT.Address[2],
will be copied to the IP Destination Address field.

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 34]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

9. Optimizations

A number address of optimizations can be added to the basic operation initiator of the Route
Discovery and Route Maintenance as described MUST NOT be listed in Sections 8.4
and 8.5 that can reduce the number of overhead packets and improve Address[i] fields; the average efficiency
address given in Address[1] is thus the address of the routes used first
node on data packets. This
section discusses some of those optimizations.

9.1. Leveraging the Route Cache

The data in a node's Route Cache may be stored in any format, but path after the active routes in its cache form a tree initiator. The number of routes, rooted at
this node, to other nodes addresses
present in this field is indicated by the ad hoc network. For example, the
illustration below shows an ad hoc network of six mobile nodes, Opt Data Len field in
which mobile
the option (n = (Opt Data Len - 2) / 4). Each node A has earlier completed a propagating
the Route Discovery for
mobile node D and has cached a route Request adds its own address to D through B and C:

B->C->D
+---+ +---+ +---+ +---+ this list, increasing
the Opt Data Len value by 4 octets.

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

Johnson, et al Expires 2 September 2001 [Page 24]

INTERNET-DRAFT The Dynamic Source Routing Protocol 2 March 2001

5.3. Route Reply Option

The Route Reply DSR option 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
+-+-+-+-+-+-+-+-+
| A |---->| B |---->| C |---->| D Option Type |
+---+ +---+ +---+ +---+

+---+
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| F Opt Data Len |L| Reserved | +---+
+---+ Identification | E
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|
+---+

Since nodes B and C are on the route Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[2] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[n] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

IP fields:

Source Address

Set to D, the address of the node A also learns sending the
route to both Route Reply.
In the case of these nodes a node sending a reply from its Route Discovery for D. If A
later performs
Cache (Section 3.3.2) or sending a gratuitous Route Discovery and learns the route to E through B
and C, it can represent Reply
(Section 3.4.2), this in its Route Cache with address can differ from the addition address that
was the target of the single new hop from C to E. If A then learns it can reach C in a
single hop (without needing to go through B), A SHOULD use this new
route to C Route Discovery.

Destination Address

MUST be set to also shorten the routes to D and E in its Route Cache.

9.1.1. Promiscuous Learning address of Source Routes

A the source node can add entries to its Route Cache any time it learns a new
route. In particular, when a node forwards a data packet as an
intermediate hop on of the route in that packet,
being returned. Copied from the forwarding node is
able to observe Source Address field of the entire route
Route Request generating the Route Reply, or in the packet. Thus, for example,
when any intermediate node B forwards packets case of a
gratuitous Route Reply, copied from A to D, B SHOULD
add the source route information from that packet's Routing Header
to its own Route Cache. If a node forwards a Source Address field of
the data packet triggering the gratuitous Reply.

Route Reply packet, it
SHOULD also add the source route information from fields:

Option Type

Opt Data Len

8-bit unsigned integer. Length of the route record
being returned option, in octets,
excluding the Route Reply, to its own Route Cache.

Broch, Johnson, Option Type and Maltz Opt Data Len fields.

Johnson, et al Expires 22 April 2000 2 September 2001 [Page 35] 25]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

In addition, since all wireless network transmissions at the physical
layer are inherently broadcast, it may be possible for a node 2 March 2001

Last Hop External (L)

Set to
configure its network interface into promiscuous receive mode, such indicate that the last node is able to receive all packets without link layer
address filtering. In this case, the node MAY add to its Route Cache indicated by the route information from any packet it can overhear.

9.2. Preventing Route
Reply Storms

The ability for nodes (Address[n]) is actually in a network external to reply the
DSR network; the exact sequence of hops leading to a Route Request it outside
the DSR network is not targeted at
them by using their represented in the Route Caches can result Reply. Nodes
caching this hop in a their Route Reply storm.
If Cache MUST flag the cached hop
with the External flag. Such hops MUST NOT be returned in a node broadcasts
cached Route Reply generated from this Route Cache entry, and
selection of routes from the Route Cache to route a packet
being sent SHOULD prefer routes that contain no hops flagged as
External.

Reserved

Sent as 0; ignored on reception.

Identification

Copied from the Identification field of the Route Request for a node that its neighbors
have
which this Reply is sent in their response. Sent as 0 if the Route Caches, each neighbor may attempt
Reply is not sent in response to send a Route Reply, thereby wasting bandwidth and increasing Request (a gratuitous
Route Reply).

Address[1..n]

The source route being returned by the rate Route Reply. The route
indicates a sequence of collisions in hops, originating at the area. For example, source node
specified in the network shown in
Section 9.1, if both node A and node B receive F's Route Request,
they will both attempt to reply from their Route Caches. Both will
send their Replies at about Destination Address field of the same time since they receive IP header
of the
broadcast at about packet carrying the same time. Particularly when more than Route Reply, through each of the
two mobile
Address[i] nodes in this example are involved, these simultaneous
replies from the mobile nodes receiving order listed in the broadcast may create
packet collisions among some or all Route Reply,
ending with the destination node indicated by Address[n].
The number of these replies and may cause
local congestion addresses present in the wireless network. In addition, it will
often be Address[1..n]
field is indicated by the case that Opt Data Len field in the different replies will indicate routes
of different lengths. For example, A's Route Reply will indicate option
(n = (Opt Data Len - 3) / 4).

A Route Reply option MAY appear one or more times within a
route to D that DSR
header.

Johnson, et al Expires 2 September 2001 [Page 26]

INTERNET-DRAFT The Dynamic Source Routing Protocol 2 March 2001

5.4. Route Error Option

The Route Error DSR option is one hop longer than that 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

Opt Data Len

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

For interfaces which can promiscuously listen to the channel, mobile
nodes SHOULD use current definition of the following algorithm Route Error option,
this field MUST be set to reduce 10, plus the number size of
simultaneous replies by slightly delaying their Route Reply:

1. Pick a delay period

d = H * (h - 1 + r)

where h is the length any
Type-Specific Information present in number of network hops for the route
to be returned in this node's Route Reply, r is a random number
between 0 and 1, and H is a small constant delay Error. Further
extensions to be introduced
per hop.

2. Delay transmitting the Route Reply from this node for a period Error option format may also be
included after the Type-Specific Information portion of d.

3. Within the delay period, promiscuously receive all packets at
this node. If a packet is received
Route Error option specified above. The presence of such
extensions will be indicated by this node during the delay
period that Opt Data Len field.
When the Opt Data Len is addressed to greater than that required for
the target fixed portion of this the Route Discovery
(the target is Error plus the final destination address for necessary
Type-Specific Information as indicated by the packet,
through any sequence of intermediate hops), and if Option Type
value in the length 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 route on this packet following type
value is less than h, then cancel defined:

1 = NODE_UNREACHABLE

Other values of the delay

Broch, Error Type field are reserved for future
use.

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 36] 27]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

timer and do not transmit the Route Reply 2 March 2001

Reservd

Reserved. Sent as 0; ignored on reception.

Salvage

A 4-bit unsigned integer. Copied from this node; this
node may infer that the initiator Salvage field in the
Source Route option of this the packet triggering the Route Discovery has
already received a Error,
incremented by the node returning the Route Reply, giving an equally good or better
route.

9.3. Piggybacking on Error.

Error Source Address

The address of the node originating the Route Discoveries

As described in Section 5.1, when one Error (e.g., the
node needs that attempted to send forward a packet
to another, if and discovered the sender does not have a route cached link
failure).

Error Destination Address

The address of the node to which the
destination node, it must initiate a Route Discovery, buffering the
original packet until Error must be
delivered For example, when the Route Reply is returned. The delay for
Route Discovery and the total number of packets transmitted can be
reduced by allowing data to be piggybacked on Route Request packets.
Since some Route Requests may be propagated widely within the ad hoc
network, though, the amount of data piggybacked must be limited. We
currently use piggybacking when sending a Route Reply or a Route Error packet, since both are naturally small in size. Small data
packets such as the initial SYN packet opening a TCP connection [18]
could easily be piggybacked.

One problem, however, arises when piggybacking on Route Request
packets. If a Route Request Type field is received by a node that replies set to the request based on its Route Cache without propagating the
Request (Section 9.1), the piggybacked data will be lost if the node
simply discards the Route Request. In this case, before discarding
the packet, the node must construct a new packet containing the
piggybacked data from the Route Request packet. The source route
in
NODE_UNREACHABLE, this packet MUST field will be constructed set to appear as if the new packet
had been sent by the initiator address of the Route Discovery and had been
forwarded normally to this node. Hence,
node that generated the first portion of routing information claiming that the
route is taken
hop from the accumulated route record Error Source Address to Unreachable Node Address
(specified in the Route Request
packet and Type-Specific Information) was a valid hop.

Type-Specific Information

Information specific to the remainder Error Type of the route is taken from this node's Route
Cache. The sender address in the packet MUST also be set to the
initiator of Error
message.

Currently, the Type-Specific Information field is defined only for
Route Discovery. Since Error messages of type NODE_UNREACHABLE. In this case, the replying node will be
unable to correctly recompute an Authentication header for the split
off piggybacked data, data covered by an Authentication header SHOULD
NOT be piggybacked on Route Request packets.

9.4. Discovering Shorter Routes

Once a route between a packet source and a destination has been
discovered,
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 basic DSR protocol MAY continue to use node that route
for all traffic from the source was found to the destination as long as
it continues be unreachable
(the next hop neighbor to work, even if the nodes move such that a shorter
route becomes possible. In many cases, the basic Route Maintenance
procedure will discover which the shorter route, since if a node moves
enough with address
Error Source Address was attempting to create a shorter route, it will likely also move out of
transmission range of at least one hop on transmit the existing route.

Broch, packet).

A Route Error option MAY appear one or more times within a DSR
header.

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 37] 28]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

Furthermore, when a data packet is received as the result of
operating in promiscuous receive mode, the node checks if the Routing
Header packet contains its address in the unprocessed portion of the
source route (Address[NumAddrs - SegLft] to Address[NumAddrs]). If
so, the node knows that packet could bypass the unprocessed hops
preceding it in the source route. 2 March 2001

5.5. Acknowledgment Request Option

The node then sends what Acknowledgment Request DSR option is called
a gratuitous Route Reply message to the packet's source, giving it
the shorter route without these hops.

The following algorithm describes how a node A should process packets
with an IP.Destination_Address not addressed to A or the IP broadcast
address or a multicast address that are received encoded as a result follows:

Option Type

Opt Data Len

8-bit unsigned integer. Length of A
being the option, in promiscuous receive mode:

1. If octets,
excluding the packet Option Type and Opt Data Len fields.

Identification

The Identification field is not a data packet containing set to a Routing Header,
drop the packet. DONE.

2. If the home address of this node does not appear in unique nonzero value and
is copied into the portion Identification field of the source route that has not yet been processed (indicated Acknowledgement
option when returned by
Segments Left), then drop the packet. DONE.

3. Otherwise, the node B that just transmitted receiving the packet (indicated
by Address[NumAddrs - SegLft - 1]) can communicate directly with over this node A. Create a Route Reply.
hop.

ACK Request Source Address

The Route Reply MUST list
the entire source route contained in the received packet with the
exception address of the intermediate nodes between node B and node A.

4. Send this gratuitous Route Reply to the node listed as the
IP.Source_Address of the received packet. If Route Discovery
is required it MAY be initiated, or requesting the gratuitous Route Reply
packet MAY be dropped.

9.5. Rate Limiting the Route Discovery Process

One common error condition that must be handled in an ad hoc network acknowledgment.

An Acknowledgement Request option MUST NOT appear more than once
within a DSR header.

Johnson, et al Expires 2 September 2001 [Page 29]

INTERNET-DRAFT The Dynamic Source Routing Protocol 2 March 2001

5.6. Acknowledgment Option

The Acknowledgment DSR option is encoded as follows:

Option Type

Opt Data Len

8-bit unsigned integer. Length of the case option, in which octets,
excluding the network effectively becomes partitioned.
That is, two nodes that wish to communicate are not within
transmission range of each other, Option Type and there are not enough other
mobile nodes between them to form a sequence Opt Data Len fields.

Identification

Copied from the Identification field of hops through which
they can forward packets. If a new Route Discovery was initiated
for each the Acknowledgement
Request option of the packet sent by a node in this situation, a large number being acknowledged.

ACK Source Address

The address of
unproductive Route Request packets would be propagated throughout the
subset node originating the acknowledgment.

ACK Destination Address

The address of the ad hoc network reachable from this node. In order node to
reduce which the overhead from such Route Discoveries, we use exponential
back-off acknowledgment is to limit the rate at which new Route Discoveries may be
initiated from any node for the same target. If the node attempts to
send additional data packets to this same node
delivered.

An Acknowledgement option MAY appear one or more frequently than
this limit, the subsequent packets SHOULD be buffered in the Send
Buffer until a Route Reply is received, but it MUST NOT initiate times within a

Broch, DSR
header.

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 38] 30]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

new 2 March 2001

5.7. Source Route Discovery until the minimum allowable interval between new Option

The Source Route Discoveries for this target has been reached. This limitation
on the maximum rate DSR option 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Opt Data Len |F|L|Reservd|Salvage| Segs Left |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[2] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[n] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Option Type

Opt Data Len

8-bit unsigned integer. Length of Route Discoveries for the same target is
similar to option, in octets,
excluding the mechanism required by Internet nodes to limit Option Type and Opt Data Len fields. For the rate
at which ARP requests are sent to any single IP address [2].

9.6. Improved Handling of Route Errors

All nodes SHOULD process all
format of the Source Route Error messages they
receive, regardless of whether option defined here, this field
MUST be set to the node value (n * 4) + 2, where n is the destination number of
addresses present in the Route Error, is forwarding Address[i] fields.

First Hop External (F)

Set to indicate that the first node indicated by the Source
Route Error, or promiscuously
overhears the Route Error.

Since option is actually in a Route Error packet names both ends of network external to the hop that is no
longer valid, any DSR
network; the exact sequence of hops leading from it outside the nodes receiving
DSR network are not represented in the error packet may update Source Route option.
Nodes caching this hop in their Route Caches to reflect Cache MUST flag the fact that
cached hop with the two nodes indicated External flag. Such hops MUST NOT be
returned in the packet can no longer directly communicate. A node receiving a Route Error packet simply searches its Reply generated from this Route Cache for any
entry, and selection of routes
using this hop. For each such route found, the route is effectively
truncated at this hop. All nodes on from the Route Cache to route before this hop are
still reachable on this route, but subsequent nodes are not.

An experimental optimization
a packet being sent SHOULD prefer routes that contain no hops
flagged as External.

Last Hop External (L)

Set to improve indicate that the handling of errors is
to support last hop indicated by the caching of "negative" information in a node's Source Route
Cache. The goal of negative information
option is to record that actually in a given
route was tried and found not network external to work, so that if the same route
is discovered again shortly after the failure, the Route Cache can
ignore or downgrade DSR network;
the metric exact sequence of hops leading to it outside the failed route.

We have DSR
network are not currently included this represented in the Source Route option. Nodes
caching of negative information this hop in our simulations, since it appears to be unnecessary if nodes also
promiscuously receive their Route Error packets.

9.7. Increasing Scalability

We recently designed and began experimenting with ways to integrate
ad hoc networks with Cache MUST flag the Internet and with Mobile IP [14]. In
addition to this, we are also exploring ways to increase the
scalability of ad hoc networks by taking advantage of their
cooperative nature and the fact that some hierarchy can be imposed
on an ad hoc network, just be assigning addresses to the nodes in a
reasonable way. These ideas are described in a workshop paper [4].

Broch, cached

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 39] 31]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

10. Path-State 2 March 2001

hop with the External flag. Such hops MUST NOT be returned
in a Route Reply generated from this Route Cache entry, and Flow-State Mechanisms

This section describes
selection of routes from the current design Route Cache to route a packet
being sent SHOULD prefer routes that contain no hops flagged as
External.

Reserved

Sent as 0; ignored on reception.

Salvage

A 4-bit unsigned integer. Count of our framework for
supporting better-than-best-effort Quality number of times that
this packet has been salvaged as a part of Service in DSR
networks. The framework dovetails into DSR's existing mechanisms,
and, like DSR itself, is completely on-demand in nature --- no
packets are sent unless there is user data to transfer. The
framework is based on the introduction routing
(Section 3.4.1).

Segments Left (Segs Left)

Number of two kinds route segments remaining, i.e., number of soft-state,
called path-state and flow-state, at the explicitly
listed intermediate nodes along still to be visited before reaching
the
path between senders and destinations.

Taken together, final destination.

Address[1..n]

The sequence of addresses of the path-state source route. In routing
and flow-state extensions extend the
Quality of Service provided by DSR networks in forwarding the following ways:

- They eliminate packet, the need for all data packets to carry source route is processed as
described in Sections 6.1.3 and 6.1.5.

When forwarding a packet along a DSR source
route, increasing route using a Source
Route option in the efficiency of packet's DSR header, the protocol Source Address field in general.

- They provide accurate measurements of
the state packet's IP header is always set to the address of the network to
higher layers protocols for use in adaptation.

- They enable senders to explicitly manage packet's
ultimate destination. A node receiving a packet containing a DSR
header with a Source Route option MUST examine the consumption of
resources across indicated source
route to determine if it is the network.

- They enable intended next hop for the network to provide better-than-best-effort
service via admission control packet and per-flow resource management.

10.1. Overview

Path-state allows intermediate nodes
determine how to forward packets according to
a predetermined source route, even when most packets do not include the full source route. Conceptually, packet, as defined in Sections 6.1.4
and 6.1.5.

Johnson, et al Expires 2 September 2001 [Page 32]

INTERNET-DRAFT The Dynamic Source Routing Protocol 2 March 2001

5.8. Pad1 Option

The Pad1 DSR option is encoded as follows:

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

Option Type

A Pad1 option MAY be included in the originator Options field of each data
packet initially includes both a source route and a unique path
identifier DSR header
in each packet it sends. As intermediate order to align subsequent DSR options, but such alignment is
not required and MUST NOT be expected by nodes forward
the packet, they cache the source route from the packet, indexed receiving packets
containing a DSR header.

The total length of a DSR header, indicated by the path identifier. The source can then send subsequent packets
carrying only Payload Length
field in the path identifier, since intermediate nodes will DSR header MUST be
able to forward the packet based on the source route for the path
that they have cached.

While path-state allows the elimination a multiple of the source route from each 4 octets. When
building a DSR header in a packet, thereby reducing sufficient Pad1 or PadN options
MUST be included in the overhead Options field of the DSR protocol, it also
provides a way for sources header to monitor make the state of each path through
the network. When
total length a source wishes to know the characteristics multiple of
a path through 4 octets.

If more than one consecutive octet of padding is being inserted in
the network, it piggybacks Options field of a path-metrics header
onto any data or control packet traversing the path. As the
packet propagates through DSR header, the network, each intermediate node
updates PadN option, described next,
SHOULD be used, rather than multiple Pad1 options.

Note that the set format of path-metrics carried by the packet to reflect
the local network conditions seen at the node. These metrics are
reflected back to the sender by the destination, along with the path

Broch, Pad1 option is a special case; it does
not have an Opt Data Len or Option Data field.

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 40] 33]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

identifier, and enable the sender to track the value of these metrics
for each of the source routes it 2 March 2001

5.9. PadN Option

The PadN DSR option is currently using.

We are currently experimenting with metrics that are easy for nodes
to measure, that require constant size to represent regardless of
source route length, and that would enable the sender's network
layer to provide useful feedback to higher layers on the state encoded as follows:

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

Option Type

Opt Data Len

8-bit unsigned integer. Length of the network. For example, by including ``available bandwidth''
or ``battery level'' as a metric, senders can load balance option, in octets,
excluding the consumption Option Type and Opt Data Len fields.

Option Data

A number of resources across zero valued octets equal to the network. We have also
considered Opt Data Len.

A PadN option MAY be included in the possibility Options field of replacing the TCP congestion control
algorithm with a ``leaky-bucket'' system controlled by the reflected
path-metrics --- our measured performance results show this could
dramatically improve TCP throughput DSR header
in environments where many
packets are lost due to packet corruption. The feedback could also
be used as inputs order to other researcher's systems for improving the
transport layer, align subsequent DSR options, but such as Liu alignment is
not required and Singh's ATCP [11], or for adaptation
at higher layers, as in Odyssey [13].

Flow-state allows MUST NOT be expected by nodes receiving packets
containing a source to differentiate its traffic into
flows, and then request better-than-best-effort handling for these
flows. With the additional information provided DSR header.

The total length of a DSR header, indicated by the flow-state, Payload Length
field in the network can provide admission control and promise DSR header MUST be a specific
Quality multiple of Service (QoS) to each flow. Since the ad hoc network may
frequently change topology, 4 octets. When
building a DSR header in a packet, sufficient Pad1 or PadN options
MUST be included in the flow-state mechanisms are directly
integrated into Options field of the routing protocol to minimize their reaction time
and provide notifications DSR header to a flow when make the network must break its
promise for
total length a specific level multiple of QoS.

10.2. Path-State and Flow-State Identifiers 4 octets.

Johnson, et al Expires 2 September 2001 [Page 34]

INTERNET-DRAFT The metadata that intermediate nodes in the network must process
is divided into path-state and flow-state, where path-state is
the fundamental unit of Dynamic Source Routing Protocol 2 March 2001

6. Detailed Operation

6.1. General Packet Processing

6.1.1. Originating a Packet

When originating any packet, a node using DSR routing information and flow-state is MUST perform
the
fundamental unit of Quality of Service information.

Path-state is associated with a particular set following sequence of hops through steps:

- Search the
network from some source S to a destination D (i.e., node's Route Cache for a particular
source route in to the network). It consists of address given in
the information needed
to route packets along IP Destination Address field in the path, and information about packet's header.

- If no such route is found in the carrying
capacity of Route Cache, then perform
Route Discovery for the path, such Destination Address, as described in
Section 6.2.

- If the unused bandwidth along packet contains a Route Request option, then replace the path or
IP Destination Address field with the minimum latency IP "limited broadcast"
address (255.255.255.255) [3].

- Else, this node must have a route to the Destination Address
of the path.

Flow-state is specific to packet (since otherwise a particular class Route Request would have
been added to the packet). If the length of packets flowing
between S and D that is routed over a given path. Flow-state this route is
used
greater than 1 hop, or if the node determines to record Quality request a DSR
network-layer acknowledgement from the first hop of Service promises that have been made for the route,
then insert a
particular flow, DSR header as described in Section 6.1.2, and allows packets
insert a Source Route option, as described in Section 6.1.3. The
source route in the packet is initialized from S the route to D that take the same
path through
Destination Address found in the network Route Cache.

- Transmit the packet to be treated differently by intermediate
nodes. For example, all the TCP connections between S and D that

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 41]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

take address given in the same path will share next hop, using
Route Maintenance to retransmit the same path-state, but may have
independent flow-state. At any point packet if necessary, as
described in time, S may use multiple
paths for its traffic Section 6.3.

6.1.2. Adding a DSR Header to D and each of these paths may be comprised
of many flows. However, a single network layer flow may not be
multiplexed over different paths.

To represent paths and flows inside the network, we use Packet

A node originating a scheme
inspired by packet adds a DSR header to the Virtual Path Index and Virtual Circuit Index of
ATM networks [23, p. 451]. Paths are identified packet, if
necessary, to carry information needed by the logical
concatenation of the source node address and routing protocol. A
packet MUST NOT contain more than one DSR header. A DSR header is
added to a 16-bit path identifier
where the low 5 bits are 0. Flows are identified packet by a path
identifier where performing the low 5 bits are used to distinguish between following sequence of steps
(these steps assume that the
different flows packet contains no other headers that use
MUST be located in the same path.

This scheme has two main advantages. First, each source node can
independently generate globally unique path- and flow-identifiers.
Second, packet before the hierarchical relation of flow-identifiers to
path-identifiers means DSR header):

- Insert a DSR header after the IP header but before any other
header that many flows from may be present.

- Set the same source node can
share Next Header field of the same path-state, which reduces DSR header to the overhead Protocol
number field of maintaining the routing information. packet's IP header.

Johnson, et al Expires 2 September 2001 [Page 35]

INTERNET-DRAFT The drawback is that if a flow must be
rerouted, its flow identifier will change. However, when a flow is
rerouted the QoS metadata must be renegotiated anyway, so changing
flow identifiers will not create needless additional work in Dynamic Source Routing Protocol 2 March 2001

- Set the
network.

10.3. Path-State Creation, Use, and Maintenance

The path-state portion Protocol field of the protocol has two major goals. The
first goal is packet's IP header to ensure sufficient state exists at the nodes along Protocol
number assigned for a
path from DSR header (???).

6.1.3. Adding a source S Source Route Option to a destination D so that packets from S Packet

A node originating a packet adds a Source Route option to D
do not need the packet,
if necessary, in order to carry the complete source route. The second goal is
to allow S to discover the characteristics route of a particular path to D
so that it can adapt its sending pattern hops from this
originating node to the capabilities final destination address of the
path, or even choose a different path entirely.

The next sections describe how packet.
Specifically, the path-state is created, how node adding the
characteristics of Source Route option constructs
the path are discovered, Source Route option and what metrics can be
used to characterize modifies the path.

10.3.1. Creating Path-State for Routing

To create IP packet according to the path-state, we assume that
following sequence of steps:

- A Source Route Discovery proceeds option, as
normal described in DSR. Once the source node S has obtained a source route Section 5.7, is created
and appended to the destination D, it begins sending data packets to D as normally
done DSR header in DSR, with each the packet carrying a full source route header.
Internally, S assigns a path-identifier (a DSR header is
added, as described in Section 6.1.2, if not already present).

- The number of Address[i] fields to that particular source
route and stores include in the DSR Source
Route option (n) is the path-identifier number of intermediate nodes in its route cache along with the
source route. S then includes route for the path-identifier as part packet (i.e., excluding address of the

Broch, Johnson,
originating node and Maltz Expires 22 April 2000 [Page 42]

INTERNET-DRAFT the final destination address of the
packet). The Dynamic Segments Left field in the DSR Source Routing Protocol 22 October 1999

A -----------------> B -----------------> C -----------------> D

(a) Packet with path identifier and source route.

A -----------------> B -----------------> C -----------------> D

(b) Packet with path identifier only.

Figure 2: Path identifiers assigned to a source route by the
originating node A enable later packets Route option
is initialized equal to omit n.

- The Destination Address from the source route.

source route IP header as shown is copied into
Address[n] in Figure 2(a). As each intermediate
node processes the DSR Source Route option.

- The first hop of the source route to forward for the packet, it also stores packet is copied into
the source route Destination Address field in its route cache, indexed by the source and
path-identifier.

After sending a packet containing both IP header.

- The remaining hops of the source route and for the
path-identifier packet are copied
into sequential Address[i] fields in the Source Route option,
for i = 1, 2, ..., n-1.

- The First Hop External (F) bit in the Source Route option is
copied from the External bit flagging the first hop node in the network, S can begin sending subsequent
packets to D without a full
source route --- carrying only for the
path-identifier packet, as shown indicated in Figure 2(b). Each intermediate node
receiving such a packet queries its route cache to find the route Route Cache.

- The Last Hop External (L) bit in the packet Source Route option is supposed to take, and determines its next hop. As
explained
copied from the External bit flagging the last hop node in Section 10.5, if the cached
source route is not
available at some intermediate node, S will receive a Route Error and
can then correct the situation.

10.3.2. Monitoring Characteristics of for the Path

In order to support network layer services such packet, as balancing the
traffic load across indicated in the network, end-systems must have Route Cache.

6.1.4. Receiving a method for
determining the characteristics of the paths through the network that

Broch, Packet

When a node receives any packet containing a DSR header, it MUST
process the packet according to the following sequence of steps:

- If the Destination Address in the packet's IP header matches
one of this receiving node's own IP address(es), remove the DSR

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 43] 36]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

they could use. While many schemes have been proposed by which the
end-systems themselves can measure the characteristics of a path
(e.g., TCP congestion window and RTT calculations [1, 22, 24] 2 March 2001

header and
SPAND [21]), we hypothesize that, particularly in all the included DSR options in the dynamic
environment of an ad hoc network, more useful, more accurate, header, and
more timely information can be developed by enlisting pass
the aid rest of the
nodes along the path to measure the path characteristics.

We propose that each node can measure the activity around itself,
and thereby determine information such as: the mean latency it adds packet to the packets it forwards network layer.

- Examine and the latency variation (jitter); the
number process each of additional packets per second it believes it can process;
or the unused amount of wireless media capacity options (if any) in the air around DSR
header in the node. Experimentation will be required to discover exactly order in which metrics will prove to they occur in the packet, skipping
over any Pad1 or PadN options.

Any DSR routing information carried in a packet SHOULD be accurately measurable examined
and useful,
though Section 10.3.3 provides several proposals. If reflected in the metrics
kept by each node on a path node's Route Cache, even if the options in
the packet are combined, not otherwise processed as described above. In
particular, the result should following routing information SHOULD be handled in
this way:

- In a
characterization of Route Request option, the path that accumulated route record,
represented by the packet sender can use to
organize or adapt its offered load.

To implement this scheme, we first define a new type IP Source Address of extension
header for DSR than can be piggybacked onto a packet in the same way
as the existing DSR headers. This new header is called the path
metrics header (written as Measure) packet and conceptually consists of by the
path-identifier
sequence of Address[i] entries in the path along which Route Request option SHOULD
be added to the metrics are measured, node's Route Cache.

- In a Route Reply option, the type route record being returned,
represented by the sequence of Address[i] entries in the Measure, Route
Request option and by the metrics themselves encoded Destination Address in a TLV
format (Section 10.6.2).

Whenever a sender S wishes the packet's IP
header SHOULD be added to measure the characteristics of a path
it is using, it includes node's Route Cache.

- In an Acknowledgement option, the Measure header in any packet it sends
along that path, setting single link from the type of
ACK Source Address to the header ACK Destination Address SHOULD be added
to record. As each
node along the path forwards node's Route Cache.

- In a Route Error option, the packet, it updates single link from the variables
inside
Error Source Address to the Measure header with Unreachable Node Address MUST
be removed from the metrics it has measured locally.
When node's Route Cache.

- In a Source Route option, the header reaches indicated source route SHOULD
be added to the final destination D, D sets node's Route Cache, subject to the type conditions
identified in Section 3.3.1. The full sequence of hops in the Measure header to return and piggybacks
DSR Source Route option is as follows:

* The Source Address in the packet's IP header into any
packet headed back to S. Since is the path metrics header includes first hop
(the sender of the path-identifier packet).

* The sequence of hops

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

follow immediately after the path along which it was measured, S can
include IP Source Address in the data into its route cache for future use, and can treat source
route, where n is the receipt number of addresses in the path metrics header as a positive acknowledgment
that the path-state between S and D for packet, or
(Opt Data Len - 2) / 4.

* The Destination Address in the given path-identifier packet's IP header is correctly set up. This could lead S to cease including source
routes in the packets it sends along
final destination of the path, as described in
Section 10.3.1.

If we find that it packet and is valuable to immediately provide S with the path
metrics last hop of every discovered route, we could alter Route Discovery
slightly to generate this information. Currently, if an intermediate
node has a cached route that it can use to answer a Route Request,
it generates a Route Reply itself. Instead, we could require it to
place its proposed route on the Route Request (turning it from a

Broch,
source route.

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 44] 37]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

flood-fill broadcast into 2 March 2001

In addition to the processing of received packets described above, a unicast packet) and send
node SHOULD examine the packet to determine if the destination so it will measure the metrics receipt of this
packet indicates an opportunity for automatic route shortening, as
described in Section 3.4.2. If the complete path.
The destination will received packet satisfies the
tests described there, then return this node SHOULD perform the metrics following
sequence of steps:

- Return a gratuitous Route Reply to the source along with IP Source Address of the Route Reply
packet, as described above.

We have been intending to experiment with this alteration to
Route Discovery for some time, in Section 3.4.2.

- Discard the received packet, since it offers two benefits,
even without path-state metrics. It should decrease the
number packet has been received
before its normal traversal of broken routes returned by Route Discovery since
each cached the packet's source route is tested before being returned, and
it should save us from jeopardizing one data packet for
every bad route in someone's cache. The cost is some extra
latency on Route Discovery.

10.3.3. Candidate Metrics

In order to limit the additional overhead that collecting and
distributing path-state metrics will place on the network, all the
metrics must would
have the property that the amount of space required caused it to
express the metric does not increase as the number reach this receiving node. Another copy of hops on
the
path increases. Experimentation packet will be required to determine which
metrics are most accurately measured and most useful, but our initial
set of candidates includes normally arrive at this node as indicated in
the following:

- Interface queue length --- Our previous work [12] has shown that packet's source route; discarding this is a good estimator of local congestion.

- Rate initial copy of interface queue draining --- When an interface is
backlogged, the rate at
packet, which packets leave triggered the queue directly
measures gratuitous Route Reply, will prevent
the usable capacity duplication of this packet that interface.

- Quiet time fraction --- When an interface is not backlogged,
the usable capacity of would otherwise occur.

6.1.5. Processing a Received Source Route Option

If a received packet contains a DSR header with a DSR Source Route
option, the interface can Source Route option MUST be estimated by
promiscuously listening to the media examined and measuring the fraction
of time during which it processed (even
though this node is not indicated in use (though this will
overestimate the capacity).

- Fraction Free Air Time --- The fraction Destination Address field of time our interface
would be able
the packet's IP header).

If, after processing a Source Route option in a received packet, an
intermediate node determines that the packet is to send be forwarded onto
a packet. That is, link whose link MTU is less than the fraction size of time the interface does not sense carrier, is not deferring, packet, the node
MUST discard the packet and is
not backed off. Current experiments show this is send an excellent
predictor of congestion and available capacity.

- Forwarding latency and variation --- This can be measured
as ICMP Packet Too Big message to
the time between when packet's Source Address [23].

A Source Route option in a packet is received and when it DSR header for IPv4 is
acknowledged by processed according
to the next hop.

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 45]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999 following sequence of steps:

- Unidirectional links --- Paths containing unidirectional links
are usable, but undesirable as they increase If the overhead value of the Segments Left field in the Source Route Maintenance.

- Packet loss rate --- Signal quality information
option equals 0, then remove the Source Route option from the
interface itself, or DSR
header.

- Else, let n equal (Opt Data Len - 2) / 4. This is the frequency number of hop-by-hop retransmission,
can be used to estimate
addresses in the loss rate of each link. Source Route option.

- Likelihood of path breakage --- Intermediate nodes may know ahead
of time that they intend to shutdown or move such that paths
through them will no longer work.

These metrics all have If the property that they can be expressed in
a single value that each node can measure locally. As a packet
with a path metrics header passes through a node, the metrics in of the header can be updated Segments Left field is greater than n, then
send an ICMP Parameter Problem, Code 0, message [23] to reflect the node's metrics using a
combination function like minimum, maximum, sum, or weighted average
that produces another single value IP
Source Address, pointing to replace the one already in Segments Left field, and discard
the header. This updating will be done at packet. Do not process the last possible moment
before Source Route option further.

- Else, decrement the packet is forwarded, in order to assure value of the packet has Segments Left field by 1. Let i
equal n minus Segments Left. This is the
most current metrics on it when it leaves.

10.4. Flow-State Creation, Use, and Maintenance

The flow-state portion index of the protocol enables a sender to obtain
promises from all nodes along a path next
address to be visited in the Address vector.

Johnson, et al Expires 2 September 2001 [Page 38]

INTERNET-DRAFT The Dynamic Source Routing Protocol 2 March 2001

- If Address[i] or the IP Destination Address is a destination that a
certain set of resources are available along multicast
address, then discard the path, and that packet. Do not process the intermediate nodes are committed to making these resources
available for Source
Route option further.

- Forward the particular flow. This allows a sender packet to obtain
better-than-best-effort Quality the IP address specified in the Address[i]
field of Service for a flow by obtaining
promises from the intermediate nodes to reserve IP header, following normal IP forwarding
procedures, including checking and decrementing the resources needed
to provide that QoS.

Unlike prior QoS work Time-to-Live
(TTL) field in wired networks, at the packet's IP header [24, 3]. In this point we cannot
formally characterize or bound exactly what type
forwarding of services the
flow-state protocol will packet, the next hop node (identified by
Address[i]) MUST be able to offer. The goal is to provide
CBR and TCP streams with treated as a direct neighbor node; the ability
transmission to specify and obtain that next node MUST be done in a
minimum bandwidth single IP
forwarding hop, without Route Discovery and delay/jitter bound. If without searching the environment is
particularly harsh, it is possible that only best-effort service will
be offerable. It is this intuition that leads us to
Route Cache.

- In forwarding the system packet, perform Route Maintenance for the next
hop of
promises and notifications. Experimentally, we hope to determine
how stable and effective this system will be the packet, by verifying that the packet was received by
that next hop, as described in Section 6.3.

Multicast addresses MUST NOT appear in a multi-hop ad hoc
network environment.

10.4.1. Requesting Promises along Existing Paths

Similar to Source Route option or in
the use IP Destination Address field of the path metrics header, at any time a promise
can be requested or changed along any path an originator is currently

Broch, packet carrying a Source Route
option in a DSR header.

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 46] 39]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

using. Once an originating 2 March 2001

6.2. Route Discovery Processing

Route Discovery is the mechanism by which a node has created S wishing to send a path-identifier
for
packet to a route through the network, it can request destination node D obtains a promise of
network resources along that source route by first generating to D. Route
Discovery is used only when S attempts to send a new
flow-identifier packet to identify the promise. D and
does not already know a route to D. The originator then fills
out node initiating a flow-request header (written Route
Discovery is known as Flow Request) and inserts it
into any packet sent along that path.

Figure 3 shows the conceptual layout of a Flow Request, which
contains the new path-identifier assigned by the originator, the
flow-identifier of the promise that this request supersedes (if any), the requested lifetime "initiator" of the promise, Route Discovery, and the QoS parameters that
describe
destination node for which the requested promise itself. Section 10.6.3 provides Route Discovery is initiated is known
as the
detailed packet format. The use "target" of the minimum and requested fields
for the QoS parameters differs depending Route Discovery.

Route Discovery operates entirely on whether the Flow Request
is piggybacked demand, with a node initiating
Route Discovery based on its own origination of new packets for
some destination address to which it does not currently know a
route. Route Request Discovery does not depend on any periodic or not, as described below.

When background
exchange of routing information or neighbor node detection at any
layer in the network protocol stack at any node.

The Route Discovery procedure utilizes two types of messages, a Flow Route
Request piggybacked on a unicast packet is received by (Section 5.2) and a
node, Route Reply (Section 5.3), to actively
search the node performs the following steps:

- If the node is ad hoc network for a route to the destination desired destination.
These DSR messages MAY be carried in any type of the IP packet, it converts through
use of the
Flow Request into DSR header as described in Section 5.

A Route Discovery for a Measure with type return and uses destination address SHOULD NOT be initiated
unless the current
values initiating node has a packet in its Send Buffer requiring
delivery to that destination. A Route Discovery for a given target
node MUST NOT be initiated unless permitted by the desired fields of rate-limiting
information contained in the Flow Route Request to populate Table. After each
Route Discovery attempt, the
fields interval between successive Route
Discoveries for this target MUST be doubled, up to a maximum of
MAX_REQUEST_PERIOD, until a valid Route Reply is received for this
target.

6.2.1. Originating a Route Request

A node initiating a Route Discovery for some target creates and
initializes a Route Request option in a DSR header in some IP packet.
This MAY be a separate IP packet, used only to carry this Route
Request option, or the Measure. It then piggybacks node MAY include the Measure onto any Route Request option
in some existing packet being returned it needs to send to the originator.

- Else if the intermediate target node has available enough resources to
meet (e.g.,
the minimum requested promise in IP packet originated by this node, that caused the Flow Request, it:

* Sets aside node to
attempt Route Discovery for the maximum destination address of its available resources and the
desired resources. packet).
The set aside resources are held Route Request option MUST be included in a
tentative promise pool until DSR header in the promise is confirmed, or a
relatively short timeout expires.

* Nodes can recycle resources from listed old flow-id

+--------------------------------------+
| flow-id | old flow-id |
+--------------------------------------+
| lifetime |
+--------------------------------------+
| capacity | min | desired |
| latency | min | desired |
|variation | min | desired |
| loss | min | desired |
+--------------------------------------+

Figure 3: Conceptual layout of
packet. To initialize the Flow Route Request header.

Broch, option, the node performs
the following sequence of steps:

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

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 47] 40]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

* Updates the desired fields of 2 March 2001

- The Opt Data Len field in the Flow Request option MUST be set to reflect the resources set aside (there is questionable value in a
down stream node allocating more resources to a flow than an
upstream node can currently handle).

* Forward 6.
The total size of the packet and piggybacked Flow Route Request to option when initiated
is 8 octets; the next
node on Opt Data Len field excludes the path. size of the
Option Type and Opt Data Len fields themselves.

- Else, The Identification field in the node does not have enough resources option MUST be set to meet the
minimum requested promise, so it sends the originator a new
value, different from that used for other Route
Error piggybacked with Requests recently
initiated by this node. For example, each node MAY maintain a Measure reflecting the minimum of the
current values of the desired fields in the Flow
single counter value for generating a new Identification value
for each Route Request and the
available resources. it initiates.

- The type Target Address field is in the option MUST be set to refused. Such a
Measure enables the originator to learn three things: IP
address that its
requested cannot be satisfied along the given path; is the identity target of this Route Discovery.

The Source Address in the bottleneck node; and the available resources up to and
through IP header of this packet MUST be the bottleneck node.

When node's
own IP address. The Destination Address in the originating node receives a Measure IP header of type return
for a flow on which this
packet MUST be the IP "limited broadcast" address (255.255.255.255).

A node MUST maintain in its Route Request Table, information about
Route Requests that it has an outstanding Flow initiates. When initiating a new Route
Request, it accepts the promised level of service by changing node MUST use the type of information recorded in the Measure
header to confirm Route
Request Table entry for the target of that Route Request, and piggybacking it MUST
update that information in the header on any packet going
along table entry for use in the flow. This informs next Route
Request initiated for this target. In particular:

- The Route Request Table entry for a target node records the intermediate nodes to move
Time-to-Live (TTL) field used in the set
aside resources from IP header of the tentative promise pool to last Route
Request initiated by this node for that target node. This
value allows the allocated
pool, and enables upstream nodes node to free any set aside resources in
excess implement a variety of algorithms
for controlling the capacity spread of its Route Request on each Route
Discovery initiated for a bottleneck downstream node.

The target. As examples, two possible
algorithms for this use of the old flow-id to recycle resources is important TTL field are described in
Section 3.3.4.

- The Route Request Table entry for two
reasons. First, it enables an originator to attempt to increase or
decrease the amount of a current promise without losing the resources
it already has promised. Second, both packet loss and target node records the expanding
ring search
number of consecutive Route Discovery may result in several Flow Requests
being sent for the same flow. If subsequent Flow Requests initiated for this target
since receiving a
flow were not able valid Route Reply giving a route to notify intermediate nodes that they can reuse
resources set aside while processing earlier Flow Requests, target
node, and the
network could quickly reach a state where admissible flows are being
needlessly rejected.

10.4.2. Requesting Promises as Part remaining amount of Route Discovery

The scheme for requesting promises described in the previous section
has the advantage time before which this node MAY
next attempt at a Route Discovery for that it enables target node.

These values MUST be used to implement an originator exponential back-off
algorithm to request or update
a promise for a flow along any route currently in its route cache,
regardless of how it obtained the route. For limit the common case in rate at which a this node wishes to obtain a resource promise for a initiates new flow to
a previously unknown destination, we can integrate
Route Discoveries for the flow request
with same target address. Until a valid
Route Reply is received for this target node address, the timeout
between consecutive Route Discovery initiations for this target
node SHOULD increase by doubling the destination.

Broch, Johnson, timeout value on each new
initiation.

The behavior of a node processing a packet containing DSR header with
both a Source Route option and Maltz a Route Request option is unspecified.

Johnson, et al Expires 22 April 2000 2 September 2001 [Page 48] 41]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

Integrating the flow request with 2 March 2001

Packets SHOULD NOT contain both a Source Route Discovery enables us to avoid
the inefficiency of discovering routes that will not option and a Route
Request option.

Packets containing a Route Request option SHOULD NOT be usable
retransmitted, SHOULD NOT request a DSR acknowledgment by including
an Acknowledgement Request option, SHOULD NOT expect a passive
acknowledgment, and SHOULD NOT be placed in the
flow due to insufficient resources. Retransmission
Buffer. The integration repeated transmission of flow requests
with packets containing a Route Discovery also allows us to avoid
Request option is controlled solely by the logic described in this
section.

6.2.2. Processing a common pitfall of
QoS schemes that layer Received Route Request Option

When a reservation signaling protocol on top of node receives a unicast routing algorithm --- schemes without tight integration
will refuse admissible flows whenever packet containing a Route Request option, the unicast routing algorithm
directs
node MUST process the request packets into a congested area option according to the following sequence of
steps:

- If the network,
unless Target Address field in the signaling protocol also provides Route Request matches this
node's own IP address, then the node SHOULD return a method Route Reply
to backtrack the request and route around initiator of this Route Request (the Source Address in the congested area. Utilizing
IP header of the same
mechanisms currently used packet), as described in Route Discovery, we can avoid the need Section 6.2.4. The
source route for backtracking.

We call this reply is the combination sequence of flow requests with hops

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

where initiator is the address of the initiator of this Route Discovery
QoS-guided
Request, each Address[i] is an address from the Route Request,
and target is the target of the Route Discovery, which originating nodes can invoke simply
by piggybacking a Flow Request on (the Target Address
field in the Route Request. Each Request).

The node
receiving MUST then continue processing the Flow Request uses rest of the same algorithm described packet
normally. The node in
Section 10.4.1, with two exceptions:

- Nodes silently discard this case MUST NOT retransmit the Route
Request if they can to propagate it to other nodes. Do not meet
minimum requirements

- Unless process the Route
Request indicates that replying from cache is
forbidden, nodes with a cached option further.

- Else, the node MUST examine the route to destination unicast recorded in the Route
Request along option (the IP Source Address field and the sequence of
Address[i] fields) to determine if this node's own IP address
already appears in this list of addresses. If so, the cached route.

A node requiring a route with a QoS promise uses MUST
discard the entire packet carrying the following
algorithm. First, it sends a Route Request that permits intermediate
nodes to reply from cache. If option.

- Else, the network is uncongested, this
should frequently and quickly succeed in returning both a Route Reply
and a Measure describing the available QoS along the discovered
path. If after a timeout, the originating node has not received a
Route Reply, it begins another MUST search its Route Discovery, this time forbidding
replies from cache, which will force an exploration of all feasible
paths to the destination.

This scheme does risk Request Table for an implosion of unicast Requests at entry
for the target initiator of the this Route Discovery (e.g., if target Request (the IP Source Address
field). If such an entry is a popular server to which
many nodes have cached routes). At the cost of additional complexity
and soft-state, it would be possible to add hold-downs at found in the nodes
surrounding table, the target so that only node MUST
search the first few cache of Identification values of recently received
Route Requests are
forwarded towards the target.

10.4.3. Providing Notifications of Changing Path Metrics

When a node detects in that it must break a promise, it must notify the
node table entry, to which it made that promise. It is determine if an open question how entry
is present in the
now reduced resources should be distributed among cache matching the flows. We

Broch, Johnson, Identification value
and Maltz target node address in this Route Request. If such an
(Identification, target address) entry is found in this cache in

Johnson, et al Expires 22 April 2000 2 September 2001 [Page 49] 42]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

currently pick 2 March 2001

this entry in the minimum set of promises to break that leave Route Request Table, then the
other promises unchanged.

The difficulty in providing notification of a changed path metric is
getting this information back to node MUST discard
the source. When promise must be
broken at a entire packet carrying the Route Request option.

- Else, this node B, it sends a Measure to SHOULD further process the originator indicating
what resources are now available. The use of Measure headers Route Request
according to
determine the currently available resources along a path is more
problematic, however, as following sequence of steps:

* Add an entry for every Measure sent by the originator,
the destination must send this Route Request in its cache of
(Identification, target address) values of recently received
Route Requests.

* Create a response containing the measured metrics.

If the traffic is TCP, the overhead copy of this entire packet and perform the responses are low, as
they can be piggybacked following
steps on the ACK stream. For one-way CBR traffic
though, introducing the overhead copy of a reverse stream the packet.

* Append this node's own IP address to carry the
changing metrics could be severe.

If list of Address[i]
values in the overhead Route Request, and increase the value of the responses becomes
Opt Data Len field in the Route Request by 4 (the size of an
IP address).

* This node SHOULD search its own Route Cache for a problem, route
(from itself, as if it may be
possible were the source of a packet) to implement the
target of this Route Request. If such a enhanced piggyback mechanism. The approach route is based on found in
its Route Cache, then this node SHOULD follow the fact that although no work has been exerted procedure
outlined in Section 6.2.3 to create
hop-by-hop routing information at each node, chances are good that
each node can determine return a next-hop for packets headed "cached Route Reply"
to any known
destination by simply examining its route cache. By piggybacking the Measure header for one hop onto any packet that is headed to
that next-hop, we can cheaply create a reverse flow initiator of information
that will eventually reach this Route Request, if permitted by the originator of
restrictions specified there.

* If the Measure. Each node who receives does not return a Measure cached Route Reply, then this
node SHOULD link-layer re-broadcast this copy of the packet,
with a type of return simply piggybacks short jitter delay before the Measure for one-hop on packets that seem to broadcast is sent. The
jitter period SHOULD be flowing chosen as a random period, uniformly
distributed between 0 and BROADCAST_JITTER.

6.2.3. Generating Route Replies using the
right direction back Route Cache

As described in Section 3.3.2, it is possible for a node processing a
received Route Request to avoid propagating the source. To insure Route Request further
toward the timeliness target of the information, each Measure being returned Request, if this node has in its Route Cache
a route from itself to an originator could
include this target. Such a deadline Route Reply generated by which the information is supposed to reach the
originator. If it appears that hop-by-hop propagation will result
in missing the deadline, the Measure can be unicast as
a first-class
packet node from its own cached route to the originator.

10.5. Expiration target of State from Intermediate Nodes

Since there a Route Request is no guarantee that either the source or destination of
called a packet flow will be able to communicate with all "cached Route Reply", and this mechanism can greatly reduce
the overall overhead of Route Discovery on the nodes that
carried network by reducing
the flow when they wish to terminate flood of Route Requests. The general processing of a received
Route Request is described in Section 6.2.2; this section specifies
the flow, there must additional requirements that MUST be time-based expiration mechanism by which intermediate nodes can
purge the path-state met before a cached Route
Reply may be generated and flow-state from their caches returned and reclaim specifies the
resources set aside procedure for
returning such a cached Route Reply.

While processing a received Route Request, for a node to maintain it. However, if intermediate nodes
were possibly
return a cached Route Reply, it MUST have in its Route Cache a route

Johnson, et al Expires 2 September 2001 [Page 43]

INTERNET-DRAFT The Dynamic Source Routing Protocol 2 March 2001

from itself to purge the state target of an active flow, the intermediate nodes
would find themselves with packets to forward that do not contain
a source route, but only contain this Route Request. However, before
generating a flow-identifier cached Route Reply for this Route Request, the node MUST
verify that references
state they there are no longer hold. Since intermediate nodes do not
necessarily know duplicate addresses listed in the route
accumulated in the timing Route Request together with which the sender originates packets,
an inactivity timer alone would have to route from this
node's Route Cache. Specifically, there MUST be set very conservatively to
prevent purging no duplicates among
the path-state of low bit-rate connections.

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 50]

INTERNET-DRAFT following addresses:

- The Dynamic IP Source Routing Protocol 22 October 1999

To solve the expiration problem, we take advantage Address of the relatively
``soft'' nature of packet containing the path-state and flow-state. When Route Request,

- The Address[i] fields in the state
is created, Route Request, and

- The nodes listed in the source node specifies a time after which it should
be discarded (This time will typically be on route obtained from this node's Route
Cache, excluding the order address of a hundred
seconds). The source this node can thereby estimate how often it must
refresh itself (this node
itself is the common point between the state, for example, by sending packets that contain a
full source route on them. Should accumulated in the state have somehow expired
at an intermediate node when a packet labeled with a flow or path
identifier arrives,
Route Request and the route obtained from the Route Cache).

If any duplicates exist among these addresses, then the intermediate node can return MUST NOT
send a cached Route Error Reply. The node SHOULD continue to process the source node specifying ``missing state information''
Route Request as described in Section 6.2.2.

If the cause
of the Error Route Request and elicit the sender to refresh the missing state.

Since all path-state information is guaranteed to have expired route from the network after a bounded amount of time, nodes can safely and
unambiguously reuse path- and flow-identifiers after that period.

10.6. Packet Formats

10.6.1. Identifier Option

Path and flow identifiers are carried as an option inside Route Cache meet the
restriction above, then the
Hop-by-Hop options header. This option MAY NOT appear more than once
in a single Hop-by-Hop Options header.

Option Type

???. A node that does not understand SHOULD construct and return a cached
Route Reply as follows:

- The source route for this option should ignore reply is the sequence of hops

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

where initiator is the address of the initiator of this option and continue processing Route
Request, each Address[i] is an address from the packet, Route Request,
and c-route is the Option
Data does not change en-route (the top three bits are 000).

Option Length

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

Path-ID

The identifier assigned source route to this path by
target node, obtained from the node listed as node's Route Cache. In appending
this cached route to the
IP Source Address (Section 10.2).

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 51]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

Flow-ID

The identifier assigned by source route for the reply, the address
of this node itself MUST be excluded, since it is already listed
as the IP Source
Address to Address[n].

- Send a particular flow along Route Reply to the path identified by initiator of the
Path-ID. If this portion is 0, Route Request, using
the option names a path, but not
a particular flow.

Discussion: This encoding procedure defined in Section 6.2.4. The initiator of the path and flow identifiers will cost
8 bytes of additional header overhead
Route Request is indicated in a data packet with no other
extensions or options (4 bytes for the Hop-by-Hop options header, and
4 bytes for Source Address field in the identifier option).
packet's IP header.

6.2.4. Originating a Route Reply

A more compact encoding would be
to define that, in node originates a DSR network, an IP destination address with Route Reply in order to reply to a
first octet of 127 actually encodes received and
processed Route Request, according to the path procedures described in
Sections 6.2.2 and flow identifiers 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 1 1 1 1 1 1 1| reserved | Path-ID | Flow-ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 6.2.3. The DSR module of the final destination would replace the IP
destination address with its actual value before passing the packet
up Route Reply is returned in a Route
Reply option (Section 5.3). The Route Reply option MAY be returned
to the stack for further processing.

This encoding has initiator of the advantage that it requires no additional
overhead Route Request in a data packet. separate IP packet, used

Johnson, et al Expires 2 September 2001 [Page 44]

INTERNET-DRAFT The disadvantage is that if the Dynamic Source Routing Protocol 2 March 2001

only to carry this Route Reply option, or it MAY be included in any
other IP packet
was somehow received by a DSR-unaware node without first being
processed by sent to this address.

The Route Reply option MUST be included in a DSR gateway node [4], the DSR-unaware node will either
drop header in the packet or will attempt
returned to receive it locally (since the IP
destination address belongs to initiator. To initialize the loopback subnet).

10.6.2. Path-Metrics Option

Path-metrics are carried as an option inside Route Reply option, the Hop-by-Hop options
header.

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 52]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

Option Type

???. A
node that does not understand this option should ignore
this option and continue processing the packet, and performs the Option
Data does change en-route (the top three bits are 001).

Option Length

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

Path-ID and Flow-ID steps:

- The path identifier of the path that the metrics correspond
to. If the Path-Metrics Option Type equals Measure, then the
Path-ID and Flow-ID fields MUST equal those in any Identifier
Option carried in the Hop-by-Hop Options Header.

Type

One of

Measure

Each node processing the option should update the metrics MUST be set to reflect the conditions at that node.

Reply value 3.

- The metrics Opt Data Len field in this option SHOULD NOT be modified by any
intermediate node. They represent the metrics measured
along the identified path.

Confirm

The metrics in this option MUST NOT be modified by any
intermediate node. They represent a confirmation by
the sender that will transmit traffic conforming set to the
listed Quality value
(n * 4) + 3, where n is the number of Service metrics along addresses in the identified
flow.

Metrics source
route being returned (excluding the Route Discovery initiator
node's address).

- The individual path-metrics, encoded as described Last Hop External (L) bit in
Section 10.6.4. Unknown metrics SHOULD be ignored. If a
single value is provide for the metric, it option MUST be interpreted
as the metrics value. If two values are provided for initialized
to 0.

- The Reserved field in the
metric, they option MUST be interpreted as initialized to 0.

- The Route Request Identifier MUST be initialized to the range
Identifier field of values taken
by the metric (low value first). It Route Request that this reply is undefined for there to
be more than two values for the metric.

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 53]

INTERNET-DRAFT sent in
response to.

- The Dynamic Source Routing Protocol 22 October 1999

10.6.3. Flow Request Option

Flow-requests sequence of addresses of the source route are carried as an option inside copied into
the Hop-by-Hop options
header. They allow a sender to request that intermediate nodes
reserve sufficient resources for a flow Address[i] fields of the option. Address[1] MUST be set
to provide that flow with the
QoS characteristics described by first hop of the metrics.

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 | Lifetime |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| old | old | new | new |
| Path-ID | Flow-ID | Path-ID | Flow-ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Metrics ...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Option Type

???. A node that does not understand this option should ignore
this option and continue processing route after the packet, and initiator of the Option
Data does change en-route Route
Discovery, Address[n] MUST be set to the last hop of the source
route (the top three bits are 001).

Option Length

8-bit unsigned integer. Length address of the option, target node), and each other Address[i]
MUST be set to the next address in sequence in octets,
excluding the Option Type and Option Length fields.

old Path-ID and old Flow-ID source route
being returned.

The flow identifier provide Destination Address field in the IP header of the packet carrying
the Route Reply option MUST be set to the address of the initiator
of the Route Discovery (i.e., for a previous request which Route Reply being returned in
response to some Route Request, the IP Source Address of the Route
Request).

After creating and initializing the Route Reply option and the IP
packet containing it, send the Route Reply. In sending the Route
Reply from this
request supersedes.

new Path-ID node (but not from nodes forwarding the Route Reply),
this node SHOULD delay the rely by a small jitter period chosen
randomly between 0 and new Flow-ID

The flow identifier BROADCAST_JITTER milliseconds.

If the MAC layer above which DSR is operating requires
bidirectionality for unidirectional transmissions, the Route
Reply MUST be sent by reversing the sequence of hops that will are stored
in it.

If sending a Route Reply to the originator of the Route Request
requires performing a Route Discovery, the Route Reply Option MUST

Johnson, et al Expires 2 September 2001 [Page 45]

INTERNET-DRAFT The Dynamic Source Routing Protocol 2 March 2001

be used with piggybacked on the packet that contains the Route Request. This
piggybacking prevents a loop wherein the target of the new Route
Request (which was itself the originator of the original Route
Request) must do another Route Request in order to return its Route
Reply.

If sending the Route Reply to the originator of the Route Request
does not require performing Route Discovery, a node SHOULD send a
unicast Route Reply in response to every received Route Request
targeted at it.

6.2.5. Processing a Route Reply Option

Upon receiving a Route Reply, a node SHOULD extract the source route
from the Route Reply and add this routing information to its Route
Cache. The source route from the Route Reply is the sequence of hops

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

where initiator is the value of the Destination Address field in
the IP header of the packet carrying the Route Reply (the address
of the initiator of the Route Discovery), and each Address[i] is a
node through which the source route passes, in turn, on the route to
the target of the Route Discovery. Address[n] is the address of the
target.

If the Last Hop External (L) bit is set in the Route Reply, the node
MUST flag the hop Address[n] in its Route Cache as External.

Each packet in the Send Buffer SHOULD then be checked to see whether
the information in the Route Reply and now in the Route Cache allows
it to be sent immediately.

Johnson, et al Expires 2 September 2001 [Page 46]

INTERNET-DRAFT The Dynamic Source Routing Protocol 2 March 2001

6.3. Route Maintenance Processing

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.

When forwarding a packet, a node MUST attempt to receive an
acknowledgement for the packet from the next hop. If no
acknowledgement is received, the node SHOULD return a Route Error to
the IP Source Address of the packet, as described in Section 6.3.3.
A node's algorithm for deciding whether or not to return a Route
Error MUST NOT allow any node to attempt to send an unbounded number
of packets along a broken link without receiving a Route Error.

6.3.1. Using Network-Layer Acknowledgments

When a node retransmits a packet or has no other way to ensure
successful delivery of a packet to the next hop, it MUST request a
network-layer acknowledgement by placing inserting an Acknowledgement
Request the DSR header. The Identification value contained in that
header MUST be unique over all packets delivered to the same next hop
which are either unacknowledged or recently acknowledged.

A node receiving an Acknowledgement Request MUST send an
acknowledgement to the previous hop by performing the following
sequence of steps:

- Create a packet and set the IP Source Address to the address
of this node, the IP Destination Address to the address of the
previous hop, and the IP Protocol field to the protocol number
reserved for DSR headers.

- Set the DSR header's Next Header field to be the "No Next Header"
value.

- Set the Acknowledgement option's Option Type field to 6, and the
Opt Data Len field to 10.

- Copy the Identification field from the Acknowledgement Request
option into the Identification field in the Acknowledgement
option. Set the ACK Source Address field in the option to be the
IP Source Address and the ACK Destination Address field to the IP
Destination Address.

Johnson, et al Expires 2 September 2001 [Page 47]

INTERNET-DRAFT The Dynamic Source Routing Protocol 2 March 2001

- Send the packet as described in Section 6.1.1.

6.3.2. Using Link Layer Acknowledgments

If explicit failure notifications are provided by the link layer,
then all packets are assumed to be correctly received by the
next hop, and a Route Error is sent only when an explicit failure
notification is made from the link layer.

Nodes receiving a packet without an Acknowledgement Request Option
do not need to send an explicit Acknowledgment to the packet's
originator, since the link layer will notify the originator if the
packet was not received properly.

6.3.3. Originating a Route Error

When a node is unable to verify successful delivery of a packet to
the next hop after a maximum number of retransmission attempts,
a node SHOULD send a Route Error to the IP Source Address of the
packet. In addition, a node's algorithm for deciding whether or not
to return a Route Error MUST NOT allow any node to attempt to send
an unbounded number of packets along a broken link without receiving
a Route Error. When sending a Route Error for a packet containing
either a Route Error option or an Acknowledgement option, a node
SHOULD add these options to its Route Error, subject to some limit on
lifetime. Specifically, we define the "salvage count" of an option
to identify be the
packets that should receive sum of one plus the QoS described by salvage count recorded in the included
metrics.

Metrics

The metrics that characterize Source
Route option plus the desired QoS, encoded as
described in Section 10.6.4. Unknown metrics SHOULD be
ignored. If a range sum of values are provided for the salvage counts of any Route Errors
preceding that option.

A node transmitting a metric, they Route Error MUST be interpreted as follow the minimum acceptable value following steps:

- Create a packet and set the
desired value.

Broch, Johnson, and Maltz Expires 22 April 2000 [Page 54]

INTERNET-DRAFT The Dynamic IP Source Routing Protocol 22 October 1999

10.6.4. Encoding Path-Metrics

Each path-metric is encoded in a modified Type-Length-Value form as

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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type |R| Length | Data...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Type

The type Address to the address of metric

R bit

If 0,
this node, the data is a list IP Destination Address to the address IP Source
Address of discrete values the metric can
or did take. If 1, packet experiencing the data represent error.

- Insert a range of values DSR header into the metric can or did take. If packet.

- Add a single metric value is
supplied, Route Error Option, setting the range is assumed Error Type to be 0 <= metric <= value. If
two metric values are supplied,
NODE_UNREACHABLE, the range is assumed Reserved bits to be
value1 <= metric <= value2.

Option Length

8-bit unsigned integer. Length of 0, the metric, in octets,
excluding Salvage value to
one plus the Type Salvage value from the DSR Source Route option, and Length fields.

The currently defined metric types follow:

Padding

Type: 0
the Unreachable Node Address to the address of the next hop. Set
the Error Source Address to the IP Source Address and the Error
Destination to the IP Destination Address.

- The padding metric is special in that it contains no length field node MAY append each Route Error and
no data.

Available Capacity

Type: 1

Broch, Acknowledgement
option, in order, from the packet experiencing the error,

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 55] 48]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

Data encoded as

0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Mantissa | Shift |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

where March 2001

though it MUST exclude options with salvage counts greater
than MAX_SALVAGE_TIMES.

- Send the value is (Mantissa << Shift) bits per second.

Delay and Delay Variation

Data encoded packet as

0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Delay |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Type: 2 - Delay

The value is Delay milliseconds.

Type: 3 described in Section 6.1.1.

6.3.4. Processing a Route Error Option

A node receiving a Route Error MUST process it as follows:

- Delay Variation

The value is Delete all routes from the standard deviation of Delay, in milliseconds.

Link Bidirectionality

Type: 16 Route Cache that have a link from the
Route Error Source Address to the Unreachable Node Address.

- Link Bidirectionality

Data encoded as

0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| # Uni-links | #Explicit ACK |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

where # Uni-links If the option following the Route Error is an Acknowledgement
or Route Error option sent by this node (that is, with
Acknowledgement or Error Source Address equal to this node's
address), copy the DSR options following the current Route
Error into a new packet with IP Source Address equal to this
node's own IP address and IP Destination Address equal to the
Acknowledgement or Error Destination Address. Transmit this
packet as described in Section 6.1.1, with the number salvage count in
the Source Route option set to the Salvage value of uni-directional links on the path,
and # Explicit ACK Route
Error.

6.3.5. Salvaging a Packet

When a node is unable to verify successful delivery of a packet
to the next hop after a maximum number of hops which require explicit
acknowledgments.

Broch, Johnson, retransmission attempts
and Maltz Expires 22 April 2000 [Page 56]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

Packet Loss Rate

Data encoded as

0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| # Packets Lost |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

where has transmitted a Route Error to the loss rate is (# Packets Lost / 2 ** 16).

Type: 17 - Path Packet Loss Rate

The value is sender, it MAY attempt to
salvage the expected packet loss rate by examining its route cache. If the node can
find a route to the packet's IP Destination Address in its own Route
Cache, then this node replaces the packet's Source Route option
with a new Source Route option in the same way as described in
Section 6.1.3, except that Address[1] MUST be set to the address of
this node and the entire path

Type: 18 - Worst Loss Rate

The value is Salvage field MUST be set to 1 plus the expected packet loss rate value of
the single worst link Salvage field in the path.

Broch, Source Route option that caused the error.

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 57] 49]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

11. 2 March 2001

7. Constants

BROADCAST_JITTER 10 milliseconds

MAX_ROUTE_LEN 15 nodes

Interface Indexes
IF_INDEX_INVALID 0x7F
IF_INDEX_MA 0x7E
IF_INDEX_ROUTER 0x7D

MAX_SALVAGE_TIMES 15 salvages

Route Cache
ROUTE_CACHE_TIMEOUT 300 seconds

Send Buffer
SEND_BUFFER_TIMEOUT 30 seconds

Route Request Table
MAX_REQUEST_ENTRIES 32
REQUEST_TABLE_SIZE 64 nodes
MAX_REQUEST_IDS 8
REQUEST_TABLE_IDS 16 identifiers
MAX_REQUEST_REXMT 16 retransmissions
MAX_REQUEST_PERIOD 10 seconds
REQUEST_PERIOD 500 milliseconds
RING0_REQUEST_TIMEOUT
NONPROP_REQUEST_TIMEOUT 30 milliseconds

Retransmission Buffer
DSR_RXMT_BUFFER_SIZE 50 packets

Retransmission Timer
DSR_MAXRXTSHIFT 2

Broch,

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 58] 50]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

12. IANA Considerations

This document proposes the use of the Destination Options header and
the Hop-by-Hop Options header, originally defined for IPv6, in IPv4.
The Next Header values indicating these two extension headers thus
must be reserved within the IPv4 Protocol number space.

Furthermore, this 2 March 2001

8. IANA Considerations

This document defines four new types of destination
options, each proposes the use of which must be assigned an Option Type value:

- The DSR Route Request option, described in Section 7.1.1

- The DSR Route Reply option, described in Section 7.2.1

- The DSR Route Error option, described in Section 7.2.2

- The DSR Acknowledgment option, described in Section 7.2.3 a DSR also header, which requires a routing header Routing Type be allocated for an IP
Protocol number.

In addition, this document proposes use of the
DSR Source Route value "No Next Header"
(originally defined for use in Section 7.3.

In IPv4, we require two new protocol numbers be issued IPv6) within an IPv4 packet, to identify
the next
indicate that no further header as either an IPv6-style destination option, or an
IPv6-style routing follows a DSR header. Other protocols can make use of these
protocol numbers as nodes that support them will processes any
included destination options or routing headers according to the
normal IPv6 semantics.

Broch,

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 59] 51]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

13. 2 March 2001

9. Security Considerations

This document does not specifically address security concerns. This
document does assume that all nodes participating in the DSR protocol
do so in good faith and with out without malicious intent to corrupt the
routing ability of the network. In mission-oriented environments
where all the nodes participating in the DSR protocol share a
common goal that motivates their participation in the protocol, the
communications between the nodes can be encrypted at the physical
channel or link layer to prevent attack by outsiders.

Broch,

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 60] 52]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999 2 March 2001

Appendix A. Location of DSR Functions in the ISO Network Reference Model

When designing DSR, we had to determine at what level layer within
the protocol hierarchy to implement source ad hoc network routing. We
considered two different options: routing at the link layer (ISO
layer 2) and routing at the network layer (ISO layer 3). Originally,
we opted to route at the link layer for the following several reasons:

- Pragmatically, running the DSR protocol at the link layer
maximizes the number of mobile nodes that can participate in
ad hoc networks. For example, the protocol can route equally
well between IPv4 [17], [24], IPv6 [6], [7], and IPX [7] [27] nodes.

- Historically, Historically [12, 13], DSR grew from our contemplation of
a multi-hop ARP
protocol [8, 9] and propagating version of the Internet's Address
Resolution Protocol (ARP) [22], as well as from the routing
mechanism used in IEEE 802 source routing bridges [15]. ARP [16] is a [21]. These
are layer 2 protocol. protocols.

- Technically, we designed DSR to be simple enough that that it could
be implemented directly in the firmware inside wireless network
interface cards, cards [12, 13], well below the layer 3 software within
a mobile node. We see great potential in this for DSR running between clouds
inside a cloud of mobile nodes around a fixed base stations. station,
where DSR would act to transparently fill in extend the coverage gaps between base stations. range
to these nodes. Mobile nodes that would otherwise be unable
to communicate with the base station due to factors such as
distance, fading, or local interference sources could then reach
the base station through their peers.

Ultimately, however, we decided to specify and to implement [19]
DSR as a layer 3 protocol protocol, since this is the only layer at which we
could realistically support nodes with multiple network interfaces of
different types.

Broch, types forming an ad hoc network.

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 61] 53]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999 2 March 2001

Appendix B. Implementation and Evaluation Status

We have

The DSR protocol has been implemented Dynamic Source Routing (DSR) under the FreeBSD 2.2.7
operating system running on Intel x86 platforms. FreeBSD is based
on a variety of free software, including 4.4 BSD Lite from the
University of California, Berkeley. For the environments in which
we used it, this implementation is functionally equivalent to the
protocol specified in this draft.

During the 7 months from August 1998 to February 1999, we designed
and implemented a full-scale physical testbed to enable the
evaluation of ad hoc network performance in the field. field, in a actively
mobile ad hoc network under realistic communication workloads.
The last week of February and the first week of March included
demonstrations of this testbed to a number of our sponsors and
partners, including Lucent Technologies, Bell Atlantic, and DARPA.
A complete description of the testbed is available as a Technical
Report [12]. [19].

The software is currently being was ported to FreeBSD 3.3.

Implementors notes:

- Added field to Route Error

Broch, Johnson, 3.3, and Maltz a preliminary version
of Quality of Service (QoS) support was added. A demonstration of
this modified version of DSR was presented in July 2000. Those QoS
features are not included in this draft, and will be added later in a
separate draft on top of the base protocol specified here.

The DSR protocol has been extensively studied using simulation; we
have implemented DSR in the ns-2 simulator [5, 18] and conducted
evaluations of different caching strategies documented in this
draft [9].

Several independent groups have also used DSR as a platform for their
own research, or and as a basis of comparison between ad hoc network
routing protocols.

Johnson, et al Expires 22 April 2000 2 September 2001 [Page 62] 54]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

Acknowledgments 2 March 2001

Acknowledgements

The protocol described in this draft has been designed and developed
within the CMU Monarch Project, a research project at Rice University and
Carnegie Mellon University which is developing adaptive networking
protocols and protocol interfaces to allow truly seamless wireless
and mobile node networking [10, 19]. [14, 6].

The current members authors would like to acknowledge the substantial contributions
of Josh Broch in helping to design, simulate, and implement the CMU Monarch Project
include:

- DSR
protocol. Josh is currently on leave of absence from Carnegie Mellon
University at AON Networks. We thank him for his contributions to
earlier versions of this draft.

We would also like to acknowledge the assistance of Robert V. Barron

- Josh Broch

- Yih-Chun Hu

- Jorjeta Jetcheva

- David B. Johnson

- Qifa Ke

- David A. Maltz

Broch,
at Carnegie Mellon University. Bob ported our DSR implementation
from FreeBSD 2.2.7 into FreeBSD 3.3.

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 63] 55]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999 2 March 2001

References

[1] M. Allman, V. Paxson, David F. Bantz and W. Stevens. Tcp congestion control.
Internet Request For Comments RFC 2581, April 1999. Frederic J. Bauchot. Wireless LAN design
alternatives. IEEE Network, 8(2):43--53, March/April 1994.

[2] R. Vaduvur Bharghavan, Alan Demers, Scott Shenker, and Lixia
Zhang. MACAW: A media access protocol for wireless LAN's. In
Proceedings of the ACM SIGCOMM '94 Conference, pages 212--225,
August 1994.

[3] Robert T. Braden, editor. Requirements for Internet Hosts --
Communication Layers.
hosts---communication layers. RFC 1122, October 1989.

[3]

[4] Scott Bradner. Key words for use in RFCs to Indicate
Requirement Levels. indicate
requirement levels. RFC 2119, March 1997.

[4]

[5] Josh Broch, David A. Maltz, and David B. Johnson. Supporting
Hierarchy Johnson, Yih-Chun Hu,
and Heterogeneous Interfaces in Multi-Hop Wireless
Ad Hoc Networks. Jorjeta Jetcheva. A performance comparison of multi-hop
wireless ad hoc network routing protocols. In Proceedings of
the Workshop Fourth Annual ACM/IEEE International Conference on Mobile
Computing held in conjunction with the International Symposium
on Parallel Architectures, Algorithms, and Networks, Networking, pages
370--375, Perth, Australia, June 1999.

[5] M. Scott Corson and Joe Macker. Mobile Ad hoc Networking
(MANET): Routing Protocol Performance Issues and Evaluation
Considerations howpublished = RFC 2501, month = jan, year =
1999. 85--97, October 1998.

[6] Carnegie Mellon University Monarch Project. CMU Monarch Project
Home Page. Available at http://www.monarch.cs.cmu.edu/.

[7] Stephen E. Deering and Robert M. Hinden. Internet Protocol, Protocol
version 6 (IPv6) Specification. specification. RFC 2460, December 1998.

[7] IPX Router Specification. Novell Part Number 107-000029-001,
Document Version 1.30, March 1996.

[8] Ralph Droms. Dynamic Host Configuration Protocol. RFC 2131,
March 1997.

[9] Yih-Chun Hu and David B. Johnson. Routing Caching strategies in Ad Hoc Networks
on-demand routing protocols for wireless ad hoc networks. In
Proceedings of the Sixth Annual ACM International Conference on
Mobile Computing and Networking, August 2000.

[10] IEEE Computer Society LAN MAN Standards Committee. Wireless
LAN Medium Access Control (MAC) and Physical Layer (PHY)
Specifications, IEEE Std 802.11-1997. The Institute of
Electrical and Electronics Engineers, New York, New York, 1997.

[11] Per Johansson, Tony Larsson, Nicklas Hedman, Bartosz Mielczarek,
and Mikael Degermark. Scenario-based performance analysis of
routing protocols for mobile ad-hoc networks. In Proceedings
of the Fifth Annual ACM/IEEE International Conference on Mobile Hosts.
Computing and Networking, pages 195--206, August 1999.

[12] David B. Johnson. Routing in ad hoc networks of mobile hosts.
In Proceedings of the IEEE Workshop on Mobile Computing Systems
and Applications, pages 158--163, December 1994.

[9]

Johnson, et al Expires 2 September 2001 [Page 56]

INTERNET-DRAFT The Dynamic Source Routing Protocol 2 March 2001

[13] David B. Johnson and David A. Maltz. Dynamic Source Routing in
Ad Hoc Wireless Networks.
ad hoc wireless networks. In Mobile Computing, edited by Tomasz
Imielinski and Hank Korth, chapter 5, pages 153--181. Kluwer
Academic Publishers, 1996.

[10]

[14] David B. Johnson and David A. Maltz. Protocols for Adaptive
Wireless adaptive
wireless and Mobile Networking. mobile networking. IEEE Personal Communications,
3(1):34--42, February 1996.

[11] Jian Liu

[15] John Jubin and Janet D. Tornow. The DARPA Packet Radio Network
Protocols. Proceedings of the IEEE, 75(1):21--32, January 1987.

[16] Phil Karn. MACA---A new channel access method for packet radio.
In ARRL/CRRL Amateur Radio 9th Computer Networking Conference,
pages 134--140, September 1990.

[17] Gregory S. Lauer. Packet-radio routing. In Routing in
Communications Networks, edited by Martha E. Steenstrup,
chapter 11, pages 351--396. Prentice-Hall, Englewood Cliffs,
New Jersey, 1995.

[18] David A. Maltz, Josh Broch, Jorjeta Jetcheva, and Suresh Singh. Atcp: Tcp David B.
Johnson. The effects of on-demand behavior in routing protocols
for mobile multi-hop wireless ad hoc networks. Available from web page??? Personal Communication,
June IEEE Journal on
Selected Areas of Communications, 17(8):1439--1453, August 1999.

[12]

[19] David A. Maltz, Josh Broch, and David B. Johnson. Experiences
Designing
designing and Building building a Multi-Hop Wireless Ad Hoc Network
Testbed. multi-hop wireless ad hoc network
testbed. Technical Report 99-116, CMU-CS-99-116, School of Computer
Science, Carnegie Mellon University, Pittsburgh, Pennsylvania,
March 1999.

[20] David A. Maltz, Josh Broch, Johnson, and Maltz Expires 22 April 2000 [Page 64]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999

[13] Brian D. Noble, M. Satyanarayanan, Dushyanth Narayanan,
Eric J. Tilton, Jason Flinn, and Kevin R. Walker. Agile
Application-Aware Adaptation for Mobility. In Proceedings of
the 16th ACM Symposium on Operating System Principles, pages
276--287, St. Malo, France, October 1997.

[14] Charles Perkins, editor. IP Mobility Support. RFC 2002,
October 1996.

[15] David B. Johnson. Lessons from
a full-scale multihop wireless ad hoc network testbed. IEEE
Personal Communications, 8(1):8--15, February 2001.

[21] Radia Perlman. Interconnections: Bridges and Routers.
Addison-Wesley, Reading, Massachusetts, 1992.

[16]

[22] David C. Plummer. An Ethernet address resolution protocol:
Or converting network protocol addresses to 48.bit Ethernet
addresses for transmission on Ethernet hardware. RFC 826,
November 1982.

[17]

[23] J. Postel. B. Postel, editor. Internet Control Message Protocol.
RFC 792, September 1981.

[24] J. B. Postel, editor. Internet Protocol. RFC 791, September
1981.

[18]

Johnson, et al Expires 2 September 2001 [Page 57]

INTERNET-DRAFT The Dynamic Source Routing Protocol 2 March 2001

[25] J. Postel. B. Postel, editor. Transmission Control Protocol. RFC 793,
September 1981.

[19] The CMU Monarch Project. http://www.monarch.cs.cmu.edu/.
Computer Science Department, Carnegie Mellon University.

[20] J.

[26] Joyce K. Reynolds and J. Jon Postel. Assigned Numbers. numbers. RFC 1700,
October 1994.

[21] Srinivasan Seshan, Mark Stemm, and Randy H. Katz. Spand:
Shared passive network performance discovery. In Proceedings of
the USENIX Symposium on Internet Technologies and Systems, See also http://www.iana.org/numbers.html.

[27] Paul Turner. NetWare communications processes. NetWare
Application Notes, Novell Research, pages
135--146, dec 1997.

[22] W. Richard Stevens. TCP/IP IIlustrated, The Protocols,
volume 1. Addison-Welsley, 1994.

[23] Andrew S. Tannenbaum. Computer Networks. Prentice Hall, third
edition, 1996.

[24] Gary R. Wright and W. Richard Stevens. TCP/IP IIlustrated, The
Implementation, volume 2. Addison-Welsley, 1995.

Broch, 25--91, September
1990.

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 65] 58]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999 2 March 2001

Chair's Address

The MANET Working Group can be contacted via its current chairs:

M. Scott Corson Phone: +1 301 405-6630
Institute for Systems Research Email: corson@isr.umd.edu
University of Maryland
College Park, MD 20742
USA

Phone: +1 301 405-6630
Email: corson@isr.umd.edu

Joseph Macker Phone: +1 202 767-2001
Information Technology Division Email: macker@itd.nrl.navy.mil
Naval Research Laboratory
Washington, DC 20375
USA

Phone: +1 202 767-2001
Email: macker@itd.nrl.navy.mil

Broch,

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 66] 59]

INTERNET-DRAFT The Dynamic Source Routing Protocol 22 October 1999 2 March 2001

Authors' Addresses

Questions about this document can also be directed to the authors:

Josh Broch
Carnegie Mellon

David B. Johnson Phone: +1 713 348-3063
Rice University
Electrical and Fax: +1 713 348-5930
Computer Engineering
5000 Forbes Avenue
Pittsburgh, PA 15213-3890 Science Department, MS 132 Email: dbj@cs.rice.edu
6100 Main Street
Houston, TX 77005-1892
USA

David A. Maltz Phone: +1 412 268-3056 650 688-3128
AON Networks Fax: +1 412 268-7196 650 688-3119
3045 Park Blvd. Email: broch@cs.cmu.edu

David B. Johnson
Carnegie Mellon University
Computer Science Department
5000 Forbes Avenue
Pittsburgh, PA 15213-3891 dmaltz@cs.cmu.edu
Palo Alto, CA 94306
USA

Yih-Chun Hu Phone: +1 412 268-7399 268-3075
Rice University Fax: +1 412 268-5576
Computer Science Department, MS 132 Email: dbj@cs.cmu.edu

David A. Maltz yihchun@cs.cmu.edu
6100 Main Street
Houston, TX 77005-1892
USA

Jorjeta G. Jetcheva Phone: +1 412 268-3053
Carnegie Mellon University Fax: +1 412 268-5576
Computer Science Department Email: jorjeta@cs.cmu.edu
5000 Forbes Avenue
Pittsburgh, PA 15213-3891
USA

Phone: +1 412 268-3621
Fax: +1 412 268-5576
Email: dmaltz@cs.cmu.edu

Broch,

Johnson, and Maltz et al Expires 22 April 2000 2 September 2001 [Page 67] 60]
----