roll
Internet-Draft M.Qasem
Intended Status: Standards Track A.Al-Dubai
Expires: May 2, 2018 I.Romdhani
B.Ghaleb
Edinburgh Napier University
J. Hou
R. Jadhav
Huawei Technologies
October 29, 2017
Load Balancing Objective Function in RPL
draft-qasem-roll-rpl-load-balancing-02
Abstract
This document proposes an extended Objective Function(OF)that
balances the number of child 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. Finally, the
potential extra overhead has been mitigated using a new utilization
technique.
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
Qasem, et al. Expires May 2, 2018 [Page 1]
INTERNET DRAFT Load Balancing OF for RPL October 29, 2017
http://www.ietf.org/1id-abstracts.html
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 DIO message . . . . . . . . 6
4.3 Proposed New Metric for Parent Selection . . . . . . . . . . 7
5 Security Considerations . . . . . . . . . . . . . . . . . . . . 9
6 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 9
7 References . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.1 Normative References . . . . . . . . . . . . . . . . . . . 9
7.2 Informative References . . . . . . . . . . . . . . . . . . 10
Appendix A. . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10
Qasem, et al. Expires May 2, 2018 [Page 2]
INTERNET DRAFT Load Balancing OF for RPL October 29, 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 May 2, 2018 [Page 3]
INTERNET DRAFT Load Balancing OF for RPL October 29, 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 May 2, 2018 [Page 4]
INTERNET DRAFT Load Balancing OF for RPL October 29, 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 | Child 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 May 2, 2018 [Page 5]
INTERNET DRAFT Load Balancing OF for RPL October 29, 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, that results in a 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.
However, it is expected to increase the churn or oscillation as a result
of changing the parent. It is a trade-off between unfairness and
oscillation, however, this oscillation can be minimized in two
techniques to enhance the stability:
a) using the number of children along with another metric(s)(e.g. ETX,
number of hops, energy, etc., according to the application
requirements).
b) Using the hysteresis threshold for the number of children(in a
lexical manner)to switch from parent to another, the selected threshold
depends on the application requirements.
4.2 A new utilization technique for DIO message
Qasem, et al. Expires May 2, 2018 [Page 6]
INTERNET DRAFT Load Balancing OF for RPL October 29, 2017
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
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, setting up an acknowledgement mechanism between parent
and children to count the number of children for each parent. However,
this acknowledgement 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. Each DIO contains the IP
address of the chosen preferred parent as detailed in section 4.3. 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 by ONE for this node if there is a
matching.
Hence, this technique evades increasing any extra overhead,
additionally, the coming DIOs from the child nodes has been utilized to
allow each preferred parent to distinguish the number of its children
during the DODAG construction stage to optimize the routing.
4.3 Proposed New Metric for Parent Selection
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 other identifiers [RFC6550]. This section introduces the
number of child nodes as a new metric/constraint in the DAG Metric
Container, which includes the selected parent address in the option
field within the DIO message. The newly added information is 2 octets
named by Child Node Count (CNC) which is per this document defined in
the DAG Metric Container.
The Child Node Count (CNC) object is used to provide information related
Qasem, et al. Expires May 2, 2018 [Page 7]
INTERNET DRAFT Load Balancing OF for RPL October 29, 2017
to the number of child nodes in the DIO source node, and may be used as
a metric or as constraint.
The CNC object MAY be present in the DAG Metric Container. There MUST
NOT be more than one CNC object as a constraint per DAG Metric
Container, and there MUST NOT be more than one CNC object as a metric
per DAG Metric Container. The format of the CNC object body is as
follows:
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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Flags |P| CNC | CNC_MAX | |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +
| |
+ +
| |
+ Parent Address +
| |
+ +-+-+-+-+-+-+-+-+
| |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3: Child Node Count Object Body Format
Flags field (8 bits). The following one bits of the CNC object are
currently defined:
'P'flag: Parent Address State. This, if set to 1, indicates there is a
parent address field in the CNC object.
CNC: 8-bits. The Child Node Count is encoded in 8 bits in unsigned
integer format, expressed in number count, representing the number of
child nodes.
MAX_CNC: 8-bits. The Maximum Child Node Count is encoded in 8 bits. The
MAX_CNC field indicates the maximum number of children a node can hold.
This parameter is set by implementers based on neighbor cache entry or
the size limit of routing table. Nodes should not hold child nodes more
than MAX_CNC.
Parent Address (optional): 128-bit IPv6 address of parent node. This
field is only present when the'P'flag is set to 1.
In the storing mode, DAO can be used for child nodes registration while
No-PathDAO can be used for de-registration, and this gives a way to
count the number of child nodes. Thus, to minimize traffic load, the
Qasem, et al. Expires May 2, 2018 [Page 8]
INTERNET DRAFT Load Balancing OF for RPL October 29, 2017
Parent Address field in the CNC object should not be present in the
storing mode.
In the non-storing mode, NS/NA could be an optional way for child node
counting. When the 'P' flag is set, the Parent Address in the CNC object
should be used for child node counting according to the technique
illustrated in section 4.2.
When this CNC metric is used, RANK computing reflects the ability of
each node to hold more child nodes. Also, a new way for the RANK
computing has been suggested: RANK = CNC / CNC_MAX * 255. A node with
smaller RANK has high priority to accept new child nodes, a node with
RANK = 255 should not hold new child nodes any more.
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
IANA is requested to allocate a new value for the new metric type "CNC"
in the Routing Metric/Constraint Type in the DAG Metric Container.
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 May 2, 2018 [Page 9]
INTERNET DRAFT Load Balancing OF for RPL October 29, 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 May 2, 2018 [Page 10]
INTERNET DRAFT Load Balancing OF for RPL October 29, 2017
10 Colinton Road, EH10 5DT, Edinburgh, UK
Email: b.ghaleb@napier.ac.uk
Jianqiang Hou (editor)
Huawei Technologies
101 Software Avenue,
Nanjing 210012
China
Phone: +86-15852944235
Email: houjianqiang@huawei.com
Rahul Arvind Jadhav
Huawei Technologies
Kundalahalli Village, Whitefield,
Bangalore, Karnataka 560037
India
Phone: +91-080-49160700
Email: rahul.ietf@gmail.com
Qasem, et al. Expires May 2, 2018 [Page 11]