Re: [6tsch] On the fly scheduling

["Pascal Thubert (pthubert)" <[e-mail]>]

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]> [mailto:[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]<mailto:[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]<mailto:[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]<mailto:[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]<mailto:[e-mail]> [[e-mail]<mailto:[e-mail]>] on behalf of Pascal Thubert (pthubert) [[e-mail]<mailto:[e-mail]>]
Sent: Thursday, October 03, 2013 4:09 PM
To: [e-mail]<mailto:[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]> [mailto:[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]<mailto:[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<http://www.ingenieria.udp.cl>
(56 2) 676 8125<tel:%2856%202%29%20676%208125>
_______________________________________________
6tsch mailing list
[e-mail]<mailto:[e-mail]>
https://www.ietf.org/mailman/listinfo/6tsch


_______________________________________________
6tsch mailing list
[e-mail]<mailto:[e-mail]>
https://www.ietf.org/mailman/listinfo/6tsch


_______________________________________________
6tsch mailing list
[e-mail]<mailto:[e-mail]>
https://www.ietf.org/mailman/listinfo/6tsch