Re: [Roll] Revisiting the Trickle Algorithm

Badis Djamaa <badis.djamaa@gmail.com> Mon, 19 January 2015 23:43 UTC

Return-Path: <badis.djamaa@gmail.com>
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 BCF7A1B2D29 for <roll@ietfa.amsl.com>; Mon, 19 Jan 2015 15:43:13 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, SPF_PASS=-0.001] 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 lyS1A7cEVEjV for <roll@ietfa.amsl.com>; Mon, 19 Jan 2015 15:43:11 -0800 (PST)
Received: from mail-qc0-x235.google.com (mail-qc0-x235.google.com [IPv6:2607:f8b0:400d:c01::235]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id D1D581ACE82 for <roll@ietf.org>; Mon, 19 Jan 2015 15:43:10 -0800 (PST)
Received: by mail-qc0-f181.google.com with SMTP id l6so19800855qcy.12 for <roll@ietf.org>; Mon, 19 Jan 2015 15:43:10 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type; bh=M1bIgIHJ4frE0XKteIRTgqnneesuqduU9INNun+IzJk=; b=cQXJ92hYVf42b/5ptC65lReUFUyqpwkO+SOrpYdZq/SZs945Aw7hm1dpUxA29uxaw5 HSytcKES7/NBemBhxvphtxYoXwX0wGr2lOb+gjpfwz/1RwS7oitFtzk+cuAcrRC7UTkM azUHfxOoiKXE+ygWIiiPmgnta646AUDZq6B+uWkaDIHRhZ+jrvjz4pmKIuPAALarO8Ta ifJdDyLw49QZjyt0hO5yC/b1WHsrhD7LbcFZ2kWz1VCI3O1F2Q64V2t5Yvi5eV7rQ8Z8 OCzGCr21AnAPc2uLlcAi6k5IpAquLTadjjDx305YjaKmlxhMw0uFTM4PxtHNXh9sXPHg Ikkg==
MIME-Version: 1.0
X-Received: by 10.224.28.198 with SMTP id n6mr52623736qac.15.1421710989946; Mon, 19 Jan 2015 15:43:09 -0800 (PST)
Received: by 10.140.27.145 with HTTP; Mon, 19 Jan 2015 15:43:09 -0800 (PST)
In-Reply-To: <CAPm4LDRY4dUYgshFN96eJbOT4Fv18N9yOQBXeO23akRmdQ_KVg@mail.gmail.com>
References: <CAPm4LDTj3-ZTZGi86ttgqNuTSRnEBUY59rAnxmr_DMvuhNWGGA@mail.gmail.com> <CAErDfUSewgX8i-qrZUTAv6S-7XQ5Vu2O5Z1qj0pUT=akwg3MiA@mail.gmail.com> <CAPm4LDRY4dUYgshFN96eJbOT4Fv18N9yOQBXeO23akRmdQ_KVg@mail.gmail.com>
Date: Mon, 19 Jan 2015 23:43:09 +0000
Message-ID: <CAPm4LDRFqO4AhrPJjgWfn9e_XncFFYsZ=ZgkMcdvJNpaBFrc2g@mail.gmail.com>
From: Badis Djamaa <badis.djamaa@gmail.com>
To: Omprakash Gnawali <gnawali@cs.uh.edu>
Content-Type: multipart/alternative; boundary=001a11c2cc9a87766a050d09e26e
Archived-At: <http://mailarchive.ietf.org/arch/msg/roll/kY-OcROZGQIF20-JcQ2tsf83hPQ>
Cc: Jonathan Hui <jonhui@cisco.com>, "Thomas Heide Clausen \(work\)" <T.Clausen@computer.org>, ROLL WG <roll@ietf.org>, badis DJAMAA <badis.djamaa@ieee.org>, JeongGil Ko <jgko@cs.jhu.edu>
Subject: Re: [Roll] 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 23:43:14 -0000

Thank you Gnawali for your comments,



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



Figure1, page 2 of the document, shows the scheme in its best-case
(lossless networks). From that Figure, we can see a side-effect of the
proposed scheme which can add an extra cost in lossy-networks.



Figure 4 in page 4, clearly shows this side-effect in lossy networks. But
results in Figure 5 ( network with 90% physical loss rate) shows that the
extra cost only affects a few following intervals and disappears later.
Also Figure 5 shows that this additional cost does not affect trickle
scalability.



When generating heavy inconsistencies (periodically injecting new packets),
testbed results depicted in third row of graphs in Figure 6, page 4, shows
a bigger additional cost because of heavy inconsistent traffic being
generated.



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



Because of the side-effect depicted in Figure 4, the additional cost
increases if we go for n intervals. Generally speaking, Trickle's
scalability might remain logarithmic, because the extra cost only depends
on losses. However, the extra cost is noticeable under heavy inconsistent
traffic and wastes energy.



Note however, that we made a small variation to the scheme by letting a
node that transmitted in an Imin interval to start listening
immediately (put c=0). Preliminary results look promising and show that the
side-effect can be addressed.



More results are being analysed to see whether other side-effects can
emerge.



Best, badis

 On 19 January 2015 at 15:01, Omprakash Gnawali <gnawali@cs.uh.edu> wrote:

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