Re: [Roll] updating DAO caches - a proposal

["Pascal Thubert (pthubert)" <pthubert at cisco.com>]

Hello Roger (and Richard)

I think I'm mostly with you too. 
Need to make sure we're fully on the same page.

Pascal

>-----Original Message-----
>From: roll-bounces at ietf.org [mailto:roll-bounces at ietf.org] On Behalf Of
Roger K. Alexander
>Sent: samedi 21 novembre 2009 19:17
>To: 'Richard Kelsey'; roll at ietf.org
>Subject: Re: [Roll] updating DAO caches - a proposal
>
>Hi Richard,
>
>As indicated below, I would support this proposal as a base for further
DAO
>operation specification.
>
>Roger
>
>> -----Original Message-----
>> From: roll-bounces at ietf.org [mailto:roll-bounces at ietf.org] On Behalf
Of
>> Richard Kelsey
>> Sent: Thursday, November 19, 2009 2:22 PM
>> To: roll at ietf.org
>> Subject: [Roll] updating DAO caches - a proposal
>>
>>
>> Below is an actual concrete proposal for managing DAO
>> caches.  I believe that this would work well when all nodes
>> cache DAOs and when no nodes do so.  It does a reasonable
>> job when only some nodes cache DAOs, although in some
>> situations there will be some superfluous DAOs transmitted.
>>
>> This assumes that DAOs are sent only to the preferred
>> parent.  If DAO are sent to multiple parents the situation
>> becomes more complex.

YES. 

Fanning out does not guarantee multipath opportunities on the way back.
And that creates overload of states.


>> In a network with no DAO caches the new (C) flag is never
>> set.  Whenever a node moves it sends a single DAO that
>> propagates to the root, which stores the nodes new location.

But then its children that are dragged along do not update the root? 

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.

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

>> In a network where all nodes cache DAOs, a node that moves
>> sends the contents of its cache to its new parent.  These
>> propagate up the tree, with each node forwarding on only
>> those prefixes which are new to its cache.  The forwarding
>> stops when it reaches the least common ancestor of the
>> node's old and new locations.
>
>Agreed.

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.

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


Do we agree in this one?

>
>> In a mixed network, nodes with caches and nodes whose only
>> caching ancestor is the root will have the same behavior
>> as above.  A node without a cache will send its own DAO and
>> set the Destination Advertisement Trigger to cause its
>> sub-DAG to send DAOs as well.  The Trigger will propagate
>> downwards causing more DAOs to be sent, but descedents that
>> have a cache will not propagate the Trigger to their own
>> sub-DAG.
>
>Some further refinement may need to be considered. Where nodes maintain
DAO
>caches the triggering of outward routing updates to the sub-DAG is not
>needed unless there has been a change in the path cost from the moving
node

We agree. For all I understand, a node that caches 'absorbs' the D bit;
that is it updates the parent that has set the D bit with its all cache
and does not propagate the D bit. 

Metrics changes are subject to the trickle exponential backoff but that
is a different process. If there is a significant change, the child will
be told by the parent from that process, and either dump its cache (if
it caches) or send its DAO and send a DIO with the D bit set (if it does
not cache).

>to the DAG root, which would then affect connectivity decisions of the
>sub-DAG nodes (one of the traffic reducing benefits of multiple parents
is
>the potential to mute the effect of individual link connectivity
changes).
>For nodes that do not maintain DAO caches, it should be possible to
apply
>the same mechanism since the moving parent node sends a DAO update
towards
>the root updating subsequent outward routes.
>

Hum. I fear that we are back to the 'one hop' source route collection I
discussed above with the root rebuilding the source route recursively. I
hope we are not going that way...

>>
>>                                   -Richard Kelsey
>>
>> ----------------
>> Proposal:
>>
>> Add a new DIO flag:
>>
>>          Destination Advertisements Cache (C): The Destination
>>                Advertisement Cache (C) flag is set when a node below
>>                the DAG root in the successor chain caches DAOs sent
>>                upwards.  DAG roots NUST NOT set this flag.  Nodes
>>                below the root that maintain a DAO cache MUST set this
>>                flag.  Nodes below the root that do not maintain a DAO
>>                cache MUST set this flag to the value received from
>>                their preferred DAG Parent.
>>
>>
>> In 5.10.1.1. replace
>>
>>    A node that modifies its DAG Parent set may set the `D' bit in
>>    subsequent DIO propagation in order to trigger destination
>>    advertisements to be updated to its DAG Parents and other
ancestors
>>    on the DAG.  Additional recommendations and guidelines regarding
>>    the use of this mechanism are still under consideration and will
be
>>    elaborated in a future revision of this specification.
>>
>> with
>>
>>    When a node selects a new preferred parent it MUST send that
parent
>>    a unicast DIO.  If the node maintains a DIO cache the DIO sent
MUST

DAO I presume?

>>    include the prefixes in the DAO cache.  If the node does not
>>    maintain a DIO cache and either the new preferred parent's DIO or
>>    the old preferred parent's DIO has the Destination Advertisements
>>    Cache set, then the node MUST set the Destination Advertisement
>>    Trigger in its own subsequent DIO.
>>


Several things:

- A node should prefer a parent that can cache; If that's generic enough
that should be in the DIO.

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

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

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

Are we on the same line?


Pascal



>>
>>
>> _______________________________________________
>> Roll mailing list
>> Roll at ietf.org
>> https://www.ietf.org/mailman/listinfo/roll
>
>_______________________________________________
>Roll mailing list
>Roll at ietf.org
>https://www.ietf.org/mailman/listinfo/roll