ROLL C. Ji, Ed. Internet-Draft R. Koutsiamanis Intended status: Standards Track G. Papadopoulos Expires: June 4, 2018 IMT Atlantique D. Dujovne Universidad Diego Portales N. Montavont IMT Atlantique December 1, 2017 Traffic-aware Objective Function draft-ji-traffic-aware-objective-function-00 Abstract This document proposes a packet transmission rate metric for parent selection. This metric represents the amount of traffic that the node is transmitting to the current parent node. This document also proposes an Objective Function (OF) using the packet transmission rate metric for parent selection in order to balance the amount of traffic between nodes. Status of This Memo This Internet-Draft is submitted in full conformance with the provisions of BCP 78 and BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF). Note that other groups may also distribute working documents as Internet-Drafts. The list of current Internet- Drafts is at https://datatracker.ietf.org/drafts/current/. 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." This Internet-Draft will expire on June 4, 2018. Copyright 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 (https://trustee.ietf.org/license-info) in effect on the date of Ji, et al. Expires June 4, 2018 [Page 1] Internet-Draft Traffic-aware OF December 2017 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 . . . . . . . . . . . . . . . . . . . . . . . . 2 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 3. DODAG construction in RPL . . . . . . . . . . . . . . . . . . 3 4. Load distribution problem in RPL . . . . . . . . . . . . . . 3 5. TAOF description . . . . . . . . . . . . . . . . . . . . . . 5 6. DIO Metric Container Type extension . . . . . . . . . . . . . 6 7. Security Considerations . . . . . . . . . . . . . . . . . . . 7 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 7 9. Informative references . . . . . . . . . . . . . . . . . . . 8 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 8 1. Introduction RPL [RFC6550] is an IPv6 Routing protocol for LLNs. It uses Objective Functions (OF) to construct the Destination Oriented Directed Acyclic Graph (DODAG) containing the nodes of the network. The existing OFs defined are OF Zero (OF0) [RFC6552] and Minimum Rank with Hysteresis OF (MRHOF) [RFC6719]. These OFs specify how nodes in a DODAG select their preferred parent using different metrics. The metrics can be separated into two different types, link metrics (e.g. ETX) and node metrics (e.g. energy). Experimental results [I-D.qasem-roll-rpl-load-balancing] conclude that using the current OFs leads to an unbalanced network within which some of the nodes are overloaded. In this case, a node is overloaded in the sense that it forwards much more packets than it otherwise would if the network were balanced. This problem has consequences for the lifetime of the network because overloaded nodes tend to drain quicker than others, a problem which becomes even more significant when the overloaded nodes are near the DODAG root [I-D.qasem-roll-rpl-load-balancing]. This problem is still an open issue and this draft proposes a new way of parent selection as an attempt towards a solution. This draft proposes a new OF that considers the packet transmission rate as a representation of traffic each node faces and use this information to balance the amount of traffic between nodes. In brief, each node tracks its packet transmission rate and appends this information to DIO messages it sends as a DAG Metric Container Ji, et al. Expires June 4, 2018 [Page 2] Internet-Draft Traffic-aware OF December 2017 option. When the DIO message is received by child nodes or potential child nodes, the packet transmission rate information is stored and used to influence the result when RPL parent selection is performed. 2. 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 [RFC2119]. 3. DODAG construction in RPL RPL uses OFs to construct a DODAG. OFs define the way the nodes select their preferred parent and how they compute the new rank. A node's rank is always larger than its parent's rank because the calculation of rank is based on an increment to the parent's rank. This increment differs for each OF but all include the MinHopRankIncrease which is the minimum increase in rank between a node and a node's parent and a step. Different OFs use different metrics or constraints to select the preferred parent and to define the step, depending on application requirements. Nodes obtain these values from DODAG Information Object (DIO) control messages sent by their neighbor nodes. The construction of a DODAG starts when the root node sends DIO messages to its neighbors. After receiving the DIO, these neighbor nodes select the root as their preferred parent if they wish to join the DODAG. In order to announce that they joined the DODAG as its child node, they send a Destination Advertisement Object (DAO) to their preferred parent - the DODAG root. After joining the DODAG, these nodes send their own DIO messages with the new computed rank to their neighbors. This procedure repeats for every node which joins the DODAG. 4. Load distribution problem in RPL Numerous experiments using existing OFs have been conducted and according to results, RPL faces a load distribution problem in large LLNs. With RPL using existing OFs, such as MRHOF, an unbalanced network is formed with some of the nodes overloaded and other nodes at rest. This problem is severe for network performance because overloaded nodes will use up their available energy faster than other nodes. This is exacerbated for nodes near the root (within 1 hop distance) or nodes which are the only parent candidate for some other nodes. Additionally, when the overloaded node shuts down, a big part of the network will become disconnected and will have to be transferred to another parent. There is a high probability that the children nodes will also select the same new node as their parent, Ji, et al. Expires June 4, 2018 [Page 3] Internet-Draft Traffic-aware OF December 2017 leading to another overloaded node. Also, when a node has selected its parent, it will change only when the parent node is not reachable (due to battery depletion or packet losses). The existing OFs usually use a single metric to compare parent candidates, for example, as described in [RFC6719] the default metric used in MRHOF is ETX [RFC6551], which represents the number of transmissions a node expects to make to a destination in order to successfully deliver one packet. The result from using a single metric is that nodes prefer to select the same node as their parent, which according to [I-D.qasem-roll-rpl-load-balancing] leads to an unbalanced network with overloaded nodes (node load is indicated by a node's child count). But the child count does not accurately indicate the load because among these child nodes, some of them may have higher traffic load and others may have lower. The network traffic can be quantified by tracking the packets a node generates/sends/receives and the amount of energy it consumes. Energy consumption is strongly correlated to the amount of network traffic handled by a node since the energy consumption for the operation of the radio is the primary energy consumer in typical nodes. However, directly measuring the packet transmission rate is both more accurate and also works when nodes have atypical energy consumption profiles (e.g. increased node processing or high energy consumption sensors). 4pkt/s (R) 4pkt/s (R) ^ ^ | | +-------+-------+ +-------+-------+ | | | | + + + + 3pkt/s (A) 1pkt/s (B) 2pkt/s (A) 2pkt/s (B) ^ ^ ^ ^ | | | | +------+------+ | +------+ +------+ | | | | | | | | + + + + + + + + (C1) (C2) (C3) (D1) (C1) (C2) (C3) (D1) 1pkt/s 1pkt/s 1pkt/s 1pkt/s 1pkt/s 1pkt/s 1pkt/s 1pkt/s Unbalanced Balanced Figure 1: Packet Transmission Rates of nodes with the same requirements As a first simple example, an unbalanced network with nodes which all have the same packet transmission rates is shown in Figure 1. Its Ji, et al. Expires June 4, 2018 [Page 4] Internet-Draft Traffic-aware OF December 2017 transformation into a balanced equivalent network is shown on the right. 6pkt/s (R) 6pkt/s (R) ^ ^ | | +-------+-------+ +-------+-------+ | | | | + + + + 2pkt/s (A) 4pkt/s (B) 3pkt/s (A) 3pkt/s (B) ^ ^ ^ ^ | | | | +------+ +------+ +------+------+ + | | | | | | | | + + + + + + + + (C1) (C2) (D1) (D2) (C1) (C2) (D1) (D2) 1pkt/s 1pkt/s 1pkt/s 3pkt/s 1pkt/s 1pkt/s 1pkt/s 3pkt/s Unbalanced Balanced Figure 2: Packet Transmission Rates of nodes with different requirements As a second simple example, an unbalanced network with nodes which have different packet transmission rates is shown in Figure 2. Its transformation into a balanced equivalent network is shown on the right. 5. TAOF description In this specification, a metric is proposed to be used in the parent selection mechanism, the Packet Transmission Rate (PTR) which represents the number of packets each node transmitted (sent or forwarded) during a certain time period. As mentioned below, the number of transmitted packets can directly show the amount of traffic each node is facing. This information is added in DIO messages and is broadcast to every neighbor. At first, each node MUST identify from their neighbor set which nodes are acceptable to be selected as a parent. For this purpose, the metric ETX is used as a filter to filter out parent candidates with low link quality with a preference for nodes with link quality below a given threshold. The ETX threshold SHOULD be different depending on application requirements. The suggested value for the relevant threshold MAX_PATH_COST from MRHOF [RFC6719] is 32768, which means the specific path has expected transmission counts greater than 256. Ji, et al. Expires June 4, 2018 [Page 5] Internet-Draft Traffic-aware OF December 2017 For the packet transmission rate, each node maintains in a variable a counter which will increment by 1 every time a data packet is transmitted by the node. When the ETX value is used as a filter, nodes with bad link quality will not be included in the parent set. This ensures that undue retransmissions caused by bad link will be avoided. In any case, the node chooses the parent candidate with the least packet transmission rate. This proposal is expected to increase the frequency of parent change because the packet transmission rate is more likely to be different between DIO messages, even for DIO messages from the same node. There are multiple ways to minimize the frequency of unnecessary parent changes: a. Use the packet transmission rate in combination with another metric (e.g. child count, hop counts). b. Use a threshold when comparing the packet transmission rate, similar to the approach in MRHOF [RFC6719]. Switch parents when the difference of packet transmission rate between the original parent and the alternative parent is above a threshold. This threshold depends on different factors (e.g. network size, average traffic load) and SHOULD be defined differently for each use case. 6. DIO Metric Container Type extension 0 1 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Packet Transmission Rate (PTR)| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 3: DAG metric container type format. A DIO message carries fields as described in RFC6550 [RFC6550] and the available options for the DAG metric container are described in RFC6551 [RFC6551]. In this specification, a metric container option is proposed and the detailed format is shown in Figure 3. The information carried is the PTR, represented as a 2 byte unsigned integer. Ji, et al. Expires June 4, 2018 [Page 6] Internet-Draft Traffic-aware OF December 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 + | | + + | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | DAGMC Type (PC)| DAGMC Length | Packet Transmission Rate (PTR)| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 4: Example DIO Message with a DAG Metric Container option An example DIO Message containing the proposed DAG Metric Container type is shown in Figure 4. The explicit definition of the fields is: DAGMC type: The type of the proposed DAGMC extension. To be assigned by IANA. DAGMC Length: The total length of the proposed DAGMC extension in bytes. MUST be 2. Packet Transmission Rate (PTR): The DAG Metric Container data, containing the packet transmission rate, represented as a 2 byte unsigned integer. 7. Security Considerations The structure of the DIO control message is extended, within the predefined DIO options. Therefore, the security mechanisms defined in RPL [RFC6550] apply to this proposed extension. 8. IANA Considerations This proposal requests the allocation of a new value for the metric type "PTR" in the Routing Metric/Constraint Type in the DAG MC from IANA. Ji, et al. Expires June 4, 2018 [Page 7] Internet-Draft Traffic-aware OF December 2017 9. Informative references [I-D.qasem-roll-rpl-load-balancing] Qasem, M., Al-Dubai, A., Romdhani, I., Ghaleb, B., Hou, J., and R. Jadhav, "Load Balancing Objective Function in RPL", draft-qasem-roll-rpl-load-balancing-02 (work in progress), October 2017. [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . [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, DOI 10.17487/RFC6550, March 2012, . [RFC6551] Vasseur, JP., 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, DOI 10.17487/RFC6551, March 2012, . [RFC6552] Thubert, P., Ed., "Objective Function Zero for the Routing Protocol for Low-Power and Lossy Networks (RPL)", RFC 6552, DOI 10.17487/RFC6552, March 2012, . [RFC6719] Gnawali, O. and P. Levis, "The Minimum Rank with Hysteresis Objective Function", RFC 6719, DOI 10.17487/RFC6719, September 2012, . Authors' Addresses Chenyang Ji (editor) IMT Atlantique Office D00 - 116A 2 Rue de la Chataigneraie Cesson-Sevigne - Rennes 35510 FRANCE Email: chenyang.ji@imt-atlantique.net Ji, et al. Expires June 4, 2018 [Page 8] Internet-Draft Traffic-aware OF December 2017 Remous-Aris Koutsiamanis IMT Atlantique Office B00 - 126A 2 Rue de la Chataigneraie Cesson-Sevigne - Rennes 35510 FRANCE Phone: +33 299 12 70 49 Email: aris@ariskou.com Georgios Papadopoulos IMT Atlantique Office B00 - 114A 2 Rue de la Chataigneraie Cesson-Sevigne - Rennes 35510 FRANCE Phone: +33 299 12 70 04 Email: georgios.papadopoulos@imt-atlantique.fr Diego Dujovne Universidad Diego Portales Escuela de Informatica y Telecomunicaciones, Av. Ejercito 441 Santiago, Region Metropolitana Chile Phone: +56 (2) 676-8121 Email: diego.dujovne@mail.udp.cl Nicolas Montavont IMT Atlantique Office B00 - 106A 2 Rue de la Chataigneraie Cesson-Sevigne - Rennes 35510 FRANCE Phone: +33 299 12 70 23 Email: nicolas.montavont@imt-atlantique.fr Ji, et al. Expires June 4, 2018 [Page 9]