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, . [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, . [RFC6552] Thubert, P., Ed., "Objective Function Zero for the Routing Protocol for Low-Power and Lossy Networks (RPL)", RFC 6552, March 2012, . [RFC6719] Gnawali, O. and P. Levis, "The Minimum Rank with Hysteresis Objective Function", RFC 6719, September 2012, . 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, . [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, . 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]