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]