Re: [6tsch] simulation for random schedule allocation
Thomas Watteyne <watteyne@eecs.berkeley.edu> Wed, 26 June 2013 06:31 UTC
Return-Path: <twatteyne@gmail.com>
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 712CE21F9C35 for <6tsch@ietfa.amsl.com>; Tue, 25 Jun 2013 23:31:34 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.977
X-Spam-Level:
X-Spam-Status: No, score=-1.977 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001, NO_RELAYS=-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 mgP4moDilB6s for <6tsch@ietfa.amsl.com>; Tue, 25 Jun 2013 23:31:33 -0700 (PDT)
Received: from mail-pb0-x229.google.com (mail-pb0-x229.google.com [IPv6:2607:f8b0:400e:c01::229]) by ietfa.amsl.com (Postfix) with ESMTP id 8EB2F21E8116 for <6tsch@ietf.org>; Tue, 25 Jun 2013 23:31:33 -0700 (PDT)
Received: by mail-pb0-f41.google.com with SMTP id rp16so13780739pbb.14 for <6tsch@ietf.org>; Tue, 25 Jun 2013 23:31:33 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:from:date :x-google-sender-auth:message-id:subject:to:content-type; bh=8wQHT3sjwiqcJbgyRpSLubrb7EBzFluCHkCy9gSKHcA=; b=FSOjVyEr9fasMI+bdDoa+d5YD7e4N5a2exn8nyBT/HPQsvj/V4nr1+shU42UiXIBON 4Dwy2pSWYmzyFbnkNVdp6TQXt7c1hwcNCCqQowClEsgc5GY+YFrWMUsMUEJmk3AjZ/0/ XN1se6ad0xccE+k7oN7EEQOAT3ZP8CGO4ey/UCuvjLOBjk65815KaTAKlDIjPZLtrroR ezxcdkUls6UwzWKD9D3gmxUxpdfN4iqwiczs9BekA38UvDpkg/xA1E7Gxan5LCKWVTUv kMAQxUCjRB60yW0oLyEs2XUazDHURJKbOLG/lcnjtTTC/x/vcs8hgW4t6PPLwH1DyTSH 7okg==
X-Received: by 10.66.122.163 with SMTP id lt3mr3140362pab.219.1372228293324; Tue, 25 Jun 2013 23:31:33 -0700 (PDT)
MIME-Version: 1.0
Sender: twatteyne@gmail.com
Received: by 10.66.147.228 with HTTP; Tue, 25 Jun 2013 23:31:13 -0700 (PDT)
In-Reply-To: <CALEMV4bP5PJMA5v+3kS24CyocjG8_FKC0FXGJDAP3bZ8zgKvAA@mail.gmail.com>
References: <CALEMV4bP5PJMA5v+3kS24CyocjG8_FKC0FXGJDAP3bZ8zgKvAA@mail.gmail.com>
From: Thomas Watteyne <watteyne@eecs.berkeley.edu>
Date: Tue, 25 Jun 2013 23:31:13 -0700
X-Google-Sender-Auth: Nf-6zKQTBZwImJk3qfsGH4Jzvt0
Message-ID: <CADJ9OA9u03YXOCVL7835DCq6Aq9Qq7S-77yGNBUfJKNc4XbV3w@mail.gmail.com>
To: "6tsch@ietf.org" <6tsch@ietf.org>
Content-Type: multipart/alternative; boundary="047d7bf16048f975c604e008cbe0"
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 06:31:34 -0000
Xavi, Very cool! I have a bit of a hard time interpreting your results, or at least using them to answer my question. Maybe you can shine some light on the following scenario? Don't hesitate to shout if I missed something. I have a neighborhood of N nodes. As a first step, we can assume all nodes hear all nodes, i.e. the neighborhood is fully meshed. A more realistic scenario can come later. Some of these nodes schedule cells to one another, using the purely random approach. Once this is done, they start communicating over those cells and, for some cells, *realize* that there are collisions. They then decide to * reallocate* these cells to different (random) locations in the schedule. In the "healthy" case this process goes on until there are no more collisions, i.e. until the pairs of motes are communicating on cells which are not actively used by any other pair in the neighborhood. In this "healthy" case, if I plot the number of reallocations as a function of time, and assuming that all motes are switched on at the same time (which is very artificial, but "bad case" scenario), I expect to see the number of reallocation first increase, then come back down to 0. I expect the time to converge to zero to increase as the load increases. The load can be changed by adding more motes into my neighborhood, or allocating more cells per pair of neighbor nodes (both cases are equivalent?). At some threshold load, however, we switch from the "healthy" state to the "collapse" state. In the latter, the number of reallocations never converges back to zero, as the network is constantly busy detecting and fixing collisions. This can be considered a network collapse, which is a very bad outcome, since the nodes are constantly busy communicating, but the network is not relaying data. This can probably be easily described using aloha-type analysis. What I'd like to know is that threshold load, i.e. the load at which this network switch from "healthy" to "collapse". If this threshold is very high, we might consider the random scheduling for sparse network; if it's very low, we cannot as it will never work well. There are a couple of items I underlined above which I believe are important: - "realizing" that there is a collision is not immediate for a node. We have discussed the possibility of comparing statistics of several cells in the same bundle. As a first simulation step, we could consider that a single collision triggers a reallocation. In a more realistic scenario, the simulation could model the actual statistics and the little algorithm which looks at them and triggers a reallocation. This delay may have an impact on the performance of the network, and the threshold load. - reallocating is not an immediate thing, as it requires the two neighbors to send a couple of "negotiation" packets back-and-forth. The exact protocol isn't defined yet, but it will also introduce some latency. Some strange side-effect is that, during some period of time, the new cell will have been allocated, but the old one not deleted yet, possibly resulting in even more collisions. I have the impression that your simulation does not (yet) model the dynamic reallocation of cells. I haven't looked at the code, so please let me know if my impression is wrong. Thoughts? What do you think the next steps are? Anything other people from the group can help with (or have already done)? Thomas On Tue, Jun 25, 2013 at 5:24 PM, Xavier Vilajosana Guillen < xvilajosana@eecs.berkeley.edu> wrote: > Dear all, I plotted some of the results in case this can help on the > discussion about probabilistic selection of slots. > > Note that I am playing with a 101 * 16 schedule and trying to allocate > from few links to almost all the schedule. > > This plots correspond to one of the simulated nodes (of a 50 node network) > with a high neighbour density. (the rest are quite similar and vary a > little depending on the number of neighbours they have, nothing relevant > though) > > Other cases can be simulated but before I will wait for your comments and > suggestions so I spent the time on the right direction. > > kind regards, > > Xavi > > _______________________________________________ > 6tsch mailing list > 6tsch@ietf.org > https://www.ietf.org/mailman/listinfo/6tsch > >
- 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