[Roll] Fwd: Revisiting the Trickle Algorithm

Omprakash Gnawali <gnawali@cs.uh.edu> Mon, 19 January 2015 15:10 UTC

Return-Path: <gnawali@cs.uh.edu>
X-Original-To: roll@ietfa.amsl.com
Delivered-To: roll@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 1B7DD1B2AA2 for <roll@ietfa.amsl.com>; Mon, 19 Jan 2015 07:10:46 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -3.588
X-Spam-Level:
X-Spam-Status: No, score=-3.588 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, FM_FORGED_GMAIL=0.622, RCVD_IN_DNSWL_MED=-2.3, T_RP_MATCHES_RCVD=-0.01] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id Doqh3edalfXk for <roll@ietfa.amsl.com>; Mon, 19 Jan 2015 07:10:42 -0800 (PST)
Received: from dijkstra.cs.uh.edu (dijkstra.cs.uh.edu [129.7.240.12]) by ietfa.amsl.com (Postfix) with ESMTP id 204071B2A9A for <roll@ietf.org>; Mon, 19 Jan 2015 07:10:42 -0800 (PST)
Received: from localhost (dijkstra.cs.uh.edu [127.0.0.1]) by dijkstra.cs.uh.edu (Postfix) with ESMTP id A390A23CA69 for <roll@ietf.org>; Mon, 19 Jan 2015 09:10:40 -0600 (CST)
X-Virus-Scanned: amavisd-new at cs.uh.edu
Received: from dijkstra.cs.uh.edu ([127.0.0.1]) by localhost (dijkstra.cs.uh.edu [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id RAFUA90408eU for <roll@ietf.org>; Mon, 19 Jan 2015 09:10:37 -0600 (CST)
Received: from it.cs.uh.edu (unknown [129.7.240.6]) by dijkstra.cs.uh.edu (Postfix) with ESMTP id CA01A23CA5A for <roll@ietf.org>; Mon, 19 Jan 2015 09:10:37 -0600 (CST)
Received: from mail-pd0-f173.google.com (mail-pd0-f173.google.com [209.85.192.173]) by it.cs.uh.edu (Postfix) with ESMTP id 15ED42A28075 for <roll@ietf.org>; Mon, 19 Jan 2015 09:20:08 -0600 (CST)
Received: by mail-pd0-f173.google.com with SMTP id fp1so12223689pdb.4 for <roll@ietf.org>; Mon, 19 Jan 2015 07:10:36 -0800 (PST)
X-Received: by 10.68.208.65 with SMTP id mc1mr45077129pbc.111.1421680236989; Mon, 19 Jan 2015 07:10:36 -0800 (PST)
MIME-Version: 1.0
Received: by 10.70.125.169 with HTTP; Mon, 19 Jan 2015 07:10:16 -0800 (PST)
In-Reply-To: <CAErDfUSewgX8i-qrZUTAv6S-7XQ5Vu2O5Z1qj0pUT=akwg3MiA@mail.gmail.com>
References: <CAPm4LDTj3-ZTZGi86ttgqNuTSRnEBUY59rAnxmr_DMvuhNWGGA@mail.gmail.com> <CAErDfUSewgX8i-qrZUTAv6S-7XQ5Vu2O5Z1qj0pUT=akwg3MiA@mail.gmail.com>
From: Omprakash Gnawali <gnawali@cs.uh.edu>
Date: Mon, 19 Jan 2015 09:10:16 -0600
Message-ID: <CAErDfUQ4CD01wGvqwLBQxOw8=Nb6R6rHCesc4VFp06gOH08d4Q@mail.gmail.com>
To: ROLL WG <roll@ietf.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: <http://mailarchive.ietf.org/arch/msg/roll/zZiOLOV01oCcEpzOJThRe_JkDo0>
Subject: [Roll] Fwd: Revisiting the Trickle Algorithm
X-BeenThere: roll@ietf.org
X-Mailman-Version: 2.1.15
Precedence: list
Reply-To: Routing Over Low power and Lossy networks <roll@ietf.org>
List-Id: Routing Over Low power and Lossy networks <roll.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/roll>, <mailto:roll-request@ietf.org?subject=unsubscribe>
List-Archive: <http://www.ietf.org/mail-archive/web/roll/>
List-Post: <mailto:roll@ietf.org>
List-Help: <mailto:roll-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/roll>, <mailto:roll-request@ietf.org?subject=subscribe>
X-List-Received-Date: Mon, 19 Jan 2015 15:10:46 -0000

---------- Forwarded message ----------
From: Omprakash Gnawali <gnawali@cs.uh.edu>
Date: Mon, Jan 19, 2015 at 9:01 AM
Subject: Re: Revisiting the Trickle Algorithm
To: badis DJAMAA <badis.djamaa@ieee.org>
Cc: ROLL WG <roll@ietf.org>rg>, "Thomas Heide Clausen (work)"
<T.Clausen@computer.org>rg>, Philip Levis <pal@cs.stanford.edu>du>, JeongGil
Ko <jgko@cs.jhu.edu>du>, JeongGil Ko <jeonggil.ko@gmail.com>om>, Jonathan
Hui <jonhui@cisco.com>om>, Ines Robles <maria.ines.robles@ericsson.com>om>,
Michael Richardson <mcr+ietf@sandelman.ca>


It is a good idea to explore how to make Trickle work better.

Could you discuss the tradeoffs due to the proposed modification? Are
there some scenarios that will be worse off due to the changes?

Did you consider minor variations to your scheme - e.g., rather than
just the first interval starting at 0, how about the first n intervals
starting at 0 rather than I/2?

It will be useful to poll the community what they use for Imin and do
experiments with similar Imin.

- om_p


On Mon, Jan 19, 2015 at 7:51 AM, badis DJAMAA <badis.djamaa@ieee.org> wrote:
> Dear all
>
> We have been working with Trickle for more than two years. A 4-page document
> available here https://dspace.lib.cranfield.ac.uk/handle/1826/9033  shows
> that by a simple modification to Trickle, a great decrease in the
> propagation time can be achieved without affecting Trickle's scalability.
>
> The results are backed by extensive simulations and large-scale testbed
> experiments. In-depth explanation along with more extensive results are
> under analysis to be announced very soon.
>
> In a nutshell the modification recommends to change step 2, section 4.2. of
> RFC6206 as follows
>
> Old:
>
>  2.  When an interval begins, Trickle resets c to 0 and sets t to a
>        random point in the interval, taken from the range [I/2, I), that
>        is, values greater than or equal to I/2 and less than I.  The
>        interval ends at I.
>
> New:
>
>  2.  When an interval begins, Trickle resets c to 0 and sets t to a
>        random point in the interval, taken from the range:
>
>        o   [0, Imin) if the interval began as result of step 6
>          (because of an inconsistency or external events).
>
>    o   [I/2, I), otherwise(the interval began because of step 1 or step 5)
>
> The rationale behind this modification is briefly explained here
> https://dspace.lib.cranfield.ac.uk/handle/1826/9033
>
> any comment is warmly welcomed
>
> All the best
> badis