6TiSCH                                                   D. Dujovne, Ed.
Internet-Draft                                Universidad Diego Portales
Intended status: Informational Standards Track                              LA. Grieco
Expires: January 9, May 4, 2017                                 Politecnico di Bari
                                                          MR. Palattella
                                                University of
                   Luxembourg Institute of Science and Technology (LIST)
                                                            N. Accettura
                                       University of California Berkeley
                                                            July 8,
                                                        October 31, 2016

               6TiSCH 6top Scheduling Function Zero (SF0)


   This document defines a 6top Scheduling Function called "Scheduling
   Function Zero" (SF0).  SF0 dynamically adapts the number of reserved allocated
   cells between neighbor nodes, based on the amount of currently
   bandwidth cells and the neighbour 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.  Some basic rules for deciding when to add/
   delete  This function selects
   the candidate cells and for selecting from the schedule, defines which cells to will be
   added/deleted within and triggers the schedule are also provided. allocation/deallocation process.

Requirements Language

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "OPTIONAL" in this document are to be interpreted as described in RFC
   2119 [RFC2119].

Status of This Memo

   This Internet-Draft is submitted in full conformance with the
   provisions of BCP 78 and BCP 79.

   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 January 9, May 4, 2017.

Copyright Notice

   Copyright (c) 2016 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
   carefully, as they describe your rights and restrictions with respect
   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.  Introduction  TEMPORARY EDITORIAL NOTES . . . . . . . . . . . . . . . . . .   3
   2.  Introduction  . . . . . . . . .   2
   2.  Scheduling Function Identifier . . . . . . . . . . . . . . .   3
   3.  Rules for Adding/Deleting Cells  Scheduling Function Identifier  . . . . . . . . . . . . . . .   3
     3.1.   4
   4.  SF0 Triggering Events . . . . . . . . . . . . . . . . . .   3
     3.2. . .   4
   5.  SF0 Bandwidth Cell Estimation Algorithm . . . . . . . . . . .   3
     3.3. . . . . .   5
   6.  SF0 Allocation Policy . . . . . . . . . . . . . . . . . .   4
   4. . .   5
   7.  Rules for CellList  . . . . . . . . . . . . . . . . . . . . .   5
   5.   6
   8.  6P Timeout Value  . . . . . . . . . . . . . . . . . . . . . .   6
   6.   7
   9.  Meaning of Metadata Information . . . . . . . . . . . . . . .   6
   7.   7
   10. Node Behavior at Boot . . . . . . . . . . . . . . . . . . . .   6
   8.   7
   11. Relocating Cells  . . . . . . . . . . . . . . . . . . . . . .   6
   9.   7
   12. Forced Cell Deletion Policy . . . . . . . . . . . . . . . . .   7
   10.   8
   13. 6P Error Handling . . . . . . . . . . . . . . . . . . . . . .   7
   11.   8
   14. Examples  . . . . . . . . . . . . . . . . . . . . . . . . . .   7
   12.   8
   15. Implementation Status . . . . . . . . . . . . . . . . . . . .   7
   13.   8
   16. Security Considerations . . . . . . . . . . . . . . . . . . .   8
   14.   9
   17. IANA Considerations . . . . . . . . . . . . . . . . . . . . .   8
   15.   9
   18. 6P Compliance . . . . . . . . . . . . . . . . . . . . . . . .   9
   19. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . .   8
   16.  10
   20. References  . . . . . . . . . . . . . . . . . . . . . . . . .   8
     16.1.  10
     20.1.  Normative References . . . . . . . . . . . . . . . . . .   8
     16.2.  10
     20.2.  Informative References . . . . . . . . . . . . . . . . .   9  10
   Appendix A.  [TEMPORARY] Changelog  . . . . . . . . . . . . . . .  11
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   9  11


   This document defines the Scheduling Function for is an Internet Draft, so it is work-in-progress by
   nature.  It contains the 6top sublayer
   [I-D.wang-6tisch-6top-sublayer] called "Scheduling Function Zero"

   This document addresses following work-in-progress elements:

   o  "TODO" statements are elements which have not yet been written by
      the requirements authors for a scheduling function
   listed in [I-D.wang-6tisch-6top-sublayer], Section 4.2, and follows
   the recommended outline from Section 4.3.  This draft agrees some reason (lack of time, ongoing discussions
      with no clear consensus, etc).  The statement does indicate that
   terminology defined on [I-D.ietf-6tisch-terminology] and is designed
   within text will be written at some time.
   o  "TEMPORARY" appendices are there to capture current ongoing
      discussions, or the context of [RFC7554]

2.  Scheduling Function Identifier

   The Scheduling Function Identifier (SFID) changelog of SF0 the document.  These appendices
      will be removed in the final text.
   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 IANA_SFID_SF0.

3.  Rules 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 Adding/Deleting Cells 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.  From the allocated cells, a part of them can be under
   effective use by the neighbours, while the rest of cells are over-
   provisioned to detect an increase in cell usage without packet loss.
   The Scheduling Algorithm collects the cell allocation/deletion
   requests from the neighbors and the number of cells which are
   currently under usage.  First, a 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 experiment 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.

   To synthesize, a node running SF0 determines when to add/delete cells
   in a three-
   step three-step process:

   1.  It waits for a triggering event (Section 3.1). 4).
   2.  It applies the Bandwidth Cell Estimation Algorithm (BEA) (CEA) for a particular
       neighbor to determine how much bandwidth is many cells are required to that
       neighbor (Section 3.2). 5).
   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 3.3).

3.1. 6).

   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
   [TODO: update if needed] from [I-D.ietf-6tisch-6top-protocol], and
   follows the recommended outline listed in Section 5.3 [TODO: update
   if needed] 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.

4.  SF0 Triggering Events

   We RECOMMEND SF0 to be triggered at least by the following events:

   1.  If there is a change in the Current Outgoing Bandwidth Usage
       (COBU) current number of used cells
   2.  If there is any New Incoming Bandwidth Requirements from
       neighbour nodes (NIBR) a successful cell allocation/deallocation process
       with the neighbour.

   This allows SF0 to be triggered by any change in local outgoing
   bandwidth and/or locally generated or
   incoming bandwidth.  A relocation request from the
   neighbour is considered as an Incoming Bandwidth Request, given that
   it is expected to increase packet delivery rate on the relocated
   cells, thus increasing the required bandwidth. traffic.  The exact mechanism of when SF0 is triggered is


5.  SF0 Bandwidth Cell Estimation Algorithm

   The Bandwidth Cell Estimation Algorithm takes into account the sum of the new incoming bandwidth
   cell requirements from the neighbour nodes neighbor node and also the current outgoing bandwidth value.
   number of effectively used cells.  This allows the node algorithm to
   the total outgoing bandwidth requirement. a new number of cells to be allocated.  As a consequence,
   Bandwidth Cell Estimation Algorithm for SF0 follows the steps described

   1.  Collect the New Incoming Bandwidth Requirements new incoming cell requirements from neighbour
       nodes (NIBR) the neighbor
   2.  Obtain  Collect the Current Outgoing Bandwidth Usage (COBU) current number of effectively used cells
   3.  Calculate the New Outgoing Bandwidth (NOB) as: NOB=COBU+NIBR new number of cells to be allocated by adding the
       current number of effectively used cells and the new incoming
       cells requirement
   4.  Submit the request to the allocation policy as REQUIREDCELLS
   5.  Return to step 1 and wait for a triggering event.


   A new incoming cell requirement is the result of a successful
   allocation process from the neighbor.  TODO/REMARK: Add a number of
   cells to the required cells as OVERPROVISION to guarantee that the
   growth on the effectively used cells can be identified without packet
   loss.  This 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 of effectively used cells.

6.  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
   bandwidth cell

   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 Bandwidth 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' neighbours. 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.

      |   |   |   |   |   |   |   |   |   |
                      |     SF0THRESH     |
                      |                   |
      REQUIREDCELLS   |                   |
      +---+---+       |                   |       DELETE
      |   |   |       |                   |       ONE/MORE
      +---+---+       |                   |       CELLS
                      |                   |
          REQUIREDCELLS                   |
      +---+---+---+---+---+---+           |       DO
      |   |   |   |   |   |   |           |       NOTHING
      +---+---+---+---+---+---+           |
                      |                   |
                  REQUIREDCELLS           |
      +---+---+---+---+---+---+---+---+---+---+   ADD
      |   |   |   |   |   |   |   |   |   |   |   ONE/MORE
      +---+---+---+---+---+---+---+---+---+---+   CELLS

                    Figure 1: The SF0 Allocation Policy

   3.  If SCHEDULEDCELLS<=REQUIREDCELLS, add one or more cells.

   When SF0THRESH equals 0, any discrepancy between REQUIREDCELLS and
   SCHEDULEDCELLS triggers an action to add/delete cells.  Positive
   values of SF0THRESH reduce the number of 6P Transactions.

7.  Rules for CellList

   There are two methods to define the CellList: The Allocation Policy also translates Whitelist method,
   which fills the bandwidth requirement into
   cells according to their PDR.  For example, if a cell CellList with a 100% PDR
   is equivalent to 1Kbps, and the required bandwith is 8Kbps, then, the number of scheduled proposed cells will be 8.  However, if two of to the
   neighbour, and the Blacklist, which fills the CellList with the
   allocated cells have a 70% PDR, there number of scheduled cells will
   which cannot be 9.

4.  Rules for CellList used by the neighbour.  The rule to select the method
   is implementation-specific.  When issuing a 6top ADD Request, SF0
   executes the following sequence:

      Whitelist case:

         The Transaction Source node: Prepares the CellList field by
         selecting randomly the required cells, verifying that the slot
         offset and channel offset are not occupied and choose
         channelOffset randomly for each cell.
         The Transaction Destination node: Goes through the cells in the
         CellList in order, verifying whether there are no slotOffset
      Blacklist case:

         The Transaction Source node: Prepares the CellList field by
         building a list of currently scheduled cells into the CellList.
         The Transaction Destination node: Selects randomly the required
         cells from the unallocated cells on the schedule, verifying
         that the slot offset and channel offset are not occupied from
         the ones on the CellList.


8.  6P Timeout Value

   The general timeout equals the equivalent time of the number of slots
   until the next scheduled cell.

6.  TODO/REMARK: The exact calculation is
   currently under discussion on the Mailing List.

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
      BIT 15 [WBLIST] is used to indicate that the CellList provided is
      a Whitelist (value=0) or a Blacklist (value=1).

   TODO: length of the SlotFrame SHOULD be an integer multiple of the
   length of the minimal SlotFrame.


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 neighbour 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.  Given the TSCH
   parameters for the backoff mechanism, macMinBE and macMaxBE, and the
   length in seconds retries, as
   defined by Section 4.3.4 of the minimal Slotframe, SM, the [I-D.ietf-6tisch-6top-protocol].  TODO/
   REMARK: The initial timeout value is
   computed as: timeout = (2^(macMaxBE+1)-2^macMinBE) * SM

8. currently under discussion.

11.  Relocating Cells

   SF0 uses Packet Delivery Rate (PDR) statistics to monitor the
   currently allocated cells for cell re-allocation relocation (by changing their
   slotOffset and/or channelOffset) when it finds out that channelOffset).  When the PDR of one or more
   softcells is below 20% of the average PDR.

9. PDR of the rest of the
   scheduled cells, SF0 relocates the cell(s) to a number of available
   cells selected randomly.  REMARK: This criteria is currently under
   discussion; simulation/experimentation is required to either adjust
   the threshold or to change the process.

12.  Forced Cell Deletion Policy

   TODO: When all the cells are scheduled, we need a policy to free
   cells, for example, under alarm conditions or if a node dissappears disappears
   from the neighbour neighbor list.


13.  6P Error Handling

   A node implementing SF0 handles a 6P Response depending on the Return
   Code it contains:

      If the number of elements in the CellList is the number of cells
      specified in the NumCells field of the 6P ALL ADD Request, the
      operation is complete.  The node does not take further action.
      If the number of elements in the CellList is smaller (possibly 0)
      than the number of cells specified in the NumCells field of the 6P
      ADD Request, the neighbor has received the request, but less than
      NumCells of the cells in the CellList were.  In that case, the
      node MAY retry immediately with a different CellList if the amount
      of storage space permits, or build a new (random) CellList.
   RC_ERR_VER:  The node MUST NOT retry immediately.  The node MAY add
      the neighbor node on to a blacklist.  The node MAY retry to contact
      this neighbor later.
   RC_ERR_SFID:  The node MUST NOT retry immediately.  The node MAY add
      the neighbor node on to a blacklist.  The node MAY retry to contact
      this neighbor later.
   RC_ERR_GEN:  The node MUST issue a CLEAR command tot he neighbour.
   RC_ERR_BUSY:  Wait for a timeout and restart the scheduling process.
   RC_ERR_NORES:  Wait for a timeout and restart the scheduling process.
   RC_ERR_RESET:  Abort 6P Transaction
   RC_ERR:  Abort 6P Transaction.  The node MAY retry to contact this
      neighbor later.


14.  Examples



15.  Implementation Status

   This section records the status of known implementations of the
   protocol defined by this specification at the time of posting of this
   Internet-Draft, and is based on a proposal described in [RFC6982].
   The description of implementations in this section is intended to
   assist the IETF in its decision processes in progressing drafts to
   RFCs.  Please note that the listing of any individual implementation
   here does not imply endorsement by the IETF.  Furthermore, no effort
   has been spent to verify the information presented here that was
   supplied by IETF contributors.  This is not intended as, and must not
   be construed to be, a catalog of available implementations or their
   features.  Readers are advised to note that other implementations may

   According to [RFC6982], "this will allow reviewers and working groups
   to assign due consideration to documents that have the benefit of
   running code, which may serve as evidence of valuable experimentation
   and feedback that have made the implemented protocols more mature.
   It is up to the individual working groups to use this information as
   they see fit".

   OpenWSN:  This specification is implemented in the OpenWSN project
      [OpenWSN].  The authors of this document are collaborating with
      the OpenWSN community to gather feedback about the status and
      performance of the protocols described in this document.  Results
      from that discussion will appear in this section in future
      revision of this specification.


16.  Security Considerations



17.  IANA Considerations



18.  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
   o  MUST specify a value for the 6P Timeout, or a rule/equation to
      calculate it.
   o  MUST specify a meaning for the "Metadata" field in the 6P ADD
      Request.  OK
   o  MUST specify the behavior of a node when it boots.  OK
   o  MUST specify what to do after an error has occurred (either the
      node sent a 6P Response with an error code, or received one).  OK
   o  MUST specify the list of statistics to gather.  An example
      statistic if the number of transmitted frames to each neighbor.
      In case the SF requires no statistics to be gathered, the specific
      of the SF MUST explicitly state so.

   o  SHOULD clearly state the application domain the SF is created for.
   o  SHOULD contain examples which highlight normal and error
   o  SHOULD contain a list of current implementations, at least during
      the I-D state of the document, per [RFC6982].
   o  SHOULD contain a performance evaluation of the scheme, possibly
      through references to external documents.
   o  MAY redefine the format of the CellList? field.

19.  Acknowledgments

   Thanks to Kris Pister for his contribution in designing the default
   Bandwidth Estimation Algorithm.  Thanks to Qin Wang and Thomas
   Watteyne for their support in defining the interaction between SF0
   and the 6top sublayer.

   This work is partially supported by the Fondecyt 1121475 Project, the
   Inria-Chile "Network Design" group, and the IoT6 European Project
   (STREP) of the 7th Framework Program (Grant 288445).


20.  References


20.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,


20.2.  Informative References

   [RFC7554]  Watteyne, T., Ed., Palattella, M., and L. Grieco, "Using
              IEEE 802.15.4e Time-Slotted Channel Hopping (TSCH) in the
              Internet of Things (IoT): Problem Statement", RFC 7554,
              DOI 10.17487/RFC7554, May 2015,

   [RFC6982]  Sheffer, Y. and A. Farrel, "Improving Awareness of Running
              Code: The Implementation Status Section", RFC 6982,
              DOI 10.17487/RFC6982, July 2013,

              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-07 (work in
              progress), March 2016.


              Wang, Q. and X. Vilajosana, "6TiSCH Operation Sublayer
              (6top)", draft-wang-6tisch-6top-sublayer-04 "6top Protocol (6P)", draft-
              ietf-6tisch-6top-protocol-02 (work in progress), November 2015. July

   [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.

Appendix A.  [TEMPORARY] Changelog

   o  draft-ietf-6tisch-6top-sf0-02

      *  Editorial changes (figs, typos, ...)

Authors' Addresses

   Diego Dujovne (editor)
   Universidad Diego Portales
   Escuela de Informatica y Telecomunicaciones
   Av. Ejercito 441
   Santiago, Region Metropolitana

   Phone: +56 (2) 676-8121
   Email: diego.dujovne@mail.udp.cl

   Luigi Alfredo Grieco
   Politecnico di Bari
   Department of Electrical and Information Engineering
   Via Orabona 4
   Bari  70125

   Phone: 00390805963911
   Email: a.grieco@poliba.it

   Maria Rita Palattella
   University of
   Interdisciplinary Centre for Security, Reliability Institute of Science and Trust
   4, Technology (LIST)
   Department 'Environmental Research and Innovation' (ERIN)
   41, rue Alphonse Weicker du Brill
   Belvaux  L-4422
   Grand-duchy of Luxembourg  L-2721

   Phone: (+352) 46 66 44 5841 +352 275 888-5055
   Email: maria-rita.palattella@uni.lu mariarita.palattella@list.lu
   Nicola Accettura
   University of California Berkeley
   Berkeley Sensor & Actuator Center
   490 Cory Hall
   Berkeley, California  94720
   7, avenue du Colonel Roche
   Toulouse  31400

   Phone: +33 5 61 33 69 76
   Email: nicola.accettura@eecs.berkeley.edu nicola.accettura@laas.fr