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

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

Hi Pascal, Richard, others,

On Nov 23, 2009, at 7:06 AM, "Pascal Thubert (pthubert)" <[email-masked] 
 > wrote:

> 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: [email-masked] [mailto:[email-masked]] On  
>> Behalf Of
> Roger K. Alexander
>> Sent: samedi 21 novembre 2009 19:17
>> To: 'Richard Kelsey'; [email-masked]
>> 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: [email-masked] [mailto:[email-masked]] On Behalf
> Of
>>> Richard Kelsey
>>> Sent: Thursday, November 19, 2009 2:22 PM
>>> To: [email-masked]
>>> 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.
>
>

Indeed multiple parents do not guarantee diverse outward end-to-end  
paths but it improves the potential.

The use of just a single (acknowledged) parent should be left as an  
implementation choice (note that nodes can also maintain state for  
other non-acknowledged parent nodes without sending DAO updates to  
those nodes). Multiple parents need to be supported as part of the  
core RPL specification.

>>> 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 specification should allow nodes to be able to maintain multiple  
(acknowledged) parents.

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

Yes. Furthermore, with multiple parents the given sequence number  
associated with the update will ensure that updates arriving on  
different paths allow a common ancestor to maintain multiple forward  
(outward) routes. Note, delays or loss of DAO updates on different  
paths to the common ancestor can lead to temporary elimination of  
segments of the potential multiple outward paths.

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

Agreed.

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

The root or other state-maintaining node would be capable of  
rebuilding the source route recursively. For 'mixed' node  
environments, other stateful nodes will need to support this  
processing as well.

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

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

Yes. I think this may be part of the tradeoff for a stateless node. A  
node that maintains state will send a DIO on its sub-DAG only if there  
is a cost change to the root.

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

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 30 Nov 2009 14:53:27 +0100

Hi Roger and Richard:

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) ?

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

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

Pascal

>From: Roger Alexander [mailto:[email-masked]]
>Sent: lundi 30 novembre 2009 04:18
>To: Pascal Thubert (pthubert)
>Cc: Richard Kelsey; <[email-masked]>
Behalf

---

From: "Roger K. Alexander" <[email-masked]>
Date: Mon, 30 Nov 2009 18:44:14 -0500

Hi Pascal,

General agreement. Thanks.

Roger

> From: Pascal Thubert (pthubert) [mailto:[email-masked]]
> Sent: Monday, November 30, 2009 8:53 AM
> To: Roger Alexander; Richard Kelsey
> Cc: [email-masked]; [email-masked]
> Subject: RE: [Roll] updating DAO caches - a proposal
> 
> Hi Roger and Richard:
> 

Agreed. This could be in the form of a DIO with Ack indicator.

Agreed.

> parents, details left out.

Agreed. More generically, "a node MAY send the DAO to multiple parents". In
any event, there may not always be multiple candidate parents.

Agreed. 

> only the destination and sequence set by the originator.

Agreed. The sequence number must be as set by each originator. This will
allow a common ancestor to maintain diverse outward routing entries where
applicable and similarly purge outdated entries as needed.

OK.

> parent dumps its DAO info.

OK. This will allow for some recovery of lost DIOs. However the D bit
setting of the lost DIO is not recovered.
 
> If the node does not cache all DAOs or if
> the

I need to give some further thought to the final mechanism. Thanks.

---

From: JP Vasseur <[email-masked]>
Date: Tue, 1 Dec 2009 08:33:47 +0100

Hi,

Looks good. I had a proposal for the DAO packing - let me send it to  
the list for discussion.

Thanks.

JP.