Internet DRAFT - draft-baraq-roll-drizzle
draft-baraq-roll-drizzle
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]
