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