idnits 2.17.1 draft-ietf-6tisch-6top-sf0-05.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 (July 2, 2017) is 2490 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Missing Reference: 'SLOTFRAME' is mentioned on line 364, but not defined == Missing Reference: 'TIMEOUT' is mentioned on line 365, but not defined == Missing Reference: 'WBLIST' is mentioned on line 366, but not defined == Missing Reference: 'TEMPORARY' is mentioned on line 553, but not defined == Outdated reference: A later version (-12) exists of draft-ietf-6tisch-6top-protocol-07 == Outdated reference: A later version (-10) exists of draft-ietf-6tisch-terminology-09 -- Obsolete informational reference (is this intentional?): RFC 6982 (Obsoleted by RFC 7942) Summary: 0 errors (**), 0 flaws (~~), 7 warnings (==), 2 comments (--). 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: January 3, 2018 Politecnico di Bari 6 MR. Palattella 7 Luxembourg Institute of Science and Technology (LIST) 8 N. Accettura 9 LAAS-CNRS 10 July 2, 2017 12 6TiSCH 6top Scheduling Function Zero (SF0) 13 draft-ietf-6tisch-6top-sf0-05 15 Abstract 17 This document defines a Scheduling Function called "Scheduling 18 Function Zero" (SF0). SF0 dynamically adapts the number of scheduled 19 cells between neighbor nodes, based on the amount of currently 20 allocated cells and the neighbor nodes' cell requirements. Neighbor 21 nodes negotiate in a distributed neighbor-to-neighbor basis the 22 number of cell(s) to be added/deleted. SF0 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 http://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 January 3, 2018. 50 Copyright Notice 52 Copyright (c) 2017 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 (http://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. TEMPORARY EDITORIAL NOTES . . . . . . . . . . . . . . . . . . 3 68 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 69 3. Scheduling Function Identifier . . . . . . . . . . . . . . . 4 70 4. Allocated and Used Cells . . . . . . . . . . . . . . . . . . 4 71 5. Overprovisioning . . . . . . . . . . . . . . . . . . . . . . 4 72 6. Scheduling Algorithm . . . . . . . . . . . . . . . . . . . . 4 73 6.1. SF0 Triggering Events . . . . . . . . . . . . . . . . . . 4 74 6.2. SF0 Cell Estimation Algorithm . . . . . . . . . . . . . . 4 75 6.3. SF0 Allocation Policy . . . . . . . . . . . . . . . . . . 6 76 7. Rules for CellList . . . . . . . . . . . . . . . . . . . . . 8 77 8. 6P Timeout Value . . . . . . . . . . . . . . . . . . . . . . 8 78 9. Meaning of Metadata Information . . . . . . . . . . . . . . . 9 79 10. Node Behavior at Boot . . . . . . . . . . . . . . . . . . . . 9 80 11. Cell Type . . . . . . . . . . . . . . . . . . . . . . . . . . 9 81 12. SF0 Statistics . . . . . . . . . . . . . . . . . . . . . . . 9 82 13. Relocating Cells . . . . . . . . . . . . . . . . . . . . . . 9 83 14. Forced Cell Deletion Policy . . . . . . . . . . . . . . . . . 10 84 15. 6P Error Handling . . . . . . . . . . . . . . . . . . . . . . 10 85 16. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 10 86 17. Implementation Status . . . . . . . . . . . . . . . . . . . . 10 87 18. Security Considerations . . . . . . . . . . . . . . . . . . . 11 88 19. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 89 20. 6P Compliance . . . . . . . . . . . . . . . . . . . . . . . . 11 90 21. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 12 91 22. References . . . . . . . . . . . . . . . . . . . . . . . . . 12 92 22.1. Normative References . . . . . . . . . . . . . . . . . . 12 93 22.2. Informative References . . . . . . . . . . . . . . . . . 12 94 Appendix A. [TEMPORARY] Changelog . . . . . . . . . . . . . . . 13 95 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 13 97 1. TEMPORARY EDITORIAL NOTES 99 This document is an Internet Draft, so it is work-in-progress by 100 nature. It contains the following work-in-progress elements: 102 o "TODO" statements are elements which have not yet been written by 103 the authors for some reason (lack of time, ongoing discussions 104 with no clear consensus, etc). The statement does indicate that 105 the text will be written at some time. 106 o "TEMPORARY" appendices are there to capture current ongoing 107 discussions, or the changelog of the document. These appendices 108 will be removed in the final text. 109 o "IANA_" identifiers are placeholders for numbers assigned by IANA. 110 These placeholders are to be replaced by the actual values they 111 represent after their assignment by IANA. 112 o The string "REMARK" is put before a remark (questions, suggestion, 113 etc) from an author, editor of contributor. These are on-going 114 discussions at the time to writing, NOT part of the final text. 115 o This section will be removed in the final text. 117 2. Introduction 119 This document defines a minimal Scheduling Function using the 6P 120 protocol [I-D.ietf-6tisch-6top-protocol], called "Scheduling Function 121 Zero" (SF0). SF0 is designed to offer a number of functionalities to 122 be usable in a wide range of applications. SF0 defines two 123 algorithms: The Scheduling Algorithm defines the number of cells to 124 allocate/delete between two neighbours and the Relocation Algorithm 125 defines when to relocate a cell. 127 To synthesize, a node running SF0 determines when to add/delete cells 128 in a three-step process: 130 1. It waits for a triggering event (Section 6.1). 131 2. It applies the Cell Estimation Algorithm (CEA) for a particular 132 neighbor to determine how many cells are required to that 133 neighbor (Section 6.2). 134 3. It applies the Allocation Policy to compare the number of 135 required cells to the number of already scheduled cells, and 136 determines the number of cells to add/delete (Section 6.3). 138 We expect additional SFs, offering more functionalities for a more 139 specific use case, to be defined in future documents. SF0 addresses 140 the requirements for a scheduling function listed in Section 5.2 from 141 [I-D.ietf-6tisch-6top-protocol], and follows the recommended outline 142 listed in Section 5.3 of [I-D.ietf-6tisch-6top-protocol]. This 143 document follows the terminology defined in 144 [I-D.ietf-6tisch-terminology]. 146 3. Scheduling Function Identifier 148 The Scheduling Function Identifier (SFID) of SF0 is 149 IANA_6TISCH_SFID_SF0. 151 4. Allocated and Used Cells 153 An allocated cell is assigned as a TX, RX or Shared cell on the 154 schedule, as a reserved resource. This reservation does not imply 155 that a packet will be transmitted during the scheduled cell time. A 156 used cell is a cell where a packet has been transmitted during the 157 scheduled cell time on the last slotframe. 159 5. Overprovisioning 161 Overprovisioning is the action and effect of increasing a value 162 representing an amount of resources. In the case of SF0, 163 overprovisioning is done as a provision to reduce traffic variability 164 effects on packet loss, to the expense of artificially allocating a 165 number of cells. 167 6. Scheduling Algorithm 169 A number of TX cells must be allocated between neighbor nodes in 170 order to enable data transmission among them. A portion of these 171 allocated cells will be used by neighbors, while the remaining cells 172 can be over-provisioned to handle unanticipated increases in cell 173 requirements. The Scheduling Algorithm collects the cell allocation/ 174 deallocation requests from the neighbors and the number of cells 175 which are currently under usage. First, the Cell Estimation 176 Algorithm calculates the number of required cells and second, the 177 calculated number is transferred to the Allocation Policy. In order 178 to reduce consumption, this algorithm is triggered only when there is 179 a change on the number of used cells from a particular node. 181 6.1. SF0 Triggering Events 183 We RECOMMEND SF0 to be triggered at by the following event: If there 184 is a change on the number of used cells towards any of the 185 neighbours. The exact mechanism of when SF0 is triggered is 186 implementation-specific. 188 6.2. SF0 Cell Estimation Algorithm 190 The Cell Estimation Algorithm takes into account the number of 191 current used cells to the neighbour. This allows the algorithm to 192 estimate a new number of cells to be scheduled to the neighbour. As 193 a consequence, the Cell Estimation Algorithm for SF0 follows the 194 steps described below: 196 1. Collect the current number of used cells to the neighbour 197 2. Calculate the new number of cells to be scheduled to the 198 neighbour by adding the current number of used cells plus an 199 OVERPROVISION number of cells 200 3. Transfer the request to the allocation policy as REQUIREDCELLS 201 4. Return to step 1 and wait for a triggering event. 203 The Cell Estimation Algorithm is depicted on figure Figure 1. The 204 OVERPROVISION parameter is calculated as a percentage of the number 205 of currently scheduled cells to the neighbour. OVERPROVISION is 206 added to the amount of used cells to the neighbour to reduce the 207 probability of packet loss given a sudden growth on the number of 208 used cells to the neighbour. The OVERPROVISION value is 209 implementation-specific. A value of OVERPROVISION equal to zero 210 leads to queue growth and possible packet loss: In this case, there 211 are no overprovisioned cells where a sudden growth on the number of 212 cells can absorbed and detected. 214 +-------------------+ 215 | Triggering | 216 | Event |<-----+ 217 | | | 218 +-------------------+ | 219 | | 220 V | 221 +-------------------+ | 222 | Collect number of | | 223 | used cells | | 224 +-------------------+ | 225 | | 226 V | 227 +-------------------+ | 228 | used cells | | 229 | + | | 230 | OVERPROVISION | | 231 | = | | 232 | REQUIREDCELLS | | 233 +-------------------+ | 234 | | 235 V | 236 +-------------------+ | 237 | REQUIREDCELLS | | 238 | | | | 239 | V |------+ 240 | Allocation | 241 | Policy | 242 +-------------------+ 244 Figure 1: The SF0 Estimation Algorithm 246 6.3. SF0 Allocation Policy 248 The "Allocation Policy" is the set of rules used by SF0 to decide 249 when to add/delete cells to a particular neighbor to satisfy the cell 250 requirements. 252 SF0 uses the following parameters: 254 SCHEDULEDCELLS: The number of cells scheduled from the current node 255 to a particular neighbor. 256 REQUIREDCELLS: The number of cells calculated by the Cell Estimation 257 Algorithm from the current node to that neighbor. 258 SF0THRESH: Threshold parameter introducing cell over-provisioning in 259 the allocation policy. It is a non-negative value expressed as 260 number of cells. The definition of this value is implementation- 261 specific. A setting of SF0THRESH>0 will cause the node to 262 allocate at least SF0THRESH cells to each of its' neighbors. 264 The SF0 allocation policy compares REQUIREDCELLS with SCHEDULEDCELLS 265 and decides to add/delete cells taking into account SF0THRESH. This 266 is illustrated in Figure 2. The number of cells to be added/deleted 267 is out of the scope of this document and it is implementation- 268 dependent. 270 SCHEDULEDCELLS 271 <---------------------------------> 272 +---+---+---+---+---+---+---+---+---+ 273 | | | | | | | | | | 274 +---+---+---+---+---+---+---+---+---+ 275 |<----------------->| 276 | SF0THRESH | 277 | | 278 REQUIREDCELLS | | 279 +---+---+ | | DELETE 280 | | | | | ONE/MORE 281 +---+---+ | | CELLS 282 | | 283 REQUIREDCELLS | 284 +---+---+---+---+---+---+ | DO 285 | | | | | | | | NOTHING 286 +---+---+---+---+---+---+ | 287 | | 288 REQUIREDCELLS | 289 +---+---+---+---+---+---+---+---+---+---+ ADD 290 | | | | | | | | | | | ONE/MORE 291 +---+---+---+---+---+---+---+---+---+---+ CELLS 293 Figure 2: The SF0 Allocation Policy 295 1. If REQUIREDCELLS<(SCHEDULEDCELLS-SF0THRESH), delete one or more 296 cells. 297 2. If (SCHEDULEDCELLS-SF0THRESH)<=REQUIREDCELLS<=SCHEDULEDCELLS, do 298 nothing. 299 3. If SCHEDULEDCELLS|B|-----Second Exchange----->|A| 350 |Complete transaction------------------------------------------| 352 Figure 3: Example Transaction where the timeout does not expire 354 |Timeout Value----------------------------------------------| 355 |A|------First Exchange-------->|B|-----Second Exchange----->|A| 356 |Non-Complete transaction--------------------------------------| 358 Figure 4: Example Transaction where the timeout expires 360 9. Meaning of Metadata Information 362 The Metadata 16-bit field is used as follows: 364 BITS 0-7 [SLOTFRAME] are used to identify the slotframe number 365 BITS 8-14 [TIMEOUT] represents the Timeout value 366 BIT 15 [WBLIST] is used to indicate that the CellList provided is 367 a Whitelist (value=0) or a Blacklist (value=1). 369 10. Node Behavior at Boot 371 In order to define a known state after the node is restarted, a CLEAR 372 command is issued to each of the neighbor nodes to enable a new 373 allocation process and at least a SF0THRESH number of cells MUST be 374 allocated to each of the neighbours. 376 11. Cell Type 378 SF0 uses TX (Transmission) cell type only, thus defining celloptions 379 as TX=0, RX=1 and S=0 according to section 4.2.6 of 380 [I-D.ietf-6tisch-6top-protocol]. 382 12. SF0 Statistics 384 Packet Delivery Rate (PDR) is calculated per cell, as the percentage 385 of acknowledged packets, for the last 10 packet transmission 386 attempts. There is no retransmission policy on SF0. 388 13. Relocating Cells 390 Allocated cells may experience packet loss from different sources, 391 such as noise, interference or cell collision (after the same cell is 392 allocated by other nodes in range on the network). 394 SF0 uses Packet Delivery Rate (PDR) statistics to monitor the 395 currently allocated cells for cell relocation (by changing their 396 slotOffset and/or channelOffset). When the PDR of one or more 397 softcells is below PDR_THRESHOLD, SF0 relocates each of the cell(s) 398 to a number of available cells selected randomly. PDR_THRESHOLD is 399 out of the scope of this document and it is implementation-dependent. 401 14. Forced Cell Deletion Policy 403 When all the cells are scheduled, we need a policy to free cells, for 404 example, under alarm conditions or if a node disappears from the 405 neighbor list. The action to follow this condition is out of scope 406 of this document and it is implementation-dependent. 408 15. 6P Error Handling 410 A node implementing SF0 handles a 6P Response depending on the Return 411 Code it contains: 413 RC_SUCCESS: 414 If the number of elements in the CellList is the number of cells 415 specified in the NumCells field of the 6P ADD Request, the 416 operation is complete. The node does not take further action. 417 If the number of elements in the CellList is smaller (possibly 0) 418 than the number of cells specified in the NumCells field of the 6P 419 ADD Request, the neighbor has received the request, but less than 420 NumCells of the cells in the CellList were allocated. In that 421 case, the node MAY retry immediately with a different CellList if 422 the amount of storage space permits, or build a new (random) 423 CellList. 424 RC_ERR_VER: The node MUST NOT retry immediately. The node MAY add 425 the neighbor node to a blacklist. The node MAY retry to contact 426 this neighbor later. 427 RC_ERR_SFID: The node MUST NOT retry immediately. The node MAY add 428 the neighbor node to a blacklist. The node MAY retry to contact 429 this neighbor later. 430 RC_ERR_GEN: The node MUST issue a CLEAR command to the neighbour. 431 RC_ERR_BUSY: Wait for a timeout and restart the scheduling process. 432 RC_ERR_NORES: Wait for a timeout and restart the scheduling process. 433 RC_ERR_RESET: Abort 6P Transaction 434 RC_ERR: Abort 6P Transaction. The node MAY retry to contact this 435 neighbor later. 437 16. Examples 439 TODO 441 17. Implementation Status 443 This section records the status of known implementations of the 444 protocol defined by this specification at the time of posting of this 445 Internet-Draft, and is based on a proposal described in [RFC6982]. 446 The description of implementations in this section is intended to 447 assist the IETF in its decision processes in progressing drafts to 448 RFCs. Please note that the listing of any individual implementation 449 here does not imply endorsement by the IETF. Furthermore, no effort 450 has been spent to verify the information presented here that was 451 supplied by IETF contributors. This is not intended as, and must not 452 be construed to be, a catalog of available implementations or their 453 features. Readers are advised to note that other implementations may 454 exist. 456 According to [RFC6982], "this will allow reviewers and working groups 457 to assign due consideration to documents that have the benefit of 458 running code, which may serve as evidence of valuable experimentation 459 and feedback that have made the implemented protocols more mature. 460 It is up to the individual working groups to use this information as 461 they see fit". 463 OpenWSN: This specification is implemented in the OpenWSN project 464 [OpenWSN]. The authors of this document are collaborating with 465 the OpenWSN community to gather feedback about the status and 466 performance of the protocols described in this document. Results 467 from that discussion will appear in this section in future 468 revision of this specification. 470 18. Security Considerations 472 TODO 474 19. IANA Considerations 476 o IANA_6TiSCH_SFID_SF0 478 20. 6P Compliance 480 o MUST specify an identifier for that SF. OK 481 o MUST specify the rule for a node to decide when to add/delete one 482 or more cells to a neighbor. OK 483 o MUST specify the rule for a Transaction source to select cells to 484 add to the CellList field in the 6P ADD Request. OK 485 o MUST specify the rule for a Transaction destination to select 486 cells from CellList to add to its schedule. OK 487 o MUST specify a value for the 6P Timeout, or a rule/equation to 488 calculate it. OK 489 o MUST specify a meaning for the "Metadata" field in the 6P ADD 490 Request. OK 491 o MUST specify the behavior of a node when it boots. OK 492 o MUST specify what to do after an error has occurred (either the 493 node sent a 6P Response with an error code, or received one). OK 494 o MUST specify the list of statistics to gather. An example 495 statistic if the number of transmitted frames to each neighbor. 497 In case the SF requires no statistics to be gathered, the specific 498 of the SF MUST explicitly state so. OK 499 o SHOULD clearly state the application domain the SF is created for. 500 OK 501 o SHOULD contain examples which highlight normal and error 502 scenarios. 503 o SHOULD contain a list of current implementations, at least during 504 the I-D state of the document, per [RFC6982]. 505 o SHOULD contain a performance evaluation of the scheme, possibly 506 through references to external documents. 507 o MAY redefine the format of the CellList? field. OK 509 21. Acknowledgments 511 Thanks to Kris Pister for his contribution in designing the default 512 Bandwidth Estimation Algorithm. Thanks to Qin Wang and Thomas 513 Watteyne for their support in defining the interaction between SF0 514 and the 6top sublayer. 516 This work is partially supported by the Fondecyt 1121475 Project, the 517 Inria-Chile "Network Design" group, and the IoT6 European Project 518 (STREP) of the 7th Framework Program (Grant 288445). 520 22. References 522 22.1. Normative References 524 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 525 Requirement Levels", BCP 14, RFC 2119, 526 DOI 10.17487/RFC2119, March 1997, 527 . 529 22.2. Informative References 531 [I-D.ietf-6tisch-6top-protocol] 532 Wang, Q., Vilajosana, X., and T. Watteyne, "6top Protocol 533 (6P)", draft-ietf-6tisch-6top-protocol-07 (work in 534 progress), June 2017. 536 [I-D.ietf-6tisch-terminology] 537 Palattella, M., Thubert, P., Watteyne, T., and Q. Wang, 538 "Terminology in IPv6 over the TSCH mode of IEEE 539 802.15.4e", draft-ietf-6tisch-terminology-09 (work in 540 progress), June 2017. 542 [OpenWSN] Watteyne, T., Vilajosana, X., Kerkez, B., Chraim, F., 543 Weekly, K., Wang, Q., Glaser, S., and K. Pister, "OpenWSN: 544 a Standards-Based Low-Power Wireless Development 545 Environment", Transactions on Emerging Telecommunications 546 Technologies , August 2012. 548 [RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running 549 Code: The Implementation Status Section", RFC 6982, 550 DOI 10.17487/RFC6982, July 2013, 551 . 553 Appendix A. [TEMPORARY] Changelog 555 o draft-ietf-6tisch-6top-sf0-02 557 * Editorial changes (figs, typos, ...) 558 o draft-ietf-6tisch-6top-sf0-03 560 * Fixed typos 561 * Removed references to "effectively used cells" 562 * Changed Cell Estimation Algorithm to the third proposed 563 alternative on IETF97 564 * Forced cell deletion becomes implementation specific 565 * Added PDR calculation formula 566 * Added PDR_THRESHOLD as implementation specific value 568 Authors' Addresses 570 Diego Dujovne (editor) 571 Universidad Diego Portales 572 Escuela de Informatica y Telecomunicaciones 573 Av. Ejercito 441 574 Santiago, Region Metropolitana 575 Chile 577 Phone: +56 (2) 676-8121 578 Email: diego.dujovne@mail.udp.cl 580 Luigi Alfredo Grieco 581 Politecnico di Bari 582 Department of Electrical and Information Engineering 583 Via Orabona 4 584 Bari 70125 585 Italy 587 Phone: 00390805963911 588 Email: a.grieco@poliba.it 589 Maria Rita Palattella 590 Luxembourg Institute of Science and Technology (LIST) 591 Department 'Environmental Research and Innovation' (ERIN) 592 41, rue du Brill 593 Belvaux L-4422 594 Grand-duchy of Luxembourg 596 Phone: +352 275 888-5055 597 Email: mariarita.palattella@list.lu 599 Nicola Accettura 600 LAAS-CNRS 601 7, avenue du Colonel Roche 602 Toulouse 31400 603 France 605 Phone: +33 5 61 33 69 76 606 Email: nicola.accettura@laas.fr