roll
Internet-Draft M.Qasem
Intended Status: Standards Track A.Al-Dubai
Expires: August 10, 2017 I.Romdhani
B.Ghaleb
Edinburgh Napier University
February 6, 2017
Load Balancing Objective Function in RPL
draft-qasem-roll-rpl-load-balancing-00
Abstract
This document proposes an extended Objective Function(OF) that
balances the number of children nodes of the parent nodes to avoid
the overloading problem and ensure node lifetime maximization in the
IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL). The
standard OFs are used to build a Destination Oriented Directed
Acyclic Graph (DODAG) where the bottleneck nodes may suffer from
unbalanced traffic load. As a result, a part of the network may be
disconnected as the energy of the overloaded preferred parent node
will drain much faster than other candidate parents. Thus, a new RPL
metric has been introduced to balance the traffic load over the
network. The potential extra overhead has been mitigated using a new
utilization technique. Finally, the proposed OF amends the DODAG
Information Object (DIO) message format.
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
Qasem, et al. Expires August 10, 2017 [Page 1]
INTERNET DRAFT Load Balancing OF for RPL February 6, 2017
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
Copyright and License Notice
Copyright (c) 2017 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 DODAG construction in a nutshell . . . . . . . . . . . . . . . 4
3 Load balancing in RPL . . . . . . . . . . . . . . . . . . . . . 4
4 The proposed objective function . . . . . . . . . . . . . . . . 6
4.1 Balancing the load traffic . . . . . . . . . . . . . . . . . 6
4.2 A new utilization technique for the amended DIO . . . . . . 6
4.3 The amended DIO message . . . . . . . . . . . . . . . . . . 7
5 Security Considerations . . . . . . . . . . . . . . . . . . . . 7
6 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 7
7 References . . . . . . . . . . . . . . . . . . . . . . . . . . 8
7.1 Normative References . . . . . . . . . . . . . . . . . . . 8
7.2 Informative References . . . . . . . . . . . . . . . . . . 9
Appendix A. . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 9
Qasem, et al. Expires August 10, 2017 [Page 2]
INTERNET DRAFT Load Balancing OF for RPL February 6, 2017
1 Introduction
IPv6 Routing Protocol for LLNs (RPL) [RFC6550] defined two OFs to
optimize the path selection towards the root node, namely, the OF
zero (OF0) [RFC6552], and the Minimum Rank with Hysteresis OF
(MRHOF)[RFC6719]. The Destination Oriented Directed Acyclic Graph
(DODAG) construction is built by the RPL OF, that specify how nodes
select the preferred parent node by translating one or more metrics
into the rank value.
The used OF calculates the rank based on some routing metrics [RFC
6551] such as hop-count, delay, energy, and so forth. The parent node
in RPL can serve more than one child if it is chosen by them as
preferred parent. Consequently, the overloaded preferred parents will
become fragile nodes as their energy risks to drain much quicker than
other nodes.
Having conducted simulation experiments and rigours analysis, it is
concluded that the current OFs lead to build a topology that suffers
from an unbalanced load traffic in bottleneck nodes especially for
the first hop nodes (i.e., from the root). Consequently, this problem
has a crucial impact on the lifetime of these types of nodes. The
battery depletion of that overloaded parent node may affect the
network reliability negatively.
This challenging problem is still an open issue. In an attempt to
overcome this problem, this draft proposes a new OF to mitigate the
overusing of the bottleneck node to prolong its battery lifetime.
This draft proposes an extended Objective Function(OF) that balances
the number of children nodes for the overloaded nodes to ensure node
lifetime maximization in RPL and can be summarized as follows. First,
a new RPL metric has been used to balance the load traffic among the
bottleneck nodes. Second, the DODAG Information Object (DIO) message
has been amended by injecting the IP address of the chosen parent
before broadcasting it. Third, a new utilization technique has been
proposed for the amended DIO message to avoid increasing the overhead
of the handshaking and acknowledgment processes. Simulation
experiments have been conducted to validate the extended OF
performance as detailed in Appendix A.
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].
Qasem, et al. Expires August 10, 2017 [Page 3]
INTERNET DRAFT Load Balancing OF for RPL February 6, 2017
2 DODAG construction in a nutshell
RPL is a proactive distance vector routing protocol designed for LLNs
[RFC6550], it constructs a DODAG using a certain OF that suits the
application requirements. Essentially, RPL relies on a DODAG
Information Object (DIO) control message to build the DODAG.
Thus, the starting point begins when the root node broadcasts the DIO
message to the downstream neighbor nodes. As soon as the closest node
receives the message, it can decide whether to join this DODAG or not
based on the calculated rank according to the equations (1) and (2)
[RFC6719].
Rank(N) = Rank(PN) + RankIncrease (1)
RankIncrease = Step * MinHopRankIncrease (2)
Where Step represents a scalar value and MinHopRankIncrease
represents the minimum RPL parameter. If the node decides to join,
then it adds the DIO sender to the candidate parent list. Next, the
preferred parent, i.e. the next hop to the root, will be chosen based
on the rank from this list to receive all traffic from the child
node. Then, it computes its own rank with a monotonical increase
according to the selected OF.
After that, the node propagates its own DIO with all updated
information to all its neighbors including the preferred parent. [RFC
6551] defined the number of node metrics/constraints (e.g. hop count
and energy) and the link metrics/constraints (e.g. ETX and
throughput) that might be used in the OFs [RFC6552][RFC6719].
3 Load balancing in RPL
RPL is designed with several robust features such as exiguous delay,
quick configuration, loop-free topology, and self-healing. However,
the load imbalance is considered as a significant weakness in this
protocol. More specifically, RPL is dealing with non-uniform
distribution in large-scale LLNs, which may lead to unequal data
traffic distribution. Consequently, the energy of the overloaded
nodes will be drained much faster than other nodes. Furthermore, this
problem has more harmful impacts if the overloaded node is a
bottleneck node (i.e. with the first hop to the root) as shown in
Figure 1 for node A and B.
Qasem, et al. Expires August 10, 2017 [Page 4]
INTERNET DRAFT Load Balancing OF for RPL February 6, 2017
------+---------
| Internet
|
+-----+
| | Border Router
| | (RPL Root)
+-----+
|
o N / \
o o M F A B
o o G E C D H
o o P R J K o o o
o o o o o o
o o o o
o o o
o o o
Figure 1: Bottleneck nodes in RPL
Figure 2 depicts the selection of the preferred parent for those nodes
are within the first hop from nodes A or B. Clearly, node A has more
children as it is surrounded by the nodes (N,M,F,G,E,P). Despite the
fact that A has more children, it dominates the shred nodes (C,D,R,J)
that are also located within the shared area of node B (i.e., within the
transmission range of A and B). That unbalanced parent selection
approach in RPL left node B only with two children, while node A has ten
children.
+----------------------------------------------------+
| Parent | Children nodes | Shared nodes |
| nodes | |between A and B |
|----------------------------------------------------|
| A | N,M,F,G,E,P,C,D.R,J | C,D,R,J |
|----------------------------------------------------|
| B | H,K | C,D,R,J |
+----------------------------------------------------+
Figure 2: The selection of the preferred parents
It is notable that the connection of all nodes through A is fragile as
it is the only link to the root with an overloaded bottleneck node,
thus, disconnecting part of the network if node A dies. In particular,
this serious problem occurs in RPL due to omitting the number of
children in existing parent selection technique.
Qasem, et al. Expires August 10, 2017 [Page 5]
INTERNET DRAFT Load Balancing OF for RPL February 6, 2017
To this end, the node sticks with the current preferred parent and
influences its rank, even if this parent deteriorates with more load
(i.e. being a parent for more children). The only conceivable scenarios
to change the current parent to another candidate parent are as follow:
first, if the current parent dies due to battery depletion. The second
possibility, when the lossy percentage becomes higher than before, so no
acknowledgement message can be heard from the preferred parent for a
certain period of time.
4 The proposed objective function
The proposed OF leverages the lifetime of the entire network. The load
balanced OF (LB-OF) balances the data traffic by taking into account the
number of children for each candidate parent.
4.1 Balancing the load traffic
As aforementioned, being a preferred parent for more children means more
overhead and unbalanced load, thus leads to drain its own energy much
faster than other candidate parents. To solve this problem, a new metric
has been proposed. The children set created in section 4.2 provides each
preferred parent with the number of children it has. Based on that, the
number of children in the rank calculation in formula (1) is
considered.
Specifically, the parent with the least number of children will be
elected as preferred parent. To this end, the balance has been achieved
by declining the number of children of the overloaded bottleneck node.
As a result, the majority of children (i.e., the shared nodes between A
and B) will choose another preferred parent according to the lower rank,
and surely has less number of children.
4.2 A new utilization technique for the amended DIO
Generally, in the upward routes the root initiates the DODAG
construction by sending the first DIO message. Once other nodes receive
this DIO, they select the sender as a preferred parent, and then they
start calculating their own ranks based on the assigned OF. After that,
each node broadcasts its own DIO message (i.e. the updated DIO that
contains the new calculated rank value) to all neighbors including the
chosen preferred parent which sent the original DIO message. In the
standard OFs, the preferred parent ignores the DIOs that come from its
child based on the rank.
In this stage, the aim is to allow each parent to count its number of
children to avoid later possible overloading situations. However, that
Qasem, et al. Expires August 10, 2017 [Page 6]
INTERNET DRAFT Load Balancing OF for RPL February 6, 2017
is not possible in the upward routes (i.e., while maintaining the DODAG
through DIOs), as the only control message that can be acknowledged by
the destination is the Destination Advertisement Object (DAO) message in
the downward routes to recognize the number of children for each
parent.
Alternatively, a handshaking mechanism between parent and children can
be set up to count the number of children for each parent, but this also
brings an extra overhead for the entire network and subsequently
increases the power consumption massively. To overcome this problem, LB-
OF using a new technique is proposed as detailed below. In LB-OF
algorithm, the received DIO from the child node is counted by the
preferred parent node using a special buffer (set) created for this
purpose. As detailed in section 4.3, the amended DIO contains the IP
address of the chosen preferred parent. Thus, for each received DIO, the
node matches its own IP address with the preferred parent IP address
which is inserted in the DIO message, then increments the number of
children set by one for this node if there is a matching.
Hence, this technique evades increasing the overhead that can be caused
by the handshaking process (which could be used for the entire network).
In addition, the coming DIOs from the children nodes has been utilized
to allow each preferred parent to distinguish the number of its children
during the DODAG construction stage.
4.3 The amended DIO message
Typically, the DIO carries the RPL InstanceID, DODAG identifier, version
number, Rank and the OF that has been used to calculate the rank, in
addition to others identifiers [RFC6550]. The DIO has been amended by
injecting the chosen preferred parent IP address into the propagated DIO
as shown in Figure 3.
5 Security Considerations
Since the routing metrics/constraints are carried within RPL message,
the security routing mechanisms defined in [RFC6550] apply here.
6 IANA Considerations
The IANA defined in [RFC6551] apply here according to [RFC5226].
Qasem, et al. Expires August 10, 2017 [Page 7]
INTERNET DRAFT Load Balancing OF for RPL February 6, 2017
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| RPLInstanceID |Version Number | Rank |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|G|0| MOP | Prf | DTSN | Flags | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ +
| |
+ DODAGID +
| |
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| |
+ +
| |
+ Parent Address +
| |
+ +
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Option(s)...
+-+-+-+-+-+-+-+-+
Figure 3: The amended DIO message format
7 References
7.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 Zero 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.
Qasem, et al. Expires August 10, 2017 [Page 8]
INTERNET DRAFT Load Balancing OF for RPL February 6, 2017
7.2 Informative References
[RFC5226] Narten, T. and H. Alvestrand, "Guidelines for Writing an
IANA Considerations Section in RFCs", BCP 26, RFC 5226,
May 2008.
[Contiki] Contik O.S and cooja simulatoer http://www.contiki-os.org/
Appendix A.
The protocol has been simulated with Cooja simulator based
on Instant Contiki 2.7 operating system [Contiki].
Collected results corroborate the superiority of our OF
over the existing ones in terms of lifetime, power
consumption and packet delivery ratio.
Authors' Addresses
Mamoun Qasem (editor)
Edinburgh Napier University
10 Colinton Road, EH10 5DT, Edinburgh, UK
Phone: +44 131 455 2772
Email: m.qasem@napier.ac.uk
Ahmed Al-Dubai
Edinburgh Napier University
10 Colinton Road, EH10 5DT, Edinburgh, UK
Phone: +44 131 455 2796
Email: a.al-dubai@napier.ac.uk
Imed Romdhani
Edinburgh Napier University
10 Colinton Road, EH10 5DT, Edinburgh, UK
Phone: +44 131 455 2726
Email: i.romdhani@napier.ac.uk
Baraq Ghaleb
Edinburgh Napier University
Qasem, et al. Expires August 10, 2017 [Page 9]
INTERNET DRAFT Load Balancing OF for RPL February 6, 2017
10 Colinton Road, EH10 5DT, Edinburgh, UK
Email: b.ghaleb@napier.ac.uk
Qasem, et al. Expires August 10, 2017 [Page 10]