idnits 2.17.1 draft-cardenas-dff-14.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (May 7, 2013) is 4006 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- ** Obsolete normative reference: RFC 2460 (Obsoleted by RFC 8200) Summary: 1 error (**), 0 flaws (~~), 1 warning (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Internet Engineering Task Force U. Herberg, Ed. 3 Internet-Draft Fujitsu 4 Intended status: Experimental A. Cardenas 5 Expires: November 8, 2013 University of Texas at Dallas 6 T. Iwao 7 Fujitsu 8 M. Dow 9 Freescale 10 S. Cespedes 11 U. Icesi 12 May 7, 2013 14 Depth-First Forwarding in Unreliable Networks (DFF) 15 draft-cardenas-dff-14 17 Abstract 19 This document specifies the "Depth-First Forwarding" (DFF) protocol 20 for IPv6 networks, a data forwarding mechanism that can increase 21 reliability of data delivery in networks with dynamic topology and/or 22 lossy links. The protocol operates entirely on the forwarding plane, 23 but may interact with the routing plane. DFF forwards data packets 24 using a mechanism similar to a "depth-first search" for the 25 destination of a packet. The routing plane may be informed of 26 failures to deliver a packet or loops. This document specifies the 27 DFF mechanism both for IPv6 networks (as specified in RFC2460) and in 28 addition also for LoWPAN "mesh-under" networks (as specified in 29 RFC4944). The design of DFF assumes that the underlying link layer 30 provides means to detect if a packet has been successfully delivered 31 to the next hop or not. It is applicable for networks with little 32 traffic, and is used for unicast transmissions only. 34 Status of this Memo 36 This Internet-Draft is submitted in full conformance with the 37 provisions of BCP 78 and BCP 79. 39 Internet-Drafts are working documents of the Internet Engineering 40 Task Force (IETF). Note that other groups may also distribute 41 working documents as Internet-Drafts. The list of current Internet- 42 Drafts is at http://datatracker.ietf.org/drafts/current/. 44 Internet-Drafts are draft documents valid for a maximum of six months 45 and may be updated, replaced, or obsoleted by other documents at any 46 time. It is inappropriate to use Internet-Drafts as reference 47 material or to cite them other than as "work in progress." 48 This Internet-Draft will expire on November 8, 2013. 50 Copyright Notice 52 Copyright (c) 2013 IETF Trust and the persons identified as the 53 document authors. All rights reserved. 55 This document is subject to BCP 78 and the IETF Trust's Legal 56 Provisions Relating to IETF Documents 57 (http://trustee.ietf.org/license-info) in effect on the date of 58 publication of this document. Please review these documents 59 carefully, as they describe your rights and restrictions with respect 60 to this document. Code Components extracted from this document must 61 include Simplified BSD License text as described in Section 4.e of 62 the Trust Legal Provisions and are provided without warranty as 63 described in the Simplified BSD License. 65 Table of Contents 67 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 5 68 1.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . 5 69 1.2. Experiments to be conducted . . . . . . . . . . . . . . . 6 70 2. Notation and Terminology . . . . . . . . . . . . . . . . . . . 7 71 2.1. Notation . . . . . . . . . . . . . . . . . . . . . . . . . 7 72 2.2. Terminology . . . . . . . . . . . . . . . . . . . . . . . 8 73 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 9 74 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 11 75 4.1. Information Sets Overview . . . . . . . . . . . . . . . . 12 76 4.2. Signaling Overview . . . . . . . . . . . . . . . . . . . . 12 77 5. Protocol Dependencies . . . . . . . . . . . . . . . . . . . . 13 78 6. Information Sets . . . . . . . . . . . . . . . . . . . . . . . 14 79 6.1. Symmetric Neighbor List . . . . . . . . . . . . . . . . . 14 80 6.2. Processed Set . . . . . . . . . . . . . . . . . . . . . . 14 81 7. Packet Header Fields . . . . . . . . . . . . . . . . . . . . . 15 82 8. Protocol Parameters . . . . . . . . . . . . . . . . . . . . . 16 83 9. Data Packet Generation and Processing . . . . . . . . . . . . 16 84 9.1. Data Packets Entering the DFF Routing Domain . . . . . . . 17 85 9.2. Data Packet Processing . . . . . . . . . . . . . . . . . . 18 86 10. Unsuccessful Packet Transmission . . . . . . . . . . . . . . . 20 87 11. Determining the Next Hop for a Packet . . . . . . . . . . . . 21 88 12. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . 22 89 13. Modes of Operation . . . . . . . . . . . . . . . . . . . . . . 22 90 13.1. Route-Over . . . . . . . . . . . . . . . . . . . . . . . . 23 91 13.1.1. Mapping of DFF Terminology to IPv6 Terminology . . . 23 92 13.1.2. Packet Format . . . . . . . . . . . . . . . . . . . . 23 93 13.2. Mesh-Under . . . . . . . . . . . . . . . . . . . . . . . . 25 94 13.2.1. Mapping of DFF Terminology to LoWPAN Terminology . . 25 95 13.2.2. Packet Format . . . . . . . . . . . . . . . . . . . . 26 96 14. Scope Limitation of DFF . . . . . . . . . . . . . . . . . . . 27 97 14.1. Route-Over MoP . . . . . . . . . . . . . . . . . . . . . . 29 98 14.2. Mesh-Under MoP . . . . . . . . . . . . . . . . . . . . . . 30 99 15. MTU Exceedance . . . . . . . . . . . . . . . . . . . . . . . . 32 100 16. Security Considerations . . . . . . . . . . . . . . . . . . . 32 101 16.1. Attacks Out of Scope . . . . . . . . . . . . . . . . . . . 32 102 16.2. Protection Mechanisms of DFF . . . . . . . . . . . . . . . 32 103 16.3. Attacks In Scope . . . . . . . . . . . . . . . . . . . . . 33 104 16.3.1. Denial of Service . . . . . . . . . . . . . . . . . . 33 105 16.3.2. Packet Header Modification . . . . . . . . . . . . . 33 106 16.3.2.1. Return Flag Tampering . . . . . . . . . . . . . . 34 107 16.3.2.2. Duplicate Flag Tampering . . . . . . . . . . . . 34 108 16.3.2.3. Sequence Number Tampering . . . . . . . . . . . . 34 109 17. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 35 110 18. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 35 111 19. References . . . . . . . . . . . . . . . . . . . . . . . . . . 35 112 19.1. Normative References . . . . . . . . . . . . . . . . . . . 35 113 19.2. Informative References . . . . . . . . . . . . . . . . . . 36 114 Appendix A. Examples . . . . . . . . . . . . . . . . . . . . . . 37 115 A.1. Example 1: Normal Delivery . . . . . . . . . . . . . . . . 37 116 A.2. Example 2: Forwarding with Link Failure . . . . . . . . . 37 117 A.3. Example 3: Forwarding with Missed Link Layer 118 Acknowledgment . . . . . . . . . . . . . . . . . . . . . . 38 119 A.4. Example 4: Forwarding with a Loop . . . . . . . . . . . . 39 120 Appendix B. Deployment Experience . . . . . . . . . . . . . . . . 40 121 B.1. Deployments in Japan . . . . . . . . . . . . . . . . . . . 40 122 B.2. Kit Carson Electric Cooperative . . . . . . . . . . . . . 40 123 B.3. Simulations . . . . . . . . . . . . . . . . . . . . . . . 40 124 B.4. Open Source Implementation . . . . . . . . . . . . . . . . 40 125 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 41 127 1. Introduction 129 This document specifies the Depth-First Forwarding (DFF) protocol for 130 IPv6 networks, both for IPv6 forwarding ([RFC2460], henceforth 131 denoted "route-over"), and also for "mesh-under" forwarding using the 132 LoWPAN adaptation layer ([RFC4944]). The protocol operates entirely 133 on the forwarding plane, but may interact with the routing plane. 134 The purpose of DFF is to increase reliability of data delivery in 135 networks with dynamic topologies and/or lossy links. 137 DFF forwards data packets using a "depth-first search" for the 138 destination of the packets. DFF relies on an external neighborhood 139 discovery mechanism which lists neighbors of a router that may be 140 attempted as next hops for a data packet. In addition, DFF may use 141 information from the Routing Information Base (RIB) for deciding in 142 which order to try to send the packet to the neighboring routers. 144 If the packet makes no forward progress using the first selected next 145 hop, DFF will successively try all neighbors of the router. If none 146 of the next hops successfully receives or forwards the packet, DFF 147 returns the packet to the previous hop, which in turn tries to send 148 it to alternate neighbors. 150 As network topologies do not necessarily form trees, loops can occur. 151 Therefore, DFF contains a loop detection and avoidance mechanism. 153 DFF may provide information, which may - by a mechanism outside of 154 this specification - be used for updating cost of routes in the RIB 155 based on failed or successful delivery of packets through alternative 156 next hops. Such information may also be used by a routing protocol. 158 DFF assumes that the underlying link layer provides means to detect 159 if a packet has been successfully delivered to the next hop or not, 160 is designed for networks with little traffic, and is used for unicast 161 transmissions only. 163 1.1. Motivation 165 In networks with dynamic topologies and/or lossy links, even frequent 166 exchanges of control messages between routers for updating the 167 routing tables cannot guarantee that the routes correspond to the 168 effective topology of the network at all times. Packets may not be 169 delivered to their destination because the topology has changed since 170 the last routing protocol update. 172 More frequent routing protocol updates can mitigate that problem to a 173 certain extent, however this requires additional signaling, consuming 174 channel and router resources (e.g., when flooding control messages 175 through the network). This is problematic in networks with lossy 176 links, where further control traffic exchange can worsen the network 177 stability because of collisions. Moreover, additional control 178 traffic exchange may drain energy from battery-driven routers. 180 The data-forwarding mechanism specified in this document allows for 181 forwarding data packets along alternate paths for increasing 182 reliability of data delivery, using a depth-first search. The 183 objective is to decrease the necessary control traffic overhead in 184 the network, and at the same time to increase delivery success rates. 186 As this specification is intended for experimentation, the mechanism 187 is also specified for forwarding on the LoWPAN adaption layer 188 (according to Section 11 of [RFC4944]), in addition to IPv6 189 forwarding as specified in [RFC2460]. Other than different header 190 formats, the DFF mechanism for route-over and mesh-under is similar, 191 and is therefore first defined in general, and then more specifically 192 for both IPv6 route-over forwarding (as specified in Section 13.1), 193 and for LoWPAN adaptation layer mesh-under (as specified in 194 Section 13.2). 196 1.2. Experiments to be conducted 198 This document is presented as an Experimental specification that can 199 increase reliability of data delivery in networks with dynamic 200 topology and/or lossy links. It is anticipated that, once sufficient 201 operational experience has been gained, this specification will be 202 revised to progress it on to the Standards Track. This experiment is 203 intended to be tried in networks that meet the applicability 204 described in Section 3, and with the scope limitations set out in 205 Section 14. While experimentation is encouraged in such networks, 206 operators should exercise caution before attempting this experiment 207 in other types of network as the stability of interaction between DFF 208 and routing in those networks has not been established. 210 Experience reports regarding DFF implementation and deployment are 211 encouraged particularly with respect to: 213 o Optimal values for the parameter P_HOLD_TIME, depending on the 214 size of the network, the topology and the amount of traffic 215 originated per router. The longer a Processed Tuple is hold, the 216 more memory is consumed on a router. Moreover, if a tuple is hold 217 too long, a sequence number wrap-around may occur, and a new 218 packet may have the same sequence number as one indicated in an 219 old Processed Tuple. However, if the tuple is expired too soon 220 (before the packet has been completed its path to the 221 destination), it may be mistakenly detected as new packet instead 222 of one already seen. 224 o Optimal values for the parameter MAX_HOP_LIMIT, depending on the 225 size of the network, the topology, and the lossyness of the link 226 layer. MAX_HOP_LIMIT makes sure that packets do not unnecessarily 227 traverse in the network; it may be used to limit the "detour" of 228 packets that is acceptable. The value may also be based on a per- 229 packet-basis if hop-count information is available from the RIB or 230 routing protocol. In such a case, the hop-limit for the packet 231 may be a percentage (e.g., 200%) of the hop-count value indicated 232 in the routing table. 234 o Optimal methods to increase cost of a route when a loop or lost L2 235 ACK is detected by DFF. While this is not specified as a 236 normative part of this document, it may be of interest in an 237 experiment to find good values of how much to increase link cost 238 in the RIB or routing protocol. 240 o Performance of using DFF in combination with different routing 241 protocols, such as reactive and proactive protocols. This also 242 implies how routes are updated by the RIB / routing protocol when 243 informed by DFF about loops or broken links. 245 2. Notation and Terminology 247 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 248 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 249 "OPTIONAL" in this document are to be interpreted as described in 250 [RFC2119]. 252 Additionally, this document uses the notation in Section 2.1 and the 253 terminology in Section 2.2. 255 2.1. Notation 257 The following notations are used in this document: 259 List: A list of elements is defined as [] for an empty list, 260 [element] for a list with one element, and [element1, element2, 261 ...] for a list with multiple elements. 263 Concatenation of lists: If L1 and L2 are lists, then L1@L2 is a new 264 list with first all elements of L1, followed by all elements of L2 265 in that order. 267 Byte order: All packet formats in this specification use network 268 byte order (most significant octet first) for all fields. The 269 most significant bit in an octet is numbered bit 0, and the least 270 significant bit of an octet is numbered bit 7. 272 Assignment: a := b 273 An assignment operator, whereby the left side (a) is assigned the 274 value of the right side (b). 276 Comparison: c = d 277 A comparison operator, returning true if the value of the left 278 side (c) is equal to the value of the right side (d). 280 Flags: This specification uses multiple 1-bit flags. A value of '0' 281 of a flag means 'false', a value of '1' means 'true'. 283 2.2. Terminology 285 The terms "route-over" and "mesh-under", introduced in [RFC6775] are 286 used in this document, where "route-over" is not only limited to 287 6LoWPANs but applies to general IPv6 networks: 289 Mesh-under: A topology where nodes are connected to a [6LoWPAN 290 Border Router] 6LBR through a mesh using link-layer forwarding. 291 Thus, in a mesh-under configuration, all IPv6 hosts in a LoWPAN 292 are only one IP hop away from the 6LBR. This topology simulates 293 the typical IP-subnet topology with one router with multiple nodes 294 in the same subnet. 296 Route-over: A topology where hosts are connected to the 6LBR through 297 the use of intermediate layer-3 (IP) routing. Here, hosts are 298 typically multiple IP hops away from a [6LoWPAN Router] 6LBR. The 299 route-over topology typically consists of a 6LBR, a set of 6LRs, 300 and hosts. 302 The following terms are used in this document. As the DFF mechanism 303 is specified both for route-over IPv6 and for mesh-under LoWPAN 304 adaptation layer, the terms are generally defined in this section, 305 and then specifically mapped for each of the different modes of 306 operation in Section 13. 308 Depth-first search: "Depth-first search (DFS) is an algorithm for 309 traversing or searching a tree, tree structure, or graph. One 310 starts at the root (selecting some node as the root in the graph 311 case) and explores as far as possible along each branch before 312 backtracking" [DFS_wikipedia]. In this document, the algorithm 313 for traversing a graph is applied to forwarding packets in a 314 computer network, with nodes being routers. 316 Routing Information Base (RIB): A table stored in the user-space of 317 an operating system of a router or host. The table lists routes 318 to network destinations, as well as associated metrics with these 319 routes. 321 Mode of Operation (MoP): The DFF mechanism specified in this 322 document can either be used as "route-over" IPv6 forwarding 323 mechanism (Mode of Operation: "route-over"), or as "mesh-under" 324 LoWPAN adaptation layer (Mode of Operation: "mesh-under"). 326 Packet: An IPv6 Packet (for "route-over" MoP) or a "LoWPAN 327 encapsulated packet" (for "mesh-under" MoP) containing an IPv6 328 Packet as payload. 330 Packet Header: An IPv6 extension header (for "route-over" MoP) or a 331 LoWPAN header (for "mesh-under" MoP). 333 Address: An IPv6 address (for "route-over" MoP), or a 16-bit short 334 or EUI-64 link layer address (for "mesh-under" MoP). 336 Originator: The router which added the DFF header (specified in 337 Section 7) to a Packet. 339 Originator Address: An Address of the Originator. This Address 340 SHOULD be an Address configured on the interface which transmits 341 the Packet, selected according to [RFC6724]. 343 Destination: The router or host to which a Packet is finally 344 destined. In case this router or host is outside of the routing 345 domain in which DFF is used, the Destination is the router that 346 removes the DFF header (specified in Section 7) from the Packet. 347 This case is described in Section 14.1. 349 Destination Address: An Address to which the Packet is sent. 351 Next Hop: An Address of the next hop router to which the Packet is 352 sent along the path to the Destination. 354 Previous Hop: The Address of the previous hop router from which a 355 Packet has been received. In case the Packet has been received by 356 a router from outside of the routing domain where DFF is used 357 (i.e., no DFF header is contained in the Packet), the Originator 358 Address of the router adding the DFF header to the Packet is used 359 as the Previous Hop. 361 Hop Limit: An upper bound how many times the Packet may be 362 forwarded. 364 3. Applicability Statement 366 This document specifies DFF, a packet forwarding mechanism intended 367 for use in networks with dynamic topology and/or lossy links with the 368 purpose of increasing reliability of data delivery. The protocol's 369 applicability is determined by its characteristics, which are that 370 this protocol: 372 o Is applicable for use in IPv6 networks, either as "route-over" 373 forwarding mechanism using IPv6 ([RFC2460]), or as "mesh-under" 374 forwarding mechanism using the frame format for transmission of 375 IPv6 packets defined in [RFC4944]. 377 o Assumes addresses used in the network are either IPv6 addresses 378 (if the protocol is used as "route-over"), or 16-bit short or 379 EUI-64 link layer addresses, as specified in [RFC4944] if the 380 protocol is used as "mesh-under". In "mesh-under" mode, mixed 16- 381 bit and EUI-64 addresses within one DFF routing domain are allowed 382 (if conform with [RFC4944]), as long as DFF is limited to be used 383 within one PAN (Personal Area Network). It is assumed that the 384 "route-over" mode and "mesh-under" mode are mutually exclusive in 385 the same routing domain. 387 o Assumes that the underlying link layer provides means to detect if 388 a Packet has been successfully delivered to the Next Hop or not 389 (e.g., by L2 ACK messages). Examples for such underlying link 390 layers are IEEE 802.15.4 or IEEE 802.11. 392 o Is applicable in networks with lossy links and/or with a dynamic 393 topology. In networks with very stable links and fixed topology, 394 DFF will not bring any benefit (but also not be harmful, other 395 than the additional overhead for the Packet header). 397 o Works in a completely distributed manner, and does not depend on 398 any central entity. 400 o Is applicable for networks with little traffic in terms of numbers 401 of Packets per second, since each recently forwarded Packet 402 increases the state on a router. The amount of traffic per time 403 that is supported by DFF depends on the memory resources of the 404 router running DFF, on the density of the network, on the loss 405 rate of the channel, and the maximum hop limit for each Packet: 406 for each recently seen Packet, a list of Next Hops that the Packet 407 has been sent to is stored in memory. The stored entries can be 408 deleted after an expiration time, so that only recently received 409 Packets require storage on the router. Implementations are 410 advised to measure and report rates of packets in the network, and 411 also to report memory usage. Thus, operators can determine memory 412 exhaustion because of growing Information Sets or problems because 413 of too rapid sequence number wrap-around. 415 o Is applicable for dense topologies with multiple paths between 416 each source and each destination. Certain topologies are less 417 suitable for DFF: topologies that can be partitioned by the 418 removal of a single router or link, topologies with multiple stub 419 routers that each have a single link to the network, topologies 420 with only a single path to a destination, or topologies where the 421 "detour" that a Packet makes during the depth-first search in 422 order to reach the destination would be too long. Note that the 423 number of retransmissions of a Packet that stipulate a "too long" 424 path depends on the underlying link layer (capacity and 425 probability of Packet loss), as well as how much bandwidth is 426 required for data traffic by applications running in the network. 427 In such topologies, the Packet may never reach the Destination, 428 and therefore unnecessary transmissions of data Packets may occur 429 until the Hop Limit of the Packet reaches zero and the Packet is 430 dropped. This may consume channel and router resources. 432 o Is used for unicast transmissions only (not for anycast or 433 multicast). 435 o Is for use within stub networks, and for traffic between a router 436 inside the routing domain in which DFF is used and a known border 437 router. Examples of such networks are LoWPANs. Scope limitations 438 are described in Section 14. 440 4. Protocol Overview and Functioning 442 When a Packet is to be forwarded by a router using DFF, the router 443 creates a list of candidate Next Hops for that Packet. This list 444 (created per packet) is ordered, and Section 11 provides 445 recommendations of how to order the list, e.g., first listing Next 446 Hops listed in the RIB, if available, ordered in increasing cost, 447 followed by other neighbors provided by an external neighborhood 448 discovery. DFF proceeds to forward the Packet to the Next Hop listed 449 first in the list. If the transmission was not successful (as 450 determined by the underlying link layer) or if the Packet was 451 "returned" by a Next Hop to which it had been sent before, the router 452 will try to forward the Packet to the next Next Hop on the list. A 453 router "returns" a Packet to the router from which it was originally 454 received, once it has unsuccessfully tried to forward the Packet to 455 all elements in the candidate Next Hop list. If the Packet is 456 eventually returned to the Originator of the Packet, and after the 457 Originator has exhausted all of its Next Hops for the Packet, the 458 Packet is dropped. 460 For each recently forwarded Packet, a router running DFF stores 461 information about the Packet as entry in an information set, denoted 462 Processed Set. Each entry in the Processed Set contains a sequence 463 number, included in the Packet Header, identifying the Packet (refer 464 to Section 12 for further details on the sequence number). 465 Furthermore, the entry contains a list of Next Hops to which the 466 Packet has been sent. This list of recently forwarded Packets also 467 allows for avoiding loops when forwarding a Packet. Entries in the 468 Processed Set expire after a given expiration timeout, and are 469 removed. 471 4.1. Information Sets Overview 473 This specification requires a single set on each router, the 474 Processed Set. The Processed Set stores the sequence number, the 475 Originator Address, the Previous Hop and a list of Next Hops, to 476 which the Packet has been sent, for each recently seen Packet. 477 Entries in the set are removed after a predefined time-out. Each 478 time a Packet is forwarded to a Next Hop, that Next Hop is added to 479 the list of Next Hops of the entry for the Packet. 481 Note that an implementation of this protocol may maintain the 482 information of the Processed Set in the indicated form, or in any 483 other organization which offers access to this information. In 484 particular, it is not necessary to remove Tuples from a Set at the 485 exact time indicated, only to behave as if the Tuples were removed at 486 that time. 488 In addition to the Processed Set, a list of symmetric neighbors must 489 be provided by an external neighborhood discovery mechanism, or may 490 be determined from the RIB (e.g., if the RIB provides routes to 491 adjacent routers, and if these one-hop routes are verified to be 492 symmetric). 494 4.2. Signaling Overview 496 Information is needed on a per-packet basis by a router running DFF 497 that receives a Packet. This information is encoded in the Packet 498 Header that is specified in this document as IPv6 Hop-by-Hop Options 499 extension header and as LoWPAN header respectively, for the intended 500 "route-over" and "mesh-under" Modes of Operations. This DFF header 501 contains a sequence number used for uniquely identifying a Packet, 502 and two flags: RET (for "return") and DUP (for "duplicated"). 504 While a router successively tries sending a data Packet to one or 505 more of its neighbors, RET = 0. If none of the transmissions of the 506 Packet to the neighbors of a router have succeeded, the Packet is 507 returned to the router from which the Packet has been first received, 508 indicated by setting the return flag (RET := 1). The RET flag is 509 required to discern between a deliberately returned Packet and a 510 looping Packet: if a router receives a Packet with RET = 1 (and DUP = 511 0 or DUP = 1) that it has already forwarded, the Packet was 512 deliberately returned, and the router will continue to successively 513 send the Packet to routers from the candidate Next Hop list. If that 514 Packet has RET = 0, the router assumes that the Packet is looping and 515 returns it to the router from which it last received it. An external 516 mechanism may use this information for increasing the route cost of 517 the route to the Destination using the Next Hop which resulted in the 518 loop in the RIB or the routing protocol. It is out of scope of this 519 document to specify such a mechanism. Note that once DUP is set to 520 1, loop detection is not possible any more as the flag is not reset 521 any more. Therefore, a Packet may loop if the RIBs of routers in the 522 domain are inconsistent, until hop limit has reached 0. 524 Whenever a Packet transmission to a neighbor has failed (as 525 determined by the underlying link layer, e.g., using L2 ACKs), the 526 duplicate (DUP) flag is set in the Packet Header for the following 527 transmissions. The rationale is that the Packet may have been 528 successfully received by the neighbor and only the L2 ACK has been 529 lost, resulting in possible duplicates of the Packet in the network. 530 The DUP flag tags such a possible duplicate. The DUP flag is 531 required to discern between a duplicated Packet and a looping Packet: 532 if a router receives a Packet with DUP = 1 (and RET = 0) that it has 533 already forwarded, the Packet is not considered looping, and 534 successively forwarded to the next router from the candidate Next Hop 535 list. If the received Packet has DUP = 0 (and RET = 0), the router 536 assumes that the Packet is looping, sets RET := 1, and returns it to 537 the Previous Hop. Again, an external mechanism may use this 538 information for increasing route costs and/or informing the routing 539 protocol. 541 The reason for not dropping received duplicated Packets (with DUP = 542 1) is that a duplicated Packet may during its path again be 543 duplicated if another L2 ACK is lost. However, when DUP is already 544 set to 1, it is not possible discerning the duplicate from the 545 duplicate of the duplicate. As a consequence, loop detection is not 546 possible after the second lost L2 ACK on the path of a Packet. 547 However, if duplicates are simply dropped, it is possible that the 548 Packet was actually a looping packet (and not a duplicate), and so 549 the Depth First Search would be interrupted. 551 5. Protocol Dependencies 553 DFF MAY use information from the Routing Information Base (RIB), 554 specifically for determining an order of preference for to which next 555 hops a packet should be forwarded (e.g., the packet may be forwarded 556 first to neighbors that are listed in the RIB as next hops to the 557 destination, preferring those with the lowest route cost). 558 Section 11 provides recommendations about the order of preference for 559 the next hops of a packet. 561 DFF MUST have access to a list of symmetric neighbors for each 562 router, provided by a mechanism such as, e.g., NHDP [RFC6130]. That 563 neighborhood discovery protocol is not specified in this document. 565 6. Information Sets 567 This section specifies the information sets used by DFF. 569 6.1. Symmetric Neighbor List 571 DFF MUST have access to a list of Addresses of symmetric neighbors of 572 the router. This list can be provided by an external neighborhood 573 discovery mechanism, or alternatively may be determined from the RIB 574 (e.g., if the RIB provides routes to adjacent routers, and if these 575 one-hop routes are verified to be symmetric). The list of Addresses 576 of symmetric neighbors is not specified within this document. The 577 Addresses in the list are used to construct a list of candidate Next 578 Hops for a Packet, as specified in Section 11. 580 6.2. Processed Set 582 Each router maintains a Processed Set in order to support the loop 583 detection functionality. The Processed Set lists sequence numbers of 584 previously received Packets, as well as a list of Next Hops to which 585 the Packet has been sent successively as part of the depth-first 586 forwarding mechanism. To protect against this situation, it is 587 recommended that an implementation retains the Processed Set in non- 588 volatile storage if such is provided by the router. 590 The set consists of Processed Tuples 592 (P_orig_address, P_seq_number, P_prev_hop, 593 P_next_hop_neighbor_list, P_time) 595 where 597 P_orig_address is the Originator Address of the received Packet; 599 P_seq_number is the sequence number of the received Packet; 600 P_prev_hop is the Address of the Previous Hop of the Packet; 602 P_next_hop_neighbor_list is a list of Addresses of Next Hops to 603 which the Packet has been sent previously, as part of the depth- 604 first forwarding mechanism, as specified in Section 9.2; 606 P_time specifies when this Tuple expires and MUST be removed. 608 The consequences when no or not enough non-volatile storage is 609 available on a router (e.g., because of limited resources) or when an 610 implementation chooses not to make the Processed Set persistent, are 611 that Packets that are already in a loop caused by the routing 612 protocol may continue to loop until the hop limit is exhausted. Non- 613 looping Packets may be sent to Next Hops that have already received 614 the Packet previously and will return the Packet, leading to some 615 unnecessary retransmissions. This effect is only temporary and 616 applies only for Packets already traversing the network. 618 7. Packet Header Fields 620 This section specifies the information required by DFF in the Packet 621 Header. Note that, depending on whether DFF is used in the "route- 622 over" MoP or in the "mesh-under" MoP, the DFF header is either an 623 IPv6 Hop-by-Hop Options extension header (as specified in 624 Section 13.1.2) or a LoWPAN header (as specified in Section 13.2.2). 625 Section 13.1.2 and Section 13.2.2 specify the precise order, format 626 and encoding of the fields that are listed in this section. 628 Version (VER) - This 2-bit value indicates the version of DFF that 629 is used. This specification defines value 00. Packets with other 630 values of the version MUST be forwarded using forwarding as 631 defined in [RFC2460] and [RFC4944] for route-over and mesh-under 632 MoP respectively. 634 Duplicate Packet Flag (DUP) - This 1-bit flag is set in the DFF 635 header of a Packet, when that Packet is being re-transmitted due 636 to a signal from the link-layer that the original transmission 637 failed, as specified in Section 9.2. Once the flag is set to 1, 638 it MUST NOT be modified by routers forwarding the Packet. 640 Return Packet Flag (RET) - The 1-bit flag MUST be set to 1 prior to 641 sending the Packet back to the Previous Hop. Upon receiving a 642 packet with RET = 1, and before sending it to a new Candidate Next 643 Hop, that flag MUST be set to 0 as specified in Section 9.2. 645 Sequence Number - A 16-bit field, containing an unsigned integer 646 sequence number generated by the Originator, unique to each router 647 for each Packet to which the DFF has been added, as specified in 648 Section 12. The Originator Address concatenated with the sequence 649 number represents an identifier of previously seen data Packets. 650 Refer to Section 12 for further information about sequence 651 numbers. 653 8. Protocol Parameters 655 The parameters used in this specification are listed in this section. 656 These parameters are configurable, do not need to be stored in non- 657 volatile storage, and can be varied by implementations at run time. 658 Default values for the parameters depend on the network size, 659 topology, link layer and traffic patterns. Part of the 660 experimentation described in Section 1.2 is to determine suitable 661 default values. 663 P_HOLD_TIME - Is the time period after which a newly created or 664 modified Processed Tuple expires and MUST be deleted. An 665 implementation SHOULD use a value for P_HOLD_TIME that is high 666 enough that the Processed Tuple for a Packet is still in memory on 667 all forwarding routers while the Packet is transiting the routing 668 domain. The value SHOULD at least be MAX_HOP_LIMIT times the 669 expected time to send a Packet to a router on the same link. The 670 value MUST be lower than the time it takes until the same sequence 671 number is reached again after a wrap-around on the router 672 identified by P_orig_address of the Processed Tuple. 674 MAX_HOP_LIMIT - Is the initial value of Hop Limit, and therefore the 675 maximum number of times that a Packet is forwarded in the routing 676 domain. When choosing the value of MAX_HOP_LIMIT, the size of the 677 network, the distance between source and destination in number of 678 hops, and the maximum possible "detour" of a Packet SHOULD be 679 considered (compared to the shortest path). Such information MAY 680 be used from the RIB, if provided. 682 9. Data Packet Generation and Processing 684 The following sections specify the process of handling a Packet 685 entering the DFF routing domain (i.e., without DFF header) in 686 Section 9.1, as well as forwarding a data Packet from another router 687 running DFF in Section 9.2. 689 9.1. Data Packets Entering the DFF Routing Domain 691 This section applies for any data Packets upon their first entry into 692 a routing domain, in which DFF is used. This occurs when a new data 693 Packet is generated on this router, or when a data Packet is 694 forwarded from outside the routing domain (i.e., from a host attached 695 to this router or from a router outside the routing domain in which 696 DFF is used). Before such a data Packet (henceforth denoted "current 697 Packet") is transmitted, the following steps MUST be executed: 699 1. If required, encapsulate the Packet as specified in Section 14. 701 2. Add the DFF header to the current Packet (to the outer header if 702 the Packet has been encapsulated), with: 704 * DUP := 0; 706 * RET := 0; 708 * Sequence Number := a new sequence number of the Packet (as 709 specified in Section 12). 711 3. Check that the Packet does not exceed the MTU as specified in 712 Section 15. In case it does, execute the procedures listed in 713 Section 15 and do not further process the Packet. 715 4. Select the Next Hop (henceforth denoted "next_hop") for the 716 current Packet, as specified in Section 11. 718 5. Add a Processed Tuple to the Processed Set with: 720 * P_orig_address := the Originator Address of the current 721 Packet; 723 * P_seq_number := the sequence number of the current Packet; 725 * P_prev_hop := the Originator Address of the current Packet; 727 * P_next_hop_neighbor_list := [next_hop]; 729 * P_time := current time + P_HOLD_TIME. 731 6. Pass the current Packet to the underlying link layer for 732 transmission to next_hop. If the transmission fails (as 733 determined by the link layer), the procedures in Section 10 MUST 734 be executed. 736 9.2. Data Packet Processing 738 When a Packet (henceforth denoted the "current Packet") is received 739 by a router, then the following tasks MUST be performed: 741 1. If the Packet Header is malformed (i.e., the header format is not 742 as expected by this specification), drop the Packet. 744 2. Otherwise, if the Destination Address of the Packet matches an 745 Address of an interface of this router, deliver the Packet to 746 upper layers and do not further process the Packet as specified 747 below. 749 3. Decrement the value of the Hop Limit field by one (1). 751 4. Drop the Packet if Hop Limit is decremented to zero and do not 752 further process the Packet as specified below. 754 5. If no Processed Tuple (henceforth denoted the "current tuple") 755 exists in the Processed Set, with: 757 + P_orig_address = the Originator Address of the current Packet, 758 AND; 760 + P_seq_number = the sequence number of the current Packet. 762 Then: 764 1. Add a Processed Tuple (henceforth denoted the "current 765 tuple") with: 767 + P_orig_address := the Originator Address of the current 768 Packet; 770 + P_seq_number := the sequence number of the current Packet; 772 + P_prev_hop := the Previous Hop Address of the current 773 Packet; 775 + P_next_hop_neighbor_list := []; 777 + P_time := current time + P_HOLD_TIME. 779 2. Set RET to 0 in the DFF header. 781 3. Select the Next Hop (henceforth denoted "next_hop") for the 782 current Packet, as specified in Section 11. 784 4. P_next_hop_neighbor_list := P_next_hop_neighbor_list@ 785 [next_hop]. 787 5. Pass the current Packet to the underlying link layer for 788 transmission to next_hop. If the transmission fails (as 789 determined by the link layer), the procedures in Section 10 790 MUST be executed. 792 6. Otherwise, if a tuple exists: 794 1. If the return flag of the current Packet is not set (RET = 0) 795 (i.e., a loop has been detected): 797 1. Set RET := 1. 799 2. Pass the current Packet to the underlying link layer for 800 transmission to the Previous Hop. 802 2. Otherwise, if the return flag of the current Packet is set 803 (RET = 1): 805 1. If the Previous Hop of the Packet is not contained in 806 P_next_hop_neighbor_list of the current tuple, drop the 807 Packet. 809 2. If the Previous Hop of the Packet (i.e., the address of 810 the router from which the current Packet has just been 811 received) is equal to P_prev_hop of current tuple (i.e., 812 the address of the router from which the current Packet 813 has been first received), drop the Packet. 815 3. Set RET := 0. 817 4. Select the Next Hop (henceforth denoted "next_hop") for 818 the current Packet, as specified in Section 11. 820 5. Modify the current tuple: 822 - P_next_hop_neighbor_list := P_next_hop_neighbor_list@ 823 [next_hop]; 825 - P_time := current time + P_HOLD_TIME. 827 6. If the selected Next Hop is equal to P_prev_hop of the 828 current tuple, as specified in Section 11, (i.e., all 829 Candidate Next Hops have been unsuccessfully tried), set 830 RET := 1. If this router (i.e., the router receiving the 831 current packet) has the same Address as the Originator 832 Address of the current Packet, drop the Packet. 834 7. Pass the current Packet to the underlying link layer for 835 transmission to next_hop. If transmission fails (as 836 determined by the link layer), the procedures in 837 Section 10 MUST be executed. 839 10. Unsuccessful Packet Transmission 841 DFF requires that the underlying link layer provides information as 842 to whether a Packet is successfully received by the Next Hop. Absence 843 of such a signal is interpreted as delivery failure of the Packet 844 (henceforth denoted the "current Packet"). Note that the underlying 845 link layer MAY retry sending the Packet multiple times (e.g., using 846 exponential back-off) before determining that the Packet has not been 847 successfully received by the Next Hop. Whenever Section 9 explicitly 848 requests it in case of such a delivery failure, the following steps 849 are executed: 851 1. Set the duplicate flag (DUP) of the DFF header of the current 852 Packet to 1. 854 2. Select the Next Hop (henceforth denoted "next_hop") for the 855 current Packet, as specified in Section 11. 857 3. Find the Processed Tuple (the "current tuple") in the Processed 858 Set, with: 860 + P_orig_address = the Originator Address of the current Packet, 861 AND; 863 + P_seq_number = the sequence number of the current Packet, 865 4. If no current tuple is found, drop the Packet. 867 5. Otherwise, modify the current tuple: 869 * P_next_hop_neighbor_list := P_next_hop_neighbor_list@ 870 [next_hop]; 872 * P_time := current time + P_HOLD_TIME. 874 6. If the selected next_hop is equal to P_prev_hop of the current 875 tuple, as specified in Section 11 (i.e., all neighbors have been 876 unsuccessfully tried): 878 * RET := 1 880 * Decrement the value of the Hop Limit field by one (1). Drop 881 the Packet if Hop Limit is decremented to zero. 883 7. Otherwise 885 * RET := 0 887 8. Transmit the current Packet to next_hop. If transmission fails 888 (determined by the link layer), and if the next_hop does not 889 equal P_prev_hop from the current tuple, the procedures in 890 Section 10 MUST be executed. 892 11. Determining the Next Hop for a Packet 894 When forwarding a Packet, a router determines a valid Next Hop for 895 that Packet as specified in this section. As a Processed Tuple was 896 either existing when receiving the Packet (henceforth denoted the 897 "current Packet"), or otherwise was created, it can be assumed the a 898 Processed Tuple for that Packet (henceforth denoted the "current 899 tuple") is available. 901 The Next Hop is chosen from a list of candidate Next Hops in order of 902 decreasing priority. This list is created per Packet. The maximum 903 candidate Next Hop List for a Packet contains all the neighbors of 904 the router (as determined from an external neighborhood discovery 905 process), except for the Previous Hop of the current Packet. A 906 smaller list MAY be used, if desired, and the exact selection of the 907 size of the candidate Next Hop List is a local decision in each 908 router, which does not affect interoperability. Selecting a smaller 909 list may reduce the path length of a Packet traversing the network 910 and reduce required state in the Processed Set, but may result in 911 valid paths that are not explored. If information from the RIB is 912 used, then the candidate Next Hop list MUST contain at least the Next 913 Hop, indicated in the RIB as the Next Hop on the shortest path to the 914 destination, and SHOULD contain all Next Hops, indicated to the RIB 915 as Next Hops on paths to the destination. If a Next Hop from the RIB 916 equals the Previous Hop of the current Packet, it MUST NOT be added 917 to the candidate Next Hop list. 919 The list MUST NOT contain Addresses which are listed in 920 P_next_hop_neighbor_list of the current tuple, in order to avoid 921 sending the Packet to the same neighbor multiple times. Moreover, an 922 Address MUST NOT appear more than once in the list, for the same 923 reason. Also, Addresses of an interface of this router MUST NOT be 924 added to the list. 926 The list has an order of preference, where Next Hops at the top of 927 the list being the ones that Packets are sent to first in the depth- 928 first processing specified in Section 9.1 and Section 9.2. The 929 following order is RECOMMENDED, with the elements listed on top 930 having the highest preference: 932 1. The neighbor that is indicated in the RIB as the Next Hop on the 933 shortest path to the destination of the current Packet; 935 2. Other neighbors indicated in the RIB as Next Hops on path to the 936 destination of the current Packet; 938 3. All other symmetric neighbors (except the Previous Hop of the 939 current Packet). 941 Additional information from the RIB or the list of symmetric 942 neighbors MAY be used for determining the order, such as route cost 943 or link quality. 945 If the candidate Next Hop list created as specified in this section 946 is empty, the selected Next Hop MUST be P_prev_hop of the current 947 tuple; this case applies when returning the Packet to the Previous 948 Hop. 950 12. Sequence Numbers 952 Whenever a router generates a Packet or forwards a Packet on behalf 953 of a host or a router outside the routing domain where DFF is used, a 954 sequence number MUST be created and included in the DFF header. This 955 sequence number MUST be unique locally on each router where it is 956 created. A sequence number MUST start at 0 for the first Packet to 957 which the DFF header is added, and then increase in steps of 1 for 958 each new Packet. The sequence number MUST NOT be greater than 65535 959 and MUST wrap around to 0. 961 13. Modes of Operation 963 DFF can be used either as "route-over" IPv6 forwarding protocol, or 964 alternatively as "mesh-under" data forwarding protocol for the LoWPAN 965 adaptation layer ([RFC4944]). Previous sections have specified the 966 DFF mechanism in general; specific differences for each MoP are 967 specified in this section. 969 13.1. Route-Over 971 This section maps the general terminology from Section 2.2 to the 972 specific terminology when using the "route-over" MoP. 974 13.1.1. Mapping of DFF Terminology to IPv6 Terminology 976 The following terms are those listed in Section 2.2, and their 977 meaning is explicitly defined when DFF is used in the "route-over" 978 MoP: 980 Packet - An IPv6 packet, as specified in [RFC2460]. 982 Packet Header - An IPv6 extension header, as specified in [RFC2460]. 984 Address - An IPv6 address, as specified in [RFC4291]. 986 Originator Address - The Originator Address corresponds to the 987 Source address field of the IPv6 header as specified in [RFC2460]. 989 Destination Address - The Destination Address corresponds to the 990 Destination field of the IPv6 header as specified in [RFC2460]. 992 Next Hop - The Next Hop is the IPv6 address of the next hop to which 993 the Packet is sent; the link layer address from that IP address is 994 resolved by a mechanism such as ND [RFC4861]. The link layer 995 address is then used by L2 as destination. 997 Previous Hop - The Previous Hop is the IPv6 address from the 998 interface of the previous hop from which the Packet has been 999 received. 1001 Hop Limit - The Hop Limit corresponds to the Hop Limit field in the 1002 IPv6 header as specified in [RFC2460]. 1004 13.1.2. Packet Format 1006 In the "route-over" MoP, all IPv6 Packets MUST conform with the 1007 format specified in [RFC2460]. 1009 The DFF header, as specified below, is an IPv6 Extension Hop-by-Hop 1010 Options header, and is depicted in Figure 1 (where DUP is abbreviated 1011 to D, and RET is abbreviated to R because of the limited space in the 1012 figure). This document specifies a new option to be used inside the 1013 Hop-by-Hop Options header, which contains the DFF fields (DUP and RET 1014 flags and sequence number, as specified in Section 7). 1016 [RFC6564] specifies: 1018 New options for the existing Hop-by-Hop Header SHOULD NOT be 1019 created or specified unless no alternative solution is feasible. 1020 Any proposal to create a new option for the existing Hop-by-Hop 1021 Header MUST include a detailed explanation of why the hop-by-hop 1022 behavior is absolutely essential in the document proposing the new 1023 option with hop-by-hop behavior. 1025 [RFC6564] recommends to use Destination Headers instead of Hop-by-Hop 1026 Option headers. Destination Headers are only read by the destination 1027 of an IPv6 packet, not by intermediate routers. However, the 1028 mechanism specified in this document relies on intermediate routers 1029 reading and editing the header. Specifically, the sequence number 1030 and the DUP and RET flags are read by each router running the DFF 1031 protocol. Modifying the DUP flag and RET flag is essential for this 1032 protocol to tag duplicate or returned Packets. Without the DUP flag, 1033 a duplicate Packet cannot be discerned from a looping Packet, and 1034 without the RET flag, a returned Packet cannot be discerned from a 1035 looping Packet. 1037 1 2 3 1038 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 1039 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1040 | Next Header | Hdr Ext Len | OptTypeDFF | OptDataLenDFF | 1041 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1042 |VER|D|R|0|0|0|0| Sequence Number | Pad1 | 1043 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1045 Figure 1: IPv6 DFF Header 1047 Field definitions of the DFF header are as follows: 1049 Next Header - 8-bit selector. Identifies the type of header 1050 immediately following the Hop-by-Hop Options header. As specified 1051 in [RFC2460]. 1053 Hdr Ext Len - 8-bit unsigned integer. Length of the Hop-by-Hop 1054 Options header in 8-octet units, not including the first 8 octets. 1055 As specified in [RFC2460]. This value is set to 0 (zero). 1057 OptTypeDFF - 8-bit identifier of the type of option as specified in 1058 [RFC2460]. This value is set to IP_DFF. The two high order bits 1059 of the option type MUST be set to '11' and the third bit is equal 1060 to '1'. With these bits, according to [RFC2460], routers that do 1061 not understand this option on a received Packet discard the packet 1062 and, only if the packet's Destination Address was not a multicast 1063 address, send an ICMP Parameter Problem, Code 2, message to the 1064 packet's Source Address, pointing to the unrecognized Option Type. 1065 Also, according to [RFC2460], the values within the option are 1066 expected to change en route. 1068 OptDataLenDFF - 8-bit unsigned integer. Length of the Option Data 1069 field of this option, in octets as specified in [RFC2460]. This 1070 value is set to 2 (two). 1072 DFF fields - A 2-bit version field (abbreviated as VER), the DUP 1073 (abbreviated as D) and RET (abbreviated as R) flags follow after 1074 Mesh Forw, as specified in Section 7. The version specified in 1075 this document is 00. All other bits (besides VER, DUP, and RET) 1076 of this octet are reserved and MUST be set to 0. 1078 Sequence Number - A 16-bit field, containing an unsigned integer 1079 sequence number, as specified in Section 7. 1081 Pad1 - Since the Hop-by-Hop Options header must have a length of 1082 multiples of 8 octets, a Pad1 option is used, as specified in 1083 [RFC2460]. All bits of this octet are 0. 1085 13.2. Mesh-Under 1087 This section maps the general terminology from Section 2.2 to the 1088 specific terminology when using the "mesh-under" MoP. 1090 13.2.1. Mapping of DFF Terminology to LoWPAN Terminology 1092 The following terms are those listed in Section 2.2 (besides "Mode of 1093 Operation"), and their meaning is explicitly defined when DFF is used 1094 in the "mesh-under" MoP: 1096 Packet - A "LoWPAN encapsulated packet" (as specified in [RFC4944], 1097 which contains an IPv6 packet as payload. 1099 Packet Header - A LoWPAN header, as specified in [RFC4944]. 1101 Address - A 16-bit short or EUI-64 link layer address, as specified 1102 in [RFC4944]. 1104 Originator Address - The Originator Address corresponds to the 1105 Originator Address field of the Mesh Addressing header as 1106 specified in [RFC4944]. 1108 Destination Address - The Destination Address corresponds to the 1109 Final Destination field of the Mesh Addressing header as specified 1110 in [RFC4944]. 1112 Next Hop - The Next Hop is the destination address of a frame 1113 containing a LoWPAN encapsulated packet, as specified in 1114 [RFC4944]. 1116 Previous Hop - The Previous Hop is the source address of the frame 1117 containing a LoWPAN encapsulated packet, as specified in 1118 [RFC4944]. 1120 Hop Limit - The Hop Limit corresponds to the Deep Hops Left field in 1121 the Mesh Addressing header as specified in [RFC4944]. 1123 13.2.2. Packet Format 1125 In the "mesh-under" MoP, all IPv6 Packets MUST conform with the 1126 format specified in [RFC4944]. All data Packets exchanged by routers 1127 using this specification MUST contain the Mesh Addressing header as 1128 part of the LoWPAN encapsulation, as specified in [RFC4944]. 1130 The DFF header, as specified below, MUST follow the Mesh Addressing 1131 header. After these two headers, any other LoWPAN header, e.g., 1132 header compression or fragmentation headers, MAY also be added before 1133 the actual payload. Figure 2 depicts the Mesh Addressing header 1134 defined in [RFC4944], and Figure 3 depicts the DFF header. 1136 1 2 3 1137 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 1138 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1139 |1 0|V|F|HopsLft| DeepHopsLeft |orig. address, final address... 1140 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1142 Figure 2: Mesh Addressing Header 1144 1 2 3 1145 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 1146 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1147 |0 1| Mesh Forw |VER|D|R|0|0|0|0| sequence number | 1148 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 1150 Figure 3: Header for DFF data Packets 1152 Field definitions of the Mesh Addressing header are as specified in 1154 [RFC4944]. When adding that header to the LoWPAN encapsulation on 1155 the Originator, the fields of the Mesh Addressing header MUST be set 1156 to the following values: 1158 o V := 0 if the Originator Address is an IEEE extended 64-bit 1159 address (EUI-64); otherwise, V := 1 if it is a short 16-bit 1160 address. 1162 o F := 0 if the Final Destination Address is an IEEE extended 64-bit 1163 address (EUI-64); otherwise, F := 1 if it is a short 16-bit 1164 address. 1166 o Hops Left := 0xF (i.e., reserved value indicating that the Deep 1167 Hops Left field is following); 1169 o Deep Hops Left := MAX_HOP_LIMIT. 1171 Field definitions of the DFF header are as follows: 1173 Mesh Forw - A 6-bit identifier that allows for the use of different 1174 mesh forwarding mechanisms. As specified in [RFC4944], additional 1175 mesh forwarding mechanisms should use the reserved dispatch byte 1176 values following LOWPAN_BCO; therefore, 0 1 MUST precede Mesh 1177 Forw. The value of Mesh Forw is LOWPAN_DFF. 1179 DFF fields - A 2-bit version field (abbreviated as VER), the DUP 1180 (abbreviated as D) and RET (abbreviated as R) flags follow after 1181 Mesh Forw, as specified in Section 7. The version specified in 1182 this document is 00. All other bits (besides VER, DUP, and RET) 1183 of this octet are reserved and MUST be set to 0. 1185 Sequence Number - A 16-bit field, containing an unsigned integer 1186 sequence number, as specified in Section 7. 1188 14. Scope Limitation of DFF 1190 The forwarding mechanism specified in this document MUST be limited 1191 in scope to the routing domain in which DFF is used. That also 1192 implies that any headers specific to DFF do not traverse the 1193 boundaries of the routing domain. This section specifies, both for 1194 the "route-over" MoP and the "mesh-under" MoP, how to limit the scope 1195 of DFF to the routing domain in which it is used. 1197 Figure 4 to Figure 7 depict four different cases for source and 1198 destination of traffic with regards to the scope of the routing 1199 domain in which DFF is used. Section 14.2 and Section 14.1 specify 1200 how routers limit the scope of DFF for the "route-over" MoP and the 1201 "mesh-under" MoP respectively for these cases. In these sections, 1202 all nodes "inside the routing domain" are routers and use DFF, and 1203 may also be sources or destinations. Sources or destinations 1204 "outside the routing domain" do not run DFF and are either hosts 1205 attached to a router in the routing domain that is running DFF, or 1206 are themselves routers but outside the routing domain and not running 1207 DFF. 1209 +-----------------+ 1210 | | 1211 | (S) ----> (D) | 1212 | | 1213 +-----------------+ 1214 Routing Domain 1216 Figure 4: Traffic within the routing domain (from S to D) 1218 +-----------------+ 1219 | | 1220 | (S) --------> (R) --------> (D) 1221 | | 1222 +-----------------+ 1223 Routing Domain 1225 Figure 5: Traffic from within the routing domain to outside of the 1226 domain (from S to D) 1228 +-----------------+ 1229 | | 1230 (S) --------> (R) --------> (D) | 1231 | | 1232 +-----------------+ 1233 Routing Domain 1235 Figure 6: Traffic from outside the routing domain to inside the 1236 domain (from S to D) 1238 +-----------------+ 1239 | | 1240 (S) --------> (R1) -----------> (R2) --------> (D) 1241 | | 1242 +-----------------+ 1243 Routing Domain 1245 Figure 7: Traffic from outside the routing domain, traversing the 1246 domain and then to the outside of the domain (from S to D) 1248 14.1. Route-Over MoP 1250 In Figure 4, both the source and destination of the traffic are 1251 routers within the routing domain. If traffic is originated at S, 1252 the DFF header is added to the IPv6 header (as specified in 1253 Section 13.1.2). The Originator Address is set to S and the 1254 Destination Address is set to D. The Packet is forwarded to D using 1255 this specification. When router D receives the Packet, it processes 1256 the payload of the IPv6 Packet in upper layers. This case assumes 1257 that S has knowledge that D is in the routing domain, e.g., because 1258 of administrative setting based on the IP address of the Destination. 1259 If S has no knowledge about whether D is in the routing domain, IPv6- 1260 in-IPv6 tunnels as specified in [RFC2473] MUST be used. These cases 1261 are described in the following paragraphs. 1263 In Figure 5, the source of the traffic (S) is within the routing 1264 domain, and the destination (D) is outside of the routing domain. 1265 The IPv6 Packet, originated at S, MUST be encapsulated according to 1266 [RFC2473] (IPv6-in-IPv6 tunnels), and the DFF header added to the 1267 outer IPv6 header. S chooses the next router that should process the 1268 Packet as the tunnel exit-point (R). Administrative setting, as well 1269 as information from a routing protocol may be used to determine the 1270 tunnel exit-point. If no information is available which router to 1271 choose as tunnel exit-point, the Next Hop MUST be used as tunnel 1272 exit-point. In some cases, the tunnel exit-point will be the final 1273 router along a path towards the Packet's Destination, and the Packet 1274 will only traverse a single tunnel (e.g., if R is a known border 1275 router then S can choose R as tunnel exit- point). In other cases, 1276 the tunnel exit-point will not be the final router along the path to 1277 D, and the Packet may traverse multiple tunnels to reach the 1278 Destination; note that in this case, the DFF mechanism is only used 1279 inside each IPv6-in-IPv6 tunnel. The Originator Address of the 1280 Packet is set to S and the Destination Address is set to the tunnel 1281 exit-point (in the outer IPv6 header). The Packet is forwarded to 1282 the tunnel exit-point using this specification (potentially using 1283 multiple consecutive IPv6-in-IPv6 tunnels). When router R receives 1284 the Packet, it decapsulates the IPv6 Packet and forwards the inner 1285 IPv6 Packet to D, using normal IPv6 forwarding as specified in 1286 [RFC2460]. 1288 In Figure 6, the source of the traffic (S) is outside of the routing 1289 domain, and the destination (D) is inside of the routing domain. The 1290 IPv6 Packet, originated at S, is forwarded to R using normal IPv6 1291 forwarding as specified in [RFC2460]. Router R MUST encapsulate the 1292 IPv6 Packet according to [RFC2473], and add the DFF header (as 1293 specified in Section 13.1.2) to the outer IPv6 header. Like in the 1294 previous case, R has to select a tunnel exit-point; if it knows that 1295 D is in the routing domain (e.g., based on administrative settings), 1296 it SHOULD select D as the tunnel exit-point. In case it does not 1297 have any information which exit-point to select, it MUST use the Next 1298 Hop as tunnel exit-point, limiting the effectiveness of DFF to inside 1299 each IPv6-in-IPv6 tunnel. The Originator Address of the Packet is 1300 set to R, the Destination Address to the tunnel exit-point (both in 1301 the outer IPv6 header), the sequence number in the DFF header is 1302 generated locally on R. The Packet is forwarded to D using this 1303 specification. When router D receives the Packet, it decapsulates 1304 the inner IPv6 Packet and processes the payload of the inner IPv6 1305 Packet in upper layers. 1307 This mechanism is typically not used in transit networks; therefore, 1308 this case is discouraged, but described nevertheless for 1309 completeness: In Figure 7, both the source of the traffic (S) and the 1310 destination (D) are outside of the routing domain. The IPv6 Packet, 1311 originated at S, is forwarded to R1 using normal IPv6 forwarding as 1312 specified in [RFC2460]. Router R1 MUST encapsulate the IPv6 Packet 1313 according to [RFC2473] and add the DFF header (as specified in 1314 Section 13.1.2). R1 selects a tunnel exit-point like in the previous 1315 cases; if R2 is, e.g., a known border router, then R1 can select R2 1316 as tunnel exit-point. The Originator Address is set to R1, the 1317 Destination Address to the tunnel exit-point (both in the outer IPv6 1318 header), the sequence number in the DFF header is generated locally 1319 on R1. The Packet is forwarded to the tunnel exit-point using this 1320 specification (potentially traversing multiple consecutive IPv6-in- 1321 IPv6 tunnels). When router R2 receives the Packet, it decapsulates 1322 the inner IPv6 Packet and forwards the inner IPv6 Packet to D, using 1323 normal IPv6 forwarding as specified in [RFC2460]. 1325 14.2. Mesh-Under MoP 1327 In Figure 4, both the source and destination of the traffic are 1328 routers within the routing domain. If traffic is originated at 1329 router S, the LoWPAN encapsulated Packet is created from the IPv6 1330 packet as specified in [RFC4944]. Then, the Mesh Addressing header 1331 and the DFF header (as specified in Section 13.2.2) are added to the 1332 LoWPAN encapsulation on router S. The Originator Address is set to S 1333 and the Destination Address is set to D. The Packet is then forwarded 1334 using this specification. When router D receives the Packet, it 1335 processes the payload of the Packet in upper layers. 1337 In Figure 5, the source of the traffic (S) is within the routing 1338 domain, and the destination (D) is outside of the routing domain 1339 (which is known by S to be outside the routing domain because D uses 1340 a different IP prefix from the PAN). The LoWPAN encapsulated Packet, 1341 originated at router S, is created from the IPv6 packet as specified 1342 in [RFC4944]. Then, the Mesh Addressing header and the DFF header 1343 (as specified in Section 13.2.2) are added to the LoWPAN 1344 encapsulation on router S. The Originator Address is set to S and the 1345 Destination Address is set to R, which is a known border router of 1346 the PAN. The Packet is then forwarded using this specification. 1347 When router R receives the Packet, it restores the IPv6 packet from 1348 the LoWPAN encapsulated Packet and forwards it to D, using normal 1349 IPv6 forwarding as specified in [RFC2460]. 1351 In Figure 6, the source of the traffic (S) is outside of the routing 1352 domain, and the destination (D) is inside of the routing domain. The 1353 IPv6 packet, originated at S, is forwarded to R using normal IPv6 1354 forwarding as specified in [RFC2460]. Router R (which is a known 1355 border router to the PAN) creates the LoWPAN encapsulated Packet from 1356 the IPv6 packet as specified in [RFC4944]. Then, R adds the Mesh 1357 Addressing header and the DFF header (as specified in 1358 Section 13.2.2). The Originator Address is set to R, the Destination 1359 Address to D, the sequence number in the DFF header is generated 1360 locally on R. The Packet is forwarded to D using this specification. 1361 When router D receives the Packet, it restores the IPv6 packet from 1362 the LoWPAN encapsulated Packet and processes the payload in upper 1363 layers. 1365 As LoWPANs are typically no transit networks, this case is 1366 discouraged, but described nevertheless for completeness: In 1367 Figure 7, both the source of the traffic (S) and the destination (D) 1368 are outside of the routing domain. The IPv6 packet, originated at S, 1369 is forwarded to R1 using normal IPv6 forwarding as specified in 1370 [RFC2460]. Router R1 (which is a known border router of the PAN) 1371 creates the LoWPAN encapsulated Packet from the IPv6 Packet as 1372 specified in [RFC4944]. Then, it adds the Mesh Addressing header and 1373 the DFF header (as specified in Section 13.2.2). The Originator 1374 Address is set to R1, the Destination Address to R2 (which is another 1375 border router towards the Destination), the sequence number in the 1376 DFF header is generated locally on R1. The Packet is forwarded to R2 1377 using this specification. When router R2 receives the Packet, it 1378 restores the IPv6 packet from the LoWPAN encapsulated Packet and 1379 forwards the IPv6 packet to D, using normal IPv6 forwarding as 1380 specified in [RFC2460]. 1382 15. MTU Exceedance 1384 When adding the DFF header as specified in Section 9.1 or when 1385 encapsulating the Packet as specified in Section 14, the Packet size 1386 may exceed the MTU. This is described in Section 5 of [RFC2460]. 1387 When the Packet size of a Packet to be forwarded by DFF exceeds the 1388 MTU, the following steps are executed: 1390 1. The router MUST discard the Packet. 1392 2. The router MAY log the event locally (depending on the storage 1393 capabilities of the router). 1395 3. The router MUST send back an ICMP Packet Too Big to the source of 1396 the Packet reporting back the Next Hop MTU considering the 1397 additional overhead of adding the headers. 1399 16. Security Considerations 1401 Based on the recommendations in [RFC3552], this section describes 1402 security threats to DFF, lists which attacks are out of scope, which 1403 attacks DFF is susceptible to, and which attacks DFF protects 1404 against. 1406 16.1. Attacks Out of Scope 1408 As DFF is a data forwarding protocol, any security issues concerning 1409 the payload of the Packets are not considered in this section. 1411 It is the responsibility of upper layers to use appropriate security 1412 mechanisms (IPsec, TLS, ...) according to application requirements. 1413 As DFF does not modify the contents of IP datagrams, other than the 1414 DFF header (which is a Hop-by-Hop Options extension header in the 1415 "route-over" MoP, and therefore not protected by IPsec), no special 1416 considerations for IPsec have to be addressed. 1418 Any attack that is not specific to DFF, but that applies in general 1419 to the link layer (e.g., wireless, PLC), is out of scope. In 1420 particular, these attacks are: Eavesdropping, Packet insertion, 1421 Packet replaying, Packet deletion, and man-in-the-middle attacks. 1422 Appropriate link-layer encryption can mitigate part of these attacks 1423 and is therefore RECOMMENDED. 1425 16.2. Protection Mechanisms of DFF 1427 DFF itself does not provide any additional integrity, confidentiality 1428 or authentication. Therefore, the level of protection of DFF depends 1429 on the underlying link layer security as well as protection of the 1430 payload by upper layer security (e.g., IPsec). 1432 In the following sections, whenever encrypting or digitally signing 1433 Packets is suggested for protecting DFF, it is assumed that routers 1434 are not compromised. 1436 16.3. Attacks In Scope 1438 This section discusses security threats to DFF, and for each 1439 describes whether (and how) DFF is affected by the threat. DFF is 1440 designed to be used in lossy and unreliable networks. Predominant 1441 examples of lossy networks are wireless networks, where routers send 1442 Packets via broadcast. The attacks listed below are easier to 1443 exploit in wireless media, but can also be observed in wired 1444 networks. 1446 16.3.1. Denial of Service 1448 Denial of Service attacks are possible when using DFF by either 1449 exceeding the storage on a router, or by exceeding the available 1450 bandwidth of the channel. As DFF does not contain any algorithms 1451 with high complexity, it is unlikely that the processing power of the 1452 router could be exhausted by an attack on DFF. 1454 The storage of a router can be exhausted by increasing the size of 1455 the Processed Set, i.e., by adding new tuples, or by increasing the 1456 size of each tuple. New tuples can be added by injecting new Packets 1457 in the network, or by forwarding overheard Packets. 1459 Another possible DoS attack is to send Packets to a non-existing 1460 Address in the network. DFF would perform a depth-first search until 1461 the Hop Limit has reached zero. Is is therefore RECOMMENDED to set 1462 the Hop Limit to a value that limits the path length. 1464 If security provided by the link layer is used, this attack can be 1465 mitigated if the malicious router does not possess valid credentials, 1466 since other routers would not forward data through the malicious 1467 router. 1469 16.3.2. Packet Header Modification 1471 The following attacks can be exploited by modifying the Packet Header 1472 information, unless additional security (such as link layer security) 1473 is used: 1475 16.3.2.1. Return Flag Tampering 1477 A malicious router may tamper the "return" flag of a DFF Packet, and 1478 send it back to the previous hop, but only if that router had been 1479 selected as next hop by the receiving router before (as specified in 1480 Section 9.2). If the malicious router had not been selected as next 1481 hop, then a returned Packet is dropped by the receiving router. If, 1482 otherwise, the malicious router had been selected as next hop by the 1483 receiving router, and the malicious router has set the return flag, 1484 the receiving router would then try alternative neighbors. This may 1485 lead to Packets never reaching their Destination, as well as 1486 unnecessary depth-first search in the network (bandwidth exhaustion / 1487 energy drain). 1489 This attack can be mitigated by using appropriate security of the 1490 underlying link layer. 1492 16.3.2.2. Duplicate Flag Tampering 1494 A malicious router may modify the Duplicate Flag of a Packet that it 1495 forwards. 1497 If it changes the flag from 0 to 1, the Packet would be detected as 1498 duplicate by other routers in the network and not as looping packet. 1500 If the Duplicate Flag is set from 1 to 0, and a router receives that 1501 Packet for the second time (i.e., it has already received a Packet 1502 with the same Originator Address and sequence number before), it will 1503 wrongly detect a loop. 1505 This attack can be mitigated by using appropriate security of the 1506 underlying link layer. 1508 16.3.2.3. Sequence Number Tampering 1510 A malicious router may modify the sequence number of a Packet that it 1511 forwards. 1513 In particular, if the sequence number is modified to a number of 1514 another, previously sent, Packet of the same Originator, this Packet 1515 may wrongly be perceived as looping packet. 1517 This attack can be mitigated by using appropriate security of the 1518 underlying link layer. 1520 17. IANA Considerations 1522 IANA is requested to allocate a value from the Dispatch Type Field 1523 registry for LOWPAN_DFF. 1525 IANA is requested to allocate a value from the Destination Options 1526 and Hop-by-Hop Options registry for IP_DFF. The first three bits of 1527 that value MUST be 111. 1529 18. Acknowledgements 1531 Jari Arkko (Ericsson), Antonin Bas (Ecole Polytechnique), Thomas 1532 Clausen (Ecole Polytechnifque), Yuichi Igarashi (Hitachi), Kazuya 1533 Monden (Hitachi), Geoff Mulligan (Proto6), Hiroki Satoh (Hitachi), 1534 Ganesh Venkatesh (Mobelitix), and Jiazi Yi (Ecole Polytechnique) 1535 provided useful reviews of the draft and discussions which helped to 1536 improve this document. 1538 The authors also would like to thank Ralph Droms, Adrian Farrel, 1539 Stephen Farrell, Ted Lemon, Alvaro Retana, Dan Romascanu, and Martin 1540 Stiemerling for their reviews during IETF LC and IESG evaluation. 1542 19. References 1544 19.1. Normative References 1546 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 1547 Requirement Levels", BCP 14, RFC 2119, March 1997. 1549 [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 1550 (IPv6) Specification", RFC 2460, December 1998. 1552 [RFC2473] Conta, A. and S. Deering, "Generic Packet Tunneling in 1553 IPv6 Specification", RFC 2473, December 1998. 1555 [RFC4291] Hinden, R. and S. Deering, "IP Version 6 Addressing 1556 Architecture", RFC 4291, February 2006. 1558 [RFC4944] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, 1559 "Transmission of IPv6 Packets over IEEE 802.15.4 1560 Networks", RFC 4944, September 2007. 1562 [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc 1563 Network (MANET) Neighborhood Discovery Protocol (NHDP)", 1564 RFC 6130, April 2011. 1566 [RFC6564] Krishnan, S., Woodyatt, J., Kline, E., Hoagland, J., and 1567 M. Bhatia, "A Uniform Format for IPv6 Extension Headers", 1568 RFC 6564, April 2012. 1570 [RFC6724] Thaler, D., Draves, R., Matsumoto, A., and T. Chown, 1571 "Default Address Selection for Internet Protocol Version 6 1572 (IPv6)", RFC 6724, September 2012. 1574 19.2. Informative References 1576 [DFF_paper1] 1577 Cespedes, S., Cardenas, A., and T. Iwao, "Comparison of 1578 Data Forwarding Mechanisms for AMI Networks", 2012 IEEE 1579 Innovative Smart Grid Technologies Conference (ISGT), 1580 January 2012. 1582 [DFF_paper2] 1583 Iwao, T., Iwao, T., Yura, M., Nakaya, Y., Cardenas, A., 1584 Lee, S., and R. Masuoka, "Dynamic Data Forwarding in 1585 Wireless Mesh Networks", First IEEE International 1586 Conference on Smart Grid Communications (SmartGridComm), 1587 October 2010. 1589 [DFS_wikipedia] 1590 "Dynamic Data Forwarding in Wireless Mesh Networks", http 1591 ://en.wikipedia.org/w/ 1592 index.php?title=Depth-first_search&oldid=549733112, 1593 March 2013. 1595 [KCEC_press_release] 1596 Kit Carson Electric Cooperative (KCEC), "DFF deployed by 1597 KCEC (Press Release)", http://www.kitcarson.com/ 1598 index.php?option=com_content&view=article&id=45&Itemid=1, 1599 2011. 1601 [RFC3552] Rescorla, E. and B. Korver, "Guidelines for Writing RFC 1602 Text on Security Considerations", BCP 72, RFC 3552, 1603 July 2003. 1605 [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, 1606 "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, 1607 September 2007. 1609 [RFC6775] Shelby, Z., Chakrabarti, S., Nordmark, E., and C. Bormann, 1610 "Neighbor Discovery Optimization for IPv6 over Low-Power 1611 Wireless Personal Area Networks (6LoWPANs)", RFC 6775, 1612 November 2012. 1614 Appendix A. Examples 1616 In this section, some example network topologies are depicted, using 1617 the DFF mechanism for data forwarding. In these examples, it is 1618 assumed that a routing protocol is running which adds or inserts 1619 entries into the RIB. 1621 A.1. Example 1: Normal Delivery 1623 Figure 8 depicts a network topology with seven routers A to G, with 1624 links between them as indicated by lines. It is assumed that router 1625 A sends a Packet to G, through B and D, according to the routing 1626 protocol. 1628 +---+ 1629 +---+ D +-----+ 1630 | +---+ | 1631 +---+ | | 1632 +---+ B +---+ | 1633 | +---+ | | 1634 +-+-+ | +---+ +-+-+ 1635 | A | +---+ E +---+ G + 1636 +-+-+ +---+ +-+-+ 1637 | +---+ | 1638 +---+ C +---+ | 1639 +---+ | | 1640 | +---+ | 1641 +---+ F +-----+ 1642 +---+ 1644 Figure 8: Example 1: normal delivery 1646 If no link fails in this topology, and no loop occurs, then DFF 1647 forward the Packet along the Next Hops listed in each of the routers 1648 RIB along the path towards the destination. Each router adds a 1649 Processed Tuple for the incoming Packet, and selects the Next Hop as 1650 specified in Section 11, i.e., it will first select the next hop for 1651 router G as determined by the routing protocol. 1653 A.2. Example 2: Forwarding with Link Failure 1655 Figure 9 depicts the same topology as the Example 1, but both links 1656 between B and D and between B and E are unavailable (e.g., because of 1657 wireless link characteristics). 1659 +---+ 1660 XXX-+ D +-----+ 1661 X +---+ | 1662 +---+ X | 1663 +---+ B +---+ | 1664 | +---+ X | 1665 +-+-+ X +---+ +-+-+ 1666 | A | XXXX+ E +---+ G + 1667 +-+-+ +---+ +-+-+ 1668 | +---+ | 1669 +---+ C +---+ | 1670 +---+ | | 1671 | +---+ | 1672 +---+ F +-----+ 1673 +---+ 1675 Figure 9: Example 2: link failure 1677 When B receives the Packet from router A, it adds a Processed Tuple, 1678 and then tries to forward the Packet to D. Once B detects that the 1679 Packet cannot be successfully delivered to D because it does not 1680 receive link layer ACKs, it will follow the procedures listed in 1681 Section 10, by setting the DUP flag to 1, selecting E as new next 1682 hop, adding E to the list of next hops in the Processed Tuple, and 1683 then forwarding the Packet to E. 1685 As the link to E also fails, B will again follow the procedure in 1686 Section 10. As all possible next hops (D and E) are listed in the 1687 Processed Tuple, B will set the RET flag in the Packet and return it 1688 to A. 1690 A determines that it already has a Processed Tuple for the returned 1691 Packet, reset the RET flag of the Packet and select a new next hop 1692 for the Packet. As B is already in the list of next hops in the 1693 Processed Tuple, it will select C as next hop and forward the Packet 1694 to it. C will then forward the Packet to F, and F delivers the 1695 Packet to its Destination G. 1697 A.3. Example 3: Forwarding with Missed Link Layer Acknowledgment 1699 Figure 10 depicts the same topology as the Example 1, but the link 1700 layer acknowledgments from C to A are lost (e.g., because the link is 1701 uni-directional). It is assumed that A prefers a path to G through C 1702 and F. 1704 +---+ 1705 +---+ D +-----+ 1706 | +---+ | 1707 +---+ | | 1708 +---+ B +---+ | 1709 | +---+ | | 1710 +-+-+ | +---+ +-+-+ 1711 | A | +---+ E +---+ G + 1712 +-+-+ +---+ +-+-+ 1713 . +---+ | 1714 +...+ C +---+ | 1715 +---+ | | 1716 | +---+ | 1717 +---+ F +-----+ 1718 +---+ 1720 Figure 10: Example 3: missed link layer acknowledgment 1722 While C successfully receives the Packet from A, A does not receive 1723 the L2 ACK and assumes the Packet has not been delivered to C. 1724 Therefore, it sets the DUP flag of the Packet to 1, in order to 1725 indicate that this Packet may be a duplicate. Then, it forwards the 1726 Packet to B. 1728 A.4. Example 4: Forwarding with a Loop 1730 Figure 11 depicts the same topology as the Example 1, but there is a 1731 loop from D to A, and A sends the Packet to G through B and D. 1733 +-----------------+ 1734 | | 1735 | +-+-+ 1736 | +---+ D + 1737 | | +---+ 1738 \|/ +---+ | 1739 +---+ B +---+ 1740 | +---+ | 1741 +-+-+ | +---+ +-+-+ 1742 | A | +---+ E +---+ G + 1743 +-+-+ +---+ +-+-+ 1744 | +---+ | 1745 +---+ C +---+ | 1746 +---+ | | 1747 | +---+ | 1748 +---+ F +-----+ 1749 +---+ 1751 Figure 11: Example 4: loop 1753 When A receives the Packet through the loop from D, it will find a 1754 Processed Tuple for the Packet. Router A will set the RET flag and 1755 return the Packet to D, which in turn will return it to B. B will 1756 then select E as next hop, which will then forward it to G. 1758 Appendix B. Deployment Experience 1760 DFF has been deployed and experimented with both in real deployments 1761 and in network simulations, as described in the following. 1763 B.1. Deployments in Japan 1765 The majority of the large Advanced Metering Infrastructure (AMI) 1766 deployments using DFF are located in Japan, but the data of these 1767 networks is property of Japanese utilities and cannot be disclosed. 1769 B.2. Kit Carson Electric Cooperative 1771 DFF has been deployed at Kit Carson Electric Cooperative (KCEC), a 1772 non-profit organization distributing electricity to about 30,000 1773 customers in New Mexico. As described in a press release 1774 [KCEC_press_release], DFF is running on currently about 2000 electric 1775 meters. All meters are connected through a mesh network using an 1776 unreliable, wireless medium. DFF is used together with a distance 1777 vector routing protocol. Metering data from each meter is sent 1778 towards a gateway periodically every 15 minutes. The data delivery 1779 reliability is over 99%. 1781 B.3. Simulations 1783 DFF has been evaluated in Ns2 and OMNEST simulations, in conjunction 1784 with a distance vector routing protocol. The performance of DFF has 1785 been compared to using only the routing protocol without DFF. The 1786 results published in peer-reviewed academic papers 1787 ([DFF_paper1][DFF_paper2]) show significant improvements of the 1788 Packet delivery ratio compared to using only the distance vector 1789 protocol. 1791 B.4. Open Source Implementation 1793 Fujitsu Laboratories of America is currently working on an open 1794 source implementation of DFF, which is to be released in early 2013, 1795 and which allows for interoperability testings of different DFF 1796 implementations. The implementation is written in Java, and can be 1797 used both on real machines and in the Ns2 simulator. 1799 Authors' Addresses 1801 Ulrich Herberg (editor) 1802 Fujitsu 1803 1240 E. Arques Avenue, M/S 345 1804 Sunnyvale, CA 94085 1805 US 1807 Phone: +1 408 530-4528 1808 Email: ulrich.herberg@us.fujitsu.com 1810 Alvaro A. Cardenas 1811 University of Texas at Dallas 1812 School of Computer Science, 800 West Campbell Rd, EC 31 1813 Richardson, TX 75080-3021 1814 US 1816 Email: alvaro.cardenas@me.com 1818 Tadashige Iwao 1819 Fujitsu 1820 Shiodome City Center, 5-2, Higashi-shimbashi 1-chome, Minato-ku 1821 Tokyo, 1822 JP 1824 Phone: +81-44-754-3343 1825 Email: smartnetpro-iwao_std@ml.css.fujitsu.com 1827 Michael L. Dow 1828 Freescale 1829 6501 William Cannon Drive West 1830 Austin, TX 78735 1831 USA 1833 Phone: +1 512 895 4944 1834 Email: m.dow@freescale.com 1835 Sandra L. Cespedes 1836 U. Icesi 1837 Calle 18 No. 122-135 Pance 1838 Cali, Valle 1839 Colombia 1841 Phone: 1842 Email: scespedes@icesi.edu.co