6TiSCH On-the-Fly Scheduling
draft-dujovne-6tisch-on-the-fly-01

6TiSCH                                                   D. Dujovne, Ed.
Internet-Draft                                Universidad Diego Portales
Intended status: Informational                                LA. Grieco
Expires: July 28, 2014                               Politecnico di Bari
                                                          MR. Palattella
                                                University of Luxembourg
                                                            N. Accettura
                                                     Politecnico di Bari
                                                        January 24, 2014

                      6TiSCH On-the-Fly Scheduling
                   draft-dujovne-6tisch-on-the-fly-01

Abstract

   This document describes the environment, problem statement, and goals
   of 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 Softcells between neighbor
   nodes to satisfy different types of constraints, based on the
   specific application.  The Softcell 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 Softcells 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 Softcell between a couple of nodes, or a
   Bundle in the TSCH schedule.  Also, OTF allows to negotiate the
   aggregate bandwidth without explicitly dealing with a reservation of
   a specific subset of Softcells.

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 July 28, 2014                 [Page 1]
Internet-Draft              6tisch-on-the-fly               January 2014

   This Internet-Draft will expire on July 28, 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  . . . . . . . . . . . . . . . . . . . . .   4
   4.  Input parameters: statistics and instant values . . . . . . .   4
   5.  Bundle usage management in OTF: TODO  . . . . . . . . . . . .   5
     5.1.  Cell Reservation/Deletion . . . . . . . . . . . . . . . .   5
     5.2.  Bundle Size Increase/Decrease . . . . . . . . . . . . . .   5
   6.  Schedule storage on OTF: TODO . . . . . . . . . . . . . . . .   5
   7.  Scheduling Algorithm container and selection  . . . . . . . .   5
   8.  Acknowledgements  . . . . . . . . . . . . . . . . . . . . . .   6
   9.  References  . . . . . . . . . . . . . . . . . . . . . . . . .   6
     9.1.  Informative References  . . . . . . . . . . . . . . . . .   6
     9.2.  External Informative References . . . . . . . . . . . . .   6
   Authors' Addresses  . . . . . . . . . . . . . . . . . . . . . . .   7

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 extensible, and
   thus, applicable in different scenarios, this draft is a general

Dujovne, et al.           Expires July 28, 2014                 [Page 2]
Internet-Draft              6tisch-on-the-fly               January 2014

   framework.  The exact scheduling algorithm and set of statistics is
   out of scope of this document.  This document follows the terminology
   defined in [I-D.ietf-6tisch-terminology] and the mechanisms described
   on [I-D.ietf-6tisch-tsch]

2.  Allocation policy

   OTF Softcell scheduling is distributed.  OTF sends scheduling
   requests to the 6top module, which allocates the requested Softcells.
   Softcell scheduling requests to the 6top layer are negotiated on a
   peer to peer basis without the participation of a PCE.  While a
   distributed mechanism reduces the latency compared to a centralized
   one, this may generate Softcell allocation collisions between
   different pairs of neighbor nodes.  OTF keeps track of the Softcell
   and Bundle scheduling.

   An allocation policy describes which are the rules to follow in order
   to comply with the requirements of different types of traffic,
   according to its variability, throughput and latency restrictions.

   OTF supports 3 types of allocation policies, namely Single, Group and
   Hybrid allocation policies.

   Single allocation policy: OTF schedules individual Softcells in
   response to the current algorithm requests.  OTF schedules single
   Softcells from the scheduling requests to 6top.  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 is used for communication.
   The remaining cells inside the Bundle remains 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 keeps track of the individual softcells, the

Dujovne, et al.           Expires July 28, 2014                 [Page 3]
Internet-Draft              6tisch-on-the-fly               January 2014

   allocated Bundles and the number of allocated cells inside the
   Bundle.

3.  Allocation methods

   Unlike the Allocation Policies, an allocation method deals with the
   specific mechanisms to schedule cells from 6top.  Given an Allocation
   Policy, the algorithm uses one or two methods altogether.  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: Since Bundles represent a group of pre-
   scheduled Softcells, they become immediately available.  Unlike
   SoftCell scheduling, which requires a negotiation period between the
   node's 6top layers, the delay is reduced when a Softcell from a
   Bundle is used.  Nevertheless, the use of Bundles forces the receiver
   module from the node to be in the Active state during the length of
   the Bundle, thus increasing power consumption.

   Once the Bundle is allocated, OTF may ask for sizing/re-sizing BW of
   a bundle, which implies softcells are reserved.  For this purpose,
   OTF only calculates the required Bandwidth, and 6top maps the BW to
   the number of soft cells according to some QoS setting, e.g. over-
   provision ratio, and finally 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: When there is a scheduling
   request to 6top for a new Softcell, the 6top layer negotiates this
   request with the 6top layer of the neighbor.  This negotiation may
   take one or more Softcells to complete, thus increasing the overhead.
   On the other side, when Softcell scheduling is used, the receiver
   module from the node only stays in the Active node for the scheduled
   Softcells, thus saving energy.  This mechanism assumes that the OTF
   algorithm schedules Softcells only when they are required.

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

Dujovne, et al.           Expires July 28, 2014                 [Page 4]
Internet-Draft              6tisch-on-the-fly               January 2014

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

   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 Softcells.  Direct interaction with
   6top

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.  Scheduling Algorithm container and selection

   There can be several scheduling algorithms for OTF.  The current
   algorithm can be selected with an external command.  The commands
   allowed are: SET and GET.  Scheduling algorithms are numbered from 1
   to 255.  OTF algorithm 0 is reserved for the default scheduling
   algorithm, defined as follows:

   Step 1: Obtain the Bandwidth requests from child nodes (incoming
   traffic)

   Step 2: Obtain the node Bandwidth requirement from the application
   (self traffic)

Dujovne, et al.           Expires July 28, 2014                 [Page 5]
Internet-Draft              6tisch-on-the-fly               January 2014

   Step 3: Obtain the current outgoing scheduled Bandwidth (outgoing
   traffic)

   Step 4: If (outgoing < incoming + self) then schedule a number of
   Soft Cells to satisfy requirements

   Step 5: If (outgoing > incoming + self) then unschedule the unused
   Soft Cells

   Step 6: Loop to Step 1

8.  Acknowledgements

   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

   [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-00 (work in
              progress), November 2013.

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

   [I-D.ietf-6tisch-tsch]
              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.

9.2.  External Informative References

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

Dujovne, et al.           Expires July 28, 2014                 [Page 6]
Internet-Draft              6tisch-on-the-fly               January 2014

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

   [TASA-PIMRC]
              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-tasa-25511.pdf>.

   [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
              /Accettura_et_al_GTTI2013.pdf>.

Authors' Addresses

   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

Dujovne, et al.           Expires July 28, 2014                 [Page 7]
Internet-Draft              6tisch-on-the-fly               January 2014

   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
   Politecnico di Bari
   Electrical and Electronics Department
   Via Orabona 4
   Bari  70125
   Italy

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

Dujovne, et al.           Expires July 28, 2014                 [Page 8]