[Roll] simplified Trickle (was Re: trickle question)

[Omprakash Gnawali <[e-mail]>]

On Sat, Nov 14, 2009 at 11:12 AM, Philip Levis <[e-mail]> wrote:
>
> On Nov 14, 2009, at 7:16 AM, Joakim Eriksson wrote:
>
>> Hello Phil and Julien,
>>
>> Is it really necessary to wait until the complete I interval has
>> passed before doubling I and restarting T (with the new interval)?
>>
>> It feels that we get basically the same behavior with less complex
>> code if we skip the wait for the complete interval to pass.
>
> Hm -- I can't recall if I tried this variant. I'm searching around for the
> analytical simulator source code, if I find it, I'll let you know.
>
> One thing is that trickle is more efficient when intervals are synchronized
> (it sends half as many messages). Let's say you reset the interval after T.
> First, the average interval length is 0.75I, leading to 33% more messages.
> Second, it will inherently desynchronize intervals, leading to twice as many
> messages compared to the best case. This is a total overhead of sending
> approximately 2.5 times as many messages if you don't. Of course, the 33%
> also results in a lower detection latency.
>
> Given how the interval length changes, if you want to implement it this way,
> *all* nodes need to do so, or you break load balancing.
>
> But this is just off the top of my head. The behavior of protocols like
> these can often be not something you'd expect (e.g., "basically the same
> behavior"). I would definitely run some tests to see how it behaves under
> very high density. It could be that nodes which pick small T values end up
> shouldering more of the load due to a variant of the short listen problem.
>  My intuition is that this is a shortcut which probably isn't worth it as it
> might bite you later, but that intuition could be wrong.
>
> Usually, it's just easier to keep track of the rand() result, rather than
> keep two timers.

I ran the version than Joakim suggested (Truncated interval) and the
one of the draft (Full interval). Here are the results:
http://stuff.stanford.edu/~om_p/ctp/trickle-interval/beacontime.html

(Graph with lots of lines show number of beacons for each node).

Experiment setup:
- 55 nodes with cc2420 radios (Tutornet)
- max interval 512s
- 0 dBm transmit power
- CTP Noe as is and with modifications for truncated interval

Result: Larger number of beacons with Truncated intervals, otherwise
performance measured in delivery ratio and cost (excluding control
pkts) similar. We can use a larger interval with the truncated
interval to match the number of beacons with the full interval.

It makes sense to use the simplified specification.

- om_p