-----Original Message-----
From: Richard Ogier [mailto:[EMAIL PROTECTED]
Sent: Friday, March 16, 2007 6:24 PM
To: [email protected]
Subject: [OSPF] OSPF-MDR and MPR-OSPF
All,
I see that INRIA is presenting their updated draft for MPR-OSPF:
draft-baccelli-ospf-mpr-ext-03.txt
There is also an updated draft for OSPF-MDR:
draft-ogier-manet-ospf-extension-09.txt
The main changes are that the BMDR algorithm has been simplified and
the min-cost LSA algorithm has been modified to ensure that neighbor
advertisement is symmetric. Another update will be submitted before
the next IETF meeting in July, mainly to improve readability.
Since I won't be at the meeting on Monday, and since MPR-OSPF
and OSPF-MDR are competing proposals for the MANET extension of
OSPF, I thought it would be good to post my views here.
In my opinion, MPR-OSPF should not be accepted as an experimental
WG draft unless it can be shown to achieve approximately the same
(or better) performance and scalability as OSPF-MDR. So far,
this has not been shown.
Also, MPR-OSPF appears to be an extension of Cisco's OSPF-OR
solution,
with both solutions using MPR flooding. I don't think we should have
two MPR-based extensions of OSPF. We should be able to restrict to
two drafts: one based on MPR flooding, and one based on CDS/MDR
flooding. MPR-OSPF seems to offer two techniques that are not
included in OSPF-OR: LSA reduction and multicast retransmitted LSAs.
These two techniques can be added to OSPF-OR.
So, I suggest that OSPF-OR (with these added techniques) be compared
to MPR-OSPF; the better of these two solutions should then become
an experimental WG draft.
There seem to be four main issues regarding OSPF-MDR versus MPR-OSPF:
1. Performance, including overhead, scalability, and delivery ratio.
(Note that delivery ratio reflects robustness when routers are
mobile and frequent topology changes occur).
2. Maturity.
3. Simplicity.
4. Whether it is important for all links of a route, except the
first link, to be synchronized.
The 4th issue seems odd, especially since it is not clear why only
the *first* link need not be synchronized, but this is something that
INRIA has brought up repeatedly. In OSPF, any link of a route need
not be directly synchronized (Full) if the two routers are connected
via a broadcast network. But *all* links of a route (including the
first) must at least be *indirectly* synchronized, which OSPF-MDR
ensures, but MPR-OSPF does not.
In any case, the effect of this choice will be reflected in the
performance results, so we should compare the performance results.
If OSPF-MDR does not have enough synchronized links, then this should
be reflected in delivery ratio when routers are mobile. But so far,
simulation results have shown that OSPF-MDR has a much better
delivery ratio than MPR-OSPF.
On the ospf-manet list, I recently posted some simulation results
comparing OSPF-MDR to MPR-OSPF in networks with up to 100 nodes:
http://www1.ietf.org/mail-archive/web/ospf-manet/current/
msg00372.html
To summarize, these results show that OSPF-MDR generates much less
overhead (especially in larger networks) and provides much better
delivery ratios than MPR-OSPF. For 100 nodes, the delivery ratio
was 84% for MPR-OSPF vs. 93% for OSPF-MDR, with MPR-OSPF generating
almost twice as much overhead.
Regarding maturity, I believe (and I know some others agree) that
INRIA's maturity argument is weak because, although MPRs have been
around for several years, CDS-based flooding has been around since
the 1980s. (In fact, the Designated Router is a special case of a CDS
for broadcast networks.) And the application of MPR adjacency
reduction
for extending OSPF to MANETs is relatively new, no more mature than
applying a CDS to extend OSPF. For example, INRIA did not realize
until their latest draft update that a router must indicate to its
neighbors (in Hellos) whether it is a "synch router" (the new S bit
is used for this).
Also, the rule for selecting synch routers has changed in the
latest draft update, and still does not ensure that all routers are
connected via synchronized links when routers have multiple MANET
interfaces, as I recently discussed on the ospf-manet list:
http://www1.ietf.org/mail-archive/web/ospf-manet/current/
msg00376.html
Finally, I will discuss the issue of simplicity. The draft for
OSPF-MDR is longer than the draft for MPR-OSPF, but it contains
more options (e.g., differential Hellos, non-ackable LSAs,
biconnected adjacencies, etc.) and more details (e.g., changes in the
state machines, more precise rules for when to become adjacent, more
details for processing Hellos and maintaining neighbor data, etc.).
For example, INRIA's draft states that synch routers must set the S
bit in Hellos, but does not yet say how this bit should be processed
in a received Hello.
The rest of this message will argue that OSPF-MDR is not
significantly
more complex than MPR-OSPF. Even if it is a little more complex,
its superior performance more than makes up for this.
First, the MPR selection algorithm is no simpler than the MDR
selection
algorithm (which uses a depth-first search algorithm to find paths
from one neighbor to all other neighbors). The selection of
Backup MDRs is analogous to the selection of backup/redundant MPRs,
which is specified in OLSR (RFC3626) but not yet in MPR-OSPR.
The selection of Backup MDRs is optional (to be clarified in the
next draft update), but improves robustness, as would be the case
for backup/redundant MPRs. (Also note that the BMDR algorithm has
been simplified in the latest draft update.)
Just as MPRs are advertised in Hellos, OSPF-MDR advertises dependent
neighbors in Hellos; in both cases, these are neighbors that become
adjacent. However, if adjacency reduction is not used, OSPF-MDR does
NOT need to advertise dependent neighbors in Hellos, which makes it
simpler than MPR-OSPF.
(The simplicity of OSPF-MDR when adjacency reduction is not
used will be made clear in the next draft update.)
For the selection of neighbors to advertise in LSAs, MPR-OSPF
selects "path MPRs", while OSPF-MDR selects SANs (Selected Advertised
Neighbors), both of which are reported in Hellos using an LLS TLV.
Also, both protocols advertise link costs/metrics in Hellos using
an LLS TLV, except that MPR-OSPF must include twice as many
link costs (forward and reverse costs), since the selection of
path MPRs requires this additional information.
But the method used for LSA reduction is not really an issue for
comparing OSPF-MDR to MPR-OSPF, since OSPF-MDR can use either method
for LSA reduction (e.g., SANs can be selected to be path MPRs if
this improves performance, although that would require reporting
reverse link costs in Hellos).
Therefore, OSPF-MDR is not significantly more complex than MPR-OSPF.
Even if it is a little more complex, that would be justified
by the much better performance. As I mentioned above, I think
MPR-OSPF should be accepted as an experimental WG draft only
if it can be shown to achieve approximately the same or better
performance and scalability as OSPF-MDR. So far, simulation
results indicate that this is not the case.
Richard
_______________________________________________
OSPF mailing list
[email protected]
https://www1.ietf.org/mailman/listinfo/ospf
