Subject: [Ospf-manet] OSPF extension for MANETs

From: Emmanuel Baccelli <[email-masked]>
Date: Mon, 27 Feb 2006 15:18:25 +0100

Hi all,

as discussed, here is a contribution to OSPF extension for MANETs, 
incorporating MPR mechanisms for flooding overhead reduction and 
adjacency reduction.
http://www.lix.polytechnique.fr/~baccelli/MPR-OSPF/draft-baccelli-ospf-mpr-ext.txt

Emmanuel

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

---

From: Richard Ogier <[email-masked]>
Date: Mon, 27 Feb 2006 17:04:16 -0800

> http://www.lix.polytechnique.fr/~baccelli/MPR-OSPF/draft-baccelli-ospf-mpr-ext.txt 
Emmanuel,

My first reaction is that it would have been nice to see this
proposal about a year ago.  My second reaction is that your proposal
needs to be implemented in GTNetS so it can be compared to
OSPF-MDR and OR/SP.  (I am not sure who will do this.)
The design team agreed long ago to compare the proposals
in GTNetS, and Boeing has put a lot of effort into doing this.

In any case, based on the simulation results that I posted on 2/8/2006,
your approach in which each router forms an adjacency with each
MPR neighbor will result in much more overhead than OSPF-MDR,
as I mentioned in my position draft.  For example, in a dense 100-node
network (with range equal to 0.5 times the width of the square grid),
using MPR adjacencies resulted in 13.3 times as many new adjacencies
per second as 1-connected MDRs.
This implies 13.3 times as much Database Description (DD) overhead.
A GTNetS simulation shows that the DD overhead for 1-connected MDRs in
this scenario is 76.75 kbps, which implies a DD overhead of
13.3 * 76.75 = 1,020 kbps for MPR adjacencies.
(Of course, this is an estimate, so your approach needs to be
implemented in GTNetS to verify this.)

To make matters worse, your MPR selection algorithm makes no attempt
to select MPRs persistently, e.g., to give higher priority to neighbors
that are already adjacent, whereas the ratio of 13.3 assumed
that MPRs are selected persistently.

There is also an error in your draft.  You stated:

"This ensures that the adjacencies over
the whole OSPF network contain the shortest paths"

and

"In wireless ad hoc parts of the OSPF network, routing is performed
over synchronized adjacencies, as in usual OSPF."

The following example shows that the set of adjacencies does
not always contain the min-hop paths.

       5
      / \
     /   \
    1 --- 2
    |     |
    |     |
    3 --- 4
     \   /
      \ /
       6

In the above example:
Node 1 selects 3 as MPR to cover 4 and 6.
Node 2 selects 4 as MPR to cover 3 and 6.
Node 3 selects 1 as MPR to cover 2 and 5.
Node 4 selects 2 as MPR to cover 1 and 5.
Node 5 becomes adjacent with 1 and 2.
Node 6 becomes adjacent with 3 and 4.

As a result, all neighbor pairs become adjacent
except for [1, 2] and [3, 4].

The set of adjacencies does form a connected subgraph that
spans all nodes (which is guaranteed).
However, the set of adjacencies does not contain a min-hop path
between nodes 1 and 4 (or between nodes 2 and 3).

For example, if node 1 wanted to route packets to node 4,
it would have to select node 2 as the next hop, even though
node 2 is not adjacent (not synchronized).
This problem can be fixed, but you must use the concept
of routable neighbors or unsynchronized adjacencies, as used by OSPF-MDR
or OR/SP. For example, node 2 would be considered routable if there
exists a path of synchronized adjacencies to node 2.

But then, you are no longer routing only along synchronized
adjacencies, so you lose one of the advantages that you claim.

Richard