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

From: Mukul Goyal <[email-masked]>
Date: Sun, 20 Jun 2010 01:19:42 -0500 (CDT)

Hi all

I would like to start a discussion about the following important features of the P2P route discovery mechanism: 
1)	a limit on the “distance” the discovery messages may travel
2)	a “good enough” criteria for route selection.

The discovery message propagation takes place via the creation of a temporary DAG. The reason we chose to propagate the discovery message as an option inside the DIO was strong controls available for DIO propagation: 
1)rank based poisoning of DIOs traveling inwards and 
2)trickle controlled generation. 
We added a further control: a maximum limit on the rank. A node MUST not join this DAG if its rank in the DAG will exceed this limit. This maximum rank value limits the “distance” that a discovery message may travel.
 
Now, having made the decision regarding using DIOs as discovery messages, the next question is how does a node select its rank in this temporary DAG and what metrics are to be used for the creation of this DAG?

One answer would be: use the same metrics for DAG formation that are to be used for route selection.

The other answer is: Since highly-constrained devices may find it difficult to compute a complex objective function, involving multiple routing metrics, for each received DIO/Discovery message, let us allow the use of simpler/fewer metrics for the creation of the temporary DAG. For example, the objective of route discovery might be to find the routes that have the success rate more than 90% and latency less than 100ms, but the rank calculation in the temporary dag is simply based on minimizing the hop-count. In this example, the route selection criteria/metrics are totally different from the rank calculation metrics. Another example, where the two are related, is using criteria – ETX less than 10 and latency less than 200ms – for route selection and calculate the rank in the temporary DAG based on minimizing ETX alone.

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.
 
Now, as the DIOs reach the target router, it examines the metrics to determine if the routes advertized by these DIOs meet the “good enough” criteria. In the two examples discussed above, the “good enough” criteria are: 
1) success rate more than 90% AND latency less than 100ms; 
2) ETX less than 10 AND latency less than 200ms
respectively.

Since the "good enough" criteria is just a bunch of constraints, I suspect there is no need to specify an OCP inside a Route Discovery Option. (The Route Discovery Option defined in p2p-rpl-01 does include an optional OCP field; I think it should go away).

Thanks
Mukul

---

From: [email-masked]
Date: Mon, 21 Jun 2010 09:06:40 -0500

Mukul,

The P2P mechanism was added specifically
to find 'good enough' low-latency routes.  I don't believe there's
another announced use case.  Hence, I would think the objective function
would be well defined for any P2P route, whether it be minimal hop counts
or ETX or whatever.  Whatever metric we come up with that defines
low-latency routes should be the metric used for P2P routes.

Jerry

From:

Mukul Goyal <[email-masked]>

To:

roll <[email-masked]>

Date:

06/20/2010 01:19 AM

Subject:

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

Hi all

I would like to start a discussion about the following important features
of the P2P route discovery mechanism:

1)
a limit on the “distance” the discovery messages may travel

2)
a “good enough” criteria for route selection.

The discovery message propagation takes place via the creation of a temporary
DAG. The reason we chose to propagate the discovery message as an option
inside the DIO was strong controls available for DIO propagation:

We added a further control: a maximum limit on the rank. A node MUST not
join this DAG if its rank in the DAG will exceed this limit. This maximum
rank value limits the “distance” that a discovery message may travel.

Now, having made the decision regarding using DIOs as discovery messages,
the next question is how does a node select its rank in this temporary
DAG and what metrics are to be used for the creation of this DAG?

One answer would be: use the same metrics for DAG formation that are to
be used for route selection.

The other answer is: Since highly-constrained devices may find it difficult
to compute a complex objective function, involving multiple routing metrics,
for each received DIO/Discovery message, let us allow the use of simpler/fewer
metrics for the creation of the temporary DAG. For example, the objective
of route discovery might be to find the routes that have the success rate
more than 90% and latency less than 100ms, but the rank calculation in
the temporary dag is simply based on minimizing the hop-count. In this
example, the route selection criteria/metrics are totally different from
the rank calculation metrics. Another example, where the two are related,
is using criteria – ETX less than 10 and latency less than 200ms – for
route selection and calculate the rank in the temporary DAG based on minimizing
ETX alone.

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.

Now, as the DIOs reach the target router, it examines the metrics to determine
if the routes advertized by these DIOs meet the “good enough” criteria.
In the two examples discussed above, the “good enough” criteria are:

respectively.

Since the "good enough" criteria is just a bunch of constraints,
I suspect there is no need to specify an OCP inside a Route Discovery Option.
(The Route Discovery Option defined in p2p-rpl-01 does include an optional
OCP field; I think it should go away).

Thanks

Mukul

_______________________________________________

Roll mailing list

[email-masked]

https://www.ietf.org/mailman/listinfo/roll

---

From: Mukul Goyal <[email-masked]>
Date: Mon, 21 Jun 2010 12:13:13 -0500 (CDT)

Hi Jerry

I guess objective functiions other than "minimize a metric" can also be used. 

My main question was do we need an OF at all since the "good enough" criteria is a bunch of constraints. The OF can help the target router choose the best routes among the ones that meet the good enough criteria. So, I guess OF will be useful if the target router intends to wait for a while before sending the Discovery Reply back. During this duration, the target router can apply the OF to select the best routes among the ones that met the good enough criteria. If the target router does not wait, i.e. it immediately accepts a route if it meets the good enough criteria, then OF seems redundant information. 

So, I guess, it makes sense to keep OF in the Route Discovery Option to help target routers that want to wait a while before sending Discovery Reply back.

Thanks
Mukul

----- Original Message -----
From: "Jerald P Martocci" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "roll" <[email-masked]>, [email-masked]
Sent: Monday, June 21, 2010 9:06:40 AM
Subject: Re: [Roll] P2P: "distance" and the "good enough" criteria

Mukul,

The P2P mechanism was added specifically to find 'good enough'
low-latency routes.  I don't believe there's another announced use case.
 Hence, I would think the objective function would be well defined for
any P2P route, whether it be minimal hop counts or ETX or whatever.
 Whatever metric we come up with that defines low-latency routes should
be the metric used for P2P routes.

Jerry

From: Mukul Goyal <[email-masked]>
To: roll <[email-masked]>
Date: 06/20/2010 01:19 AM
Subject: [Roll] P2P: "distance" and the "good enough" criteria

Hi all

I would like to start a discussion about the following important
features of the P2P route discovery mechanism:
1)                 a limit on the “distance” the discovery messages may
travel 2)                 a “good enough” criteria for route selection.

The discovery message propagation takes place via the creation of a
temporary DAG. The reason we chose to propagate the discovery message as
an option inside the DIO was strong controls available for DIO
propagation: 1)rank based poisoning of DIOs traveling inwards and
2)trickle controlled generation.
We added a further control: a maximum limit on the rank. A node MUST not
join this DAG if its rank in the DAG will exceed this limit. This
maximum rank value limits the “distance” that a discovery message may
travel.

Now, having made the decision regarding using DIOs as discovery
messages, the next question is how does a node select its rank in this
temporary DAG and what metrics are to be used for the creation of this
DAG?

The other answer is: Since highly-constrained devices may find it
difficult to compute a complex objective function, involving multiple
routing metrics, for each received DIO/Discovery message, let us allow
the use of simpler/fewer metrics for the creation of the temporary DAG.
For example, the objective of route discovery might be to find the
routes that have the success rate more than 90% and latency less than
100ms, but the rank calculation in the temporary dag is simply based on
minimizing the hop-count. In this example, the route selection
criteria/metrics are totally different from the rank calculation
metrics. Another example, where the two are related, is using criteria –
ETX less than 10 and latency less than 200ms – for route selection and
calculate the rank in the temporary DAG based on minimizing ETX alone.

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.

Now, as the DIOs reach the target router, it examines the metrics to
determine if the routes advertized by these DIOs meet the “good enough”
criteria. In the two examples discussed above, the “good enough”
criteria are:
1) success rate more than 90% AND latency less than 100ms;
2) ETX less than 10 AND latency less than 200ms
respectively.

Since the "good enough" criteria is just a bunch of constraints, I
suspect there is no need to specify an OCP inside a Route Discovery
Option. (The Route Discovery Option defined in p2p-rpl-01 does include
an optional OCP field; I think it should go away).

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

---

From: JP Vasseur <[email-masked]>
Date: Wed, 23 Jun 2010 20:19:11 +0200

Hi Mukul,

On Jun 20, 2010, at 8:19 AM, Mukul Goyal wrote:

> temporary DAG. The reason we chose to propagate the discovery  
> message as an option inside the DIO was strong controls available  
> for DIO propagation:
> We added a further control: a maximum limit on the rank. A node MUST  
> not join this DAG if its rank in the DAG will exceed this limit.  
> This maximum rank value limits the “distance” that a discovery  
> message may travel.
>
> messages, the next question is how does a node select its rank in  
> this temporary DAG and what metrics are to be used for the creation  
> of this DAG?
>
> difficult to compute a complex objective function, involving  
> multiple routing metrics, for each received DIO/Discovery message,  
> let us allow the use of simpler/fewer metrics for the creation of  
> the temporary DAG. For example, the objective of route discovery  
> might be to find the routes that have the success rate more than 90%  
> and latency less than 100ms, but the rank calculation in the  
> temporary dag is simply based on minimizing the hop-count. In this  
> example, the route selection criteria/metrics are totally different  
> from the rank calculation metrics. Another example, where the two  
> are related, is using criteria – ETX less than 10 and latency less  
> than 200ms – for route selection and calculate the rank in the  
> temporary DAG based on minimizing ETX alone.
>

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).

> 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.
>
> determine if the routes advertized by these DIOs meet the “good  
> enough” criteria. In the two examples discussed above, the “good  
> enough” criteria are:
> Option. (The Route Discovery Option defined in p2p-rpl-01 does  
> include an optional OCP field; I think it should go away).
>
>
> Thanks
> Mukul

---

From: Mukul Goyal <[email-masked]>
Date: Thu, 24 Jun 2010 01:16:22 -0500 (CDT)

Hi JP

>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??

Thanks
Mukul

---

From: JP Vasseur <[email-masked]>
Date: Thu, 24 Jun 2010 08:39:13 +0200

Hi Mukul,

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

> 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.