Re: [6tsch] On the fly scheduling

Qin Wang <qinwang@berkeley.edu> Thu, 03 October 2013 19:50 UTC

Return-Path: <qinwang@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 0318721F8D62 for <6tsch@ietfa.amsl.com>; Thu, 3 Oct 2013 12:50:09 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.976
X-Spam-Level:
X-Spam-Status: No, score=-2.976 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, FM_FORGED_GMAIL=0.622, HTML_MESSAGE=0.001, 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 tqPHGTQCN4qA for <6tsch@ietfa.amsl.com>; Thu, 3 Oct 2013 12:49:57 -0700 (PDT)
Received: from mail-ie0-f175.google.com (mail-ie0-f175.google.com [209.85.223.175]) by ietfa.amsl.com (Postfix) with ESMTP id E072121F9396 for <6tsch@ietf.org>; Thu, 3 Oct 2013 12:33:08 -0700 (PDT)
Received: by mail-ie0-f175.google.com with SMTP id e14so6782017iej.34 for <6tsch@ietf.org>; Thu, 03 Oct 2013 12:33:08 -0700 (PDT)
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:date :message-id:subject:from:to:cc:content-type; bh=tJkFhg5IV7QtobbThcZz8GWSguZcOMPdcwpKtwkE4k0=; b=Kib0Yig6KWoQFx2AviLqYCtcfgX/RyHzPKJUFOh8CQxtNjwJWLeeT7U1DXjQfNxWLc bu2XCXqkVQLsfyhlGSUIjCuGYu/PV+gGLTyVHG2Cx7byI5Yjc9vzhUHlqVKgTNiJm1UB JPBJt8WGFWmHGucMZLhyKcUjnHGCRjJHAWbvomk6XU4B7G1p4o5M2Y2JZFNBNh8TQ8Lz gtdoHbsVoPmqxpw4xfQnowS9yrCrSoUXZTXuMPmF+g0AxSGHA0ycmqOr64HsS4CQhYZ4 MjPU2Y7ftZgJ4PBECBCJQbDSfq4B3iKz9D2wFnPs4qYNSbjtzBs1L2dUMvFi3iAc1O68 j/ig==
X-Gm-Message-State: ALoCoQmQixMHm7RSB+tYG6PsbuKvbFqU825cKQPx2cs0yg52FfCvKL0ES8rtkk3QX6//XnMsLrxP
MIME-Version: 1.0
X-Received: by 10.50.13.104 with SMTP id g8mr3539899igc.30.1380828788221; Thu, 03 Oct 2013 12:33:08 -0700 (PDT)
Received: by 10.64.130.234 with HTTP; Thu, 3 Oct 2013 12:33:08 -0700 (PDT)
In-Reply-To: <CADJ9OA_itqDTLObLX-bByT1cQ8s=CXvdiNkvmsSUsk-z+7CnUA@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>
Date: Fri, 4 Oct 2013 03:33:08 +0800
Message-ID: <CAAzoce7AYoek5uL93t3bbfXnkPVwQeik4_gnytkyp6TD8YpqAw@mail.gmail.com>
From: Qin Wang <qinwang@berkeley.edu>
To: Thomas Watteyne <watteyne@eecs.berkeley.edu>
Content-Type: multipart/alternative; boundary=089e013c69c66af5ac04e7db4114
Cc: 6TSCH <6tsch@ietf.org>
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 19:50:09 -0000

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
>
>