ROLL INTERNET-DRAFT B.Ghaleb Intended Status: Standards Track A.Al-Dubai Expires: September 23, 2019 I.Romdhani M.Qasem Edinburgh Napier University March 23, 2020 Load-balancing and Stability Aware Objective Function (LBSA) draft-baraq-roll-lbsa-00 Abstract 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. 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 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 http://www.ietf.org/shadow.html 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 (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. 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", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 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 network. 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. 265-273. 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 EMail: b.ghaleb@napier.ac.uk Ahmed Al-Dubai Edinburgh Napier Universty 10 Colinton Road, EH10 5DT, Edinburgh, UK Phone: +44 131 455 2796 EMail: a.al-dubai@napier.ac.uk Imed Romdhani (Editor) Edinburgh Napier Universty 10 Colinton Road, EH10 5DT, Edinburgh, UK Phone: +44 131 455 2726 EMail: i.romdhani@napier.ac.uk Mamoun Qasem Edinburgh Napier Universty 10 Colinton Road, EH10 5DT, Edinburgh, UK EMail: m.qasem@napier.ac.uk Ghaleb, et al. Expires September 23, 2019 [Page 7]