Subject: Re: [Roll] trickle question

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Wed, 11 Nov 2009 15:28:14 +0100

Hi,
 
sorry, pressed send button to early:
what happens if I expires when T is still running. the text says to
reset T. I would let T expire and next time set it according to the
potentially doubled value of I.
 
Julien

________________________________

	From: Julien Abeille (jabeille) 
	Sent: mercredi 11 novembre 2009 15:27
	To: roll
	Subject: trickle question

	Hi all,
	 
	what happens if I expires when T is still running

---

From: Philip Levis <[email-masked]>
Date: Wed, 11 Nov 2009 08:18:30 -0800

> potentially doubled value of I.

The interval I can't expire while timer T is still running, as T is in  
the range of [I/2, I). (There's a typo in the draft).

The one exception is when an event causes Trickle to reset I to I_min.  
But resetting I also resets T.

Phil

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Wed, 11 Nov 2009 19:10:16 +0100

Hi Phil,

I thought that when T expires, you restart T (without restarting I).
Hence if e.g I compute T= 3/4I, start both I and T, after 3/4I, I
restart T to e.g. 5/6I. After 1/4 I more, I expires, T is still running.
Did I misunderstand?

Best,
Julien

> -----Original Message-----
> From: Philip Levis [mailto:[email-masked]] 
> Sent: mercredi 11 novembre 2009 17:19
> To: Julien Abeille (jabeille)
> Cc: roll
> Subject: Re: [Roll] trickle question
> 
> 
> The interval I can't expire while timer T is still running, 
> as T is in the range of [I/2, I). (There's a typo in the draft).
>

---

From: Philip Levis <[email-masked]>
Date: Wed, 11 Nov 2009 10:17:30 -0800

> restart T to e.g. 5/6I. After 1/4 I more, I expires, T is still  

Once T has fired, you don't restart it until a new interval begins (I  
expires or the trickle timer is reset).

Phil

---

From: "Julien Abeille (jabeille)" <[email-masked]>
Date: Wed, 11 Nov 2009 22:13:53 +0100

Ok, thanks. 
Julien 

> Sent: mercredi 11 novembre 2009 19:18
> Once T has fired, you don't restart it until a new interval 
> begins (I expires or the trickle timer is reset).
> 
> Phil
>

---

From: Joakim Eriksson <[email-masked]>
Date: Sat, 14 Nov 2009 16:16:08 +0100

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.

Best regards,
-- Joakim Eriksson, SICS

Julien Abeille (jabeille) skrev:
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: Omprakash Gnawali <[email-masked]>
Date: Sat, 14 Nov 2009 09:24:22 -0800

> code if we skip the wait for the complete interval to pass.

What would the less complex code look like? Do you have some high
level pseudocode for what you had in mind?

- om_p

---

From: Joakim Eriksson <[email-masked]>
Date: Sat, 14 Nov 2009 18:42:37 +0100

Hi,

Well the difference is that you do not need to treat the I
(interval) as a timer, so it would be:

Some pseudo code:

When T triggers:
--
if (C > REDUNDANCY_CONSTANT) sendDIO();
C = 0;
if (doublings++ < max_doublings) I = I * 2;
T.start(I/2 + rand() * I/2);
--

The only timer that is needed is T in this case.

Based on specification it needs to be:

When T triggers:
--
if (C > REDUNDANCY_CONSTANT) sendDIO();
--

and When I_timer triggers:
--
C = 0;
if (doublings++ < max_doublings) I = I * 2;
T.start(I/2 + rand() * I/2);
I_timer.start(I);
--

So there is a need for a second timers (or accounting of the
rand() result) if we need to wait before restarting T.
Skipping the interval timer will give slightly less complex
code (well, not much) and less resource need (timers/RAM).

Best regards,
-- Joakim Eriksson, SICS

---

From: Philip Levis <[email-masked]>
Date: Sat, 14 Nov 2009 11:12:58 -0800

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

Phil

---

From: Joakim Eriksson <[email-masked]>
Date: Sat, 14 Nov 2009 23:08:03 +0100

Philip Levis wrote:
> 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!

> 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 

Yes, I agree on that!

Best regards,
-- Joakim Eriksson, SICS

---

From: Omprakash Gnawali <[email-masked]>
Date: Sun, 29 Nov 2009 05:53:23 -0800

> (interval) as a timer, so it would be:

That was a typo

"When the timer fires at time T, the node compares C to the redundancy
   constant, DEFAULT_DIO_REDUNDANCY_CONSTANT.  If C is less than that
   value, the node generates a new RA and broadcasts it."

...

> T.start(I/2 + rand() * I/2);

Same typo.

- om_p