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

Versions: 00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 RFC 6971

Internet Engineering Task Force                              A. Cardenas
Internet-Draft                                      Fujitsu Laboratories
Intended status: Informational                               S. Cespedes
Expires: January 12, 2012                        U. Icesi/U. of Waterloo
                                                                 T. Iwao
                                                         Fujitsu Limited
                                                           July 11, 2011


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

Abstract

   Routing protocols are generally composed of two independent phases,
   the control plane and the data forwarding plane.  The control plane
   is responsible for route discovery and maintenance.  The data
   forwarding plane performs a table lookup operation to set the packet
   on the right path.  In unreliable networks, the routing process
   incurs a large control overhead when is constantly repairing routes,
   detecting loops, and finding alternate paths due to frequent link
   failures.

   This document describes the Depth-First Forwarding (DFF) protocol; a
   data forwarding mechanism that can be used to minimize the burden and
   control overhead of a control plane used in unreliable networks.  DFF
   offers reliability and low control overhead by supporting in the data
   plane loop detection, updates to the routing tables, and rerouting of
   data packets through alternate paths.  DFF can be integrated with
   different types of control plane mechanisms and can be used in mesh-
   under and route-over specifications.  In this draft, we describe a
   sample DFF implementation as a 6LoWPAN mesh-under data forwarding
   protocol.

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



Cardenas, et al.        Expires January 12, 2012                [Page 1]

Internet-Draft                     DFF                         July 2011


   This Internet-Draft will expire on January 12, 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
   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.



































Cardenas, et al.        Expires January 12, 2012                [Page 2]

Internet-Draft                     DFF                         July 2011


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  4
     1.1.  Requirements notation  . . . . . . . . . . . . . . . . . .  4
     1.2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . .  4
   2.  Protocol Overview  . . . . . . . . . . . . . . . . . . . . . .  5
   3.  Depth-First Forwarding Operation . . . . . . . . . . . . . . .  5
   4.  Coexistence with other packet formats  . . . . . . . . . . . .  7
   5.  Message Formats  . . . . . . . . . . . . . . . . . . . . . . .  8
   6.  Data Structures  . . . . . . . . . . . . . . . . . . . . . . .  9
   7.  Hop-by-Hop Implementation Options  . . . . . . . . . . . . . . 10
   8.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . 11
   9.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 11
   10. Security Considerations  . . . . . . . . . . . . . . . . . . . 11
   11. Appendix A: Example Implementation of a Control Plane for
       DFF  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
     11.1. Data structures  . . . . . . . . . . . . . . . . . . . . . 12
     11.2. Route Discovery  . . . . . . . . . . . . . . . . . . . . . 13
   12. Appendix B: Implementing DFF without requesting new
       dispatch bytes . . . . . . . . . . . . . . . . . . . . . . . . 14
   13. Normative References . . . . . . . . . . . . . . . . . . . . . 15
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 15





























Cardenas, et al.        Expires January 12, 2012                [Page 3]

Internet-Draft                     DFF                         July 2011


1.  Introduction

   Networks with dynamic links present a challenge for typical routing
   protocols because the reliability of links may be different at the
   time when the route was discovered from the time when the data is
   forwarded.

   In these unreliable networks, the control overhead for detecting
   routing errors and for fixing paths happens often, so it is important
   to avoid expensive control plane mechanisms that might overreact in
   the presence of instability.  Because a lightweight control plane
   mechanism cannot guarantee the construction and maintenance of error-
   free routes, a data forwarding protocol designed for these conditions
   should be able to detect errors and find backup paths to survive link
   failures.

   This document describes Depth-First Forwarding (DFF), a data
   forwarding mechanism that can detect loops, update the routing
   tables, and reroute data packets via alternate paths.  DFF is
   compatible with light-weight control plane mechanisms supporting
   routing tables that maintain more than one possible next hop for each
   final destination.

1.1.  Requirements notation

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

1.2.  Terminology

   Readers are expected to be familiar with all the terms and concepts
   that are discussed in "Transmission of IPv6 Packets over IEEE
   802.15.4 Networks" [RFC4944].

   Other terms used:

   Final Destination: This is the final destination of the data packet
   within the mesh network.

   Local destination: The local destination of the data packet refers to
   the next-hop neighbor to which the packet is forwarded on its way to
   the final destination.

   Originator: This is the source node that created the 6lowpan data
   packet.





Cardenas, et al.        Expires January 12, 2012                [Page 4]

Internet-Draft                     DFF                         July 2011


2.  Protocol Overview

   DFF is a data forwarding mechanism responsible for detecting loops,
   choosing alternate next hops, and updating the cost metrics in the
   routing tables to reflect information gathered by forwarding data
   packets.

   DFF is intended to work in a network where nodes maintain proactively
   a routing table with multiple candidate next hops for each final
   destination.  An example of a control plane satisfying these
   conditions is described in the Appendix.

   DFF provides an advantage in networks where the reliability of links
   changes rapidly.  It assumes that the control plane mechanism cannot
   guarantee up to date routing tables, nor the absence of loops.
   Therefore, whenever a data packet is forwarded, DFF can keep a data
   packet identifier to detect loops, update routing tables if a loop is
   detected, and use alternate paths to reroute the packet around the
   failed path.

   DFF achieves this functionality by implementing a distributed depth-
   first search over the network graph as defined by the routing table.
   If the routing tables are up to date, the search only involves the
   default route.  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 then sent to an alternate next hop neighbor.  A distributed
   depth-first search mechanism is implemented in order to keep track of
   the nodes that have participated in the forwarding of the data
   packet.

   Although DFF can be used without a control plane by performing a
   blind (i.e., without a routing table) depth-first search of the
   network, this configuration will incur in increased latency because
   data packets are forwarded by intermediate nodes to a random next-hop
   neighbor.  Therefore, it is recommended to implement DFF in
   combination with a proactive control plane protocol, in order to
   efficiently guide the depth-first search by using information stored
   in the routing tables.


3.  Depth-First Forwarding Operation

   The operation procedure described in this section relies on the
   existence of a routing table in every node.  This table SHOULD be
   filled by a proactive control plane that stores multiple candidate
   next hops for final destinations.  An example of a proactive distance
   vector control plane that could be integrated to DFF is provided in



Cardenas, et al.        Expires January 12, 2012                [Page 5]

Internet-Draft                     DFF                         July 2011


   the Appendix.

   In order for an originator to send packets based on depth-first
   forwarding, it first encapsulates the data packet using the standard
   mesh header defined in [RFC4944] and the DFF mesh header (Figure 1).
   The DFF mesh header is employed for detecting loops based on the
   unique data identifier (DID) of the packet, and for rerouting packets
   in the forwarding path.  The originator then checks the routing table
   to select the next hop with the lowest cost to reach the destination.
   Before forwarding the packet, an entry is created in the loop
   detection table (Figure 2), where packet's information such as the
   originator's address, DID, previous hop (it points to the node itself
   when the node is the originator of packet), and the selected next hop
   are stored.

   Upon reception of a data packet at an intermediate node (which might
   be the originator if there is a loop in the path), the node checks if
   an entry with the same [originator,DID] exists in the loop detection
   table.  If there is no such entry, the intermediate node SHOULD
   create a new entry in a similar way to that described for the
   originator of the data packet; however, in the Previous hop field, it
   stores the address of the router from which the packet has been
   received.  After the entry has been created in the loop detection
   table, the node forwards the packet to the selected candidate next
   hop.

   For those cases in which an entry already exists in the loop
   detection table, the node checks which one was the last attempted
   node, and poisons the routing table entry that uses that particular
   node to reach the destination.  By poisoning failed paths, DFF
   updates the routing table based on the results from the data plane.
   Then, in order to reroute the data packet, the node selects a new
   next hop among the list of candidates stored in the routing table.
   The selected node MUST not be registered as a previous attempt in the
   list of attempted next-hops in the loop detection table.  I also MUST
   be a different node from that registered in the Previous Hop field.
   In this way, DFF effectively makes data forwarding with loops a
   depth-first search guided by the routing table stored in each node.

   If the node has attempted all the candidate next hops, it turns on
   the return flag in the packet's DFF mesh header and sends the packet
   back to the Previous Hop. The return flag is updated hop-by-hop: it
   is turned on only when a packet has been returned to the previous
   node because the node has failed to forward the packet after trying
   (and failing) with all the possible next hops.  In any other case,
   the flag is turned off by every node before forwarding the packet to
   the next-hop.




Cardenas, et al.        Expires January 12, 2012                [Page 6]

Internet-Draft                     DFF                         July 2011


   If a node has attempted all the candidate next-hops and also founds
   itself registered in the Previous Hop field of the loop detection
   table (i.e., it is the originator of the packet), this means that
   routing has failed; therefore, the originator must drop the packet
   and delete the entry in the loop table.

   In addition to rerouting packets when a loop is detected, nodes
   reroute packets when the link layer fails to receive ACK from the
   neighbor they sent the data packet to.  As soon as the link layer
   gives up on the transmission, DFF proceeds to reroute the packet
   through a different candidate.  In this case, nodes set a duplicate
   detection flag in the DFF mesh header, identifying the packet as a
   potential duplicate.  Duplicate packets may appear in the network
   when the link layer reports a failed transmission due to a failed
   reception of ACKs from the recipient of the packet.  This situation
   is likely to happen in links that are lossy only in one direction.

   Duplicate packets do not alter the depth-first search logic: if a
   packet with a duplicate flag is received by a node who has already
   sent a packet with the same [originator,DID] to Next Hop n (Last Next
   Hop attempted), it assumes that this corresponds to a loop, and the
   node then attempts to reroute the packet to Next Hop n+1 (if
   available), or to send it back to Previous Hop if no other candidate
   next hop are available.  This, however, may correspond to a false
   loop detection (i.e., the packet has not came back from a loop, but
   instead, has been re-sent as a duplicate from the previous hop);
   therefore, DFF does not poison entries in the routing table whenever
   the forwarded packet has the duplicate flag activated.  The only
   exception to this rule appears for the case when the packet has the
   duplicate and the returned flag both turned on.  In such case, DFF
   proceeds to poison the route, since this is a clear indication that
   the forwarding path through the last attempted node is broken.


4.  Coexistence with other packet formats

   For packets encapsulated according to [RFC4944] that do not include a
   DFF mesh header, the DFF node processes them with a simple forwarding
   mechanism that selects the next hop with the lowest cost to reach the
   final destination.  In this case, the node does node create any
   entries in the loop detection table, and it does not attempt to
   reroute such packets through alternate paths.  This forwarding option
   allows for the coexistence of DFF nodes with nodes that do not follow
   the message formats defined in this document (Figure 1).

   A 6lowpan mesh header [RFC4944] is still required for the operation
   of this basic forwarding mechanism.




Cardenas, et al.        Expires January 12, 2012                [Page 7]

Internet-Draft                     DFF                         July 2011


5.  Message Formats

   This document assumes that multi-hop forwarding occurs in the
   adaptation layer following the message format of [RFC4944].
   [RFC4944] indicates that hop-by-hop processing headers with
   additional mesh routing capabilities may be expressed by defining
   additional headers that precede fragmentation or addressing headers.
   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 data forwarding
   mechanism (in this case DFF).

   After these two headers, other LoWPAN headers such as hop-by-hop
   options, header compression or fragmentation can also be included
   before the actual payload.  (Figure 1) shows the mesh headers 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:

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

   Mesh Forw:  is 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, 01 SHOULD
      precede Mesh Forw.  A possible value to use as a mesh forwarding
      identifier based on the reserved ranges defined in [RFC4944] is
      010001.  In this case the dispatch byte would be 01010001.

   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 the value of 1 by the node
      that re-sends the packet after detecting link-layer failure to
      deliver through the last attempted next-hop.  Once the flag is set
      to 1, it MUST not be modified by intermediate nodes.





Cardenas, et al.        Expires January 12, 2012                [Page 8]

Internet-Draft                     DFF                         July 2011


   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 through all the available next-hops.  The
      flag MUST be set to the value of 1 prior to forward the packet
      back to the previous hop and MUST be set to 0 prior to forward the
      packet through a node in the list of candidate next-hop.  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.  The originator address concatenated
      with the DID sequence number form an identifier of previously seen
      data packets.


6.  Data Structures

   The loop detection option is based on the idea of storing the DID and
   originator-ID of a data packet, so that if a packet containing the
   same DID identifier and originator is received, DFF detects it as a
   loop.

   After the loop is detected, DFF follows a distributed depth-first
   search for the destination through the candidate next hops kept in
   the routing table.  In order to do a Depth-First search, nodes need
   to keep a list of their children (i.e., the candidate next hops that
   have been used to forward the packet), and the previous hop (the node
   who sent the data packet for the first time to the current router).

   A Loop Detection Table (Figure 2) needs to be kept by the nodes to
   support the loop detection functionality.  The candidate next hop
   field does not need to be pre-stored, it can be filled dynamically as
   soon as the node attempts to send the packet to a next-hop neighbor.

















Cardenas, et al.        Expires January 12, 2012                [Page 9]

Internet-Draft                     DFF                         July 2011


    +---------+-------------------------------------------------------+
    |Parameter| Description                                           |
    +---------+-------------------------------------------------------+
    |(O,DID)  | Source Address concatenated with a sequential         |
    |         | number. Used to identify previously seen data packets |
    +---------+-------------------------------------------------------+
    |Previous | Address of the router who sent the data packet for the|
    |Hop      | first time to the current router. If forwarding fails,|
    |         | return data packet to this router                     |
    +---------+-------------------------------------------------------+
    |TTL      | Time to live for the current DID entry                |
    +---------+-------------------------------------------------------+
    |Next Hop | First neighbor selected to forward the packet         |
    | 1       |                                                       |
    +---------+-------------------------------------------------------+
    | ...     | ...                                                   |
    +---------+-------------------------------------------------------+
    |Next hop | Neighbor selected the k-th time                       |
    | K       |                                                       |
    +---------+-------------------------------------------------------+


            Figure 2: Basic Elements of a Loop Detection Table


7.  Hop-by-Hop Implementation Options

   While DFF can be used in a route-over or mesh-under protocol, this
   document provides a sample implementation of a mesh-under forwarding
   solution for 6LoWPAN networks; therefore, all addresses referenced in
   this document are either 16-bit short or EUI-64 link layer addresses.

   DFF requires the use of hop-by-hop options, and this document
   describes how these hop-by-hop options can be implemented by
   allocating a new dispatch byte from the reserved values for mesh
   forwarding in [RFC4944].

   To avoid the request of a new dispatch byte, the appendix describes a
   way to implement DFF by overloading the fragmentation header in
   [RFC4944].  This implementation has the advantage of using headers
   already defined by the standard; however, the implementation by
   overloading the fragmentation header only allows rerouting a packet
   on loop detection and not when a link fails.  The reason behind this
   loss of functionality is that rerouting when a link fails requires
   the use of a duplicate flag in the header of the packet.  This is a
   hop-by-hop option that can be set by intermediate nodes, and the
   fragmentation header of [RFC4944] cannot be changed by intermediate
   nodes.



Cardenas, et al.        Expires January 12, 2012               [Page 10]

Internet-Draft                     DFF                         July 2011


   Similarly, a route over implementation of DFF would need to obtain
   new fields in the hop-by-hop options of IPv6 packets.


8.  Acknowledgements

   Ganesh Venkatesh, and Geoff Mulligan provided useful discussions
   which helped shape this document.


9.  IANA Considerations

   This memo includes the request of a new dispatch byte to identify DFF
   headers.  In the Appendix there is an implementation that avoids the
   use of new dispatch bytes.


10.  Security Considerations

   The security of a mesh forwarding protocol depends on the integrity,
   authentication, and confidentiality of the 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].


11.  Appendix A: Example Implementation of a Control Plane for DFF

   There are many route discovery protocols compatible with DFF.  The
   final selection of which control plane to use depends on the resource
   considerations of the nodes in the network.  If nodes have tight
   memory constraints and the network is large, managing the size of the
   routing table is important.  Therefore, a control plane that builds a
   network with a routing table that grows at a slower rate than the
   size of the network--e.g., hierarchical routing, or clustering--is
   important.  If minimizing the routing stretch of the network is a
   priority, and if nodes have enough memory to accommodate a routing
   table of the size of the network, then a routing protocol that stores
   a routing entry for each destination can be implemented.

   The only condition of a control plane that will leverage an
   implementation of DFF is that for each final destination, each node
   should be able to maintain a number of alternate routes being
   advertised by multiple neighbors, which would be used if a selected
   route were to fail.

   While a number of routing protocols satisfy the above constraint,
   they tend to include extra overhead for preventing loops or dealing



Cardenas, et al.        Expires January 12, 2012               [Page 11]

Internet-Draft                     DFF                         July 2011


   with routing inconsistencies or failures.  One of the primary goals
   of DFF is to avoid the use of these extra control messages.  This
   appendix presents a basic control plane compatible with DFF.  It is a
   distance vector protocol that assumes no other control message other
   than periodic routing updates.

   This reference implementation requires two data structures: a link
   table and a routing table.  Both data structures are updated by means
   of periodic control messages that include information about the
   announcing neighbor and the destinations stored by the announcing
   neighbor in its routing table.

11.1.  Data structures

   Link Table

   The Link Table is used to maintain a list of neighbors and the
   quality of their links.  The structure of the link table depends of
   the implementation; however, some key fields are shown in (Figure 3).

     +---------+-----------------------------------------------------+
     |Parameter| Description                                         |
     +---------+-----------------------------------------------------+
     |Next Hop | The address of the neighbor                         |
     +---------+-----------------------------------------------------+
     |Link     | The cost as defined by the metric. If the ETX       |
     |Cost     | metric is used, then the Link Cost is the ETX to    |
     |         | reach this neighbor                                 |
     +---------+-----------------------------------------------------+
     |TTL      | A time to live value used to delete this entry if no|
     |         | new control messages from the neighbor are received |
     |         | before the TTL timer expires.                       |
     +---------+-----------------------------------------------------+
     |Transmit | The forward quality of the link. If ETX metric is   |
     |quality  | used, this field keeps an estimate of the likelihood|
     |         | that a packet successfully arrives at the neighbor  |
     +---------+-----------------------------------------------------+
     |Receiving| The reverse delivery ratio of the link.If ETX metric|
     |quality  | is used, it keeps an estimate of the likelihood that|
     |         | a packet from this neighbor is successfully received|
     +---------+-----------------------------------------------------+
     |One Way  | If the current node does not see itself in the list |
     |Link     | of destinations announced by this neighbor, then    |
     |         | this field is true to indicate it is one-way link   |
     +---------+-----------------------------------------------------+

                    Figure 3: Elements of a Link Table




Cardenas, et al.        Expires January 12, 2012               [Page 12]

Internet-Draft                     DFF                         July 2011


   Routing Table

   The Routing Table contains up to K candidate next hops for each final
   destination.

   The structure of the routing table is implementation dependent;
   however the routing table must contain at least the fields shown in
   (Figure 4) per entry.

     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                    |  Local DST Address 1  |  Cost  | TTL     |
     + Final  DST Address |          ...          |        ...       ~
     |                    |  Local DST Address K  |  Cost  | TTL     |
     +---------------------------------------------------------------+
                                     :
                                     :
     +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
     |                    |  Local DST Address 1  |  Cost  | TTL     |
     + Final  DST Address |          ...          |        ...       ~
     |                    |  Local DST Address K  |  Cost  | TTL     |
     +---------------------------------------------------------------+


                      Figure 4: Routing Table Format

   Final DST Address:  The address of the target destination.

   Local DST Address 1:  The address of the first next-hop candidate.
      The Local DST candidates are sorted based on their cost to reach
      the destination, with Local DEST Address 1 being the next hop for
      the best route, and Local DEST Address K (if available) being the
      next hop for the Kth optimal route.

   TTL:  A time to live value used to delete this entry if the timer
      expires.

   Cost:  The cost to reach the destination through a next hop.

11.2.  Route Discovery

   A route discovery mechanism compatible with DFF needs to be based on
   distance vector, maintain a routing table, and support multiple
   alternate next hops per destination.

   This sample implementation is based on a proactive distance vector
   routing algorithm, where routing table messages are used to exchange
   reachability information among neighboring nodes.




Cardenas, et al.        Expires January 12, 2012               [Page 13]

Internet-Draft                     DFF                         July 2011


   An important configuration parameter is the number of possible next
   hops kept for each destination.  By default the number of possible
   next hops for each final destination in the routing table is a
   maximum of 3.  Having more than one possible next hop improves the
   reliability of the protocol by allowing the depth-first search
   algorithm to use alternate routes in case using preferred next hop
   results in a loop, or if the preferred next hop does not acknowledge
   reception of the data packet.

   Routing table updates are transmitted as configured by the
   administrator; they can be periodic or dynamic.  One of the main
   characteristics of DFF is that it does not need an up to date routing
   table because the loop detection and depth-first search mechanism
   attempts to find alternate routes even when the routing table
   contains stale information.

   Routing table updates should include the following fields:

   Destination Addr:  The Address of the destination in the routing
      table entry.

   Cost to DST:  The total cost to reach DST.  This value depends on the
      metric used.  A popular metric is ETX.

   Based on the information received in the routing table updates, each
   node updates its routing table to be later used by the DFF forwarding
   mechanism.


12.  Appendix B: Implementing DFF without requesting new dispatch bytes

   DFF can be implemented as a full standard conforming to [RFC4944]
   without requesting any new dispatch bytes.  In this way, nodes
   implementing DFF can interoperate with other nodes that only
   implement headers defined in [RFC4944].

   A possible way to avoid the DFF mesh header is by overloading the
   datagram_tag and datagram_offset fields of the fragmentation header
   defined in [RFC4944].

   Because each source maintains a sequence number for the datagram_tag,
   and the datagram_offset can be used to differentiate between
   fragmented packets with the same value in datagram_tag, the DID value
   required by DFF can be generated by the concatenation of the
   datagram_tag and datagram_offset values of a fragmented data frame.

   Nonetheless, an implementation of DFF that avoids the request of a
   new dispatch byte will prevent the use of flags, and without the



Cardenas, et al.        Expires January 12, 2012               [Page 14]

Internet-Draft                     DFF                         July 2011


   existence of a duplicate flag, duplicate packets will not be
   detected.  Therefore, it is RECOMMENDED that nodes that implement DFF
   by using the datagram_tag and datagram_offset fields for storing the
   DID value, do not reroute on link-layer ACK failures, but only on
   loop detections.  In this case, all previously seen [originator,DID]
   values can be assumed to correspond to loop detections, and the
   routing table cost to reach the final destination via the last
   attempted neighbor can be safely poisoned, without the risk of
   poisoning valid routes taken by duplicate packets.

   This implementation of DFF assumes the existence of fragmentation
   headers within the LoWPAN encapsulation.  This works well if data
   packets are fragmented, but if the entire payload datagram fits
   within a single 802.15.4 frame, then [RFC4944] states that the LoWPAN
   encapsulation should not contain a fragmentation header.  However,
   the use of a fragmentation header for a packet that does not need to
   be fragmented should, in principle, not affect the operation of nodes
   implementing [RFC4944].  Therefore, even if a packet does not need to
   be fragmented, the originator node can append the fragmentation
   header so DFF nodes can use it for extracting the DID identifier.

   The control plane used to populate the routing tables can also avoid
   the need to request a new dispatch byte by encapsulating routing
   updates in UDP packets.


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


Authors' Addresses

   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





Cardenas, et al.        Expires January 12, 2012               [Page 15]

Internet-Draft                     DFF                         July 2011


   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-3-6252-2283
   Email: smartnetpro-iwao_std@ml.css.fujitsu.com

































Cardenas, et al.        Expires January 12, 2012               [Page 16]


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