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

From: Mukul Goyal <[email-masked]>
Date: Mon, 29 Mar 2010 01:17:31 -0500 (CDT)

A related question that has been bugging me for a while is:

Does RPL assume routing metrics to be essentially symmetric in nature?

When node B receives a DIO from node A about a DAG with root R, it can choose whether link B->A is going to be part of the route from B to R. Node B can use its knowledge of link cost B->A in making this decision.

But when node B picks parent A as a DAO parent, it is deciding that link A->B can be on the path from root R to itself. But B does not know the link cost A->B unless it is assumed to be same as link cost B->A!!!

If RPL indeed assumes symmetrical link costs, it would be good to admit it in the draft explicitly.

Thanks
Mukul

----- Original Message -----
From: "JeongGil Ko (John)" <[email-masked]>
To: "Pascal Thubert (pthubert)" <[email-masked]>
Cc: [email-masked]
Sent: Monday, March 29, 2010 1:03:32 AM GMT -06:00 US/Canada Central
Subject: Re: [Roll] proposal for DAOs in non-caching DODAGs

Hi Pascal,

I see your point. One question, that confuses me is how the set of 'preferred DAO parents' are determined. Is this set different from the preferred parent set in DIOs? I guess another way of asking is to ask is how the DAORank is defined and computed (this question was asked previously but I didn't really get a clear answer). Will each node that initiates a DAO for a specific prefix be DAORank = 1 and the rank computation continue just like the DIO process? In this case is it true that each node may need to maintain different DAORank values for many different prefixes?

Thanks!

-John

On Mar 28, 2010, at 10:44 PM, Pascal Thubert (pthubert) wrote:

> Hi John:
> 
> Obviously, having multiple parents enables the root to compute multiple
> paths down to the node. So your proposal is tempting. But beware, this
> is a slippery slope towards centralized Link State computation and away
> from the RPL core design, and we can't be designing 2 protocols, by
> charter.
> 
> The RPL design is that the choice of the best parents belongs to the OF
> in the node, not the root. Richard's proposal centralizes in the root
> the forwarding decision along the DAG that happens hop by hop with
> stateful DAOs, but the routing  states are built in the exact same
> fashion whether it is stateful or stateless, by having each node select
> a set of preferred DAO parents. Note that we do not specify how a node
> selects the next hop between multiple DAO children in the stateful mode.
> In the same fashion, we do not specify how the root makes the multi hop
> decision.
> 
> My suggestion to address your problem would be that the OF in the node
> provides more info on how it orders the parents, maybe by setting a
> preference level (like 0-3) for each parent in the source route DAO. The
> root retains the possibility to build multiple non-overlapping path, do
> load balancing, signal to L2 when L2 paths/circuits need to be enabled,
> etc... We have not made the step towards a centralized routing model. 
> 
> Cheers,
> 
> Pascal
> 
> 
>> -----Original Message-----
>> From: [email-masked] [mailto:[email-masked]] On Behalf
> Of
>> JeongGil Ko (John)
>> Sent: Sunday, March 28, 2010 11:42 PM
>> To: Richard Kelsey
>> Cc: [email-masked]
>> Subject: Re: [Roll] proposal for DAOs in non-caching DODAGs
>> 
>> Richard,
>> 
>> I agree that if we start adding downwards routes then the root will
> have
>> many sub-route (or sub-path) information that it already has. If we
> decide
>> the add the neighbor (parent) information in the DAOs do we also add
> link
>> quality estimation values for each link associated with a parent node?
>> Otherwise the root will have a connectivity graph of the network (DAG)
> but
>> will have no way to figure out which path is cost-efficient to select
> (the root
>> can come up with many combinations of paths to select from)?
>> 
>> Thanks.
>> 
>> -John
>> 
>> On Mar 28, 2010, at 2:20 PM, Richard Kelsey wrote:
>> 
>>> Pascal and I had a discussion on how to simplify DAOs if the group
>>> confirms the decision to not explicitly support DAGs with mixed
>>> caching and non-caching routers.  The obvious simplification is that
>>> the DIO 'S' flag is either on or off throughout a DODAG, eliminating
>>> the need to do anything when it changes.
>>> 
>>> More interestingly, the reverse route stack is no longer needed.  It
>>> is not used if all nodes cache DAOs.  If only the root does so,
>>> including intermediate hops when forwarding DAOs only duplicates
>>> information that the root will receive from others.
>>> 
>>> Our proposal is to replace the reverse route stack with a set of
>>> parents that is forwarded up the DAG to the root.
>>> The DAO format stays the same, except that the reverse route stack
> is
>>> now a set of parents and is not changed when forwarded.
>>> 
>>> The root can then reconstruct the DAG and compute downwards routes
> as
>>> needed.  This is not as big a change as it may
>>> seem: in the current draft the root may have to compute the paths to
>>> nodes whose S bit is not set.  Path computation is simpler than for
> a
>>> full link-state protocol, as the DIOs have preselected the better
>>> up/down links in forming the DAG and other links are not reported.
>>> 
>>> The advantages of using a parent set rather than a reverse route
> stack
>>> are:
>>> - downward path diversity while only sending DAOs
>>>   to the preferred parent
>>> - DAOs do not grow with DAG depth
>>> - DAO forwarding is simpler
>>> 
>>> What do people think?
>>>                                 -Richard Kelsey
>>> _______________________________________________
>>> Roll mailing list
>>> [email-masked]
>>> https://www.ietf.org/mailman/listinfo/roll
>>> 
>> 
>> ------
>> JeongGil Ko (John)
>> Ph.D. Student
>> Department of Computer Science
>> Johns Hopkins University
>> http://www.cs.jhu.edu/~jgko
>> 
>> _______________________________________________
>> Roll mailing list
>> [email-masked]
>> https://www.ietf.org/mailman/listinfo/roll
> 

------
JeongGil Ko (John)
Ph.D. Student
Department of Computer Science
Johns Hopkins University
http://www.cs.jhu.edu/~jgko

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

---

From: JP Vasseur <[email-masked]>
Date: Mon, 29 Mar 2010 08:29:03 +0200

On Mar 29, 2010, at 8:17 AM, Mukul Goyal wrote:

> When node B receives a DIO from node A about a DAG with root R, it  
> can choose whether link B->A is going to be part of the route from B  
> to R. Node B can use its knowledge of link cost B->A in making this  
> decision.
>
> But when node B picks parent A as a DAO parent, it is deciding that  
> link A->B can be on the path from root R to itself. But B does not  
> know the link cost A->B unless it is assumed to be same as link cost  
> B->A!!!
>

You can add the DAG metric container in both the DIO and DAO.

> I see your point. One question, that confuses me is how the set of  
> 'preferred DAO parents' are determined. Is this set different from  
> the preferred parent set in DIOs? I guess another way of asking is  
> to ask is how the DAORank is defined and computed (this question was  
> asked previously but I didn't really get a clear answer). Will each  
> node that initiates a DAO for a specific prefix be DAORank = 1 and  
> the rank computation continue just like the DIO process? In this  
> case is it true that each node may need to maintain different  
> DAORank values for many different prefixes?
>
> Thanks!
>
> -John
>

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 29 Mar 2010 08:41:32 +0200

Hi Mukul
 
> Does RPL assume routing metrics to be essentially symmetric in nature?

[Pascal] Certainly not ! An instance builds a single DAG though. So a node has to mick DAO and DIO parents and compute a Rank that's higher than any of those.
To do better than that, one can deploy an up and a down instance, each optimizing for one direction only.

> When node B receives a DIO from node A about a DAG with root R, it can
> choose whether link B->A is going to be part of the route from B to R. Node B
> can use its knowledge of link cost B->A in making this decision.
> 
> But when node B picks parent A as a DAO parent, it is deciding that link A->B
> can be on the path from root R to itself. But B does not know the link cost A-
> >B unless it is assumed to be same as link cost B->A!!!

[Pascal] RPL enables multiple metrics in the same DIO with some logic to tie them in. Some metrics can deal with the up and others with the down direction. 
Makes sense?

Pascal
> I see your point. One question, that confuses me is how the set of 'preferred
> DAO parents' are determined. Is this set different from the preferred parent
> set in DIOs? I guess another way of asking is to ask is how the DAORank is
> defined and computed (this question was asked previously but I didn't really
> get a clear answer). Will each node that initiates a DAO for a specific prefix be
> DAORank = 1 and the rank computation continue just like the DIO process? In
> this case is it true that each node may need to maintain different DAORank
> values for many different prefixes?
> 
> Thanks!
> 
> -John
> 
> > Obviously, having multiple parents enables the root to compute
> > multiple paths down to the node. So your proposal is tempting. But
> > beware, this is a slippery slope towards centralized Link State
> > computation and away from the RPL core design, and we can't be
> > designing 2 protocols, by charter.
> >
> > The RPL design is that the choice of the best parents belongs to the
> > OF in the node, not the root. Richard's proposal centralizes in the
> > root the forwarding decision along the DAG that happens hop by hop
> > with stateful DAOs, but the routing  states are built in the exact
> > same fashion whether it is stateful or stateless, by having each node
> > select a set of preferred DAO parents. Note that we do not specify how
> > a node selects the next hop between multiple DAO children in the stateful
> mode.
> > In the same fashion, we do not specify how the root makes the multi
> > hop decision.
> >
> > preference level (like 0-3) for each parent in the source route DAO.
> > The root retains the possibility to build multiple non-overlapping
> > path, do load balancing, signal to L2 when L2 paths/circuits need to
> > be enabled, etc... We have not made the step towards a centralized
> routing model.
> >
> > Cheers,
> >
> > Pascal
> >
> >

---

From: Mukul Goyal <[email-masked]>
Date: Mon, 29 Mar 2010 01:57:33 -0500 (CDT)

Hi Pascal

[MG] So, when node A sends out a DIO, one metric object would indicate the aggregated metric from root till A and another metric object would indicate the local link/node level metric value? This works for a node-level metric value. But, the link-level metric value (e.g. link LQL) would be different for different receivers of the DIO. A DIO is sent via link-local multicast. So, in order to send a local link-level metric value, node A would have to identify the receiver(s) for which this value is valid. No?

Mukul

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 29 Mar 2010 11:58:08 +0200

Hi Mukul,

I think I understand what you're saying. 

Here, we are talking about link indicators, as can be evaluated by either one end or the other from link layer information, as opposed to metrics in the metrics containers in DIO/DAO that are L3 abstraction aggregated along the rest of the route. And yes, for all I know, some indicators are receiver side (like RSSI/RCPI) while others are sender side (like a stats on retries or xmit queue latency).
 
Depending on the indicator, it seems that the child is in position to compute the (1 hop) link metric upon DIO(s) for either the upward or the downward path.

Ideally, we'd like them all to be receiver side so that a child can compute everything upon a DIO, preferred DIO parent(s) for default route and preferred DAO parent(s) for downward route. If we cannot do that and we still want the child to get metrics for the other direction, it appears that some additional mechanism must be put in place whereby the child sends something to the parent, and the parent sends back its own view of the link child->parent so that now the child can make an informed decision.

We have no unicast message from parent to child at this point. The thing closest to why you seem to be asking for would be a unicast DIS followed by a unicast DIO whereby the parent places a link metrics container that informs the child of the parent's view of the link. It makes sense to me that such a process belong to the grey zone where a child assesses the quality of a link with a candidate neighbor prior to allowing it as a parent.

Is that your question?

Pascal

> From: Mukul Goyal [mailto:[email-masked]]
> Sent: Monday, March 29, 2010 8:58 AM
> To: Pascal Thubert (pthubert)
> Cc: [email-masked]; JeongGil Ko (John)
> > know the link cost A-
> [Pascal] RPL enables multiple metrics in the same DIO with some logic to tie
> them in. Some metrics can deal with the up and others with the down
> direction.
> Makes sense?
> 
> [MG] So, when node A sends out a DIO, one metric object would indicate the
> aggregated metric from root till A and another metric object would indicate
> the local link/node level metric value? This works for a node-level metric
> value. But, the link-level metric value (e.g. link LQL) would be different for
> different receivers of the DIO. A DIO is sent via link-local multicast. So, in
> order to send a local link-level metric value, node A would have to identify
> the receiver(s) for which this value is valid. No?
> 
> 
> Mukul