idnits 2.17.1 draft-ji-roll-traffic-aware-objective-function-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (September 13, 2018) is 2046 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) No issues found here. Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 ROLL C. Ji, Ed. 3 Internet-Draft R. Koutsiamanis 4 Intended status: Standards Track G. Papadopoulos 5 Expires: March 17, 2019 IMT Atlantique 6 D. Dujovne 7 Universidad Diego Portales 8 N. Montavont 9 IMT Atlantique 10 September 13, 2018 12 Traffic-aware Objective Function 13 draft-ji-roll-traffic-aware-objective-function-02 15 Abstract 17 This document proposes a packet transmission rate metric for parent 18 selection. This metric represents the amount of traffic that the 19 node is transmitting to the current parent node. This document also 20 proposes an Objective Function (OF) using the packet transmission 21 rate metric for parent selection in order to balance the amount of 22 traffic between nodes. 24 Status of This Memo 26 This Internet-Draft is submitted in full conformance with the 27 provisions of BCP 78 and BCP 79. 29 Internet-Drafts are working documents of the Internet Engineering 30 Task Force (IETF). Note that other groups may also distribute 31 working documents as Internet-Drafts. The list of current Internet- 32 Drafts is at https://datatracker.ietf.org/drafts/current/. 34 Internet-Drafts are draft documents valid for a maximum of six months 35 and may be updated, replaced, or obsoleted by other documents at any 36 time. It is inappropriate to use Internet-Drafts as reference 37 material or to cite them other than as "work in progress." 39 This Internet-Draft will expire on March 17, 2019. 41 Copyright Notice 43 Copyright (c) 2018 IETF Trust and the persons identified as the 44 document authors. All rights reserved. 46 This document is subject to BCP 78 and the IETF Trust's Legal 47 Provisions Relating to IETF Documents 48 (https://trustee.ietf.org/license-info) in effect on the date of 49 publication of this document. Please review these documents 50 carefully, as they describe your rights and restrictions with respect 51 to this document. Code Components extracted from this document must 52 include Simplified BSD License text as described in Section 4.e of 53 the Trust Legal Provisions and are provided without warranty as 54 described in the Simplified BSD License. 56 Table of Contents 58 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 59 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 60 3. DODAG construction in RPL . . . . . . . . . . . . . . . . . . 3 61 4. Load distribution problem in RPL . . . . . . . . . . . . . . 3 62 5. TAOF description . . . . . . . . . . . . . . . . . . . . . . 5 63 6. DIO Metric Container Type extension . . . . . . . . . . . . . 6 64 7. Security Considerations . . . . . . . . . . . . . . . . . . . 8 65 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 8 66 9. Informative references . . . . . . . . . . . . . . . . . . . 8 67 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9 69 1. Introduction 71 RPL [RFC6550] is an IPv6 Routing protocol for LLNs. It uses 72 Objective Functions (OF) to construct the Destination Oriented 73 Directed Acyclic Graph (DODAG) containing the nodes of the network. 74 The existing OFs defined are OF Zero (OF0) [RFC6552] and Minimum Rank 75 with Hysteresis OF (MRHOF) [RFC6719]. These OFs specify how nodes in 76 a DODAG select their preferred parent using different metrics. 78 The metrics can be separated into two different types, link metrics 79 (e.g. ETX) and node metrics (e.g. energy). Experimental results 80 [I-D.qasem-roll-rpl-load-balancing] conclude that using the current 81 OFs leads to an unbalanced network within which some of the nodes are 82 overloaded. In this case, a node is overloaded in the sense that it 83 forwards much more packets than it otherwise would if the network 84 were balanced. This problem has consequences for the lifetime of the 85 network because overloaded nodes tend to drain quicker than others, a 86 problem which becomes even more significant when the overloaded nodes 87 are near the DODAG root [I-D.qasem-roll-rpl-load-balancing]. 89 This problem is still an open issue and this draft proposes a new way 90 of parent selection as an attempt towards a solution. This draft 91 proposes a new OF that considers the packet transmission rate as a 92 representation of traffic each node faces and use this information to 93 balance the amount of traffic between nodes. 95 In brief, each node tracks its packet transmission rate and appends 96 this information to DIO messages it sends as a DAG Metric Container 97 option. When the DIO message is received by child nodes or potential 98 child nodes, the packet transmission rate information is stored and 99 used to influence the result when RPL parent selection is performed. 101 2. Terminology 103 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 104 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 105 document are to be interpreted as described in [RFC2119]. 107 3. DODAG construction in RPL 109 RPL uses OFs to construct a DODAG. OFs define the way the nodes 110 select their preferred parent and how they compute the new rank. A 111 node's rank is always larger than its parent's rank because the 112 calculation of rank is based on an increment to the parent's rank. 113 This increment differs for each OF but all include the 114 MinHopRankIncrease which is the minimum increase in rank between a 115 node and a node's parent and a step. Different OFs use different 116 metrics or constraints to select the preferred parent and to define 117 the step, depending on application requirements. Nodes obtain these 118 values from DODAG Information Object (DIO) control messages sent by 119 their neighbor nodes. 121 The construction of a DODAG starts when the root node sends DIO 122 messages to its neighbors. After receiving the DIO, these neighbor 123 nodes select the root as their preferred parent if they wish to join 124 the DODAG. In order to announce that they joined the DODAG as its 125 child node, they send a Destination Advertisement Object (DAO) to 126 their preferred parent - the DODAG root. After joining the DODAG, 127 these nodes send their own DIO messages with the new computed rank to 128 their neighbors. This procedure repeats for every node which joins 129 the DODAG. 131 4. Load distribution problem in RPL 133 Numerous experiments using existing OFs have been conducted and 134 according to results, RPL faces a load distribution problem in large 135 LLNs. With RPL using existing OFs, such as MRHOF, an unbalanced 136 network is formed with some of the nodes overloaded and other nodes 137 at rest. This problem is severe for network performance because 138 overloaded nodes will use up their available energy faster than other 139 nodes. This is exacerbated for nodes near the root (within 1 hop 140 distance) or nodes which are the only parent candidate for some other 141 nodes. Additionally, when the overloaded node shuts down, a big part 142 of the network will become disconnected and will have to be 143 transferred to another parent. There is a high probability that the 144 children nodes will also select the same new node as their parent, 145 leading to another overloaded node. Also, when a node has selected 146 its parent, it will change only when the parent node is not reachable 147 (due to battery depletion or packet losses). 149 The existing OFs usually use a single metric to compare parent 150 candidates, for example, as described in [RFC6719] the default metric 151 used in MRHOF is ETX [RFC6551], which represents the number of 152 transmissions a node expects to make to a destination in order to 153 successfully deliver one packet. The result from using a single 154 metric is that nodes prefer to select the same node as their parent, 155 which according to [I-D.qasem-roll-rpl-load-balancing] leads to an 156 unbalanced network with overloaded nodes (node load is indicated by a 157 node's child count). But the child count does not accurately 158 indicate the load because among these child nodes, some of them may 159 have higher traffic load and others may have lower. 161 The network traffic can be quantified by tracking the packets a node 162 generates/sends/receives and the amount of energy it consumes. 163 Energy consumption is strongly correlated to the amount of network 164 traffic handled by a node since the energy consumption for the 165 operation of the radio is the primary energy consumer in typical 166 nodes. However, directly measuring the packet transmission rate is 167 both more accurate and also works when nodes have atypical energy 168 consumption profiles (e.g. increased node processing or high energy 169 consumption sensors). 171 4pkt/s (R) 4pkt/s (R) 172 ^ ^ 173 | | 174 +-------+-------+ +-------+-------+ 175 | | | | 176 + + + + 177 3pkt/s (A) 1pkt/s (B) 2pkt/s (A) 2pkt/s (B) 178 ^ ^ ^ ^ 179 | | | | 180 +------+------+ | +------+ +------+ 181 | | | | | | | | 182 + + + + + + + + 183 (C1) (C2) (C3) (D1) (C1) (C2) (C3) (D1) 184 1pkt/s 1pkt/s 1pkt/s 1pkt/s 1pkt/s 1pkt/s 1pkt/s 1pkt/s 186 Unbalanced Balanced 188 Figure 1: Packet Transmission Rates of nodes with the same 189 requirements 191 As a first simple example, an unbalanced network with nodes which all 192 have the same packet transmission rates is shown in Figure 1. Its 193 transformation into a balanced equivalent network is shown on the 194 right. 196 6pkt/s (R) 6pkt/s (R) 197 ^ ^ 198 | | 199 +-------+-------+ +-------+-------+ 200 | | | | 201 + + + + 202 2pkt/s (A) 4pkt/s (B) 3pkt/s (A) 3pkt/s (B) 203 ^ ^ ^ ^ 204 | | | | 205 +------+ +------+ +------+------+ + 206 | | | | | | | | 207 + + + + + + + + 208 (C1) (C2) (D1) (D2) (C1) (C2) (D1) (D2) 209 1pkt/s 1pkt/s 1pkt/s 3pkt/s 1pkt/s 1pkt/s 1pkt/s 3pkt/s 211 Unbalanced Balanced 213 Figure 2: Packet Transmission Rates of nodes with different 214 requirements 216 As a second simple example, an unbalanced network with nodes which 217 have different packet transmission rates is shown in Figure 2. Its 218 transformation into a balanced equivalent network is shown on the 219 right. 221 5. TAOF description 223 In this specification, a metric is proposed to be used in the parent 224 selection mechanism, the Packet Transmission Rate (PTR) which 225 represents the number of packets each node transmitted (sent or 226 forwarded) during a certain time period. The period used, named 227 PACKET_TRANSMISSION_RATE_PERIOD, is a parameter which is common to 228 the whole RPL instance. This parameter CAN be pre-configured on all 229 the nodes. The period used SHOULD coincide with a sliding window of 230 the same size used to calculate the packets transferred during this 231 period. Therefore, whenever the PTR value is reported it will refer 232 to the previous PACKET_TRANSMISSION_RATE_PERIOD period of time. As 233 mentioned below, the number of transmitted packets can directly show 234 the amount of traffic each node is facing. This information is added 235 in DIO messages and is broadcast to every neighbor. 237 At first, each node MUST identify from their neighbor set which nodes 238 are acceptable to be selected as a parent. For this purpose, the 239 metric ETX is used as a filter to filter out parent candidates with 240 low link quality with a preference for nodes with link quality below 241 a given threshold. The ETX threshold SHOULD be different depending 242 on application requirements. The suggested value for the relevant 243 threshold MAX_PATH_COST from MRHOF [RFC6719] is 32768, which means 244 the specific path has expected transmission counts greater than 256. 246 For the packet transmission rate, each node maintains in a variable a 247 counter which will increment by 1 every time a data packet is 248 transmitted by the node. When the ETX value is used as a filter, 249 nodes with bad link quality will not be included in the parent set. 250 This ensures that undue retransmissions caused by bad link will be 251 avoided. In any case, the node chooses the parent candidate with the 252 least packet transmission rate. 254 This proposal is expected to increase the frequency of parent change 255 because the packet transmission rate is more likely to be different 256 between DIO messages, even for DIO messages from the same node. 257 There are multiple ways to minimize the frequency of unnecessary 258 parent changes: 260 a. Use the packet transmission rate in combination with another 261 metric (e.g. child count, hop counts). 263 b. Use a threshold when comparing the packet transmission rate, 264 similar to the approach in MRHOF [RFC6719]. Switch parents when 265 the difference of packet transmission rate between the original 266 parent and the alternative parent is above a threshold. This 267 threshold depends on different factors (e.g. network size, 268 average traffic load) and SHOULD be defined differently for each 269 use case. 271 6. DIO Metric Container Type extension 273 0 1 274 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 275 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 276 | Packet Transmission Rate (PTR)| 277 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 279 Figure 3: DAG metric container type format. 281 A DIO message carries fields as described in RFC6550 [RFC6550] and 282 the available options for the DAG metric container are described in 283 RFC6551 [RFC6551]. In this specification, a metric container option 284 is proposed and the detailed format is shown in Figure 3. The 285 information carried is the PTR, represented as a 2 byte unsigned 286 integer. 288 0 1 2 3 289 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 290 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 291 | RPLInstanceID |Version Number | Rank | 292 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 293 |G|0| MOP | Prf | DTSN | Flags | Reserved | 294 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 295 | | 296 + + 297 | | 298 + DODAGID + 299 | | 300 + + 301 | | 302 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 303 | DAGMC Type (2)| DAGMC Length | | 304 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 305 | | 306 // DAG Metric Container data // 307 | | 308 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 310 Figure 4: Example DIO Message with a DAG Metric Container option 312 The structure of the DIO Control Message when a DAG Metric Container 313 option is included is shown in Figure 4. The DAG Metric Container 314 option type (DAGMC Type in Figure 4) has the value 0x02 as per the 315 IANA registry for the RPL Control Message Options, and is defined in 316 [RFC6550]. The DAG Metric Container option length (DAGMC Length in 317 Figure 4) expresses the the DAG Metric Container length in bytes. 318 DAG Metric Container data holds the actual data and is shown further 319 expanded in Figure 5. 321 0 1 2 3 322 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 323 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 324 |Routing-MC-Type|Res Flags|P|C|O|R| A | Prec | Length (bytes)| 325 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 326 | Packet Transmission Rate (PTR)| 327 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 329 Figure 5: DAG Metric Container (MC) data with Packet Transmission 330 Rate (PTR) object body 332 An example DAG Metric Container containing the proposed Metric 333 Container object is shown in Figure 5. The explicit definition of 334 the fields is: 336 Routing-MC-Type: TBD1. The type of the proposed DAGMC extension. 337 To be assigned by IANA. 339 Packet Transmission Rate (PTR): The packet transmission rate, 340 represented as a 2 byte unsigned integer. 342 7. Security Considerations 344 The structure of the DIO control message is extended, within the 345 predefined DIO options. Therefore, the security mechanisms defined 346 in RPL [RFC6550] apply to this proposed extension. 348 8. IANA Considerations 350 This proposal requests the allocation of a new value TBD1 for the 351 metric type "PTR" in the Routing-MC-Type field in the DAG MC from 352 IANA. 354 Additionally, an Objective Code Point (OCP) with value TBD2 for TAOF 355 needs to be assigned in the Objective Code Point Registry as 356 described in Section 20.5 of [RFC6550]. 358 9. Informative references 360 [I-D.qasem-roll-rpl-load-balancing] 361 Qasem, M., Al-Dubai, A., Romdhani, I., Ghaleb, B., Hou, 362 J., and R. Jadhav, "Load Balancing Objective Function in 363 RPL", draft-qasem-roll-rpl-load-balancing-02 (work in 364 progress), October 2017. 366 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 367 Requirement Levels", BCP 14, RFC 2119, 368 DOI 10.17487/RFC2119, March 1997, 369 . 371 [RFC6550] Winter, T., Ed., Thubert, P., Ed., Brandt, A., Hui, J., 372 Kelsey, R., Levis, P., Pister, K., Struik, R., Vasseur, 373 JP., and R. Alexander, "RPL: IPv6 Routing Protocol for 374 Low-Power and Lossy Networks", RFC 6550, 375 DOI 10.17487/RFC6550, March 2012, 376 . 378 [RFC6551] Vasseur, JP., Ed., Kim, M., Ed., Pister, K., Dejean, N., 379 and D. Barthel, "Routing Metrics Used for Path Calculation 380 in Low-Power and Lossy Networks", RFC 6551, 381 DOI 10.17487/RFC6551, March 2012, 382 . 384 [RFC6552] Thubert, P., Ed., "Objective Function Zero for the Routing 385 Protocol for Low-Power and Lossy Networks (RPL)", 386 RFC 6552, DOI 10.17487/RFC6552, March 2012, 387 . 389 [RFC6719] Gnawali, O. and P. Levis, "The Minimum Rank with 390 Hysteresis Objective Function", RFC 6719, 391 DOI 10.17487/RFC6719, September 2012, 392 . 394 Authors' Addresses 396 Chenyang Ji (editor) 397 IMT Atlantique 398 Office D00 - 116A 399 2 Rue de la Chataigneraie 400 Cesson-Sevigne - Rennes 35510 401 FRANCE 403 Email: chenyang.ji@imt-atlantique.net 405 Remous-Aris Koutsiamanis 406 IMT Atlantique 407 Office B00 - 126A 408 2 Rue de la Chataigneraie 409 Cesson-Sevigne - Rennes 35510 410 FRANCE 412 Phone: +33 299 12 70 49 413 Email: aris@ariskou.com 415 Georgios Papadopoulos 416 IMT Atlantique 417 Office B00 - 114A 418 2 Rue de la Chataigneraie 419 Cesson-Sevigne - Rennes 35510 420 FRANCE 422 Phone: +33 299 12 70 04 423 Email: georgios.papadopoulos@imt-atlantique.fr 424 Diego Dujovne 425 Universidad Diego Portales 426 Escuela de Informatica y Telecomunicaciones, Av. Ejercito 441 427 Santiago, Region Metropolitana 428 Chile 430 Phone: +56 (2) 676-8121 431 Email: diego.dujovne@mail.udp.cl 433 Nicolas Montavont 434 IMT Atlantique 435 Office B00 - 106A 436 2 Rue de la Chataigneraie 437 Cesson-Sevigne - Rennes 35510 438 FRANCE 440 Phone: +33 299 12 70 23 441 Email: nicolas.montavont@imt-atlantique.fr