Re: [6tsch] simulation for random schedule allocation

[Xavier Vilajosana Guillen <[e-mail]>]

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 <
[e-mail]> wrote:

> 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
>>
>>
>
> _______________________________________________
> 6tsch mailing list
> [e-mail]
> https://www.ietf.org/mailman/listinfo/6tsch
>
>