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

From: Roger Alexander <[email-masked]>
Date: Sun, 29 Nov 2009 22:37:20 -0500

On Nov 23, 2009, at 12:44 PM, "Pascal Thubert (pthubert)" <[email-masked] 
 > wrote:

> Hi Richard
>
>>>
>>> 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.
>
> One would be the massaging; It is easier for the node that caches to
> just store the source route info with the destination and not care  
> about
> the path as you do here. But then, obviously there's a waste. Your
> proposal saves a lot of bandwidth.
>
> Another could be the sequence. DAOs can be out of sequence because  
> they
> are cached. This is why DAOs have a sequence in the first place, an  
> old
> sequence must not overwrite a newer one. Cache do not propagate source
> route so that's less of an issue. Still an info might pass another  
> one.
> How can we be sure that F->G->C is newer than A->B->C->D->E. Should we
> really do F->G->C->D->E?
>
> If we compare your proposal with what I thought I understood from  
> you at
> some point. Say that the source route DAOs are in the form E-via-D, so
> you end up with D-via-C etc... Then the nodes that do not cache just
> forward the bubbles unchanged up to the cache. One advantage is that
> each info can have its own sequence. Another is that when E' and E"  
> both
> children of D send their own source route, there's no need to repeat  
> the
> information for A->B->C->D.
>
> From your algorithm, things become, nodes send a DAO to their parent
> with self as destination and a new sequence each time.
> - If the parent caches, then it set a route down via the source of the
> DAO, caches, and later resend a DAO with the same destination as if it
> owned the destination. Such process could recurse to the top if all
> nodes cache, that's the normal DAO processing.
> - if the parent does not cache (say D->E, D does not cache), then D
> places 'viaD' in E's DAO. The DAO then flies unchanged up to the  
> cache.
> - when the cache gets a DAO with a viaD information, it stores it
> together with the destination. During the route lookup, it will
> reassemble the via informations into a Routing header. The cache
> advertises all destinations as if it owns them and it hides that E  
> has a
> via, so in its DAO.
>
> Flies?

Yes it is also consistent with the vision of a model in which the DAO  
update process works uniformly independent of whether nodes maintain  
or do not maintain state.

>
>>
>>> I'll continue with the assumption that the Reverse Route
>>> Stack contains multiple hops.
>>
>> I wasn't proposing otherwise.
>
> I figured it made sense that you would :)
>
>
>>> 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.
>
> Aie, I did not have that in mind; should we support that?
>
>
>
>>> 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.
>
> If we support the above. I thought we would not do transit but just
> stub.
>
>
>>> 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.
>
> Makes more sense with your
> 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 did not expect that behavior.
>
>>> - 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.
>
> If the sequence nb has also an id of the cache
>
>
>> 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.
>
> DAOs are repeated over and over. If one indicating a change is missed,
> there is a service interruption till the next
>
Also any loss of a diverse outward segment would be corrected with  
subsequent updates.

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

I think this may be part of the tradeoff of stateless node existence.

> Yes, I see what you have in mind now; Would work.
> We need to better understand all the pro/cons.

Yes.

> cheers
>>                              -Richard Kelsey