Subject: Re: [Roll] proposal for DAOs in non-caching DODAGs

From: Mukul Goyal <[email-masked]>
Date: Sat, 3 Apr 2010 19:47:44 -0500 (CDT)

Phil:

Please see my response below.

Thanks
Mukul

[Phil] I'm not sure I understand the concern. Is it that if this isn't stated explicitly, then an implementation might put a neighbor in the parent set for which it cannot compute DAGRank from the OF? How would it ever compute its own DAGRank? Can you explain the failure condition? 

[Mukul]
Consider the situation where node A receives a DIO from node B and knows the cost of link B->A (either it already knew this cost or DIO carries this cost or it assumes a value for this cost) but not that of link A->B. Then, node A may be able to compute its DAG rank via node B and thus possibly select node B as a DIO parent. But, even if B becomes a DIO parent, A should not consider B as a candidate for DAO parenthood because A does not know the cost of link A->B.     

[Phil] So a node A MUST NOT select node B as a parent if the OF cannot compute the DAGRank of the resulting route? 

[Mukul]
Node A may have sufficient information to calculate its DAG rank via B but still may not have the information to calculate B's suitability as a DAO parent (e.g. if OF just considers the upwards costs in calculating the DAG rank and such costs are known to A but requires knowledge of downwards costs for a parent's selection as DAO parent and these downwards costs (from B to A) are not known to A). 

[Phil] Does it say yes my sentence is correct or no it is not correct? 

[Mukul]
It says that your sentence is not correct. This is because your sentence assumes that the DAGrank calculation requires knowledge of all sorts of costs that the node may need to choose its DAG or DAO parents. This assumption is not true. A DAGrank is simply a loop avoidance mechanism that may not be a very good indicator of actual routing costs in either direction. I know you would disagree with me (based on my understanding of your point of view from your previous posts). 

[Phil]
Ah -- I think this is why we can't seem to agree: we're coming from different assumptions. There was a change in -07; Richard noted that having Rank *not* reflect a metric is problematic, as it constrains parent selection. I.e., if Rank does not directly reflect a metric, it's possible that a node can't pick a better (lower metric) parent because it has a higher Rank. This led to the inclusion of MinHopRankIncrease, elevating Rank to 16-bits, and the introduction of DAGRank, such that Rank could still reflect a good fidelity metric but DAGRank can provide good loop avoidance and topology constraints. 

The operating assumption is that since Rank constrains the set of parents a node can select, then separating it from metrics is problematic. 

The OF computes the Rank (this has always been the case): it should have all of the needed information. Or is there something in the draft that says it won't? 

[Mukul]
I can see that RPL-7 talks about 16-bit rank and MinHopRankIncrease. But I could find no text in the draft that says that the rank should represent the routing cost. In fact, Section 3.6.2 clearly says that the rank represents a node's position in the DAG and that "The rank is not a cost metric, although its value can be derived from and influenced by metrics." (2nd paragraph in 3.6.2). 

Rank can be made to reflect the routing costs if desired. But, it is not mandatory to do so (atleast as per RPL-7). It should not be mandatory to do so. Rank's primary objective is to indicate node's position in the DAG. Whether it reflects the routing costs as well is secondary/optional.

Hence, OF need not consider the costs in both directions while choosing the rank. So, the rank of a parent may not indicate its suitability to serve as a DAO parent. In fact, second bullet point in Section 6.2.3 makes it clear:

"The selection of DAO parents is implementation specific and may be based on selecting the DODAG Parents that offer the best upwards cost (as opposed to downwards or mixed), as determined by the metrics in use and the Objective Function.
"
I guess it wont hurt to mention in the draft that if a DAG plans to support downwards routes then the DIOs should carry downwards routing metrics (both aggregated and local values, i.e. a DIO from A should carry aggregated routing cost from root till A and local cost from A to specific neighbors).
   
Thanks
Mukul

---

From: Robert Cragie <[email-masked]>
Date: Thu, 08 Apr 2010 12:26:08 +0100

Hi Mukul

On 08/04/2010 12:07 PM, Mukul Goyal wrote:

> Hi Robert
>
>    
>> So when B receives a multicast DIO from A, B may know:
>>      
>    
>> 1) unidirectional cost A->B only or
>> 2) unidirectional cost B->A only or
>> 3) both or
>> 4) none
>>      
> Whether B knows A->B or B->A or both or none, really depends on the definition of L3 cost. Here are some examples:
>
> If the cost is ETX, it seems that B does not know A->B. It may know B->A on the basis of past history of sending packets to A.
>    
<RCC>But B knows there is a viable link A->B at that epoch by virtue of 
receiving the packet at the very least. It would seem pointless to 
ignore this as part of the link cost assessment, surely?</RCC>
> If the cost is LQI, B knows A->B. It probably does not know B->A unless it received some past feedback from A.
>
>    
Robert Cragie (Pacific Gas & Electric)

Gridmerge Ltd.
89 Greenfield Crescent,
Wakefield, WF4 4WA, UK
+44 (0) 1924 910888
http://www.gridmerge.com <http://www.gridmerge.com/>

---

From: Michael Richardson <[email-masked]>
Date: Mon, 12 Apr 2010 09:50:26 -0400

notsure1> I'm not sure I understand the concern. Is it that if this
    notsure1> isn't stated explicitly, then an implementation might put a
    notsure1> neighbor in the parent set for which it cannot compute
    notsure1> DAGRank from the OF? How would it ever compute its own
    notsure1> DAGRank? Can you explain the failure condition? 

    notsure2> Consider the situation where node A receives a DIO from
    notsure2> node B and knows the cost of link B->A (either it already
    notsure2> knew this cost or DIO carries this cost or it assumes a
    notsure2> value for this cost) but not that of link A->B. Then, node
    notsure2> A may be able to compute its DAG rank via node B and thus
    notsure2> possibly select node B as a DIO parent. But, even if B
    notsure2> becomes a DIO parent, A should not consider B as a
    notsure2> candidate for DAO parenthood because A does not know the
    notsure2> cost of link A->B.     

    Phil> So a node A MUST NOT select node B as a parent if the OF
    Phil> cannot compute the DAGRank of the resulting route? 

>>>>> "Mukul" == Mukul Goyal <[email-masked]> writes:
    Mukul> Node A may have sufficient information to calculate its DAG
    Mukul> rank via B but still may not have the information to
    Mukul> calculate B's suitability as a DAO parent (e.g. if OF just
    Mukul> considers the upwards costs in calculating the DAG rank and
    Mukul> such costs are known to A but requires knowledge of downwards
    Mukul> costs for a parent's selection as DAO parent and these
    Mukul> downwards costs (from B to A) are not known to A). 

Naively, if the A->B link is never used, then you'd never know what the
cost of the link is.   

But Jonathan has said:

>>>>> "Jonathan" == Jonathan Hui <[email-masked]> writes:
    Jonathan> It's obvious that if A's link cost estimation information
    Jonathan> about the  path from A -> B, then whatever mechanism is
    Jonathan> used to generate that  link cost metric needs to be
    Jonathan> communicated to be resident at A.  It's  not obvious to me
    Jonathan> that the routing protocol should be responsible for  make
    Jonathan> sure this happens. I'd actually prefer that the link
    Jonathan> estimation  mechanism handle the necessary propagation of
    Jonathan> information. 

So this suggests to me that there is some possibly-out-of-scope,
possibly-layer-2-specific, mechanism that calculates the costs.

Is this correct?

I would rather do all the work with as few transmissions as possible.
I would think that the A->B cost includes such things as the transmit
power required for B to hear A, and reducing that extends battery life.

I would imagine B transmitting their DIO messages with increasing power
until it gets an ack from A.  (We haven't defined such an ACK yet)

I would want to use the A->B link, if it can be used, until such time as
another link appears with a lower cost.  

- -- 
]       He who is tired of Weird Al is tired of life!           |  firewalls  [
]   Michael Richardson, Sandelman Software Works, Ottawa, ON    |net architect[
] [email-masked] http://www.sandelman.ottawa.on.ca/ |device driver[
   Kyoto Plus: watch the video <http://www.youtube.com/watch?v=kzx1ycLXQSE>
	               then sign the petition.