Re: [6tsch] simulation for random schedule allocation

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

Hi Qin,

I agree, the simulator can be improved in many many ways, my initial idea
was simply to get the numbers on what was the behaviour according to how
"full" the schedule is, I don't think that not having a network that can be
projected in a 2D plane is a problem as the trend of the data will be the
same.

I can work more on the simulator if we think this is a tool we want to
exploit, to have the rough idea that random selection of links with low
crowded schedules will work I think it is enough.

cheers!
Xavi

Xavi


On Thu, Jun 27, 2013 at 7:36 AM, Qin Wang <[e-mail]> wrote:

> Xavi,
>
> From
> https://github.com/xvilajosana/6TSCH/blob/master/simulator/src/edu/berkeley/sixtus/simul/SimulatorEngine.java,
> (createNetworkTopology(Random ran)), I understand how the network
> topology is established. I think it may result in some cross edges, which
> will not happen in real network deployment.
>
> To avoid the problem, usually, we can think that a 2D array presents a
> area, say L*L, and then assign each node (x,y) in the L*L randomly. As
> result, each node will have some amount of neighbors. Does it make sense?
>
> Thought?
>
> Qin
>
>
>
>
>
>
>
>
>
>
> On Thu, Jun 27, 2013 at 9:53 PM, Xavier Vilajosana Guillen <
> [e-mail]> wrote:
>
>> Hi Maria Rita, see inline please
>>
>>
>> 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.
>>
>> I agree, the first set of simulations was completely brute force but
>> showed something that it is interesting (and this was my main objective),
>> with low density schedules (i.e almost all cells non-scheduled ) the
>> collision probability at the first choice is very low meaning that with few
>> retries in case of collision it will find a right cell. With dense
>> schedules (out of the scope on the majority of TSCH networks) the
>> allocation performance is very bad. It is important to bear in mind that
>> a network with 10% of its schedule allocated is a very busy network.(from
>> what we have seen on different network deployments)
>>
>> 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.
>>
>> If you look the code you will see that the network is expressed using 2
>> variables, one is a 1 dimension array of nodes (50 on my experiments),each
>> node keeps a slotframe structure being a 101*16 matrix of Cells, where a
>> cell is a data structure with some information. In addition the network
>> topology is built using an adjacency matrix, each row represents a node
>> that is matched with its neighbors represented by the column. This can be
>> done in many different ways but I guess it is pretty simple in that way. My
>> initial idea on that simulator was to get some numbers, I did not put
>> effort on having a new super efficient NS-2! and therefore the code is
>> super simple and objective driven. If we feel that we need to consolidate
>> that then I need to work on putting some more effort on its structure and
>> design.
>>
>> 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.
>>
>> Yes, I agree too, this can be configured easily.
>>
>> thanks for your comments!
>>
>> Thank you!
>> Maria Rita
>>
>> Xavi
>>
>>
>> On Thu, Jun 27, 2013 at 1:07 AM, Maria Rita PALATTELLA <
>> [e-mail]> wrote:
>>
>>>  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
>>
>>
>