Re: [6tsch] On the fly scheduling

[Qin Wang <[e-mail]>]

Hi Pascal and all,

It is a interesting approach. I would like to put different approaches
above together.

Objective: meet some QoS requirement.
Tool 1: pre-allocation, like what Pascal suggested, assign number of cells
to a bundle, and on/off them on demand.
Tool 2: post-allocation, like discussed in other emails in this thread,
adjust the number of cells in a bundle according to statistics information.

In reality, I think a mote may use the combination of tool 1 and tool 2,
e.g. at the beginning, mote allocates some cells for a bundle, and use them
in the mode of on/off on demand; when statistics information show 2 more
cells needed, then mote is triggered to allocates 3 more cells for the
bundle, and then also use them in the mode of on/off on demand.

If it is the case, a solution should include the the following parts:
(1) mechanism to create/delete softcells
(2) mechanism to provide statistics information
(3) mechanism to on/off cell on demand
(4) algorithm to determine how many cells needed for a QoS requirement like
(dataflow/burst-feature, delay-tolerance, {statistics info},  ...)

What do you think?

Qin




On Fri, Oct 4, 2013 at 5:30 PM, Pascal Thubert (pthubert) <
[e-mail]> wrote:

>  Dear all:****
>
> ** **
>
> Statistics and hysteresis can be costly in terms of memory and CPU, may
> not be the best strategy to address bursts of traffic in a stochastic IP
> network, and the strategy to derive the allocation from the past
> observation may be hard to determine in a particular case and even harder
> to generalize.****
>
> ** **
>
> The needs of bandwidth may be very dynamic for instance in the case of
> alarms/alerts, or in the case of a brutal variation of monitored data.
> Changes in the network topology impacting the rank of a node within the DAG
> may also impact brutally its needs of bandwidth. So we cannot only rely on
> past observations and but also need to maintain some capabilities that rely
> on current needs that operate efficiently in terms of control and yet very
> dynamically to accept both brutal bursts of traffic and longer term
> variations.****
>
> ** **
>
> Considering that we have ample room in a SlotFrame, a simple strategy,
> derived from traditional memory management, could be to augment the number
> of cells in a bundle each time it is saturated. As an image, GNU’s obstack
> seem to grow linearly one chunk at a time, but I know of chunk
> implementations that double the size of a dynamic chunk each time it is
> saturated and a geometrical growth may a better approach for us. ****
>
> ** **
>
> In a bundle, a portion of the cells is always on. The rest can stay idle
> (no wake to send or listen) unless a previous cell indicates that there is
> more to come. If we agree on a strategy like this then we can start working
> out the details, in particular how handle lazy release or one-shot
> override, how we observe unallocated slots to make them candidate for
> allocation, etc...****
>
> ** **
>
> As you see, even implementing such a simple strategy can already be quite
> some work in a constrained device. ****
>
> ** **
>
> Cheers,****
>
> ** **
>
> Pascal****
>
> ** **
>
> *From:* [e-mail] [mailto:[e-mail]] *On Behalf
> Of *Maria Rita PALATTELLA
> *Sent:* vendredi 4 octobre 2013 09:19
> *To:* Thomas Watteyne; 6TSCH
>
> *Subject:* Re: [6tsch] On the fly scheduling****
>
>  ** **
>
> +1 for me too.****
>
> ** **
>
> For sure, according to the specific requirements of the applications,
> different algorithms may be used for building the schedule. But the
> functionalities offers by 6top (i.e., collect statist. Info, send commands
> for scheduling cells) will be still the same (no matter which algorithm is
> used). ****
>
> ** **
>
> The statistics needed could change because different algorithms may use
> different input as parameters.  So, we will have to include a set of
> statistic information, or anyway, make sure it is possible to extend them.
> ****
>
> ** **
>
> Maria Rita****
>
> ** **
>
> ** **
>
> ** **
>
> *From:* [e-mail] [mailto:[e-mail]<[e-mail]>]
> *On Behalf Of *Thomas Watteyne
> *Sent:* Thursday, October 03, 2013 10:11 PM
> *To:* 6TSCH
> *Subject:* Re: [6tsch] On the fly scheduling****
>
> ** **
>
> That would indeed be clean.****
>
> ** **
>
> On Thu, Oct 3, 2013 at 12:33 PM, Qin Wang <[e-mail]> wrote:***
> *
>
> Hi all,****
>
> ** **
>
> +1 for the proposal. ****
>
> ** **
>
> Regarding to how to approach, I agree with Thomas. There is an entity
> running on top of 6top, which reads queue information and other statistics
> information from 6top, sends instruction like create/delete softcells to
> 6top. I think we can use the design methodology of Objective Function in
> RPL, i.e. define the statistics information and the interface to/from 6top,
> and leave the specific algorithm open.****
>
> ** **
>
> What do you think?****
>
> ** **
>
> Qin ****
>
> ** **
>
> ** **
>
> ** **
>
> On Fri, Oct 4, 2013 at 12:45 AM, Thomas Watteyne <
> [e-mail]> wrote:****
>
> +1 for the proposal.****
>
> ** **
>
> I believe it could be a very simple and powerful approach. Diego, would
> you agree that this can be considered a distributed mechanism sitting on
> top of 6top?****
>
> ** **
>
> That is, 6top provides:****
>
>    - commands to modify the number of soft cells in a bundle****
>    - commands to retrieve usage statistics of the cells/bundles****
>
>  The way I see it, your proposal consists of an algorithm which feeds
> from the usage statistics and triggers changes in the number of soft cells
> in a bundle. Correct?****
>
> ** **
>
> The questions to answer for now is whether 6top provides the right
> statistics.****
>
> ** **
>
> Maria Rita, one big difference with TASA is that OTF scheduling is
> distributed.****
>
> ** **
>
> Thomas****
>
> ** **
>
> On Thu, Oct 3, 2013 at 9:11 AM, Maria Rita PALATTELLA <
> [e-mail]> wrote:****
>
> Diego,( all)
>
> what you are suggesting (i.e., reserve cells based on queue size, delay)
> is actually the main idea behind TASA (Traffic Aware Scheduling Algorithm).
>
> TASA builds the schedule based on the local (number of pkt generated by
> the node) and global queue level ( i.e., local + pkt to be forwarded,
> generated by children). It gives priority to nodes with longer queues and
> it aims to reduce the latency for delivering the pkt. At the same time
> while building the schedule it minimizes the number of scheduled cells in
> order to reduce the network duty cycle.
> TASA is centralized and thus it assumes that the PCE has all the info
> needed for setting up the schedule. in other words, it knows the traffic
> generated by each nodes, and the paths followed by each pkt.
> With a "on the fly solution", we will not need to know all this info a
> priori. but we will use 6top monitoring functions and the control flows
> message for scheduling the cells.
>
> Btw, I agree with all the points raised up by Xavi.  We will have to
> address his questions.
>
> And I support Pascal's suggestions about how to deal with bundle.
>
> Maria Rita****
>  ------------------------------
>
> *From:* [e-mail] [[e-mail]] on behalf of
> Pascal Thubert (pthubert) [[e-mail]]
> *Sent:* Thursday, October 03, 2013 4:09 PM
> *To:* [e-mail]; Prof. Diego Dujovne****
>
>
> *Cc:* 6TSCH
> *Subject:* Re: [6tsch] On the fly scheduling****
>
> ** **
>
> +1 too.****
>
>  ****
>
> I think that the queue size matters at enqueue but the latency is really
> what we care for at dequeue, that is how long did this device keep this
> message in queue (even if we are far from ****
>
> buffer bloat conditions in such a device). If one of the 2 conditions
> (size at enqueue, latency at dequeue) is reached then the bundle should be
> increased. ****
>
>  ****
>
> I agree with Xavi that we want to avoid changing the bundle size all the
> time. We discussed that with Qin and others earlier on the ML. One way of
> increasing the bundle dynamically at a very low cost (not even a
> hysteresis)  is to have it large amount of cells from the start but used
> like 10% by default (xmit/listen happens only once in 10 time slots). A bit
> in the frame indicates whether the next (normally unused) slot will indeed
> be used. The bit can be present in the data and acked in the ack. This can
> also implicitly be triggered for retries.****
>
>  ****
>
> Please keep us tuned!****
>
>  ****
>
> Cheers,****
>
>  ****
>
> PS Note that Cisco has IPR on chaining time slots and flagging whether the
> next is used or not. We already declared our IPR against the architecture
> draft and provided terms.****
>
>  ****
>
> Pascal****
>
>  ****
>
> *From:* [e-mail] [mailto:[e-mail]] *On Behalf
> Of *Xavier Vilajosana Guillen
> *Sent:* jeudi 3 octobre 2013 15:46
> *To:* Prof. Diego Dujovne
> *Cc:* 6TSCH
> *Subject:* Re: [6tsch] On the fly scheduling****
>
>  ****
>
> Diego,
>
> +1****
>
> it seems to a me a very interesting idea to explore. Maybe we can start
> putting some rules of this mechanism on the table and prepare a simulation.
> I am completely in with that idea.****
>
> Some questions arise:****
>
> 1-how fast do you react to changes on the queue size to avoid hysteresis
> -- i.e how do you maintain certain stability in the schedule (so you don't
> start installing and removing links very often)****
>
> 2-how you map queue size (only one or if more than one queue) to actual
> link requirements****
>
> 3-how you recover from link collisions in case of multiple nodes schedule
> the same cells.****
>
> 4-how to decide to who (what neighbor) install more links according to
> queue size?****
>
>  ****
>
> cheers!
> Xavi****
>
>  ****
>
>  ****
>
> On Thu, Oct 3, 2013 at 3:23 AM, Prof. Diego Dujovne <
> [e-mail]> wrote:****
>
> Dear all,
>             I've been looking into the idea of "on the fly scheduling",
> presented on the Sept 27th webex call as "on-the-fly decentralized
> reservation".
> The basic mechanism would be based on analysing the queue size
> on a node and dynamically adapt the number of reserved
> cells to satisfy queue size, delay and/or power
> consumption thresholds.
>             This mechanism would work inside 6top, between pairs of nodes.
> As a first approach, it would be based on the minimal draft.
> What do you think on this starting point?
> I (gladly) receive comments to add or modify this proposal.
>
>                                      Diego
>
>
>
>
> --
> DIEGO DUJOVNE
> Académico Escuela de Ingeniería en Informática y Telecomunicaciones
> Facultad de Ingeniería UDP
> www.ingenieria.udp.cl
> (56 2) 676 8125
> _______________________________________________
> 6tsch mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/6tsch****
>
>  ****
>
>
> _______________________________________________
> 6tsch mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/6tsch****
>
> ** **
>
>
> _______________________________________________
> 6tsch mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/6tsch****
>
> ** **
>
> ** **
>
> _______________________________________________
> 6tsch mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/6tsch
>
>