Subject: [6tsch] simulation for random schedule allocation

From: Xavier Vilajosana Guillen <[email-masked]>
Date: Tue, 25 Jun 2013 11:46:27 -0700

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

---

From: <[email-masked]>
Date: Wed, 26 Jun 2013 14:28:05 +0000

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: [email-masked] [mailto:[email-masked]] On Behalf Of Xavier Vilajosana Guillen
Sent: Wednesday, June 26, 2013 3:46 AM
To: [email-masked]
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 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

---

From: Xavier Vilajosana Guillen <[email-masked]>
Date: Wed, 26 Jun 2013 09:33:05 -0700

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, <[email-masked]> 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:* [email-masked] [mailto:[email-masked]] *On Behalf
> Of *Xavier Vilajosana Guillen
> *Sent:* Wednesday, June 26, 2013 3:46 AM
> *To:* [email-masked]
>
> *Subject:* [6tsch] simulation for random schedule allocation****
>
> ** **
>
>
> ****
>
> Hi all,
>
> The simulation prints statistics for the test (and the collisions if we
> are interested.)****
>
> uniform or almost uniform distribution.****
>
> 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****
>

---

From: Qin Wang <[email-masked]>
Date: Thu, 27 Jun 2013 04:03:34 +0800

Xavi,

I'm not sure I understand the simulation completely. I just have a question
about the topology of network, which is established by choosing neighbors
randomly and independently. My feeling is it may result in a network with
cross edges, in another word, a network which cannot be placed on a 2D
plate.  Correct?  If my understanding is correct, I would like to suggest
using conventional method to establish the network, i.e. set N nodes into a
2D array, with uniform distribution. N will reflect the network density,
i.e. the average number of neighbors.

Then, based on the network, we can play cell reservation.

Thought?

Qin

On Thu, Jun 27, 2013 at 12:33 AM, Xavier Vilajosana Guillen <
[email-masked]> wrote:

>> *From:* [email-masked] [mailto:[email-masked]] *On
>> Behalf Of *Xavier Vilajosana Guillen
>> 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)
>>
>> 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. ****
>>
> _______________________________________________
> 6tsch mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/6tsch
>
>

---

From: <[email-masked]>
Date: Wed, 26 Jun 2013 22:56:54 +0000

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: [email-masked] [mailto:[email-masked]] On Behalf Of Xavier Vilajosana Guillen
Sent: Thursday, June 27, 2013 1:33 AM
To: ohba yoshihiro
Cc: [email-masked]
Subject: Re: [6tsch] simulation for random schedule allocation

Hi Yoshihiro,

“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, <[email-masked]<mailto:[email-masked]>> wrote:
Hi Xavi,

“

Regards,
Yoshihiro Ohba

From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]<mailto:[email-masked]>] On Behalf Of Xavier Vilajosana Guillen
Sent: Wednesday, June 26, 2013 3:46 AM
To: [email-masked]<mailto:[email-masked]>

Hi all,

Network: 50 nodes

---

From: Xavier Vilajosana Guillen <[email-masked]>
Date: Wed, 26 Jun 2013 17:27:33 -0700

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, <[email-masked]> 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****
>
> ** **
>
> ** **
>
> *Sent:* Thursday, June 27, 2013 1:33 AM
> *To:* ohba yoshihiro
> *Cc:* [email-masked]
> *Subject:* Re: [6tsch] simulation for random schedule allocation****
>
> ** **
>
> Hi Yoshihiro,****
>
> usually.****
> might be more than one link to a neighbour in that case.****
>
> regards,
> Xavi****
>
>
> ****
>
> Xavi****
>
> ** **
>
> On Wed, Jun 26, 2013 at 7:28 AM, <[email-masked]> wrote:****
>
> Hi Xavi,****
>
>  ****
>
> *To:* [email-masked]****

---

From: Maria Rita PALATTELLA <[email-masked]>
Date: Thu, 27 Jun 2013 08:07:30 +0000

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: [email-masked] [[email-masked]] on behalf of Xavier Vilajosana Guillen [[email-masked]]
Sent: Thursday, June 27, 2013 2:27 AM
To: [email-masked]
Cc: [email-masked]
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.

regards,
X

Xavi

On Wed, Jun 26, 2013 at 3:56 PM, <[email-masked]<mailto:[email-masked]>> wrote:
Hi Xavi,

Yoshihiro Ohba

From: [email-masked]<mailto:[email-masked]> [mailto:[email-masked]<mailto:[email-masked]>] On Behalf Of Xavier Vilajosana Guillen
Sent: Thursday, June 27, 2013 1:33 AM
To: ohba yoshihiro
Cc: [email-masked]<mailto:[email-masked]>
Subject: Re: [6tsch] simulation for random schedule allocation

Hi Yoshihiro,

Xavi

“

Regards,
Yoshihiro Ohba

Hi all,

Network: 50 nodes

---

From: "Alfredo Grieco" <[email-masked]>
Date: Thu, 27 Jun 2013 10:41:23 +0200

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: [email-masked] [mailto:[email-masked]] Per conto di
Maria Rita PALATTELLA
Inviato: Thursday, June 27, 2013 10:08 AM
A: [email-masked]; [email-masked]
Cc: [email-masked]
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: [email-masked] [[email-masked]] on behalf of Xavier
Vilajosana Guillen [[email-masked]]
Sent: Thursday, June 27, 2013 2:27 AM
To: [email-masked]
Cc: [email-masked]
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.

Xavi

 
 
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: [email-masked] [mailto:[email-masked]] On Behalf Of
Xavier Vilajosana Guillen
Sent: Thursday, June 27, 2013 1:33 AM
To: ohba yoshihiro
Cc: [email-masked]
Subject: Re: [6tsch] simulation for random schedule allocation
 
Hi Yoshihiro,

Xavi

 
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.”
 
“

Regards,
Yoshihiro Ohba
 
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Xavier Vilajosana Guillen
Sent: Wednesday, June 26, 2013 3:46 AM
To: [email-masked]

Hi all,

Network: 50 nodes

Topology: Random, where each node has a random number of neighbors between 2
and 10.

---

From: Xavier Vilajosana Guillen <[email-masked]>
Date: Thu, 27 Jun 2013 06:53:21 -0700

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

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 <
[email-masked]> wrote:

> 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.
>
> 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."
> 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*.”
>  ------------------------------
> *From:* [email-masked] [[email-masked]] on behalf of
> Xavier Vilajosana Guillen [[email-masked]]
> *Sent:* Thursday, June 27, 2013 2:27 AM
> *To:* [email-masked]
>
> *Cc:* [email-masked]
> *Subject:* Re: [6tsch] simulation for random schedule allocation
>
>      Hi Yoshihiro,
>
>  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
>  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.
>
>> 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****
>>
>> ** **
>>

---

From: Qin Wang <[email-masked]>
Date: Thu, 27 Jun 2013 22:36:48 +0800

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 <
[email-masked]> wrote:

> 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)
>
>> This way of representing the network can create somehow a bit of
>> confusion with the TSCH schedule representation, where we have (timeslot,
>> channeloffset) cells.
>> 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
>>
>>
>>> “Topology: Random, where each node requests a random number of
>>> neighbours between 2 and 10.”****
>>>

---

From: Kris Pister <[email-masked]>
Date: Thu, 27 Jun 2013 09:28:06 -0700

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

---

From: Xavier Vilajosana Guillen <[email-masked]>
Date: Thu, 27 Jun 2013 10:32:52 -0700

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 <[email-masked]> wrote:

> (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.
>
>>>> I am trying to understand the simulation model from your description
>>>> and the result.****
>>>>
>>>>  ****
>>>>

---

From: Xavier Vilajosana Guillen <[email-masked]>
Date: Thu, 27 Jun 2013 10:36:23 -0700

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 <[email-masked]> wrote:

> 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.
>
> 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
>
>
>> Da: [email-masked] [mailto:[email-masked]**] Per conto di
>> Maria Rita PALATTELLA
>> of
>> nodes
>> the
>>   ______________________________**__________
>> Vilajosana Guillen [[email-masked]**]
>> nodes
>> it,
>> https://github.com/**xvilajosana/6TSCH<https://github.com/xvilajosana/6TSCH>
>> Node
>>     From: [email-masked] [mailto:[email-masked]**] On
>> Behalf Of
>> and the
>> between
>>   From: [email-masked] [mailto:[email-masked]**] On
>> Behalf Of
>> are
>> that
>> ______________________________**_________________
>> 6tsch mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/**listinfo/6tsch<https://www.ietf.org/mailman/listinfo/6tsch>
>>
>
> ______________________________**_________________
> 6tsch mailing list
> [email-masked]
> https://www.ietf.org/mailman/**listinfo/6tsch<https://www.ietf.org/mailman/listinfo/6tsch>
>

---

From: Qin Wang <[email-masked]>
Date: Fri, 28 Jun 2013 01:49:40 +0800

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 <
[email-masked]> wrote:

>>> 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)
>>>
>>>> I have some questions about the simulations. Please, feel free to
>>>> ignore my comments, if they are inappropriate.
>>>>
>>>> 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.
>>>>
>>>> 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."
>>>>  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.
>>>>
>>>>> 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 simulation prints statistics for the test (and the collisions if
>>>>> we are interested.)****
>>>>>

---

From: Thomas Watteyne <[email-masked]>
Date: Thu, 27 Jun 2013 13:40:33 -0700

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 <[email-masked]> wrote:

>>>>> 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.
>>>>>
>>>>>> 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****
>>>>>>
>>>>>> ** **
>>>>>>
>>>>>> ** **
>>>>>>
>>>>>> 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
>>>>>> Worst case is around 11% when allocating 10 links to each neighbour
>>>>>> in that 50 node network.****
>>>>>>

---

From: Qin Wang <[email-masked]>
Date: Fri, 28 Jun 2013 05:22:44 +0800

agree!

Qin

On Fri, Jun 28, 2013 at 4:40 AM, Thomas Watteyne <[email-masked]
> wrote:

>>> 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.
>>>
>>>>> 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.
>>>>>
>>>>>>  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.
>>>>>>
>>>>>>  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
>>>>>> On Wed, Jun 26, 2013 at 3:56 PM, <[email-masked]>wrote:
>>>>>>
>>>>>>>  Hi Xavi,****
>>>>>>>
>>>>>>> ** **
>>>>>>>
>>>>>>> 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
>>>>>>> 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)
>>>>>>>

---

From: Maria Rita PALATTELLA <[email-masked]>
Date: Fri, 28 Jun 2013 07:21:36 +0000

+1
I do agree with Thomas too.
No need to develop another simulator for this preliminary test.
For the future, we may use OpneWSNone.
Maria Rita

From: [email-masked] [mailto:[email-masked]] On Behalf Of Qin Wang
Sent: Thursday, June 27, 2013 11:23 PM
To: Thomas Watteyne
Cc: [email-masked]
Subject: Re: [6tsch] simulation for random schedule allocation

agree!

Qin

On Fri, Jun 28, 2013 at 4:40 AM, Thomas Watteyne <[email-masked]<mailto:[email-masked]>> wrote:
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 <[email-masked]<mailto:[email-masked]>> 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 <[email-masked]<mailto:[email-masked]>> 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 <[email-masked]<mailto:[email-masked]>> 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 <[email-masked]<mailto:[email-masked]>> wrote:
Hi Maria Rita, see inline please

Hello Xavi,

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.

Thank you!
Maria Rita

Xavi

On Thu, Jun 27, 2013 at 1:07 AM, Maria Rita PALATTELLA <[email-masked]<mailto:[email-masked]>> 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.

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: [email-masked]<mailto:[email-masked]> [[email-masked]<mailto:[email-masked]>] on behalf of Xavier Vilajosana Guillen [[email-masked]<mailto:[email-masked]>]
Sent: Thursday, June 27, 2013 2:27 AM
To: [email-masked]<mailto:[email-masked]>

Hi Yoshihiro,

Xavi

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

Hi Yoshihiro,

"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

"Topology: Random, where each node has a random number of neighbors between 2 and 10."

"
"

Regards,
Yoshihiro Ohba

Hi all,

Network: 50 nodes

_______________________________________________
6tsch mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/6tsch

_______________________________________________
6tsch mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/6tsch

_______________________________________________
6tsch mailing list
[email-masked]<mailto:[email-masked]>
https://www.ietf.org/mailman/listinfo/6tsch