| Internet Engineering Task Force | U.H. Herberg |
| Internet-Draft | A.C. Cardenas |
| Intended status: Experimental Protocol | Fujitsu Laboratories |
| Expires: May 04, 2012 | S.C. Cespedes |
| U. Icesi/U. of Waterloo | |
| T.I. Iwao | |
| Fujitsu Limited | |
| November 01, 2011 |
Depth-First Forwarding in Unreliable Networks
draft-cardenas-dff-02
This document describes the Depth-First Forwarding (DFF) protocol for IPv6 networks based on the IEEE 802.15.4 link layer (6lowpan). The protocol is a mesh-under data forwarding mechanism that increases reliability of data delivery in cases where the next hop along the path to the destination, as determined by the underlying routing protocol, is not reachable. In that case, a node running DFF tries to forward the packet successively to all neighbors, and - if the packet makes no forward progress - returns it to the previous hop, similar to a "depth-first search" in graph theory.
This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress."
This Internet-Draft will expire on May 04, 2012.
Copyright (c) 2011 IETF Trust and the persons identified as the document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License.
This document describes the Depth-First Forwarding (DFF) protocol for IPv6 networks based on the IEEE 802.15.4 link layer, as specified in [RFC4944]. The protocol is a mesh-under data forwarding mechanism that increases reliability of data delivery in cases where the next hop along the path to the destination, as determined by the underlying routing protocol, is not reachable. In that case, a node running DFF tries to forward the packet successively to all neighbors, and - if the packet makes no forward progress - returns it to the previous hop, similar to a "depth-first search" in graph theory.
As network topologies do not necessarily form a tree, loops can occur. Therefore, DFF contains a loop detection and avoidance mechanism.
While rerouting the packet through alternative next hops, the routing table can be updated, and thus, DFF provides an optional local route repair mechanism.
Any underlying mesh-under routing mechanism can be used with DFF, as long as such routing mechanism provides lists of bidirectional neighbors for each node. This specification assumes there is such a protocol in place and outlines the requirements for that protocol, as well as the interaction between the specified forwarding mechanism and the routing protocol.
In networks with very dynamic topologies, even frequent exchanges of control messages between nodes for updating the routing tables cannot guarantee freshness of routes: packets may not be delivered to their destination because the topology has changed since the last routing protocol update.
While more frequent routing protocol updates could mitigate that problem to a certain extent, more frequent routing protocol updates require network bandwidth (e.g. when flooding control messages through the network for route discovery). This is an issue in networks with very lossy links, where further control traffic exchange can worsen the network stability. Moreover, additional control traffic exchange (e.g. network-wide floods) drains energy from battery-driven nodes.
The data-forwarding mechanism specified in this document allows forwarding data packets along alternate paths for increasing reliability of data delivery, using a depth-first search. The objective is to decrease the necessary control traffic overhead of the underlying routing protocol, and in the same time to increase delivery success rates. Optionally, the underlying routing protocol can be informed about the updated topology, and routes can then be repaired.
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].
Additionally, this document uses the notation in Section 2.1 and the terminology in Section 2.2.
The following notations are used in this document:
All terms introduced in [RFC4944] are to be interpreted as described therein.
Additionally, this document uses the following terminology:
This protocol:
DFF is a mesh-under data forwarding mechanism responsible for detecting loops, choosing alternate next hops, and optionally updating the cost metrics in the routing tables to reflect information gathered by forwarding data packets. DFF operates on 6lowpan based networks (using the frame format and the transmission of IPv6 packets defined in [RFC4944]).
DFF is intended to work in a network where nodes maintain a bidirectional neighbor table as candidates for a possible next hop of a packet, and a routing table with one or more candidate next hops for each final destination.
DFF provides advantages in networks where the reliability of links is low and the link quality may change rapidly. It assumes that the control plane mechanism cannot guarantee up-to-date routing tables, nor necessarily the absence of loops. Therefore, whenever a data packet is forwarded, DFF stores a data packet identifier to detect loops, and uses alternate paths to reroute the packet to the destination, optionally updating routing tables if a loop is detected.
DFF achieves this functionality by implementing a distributed depth-first search over the network graph. If the routing tables are up-to-date, the search only involves the default route (i.e. uses the shortest path as calculated by the underlying routing protocol). However, if the routing table is not up-to-date and forwarding of a data packet results in a loop, or if the link layer fails to successfully transmit the packet to the next hop, the data packet is sent to an alternate next hop neighbor. This alternate next hop is selected from the neighbor set of the underlying mesh-under routing protocol, using a descending order of priority which takes into account link metrics. DFF lists for each recently forwarded packet which neighbors that packet has been sent to, allowing for trying to forward the packet to all candidates for the next hop.
If none of the transmissions to the neighbors has succeeded, the packet is returned to the previous hop, indicated by setting a return (RET) flag, which is defined in a 6lowpan dispatch byte. The previous hop then continues to try other neighbors in turn, resulting in a depth-first search in the network.
Whenever a packet has been sent to a neighbor and no link layer acknowledgment (ACK) has been received, the duplicate (DUP) flag is set in the packet header for the following transmissions. The rationale is that the packet may have been successfully received by the neighbor and only the ACK has been lost, resulting in duplicates of the packet in the network. The DUP flag tags such a possible duplicate.
Whenever a node receives a packet that it has already forwarded, and which is not a duplicate (as indicated by the DUP flag), it will assume a loop and return the packet to the previous hop (with the RET flag set). Optionally, the link to the next hop to which the node has originally sent the packet may be "poisoned" (i.e. the link cost will be increased).
DFF requires an underlying mechanism that minimally provides a list of bidirectional neighbors of a node. However, in order to avoid sending a packet to any random neighbor as next hop, and therefore possibly performing a network-wide depth-first search, it is recommended to implement DFF in combination with a routing protocol that provides multiple paths to a destination, in order to efficiently choose alternative next hops.
This section specifies optional and mandatory data structures of DFF. DFF itself is no routing protocol, but a data forwarding protocol. However, DFF relies on some information from the underlying routing protocol, in order to perform the depth-first search.
DFF MUST have read access to a list of bidirectional neighbors, henceforth called "Neighbor Set", provided by the underlying routing protocol. The Neighbor Set MUST at least provide the addresses of the direct neighbors of the node, and MAY provide additional information representing the cost of sending a packet to each neighbor (e.g. using a link metric). If DFF has write access to the Neighbor Set, updating link costs ("poisoning") is supported.
DFF MAY have read access to a list of destinations in the network with one or more possible next hops for reaching each destination, henceforth called "Routing Set", provided by the underlying routing protocol. If the routing protocol provides a Routing Set, it MUST at least provide the addresses of destinations and one or more possible next hops to reach that destination, and MAY provide additional information representing the cost of sending a packet to the destination (e.g. using a route metric). If DFF has write access to the Routing Set, updating route costs ("poisoning") is supported.
Each node MUST maintain a Processed Set in order to support the loop detection functionality. The Processed Set lists sequence numbers of previously received packets, as well as a list of next hops to which the packet has been sent successively as part of the depth-first search mechanism. The set consists of Processed Tuples:
where
This document assumes that the data forwarding as well as the underlying routing protocol are based on the LoWPAN adaptation layer ("mesh-under"), and that data packets are conform with the packet format specified in [RFC4944]. In particular, [RFC4944] states that [RFC4944], and MAY be preceded by a header that identifies the DFF data forwarding mechanism, which is defined in the following.
Hence, all data packets to be forwarded using DFF MUST be preceded by the standard mesh (L2) addressing header defined in
After these two headers, any other LoWPAN header, e.g. hop-by-hop options, header compression or fragmentation, MAY also be added before the actual payload. (Figure 1) depicts the mesh header of a data frame to be forwarded with DFF.
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Mesh type and header |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0 1| Mesh Forw |D|R|x| DID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Field definitions are as follows:
The parameters and constants used in this specification are described in this section.
The following sections describe the process of handling a new packet, generated on a node (Section 8.1), as well as forwarding a packet from another node (Section 8.2).
Before a new packet (the "current packet") is transmitted on a node, the following steps MUST be performed:
If a packet (the "current packet") is received on the node, then the following tasks MUST be performed:
then:
If a packet (the "current packet") has been sent to the next hop, as specified in Section 8.1 and Section 8.2, and no link layer acknowledgment has been received after several retries (as specified in [ieee802.15.4]), then:
and modify the current tuple:
Before a packet (the "current packet") is sent from a node towards the packet destination, a valid next hop along the path has to be selected. This section describes how to select the next hop (denoted "next_hop"). As a Processed Tuple was either existing when receiving the packet, or otherwise was created, it can be assumed the a Processed Tuple for that packet (the "current tuple") is available.
The next hop is chosen from the Neighbor Set in order of decreasing preference of the following conditions. This list is only a suggestion, any other order of priority MAY be used.
When a packet is returned (i.e. a packet with RET=1 is received by a node) or a link layer acknowledgment (ACK) has not been received for a forwarded packet, the cost for the route MAY be increased, so that future transmissions prefer other routes. For the case of a missing link layer ACK, in addition to increasing the route cost, the link cost to the neighbor may also be increased.
It is up to the implementation to decide by how much the route and link cost should be increased and out of scope of this document.
This section lists the parameters and constants used in the specification of the protocol, and proposed values of each that MAY be used when a single value of each is used.
The security of the underlying mesh routing protocol depends on the integrity, authentication, and confidentiality of the control messages. The security mechanisms for protecting the network can be provided by link-layer technologies. Further details are presented in the Security Considerations section of [RFC4944].
IANA is requested to allocate a value from the Dispatch Type Field registry for LOWPAN_DFF.
Yuichi Igarashi (Hitachi), Kazuya Monden (Hitachi), Geoff Mulligan (IPSO), Hiroki Satoh (Hitachi), and Ganesh Venkatesh (UC San Diego) provided useful discussions which helped to improve this document.
| [RFC2119] | Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, March 1997. |
| [RFC4944] | Montenegro, G., Kushalnagar, N., Hui, J. and D. Culler, "Transmission of IPv6 Packets over IEEE 802.15.4 Networks", RFC 4944, September 2007. |
| [ieee802.15.4] | Computer Society, IEEE, "IEEE Std. 802.15.4-2003", October 2003. |
In this section, some example network topologies are depicted, using the DFF mechanism for data forwarding. In these examples, it is assumed that the underlying routing protocol provides a list of neighbors of each node, and a routing table with one or more next hops to a destination, if the topology provides a path from the node to the destination.
+---+
+---+ D +-----+
| +---+ |
+---+ | |
+---+ B +---+ |
| +---+ | |
+-+-+ | +---+ +-+-+
| A | +---+ E +---+ G +
+-+-+ +---+ +-+-+
| +---+ |
+---+ C +---+ |
+---+ | |
| +---+ |
+---+ F +-----+
+---+
Figure 2 depicts a network topology with seven nodes A to G, with links between them as indicated by lines. It is assumed that node A sends a packet to G, through B and D, according to the underlying routing protocol. Section 10, i.e. it will first select the next hop for node G as determined by the underlying routing protocol.
+---+
XXX-+ D +-----+
X +---+ |
+---+ X |
+---+ B +---+ |
| +---+ X |
+-+-+ X +---+ +-+-+
| A | XXXX+ E +---+ G +
+-+-+ +---+ +-+-+
| +---+ |
+---+ C +---+ |
+---+ | |
| +---+ |
+---+ F +-----+
+---+
Figure 3 depicts the same topology as the Example 1, but both links between B and D and between B and E are unavailable (e.g. because of wireless link characteristics). Section 9, by setting the DUP flag to 1, selecting E as new next hop, adding E to the list of next hops in the Processed Tuple, and then forwarding the packet to E.
As the link to E also fails, B will again follow the procedure in Section 9. As all possible next hops (D and E) are listed in the Processed Tuple, B will set the RET flag in the packet and return it to A.
A determines that it already has a Processed Tuple for the returned packet, reset the RET flag of the packet and select a new next hop for the packet. As B is already in the list of next hops in the Processed Tuple, it will select C as next hop and forward the packet to it. C will then forward the packet to F, and F delivers the packet to its destination G.
+---+
+---+ D +-----+
| +---+ |
+---+ | |
+---+ B +---+ |
| +---+ | |
+-+-+ | +---+ +-+-+
| A | +---+ E +---+ G +
+-+-+ +---+ +-+-+
. +---+ |
+...+ C +---+ |
+---+ | |
| +---+ |
+---+ F +-----+
+---+
Figure 4 depicts the same topology as the Example 1, but the link layer acknowledgments from C to A are lost (e.g. because the link is uni-directional). It is assumed that A prefers a path to G through C and F.
+-----------------+
| |
| +-+-+
| +---+ D +
| | +---+
\|/ +---+ |
+---+ B +---+
| +---+ |
+-+-+ | +---+ +-+-+
| A | +---+ E +---+ G +
+-+-+ +---+ +-+-+
| +---+ |
+---+ C +---+ |
+---+ | |
| +---+ |
+---+ F +-----+
+---+
Figure 5 depicts the same topology as the Example 1, but there is a loop from D to A, and A sends the packet through B and D.