Subject: [Roll] Revisiting the Trickle Algorithm

From: badis DJAMAA <[email-masked]>
Date: Mon, 19 Jan 2015 13:51:11 +0000

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
<https://tools.ietf.org/html/rfc6206#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

---

From: Omprakash Gnawali <[email-masked]>
Date: Mon, 19 Jan 2015 09:10:16 -0600

---------- Forwarded message ----------
From: Omprakash Gnawali <[email-masked]>
Date: Mon, Jan 19, 2015 at 9:01 AM
Subject: Re: Revisiting the Trickle Algorithm
To: badis DJAMAA <[email-masked]>
Cc: 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]>

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  shows
> that by a simple modification to Trickle, a great decrease in the
> In a nutshell the modification recommends to change step 2, section 4.2. of
> RFC6206 as follows
>
> Old:
>
>          (because of an inconsistency or external events).
>

---

From: Badis Djamaa <[email-masked]>
Date: Mon, 19 Jan 2015 23:43:09 +0000

Thank you Gnawali for your comments,

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

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

> document

---

From: peter van der Stok <[email-masked]>
Date: Tue, 20 Jan 2015 16:06:18 +0100

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:
> 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.
> 
> 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.
> 
>>> available here https://dspace.lib.cranfield.ac.uk/handle/1826/9033
>> [1] shows
>>> https://dspace.lib.cranfield.ac.uk/handle/1826/9033 [1]
>>> 
> Links:
> ------
> [1] https://dspace.lib.cranfield.ac.uk/handle/1826/9033
> 
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll