Re: [Roll] updating DAO caches - a proposal

[Richard Kelsey <richard.kelsey at ember.com>]

> Date: Mon, 23 Nov 2009 16:06:18 +0100
> From: "Pascal Thubert (pthubert)" <pthubert at cisco.com>
>
> Richard> In a network with no DAO caches the new (C) flag is never
> Richard> set.  Whenever a node moves it sends a single DAO that
> Richard> propagates to the root, which stores the nodes new location.
> 
> But then its children that are dragged along do not update the root? 

Correct.

> That would work only if you use DAO for one_hop
> information and leave it up to the root to rebuild the
> source route.  Please let us know what you have in mind
> here, since that might yield complexities.

Yes, it is what I have in mind.  If the root has
A->B->C->D->E in its cache and then it receives
F->G->C, its route to E becomes F->G->C->D->E.

I do not see where complexities could arise.

> I'll continue with the assumption that the Reverse Route
> Stack contains multiple hops.

I wasn't proposing otherwise.

> Richard> In a network where all nodes cache DAOs, a node that moves
> Richard> sends the contents of its cache to its new parent.  These
> Richard> propagate up the tree, with each node forwarding on only
> Richard> those prefixes which are new to its cache.  The forwarding
> Richard> stops when it reaches the least common ancestor of the
> Richard> node's old and new locations.
> 
> IF we all agree on the above, that is sending only to one preferred
> parent, then there can only be one child that advertises a DAO
> destination. Thus there can be only one route to a destination. Thus if
> 2 children advertise a same destination, one is wrong.

Not necessarily, if the destination is not on the subnet.
There may be be redundant routes.

> The newest sequence in the DAO indicates the one that is
> correct. The other one should be cleaned up.

The newest sequence is assumed to be correct.  Earlier
sequences may also be correct, but they are redundant
and not saved.

> Several things:
> 
> - I fail to see why the DAG root does not set the flag. What happens if
> it is the only one that caches then? It appears that movements do not
> trigger DAOs though the source route path changes.

If the DAG root sets the flag then sub-DAGs have to send
DAOs after every move.  Those DAOs contain no information
that is not already cached on the root, so it is wasteful
to send them.

> - the D bit is not enough. The initial spec has a hash. In multihop
> source route, are you sure the D will propagate without a loss? The hash
> is one of those values that would cause resetting trickle if changed so
> it should propagate efficiently.

This is a good point.  A hash doesn't work for what I am
proposing, because a change in the route to the root does
not necessarily require that a new DAO be sent.  A sequence
number might work.  I'll have to think about it.

As an aside, the DAO mechanism depends on the link layer
being 100% reliable.  If the link layer can lose messages a
number of changes will be necessary.  The ROLL document
needs to be explicit about the link-layer requirements.

> - I think the node that does not cache should send a DAO to its parent
> when the hash in the DIO changes. The hash should start up there at the
> first parent (included) that caches and include the path down the
> preferred tree to this node. So if anything happens between the cache
> and this node, or if the parent that caches changes, this node knows and
> sends a DOA, and propagate the DIO with itself added to the changed
> hash, so the hash changes. IOW if there is a cache up there and if the
> path to that cache or the cache itself changes then this node must send
> a DAO to inform nodes along that path. DAOs can be absorbed by the cache
> up there if that yields no difference that requires informing its own
> parent.

This will again require nodes to send redundant DAOs,
especially in the case where the only the root stores DAOs.

                                   -Richard Kelsey