Internet DRAFT - draft-qasem-roll-rpl-load-balancing

draft-qasem-roll-rpl-load-balancing



 



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]