[Docs] [txt|pdf|xml|html] [Tracker] [Email] [Nits]
Versions: 00 01
6TiSCH S. Duquennoy, Ed.
Internet-Draft Inria
Intended status: Standards Track X. Vilajosana
Expires: January 4, 2018 Universitat Oberta de Catalunya
T. Watteyne
Inria
July 3, 2017
6TiSCH Autonomous Scheduling Function (ASF)
draft-duquennoy-6tisch-asf-00
Abstract
This document defines a Scheduling Function called "ASF": the 6TiSCH
Autoonomous Scheduling Function. With ASF, nodes maintain their TSCH
schedule based on local neighborhood knowledge, without any
signaling. Hashes of the nodes' MAC address are used to
deterministically derive the [slotOffset,channelOffset] location of
cells in the TSCH schedule. The MAC, control, and application
traffic planes are assigned to distinct slotframes, for isolation and
flexible dimensioning. This approach provides over-provisioned
schedules with low maintenance, in pursuit for simplicity rather than
optimality.
Requirements Language
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
"OPTIONAL" in this document are to be interpreted as described in RFC
2119 [RFC2119].
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 January 4, 2018.
Duquennoy, et al. Expires January 4, 2018 [Page 1]
Internet-Draft 6TiSCH Autonomous Scheduling Function (ASF) July 2017
Copyright Notice
Copyright (c) 2017 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. TEMPORARY EDITORIAL NOTES . . . . . . . . . . . . . . . . . . 3
2. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 3
2.1. Application Domains . . . . . . . . . . . . . . . . . . . 3
3. General Operation . . . . . . . . . . . . . . . . . . . . . . 4
3.1. Types of Slotframes . . . . . . . . . . . . . . . . . . . 4
3.2. Cell Coordinates . . . . . . . . . . . . . . . . . . . . 4
3.3. Slotframes Definition . . . . . . . . . . . . . . . . . . 5
4. Configuration . . . . . . . . . . . . . . . . . . . . . . . . 5
5. Scheduling Function Identifier . . . . . . . . . . . . . . . 6
6. Rules for Adding/Deleting Cells . . . . . . . . . . . . . . . 6
7. Rules for CellList . . . . . . . . . . . . . . . . . . . . . 7
8. 6P Timeout Value . . . . . . . . . . . . . . . . . . . . . . 7
9. Rule for Ordering Cells . . . . . . . . . . . . . . . . . . . 7
10. Meaning of the Metadata Field . . . . . . . . . . . . . . . . 7
11. Node Behavior at Boot . . . . . . . . . . . . . . . . . . . . 8
12. 6P Error Handling . . . . . . . . . . . . . . . . . . . . . . 8
13. Examples . . . . . . . . . . . . . . . . . . . . . . . . . . 8
14. Implementation Status . . . . . . . . . . . . . . . . . . . . 8
15. Security Considerations . . . . . . . . . . . . . . . . . . . 9
16. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 9
16.1. 6P Scheduling Function Identifiers 'ASF' . . . . . . . . 9
17. References . . . . . . . . . . . . . . . . . . . . . . . . . 9
17.1. Normative References . . . . . . . . . . . . . . . . . . 9
17.2. Informative References . . . . . . . . . . . . . . . . . 9
Appendix A. Contributors . . . . . . . . . . . . . . . . . . . . 10
Appendix B. Acknowledgments . . . . . . . . . . . . . . . . . . 10
Appendix C. [TEMPORARY] Changelog . . . . . . . . . . . . . . . 10
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 11
Duquennoy, et al. Expires January 4, 2018 [Page 2]
Internet-Draft 6TiSCH Autonomous Scheduling Function (ASF) July 2017
1. TEMPORARY EDITORIAL NOTES
This document is an Internet Draft, so work-in-progress by nature.
It contains the following work-in-progress elements:
o "TODO" statements are elements which have not yet been written by
the authors for some reason (lack of time, ongoing discussions
with no clear consensus, etc). The statement does indicate that
the text will be written at some point.
o "TEMPORARY" appendices are there to capture current ongoing
discussions, or the changelog of the document. These appendices
will be removed in the final text.
o "IANA_*" identifiers are placeholders for numbers assigned by
IANA. These placeholders are to be replaced by the actual values
they represent after their assignment by IANA.
o "RFCXXXX" refers to the RFC number of this specification, once
published.
o The string "REMARK" is put before a remark (questions, suggestion,
etc) from an author, editor or contributor. These are on-going
discussions at the time of writing, and will not be part of the
final text.
o This section will be removed in the final text.
2. Introduction
This document defines an autonomous Scheduling Function for the 6top
sublayer [I-D.ietf-6tisch-6top-protocol], called "ASF". It is
designed to operate without any signaling, keeping the TSCH schedule
consistent between neighbors at all times (matching slots for
transmission and reception). ASF uses 6P for neighbor schedule
inspection (commands STATUS and LIST), but not for adding/deleting
cells. ASF isolates the traffic from different planes in distinct
slotframes, so as to avoid any disruption between MAC
synchronization, control and application traffic.
ASF addresses all requirements listed in Section "Requirements for an
SF" from [I-D.ietf-6tisch-6top-protocol]. The organization of this
document follows section "Recommended Structure of an SF
Specification" in [I-D.ietf-6tisch-6top-protocol]. This document
follows the terminology defined in [I-D.ietf-6tisch-terminology].
2.1. Application Domains
ASF is primarily targeted at applications with random traffic flows,
such as interactive CoAP traffic. Its main strength is its
signaling-free nature, which ensures the slots installed at
neighboring nodes are consistent at all times. Its main weakness is
its contention-based nature and its need to over-provision the
Duquennoy, et al. Expires January 4, 2018 [Page 3]
Internet-Draft 6TiSCH Autonomous Scheduling Function (ASF) July 2017
schedule, rendering it unable to meet stringent latency and energy
requirements. An example application domains is building
instrumentation. ASF was evaluated experimentally and shown to
achieve over 99.99% end-to-end delivery in 6TiSCH/RPL testbeds
[Orchestra-SenSys].
3. General Operation
ASF uses multiple slotframes, each assigned to one particular type of
traffic, e.g. TSCH synchronization, routing control or application
traffic. Nodes maintain the cells within the slotframes
autonomously, based on the hash of either the source's or
destination's MAC address. Each slotframe is uniquely assigned a set
of channel offsets.
3.1. Types of Slotframes
There are three different types of slotframes, decribed next:
Rendez-vous slotframe: Contains a contention-based rendez-vous cell
with fixed coordinates, options Rx, Tx, and Shared. The cell can
be used for any type of traffic, including broadcast. This
slotframe is equivalent to the 6TiSCH minimal schedule [RFC8180].
Receiver-based slotframe: Nodes have one receive (option Rx) cell at
coordinates derived from a hash of their MAC address. For
transmitting to a given neighbor, nodes maintain a cell (options
Tx, Shared) at coordinates derived from a hash of the neighbor's
MAC address. For instance, a node may maintain such a transmit
cell for each known neighbor in the IPv6 NDP cache, or to a subset
such as the RPL preferred parent(s) or TSCH time source(s).
Sender-based slotframe: Nodes have one transmit cell (options Tx,
Shared) at coordinates derived from a hash of their MAC address.
To listen to a given neighbor, they maintain a cell (option Rx) at
coordinates derived from a hash of the neighbor's MAC address.
Typically, nodes only listen to a subset of neighbors, such as the
RPL preferred parent(s) or TSCH time source(s).
3.2. Cell Coordinates
Cell coordinates in ASF are either fixed (for rendez-vous slotframes)
or derived from a MAC address (for receiver- and sender-based
slotframes). To derive coordinates from a MAC address, nodes MUST
use the hash function SAX [SAX-DASFAA] on the EUI-64. Let S_len be
the length of slotframe S, and S_channels be the set of channels
assigned to slotframe S. The slot coordinates derived from a given
MAC address are computed as follows:
slotOffset(MAC) = hash(MAC) % S_len
Duquennoy, et al. Expires January 4, 2018 [Page 4]
Internet-Draft 6TiSCH Autonomous Scheduling Function (ASF) July 2017
channelOffset(MAC) = S_channels[(hash(MAC) / L) % len(S_channels)]
3.3. Slotframes Definition
By default, nodes maintain the four following slotframes:
SlotframeA: TSCH Enhanced Beacons: Nodes MUST send all TSCH Enhanced
Beacons (EBs) on this slotframe. This is a sender-based
slotframe. Nodes have one transmit cell based on their MAC
address, and listen to their TSCH time source with one receive
cell (with additional option TimeKeeping).
SlotframeB: TSCH Keep-Alives: Nodes MUST send all Keep-Alives (KAs)
on this slotframe. This is a receiver-based slotframe. Nodes
have one receive cell based on their MAC address, and one transmit
cell towards their TSCH time source (with additional option
TimeKeeping).
SlotframeC: Application traffic: Nodes MUST send all unicast UDP and
TCP frames in this slotframe. This is a received-based slotframe.
Nodes have one receive cell based on their MAC address, and
maintain as many transmit cells as they have neighbors in their
IPv6 NDP cache. Every time a node is added/removed to the NDP
cache, a new transmit cell is immediatly added/removed.
SlotframeD: Other Traffic: Nodes MUST send all other traffic to this
slotframe, such as 6P or ICMPv6 traffic. This is a rendez-vous
slotrame. All nodes have one single cell at slotOffset 0 and at
the first channel offset of the slotframe.
As the slotframes repeat over time, cells from different slotframes
will overlap periodically. In case a node has multiple cells
schedule at the same time, the precedence rules from
[IEEE802154-2015] apply.
In order to fully isolate the different planes, we RECOMMEND
provisioning separate packet queues for each slotframe. This ensures
that transient bursts at the application layer will not affect TSCH
synchronization nor routing topology maintenance. Conversely,
occasional routing or TSCH traffic will not affect each other nor
affect the application.
4. Configuration
ASF defines a set of configuration parameters listed in Figure 1. In
order to distribute cell overlap uniformly (see Section 3.3), we
RECOMMEND selecting slotframe lengths that are co-primes. TODO
define how configuration is discovered. Can be through new EB IEs,
or through new/extended 6P command(s).
Duquennoy, et al. Expires January 4, 2018 [Page 5]
Internet-Draft 6TiSCH Autonomous Scheduling Function (ASF) July 2017
+--------------------------------+----------------------------------+
| Property | Example Setting |
+--------------------------------+----------------------------------+
| SlotframeA length | 397 |
+--------------------------------+----------------------------------+
| SlotframeA handle | 4 (lowest precedence) |
+--------------------------------+----------------------------------+
| SlotframeA channelOffsets | 0 |
+--------------------------------+----------------------------------+
| SlotframeA type of cells | ADVERTISING |
+--------------------------------+----------------------------------+
| SlotframeB length | 389 |
+--------------------------------+----------------------------------+
| SlotframeB handle | 0 (highest precedence) |
+--------------------------------+----------------------------------+
| SlotframeB channelOffsets | 1 |
+--------------------------------+----------------------------------+
| SlotframeB type of cells | NORMAL |
+--------------------------------+----------------------------------+
| SlotframeC length | Trades-off app. traffic capacity |
| | against energy. Ex. value: 17 |
+--------------------------------+----------------------------------+
| SlotframeC handle | 1 |
+--------------------------------+----------------------------------+
| SlotframeC channelOffsets | 2 to 14 |
+--------------------------------+----------------------------------+
| SlotframeA type of cells | NORMAL |
+--------------------------------+----------------------------------+
| SlotframeD length | 31 |
+--------------------------------+----------------------------------+
| SlotframeD handle | 2 |
+--------------------------------+----------------------------------+
| SlotframeD channelOffsets | 15 |
+--------------------------------+----------------------------------+
| SlotframeD type of cells | NORMAL |
+--------------------------------+----------------------------------+
Figure 1: Example Settings for ASF.
5. Scheduling Function Identifier
The Scheduling Function Identifier (SFID) of ASF is IANA_SFID_ASF.
6. Rules for Adding/Deleting Cells
ASF nodes maintain their cells autonomously, and do not use 6P ADD
nor DELETE.
Duquennoy, et al. Expires January 4, 2018 [Page 6]
Internet-Draft 6TiSCH Autonomous Scheduling Function (ASF) July 2017
7. Rules for CellList
For the 6P LIST command, ASF uses the default CellList field format
defined in Section 4.2.4 [TODO: update if needed] of
[I-D.ietf-6tisch-6top-protocol].
8. 6P Timeout Value
The timeout is of low criticality in ASF as 6P Requests are only used
for schedule inspection, not for cell addition/removal. The
RECOMMENDED timeout value in slots is:
2^(macMaxBe+2)*SlotframeD_len
which is an upper bound of the maximum time spent in transmission
attempts of a 6P Request and Response, over slotframeD (where 6P
traffic is sent). The upper bound is conservative, giving extra time
for time spent in packet queues.
Assuming default values ([IEEE802154-2015] and Figure 1), that is
macMaxBe==5 and Slotframe2_len==31, this results in a timeout of 3968
timeslots.
9. Rule for Ordering Cells
Cells are ordered by increasing slotframe handle, then by timeslot,
then channel offset.
10. Meaning of the Metadata Field
The Metadata 16-bit field is used as follows: Figure Figure 2 shows
the format of the Metadata field, where:
o Slotframe: is used to identify a slotframe by its handle.
o BITS 8-15 are reserved.
1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Slotframe | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 2: Format of the Metadata Field.
Duquennoy, et al. Expires January 4, 2018 [Page 7]
Internet-Draft 6TiSCH Autonomous Scheduling Function (ASF) July 2017
11. Node Behavior at Boot
At boot, ASF creates four empty slotframes with length and handle
described in Section 4.
TODO describe configuration discovery.
12. 6P Error Handling
ASF only uses 6P commands COUNT and LIST. In case of error on STATUS
or LIST, the node MAY retry to contact this neighbor after the 6P
timeout.
13. Examples
TODO
14. Implementation Status
This section records the status of known implementations of the
protocol defined by this specification at the time of posting of this
Internet-Draft, and is based on a proposal described in [RFC6982].
The description of implementations in this section is intended to
assist the IETF in its decision processes in progressing drafts to
RFCs. Please note that the listing of any individual implementation
here does not imply endorsement by the IETF. Furthermore, no effort
has been spent to verify the information presented here that was
supplied by IETF contributors. This is not intended as, and must not
be construed to be, a catalog of available implementations or their
features. Readers are advised to note that other implementations may
exist.
According to [RFC6982], "this will allow reviewers and working groups
to assign due consideration to documents that have the benefit of
running code, which may serve as evidence of valuable experimentation
and feedback that have made the implemented protocols more mature.
It is up to the individual working groups to use this information as
they see fit".
Contiki: The mechanism behind this specification is implemented in
the Contiki project [Contiki]. Adjustments to exactly match this
specification are in progress. The mechanism was evaluated
experimentally in large-scale testbeds in [Orchestra-SenSys].
Duquennoy, et al. Expires January 4, 2018 [Page 8]
Internet-Draft 6TiSCH Autonomous Scheduling Function (ASF) July 2017
15. Security Considerations
ASF is not threatened by attacks on 6P messages as it operates
without signaling. However, it bases its TSCH schedule on external
information, namely: (1) the identify of the current TSCH time source
and (2) the MAC address of its neighbors. ASF relies on link-layer
security to ensure the integrity of the above information.
16. IANA Considerations
16.1. 6P Scheduling Function Identifiers 'ASF'
This document adds the following number to the "6P Scheduling
Function Identifiers" registry defined by
[I-D.ietf-6tisch-6top-protocol]:
+----------------------+--------------------------------------+-----------+
| SFID | Name | Reference |
+----------------------+--------------------------------------+-----------+
| IANA_6TiSCH_SFID_ASF | Autonomous Scheduling Function (ASF) | TODO |
+----------------------+--------------------------------------+-----------+
Figure 3: 6P Scheduling Function Identifiers 'ASF'.
17. References
17.1. Normative References
[IEEE802154-2015]
IEEE standard for Information Technology, "IEEE Std
802.15.4-2015 Standard for Low-Rate Wireless Personal Area
Networks (WPANs)", December 2015.
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997,
<http://www.rfc-editor.org/info/rfc2119>.
17.2. Informative References
[Contiki] Dunkels, A., Lignan, A., Thebaudeau, B., Quattlebaum, R.,
Rosendal, F., Oikonomou, G., Deru, L., Alvira, M.,
Tsiftes, N., Schmidt, O., and S. Duquennoy, "The Contiki
Open Source OS for the Internet of Things",
https://github.com/contiki-os/contiki , November 2016.
Duquennoy, et al. Expires January 4, 2018 [Page 9]
Internet-Draft 6TiSCH Autonomous Scheduling Function (ASF) July 2017
[I-D.ietf-6tisch-6top-protocol]
Wang, Q., Vilajosana, X., and T. Watteyne, "6top Protocol
(6P)", draft-ietf-6tisch-6top-protocol-07 (work in
progress), June 2017.
[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-09 (work in
progress), June 2017.
[Orchestra-SenSys]
Duquennoy, S., Al Nahas, B., Landsiedel, O., and T.
Watteyne, "Orchestra: Robust Mesh Networks Through
Autonomously Scheduled TSCH", ACM SenSys 2015 , November
2015.
[RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running
Code: The Implementation Status Section", RFC 6982,
DOI 10.17487/RFC6982, July 2013,
<http://www.rfc-editor.org/info/rfc6982>.
[RFC8180] Vilajosana, X., Ed., Pister, K., and T. Watteyne, "Minimal
IPv6 over the TSCH Mode of IEEE 802.15.4e (6TiSCH)
Configuration", BCP 210, RFC 8180, DOI 10.17487/RFC8180,
May 2017, <http://www.rfc-editor.org/info/rfc8180>.
[SAX-DASFAA]
Ramakrishna, M. and J. Zobel, "Performance in Practice of
String Hashing Functions", DASFAA , 1997.
Appendix A. Contributors
Beshr Al Nahas (Chalmers University, beshr@chalmers.se) and Olaf
Landsiedel (Chalmers University, olafl@chalmers.se) contributed to
the design and evaluation of ASF.
Appendix B. Acknowledgments
TODO people
TODO projects
Appendix C. [TEMPORARY] Changelog
o draft-duquennoy-6tisch-asf-00
* Initial draft.
Duquennoy, et al. Expires January 4, 2018 [Page 10]
Internet-Draft 6TiSCH Autonomous Scheduling Function (ASF) July 2017
Authors' Addresses
Simon Duquennoy (editor)
Inria
40 Avenue Halley
Building A
Villeneuve d'Ascq
France
Email: simon.duquennoy@inria.fr
Xavier Vilajosana
Universitat Oberta de Catalunya
156 Rambla Poblenou
Barcelona, Catalonia 08018
Spain
Email: xvilajosana@uoc.edu
Thomas Watteyne
Inria
2 Rue Simone Iff
Paris
France
Email: thomas.watteyne@inria.fr
Duquennoy, et al. Expires January 4, 2018 [Page 11]
Html markup produced by rfcmarkup 1.129b, available from
https://tools.ietf.org/tools/rfcmarkup/