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

Versions: 00 01 draft-jadhav-roll-efficient-npdao

ROLL WG                                                        R. Jadhav
INTERNET-DRAFT                                                  R. Sahoo
Intended Status: Informational                                    Z. Cao
Expires: December 27, 2016                                   Huawei Tech
                                                                 H. Deng
                                                            China Mobile
                                                           June 27, 2016


                     No-Path DAO Problem Statement
                  draft-jadhav-roll-no-path-dao-ps-01


Abstract

   This document describes the problems associated with the use of No-
   Path DAO messaging in RPL.

Status of this Memo

   This Internet-Draft is submitted to IETF in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as
   Internet-Drafts.

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

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/1id-abstracts.html

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html


Copyright and License Notice

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



Jadhav, et al.         Expires December 27, 2016                [Page 1]


INTERNET DRAFT      draft-jadhav-roll-no-path-dao-01       June 27, 2016


   publication of this document. Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document. Code Components extracted from this document must
   include Simplified BSD License text as described in Section 4.e of
   the Trust Legal Provisions and are provided without warranty as
   described in the Simplified BSD License.



Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
     1.1. Current No-Path DAO messaging . . . . . . . . . . . . . . .  3
     1.2. Cases when No-Path DAO may be used  . . . . . . . . . . . .  4
     1.3. Why No-Path DAO is important? . . . . . . . . . . . . . . .  5
     1.4. Terminology . . . . . . . . . . . . . . . . . . . . . . . .  5
   2. Problems with current No-Path DAO messaging . . . . . . . . . .  5
     2.1. Lost NP-DAO due to Link break to the previous parent  . . .  5
     2.2. Invalidate routes to dependent nodes of the switching
          node  . . . . . . . . . . . . . . . . . . . . . . . . . . .  6
     2.3. Route downtime caused by asynchronous operation of NPDAO
          and DAO . . . . . . . . . . . . . . . . . . . . . . . . . .  6
   3. Requirements for the No-Path DAO Optimization . . . . . . . . .  6
     3.1. Req#1: Tolerant to the link failures to the previous
          parents.  . . . . . . . . . . . . . . . . . . . . . . . . .  7
     3.2. Req#2: Support of removal of entries to the dependent
          nodes of the switching node.  . . . . . . . . . . . . . . .  7
     3.3. Req#3: No disruption of downstream reachability to the
          node while sending NP-DAO.  . . . . . . . . . . . . . . . .  7
   4.  Existing Solution  . . . . . . . . . . . . . . . . . . . . . .  7
     4.1. NP-DAO can be generated by the parent node who detects
          link failure to the child . . . . . . . . . . . . . . . . .  7
     4.2. NP-DAO can be generated once the link is restored to the
          previous parent.  . . . . . . . . . . . . . . . . . . . . .  8
   5.  Security Considerations  . . . . . . . . . . . . . . . . . . .  9
   6.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . .  9
   7.  Acknowledgements . . . . . . . . . . . . . . . . . . . . . . .  9
   8.  References . . . . . . . . . . . . . . . . . . . . . . . . . .  9
     8.1. Normative References  . . . . . . . . . . . . . . . . . . .  9
     8.2. Informative References  . . . . . . . . . . . . . . . . . .  9
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . .  9










Jadhav, et al.         Expires December 27, 2016                [Page 2]


INTERNET DRAFT      draft-jadhav-roll-no-path-dao-01       June 27, 2016


1.  Introduction

   RPL [RFC6550] specifies a proactive distance-vector based routing
   scheme. The specification has an optional messaging in the form of
   DAO messages using which the 6LBR can learn route towards any of the
   nodes. In storing mode, DAO messages would result in routing entries
   been created on all intermediate hops from the node's parent all the
   way towards the 6LBR.

   [RFC6550] also allows use of No-Path DAO (NPDAO) messaging to
   invalidate a routing path and thus releasing of any resources
   utilized on that path. A No-Path DAO is a DAO message with route
   lifetime of zero, signaling route invalidation for the given target.

   This document studies the problems associated with the current use of
   No-Path DAO messaging, which creates route inefficiency and
   inconsistence. This document also discusses the requirements for an
   optimized No-Path DAO messaging scheme.

1.1. Current No-Path DAO messaging

   [RFC6550] introduced No-Path DAO messaging in the storing mode so
   that the node switching its current parent can inform its parents and
   ancestors to invalidate the existing route. Subsequently parents or
   ancestors would release any resources (such as the routing entry) it
   maintains on behalf of that child node. The No-Path DAO message
   always traverses the RPL tree in upward direction, originating at the
   target node itself.

   For the rest of this document consider the following topology:





















Jadhav, et al.         Expires December 27, 2016                [Page 3]


INTERNET DRAFT      draft-jadhav-roll-no-path-dao-01       June 27, 2016


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

                       Figure 1: Sample Topology

   Node (D) is connected via preferred parent (B). (D) has an alternate
   path via (C) towards the BR. Node (A) is the common ancestor for (D)
   for paths through (B)-(G) and (C)-(H). When (D) switches from (B) to
   (C), [RFC6550] suggests sending No-Path DAO to (B) and regular DAO to
   (C).

1.2. Cases when No-Path DAO may be used

   There are following cases in which a node switches its parent and may
   employ No-Path DAO messaging:

   Case I: Current parent becomes unavailable because of transient or
   permanent link or parent node failure.

   Case II: The node finds a better parent node i.e. the metrics of
   another parent is better than its current parent.

   Case III: The node switches to a new parent whom it "thinks" has a
   better metric but does not in reality.

   The usual steps of operation when the node switches the parent is
   that the node sends a No-Path DAO message via its current parent to
   invalidate its current route and subsequently it tries to establish a
   new routing path by sending a new DAO via its new parent.



Jadhav, et al.         Expires December 27, 2016                [Page 4]


INTERNET DRAFT      draft-jadhav-roll-no-path-dao-01       June 27, 2016


1.3. Why No-Path DAO is important?

   Nodes in LLNs may be resource constrained. There is limited memory
   available and routing entry records are the one of the primary
   elements occupying dynamic memory in the nodes. Route invalidation
   helps 6LR nodes to decide which entries could be discarded to better
   achieve resource utilization in case of contention. Thus it becomes
   necessary to have efficient route invalidation mechanism. Also note
   that a single parent switch may result in a "sub-tree" switching from
   one parent to another. Thus the route invalidation needs to be done
   on behalf of the sub-tree and not the switching node alone. In the
   above example, when Node (D) switches parent, the route invalidation
   needs to be done for (D), (E) and (F). Thus without efficient route
   invalidation, a 6LR may have to hold a lot of unwanted route entries.

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

   Common Ancestor node: 6LR node which is the first common node on the
   old and new path for the child node.

   Current parent: Parent 6LR node before switching to the new path

   New parent: Parent 6LR node after switching to the new path

   NPDAO: No-Path DAO. A DAO message which has target with lifetime 0.

   Reverse NPDAO: A No-Path DAO message which traverses downstream in
   the network.

   Regular DAO: A DAO message with non-zero lifetime.

   This document also uses terminology described in [RFC6550].

2. Problems with current No-Path DAO messaging

   We will confront the following problems when using the current NP-DAO
   messaging.

2.1. Lost NP-DAO due to Link break to the previous parent

   When the node switches its parent, the NPDAO is to be sent via its
   previous parent and a regular DAO via its new parent. In cases where
   the node switches its parent because of transient or permanent parent
   link/node failure then the NPDAO message is bound to fail. [RFC6550]



Jadhav, et al.         Expires December 27, 2016                [Page 5]


INTERNET DRAFT      draft-jadhav-roll-no-path-dao-01       June 27, 2016


   assumes communication link with the previous parent for No-Path DAO
   messaging.

   [RFC6550] mentions use of route lifetime to remove unwanted routes in
   case the routes could not be refreshed. But route lifetimes in case
   of LLNs could be substantially high and thus the route entries would
   be stuck for long.

2.2. Invalidate routes to dependent nodes of the switching node

   No-path DAO is sent by the node who has switched the parent but it
   does not work for the dependent child nodes below it. The
   specification does not specify how route invalidation will work for
   sub-childs, resulting in stale routing entries on behalf of the sub-
   childs on the previous route. The only way for 6LR to invalidate the
   route entries for dependent nodes would be to use route lifetime
   expiry which could be substantially high for LLNs. In the example
   topology, when Node (D) switches its parent, Node (D) generates an
   NPDAO on its behalf. Post switching, Node (D) transmits a DIO with
   incremented DTSN so that child nodes, node (E) and (F), generate DAOs
   to trigger route update on the new path for themselves. There is no
   NPDAO generated by these child nodes through the previous path
   resulting in stale entries on nodes (B) and (G) for nodes (E) and
   (F).

2.3. Route downtime caused by asynchronous operation of NPDAO and DAO

   A switching node may generate both an NPDAO and DAO via two different
   paths at almost the same time. There is a possibility that an NPDAO
   generated may invalidate the previous route and the regular DAO sent
   via the new path gets lost on the way. This may result in route
   downtime thus impacting downward traffic for the switching node. In
   the example topology, consider Node (D) switches from parent (B) to
   (C) because the metrics of the path via (C) are better. Note that the
   previous path via (B) may still be available (albeit at relatively
   bad metrics). An NPDAO sent from previous route may invalidate the
   existing route whereas there is no way to determine whether the new
   DAO has successfully updated the route entries on the new path.

   An implementation technique to avoid this problem is to further delay
   the route invalidation by a fixed time interval after receiving an
   NPDAO, considering the time taken for the new path to be established.
   Coming up with such a time interval is tricky since the new route may
   also not be available and it may subsequently require more parent
   switches to establish a new path.

3. Requirements for the No-Path DAO Optimization




Jadhav, et al.         Expires December 27, 2016                [Page 6]


INTERNET DRAFT      draft-jadhav-roll-no-path-dao-01       June 27, 2016


   We identify the following requirements for the NP-DAO optimization.

3.1. Req#1: Tolerant to the link failures to the previous parents.

   When the switching node send the NP-DAO message to the previous
   parent, it is normal that the link to the previous parent is prone to
   failure.  Therefore, it is required that the NP-DAO message MUST be
   tolerant to the link failure during the switching.

3.2. Req#2: Support of removal of entries to the dependent nodes of the
   switching node.

   While switching the parent node and sending NP-DAO message, it is
   required that the routing entries to the dependent nodes of the
   switching node will be updated accordingly on the previous parents
   and other relevant upstream nodes.

3.3. Req#3: No disruption of downstream reachability to the node while
   sending NP-DAO.

   While sending the NP-DAO and DAO messages, it is possible that the
   NP-DAO successfully invalidates the previous path, while the newly
   sent DAO gets lost (new path not set up successfully). This will
   result into downstream unreachability to the current switching node.
   Therefore, it is desirable that the NP-DAO is synchronized with the
   DAO to avoid the risk of routing downtime.

4.  Existing Solution

4.1. NP-DAO can be generated by the parent node who detects link failure
   to the child

   RPL [RFC6550] states mechanisms which could be utilized to clear DAO
   states in a sub-DODAG. [RFC6550] Section 11.2.2.3 states "With DAO
   inconsistency loop recovery, a packet can be used to recursively
   explore and clean up the obsolete DAO states along a sub-DODAG."

   Thus in the sample topology in Figure 1, when Node (B) detects link
   failure to (D), (B) has an option of generating an NP-DAO on behalf
   of Node (D) and its sub-childs, (E) and (F).

   This section explains why generation of an NP-DAO in such cases may
   not function as desired. Primarily the DAO state information in the
   form of Path Sequence plays a major role here. Every target is
   associated with a Path Sequence number which relates to the latest
   state of the target. [RFC6550] Section 7.1 explains the semantics of
   Path Sequence number. The target node increments the Path Sequence
   number every time it generates a new DAO. The router nodes en-route



Jadhav, et al.         Expires December 27, 2016                [Page 7]


INTERNET DRAFT      draft-jadhav-roll-no-path-dao-01       June 27, 2016


   utilize this Path Sequence number to decide the freshness of target
   information. If a non-target node has to generate an NP-DAO then it
   could use following two possibilities with Path Sequence number:

   Let the Path Sequence number of old regular DAO that flowed through
   (B) be x. The subsequent regular DAO generated by Node (D) will have
   sequence number x+1.

   i. Node (B) uses the previous Path Sequence number from the regular
   DAO i.e. NP-DAO(pathseq=x)

   ii. Node (B) increments the Path Sequence number i.e. NP-
   DAO(pathseq=x+1)

   In case i, the NP-DAO(pathseq=x) will be dropped by all the
   intermediate nodes since the semantics of Path Sequence number
   dictates that any DAO with an older Path Sequence number be dropped.

   In case ii, there is a risk that the NP-DAO(pathseq=x+1) traverses up
   the DODAG and invalidates all the routes till the root and then the
   regular DAO(pathseq=x+1) from the target traverses upwards. In this
   case the regular DAO(pathseq=x+1) will be dropped from common
   ancestor node to the root. This will result in route downtime.

   Another problem with this scheme is its dependence on the upstream
   neighbor to detect that the downstream neighbor is unavailable. There
   are two possibilities by which such a detection might be put to work:

   i. There is P2P traffic from the previous sub-DODAG to any of nodes
   in the sub-tree which has switched the path. In the above example,
   lets consider that Node (G) has P2P traffic for either of nodes (D),
   (E), or (F). In this case, Node (B) will detect forwarding error
   while forwarding the packets from Node (B) to (D). But dependence on
   P2P traffic may not be an optimal way to solve this problem
   considering the reactive approach of the scheme. The P2P traffic
   pattern might be sparse and thus such a detection might kick-in too
   late.

   ii. The other case is where Node (B) explicitly employs some
   mechanism to probe directly attached downstream child nodes. Such
   kind of schemes are seldom used.

4.2. NP-DAO can be generated once the link is restored to the previous
   parent.

   This scheme solves a specific scenario of transient links. The child
   node can detect that the connection to previous parent is restored
   and then transmit an NP-DAO to the previous parent to invalidate the



Jadhav, et al.         Expires December 27, 2016                [Page 8]


INTERNET DRAFT      draft-jadhav-roll-no-path-dao-01       June 27, 2016


   route. This scheme is stateful, thus requires more memory and solves
   a specific scenario.

5.  Security Considerations

   This draft is a problem statement, and therefore, does not introduce
   any new security risks.


6.  IANA Considerations

   Not applicable to this document.

7.  Acknowledgements

   We would like to thank Cenk Gundogan, Simon Duquennoy and Pascal
   Thubert for their review and insightful comments.

8.  References

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

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

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

8.2. Informative References

    [RFC5548] Dohler, M., Ed., Watteyne, T., Ed., Winter, T., Ed., and
              D. Barthel, Ed., "Routing Requirements for Urban Low-Power
              and Lossy Networks", RFC 5548, May 2009.

Authors' Addresses

   Rahul Arvind Jadhav
   Huawei Tech,
   Kundalahalli Village,



Jadhav, et al.         Expires December 27, 2016                [Page 9]


INTERNET DRAFT      draft-jadhav-roll-no-path-dao-01       June 27, 2016


   Bangalore, India

   EMail: rahul.jadhav@huawei.com

   Rabi Narayan Sahoo
   Huawei Tech,
   Kundalahalli Village,
   Bangalore, India

   EMail: rabinarayans@huawei.com

   Zhen Cao
   Huawei Tech,
   Beijing, China

   EMail: zhen.cao@huawei.com

   Hui Deng
   China Mobile,
   Beijing, China

   EMail: denghui@chinamobile.com





























Jadhav, et al.         Expires December 27, 2016               [Page 10]


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