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]