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

From: "Spagnolo, Phillip A" <[email-masked]>
Date: Fri, 28 Oct 2005 15:31:12 -0700

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:[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. 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
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> 

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

---

From: Richard Ogier <[email-masked]>
Date: Mon, 31 Oct 2005 12:47:37 -0800

All,

I ran some simulations using my simple C program
to compare the number of adjacencies and rate of new
adjacencies for MDR with uniconnected adjacencies,
and for an MPR-based method that guarantees the
adjacency graph is connected.

The MPR-based method selects a neighbor to be an MPR
if it is the maximum RID neighbor that can cover
some 2-hop neighbor. (Redundant MPRs cannot be removed
since this could violate the connectivity property.)
Each node becomes adjacent with all of its MPRs,
and a node that has a larger RID than all of its neighbors
becomes adjacent with all of its neighbors.
(I can prove that this results in a connected adjacency graph.)

Nodes are placed randomly in a unit square, the transmission
radius is 0.5, and nodes move in a random direction (bouncing
off sides of the square) at a speed of 1/20 of the radius
per second.  Results are averaged over 100 runs.

Adjacencies are bidirectional and are counted only once
for both directions.  Note that the MPR-based method does
not use persistence (unlike MDRs), since it is not clear
how to select MPRs persistently while ensuring connectivity.
(This may explain the large rate of new adjacencies for MPRs.)

#nodes   Method     Average no. adj.    Average rate of new adj.
----------------------------------------------------------------
50        MDRs          50.6                   2.92 (adj per sec)
50        MPRs         227.0                  35.67
----------------------------------------------------------------
100       MDRs         100.0                   4.91
100       MPRs         572.9                 113.08
----------------------------------------------------------------

Richard

---

From: Richard Ogier <[email-masked]>
Date: Mon, 31 Oct 2005 16:30:27 -0800

All,

The simulation results I presented in my last message assumed
that an adjacency is torn down as soon as the condition for
forming the adjacency is no longer satisfied. To increase
stability, OSPF-MDR keeps an existing adjacency as long as
either endpoint is an MDR (for uniconnected adjacencies).
Similarly, the MPR-based method (in which each router becomes
adjacent with its MPRs) can keep an existing adjacency
as long as the two endpoints are bidirectional neighbors.
The simulation results for these modified methods
are given below.  This affects OSPF-MDR by increasing the
number of adjacencies by about 10% and reducing the rate
of new adjacencies by about 5%.  This affects the MPR-based
method more dramatically, more than doubling the number of
adjacencies, and reducing the rate of new adjacencies by
about 45%.

The average number of edges is 594 for the 50 node network,
and 2402 for the 100 node network.

New results:

#nodes   Method     Average # adj.    Average rate of new adj.
----------------------------------------------------------------
50        MDRs          54.8                   2.78 (adj per sec)
50        MPRs         463.4                  19.00
----------------------------------------------------------------
100       MDRs         110.1                   4.73
100       MPRs        1440.2                  64.02
----------------------------------------------------------------

Old results (adjacency is torn down when the condition for forming
an adjacency is no longer satisfied):

#nodes   Method     Average # adj.    Average rate of new adj.
----------------------------------------------------------------
50        MDRs          50.6                   2.92 (adj per sec)
50        MPRs         227.0                  35.67
----------------------------------------------------------------
100       MDRs         100.0                   4.91
100       MPRs         572.9                 113.08
----------------------------------------------------------------

Richard