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

From: Jonathan Hui <[email-masked]>
Date: Thu, 1 Apr 2010 08:46:18 -0700

Hi Pascal,

On Mar 31, 2010, at 11:57 PM, Pascal Thubert (pthubert) wrote:

> The default route is needed as soon as you do some P2P along the DAG,
> because you cannot switch instance on the way. This is somewhat
> unrelated to the discussion here.

Fully agree.  I would classify a P2P RPL instance as needing to deal  
with both upward and downward routes.

> The question is rather which instance is applied to a packet before  
> the
> packet is sent out.
>
> The application in a RPL node needs to be (abstractly) aware of
> instances, and it should tag the packets with the proper instance ID  
> so
> that the DAG that is computed to optimize the upstream is used. Even  
> if
> multiple DAGs have a default route, we still use the right one.

If this is our working assumption, then we need to document it  
clearly.  It implies that host nodes that do not participate in RPL  
will need to understand which RPL instances are available, what  
properties they have, and what RPL instance IDs map to them.  At some  
level, I would feel more comfortable saying that an app is  
knowledgeable of what kind of services it wants (e.g. deliver this  
packet with low latency).  But note in that last example, 'low  
latency' may mean traversing two separate instances if I have separate  
instances for upwards and downwards routes.  Another concern may be  
for provisioning - can/should a router use default routes setup by an  
instance purely intended for downward routing?  At this point, I guess  
I would need to see this fleshed out more to see how this would work...

--
Jonathan Hui

---

From: "Anders Brandt" <[email-masked]>
Date: Thu, 8 Apr 2010 11:31:09 +0200

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On 
> Behalf Of Richard Kelsey
> Sent: Wednesday, March 31, 2010 17:14
> To: Jonathan Hui
> Cc: [email-masked]
> Subject: Re: [Roll] proposal for DAOs in non-caching DODAGs
> 
> > From: Jonathan Hui <[email-masked]>
> > Date: Tue, 30 Mar 2010 19:08:42 -0700
> > 
> > I like the proposal in general, though it does need to be 
> fleshed out 
> > a bit more.
> 
> I have not gone over the draft to see exactly what changes 
> would be required.  If there is enough support for going 
> forward, I will do so.  This is all assuming that we stop 
> supporting mixed mode, which will require its own set of 
> changes to the text.
> 
> > Specifically, this works well in the non-storing case if all nodes 
> > source DAOs to the root so that the root can properly 
> construct paths 
> > back to any individual node that is sending DAOs.  But is there any 
> > desire to allow some nodes not to source DAOs if they don't 
> need to?  
> > If so, we should specify that a node MUST source DAOs as 
> long as they 
> > are forwarding DAOs for descendants.
> 
> The current draft requires that all nodes send DAOs:
> 
>    13.  A node that receives a newly incremented DTSN from a 
> DAO Parent
>         MUST schedule a DAO transmission.
> 
> If we wanted to relax this, then yes, forwarding a DAO would 
> require that the forwarder also send their own DIO.
> 
> > Separately, it might be nice to include a record-route 
> mechanism (not 
> > the same as reverse route stack DAOs) so that nodes that 
> only want to 
> > quickly establish routes can do so without having to 
> possibly wait for 
> > all ancestors to source their own DAOs as well.  I've found that 
> > record-route works really well in short request-response 
> transactions, 
> > especially in cases where you don't want to continuously maintain 
> > downward routing state.
> 
> Yes.  Would record route go in the RPL draft?  I associate it 
> what source route, which apparently cannot be in the RPL draft.

Hm. Since source routing is the lowest common denominator for RPL I sure
expect source routing is going to be in the RPL draft.

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

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 12 Apr 2010 15:39:05 +0200

Hi Richard:

Following up on this proposal and Jonathan's answers, I've been trying
to formulate how the parents up the DAG know that they need to
participate to the source route and send their own DAO indicating their
own parents.

As discussed earlier, one option is that all routers in the network do
send DAOs with their parents, so we're all set. But that falls short in
a number of cases, including P2P where we only want to trace back the
path between A and B. 

Or, we ask the destination to send uncast a DAO to each of its DAO
parent. So each parent knows that it has to send its own DAO and so on
recursively; as soon as a router has at least one child that is a source
route destination then it must send its own DAO information.

What do you think?

Pascal

> From: [email-masked] [mailto:[email-masked]] On Behalf
Of
> Richard Kelsey
> Sent: Sunday, March 28, 2010 11:21 PM
> To: [email-masked]
> Subject: [Roll] proposal for DAOs in non-caching DODAGs
> 
> 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

---

From: "JeongGil Ko (John)" <[email-masked]>
Date: Tue, 30 Mar 2010 19:51:18 -0700

On Mar 30, 2010, at 7:18 PM, Jonathan Hui <[email-masked]> wrote:

>
> On Mar 30, 2010, at 3:38 PM, Roger Alexander wrote:
>> I should be a bit more precise... the Rank is used in the selection  
>> of the
>> parents but the aggregated metric advertised by the Parents plus  
>> that of the
>> local link is what determines the total aggregated path cost. With  
>> the
>> ability of the DIO to carry a Metric Container for either direction  
>> (this
>> may need further specification in the current draft) then even if the
>> metrics are drastically different a node can still determine  
>> aggregate
>> upward and downward path costs and make a choice of Preferred and DAO
>> Parents.
>>
>> Note: With multiple parents the aggregated metric advertised by a  
>> node in
>> its DIO, for either direction, may reflect some average across  
>> parents. I do
>> not believe this is currently defined.
>
>
> I agree with Roger.  Accounting for asymmetric link properties is  
> best done by representing the path cost of each direction separately  
> within the DIO and not by including some path cost in the DAO.  Like  
> building optimal paths to the root, building optimal paths from the  
> root needs to originate from the root itself so that nodes can make  
> more informed decisions when picking DAO parents.  Without any cost  
> information for paths away from the root, a node is blind in  
> choosing its DAO parents.  Utilizing the cost towards the root isn't  
> useful since the reverse cost may have no relation to it.
>

So let me see if I got it correctly. A DIO will contain rank info for  
both down and upwards paths. Right? A node can define it's preferred  
parent list (for both directions) wrt this DIO's rank information? If  
this is the case then I can see how this can work out. I see packet  
formats changing for both DIOs and DAOs here :)

John

> What I like about keeping all path cost information in the DIO is  
> that it allows a choice in whether you utilize separate path cost  
> values for the forward and reverse path or the same path cost value  
> for both directions.  The former case allows paths to optimize for  
> asymmetric link properties but comes at the price of maintaining and  
> communicate more state.  The latter is useful if you want to reduce  
> the cost of maintaining separate cost metrics at the price of  
> selecting the same route for both directions.
>
> --
> Jonathan Hui
>

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 27 Apr 2010 13:10:14 -0400

> Date: Mon, 12 Apr 2010 15:39:05 +0200
> From: "Pascal Thubert (pthubert)" <[email-masked]>
> 
> send DAOs with their parents, so we're all set.

Right.

> But that falls short in

Are there other cases?  I have been waiting for the P2P proposal
to see if this need to be addressed there.

> route destination then it must send its own DAO information.

Before trying to address the issue we need to when and
where it arises.
                                  -Richard Kelsey