idnits 2.17.1 draft-ietf-6tisch-6top-sf0-04.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 (April 28, 2017) is 2555 days in the past. Is this intentional? Checking references for intended status: Experimental ---------------------------------------------------------------------------- == Missing Reference: 'SLOTFRAME' is mentioned on line 303, but not defined == Missing Reference: 'WBLIST' is mentioned on line 305, but not defined == Missing Reference: 'TEMPORARY' is mentioned on line 493, but not defined -- Obsolete informational reference (is this intentional?): RFC 6982 (Obsoleted by RFC 7942) == Outdated reference: A later version (-10) exists of draft-ietf-6tisch-terminology-08 == Outdated reference: A later version (-12) exists of draft-ietf-6tisch-6top-protocol-04 Summary: 0 errors (**), 0 flaws (~~), 6 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: October 30, 2017 Politecnico di Bari 6 MR. Palattella 7 Luxembourg Institute of Science and Technology (LIST) 8 N. Accettura 9 LAAS-CNRS 10 April 28, 2017 12 6TiSCH 6top Scheduling Function Zero (SF0) 13 draft-ietf-6tisch-6top-sf0-04 15 Abstract 17 This document defines a Scheduling Function called "Scheduling 18 Function Zero" (SF0). SF0 dynamically adapts the number of allocated 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 October 30, 2017. 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. SF0 Triggering Events . . . . . . . . . . . . . . . . . . . . 4 71 5. SF0 Cell Estimation Algorithm . . . . . . . . . . . . . . . . 4 72 6. SF0 Allocation Policy . . . . . . . . . . . . . . . . . . . . 5 73 7. Rules for CellList . . . . . . . . . . . . . . . . . . . . . 6 74 8. 6P Timeout Value . . . . . . . . . . . . . . . . . . . . . . 7 75 9. Meaning of Metadata Information . . . . . . . . . . . . . . . 7 76 10. Node Behavior at Boot . . . . . . . . . . . . . . . . . . . . 7 77 11. Cell Type . . . . . . . . . . . . . . . . . . . . . . . . . . 7 78 12. SF0 Statistics . . . . . . . . . . . . . . . . . . . . . . . 8 79 13. Relocating Cells . . . . . . . . . . . . . . . . . . . . . . 8 80 14. Forced Cell Deletion Policy . . . . . . . . . . . . . . . . . 8 81 15. 6P Error Handling . . . . . . . . . . . . . . . . . . . . . . 8 82 16. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 9 83 17. Implementation Status . . . . . . . . . . . . . . . . . . . . 9 84 18. Security Considerations . . . . . . . . . . . . . . . . . . . 9 85 19. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 86 20. 6P Compliance . . . . . . . . . . . . . . . . . . . . . . . . 10 87 21. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 10 88 22. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 89 22.1. Normative References . . . . . . . . . . . . . . . . . . 10 90 22.2. Informative References . . . . . . . . . . . . . . . . . 11 91 Appendix A. [TEMPORARY] Changelog . . . . . . . . . . . . . . . 11 92 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 12 94 1. TEMPORARY EDITORIAL NOTES 96 This document is an Internet Draft, so it is work-in-progress by 97 nature. It contains the following work-in-progress elements: 99 o "TODO" statements are elements which have not yet been written by 100 the authors for some reason (lack of time, ongoing discussions 101 with no clear consensus, etc). The statement does indicate that 102 the text will be written at some time. 103 o "TEMPORARY" appendices are there to capture current ongoing 104 discussions, or the changelog of the document. These appendices 105 will be removed in the final text. 106 o "IANA_" identifiers are placeholders for numbers assigned by IANA. 107 These placeholders are to be replaced by the actual values they 108 represent after their assignment by IANA. 109 o The string "REMARK" is put before a remark (questions, suggestion, 110 etc) from an author, editor of contributor. These are on-going 111 discussions at the time to writing, NOT part of the final text. 112 o This section will be removed in the final text. 114 2. Introduction 116 This document defines a minimal Scheduling Function for the 6top 117 sublayer [I-D.ietf-6tisch-6top-protocol], called "Scheduling Function 118 Zero" (SF0). SF0 is designed to offer the minimal set of 119 functionalities to be usable in a wide range of applications. SF0 120 defines two algorithms: The Scheduling Algorithm defines the number 121 of cells to allocate/delete between two neighbours and the relocation 122 algorithm defines when to relocate a cell. 124 The Scheduling Algorithm: A number of TX and/or RX cells must be 125 allocated between neighbor nodes in order to enable data transmission 126 among them. A portion of these allocated cells will be utilized by 127 neighbors, while the remaining cells can be over-provisioned to 128 handle unanticipated increases in cell requirements. The Scheduling 129 Algorithm collects the cell allocation/deletion requests from the 130 neighbors and the number of cells which are currently under usage. 131 First, the Cell Estimation Algotithm calculates the number of 132 required cells by adding the collected values and second, the 133 calculated value is given to the Allocation Policy, which provides 134 stability by adding hystheresis and overprovisioning by deciding when 135 to schedule the new number of cells, according to a threshold. In 136 order to reduce consumption, this algorithm is triggered only when 137 there is a change on the number of effectively used cells or if there 138 is a change on the number of requested cells from a particular node. 140 The Relocation Algorithm: Allocated cells may experience packet loss 141 from different sources, such as noise, interference or cell collision 142 (after the same cell is allocated by other nodes in range on the 143 network). In order to avoid this problem, Packet Delivery Rate (PDR) 144 is monitored periodically for each allocated cell. A relocation is 145 triggered when the PDR value drops below a certain threshold, 146 compared to the average PDR of the rest of allocated cells. The 147 destination location on the schedule is defined randomly. 149 To synthesize, a node running SF0 determines when to add/delete cells 150 in a three-step process: 152 1. It waits for a triggering event (Section 4). 153 2. It applies the Cell Estimation Algorithm (CEA) for a particular 154 neighbor to determine how many cells are required to that 155 neighbor (Section 5). 156 3. It applies the Allocation Policy to compare the number of 157 required cells to the number of already scheduled cells, and 158 determines the number of cells to add/delete (Section 6). 160 We expect additional SFs, offering more functionalities for a more 161 specific use case, to be defined in future documents. SF0 addresses 162 the requirements for a scheduling function listed in Section 5.2 from 163 [I-D.ietf-6tisch-6top-protocol], and follows the recommended outline 164 listed in Section 5.3 of [I-D.ietf-6tisch-6top-protocol]. This 165 document follows the terminology defined in 166 [I-D.ietf-6tisch-terminology]. 168 3. Scheduling Function Identifier 170 The Scheduling Function Identifier (SFID) of SF0 is IANA_SFID_SF0. 172 4. SF0 Triggering Events 174 We RECOMMEND SF0 to be triggered at least by the following events: 176 1. If there is a change in the current number of required cells 177 2. If there is a successful cell allocation/deallocation process 178 with the neighbour. 180 This allows SF0 to be triggered by any change in locally generated or 181 incoming traffic. The exact mechanism of when SF0 is triggered is 182 implementation-specific. 184 5. SF0 Cell Estimation Algorithm 186 The Cell Estimation Algorithm takes into account the new incoming 187 cell requirements from the neighbor node and the current outgoing 188 number of used cells. This allows the algorithm to estimate a new 189 number of cells to be allocated. As a consequence, the Cell 190 Estimation Algorithm for SF0 follows the steps described below: 192 1. Collect the current number of used cells 193 2. Calculate the new number of cells to be allocated by adding the 194 current number of used cells plus an OVERPROVISION number of 195 cells 196 3. Submit the request to the allocation policy as REQUIREDCELLS 197 4. Return to step 1 and wait for a triggering event. 199 The OVERPROVISION parameter is a percentage of the currently 200 allocated cells which is added to the used cells to guarantee that 201 the growth on the number of used cells can be detected without packet 202 loss. This percentage value is implementation-specific. A value of 203 OVERPROVISION equal to zero leads to queue growth and possible packet 204 loss, since there are no overprovisioned cells to detect if there is 205 a growth on the number of used cells. 207 6. SF0 Allocation Policy 209 The "Allocation Policy" is the set of rules used by SF0 to decide 210 when to add/delete cells to a particular neighbor to satisfy the cell 211 requirements. 213 SF0 uses the following parameters: 215 SCHEDULEDCELLS: The number of cells scheduled from the current node 216 to a particular neighbor. 217 REQUIREDCELLS: The number of cells calculated by the Cell Estimation 218 Algorithm from the current node to that neighbor. 219 SF0THRESH: Threshold parameter introducing cell over-provisioning in 220 the allocation policy. It is a non-negative value expressed as 221 number of cells. The definition of this value is implementation- 222 specific. A setting of SF0THRESH>0 will cause the node to 223 allocate at least SF0THRESH cells to each of its' neighbors. 225 The SF0 allocation policy compares REQUIREDCELLS with SCHEDULEDCELLS 226 and decides to add/delete cells taking into account SF0THRESH. This 227 is illustrated in Figure 1. The number of cells to be scheduled/ 228 deleted is out of the scope of this document and it is 229 implementation-dependent. 231 SCHEDULEDCELLS 232 <---------------------------------> 233 +---+---+---+---+---+---+---+---+---+ 234 | | | | | | | | | | 235 +---+---+---+---+---+---+---+---+---+ 236 |<----------------->| 237 | SF0THRESH | 238 | | 239 REQUIREDCELLS | | 240 +---+---+ | | DELETE 241 | | | | | ONE/MORE 242 +---+---+ | | CELLS 243 | | 244 REQUIREDCELLS | 245 +---+---+---+---+---+---+ | DO 246 | | | | | | | | NOTHING 247 +---+---+---+---+---+---+ | 248 | | 249 REQUIREDCELLS | 250 +---+---+---+---+---+---+---+---+---+---+ ADD 251 | | | | | | | | | | | ONE/MORE 252 +---+---+---+---+---+---+---+---+---+---+ CELLS 254 Figure 1: The SF0 Allocation Policy 256 1. If REQUIREDCELLS<(SCHEDULEDCELLS-SF0THRESH), delete one or more 257 cells. 258 2. If (SCHEDULEDCELLS-SF0THRESH)<=REQUIREDCELLS<=SCHEDULEDCELLS, do 259 nothing. 260 3. If SCHEDULEDCELLS<=REQUIREDCELLS, add one or more cells. 262 When SF0THRESH equals 0, any discrepancy between REQUIREDCELLS and 263 SCHEDULEDCELLS triggers an action to add/delete cells. Positive 264 values of SF0THRESH reduce the number of 6P Transactions. 266 7. Rules for CellList 268 There are two methods to define the CellList: The Whitelist method, 269 which fills the CellList with the number of proposed cells to the 270 neighbour, and the Blacklist, which fills the CellList with the cells 271 which cannot be used by the neighbour. The rule to select the method 272 is implementation-specific. When issuing a 6top ADD Request, SF0 273 executes the following sequence: 275 Whitelist case: 277 The Transaction Source node: Prepares the CellList field by 278 selecting randomly the required cells, verifying that the slot 279 offset and channel offset are not occupied and choose 280 channelOffset randomly for each cell. 281 The Transaction Destination node: Goes through the cells in the 282 CellList in order, verifying whether there are no slotOffset 283 conflicts. 284 Blacklist case: 286 The Transaction Source node: Prepares the CellList field by 287 building a list of currently scheduled cells into the CellList. 288 The Transaction Destination node: Selects randomly the required 289 cells from the unallocated cells on the schedule, verifying 290 that the slot offset and channel offset are not occupied from 291 the ones on the CellList. 293 8. 6P Timeout Value 295 The general timeout equals the equivalent time of the number of slots 296 until the next scheduled cell. TODO/REMARK: The exact calculation is 297 currently under discussion on the Mailing List. 299 9. Meaning of Metadata Information 301 The Metadata 16-bit field is used as follows: 303 BITS 0-7 [SLOTFRAME] are used to identify the slotframe number 304 BITS 8-14 are RESERVED 305 BIT 15 [WBLIST] is used to indicate that the CellList provided is 306 a Whitelist (value=0) or a Blacklist (value=1). 308 10. Node Behavior at Boot 310 In order to define a known state after the node is restarted, a CLEAR 311 command is issued to each of the neighbor nodes to enable a new 312 allocation process. The 6P Initial Timeout Value provided by SF0 313 should allow for the maximum number of TSCH link-layer retries, as 314 defined by Section 4.3.4 of [I-D.ietf-6tisch-6top-protocol]. TODO/ 315 REMARK: The initial timeout is currently under discussion on the 316 Mailing List. 318 11. Cell Type 320 SF0 uses TX (Transmission) cell type only, thus defining celloptions 321 as TX=0, RX=1 and S=0 according to section 4.2.6 of 322 [I-D.ietf-6tisch-6top-protocol]. 324 12. SF0 Statistics 326 Packet Delivery Rate (PDR) is calculated per cell, as the quotient of 327 the number of successfully delivered packets to 10, for the last 10 328 packet transmission attempts, without counting retransmissions. 330 13. Relocating Cells 332 SF0 uses Packet Delivery Rate (PDR) statistics to monitor the 333 currently allocated cells for cell relocation (by changing their 334 slotOffset and/or channelOffset). When the PDR of one or more 335 softcells is below PDR_THRESHOLD, defined as a percentage of the 336 average of the PDR of the rest of the scheduled cells, SF0 relocates 337 each of the cell(s) to a number of available cells selected randomly. 338 PDR_THRESHOLD is out of the scope of this document and it is 339 implementation-dependent. 341 14. Forced Cell Deletion Policy 343 When all the cells are scheduled, we need a policy to free cells, for 344 example, under alarm conditions or if a node disappears from the 345 neighbor list. The action to follow this condition is out of scope 346 of this document and it is implementation-dependent. 348 15. 6P Error Handling 350 A node implementing SF0 handles a 6P Response depending on the Return 351 Code it contains: 353 RC_SUCCESS: 354 If the number of elements in the CellList is the number of cells 355 specified in the NumCells field of the 6P ADD Request, the 356 operation is complete. The node does not take further action. 357 If the number of elements in the CellList is smaller (possibly 0) 358 than the number of cells specified in the NumCells field of the 6P 359 ADD Request, the neighbor has received the request, but less than 360 NumCells of the cells in the CellList were allocated. In that 361 case, the node MAY retry immediately with a different CellList if 362 the amount of storage space permits, or build a new (random) 363 CellList. 364 RC_ERR_VER: The node MUST NOT retry immediately. The node MAY add 365 the neighbor node to a blacklist. The node MAY retry to contact 366 this neighbor later. 367 RC_ERR_SFID: The node MUST NOT retry immediately. The node MAY add 368 the neighbor node to a blacklist. The node MAY retry to contact 369 this neighbor later. 370 RC_ERR_GEN: The node MUST issue a CLEAR command to the neighbour. 371 RC_ERR_BUSY: Wait for a timeout and restart the scheduling process. 373 RC_ERR_NORES: Wait for a timeout and restart the scheduling process. 374 RC_ERR_RESET: Abort 6P Transaction 375 RC_ERR: Abort 6P Transaction. The node MAY retry to contact this 376 neighbor later. 378 16. Examples 380 TODO 382 17. Implementation Status 384 This section records the status of known implementations of the 385 protocol defined by this specification at the time of posting of this 386 Internet-Draft, and is based on a proposal described in [RFC6982]. 387 The description of implementations in this section is intended to 388 assist the IETF in its decision processes in progressing drafts to 389 RFCs. Please note that the listing of any individual implementation 390 here does not imply endorsement by the IETF. Furthermore, no effort 391 has been spent to verify the information presented here that was 392 supplied by IETF contributors. This is not intended as, and must not 393 be construed to be, a catalog of available implementations or their 394 features. Readers are advised to note that other implementations may 395 exist. 397 According to [RFC6982], "this will allow reviewers and working groups 398 to assign due consideration to documents that have the benefit of 399 running code, which may serve as evidence of valuable experimentation 400 and feedback that have made the implemented protocols more mature. 401 It is up to the individual working groups to use this information as 402 they see fit". 404 OpenWSN: This specification is implemented in the OpenWSN project 405 [OpenWSN]. The authors of this document are collaborating with 406 the OpenWSN community to gather feedback about the status and 407 performance of the protocols described in this document. Results 408 from that discussion will appear in this section in future 409 revision of this specification. 411 18. Security Considerations 413 TODO 415 19. IANA Considerations 417 o IANA_SFID_SF0 419 20. 6P Compliance 421 o MUST specify an identifier for that SF. OK 422 o MUST specify the rule for a node to decide when to add/delete one 423 or more cells to a neighbor. OK 424 o MUST specify the rule for a Transaction source to select cells to 425 add to the CellList field in the 6P ADD Request. OK 426 o MUST specify the rule for a Transaction destination to select 427 cells from CellList to add to its schedule. OK 428 o MUST specify a value for the 6P Timeout, or a rule/equation to 429 calculate it. OK 430 o MUST specify a meaning for the "Metadata" field in the 6P ADD 431 Request. OK 432 o MUST specify the behavior of a node when it boots. OK 433 o MUST specify what to do after an error has occurred (either the 434 node sent a 6P Response with an error code, or received one). OK 435 o MUST specify the list of statistics to gather. An example 436 statistic if the number of transmitted frames to each neighbor. 437 In case the SF requires no statistics to be gathered, the specific 438 of the SF MUST explicitly state so. OK 439 o SHOULD clearly state the application domain the SF is created for. 440 OK 441 o SHOULD contain examples which highlight normal and error 442 scenarios. 443 o SHOULD contain a list of current implementations, at least during 444 the I-D state of the document, per [RFC6982]. 445 o SHOULD contain a performance evaluation of the scheme, possibly 446 through references to external documents. 447 o MAY redefine the format of the CellList? field. OK 449 21. Acknowledgments 451 Thanks to Kris Pister for his contribution in designing the default 452 Bandwidth Estimation Algorithm. Thanks to Qin Wang and Thomas 453 Watteyne for their support in defining the interaction between SF0 454 and the 6top sublayer. 456 This work is partially supported by the Fondecyt 1121475 Project, the 457 Inria-Chile "Network Design" group, and the IoT6 European Project 458 (STREP) of the 7th Framework Program (Grant 288445). 460 22. References 462 22.1. Normative References 464 [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate 465 Requirement Levels", BCP 14, RFC 2119, 466 DOI 10.17487/RFC2119, March 1997, 467 . 469 22.2. Informative References 471 [RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running 472 Code: The Implementation Status Section", RFC 6982, 473 DOI 10.17487/RFC6982, July 2013, 474 . 476 [I-D.ietf-6tisch-terminology] 477 Palattella, M., Thubert, P., Watteyne, T., and Q. Wang, 478 "Terminology in IPv6 over the TSCH mode of IEEE 479 802.15.4e", draft-ietf-6tisch-terminology-08 (work in 480 progress), December 2016. 482 [I-D.ietf-6tisch-6top-protocol] 483 Wang, Q., Vilajosana, X., and T. Watteyne, "6top Protocol 484 (6P)", draft-ietf-6tisch-6top-protocol-04 (work in 485 progress), March 2017. 487 [OpenWSN] Watteyne, T., Vilajosana, X., Kerkez, B., Chraim, F., 488 Weekly, K., Wang, Q., Glaser, S., and K. Pister, "OpenWSN: 489 a Standards-Based Low-Power Wireless Development 490 Environment", Transactions on Emerging Telecommunications 491 Technologies , August 2012. 493 Appendix A. [TEMPORARY] Changelog 495 o draft-ietf-6tisch-6top-sf0-02 497 * Editorial changes (figs, typos, ...) 498 o draft-ietf-6tisch-6top-sf0-03 500 * Fixed typos 501 * Removed references to "effectively used cells" 502 * Changed Cell Estimation Algorithm to the third proposed 503 alternative on IETF97 504 * Forced cell deletion becomes implementation specific 505 * Added PDR calculation formula 506 * Added PDR_THRESHOLD as implementation specific value 508 Authors' Addresses 510 Diego Dujovne (editor) 511 Universidad Diego Portales 512 Escuela de Informatica y Telecomunicaciones 513 Av. Ejercito 441 514 Santiago, Region Metropolitana 515 Chile 517 Phone: +56 (2) 676-8121 518 Email: diego.dujovne@mail.udp.cl 520 Luigi Alfredo Grieco 521 Politecnico di Bari 522 Department of Electrical and Information Engineering 523 Via Orabona 4 524 Bari 70125 525 Italy 527 Phone: 00390805963911 528 Email: a.grieco@poliba.it 530 Maria Rita Palattella 531 Luxembourg Institute of Science and Technology (LIST) 532 Department 'Environmental Research and Innovation' (ERIN) 533 41, rue du Brill 534 Belvaux L-4422 535 Grand-duchy of Luxembourg 537 Phone: +352 275 888-5055 538 Email: mariarita.palattella@list.lu 540 Nicola Accettura 541 LAAS-CNRS 542 7, avenue du Colonel Roche 543 Toulouse 31400 544 France 546 Phone: +33 5 61 33 69 76 547 Email: nicola.accettura@laas.fr