Subject: RE: [Ospf-wireless-design] Synchronization requirement for including aneighbor in LSA

From: "Henderson, Thomas R" <[email-masked]>
Date: Thu, 31 Mar 2005 13:47:48 -0800

Richard, responses below:

> -----Original Message-----
> From: Richard Ogier [mailto:[email-masked]] 
> Sent: Thursday, March 31, 2005 12:18 PM
> To: [email-masked]
> Subject: [Ospf-wireless-design] Synchronization requirement 
> for including aneighbor in LSA
> 
> All,
> 
> I want to discuss the definition of a "synchronized" neighbor 
> in Section 5 of my draft, and explain why I think this is a 
> good requirement for a neighbor to be included in the router LSA.
> This condition is valid for both full-topology and 
> partial-topology LSAs, so the discussion below applies to either case.
> 
> First, I am assuming that a set of adjacencies has been 
> formed that spans the entire network, so that there exists a 
> (suboptimal) path from each router to every other router via 
> adjacent edges (except temporarily as new adjacencies are 
> formed in response to topology changes).
> 
> Each router will include, at a minimum, each fully adjacent 
> neighbor in its router LSA. This will provide suboptimal 
> routes to each reachable router.
> 
> The question is, what other neighbors can be included in the 
> router LSA?
> 
> Suppose that node i has a non-adjacent, 2-way neighbor j, and 
> that the SPF calculation has calculated a route to node j via 
> a fully adjacent neighbor k. Then node i can route data 
> packets to neighbor j via neighbor k. (Or, neighbor j might 
> not be the final destination, but might be an intermedate 
> node to another destination.) So, instead of using neighbor k 
> as the next hop, why not take a shortcut and forward the data 
> packet directly to neighbor j as the next hop?  This is quite 
> reasonable, and is exactly what the synchronized neighbor rule says.
> 
> Once neighbor j has been declared to be an acceptable next 
> hop (to any destination), it can be included in node i's router LSA.
> 
> Note that this is a generalization of what is allowed in an 
> OSPF broadcast network, which allows a non-DR/BDR i to use 
> another non-DR/BDR j as a next hop as long as both are fully 
> adjacent to the DR.  In a broadcast network, there is no need 
> for node i to include node j in its LSA, since the network 
> LSA originated by the DR already implies this information. 
> But when we generalize to a multihop network, the only way 
> node i can inform other routers that it can forward packets 
> to node j, is to include node j in its router LSA.

I think that this is potentially an important optimization, since,
unlike the OSPF broadcast case, i and j may be more than two hops away
from one another if only adjacencies are traversed.

> 
> A possible concern: What if, after declaring node j to be an 
> acceptable next hop, there temporarily does not exist a path 
> of fully adjacent edges to node j, due to topology changes?
> The above rule does not detect this and does not remove node 
> j as an acceptable next hop (unless node j is no longer reachable).

Won't this event trigger a recalculation of who is serving as DR/BDR
with respect to i and j (that is, either i or j or both will be promoted
to DR status), and therefore this should get resolved automatically?

> 
> The answer is that the protocol will be robust enough (if designed
> properly) to maintain sufficient database synchronization 
> even when topology changes cause old adjacencies to fail and 
> require new adjacencies to be formed.
> 
> The only case where routers may not be acceptably 
> synchronized is when the network partitions, i.e., some 
> destinations become temporarily unreachable.  The above rule 
> will detect this, since it requires a neighbor to be 
> reachable via a current path that has already been determined 
> to be acceptable.

Have you addressed the question of how routers decide which DR/BDR that
they should become adjacent to?  That seems a bit trickier to me than
the above.  Conceptually, your approach has the intuitive appeal that
DRs/BDRs are nodes that attract adjacencies, but a given non-DR node may
have several DRs to choose from: which ones and how many should it
choose?  How are inconsistent selections mitigated (e.g., i wants to
neighbor with j but j does not want to neighbor with i, perhaps because
some adjacency threshold is reached)?

This question also holds for the MPR case, for which it is even less
clear to me how to systematically prune the adjacencies (perhaps just
forming with one's MPRs, but MPR/MPR-selector is an asymmetric
relationship, which may lead to more adjacencies than desired...hmm).

Fred Baker posited this back in 2002 in the "outsider's view" draft, but
we took a look at the concept in our Milcom 2003 paper (with a simple
heuristic) and found that the heuristic that we picked didn't help the
scaling that much (not that this proves anything-- we may have picked a
bad heuristic-- but it is not intuitively clear to me what a better one
might be).

Tom

_______________________________________________
Ospf-wireless-design mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design

---

From: Richard Ogier <[email-masked]>
Date: Thu, 31 Mar 2005 17:18:10 -0800

Tom,

>to DR status), and therefore this should get resolved automatically?
Yes. We agree that this should not be a problem as long as the protocol
is sufficiently robust.

>they should become adjacent to?
>

Yes, the rules for deciding which DR/BDR neighbors to become adjacent
with have been written down and are being implemented.
A non-DR selects a DR as parent (indicated in the DR field of its
Hellos), and a DR/BDR as backup parent (indicated in the BDR field
of its Hellos). These are persistent, e.g., the parent does not
change as long as it is a DR neighbor.

>That seems a bit trickier to me than

Right now we are assuming two (adjacent) parents, which I think
will be sufficient (with the robustness enhancements that I plan
to implement), but simulations will test this.
If a child selects a DR parent, then the DR parent
must form an adjacency with the child, so there is no problem
with inconsistency. There is currently no plan to limit the number
of adjacent neighbors that a DR can have (the worst case is all
neighbors). Note, for example, that the router with the largest value
of (DRLevel, RtrPri, RID) could be adjacent with all of its neighbors,
but will form only one new adjacency each time it gets a new neighbor.

>relationship, which may lead to more adjacencies than desired...hmm).
Yes, that would definitely be more adjacencies than needed
(and is not guaranteed to be connected).
One solution is to use the MPR-based CDS described in the INRIA
report (reference [Adjih02] of my draft), which can work as
follows (using terminology from my draft): A router selects itself
as a DR if its neighbor with largest (DRLevel, RtrPri, RID) has
selected it as an MPR. Then the router can become adjacent with
the MPR selector, and with all other neighbors that are not covered
by the MPR selector. Even this will result in more adjacencies than
needed, but can be improved if each non-DR selects a (persistent)
parent as in my draft. Also, this would not be biconnected - making
it biconnected would double the number of adjacencies and probably
cause the rate of new adjacencies to exceed the number of new edges
for a 50 node network (based on my simulation results for the
case of self-selected MPRs).

The case of self-selected MPRs is the MPN CDS algorithm in my draft
with h = 2. I.e., this is the same as above, except that MPRs are
self-selected.  My simulations show that this method can result
in an average rate of new adjacencies that is significantly less than
the rate of new edges only for 100 nodes (but not 50 nodes) or if
we are satisfied with the set of adjacencies being 1-connected instead
of biconnected.  In other words, it can help, but is not as efficient
as using the Essential CDS algorithm.  I plan to run simulations
with the MPN CDS algorithm, with h = 2 and h = 3 (this just involves
changing a parameter in the Essential CDS algorithm).

Richard

---

From: Richard Ogier <[email-masked]>
Date: Thu, 31 Mar 2005 20:38:51 -0800

Tom,  I have a few more comments below.

<snip>

>some adjacency threshold is reached)?

If it is found to be necessary for a non-DR to become adjacent with more
than two DR/BDRs, then a natural alternative solution is to simply have
each DR become adjacent with each dependent neighbor (including non-DR
neighbors). (This was the original solution before I thought of the
"persistent parent" optimization.)
This can still be a good solution - the fact that DRs are persistent
make the adjacencies fairly stable.
But to avoid too many adjacencies, I would not require
"backup dependent neighbors" to be adjacent (at least for non-DRs).

Having each non-DR be adjacent with each DR/BDR neighbor that selects
it as either a dependent neighbor or a backup dependent neighbor
is analogous to having each router be adjacent to not only its MPRs
but also to its backup MPRs. As we have discussed, even being adjacent
with all MPRs is probably too much. The Essential CDS algorithm will
result in fewer adjacencies than if all MPRs were adjacent.
(The latter would be equivalent to the ANP CDS algorithm with h = 2.)

Even if we drop the biconnectivity requirement, each non-DR will likely
be adjacent to more than two DRs, for the same reason that a router
usually has more than two MPRs.  But more importantly, the adjacent
DRs will be more "spread out", so that each 2-hop neighbor will
likely be reachable in at most 3 hops via DRs.

Anyway, I plan to experiment with the above variation when
running simulations.

Richard