Subject: [Roll] WG Last Call on draft-ietf-roll-trickle-02

From: JP Vasseur <[email-masked]>
Date: Wed, 28 Jul 2010 10:05:41 +0200

Dear WG,

draft-ietf-roll-trickle-02 is stable and now ready for WG Last Call.

This starts a 2-week Working Group last call ending on August 11 at  
9:00am ET.

Please send your comments to the authors and the list.

Thanks.

JP.

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Thu, 29 Jul 2010 09:58:20 +0300

Authors/ROLL WG,

Find below some minor comments/clarifications I have on the Trickle draft.

Suggest to replace the term “wireless” with “LLN” (trickle is potentially
not used solely by wireless – though it was developed on a wireless platform
I understand).

It appears in the abstract, in the intro, at the last para of section 3., at
section 6.7.

“Abstract

   The Trickle algorithm allows *wireless* nodes to exchange information

   in a highly robust,...”

“1.  Introduction

   The Trickle algorithm is designed for *wireless* networks.”

“3. Trickle Algorithm Overview

   … Sparser networks require more transmissions per node, but

   utilization of the radio channel over space will not increase.  This

   is an important property in *wireless* networks, where the channel is a

   valuable shared resource.”

“6.7.  Tweaks and improvements to Trickle

   … However, in dynamic network environments such as *wireless*,

   the coordination needed to compute the…

Last paragraph of section 3 is a little unclear to me.

“  A single, disconnected node must transmit at the communication rate.”

Can you clarify this sentence? What do you mean by “must transmit at the
communication rate”? The communication rate is the output of the number of
transmissions a disconnected node makes, not the other way around.

“  In a lossless, single-hop network of size n, the sum of transmissions

   over the network is the communication rate, so for each node it is

   1/n.”

I think “the sum of transmissions” should be “the sum of transmission
rates”, right? This property is true only if all nodes have the same arrival
rates. Is this always the case, or just the case when using trickle? You
probably mean that this is a long term average, not always, right?

   Sparser networks require more transmissions per node, but

   utilization of the radio channel over space will not increase.  This

   is an important property in wireless networks, where the channel is a

   valuable shared resource.  Additionally, reducing transmissions in

   dense networks conserves system energy.”

I think the word Trickle is missing in the above to emphasize the fact
that what you describe is true for the trickle mechanism, not in a
network consisting of both trickle control data together with
application data.

I have some questions/clarifications for section 4.2:

Generally, what I think required is a more precise description of the
term “interval”.

When does an interval start? When did the previous ended? After the
previous I expires or when t is reached (and transmission or
suppression of transmission is decided on)? It is not so clear in the
text. If it is  when I expires, then after the transmission a node
must wait from the randomized time t till I expires and then
re-randomize the next t, and that leads to the question of what
happens with all the (in)consistencies it hears till the next interval
starts? Should they be counted as well (in step 2 it says to count all
consistencies and in step 1 it says to set c to 0, i.e. disregard
counts from t till I expires)? Some clarification would be helpful.

One comment on operational considerations (section 6):

Do you see value in describing some typical “events” that can be used to
reset the timer? What are the guidelines/limitations for doing these resets,
what could be considered good events and what could be considered bad
events?

Best regards,

Yoav

---

From: Chauvenet Cédric <[email-masked]>
Date: Thu, 29 Jul 2010 11:09:04 +0200

Hi all,

I support first Yoav comment.

As RPL is PHY agnostic, wireless references should be limited.
The LLN term is more general end well suited here.

Regards,
Cédric

Le 29 juil. 2010 à 08:58, Yoav Ben-Yehezkel a écrit :

> Suggest to replace the term “wireless” with “LLN” (trickle is potentially not used solely by wireless – though it was developed on a wireless platform I understand).
>  
> It appears in the abstract, in the intro, at the last para of section 3., at section 6.7.
> “Abstract
>  
>    The Trickle algorithm allows wireless nodes to exchange information
>    in a highly robust,...”
>  
>  
> “1.  Introduction
>  
>    The Trickle algorithm is designed for wireless networks.”
>  
>    … However, in dynamic network environments such as wireless,
> Can you clarify this sentence? What do you mean by “must transmit at the communication rate”? The communication rate is the output of the number of transmissions a disconnected node makes, not the other way around.
>  
> I think “the sum of transmissions” should be “the sum of transmission rates”, right? This property is true only if all nodes have the same arrival rates. Is this always the case, or just the case when using trickle? You probably mean that this is a long term average, not always, right?
>  
> I think the word Trickle is missing in the above to emphasize the fact that what you describe is true for the trickle mechanism, not in a network consisting of both trickle control data together with application data.
>  
>  
> Generally, what I think required is a more precise description of the term “interval”.
> When does an interval start? When did the previous ended? After the previous I expires or when t is reached (and transmission or suppression of transmission is decided on)? It is not so clear in the text. If it is  when I expires, then after the transmission a node must wait from the randomized time t till I expires and then re-randomize the next t, and that leads to the question of what happens with all the (in)consistencies it hears till the next interval starts? Should they be counted as well (in step 2 it says to count all consistencies and in step 1 it says to set c to 0, i.e. disregard counts from t till I expires)? Some clarification would be helpful.
>  
> Do you see value in describing some typical “events” that can be used to reset the timer? What are the guidelines/limitations for doing these resets, what could be considered good events and what could be considered bad events?
>  
> Best regards,
> Yoav
>  
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll

---

From: Philip Levis <[email-masked]>
Date: Thu, 29 Jul 2010 11:49:53 +0200

Yoav, my comments are inline.

>    the coordination needed to compute the…

This is a good point. What this text is trying to get at is that Trickle is designed for, and well-suited to, lossy broadcast media. We've never really examined its use in low-loss switched networks (e.g., Ethernet). When the algorithm was designed, lossy broadcast media basically meant wireless, and not just low-power wireless. E.g., Trickle is well suited to 802.11. We didn't really consider PLC -- in the context of ROLL, however, it should definitely be considered.

Correspondingly, I don't think LLN is the right term either. How about "lossy broadcast-based networks," with a few examples (e.g., wireless, PLC)?

> Can you clarify this sentence? What do you mean by “must transmit at the communication rate”? The communication rate is the output of the number of transmissions a disconnected node makes, not the…

Ah -- I see. This sentence is referring to the prior paragraph, which reads:

"As long as the network is connected and there is some minimum communication rate for each node, the network will reach eventual consistency."

The point is that communication is either transmission or reception and that the edge case of a solitary node, its communication will be all transmissions. In networks of multiple nodes, a node's communication can be some mix of receptions and transmissions.

Would it make more sense if the text read "Trickle communication rate" rather than "communication rate?"

> I think “the sum of transmissions” should be “the sum of transmission rates”, right? This property is true only if all nodes have the same arrival rates. Is this always the case, or just the case w…

I don't understand -- the same arrival rates? It's a lossless, single-hop network: when a node transmits, every other node hears the transmission. So the communication (reception+transmission) rates across the network are uniform.

> I think the word Trickle is missing in the above to emphasize the fact that what you describe is true for the trickle mechanism, not in a network consisting of both trickle control data together wi…

Which sentence do you think is unclear? Is it that application data does not necessarily follow this property of scaling? I'd like to think there is some context, and that it doesn't have to be that every sentence says Trickle in it.

> When does an interval start? When did the previous ended? After the previous I expires or when t is reached (and transmission or suppression of transmission is decided on)? It is not so clear in th…

From -02:

   o I, the current interval size

   1.  When an interval begins, Trickle resets c to 0 and sets t to a
       random point in the interval, taken from the range [I/2, I).

I'm not sure how this can be more precise... would changing the text to

   1.  When an interval begins, Trickle resets c to 0 and sets t to a
       random point in the interval, taken from the range [I/2, I). The
       interval ends at I.

be helpful?

> Do you see value in describing some typical “events” that can be used to reset the timer? What are the guidelines/limitations for doing these resets, what could be considered good events and what c…

I'm really a bit wary of doing this -- almost any recommendations we could come up with would be wrong in some cases. E.g., the recommendations for multicast are very different than protocol acknowledgment timing. Perhaps the document can point to references of a few examples of its use, from which a reader might benefit?

Phil

---

From: Joakim Eriksson <[email-masked]>
Date: Thu, 29 Jul 2010 12:10:14 +0200

Regarding mismatched Imax,

 From section: 6.3.  Mismatched Imax:

"If nodes do not agree on Imax, then this can cause long-term problems
    with transmission load.  Nodes with small Imax values will transmit
    faster, suppressing those with larger Imax values.  The nodes with
    larger Imax values, always suppressed, will never transmit.  In the
    base case, when the network is consistent, this can cause long-term
    inequities in energy cost."

This only mentions problems with energy costs. But is it not also a
problem if these nodes that never transmits are also the only link to
other nodes in the network? This might cause very slow propagation of
new information to these weakly connected parts of the network.

I think it is a good thing to warn a bit more for mismatched Imax.

Best regards,
-- Joakim Eriksson, SICS

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Thu, 29 Jul 2010 13:47:43 +0300

Thanks Phil,

I think now I understand better some of the points. With these
understandings, I’d like to bring up some more the topics for further
discussion. I’m OK with all your explanations excluding the ones that are in
the below list.

----

…

Phil: "Correspondingly, I don't think LLN is the right term either. How
about "lossy broadcast-based networks," with a few examples (e.g., wireless,
PLC)?"

Yoav: I definitely support the examples.

I'm not familiar with the term "lossy broadcast-based networks", is this a
commonly used term? To me, something like "lossy and partially connected
networks" would make more sense. But if people understand what that means, I
wouldn't object.

----

> Last paragraph of section 3 is a little unclear to me.

…

Phil: Would it make more sense if the text read "Trickle communication rate"
rather than "communication rate?"

Yoav: It would make sense to explain some terminology. For example,
communication rate, maybe also: (in)consistency, event, maybe also “lossy
broadcast-based networks” that you spoke of earlier. Specifically, to me the
term “communication rate” was not self-explanatory and I would appreciate it
if you described it somewhere.

Yoav: Something like: ”communication rate – the communication rate of a node
is the sum of transmission and reception rates of this node.”

Yoav: maybe also: “Trickle communication rate – the trickle communication
rate equals the communication rate of trickle messages only.”

With this understanding in mind, I still think that the sentence:

Yoav: Is somewhat misleading, and mixes the outcome with the given scenario.

Yoav: Would you consider a re-write in the form of:

Yoav: "In the case of a single, disconnected node, the communication rate is
equal to the transmission rate."

Yoav: Is this what you were trying to say?

----

>    1/n.”

…

Yoav: How does one sum up transmissions? It is not a numeric value. One can
count them, or sum their rates.

Yoav: I agree that the transmission rates will be uniformly distributed when
using the trickle and the same communication rates will be the sum of the
transmission rates.

Yoav: Trying to follow this logic, I would like to propose the following
re-write here:

Yoav: " In a lossless, single-hop network of size n, the sum of transmission
rates of trickle messages (summed over all nodes) equals the trickle
communication rate of each node separately. The trickle mechanism balances
the load in such a scenario, such that for each node, the transmission rate
of trickle messages is 1/n times the trickle communication rate."

Yoav: Is the above correct? Does it clarify my point better?

----

> I have some questions/clarifications for section 4.2:

…

Phil: I'm not sure how this can be more precise... would changing the text
to

Phil:   1.  When an interval begins, Trickle resets c to 0 and sets t to a

       interval ends at I.

Phil: be helpful?

Yoav: Yes! So is my understanding that between t and I, there's no meaning
to counting consistencies correct? Would it promote this understanding (not
so much implementation or correctness) if you change rule 2. to:

Yoav: " 2.  Whenever Trickle hears a transmission that is "consistent," it

       increments counter c." to:

Yoav: " 2. Whenever Trickle hears a transmission that is "consistent," *until
t expires*, it

       increments counter c."

----

> One comment on operational considerations (section 6):

…

Phil: Perhaps the document can point to references of a few examples of its
use, from which a reader might benefit?

Yoav: that would be good enough for me.

----

Thanks for the productive response.

Best Regards,

Yoav

-----Original Message-----
From: Philip Levis [mailto:[email-masked]]
Sent: Thursday, July 29, 2010 12:50 PM
To: Yoav Ben-Yehezkel
Cc: [email-masked]; [email-masked]; [email-masked];
[email-masked]; [email-masked]
Subject: Re: [Roll] WG Last Call on draft-ietf-roll-trickle-02

>    the coordination needed to compute the…

This is a good point. What this text is trying to get at is that Trickle is
designed for, and well-suited to, lossy broadcast media. We've never really
examined its use in low-loss switched networks (e.g., Ethernet). When the
algorithm was designed, lossy broadcast media basically meant wireless, and
not just low-power wireless. E.g., Trickle is well suited to 802.11. We
didn't really consider PLC -- in the context of ROLL, however, it should
definitely be considered.

Correspondingly, I don't think LLN is the right term either. How about
"lossy broadcast-based networks," with a few examples (e.g., wireless, PLC)?

"As long as the network is connected and there is some minimum communication
rate for each node, the network will reach eventual consistency."

The point is that communication is either transmission or reception and that
the edge case of a solitary node, its communication will be all
transmissions. In networks of multiple nodes, a node's communication can be
some mix of receptions and transmissions.

Would it make more sense if the text read "Trickle communication rate"
rather than "communication rate?"

I don't understand -- the same arrival rates? It's a lossless, single-hop
network: when a node transmits, every other node hears the transmission. So
the communication (reception+transmission) rates across the network are
uniform.

> I think the word Trickle is missing in the above to emphasize the fact
that what you describe is true for the trickle mechanism, not in a network
consisting of both trickle control data together with application data.

Which sentence do you think is unclear? Is it that application data does not
necessarily follow this property of scaling? I'd like to think there is some
context, and that it doesn't have to be that every sentence says Trickle in
it.

> When does an interval start? When did the previous ended? After the
previous I expires or when t is reached (and transmission or suppression of
transmission is decided on)? It is not so clear in the text. If it is  when
I expires, then after the transmission a node must wait from the randomized
time t till I expires and then re-randomize the next t, and that leads to
the question of what happens with all the (in)consistencies it hears till
the next interval starts? Should they be counted as well (in step 2 it says
to count all consistencies and in step 1 it says to set c to 0, i.e.
disregard counts from t till I expires)? Some clarification would be
helpful.

       interval ends at I.

be helpful?

I'm really a bit wary of doing this -- almost any recommendations we could
come up with would be wrong in some cases. E.g., the recommendations for
multicast are very different than protocol acknowledgment timing. Perhaps
the document can point to references of a few examples of its use, from
which a reader might benefit?

Phil

---

From: Philip Levis <[email-masked]>
Date: Thu, 29 Jul 2010 14:37:11 +0200

On Jul 29, 2010, at 12:47 PM, Yoav Ben-Yehezkel wrote:

> Thanks Phil,
>  
> I think now I understand better some of the points. With these understandings, I’d like to bring up some more the topics for further discussion. I’m OK with all your explanations excluding the ones that are in the below list.
>  
> ----
> Phil: "Correspondingly, I don't think LLN is the right term either. How about "lossy broadcast-based networks," with a few examples (e.g., wireless, PLC)?"
>  
> I'm not familiar with the term "lossy broadcast-based networks", is this a commonly used term? To me, something like "lossy and partially connected networks" would make more sense. But if people understand what that means, I wouldn't object.

Hm. My intention wasn't that it be a term, with long-standing implications; rather, it be a simple descriptive statement. The issue isn't partial connection (one could infer that to be a graph that isn't fully connected), rather packet loss.

> Phil: Would it make more sense if the text read "Trickle communication rate" rather than "communication rate?"
>  
> Yoav: It would make sense to explain some terminology. For example, communication rate, maybe also: (in)consistency, event, maybe also “lossy broadcast-based networks” that you spoke of earlier. Specifically, to me the term “communication rate” was not self-explanatory and I would appreciate it if you described it somewhere.
>  
> Yoav: Something like: ”communication rate – the communication rate of a node is the sum of transmission and reception rates of this node.”
> Yoav: maybe also: “Trickle communication rate – the trickle communication rate equals the communication rate of trickle messages only.

Section 3 says something very close:

"As long as every node communicates somehow - either receives or transmits - the need for an update will be detected."

> ”
> Yoav: "In the case of a single, disconnected node, the communication rate is equal to the transmission rate."
>  

Yes. I'd be happy to make that change.

> Yoav: How does one sum up transmissions? It is not a numeric value. One can count them, or sum their rates.

Rate is a count over time. You sum the transmissions in an interval.

>  
> Yoav: I agree that the transmission rates will be uniformly distributed when using the trickle and the same communication rates will be the sum of the transmission rates.
>  
> Yoav: Trying to follow this logic, I would like to propose the following re-write here:
> Yoav: " In a lossless, single-hop network of size n, the sum of transmission rates of trickle messages (summed over all nodes) equals the trickle communication rate of each node separately. The trickle mechanism balances the load in such a scenario, such that for each node, the transmission rate of trickle messages is 1/n times the trickle communication rate."
>  

It's correct. I'd clean up the text a little:

"In a lossless, single-hop network of size n, the communication rate at each node equals the sum of the Trickle transmission rates across all nodes. Trickle balances the load in such a scenario. Each node's Trickle transmission rate is 1/nth of Trickle communication rate."

Is that OK?

> Phil: I'm not sure how this can be more precise... would changing the text to
>  
> Yoav: Yes! So is my understanding that between t and I, there's no meaning to counting consistencies correct? Would it promote this understanding (not so much implementation or correctness) if you change rule 2. to:
>  
> Yoav: " 2. Whenever Trickle hears a transmission that is "consistent," until t expires, it
>        increments counter c."

I personally think this overspecifies. It turns out that incrementing c after t doesn't matter, but your text suggests you should add an if statement to the implementation. This is added code which doesn't accomplish anything -- exactly the kind of thing you want to avoid in LLNs. :)

> Phil: Perhaps the document can point to references of a few examples of its use, from which a reader might benefit?
>  

OK.

> Thanks for the productive response.

No problem. Thanks for the comments!

Phil

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Thu, 29 Jul 2010 17:29:31 +0300

Phil,

No more comments :)
Thanks for accommodating most of my comments, I find the specifications
clearer now.

Regards,
Yoav

-----Original Message-----
From: Philip Levis [mailto:[email-masked]]
Sent: Thursday, July 29, 2010 3:37 PM
To: Yoav Ben-Yehezkel
Cc: [email-masked]; [email-masked]; [email-masked];

> I think now I understand better some of the points. With these
understandings, I'd like to bring up some more the topics for further
discussion. I'm OK with all your explanations excluding the ones that are
in the below list.
>
> ----
> > Suggest to replace the term "wireless" with "LLN" (trickle is
potentially not used solely by wireless - though it was developed on a
wireless platform I understand).
> .
about "lossy broadcast-based networks," with a few examples (e.g.,
wireless, PLC)?"
> I'm not familiar with the term "lossy broadcast-based networks", is this
a commonly used term? To me, something like "lossy and partially connected
networks" would make more sense. But if people understand what that means,
I wouldn't object.

Hm. My intention wasn't that it be a term, with long-standing
implications; rather, it be a simple descriptive statement. The issue
isn't partial connection (one could infer that to be a graph that isn't
fully connected), rather packet loss.

> .
communication rate, maybe also: (in)consistency, event, maybe also "lossy
broadcast-based networks" that you spoke of earlier. Specifically, to me
the term "communication rate" was not self-explanatory and I would
appreciate it if you described it somewhere.
>
> Yoav: Something like: "communication rate - the communication rate of a
node is the sum of transmission and reception rates of this node."
> Yoav: maybe also: "Trickle communication rate - the trickle
communication rate equals the communication rate of trickle messages only.

"As long as every node communicates somehow - either receives or transmits
- the need for an update will be detected."

> "
>  "  A single, disconnected node must transmit at the communication
rate."

> ----
> >
> > "  In a lossless, single-hop network of size n, the sum of
transmissions
> >    1/n."
> .

>
> Yoav: I agree that the transmission rates will be uniformly distributed
when using the trickle and the same communication rates will be the sum of
the transmission rates.
re-write here:
> Yoav: " In a lossless, single-hop network of size n, the sum of
transmission rates of trickle messages (summed over all nodes) equals the
trickle communication rate of each node separately. The trickle mechanism
balances the load in such a scenario, such that for each node, the
transmission rate of trickle messages is 1/n times the trickle
communication rate."

"In a lossless, single-hop network of size n, the communication rate at
each node equals the sum of the Trickle transmission rates across all
nodes. Trickle balances the load in such a scenario. Each node's Trickle
transmission rate is 1/nth of Trickle communication rate."

Is that OK?

> .
> Yoav: Yes! So is my understanding that between t and I, there's no
meaning to counting consistencies correct? Would it promote this
understanding (not so much implementation or correctness) if you change
> Yoav: " 2. Whenever Trickle hears a transmission that is "consistent,"
until t expires, it

I personally think this overspecifies. It turns out that incrementing c
after t doesn't matter, but your text suggests you should add an if
statement to the implementation. This is added code which doesn't
accomplish anything -- exactly the kind of thing you want to avoid in
LLNs. :)

> .
> Phil: Perhaps the document can point to references of a few examples of
its use, from which a reader might benefit?

OK.

Phil