Subject: [OSPF] OSPF-MDR and MPR-OSPF

From: Richard Ogier <[email-masked]>
Date: Fri, 16 Mar 2007 14:24:08 -0800

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-masked]
https://www1.ietf.org/mailman/listinfo/ospf

---

From: "Stan Ratliff \(sratliff\)" <[email-masked]>
Date: Fri, 16 Mar 2007 17:42:55 -0400

Please allow me to also submit my opinion, since I won't be 
attending next week as well. 

Having made the decision to go with experimental drafts, I 
see no need to place the restrictions Richard proposes on 
the drafts, or to limit the number of drafts to only two. As 
was mentioned in San Diego, we should pursue multiple 
experimental drafts, *and let the marketplace decide which
approach is superior*. Halting an avenue of potential 
research at this juncture seems premature to me. 

So, I vote for 3 experimental proposals, and may the 
best approach win in the market. 

Regards,
Stan

>-----Original Message-----
>From: Richard Ogier [mailto:[email-masked]] 
>Sent: Friday, March 16, 2007 6:24 PM
>To: [email-masked]
>Subject: [OSPF] OSPF-MDR and MPR-OSPF
>
>All,
>

---

From: Acee Lindem <[email-masked]>
Date: Fri, 16 Mar 2007 18:12:11 -0400

Hey Guys,
At the risk of being drawn into a protracted discussion, I'd agree  
that the WG is on the path of multiple experimental drafts. While  
experimental status will not carry the same consensus and stability  
requirements as standards track, any document we publish as a WG  
document will need to be reviewed and endorsed by the WG.  
Additionally, the experimental drafts should be different enough to  
offer alternative approaches - we certainly don't want more drafts  
which are slight variations of the ones being proposed.
Thanks,
Acee

---

From: Richard Ogier <[email-masked]>
Date: Sat, 17 Mar 2007 16:36:50 -0800

> which are slight variations of the ones being proposed.

Yes, I think the two MPR-based proposals are very similar
and easily mergeable.  Ciscos's OSPF-OR draft does not
yet include LSA reduction, but since INRIA's MPR-OSPF draft
achieves LSA reduction based on "path MPRs", it would be easy
to employ this method in OSPF-OR.

Given this, OSPF-OR and MPR-OSPF become very similar proposals, both
using MPR flooding and LSA reduction based on path MPRs.
The main difference would be two different methods for adjacency
reduction, but these can be considered two different options,
or it can be decided which method is preferable.

I don't think it makes sense to have two very similar MPR-based
proposals for extending OSPF to MANETs.
Therefore, I would like to request that a vote be taken to
determine whether the WG would rather have:

(a) A single experimental WG draft for the MPR-based approach
    to OSPF-MANET, which combines methods from Cisco's draft
    and INRIA's draft, or
(b) Two separate (but similar) experimental WG drafts for the
    MPR-based approach to OSPF-MANET.

Another issue, which I discussed in my last message, is that
MPR-OSPF has not yet been shown to achieve approximately
the same performance as OSPF-MDR.  This might be another
reason to choose (a) instead of (b) above.

Richard

>>> http://www1.ietf.org/mail-archive/web/ospf-manet/current/ msg00372.html
>>>
>>> http://www1.ietf.org/mail-archive/web/ospf-manet/current/ msg00376.html
>>>

---

From: Richard Ogier <[email-masked]>
Date: Sat, 24 Mar 2007 16:38:21 -0800

First, I have a question about Emmanuel's presentation.
https://datatracker.ietf.org/public/meeting_materials.cgi?meeting_num=68

On the slide that presents simulation results for 60 to 100 nodes,
it says velocity = 3 m/s.  Is this really the maximum node speed?
Or should it be 30 m/s?  I think that 0.934 is a low delivery
ratio for 3 m/s.   Also, what Hello Interval did you use for this
simulation?

I think it is ironic that nobody commented that INRIA's solution is not
robust.  Let me explain.  Chandra's draft uses the pushback timer and
non-active ORs (which I will call backup MPRs) to achieve robustness.
About two years ago, several people from Cisco criticized OSPF-MDR for
not being robustness enough, since its Backup MDRs only guaranteed
biconnected coverage, whereas any router can be a backup MPR.
(I always claimed that one must limit the number of backup relays to
achieve scalability, and later Cisco did this by selecting parameters in
a way that ensured only a small percentage of backup MPRs would fire.)
Simulations consistently showed that OSPF-MDR was as robust as OSPF-OR,
implying that biconnected coverage is sufficient (along with the ability
to respond quickly to topology changes).

So it is ironic that is that nobody commented that INRIA's solution is
not robust, even though it does not use *any* backup relays, nor does
it propose any sort of redundancy in relays or adjacencies.
INRIA's is the ONLY proposal that doesn't try to achieve robustness
through redundancy.  (Maybe they plan to add this later?)
This may partly explain why MPR-OSPF achieved a much lower
delivery ratio than OSPF-MDR in the simulation results I posted
earlier, but I suspect that the choice of LSAs and the fact that MDRs
are self-selected (thus allowing faster response to topology changes)
are also factors.

Now, I want to comment on the similarity between MPR-OSPF and OSPF-OR,
since Acee commented at the meeting that the two proposals are very
different.  My point is that the two proposals are easily mergeable,
and that the only difference in *corresponding* methods are the methods
for adjacency reduction.

The three differences below are methods that are used by one of
the proposals, for which a corresponding method does not exist in
the other proposal, but can be used by the other proposal:

1. For robustness, OSPF-OR uses backup MPRs (non-active ORs),
but the same technique can easily be used by MPR-OSPF.
(MPR-OSPF does not yet have *any* method for achieving
robustness through redundancy.)

2. MPR-OSPF uses multicast LSA retransmissions, and this can
easily be used by OSPF-OR.

3. MPR-OSPF uses path-MPR-based LSAs, and this can easily
be used by OSPF-OR.  In fact, OSPF-OR does not yet propose
any method for LSA reduction, so by default this is the
method that would be used.

Now, I hope you see what I mean.
I guess the question is why the two MPR teams cannot get together
and agree on a single solution based on MPR flooding.
Based on my points above, this should not be very difficult to do.
But of course, if they cannot agree, then the two MDR proposals
cannot be merged. I was just trying to encourage such a merging.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Mon, 26 Mar 2007 09:13:27 -0800

> ratio for 3 m/s.   Also, what Hello Interval did you use for this

It occurred to me that the transmission range was not given, so
the 0.934 delivery ratio could be due to temporary network partitions.
Still, in order repeat the experiment and understand the results,
we need to know the range as well as the parameters such as
HelloInterval and RxmtInterval.  Can you provide these?

Richard