Re: [6tsch] On the fly scheduling

Kris Pister <ksjp@berkeley.edu> Fri, 04 October 2013 14:57 UTC

Return-Path: <ksjp@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 6C9DB21F9E11 for <6tsch@ietfa.amsl.com>; Fri, 4 Oct 2013 07:57:07 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.998
X-Spam-Level:
X-Spam-Status: No, score=-2.998 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, HTML_MESSAGE=0.001, J_CHICKENPOX_64=0.6, 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 p7gl8zfoUNVL for <6tsch@ietfa.amsl.com>; Fri, 4 Oct 2013 07:56:52 -0700 (PDT)
Received: from mail-pb0-f44.google.com (mail-pb0-f44.google.com [209.85.160.44]) by ietfa.amsl.com (Postfix) with ESMTP id 6964F21F9396 for <6tsch@ietf.org>; Fri, 4 Oct 2013 07:54:21 -0700 (PDT)
Received: by mail-pb0-f44.google.com with SMTP id xa7so4107661pbc.31 for <6tsch@ietf.org>; Fri, 04 Oct 2013 07:54:21 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:message-id:date:from:user-agent:mime-version:to :subject:references:in-reply-to:content-type; bh=8xV6nQPUypTRnt+AnpHxeXROD3u7KL7qdGMEhphtM5E=; b=I3uJf4dp0rK1aOUr7o5yeYMmj2qGhlyHqSAkZvHFfl8jZyZq4cyBWLU9jbjEIc+NmT zRRi2SzBLEMoJEQGprFgbD2MdiQ+lJ15UQGvhmC/o/Tqlc8tUmyCqZ7KLzdXx6X26hrF STkByCTGP9huWXmo0RFxqEPAPTM7h9DIHdVs4EjqDBQz8IlFW/tuxSSAfIOPINwnu1Fu nMIbGabMl7O3S3YKw1fbkqeh2msB1viSs/eG8EwG+HhiF0cCiJKhuSgzDvRokkFQ1cEn irF8sn3L/v6+O7mEsiEtvdcL+vGcGfBa+6yB3JvxVi3Cem/mFQzWrhpaMjmv0P8wGopn ruTw==
X-Gm-Message-State: ALoCoQlKcAm6KH2gjRYrdDvBBUaY0c36jRRDr374lGizBbFmLjrwNi9pB6jpYD82HMOtcbatfbd0
X-Received: by 10.66.246.229 with SMTP id xz5mr15948475pac.128.1380898460006; Fri, 04 Oct 2013 07:54:20 -0700 (PDT)
Received: from [128.32.32.89] (dhcp-32-89.EECS.Berkeley.EDU. [128.32.32.89]) by mx.google.com with ESMTPSA id iu7sm15208101pbc.45.1969.12.31.16.00.00 (version=TLSv1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Fri, 04 Oct 2013 07:54:19 -0700 (PDT)
Message-ID: <524ED6A0.2030702@berkeley.edu>
Date: Fri, 04 Oct 2013 07:54:24 -0700
From: Kris Pister <ksjp@berkeley.edu>
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:17.0) Gecko/20130801 Thunderbird/17.0.8
MIME-Version: 1.0
To: 6tsch@ietf.org
References: <CAH7SZV86jyR6d3LbOqqFswzUN3brPdNni3GFuD-yeDYPYktNZQ@mail.gmail.com> <CALEMV4atkUjm0yRG1oOo=ayNL2jjd1ygSc_v68JuUeCpoH4+EA@mail.gmail.com> <E045AECD98228444A58C61C200AE1BD8414CEBBD@xmb-rcd-x01.cisco.com> <F085911F642A6847987ADA23E611780D1859FA68@hoshi.uni.lux> <CADJ9OA_itqDTLObLX-bByT1cQ8s=CXvdiNkvmsSUsk-z+7CnUA@mail.gmail.com> <CAAzoce7AYoek5uL93t3bbfXnkPVwQeik4_gnytkyp6TD8YpqAw@mail.gmail.com> <CADJ9OA9kbCQeY6VtoZtSVMw-XC_Kw5b=u+8mc-R0eocR-ij-nQ@mail.gmail.com> <F085911F642A6847987ADA23E611780D185A39B6@hoshi.uni.lux> <E045AECD98228444A58C61C200AE1BD8414D2118@xmb-rcd-x01.cisco.com>
In-Reply-To: <E045AECD98228444A58C61C200AE1BD8414D2118@xmb-rcd-x01.cisco.com>
Content-Type: multipart/alternative; boundary="------------000703060406070106070906"
Subject: Re: [6tsch] On the fly scheduling
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: Fri, 04 Oct 2013 14:57:08 -0000

On 10/4/2013 2:30 AM, Pascal Thubert (pthubert) wrote:
> As you see, even implementing such a simple strategy can already be 
> quite some work in a constrained device. 

Or it can be really really simple and still quite effective for 90% of 
use cases.

One very simple algorithm:
  * each node knows its own desired bandwidth (in cells/sec) to the 
destination.
  * each node knows how many cells/sec it has as inputs from children
  * each node knows how many cells/sec it has as outputs to parents

Here's my super-sophisticated proposal:
if (outputs <  inputs+self) pick the best parent and add a new cell.
if (outputs > inputs+self + 1) pick the worst cell and delete it

This is not optimal.  It guarantees some wasted bandwidth.  But it works 
great in most situations,
and is pretty easy to implement.  If the number "1" is open to some 
interpretation (should be in
cells/superframe, possibly include some time delay) you can minimize churn.
Desired bandwidth can change based on application performance (e.g. 
round-trip latency)
or MAC performance (measured cell PDR, queue length).  But none of that 
is really necessary to get
a good network up and running.

Lance Doherty did some simulations of this in matlab back in 2004. I'll 
see if I can dig those up.

ksjp