Re: [6tsch] simulation for random schedule allocation

Qin Wang <qinwang@berkeley.edu> Thu, 27 June 2013 21:23 UTC

Return-Path: <qinwang@berkeley.edu>
X-Original-To: 6tsch@ietfa.amsl.com
Delivered-To: 6tsch@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 9CD7D21F8E37 for <6tsch@ietfa.amsl.com>; Thu, 27 Jun 2013 14:23:01 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.364
X-Spam-Level:
X-Spam-Status: No, score=-2.364 tagged_above=-999 required=5 tests=[AWL=0.613, BAYES_00=-2.599, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-1]
Received: from mail.ietf.org ([12.22.58.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id uQLpvlKokHY9 for <6tsch@ietfa.amsl.com>; Thu, 27 Jun 2013 14:22:55 -0700 (PDT)
Received: from mail-ie0-f175.google.com (mail-ie0-f175.google.com [209.85.223.175]) by ietfa.amsl.com (Postfix) with ESMTP id D670721F8411 for <6tsch@ietf.org>; Thu, 27 Jun 2013 14:22:49 -0700 (PDT)
Received: by mail-ie0-f175.google.com with SMTP id a13so2430735iee.6 for <6tsch@ietf.org>; Thu, 27 Jun 2013 14:22:44 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:x-gm-message-state; bh=heNsey3DOIbOVze6g1cax0stiL+ELpKFaX7z+TnQ8lk=; b=p3HmtZ/PqbAH+Td31hiirpuf59KgdHXOIb6Iy1FZN8FWrqOZ+oEiBA3B3ivFxubP2j /F8jHk2I/GJlaZEJpKZ/6PON9rWcUCl/beNU8T43GSwkpo5Ir2xX+E67V9BE5dZm7zgg 16xioDFIv/vLQ5oWe1E1ED4Zij30wIfA01MnEbjg4zbJF2MInDrPxi3xWAB2yUuBBrsX 8XK85ilQ0Mo+IgiMP+Gj0O4iVE55m3eiXEBO0rQMExqL5p+dLnzkcZMBLvmfDU+A+P5e B+0NTUk6AmVe/DrNCU8r+a279nsB4KUmhwnm15M5RwK+C+aa57oB8f81UdgkGAjpoWLc v7TA==
MIME-Version: 1.0
X-Received: by 10.50.67.43 with SMTP id k11mr673807igt.26.1372368164229; Thu, 27 Jun 2013 14:22:44 -0700 (PDT)
Received: by 10.64.240.20 with HTTP; Thu, 27 Jun 2013 14:22:44 -0700 (PDT)
In-Reply-To: <CADJ9OA-p8+suiEKsob+gK_pGKMQOC6GiSPz_snKMQ_QiRi2Cog@mail.gmail.com>
References: <CALEMV4b27w3=hCkovP1JpQwQnN_jcu98hGPtjT349LhFBPb0XQ@mail.gmail.com> <674F70E5F2BE564CB06B6901FD3DD78B12D2691A@tgxml338.toshiba.local> <CALEMV4Zbqjd66Msot7cr45oFtG60zFFgUkAfPMLCq17zYR+ejw@mail.gmail.com> <674F70E5F2BE564CB06B6901FD3DD78B12D26BDD@tgxml338.toshiba.local> <CALEMV4a4X4+8k5o1o7HVpjL8xdQ1WiwprP1HD6Vzv-8p4iceKw@mail.gmail.com> <F085911F642A6847987ADA23E611780D1857A510@hoshi.uni.lux> <CALEMV4ZrXue_yGW1DRODD=AyXj5MSxcKmbZJ_h2RvvHhfra-=w@mail.gmail.com> <CAAzoce4Aqyc+Mcu5rMNA25xPL2ktNpb=LVuyS7ZEMmi6CBPQFw@mail.gmail.com> <CALEMV4aP0+UJBGf+OwAqD5qk7AVsrU9OwGvWRAz1G3C4E9kAZQ@mail.gmail.com> <CAAzoce6zYjRjwdw5Tzo6Dq4c_mxZ9+4D0DbZSyyKxigp9x5zvw@mail.gmail.com> <CADJ9OA-p8+suiEKsob+gK_pGKMQOC6GiSPz_snKMQ_QiRi2Cog@mail.gmail.com>
Date: Fri, 28 Jun 2013 05:22:44 +0800
Message-ID: <CAAzoce76M+EndkzxrBzsL6bopK6GLz4A5P+A2Owah17KKM2urg@mail.gmail.com>
From: Qin Wang <qinwang@berkeley.edu>
To: Thomas Watteyne <watteyne@eecs.berkeley.edu>
Content-Type: multipart/alternative; boundary="047d7bd76db0ee1fff04e0295cbc"
X-Gm-Message-State: ALoCoQkH8G12kEMh44s/Pl7D/++cyov/iO+Q9frF2zWU0xHB2y+64vlOOfUMWmkuSfdf+D2pyfzW
Cc: "6tsch@ietf.org" <6tsch@ietf.org>
Subject: Re: [6tsch] simulation for random schedule allocation
X-BeenThere: 6tsch@ietf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: "Discuss link layer model for Deterministic IPv6 over the TSCH mode of IEEE 802.15.4e, and impacts on RPL and 6LoWPAN such as resource allocation" <6tsch.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/6tsch>, <mailto:6tsch-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/6tsch>
List-Post: <mailto:6tsch@ietf.org>
List-Help: <mailto:6tsch-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/6tsch>, <mailto:6tsch-request@ietf.org?subject=subscribe>
X-List-Received-Date: Thu, 27 Jun 2013 21:23:02 -0000

agree!

Qin


On Fri, Jun 28, 2013 at 4:40 AM, Thomas Watteyne <watteyne@eecs.berkeley.edu
> 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 <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
>>
>>
>
> _______________________________________________
> 6tsch mailing list
> 6tsch@ietf.org
> https://www.ietf.org/mailman/listinfo/6tsch
>
>