Internet DRAFT - draft-baraq-roll-lbsa
draft-baraq-roll-lbsa
ROLL
INTERNET-DRAFT B.Ghaleb
Intended Status: Standards Track A.Al-Dubai
Expires: September 23, 2019 I.Romdhani
M.Qasem
Edinburgh Napier University
March 23, 2020
Load-balancing and Stability Aware Objective Function (LBSA)
draft-baraq-roll-lbsa-00
Abstract
The IPv6 Routing Protocol for Low-power and Lossy Networks (RPL) has
been recently standardized as the de facto solution for routing in
the context of the emerging Internet of Things (IoT) paradigm. RPL,
along with other standards, has provided a baseline framework for IoT
that has helped advance communications in the world of embedded
resource-constrained networks. However, RPL still suffers from issues
that may limit its efficiency such as the absence of an efficient
load-balancing primitive. To address this problem, a novel load-
balancing scheme is introduced that ensures a fair distribution of
traffic among nodes while minimizing overhead
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
The list of Internet-Draft Shadow Directories can be accessed at
Ghaleb, et al. Expires September 23, 2019 [Page 1]
INTERNET DRAFT LBSA Objective Function June 10, 2019
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. Load-balancing aware Objective Function . . . . . . . . . . . 3
2.1 The load-balancing metric . . . . . . . . . . . . . . . . . 4
2.1.1 Measuring the Number of Children Metric . . . . . . . . 4
2.2 The Timely Propagation Primitive . . . . . . . . . . . . . . 5
2.3 Avoiding The Herding Problem . . . . . . . . . . . . . . . . 5
3 Security Considerations . . . . . . . . . . . . . . . . . . . . 6
4 References . . . . . . . . . . . . . . . . . . . . . . . . . . 6
4.1 Normative References . . . . . . . . . . . . . . . . . . . 6
4.2 Informative References . . . . . . . . . . . . . . . . . . 6
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 7
Ghaleb, et al. Expires September 23, 2019 [Page 2]
INTERNET DRAFT LBSA Objective Function June 10, 2019
1 Introduction
The standardized Routing Protocol for Low-power and Lossy networks
(RPL) [RFC6550] lacks in an efficient routing primitive that ensures
a fair distribution of traffic among nodes while minimizing overhead.
The absence of such mechanism may prevent the distribution of traffic
among multiple nodes, potentially increasing data loss caused by the
node packet buffer overflow or leading to a faster depletion of the
energy of overloaded nodes which in turn may result in service
disruption [1][2][3][4]. However, poorly implemented load balancing
causes problems too. An example is the herding-effect [1], in which
the network suffers topological instability caused by nodes
repeatedly switching preferred parents in a futile attempt to achieve
load balancing [1]. For instance, in Figure 1a, you can see that six
nodes have selected the lightly loaded parent, A, upon receiving its
DIO. However, in Figure 1b, all six nodes simultaneously changed
their preferred parent to, B, in an attempt to load-balance the
traffic upon receiving a new DIO from that node announcing a fewer
number of children than node A. However, when receiving a new DIO
from node A, the migration reverses, resulting in load oscillation
with no balancing.
+---+ +---+
|LBR| |LBR|
+---+ +---+
/ /\
/ / \
+--+ +--+ Continuous loop +--+ +--+
:A : :B : <--------------> :A : :B :
+--+ +--+ +--+ +--+
/ \
/ \
* * * (Children) * * * (Children)
* * * * * *
(a) (b)
Figure 1: The herding-effect problem
1.1 Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
document are to be interpreted as described in RFC 2119 [RFC2119].
2. Load-balancing aware Objective Function
In order to address the load-balancing problem of RPL, a new load
balancing OF is proposed in this study and discussed in the following
Ghaleb, et al. Expires September 23, 2019 [Page 3]
INTERNET DRAFT LBSA Objective Function June 10, 2019
subsections. We emphasize here that the main goal of the proposed
solution is to introduce a load-balancing mechanism into RPL while
maintaining stability with minimal overhead. In order to achieve this
goal, we articulate that a stable and efficient load-balancing
mechanism should comprise the following sub-components: several steps
as follows: 1) A suitable metric (single or composite) for load-
balancing. 2) A propagation primitive that ensures timely and
efficient propagation of load balancing information before it becomes
obsolete. 3) A routing primitive that mitigates the instability
problem that may arise from introducing load-balancing into the
network.
2.1 The load-balancing metric
Several routing metrics for RPL networks have been proposed in the
literature [RFC6551] including load-balancing metrics such as number
of children, throughput, and queue utilization factor. In this draft,
we opt to use the number of children metric for the purpose of load-
balancing for two primary reasons. First, it can be measured easily
based on the data-plane traffic without incurring any extra overhead
in the control-plane, especially in periodic applications as
discussed next. Second, in the vast majority of applications, it
reflects the actual network load.
2.1.1 Measuring the number of children metric
In this draft, we introduce for the first time the notion of calculating the number of
children based on the data-plane messages rather than relying on
RPL's DAO messages. In fact, number of children can be calculated
based on RPL's DAO messages, however, as these messages are an
optional feature of RPL, they may not be available in all scenarios. To
calculate the number of children based on data-plane traffic, we
exploit the fact that IPv6 data packets carry the source address of
the sender in the header of the packet, in addition to the RPL Hop-
by-Hop (HBH) header option. Hence, when an IPv6 packet is received,
the protocol first determines if it is a control or a data packet by
inspecting if the RPL HBH Option is exist or not. The presence of
such an option indicates that a data packet is being received at the
network layer. If the received packet is data, it inspects its
direction to decide if the sender is a child or not (direction is
specified by the Down flag in the RPL HBH Option). If the packet is
heading upward, the sender is a child so the protocol adds the sender
IP Address (CHIP) to the list of children (CHList) of the receiver.
If no data packets are received from an existing child during a pre-
specified interval, it is removed. This interval is set proportional
to the traffic rate.
Ghaleb, et al. Expires September 23, 2019 [Page 4]
INTERNET DRAFT LBSA Objective Function June 10, 2019
2.2 The Timely Propagation Primitive
The second step towards realizing an efficient load-balancing
objective function is the timely propagation of the routing
information, especially those related to the load-balancing metric
(i.e., number of children). In fact, the propagation of routing
information carried in RPL's DIO messages is regulated by means of
Trickle [RFC6206] in which the DIO transmission rate is increased
upon detecting inconsistencies in the network. For example, the current
implementation of Trickle in Contiki OS has restricted the number of
times the network is declared inconsistent to a few cases to minimize
the control-plane overhead. These cases include global repair, local
repair, and parent change. Here, it is clear that a change in a
node's rank does not trigger a resetting of the Trickle timer, so
some routing decisions might be taken based on obsolete routing
information due to the long DIO transmission period in the consistent
state. Hence, a problematic gap may arise between the time the node
has changed its preferred parent and the scheduled time for the DIO
to be sent at.
To overcome this concern, we have opted to permit the node to declare
an inconsistency upon detecting that its number of children has been
increased or decreased by a pre-specified threshold. This will allow
neighboring nodes to receive the load information in a timely manner,
at the cost of some increased overhead. To reduce the overhead
resulting from resetting the Trickle timer, the protocol does not do
this every time the node's balancing information changes (in terms of
number of children). Instead, it uses a FastPropagation Timer (Reset
Timer): when this expires a node checks whether it should reset its
Trickle timer or not. The propagation of rank information is still
governed by the Trickle algorithm itself.
2.3 Avoiding The Herding Problem
One of the obstacles toward achieving load balancing in RPL is the
way the protocol switches preferred parents. The common strategy
adopted by RPL is to allow a specific node to switch immediately to a
better parent upon detecting such a parent by means of DIOs. This may
have the advantage of timely switching; however, in the context of
load balancing, changing preferred parent immediately on discovery
may give rise to the herding effect explained earlier. To address
this issue, we have introduced the idea of the Balancing Timer (or
Scheduling Timer). This timer regulates the timing of parent
selection process. Instead of having a node performing this process
immediately upon receiving a new DIO, the parent selection in our
proposed mechanism is performed regularly at pre-determined interval.
However, we exclude the first received DIO from this policy to allow
faster convergence time at the stage of DODAG construction. In other
Ghaleb, et al. Expires September 23, 2019 [Page 5]
INTERNET DRAFT LBSA Objective Function June 10, 2019
words, when a node receives a DIO for the first time, it will
immediately choose the sender as its preferred parent. Then, the node
must wait until the expiration of the Balancing Timer in order to
check whether a better parent is available or not so it can change to
a new preferred parent. The Balancing Timer is reset every time the
node performs the parent selection process. The value of the
Balancing Timer should be set in a way that allow for several DIOs to
be received at the node so it can have several candidate parents
which is better to be set empirically. The details of this process is
also illustrated in Algorithm 5-1.
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.
[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] H. S. Kim, J. Paek and S. Bahk, "QU-RPL: Queue utilization based
RPL for load balancing in large scale industrial applications," in
the 12th Annual IEEE International Conference on Sensing,
Communication, and Networking (SECON), Seattle, WA, Jun. 2015, pp.
265-273.
Ghaleb, et al. Expires September 23, 2019 [Page 6]
INTERNET DRAFT LBSA Objective Function June 10, 2019
[2] J. Tripathi and J. C. De Oliveira, "Quantifying load imbalance: A
practical implementation for data collection in low power lossy
networks," 47th Annual Conference on Information Sciences and
Systems (CISS), Baltimore, MD, 2013, pp. 1-6.
[3] X. Liu, J. Guo, G. Bhatti, P. Orlik and K. Parsons, "Load balanced
routing for low power and lossy networks," in the IEEE Wireless
Communications and Networking Conference (WCNC), Apr. 2013,
Shanghai, pp. 2238-2243.
[4] B. Ghaleb, A. Al-Dubai, E. Ekonomou, W. Gharib, L. Mackenzi and M.
Bani Khala, "A New Load-Balancing Aware Objective Function for
RPL's IoT Networks," 2018 IEEE 20th International Conference on
High Performance Computing and Communications; IEEE 16th
International Conference on Smart City; IEEE 4th International
Conference on Data Science and Systems (HPCC/SmartCity/DSS),
Exeter, United Kingdom, 2018, pp. 909-914.
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, 2019 [Page 7]
