[Docs] [txt|pdf|xml|html] [Tracker] [Email] [Diff1] [Diff2] [Nits] [IPR]

Versions: 00 01 02 03 04 05 06 RFC 6971

Internet Engineering Task Force                               U. Herberg
Internet-Draft                                               A. Cardenas
Intended status: Experimental                                    T. Iwao
Expires: May 17, 2012                                            Fujitsu
                                                                  M. Dow
                                                               Freescale
                                                             S. Cespedes
                                                 U. Icesi/U. of Waterloo
                                                       November 14, 2011


             Depth-First Forwarding in Unreliable Networks
                         draft-cardenas-dff-03

Abstract

   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.

Status of this Memo

   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 Notice

   Copyright (c) 2011 IETF Trust and the persons identified as the



Herberg, et al.           Expires May 17, 2012                  [Page 1]

Internet-Draft                     DFF                     November 2011


   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.


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  4
     1.1.  Motivation . . . . . . . . . . . . . . . . . . . . . . . .  4
     1.2.  Protocol Dependencies  . . . . . . . . . . . . . . . . . .  5
   2.  Notation and Terminology . . . . . . . . . . . . . . . . . . .  5
     2.1.  Notation . . . . . . . . . . . . . . . . . . . . . . . . .  5
     2.2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . .  6
   3.  Applicability Statement  . . . . . . . . . . . . . . . . . . .  6
   4.  Protocol Overview and Functioning  . . . . . . . . . . . . . .  7
   5.  Information Sets . . . . . . . . . . . . . . . . . . . . . . .  8
     5.1.  Processed Set  . . . . . . . . . . . . . . . . . . . . . .  8
   6.  Packet Format  . . . . . . . . . . . . . . . . . . . . . . . .  9
   7.  Protocol Parameters and Constants  . . . . . . . . . . . . . . 11
   8.  Data Packet Generation and Processing  . . . . . . . . . . . . 11
     8.1.  Data Packet Generation . . . . . . . . . . . . . . . . . . 11
     8.2.  Data Packet Processing . . . . . . . . . . . . . . . . . . 12
   9.  Missed Link Layer Acknowledgment when Sending a Packet . . . . 14
   10. Getting the Next Hop for a Packet  . . . . . . . . . . . . . . 15
   11. Poisoning  . . . . . . . . . . . . . . . . . . . . . . . . . . 16
   12. Route Repair Mechanism . . . . . . . . . . . . . . . . . . . . 16
   13. Sequence Numbers . . . . . . . . . . . . . . . . . . . . . . . 16
   14. Proposed Values for Parameters and Constants . . . . . . . . . 16
   15. Security Considerations  . . . . . . . . . . . . . . . . . . . 17
   16. IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 17
   17. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 17
   18. References . . . . . . . . . . . . . . . . . . . . . . . . . . 17
     18.1. Normative References . . . . . . . . . . . . . . . . . . . 17
     18.2. Informative References . . . . . . . . . . . . . . . . . . 17
   Appendix A.  Examples  . . . . . . . . . . . . . . . . . . . . . . 18
     A.1.  Example 1: Normal Delivery . . . . . . . . . . . . . . . . 18
     A.2.  Example 2: Forwarding with Link Failure  . . . . . . . . . 18
     A.3.  Example 3: Forwarding with Missed Link Layer
           Acknowledgment . . . . . . . . . . . . . . . . . . . . . . 19
     A.4.  Example 4: Forwarding with a Loop  . . . . . . . . . . . . 20



Herberg, et al.           Expires May 17, 2012                  [Page 2]

Internet-Draft                     DFF                     November 2011


   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 21


















































Herberg, et al.           Expires May 17, 2012                  [Page 3]

Internet-Draft                     DFF                     November 2011


1.  Introduction

   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.

1.1.  Motivation

   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



Herberg, et al.           Expires May 17, 2012                  [Page 4]

Internet-Draft                     DFF                     November 2011


   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.

1.2.  Protocol Dependencies

   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.


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].

   Additionally, this document uses the notation in Section 2.1 and the
   terminology in Section 2.2.

2.1.  Notation

   The following notations are used in this document:

   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.






Herberg, et al.           Expires May 17, 2012                  [Page 5]

Internet-Draft                     DFF                     November 2011


   Concatenation of lists:  If L1 and L2 are lists, then L1@L2 is a new
      list with all elements of L2 concatenated to L1.

2.2.  Terminology

   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:

   Address  - An address is either a 16-bit short or a EUI-64 link layer
      address, as specified in [RFC4944].

   Packet  - An IPv6 packet encapsulated in a IEEE 802.15.4 frame, using
      the LoWPAN adaption layer as specified in [RFC4944].


3.  Applicability Statement

   This protocol:

   o  Is applicable for use in LoWPAN based networks, using the frame
      format for transmission of IPv6 packets defined in [RFC4944].

   o  Assumes addresses used in the network are either 16-bit short or
      EUI-64 link layer address, as specified in [RFC4944].

   o  Operates as "mesh-under" forwarding protocol, i.e. on the link
      layer.  While the proposed mechanism could also be used as "route-
      over", this is not specified in this document and thus out of
      scope.

   o  Is designed to work in networks with lossy links or with a dynamic
      topology.

   o  Relies on an external neighborhood discovery mechanism, which MUST
      provide a list of bidirectional neighbors of a node.  In addition,
      DFF MAY use information from a mesh-under routing protocol used in
      conjunction to DFF.  Such a protocol provide provides "hints" to
      DFF in which order the neighbors should be successively tried as
      next hop for a packet.

   o  Increases reliability of data delivery by trying alternative
      paths, using a "depth-first forwarding" approach.

   o  Provides a loop detection mechanism, and an optional local route
      repair mechanism if a mesh-under routing protocol is used in



Herberg, et al.           Expires May 17, 2012                  [Page 6]

Internet-Draft                     DFF                     November 2011


      conjunction to DFF.

   o  Is designed to work in a completely distributed manner, and does
      not depend on any central entity.


4.  Protocol Overview and Functioning

   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.




Herberg, et al.           Expires May 17, 2012                  [Page 7]

Internet-Draft                     DFF                     November 2011


   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).


5.  Information Sets

   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.

5.1.  Processed Set

   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:

      (P_orig_address, P_seq_number, P_prev_hop,
      P_next_hop_neighbor_list, P_time)

   where






Herberg, et al.           Expires May 17, 2012                  [Page 8]

Internet-Draft                     DFF                     November 2011


      P_orig_address is is the Originator Address of the received
      packet;

      P_seq_number is the Sequence Number of the received packet;

      P_prev_hop is the Source Address (i.e. the previous hop) of the
      packet;

      P_next_hop_neighbor_list is a list of addresses of next hops to
      which the packet has been sent previously, as part of the depth-
      first search mechanism, as explained in Section 8.2;

      P_time specifies when this Tuple expires and MUST be removed.


6.  Packet Format

   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

      Additional mesh routing capabilities, such as specifying the mesh
      routing protocol, source routing, and so on may be expressed by
      defining additional routing headers that precede the fragmentation
      or addressing header in the header stack.

   Hence, all data packets to be forwarded using DFF MUST be preceded by
   the Mesh Addressing header defined in [RFC4944], and SHOULD be
   preceded by a header that identifies the DFF data forwarding
   mechanism, which is defined in the following.

   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...
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                     Figure 1: Mesh Addressing Header







Herberg, et al.           Expires May 17, 2012                  [Page 9]

Internet-Draft                     DFF                     November 2011


                           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      |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                   Figure 2: Header for DFF data frames

   Field definitions of the Mesh Addressing header are as specified in
   [RFC4944].

   Field definitions of the DFF header are as follows:

   Mesh Forw  - A 6-bit identifier that allows for the use of different
      mesh forwarding mechanisms.  As specified in [RFC4944], additional
      mesh forwarding mechanisms should use the reserved dispatch byte
      values following LOWPAN_BCO; therefore, 0 1 MUST precede Mesh
      Forw.  The value of Mesh Forw is LOWPAN_DFF.

   Duplicate packet flag (D)  - This flag is included in the DFF mesh
      header to indicate that the packet has been re-sent as a
      duplicate.  The flag MUST be set to 1 by the node that re-sends
      the packet after detecting link-layer failure to deliver through
      the last attempted next-hop, as specified in Section 8.2.  Once
      the flag is set to 1, it MUST not be modified by nodes forwarding
      the packet.

   Return packet flag (R)  - This flag is included in the DFF mesh
      header to indicate that the packet has been returned to the
      previous hop after failure to deliver to all the available next-
      hops.  The flag MUST be set to 1 prior to forwarding the packet
      back to the previous hop and MUST be set to 0 prior to forwarding
      the packet to the selected next-hop, as specified in Section 8.2.
      This flag is modified in a hop-by-hop basis.

   Reserved flag (x)  - This bit is reserved for future flag
      definitions.

   Sequence Number  - This is a sequence number generated by the
      originator, unique on a node for each new generated packet, as
      specified in Section 13.  The Originator Address concatenated with
      the Sequence Number represent an identifier of previously seen
      data packets.








Herberg, et al.           Expires May 17, 2012                 [Page 10]

Internet-Draft                     DFF                     November 2011


7.  Protocol Parameters and Constants

   The parameters and constants used in this specification are described
   in this section.

   P_HOLD_TIME  - is the time period after which a newly created
      Processed Tuple expires and MUST be deleted.

   MAX_HOPS_LEFT  - is the initial value of Deep Hops Left in the mesh
      header specified in [RFC4944].


8.  Data Packet Generation and Processing

   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].

8.1.  Data Packet Generation

   Before a new packet (denoted the "current packet") is transmitted on
   a node, the following steps MUST be performed:

   1.  Add the Mesh Addressing header to the current packet, as
       specified in [RFC4944] and described in Section 6, with:

       *  V and F are set according to the used address length;

       *  Hops Left := 0xF (i.e. reserved value indicating that the Deep
          Hops Left field is following);

       *  Deep Hops Left := MAX_HOPS_LEFT;

       *  Originator Address := address of this node;

       *  Final Destination Address := address of the final destination
          node.





Herberg, et al.           Expires May 17, 2012                 [Page 11]

Internet-Draft                     DFF                     November 2011


   2.  Add the DFF header to the current packet, as specified in
       Section 6, with:

       *  Duplicate packet flag (D) := 0;

       *  Return packet flag (R) := 0;

       *  Sequence Number := a new Sequence Number of the packet (as
          defined in Section 13).

   3.  Select the next hop (denoted "next_hop") for the current packet,
       as specified in Section 10.

   4.  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.

   5.  Set the Source Address in the 802.15.4 header to the node's own
       address and the Destination Address to next_hop.

   6.  Transmit the current packet.  If the transmission fails
       (determined by missing link layer acknowledgments), the
       procedures in Section 9 SHOULD be executed.

8.2.  Data Packet Processing

   If a packet (denoted the "current packet") is received on the node,
   then the following tasks MUST be performed:

   1.  If the Final Destination Address from the Mesh Addressing header
       matches the address of this node, consume the packet as per
       normal delivery.

   2.  Otherwise, decrement the value of the Deep Hops Left field in the
       mesh header.  Drop the packet if Deep Hops Left is decremented to
       zero.

   3.  If no Processed Tuple (denoted the "current tuple") exists in the
       Processed Set, with:



Herberg, et al.           Expires May 17, 2012                 [Page 12]

Internet-Draft                     DFF                     November 2011


       +  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 (denoted 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 Source Address (i.e. the previous hop)
              of the current packet;

           +  P_next_hop_neighbor_list := [];

           +  P_time := current time + P_HOLD_TIME.

       2.  Set RET to 0 in the packet DFF header.

       3.  Select the next hop (denoted "next_hop") for the current
           packet, as specified in Section 10.

       4.  P_next_hop_neighbor_list := P_next_hop_neighbor_list@
           [next_hop];

       5.  Set the Source Address in the 802.15.4 header to the node's
           own address and the Destination Address field to next_hop.

       6.  Transmit the current packet.  If the transmission fails
           (determined by missing link layer acknowledgments), the
           procedures in Section 9 SHOULD be executed.

   4.  Otherwise, if a tuple exists:

       1.  If the return flag of the current packet is not set (RET=0)
           (i.e. a loop has been detected):

           1.  Set RET := 1

           2.  Set the Source Address in the 802.15.4 header to the
               node's own address and the Destination Address field to
               the Source Address of the current packet (i.e. the
               previous hop).




Herberg, et al.           Expires May 17, 2012                 [Page 13]

Internet-Draft                     DFF                     November 2011


           3.  Transmit the current packet.

       2.  Otherwise, if the return flag of the current packet is set
           (RET = 1):

           1.  Set RET := 0

           2.  Execute the "poisoning" procedure specified in
               Section 11.

           3.  Select the next hop (denoted "next_hop") for the current
               packet, as specified in Section 10.

           4.  Modify the current tuple:

               -  P_next_hop_neighbor_list := P_next_hop_neighbor_list@
                  [next_hop];

               -  P_time := current time + P_HOLD_TIME.

           5.  If the selected next hop is equal to P_prev_hop of the
               current tuple (i.e. all neighbors have been
               unsuccessfully tried), set the RET flag (RET := 1).  If
               this node has the same address as the Originator Address
               of the current packet, drop the packet.

           6.  Set the Source Address in the 802.15.4 header to the
               node's own address and the Destination Address field to
               next_hop.

           7.  Transmit the current packet.  If the transmission fails
               (determined by missing link layer acknowledgments), the
               procedures in Section 9 SHOULD be executed.


9.  Missed Link Layer Acknowledgment when Sending a Packet

   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:

   1.  Set the duplicate flag (DUP) of the DFF header of the current
       packet to 1.

   2.  Select the next hop (denoted "next_hop") for the current packet,
       as specified in Section 10.




Herberg, et al.           Expires May 17, 2012                 [Page 14]

Internet-Draft                     DFF                     November 2011


   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,

       and modify the current tuple:

       *  P_next_hop_neighbor_list := P_next_hop_neighbor_list@
          [next_hop];

       *  P_time := current time + P_HOLD_TIME.

   4.  If the selected next hop is equal to P_prev_hop of the current
       tuple, set the RET flag (RET := 1), otherwise reset it (RET :=
       0).

   5.  Set the Source Address in the 802.15.4 header to the node's own
       address and the Destination Address field to next_hop.

   6.  Transmit the current packet.  If the transmission fails
       (determined by missing link layer acknowledgments), the
       procedures in Section 9 SHOULD be executed.


10.  Getting the Next Hop for a Packet

   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.

   1.  If a mesh-under routing protocol is used, then a next hop along
       the path to the Final Destination Address of the packet may be
       added, where next hops with lower route costs have a higher
       priority.



Herberg, et al.           Expires May 17, 2012                 [Page 15]

Internet-Draft                     DFF                     November 2011


   2.  All other neighbors from an external neighborhood discovery
       process can be added.

   3.  P_prev_hop of the current tuple SHOULD be added last; this case
       is only used for returning the packet to the previous hop, in
       which case the RET flag MUST be set to 1.


11.  Poisoning

   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.


12.  Route Repair Mechanism

   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).


13.  Sequence Numbers

   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.


14.  Proposed Values for Parameters and Constants

   This section lists the parameters and constants used in the



Herberg, et al.           Expires May 17, 2012                 [Page 16]

Internet-Draft                     DFF                     November 2011


   specification of the protocol, and proposed values of each that MAY
   be used.

   o  P_HOLD_TIME := 5 seconds

   o  MAX_HOPS_LEFT := 255


15.  Security Considerations

   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].


16.  IANA Considerations

   IANA is requested to allocate a value from the Dispatch Type Field
   registry for LOWPAN_DFF.


17.  Acknowledgements

   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.


18.  References

18.1.  Normative References

   [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.

18.2.  Informative References

   [RFC4861]  Narten, T., Nordmark, E., Simpson, W., and H. Soliman,
              "Neighbor Discovery for IP version 6 (IPv6)", RFC 4861,



Herberg, et al.           Expires May 17, 2012                 [Page 17]

Internet-Draft                     DFF                     November 2011


              September 2007.


Appendix A.  Examples

   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.

A.1.  Example 1: Normal Delivery

   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.

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

                   Figure 3: Example 1: normal delivery

   If no link fails in this topology, and no loop occurs, then DFF will
   not modify the usual data forwarding mechanism.  Each node adds a
   Processed Tuple for the incoming packet, and selects the next hop
   according to Section 10, i.e. it will first select the next hop for
   node G as determined by the mesh-under routing protocol.

A.2.  Example 2: Forwarding with Link Failure

   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).



Herberg, et al.           Expires May 17, 2012                 [Page 18]

Internet-Draft                     DFF                     November 2011


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

                     Figure 4: Example 2: link failure

   When B receives the packet from node a, it adds a Processed Tuple,
   and then tries to forward the packet to D. Once B detects that the
   packet cannot be successfully delivered to D because it does not
   receive link layer ACKs, it will follow the procedures listed in
   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.

A.3.  Example 3: Forwarding with Missed Link Layer Acknowledgment

   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.







Herberg, et al.           Expires May 17, 2012                 [Page 19]

Internet-Draft                     DFF                     November 2011


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

           Figure 5: Example 3: missed link layer acknowledgment

   While C successfully receives the packet from A, A does not receive
   the ACK and assumes the packet has not been delivered to C.
   Therefore, it sets the DUP flag of the packet to 1, in order to
   indicate that this packet is a duplicate.  Then, it forwards the
   packet to B.

A.4.  Example 4: Forwarding with a Loop

   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.

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

                         Figure 6: Example 4: loop



Herberg, et al.           Expires May 17, 2012                 [Page 20]

Internet-Draft                     DFF                     November 2011


   When A receives the packet through the loop from D, it will find a
   Processed Tuple for the packet.  Node A will set the RET flag and
   return the packet to D, which in turn will return it to B. B will
   then select E as next hop, which will then forward it to G.


Authors' Addresses

   Ulrich Herberg
   Fujitsu
   1240 E. Arques Avenue, M/S 345
   Sunnyvale, CA  94085
   US

   Phone: +1 408 530-4528
   Email: ulrich.herberg@us.fujitsu.com


   Alvaro A. Cardenas
   Fujitsu
   1240 E. Arques Avenue, M/S 345
   Sunnyvale, CA  94085
   US

   Phone: +1 408 530-4516
   Email: alvaro.cardenas-mora@us.fujitsu.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





Herberg, et al.           Expires May 17, 2012                 [Page 21]

Internet-Draft                     DFF                     November 2011


   Sandra L. Cespedes
   U. Icesi/U. of Waterloo
   Calle 18 No. 122-135 Pance
   Cali, Valle
   Colombia

   Phone:
   Email: slcesped@bbcr.uwaterloo.ca











































Herberg, et al.           Expires May 17, 2012                 [Page 22]


Html markup produced by rfcmarkup 1.109, available from https://tools.ietf.org/tools/rfcmarkup/