Subject: [Roll] updating DAO caches - a proposal

From: Richard Kelsey <[email-masked]>
Date: Thu, 19 Nov 2009 14:22:25 -0500

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.

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.

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.

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.

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

----------------

---

From: Michael Richardson <[email-masked]>
Date: Thu, 19 Nov 2009 16:31:13 -0500

>>>>> "Richard" == Richard Kelsey <[email-masked]> writes:
    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.

Please confirm... at the least common ancestor, the contents of the
cache change, but nothing is new..?

    Richard> In a mixed network, nodes with caches and nodes whose only
    Richard> caching ancestor is the root will have the same behavior
    Richard> as above.  A node without a cache will send its own DAO and
    Richard> set the Destination Advertisement Trigger to cause its

So, in effect, a node that does not cache, has a cache size of 0, so all
DAOs are always "new"

I think this works.

- -- 
]       He who is tired of Weird Al is tired of life!           |  firewalls  [
]   Michael Richardson, Sandelman Software Works, Ottawa, ON    |net architect[
] [email-masked] http://www.sandelman.ottawa.on.ca/ |device driver[
   Kyoto Plus: watch the video <http://www.youtube.com/watch?v=kzx1ycLXQSE>
	               then sign the petition.

---

From: Michael Richardson <[email-masked]>
Date: Thu, 19 Nov 2009 16:33:31 -0500

Let me add that Richard's preamble text is good, clear discussion that
also belongs in the draft.

--

---

From: Richard Kelsey <[email-masked]>
Date: Thu, 19 Nov 2009 16:47:41 -0500

> From: Michael Richardson <[email-masked]>
> Date: Thu, 19 Nov 2009 16:31:13 -0500
> 

At the least common ancestor the prefixes in the cache do
not change, but the associated next hops do.  Because DAOs
contain only the prefixes, and not the next hops, the least
common ancestor does not need to send a new one.

                               -Richard Kelsey

---

From: "Roger K. Alexander" <[email-masked]>
Date: Sat, 21 Nov 2009 13:16:53 -0500

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

Agreed.

> have a cache will not propagate the Trigger to their own

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

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

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 23 Nov 2009 16:06:18 +0100

Hello Roger (and Richard)

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

Pascal

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

YES. 

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

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

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

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?

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

>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

DAO I presume?

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

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 23 Nov 2009 11:19:40 -0500

> Date: Mon, 23 Nov 2009 16:06:18 +0100
> From: "Pascal Thubert (pthubert)" <[email-masked]>
>
> 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.
> 

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.

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

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

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

> up there if that yields no difference that requires informing its own

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

                                   -Richard Kelsey

---

From: "Pascal Thubert (pthubert)" <[email-masked]>
Date: Mon, 23 Nov 2009 20:44:20 +0100

Hi Richard

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

>I wasn't proposing otherwise.

I figured it made sense that you would :)

>There may be be redundant routes.

Aie, I did not have that in mind; should we support that?

>sequences may also be correct, but they are redundant

If we support the above. I thought we would not do transit but just
stub.

>that is not already cached on the root, so it is wasteful

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.

>number might work.  I'll have to think about it.

If the sequence nb has also an id of the cache

>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

>especially in the case where the only the root stores DAOs.
Yes, I see what you have in mind now; Would work.
We need to better understand all the pro/cons.

cheers

---

From: Richard Kelsey <[email-masked]>
Date: Mon, 23 Nov 2009 15:51:27 -0500

> Date: Mon, 23 Nov 2009 20:44:20 +0100

Pascal,

I have to consider your response to my proposal.  For
now I will just respond to points you made about DAOs
in the current draft.

> >> destination. Thus there can be only one route to a destination. Thus
> >> if 2 children advertise a same destination, one is wrong.
> >

We do not prohibit it, which I would think means that we
support it.  I don't care one way or the other.

> there is a service interruption till the next

If DAOs are sent repeatedly, what is the purpose of the `D'
destination advertisement bit?  Is it just to synchronize
the sending of new DAOs rather than waiting for them to be
sent?

Also, in -04, section 5.9.1.3. says:

   When sending a destination advertisement to a DA parent, a node
   includes the DAOs for prefix entries not already reported (since the
   last DA Trigger from an DIO message) in the Reachable and Connected
   lists, as well as no-DAOs for all the entries in the Unreachable
   list.

This indicates that a new DAO only includes new information.
Prefix entries sent in an earlier DAO are not included in a
later one.
                                      -Richard Kelsey