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

From: Robert Cragie <[email-masked]>
Date: Wed, 07 Apr 2010 20:50:25 +0100

Apologies in advance for the long e-mail. I'm trying to follow this 
thread and draw some conclusions.

_DIO/DAO parent_

I find the terms DIO parent and DAO parent confusing. There can only be 
one parent type and that is a node with a lower rank than you. This is 
why I tend to subscribe to Pascal's view that these are really two 
separate DAGs. If there is some convenient way of amalgamating them then 
all well and good but I sometimes wonder if it wouldn't be easier to 
call them all DAGs and consider the downward route an additional 
'twig-like' DAG to a single node. In this way, a common objective 
function for reaching a node makes far more sense.

In fact, I wonder what the need for a separate DAO message is at all. 
The main distinction between a DIO and a DAO is that a DAO sent up the 
DAG as opposed to multicast, i.e. directed; however the DAO is not 
/routed /through the DAG and has concept of rank and parents too for 
propagation. So really it does not seem much different to a DIO. It just 
has some rough guidance from another DAG as to where to direct it. So we 
could consider three DIO's:

   1. DIO to all, multicast
   2. DIO to target, multicast
   3. DIO to target, directed

(1) is what is currently DIO, (2) is what we need for P2P, (3) is what 
is currently DAO. OK, maybe we just call (3) a DAO still but let's clean 
up how it propagates.

Note we may be wanting to add Richard's, parent tables to the DIO as 
well as replacing the DAO RRstack for the non-storing P2P solution.

_Link costs and DAG formation_

Regarding link costs and their place in DAG formation, Mukul stated in 
an earlier e-mail:

/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
/
I would say B always has some semblance of the link cost from A->B by 
virtue of having received a packet from A. At the very least, it knows A 
is able to communicate to B because, well, it received it. It could then 
use further metrics such as LQL to further judge the link cost. So I 
would revise this to:

So when B receives a multicast DIO from A, B:

   1. will have some notion of unidirectional cost A->B by virtue of
      receiving it
   2. may know unidirectional cost B->A only
   3. may know both

Consider the simple DAG below. Apologies for the drawn-out scenario and 
please correct anything which seems wrong. For rank I am using simple 
cardinal number ordinality:

     A
    / \
   B   C
  / \ / \
D   E   F

   1. A transmits DIO
   2. B hears DIO
         1. B knows there is a route from A->B by virtue of receiving it
         2. /*B does not necessarily know there is a route from B->A as
            it may not have the unidirectional link cost from B->A*/
         3. /*If the objective of forming the DODAG is to be able to
            route to A then B needs some metric for link cost from B->A*/
         4. B must compute its rank based on the objective function, the
            DIO from A and possibly other stored state
         5. B computes its rank as A+1 and marks A as parent
         6. Some time later, B transmits DIO
               1. D hears DIO
                     1. D knows there is a route from B->D by virtue of
                        receiving it
                     2. */D does not necessarily know there is a route
                        from D->B as it may not have the unidirectional
                        link cost from D->B/*
                     3. */If the objective of forming the DODAG is to be
                        able to route to A then D needs some metric for
                        link cost from D->B/*
                     4. D must compute its rank based on the objective
                        function, the DIO from B and possibly other
                        stored state
                     5. D computes its rank as B+1 (= A+2) and marks B
                        as a parent
                     6. Some time later, D transmits DIO
               2. E hears DIO
                     1. E knows there is a route from B->E by virtue of
                        receiving it
                     2. */E does not necessarily know there is a route
                        from E->B as it may not have the unidirectional
                        link cost from E->B/*
                     3. */If the objective of forming the DODAG is to be
                        able to route to A then E needs some metric for
                        link cost from E->B/*
                     4. E must compute its rank based on the objective
                        function, the DIO from B and possibly other
                        stored state
                     5. E computes its rank as B+1 (= A+2) and marks B
                        as a parent
                     6. Some time later, E transmits DIO
   3. C hears DIO
         1. C knows there is a route from A->C by virtue of receiving it
         2. /*C does not necessarily know there is a route from C->A as
            it may not have the unidirectional link cost from C->A*/
         3. /*If the objective of forming the DODAG is to be able to
            route from C->A then C needs some metric for link cost from
            C->A*/
         4. C must compute its rank based on the objective function, the
            DIO from A and possibly other stored state
         5. C computes its rank as A+1
         6. Some time later, C transmits DIO
               1. E hears DIO (assume E has already heard DIO from B)
                     1. E knows there is a route from C->E by virtue of
                        receiving it
                     2. */E does not necessarily know there is a route
                        from E->C as it may not have the unidirectional
                        link cost from E->C/*
                     3. */If the objective of forming the DODAG is to be
                        able to route to A then E needs some metric for
                        link cost from E->C/*
                     4. E must compute its rank based on the objective
                        function, the DIO from C and possibly other
                        stored state
                     5. E computes its rank as C+1 (= A+2). As it is the
                        same as previously calculated rank, it marks C
                        as another potential parent
                     6. Some time later, E continues to transmit DIO as
                        it was already transmitting it
               2. F hears DIO
                     1. F knows there is a route from C->F by virtue of
                        receiving it
                     2. /*F does not necessarily know there is a route
                        from F->C as it may not have the unidirectional
                        link cost from F->C*/
                     3. /*If the objective of forming the DODAG is to be
                        able to route to A then F needs some metric for
                        link cost from F->C*/
                     4. F must compute its rank based on the objective
                        function, the DIO from C and possibly other
                        stored state
                     5. F computes its rank as C+1 (= A+2) and marks C
                        as a parent
                     6. Some time later, F transmits DIO

Consider a path along that DAG, (A - B - D):

   1. Using DIOs doesn't naturally form the route from D to A (A <- B <-
      D) unless outgoing costs (i.e. B's perception of B->A, D's
      perception of D->B) is known
   2. Using a DIO does naturally form the route from A to D (A -> B ->
      D) on the assumption that reception of data is a reasonable
      confirmation that a link exists
         1. However as DIO originator, A needs to know that D heard its
            DIO via B therefore still needs a return path back to A via
            B. So it's catch 22.

The bottom line is that I cannot see how DAG formation can function 
properly without the outgoing cost being known. The question is - how do 
we know it? Three possible solutions for A <- B:

   1. B receives data from A with A's perception of B->A based on
      incoming cost
   2. B has a perception of B->A outgoing cost based on other metrics
      e.g. failed L2 acks
   3. B assumes that A is reachable by virtue of having received from it

(1) is probably the best, (2) is workable but still requires a viable 
link from A -> B and (3) is guessing. To achieve (1), there is probably 
some need for additional status messages to propagate this information.

Robert

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

On 01/04/2010 3:31 AM, Philip Levis wrote:
>
> On Mar 31, 2010, at 5:43 PM, Mukul Goyal wrote:
>
>>>>> 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?
>>>>
>>>> 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?
>>>
>>> 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]
>> I'm sorry -- your sentence is kind of long and convoluted, and I 
>> can't understand it.
>>
>> I am sorry too: for the length and convolution of my sentence. :)
>> And for the fact that you can't understand it (if you say so). :)
>>
>> Hey, I am kidding. Dont get mad at me.
>>
>> [Phil] Does it say yes my sentence is correct or no it is not correct?
>>
>> 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).
>
> 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?
>
> Phil
>
>
> _______________________________________________
> Roll mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/roll
>

---

From: Yoav Ben-Yehezkel <[email-masked]>
Date: Thu, 8 Apr 2010 10:54:54 +0300

+1

*From:* [email-masked] [mailto:[email-masked]] *On
Behalf Of *Robert
Cragie
*Sent:* Wednesday, April 07, 2010 10:50 PM
*To:* [email-masked]
*Subject:* Re: [Roll] proposal for DAOs in non-caching DODAGs

Apologies in advance for the long e-mail. I'm trying to follow this thread
and draw some conclusions.

*DIO/DAO parent*

I find the terms DIO parent and DAO parent confusing. There can only be one
parent type and that is a node with a lower rank than you. This is why I
tend to subscribe to Pascal's view that these are really two separate DAGs.
If there is some convenient way of amalgamating them then all well and good
but I sometimes wonder if it wouldn't be easier to call them all DAGs and
consider the downward route an additional 'twig-like' DAG to a single node.
In this way, a common objective function for reaching a node makes far more
sense.

In fact, I wonder what the need for a separate DAO message is at all. The
main distinction between a DIO and a DAO is that a DAO sent up the DAG as
opposed to multicast, i.e. directed; however the DAO is not *routed *through
the DAG and has concept of rank and parents too for propagation. So really
it does not seem much different to a DIO. It just has some rough guidance
from another DAG as to where to direct it. So we could consider three DIO's:

   1. DIO to all, multicast

(1) is what is currently DIO, (2) is what we need for P2P, (3) is what is
currently DAO. OK, maybe we just call (3) a DAO still but let's clean up how
it propagates.

Note we may be wanting to add Richard's, parent tables to the DIO as well as
replacing the DAO RRstack for the non-storing P2P solution.

*Link costs and DAG formation*

Regarding link costs and their place in DAG formation, Mukul stated in an
earlier e-mail:

*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
*
I would say B always has some semblance of the link cost from A->B by virtue
of having received a packet from A. At the very least, it knows A is able to
communicate to B because, well, it received it. It could then use further
metrics such as LQL to further judge the link cost. So I would revise this
to:

    A
   / \
  B   C
 / \ / \
D   E   F

   1. A transmits DIO
   2. B hears DIO
      1. B knows there is a route from A->B by virtue of receiving it
      2. *B does not necessarily know there is a route from B->A as it may
      not have the unidirectional link cost from B->A*
      3. *If the objective of forming the DODAG is to be able to route to A
      then B needs some metric for link cost from B->A*
      4. B must compute its rank based on the objective function, the DIO
      from A and possibly other stored state
      5. B computes its rank as A+1 and marks A as parent
      6. Some time later, B transmits DIO
         1. D hears DIO
            1. D knows there is a route from B->D by virtue of receiving it
            2. *D does not necessarily know there is a route from D->B as it
            may not have the unidirectional link cost from D->B*
            3. *If the objective of forming the DODAG is to be able to route
            to A then D needs some metric for link cost from D->B*
            4. D must compute its rank based on the objective function, the
            DIO from B and possibly other stored state
            5. D computes its rank as B+1 (= A+2) and marks B as a parent
            6. Some time later, D transmits DIO
         2. E hears DIO
            1. E knows there is a route from B->E by virtue of receiving it
            2. *E does not necessarily know there is a route from E->B as it
            may not have the unidirectional link cost from E->B*
            3. *If the objective of forming the DODAG is to be able to route
            to A then E needs some metric for link cost from E->B*
            4. E must compute its rank based on the objective function, the
            DIO from B and possibly other stored state
            5. E computes its rank as B+1 (= A+2) and marks B as a parent
            6. Some time later, E transmits DIO
          3. C hears DIO
      1. C knows there is a route from A->C by virtue of receiving it
      2. *C does not necessarily know there is a route from C->A as it may
      not have the unidirectional link cost from C->A*
      3. *If the objective of forming the DODAG is to be able to route from
      C->A then C needs some metric for link cost from C->A*
      4. C must compute its rank based on the objective function, the DIO
      from A and possibly other stored state
      5. C computes its rank as A+1
      6. Some time later, C transmits DIO
         1. E hears DIO (assume E has already heard DIO from B)
            1. E knows there is a route from C->E by virtue of receiving it
            2. *E does not necessarily know there is a route from E->C as it
            may not have the unidirectional link cost from E->C*
            3. *If the objective of forming the DODAG is to be able to route
            to A then E needs some metric for link cost from E->C*
            4. E must compute its rank based on the objective function, the
            DIO from C and possibly other stored state
            5. E computes its rank as C+1 (= A+2). As it is the same as
            previously calculated rank, it marks C as another potential parent
            6. Some time later, E continues to transmit DIO as it was
            already transmitting it
         2. F hears DIO
            1. F knows there is a route from C->F by virtue of receiving it
            2. *F does not necessarily know there is a route from F->C as it
            may not have the unidirectional link cost from F->C*
            3. *If the objective of forming the DODAG is to be able to route
            to A then F needs some metric for link cost from F->C*
            4. F must compute its rank based on the objective function, the
            DIO from C and possibly other stored state
            5. F computes its rank as C+1 (= A+2) and marks C as a parent
            6. Some time later, F transmits DIO

   1. Using DIOs doesn't naturally form the route from D to A (A <- B <- D)
   unless outgoing costs (i.e. B's perception of B->A, D's perception of D->B)
   is known
   2. Using a DIO does naturally form the route from A to D (A -> B -> D) on
   the assumption that reception of data is a reasonable confirmation that a
   link exists
      1. However as DIO originator, A needs to know that D heard its DIO via
      B therefore still needs a return path back to A via B. So it's catch 22.

The bottom line is that I cannot see how DAG formation can function properly
without the outgoing cost being known. The question is - how do we know it?
Three possible solutions for A <- B:

   1. B receives data from A with A's perception of B->A based on incoming
   cost
   2. B has a perception of B->A outgoing cost based on other metrics e.g.
   failed L2 acks
   3. B assumes that A is reachable by virtue of having received from it

(1) is probably the best, (2) is workable but still requires a viable link
from A -> B and (3) is guessing. To achieve (1), there is probably some need
for additional status messages to propagate this information.

Robert

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

   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?

  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?

 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]
I'm sorry -- your sentence is kind of long and convoluted, and I can't
understand it.

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

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?

Phil

Roll mailing list

[email-masked]

---

From: Michael Richardson <[email-masked]>
Date: Mon, 12 Apr 2010 10:02:28 -0400

Robert, thanks for the great write up.
{Like you, I don't try to keep on top of the threads as they occur.}

My understanding is that *some* L2s already know the cost values due to
layer-2 activity.  I still think that this information should be
transmitted again at Layer-3, and that some Layer-2 won't be able to
calculate cost, or that cost won't be visible to layer-3!

I agree with your analysis of DIO/DAO confusion.
It's clear we need ACKs in this protocol.  

I think that some of the ACKs were implicit when we started as being
inside the ND payloads, because the NDs were themselves already
bi-directional. 

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