idnits 2.17.1 draft-qasem-roll-rpl-load-balancing-02.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 : ---------------------------------------------------------------------------- ** There are 3 instances of lines with control characters in the document. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == Line 219 has weird spacing: '...xisting paren...' -- The document date (October 29, 2017) is 2370 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: 'RFC2119' is mentioned on line 131, but not defined == Unused Reference: 'RFC6551' is defined on line 403, but no explicit reference was found in the text == Unused Reference: 'RFC5226' is defined on line 409, but no explicit reference was found in the text -- Obsolete informational reference (is this intentional?): RFC 5226 (Obsoleted by RFC 8126) Summary: 1 error (**), 0 flaws (~~), 5 warnings (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 roll 3 Internet-Draft M.Qasem 4 Intended Status: Standards Track A.Al-Dubai 5 Expires: May 2, 2018 I.Romdhani 6 B.Ghaleb 7 Edinburgh Napier University 8 J. Hou 9 R. Jadhav 10 Huawei Technologies 11 October 29, 2017 13 Load Balancing Objective Function in RPL 14 draft-qasem-roll-rpl-load-balancing-02 16 Abstract 18 This document proposes an extended Objective Function(OF)that 19 balances the number of child nodes of the parent nodes to avoid the 20 overloading problem and ensure node lifetime maximization in the IPv6 21 Routing Protocol for Low-Power and Lossy Networks (RPL). The standard 22 OFs are used to build a Destination Oriented Directed Acyclic Graph 23 (DODAG) where the bottleneck nodes may suffer from unbalanced traffic 24 load. As a result, a part of the network may be disconnected as the 25 energy of the overloaded preferred parent node will drain much faster 26 than other candidate parents. Thus, a new RPL metric has been 27 introduced to balance the traffic load over the network. Finally, the 28 potential extra overhead has been mitigated using a new utilization 29 technique. 31 Status of this Memo 33 This Internet-Draft is submitted to IETF in full conformance with the 34 provisions of BCP 78 and BCP 79. 36 Internet-Drafts are working documents of the Internet Engineering 37 Task Force (IETF), its areas, and its working groups. Note that 38 other groups may also distribute working documents as 39 Internet-Drafts. 41 Internet-Drafts are draft documents valid for a maximum of six months 42 and may be updated, replaced, or obsoleted by other documents at any 43 time. It is inappropriate to use Internet-Drafts as reference 44 material or to cite them other than as "work in progress." 46 The list of current Internet-Drafts can be accessed at 47 http://www.ietf.org/1id-abstracts.html 49 The list of Internet-Draft Shadow Directories can be accessed at 50 http://www.ietf.org/shadow.html 52 Copyright and License Notice 54 Copyright (c) 2017 IETF Trust and the persons identified as the 55 document authors. All rights reserved. 57 This document is subject to BCP 78 and the IETF Trust's Legal 58 Provisions Relating to IETF Documents 59 (http://trustee.ietf.org/license-info) in effect on the date of 60 publication of this document. Please review these documents 61 carefully, as they describe your rights and restrictions with respect 62 to this document. Code Components extracted from this document must 63 include Simplified BSD License text as described in Section 4.e of 64 the Trust Legal Provisions and are provided without warranty as 65 described in the Simplified BSD License. 67 Table of Contents 69 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 70 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . 3 71 2 DODAG construction in a nutshell . . . . . . . . . . . . . . . 4 72 3 Load balancing in RPL . . . . . . . . . . . . . . . . . . . . . 4 73 4 The proposed objective function . . . . . . . . . . . . . . . . 6 74 4.1 Balancing the load traffic . . . . . . . . . . . . . . . . . 6 75 4.2 A new utilization technique for DIO message . . . . . . . . 6 76 4.3 Proposed New Metric for Parent Selection . . . . . . . . . . 7 77 5 Security Considerations . . . . . . . . . . . . . . . . . . . . 9 78 6 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 9 79 7 References . . . . . . . . . . . . . . . . . . . . . . . . . . 9 80 7.1 Normative References . . . . . . . . . . . . . . . . . . . 9 81 7.2 Informative References . . . . . . . . . . . . . . . . . . 10 82 Appendix A. . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 83 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10 85 1 Introduction 87 IPv6 Routing Protocol for LLNs (RPL) [RFC6550] defined two OFs to 88 optimize the path selection towards the root node, namely, the OF 89 zero (OF0) [RFC6552], and the Minimum Rank with Hysteresis OF 90 (MRHOF)[RFC6719]. The Destination Oriented Directed Acyclic Graph 91 (DODAG) construction is built by the RPL OF, that specify how nodes 92 select the preferred parent node by translating one or more metrics 93 into the rank value. 95 The used OF calculates the rank based on some routing metrics [RFC 96 6551] such as hop-count, delay, energy, and so forth. The parent node 97 in RPL can serve more than one child if it is chosen by them as 98 preferred parent. Consequently, the overloaded preferred parents will 99 become fragile nodes as their energy risks to drain much quicker than 100 other nodes. 102 Having conducted simulation experiments and rigours analysis, it is 103 concluded that the current OFs lead to build a topology that suffers 104 from an unbalanced load traffic in bottleneck nodes especially for 105 the first hop nodes (i.e., from the root). Consequently, this problem 106 has a crucial impact on the lifetime of these types of nodes. The 107 battery depletion of that overloaded parent node may affect the 108 network reliability negatively. 110 This challenging problem is still an open issue. In an attempt to 111 overcome this problem, this draft proposes a new OF to mitigate the 112 overusing of the bottleneck node to prolong its battery lifetime. 114 This draft proposes an extended Objective Function(OF) that balances 115 the number of children nodes for the overloaded nodes to ensure node 116 lifetime maximization in RPL and can be summarized as follows. First, 117 a new RPL metric has been used to balance the load traffic among the 118 bottleneck nodes. Second, the DODAG Information Object (DIO) message 119 has been amended by injecting the IP address of the chosen parent 120 before broadcasting it. Third, a new utilization technique has been 121 proposed for the amended DIO message to avoid increasing the overhead 122 of the handshaking and acknowledgment processes. Simulation 123 experiments have been conducted to validate the extended OF 124 performance as detailed in Appendix A. 126 1.1 Terminology 128 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 129 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 130 document are to be interpreted as described in RFC 2119 [RFC2119]. 132 2 DODAG construction in a nutshell 134 RPL is a proactive distance vector routing protocol designed for LLNs 135 [RFC6550], it constructs a DODAG using a certain OF that suits the 136 application requirements. Essentially, RPL relies on a DODAG 137 Information Object (DIO) control message to build the DODAG. 139 Thus, the starting point begins when the root node broadcasts the DIO 140 message to the downstream neighbor nodes. As soon as the closest node 141 receives the message, it can decide whether to join this DODAG or not 142 based on the calculated rank according to the equations (1) and (2) 143 [RFC6719]. 145 Rank(N) = Rank(PN) + RankIncrease (1) 147 RankIncrease = Step * MinHopRankIncrease (2) 149 Where Step represents a scalar value and MinHopRankIncrease 150 represents the minimum RPL parameter. If the node decides to join, 151 then it adds the DIO sender to the candidate parent list. Next, the 152 preferred parent, i.e. the next hop to the root, will be chosen based 153 on the rank from this list to receive all traffic from the child 154 node. Then, it computes its own rank with a monotonical increase 155 according to the selected OF. 157 After that, the node propagates its own DIO with all updated 158 information to all its neighbors including the preferred parent. [RFC 159 6551] defined the number of node metrics/constraints (e.g. hop count 160 and energy) and the link metrics/constraints (e.g. ETX and 161 throughput) that might be used in the OFs [RFC6552][RFC6719]. 163 3 Load balancing in RPL 165 RPL is designed with several robust features such as exiguous delay, 166 quick configuration, loop-free topology, and self-healing. However, 167 the load imbalance is considered as a significant weakness in this 168 protocol. More specifically, RPL is dealing with non-uniform 169 distribution in large-scale LLNs, which may lead to unequal data 170 traffic distribution. Consequently, the energy of the overloaded 171 nodes will be drained much faster than other nodes. Furthermore, this 172 problem has more harmful impacts if the overloaded node is a 173 bottleneck node (i.e. with the first hop to the root) as shown in 174 Figure 1 for node A and B. 176 ------+--------- 177 | Internet 178 | 179 +-----+ 180 | | Border Router 181 | | (RPL Root) 182 +-----+ 183 | 184 o N / \ 185 o o M F A B 186 o o G E C D H 187 o o P R J K o o o 188 o o o o o o 189 o o o o 190 o o o 191 o o o 193 Figure 1: Bottleneck nodes in RPL 195 Figure 2 depicts the selection of the preferred parent for those nodes 196 are within the first hop from nodes A or B. Clearly, node A has more 197 children as it is surrounded by the nodes (N,M,F,G,E,P). Despite the 198 fact that A has more children, it dominates the shred nodes (C,D,R,J) 199 that are also located within the shared area of node B (i.e., within the 200 transmission range of A and B). That unbalanced parent selection 201 approach in RPL left node B only with two children, while node A has ten 202 children. 204 +----------------------------------------------------+ 205 | Parent | Child nodes | Shared nodes | 206 | nodes | |between A and B | 207 |----------------------------------------------------| 208 | A | N,M,F,G,E,P,C,D.R,J | C,D,R,J | 209 |----------------------------------------------------| 210 | B | H,K | C,D,R,J | 211 +----------------------------------------------------+ 213 Figure 2: The selection of the preferred parents 215 It is notable that the connection of all nodes through A is fragile as 216 it is the only link to the root with an overloaded bottleneck node, 217 thus, disconnecting part of the network if node A dies. In particular, 218 this serious problem occurs in RPL due to omitting the number of 219 children in existing parent selection technique. 221 To this end, the node sticks with the current preferred parent and 222 influences its rank, even if this parent deteriorates with more load 223 (i.e. being a parent for more children). The only conceivable scenarios 224 to change the current parent to another candidate parent are as follow: 225 first, if the current parent dies due to battery depletion. The second 226 possibility, when the lossy percentage becomes higher than before, so no 227 acknowledgement message can be heard from the preferred parent for a 228 certain period of time. 230 4 The proposed objective function 232 The proposed OF leverages the lifetime of the entire network. The load 233 balanced OF (LB-OF) balances the data traffic by taking into account the 234 number of children for each candidate parent. 236 4.1 Balancing the load traffic 238 As aforementioned, being a preferred parent for more children means more 239 overhead and unbalanced load, that results in a drain its own energy 240 much faster than other candidate parents. To solve this problem, a new 241 metric has been proposed. The children set created in section 4.2 242 provides each preferred parent with the number of children it has. Based 243 on that, the number of children in the rank calculation in formula (1) 244 is considered. 246 Specifically, the parent with the least number of children will be 247 elected as preferred parent. To this end, the balance has been achieved 248 by declining the number of children of the overloaded bottleneck node. 249 As a result, the majority of children (i.e., the shared nodes between A 250 and B) will choose another preferred parent according to the lower rank, 251 and surely has less number of children. 253 However, it is expected to increase the churn or oscillation as a result 254 of changing the parent. It is a trade-off between unfairness and 255 oscillation, however, this oscillation can be minimized in two 256 techniques to enhance the stability: 258 a) using the number of children along with another metric(s)(e.g. ETX, 259 number of hops, energy, etc., according to the application 260 requirements). 262 b) Using the hysteresis threshold for the number of children(in a 263 lexical manner)to switch from parent to another, the selected threshold 264 depends on the application requirements. 266 4.2 A new utilization technique for DIO message 267 Generally, in the upward routes the root initiates the DODAG 268 construction by sending the first DIO message. Once other nodes receive 269 this DIO, they select the sender as a preferred parent, and then they 270 start calculating their own ranks based on the assigned OF. After that, 271 each node broadcasts its own DIO message (i.e. the updated DIO that 272 contains the new calculated rank value) to all neighbors including the 273 chosen preferred parent which sent the original DIO message. In the 274 standard OFs, the preferred parent ignores the DIOs that come from its 275 child based on the rank. 277 In this stage, the aim is to allow each parent to count its number of 278 children to avoid later possible overloading situations. However, that 279 is not possible in the upward routes (i.e., while maintaining the DODAG 280 through DIOs), as the only control message that can be acknowledged by 281 the destination is the Destination Advertisement Object (DAO) message in 282 the downward routes to recognize the number of children for each 283 parent. 285 Alternatively, setting up an acknowledgement mechanism between parent 286 and children to count the number of children for each parent. However, 287 this acknowledgement also brings an extra overhead for the entire 288 network and subsequently increases the power consumption massively. To 289 overcome this problem, LB-OF using a new technique is proposed as 290 detailed below. In LB-OF algorithm, the received DIO from the child node 291 is counted by the preferred parent node. Each DIO contains the IP 292 address of the chosen preferred parent as detailed in section 4.3. Thus, 293 for each received DIO, the node matches its own IP address with the 294 preferred parent IP address which is inserted in the DIO message, then 295 increments the number of children by ONE for this node if there is a 296 matching. 298 Hence, this technique evades increasing any extra overhead, 299 additionally, the coming DIOs from the child nodes has been utilized to 300 allow each preferred parent to distinguish the number of its children 301 during the DODAG construction stage to optimize the routing. 303 4.3 Proposed New Metric for Parent Selection 305 Typically, the DIO carries the RPL InstanceID, DODAG identifier, version 306 number, Rank and the OF that has been used to calculate the rank, in 307 addition to other identifiers [RFC6550]. This section introduces the 308 number of child nodes as a new metric/constraint in the DAG Metric 309 Container, which includes the selected parent address in the option 310 field within the DIO message. The newly added information is 2 octets 311 named by Child Node Count (CNC) which is per this document defined in 312 the DAG Metric Container. 314 The Child Node Count (CNC) object is used to provide information related 315 to the number of child nodes in the DIO source node, and may be used as 316 a metric or as constraint. 318 The CNC object MAY be present in the DAG Metric Container. There MUST 319 NOT be more than one CNC object as a constraint per DAG Metric 320 Container, and there MUST NOT be more than one CNC object as a metric 321 per DAG Metric Container. The format of the CNC object body is as 322 follows: 324 0 1 2 3 325 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 326 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 327 | Flags |P| CNC | CNC_MAX | | 328 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + 329 | | 330 + + 331 | | 332 + Parent Address + 333 | | 334 + +-+-+-+-+-+-+-+-+ 335 | | 336 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 338 Figure 3: Child Node Count Object Body Format 340 Flags field (8 bits). The following one bits of the CNC object are 341 currently defined: 343 'P'flag: Parent Address State. This, if set to 1, indicates there is a 344 parent address field in the CNC object. 346 CNC: 8-bits. The Child Node Count is encoded in 8 bits in unsigned 347 integer format, expressed in number count, representing the number of 348 child nodes. 350 MAX_CNC: 8-bits. The Maximum Child Node Count is encoded in 8 bits. The 351 MAX_CNC field indicates the maximum number of children a node can hold. 352 This parameter is set by implementers based on neighbor cache entry or 353 the size limit of routing table. Nodes should not hold child nodes more 354 than MAX_CNC. 356 Parent Address (optional): 128-bit IPv6 address of parent node. This 357 field is only present when the'P'flag is set to 1. 359 In the storing mode, DAO can be used for child nodes registration while 360 No-PathDAO can be used for de-registration, and this gives a way to 361 count the number of child nodes. Thus, to minimize traffic load, the 362 Parent Address field in the CNC object should not be present in the 363 storing mode. 365 In the non-storing mode, NS/NA could be an optional way for child node 366 counting. When the 'P' flag is set, the Parent Address in the CNC object 367 should be used for child node counting according to the technique 368 illustrated in section 4.2. 370 When this CNC metric is used, RANK computing reflects the ability of 371 each node to hold more child nodes. Also, a new way for the RANK 372 computing has been suggested: RANK = CNC / CNC_MAX * 255. A node with 373 smaller RANK has high priority to accept new child nodes, a node with 374 RANK = 255 should not hold new child nodes any more. 376 5 Security Considerations 378 Since the routing metrics/constraints are carried within RPL message, 379 the security routing mechanisms defined in [RFC6550] apply here. 381 6 IANA Considerations 383 IANA is requested to allocate a new value for the new metric type "CNC" 384 in the Routing Metric/Constraint Type in the DAG Metric Container. 386 7 References 388 7.1 Normative References 390 [RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J., 391 Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, 392 JP., and R. Alexander, "RPL: IPv6 Routing Protocol for 393 Low-Power and Lossy Networks", RFC 6550, March 2012. 395 [RFC6552] Thubert, P., Ed., "Objective Function Zero for the Routing 396 Protocol for Low-Power and Lossy Networks (RPL)", RFC 397 6552, March 2012. 399 [RFC6719] Gnawali, O. and P. Levis, "The Minimum Rank with 400 Hysteresis Objective Function", RFC 6719, DOI 401 10.17487/RFC6719, September 2012. 403 [RFC6551] Vasseur, J., Ed., Kim, M., Ed., Pister, K., Dejean, N., 404 and D. Barthel, "Routing Metrics Used for Path Calculation 405 in Low-Power and Lossy Networks", RFC 6551, March 2012. 407 7.2 Informative References 409 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 410 IANA Considerations Section in RFCs", BCP 26, RFC 5226, 411 May 2008. 413 [Contiki] Contik O.S and cooja simulatoer http://www.contiki-os.org/ 415 Appendix A. 417 The protocol has been simulated with Cooja simulator based 418 on Instant Contiki 2.7 operating system [Contiki]. 419 Collected results corroborate the superiority of our OF 420 over the existing ones in terms of lifetime, power 421 consumption and packet delivery ratio. 423 Authors' Addresses 425 Mamoun Qasem (editor) 426 Edinburgh Napier University 427 10 Colinton Road, EH10 5DT, Edinburgh, UK 429 Phone: +44 131 455 2772 430 Email: m.qasem@napier.ac.uk 432 Ahmed Al-Dubai 433 Edinburgh Napier University 434 10 Colinton Road, EH10 5DT, Edinburgh, UK 436 Phone: +44 131 455 2796 437 Email: a.al-dubai@napier.ac.uk 439 Imed Romdhani 440 Edinburgh Napier University 441 10 Colinton Road, EH10 5DT, Edinburgh, UK 443 Phone: +44 131 455 2726 444 Email: i.romdhani@napier.ac.uk 446 Baraq Ghaleb 447 Edinburgh Napier University 448 10 Colinton Road, EH10 5DT, Edinburgh, UK 450 Email: b.ghaleb@napier.ac.uk 452 Jianqiang Hou (editor) 453 Huawei Technologies 454 101 Software Avenue, 455 Nanjing 210012 456 China 458 Phone: +86-15852944235 459 Email: houjianqiang@huawei.com 461 Rahul Arvind Jadhav 462 Huawei Technologies 463 Kundalahalli Village, Whitefield, 464 Bangalore, Karnataka 560037 465 India 467 Phone: +91-080-49160700 468 Email: rahul.ietf@gmail.com