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

From: Omprakash Gnawali <[email-masked]>
Date: Sun, 29 Nov 2009 13:12:58 -0800

On Sat, Nov 14, 2009 at 11:12 AM, Philip Levis <[email-masked]> 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

---

From: Philip Levis <[email-masked]>
Date: Sun, 29 Nov 2009 18:08:35 -0800

> It makes sense to use the simplified specification.

Om -- I think it deserves greater investigation than a single  
experiment. Joakim has been examining the effect more deeply. There  
are other optimizations that one can do (such as Gummadi's suggestion  
of suppression time).

Phil

---

From: Joakim Eriksson <[email-masked]>
Date: Mon, 30 Nov 2009 09:36:52 +0100

Philip Levis skrev:
> experiment. Joakim has been examining the effect more deeply. There are 
> other optimizations that one can do (such as Gummadi's suggestion of 
> suppression time).

Yes, there are quite a lot of interesting modifications that can be 
made. This simplification will remove one of the possible problems,
the sensitivity to unsynchronized networks, but will add more total
packets sent by ~13-14 percent (when compensating for the shorter
interval). The "optimal" version of Trickle needs to listen a full
interval to avoid missing packets, but that is going to be slightly
more complex than the original Trickle.

The question is: what are the priorities for the timer? My guess is
that we can get rid of the small problems that Trickle has and still
keep it fairly simple and resource efficient.

Best regards,
-- Joakim Eriksson, SICS

---

From: Joakim Eriksson <[email-masked]>
Date: Mon, 30 Nov 2009 10:59:46 +0100

Hello, some more results on Trickle.

I have been trying lots of different versions of Trickle and
realized that it is quite interesting and difficult to predict
what is going to happen when a knob is tuned. I did some simulations
on the simplified trickle that skips waiting for the interval (as
previously suggested) and to get relevant results I made the interval
33% longer. The first simulation is the scalability test (same as
figure 6 in the original Trickle paper):

http://www.sics.se/~joakime/tricklem0-scale.pdf

The settings are the K are 1, all nodes have a perfect medium
(e.g. no loss, single hop).

It shows:
- Trickle is synchronized (one packet per interval, all the time).
- Trickle without synchronization where T is taken from 0 - I (disaster)
- Trickle without synchronization (almost two packets with 512 nodes)
- Modified Trickle without synch (1.5 packets with 512 nodes)
- The best version i got currently (opt?) (< 1.1 packets with 512 nodes)

Trickle and the modified trickle are both good enough here I believe.

But Trickle's load balancing can break in some situations. I did a
simulation with K=1, 10 nodes synchronized and an 11:th node joining
out of synch. The results of this can be seen in the following figure:

http://www.sics.se/~joakime/trickle-phase-k1-000.pdf

The joining node is lucky when it gets in before 50% of the cycle has
passed. At above 20% it does never need to send at all
(since one of the other 10 did the job already). Is the node later than
50% it will take all the workload - this is what I would like to get
avoid if I was a node ;-)

The modified (simplified) version that does not wait out the interval
will never end up synchronized for more than a very short time so the
same simulation ends up looking like this:

http://www.sics.se/~joakime/tricklemod0-phase-000.pdf

Best regards,
-- Joakim Eriksson, SICS

Joakim Eriksson skrev:
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: Philip Levis <[email-masked]>
Date: Mon, 30 Nov 2009 09:14:17 -0800

On Nov 30, 2009, at 1:59 AM, Joakim Eriksson wrote:

> ....

Tom Anderson noted this issue when the paper was first published:  
there are three considerations which, in practice, make this behavior  
amazingly unlikely and therefore of limited concern:

1) Having all nodes perfectly synchronized is difficult/impossible
   1a) Packet losses mean that nodes typically do not agree on exactly  
when an interval starts
   1b) Nodes will, over time, fall out of synchronization due to local  
clock variations
2) Networks have packet losses
   2a) At some point the lagging node will not hear a transmission,  
will transmit, and suppress the others
3) The network is single-hop

In essence, this behavior is only really apparent in tightly  
controlled, aberrant settings (such as a single-hop simulation with no  
clock skew, perfect synchronization, and lossless packet  
communication). This doesn't mean that also covering this case isn't  
beneficial: it just needs to be judged against the performance effects  
in less aberrant cases.

Phil

---

From: Joakim Eriksson <[email-masked]>
Date: Mon, 30 Nov 2009 20:13:31 +0100

Philip Levis skrev:
> Tom Anderson noted this issue when the paper was first published: there 
> are three considerations which, in practice, make this behavior 

Over time they will, but assuming that many nodes will receive the same
new DIO at the same time there will be quite a long period of fairly
synchronized nodes (given that the max interval is several minutes).
Any node joining while this situation persist might end up in a bad or
good case.

>   2a) At some point the lagging node will not hear a transmission, will 
> transmit, and suppress the others

Yes, but it will be back in the same "problematic" or lucky state
the next interval since it will not move from its position in the 
interval due to the packet loss.

> 3) The network is single-hop

Yes, but I have seen the same situation in multi-hop simulations where
I am running hundreds of nodes over ~10 hops or so. Some nodes get much
more of the load than others.

> In essence, this behavior is only really apparent in tightly controlled, 
> aberrant settings (such as a single-hop simulation with no clock skew, 
> perfect synchronization, and lossless packet communication). This 
> doesn't mean that also covering this case isn't beneficial: it just 
> needs to be judged against the performance effects in less aberrant cases.

Yes, what I would like to have is something that performs as well as 
original Trickle in the normal case, and better in the worst cases.

I guess Trickle is good enough, but there are potential improvements
that I think needs to be studied carefully before we go ahead and
finalize the version that goes into RPL.

Best regards,
-- Joakim Eriksson, SICS

---

From: Omprakash Gnawali <[email-masked]>
Date: Mon, 30 Nov 2009 21:23:46 -0800

On Mon, Nov 30, 2009 at 9:14 AM, Philip Levis <[email-masked]> wrote:
> Tom Anderson noted this issue when the paper was first published: there are
> three considerations which, in practice, make this behavior amazingly
> unlikely and therefore of limited concern:
>
>  1a) Packet losses mean that nodes typically do not agree on exactly when an
> interval starts
>  1b) Nodes will, over time, fall out of synchronization due to local clock
> variations
> perfect synchronization, and lossless packet communication). This doesn't
> mean that also covering this case isn't beneficial: it just needs to be
> judged against the performance effects in less aberrant cases.

This synchronization might be more commonplace that what we think. I
think Joakim was discussing that in one of the later emails. In one
experiment, I rebooted a few nodes in the middle of the quiet period
(the first half when the timers don't fire), only to find the network
synchronize after a few intervals. Here is the graph:
http://stuff.stanford.edu/~om_p/ctp/trickle-interval/trickle-fullint-reboots/beacontime.html

Experiment: 56 nodes, cc2420, 0 dBm. At approx. 2100s, reboot 3 nodes.
Pick 10 random nodes in the network, divide them into three groups,
reboot each group at a time, group reboots separated by number of
seconds (corresponding to the three steps on the graph).

I only have this experiment about synchronization, which does not
prove much, other than that a network can get synchronized.

> Om -- I think it deserves greater investigation than a single experiment.

I forgot to mention that I have run full and truncated intervals with
redundancy constant=inf,15,10,5, two hrs for each redundancy constant.
I think Joakim's experiments provide a different perspective on how
these timers and the modifications work.

- om_p

---

From: Philip Levis <[email-masked]>
Date: Mon, 30 Nov 2009 21:58:33 -0800

On Nov 30, 2009, at 9:23 PM, Omprakash Gnawali wrote:

>> there are
>> controlled,
>> doesn't

Right -- the synchronization happens when a node sends a packet with  
the pull bit. The synchronization effect of request/response exchanges  
is well known: Deluge takes advantage of it to remove the listen-only  
period. But there are other events which reset intervals and *break*  
synchrony, such as a datapath inconsistency. The important result for  
Joakim's experiment is that load balancing works fine in a perfectly  
synchronized network and an unsynchronized one, but is imperfect in  
one which is mostly synchronized (a few nodes are out of phase).

A better indication of the degree of synchrony you see, I think, is  
one of the figures from your SenSys slides, where you shown the  
beacons over time.

>> experiment.

Maybe the two of you should compare notes?

Phil