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