6TiSCH                                                   D. Dujovne, Ed.
Internet-Draft                                Universidad Diego Portales
Intended status: Informational                                LA. Grieco
Expires: June 8, 2014                                Politecnico di Bari
                                                          MR. Palattella
                                                University of Luxembourg
                                                            N. Accettura
                                                     Politecnico di Bari
                                                        December 5, 2013

                      6TiSCH On-the-Fly Scheduling


   This document describes the environment, problem statement, and goals
   of the On-The-Fly (OTF) scheduling for the IEEE802.15.4e TSCH MAC
   protocol in the context of LLNs.  The purpose of OTF is to
   dynamically adapt the number of reserved cells between neighbor nodes
   to satisfy different type of constraints, based on the specific
   application.  The cell reservation with OTF is distributed: neighbor
   nodes negotiate the cell(s) to be (re)allocated/deleted among them,
   without the intervention of a centralized entity.  This document aims
   to define a module which uses the functionalities provided by the
   6top sublayer to extract statistics and to reserve/delete cells in
   the schedule, leaving the reservation/deletion algorithm, and the
   number and type of statistics to be used in the algorithm itself,
   open.  OTF allows to reserve/delete either a single cell between a
   couple of nodes, or a set of them (i.e., a bundle) in the TSCH
   schedule.  Also, OTF allows to negotiate the aggregate bandwidth of a
   link without explicitly dealing with a reservation of a specific
   subset of cells.

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 June 8, 2014                  [Page 1]

Internet-Draft              6tisch-on-the-fly              December 2013

   This Internet-Draft will expire on June 8, 2014.

Copyright Notice

   Copyright (c) 2013 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
     2.1.  Allocation methods  . . . . . . . . . . . . . . . . . . .   3
   3.  Input parameters: statistics and instant values . . . . . . .   4
   4.  Bundle usage management in OTF  . . . . . . . . . . . . . . .   4
     4.1.  Cell Reservation/Deletion . . . . . . . . . . . . . . . .   4
     4.2.  Bundle Size Increase/Decrease . . . . . . . . . . . . . .   4
   5.  Schedule storage on OTF . . . . . . . . . . . . . . . . . . .   5
   6.  Algorithm selection . . . . . . . . . . . . . . . . . . . . .   5
   7.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .   5
   8.  References  . . . . . . . . . . . . . . . . . . . . . . . . .   5
     8.1.  Informative References  . . . . . . . . . . . . . . . . .   5
     8.2.  External Informative References . . . . . . . . . . . . .   6
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   6

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 intended to
   enable a node to define a common schedule with its neighbors without
   the intervention of a centralized entity.  In particular, this
   document describes the methods, flows and packets involved in this
   process by using the functionalities offered by the 6top sublayer, as
   defined in [I-D.wang-6tisch-6top].  In order to be extendible, and
   thus, applicable in different scenario, OTF has not been designed for

Dujovne, et al.           Expires June 8, 2014                  [Page 2]

Internet-Draft              6tisch-on-the-fly              December 2013

   working with a specific scheduling algorithm nor with a well-defined
   set of statistics.  It provides a general framework and a set of
   methods that can be used by different algorithms.  This document
   follows the terminology defined in
   [I-D.palattella-6tisch-terminology] and the mechanisms described on

2.  Allocation policy

   OTF Cell allocation is distributed.  All the allocation requests are
   sent to 6top, which will be in charge of granting the requested
   Softcells or Bundles.  Since the requests are satisfied on a peer to
   peer basis, without the participation of a PCE, this may generate
   Softcell reservation collisions between different pairs of nodes.
   Although distributed reservation reduces the latency, this can be
   done at the cost of increasing the Softcell allocation collision
   probability There are 3 types of allocation policies supported by
   OTF, namely Post-allocation, Pre-allocation and Hybrid allocation.

   On the Post-allocation policy, according to the current algorithm
   decision, OTF sends allocation requests to 6top for individual
   softcells.  After the softcells are granted, OTF keeps track of the
   number of cells allocated for each of the neighbours.  If the
   algorithm decides to free cells to any neighbour, a deallocation
   request is issued to 6top.  When the deallocation is confirmed, OTF
   updates the internal cell allocation tables.

   On the Pre-allocation policy, given a decision from the algorithm,
   OTF requests to 6top the allocation of a block of Softcells, called a
   Bundle.  When the allocation is granted, the algorithm decides which
   of the allocated cells inside the Bundle will be used for
   communication.  The remaining cells inside the Bundle will remain
   allocated but not used.  OTF keeps track of the allocated Bundles,
   and the number of used cells inside the Bundle.  Used cells inside a
   Bundle are consecutive starting from the first cell in the Bundle.
   When the algorihtm decides to enlarge or reduce the Bundle size, OTF
   forwards this request to 6top.

   On the Hybrid allocation policy, when the algorithm issues an
   allocation request for new cells, OTF must decide between allocating
   individual softcells, incrementing the number of used cells within a
   Bundle, or request to 6top to enlarge the Bundle if there were no
   free cells inside.  OTF keps track of the individual softcells, the
   allocated Bundles and the number of allocated cells inside the

2.1.  Allocation methods

Dujovne, et al.           Expires June 8, 2014                  [Page 3]

Internet-Draft              6tisch-on-the-fly              December 2013

   OTF uses two allocation methods: Bundle and Softcell.

   The Bundle allocation method requests to 6top a group of cells called
   a Bundle.  OTF manages internally the allocation of individual cells
   within the Bundle.  The goal of this allocation method is to provide
   a low-delay response after a surge in bandwidth usage, at the expense
   of energy consumption.  Once the Bundle is allocated, OTF may ask for
   sizing/re-sizing BW of a bundle, which implies softcells will be
   reserved.  For this purpose, OTF only calculates required Bandwidth,
   and 6top maps the BW to the number of soft cells according to some
   QoS setting, e.g. over-provision ratio, and then allocates and
   maintains them.

   The Softcell allocation method calculates the required Bandwidth and
   requests individual softcells to 6top.  The 6top layer allocates and
   maintains the individual softcells.  This method reduces energy
   consumption by allocating only the required bandwidth, to the expense
   of increasing cell allocation latency.

3.  Input parameters: statistics and instant values

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

   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 list of parameters from 6top and thus, for checking
   if a parameter is avaialble or not

4.  Bundle usage management in OTF

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

4.1.  Cell Reservation/Deletion

   The commands to reserve/delete Softcells. interaction with 6top

4.2.  Bundle Size Increase/Decrease

   The commands to increase/decrease the Bundle size. interaction with

Dujovne, et al.           Expires June 8, 2014                  [Page 4]

Internet-Draft              6tisch-on-the-fly              December 2013

5.  Schedule storage on OTF

   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?)

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

6.  Algorithm selection

   There may be multiple algorithms stored within OTF.  Here we describe
   how to select one of the stored algorithms.

7.  Acknowledgements

   Special thanks to for his review and valuable comments.  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).

8.  References

8.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-palattella-6tisch-terminology-00 (work
              in progress), October 2013.

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

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

Dujovne, et al.           Expires June 8, 2014                  [Page 5]

Internet-Draft              6tisch-on-the-fly              December 2013

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

              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/120531-submitted-

   [DeTAS]    Accettura, N., Palattella, , Boggia, G., Grieco, LA., and
              M. Dohler, "DeTAS: a Decentralized Traffic Aware
              Scheduling technique enabling IoT-compliant Multi-hop Low-
              power and Lossy Networks", IEEE WoWMoM on the Internet of
              Things 2013, June 2013, < http://www.gtti.it/GTTI13/papers

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

Dujovne, et al.           Expires June 8, 2014                  [Page 6]

Internet-Draft              6tisch-on-the-fly              December 2013

   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

   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 June 8, 2014                  [Page 7]