| Internet Engineering Task Force | U.H. Herberg |
| Internet-Draft | A.C. Cardenas |
| Intended status: Experimental Protocol | T.I. Iwao |
| Expires: May 17, 2012 | Fujitsu |
| M.L. Dow | |
| Freescale | |
| S.C. Cespedes | |
| U. Icesi/U. of Waterloo | |
| November 14, 2011 |
Depth-First Forwarding in Unreliable Networks
draft-cardenas-dff-03
This document describes the Depth-First Forwarding (DFF) protocol for IPv6 networks based on the LoWPAN adaptation layer. The protocol is a mesh-under data forwarding mechanism that increases reliability of data delivery.
DFF forwards data packets using a network-wide "depth-first search" for the Final Destination of the packet. DFF may be used in conjunction with a mesh-under routing protocol, which provides "hints" for DFF in which order to try to send the packet to the neighbors discovered by the neighborhood discovery mechanism. In that case, DFF can be used as local repair mechanism.
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 17, 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 LoWPAN adaptation layer, as specified in [RFC4944]. The protocol is a mesh-under data forwarding mechanism that increases reliability of data delivery in networks with dynamic topologies.
DFF forwards data packets using a network-wide "depth-first search" for the final destination of the packet. DFF relies on a neighborhood discovery mechanism which lists neighbors of a node for the next hop of a data packet. In addition, DFF may be used in conjunction with a mesh-under routing protocol, which provides "hints" for DFF in which order to try to send the packet to the neighbors discovered by the neighborhood discovery mechanism.
If the packet makes no forward progress using the selected next hop, DFF will successively try all neighbors of the node (as determined by an additional mechanism, e.g. a mesh-under routing protocol, ND, HELLO message exchange). If none of the next hops successfully receives the packet, DFF returns the packet to the previous hop, which in turn tries to send it to alternate neighbors.
As network topologies do not necessarily form a tree, loops can occur. Therefore, DFF contains a loop detection and avoidance mechanism.
If DFF is used in conjunction with a mesh-under routing protocol, the cost of routes provided by that routing protocol may be updated while rerouting the packet through alternative next hops. Thus, DFF provides an optional local route repair mechanism.
In networks with 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, that requires network bandwidth (e.g. when flooding control messages through the network for route discovery). This is an issue in networks with lossy links, where further control traffic exchange can worsen the network stability because of collisions (e.g. in the case of a network-wide flood of Route Request messages or Link State Advertisements). Moreover, additional control traffic exchange drains energy from battery-driven nodes.
The data-forwarding mechanism specified in this document allows for 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 in the network, and in the same time to increase delivery success rates. If a mesh-under routing protocol is used in conjunction to DFF, that protocol can be informed about the updated topology, and routes can then be repaired.
DFF can be used as stand-alone forwarding mechanism, but may be used in conjunction with a mesh-under routing protocol which allows for providing an order of preference to which next hops a packet should be forwarded (e.g. the packet may be forwarded first to neighbors that are listed as next hops to the final destination, preferring those with the lowest route cost).
DFF requires a list of bidirectional neighbors for each node, which must be provided by an external mechanism, such as specified in [RFC4861]. This specification assumes there is such a neighborhood discovery protocol in place and outlines the requirements for that protocol, as well as the interaction between DFF and a mesh-under routing protocol if such is used in conjunction to DFF.
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, in particular Originator Address, Final Destination Address, Source Address, and Destination Address.
Additionally, this document uses the following terminology:
This protocol:
DFF is a mesh-under data forwarding mechanism responsible for finding a path to a Final Destination of a packet, using a "depth-first search" in the network. DFF operates on LoWPAN based networks (using the frame format and the transmission of IPv6 packets defined in [RFC4944]).
DFF requires an external mechanism to discover the bidirectional neighborhood of a node. The specification of such a mechanism is out of scope of this document. The list of neighbors is required because DFF successively tries to forward a packet to all neighbors of a node during the depth-first search, and eventually returns it to the previous hop if the packet was not successfully received by any of the neighbors.
In addition to the mandatory neighborhood information, DFF may use information from a mesh-under routing protocol that runs in conjunction to DFF. Such protocol can increase the efficiency of the depth-first search, as it allows for providing an order of preference which next hops to try first (e.g. by preferring neighbors that are listed in the mesh-under routing protocol as next hops along the path to the final destination, and by preferring next hops with a lower route cost). If the topology as reflected by that mesh-under routing protocol represents the effective topology of the network, then DFF will forward the data packet along the path provided by the protocol. However, if the topology has changed and the routing protocol has not yet converged, then DFF will try alternate paths. Compared to the typical forwarding mechanism in LoWPAN networks, a mesh-under routing protocol thus only serves DFF to give recommendations (or "hints") where to forward a packet. That also implies that if the mesh-under routing protocol does not provide a route to a final destination, the data packet would not be dropped but forwarded by DFF, trying to find a path to that final destination.
In order to avoid loops when forwarding a data packet towards its Final Destination, DFF stores a data packet identifier (i.e. a sequence number) to detect loops. DFF lists for each recently forwarded packet which neighbors that packet has already been sent to, allowing for trying to forward the packet to all candidates for the next hop.
DFF requires additional header information for each data packet, provided by a LoWPAN dispatch byte specified in this document. This header contains a sequence number used for identifying a packet uniquely, and two flags: RET and DUP. If none of the transmissions of a data packet to the neighbors of a node has succeeded, the packet is returned to the previous hop, indicated by setting the return (RET) flag. 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 (as identified by the sequence number of the packet), and which is not a duplicate (i.e. DUP = 0), it will assume a loop and return the packet to the previous hop (with the RET flag set). Optionally, if a mesh-under routing protocol is used in conjunction to DFF, the route using the next hop which resulted in the loop may be "poisoned" (i.e. the route cost may be increased).
This section specifies the information sets used by DFF. In addition, DFF requires access to a list of bidirectional neighbors of the node, provided by an external neighborhood discovery mechanism, which is not specified within this document.
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 is 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 SHOULD 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 Mesh 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 Addressing header defined in [RFC4944], and Figure 2 depicts 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...
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
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 |D|R|x| Sequence Number |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Field definitions of the Mesh Addressing header are as specified in [RFC4944].
Field definitions of the DFF header 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). When DFF is used, the following specification MUST be used instead of the default frame delivery, specified in Section 11 of [RFC4944].
In the following, it is assumed that all data packets are preceded by the Mesh Addressing header and the DFF header, as specified in Section 6. In order to allow for interoperability with nodes not using DFF as forwarding mechanism, packets that are preceded by the Mesh Addressing header but not the DFF header are treated as specified in Section 11 of [RFC4944].
Before a new packet (denoted the "current packet") is transmitted on a node, the following steps MUST be performed:
If a packet (denoted 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 a list of neighbors in order of decreasing preference of the following conditions. This list is only a suggestion, any other order of priority MAY be used, however, P_prev_hop of the current tuple SHOULD be the last entry. The list SHOULD NOT contain addresses which are listed in P_next_hop_neighbor_list of the current tuple, and an address SHOULD NOT appear more than once in the list.
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, and if a mesh-under routing protocol is used in conjunction to DFF, the cost for the route MAY be increased in that routing protocol. Thus, 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 if such is supported by the neighborhood discovery process.
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.
If DFF is used in conjunction with a mesh-under routing protocol, route repair mechanisms of that mesh-under routing protocol MAY be disabled in order to avoid unnecessary flooding of the network. As DFF finds alternate paths for the data traffic, and in addition may "poison" unused routes of the mesh-under routing protocol, route repair mechanisms may be unnecessary and even reduce the stability of the network (e.g. because of collisions when Route Requests or Link State Advertisements are flooded in the network).
Whenever a node generates a packet, a sequence number is required in the DFF header. This sequence number needs to be unique only locally on each node. For example, a sequence number may start at 0 for the first generated packet, and then increase in steps of 1 for each new packet. The sequence number MUST not be greater than 65535 and SHOULD wrap around to 0.
This section lists the parameters and constants used in the specification of the protocol, and proposed values of each that MAY be used.
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), Ganesh Venkatesh (UC San Diego), and Jiazi Yi (Ecole Polytechnique) 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. |
| [RFC4861] | Narten, T., Nordmark, E., Simpson, W. and H. Soliman, "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861, September 2007. |
In this section, some example network topologies are depicted, using the DFF mechanism for data forwarding. In these examples, it is assumed that DFF is used in conjunction to a mesh-under routing protocol. This 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 3 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 mesh-under routing protocol. Section 10, i.e. it will first select the next hop for node G as determined by the mesh-under routing protocol.
+---+
XXX-+ D +-----+
X +---+ |
+---+ X |
+---+ B +---+ |
| +---+ X |
+-+-+ X +---+ +-+-+
| A | XXXX+ E +---+ G +
+-+-+ +---+ +-+-+
| +---+ |
+---+ C +---+ |
+---+ | |
| +---+ |
+---+ F +-----+
+---+
Figure 4 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 5 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 6 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.