Subject: Re: [Roll] Fwd: New Version Notification for draft-levis-roll-trickle-00

From: Phoebus Chen <[email-masked]>
Date: Mon, 08 Mar 2010 23:27:55 +0100

Phil, Omprakash, and Joakim,

Did you find any resolution to Trickle's load balancing problem that was 
discussed in this previous thread?
http://www.ietf.org/mail-archive/web/roll/current/msg02707.html

This is related to the concern I raised in a previous email
http://www.ietf.org/mail-archive/web/roll/current/msg02723.html
regarding how Trickle affects the selection of parents (or how the rules 
on how to defer joining a DODAG may affect Trickle's operation, point #2 
I made in the email thread).

I am concerned that the redundancy suppression mechanisms in Trickle 
will suppress the DIO advertisements of some of the potential parents of 
a node, and the node will end up choosing a bad parent (or bad parents).

Let me illustrate with an example:
----------------------------------
Assume that "DIOs that advertise the same rank" are considered 
redundant, as suggested by (draft-ietf-roll-rpl-06, pg. 38, Section 
5.3.5.1.1).

Nodes A, B, and C are waiting to connect to the DODAG.  Node A connects 
to the DODAG first, starts it's Trickle timer, and advertises its DIO, 
but C misses the message (maybe a fluke, because an 802.11 access point 
happened to go off nearby).  After roughly I_min, Node B connects to the 
DAG (but node A is not a parent), starts it's Trickle timer, and 
advertises the same rank as A.  Node B may have deferred joining the 
DODAG for I_min because it wanted to find a better parent.  Now, node B 
always has a shorter interval I than node A, so it should always 
advertise its DIO before node A (since T is always within [I/2,I]).  If 
the redundancy constant is set to 1, then B will always suppress A 
(until a packet is lost, but let's say this is uncommon).

Let's say C needs to connect through the DODAG through B or A.  C will 
choose B since C never hears A's DIO advertisements, and C will compute 
it's rank based on B's rank (B is C's preferred parent).  But it may be 
that A would be a better choice for C, and should be the preferred 
parent for C.
----------------------------------

This may sound like a contrived example, but my point is that a 
low-chance event such as C missing A's first advertisement could result 
in C not knowing that A is present for a long time... past the time that 
C has to make a decision on how it connects to the DODAG (compute and 
advertise a rank).  I think variants of this example with multiple 
parents could occur and cause the building of very suboptimal DODAGs.

The root of the problem is that Trickle was designed for ensuring 
consistency, but is being applied to a situation where nodes are 
actually advertising different values (their rank, their metrics).  It's 
tricky to say what should be suppressed.  I'm having a hard time 
imagining using something besides rank or the Objective Function metric 
for measuring consistency.

Could you guys give your thoughts on this?

-- 
Phoebus Chen
Postdoctoral Researcher
Automatic Control Lab, KTH (Royal Institute of Technology)
http://www.ee.kth.se/~phoebus

On 2/26/10 2:20 AM, Philip Levis wrote:
> Thomas and I thought it might make sense to separate Trickle out from
> the RPL specification. Here's a first version of the draft:
>
> http://www.ietf.org/internet-drafts/draft-levis-roll-trickle-00.txt
>
> Phil
>
> Begin forwarded message:
>
>> *From: *IETF I-D Submission Tool <[email-masked]
>> <mailto:[email-masked]>>
>> *Date: *February 25, 2010 5:17:01 PM PST
>> *To: [email-masked] <mailto:[email-masked]>
>> *Cc: [email-masked] <mailto:[email-masked]>
>> *Subject: **New Version Notification for draft-levis-roll-trickle-00 *
>>
>>
>> A new version of I-D, draft-levis-roll-trickle-00.txt has been
>> successfuly submitted by P Levis and posted to the IETF repository.
>>
>> Filename: draft-levis-roll-trickle
>> Revision: 00
>> Title: The Trickle Algorithm
>> Creation_date: 2010-02-25
>> WG ID: Independent Submission
>> Number_of_pages: 8
>>
>> Abstract:
>> The Trickle algorithm allows wireless nodes to exchange information
>> in a highly robust, energy efficient, simple, and scalable manner.
>> Dynamically adjusting transmission windows allows Trickle to spread
>> new information on the scale of link-layer transmission times while
>> sending only a few messages per hour when information does not
>> change. A simple suppression nechanism and transmission point
>> selection allows Trickle's communication rate to scale
>> logarithmically with density. This document describes Trickle and
>> considerations in its use.
>>
>>
>>
>> The IETF Secretariat.
>>
>>
>

---

From: Phoebus Chen <[email-masked]>
Date: Mon, 08 Mar 2010 23:47:31 +0100

Sorry, I just realized the last part of my example is bad... see the 
correction below.

> Let me illustrate with an example:

Disregard the last two sentences.  Since A and B has the same rank, C 
wouldn't have a problem with it's rank computation, just with it's 
choice of parents.  That's what I was concerned with.  If we are using 
metrics for consistency checks, and the metric is computed from multiple 
parents (rather than the single best parent), this would also be a problem.

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 09 Mar 2010 08:31:21 -0500

> Date: Mon, 08 Mar 2010 23:27:55 +0100
> From: Phoebus Chen <[email-masked]>
> 
> [example elided]

Phoebus,

There was an earlier dicussion of this on the roll list.
See, for example, 

http://www.ietf.org/mail-archive/web/roll/current/msg01381.html

The thread was a discussion mostly between Jonathan and
myself about the redundancy counter and whether DIOs should
be suppressed.  In the end the agreement was that "it
depends".  The value of DIO suppression varies in different
use cases, making it a requirement in some and unimportant
in others.  

In the current draft the DIORedundancyConstant is settable
on a per-DODAG basis.  For those cases where the benefit of
more reliable DIO information outweighs the cost of sending
more of them, setting DIORedundancyConstant to 0xFF disables
the DIO suppression mechanism entirely.

                             -Richard Kelsey

---

From: Phoebus Chen <[email-masked]>
Date: Tue, 09 Mar 2010 15:46:03 +0100

Richard,

Thanks for bringing up that very relevant discussion thread... I had 
forgotten about it.  I guess this issue is partially resolved by falling 
back to disabling the suppression mechanism.

I was hoping that something more clever could be done by modifying 
Trickle's mechanisms, as Joakim, Phil, and Omprakash seemed to have been 
doing.  And maybe by redefining the consistency check.  I don't have any 
good suggestions regarding this right now, so I was probing the list for 
the current status on this issue.  Thanks for your response.

Phoebus

On 3/9/10 2:31 PM, Richard Kelsey wrote:
>> From: Phoebus Chen<[email-masked]>
>>

---

From: Omprakash Gnawali <[email-masked]>
Date: Tue, 9 Mar 2010 13:28:09 -0800

On Tue, Mar 9, 2010 at 6:46 AM, Phoebus Chen <[email-masked]> wrote:
> I was hoping that something more clever could be done by modifying Trickle's
> mechanisms, as Joakim, Phil, and Omprakash seemed to have been doing.  And
> maybe by redefining the consistency check.  I don't have any good
> suggestions regarding this right now, so I was probing the list for the
> current status on this issue.  Thanks for your response.

Joakim, Phil, and I did some experiments to explore variations in
Trickle and what if any impact it would have on propagation speeds. We
found some corner cases where dissemination latency can be long. And
it turns out if we tweak the Trickle algorithm to improve Trickle
timer schedule synchronization among the nodes, not only does the
latency go down but also the pkt tx overhead per node becomes more
uniform across the network. These explorations were done in the
context of dissemination of key-values to the network rather than
using Trickle to time the beacons for a routing protocol. We haven't
explored these variations in the context of RPL or RPL-like protocols
(eg. CTP). The impact might not be pronounced, however we don't have
evidence either way at the moment.

- om_p

---

From: Omprakash Gnawali <[email-masked]>
Date: Tue, 9 Mar 2010 13:39:09 -0800

> the DIO suppression mechanism entirely.

There is evidence that a threshold that is too low can be detrimental.
In CTP, I can see the path cost go up with low thresholds. I can guess
that the right threshold is network/density dependent.

As Phoebus points out, the definition of inconsistency gets more
complicated when we start using different metrics. If a path has
become inconsistent according to one metric but is still consistent
according to another metric, is that an inconsistency? Perhaps. But
the answer might sometimes depend on the combination of the metrics
being used for routing as well as the relative importance of each
metric in a particular metric. It might be more important to ensure
that a network is "consistent" according to a particular metric but
not so important to maintain strict consistency according to other
metrics in the same network.

- om_p

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Tue, 9 Mar 2010 23:50:27 +0200

Hi,

See concern regarding pkt tx overhead per node becomes more uniform across
the network (marked <Y> </Y>).

Thanks,
Yoav

-----Original Message-----
From: [email-masked] [mailto:[email-masked]] On Behalf Of
Omprakash Gnawali
Sent: Tuesday, March 09, 2010 11:28 PM
To: [email-masked]
Cc: [email-masked]
Subject: Re: [Roll] Fwd: New Version Notification for
draft-levis-roll-trickle-00

> I was hoping that something more clever could be done by modifying
Trickle's

uniform across the network.

<Y>
Consider the case where there is a large "cloud" of nodes that borders
with a smaller cloud where all nodes are transmitting at the same uniform
rate (see figure below).
If the tx rates are uniform across the network, the overall number of
transmissions in the large cloud may be significantly larger than the
smaller cloud.
In addition, the border nodes that are in both clouds will suffer most
(experience approximately twice as many transmissions).
Alternatively, if the rate per station is small, it will take a longer
time for reaching consistency in the smaller cloud relative to the time in
the larger cloud.

  Small cloud
   of nodes
        |
   OOO  |
  O   O O
 O     O O
  O   O|O
   OOO +----- border nodes (experiencing transmissions from both clouds)
    |
Large cloud
  of nodes

It would be nice if the trickle overall number of transmissions within a
cloud can be somehow limited by some sort of congestion control algorithm
thereby balancing the traffic rates experienced and smoothing the
consistency update durations within each cloud.

</Y>

These explorations were done in the

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

---

From: Philip Levis <[email-masked]>
Date: Sun, 14 Mar 2010 22:38:51 -0700

On Mar 8, 2010, at 2:27 PM, Phoebus Chen wrote:

> Did you find any resolution to Trickle's load balancing problem that was discussed in this previous thread?

We've been discussing it with Joakim.

The short answer is that these are contrived edge cases. They can happen in practice, but are *very* unlikely and the next Trickle reset will clear them. So while we do want to solve them for the sake of completeness, (Joakim has been evaluating some ideas and showing me and Om the results), I don't think they're a significant issue in real situations.

> regarding how Trickle affects the selection of parents (or how the rules on how to defer joining a DODAG may affect Trickle's operation, point #2 I made in the email thread).

This is a good point -- the Trickle draft tries to address this, by noting a protocol should specify what constitutes a redundant transmission. 

> I am concerned that the redundancy suppression mechanisms in Trickle will suppress the DIO advertisements of some of the potential parents of a node, and the node will end up choosing a bad parent (or bad parents).

Well, do you mean bad in terms of Rank, or ba

> Assume that "DIOs that advertise the same rank" are considered redundant, as suggested by (draft-ietf-roll-rpl-06, pg. 38, Section 5.3.5.1.1).
> 
> Nodes A, B, and C are waiting to connect to the DODAG.  Node A connects to the DODAG first, starts it's Trickle timer, and advertises its DIO, but C misses the message (maybe a fluke, because an 802.11 access point happened to go off nearby).  After roughly I_min, Node B connects to the DAG (but node A is not a parent), starts it's Trickle timer, and advertises the same rank as A.  Node B may have deferred joining the DODAG for I_min because it wanted to find a better parent.  Now, node B always has a shorter interval I than node A, so it should always advertise its DIO before node A (since T is always within [I/2,I]).  If the redundancy constant is set to 1, then B will always suppress A (until a packet is lost, but let's say this is uncommon).

True, unless some other node suppresses B. This also assumes that B's messages are never lost by A. RPL allows a DODAG Root to increment the sequence number, such that Trickle timers reset in a more coherent fashion if such problems occur.

> Could you guys give your thoughts on this?

Generally, it's possible to come up with constructed edge cases under which Trickle acts poorly; in practice, the general messiness of wireless networks (packet losses, etc.) means they rarely last long.

Phil

---

From: Omprakash Gnawali <[email-masked]>
Date: Mon, 15 Mar 2010 01:13:25 -0700

Section 5 of the draft states that Imin should not be used to specify
the minimum interval. I wonder if this makes the intervals too
abstract for RPL implementations. Are the implementations allowed to
hard code the minimum interval? Will there be a dynamic lookup
mechanism into the link layer or compile time flags to learn about the
worst case latency?

It is not clear if Imax should be specified as a function of the worst
case link layer latency.

"Worst case latency is the time until the first
      link-layer transmission of the frame assuming an idle channel
      (does not include backoff, virtual carrier sense, etc.).
"

Does it include preamble, etc.?

Are we talking about only the function of data rate (transmisstion) ?

- om_p

---

From: Philip Levis <[email-masked]>
Date: Mon, 15 Mar 2010 09:08:40 -0700

On Mar 15, 2010, at 1:13 AM, Omprakash Gnawali wrote:

> hard code the minimum interval?

No -- because it is specified in the DIO suboption. Note that these specifications are only for the *default* values. The draft does *not* say a protocol has to specify Imin in terms of this parameter.

> Will there be a dynamic lookup

If you want a code implementation that is 100% link layer independent, then there must be some way to specify or compute this value. It could be an interface the OS provides, a compile-time constant, etc.

The basic reason is pretty simple: given the really huge variation in link layer latencies once you consider low-power link layers, it is a bad idea for a network protocol to specify time values. Let's take RPL as an example. If it specifies the default value as 1 second, this could be too small (for ultra-low power link layers) or too big (for 802.11abgn). However, if it specifies the default value as a factor of the link-layer latency (e.g., 4), then the *default* value works across different link layers.

Having time constants in network protocols just doesn't work when you have the 3+ orders of magnitude range that low-power link layers can bring.

Note that while Imin in a protocol specification is in terms of this value, this does not mean that protocols must specify it in terms of it. E.g., it would perfectly fine for a RPL network configuration suboption to specify a value for Imin in milliseconds.

> It is not clear if Imax should be specified as a function of the worst

You mean Imin? What should it be specified in terms of?

> Are we talking about only the function of data rate (transmisstion) ?

Jonathan Hui also brought this up. I agree that the current wording is suboptimal. 

The basic goal is to have some notion of how long a packet can take. My original intention was to include preamble and backoff times, but not congestion or retransmissions. E.g., if the channel is clear and the packet is delivered successfully, how long could it take? This seemed like the most useful measure to me, but I could be wrong. Do you think there's a better one?

Phil

---

From: Omprakash Gnawali <[email-masked]>
Date: Mon, 15 Mar 2010 12:47:01 -0700

On Mon, Mar 15, 2010 at 9:08 AM, Philip Levis <[email-masked]> wrote:
...
> You mean Imin? What should it be specified in terms of?

The text does not say Imax should also be specified in terms of link
layer latency. It only talks about Imin in relation to worst case
latency. I was wondering if that was intentional or something to be
fixed in the next version.

> The basic goal is to have some notion of how long a packet can take. My original intention was to include preamble and backoff times, but not congestion or retransmissions. E.g., if the channel is…

One approach would be to abstract everything that the link layer does
and just look at the maximum delay between packet hand off to the link
layer and final success/failure notification/status determination for
that packet. This would include retx, channel access times, node wake
up times, and everything else. One advantage of this approach is two
DIOs with interval larger than this time at the transmitter will
maintain that time difference at the receiver. Otherwise, the timing
is less useful in this type of reasoning.

If the DIOs are all broadcast, we don't need to worry about retx.

- om_p

---

From: Omprakash Gnawali <[email-masked]>
Date: Mon, 15 Mar 2010 12:52:36 -0700

> maintain that time difference at the receiver. Otherwise, the timing

One correction - the DIOs will be separated in time, that is all that
can be guaranteed with this approach.

- om_p

---

From: Phoebus Chen <[email-masked]>
Date: Mon, 15 Mar 2010 21:37:00 +0100

Hey Phil,
	Glad to see you're back.  See comments below.

On 3/15/10 6:38 AM, Philip Levis wrote:
> The short answer is that these are contrived edge cases. They can happen
> in practice, but are *very* unlikely and the next Trickle reset will
> clear them. So while we do want to solve them for the sake of
> completeness, (Joakim has been evaluating some ideas and showing me and
> Om the results), I don't think they're a significant issue in real
> situations.
>
>> regarding how Trickle affects the selection of parents (or how the
>> rules on how to defer joining a DODAG may affect Trickle's operation,
>> point #2 I made in the email thread).
>
> This is a good point -- the Trickle draft tries to address this, by
> noting a protocol should specify what constitutes a redundant transmission.
>
>> will suppress the DIO advertisements of some of the potential parents
>> of a node, and the node will end up choosing a bad parent (or bad
>> parents).
>
>> but C misses the message (maybe a fluke, because an 802.11 access
>> point happened to go off nearby). After roughly I_min, Node B connects
>> to the DAG (but node A is not a parent), starts it's Trickle timer,
>> and advertises the same rank as A. Node B may have deferred joining
>> the DODAG for I_min because it wanted to find a better parent. Now,
>> node B always has a shorter interval I than node A, so it should
>> always advertise its DIO before node A (since T is always within
>> [I/2,I]). If the redundancy constant is set to 1, then B will always
>> suppress A (until a packet is lost, but let's say this is uncommon).
>
> True, unless some other node suppresses B. This also assumes that B's
> messages are never lost by A. RPL allows a DODAG Root to increment the
> sequence number, such that Trickle timers reset in a more coherent
> fashion if such problems occur.
>

Hmm, I'm still not fully convinced that scenarios similar to the one I 
described are edge cases.  My point is that a rare event, such as a 
missed DIO advertisement, along with Trickle suppressions could throw 
the network into an unbalanced state with nodes not equally sharing the 
responsibility of sending DIO advertisements.  In this respect, the load 
balancing in Trickle is not robust to rare events.  I agree with you 
that packet losses may be able to reset this imbalance eventually, but 
I'm concerned that by the time this happens, nodes that were listening 
to these DIO advertisements to choose their parents will have already 
joined the network and committed to a rank.  I don't have a firm grasp 
of how "suboptimal" this would be, or even if once can "bound" in a 
probabilistic sense how suboptimal the topology is (as measured by a 
metric in the OF) relative to an RPL topology where all transmissions 
were perfect.

Also, incrementing the DODAG sequence number from the root is a 
heavy-handed, global approach to "reset in a more coherent fashion" the 
Trickle timers.  You may "fix" the Trickle timers one part of the 
network (no lost DIOs), but "break" the Trickle timers in other parts of 
the network (lose DIOs where originally you did not lose them).

> Generally, it's possible to come up with constructed edge cases under
> which Trickle acts poorly; in practice, the general messiness of
> wireless networks (packet losses, etc.) means they rarely last long.
>

Another place where the Trickle intervals of neighboring nodes can be 
partially unsynchronized is in the (currently unspecified) time that 
nodes can defer before joining the RPL topology.  You mentioned in 
http://www.ietf.org/mail-archive/web/roll/current/msg02710.html that 
load balancing is imperfect when a network is mostly synchronized but a 
few nodes are out of phase.  I'm trying to think of how one can design a 
rule for nodes to defer joining the network that can guarantee with high 
probability that we can avoid that situation in most network 
deployments, and right now I don't have an answer.

I hope we'll get a better understanding of how Trickle operates in RPL 
over time.  It will help us isolate problems in RPL deployments in the 
future, i.e. understand which parameters were tuned wrong when the 
metric being optimized on the topology is far worse than expected.

---

From: Philip Levis <[email-masked]>
Date: Tue, 16 Mar 2010 17:15:24 -0700

> fixed in the next version.

IMax is defined as a number of doublings of the minimum interval. It's therefore implicitly defined in terms of link layer latency. Or am I missing something?

> is less useful in this type of reasoning.

This gets tricky when one considers an always busy channel: in theory, a packet can back off indefinitely.

I agree that a better wording is needed: I'm just not sure yet what it should be.

Phil

---

From: Omprakash Gnawali <[email-masked]>
Date: Tue, 16 Mar 2010 18:06:24 -0700

> I agree that a better wording is needed: I'm just not sure yet what it should be.

If we are using retx, there might be max retx. For backoffs, there
might be maximum number of them. Does 15.4 spec has bounds on these
times?

We can also specify in terms of minimum time, which is what you were
thinking originally I think.

- om_p