idnits 2.17.1 draft-qasem-roll-rpl-load-balancing-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 : ---------------------------------------------------------------------------- ** 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 216 has weird spacing: '...xisting paren...' == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (February 6, 2017) is 2635 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 128, but not defined -- Obsolete informational reference (is this intentional?): RFC 5226 (Obsoleted by RFC 8126) Summary: 1 error (**), 0 flaws (~~), 4 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: August 10, 2017 I.Romdhani 6 B.Ghaleb 7 Edinburgh Napier University 8 February 6, 2017 10 Load Balancing Objective Function in RPL 11 draft-qasem-roll-rpl-load-balancing-00 13 Abstract 15 This document proposes an extended Objective Function(OF) that 16 balances the number of children nodes of the parent nodes to avoid 17 the overloading problem and ensure node lifetime maximization in the 18 IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL). The 19 standard OFs are used to build a Destination Oriented Directed 20 Acyclic Graph (DODAG) where the bottleneck nodes may suffer from 21 unbalanced traffic load. As a result, a part of the network may be 22 disconnected as the energy of the overloaded preferred parent node 23 will drain much faster than other candidate parents. Thus, a new RPL 24 metric has been introduced to balance the traffic load over the 25 network. The potential extra overhead has been mitigated using a new 26 utilization technique. Finally, the proposed OF amends the DODAG 27 Information Object (DIO) message format. 29 Status of this Memo 31 This Internet-Draft is submitted to IETF in full conformance with the 32 provisions of BCP 78 and BCP 79. 34 Internet-Drafts are working documents of the Internet Engineering 35 Task Force (IETF), its areas, and its working groups. Note that 36 other groups may also distribute working documents as 37 Internet-Drafts. 39 Internet-Drafts are draft documents valid for a maximum of six months 40 and may be updated, replaced, or obsoleted by other documents at any 41 time. It is inappropriate to use Internet-Drafts as reference 42 material or to cite them other than as "work in progress." 44 The list of current Internet-Drafts can be accessed at 45 http://www.ietf.org/1id-abstracts.html 46 The list of Internet-Draft Shadow Directories can be accessed at 47 http://www.ietf.org/shadow.html 49 Copyright and License Notice 51 Copyright (c) 2017 IETF Trust and the persons identified as the 52 document authors. All rights reserved. 54 This document is subject to BCP 78 and the IETF Trust's Legal 55 Provisions Relating to IETF Documents 56 (http://trustee.ietf.org/license-info) in effect on the date of 57 publication of this document. Please review these documents 58 carefully, as they describe your rights and restrictions with respect 59 to this document. Code Components extracted from this document must 60 include Simplified BSD License text as described in Section 4.e of 61 the Trust Legal Provisions and are provided without warranty as 62 described in the Simplified BSD License. 64 Table of Contents 66 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 67 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . 3 68 2 DODAG construction in a nutshell . . . . . . . . . . . . . . . 4 69 3 Load balancing in RPL . . . . . . . . . . . . . . . . . . . . . 4 70 4 The proposed objective function . . . . . . . . . . . . . . . . 6 71 4.1 Balancing the load traffic . . . . . . . . . . . . . . . . . 6 72 4.2 A new utilization technique for the amended DIO . . . . . . 6 73 4.3 The amended DIO message . . . . . . . . . . . . . . . . . . 7 74 5 Security Considerations . . . . . . . . . . . . . . . . . . . . 7 75 6 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 7 76 7 References . . . . . . . . . . . . . . . . . . . . . . . . . . 8 77 7.1 Normative References . . . . . . . . . . . . . . . . . . . 8 78 7.2 Informative References . . . . . . . . . . . . . . . . . . 9 79 Appendix A. . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 80 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 9 82 1 Introduction 84 IPv6 Routing Protocol for LLNs (RPL) [RFC6550] defined two OFs to 85 optimize the path selection towards the root node, namely, the OF 86 zero (OF0) [RFC6552], and the Minimum Rank with Hysteresis OF 87 (MRHOF)[RFC6719]. The Destination Oriented Directed Acyclic Graph 88 (DODAG) construction is built by the RPL OF, that specify how nodes 89 select the preferred parent node by translating one or more metrics 90 into the rank value. 92 The used OF calculates the rank based on some routing metrics [RFC 93 6551] such as hop-count, delay, energy, and so forth. The parent node 94 in RPL can serve more than one child if it is chosen by them as 95 preferred parent. Consequently, the overloaded preferred parents will 96 become fragile nodes as their energy risks to drain much quicker than 97 other nodes. 99 Having conducted simulation experiments and rigours analysis, it is 100 concluded that the current OFs lead to build a topology that suffers 101 from an unbalanced load traffic in bottleneck nodes especially for 102 the first hop nodes (i.e., from the root). Consequently, this problem 103 has a crucial impact on the lifetime of these types of nodes. The 104 battery depletion of that overloaded parent node may affect the 105 network reliability negatively. 107 This challenging problem is still an open issue. In an attempt to 108 overcome this problem, this draft proposes a new OF to mitigate the 109 overusing of the bottleneck node to prolong its battery lifetime. 111 This draft proposes an extended Objective Function(OF) that balances 112 the number of children nodes for the overloaded nodes to ensure node 113 lifetime maximization in RPL and can be summarized as follows. First, 114 a new RPL metric has been used to balance the load traffic among the 115 bottleneck nodes. Second, the DODAG Information Object (DIO) message 116 has been amended by injecting the IP address of the chosen parent 117 before broadcasting it. Third, a new utilization technique has been 118 proposed for the amended DIO message to avoid increasing the overhead 119 of the handshaking and acknowledgment processes. Simulation 120 experiments have been conducted to validate the extended OF 121 performance as detailed in Appendix A. 123 1.1 Terminology 125 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 126 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 127 document are to be interpreted as described in RFC 2119 [RFC2119]. 129 2 DODAG construction in a nutshell 131 RPL is a proactive distance vector routing protocol designed for LLNs 132 [RFC6550], it constructs a DODAG using a certain OF that suits the 133 application requirements. Essentially, RPL relies on a DODAG 134 Information Object (DIO) control message to build the DODAG. 136 Thus, the starting point begins when the root node broadcasts the DIO 137 message to the downstream neighbor nodes. As soon as the closest node 138 receives the message, it can decide whether to join this DODAG or not 139 based on the calculated rank according to the equations (1) and (2) 140 [RFC6719]. 142 Rank(N) = Rank(PN) + RankIncrease (1) 144 RankIncrease = Step * MinHopRankIncrease (2) 146 Where Step represents a scalar value and MinHopRankIncrease 147 represents the minimum RPL parameter. If the node decides to join, 148 then it adds the DIO sender to the candidate parent list. Next, the 149 preferred parent, i.e. the next hop to the root, will be chosen based 150 on the rank from this list to receive all traffic from the child 151 node. Then, it computes its own rank with a monotonical increase 152 according to the selected OF. 154 After that, the node propagates its own DIO with all updated 155 information to all its neighbors including the preferred parent. [RFC 156 6551] defined the number of node metrics/constraints (e.g. hop count 157 and energy) and the link metrics/constraints (e.g. ETX and 158 throughput) that might be used in the OFs [RFC6552][RFC6719]. 160 3 Load balancing in RPL 162 RPL is designed with several robust features such as exiguous delay, 163 quick configuration, loop-free topology, and self-healing. However, 164 the load imbalance is considered as a significant weakness in this 165 protocol. More specifically, RPL is dealing with non-uniform 166 distribution in large-scale LLNs, which may lead to unequal data 167 traffic distribution. Consequently, the energy of the overloaded 168 nodes will be drained much faster than other nodes. Furthermore, this 169 problem has more harmful impacts if the overloaded node is a 170 bottleneck node (i.e. with the first hop to the root) as shown in 171 Figure 1 for node A and B. 173 ------+--------- 174 | Internet 175 | 176 +-----+ 177 | | Border Router 178 | | (RPL Root) 179 +-----+ 180 | 181 o N / \ 182 o o M F A B 183 o o G E C D H 184 o o P R J K o o o 185 o o o o o o 186 o o o o 187 o o o 188 o o o 190 Figure 1: Bottleneck nodes in RPL 192 Figure 2 depicts the selection of the preferred parent for those nodes 193 are within the first hop from nodes A or B. Clearly, node A has more 194 children as it is surrounded by the nodes (N,M,F,G,E,P). Despite the 195 fact that A has more children, it dominates the shred nodes (C,D,R,J) 196 that are also located within the shared area of node B (i.e., within the 197 transmission range of A and B). That unbalanced parent selection 198 approach in RPL left node B only with two children, while node A has ten 199 children. 201 +----------------------------------------------------+ 202 | Parent | Children nodes | Shared nodes | 203 | nodes | |between A and B | 204 |----------------------------------------------------| 205 | A | N,M,F,G,E,P,C,D.R,J | C,D,R,J | 206 |----------------------------------------------------| 207 | B | H,K | C,D,R,J | 208 +----------------------------------------------------+ 210 Figure 2: The selection of the preferred parents 212 It is notable that the connection of all nodes through A is fragile as 213 it is the only link to the root with an overloaded bottleneck node, 214 thus, disconnecting part of the network if node A dies. In particular, 215 this serious problem occurs in RPL due to omitting the number of 216 children in existing parent selection technique. 218 To this end, the node sticks with the current preferred parent and 219 influences its rank, even if this parent deteriorates with more load 220 (i.e. being a parent for more children). The only conceivable scenarios 221 to change the current parent to another candidate parent are as follow: 222 first, if the current parent dies due to battery depletion. The second 223 possibility, when the lossy percentage becomes higher than before, so no 224 acknowledgement message can be heard from the preferred parent for a 225 certain period of time. 227 4 The proposed objective function 229 The proposed OF leverages the lifetime of the entire network. The load 230 balanced OF (LB-OF) balances the data traffic by taking into account the 231 number of children for each candidate parent. 233 4.1 Balancing the load traffic 235 As aforementioned, being a preferred parent for more children means more 236 overhead and unbalanced load, thus leads to drain its own energy much 237 faster than other candidate parents. To solve this problem, a new metric 238 has been proposed. The children set created in section 4.2 provides each 239 preferred parent with the number of children it has. Based on that, the 240 number of children in the rank calculation in formula (1) is 241 considered. 243 Specifically, the parent with the least number of children will be 244 elected as preferred parent. To this end, the balance has been achieved 245 by declining the number of children of the overloaded bottleneck node. 246 As a result, the majority of children (i.e., the shared nodes between A 247 and B) will choose another preferred parent according to the lower rank, 248 and surely has less number of children. 250 4.2 A new utilization technique for the amended DIO 252 Generally, in the upward routes the root initiates the DODAG 253 construction by sending the first DIO message. Once other nodes receive 254 this DIO, they select the sender as a preferred parent, and then they 255 start calculating their own ranks based on the assigned OF. After that, 256 each node broadcasts its own DIO message (i.e. the updated DIO that 257 contains the new calculated rank value) to all neighbors including the 258 chosen preferred parent which sent the original DIO message. In the 259 standard OFs, the preferred parent ignores the DIOs that come from its 260 child based on the rank. 262 In this stage, the aim is to allow each parent to count its number of 263 children to avoid later possible overloading situations. However, that 264 is not possible in the upward routes (i.e., while maintaining the DODAG 265 through DIOs), as the only control message that can be acknowledged by 266 the destination is the Destination Advertisement Object (DAO) message in 267 the downward routes to recognize the number of children for each 268 parent. 270 Alternatively, a handshaking mechanism between parent and children can 271 be set up to count the number of children for each parent, but this also 272 brings an extra overhead for the entire network and subsequently 273 increases the power consumption massively. To overcome this problem, LB- 274 OF using a new technique is proposed as detailed below. In LB-OF 275 algorithm, the received DIO from the child node is counted by the 276 preferred parent node using a special buffer (set) created for this 277 purpose. As detailed in section 4.3, the amended DIO contains the IP 278 address of the chosen preferred parent. Thus, for each received DIO, the 279 node matches its own IP address with the preferred parent IP address 280 which is inserted in the DIO message, then increments the number of 281 children set by one for this node if there is a matching. 283 Hence, this technique evades increasing the overhead that can be caused 284 by the handshaking process (which could be used for the entire network). 285 In addition, the coming DIOs from the children nodes has been utilized 286 to allow each preferred parent to distinguish the number of its children 287 during the DODAG construction stage. 289 4.3 The amended DIO message 291 Typically, the DIO carries the RPL InstanceID, DODAG identifier, version 292 number, Rank and the OF that has been used to calculate the rank, in 293 addition to others identifiers [RFC6550]. The DIO has been amended by 294 injecting the chosen preferred parent IP address into the propagated DIO 295 as shown in Figure 3. 297 5 Security Considerations 299 Since the routing metrics/constraints are carried within RPL message, 300 the security routing mechanisms defined in [RFC6550] apply here. 302 6 IANA Considerations 304 The IANA defined in [RFC6551] apply here according to [RFC5226]. 306 0 1 2 3 307 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 308 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 309 | RPLInstanceID |Version Number | Rank | 310 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 311 |G|0| MOP | Prf | DTSN | Flags | Reserved | 312 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 313 | | 314 + + 315 | | 316 + DODAGID + 317 | | 318 + + 319 | | 320 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 321 | | 322 + + 323 | | 324 + Parent Address + 325 | | 326 + + 327 | | 328 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 329 | Option(s)... 330 +-+-+-+-+-+-+-+-+ 332 Figure 3: The amended DIO message format 334 7 References 336 7.1 Normative References 338 [RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J., 339 Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, 340 JP., and R. Alexander, "RPL: IPv6 Routing Protocol for 341 Low-Power and Lossy Networks", RFC 6550, March 2012. 343 [RFC6552] Thubert, P., Ed., "Objective Function Zero for the Routing 344 Protocol for Low-Power and Lossy Networks (RPL)", RFC 345 6552, March 2012. 347 [RFC6719] Gnawali, O. and P. Levis, "The Minimum Rank with 348 Hysteresis Objective Function", RFC 6719, DOI 349 10.17487/RFC6719, September 2012. 351 [RFC6551] Vasseur, J., Ed., Kim, M., Ed., Pister, K., Dejean, N., 352 and D. Barthel, "Routing Metrics Used for Path Calculation 353 in Low-Power and Lossy Networks", RFC 6551, March 2012. 355 7.2 Informative References 357 [RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an 358 IANA Considerations Section in RFCs", BCP 26, RFC 5226, 359 May 2008. 361 [Contiki] Contik O.S and cooja simulatoer http://www.contiki-os.org/ 363 Appendix A. 365 The protocol has been simulated with Cooja simulator based 366 on Instant Contiki 2.7 operating system [Contiki]. 367 Collected results corroborate the superiority of our OF 368 over the existing ones in terms of lifetime, power 369 consumption and packet delivery ratio. 371 Authors' Addresses 373 Mamoun Qasem (editor) 374 Edinburgh Napier University 375 10 Colinton Road, EH10 5DT, Edinburgh, UK 377 Phone: +44 131 455 2772 378 Email: m.qasem@napier.ac.uk 380 Ahmed Al-Dubai 381 Edinburgh Napier University 382 10 Colinton Road, EH10 5DT, Edinburgh, UK 384 Phone: +44 131 455 2796 385 Email: a.al-dubai@napier.ac.uk 387 Imed Romdhani 388 Edinburgh Napier University 389 10 Colinton Road, EH10 5DT, Edinburgh, UK 391 Phone: +44 131 455 2726 392 Email: i.romdhani@napier.ac.uk 394 Baraq Ghaleb 395 Edinburgh Napier University 396 10 Colinton Road, EH10 5DT, Edinburgh, UK 398 Email: b.ghaleb@napier.ac.uk