RFC 6971

Depth-First Forwarding (DFF) in Unreliable Networks

📅 published June 2013, from ietf

RFC 6971: Depth-First Forwarding (DFF) in Unreliable Networks 🦋

Okay bestie, let's do the paperwork first 💅. This is RFC 6971, titled Depth-First Forwarding (DFF) in Unreliable Networks. It's filed as an Experimental doc (ISSN 2070-1721) and dated June 2013 🎀.

The authors are U. Herberg, Ed. (Fujitsu), A. Cardenas (University of Texas at Dallas), T. Iwao (Fujitsu), M. Dow (Freescale), and S. Cespedes (Icesi University). The header doesn't mark this RFC as obsoleting or updating any other document, so it's a standalone main character 🌟.

Abstract

Okay so the vibe here is: this doc defines Depth-First Forwarding (DFF) for IPv6 networks 🧚. It's a data-forwarding mechanism that makes delivery more reliable when your network topology keeps shifting and/or your links are lossy 😭. DFF lives entirely on the forwarding plane, but it can still chat with the routing plane 💬.

The way it works is kind of like a "depth-first search" hunting for a packet's destination 🔍. The routing plane can be told when a packet fails to get delivered or when a loop shows up 🔁. The spec covers two flavors: IPv6 networks (per RFC 2460) and "mesh-under" Low-Power Wireless Personal Area Networks (LoWPANs), per RFC 4944 🌸.

DFF assumes the link layer can detect whether a packet actually made it to the Next Hop ✅. It's meant for networks with little traffic, and it's for unicast transmissions only 💜.

Status of This Memo

Heads up, this one is not an Internet Standards Track spec 🙈. It's been published so people can examine it, experimentally implement it, and evaluate it 🧪.

It defines an Experimental Protocol for the Internet community 🌈. It's a product of the Internet Engineering Task Force (IETF), it represents IETF community consensus, it's had public review, and the Internet Engineering Steering Group (IESG) approved it for publication 👑. Not every IESG-approved doc is a candidate for any level of Internet Standard, so check Section 2 of RFC 5741 if you're curious 🤓.

For the latest status, errata, and feedback info, go to http://www.rfc-editor.org/info/rfc6971 🔗.

Copyright (c) 2013 IETF Trust and the persons identified as the document authors. All rights reserved ©️.

This doc is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info), as they stand on the publication date 📜. Please actually read these, because they spell out your rights and restrictions for this doc 🫶. Any Code Components pulled out of this document must include the Simplified BSD License text, as described in Section 4.e of the Trust Legal Provisions. They're also provided without warranty, as described in the Simplified BSD License ⚠️.

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  4
     1.1.  Motivation . . . . . . . . . . . . . . . . . . . . . . . .  4
     1.2.  Experiments to Be Conducted  . . . . . . . . . . . . . . .  5
   2.  Notation and Terminology . . . . . . . . . . . . . . . . . . .  6
     2.1.  Notation . . . . . . . . . . . . . . . . . . . . . . . . .  6
     2.2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . .  7
   3.  Applicability Statement  . . . . . . . . . . . . . . . . . . .  9
   4.  Protocol Overview and Functioning  . . . . . . . . . . . . . . 10
     4.1.  Overview of Information Sets . . . . . . . . . . . . . . . 11
     4.2.  Signaling Overview . . . . . . . . . . . . . . . . . . . . 11
   5.  Protocol Dependencies  . . . . . . . . . . . . . . . . . . . . 13
   6.  Information Sets . . . . . . . . . . . . . . . . . . . . . . . 13
     6.1.  Symmetric Neighbor List  . . . . . . . . . . . . . . . . . 13
     6.2.  Processed Set  . . . . . . . . . . . . . . . . . . . . . . 13
   7.  Packet Header Fields . . . . . . . . . . . . . . . . . . . . . 14
   8.  Protocol Parameters  . . . . . . . . . . . . . . . . . . . . . 15
   9.  Data Packet Generation and Processing  . . . . . . . . . . . . 15
     9.1.  Data Packets Entering the DFF Routing Domain . . . . . . . 16
     9.2.  Data Packet Processing . . . . . . . . . . . . . . . . . . 17
   10. Unsuccessful Packet Transmission . . . . . . . . . . . . . . . 19
   11. Determining the Next Hop for a Packet  . . . . . . . . . . . . 20
   12. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . 21
   13. Modes of Operation . . . . . . . . . . . . . . . . . . . . . . 21
     13.1. Route-Over . . . . . . . . . . . . . . . . . . . . . . . . 22
       13.1.1.  Mapping of DFF Terminology to IPv6 Terminology  . . . 22
       13.1.2.  Packet Format . . . . . . . . . . . . . . . . . . . . 22
     13.2. Mesh-Under . . . . . . . . . . . . . . . . . . . . . . . . 24
       13.2.1.  Mapping of DFF Terminology to LoWPAN Terminology  . . 24
       13.2.2.  Packet Format . . . . . . . . . . . . . . . . . . . . 25
   14. Scope Limitation of DFF  . . . . . . . . . . . . . . . . . . . 26
     14.1. Route-Over MoP . . . . . . . . . . . . . . . . . . . . . . 28
     14.2. Mesh-Under MoP . . . . . . . . . . . . . . . . . . . . . . 29
   15. MTU Exceedance . . . . . . . . . . . . . . . . . . . . . . . . 30
   16. Security Considerations  . . . . . . . . . . . . . . . . . . . 31
     16.1. Attacks That Are Out of Scope  . . . . . . . . . . . . . . 31
     16.2. Protection Mechanisms of DFF . . . . . . . . . . . . . . . 31
     16.3. Attacks That Are in Scope  . . . . . . . . . . . . . . . . 32
       16.3.1.  Denial of Service . . . . . . . . . . . . . . . . . . 32
       16.3.2.  Packet Header Modification  . . . . . . . . . . . . . 32
         16.3.2.1.  Return Flag Tampering . . . . . . . . . . . . . . 32
         16.3.2.2.  Duplicate Flag Tampering  . . . . . . . . . . . . 33
         16.3.2.3.  Sequence Number Tampering . . . . . . . . . . . . 33
   17. IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 33
   18. Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . 34
   19. References . . . . . . . . . . . . . . . . . . . . . . . . . . 34
     19.1. Normative References . . . . . . . . . . . . . . . . . . . 34
     19.2. Informative References . . . . . . . . . . . . . . . . . . 35
   Appendix A.  Examples  . . . . . . . . . . . . . . . . . . . . . . 36
     A.1.  Example 1: Normal Delivery . . . . . . . . . . . . . . . . 36
     A.2.  Example 2: Forwarding with Link Failure  . . . . . . . . . 37
     A.3.  Example 3: Forwarding with Missed Link-Layer
           Acknowledgment . . . . . . . . . . . . . . . . . . . . . . 38
     A.4.  Example 4: Forwarding with a Loop  . . . . . . . . . . . . 39
   Appendix B.  Deployment Experience . . . . . . . . . . . . . . . . 40
     B.1.  Deployments in Japan . . . . . . . . . . . . . . . . . . . 40
     B.2.  Kit Carson Electric Cooperative  . . . . . . . . . . . . . 40
     B.3.  Simulations  . . . . . . . . . . . . . . . . . . . . . . . 40
     B.4.  Open-Source Implementation . . . . . . . . . . . . . . . . 40

1. Introduction ✨

This doc specifies DFF for IPv6 networks, in two modes: plain IPv6 forwarding per [RFC2460] (we'll call this "route-over"), and "mesh-under" forwarding using the LoWPAN adaptation layer from [RFC4944] 🌐. DFF lives entirely on the forwarding plane, but it can interact with the routing plane 💫. The whole point is to boost delivery reliability in networks with dynamic topologies and/or lossy links 💖.

So DFF forwards data packets with a "depth-first search" for the packet's destination 🔎. It leans on an external neighborhood discovery mechanism, which gives a list of the router's neighbors that can be tried as Next Hops for a data packet 📋. On top of that, DFF can use info from the Routing Information Base (RIB) to decide what order to try the neighboring routers in 🧭.

If the packet doesn't make forward progress through the first chosen Next Hop, DFF will successively try all of the router's neighbors 🏃‍♀️. And if none of the Next Hops successfully receives or forwards the packet, DFF sends it back to the Previous Hop, which then tries alternate neighbors of its own 🔄.

Network topologies don't always form trees, so loops can happen 🌀. That's why DFF has a loop detection and avoidance mechanism built in 🛡️.

DFF may also provide information that, through a mechanism outside this spec, can be used to update the cost of routes in the RIB, based on whether packets were delivered successfully or not through alternative Next Hops 📈. A routing protocol may use this info too 🫶.

DFF assumes the underlying link layer can detect whether a packet was successfully delivered to the Next Hop 🕵️‍♀️. It's designed for networks with little traffic and it's used for unicast transmissions only 🦋.

1.1. Motivation 💅

Okay, so here's the problem 😩. In networks with dynamic topologies and/or lossy links, even frequent control message exchanges between routers, used to update routing tables, can't guarantee the routes match the network's actual topology at every moment 🌪️. A packet can get dropped because the topology changed since the last routing protocol update 💀.

Updating the routing protocol more often helps a bit 🙃. But it needs extra signaling, which eats channel and router resources (flooding control messages through the network, for example) 📡. That's a mess in lossy networks, because more control traffic can make things less stable thanks to collisions 💥. Extra control traffic can also drain the energy of battery-powered routers 🔋.

So the data-forwarding mechanism in this doc lets packets take alternate paths using a depth-first search, which boosts delivery reliability 🛤️. The goal is to cut the control traffic overhead in the network and, at the same time, bump up delivery success rates 🎯.

Since this spec is meant for experimentation, the mechanism is also specified for forwarding on the LoWPAN adaptation layer (according to Section 11 of [RFC4944]), not just IPv6 forwarding as specified in [RFC2460] 🧪. Apart from the different header formats, DFF works the same way for route-over and mesh-under 👯. So it's defined in general first, then more specifically for IPv6 route-over forwarding (Section 13.1) and LoWPAN adaptation layer mesh-under (Section 13.2) 🎀.

Part 1 of 8 is done, bestie 💖 more parts are coming, so stay tuned 🧚✨

1.2. Experiments to Be Conducted ✨

okay so this doc is an Experimental spec 🧪 that can make data delivery more reliable in networks with dynamic topology and/or lossy links 💖 once there's enough real-world experience, the plan is to revise it and move it onto the Standards Track 🚀 this experiment is meant for networks that match the applicability in Section 3 and stay inside the scope limits in Section 14 🎀 experimenting is encouraged there, but operators should be careful trying it in other kinds of networks, because how DFF and routing play together in those hasn't been established yet 🫶

experience reports about DFF implementation and deployment are super welcome, especially on:

  • Optimal values for the parameter P_HOLD_TIME, depending on the size of the network, the topology, and the amount of traffic originated per router. the longer a Processed Tuple is held, the more memory a router eats 💀 and if a tuple is held too long, a sequence number wrap-around may occur, so a new packet could have the same sequence number as one listed in an old Processed Tuple. but if the tuple expires too soon (before the packet has finished its path to the destination), it may be wrongly detected as a new packet instead of one already seen 😭
  • Optimal values for the parameter MAX_HOP_LIMIT, depending on the size of the network, the topology, and how lossy the link layer is. MAX_HOP_LIMIT makes sure packets don't needlessly wander around the network 🦋 it can be used to limit how big a "detour" a packet is allowed to take 🌸 the value may also be set on a per-packet basis if hop-count information is available from the RIB or routing protocol. in that case, the Hop Limit for the packet may be a percentage (e.g., 200%) of the hop-count value indicated in the routing table 🧚
  • Optimal methods to increase the cost of a route when a loop or lost Layer 2 (L2) ACK is detected by DFF. this isn't specified as a normative part of this document, but it may be of interest in an experiment to find good values for how much to increase link cost in the RIB or routing protocol 👑
  • Performance of using DFF in combination with different routing protocols, such as reactive and proactive protocols. this also covers how routes get updated by the RIB or routing protocol when DFF tells it about loops or broken links 🌈

2. Notation and Terminology 💅

The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. 🔥

okay and this document also uses the notation in Section 2.1 and the terminology in Section 2.2 🫶

2.1. Notation 🎀

here's the notation this document uses:

List: a list of elements is defined as [] for an empty list, [element] for a list with one element, and [element1, element2, ...] for a list with multiple elements 🍓

Concatenation of Lists: if List1 and List2 are lists, then List1@List2 is a new list with all elements of List1 first, followed by all elements of List2 💖

Byte Order: all packet formats in this specification use network byte order (most significant octet first) for all fields. the most significant bit in an octet is numbered bit 0, and the least significant bit of an octet is numbered bit 7. this is the one that trips everyone up, so bookmark it 🙈

Assignment: a := b. an assignment operator, where the left side (a) is assigned the value of the right side (b) ✨

Comparison: c = d. a comparison operator that returns true if the value of the left side (c) is equal to the value of the right side (d) 🦋

Flags: this specification uses multiple 1-bit flags. a value of '0' of a flag means 'false'; a value of '1' means 'true' 🌸

2.2. Terminology 🧚

the terms "route-over" and "mesh-under", introduced in [RFC6775], are used in this document. "route-over" isn't only limited to IPv6 over Low-Power Wireless Personal Area Networks (6LoWPANs), it also applies to general IPv6 networks 🌈

Mesh-under: a topology where nodes are connected to a 6LoWPAN Border Router (6LBR) through a mesh using link-layer forwarding. so in a mesh-under configuration, all IPv6 hosts in a LoWPAN are only one IP hop away from the 6LBR. this topology simulates the typical IP-subnet topology with one router and multiple nodes in the same subnet 👑

Route-over: a topology where hosts are connected to the 6LBR through intermediate layer-3 (IP) routing. here, hosts are typically multiple IP hops away from a 6LBR. the route-over topology typically consists of a 6LBR, a set of 6LoWPAN Routers (6LRs), and hosts 💜

the following terms are used in this document too. because the DFF mechanism is specified for both route-over IPv6 and the mesh-under LoWPAN adaptation layer, these terms are generally defined here and then specifically mapped for each mode of operation in Section 13 🦋

Depth-First Search: "Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking" [DFS_wikipedia]. in this document, the algorithm for traversing a graph is applied to forwarding packets in a computer network, with nodes being routers 🍓

Routing Information Base (RIB): a table stored in the user space of an operating system of a router or host. the table lists routes to network destinations, as well as associated metrics with these routes 🎀

Mode of Operation (MoP): the DFF mechanism specified in this document can be used either as the "route-over" IPv6-forwarding mechanism (Mode of Operation: "route-over") or as the "mesh-under" LoWPAN adaptation layer (Mode of Operation: "mesh-under") ✨

Packet: an IPv6 packet (for "route-over" MoP) or a "LoWPAN-encapsulated packet" (for "mesh-under" MoP), containing an IPv6 packet as payload 🌸

Packet Header: an IPv6 extension header (for "route-over" MoP) or a LoWPAN header (for "mesh-under" MoP) 🧚

Address: an IPv6 address (for "route-over" MoP), or a 16-bit short or 64-bit Extended Unique Identifier (EUI-64) link-layer address (for "mesh-under" MoP) 💖

Originator: the router that added the DFF header (specified in Section 7) to a packet 👑

Originator Address: an address of the Originator. according to [RFC6724], this address SHOULD be selected from the addresses that are configured on the interface that transmits the packet 🫶

Destination: the router or host to which a packet is finally destined. in case this router or host is outside of the routing domain in which DFF is used, the destination is the router that removes the DFF header (specified in Section 7) from the packet. this case is described in Section 14.1 🌈

Destination Address: an address to which the packet is sent 🦋

Next Hop: an address of the Next Hop to which the packet is sent along the path to the destination 🍓

Previous Hop: the address of the previous-hop router from which a packet has been received. in case the packet has been received by a router from outside of the routing domain where DFF is used (i.e., no DFF header is contained in the packet), the Originator Address of the router adding the DFF header to the packet is used as the Previous Hop 🙈

Hop Limit: an upper bound denoting how many times the packet may be forwarded 💅

3. Applicability Statement ✨

okay so this doc is about DFF, a packet-forwarding mechanism made for networks with dynamic topology and/or lossy links 🦋 its whole goal is making data delivery more reliable, and its applicability comes down to these traits, bestie:

  • It works for IPv6 networks, either as a "route-over" forwarding mechanism using IPv6 [RFC2460], or as a "mesh-under" forwarding mechanism using the frame format for transmission of IPv6 packets, as defined in [RFC4944] 💖
  • It assumes the addresses in the network are either IPv6 addresses (if it's used as "route-over"), or 16-bit short or EUI-64 link-layer addresses, as specified in [RFC4944], if it's used as "mesh-under". In "mesh-under" mode, mixing 16-bit and EUI-64 addresses inside one DFF routing domain is allowed (if they conform with [RFC4944]), as long as DFF stays within one PAN (Personal Area Network) 🌸 It's also assumed that "route-over" mode and "mesh-under" mode are mutually exclusive in the same routing domain, so don't mix them 🙈
  • It assumes the underlying link layer can detect whether a packet was successfully delivered to the Next Hop or not (e.g., by L2 ACK messages). Examples of such underlying link layers are specified in IEEE 802.15.4 and IEEE 802.11 🔥
  • It's applicable in networks with lossy links and/or a dynamic topology. In networks with very stable links and a fixed topology, DFF won't bring any benefit (but it also won't be harmful, other than the extra overhead for the packet header) 🧚
  • It works in a completely distributed manner and doesn't depend on any central entity 👑
  • It's applicable for networks with little traffic in terms of packets per second, since every recently forwarded packet increases the state on a router 💀 The amount of traffic per time that DFF supports depends on the memory resources of the router running DFF, the density of the network, the loss rate of the channel, and the maximum Hop Limit for each packet. For each recently seen packet, a list of the Next Hops the packet has been sent to is stored in memory. Those stored entries can be deleted after an expiration time, so only recently received packets need storage on the router 🍓 Implementations are advised to measure and report rates of packets in the network, and also to report memory usage. That way, operators can spot memory exhaustion from growing information sets, or problems from sequence numbers wrapping around too fast 😭
  • It's applicable for dense topologies with multiple paths between each source and each destination 💅 Some topologies are less suitable for DFF: topologies that can be partitioned by removing a single router or link, topologies with multiple stub routers that each have a single link to the network, topologies with only a single path to a destination, or topologies where the "detour" a packet takes during the depth-first search to reach the destination would be too long. Note that how many retransmissions of a packet count as a "too long" path depends on the underlying link layer (capacity and probability of packet loss), plus how much bandwidth the applications running in the network need for data traffic 🌈 In those topologies the packet may never reach the destination, so unnecessary data packet transmissions can happen until the packet's Hop Limit hits zero and it gets dropped. That can eat up channel and router resources 😩
  • It's used for unicast transmissions only (not anycast or multicast) 🎀
  • It's for use within stub networks, and for traffic between a router inside the routing domain where DFF is used and a known border router. Examples of such networks are LoWPANs. Scope limitations are described in Section 14 ✨

4. Protocol Overview and Functioning 🦋

okay this is the main vibe check 💖 When a router is forwarding a packet using DFF, it builds a list of candidate Next Hops for that packet. This list is made per packet and it's ordered, and Section 11 has recommendations on how to order it. For example, it could list the Next Hops from the RIB first (if there are any), ordered by increasing cost, followed by other neighbors provided by an external neighborhood discovery 🫶 DFF then forwards the packet to the first Next Hop on the list. If the transmission didn't succeed (as the underlying link layer decides), or if the packet was "returned" by a Next Hop it had already been sent to before, the router tries the next Next Hop on the list. A router "returns" a packet to the router it was originally received from once it's tried every element in the candidate Next Hop list and none worked 😤 And if the packet makes it back to the Originator, and the Originator has run out of all its Next Hops for that packet, the packet gets dropped 🥀

Each router running DFF stores info about each recently forwarded packet as an entry in an information set called the "Processed Set" 📚 Every entry has a sequence number from the packet header that identifies the packet (see Section 12 for more on the sequence number). The entry also holds a list of the Next Hops the packet was sent to. This list is what lets DFF avoid loops when forwarding a packet, which is honestly so clever 🧠 Entries in the Processed Set expire after a set expiration timeout and then get removed 🕰️

4.1. Overview of Information Sets

this spec needs exactly one set on each router: the Processed Set 💜 It stores the sequence number, the Originator Address, the Previous Hop, and a list of the Next Hops the packet was sent to, for each recently seen packet. Entries get removed after a predefined timeout. Every time a packet is forwarded to a Next Hop, that Next Hop gets added to the packet's entry in the list of Next Hops ✨

Heads up that an implementation can keep the Processed Set info in the form shown here, or in any other organization that still gives access to this info 🌸 Also, it's not necessary to remove tuples at the exact time indicated, as long as it behaves as if they were removed at that time. Totally flexible, no cap 💅

On top of the Processed Set, a list of symmetric neighbors has to be provided by an external neighborhood discovery mechanism, or it can be figured out from the RIB (for example, if the RIB has routes to adjacent routers, and those one-hop routes are verified to be symmetric) 🔥

4.2. Signaling Overview

the router running DFF needs info on a per-packet basis whenever it receives a packet 🎀 That info is encoded in the packet header specified in this document as the IPv6 Hop-by-Hop Options header and the LoWPAN header, for the "route-over" and "mesh-under" Modes of Operation respectively. This DFF header carries a sequence number used to uniquely identify a packet, plus two flags: RET (for "return") and DUP (for "duplicate") 🦋

While a router is trying to send a data packet to one or more of its neighbors, RET = 0. If none of the transmissions of the packet to the router's neighbors succeed, the packet is returned to the router it was first received from, by setting the return flag (RET := 1) 🧚 The RET flag is what tells a deliberately returned packet apart from a looping one. If a router receives a packet with RET = 1 (and DUP = 0 or DUP = 1) that it has already forwarded, the packet was deliberately returned, so the router keeps sending it to routers from the candidate Next Hop list. If the packet has RET = 0, the router assumes it's looping and returns it to the router it was last received from 🌀 An external mechanism can use this info to increase the route cost, in the RIB or the routing protocol, of the route to the destination via the Next Hop that caused the loop. Specifying such a mechanism is out of scope for this document 🙅‍♀️ Also, once DUP is set to 1, loop detection isn't possible anymore, because the flag never gets reset. So a packet may loop if the RIBs of the routers in the domain are inconsistent, until its Hop Limit reaches 0 😵‍💫

Whenever a packet transmission to a neighbor fails (as the underlying link layer determines, e.g., using L2 ACKs), the DUP flag gets set in the packet header for the following transmissions 🥺 The reasoning: the neighbor may have received the packet fine and only the L2 ACK got lost, which can cause possible duplicates of the packet in the network. The DUP flag tags that possible duplicate 🏷️ The DUP flag is what tells a duplicated packet apart from a looping one. If a router receives a packet with DUP = 1 (and RET = 0) that it has already forwarded, it's not treated as looping, and it's forwarded on to the next router from the candidate Next Hop list. If the received packet has DUP = 0 (and RET = 0), the router assumes it's looping, sets RET := 1, and returns it to the Previous Hop. Again, an external mechanism can use this info to increase route costs and/or inform the routing protocol 💫

The reason received duplicated packets (with DUP = 1) don't get dropped is that a duplicated packet can get duplicated again on its path if another L2 ACK gets lost 😱 But once DUP is already 1, there's no way to tell the duplicate apart from the duplicate of the duplicate. So loop detection stops working after the second lost L2 ACK on a packet's path. And if duplicates were simply dropped, the packet might actually have been a looping one (not a duplicate), and then the depth-first search would get interrupted 🙈

5. Protocol Dependencies 💖

DFF MAY use info from the Routing Information Base (RIB), specifically to decide the order of preference for which Next Hops a packet should be forwarded to. For example, the packet might go to neighbors listed in the RIB as Next Hops to the destination first, preferring the ones with the lowest route cost 🌸 Section 11 has recommendations about the order of preference for a packet's Next Hops ✨

DFF MUST have access to a list of symmetric neighbors for each router. This list is provided by a neighborhood discovery protocol, such as the one defined in [RFC6130]. A neighborhood discovery protocol is not specified in this document 🫶

6. Information Sets 🧚

this section specifies the information sets DFF uses 💜

6.1. Symmetric Neighbor List 💖

okay so DFF MUST have access to a list of addresses of symmetric neighbors of the router 🦋 bestie, this list can come from an external neighborhood discovery mechanism, or it can be figured out from the RIB. like, if the RIB gives you routes to adjacent routers and those one-hop routes are verified to be symmetric, you've got your list 🧚 the list itself isn't specified in this document, fr fr. those addresses get used to build the list of candidate Next Hops for a packet, as specified in Section 11 ✨

6.2. Processed Set 🎀

every router keeps a Processed Set so loop detection can actually work 🔁 it's giving memory 🧠 it tracks sequence numbers of packets it already got, plus a list of Next Hops that the packet was sent to one after another during the depth-first forwarding mechanism. so yeah, it's a whole diary of where packets have been 💅

it is recommended that an implementation keeps the Processed Set in non-volatile storage if the router actually has some 💾 that's the lowkey best move

each Processed Tuple looks like this:

(P_orig_address, P_seq_number, P_prev_hop,
P_next_hop_neighbor_list, P_time)

and here's what each piece means 👑

  • P_orig_address is the Originator Address of the received packet 🌸
  • P_seq_number is the sequence number of the received packet 🔢
  • P_prev_hop is the address of the Previous Hop of the packet 🚪
  • P_next_hop_neighbor_list is a list of addresses of Next Hops that the packet was sent to earlier, as part of the depth-first forwarding mechanism, as specified in Section 9.2 🌈
  • P_time says when this tuple expires, and at that point it MUST be removed 🗑️ bye bye tuple!!

now the tea ☕ if a router has no non-volatile storage, or not enough of it (limited resources, you know the drill 🥲), or it just chooses not to make the Processed Set persistent, then packets that are already stuck in a loop from the routing protocol might keep looping until the Hop Limit runs out 🌀 and non-looping packets might get sent to Next Hops that already got the packet and will send it right back, so you get some extra unnecessary retransmissions 😭 the good news is this effect is only temporary and only hits packets already traveling through the network ✨

7. Packet Header Fields 🍓

this section lists the info DFF needs in the packet header 📦 depending on whether DFF is running in the route-over MoP or the mesh-under MoP, the DFF header is either an IPv6 Hop-by-Hop Options header (as specified in Section 13.1.2) or a LoWPAN header (as specified in Section 13.2.2) 🫶 those sections are where the exact order, format, and encoding of the fields live, so go there if you're building this for real 🧑‍💻

  • Version (VER) is a 2-bit value that tells you which version of DFF is being used 🔖 this spec defines value 00. packets with other version values MUST be forwarded using the route-over MoP and mesh-under MoP as defined in [RFC2460] and [RFC4944], respectively 🦋
  • Duplicate (DUP) Packet Flag is a 1-bit flag that gets set in the DFF header when a packet is being retransmitted because the link layer signaled that the original transmission failed, as specified in Section 9.2 📡 once that flag is set to 1, routers forwarding the packet MUST NOT modify it 🔒 hands off, bestie!
  • Return (RET) Packet Flag is a 1-bit flag that MUST be set to 1 before the packet gets sent back to the Previous Hop 🔙 when a router gets a packet with RET = 1, that flag MUST be set to 0 before the packet goes to a new candidate Next Hop, as specified in Section 9.2 🔄
  • Sequence Number is a 16-bit field with an unsigned integer that the Originator generates 🔢 it's unique to each router for each packet the DFF has been added to, as specified in Section 12. the Originator Address concatenated with the sequence number is basically an identifier for previously seen data packets 🪪 check Section 12 for more about sequence numbers, it's a whole thing 💅

8. Protocol Parameters 🧚

here are the parameters this spec uses ✨ they're configurable, they don't need to live in non-volatile storage, and implementations can change them at run-time 🔧 the defaults depend on network size, topology, link layer, and traffic patterns. figuring out good defaults is part of the experimentation from Section 1.2 🧪

P_HOLD_TIME 🕰️ is the time period after which a newly created or modified Processed Tuple expires and MUST be deleted. an implementation SHOULD pick a P_HOLD_TIME that's high enough that the Processed Tuple for a packet is still in memory on every forwarding router while the packet is transiting the routing domain 🧠 the value SHOULD be at least MAX_HOP_LIMIT times the expected time to send a packet to a router on the same link 📈 and the value MUST be lower than the time it takes for the same sequence number to be reached again after a wrap-around on the router identified by P_orig_address of the Processed Tuple ⏳ it's all about timing, bestie

MAX_HOP_LIMIT 🌍 is the initial value of Hop Limit, which is also the maximum number of times a packet gets forwarded in the routing domain 🚀 when you choose it, the size of the network, the distance between source and destination in hops, and the maximum possible "detour" of a packet SHOULD be considered (compared to the shortest path) 🗺️ info from the RIB MAY be used for this, if the RIB provides it 📚

9. Data Packet Generation and Processing 💜

this section walks through two things: handling a packet that's entering the DFF routing domain (so, one without a DFF header, Section 9.1) and forwarding a data packet from another router running DFF (Section 9.2) 💅

9.1. Data Packets Entering the DFF Routing Domain 🌸

this part applies to any data packet the first time it enters a routing domain where DFF is used 🚪 that happens when a brand new data packet is made on this router, or when a data packet gets forwarded in from outside the routing domain (like from a host attached to this router, or from a router outside the DFF domain) 🌐 before that packet (which we'll call the "current packet") gets transmitted, these steps MUST be executed:

  1. If required, encapsulate the packet, as specified in Section 14. 📦
  2. Add the DFF header to the current packet (to the outer header if the packet has been encapsulated) with:
    • DUP := 0;
    • RET := 0;
    • Sequence Number := a new sequence number of the packet (as specified in Section 12) 🔢
  3. Check that the packet does not exceed the MTU, as specified in Section 15. If it does, execute the procedures listed in Section 15 and don't process the packet any further 📏
  4. Select the Next Hop (we'll call it "next_hop") for the current packet, as specified in Section 11. 🎯
  5. Add a Processed Tuple to the Processed Set with:
    • P_orig_address := the Originator Address of the current packet;
    • P_seq_number := the sequence number of the current packet;
    • P_prev_hop := the Originator Address of the current packet;
    • P_next_hop_neighbor_list := [next_hop];
    • P_time := current time + P_HOLD_TIME. ⏰
  6. Pass the current packet to the underlying link layer for transmission to next_hop. If the transmission fails (as the link layer determines), the procedures in Section 10 MUST be executed. 🚨

9.2. Data Packet Processing 🦋

when a router receives a packet (the "current packet"), these tasks MUST be performed 📬 no cap, this is the core of it:

  1. If the packet header is malformed (meaning the header format isn't what this spec expects), drop the packet. 🗑️
  2. Otherwise, if the Destination Address of the packet matches an address of an interface on this router, deliver the packet to upper layers and don't process it any further, as specified below. 🎉
  3. Decrement the value of the Hop Limit field by one (1). ➖
  4. Drop the packet if Hop Limit gets decremented to zero, and don't process it any further, as specified below. 💀
  5. If there's no Processed Tuple (the "current tuple") in the Processed Set where both of these are true:
    • P_orig_address = the Originator Address of the current packet, AND;
    • P_seq_number = the sequence number of the current packet.

then:

  1. Add a Processed Tuple (the "current tuple") with:
    • P_orig_address := the Originator Address of the current packet;
    • P_seq_number := the sequence number of the current packet;
    • P_prev_hop := the Previous Hop Address of the current packet;
    • P_next_hop_neighbor_list := [];
    • P_time := current time + P_HOLD_TIME. ⏳
  2. Set RET to 0 in the DFF header. 🔄
  3. Select the Next Hop (the "next_hop") for the current packet, as specified in Section 11. 🎯
  4. P_next_hop_neighbor_list := P_next_hop_neighbor_list@[next_hop]; 📝
  5. Pass the current packet to the underlying link layer for transmission to next_hop. If the transmission fails (as the link layer determines), the procedures in Section 10 MUST be executed. 🚨
  1. Otherwise, if a tuple exists:
    1. If the return flag of the current packet is not set (RET = 0), which means a loop has been detected:
      1. Set RET := 1. 🔁
      2. Pass the current packet to the underlying link layer for transmission to the Previous Hop. 🔙
    2. Otherwise, if the return flag of the current packet is set (RET = 1):
      1. If the Previous Hop of the packet is not contained in the P_next_hop_neighbor_list of the current tuple, drop the packet. 🚫
      2. If the Previous Hop of the packet (the address of the router the current packet was just received from) equals P_prev_hop of the current tuple (the address of the router the current packet was first received from), drop the packet. 🙅‍♀️
      3. Set RET := 0. 🔄
      4. Select the Next Hop (the "next_hop") for the current packet, as specified in Section 11. 🎯
      5. Modify the current tuple:
        • P_next_hop_neighbor_list := P_next_hop_neighbor_list@[next_hop];
        • P_time := current time + P_HOLD_TIME.
      6. If the selected Next Hop equals P_prev_hop of the current tuple, as specified in Section 11 (meaning all candidate Next Hops have been tried unsuccessfully), set RET := 1. If this router (the router receiving the current packet) has the same address as the Originator Address of the current packet, drop the packet. 😤
      7. Pass the current packet to the underlying link layer for transmission to next_hop. If transmission fails (as the link layer determines), the procedures in Section 10 MUST be executed. 🚨

10. Unsuccessful Packet Transmission 💌

okay so DFF needs the link layer to tell it whether a packet actually reached the Next Hop 📬 If that signal never shows up, it counts as a delivery failure, and we call that packet the "current packet" 💅 The link layer MAY retry sending the packet multiple times (e.g., using exponential back-off) before deciding the Next Hop never got it 🔁 The steps below run whenever a delivery failure happens and Section 9 says to run them 🫶

  1. Flip the DUP flag in the DFF header of the current packet to 1 🚩
  2. Pick the Next Hop (we'll call it "next_hop" 💕) for the current packet, the way Section 11 spells out 🎯
  3. Find the Processed Tuple (the "current tuple") in the Processed Set with:
    • P_orig_address = the Originator Address of the current packet, AND;
    • P_seq_number = the sequence number of the current packet.
  4. If no current tuple is found, drop the packet. 👋
  5. Otherwise, modify the current tuple:
    • P_next_hop_neighbor_list := P_next_hop_neighbor_list@[next_hop];
    • P_time := current time + P_HOLD_TIME.
  6. If the selected next_hop is equal to P_prev_hop of the current tuple, as specified in Section 11 (i.e., all neighbors have been unsuccessfully tried), then:
    • RET := 1
    • Decrement the value of the Hop Limit field by one (1). Drop the packet if the Hop Limit is decremented to zero. 💀
  7. Otherwise
    • RET := 0
  8. Transmit the current packet to next_hop. If transmission fails (as determined by the link layer), and if the next_hop does not equal P_prev_hop from the current tuple, the procedures in Section 10 MUST be executed. 🔁✨

11. Determining the Next Hop for a Packet 🧭

When a router forwards a packet, it picks a valid Next Hop for that packet, as this section explains 🗺️ Once a Processed Tuple either existed when the packet came in (the "current packet") or got created, the Processed Tuple for that packet (the "current tuple") is guaranteed to be there 🫶

The Next Hop is chosen from a list of candidate Next Hops, ordered by decreasing priority 📋 This list gets made per packet 💅 The biggest possible candidate Next Hop list for a packet has every neighbor of the router (found through an external neighborhood discovery process) except the Previous Hop of the current packet 🌸 A smaller list MAY be used, if desired, and picking the size of the candidate Next Hop list is a local decision each router makes, which does not affect interoperability 🦋 A smaller list might reduce the path length of a packet crossing the network and cut down the state needed in the Processed Set, but it may result in valid paths that never get explored 🤷‍♀️ If information from the RIB is used, then the candidate Next Hop list MUST contain at least the Next Hop the RIB marks as the Next Hop on the shortest path to the destination, and it SHOULD contain all Next Hops the RIB marks as Next Hops on paths to the destination 🎀 If a Next Hop from the RIB equals the Previous Hop of the current packet, it MUST NOT be added to the candidate Next Hop list 🚫

The list MUST NOT contain addresses that are listed in P_next_hop_neighbor_list of the current tuple, so the packet doesn't get sent to the same neighbor over and over 🔁 Also, an address MUST NOT appear more than once in the list, for that same reason 🙅‍♀️ Plus, addresses of an interface of this router MUST NOT be added to the list 💖

The list has an order of preference, and packets go first to the Next Hops at the top of the list during depth-first processing, as specified in Sections 9.1 and 9.2 🏃‍♀️ The following order is RECOMMENDED, with the elements at the top having the highest preference 👑:

  1. The neighbor that is indicated in the RIB as the Next Hop on the shortest path to the destination of the current packet;
  2. Other neighbors indicated in the RIB as Next Hops on the path to the destination of the current packet;
  3. All other symmetric neighbors (except the Previous Hop of the current packet).

Additional information from the RIB or the list of symmetric neighbors (such as route cost or link quality) MAY be used for determining the order 📊

If the candidate Next Hop list made as specified in this section is empty, the selected Next Hop MUST be P_prev_hop of the current tuple. This case applies when the packet gets returned to the Previous Hop 🔙💜

12. Sequence Numbers 🔢

Whenever a router generates a packet, or forwards a packet on behalf of a host or a router outside the routing domain where DFF is used, a sequence number MUST be created and included in the DFF header ✨ This sequence number MUST be unique locally on each router where it is created 🔑 A sequence number MUST start at 0 for the first packet the DFF header gets added to, and then go up by 1 for each new packet 📈 The sequence number MUST NOT be greater than 65535 and MUST wrap around to 0 🔄 iconic counting, honestly 💅

13. Modes of Operation 🦋

DFF can be used either as the "route-over" IPv6-forwarding protocol, or as the "mesh-under" data-forwarding protocol for the LoWPAN adaptation layer [RFC4944] 🌈 Previous sections explained the DFF mechanism in general, and the differences for each MoP are specified in this section 🧚

13.1. Route-Over 🌸

This section maps the general terminology from Section 2.2 to the specific terminology used with the "route-over" MoP 🗝️

13.1.1. Mapping of DFF Terminology to IPv6 Terminology 🫧

The following terms are the ones listed in Section 2.2, and their meaning is explicitly defined when DFF is used in the "route-over" MoP 💖

  • Packet - An IPv6 packet, as specified in [RFC2460].
  • Packet Header - An IPv6 extension header, as specified in [RFC2460].
  • Address - An IPv6 address, as specified in [RFC4291].
  • Originator Address - The Originator Address corresponds to the Source Address field of the IPv6 header, as specified in [RFC2460].
  • Destination Address - The Destination Address corresponds to the destination field of the IPv6 header, as specified in [RFC2460].
  • Next Hop - The Next Hop is the IPv6 address of the node the packet is sent to. The link-layer address for that IP address is resolved by a mechanism such as Neighbor Discovery (ND) [RFC4861]. L2 then uses the link-layer address as the destination. 📮
  • Previous Hop - The Previous Hop is the IPv6 address from the interface of the node the packet was received from. 🔙
  • Hop Limit - The Hop Limit corresponds to the Hop Limit field in the IPv6 header, as specified in [RFC2460]. ⏳

13.1.2. Packet Format 📦

In the "route-over" MoP, all IPv6 packets MUST conform with the format specified in [RFC2460] 🫶

The DFF header, as specified below, is an IPv6 Hop-by-Hop Options header, and it's drawn in Figure 1 (where DUP is shortened to D, and RET is shortened to R because the figure is tight on space) 🎀 This document specifies a new option to go inside the Hop-by-Hop Options header, which holds the DFF fields (the DUP and RET flags and the sequence number, as specified in Section 7) 🍓

[RFC6564] specifies:

New options for the existing Hop-by-Hop Header SHOULD NOT be created or specified unless no alternative solution is feasible. Any proposal to create a new option for the existing Hop-by-Hop Header MUST include a detailed explanation of why the hop-by-hop behavior is absolutely essential in the document proposing the new option with hop-by-hop behavior.

[RFC6564] recommends using destination headers instead of Hop-by-Hop Options headers. Destination headers are only read by the destination of an IPv6 packet, not by intermediate routers. However, the mechanism specified in this document relies on intermediate routers reading and editing the header. Specifically, the sequence number and the DUP and RET flags are read by each router running the DFF protocol. Modifying the DUP and RET flags is essential for this protocol to tag duplicate or returned packets. Without the DUP flag, a duplicate packet cannot be discerned from a looping packet, and without the RET flag, a returned packet cannot be discerned from a looping packet. 😭🫶

                      1                   2                   3
  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |  Next Header  |  Hdr Ext Len  |  OptTypeDFF   | OptDataLenDFF |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |VER|D|R|0|0|0|0|        Sequence Number        |      Pad1     |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Figure 1: IPv6 DFF Header 🖼️

Field definitions of the DFF header are as follows 📝

  • Next Header - 8-bit selector. Identifies the type of header immediately following the Hop-by-Hop Options header, as specified in [RFC2460].
  • Hdr Ext Len - 8-bit unsigned integer. Length of the Hop-by-Hop Options header in 8-octet units, not including the first 8 octets, as specified in [RFC2460]. This value is set to 0 (zero).
  • OptTypeDFF - 8-bit identifier of the type of option, as specified in [RFC2460]. This value is set to IP_DFF. The two high-order bits of the option type MUST be set to '11', and the third bit is equal to '1'. With these bits, according to [RFC2460], routers that do not understand this option on a received packet discard the packet and, only if the packet's Destination Address was not a multicast address, send an ICMP Parameter Problem (Code 2) message to the packet's Source Address, pointing to the unrecognized option type. Also, according to [RFC2460], the values within the option are expected to change en route. 🧐
  • OptDataLenDFF - 8-bit unsigned integer. Length of the option data field of this option, in octets, as specified in [RFC2460]. This value is set to 2 (two).
  • DFF fields - A 2-bit version field (abbreviated as VER); the DUP (abbreviated as D) and RET (abbreviated as R) flags follow after Mesh Forw, as specified in Section 13.2.2. The version specified in this document is '00'. All other bits (besides VER, DUP, and RET) of this octet are reserved and MUST be set to 0. 🔢
  • Sequence Number - A 16-bit field, containing an unsigned integer sequence number, as specified in Section 7. 🔁
  • Pad1 - Since the Hop-by-Hop Options header must have a length that is a multiple of 8 octets, a Pad1 option is used, as specified in [RFC2460]. All bits of this octet are 0. 🧸

13.2. Mesh-Under 🌊

This section maps the general terminology from Section 2.2 to the specific terminology used with the "mesh-under" MoP 💜

13.2.1. Mapping of DFF Terminology to LoWPAN Terminology

okay so this is the translation guide 💅 the terms from Section 2.2 (except "Mode of Operation") get their own specific meaning when DFF runs in the "mesh-under" MoP 🦋

  • Packet - a "LoWPAN-encapsulated packet" (as specified in [RFC4944]) that carries an IPv6 packet as its payload 🎀
  • Packet Header - a LoWPAN header, as specified in [RFC4944] ✨
  • Address - a 16-bit short or EUI-64 link-layer address, as specified in [RFC4944] 🌸
  • Originator Address - this matches the Originator Address field of the Mesh Addressing header, as specified in [RFC4944] 🧚
  • Destination Address - this matches the Final Destination field of the Mesh Addressing header, as specified in [RFC4944] 💖
  • Next Hop - the Destination Address of a frame carrying a LoWPAN-encapsulated packet, as specified in [RFC4944] 🦋
  • Previous Hop - the Source Address of the frame carrying a LoWPAN-encapsulated packet, as specified in [RFC4944] 🌈
  • Hop Limit - this corresponds to the Deep Hops Left field in the Mesh Addressing header, as specified in [RFC4944] 🍓

13.2.2. Packet Format

bestie, this is where the headers get stacked up 🥞 in the "mesh-under" MoP, every IPv6 packet MUST conform with the format in [RFC4944] ✨ and every data packet that routers send under this spec MUST carry the Mesh Addressing header as part of the LoWPAN encapsulation, as [RFC4944] describes 💅

the DFF header MUST come right after the Mesh Addressing header 🎀 then, if you want, you MAY also add other LoWPAN headers before the actual payload, like header compression or fragmentation headers 🌸 Figure 2 shows the Mesh Addressing header from [RFC4944], and Figure 3 shows the DFF header 🦋

                      1                   2                   3
  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |1 0|V|F|HopsLft| DeepHopsLeft  |orig. address, final address...
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                 Figure 2: Mesh Addressing Header


                      1                   2                   3
  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |0 1| Mesh Forw |VER|D|R|0|0|0|0|        sequence number        |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

               Figure 3: Header for DFF Data Packets

the field rules for the Mesh Addressing header are the ones from [RFC4944] 🧚 but when the Originator adds that header to the LoWPAN encapsulation, the fields MUST be set like this:

  • V := 0 if the Originator Address is an IEEE extended 64-bit address (EUI-64); otherwise, V := 1 if it is a short 16-bit address.
  • F := 0 if the Final Destination Address is an IEEE extended 64-bit address (EUI-64); otherwise, F := 1 if it is a short 16-bit address.
  • Hops Left := 0xF (i.e., a reserved value that tells you the Deep Hops Left field follows) 🍓
  • Deep Hops Left := MAX_HOP_LIMIT 🌈

now the DFF header fields 🥰

  • Mesh Forw - a 6-bit identifier that lets you use different mesh-forwarding mechanisms 💖 as [RFC4944] says, extra mesh-forwarding mechanisms should use the reserved dispatch byte values after LOWPAN_BC0, so '0 1' MUST precede Mesh Forw 🦋 the value of Mesh Forw is LOWPAN_DFF ✨
  • DFF fields - a 2-bit version field (abbreviated as VER) 🎀 the DUP flag (abbreviated as D) and the RET flag (abbreviated as R) come right after Mesh Forw, as specified in Section 13.2.2 🌸 the version in this document is '00' 💅 every other bit in this octet (besides VER, DUP, and RET) is reserved and MUST be set to 0 🔒
  • Sequence Number - a 16-bit field holding an unsigned integer sequence number, as specified in Section 7 🧚

14. Scope Limitation of DFF ✨

the forwarding mechanism in this document MUST be limited in scope to the routing domain where DFF is used 🌍 that also means any headers that are specific to DFF do not cross the edge of the routing domain 🚧 this section explains, for both the "route-over" MoP and the "mesh-under" MoP, how to keep DFF inside the routing domain it's used in 💜

Figures 4 to 7 show four different setups for where traffic starts and ends, compared to the routing domain where DFF is used 🦋 Sections 14.1 and 14.2 explain how routers keep DFF scoped for the "route-over" MoP and the "mesh-under" MoP respectively, for these cases 💅 in these sections, every node "inside the routing domain" is a router that uses DFF, and it may also be a source or a destination 🧚 sources or destinations "outside the routing domain" do not run DFF 😭 they are either hosts attached to a router inside the routing domain that runs DFF, or they are routers outside the routing domain that don't run DFF 🌸

                    +-----------------+
                    |                 |
                    |  (S) ----> (D)  |
                    |                 |
                    +-----------------+
                    Routing Domain

     Figure 4: Traffic within the Routing Domain (from S to D)

                    +-----------------+
                    |                 |
                    |  (S) --------> (R) --------> (D)
                    |                 |
                    +-----------------+
                    Routing Domain

        Figure 5: Traffic from Within the Routing Domain to
                Outside of the Domain (from S to D)

                    +-----------------+
                    |                 |
     (S) --------> (R) --------> (D)  |
                    |                 |
                    +-----------------+
                    Routing Domain

       Figure 6: Traffic from Outside the Routing Domain to
                  Inside the Domain (from S to D)

                    +-----------------+
                    |                 |
     (S) --------> (R1) -----------> (R2) --------> (D)
                    |                 |
                    +-----------------+
                    Routing Domain

 Figure 7: Traffic from Outside the Routing Domain, Traversing the
    Domain and Then to the Outside of the Domain (from S to D)

          Key:
              (S) = source router
              (D) = destination router
              (R), (R1), (R2) = other routers

14.1. Route-Over MoP

in Figure 4 🌟 both the source and the destination are routers inside the routing domain 🏠 if traffic starts at S, the DFF header goes onto the IPv6 header (as specified in Section 13.1.2) 🎀 the Originator Address is set to S and the Destination Address is set to D 💖 the packet is forwarded to D using this specification 🦋 when router D gets the packet, it processes the IPv6 payload in the upper layers 🧚 this case assumes S knows that D is in the routing domain, for example because of an administrative setting based on the destination's IP address 🌸 if S has no idea whether D is in the routing domain, IPv6-in-IPv6 tunnels as specified in [RFC2473] MUST be used 🚇 those cases are covered in the paragraphs below 💅

in Figure 5, the source (S) is inside the routing domain and the destination (D) is outside of it 🚪 the IPv6 packet from S MUST be encapsulated according to [RFC2473] (IPv6-in-IPv6 tunnels), and the DFF header MUST be added to the outer IPv6 header 🎀 S picks the next router that should process the packet as the tunnel exit-point (R) 🧚 administrative settings and information from a routing protocol can both help decide the tunnel exit-point 🦋 if there's no info about which router to pick as the tunnel exit-point, the Next Hop MUST be used as the tunnel exit-point 💜 sometimes the tunnel exit-point ends up being the final router on the path toward the packet's destination, so the packet only goes through one tunnel (like if R is a known border router, S can choose R as the tunnel exit-point) 🌈 other times the tunnel exit-point is NOT the final router on the way to D, so the packet might go through multiple tunnels to get there 😤 in that case, the DFF mechanism is only used inside each IPv6-in-IPv6 tunnel 🌸 the Originator Address is set to S and the Destination Address is set to the tunnel exit-point (in the outer IPv6 header) 💖 the packet is forwarded to the tunnel exit-point using this specification (possibly over several IPv6-in-IPv6 tunnels in a row) 🦋 when router R gets the packet, it decapsulates the IPv6 packet and forwards the inner IPv6 packet to D, using normal IPv6 forwarding as specified in [RFC2460] ✨

in Figure 6, the source (S) is outside the routing domain and the destination (D) is inside it 🌷 the IPv6 packet from S is forwarded to R using normal IPv6 forwarding as specified in [RFC2460] 🚀 router R MUST encapsulate the IPv6 packet according to [RFC2473] and add the DFF header (as specified in Section 13.1.2) to the outer IPv6 header 🎀 just like the previous case, R has to pick a tunnel exit-point 🧚 if it knows D is in the routing domain (for example from administrative settings), it SHOULD select D as the tunnel exit-point 🌟 if it has no info about which exit-point to pick, it MUST use the Next Hop as the tunnel exit-point, which limits DFF's effect to inside each IPv6-in-IPv6 tunnel 🥺 the Originator Address of the packet is set to R, the Destination Address is set to the tunnel exit-point (both in the outer IPv6 header), and the sequence number in the DFF header is generated locally on R 💅 the packet is forwarded to D using this specification 🦋 when router D gets the packet, it decapsulates the inner IPv6 packet and processes the inner IPv6 payload in the upper layers 💖

this mechanism is usually not used in transit networks, so it's discouraged 🙈 but it's described anyway, for completeness 📚 in Figure 7, both the source (S) and the destination (D) are outside the routing domain 🌍 the IPv6 packet from S is forwarded to R1 using normal IPv6 forwarding, as specified in [RFC2460] 🚀 router R1 MUST encapsulate the IPv6 packet according to [RFC2473] and add the DFF header (as specified in Section 13.1.2) 🎀 R1 picks a tunnel exit-point like in the previous cases; for example, if R2 is a known border router, R1 can select R2 as the tunnel exit-point 🧚 the Originator Address is set to R1, the Destination Address is set to the tunnel exit-point (both in the outer IPv6 header), and the sequence number in the DFF header is generated locally on R1 💜 the packet is forwarded to the tunnel exit-point using this specification (possibly going through several IPv6-in-IPv6 tunnels in a row) 🌈 when router R2 gets the packet, it decapsulates the inner IPv6 packet and forwards it to D, using normal IPv6 forwarding as specified in [RFC2460] ✨

14.2. Mesh-Under MoP 🦋

okay so in Figure 4, both the source and the destination are routers inside the routing domain 🌸 If the traffic starts at router S, the LoWPAN-encapsulated packet gets built from the IPv6 packet, as specified in [RFC4944]. Then the Mesh Addressing header and the DFF header (as specified in Section 13.2.2) get added onto that LoWPAN encapsulation on router S. The Originator Address is set to S and the Destination Address is set to D. The packet then gets forwarded using this specification. When router D receives it, D processes the payload up in the upper layers ✨

In Figure 5, the source (S) is inside the routing domain, but the destination (D) is outside of it. S knows D is outside because D uses a different IP prefix from the PAN 👀 The LoWPAN-encapsulated packet, originated at router S, is created from the IPv6 packet as specified in [RFC4944]. Then the Mesh Addressing header and the DFF header (as specified in Section 13.2.2) get added onto the LoWPAN encapsulation on router S. The Originator Address is set to S and the Destination Address is set to R, which is a known border router of the PAN. The packet then gets forwarded using this specification. When router R receives it, R restores the IPv6 packet from the LoWPAN-encapsulated packet and forwards it to D, using normal IPv6 forwarding as specified in [RFC2460] 💅

In Figure 6, it's flipped: the source (S) is outside the routing domain and the destination (D) is inside it 🔥 The IPv6 packet, originated at S, gets forwarded to R using normal IPv6 forwarding, as specified in [RFC2460]. Router R, which is a known border router to the PAN, creates the LoWPAN-encapsulated packet from the IPv6 packet, as specified in [RFC4944]. Then R adds the Mesh Addressing header and the DFF header (as specified in Section 13.2.2). The Originator Address is set to R, the Destination Address is set to D, and the sequence number in the DFF header is generated locally on R. The packet is forwarded to D using this specification. When router D receives it, D restores the IPv6 packet from the LoWPAN-encapsulated packet and processes the payload in the upper layers 🧚

Now the spicy one 🌶️ Figure 7 covers the case where both the source (S) and the destination (D) are outside of the routing domain. Because LoWPANs are typically not transit networks, this case is discouraged 🙈 It's only described here for completeness, so don't go building your life around it 💀 The IPv6 packet, originated at S, is forwarded to R1 using normal IPv6 forwarding, as specified in [RFC2460]. Router R1, which is a known border router of the PAN, creates the LoWPAN-encapsulated packet from the IPv6 packet, as specified in [RFC4944]. Then it adds the Mesh Addressing header and the DFF header (as specified in Section 13.2.2). The Originator Address is set to R1, the Destination Address is set to R2 (which is another border router towards the destination), and the sequence number in the DFF header is generated locally on R1. The packet is forwarded to R2 using this specification. When router R2 receives it, R2 restores the IPv6 packet from the LoWPAN-encapsulated packet and forwards that IPv6 packet to D, using normal IPv6 forwarding as specified in [RFC2460] 🌈

15. MTU Exceedance ✨

okay this part is about the size limit 📏 When the DFF header is added (as specified in Section 9.1), or when the packet gets encapsulated (as specified in Section 14), the packet can end up bigger than the MTU. This is described in Section 5 of [RFC2460]. So when a packet that DFF is about to forward goes over the MTU, these steps apply:

  1. The router MUST discard the packet. 🚫
  2. The router MAY log the event locally, depending on the storage capabilities of the router. 📝
  3. The router MUST send back an ICMP Packet Too Big message to the source of the packet and report back the Next Hop MTU, which includes the overhead of adding the headers 💌

16. Security Considerations 🔐

ngl this section is seriously important, so pay attention bestie 😭 It's based on the recommendations in [RFC3552]. It describes the security threats to DFF, lists which attacks are out of scope, which attacks DFF is susceptible to, and which attacks DFF protects against. Let's gooo 🫶

16.1. Attacks That Are Out of Scope 🙅

Since DFF is a data-forwarding protocol, any security issues about the payload of the packets aren't covered in this section 🎀

It's the job of the upper layers to use the right security mechanisms (IPsec, Transport Layer Security (TLS), etc.) based on what the application needs. DFF doesn't modify the contents of IP datagrams, except for the DFF header. In the "route-over" MoP, that DFF header is a Hop-by-Hop Options extension header, which means IPsec doesn't protect it. So no special IPsec considerations need to be handled here 💖

Any attack that isn't specific to DFF but applies in general to the link layer (e.g., wireless, Power Line Communication (PLC)) is also out of scope. Those attacks are: eavesdropping, packet insertion, packet replay, packet deletion, and man-in-the-middle attacks. Appropriate link-layer encryption can mitigate part of these attacks, so it is RECOMMENDED 🔒

16.2. Protection Mechanisms of DFF 🛡️

DFF doesn't provide any extra integrity, confidentiality, or authentication on its own 🥺 So how protected DFF is depends on the underlying link-layer security, plus the protection of the payload from upper-layer security (e.g., IPsec).

In the following sections, whenever encrypting or digitally signing packets is suggested to protect DFF, it's assumed that the routers are not compromised 🤞

16.3. Attacks That Are in Scope 🎯

This section talks about the security threats to DFF. For each one, it describes whether (and how) DFF is affected by the threat. DFF is designed for lossy and unreliable networks 📶 The predominant examples of lossy networks are wireless networks, where routers send packets via broadcast. The attacks listed below are easier to pull off on wireless media, but they can also show up in wired networks 👀

16.3.1. Denial of Service 💥

Denial-of-service (DoS) attacks are possible with DFF, either by exceeding the storage on a router or by exceeding the available bandwidth of the channel. DFF doesn't contain any algorithms with high complexity, so it's unlikely an attack on DFF could exhaust a router's processing power 🧠

A router's storage can get exhausted by growing the Processed Set, i.e., by adding new tuples or by increasing the size of each tuple. New tuples can be added by injecting new packets into the network or by forwarding overheard packets 📦

Another possible DoS attack is sending packets to a non-existing address in the network. DFF would then perform a depth-first search until the Hop Limit has reached zero 🌀 So it is RECOMMENDED to set the Hop Limit to a value that limits the path length 📏

If the security provided by the link layer is used, this attack can be mitigated when the malicious router doesn't have valid credentials. That's because other routers wouldn't forward data through the malicious router 🙅‍♀️

16.3.2. Packet Header Modification 🎀

The following attacks can be exploited by modifying the packet header information, unless additional security (such as link-layer security) is used 🧐

16.3.2.1. Return Flag Tampering 🔁

A malicious router may tamper with the "return" flag of a DFF packet and send it back to the Previous Hop. But this only works if the malicious router has been selected as the Next Hop by the receiving router (as specified in Section 9.2). If the malicious router had not been selected as the Next Hop, then a returned packet is dropped by the receiving router. Otherwise (i.e., the malicious router had been selected as the Next Hop by the receiving router, and the malicious router has set the return flag), the receiving router then tries alternative neighbors. This can lead to packets never reaching their destination, plus an unnecessary depth-first search in the network (bandwidth exhaustion / energy drain) 😩

This attack can be mitigated by using appropriate security of the underlying link layer 🔐

16.3.2.2. Duplicate Flag Tampering 👯

A malicious router may modify the Duplicate Flag of a packet that it forwards.

If it changes the flag from 0 to 1, the packet would be detected as a duplicate by other routers in the network, and not as a looping packet 🔄

If the Duplicate Flag is changed from 1 to 0, and a router receives that packet for the second time (i.e., it has already received a packet with the same Originator Address and sequence number before), it will wrongly detect a loop 🙃

This attack can be mitigated by using appropriate security of the underlying link layer 🔐

16.3.2.3. Sequence Number Tampering 🔢

A malicious router may modify the sequence number of a packet that it forwards.

In particular, if the sequence number is changed to the number of another, previously sent packet from the same Originator, that packet may be wrongly perceived as a looping packet 😵‍💫

This attack can be mitigated by using appropriate security of the underlying link layer 🔐

17. IANA Considerations 📋

IANA has allocated the value 01 000011 for LOWPAN_DFF from the Dispatch Type Field registry 🪄

IANA has allocated the value 0xEE for IP_DFF from the Destination Options and Hop-by-Hop Options registry. The first 3 bits of that value are 111 💜

18. Acknowledgments 🫶

Jari Arkko (Ericsson), Abdussalam Baryun (University of Glamorgan), Antonin Bas (Ecole Polytechnique), Thomas Clausen (Ecole Polytechnifque), Yuichi Igarashi (Hitachi), Kazuya Monden (Hitachi), Geoff Mulligan (Proto6), Hiroki Satoh (Hitachi), Ganesh Venkatesh (Mobelitix), and Jiazi Yi (Ecole Polytechnique) gave useful reviews of the draft and discussions, which helped make this document better 🌟

The authors also want to thank Ralph Droms, Adrian Farrel, Stephen Farrell, Ted Lemon, Alvaro Retana, Dan Romascanu, and Martin Stiemerling for their reviews during IETF LC and IESG evaluation 💐

19. References 📚

19.1. Normative References 🔗

  • [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997.
  • [RFC2460] Deering, S. and R. Hinden, "Internet Protocol, Version 6 (IPv6) Specification", RFC 2460, December 1998.
  • [RFC2473] Conta, A. and S. Deering, "Generic Packet Tunneling in IPv6 Specification", RFC 2473, December 1998.
  • [RFC4291] Hinden, R. and S. Deering, "IP Version 6 Addressing Architecture", RFC 4291, February 2006.
  • [RFC4944] Montenegro, G., Kushalnagar, N., Hui, J., and D. Culler, "Transmission of IPv6 Packets over IEEE 802.15.4 Networks", RFC 4944, September 2007.
  • [RFC6130] Clausen, T., Dearlove, C., and J. Dean, "Mobile Ad Hoc Network (MANET) Neighborhood Discovery Protocol (NHDP)", RFC 6130, April 2011.
  • [RFC6564] Krishnan, S., Woodyatt, J., Kline, E., Hoagland, J., and M. Bhatia, "A Uniform Format for IPv6 Extension Headers", RFC 6564, April 2012.
  • [RFC6724] Thaler, D., Draves, R., Matsumoto, A., and T. Chown, "Default Address Selection for Internet Protocol Version 6 (IPv6)", RFC 6724, September 2012.

19.2. Informative References 📚✨

Okay bestie, now the reading list 📚 These are the informative ones, so they're background to dig into, not rules to follow.

  • [DFF_paper1] Cespedes, S., Cardenas, A., and T. Iwao, "Comparison of Data Forwarding Mechanisms for AMI Networks", 2012 IEEE Innovative Smart Grid Technologies Conference (ISGT), January 2012.
  • [DFF_paper2] Iwao, T., Iwao, T., Yura, M., Nakaya, Y., Cardenas, A., Lee, S., and R. Masuoka, "Dynamic Data Forwarding in Wireless Mesh Networks", First IEEE International Conference on Smart Grid Communications (SmartGridComm), October 2010.
  • [DFS_wikipedia] Wikipedia, "Depth-first search", May 2013, <http://en.wikipedia.org/w/index.php?title=Depth-first_search&oldid=555203731>.
  • [KCEC_press_release] Kit Carson Electric Cooperative (KCEC), "DFF deployed by KCEC", Press Release, 2011, <http://www.kitcarson.com/index.php?option=com_content&view=article&id=45&Itemid=1>.
  • [RFC3552] Rescorla, E. and B. Korver, "Guidelines for Writing RFC Text on Security Considerations", BCP 72, RFC 3552, July 2003. 🔒
  • [RFC4861] Narten, T., Nordmark, E., Simpson, W., and H. Soliman, "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, September 2007.
  • [RFC6775] Shelby, Z., Chakrabarti, S., Nordmark, E., and C. Bormann, "Neighbor Discovery Optimization for IPv6 over Low-Power Wireless Personal Area Networks (6LoWPANs)", RFC 6775, November 2012.

Appendix A. Examples 🗺️

Time for the picture show 🎬 This appendix has some example network topologies, and every single one uses the DFF mechanism for data forwarding. We're also assuming a routing protocol is running that adds or inserts entries into the RIB.

A.1. Example 1: Normal Delivery 💖

Example 1 is a topology with seven routers, A to G, linked up the way the lines show. Router A sends a packet to G through B and D, following what the routing protocol says.

                                    +---+
                                +---+ D +-----+
                                |   +---+     |
                        +---+   |             |
                    +---+ B +---+             |
                    |   +---+   |             |
                  +-+-+         |   +---+   +-+-+
                  | A |         +---+ E +---+ G +
                  +-+-+             +---+   +-+-+
                    |   +---+                 |
                    +---+ C +---+             |
                        +---+   |             |
                                |   +---+     |
                                +---+ F +-----+
                                    +---+

Example 1: Normal Delivery

If no link fails and no loop shows up, DFF sends the packet along the Next Hops in the RIB of each router on the way to the destination. Each router adds a Processed Tuple for the incoming packet and picks the Next Hop as described in Section 11. So the first thing it does is pick the Next Hop for router G, as set by the routing protocol. ✨

Example 2 is the same topology as Example 1, except both the link between B and D and the link between B and E are down. (Maybe the wireless link is being moody 🌧️)

                                    +---+
                                XXXX+ D +-----+
                                X   +---+     |
                        +---+   X             |
                    +---+ B +---+             |
                    |   +---+   X             |
                  +-+-+         X   +---+   +-+-+
                  | A |         XXXX+ E +---+ G +
                  +-+-+             +---+   +-+-+
                    |   +---+                 |
                    +---+ C +---+             |
                        +---+   |             |
                                |   +---+     |
                                +---+ F +-----+
                                    +---+

Example 2: Link Failure

When B gets the packet from router A, it adds a Processed Tuple and then tries to send it to D. Once B figures out the packet can't reach D, because no link-layer ACKs come back, it follows the procedures in Section 10. That means it sets the DUP flag to 1, picks E as the new Next Hop, adds E to the list of Next Hops in the Processed Tuple, and forwards the packet to E. 🏃‍♀️

The link to E is down too, so B goes through the Section 10 procedure again. Since every possible Next Hop (D and E) is already in the Processed Tuple, B sets the RET flag on the packet and sends it back to A. 🔁

A notices it already has a Processed Tuple for the returned packet, resets the RET flag, and picks a new Next Hop. B is already in the list of Next Hops in the Processed Tuple, so A picks C as the Next Hop and forwards the packet there. C then forwards it to F, and F delivers it to its destination, G. 🎉

Example 3 is the same topology as Example 1, but the link-layer acknowledgments from C to A get lost. (Maybe the link only goes one way 🤷‍♀️) It's assumed that A prefers a path to G through C and F.

                                    +---+
                                +---+ D +-----+
                                |   +---+     |
                        +---+   |             |
                    +---+ B +---+             |
                    |   +---+   |             |
                  +-+-+         |   +---+   +-+-+
                  | A |         +---+ E +---+ G +
                  +-+-+             +---+   +-+-+
                    .   +---+                 |
                    +...+ C +---+             |
                        +---+   |             |
                                |   +---+     |
                                +---+ F +-----+
                                    +---+

Example 3: Missed Link-Layer Acknowledgment

C does get the packet from A, but A never sees the L2 ACK, so A assumes the packet never reached C. So A sets the DUP flag of the packet to 1, to flag that this packet might be a duplicate, and then forwards it to B. 👀

A.4. Example 4: Forwarding with a Loop 🌀

Example 4 is the same topology as Example 1, but there's a loop from D to A, and A sends the packet to G through B and D.

                    +-----------------+
                    |                 |
                    |               +-+-+
                    |           +---+ D +
                    |           |   +---+
                   \|/  +---+   |
                    +---+ B +---+
                    |   +---+   |
                  +-+-+         |   +---+   +-+-+
                  | A |         +---+ E +---+ G +
                  +-+-+             +---+   +-+-+
                    |   +---+                 |
                    +---+ C +---+             |
                        +---+   |             |
                                |   +---+     |
                                +---+ F +-----+
                                    +---+

Example 4: Loop

When A gets the packet back through the loop from D, it finds a Processed Tuple for the packet. A sets the RET flag and sends the packet back to D, which sends it on to B. B then picks E as the Next Hop, and E forwards it to G. 🔄

Appendix B. Deployment Experience 🚀

DFF has been deployed and tested out in the real world and in network simulations, as you'll see below.

B.1. Deployments in Japan 🇯🇵

Most of the big Advanced Metering Infrastructure (AMI) deployments using DFF are in Japan. That network data belongs to Japanese utilities, though, so it can't be disclosed.

B.2. Kit Carson Electric Cooperative 💡

DFF has been deployed at Kit Carson Electric Cooperative (KCEC), a non-profit that distributes electricity to about 30,000 customers in New Mexico. According to a press release [KCEC_press_release], DFF currently runs on about 2000 electric meters. All the meters connect through a mesh network over an unreliable, wireless medium. DFF works together with a distance-vector routing protocol. Each meter sends its metering data toward a gateway periodically (every 15 minutes). The data delivery reliability is over 99%. 🥳

B.3. Simulations 🧪

DFF has been evaluated in Ns2 (http://nsnam.isi.edu/nsnam) and OMNEST (http://www.omnest.com) simulations, together with a distance-vector routing protocol. DFF's performance was compared against using only the routing protocol without DFF. The results in peer-reviewed academic papers [DFF_paper1] [DFF_paper2] show significant improvements in the packet delivery ratio compared to using only the distance-vector protocol. 📈

B.4. Open-Source Implementation 💻

Fujitsu Laboratories of America is working on an open-source implementation of DFF, which will be released in 2013 and will allow interoperability testing between different DFF implementations. It's written in Java and can run on real machines as well as in the Ns2 simulator. 🫶

Authors' Addresses 💌

Ulrich Herberg (editor)
Fujitsu
1240 E. Arques Avenue, M/S 345
Sunnyvale, CA  94085
USA
Phone: +1 408 530 4528
EMail: ulrich.herberg@us.fujitsu.com
Alvaro A. Cardenas
University of Texas at Dallas
School of Computer Science, 800 West Campbell Rd, EC 31
Richardson, TX  75080-3021
USA
EMail: alvaro.cardenas@me.com
Tadashige Iwao
Fujitsu
Shiodome City Center, 5-2, Higashi-shimbashi 1-chome, Minato-ku
Tokyo,
JP
Phone: +81-44-754-3343
EMail: smartnetpro-iwao_std@ml.css.fujitsu.com
Michael L. Dow
Freescale
6501 William Cannon Drive West
Austin, TX  78735
USA
Phone: +1 512 895 4944
EMail: m.dow@freescale.com
Sandra L. Cespedes
Icesi University
Calle 18 #122-135, Pance
Cali,
Colombia
Phone: +57 (2) 5552334
EMail: scespedes@icesi.edu.co

That's the whole RFC, bestie! 🌈👑

📦 where this page comes from