Subject: [Ospf-wireless-design] Re: consensus

From: Emmanuel Baccelli <[email-masked]>
Date: Fri, 04 Nov 2005 11:28:41 +0100

Hi all,

i want to point out that it could be beneficial to include Philippe 
Jacquet in this debate as he and Richard
already had many discussions about related subjects on the MANET mailing 
list (and these may not be totally
taken into account yet in this design).

I also want to clarify my point of view, because it seems i was not 
clear enough. I think that flooding schemes
and topology reduction schemes do not have to be tied together. In 
particular it may not be the best approach
to evaluate a solution only based on the topology reduction performance 
it achieves. For example, flooding
can be done with an MPR-based mechanism, while topology reduction can be 
done based on a CDS approach.
I think we can have a flooding optimization design that is more 
independent from the topology reduction design
than the recent discussions seem to point out.

One thing that must be considered though, is the stretch factor that is 
implied by the topology reduction scheme going
with MDRs. We are currently at INRIA running some simulations to 
evaluate this stretch factor. It seems it may be
quite substantial, and this should be taken into account in the design, 
as route stretching introduces an overhead that
is proportional to the data traffic. On the other hand using 
MPR/MPRselector adjacencies does yield more adjacencies,
but no route stretching whatsoever. So here (in the topology reduction 
design) there is a trade-off that was not yet fully
discussed in my opinion.

As far as the flooding optimization design is concerned, it was not 
discussed so much lately, as the focus was rather on topology
reduction design. It should be beneficial to continue discussing this 
point, and we would like to get some feedback on our report
that we published this summer about the stability of CDS-based flooding 
schemes. It seems that when the ad hoc nodes are not
static, MPR flooding performance is much steadier than CDS-based 
flooding which is rather fragile, especially when the
CDS is reduced to the fewest nodes. ( 
ftp://ftp.inria.fr/INRIA/publication/publi-pdf/RR/RR-5609.pdf )

We also ran some quick simulations to evaluate the number of  MPR 
adjacencies (for the same
domain/range parameters as Richard), and we found the numbers shown below:

Number    Number of
of nodes    MPR links
10             10.50
20             32.72
30             57.56
40             84.14
50           114.56
60           143.88
70           178.64
80           211.04
90           241.80
100         273.90

We were therefore very surprised to compare these with the simulation 
results given by
Richard, as there is a rather drastic difference?

Emmanuel

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

---

From: "Joe Macker" <[email-masked]>
Date: Fri, 4 Nov 2005 13:30:09 -0500

Emmanuel:

You have some interesting thoughts on analysis specifics and perhaps some of
this should taken to the manet-dt list if we talk about flooding
effectiveness, especially fragility as you mention. 

I have been leaning towards adjacency reduction as a key factor for
OSPF-MANET work, but as I have mentioned we have ongoing work looking at
flooding optimizations only in the context of SMF.  Adjacency reduction and
flooding effectiveness can be different subjects.  

See draft-ietf-manet-smf-01. We have been examining several CDS algorithms
for this purpose. including modifications of ones being considered in
manet-ospf.  There is some common ground here between ongoing manet SMF work
and OSPF-manet.  However, in the routing control plane adjacency reduction
is a scalability winner and I think that has been an appropriate area of
concentration.  If there is a significant win in the flooding effectivenesss
by protocol A vs. B (when mobile), I think that should be pointed out. So
far we see similar performance between several algorithms considered when
looing at packets delivered vs. packet sent in a variety of mobile
scenarios.  

Justin Dean has done some analysis, both analytical and mobile simulation of
CF,MPR, MPR-CDS (shared set), MDR (without redundant sets).  He will be in
Vancouver and could talk off-line about some of what he has done.

-Joe

>-----Original Message-----
>From: [email-masked] 
>[mailto:[email-masked]] On Behalf 
>Of Emmanuel Baccelli
>Sent: Friday, November 04, 2005 5:29 AM
>To: [email-masked]
>Subject: [Ospf-wireless-design] Re: consensus
>
>Hi all,
>
>i want to point out that it could be beneficial to include 
>Philippe Jacquet in this debate as he and Richard already had 
>many discussions about related subjects on the MANET mailing 
>list (and these may not be totally taken into account yet in 
>this design).
>
>I also want to clarify my point of view, because it seems i 
>was not clear enough. I think that flooding schemes and 
>topology reduction schemes do not have to be tied together. In 
>particular it may not be the best approach to evaluate a 
>solution only based on the topology reduction performance it 
>achieves. For example, flooding can be done with an MPR-based 
>mechanism, while topology reduction can be done based on a CDS 
>approach.
>I think we can have a flooding optimization design that is 
>more independent from the topology reduction design than the 
>recent discussions seem to point out.
>
>One thing that must be considered though, is the stretch 
>factor that is implied by the topology reduction scheme going 
>with MDRs. We are currently at INRIA running some simulations 
>to evaluate this stretch factor. It seems it may be quite 
>substantial, and this should be taken into account in the 
>design, as route stretching introduces an overhead that is 
>proportional to the data traffic. On the other hand using 
>MPR/MPRselector adjacencies does yield more adjacencies, but 
>no route stretching whatsoever. So here (in the topology reduction
>design) there is a trade-off that was not yet fully discussed 
>in my opinion.
>
>As far as the flooding optimization design is concerned, it 
>was not discussed so much lately, as the focus was rather on 
>topology reduction design. It should be beneficial to continue 
>discussing this point, and we would like to get some feedback 
>on our report that we published this summer about the 
>stability of CDS-based flooding schemes. It seems that when 
>the ad hoc nodes are not static, MPR flooding performance is 
>much steadier than CDS-based flooding which is rather fragile, 
>especially when the CDS is reduced to the fewest nodes. ( 
>We also ran some quick simulations to evaluate the number of  
>MPR adjacencies (for the same domain/range parameters as 
>Richard), and we found the numbers shown below:
>
>Number    Number of
>of nodes    MPR links
>10             10.50
>20             32.72
>30             57.56
>40             84.14
>50           114.56
>60           143.88
>70           178.64
>80           211.04
>90           241.80
>100         273.90
>
>We were therefore very surprised to compare these with the 
>simulation results given by Richard, as there is a rather 
>drastic difference?
>
>Emmanuel
>
>
>

---

From: Richard Ogier <[email-masked]>
Date: Fri, 04 Nov 2005 10:35:08 -0800

Emmanuel,

You seem to be missing some points in the recent discussion.
Phil pointed out one of these in his email today.
Another one you seem to be missing is that adjacencies
based on MPRs (the way you select them) do not work, since they
do not guarantee the graph of adjacencies is connected.

> Richard, as there is a rather drastic difference? 

As I explained, the simulations I ran used a modified method of selecting
MPRs that ensures the adjacency graph is connected.  However, Phil's
simulation results show that MPRs result in many more adjacenies
than OSPF-MDR even if the usual method is used for selecting MPRs.

Regarding my discussion with Philippe Jacquet on the MANET list, it did not
go beyond what we are discussing here.  Philippe never replied after
I correctly pointed out that OSPF-MDR results in fewer adjacencies than
using MPRs.

http://www1.ietf.org/mail-archive/web/manet/current/msg07547.html

Richard

Emmanuel Baccelli wrote:

> already had many discussions about related subjects on the MANET 
> mailing list (and these may not be totally
> to evaluate a solution only based on the topology reduction 
> performance it achieves. For example, flooding
> can be done with an MPR-based mechanism, while topology reduction can 
> be done based on a CDS approach.
> One thing that must be considered though, is the stretch factor that 
> is implied by the topology reduction scheme going
> quite substantial, and this should be taken into account in the 
> design, as route stretching introduces an overhead that
> that we published this summer about the stability of CDS-based 
> flooding schemes. It seems that when the ad hoc nodes are not

---

From: Richard Ogier <[email-masked]>
Date: Fri, 04 Nov 2005 10:46:38 -0800

> Richard, as there is a rather drastic difference? 

Another important reason for the difference, for the last
set of simulation results that I presented, is that I was
using *persistent* adjacencies, so that once an adjacency
is formed, it is never torn down as long as a bidirectional
link exists.  This was done to reduce the *rate* of new adjacencies,
which is more important than the average number of adjacencies.
(Even with this modification, the rate of new adjacencies was much
larger for MPRs than for OSPF-MDR.)

I am just repeating what I explained in my emails presenting
simulation results, so please refer to those emails for
more details.

Richard

---

From: Acee Lindem <[email-masked]>
Date: Fri, 04 Nov 2005 14:50:53 -0500

> do not guarantee the graph of adjacencies is connected.
Hi Richard,
I don't understand why it wouldn't if an adjacency is formed (or retained)
if either neighbor selects the other as a relay? Of course, to do this 
effectively
the MPR selection algorithm should consider whether or not there is an
exant adjacency and give those relay candidate preference.

Thanks,
Acee

---

From: Richard Ogier <[email-masked]>
Date: Fri, 04 Nov 2005 13:29:12 -0800

> exant adjacency and give those relay candidate preference.

Acee,

I gave a few examples in an email I posted a few days ago, showing why
the resulting adjacency graph is not guaranteed to be connected, even if
an adjacency is formed when either neighbor selects the other as an MPR.
I don't have access to my old emails now, but the simplest example
is a fully connected network, which has no MPRs.

In any case, we seem to be in agreement that using MPRs to select
adjacent neighbors results in more adjacencies than using MDRs.
Even more significant, using MPRs results in a MUCH greater RATE
of new adjacencies than OSPF-MDR (according to my simulations).

Emmanuel wrote:

> On the other hand using MPR/MPRselector adjacencies does yield more 
> adjacencies,
> design) there is a
> trade-off that was not yet fully discussed in my opinion. 

As Phil pointed out, there is no such trade-off, since MDRs can be used
with min-cost LSAs (or even with LSAs based on MPRs) without any
route stretch.

As I mentioned, I still think it is worth evaluating the selection of
the CDS/MDRs based on pruning MPRs, and this can easily be implemented
by modifying the GTNetS code for OSPF-MDR.  It is also worth evaluating
the use of LSAs based on MPRs (the LSA would contain MPR selectors as
in OLSR).   Therefore, based on the recent discussions (from which
we can exclude MPR-based adjacencies), it appears to me that the consensus
is headed toward using a CDS, which may or may not be based on MPRs.
Since we already have a CDS solution that performs very well (OSPF-MDR),
I hope we can agree to use OSPF-MDR as a starting point, and to evaluate
modifications of it that use MPRs to select the MDRs and/or to generate
LSAs.

 > Of course, to do this effectively

Giving existing adjacencies higher preference when selecting
MPRs does not help to ensure the adjacency graph is connected.
Using my modified MPR selection algorithm, which ensures the adjacency
graph is connected, you would have to give MPRs preference *independently*
of the MPR selector, so that all nodes agree on the priority of
a given node.  I tried doing this in simulations (so that a node
has higher priority if *any* neighbor selected it as an MPR),
but it did not help performance.  This is probably because, with the
modified MPR selection algorithm, more than half of the nodes are
selected as MPR by some neighbor.

Richard