[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00

ROLL Working Group                                           J. Hou, Ed.
INTERNET-DRAFT                                                 R. Jadhav
Intended Status: Standard Track                                   Z. Luo
Expires: September 13, 2017                          Huawei Technologies
                                                          March 12, 2017


      Optimization of Parent-node Selection in RPL-based Networks
                 draft-hou-roll-rpl-parent-selection-00

Abstract

   This document describes the problems in the DODAG construction of
   RPL-based network including "Thundering Herd" problem and Randomly
   Unbalanced Networking.  The corresponding optimization methods are
   proposed to improve balancing the selection of parent nodes.

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).  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 September 13, 2017.

Copyright Notice

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



Hou, et al             Expires September 13, 2017               [Page 1]


INTERNET DRAFT      Parent Selection in RPL Networks      March 12, 2017


Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  2
     1.1.  Requirements Notation and Terminology  . . . . . . . . . .  3
   2.  DODAG Construction and Objective Functions . . . . . . . . . .  3
   3.  Problems with Current DODAG construction . . . . . . . . . . .  4
     3.1.  Problem 1: "Thundering Herd" Phenomenon  . . . . . . . . .  4
     3.2.  Problem 2: Randomly Unbalanced Network . . . . . . . . . .  5
   4.  Optimized Solution . . . . . . . . . . . . . . . . . . . . . .  6
     4.1.  Solution 1: Increment the ETX_Initial value  . . . . . . .  6
     4.2.  Solution 2: Introducing the Child Node Count Metric  . . .  7
   5.  Security Considerations  . . . . . . . . . . . . . . . . . . .  9
   6.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . .  9
   7.  References . . . . . . . . . . . . . . . . . . . . . . . . . .  9
     7.1.  Normative References . . . . . . . . . . . . . . . . . . .  9
     7.2.  Informative References . . . . . . . . . . . . . . . . . . 10
   8.  Acknowledgments  . . . . . . . . . . . . . . . . . . . . . . . 10
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10

1.  Introduction

   IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL) is a
   route-over distance vector routing protocol for networks in
   constrained conditions such as limited power and bandwidth.  This
   protocol defines a Destination Oriented Directed Acyclic Graph
   (DODAG) to avoid the emergence of loops in the network [RFC 6550].
   The routing procedure is based on an objective function (OF)
   including a set of metrics/constraints.  The selection of the parent
   node in the RPL-based network directly influences the networking
   balance, and particularly, a poor balance causes the frequent
   switches of parent nodes.  During the switching process, the delayed
   communication directly affects the stability of the entire network,
   so networking balance is an important indicator of the stability of
   mesh network.

   In the RPL-based mesh network, due to the lack of balance algorithm,
   a large batch of nodes possibly select the same parent node and leave
   others empty, turning this focused parent node to be a forwarding
   point.  A higher rate of transmission failure will result in a sharp
   increment in RANK, which triggers all child nodes to re-select and
   switch their parent node, and so on, causing frequent switching of
   the parent node.  This phenomenon is particularly frequent at the
   beginning of networking that greatly decrements the efficiency of
   networking and communication stability.  Therefore, the mechanism to
   select the parent node, making 6LoWPAN reach a balanced mesh network,
   is an urgent problem to be solved.

   This document points out the problems associated with the RPL-based



Hou, et al             Expires September 13, 2017               [Page 2]


INTERNET DRAFT      Parent Selection in RPL Networks      March 12, 2017


   networking, and proposes solutions for optimizing the balance of
   parent selection problems.  Modifications are incrementing the RANK
   default value and introducing a new metric called "Child Node Count".

1.1.  Requirements Notation and Terminology

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

   Below are the terms used in this document:

   6LBR: 6Lo Border Router

   6LN: 6Lo Node

   CNC: Child Node Count

   DAO: Destination Advertisement Object

   DIO: DODAG Information Object

   ETX: Expected Transmission Time

   MOP: Mode of Operation

   MRHOF: Minimum Rank with Hysteresis Objective Function

   OP0: Objective Function Zero

   RSSI: Received Signal Strength Indicator

2.  DODAG Construction and Objective Functions

   In general, an RPL-based network consists of three types of nodes:
   root node, connecting to another network as a gateway; router,
   forwarding topology information and data packets to their neighbors;
   leaf node, only joining a DODAG as an end member.  The construction
   of a DODAG starts at the root node, through the routers, down to the
   leaf nodes.  The root node broadcasts to its sub-nodes the DODAG
   Information Object (DIO) messages that contain the RANK information.
   Once receiving DIO messages, a sub-node chooses the node with the
   minimum RANK as its appropriate parent node.  Afterwards, the routers
   will compute their own RANK according to the Objective Function (OF),
   update the DIO message, and forward to their neighbors.

   Objective Function Zero (OF0) is designed as a default OF that allows



Hou, et al             Expires September 13, 2017               [Page 3]


INTERNET DRAFT      Parent Selection in RPL Networks      March 12, 2017


   interoperation between implementations in a wide spectrum of use
   cases [RFC 6552].  OF0 specifies that a node calculates its own RANK
   R(N) according to the following equation:

   R(N) = R(P) + rank_increase      (1)

   where rank_increase = (Rf * Sp + Sr) * MinHopRankIncrease (Rf,
   Rank_Factor; Sp, Step_of_Rank; Sr, Stretch_of_Rank).  R(P) is the
   RANK of the parent node.

   Apart from OF0, the Minimum Rank with Hysteresis Objective Function
   (MRHOF) is another OF that selects routes that minimize a metric.
   One common metric used in OF is the Expected Transmission Count
   (ETX), indicating the number of transmissions a node expects to make
   to a destination in order to successfully deliver a packet [RFC
   6551].  When MRHOF uses ETX as its metric, nodes locally compute the
   ETX of links to its neighbors and add this value to their advertised
   Rank to compute the associated Rank of routes [RFC 6719].  In this
   case, the calculation of RANK can be simplified to be equation

   R(N) = R(P) + ETX(N) * 128       (2)

   where ETX(N) is the ETX of links to its parent node.  The ETX value
   normally follows an update formula

   ETX = ETX_Old * 0.9 + ETX_New * 0.1      (3)

   where ETX_Old is the previous ETX value, and ETX_New is calculated by
   ETX= 1 / (Df * Dr) in which Df is the measured probability that a
   packet is received by the neighbor and Dr is the measured probability
   that the acknowledgment packet is successfully received [RFC 6551].
   Once a node joins an RPL network with a default value ETX(N), e.g.
   1*R, the ETX gradually converges to the actual value after several
   times of update.

3.  Problems with Current DODAG construction

3.1.  Problem 1: "Thundering Herd" Phenomenon

   When a node joins the RPL-based network (such as 6LN_New in Figure
   1), the transmission path may be better than other nodes because the
   Default_Rank_Increase is 3*256, calculated by equation (1) with the
   following default values specified in [RFC 6552]:

   DEFAULT_MIN_HOP_RANK_INCREASE = 256

   DEFAULT_STEP_OF_RANK: 3




Hou, et al             Expires September 13, 2017               [Page 4]


INTERNET DRAFT      Parent Selection in RPL Networks      March 12, 2017


   DEFAULT_RANK_STRETCH: 0

   DEFAULT_RANK_FACTOR: 1

   Suppose the RANK of 6LN in Figure 1 is much higher than 4*256 and
   meets the requirement of parent switching when 6LN_New joins.  Then
   once 6LN_New broadcasts the DIO messages including the RANK value of
   4*256 (1*256 for Root_Rank; 3*256 for Rank_Increase), it may trigger
   a switch of numerous child nodes (circles in Figure 1) from their
   original parent nodes.  Note that the dashed box depicted in Figure 1
   is the common coverage of 6LN and 6LN_New.  So once a new node joins
   a network with a small RANK default value, it may suddenly attract
   numerous sub-nodes, impacting on the stability of the network.  This
   phenomenon is called "Thundering Herd".

                                6LBR
                                 /\
                                /  \
                               /    \
                             6LN     \
                             /|\   6LN_New
                            / | \    /|\
                         + - - - - - - - - +
                         | o o o o o o o o | Numerous
                         |   o  o o  o  o  |
                         |  o  o   o  o  o |   6LNs
                         | o   o    o    o |
                         + - - - - - - - - +

         Figure 1: Example of Network Topology of "Thundering Herd"

3.2.  Problem 2: Randomly Unbalanced Network

   Although the RANK in DIO messages reflects various features of the
   network quality (e.g. Hop_Count, Latency, ETX), there is another
   issue waiting to be solved: balancing the parent selection among
   nodes with the same RANK value.  Currently in this case a node
   randomly chooses one as its parent node from the candidate parents
   with the same RANK, which gives the possibility of unbalanced
   networking.  As depicted in Figure 2, the RANK of node A, B and C are
   supposed to be equal, but node B by chance dominates in the number of
   child nodes even though they share the common coverage (dashed
   square).  It is a waste of resource that Node A is left empty while
   reachable for the sub-nodes.  After a long period of time, the
   network only achieves a relative balance which is easy to be broken
   when new nodes join in.

   This problem is particularly serious when the unbalanced networking



Hou, et al             Expires September 13, 2017               [Page 5]


INTERNET DRAFT      Parent Selection in RPL Networks      March 12, 2017


   happens near the root node and above a large number of sub-nodes.
   Suppose in Figure 2 there are numerous child nodes connected to node
   D, E, F, G, and H, which put high load pressure on node B and C.  In
   this case, overload and traffic block are likely to happen near the
   root, which further forces the network structure conversion.  Node D,
   E, F may switch their parent node after network reconstruction but
   the best solution is achieving a balance in the parent selection at
   the beginning of the networking.

                                6LBR
                                 /|\
                                / | \
                               /  |  \
                              /   |   \
                             A    B    C
                           + - - - - - - +
                           |     /|\  /| |
                           |    / | \/ | |
                           |   /  | /\ | |
                           |  D   E/  F| |
                           |      /    | |
                           |     H     G |
                           + - - - - - - +

          Figure 2: Example of Randomly Unbalanced Network Topology

4.  Optimized Solution

4.1.  Solution 1: Increment the ETX_Initial value

   In order to reduce the impact of the Thundering Herd phenomenon in
   the network, the Default_Step_of_Rank value defined in OF0 SHOULD per
   this document be incremented to

   DEFAULT_STEP_OF_RANK: 4

   So the Default_Rank_Increase is 4*256, and then based on the actual
   transmission result, the RANK gradually approaches the actual value.
   In this way, a new node joining the RPL network is initially set to
   be with a larger RANK default value.  If transmissions through this
   node are of high quality, the RANK of this node will decrement
   gradually and attract child nodes one by one, which reduces the
   appearance of the Thundering Herd phenomenon.  It is worthwhile
   noting that this solution is particularly applicable for the
   scenarios with numerous nodes and high node density.

   This modification is also suitable for the MRHOF.  Take ETX metric
   for an example: the default ETX(N) according to the modification



Hou, et al             Expires September 13, 2017               [Page 6]


INTERNET DRAFT      Parent Selection in RPL Networks      March 12, 2017


   SHALL be set to 8, which gives R(N) = R(P) + 8*128 according to
   equation (2).  The high initial RANK lowers the possibility of
   Thundering Herd phenomenon while afterwards the RANK gradually
   converges to the actual value according to equation (3).

4.2.  Solution 2: Introducing the Child Node Count Metric

   In order to optimize the randomly unbalanced networking, this
   document proposes a method: introducing the number of child nodes as
   a new metric/constraint in the DAG Metric Container, which can be
   included in the Option field in the DIO message.  The newly added
   information is 2 octets named by Child Node Count (CNC) which is per
   this document defined in the DAG Metric Container.  The Routing
   Metric/Constraint Type is per this document RECOMMENDED to be value
   9.

   The Child Node Count (CNC) object is used to provide information
   related to the number of child nodes in the DIO source node, and may
   be used as a metric or as constraint.

   The CNC object MAY be present in the DAG Metric Container.  There
   MUST NOT be more than one CNC object as a constraint per DAG Metric
   Container, and there MUST NOT be more than one CNC object as a metric
   per DAG Metric Container.

   The format of the CNC object body is as follows:

                    0                   1
                    0 1 2 3 4 5 6 7 8 9 0 1 2 3
                   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                   |  (sub-object) .....
                   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+

             Figure 3: Child Node Count Object Body Format

                   0                   1
                   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
                  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                  |      CNC      |    MAX_CNC    |
                  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

             Figure 4: Child Node Count Sub-Object Format

   CNC: 8 bits.  The Child Node Count is encoded in 8 bits in unsigned
   integer format, expressed in number count, representing the number of
   child nodes.

   MAX_CNC: 8 bits.  The Maximum Child Node Count is encoded in 8 bits



Hou, et al             Expires September 13, 2017               [Page 7]


INTERNET DRAFT      Parent Selection in RPL Networks      March 12, 2017


   in unsigned integer format, expressed in number count, representing
   the maximum number of child nodes allowed in the neighbor cache.

   The CNC field gives the number of child nodes while together with the
   MAX_CNC field, sub-nodes are able to know the capacity of the
   candidate parent nodes, minimizing the need of NACK messages.  The
   CNC object may be used as a constraint or a path metric.  For
   example, one may want the CNC not to exceed some value.  In this
   case, the CNC object common header indicates that the provided value
   relates to a constraint.  In another example, the CNC object may be
   used as an aggregated additive metric where the value is updated
   along the path to reflect the number of child nodes along the path.

   To solve the Randomly Unbalanced Network addressed in problem 2, this
   document proposes a optimization: using a combined metrics of ETX and
   CNC in the parent selection process.  In this method, Prec field in
   the Routing Metric/Constraint Object is used with the following
   precedence: ETX > CNC, e.g. Prec of ETX is set to 0 and Prec of CNC
   is 1.  In this case, the DAG Metric Container carries two Routing
   Metric/Constraint objects: one is an ETX metric object with header
   (C=0, O=0, A=00, R=0) and the second one is a Child Node Count object
   with header (C=0, O=0, A=00, R=0).  Since Prec of ETX is set to be 0,
   which gives a higher priority, then nodes first choose the candidate
   parent nodes with the best link quality according to ETX.
   Afterwards, among the candidate parent nodes, the node with minimum
   CNC is selected to be the parent node.  Note that this method is
   applicable for the storing mode of operation in which the nodes
   stores the information of their neighbors and thus are able to
   calculate the number of child nodes.  In addition, when the candidate
   parent nodes contain both the same ETX and CNC, the child node SHOUD
   randomly choose one as the parent node among them.

   This method is applicable for the storing mode of Mode of Operation
   (MOP) in which the Destination Advertisement Object (DAO) message is
   unicast from the child to the selected parent(s).  For the non-
   storing mode, the CNC metric/constraint SHOULD NOT be used in the DIO
   messages, or if used, the CNC value MUST be set to 0.  It is worthy
   to note that [draft-jadhav-lwig-nbr-mgmt-policy-00] gives a
   conceptual idea of this method in its section 2.5.3 while this
   document proposes the standard method to solve the unbalanced
   networking problem.

   In the wireless networking scenarios, it would be better to take the
   wireless signal strength into consideration in the parent selection
   process, otherwise the optimally balanced network may lead to worse
   network communication quality for some child nodes.  The wireless
   signal strength can be quantified by the Received Signal Strength
   Indicator (RSSI).  This element can be added in the parent selection



Hou, et al             Expires September 13, 2017               [Page 8]


INTERNET DRAFT      Parent Selection in RPL Networks      March 12, 2017


   process with the priority: ETX > RSSI > CNC.  Note that the selection
   in the RSSI processes are not to choose the best value but to filter
   out candidate parent nodes according to the ranges (e.g. -80dB < RSSI
   <20dB).  The RSSI value can be measured by the child nodes thus no
   additional modification is needed in the DAG Metric Container.  So
   the parent node selection in wireless mesh networks can be processed
   as follows: Nodes in the network obtain the identity of candidate
   parent nodes, the number of child nodes, and the RANK.  A filtering
   process takes place in the candidate parent nodes based on the
   identification and the RANK.  Then these candidate parent nodes are
   filtered again according to the wireless communication quality index,
   RSSI.  Finally, the candidate parent node with the minimum number of
   child nodes is determined as the target parent node in the network.
   Note that the RANK of each candidate parent node is the average value
   based on the current ETX, which is set to be greater than the default
   path coefficient R.  The RANK of a node describes the total path to
   the border router (BR), which is determined by the RANK of the parent
   node together with the current ETX.

5.  Security Considerations

   This document has no security consideration beyond those in [RFC
   6550], [RFC 6551], [RFC 6552] and [RFC 6719].

6.  IANA Considerations

   This document creates an IANA registry for the Routing
   Metric/Constraint Type. The assigned value is shown below in
   comparison with the existing values:

   Value   Meaning                    Reference

     1     Node State and Attribute   RFC6551
     2     Node Energy                RFC6551
     3     Hop Count                  RFC6551
     4     Link Throughput            RFC6551
     5     Link Latency               RFC6551
     6     Link Quality Level         RFC6551
     7     Link ETX                   RFC6551
     8     Link Color                 RFC6551
     9     Child Node Count(*)        This document

7.  References

7.1.  Normative References

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



Hou, et al             Expires September 13, 2017               [Page 9]


INTERNET DRAFT      Parent Selection in RPL Networks      March 12, 2017


             10.17487/RFC2119, March 1997, <http://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, March 2012,
             <http://www.rfc-editor.org/info/rfc6550>.

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

   [RFC6719] Gnawali, O. and P. Levis, "The Minimum Rank with Hysteresis
             Objective Function", RFC 6719, September 2012,
             <http://www.rfc-editor.org/info/rfc6719>.

7.2.  Informative References

   [draft-jadhav-lwig-nbr-mgmt-policy-00] Jadhav, R., Sahoo, R.,
             Duquennoy, S., and J. Eriksson, "Neighbor Management Policy
             for 6LoWPAN", draft-jadhav-lwig-nbr-mgmt-policy-00, January
             2017, <https://tools.ietf.org/html/draft-jadhav-lwig-nbr-
             mgmt-policy-00>.

   [RFC6551] Vasseur, J., 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,
             <http://www.rfc-editor.org/info/rfc6551>.

8.  Acknowledgments

   Authors wish to thank Yizhou li and Yuefeng Wu for their valuable
   comments and contributions.

Authors' Addresses

   Jianqiang Hou (editor)
   Huawei Technologies
   101 Software Avenue,
   Nanjing 210012
   China

   Phone: +86-15852944235
   Email: houjianqiang@huawei.com


   Rahul Arvind Jadhav



Hou, et al             Expires September 13, 2017              [Page 10]


INTERNET DRAFT      Parent Selection in RPL Networks      March 12, 2017


   Huawei Technologies
   Kundalahalli Village, Whitefield,
   Bangalore, Karnataka  560037
   India

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


   Zhenhui Luo
   Huawei Technologies
   Bantian, Longgang District,
   Shenzhen 518129
   China

   Phone: +86-18680331295
   Email: luozhenhui@huawei.com


































Hou, et al             Expires September 13, 2017              [Page 11]


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