Re: [Roll] trickle question

[Joakim Eriksson <joakime at sics.se>]

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

That would be great!

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

Is it really the same as unsynchronized trickle (according to the spec)?
If we skip waiting for the interval we will reset and restart the
counting of sent messages, and count received DIOs immediately.
In the version in the specification all nodes will ignore any
other nodes DIO messages that happen to come after their own
transmission but before the the interval ends.

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

Yes, if a single node would run this it will have a higher likelihood
to send than the other nodes. But the interval I length is still
doubled in each cycle, so it is not as bad as if it would just
double the interval that it feeds to T (e.g. I/2 + rand()*I/2).

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

It should not be the short listening problem, I think, but there
might be other "emergent behaviors" that is more or less impossible
to see without a proper round of simulations.

> Usually, it's just easier to keep track of the rand() result, rather 
> than keep two timers.

Yes, I agree on that!

Best regards,
-- Joakim Eriksson, SICS

> Phil