Re: [6tsch] simulation for random schedule allocation

[Thomas Watteyne <[e-mail]>]

Xavi,

Very cool!

I have a bit of a hard time interpreting your results, or at least using
them to answer my question. Maybe you can shine some light on the following
scenario? Don't hesitate to shout if I missed something.

I have a neighborhood of N nodes. As a first step, we can assume all nodes
hear all nodes, i.e. the neighborhood is fully meshed. A more realistic
scenario can come later.

Some of these nodes schedule cells to one another, using the purely random
approach. Once this is done, they start communicating over those cells and,
for some cells, *realize* that there are collisions. They then decide to *
reallocate* these cells to different (random) locations in the schedule. In
the "healthy" case this process goes on until there are no more collisions,
i.e. until the pairs of motes are communicating on cells which are not
actively used by any other pair in the neighborhood.

In this "healthy" case, if I plot the number of reallocations as a function
of time, and assuming that all motes are switched on at the same time
(which is very artificial, but "bad case" scenario), I expect to see the
number of reallocation first increase, then come back down to 0. I expect
the time to converge to zero to increase as the load increases. The load
can be changed by adding more motes into my neighborhood, or allocating
more cells per pair of neighbor nodes (both cases are equivalent?).

At some threshold load, however, we switch from the "healthy" state to the
"collapse" state. In the latter, the number of reallocations never
converges back to zero, as the network is constantly busy detecting and
fixing collisions. This can be considered a network collapse, which is a
very bad outcome, since the nodes are constantly busy communicating, but
the network is not relaying data.

This can probably be easily described using aloha-type analysis. What I'd
like to know is that threshold load, i.e. the load at which this network
switch from "healthy" to "collapse". If this threshold is very high, we
might consider the random scheduling for sparse network; if it's very low,
we cannot as it will never work well.

There are a couple of items I underlined above which I believe are
important:
- "realizing" that there is a collision is not immediate for a node. We
have discussed the possibility of comparing statistics of several cells in
the same bundle. As a first simulation step, we could consider that a
single collision triggers a reallocation. In a more realistic scenario, the
simulation could model the actual statistics and the little algorithm which
looks at them and triggers a reallocation. This delay may have an impact on
the performance of the network, and the threshold load.
- reallocating is not an immediate thing, as it requires the two neighbors
to send a couple of "negotiation" packets back-and-forth. The exact
protocol isn't defined yet, but it will also introduce some latency. Some
strange side-effect is that, during some period of time, the new cell will
have been allocated, but the old one not deleted yet, possibly resulting in
even more collisions.

I have the impression that your simulation does not (yet) model the dynamic
reallocation of cells. I haven't looked at the code, so please let me know
if my impression is wrong.

Thoughts? What do you think the next steps are? Anything other people from
the group can help with (or have already done)?

Thomas


On Tue, Jun 25, 2013 at 5:24 PM, Xavier Vilajosana Guillen <
[e-mail]> wrote:

> Dear all, I plotted some of the results in case this can help on the
> discussion about probabilistic selection of slots.
>
> Note that I am playing with a 101 * 16 schedule and trying to allocate
> from few links to almost all the schedule.
>
> This plots correspond to one of the simulated nodes (of a 50 node network)
> with a high neighbour density. (the rest are quite similar and vary a
> little depending on the number of neighbours they have, nothing relevant
> though)
>
> Other cases can be simulated but before I will wait for your comments and
> suggestions so I spent the time on the right direction.
>
> kind regards,
>
> Xavi
>
> _______________________________________________
> 6tsch mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/6tsch
>
>