ROLL INTERNET-DRAFT B.Ghaleb Intended Status: Standards Track A.Al-Dubai Expires: September 23, 2018 I.Romdhani M.Qasem Edinburgh Napier University March 22, 2018 Drizzle Algorithm draft-baraq-roll-drizzle-00 Abstract Trickle algorithm used in RPL routing protocol suffers from some issues related to power, network convergence time and overhead and load-distribution. To optimize this algorithm for Low-power and Lossy Networks (LLNs), a new algorithm called Drizzle is introduced. Drizzle uses an adaptive suppression mechanism that permits the nodes to have different transmission probabilities, which are consistent with their transmission history. Compared to Trickle, Drizzle removes the listen-only period from Drizzle's intervals, thus, leading to faster convergence time. Furthermore, a new policy for setting the redundancy coefficient has been used to mitigate the negative effect of the short-listen problem presented when removing the listen-only period and to further boost the fairness in the network. Status of this Memo This Internet-Draft is submitted to IETF in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet-Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/1id-abstracts.html Ghaleb, et al. Expires September 23, 2018 [Page 1] INTERNET DRAFT Drizzle Algorithm March 22, 2018 The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html Copyright and License Notice Copyright (c) 2018 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents carefully, as they describe your rights and restrictions with respect to this document. Code Components extracted from this document must include Simplified BSD License text as described in Section 4.e of the Trust Legal Provisions and are provided without warranty as described in the Simplified BSD License. Table of Contents 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.1 Terminology . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Drizzle Algorithm . . . . . . . . . . . . . . . . . . . . . . 4 2.1 Drizzle Variables . . . . . . . . . . . . . . . . . . . . . 4 2.1 Drizzle Parameters . . . . . . . . . . . . . . . . . . . . . 4 2.1 Drizzle Operations . . . . . . . . . . . . . . . . . . . . . 5 3 Security Considerations . . . . . . . . . . . . . . . . . . . . 7 4 References . . . . . . . . . . . . . . . . . . . . . . . . . . 7 4.1 Normative References . . . . . . . . . . . . . . . . . . . 7 4.2 Informative References . . . . . . . . . . . . . . . . . . 7 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 8 Ghaleb, et al. Expires September 23, 2018 [Page 2] INTERNET DRAFT Drizzle Algorithm March 22, 2018 1 Introduction A key design principle of any routing protocol is to have an efficient mechanism for disseminating routing information through the network, and maintaining up-to-date information. One of the mechanisms to perform this task is to periodically propagate the routing information so often which is widely used in unconstrained wired networks. A major issue with adopting this approach is the high volume of traffic overhead that may affect negatively the performance of the resource-constrained large-scale LLNs [1]. The simplicity of route update and maintenance adopted by those routing protocols is the primary reason behind this issue. This is because that routing information must be propagated periodically by each sensor node even in the case when there is no a significant change in the state of the network [1]. A recent and more efficient approach is the one standardized by the IETF ROLL group to regulate the emission of routing information in LLNs, namely, Trickle algorithm [RFC 6206]. The basic idea behind Trickle is to equip resource-constrained nodes with a simple and energy-efficient primitive for disseminating routing information throughout the network. Trickle uses two mechanisms to achieve this goal. The first mechanism is to adaptively increase the signaling rate upon detecting new routing information. In contrast, it exponentially reduces the signaling rate when the network state is up-to-date in order to save energy and bandwidth. The second is the suppression mechanism in which a node suppresses the transmission of its routing information if detected that enough number of its neighbors have transmitted the same piece of information. The main issue with Trickle is that it is mainly developed for code propagation which in one way or another has different characteristics in comparison with routing maintenance in a routing protocol [2]. Specifically , Trickle has some issues related to its convergence time and fairness as detailed in [3][4] To alleviate Trickle issues, an enhanced algorithm for disseminating routing information in LLNs is proposed. The proposed Drizzle algorithm attempts to address the limitations of the previous algorithms and in particular Trickle algorithm. Drizzle offers an adaptive suppression mechanism that permits the nodes to have different transmission probabilities, which are consistent with their transmission history, removes the listen-only period thus, leading to faster convergence time and implements a new policy for setting the redundancy coefficient. 1.1 Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this Ghaleb, et al. Expires September 23, 2018 [Page 3] INTERNET DRAFT Drizzle Algorithm March 22, 2018 document are to be interpreted as described in RFC 2119 [RFC2119]. 2. Drizzle Algorithm Compared to Trickle, Drizzle has many distinguishing features and different policies enhance routing maintenance in LLNs. Drizzle differs in two major ways. First, the suppression mechanism in Drizzle is adaptive so that the nodes have the capacity to adjust their transmission probability according to their transmission history. This, in one hand, relieves the network administrator from the concern of configuring the redundancy coefficient. On the other hand, it will endorse the fairness of the algorithm, as the nodes that have transmitted more in the previous intervals would have less probability to send in the current interval. The fairness of the algorithm has been further supported by giving each node a transmission slot within each interval also depending on their transmission history. Second, Drizzle eliminates the listen-only period presented in Trickle intervals so that each node can schedule its transmission at any point throughout the interval rather than the second half only. This would enable the nodes to contend in a wider window reducing the collision probability. Another advantage of this primitive is that any change in the network state will have the chance to be propagated more rapidly than in other techniques such as in Trickle algorithm. In this regards, Drizzle uses the same number of parameters used by Trickle and seven maintaining-state variables as described in the following sections. 2.1 Drizzle Variables - s: Number of sent messages until the algorithm reset its interval to the minimum interval. - n: Number of intervals between two resets. - R: A flag (0 or 1) according to the case that produced inconsistency state. - ck: Current value of the redundancy coefficient. - I: Length of the current interval. - t: A randomly chosen time within the current interval to transmit at. - c: Message counter to keep a track of number of received consistent messages within the current interval. 2.1 Drizzle Parameters Ghaleb, et al. Expires September 23, 2018 [Page 4] INTERNET DRAFT Drizzle Algorithm March 22, 2018 Drizzle uses the following parameters: - The minimum interval length (Imin): This is the fastest transmission rate in time units that a node should transmit at when inconsistency in the network has been discovered. - The maximum interval length (Imax): This is the slowest transmission rate in time units that a node should transmit at when the network reaches its steady phase. - The redundancy factor (K): represents the number of received consistent messages that a node should receive during one interval before suppressing its own transmission. 2.1 Drizzle Operations Drizzle is executed over eight steps: - Step 1: Drizzle starts its operations by setting its first interval to "Imin", and the redundancy value "ck" to the initial value of the redundancy coefficient "k". It also sets the broadcast messages number "s" and the consistency counter "c" to 0. Finally, it sets the "R" and the number of intervals "n" to 1. - Step 2: On the beginning of each interval "I", Drizzle assigns a randomly selected value in the interval to the variable "t" taken from the range: [s * I/n, (s + 1) * I/n]. - Step 3: Upon receiving a consistent message, Drizzle increments its consistency counter by one. - Step 4: When a node running Drizzle detects inconsistency state, Drizzle resets its timer by setting I to "Imin", if it was not already set, resets the interval counter "c" and the message counter "s" to 0 while it resets the value of interval counter "n" to 1. It also sets the value of the "R" to either one or 0 according to the case that produced the inconsistency. We limit the cases in which the "R" is set to 1 to only three cases: * (a) when the root establishes the construction of the DODAG, * (b) when the root initiates a global repair, * and (c) when a node firstly joins the DODAG. - Step 5: At the randomly selected time "t", if the counter "c" is less than the redundancy coefficient "ck", Drizzle transmits its scheduled message, otherwise, the message is suppressed. At this time Drizzle also resets the consistency counter "c" to 0. - Step 6: If the scheduled message has been transmitted, Drizzle Ghaleb, et al. Expires September 23, 2018 [Page 5] INTERNET DRAFT Drizzle Algorithm March 22, 2018 increases the broadcasted messages number "s" by a value of 1. It also decrements the redundancy coefficient current value by 1. If the value of "ck" would be less than 0, Drizzle sets it to 0. - Step 7: If the scheduled message has been suppressed, Drizzle increments the redundancy coefficient current value by 1. If the value of "ck" would exceed the initial value of the redundancy coefficient "k", Drizzle sets it to "k". - Step 8: Finally, once the interval "I" expires, Drizzle decreases its transmission rate through doubling the length of the interval providing that the "R" value is 1. If the value of the "R" is equal to 0, Drizzle decreases its transmission rate through entering directly the slowest transmission rate. In all cases, if the size of the new interval would exceed "Imax". Drizzle sets the interval size "I" to "Imax" and re-executes the steps from Step 2. The interval counter "n" is increased by 1. Ghaleb, et al. Expires September 23, 2018 [Page 6] INTERNET DRAFT Drizzle Algorithm March 22, 2018 3 Security Considerations Since the routing metrics/constraints are carried within RPL message, the security routing mechanisms defined in [RFC6550] apply here. 4 References 4.1 Normative References [RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J. Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur,JP., and R. Alexander, "RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks", RFC 6550, March 2012. [RFC6552] Thubert, P., Ed., "Objective Function 0 for the Routing Protocol for Low-Power and Lossy Networks (RPL)", RFC 6552, March 2012. [RFC6719] Gnawali, O. and P. Levis, "The Minimum Rank with Hysteresis Objective Function", RFC 6719, DOI 10.17487/RFC6719, September 2012. [RFC6551] Vasseur, J., Ed., Kim, M., Ed., Pister, K., Dejean, N., and D. Barthel, "Routing Metrics Used for Path Calculation in Low-Power and Lossy Networks", RFC 6551, March 2012. [RFC 6206] P. Levis, T. Clausen, J. Hui, O. Gnawali, and J. Ko, "The Trickle algorithm," RFC 6206, Internet Engineering Task Force (IETF), 2011 4.2 Informative References [1] L. Praditasnee, Y.-C. Tian, and D. Jayalath, "Efficient route update and maintenance processes for multipath routing in large- scale industrial wireless sensor networks," in Telecommunication Networks and Applications Conference (ATNAC), 2012 Australasian, 2012, pp. 1-6. [2] C. Vallati and E. Mingozzi, "Trickle-F: Fair broadcast suppression to improve energy-efficient route formation with the RPL routing protocol,"in Sustainable Internet and ICT for Sustainability (SustainIT), 2013,2013, pp. 1-9. [3] B. Djamaa and M. Richardson, "Optimizing the Trickle Ghaleb, et al. Expires September 23, 2018 [Page 7] INTERNET DRAFT Drizzle Algorithm March 22, 2018 Algorithm,"IEEE Communications Letters, vol. 19, no. 5, pp. 819- 822, May 2015. [4] B. Ghaleb, A. Al-Dubai, I. Romdha, Y. Nasser and A. Boukerche, "Drizzle: Adaptive and fair route maintenance algorithm for Low- power and Lossy Networks in IoT," 2017 IEEE International Conference on Communications (ICC), Paris, 2017, pp. 1-6. Authors' Addresses Baraq Ghaleb (Editor) Edinburgh Napier Universty 10 Colinton Road, EH10 5DT, Edinburgh, UK EMail: b.ghaleb@napier.ac.uk Ahmed Al-Dubai Edinburgh Napier Universty 10 Colinton Road, EH10 5DT, Edinburgh, UK Phone: +44 131 455 2796 EMail: a.al-dubai@napier.ac.uk Imed Romdhani (Editor) Edinburgh Napier Universty 10 Colinton Road, EH10 5DT, Edinburgh, UK Phone: +44 131 455 2726 EMail: i.romdhani@napier.ac.uk Mamoun Qasem Edinburgh Napier Universty 10 Colinton Road, EH10 5DT, Edinburgh, UK EMail: m.qasem@napier.ac.uk Ghaleb, et al. Expires September 23, 2018 [Page 8]