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

From: Richard Kelsey <[email-masked]>
Date: Wed, 01 Jul 2009 08:54:07 -0400

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

Jonathan,

   On Jun 30, 2009, at 3:25 PM, Richard Kelsey wrote:
   > 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.

   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.

The problem is that 'similar routing cost' is in the eye of
the beholder.  How does a node determine that a received RA
will be considered similar to its own by other devices?
This not a problem in a network where all nodes are running
the same stack from the same vendor.  For it to work in a
network running multiple stacks from multiple vendors there
will have to be a shared, well-defined notion of 'cost'.

For example, consider the issue of trust.  If node A trusts
node B but not node C, then C's RA is not a replacement for
B's and should not suppress it.  How does B learn this?

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

   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.

My other concern with the suppression mechanism is how it
behaves in networks with variable density.  I have run a few
simulations of this.  If you have a cluster of, say, 20
nodes that can all hear each other and a few scattered
outliers that can hear only one or two nodes in the cluster,
it can take a while for the outliers to hear an updated RA.
This doesn't happen in the original Trickle, as the outliers
get updated as soon as they themselves transmit.  With the
RA version, hearing an outdated RA does not trigger a
transmission.

Would it be OK to unicast an RA in such a case?  In other
words, if node A hears an RA from node B that has an
older sequence number, node A could unicast its RA to B
while leaving its Trickle timer as-is.

   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.

I agree that there has to be a way to limit broadcasts.  I
am not convinced that Trickle is always appropriate, but I
admit that I do not have an alternative proposal.  Setting
k to infinity addresses my concerns.  In rpl-00 k is a
constant, DEFAULT_DIO_REDUNDANCY_CONSTANT.  We could add
a DIORedundancyLimit field.

   > It would bother me at all if RPL became more like the
   > 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.

The data-based loop detection was what I had in mind.

                                    -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 1 Jul 2009 08:06:31 -0700

Hi Richard,

> will have to be a shared, well-defined notion of 'cost'.

The larger issue is that we intentionally didn't even try to define  
the 'cost'. Different networks will use different metric(s) and we  
cannot possibly dream up all metrics that might be used. The best  
thing we can do is define what happens in the default case - the case  
where you just don't know how to process another node's metrics.

> B's and should not suppress it.  How does B learn this?

Is this "trust" from a security view? I guess I was assuming that it  
will be enough for B and C to determine from their own logic the  
capabilities and costs each provides. If they are the same, then go  
ahead and suppress. If they are different (because values are  
different or the metrics are not understandable) then you should  
default to no suppression. But if the logic for what capabilities B  
and C may provide are implemented only on node A, then I agree that's  
an issue.

> RA version, hearing an outdated RA does not trigger a

I'd argue that hearing an inconsistent RA should always trigger a  
Trickle reset. This may be due to a sequence number change or some  
other indicators like data-driven loop detection. I prefer the term  
inconsistent since Trickle resets shouldn't be based on just the  
sequence number.

One useful behavior of Trickle is that the "outliers" won't be  
suppressed by the other nodes. So once the outliers advertise, then  
only the nodes that can hear the outliers will reset their Trickle  
timer. Of course, this assumes that radio range is symmetric - the  
worse case being if the outliers have a larger radio range. In the  
end, Trickle does impose a resource-consumption-delay tradeoff -  
especially if you set the parameters such that it operates  
conservatively (i.e. k is a small value).

> while leaving its Trickle timer as-is.

We have discussed whether or not it is OK to unicast, but haven't gone  
into the discussion in-depth. Of course, the challenge is avoiding RA  
collisions, especially in dense networks.

> a DIORedundancyLimit field.

Agree. k allows an operator to make a tradeoff, so it probably should  
be parameter carried in the RA similar to the min/max period for  
Trickle. We'll look into including this in the next rev.

> The data-based loop detection was what I had in mind.

Sure. We have plans to include this already.

--
Jonathan Hui

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 1 Jul 2009 08:51:47 -0700

Hi Richard,

On Jul 1, 2009, at 8:34 AM, Richard Kelsey wrote:
>   ahead and suppress.
> "Trust" was just a stand in for any asymmetric link metric.
> It could be energy or anything else.
>
> The problem is not B's and C's cost determination, but
> that of A.  Even if B and C agree on what their costs are,
> in picking a parent A is going to consider its own costs for
> forwarding via B and C.  Those costs may be quite different
> and unknown to B and C.

Right. But I don't think that k = infinity has to be the default  
value. A main effect of Trickle is that k bounds the effective density  
of RAs for a given time period. If that k-bounded density is forgiving  
enough, then these corner cases shouldn't be an issue most of the  
time. Of course, it is probabilistic.

> The -00 draft does not include this in the list in section
> 5.3.2.  In rule 5 of section 5.4 it states:
>
> Nodes MUST ignore RAs that are received from other routers
> located deeper within the same DAG.
>
> That clearly rules out a Trickle reset when hearing an
> out-of-date RA from a child.

Yes. That text was basically lifted from one of Pascal's drafts. What  
we did was take a bunch of mechanisms we thought were useful and tried  
to bring them together. There certainly is more work to do here in  
making sure that these mechanisms work together properly.

--
Jonathan Hui

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 01 Jul 2009 11:34:12 -0400

Jonathan,

   From: Jonathan Hui <[email-masked]>
   Date: Wed, 1 Jul 2009 08:06:31 -0700

   > will have to be a shared, well-defined notion of 'cost'.

   The larger issue is that we intentionally didn't even try
   to define the 'cost'.

Yes.  I think this leads so some significant complications,
but that's a topic for a different thread.

   > We could add a DIORedundancyLimit field.

Great.
                                -Richard Kelsey

---

From: Richard Kelsey <[email-masked]>
Date: Wed, 01 Jul 2009 16:20:45 -0400

Jonathan,

   From: Jonathan Hui <[email-masked]>
   Date: Wed, 1 Jul 2009 08:51:47 -0700

The choice of k has to balance bandwidth versus
responsiveness.  I wouldn't advocate k = infinity is the
best everywhere, but it is the best in many cases.

   > out-of-date RA from a child.

   Yes.  That text was basically lifted from one of Pascal's
   drafts.  What we did was take a bunch of mechanisms we
   thought were useful and tried to bring them together.

I think that text is correct, in that you cannot trigger
a Trickle reset just because you hear an inconsistent RA.
Suppose node A hears an inconsistent RA from node B.  There
are two cases:

 - If node B will accept A as a parent, then node A
   should do a Trickle reset.

 - If node B will not accept A as a parent, then A
   should not do a Trickle reset.

The problem is that node A has no way of determining which
of these two is actually the case.  The safe thing to do
is to not do a reset.  Otherwise A will continue to reset
until B gets updated from other devices.

On the other hand, if B will accept only A as a parent,
perhaps because no other possible parent is in range, and A
allows its RAs to be suppressed by other RAs and also
ignores B's out-of-date RAs, then B might have to wait a
while before getting updated.

This is why I think it makes sense to set k to infinity.

                                     -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 1 Jul 2009 14:27:33 -0700

> best everywhere, but it is the best in many cases.

More precisely, the tradeoff between resource (channel and energy)  
utilization and responsiveness is most acute for nodes that have  
limited potential routes. When there are a good number of potential  
routes, responsiveness doesn't suffer much. When there are lots of  
potential routes, Trickle reduces wasted energy in unnecessary RAs.

> until B gets updated from other devices.

That depends on what you consider "safe". This, again, is a tradeoff  
between resource consumption and responsiveness. If responsiveness is  
more important than energy and/or channel channel utilization, then A  
should do a reset.

> while before getting updated.

If B only has 1 choice for a parent, then there's not much receiver  
diversity to talk about. And if B's RA does not trigger A to reset,  
then it will have to wait a while if Trickle's upper-bound is set to  
something large.

> This is why I think it makes sense to set k to infinity.

I think we're both right on this issue. It falls in the category of  
"it depends". That's why I agreed that it makes sense to make k a  
parameter carried within the protocol.

--
Jonathan Hui

---

From: Omprakash Gnawali <[email-masked]>
Date: Wed, 1 Jul 2009 19:31:18 -0700

On Wed, Jul 1, 2009 at 5:54 AM, Richard Kelsey<[email-masked]> wrote:
...
>
>   >   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
>   >
>   > 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.
>

Just one data point from the CTP paper (which does not use
suppression) - it has been known to work efficiently even in networks
with node degree of up to (214,305) or (114,120). That is pretty
dense.

- om_p

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 1 Jul 2009 19:35:29 -0700

> with node degree of up to (214,305) or (114,120). That is pretty

Try the same experiment with LPL set to a reasonable duty cycle :)

I'm not saying that suppression is necessary in all cases - just  
necessary in some cases. While we should be link agnostic, we should  
also be cognizant of link protocols that are likely to be used.

--
Jonathan Hui

---

From: Philip Levis <[email-masked]>
Date: Wed, 1 Jul 2009 20:01:29 -0700

On Jul 1, 2009, at 7:35 PM, Jonathan Hui wrote:

> necessary in some cases. While we should be link agnostic, we  
> should also be cognizant of link protocols that are likely to be used.

I agree. I would take the CTP results to say that a network *can*  
work without suppression, but it's quite clear that doing so is  
desirable.

I'll go out on a limb and say that exactly how the suppression works  
is something which should not be specified yet: that leaves it open  
for future work to figure out, just as 793 doesn't specify fast  
retransmit. Instead, the specification should state the MUSTs of when  
RAs are sent necessary for correct operation and note that additional  
RAs MAY be sent. I'd interpret this as MUSTs of when the timer must  
be reset and when packets MUST NOT increment c.

Phil

  I'd

Phil

---

From: Jonathan Hui <[email-masked]>
Date: Wed, 1 Jul 2009 20:13:54 -0700

On Jul 1, 2009, at 8:01 PM, Philip Levis wrote:
> retransmit. Instead, the specification should state the MUSTs of  
> when RAs are sent necessary for correct operation and note that  
> additional RAs MAY be sent. I'd interpret this as MUSTs of when the  
> timer must be reset and when packets MUST NOT increment c.

Sure. There seems to be a dependency between suppression and the  
routing metric anyway, so I think we can lump this in with these  
"logic plugins" that are occasionally referred to on the ML.

Only issue is now we have to interoperate with nodes that may never  
suppress themselves. Since we're talking about variations of Trickle  
suppression rules, I'd say that we might want nodes to force an  
advertisement with a relatively long period to avoid starvation when  
neighboring nodes fail to suppress themselves. It does, however, mean  
that these slow, unsuppressed advertisements will grow with density.  
But if the WG agrees to defer the suppression specification, then we  
can table this discussion for now.

--
Jonathan Hui

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 3 Jul 2009 15:51:11 +0200

Hi Phil:

I think I asked you that same question in Dublin but now we have a
context.

What I'd really like to suppress is the behavior of a router being a
router, as opposed to suppressing some RAs from every routers.

Like if I have many of other routers around I could yield and suppress
RAs totally. The idea being that some nodes act as routers for some time
and then they stop because they think they've done enough. Neighbors
node discovering a lesser density take over and now act as routers.

Could you adapt your trickle thinking to get there?

Pascal

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Philip Levis
>Sent: jeudi 2 juillet 2009 05:01
>To: Jonathan Hui
>Cc: [email-masked]; Omprakash Gnawali
>Subject: Re: [Roll] Trickle in draft-dt-roll-rpl-00.txt
>
>
>_______________________________________________
>Roll mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/roll

---

From: Richard Kelsey <[email-masked]>
Date: Sun, 05 Jul 2009 22:26:34 -0400

Pascal,

   Date: Fri, 3 Jul 2009 15:51:11 +0200
   From: "Pascal Thubert (pthubert)" <[email-masked]>

The problematic situation for this is when there is a dense
clique of nodes and two other nodes, one just out of range
of the clique and the other half way inbetween:

    o o o
   o o o o <--- 3/4 hop ---> o <--- 3/4 hop ---> o
    o o o
    
To keep the network connected you want to avoid having the
node in the middle, which has all those neighbors over on
the left, from deciding not to be a router.

                              -Richard Kelsey

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 6 Jul 2009 12:25:27 +0200

>the left, from deciding not to be a router.

That's correct. Same for trickle in the current draft. 

RPL enables a node to detach and form its own tree. The result is that
children migrate.
A goal is that a subdag that is drawn with a detaching parent is minimal
to NULL.
If it is NULL, then the node can safely abort it's router function. For
a while.

So we can cope with this issue. First we have to decide if we want this
feature or not.

I'd argue that trickling on the RA interval has some unwanted effect,
part of that making parent disappearance hard to detect at L3 (think
about how MIPv6 uses RA interval). Trickling on the role might be a
better idea, at least in some cases. And it does NOT have to be one OR
the other.

:)

Pascal

>From: Richard Kelsey [mailto:[email-masked]]
>Sent: lundi 6 juillet 2009 04:27
>To: Pascal Thubert (pthubert)
>Cc: [email-masked]; [email-masked]; [email-masked];
[email-masked]

---

From: Philip Levis <[email-masked]>
Date: Mon, 6 Jul 2009 09:56:22 -0700

> Could you adapt your trickle thinking to get there?

Can you be more precise? Is it that you want a router to more  
aggressively suppress others, or is it that you want a router to  
decide it should suppress itself more? Two questions. The first is:  
where is the decision is made? Is it:

1) Node A decides node B should stop being a router, or
2) Node B decides it should stop being a router?

1) has problematic security implications.

The second is whether node B (who thinks it's done enough) should  
suppress its RAs even if there are no other nodes around it sending  
RAs. I.e., what happens when every node thinks it's done enough?

The simplest way to get (reasonably) deterministic suppression through  
priorities is by having different interval lengths. If node A has an  
interval of length T and node B has an interval of length 2T, node A  
will always transmit in node B's quiet period and suppress it. But  
this assumes k=1.

Ultimately, Trickle is a randomized algorithm, and there are always  
chances of packet drops. So without entertaining the possibility of  
disconnection, B will send *some* RAs, albeit perhaps far fewer than A.

Phil

---

From: Jonathan Hui <[email-masked]>
Date: Mon, 6 Jul 2009 14:13:33 -0700

> disconnection, B will send *some* RAs, albeit perhaps far fewer than  

Exactly. The goal of Trickle isn't to actively enable or disable  
routers. It simply reduces the transmission rate of RAs a particular  
node sends. Every router is still a router. It is a tradeoff between  
resource consumption and latency. Channel capacity is one such  
resource so it makes sense for any node that has many neighbors to  
reduce the number of RA transmissions because the finite channel  
capacity is shared with all of its neighbors. If the resource  
constraints on transmitting RAs is lax, then suppression probably does  
more harm than good from a latency perspective.

I'm not convinced that a more complex topology maintenance scheme is  
the right way to go either. There's been a bunch of work in developing  
such mechanisms in the sensornet space, but their effectiveness in  
real-world environments is often hindered by the very things we worry  
about - dynamic radio connectivity, message loss, limited energy, etc.

--
Jonathan Hui

---

From: JP Vasseur <[email-masked]>
Date: Tue, 7 Jul 2009 15:40:43 +0200

but the goal of using trickle here is not to activate and disactivate  
routers, simply to reduce the frequency at which RAs are being sent w/ 
o compromising too much the reaction time.

JP.

On Jul 6, 2009, at 6:56 PM, Philip Levis wrote:

> The simplest way to get (reasonably) deterministic suppression  
> through priorities is by having different interval lengths. If node  
> A has an interval of length T and node B has an interval of length  
> 2T, node A will always transmit in node B's quiet period and  
> suppress it. But this assumes k=1.
>