[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00

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]


Html markup produced by rfcmarkup 1.127, available from https://tools.ietf.org/tools/rfcmarkup/