Subject: Re: [Ospf-manet] Update to OSPF-MDR draft

From: Richard Ogier <[email-masked]>
Date: Wed, 08 Feb 2006 08:58:09 -0800

Philippe,

I ran some simulations to compare not only the number of adjacencies,
but also the rate of new adjacencies for MPRs versus MDRs.
(The latter is important in OSPF because database exchange must
be performed for each new adjacency.)

I was careful to select MPRs persistently.  A neighbor j was added
as MPR if it lexicographically maximized (adj_level[j], D[j], RID[j]),
where adj_level[j] = 1 if j is already adjacent and 0 otherwise, and
D[j] is the number of uncovered 2-hop neighbors that are neighbors of j.
(Of course, a neighbor is selected as MPR if it is the only neighbor
that covers some 2-hop neighbor.)
When removing redundant MPRs, I first removed selected MPRs that
are not yet adjacent (i.e., were just added).

For MPRs, a link (i,j) is an adjacency if either node i or j is an
MPR of the other, or if either node has the largest RID in
the network.  (The latter is necessary to ensure the adjacency
graph is connected, as pointed out by XXXX, and I am not
sure you included these links in your results.)

Nodes moved randomly in a unit square with speed equal
to 0.1 * range per second (fast mobility).
Rather than use random waypoint, nodes bounced of the sides of the
square, so that node positions are uniformly distributed.

Results are given below for 100 nodes, for range = .5 and .25.
For comparison, I also give the results for the full-topology
solution (i.e., all links are adjacent).
I also show how the rate of new adjacencies changes when
the number of nodes increases from 50 to 200 (for range = .5).

    100 nodes, range = 0.5:
                           Avg. no. adj.  Avg. rate of new adj. (per sec)
                           ----------------------------------------------
    Full topology              2384.29            138.25
    MPRs                        292.62            111.02
    1-connected MDRs            119.32              8.34
    2-connected MDRs            215.82             17.73

    100 nodes, range = 0.25
                           Avg. no. adj.  Avg. rate of new adj. (per sec)
                           ----------------------------------------------
    Full topology               766.33             54.31
    MPRs                        310.63             99.56
    1-connected MDRs            151.44             13.87
    2-connected MDRs            280.68             27.90            

Note that for the dense case, MPRs result in 13 times as many new
adjacencies per second as 1-connected MPRs!
Also note that for the sparse case, MPRs result in a higher
rate of new adjacencies than the full topology solution.

The following table shows how the rate of new adjacencies
increases with the number of nodes, for range = 0.5.

    Rate of new adjacencies:
                       50        100        150        200
                       -------------------------------------
    Full topology      34.17    138.25     311.32     551.80
    MPRs               39.84    111.02     193.14     283.77
    1-connected MDRs    4.61      8.34      12.79      15.34
    2-connected MDRs    9.73     17.73      26.28      33.53

I think these results show that the solution in which
all MPR links are synchronized is simply not scalable.
Certainly the MDR solution is much more scalable.
When the number of nodes is more than 100, database exchange
for new adjacencies becomes the main contributor of overhead
when partial-topology LSAs are used.
Based on these result, I doubt that the MPR solution is even
feasible for 100 nodes.  We can implement it in GTNetS to
find out (if someone is willing to spend the time to do this).

Lessons learned:
1. We cannot have an efficient or scalable solution if we require all
   MPR links to be synchronized.
2. We cannot have an efficient or scalable solution if we restrict
   routing to use only synchronized links.
3. We certainly cannot have an efficient or scalable solution if
   we require *all* links to be synchronized.
4. If we do not restrict routing to use only synchronized links, then
   not only can we have a solution that scales to more than 100 nodes,
   but it is possible to route along shortest paths using any metric.

Note that even the MPR solution does not restrict routing to use
only synchronized links, since the first hop of a min-hop path need
not be an MPR or MPR selector!  Also, OSPF does not require this in
a broadcast network. So it is not clear what we are arguing about.
As others have said, the goal is to provide high quality routing
(with a good delivery ratio) with low overhead.

Richard

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