Subject: OSPF WG Meeting Presentations and Minutes

From: Acee Lindem <[email-masked]>
Date: Wed, 9 Nov 2005 21:11:00 -0500

The link  below contains the OSPF WG presentations and minutes. If you
have corrections how you were quoted in the minutes - please unicast 
them to me.
Note that I've intentionally cross-posted the Manet IETF list.

https://datatracker.ietf.org/public/meeting_materials.cgi?meeting_num=64

---

From: Richard Ogier <[email-masked]>
Date: Sat, 19 Nov 2005 09:07:51 -0800

All,

Please see my comments below, in the context of the OSPF minutes.
Comments made at a WG session can be misleading, and there is often
not enough time at the meeting to present opposing viewpoints.
I am posting this message for this reason, and to help people
understand OSPF-MDR better.
I am posting this to both the OSPF and MANET lists.
(There is some overlap with my previous post to the OSPF list, but I
tried to give fewer opinions and more supporting facts this time.)

 >            OSPF WG IETF 64 Minutes
 >            Scribes: Padma Pillay-Esnault and Acee

(snip)

 >   - MANET Extension of OSPF Using CDS Flooding (Refer to presentation)
 >      Phil Spagnolo

 >     Fred Baker: What is inherently broadcast about a MANET? Frame 
relay is a
 >        prime example of a network that was initially incorrectly 
modeled in
 >        OSPF.

 >     Tom: No optimizations in MDR that are specific to broadcast.
 >        Broadcast capabilities will be exploited if available.

I also recall that Fred Baker mentioned that OSPF has a problem when
the DR and Backup DR are separated by an obstacle. This may be true
for (unmodified) OSPF, but OSPF-MDR is an extension of OSPF that has
been shown to perform well in MANETs, so this comment does not apply
to OSPF-MDR.

In a fully connected MANET, OSPF-MDR does closely resemble OSPF in
a broadcast network, since both protocols will select the same two
routers as DR/MDR and Backup DR/MDR, and each adjacency has a DR/MDR
or Backup DR/MDR as one of its endpoints. In this sense, OSPF-MDR is
a generalization of OSPF, i.e., an OSPF broadcast network can be
considered a special case of a MANET. But even in a fully connected
MANET, there are a few differences to make OSPF-MDR more robust
(e.g., it selects a 2nd Backup MDR to provide a biconnected
backbone).

 >     Alvaro: MDRs favor adjacency reduction. However, more neighbors 
requires
 >        more time for MDR selection during which time flooding will not be
 >        done. In contrast, MPRs have built-in redundancy during 
transients.

The above statement is miseading.  First of all, the difference that
Alvaro is referring to is a design choice that can be applied to *either*
MDRs or MPRs, i.e., the issue does not favor one core approach over
the other.  In Cisco's solution (draft-chandra-ospf-manet-ext-03) any
neighbor of a router that floods an LSA can potentially forward the LSA
after PushbackInterval).  (Such neighbors are called non-active
overlapping relays or Backup MPRs.)
A similar mechanism could be used in OSPF-MDR, so that any router
could act as a Backup MDR and thus forward a flooded LSA.
SO THIS TECHNIQUE CAN BE USED WITH *EITHER* APPROACH.

The problem with this technique (in both approaches) is that
in a very dense network, there will be a very large number of such
Backup MPRs/MDRs, and even with jitter, a certain fraction of these
will forward the LSA - so the number of neighbors that forward
a given LSA will be proportional to the node degree - as a result,
the flooding overhead is no longer linear in the number of nodes
and the protocol is no longer scalable.

One might argue that we don't need to support more than about 50
neighbors, but as a design principle I prefer to maintain scalability
and ensure that the overhead is (approximately) linear in the number
of nodes.

The way this is done in OSPF-MDR is to select MDRs and Backup MDRs,
to form a biconnected backbone that is used both for flooding
and for defining adjacencies (same as OSPF).
This is done in O(d^2) time, just as MPRs (active overlapping relays)
are selected in O(d^2) time, where d is node degree.
The criticism seems to be that flooding will not be done if two
(Backup) MDRs fail at the same time, until a new MDR is selected.

1. First of all, the probability of this happening is small,
and in fact it usually takes the failure of more than
two (Backup) MDRs to partition the biconnected backbone
(because MDRs are selected based on local information, so
there is usually more than biconnected redundancy).
I.e., the event that the backbone becomes partitioned
is a rare event.

2. Second, in the rare event that the backbone becomes
partitioned, a new MDR will be selected within a few
seconds, based on 2-hop information from Hellos.
How detrimental is it to experience a few seconds delay
(in flooding LSAs) on rare occasions?

The important question is, whether or not you believe the
above claims, how does OSPF-MDR perform in mobile networks?
So far, it seems to perform as well as MPRs in terms of
delivery ratio.  If there is a problem with robustness,
it should show up in the delivery ratio.

And as I mentioned, if necessary, the technique of allowing
any router to be a Backup MDR *could* be employed.  But I
don't think it will be necessary or beneficial.

 >     Tom: Both algorithms have comparable costs with respect to selection.
 >
 >   - High Mobility Scenarios with MPRs and MDRs (Refer to presentations)
 >      Stan Ratliff

Here, I will just summarize my comments regarding Stan's simulation
results that I previously posted on the OSPF list.  First of all,
Stan compared MPRs with Smart Peering, which creates a 1-connected
adjacency graph, to the *biconnected* version of OSPF-MDR, which is
not a fair comparison.  For fairness, it should be compared to the
1-connected version of OSPF-MDR.  Second, the routes obtained with Smart
Peering were much longer than the ones obtained with OSPF-MDR, which
should not be the case since both methods use full LSAs and thus should
produce min-hop paths. This and other anomalies in the simulation
statistics indicate that there is probably a bug.  Also, the simulations
emphasized sparse networks - I think that performance should also be
compared in dense networks.  Anyway, I'm sure that future simulations
will provide a fair comparison.

Richard

 >     Tom: What is the timetable for the release of the code and draft 
update?

 >          Random wavepoint is normally the worst case and most agressive
 >          scenario.

 >          What is the evolution of adjacencies as smart peering is 
used over
 >          time?

 >     Acee: Draft and code should be available within week or so after 
IETF.

 >     Russ: Mobility has two components - range and area. What is the 
spareness
 >           of the topology?

 >   - OSPF Link Local Signalling as Standards Track (Refer to presentation)
 >      Acee Lindem