Re: [6tsch] simulation for random schedule allocation

[Qin Wang <[e-mail]>]

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