Subject: RE: [Ospf-manet] evaluation plan for OSPF MANET

From: "Henderson, Thomas R" <[email-masked]>
Date: Fri, 2 Dec 2005 12:48:30 -0800

> -----Original Message-----
> From: Richard Ogier [mailto:[email-masked]] 
> Sent: Thursday, December 01, 2005 11:43 PM
> To: [email-masked]
> Subject: Re: [Ospf-manet] evaluation plan for OSPF MANET
> 
> Henderson, Thomas R wrote:
> >>
> >Abhay, it is not clear to me how they would interact.  From 
> your recent 
> >smart peering draft (section 4.4):
> >
> >   "If flooding is disabled,
> >   then the relay election algorithm needs to prune 
> neighbors that are
> >   connected via an Unsynchronized Adjacency from our 1-hop and 2-hop
> >   neighbor lists."
> >
> >There seems to be a circular dependency in this process-- 
> relays need 
> >to be elected to disseminate the LSA information that is needed to 
> >determine whether a neighbor is synchronized or unsynchronized 
> >adjacency.  Or are initial relays perhaps deselected and the 
> >adjacencies torn down once more network information is learned?
> >
> 
> The circular dependence that Tom mentioned does not prevent 
> the protocol from working, since a neighbor will by default 
> become adjacent unless the router has received LSA 
> information that indicates there exists a synchronized path 
> to the neighbor.
> (Tom's comment may have implications in terms of performance, 
> but that would show up in simulations.)

Although I agree it probably does not preclude things from strictly
working, I assume that it will preclude things from working as intended;
that is, the graph will end up with many more adjacencies than intended,
because an adjacency will get set up before there is a chance to choose
it as an unsynchronized adjacency.  I am just trying to understand how
(whether) this can be avoided in the implementation.

> 
> Preferably, the flooding process and MPR selection should be 
> independent of the choice of LSAs (partial or full).
> (Tom also mentioned this.)
> This implies that full 2-hop neighbor information (from 
> Hellos) should be used to select MPRs, so that the 2-hop 
> neighbor information does not depend on the choice of LSAs.
> 
> This does not imply that the choice of MPRs must be 
> independent of which neighbors are adjacent, since the 
> selection of adjacent neighbors is independent of the choice 
> of LSAs, assuming that LSAs always contain fully adjacent neighbors.
> So, it is OK to require MPRs to be adjacent neighbors (i.e., 
> to exclude UA neighbors).
> 
> HOWEVER, this will mean that MPRs no longer provide min-hop 
> paths, which implies that LSAs based on MPRs cannot be used 
> for min-hop routing.  (But the min-cost LSAs of OSPF-MDR 
> could be used.)  This could also affect flooding performance, 
> since LSAs will no longer be flooded along min-hop paths.
> 
> Therefore, it seems like it is best to select MPRs based on 
> full 2-hop neighbor information from Hellos, and NOT to 
> confine MPRs and flooding to adjacent neighbors (i.e., not to 
> disable flooding on unsynchronized adjacencies).
> On the other hand, there may also be drawbacks of selecting 
> MPRs independently of adjacencies, so it is not obvious which 
> way is better.  (Note that OSPF-MDR automatically selects 
> adjacencies to be aligned with MDRs.)
> 

I agree with the above analysis.  I don't know what the implications are
(if any) of allowing flooding to occur over the unsynchronized
adjacencies.

If the partial topology is decoupled from the MPRs and the
synchronized/unsynchronized adjacencies, and flooding doesn't care which
type of adjacency, then it seems to me that unsynchronized adjacencies
become merely a means to avoid DB synchronization between two neighbors,
and the partial topology is then just a purely local optimization such
as the min-cost MDR technique looking at the local neighborhood.  I
think that implementing this would be straightforward based on the above
description.  However, the other approach (where flooding requires
normal adjacencies) still seems underspecified to me.

Tom

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

---

From: Richard Ogier <[email-masked]>
Date: Sat, 03 Dec 2005 10:19:57 -0800

Henderson, Thomas R wrote:

>>>Abhay, it is not clear to me how they would interact.  From your recent
>>>   then the relay election algorithm needs to prune neighbors that are
>>>There seems to be a circular dependency in this process-- relays need to
>>>be elected to disseminate the LSA information that is needed to
>>>adjacency.  Or are initial relays perhaps deselected and the adjacencies
>>>torn down once more network information is learned?
>>>

I will try to analyze what happens when a node joins the network.

The new router will discover neighbors via Hellos and will get a
2-WayReceived from each bidirectional neighbor, over the period
of one Hello interval (assuming Hellos are not missed).
So, in a dense network, a new router could get a 2-WayReceived
from 50 neighbors in 1 or 2 seconds.

The new router will become adjacent with the first neighbor it
discovers, and will start database exchange with this neighbor.
If the router finishes database exchange with the first neighbor
before getting a 2-WayReceived from the second neighbor, then the
router need not form any more adjacencies (assuming the LSAs
received from the first neighbor indicate that a synchronized path
exists to all other neighbors). Otherwise, the router may form
adjacencies with several of its neighbors.

To avoid unnecessarily forming an adjacency with a second neighbor,
the router could wait until it is fully synchronized with the first
neighbor before selecting a second neighbor to become adjacent with.
This is a bit awkward, since the router might have to wait a long
time for the first neighbor to become fully synchronized.

Thus, the choice of which neighbor(s) to become adjacent with
is random, depending on the order in which Hellos are sent.
(In OSPF and OSPF-MDR, the router will form an adjacency with
a DR/MDR and BDR/BMDR.)
The router could instead wait for one Hello interval and then
select the neighbor with the largest value of (RtrPri, RID).
(We can call such a neighbor a "parent" as in OSPF-MDR.)
This might help reduce the diameter of the adjacency graph
at the expense of an additional delay.

Now, I would like to describe a mapping or association between
OR/SP (Smart Peering), and OSPF-MDR, in order to compare them.
The association with the parent of OSPF-MDR has already been mentioned.
Consider the adjacency graph of OR/SP, and assume for simplicity
that it is uniconnected (not biconnected).
Each router with a single adjacency is a leaf of the adjacency graph
and its only adjacent neighbor is its "parent".
Each router with more than one adjacency is a backbone router,
analagous to an MDR in OSPF-MDR.
Assuming that MPRs are required to be adjacent neighbors (and are
required to cover only 2-hop neighbors that are adjacent to the MPR),
any selected MPR will be a backbone router, i.e., an MDR.
This mapping between the two approaches might help to analyze the
similarities and differences between the two approaches.

One difference is that in OSPF-MDR, an MDR selects itself and its
adjacent neighbors jointly (at the same time) based on information
from received Hellos, and independently of LSAs.
(This is similar to a DR in OSPF, but is not similar to OR/SP.)
Each MDR Other forms an adjacency with an MDR neighbor (its parent).

One advantage of this is that adjacencies are not selected randomly,
they are selected to be aligned with MDRs (similar to OSPF).
This alignment helps to limit the number of adjacencies, and may
also help to improve flooding performance.
Another advantage is that, since the choice of adjacent neighbors
does not depend on LSAs, it would never be necessary for a new router
to wait for the first neighbor to become fully synchronized before
selecting a second adjacent neighbor (as discussed above).
Also, it is not necessary to modify the LSA to indicate which
neighbors are unsynchronized.  Note that this technique requires
the LS sequence number to be incremented even if the only
change is that an unsynchronized neighbor became fully adjacent
(which means nothing to a non-MANET router that received the LSA).

I have another comment below.

>normal adjacencies) still seems underspecified to me.

If MPRs are based on full 2-hop neighbor info (from Hellos),
and are not limited to adjacent neighbors,
think a choice can still be made regarding the operation of the
pushback mechanism for adjacent vs. non-adjacent neighbors.
In particular, a router can choose to process LS ACKs
only from adjacent neighbors.
I think this is a good idea (and is done in OSPF-MDR), since
each router could receive a huge number of such ACKs from its
neighbors (since each neighbor must ACK each LSA that it receives).
If routers process LS ACKs only from adjacent neighbors,
then an inactive OR can ignore non-adjacent neighbors when deciding
whether to flood an LSA upon expiration of the pushback timer.

BTW, I think the terms "synchronized adjacency" and "unsynchronized
adjacency" are misleading or misused. What do you call a neighbor that
is in state Exchange?  It is called an adjacency in OSPF, but is not
yet synchronized.  That seems to make it an "unsynchronized
adjacency", but that does not agree with Cisco's definition of
"unsynchronized adjacency".

Richard