Internet DRAFT - draft-baraq-roll-lbsa



INTERNET-DRAFT                                                  B.Ghaleb
Intended Status: Standards Track                              A.Al-Dubai
Expires: September 23, 2019                                   I.Romdhani
                                             Edinburgh Napier University
                                                          March 23, 2020

      Load-balancing and Stability Aware Objective Function (LBSA)


   The IPv6 Routing Protocol for Low-power and Lossy Networks (RPL) has
   been recently standardized as the de facto solution for routing in
   the context of the emerging Internet of Things (IoT) paradigm. RPL,
   along with other standards, has provided a baseline framework for IoT
   that has helped advance communications in the world of embedded
   resource-constrained networks. However, RPL still suffers from issues
   that may limit its efficiency such as the absence of an efficient
   load-balancing primitive.  To address this problem, a novel load-
   balancing scheme is introduced that ensures a fair distribution of
   traffic among nodes while minimizing overhead

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 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

   The list of Internet-Draft Shadow Directories can be accessed at

Ghaleb, et al.         Expires September 23, 2019               [Page 1]
INTERNET DRAFT          LBSA Objective Function            June 10, 2019

Copyright and License Notice

   Copyright (c) 2018 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
   ( 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.  Load-balancing aware Objective Function  . . . . . . . . . . .  3
     2.1 The load-balancing metric  . . . . . . . . . . . . . . . . .  4
       2.1.1 Measuring the Number of Children Metric  . . . . . . . .  4
     2.2 The Timely Propagation Primitive . . . . . . . . . . . . . .  5
     2.3 Avoiding The Herding Problem . . . . . . . . . . . . . . . .  5
   3  Security Considerations . . . . . . . . . . . . . . . . . . . .  6
   4  References  . . . . . . . . . . . . . . . . . . . . . . . . . .  6
     4.1  Normative References  . . . . . . . . . . . . . . . . . . .  6
     4.2  Informative References  . . . . . . . . . . . . . . . . . .  6
   Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . .  7


Ghaleb, et al.         Expires September 23, 2019               [Page 2]
INTERNET DRAFT          LBSA Objective Function            June 10, 2019

1  Introduction

   The standardized Routing Protocol for Low-power and Lossy networks
   (RPL) [RFC6550] lacks in an efficient routing primitive that ensures
   a fair distribution of traffic among nodes while minimizing overhead.
   The absence of such mechanism may prevent the distribution of traffic
   among multiple nodes, potentially increasing data loss caused by the
   node packet buffer overflow or leading to a faster depletion of the
   energy of overloaded nodes which in turn may result in service
   disruption [1][2][3][4]. However, poorly implemented load balancing
   causes problems too. An example is the herding-effect [1], in which
   the network suffers topological instability caused by nodes
   repeatedly switching preferred parents in a futile attempt to achieve
   load balancing [1].  For instance, in Figure 1a, you can see that six
   nodes have selected the lightly loaded parent, A, upon receiving its
   DIO. However, in Figure 1b,  all six nodes simultaneously changed
   their preferred parent to, B, in an attempt to load-balance the
   traffic upon receiving a new DIO from that node announcing a fewer
   number of children than node A. However, when receiving a new DIO
   from node A, the migration reverses, resulting in load oscillation
   with no balancing.

                +---+                               +---+
                |LBR|                               |LBR|
                +---+                               +---+
                 /                                    /\
                /                                    /  \
           +--+    +--+    Continuous loop       +--+    +--+
           :A :    :B :    <-------------->      :A :    :B :
           +--+    +--+                          +--+    +--+
           /                                               \       
          /                                                 \
       * * * (Children)                               * * * (Children)
       * * *                                          * * *
              (a)                                             (b)
                        Figure 1: The herding-effect problem

1.1  Terminology

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   document are to be interpreted as described in RFC 2119 [RFC2119].

2.  Load-balancing aware Objective Function

   In order to address the load-balancing problem of RPL, a new load
   balancing OF is proposed in this study and discussed in the following

Ghaleb, et al.         Expires September 23, 2019               [Page 3]
INTERNET DRAFT          LBSA Objective Function            June 10, 2019

   subsections.  We emphasize here that the main goal of the proposed
   solution is to introduce a load-balancing mechanism into RPL while
   maintaining stability with minimal overhead. In order to achieve this
   goal, we articulate that a stable and efficient load-balancing
   mechanism should comprise the following sub-components: several steps
   as follows: 1) A suitable metric (single or composite) for load-
   balancing. 2) A propagation primitive that ensures timely and
   efficient propagation of load balancing information before it becomes
   obsolete. 3) A routing primitive that mitigates the instability
   problem that may arise from introducing load-balancing into the

2.1 The load-balancing metric 

   Several routing metrics for RPL networks have been proposed in the
   literature  [RFC6551] including load-balancing metrics such as number
   of children, throughput, and queue utilization factor. In this draft,
   we opt to use the number of children metric for the purpose of load-
   balancing for two primary reasons. First, it can be measured easily
   based on the data-plane traffic without incurring any extra overhead
   in the control-plane, especially in periodic applications as
   discussed next.  Second, in the vast majority of applications, it
   reflects the actual network load.

2.1.1 Measuring the number of children metric 
   In this draft, we introduce for the first time the notion of calculating the number of
   children based on the data-plane messages rather than relying on
   RPL's DAO messages. In fact, number of children can be calculated
   based on RPL's DAO messages, however, as these messages are an
   optional feature of RPL, they may not be available in all scenarios. To
   calculate the number of children based on data-plane traffic, we
   exploit the fact that IPv6 data packets carry the source address of
   the sender in the header of the packet, in addition to the RPL Hop-
   by-Hop (HBH) header option. Hence, when an IPv6 packet is received,
   the protocol first determines if it is a control or a data packet by
   inspecting if the RPL HBH Option is exist or not. The presence of
   such an option indicates that a data packet is being received at the
   network layer.  If the received packet is data, it inspects its
   direction to decide if the sender is a child or not (direction is
   specified by the Down flag in the RPL HBH Option).  If the packet is
   heading upward, the sender is a child so the protocol adds the sender
   IP Address (CHIP) to the list of children (CHList) of the receiver.
   If no data packets are received from an existing child during a pre-
   specified interval, it is removed. This interval is set proportional
   to the traffic rate. 


Ghaleb, et al.         Expires September 23, 2019               [Page 4]
INTERNET DRAFT          LBSA Objective Function            June 10, 2019

2.2 The Timely Propagation Primitive

   The second step towards realizing an efficient load-balancing
   objective function is the timely propagation of the routing
   information, especially those related to the load-balancing metric
   (i.e., number of children). In fact, the propagation of routing
   information carried in RPL's DIO messages is regulated by means of
   Trickle [RFC6206] in which the DIO transmission rate is increased
   upon detecting inconsistencies in the network. For example, the current
   implementation of Trickle in Contiki OS has restricted the number of
   times the network is declared inconsistent to a few cases to minimize
   the control-plane overhead. These cases include global repair, local
   repair, and parent change. Here, it is clear that a change in a
   node's rank does not trigger a resetting of the Trickle timer, so
   some routing decisions might be taken based on obsolete routing
   information due to the long DIO transmission period in the consistent
   state. Hence, a problematic gap may arise between the time the node
   has changed its preferred parent and the scheduled time for the DIO
   to be sent at.

   To overcome this concern, we have opted to permit the node to declare
   an inconsistency upon detecting that its number of children has been
   increased or decreased by a pre-specified threshold. This will allow
   neighboring nodes to receive the load information in a timely manner,
   at the cost of some increased overhead. To reduce the overhead
   resulting from resetting the Trickle timer, the protocol does not do
   this every time the node's balancing information changes (in terms of
   number of children). Instead, it uses a FastPropagation Timer (Reset
   Timer): when this expires a node checks whether it should reset its
   Trickle timer or not. The propagation of rank information is still
   governed by the Trickle algorithm itself. 

2.3 Avoiding The Herding Problem 

   One of the obstacles toward achieving load balancing in RPL is the
   way the protocol switches preferred parents. The common strategy
   adopted by RPL is to allow a specific node to switch immediately to a
   better parent upon detecting such a parent by means of DIOs. This may
   have the advantage of timely switching; however, in the context of
   load balancing, changing preferred parent immediately on discovery
   may give rise to the herding effect explained earlier. To address
   this issue, we have introduced the idea of the Balancing Timer (or
   Scheduling Timer). This timer regulates the timing of parent
   selection process. Instead of having a node performing this process
   immediately upon receiving a new DIO, the parent selection in our
   proposed mechanism is performed regularly at pre-determined interval.
   However, we exclude the first received DIO from this policy to allow
   faster convergence time at the stage of DODAG construction. In other

Ghaleb, et al.         Expires September 23, 2019               [Page 5]
INTERNET DRAFT          LBSA Objective Function            June 10, 2019

   words, when a node receives a DIO for the first time, it will
   immediately choose the sender as its preferred parent. Then, the node
   must wait until the expiration of the Balancing Timer in order to
   check whether a better parent is available or not so it can change to
   a new preferred parent. The Balancing Timer is reset every time the
   node performs the parent selection process. The value of the
   Balancing Timer should be set in a way that allow for several DIOs to
   be received at the node so it can have several candidate parents
   which is better to be set empirically. The details of this process is
   also illustrated in Algorithm 5-1.

3  Security Considerations

   Since the routing metrics/constraints are carried within RPL message,
   the security routing mechanisms defined in [RFC6550] apply here.

4  References

4.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.

   [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.

   [RFC 6206] P. Levis, T. Clausen, J. Hui, O. Gnawali, and J. Ko, "The
              Trickle algorithm," RFC 6206, Internet Engineering Task
              Force (IETF), 2011

4.2  Informative References

 [1] H. S. Kim, J. Paek and S. Bahk, "QU-RPL: Queue utilization based
     RPL for load balancing in large scale industrial applications," in
     the 12th Annual IEEE International Conference on Sensing,
     Communication, and Networking (SECON), Seattle, WA, Jun. 2015, pp.


Ghaleb, et al.         Expires September 23, 2019               [Page 6]
INTERNET DRAFT          LBSA Objective Function            June 10, 2019

 [2] J. Tripathi and J. C. De Oliveira, "Quantifying load imbalance: A
     practical implementation for data collection in low power lossy
     networks,"  47th Annual Conference on Information Sciences and
     Systems (CISS), Baltimore, MD, 2013, pp. 1-6.

 [3] X. Liu, J. Guo, G. Bhatti, P. Orlik and K. Parsons, "Load balanced
     routing for low power and lossy networks," in the IEEE Wireless
     Communications and Networking Conference (WCNC), Apr. 2013,
     Shanghai, pp. 2238-2243.

 [4] B. Ghaleb, A. Al-Dubai, E. Ekonomou, W. Gharib, L. Mackenzi and M.
     Bani Khala, "A New Load-Balancing Aware Objective Function for
     RPL's IoT Networks," 2018 IEEE 20th International Conference on
     High Performance Computing and Communications; IEEE 16th
     International Conference on Smart City; IEEE 4th International
     Conference on Data Science and Systems (HPCC/SmartCity/DSS),
     Exeter, United Kingdom, 2018, pp. 909-914.

Authors' Addresses

     Baraq Ghaleb (Editor)
     Edinburgh Napier Universty
     10 Colinton Road, EH10 5DT, Edinburgh, UK

     Ahmed Al-Dubai
     Edinburgh Napier Universty
     10 Colinton Road, EH10 5DT, Edinburgh, UK
     Phone: +44 131 455 2796

     Imed Romdhani (Editor)
     Edinburgh Napier Universty
     10 Colinton Road, EH10 5DT, Edinburgh, UK
     Phone: +44 131 455 2726

     Mamoun Qasem
     Edinburgh Napier Universty
     10 Colinton Road, EH10 5DT, Edinburgh, UK

Ghaleb, et al.         Expires September 23, 2019               [Page 7]