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
draft-dujovne-6tisch-on-the-fly-00
Abstract
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
[I-D.watteyne-6tisch-tsch]
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
Bundle.
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
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 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
6top
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
[I-D.palattella-6tisch-terminology]
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.
[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.watteyne-6tisch-tsch]
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
[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.
[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
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
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
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 June 8, 2014 [Page 7]