idnits 2.17.1 draft-baraq-roll-lbsa-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 : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** There are 3 instances of too long lines in the document, the longest one being 17 characters in excess of 72. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year == The document doesn't use any RFC 2119 keywords, yet seems to have RFC 2119 boilerplate text. -- The document date (March 23, 2020) is 1494 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 119, but not defined == Missing Reference: 'RFC6206' is mentioned on line 177, but not defined == Unused Reference: 'RFC 6206' is defined on line 247, but no explicit reference was found in the text Summary: 2 errors (**), 0 flaws (~~), 5 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 ROLL 3 INTERNET-DRAFT B.Ghaleb 4 Intended Status: Standards Track A.Al-Dubai 5 Expires: September 23, 2019 I.Romdhani 6 M.Qasem 7 Edinburgh Napier University 8 March 23, 2020 10 Load-balancing and Stability Aware Objective Function (LBSA) 11 draft-baraq-roll-lbsa-00 13 Abstract 15 The IPv6 Routing Protocol for Low-power and Lossy Networks (RPL) has 16 been recently standardized as the de facto solution for routing in 17 the context of the emerging Internet of Things (IoT) paradigm. RPL, 18 along with other standards, has provided a baseline framework for IoT 19 that has helped advance communications in the world of embedded 20 resource-constrained networks. However, RPL still suffers from issues 21 that may limit its efficiency such as the absence of an efficient 22 load-balancing primitive. To address this problem, a novel load- 23 balancing scheme is introduced that ensures a fair distribution of 24 traffic among nodes while minimizing overhead 26 Status of this Memo 28 This Internet-Draft is submitted to IETF in full conformance with the 29 provisions of BCP 78 and BCP 79. 31 Internet-Drafts are working documents of the Internet Engineering 32 Task Force (IETF), its areas, and its working groups. Note that 33 other groups may also distribute working documents as 34 Internet-Drafts. 36 Internet-Drafts are draft documents valid for a maximum of six months 37 and may be updated, replaced, or obsoleted by other documents at any 38 time. It is inappropriate to use Internet-Drafts as reference 39 material or to cite them other than as "work in progress." 41 The list of current Internet-Drafts can be accessed at 42 http://www.ietf.org/1id-abstracts.html 44 The list of Internet-Draft Shadow Directories can be accessed at 45 http://www.ietf.org/shadow.html 47 Copyright and License Notice 49 Copyright (c) 2018 IETF Trust and the persons identified as the 50 document authors. All rights reserved. 52 This document is subject to BCP 78 and the IETF Trust's Legal 53 Provisions Relating to IETF Documents 54 (http://trustee.ietf.org/license-info) in effect on the date of 55 publication of this document. Please review these documents 56 carefully, as they describe your rights and restrictions with respect 57 to this document. Code Components extracted from this document must 58 include Simplified BSD License text as described in Section 4.e of 59 the Trust Legal Provisions and are provided without warranty as 60 described in the Simplified BSD License. 62 Table of Contents 64 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 65 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . 3 66 2. Load-balancing aware Objective Function . . . . . . . . . . . 3 67 2.1 The load-balancing metric . . . . . . . . . . . . . . . . . 4 68 2.1.1 Measuring the Number of Children Metric . . . . . . . . 4 69 2.2 The Timely Propagation Primitive . . . . . . . . . . . . . . 5 70 2.3 Avoiding The Herding Problem . . . . . . . . . . . . . . . . 5 71 3 Security Considerations . . . . . . . . . . . . . . . . . . . . 6 72 4 References . . . . . . . . . . . . . . . . . . . . . . . . . . 6 73 4.1 Normative References . . . . . . . . . . . . . . . . . . . 6 74 4.2 Informative References . . . . . . . . . . . . . . . . . . 6 75 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 7 77 1 Introduction 79 The standardized Routing Protocol for Low-power and Lossy networks 80 (RPL) [RFC6550] lacks in an efficient routing primitive that ensures 81 a fair distribution of traffic among nodes while minimizing overhead. 82 The absence of such mechanism may prevent the distribution of traffic 83 among multiple nodes, potentially increasing data loss caused by the 84 node packet buffer overflow or leading to a faster depletion of the 85 energy of overloaded nodes which in turn may result in service 86 disruption [1][2][3][4]. However, poorly implemented load balancing 87 causes problems too. An example is the herding-effect [1], in which 88 the network suffers topological instability caused by nodes 89 repeatedly switching preferred parents in a futile attempt to achieve 90 load balancing [1]. For instance, in Figure 1a, you can see that six 91 nodes have selected the lightly loaded parent, A, upon receiving its 92 DIO. However, in Figure 1b, all six nodes simultaneously changed 93 their preferred parent to, B, in an attempt to load-balance the 94 traffic upon receiving a new DIO from that node announcing a fewer 95 number of children than node A. However, when receiving a new DIO 96 from node A, the migration reverses, resulting in load oscillation 97 with no balancing. 99 +---+ +---+ 100 |LBR| |LBR| 101 +---+ +---+ 102 / /\ 103 / / \ 104 +--+ +--+ Continuous loop +--+ +--+ 105 :A : :B : <--------------> :A : :B : 106 +--+ +--+ +--+ +--+ 107 / \ 108 / \ 109 * * * (Children) * * * (Children) 110 * * * * * * 111 (a) (b) 112 Figure 1: The herding-effect problem 114 1.1 Terminology 116 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 117 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 118 document are to be interpreted as described in RFC 2119 [RFC2119]. 120 2. Load-balancing aware Objective Function 122 In order to address the load-balancing problem of RPL, a new load 123 balancing OF is proposed in this study and discussed in the following 124 subsections. We emphasize here that the main goal of the proposed 125 solution is to introduce a load-balancing mechanism into RPL while 126 maintaining stability with minimal overhead. In order to achieve this 127 goal, we articulate that a stable and efficient load-balancing 128 mechanism should comprise the following sub-components: several steps 129 as follows: 1) A suitable metric (single or composite) for load- 130 balancing. 2) A propagation primitive that ensures timely and 131 efficient propagation of load balancing information before it becomes 132 obsolete. 3) A routing primitive that mitigates the instability 133 problem that may arise from introducing load-balancing into the 134 network. 136 2.1 The load-balancing metric 138 Several routing metrics for RPL networks have been proposed in the 139 literature [RFC6551] including load-balancing metrics such as number 140 of children, throughput, and queue utilization factor. In this draft, 141 we opt to use the number of children metric for the purpose of load- 142 balancing for two primary reasons. First, it can be measured easily 143 based on the data-plane traffic without incurring any extra overhead 144 in the control-plane, especially in periodic applications as 145 discussed next. Second, in the vast majority of applications, it 146 reflects the actual network load. 148 2.1.1 Measuring the number of children metric 149 In this draft, we introduce for the first time the notion of calculating the number of 150 children based on the data-plane messages rather than relying on 151 RPL's DAO messages. In fact, number of children can be calculated 152 based on RPL's DAO messages, however, as these messages are an 153 optional feature of RPL, they may not be available in all scenarios. To 154 calculate the number of children based on data-plane traffic, we 155 exploit the fact that IPv6 data packets carry the source address of 156 the sender in the header of the packet, in addition to the RPL Hop- 157 by-Hop (HBH) header option. Hence, when an IPv6 packet is received, 158 the protocol first determines if it is a control or a data packet by 159 inspecting if the RPL HBH Option is exist or not. The presence of 160 such an option indicates that a data packet is being received at the 161 network layer. If the received packet is data, it inspects its 162 direction to decide if the sender is a child or not (direction is 163 specified by the Down flag in the RPL HBH Option). If the packet is 164 heading upward, the sender is a child so the protocol adds the sender 165 IP Address (CHIP) to the list of children (CHList) of the receiver. 166 If no data packets are received from an existing child during a pre- 167 specified interval, it is removed. This interval is set proportional 168 to the traffic rate. 170 2.2 The Timely Propagation Primitive 172 The second step towards realizing an efficient load-balancing 173 objective function is the timely propagation of the routing 174 information, especially those related to the load-balancing metric 175 (i.e., number of children). In fact, the propagation of routing 176 information carried in RPL's DIO messages is regulated by means of 177 Trickle [RFC6206] in which the DIO transmission rate is increased 178 upon detecting inconsistencies in the network. For example, the current 179 implementation of Trickle in Contiki OS has restricted the number of 180 times the network is declared inconsistent to a few cases to minimize 181 the control-plane overhead. These cases include global repair, local 182 repair, and parent change. Here, it is clear that a change in a 183 node's rank does not trigger a resetting of the Trickle timer, so 184 some routing decisions might be taken based on obsolete routing 185 information due to the long DIO transmission period in the consistent 186 state. Hence, a problematic gap may arise between the time the node 187 has changed its preferred parent and the scheduled time for the DIO 188 to be sent at. 190 To overcome this concern, we have opted to permit the node to declare 191 an inconsistency upon detecting that its number of children has been 192 increased or decreased by a pre-specified threshold. This will allow 193 neighboring nodes to receive the load information in a timely manner, 194 at the cost of some increased overhead. To reduce the overhead 195 resulting from resetting the Trickle timer, the protocol does not do 196 this every time the node's balancing information changes (in terms of 197 number of children). Instead, it uses a FastPropagation Timer (Reset 198 Timer): when this expires a node checks whether it should reset its 199 Trickle timer or not. The propagation of rank information is still 200 governed by the Trickle algorithm itself. 202 2.3 Avoiding The Herding Problem 204 One of the obstacles toward achieving load balancing in RPL is the 205 way the protocol switches preferred parents. The common strategy 206 adopted by RPL is to allow a specific node to switch immediately to a 207 better parent upon detecting such a parent by means of DIOs. This may 208 have the advantage of timely switching; however, in the context of 209 load balancing, changing preferred parent immediately on discovery 210 may give rise to the herding effect explained earlier. To address 211 this issue, we have introduced the idea of the Balancing Timer (or 212 Scheduling Timer). This timer regulates the timing of parent 213 selection process. Instead of having a node performing this process 214 immediately upon receiving a new DIO, the parent selection in our 215 proposed mechanism is performed regularly at pre-determined interval. 216 However, we exclude the first received DIO from this policy to allow 217 faster convergence time at the stage of DODAG construction. In other 218 words, when a node receives a DIO for the first time, it will 219 immediately choose the sender as its preferred parent. Then, the node 220 must wait until the expiration of the Balancing Timer in order to 221 check whether a better parent is available or not so it can change to 222 a new preferred parent. The Balancing Timer is reset every time the 223 node performs the parent selection process. The value of the 224 Balancing Timer should be set in a way that allow for several DIOs to 225 be received at the node so it can have several candidate parents 226 which is better to be set empirically. The details of this process is 227 also illustrated in Algorithm 5-1. 229 3 Security Considerations 231 Since the routing metrics/constraints are carried within RPL message, 232 the security routing mechanisms defined in [RFC6550] apply here. 234 4 References 236 4.1 Normative References 238 [RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J. 239 Kelsey, R., Levis, P., Pister, K., Struik, R., 240 Vasseur,JP., and R. Alexander, "RPL: IPv6 Routing Protocol 241 for Low-Power and Lossy Networks", RFC 6550, March 2012. 243 [RFC6551] Vasseur, J., Ed., Kim, M., Ed., Pister, K., Dejean, N., 244 and D. Barthel, "Routing Metrics Used for Path Calculation 245 in Low-Power and Lossy Networks", RFC 6551, March 2012. 247 [RFC 6206] P. Levis, T. Clausen, J. Hui, O. Gnawali, and J. Ko, "The 248 Trickle algorithm," RFC 6206, Internet Engineering Task 249 Force (IETF), 2011 251 4.2 Informative References 253 [1] H. S. Kim, J. Paek and S. Bahk, "QU-RPL: Queue utilization based 254 RPL for load balancing in large scale industrial applications," in 255 the 12th Annual IEEE International Conference on Sensing, 256 Communication, and Networking (SECON), Seattle, WA, Jun. 2015, pp. 257 265-273. 259 [2] J. Tripathi and J. C. De Oliveira, "Quantifying load imbalance: A 260 practical implementation for data collection in low power lossy 261 networks," 47th Annual Conference on Information Sciences and 262 Systems (CISS), Baltimore, MD, 2013, pp. 1-6. 264 [3] X. Liu, J. Guo, G. Bhatti, P. Orlik and K. Parsons, "Load balanced 265 routing for low power and lossy networks," in the IEEE Wireless 266 Communications and Networking Conference (WCNC), Apr. 2013, 267 Shanghai, pp. 2238-2243. 269 [4] B. Ghaleb, A. Al-Dubai, E. Ekonomou, W. Gharib, L. Mackenzi and M. 270 Bani Khala, "A New Load-Balancing Aware Objective Function for 271 RPL's IoT Networks," 2018 IEEE 20th International Conference on 272 High Performance Computing and Communications; IEEE 16th 273 International Conference on Smart City; IEEE 4th International 274 Conference on Data Science and Systems (HPCC/SmartCity/DSS), 275 Exeter, United Kingdom, 2018, pp. 909-914. 277 Authors' Addresses 279 Baraq Ghaleb (Editor) 280 Edinburgh Napier Universty 281 10 Colinton Road, EH10 5DT, Edinburgh, UK 282 EMail: b.ghaleb@napier.ac.uk 284 Ahmed Al-Dubai 285 Edinburgh Napier Universty 286 10 Colinton Road, EH10 5DT, Edinburgh, UK 287 Phone: +44 131 455 2796 288 EMail: a.al-dubai@napier.ac.uk 290 Imed Romdhani (Editor) 291 Edinburgh Napier Universty 292 10 Colinton Road, EH10 5DT, Edinburgh, UK 293 Phone: +44 131 455 2726 294 EMail: i.romdhani@napier.ac.uk 296 Mamoun Qasem 297 Edinburgh Napier Universty 298 10 Colinton Road, EH10 5DT, Edinburgh, UK 299 EMail: m.qasem@napier.ac.uk