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

["Spagnolo, Phillip A" <[e-mail]>]

Emmanuel,
 
I have instrumented our simulation to count the number of adjacencies
that would be formed if adjacencies were formed between all MPRs and MPR
Selectors.  Richard's examples seemed to show that just having
adjacencies between MPRs and MPR selectors can cause partition, but this
should give a rough estimate of the set size.

My first intention was to implement the OR draft in GTNetS with
adjacencies only being formed between MPRs and MPR selectors.  However,
after looking at the work to be done, I didn't think it was possible to
complete by the next meeting.  See my notes below on some design issues
that need to be worked out.
 
Instead, I ran the standard ORs and I sampled the number of links that
would be adjacencies every half second.  This was done by counting the
MPRs that a node selected without double counting nodes that selected
each other.  At the end of the simulation, I computed the average number
of adjacencies in the network.  This is an estimate of the true result
because reducing the adjacencies would cause different MPRs to be
selected, we don't see the result of having to remove adjacencies,
etc...

The OR results below are compared against the MDRs with uniconnected
adjacencies.  

Nodes		OR-adjacencies		uni-MDR-adjacencies
10		11.88				11.69
20		42.04				31.04
30		77.30				40.74
40		136.87			53.09
50		193.35			63.47

As expected, it appears that more adjacencies are formed when using
MPR/MPR selectors.  

Do you agree with the estimate?  Do you still feel that this is approach
is viable?  Do you want the code to try yourself?

Sincerely,
Phil

P.S. Below are "some" items that would need to be worked out 
before implementing the MPR/MPR selector adjacencies

-When should the MPR calculation be made?  In the past, it 
only needed to be run when a hello was sent.  Now, it needs 
to occur whenever a neighborhood change is made.

-Should the MPR and MPR selector agree on their roles before 
creating an adjacency or should they always accept an adjacency?

-How do we remove adjacencies to get a fair comparison with MDRs?

-How should full adjacency connectivity be ensured?


> -----Original Message-----
> From: Emmanuel Baccelli [mailto:[e-mail]] 
> Sent: Wednesday, October 26, 2005 3:48 AM
> To: [e-mail]
> 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. 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). 
> 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.
> 
> 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:
> (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.
> 
> Emmanuel
> 
> 
> 
> _______________________________________________
> Ospf-wireless-design mailing list
> [e-mail]
> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> 

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