Subject: Re: [Roll] updating DAO caches - a proposal

From: Richard Kelsey <[email-masked]>
Date: Tue, 01 Dec 2009 10:09:48 -0500

> Date: Mon, 30 Nov 2009 14:53:27 +0100
> From: "Pascal Thubert (pthubert)" <[email-masked]>
> 
> For R05 I think we will not have time to converge on source route. 
> I'll make a separate thread for R05 for the common pieces.
> 
> This thread is about source route so I keep it this way. 
> 
> To integrate source route I think that we'll need to convert the routing
> header in a string of shorter tags.
> 
> Here's how that could happen:
> 
> - ack the DAO. What about a DA Confirm (DAC) ?

Acking the DAO seems like a partial patch.  What is
needed is an ack from the caching node, not from one's
immediate parent.

> - Multiple destination info may be piggy backed (BNF?)
> 
> - DAO Originator and caching parent MAY send the DAO to multiple
> parents, details left out. 
> 
> - A parent keeps track of its children. For each child, it maintains the
> tag that points onto the child and associated to that, the link local
> and the (destinations, originator sequence) for destinations owned by
> that child. This is done to aggregate multiple destinations in one
> messages, enable no-DAOs, etc...
> - a caching parent also keeps track of destinations. For those
> destinations, it maintains the tag that points onto the next_hop child
> and associated to that, the link local and the (destinations, originator
> sequence) for destinations owned by or reachable via that child.
> 
> - A DAO emitted by the Originator node and a caching parent contains
> only the destination and sequence set by the originator. 
> - A parent that propagates a DAO without caching it adds a local tag
> that points onto the child (see that as a locally significant
> compression of the child LLA, or an index on that child). 

That tag of yours sure looks like a label.  If we are going
to use labels I think that they need to be in a separate
document.  Either that or we should integrate the use of
labels into all of RPL.

> - A Node that sends DIOs maintains its own cache_sequence that it places
> in the DIO. The sequence is increments to request the children to send
> their DIOs. 
> - A child that changes its parent or gets a new cache_sequence from its
> parent dumps its DAO info. If the node does not cache all DAOs or if the
> D bit is set then the node needs to update its own cache_sequence, and
> propagate the DIO with the same setting of the D bit.
> 
> What do you think?

RPL is starting to look schizophrenic.  On one hand we have
the DAG mechanism which, especially with local repair, aims
to make it as cheap as possible to react to changes in the
topology.  On the other hand we have the DAO mechanism which
maintains a distributed route database and where a single
DAG link change can trigger widespread updates.  How likely
is it that topology changes will be common enough that we
need fast local DAG repair and also rare enough that the
resulting DAOs successfully maintain the downward routes
without swamping the network with control messages?  We
are in danger of painting ourselves into a corner.

                             -Richard Kelsey

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Tue, 1 Dec 2009 17:04:54 +0100

Hi Richard

>needed is an ack from the caching node, not from one's

Hop by hop you get some degree of recovery. The ack also enables the
parent to Nack.
This could happen for multiple reasons, like out of memory, or
security/policies

>document.  Either that or we should integrate the use of

This is more like a locally significant compression of the next hop Link
local address.

The term label is encumbered with MPLS, and seems to imply a lot more
than we do here, like LDP, switching...  Maybe in some future we'll
integrate more "real" labels, but we're far from doing that here.

>are in danger of painting ourselves into a corner.

Good question that applies to DAO in general not just this mechanism :) 
You'll note that the string of tags could be refreshed not only in DAOs,
but with traffic if such thing is needed. That would adapt what's most
needed to fast changes.

Pascal

---

From: Richard Kelsey <[email-masked]>
Date: Tue, 01 Dec 2009 21:50:09 -0500

> Date: Tue, 1 Dec 2009 17:04:54 +0100

If we do use labels, why only use them a little bit?  We
need to maximize the utility of whatever mechanisms we have.
It really seems like we are piling on patch after patch and
losing sight of the big picture.

> Richard>RPL is starting to look schizophrenic.  On one hand we have
> Richard>the DAG mechanism which, especially with local repair, aims
> Richard>to make it as cheap as possible to react to changes in the
> Richard>topology.  On the other hand we have the DAO mechanism which
> Richard>maintains a distributed route database and where a single
> Richard>DAG link change can trigger widespread updates.  How likely
> Richard>is it that topology changes will be common enough that we
> Richard>need fast local DAG repair and also rare enough that the
> Richard>resulting DAOs successfully maintain the downward routes
> Richard>without swamping the network with control messages?  We
> Richard>are in danger of painting ourselves into a corner.
> 

To some extent yes, but it doesn't apply to all DAO
mechanisms equally.  For example, sending plain record
routes, either periodically or on demand, would have much
less interaction with DIOs and DAG changes and would have a
much more predictable behavior.

                              -Richard Kelsey

---

From: Jonathan Hui <[email-masked]>
Date: Thu, 3 Dec 2009 10:32:35 -0800

> losing sight of the big picture.

Agree.  In general, if we have an end-goal in mind, I'd much rather  
design for that end-goal than patch our way to it.  In the end, if we  
want to use "labels" (which I think is a useful path to explore  
thoroughly for a number of reasons), then we should at least agree on  
what the solution will look like even if it is not specified in the  
core RPL spec.

> much more predictable behavior.

I also believe that DIO and DAO mechanisms should be decoupled.  The  
coupling in small scale networks doesn't matter much.  Global  
coordination in large scale networks is challenging.

--
Jonathan Hui