6TiSCH Working Group Seo Hyang Kim Internet-Draft Seoul National University Intended status: Standards Track Na Eon Kim Expires: June 17, 2017 Seoul National University Nguyen Duc Lam Seoul National University Chong Kown Kim Seoul National University December 15, 2016 Autonomous Link-based TSCH Cell Scheduling draft-3k1n-6tisch-alice0-01 Abstract This document describes the limitation of present TSCH cell scheduling methods which use centralized or decentralized approach. It firstly overview pros and cons of various cell scheduling approaches including centralized, decentralized and autonomous TSCH cell scheduling methods. It also suggest design considerations on devising autonomous scheduling approach to avoid unexpected confliction and increase channel utilization. For the last, it provides one example that reflects all design considerations mentioned. 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." This Internet-Draft will expire on June 17, 2017. Kim, et al. Expires June 17, 2017 [page 1] Internet-Draft ALICE December 2016 Copyright Notice Copyright (c) 2016 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 . . . . . . . . . . . . . . . . . . . .. . . . . . 3 2. Requirements Language . . . . . . . . . . . . . . . . . . . . . 3 3. Terminology. . . . . . . . . . . . . . . . . . . . . . . . . . 3 4. TSCH Cell Scheduling. . . . . . . .. . . . . . . . . . . . . . 3 4.1. Centralized Approach . . . . . . . . . . . . . . . . . . 4 4.2. Decentralized Approach. . . . . . . . . . . . . . . . . 5 4.3. Autonomous Approach . . . . . . . . . . . . . . . . . . 5 5. Design Considerations for Autonomous TSCH Cell Scheduling . . . 6 5.1. Link-based scheduling . . . . . . . . . . . . . . . . . 6 5.2. Hop-count-based scheduling . . . . . . . . . . . . . . . 7 5.3. SlotframeID . . . . . . . . . . . . . . . . . . . . . . 7 5.4. Upstream: link-based, Downstream: node-based . . . . . . 7 5.5. Upstream downstream scheduling . . . . . . . . . . . . . 8 6. ALICE overview . . . . . . . . . .. . . . . . . . . . . . . . 8 6.1. Link-based scheduling . . . . . . . . . . . . . . . . . 9 6.2. Hop-count-based scheduling . . . . . . . . . . . . . . . 9 6.3. SlotframeID . . . . . . . . . . . . . . . . . . . . . . 9 6.4. Upstream: link-based, Downstream: node-based . . . . . . 10 6.5. Upstream downstream scheduling . . . . . . . . . . . . . 10 7. ALICE details . . . . . . . . . . . . . . . . . . . . . . . . . 10 7.1. Upstream cell scheduling. . . . . . . . . . . . . . . . . 11 7.1.1. Recieve scheduling . . . . . . . . . . . . . . . . 11 7.1.2. Send scheduling. . . . . . . . . . . . . . . . . . 11 7.2. Downstream cell scheduling. . . . . . . . . . . . . . . . 11 7.2.1. Recieve scheduling . . . . . . . . . . . . . . . . 11 7.2.2. Send scheduling. . . . . . . . . . . . . . . . . . 11 7.3. Upstream and Downstream Scheduling. . . . . . . . . . . . 12 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . . 12 9. Security Considerations . . . . . . . . . . . . . . . . . . . 12 10. Acknowlegement. . . . . . . . . . . . . . . . . . . . . . . . 12 11. References. . . . . . . . . . . . . . . . . . . . . . . . . . . 13 11.1. Normative References. . . . . . . . . .. . . . . . . . . 13 11.2. Informative References. . . . . .. . . . . . . . . . . 13 Authors' Addresses . . . . . . . . . . . . . . . . . . . . .. . . . 14 Kim, et al. Expires June 17, 2017 [page 2] Internet-Draft ALICE December 2016 1. Introduction In the communication using TSCH, multiple channels can be used simultaneously and channel hopping is used. It is different from traditional ZigBee communication. With increasing interest on IoT network, various TSCH cell scheduling method has been provided. This document describes the limitation of present TSCH cell scheduling methods which mainly use centralized or decentralized approach. It firstly overview pros and cons of various cell scheduling approaches including centralized, decentralized and autonomous TSCH cell scheduling methods. Specifically, this document focus on autonomous approach. The biggest benefits of autonomous scheduling method is its simple and light scheduling without any negotiation and its quick response to the sudden network changes. This document also suggest design considerations on devising autonomous scheduling approach to avoid unexpected confliction and increase channel utilization. For the last, it provides one example that reflects all design considerations mentioned: Autonomous Link- based TSCH Cell Scheduling (ALICE). 2. Requirements Language The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in RFC 2119 [RFC 2119]. 3. Terminology Cell : This document follows the same definition used in [RFC 7554] ASN : This document follows the same definition used in [RFC 7554] Slotframe : This document follows the same definition used in [RFC 7554] LinkNum : In the IoT sensor network, nodes and links form a graph and each link has a node at both ends. LinkNum of specific link is defined as the sum of NodeIDs of two connected nodes with that link. SlotframeID : ID of the slotframe in the TSCH network. 4.TSCH cell scheduling Regarding TSCH cell scheduling, detailed description is provided in [RFC 7554]. Here, we briefly overview important characteristics used in this document. Kim, et al. Expires June 17, 2017 [page 3] Internet-Draft ALICE December 2016 chOff ^ Slotframe | - +-----------------------------------------+ | | | B | | | | | | +-----------------------------------------+ | | | | C | | | | M | +-----------------------------------------+ | | | F | | | D,G | | | +-----------------------------------------+ | | A | | | | | E | _ +-----------------------------------------+---> Time ___________________________________________ Z Figure 1: Structure of TSCH slotframe In the communication using TSCH, multiple channels can be used simultaneously and channel hopping is used. It is different from traditional ZigBee communication. In TSCH, slotframe repeats over time and the slotframe length is defined as the number of time offsets. In Figure 1, one example of TSCH slotframe is described. In this example, the number of channel offsets is M=4 and the number of time offsets is Z=6. Z is also a slotframe length. The total number of cells that is available in a slotframe is M*Z=24. In the example, only 6 cells are scheduled in the slotframe. If two closely located nodes try to send packets in the same cell, it will conflict and the transmission of the both users will fail. So to avoid confliction while achieving high channel utilization and energy efficiency, wise and canny scheduling method should be used in TSCH cell scheduling. Present method can be mainly categorized by two major approaches: Centralized and decentralized scheduling. 4.1. Centralized approach In the IoT sensor network using centralized TSCH cell scheduling approach, one representative node schedules wakeup and sleep of every node in the same network. Since only one node schedules the whole communication in the network, for that node, large amount of information is needed. Depending on the algorithm, various information can be used and an optimized scheduling can be realized. However, since only one specific node can execute TSCH cell scheduling, quick action cannot be executed when the network topology has been changed suddenly. Moreover, every node has to deliver the information that will be used in the scheduling node, which causes communication overhead using additive energy and bandwidth resources. Furthermore, centralized approach takes long time for the initialization. * We categorize following kinds of scheduling as centralized approach. Kim, et al. Expires June 17, 2017 [page 4] Internet-Draft ALICE December 2016 The network is divided into multiple regions. In each region, one centralized scheduler executes centralized TSCH cell scheduling for every node located in the same region with that node. In this network, though multiple schedulers execute TSCH cell scheduling, it is not fully decentralized manner. Rather, it can be viewed as a combination of multiple centralized scheduling. 4.2. Decentralized approach In the IoT sensor network using decentralized TSCH cell scheduling approach, every node can schedule their own plan for wakeup and sleep time. Each node communicate with their neighbors to avoid confliction caused by simultaneous same channel usage among interfering nodes. To implement this network, specific negotiation protocol should be decided. Compared to the centralized approach, each node using the decentralized TSCH cell scheduling approach needs only small amount of information received from their close neighbors. As a result, it is robust for a sudden network change compared to the centralized approach. However, because of the scanty information, decentralized approach lacks visibility on the view of the whole network. 4.3. Autonomous approach Though decentralized approach shows quick response for the sudden changes of network topology, it still needs additive communication for the negotiation between neighbors. In the autonomous approach, no negotiation is needed for the TSCH scheduling. One representative method has been proposed in [Orchestra-Sensys15]. They only use information received from RPL routing protocol [RFC 6550]. They do not use additive communication for the negotiation among the neighbors in TSCH cell scheduling. They autonomously calculate their own plan on cell usage based on the RPL structure. They use NodeID such as MAC address of their RPL parent node. With this method, node-based cell scheduling is executed. For example, in the receiver-based scheduling, receiving nodes are scheduled on the TSCH cells. Scheduled node listen at the corresponding cell and any node who wants to send packet to that node wakeup and send packet to the receiving node at the same cell. Sender-based scheduling executes in the similar manner. Including the above method [Orchestra-Sensys15], though autonomous TSCH cell scheduling approach also lacks other available information, the biggest benefits of this approach is its simple and light scheduling without any negotiation and its quick response to the sudden network changes. Kim, et al. Expires June 17, 2017 [page 5] Internet-Draft ALICE December 2016 5. Design considerations of autonomous TSCH cell scheduling method This section describes the design considerations for autonomous TSCH cell scheduling. In the design of TSCH cell scheduling, one of the biggest challenge is to make scheduling by avoiding confliction among interfering nodes. However, since autonomous scheduling does not use any negotiation, it lacks information. In this condition, the thing that autonomous scheduler can do is to reduce the probability of confliction. +---+ | A | +---+ / \ / \ +---+ +---+ | B | | C | +---+ +---+ / \ / \ / \ / \ +---+ +---+ +---+ +---+ | D | | E | | F | | G | +---+ +---+ +---+ +---+ / \ / \ / \ / \ H I J K L M N O Figure 2: Nodes and Links in the Tree Topology 5.1. Link-based scheduling Consideration 1: One node cannot receive packets from the two different nodes simultaneously at the same timeslot. For example, in the topology described in Figure 2, in the upstream transmission, node B is connected to both node D and node E. If these two child nodes send packets to the node B at the same timeslot, B will fail to listen both two packets successfully. In this situation, the link D-B and the link E-B can be scheduled in the same channel offset or in the different channel offsets. In the former case, if two child node sends packet simultaneously at the same time offset, two transmission will be conflict at the same channel and B cannot receive any packet. In the latter case, depending on the node B's selection of the channel offset to listen at, one of the packets sent from the node A or the node B can be received successfully. Kim, et al. Expires June 17, 2017 [page 6] Internet-Draft ALICE December 2016 5.2. Hop-count-based scheduling Consideration 2: One node cannot listen and send packets simultaneously at the same timeslot. For example, in the topology described in Figure 2, in the upstream, node B is connected to both node A and node D. If the link B-A and the link D-B is scheduled at the same timeslot, node D will send to the node B and the node B will send to the node A. However, node D cannot listen and send simultaneously at the same timeslot. 5.3. SlotfrmaeID Consideration 3: In the view of one specific node, the scheduling of different slotframes should be changed to avoid consistent confliction. If the scheduling result for a slotframe persists, the conflicting nodes in a cell will conflict again at the next slotframe. For example, in the topology described in Figure 2, in the upstream, there are two links B-A and C-A. If these links are scheduled in the same cell and node B and node C send packets to the node A at the same timeslot, two packet transmissions will fail. If this scheduling persist at the next slotframe, the same situation will occur again. 5.4. Upstream: link-based, Downstream: node-based Consideration 4: Cell scheduling method of upstream and downstream should be differentiated. In the case of IoT network, the amount of upstream traffic is much larger than that of downstream traffic. Moreover, if tree topology is used for the routing protocol as described in Figure 2, one node has multiple child nodes and only one parent node. In this structure, in the case of upstream, every child node has different packets to send to their parent node. So one node should listen from their multiple child using different cells. However, in the case of downstream, the server may request or respond to every node in the network or to the one specific node. Moreover, the amount of downstream packets are smaller than that of upstream packets and the scheduled cell for downstream may not be used with high probability. So, in the topology described in Figure 2, when the link B-D and the link B-E is scheduled, scheduling these two links at the same cell is more efficient than scheduling these links at the different cells. By doing this, in the case where the server sends one packet to every node in the network, node B can forward this message to all their child nodes at only one transmission. In the other case where the node B sends a packet to one of its child nodes, it can send the packet to the specific node while multiple child nodes listen at the same timeslot. Kim, et al. Expires June 17, 2017 [page 7] Internet-Draft ALICE December 2016 5.5. Upstream downstream scheduling Consideration 5: One node cannot receive or send packets from both their parent node and child node simultaneously. In other words, in the view of one specific node, upstream and downstream can not be happen at the same timeslot. For example, in the topology described in Figure 2, the node B is connected to both node A and node D. If both node A and node D is scheduled to send packets to the node B at the same timeslot, or the node B is scheduled to send packets to the node A and the node D at the same timeslot as a result of cell calculation by using autonomous scheduling method, at least one transmission will fail since node B cannot receive different packets from the different nodes and send different packets to the different nodes. 6. ALICE overview In this section, we define Autonomous LInk-based tsch CEll scheduling (ALICE). This scheduling method reflects 5 design considerations described above. To use autonomous scheduling approach, ALICE utilizes limited information on the basis of RPL routing topology as shown in [Orchestra-Sensys15]. By using all 3 types of RPL messages (DIS, DIO and DAO), each node using ALICE knows NodeID (e.g. MAC address) of their parent and child nodes. They use another information such as Absolute Slot Number (ASN) and RPL hop-count. chOff ^ Slotframe | Even Rank || Odd Rank | - +--------------------||--------------------+ | | L->F | C->A | M->F || F->C | | | | | | | || | | | | +--------------------||--------------------+ | | I->D | | J->E || | G->C | | | | | | O->G || | | | M | +--------------------||--------------------+ | | | H->D | || | D->B | | | | | | || | | | | +--------------------||--------------------+ | | B->A | | N->G || | | E->B | | | K->E | | || | | | - +--------------------||--------------------+---> Time |__________________________________________| Z Figure 3: Autonomous Link-based TSCH Cell Scheduling (ALICE) Kim, et al. Expires June 17, 2017 [page 8] Internet-Draft ALICE December 2016 6.1. Link-based scheduling In ALICE, the tree topology is used for the routing protocol as RPL is used together with TSCH. In its TSCH cell scheduling, every link in the tree topology is scheduled at least once a slotframe. For example, in Figure 2, there are 13 links and each link is scheduled in a cell in a slotframe as described in Figure 3. Since ALICE uses link-based scheduling, we allocate LinkNum to every link. LinkNum is the sum of NodeIDs of two connected nodes with that link. For example, in the Figure 2, node A and node B is connected with the link A-B. Then, LinkNum of the link A-B is the sum of NodeID of node A and that of node B. By using the value of LinkID, nodes in the network autonomously calculate their plan for wakeup and sleep time. 6.2. Hop-count-based scheduling By using hop-count-based scheduling, ALICE avoids the situation where one node listens and sends simultaneously. With RPL, every node knows their own hop-count. In this document, we call hop-count as rank. Multiple cells in a slotframe is grouped into two different sections. Even rank nodes are scheduled in the cells in the first section and the odd rank nodes are scheduled in the the cells in the second section. 6.3. SlotframeID In ALICE scheduling, every slotframe has different cell scheduling results since ALICE uses SlotframeID in their autonomous scheduling algorithm. SlotframeID increases with time. SlotframeID is calculated by flooring ASN%Z. SlotframeID = floor(ASN%Z) As Figure 4 describes, as SlotframeID changes, the result of cell scheduling becomes completely different. ^ chOff | +-----------------------------------------------+ | | B | | | | |F | | |D | | | +-----------------------------------------------+ | | |C | | | | |A | | | | | +-----------------------------------------------+ | | F | | |D,G| | | | | |E | | +-----------------------------------------------+ #chOff=0 |A | | | | |E |C | |B | | |G | +-----------------------------------------------+-->Time |-----------------------|-----------------------| Z Z Figure 4: Differenct slotframes have different cell scheduling results Kim, et al. Expires June 17, 2017 [page 9] Internet-Draft ALICE December 2016 6.4. Upstream: link-based, Downstream: node-based ALICE uses different scheduling style for uplink and downlink streams. For the upstream, it has link-based scheduling approach and for the downstream, it has node-based scheduling approach as [Orchestra-Sensys15]. 6.5. Upstream downstream scheduling Since the amount of upstream traffic is much more than that of downstream traffic, ALICE give more chance for the upstream traffic compared to the downstream traffic in its cell scheduling. For example, with the length K for a slotframe-cycle, K-1 slotframes are allocated for the upstream and 1 slotframe is allocated for the downstream. More specific example is described in Figure 5. If K=3, 2 slotframes are allocated for the upstream and 1 slotframe is allocated for the downstream. ^ [ K=3 ] chOff | +-----------+-----------+-----------++-----------+-- | | B | | | C | D | C | | B || A | | E | +------------------------------------------------+-- | E | C | | |A,B| | E | | A || | C | | +------------------------------------------------+-- 0 | A | | D | E | | | | D | || | B | D | +-----------+-----------+-----------++-----------+---->Time |-----Z-----+-----Z-----|-----Z-----||-----Z-----|-- |........uplink.........|..downlink.||......uplink.. |______________1cycle_______________||______1cycle__ Figure 5: Upstream and Downstream Scheduling 7. ALICE details In this section, we define ALICE scheduling details. In the network with ALICE, every node has ALICE scheduler and calculates specific cells for send or receive packets autonomously on the basis of LinkNum, SlotframeID and Rank. As defined above, LinkNum of one link is defined on the basis of NodeID of two nodes that is connected with that link. SlotframeID is on the basis of ASN. To calculate the specific ChannelOffset and the TimeOffset, ALICE uses hash function as [Orchestra-Sensys15] does. Here, we use M and Z for the number of channel offsets and the number of time offsets in a slotframe, respectively. Kim, et al. Expires June 17, 2017 [page 10] Internet-Draft ALICE December 2016 7.1. Upstream cell scheduling In the upstream traffic, a node receives packets from its child nodes and sends packet to its parent node. Upstream cell scheduling is done only in the upstream period. 7.1.1. Receive Scheduling TimeOffset = (NodeRank%2)*(Z/2) +Hash(NodeID+ChildID+SlotframeID) %(Z/2) ChannelOffset = Hash(ChildID+SlotframeID)%M 7.1.2. Send Scheduling TimeOffset = (ParentRank%2)*(Z/2) + Hash(ParentID+NodeID+SlotframeID) %(Z/2) ChannelOffset = Hash(NodeID+SlotframeID)%M 7.2. Downstream cell scheduling In the downstream traffic, a node receives packet from its parent node and sends packet to its child nodes. Downstream cell scheduling is done only in the downstream period. 7.2.1. Receive Scheduling TimeOffset = (ParentRank%2)*(Z/2) + Hash(ParentID+SlotframeID)%(Z/2) ChannelOffset = Hash(ParentID+SlotframeID)%M 7.2.2. Send Scheduling TimeOffset = (NodeRank%2)*(Z/2) + Hash(NodeID+SlotframeID)%(Z/2) ChannelOffset = Hash(NodeID+SlotframeID)%M Kim, et al. Expires June 17, 2017 [page 11] Internet-Draft ALICE December 2016 7.3. Upstream and Downstream Scheduling K is the number of slotframes in a group that is composed multiple slotframes during a pair of one upstream period and one downstream period. In other words, in each cycle, one downstream period and one upstream period are shown. Since the amount of upstream traffic is much more than that of downstream traffic, the number of cells for the upstream traffic should be larger than that of downstream traffic. Since the number of cells in a timeslot does not change, longer time is allocated for the upstream period compared to downstream period. During the upstream period, upstream cell scheduling is executed and during the downstream period, downstream cell scheduling is executed. Decision of upstream and downstream period is simple as follows. The algorithm is on the basis of SlotframeID and the parameter K. If (SlotframeID%K==0) Downstream period Else Upstream period End 8. IANA Considerations There are no IANA considerations related to this document. 9. Security Considerations Autonomous TSCH cell scheduling method has similar requirements on security as [RFC7554]. 10. Acknolwedgement This work was supported by Institute for Information & communications Technology Promotion(IITP) grant funded by the Korea government(MSIP) (No.B0190-16-2017,Resilient/Fault-Tolerant Autonomic Networking Based on Physicality, Relationship and Service Semantic of IoT Devices), the MSIP(Ministry of Science, ICT and Future Planning), Korea, under the ITRC(Information Technology Research Center) support program (IITP-2016-R0992-16-1023) supervised by the IITP(Institute for Information & communications Technology Promotion and the National Research Foundation of Korea(NRF) Grant funded by the Korean Government(MSIP) (No.2016R1A5A1012966). Kim, et al. Expires June 17, 2017 [page 12] Internet-Draft ALICE December 2016 11. Reference 11.1. Normative References [RFC 7554] T. Watteyne, Ed., L. Grieco, "Using IEEE 802.15.4e Time-Slotted Channel Hopping (TSCH) in the Internet of Things (IoT): Problem Statement", RFC 7554, May 2015 [RFC 6550] T. Winter, Ed., P. Thubert, Ed., A. Brandt, J. Hui, R. Kelsey, P. Levis, K. Pister, R. Struik, JP. Vasseur, R. Alexander, "RPL: IPv6 Routing Protocol for Low-Power and Lossy Networks", RFC 6550, March 2012 11.2. Informative References [Orchestra-Sensys15] Duquennoy, Simon, et al. "Orchestra: Robust mesh networks through autonomously scheduled TSCH." Proceedings of the 13th ACM Conference on Embedded Networked Sensor Systems. ACM, 2015. Kim, et al. Expires June 17, 2017 [page 13] Internet-Draft ALICE December 2016 Authors' Addresses Seo Hyang Kim Department of Computer Science and Engineering Seoul National University Seoul, South Korea Phone: +82 (0)2 880 1858 Email: shkim@popeye.snu.ac.kr Na Eon Kim Department of Computer Science and Engineering Seoul National University Seoul, South Korea Phone: +82 (0)2 880 1858 Email: nekim@popeye.snu.ac.kr Nguyen Duc Lam Department of Computer Science and Engineering Seoul National University Seoul, South Korea Phone: +82 (0)2 880 1858 Email: lam@popeye.snu.ac.kr Chong Kwon Kim Department of Computer Science and Engineering Seoul National University Seoul, South Korea Phone: +82 (0)2 880 1858 Email: ckim@snu.ac.kr Kim, et al. Expires June 17, 2017 [page 14]