[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                       Fujitsu Laboratories
Expires: May 3, 2012                                         S. Cespedes
                                                 U. Icesi/U. of Waterloo
                                                                 T. Iwao
                                                         Fujitsu Limited
                                                        October 31, 2011


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

Abstract

   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.

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 3, 2012.

Copyright Notice

   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



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

Internet-Draft                     DFF                      October 2011


   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 . . . . . . . . . . . . . . . . . . . . . . . . .  3
     1.1.  Motivation . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Notation and Terminology . . . . . . . . . . . . . . . . . . .  4
     2.1.  Notation . . . . . . . . . . . . . . . . . . . . . . . . .  4
     2.2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . .  4
   3.  Applicability Statement  . . . . . . . . . . . . . . . . . . .  5
   4.  Protocol Overview and Functioning  . . . . . . . . . . . . . .  5
   5.  Data Structures  . . . . . . . . . . . . . . . . . . . . . . .  7
     5.1.  Neighbor Set . . . . . . . . . . . . . . . . . . . . . . .  7
     5.2.  Routing Set  . . . . . . . . . . . . . . . . . . . . . . .  7
     5.3.  Processed Set  . . . . . . . . . . . . . . . . . . . . . .  7
   6.  Packet Format  . . . . . . . . . . . . . . . . . . . . . . . .  8
   7.  Protocol Parameters and Constants  . . . . . . . . . . . . . .  9
   8.  Data Packet Generation and Processing  . . . . . . . . . . . .  9
     8.1.  Data Packet Generation . . . . . . . . . . . . . . . . . . 10
     8.2.  Data Packet Processing . . . . . . . . . . . . . . . . . . 10
   9.  Missed Link Layer Acknowledgment when Sending a Packet . . . . 12
   10. Getting the Next Hop for a Packet  . . . . . . . . . . . . . . 13
   11. Poisoning  . . . . . . . . . . . . . . . . . . . . . . . . . . 13
   12. Proposed Values for Parameters and Constants . . . . . . . . . 14
   13. Security Considerations  . . . . . . . . . . . . . . . . . . . 14
   14. IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 14
   15. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 14
   16. Normative References . . . . . . . . . . . . . . . . . . . . . 14
   Appendix A.  Examples  . . . . . . . . . . . . . . . . . . . . . . 14
     A.1.  Example 1: Normal Delivery . . . . . . . . . . . . . . . . 15
     A.2.  Example 2: Forwarding with Link Failure  . . . . . . . . . 15
     A.3.  Example 3: Forwarding with Missed Link Layer
           Acknowledgment . . . . . . . . . . . . . . . . . . . . . . 16
     A.4.  Example 4: Forwarding with a Loop  . . . . . . . . . . . . 17
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 18








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

Internet-Draft                     DFF                      October 2011


1.  Introduction

   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.

1.1.  Motivation

   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



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

Internet-Draft                     DFF                      October 2011


   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.


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.

   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.

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

   Originator Address  - An address of a node that is included as source
      address in the packet header.








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

Internet-Draft                     DFF                      October 2011


3.  Applicability Statement

   This protocol:

   o  Is applicable for use in IEEE 802.15.4 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 underlying mesh-under routing protocol.  This routing
      protocol MUST provide a list of bidirectional neighbors of a node,
      and MAY provide one more multiple paths to destinations in the
      network (i.e. store one or more next hop nodes for a destination
      with an associated routing cost).

   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.

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



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

Internet-Draft                     DFF                      October 2011


   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



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

Internet-Draft                     DFF                      October 2011


   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.


5.  Data Structures

   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.

5.1.  Neighbor Set

   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.

5.2.  Routing Set

   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.

5.3.  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 3, 2012                  [Page 7]

Internet-Draft                     DFF                      October 2011


      P_orig_address is is the originator address of the received
      message;

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

      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 standard mesh (L2) addressing header defined in [RFC4944], and
   MAY 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 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             |
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                 Figure 1: Mesh Header for DFF data frames

   Field definitions are as follows:




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

Internet-Draft                     DFF                      October 2011


   Mesh type and header  - The mesh (L2) addressing header and its
      associated dispatch byte as defined in [RFC4944].

   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.

   DID  - This is the data packet identifier.  It is a sequence number
      generated by the originator, unique on a node for each new
      generated packet.  The originator address concatenated with the
      DID sequence number represent an identifier of previously seen
      data packets.


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.


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



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

Internet-Draft                     DFF                      October 2011


   from another node (Section 8.2).

8.1.  Data Packet Generation

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

   1.  Add the mesh header to the current packet, as specified in
       Section 6, with:

       *  Duplicate packet flag (D) := 0;

       *  Return packet flag (R) := 0;

       *  DID := a new sequence number of the packet.

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

   3.  Add a Processed Tuple to the Processed Set with:

       *  P_orig_address := the originator address of this node;

       *  P_seq_number := the sequence number of the current packet, as
          added in the header in Step 1;

       *  P_prev_hop := the originator address of this node;

       *  P_next_hop_neighbor_list := [next_hop];

       *  P_time := current time + P_HOLD_TIME.

   4.  Forward the current packet to next_hop.

8.2.  Data Packet Processing

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

   1.  If the packet does not contain the DFF header, specified in
       Section 6, select the next hop (denoted "next_hop") for the
       current packet, as specified in Section 10, and then forward it
       to next_hop.  This allows for interoperability of nodes sending
       packets without DFF, by forwarding them without the specified
       depth-first forwarding mechanism.

   2.  Otherwise, if no Processed Tuple (the "current tuple") exists in
       the Processed Set, with:



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

Internet-Draft                     DFF                      October 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 (the "current tuple") with:

           +  P_orig_address := the originator address of the current
              packet;

           +  P_seq_number := the sequence number (DID) of the current
              packet;

           +  P_prev_hop := address of the previous hop of the current
              packet;

           +  P_next_hop_neighbor_list := [next_hop];

           +  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, and then forward the
           current packet to next_hop.  If the transmission fails
           (determined by missing link layer acknowledgments), the
           procedures in Section 9 SHOULD be executed.

   3.  Otherwise, if a tuple exists:

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

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

           1.  Set RET:=0

           2.  Increase the route cost in the routing table entry for
               the packet destination with the next hop of the current
               packet, as defined in Section 11.

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



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

Internet-Draft                     DFF                      October 2011


           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),
               otherwise reset it (RET := 0).

           6.  Forward the current packet to next_hop.  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.

   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.






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

Internet-Draft                     DFF                      October 2011


   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.  Forward the current packet to next_hop.


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

   1.  The neighbor is listed in the Routing Set as next hop for the
       destination of the current packet, with lower route costs having
       a higher priority, and the neighbor is not listed in
       P_next_hop_neighbor_list of the current tuple.

   2.  The neighbor is not listed in the Routing Set as any next hop
       destination of the current packet, and the neighbor is not listed
       in P_next_hop_neighbor_list of the current tuple.

   3.  The neighbor is the same as P_prev_hop of the current tuple; 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, 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.






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

Internet-Draft                     DFF                      October 2011


12.  Proposed Values for Parameters and Constants

   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.

   o  P_HOLD_TIME := 5 seconds


13.  Security Considerations

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


14.  IANA Considerations

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


15.  Acknowledgements

   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.


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


Appendix A.  Examples

   In this section, some example network topologies are depicted, using



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

Internet-Draft                     DFF                      October 2011


   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.

A.1.  Example 1: Normal Delivery

   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.

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

                   Figure 2: 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 underlying routing protocol.

A.2.  Example 2: Forwarding with Link Failure

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









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

Internet-Draft                     DFF                      October 2011


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

                     Figure 3: 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 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.







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

Internet-Draft                     DFF                      October 2011


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

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

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

                         Figure 5: Example 4: loop



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

Internet-Draft                     DFF                      October 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 Laboratories
   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 Laboratories
   1240 E. Arques Avenue, M/S 345
   Sunnyvale, CA  94085
   US

   Phone: +1 408 530-4516
   Email: alvaro.cardenas-mora@us.fujitsu.com


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

   Phone: +1 (519) 8884567 x37448
   Email: slcesped@bbcr.uwaterloo.ca


   Tadashige Iwao
   Fujitsu Limited
   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





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


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