Subject: Re: [Roll] Fwd: New Version Notification for draft-ietf-roll-minrank-hysteresis-of-01

From: Phoebus Chen <[email-masked]>
Date: Tue, 01 Mar 2011 18:47:08 +0100

On 3/1/11 1:41 AM, Omprakash Gnawali wrote:
> - Parent set - only the preferred parent in the parent set. From the
> perspective of this OF, the nodes do not narrow down the list of
> candidates to a smaller set and pick a node from that smaller set. I
> am open to suggestion on a different way to explain and think about
> the parent set.
>

Omprakash,

   Just trying to understand this more clearly.  Is the reason for 
limiting the parent set to only the preferred parent, and not all the 
neighbors in the neighbor table that have rank less than the current 
node, to make sure data packets are routed along a tree?  I always 
interpreted the parent set as the set of neighbors that you can route 
packets to, upward towards the root.  Is this to limit the variability 
in end-to-end latency, etc. that comes from multipath hop-by-hop 
routing, at the cost of path diversity?

-- 
Phoebus Chen
Postdoctoral Researcher
Automatic Control Lab, KTH (Royal Institute of Technology)
http://www.ee.kth.se/~phoebus

---

From: Omprakash Gnawali <[email-masked]>
Date: Tue, 1 Mar 2011 12:18:21 -0800

On Tue, Mar 1, 2011 at 9:47 AM, Phoebus Chen <[email-masked]> wrote:
>  Just trying to understand this more clearly.  Is the reason for limiting
> the parent set to only the preferred parent, and not all the neighbors in
> the neighbor table that have rank less than the current node, to make sure
> data packets are routed along a tree?  I always interpreted the parent set
> as the set of neighbors that you can route packets to, upward towards the
> root.  Is this to limit the variability in end-to-end latency, etc. that
> comes from multipath hop-by-hop routing, at the cost of path diversity?

This OF does not give you access to those nodes with lower rank nor
treats them differently from nodes with rank lower than itself. The
only thing the OF gives you is the preferred parent. So, I changed the
language to make it very clear.

In an alternate version, yes, you could have multiple candidate
parents and route through any of them. Then there would be concerns
such as the ones you expressed. Despite the concerns, it is possible
it will turn out to be a system that performs well. If there is
substantial interest in "alternate" parents, we can incorporate that
in this OF or write a different one. If we do that, the output of the
OF would be an ordered parent set, not the preferred parent.

- om_p

---

From: Phoebus Chen <[email-masked]>
Date: Wed, 02 Mar 2011 21:54:00 +0100

On 3/1/11 9:18 PM, Omprakash Gnawali wrote:
> On Tue, Mar 1, 2011 at 9:47 AM, Phoebus Chen<[email-masked]>  wrote:

I would be interested in having alternate parents, but maybe it's better 
to hear from people in industry.  There may be some subtleties to having 
alternate parents since the advertised metric is only with respect to 
the path through the preferred parent.  Nonetheless, it should be easy 
to add a configurable constant specifying the size of the parent set and 
just order the alternate parents by link ETX + remaining ETX.  I've been 
discussing with others to understand the issues that need to be handled 
if we write an OF specifically for multipath, but we're not ready to 
make recommendations yet.

---

From: Philip Levis <[email-masked]>
Date: Wed, 2 Mar 2011 14:59:49 -0800

On Mar 2, 2011, at 12:54 PM, Phoebus Chen wrote:

> I would be interested in having alternate parents, but maybe it's better to hear from people in industry.  There may be some subtleties to having alternate parents since the advertised metric is only with respect to the path through the preferred parent.  Nonetheless, it should be easy to add a configurable constant specifying the size of the parent set and just order the alternate parents by link ETX + remaining ETX.  I've been discussing with others to understand the issues that need to be handled if we write an OF specifically for multipath, but we're not ready to make recommendations yet.

Hm -- I think it makes sense to allow multiple elements in the parent set, if only because I know of at least one solid implementation that has done so (Arch Rock/Cisco). It would be a mistake to preclude this approach for such a basic OF.

Phil

---

From: Omprakash Gnawali <[email-masked]>
Date: Wed, 2 Mar 2011 16:51:52 -0800

> Hm -- I think it makes sense to allow multiple elements in the parent set, if only because I know of at least one solid implementation that has done so (Arch Rock/Cisco). It would be a mistake to p…

My goal was it make the language clear that this OF in this version
has a single parent in the set.

Two specific questions regarding multiple parents -

What rank do you advertise?

How do you use multiple parents? For example, do you go to the 2nd
best parent when the best parent is unreachable? Do you use multiple
parents simultaneously or using different policies? The first scenario
is covered by this OF although implicitly. The second scenario is not
covered.

- om_p

---

From: Philip Levis <[email-masked]>
Date: Wed, 2 Mar 2011 17:12:41 -0800

> What rank do you advertise?

Well, take a look at the RPL spec. It says exactly what you have to advertise.

> is covered by this OF although implicitly. The second scenario is not

Implementation-specific decision. E.g., Jonathan's layer would alternate between the parents after a small number of link-layer losses. Basically, adapt in response to bursts of losses.

Phil

---

From: Omprakash Gnawali <[email-masked]>
Date: Wed, 2 Mar 2011 17:43:23 -0800

>From rpl-18:
"...
   o  When the scan is complete, the preferred parent is elected and the
      node's rank is computed as the preferred parent rank plus the step
      in rank with that parent.
.."

> Implementation-specific decision. E.g., Jonathan's layer would alternate between the parents after a small number of link-layer losses. Basically, adapt in response to bursts of losses.

Sure. I think Boomerang also had some experience with multiple parents.

>From rpl-18:

" The OF is used to compute
   an ordered list of parents."

So, I can indicate that an order list of parents is available. I
believe those two routing systems picked the neighbor with the
smallest path metric as the parent and the 2nd and 3rd shortest as the
alternate parents. Some questions for WG -

How large should this ordered list be?

How do we decide which nodes to put in this list? When we perform
parent selection, we pick a node as a parent that allows us to
minimize our estimated path cost and rank. So, path through any other
neighbor has higher estimated cost. How much higher is ok?

- om_p

---

From: Philip Levis <[email-masked]>
Date: Wed, 2 Mar 2011 17:51:21 -0800

>      in rank with that parent.

Ugh. This text in 14.1 is misleading/incorrect. The important point is in 3.5.2 and 8.2.1. 8.2.1 says:

   5.  A node's rank MUST be greater than all elements of its DODAG
       parent set.

This wording in 14.1 means that your parent set must be of size 1 unless each results in the same rank computation. Clearly a problem. Note that 14.1 is not a requirement for following the specification. It probably deserves a read-through to clean up these kinds of inconsistencies, just to make people's lives easier.

Phil

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 3 Mar 2011 09:47:02 +0100

Hi Phil:

> Ugh. This text in 14.1 is misleading/incorrect. The important point is
in 3.5.2
> and 8.2.1. 8.2.1 says:
> This wording in 14.1 means that your parent set must be of size 1
unless each
> results in the same rank computation. Clearly a problem. Note that
14.1 is not
> a requirement for following the specification. It probably deserves a
read-
> through to clean up these kinds of inconsistencies, just to make
people's
> lives easier.

[Pascal] This wording in 14.1 was expected to mean that a node computes
its Rank based on the preferred parent, and then, any neighbor that has
a lower Rank is an acceptable parent. So the parent set can be a lot
more than 1. Those neighbors can have ranks that are between that of the
node and that of its preferred parent, or even ranks that are smaller
than that of the preferred parent but for some reasons those neighbors
are not preferred, which I expect is very typical of avoiding Worst Path
First. The concept of preferred is supposed to help the node being
honest about the real metrics to the root. This somewhat means that the
preferred parent is also preferred for forwarding up.

Cheers,

Pascal

---

From: Philip Levis <[email-masked]>
Date: Fri, 4 Mar 2011 10:04:04 -0700

> preferred parent is also preferred for forwarding up.

This seems backwards, and I think is contrary to how the text in upward routes was written. The approach described in upward routes is that a node can have a parent set where the parents differ in Rank. If the route using element 1...n from the parent set has Rank R1...Rn, then the node must advertise a Rank >= max(R1...Rn).

It seems the text in 14.1 has restricted this significantly, as you state above: if you follow 14.1, then the preferred parent is equal to max(R1...Rn): it is the worst path.

This seems problematic, don't you think? Advertising a Rank >= max(R1...Rn) is honest; the node might pick an element of its parent set to forward, and so needs to inform other nodes what its worst case Rank is.

Does this make sense?

Phil

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Fri, 4 Mar 2011 20:04:45 +0100

Hi Phil:

> >
> > [Pascal] This wording in 14.1 was expected to mean that a node
> > computes its Rank based on the preferred parent, and then, any
> > neighbor that has a lower Rank is an acceptable parent. So the
parent
> > set can be a lot more than 1. Those neighbors can have ranks that
are
> > between that of the node and that of its preferred parent, or even
> > ranks that are smaller than that of the preferred parent but for
some
> > reasons those neighbors are not preferred, which I expect is very
> > typical of avoiding Worst Path First. The concept of preferred is
> > supposed to help the node being honest about the real metrics to the
> > root. This somewhat means that the preferred parent is also
preferred for
> forwarding up.
> 
> This seems backwards, and I think is contrary to how the text in
upward
> routes was written. The approach described in upward routes is that a
node
> can have a parent set where the parents differ in Rank. If the route
using
> element 1...n from the parent set has Rank R1...Rn, then the node must
> advertise a Rank >= max(R1...Rn).

[Pascal] This is correct.

> 
> It seems the text in 14.1 has restricted this significantly, as you
state above: if
> you follow 14.1, then the preferred parent is equal to max(R1...Rn):
it is the
> worst path.

[Pascal] I still fail to see how you can read this in 14.1 but if the
text leads to such understanding, then I agree it must be amended.
The best parent is selected from the metrics properties, not rank. This
gives us a reference path against which we can compare other paths.

> This seems problematic, don't you think? Advertising a Rank >=
max(R1...Rn)
> is honest; the node might pick an element of its parent set to
forward, and so
> needs to inform other nodes what its worst case Rank is.
> 
> Does this make sense?

[Pascal] Unsure what you really mean. I hope you can spare time at the
next IETF to discuss that?
If the node uses a rank that is based on a given parent and then uses
another parent then it is somewhat lying about the cost.
The spec contains the lie within borders by forcing all the other
parents to have a rank that is more than self. 
We decided not to advertise all the metrics of all the parents because
if we start that way, then we also need to advertise the ratio that
you're using etc...

Cheers,

Pascal

---

From: Philip Levis <[email-masked]>
Date: Fri, 4 Mar 2011 11:57:06 -0800

> if we start that way, then we also need to advertise the ratio that

Sure -- does the above bullet point from 14.1 explain the issue?

Phil

---

From: Omprakash Gnawali <[email-masked]>
Date: Fri, 4 Mar 2011 19:08:05 -0800

> Sure -- does the above bullet point from 14.1 explain the issue?

Based on the text in the OF section, this is definitely an issue.

In RPL draft, rather than prescribe how OF computes rank in such
detail, I would prefer to describe the input and output and leave the
details about how the rank is computed to the OF drafts. That way we
would also eliminate the contradiction we are discussing here.

- om_p

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 8 Mar 2011 14:25:40 +0100

Hi Om and Phil:

Several things:

In one hand I agree with Om that we must leave liberty to the OF to be what they need to be. Earlier versions tried to implement what you're asking now, that is specify an abstract interface to the OF and be done. For some reasons, that text faced opposition and it was removed. My suggestion here would be to start a separate draft to propose some APIs. 

OTOH, though the main spec does not wish to be on the way of the OF, it tries to make some design recommendations. And the most critical one is probably to avoid the so-called "greediness" issue. To do this, the draft recommends to compute  a reference path through a preferred parent, and define the rank and the advertised metrics based on that path. This is no absolute (uppercase) must and we can make that more clear without requiring a new last call, and I'm open to such editorial change.

But I fail to see any "contradiction" in the current text. 

In my view, this text :
"
"

Certainly does not mean that:

"
the preferred parent is equal to max(R1...Rn):
"

Let's take an example:

|         root
|
|
|               P1
|                      
|                     P2
|  P3
|                 
|                      N      
|          
V Rank

Node N sees a number of other nodes, including P1, P2, ... Pi  of respective ranks R1, R2, ... Ri

Say that for the metrics at hand P1 is "close" and parented to the root and far from N. The metrics from P1 to root is good but from N to P1, it is real bad. P1 is typically the Worst path first next hop that we do not wish to favor.

Say that P2 is  closer to N, P2 has both P1 and root as parents, root preferred. The metrics P2 to root is not as good as P1 to root but the overall metrics N-> root via P2 is better than via P1.

Then comes P3. P3 is somewhere "between" P2 and N. It is parented at P1 and P2, P1 preferred . The overall metrics N-> root via P2 is better than via P3. Thus P2 is preferred parent. This N's Rank  RN is computed off P2.

In terms of Rank, say we get for  given OF:

R1 = 5
R2 = R1 + step(P2->P1) 	= 5 + 3 = 8
R3 = R1 + step(P3->P1) 	= 5 + 5 = 10
RN = R2 + step(P2->P1) = 8 + 4 = 12

Because RN is more than R1, R2 and R3, P1 P2 and P3 can all be selected as parents for node N. But the best balance between the first hop and the rest of the way is N->P2->P1 and that's why P2 is preferred parent.
And the rank of the preferred parent is certainly not ' equal to max(R1...Rn)' - that would be P3.

So:

- I still do not see that we have a problem 

- I'm fine with lowering the shield slightly in 14.1 to ensure that people understand that this text is a generic recommendation but that the OF may override it.

- We must be clear we need to avoid a greedy behavior by which P3 would increase its Rank to get N as an additional parent. What greedy P3 gains, N loses, which is unfair. More, if N decides to be greedy and also augment its Rank, we are in a loop and that creates instabilities. It seems to me that the current text prevents greediness by forcing nodes to be true to their metrics. I do not wish to add a lot of text to discuss greediness and so it would be nice that a rewording still maintains that property without writing a book.

Cheers,

Pascal
http://www.xtranormal.com/watch/7011357/

> -----Original Message-----
> From: Omprakash Gnawali [mailto:[email-masked]]
> Sent: Saturday, March 05, 2011 4:08 AM
> To: Philip Levis
> Cc: Pascal Thubert (pthubert); [email-masked]; [email-masked]
> Subject: Re: [Roll] Fwd: New Version Notification fordraft-ietf-roll-minrank-
> hysteresis-of-01
> 
> >>>> supposed to help the node being honest about the real metrics to
> >>>> the root. This somewhat means that the preferred parent is also
> >> preferred for
> >>> forwarding up.
> >>>
> >>> element 1...n from the parent set has Rank R1...Rn, then the node
> >>> must advertise a Rank >= max(R1...Rn).
> >>
> >> The best parent is selected from the metrics properties, not rank.
> >> This gives us a reference path against which we can compare other paths.
> >
> >
> >> [Pascal] Unsure what you really mean. I hope you can spare time at
> >> the next IETF to discuss that?
> >> We decided not to advertise all the metrics of all the parents
> >> because if we start that way, then we also need to advertise the
> >> ratio that you're using etc...
> >
> In RPL draft, rather than prescribe how OF computes rank in such detail, I
> would prefer to describe the input and output and leave the details about
> how the rank is computed to the OF drafts. That way we would also eliminate
> the contradiction we are discussing here.
> 
> - om_p

---

From: C Chauvenet <[email-masked]>
Date: Tue, 8 Mar 2011 06:05:36 -0800

Hi Pascal, all, 

In your example :

R1 = 5

I guess the last line should rather be : RN = R2 + step(N->P2) = 8 + 4 = 12.

Otherwise, I really like your example and agree that the section 14.1 your are refering to is quite explicit and may not mean a  " max(R1...Rn)" computation. If people find it unclear, it may be reworded, but I find it understandable as is. Furthermore, more guidelines may be added in a seperate document like the recommendation draft that is currently ongoing.

Best,

Cédric.

-----Message d'origine-----
De : [email-masked] [mailto:[email-masked]] De la part de Pascal Thubert (pthubert)
Envoyé : mardi 8 mars 2011 14:26
À : Omprakash Gnawali; Philip Levis
Cc : [email-masked]; [email-masked]
Objet : Re: [Roll] Fwd: New Version Notification fordraft-ietf-roll-minrank-hysteresis-of-01

Hi Om and Phil:

Several things:

In my view, this text :
"

"

Let's take an example:

|         root
|
|
|               P1
|                      
|                     P2
|  P3
|                 
|                      N      
|          
V Rank

R1 = 5

So:

Cheers,

Pascal

> >>>> between that of the node and that of its preferred parent, or 
> >>>> even ranks that are smaller than that of the preferred parent but 
> >>>> for
> >> some
> >> [Pascal] I still fail to see how you can read this in 14.1 but if 
> >> the text leads to such understanding, then I agree it must be amended.
> >> If the node uses a rank that is based on a given parent and then 
> >> uses another parent then it is somewhat lying about the cost.
_______________________________________________
Roll mailing list
[email-masked]
https://www.ietf.org/mailman/listinfo/roll

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 8 Mar 2011 16:26:13 +0100

Good catch : ) 

In fact my mistake was: 
Say that P2 is  closer to N, P2 has both P1 and root as parents, root preferred 
-> 
Say that P2 is  closer to N, P2 has both P1 and root as parents, P1 preferred.

Same result though...

Thanks for all : )

Pascal

> From: C Chauvenet [mailto:[email-masked]]
> Sent: Tuesday, March 08, 2011 3:06 PM
> To: Pascal Thubert (pthubert); Omprakash Gnawali; Philip Levis
> Cc: [email-masked]; [email-masked]
> Subject: RE: [Roll] Fwd: New Version Notificationfordraft-ietf-roll-minrank-
> hysteresis-of-01
> 
> Hi Pascal, all,
> 
> In your example :
> 
> R1 = 5
> Otherwise, I really like your example and agree that the section 14.1 your are
> refering to is quite explicit and may not mean a  " max(R1...Rn)" computation.
> If people find it unclear, it may be reworded, but I find it understandable as
> is. Furthermore, more guidelines may be added in a seperate document like
> the recommendation draft that is currently ongoing.
> 
> Best,
> 
> Cédric.
> 
> De : [email-masked] [mailto:[email-masked]] De la part de Pascal
> Thubert (pthubert) Envoyé : mardi 8 mars 2011 14:26 À : Omprakash Gnawali;
> Philip Levis Cc : [email-masked]; [email-masked] Objet : Re: [Roll] Fwd: New
> Version Notification fordraft-ietf-roll-minrank-hysteresis-of-01
> 
> Hi Om and Phil:
> 
> Several things:
> 
> In one hand I agree with Om that we must leave liberty to the OF to be what
> they need to be. Earlier versions tried to implement what you're asking now,
> that is specify an abstract interface to the OF and be done. For some reasons,
> that text faced opposition and it was removed. My suggestion here would be
> to start a separate draft to propose some APIs.
> 
> OTOH, though the main spec does not wish to be on the way of the OF, it
> tries to make some design recommendations. And the most critical one is
> probably to avoid the so-called "greediness" issue. To do this, the draft
> recommends to compute  a reference path through a preferred parent, and
> define the rank and the advertised metrics based on that path. This is no
> absolute (uppercase) must and we can make that more clear without
> requiring a new last call, and I'm open to such editorial change.
> 
> Say that for the metrics at hand P1 is "close" and parented to the root and far
> from N. The metrics from P1 to root is good but from N to P1, it is real bad. P1
> is typically the Worst path first next hop that we do not wish to favor.
> 
> Say that P2 is  closer to N, P2 has both P1 and root as parents, root preferred.
> The metrics P2 to root is not as good as P1 to root but the overall metrics N->
> root via P2 is better than via P1.
> 
> Then comes P3. P3 is somewhere "between" P2 and N. It is parented at P1
> and P2, P1 preferred . The overall metrics N-> root via P2 is better than via
> P3. Thus P2 is preferred parent. This N's Rank  RN is computed off P2.
> 
> Because RN is more than R1, R2 and R3, P1 P2 and P3 can all be selected as
> parents for node N. But the best balance between the first hop and the rest
> of the way is N->P2->P1 and that's why P2 is preferred parent.
> - I'm fine with lowering the shield slightly in 14.1 to ensure that people
> understand that this text is a generic recommendation but that the OF may
> override it.
> 
> - We must be clear we need to avoid a greedy behavior by which P3 would
> increase its Rank to get N as an additional parent. What greedy P3 gains, N
> loses, which is unfair. More, if N decides to be greedy and also augment its
> Rank, we are in a loop and that creates instabilities. It seems to me that the
> current text prevents greediness by forcing nodes to be true to their metrics.
> I do not wish to add a lot of text to discuss greediness and so it would be nice
> that a rewording still maintains that property without writing a book.
> 
> Cheers,
> 
> Pascal

---

From: Philip Levis <[email-masked]>
Date: Thu, 10 Mar 2011 08:34:19 -0800

>      in rank with that parent.

The issue is when minHopRankIncrease is 1, e.g., in your last resort OF.

Phil

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Thu, 10 Mar 2011 18:09:10 +0100

Pascal

> From: Philip Levis [mailto:[email-masked]]
> Sent: Thursday, March 10, 2011 5:34 PM
> To: Pascal Thubert (pthubert)
> Cc: Omprakash Gnawali; [email-masked]; [email-masked]
> > In one hand I agree with Om that we must leave liberty to the OF to
be
> what they need to be. Earlier versions tried to implement what you're
asking
> now, that is specify an abstract interface to the OF and be done. For
some
> reasons, that text faced opposition and it was removed. My suggestion
here
> would be to start a separate draft to propose some APIs.
> >
[Pascal] 
Hum: minHopRankIncrease is a min. In the case of OF0, the default
increase is 4 times that min. Which leaves room.
Also, some alternate parents like P1 in my example might have a lower
Rank than the preferred parent.
All in all, a node can have multiple parents, at a lower, same or higher
parent than the preferred.

Pascal

---

From: Philip Levis <[email-masked]>
Date: Thu, 10 Mar 2011 10:09:33 -0800

> parent than the preferred.

Please combine these different specifications together:

8.2.2.4.  Rank and Movement within a DODAG Version

   1.  A node MUST NOT advertise a Rank less than or equal to any member
       of its parent set within the DODAG Version.

and

The failure case is simple. Consider an OF which has a node maintain three elements in its parent set. The Cisco/ARC implementation does this. The MinHopRankIncrease is 10. There are three elements of the parent set, which advertise Ranks of A=20, B=30, and C=35. If the node computes its Rank with respect to each element of the parent set, it obtains a=30, b=40, and c=45 (upper case is the parent's Rank, lower case is the Rank computed from that route). 

There are two options:

Option 1: The node chooses A as the preferred parent. It advertises a Rank of a=30. Following 8.2.2.4, it cannot include B or C in its parent set. If the MaxRankIncrease is less than 10, the node cannot fall back to B or C in this DODAG Iteration.

Option 2: The node chooses B or C as the preferred parent. It advertises a Rank of b=40 or c=45. Please note that 8.2.1 says "Finally, the preferred parent is a member of the parent set that is the preferred next hop in upward routes." This means that if the node wishes to have routing flexibility in the face of link failure, it must use suboptimal routes. It cannot select B as its preferred parent then route mostly through A.

The basic issue is that the flexibility afforded in parent selection is constrained to approximately MinHopRankIncrease, or, if the OF is very pessimistic, closer to its per-hop Rank increase.

If you remove the requirement from 14.1, then the node could have A as its preferred parent and advertise a Rank of 36 (max(parent set) + 1). This Rank is higher than that computed for its preferred parent, but the understanding is that it may need to very quickly fall over to another element of its parent set: 30 is not a guarantee under any stretch of the imagination. This is, as far as I understand it, much closer to what existing implementations do.

I know you're always concerned with this idea of "greedy" nodes gobbling up a big parent set and advertising a high Rank, but I don't think that can really happen given the current DIO processing rules. Once a node sends a DIO, it constrains how much deeper (how "greedy") it can move in the DODAG.

Phil

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Sat, 12 Mar 2011 15:43:32 +0100

> >> The issue is when minHopRankIncrease is 1, e.g., in your last
resort
> > OF.
> > All in all, a node can have multiple parents, at a lower, same or
> > higher parent than the preferred.
> 
> The failure case is simple. Consider an OF which has a node maintain
three
> elements in its parent set. The Cisco/ARC implementation does this.
The
> MinHopRankIncrease is 10. There are three elements of the parent set,
> which advertise Ranks of A=20, B=30, and C=35. If the node computes
its
> Rank with respect to each element of the parent set, it obtains a=30,
b=40,
> and c=45 (upper case is the parent's Rank, lower case is the Rank
computed
> from that route).
> 
> There are two options:
> 
> Option 1: The node chooses A as the preferred parent. It advertises a
Rank of
> a=30. Following 8.2.2.4, it cannot include B or C in its parent set.
If the
> MaxRankIncrease is less than 10, the node cannot fall back to B or C
in this
> DODAG Iteration.

[Pascal] You made the hypothesis that the step to A B and C is the min
increase. That looks surprising but let's assume it is true.
If A is the preferred parent for the actual metrics at hand, the node
has to live with it. Assuming a lower Rank than the true one to be below
B would in turn prevent B from using A. From the selfish position of the
node that's probably fine, but B might think otherwise. The text does
what it intends to do, that is prevent greediness. We are trying to
build a society of nodes, not to optimize for one given node.

> Option 2: The node chooses B or C as the preferred parent. It
advertises a
> Rank of b=40 or c=45. Please note that 8.2.1 says "Finally, the
preferred
> parent is a member of the parent set that is the preferred next hop in
> upward routes." This means that if the node wishes to have routing
flexibility
> in the face of link failure, it must use suboptimal routes. It cannot
select B as
> its preferred parent then route mostly through A.

[Pascal] Agreed. If in turn the path through B as better or equal
metrics than through A then the node might pick B and be true to the
metric, thus obey RPL's greediness avoidance. 

> 
> The basic issue is that the flexibility afforded in parent selection
is
> constrained to approximately MinHopRankIncrease, or, if the OF is very
> pessimistic, closer to its per-hop Rank increase.
> 
[Pascal] We can allow more flexibility as long as the OF has its own
anti-greediness strategy. I do not mind adding text around the sentence
saying that it is a recommended strategy but that a given OF might have
an alternate strategy.

> If you remove the requirement from 14.1, then the node could have A as
its
> preferred parent and advertise a Rank of 36 (max(parent set) + 1).
This Rank
> is higher than that computed for its preferred parent, but the
understanding
> is that it may need to very quickly fall over to another element of
its parent
> set: 30 is not a guarantee under any stretch of the imagination. This
is, as far
> as I understand it, much closer to what existing implementations do.
> 
> I know you're always concerned with this idea of "greedy" nodes
gobbling up
> a big parent set and advertising a high Rank, but I don't think that
can really
> happen given the current DIO processing rules. Once a node sends a
DIO, it
> constrains how much deeper (how "greedy") it can move in the DODAG.
> 
[Pascal] Yes, that basically stops a count to infinity that we would
create in the first place. The best way to get a good graph is probably
not to let the CTI limits decide but to be true to the metrics. 

Pascal

---

From: Philip Levis <[email-masked]>
Date: Sun, 13 Mar 2011 17:16:27 -0700

On Mar 12, 2011, at 6:43 AM, Pascal Thubert (pthubert) wrote:

> increase.

No, this is not a hypothesis. It's a possible network setup. Or do you think it's impossible for a network to ever look like this? I am happy to show you gigabytes of traces from real wireless networks showing such circumstances.

> That looks surprising but let's assume it is true.

I do not understand your metaphors. 

> not to let the CTI limits decide but to be true to the metrics. 

What makes you say this? The issue I have is that your claims on what is better to do seem to be at odds with current practice in most protocol implementations I am aware of. I'm looking for data to support your claims.

Phil