Internet DRAFT - draft-dujovne-6tisch-6top-sf0

draft-dujovne-6tisch-6top-sf0







6TiSCH                                                   D. Dujovne, Ed.
Internet-Draft                                Universidad Diego Portales
Intended status: Informational                                LA. Grieco
Expires: September 22, 2016                          Politecnico di Bari
                                                          MR. Palattella
                                                University of Luxembourg
                                                            N. Accettura
                                       University of California Berkeley
                                                          March 21, 2016


               6TiSCH 6top Scheduling Function Zero (SF0)
                    draft-dujovne-6tisch-6top-sf0-01

Abstract

   This document defines a 6top Scheduling Function called "Scheduling
   Function Zero" (SF0).  SF0 dynamically adapts the number of reserved
   cells between neighbor nodes, based on the currently allocated
   bandwidth and the neighbour nodes' requirements.  Neighbor nodes
   negotiate in a distributed neighbor-to-neighbor basis the 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 cells and for selecting the cells to be added/deleted within
   the schedule are also provided.

Requirements Language

   The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
   "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."




Dujovne, et al.        Expires September 22, 2016               [Page 1]

Internet-Draft               6tisch-6top-sf0                  March 2016


   This Internet-Draft will expire on September 22, 2016.

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  . . . . . . . . . . . . . . . . . . . . . . . .   2
   2.  Scheduling Function Identifier  . . . . . . . . . . . . . . .   3
   3.  Rules for Adding/Deleting Cells . . . . . . . . . . . . . . .   3
     3.1.  SF0 Triggering Events . . . . . . . . . . . . . . . . . .   3
     3.2.  SF0 Bandwidth Estimation Algorithm  . . . . . . . . . . .   3
     3.3.  SF0 Allocation Policy . . . . . . . . . . . . . . . . . .   4
   4.  Rules for CellList  . . . . . . . . . . . . . . . . . . . . .   5
   5.  6P Timeout Value  . . . . . . . . . . . . . . . . . . . . . .   6
   6.  Meaning of Metadata Information . . . . . . . . . . . . . . .   6
   7.  Node Behavior at Boot . . . . . . . . . . . . . . . . . . . .   6
   8.  Relocating Cells  . . . . . . . . . . . . . . . . . . . . . .   6
   9.  Forced Cell Deletion Policy . . . . . . . . . . . . . . . . .   7
   10. 6P Error Handling . . . . . . . . . . . . . . . . . . . . . .   7
   11. Examples  . . . . . . . . . . . . . . . . . . . . . . . . . .   7
   12. Implementation Status . . . . . . . . . . . . . . . . . . . .   7
   13. Security Considerations . . . . . . . . . . . . . . . . . . .   8
   14. IANA Considerations . . . . . . . . . . . . . . . . . . . . .   8
   15. Acknowledgments . . . . . . . . . . . . . . . . . . . . . . .   8
   16. References  . . . . . . . . . . . . . . . . . . . . . . . . .   8
     16.1.  Normative References . . . . . . . . . . . . . . . . . .   8
     16.2.  Informative References . . . . . . . . . . . . . . . . .   9
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   9

1.  Introduction

   This document defines the Scheduling Function for the 6top sublayer
   [I-D.wang-6tisch-6top-sublayer] called "Scheduling Function Zero"
   (SF0).




Dujovne, et al.        Expires September 22, 2016               [Page 2]

Internet-Draft               6tisch-6top-sf0                  March 2016


   This document addresses the requirements for a scheduling function
   listed in [I-D.wang-6tisch-6top-sublayer], Section 4.2, and follows
   the recommended outline from Section 4.3.

2.  Scheduling Function Identifier

   The Scheduling Function Identifier (SFID) of SF0 is IANA_SFID_SF0.

3.  Rules for Adding/Deleting Cells

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

   1.  It waits for a triggering event (Section 3.1).
   2.  It applies the Bandwidth Estimation Algorithm (BEA) for a
       particular neighbor to determine how much bandwidth is required
       to that neighbor (Section 3.2).
   3.  It applies the Allocation Policy to compare the number of
       required cells to the number of already scheduled cells, and
       determine the number of cells to add/delete (Section 3.3).

3.1.  SF0 Triggering Events

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

   1.  If the Remaining Available Bandwidth (RAB) is less than the
       Minimum Remaining Bandwidth (MRB)
   2.  If there is any New Incoming Bandwidth Requirements from
       neighbour nodes (NIBR)

   This allows SF0 to be triggered by any change in local node bandwidth
   and/or incoming bandwidth.  The exact mechanism of when SF0 is
   triggered is implementation-specific.

3.2.  SF0 Bandwidth Estimation Algorithm

   The Bandwidth Estimation Algorithm takes into account the sum of the
   incoming bandwidth requirements from the neighbour nodes and the used
   outgoing bandwidth.  This allows the node to estimate the total
   outgoing bandwidth requirement.  As a consequence, the Bandwidth
   Estimation Algorithm for SF0 follows the steps described below:

   1.  Collect the New Incoming Bandwidth Requirements from neighbour
       nodes (NIBR)
   2.  Obtain the Current Outgoing Bandwidth Usage (COBU)
   3.  Obtain the number of Current Scheduled Bandwidth (CSB)
   4.  Calculate the New Outgoing Bandwidth (NOB) as: NOB=COBU+NIBR
   5.  Calculate the Remaining Available Bandwidth (RAB) as RAB=CSB-NOB



Dujovne, et al.        Expires September 22, 2016               [Page 3]

Internet-Draft               6tisch-6top-sf0                  March 2016


   6.  If the RAB is less than the Minimum Remaining Bandwidth (MRB),
       Add MRB to the NOB: NOB=NOB+MRB
   7.  Submit the request to the allocation policy
   8.  Return to step 1 and wait for a triggering event.

3.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
   bandwidth 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 Bandwidth
      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; however, it is RECOMMENDED a SF0THRESH value of 3 cells.
      A setting of SF0THRESH>0 will cause the node to allocate at least
      SF0THRESH cells to each of its' neighbours.

   The SF0 allocation policy compares REQUIREDCELLS with SCHEDULEDCELLS
   and decides to add/delete cells taking into account SF0THRESH.  This
   is illustrated in Figure 1.
























Dujovne, et al.        Expires September 22, 2016               [Page 4]

Internet-Draft               6tisch-6top-sf0                  March 2016


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

                    Figure 1: 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.

   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.

   The Allocation Policy also translates the bandwidth requirement into
   cells according to their PDR.  For example, if a cell with a 100% PDR
   is equivalent to 1Kbps, and the required bandwith is 8Kbps, then, the
   number of scheduled cells will be 8.  However, if two of the
   allocated cells have a 70% PDR, there number of scheduled cells will
   be 9.

4.  Rules for CellList

   When issuing a 6top ADD Request, SF0 executes the following sequence:

      Whitelist case:




Dujovne, et al.        Expires September 22, 2016               [Page 5]

Internet-Draft               6tisch-6top-sf0                  March 2016


         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.
         The Transaction Destination node: Goes through the cells in the
         CellList in order, verifying whether there are no slotOffset
         conflicts.
      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, verifying that the slot offset and channel offset are
         not occupied from the ones on the CellList.

5.  6P Timeout Value

   The 6P Timeout Value provided by SF0 allows the maximum number of
   TSCH link-layer retries.  Given the TSCH parameters for the backoff
   mechanism, macMinBE and macMaxBE, and the length in seconds of the
   minimal Slotframe, SM, the timeout value is computed as: timeout =
   (2^(macMaxBE+1)-2^macMinBE) * SM TODO: Change general timeout to a
   timeout adapted to the schedule: SF to use the number of slots until
   the next scheduled cell.

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

7.  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 nodes to enable a new
   allocation process.  TODO: Temporary cells from a pool for the join
   process.

8.  Relocating Cells

   SF0 uses Packet Delivery Rate (PDR) statistics to monitor the
   currently allocated cells for cell re-allocation (by changing their




Dujovne, et al.        Expires September 22, 2016               [Page 6]

Internet-Draft               6tisch-6top-sf0                  March 2016


   slotOffset and/or channelOffset) when it finds out that the PDR of
   one or more softcells below 20% of the average PDR.

9.  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
   from the neighbour list.

10.  6P Error Handling

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

   RC_SUCCESS:
      If the number of elements in the CellList is the number of cells
      specified in the NumCells field of the 6P ALL 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
      ALL 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 a blacklist.  The node MAY retry to contact
      this neighbor later.
   RC_ERR_6OFID:  The node MUST NOT retry immediately.  The node MAY add
      the neighbor node on a blacklist.  The node MAY retry to contact
      this neighbor later.
   RC_ERR_NORESOURCES:  Wait for a timeout and restart the scheduling
      process.
   RC_ERR_BUSY:  Issue a RESET command.

11.  Examples

   TODO

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



Dujovne, et al.        Expires September 22, 2016               [Page 7]

Internet-Draft               6tisch-6top-sf0                  March 2016


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

   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.

13.  Security Considerations

   TODO

14.  IANA Considerations

   o  IANA_SFID_SF0

15.  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).

16.  References

16.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,
              <http://www.rfc-editor.org/info/rfc2119>.





Dujovne, et al.        Expires September 22, 2016               [Page 8]

Internet-Draft               6tisch-6top-sf0                  March 2016


   [IEEE802154e]
              IEEE standard for Information Technology, "IEEE std.
              802.15.4e, Part. 15.4: Low-Rate Wireless Personal Area
              Networks (LR-WPANs) Amendament 1: MAC sublayer", April
              2012.

   [IEEE802154]
              IEEE standard for Information Technology, "IEEE std.
              802.15.4, Part. 15.4: Wireless Medium Access Control (MAC)
              and Physical Layer (PHY) Specifications for Low-Rate
              Wireless Personal Area Networks", June 2011.

16.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,
              <http://www.rfc-editor.org/info/rfc7554>.

   [RFC6982]  Sheffer, Y. and A. Farrel, "Improving Awareness of Running
              Code: The Implementation Status Section", RFC 6982,
              DOI 10.17487/RFC6982, July 2013,
              <http://www.rfc-editor.org/info/rfc6982>.

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

   [I-D.wang-6tisch-6top-sublayer]
              Wang, Q. and X. Vilajosana, "6TiSCH Operation Sublayer
              (6top)", draft-wang-6tisch-6top-sublayer-04 (work in
              progress), November 2015.

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

Authors' Addresses








Dujovne, et al.        Expires September 22, 2016               [Page 9]

Internet-Draft               6tisch-6top-sf0                  March 2016


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

   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
   Italy

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


   Maria Rita Palattella
   University of Luxembourg
   Interdisciplinary Centre for Security, Reliability and Trust
   4, rue Alphonse Weicker
   Luxembourg  L-2721
   LUXEMBOURG

   Phone: (+352) 46 66 44 5841
   Email: maria-rita.palattella@uni.lu


   Nicola Accettura
   University of California Berkeley
   Berkeley Sensor & Actuator Center
   490 Cory Hall
   Berkeley, California  94720
   USA

   Email: nicola.accettura@eecs.berkeley.edu










Dujovne, et al.        Expires September 22, 2016              [Page 10]