Subject: [6tsch] TASA: centralized scheduling

From: Thomas Watteyne <[email-masked]>
Date: Thu, 31 Jan 2013 09:33:42 -0800

Maria Rita,
Thanks for introducing TASA to the group. As per Don's suggestion, allow me
to branch this thread and edit the header. I will do the same with Qin's
uRes proposal.
Thomas

On Tue, Jan 29, 2013 at 1:14 PM, Maria Rita PALATTELLA <
[email-masked]> wrote:

>  Thomas,
>
> for sure it is a long email, but full of interesting info and thoughts!
>
> I totally agree with you about the idea of having a 6tsch layer, between
> TSCH and RPL. Actually, TASA (Traffic-Aware Scheduling Algorithm [1-3]) is
> built on such idea.
>
> TASA is a centralized scheduling algorithm, running on a master node in a
> IEEE802.1.5.4e network. It allows to build TSCH schedule, based on the
> network topology and the traffic load. Thus, it uses the information
> related to the paths, coming from RPL, and those related to the traffic
> (i.e., average traffic load generated by each node) in order to provide
> time slots/channel hops patterns, able to fulfill given requirements (i.e.,
> duty cycle, throughput, etc.) .
>
> You can find more info and details here:
>
>
>    - [1] Palattella, Maria Rita; Accettura, Nicola; Dohler, Mischa;
>    Grieco, Luigi Alfredo; Boggia, Gennaro: Traffic Aware Scheduling
>    Algorithm for Multi-Hop IEEE 802.15.4e Networks<http://publications.uni.lu/record/9659>,
>    Personal Indoor and Mobile Radio Communications (PIMRC), 2012 IEEE 23rd
>    International Symposium on, 2012, pp. 327-332
>    - [2] Palattella, Maria Rita; Accettura, Nicola; Dohler, Mischa;
>    Grieco, Luigi Alfredo; Boggia, Gennaro: Traffic-Aware Time-Critical
>    Scheduling In Heavily Duty-Cycled IEEE 802.15.4e For An Industrial IoT<http://publications.uni.lu/record/9689>,
>    Proc. of IEEE Sensors 2012, 2012.
>    - [3] Accettura, Nicola; Palattella, Maria Rita; Dohler, Mischa;
>    Grieco, Luigi Alfredo; Boggia, Gennaro: Standardized Power-Efficient &
>    Internet-Enabled Communication Stack for Capillary M2M Networks<http://publications.uni.lu/record/8095>,
>    Proc. of IEEE WCNC 2012, Workshop on Internet of Things Enabling
>    Technologies, 2012, pp. 226-231, ISBN: 978-1-4673-0681-2
>
>
>  Of course, I will be more than happy in providing more information, and
> discuss more about TASA in case you may find in it a possible solution to
> our problem (or at least, part of the problem)!
>  Best Regards,
> Maria Rita
>
>
>  ------------------------------
> *From:* [email-masked] [[email-masked]] on behalf of
> Thomas Watteyne [[email-masked]]
> *Sent:* Tuesday, January 29, 2013 9:04 PM
> *To:* [email-masked]
>
> *Subject:* Re: [6tsch] Welcome to the "6tsch" mailing list
>
>  Nick, Michael,
>
>  Very interesting discussion, indeed. I can't resist to add my 2c.
>
>  IEEE802.15.4e TSCH makes a subtle distinction between a *link *("a
> single slot scheduled from mote A to mote B") and a *path *("union of all
> links between A and B"). A link is attached a <neighbor, slotOffset,
> channelOffset, TX|RX> tuple [1]. If multiple links are scheduled to the
> same neighbor, they are typically equivalent, i.e. the MAC layer sends the
> packet on whichever of these links happens to show up after the packet was
> put in the MAC queue. Since the slotframe repeats over time (and the length
> of the slotframe is typically constant), each *link* gives you a
> "quantum" of bandwidth to a given neighbor. By modifying the number of
> links in a *path*, you modify the resources allocated between two
> neighbors.
>
>  The TSCH standard is *extremely* flexible, and you can implement lots of
> fanciness within the standard. Implementations can for example keep
> per-link statistics: at any time, you can know how many packets you
> sent/received, for each neighbor and for each link. Based on this
> information, you can play with the queuing behavior (e.g. wait for this
> link to show up because this one is behaving bad), or with the schedule
> (e.g. link 14 to neighbor A is worse than all the other to this neighbor,
> let's talk to mote A to replace it with another one). TSCH really only
> defines how to execute the schedule, so there's lots (and lots) of room for
> defining behavior.
>
>  Maybe too much room to be handled entirely by RPL. As I see it, RPL only
> wants to know about some cost associated with the topology, and uses that
> to compute multi-hop routes. In particular, I believe RPL is more
> interested in *paths* (the "performance" of the connection between two
> neighbors), rather than the individual *links *making up each path. In my
> opinion (and this is, I believe, perfectly in line with *Xavi*'s
> comment), we could define a *6tsch* layer which sits between TSCH and
> RPL. The goal of this layer would be to (1) turn some throughput
> requirements into *links *in the schedule and (2) collect information and
> feedback *path* statistics to RPL.
>
>  Implementations of this layer can be all over the spectrum: it can be
> controlled by an outside (central) scheduler, it can implement some
> neighbor-to-neighbor communication to set up a schedule in a distributed
> fashion, or anything in-between. The goal is, I believe, to avoid for RPL
> to have to specify the exact slot to send on, RPL tells the *6tsch* layer
> to "send this packet to neighbor A".
>
>  To come back to *Michael*'s comment, I believe that, with this setup,
> RPL actually can be using traditional metrics (ETX, bandwidth, latency,
> etc), the *6tsch* layer taking care of MAC specifics.
>
>  One last thing I believe is important: what TSCH *does* define is how to
> frequency hop. At each occurrence of a slot in the slotframe, the frequency
> to communicate on is recalculated [2], and is different from the last time.
> This means that neither the *6tsch* layer nor RPL need to worry about the
> actual frequency to communicate on; the schedule just looks like a grid.
>
>  I realize now this became a quite long e-mail, thanks for ready through
> here!
>
>  Thoughts?
>
>  Thomas
>
> [1] IEEE802.15.4e, Section 6.2.19.3
> [2] IEEE802.15.4e, Section 5.1.1a
>
> On Tue, Jan 29, 2013 at 6:05 AM, Michael Richardson <[email-masked]
> > wrote:
>
>>
>> >>>>> "Nick" == Nick Moore <[email-masked]> writes:
>>      Nick> * Should all this
>>      Nick> be happening down in the MAC layer instead?
>>
>>     >> No.
>>
>>     Nick> OK, but why?  What makes this an L3 (/ L2.5) thing?
>>
>>     Nick> I'm not just asking to be contrarian, if this is to become an
>>     Nick> IETF WG that'd be part of the charter ...
>>
>> A number of reasons.
>> 1) the bufferbloat results suggests that buffering at L2 is a bad
>>    thing.  While very resource constrained nodes are unlikely to have much
>>    buffer at all, this is not true for edge/gateway nodes, and it is
>>    increasing untrue of various wearable and PAN-type devices such as
>>    smartphones which will get LLN interfaces.
>>
>>    It was particularly a surprise to many layer-3 types what the 802.11
>>    access point people are doing at layer 2.  A lot of it invalidates
>>    significant architectural assumptions.  In many cases, the layer-2
>>    optimizations are coding to the benchmarks, rather than the real
>> traffic.
>>
>> 2) layer-3 (and higher) may need to make (re-)prioritization decisions
>> based
>>    upon what the transimission schedule is.
>>    Consider an actuator of some kind (a device that includes a fire
>>    supressor...) that, due to its critical nature has multiple layer-2
>>    connections using different technologies.  Maybe IPv6 over CAN over
>>    9600 baud multi-drop RS422 and 4e.  Layer-3 LLNs can easily build a
>>    DAG that includes both transports, realize that as slow as the 4e
>>    might be, it's usually still faster for non-critical traffic than the
>> CAN.
>>
>>    The layer-3 DAG would actually permit the the device to be addressed
>>    by the application using a single IPv6 address, with the network
>>    figuring out how to get things there.  That means less complexity and
>>    network knowledge required by the application.
>>
>>    There may be times during the 4e cycle when the CAN is faster than
>>    the wireless.  There also could be congestion on the 4e which would
>>    cause the slot to be missed.  If the packet remained queued for the
>>    same layer-2, it would remain for an entire cycle.
>>
>> 3) In the ethernet world, I point to STP and its variants as layer-2
>>    attempts to do routing, which failed.  Well, it does what it was
>>    advertised to do (detect and disable loops), but it turns out that
>>    we need much more than that.
>>    People have gone to layer-3 solutions like OSPF instead, because it
>>    provides diagnostics, works across vendors, and it responds much
>>    faster. And we also have TRILL.
>>
>> --
>> Michael Richardson <[email-masked]>, Sandelman Software Works
>>
>>
>>
>> _______________________________________________
>> 6tsch mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/6tsch
>>
>>
>
>