wdiff draft-ietf-manet-dsr-03.txt draft-ietf-manet-dsr-04.txt

IETF MANET Working Group Josh Broch
INTERNET-DRAFT David B. Johnson Johnson, Rice University
INTERNET-DRAFT David A. Maltz Maltz, AON Networks
17 November 2000 Yih-Chun Hu, Carnegie Mellon 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-04.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.

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. in multi-hop wireless ad hoc networks.

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 12
3.4.1. Packet Salvaging . . . . . . . . . . . . . . . . 12
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. 19

5. Packet Formats 11
7.1. 20
5.1. Destination Options Headers Header . . . . . . . . . . . . . . . 11
7.1.1. 21
5.1.1. DSR Route Request Option . . . . . . . . . . . . 12
7.2. 22
5.2. Hop-by-Hop Options Headers Header . . . . . . . . . . . . . . . 14
7.2.1. . 24
5.2.1. DSR Route Reply Option . . . . . . . . . . . . . 15
7.2.2. 25
5.2.2. DSR Route Error Option . . . . . . . . . . . . . 17
7.2.3. 27
5.2.3. DSR Acknowledgment Option . . . . . . . . . . . . 18
7.3. 29
5.3. DSR Routing Header . . . . . . . . . . . . . . . . . . . 20

8. 30

6. Detailed Operation 23
8.1. Originating a Data 33
6.1. General Packet Processing . . . . . . . . . . . . . . . . 23
8.2. 33
6.1.1. Originating a Packet with a DSR Routing Header . . . . . 23
8.3. Processing . . . . . . . . . 33
6.1.2. Adding a DSR Routing Header to a Packet . . . . . 34
6.1.3. Receiving a Packet . . . . . . . . . . 24
8.4. Route Discovery . . . . . . 36
6.1.4. Processing a Routing Header in a Received Packet 38
6.2. Route Discovery Processing . . . . . . . . . . . . . . . 25
8.4.1. 40
6.2.1. Originating a Route Request . . . . . . . . . . . 25
8.4.2. 40
6.2.2. Processing a Received Route Request Option . . . . . . . . 26
8.4.3. 42
6.2.3. Generating Route Replies using the Route Cache . 27
8.4.4. 43
6.2.4. Originating a Route Reply . . . . . . . . . . . . 28
8.4.5. 45
6.2.5. Processing a Route Reply Option . . . . . . . . . 29
8.5. 46
6.3. Route Maintenance Processing . . . . . . . . . . . . . . . . . . . . 30
8.5.1. 47
6.3.1. Using Network-Layer Acknowledgments . . . . . . . 30
8.5.2. 47
6.3.2. Using Link Layer Acknowledgments . . . . . . . . 32
8.5.3. 48
6.3.3. Originating a Route Error . . . . . . . . . . . . 32
8.5.4. 48
6.3.4. Processing a Route Error Option . . . . . . . . . 33
8.5.5. 49
6.3.5. Salvaging a Packet . . . . . . . . . . . . . . . 33 49

7. Constants 50

8. IANA Considerations 51

9. Optimizations 35
9.1. Leveraging the Route Cache . . . . . . . . . . . . . . . 35
9.1.1. Promiscuous Learning Security Considerations 52

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

Appendix B. Implementation and Evaluation Status 54

Acknowledgements 55

References 56

Chair's Address 59

Authors' Addresses 60

1. Introduction

The Dynamic Source Routes . . . . . . 35
9.2. Preventing Route Reply Storms . . . . . . . . . . . . . . 36
9.3. Piggybacking on Route Discoveries . . . . . . . . . . . . 37
9.4. Discovering Shorter Routes . . . . . . . . . . . . . . . 37
9.5. Rate Limiting the Route Discovery Process . . . . . . . . 38
9.6. Improved Handling of Route Errors . . . . . . . . . . . . 39
9.7. Increasing Scalability . . . . . . . . . . . . . . . . . 39

10. Path-State and Flow-State Mechanisms 40
10.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 40
10.2. Path-State and Flow-State Identifiers . . . . . . . . . . 41
10.3. Path-State Creation, Use, and Maintenance . . . . . . . . 42
10.3.1. Creating Path-State for Routing . . . . . . . . . 42
10.3.2. Monitoring Characteristics of the Path . . . . . 43
10.3.3. Candidate Metrics . . . . . . . . . . . . . . . . 45
10.4. Flow-State Creation, Use, 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 . . . . . . . . . . . . . . . 54
10.6.4. Encoding Path-Metrics . . . . . . . . . . . . . . 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

Chair's Address 66

Authors' Addresses 67

1. Introduction

This document describes Dynamic Source Routing (DSR) [8, 9], a
protocol developed by the Monarch Project [10, 19] at Carnegie Mellon
University for routing packets in a mobile ad hoc network [5].

Source routing is a routing technique in which the sender of a packet
determines the complete sequence of nodes through which to forward
the packet; the sender explicitly lists this route in the packet's
header, identifying each forwarding "hop" by the address of the next
node to which to transmit the packet on its way to the destination
node.

DSR offers a number of potential advantages over other routing
protocols for mobile ad hoc networks. First, DSR uses no periodic
routing messages of any kind (e.g., no router advertisements and no
link-level neighbor status messages), thereby significantly reducing
network bandwidth overhead, conserving battery power, reducing the
probability of packet collision, 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
such as node movement, yet requires no routing protocol overhead
during periods in which no such changes occur.

In addition, DSR has been designed to compute correct routes in
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, or the
intentional use of asymmetric communication technology such as
satellites. Due to the existence of asymmetric links, traditional
link-state or distance vector protocols may compute routes that do
not work. DSR, however, will always find a correct route even in the
presence of asymmetric links.

2. Changes

Changes from version 02 to version 03 (10/1999)

- Added description of path-state and flow-state maintenance
(Section 10). These extensions remove the need for every
data packet to carry a source route, thereby decreasing
the byte-overhead of DSR. They also provide a framework for
supporting QoS inside DSR networks.

3. Assumptions

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

We refer to the minimum number of hops necessary for a packet to
reach from any node located at one extreme edge of the network to
another node located at the opposite extreme, as the diameter of the
network. We assume that the diameter of an 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 the wireless
network. A node receiving 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 to
deliver every received packet to the network driver software without
filtering based on link-layer destination address. Although we do
not require this facility, it is for example common in current LAN
hardware for broadcast media including wireless, and some of our
optimizations take advantage of its availability. Use of promiscuous
mode does increase the software overhead on 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
that portions of the protocol are also suitable for implementation
directly within a programmable network interface unit to avoid this
overhead on the CPU.

4. Terminology

4.1. General Terms

link

A communication facility 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 to a link.

prefix

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

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 for use by Mobile IP [14]
mobility agents (home or foreign agents) to indicate that they
believe they can reach a destination via a connected internet
infrastructure. The index IF_INDEX_ROUTER is reserved for
use by routers not acting as Mobile IP mobility agents to
indicate that they believe they can reach the destination via a
connected internet infrastructure.

The distinction between the index for mobility agents and
the index for routers, allows mobility agents to advertise
their existence ``for free''. A node that processes a routing
header listing the interface index IF_INDEX_MA, can then send
a unicast Agent Solicitation to the corresponding address in
the routing header to obtain complete information about 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 of data in
the same packet so that all data elements move through 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 of where
the node is attached to the Internet [14]. If a node has more
than one home address, it SHOULD select and use 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
of home addresses and interface indexes that contains all the
information that would be needed to forward a packet through
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, and the address of
the node which is intended to receive the packet.

DSR Routing Headers as described in Section 7.3 use a more
compact encoding of the source route and do not explicitly list
address S in the Routing Header`, since it is carried as the IP
Source Address 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
packets through the network to D. Performing a Route Discovery
involves sending one or more Route Request packets.

Route Maintenance

The process in DSR of monitoring the status of a source route
while in use, so that any link-failures along the source route
can be detected and the broken link removed from use.

4.2. Specification Language

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

5. Protocol Overview

5.1. Route Discovery and Route Maintenance

A source routing Routing protocol must solve two challenges, which DSR terms
Route Discovery and Route Maintenance. Route Discovery is the
mechanism whereby a node S wishing to send a packet to a destination
D obtains a source route to D.

Route Maintenance is the mechanism whereby S (DSR) [12, 13] is able to detect, while
using a source route to D, if the network topology has changed such
that it can no longer simple and
efficient routing protocol designed specifically for use its route to D because a link along in multi-hop
wireless ad hoc networks of mobile nodes. Using DSR, the
route no longer works. When Route Maintenance indicates a source
route network
is broken, S can attempt completely self-organizing and self-configuring, requiring no
existing network infrastructure or administration. Network nodes
cooperate to use any forward packets for each other route it happens to
know to D, or can invoke Route Discovery again to find a new route.

To perform Route Discovery, the source node S link-layer broadcasts
a Route Request packet. Here, node S is termed the initiator allow communication
over multiple "hops" between nodes not directly within wireless
transmission range of one another. As nodes in the
Route Discovery, and the node to which S is attempting to discover a
source route, say D, is termed network move
about or join or leave the target network, and as wireless transmission
conditions such as sources of interference change, all routing is
automatically determined and maintained by the Discovery.

Each node that hears DSR routing protocol.
Since the Route Request packet forwards a copy number or sequence of intermediate hops needed to reach any
destination may change at any time, the
Request, if appropriate, by adding its own address resulting network topology
may be quite rich and rapidly changing.

The DSR protocol allows nodes to dynamically discover a source
route
being recorded across multiple network hops to any destination in the Request ad hoc
network. Each data packet and sent then rebroadcasting the
Route Request.

The forwarding of Route Requests is constructed so that copies of the
Request propagate hop-by-hop outward from the node initiating the
Route Discovery, until either carries in its header the target
complete, ordered list of nodes through which the Request is found or
until another node is found that can supply a route packet will pass,
allowing packet routing to be trivially loop-free and avoiding the target.

The basic mechanism of forwarding Route Requests forwards the Request
if the node (1) is not
need for up-to-date routing information in the target of intermediate nodes
through which the Request, (2) packet is not already
listed in the recorded forwarded. By including this source
route in this copy of the Request, 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 such a Route Request, since header of each Route Request packet contains
a unique identifier for this Route Discovery, generated by the
initiator data packet, other nodes forwarding or
overhearing any of the Discovery. Each node maintains an LRU these packets may also easily cache of this routing
information for future use.

In designing DSR, we sought to create a routing protocol that had
very low overhead yet was able to react quickly to changes in the
unique identifier from each recently received Route Request. By not
propagating any copies
network. The DSR protocol provides highly reactive service to help
ensure successful delivery of a Request after the first, the overhead data packets in spite of
forwarding additional copies that reach this node along different
paths movement
or other changes in network conditions.

The DSR protocol is avoided.

In addition, composed of two mechanisms that work together to
allow the Time-to-Live field discovery and maintenance of source routes in the IP header of ad hoc
network:

- Route Discovery is the mechanism by which a node S wishing to
send a packet
carrying the to a destination node D obtains a source route
to D. Route Request MAY be Discovery is used only when S attempts to limit send a
packet to D and does not already know a route to D.

- Route Maintenance is the scope over mechanism by which
the Request will propagate, node S is able
to detect, while using a source route to D, if the normal behavior of Time-to-Live
defined by IP [17, 2]. Additional optimizations on network
topology has changed such that it can no longer use its route
to D because a link along the handling and
forwarding of route no longer works. When Route Requests are also
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 further reduce the D.

In DSR, Route Discovery overhead.

When the target of the Request (e.g., node D) receives the and Route
Request, Maintenance each operate entirely
"on demand". In particular, unlike other protocols, DSR requires no
periodic packets of any kind at any level within the recorded source route network. For
example, DSR does not use any periodic routing advertisement, link
status sensing, or neighbor detection packets, and does not rely on
these functions from any underlying protocols in the Request identifies the
sequence network. This
entirely on-demand behavior and lack of hops over which this copy periodic activity allows
the number of overhead packets caused by DSR to scale all the Request reached D.
Node D copies this recorded source route into a Route Reply packet way
down to zero, when all nodes are approximately stationary with
respect to each other and sends this Route Reply back all routes needed for current communication
have already been discovered. As nodes begin to move more or
as communication patterns change, the initiator routing packet overhead of
DSR automatically scales to only that needed to track the Route Request
(e.g., node S).

All source routes learned by a node are kept
currently in a Route Cache, which
is used to further reduce use. Network topology changes not affecting routes
currently in use are ignored and do not cause reaction from the cost of Route Discovery. When a node
wishes
protocol.

In response to send a packet, it examines its own Route Cache and performs single Route Discovery only if no suitable source route is found in its
Cache.

Further, when some intermediate node B receives a Route Request (as well as through routing
information 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 other packets overheard), a route, it might not have node may learn and cache
multiple routes to propagate any destination. This allows the Route Request, but instead return a Route Reply reaction to
routing changes to be much more rapid, since a node S based on with multiple
routes to a destination can try another cached route if the concatenation one it
has been using should fail. This caching of multiple routes also
avoids the recorded source route from
S overhead of needing to B in the perform a new Route Request and the cached Discovery each
time a route from B to D. in use breaks.

The
details operation of replying from a both Route Cache Discovery and Route Maintenance in this way DSR
are discussed designed to allow uni-directional links and asymmetric routes
to be easily supported. In particular, as noted in Section 9.1.

As 2, in
wireless networks, it is possible that a node overhears routes being used by others, either on data
packets link between two nodes may
not work equally well in both directions, due to differing antenna
or on control packets used by Route Discovery propagation patterns or Route
Maintenance, sources of interference. DSR allows such
uni-directional links to be used when necessary, improving overall
performance and network connectivity in the node MAY insert those routes into its Route Cache,
leveraging system.

This document specifies the Route Discovery operations operation of the DSR protocol for routing
unicast IP packets in multi-hop wireless ad hoc networks. Advanced,
optional features, such as Quality of Service (QoS) support and
efficient multicast routing, are covered in other nodes documents. The
specification of DSR in
the network. Such route information MAY this document provides a compatible base
on which such features can be learned added, either by
promiscuously snooping on packets independently or when forwarding packets.

5.2. Packet Forwarding

To represent a source route within a packet's header, by
integration with the DSR uses a
Routing Header similar operation specified here.

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

2. Assumptions

We assume that all nodes wishing to communicate with other nodes
within the Routing Header format specified for
IPv6, adapted ad hoc network are willing to participate fully in the needs
protocols of DSR and to the use of DSR in IPv4 (or
in IPv6 network. In particular, each node participating in
the future). The DSR Routing Header uses a unique Routing
Type field value network SHOULD also be willing to distinguish it from the existing Type 0 Routing
Header defined within IPv6 [6].

To forward a packet, a receiving node N simply processes the Routing
Header as specified packets for other nodes
in Section 8.3 and transmits the packet to network.

The diameter of an ad hoc network is the next hop. If minimum number of hops
necessary for a forwarding error occurs along the link packet to the
next hop in the route, this reach from any node N sends a Route Error back located at one extreme
edge of the ad hoc network to another node located at the
originator S of this packet informing S opposite
extreme. We assume that this link is "broken".
If diameter will often be small (e.g.,
perhaps 5 or 10 hops), but may often be greater than 1.

Packets may be lost or corrupted in transmission on the wireless
network. We assume that a node N's Route Cache contains receiving a different route to the destination
of the original packet, then the corrupted packet is salvaged using can
detect the new
source route (Section 8.5.5). Otherwise, error and discard the packet is dropped.

Each node overhearing or forwarding a Route Error packet also
removes from its Route Cache packet.

Nodes within the ad hoc network MAY move at any time without notice,
and MAY even move continuously, but we assume that the link indicated speed with
which nodes move is moderate with respect to be broken, thereby
cleaning the stale cache data from packet transmission
latency and wireless transmission range of the network.

5.3. Multicast Routing

At this time particular underlying
network hardware in use. In particular, DSR does not support true multicasting. However, it
does can support very
rapid rates of arbitrary node mobility, but we assume that nodes do
not continuously move so rapidly as to make the controlled flooding of a every
individual data packet the only possible routing protocol.

A common feature of many network interfaces, including most current
LAN hardware for broadcast media such as wireless, is the ability
to all nodes operate the network interface in "promiscuous" receive mode.
This mode causes the hardware to deliver every received packet to
the network that are within driver software without filtering based on link-layer
destination address. Although we do not require this facility, some number
of hops our optimizations can take advantage of the originator.
While this mechanism does not support pruning its availability. Use
of promiscuous mode does increase the broadcast
tree to conserve software overhead on the CPU,
but we believe that wireless network resources, it can be used to distribute
information speeds are more the inherent
limiting factor to nodes performance in current and future systems; we also
believe that portions of the network.

When an application on a DSR node sends protocol are suitable for implementation
directly within a packet programmable network interface unit to a multicast
address, DSR piggybacks the data from the packet inside a Route
Request packet targeted at the multicast address. The normal Route
Request distribution scheme described in Sections 5.1 and 8.4.2
will result in avoid this packet being efficiently distributed to all
nodes in
overhead on the network within CPU [13]. Use of promiscuous mode may also increase
the specified TTL power consumption of the originator.
The receiving nodes can then do destination address filtering network interface hardware, depending
on the packet, discarding it if they do not wish to receive multicast
packets destined to this multicast address.

6. Conceptual Data Structures

In order to participate in design of the Dynamic Source Routing Protocol, a
node needs four conceptual data structures: a Route Cache, a Route
Request Table, a Send Buffer, receiver hardware, and a Retransmission Buffer. These
data structures MAY be implemented in any manner consistent with the
external behavior described in this document.

6.1. Route Cache

All routing information needed by a node participating in an ad hoc
network using such cases, DSR is stored in a Route Cache. Each node in can
easily be used without the
network maintains its own Route Cache. The node adds information optimizations that depend on promiscuous
receive mode, or can be programmed to only periodically switch the Cache as it learns
interface into promiscuous mode. Use of new links promiscuous receive mode is
entirely optional.

Wireless communication ability between any pair of nodes can at
times not work equally well in the ad hoc
network, both directions, due for example through packets carrying either a Route Reply to
differing antenna or
a Routing Header. Likewise, the node removes information from the
cache as it learns existing links in the ad hoc network have broken,
for example through packets carrying a Route Error propagation patterns or through sources of interference
around the
link-layer retransmission mechanism reporting a failure two nodes [1, 17]. That is, wireless communications
between each pair of nodes will in forwarding
a packet to its next-hop destination. The Route Cache is indexed
logically by destination node address, and supports the following
operations:

void Insert(Route RT)

Inserts information extracted from source route RT into many cases be able to operate
bi-directionally, but at times the
Route Cache.

Route Get(Node DEST)

Returns a source route from this wireless link between two nodes
may be only uni-directional, allowing one node to DEST (if one successfully send
packets to the other while no communication is
known).

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

Removes from possible in the route cache any routes which assume that a
packet transmitted by node FROM
reverse direction. Although many routing protocols operate correctly
only over its interface with the
given INDEX will be received by node TO.

Each implementation MAY choose the cache replacement bi-directional links, DSR can successfully discover and cache search
strategies for its Route Cache
forward packets over paths that are most appropriate for its
particular network environment. For example, some environments may
choose 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 return the shortest route required bi-directional exchange of RTS and CTS
packets in these protocols and due to a node (the shortest sequence the link-level acknowledgement
feature in IEEE 802.11; when used on top of hops), while others may select an alternate metric for MAC protocols such as
these, DSR can take advantage of additional optimizations, such as
the Get()
operation.

The Route Cache SHOULD support storing more than one easy ability to reverse a source route for
each destination.

If there are multiple cached routes to obtain a destination, route back to
the Route Get()
operation SHOULD prefer routes that do not traverse a hop with an
interface index origin of IF_INDEX_MA or IF_INDEX_ROUTER. This will prefer
routes that lead directly to the target original route.

The IP address used by a node over routes that attempt
to reach using the target via DSR protocol MAY be assigned
by any internet infrastructure connected to mechanism (e.g., static assignment or use of DHCP for dynamic
assignment [8]), although the method of such assignment is outside
the
ad hoc network.

If a scope of this specification.

3. DSR Protocol Overview

3.1. Basic DSR Route Discovery

When some node S is using originates a source route new packet destined to some destination D that
includes intermediate other
node N, S SHOULD shorten the route to
destination D when D, it learns places in the header of the packet a shorter source route to node N than giving
the
one sequence of hops that is listed as the prefix of packet is to follow on its current route way to
D.

A node Normally, S using will obtain a suitable source route to destination D through intermediate
node N, MAY shorten the source route by searching
its "Route Cache" of routes previously learned, but if no route is
found in its cache, it learns of a shorter path
from node N to node D.

The will initiate the Route Cache replacement policy SHOULD allow routes Discovery protocol
to be
categorized based upon "preference", where routes with dynamically find a higher
preferences are less likely new route to be removed from D. In this case, we call S the cache.
"initiator" and D the "target" of the Route Discovery.

For example, suppose a node could prefer routes for which it initiated A is attempting to discover a route to
node E. The Route Discovery over routes that it learned 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 result of promiscuous
snooping on other packets. In particular, a Route Discovery, node SHOULD prefer
routes that it is presently using over those that it A transmits a "Route Request"
message as a single local broadcast packet, which is not.

6.2. received by
(approximately) all nodes currently within wireless transmission
range of A, including node B in this example. Each Route Request Table

The
message identifies the initiator and target of the Route Request Table is Discovery,
and also contains a collection unique request identification (2, in this
example), determined by the initiator of records about the Request. Each
Route Request packets that were recently originated or forwarded by also contains a record listing the address of each
intermediate node through which this
node. The table particular copy of the Route
Request message has been forwarded. This route record is indexed initialized
to an empty list by the home address initiator of the target of Route Discovery. In this
example, the route discovery. A record maintained on initially lists only node S for A.

When another node D contains
the following:

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

- The remaining amount Request (such as node B in this
example), if it is the target of time that S must wait before the next
attempt at a Route Discovery for D.

- The Time-to-live (TTL) field in Discovery, it returns
a "Route Reply" message to the IP header initiator of last the Route
Request originated by S for D.

- A FIFO cache Discovery,
giving a copy of the last ID_FIFO_SIZE Identification values accumulated route record from the Route Request packets targeted at node D that were forwarded by Request;
when the initiator receives this node.

Nodes SHOULD Route Reply, it caches this route
in its Route Cache for use an LRU policy in sending subsequent packets to manage this
destination. Otherwise, if this node receiving the entries of in their Route Request Table.

ID_FIFO_SIZE MUST NOT be set to an unlimited value, since,
has recently seen another Route Request message from this initiator
bearing this same request identification and target address, or if it
finds that its own address is already listed in the
worst case, when a node crashes and reboots route record in
the first ID_FIFO_SIZE Route Request packets message, it sends may appear to be duplicates discards the Request. Otherwise, this
node appends its own address to the
other nodes route record in the network.

6.3. Send Buffer

The Send Buffer of some node is a queue of packets that cannot be
transmitted Route Request
message and propagates it by that node because transmitting it does not yet have as a source
route to each respective packet's destination. Each local broadcast
packet in (with the
Send Buffer is stamped with same request identification). In this example,
node B broadcast the time that it Route Request, which is placed into the
Buffer, received by node C;
nodes C and SHOULD be removed from D each also broadcast the Send Buffer and discarded
SEND_BUFFER_TIMEOUT seconds after initially being placed Request in turn, resulting in the
Buffer. If necessary, a FIFO strategy SHOULD be used to evict
packets before they timeout to prevent
copy of the buffer from overflowing.

Subject Request being received by node E.

In returning the Route Reply to the rate limiting defined in Section 8.4, a initiator of the Route
Discovery SHOULD be initiated as often Discovery,
such as possible node E replying back to A in this example, node E will
typically examine its own Route Cache for a route back to A, and if
found, will use it for the
destination address source route for delivery of any packets residing in the Send Buffer.

6.4. Retransmission Buffer

The Retransmission Buffer of a packet
containing the Route Reply. Otherwise, E SHOULD perform its own
Route Discovery for target node A, but to avoid possible infinite
recursion of Route Discoveries, it MUST piggyback this Route Reply on
its own Route Request message for A.

It is also possible to piggyback other small data packets, such as a queue of packets sent by
TCP SYN packet [26], on a Route Request using this node that are awaiting same mechanism.
Node E could also simply reverse the receipt sequence of an acknowledgment from hops in the
next hop route
record that it is trying to send in the Route Reply, and use this
as the source route (Section 7.3).

For each on the packet in carrying the Retransmission Buffer, a node maintains (1) Route Reply itself.
For MAC protocols such as IEEE 802.11 that require a
count bi-directional
frame exchange as part of the number MAC protocol [10], this route reversal
is preferred as it avoids the overhead of retransmissions a possible second Route
Discovery, and (2) it tests the time of discovered route to ensure it is
bi-directional before the last
retransmission.

Packets are removed from Route Discovery initiator begins using the buffer when an acknowledgment
is received, or when
route. However, this technique will prevent the number discovery of retransmissions exceeds
DSR_MAXRXTSHIFT. routes
using uni-directional links. In wireless environments where the later case, the removal use
of uni-directional links is permitted, such routes may in some cases
be more efficient than those with only bi-directional links, or they
may be the packet from only way to achieve connectivity to the Retransmission Buffer SHOULD result in target node.

When initiating a Route Error being
returned to Discovery, the initial source sending node saves a copy of
the original packet (Section 8.5).

7. Packet Formats

Dynamic Source Routing makes use in a local buffer called the "Send Buffer". The
Send Buffer contains a copy of four options carrying control
information each packet that can cannot be piggybacked transmitted
by this node because it does not yet have a source route to the
packet's destination. Each packet in any existing IP packet.

The mechanism used for these options the Send Buffer is based on stamped with
the design of time that it was placed into the
Hop-by-Hop Buffer and Destination Options mechanisms is discarded after
residing in IPv6 [6]. The
ability to generate and process such options must be added to an IPv4
protocol stack. Specifically, the Protocol field in Send Buffer for some timeout period; if necessary
for preventing the IP header
is Send Buffer from overflowing, a FIFO or other
replacement strategy MAY also be used to indicate that evict packets before they
expire.

While a Hop-by-Hop Options or Destination Options
extension header exists between packet remains in the IP header and Send Buffer, the remaining
portion of node SHOULD
occasionally initiate a new Route Discovery for the packet's payload (such as a transport layer header).
The Next Header field in each extension header will then indicate
destination address. However, the
type of header that follows node MUST limit the rate at which
such new Route Discoveries for the same address are initiated, since
it in a packet.

7.1. Destination Options Headers

The Destination Options header is used to carry optional information possible that need be examined only by a packet's the destination node(s). The
Destination Options header node is identified by a Next Header (or
Protocol) value of 60 in not currently reachable.
In particular, due to the immediately preceding header, limited wireless transmission range and has the following format:

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

Next Header

8-bit selector. Identifies
movement of the type nodes in the network, the network may at times become
partitioned, meaning that there is currently no sequence of header immediately
following nodes
through which a packet could be forwarded to reach the Destination Options header. Uses destination.
Depending on the same values
as movement pattern and the IPv4 Protocol field [20].

Hdr Ext Len

8-bit unsigned integer. Length density of the Destination Options
header nodes in 4-octet units, not including the first 8 octets.

Options

Variable-length field, of length
network, such that the complete
Destination Options header is an integer multiple of 4 octets
long. Contains one network partitions may be rare or more TLV-encoded options.

The following destination option is used by the Dynamic Source
Routing protocol:

- DSR may be common.

If a new Route Request option (Section 7.1.1)

This destination option MUST NOT appear multiple times within Discovery was initiated for each packet sent by a
single Destination Options header.

7.1.1. DSR
node in such a situation, a large number of unproductive Route
Request Option

The DSR packets would be propagated throughout the subset of the
ad hoc network reachable from this node. In order to reduce the
overhead from such Route Request destination 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| 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:

Source Address Discoveries, a node MUST be use an exponential
back-off algorithm to limit the home address of rate at which it initiates new Route
Discoveries for the same target. If the node originating attempts to send
additional data packets to this packet.
Intermediate nodes that repropagate the request do not change same node more frequently than this field.

Destination Address

MUST be
limit, the limited broadcast address (255.255.255.255).

Hop Limit (TTL)

Can subsequent packets SHOULD be varied from 1 buffered in the Send Buffer
until a Route Reply is received giving a route to 255, this destination,
but the node MUST NOT initiate a new Route Discovery until the
minimum allowable interval between new Route Discoveries for example this
target has been reached. This limitation on the maximum rate of
Route Discoveries for the same target is similar to implement
expanding-ring searches. 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 Request fields:

Option Type

???. A Maintenance

When originating or forwarding a packet using a source route, each
node transmitting the packet is responsible for confirming that does not understand the
packet has been received by the next hop along the source route; the
packet SHOULD be retransmitted (up to a maximum number of attempts)
until this option MUST discard confirmation of receipt is received. For example, in the
situation shown below, node A has originated a packet for node E
using a source route through intermediate nodes B, C, and D:

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

In this case, node A is responsible for receipt of the 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 Option Data
destination E.

This confirmation of receipt in many cases may change en-route (the top
three bits are 011).

Option Length

8-bit unsigned integer. Length be provided at no cost
to DSR, either as an existing standard part of the option, MAC protocol in octets,
excluding
use (such as the Option Type and Option Length fields.

Identification

A unique value generated link-level acknowledgement frame defined by IEEE
802.11 [10]), or by the initiator (original sender)
of the Route Request. This value allows a recipient "passive acknowledgement" [15] (in which, for
example, B confirms receipt at C by overhearing C transmit the packet
to
determine whether or not forward it has recently seen this a copy on to D). If neither of
this Request; if it has, these confirmation mechanisms
are available, the node transmitting the packet is simply discarded. When
propagating can explicitly
request a Route Request, this field MUST DSR-specific software acknowledgement be copied from returned by the
received copy of
next hop; this software acknowledgement will normally be transmitted
directly to the Request being forwarded.

Target Address

The home address of sending node, but if the node that link between these two nodes
is the target of the Route
Request.

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

A flag associated with each interface index that indicates
whether or not the corresponding node repropagated the Request uni-directional, this software acknowledgement may travel over a different physical interface type than over which it
different, multi-hop path.

If no receipt confirmation is received after the Request.

IN Index[1..n]

IN Index[i] is packet has been
retransmitted the index maximum number of the interface over which the node
indicated attempts by Address[i] received the Route Request option.
These are used to record some hop, this node
SHOULD return a reverse route from "Route Error" message to the target original sender of the request to
packet, identifying the originator, link over which a Route Reply MAY be
sent.

OUT Index[1..n]

OUT Index[i] is the interface index that the node indicated by
Address[i-1] used when rebroadcasting packet could not be
forwarded. For example, in the Route Request option.

Address[1..n]

Address[i] example shown above, if C is unable
to deliver the home address of packet to the ith next hop recorded in the D, then C returns a Route Request option.

7.2. Hop-by-Hop Options Headers

The Hop-by-Hop Options header is used Error
to carry optional information A, stating that must be examined by every node along a packet's delivery path.
The Hop-by-Hop Options header the link from C to D is identified by a Next Header (or
Protocol) value currently "broken". Node
A then removes this broken link from its cache; any retransmission
of ??? in the IP header, and original packet can be performed by upper layer protocols
such as TCP, if necessary. For sending such a retransmission or
other packets to this same destination E, if A has in its Route Cache
another route to E (for example, from additional Route Replys from
its earlier Route Discovery, or from having overheard sufficient
routing information from other packets), it can send the following
format:

Next Header

8-bit selector. Identifies the type of header immediately
following the Hop-by-Hop Options header. Uses the same values
as packet
using the IPv4 Protocol field [20].

Hdr Ext Len

8-bit unsigned integer. Length of new route immediately. Otherwise, it SHOULD perform a new
Route Discovery for this target (subject to the Hop-by-Hop Options
header exponential back-off
described in 4-octet units, not including 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 first 8 octets.

Options

Variable-length field, of length such
routing information from that packet to its own Route Cache. In
particular, 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 source route used by in a data packet, the Dynamic Source
Routing protocol:

- DSR Route Reply option (Section 7.2.1)

- DSR accumulated
route record in a Route Error option (Section 7.2.2)

- DSR Acknowledgment option (Section 7.2.3)

All of these destination options MAY appear one Request, or more times within the route being returned in a single Hop-by-Hop Options header.

7.2.1. DSR Route Reply Option

The DSR
Route Reply hop-by-hop option MAY all be cached by any node. Routing information from
any of these packets received can be cached, whether the packet
was addressed to this node, sent to a broadcast (or multicast)
MAC address, or received while the node's network interface 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 | 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] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|C|OUT Index[5] |C|OUT Index[6] |C|OUT Index[7] |C|OUT Index[8] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
promiscuous mode.

One limitation, however, on caching of such overheard routing
information is the possible presence of uni-directional links in the
ad hoc network (Section 2). For example, in the situation shown
below, node A is using a source route to communicate with node E:

+-----+ +-----+ +-----+ +-----+ +-----+
| Address[5] A |---->| B |---->| C |---->| D |---->| E |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
+-----+ +-----+ +-----+ +-----+ +-----+
^
|
+-----+ +-----+ +-----+ +-----+ +-----+
| ... V |---->| W |---->| X |---->| Y |---->| Z |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type

???. A
+-----+ +-----+ +-----+ +-----+ +-----+
As node C forwards a data packet along the route from A to E, it
can always add to its cache the presence of the "forward" direction
links that does not understand this option should ignore
this option and continue processing it learns from the packet, headers of these packets, from itself
to D and from D to E. However, the Option
Data does "reverse" direction of the links
identified in the packet headers, from itself back to B and from B to
A, may not change en-route (the top three bits work for it since these links might be uni-directional.
If C knows that the links are 000).

Option Length

8-bit unsigned integer. Length of in fact bi-directional, for example due
to the option, MAC protocol in use, it could cache them but otherwise SHOULD
not.

Likewise, node V in octets,
excluding the Option Type example above is using a 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 links involved can be known to be bi-directional
or not before caching them. If the link from X to C (over which this
data packet was received) can be known to be bi-directional, then C
could cache the link from itself to X, the link from X to Y, and Option Length fields.

Reserved

Sent as 0; ignored on reception.

Target Address

The home address of the node
link from Y to Z. If all links can be assumed to be bi-directional,
C could also cache the links from X to W and from W to V. Similar
considerations apply to which the routing information that might be learned
from forwarded or otherwise overheard Route Request or Route Reply must be
delivered.

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

If the C bit associated with a
packets.

3.3.2. Replying to Route Requests using Cached Routes

A node N is set, it implies N will
be forwarding the packet out receiving a different interface than the one
over Route Request for which it was received (i.e., the node sending the packet
to N should not expect a passive acknowledgment).

OUT Index[1..n]

OUT Index[i] is not the interface index of the ith hop listed in
the target,
searches its own Route Reply option. It denotes the interface that should
be used by Address[i-1] Cache for a route to reach Address[i] when using the
specified source route.

Address[1..n]

Address[i] is the home address target of the ith hop listed in
Request. If found, the node generally returns a Route Reply option.

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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Option Length | Index | Error Type |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Error Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Error Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unreachable Node Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Option Type

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

Option Length

8-bit unsigned integer. Length of initiator itself rather than forwarding the option, in octets,
excluding Route Request. In
the Option Type and Option Length fields.

Index

The interface index of Route Reply, it sets the network interface route record to list the sequence of
hops over which this copy of the
node designated by Error Source Address tried Route Request was forwarded to forward a
packet it,
concatenated with its own idea of the route from itself to the target
from its Route Cache.

However, before transmitting a Route Reply packet that was generated
using information from its Route Cache in this way, a node designated MUST
verify that the resulting route being returned in the Route Reply,
after this concatenation, contains no duplicate nodes listed in the
route record. For example, the figure below illustrates a case in
which a Route Request for target E has been received by Unreachable Node Address.

Error Type

The type of error encountered. Values between 0 node F, and 127
inclusive indicate
node F already has in its Route Cache a hard failure route from itself to E:

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

The concatenation of connectivity between the
Error Source Address accumulated route from the Route Request and
the Unreachable Node Address. Values
between 128 cached route from F's Route Cache would include a duplicate node
in passing from C to F and 255 inclusive indicate back to C.

Node F in this case could attempt to edit the route to eliminate
the duplication, resulting in a soft failure.

NODE_UNREACHABLE 1

PATH_STATE_NOT_FOUND 129

Error Source Address

The home address of route from A to B to C to D and on
to E, but in this case, node F would not be on the route that it
returned in its own Route Reply. DSR Route Discovery prohibits
node originating the F from returning such a Route Error (e.g., Reply from its cache for two
reasons. First, this limitation increases the node probability that attempted to forward a packet and discovered the
link failure).
resulting route is valid, since F in this case should have received
a Route Error Destination Address

The home address of the node to which if the route had previously stopped working. Second,
this limitation means that a Route Error must be
delivered (e.g, traversing the route is very
likely to pass through any node that generated the routing information
claiming that sent the hop Error Source Address to Unreachable Node
Address was a valid hop).

Unreachable Node Address

The home address of Route Reply for the node that was found to be unreachable
(the next hop neighbor to
route (including F), which the node at ``Error Source
Address'' was attempting helps to transmit the packet).

7.2.3. DSR Acknowledgment Option

The DSR Acknowledgment hop-by-hop option ensure that stale data is encoded in
type-length-value (TLV) format removed
from caches (such 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 at F) in a timely manner. Otherwise, the packet, and next
Route Discovery initiated by A might also be contaminated by a Route
Reply from F containing the Option
Data same stale route. If the Route Request
does not change en-route (the top three bits are 000).

Option Length

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

Identification

A 32-bit value that when taken node (node F in conjunction with Data Source
Address, uniquely identifies this example)
discards the packet being acknowledged. Route Request rather than replying to it or propagating
it.

3.3.3. Preventing Route Reply Storms

The Identification value is computed ability for nodes to reply to a Route Request based on
information in their Route Caches, as ((ip_id << 16) | ip_off)
where ip_id is the value of 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 16-bit Identification field node's neighbors have a route in their Route Caches,
each neighbor may attempt to send a Route Reply, thereby wasting
bandwidth and possibly increasing the IP header number of network collisions in
the packet being acknowledged, area.

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

+-----+ +-----+
| D |< >| C |
+-----+ \ / +-----+
Cache: C - B - G \ / Cache: B - G
\ +-----+ /
-| A |-
+-----+\ +-----+ +-----+
| | \--->| B | | G |
/ \ +-----+ +-----+
/ \ Cache: G
v v
+-----+ +-----+
| E | | F |
+-----+ +-----+
Cache: F - B - G Cache: B - G

Normally, they would all attempt to reply from their own Route
Caches, and would all send their Replys at about the same time since
they all received the 13-bit Fragment Offset field in broadcast Route Request at about the IP header
of same time.
Such simultaneous replies from different nodes all receiving the
Route Request may create packet being acknowledged.

When constructing the Identification, ip_id collisions among some or all of these
Replies and ip_off MUST be
in host byte-order. The entire Identification value MUST then
be converted to network byte-order before being placed may cause local congestion in the
Acknowledgment option.

ACK Source Address

The home address of wireless network. In
addition, it will often be the node originating case that the Acknowledgment.

ACK Destination Address

The home address different replies will
indicate routes of the different lengths, as shown in this example.

If a node to which the Acknowledgment must
be delivered.

Data Source Address

The IP Source Address of the packet being acknowledged.

7.3. DSR Routing Header

As specified can put its network interface into promiscuous receive
mode, it SHOULD delay sending its own Route Reply for IPv6 [6], a Routing header is used by a source to
list one or more intermediate nodes short period,
while listening to be ``visited'' on see if the way to initiating node begins using a packet's destination. This function is similar to IPv4's Loose
Source and Record shorter
route first. That is, this node SHOULD delay sending its own Route option, but
Reply for a random period d = H * (h - 1 + r), where h is the Routing header does not
record length
in number of network hops for the route taken as the packet is forwarded. The specific
processing steps required to implement the Routing header must be
added to an IPv4 protocol stack. The Routing header returned in this node's
Route Reply, r is a random number between 0 and 1, and H is identified by a Next Header value of 43 in small
constant delay (at least twice the immediately preceding header, maximum wireless link propagation
delay) to be introduced per hop. This delay effectively randomizes
the time at which each node sends its Route Reply, with all nodes
sending Route Replys giving routes of length less than h sending
their Replys before this node, and
has all nodes sending Route Replys
giving routes of length greater than h sending their Replys after
this node. Within the following format:

The type specific delay period, this node promiscuously receives
all packets, looking for data packets from the initiator of this
Route Discovery destined for the target of the Discovery. If such
a Routing Header carrying a DSR Source
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] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Routing Header Fields:

Next Header

8-bit selector. Identifies data packet received by this node during the type delay period uses a
source route of header immediately
following length less than or equal to h, this node may infer
that the Routing header.

Hdr Ext Len

8-bit unsigned integer. Length initiator of the Routing header in
4-octet units, not including Route Discovery has already received a
Route Reply giving an equally good or better route. In this case,
this node SHOULD cancel its delay timer and SHOULD NOT send its Route
Reply for this Route Discovery.

3.3.4. Route Request Hop Limits

Each Route Request message contains a "hop limit" that may be used
to limit the first 8 octets.

Routing Type

???

Segments Left

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

Type Specific Fields:

Acknowledgment Request (R)

The Acknowledgment Request (R) bit Route Request. This hop limit is set to request an
explicit acknowledgment from implemented using the next hop. After processing
Time-to-Live (TTL) field in the Routing Header, The IP Destination Address lists the
address header 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 carrying
the Route Request. As the Request is forwarded, this Routing
Header was generated by Address[1] limit is
decremented, and not the IP Source
Address (Section 8.5.5).

Reserved

Sent as 0; ignored on reception.

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

If Request packet is discarded if the C bit associated with limit reaches
zero before finding the target.

This Route Request hop limit can be used to implement a variety of
algorithms for controlling the spread of a Route Request during a
Route Discovery attempt. For example, a node MAY send its first
Route Request attempt for some target node using a hop limit of 1,
such that any node N receiving the initial transmission of the Route
Request will not forward it to other nodes by rebroadcasting it.
This form of Route Request is set, it implies N will
be forwarding the packet out called a different interface than "non-propagating" Route
Request. It provides an inexpensive method for determining if the one
over which it was received (i.e.,
target is currently a neighbor of the initiator or if a neighbor
node sending the packet
to N should not expect has a passive acknowledgment and MAY wish route to
set the R bit).

OUT Index[1..n]

Index[i] is target cached (effectively using the interface index that
neighbors' Route Caches as an extension of the node indicated
by Address[i-1] must 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 when transmitting of the packet hop limit in a Route Request is to
Address[i]. Index[1] indicates which interface
implement an "expanding ring" search for the target [13]. For
example, a node
indicated by the IP Source Address uses to transmit the packet.

Address[1..n]

Address[i] could send an initial non-propagating Route Request
as described above; if no Route Reply is received for it, the home address of the ith node
could initiate another Route Request with a hop in the Routing
header.

Note that Address[1] limit of 2. For
each Route Request initiated, if no Route Reply is received for it,
the node could double the first intermediate hop along limit used on the route.
The address of previous attempt,
to progressively explore for the originating target node is without allowing the IP Source Address. The
only exception
Route Request to propagate over the entire network. However, this rule is for packets that are salvaged,
expanding ring search approach could have the effect of increasing
the average latency of Route Discovery, since multiple Discovery
attempts and timeouts may be needed before discovering a route to the
target node.

3.4. Additional Route Maintenance Features

3.4.1. Packet Salvaging

After sending a Route Error message as part of Route Maintenance as
described in Section 8.5.5. A packet that has been salvaged has an
alternate route placed on it by an intermediate 3.2, a node in may attempt to "salvage" the network,
and in this case, data
packet that caused the address of Route Error rather than discarding it. To
attempt to salvage a packet, the originating node (the salvaging
node) is Address[1]. Salvaged packets are indicated by setting the S
bit in the DSR Routing header.

8. Detailed Operation

8.1. Originating sending a Data Packet

When node A originates Route Error searches
its own Route Cache for a packet, route from itself to the following steps MUST be taken
before transmitting destination of the packet:

1. If
packet causing the destination address is Error. If such a multicast address, piggyback route is found, the node may
salvage the
data packet on a after returning the Route Request targeting Error by replacing the multicast address.
original source route on the packet with the route from its Route
Cache. The following fields MUST be initialized as specified:

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

DONE.

2. Otherwise, call Route_Cache.Get() then forwards the packet to determine if there is a
cached the next node indicated
along this source route to route. For example, in the destination.

3. If situation shown in the cached
example of Section 3.2, if node C has another route indicates that cached to node E,
it can salvage the destination is directly
reachable over one hop, no Routing Header should be added packet by applying this route to the packet rather
than discarding the packet. Initialize

When salvaging a packet in this way, a count is maintained in the following fields:

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

DONE.

4. Otherwise, if the cached route indicates number of times that multiple hops are
required it has been salvaged, to reach the destination, insert prevent a Routing Header into
the
single packet as described in Section 8.2. DONE.

5. from being salvaged endlessly. Otherwise, if no cached route to the destination is found, insert it could be
possible for the packet into to enter a routing loop, as different nodes
repeatedly salvage the Send Buffer packet and initiate replace the source route on the
packet with routes to each other.

3.4.2. Automatic Route Discovery as
described Shortening

Source routes in Section 8.4.

8.2. Originating a Packet with a DSR Routing Header

When use may be automatically shortened if one or more
intermediate hops in the route become no longer necessary. This
mechanism of automatically shortening routes in use is somewhat
similar to the use of passive acknowledgements. In particular, if a
node originates is able to overhear a packet with carrying a Routing Header, source route (e.g., by
operating its network interface in promiscuous receive mode), then
this node examines the address unused portion of that source route. If this
node is not the first intended next hop for the packet but is named in
the later unused portion of the packet's source route, then it can
infer that the intermediate nodes before itself in the source route MUST be listed as
are no longer needed in the IP
Destination Address as well as Address[1] route. For example, the figure below
illustrates an example in which node D has overheard a data packet
being transmitted from B to C, for later forwarding to D and to E:

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

In this case, this node (node D) returns a "gratuitous" Route Reply
message to the Routing Header.
The final destination original sender of the packet is listed (node A). The Route
Reply gives the shorter route as the last hop
in concatenation of the Routing Header (Address[n]). At each intermediate hop i,
Address[i] is copied into portion of
the IP Destination Address and original source route up through the packet
is retransmitted.

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

IP.Source_Address = Home address (node B), plus the suffix of the original source
route beginning with the node returning the gratuitous Route Reply
(node D). In this example, the route returned in the gratuitous Route
Reply message sent from D to A
IP.Destination_Address = Home address gives the new route as the sequence of node B
RT.Segments_Left = 2
RT.Out_Index[1] = Interface index used by
hops from 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 of node B
RT.Address[2] = Home address of node C
RT.Address[3] = Home address to E.

3.4.3. Increased Spreading of node D

8.3. Processing Route Error Messages

When a Routing Header

Excluding the exceptions listed here, source node receives a DSR Routing Header is
processed using the same rules as outlined Route Error for Type 0 Routing Headers
in IPv6 [6]. The Routing Header is only processed by the a data packet that
it originated, this source node whose
address appears as the IP destination of the packet. The following
additional rules apply propagates this Route Error to processing the type specific data of a DSR
Source Route:

Let

SegLft = its
neighbors by piggybacking it on its next Route Request. In this way,
stale information in the value caches of Segments Left when the packet was nodes around this source node will
not generate Route Replys that contain the same invalid link for
which this source node received
NumAddrs = the total number of addresses Route Error.

For example, in the Routing Header

1. The address of the next hop, Address[NumAddrs - SegLft + 1],
is copied into situation shown in the IP.Destination_Address example of Section 3.2,
node A learns from the packet. The
existing IP.Destination_Address is NOT copied back into the
Address list of Route Error message from C, that the Routing Header.

2. The interface used link from
C to transmit the packet D is currently broken. It thus removes this link from its own
Route Cache and initiates a new Route Discovery (if it doesn't have
another route to E in its next hop from
this node MUST be the interface denoted by Index[NumAddrs -
SegLft + 1].

3. If Route Cache). On the Acknowledgment Route Request (R) bit is set, the packet
initiating this Route Discovery, node MUST
transmit A piggybacks a packet containing copy of this
Route Error message, ensuring that the DSR Acknowledgment option Route Error message spreads
well to
the previous hop, Address[NumAddrs - SegLft - 1], performing other nodes, and guaranteeing that any Route Discovery if necessary. (Address[0] is taken as the
IP.Source_Address)

4. Perform Reply that it
receives (including those from other node's Route Maintenance by verifying Caches) in response
to this Route Request does not contain a route that assumes the packet was
received by
existence of this broken link.

4. Conceptual Data Structures

This document describes the next hop as described DSR protocol in Section 8.5.

8.4. Route Discovery

Route Discovery is the on-demand process by which nodes actively
obtain source routes to destinations to which they are actively
attempting to send packets. The destination node for which terms of a
Route Discovery is initiated is known as number of
conceptual data structures. This section describes each of these
data structures and provides an overview of its use in the "target" protocol.
In an implementation of the Route
Discovery. A Route Discovery for a destination SHOULD NOT protocol, these data structures MAY be
initiated unless the initiating node has a packet
implemented in any manner consistent with the Send Buffer
requiring delivery to that destination. A external behavior
described in this document.

4.1. Route Discovery for Cache

All routing information needed by a
given target node MUST NOT be initiated unless permitted by the
rate-limiting information contained participating in an ad hoc
network using DSR is stored in a Route Cache. Each node in the
network maintains its own Route Request Table.
After each Cache. A node adds information
to its Route Discovery attempt, the interval Cache as it learns of new links between successive
Route Discoveries nodes in the
ad hoc network; for this target must be doubled, up to example, a maximum node may learn of
MAX_REQUEST_PERIOD.

Route Discoveries for new links when it
receives a multicast address SHOULD NOT be rate limited,
and SHOULD always be permitted.

8.4.1. Originating packet carrying either a Route Request

The basic Route Discovery algorithm for Reply or a unicast destination is as
follows:

1. Originate DSR Routing
header. Likewise, a node removes information from its Route Request packet with Cache as
it learns that existing links in the IP header Time-to-Live
field initialized to 1. This type ad hoc network have broken; for
example, a node may learn of Route Request is called a
non-propagating broken link when it receives a packet
carrying a Route Request and allows the originator of the
Request to inexpensively query Error or through the route caches of each of its
neighbors for link-layer retransmission
mechanism reporting a route failure in forwarding a packet to the its next-hop
destination.

2. If a Route Reply

It is received in response possible to the non-propagating
Request, use the returned source route interface a DSR network with other networks,
external to transmit all packets this DSR network. Such external networks may, for
example, be the destination 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 are treated as external networks
in the Send Buffer. DONE.

3. Otherwise, if no Route Reply is received within
RING0_REQUEST_TIMEOUT seconds, transmit a Route Request
with the IP header Time-to-Live field initialized order to
MAX_ROUTE_LEN. This type improve scalability. The complete handling of Route Request such
external networks is called a propagating
Route Request. Update the information in the Route Request
Table, to double beyond the amount scope of time before any subsequent Route
Discovery attempt this document. However,
this document specifies a minimal set of requirements and features
necessary to allow nodes only implementing this target.

4. If no Route Reply is received within the time interval indicated
by the Route Request Table, GOTO step 1.

The Route Request option SHOULD be initialized as follows:

IP.Source_Address = specification to
interoperate correctly with nodes implementing interfaces to such
external networks. This node's home address
IP.Destination_Address = 255.255.255.255
Request.Target = Home address of intended destination
Request.OUT_Index[1] = Index minimal set of interface used to transmit requirements and features
involve the Request

The behavior of a node processing a packet containing both a Routing
Header First Hop External (F) and Last Hop External (L) bits in
a Route Request Destination option is unspecified.
Packets SHOULD NOT contain both a DSR Routing Header and a DSR Route Request
Destination option. [This is not exactly true: A Route Request
option appearing Reply option, and the addition
of an External flag bit tagging each node in the second Destination Options header that IPv6
allows after Route Cache, copied
from the First Hop External (F) and Last Hop External (L) bits in the
Routing Header would probably do-what-you-mean,
though we have not triple-checked it yet. Namely, it would allow header or Route Reply from which the
originator of a link to this node was
learned.

The Route Cache SHOULD support storing more than one route discovery to unicast each
destination. In searching the request Route Cache for a route to some other
destination node, where it would be released the Route Cache is indexed by destination node
address.

- Each implementation of DSR at any node MAY choose any appropriate
strategy and begin algorithm for searching its Route Cache and
selecting a "best" route to the flood fill. We call
this destination from among those
found. For example, a Route Request Blossom since node MAY choose to select the unicast portion shortest
route to the destination (the shortest sequence of hops), or it
MAY use an alternate metric to select the path
looks like route from the Cache.

- However, if there are multiple cached routes to a stem on destination,
the blossoming flood-fill selection of routes when searching the request.]

Packets containing a Route Request Destination option SHOULD NOT be
retransmitted, Cache SHOULD NOT request an explicit
prefer routes that do not have the External flag set on any
node. This will prefer routes that lead directly to the target
node instead of routes that attempt to reach the target via any
external networks connected to the DSR Acknowledgment by
setting ad hoc network.

- In addition, any route selected when searching the R bit, SHOULD Route Cache
MUST NOT expect a passive acknowledgment, and
SHOULD have the External bit set for any nodes other than
possibly the first node, the last node, or both; the External bit
MUST NOT be placed set for any intermediate hops in the Retransmission Buffer. The repeated
transmission route selected.

An implementation of packets containing a Route Request Destination option
is controlled solely by the logic described in this section.

8.4.2. Processing a Route Request Option

When Cache MAY provide a fixed capacity for
the cache, or the cache size MAY be variable.

- Each implementation of DSR at each node A receives a packet containing a Route Request option, MAY choose any
appropriate policy for managing the entries in its Route Request option is processed Cache,
such as follows:

1. If Request.Target_Address matches the home address when limited cache capacity requires a choice of this node,
then which
entries to retain in the Route Request option contains cache. For example, a complete source route
describing node MAY chose a
"least recently used" (LRU) cache replacement policy, in which
the path entry last used longest ago is discarded from the initiator of cache if a
decision needs to be made to allow space in the 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 in the Destination Option extension
header. DONE.

2. Otherwise, if the combination (IP.Source_Address,
Request.Identification) is found Route Cache in any node.
For example, the Route Request
Table, then discard following two types of organization are possible:

- In DSR, the packet, since this route returned in each Route 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.3)
represents a complete path (a sequence of links) leading to the Destination option.

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

4. Otherwise, if the home address
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, 19] and the rules
through implementation of Section 8.4.3 permit it, return DSR in a Cached mobile outdoor testbed under
significant workload [20, 21].

- 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 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 any overheard packets can be
merged together to form new routes in the Request,
it SHOULD append network, but this cached route
is not possible in a path cache due to the accumulated route record separation of each
individual path in the packet and return this route cache.

This type of organization for the Route Cache in DSR, including
the effect of a Route Reply packet range of implementation choices, has been studied
through detailed simulation [9].

The choice of data structure organization to
the initiator without propagating (re-broadcasting) the Route
Request. Thus, use for example, if node F in the example network shown Route Cache
in Figure 8.4.3 needs to send any DSR implementation is a packet to local matter for each node D, it will initiate
a Route Discovery and broadcast a 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
were recently originated or forwarded by this
broadcast node. The table is received
indexed by node A, node A can simply return a IP address.

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

Before transmitting which this node has initiated a Route Reply packet that was generated using
information from its Route Cache, a node MUST verify that:

1. The resulting route contains no loops.

2. Request:

- The node issuing the Route Reply is listed in the route that it
specifies in its Reply. This increases the probability time that the
route is valid, since the this node in question should have received last originated a Route Error if this route stopped working. Additionally, this
requirement means Discovery for
that target node.

- The number of consecutive Route Requests initiated for this
target since receiving a valid Route Error traversing the route will
pass through the node that issued the Reply based on stale cache
data, which is critical for ensuring stale data is removed from
caches in giving a timely manner. Without route to that
target node.

- The remaining amount of time before which this requirement, the node MAY next
attempt at a Route Discovery for that target node.

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

In addition, the original requester might also be
contaminated by a Route Reply Request Table on a node also records the
following information about initiator nodes from which this node has
received a Route Request:

- A FIFO cache of size REQUEST_TABLE_IDS entries containing the same
stale route.

8.4.4. Originating a
Identification value and target address from the most recent
Route Reply

Let REQPacket denote a packet Requests received by this node A from that
contains a initiator node.

Nodes SHOULD use an LRU policy to manage the entries in their Route
Request option which lists node A as the
REQPacket.Request.Target_Address. Let REPPacket Table.

The number of Identification values to retain in each Route Request
Table entry, REQUEST_TABLE_IDS, MUST NOT be unlimited, since,
in the worst case, when a packet
transmitted by node A that contains a corresponding Route Reply. The crashes and reboots, the first
REQUEST_TABLE_IDS Route Reply option transmitted in response Requests it initiates could appear to be
duplicates to the other nodes in the network.

4.3. Send Buffer

The Send Buffer of some node is a Route Request MUST queue of packets that cannot be
initialized as follows:

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

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

Figure 1: An example network where A knows
transmitted by that node because it does not yet have a source
route to D via B each respective packet's destination. Each packet in the
Send Buffer is stamped with the time that it is placed into the
Buffer, and C.

1. SHOULD be removed from the Send Buffer and discarded
SEND_BUFFER_TIMEOUT seconds after initially being placed in the
Buffer. If REQPacket.Request.Address[] does not contain any hops, then
node A is only necessary, a single hop from FIFO strategy SHOULD be used to evict
packets before they timeout to prevent the originator of buffer from overflowing.

Subject to the Route
Request. Build rate limiting defined in Section 6.2, a Route Reply packet
Discovery SHOULD be initiated 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 often as possible for the
destination address of node A

GOTO step 3.

2. Otherwise, build a Route Reply packet as follows:

REPPacket.IP.Source_Address = any packets residing in the Send Buffer.

4.4. Retransmission Buffer

The home address Retransmission Buffer of a 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 queue of packets sent by
this node that are awaiting the Route
Request requires performing a Route Discovery, receipt of an acknowledgment from the Route Reply
hop-by-hop option MUST be piggybacked on
next hop in the source route (Section 5.3).

For each packet that contains in the
Route Request. This prevents Retransmission Buffer, a loop wherein the target node maintains (1) a
count of the new
Route Request (which was itself number of retransmissions and (2) the originator time of the original Route
Request) must do another Route Request in order to return its Route
Reply.

If sending last
retransmission.

Packets are removed from the Route Reply to buffer when an acknowledgment
is received, or when the originator number of retransmissions exceeds
DSR_MAXRXTSHIFT. In the Route Request
does not require performing Route Discovery, a node later case, the removal of the packet from
the Retransmission Buffer SHOULD send result in a
unicast Route Reply Error being
returned to the original source of the packet (Section 6.3).

5. Packet Formats

Dynamic Source Routing makes use of four options carrying control
information that can be piggybacked in response any existing IP packet. The
mechanism used to every Route Request targeted at
it.

8.4.5. Processing represent these options in a Route Reply Option

Upon receipt packet is based on
the design of a Route Reply, a node should extract the source route
(Target_Address, OUT_Index[1]:Address[1], .. OUT_Index[n]:Address[n]
) Hop-by-Hop and insert this route into its Route Cache. All the packets Destination Options mechanisms in the
Send Buffer SHOULD
IPv6 [7]. The ability to generate and process such options must
be checked added to see whether an IPv4 protocol stack. Specifically, the information Protocol
field in the
Reply allows them IP header is used to be sent immediately.

8.5. Route Maintenance

Route Maintenance requires indicate that whenever a node transmits a data
packet, a Route Reply, Hop-by-Hop Options
extension header or a Route Error, it must verify that the next
hop (indicated by the Destination Options extension header follows the
IP Address) correctly receives header, and the Next Header field in the extension header is used
to indicate the type of protocol header (such as a transport layer
header) following the extension header.

In addition, DSR makes use of one additional header type, to carry
the source route for a packet.

If This DSR Routing header is based on
the sender cannot verify that design of the next hop received Routing header defined for IPv6 [7]. DSR defines
a new value for the packet, it Routing Type field to distinguish a DSR Routing
header from other types of Routing headers.

For IPv6, all extension headers are a multiple of 8 bytes in length.
However, for use in IPv4 packets, all extension headers only MUST decide that its link to be
a multiple of 4 bytes long. This requirement preserves the next hop is broken alignment
of any following extension headers and MUST send of any additional header
(e.g., a
Route Error to the node responsible for generating TCP header [26]) following the Routing last extension header.

5.1. Destination Options Header
that contains the broken link (Section 8.5.3).

The following ways may be Destination Options extension header is used to verify carry optional
information that the next hop correctly
received needs to be examined only by a packet:

- packet's destination
node(s). The receipt of Destination Options extension header is identified by
a passive acknowledgment (Section 8.5.1).

- The receipt of an explicitly requested acknowledgment
(Section 8.5.1).

- By the presence Next Header (or Protocol) value of positive feedback from the link layer
indicating that the packet was acknowledged by the next hop
(Section 8.5.2).

- By 60 in the absence of explicit failure notification from immediately preceding
header [7], and has 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 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 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 | Hdr Ext Len | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
| |
. .
. Options .
. .
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Next Header with

8-bit selector. Identifies the R bit set (e.g., packets which contain only an Acknowledgment
and a Routing Header for which type of header immediately
following the last forwarding hop requires an
explicit acknowledgment Destination Options header. Uses the same values
as the IPv4 Protocol field [27].

Hdr Ext Len

8-bit unsigned integer. Length of receipt by the final destination).

8.5.1. Using Network-Layer Acknowledgments

For link layers that do Destination Options
header in 4-octet units, not provide explicit failure notification, including the first 8 octets.

Options

Variable-length field, of length such that the complete
Destination Options header is an integer multiple of 4 octets
long. Contains one or more TLV-encoded options.

The following steps SHOULD be destination option type is 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. DSR protocol:

- If the packet does not contain a Routing Header, the node DSR Route Request option (Section 5.1.1)

5.1.1. DSR Route Request Option

The DSR Route Request destination option is encoded in
type-length-value (TLV) format as follows:

IP fields:

Source Address

MUST
transmit a packet containing the DSR Acknowledgment option
to the previous hop as indicated by the IP.Source_Address.
Since the receiving node is the final destination, there
will be no opportunity for the originator set to obtain a
passive acknowledgment, 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 address of the packet into the
Retransmission Buffer and update the information maintained about
this packet in the Retransmission Buffer.

2. If after processing the Routing Header, RH.Segments_Left is equal
to 0, then node A MUST set originating this packet.
Intermediate nodes that repropagate the Acknowledgment Route Request (R) bit in
the Routing Header before transmitting the packet over its final
hop.

3. If after processing 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 MUST not
change this field.

Destination Address

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

Hop Limit (TTL)

Can be varied from 1 to 255, for example to implement
non-propagating Route Requests and Route Request (R) bit in the Routing Header before transmitting the
packet (since the C bit was set during expanding-ring
searches (Section 3.3.4).

Route Discovery by the
node now listed as the IP.Destination_Address Request fields:

Option Type

???. The top three bits of this Option Type value are equal to indicate
011, meaning that
it will propagate the packet out a different interface, and that node A will not receive a passive acknowledgment).

4. Set the retransmission timer for the packet 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 that does not understand this option
MUST discard the
Retransmission Buffer packet, and disable that the retransmission timer.
DONE.

7. Otherwise, when Option Data may change
en-route [7].

Option Length

8-bit unsigned integer. Length of the Retransmission Timer expires, remove option, in octets,
excluding the
packet from Option Type and Option Length fields.

Identification

A unique value generated by the Retransmission Buffer.

8. If DSR_MAXRXTSHIFT transmissions have been done, then attempt
to salvage initiator (original sender) of
the packet (Section 8.5.5). Also, Route Request. Nodes initiating a Route Request generate
a new Identification value for each Route
Error. DONE.

9. GOTO step 1.

8.5.2. Using Link Layer Acknowledgments

If explicit failure notifications are provided by the link layer,
then Request, for example
based on a sequence number counter of all packets are assumed to be correctly received Route Requests
initiated by the next hop
and a Route Error is sent only when node.

This value allows a explicit failure notification
is made from the link layer.

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

8.5.3. Originating determine whether it
has recently seen a Route Error

If the next hop copy of a packet this Route Request: if this
Identification value is found to be unreachable as described by this receiving node in Section 8.5, a its
Route Error packet (Section 7.2.2) MUST be returned
to Request Table (in the node whose cache generated of Identification values
in the information used to route entry there for this initiating node), this receiving
node MUST discard the
packet. Route Request. When a node A generates propagating a Route Error for packet P, it
Request, this field MUST
initialize be copied from the fields in received copy of
the Route Error as follows:

Error.Source_Address = Home address of node A
Error.Unreachable_Address = Home Request being forwarded.

Target Address

The address of the unreachable node

- If the packet contains a DSR Routing Header and the S bit that is NOT
set, the packet has been forwarded without target of the need for salvaging
up to this point.

Error.Destination_Address = P.IP.Source_Address

- Otherwise, if Route
Request.

Address[1..n]

Address[i] is the packet contains a DSR Routing Header and address of the S
bit IS set, i-th hop recorded in the packet has been salvaged by an intermediate node,
and thus
Route Request option. The number of addresses present in this Routing Header was placed there
field is indicated by the salvaging
node.

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

- Otherwise, if the packet does not contain a DSR Routing Header, Option Length field in the packet must have been originated by this node A.

Error.Destination_Address option
(n = Home address of (Option Length - 6) / 4). Each node A

Send the packet containing repropagating the
Route Error to Error.Destination_Address,
performing Route Discovery if necessary.

As an optimization, Route Errors that are discovered by the
packet's originator (such that Error.Source_Address is equal Request adds its own address to
Error.Destination_Address) SHOULD be processed internally. Such
processing should invoke all this list, increasing the steps that would be taken if a Route
Error option was created, transmitted, received, and processed,
but an actual packet containing a
Option Length value by 4.

The DSR Route Error Request destination option SHOULD MUST NOT be
transmitted.

8.5.4. Processing a Route Error Option

Upon receipt of a Route Error via any mechanism, a node
SHOULD remove appear more than
once within any route from its Route Cache that uses the hop
(Error.Source_Address, Error.Index to Error.Unreachable_Address).
This includes all Route Errors overheard, and those processed
internally as described in Section 8.5.3.

When the single Destination Options extension header.

5.2. Hop-by-Hop Options Header

The Hop-by-Hop Options extension header is used to carry optional
information that must be examined by every node along a packet's
delivery path. The Hop-by-Hop Options extension header is identified
by Error.Destination_Address receives a Protocol value of 0 in the Route Error, it SHOULD verify that IP header [7], and has the source route
responsible for delivering following
format:

Next Header

8-bit selector. Identifies the Route Error includes type of header immediately
following the Hop-by-Hop Options header. Uses the same
hops values
as the working prefix IPv4 Protocol field [27].

Hdr Ext Len

8-bit unsigned integer. Length of the original packet's source route
(Error.Destination_Address to Error.Source_Address). If any
hop listed Hop-by-Hop Options
header in the working prefix is 4-octet units, not included in the Route
Error's source route, then the originator SHOULD forward the Route
Error back along including the working prefix (Error.Destination_Address to
Error.Source_Address) so first 8 octets.

Options

Variable-length field, of length such that each node along the working prefix will
remove the invalid route from its Route Cache. complete
Hop-by-Hop Options header is an integer multiple of 4 octets
long. Contains one or more TLV-encoded options.

If present in an IP packet, the node processing a Route Error option discovers its home
address is Error.Destination_Address and Hop-by-Hop Options extension header
MUST appear in the packet contains
additional Route Error option(s) later on the inside of immediately following the Hop IP header.

The following hop-by-hop option types are used by Hop options header, we call the additional Route Errors nested DSR protocol:

- DSR Route Errors. The node MUST deliver the first nested Reply option (Section 5.2.1)

- DSR Route Error
to Nested_Error.Destination_Address, performing option (Section 5.2.2)

- DSR Acknowledgment option (Section 5.2.3)

5.2.1. DSR Route Discovery if
needed. It does this by removing the Reply Option

The DSR Route Error Reply hop-by-hop option listing
itself is encoded in type-length-value
(TLV) format as the Error.Destination_Address, finding the first nested
Route Error option, and originating the remaining packet to
Nested_Error.Destination_Address. This mechanism allows for the
proper handling 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 |L| Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[2] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[n] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Option Type

???. The top three bits of Route Errors that this Option Type value are discovered while delivering
a Route Error.

8.5.5. Salvaging a Packet

When node A attempts equal to salvage
000, meaning that a packet originated at node S that does not understand this option
SHOULD ignore this option and
destined for node D, it MUST perform continue processing the following steps:

1. Generate packet,
and send a Route Error to S as explained that the Option Data does not change en-route [7].

Option Length

8-bit unsigned integer. Length of the option, in
Section 8.5.3.

2. Call Route_Cache.Get() to determine if it has a cached source
route to octets,
excluding the packet's ultimate destination D (which is Option Type and Option Length fields.

Last Hop External (L)

Set to indicate that the last
Address listed in the Routing Header).

3. If node A does not have indicated by the Route Reply
is actually in a cached route for node D, it MUST
discard network external to the packet. DONE.

4. Otherwise, let Salvage_Address[1] through Salvage_Address[m] be DSR network; the exact
sequence of hops returned from the Route Cache. Initialize leading to it outside the following fields DSR network are not
represented in 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 IP Source Address of the packet MUST remain unchanged. When the
Routing Header Route Reply. Nodes caching this hop in
their Route Cache MUST flag the outgoing packet is processed, RT.Address[2],
will be copied to cached hop with the IP Destination Address field.

9. Optimizations

A number of optimizations can External
flag. Such hops MUST NOT be added to the basic operation of returned in a cached Route Discovery and Reply
generated from this Route Maintenance as described in Sections 8.4
and 8.5 that can reduce the number of overhead packets Cache entry, and improve
the average efficiency selection of the routes used on data packets. This
section discusses some of those optimizations.

9.1. Leveraging
from the Route Cache

The data in to route a node's Route Cache may be stored in any format, but
the active packet being sent SHOULD prefer
routes in its cache form a tree of routes, rooted at
this node, to other that contain no nodes in flagged as External.

Reserved

Sent as 0; ignored on reception.

Address[1..n]

The source route being returned by the ad hoc network. For example, Route Reply, indicating
a route from the
illustration below shows an ad hoc network node with address Address[1] to the node with
address Address[n]. The number of six mobile nodes, addresses present in
which mobile node this
field is indicated by the Option Length field in the option
(n = (Option Length - 1) / 4).

A has earlier completed a DSR Route Discovery for
mobile node D and has cached Reply destination option MAY appear one or more times
within a route to D through B and C:

B->C->D
+---+ +---+ +---+ +---+ single Hop-by-Hop Options extension header.

5.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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| A |---->| B |---->| C |---->| D Option Type |
+---+ +---+ +---+ +---+

Since nodes B and C Error Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Unreachable Node Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Option Type

???. The top three bits of this Option Type value are on the route to D, node A also learns the
route equal to both of these nodes from its Route Discovery for D. If A
later performs
000, meaning that a Route Discovery node that does not understand this option
SHOULD ignore this option and learns continue processing the route to E through B packet,
and C, it can represent this in its Route Cache with that the addition Option Data does not change en-route [7].

Option Length

8-bit unsigned integer. Length of the single new hop from C to E. If A then learns it can reach C option, in a
single hop (without needing to go through B), A SHOULD use this new
route octets,
excluding the Option Type and Option Length fields.

For the current definition of the DSR Route Error option, this
field MUST be set to C 13. Extensions to also shorten the routes to D and E in its DSR Route Cache.

9.1.1. Promiscuous Learning Error
option format may be included after the fixed portion of Source Routes

A node can add entries to its the
DSR Route Cache any time it learns a new
route. In particular, when a node forwards a data packet as an
intermediate hop on Error option specified above. The presence of such
extensions will be indicated by the route in that packet, Option Length field. When
the forwarding node Option Length is
able to observe greater than 13 octets, the entire route in remaining
octets are interpreted as extensions. Currently, no extensions
have been defined.

Error Type

The type of error encountered. Currently, the packet. Thus, following type
value is defined:

NODE_UNREACHABLE 1

Other values of the Error Type field are reserved for example,
when any intermediate node B forwards packets from future
use.

Reservd

Reserved. Sent as 0; ignored on reception.

Salvage

A to D, B SHOULD
add the source route information 4-bit unsigned integer. Copied from that packet's the Salvage field in the
DSR Routing Header
to its own header of the packet triggering the Route Cache. If a Error,
incremented by the node forwards a Route Reply packet, it
SHOULD also add returning the source route information from Route Error.

Error Source Address

The address of the route record
being returned in node originating the Route Reply, to its own Route Cache.

In addition, since all wireless network transmissions at Error (e.g., the physical
layer are inherently broadcast, it may be possible for a
node to
configure its network interface into promiscuous receive mode, such that the node is able attempted to receive all packets without forward a packet and discovered the link layer
failure).

Error Destination Address

The address filtering. In this case, of the node MAY add to its which the Route Cache Error must
be delivered (e.g., the route node that generated the routing
information from any packet it can overhear.

9.2. Preventing Route Reply Storms claiming that the hop Error Source Address to
Unreachable Node Address was a valid hop).

Unreachable Node Address

The ability for nodes address of the node that was found to reply be unreachable
(the next hop neighbor to a Route Request not targeted at
them by using their Route Caches can result in a Route Reply storm.
If a which the node broadcasts a with address
Error Source Address was attempting to transmit the packet).

A DSR Route Request for Error destination option MAY appear one or more times
within a node that its neighbors
have single Hop-by-Hop Options extension header.

5.2.3. DSR Acknowledgment Option

The DSR Acknowledgment hop-by-hop option is encoded in their Route Caches, each neighbor may attempt
type-length-value (TLV) format as follows:

Option Type

???. The top three bits of this Option Type value are equal to send
000, meaning that a
Route Reply, thereby wasting bandwidth node that does not understand this option
SHOULD ignore this option and increasing continue processing the rate packet,
and that the Option Data does not change en-route [7].

Option Length

8-bit unsigned integer. Length of collisions in the area. For example, option, in octets,
excluding the network shown in
Section 9.1, if both node A Option Type and node B receive F's Route Request,
they will both attempt to reply Option Length fields.

Identification

Copied from their Route Caches. Both will
send their Replies at about the same time since they receive the
broadcast at about the same time. Particularly when more than the
two mobile nodes in this example are involved, these simultaneous
replies from Identification field of the mobile nodes receiving DSR Routing header
of the broadcast may create packet collisions among some or all being acknowledged.

ACK Source Address

The address of these replies and may cause
local congestion in the wireless network. In addition, it will
often be the case that node originating the different replies will indicate routes DSR Acknowledgment.

ACK Destination Address

The address of different lengths. For example, A's Route Reply will indicate a
route to D that is one hop longer than that in B's reply.

For interfaces which can promiscuously listen to the channel, mobile
nodes SHOULD use the following algorithm node to reduce which the number of
simultaneous replies by slightly delaying their Route Reply:

1. Pick a delay period

d = H * (h - 1 + r)

where h DSR Acknowledgment is the length 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 delivered.

A DSR Acknowledgement destination option MAY appear one or more times
within a small constant delay to be introduced
per hop.

2. Delay transmitting the Route Reply from this node single Hop-by-Hop Options extension header.

5.3. DSR Routing Header

As specified for IPv6 [7], a period
of d.

3. Within Routing header is used by a source to
list one or more intermediate nodes to be "visited" on the delay period, promiscuously receive all packets at
this node. If way to
a packet packet's destination. This function is received by this node during similar to IPv4's Loose
Source and Record Route option, but the delay
period that Routing header does not
record the route taken as the packet is addressed forwarded. The specific
processing steps required to implement the target of this Route Discovery
(the target Routing header must be
added to an IPv4 protocol stack. The Routing header is identified by
a Next Header value of 43 in the final destination address immediately preceding header, and
has the following format:

0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Next Header | Hdr Ext Len | Routing Type | Segments Left |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
. .
. type-specific data .
. .
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The type-specific data for a Routing Header carrying a DSR Source
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|F|L| Reserved |Salvage| Identification |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[1] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[2] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ... |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Address[n] |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Routing header fields:

Next Header

8-bit selector. Identifies the packet,
through any sequence type of intermediate hops), and if header immediately
following the length Routing header.

Hdr Ext Len

8-bit unsigned integer. Length of the route on this packet is less than h, then cancel the delay
timer and do Routing header in
4-octet units, not transmit the Route Reply from this node; this
node may infer that including the initiator first 8 octets.

Routing Type

???

Segments Left

Number of this Route Discovery has
already received a Route Reply, giving an equally good or better
route.

9.3. Piggybacking on Route Discoveries

As described in Section 5.1, when one node needs to send a packet
to another, if the sender does not have a route cached to the
destination node, it must initiate a Route Discovery, buffering the
original packet until the Route Reply is returned. The delay for
Route Discovery and the total segments remaining, i.e., 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 is received by a node that replies
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, explicitly
listed intermediate nodes still to be visited before discarding reaching
the packet, final destination.

Type-specific fields:

First Hop External (F)

Set to indicate that the first node must construct indicated by the Routing
header is actually in a new packet containing network external to the
piggybacked data DSR network;
the exact sequence of hops leading from it outside the Route Request packet. The source route DSR
network are not represented in the Routing header. Nodes
caching this packet hop in their Route Cache MUST be constructed to appear as if the new packet
had been sent by flag the initiator of cached
hop with the External flag. Such hops MUST NOT be returned
in a Route Discovery and had been
forwarded normally to Reply generated from this node. Hence, the first portion Route Cache entry, and
selection of the
route is taken routes from the accumulated route record in the Route Request Cache to route a packet and
being sent SHOULD prefer routes that contain no hops flagged as
External.

Last Hop External (L)

Set to indicate that the remainder of last hop indicated by the route Routing
header is taken from this node's Route
Cache. The sender address actually in the packet MUST also be set a network external to the
initiator DSR network;
the exact sequence of hops leading to it outside the DSR
network are not represented in the Routing header. Nodes
caching this hop in their Route Discovery. Since Cache MUST flag the replying node will be
unable to correctly recompute an Authentication header for cached
hop with the split
off piggybacked data, data covered by an Authentication header SHOULD External flag. Such hops MUST NOT be piggybacked on Route Request packets.

9.4. Discovering Shorter Routes

Once returned
in a Route Reply generated from this Route Cache entry, and
selection of routes from the Route Cache to route between a packet source and a destination
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 number of times that
this packet has been
discovered, the basic salvaged as a part of DSR protocol MAY continue routing
(Section 3.4.1).

Identification

Used to use request that route
for all traffic from the source to the destination as long as
it continues a DSR Acknowledgement option be returned
to work, even if the nodes move such this transmitting node for this hop. The special value of 0
indicates that a shorter
route becomes possible. In many cases, the basic Route Maintenance
procedure will discover no DSR Acknowledgement is requested. Otherwise,
the shorter route, since if a node moves
enough Identification field is set to create a shorter route, it will likely also move out of
transmission range of at least one hop on unique nonzero number
by this node transmitting the existing route.

Furthermore, when a data packet and is received as copied into the result
Identification field of
operating in promiscuous receive mode, the DSR Acknowledgement option when
returned by the node checks if receiving the Routing
Header packet contains its address in the unprocessed portion over this hop.

Address[1..n]

The sequence of addresses 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. The node then sends what is called
a gratuitous Route Reply message to In routing
and forwarding the packet's source, giving it packet, the shorter source 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 is processed as a result of A
being
described in promiscuous receive mode:

1. If the packet is not Sections 6.1.2 and 6.1.4.

6. Detailed Operation

6.1. General Packet Processing

6.1.1. Originating a data packet containing Packet

When originating any packet, a Routing Header,
drop the packet. DONE.

2. If the home address of this node does not appear in using DSR routing MUST perform
the portion following sequence of steps:

- Search the source node's Route Cache for a route that has not yet been processed (indicated by
Segments Left), then drop to the packet. DONE.

3. Otherwise, address given in
the node B that just transmitted IP Destination Address field in the packet (indicated
by Address[NumAddrs - SegLft packet's header.

- 1]) can communicate directly with
this node A. Create a If no such route is found in the Route Reply. The Cache, then perform
Route Reply MUST list Discovery for the entire source route contained Destination Address, as described in
Section 6.2.

- If the received packet contains a Route Request option, then replace the
IP Destination Address field with the
exception IP "limited broadcast"
address (255.255.255.255) [3].

- Else, this node must have a route to the Destination Address
of the intermediate nodes between node B and node A.

4. Send this gratuitous packet (since otherwise a Route Reply Request would have
been added to the node listed as packet). If the
IP.Source_Address length of the received packet. If Route Discovery this route is required it MAY be initiated,
greater than 1 hop, or if the gratuitous Route Reply
packet MAY be dropped.

9.5. Rate Limiting node determines to request a DSR
network-layer acknowledgement from the Route Discovery Process

One common error condition that must be handled in an ad hoc network
is first hop of the case route,
then insert a DSR Routing header into the packet, as described
in Section 6.1.2. The source route in which the network effectively becomes partitioned.
That is, two nodes that wish packet is initialized
from the route to communicate are not within
transmission range of each other, and there are not enough other
mobile nodes between them the Destination Address found in the Route
Cache.

- Transmit the packet to form a sequence of hops through which
they can forward packets. If a new the address given in the IP
Destination Address, using Route Discovery was initiated
for each Maintenance to retransmit the
packet sent by a node if necessary, as described in this situation, Section 6.3.

6.1.2. Adding a large number DSR Routing Header to a Packet

The design of
unproductive Route Request packets would be propagated throughout the
subset DSR Routing header is based on the design of a
Routing header in IPv6 [7]. A node originating a packet adds a
DSR Routing header to the ad hoc network reachable from this node. In packet, if necessary, in order to
reduce carry
the overhead source route of hops from such Route Discoveries, we use exponential
back-off this originating node to limit the rate at which new Route Discoveries may be
initiated from any node for final
destination address of the same target. If packet. Specifically, the node attempts adding the
DSR Routing header constructs the Routing header and modifies the IP
packet according to
send additional data packets the following sequence of steps:

- A DSR Routing header, as described in Section 5.3, is created
and added to this same node more frequently than
this limit, the subsequent packets SHOULD packet after the IP header and any Hop-by-Hop
Options header that may already be buffered in the Send
Buffer until a Route Reply is received, packet, but it MUST NOT initiate before any
Destination Options header (e.g., containing a
new Route Discovery until the minimum allowable interval between new DSR Route Discoveries for this target has been reached. This limitation
on the maximum rate Reply
option) that may be present.

- The number of Route Discoveries for the same target is
similar Address fields to include in the mechanism required by Internet nodes to limit DSR Routing
header (n) is the rate
at which ARP requests are sent to any single IP address [2].

9.6. Improved Handling number of Route Errors

All intermediate nodes SHOULD process all of in the Route Error messages they
receive, regardless source
route for the packet (i.e., excluding address of whether the originating
node is and the final destination address of the Route Error, packet). The
Segments Left field in the DSR Routing header is forwarding initialized
equal to n.

- The Source Address from the Route Error, or promiscuously
overhears IP header is copied into Address[n]
in the Route Error.

Since a Route Error packet names both ends DSR Routing header.

- The first hop of the hop that source route for the packet is no
longer valid, any copied into
the Source Address field in the IP header.

- The remaining hops of the nodes receiving source route for the error packet may update
their Route Caches to reflect are copied
into sequential Address[i] fields in the fact that DSR routing header,
for i = 1, 2, ..., n-1.

- The First Hop External (F) bit in the two nodes Routing header is copied
from the External bit flagging the first hop node in the source
route for the packet, as indicated in the packet can no longer directly communicate. A node receiving
a Route Error packet simply searches its Route Cache for any routes
using this hop. For each such route found, Cache.

- The Last Hop External (L) bit in the route Routing header is effectively
truncated at this hop. All nodes on copied
from the route before this hop are
still reachable on this route, but subsequent nodes are not.

An experimental optimization to improve External bit flagging the handling of errors is
to support last hop node in the caching of "negative" information source
route for the packet, as indicated in a node's the Route Cache.

- All other fields in the type-specific data in the DSR Routing
header are initialized to 0.

- The goal of negative information Routing Type field in the DSR Routing header is initialized
to record that a given
route was tried and found not to work, so that if ???.

- The Hdr Ext Len field in the same route DSR Routing header is discovered again shortly after the failure, initialized
to 4.

- Next Header field in the Route Cache can
ignore or downgrade DSR Routing header is set equal to the metric of
current value in the failed route.

We have not currently included this caching of negative information Protocol field in our simulations, since it appears to be unnecessary if nodes also
promiscuously receive Route Error packets.

9.7. Increasing Scalability

We recently designed and began experimenting with ways to integrate
ad hoc networks with the Internet and with Mobile IP [14]. In
addition to this, we are also exploring ways to increase header (or the
scalability of ad hoc networks by taking advantage of their
cooperative nature
Next Header field in the preceding extension header), and the fact that some hierarchy can be imposed
on an ad hoc network, just be assigning addresses
Protocol field (or preceding Next Header field) is set equal
to the nodes in 43 to indicate a
reasonable way. These ideas are described in Routing header extension header [7].

6.1.3. Receiving a workshop paper [4].

10. Path-State and Flow-State Mechanisms

This section describes Packet

When a node receives any packet, it MUST process the current design of our framework for
supporting better-than-best-effort Quality packet according
to the following sequence of Service in DSR
networks. The framework dovetails into DSR's existing mechanisms,
and, like DSR itself, is completely on-demand steps:

- If the Destination Address in nature --- no
packets are sent unless there is user data to transfer. The
framework is based on the introduction packet's IP header does not
match any of two kinds this receiving node's own IP address(s), then the
processing of soft-state,
called path-state and flow-state, at this packet depends on whether the intermediate nodes along packet contains
a DSR Routing header:

* If the
path between senders and destinations.

Taken together, packet contains a DSR Routing header, then discard the
packet.

* Else, if the packet contains a Hop-by-Hop Options extension
header (if present, this MUST immediately follow the packet's
IP header), then process the path-state options contained in the
Hop-by-Hop Options extension header. Forward the packet
using normal IP forwarding proceedures and flow-state extensions extend do not process the
Quality
packet further.

- Examine and process each of Service provided by DSR networks the extension headers (if any) in
the following ways:

- They eliminate packet in the need for all data packets to carry a source
route, increasing order in which they occur in the efficiency of packet. By
dispatching on the protocol Protocol field in general.

- They provide accurate measurements of the state packet's IP header,
and subsequently dispatching on the Next Header field of each
encountered extension header, the network to
higher layers protocols appropriate protocol module is
executed by the receiving node for use in adaptation. each extension header.

- They enable senders to explicitly manage If a Hop-by-Hop Options extension header or Destination Options
extension headers is encountered in processing the consumption of
resources across packet, the network.

- They enable
receiving node MUST process any options given in this header in
the network to provide better-than-best-effort
service via admission control and per-flow resource management.

10.1. Overview

Path-state allows intermediate nodes to forward packets according to
a predetermined source route, even when most packets do not include order in which they occur in the full source route. Conceptually, Options field within the originator of each data
packet initially includes both
option.

Any DSR routing information carried in a source route packet SHOULD be examined
and a unique path
identifier reflected in each the node's Route Cache, even if the options in
the packet it sends. As intermediate nodes forward are not otherwise processed as described above. In
particular, the packet, they cache following routing information SHOULD be handled in
this way:

- In a DSR Route Request option, the source accumulated route from record,
represented by the packet, indexed IP Source Address of the packet and by the path identifier. The source can then send subsequent packets
carrying only
sequence of Address[i] entries in the path identifier, since intermediate nodes will Route Request option SHOULD
be
able added to forward the packet based on node's Route Cache.

- In a DSR Route Reply option, the source route for the path
that they have cached.

While path-state allows record being returned,
represented by the elimination sequence of Address[i] entries in the source route from each
packet, thereby reducing Route
Request option and by the overhead of Destination Address in the DSR protocol, it also
provides a way for sources packet's IP
header SHOULD be added to monitor the state of each path through the network. When node's Route Cache.

- In a source wishes DSR Acknowledgement option, the single link from the
ACK Source Address to know the characteristics of
a path through ACK Destination Address SHOULD be added
to the network, it piggybacks node's Route Cache.

- In a path-metrics header
onto any data or control packet traversing the path. As DSR Route Error option, the
packet propagates through single link from the network, each intermediate node
updates
Error Source Address to the set of path-metrics carried by Unreachable Node Address MUST be
removed from the packet to reflect node's Route Cache.

- In a DSR Routing header, the local network conditions seen at indicated source route SHOULD be
added to the node. These metrics are
reflected back node's Route Cache, subject to the sender by conditions
identified in Section 3.3.1. The full sequence of hops in the destination, along with
DSR Routing header is as follows:

* The Source Address in the path
identifier, and enable packet's IP header is the first hop
(the sender to track the value of these metrics
for each of the source routes it packet).

* Let n equal Hdr Ext Len. This 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 number of addresses in
the state Routing header. Let i equal n minus Segments Left.

* The sequence of hops

Address[1], Address[2], ..., Address[i]

follow immediately after the network. For example, by including ``available bandwidth''
or ``battery level'' as a metric, senders can load balance IP Source Address in the consumption of resources across source
route.

* The Destination Address in the network. We have also
considered packet's IP header follows
immediately next in the possibility source route.

* The sequence of replacing hops

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

follow next in the TCP congestion control
algorithm with a ``leaky-bucket'' system controlled by source route. The address Address[n]
above is the reflected
path-metrics --- our measured performance results show this could
dramatically improve TCP throughput final hop in environments where many
packets are lost due to packet corruption. The feedback could also
be used as inputs the source route.

In addition to other researcher's systems for improving the
transport layer, such as Liu and Singh's ATCP [11], or for adaptation
at higher layers, as in Odyssey [13].

Flow-state allows processing of received packets described above, a source
node SHOULD examine the packet to differentiate its traffic into
flows, and then request better-than-best-effort handling determine if the receipt of this
packet indicates an opportunity for these
flows. With automatic route shortening, as
described in Section 3.4.2. If the additional information provided by received packet satisfies the flow-state,
tests described there, then this node SHOULD perform the network can provide admission control and promise a specific
Quality following
sequence of Service (QoS) steps:

- Return a gratuitous Route Reply to each flow. Since the ad hoc network may
frequently change topology, IP Source Address of the flow-state mechanisms are directly
integrated into
packet, as described in Section 3.4.2.

- Discard the routing protocol to minimize their reaction time
and provide notifications to a flow when received packet, since the network must break packet has been received
before its
promise for a specific level normal traversal of QoS.

10.2. Path-State and Flow-State Identifiers

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 packet's source route would
have caused it to reach this receiving node. Another copy of routing information and flow-state is
the
fundamental unit packet will normally arrive at this node as indicated in
the packet's source route; discarding this initial copy of Quality the
packet, which triggered the gratuitous Route Reply, will prevent
the duplication of Service information.

Path-state is associated with this packet that would otherwise occur.

6.1.4. Processing a particular set of hops through the
network from some source S to Routing Header in a destination D (i.e., Received Packet

A Routing header in a particular
source route packet is not examined or processed until the
packet reaches the node identified in the network). It consists of Destination Address field
in the information needed
to route packets along packet's IP header. In that node, dispatching on the path, and information about Protocol
field in the carrying
capacity of packet's IP header (or the path, such as Next Header field in the unused bandwidth along
preceding extension header) causes the path or Routing header module in that
node's IP implementation to be invoked. The node then examines the
Routing Type field in the minimum latency of Routing header to determine the path.

Flow-state is specific to a particular class
type of packets flowing
between S and D processing for that is routed over a given path. Flow-state is
used to record Quality type of Service promises that have been made Routing header. The processing
for a
particular flow, and allows packets from S to D that take the same
path through the network to be treated differently by intermediate
nodes. For example, all Routing header here in general follows the TCP connections between S procedures specified
for IPv6 Routing headers, and D that
take the same path will share the same path-state, but may have
independent flow-state. At any point in time, S may use multiple
paths processing specifically for its traffic 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 DSR
Routing header in general follows the network, we use general procedures specified
for a scheme
inspired by Type 0 Routing header in IPv6 [7].

If, while processing a received packet, a node encounters a Routing
header with an unrecognized Routing Type value, the Virtual Path Index and Virtual Circuit Index required behavior
of
ATM networks [23, p. 451]. Paths are identified by the logical
concatenation node depends on the value of the source Segments Left field, as
follows:

- If Segments Left is 0, the node address MUST ignore the Routing header
and a 16-bit path identifier
where proceed to process the low 5 bits are 0. Flows are next header in the packet, whose type
is identified by a path
identifier where the low 5 bits are used to distinguish between Next Header field in the
different flows that use Routing header.

- If Segments Left is non-zero, the same path.

This scheme has two main advantages. First, each source node can
independently generate globally unique path- MUST discard the packet
and flow-identifiers.
Second, send an ICMP Parameter Problem, Code 0, message [24] to
the hierarchical relation of flow-identifiers packet's Source Address, pointing to
path-identifiers means that many flows from the same source unrecognized
Routing Type.

If, after processing a Routing header in a received packet, an
intermediate node can
share the same path-state, which reduces the overhead of maintaining determines that the routing information. The drawback packet is that if a flow must to be
rerouted, its flow identifier will change. However, when forwarded onto
a flow link whose link MTU is
rerouted the QoS metadata must be renegotiated anyway, so changing
flow identifiers will not create needless additional work in less than the
network.

10.3. Path-State Creation, Use, and Maintenance

The path-state portion size of the protocol has two major goals. The
first goal is to ensure sufficient state exists at packet, the nodes along a
path from a source S node
MUST discard the packet and send an ICMP Packet Too Big message to
the packet's Source Address [24].

A DSR Routing header is identified by a destination D so that packets from S to D
do not need to carry Routing Type value of ???
in the complete source route. The second goal Routing header. A DSR Routing header for IPv4 is processed
according to allow S to discover the characteristics following sequence of a particular path to D
so that it can adapt its sending pattern to steps:

- If the capabilities value of the
path, or even choose a different path entirely.

The Segments Left field in the Routing header
equals 0, then proceed to process the next sections describe how header in the packet,
whose type is identified by the Next Header field in the Routing
header. Do not process the path-state Routing header further.

- Else, let n equal Hdr Ext Len. This is created, how the
characteristics number of addresses
in the Routing header.

- If the value of the path are discovered, and what metrics can be
used Segments Left field is greater than n, then
send an ICMP Parameter Problem, Code 0, message [24] to the IP
Source Address, pointing to characterize the path.

10.3.1. Creating Path-State for Segments Left field, and discard
the packet. Do not process the Routing

To create header further.

- Else, decrement the path-state, we assume that Route Discovery proceeds as
normal in DSR. Once value of the source node S has obtained a source route to Segments Left field by 1. Let i
equal n minus Segments Left. This is the destination D, it begins sending data packets index of the next
address to D as normally
done be visited in DSR, with each packet carrying a full source route header.
Internally, S assigns a path-identifier to that particular source
route and stores the path-identifier in its route cache along with Address vector.

- If Address[i] or the source route. S IP Destination Address is a multicast
address, then includes discard the path-identifier as part of packet. Do not process the

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

(a) Packet with path identifier Routing
header further.

- Else, swap the IP Destination Address and source route.

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

(b) Packet with path identifier only.

Figure 2: Path identifiers assigned to a source route by Address[i].

- Forward the
originating node A enable later packets packet to omit the source route.

source route header as shown IP address specified in Figure 2(a). As each intermediate
node processes the source route to forward the packet, it also stores the source route in its route cache, indexed by
Destination Address field of the source IP header, following normal IP
forwarding procedures, including checking and
path-identifier.

After sending a packet containing both decrementing the
Time-to-Live (TTL) field in the source route and packet's IP header [25, 3]. In
this forwarding of the
path-identifier into packet, the network, S can begin sending subsequent
packets to D without a full source route --- carrying only next hop node (identified by
the
path-identifier Destination Address) MUST be treated as shown in Figure 2(b). Each intermediate node
receiving such a packet queries its route cache to find the route direct neighbor
node; the packet is supposed transmission to take, and determines its that next hop. As
explained node MUST be done in Section 10.5, if the cached source route is not
available at some intermediate node, S will receive a single
IP forwarding hop, without Route Error Discovery and
can then correct the situation.

10.3.2. Monitoring Characteristics of without searching
the Path Route Cache.

- In order to support network layer services such as balancing the
traffic load across forwarding the network, end-systems must have a method packet, perform Route Maintenance for
determining the characteristics next
hop of the paths through the network that
they could use. While many schemes have been proposed packet, by which the
end-systems themselves can measure verifying that the characteristics of a path
(e.g., TCP congestion window and RTT calculations [1, 22, 24] and
SPAND [21]), we hypothesize that, particularly packet was received by
that next hop, as described in the Section 6.3.

Multicast addresses must not appear in a DSR Routing header or in
the dynamic
environment IP Destination Address field of an ad hoc network, more useful, more accurate, and
more timely information can be developed a packet carrying a DSR Routing
header.

6.2. Route Discovery Processing

Route Discovery is the mechanism by enlisting which a node S wishing to send a
packet to a destination node D obtains a source route to D. Route
Discovery is used only when S attempts to send a packet to D and
does not already know a route to D. The node initiating a Route
Discovery is known as the aid "initiator" of the
nodes along the path to measure the path characteristics.

We propose that each node can measure the activity around itself, Route Discovery, and thereby determine information such as: the mean latency it adds
to
destination node for which the packets it forwards and Route Discovery is initiated is known
as the latency variation (jitter); "target" of the
number Route Discovery.

Route Discovery operates entirely on demand, with a node initiating
Route Discovery based on its own origination of additional new packets per second it believes for
some destination address to which it can process; does not currently know a
route. Route Discovery does not depend on any periodic or the unused amount background
exchange of wireless media capacity routing information or neighbor node detection at any
layer in the air around
the network protocol stack at any node. Experimentation will be required to discover exactly
which metrics will prove to be accurately measurable

The Route Discovery procedure utilizes two types of messages, a DSR
Route Request (Section 5.1.1) and useful,
though Section 10.3.3 provides several proposals. If a DSR Route Reply (Section 5.2.1),
to actively search the metrics
kept by each node on ad hoc network for a path are combined, route to the result should desired
destination. These DSR messages MAY be a
characterization carried in any type of the path that the packet sender can IP
packet, through use to
organize or adapt its offered load.

To implement this scheme, we first define a new type of extension
header for DSR than can be piggybacked onto headers as described in Section 5:
a packet Route Request is carried in the same way
as the existing DSR headers. This new header a Destination options extension header,
and a Route Reply is called carried in a Hop-by-Hop options extension
header.

A Route Discovery for a destination SHOULD NOT be initiated unless
the path
metrics header (written as Measure) and conceptually consists of initiating node has a packet in the
path-identifier of Send Buffer requiring
delivery to that destination. A Route Discovery for a given target
node MUST NOT be initiated unless permitted by the path along which rate-limiting
information contained in the metrics are measured, Route Request Table. After each
Route Discovery attempt, the type interval between successive Route
Discoveries for this target must be doubled, up to a maximum of the Measure,
MAX_REQUEST_PERIOD.

6.2.1. Originating a Route Request

A node initiating a Route Discovery for some target creates and the metrics themselves encoded in
initializes a TLV
format (Section 10.6.2).

Whenever DSR Route Request option in some IP packet. This
MAY be a sender S wishes separate IP packet, used only to measure carry this Route Request
option, or the characteristics of a path
it is using, it includes node MAY include the Measure header Route Request option in any some
existing packet it sends
along that path, setting the type of the header needs to record. As each send to the target node along (e.g., the path forwards IP
packet originated by this node, that caused the packet, it updates node to attempt Route
Discovery for the variables
inside destination address of the Measure packet).

The Route Request option MUST be included in a Destination Options
extension header with in the metrics it has measured locally.
When packet. To initialize the header reaches Route Request
option, the final destination D, D sets node performs the type following sequence of steps:

- The Option Type in the Measure header option MUST be set to return and piggybacks the header into any
packet headed back to S. Since value ???.

- The Option Length field in the path metrics header includes option MUST be set to the path-identifier value 6.
The total size of the path along which it was measured, S can
include the data into its route cache for future use, and can treat Route Request option when initiated is
8 octets; the receipt of Option Length field excludes the path metrics header as a positive acknowledgment
that size of the path-state between S
Option Type and D for Option Length fields themselves.

- The Identification field in the given path-identifier
is correctly option MUST be set up. This could lead S to cease including source
routes in the packets it sends along the path, as described in
Section 10.3.1.

If we find a new
value, different from that it is valuable to immediately provide S with the path
metrics of every discovered route, we could alter used for other Route Discovery
slightly to generate Requests recently
initiated by this information. Currently, if an intermediate node. For example, each node has a cached route that it can use to answer MAY maintain a Route Request,
it generates
single counter value for generating a Route Reply itself. Instead, we could require it to
place its proposed route on the new Identification value
for each Route Request (turning it from a
flood-fill broadcast into a unicast packet) and send initiates.

- The Target Address field in the packet option MUST be set to the destination so it will measure IP
address that is the metrics target of the complete path. this Route Discovery.

The destination will then return Source Address in the metrics to IP header of this packet MUST be the source along with node's
own IP address. The Destination Address in the Route Reply as described above.

We have been intending to experiment with IP header of this alteration to
packet MUST be the IP "limited broadcast" address (255.255.255.255).

A node MUST maintain in its Route Discovery for some time, since Request Table, information about
Route Requests that it offers two benefits,
even without path-state metrics. It should decrease initiates. When initiating a new Route
Request, the node MUST use the information recorded in the Route
Request Table entry for the
number target of broken routes returned by that Route Discovery since
each cached route is tested before being returned, Request, and it should save us from jeopardizing one data packet MUST
update that information in the table entry for
every bad route use in someone's cache. The cost is some extra
latency on the next Route Discovery.

10.3.3. Candidate Metrics
Request initiated for this target. In order to limit the additional overhead that collecting and
distributing path-state metrics will place on particular:

- The Route Request Table entry for a target node records the network, all
Time-to-Live (TTL) field used in the
metrics must have IP header of the property last Route
Request initiated by this node for that target node. This
value allows the amount of space required node to
express the metric does not increase as the number implement a variety of hops on algorithms
for controlling the
path increases. Experimentation will be required to determine which
metrics are most accurately measured and most useful, but our initial
set spread of candidates includes the following:

- Interface queue length --- Our previous work [12] has shown that
this is its Route Request on each Route
Discovery initiated for a good estimator of local congestion.

- Rate target. As examples, two possible
algorithms for this use of interface queue draining --- When an interface is
backlogged, the rate at which packets leave the queue directly
measures the usable capacity of that interface. TTL field are described in
Section 3.3.4.

- Quiet time fraction --- When an interface is not backlogged, The Route Request Table entry for a target node records the usable capacity
number of the interface can be estimated by
promiscuously listening consecutive Route Requests initiated for this target
since receiving a valid Route Reply giving a route to the media that target
node, and measuring the fraction remaining amount of time during before which it is not in use (though this will
overestimate the capacity).

- Fraction Free Air Time --- The fraction of time our interface
would node MAY
next attempt at a Route Discovery for that target node.

These values MUST be able used to send a packet. That is, implement an exponential back-off
algorithm to limit the fraction of time rate at which this node initiates new
Route Discoveries for the interface does not sense carrier, is not deferring, and same target address. Until a valid
Route Reply is
not backed off. Current experiments show received for this is an excellent
predictor of congestion and available capacity.

- Forwarding latency and variation --- This can be measured
as target node address, the time timeout
between when consecutive Route Discovery initiations for this target
node SHOULD increase by doubling the timeout value on each new
initiation.

The behavior of a node processing a packet containing both a Routing
Header and a Route Request Destination option is received unspecified.
Packets SHOULD NOT contain both a Routing Header and when it a Route Request
Destination option. [This is
acknowledged by the next hop.

- Unidirectional links --- Paths containing unidirectional links
are usable, but undesirable as they increase the overhead of not exactly true: A Route Maintenance.

- Packet loss rate --- Signal quality information from Request
option appearing in the
interface itself, or second Destination Options header that IPv6
allows after the frequency of hop-by-hop retransmission,
can be used to estimate Routing Header would probably do-what-you-mean,
though we have not triple-checked it yet. Namely, it would allow the loss rate of each link.

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

These metrics all have unicast the property that they can request to some other
node, where it would be expressed in
a single value that each node can measure locally. As a packet
with released and begin the flood fill. We call
this a Route Request Blossom since the unicast portion of the path metrics header passes through
looks like a node, stem on the metrics in blossoming flood-fill of the header can request.]

Packets containing a Route Request Destination option SHOULD NOT be updated to reflect
retransmitted, SHOULD NOT request an explicit DSR Acknowledgment by
setting the node's metrics using R bit, SHOULD NOT expect a
combination function like minimum, maximum, sum, or weighted average
that produces another single value to replace the one already in
the header. This updating will passive acknowledgment, and
SHOULD NOT be done at the last possible moment
before the packet is forwarded, placed in order to assure the packet has the
most current metrics on it when it leaves.

10.4. Flow-State Creation, Use, and Maintenance Retransmission Buffer. The flow-state portion repeated
transmission of packets containing a Route Request Destination option
is controlled solely by the protocol enables logic described in this section.

6.2.2. Processing a sender to obtain
promises from all nodes along Received Route Request Option

When a path to node receives a destination that packet containing a
certain set of resources are available along Route Request option, the path, and that
node MUST process the intermediate nodes are committed option according to making these resources
available for the particular flow. This allows following sequence of
steps:

- If the Target Address field in the Route Request matches this
node's own IP address, then the node SHOULD return a sender Route Reply
to obtain
better-than-best-effort Quality the initiator of Service for a flow by obtaining
promises from this Route Request (the Source Address in the intermediate nodes to reserve
IP header of the resources needed
to provide that QoS.

Unlike prior QoS work packet), as described in wired networks, at Section 6.2.4. The
source route for this point we cannot
formally characterize or bound exactly what type reply is the sequence of services hops

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

where initiator is the
flow-state protocol will be able to offer. The goal address of the initiator of this Route
Request, each Address[i] is to provide
CBR and TCP streams with an address from the ability to specify and obtain a
minimum bandwidth Route Request,
and delay/jitter bound. If the environment is
particularly harsh, it is possible that only best-effort service will
be offerable. It target is this intuition that leads us to the system target of
promises and notifications. Experimentally, we hope to determine
how stable and effective this system will be the Route Request (the Target Address
field in a multi-hop ad hoc
network environment.

10.4.1. Requesting Promises along Existing Paths

Similar to the use of Route Request).

The node MUST then continue processing the path metrics header, at packet normally,
including any time a promise
can be requested following options or changed along any path an originator is currently
using. Once an originating extension headers in the
packet. The node has created a path-identifier
for a route through MUST NOT retransmit the network, Route Request to
propagate it can request a promise of
network resources along that route by first generating a new
flow-identifier to identify other nodes. Do not process the promise. The originator then fills
out a flow-request header (written as Flow Request) Route Request
option further.

- Else, the node MUST examine the route recorded in the Route
Request option (the IP Source Address field and inserts it
into any packet sent along that path.

Figure 3 shows the conceptual layout sequence of a Flow Request, which
contains
Address[i] fields) to determine if this node's own IP address
already appears in this list of addresses. If so, the new path-identifier assigned by node MUST
discard the originator, entire packet carrying the
flow-identifier of Route Request option.

- Else, the promise that this request supersedes (if any), node MUST search its Route Request Table for an entry
for the requested lifetime initiator of this Route Request (the IP Source Address
field). If such an entry is found in the promise, and table, the QoS parameters that
describe node MUST
search the requested promise itself. Section 10.6.3 provides cache of Identification values of recently received
Route Requests in that table entry, to determine if an entry
is present in the
detailed packet format. The use of cache matching the minimum Identification value
and requested fields
for the QoS parameters differs depending on whether the Flow Request target node address in this Route Request. If such an
(Identification, target address) entry is piggybacked on a found in this cache in
this entry in the Route Request or not, as described below.

When a Flow Request piggybacked on a unicast packet is received by a
node, Table, then the node performs MUST discard
the following steps: entire packet carrying the Route Request option.

- Else, this node SHOULD repropagate this Route Request. If it
does so, the node is MUST do so according to the destination following sequence
of the packet, it converts the
Flow steps:

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

* Create a Measure with type return copy of this entire packet and uses perform the current
values in following
steps on the desired fields copy of the Flow Request packet.

* Append this node's own IP address to populate the
fields list of the Measure. It then piggybacks the Measure onto any
packet being returned to the originator.

- Else if the intermediate node has available enough resources to
meet the minimum requested promise Address[i]
values in the Flow Route Request, it:

* Sets aside and increase the maximum value of its available resources and the
desired resources. The set aside resources are held
Option Length field in a
tentative promise pool until 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 the Flow Route Request header. by 4 (the size of an
IP address).

* Updates This node SHOULD search its own Route Cache for a route
(from itself, as if it were the desired fields source of the Flow Request a packet) to reflect the resources set aside (there
target of this Route Request. If such a route is questionable value found in a
down stream
its Route Cache, then this node allocating more resources SHOULD follow the procedure
outlined in Section 6.2.3 to return a flow than an
upstream node can currently handle).

* Forward the packet and piggybacked Flow Request "cached Route Reply"
to the next
node on initiator of this Route Request, if permitted by the path.

- Else,
restrictions specified there.

* If the node does not have enough resources to meet the
minimum requested promise, so it sends the originator return a cached Route
Error piggybacked with a Measure reflecting the minimum of the
current values Reply, then this
node SHOULD link-layer re-broadcast this copy of the desired fields in packet,
with a short jitter delay before the Flow Request broadcast is sent. The
jitter period SHOULD be chosen as a random period, uniformly
distributed between 0 and BROADCAST_JITTER.

6.2.3. Generating Route Replies using the
available resources. The type field Route Cache

As described in Section 3.3.2, it is set to refused. Such possible for a
Measure enables the originator node processing a
received Route Request to learn three things: that its
requested cannot be satisfied along avoid propagating the given path; Route Request further
toward the identity target of the bottleneck node; and the available resources up to and
through the bottleneck node.

When the originating Request, if this node receives a Measure header of type return
for a flow on which it has an outstanding Flow Request, it accepts
the promised level of service by changing the type of the Measure
header to confirm and piggybacking the header on any packet going
along the flow. This informs the intermediate nodes to move the set
aside resources from the tentative promise pool to the allocated
pool, and enables upstream nodes to free any set aside resources in
excess of the capacity of its Route Cache
a bottleneck downstream node.

The use of the old flow-id to recycle resources is important for two
reasons. First, it enables an originator route from itself to attempt this target. Such a Route Reply generated by
a node from its own cached route to increase or
decrease the amount target of a current promise without losing the resources
it already has promised. Second, both packet loss Route Request is
called a "cached Route Reply", and this mechanism can greatly reduce
the expanding
ring search overall overhead of Route Discovery may result in several Flow Requests
being sent for the same flow. If subsequent Flow Requests for a
flow were not able to notify intermediate nodes that they can reuse
resources set aside while processing earlier Flow Requests, on the network could quickly reach a state where admissible flows are being
needlessly rejected.

10.4.2. Requesting Promises as Part by reducing
the flood of Route Discovery Requests. The scheme for requesting promises general processing of a received
Route Request is described in the previous Section 6.2.2; this section
has specifies
the advantage additional requirements that it enables an originator to request or update MUST be met before a promise cached Route
Reply may be generated and returned and specifies the procedure for
returning such a flow along any route currently in its route cache,
regardless of how it obtained the route. For the common case in
which cached Route Reply.

While processing a received Route Request, for a node wishes to obtain possibly
return a resource promise for cached Route Reply, it MUST have in its Route Cache a new flow route
from itself to
a previously unknown destination, we can integrate the flow request
with the target of this Route Discovery Request. However, before
generating a cached Route Reply for the destination.

Integrating the flow request with this Route Discovery enables us to avoid Request, the inefficiency of discovering routes node MUST
verify that will not be usable by there are no duplicate addresses listed in the route
accumulated in the
flow due to insufficient resources. The integration of flow requests
with Route Discovery also allows us to avoid a common pitfall of
QoS schemes that layer a reservation signaling protocol on top of
a unicast routing algorithm --- schemes without tight integration
will refuse admissible flows whenever Request together with the unicast routing algorithm
directs route from this
node's Route Cache. Specifically, there MUST be no duplicates among
the request packets into a congested area following addresses:

- The IP Source Address of the network,
unless packet containing the signaling protocol also provides a method to backtrack Route Request,

- The Address[i] fields in the request Route Request, and

- The nodes listed in the route around obtained from this node's Route
Cache, excluding the congested area. Utilizing address of this node itself (this node
itself is the same
mechanisms currently used common point between the route accumulated in the
Route Discovery, we can avoid Request and the need
for backtracking.

We call route obtained from the combination of flow requests with Route Discovery
QoS-guided Route Discovery, which originating nodes can invoke simply
by piggybacking a Flow Request on Cache).

If any duplicates exist among these addresses, then the node MUST NOT
send a cached Route Request. Each Reply. The node
receiving SHOULD continue to process the Flow
Route Request uses the same algorithm as described in Section 10.4.1, with two exceptions:

- Nodes silently discard 6.2.2.

If the Route Request if they can not and the route from the Route Cache meet
minimum requirements the
restriction above, then the node SHOULD construct and return a cached
Route Reply as follows:

- Unless The source route for this 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 Route Request indicates that replying
Request, each Address[i] is an address from cache the Route Request,
and c-route is
forbidden, nodes with a the sequence of hops in the source route to this
target node, obtained from the node's Route Cache. In appending
this cached route to destination unicast the source route for the reply, the address
of this node itself MUST be excluded, since it is already listed
as Address[n].

- Send a Route Reply to the initiator of the Route Request, using
the procedure defined in Section 6.2.4. The initiator of the
Route Request along is indicated in the cached route. Source Address field in the
packet's IP header.

6.2.4. Originating a Route Reply

A node requiring a route with a QoS promise uses the following
algorithm. First, it sends originates a Route Request that permits intermediate
nodes Reply in order to reply from cache. If the network is uncongested, this
should frequently to a received and quickly succeed
processed Route Request, according to the procedures described in returning both a
Sections 6.2.2 and 6.2.3. The Route Reply
and a Measure describing the available QoS along the discovered
path. If after a timeout, the originating node has not received is returned in a DSR Route Reply, it begins another
Reply option (Section 5.2.1). The Route Discovery, this time forbidding
replies from cache, which will force an exploration of all feasible
paths Reply option MAY be returned
to the destination.

This scheme does risk an implosion of unicast Requests at the target initiator of the Route Discovery (e.g., if target is Request in a popular server separate IP packet, used
only to which
many nodes have cached routes). At the cost of additional complexity
and soft-state, carry this Route Reply option, or it would MAY be possible included in any
other IP packet being sent to add hold-downs at the nodes
surrounding the target so that only the first few Requests are
forwarded towards the target.

10.4.3. Providing Notifications of Changing Path Metrics

When a node detects that it must break this address.

The Route Reply option MUST be included in a promise, it must notify Hop-by-Hop Options
extension header in the
node packet returned to which it made that promise. It is an open question how the
now reduced resources should be distributed among initiator. To
initialize the flows. We
currently pick Route Reply option, the minimum set of promises to break that leave node performs the
other promises unchanged.

The difficulty in providing notification following
sequence of a changed path metric is
getting this information back to steps:

- The Option Type in the source. When promise must option MUST be
broken at a node B, it sends a Measure set to the originator indicating
what resources are now available. value ???.

- The use of Measure headers Option Length field in the option MUST be set to
determine the currently available resources along a path value
(n * 4) + 1, where n is more
problematic, however, as for every Measure sent by the originator, number of addresses in the destination must send a response containing source
route being returned (excluding the measured metrics.

If Route Discovery initiator
node's address).

- The Last Hop External (L) bit in the traffic is TCP, option MUST be initialized
to 0.

- The Reserved field in the overhead option MUST be initialized to 0.

- The sequence of addresses of the responses source route are low, as
they can be piggybacked on the ACK stream. For one-way CBR traffic
though, introducing copied into
the overhead Address[i] fields of a reverse stream to carry the
changing metrics could option. Address[1] MUST be severe.

If set
to the overhead first hop of the responses becomes a problem, it may be
possible to implement a enhanced piggyback mechanism. The approach
is based on route after the fact that although no work has been exerted to create
hop-by-hop routing information at each node, chances are good that
each node can determine a next-hop for packets headed initiator of the Route
Discovery, Address[n] MUST be set to any known
destination by simply examining its route cache. By piggybacking the Measure header for one last hop onto any packet that is headed to
that next-hop, we can cheaply create a reverse flow of information
that will eventually reach the originator source
route (the address of the Measure. Each
node who receives a Measure with a type target node), and each other Address[i]
MUST be set to the next address in sequence in the source route
being returned.

The Destination Address field in the IP header of return simply piggybacks the Measure for one-hop on packets that seem to be flowing packet carrying
the
right direction back Route Reply option MUST be set to the source. To insure address of the timeliness initiator
of the information, each Measure Route Discovery (i.e., for a Route Reply being returned in
response to an originator could
include a deadline by which some Route Request, the information is supposed to reach IP Source Address of the
originator. If it appears that hop-by-hop propagation will result
in missing Route
Request).

After creating and initializing the deadline, DSR Route Reply option and
the Measure can be unicast as a first-class IP packet to containing it, send the originator.

10.5. Expiration of State from Intermediate Nodes

Since there Route Reply, jittered by
T milliseconds, where T is no guarantee that either the source or destination of a packet flow will be able uniformly distributed random number
between 0 and BROADCAST_JITTER.

If sending a Route Reply to communicate with all of the nodes that
carried originator of the flow when they wish to terminate Route Request
requires performing a Route Discovery, the flow, there must Route Reply hop-by-hop
option MUST be time-based expiration mechanism by which intermediate nodes can
purge piggybacked on the path-state and flow-state from their caches and reclaim packet that contains the
resources set aside to maintain it. However, if intermediate nodes
were to purge Route
Request. This piggybacking prevents a loop wherein 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 a flow-identifier that references
state they no longer hold. Since intermediate nodes do not
necessarily know
new Route Request (which was itself the timing with which originator of the sender originates packets,
an inactivity timer alone would have to be set very conservatively original
Route Request) must do another Route Request in order to
prevent purging the path-state of low bit-rate connections.

To solve return its
Route Reply.

If sending the expiration problem, we take advantage of Route Reply to the relatively
``soft'' nature originator of the path-state and flow-state. When the state
is created, the source node specifies a time after which it should
be discarded (This time will typically be on the order of Route Request
does not require performing Route Discovery, a hundred
seconds). The source node can thereby estimate how often it must
refresh the state, for example, by sending packets that contain SHOULD send a
full source route on them. Should the state have somehow expired
unicast Route Reply in response to every received Route Request
targeted at an intermediate node when a packet labeled with it.

6.2.5. Processing a flow or path
identifier arrives, the intermediate node can return Route Reply Option

Upon receiving a Route Error to
the source Reply, a node specifying ``missing state information'' as SHOULD extract the cause
of source route
from the Error Route Reply and elicit the sender to refresh the missing state.

Since all path-state add this routing information is guaranteed to have expired its Route
Cache. The source route from the network after a bounded amount Route Reply is the sequence 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 hops

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

where initiator is the
Hop-by-Hop options header. This option MAY NOT appear more than once value of the Destination Address field in a single Hop-by-Hop Options header.

Option Type

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

Option Length

8-bit unsigned integer. Length address
of the option, in octets,
excluding initiator of the Option Type Route Discovery), and Option Length fields.

Path-ID

The identifier assigned each Address[i] is a
node through which the source route passes, in turn, on the route to this path by
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 listed
MUST flag the hop Address[n] in its Route Cache as External.

Each packet in the
IP Source Address (Section 10.2).

Flow-ID

The identifier assigned by 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.

6.3. Route Maintenance Processing

Route Maintenance is the mechanism by which node listed as S is able to detect,
while using a source route to D, if the IP Source
Address network topology has changed
such that it can no longer use its route to D because a particular flow link along
the path identified by 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
Path-ID. packet from the next hop. If this portion no
acknowledgement is 0, received, the option names a path, but not node SHOULD return a particular flow.

Discussion: This encoding of Route Error to
the path and flow identifiers will cost
8 bytes IP Source Address of additional header overhead the packet, as described in Section 6.3.3

6.3.1. Using Network-Layer Acknowledgments

When a node retransmits a data packet with or has no other
extensions or options (4 bytes for the Hop-by-Hop options header, and
4 bytes for the identifier option). A more compact encoding would be way to define that, in ensure
successful delivery of a DSR network, an IP destination address with packet to the next hop, it SHOULD request
a
first octet of 127 actually encodes network-layer acknowledgement by placing a non-zero value in the path 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 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

The DSR module
Identification field of the final destination would replace DSR Routing header. Such a value MUST
be unique over all packets delivered to the IP
destination address same next hop which are
either unacknowledged or recently acknowledged.

A node receiving a DSR Routing header with its actual a non-zero value before passing in the packet
up
Identification field MUST send an acknowledgement to the stack for further processing.

This encoding has previous hop
by performing the advantage that it requires no additional
overhead in following sequence of steps:

- Create a data packet. The disadvantage is that if the packet
was somehow received by a DSR-unaware node without first being
processed by a DSR gateway node [4], and set the DSR-unaware node will either
drop IP Source Address to the packet or will attempt address
of this node, the IP Destination Address to receive it locally (since the IP
destination address belongs of the
previous hop, and the IP Protocol field to the loopback subnet).

10.6.2. Path-Metrics Option

Path-metrics are carried as an option inside protocol number
reserved for Hop-by-Hop Options extension headers.

- Set the Hop-by-Hop options
header.

???. A node that does not understand this option should ignore
this option and continue processing Options extension header's Next Header field
to be the packet, and "No Next Header" value. Set the Option
Data does change en-route (the top three bits are 001).

Option Length

8-bit unsigned integer. Header Extension
Length of to the option, in octets,
excluding size of a DSR Acknowledgement Option.

- Set the DSR Acknowledgement option's Option Type and Option Length fields.

Path-ID and Flow-ID

The path identifier of the path that the metrics correspond
to. If field to
the Path-Metrics Option Type equals Measure, then the
Path-ID reserved for DSR Acknowledgements, 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
Option Length field to 10.

- Copy the option should update Identification field from the metrics
to reflect Routing Header into
the conditions at that node.

The metrics Identification field in this option SHOULD NOT be modified by any
intermediate node. They represent the metrics measured
along DSR Acknowledgement Option.
Set the identified path.

Confirm

The metrics ACK Source Address field in this the option MUST NOT to be modified by any
intermediate node. They represent a confirmation by the sender that will transmit traffic conforming IP
Source Address and the ACK Destination Address field to the
listed Quality of Service metrics along IP
Destination Address.

- Send the identified
flow.

Metrics

The individual path-metrics, encoded packet as described in Section 10.6.4. Unknown metrics SHOULD be ignored. If a
single value is provide for the metric, it MUST be interpreted
as the metrics value. 6.1.1.

6.3.2. Using Link Layer Acknowledgments

If two values explicit failure notifications are provided for by the
metric, they MUST link layer,
then all packets are assumed to be interpreted as the range of values taken correctly received by the metric (low value first). It
next hop, and a Route Error is undefined for there to
be more than two values for sent only when an explicit failure
notification is made from the metric.

10.6.3. Flow Request Option

Flow-requests are carried as link layer.

Nodes receiving a packet without a Routing Header do not need to send
an option inside explicit Acknowledgment to the Hop-by-Hop options
header. They allow packet's originator, since the
link layer will notify the originator if the packet was not received
properly.

6.3.3. Originating a sender Route Error

When a node is unable to request that intermediate nodes
reserve sufficient resources for verify successful delivery of a flow packet to provide that flow with
the
QoS characteristics described by 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 next hop after a maximum number of retransmission attempts,
a node that does not understand this option should ignore
this SHOULD send a Route Error to the IP Source Address of the
packet. When sending a Route Error for a packet containing either a
DSR Route Error option and continue processing or a DSR Acknowledgement option, a node SHOULD
add these options to it's Route Error, subject to some limit on
lifetime. Specifically, we define the packet, and "salvage count" of an option
to be the Option
Data does change en-route (the top three bits are 001).

Option Length

8-bit unsigned integer. Length sum of one plus the option, salvage count recorded in octets,
excluding the Option Type and Option Length fields.

old Path-ID and old Flow-ID

The flow identifier provide in DSR
Routing header plus the sum of the salvage counts of any DSR Route
Errors preceding that option.

A node transmitting a previous request which this
request supersedes.

new Path-ID Route Error MUST follow the following steps:

- Create a packet and new Flow-ID

The flow identifier that will be used with to identify set the
packets that should receive IP Source Address to the QoS described by address of
this node, the included
metrics.

Metrics

The metrics that characterize IP Destination Address to the desired QoS, encoded as
described in Section 10.6.4. Unknown metrics SHOULD be
ignored. If a range address IP Source
Address of values are provided for a metric, they
MUST be interpreted as the minimum acceptable value and packet experiencing the
desired value.

10.6.4. Encoding Path-Metrics

Each path-metric is encoded in error.

- Insert 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 of metric

R bit

If 0, Hop-by-Hop Options Header into the data is packet.

- Add a list of discrete values Route Error Option, setting the metric can
or did take. If 1, Error Type to
NODE_UNREACHABLE, the Reserved bits to 0, the data represent a range of values Salvage value to
one plus the metric can or did take. If a single metric Salvage value is
supplied, from the range is assumed to be 0 <= metric <= value. If
two metric values are supplied, DSR Routing header, and the range is assumed
Unreachable Node Address to be
value1 <= metric <= value2.

Option Length

8-bit unsigned integer. Length the address of the metric, in octets,
excluding next hop. Set
the Type Error Source Address to the IP Source Address and Length fields.

The currently defined metric types follow:

Padding

Type: 0 the Error
Destination to the IP Destination Address.

- The padding metric is special node MAY append each DSR Route Error and DSR Acknowledgement,
in that order, from the packet experiencing the error, though it contains no length field and
no data.

Available Capacity

Type: 1
Data encoded MUST
exclude options with salvage counts greater than 15.

- Send the packet as

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

where 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:

- Delete all routes from the value Route Cache that have a link from the
Route Error Source Address to the Unreachable Node Address.

- If the Hop-by-Hop option following the Route Error is (Mantissa << Shift) bits per second.

Delay a DSR
Acknowledgement or DSR Route Error option sent by this node
(that is, with Acknowledgement or Error Source Address equal to
this node's address), copy the Hop-by-Hop options following the
current Route Error into a new packet with IP Source Address
equal to this node's own IP address and Delay Variation

Data encoded IP Destination Address
equal to the Acknowledgement or Error Destination Address.
Transmit this 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 - Delay Variation

The value is described in Section 6.1.1, with the standard deviation of Delay,
salvage count in milliseconds.

Link Bidirectionality

Type: 16 - 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 is the number DSR Routing header 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.

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 retransmission attempts
and 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 Routing header with a new
Routing Header in the same way as described in Section 6.1.2, 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.

11. Routing Header that caused the error.

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

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

12.

8. IANA Considerations

This document proposes the use in IPv4 of the Destination Options header and
extension header, the Hop-by-Hop Options extension header, and
Routing header, which were originally defined for IPv6, in IPv4. IPv6 [7]. The
Next Header values indicating these two three extension headers thus header types (60,
0, and 43, respectively) must therefore be reserved within the IPv4
Protocol number space.

Furthermore, In addition, the "No Next Header" type value
of 69, defined for IPv6, must also be defined for use in IPv4. Other
protocols in IPv4 wishing to use these IPv6-style extension headers
can also make use of these Protocol number assignments.

For use within a Destination Options extension header, this document
defines four one new types type of destination
options, each of option, which must be assigned an
Option Type value:

- The DSR Route Request option, described in Section 7.1.1

- 5.1.1. The top
three bits of this Option Type value MUST be 011.

For use within a Hop-by-Hop Options extension header, this document
defines three new types of hop-by-hop options, each of which must be
assigned an Option Type value:

- DSR Route Reply option, described in Section 7.2.1

- 5.2.1. The top
three bits of this Option Type value MUST be 000.

- DSR Route Error option, described in Section 7.2.2

- 5.2.2. The top
three bits of this Option Type value MUST be 000.

- DSR Acknowledgment option, described in Section 7.2.3

DSR also requires 5.2.3. The top
three bits of this Option Type value MUST be 000.

For use within a Routing header, this document defines one new type
of routing header header, which must be assigned an Routing Type be allocated for the value:

- DSR Source Route Routing Header, defined in Section 7.3.

In IPv4, we require two new protocol numbers be issued to identify
the next header as either an IPv6-style destination option, or an
IPv6-style routing 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.

13. 5.3.

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.

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], [25], IPv6 [6], [7], and IPX [7] [28] 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) [23], as well as from the routing
mechanism used in IEEE 802 source routing bridges [15]. ARP [16] is a [22]. 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 [20]
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. types forming an ad hoc network.

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]. [20].

The software is currently being was ported to FreeBSD 3.3.

Implementors notes:

- Added field to Route Error

Acknowledgments 3.3, and 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
seprate 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, 19] and conducted
evaluations of different caching strategies documented in this
draft [9].

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

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
at Carnegie Mellon University. Bob ported our DSR implementation
from FreeBSD 2.2.7 into FreeBSD 3.3.

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]

[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 Maltz. Protocols for adaptive
wireless and mobile networking. IEEE Personal Communications,
3(1):34--42, February 1996.

[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] S.B. Lee, A. Gahng-Seop, X. Zhang, and A.T. Campbell. INSIGNIA:
An IP-Based Quality of Service Framework for Adaptive
Wireless and Mobile Networking. IEEE Personal Communications,
3(1):34--42, February 1996.

[11] Jian Liu Ad Hoc
Networks. Journal of Parallel and Distributed Computing,
60(4):374--406, April 2000.

[19] 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]

[20] 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.

[13] Brian D. Noble, M. Satyanarayanan, Dushyanth Narayanan,
Eric J. Tilton, Jason Flinn, and Kevin R. Walker. Agile
Application-Aware Adaptation for Mobility.

[21] David A. Maltz, Josh Broch, and David B. Johnson. Quantitative
lessons from a full-scale multi-hop wireless ad hoc network
testbed. In Proceedings of the 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] IEEE Wireless Communications and
Networking Conference, September 2000.

[22] Radia Perlman. Interconnections: Bridges and Routers.
Addison-Wesley, Reading, Massachusetts, 1992.

[16]

[23] 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]

[24] J. Postel. B. Postel, editor. Internet Control Message Protocol.
RFC 792, September 1981.

[25] J. B. Postel, editor. Internet Protocol. RFC 791, September
1981.

[18]

[26] 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.

[27] 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.

[28] 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. 25--91, September
1990.

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

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 dmaltz@cs.cmu.com
Palo Alto, CA 94306
USA

Yih-Chun Hu Phone: +1 412 268-3075
Carnegie Mellon University Fax: +1 412 268-5576
Computer Science Department Email: yihchun@cs.cmu.edu
5000 Forbes Avenue
Pittsburgh, PA 15213-3891
USA

Jorjeta G. Jetcheva Phone: +1 412 268-7399 268-3053
Carnegie Mellon University Fax: +1 412 268-5576
Email: dbj@cs.cmu.edu

David A. Maltz
Carnegie Mellon University
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