Re: [Roll] Revisiting the Trickle Algorithm

[Badis Djamaa <[e-mail]>]

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 <[e-mail]> wrote:

> On Mon, Jan 19, 2015 at 5:35 PM, Badis Djamaa <[e-mail]>
> wrote:
> > 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.
>
>
> 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
>