Subject: [Roll] DIO DAGRank field

From: Philip Levis <[email-masked]>
Date: Fri, 18 Dec 2009 12:57:49 -0800

Currently, the DIO DAGRank field is 8 bits. Is this sufficient?

I am concerned with the compression of metrics to Rank. Some metrics  
one can expect to have a reasonably small range (ETX/ETT). Others,  
such as latency, can have a very large range (latency). I am a bit  
worried whether an 8-bit Rank will be sufficient for these kinds of  
metrics. Looking at OF0, for example, a given link can lead to a Rank  
increase of up to 16: an 8-bit value means that there can be a 16-hop  
limit. Since OF0 does not define how a link cost of 16 is determined,  
it could be that an implementation leans towards high values and so  
the network cannot scale out.

It seems to me that a 16-bit value would be much safer. We don't want  
to end up painting ourselves into the same corner that RIP did.

Thoughts?

Phil

---

From: JP Vasseur <[email-masked]>
Date: Sat, 19 Dec 2009 10:13:25 +0100

On Dec 18, 2009, at 9:57 PM, Philip Levis wrote:

> metrics. Looking at OF0, for example, a given link can lead to a  
> Rank increase of up to 16: an 8-bit value means that there can be a  
> 16-hop limit. Since OF0 does not define how a link cost of 16 is  
> determined, it could be that an implementation leans towards high  
> values and so the network cannot scale out.
>
> It seems to me that a 16-bit value would be much safer. We don't  
> want to end up painting ourselves into the same corner that RIP did.
>
> Thoughts?

Right, on the other hand if there is a need for a more sophisticated  
metric, we use the metrics defined in the metric-ID. I have the  
feeling that OF0 is to be used in fairly simple network where the  
metric and the rank are tightly coupled but in other networks other  
metrics will be used. Since you refer to latency there is a latency  
metric that has been defined. Let's see what others think.

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

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 21 Dec 2009 08:34:31 -0500

> From: JP Vasseur <[email-masked]>
> Date: Sat, 19 Dec 2009 10:13:25 +0100
>> 
> > metrics. [...]

Yes, there is a latency metric with a 32-bit floating point
latency in milliseconds.  It seems silly to have that much
precision and range in the metric and then use an 8-bit
rank.  For a DAG based on latency you need to pick the
latency that corresponds to a rank increase of one.  Here
are some possibilities:

 latency per rank increment  10ms      30ms     100ms
 maximum path latency       2.5 sec  7.5 sec   25 sec

For a very low power 802.15.4 network, a maximum path
latency of 25 seconds seems none too high.  At the same
time, a pair of line-powered 802.15.4 neighbors should have
a latency of 30ms or less.  All that range in the metric
doesn't help because it gets lost in the translation to
the rank.
                              -Richard Kelsey

---

From: JP Vasseur <[email-masked]>
Date: Mon, 21 Dec 2009 14:41:10 +0100

On Dec 21, 2009, at 2:34 PM, Richard Kelsey wrote:

> latency in milliseconds.

We can certainly change the way we encode this metric and others.

> It seems silly to have that much
> rank.

They may not be correlated at all, the rank only being used for "loop  
management"
and the latency for path computation.

> For a DAG based on latency you need to pick the
> latency that corresponds to a rank increase of one.

Why ?

> Here

But it does not have to be translated to the rank at all ?

Cheers.

JP.

---

From: Philip Levis <[email-masked]>
Date: Mon, 21 Dec 2009 08:46:02 -0800

On Dec 21, 2009, at 5:41 AM, JP Vasseur wrote:

> They may not be correlated at all, the rank only being used for "loop management"

JP,

I don't think we can have it both ways. Rank should either be a topological property or a metric property. That is, I think it's problematic to overload Rank so that it could either be a coarse distillation of a route metric *or* a hopcount. If it's the former, it needs 16 bits; if it's the latter, 8 is fine. But to keep it at 8 and say that it could be either means that metrics with large ranges must use it as a hopcount. This seems like an arbitrary decision.

For example, OF0 equates Rank with link (and route) quality, such that nodes choose the best route by choosing the lowest Rank next hop. This kind of conflation is at the core of the problem, I think. Shouldn't this be a metric container decision?

Phil

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 21 Dec 2009 23:00:34 -0500

> Date: Mon, 21 Dec 2009 14:41:10 +0100
> 
> They may not be correlated at all, the rank only being
> used for "loop management" and the latency for path
> computation.

This has been gone over in detail before on this list.  The
rank trumps the metric.  It may only be for "loop
management", but if the rank makes a neighbor ineligble as a
parent, it doesn't matter what the neighbor's metric is,
the neighbor cannot be a parent.

> > latency that corresponds to a rank increase of one.

To minimize the discrepancy between the metric and the rank.
The set of possible parents is based on rank, not metric.
If the metric and rank are not in sync, then the best
parents according to the metric may easily not be in the set
of possible parents allowed by the rank.

> But it does not have to be translated to the rank at all ?

If the latency is not translated into the rank then
the DAG will not optimize latency.  RPL optimizes rank
first and metric second.
                             -Richard Kelsey

---

From: Philip Levis <[email-masked]>
Date: Tue, 29 Dec 2009 12:06:44 -0800

> the DAG will not optimize latency.  RPL optimizes rank

Richard --  I agree with your analysis of Rank. Right now it seems to be a bit vague, and operating under the assumption that we'll figure it out later. It is a mix of a logical property for loop avoidance and a route quality property. It should be clearly one or the other. At the very least, if we follow the current hybrid approach, there need to be constraints on how much Rank can increment on each hop, and this value needs to be considered in the field width. For example, with OF0 it's a bit strange that two neighbors, both of whom have a hopcount of 2, can have Ranks of 2 and 32. I'm also a bit worried as to how Rank will translate from highly variable metrics such as latency, or decreasing metrics, such as a throughput.

These are the kinds of things we should be discussing and resolving with respect to the draft. Before we start adding additional mechanisms for optimization, we need to make sure the existing ones are sound and effective.

It seems to me that RPL would be much simpler if there were a strong division between Rank and metric, with the former being used for loop avoidance and detection and the latter being used for route optimization. It would, at the very least, simplify route selection and OF definition.

Phil