RPL Observations
draft-rahul-roll-rpl-observations-00

ROLL                                                      R. Jadhav, Ed.
Internet-Draft                                                  R. Sahoo
Intended status: Standards Track                                   Y. Wu
Expires: August 8, 2018                                           Huawei
                                                        February 4, 2018

                            RPL Observations
                  draft-rahul-roll-rpl-observations-00

Abstract

   This document describes RPL protocol design issues, various
   observations and possible consequences of the design and
   implementation choices.  Also mentioned are implementation notes for
   the developers to be used in specific contexts.

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 https://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 August 8, 2018.

Copyright Notice

   Copyright (c) 2018 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
   (https://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.

Jadhav, et al.           Expires August 8, 2018                 [Page 1]
Internet-Draft              RPL Observations               February 2018

Table of Contents

   1.  Introduction  . . . . . . . . . . . . . . . . . . . . . . . .   2
     1.1.  Requirements Language and Terminology . . . . . . . . . .   3
   2.  Managing persistent variables across node reboots . . . . . .   3
     2.1.  Persistent storage and RPL state information  . . . . . .   3
     2.2.  Lollipop Counters . . . . . . . . . . . . . . . . . . . .   3
     2.3.  RPL State variables . . . . . . . . . . . . . . . . . . .   4
       2.3.1.  DODAG Version . . . . . . . . . . . . . . . . . . . .   5
       2.3.2.  DTSN field in DIO . . . . . . . . . . . . . . . . . .   5
       2.3.3.  PathSequence  . . . . . . . . . . . . . . . . . . . .   5
     2.4.  State variables update frequency  . . . . . . . . . . . .   5
     2.5.  Recommendations . . . . . . . . . . . . . . . . . . . . .   6
     2.6.  Implementation Notes  . . . . . . . . . . . . . . . . . .   6
   3.  DTSN increment in storing MOP . . . . . . . . . . . . . . . .   6
   4.  DAO retransmission and use of DAO-ACK . . . . . . . . . . . .   7
   5.  Handling resource unavailability  . . . . . . . . . . . . . .   8
   6.  Traffic Types observations  . . . . . . . . . . . . . . . . .   9
   7.  RPL under-specification . . . . . . . . . . . . . . . . . . .   9
   8.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .  10
   9.  IANA Considerations . . . . . . . . . . . . . . . . . . . . .  10
   10. Security Considerations . . . . . . . . . . . . . . . . . . .  10
   11. References  . . . . . . . . . . . . . . . . . . . . . . . . .  10
     11.1.  Normative References . . . . . . . . . . . . . . . . . .  10
     11.2.  Informative References . . . . . . . . . . . . . . . . .  11
   Appendix A.  Additional Stuff . . . . . . . . . . . . . . . . . .  11
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .  11

1.  Introduction

   RPL [RFC6550] specifies a proactive distance-vector routing scheme
   designed for LLNs (Low Power and Lossy Networks).  RPL enables the
   network to be formed as a DODAG and supports storing mode and non-
   storing mode of operations.  Non-storing mode allows reduced memory
   resource usage on the nodes by allowing non-BR nodes to operate
   without managing a routing table and involves use of source routing
   by the 6LBR to direct the traffic along a specific path.  In storing
   mode of operation intermediate routers maintain routing tables.

   This work aims to highlight various issues with RPL which makes it
   difficult to handle certain scenarios.  This work will highlight such
   issues in context to RPL's mode of operations (storing versus non-
   storing).  There are cases where RPL does not provide clear rules and
   implementations have to make their choices hindering interoperability
   and performance.

   [I-D.clausen-lln-rpl-experiences] provides some interesting points.
   Some sections in this draft may overlap with some observations in

Jadhav, et al.           Expires August 8, 2018                 [Page 2]
Internet-Draft              RPL Observations               February 2018

   [clausen], but this is been done to further extend some scenarios or
   observations.  It is highly encouraged that readers should also visit
   [I-D.clausen-lln-rpl-experiences] for other insights.  Regardless,
   this draft is self-sufficient in a way that it does not expect to
   have read [clausen-draft].

1.1.  Requirements Language and 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 RFC 2119 [RFC2119].

   NS-MOP = RPL Non-storing Mode of Operation

   S-MOP = RPL Storing Mode of Operation

   This document uses terminology described in [RFC6550] and [RFC6775].

2.  Managing persistent variables across node reboots

2.1.  Persistent storage and RPL state information

   Devices are required to be functional for several years without
   manual maintanence.  Usually battery power consumption is considered
   key for operating the devices for several (tens of) years.  But apart
   from battery, flash memory endurance may prove to be a lifetime
   bottleneck in constrained networks.  Endurance is defined as maximum
   number of erase-write cycles that a NAND/NOR cell can undergo before
   losing its 'gauranteed' write operation.  In some cases (cheaper
   NAND-MLC/TLC), the endurance can be as less as 2K cycles.  Thus for
   e.g.  if a given cell is written 5 times a day, that NAND-flash cell
   assuming an endurance of 10K cycles may last for less than 6 years.

   In a star topology, the amount of persistent data write done by
   network protocols is very limited.  But ad-hoc networks employing
   routing protocols such as RPL assume certain state information to be
   retained across node reboots.  In case of IoT devices this storage is
   mostly floating gate based NAND/NOR based flash memory.  The impact
   of loss of this state information differs depending upon the type
   (6LN/6LR/6LBR) of the node.

2.2.  Lollipop Counters

   [RFC6550] Section 7.2. explains sequence counter operation defining
   lollipop [Perlman83] style counters.  Lollipop counters specify
   mechanism in which even if the counter value wraps, the algorithm
   would be able to tell whether the received value is the latest or

Jadhav, et al.           Expires August 8, 2018                 [Page 3]
Internet-Draft              RPL Observations               February 2018

   not.  This mechanism also helps in "some cases" to recover from node
   reboot, but is not foolproof.

   Consider an e.g. where Node A boots up and initialises the seqcnt to
   240 as recommended in [RFC6550].  Node A communicates to Node B using
   this seqcnt and node B uses this seqcnt to determine whether the
   information node A sent in the packet is latest.  Now lets assume,
   the counter value reaches 250 after some operations on Node A, and
   node B keeps receiving updated seqcnt from node A.  Now consider that
   node A reboots, and since it reinitializes the seqcnt value to 240
   and sends the information to node B (who has seqcnt of 250 stored on
   behalf of node A).  As per section 7.2. of [RFC6550], when node B
   receives this packet it will consider the information to be old
   (since 240 < 250).

                         +-----+-----+----------+
                         |  A  |  B  |  Output  |
                         +-----+-----+----------+
                         | 240 | 240 | A<B, old |
                         | 240 | 241 | A<B, old |
                         | 240 |  :: | A<B, old |
                         | 240 | 256 | A<B, old |
                         | 240 |  0  | A<B, new |
                         | 240 |  1  | A>B, new |
                         | 240 |  :: | A>B, new |
                         | 240 | 127 | A>B, new |
                         +-----+-----+----------+

      Default values for lollipop counters considered from [RFC6550]
                               Section 7.2.

                Table 1: Example lollipop counter operation

   Based on this figure, there is dead zone (240 to 0) in which if A
   operates after reboot then the seqcnt will always be considered
   smaller.  Thus node A needs to maintain the seqcnt in persistent
   storage and reuse this on reboot.

2.3.  RPL State variables

   The impact of loss of RPL state information differs depending upon
   the node type (6LN/6LR/6LBR).  Following sections explain different
   state variables and the impact in case this information is lost on
   reboot.

Jadhav, et al.           Expires August 8, 2018                 [Page 4]
Internet-Draft              RPL Observations               February 2018

2.3.1.  DODAG Version

   The tuple (RPLInstanceID, DODAGID, DODAGVersionNumber) uniquely
   identifies a DODAG Version.  DODAGVersionNumber is incremented
   everytime a global repair is initiated for the instance (global or
   local).  A node receiving an older DODAGVersionNumber will ignore the
   DIO message assuming it to be from old DODAG version.  Thus a 6LBR
   node (and 6LR node in case of local DODAG) needs to maintain the
   DODAGVersionNumber in the persistent storage, so as to be available
   on reboot.  In case the 6LBR could not use the latest
   DODAGVersionNumber the implication are that it won't be able to
   recover/re-establish the routing table.

2.3.2.  DTSN field in DIO

   DTSN (Destination advertisement Trigger Sequence Number) is a DIO
   message field used as part of procedure to maintain Downward routes.
   A 6LBR/6LR node may increment a DTSN in case it requires the
   downstream nodes to send DAO and thus update downward routes on the
   6LBR/6LR node.  In case of RPL NS-MOP, only the 6LBR maintains the
   downward routes and thus controls this field update.  In case of
   S-MOP, 6LRs additionally keep downward routes and thus control this
   field update.

   In S-MOP, when a 6LR node switches parent it may have to issue a DIO
   with incremented DTSN to trigger downstream child nodes to send DAO
   so that the downward routes are established in all parent/ancestor
   set.  Thus in S-MOP, the frequency of DTSN update might be relatively
   high (given the node density and hysteresis set by objective function
   to switch parent).

2.3.3.  PathSequence

   PathSequence is part of RPL Transit Option, and associated with RPL
   Target option.  A node whichs owns a target address can associate a
   PathSequence in the DAO message to denote freshness of the target
   information.  This is especially useful when a node uses multiple
   paths or multiple parents to advertise its reachability.

   Loss of PathSequence information maintained on the target node can
   result in routing adjacencies been lost on 6LRs/6LBR/6BBR.

2.4.  State variables update frequency

Jadhav, et al.           Expires August 8, 2018                 [Page 5]
Internet-Draft              RPL Observations               February 2018

    +--------------------+-------------------+------------------------+
    |   State variable   |  Update frequency |   Impacts node type    |
    +--------------------+-------------------+------------------------+
    | DODAGVersionNumber |        Low        | 6LBR, 6LR(local DODAG) |
    |        DTSN        | High(SM),Low(NSM) |       6LBR, 6LR        |
    |    PathSequence    | High(SM),Low(NSM) |        6LR, 6LN        |
    +--------------------+-------------------+------------------------+

   Low=<5 per day, High=>5 per day; SM=Storing MOP, NSM=Non-Storing MOP

                       Table 2: RPL State variables

2.5.  Recommendations

   It is necessary that RPL avoids using persistent storage as far as
   possible.  Ideally, extensions to RPL should consider this as a
   design requirement especially for 6LR and 6LN nodes.  DTSN and
   PathSequence are the primary state variables which have major impact.

2.6.  Implementation Notes

   An implementation should use a random DAOSequence number on reboot so
   as to avoid a risk of reusing the same DAOSequence on reboot.  A
   parent node will not respond with a DAO-ACK in case it sees a DAO
   with the same previous DAOSequence.

   Write-Before-Use: The state information should be written to the
   flash before using it in the messaging.  If it is done the other way,
   then the chances are that the node power downs before writing to the
   persistent storage.

3.  DTSN increment in storing MOP

   DTSN increment has major impact on the overall RPL control traffic
   and on the efficiency of downstream route update.  DTSN is sent as
   part of DIO message and signals the downstream nodes to trigger the
   target advertisement.  The 6LR needs to decide when to update the
   DTSN and usually it should do it in a conservative way.  The DTSN
   update mechanism determines how soon the downward routes are
   established along the new path.  RPL specifications does not provide
   any clear mechansim on how the DTSN update should happen in case of
   storing mode.

Jadhav, et al.           Expires August 8, 2018                 [Page 6]
Internet-Draft              RPL Observations               February 2018

                                   (6LBR)
                                      |
                                      |
                                      |
                                     (A)
                                     / \
                                    /   \
                                   /     \
                                 (B)    -(C)
                                  |    /  |
                                  |   /   |
                                  |  /    |
                                 (D)-    (E)
                                   \      ;
                                    \    ;
                                     \  ;
                                      (F)
                                      / \
                                     /   \
                                    /     \
                                  (G)     (H)

                         Figure 1: Sample topology

   Consider example topology shown in figure Figure 1, assume that node
   D switches the parent from node B to C.  Ideally the downstream nodes
   D and its sub-childs should send their target advertisement to the
   new path via node C.  To achieve this result in a efficient way is a
   challenge.  Incrementing DTSN is the only way to trigger the DAO on
   downstream nodes.  But this trigger should be sent not only on the
   first hop but to all the grand-child nodes.  Thus DTSN has to be
   incremented in the complete sub-DODAG rooted at node D thus resulting
   in DIO/DAO storm along the sub-DODAG.  This is specifically a big
   issue in high density networks where the metric deteoration might
   happen transiently even though the signal strength is good.

   The primary implementation issue is whether a child node increment
   its own DTSN when it receives DTSN update from its parent node?  This
   would result in DAO-updates in the sub-DODAG, thus the cost could be
   very high.  If not incremented it may result in serious loss of
   connectivity for nodes in the sub-DODAG.

4.  DAO retransmission and use of DAO-ACK

   [RFC6550] has an optional DAO-ACK mechanism using which an upstream
   parent confirms the reception of a DAO from the downstream child.  In
   case of storing mode, the DAO is addressed to the immediate hop

Jadhav, et al.           Expires August 8, 2018                 [Page 7]
Internet-Draft              RPL Observations               February 2018

   upstream parent resulting in DAO-ACK from the parent.  There are two
   implementations possible:

   (1)  A parent responds with a DAO-ACK immedetialy after receiving the
        DAO.

   (2)  A node waits for the upstream parent to send DAO-ACK to respond
        with a DAO-ACK downstream.  This may not be feasible to use on
        constrained devices because it requires additional state
        information and timers to be handled on behalf of multiple
        downstream nodes whose DAO is in transit.

   Following scenarios do not have clear handling in the specs:

   (1)  What happens if the DAO-ACK for the target is lost at the
        ancestor node link?

   (2)  What happens if the DAO-ACK with Status!=0 is responded by
        ancestor node?

   (3)  Is there any way for the target node to know that the DAO it
        sent has reached the 6LBR successfully?

   Note that any of these inefficiencies are not present in case of
   NSMOP in which the DAO is addressed directly to the 6LBR.

5.  Handling resource unavailability

   The nodes in the constrained networks have to maintain various
   records such as neighbor cache entries and routing entries on behalf
   of other targets to facilitate packet forwarding.  Because of the
   constrained nature of the devices the memory available may be very
   limited and thus the path selection algorithm may have to take into
   consideration such resource constraints as well.

   RPL currently does not have any mechanism to advertise such resource
   indicator metrics.  The primary tables associated with RPL are
   routing table and the neighbor cache.  Even though neighbor cache is
   not directly linked with RPL protocol, the maintenance of routing
   adjacencies results in updates to neigbor cache.

   Following needs to be handled by the specs:

      Is it possible to know that an upstream parent/ancestor cannot
      hold enough routing entries and thus this path should not be used?

Jadhav, et al.           Expires August 8, 2018                 [Page 8]
Internet-Draft              RPL Observations               February 2018

      Is it possible to know that an upstream parent cannot hold any
      more neighbor cache entry and thus this upstream parent should not
      be used?

6.  Traffic Types observations

   RPL is more suited towards MP2P (multi-point to point) traffic, the
   central point here usually is a grounded root/6LBR node.  [RFC6997]
   allows establishing P2P paths within the DODAG.  There are situations
   where a MP2P network needs to be established within the DODAG.  For
   e.g. there could be multiple switches connecting the same light bulb.
   Currently to achieve this, every switch needs to establish a P2P path
   to the bulb.  In cases where the cardinality of nodes connecting to
   the same node is high the cost of establishing P2P paths could be
   very high.  RPL allows 'floating' DODAG to be created but the
   specification defines it to be used under other circumstances.  To
   quote [RFC6550],

   "A grounded DODAG offers connectivity to hosts that are required for
   satisfying the application-defined goal.  ___A floating DODAG is not
   expected to satisfy the goal; in most cases, it only provides routes
   to nodes within the DODAG.  Floating DODAGs may be used, for example,
   to preserve interconnectivity during repair.___"

   Thus it is not clear whether floating DODAGs can be put to use for
   establishing MP2P paths within the DODAG.

7.  RPL under-specification

   (a)  PathSequence: Is it mandatory to use PathSequence in DAO Transit
        container?  RPL mentions that a 6LR/6LBR hosting the routing
        entry on behalf of target node should refresh the lifetime on
        reception of a new Path Sequence.  But RPL does not necessarily
        mandate use of Path Sequence.  Most of the open source
        implementation [RIOT] [CONTIKI] currently do not issue Path
        Sequence in the DAO message.

   (b)  Target Container aggregation in DAO: RPL allows multiple targets
        to be aggregated in a single DAO message and has introduced a
        notion of DelayDAO using which a 6LR node could delay its DAO to
        enable such aggregation.  But RPL does not have clear text on
        handling of aggregated DAOs and thus it hinders
        interoperability.

   (c)  DTSN Update: RPL does not clearly define in which cases DTSN
        should be updated in case of storing mode of operation.  More
        details for this are presented in Section 3.

Jadhav, et al.           Expires August 8, 2018                 [Page 9]
Internet-Draft              RPL Observations               February 2018

8.  Acknowledgements

9.  IANA Considerations

   This memo includes no request to IANA.

10.  Security Considerations

   This is an information draft and does add any changes to the existing
   specifications.

11.  References

11.1.  Normative References

   [RFC2119]  Bradner, S., "Key words for use in RFCs to Indicate
              Requirement Levels", BCP 14, RFC 2119,
              DOI 10.17487/RFC2119, March 1997,
              <https://www.rfc-editor.org/info/rfc2119>.

   [RFC6550]  Winter, T., Ed., Thubert, P., Ed., 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,
              DOI 10.17487/RFC6550, March 2012,
              <https://www.rfc-editor.org/info/rfc6550>.

   [RFC6551]  Vasseur, JP., Ed., Kim, M., Ed., Pister, K., Dejean, N.,
              and D. Barthel, "Routing Metrics Used for Path Calculation
              in Low-Power and Lossy Networks", RFC 6551,
              DOI 10.17487/RFC6551, March 2012,
              <https://www.rfc-editor.org/info/rfc6551>.

   [RFC6552]  Thubert, P., Ed., "Objective Function Zero for the Routing
              Protocol for Low-Power and Lossy Networks (RPL)",
              RFC 6552, DOI 10.17487/RFC6552, March 2012,
              <https://www.rfc-editor.org/info/rfc6552>.

   [RFC6775]  Shelby, Z., Ed., Chakrabarti, S., Nordmark, E., and C.
              Bormann, "Neighbor Discovery Optimization for IPv6 over
              Low-Power Wireless Personal Area Networks (6LoWPANs)",
              RFC 6775, DOI 10.17487/RFC6775, November 2012,
              <https://www.rfc-editor.org/info/rfc6775>.

Jadhav, et al.           Expires August 8, 2018                [Page 10]
Internet-Draft              RPL Observations               February 2018

   [RFC6997]  Goyal, M., Ed., Baccelli, E., Philipp, M., Brandt, A., and
              J. Martocci, "Reactive Discovery of Point-to-Point Routes
              in Low-Power and Lossy Networks", RFC 6997,
              DOI 10.17487/RFC6997, August 2013,
              <https://www.rfc-editor.org/info/rfc6997>.

11.2.  Informative References

   [I-D.clausen-lln-rpl-experiences]
              Clausen, T., Verdiere, A., Yi, J., Herberg, U., and Y.
              Igarashi, "Observations on RPL: IPv6 Routing Protocol for
              Low power and Lossy Networks", draft-clausen-lln-rpl-
              experiences-10 (work in progress), January 2018.

   [Perlman83]
              Perlman, R., "Fault-Tolerant Broadcast of Routing
              Information", North-Holland Computer Networks, Vol.7,
              December 1983.

Appendix A.  Additional Stuff

Authors' Addresses

   Rahul Arvind Jadhav (editor)
   Huawei
   Kundalahalli Village, Whitefield,
   Bangalore, Karnataka  560037
   India

   Phone: +91-080-49160700
   Email: rahul.ietf@gmail.com

   Rabi Narayan Sahoo
   Huawei
   Kundalahalli Village, Whitefield,
   Bangalore, Karnataka  560037
   India

   Phone: +91-080-49160700
   Email: rabinarayans@huawei.com

Jadhav, et al.           Expires August 8, 2018                [Page 11]
Internet-Draft              RPL Observations               February 2018

   Yuefeng Wu
   Huawei
   No.101, Software Avenue, Yuhuatai District,
   Nanjing, Jiangsu  210012
   China

   Phone: +86-15251896569
   Email: wuyuefeng@huawei.com

Jadhav, et al.           Expires August 8, 2018                [Page 12]