Subject: Re: [Roll] P2P: "distance" and the "good enough" criteria

From: Mukul Goyal <[email-masked]>
Date: Thu, 24 Jun 2010 02:47:11 -0500 (CDT)

JP

>Not quite ;-) If you receive two DIOs with M1 and M2, the node will
>likely select its parent according to the one with the lowest rank.
>Even if you change the OF to make the metric selection more important,
>the rank rule will make you not optimized against M2 as you pointed
>out, agree ?

Yes, but please keep in mind that the objective is to discover "good enough" routes and not the optimal routes. If such good enough routes could still be discovered inspite of using simpler (or fewer or different) metrics (and a simple OF) for temporary DAG creation, it should be OK. The advantage of this flexibility is that a constrained device just needs to know one OF and will still be able to participate in P2P route discovery (because temporary DAG formation will be based on that OF). One can always use the same metrics for both good enough criteia and temporary DAG formation.

I guess one has to view the temporary DAG structure as a way to constrain the topology (possibly in an arbitrary fashion) and discover "good enough" routes within this constrained topology. 

Also, please remember that RPL specifies DAG rank to be the indicator of a router's position in the DAG and allows the DAG rank to be different than the routing cost to reach the root.

Thanks
Mukul

----- Original Message -----
From: "JP Vasseur" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "roll" <[email-masked]>
Sent: Thursday, June 24, 2010 1:39:13 AM
Subject: Re: [Roll] P2P: "distance" and the "good enough" criteria

Hi Mukul,

On Jun 24, 2010, at 8:16 AM, Mukul Goyal wrote:

> Hi JP
>
>> The main concern of using different metric though is that the metric
>> used to form the temporary DAG will determine the discovered path
>> cost itself. In other words, if you use metric M1 for the temporary
>> DAG (route discovery), the discovered route will be optimized
>> according to
>> THAT metric M1, not a potentially other metric M2 that you would like
>> to use to discover the "best" router (according to M2).
>
> No, this is not true. The DAG rank will be based on M1 but whenever
> a router in the DAG receives a better (or newer, depending on the
> implementation) value for M2, it will reset the trickle timer and
> advertize this better M2 value in its DIO. It is true that the
> router will ignore better M2 values received from lower ranked
> neighbors, but all better M2 values received from higher ranked
> neighbors would still be advertized further. Do you agree??
>

Not quite ;-) If you receive two DIOs with M1 and M2, the node will
likely select its parent according to the one with the lowest rank.
Even if you change the OF to make the metric selection more important,
the rank rule will make you not optimized against M2 as you pointed
out, agree ?

Cheers.

JP.

> Thanks
> Mukul
>
>
>
>>> So, a node, that joins the temporary DAG at a rank x, ignores DIOs
>>> received from nodes with lower (higher in numerical value) rank.
>>> This does have the effect that if a DIO from a lower ranked node
>>> carries information about a really good route (in terms of metrics
>>> used for route selection), it will be ignored as well. But, this is
>>> the price one has to pay for using different metrics for temporary
>>> DAG formation than for route selection. When a node receives a DIO
>>> from a higher ranked neighbor, it updates the metrics used for route
>>> discovery and possibly advertises these values in its own DIO.
>>>

---

From: Philip Levis <[email-masked]>
Date: Fri, 25 Jun 2010 17:54:58 -0400

> Yes, but please keep in mind that the objective is to discover "good enough" routes and not the optimal routes. If such good enough routes could still be discovered inspite of using simpler (or few…

Can you be a little clearer on what "good enough" is? Hysteresis and estimation inaccuracy means that wireless meshes rarely use the "optimal" route: doing so would lead to high unstable topologies. Maybe reversing the question would be helpful: what kind of route would not be "good enough?" How do we evaluate whether the protocol meets this requirement?

Phil

---

From: Mukul Goyal <[email-masked]>
Date: Fri, 25 Jun 2010 22:09:51 -0500 (CDT)

>Can you be a little clearer on what "good enough" is? Hysteresis and
>estimation inaccuracy means that wireless meshes rarely use the
>"optimal" route: doing so would lead to high unstable topologies.

"Good enough" is what an origin router wants it to be. Here are some examples:

1. An origin router that expects the target router to be less than 5 hops away may specify "hop-count <= 5" as the good enough criteria. 

2. An origin router that measures the total ETX of its along-DAG route to the target router to be 20 may specify "ETX <= x*20", where x is a fraction that origin router decides, as the good enough criteria.   

> Maybe
>reversing the question would be helpful: what kind of route would not be
>"good enough?"

Again, the origin router would know what "good enough" is. It is origin router's prerogative to decide if a route is "good enough" or not and what is the "good enough" criteria.

> How do we evaluate whether the protocol meets this
>requirement?

The protocol offers a way to discover "good enough" routes. Obviously, the protocol can not guarantee that such routes would be discovered if they exist.

Mukul
----- Original Message -----
From: "Philip Levis" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "JP Vasseur" <[email-masked]>, "roll" <[email-masked]>
Sent: Friday, June 25, 2010 4:54:58 PM
Subject: Re: [Roll] P2P: "distance" and the "good enough" criteria

On Jun 24, 2010, at 3:47 AM, Mukul Goyal wrote:

>> Even if you change the OF to make the metric selection more
>> important, the rank rule will make you not optimized against M2 as
>> you pointed
>> out, agree ?
>
> Yes, but please keep in mind that the objective is to discover "good
> enough" routes and not the optimal routes. If such good enough routes
> could still be discovered inspite of using simpler (or fewer or
> different) metrics (and a simple OF) for temporary DAG creation, it
> should be OK. The advantage of this flexibility is that a constrained
> device just needs to know one OF and will still be able to participate
> in P2P route discovery (because temporary DAG formation will be based
> on that OF). One can always use the same metrics for both good enough
> criteia and temporary DAG formation.

Phil

---

From: Philip Levis <[email-masked]>
Date: Mon, 28 Jun 2010 09:29:55 -0700

> 2. An origin router that measures the total ETX of its along-DAG route to the target router to be 20 may specify "ETX <= x*20", where x is a fraction that origin router decides, as the good enough…

This makes sense. Clearly some kind of intelligent route discovery is going to do better than simple scoped flooding. So basically a node requests a route, the LLN tries to discover some good ones, then that node decides if they are good enough? The major question then is how an intermediate node decides which routes to forward to the discovering node.

Phil