Re: [6tsch] simulation for random schedule allocation

Qin, all,

I believe the goal of the simulation work here is to be able to quicly
verify that some of the assumption we make makes sense, rather than
implementing the full behavior. Once those assumption are verified, we can
move on to a full-featured simulator (such as the OpenWSN one). So I would
say that there is space for both ends of the spectrum: Xavi's quick testing
tools, and a full featured simulator.

Thomas

On Thu, Jun 27, 2013 at 10:49 AM, Qin Wang <qinwang@berkeley.edu> wrote:

> Hi Xavi,
>
> I agree that for getting a idea about how crowded the schedule will be,
> there is no problem in using current mechanism to establish network
> topology.
>
> Although there are many network simulation tools like NS2, OmNet, I do
> think this tool will be very useful for 6tsch development and future
> research on 6tsch. So it is worth to put more effort to make it more
> realistic and flexible.
>
> How do you think?
>
> Qin
>
>
>
>
>
> On Fri, Jun 28, 2013 at 1:32 AM, Xavier Vilajosana Guillen <
> xvilajosana@eecs.berkeley.edu> wrote:
>
>> 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 <qinwang@berkeley.edu> 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 <
>>> xvilajosana@eecs.berkeley.edu> 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 <
>>>> maria-rita.palattella@uni.lu> 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:* 6tsch-bounces@ietf.org [6tsch-bounces@ietf.org] on behalf of
>>>>> Xavier Vilajosana Guillen [xvilajosana@eecs.berkeley.edu]
>>>>> *Sent:* Thursday, June 27, 2013 2:27 AM
>>>>> *To:* yoshihiro.ohba@toshiba.co.jp
>>>>>
>>>>> *Cc:* 6tsch@ietf.org
>>>>> *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, <yoshihiro.ohba@toshiba.co.jp> 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:* 6tsch-bounces@ietf.org [mailto:6tsch-bounces@ietf.org] *On
>>>>>> Behalf Of *Xavier Vilajosana Guillen
>>>>>> *Sent:* Thursday, June 27, 2013 1:33 AM
>>>>>> *To:* ohba yoshihiro
>>>>>> *Cc:* 6tsch@ietf.org
>>>>>> *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, <yoshihiro.ohba@toshiba.co.jp>
>>>>>> 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:* 6tsch-bounces@ietf.org [mailto:6tsch-bounces@ietf.org] *On
>>>>>> Behalf Of *Xavier Vilajosana Guillen
>>>>>> *Sent:* Wednesday, June 26, 2013 3:46 AM
>>>>>> *To:* 6tsch@ietf.org****
>>>>>>
>>>>>>
>>>>>> *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
>>>> 6tsch@ietf.org
>>>> https://www.ietf.org/mailman/listinfo/6tsch
>>>>
>>>>
>>>
>>
>
> _______________________________________________
> 6tsch mailing list
> 6tsch@ietf.org
> https://www.ietf.org/mailman/listinfo/6tsch
>
>