ROLL                                                              J. Guo
Internet-Draft                                                  P. Orlik
Intended status: Standards Track       Mitsubishi Electric Research Labs
Expires: December 28, 2013                                 June 26, 2013



                             Loop Free RPL
                    draft-guo-roll-loop-free-rpl-02


Abstract

   The IETF has developed the IPv6 based standards for Low-power and
   Lossy Networks (LLNs) to meet requirements of constrained
   applications, such as field monitoring, inventory control and so on.
   The IPv6 Routing Protocol for LLNs (RPL) was published as [RFC6550]
   in March 2012. Based on routing metrics and constraints [RFC6551],
   RPL builds Directed Acyclic Graph (DAG) topology to establish
   bidirectional routes for LLNs for traffic types of multipoint-to-
   point, point-to-multipoint, and point-to-point. RPL routes are
   optimized for traffic to or from one or more roots that act as sinks.
   As a result, a DAG is partitioned into one or more Destination
   Oriented DAGs (DODAGs), one DODAG per sink. RPL is widely considered
   as a feasible routing protocol for LLNs. However, DODAG loops and
   lack of a loop free DODAG local repair mechanism are two open issues
   to be addressed. This draft introduces an alternative rank and an
   Objective Function to eliminate DODAG loops in RPL. Based on the
   proposed rank and Objective Function, this draft introduces a loop
   free RPL.





















Guo, et al.            Expires December 28, 2013                [Page 1]


Internet-Draft               Loop Free RPL                 July 26, 2013


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 December 28, 2013.

Copyright Notice

   Copyright (c) 2013 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.




















Guo, et al.            Expires December 28, 2013                [Page 2]


Internet-Draft               Loop Free RPL                 July 26, 2013


Table of Contents

   1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . 4
   2. Terminology  . . . . . . . . . . . . . . . . . . . . . . . . . . 5
   3. Alternative Rank . . . . . . . . . . . . . . . . . . . . . . . . 6
      3.1. Alternative Rank Definition . . . . . . . . . . . . . . . . 6
      3.2. Rank Split Operation  . . . . . . . . . . . . . . . . . . . 7
   4. ICMPv6 RPL Control Message Extension . . . . . . . . . . . . . . 7
      4.1. Format of the Modified DIO Base Object . . . . . . . . . .  7
      4.2. DODAG Repair Request (DRQ) . . . . . . . . . . . . . . . .  8
           4.2.1. Format of the DRQ Base Object  . . . . . . . . . . . 8
           4.2.2. Secure DRQ . . . . . . . . . . . . . . . . . . . . . 9
           4.2.3. DRQ Options  . . . . . . . . . . . . . . . . . . . . 9
      4.3. DODAG Repair Reply (DRP) . . . . . . . . . . . . . . . . . 10
           4.3.1. Format of the DRP Base Object . . . . . . . . . . . 10
           4.3.2. Secure DRP  . . . . . . . . . . . . . . . . . . . . 11
           4.3.3. DRP Options . . . . . . . . . . . . . . . . . . . . 11
      4.4. Format of the Path Option  . . . . . . . . . . . . . . . . 11
   5. DODAG Construction  . . . . . . . . . . . . . . . . . . . . . . 12
   6. DODAG Local Repair  . . . . . . . . . . . . . . . . . . . . . . 13
      6.1. DODAG Local Repair in Storing Mode . . . . . . . . . . . . 14
           6.1.1. DRQ Message Processing  . . . . . . . . . . . . . . 14
           6.1.2. DRP Message Processing  . . . . . . . . . . . . . . 15
      6.2. DODAG Local Repair in Non-Storing Mode . . . . . . . . . . 16
          6.2.1. DRQ Message Processing . . . . . . . . . . . . . . . 16
          6.2.2. DRP Message Processing . . . . . . . . . . . . . . . 17
   7. Security Considerations . . . . . . . . . . . . . . . . . . . . 18
   8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 18
   9. References  . . . . . . . . . . . . . . . . . . . . . . . . . . 18
      9.1. Normative References . . . . . . . . . . . . . . . . . . . 18
      9.2. Informative References . . . . . . . . . . . . . . . . . . 19
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 19



















Guo, et al.            Expires December 28, 2013                [Page 3]


Internet-Draft               Loop Free RPL                 July 26, 2013


1.  Introduction

   Low-power and Lossy Networks (LLNs) are a class of networks in which
   nodes and their communication links are constrained. LLN nodes
   typically operate with constrains on processing power, physical size,
   memory, power consumption, lifetime, and rate of activity. Their
   communication links are characterized by high loss rate, low data
   rate, instability, low transmission power, and short transmission
   range. There can be from a few dozen up to thousands of nodes within
   a LLN. Routing in LLNs is different from routing in mobile ad-hoc
   networks. The IETF has developed an IPv6 Routing Protocol for LLNs
   (RPL) published in [RFC6550]. RPL supports multipoint-to-point
   traffic and point-to-multipoint traffic. The support for point-to-
   point traffic is also available.

   RPL builds Directed Acyclic Graph (DAG) topology, which is
   partitioned into one or more Destination Oriented  DAGs (DODAGs).
   DODAG is basic logical structure in RPL. RPL nodes construct and
   maintain DODAG through the DODAG Information Object (DIO) message
   which is transmitted via link-local multicasting by using the Trickle
   timer [RFC6206]. The sink in a DODAG is called the DODAG root. RPL
   defines rules to transmit the DIO messages within a DODAG. The DODAG
   root configures the DODAG parameters including RPLInstanceID,
   DODAGVersionNumber, DODAGID, Rank, etc. and advertises the DODAG
   parameters in the DIO messages. To join a DODAG, a node selects a set
   of DODAG parents, on the routes towards the DODAG root, and a
   preferred DODAG parent as the preferred next hop node for upward
   traffic. Once a node joins a DODAG, it transmits DIO messages to
   advertise the DODAG parameters.

   The traffic inside a LLN flows along the edges of the DODAG, either
   upward or downward. In RPL, upward routes, having the DODAG root as
   destination, are provided by the DODAG construction mechanism using
   DIO messages. Downward routes, from the DODAG root to any other
   destination, are provided by these destinations transmitting the
   Destination Advertisement Object (DAO) messages.

   Three different modes of operation (MOP) for downward routes are
   specified in [RFC6550]:

     1) No downward routes supported by RPL.
     2) Storing mode of operation in which each router stores downward
      routing tables for its sub-DODAG. In Storing mode, the DAO message
      is sent to DAO parents. A node unicasts the DAO messages to the
      selected parent(s). Transmission of the DAO messages propagates
      from the nodes towards the DODAG root, where each intermediate
      router adds its downward routing stack to the DAO messages. In
      Storing mode, downward traffic is sent by using the downward



Guo, et al.            Expires December 28, 2013                [Page 4]


Internet-Draft               Loop Free RPL                 July 26, 2013


      routing tables.
     3) Non-Storing mode of operation in which only the DODAG root
      stores routes to all nodes in the network. In Non-Storing mode,
      the DAO message is sent to the DODAG root. A node unicasts the DAO
      messages to the DODAG root, which then calculates routes to all
      destinations by piecing together the information collected from
      the DAO messages. In Non-Storing mode, downward traffic is sent by
      way of source routing.

   An RPL node may act as a leaf node or as a router. RPL defines
   operation rules for both leaf node and router. For example, a leaf
   node does not extend DODAG connectivity. An RPL router needs to
   implement Trickle timer algorithm [RFC6206]. An RPL router
   implementation needs to support the MOP in use by the DODAG, that is,
   support for upward routes only or support for upward routes and
   downward routes in Storing mode or support for upward routes and
   downward routes in Non-Storing mode.

   RPL has been implemented and tested [draft-clausen-lln-rpl-
   experiences-04]. A snapshot of the DODAG was made every ten seconds.
   In 74.14% of the 4114 snapshots, at least one loop was observed. In
   RPL, the cause of DODAG loops comes from rank increase. This draft
   introduces an alternative rank and an Objective Function to eliminate
   DODAG loops in RPL. In this draft, a node's rank never increases,
   even if a parent becomes unreachable. As a result, the introduced
   rank and Objective Function prevent DODAG loops from occurring. This
   draft also introduces a method for repairing DODAG locally without
   causing any DODAG loop. The DODAG local repair method applies to both
   Storing and Non-Storing modes of operation in RPL.

2.  Terminology

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

   Additionally, this draft employs terminologies defined in [RFC6550],
   and extends following terminologies:

   DIO: DODAG Information Object in which the rank is represented by two
         integers.

   Up: Up refers to the direction from leaf node or router towards the
         DODAG root.

   Down: Down refers to the direction from the DODAG root towards leaf
         node or router.




Guo, et al.            Expires December 28, 2013                [Page 5]


Internet-Draft               Loop Free RPL                 July 26, 2013


   This draft introduces the following new terminologies:

   DRQ: DODAG Repair Request

   DRP: DODAG Repair Reply

   Rank_DRQ: The rank of the node generating the DRQ message.

   Rank_DRP: The rank of the node transmitting the DRP message.

   DRQID: IPv6 address of the node generating DRQ message.

   DRSN: Sequence number of the DRQ message of the node generating DRQ
         message.

3.  Alternative Rank

   In RPL, the rank plays very important role in the DODAG construction
   and maintenance. The rank of a node defines a position of the node
   relative to other nodes with respect to the DODAG root. Each node
   maintains its own rank. The DODAG root has the lowest rank. Nodes
   maintain their ranks based on parent-child relationship such that a
   child must have a rank strictly greater than ranks of all its DODAG
   parents. The DODAG root has no parent. The acyclic structure of the
   DODAG is guaranteed as long as the rank of any node is strictly
   greater than ranks of its DODAG parents. It is safe for a node to
   decrease its rank, as long as its rank remains greater than the ranks
   of its DODAG parents. However, the rank increase can cause DODAG
   loops. RPL allows rank increase, which is the source of DODAG loops
   in RPL. A node's rank increase may also cause all nodes in sub-DODAG
   to increase their ranks, which may lead to instability in the rank
   values.

3.1.  Alternative Rank Definition

   DODAG loops in RPL can be avoided if nodes do not increase their
   ranks. In order to meet this restriction, this draft defines the rank
   of a node as a proper fraction:

                             Rank = m/n (1)

   where m and n are integers such that 0 <= m < n.

   The principle of this alternative rank definition comes from the fact
   that there are an infinite number of proper fractions between any two
   proper fractions. This guarantees that a node can decrease its rank
   for any number of times and still keep its rank greater than ranks of
   its DODAG parents.



Guo, et al.            Expires December 28, 2013                [Page 6]


Internet-Draft               Loop Free RPL                 July 26, 2013


   In this draft, a node maintains its rank as two integers, that is,
   numerator and denominator. The fractional value is used in rank
   operations, such as rank comparison.

   The ROOT_RANK is defined as 0/1 and maintained as 0 and 1. The DODAG
   root sets its rank to ROOT_RANK. The INFINITE_RANK is defined as 1/1
   and maintained as 1 and 1. The INFINITE_RANK can not be advertised in
   the DIO messages by any node.

3.2.  Rank Split Operation

   For any two ranks R1 = m/n and R2 = p/q, the rank split operation is
   defined as:

                      sp(R1, R2) = (m+p)/(n+q)  (2)

   It can be shown that if R1 < R2, then R1 < sp(R1,R2) < R2. That is,
   the split operation splits two ranks R1 and R2 and generates a new
   rank sp(R1,R2) that is in between R1 and R2.

4.  ICMPv6 RPL Control Message Extension

   This draft uses RPL control messages defined in [RFC6550] except the
   DIO message. The rank is advertised in the RPL control message using
   two integers, numerator and denominator, instead of the fractional
   value. As a result, the format of DIO Base Object is modified. In
   addition, to repair a DODAG locally, two new RPL control messages,
   DODAG Repair Request (DRQ) message and DODAG Repair Reply (DRP)
   message, are introduced. RPL control message format is defined in
   Figure 6 and Figure 7 of [RFC6550]. The code field for the DRQ and
   DRP messages needs to be assigned by IANA. The message base for DRQ
   and DRP are defined as follows.

4.1.  Format of the Modified DIO Base Object

        0                   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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       | RPLInstanceID |Version Number |            Rank_N             |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |             Rank_D            |G|0| MOP | Prf |     DTSN      |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |     Flags     |                   Reserved                    |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
       +                                                               +
       |                                                               |
       +                            DODAGID                            +



Guo, et al.            Expires December 28, 2013                [Page 7]


Internet-Draft               Loop Free RPL                 July 26, 2013


       |                                                               |
       +                                                               +
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |   Option(s)...
       +-+-+-+-+-+-+-+-+

                      Figure 1: The Modified DIO Base Object

   Rank_N: 16-bit unsigned integer indicating the numerator of
         fractional rank of the node generating DIO message.

   Rank_D: 16-bit unsigned integer indicating the denominator of
         fractional rank of the node generating DIO message.

   The rest of fields are same as being described in [RFC6550].

4.2.  DODAG Repair Request (DRQ)

         The DRQ message is used by a node to repair a DODAG locally if
         a parent becomes unreachable. A node may also use the DRQ
         message to discover additional parents if it is necessary.
         Functionality of DRQ message is different from DIS message
         defined in [RFC6550]. A DRQ message can be relayed multiple
         hops.

4.2.1.  Format of the DRQ Base Object

        0                   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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       | RPLInstanceID |Version Number |             RankQ_N           |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |              RankQ_D          |      DRSN     |  HC   |   MH  |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
       +                                                               +
       |                                                               |
       +                            DODAGID                            +
       |                                                               |
       +                                                               +
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
       +                                                               +
       |                                                               |
       +                             DRQID                             +
       |                                                               |



Guo, et al.            Expires December 28, 2013                [Page 8]


Internet-Draft               Loop Free RPL                 July 26, 2013


       +                                                               +
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |   Option(s)...
       +-+-+-+-+-+-+-+-+

                      Figure 2: The DRQ Base Object

   RPLInstanceID: 8-bit unsigned field as described in [RFC6550] to
         indicate which RPL Instance the DODAG is a part.

   Version Number: 8-bit unsigned integer as described in [RFC6550] to
         indicate the DODAGVersionNumber.

   RankQ_N: 16-bit unsigned integer indicating the numerator of
         fractional rank of the node generating the DRQ message.

   RankQ_D: 16-bit unsigned integer indicating the denominator of
         fractional rank of the node generating the DRQ message.

   DRSN: 8-bit field indicating sequence number of the DRQ message of
         the node generating the DRQ message.

   HC: 4-bit field to indicate the number of hops traveled by a DRQ
         message.

   MH: 4-bit field to indicate the maximum number of hops a DRQ message
         can travel. If a DRQ message reaches the maximum number of
         hops, it must be ignored.

   DODAGID: 128-bit field as defined in [RFC6550]. A DODAGID is the
         identifier of a DODAG root. The DODAGID is unique within the
         scope of a RPL Instance in the LLN. The DODAGID must be a
         routable IPv6 address belonging to the DODAG root.

   DRQID: 128-bit IPv6 address of the node generating the DRQ message.

4.2.2.  Secure DRQ

   A Secure DRQ message follows the format in Figure 7 of [RFC6550],
   where the base format is the DRQ message shown in Figure 2.

4.2.3.  DRQ Options

   The DRQ message may carry valid options.

   This draft allows for the DRQ message to carry the following options:




Guo, et al.            Expires December 28, 2013                [Page 9]


Internet-Draft               Loop Free RPL                 July 26, 2013


      0x00 Pad1
      0x01 PadN
      Path: This option field is present only if MOP is Non-Storing. The
      Path field contains IPv6 addresses of nodes traversed by the DRQ
      message along the path.

4.3.  DODAG Repair Reply (DRP)

      Upon receiving a DRQ message, a router with lower rank and non-
      empty DODAG parent set may generate a DRP message in responding to
      a received DRQ message.

4.3.1.  Format of the DRP Base Object

        0                   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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       | RPLInstanceID |Version Number |             RankQ_N           |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |              RankQ_D          |             RankP_N           |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |              RankP_D          |      DRSN     |  Reserved     |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
       +                                                               +
       |                                                               |
       +                            DODAGID                            +
       |                                                               |
       +                                                               +
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
       +                                                               +
       |                                                               |
       +                             DRPID                             +
       |                                                               |
       +                                                               +
       |                                                               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |   Option(s)...
       +-+-+-+-+-+-+-+-+

                      Figure 3: The DRP Base Object

   RPLInstanceID: 8-bit unsigned field as described in [RFC6550] to
         indicate which RPL Instance the DODAG is a part.

   Version Number: 8-bit unsigned integer as described in [RFC6550] to



Guo, et al.            Expires December 28, 2013               [Page 10]


Internet-Draft               Loop Free RPL                 July 26, 2013


         indicate the DODAGVersionNumber.

   RankQ_N: 16-bit unsigned integer indicating the numerator of
         fractional rank of the node generating the DRQ message.

   RankQ_D: 16-bit unsigned integer indicating the denominator of
         fractional rank of the node generating the DRQ message.

   RankP_N: 16-bit unsigned integer indicating the numerator of
         fractional rank of the node sending the DRP message.

   RankP_D: 16-bit unsigned integer indicating the denominator of
         fractional rank of the node sending the DRP message.

   DRSN: 8-bit field indicating the sequence number of DRQ message of
         the node generating the DRQ message.

   Reserved: 8 unassigned bits of the DRP Base are reserved. They must
         be set to zero on transmission and must be ignored on
         reception.

   DODAGID: 128-bit field as defined in [RFC6550]. A DODAGID is the
         identifier of a DODAG root. The DODAGID is unique within the
         scope of a RPL Instance in the LLN. The DODAGID MUST be a
         routable IPv6 address belonging to the DODAG root.

   DRPID: 128-bit IPv6 address of the node that is destination of the
         DRP message.

4.3.2.  Secure DRP

   A Secure DRP message follows the format in Figure 7 of [RFC6550],
   where the base format is the DRP message shown in Figure 3.

4.3.3.  DRP Options

   The DRP message may carry valid options.

   This draft allows for the DRP message to carry the following options:

      0x00 Pad1
      0x01 PadN
      Path: This option is present only if MOP is Non-Storing and flag F
      is set. The Path field contains IPv6 addresses of traversed nodes
      by the DRQ message and the upward DRP message along the path.

4.4.  RPL Control Message Options




Guo, et al.            Expires December 28, 2013               [Page 11]


Internet-Draft               Loop Free RPL                 July 26, 2013


   The formats of option Pad1 and PadN are described in Figure 20 and
   Figure 21 of [RFC6550], respectively.

   The format of the Path option is as follows:

        0                   1                   2
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - -
       |  Option Type  | Option Length | Path Data
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+- - - - - - - -

                   Figure 4: Format of the Path Option

   Option Type: 8-bit identifier of the type of option. The Option Type
         value needs to be assigned by IANA.

   Option Length: 8-bit unsigned integer, representing the length in
         octets of the option Path Data field, not including the Option
         Type and Option Length fields.

   Path Data: A variable length field that contains a list of IPv6
         addresses.

5.  DODAG Construction

   In RPL, a DODAG is uniquely identified by the (RPLInstanceID,
   DODAGID) tuple and a DODAG Version is uniquely identified by the
   (RPLInstanceID, DODAGID, DODAGVersionNumber) tuple. The
   DODAGVersionNumber is monotonically incremented by the DODAG root.

   To construct a new DODAG, the DODAG root configures DODAG parameters
   and transmits a DIO message with new (RPLInstanceID, DODAGID) tuple.
   To construct a new DODAG Version, the DODAG root transmits a DIO
   message with an increased DODAGVersionNumber. The DIO message is
   transmitted via link-local multicasting to all-RPL-nodes. Nodes
   obtain the DODAG parameters configured by the DODAG root in received
   DIO messages.

   Upon receiving the DIO messages transmitted by the DODAG root or
   neighboring nodes containing new (RPLInstanceID, DODAGID,
   DODAGVersionNumber) tuple, the first hop neighboring nodes of the
   DODAG root may decide to join new DODAG advertised in received DIO
   messages. To do so, the first hop nodes add the DODAG root and
   selected neighboring nodes into their DODAG parent set and store the
   DODAG parameters advertised in received DIO messages. The first hop
   nodes keep all DODAG parameters unchanged except the rank. The first
   hop nodes use information carried in received DIO messages to
   calculate their ranks. To calculate its rank, a first hop node find



Guo, et al.            Expires December 28, 2013               [Page 12]


Internet-Draft               Loop Free RPL                 July 26, 2013


   the maximum rank, Rank_Max, of the ranks of its DODAG parents. A
   first hop node set its rank such that its rank > Rank_max and its
   rank <= sp(Rank_Max, INFINITE_RANK). Upon joining a new DODAG, the
   first hop routers generate and transmit the DIO messages by following
   rules specified in [RFC6550] to advertise the DODAG parameters. A
   router must not transmit the DIO messages for DODAG Versions of which
   it is not a member. A router that is not the DODAG root must not
   change the DODAG parameters received in DIO messages except the rank
   and DTSN fields. All other DODAG parameters, such as the DODAGID and
   DODAGVersionNumber, must be propagated unchanged down the DODAG as
   nodes join new DODAG or new DODAG Version.

   Upon receiving the DIO messages transmitted by the first hop
   neighboring routers, the second hop neighboring nodes of the DODAG
   root that want to join new DODAG or new DODAG Version perform same
   procedure as the first hop neighboring nodes do. The second hop
   routers then generate and transmit the DIO messages same as the first
   hop router do.

   This DIO message propagation process continues until all nodes
   receive the DIO messages, select the DODAG parents and store their
   DODAG parameters, that is, the DODAG is completely constructed.

   Among its DODAG parents, a node selects one preferred DODAG parent to
   be used as the preferred next hop node along upward routes to the
   DODAG root. A node also selects some of its DODAG parents as its DAO
   parents and schedules the DAO transmission.

6.  DOADG Local Repair

   When a DODAG parent becomes unreachable, a node may switch to another
   DODAG parent for upward traffic. DODAG may be locally repaired by the
   node transmitting a DRQ message. The DRQ message is transmitted by
   the DRQ message generator via link-local multicasting to all-RPL-
   nodes.

   Upon receiving a DRQ message, a link-local neighboring router which
   is not the DODAG root discards the DRQ message if it does not have
   any DODAG parent. If the link-local neighboring router is the DODAG
   root, it accepts the DRQ message and generates a DRP message. If the
   link-local neighboring router is not the DODAG root and has a non-
   empty DODAG parent set and its rank is lower than Rank_DRQ (=
   RankQ_N/RankQ_D), it accepts the DRQ message and generates a DRP
   message. If the link-local neighboring router is not the DODAG root
   and has a non-empty DODAG parent set and its rank is greater than or
   equal to Rank_DRQ, it forwards the DRQ message to its preferred DODAG
   parent. This forwarding process continues until the DRQ message is
   discarded if HC of this DRQ message reaches MH or by a router that



Guo, et al.            Expires December 28, 2013               [Page 13]


Internet-Draft               Loop Free RPL                 July 26, 2013


   has an empty DODAG parent set. Otherwise, the DRQ message reaches a
   router which is either the DODAG root or a router that has a non-
   empty DODAG parent set and a rank lower than Rank_DRQ, a DRP message
   is then generated.

   The DRP message is unicasted. In Storing mode, the DRP message
   generator transmits the DRP message to the DRQ message generator by
   using a downward routing table. In Non-Storing mode, the DRP message
   is transmitted to the DRQ message generator by using Path option
   field.

6.1.  DODAG Local Repair in Storing Mode

   In Storing mode, if a DODAG parent becomes unreachable, a node
   removes that DODAG parent from its DODAG parent set.

   If the updated DODAG parent set becomes empty, the node shall
   transmit a DRQ message to discover new DODAG parents.

   If the updated DODAG parent set is not empty, the node checks if the
   removed DODAG parent is its preferred DODAG parent. If yes, the node
   shall select a new preferred DODAG parent. Whether or not the removed
   DODAG parent is the preferred DODAG parent, the node may transmit a
   DRQ message to discover additional parents. The node may also
   schedule a No-Path DAO message transmission if the removed DODAG
   parent is its DAO parent.

   To transmit a DRQ message in Storing mode, the node generates a DRQ
   message. It sets RPLInstanceID, DODAGVersionNumber and DODAGID by
   using the maintained DODAG parameters. It sets RankQ_N and RankQ_D to
   the numerator and denominator of its fractional rank, respectively.
   The node increases its DRSN by 1 and sets HC = 0 and MH to an
   appropriate value. There is no Path option field in Storing mode.

6.1.1.  DRQ Message Processing

   When a router receives a DRQ message, it discards the DRQ message if
   its DODAG parent set is empty. Otherwise, the router performs the
   following filtering process and discards the DRQ message if any of
   following conditions is true:

      i) RPLInstanceID or DODAGVersionNumber or DODAGID in the DRQ
      message is not equal to the respective value maintained by the
      router.
      ii) The DRQ message was received already by comparing DRQID and
      DRSN.
      iii) HC is equal to MH.
      iv) The DRQ message is transmitted by router's DODAG parent.



Guo, et al.            Expires December 28, 2013               [Page 14]


Internet-Draft               Loop Free RPL                 July 26, 2013


      v) The DRQ message is generated by router itself or by its DODAG
      parent.

   If the DRQ message passes filtering process, the receiving router
   processes the DRQ message further.

   If the receiving router is the DODAG root, it accepts the DRQ message
   and generates a DRP message. To generate a DRP message, the DODAG
   root copies RPLInstanceID, DODAGVersionNumber, DRSN, and DODAGID from
   the DRQ message. It sets DRPID to DRQID, RankQ_N and RankQ_D to the
   RankQ_N and RankQ_D in DRQ message, respectively. It sets RankP_N and
   RankP_D to the numerator and denominator of its fractional rank,
   respectively. The DODAG root forwards the DRP message to the node
   from which it received the DRQ message.

   If the receiving router is not the DODAG root and its rank is lower
   than Rank_DRQ, the router accepts the DRQ message and generates a DRP
   message as the root does. The router forwards the DRP message to the
   node from which it received the DRQ message.

   If the receiving router is not the DODAG root and its rank is greater
   than or equal to Rank_DRQ, it adds a route entry to node DRQID into
   its downward routing table, increases value of HC field by 1 and
   forwards the DRQ message to its preferred DODAG parent.

6.1.2.  DRP Message Processing

   When a node receives a DRP message, it first performs filtering
   process and discards the DRP message if any of following conditions
   is true:

      i) RPLInstanceID or DODAGVersionNumber or DODAGID in the DRP
      message is not equal to the respective value maintained by the
      receiving node.
      ii) The DRP message was received already by comparing DRPID and
      DRSN.
      iii) The receiving node is leaf node and is not the DRQ message
      generator.

   If DRP message passes filtering process, the receiving node processes
   the DRP message further.

   If the receiving node is the DRQ message generator and the DRP
   message sender is not in its DODAG parent set, it may add the DRP
   message sender into its DODAG parent set and select a new preferred
   DODAG parent. The receiving node may schedule a DAO message
   transmission if the DRP message sender is added into its DAO parent
   set.



Guo, et al.            Expires December 28, 2013               [Page 15]


Internet-Draft               Loop Free RPL                 July 26, 2013


   If the receiving node is not the DRQ message generator, it must be a
   router.

   If the receiving router has no route entry to node DRPID in its
   downward routing table, it discards the DRP message.

   If the receiving router has a downward route entry to node DRPID and
   its rank is greater than or equal to Rank_DRQ (= RankQ_N/RankQ_D), it
   decreases its rank to sp(Rank_DRQ, Rank_DRP), where Rank_DRP =
   RankP_N/RankP_D. The receiving router updates its DODAG parent set
   caused by its rank decrease, that is, removing DODAG parents whose
   ranks are greater than or equal to sp(Rank_DRQ, Rank_DRP). If its
   preferred DODAG parent is removed, it selects a new preferred DODAG
   parent. The receiving router then updates the RankP_N and RankP_D
   fields of the DRP message to the numerator and denominator of its
   fractional rank, respectively, and forwards the DRP message to next
   hop node on the downward route. It may schedule a No-Path DAO message
   transmission if any of its DAO parents is removed due to its rank
   decrease.

   If the receiving router has a downward route entry to node DRPID and
   its rank is lower than Rank_DRQ, it updates the RankP_N and RankP_D
   fields of DRP message to the numerator and denominator of its
   fractional rank, respectively, and forwards the DRP message to next
   hop node on the downward route. Noticed that the rank of receiving
   router is less than Rank_DRQ if the receiving router is on multiple
   DODAG repair downward routes. When the receiving router receives a
   DRP message, it may decrease its rank. Therefore, subsequent DRP
   messages may carry a Rank_DRQ greater than or equal to the rank of
   receiving router. If the receiving router is only on a single DODAG
   repair downward route, its rank must be greater than or equal to
   Rank_DRQ based on the DRQ message process procedure.

6.2.  DODAG Local Repair in Non-Storing Mode

   The handling of parent unreachability in Non-Storing mode is similar
   to that in Storing mode. The first difference is that after removing
   a DAO parent from its DAO parent set, if its DODAG parent set is not
   empty, a node may schedule a DAO message transmission instead of the
   No-Path DAO message transmission. The second difference is that to
   generate a DRQ message in Non-Storing mode, a node adds a Path option
   field by inserting its IPv6 address into the Path option field. The
   third difference is that the DRP message is sent to destination node
   DRPID by source routing via Path option.

6.2.1.  DRQ Message Processing

   When a router receives a DRQ message, it performs same filtering



Guo, et al.            Expires December 28, 2013               [Page 16]


Internet-Draft               Loop Free RPL                 July 26, 2013


   process as that in Storing mode. If the DRQ message passes filtering
   process, the receiving router processes the DRQ message further.

   If the receiving router is the DODAG root, it accepts the DRQ message
   and generates a DRP message similarly as in Storing mode. The DODAG
   root copies Path option field from DRQ message to Path option field
   of DRP message. The DODAG root transmits the DRP message to
   destination node DRPID by using the route provided in Path option
   field, and on the downward route, intermediate routers obtain next
   hop node from the Path option field of DRP message.

   If the receiving router is not the DODAG root and its rank is lower
   than Rank_DRQ, it accepts the DRQ message and generates a DRP message
   similarly as the DODAG root does. It copies the Path option field
   from DRQ message to the Path option field of DRP message. The
   receiving router forwards the DRP message to the node from which it
   received the DRQ message. The DRP message is sent to destination node
   DRPID via route provided in Path option field.

   If the receiving router is not the DODAG root and its rank is greater
   than or equal to Rank_DRQ, It updates the DRQ message by inserting
   its own IPv6 address into the Path option field, increasing the value
   of HC field by 1 and forwards the DRQ message to its preferred DODAG
   parent.

6.2.2.  DRP Message Processing

   When a node receives a DRP message, it performs the same filtering
   process as in Storing mode. If the DRP message passes filtering
   process, the receiving node processes the DRP message further. The
   receiving node can be a leaf node or a router.

   If the receiving node is the DRQ message generator and the DRP
   message sender is not in its DODAG parent set, it may add the DRP
   message sender into its DODAG parent set. The receiving node may
   select a new preferred DODAG parent. It may also schedule a DAO
   message transmission if the DRP message sender is added into its DAO
   parent set.

   If the receiving node is not DRQ message generator, it must be a
   router.

   If the receiving router is not on the downward route, it discards the
   DRP message. Otherwise, if its rank is lower than Rank_DRQ, the
   receiving router updates the RankP_N and RankP_D fields of the DRP
   message to the numerator and denominator of its fractional rank,
   respectively, and forwards the DRP message to destination node DRPID
   by obtaining route provided in the Path option field. Again, the rank



Guo, et al.            Expires December 28, 2013               [Page 17]


Internet-Draft               Loop Free RPL                 July 26, 2013


   of receiving router is less than Rank_DRQ if the receiving router is
   on multiple DODAG repair downward routes. If its rank is greater than
   or equal to Rank_DRQ, the receiving router decreases its rank to
   sp(Rank_DRQ, Rank_DRP) and updates its DODAG parent set by removing
   any DODAG parent whose rank is greater than or equal to sp(Rank_DRQ,
   Rank_DRP). If its preferred DODAG parent is removed, it selects a new
   preferred DODAG parent. The receiving router updates the RankP_N and
   RankP_D fields of DRP message to the numerator and denominator of its
   fractional rank, respectively, and forwards the DRP message to the
   destination node DRPID by obtaining route provided in the Path option
   field. Furthermore, the receiving router may schedule a DAO message
   transmission if any of its DAO parents was removed due to its rank
   decrease.

7.  Security Considerations

   This draft introduces an alternative rank computation method and a
   DODAG local repair mechanism. In general, the security considerations
   for the DODAG construction and maintenance are similar to the ones
   for the operation of RPL as described in Section 19 of [RFC6550].
   Section 10 of RPL specification [RFC6550] describes a variety of
   security mechanisms that provide data confidentiality,
   authentication, replay protection and delay protection services. Each
   RPL control message has a secure version that allows the
   specification of the level of security and the algorithms used to
   secure the message. New RPL control messages (DRQ and DRP) defined in
   this draft have secure versions as well.

8.  IANA Considerations

   This draft defines two new RPL Control Messages types and a new RPL
   Control Message Option.

   Code field for the DODAG Repair Request (DRQ) message needs to be
   assigned by IANA.

   Code field for the DODAG Repair Reply (DRP) message needs to be
   assigned by IANA.

   Option Type field for Path option field needs to be assigned by IANA.


9.  References

9.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119, March 1997.



Guo, et al.            Expires December 28, 2013               [Page 18]


Internet-Draft               Loop Free RPL                 July 26, 2013


   [RFC4443]  Conta, A., Deering, S., and M. Gupta, "Internet Control
              Message Protocol (ICMPv6) for the Internet Protocol
              Version 6 (IPv6) Specification", RFC 4443, March 2006.

   [RFC6550]  Winter, T., Thubert, P., Brandt, A., Hui, J., Kelsey, R.,
              Levis, P., Pister, K., Struik, R., Vasseur, JP., and R.
              Alexander, "RPL: IPv6 Routing Protocol for Low-Power and
               Lossy Networks", RFC 6550, March 2012.

   [RFC6206]  Levis, P., Clausen, T., Hui, J., Gnawali, O., Ko, J., "The
              Trickle Algorithm", RFC 6206, March 2011.

   [RFC6551]  Vasseur, JP., Kim, M., Pister, K., Dejean, N., and D.
              Barthel, "Routing Metrics Used for Path Calculation in
              Low-Power and Lossy Networks", RFC 6551, March 2012.


9.2.  Informative References

   [83rd IETF Meeting Presentation]  Clausen, T., Yi, J., Colin de
              Verdiere, A., Herberg, U., "Experiences with RPL: IPv6
              Routing Protocol for Low power and Lossy Networks", Paris,
              France, March 2012.


Authors' Addresses

   Jianlin Guo
   Mitsubishi Electric Research Laboratories
   201 Broadway
   Cambridge, Massachusetts 02139
   USA

   Phone: +1 617 621 7541
   Email: guo@merl.com


   Philip Orlik
   Mitsubishi Electric Research Laboratories
   201 Broadway
   Cambridge, Massachusetts 02139
   USA

   Phone: +1 617 621 7570
   Email: porlik@merl.com






Guo, et al.            Expires December 28, 2013               [Page 19]