idnits 2.17.1 draft-ietf-manet-dsrflow-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- ** Missing expiration date. The document expiration date should appear on the first and last page. == No 'Intended status' indicated for this document; assuming Proposed Standard == The page length should not exceed 58 lines per page, but there was 33 longer pages, the longest (page 0) being 59 lines Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack separate sections for Informative/Normative References. All references will be assumed normative when checking for downward references. Miscellaneous warnings: ---------------------------------------------------------------------------- == The document seems to lack the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. (The document does seem to have the reference to RFC 2119 which the ID-Checklist requires). -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (23 February 2001) is 8460 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Outdated reference: A later version (-10) exists of draft-ietf-manet-dsr-05 ** Downref: Normative reference to an Experimental draft: draft-ietf-manet-dsr (ref. '2') ** Obsolete normative reference: RFC 1700 (ref. '3') (Obsoleted by RFC 3232) Summary: 5 errors (**), 0 flaws (~~), 4 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 1 IETF MANET Working Group Yih-Chun Hu, Rice University 2 INTERNET-DRAFT David B. Johnson, Rice University 3 David A. Maltz, AON Networks 4 23 February 2001 6 Flow State in the Dynamic Source Routing Protocol 7 for Mobile Ad Hoc Networks 9 11 Status of This Memo 13 This document is an Internet-Draft and is in full conformance with 14 all provisions of Section 10 of RFC 2026 except that the right to 15 produce derivative works is not granted. 17 Internet-Drafts are working documents of the Internet Engineering 18 Task Force (IETF), its areas, and its working groups. Note 19 that other groups may also distribute working documents as 20 Internet-Drafts. 22 Internet-Drafts are draft documents valid for a maximum of six months 23 and may be updated, replaced, or obsoleted by other documents at 24 any time. It is inappropriate to use Internet-Drafts as reference 25 material or to cite them other than as "work in progress." 27 The list of current Internet-Drafts can be accessed at 28 http://www.ietf.org/ietf/1id-abstracts.txt 30 The list of Internet-Draft Shadow Directories can be accessed at 31 http://www.ietf.org/shadow.html. 33 Abstract 35 This document defines an extension to the Dynamic Source Routing 36 protocol (DSR), a simple and efficient routing protocol designed 37 specifically for use in multi-hop wireless ad hoc networks of mobile 38 nodes. DSR enables the sender of a packet to determine the sequence 39 of nodes through with the packet must be forwarded to reach the 40 intended destination node, and to route that packet along that 41 sequence of hops by including a source route header in the packet. 42 All aspects of the protocol operate entirely on-demand, allowing the 43 routing packet overhead of DSR to scale automatically to only that 44 needed to react to changes in the routes currently in use. The DSR 45 extension defined in this document, known as "flow state", allows the 46 routing of most packets without an explicit source route header in 47 the packet, further reducing the overhead of the protocol while still 48 preserving the fundamental properties of DSR's operation. 50 Contents 52 Status of This Memo i 54 Abstract i 56 1. Introduction 1 58 2. DSR Flow State Overview 2 59 2.1. Flow Establishment . . . . . . . . . . . . . . . . . . . 2 60 2.2. Receiving and Forwarding Establishment Packets . . . . . 3 61 2.3. Sending Packets Along Established Flows . . . . . . . . . 3 62 2.4. Receiving and Forwarding Packets Sent Along Established 63 Flows . . . . . . . . . . . . . . . . . . . . . . . . 4 64 2.5. Processing Errors . . . . . . . . . . . . . . . . . . . . 5 65 2.6. Automatic Route Shortening . . . . . . . . . . . . . . . 5 66 2.7. Loop Detection . . . . . . . . . . . . . . . . . . . . . 6 67 2.8. Acknowledgement Destination . . . . . . . . . . . . . . . 6 68 2.9. Crash Recovery . . . . . . . . . . . . . . . . . . . . . 6 69 2.10. Rate Limiting . . . . . . . . . . . . . . . . . . . . . . 6 70 2.11. Interaction with Salvaging . . . . . . . . . . . . . . . 7 72 3. Conceptual Data Structures 8 73 3.1. Flow Table . . . . . . . . . . . . . . . . . . . . . . . 8 74 3.2. Automatic Route Shortening Table . . . . . . . . . . . . 9 75 3.3. Default Flow ID Table . . . . . . . . . . . . . . . . . . 9 77 4. Packet Formats 10 78 4.1. DSR Flow State Header . . . . . . . . . . . . . . . . . . 11 79 4.2. DSR Header Options and Extensions . . . . . . . . . . . . 12 80 4.2.1. Virtual Route Option . . . . . . . . . . . . . . 12 81 4.2.2. Timeout Option . . . . . . . . . . . . . . . . . 13 82 4.2.3. Destination and Flow ID Option . . . . . . . . . 14 83 4.2.4. New Error Type Value for Unknown Flow . . . . . . 15 84 4.2.5. New Error Type Value for Default Flow Unknown . . 16 85 4.2.6. Acknowledgement Request Option 86 Previous Hop Address Extension . . . . . . 17 88 5. Detailed Operation 18 89 5.1. Originating a Packet . . . . . . . . . . . . . . . . . . 18 90 5.1.1. Inserting a DSR Flow State Header . . . . . . . . 20 91 5.2. Receiving a Packet . . . . . . . . . . . . . . . . . . . 20 92 5.3. Forwarding a Packet Using Flow IDs . . . . . . . . . . . 24 93 5.4. Promiscuously Receiving a Packet . . . . . . . . . . . . 24 94 5.5. Operation Where the Layer Below DSR Decreases the IP TTL 95 Non-Uniformly . . . . . . . . . . . . . . . . . . . . 25 96 5.6. Salvage Interactions with DSR . . . . . . . . . . . . . . 25 98 6. IANA Considerations 26 100 7. Security Considerations 26 102 Implementation Status 27 104 References 28 106 Chair's Address 29 108 Authors' Addresses 30 109 1. Introduction 111 The Dynamic Source Routing protocol (DSR) is a simple and efficient 112 routing protocol designed specifically for use in multi-hop wireless 113 ad hoc networks of mobile nodes. DSR enables the sender of a packet 114 to determine the sequence of nodes through with the packet must 115 be forwarded to reach the intended destination node, and to route 116 that packet along that sequence of hops by including a source route 117 header in the packet. All aspects of the protocol operate entirely 118 on-demand, allowing the routing packet overhead of DSR to scale 119 automatically to only that needed to react to changes in the routes 120 currently in use. 122 This document defines an extension to the DSR protocol, known as 123 "flow state", that allows the routing of most packets without an 124 explicit source route header in the packet, further reducing the 125 overhead of the protocol while still preserving the fundamental 126 properties of DSR's operation. Once a sending node has discovered 127 a source route such as through DSR's Route Discovery mechanism, the 128 flow state mechanism allows the sending node to establish hop-by-hop 129 forwarding state within the network, based on this source route, to 130 enable each node along the route to forward the packet to the next 131 hop based on the node's own local knowledge of the flow along which 132 this packet is being routed. Flow state is dynamically initialized 133 by the first packet using a source route and is then able to route 134 subsequent packets along the same flow without use of a source route 135 header in the packet. The state established at each hop along a flow 136 is "soft state" and thus automatically expires when no longer needed. 138 This document relies on the base specification of the DSR protocol 139 for routing unicast IP packets [2]. The flow state extension 140 described here is fully compatible with nodes implementing that base 141 specification. 143 The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 144 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 145 document are to be interpreted as described in RFC 2119 [1]. 147 2. DSR Flow State Overview 149 2.1. Flow Establishment 151 A source node sending packets to some destination node MAY use the 152 DSR flow state extension described here to establish a route to 153 that destination as a flow. A "flow" is a route from the source to 154 the destination represented by hop-by-hop forwarding state within 155 the nodes along the route. Each flow is uniquely identified by a 156 combination of the source node address, the destination node address, 157 and a flow identifier (flow ID) chosen by the source node. 159 Each flow ID is a 16-bit unsigned integer. Comparison between 160 different flow IDs MUST be performed modulo 2**16. For example, 161 using an implementation in the C programming language, a 162 flow ID value (a) is greater than another flow ID value (b) if 163 ((short)((a) - (b)) > 0), if a C language "short" data type is 164 implemented as a 16-bit signed integer. 166 A DSR Flow State header in a packet identifies the flow ID to 167 be followed in forwarding that packet. From a given source to 168 some destination, any number of different flows MAY exist and 169 be in use, for example following different sequences of hops to 170 reach the destination. One of these flows may be considered to be 171 the "default" flow from that source to that destination. A node 172 receiving a packet with neither a DSR header [2] specifying the route 173 to be taken (with a Source Route option in the DSR header) nor a DSR 174 Flow State header specifying the flow to be followed, is forwarded 175 along the default flow for the source and destination addresses 176 specified in the packet's IP header. 178 In establishing a new flow, the source node generates a nonzero 179 16-bit flow ID greater than any unexpired flow IDs for this 180 (source, destination) pair. If the source wishes for this flow to 181 become the default flow, the low bit of the flow ID MUST be set (the 182 flow ID is an odd number); otherwise, the low bit MUST NOT be set 183 (the flow ID is an even number). 185 The source node establishing the new flow then transmits a packet 186 containing a DSR header with a Source Route option, as defined in the 187 base specification for DSR [2]; to establish the flow, the source 188 node also MUST include in the packet a DSR Flow State header, with 189 the Flow ID field set to the chosen flow ID for the new flow, and 190 MUST include a Timeout option in the DSR header, giving the lifetime 191 after which information about this flow is to expire. 193 The source node also records this flow in its Flow Table for future 194 use, setting the TTL in this Flow Table entry to be the value used in 195 the TTL field in the packets's IP header and setting the Lifetime in 196 this entry to be the lifetime specified in the Timeout option in the 197 DSR header. 199 Any further packets sent with this flow ID before the timeout that 200 also contain a DSR header with a Source Route option MUST use this 201 same source route in the Source Route option. 203 2.2. Receiving and Forwarding Establishment Packets 205 Packets intended to establish a flow, as described in Section 2.1, 206 contain a DSR header with a Source Route option, and are forwarded 207 along the indicated route according to the procedures defined in 208 the base DSR specification [2]. A node implementing the DSR flow 209 state extension, when receiving and forwarding such a DSR packet, 210 also keep some state in its own Flow Table to enable it to forward 211 future packets that are sent along this flow with only the flow ID 212 specified. Specifically, if the packet also contains a DSR Flow 213 State header, this packet SHOULD cause an entry to be established for 214 this flow in the Flow Table of each node along the packet's route. 216 The Hop Count field of the DSR Flow State header is also stored in 217 the Flow Table, as is Lifetime Option specified in the DSR header. 219 If the Flow ID is odd and there is no flow in the Flow Table with 220 Flow ID greater than the received Flow ID, set the default Flow ID 221 for this (IP Source Address, IP Destination Address) pair to the 222 received Flow ID, and the TTL of the packet is recorded. 224 The Flow ID Option is removed before final delivery of the packet. 226 2.3. Sending Packets Along Established Flows 228 When a flow is established as described in Section 2.1, a packet 229 is sent which establishes state in each node along the route. 230 This state is soft; that is, the protocol contains mechanisms for 231 recovering from the loss of this state. However, the use of these 232 mechanisms may result in reduced performance for packets sent 233 along flows with forgotten state. As a result, it is desirable 234 to differentiate behavior based on whether or not the sender is 235 reasonably certain that the flow state exists on each node along 236 the route. We define a flow's state to be "established end-to-end" 237 if the Flow Tables of all nodes on the route contains forwarding 238 information for that flow. While it is impossible to detect whether 239 or not a flow's state has been established end-to-end without sending 240 packets, implementations may make reasonable assumptions about the 241 retention of flow state and the probability that an establishment 242 packet has been seen by all nodes on the route. 244 A source wishing to send a packet along an established flow 245 determines if the flow state has been established end-to-end. If it 246 has not, a DSR header with Source Route option with this flow's route 247 is added to the packet. The source SHOULD set the Flow ID field of 248 the DSR Flow State header either to the flow ID previously associated 249 with this flow's route or to zero. If it sets the Flow ID field to 250 any other value, it MUST follow the processing steps in Section 2.1 251 for establishing a new flow ID. If it sets the Flow ID field to a 252 nonzero value, it MUST include a Timeout option with a value not 253 greater than the timeout remaining in the node's Flow Table, and if 254 its TTL is not equal to that specified in the flow table, the flow 255 MUST NOT be used as a default flow in the future. 257 Once flow state has been established end-to-end for non-default 258 flows, a source adds a DSR Flow State header to each packet it wishes 259 to send along that flow, setting the Flow ID field to the flow ID of 260 that flow. A Source Route option SHOULD NOT be added to the packet, 261 though if one is, then the steps for processing flows that have not 262 been established end to end MUST be followed. 264 Once flow state has been established end-to-end for default flows, 265 sources sending packets with IP TTL equal to the TTL value in the 266 local Flow Table entry for this flow then transmit the packet to 267 the next hop. In this case, a DSR Flow State header SHOULD NOT be 268 added to the packet and a DSR header likewise SHOULD NOT be added to 269 the packet; though if one is, the steps for sending packets along 270 non-default flows MUST be followed. If the IP TTL is not equal to 271 the TTL value in the local Flow Table, then the steps for processing 272 a non-default flow MUST be followed. 274 2.4. Receiving and Forwarding Packets Sent Along Established Flows 276 The handling of packets containing a DSR header with both a nonzero 277 Flow ID and a Source Route option is described in Section 2.2. The 278 handling of packets with a Source Route option and Flow ID equal 279 to zero is described in the base specification. This section only 280 describes handling of packets without a Source Route option. 282 If a node receives a packet with a Flow ID that indicates a flow not 283 currently in the node's Flow Table, it returns a Route Error of type 284 Unknown Flow. It MAY attempt to salvage the packet, though if it 285 does, it MUST zero the Flow ID. 287 If a node receives a packet with a Flow ID in the DSR header that 288 indicates an unexpired flow in the node's Flow Table, it increments 289 the Hop Count in the DSR header and forwards the packet to the next 290 hop indicated in the Flow Table. 292 If a node receives a packet with no DSR header and no DSR Flow State 293 header, it checks the Default Flow Table. If there is no entry, it 294 returns a Route Error of type Default Flow Unknown. It may attempt 295 to salvage the packet, though if it does, it MUST zero the Flow ID. 296 If there is an entry, it forwards to the next hop indicated in the 297 Flow Table for the default flow. 299 2.5. Processing Errors 301 When a node receives a Route Error of type Unknown Flow, it marks 302 the flow to indicate that it has not been established end-to-end. 303 When a node receives a Route Error of type Default Flow Unknown, it 304 marks the default flow to indicate that it has not been established 305 end-to-end. 307 2.6. Automatic Route Shortening 309 Because a full source route is not carried in every packet, an 310 alternate method for performing automatic route shortening is 311 necessary. Instead, nodes promiscuously listen to packets, and 312 if a node receives a packet with (source, destination, Flow ID) 313 found in the Flow table but the packet is not MAC addressed to the 314 node, it determines whether the packet was sent by an upstream or 315 downstream node by examining the Hop Count field in the DSR header. 316 If the Hop Count field is lower than the expected Hop Count at this 317 node, the node assumes that the packet was sent by an upstream 318 node, and adds the packet to an Automatic Route Shortening table, 319 possibly evicting an earlier packet added to this table. When the 320 packet is then sent to that node for forwarding, it finds that it 321 has previously received the packet by checking the Automatic Route 322 Shortening table, and returns a gratuitous Route Reply to the source 323 of the packet. 325 When a packet does not contain a DSR header, the node promiscuously 326 receiving a packet assumes that the Flow ID is the default flow 327 for the IP Source and IP Destination. To determine whether the 328 packet was sent by an upstream or downstream node, it examines the 329 IP TTL field; if the IP TTL field is higher than the TTL recorded 330 during establishment, the packet is added to an Automatic Route 331 Shortening table. As in the case of packets with DSR headers, when 332 the packet is then sent to that node for forwarding, it finds that it 333 has previously received the packet by checking the Automatic Route 334 Shortening table, and returns a gratuitous Route Reply to the source 335 of the packet. 337 In order for this technique to work, each node in a route must 338 decrement the TTL by a uniform amount for each packet. If any 339 node intends to change the TTL of a packet sent using default flow 340 forwarding by an amount different from the change in TTL of that 341 flow's establishment packet, it MUST add a DSR header specifying the 342 Hop Count of this node as well as the Flow ID that the packet was 343 sent along. 345 If a DSR packet is received from the previous hop using default flow 346 forwarding, and the packet has an unexpected TTL, the receiving node 347 MUST insert a DSR header specifying the Hop Count of this node as 348 well as the Flow ID of the default flow. 350 2.7. Loop Detection 352 If a node receives a packet for forwarding with adjusted TTL 353 lower than expected and default flow forwarding is being used, it 354 sends a Route Error of type Default Flow Unknown back to the IP 355 source. It can attempt delivery of the packet by normal salvaging 356 (subject to constraints described in Section 5.6) or by inserting a 357 Flow ID option with Special TTL extension based on what that node's 358 understanding of the default Flow ID and TTL. 360 2.8. Acknowledgement Destination 362 In the base specification, nodes sending Acknowledgements determine 363 the previous hop by examining the Source Route option. In packets 364 sent using Flow State, the previous hop is not necessarily known. 365 In order to allow nodes that have lost flow state to determine the 366 previous hop, the address of the previous hop can optionally be 367 stored in the Acknowledgement Request. This extension SHOULD NOT be 368 used when a Source Route option is present, MAY be used when flow 369 state routing is used without a Source Route option, and SHOULD be 370 used before Route Maintenance determines that a packet cannot be 371 successfully sent. 373 2.9. Crash Recovery 375 Each node has a maximum Timeout value that it can possibly generate. 376 This can be based on the largest number that can be set in a timeout 377 option (2**16 - 1 seconds) or set in system software. When a node 378 crashes, it does not establish new flows for a period equal to this 379 maximum Timeout value, in order to avoid colliding with its old 380 Flow IDs. 382 2.10. Rate Limiting 384 Flow IDs can be assigned with a counter. More specifically, the 385 "Current Flow ID" is kept. When a new default Flow ID needs to be 386 assigned, if the Current Flow ID is odd, the Current Flow ID is 387 assigned as the Flow ID and the Current Flow ID is incremented by 388 one; if the Current Flow ID is even, one plus the Current Flow ID is 389 assigned as the Flow ID and the Current Flow ID is incremented by 390 two. 392 If Flow IDs are assigned in this way, one algorithm for avoiding 393 duplicate, unexpired Flow IDs is to rate limit new Flow IDs to an 394 average rate of n assignments per second, where n is 2**15 divided by 395 the maximum Timeout value. This can be averaged over any period not 396 exceeding the maximum Timeout value. 398 2.11. Interaction with Salvaging 400 Salvaging in the base protocol is modified to zero the Flow ID field. 401 Also, any time the base DSR specification refers to the Salvage field 402 in the Source Route option in a DSR header, packets without a Source 403 Route option are considered to have the value zero in the Salvage 404 field. 406 3. Conceptual Data Structures 408 This section describes conceptual data structures added to those in 409 the base specification. In an implementation of the protocol, these 410 data structures MAY be implemented in any manner consistent with the 411 external behavior described in this document. 413 3.1. Flow Table 415 The Flow Table records information about flows from which packets 416 have been recently sent or forwarded by this node. The table is 417 indexed by a triple (IP Source Address, IP Destination Address, 418 Flow ID), where Flow ID is a 16-bit token assigned by the source as 419 described in Section 2.1. The table 421 - MUST keep outgoing interface 423 - MUST keep outgoing MAC destination 425 - MUST keep a timeout 427 - MUST keep a Hop Count 429 - MUST keep an expected TTL 431 - MUST keep an indication of whether or not this flow can be used 432 as default if the source is this node and the Flow ID is odd 434 - SHOULD keep expected previous hop 436 - SHOULD keep the complete source route (Nodes not keeping complete 437 source route information cannot participate in Automatic Route 438 Shortening) 440 - SHOULD keep a flag indicating whether or not the next hop of this 441 flow is in range 443 - MAY keep a last-used time 445 - MAY keep a list of all links in this flow 447 The entry MUST be deleted when the timeout expires. 449 The flag indicating whether or not the next hop of this flow is in 450 range essentially serves as a negative cache of this link and can 451 reduce the number of transmission attempts along broken links. 453 3.2. Automatic Route Shortening Table 455 The Automatic Route Shortening Table records packets for which 456 Automatic Route Shortening may be possible. The table is indexed by 457 a triple (IP Source Address, IP Destination Address, Flow ID), and 459 - MUST keep a list of (Packet, Shortened Route) pairs 461 - MAY expire packets at any time 463 3.3. Default Flow ID Table 465 For each (source, destination) pair for which a node forwards 466 packets, it MUST record: 468 - the largest odd Flow ID seen 470 - the time at which all of this pair's flows that are forwarded by 471 this node expire 473 - the current canonical Flow ID 475 - a flag indicating whether or not the current canonical Flow ID is 476 valid 478 If a node deletes this record for a (source, destination) pair, 479 it MUST also delete all Flow Table entries for that (source, 480 destination) pair. Nodes MUST delete table entries if all of this 481 pair's flows that are forwarded by this node expire. 483 4. Packet Formats 485 The DSR flow state extension requires a new header type, the DSR Flow 486 State header. 488 In addition, this extension adds the following three options for the 489 DSR header defined in the base DSR specification: 491 - Virtual Route Option 493 - Timeout Option 495 - Destination and Flow ID Option 497 Two new Error Type values are defined for use in the Route Error 498 option in a DSR header: 500 - Unknown Flow 502 - Default Flow Unknown 504 Finally, an extension to the Acknowledgement Request option in a DSR 505 header is also defined: 507 - Previous Hop Address 509 4.1. DSR Flow State Header 511 The DSR Flow State header is a small 4-byte header optionally used to 512 carry the flow ID and hop count for a packet being sent along a DSR 513 flow. 515 0 1 2 3 516 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 517 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 518 | Next Header | Hop Count | Flow Identifier | 519 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 521 Next Header 523 8-bit selector. Identifies the type of header immediately 524 following the Destination Options header. Uses the same values 525 as the IPv4 Protocol field [3]. 527 Hop Count 529 8-bit unsigned integer. The number of hops through which this 530 packet has been forwarded. 532 Flow Identification 534 The flow ID for this flow, as described in Section 2.1. 536 4.2. DSR Header Options and Extensions 538 4.2.1. Virtual Route Option 540 A Virtual Route is defined for use in a DSR header to indicate that 541 a DSR node processing the DSR header should stop processing further 542 options after this point in the header. This option is encoded as 543 follows: 545 0 1 546 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 547 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 548 | Option Type | Option Length | 549 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 551 Option Type 553 8 555 Option Length 557 8-bit unsigned integer. Length of the option, in octets, 558 excluding the Option Type and Option Length fields. 560 When no extensions are present, the Option Length of a Virtual 561 Route Option is 0. Further extensions to DSR may include 562 additional data in a Virtual Route Option. The presence of 563 such extensions is indicated by an Option Length greater 564 than 0. Currently, no such extensions have been defined. 566 The Virtual Route option MAY appear one or more times within a DSR 567 header. 569 4.2.2. Timeout Option 571 The Timeout option is defined for use in a DSR header to indicate the 572 amount of time before the expiration of the flow ID along which the 573 packet is being sent. 575 0 1 2 3 576 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 577 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 578 | Option Type | Option Length | Timeout | 579 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 581 Option Type 583 9 585 Option Length 587 8-bit unsigned integer. Length of the option, in octets, 588 excluding the Option Type and Option Length fields. 590 When no extensions are present, the Option Length of a Timeout 591 Option is 2. Further extensions to DSR may include additional 592 data in a Timeout Option. The presence of such extensions is 593 indicated by an Option Length greater than 2. Currently, no 594 such extensions have been defined. 596 Timeout 598 The number of seconds for which this flow remains valid. 600 The Timeout option MUST NOT appear more than once within a DSR 601 header. 603 4.2.3. Destination and Flow ID Option 605 The Destination and Flow ID option is defined for use in a DSR header 606 to send a packet to an intermediate host along one flow, for eventual 607 forwarding to the final destination along a different flow. This 608 option enables the aggregation of the state of multiple flows. 610 0 1 2 3 611 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 612 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 613 | Option Type | Option Length | New Flow Identifier | 614 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 615 | New IP Destination Address | 616 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 618 Option Type 620 10 622 Option Length 624 8-bit unsigned integer. Length of the option, in octets, 625 excluding the Option Type and Option Length fields. 627 When no extensions are present, the Option Length of a 628 Destination and Flow ID Option is 6. Further extensions to 629 DSR may include additional data in a Destination and Flow ID 630 Option. The presence of such extensions is indicated by an 631 Option Length greater than 6. Currently, no such extensions 632 have been defined. 634 New Flow Identifier 636 Indicates the next identifier to store in the Flow ID field of 637 the DSR header. 639 New IP Destination Address 641 Indicates the next address to store in the Destination Address 642 field of the IP header. 644 The Destination and Flow ID Option MAY appear one or more times 645 within a DSR header. 647 4.2.4. New Error Type Value for Unknown Flow 649 A new Error Type value of 129 (Unknown Flow) is defined for use in a 650 Route Error option in a DSR header. The Type-Specific Information 651 for errors of this type is encoded as follows: 653 0 1 2 3 654 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 655 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 656 | Original IP Destination Address | 657 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 658 | Flow~ID | 659 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 661 Original IP Destination Address 663 The IP Destination Address of the packet that caused the error. 665 Flow ID 667 The Flow ID contained in the DSR Flow ID Option that caused the 668 error. 670 4.2.5. New Error Type Value for Default Flow Unknown 672 A new Error Type value of 130 (Default Flow Unknown) is defined for 673 use in a Route Error option in a DSR header. The Type-Specific 674 Information for errors of this type is encoded as follows: 676 0 1 2 3 677 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 678 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 679 | Original IP Destination Address | 680 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 682 Original IP Destination Address 684 The IP Destination Address of the packet that caused the error. 686 4.2.6. Acknowledgement Request Option Previous Hop Address Extension 688 When the Option Length field of an Acknowledgement Request option in 689 a DSR header is greater than or equal to 6, a Previous Hop Address 690 Extension is present. The option is then formatted as follows: 692 0 1 2 3 693 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 694 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 695 | Option Type | Option Length | Packet Identifier | 696 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 697 | ACK Request Source Address | 698 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 700 Option Type 702 5 704 Option Length 706 8-bit unsigned integer. Length of the option, in octets, 707 excluding the Option Type and Option Length fields. 709 When no extensions are present, the Option Length of a 710 Acknowledgement Request Option is 2. Further extensions to 711 DSR may include additional data in a Acknowledgement Request 712 Option. The presence of such extensions is indicated by an 713 Option Length greater than 2. 715 Currently, one such extension has been defined. If the 716 Option Length is at least 6, then a ACK Request Source Address 717 is present. 719 Packet Identifier 721 The Packet Identifier field is set to a unique number and is 722 copied into the Identification field of the DSR Acknowledgement 723 option when returned by the node receiving the packet over this 724 hop. 726 ACK Request Source Address 728 The address of the node requesting the DSR Acknowledgment. 730 5. Detailed Operation 732 5.1. Originating a Packet 734 When originating any packet to be routed using flow state, a node 735 using DSR Flow State MUST: 737 - If the route to be used for this packet has never had a DSR Flow 738 State established along it: 740 * Generate a 16-bit Flow ID larger than any unexpired Flow IDs 741 used for this destination. Odd Flow IDs MUST be chosen for 742 "default" flows; even Flow IDs MUST be chosen for non-default 743 flows 745 * Add a DSR header, as specified in the base DSR protocol 746 specification 748 * Add a DSR Flow State header, as described in Section 5.1.1 750 * Set the Flow ID field in the DSR Flow State header to the 751 Flow ID generated in the first step 753 * Add a Timeout Option to the DSR header 755 * Add a Source Route option after the Timeout Option with the 756 route to be used, as specified in the base DSR protocol 757 specification 759 * The source SHOULD record this flow in its Flow Table 761 * If this flow is recorded in the Flow Table, the TTL MUST be 762 set to be the TTL of the flow establishment packet. 764 * If this flow is recorded in the Flow Table, the timeout MUST 765 be set to a value no less than the value specified in the 766 Timeout Option. 768 - If the route to be used for this packet has had DSR Flow State 769 established along it, but has not been established end-to-end 771 * Add a DSR header, as specified in the base DSR protocol 772 specification 774 * Add a DSR Flow State header, as described in Section 5.1.1 776 * The Flow ID field of the DSR Flow State header SHOULD be the 777 Flow ID previously used for this route. If it is not, the 778 steps for sending packets along never before established 779 routes MUST be followed in place of these. 781 * Add a Timeout Option to the DSR header, setting the Timeout 782 to a value not greater than the timeout remaining for this 783 flow in the Flow Table. 785 * Add a Source Route option after the Timeout Option with the 786 route to be used, as specified in the base DSR protocol 787 specification 789 * If the IP TTL is not equal to the TTL specified in the Flow 790 Table, the source MUST set a flag to indicate that this flow 791 cannot be used as default. 793 - If the route the node wishes to use for this packet has been 794 established end-to-end and is not default 796 * Add a DSR Flow State header, as described in Section 5.1.1 798 * The Flow ID field of the DSR Flow State header SHOULD be the 799 Flow ID previously used for this route. If it is not, the 800 steps for sending packets along never before established 801 routes MUST be followed in place of these. 803 * If the next hop requires a Hop-by-Hop acknowledgement, 804 add a DSR header, as specified in the base DSR protocol 805 specification, and an Acknowledgement Request Option, as 806 specified in the base DSR protocol specification. 808 * A DSR header SHOULD NOT be added to a packet, unless it is 809 added to carry an Acknowledgement Request Option, in which 810 case: 812 + A Source Route option in the DSR header SHOULD NOT be 813 added. 815 + If a Source Route option in the DSR header is added, 816 the steps for sending packets along routes not yet 817 established end-to-end MUST be followed in place of 818 these. 820 + A Timeout Option SHOULD NOT be added. 822 + If a Timeout Option is added, it MUST specify a timeout 823 not greater than the timeout remaining for this flow in 824 the Flow Table. 826 - If the route the node wishes to use for this packet has been 827 established end-to-end and is the current default 829 * If the IP TTL is not equal to the TTL specified in the Flow 830 Table, the source MUST follow the steps for sending a packet 831 along a non-default flow that has been established end-to-end 832 in place of these steps. 834 * If the next hop requires a Hop-by-Hop acknowledgement, the 835 sending node MUST add a DSR header and an Acknowledgement 836 Request Option, as specified in the base DSR protocol 837 specification. The sending node MUST NOT add any additional 838 options to this header. 840 * A DSR header SHOULD NOT be added, except as specified in 841 the previous step. If one is added in a way inconsistent 842 with the previous step, the source MUST follow the steps 843 for sending a packet along a non-default flow that has been 844 established end-to-end in place of these steps. 846 5.1.1. Inserting a DSR Flow State Header 848 A node originating a packet adds a DSR Flow State header to the 849 packet, if necessary, to carry information needed by the routing 850 protocol. Only one DSR Flow State header may be in any packet. 851 A DSR Flow State header is added to a packet by performing the 852 following sequence of steps: 854 - Insert a DSR Flow State header after the IP header and any 855 Hop-by-Hop Options header that may already be in the packet, but 856 before any other header that may be present. 858 - Set the Next Header field of the DSR Flow State header to the 859 Next Header field of the previous header (either an IP header or 860 a Hop-by-Hop Options header). 862 - Set the Next Header field of the previous header to the Protocol 863 number assigned to DSR Flow State headers. 865 5.2. Receiving a Packet 867 This section describes processing only for packets that are sent to 868 the processing node; that is, when the MAC Destination Address is the 869 MAC address of the processing node. Otherwise, the process described 870 in Sections 5.4 should be followed. 872 The flow that a packet is being sent along is considered to be in the 873 Flow Table if the triple (IP Source Address, IP Destination Address, 874 Flow ID) has an unexpired entry in the flow table. 876 When a node using DSR Flow State receives a packet, it MUST follow 877 the following steps for processing: 879 - If a DSR Flow State header is present, increment the Hop Count 880 field 882 - If the triple (IP Source Address, IP Destination Address, 883 Flow ID) is in the Automatic Route Shortening table, and the 884 packet is in the entry, the node MAY send a Gratuitous Reply as 885 described in the base specification, giving any routes by which 886 the packet originally reached this node, subject to the rate 887 limiting specified in the base DSR protocol specification. If 888 no DSR Flow State header is present, and no Source Route option 889 is present, then for the purposes of this step, the Flow ID is 890 equal to the default Flow ID in the Default Flow Table for the 891 (IP Source Address, IP Destination Address) pair. If no DSR Flow 892 State header is present but a Source Route option is present, 893 skip this step. 895 - Process each of the Options within the DSR header in order: 897 * On receiving a Pad1 or PadN option, skip over the option 899 * On receiving a Route Request for which this node is the 900 destination, remove the option and return a Route Reply as 901 specified in the base DSR protocol specification 903 * On receiving a broadcast Route Request that this node has not 904 previously seen for which this node is not the destination, 905 append this node's incoming interface address to the Route 906 Request, continue propagating the Route Request as specified 907 in the base DSR protocol specification, send the payload, if 908 any, to the network layer, and stop processing. 910 * On receiving a Route Request that this node has not 911 previously seen for which this node is not the destination, 912 discard the packet and stop processing. 914 * On receiving any Route Request, add appropriate links to the 915 cache, as specified in the base DSR protocol specification. 917 * On receiving a Route Reply that this node is the Requester 918 for, remove the Route Reply from the packet and process it as 919 specified in the base DSR protocol specification. 921 * On receiving any Route Reply, add appropriate links to the 922 cache, as specified in the base DSR protocol specification. 924 * On receiving any Route Error of type NODE_UNREACHABLE, remove 925 appropriate links to the cache, as specified in the base DSR 926 protocol specification. 928 * On receiving a Route Error of type NODE_UNREACHABLE that this 929 node is the Error Destination Address of, remove the Route 930 Error from the packet and process it as specified in the base 931 DSR protocol specification. It also MUST stop originating 932 packets along any flows using the link from Error Source 933 Address to Unreachable Node, and it MAY remove from its Flow 934 Table any flows using the link from Error Source Address to 935 Unreachable Node. 937 * On receiving a Route Error of type UNKNOWN_FLOW that this 938 node is the Error Destination Address of, remove the Route 939 Error from the packet and mark the flow specified by the 940 triple (Error Destination Address, Original IP Destination 941 Address, Flow ID) as not having been established end-to-end. 943 * On receiving a Route Error of type DEFAULT_FLOW_UNKNOWN that 944 this node is the Error Destination Address of, remove the 945 Route Error from the packet and mark the default flow between 946 the Error Destination Address and the Original IP Destination 947 Address as not having been established end-to-end. 949 * On receiving a Acknowledgment Request option, the receiving 950 node removes the Acknowledgement Request option and replies 951 to the previous hop with a Acknowledgement option. If the 952 previous hop cannot be determined, the Acknowledgement 953 Request option is discarded, and processing continues. 955 * On receiving a Acknowledgement option, the receiving node 956 removes the Acknowledgement option and processes it. 958 * On receiving any Acknowledgement option, add the appropriate 959 link to the cache, as specified in the base DSR protocol 960 specification. 962 * On receiving any Source Route option, add appropriate 963 links to the cache, as specified in the base DSR protocol 964 specification. 966 * On receiving a Source Route option and either no DSR Flow 967 State header is present, the flow this packet is being sent 968 along is in the Flow Table, or no Timeout Option preceded 969 the Source Route option in this DSR header, process it as 970 specified in the base DSR protocol specification. Stop 971 processing this packet unless the last address in the Source 972 Route option is an address of this node. 974 * On receiving a Source Route option in a packet with a DSR 975 Flow State header, and the Flow ID specified in the DSR Flow 976 State header is not in the Flow Table, add the flow to the 977 Flow Table, setting the Timeout value to a value not greater 978 than the Timeout field of the Timeout Option in this header. 979 If no Timeout Option preceded the Source Route option in this 980 header, the flow MUST NOT be added to the Flow Table. 982 If the Flow ID is odd and larger than any unexpired, odd 983 Flow IDs, it is set to be default in the Default Flow ID 984 Table. 986 Then process the Route Option as specified in the base DSR 987 protocol specification. Stop processing this packet unless 988 the last address in the Source Route option is an address of 989 this node. 991 * On receiving a Virtual Route Option, when the IP Destination 992 Address is an address of this node, discard the Option and 993 continue processing. 995 * On receiving a Virtual Route Option, when the IP Destination 996 Address is not an address of this node, forward the packet 997 according to the Flow ID, as described in Section 5.3 stop 998 processing this packet. 1000 * On receiving a Timeout Option, check if this packet contains 1001 a DSR Flow State header. If this packet does not contain a 1002 DSR Flow State header, discard the Option. Otherwise, record 1003 the Timeout value in the option for future reference. The 1004 value recorded SHOULD be discarded when the node has finished 1005 processing this DSR header. If the flow that this packet is 1006 being sent along is in the Flow Table, it MAY set the flow to 1007 time out no more than Timeout seconds in the future. 1009 * On receiving a Destination and Flow ID Option, if the 1010 IP Destination Address is not an address of this node, 1011 forward the packet according to the Flow ID, as described in 1012 Section 5.3, and stop processing this packet. 1014 * On receiving a Destination and Flow ID Option, if the IP 1015 Destination Address is an address of this node, set the 1016 IP Destination Address to the New IP Destination Address 1017 specified in the option, and set the Flow ID to the New 1018 Flow Identifier. Then remove the Option from the packet and 1019 continue processing. 1021 - If the IP Destination Address is an address of this node, remove 1022 the DSR header, if any, and pass the packet up the network stack 1023 and stop processing. 1025 - If there is still a DSR header containing no options, remove the 1026 DSR header. 1028 - If there is still a DSR Flow State header, forward the packet 1029 according to the Flow ID, as described in Section 5.3. 1031 - If there is neither a DSR header nor a DSR Flow State header, but 1032 there is an entry in the Default Flow Table for the (IP Source 1033 Address, IP Destination Address) pair: 1035 * If the IP TTL is not equal to the TTL expected in the Flow 1036 Table, insert a DSR Flow State header, setting Hop Count 1037 equal to the Hop Count of this node, and the Flow ID equal 1038 to the default Flow ID found in the table, and forward this 1039 packet according to the Flow ID, as described in Section 5.3. 1041 * Otherwise, follow the steps for forwarding the packet using 1042 Flow IDs described in Section 5.3, but taking the Flow ID to 1043 be the default Flow ID found in the table. 1045 - If there is no DSR header, no DSR Flow State header, and no 1046 default flow can be found, the node returns a Route Error of 1047 type Default Flow Unknown to the IP Source Address, specifying 1048 the IP Destination Address as the Original IP Destination in the 1049 type-specific field. 1051 5.3. Forwarding a Packet Using Flow IDs 1053 To forward a packet using Flow IDs, a node MUST follow the following 1054 sequence of steps: 1056 - If the triple (IP Source Address, IP Destination Address, 1057 Flow ID) is not in the Flow Table, return a Route Error of type 1058 Unknown Flow. 1060 - If a hop-by-hop acknowledgement is required for the next hop, the 1061 node MUST include an Acknowledegment Request option as specified 1062 in the base DSR protocol specification. If no DSR header is in 1063 the packet for the Acknowledgement Request option to be attached 1064 to, it MUST be included, as specified in the base DSR protocol 1065 specification, except that it MUST be added after the DSR Flow 1066 State header, if one is present. 1068 - Attempt to transmit this packet to the next hop as specified in 1069 the Flow Table, performing Route Maintenance to detect broken 1070 routes. 1072 5.4. Promiscuously Receiving a Packet 1074 This section describes processing only for packets that have MAC 1075 destinations other than the processing node. Otherwise, the process 1076 described in Section 5.2 should be followed. 1078 When a node using DSR Flow State promiscuously overhears a packet, it 1079 SHOULD follow the following steps for processing: 1081 - If the packet has a DSR Flow State header, and if the triple (IP 1082 Source Address, IP Destination Address, Flow ID) is in the Flow 1083 Table and the Hop Count is less than the Hop Count in the flow's 1084 entry, the node MAY retain the packet in the Automatic Route 1085 Shortening table. If it can be determined that this Flow ID has 1086 been recently used, it SHOULD retain the packet in the Automatic 1087 Route Shortening table. 1089 - If the packet has neither a DSR Flow State header nor a Source 1090 Route option, and a Default Flow ID can be found in the Default 1091 Flow Table for (IP Source Address, IP Destination Address), and 1092 the IP TTL is greater than the TTL in the table for the default 1093 flow, the node MAY retain the packet in the Automatic Route 1094 Shortening table. If it can be determined that this Flow ID has 1095 been recently used, it SHOULD retain the packet in the Automatic 1096 Route Shortening table. 1098 5.5. Operation Where the Layer Below DSR Decreases the IP TTL 1099 Non-Uniformly 1101 Some nodes may use an IP tunnel as a DSR hop. If different packets 1102 sent along this IP tunnel can take different routes, the reduction 1103 in IP TTL across this link may be different for different packets. 1104 This prevents the Automatic Route Shortening and Loop Detection 1105 functionality from working properly when used in conjunction with 1106 default routes. 1108 Nodes forwarding packets without a Source Route option on to a link 1109 with unpredictable TTL changes MUST ensure that a DSR Flow State 1110 header is present, indicating the correct Hop Count and Flow ID. 1112 5.6. Salvage Interactions with DSR 1114 Nodes salvaging packets MUST remove the DSR Flow State header, if 1115 present. 1117 Any time the base specification refers to the Salvage field in the 1118 Source Route option, packets without a Source Route option are 1119 considered to have the value zero in the Salvage field. 1121 6. IANA Considerations 1123 This document contains no new IANA considerations beyond those 1124 required by the base DSR protocol specification [2]. 1126 7. Security Considerations 1128 All security considerations outlined in the base DSR protocol 1129 specification [2] apply to this document as well. 1131 Implementation Status 1133 A preliminary version of the flow state modifications described here 1134 was implemented in FreeBSD 3.3. A demonstration of this modified 1135 version of DSR was presented in July 2000. 1137 References 1139 [1] Scott Bradner. Key words for use in RFCs to indicate requirement 1140 levels. RFC 2119, March 1997. 1142 [2] David B. Johnson, David A. Maltz, Yih-Chun Hu, and Jorjeta 1143 Jetcheva. The Dynamic Source Routing protocol for mobile ad hoc 1144 networks. Internet-Draft, draft-ietf-manet-dsr-05.txt, March 1145 2001. Work in progress. 1147 [3] Joyce K. Reynolds and Jon Postel. Assigned numbers. RFC 1700, 1148 October 1994. See also http://www.iana.org/numbers.html. 1150 Chair's Address 1152 The MANET Working Group can be contacted via its current chairs: 1154 M. Scott Corson Phone: +1 301 405-6630 1155 Institute for Systems Research Email: corson@isr.umd.edu 1156 University of Maryland 1157 College Park, MD 20742 1158 USA 1160 Joseph Macker Phone: +1 202 767-2001 1161 Information Technology Division Email: macker@itd.nrl.navy.mil 1162 Naval Research Laboratory 1163 Washington, DC 20375 1164 USA 1166 Authors' Addresses 1168 Questions about this document can also be directed to the authors: 1170 Yih-Chun Hu Phone: +1 412 268-3075 1171 Carnegie Mellon University Fax: +1 412 268-5576 1172 Computer Science Department Email: yihchun@cs.cmu.edu 1173 5000 Forbes Avenue 1174 Pittsburgh, PA 15213-3891 1175 USA 1177 David B. Johnson Phone: +1 713 348-3063 1178 Rice University Fax: +1 713 348-5930 1179 Computer Science Department, MS 132 Email: dbj@cs.rice.edu 1180 6100 Main Street 1181 Houston, TX 77005-1892 1182 USA 1184 David A. Maltz Phone: +1 650 688-3128 1185 AON Networks Fax: +1 650 688-3119 1186 3045 Park Blvd. Email: dmaltz@cs.cmu.edu 1187 Palo Alto, CA 94306 1188 USA