idnits 2.17.00 (12 Aug 2021) /tmp/idnits36280/draft-ietf-6tisch-6top-sfx-01.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 (March 5, 2018) is 1532 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Missing Reference: 'SLOTFRAME' is mentioned on line 339, but not defined == Missing Reference: 'TIMEOUT' is mentioned on line 340, but not defined == Missing Reference: 'WBLIST' is mentioned on line 341, but not defined == Outdated reference: draft-ietf-6tisch-6top-protocol has been published as RFC 8480 == Outdated reference: draft-ietf-6tisch-minimal-security has been published as RFC 9031 Summary: 0 errors (**), 0 flaws (~~), 6 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 6TiSCH D. Dujovne, Ed. 3 Internet-Draft Universidad Diego Portales 4 Intended status: Experimental LA. Grieco 5 Expires: September 6, 2018 Politecnico di Bari 6 MR. Palattella 7 Luxembourg Institute of Science and Technology (LIST) 8 N. Accettura 9 LAAS-CNRS 10 March 5, 2018 12 6TiSCH Experimental Scheduling Function (SFX) 13 draft-ietf-6tisch-6top-sfx-01 15 Abstract 17 This document defines a Scheduling Function called "Experimental 18 Scheduling Function" (SFX). SFX dynamically adapts the number of 19 scheduled cells between neighbor nodes, based on the amount of 20 currently allocated cells and the neighbor nodes' cell requirements. 21 Neighbor nodes negotiate in a distributed neighbor-to-neighbor basis 22 the number of cell(s) to be added/deleted. SFX uses the 6P signaling 23 messages to add/delete cells in the schedule. This function selects 24 the candidate cells from the schedule, defines which cells will be 25 added/deleted and triggers the allocation/deallocation process. 27 Requirements Language 29 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 30 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and 31 "OPTIONAL" in this document are to be interpreted as described in RFC 32 2119 [RFC2119]. 34 Status of This Memo 36 This Internet-Draft is submitted in full conformance with the 37 provisions of BCP 78 and BCP 79. 39 Internet-Drafts are working documents of the Internet Engineering 40 Task Force (IETF). Note that other groups may also distribute 41 working documents as Internet-Drafts. The list of current Internet- 42 Drafts is at https://datatracker.ietf.org/drafts/current/. 44 Internet-Drafts are draft documents valid for a maximum of six months 45 and may be updated, replaced, or obsoleted by other documents at any 46 time. It is inappropriate to use Internet-Drafts as reference 47 material or to cite them other than as "work in progress." 48 This Internet-Draft will expire on September 6, 2018. 50 Copyright Notice 52 Copyright (c) 2018 IETF Trust and the persons identified as the 53 document authors. All rights reserved. 55 This document is subject to BCP 78 and the IETF Trust's Legal 56 Provisions Relating to IETF Documents 57 (https://trustee.ietf.org/license-info) in effect on the date of 58 publication of this document. Please review these documents 59 carefully, as they describe your rights and restrictions with respect 60 to this document. Code Components extracted from this document must 61 include Simplified BSD License text as described in Section 4.e of 62 the Trust Legal Provisions and are provided without warranty as 63 described in the Simplified BSD License. 65 Table of Contents 67 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 68 2. Scheduling Function Identifier . . . . . . . . . . . . . . . 3 69 3. Allocated and Used Cells . . . . . . . . . . . . . . . . . . 3 70 4. Overprovisioning . . . . . . . . . . . . . . . . . . . . . . 3 71 5. Scheduling Algorithm . . . . . . . . . . . . . . . . . . . . 4 72 5.1. SFX Triggering Events . . . . . . . . . . . . . . . . . . 4 73 5.2. SFX Cell Estimation Algorithm . . . . . . . . . . . . . . 4 74 5.3. SFX Allocation Policy . . . . . . . . . . . . . . . . . . 5 75 6. Rules for CellList . . . . . . . . . . . . . . . . . . . . . 7 76 7. 6P Timeout Value . . . . . . . . . . . . . . . . . . . . . . 7 77 8. Meaning of Metadata Information . . . . . . . . . . . . . . . 8 78 9. Node Behavior at Boot . . . . . . . . . . . . . . . . . . . . 8 79 10. Cell Type . . . . . . . . . . . . . . . . . . . . . . . . . . 8 80 11. SFX Statistics . . . . . . . . . . . . . . . . . . . . . . . 8 81 12. Relocating Cells . . . . . . . . . . . . . . . . . . . . . . 8 82 13. Forced Cell Deletion Policy . . . . . . . . . . . . . . . . . 9 83 14. 6P Error Handling . . . . . . . . . . . . . . . . . . . . . . 9 84 15. Experimental requirements . . . . . . . . . . . . . . . . . . 9 85 16. Security Considerations . . . . . . . . . . . . . . . . . . . 10 86 17. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 10 87 17.1. SFX Scheduling Function Identifiers . . . . . . . . . . 10 88 18. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 10 89 19. References . . . . . . . . . . . . . . . . . . . . . . . . . 11 90 19.1. Normative References . . . . . . . . . . . . . . . . . . 11 91 19.2. Informative References . . . . . . . . . . . . . . . . . 11 92 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11 94 1. Introduction 96 This document defines a Scheduling Function using the 6P protocol 97 [I-D.ietf-6tisch-6top-protocol], called "Experimental Scheduling 98 Function" (SFX). SFX is designed to offer a number of 99 functionalities to be usable in a wide range of applications. SFX 100 defines two algorithms: the Scheduling Algorithm which defines the 101 number of cells to allocate/delete between two neighbors, and the 102 Relocation Algorithm defines when to relocate a cell. 104 To synthesize, a node running SFX determines when to add/delete cells 105 in a three-step process: 107 1. It waits for a triggering event (Section 5.1). 108 2. It applies the Cell Estimation Algorithm (CEA) for a particular 109 neighbor to determine how many cells are required to that 110 neighbor (Section 5.2). 111 3. It applies the Allocation Policy to compare the number of 112 required cells to the number of already scheduled cells, and 113 determines the number of cells to add/delete (Section 5.3). 115 SFX addresses the requirements for a scheduling function listed in 116 Section 5.2 from [I-D.ietf-6tisch-6top-protocol], and follows the 117 recommended outline listed in Section 5.3 of 118 [I-D.ietf-6tisch-6top-protocol]. This document follows the 119 terminology defined in [I-D.ietf-6tisch-terminology]. 121 2. Scheduling Function Identifier 123 The Scheduling Function Identifier (SFID) of SFX is 124 IANA_6TISCH_SFID_SFX. 126 3. Allocated and Used Cells 128 An allocated cell is assigned as a TX, RX or Shared cell on the 129 schedule, as a reserved resource. This reservation does not imply 130 that a packet will be transmitted during the scheduled cell time. A 131 used cell is a cell where a packet has been transmitted during the 132 scheduled cell time on the last slotframe. 134 4. Overprovisioning 136 Overprovisioning is the action and effect of increasing a value 137 representing an amount of resources. In the case of SFX, 138 overprovisioning is done as a provision to reduce traffic variability 139 effects on packet loss, to the expense of artificially allocating a 140 number of cells. 142 5. Scheduling Algorithm 144 A number of TX cells must be allocated between neighbor nodes in 145 order to enable data transmission among them. A portion of these 146 allocated cells will be used by neighbors, while the remaining cells 147 can be over-provisioned to handle unanticipated increases in cell 148 requirements. The Scheduling Algorithm collects the cell allocation/ 149 deallocation requests from the neighbors and the number of cells 150 which are currently under usage. First, the Cell Estimation 151 Algorithm calculates the number of required cells and second, the 152 calculated number is transferred to the Allocation Policy. In order 153 to reduce consumption, this algorithm is triggered only when there is 154 a change on the number of used cells from a particular node. 156 5.1. SFX Triggering Events 158 We RECOMMEND SFX to be triggered by the following event: if there is 159 a change on the number of used cells towards any of the neighbors. 160 The exact mechanism of when SFX is triggered is implementation- 161 specific. 163 5.2. SFX Cell Estimation Algorithm 165 The Cell Estimation Algorithm takes into account the number of 166 currently used cells to the neighbor. This allows the algorithm to 167 estimate a new number of cells to be scheduled to the neighbor. As a 168 consequence, the Cell Estimation Algorithm for SFX follows the steps 169 described below: 171 1. Collect the current number of used cells to the neighbor. 172 2. Calculate the new number of cells to be scheduled to the neighbor 173 by adding the current number of used cells plus an OVERPROVISION 174 number of cells. 175 3. Transfer the request to the allocation policy as REQUIREDCELLS. 176 4. Return to step 1 and wait for a triggering event. 178 The Cell Estimation Algorithm is depicted in Figure 1. The 179 OVERPROVISION parameter is calculated as a percentage of the number 180 of currently scheduled cells to the neighbor. OVERPROVISION is added 181 to the amount of used cells to the neighbor to reduce the probability 182 of packet loss given a sudden growth on the number of used cells to 183 the neighbor. The OVERPROVISION value is implementation-specific. A 184 value of OVERPROVISION equal to zero leads to queue growth and 185 possible packet loss. In this case, there are no overprovisioned 186 cells where a sudden growth on the number of cells can absorbed and 187 detected. 189 +-------------------+ 190 | Triggering | 191 | Event |<-----+ 192 | | | 193 +-------------------+ | 194 | | 195 V | 196 +-------------------+ | 197 | Collect number of | | 198 | used cells | | 199 +-------------------+ | 200 | | 201 V | 202 +-------------------+ | 203 | used cells | | 204 | + | | 205 | OVERPROVISION | | 206 | = | | 207 | REQUIREDCELLS | | 208 +-------------------+ | 209 | | 210 V | 211 +-------------------+ | 212 | REQUIREDCELLS | | 213 | | | | 214 | V |------+ 215 | Allocation | 216 | Policy | 217 +-------------------+ 219 Figure 1: The SFX Estimation Algorithm 221 5.3. SFX Allocation Policy 223 The "Allocation Policy" is the set of rules used by SFX to decide 224 when to add/delete cells to a particular neighbor to satisfy the cell 225 requirements. 227 SFX uses the following parameters: 229 SCHEDULEDCELLS: The number of cells scheduled from the current node 230 to a particular neighbor. 231 REQUIREDCELLS: The number of cells calculated by the Cell Estimation 232 Algorithm from the current node to that neighbor. 233 SFXTHRESH: Threshold parameter introducing cell over-provisioning in 234 the allocation policy. It is a non-negative value expressed as a 235 number of cells. The definition of this value is implementation- 236 specific. A setting of SFXTHRESH>0 causes the node to allocate at 237 least SFXTHRESH cells to each of its' neighbors. 239 The SFX allocation policy compares REQUIREDCELLS with SCHEDULEDCELLS 240 and decides to add/delete cells taking into account SFXTHRESH. This 241 is illustrated in Figure 2. The number of cells to be added/deleted 242 is out of the scope of this document and it is implementation- 243 dependent. 245 SCHEDULEDCELLS 246 <---------------------------------> 247 +---+---+---+---+---+---+---+---+---+ 248 | | | | | | | | | | 249 +---+---+---+---+---+---+---+---+---+ 250 |<----------------->| 251 | SFXTHRESH | 252 | | 253 REQUIREDCELLS | | 254 +---+---+ | | DELETE 255 | | | | | ONE/MORE 256 +---+---+ | | CELLS 257 | | 258 REQUIREDCELLS | 259 +---+---+---+---+---+---+ | DO 260 | | | | | | | | NOTHING 261 +---+---+---+---+---+---+ | 262 | | 263 REQUIREDCELLS | 264 +---+---+---+---+---+---+---+---+---+---+ ADD 265 | | | | | | | | | | | ONE/MORE 266 +---+---+---+---+---+---+---+---+---+---+ CELLS 268 Figure 2: The SFX Allocation Policy 270 1. If REQUIREDCELLS<(SCHEDULEDCELLS-SFXTHRESH), delete one or more 271 cells. 272 2. If (SCHEDULEDCELLS-SFXTHRESH)<=REQUIREDCELLS<=SCHEDULEDCELLS, do 273 nothing. 274 3. If SCHEDULEDCELLS|B|-----Second Exchange----->|A| 325 |Complete transaction------------------------------------------| 327 Figure 3: Example Transaction where the timeout does not expire 329 |Timeout Value----------------------------------------------| 330 |A|------First Exchange-------->|B|-----Second Exchange----->|A| 331 |Non-Complete transaction--------------------------------------| 333 Figure 4: Example Transaction where the timeout expires 335 8. Meaning of Metadata Information 337 The Metadata 16-bit field is used as follows: 339 BITS 0-7 [SLOTFRAME] are used to identify the slotframe number 340 BITS 8-14 [TIMEOUT] represents the Timeout value 341 BIT 15 [WBLIST] is used to indicate that the CellList provided is 342 a Whitelist (value=0) or a Blacklist (value=1). 344 9. Node Behavior at Boot 346 In order to define a known state after the node is restarted, a CLEAR 347 command is issued to each of the neighbor nodes to enable a new 348 allocation process and at least a SFXTHRESH number of cells MUST be 349 allocated to each of the neighbors. 351 10. Cell Type 353 SFX uses the TX (Transmission) cell type only, thus defining 354 celloptions as TX=0, RX=1 and S=0 according to section 4.2.6 of 355 [I-D.ietf-6tisch-6top-protocol]. 357 11. SFX Statistics 359 Packet Delivery Rate (PDR) is calculated per cell, as the percentage 360 of acknowledged packets, for the last 10 packet transmission 361 attempts. There is no retransmission policy on SFX. 363 12. Relocating Cells 365 Allocated cells may experience packet loss from different sources, 366 such as noise, interference or cell collision (after the same cell is 367 allocated by other nodes in range on the network). 369 SFX uses Packet Delivery Rate (PDR) statistics to monitor the 370 currently allocated cells for cell relocation (by changing their 371 slotOffset and/or channelOffset). When the PDR of one or more 372 softcells is below PDR_THRESHOLD, SFX relocates each of the cell(s) 373 to a number of available cells selected randomly. PDR_THRESHOLD is 374 out of the scope of this document and it is implementation-dependent. 376 13. Forced Cell Deletion Policy 378 When all the cells are scheduled, we need a policy to free cells, for 379 example, under alarm conditions, or if a node disappears from the 380 neighbor list. The action to follow this condition is out of scope 381 of this document and it is implementation-dependent. 383 14. 6P Error Handling 385 A node implementing SFX handles a 6P Response depending on the Return 386 Code it contains: 388 RC_SUCCESS: 389 If the number of elements in the CellList is the number of cells 390 specified in the NumCells field of the 6P ADD Request, the 391 operation is complete. The node does not take further action. 392 If the number of elements in the CellList is smaller (possibly 0) 393 than the number of cells specified in the NumCells field of the 6P 394 ADD Request, the neighbor has received the request, but less than 395 NumCells of the cells in the CellList were allocated. In that 396 case, the node MAY retry immediately with a different CellList if 397 the amount of storage space permits, or build a new (random) 398 CellList. 399 RC_EOL: If an LIST command is issued and the RC_EOL is received, the 400 node MUST understand what is specified on Section 3.3.5 of 401 [I-D.ietf-6tisch-6top-protocol]. 402 RC_ERR_VER: The node MUST NOT retry immediately. The node MAY add 403 the neighbor node to a blacklist. The node MAY retry to contact 404 this neighbor later. 405 RC_ERR_SFID: The node MUST NOT retry immediately. The node MAY add 406 the neighbor node to a blacklist. The node MAY retry to contact 407 this neighbor later. 408 RC_ERR_SEQNUM: The node MUST issue a CLEAR command to the neighbor. 409 RC_ERR_BUSY: Wait for a timeout and restart the scheduling process. 410 RC_ERR_CELLLIST: Wait for a timeout and restart the scheduling 411 process. 412 RC_ERR_LOCKED: Wait for a timeout and restart the scheduling 413 process. 414 RC_RESET: Abort 6P Transaction. 415 RC_ERR: Abort 6P Transaction. The node MAY retry to contact this 416 neighbor later. 418 15. Experimental requirements 420 In order to evaluate the performance of this draft, we propose the 421 following experimental work: 423 1. Define values for OVERPROVISION, SFXTHRESH and ranges to the 424 number of cells to Add or Delete after the Allocation Policy is 425 applied for typical use cases. 426 2. Analyze the scheduling stability (in terms of oscillation) and 427 the hysteresis effect on scheduling using SFX. A tradeoff shall 428 be found between the reactivity of the algorithm facing new 429 scheduling requirements and the number of overprovisioned cells. 430 3. Define the PDR value below the Average which is most effective 431 for blacklisting cells and a method to whitelist cells. Analyze 432 the stability and long-term behavior of this algorithm. 433 4. Measure the distribution of cell scheduling delay (including the 434 time taken by 6P) to estimate timeouts for different type of 435 transactions. 437 16. Security Considerations 439 SFX is defined as an algorithm designed to efficiently fulfill 440 bandwidth requirements between neighbour nodes and does not define a 441 new protocol SFX uses the Minimal IPv6 over the TSCH Mode of IEEE 442 802.15.4e (6TiSCH) Configuration standardized on [RFC8180] and the 443 6top Protocol (6P): [I-D.ietf-6tisch-6top-protocol]. SFX relies on 444 the security framework described on 445 [I-D.ietf-6tisch-minimal-security]. 447 17. IANA Considerations 449 17.1. SFX Scheduling Function Identifiers 451 This document provide a new element to the "6P Scheduling Function 452 Identifiers" sub-registry, which is part of the "IPv6 over the TSCH 453 mode of IEEE 802.15.4e (6TiSCH) parameters" registry, as defined by 454 [I-D.ietf-6tisch-6top-protocol]. This Subtype is defined on figure 455 Figure 5 457 +----------------------+--------------------------+-------------+ 458 | SFID | Name | Reference | 459 +----------------------+--------------------------+-------------+ 460 | IANA_6TISCH_SFID_SFX | Experimental Scheduling | RFCXXXX | 461 | | Function (SFX) | (NOTE:this) | 462 +----------------------+--------------------------+-------------+ 464 Figure 5: IETF IE Subtype '6P' 466 18. Acknowledgments 468 Thanks to Kris Pister for his contribution in designing the default 469 Bandwidth Estimation Algorithm. Thanks to Qin Wang and Thomas 470 Watteyne for their support in defining the interaction between SFX 471 and the 6top sublayer. 473 This work is partially supported by the Fondecyt 1121475 Project, the 474 Inria-Chile "Network Design" group, and the IoT6 European Project 475 (STREP) of the 7th Framework Program (Grant 288445). 477 19. References 479 19.1. Normative References 481 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 482 Requirement Levels", BCP 14, RFC 2119, 483 DOI 10.17487/RFC2119, March 1997, 484 . 486 [RFC8180] Vilajosana, X., Ed., Pister, K., and T. Watteyne, "Minimal 487 IPv6 over the TSCH Mode of IEEE 802.15.4e (6TiSCH) 488 Configuration", BCP 210, RFC 8180, DOI 10.17487/RFC8180, 489 May 2017, . 491 19.2. Informative References 493 [I-D.ietf-6tisch-6top-protocol] 494 Wang, Q., Vilajosana, X., and T. Watteyne, "6top Protocol 495 (6P)", draft-ietf-6tisch-6top-protocol-09 (work in 496 progress), October 2017. 498 [I-D.ietf-6tisch-minimal-security] 499 Vucinic, M., Simon, J., Pister, K., and M. Richardson, 500 "Minimal Security Framework for 6TiSCH", draft-ietf- 501 6tisch-minimal-security-04 (work in progress), October 502 2017. 504 [I-D.ietf-6tisch-terminology] 505 Palattella, M., Thubert, P., Watteyne, T., and Q. Wang, 506 "Terms Used in IPv6 over the TSCH mode of IEEE 802.15.4e", 507 draft-ietf-6tisch-terminology-10 (work in progress), March 508 2018. 510 Authors' Addresses 511 Diego Dujovne (editor) 512 Universidad Diego Portales 513 Escuela de Informatica y Telecomunicaciones 514 Av. Ejercito 441 515 Santiago, Region Metropolitana 516 Chile 518 Phone: +56 (2) 676-8121 519 Email: diego.dujovne@mail.udp.cl 521 Luigi Alfredo Grieco 522 Politecnico di Bari 523 Department of Electrical and Information Engineering 524 Via Orabona 4 525 Bari 70125 526 Italy 528 Phone: 00390805963911 529 Email: a.grieco@poliba.it 531 Maria Rita Palattella 532 Luxembourg Institute of Science and Technology (LIST) 533 Department 'Environmental Research and Innovation' (ERIN) 534 41, rue du Brill 535 Belvaux L-4422 536 Grand-duchy of Luxembourg 538 Phone: +352 275 888-5055 539 Email: mariarita.palattella@list.lu 541 Nicola Accettura 542 LAAS-CNRS 543 7, avenue du Colonel Roche 544 Toulouse 31400 545 France 547 Phone: +33 5 61 33 69 76 548 Email: nicola.accettura@laas.fr