Re: [6tsch] simulation for random schedule allocation

<yoshihiro.ohba@toshiba.co.jp> Wed, 26 June 2013 14:28 UTC

Return-Path: <yoshihiro.ohba@toshiba.co.jp>
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 BBEE61F0D38 for <6tsch@ietfa.amsl.com>; Wed, 26 Jun 2013 07:28:21 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -8.088
X-Spam-Level:
X-Spam-Status: No, score=-8.088 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, HELO_EQ_JP=1.244, HOST_EQ_JP=1.265, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_HI=-8, UNPARSEABLE_RELAY=0.001]
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 kWwdOkZyf0fr for <6tsch@ietfa.amsl.com>; Wed, 26 Jun 2013 07:28:15 -0700 (PDT)
Received: from imx12.toshiba.co.jp (imx12.toshiba.co.jp [61.202.160.132]) by ietfa.amsl.com (Postfix) with ESMTP id CE2D91F0D33 for <6tsch@ietf.org>; Wed, 26 Jun 2013 07:28:14 -0700 (PDT)
Received: from tsbmgw-mgw01.tsbmgw-mgw01.toshiba.co.jp ([133.199.232.103]) by imx12.toshiba.co.jp with ESMTP id r5QES7SJ002870 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Wed, 26 Jun 2013 23:28:07 +0900 (JST)
Received: from tsbmgw-mgw01 (localhost [127.0.0.1]) by tsbmgw-mgw01.tsbmgw-mgw01.toshiba.co.jp (8.13.8/8.14.5) with ESMTP id r5QES73N028743; Wed, 26 Jun 2013 23:28:07 +0900
Received: from localhost ([127.0.0.1]) by tsbmgw-mgw01 (JAMES SMTP Server 2.3.1) with SMTP ID 407; Wed, 26 Jun 2013 23:28:07 +0900 (JST)
Received: from arc11.toshiba.co.jp ([133.199.90.127]) by tsbmgw-mgw01.tsbmgw-mgw01.toshiba.co.jp (8.13.8/8.14.5) with ESMTP id r5QES7mK028740; Wed, 26 Jun 2013 23:28:07 +0900
Received: (from root@localhost) by arc11.toshiba.co.jp id r5QES7XN028548; Wed, 26 Jun 2013 23:28:07 +0900 (JST)
Received: from ovp11.toshiba.co.jp [133.199.90.148] by arc11.toshiba.co.jp with ESMTP id ZAA28547; Wed, 26 Jun 2013 23:28:07 +0900
Received: from mx.toshiba.co.jp (localhost [127.0.0.1]) by ovp11.toshiba.co.jp with ESMTP id r5QES6Ot001889; Wed, 26 Jun 2013 23:28:06 +0900 (JST)
Received: from tgxml329.toshiba.local by toshiba.co.jp id r5QES6Tl012583; Wed, 26 Jun 2013 23:28:06 +0900 (JST)
Received: from TGXML338.toshiba.local ([169.254.4.194]) by tgxml329.toshiba.local ([133.199.60.16]) with mapi id 14.03.0123.003; Wed, 26 Jun 2013 23:28:06 +0900
From: yoshihiro.ohba@toshiba.co.jp
To: xvilajosana@eecs.berkeley.edu, 6tsch@ietf.org
Thread-Topic: [6tsch] simulation for random schedule allocation
Thread-Index: AQHOcdRxZ3pDJXAb0ky1Inthw566LZlIC45Q
Date: Wed, 26 Jun 2013 14:28:05 +0000
Message-ID: <674F70E5F2BE564CB06B6901FD3DD78B12D2691A@tgxml338.toshiba.local>
References: <CALEMV4b27w3=hCkovP1JpQwQnN_jcu98hGPtjT349LhFBPb0XQ@mail.gmail.com>
In-Reply-To: <CALEMV4b27w3=hCkovP1JpQwQnN_jcu98hGPtjT349LhFBPb0XQ@mail.gmail.com>
Accept-Language: ja-JP, en-US
Content-Language: ja-JP
x-originating-ip: [133.199.18.204]
msscp.transfermailtomossagent: 103
Content-Type: multipart/alternative; boundary="_000_674F70E5F2BE564CB06B6901FD3DD78B12D2691Atgxml338toshiba_"
MIME-Version: 1.0
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: Wed, 26 Jun 2013 14:28:21 -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: 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