Re: [6tsch] On the fly scheduling
Thomas Watteyne <watteyne@eecs.berkeley.edu> Thu, 03 October 2013 20:27 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 7210921E80C9 for <6tsch@ietfa.amsl.com>; Thu, 3 Oct 2013 13:27:47 -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 t6k3-uvtdp9u for <6tsch@ietfa.amsl.com>; Thu, 3 Oct 2013 13:27:39 -0700 (PDT)
Received: from mail-pb0-x22c.google.com (mail-pb0-x22c.google.com [IPv6:2607:f8b0:400e:c01::22c]) by ietfa.amsl.com (Postfix) with ESMTP id E28B321F9AE3 for <6tsch@ietf.org>; Thu, 3 Oct 2013 13:11:35 -0700 (PDT)
Received: by mail-pb0-f44.google.com with SMTP id xa7so2957087pbc.17 for <6tsch@ietf.org>; Thu, 03 Oct 2013 13:11:35 -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=QPjeQyv5Tc9RVw39/cTACPlwYfI1ZjohVQEmmbB2QT4=; b=sWPsEvje1npUOOVeoRSxLutq+nfGoA4tjJ2wqTqHNzKezOu/1mGXI7cbGk7vGwksZF +nKeyFo28YQ8s253CQIB6MHrBLiqEBj9XEqnSJ3feLWlLcpQ8zSceiLuNpnqDHb1JEJW u0Ab/NtupTZ0272BEV2thRUM0r51y9te/GdasYjvoiNVHph3GVgMQbXvXr+P0DxNFs5L /g6Z7lr2aSZ+gUAJ7tKyQp6zG42AODoFXdZUVMH7BdhC2yguYNrz4sajZL3o1Elw8R6J URgimBsop1pnrVeeszM/EWzvauz/V/hNd9cJHAWvnlktY4l9dbQ3ZK6jGpEOxnZDyUBx YmnQ==
X-Received: by 10.66.121.201 with SMTP id lm9mr11433584pab.80.1380831095570; Thu, 03 Oct 2013 13:11:35 -0700 (PDT)
MIME-Version: 1.0
Sender: twatteyne@gmail.com
Received: by 10.66.147.193 with HTTP; Thu, 3 Oct 2013 13:11:15 -0700 (PDT)
In-Reply-To: <CAAzoce7AYoek5uL93t3bbfXnkPVwQeik4_gnytkyp6TD8YpqAw@mail.gmail.com>
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>
From: Thomas Watteyne <watteyne@eecs.berkeley.edu>
Date: Thu, 03 Oct 2013 13:11:15 -0700
X-Google-Sender-Auth: l4spyEsYLTu5HqbT-zgdvjiao_E
Message-ID: <CADJ9OA9kbCQeY6VtoZtSVMw-XC_Kw5b=u+8mc-R0eocR-ij-nQ@mail.gmail.com>
To: 6TSCH <6tsch@ietf.org>
Content-Type: multipart/alternative; boundary="047d7b2e4ca4f2491604e7dbca87"
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 20:27:48 -0000
That would indeed be clean. On Thu, Oct 3, 2013 at 12:33 PM, Qin Wang <qinwang@berkeley.edu> wrote: > Hi all, > > +1 for the proposal. > > Regarding to how to approach, I agree with Thomas. There is an entity > running on top of 6top, which reads queue information and other statistics > information from 6top, sends instruction like create/delete softcells to > 6top. I think we can use the design methodology of Objective Function in > RPL, i.e. define the statistics information and the interface to/from 6top, > and leave the specific algorithm open. > > What do you think? > > Qin > > > > > On Fri, Oct 4, 2013 at 12:45 AM, Thomas Watteyne < > watteyne@eecs.berkeley.edu> wrote: > >> +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 >>> >>> >> >> _______________________________________________ >> 6tsch mailing list >> 6tsch@ietf.org >> https://www.ietf.org/mailman/listinfo/6tsch >> >> >
- [6tsch] On the fly scheduling Prof. Diego Dujovne
- Re: [6tsch] On the fly scheduling Xavier Vilajosana Guillen
- Re: [6tsch] On the fly scheduling Pascal Thubert (pthubert)
- Re: [6tsch] On the fly scheduling Maria Rita PALATTELLA
- Re: [6tsch] On the fly scheduling Thomas Watteyne
- Re: [6tsch] On the fly scheduling Maria Rita PALATTELLA
- Re: [6tsch] On the fly scheduling Qin Wang
- Re: [6tsch] On the fly scheduling Thomas Watteyne
- Re: [6tsch] On the fly scheduling Maria Rita PALATTELLA
- Re: [6tsch] On the fly scheduling Pascal Thubert (pthubert)
- Re: [6tsch] On the fly scheduling Qin Wang
- Re: [6tsch] On the fly scheduling Kris Pister
- Re: [6tsch] On the fly scheduling Guillaume Gaillard
- Re: [6tsch] On the fly scheduling Qin Wang
- Re: [6tsch] On the fly scheduling Guillaume Gaillard