Subject: Re: [Roll] LC RPL-10

From: Nicolas DEJEAN <[email-masked]>
Date: Thu, 1 Jul 2010 20:51:45 +0200

Hi Pascal, WG,

2010/6/30 Pascal Thubert (pthubert) <[email-masked]>:
> Hi Michael:
>
> Chicken and an egg... The Last call is an opportunity to give us an
> hopefully last round of comments before we expose the spec to a larger
> audience.
>
> What it tells us is that the chairs trust that we are getting somewhere,
> and probably very close to where we want to be.
> What is also tells us is that now is a good time to reread the spec and
> see what's missing.
>
> We already know we need to add text on path sequence based on the FSM
> that was present till 08.
> There's also discussion on DAO Ack for non-storing that might impact the
> behavior described in 10,
> and non-RPL hosts support that might be incompletely described.
>
> Anything else we need to add / update / delete ?
>

As you asked for other updates, I had a look at rpl-10.

Despite the impressing amount of work performed on this version, I
have not seen any change concerning the DIS reception and Trickle
Timer Reset.
This issue was raised while dealing with Ticket #29.
http://www.ietf.org/mail-archive/web/roll/current/msg03810.html is the
last message posted on the thread (by me) before closing with the
conclusion that DIS could now carry TLVs.

This is already fine but the other subject discussed (that was not
part of the ticket #29) has been lost in the battle.

It seems to me that we had almost reached a concensus on this subject
by adding some flags in order to break the currently existing link
between:
- the transmission method used for sending the DIS (unicast/multicast)
- the Reset of the Trickle Timer (inconsistencies)
- the transmission method used for answering (again unicast/multicast)

Some flags were proposed:
- C/R flag for driving the reset of the Trickle Timer
- U flag for driving how the answered DIOs must be sent:unicast or multicast

In rpl-10, some options exist but there is no such flag defined.

Moreover, the second and third bullets describing the different
Trickle Timer reset cases in section 7.3 contain hard MUST that could
be softened by the flags proposed and let the door openened to some
evolutions.

IMHO, adding these 2 flags gives some opportunity to implement
solutions like the 'Quick connection process' I described without
adding complexity. Moreover, methods, goals and consequences will not
be linked (Clarity is also a protocol quality).

What do you think?

> Pascal

Thank you,

Nicolas.

>
>> -----Original Message-----
>> From: [email-masked] [mailto:[email-masked]] On Behalf
> Of
>> Michael Richardson
>> Sent: Wednesday, June 30, 2010 3:29 PM
>> To: David Culler
>> Cc: [email-masked]
>> Subject: Re: [Roll] LC RPL-10
>>
>>
>> >>>>> "David" == David Culler <[email-masked]> writes:
>>     David> Dear ROLL WG, I would like to propose that we Last Call rpl
>>     David> with http://www.ietf.org/id/draft-ietf-roll-rpl-10.txt.  We
>>     David> have completed a significant body of clean up and
>>     David> simplification items since IETF 77, and we have wrapped up
>>
>> I agree with WG LC on -10.txt, but not until after IETF78.
>> I'm not sure you understand what a last call is. It's not an
> opportunity
>> for:
>>
>>     David> settled down.  By going to LC now, we have three weeks to
>>     David> focus all of our attention on last minute clarifications
> and
>>     David> clean up of the document before Maastricht.  Those
>>     David> refinements will be captured in 11 once submissions reopen
> at
>>     David> IETF 78.
>>
>> A LC is what you do after those clarifications are done.
>>
>> --
>> ]       He who is tired of Weird Al is tired of life!           |
> firewalls  [
>> ]   Michael Richardson, Sandelman Software Works, Ottawa, ON    |net
>> architect[
>> ] [email-masked] http://www.sandelman.ottawa.on.ca/
>> |device driver[
>>    Kyoto Plus: watch the video
>> <http://www.youtube.com/watch?v=kzx1ycLXQSE>
>>                      then sign the petition.
>> _______________________________________________
>> Roll mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/roll
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>

---

From: Philip Levis <[email-masked]>
Date: Thu, 1 Jul 2010 19:45:44 -0700

> be linked (Clarity is also a protocol quality).

A couple of thoughts/opinions:

1) I personally don't think these optimizations matter much. The  
possible cost of disrupting Trickle is much, much higher than the  
cost of a few extra timer resets. In highly, highly dynamic  
environments, we see CTP's trickle-based control traffic to be 6-8%  
of the total traffic. Since CTP uses datapath validation, this is  
tied to the data rate (it wouldn't go up much if we lowered the data  
rate). In stable environments, it can be under 1%. If we're worried  
about the efficiency of RPL, this is *not* the place to start.

2) There's extensive research and deployment experience with Trickle;  
we know how it works both in theory and practice. This doesn't mean  
it can't be improved (Joakim has made several good points), but I'd  
strongly, strongly caution against tweaking it without a lot of  
evidence and testing first. Even slight changes can disrupt its  
delicate balance (e.g., waiting until interval expiration to reset  
can prevent the network from reaching consistency).

3) It is absolutely critical that reset be tied the transmission  
mechanism. In particular, it can be disastrous when a node responds  
immediately to a multicast message.

4) The Trickle timer is not doing more than it was intended to do; it  
is a simple yet amazingly powerful mechanism. One major use is  
establishing eventual consistency, but there are others.

Phil

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 02 Jul 2010 09:05:43 +0200

I think there are several security aspects of RPL that need to be
figured out.

o should IPsec AH be used instead of RPL Abit CCM* security.
o should security-framework draft and security in RPL draft be coherent
   (they seem to diverge in the preference of authentication over
   confidentiality).
o should the 6MAN RPL related documents be covered coherently by the
   same security as RPL.

When these are clearer I can provide technical comments to the RPL draft
security text, for example how to fix this:

draft-ietf-roll-rpl-10:
"The exact placement and format of message integrity/authentication
codes has not yet been determined."

For example, if I know IPsec AH is used instead of Abit CCM* then I can
suggest where the placement and format of authentication.

and this:
"[reference to RoLL security-framework absent]"

If I know the two docs should in sync then I suggest to refer each other.

Alex

Le 30/06/2010 06:16, David Culler a écrit :
> Dear ROLL WG, I would like to propose that we Last Call rpl with
> http://www.ietf.org/id/draft-ietf-roll-rpl-10.txt.  We have completed
> a significant body of clean up and simplification items since IETF
> 77, and we have wrapped up the critical open items, including routing
> security.  We have few open tickets.  We have areas of future work,
> but we have been able to separate them from the core spec, so they
> can be developed more fully while experience is gained with the core.
> We have numerous implementations that are operational and many many
> more that are waiting to be sure things have settled down.  By going
> to LC now, we have three weeks to focus all of our attention on last
> minute clarifications and clean up of the document before Maastricht.
> Those refinements will be captured in 11 once submissions reopen at
> IETF 78.
>
> So, please all in favor of LC on RPL-10...
> _______________________________________________ Roll mailing list
> [email-masked] https://www.ietf.org/mailman/listinfo/roll
>

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 2 Jul 2010 11:25:19 +0200

Hi Alex:

CCM is the de facto standard in the WSN space. It is used at all layers from 2 to 4. 
One deployed example is ISA100.11a that uses it in the data link and to build transport layer MICs.
The spec certainly needs to accommodate the real world, and in this case, the existing hardware assists present in the chipsets.

Pascal

> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> Alexandru Petrescu
> Sent: Friday, July 02, 2010 9:06 AM
> Cc: [email-masked]
> Subject: Re: [Roll] Security (was: LC RPL-10)
>

---

From: Philip Levis <[email-masked]>
Date: Fri, 2 Jul 2010 07:55:40 -0700

> codes has not yet been determined."

Ah -- nice catch. This is leftover text from -08 that should be  
removed. The document currently specifies where they should go.

Phil

---

From: Alexandru Petrescu <[email-masked]>
Date: Fri, 02 Jul 2010 17:41:14 +0200

Le 02/07/2010 11:25, Pascal Thubert (pthubert) a écrit :
> Hi Alex:
>
> CCM is the de facto standard in the WSN space. It is used at all
> layers from 2 to 4. One deployed example is ISA100.11a that uses it
> in the data link and to build transport layer MICs. The spec
> certainly needs to accommodate the real world, and in this case, the
>  existing hardware assists present in the chipsets.

Hmm, good to learn CCM is the de facto stadard in the WSN space, namely
ISA100.11a. (is ISA100.11a equating WSN).

IPsec AH hardware may already exist too, largely deployed in the real
world, de facto.

In addition to the availability of hardware (CCM vs e.g. MD4 of IPSec)
we could also discuss export control (is CCM more controlled than MD4?),
home space standards, smart grid standards - would they all use CCM de
facto?

We may discuss more about the CCM choice, I am all ears.

Alex

>
> Pascal
>
>
>> -----Original Message----- From: [email-masked]
>> [mailto:[email-masked]] On Behalf Of Alexandru Petrescu
>> Sent: Friday, July 02, 2010 9:06 AM Cc: [email-masked] Subject: Re:
>>  [Roll] Security (was: LC RPL-10)
>>
>> o should IPsec AH be used instead of RPL Abit CCM* security. o
>> should security-framework draft and security in RPL draft be
>> coherent (they seem to diverge in the preference of authentication
>>  over confidentiality). o should the 6MAN RPL related documents be
>>  covered coherently by the same security as RPL.
>>
>> When these are clearer I can provide technical comments to the RPL
>>  draft security text, for example how to fix this:
>>
>> draft-ietf-roll-rpl-10: "The exact placement and format of message
>>  integrity/authentication codes has not yet been determined."
>>
>> For example, if I know IPsec AH is used instead of Abit CCM* then I
>> can suggest where the placement and format of authentication.
>>
>> and this: "[reference to RoLL security-framework absent]"
>>
>>>  http://www.ietf.org/id/draft-ietf-roll-rpl-10.txt.  We have
>>> completed a significant body of clean up and simplification items
>>> since IETF 77, and we have wrapped up the critical open items,
>>> including routing security.  We have few open tickets.  We have
>>> areas of future work, but we have been able to separate them from
>>> the core spec, so they can be developed more fully while
>>> experience is gained with the core. We have numerous
>>> implementations that are operational and many many more that are
>>>  waiting to be sure things have settled down.  By going to LC
>>> now, we have three weeks to focus all of our attention on last
>>> minute clarifications and clean up of the document before
>>> Maastricht. Those refinements will be captured in 11 once
>>> submissions reopen at IETF 78.
>>>

---

From: Zach Shelby <[email-masked]>
Date: Tue, 6 Jul 2010 12:16:36 +0300

> The spec certainly needs to accommodate the real world, and in this case, the existing hardware assists present in the chipsets.

+1

-- 
Zach Shelby, Chief Nerd, Sensinode Ltd.
http://zachshelby.org  - My blog "On the Internet of Things"
http://6lowpan.net - My book "6LoWPAN: The Wireless Embedded Internet"
Mobile: +358 40 7796297

---

From: Tim Winter <[email-masked]>
Date: Mon, 12 Jul 2010 17:58:25 -0400

Hi Nicolas, Phil,

>> 2010/6/30 Pascal Thubert (pthubert) <[email-masked]>:

[SNIP]

> possible cost of disrupting Trickle is much, much higher than the cost
> of a few extra timer resets. In highly, highly dynamic environments, we
> see CTP's trickle-based control traffic to be 6-8% of the total traffic.
> Since CTP uses datapath validation, this is tied to the data rate (it
> wouldn't go up much if we lowered the data rate). In stable
> environments, it can be under 1%. If we're worried about the efficiency
> of RPL, this is *not* the place to start.
>
> 2) There's extensive research and deployment experience with Trickle; we
> know how it works both in theory and practice. This doesn't mean it
> can't be improved (Joakim has made several good points), but I'd
> strongly, strongly caution against tweaking it without a lot of evidence
> and testing first. Even slight changes can disrupt its delicate balance
> (e.g., waiting until interval expiration to reset can prevent the
> network from reaching consistency).
>
> 4) The Trickle timer is not doing more than it was intended to do; it is
> a simple yet amazingly powerful mechanism. One major use is establishing
> eventual consistency, but there are others.
>
> Phil

RPL-10 does keep some bits reserved in the DIS message as well as the Solicited 
Information option -- do you think that it would make sense to get more experience 
with the proposed  C/R, U flags and then, after they have been proved out and all of 
the ramifications are understood, to define them in a future extension to the RPL 
base specfication?

-Tim

---

From: Philip Levis <[email-masked]>
Date: Mon, 12 Jul 2010 16:07:02 -0700

On Jul 12, 2010, at 2:58 PM, Tim Winter wrote:

> Hi Nicolas, Phil,
> 
> 
> RPL-10 does keep some bits reserved in the DIS message as well as the Solicited Information option -- do you think that it would make sense to get more experience with the proposed  C/R, U flags and then, after they have been proved out and all of the ramifications are understood, to define them in a future extension to the RPL base specfication?

Sure, makes sense to me. Until then, we should strive for the minimum viable protocol.

Phil

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 13 Jul 2010 09:55:02 +0200

I'm on the same line as Tim and Phil for this one. 

In one hand I agree that the every DIS is not necessarily an
inconsistency that should trigger Trickle to reset its timer, but OTOH
I'm unsure that the originator has all the information to figure that
out.

Let us get more experience in determining which inconsistencies we
really care about, and then we'll publish add-ons to the standard that
cover those as required.

Pascal

> From: [email-masked] [mailto:[email-masked]] On Behalf
Of Philip
> Levis
> Sent: Tuesday, July 13, 2010 1:07 AM
> To: Tim Winter
> Cc: [email-masked]
> Subject: Re: [Roll] Proposed DIS flags (Re: LC RPL-10)
> 
> 
> > RPL-10 does keep some bits reserved in the DIS message as well as
the
> Solicited Information option -- do you think that it would make sense
to get
> more experience with the proposed  C/R, U flags and then, after they
have
> been proved out and all of the ramifications are understood, to define
them in
> a future extension to the RPL base specfication?
> 
> Sure, makes sense to me. Until then, we should strive for the minimum
viable
> protocol.

---

From: JP Vasseur <[email-masked]>
Date: Tue, 13 Jul 2010 11:05:55 +0200

I think so too. Nicolas, you could have a simple ID defining those  
bits in a separate document.
At least the DIS format is now flexible to allow for such extensions.

JP.

On Jul 13, 2010, at 1:07 AM, Philip Levis wrote:

>> the Solicited Information option -- do you think that it would make  
>> sense to get more experience with the proposed  C/R, U flags and  
>> then, after they have been proved out and all of the ramifications  
>> are understood, to define them in a future extension to the RPL  
>> base specfication?
>

---

From: Nicolas DEJEAN <[email-masked]>
Date: Tue, 13 Jul 2010 16:17:14 +0200

Hello Phil,

>1) I personally don't think these optimizations matter much.

Dominique had explained and documented in
http://www.ietf.org/mail-archive/web/roll/current/msg03306.html that
these optimizations do matter in our application domain. Please find
at the bottom of this message the description of an even more critical
case extracted from real life deployment.

>The
>of a few extra timer resets.

In principle,  I agree , yet see below what exactly we are requesting.

>In highly, highly dynamic environments, we
>environments, it can be under 1%.

The transmission rate of control information can be very low, yet the
reception rate can be high in very dense environment. We have been
severely affected by this in the past and have learned how to deal
with it.

>If we're worried about the efficiency

Maybe  there are other issues , but this one  alone  would lead to
real lifetime issues in Metering networks.

>network from reaching consistency).

OK, I understand the issue.

Clearly, I did not underline  enough  that this quick connection
process would  only  be used  by  leaf nodes which will not directly
change the network topology. As a consequence ,  inconsistency  will
not occur  in this case.

>immediately to a multicast message.

As a reminder, the proposal was to have two flags  in DIS packets   to
 driv e  the behavior of the  neighbor router :
- R flag:  controls  the reset of the Trickle Timer at the  neighbor router
- U flag: requests a unicast /multicast  answer from the  neighbor router

More precisely, the configuration R=0  (don't reset) and U=1
(unicast)  is the one we absolutely need.
As already explained above, this configuration should be reserved to
the quick attachment of a leaf node to the network, which will not
disrupt the network topology.

As a side comment, RPL is a routing protocol.  Collision avoidance
should be managed at the MAC layer.
For sure, we do not want to encourage a lot of immediate answers to a
multicast message. This is the "raison d'être" of the filtering
options in DIS.
Moreover, some MAC layers are able to correctly handle a decent number
of concurrent answers.

>eventual consistency, but there are others.

Without a mechanism to achieve the behavior that we proposed abo ve ,
RPL will not achieve the lifetime of currently deployed smart metering
networks using propriatery protocols.  Again, see msg... and msg...
for details.

>Phil

Thanks,

Nicolas.

-----------------------

As a complement to Dominique's example, a much more critical setting
is an appartment
building ensemble.
We have experienced rare "worst cases" where all meters and routers
are in radio range.
You still need a fair amount of routers for energy density and link stability.

Using the same notations as
http://www.ietf.org/mail-archive/web/roll/current/msg03306.html, here
are rough calculations:

****** with no DIS options
1 DIS transmission from meter, responded to by N meters and 3N/20 routeurs
NT = 1 + N + 3N/20 = 1 + 23N/20
All N meters and 3N/20 routers overhear all transmissions
NR = NT * 23N/20
Therefore
Etotal = 6 * NT + NT * 23N/20 = 6 * (1 + 23N/20) + (1 + 23N/20)*23N/20
= 6 + 8.05 N + 1.3225 N^2

******* with DIS options
still assuming 7 rounds are necessary to get a response
NT0 = 7
Let's assume that, in addition to the filtering mentioned in previous
mail, we also filter on node attribute to exclude responses from
meters
Number of DIO transmissions from meters NT1 = 0
Number of DIO transmissions from routers NT2 = N/40
NR = NT * 23N/20
Etotal = 6 * (7+N/40) + (7+N/40)*23N/20 = 42 + 6N/40 + 161N/20 + 23N^2/800

In this setting, the energy saving ranges from 3 to 20 as N is varied
accross [20..200].

-----------------------

---

From: Nicolas DEJEAN <[email-masked]>
Date: Tue, 13 Jul 2010 16:21:59 +0200

Hello Tim,

2010/7/12 Tim Winter <[email-masked]>:
> RPL-10 does keep some bits reserved in the DIS message as well as the
> Solicited Information option -- do you think that it would make sense to get
> more experience with the proposed  C/R, U flags and then, after they have
> been proved out and all of the ramifications are understood, to define them
> in a future extension to the RPL base specfication?
>
> -Tim

In a general manner, I would tend to agree.
However, what disturbs me in this particular case is that a critical
case as clearly been identified and documented.
I'm afraid that the barrier to adoption of the mechanism we need will
greatly increase once RPL is out as an RFC without them.

I would feel really more comfortable if:
- we defined the flags,
- take them into account in the different Trickle reset conditions,
- add a sentence  specifying the default behaviour to be  R=1 and U=0
(this is what we currently have with Trickle) ,
- add a sentence explaining how the case R= 0  and U=1 could be used
by leaf nodes.

Alternatively, can you suggest a better way of achieving the
well-identified behavior described above (leaf-node only, no reset,
unicast answer)?

Thanks,

Nicolas.

---

From: Nicolas DEJEAN <[email-masked]>
Date: Tue, 13 Jul 2010 16:27:28 +0200

Hello Pascal,

> I'm unsure that the originator has all the information to figure that

We have at least identified one case where the originator knows this:
the attachment as a leaf node.

> really care about, and then we'll publish add-ons to the standard that

What disturbs me in postponing the integration of these flags into the
specifications is that we already know a common case where the only
described behaviour will not fit in terms of energy consumption.

Please, read http://www.ietf.org/mail-archive/web/roll/current/msg03306.html
as a reference for this case.

Thanks,

Nicolas.

---

From: Nicolas DEJEAN <[email-masked]>
Date: Tue, 13 Jul 2010 16:32:10 +0200

Hello JP,

2010/7/13 JP Vasseur <[email-masked]>:
> I think so too. Nicolas, you could have a simple ID defining those bits in a
> separate document.

You are right, the DIS format should allow that.

My issue here is that on the one hand there is a collection of MUSTs
that drive the behaviour of Trickle and on the other hand  we have
shown that this behaviour does not  satisfy  a  clearly identified,
common ,  application category.

If we don't add NOW a way by which leaf-nodes can do a multicast DIS
request and get unicast reponses without Trickle timer reset, it will
be increasingly difficult to get that behavior later,  as it will have
to contradict some RFC text.

We are fine with specifying  the DIS filtering options in a separate
ID , since it will require some amount of text.

However,  creating  a separate  ID only for two  flag  bits  and one
bit combination seems  a bit odd  to me.

Thanks,

Nicolas.

>> viable protocol.

---

From: Philip Levis <[email-masked]>
Date: Tue, 13 Jul 2010 10:01:42 -0700

> case extracted from real life deployment.

I'm confused: the message you reference describes the need for filtering who responds to a DIS, mechanisms which are in the draft currently. There's no mention for need of U and R bits.

Phil

---

From: Nicolas DEJEAN <[email-masked]>
Date: Wed, 14 Jul 2010 10:58:32 +0200

Hello Phil,

> I'm confused: the message you reference describes the need for filtering who responds to a DIS, mechanisms which are in the draft currently. There's no mention for need of U and R bits.
You are right, this message in particular does not describe the
proposed flags but presents the impact of over-hearing in a well
identified case taken from real-life deployments.

http://www.ietf.org/mail-archive/web/roll/current/msg03810.html
presents a solution proposal for solving this critical case.

This proposal uses both DIS filtering and flags for avoiding increased
control traffic and thus over-hearing during deployment phases.

Thanks,

Nicolas.

---

From: Philip Levis <[email-masked]>
Date: Wed, 14 Jul 2010 10:29:11 -0700

> control traffic and thus over-hearing during deployment phases.

I'm still confused: is your concern that the requirement (scoping responses to DIS messages) isn't satisfied in the current draft, or are you insisting that RPL include your proposal without any changes?

Phil

---

From: Nicolas DEJEAN <[email-masked]>
Date: Thu, 15 Jul 2010 11:25:06 +0200

Hello Phil, WG,

> I'm still confused: is your concern that the requirement (scoping responses to DIS messages) isn't satisfied in the current draft, or are you insisting that RPL include your proposal without any ch…

The starting point is the critical case that was described.
One solution for solving this case is the mechanism I proposed (it is
not new, it has been validated in the field).
This proposal is more an example than a requirement.

My issue today is that the current draft completely forbids the
implementation of the mechanism I described as a multicast DIS
reception always:
- triggers the Reset of the Trickle Timer,
- implies answers sent in multicast.
These two consequences will clearly increase control traffic and thus
over-hearing phenomenon.

Implementation of the proposed mechanism requires some modifications
into the draft for having the ability to:
- keep the same behavior as the one currently described into the Draft
for reaching consistency (R=1, U=0 allows that),
- implement the proposed mechanism for leaf nodes deployment (R=0, U=1
allows this case).

For instance, in rpl-10, the text from 7.3 might be changed like this
for managing the Reset of the Trickle Timer:
----------------------
   o  When a node receives a multicast DIS message *with the R flag
set and* without a Solicited
      Information option.

   o  When a node receives a multicast DIS *with the R flag set and*
with a Solicited Information
      option and the node matches all of the predicates in the Solicited
      Information option.
-----------------------

A sentence like the following is also required:
-----------------------
When a node receives a multicast DIS *with the R flag clear*, it MUST
NOT reset its Trickle Timer.
-----------------------

Also, a sentence might be added for managing the transmission mode of
answered DIOs:
----------------------
When a node receives a DIS (unicast or multicast) with the U flag set,
it MUST unicast a DIO to the sender in response.
----------------------

Clearly, some use case have to be described for specifying when to set
or not R and U flags:
- default operational mode for network consistency: R=1 and U=0,
- specific leaf node deployment: R=0 and U=1.

As a conclusion, the goal of the proposed R and U flags is not to
modify the well-known behavior that allows the network reaching
consistency but to extend the possible usage of DIS/DIOs to
energy-efficient leaf node deployment.

> Phil

For answering directly your question, I do not expect that RPL
includes the proposed mechanism.
It might be described in a separate document if the WG shows some
interest for it.

However, adding these two flags to the Draft is one solution for
allowing this mechanism to be implemented.

Is my concern clearer now?

In these conditions, does the integration of R and U flags seem acceptable now?

Thanks,

Nicolas.

---

From: Philip Levis <[email-masked]>
Date: Thu, 15 Jul 2010 15:39:05 -0700

> for managing the Reset of the Trickle Timer:

Why doesn't the existing mechanism (unicast request obtains a unicast response without resetting the timer) solve this problem? 

The mechanism you describe has a serious flaw; I brought this up in prior responses but you haven't explained why it isn't a problem. In particular:

"When a node receives a DIS (unicast or multicast) with the U flag set, it MUST unicast a DIO to the sender in response."

If a node sends a multicast DIS with the U flag, then it will cause all neighbors to send a unicast DIO in response. Because the responses are unicast, they will not suppress one another. This traffic pattern (a flood response) is a terrible problem in low-power wireless, in part due to the hidden terminal problem. Nodes will be possibly spending lots of energy to transmit packets that just collide. I think it is a bad idea to assume that an LLN node has an excellent enough understanding of the network in order to carefully expand DIS predicates until a small number of nodes respond.

It's useful to note that if a message does not reset the timer, handling suppression in a safe way becomes an open problem. That is, I do not know of any existing solutions that have been evaluated in real networks. E.g., let's say we're close to the end of an interval. If a message does not reset the timer, then if there have already been enough transmissions in the interval a node won't respond. Responding without suppression can lead to a flood response. There might be ways out of this (e.g., resetting the counter), but I'd consider such approaches highly highly experimental.

It sounds like you want to be able to send a multicast message and get an immediate, single response from every neighbor? Your original mail said:

"Just to re-inforce this calculation, it has been our experience that
node insertion into a dense low-power network, if done wrong, is a
significant energy drain."

So I guess I have 3 questions:

 1) Why does the unicast/multicast distinction not solve the problem?
 2) If the issue is discovery on inserting a new node, can you explain how unicast responses from many neighbors (or an iterative DIS with options search) is more efficient than suppression over a logarithmic number of intervals?
 3) If the issue is inserting many new nodes at the same time and many triggering resets, why doesn't a simple DIO timeout (e.g., 5 minutes) before issuing a DIS work?

I feel like there's some very specific use case you're trying to describe and I just don't understand it yet. Sorry to be slow.

Phil

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 16 Jul 2010 16:02:43 +0200

Hi:

I think that there are cases where the node could suggest things (hint) but it appears to me that the routers have a better history than the node so even if we have bits, they can only be information/ suggestion. For instance, a router that has history to support a very sparse network could answer rapidly and unicast. In a dense configuration it should let trickle play out. The host cannot know that sort of thing. ND is similar, RAs can be sent unicast or multicast. 

But a host can know that it is a leaf that does not impact the routing, that it is discovering the environment etc... The question at some point was whether we needed to play out the exponential back off or remember to set back the trickle timer to its original value because the trigger was not an inconsistency. I thought that the optimization was worth it but that did not reach consensus.

Pascal

> From: Nicolas DEJEAN [mailto:[email-masked]]
> Sent: Tuesday, July 13, 2010 4:27 PM
> To: Pascal Thubert (pthubert)
> Cc: Philip Levis; Tim Winter; [email-masked]

---

From: Nicolas DEJEAN <[email-masked]>
Date: Fri, 16 Jul 2010 18:06:33 +0200

Hello Phil,

> Why doesn't the existing mechanism (unicast request obtains a unicast response without resetting the timer) solve this problem?

See answer to your question 1 below.

> If a node sends a multicast DIS with the U flag, then it will cause all neighbors to send a unicast DIO in response. Because the responses are unicast, they will not suppress one another. This traf…

We indeed don't want unicast responses to suppress one another. The
"flood" will be kept under control by the DIS options. It is our
experience in smart metering network that the LLN node (via the
technician impatiently standing in front of it during installation)
does have enough understanding of the network to craft DIS predicates,
and does not want to wait one minute more than absolutely necessary.
Note that the Trickle max period is anticipated to be several hours in
water/gas smart metering networks.

>  1) Why does the unicast/multicast distinction not solve the problem?

When inserting a new node in a dense environment, without pre-existing
information about the qualifications of routers around, running
through their list one by one is an expensive proposition.

>  2) If the issue is discovery on inserting a new node, can you explain how unicast responses from many neighbors (or an iterative DIS with options search) is more efficient than suppression over a…

With our MAC layer of interest, unicast responses will not induce
overhearing at other receivers in the neighborhood, while multicast
will. With the DIS search options, there won't be that many neighbors
to respond, and we will quickly get responses from all nodes we are
interested in, not at some random later time depending on suppression.

>  3) If the issue is inserting many new nodes at the same time and many triggering resets, why doesn't a simple DIO timeout (e.g., 5 minutes) before issuing a DIS work?

See explanation above about technician not having to wait one minute
more than strictly necessary.

> I feel like there's some very specific use case you're trying to describe and I just don't understand it yet. Sorry to be slow.

Please excuse my french ;-)

> Phil

Cheers,

Nicolas.

---

From: Philip Levis <[email-masked]>
Date: Tue, 20 Jul 2010 09:33:29 -0700

>> I feel like there's some very specific use case you're trying to describe and I just don't understand it yet. Sorry to be slow.

This seems like a really narrow use case, which is a mix of application requirements and a particular way you are trying to use DIO transmissions. Correct me if I'm wrong, but I think the requirement is:

R1) A technician needs to be able to deploy a node in a dense network and have it come up very quickly with little energy spent 

The proposed solution assumes:

A1) The network is engineered in such a way, combined with node knowledge of the network, that nodes can issue iteratively broader DIS queries to optimize the responses;
A2) The MAC layer is such that broadcast operations are much more expensive than unicast
A3) The MAC layer is such that broadcast operations are expensive with respect to receive energy
A4) On a multicast request, the MAC layer is such that a response implosion is not a problem

Doesn't this seem like a very narrow set of assumptions to use as a basis for including a new mechanism?

Can you walk me through the math for the energy cost? Here's how I see it, how am I wrong:

Let us suppose an Imin of 1 sec and a max doublings of 14 (max interval length is then 4.5 hours). Assuming that the network starts at Imax, over the 4.5 hours after a multicast DIS, nodes will hear 14k rather than k messages. Is the concern the receiver energy cost or transmitter energy cost? What sort of low-power MAC is used? If it is a strobing MAC, there shouldn't be a large receive energy cost; if it is a preamble MAC, then there can be. So is there an assumption of a preamble MAC?

Please note with respect to R1, Trickle has been demonstrated to accomplish this goal (please see the CTP paper). The one caveat is that when the node first comes up, it might start with a "good enough" route. Then, over time, as it learns about more of its neighbors it improves the route. Is this an unacceptable problem in your domain? 

Phil