roll Internet-Draft M.Qasem Intended Status: Standards Track A.Al-Dubai Expires: February 10, 2018 I.Romdhani B.Ghaleb Edinburgh Napier University August 9, 2017 Load Balancing Objective Function in RPL draft-qasem-roll-rpl-load-balancing-01 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. 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 http://www.ietf.org/1id-abstracts.html The list of Internet-Draft Shadow Directories can be accessed at Qasem, et al. Expires February 10, 2018 [Page 1] INTERNET DRAFT Load Balancing OF for RPL August 9, 2017 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 The Selected Parent Option . . . . . . . . . . . . . . . . . 7 5 Security Considerations . . . . . . . . . . . . . . . . . . . . 7 6 IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 8 7 References . . . . . . . . . . . . . . . . . . . . . . . . . . 8 7.1 Normative References . . . . . . . . . . . . . . . . . . . 8 7.2 Informative References . . . . . . . . . . . . . . . . . . 9 Appendix A. . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 9 Qasem, et al. Expires February 10, 2018 [Page 2] INTERNET DRAFT Load Balancing OF for RPL August 9, 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 February 10, 2018 [Page 3] INTERNET DRAFT Load Balancing OF for RPL August 9, 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 February 10, 2018 [Page 4] INTERNET DRAFT Load Balancing OF for RPL August 9, 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 February 10, 2018 [Page 5] INTERNET DRAFT Load Balancing OF for RPL August 9, 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 February 10, 2018 [Page 6] INTERNET DRAFT Load Balancing OF for RPL August 9, 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 children 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 The Selected Parent Option 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]. However, the option field within DIO message could be utilized to inject the selected parent address, and its format is as shown in Figure 3. 5 Security Considerations Since the routing metrics/constraints are carried within RPL message, Qasem, et al. Expires February 10, 2018 [Page 7] INTERNET DRAFT Load Balancing OF for RPL August 9, 2017 the security routing mechanisms defined in [RFC6550] apply here. 6 IANA Considerations The IANA defined in [RFC6551] apply here according to [RFC5226]. 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 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type | Option Length | Flags | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | | + + | | + Parent Address + | | + +-+-+-+-+-+-+-+-+-+ | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 3: Format of the Selected Parent Option 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 Qasem, et al. Expires February 10, 2018 [Page 8] INTERNET DRAFT Load Balancing OF for RPL August 9, 2017 in Low-Power and Lossy Networks", RFC 6551, March 2012. 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 Qasem, et al. Expires February 10, 2018 [Page 9] INTERNET DRAFT Load Balancing OF for RPL August 9, 2017 Baraq Ghaleb Edinburgh Napier University 10 Colinton Road, EH10 5DT, Edinburgh, UK Email: b.ghaleb@napier.ac.uk Qasem, et al. Expires February 10, 2018 [Page 10]