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

[Kris Pister <[e-mail]>]

 >> 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
> 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