Re: [6tsch] On the fly scheduling

Thomas Watteyne <watteyne@eecs.berkeley.edu> Thu, 03 October 2013 17:03 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 1D9F921E80E9 for <6tsch@ietfa.amsl.com>; Thu, 3 Oct 2013 10:03:08 -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 NIe1moXvqOLO for <6tsch@ietfa.amsl.com>; Thu, 3 Oct 2013 10:03:00 -0700 (PDT)
Received: from mail-pd0-x231.google.com (mail-pd0-x231.google.com [IPv6:2607:f8b0:400e:c02::231]) by ietfa.amsl.com (Postfix) with ESMTP id 0B49511E8150 for <6tsch@ietf.org>; Thu, 3 Oct 2013 09:45:38 -0700 (PDT)
Received: by mail-pd0-f177.google.com with SMTP id y10so2715575pdj.36 for <6tsch@ietf.org>; Thu, 03 Oct 2013 09:45:38 -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:message-id :subject:to:content-type; bh=4raz8HtuaTDmPWWjRAQCV5jmKzhKd2yC1t63I2gRVmg=; b=jUx/35iZaatxaHRFvDxmJ6DWUCIN9f7+sj7IR50mYoTYs5bD7ypjKoODjnwo8qOF2y KcS/geMGA9Ka3xMR/AK/c8veFiA823dmF2PbgJvPaqZWZk/c7bqrjNtrLPDy7tI2AT3I 5lqmHl695aia9ir2s9lM8DTWPjEI0mezp77eHMhVvcWovidV+UIv2u7PHbn4fHw6tOxt naqPekUix9Ae7qzFcQke6dDxgEE6p8T9hKEH4FAC9bk+DH/kR2WdXWFxIXZD8+YUcUWG 4kUupVb7YuJRvZkOzQ3nQqF/Y8XrMHoIJiH1sltBA7SFIyHkrQ53pMjZEi1iKxpzMbe7 SXTA==
X-Received: by 10.66.121.201 with SMTP id lm9mr10556108pab.80.1380818738773; Thu, 03 Oct 2013 09:45:38 -0700 (PDT)
MIME-Version: 1.0
Sender: twatteyne@gmail.com
Received: by 10.66.147.193 with HTTP; Thu, 3 Oct 2013 09:45:17 -0700 (PDT)
In-Reply-To: <F085911F642A6847987ADA23E611780D1859FA68@hoshi.uni.lux>
References: <CAH7SZV86jyR6d3LbOqqFswzUN3brPdNni3GFuD-yeDYPYktNZQ@mail.gmail.com> <CALEMV4atkUjm0yRG1oOo=ayNL2jjd1ygSc_v68JuUeCpoH4+EA@mail.gmail.com> <E045AECD98228444A58C61C200AE1BD8414CEBBD@xmb-rcd-x01.cisco.com> <F085911F642A6847987ADA23E611780D1859FA68@hoshi.uni.lux>
From: Thomas Watteyne <watteyne@eecs.berkeley.edu>
Date: Thu, 3 Oct 2013 09:45:17 -0700
X-Google-Sender-Auth: R0SsSS2s1EVoyv3VZOnwIbNbnIE
Message-ID: <CADJ9OA_itqDTLObLX-bByT1cQ8s=CXvdiNkvmsSUsk-z+7CnUA@mail.gmail.com>
To: 6TSCH <6tsch@ietf.org>
Content-Type: multipart/alternative; boundary=047d7b2e4ca46c859904e7d8eae5
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: Thu, 03 Oct 2013 17:03:08 -0000

+1 for the proposal.

I believe it could be a very simple and powerful approach. Diego, would you
agree that this can be considered a distributed mechanism sitting on top of
6top?

That is, 6top provides:

   - commands to modify the number of soft cells in a bundle
   - commands to retrieve usage statistics of the cells/bundles

The way I see it, your proposal consists of an algorithm which feeds from
the usage statistics and triggers changes in the number of soft cells in a
bundle. Correct?

The questions to answer for now is whether 6top provides the right
statistics.

Maria Rita, one big difference with TASA is that OTF scheduling is
distributed.

Thomas

On Thu, Oct 3, 2013 at 9:11 AM, Maria Rita PALATTELLA <
maria-rita.palattella@uni.lu> wrote:

>  Diego,( all)
>
> what you are suggesting (i.e., reserve cells based on queue size, delay)
> is actually the main idea behind TASA (Traffic Aware Scheduling Algorithm).
>
> TASA builds the schedule based on the local (number of pkt generated by
> the node) and global queue level ( i.e., local + pkt to be forwarded,
> generated by children). It gives priority to nodes with longer queues and
> it aims to reduce the latency for delivering the pkt. At the same time
> while building the schedule it minimizes the number of scheduled cells in
> order to reduce the network duty cycle.
> TASA is centralized and thus it assumes that the PCE has all the info
> needed for setting up the schedule. in other words, it knows the traffic
> generated by each nodes, and the paths followed by each pkt.
> With a "on the fly solution", we will not need to know all this info a
> priori. but we will use 6top monitoring functions and the control flows
> message for scheduling the cells.
>
> Btw, I agree with all the points raised up by Xavi.  We will have to
> address his questions.
>
> And I support Pascal's suggestions about how to deal with bundle.
>
> Maria Rita
>
>
>  ------------------------------
> *From:* 6tsch-bounces@ietf.org [6tsch-bounces@ietf.org] on behalf of
> Pascal Thubert (pthubert) [pthubert@cisco.com]
> *Sent:* Thursday, October 03, 2013 4:09 PM
> *To:* xvilajosana@eecs.berkeley.edu; Prof. Diego Dujovne
>
> *Cc:* 6TSCH
> *Subject:* Re: [6tsch] On the fly scheduling
>
>   +1 too.
>
>
>
> I think that the queue size matters at enqueue but the latency is really
> what we care for at dequeue, that is how long did this device keep this
> message in queue (even if we are far from
>
> buffer bloat conditions in such a device). If one of the 2 conditions
> (size at enqueue, latency at dequeue) is reached then the bundle should be
> increased.
>
>
>
> I agree with Xavi that we want to avoid changing the bundle size all the
> time. We discussed that with Qin and others earlier on the ML. One way of
> increasing the bundle dynamically at a very low cost (not even a
> hysteresis)  is to have it large amount of cells from the start but used
> like 10% by default (xmit/listen happens only once in 10 time slots). A bit
> in the frame indicates whether the next (normally unused) slot will indeed
> be used. The bit can be present in the data and acked in the ack. This can
> also implicitly be triggered for retries.
>
>
>
> Please keep us tuned!
>
>
>
> Cheers,
>
>
>
> PS Note that Cisco has IPR on chaining time slots and flagging whether the
> next is used or not. We already declared our IPR against the architecture
> draft and provided terms.
>
>
>
> Pascal
>
>
>
> *From:* 6tsch-bounces@ietf.org [mailto:6tsch-bounces@ietf.org] *On Behalf
> Of *Xavier Vilajosana Guillen
> *Sent:* jeudi 3 octobre 2013 15:46
> *To:* Prof. Diego Dujovne
> *Cc:* 6TSCH
> *Subject:* Re: [6tsch] On the fly scheduling
>
>
>
> Diego,
>
> +1
>
> it seems to a me a very interesting idea to explore. Maybe we can start
> putting some rules of this mechanism on the table and prepare a simulation.
> I am completely in with that idea.
>
> Some questions arise:
>
> 1-how fast do you react to changes on the queue size to avoid hysteresis
> -- i.e how do you maintain certain stability in the schedule (so you don't
> start installing and removing links very often)
>
> 2-how you map queue size (only one or if more than one queue) to actual
> link requirements
>
> 3-how you recover from link collisions in case of multiple nodes schedule
> the same cells.
>
> 4-how to decide to who (what neighbor) install more links according to
> queue size?
>
>
>
> cheers!
> Xavi
>
>
>
>
>
> On Thu, Oct 3, 2013 at 3:23 AM, Prof. Diego Dujovne <
> diego.dujovne@mail.udp.cl> wrote:
>
> Dear all,
>             I've been looking into the idea of "on the fly scheduling",
> presented on the Sept 27th webex call as "on-the-fly decentralized
> reservation".
> The basic mechanism would be based on analysing the queue size
> on a node and dynamically adapt the number of reserved
> cells to satisfy queue size, delay and/or power
> consumption thresholds.
>             This mechanism would work inside 6top, between pairs of nodes.
> As a first approach, it would be based on the minimal draft.
> What do you think on this starting point?
> I (gladly) receive comments to add or modify this proposal.
>
>                                      Diego
>
>
>
>
> --
> DIEGO DUJOVNE
> Académico Escuela de Ingeniería en Informática y Telecomunicaciones
> Facultad de Ingeniería UDP
> www.ingenieria.udp.cl
> (56 2) 676 8125
> _______________________________________________
> 6tsch mailing list
> 6tsch@ietf.org
> https://www.ietf.org/mailman/listinfo/6tsch
>
>
>
> _______________________________________________
> 6tsch mailing list
> 6tsch@ietf.org
> https://www.ietf.org/mailman/listinfo/6tsch
>
>