Re: [6tsch] R: simulation for random schedule allocation

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

what I can do is provide some plots with more details on what will happen
in networks with schedules below 20% allocation (which are more realistic
cases). I can add number of tries to find a non-collidiing cell and see how
long it takes to converge according to the schedule load.

regards,
Xavi



Xavi


On Thu, Jun 27, 2013 at 9:28 AM, Kris Pister <[e-mail]> wrote:

> >> nodes with a low rank will experience a pretty high collision
> probability
>
> Yes, but only in a really busy network. Let's assume that we are doing
> data collection to/through a single dodag root. Let's also assume that the
> dodag root has a single radio, so it can only do one thing in any time
> slot, and it's smart enough not to schedule more than one thing in any time
> slot. We now have a throughput limit out of our network - one packet per
> timeslot, corresponding to one RX link per timeslot at the root. That
> occupies 1/15th or 1/16th of the available cell space, and collisions from
> the one-hop ring to the root are avoided by the root being smart. If all
> nodes are in the one-hop ring, we have a single collision domain, and any
> sibling connectivity for redundancy will risk collisions. If all nodes are
> not in the one-hop ring, then we'll need more links for connectivity not
> just redundancy, but by definition we will no long have a single collision
> domain. If you try to draw this kind of traffic as a dot on one of Xavi's
> plots they end up pretty close to the origin, in the relatively low
> collision part of the curves.
>
> In these limiting cases you can certainly show that an omniscient (or at
> least "more-scient") scheduler will give you both higher throughput and
> lower energy cost. But its hard to find a single-dodag-radio converge-cast
> application where random choice with some mild feedback won't work.
>
> ksjp
>
>
> On 6/27/2013 1:41 AM, Alfredo Grieco wrote:
>
>> Hi all,
>>
>> I guess that the point here is that the simulations of Xavi clearly
>> highlight that as the load increases the collision probability increases
>> too. I developed some Binomial expressions for a single hop network and
>> results are very similar to the ones of Xavi.
>>
>> Of course the scenarios can be made more and more realistic (as Maria Rita
>> and Yoshihiro are suggesting) but the indication of these preliminary
>> outcomes seem to be that nodes with a low rank will experience a pretty
>> high
>> collision probability (due to a higher load) if they choose cells
>> according
>> to a pure random technique whereas nodes with a high rank can safely use a
>> random approach without any problem.
>>
>> Again, it seems that the rank of a node has to play some role in the
>> mechanism used to select cells in order to avoid performance degradation.
>> I
>> believe that this kind of indication should be provided in some of the
>> drafts in progress.
>>
>> Cheers
>>
>> Alfredo
>>
>> Da: [e-mail] [mailto:[e-mail]**] Per conto di
>> Maria Rita PALATTELLA
>> Inviato: Thursday, June 27, 2013 10:08 AM
>> A: [e-mail]; [e-mail]
>> Cc: [e-mail]
>> Oggetto: Re: [6tsch] simulation for random schedule allocation
>>
>> Hello Xavi,
>> first of all many thanks for having built the code and run this first set
>> of
>> simulations for the WG.
>> I have some questions about the simulations. Please, feel free to ignore
>> my
>> comments, if they are inappropriate.
>>
>> 1)"Each node requests a link to each of its neighbors."
>> Is it really what we want? In my point of view, each node will ask a set
>> of
>> links (i.e., cells) according to the paths along which it will transmit
>> its
>> own traffic, and forwards the traffic received by other neighbors. In
>> other
>> words, the number of requested cells per node should be less than what we
>> are simulating right now. For sure, in the actual scenario, we have higher
>> probability of collision.
>>
>> 2) " the network is represented by a boolean square matrix of
>> num_nodes*num_nodes. Two nodes are neighbours if the cell for that two
>> nodes
>> (indexed by node ids) is true. if X is neighbour of Y the cells (x,y) and
>> (y,x) will be true."
>> This way of representing the network can create somehow a bit of confusion
>> with the TSCH schedule representation, where we have (timeslot,
>> channeloffset) cells.
>> Can't we find a different way for representing the network, and defying
>> the
>> set of neighbors? Moreover, this point 2) is linked with point 1) I guess,
>> i.e., assuming each node will request a link to each of its neighbors.
>>
>> 3) "Topology: Random, where each node requests a random number of
>> neighbours
>> between 2 and 10.”
>> Even though I am in favor of having a random topology, and a random number
>> of neighbors, maybe, for having a preliminary idea of the network
>> behavior,
>> we could run a set of simulations, where we fix the number of neighbors
>> (i.e., having it constant). Basically, my suggestion is to keep some
>> parameters constant, while we change others, in order to see how each of
>> them impact the cells allocation.
>>
>> Thank you!
>> Maria Rita
>>
>>   ______________________________**__________
>> From: [e-mail] [[e-mail]] on behalf of Xavier
>> Vilajosana Guillen [[e-mail]**]
>> Sent: Thursday, June 27, 2013 2:27 AM
>> To: [e-mail]
>> Cc: [e-mail]
>> Subject: Re: [6tsch] simulation for random schedule allocation
>> Hi Yoshihiro,
>> the network is represented by a boolean square matrix of
>> num_nodes*num_nodes. Two nodes are neighbours if the cell for that two
>> nodes
>> (indexed by node ids) is true. if X is neighbour of Y the cells (x,y) and
>> (y,x) will be true.
>> When a node requests a link it always requests a TX link, the counter part
>> sets it to RX links so a link allocation happens at both sides. In a
>> particular node Number of allocated links is the accumulation of both TX
>> and
>> RX allocated in that node.
>> Regarding your question, if X requests a TX link to Y the schedule of X
>> allocates a TX link to Y and the schedule of Y allocates a RX link from X.
>> If Y requests a TX link to X, X allocates a RX link from Y.
>> A link is not allocated in either side if there is a collision, and then I
>> increment the collision counter.
>> The code is here in case someone wants to play. Sorry it is not very clean
>> but I will clean it as soon as I can. If someone modifies it or improves
>> it,
>> feel free to commit your changes to the repository so the simulator
>> becomes
>> better.
>>
>> https://github.com/**xvilajosana/6TSCH<https://github.com/xvilajosana/6TSCH>
>> hope this makes things clear.
>> regards,
>> X
>>
>>
>>
>> Xavi
>>
>> On Wed, Jun 26, 2013 at 3:56 PM, <[e-mail]> wrote:
>> Hi Xavi,
>>   Thanks for your explanation.  I have better understanding now.
>>   I have one more question.
>>   You mentioned “there might be more than one link to a neighbor”.   Say
>> Node
>> X selected only one neighbor Node Y and requests one link to Node Y.  The
>> resulting number of links associated with Node X can be two (2) when Node
>> Y
>> also selected Node X as its neighbor and requested one link to Node X.  Is
>> my understanding correct?
>>   Yoshihiro Ohba
>>     From: [e-mail] [mailto:[e-mail]**] On
>> Behalf Of
>> Xavier Vilajosana Guillen
>> Sent: Thursday, June 27, 2013 1:33 AM
>> To: ohba yoshihiro
>> Cc: [e-mail]
>> Subject: Re: [6tsch] simulation for random schedule allocation
>>   Hi Yoshihiro,
>> you are right, the formulation of the sentence is not correct. Should be:
>>
>> “Topology: Random, where each node requests a random number of neighbours
>> between 2 and 10.”
>> this means that each node when created requests a number of neighbors
>> between 2 and 10, meaning that other nodes when are created also request
>> that number of neighbours and therefore a node can have more than 10
>> neighbours, because other nodes selected it as a neighbour. From the
>> simulation results I see that nodes have between 5 and 11 neighbours
>> usually.
>> However, from the numbers you point, 28 represents the number of allocated
>> links (number of allocated cells in the schedule) to its neighbours, there
>> might be more than one link to a neighbour in that case.
>> regards,
>> Xavi
>>
>>
>> Xavi
>>   On Wed, Jun 26, 2013 at 7:28 AM, <[e-mail]> wrote:
>> Hi Xavi,
>>   Thank you very much for the simulation.
>>   I am trying to understand the simulation model from your description
>> and the
>> result.
>>   “Topology: Random, where each node has a random number of neighbors
>> between
>> 2 and 10.”
>>   “
>> ************************ requesting 1 links
>> Node,Allocated Links,Collisions,Percentage
>> 0,28,0,0.0
>> “
>>   In the above result, does Node 0 actually have 28 neighbors?
>>   Regards,
>> Yoshihiro Ohba
>>   From: [e-mail] [mailto:[e-mail]**] On
>> Behalf Of
>> Xavier Vilajosana Guillen
>> Sent: Wednesday, June 26, 2013 3:46 AM
>> To: [e-mail]
>>
>> Subject: [6tsch] simulation for random schedule allocation
>>
>>
>> Hi all,
>>
>> I prepared a little simulation to see how random schedule allocation
>> behaves. (I have the code in Java in case someone is interested)
>>
>> here there are some details (everything can be tuned in case someone wants
>> to point me to a special case)
>>
>> Network: 50 nodes
>>
>> Topology: Random, where each node has a random number of neighbors
>> between 2
>> and 10.
>>
>> Each node requests a link to each of its neighbors. This is done from 1 to
>> 10 times (i.e 10 tests, the first requesting 1 link to each neighbour, the
>> second 2, etc.. up to 10 links to each of the neighbors, can be
>> configured)
>>
>> The slotframe is 101 slots and 16 channels.
>>
>> The simulation prints statistics for the test (and the collisions if we
>> are
>> interested.)
>> I used pseudo random generator from the java language assuming it provides
>> uniform or almost uniform distribution.
>> The allocation counter counts both the number of links allocated as tx and
>> the number of links allocated as rx due to a neighbour allocating a link
>> to
>> the actual node. The percentage is the % of collisions w.r.t the allocated
>> links.
>> Worst case is around 11% when allocating 10 links to each neighbour in
>> that
>> 50 node network.
>> I can play more on it but I wanted to share that initial results.
>> please see attached file for the results.
>> regards,
>> Xavi
>>
>>
>> ______________________________**_________________
>> 6tsch mailing list
>> [e-mail]
>> https://www.ietf.org/mailman/**listinfo/6tsch<https://www.ietf.org/mailman/listinfo/6tsch>
>>
>
> ______________________________**_________________
> 6tsch mailing list
> [e-mail]
> https://www.ietf.org/mailman/**listinfo/6tsch<https://www.ietf.org/mailman/listinfo/6tsch>
>