Internet DRAFT - draft-hou-roll-rpl-parent-selection
draft-hou-roll-rpl-parent-selection
ROLL Working Group J. Hou, Ed.
INTERNET-DRAFT R. Jadhav
Intended Status: Standard Track Z. Luo
Expires: September 13, 2017 Huawei Technologies
March 12, 2017
Optimization of Parent-node Selection in RPL-based Networks
draft-hou-roll-rpl-parent-selection-00
Abstract
This document describes the problems in the DODAG construction of
RPL-based network including "Thundering Herd" problem and Randomly
Unbalanced Networking. The corresponding optimization methods are
proposed to improve balancing the selection of parent nodes.
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). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/.
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."
This Internet-Draft will expire on September 13, 2017.
Copyright 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.
Hou, et al Expires September 13, 2017 [Page 1]
INTERNET DRAFT Parent Selection in RPL Networks March 12, 2017
Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.1. Requirements Notation and Terminology . . . . . . . . . . 3
2. DODAG Construction and Objective Functions . . . . . . . . . . 3
3. Problems with Current DODAG construction . . . . . . . . . . . 4
3.1. Problem 1: "Thundering Herd" Phenomenon . . . . . . . . . 4
3.2. Problem 2: Randomly Unbalanced Network . . . . . . . . . . 5
4. Optimized Solution . . . . . . . . . . . . . . . . . . . . . . 6
4.1. Solution 1: Increment the ETX_Initial value . . . . . . . 6
4.2. Solution 2: Introducing the Child Node Count Metric . . . 7
5. Security Considerations . . . . . . . . . . . . . . . . . . . 9
6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9
7. References . . . . . . . . . . . . . . . . . . . . . . . . . . 9
7.1. Normative References . . . . . . . . . . . . . . . . . . . 9
7.2. Informative References . . . . . . . . . . . . . . . . . . 10
8. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 10
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 10
1. Introduction
IPv6 Routing Protocol for Low-Power and Lossy Networks (RPL) is a
route-over distance vector routing protocol for networks in
constrained conditions such as limited power and bandwidth. This
protocol defines a Destination Oriented Directed Acyclic Graph
(DODAG) to avoid the emergence of loops in the network [RFC 6550].
The routing procedure is based on an objective function (OF)
including a set of metrics/constraints. The selection of the parent
node in the RPL-based network directly influences the networking
balance, and particularly, a poor balance causes the frequent
switches of parent nodes. During the switching process, the delayed
communication directly affects the stability of the entire network,
so networking balance is an important indicator of the stability of
mesh network.
In the RPL-based mesh network, due to the lack of balance algorithm,
a large batch of nodes possibly select the same parent node and leave
others empty, turning this focused parent node to be a forwarding
point. A higher rate of transmission failure will result in a sharp
increment in RANK, which triggers all child nodes to re-select and
switch their parent node, and so on, causing frequent switching of
the parent node. This phenomenon is particularly frequent at the
beginning of networking that greatly decrements the efficiency of
networking and communication stability. Therefore, the mechanism to
select the parent node, making 6LoWPAN reach a balanced mesh network,
is an urgent problem to be solved.
This document points out the problems associated with the RPL-based
Hou, et al Expires September 13, 2017 [Page 2]
INTERNET DRAFT Parent Selection in RPL Networks March 12, 2017
networking, and proposes solutions for optimizing the balance of
parent selection problems. Modifications are incrementing the RANK
default value and introducing a new metric called "Child Node Count".
1.1. Requirements Notation and Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in
[RFC2119].
Below are the terms used in this document:
6LBR: 6Lo Border Router
6LN: 6Lo Node
CNC: Child Node Count
DAO: Destination Advertisement Object
DIO: DODAG Information Object
ETX: Expected Transmission Time
MOP: Mode of Operation
MRHOF: Minimum Rank with Hysteresis Objective Function
OP0: Objective Function Zero
RSSI: Received Signal Strength Indicator
2. DODAG Construction and Objective Functions
In general, an RPL-based network consists of three types of nodes:
root node, connecting to another network as a gateway; router,
forwarding topology information and data packets to their neighbors;
leaf node, only joining a DODAG as an end member. The construction
of a DODAG starts at the root node, through the routers, down to the
leaf nodes. The root node broadcasts to its sub-nodes the DODAG
Information Object (DIO) messages that contain the RANK information.
Once receiving DIO messages, a sub-node chooses the node with the
minimum RANK as its appropriate parent node. Afterwards, the routers
will compute their own RANK according to the Objective Function (OF),
update the DIO message, and forward to their neighbors.
Objective Function Zero (OF0) is designed as a default OF that allows
Hou, et al Expires September 13, 2017 [Page 3]
INTERNET DRAFT Parent Selection in RPL Networks March 12, 2017
interoperation between implementations in a wide spectrum of use
cases [RFC 6552]. OF0 specifies that a node calculates its own RANK
R(N) according to the following equation:
R(N) = R(P) + rank_increase (1)
where rank_increase = (Rf * Sp + Sr) * MinHopRankIncrease (Rf,
Rank_Factor; Sp, Step_of_Rank; Sr, Stretch_of_Rank). R(P) is the
RANK of the parent node.
Apart from OF0, the Minimum Rank with Hysteresis Objective Function
(MRHOF) is another OF that selects routes that minimize a metric.
One common metric used in OF is the Expected Transmission Count
(ETX), indicating the number of transmissions a node expects to make
to a destination in order to successfully deliver a packet [RFC
6551]. When MRHOF uses ETX as its metric, nodes locally compute the
ETX of links to its neighbors and add this value to their advertised
Rank to compute the associated Rank of routes [RFC 6719]. In this
case, the calculation of RANK can be simplified to be equation
R(N) = R(P) + ETX(N) * 128 (2)
where ETX(N) is the ETX of links to its parent node. The ETX value
normally follows an update formula
ETX = ETX_Old * 0.9 + ETX_New * 0.1 (3)
where ETX_Old is the previous ETX value, and ETX_New is calculated by
ETX= 1 / (Df * Dr) in which Df is the measured probability that a
packet is received by the neighbor and Dr is the measured probability
that the acknowledgment packet is successfully received [RFC 6551].
Once a node joins an RPL network with a default value ETX(N), e.g.
1*R, the ETX gradually converges to the actual value after several
times of update.
3. Problems with Current DODAG construction
3.1. Problem 1: "Thundering Herd" Phenomenon
When a node joins the RPL-based network (such as 6LN_New in Figure
1), the transmission path may be better than other nodes because the
Default_Rank_Increase is 3*256, calculated by equation (1) with the
following default values specified in [RFC 6552]:
DEFAULT_MIN_HOP_RANK_INCREASE = 256
DEFAULT_STEP_OF_RANK: 3
Hou, et al Expires September 13, 2017 [Page 4]
INTERNET DRAFT Parent Selection in RPL Networks March 12, 2017
DEFAULT_RANK_STRETCH: 0
DEFAULT_RANK_FACTOR: 1
Suppose the RANK of 6LN in Figure 1 is much higher than 4*256 and
meets the requirement of parent switching when 6LN_New joins. Then
once 6LN_New broadcasts the DIO messages including the RANK value of
4*256 (1*256 for Root_Rank; 3*256 for Rank_Increase), it may trigger
a switch of numerous child nodes (circles in Figure 1) from their
original parent nodes. Note that the dashed box depicted in Figure 1
is the common coverage of 6LN and 6LN_New. So once a new node joins
a network with a small RANK default value, it may suddenly attract
numerous sub-nodes, impacting on the stability of the network. This
phenomenon is called "Thundering Herd".
6LBR
/\
/ \
/ \
6LN \
/|\ 6LN_New
/ | \ /|\
+ - - - - - - - - +
| o o o o o o o o | Numerous
| o o o o o |
| o o o o o | 6LNs
| o o o o |
+ - - - - - - - - +
Figure 1: Example of Network Topology of "Thundering Herd"
3.2. Problem 2: Randomly Unbalanced Network
Although the RANK in DIO messages reflects various features of the
network quality (e.g. Hop_Count, Latency, ETX), there is another
issue waiting to be solved: balancing the parent selection among
nodes with the same RANK value. Currently in this case a node
randomly chooses one as its parent node from the candidate parents
with the same RANK, which gives the possibility of unbalanced
networking. As depicted in Figure 2, the RANK of node A, B and C are
supposed to be equal, but node B by chance dominates in the number of
child nodes even though they share the common coverage (dashed
square). It is a waste of resource that Node A is left empty while
reachable for the sub-nodes. After a long period of time, the
network only achieves a relative balance which is easy to be broken
when new nodes join in.
This problem is particularly serious when the unbalanced networking
Hou, et al Expires September 13, 2017 [Page 5]
INTERNET DRAFT Parent Selection in RPL Networks March 12, 2017
happens near the root node and above a large number of sub-nodes.
Suppose in Figure 2 there are numerous child nodes connected to node
D, E, F, G, and H, which put high load pressure on node B and C. In
this case, overload and traffic block are likely to happen near the
root, which further forces the network structure conversion. Node D,
E, F may switch their parent node after network reconstruction but
the best solution is achieving a balance in the parent selection at
the beginning of the networking.
6LBR
/|\
/ | \
/ | \
/ | \
A B C
+ - - - - - - +
| /|\ /| |
| / | \/ | |
| / | /\ | |
| D E/ F| |
| / | |
| H G |
+ - - - - - - +
Figure 2: Example of Randomly Unbalanced Network Topology
4. Optimized Solution
4.1. Solution 1: Increment the ETX_Initial value
In order to reduce the impact of the Thundering Herd phenomenon in
the network, the Default_Step_of_Rank value defined in OF0 SHOULD per
this document be incremented to
DEFAULT_STEP_OF_RANK: 4
So the Default_Rank_Increase is 4*256, and then based on the actual
transmission result, the RANK gradually approaches the actual value.
In this way, a new node joining the RPL network is initially set to
be with a larger RANK default value. If transmissions through this
node are of high quality, the RANK of this node will decrement
gradually and attract child nodes one by one, which reduces the
appearance of the Thundering Herd phenomenon. It is worthwhile
noting that this solution is particularly applicable for the
scenarios with numerous nodes and high node density.
This modification is also suitable for the MRHOF. Take ETX metric
for an example: the default ETX(N) according to the modification
Hou, et al Expires September 13, 2017 [Page 6]
INTERNET DRAFT Parent Selection in RPL Networks March 12, 2017
SHALL be set to 8, which gives R(N) = R(P) + 8*128 according to
equation (2). The high initial RANK lowers the possibility of
Thundering Herd phenomenon while afterwards the RANK gradually
converges to the actual value according to equation (3).
4.2. Solution 2: Introducing the Child Node Count Metric
In order to optimize the randomly unbalanced networking, this
document proposes a method: introducing the number of child nodes as
a new metric/constraint in the DAG Metric Container, which can be
included in the Option field in 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 Routing
Metric/Constraint Type is per this document RECOMMENDED to be value
9.
The Child Node Count (CNC) object is used to provide information
related 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
0 1 2 3 4 5 6 7 8 9 0 1 2 3
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| (sub-object) .....
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3: Child Node Count Object Body Format
0 1
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| CNC | MAX_CNC |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 4: Child Node Count Sub-Object Format
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
Hou, et al Expires September 13, 2017 [Page 7]
INTERNET DRAFT Parent Selection in RPL Networks March 12, 2017
in unsigned integer format, expressed in number count, representing
the maximum number of child nodes allowed in the neighbor cache.
The CNC field gives the number of child nodes while together with the
MAX_CNC field, sub-nodes are able to know the capacity of the
candidate parent nodes, minimizing the need of NACK messages. The
CNC object may be used as a constraint or a path metric. For
example, one may want the CNC not to exceed some value. In this
case, the CNC object common header indicates that the provided value
relates to a constraint. In another example, the CNC object may be
used as an aggregated additive metric where the value is updated
along the path to reflect the number of child nodes along the path.
To solve the Randomly Unbalanced Network addressed in problem 2, this
document proposes a optimization: using a combined metrics of ETX and
CNC in the parent selection process. In this method, Prec field in
the Routing Metric/Constraint Object is used with the following
precedence: ETX > CNC, e.g. Prec of ETX is set to 0 and Prec of CNC
is 1. In this case, the DAG Metric Container carries two Routing
Metric/Constraint objects: one is an ETX metric object with header
(C=0, O=0, A=00, R=0) and the second one is a Child Node Count object
with header (C=0, O=0, A=00, R=0). Since Prec of ETX is set to be 0,
which gives a higher priority, then nodes first choose the candidate
parent nodes with the best link quality according to ETX.
Afterwards, among the candidate parent nodes, the node with minimum
CNC is selected to be the parent node. Note that this method is
applicable for the storing mode of operation in which the nodes
stores the information of their neighbors and thus are able to
calculate the number of child nodes. In addition, when the candidate
parent nodes contain both the same ETX and CNC, the child node SHOUD
randomly choose one as the parent node among them.
This method is applicable for the storing mode of Mode of Operation
(MOP) in which the Destination Advertisement Object (DAO) message is
unicast from the child to the selected parent(s). For the non-
storing mode, the CNC metric/constraint SHOULD NOT be used in the DIO
messages, or if used, the CNC value MUST be set to 0. It is worthy
to note that [draft-jadhav-lwig-nbr-mgmt-policy-00] gives a
conceptual idea of this method in its section 2.5.3 while this
document proposes the standard method to solve the unbalanced
networking problem.
In the wireless networking scenarios, it would be better to take the
wireless signal strength into consideration in the parent selection
process, otherwise the optimally balanced network may lead to worse
network communication quality for some child nodes. The wireless
signal strength can be quantified by the Received Signal Strength
Indicator (RSSI). This element can be added in the parent selection
Hou, et al Expires September 13, 2017 [Page 8]
INTERNET DRAFT Parent Selection in RPL Networks March 12, 2017
process with the priority: ETX > RSSI > CNC. Note that the selection
in the RSSI processes are not to choose the best value but to filter
out candidate parent nodes according to the ranges (e.g. -80dB < RSSI
<20dB). The RSSI value can be measured by the child nodes thus no
additional modification is needed in the DAG Metric Container. So
the parent node selection in wireless mesh networks can be processed
as follows: Nodes in the network obtain the identity of candidate
parent nodes, the number of child nodes, and the RANK. A filtering
process takes place in the candidate parent nodes based on the
identification and the RANK. Then these candidate parent nodes are
filtered again according to the wireless communication quality index,
RSSI. Finally, the candidate parent node with the minimum number of
child nodes is determined as the target parent node in the network.
Note that the RANK of each candidate parent node is the average value
based on the current ETX, which is set to be greater than the default
path coefficient R. The RANK of a node describes the total path to
the border router (BR), which is determined by the RANK of the parent
node together with the current ETX.
5. Security Considerations
This document has no security consideration beyond those in [RFC
6550], [RFC 6551], [RFC 6552] and [RFC 6719].
6. IANA Considerations
This document creates an IANA registry for the Routing
Metric/Constraint Type. The assigned value is shown below in
comparison with the existing values:
Value Meaning Reference
1 Node State and Attribute RFC6551
2 Node Energy RFC6551
3 Hop Count RFC6551
4 Link Throughput RFC6551
5 Link Latency RFC6551
6 Link Quality Level RFC6551
7 Link ETX RFC6551
8 Link Color RFC6551
9 Child Node Count(*) This document
7. References
7.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, DOI
Hou, et al Expires September 13, 2017 [Page 9]
INTERNET DRAFT Parent Selection in RPL Networks March 12, 2017
10.17487/RFC2119, March 1997, <http://www.rfc-
editor.org/info/rfc2119>.
[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,
<http://www.rfc-editor.org/info/rfc6550>.
[RFC6552] Thubert, P., Ed., "Objective Function Zero for the Routing
Protocol for Low-Power and Lossy Networks (RPL)", RFC 6552,
March 2012, <http://www.rfc-editor.org/info/rfc6552>.
[RFC6719] Gnawali, O. and P. Levis, "The Minimum Rank with Hysteresis
Objective Function", RFC 6719, September 2012,
<http://www.rfc-editor.org/info/rfc6719>.
7.2. Informative References
[draft-jadhav-lwig-nbr-mgmt-policy-00] Jadhav, R., Sahoo, R.,
Duquennoy, S., and J. Eriksson, "Neighbor Management Policy
for 6LoWPAN", draft-jadhav-lwig-nbr-mgmt-policy-00, January
2017, <https://tools.ietf.org/html/draft-jadhav-lwig-nbr-
mgmt-policy-00>.
[RFC6551] Vasseur, J., Kim, M., Pister, K., Dejean, N., and D.
Barthel, "Routing Metrics Used for Path Calculation in Low-
Power and Lossy Networks", RFC 6551, March 2012,
<http://www.rfc-editor.org/info/rfc6551>.
8. Acknowledgments
Authors wish to thank Yizhou li and Yuefeng Wu for their valuable
comments and contributions.
Authors' Addresses
Jianqiang Hou (editor)
Huawei Technologies
101 Software Avenue,
Nanjing 210012
China
Phone: +86-15852944235
Email: houjianqiang@huawei.com
Rahul Arvind Jadhav
Hou, et al Expires September 13, 2017 [Page 10]
INTERNET DRAFT Parent Selection in RPL Networks March 12, 2017
Huawei Technologies
Kundalahalli Village, Whitefield,
Bangalore, Karnataka 560037
India
Phone: +91-080-49160700
Email: rahul.ietf@gmail.com
Zhenhui Luo
Huawei Technologies
Bantian, Longgang District,
Shenzhen 518129
China
Phone: +86-18680331295
Email: luozhenhui@huawei.com
Hou, et al Expires September 13, 2017 [Page 11]
