idnits 2.17.1 draft-hou-roll-rpl-parent-selection-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (March 12, 2017) is 2573 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: 'RFC 6550' is mentioned on line 75, but not defined == Missing Reference: 'RFC 6552' is mentioned on line 407, but not defined == Missing Reference: 'RFC 6719' is mentioned on line 407, but not defined == Missing Reference: 'RFC 6551' is mentioned on line 407, but not defined == Unused Reference: 'RFC6550' is defined on line 436, but no explicit reference was found in the text == Unused Reference: 'RFC6552' is defined on line 442, but no explicit reference was found in the text == Unused Reference: 'RFC6719' is defined on line 446, but no explicit reference was found in the text == Unused Reference: 'RFC6551' is defined on line 458, but no explicit reference was found in the text Summary: 0 errors (**), 0 flaws (~~), 9 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 ROLL Working Group J. Hou, Ed. 3 INTERNET-DRAFT R. Jadhav 4 Intended Status: Standard Track Z. Luo 5 Expires: September 13, 2017 Huawei Technologies 6 March 12, 2017 8 Optimization of Parent-node Selection in RPL-based Networks 9 draft-hou-roll-rpl-parent-selection-00 11 Abstract 13 This document describes the problems in the DODAG construction of 14 RPL-based network including "Thundering Herd" problem and Randomly 15 Unbalanced Networking. The corresponding optimization methods are 16 proposed to improve balancing the selection of parent nodes. 18 Status of this Memo 20 This Internet-Draft is submitted to IETF in full conformance with the 21 provisions of BCP 78 and BCP 79. 23 Internet-Drafts are working documents of the Internet Engineering 24 Task Force (IETF). Note that other groups may also distribute 25 working documents as Internet-Drafts. The list of current Internet- 26 Drafts is at http://datatracker.ietf.org/drafts/current/. 28 Internet-Drafts are draft documents valid for a maximum of six months 29 and may be updated, replaced, or obsoleted by other documents at any 30 time. It is inappropriate to use Internet-Drafts as reference 31 material or to cite them other than as "work in progress." 33 This Internet-Draft will expire on September 13, 2017. 35 Copyright Notice 37 Copyright (c) 2017 IETF Trust and the persons identified as the 38 document authors. All rights reserved. 40 This document is subject to BCP 78 and the IETF Trust's Legal 41 Provisions Relating to IETF Documents 42 (http://trustee.ietf.org/license-info) in effect on the date of 43 publication of this document. Please review these documents 44 carefully, as they describe your rights and restrictions with respect 45 to this document. Code Components extracted from this document must 46 include Simplified BSD License text as described in Section 4.e of 47 the Trust Legal Provisions and are provided without warranty as 48 described in the Simplified BSD License. 50 Table of Contents 52 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2 53 1.1. Requirements Notation and Terminology . . . . . . . . . . 3 54 2. DODAG Construction and Objective Functions . . . . . . . . . . 3 55 3. Problems with Current DODAG construction . . . . . . . . . . . 4 56 3.1. Problem 1: "Thundering Herd" Phenomenon . . . . . . . . . 4 57 3.2. Problem 2: Randomly Unbalanced Network . . . . . . . . . . 5 58 4. Optimized Solution . . . . . . . . . . . . . . . . . . . . . . 6 59 4.1. Solution 1: Increment the ETX_Initial value . . . . . . . 6 60 4.2. Solution 2: Introducing the Child Node Count Metric . . . 7 61 5. Security Considerations . . . . . . . . . . . . . . . . . . . 9 62 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 63 7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 9 64 7.1. Normative References . . . . . . . . . . . . . . . . . . . 9 65 7.2. Informative References . . . . . . . . . . . . . . . . . . 10 66 8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 10 67 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10 69 1. Introduction 71 IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL) is a 72 route-over distance vector routing protocol for networks in 73 constrained conditions such as limited power and bandwidth. This 74 protocol defines a Destination Oriented Directed Acyclic Graph 75 (DODAG) to avoid the emergence of loops in the network [RFC 6550]. 76 The routing procedure is based on an objective function (OF) 77 including a set of metrics/constraints. The selection of the parent 78 node in the RPL-based network directly influences the networking 79 balance, and particularly, a poor balance causes the frequent 80 switches of parent nodes. During the switching process, the delayed 81 communication directly affects the stability of the entire network, 82 so networking balance is an important indicator of the stability of 83 mesh network. 85 In the RPL-based mesh network, due to the lack of balance algorithm, 86 a large batch of nodes possibly select the same parent node and leave 87 others empty, turning this focused parent node to be a forwarding 88 point. A higher rate of transmission failure will result in a sharp 89 increment in RANK, which triggers all child nodes to re-select and 90 switch their parent node, and so on, causing frequent switching of 91 the parent node. This phenomenon is particularly frequent at the 92 beginning of networking that greatly decrements the efficiency of 93 networking and communication stability. Therefore, the mechanism to 94 select the parent node, making 6LoWPAN reach a balanced mesh network, 95 is an urgent problem to be solved. 97 This document points out the problems associated with the RPL-based 98 networking, and proposes solutions for optimizing the balance of 99 parent selection problems. Modifications are incrementing the RANK 100 default value and introducing a new metric called "Child Node Count". 102 1.1. Requirements Notation and Terminology 104 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 105 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 106 "OPTIONAL" in this document are to be interpreted as described in 107 [RFC2119]. 109 Below are the terms used in this document: 111 6LBR: 6Lo Border Router 113 6LN: 6Lo Node 115 CNC: Child Node Count 117 DAO: Destination Advertisement Object 119 DIO: DODAG Information Object 121 ETX: Expected Transmission Time 123 MOP: Mode of Operation 125 MRHOF: Minimum Rank with Hysteresis Objective Function 127 OP0: Objective Function Zero 129 RSSI: Received Signal Strength Indicator 131 2. DODAG Construction and Objective Functions 133 In general, an RPL-based network consists of three types of nodes: 134 root node, connecting to another network as a gateway; router, 135 forwarding topology information and data packets to their neighbors; 136 leaf node, only joining a DODAG as an end member. The construction 137 of a DODAG starts at the root node, through the routers, down to the 138 leaf nodes. The root node broadcasts to its sub-nodes the DODAG 139 Information Object (DIO) messages that contain the RANK information. 140 Once receiving DIO messages, a sub-node chooses the node with the 141 minimum RANK as its appropriate parent node. Afterwards, the routers 142 will compute their own RANK according to the Objective Function (OF), 143 update the DIO message, and forward to their neighbors. 145 Objective Function Zero (OF0) is designed as a default OF that allows 146 interoperation between implementations in a wide spectrum of use 147 cases [RFC 6552]. OF0 specifies that a node calculates its own RANK 148 R(N) according to the following equation: 150 R(N) = R(P) + rank_increase (1) 152 where rank_increase = (Rf * Sp + Sr) * MinHopRankIncrease (Rf, 153 Rank_Factor; Sp, Step_of_Rank; Sr, Stretch_of_Rank). R(P) is the 154 RANK of the parent node. 156 Apart from OF0, the Minimum Rank with Hysteresis Objective Function 157 (MRHOF) is another OF that selects routes that minimize a metric. 158 One common metric used in OF is the Expected Transmission Count 159 (ETX), indicating the number of transmissions a node expects to make 160 to a destination in order to successfully deliver a packet [RFC 161 6551]. When MRHOF uses ETX as its metric, nodes locally compute the 162 ETX of links to its neighbors and add this value to their advertised 163 Rank to compute the associated Rank of routes [RFC 6719]. In this 164 case, the calculation of RANK can be simplified to be equation 166 R(N) = R(P) + ETX(N) * 128 (2) 168 where ETX(N) is the ETX of links to its parent node. The ETX value 169 normally follows an update formula 171 ETX = ETX_Old * 0.9 + ETX_New * 0.1 (3) 173 where ETX_Old is the previous ETX value, and ETX_New is calculated by 174 ETX= 1 / (Df * Dr) in which Df is the measured probability that a 175 packet is received by the neighbor and Dr is the measured probability 176 that the acknowledgment packet is successfully received [RFC 6551]. 177 Once a node joins an RPL network with a default value ETX(N), e.g. 178 1*R, the ETX gradually converges to the actual value after several 179 times of update. 181 3. Problems with Current DODAG construction 183 3.1. Problem 1: "Thundering Herd" Phenomenon 185 When a node joins the RPL-based network (such as 6LN_New in Figure 186 1), the transmission path may be better than other nodes because the 187 Default_Rank_Increase is 3*256, calculated by equation (1) with the 188 following default values specified in [RFC 6552]: 190 DEFAULT_MIN_HOP_RANK_INCREASE = 256 192 DEFAULT_STEP_OF_RANK: 3 193 DEFAULT_RANK_STRETCH: 0 195 DEFAULT_RANK_FACTOR: 1 197 Suppose the RANK of 6LN in Figure 1 is much higher than 4*256 and 198 meets the requirement of parent switching when 6LN_New joins. Then 199 once 6LN_New broadcasts the DIO messages including the RANK value of 200 4*256 (1*256 for Root_Rank; 3*256 for Rank_Increase), it may trigger 201 a switch of numerous child nodes (circles in Figure 1) from their 202 original parent nodes. Note that the dashed box depicted in Figure 1 203 is the common coverage of 6LN and 6LN_New. So once a new node joins 204 a network with a small RANK default value, it may suddenly attract 205 numerous sub-nodes, impacting on the stability of the network. This 206 phenomenon is called "Thundering Herd". 208 6LBR 209 /\ 210 / \ 211 / \ 212 6LN \ 213 /|\ 6LN_New 214 / | \ /|\ 215 + - - - - - - - - + 216 | o o o o o o o o | Numerous 217 | o o o o o | 218 | o o o o o | 6LNs 219 | o o o o | 220 + - - - - - - - - + 222 Figure 1: Example of Network Topology of "Thundering Herd" 224 3.2. Problem 2: Randomly Unbalanced Network 226 Although the RANK in DIO messages reflects various features of the 227 network quality (e.g. Hop_Count, Latency, ETX), there is another 228 issue waiting to be solved: balancing the parent selection among 229 nodes with the same RANK value. Currently in this case a node 230 randomly chooses one as its parent node from the candidate parents 231 with the same RANK, which gives the possibility of unbalanced 232 networking. As depicted in Figure 2, the RANK of node A, B and C are 233 supposed to be equal, but node B by chance dominates in the number of 234 child nodes even though they share the common coverage (dashed 235 square). It is a waste of resource that Node A is left empty while 236 reachable for the sub-nodes. After a long period of time, the 237 network only achieves a relative balance which is easy to be broken 238 when new nodes join in. 240 This problem is particularly serious when the unbalanced networking 241 happens near the root node and above a large number of sub-nodes. 242 Suppose in Figure 2 there are numerous child nodes connected to node 243 D, E, F, G, and H, which put high load pressure on node B and C. In 244 this case, overload and traffic block are likely to happen near the 245 root, which further forces the network structure conversion. Node D, 246 E, F may switch their parent node after network reconstruction but 247 the best solution is achieving a balance in the parent selection at 248 the beginning of the networking. 250 6LBR 251 /|\ 252 / | \ 253 / | \ 254 / | \ 255 A B C 256 + - - - - - - + 257 | /|\ /| | 258 | / | \/ | | 259 | / | /\ | | 260 | D E/ F| | 261 | / | | 262 | H G | 263 + - - - - - - + 265 Figure 2: Example of Randomly Unbalanced Network Topology 267 4. Optimized Solution 269 4.1. Solution 1: Increment the ETX_Initial value 271 In order to reduce the impact of the Thundering Herd phenomenon in 272 the network, the Default_Step_of_Rank value defined in OF0 SHOULD per 273 this document be incremented to 275 DEFAULT_STEP_OF_RANK: 4 277 So the Default_Rank_Increase is 4*256, and then based on the actual 278 transmission result, the RANK gradually approaches the actual value. 279 In this way, a new node joining the RPL network is initially set to 280 be with a larger RANK default value. If transmissions through this 281 node are of high quality, the RANK of this node will decrement 282 gradually and attract child nodes one by one, which reduces the 283 appearance of the Thundering Herd phenomenon. It is worthwhile 284 noting that this solution is particularly applicable for the 285 scenarios with numerous nodes and high node density. 287 This modification is also suitable for the MRHOF. Take ETX metric 288 for an example: the default ETX(N) according to the modification 289 SHALL be set to 8, which gives R(N) = R(P) + 8*128 according to 290 equation (2). The high initial RANK lowers the possibility of 291 Thundering Herd phenomenon while afterwards the RANK gradually 292 converges to the actual value according to equation (3). 294 4.2. Solution 2: Introducing the Child Node Count Metric 296 In order to optimize the randomly unbalanced networking, this 297 document proposes a method: introducing the number of child nodes as 298 a new metric/constraint in the DAG Metric Container, which can be 299 included in the Option field in the DIO message. The newly added 300 information is 2 octets named by Child Node Count (CNC) which is per 301 this document defined in the DAG Metric Container. The Routing 302 Metric/Constraint Type is per this document RECOMMENDED to be value 303 9. 305 The Child Node Count (CNC) object is used to provide information 306 related to the number of child nodes in the DIO source node, and may 307 be used as a metric or as constraint. 309 The CNC object MAY be present in the DAG Metric Container. There 310 MUST NOT be more than one CNC object as a constraint per DAG Metric 311 Container, and there MUST NOT be more than one CNC object as a metric 312 per DAG Metric Container. 314 The format of the CNC object body is as follows: 316 0 1 317 0 1 2 3 4 5 6 7 8 9 0 1 2 3 318 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 319 | (sub-object) ..... 320 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 322 Figure 3: Child Node Count Object Body Format 324 0 1 325 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 326 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 327 | CNC | MAX_CNC | 328 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 330 Figure 4: Child Node Count Sub-Object Format 332 CNC: 8 bits. The Child Node Count is encoded in 8 bits in unsigned 333 integer format, expressed in number count, representing the number of 334 child nodes. 336 MAX_CNC: 8 bits. The Maximum Child Node Count is encoded in 8 bits 337 in unsigned integer format, expressed in number count, representing 338 the maximum number of child nodes allowed in the neighbor cache. 340 The CNC field gives the number of child nodes while together with the 341 MAX_CNC field, sub-nodes are able to know the capacity of the 342 candidate parent nodes, minimizing the need of NACK messages. The 343 CNC object may be used as a constraint or a path metric. For 344 example, one may want the CNC not to exceed some value. In this 345 case, the CNC object common header indicates that the provided value 346 relates to a constraint. In another example, the CNC object may be 347 used as an aggregated additive metric where the value is updated 348 along the path to reflect the number of child nodes along the path. 350 To solve the Randomly Unbalanced Network addressed in problem 2, this 351 document proposes a optimization: using a combined metrics of ETX and 352 CNC in the parent selection process. In this method, Prec field in 353 the Routing Metric/Constraint Object is used with the following 354 precedence: ETX > CNC, e.g. Prec of ETX is set to 0 and Prec of CNC 355 is 1. In this case, the DAG Metric Container carries two Routing 356 Metric/Constraint objects: one is an ETX metric object with header 357 (C=0, O=0, A=00, R=0) and the second one is a Child Node Count object 358 with header (C=0, O=0, A=00, R=0). Since Prec of ETX is set to be 0, 359 which gives a higher priority, then nodes first choose the candidate 360 parent nodes with the best link quality according to ETX. 361 Afterwards, among the candidate parent nodes, the node with minimum 362 CNC is selected to be the parent node. Note that this method is 363 applicable for the storing mode of operation in which the nodes 364 stores the information of their neighbors and thus are able to 365 calculate the number of child nodes. In addition, when the candidate 366 parent nodes contain both the same ETX and CNC, the child node SHOUD 367 randomly choose one as the parent node among them. 369 This method is applicable for the storing mode of Mode of Operation 370 (MOP) in which the Destination Advertisement Object (DAO) message is 371 unicast from the child to the selected parent(s). For the non- 372 storing mode, the CNC metric/constraint SHOULD NOT be used in the DIO 373 messages, or if used, the CNC value MUST be set to 0. It is worthy 374 to note that [draft-jadhav-lwig-nbr-mgmt-policy-00] gives a 375 conceptual idea of this method in its section 2.5.3 while this 376 document proposes the standard method to solve the unbalanced 377 networking problem. 379 In the wireless networking scenarios, it would be better to take the 380 wireless signal strength into consideration in the parent selection 381 process, otherwise the optimally balanced network may lead to worse 382 network communication quality for some child nodes. The wireless 383 signal strength can be quantified by the Received Signal Strength 384 Indicator (RSSI). This element can be added in the parent selection 385 process with the priority: ETX > RSSI > CNC. Note that the selection 386 in the RSSI processes are not to choose the best value but to filter 387 out candidate parent nodes according to the ranges (e.g. -80dB < RSSI 388 <20dB). The RSSI value can be measured by the child nodes thus no 389 additional modification is needed in the DAG Metric Container. So 390 the parent node selection in wireless mesh networks can be processed 391 as follows: Nodes in the network obtain the identity of candidate 392 parent nodes, the number of child nodes, and the RANK. A filtering 393 process takes place in the candidate parent nodes based on the 394 identification and the RANK. Then these candidate parent nodes are 395 filtered again according to the wireless communication quality index, 396 RSSI. Finally, the candidate parent node with the minimum number of 397 child nodes is determined as the target parent node in the network. 398 Note that the RANK of each candidate parent node is the average value 399 based on the current ETX, which is set to be greater than the default 400 path coefficient R. The RANK of a node describes the total path to 401 the border router (BR), which is determined by the RANK of the parent 402 node together with the current ETX. 404 5. Security Considerations 406 This document has no security consideration beyond those in [RFC 407 6550], [RFC 6551], [RFC 6552] and [RFC 6719]. 409 6. IANA Considerations 411 This document creates an IANA registry for the Routing 412 Metric/Constraint Type. The assigned value is shown below in 413 comparison with the existing values: 415 Value Meaning Reference 417 1 Node State and Attribute RFC6551 418 2 Node Energy RFC6551 419 3 Hop Count RFC6551 420 4 Link Throughput RFC6551 421 5 Link Latency RFC6551 422 6 Link Quality Level RFC6551 423 7 Link ETX RFC6551 424 8 Link Color RFC6551 425 9 Child Node Count(*) This document 427 7. References 429 7.1. Normative References 431 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 432 Requirement Levels", BCP 14, RFC 2119, DOI 433 10.17487/RFC2119, March 1997, . 436 [RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J., 437 Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, 438 JP., and R. Alexander, "RPL: IPv6 Routing Protocol for Low- 439 Power and Lossy Networks", RFC 6550, March 2012, 440 . 442 [RFC6552] Thubert, P., Ed., "Objective Function Zero for the Routing 443 Protocol for Low-Power and Lossy Networks (RPL)", RFC 6552, 444 March 2012, . 446 [RFC6719] Gnawali, O. and P. Levis, "The Minimum Rank with Hysteresis 447 Objective Function", RFC 6719, September 2012, 448 . 450 7.2. Informative References 452 [draft-jadhav-lwig-nbr-mgmt-policy-00] Jadhav, R., Sahoo, R., 453 Duquennoy, S., and J. Eriksson, "Neighbor Management Policy 454 for 6LoWPAN", draft-jadhav-lwig-nbr-mgmt-policy-00, January 455 2017, . 458 [RFC6551] Vasseur, J., Kim, M., Pister, K., Dejean, N., and D. 459 Barthel, "Routing Metrics Used for Path Calculation in Low- 460 Power and Lossy Networks", RFC 6551, March 2012, 461 . 463 8. Acknowledgments 465 Authors wish to thank Yizhou li and Yuefeng Wu for their valuable 466 comments and contributions. 468 Authors' Addresses 470 Jianqiang Hou (editor) 471 Huawei Technologies 472 101 Software Avenue, 473 Nanjing 210012 474 China 476 Phone: +86-15852944235 477 Email: houjianqiang@huawei.com 479 Rahul Arvind Jadhav 480 Huawei Technologies 481 Kundalahalli Village, Whitefield, 482 Bangalore, Karnataka 560037 483 India 485 Phone: +91-080-49160700 486 Email: rahul.ietf@gmail.com 488 Zhenhui Luo 489 Huawei Technologies 490 Bantian, Longgang District, 491 Shenzhen 518129 492 China 494 Phone: +86-18680331295 495 Email: luozhenhui@huawei.com