Subject: RE: [Ospf-wireless-design] any consensus?

From: "Henderson, Thomas R" <[email-masked]>
Date: Wed, 26 Oct 2005 08:23:07 -0700

Emmanuel, thanks for this reply.  I think we have the tools to look into
some of these claims, and perhaps you can work with us in that regard.
See some inline responses. 

> -----Original Message-----
> From: Emmanuel Baccelli [mailto:[email-masked]] 
> Sent: Wednesday, October 26, 2005 3:48 AM
> To: [email-masked]
> Subject: Re: [Ospf-wireless-design] any consensus?
> 
> 
> >
> >On July 12, Emmanuel Baccelli from INRIA posted two reports: 
>  MPR/CDS 
> >stability, and on achieving partial topology in MPR-based solution.
> >These reports haven't generated much discussion, and we 
> haven't had a 
> >chance to look carefully at the CDS stability claims.  The partial 
> >topology solutions recommended were to construct an MPR-CDS 
> or to just 
> >form adjacencies between MPRs and selectors, but because these 
> >MPR/selector relationships are not symmetric, I am guessing that it 
> >will result in many more adjacencies than the CDS approach.
> >  
> >
> 
> Hi all,
> 
> the trade-off in terms of partial topology is the following: 
> if a CDS (i.e. MDR or MPR-CDS) backbone is used to perform 
> reduction in topology advertizement, the routes in the 
> network will suffer from a stretch factor that leads to a 
> substantial amount of unnecessary retransmissions (and hence 
> overhead) in an ad hoc environment. 

This is something that we should be able to explicitly test.  Have you
looked at the results in our report on routing stretch?  We were not
seeing significant stretch using the MDR approach.  See figure 4.2f
(full topology mode).  We do start to see very slight degradation in
route quality when using partial topology (figure 4.8f) but note that
this is comparison of partial topology approaches within MDR framework
itself, not comparison of MDR and Overlapping Relays.

> We may decide to bear 
> with this, but we can also consider another approach based on 
> MPRs that does not lead to any route stretch, but may yield 
> more ajacencies (if indeed routing has to happen over ajacencies). 

Routing does not have to happen over adjacencies (forwarding can happen
over "synchronized" but not adjacent neighbors).  There do need to be a
certain (robust yet sparse) number of true adjacencies, and some
systematic way to select this subset.

> I think there is a
> fine trade off that remains to be evaluated between taking a 
> CDS or MPR as backbone to compute the reduction in topology 
> advertizement.

Again, this should be easily testable, and I don't think we yet have
data on this.  Our intuition, which needs to be tested, is that because
the MPR and selector relationship is not bidirectional, the set of
adjacencies formed by all MPRs and all selectors will be many more than
what the MDR approach yields, and there doesn't appear to be an
intuitive way to systematically prune further adjacencies from the
MPR/selector adjacency set.

> 
> On the other hand, i am convinced that MPR flooding presents 
> better properties than CDS flooding, in an ad hoc environment 
> (see the stability report we have issued 
> http://www.inria.fr/rrrt/rr-5609.html and experience gathered 
> with MPRs in MANETs over the years).
> 
> Therefore taking an approach based on MPR may be the best 
> path, as it enables to decouple the flooding optimization and 
> the topology reduction schemes. 
> This way,
> the better properties of MPR flooding can be used, while 
> topology reduction can still be either based on:
> (i) MPR-CDS adjacency, which will have the same adjacency 
> properties than
>      MDR-CDS topology reduction schemes (see the partial 
> topology report we
>      have issued http://www.inria.fr/rrrt/rr-5619.html ), or based on:

My recollection (please correct if I am wrong) is that MPR-CDS yields
larger CDS than just running a CDS algorithm itself (not that this is
necessarily bad-- sometimes larger sets are more robust, to a point),
and that it would just be easier to compute the CDS directly.

> (ii) MPR-selector links/adjacency.
> 
> I guess my point is that the MDR approach should not be 
> favoured for its topology reduction abilities, since an MPR 
> approach features at least as good topology reduction 
> abilities and a better flooding scheme.
> 

These points are debatable.  I would argue that the smart peering
approach does not provide as good a topology reduction scheme.  Whether
the other approaches you mention (MPR-CDS, and MPR/selector adjacencies)
provide as good or better scheme is what can be tested and evaluated.

On the second point, we would have to look more at the stability claims.
Please note also that we are looking at the application to OSPF, not
pure MANET flooding.  For example, Figure 4.2c is a measure of the
number of relays per node, and it shows that MDRs result in more relays
per node.  Just looking at this one figure, one might conclude that MPRs
are preferred because they yield a smaller relay set (I believe that
this has been argued about MPRs vs. CDS before).  However, we found that
this fact does not necessarily translate into reduced overhead in OSPF.
We discuss why the two schemes arrive at roughly the same overhead
performance by working in different ways in section 4.2.1 of our report.

Tom 

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

---

From: Richard Ogier <[email-masked]>
Date: Wed, 26 Oct 2005 11:51:16 -0700

>MPR/selector adjacency set.

I think that the main thing that should be tested (and I already
suggested this in my message dated 8/28/2005) is whether it is better to
use the existing MDR selection algorithm for selecting the CDS backbone,
or to select the CDS backbone based on MPRs (using the self-pruning
strategy in INRIA's report RR-5609).  This can be tested by modifying the
OSPF-MDR draft/code so that the self-pruning MPR method is used to select
MDRs. Backup MDRs can be obtained similarly by first selecting Backup MPRs
and applying self-pruning to these.  The algorithm for selecting MPRs and
Backup MPRs should be based on (MDR_Level, RtrPri, RID) as in the MDR
draft, for stability.  I.e., the MPR selection algorithm should not
be based on the number of 2-hop neighbors covered, since this would
result in poor stability.  This will also result in a larger number
of MPRs than before.

Adjacencies can be established between each (Backup) MDR
and each neighboring (Backup) MDR, and between each MDR Other
and its parents (selected as in the MDR draft). (This is allowed
by Section 5.5 of the OSPF-MDR draft.)  All other aspects of
OSPF-MDR can remain the same.  Instead of the min-cost LSAs, it would
be possible to originate LSAs based on MPRs, i.e., each router includes
all of its MPR selectors in its LSA.  The GTNetS code can be modified
to test this variation of OSPF-MDR (using MPRs).

If it is too much work to implement Backup MPRs for the purpose of
selecting Backup MDRs, then we can compare the two approaches using
only MDRs (and no Backup MDRs) which gives a 1-connected adjacency
graph.

On the other hand, since no detailed method has yet been
proposed for extending OSPF in this way, one could argue that it
is too late to consider new designs such as this.

Another possibility for consensus is to agree to use the OSPF-MDR draft
as a starting point and agree to test alternative methods for selecting
the MDRs, including methods based on MPRs.  (Also, to test alternative
methods for selecting neighbors to include in LSAs, including methods
based on MPRs.)

Richard

---

From: Richard Ogier <[email-masked]>
Date: Wed, 26 Oct 2005 20:46:41 -0700

I have a few more comments below.

>itself, not comparison of MDR and Overlapping Relays.

Emmanuel is referring to the stretch factor when only CDS backbone nodes
are allowed as intermediate nodes.  In the OSPF-MDR draft, this is
the case with MDR Full LSAs (LSAFullness = 2) but not for Min-Cost LSAs
(LSAFullness = 1).  The latter case provides min-hop routes (if all link
costs are equal) just as does routing along links defined by MPRs
(as in OLSR).

Even with MDR Full LSAs, where MDRs and Backup MDRs originate full LSAs,
the stretch factor is pretty good.  But Min-Cost LSAs have no
disadvantage compared to routing based on MPRs, since both theoretically
provide min-hop routes.  The only reason these methods might provide 
slightly
suboptimal paths is due to the delay in reacting to topology changes.

>>more ajacencies (if indeed routing has to happen over ajacencies).

As mentioned above, the Min-Cost LSAs in the OSPF-MDR draft have the
same route stretch property as routing based on MPRs.  The difference
is that Min-Cost LSAs allow routing over non-adjacencies.
(As I mentioned in my previous email, it might be useful to compare
these two approaches by modifying the OSPF-MDR code to select
MDRs and form LSAs based on MPRs.)

Now I will discuss the approach in which routing and adjacencies are
based on MPRs, i.e., in which adjacencies are formed in both directions
between each router and its selected MPRs.  First of all, as I discussed
previously, some restrictions are needed to ensure that the resulting
adjacency graph is connected.  The following example shows this.

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

If node 1 selects node 2 as an MPR, and node 4 selects
node 3 as an MPR, then the adjacency graph defined
by MPRs is not connected. This can be fixed by selecting
MPRs based on (MDRLevel, RtrPri, RID) as I mentioned in my
previous email, and by having a router form adjacencies
with all neighbors if it has a larger (MDRLevel, RtrPri, RID)
than all of its neighbors. This ensures that the adjacency
graph is connected.  But as Tom pointed out, this also
results in many more adjacencies than using a CDS approach.
It is inefficient and unnecessary to require routing
to be over adjacencies.  OSPF already allows routing
to occur between non-adjacent neighbors (in a broadcast
network).  OSPF already uses this technique to
reduce overhead, so it makes sense to use a similar
(generalized) technique in MANETs.

So, as I mentioned in my previous email, I hope we can
agree to use the OSPF-MDR approach as a starting point,
and agree to test variations that make use of MPRs
to select the CDS backbone (MDRs) and to generate LSAs.

If it is easy to also evaluate the approach in which
routing and adjacencies are based on MPRs, then we
can also evaluate that. However, I think this has already
been tried, which is probably why it was not proposed.

Richard