Subject: Re: [Roll] Fwd: New Version Notification for draft-dt-roll-p2p-rpl-00

From: Mukul Goyal <[email-masked]>
Date: Tue, 18 May 2010 01:46:16 -0500 (CDT)

Philip

[Philip]
I agree with your comment on 2 -- nodes in a P2P route may need to be neither parents nor children. My concern is a little more subtle.  

One of the dangers of on-demand mechanisms is that routes are established quickly, but detecting good links requires time. Node B receiving a discovery message from node A does not imply that A <-> B can be included in a workable route. If node B does not have a good estimate of AB, it should not forward a discovery message after hearing it from  A. Something as simple as saying that a node MUST NOT forward a discovery message if 

  1) the transmitter is outside its neighbor set, or 
  2) the link to/from the transmitter has poor properties (realize this needs to be more precise). 

might be sufficient. 

This is one of those cases where doing the simple and easy thing (just forward!) has terrible implications. I realize that the current statement of intent calls for forwarded discovery messages to include metrics/cost/Rank/etc. What's critical is that receiving a discovery packet be insufficient for determining this value, because in LLNs it is. 

Does that make sense? 

[Mukul]
I agree that a node should forward a Discovery message only if it has a good estimate of the "link cost in the right direction". I guess this can be made explicit in the draft. But, the routing metric may simply be hop-count, in which case the receipt of the Discovery message is a reasonable proof of the existence of the "hop". So, I won't say that receiving a discovery packet is always insufficient to determine the "link cost" value. It really depends on the definition of the routing cost.

Thanks
Mukul

---

From: "Anders Brandt" <[email-masked]>
Date: Tue, 18 May 2010 09:32:15 +0200

[Anders] comment inline ...

Cheers,
  Anders

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of Mukul Goyal
> Sent: Tuesday, May 18, 2010 08:46
> To: Philip Levis
> Cc: roll; Emmanuel Baccelli
> Subject: Re: [Roll] Fwd: New Version Notification 
> fordraft-dt-roll-p2p-rpl-00
> 
> Philip
> 
> [Philip]
> I agree with your comment on 2 -- nodes in a P2P route may 
> need to be neither parents nor children. My concern is a 
> little more subtle.  
> 
> One of the dangers of on-demand mechanisms is that routes are 
> established quickly, but detecting good links requires time. 
> Node B receiving a discovery message from node A does not 
> imply that A <-> B can be included in a workable route. If 
> node B does not have a good estimate of AB, it should not 
> forward a discovery message after hearing it from  A. 
> Something as simple as saying that a node MUST NOT forward a 
> discovery message if 
> 
> 
> This is one of those cases where doing the simple and easy 
> thing (just forward!) has terrible implications. I realize 
> that the current statement of intent calls for forwarded 
> discovery messages to include metrics/cost/Rank/etc. What's 
> critical is that receiving a discovery packet be insufficient 
> for determining this value, because in LLNs it is. 
> 
> 
> Does that make sense? 
> 
> [Mukul]
> I agree that a node should forward a Discovery message only 
> if it has a good estimate of the "link cost in the right 
> direction". I guess this can be made explicit in the draft. 
> But, the routing metric may simply be hop-count, in which 
> case the receipt of the Discovery message is a reasonable 
> proof of the existence of the "hop". So, I won't say that 
> receiving a discovery packet is always insufficient to 
> determine the "link cost" value. It really depends on the 
> definition of the routing cost.

[Anders] I understand your concern and if you have resources
in a node for doing more intelligent forwarding decisions, this
is wonderful.
For the most constrained nodes, however, I love the simplicity
of Trickle where you forward (randomized schedule) as long as
you have picked up less than n copies of the discovery message
from you direct range neighbors.
We must ensure that the most constrained nodes can do something
like this. For sure, such nodes cannot hold link properties for
all neighbors in a dense network.

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

---

From: JP Vasseur <[email-masked]>
Date: Tue, 18 May 2010 11:24:29 +0200

Hi Anders,

Comments (still technical, co-chair hat off again)

>> definition of the routing cost.

Still the issue is that you may not know that cost, especially if the  
A-B link does not
belong to the DAG. The wording proposed by Phil makes sense to me.

> from you direct range neighbors.

But that requires to be cautious too since that could eliminate some  
"good" paths too, and
in particular the ones that are better than the DODAG path.

---

From: Philip Levis <[email-masked]>
Date: Tue, 18 May 2010 08:36:46 -0700

On May 18, 2010, at 2:24 AM, JP Vasseur wrote:
> But that requires to be cautious too since that could eliminate some "good" paths too, and

Anders -- are you suggesting using Trickle as the route discovery mechanism, or as the data delivery mechanism?

Phil

---

From: Philip Levis <[email-masked]>
Date: Tue, 18 May 2010 08:39:18 -0700

> I agree that a node should forward a Discovery message only if it has a good estimate of the "link cost in the right direction". I guess this can be made explicit in the draft. But, the routing met…

There is extensive empirical evidence that using hopcount is a terrible idea. If the routing metric is hop-count then the LLN will not work well; you are better off routing up and down the DAG than dynamically discovering routes. The protocol can't have it both ways: argue that it quickly detects "good enough" routes with low stretch yet also needs to support detecting terrible routes. 

Hopcount as a metric is a myth that entered our imagination due to terrible wireless simulations. It is a simplification that does not work. Let's move past the 1990s and stop considering hopcount as something that RPL needs to accommodate. Remember, we're talking about LLNs: Lossy and Low Power Networks.

Phil

---

From: Mukul Goyal <[email-masked]>
Date: Tue, 18 May 2010 11:45:52 -0500 (CDT)

Hi Philip

Highly-constrained nodes, that can not afford to maintain per-neighbor state, may have no choice but to use hop-count as the metric. In any case, the reactive route discovery mechanism should not care what the routing metrics are. Note that we chose not to go deep into metrics/"routing cost" discussion in the p2p draft, simply because different people have very strong and very different opinions on what is right and what is wrong. Would you be OK with adding the following text in the description of route discovery mechanism:

A node should not forward a Discovery message further if it does not have the relevant link-level cost estimates.

Note that we can not really refer to the "neighbor table" as you had suggested earlier.

Thanks
Mukul
  
----- Original Message -----
From: "Philip Levis" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "roll" <[email-masked]>, "Emmanuel Baccelli" <[email-masked]>
Sent: Tuesday, May 18, 2010 10:39:18 AM GMT -06:00 US/Canada Central
Subject: Re: [Roll] Fwd: New Version Notification for draft-dt-roll-p2p-rpl-00

Phil

---

From: JP Vasseur <[email-masked]>
Date: Tue, 18 May 2010 18:51:57 +0200

On May 18, 2010, at 6:45 PM, Mukul Goyal wrote:

> Hi Philip
>
> Highly-constrained nodes, that can not afford to maintain per- 
> neighbor state, may have no choice but to use hop-count as the  
> metric. In any case, the reactive route discovery mechanism should  
> not care what the routing metrics are. Note that we chose not to go  
> deep into metrics/"routing cost" discussion in the p2p draft,

I would really suggest you to refer to the metric-ID and make the P2P  
solution generic enough to choose the metric of choice.

> simply because different people have very strong and very different  
> opinions on what is right and what is wrong. Would you be OK with  
> adding the following text in the description of route discovery  
> mechanism:
>
> A node should not forward a Discovery message further if it does not  
> have the relevant link-level cost estimates.
>
> Cc: "roll" <[email-masked]>, "Emmanuel Baccelli" <[email-masked] 
> >
>> I agree that a node should forward a Discovery message only if it  
>> has a good estimate of the "link cost in the right direction". I  
>> guess this can be made explicit in the draft. But, the routing  
>> metric may simply be hop-count, in which case the receipt of the  
>> Discovery message is a reasonable proof of the existence of the  
>> "hop". So, I won't say that receiving a discovery packet is always  
>> insufficient to determine the "link cost" value. It really depends  
>> on the definition of the routing cost.
>
> There is extensive empirical evidence that using hopcount is a  
> terrible idea. If the routing metric is hop-count then the LLN will  
> not work well; you are better off routing up and down the DAG than  
> dynamically discovering routes. The protocol can't have it both  
> ways: argue that it quickly detects "good enough" routes with low  
> stretch yet also needs to support detecting terrible routes.
>
> Hopcount as a metric is a myth that entered our imagination due to  
> terrible wireless simulations. It is a simplification that does not  
> work. Let's move past the 1990s and stop considering hopcount as  
> something that RPL needs to accommodate. Remember, we're talking  
> about LLNs: Lossy and Low Power Networks.
>
> Phil

---

From: JP Vasseur <[email-masked]>
Date: Tue, 18 May 2010 18:54:06 +0200

---

From: Mukul Goyal <[email-masked]>
Date: Tue, 18 May 2010 12:12:10 -0500 (CDT)

Hi JP,

> deep into metrics/"routing cost" discussion in the p2p draft,

[JP]
I would really suggest you to refer to the metric-ID and "make the P2P  
solution generic enough to choose the metric of choice".

[Mukul]
This is exactly the intent. I will add reference to the metrics ID.

Thanks
Mukul

---

From: Philip Levis <[email-masked]>
Date: Tue, 18 May 2010 10:15:35 -0700

On May 18, 2010, at 9:45 AM, Mukul Goyal wrote:

> Note that we chose not to go deep into metrics/"routing cost" discussion in the p2p draft, simply because different people have very strong and very different opinions on what is right and what is wrong. 

I'm sorry; I need to argue this point. This isn't a question of opinion. It's a question of overwhelming scientific evidence and deployment experiences from real networks. Here are two simple published studies[1,2].

Does anyone have a positive, successful, deployment example of hopcount-based routing which does not filter usable "hopcount" links based on link estimates?

That being said,

> A node should not forward a Discovery message further if it does not have the relevant link-level cost estimates.

I think that is this is changed to MUST NOT, then it could be OK. Or how about

"A node MUST NOT forward a Discovery message from a node for which it does not have relevant link-level metric information."

> Note that we can not really refer to the "neighbor table" as you had suggested earlier.

Why?

Phil

[1] Deepak Ganesan et al. "Complex Behavior at Scale: An Experimental Study of Low-Power Wireless Sensor Networks." 
[2] Douglas S. J. De Couto et al. "A high-throughput path metric for multi-hop wireless routing."

---

From: "Anders Brandt" <[email-masked]>
Date: Wed, 19 May 2010 09:25:55 +0200

hi Phil

> There is extensive empirical evidence that using hopcount is a
terrible idea.

[Anders] 
That may very well be. I suggest we put that terrible idea next to the
extensive evidence that several commercial systems works _GOOD_ENOUGH_
with simple hop-count COMBINED with the ability to find another route if
there is a substantial number of retransmissions on that actual route.
The result is terribly inexpensive chips (< $2) with radio, RAM, CPU and
everything onboard. Consumers want this!

>If the routing metric is hop-count then the LLN will not work well;
> you are better off routing up and down the DAG

[Anders] 
With these small nodes, the only DAG information maintained in
individual nodes is the DODAGID + source routes a few other nodes that
the node is supposed to control in some way. Yes, then there are some
few nodes which can do a "Turn a lot of nodes off". They will have more
RAM + non-volatile memory but we SHOULD NOT put that burden on all nodes
in the network. (sorry for SHOUTING but we should really not ignore the
extensive evidence of the successfull deployment of millions of these
extemely inexpensive chips out there)

> The protocol can't have it both ways: argue that it quickly detects
"good enough" routes with low stretch yet also needs to
> support detecting terrible routes.  

[Anders] 
The nice thing about the P2P ID proposal is that you can specify in the
discovery if you are in a hurry and just want the first route that can
turn on your lamp or if you are on a quest for "good" routes; i.e. can
live with having to wait for a number of discovery responses before you
pick the best - out of your metrics criteria.

Cheers,
  Anders

> Behalf Of Philip Levis
> Sent: Tuesday, May 18, 2010 17:39
> To: Mukul Goyal
> There is extensive empirical evidence that using hopcount is 
> a terrible idea. If the routing metric is hop-count then the 
> LLN will not work well; you are better off routing up and 
> down the DAG than dynamically discovering routes. The 
> protocol can't have it both ways: argue that it quickly 
> detects "good enough" routes with low stretch yet also needs 
> to support detecting terrible routes. 
> 
> Hopcount as a metric is a myth that entered our imagination 
> due to terrible wireless simulations. It is a simplification 
> that does not work. Let's move past the 1990s and stop 
> considering hopcount as something that RPL needs to 
> accommodate. Remember, we're talking about LLNs: Lossy and 
> Low Power Networks.
> 
> Phil

---

From: "Anders Brandt" <[email-masked]>
Date: Wed, 19 May 2010 09:31:02 +0200

Hi Phil

________________________________

	From: Philip Levis [mailto:[email-masked]] 
	Sent: Tuesday, May 18, 2010 17:37
	To: JP Vasseur
	Cc: Mukul Goyal; Anders Brandt; roll WG; Emmanuel Baccelli
	Subject: Re: [Roll] Fwd: New Version Notification
fordraft-dt-roll-p2p-rpl-00

	

			[Anders] I understand your concern and if you
have resources

			in a node for doing more intelligent forwarding
decisions, this

			is wonderful.

			For the most constrained nodes, however, I love
the simplicity

			of Trickle where you forward (randomized
schedule) as long as

			you have picked up less than n copies of the
discovery message

		But that requires to be cautious too since that could
eliminate some "good" paths too, and
		in particular the ones that are better than the DODAG
path.

	Anders -- are you suggesting using Trickle as the route
discovery mechanism, or as the data delivery mechanism? 

[Anders]
The data delivery mechanism which can ramdomly schedule the forwarding
of discovery requests and stop doing that if a number
of other nodes already did forward a copy of the same frame in the
direct range neighborhood.
(Admitted - it is a long time ago I actually did read the Trickle paper
but this is how I remember the mechanism (?)    )
 
- Anders

	
	Phil

---

From: Philip Levis <[email-masked]>
Date: Thu, 20 May 2010 10:22:14 -0700

> everything onboard. Consumers want this!

Sure -- "if there is a substantial number of retransmissions" is link validation. But I'm not sure I understand the argument: even though there's a way to avoid NUD and route rediscovery, we shouldn't use it? Or is the concern that the link metric constraint might lead to a disconnected graph?

> extemely inexpensive chips out there)

These nodes do not have neighbor sets? How do they join a DODAG? Does the home and building automation RFC state that a neighbor set of size 1 is a requirement for RPL? Should it?

Phil

---

From: [email-masked]
Date: Thu, 20 May 2010 13:18:40 -0500

Hi Phil,

For Commercial requirements, I can afford
to keep neighbor information.  A reason amount of properties for maybe
10 neighbors.  However, I need to be able to cull the list of neighbors
as needed to fit in my available RAM.  So if there are 30 nodes within
radio range and hence potential neighbors, I may only support a subset
of those nodes as neighbors.  Typically, this will be based on routes
I am already supporting or signal strength.

This is how our current ZigBee product
(AODV) operates.  Since AODV has little control packet overhead this
works well.  I am concerned with the proactive use of DIOs and DAOs
in RPL, I may not be able to support as many neighbors since it may impact
my processing power needed for my primary building application.

Jerry

From:

Philip Levis <[email-masked]>

To:

Anders Brandt <[email-masked]>

Cc:

roll <[email-masked]>, Emmanuel
Baccelli <[email-masked]>

Date:

05/20/2010 12:24 PM

Subject:

Re: [Roll] Fwd: New Version Notification
fordraft-dt-roll-p2p-rpl-00

> everything onboard. Consumers want this!

Sure -- "if there is a substantial number of retransmissions"
is link validation. But I'm not sure I understand the argument: even though
there's a way to avoid NUD and route rediscovery, we shouldn't use it?
Or is the concern that the link metric constraint might lead to a disconnected
graph?

> extemely inexpensive chips out there)

These nodes do not have neighbor sets? How do they join a DODAG? Does the
home and building automation RFC state that a neighbor set of size 1 is
a requirement for RPL? Should it?

Phil

Roll mailing list

[email-masked]

---

From: JP Vasseur <[email-masked]>
Date: Thu, 20 May 2010 21:56:25 +0200

Very useful feed-back from experience.
One quick comment though: I completely understand your motivation for  
a reactive approach
so as to avoid a "simple" device to maintain routing states and make  
it reachable quickly even
if it has not maintained states for some time. On the path quality  
front, the argument becomes
indeed a bit less compelling when the routing metrics itself may not  
really reflect the path quality.
That said, make it metric agnostic, referring to the metric-ID (so  
does RPL) and you will be fine.

Thanks.

JP.

---

From: "Anders Brandt" <[email-masked]>
Date: Tue, 25 May 2010 11:09:50 +0200

Hi Phil 

comments inline

Cheers,
  Anders

> Sent: Thursday, May 20, 2010 19:22
> To: Anders Brandt
> Cc: Mukul Goyal; roll; Emmanuel Baccelli
> > with simple hop-count COMBINED with the ability to find 
> another route 
> > if there is a substantial number of retransmissions on that 
> actual route.
> > The result is terribly inexpensive chips with radio, 
> RAM, CPU 
> > and everything onboard. Consumers want this!
> 
> is link validation. But I'm not sure I understand the 
> argument: even though there's a way to avoid NUD and route 
> rediscovery, we shouldn't use it? Or is the concern that the 
> link metric constraint might lead to a disconnected graph?

I am not sure I understand your question?
(maybe my comment below shows why I do not understand...)

> > few nodes which can do a "Turn a lot of nodes off". They will have 
> > more RAM + non-volatile memory but we SHOULD NOT put that burden on 
> > all nodes in the network. (sorry for SHOUTING but we should 
> really not 
> > ignore the extensive evidence of the successfull deployment of 
> > millions of these extemely inexpensive chips out there)
> 
> These nodes do not have neighbor sets? How do they join a 
> DODAG? Does the home and building automation RFC state that a 
> neighbor set of size 1 is a requirement for RPL? Should it?

As Jerry mentioned in another response to this thread, my nodes may hold
neighbor information on a few (<10) neighbors.
You have suggested that this is some new requirement. I (and Jerry, I
guess)
would claim that this is covered by the "memory constrained devices"
statement.
I agree that the home requirements spec does not explicitly state that a
node cannot hold link quality information for all potential neighbors.
Nevertheless, "memory constrained devices" was intended to convey that
message.

Thus, most constrained nodes may be able to hold a DODAGID, a few source
routes
to a default gateway and some source routes to other nodes in the LLN +
the few
temporary variables required for route discovery/repair.
As Jerry also proposed, my customers prefer to use the RAM for their
real
applications.