--- 1/draft-ietf-6tisch-6top-sf0-04.txt 2017-07-02 23:13:30.399471662 -0700 +++ 2/draft-ietf-6tisch-6top-sf0-05.txt 2017-07-02 23:13:30.431472425 -0700 @@ -1,28 +1,28 @@ 6TiSCH D. Dujovne, Ed. Internet-Draft Universidad Diego Portales Intended status: Experimental LA. Grieco -Expires: October 30, 2017 Politecnico di Bari +Expires: January 3, 2018 Politecnico di Bari MR. Palattella Luxembourg Institute of Science and Technology (LIST) N. Accettura LAAS-CNRS - April 28, 2017 + July 2, 2017 6TiSCH 6top Scheduling Function Zero (SF0) - draft-ietf-6tisch-6top-sf0-04 + draft-ietf-6tisch-6top-sf0-05 Abstract This document defines a Scheduling Function called "Scheduling - Function Zero" (SF0). SF0 dynamically adapts the number of allocated + Function Zero" (SF0). SF0 dynamically adapts the number of scheduled cells between neighbor nodes, based on the amount of currently allocated cells and the neighbor nodes' cell requirements. Neighbor nodes negotiate in a distributed neighbor-to-neighbor basis the number of cell(s) to be added/deleted. SF0 uses the 6P signaling messages to add/delete cells in the schedule. This function selects the candidate cells from the schedule, defines which cells will be added/deleted and triggers the allocation/deallocation process. Requirements Language @@ -38,21 +38,21 @@ 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 http://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 October 30, 2017. + This Internet-Draft will expire on January 3, 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 (http://trustee.ietf.org/license-info) in effect on the date of publication of this document. Please review these documents @@ -60,43 +60,46 @@ 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. TEMPORARY EDITORIAL NOTES . . . . . . . . . . . . . . . . . . 3 2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3 3. Scheduling Function Identifier . . . . . . . . . . . . . . . 4 - 4. SF0 Triggering Events . . . . . . . . . . . . . . . . . . . . 4 - 5. SF0 Cell Estimation Algorithm . . . . . . . . . . . . . . . . 4 - 6. SF0 Allocation Policy . . . . . . . . . . . . . . . . . . . . 5 - 7. Rules for CellList . . . . . . . . . . . . . . . . . . . . . 6 - 8. 6P Timeout Value . . . . . . . . . . . . . . . . . . . . . . 7 - 9. Meaning of Metadata Information . . . . . . . . . . . . . . . 7 - 10. Node Behavior at Boot . . . . . . . . . . . . . . . . . . . . 7 - 11. Cell Type . . . . . . . . . . . . . . . . . . . . . . . . . . 7 - 12. SF0 Statistics . . . . . . . . . . . . . . . . . . . . . . . 8 - 13. Relocating Cells . . . . . . . . . . . . . . . . . . . . . . 8 - 14. Forced Cell Deletion Policy . . . . . . . . . . . . . . . . . 8 - 15. 6P Error Handling . . . . . . . . . . . . . . . . . . . . . . 8 - 16. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 9 - 17. Implementation Status . . . . . . . . . . . . . . . . . . . . 9 - 18. Security Considerations . . . . . . . . . . . . . . . . . . . 9 - 19. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9 - 20. 6P Compliance . . . . . . . . . . . . . . . . . . . . . . . . 10 - 21. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 10 - 22. References . . . . . . . . . . . . . . . . . . . . . . . . . 10 - 22.1. Normative References . . . . . . . . . . . . . . . . . . 10 - 22.2. Informative References . . . . . . . . . . . . . . . . . 11 - Appendix A. [TEMPORARY] Changelog . . . . . . . . . . . . . . . 11 - Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 12 + 4. Allocated and Used Cells . . . . . . . . . . . . . . . . . . 4 + 5. Overprovisioning . . . . . . . . . . . . . . . . . . . . . . 4 + 6. Scheduling Algorithm . . . . . . . . . . . . . . . . . . . . 4 + 6.1. SF0 Triggering Events . . . . . . . . . . . . . . . . . . 4 + 6.2. SF0 Cell Estimation Algorithm . . . . . . . . . . . . . . 4 + 6.3. SF0 Allocation Policy . . . . . . . . . . . . . . . . . . 6 + 7. Rules for CellList . . . . . . . . . . . . . . . . . . . . . 8 + 8. 6P Timeout Value . . . . . . . . . . . . . . . . . . . . . . 8 + 9. Meaning of Metadata Information . . . . . . . . . . . . . . . 9 + 10. Node Behavior at Boot . . . . . . . . . . . . . . . . . . . . 9 + 11. Cell Type . . . . . . . . . . . . . . . . . . . . . . . . . . 9 + 12. SF0 Statistics . . . . . . . . . . . . . . . . . . . . . . . 9 + 13. Relocating Cells . . . . . . . . . . . . . . . . . . . . . . 9 + 14. Forced Cell Deletion Policy . . . . . . . . . . . . . . . . . 10 + 15. 6P Error Handling . . . . . . . . . . . . . . . . . . . . . . 10 + 16. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 10 + 17. Implementation Status . . . . . . . . . . . . . . . . . . . . 10 + 18. Security Considerations . . . . . . . . . . . . . . . . . . . 11 + 19. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 11 + 20. 6P Compliance . . . . . . . . . . . . . . . . . . . . . . . . 11 + 21. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . 12 + 22. References . . . . . . . . . . . . . . . . . . . . . . . . . 12 + 22.1. Normative References . . . . . . . . . . . . . . . . . . 12 + 22.2. Informative References . . . . . . . . . . . . . . . . . 12 + Appendix A. [TEMPORARY] Changelog . . . . . . . . . . . . . . . 13 + Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 13 1. TEMPORARY EDITORIAL NOTES This document is an Internet Draft, so it is work-in-progress by nature. It contains the following work-in-progress elements: o "TODO" statements are elements which have not yet been written by the authors for some reason (lack of time, ongoing discussions with no clear consensus, etc). The statement does indicate that the text will be written at some time. @@ -106,134 +109,170 @@ o "IANA_" identifiers are placeholders for numbers assigned by IANA. These placeholders are to be replaced by the actual values they represent after their assignment by IANA. o The string "REMARK" is put before a remark (questions, suggestion, etc) from an author, editor of contributor. These are on-going discussions at the time to writing, NOT part of the final text. o This section will be removed in the final text. 2. Introduction - This document defines a minimal Scheduling Function for the 6top - sublayer [I-D.ietf-6tisch-6top-protocol], called "Scheduling Function - Zero" (SF0). SF0 is designed to offer the minimal set of - functionalities to be usable in a wide range of applications. SF0 - defines two algorithms: The Scheduling Algorithm defines the number - of cells to allocate/delete between two neighbours and the relocation - algorithm defines when to relocate a cell. - - The Scheduling Algorithm: A number of TX and/or RX cells must be - allocated between neighbor nodes in order to enable data transmission - among them. A portion of these allocated cells will be utilized by - neighbors, while the remaining cells can be over-provisioned to - handle unanticipated increases in cell requirements. The Scheduling - Algorithm collects the cell allocation/deletion requests from the - neighbors and the number of cells which are currently under usage. - First, the Cell Estimation Algotithm calculates the number of - required cells by adding the collected values and second, the - calculated value is given to the Allocation Policy, which provides - stability by adding hystheresis and overprovisioning by deciding when - to schedule the new number of cells, according to a threshold. In - order to reduce consumption, this algorithm is triggered only when - there is a change on the number of effectively used cells or if there - is a change on the number of requested cells from a particular node. - - The Relocation Algorithm: Allocated cells may experience packet loss - from different sources, such as noise, interference or cell collision - (after the same cell is allocated by other nodes in range on the - network). In order to avoid this problem, Packet Delivery Rate (PDR) - is monitored periodically for each allocated cell. A relocation is - triggered when the PDR value drops below a certain threshold, - compared to the average PDR of the rest of allocated cells. The - destination location on the schedule is defined randomly. + This document defines a minimal Scheduling Function using the 6P + protocol [I-D.ietf-6tisch-6top-protocol], called "Scheduling Function + Zero" (SF0). SF0 is designed to offer a number of functionalities to + be usable in a wide range of applications. SF0 defines two + algorithms: The Scheduling Algorithm defines the number of cells to + allocate/delete between two neighbours and the Relocation Algorithm + defines when to relocate a cell. To synthesize, a node running SF0 determines when to add/delete cells in a three-step process: - 1. It waits for a triggering event (Section 4). + 1. It waits for a triggering event (Section 6.1). 2. It applies the Cell Estimation Algorithm (CEA) for a particular neighbor to determine how many cells are required to that - neighbor (Section 5). + neighbor (Section 6.2). 3. It applies the Allocation Policy to compare the number of required cells to the number of already scheduled cells, and - determines the number of cells to add/delete (Section 6). + determines the number of cells to add/delete (Section 6.3). We expect additional SFs, offering more functionalities for a more specific use case, to be defined in future documents. SF0 addresses the requirements for a scheduling function listed in Section 5.2 from [I-D.ietf-6tisch-6top-protocol], and follows the recommended outline listed in Section 5.3 of [I-D.ietf-6tisch-6top-protocol]. This document follows the terminology defined in [I-D.ietf-6tisch-terminology]. 3. Scheduling Function Identifier - The Scheduling Function Identifier (SFID) of SF0 is IANA_SFID_SF0. + The Scheduling Function Identifier (SFID) of SF0 is + IANA_6TISCH_SFID_SF0. -4. SF0 Triggering Events +4. Allocated and Used Cells - We RECOMMEND SF0 to be triggered at least by the following events: + An allocated cell is assigned as a TX, RX or Shared cell on the + schedule, as a reserved resource. This reservation does not imply + that a packet will be transmitted during the scheduled cell time. A + used cell is a cell where a packet has been transmitted during the + scheduled cell time on the last slotframe. - 1. If there is a change in the current number of required cells - 2. If there is a successful cell allocation/deallocation process - with the neighbour. +5. Overprovisioning - This allows SF0 to be triggered by any change in locally generated or - incoming traffic. The exact mechanism of when SF0 is triggered is + Overprovisioning is the action and effect of increasing a value + representing an amount of resources. In the case of SF0, + overprovisioning is done as a provision to reduce traffic variability + effects on packet loss, to the expense of artificially allocating a + number of cells. + +6. Scheduling Algorithm + + A number of TX cells must be allocated between neighbor nodes in + order to enable data transmission among them. A portion of these + allocated cells will be used by neighbors, while the remaining cells + can be over-provisioned to handle unanticipated increases in cell + requirements. The Scheduling Algorithm collects the cell allocation/ + deallocation requests from the neighbors and the number of cells + which are currently under usage. First, the Cell Estimation + Algorithm calculates the number of required cells and second, the + calculated number is transferred to the Allocation Policy. In order + to reduce consumption, this algorithm is triggered only when there is + a change on the number of used cells from a particular node. + +6.1. SF0 Triggering Events + + We RECOMMEND SF0 to be triggered at by the following event: If there + is a change on the number of used cells towards any of the + neighbours. The exact mechanism of when SF0 is triggered is implementation-specific. -5. SF0 Cell Estimation Algorithm +6.2. SF0 Cell Estimation Algorithm - The Cell Estimation Algorithm takes into account the new incoming - cell requirements from the neighbor node and the current outgoing - number of used cells. This allows the algorithm to estimate a new - number of cells to be allocated. As a consequence, the Cell - Estimation Algorithm for SF0 follows the steps described below: + The Cell Estimation Algorithm takes into account the number of + current used cells to the neighbour. This allows the algorithm to + estimate a new number of cells to be scheduled to the neighbour. As + a consequence, the Cell Estimation Algorithm for SF0 follows the + steps described below: - 1. Collect the current number of used cells - 2. Calculate the new number of cells to be allocated by adding the - current number of used cells plus an OVERPROVISION number of - cells - 3. Submit the request to the allocation policy as REQUIREDCELLS + 1. Collect the current number of used cells to the neighbour + 2. Calculate the new number of cells to be scheduled to the + neighbour by adding the current number of used cells plus an + OVERPROVISION number of cells + 3. Transfer the request to the allocation policy as REQUIREDCELLS 4. Return to step 1 and wait for a triggering event. - The OVERPROVISION parameter is a percentage of the currently - allocated cells which is added to the used cells to guarantee that - the growth on the number of used cells can be detected without packet - loss. This percentage value is implementation-specific. A value of - OVERPROVISION equal to zero leads to queue growth and possible packet - loss, since there are no overprovisioned cells to detect if there is - a growth on the number of used cells. + The Cell Estimation Algorithm is depicted on figure Figure 1. The + OVERPROVISION parameter is calculated as a percentage of the number + of currently scheduled cells to the neighbour. OVERPROVISION is + added to the amount of used cells to the neighbour to reduce the + probability of packet loss given a sudden growth on the number of + used cells to the neighbour. The OVERPROVISION value is + implementation-specific. A value of OVERPROVISION equal to zero + leads to queue growth and possible packet loss: In this case, there + are no overprovisioned cells where a sudden growth on the number of + cells can absorbed and detected. -6. SF0 Allocation Policy + +-------------------+ + | Triggering | + | Event |<-----+ + | | | + +-------------------+ | + | | + V | + +-------------------+ | + | Collect number of | | + | used cells | | + +-------------------+ | + | | + V | + +-------------------+ | + | used cells | | + | + | | + | OVERPROVISION | | + | = | | + | REQUIREDCELLS | | + +-------------------+ | + | | + V | + +-------------------+ | + | REQUIREDCELLS | | + | | | | + | V |------+ + | Allocation | + | Policy | + +-------------------+ + + Figure 1: The SF0 Estimation Algorithm + +6.3. SF0 Allocation Policy The "Allocation Policy" is the set of rules used by SF0 to decide when to add/delete cells to a particular neighbor to satisfy the cell requirements. SF0 uses the following parameters: SCHEDULEDCELLS: The number of cells scheduled from the current node to a particular neighbor. REQUIREDCELLS: The number of cells calculated by the Cell Estimation Algorithm from the current node to that neighbor. SF0THRESH: Threshold parameter introducing cell over-provisioning in the allocation policy. It is a non-negative value expressed as number of cells. The definition of this value is implementation- specific. A setting of SF0THRESH>0 will cause the node to allocate at least SF0THRESH cells to each of its' neighbors. The SF0 allocation policy compares REQUIREDCELLS with SCHEDULEDCELLS and decides to add/delete cells taking into account SF0THRESH. This - is illustrated in Figure 1. The number of cells to be scheduled/ - deleted is out of the scope of this document and it is - implementation-dependent. + is illustrated in Figure 2. The number of cells to be added/deleted + is out of the scope of this document and it is implementation- + dependent. SCHEDULEDCELLS <---------------------------------> +---+---+---+---+---+---+---+---+---+ | | | | | | | | | | +---+---+---+---+---+---+---+---+---+ |<----------------->| | SF0THRESH | | | REQUIREDCELLS | | @@ -244,106 +283,127 @@ REQUIREDCELLS | +---+---+---+---+---+---+ | DO | | | | | | | | NOTHING +---+---+---+---+---+---+ | | | REQUIREDCELLS | +---+---+---+---+---+---+---+---+---+---+ ADD | | | | | | | | | | | ONE/MORE +---+---+---+---+---+---+---+---+---+---+ CELLS - Figure 1: The SF0 Allocation Policy + Figure 2: The SF0 Allocation Policy 1. If REQUIREDCELLS<(SCHEDULEDCELLS-SF0THRESH), delete one or more cells. 2. If (SCHEDULEDCELLS-SF0THRESH)<=REQUIREDCELLS<=SCHEDULEDCELLS, do nothing. - 3. If SCHEDULEDCELLS<=REQUIREDCELLS, add one or more cells. + 3. If SCHEDULEDCELLS|B|-----Second Exchange----->|A| + |Complete transaction------------------------------------------| + + Figure 3: Example Transaction where the timeout does not expire + + |Timeout Value----------------------------------------------| + |A|------First Exchange-------->|B|-----Second Exchange----->|A| + |Non-Complete transaction--------------------------------------| + + Figure 4: Example Transaction where the timeout expires 9. Meaning of Metadata Information The Metadata 16-bit field is used as follows: BITS 0-7 [SLOTFRAME] are used to identify the slotframe number - BITS 8-14 are RESERVED + BITS 8-14 [TIMEOUT] represents the Timeout value BIT 15 [WBLIST] is used to indicate that the CellList provided is a Whitelist (value=0) or a Blacklist (value=1). 10. Node Behavior at Boot In order to define a known state after the node is restarted, a CLEAR command is issued to each of the neighbor nodes to enable a new - allocation process. The 6P Initial Timeout Value provided by SF0 - should allow for the maximum number of TSCH link-layer retries, as - defined by Section 4.3.4 of [I-D.ietf-6tisch-6top-protocol]. TODO/ - REMARK: The initial timeout is currently under discussion on the - Mailing List. + allocation process and at least a SF0THRESH number of cells MUST be + allocated to each of the neighbours. 11. Cell Type SF0 uses TX (Transmission) cell type only, thus defining celloptions as TX=0, RX=1 and S=0 according to section 4.2.6 of [I-D.ietf-6tisch-6top-protocol]. 12. SF0 Statistics - Packet Delivery Rate (PDR) is calculated per cell, as the quotient of - the number of successfully delivered packets to 10, for the last 10 - packet transmission attempts, without counting retransmissions. + Packet Delivery Rate (PDR) is calculated per cell, as the percentage + of acknowledged packets, for the last 10 packet transmission + attempts. There is no retransmission policy on SF0. 13. Relocating Cells + Allocated cells may experience packet loss from different sources, + such as noise, interference or cell collision (after the same cell is + allocated by other nodes in range on the network). + SF0 uses Packet Delivery Rate (PDR) statistics to monitor the currently allocated cells for cell relocation (by changing their slotOffset and/or channelOffset). When the PDR of one or more - softcells is below PDR_THRESHOLD, defined as a percentage of the - average of the PDR of the rest of the scheduled cells, SF0 relocates - each of the cell(s) to a number of available cells selected randomly. - PDR_THRESHOLD is out of the scope of this document and it is - implementation-dependent. + softcells is below PDR_THRESHOLD, SF0 relocates each of the cell(s) + to a number of available cells selected randomly. PDR_THRESHOLD is + out of the scope of this document and it is implementation-dependent. 14. Forced Cell Deletion Policy When all the cells are scheduled, we need a policy to free cells, for example, under alarm conditions or if a node disappears from the neighbor list. The action to follow this condition is out of scope of this document and it is implementation-dependent. 15. 6P Error Handling @@ -407,21 +466,21 @@ performance of the protocols described in this document. Results from that discussion will appear in this section in future revision of this specification. 18. Security Considerations TODO 19. IANA Considerations - o IANA_SFID_SF0 + o IANA_6TiSCH_SFID_SF0 20. 6P Compliance o MUST specify an identifier for that SF. OK o MUST specify the rule for a node to decide when to add/delete one or more cells to a neighbor. OK o MUST specify the rule for a Transaction source to select cells to add to the CellList field in the 6P ADD Request. OK o MUST specify the rule for a Transaction destination to select cells from CellList to add to its schedule. OK @@ -461,42 +521,42 @@ 22.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", BCP 14, RFC 2119, DOI 10.17487/RFC2119, March 1997, . 22.2. Informative References - [RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running - Code: The Implementation Status Section", RFC 6982, - DOI 10.17487/RFC6982, July 2013, - . + [I-D.ietf-6tisch-6top-protocol] + Wang, Q., Vilajosana, X., and T. Watteyne, "6top Protocol + (6P)", draft-ietf-6tisch-6top-protocol-07 (work in + progress), June 2017. [I-D.ietf-6tisch-terminology] Palattella, M., Thubert, P., Watteyne, T., and Q. Wang, "Terminology in IPv6 over the TSCH mode of IEEE - 802.15.4e", draft-ietf-6tisch-terminology-08 (work in - progress), December 2016. - - [I-D.ietf-6tisch-6top-protocol] - Wang, Q., Vilajosana, X., and T. Watteyne, "6top Protocol - (6P)", draft-ietf-6tisch-6top-protocol-04 (work in - progress), March 2017. + 802.15.4e", draft-ietf-6tisch-terminology-09 (work in + progress), June 2017. [OpenWSN] Watteyne, T., Vilajosana, X., Kerkez, B., Chraim, F., Weekly, K., Wang, Q., Glaser, S., and K. Pister, "OpenWSN: a Standards-Based Low-Power Wireless Development Environment", Transactions on Emerging Telecommunications Technologies , August 2012. + [RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running + Code: The Implementation Status Section", RFC 6982, + DOI 10.17487/RFC6982, July 2013, + . + Appendix A. [TEMPORARY] Changelog o draft-ietf-6tisch-6top-sf0-02 * Editorial changes (figs, typos, ...) o draft-ietf-6tisch-6top-sf0-03 * Fixed typos * Removed references to "effectively used cells" * Changed Cell Estimation Algorithm to the third proposed