Subject: Re: [Roll] Revisiting the Trickle Algorithm

From: Badis Djamaa <[email-masked]>
Date: Mon, 2 Feb 2015 11:24:34 +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 <[email-masked]> 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 <[email-masked]>
>> 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
>>> <[email-masked]> 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
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/roll
>>
>

---

From: Omprakash Gnawali <[email-masked]>
Date: Mon, 2 Feb 2015 10:12:43 -0600

On Mon, Jan 19, 2015 at 5:35 PM, Badis Djamaa <[email-masked]> wrote:
> 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.
>
>
>
>>just the first interval starting at 0, how about the first n intervals
> 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.
>
>
>

Look forward to this. Could you also post your code so others can do
experiments on different testbeds to verify the results once you have
converged on a design that addresses the side effects. For example, I
can try to have a student do this as a short project in TinyOS.

If the side effects remain, this will be a question of tradeoff in
which case it is better to have this as a commentary in the RFC rather
than replace it.

It will also be helpful to do a survey of what type of intervals are
being used by the community so we know how big a problem this is.

- om_p

---

From: Omprakash Gnawali <[email-masked]>
Date: Mon, 2 Feb 2015 10:37:06 -0600

---------- Forwarded message ----------
From: Omprakash Gnawali <[email-masked]>
Date: Mon, Feb 2, 2015 at 10:12 AM
Subject: Re: Revisiting the Trickle Algorithm
To: Badis Djamaa <[email-masked]>
Cc: badis DJAMAA <[email-masked]>, ROLL WG <[email-masked]>,
"Thomas Heide Clausen (work)" <[email-masked]>, Philip Levis
<[email-masked]>, JeongGil Ko <[email-masked]>, JeongGil Ko
<[email-masked]>, Jonathan Hui <[email-masked]>, Ines Robles
<[email-masked]>, Michael Richardson
<[email-masked]>

- om_p

---

From: Badis Djamaa <[email-masked]>
Date: Wed, 4 Feb 2015 18:17:56 +0000

Thank you Omprakash for your email

That's great.

The side-effect discussed in section 4.5. of the detailed report [1] might
provide other benefits.

In sparse networks using k=1, "New-Trickle" outperformed Trickle in both
time/cost aspects, as shown in Appendix A. When k > 1, however, it
generated more packets than Trickle. This is also observed in dense
single-hop networks (Figure 13 (d), page 22).

In dense multi-hop networks, this side-effect is less noticeable (see
results on pages 18-19), but another effect can emerge with smaller Imin
(Figure 11 (d)). I think this is not related to "New-Trickle" as it emerges
from the efficiency of CSMA strategies and timer-based suppression
mechanisms. Note that "New-trickle" generally transmit less in the Imin
interval as can be seen from the third column of graphs. Also, it seems
that "New-Trickle" can provide a better load distribution (Figure 10, page
12).

Allowing a node to rest c to zero at time t of an Imin interval (rather
than at the beginning of the next interval) might suppress most of this
cost. I am doing some simulations with this second design. However, I think
a detailed study is required to decide which design to choose. We can also
consider other designs.

I will send you a copy of the TinyOS code as soon as I clean it up. Both
designs are implemented and I think your student can help us to choose.

Concerning Imin and k values, I agree that such a survey better guides the
evaluation. I surveyed some of the use-cases such as RPL, MPL, CTP, some
dissemination protocols and AMI use-cases. A generic list is still to be
built.

[1]https://dspace.lib.cranfield.ac.uk/handle/1826/9116

all the best
badis

On 2 February 2015 at 16:12, Omprakash Gnawali <[email-masked]> wrote:

> (lossless
> packets),
> depends on