idnits 2.17.1 draft-baraq-roll-drizzle-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.) 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 22, 2018) is 2220 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 125, but not defined == Unused Reference: 'RFC6552' is defined on line 250, but no explicit reference was found in the text == Unused Reference: 'RFC6719' is defined on line 254, but no explicit reference was found in the text == Unused Reference: 'RFC6551' is defined on line 258, but no explicit reference was found in the text Summary: 1 error (**), 0 flaws (~~), 6 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, 2018 I.Romdhani 6 M.Qasem 7 Edinburgh Napier University 8 March 22, 2018 10 Drizzle Algorithm 11 draft-baraq-roll-drizzle-00 13 Abstract 15 Trickle algorithm used in RPL routing protocol suffers from some 16 issues related to power, network convergence time and overhead and 17 load-distribution. To optimize this algorithm for Low-power and Lossy 18 Networks (LLNs), a new algorithm called Drizzle is introduced. 19 Drizzle uses an adaptive suppression mechanism that permits the nodes 20 to have different transmission probabilities, which are consistent 21 with their transmission history. Compared to Trickle, Drizzle removes 22 the listen-only period from Drizzle's intervals, thus, leading to 23 faster convergence time. Furthermore, a new policy for setting the 24 redundancy coefficient has been used to mitigate the negative effect 25 of the short-listen problem presented when removing the listen-only 26 period and to further boost the fairness in the network. 28 Status of this Memo 30 This Internet-Draft is submitted to IETF in full conformance with the 31 provisions of BCP 78 and BCP 79. 33 Internet-Drafts are working documents of the Internet Engineering 34 Task Force (IETF), its areas, and its working groups. Note that 35 other groups may also distribute working documents as 36 Internet-Drafts. 38 Internet-Drafts are draft documents valid for a maximum of six months 39 and may be updated, replaced, or obsoleted by other documents at any 40 time. It is inappropriate to use Internet-Drafts as reference 41 material or to cite them other than as "work in progress." 43 The list of current Internet-Drafts can be accessed at 44 http://www.ietf.org/1id-abstracts.html 45 The list of Internet-Draft Shadow Directories can be accessed at 46 http://www.ietf.org/shadow.html 48 Copyright and License Notice 50 Copyright (c) 2018 IETF Trust and the persons identified as the 51 document authors. All rights reserved. 53 This document is subject to BCP 78 and the IETF Trust's Legal 54 Provisions Relating to IETF Documents 55 (http://trustee.ietf.org/license-info) in effect on the date of 56 publication of this document. Please review these documents 57 carefully, as they describe your rights and restrictions with respect 58 to this document. Code Components extracted from this document must 59 include Simplified BSD License text as described in Section 4.e of 60 the Trust Legal Provisions and are provided without warranty as 61 described in the Simplified BSD License. 63 Table of Contents 65 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 66 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . 3 67 2. Drizzle Algorithm . . . . . . . . . . . . . . . . . . . . . . 4 68 2.1 Drizzle Variables . . . . . . . . . . . . . . . . . . . . . 4 69 2.1 Drizzle Parameters . . . . . . . . . . . . . . . . . . . . . 4 70 2.1 Drizzle Operations . . . . . . . . . . . . . . . . . . . . . 5 71 3 Security Considerations . . . . . . . . . . . . . . . . . . . . 7 72 4 References . . . . . . . . . . . . . . . . . . . . . . . . . . 7 73 4.1 Normative References . . . . . . . . . . . . . . . . . . . 7 74 4.2 Informative References . . . . . . . . . . . . . . . . . . 7 75 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 8 77 1 Introduction 79 A key design principle of any routing protocol is to have an 80 efficient mechanism for disseminating routing information through the 81 network, and maintaining up-to-date information. One of the 82 mechanisms to perform this task is to periodically propagate the 83 routing information so often which is widely used in unconstrained 84 wired networks. A major issue with adopting this approach is the high 85 volume of traffic overhead that may affect negatively the performance 86 of the resource-constrained large-scale LLNs [1]. The simplicity of 87 route update and maintenance adopted by those routing protocols is 88 the primary reason behind this issue. This is because that routing 89 information must be propagated periodically by each sensor node even 90 in the case when there is no a significant change in the state of the 91 network [1]. A recent and more efficient approach is the one 92 standardized by the IETF ROLL group to regulate the emission of 93 routing information in LLNs, namely, Trickle algorithm [RFC 6206]. 94 The basic idea behind Trickle is to equip resource-constrained nodes 95 with a simple and energy-efficient primitive for disseminating 96 routing information throughout the network. Trickle uses two 97 mechanisms to achieve this goal. The first mechanism is to adaptively 98 increase the signaling rate upon detecting new routing information. 99 In contrast, it exponentially reduces the signaling rate when the 100 network state is up-to-date in order to save energy and bandwidth. 101 The second is the suppression mechanism in which a node suppresses 102 the transmission of its routing information if detected that enough 103 number of its neighbors have transmitted the same piece of 104 information. The main issue with Trickle is that it is mainly 105 developed for code propagation which in one way or another has 106 different characteristics in comparison with routing maintenance in a 107 routing protocol [2]. Specifically , Trickle has some issues related 108 to its convergence time and fairness as detailed in [3][4] 110 To alleviate Trickle issues, an enhanced algorithm for disseminating 111 routing information in LLNs is proposed. The proposed Drizzle 112 algorithm attempts to address the limitations of the previous 113 algorithms and in particular Trickle algorithm. Drizzle offers an 114 adaptive suppression mechanism that permits the nodes to have 115 different transmission probabilities, which are consistent with their 116 transmission history, removes the listen-only period thus, leading to 117 faster convergence time and implements a new policy for setting the 118 redundancy coefficient. 120 1.1 Terminology 122 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 123 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 124 document are to be interpreted as described in RFC 2119 [RFC2119]. 126 2. Drizzle Algorithm 128 Compared to Trickle, Drizzle has many distinguishing features and 129 different policies enhance routing maintenance in LLNs. Drizzle 130 differs in two major ways. First, the suppression mechanism in 131 Drizzle is adaptive so that the nodes have the capacity to adjust 132 their transmission probability according to their transmission 133 history. This, in one hand, relieves the network administrator from 134 the concern of configuring the redundancy coefficient. On the other 135 hand, it will endorse the fairness of the algorithm, as the nodes 136 that have transmitted more in the previous intervals would have less 137 probability to send in the current interval. The fairness of the 138 algorithm has been further supported by giving each node a 139 transmission slot within each interval also depending on their 140 transmission history. Second, Drizzle eliminates the listen-only 141 period presented in Trickle intervals so that each node can schedule 142 its transmission at any point throughout the interval rather than the 143 second half only. This would enable the nodes to contend in a wider 144 window reducing the collision probability. Another advantage of this 145 primitive is that any change in the network state will have the 146 chance to be propagated more rapidly than in other techniques such as 147 in Trickle algorithm. In this regards, Drizzle uses the same number 148 of parameters used by Trickle and seven maintaining-state variables 149 as described in the following sections. 151 2.1 Drizzle Variables 153 - s: Number of sent messages until the algorithm reset its interval to 154 the minimum interval. 155 - n: Number of intervals between two resets. 157 - R: A flag (0 or 1) according to the case that produced inconsistency 158 state. 160 - ck: Current value of the redundancy coefficient. 162 - I: Length of the current interval. 164 - t: A randomly chosen time within the current interval to transmit at. 166 - c: Message counter to keep a track of number of received consistent 167 messages within the current interval. 169 2.1 Drizzle Parameters 170 Drizzle uses the following parameters: 172 - The minimum interval length (Imin): This is the fastest transmission 173 rate in time units that a node should transmit at when inconsistency 174 in the network has been discovered. 176 - The maximum interval length (Imax): This is the slowest transmission 177 rate in time units that a node should transmit at when the network 178 reaches its steady phase. 180 - The redundancy factor (K): represents the number of received 181 consistent messages that a node should receive during one interval 182 before suppressing its own transmission. 184 2.1 Drizzle Operations 186 Drizzle is executed over eight steps: 188 - Step 1: Drizzle starts its operations by setting its first interval 189 to "Imin", and the redundancy value "ck" to the initial value of the 190 redundancy coefficient "k". It also sets the broadcast messages 191 number "s" and the consistency counter "c" to 0. Finally, it sets the 192 "R" and the number of intervals "n" to 1. 194 - Step 2: On the beginning of each interval "I", Drizzle assigns a 195 randomly selected value in the interval to the variable "t" taken 196 from the range: [s * I/n, (s + 1) * I/n]. 198 - Step 3: Upon receiving a consistent message, Drizzle increments its 199 consistency counter by one. 200 - Step 4: When a node running Drizzle detects inconsistency state, 201 Drizzle resets its timer by setting I to "Imin", if it was not 202 already set, resets the interval counter "c" and the message counter 203 "s" to 0 while it resets the value of interval counter "n" to 1. It 204 also sets the value of the "R" to either one or 0 according to the 205 case that produced the inconsistency. We limit the cases in which the 206 "R" is set to 1 to only three cases: 208 * (a) when the root establishes the construction of the DODAG, 209 * (b) when the root initiates a global repair, 210 * and (c) when a node firstly joins the DODAG. 212 - Step 5: At the randomly selected time "t", if the counter "c" is 213 less than the redundancy coefficient "ck", Drizzle transmits its 214 scheduled message, otherwise, the message is suppressed. At this time 215 Drizzle also resets the consistency counter "c" to 0. 217 - Step 6: If the scheduled message has been transmitted, Drizzle 218 increases the broadcasted messages number "s" by a value of 1. It 219 also decrements the redundancy coefficient current value by 1. If the 220 value of "ck" would be less than 0, Drizzle sets it to 0. 222 - Step 7: If the scheduled message has been suppressed, Drizzle 223 increments the redundancy coefficient current value by 1. If the 224 value of "ck" would exceed the initial value of the redundancy 225 coefficient "k", Drizzle sets it to "k". 227 - Step 8: Finally, once the interval "I" expires, Drizzle decreases its 228 transmission rate through doubling the length of the interval 229 providing that the "R" value is 1. If the value of the "R" is equal 230 to 0, Drizzle decreases its transmission rate through entering 231 directly the slowest transmission rate. In all cases, if the size of 232 the new interval would exceed "Imax". Drizzle sets the interval size 233 "I" to "Imax" and re-executes the steps from Step 2. The interval 234 counter "n" is increased by 1. 236 3 Security Considerations 238 Since the routing metrics/constraints are carried within RPL message, 239 the security routing mechanisms defined in [RFC6550] apply here. 241 4 References 243 4.1 Normative References 245 [RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J. 246 Kelsey, R., Levis, P., Pister, K., Struik, R., 247 Vasseur,JP., and R. Alexander, "RPL: IPv6 Routing Protocol 248 for Low-Power and Lossy Networks", RFC 6550, March 2012. 250 [RFC6552] Thubert, P., Ed., "Objective Function 0 for the Routing 251 Protocol for Low-Power and Lossy Networks (RPL)", RFC 252 6552, March 2012. 254 [RFC6719] Gnawali, O. and P. Levis, "The Minimum Rank with 255 Hysteresis Objective Function", RFC 6719, DOI 256 10.17487/RFC6719, September 2012. 258 [RFC6551] Vasseur, J., Ed., Kim, M., Ed., Pister, K., Dejean, N., 259 and D. Barthel, "Routing Metrics Used for Path Calculation 260 in Low-Power and Lossy Networks", RFC 6551, March 2012. 262 [RFC 6206] P. Levis, T. Clausen, J. Hui, O. Gnawali, and J. Ko, "The 263 Trickle algorithm," RFC 6206, Internet Engineering Task 264 Force (IETF), 2011 266 4.2 Informative References 268 [1] L. Praditasnee, Y.-C. Tian, and D. Jayalath, "Efficient route 269 update and maintenance processes for multipath routing in large- 270 scale industrial wireless sensor networks," in Telecommunication 271 Networks and Applications Conference (ATNAC), 2012 Australasian, 272 2012, pp. 1-6. 274 [2] C. Vallati and E. Mingozzi, "Trickle-F: Fair broadcast suppression 275 to improve energy-efficient route formation with the RPL routing 276 protocol,"in Sustainable Internet and ICT for Sustainability 277 (SustainIT), 2013,2013, pp. 1-9. 279 [3] B. Djamaa and M. Richardson, "Optimizing the Trickle 280 Algorithm,"IEEE Communications Letters, vol. 19, no. 5, pp. 819- 281 822, May 2015. 283 [4] B. Ghaleb, A. Al-Dubai, I. Romdha, Y. Nasser and A. Boukerche, 284 "Drizzle: Adaptive and fair route maintenance algorithm for Low- 285 power and Lossy Networks in IoT," 2017 IEEE International 286 Conference on Communications (ICC), Paris, 2017, pp. 1-6. 288 Authors' Addresses 290 Baraq Ghaleb (Editor) 291 Edinburgh Napier Universty 292 10 Colinton Road, EH10 5DT, Edinburgh, UK 293 EMail: b.ghaleb@napier.ac.uk 295 Ahmed Al-Dubai 296 Edinburgh Napier Universty 297 10 Colinton Road, EH10 5DT, Edinburgh, UK 298 Phone: +44 131 455 2796 299 EMail: a.al-dubai@napier.ac.uk 301 Imed Romdhani (Editor) 302 Edinburgh Napier Universty 303 10 Colinton Road, EH10 5DT, Edinburgh, UK 304 Phone: +44 131 455 2726 305 EMail: i.romdhani@napier.ac.uk 307 Mamoun Qasem 308 Edinburgh Napier Universty 309 10 Colinton Road, EH10 5DT, Edinburgh, UK 310 EMail: m.qasem@napier.ac.uk