idnits 2.17.1 draft-dujovne-6tisch-on-the-fly-02.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack a Security Considerations section. ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (February 14, 2014) is 3716 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- == Missing Reference: 'IEEE802154e' is mentioned on line 364, but not defined == Missing Reference: 'IEEE802154' is mentioned on line 370, but not defined == Missing Reference: 'TASA-PIMRC' is mentioned on line 376, but not defined == Missing Reference: 'DeTAS' is mentioned on line 383, but not defined == Outdated reference: A later version (-10) exists of draft-ietf-6tisch-terminology-01 == Outdated reference: A later version (-30) exists of draft-ietf-6tisch-architecture-01 == Outdated reference: A later version (-06) exists of draft-ietf-6tisch-tsch-00 Summary: 2 errors (**), 0 flaws (~~), 8 warnings (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 6TiSCH D. Dujovne, Ed. 3 Internet-Draft Universidad Diego Portales 4 Intended status: Informational LA. Grieco 5 Expires: August 18, 2014 Politecnico di Bari 6 MR. Palattella 7 University of Luxembourg 8 N. Accettura 9 Politecnico di Bari 10 February 14, 2014 12 6TiSCH On-the-Fly Scheduling 13 draft-dujovne-6tisch-on-the-fly-02 15 Abstract 17 This document describes the environment, problem statement, and goals 18 of the On-The-Fly (OTF) scheduling approach for the IEEE802.15.4e 19 TSCH MAC protocol in the context of LLNs. The purpose of OTF is to 20 dynamically adapt the aggregate bandwidth, i.e., the number of 21 reserved soft cells between neighbor nodes, based on the specific 22 application constraints to be satisfied. The soft cell and Bundle 23 reservation with OTF is distributed: through the 6top interface, 24 neighbor nodes negotiate the cell(s) to be (re)allocated/deleted, 25 without intervention of a centralized entity. This document aims at 26 defining a module which uses the functionalities provided by the 6top 27 sublayer to (i) extract statistics and (ii) determine when to reserve 28 /delete soft cells in the schedule. The exact reservation and 29 deletion algorithm, and the number and type of statistics to be used 30 in the algorithm are out of scope. OTF deals only with the number of 31 soft cells to be reserved/deleted; it is up to 6top to select the 32 specific soft cells within the TSCH schedule. 34 Status of This Memo 36 This Internet-Draft is submitted in full conformance with the 37 provisions of BCP 78 and BCP 79. 39 Internet-Drafts are working documents of the Internet Engineering 40 Task Force (IETF). Note that other groups may also distribute 41 working documents as Internet-Drafts. The list of current Internet- 42 Drafts is at http://datatracker.ietf.org/drafts/current/. 44 Internet-Drafts are draft documents valid for a maximum of six months 45 and may be updated, replaced, or obsoleted by other documents at any 46 time. It is inappropriate to use Internet-Drafts as reference 47 material or to cite them other than as "work in progress." 48 This Internet-Draft will expire on August 18, 2014. 50 Copyright Notice 52 Copyright (c) 2014 IETF Trust and the persons identified as the 53 document authors. All rights reserved. 55 This document is subject to BCP 78 and the IETF Trust's Legal 56 Provisions Relating to IETF Documents 57 (http://trustee.ietf.org/license-info) in effect on the date of 58 publication of this document. Please review these documents 59 carefully, as they describe your rights and restrictions with respect 60 to this document. Code Components extracted from this document must 61 include Simplified BSD License text as described in Section 4.e of 62 the Trust Legal Provisions and are provided without warranty as 63 described in the Simplified BSD License. 65 Table of Contents 67 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 2 68 2. Allocation policy . . . . . . . . . . . . . . . . . . . . . . 3 69 3. Allocation methods . . . . . . . . . . . . . . . . . . . . . 5 70 4. Input parameters: statistics and instant values . . . . . . . 6 71 5. bundle usage management in OTF: TODO . . . . . . . . . . . . 6 72 5.1. Cell Reservation/Deletion . . . . . . . . . . . . . . . . 6 73 5.2. bundle Size Increase/Decrease . . . . . . . . . . . . . . 6 74 6. Schedule storage on OTF: TODO . . . . . . . . . . . . . . . . 6 75 7. Bandwidth Estimation Algorithms . . . . . . . . . . . . . . . 6 76 8. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 7 77 9. References . . . . . . . . . . . . . . . . . . . . . . . . . 8 78 9.1. Informative References . . . . . . . . . . . . . . . . . 8 79 9.2. External Informative References . . . . . . . . . . . . . 8 80 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9 82 1. Introduction 84 The IEEE802.15.4e standard [IEEE802154e] was published in 2012 as an 85 amendment to the Medium Access Control (MAC) protocol defined by the 86 IEEE802.15.4-2011 [IEEE802154] standard. The Timeslotted Channel 87 Hopping (TSCH) mode of IEEE802.15.4e is the object of this document. 89 On-The-Fly (OTF) scheduling is a distributed protocol in which a node 90 negotiates the number of soft cells scheduled with its neighbors, 91 without the intervention of a centralized entity (e.g., a PCE). In 92 particular, this document describes the OTF allocation policies and 93 methods used for allocating single soft cell or group of them (i.e. 94 bundle) between two neighbors. It also proposes some potential 95 algorithms for estimating the required bandwidth. In this document, 96 internal interface used between OTF and the 6top sublayer 97 ([I-D.wang-6tisch-6top]) is defined, with a particular focus on the 98 functionalities. Example functionalities are collecting and 99 providing statistic information, or allocating/deleting cells and 100 bundles. To be extensible and applicable to different scenarios, 101 this draft is a generic framework. The exact algorithm and set of 102 statistics used for estimating the requested bandwidth is out of 103 scope. This draft follows the terminology defined in 104 [I-D.ietf-6tisch-terminology] and addresses the open issue related to 105 the scheduling mechanisms raised in [I-D.ietf-6tisch-tsch]. 107 2. Allocation policy 109 OTF is a distributed scheduling protocol which sends scheduling 110 requests to the 6top sublayer. OTF thereby dynamically increases/ 111 decreases the bandwidth allocated between neighbor nodes. 6top takes 112 care of negociating the soft cells between neighbors. Because OTF 113 delegates the selection of the specific cells to 6top, OTF only 114 supports soft cell reservation. Therefore, the term "cell" is 115 synonymous to "soft cell" in this document. 117 OTF is prone to schedule collision. Nodes might not be aware of the 118 cells allocated by other pairs of neighbors nodes. A collision 119 occurs when the same cell is allocated by different pairs in the same 120 interference space. The 6top sublayer cannot differentiate 121 collisions from other sources of packet loss. The probability of 122 having allocation collision may be kept low by grouping cells into 123 chunks (see [I-D.ietf-6tisch-terminology] and 124 [I-D.ietf-6tisch-architecture] for more details). The use of chunks 125 is outside the scope of this current version of the OTF draft. 127 We call "allocation policy" the approach used by OTF for increasing 128 or decreasing the bandwidth allocated between two nodes in order to 129 satisfy the traffic requirements. These requirements can be 130 expressed in terms of throughput, latency or other constraints. 132 OTF supports 3 different types of allocation policies: Post- 133 allocation, Pre-allocation and Hybrid allocation. 135 Post-allocation policy is based on a "recovery" approach following 136 the increased/decreased need of bandwidth. Upon reception of a 137 bandwidth request, OTF sends soft cell allocation requests to the 138 6top sublayer. OTF has to estimate the number of cells to be 139 allocated per each neighbor. OTF keeps track of such information. 140 If afterwards, it is possible to free some cells (due for instance to 141 the reduction of traffic exchanged between two neighbors), OTF asks 142 6top to de-allocate a given number of cells. Once the cells have 143 been deleted and 6top has notified the event to OTF, the latter can 144 update its internal cell allocation tables. 146 Pre-allocation policy is based on a "provision" approach. This 147 implies that the reservation of groups of equivalents cells (i.e., 148 bundles), to a given couple of nodes, is done in advance. When OTF 149 sends a bundle allocation requests to 6top, it has to indicate the 150 desired size of the bundle and the TrackID. These are the only 151 features that can be settled by OTF. 6top selects the soft cells 152 belonging to the bundle. Based on the network traffic condition 153 (e.g. queue utilization), a number of cells within the bundle is used 154 for communication. In any case, allocated cells within a bundle are 155 consecutive, starting from the first cell in the block. The cells 156 which are not currently used, are still reserved for that pair of 157 nodes, for possible future use. 159 OTF keeps track of the scheduled bundles, the bundle size, and the 160 estimated number of allocated cells within a bundle. Based on this 161 information, upon reception of a bandwidth request, OTF may ask 6top 162 to increase or decrease the bundle size. 164 The post-allocation policy compared to the pre-allocation reduces the 165 energy consumption, by allocating the exact number of soft cells when 166 they are needed, but at the expense of increased cell allocation 167 latency. In fact, for each requested soft cell, the 6top layer has 168 to negotiate the request with the 6top layer of the neighbor node. 169 Such negotiation takes some time and induces communication overhead. 171 The pre-allocation policy compared to the post-allocation reduces the 172 cell allocation latency. The soft cells within the bundle are over- 173 provisioned, and a priori scheduled. When needed, the 6top sublayer 174 of the node can allocate them, without going through any negotiation 175 phase with the 6top layer of the neighbor node. Thus, the pre- 176 allocation approach provides a low-delay response after a surge in 177 bandwidth usage. In fact, soft cells within a bundle are already 178 scheduled and become immediately available, upon bandwidth request, 179 without the need of a negotiation phase. The use of bundles does 180 force the receiver module of the node to be active during the whole 181 length of the Bundle, thus implying increased power consumption. 183 The hybrid allocation policy is a mix of the pre- and post- 184 allocation policy. It tries to take advantage of both the 185 "provision" and "recovery" approaches. Some bundles can be reserved 186 in advance for a pair of nodes. After receiving a bandwidth request, 187 OTF can decide if asking to 6top for (new) soft cell allocation (as 188 per post-allocation approach, implying a negotiation phase among the 189 neighbor nodes), or for bundle allocation/resizing (as per pre- 190 allocation approach). In fact, tt is possible that more bandwidth is 191 needed, but there are still some cells within the bundle that have 192 not been allocated yet, and that they can be used for fulfilling the 193 request. If all the cells within the bundle have already been 194 allocated, OTF has to send a bundle size increase request to 6top 195 (that still translates in soft cells allocation request). 197 3. Allocation methods 199 Beyond the allocation policies that describe the approach used by OTF 200 for fulfilling the node bandwidth requests, the OTF framework also 201 includes Allocation Methods that specify how OTF actually asks the 202 6top sublayer to satisfy the aforementioned requests. In other 203 words, the allocation methods represent the mechanisms that are used 204 by the allocation policies to pre- or post- allocate extra bandwidth. 206 In detail, OTF includes two distinct allocation methods: soft cell 207 and bundle allocation methods. Each Allocation Policy can use either 208 one or both allocation methods. As specified in 209 [I-D.wang-6tisch-6top], 6top provides a set of commands that allows 210 to schedule/allocate/delete soft cells. The same set of commands can 211 be used for reserving bundles. 213 With the soft cell allocation method, OTF asks 6top to reserve a 214 single soft cell, for communicating with a specific neighbour node, 215 on a given track. The 6top layer allocates and maintains such cell. 216 It has to be noticed that if a bundle (i.e., a group of cells) was 217 already reserved between the same couple of nodes, on the same track, 218 then, such soft cell allocation request translates into a bundle 219 resize request. In fact, the new allocated cell will increase the 220 size of the already exsisting bundle. In a similar way, when OTF 221 realizes that there is a reduction of traffic exchanged between the 222 two neighbors, it may asks 6top to delete a soft cell, in other 223 words, to decrease the bundle size. Instead, if no bundle with the 224 same TrackID already existed, then the 6top soft cell create command 225 will generate a new bundle of size 1, having the specified TrackID. 227 With the bundle allocation method, OTF sends bundle allocation 228 requests to 6top sublayer, specifying the bundle size (i.e., number 229 of soft cells forming the bundle itself) and the TrackID of the track 230 to which the cells belong. By using the soft cells commands 6top 231 generates the bundle. In fact, the request of scheduling N soft cell 232 is equivalent to asking for a bundle of size N. The cells within the 233 bundle will be allocated by 6top afterwards, according to the nodes 234 bandwith need. 236 4. Input parameters: statistics and instant values 238 Short summary of a potential set of statistics and instant values 239 that could be used as input parameters. Direct interaction with 240 6top. 242 List of parameters available from 6top: mainly statistics related to 243 queues 245 Method to configure 6top to provide historical values for each 246 requested parameter 248 Method to ask 6top for instant values for each requested parameter 250 Method for asking for a list of parameters from 6top and thus, for 251 checking if a parameter is available or not 253 5. bundle usage management in OTF: TODO 255 Methods that trigger the request of increasing/decreasing the bundle, 256 and thus, adding/deleting cells 258 5.1. Cell Reservation/Deletion 260 The commands to reserve/delete soft cells. Direct interaction with 261 6top 263 5.2. bundle Size Increase/Decrease 265 The commands to increase/decrease the bundle size. Direct 266 interaction with 6top 268 6. Schedule storage on OTF: TODO 270 The description and access to the schedule storage on OTF 272 The commands to retrieve bundle usage values and statistics from OTF 273 (based on previous values obtained by 6top?) 275 7. Bandwidth Estimation Algorithms 277 OTF supports different bandwidth estimation algorithms that can be 278 used by a node in a 6TiSCH network for checking the current traffic 279 condition and thus the actual bandwidth usage. By doing so, it is 280 possible to adapt (increase or increase) the number of scheduled 281 cells/bundles for a given pair of neighbors (e.g., parent node and 282 its child), according to their needs. OTF supports several bandwidth 283 estimation algorithms numbered from 0 to 255 in the OTF 284 implementation. The first algorithm (0) is reserved to the default 285 algorithm that is described below. By using SET and GET commands, it 286 is possible, to set the specific algorithm to be used, and get 287 information about which algorithm is actualy implemented. 289 The default bandwidth estimation algorithm, running over a parent 290 node, is articulated in the following steps: 292 Step 1: Collect the bandwidth requests from child nodes (incoming 293 traffic). 295 Step 2: Collect the node bandwidth requirement from the application 296 (self/local traffic). 298 Step 3: Collect the current outgoing scheduled bandwidth (outgoing 299 traffic). 301 Step 4: If (outgoing < incoming + self) then SCHEDULE soft cells/ 302 bundles to satisfy bandwidth requirements. 304 Step 5: If (outgoing > incoming + self) then DELETE the soft cells 305 that are not used. 307 Step 6: Loop to Step 1. 309 Based on the allocation policy that is used, at Step 4 new soft cells 310 will be scheduled, using the cell allocation method. If there are 311 free cells in the bundle that can satisfied the current bandwidth 312 request, such cells will be allocated. In the case of pre-allocation 313 policy, it may happen that the number of allocated cells within the 314 bundle is equal to the bundle size. That is, all the cells within 315 the bundle are currently used. In this case, the node asks 6top for 316 increasing the bundle size by using the bundle allocation method. 317 When the hybrid allocation policy has been selected two options are 318 available: (i) the bundle size is increased, and a number of cells 319 larger than those currently needed, can be scheduled - according to 320 post-allocation approach, or (ii) a number of soft cells equal 321 exactly to those currently needed are scheduled, as per post- 322 allocation approach. 324 8. Acknowledgements 326 Special thanks to Prof. Kris Pister for his valuable contribution in 327 designing the default Bandwidth Estimation Algorithm, and to Qin Wang 328 for her support in defining the interaction between OTF and 6top 329 sublayer. 331 Thanks to the Fondecyt 1121475 Project, to INRIA Chile "Network 332 Design" group and to the IoT6 European Project (STREP) of the 7th 333 Framework Program (Grant 288445). 335 9. References 337 9.1. Informative References 339 [I-D.ietf-6tisch-terminology] 340 Palattella, M., Thubert, P., Watteyne, T., and Q. Wang, 341 "Terminology in IPv6 over the TSCH mode of IEEE 342 802.15.4e", draft-ietf-6tisch-terminology-01 (work in 343 progress), February 2014. 345 [I-D.ietf-6tisch-architecture] 346 Thubert, P., Watteyne, T., and R. Assimiti, "An 347 Architecture for IPv6 over the TSCH mode of IEEE 348 802.15.4e", draft-ietf-6tisch-architecture-01 (work in 349 progress), February 2014. 351 [I-D.ietf-6tisch-tsch] 352 Watteyne, T., Palattella, M., and L. Grieco, "Using 353 IEEE802.15.4e TSCH in an LLN context: Overview, Problem 354 Statement and Goals", draft-ietf-6tisch-tsch-00 (work in 355 progress), November 2013. 357 [I-D.wang-6tisch-6top] 358 Wang, Q., Vilajosana, X., and T. Watteyne, "6TiSCH 359 Operation Sublayer (6top)", draft-wang-6tisch-6top-00 360 (work in progress), October 2013. 362 9.2. External Informative References 364 [IEEE802154e] 365 IEEE standard for Information Technology, "IEEE std. 366 802.15.4e, Part. 15.4: Low-Rate Wireless Personal Area 367 Networks (LR-WPANs) Amendament 1: MAC sublayer", April 368 2012. 370 [IEEE802154] 371 IEEE standard for Information Technology, "IEEE std. 372 802.15.4, Part. 15.4: Wireless Medium Access Control (MAC) 373 and Physical Layer (PHY) Specifications for Low-Rate 374 Wireless Personal Area Networks", June 2011. 376 [TASA-PIMRC] 377 Palattella, MR., Accettura, N., Dohler, M., Grieco, LA., 378 and G. Boggia, "Traffic Aware Scheduling Algorithm for 379 Multi-Hop IEEE 802.15.4e Networks", IEEE PIMRC 2012, Sept. 380 2012, < http://www.cttc.es/resources/doc/ 381 120531-submitted-tasa-25511.pdf>. 383 [DeTAS] Accettura, N., Palattella, MR., Boggia, G., Grieco, LA., 384 and M. Dohler, "Decentralized Traffic Aware Scheduling for 385 Multi-hop Low Power Lossy Networks in the Internet of 386 Things", IEEE WoWMoM 2013, June 2013. 388 Authors' Addresses 390 Diego Dujovne (editor) 391 Universidad Diego Portales 392 Escuela de Informatica y Telecomunicaciones 393 Av. Ejercito 441 394 Santiago, Region Metropolitana 395 Chile 397 Phone: +56 (2) 676-8121 398 Email: diego.dujovne@mail.udp.cl 400 Luigi Alfredo Grieco 401 Politecnico di Bari 402 Department of Electrical and Information Engineering 403 Via Orabona 4 404 Bari 70125 405 Italy 407 Phone: 00390805963911 408 Email: a.grieco@poliba.it 410 Maria Rita Palattella 411 University of Luxembourg 412 Interdisciplinary Centre for Security, Reliability and Trust 413 4, rue Alphonse Weicker 414 Luxembourg L-2721 415 LUXEMBOURG 417 Phone: (+352) 46 66 44 5841 418 Email: maria-rita.palattella@uni.lu 419 Nicola Accettura 420 Politecnico di Bari 421 Electrical and Electronics Department 422 Via Orabona 4 423 Bari 70125 424 Italy 426 Phone: +39 080 5963301 427 Email: n.accettura@poliba.it