Skip to main content

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

The information below is for an old version of the document.
Document Type
This is an older version of an Internet-Draft whose latest revision state is "Replaced".
Authors Rahul Jadhav , Rabi Narayan Sahoo , Zhen Cao , DENG Hui
Last updated 2016-02-24
Replaced by draft-jadhav-roll-efficient-npdao
RFC stream (None)
Formats
Stream Stream state (No stream defined)
Consensus boilerplate Unknown
RFC Editor Note (None)
IESG IESG state I-D Exists
Telechat date (None)
Responsible AD (None)
Send notices to (None)
draft-jadhav-roll-no-path-dao-ps-00
ROLL WG                                                        R. Jadhav
INTERNET-DRAFT                                                  R. Sahoo
Intended Status: Informational                                    Z. Cao
Expires: August 8, 2016                                      Huawei Tech
                                                                 H. Deng
                                                            China Mobile
                                                       February 25, 2016

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

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 August 8, 2016                 [Page 1]
INTERNET DRAFT      draft-jadhav-roll-no-path-dao-00   February 25, 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.  Security Considerations  . . . . . . . . . . . . . . . . . . .  7
   5.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . .  7
   6.  References . . . . . . . . . . . . . . . . . . . . . . . . . .  7
     6.1. Normative References  . . . . . . . . . . . . . . . . . . .  7
     6.2. Informative References  . . . . . . . . . . . . . . . . . .  8
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . .  8

 

Jadhav, et al.           Expires August 8, 2016                 [Page 2]
INTERNET DRAFT      draft-jadhav-roll-no-path-dao-00   February 25, 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 August 8, 2016                 [Page 3]
INTERNET DRAFT      draft-jadhav-roll-no-path-dao-00   February 25, 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 August 8, 2016                 [Page 4]
INTERNET DRAFT      draft-jadhav-roll-no-path-dao-00   February 25, 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 August 8, 2016                 [Page 5]
INTERNET DRAFT      draft-jadhav-roll-no-path-dao-00   February 25, 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 August 8, 2016                 [Page 6]
INTERNET DRAFT      draft-jadhav-roll-no-path-dao-00   February 25, 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.  Security Considerations

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

5.  IANA Considerations

   Not applicable to this document. 

6.  References

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

Jadhav, et al.           Expires August 8, 2016                 [Page 7]
INTERNET DRAFT      draft-jadhav-roll-no-path-dao-00   February 25, 2016

              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.

6.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,
   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 August 8, 2016                 [Page 8]