Re: [Roll] Revisiting the Trickle Algorithm

[peter van der Stok <[e-mail]>]

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 <[e-mail]>
> 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
>> <[e-mail]> 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
> [e-mail]
> https://www.ietf.org/mailman/listinfo/roll