Re: [6tsch] simulation for random schedule allocation
Xavier Vilajosana Guillen <xvilajosana@eecs.berkeley.edu> Thu, 27 June 2013 00:27 UTC
Return-Path: <xvilajosana@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 072CA11E8155 for <6tsch@ietfa.amsl.com>; Wed, 26 Jun 2013 17:27:39 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.384
X-Spam-Level:
X-Spam-Status: No, score=-2.384 tagged_above=-999 required=5 tests=[AWL=0.592, 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 0O-hmomuwbRB for <6tsch@ietfa.amsl.com>; Wed, 26 Jun 2013 17:27:34 -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 7C03611E8171 for <6tsch@ietf.org>; Wed, 26 Jun 2013 17:27:34 -0700 (PDT)
Received: by mail-ie0-f175.google.com with SMTP id a13so269334iee.6 for <6tsch@ietf.org>; Wed, 26 Jun 2013 17:27:34 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=mime-version:reply-to:in-reply-to:references:date:message-id :subject:from:to:cc:content-type:x-gm-message-state; bh=UY38AwcE03CGKWTq2Y9M6+cL/WpZRQglzbZt/V5c6lg=; b=cgm0MYv1CbyUz+SLnuVIqGRsN/CWFonQLFmRAZTzABwnam67QwsKmCd7nkaiAdsTTk jObRz9V2J9pH67QipDyIuVWX/B5jz6smlEb/TyXOVhvcx5sItpG3nOrG/vPnTV6ORN4f 9bb14MEOBo4j4DfASiS6vbDU2N9KYsMVy0JJmV4UDZ1xu9YCQicFcxWjOEDAC+CgE9k5 dSMkNZ3xI2IPWBFKXWdDpfHWz3TPjXGIQ/Fm4I1JhAz500WWc3eWzdWQDwIWl4qnK2YQ IkqqNMOQMp8aoz8VIeAMTbjnQ8ELHCOi3QqKn6ieJyIVQe3hm3p1qD2y6GaMGfvEG80D YzeA==
MIME-Version: 1.0
X-Received: by 10.42.228.1 with SMTP id jc1mr3560496icb.92.1372292853983; Wed, 26 Jun 2013 17:27:33 -0700 (PDT)
Received: by 10.65.14.231 with HTTP; Wed, 26 Jun 2013 17:27:33 -0700 (PDT)
In-Reply-To: <674F70E5F2BE564CB06B6901FD3DD78B12D26BDD@tgxml338.toshiba.local>
References: <CALEMV4b27w3=hCkovP1JpQwQnN_jcu98hGPtjT349LhFBPb0XQ@mail.gmail.com> <674F70E5F2BE564CB06B6901FD3DD78B12D2691A@tgxml338.toshiba.local> <CALEMV4Zbqjd66Msot7cr45oFtG60zFFgUkAfPMLCq17zYR+ejw@mail.gmail.com> <674F70E5F2BE564CB06B6901FD3DD78B12D26BDD@tgxml338.toshiba.local>
Date: Wed, 26 Jun 2013 17:27:33 -0700
Message-ID: <CALEMV4a4X4+8k5o1o7HVpjL8xdQ1WiwprP1HD6Vzv-8p4iceKw@mail.gmail.com>
From: Xavier Vilajosana Guillen <xvilajosana@eecs.berkeley.edu>
To: yoshihiro.ohba@toshiba.co.jp
Content-Type: multipart/alternative; boundary="001a1133d7b816fd4c04e017d419"
X-Gm-Message-State: ALoCoQkNjkKsEUOiAS9f1d0HFqzrDqZnMWg0rbSEdVcZBtubOmN78aVeOt7mX0wZUSZOxAHkDflF
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
Reply-To: xvilajosana@eecs.berkeley.edu
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 00:27:39 -0000
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**** > > ** ** >
- Re: [6tsch] simulation for random schedule alloca… Xavier Vilajosana Guillen
- Re: [6tsch] simulation for random schedule alloca… yoshihiro.ohba
- Re: [6tsch] simulation for random schedule alloca… Xavier Vilajosana Guillen
- [6tsch] simulation for random schedule allocation Xavier Vilajosana Guillen
- [6tsch] simulation for random schedule allocation Xavier Vilajosana Guillen
- [6tsch] simulation for random schedule allocation Xavier Vilajosana Guillen
- Re: [6tsch] simulation for random schedule alloca… Thomas Watteyne
- Re: [6tsch] simulation for random schedule alloca… Qin Wang
- Re: [6tsch] simulation for random schedule alloca… yoshihiro.ohba
- Re: [6tsch] simulation for random schedule alloca… Xavier Vilajosana Guillen
- Re: [6tsch] simulation for random schedule alloca… Maria Rita PALATTELLA
- [6tsch] R: simulation for random schedule allocat… Alfredo Grieco
- Re: [6tsch] simulation for random schedule alloca… Xavier Vilajosana Guillen
- Re: [6tsch] simulation for random schedule alloca… Qin Wang
- Re: [6tsch] R: simulation for random schedule all… Kris Pister
- Re: [6tsch] simulation for random schedule alloca… Xavier Vilajosana Guillen
- Re: [6tsch] R: simulation for random schedule all… Xavier Vilajosana Guillen
- Re: [6tsch] simulation for random schedule alloca… Qin Wang
- Re: [6tsch] simulation for random schedule alloca… Thomas Watteyne
- Re: [6tsch] simulation for random schedule alloca… Qin Wang
- Re: [6tsch] simulation for random schedule alloca… Maria Rita PALATTELLA