Subject: Re: [Roll] parent ordering

From: Mukul Goyal <[email-masked]>
Date: Wed, 23 Sep 2009 22:58:36 -0500 (CDT)

Thomas

Current RPL specs use DAG rank for loop avoidance. My impression is that DT envisioned DAG rank as a hard-to-change (DAG rank is allowed to decrease easily but elaborate procedure required to cause it to increase) node attribute that constrains the topology (a node can have only lower rank neighbors as parents). On the other hand, "path cost" is allowed to change easily. I guess it is easy to create OCP definitions where DAG rank is only loosely related to path costs (e.g. DAG rank based on long-term reliability where as path costs based on near-term reliability).

Having said that, my impression has been that current RPL specs put too much emphasis on loop avoidance. I have said it before that dealing with loops should be an add-on feature. Basic protocol should not worry about loops. Applications should be free to decide whether they want to deal with loops or not and if they want to whether they want to use a loop avoidance strategy or loop detection strategy. So, I think there is no clear need to differentiate between "path cost" and "DAG rank".

Thanks
Mukul

----- Original Message -----
From: "Thomas Watteyne" <[email-masked]>
To: "Mukul Goyal" <[email-masked]>
Cc: "IETF ROLL" <[email-masked]>
Sent: Wednesday, September 23, 2009 7:23:21 PM GMT -06:00 US/Canada Central
Subject: Re: [Roll] parent ordering

Mukul, 

You are absolutely right, I consider "path cost" and "rank" to be pretty close concepts. In fact, is there a clear need to differentiate those? What would be a case (probably an OCP definition) where rank is *not* directly inferred from path cost? 

The way I see things is weighted links interconnecting nodes, each of which then obtaining a rank by adding/multiplying wights on the way to the LBRs so that the closer to the LBR, the lower the rank. With this in mind, in your statement: 
I choose my parents based on the path costs (the costs they advertized in their DIOs + my cost to them) and pick the parent with highest DAG rank (which is solely for loop avoidance purpose; although heavily influenced by routing metrics) as my "most preferred" parent. Then I calculate my own DAG rank by adding a step value (between 1 and 16) to the DAG rank of this most preferred parent I don't see why rank and path cost as different concepts. Is there no way we could work with only path length, in order to obtain a somewhat simpler protocol? 

Thanks 
Thomas 

Mukul Goyal wrote: 

Thomas, 

There is a concept that keeps coming back, which I think needs to be 
discussed:
- in the -01 draft, section 3.3.1.5: "A node must maintain its DAG 
Parent set such that its most preferred parent from the OCP goals also 
has the greatest rank value in the DAG parent set." The statement above conflicts with the other statements in rpl-01.

Here is a quote from section 3.4.1:

" It is important to note that the DAG Rank is not itself a metric,
   although its value is derived from and influenced by the use of
   metrics to select DAG parents and take up a position in the DAG.  In
   other words, routing metrics and OCP (not rank directly) are used to
   determine the DAG structure and consequently the path cost.  The only
   aim of the rank is to inform loop avoidance as explained hereafter."

So, the most preferred parent is simply the parent with highest rank and need not be the parent with best path cost.

I guess DT needs to clarify/correct the text from section 3.3.1.5 you quoted. 

My view of DAG routing is the following. Let's say I am a node. When I 
participate in a network, I discover my neighbors, their rank (which 
they tell me in their DIO's), and the cost of the links connecting us 
(e.g. which L2 tells me, or whatever metric the OCP states). I then 
calculate, for each neighbor, what my potential rank would be if I chose 
him as my preferred parent (e.g. by adding his rank to the cost of the 
link connecting us, or whatever function the OCP states). I end up 
choosing the minimal potential rank, which I announce as my rank in my 
DIOs. It seems that you are mixing DAG rank with path cost. As per my understanding, I choose my parents based on the path costs (the costs they advertized in their DIOs + my cost to them) and pick the parent with highest DAG rank (which is solely for loop avoidance purpose; although heavily influenced by routing metrics) as my "most preferred" parent. Then I calculate my own DAG rank by adding a step value (between 1 and 16) to the DAG rank of this most preferred parent 

  When asked to forward a message, I look at my neighbor list, 
discard the ones which have a larger rank than myself, and try sending 
the packet to the neighbor which has the lowest rank among all neighbors 
(my preferred parent). If L2 tells me that failed, I work my way down 
the list, sending to the neighbor with the second-lowest rank, etc. Of 
course, every time I hear a DIOs, I update my neighbor's rank 
accordingly, and recompute mine, if needed. Again, your understanding seems to be based on using DAG rank as the path cost. I dont recall exactly but, as per my understanding, RPL does not force any particular order for forwarding preference other than that parents should be preferred over siblings.

Thanks
Mukul

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 24 Sep 2009 07:37:40 +0200

All:

For the sake if this mail and because we have not yet agreed upon more
proper names, I'll keep using parents and siblings.

But I agree completely with the efforts to find more proper names.

So: 

RPL 02 has been improved to follow the recommendations in this thread.
The text now reads along the lines of:

   Once a preferred parent is selected, the node can compute its own
   rank in the DAG and determine alternate parents.  Any node inwards
   from this node, that is with a lower rank than this node, can be used
   as an alternate parent for forwarding. 

As Dominique and Thomas explained earlier in this ML, this change was
made necessary by the redefinition of rank.

A side effect is that some forwarding parents might not become preferred
anymore because they might lead to a rank increment. This is an
additional complexity to the draft. In particular for the
anti-greediness rules that we need to revalidate. 

The new text also introduces a limited greediness for a node with a
single parent, in order to get a sibling, but not a parent. To be
discussed...

Pascal

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On Behalf Of
Mukul Goyal
>Sent: jeudi 24 septembre 2009 05:59
>To: Thomas Watteyne
>Cc: IETF ROLL
>Current RPL specs use DAG rank for loop avoidance. My impression is
that DT envisioned DAG rank as a hard-to-
>change (DAG rank is allowed to decrease easily but elaborate procedure
required to cause it to increase) node
>attribute that constrains the topology (a node can have only lower rank
neighbors as parents). On the other
>hand, "path cost" is allowed to change easily. I guess it is easy to
create OCP definitions where DAG rank is
>only loosely related to path costs (e.g. DAG rank based on long-term
reliability where as path costs based on
>near-term reliability).
>
>Having said that, my impression has been that current RPL specs put too
much emphasis on loop avoidance. I
>have said it before that dealing with loops should be an add-on
feature. Basic protocol should not worry about
>loops. Applications should be free to decide whether they want to deal
with loops or not and if they want to
>whether they want to use a loop avoidance strategy or loop detection
strategy. So, I think there is no clear
>need to differentiate between "path cost" and "DAG rank".
>
>Thanks
>Mukul
>
>You are absolutely right, I consider "path cost" and "rank" to be
pretty close concepts. In fact, is there a
>clear need to differentiate those? What would be a case (probably an
OCP definition) where rank is *not*
>directly inferred from path cost?
>
>The way I see things is weighted links interconnecting nodes, each of
which then obtaining a rank by
>adding/multiplying wights on the way to the LBRs so that the closer to
the LBR, the lower the rank. With this
>in mind, in your statement:
>I choose my parents based on the path costs (the costs they advertized
in their DIOs + my cost to them) and
>pick the parent with highest DAG rank (which is solely for loop
avoidance purpose; although heavily influenced
>by routing metrics) as my "most preferred" parent. Then I calculate my
own DAG rank by adding a step value
>(between 1 and 16) to the DAG rank of this most preferred parent I
don't see why rank and path cost as
>different concepts. Is there no way we could work with only path
length, in order to obtain a somewhat simpler
>protocol?
>has the greatest rank value in the DAG parent set." The statement above
conflicts with the other statements in
>rpl-01.
>So, the most preferred parent is simply the parent with highest rank
and need not be the parent with best path
>cost.
>DIOs. It seems that you are mixing DAG rank with path cost. As per my
understanding, I choose my parents based
>on the path costs (the costs they advertized in their DIOs + my cost to
them) and pick the parent with highest
>DAG rank (which is solely for loop avoidance purpose; although heavily
influenced by routing metrics) as my
>"most preferred" parent. Then I calculate my own DAG rank by adding a
step value (between 1 and 16) to the DAG
>rank of this most preferred parent
>
>accordingly, and recompute mine, if needed. Again, your understanding
seems to be based on using DAG rank as
>the path cost. I dont recall exactly but, as per my understanding, RPL
does not force any particular order for
>forwarding preference other than that parents should be preferred over
siblings.
>
>Thanks
>Mukul
>_______________________________________________
>Roll mailing list
>[email-masked]
>https://www.ietf.org/mailman/listinfo/roll

---

From: Thomas Watteyne <[email-masked]>
Date: Thu, 24 Sep 2009 09:56:39 -0700

Mukul, I'm happy to hear we're on the exact same line.
Thomas

---

From: Thomas Watteyne <[email-masked]>
Date: Thu, 24 Sep 2009 10:10:48 -0700

Pascal, thank you for your incredible work! Although -02 reads really 
nice, I have the following suggestion.

3.3.1 now reads:

For a node N, and its most preferred parent M, DAGRank(N) >
DAGRank(M) must hold. Further, all parents in the DAG parent set
must be of a rank less than self's DAGRank(N). In other words,
the rank presented by a node N MUST be greater (deeper) than that
presented by any of its parents.

which is in line with the discussion. Nevertheless, the following lines 
seem to be in slight contradiction:

(This mechanism serves to avoid
loops in the case where an alternate parent is used- if no
alternate parent is deeper than the preferred parent then loops
are avoided. The risk of loops occurs if there is a chance for an
alternate parent to forward traffic to a deeper successor, which
may be in the sub-DAG, and traffic then makes backwards progress
and comes back to the node again).

I suggest to remove what is in parenthesis, or rewrite to something like

(This mechanism serves to avoid loops. Node N will use one of its 
parents to relay its packet. if this parent were to be of a higher rank, 
the traffic would make backwards progress).

Thomas

Pascal Thubert (pthubert) wrote:
>> Sent: Wednesday, September 23, 2009 7:23:21 PM GMT -06:00 US/Canada
>>     
> Central
>   
>>   determine the DAG structure and consequently the path cost.  The
>>     
> only
>   
>> I guess DT needs to clarify/correct the text from section 3.3.1.5 you
>>     
> quoted.
>   
>> calculate, for each neighbor, what my potential rank would be if I
>>     
> chose
>   
>> the packet to the neighbor which has the lowest rank among all
>>     
> neighbors
>