idnits 2.17.1 draft-kim-6tisch-trfalice-00.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 : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document date (November 29, 2018) is 1975 days in the past. Is this intentional? Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) No issues found here. Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 1 comment (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 6TiSCH Working Group Seohyang Kim 3 Internet-Draft Seoul National University 4 Intended status: Standards Track Hyung-Sin Kim 5 Expires: May 27, 2019 University of California Berkeley 6 Chongkown Kim 7 Seoul National University 8 November 29, 2018 10 Autonomous and dynamic TSCH cell allocation 11 for time-varying traffic load and evolving topology 12 draft-kim-6tisch-trfalice-00 14 Abstract 16 This document provides the method that autonomously and dynamically 17 schedules TSCH slotframe based on the current traffic load. In the 18 introduction part, we introduce some basic knowledge on TSCH and 19 RPL. After this, we introduce some existing TSCH schedulers and 20 their limitations. They are classified as centralized, distributed, 21 and autonomous. Then, we propose a novel autonomous and dynamic 22 TSCH cell scheduler. With this, each node schedules its own TSCH 23 slotframe and allocates additional cells based on the current 24 traffic load without any negotiation or traffic overhead. Since 25 they allocate additional cells only when needed, energy efficient 26 operation can be achieved simultaneously. 28 Status of this Memo 30 This Internet-Draft is submitted in full conformance with the 31 provisions of BCP 78 and BCP 79. 33 Internet-Drafts are working documents of the Internet Engineering 34 Task Force (IETF). Note that other groups may also distribute 35 working documents as Internet-Drafts. The list of current Internet- 36 Drafts is at http://datatracker.ietf.org/drafts/current/. 38 Internet-Drafts are draft documents valid for a maximum of six 39 months and may be updated, replaced, or obsoleted by other 40 documents at any time. It is inappropriate to use Internet-Drafts 41 as reference material or to cite them other than as 42 "work in progress." 44 This Internet-Draft will expire on May 27, 2019. 46 Copyright Notice 48 Copyright (c) 2018 IETF Trust and the persons identified as the 49 document authors. All rights reserved. 51 This document is subject to BCP 78 and the IETF Trust's Legal 52 Provisions Relating to IETF Documents 53 (http://trustee.ietf.org/license-info) in effect on the date of 54 publication of this document. Please review these documents 55 carefully, as they describe your rights and restrictions with respect 56 to this document. Code Components extracted from this document must 57 include Simplified BSD License text as described in Section 4.e of 58 the Trust Legal Provisions and are provided without warranty as 59 described in the Simplified BSD License. 61 Table of Contents 63 1. Introduction . . . . . . . . . . . . . . . . . . . .. . . . . . 2 64 2. Requirements Language . . . . . . . . . . . . . . . . . . . . . 4 65 3. Terminology. . . . . . . . . . . . . . . . . . . . . . . . . . 4 66 4. TSCH Schedulers . . . . . . . . . .. . . . . . . . . . . . . . 4 67 4.1. Overview . . . . . . . . . . . . . . . . . . . . . . . . 4 68 4.2. Centralized Schedulers . . . . . . . . . . . . . . . . . 4 69 4.3. Distributed Schedulers . . . . . . . . . . . . . . . . 5 70 4.4. Autonomous Schedulers . . . . . . . . . . . . . . . . . 5 71 5. Autonomous and Dynamic TSCH Cell Allocation Method . . . . . . 6 72 5.1. Schedule of Unicast Slotframe. . . . . . . . . . . . . . 3 73 5.2. Schedule of Supplementary Slotframe. . . . . . . . . . . 3 74 5.3. Summary. . . . . . . . . . . . . . . . . . . . . . . . . 3 75 6. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 12 76 7. Security Considerations . . . . . . . . . . . . . . . . . . . . 12 77 8. Acknowlegement. . . . . . . . . . . . . . . . . . . . . . . . . 12 78 9. References. . . . . . . . . . . . . . . . . . . . . . . . . . . 13 79 9.1. Normative References. . . . . . . . . . . . . . . . . . . 13 80 9.2. Informative References. . . . . . . . . . . . . . . . . . 13 81 Authors' Addresses . . . . . . . . . . . . . . . . . . . . .. . . . 14 83 1. Introduction 85 TSCH is one mode on IEEE 802.15.4e standard and it is an acronym 86 of Time Slotted Channel Hopping, which has the feature of Time 87 Division Multiple Access with channel hopping. From 2003, IEEE 88 802.15.4 standard has been introduced and the standard was extended 89 with 2006 version. Zigbee is one of the mostly used protocol which 90 is on the basis of 802.15.4 standard. However, the standard was not 91 enough to support industrial network which requires higher 92 reliability. To better support industrial markets by increasing 93 robustness against external interference, the MAC portion of the 94 standard has been amended. Among 5 modes it provides, TSCH is 95 receiving most attentions from WSN researchers and industry market. 96 Moreover, by Internet Engineering Task Force (IETF) 6TiSCH working 97 group, it has been selected as a mac protocol to connect sensor 98 nodes with Internet over IPv6. 100 RPL is a routing protocol for low power and lossy network and has 101 been standardized by the IETF RoLL WG in 2012. RPL builds tree 102 topology on the basis of DODAG structure. To build and manage 103 routing topology, RPL control packets are exchanged. The routing 104 topology is maintained by using Rank and Objective Function. Each 105 node has its own rank and rank can be understood as the path cost 106 of each node to the root. Definition of rank, rank calculation or 107 parent selection rules are defined in the used objective function 108 (OF). Every node in the RPL network has a preferred parent except 109 the root. The rank of parent must be always lower than its own rank 110 and the rank of its children must be always higher than its own rank 111 By checking this value, routing loop is avoided or detected. 113 In this document, the point is that each node has preferred parent 114 and children as its RPL neighbor. To maintain routing topology, 115 they exchange RPL control messages periodically. Though other 116 routing topologies can be used over TSCH network, RPL is used 117 mostly. Moreover, to build IETF 6TiSCH compliant network, RPL and 118 TSCH should be used together. 120 Let's move on to network bootstrap phase on TSCH and RPL network. 121 Since TSCH is a link-layer protocol and RPL is a routing-layer 122 protocol, a node should join TSCH network first and join RPL next. 124 To build TSCH network, each node sends Enhanced Beacon (EB) which 125 includes TSCH network information such as frequency hopping 126 sequence, used frequency, the length of slotframe and Absolute 127 Slot Number (ASN). A node who received EB joins TSCH network and 128 it also broadcasts EB periodically. When a node joins TSCH network, 129 a node sets a node who sent EB as its time source. Since TSCH is a 130 time synchronized network, each node synchronizes its time to its 131 time source node. 133 When a node joins TSCH network, it should join RPL network to 134 exchange application-level messages. However, though IEEE 135 802.15.4e standard defines how mac executes TSCH schedule, it does 136 not provide how each node should build TSCH schedule. In general, 137 simple TSCH scheduling method is used at the initial network 138 bootstrap phase. Here, a cell (0,0) on a TSCH slotframe can be 139 used by all the nodes as a shared slot. All the nodes wake up at 140 this slot and sleep at the other timeslots synchronously. RPL 141 control packets are exchanged on this shared slot and the routing 142 topology is constructed. 144 However, just using only one cell on a TSCH slotframe does not seem 145 to make good use of TSCH technique. In order to take full 146 advantage of the benefits of TSCH technique, more number of cells 147 on a slotframe should be used for efficient communication. Here, 148 how each node schedules the slotframe directly affects network 149 performance including PDR, latency, duty cycle and throughput. 150 However, the standard does not answer this question. 152 When we design TSCH scheduling algorithm, we should consider various 153 aspects. For example, each node should have as many transmission 154 opportunity as the traffic load. A node close to the root requires 155 more communication opportunity compared to the leaf node, since it 156 should forward more number of packets between the root and its sub- 157 network. A node should receive packets from different neighbors on 158 different time slots to avoid contention at a cell. A node cannot 159 receive packets from multiple nodes at the same timeslot. With 160 only one radio interface, a node cannot listen and transmit at the 161 same timeslot. 163 It is not simple to set up a good schedule. Moreover, we should 164 remember that the RPL topology evolves over time. Even if a node 165 has an optimal schedule now, when the topology changes, new 166 schedule for the changed topology is needed. 168 Moreover, since the schedule of slotframe iterates over time, links 169 assigned to a crowded cell continue to suffer disadvantages. 170 Thereby, how we schedule slotframe directly affects performance of 171 TSCH, which again affects RPL performance. 173 2. Requirements Language 175 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", 176 "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this 177 document are to be interpreted as described in RFC 2119 [RFC 2119]. 179 3. Terminology 181 Cell : This document follows the same definition used in [RFC 7554] 183 ASN : This document follows the same definition used in [RFC 7554] 185 Slotframe : This document follows the same definition used in 186 [RFC 7554] 188 4. TSCH Schedulers 190 From now on, we will explore the existing works regarding TSCH 191 schedule. Depending upon their approach, scheduling methods are 192 categorized into 3 types: centralized, decentralized and autonomous. 194 4.1. Overview 196 Recall that IEEE 802.15.4e was standardized in 2012. At the first 197 year, centralized approaches have been proposed. With this approach, 198 a root node receives all network information from every node. After 199 obtaining a global view, this central node sets up optimal schedule. 201 However, this method requires high traffic overhead. Moreover, when 202 a new node joins network, the schedule of the whole nodes in the 203 network should be changed. 204 With this problem, naturally, the scheduling approach has been 205 changed from centralized to distributed approach. In this 206 methods, the scheduling load at the central node has been 207 distributed to all the nodes in the network. Though more flexible 208 and scalable scheduling could be achieved with this approach, 209 further traffic overhead for TSCH schedule still exists. 210 In 2015, a scheduling approach named orchestra have been proposed, 211 which does not require any traffic overhead or negotiation process. 212 With this method, each node can autonomously schedule its own TSCH 213 slotframe. Since it does not require any negotiation for TSCH 214 scheduling, it could achieve highly flexible and scalable schedule 215 regardless of topology variation. In April 2018, two more 216 autonomous scheduling method, which have similar approach to 217 Orchestra have been introduced. [Orchestra] 219 Since autonomous scheduling method does not require any traffic 220 overhead for TSCH scheduling, though it does not provide optimal 221 schedule, it provides high reliability, high flexibility, high 222 scalability with low scheduling overhead. 224 4.2. Centralized schedulers 226 TASA and MODESA are mostly cited TSCH centralized schedulers. These 227 two methods are very similar except only a few differences. Both 228 methods have very strong assumptions. They assume that the central 229 node knows complete topology information including routing topology, 230 traffic load of each node, conflict relations among nodes. They 231 assume that traffic load per each node does not change over time and 232 routing topology does not change over time. Since they assume 233 multi-point-to-point traffic scenario, they schedule only the 234 upstream links. Moreover, they assume no message loss with 0% link 235 error rate. [TASA][MODESA] 236 The difference between these two schedulers is that MOESA assumes 237 more complex network. For example, it considers queue-length of each 238 node and assumes that the root node can have multiple radio 239 interfaces. With strong assumptions described above, they could 240 build collision-free schedule. They evaluated the proposed methods 241 by using simple simulation. Moreover, since there is no message 242 loss at link-level, they only evaluated delay, duty cycle and 243 throughput. 245 4.3. Distributed schedulers 247 DeTAS and Wave are the early schedulers based on distributed 248 approach. Though the load of scheduling at the central node has 249 been distributed to all the nodes in the network, only the 250 centralized node can initiate the start of the schedule of all 251 the nodes in the network and each node!?s schedule is strongly 252 dependent on the schedule of its parent node. As a result, any 253 topology or traffic change results in a scheduling change of the 254 entire network as centralized schedule does. [DeTAS1][DeTAS2] 255 [Wave1][Wave2] 256 Both methods assume that each node has a constant traffic load and 257 multipoint-to-point scenario. The root node initiates the start of 258 the scheduling process. The node closer to the root selects cells 259 first. The cell selection rule is simple. Each node selects 260 timeslots those were not selected by its parent. 261 The difference is that, DeTAS selects channel offset on the basis of 262 hop-count, and Wave considers conflicting nodes group on its 263 channel offset schedule. To have knowledge on each node's conflicting 264 node group, Wave requires more control packets to exchange that 265 information. 266 However, these methods cannot be considered as a fully distributed 267 scheduling method in that each node!?s schedule strongly depends on 268 parent's choice. 270 From 2014, negotiation protocol for distributed TSCH schedule have 271 been proposed. The proposed negotiation technique have been 272 gradually developed through active open discussions in 6TiSCH 273 working group and has been standardized recently. They named the 274 negotiation protocol as 6P. [RFC 8480] By using 6P transactions, two 275 neighboring nodes can add, delete or relocate cells in their TSCH 276 slotframe for their unicast communication. However, 6P is just 277 used as a negotiation protocol. When to trigger 6P transaction 278 and how to schedule slotframe is determined by scheduling function. 279 OTF, SF0 and MSF are negotiation-based distributed scheduling method 280 that use 6P transaction. [OTF][SF0][MSF] With this methods, each node 281 flexibly schedules its own slotframe based on the current traffic 282 load. Whenever the required traffic load changes, each node adds or 283 delete cells. To avoid frequent schedule changes, they use 284 threshold. 285 MSF has been recently proposed, which schedules slotframe 286 autonomously by following Orchestra receiver based mode. If 287 additional cell is needed, MSF uses 6P transactions for further 288 cell allocation. 290 4.4. Autonomous schedulers 292 [Orchestra] was introduced on Sensys 2015 and it was the first and 293 the only one autonomous scheduler until April 2018. For three 294 years, no autonomous scheduler have been introduced. Although 295 two more autonomous schedulers have been introduced recently, 296 their fundamental design framework is the same as that of 297 orchestra: they calculate timeslots by hashing node ID. 298 The key idea of orchestra is that each node can obtain node IDs 299 of its parent and children from RPL level. Orchestra provides two 300 operation mode: sender-based and receiver-based. In sender-based 301 mode, each node schedules its transmission cell by hashing its 302 own node ID. By using this rule, it calculates receive cells by 303 hashing its neighbor!?s node ID, which are transmission cells of 304 its neighbor nodes. In the same way, in receiver-based mode, each 305 node calculates its receive cell by hashing its own node ID and 306 calculates its transmission cells by hashing its neighbor nodes' 307 ID. It is very simple and does not require any transmission 308 overhead for TSCH schedule. No negotiation is needed. 309 Its reliable performance was proved on a real-world large public 310 testbed. However, the limitation of Orchestra is that it 311 allocates only one TX or RX cell per slotframe, which limits 312 throughput, causing congestion near the root node. Besides, 313 the hashed values of different nodes may be the same value, 314 which makes the problem worse. 316 [Escalator] pointed out that Orchestra gives the nodes close to the 317 root and leaf nodes the same communication opportunities. It 318 focuses on the fact that a node with a larger sub-network has more 319 packets to forward. Thereby, the key idea is that each node 320 allocates different cells on its slotframe for all the nodes in 321 its sub-network. With this method, the node closer to the root 322 has more cells to forward packets. With the increased communication 323 opportunity, it could achieve higher throughput. However, since a 324 node closer to the root has large sub-tree, too many cells may be 325 allocated on its slotframe. Consequently, this node should be 326 awake for a longer time, regardless of the actual traffic load. 327 However, if the traffic load on the network is low, this node does 328 not need to stay awake for long. Moreover, since this method 329 considers hop-count information on its scheduling, with varying 330 routing topology, it may not work properly. 332 To overcome limitation of Orchestra which allocates only one TX or 333 RX cell per a slotframe, [e-TSCH-Orch] proposes different solution. 334 The key idea of the proposed method is that it allocates 335 additional multiple cells dynamically to clean the transmission 336 queue quickly. With this method, end-to-end delay is reduced with 337 the increased communication opportunity. Moreover, since cells 338 are added only when needed, nodes can use energy more efficiently. 340 In this method, slotframe is first scheduled based on Orchestra 341 receiver-based mode. Whenever each node transmits message, it 342 sends the number of packets in its transmission queue together 343 with the message, by using TSCH header. Then, a node who received 344 that message allocates additional cells consecutively from the 345 immediately next time slot. The sender sends message 346 sequentially and quickly cleans its queue. 347 However, rules for additive cell allocation are too simple, 348 thereby communication on additional cells may interfere with 349 communication in the existing cells scheduled by orchestra method, 350 which may cause network to be broken down. 352 5. Autonomous and Dynamic TSCH Cell Allocation Method 354 The trend of recent TSCH schedule research has changed from 355 centralized to distributed and has changed from a decentralized 356 approach to an autonomous approach. Regarding autonomous 357 scheduler, the most influential method to date is the orchestra, 358 and all subsequent studies are based on the design structure of 359 the orchestra. They hash node ID to calculate cells for 360 communication. 362 Recall that each node has multiple neighbors and one node is 363 connected with multiple links. With node-based scheduling method, 364 multiple different links are scheduled on a same cell. As a 365 result, scheduled links are concentrated in only a few cells 366 wasting other time slots or channel offsets. Each node SHOULD 367 utilize more time slots and more channel offsets in more efficient 368 way. 370 In the proposed method, we change the scheduling paradigm from 371 node-based to link-based. Moreover, it dynamically and autonomously 372 adds and deletes cells on a slotframe based on the current traffic 373 load. 375 Here, we use 4 different slotframes: 1) TSCH EB, 2) Broadcast 376 /Default, 3) Unicast, 4) Supplementary slotframes. 378 Scheduling rules for TSCH EB and Broadcast/Default slotframes 379 follow those of orchestra. To schedule unicast and supplementary 380 slotframes, we use a link-based scheduling approach. 382 5.1. Schedule of Unicast Slotframe 384 On the unicast slotframe, each node autonomously schedules all 385 directional links to its RPL neighbors in different cells. As a 386 result, the number of transmission (outgoing) links is equal to 387 the number of its RPL neighbors (preferred parent and children) 388 and the number of receive (incoming) links is also equal to the 389 number of its RPL neighbors. We define a link (X,Y) as the link 390 from node X to node Y. Then, the link ID of the link (X,Y) is 391 calculated by the following equation. 393 linkID(X,Y)=b*nodeID(X)+nodeID(Y) 395 Here, the coefficient b is used to distinguish the direction of the 396 link, and the value b can be the maximum value of available node 397 IDs. For example, if we use nodeID as the last byte of the mac 398 address, the value of coefficient b is 256. Thereby, we can 399 distinguish each directional link by using this equation. 401 Moreover, we also use time information by adopting ASFN. ASFN is 402 Absolute Slotframe Number that can be calculated using the 403 following equation. 405 ASFN = floor( ASN / SlotframeLength ) 407 The proposed method hashes the directional link ID and the ASFN 408 together. As a result, the TSCH schedule of the unicast slotframe 409 is changed every slotframe cycle. Therefore, even if multiple 410 links are scheduled in a same cell, they are fully distributed in 411 the next cycle. 413 Moreover, the proposed method uses multiple channel offsets so as 414 to take the benefits of channel diversity. Here we use the same 415 rule for both time offset and channel offset calculation. The 416 hashed value is projected to one offset and the projection area 417 depends on the number of available offset. 419 For hash function, a combination of integer mix function and 420 modulo operation can be used as the following form. 422 Hash(X,Y)= IntegerMixFunction(X) % Y 424 Hash(X,Y) therefore outputs a value in the range [0, Y - 1] from 425 input X. Thereby, we use the following equations to calculate a 426 cell for the link (A,B) at the current ASFN. 428 timeOffset = Hash( linkID(A,B)+ASFN , Nt_uc ) 430 channelOffset = Hash( linkID(A,B)+ASFN , Nc_uc ) +1 432 Where Nt_uc and Nc_uc are the number of time offsets and channel 433 offsets of the unicast slotframe, respectively. Thus, the ranges for 434 time offset and channel offset are [0, Nt_uc - 1] and [1, Nc_uc], 435 respectively. We do not use channel offset 0 since it is used by 436 TSCH EB slotframe. Due to priority settings between slotframes, 437 though channel offset 1 is used in the broadcast/default slotframe, 438 this offset can also be used in the unicast slot frame. 440 For example, when the shared slot of the broadcast/default slotframe 441 is activated, the channel offset 1 is used only for performing the 442 corresponding operation. At this time, although a cell in the 443 unicast slotframe is simultaneously scheduled at the same time 444 slot, the shared slot of the broadcast/default slotframe is 445 activated because of the priority setting between the slot frames. 446 In the remaining case, since broadcast/default slotframe is not 447 activated, the channel offset 1 is used only for the unicast 448 slotframe. 450 As described above, we use time information in scheduling and we 451 also use the integer mix function to achieve the result that the 452 output value is completely different when the input value is 453 changed by 1. Consequently, if the ASFN increases by 1 for every 454 slot frame cycle, the next unicast slot frame schedule will be 455 completely changed from the current schedule. 457 With this scheduling method, on the unicast slotframe, each node 458 allocated a cell for each directional link between the node 459 itself and its RPL neighbors. When the network traffic load is low 460 enough, allocating only one cell for each directional link per 461 slotframe is enough to support reliable communication. However, as 462 the traffic load increases, just allocating only one cell may not 463 enough. Moreover, a node close to the root has more packets to 464 forward to support multi-hop communication between the root and 465 the nodes in its sub-network. 467 Depending on the current traffic load, each node SHOULD dynamically 468 and flexibly manage the number of unicast cells it can use. 470 5.2. Schedule of Supplementary Slotframe 472 We can think two approaches. One is static additive cell allocation 473 based on the sub-tree size of each node. The other is dynamic and 474 additive cell allocation based on the current traffic load to its 475 RPL neighbors. In the former method, if the traffic load is low, 476 the additional allocated cells might not be used, resulting in 477 energy wastage. So we use the latter approach when we allocate 478 additional cells to achieve energy efficiency. Because additional 479 cells are allocated only when needed, we don't have to worry about 480 unnecessary wake-up period. 482 Moreover, the additional allocated cells MUST NOT interfere with 483 communication scheduled at the previous three (TSCH EB, Broadcast 484 /Default, Unicast) slotframes. So we use completely different 485 channels on supplementary slotframe with the lowest priority among 486 all the slotframes used. 488 To recognize the current traffic load and detect the traffic change 489 in real time, each node manages 4 parameters (myTxCount, myNumTx, 490 NumTx, NumRx) per each neighbor node X. 492 myTxCount(X): A counter that counts the number of required 493 transmission cell per slotframe from the node itself to its neighbor 494 X. The value is used to update myNumTx(X). Using myTxCount(X), 495 myNumTx(X) is updated at the last active cell of the current 496 slotframe schedule. After myNumTx(X) is updated, myTxCount(X) SHOULD 497 be set as 0 to count the number of required transmission cell for 498 the next slotframe cycle. When counting how many cells are needed, 499 it SHOULD consider NOT only the number of enqueued packets in the 500 transmission queue but also mac-layer retransmissions. 502 myNumTx(X): The required number of transmission cells per slotframe 503 for node X. The value is updated at the last active cell of the 504 current slotframe schedule of the current ASFN. Update equation can 505 be as follows: myNumTx(X) = (1-e)*myNumTx(X)+e*myTxCount(X). Here, 506 a coefficient e is used to implement exponentially weighted moving 507 average (EWMA). After the calculation of new myNumTx(X) at the last 508 active cell of the current slotframe, myTxCount(X) is set as 0 to 509 count the number of required transmission cell for the next 510 slotframe cycle. 512 NumTx(X): The number of transmission slots per supplementary 513 slotframe for node X. Whenever a node sends a unicast packet to its 514 neighbor node X, it sends the number myNumTx(X) on the TSCH header 515 together with the message. After receiving the link-layer 516 acknowledgement from node X, the node updates NumTx(X) to 517 myNumTx(X). The node can not update the value NumTx(X) to 518 myNumTx(X) until it receives link-layer acknowledgement to the 519 sent unicast message to node X. 521 NumRx(X): The number of listen slots per supplementary slotframe for 522 node X. Each time a unicast packet is received from the node X, 523 the value is updated to the latest value. 525 Example scenario: There are node A and B. Node A sends a unicast 526 message to node B periodically. Every slotframe cycle, node A 527 counts the number of required transmission cells for node B by 528 managing myTxCount(B). Based on this value, myNumTx(B) is updated 529 at the last cell of each slotframe cycle. Whenever node A sends a 530 unicast packet to node B, it puts myTxCount(B) in the TSCH header. 531 When it receives mac-layer acknowledgement from node B, it updates 532 NumTx(X) to the current myTxCount(B). Since node B received 533 unicast message sent from node A successfully, it knows how much 534 additional transmission cells A will allocate through the 535 information in the TSCH header. So node B allocates that amount of 536 additional listen cells. All these additional cells are allocated 537 only on the supplementary slotframe. 539 Each node has NumTx(X) and NumRx(X) for each RPL neighbors. It 540 SHOULD allocate NumTx(X) more transmission cells for the 541 transmission link (NodeID,X) and NumRx(X) more listen cells for 542 the receive link (X,NodeID). Thereby each node knows the number 543 of additional cells that SHOULD be scheduled for link (X,Y). 544 According to this value, each link (X,Y) has the number of 545 additional cells that SHOULD be scheduled on supplementary 546 slotframe and we assign different traffic ID for each additional 547 requirement for each link. For example, if N additional cell 548 assignments are required for the link (X,Y), we have N different 549 trfID(X,Y) and which are 1, 2, 3, ... , N. 551 By using trfID(X,Y), linkID(X,Y) and ASFN, each additional cell on 552 supplementary slotframe for link (X,Y) is scheduled by using the 553 following equations. 555 timeOffset = Hash(a*trfID(X,Y)+linkID(X,Y)+ASFN, Nt_sc) 556 channelOffset = Hash(a*trfID(X,Y)+linkID(X,Y)+ASFN, Nc_sc) +1+Nc_uc 558 Where Nt_sc and Nc_sc are the number of time offset and channel 559 offset in supplementary slotframe. Here, coefficient a is used to 560 distinguish a tuple of traffic ID and link ID. The value of 561 coefficient a is the maximum value of link ID. Therefore, if we use 562 the last byte of the mac address as node ID, the maximum value of 563 node ID is 256 and the maximum value of link ID is 256*256. 564 Thereby, we use 256*256=65,536 as coefficient a. 566 For channel offset, we add 1+Nc_uc to the hashed output not to use 567 the same channels used by TSCH EB, Broadcast/Default and Unicast 568 slotframes. As a result, cells scheduled on supplementary 569 slotframe does not interfere with communication in the other 570 three slotframes. 572 5.3. Summary 574 Here, we summarize the proposed method. The key idea is simple. The 575 proposed method is dynamic and autonomous TSCH cell scheduling 576 method which does not require any negotiation process or additional 577 packet exchange. we use directional link ID to allocate different 578 cell for each link and they are scheduled on unicast slotframe. We 579 use ASFN to periodically change the slotframe schedule not to 580 disadvantage links scheduled on a crowded cell. If communication 581 opportunities provided by unicast slotframe is not enough, we use 582 supplementary slotframe for additional cell allocation. 583 Supplementary slotframe does not use the channels used by the other 584 slotframes and has the lowest priority among all the used 585 slotframes, not to interfere default schedule. Since the number of 586 further allocated cells is based on the current traffic load, 587 additional cells are allocated only when needed and are 588 automatically deleted if not needed. 590 6. IANA Considerations 592 There are no IANA considerations related to this document. 594 7. Security Considerations 596 Autonomous and dynamic TSCH cell allocation method for time-varying 597 traffic load and evolving topology has similar requirements on 598 security as [RFC 7554]. 600 8. ACKNOWLEDGEMENT 602 This work was supported by the National Research Foundation of 603 Korea(NRF) Grant funded by the Korean Government(MSIP) 604 (No.2016R1A5A1012966), MSIP support program (IITP-2018-2015-0-00378) 605 supervised by the IITP, IITP grant funded by the Korea government 606 (MSIT) (No.2015-0-00557, Resilient/Fault-Tolerant Autonomic 607 Networking Based on Physicality, Relationship and Service Semantic 608 of IoT Devices) and Institute for Industrial Systems Innovation of 609 Seoul National University. 611 9. References 613 9.1. Normative References 615 [RFC 2119] S. Bradner, Key words for use in RFCs to Indicate 616 Requirement Levels, IETF Network Working Group RFC 2119, March 617 1997. 618 [RFC 8480] Q. Wang, et al., 6TiSCH Operation Sublayer (6top) Protocol 619 (6P), IETF 6TiSCH RFC 8480, November 2018. 621 9.2. Informative References 623 [RFC 7554] T. Watteyne, Ed., L. Grieco, Using IEEE 802.15.4e Time- 624 Slotted Channel Hopping(TSCH) in the Internet of Things(IoT): 625 Problem Statement, IETF 6TiSCH RFC 7554, May 2015. 626 [TASA] M. R. Palattella, et al., Traffic Aware Scheduling Algorithm 627 for Reliable Low-Power Multi-Hop IEEE 802.15.4e Networks, 628 IEEE PIMRC 2012. 629 [MODESA] R. Soua, et al., MODESA: An optimized multichannel slot 630 assignment for raw data convergecast in wireless sensor 631 networks, IEEE IPCCC, 2012. 632 [DeTAS1] N. Accettura, et al., DeTAS: a Decentralized Traffic Aware 633 Scheduling technique enabling IoT-compliant Multi-hop Low- 634 power and Lossy Networks, IEEE WoWMoM 2013. 635 [DeTAS2] N. Accettura, et al., Decentralized Traffic Aware Scheduling 636 in 6TiSCH Networks: Design and Experimental Evaluation, IEEE 637 Internet of Things Journal, vol.2, no.6, December 2015. 638 [Wave1] R. Soua, et al., A distributed joint channel and slot 639 assignment for convergecast in wireless sensor networks, NTMS 640 2014. 641 [Wave2] R. Soua, et al., Wave: a distributed scheduling algorithm for 642 convergecast in IEEE 802.15.4e TSCH networks, Transactions on 643 Emerging Telecommunications Technologies, Vol. 27, no.4, April 644 2016. 646 [OTF] M.R. Palattella, et al., On-the-fly bandwidth reservation for 647 tisch wireless industrial networks, IEEE Sensors Journal, vol. 648 16, no. 2, pp.550-560, 2016. 649 [SF0] D. Dujouvne, et al., 6TiSCH 6top Scheduling Function Zero 650 (SF0), IETF 6TiSCH Internet Draft, 5/12/2016-1/3/2018. 651 [MSF] T. Chang, et al., 6TiSCH Minimal Scheduling Function (MSF), 652 IETF 6TiSCH Internet Draft, 8/21/2018 (active I-D). 653 [Orchestra] Simon Duquennoy, et al., Orchestra: Robust Mesh Networks 654 Through Autonomously Scheduled TSCH, ACM SenSyS 2015, November 655 1-4, 2015. 656 [Escalator] S. Oh, et al., Escalator: An Autonomous Scheduling Scheme 657 for Convergecast in TSCH, MDPI Sensors, April 2018. 658 [e-TSCH-Orch] Sana Rekik, et al., Autonomous and traffic-aware 659 scheduling for TSCH networks, Computer Networks, ELSEVIER, 660 2018, 135, pp.201-212. 662 Authors' Addresses 664 Seohyang Kim 665 Department of Computer Science and Engineering 666 Seoul National University 667 Seoul, Republic of Korea 669 Phone: +82 (0)2 880 1858 670 Email: shkim@popeye.snu.ac.kr 672 Hyung-Sin Kim 673 Computer Science Division 674 University of California, Berkeley 675 Berkeley, CA, USA 677 Phone: +82 (0)2 880 1858 678 Email: hs.kim@cs.berkeley.edu 680 Chongkwon Kim 681 Department of Computer Science and Engineering 682 Seoul National University 683 Seoul, Republic of Korea 685 Phone: +82 (0)2 880 1858 686 Email: ckim@snu.ac.kr