6TiSCH                                                   D. Dujovne, Ed.
Internet-Draft                                Universidad Diego Portales
Intended status: Informational                                LA. Grieco
Expires: August 18, 2014                             Politecnico di Bari
                                                          MR. Palattella
                                                University of Luxembourg
                                                            N. Accettura
                                                     Politecnico di Bari
                                                       February 14, 2014

                      6TiSCH On-the-Fly Scheduling


   This document describes the environment, problem statement, and goals
   of the On-The-Fly (OTF) scheduling approach for the IEEE802.15.4e
   TSCH MAC protocol in the context of LLNs.  The purpose of OTF is to
   dynamically adapt the aggregate bandwidth, i.e., the number of
   reserved soft cells between neighbor nodes, based on the specific
   application constraints to be satisfied.  The soft cell and Bundle
   reservation with OTF is distributed: through the 6top interface,
   neighbor nodes negotiate the cell(s) to be (re)allocated/deleted,
   without intervention of a centralized entity.  This document aims at
   defining a module which uses the functionalities provided by the 6top
   sublayer to (i) extract statistics and (ii) determine when to reserve
   /delete soft cells in the schedule.  The exact reservation and
   deletion algorithm, and the number and type of statistics to be used
   in the algorithm are out of scope.  OTF deals only with the number of
   soft cells to be reserved/deleted; it is up to 6top to select the
   specific soft cells within the TSCH schedule.

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 August 18, 2014                [Page 1]

Internet-Draft              6tisch-on-the-fly              February 2014

   This Internet-Draft will expire on August 18, 2014.

Copyright Notice

   Copyright (c) 2014 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.  Allocation policy . . . . . . . . . . . . . . . . . . . . . .   3
   3.  Allocation methods  . . . . . . . . . . . . . . . . . . . . .   5
   4.  Input parameters: statistics and instant values . . . . . . .   6
   5.  bundle usage management in OTF: TODO  . . . . . . . . . . . .   6
     5.1.  Cell Reservation/Deletion . . . . . . . . . . . . . . . .   6
     5.2.  bundle Size Increase/Decrease . . . . . . . . . . . . . .   6
   6.  Schedule storage on OTF: TODO . . . . . . . . . . . . . . . .   6
   7.  Bandwidth Estimation Algorithms . . . . . . . . . . . . . . .   6
   8.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .   7
   9.  References  . . . . . . . . . . . . . . . . . . . . . . . . .   8
     9.1.  Informative References  . . . . . . . . . . . . . . . . .   8
     9.2.  External Informative References . . . . . . . . . . . . .   8
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   9

1.  Introduction

   The IEEE802.15.4e standard [IEEE802154e] was published in 2012 as an
   amendment to the Medium Access Control (MAC) protocol defined by the
   IEEE802.15.4-2011 [IEEE802154] standard.  The Timeslotted Channel
   Hopping (TSCH) mode of IEEE802.15.4e is the object of this document.

   On-The-Fly (OTF) scheduling is a distributed protocol in which a node
   negotiates the number of soft cells scheduled with its neighbors,
   without the intervention of a centralized entity (e.g., a PCE).  In
   particular, this document describes the OTF allocation policies and
   methods used for allocating single soft cell or group of them (i.e.
   bundle) between two neighbors.  It also proposes some potential
   algorithms for estimating the required bandwidth.  In this document,

Dujovne, et al.          Expires August 18, 2014                [Page 2]

Internet-Draft              6tisch-on-the-fly              February 2014

   internal interface used between OTF and the 6top sublayer
   ([I-D.wang-6tisch-6top]) is defined, with a particular focus on the
   functionalities.  Example functionalities are collecting and
   providing statistic information, or allocating/deleting cells and
   bundles.  To be extensible and applicable to different scenarios,
   this draft is a generic framework.  The exact algorithm and set of
   statistics used for estimating the requested bandwidth is out of
   scope.  This draft follows the terminology defined in
   [I-D.ietf-6tisch-terminology] and addresses the open issue related to
   the scheduling mechanisms raised in [I-D.ietf-6tisch-tsch].

2.  Allocation policy

   OTF is a distributed scheduling protocol which sends scheduling
   requests to the 6top sublayer.  OTF thereby dynamically increases/
   decreases the bandwidth allocated between neighbor nodes. 6top takes
   care of negociating the soft cells between neighbors.  Because OTF
   delegates the selection of the specific cells to 6top, OTF only
   supports soft cell reservation.  Therefore, the term "cell" is
   synonymous to "soft cell" in this document.

   OTF is prone to schedule collision.  Nodes might not be aware of the
   cells allocated by other pairs of neighbors nodes.  A collision
   occurs when the same cell is allocated by different pairs in the same
   interference space.  The 6top sublayer cannot differentiate
   collisions from other sources of packet loss.  The probability of
   having allocation collision may be kept low by grouping cells into
   chunks (see [I-D.ietf-6tisch-terminology] and
   [I-D.ietf-6tisch-architecture] for more details).  The use of chunks
   is outside the scope of this current version of the OTF draft.

   We call "allocation policy" the approach used by OTF for increasing
   or decreasing the bandwidth allocated between two nodes in order to
   satisfy the traffic requirements.  These requirements can be
   expressed in terms of throughput, latency or other constraints.

   OTF supports 3 different types of allocation policies: Post-
   allocation, Pre-allocation and Hybrid allocation.

   Post-allocation policy is based on a "recovery" approach following
   the increased/decreased need of bandwidth.  Upon reception of a
   bandwidth request, OTF sends soft cell allocation requests to the
   6top sublayer.  OTF has to estimate the number of cells to be
   allocated per each neighbor.  OTF keeps track of such information.
   If afterwards, it is possible to free some cells (due for instance to
   the reduction of traffic exchanged between two neighbors), OTF asks
   6top to de-allocate a given number of cells.  Once the cells have

Dujovne, et al.          Expires August 18, 2014                [Page 3]

Internet-Draft              6tisch-on-the-fly              February 2014

   been deleted and 6top has notified the event to OTF, the latter can
   update its internal cell allocation tables.

   Pre-allocation policy is based on a "provision" approach.  This
   implies that the reservation of groups of equivalents cells (i.e.,
   bundles), to a given couple of nodes, is done in advance.  When OTF
   sends a bundle allocation requests to 6top, it has to indicate the
   desired size of the bundle and the TrackID.  These are the only
   features that can be settled by OTF. 6top selects the soft cells
   belonging to the bundle.  Based on the network traffic condition
   (e.g. queue utilization), a number of cells within the bundle is used
   for communication.  In any case, allocated cells within a bundle are
   consecutive, starting from the first cell in the block.  The cells
   which are not currently used, are still reserved for that pair of
   nodes, for possible future use.

   OTF keeps track of the scheduled bundles, the bundle size, and the
   estimated number of allocated cells within a bundle.  Based on this
   information, upon reception of a bandwidth request, OTF may ask 6top
   to increase or decrease the bundle size.

   The post-allocation policy compared to the pre-allocation reduces the
   energy consumption, by allocating the exact number of soft cells when
   they are needed, but at the expense of increased cell allocation
   latency.  In fact, for each requested soft cell, the 6top layer has
   to negotiate the request with the 6top layer of the neighbor node.
   Such negotiation takes some time and induces communication overhead.

   The pre-allocation policy compared to the post-allocation reduces the
   cell allocation latency.  The soft cells within the bundle are over-
   provisioned, and a priori scheduled.  When needed, the 6top sublayer
   of the node can allocate them, without going through any negotiation
   phase with the 6top layer of the neighbor node.  Thus, the pre-
   allocation approach provides a low-delay response after a surge in
   bandwidth usage.  In fact, soft cells within a bundle are already
   scheduled and become immediately available, upon bandwidth request,
   without the need of a negotiation phase.  The use of bundles does
   force the receiver module of the node to be active during the whole
   length of the Bundle, thus implying increased power consumption.

   The hybrid allocation policy is a mix of the pre- and post-
   allocation policy.  It tries to take advantage of both the
   "provision" and "recovery" approaches.  Some bundles can be reserved
   in advance for a pair of nodes.  After receiving a bandwidth request,
   OTF can decide if asking to 6top for (new) soft cell allocation (as
   per post-allocation approach, implying a negotiation phase among the
   neighbor nodes), or for bundle allocation/resizing (as per pre-
   allocation approach).  In fact, tt is possible that more bandwidth is

Dujovne, et al.          Expires August 18, 2014                [Page 4]

Internet-Draft              6tisch-on-the-fly              February 2014

   needed, but there are still some cells within the bundle that have
   not been allocated yet, and that they can be used for fulfilling the
   request.  If all the cells within the bundle have already been
   allocated, OTF has to send a bundle size increase request to 6top
   (that still translates in soft cells allocation request).

3.  Allocation methods

   Beyond the allocation policies that describe the approach used by OTF
   for fulfilling the node bandwidth requests, the OTF framework also
   includes Allocation Methods that specify how OTF actually asks the
   6top sublayer to satisfy the aforementioned requests.  In other
   words, the allocation methods represent the mechanisms that are used
   by the allocation policies to pre- or post- allocate extra bandwidth.

   In detail, OTF includes two distinct allocation methods: soft cell
   and bundle allocation methods.  Each Allocation Policy can use either
   one or both allocation methods.  As specified in
   [I-D.wang-6tisch-6top], 6top provides a set of commands that allows
   to schedule/allocate/delete soft cells.  The same set of commands can
   be used for reserving bundles.

   With the soft cell allocation method, OTF asks 6top to reserve a
   single soft cell, for communicating with a specific neighbour node,
   on a given track.  The 6top layer allocates and maintains such cell.
   It has to be noticed that if a bundle (i.e., a group of cells) was
   already reserved between the same couple of nodes, on the same track,
   then, such soft cell allocation request translates into a bundle
   resize request.  In fact, the new allocated cell will increase the
   size of the already exsisting bundle.  In a similar way, when OTF
   realizes that there is a reduction of traffic exchanged between the
   two neighbors, it may asks 6top to delete a soft cell, in other
   words, to decrease the bundle size.  Instead, if no bundle with the
   same TrackID already existed, then the 6top soft cell create command
   will generate a new bundle of size 1, having the specified TrackID.

   With the bundle allocation method, OTF sends bundle allocation
   requests to 6top sublayer, specifying the bundle size (i.e., number
   of soft cells forming the bundle itself) and the TrackID of the track
   to which the cells belong.  By using the soft cells commands 6top
   generates the bundle.  In fact, the request of scheduling N soft cell
   is equivalent to asking for a bundle of size N. The cells within the
   bundle will be allocated by 6top afterwards, according to the nodes
   bandwith need.

Dujovne, et al.          Expires August 18, 2014                [Page 5]

Internet-Draft              6tisch-on-the-fly              February 2014

4.  Input parameters: statistics and instant values

   Short summary of a potential set of statistics and instant values
   that could be used as input parameters.  Direct interaction with

   List of parameters available from 6top: mainly statistics related to

   Method to configure 6top to provide historical values for each
   requested parameter

   Method to ask 6top for instant values for each requested parameter

   Method for asking for a list of parameters from 6top and thus, for
   checking if a parameter is available or not

5.  bundle usage management in OTF: TODO

   Methods that trigger the request of increasing/decreasing the bundle,
   and thus, adding/deleting cells

5.1.  Cell Reservation/Deletion

   The commands to reserve/delete soft cells.  Direct interaction with

5.2.  bundle Size Increase/Decrease

   The commands to increase/decrease the bundle size.  Direct
   interaction with 6top

6.  Schedule storage on OTF: TODO

   The description and access to the schedule storage on OTF

   The commands to retrieve bundle usage values and statistics from OTF
   (based on previous values obtained by 6top?)

7.  Bandwidth Estimation Algorithms

   OTF supports different bandwidth estimation algorithms that can be
   used by a node in a 6TiSCH network for checking the current traffic
   condition and thus the actual bandwidth usage.  By doing so, it is
   possible to adapt (increase or increase) the number of scheduled
   cells/bundles for a given pair of neighbors (e.g., parent node and
   its child), according to their needs.  OTF supports several bandwidth
   estimation algorithms numbered from 0 to 255 in the OTF

Dujovne, et al.          Expires August 18, 2014                [Page 6]

Internet-Draft              6tisch-on-the-fly              February 2014

   implementation.  The first algorithm (0) is reserved to the default
   algorithm that is described below.  By using SET and GET commands, it
   is possible, to set the specific algorithm to be used, and get
   information about which algorithm is actualy implemented.

   The default bandwidth estimation algorithm, running over a parent
   node, is articulated in the following steps:

   Step 1:  Collect the bandwidth requests from child nodes (incoming

   Step 2:  Collect the node bandwidth requirement from the application
         (self/local traffic).

   Step 3:  Collect the current outgoing scheduled bandwidth (outgoing

   Step 4:  If (outgoing < incoming + self) then SCHEDULE soft cells/
         bundles to satisfy bandwidth requirements.

   Step 5:  If (outgoing > incoming + self) then DELETE the soft cells
         that are not used.

   Step 6:  Loop to Step 1.

   Based on the allocation policy that is used, at Step 4 new soft cells
   will be scheduled, using the cell allocation method.  If there are
   free cells in the bundle that can satisfied the current bandwidth
   request, such cells will be allocated.  In the case of pre-allocation
   policy, it may happen that the number of allocated cells within the
   bundle is equal to the bundle size.  That is, all the cells within
   the bundle are currently used.  In this case, the node asks 6top for
   increasing the bundle size by using the bundle allocation method.
   When the hybrid allocation policy has been selected two options are
   available: (i) the bundle size is increased, and a number of cells
   larger than those currently needed, can be scheduled - according to
   post-allocation approach, or (ii) a number of soft cells equal
   exactly to those currently needed are scheduled, as per post-
   allocation approach.

8.  Acknowledgements

   Special thanks to Prof. Kris Pister for his valuable contribution in
   designing the default Bandwidth Estimation Algorithm, and to Qin Wang
   for her support in defining the interaction between OTF and 6top

Dujovne, et al.          Expires August 18, 2014                [Page 7]

Internet-Draft              6tisch-on-the-fly              February 2014

   Thanks to the Fondecyt 1121475 Project, to INRIA Chile "Network
   Design" group and to the IoT6 European Project (STREP) of the 7th
   Framework Program (Grant 288445).

9.  References

9.1.  Informative References

              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-01 (work in
              progress), February 2014.

              Thubert, P., Watteyne, T., and R. Assimiti, "An
              Architecture for IPv6 over the TSCH mode of IEEE
              802.15.4e", draft-ietf-6tisch-architecture-01 (work in
              progress), February 2014.

              Watteyne, T., Palattella, M., and L. Grieco, "Using
              IEEE802.15.4e TSCH in an LLN context: Overview, Problem
              Statement and Goals", draft-ietf-6tisch-tsch-00 (work in
              progress), November 2013.

              Wang, Q., Vilajosana, X., and T. Watteyne, "6TiSCH
              Operation Sublayer (6top)", draft-wang-6tisch-6top-00
              (work in progress), October 2013.

9.2.  External Informative References

              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

              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.

Dujovne, et al.          Expires August 18, 2014                [Page 8]

Internet-Draft              6tisch-on-the-fly              February 2014

              Palattella, MR., Accettura, N., Dohler, M., Grieco, LA.,
              and G. Boggia, "Traffic Aware Scheduling Algorithm for
              Multi-Hop IEEE 802.15.4e Networks", IEEE PIMRC 2012, Sept.
              2012, < http://www.cttc.es/resources/doc/

   [DeTAS]    Accettura, N., Palattella, MR., Boggia, G., Grieco, LA.,
              and M. Dohler, "Decentralized Traffic Aware Scheduling for
              Multi-hop Low Power Lossy Networks in the Internet of
              Things", IEEE WoWMoM 2013, June 2013.

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 Luxembourg
   Interdisciplinary Centre for Security, Reliability and Trust
   4, rue Alphonse Weicker
   Luxembourg  L-2721

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

Dujovne, et al.          Expires August 18, 2014                [Page 9]

Internet-Draft              6tisch-on-the-fly              February 2014

   Nicola Accettura
   Politecnico di Bari
   Electrical and Electronics Department
   Via Orabona 4
   Bari  70125

   Phone: +39 080 5963301
   Email: n.accettura@poliba.it

Dujovne, et al.          Expires August 18, 2014               [Page 10]