Subject: OSPF-MDR (Manet Designated Routers)

From: Richard Ogier <[email-masked]>
Date: Tue, 8 Nov 2005 20:06:50 -0800

Folks,

I was listening to the OSPF session today from my office,
and would like to make some comments and answer some
questions regarding OSPF-MDR (Manet Designated Routers).

I will address the comments/questions from Fred Baker and the
person who explained that MPRs can be selected in zero time :-)
and will then comment on the simulations presented by Stan.

First I want to make an observation.  The people who favor OSPF-MDR
are the ones who took the time to understand it well.
Therefore, it is important for people to read the OSPF-MDR draft:

http://www.ietf.org/internet-drafts/draft-ogier-manet-ospf-extension-05.txt

For an overview, here is a presentation of OSPF-MDR similar
to the one Phil presented at the OSPF session:

http://home.earthlink.net/~ogier/mdr_nov05.ppt

Fred Baker mentioned a possible drawback of the fact
that MDRs and Backup MDRs are a natural generalization
of the DR and Backup DR of an OSPF broadcast network.
He said that a problem can occur if an obstacle separates
the DR and Backup DR.  Actually, in a fully connected network
(similar to a broadcast network), OSPF-MDR actually selects
one MDR and *two* Backup MDRs. This is necessary to ensure that
the backbone consisting of (Backup) MDRs is biconnected.
As a result, if the link between the MDR and first Backup MDR
is broken, the second Backup MDR will forward LSAs between
these two routers.  This is no accident - it is the reason
for having a biconnected backbone.  At first, I was worried
that a second Backup MDR was selected, since OSPF does not
do this, but I am happy that this actually solves a known
drawback of OSPF that Fred Baker mentioned.

Next, I will address the comment of the person who explained
that MPRs can be selected in zero time.  I think he means that
any router can select itself as a Backup MPR (or overlapping relay)
if it can cover any neighbors that are not covered by the
sending neighbor.  Since all neighbors must be considered,
I think this takes O(n) time, not zero time, where n is the
number of neighbors.
In OSPF-MDR, Backup MDRs are preselected for the same purpose
as Backup MPRs (in case a primary relay fails to forward the LSA).
(Backup) MDRs are selected in O(n^2) time, same as MPRs.

One may ask the following: Why not allow any router to be a Backup MDR,
similar to the Overlapping Relay solution which allows any router to be
a Backup MPR?  I thought about this, but excluded it partly because it
is not scalable (explained below).  Also, it not necessary, since
it turns out that biconnected redundancy is sufficient for
good performance.  The reason it is not scalable is because there
can be a large number of routers that are potential Backup MPRs.
If this number is large enough, then it is possible for several of
these routers to forward the LSA at approximately the same time.

Regarding Stan's simulations comparing Smart Peering with MPRs
(which provides a 1-connected adjacency graph), with a version
of OSPF-MDR that provides a biconnected adjacency graph, my
first comment (as you might guess) is that it is not fair
to compare an algorithm that provides a 1-connected adjacency
graph with one that provides a biconnected adjacency graph.
For a fair comparison, the *uniconnected* option of OSPF-MDR
should be used.  (As I was listening to the session, I was
frustated that nobody mentioned this!)

The rest of this message is part of a message that I sent to
the wireless design team this morning.

I ran MDR with 1-connected adjacencies on the 50 node scenario
that Cisco used with radio rage = 200 and velocity = 16.
(Cisco used biconnected adjacencies for MDR, which was not a fair
comparison.)
The results are shown below for three choices of LSAFullness:
0 for Minimum LSAs, 2 for MDR Full LSAs, and 3 for Full LSAs.

The resulting delivery ratios were .834, .839, and .849 for MDR,
compared to .833 for MPRs in the same scenario, so delivery ratio
is comparable.

The resulting UDP forwards were 6265, 6255, and 5487 for MDR,
compared to 10627 for MPRs, so much longer paths were obtained
with MPRs.

The resulting total overheads were 177.59, 257.33, and 500.61
(the last one is for Full LSAs) compared to 457.24 for MPRs.

Although MDR with Full LSAs resulted in more overhead than MPRs,
the other two choices of LSAs performed better than MPRs in
all of the above metrics.  The most notable result is the very
long paths produced by MPRs, which is probably caused by a bug.

Another point is that Cisco considered very sparse networks
(e.g., radio range = 100m), which frequently partition.
Such networks necessarily have a very low delivery ratio
(e.g., 38%) due to partitions, so I am not sure how important
such scenarios are to us.

Additional comments and questions are welcome.

Richard Ogier