IETF MANET Working Group Yih-Chun Hu, Rice University
INTERNET-DRAFT David B. Johnson, Rice University
David A. Maltz, AON Networks
23 February 2001
Flow State in the Dynamic Source Routing Protocol
for Mobile Ad Hoc Networks
<draft-ietf-manet-dsrflow-00.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."
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.
Abstract
This document defines an extension to the Dynamic Source Routing
protocol (DSR), a simple and efficient routing protocol designed
specifically for use in multi-hop wireless ad hoc networks of mobile
nodes. DSR enables the sender of a packet to determine the sequence
of nodes through with the packet must be forwarded to reach the
intended destination node, and to route that packet along that
sequence of hops by including a source route header in the packet.
All aspects of the protocol operate entirely on-demand, allowing the
routing packet overhead of DSR to scale automatically to only that
needed to react to changes in the routes currently in use. The DSR
extension defined in this document, known as "flow state", allows the
routing of most packets without an explicit source route header in
the packet, further reducing the overhead of the protocol while still
preserving the fundamental properties of DSR's operation.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page i]
INTERNET-DRAFT Flow State in DSR 23 February 2001
Contents
Status of This Memo i
Abstract i
1. Introduction 1
2. DSR Flow State Overview 2
2.1. Flow Establishment . . . . . . . . . . . . . . . . . . . 2
2.2. Receiving and Forwarding Establishment Packets . . . . . 3
2.3. Sending Packets Along Established Flows . . . . . . . . . 3
2.4. Receiving and Forwarding Packets Sent Along Established
Flows . . . . . . . . . . . . . . . . . . . . . . . . 4
2.5. Processing Errors . . . . . . . . . . . . . . . . . . . . 5
2.6. Automatic Route Shortening . . . . . . . . . . . . . . . 5
2.7. Loop Detection . . . . . . . . . . . . . . . . . . . . . 6
2.8. Acknowledgement Destination . . . . . . . . . . . . . . . 6
2.9. Crash Recovery . . . . . . . . . . . . . . . . . . . . . 6
2.10. Rate Limiting . . . . . . . . . . . . . . . . . . . . . . 6
2.11. Interaction with Salvaging . . . . . . . . . . . . . . . 7
3. Conceptual Data Structures 8
3.1. Flow Table . . . . . . . . . . . . . . . . . . . . . . . 8
3.2. Automatic Route Shortening Table . . . . . . . . . . . . 9
3.3. Default Flow ID Table . . . . . . . . . . . . . . . . . . 9
4. Packet Formats 10
4.1. DSR Flow State Header . . . . . . . . . . . . . . . . . . 11
4.2. DSR Header Options and Extensions . . . . . . . . . . . . 12
4.2.1. Virtual Route Option . . . . . . . . . . . . . . 12
4.2.2. Timeout Option . . . . . . . . . . . . . . . . . 13
4.2.3. Destination and Flow ID Option . . . . . . . . . 14
4.2.4. New Error Type Value for Unknown Flow . . . . . . 15
4.2.5. New Error Type Value for Default Flow Unknown . . 16
4.2.6. Acknowledgement Request Option
Previous Hop Address Extension . . . . . . 17
5. Detailed Operation 18
5.1. Originating a Packet . . . . . . . . . . . . . . . . . . 18
5.1.1. Inserting a DSR Flow State Header . . . . . . . . 20
5.2. Receiving a Packet . . . . . . . . . . . . . . . . . . . 20
5.3. Forwarding a Packet Using Flow IDs . . . . . . . . . . . 24
5.4. Promiscuously Receiving a Packet . . . . . . . . . . . . 24
5.5. Operation Where the Layer Below DSR Decreases the IP TTL
Non-Uniformly . . . . . . . . . . . . . . . . . . . . 25
5.6. Salvage Interactions with DSR . . . . . . . . . . . . . . 25
Hu, Johnson, and Maltz Expires 23 July 2001 [Page ii]
INTERNET-DRAFT Flow State in DSR 23 February 2001
6. IANA Considerations 26
7. Security Considerations 26
Implementation Status 27
References 28
Chair's Address 29
Authors' Addresses 30
Hu, Johnson, and Maltz Expires 23 July 2001 [Page iii]
INTERNET-DRAFT Flow State in DSR 23 February 2001
1. Introduction
The Dynamic Source Routing protocol (DSR) is a simple and efficient
routing protocol designed specifically for use in multi-hop wireless
ad hoc networks of mobile nodes. DSR enables the sender of a packet
to determine the sequence of nodes through with the packet must
be forwarded to reach the intended destination node, and to route
that packet along that sequence of hops by including a source route
header in the packet. All aspects of the protocol operate entirely
on-demand, allowing the routing packet overhead of DSR to scale
automatically to only that needed to react to changes in the routes
currently in use.
This document defines an extension to the DSR protocol, known as
"flow state", that allows the routing of most packets without an
explicit source route header in the packet, further reducing the
overhead of the protocol while still preserving the fundamental
properties of DSR's operation. Once a sending node has discovered
a source route such as through DSR's Route Discovery mechanism, the
flow state mechanism allows the sending node to establish hop-by-hop
forwarding state within the network, based on this source route, to
enable each node along the route to forward the packet to the next
hop based on the node's own local knowledge of the flow along which
this packet is being routed. Flow state is dynamically initialized
by the first packet using a source route and is then able to route
subsequent packets along the same flow without use of a source route
header in the packet. The state established at each hop along a flow
is "soft state" and thus automatically expires when no longer needed.
This document relies on the base specification of the DSR protocol
for routing unicast IP packets [2]. The flow state extension
described here is fully compatible with nodes implementing that base
specification.
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 [1].
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 1]
INTERNET-DRAFT Flow State in DSR 23 February 2001
2. DSR Flow State Overview
2.1. Flow Establishment
A source node sending packets to some destination node MAY use the
DSR flow state extension described here to establish a route to
that destination as a flow. A "flow" is a route from the source to
the destination represented by hop-by-hop forwarding state within
the nodes along the route. Each flow is uniquely identified by a
combination of the source node address, the destination node address,
and a flow identifier (flow ID) chosen by the source node.
Each flow ID is a 16-bit unsigned integer. Comparison between
different flow IDs MUST be performed modulo 2**16. For example,
using an implementation in the C programming language, a
flow ID value (a) is greater than another flow ID value (b) if
((short)((a) - (b)) > 0), if a C language "short" data type is
implemented as a 16-bit signed integer.
A DSR Flow State header in a packet identifies the flow ID to
be followed in forwarding that packet. From a given source to
some destination, any number of different flows MAY exist and
be in use, for example following different sequences of hops to
reach the destination. One of these flows may be considered to be
the "default" flow from that source to that destination. A node
receiving a packet with neither a DSR header [2] specifying the route
to be taken (with a Source Route option in the DSR header) nor a DSR
Flow State header specifying the flow to be followed, is forwarded
along the default flow for the source and destination addresses
specified in the packet's IP header.
In establishing a new flow, the source node generates a nonzero
16-bit flow ID greater than any unexpired flow IDs for this
(source, destination) pair. If the source wishes for this flow to
become the default flow, the low bit of the flow ID MUST be set (the
flow ID is an odd number); otherwise, the low bit MUST NOT be set
(the flow ID is an even number).
The source node establishing the new flow then transmits a packet
containing a DSR header with a Source Route option, as defined in the
base specification for DSR [2]; to establish the flow, the source
node also MUST include in the packet a DSR Flow State header, with
the Flow ID field set to the chosen flow ID for the new flow, and
MUST include a Timeout option in the DSR header, giving the lifetime
after which information about this flow is to expire.
The source node also records this flow in its Flow Table for future
use, setting the TTL in this Flow Table entry to be the value used in
the TTL field in the packets's IP header and setting the Lifetime in
this entry to be the lifetime specified in the Timeout option in the
DSR header.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 2]
INTERNET-DRAFT Flow State in DSR 23 February 2001
Any further packets sent with this flow ID before the timeout that
also contain a DSR header with a Source Route option MUST use this
same source route in the Source Route option.
2.2. Receiving and Forwarding Establishment Packets
Packets intended to establish a flow, as described in Section 2.1,
contain a DSR header with a Source Route option, and are forwarded
along the indicated route according to the procedures defined in
the base DSR specification [2]. A node implementing the DSR flow
state extension, when receiving and forwarding such a DSR packet,
also keep some state in its own Flow Table to enable it to forward
future packets that are sent along this flow with only the flow ID
specified. Specifically, if the packet also contains a DSR Flow
State header, this packet SHOULD cause an entry to be established for
this flow in the Flow Table of each node along the packet's route.
The Hop Count field of the DSR Flow State header is also stored in
the Flow Table, as is Lifetime Option specified in the DSR header.
If the Flow ID is odd and there is no flow in the Flow Table with
Flow ID greater than the received Flow ID, set the default Flow ID
for this (IP Source Address, IP Destination Address) pair to the
received Flow ID, and the TTL of the packet is recorded.
The Flow ID Option is removed before final delivery of the packet.
2.3. Sending Packets Along Established Flows
When a flow is established as described in Section 2.1, a packet
is sent which establishes state in each node along the route.
This state is soft; that is, the protocol contains mechanisms for
recovering from the loss of this state. However, the use of these
mechanisms may result in reduced performance for packets sent
along flows with forgotten state. As a result, it is desirable
to differentiate behavior based on whether or not the sender is
reasonably certain that the flow state exists on each node along
the route. We define a flow's state to be "established end-to-end"
if the Flow Tables of all nodes on the route contains forwarding
information for that flow. While it is impossible to detect whether
or not a flow's state has been established end-to-end without sending
packets, implementations may make reasonable assumptions about the
retention of flow state and the probability that an establishment
packet has been seen by all nodes on the route.
A source wishing to send a packet along an established flow
determines if the flow state has been established end-to-end. If it
has not, a DSR header with Source Route option with this flow's route
is added to the packet. The source SHOULD set the Flow ID field of
the DSR Flow State header either to the flow ID previously associated
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 3]
INTERNET-DRAFT Flow State in DSR 23 February 2001
with this flow's route or to zero. If it sets the Flow ID field to
any other value, it MUST follow the processing steps in Section 2.1
for establishing a new flow ID. If it sets the Flow ID field to a
nonzero value, it MUST include a Timeout option with a value not
greater than the timeout remaining in the node's Flow Table, and if
its TTL is not equal to that specified in the flow table, the flow
MUST NOT be used as a default flow in the future.
Once flow state has been established end-to-end for non-default
flows, a source adds a DSR Flow State header to each packet it wishes
to send along that flow, setting the Flow ID field to the flow ID of
that flow. A Source Route option SHOULD NOT be added to the packet,
though if one is, then the steps for processing flows that have not
been established end to end MUST be followed.
Once flow state has been established end-to-end for default flows,
sources sending packets with IP TTL equal to the TTL value in the
local Flow Table entry for this flow then transmit the packet to
the next hop. In this case, a DSR Flow State header SHOULD NOT be
added to the packet and a DSR header likewise SHOULD NOT be added to
the packet; though if one is, the steps for sending packets along
non-default flows MUST be followed. If the IP TTL is not equal to
the TTL value in the local Flow Table, then the steps for processing
a non-default flow MUST be followed.
2.4. Receiving and Forwarding Packets Sent Along Established Flows
The handling of packets containing a DSR header with both a nonzero
Flow ID and a Source Route option is described in Section 2.2. The
handling of packets with a Source Route option and Flow ID equal
to zero is described in the base specification. This section only
describes handling of packets without a Source Route option.
If a node receives a packet with a Flow ID that indicates a flow not
currently in the node's Flow Table, it returns a Route Error of type
Unknown Flow. It MAY attempt to salvage the packet, though if it
does, it MUST zero the Flow ID.
If a node receives a packet with a Flow ID in the DSR header that
indicates an unexpired flow in the node's Flow Table, it increments
the Hop Count in the DSR header and forwards the packet to the next
hop indicated in the Flow Table.
If a node receives a packet with no DSR header and no DSR Flow State
header, it checks the Default Flow Table. If there is no entry, it
returns a Route Error of type Default Flow Unknown. It may attempt
to salvage the packet, though if it does, it MUST zero the Flow ID.
If there is an entry, it forwards to the next hop indicated in the
Flow Table for the default flow.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 4]
INTERNET-DRAFT Flow State in DSR 23 February 2001
2.5. Processing Errors
When a node receives a Route Error of type Unknown Flow, it marks
the flow to indicate that it has not been established end-to-end.
When a node receives a Route Error of type Default Flow Unknown, it
marks the default flow to indicate that it has not been established
end-to-end.
2.6. Automatic Route Shortening
Because a full source route is not carried in every packet, an
alternate method for performing automatic route shortening is
necessary. Instead, nodes promiscuously listen to packets, and
if a node receives a packet with (source, destination, Flow ID)
found in the Flow table but the packet is not MAC addressed to the
node, it determines whether the packet was sent by an upstream or
downstream node by examining the Hop Count field in the DSR header.
If the Hop Count field is lower than the expected Hop Count at this
node, the node assumes that the packet was sent by an upstream
node, and adds the packet to an Automatic Route Shortening table,
possibly evicting an earlier packet added to this table. When the
packet is then sent to that node for forwarding, it finds that it
has previously received the packet by checking the Automatic Route
Shortening table, and returns a gratuitous Route Reply to the source
of the packet.
When a packet does not contain a DSR header, the node promiscuously
receiving a packet assumes that the Flow ID is the default flow
for the IP Source and IP Destination. To determine whether the
packet was sent by an upstream or downstream node, it examines the
IP TTL field; if the IP TTL field is higher than the TTL recorded
during establishment, the packet is added to an Automatic Route
Shortening table. As in the case of packets with DSR headers, when
the packet is then sent to that node for forwarding, it finds that it
has previously received the packet by checking the Automatic Route
Shortening table, and returns a gratuitous Route Reply to the source
of the packet.
In order for this technique to work, each node in a route must
decrement the TTL by a uniform amount for each packet. If any
node intends to change the TTL of a packet sent using default flow
forwarding by an amount different from the change in TTL of that
flow's establishment packet, it MUST add a DSR header specifying the
Hop Count of this node as well as the Flow ID that the packet was
sent along.
If a DSR packet is received from the previous hop using default flow
forwarding, and the packet has an unexpected TTL, the receiving node
MUST insert a DSR header specifying the Hop Count of this node as
well as the Flow ID of the default flow.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 5]
INTERNET-DRAFT Flow State in DSR 23 February 2001
2.7. Loop Detection
If a node receives a packet for forwarding with adjusted TTL
lower than expected and default flow forwarding is being used, it
sends a Route Error of type Default Flow Unknown back to the IP
source. It can attempt delivery of the packet by normal salvaging
(subject to constraints described in Section 5.6) or by inserting a
Flow ID option with Special TTL extension based on what that node's
understanding of the default Flow ID and TTL.
2.8. Acknowledgement Destination
In the base specification, nodes sending Acknowledgements determine
the previous hop by examining the Source Route option. In packets
sent using Flow State, the previous hop is not necessarily known.
In order to allow nodes that have lost flow state to determine the
previous hop, the address of the previous hop can optionally be
stored in the Acknowledgement Request. This extension SHOULD NOT be
used when a Source Route option is present, MAY be used when flow
state routing is used without a Source Route option, and SHOULD be
used before Route Maintenance determines that a packet cannot be
successfully sent.
2.9. Crash Recovery
Each node has a maximum Timeout value that it can possibly generate.
This can be based on the largest number that can be set in a timeout
option (2**16 - 1 seconds) or set in system software. When a node
crashes, it does not establish new flows for a period equal to this
maximum Timeout value, in order to avoid colliding with its old
Flow IDs.
2.10. Rate Limiting
Flow IDs can be assigned with a counter. More specifically, the
"Current Flow ID" is kept. When a new default Flow ID needs to be
assigned, if the Current Flow ID is odd, the Current Flow ID is
assigned as the Flow ID and the Current Flow ID is incremented by
one; if the Current Flow ID is even, one plus the Current Flow ID is
assigned as the Flow ID and the Current Flow ID is incremented by
two.
If Flow IDs are assigned in this way, one algorithm for avoiding
duplicate, unexpired Flow IDs is to rate limit new Flow IDs to an
average rate of n assignments per second, where n is 2**15 divided by
the maximum Timeout value. This can be averaged over any period not
exceeding the maximum Timeout value.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 6]
INTERNET-DRAFT Flow State in DSR 23 February 2001
2.11. Interaction with Salvaging
Salvaging in the base protocol is modified to zero the Flow ID field.
Also, any time the base DSR specification refers to the Salvage field
in the Source Route option in a DSR header, packets without a Source
Route option are considered to have the value zero in the Salvage
field.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 7]
INTERNET-DRAFT Flow State in DSR 23 February 2001
3. Conceptual Data Structures
This section describes conceptual data structures added to those in
the base specification. In an implementation of the protocol, these
data structures MAY be implemented in any manner consistent with the
external behavior described in this document.
3.1. Flow Table
The Flow Table records information about flows from which packets
have been recently sent or forwarded by this node. The table is
indexed by a triple (IP Source Address, IP Destination Address,
Flow ID), where Flow ID is a 16-bit token assigned by the source as
described in Section 2.1. The table
- MUST keep outgoing interface
- MUST keep outgoing MAC destination
- MUST keep a timeout
- MUST keep a Hop Count
- MUST keep an expected TTL
- MUST keep an indication of whether or not this flow can be used
as default if the source is this node and the Flow ID is odd
- SHOULD keep expected previous hop
- SHOULD keep the complete source route (Nodes not keeping complete
source route information cannot participate in Automatic Route
Shortening)
- SHOULD keep a flag indicating whether or not the next hop of this
flow is in range
- MAY keep a last-used time
- MAY keep a list of all links in this flow
The entry MUST be deleted when the timeout expires.
The flag indicating whether or not the next hop of this flow is in
range essentially serves as a negative cache of this link and can
reduce the number of transmission attempts along broken links.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 8]
INTERNET-DRAFT Flow State in DSR 23 February 2001
3.2. Automatic Route Shortening Table
The Automatic Route Shortening Table records packets for which
Automatic Route Shortening may be possible. The table is indexed by
a triple (IP Source Address, IP Destination Address, Flow ID), and
- MUST keep a list of (Packet, Shortened Route) pairs
- MAY expire packets at any time
3.3. Default Flow ID Table
For each (source, destination) pair for which a node forwards
packets, it MUST record:
- the largest odd Flow ID seen
- the time at which all of this pair's flows that are forwarded by
this node expire
- the current canonical Flow ID
- a flag indicating whether or not the current canonical Flow ID is
valid
If a node deletes this record for a (source, destination) pair,
it MUST also delete all Flow Table entries for that (source,
destination) pair. Nodes MUST delete table entries if all of this
pair's flows that are forwarded by this node expire.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 9]
INTERNET-DRAFT Flow State in DSR 23 February 2001
4. Packet Formats
The DSR flow state extension requires a new header type, the DSR Flow
State header.
In addition, this extension adds the following three options for the
DSR header defined in the base DSR specification:
- Virtual Route Option
- Timeout Option
- Destination and Flow ID Option
Two new Error Type values are defined for use in the Route Error
option in a DSR header:
- Unknown Flow
- Default Flow Unknown
Finally, an extension to the Acknowledgement Request option in a DSR
header is also defined:
- Previous Hop Address
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 10]
INTERNET-DRAFT Flow State in DSR 23 February 2001
4.1. DSR Flow State Header
The DSR Flow State header is a small 4-byte header optionally used to
carry the flow ID and hop count for a packet being sent along a DSR
flow.
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 | Hop Count | Flow Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Next Header
8-bit selector. Identifies the type of header immediately
following the Destination Options header. Uses the same values
as the IPv4 Protocol field [3].
Hop Count
8-bit unsigned integer. The number of hops through which this
packet has been forwarded.
Flow Identification
The flow ID for this flow, as described in Section 2.1.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 11]
INTERNET-DRAFT Flow State in DSR 23 February 2001
4.2. DSR Header Options and Extensions
4.2.1. Virtual Route Option
A Virtual Route is defined for use in a DSR header to indicate that
a DSR node processing the DSR header should stop processing further
options after this point in the header. This option is encoded as
follows:
0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Option Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type
8
Option Length
8-bit unsigned integer. Length of the option, in octets,
excluding the Option Type and Option Length fields.
When no extensions are present, the Option Length of a Virtual
Route Option is 0. Further extensions to DSR may include
additional data in a Virtual Route Option. The presence of
such extensions is indicated by an Option Length greater
than 0. Currently, no such extensions have been defined.
The Virtual Route option MAY appear one or more times within a DSR
header.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 12]
INTERNET-DRAFT Flow State in DSR 23 February 2001
4.2.2. Timeout Option
The Timeout option is defined for use in a DSR header to indicate the
amount of time before the expiration of the flow ID along which the
packet is being sent.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Option Length | Timeout |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type
9
Option Length
8-bit unsigned integer. Length of the option, in octets,
excluding the Option Type and Option Length fields.
When no extensions are present, the Option Length of a Timeout
Option is 2. Further extensions to DSR may include additional
data in a Timeout Option. The presence of such extensions is
indicated by an Option Length greater than 2. Currently, no
such extensions have been defined.
Timeout
The number of seconds for which this flow remains valid.
The Timeout option MUST NOT appear more than once within a DSR
header.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 13]
INTERNET-DRAFT Flow State in DSR 23 February 2001
4.2.3. Destination and Flow ID Option
The Destination and Flow ID option is defined for use in a DSR header
to send a packet to an intermediate host along one flow, for eventual
forwarding to the final destination along a different flow. This
option enables the aggregation of the state of multiple flows.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Option Length | New Flow Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| New IP Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type
10
Option Length
8-bit unsigned integer. Length of the option, in octets,
excluding the Option Type and Option Length fields.
When no extensions are present, the Option Length of a
Destination and Flow ID Option is 6. Further extensions to
DSR may include additional data in a Destination and Flow ID
Option. The presence of such extensions is indicated by an
Option Length greater than 6. Currently, no such extensions
have been defined.
New Flow Identifier
Indicates the next identifier to store in the Flow ID field of
the DSR header.
New IP Destination Address
Indicates the next address to store in the Destination Address
field of the IP header.
The Destination and Flow ID Option MAY appear one or more times
within a DSR header.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 14]
INTERNET-DRAFT Flow State in DSR 23 February 2001
4.2.4. New Error Type Value for Unknown Flow
A new Error Type value of 129 (Unknown Flow) is defined for use in a
Route Error option in a DSR header. The Type-Specific Information
for errors of this type is encoded as follows:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Original IP Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Flow~ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Original IP Destination Address
The IP Destination Address of the packet that caused the error.
Flow ID
The Flow ID contained in the DSR Flow ID Option that caused the
error.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 15]
INTERNET-DRAFT Flow State in DSR 23 February 2001
4.2.5. New Error Type Value for Default Flow Unknown
A new Error Type value of 130 (Default Flow Unknown) is defined for
use in a Route Error option in a DSR header. The Type-Specific
Information for errors of this type is encoded as follows:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Original IP Destination Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Original IP Destination Address
The IP Destination Address of the packet that caused the error.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 16]
INTERNET-DRAFT Flow State in DSR 23 February 2001
4.2.6. Acknowledgement Request Option Previous Hop Address Extension
When the Option Length field of an Acknowledgement Request option in
a DSR header is greater than or equal to 6, a Previous Hop Address
Extension is present. The option is then formatted as follows:
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option Type | Option Length | Packet Identifier |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| ACK Request Source Address |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Option Type
5
Option Length
8-bit unsigned integer. Length of the option, in octets,
excluding the Option Type and Option Length fields.
When no extensions are present, the Option Length of a
Acknowledgement Request Option is 2. Further extensions to
DSR may include additional data in a Acknowledgement Request
Option. The presence of such extensions is indicated by an
Option Length greater than 2.
Currently, one such extension has been defined. If the
Option Length is at least 6, then a ACK Request Source Address
is present.
Packet Identifier
The Packet Identifier field is set to a unique number and is
copied into the Identification field of the DSR Acknowledgement
option when returned by the node receiving the packet over this
hop.
ACK Request Source Address
The address of the node requesting the DSR Acknowledgment.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 17]
INTERNET-DRAFT Flow State in DSR 23 February 2001
5. Detailed Operation
5.1. Originating a Packet
When originating any packet to be routed using flow state, a node
using DSR Flow State MUST:
- If the route to be used for this packet has never had a DSR Flow
State established along it:
* Generate a 16-bit Flow ID larger than any unexpired Flow IDs
used for this destination. Odd Flow IDs MUST be chosen for
"default" flows; even Flow IDs MUST be chosen for non-default
flows
* Add a DSR header, as specified in the base DSR protocol
specification
* Add a DSR Flow State header, as described in Section 5.1.1
* Set the Flow ID field in the DSR Flow State header to the
Flow ID generated in the first step
* Add a Timeout Option to the DSR header
* Add a Source Route option after the Timeout Option with the
route to be used, as specified in the base DSR protocol
specification
* The source SHOULD record this flow in its Flow Table
* If this flow is recorded in the Flow Table, the TTL MUST be
set to be the TTL of the flow establishment packet.
* If this flow is recorded in the Flow Table, the timeout MUST
be set to a value no less than the value specified in the
Timeout Option.
- If the route to be used for this packet has had DSR Flow State
established along it, but has not been established end-to-end
* Add a DSR header, as specified in the base DSR protocol
specification
* Add a DSR Flow State header, as described in Section 5.1.1
* The Flow ID field of the DSR Flow State header SHOULD be the
Flow ID previously used for this route. If it is not, the
steps for sending packets along never before established
routes MUST be followed in place of these.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 18]
INTERNET-DRAFT Flow State in DSR 23 February 2001
* Add a Timeout Option to the DSR header, setting the Timeout
to a value not greater than the timeout remaining for this
flow in the Flow Table.
* Add a Source Route option after the Timeout Option with the
route to be used, as specified in the base DSR protocol
specification
* If the IP TTL is not equal to the TTL specified in the Flow
Table, the source MUST set a flag to indicate that this flow
cannot be used as default.
- If the route the node wishes to use for this packet has been
established end-to-end and is not default
* Add a DSR Flow State header, as described in Section 5.1.1
* The Flow ID field of the DSR Flow State header SHOULD be the
Flow ID previously used for this route. If it is not, the
steps for sending packets along never before established
routes MUST be followed in place of these.
* If the next hop requires a Hop-by-Hop acknowledgement,
add a DSR header, as specified in the base DSR protocol
specification, and an Acknowledgement Request Option, as
specified in the base DSR protocol specification.
* A DSR header SHOULD NOT be added to a packet, unless it is
added to carry an Acknowledgement Request Option, in which
case:
+ A Source Route option in the DSR header SHOULD NOT be
added.
+ If a Source Route option in the DSR header is added,
the steps for sending packets along routes not yet
established end-to-end MUST be followed in place of
these.
+ A Timeout Option SHOULD NOT be added.
+ If a Timeout Option is added, it MUST specify a timeout
not greater than the timeout remaining for this flow in
the Flow Table.
- If the route the node wishes to use for this packet has been
established end-to-end and is the current default
* If the IP TTL is not equal to the TTL specified in the Flow
Table, the source MUST follow the steps for sending a packet
along a non-default flow that has been established end-to-end
in place of these steps.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 19]
INTERNET-DRAFT Flow State in DSR 23 February 2001
* If the next hop requires a Hop-by-Hop acknowledgement, the
sending node MUST add a DSR header and an Acknowledgement
Request Option, as specified in the base DSR protocol
specification. The sending node MUST NOT add any additional
options to this header.
* A DSR header SHOULD NOT be added, except as specified in
the previous step. If one is added in a way inconsistent
with the previous step, the source MUST follow the steps
for sending a packet along a non-default flow that has been
established end-to-end in place of these steps.
5.1.1. Inserting a DSR Flow State Header
A node originating a packet adds a DSR Flow State header to the
packet, if necessary, to carry information needed by the routing
protocol. Only one DSR Flow State header may be in any packet.
A DSR Flow State header is added to a packet by performing the
following sequence of steps:
- Insert a DSR Flow State header after the IP header and any
Hop-by-Hop Options header that may already be in the packet, but
before any other header that may be present.
- Set the Next Header field of the DSR Flow State header to the
Next Header field of the previous header (either an IP header or
a Hop-by-Hop Options header).
- Set the Next Header field of the previous header to the Protocol
number assigned to DSR Flow State headers.
5.2. Receiving a Packet
This section describes processing only for packets that are sent to
the processing node; that is, when the MAC Destination Address is the
MAC address of the processing node. Otherwise, the process described
in Sections 5.4 should be followed.
The flow that a packet is being sent along is considered to be in the
Flow Table if the triple (IP Source Address, IP Destination Address,
Flow ID) has an unexpired entry in the flow table.
When a node using DSR Flow State receives a packet, it MUST follow
the following steps for processing:
- If a DSR Flow State header is present, increment the Hop Count
field
- If the triple (IP Source Address, IP Destination Address,
Flow ID) is in the Automatic Route Shortening table, and the
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 20]
INTERNET-DRAFT Flow State in DSR 23 February 2001
packet is in the entry, the node MAY send a Gratuitous Reply as
described in the base specification, giving any routes by which
the packet originally reached this node, subject to the rate
limiting specified in the base DSR protocol specification. If
no DSR Flow State header is present, and no Source Route option
is present, then for the purposes of this step, the Flow ID is
equal to the default Flow ID in the Default Flow Table for the
(IP Source Address, IP Destination Address) pair. If no DSR Flow
State header is present but a Source Route option is present,
skip this step.
- Process each of the Options within the DSR header in order:
* On receiving a Pad1 or PadN option, skip over the option
* On receiving a Route Request for which this node is the
destination, remove the option and return a Route Reply as
specified in the base DSR protocol specification
* On receiving a broadcast Route Request that this node has not
previously seen for which this node is not the destination,
append this node's incoming interface address to the Route
Request, continue propagating the Route Request as specified
in the base DSR protocol specification, send the payload, if
any, to the network layer, and stop processing.
* On receiving a Route Request that this node has not
previously seen for which this node is not the destination,
discard the packet and stop processing.
* On receiving any Route Request, add appropriate links to the
cache, as specified in the base DSR protocol specification.
* On receiving a Route Reply that this node is the Requester
for, remove the Route Reply from the packet and process it as
specified in the base DSR protocol specification.
* On receiving any Route Reply, add appropriate links to the
cache, as specified in the base DSR protocol specification.
* On receiving any Route Error of type NODE_UNREACHABLE, remove
appropriate links to the cache, as specified in the base DSR
protocol specification.
* On receiving a Route Error of type NODE_UNREACHABLE that this
node is the Error Destination Address of, remove the Route
Error from the packet and process it as specified in the base
DSR protocol specification. It also MUST stop originating
packets along any flows using the link from Error Source
Address to Unreachable Node, and it MAY remove from its Flow
Table any flows using the link from Error Source Address to
Unreachable Node.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 21]
INTERNET-DRAFT Flow State in DSR 23 February 2001
* On receiving a Route Error of type UNKNOWN_FLOW that this
node is the Error Destination Address of, remove the Route
Error from the packet and mark the flow specified by the
triple (Error Destination Address, Original IP Destination
Address, Flow ID) as not having been established end-to-end.
* On receiving a Route Error of type DEFAULT_FLOW_UNKNOWN that
this node is the Error Destination Address of, remove the
Route Error from the packet and mark the default flow between
the Error Destination Address and the Original IP Destination
Address as not having been established end-to-end.
* On receiving a Acknowledgment Request option, the receiving
node removes the Acknowledgement Request option and replies
to the previous hop with a Acknowledgement option. If the
previous hop cannot be determined, the Acknowledgement
Request option is discarded, and processing continues.
* On receiving a Acknowledgement option, the receiving node
removes the Acknowledgement option and processes it.
* On receiving any Acknowledgement option, add the appropriate
link to the cache, as specified in the base DSR protocol
specification.
* On receiving any Source Route option, add appropriate
links to the cache, as specified in the base DSR protocol
specification.
* On receiving a Source Route option and either no DSR Flow
State header is present, the flow this packet is being sent
along is in the Flow Table, or no Timeout Option preceded
the Source Route option in this DSR header, process it as
specified in the base DSR protocol specification. Stop
processing this packet unless the last address in the Source
Route option is an address of this node.
* On receiving a Source Route option in a packet with a DSR
Flow State header, and the Flow ID specified in the DSR Flow
State header is not in the Flow Table, add the flow to the
Flow Table, setting the Timeout value to a value not greater
than the Timeout field of the Timeout Option in this header.
If no Timeout Option preceded the Source Route option in this
header, the flow MUST NOT be added to the Flow Table.
If the Flow ID is odd and larger than any unexpired, odd
Flow IDs, it is set to be default in the Default Flow ID
Table.
Then process the Route Option as specified in the base DSR
protocol specification. Stop processing this packet unless
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 22]
INTERNET-DRAFT Flow State in DSR 23 February 2001
the last address in the Source Route option is an address of
this node.
* On receiving a Virtual Route Option, when the IP Destination
Address is an address of this node, discard the Option and
continue processing.
* On receiving a Virtual Route Option, when the IP Destination
Address is not an address of this node, forward the packet
according to the Flow ID, as described in Section 5.3 stop
processing this packet.
* On receiving a Timeout Option, check if this packet contains
a DSR Flow State header. If this packet does not contain a
DSR Flow State header, discard the Option. Otherwise, record
the Timeout value in the option for future reference. The
value recorded SHOULD be discarded when the node has finished
processing this DSR header. If the flow that this packet is
being sent along is in the Flow Table, it MAY set the flow to
time out no more than Timeout seconds in the future.
* On receiving a Destination and Flow ID Option, if the
IP Destination Address is not an address of this node,
forward the packet according to the Flow ID, as described in
Section 5.3, and stop processing this packet.
* On receiving a Destination and Flow ID Option, if the IP
Destination Address is an address of this node, set the
IP Destination Address to the New IP Destination Address
specified in the option, and set the Flow ID to the New
Flow Identifier. Then remove the Option from the packet and
continue processing.
- If the IP Destination Address is an address of this node, remove
the DSR header, if any, and pass the packet up the network stack
and stop processing.
- If there is still a DSR header containing no options, remove the
DSR header.
- If there is still a DSR Flow State header, forward the packet
according to the Flow ID, as described in Section 5.3.
- If there is neither a DSR header nor a DSR Flow State header, but
there is an entry in the Default Flow Table for the (IP Source
Address, IP Destination Address) pair:
* If the IP TTL is not equal to the TTL expected in the Flow
Table, insert a DSR Flow State header, setting Hop Count
equal to the Hop Count of this node, and the Flow ID equal
to the default Flow ID found in the table, and forward this
packet according to the Flow ID, as described in Section 5.3.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 23]
INTERNET-DRAFT Flow State in DSR 23 February 2001
* Otherwise, follow the steps for forwarding the packet using
Flow IDs described in Section 5.3, but taking the Flow ID to
be the default Flow ID found in the table.
- If there is no DSR header, no DSR Flow State header, and no
default flow can be found, the node returns a Route Error of
type Default Flow Unknown to the IP Source Address, specifying
the IP Destination Address as the Original IP Destination in the
type-specific field.
5.3. Forwarding a Packet Using Flow IDs
To forward a packet using Flow IDs, a node MUST follow the following
sequence of steps:
- If the triple (IP Source Address, IP Destination Address,
Flow ID) is not in the Flow Table, return a Route Error of type
Unknown Flow.
- If a hop-by-hop acknowledgement is required for the next hop, the
node MUST include an Acknowledegment Request option as specified
in the base DSR protocol specification. If no DSR header is in
the packet for the Acknowledgement Request option to be attached
to, it MUST be included, as specified in the base DSR protocol
specification, except that it MUST be added after the DSR Flow
State header, if one is present.
- Attempt to transmit this packet to the next hop as specified in
the Flow Table, performing Route Maintenance to detect broken
routes.
5.4. Promiscuously Receiving a Packet
This section describes processing only for packets that have MAC
destinations other than the processing node. Otherwise, the process
described in Section 5.2 should be followed.
When a node using DSR Flow State promiscuously overhears a packet, it
SHOULD follow the following steps for processing:
- If the packet has a DSR Flow State header, and if the triple (IP
Source Address, IP Destination Address, Flow ID) is in the Flow
Table and the Hop Count is less than the Hop Count in the flow's
entry, the node MAY retain the packet in the Automatic Route
Shortening table. If it can be determined that this Flow ID has
been recently used, it SHOULD retain the packet in the Automatic
Route Shortening table.
- If the packet has neither a DSR Flow State header nor a Source
Route option, and a Default Flow ID can be found in the Default
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 24]
INTERNET-DRAFT Flow State in DSR 23 February 2001
Flow Table for (IP Source Address, IP Destination Address), and
the IP TTL is greater than the TTL in the table for the default
flow, the node MAY retain the packet in the Automatic Route
Shortening table. If it can be determined that this Flow ID has
been recently used, it SHOULD retain the packet in the Automatic
Route Shortening table.
5.5. Operation Where the Layer Below DSR Decreases the IP TTL
Non-Uniformly
Some nodes may use an IP tunnel as a DSR hop. If different packets
sent along this IP tunnel can take different routes, the reduction
in IP TTL across this link may be different for different packets.
This prevents the Automatic Route Shortening and Loop Detection
functionality from working properly when used in conjunction with
default routes.
Nodes forwarding packets without a Source Route option on to a link
with unpredictable TTL changes MUST ensure that a DSR Flow State
header is present, indicating the correct Hop Count and Flow ID.
5.6. Salvage Interactions with DSR
Nodes salvaging packets MUST remove the DSR Flow State header, if
present.
Any time the base specification refers to the Salvage field in the
Source Route option, packets without a Source Route option are
considered to have the value zero in the Salvage field.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 25]
INTERNET-DRAFT Flow State in DSR 23 February 2001
6. IANA Considerations
This document contains no new IANA considerations beyond those
required by the base DSR protocol specification [2].
7. Security Considerations
All security considerations outlined in the base DSR protocol
specification [2] apply to this document as well.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 26]
INTERNET-DRAFT Flow State in DSR 23 February 2001
Implementation Status
A preliminary version of the flow state modifications described here
was implemented in FreeBSD 3.3. A demonstration of this modified
version of DSR was presented in July 2000.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 27]
INTERNET-DRAFT Flow State in DSR 23 February 2001
References
[1] Scott Bradner. Key words for use in RFCs to indicate requirement
levels. RFC 2119, March 1997.
[2] David B. Johnson, David A. Maltz, Yih-Chun Hu, and Jorjeta
Jetcheva. The Dynamic Source Routing protocol for mobile ad hoc
networks. Internet-Draft, draft-ietf-manet-dsr-05.txt, March
2001. Work in progress.
[3] Joyce K. Reynolds and Jon Postel. Assigned numbers. RFC 1700,
October 1994. See also http://www.iana.org/numbers.html.
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 28]
INTERNET-DRAFT Flow State in DSR 23 February 2001
Chair's Address
The MANET Working Group can be contacted via its current chairs:
M. Scott Corson Phone: +1 301 405-6630
Institute for Systems Research Email: corson@isr.umd.edu
University of Maryland
College Park, MD 20742
USA
Joseph Macker Phone: +1 202 767-2001
Information Technology Division Email: macker@itd.nrl.navy.mil
Naval Research Laboratory
Washington, DC 20375
USA
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 29]
INTERNET-DRAFT Flow State in DSR 23 February 2001
Authors' Addresses
Questions about this document can also be directed to the authors:
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
David B. Johnson Phone: +1 713 348-3063
Rice University Fax: +1 713 348-5930
Computer Science Department, MS 132 Email: dbj@cs.rice.edu
6100 Main Street
Houston, TX 77005-1892
USA
David A. Maltz Phone: +1 650 688-3128
AON Networks Fax: +1 650 688-3119
3045 Park Blvd. Email: dmaltz@cs.cmu.edu
Palo Alto, CA 94306
USA
Hu, Johnson, and Maltz Expires 23 July 2001 [Page 30]
