Subject: [Roll] Trickle in draft-dt-roll-rpl-00.txt

From: Richard Kelsey <[email-masked]>
Date: Tue, 30 Jun 2009 13:16:26 -0400

There are some problems with how Trickle is being used for
RA transmissions in draft-dt-roll-rpl-00.

Trickle normally uses two rules for governing
retransmission:

 - Receiving an up-to-date message acts to suppress
   transmission.

 - Receiving an out-of-date message acts to promote
   transmission.
   
This works if all devices share the same data, which makes
it trivial to determine if an incoming message should
suppress or promote a transmission by the receiver.  There
is no such easy test for RAs.

Section 5.3.2 lists the cases where receiving new data
requires resetting the Trickle timer.  Receiving a 'stale'
RA never resets the timer.  In fact, in the current
document, any RA for a DAG acts to suppress an RA
transmission for that DAG.  This clearly does not work
because it causes out-of-date RAs to suppress more
up-to-date ones.  For example, a node with many children
will rarely transmit, even if the children have stale data.

For Trickle to work, if node A hears an RA from node B, node
A should:

 - act to suppress A's RA if B would make as good or better
   a parent than A for all devices that might hear node A

 - act to promote A's RA if A would make a better parent
   for B than B's current parent

There often no way to determine if either of these cases
apply, as both depend on subsequent decisions by other
devices.  Nor is there a safe conservative choice.  If A
resets its timer unnecessarily it transmits to no purpose.
If A erroneously suppresses its RAs the DAG becomes
inefficient or broken.  In the absence of a usable
'up-to-date' test for received RAs, I do not see how Trickle
can work for maintaining a DAG.

By the way, I suggested using Trickle in a similar role in
draft-kelsey-roll-lip-00.  I think the same problems apply
there as well.  Sorry about that.

                                 -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 30 Jun 2009 10:34:07 -0700

Hi Richard,

I agree with you that rpl-00 needs additional work w.r.t. the use of  
Trickle. So let me try and address some of your concerns here on the ML.

The trick with making Trickle work properly in a routing protocol is  
that you have to change the rules on what causes an increase in the  
counter, k, and what causes the timer to reset. You are right, that  
the original version of Trickle specified conditions on information  
consistency - that is receiving consistent information increase k  
while inconsistent information resets the timer.

 From a routing perspective, inconsistent routing information should  
continue to reset the Trickle timer - but we need to add one or more  
conditions to what should cause an increase in k. For example, only  
nodes that advertise the same or similar routing depth should cause an  
increase in k. This should help with the specific example you raised  
and a node will not be suppressed by its parents or descendants.

Once we have the appropriate conditions on increasing k, then the  
value of k becomes important. k=1 is probably too constrained as it  
causes other routers to suppress their RAs and avoid being discovered  
by their neighboring nodes. In practice, we have found k=5 or even k=3  
to work well. As long as several nodes are transmitting RAs within a  
radio region, that's enough density to provide good enough receiver  
diversity for other surrounding nodes. The random factor within  
Trickle also helps us here - encouraging different nodes to transmit  
RAs at different times. The only difference is that a single node's  
transmission rate increases - which is what we really want when the  
network is dense.

Does that help?

--
Jonathan Hui

On Jun 30, 2009, at 10:16 AM, Richard Kelsey wrote:

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

---

From: Philip Levis <[email-masked]>
Date: Tue, 30 Jun 2009 12:43:22 -0700

On Jun 30, 2009, at 10:34 AM, Jonathan Hui wrote:

> conditions to what should cause an increase in k.

I think you mean c? You increment c when you hear a "redundant"  
message, and transmit if c<k.

Phil

---

From: Philip Levis <[email-masked]>
Date: Tue, 30 Jun 2009 12:50:59 -0700

> is no such easy test for RAs.

Richard,

Please take a look at this recent article on Trickle, which in part  
mentions how it can be used for eventual consistency besides version  
number agreement:

http://csl.stanford.edu/~pal/pubs/p99-levis.pdf

Also, the CTP paper describes in detail how it can be used to maintain  
a routing gradient:

http://sing.stanford.edu/pubs/sing-09-01.pdf

Although note it does not discuss k/c.

Phil

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 30 Jun 2009 13:16:40 -0700

On Jun 30, 2009, at 12:43 PM, Philip Levis wrote:

>> I agree with you that rpl-00 needs additional work w.r.t. the use  
>> of Trickle. So let me try and address some of your concerns here on  
>> the ML.
>>
>> The trick with making Trickle work properly in a routing protocol  
>> is that you have to change the rules on what causes an increase in  
>> the counter, k, and what causes the timer to reset. You are right,  
>> that the original version of Trickle specified conditions on  
>> information consistency - that is receiving consistent information  
>> increase k while inconsistent information resets the timer.
>>
>> continue to reset the Trickle timer - but we need to add one or  
>> more conditions to what should cause an increase in k.
>

Yes. I meant c for what gets incremented and k for the threshold.

--
Jonathan Hui

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 30 Jun 2009 18:25:23 -0400

From: Philip Levis <[email-masked]>
   Date: Tue, 30 Jun 2009 12:50:59 -0700

Philip,

The issue isn't that the relevent information is more
than a version number, it is that the relevent information
isn't being taken into account.  For example, with a
network with a backbone of line-powered nodes and a bunch
of low-power nodes, you would prefer that nodes tend to
choose the line-powered nodes as parents.  Having RAs
from low-power nodes suppress RAs from the line-powered
nodes is going to work against this, which in turn means
that you want to take routing contraints into account
when deciding when to send an RA.

   Also, the CTP paper describes in detail how it can be used to
   maintain a routing gradient:

It does so by not using Trickle's suppression mechanism,
which is the part of Trickle which worries me.
Trickle-with-suppression and Trickle-without-suppression are
substantially different algorithms.

It would bother me at all if RPL became more like the
Collection Tree Protocol in other ways as well :-).

                            -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Tue, 30 Jun 2009 15:45:25 -0700

Hi Richard,

> when deciding when to send an RA.

I think we can successfully support this case. As I mentioned in my  
previous email, we just have to specify that c is incremented when  
receiving RAs indicating a similar routing cost to what will be  
advertised.

> substantially different algorithms.

We have and are using Trickle's suppression mechanism successfully in  
real deployments. We did run into the scenarios you have raised and  
have dealt with them simply by restricting when to increment c. In my  
view, the suppression mechanism can be critical for operation in dense  
environments - especially when using links where broadcast can be very  
expensive compared to unicast.

> Collection Tree Protocol in other ways as well :-).

We have been working very hard to pull in the good ideas from CTP. We  
are looking into including data-based loop detection, adaptive  
beaconing, etc. Note, however, that we are concerned only with routing  
here - the forwarding aspects of CTP are out-of-scope.

--
Jonathan Hui