[Docs] [txt|pdf] [Tracker] [Email] [Nits]

Versions: 00

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]


Html markup produced by rfcmarkup 1.121, available from https://tools.ietf.org/tools/rfcmarkup/