Subject: [Ospf-wireless-design] Plan for deciding between the two approaches

From: Richard Ogier <[email-masked]>
Date: Fri, 25 Mar 2005 15:04:03 -0800

There has been a suggestion that we should first decide whether to
use MPRs or MDRs (MANET Designated Routers), independently of
everything else. (This may not have been the exact suggestion,
but let's consider it for sake of argument.)

I claim that the performance of MPRs vs. MDRs depends on other
techniques used in the protocol design, so they cannot be
considered independently of these other techniques.

For example, it is possible that MPRs perform better than MDRs
when technique A is used, and MDRs perform better than MPRs
when technique B is used. In this case, it makes sense to
use technique A for MPRs and technique B for MDRs.
If MPRs with technique A performs much better than MDRs with
technique B, then that is an important result to consider.

Techniques A and B could, for example, be the use of Hellos vs.
LSAs to advertise 2-hop neighbor information. (Although in this case,
I think differential Hellos is the best solution for both approaches,
especially for the partial topology case.)

As another example, Technique B could be the trimming of adjacencies
(i.e., reducing the number of adjacencies).
One advantage of the MDR approach is that it makes it easy to
select a reduced set of adjacencies, and it seems to benefit from
this technique.  Suppose, for sake of argument, that the MPR approach
does not benefit from this technique. Then the MPR approach should
not use this technique, but the MDR approach *should* use this
technique. In other words, each approach should use the techniques
that optimize its performance.

So how should this affect the process of deciding between MPRs and MDRs?
We need to implement each approach in the best way possible,
using whatever techniques are best for the approach.
(I am talking about techniques that are easy to implement, not things
that may not feasible for certain vendors to implement, etc.)

As you might guess, I am doing my best to put together the best
combination of techniques for the MDR approach.
(The design is essentially finished, and is being implemented
in GTNetS, but I want to experiment with different parameters
and variations before deciding on the final design.)

For a fair comparison, the MPR approach should also be implemented
in the best possible way.  And if it appears that some techniques
used in the MDR appoach can also help the MPR approach, then those
techniques should be implemented and tested.
After both approaches are implemented in the best possible way,
then a fair performance comparison is possible.

This seems like the best approach to me. Not only is it fair,
but will result in the best possible design.

Richard

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

---

From: Richard Ogier <[email-masked]>
Date: Mon, 28 Mar 2005 07:14:07 -0800

Actually, the decision need not be (source-dependent) MPRs versus
(source-independent) MDRs. (MDR = MANET Designated Router.) In fact,
my draft allows both MDRs and MPRs in a unified, interoperable fashion,
where both are self-selected (in contrast to OLSR in which MPRs are
neighbor-selected). The "min-hop dependent neighbors" in my draft,
which are computed using the ANP CDS algorithm with h = 2, correspond
to the neighbors for which the router has selected itself as an MPR.

An obvious benefit of allowing both MPRs and MDRs in an interoperable
fashion is flexibility.  Even if one wishes to use MPRs in smaller
networks, it is nice to allow the option of using MDRs
to allow better scalability in larger networks.

The fact that my draft allows both MPRs and MDRs also allows
a comparison of the two approaches on a level playing field,
i.e., with all other aspects of the protocol exactly the same.

For example, to form a reduced set of adjacencies based on
(self-selected) MPRs, each router can run the MPN CDS algorithm
with h = 2.  This is similar to an algorithm in the INRIA report cited
in my draft, in which a CDS is computed based on MPRs. Some differences
between the algorithm in my draft and the one in the INRIA report:

  1. MPRs are self-selected in my draft.
  2. My draft presents a persistent version of the algorithm for
     improved stability of the CDS.
  3. The MPN CDS algorithm in my draft also computes the
     dependent/adjacent neighbors of each CDS node.

In another message, I will present simulation results comparing
the number of adjacencies and rate of new adjacencies,
for the Essential CDS algorithm versus the MPN CDS algorithm
with h = 2.  This doesn't exactly compare MDRs with MPRs, but
it compares the CDS (and corresponding adjacencies) computed by
the Essential CDS algorithm with a CDS based on MPRs.

As I said, MPRs are self-selected in my draft. So a relevant question
is whether it is better for MPRs to select themselves, or to be
selected by neighbors.

Note that in draft-chandra-ospf-manet-ext, "active overlapping relays"
are neighbor-selected MPRs, whereas "non-active overlapping relays"
are self-selected (backup) MPRs.

I can think of only two *possible* advantages of having MPRs be
neighbor-selected instead of self-selected:

1. Selecting neighbors as MPRs allows better efficiency by avoiding
   redundant MPRs. However, as the following example shows,
   this possible advantage is completely erased by the use of
   (self-selected) non-active overlapping relays.

          1
        /   \
       /     \
      2       3
       \     /
        \   /
          4

  Node 1 will select only node 3 as an MPR.
  However, node 2 will select itself as a non-active overlapping relay
  and will therefore forward each LSA flooded by node 1,
  since it cannot hear that node 3 is also forwarding each LSA.

2. Selecting neighbors as MPRs allows them to be computed in O(d^2)
   time, whereas self-selecting MPRs (for all neighbors) requires
   O(d^3) time, where d is the maximum number of neighbors per node.

   However, this time complexity is only necessary if we insist that
   each LSA must be flooded along min-hop paths, e.g., that each 2-hop
   neighbor must be reached in exactly 2 hops. This is clearly not
   a requirement for flooding LSAs. The MPN CDS algorithm in my draft,
   with h = 2, runs in O(d^2) time and results in flooding along paths
   that are less than 5% longer than min-hop paths on average (see the
   simulation results in my draft).
   Also, approximation algorithms that run in O(d^2) time exist that
   achieve an average stretch factor of 1 + epsilon for arbitrarily
   small epsilon.

   Also, considering that processor speeds are about 2000 times as fast
   as they were 20 years ago, O(d^3) should be acceptable, since
   d^3 is only 100 times d^2 when d = 100.

One disadvantage of neighbor-selected MPRs (illustrated by my
recent example) is that control information may need to propagate
two hops, versus one hop for self-selected MPRs, to recover from
a link failure. It was pointed out that (self-selected) non-active
overlapping relays can forward LSAs during such a recovery period,
but that makes one wonder why all MPRs are not self-selected
(including active overlapping relays).

In conclusion, neighbor-selected MPRs do not offer a significant
advantage over self-selected MPRs, and a unified approach
that allows both MDRs and (self-selected) MPRs in a
interoperable fashion is a more flexible approach.
In fact, a SI-CDS is necessary anyway (whether or not it is
called that) for selecting a set of adjacencies that span
all nodes, even if such a SI-CDS is based on MPRs.

I am not saying that my draft is the perfect solution.
There is much work to be done, but it is a good start.
I am currently adding some mechanisms to improve robustness,
based on feedback from the meeting in Minneapolis,
and an initial implementation (with robustness enhancements)
should be complete in the next few weeks.

Richard