Subject: [6tsch] simulation for random schedule allocation

From: Xavier Vilajosana Guillen <[email-masked]>
Date: Tue, 25 Jun 2013 17:24:24 -0700

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

---

From: Thomas Watteyne <[email-masked]>
Date: Tue, 25 Jun 2013 23:31:13 -0700

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 <
[email-masked]> wrote:

> Note that I am playing with a 101 * 16 schedule and trying to allocate
> from few links to almost all the schedule.
>
> _______________________________________________
> 6tsch mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/6tsch
>
>

---

From: Xavier Vilajosana Guillen <[email-masked]>
Date: Wed, 26 Jun 2013 07:00:28 -0700

Hi Thomas,

the presented results and my simulator only takes into account the first
part of your description but I guess gives us a clue of what will happen.

The simulator builds a network and starts allocating links to
neighbors.From the results we can see that when the schedule is "empty"
<10% of scheduled links, the collision probability when scheduling a new
link is below 8%, meaning that if we have a collision and re-schedule lots
of chances are to succeed. As the schedule is more populated, i.e 80% of
the available links are scheduled, the probability of collision is >80%,
meaning that it becomes very hard to converge to a collision free schedule.

if you look at the attached file that corresponds to the simulation results
for a node in the network (node 0) and for different number of links in its
schedule, you will see that to be able to have a 100% allocated schedule
(i.e all links) the number of collisions that happened is enormous.

e.g
Node,NumLinksRequested,NumNeighbors,TotalLinks,Allocated
Links,Collisions,IdenticaAllocation,% Collision,% Used Links
0,538,9,1616,1616,7643,425,472.95792079207916,100.0

Node 0 with 9 neighbours, requested 538 links to its neighbours and its
neighbours also requested some cells to it. 1616 (100%) got allocated but
to reach that 7643 collisions happened (this takes into account all
requests from other neighbours of course).

With that your scenario can be drawn as if the schedule is not very dense,
reallocations collision can have low probability. As it becomes dense, it
seems impossible that the mechanism will work unless we have some "guided"
selection.

X

Xavi

On Tue, Jun 25, 2013 at 11:31 PM, Thomas Watteyne <
[email-masked]> wrote:

> 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?).
>
> 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.
>
>> 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)
>>