draft-ietf-6tisch-6top-sf0-00.txt   draft-ietf-6tisch-6top-sf0-01.txt 
6TiSCH D. Dujovne, Ed. 6TiSCH D. Dujovne, Ed.
Internet-Draft Universidad Diego Portales Internet-Draft Universidad Diego Portales
Intended status: Informational LA. Grieco Intended status: Informational LA. Grieco
Expires: November 13, 2016 Politecnico di Bari Expires: January 9, 2017 Politecnico di Bari
MR. Palattella MR. Palattella
University of Luxembourg University of Luxembourg
N. Accettura N. Accettura
University of California Berkeley University of California Berkeley
May 12, 2016 July 8, 2016
6TiSCH 6top Scheduling Function Zero (SF0) 6TiSCH 6top Scheduling Function Zero (SF0)
draft-ietf-6tisch-6top-sf0-00 draft-ietf-6tisch-6top-sf0-01
Abstract Abstract
This document defines a 6top Scheduling Function called "Scheduling This document defines a 6top Scheduling Function called "Scheduling
Function Zero" (SF0). SF0 dynamically adapts the number of reserved Function Zero" (SF0). SF0 dynamically adapts the number of reserved
cells between neighbor nodes, based on the currently allocated cells between neighbor nodes, based on the currently allocated
bandwidth and the neighbour nodes' requirements. Neighbor nodes bandwidth and the neighbour nodes' requirements. Neighbor nodes
negotiate in a distributed neighbor-to-neighbor basis the cell(s) to negotiate in a distributed neighbor-to-neighbor basis the cell(s) to
be added/deleted. SF0 uses the 6P signaling messages to add/delete be added/deleted. SF0 uses the 6P signaling messages to add/delete
cells in the schedule. Some basic rules for deciding when to add/ cells in the schedule. Some basic rules for deciding when to add/
skipping to change at page 2, line 4 skipping to change at page 2, line 4
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at http://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on November 13, 2016. This Internet-Draft will expire on January 9, 2017.
Copyright Notice Copyright Notice
Copyright (c) 2016 IETF Trust and the persons identified as the Copyright (c) 2016 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
skipping to change at page 3, line 7 skipping to change at page 3, line 7
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . 9
1. Introduction 1. Introduction
This document defines the Scheduling Function for the 6top sublayer This document defines the Scheduling Function for the 6top sublayer
[I-D.wang-6tisch-6top-sublayer] called "Scheduling Function Zero" [I-D.wang-6tisch-6top-sublayer] called "Scheduling Function Zero"
(SF0). (SF0).
This document addresses the requirements for a scheduling function This document addresses the requirements for a scheduling function
listed in [I-D.wang-6tisch-6top-sublayer], Section 4.2, and follows listed in [I-D.wang-6tisch-6top-sublayer], Section 4.2, and follows
the recommended outline from Section 4.3. the recommended outline from Section 4.3. This draft agrees with the
terminology defined on [I-D.ietf-6tisch-terminology] and is designed
within the context of [RFC7554]
2. Scheduling Function Identifier 2. Scheduling Function Identifier
The Scheduling Function Identifier (SFID) of SF0 is IANA_SFID_SF0. The Scheduling Function Identifier (SFID) of SF0 is IANA_SFID_SF0.
3. Rules for Adding/Deleting Cells 3. Rules for Adding/Deleting Cells
A node running SF0 determines when to add/delete cells in a three- A node running SF0 determines when to add/delete cells in a three-
step process: step process:
skipping to change at page 3, line 30 skipping to change at page 3, line 32
particular neighbor to determine how much bandwidth is required particular neighbor to determine how much bandwidth is required
to that neighbor (Section 3.2). to that neighbor (Section 3.2).
3. It applies the Allocation Policy to compare the number of 3. It applies the Allocation Policy to compare the number of
required cells to the number of already scheduled cells, and required cells to the number of already scheduled cells, and
determine the number of cells to add/delete (Section 3.3). determine the number of cells to add/delete (Section 3.3).
3.1. SF0 Triggering Events 3.1. SF0 Triggering Events
We RECOMMEND SF0 to be triggered at least by the following events: We RECOMMEND SF0 to be triggered at least by the following events:
1. If the Remaining Available Bandwidth (RAB) is less than the 1. If there is a change in the Current Outgoing Bandwidth Usage
Minimum Remaining Bandwidth (MRB) (COBU)
2. If there is any New Incoming Bandwidth Requirements from 2. If there is any New Incoming Bandwidth Requirements from
neighbour nodes (NIBR) neighbour nodes (NIBR)
This allows SF0 to be triggered by any change in local node bandwidth This allows SF0 to be triggered by any change in local outgoing
and/or incoming bandwidth. The exact mechanism of when SF0 is bandwidth and/or incoming bandwidth. A relocation request from the
triggered is implementation-specific. neighbour is considered as an Incoming Bandwidth Request, given that
it is expected to increase packet delivery rate on the relocated
cells, thus increasing the required bandwidth. The exact mechanism
of when SF0 is triggered is implementation-specific.
3.2. SF0 Bandwidth Estimation Algorithm 3.2. SF0 Bandwidth Estimation Algorithm
The Bandwidth Estimation Algorithm takes into account the sum of the The Bandwidth Estimation Algorithm takes into account the sum of the
incoming bandwidth requirements from the neighbour nodes and the used incoming bandwidth requirements from the neighbour nodes and also the
outgoing bandwidth. This allows the node to estimate the total current outgoing bandwidth value. This allows the node to estimate
outgoing bandwidth requirement. As a consequence, the Bandwidth the total outgoing bandwidth requirement. As a consequence, the
Estimation Algorithm for SF0 follows the steps described below: Bandwidth Estimation Algorithm for SF0 follows the steps described
below:
1. Collect the New Incoming Bandwidth Requirements from neighbour 1. Collect the New Incoming Bandwidth Requirements from neighbour
nodes (NIBR) nodes (NIBR)
2. Obtain the Current Outgoing Bandwidth Usage (COBU) 2. Obtain the Current Outgoing Bandwidth Usage (COBU)
3. Obtain the number of Current Scheduled Bandwidth (CSB) 3. Calculate the New Outgoing Bandwidth (NOB) as: NOB=COBU+NIBR
4. Calculate the New Outgoing Bandwidth (NOB) as: NOB=COBU+NIBR 4. Submit the request to the allocation policy
5. Calculate the Remaining Available Bandwidth (RAB) as RAB=CSB-NOB 5. Return to step 1 and wait for a triggering event.
6. If the RAB is less than the Minimum Remaining Bandwidth (MRB),
Add MRB to the NOB: NOB=NOB+MRB
7. Submit the request to the allocation policy
8. Return to step 1 and wait for a triggering event.
3.3. SF0 Allocation Policy 3.3. SF0 Allocation Policy
The "Allocation Policy" is the set of rules used by SF0 to decide The "Allocation Policy" is the set of rules used by SF0 to decide
when to add/delete cells to a particular neighbor to satisfy the when to add/delete cells to a particular neighbor to satisfy the
bandwidth requirements. bandwidth requirements.
SF0 uses the following parameters: SF0 uses the following parameters:
SCHEDULEDCELLS: The number of cells scheduled from the current node SCHEDULEDCELLS: The number of cells scheduled from the current node
to a particular neighbor. to a particular neighbor.
REQUIREDCELLS: The number of cells calculated by the Bandwidth REQUIREDCELLS: The number of cells calculated by the Bandwidth
Estimation Algorithm from the current node to that neighbor. Estimation Algorithm from the current node to that neighbor.
SF0THRESH: Threshold parameter introducing cell over-provisioning in SF0THRESH: Threshold parameter introducing cell over-provisioning in
the allocation policy. It is a non-negative value expressed as the allocation policy. It is a non-negative value expressed as
number of cells. The definition of this value is implementation- number of cells. The definition of this value is implementation-
specific; however, it is RECOMMENDED a SF0THRESH value of 3 cells. specific. A setting of SF0THRESH>0 will cause the node to
A setting of SF0THRESH>0 will cause the node to allocate at least allocate at least SF0THRESH cells to each of its' neighbours.
SF0THRESH cells to each of its' neighbours.
The SF0 allocation policy compares REQUIREDCELLS with SCHEDULEDCELLS The SF0 allocation policy compares REQUIREDCELLS with SCHEDULEDCELLS
and decides to add/delete cells taking into account SF0THRESH. This and decides to add/delete cells taking into account SF0THRESH. This
is illustrated in Figure 1. is illustrated in Figure 1.
SCHEDULEDCELLS SCHEDULEDCELLS
<---------------------------------> <--------------------------------->
+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+
| | | | | | | | | | | | | | | | | | | |
+---+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+---+
|<----------------->| |<--------->|
| SF0THRESH | | SF0THRESH |
| | | |
REQUIREDCELLS | | REQUIREDCELLS | |
+---+---+ | | DELETE +---+---+ | | DELETE
| | | | | ONE/MORE | | | | | ONE/MORE
+---+---+ | | CELLS +---+---+ | | CELLS
| | | |
REQUIREDCELLS | REQUIREDCELLS |
+---+---+---+---+---+---+ | DO +---+---+---+---+---+---+ | DO
| | | | | | | | NOTHING | | | | | | | | NOTHING
+---+---+---+---+---+---+ | +---+---+---+---+---+---+ |
| | | |
REQUIREDCELLS | REQUIREDCELLS |
+---+---+---+---+---+---+---+---+---+---+ ADD +---+---+---+---+---+---+---+---+---+---+ ADD
| | | | | | | | | | | ONE/MORE | | | | | | | | | | | ONE/MORE
+---+---+---+---+---+---+---+---+---+---+ CELLS +---+---+---+---+---+---+---+---+---+---+ CELLS
Figure 1: The SF0 Allocation Policy Figure 1: The SF0 Allocation Policy
1. If REQUIREDCELLS<(SCHEDULEDCELLS-SF0THRESH), delete one or more 1. If REQUIREDCELLS<(SCHEDULEDCELLS-SF0THRESH), delete one or more
cells. cells.
2. If (SCHEDULEDCELLS-SF0THRESH)<=REQUIREDCELLS<=SCHEDULEDCELLS, do 2. If (SCHEDULEDCELLS-SF0THRESH)<=REQUIREDCELLS<=SCHEDULEDCELLS, do
nothing. nothing.
skipping to change at page 6, line 7 skipping to change at page 6, line 7
be 9. be 9.
4. Rules for CellList 4. Rules for CellList
When issuing a 6top ADD Request, SF0 executes the following sequence: When issuing a 6top ADD Request, SF0 executes the following sequence:
Whitelist case: Whitelist case:
The Transaction Source node: Prepares the CellList field by The Transaction Source node: Prepares the CellList field by
selecting randomly the required cells, verifying that the slot selecting randomly the required cells, verifying that the slot
offset and channel offset are not occupied. offset and channel offset are not occupied and choose
channelOffset randomly for each cell.
The Transaction Destination node: Goes through the cells in the The Transaction Destination node: Goes through the cells in the
CellList in order, verifying whether there are no slotOffset CellList in order, verifying whether there are no slotOffset
conflicts. conflicts.
Blacklist case: Blacklist case:
The Transaction Source node: Prepares the CellList field by The Transaction Source node: Prepares the CellList field by
building a list of currently scheduled cells into the CellList. building a list of currently scheduled cells into the CellList.
The Transaction Destination node: Selects randomly the required The Transaction Destination node: Selects randomly the required
cells, verifying that the slot offset and channel offset are cells from the unallocated cells on the schedule, verifying
not occupied from the ones on the CellList. that the slot offset and channel offset are not occupied from
the ones on the CellList.
5. 6P Timeout Value 5. 6P Timeout Value
The 6P Timeout Value provided by SF0 allows the maximum number of The general timeout equals the equivalent time of the number of slots
TSCH link-layer retries. Given the TSCH parameters for the backoff until the next scheduled cell.
mechanism, macMinBE and macMaxBE, and the length in seconds of the
minimal Slotframe, SM, the timeout value is computed as: timeout =
(2^(macMaxBE+1)-2^macMinBE) * SM TODO: Change general timeout to a
timeout adapted to the schedule: SF to use the number of slots until
the next scheduled cell.
6. Meaning of Metadata Information 6. Meaning of Metadata Information
The Metadata 16-bit field is used as follows: The Metadata 16-bit field is used as follows:
BITS 0-7 [SLOTFRAME] are used to identify the slotframe number BITS 0-7 [SLOTFRAME] are used to identify the slotframe number
BITS 8-14 are RESERVED BITS 8-14 are RESERVED
BIT 15 [WBLIST] is used to indicate that the CellList provided is BIT 15 [WBLIST] is used to indicate that the CellList provided is
a Whitelist (value=0) or a Blacklist (value=1). a Whitelist (value=0) or a Blacklist (value=1).
TODO: length of the SlotFrame SHOULD be an integer multiple of the TODO: length of the SlotFrame SHOULD be an integer multiple of the
length of the minimal SlotFrame. length of the minimal SlotFrame.
7. Node Behavior at Boot 7. Node Behavior at Boot
In order to define a known state after the node is restarted, a CLEAR In order to define a known state after the node is restarted, a CLEAR
command is issued to each of the neighbour nodes to enable a new command is issued to each of the neighbour nodes to enable a new
allocation process. TODO: Temporary cells from a pool for the join allocation process. The 6P Initial Timeout Value provided by SF0
process. allows the maximum number of TSCH link-layer retries. Given the TSCH
parameters for the backoff mechanism, macMinBE and macMaxBE, and the
length in seconds of the minimal Slotframe, SM, the timeout value is
computed as: timeout = (2^(macMaxBE+1)-2^macMinBE) * SM
8. Relocating Cells 8. Relocating Cells
SF0 uses Packet Delivery Rate (PDR) statistics to monitor the SF0 uses Packet Delivery Rate (PDR) statistics to monitor the
currently allocated cells for cell re-allocation (by changing their currently allocated cells for cell re-allocation (by changing their
slotOffset and/or channelOffset) when it finds out that the PDR of slotOffset and/or channelOffset) when it finds out that the PDR of
one or more softcells below 20% of the average PDR. one or more softcells below 20% of the average PDR.
9. Forced Cell Deletion Policy 9. Forced Cell Deletion Policy
skipping to change at page 7, line 28 skipping to change at page 7, line 28
RC_SUCCESS: RC_SUCCESS:
If the number of elements in the CellList is the number of cells If the number of elements in the CellList is the number of cells
specified in the NumCells field of the 6P ALL Request, the specified in the NumCells field of the 6P ALL Request, the
operation is complete. The node does not take further action. operation is complete. The node does not take further action.
If the number of elements in the CellList is smaller (possibly 0) If the number of elements in the CellList is smaller (possibly 0)
than the number of cells specified in the NumCells field of the 6P than the number of cells specified in the NumCells field of the 6P
ALL Request, the neighbor has received the request, but less than ALL Request, the neighbor has received the request, but less than
NumCells of the cells in the CellList were. In that case, the NumCells of the cells in the CellList were. In that case, the
node MAY retry immediately with a different CellList if the amount node MAY retry immediately with a different CellList if the amount
of storage space permits, or build a new (random) CellList. of storage space permits, or build a new (random) CellList.
RC_ERR_VER: The node MUST NOT retry immediately. The node MAY add RC_VER_ERR: The node MUST NOT retry immediately. The node MAY add
the neighbor node on a blacklist. The node MAY retry to contact the neighbor node on a blacklist. The node MAY retry to contact
this neighbor later. this neighbor later.
RC_ERR_6OFID: The node MUST NOT retry immediately. The node MAY add RC_SFID_ERR: The node MUST NOT retry immediately. The node MAY add
the neighbor node on a blacklist. The node MAY retry to contact the neighbor node on a blacklist. The node MAY retry to contact
this neighbor later. this neighbor later.
RC_ERR_NORESOURCES: Wait for a timeout and restart the scheduling RC_BUSY: Wait for a timeout and restart the scheduling process.
process. RC_RESET: Abort 6P Transaction
RC_ERR_BUSY: Issue a RESET command. RC_ERR: Abort 6P Transaction. The node MAY retry to contact this
neighbor later.
11. Examples 11. Examples
TODO TODO
12. Implementation Status 12. Implementation Status
This section records the status of known implementations of the This section records the status of known implementations of the
protocol defined by this specification at the time of posting of this protocol defined by this specification at the time of posting of this
Internet-Draft, and is based on a proposal described in [RFC6982]. Internet-Draft, and is based on a proposal described in [RFC6982].
skipping to change at page 9, line 5 skipping to change at page 9, line 5
16. References 16. References
16.1. Normative References 16.1. Normative References
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, Requirement Levels", BCP 14, RFC 2119,
DOI 10.17487/RFC2119, March 1997, DOI 10.17487/RFC2119, March 1997,
<http://www.rfc-editor.org/info/rfc2119>. <http://www.rfc-editor.org/info/rfc2119>.
[IEEE802154e]
IEEE standard for Information Technology, "IEEE std.
802.15.4e, Part. 15.4: Low-Rate Wireless Personal Area
Networks (LR-WPANs) Amendament 1: MAC sublayer", April
2012.
[IEEE802154]
IEEE standard for Information Technology, "IEEE std.
802.15.4, Part. 15.4: Wireless Medium Access Control (MAC)
and Physical Layer (PHY) Specifications for Low-Rate
Wireless Personal Area Networks", June 2011.
16.2. Informative References 16.2. Informative References
[RFC7554] Watteyne, T., Ed., Palattella, M., and L. Grieco, "Using [RFC7554] Watteyne, T., Ed., Palattella, M., and L. Grieco, "Using
IEEE 802.15.4e Time-Slotted Channel Hopping (TSCH) in the IEEE 802.15.4e Time-Slotted Channel Hopping (TSCH) in the
Internet of Things (IoT): Problem Statement", RFC 7554, Internet of Things (IoT): Problem Statement", RFC 7554,
DOI 10.17487/RFC7554, May 2015, DOI 10.17487/RFC7554, May 2015,
<http://www.rfc-editor.org/info/rfc7554>. <http://www.rfc-editor.org/info/rfc7554>.
[RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running [RFC6982] Sheffer, Y. and A. Farrel, "Improving Awareness of Running
Code: The Implementation Status Section", RFC 6982, Code: The Implementation Status Section", RFC 6982,
 End of changes. 19 change blocks. 
67 lines changed or deleted 57 lines changed or added

This html diff was produced by rfcdiff 1.45. The latest version is available from http://tools.ietf.org/tools/rfcdiff/