Re: [Roll] Revisiting the Trickle Algorithm

Badis Djamaa <badis.djamaa@gmail.com> Mon, 02 February 2015 11:24 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 AB32E1A00EA for <roll@ietfa.amsl.com>; Mon, 2 Feb 2015 03:24:39 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: 0.701
X-Spam-Level:
X-Spam-Status: No, score=0.701 tagged_above=-999 required=5 tests=[BAYES_50=0.8, 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 8s6-XyhBKe8t for <roll@ietfa.amsl.com>; Mon, 2 Feb 2015 03:24:35 -0800 (PST)
Received: from mail-ie0-x233.google.com (mail-ie0-x233.google.com [IPv6:2607:f8b0:4001:c03::233]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 0221D1A00CD for <roll@ietf.org>; Mon, 2 Feb 2015 03:24:35 -0800 (PST)
Received: by mail-ie0-f179.google.com with SMTP id x19so16763854ier.10 for <roll@ietf.org>; Mon, 02 Feb 2015 03:24:34 -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=BMpALFEBKVNLa50HNLhpRx4dwUimUZni/CsObRjRClA=; b=x2DFGLypJXsl9/bLYaHm/6mv0nJCR6VB/vX3oGnbpvITXKnj2xsJKH54fhLJ1WEfz0 j9xhd703f28J8O9B2GCW4LZ2q9hECSl0iCVTrQ+NjLOoYKUYZu0uI8p29pCWvtiS0t/y std53g4VEhY/BU+mMXPRDSMNjQKSoWAAfaOlx53QXx7lzRC3ZkNTtUObCtuJeC+ZC7FM aFInH2yH+ET6oPs4Nwwm2LDArN2lI5MqUM0m5VstMiIl1hxND8Edq5OeV6IQ1loj0jg2 J4p9oIoFh95YRUsoMo8CZygiX655vWMDWJdMtFeWuaVrs7hvl5ekWTOTyESxZnk1qF67 mBuw==
MIME-Version: 1.0
X-Received: by 10.107.151.80 with SMTP id z77mr21683315iod.51.1422876274170; Mon, 02 Feb 2015 03:24:34 -0800 (PST)
Received: by 10.107.52.16 with HTTP; Mon, 2 Feb 2015 03:24:34 -0800 (PST)
In-Reply-To: <a5a973822c943cd683984b5b3cacf57d@xs4all.nl>
References: <CAPm4LDTj3-ZTZGi86ttgqNuTSRnEBUY59rAnxmr_DMvuhNWGGA@mail.gmail.com> <CAErDfUSewgX8i-qrZUTAv6S-7XQ5Vu2O5Z1qj0pUT=akwg3MiA@mail.gmail.com> <CAPm4LDRY4dUYgshFN96eJbOT4Fv18N9yOQBXeO23akRmdQ_KVg@mail.gmail.com> <CAPm4LDRFqO4AhrPJjgWfn9e_XncFFYsZ=ZgkMcdvJNpaBFrc2g@mail.gmail.com> <a5a973822c943cd683984b5b3cacf57d@xs4all.nl>
Date: Mon, 2 Feb 2015 11:24:34 +0000
Message-ID: <CAPm4LDSdp-XbKRzyfuAbUeNmbhPqab8y9mySomj5HXeYyHrJmA@mail.gmail.com>
From: Badis Djamaa <badis.djamaa@gmail.com>
To: consultancy@vanderstok.org
Content-Type: multipart/alternative; boundary=001a1140f5eee1c42e050e1932f1
Archived-At: <http://mailarchive.ietf.org/arch/msg/roll/heipdckOZJzFv9hQNS6wJWDo74E>
Cc: Jonathan Hui <jonhui@cisco.com>, "Thomas Heide Clausen \(work\)" <T.Clausen@computer.org>, Routing Over Low power and Lossy networks <roll@ietf.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, 02 Feb 2015 11:24:39 -0000

Thank you for your comments peter,



Our works on Trickle started in 2012. A first paper [1] was accepted March
2013 and appeared in IEEEXplorer (October 2013). A second work [2] appeared
in Springer WiNet Journal (Jun 2014). Others including variants of the ones
discussed here are under review. I am aware of the useful  MSc thesis
mentioned, cited in our detailed report (
https://dspace.lib.cranfield.ac.uk/handle/1826/9116). If I got it right,
the thesis proposes a one-dimensional abstract mathematical model of the
message count and propagation time of Trickle and “Short-Trickle”. The
author also proposed to make the listen-only period parametric over ALL
intervals.



A quick look at the mentioned pre-print [3] shows that the authors moved
their parametric listen-only period to the Imin interval. Clearly, this
proposition is different than ours, which explicitly proposes to choose t
from [0, Imin), demonstrates why and discusses the trade-offs. Despite
this, the pre-print only models, in function of the parametric listen-only
period, simplistic line-topology lossless scenarios. Note that
mathematically modelling Trickle is also performed in many of the abundant
works related to Trickle such as [4] and [5] (2012).



To the best of our knowledge, and as of today, no published work has
proposed the New-Trickle algorithm as it is described in our first report (
https://dspace.lib.cranfield.ac.uk/handle/1826/9033) even less as detailed
in the second report (https://dspace.lib.cranfield.ac.uk/handle/1826/9116),
which are backed with around a year-worth of extensive public large-scale
testbed experiments and realistic simulations, in accordance with RFC 6206
section 6.7 <https://tools.ietf.org/html/rfc6206#section-6.7>.  Tweaks and
Improvements to Trickle, especially this paragraph:



RFC6206-TEXT: “In our experiences using Trickle, attempts to tweak its
behavior are typically not worth the cost.  As written, the algorithm is
already highly efficient: further reductions in transmissions or response
time come at the cost of failures in edge cases.  Based on our experiences,
we urge protocol designers to suppress the instinct to tweak or improve
Trickle without a great deal of experimental evidence that the change does
not violate its assumptions and break the algorithm in edge cases.”



To this end, we collected over 300 GB of data trace files and experimented
in sever conditions. Other experiments are being run in Indriya, TWIST and
IoTLab testbeds along with other simulations under TOSSIM.



We have been in contact with the first author of Trickle, Prof Philip Levis
(cc’d) with 9-page document, stating our ideas backed with experimental
results (several-months-worth of work) submitted to him just after summer
holidays (exactly on 02-09-2014). We have been in discussion with Prof
Philip since then. I would like to take this opportunity to thank Prof
Philip for his insightful and fruitful comments.



Finally, as both works and the comments seem to agree on the need for
revisiting Trickle, we are happy to collaborate. BTW, I have written an I-D
which can be used as a starting point for discussions. Please let me know
if you are interested.



Any comments and discussions concerning the detailed report are warmly
welcomed

All the best, badis



[1]
http://ieeexplore.ieee.org/xpl/articleDetails.jsp?reload=true&tp=&arnumber=6661808

[2] http://link.springer.com/article/10.1007/s11276-014-0749-3

[3] http://arxiv.org/abs/1407.6396

[4] http://ieeexplore.ieee.org/xpl/articleDetails.jsp?tp=&arnumber=6355930

[5] http://link.springer.com/chapter/10.1007/978-3-642-30422-4_10

On 20 January 2015 at 15:06, peter van der Stok <stokcons@xs4all.nl> wrote:

> Dear all,
>
> I like to draw you attention to the following articles.
> In these articles calculations are done on the optimal MPL interval
> division with the aid of queuing networks.
>
> In the masters thesis "Modeling and Simulating the Trickle algorithm" (
> http://alexandria.tue.nl/extra1/afstversl/wsk-i/meyfroyt2013.pdf ) by
> T.M.M. Meyfroyt (August 2013) propagation delay and message overhead for
> Trickle and "Short-Trickle" are compared by simulations and analysis in
> single-hop and multi-hop networks.
>
> The paper "Data Dissemination Performance in Large-Scale Sensor Networks" (
> http://dl.acm.org/citation.cfm?id=2591981 ) by T.M.M. Meyfroyt, S.C.
> Borst, O.J. Boxma, D. Denteneer (June 2014), analyzes the message overhead
> of the original Trickle algorithm compared to the "Short-Trickle
> algorithm". An extended journal version of this paper has been submitted to
> QUESTA (and has been attached in this email).
>
> In the paper "A Data Propagation Model for Wireless Gossiping" (
> http://arxiv.org/abs/1407.6396)  by T.M.M. Meyfroyt, S.C. Borst, O.J.
> Boxma, D. Denteneer (Juli 2014), an extension to the Trickle algorithm is
> proposed, similar to the "New Trickle algorithm" and its performance is
> analyzed and compared to that of the original Trickle algorithm. This paper
> has recently been accepted in Performance Evaluation (
> http://www.sciencedirect.com/science/article/pii/S0166531615000024).
>
> Hope this is useful.
>
> Greetings,
>
> peter
>
>
> Badis Djamaa schreef op 2015-01-20 00:43:
>
>> 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
>>>>
>>> [1] 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 [1]
>>>>
>>>> any comment is warmly welcomed
>>>>
>>>> All the best
>>>> badis
>>>>
>>>
>>
>>
>> Links:
>> ------
>> [1] https://dspace.lib.cranfield.ac.uk/handle/1826/9033
>>
>> _______________________________________________
>> Roll mailing list
>> Roll@ietf.org
>> https://www.ietf.org/mailman/listinfo/roll
>>
>