Subject: Re: [Ospf-manet] MPR-OSPF GTNetS simulations report

From: Richard Ogier <[email-masked]>
Date: Mon, 05 Feb 2007 08:08:36 -0800

> Hello,
>
> From the previous emails, it seemed that Dr. Ogier suggested the use 
> of simulations as a "tie breaker" to even administer a proposal to 
> experimental status. Simulations may not be the most accurate 
> representation of the reality to the last bit, but they provide 
> sufficient framework to cheaply evaluate and compare different 
> proposals against each other. I believe it should be possible to 
> design a series of parametric runs (changing node density, changing 
> mobility, changing network size, changing radio range etc etc.) to 
> extensively compare all the proposals against each other. All the 
> criticism about considering only a single/limited set of scenarios 
> gets nullified when one has conducted a parametric run, and I don't 
> see any way other than the simulations to do this.
>
> Thanks,
>
> Aniket 

Aniket,

I agree that simulations should be a part of the evaluation process.
Most people agreed at the last IETF meeting that simulations
are important, so we already have consensus on this point.

For example, if implementations show that all solutions perform
about the same for 50 nodes in a number of scenarios, but simulations
show that one scales much better to 100 or more nodes, then that is
important evidence that should be considered, and could be used
to "break a tie".

Simulations are not perfect, but will have some inaccuracy.
For example, if a simulation model is found to predict
overhead with 25% accuracy (compared to a real implementation),
and simulation results show that protocol A has 75% less overhead
than protocol B, that is a significant result.

It is interesting that Emmanuel is presenting results for at
most 50 nodes, whereas it has already been shown that MDR is
scalable to more than 100 nodes.  50-node networks are not
very challenging, now that we can support 100 nodes.
We need to simulate larger networks in order to stress the
protocols and determine which protocols are really scalable.

I ran some simulations with up to 100 nodes, using Emmanuel's
latest code release.  I will present these results in my next
message.

Richard

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

---

From: Richard Ogier <[email-masked]>
Date: Mon, 05 Feb 2007 08:16:29 -0800

Emmanuel and all,

I ran some simulations to compare INRIA's solution
with MPR LSA reduction and adjacency reduction
to MDR with min-cost LSAs and 1-connected adjacencies.

I noticed that you used my database exchange optimization
(by defining OSPF6_MANET_MDR_FLOOD_DD in Makefile).
http://www.ietf.org/internet-drafts/draft-ietf-ospf-dbex-opt-00.txt

I guess you forgot to mention this.  This reduces DD overhead
by about 50%, and therefore reduces the difference between
INRIA and MDR overhead, but it does not change the fact that
DD overhead increases much faster with MPR adjacency reduction
than with MDR, as the number of nodes increases.
So the difference in overhead is still quite dramatic in larger
networks, as the results below show.

I used your GTNetS code with MPR LSA reduction and MPR adjacency
reduction.  I used the following parameters for both INRIA and MDR,
to agree with your report:

Max velocity: 16 m/s
Pause time: 1s
HelloInterval: 2 s
DeadInterval: 6 s
RxmtInterval: 7 s
MinLSInterval: 5 s
MinLSArrival: 1 s
AckInterval: 500 ms

(Your report does not mention PushbackInterval, but it was
set to 3500 msec in your perl file, so I used that value.)
The database exchange summary list optimization was used
with both INRIA and MDR.

I ran simulations with 40, 60, 80, and 100 nodes, with range = 250 m.
The results for 40 nodes agree with your graphs (for overhead and
delivery ratio).  The results are summarized below.

MDR                       40 nodes  60 nodes  80 nodes  100 nodes
---                       --------  --------  --------  --------
Total Overhead (kbps)      72.50    138.84    252.79    370.76
LSU overhead (kbps)        17.57     29.02     49.82     65.88
LS Ack overhead (kbps)     17.31     36.66     73.46    118.57
DD overhead (kbps)         10.50     21.52     38.97     54.60
Adjacencies/node            2.66      3.02      2.83      2.41
Adj changes/node/sec        0.05      0.04      0.05      0.04
Avg LSAs out of sync        0.48      0.35      0.30      0.24
Delivery ratio              0.939     0.941     0.935     0.938

INRIA                     40 nodes  60 nodes  80 nodes  100 nodes
-----                     --------  --------  --------  --------
Total Overhead (kbps)     160.80    369.07    670.03   1174.08 (3 x MDR)
LSU overhead (kbps)        27.97     58.66    100.02    177.27
LS Ack overhead (kbps)     49.15    109.55    183.28    294.12
DD overhead (kbps)         51.21    138.09    277.72    537.95 (10 x MDR)
Adjacencies/node           16.37     21.08     26.49     31.78
Adj changes/node/sec        0.25      0.29      0.34      0.42 (10 x MDR)
Avg LSAs out of sync        1.79      1.78      1.61      1.66
Delivery ratio              0.849     0.845     0.867     0.844

For 100 nodes, INRIA's DD overhead is about 10 times that
of MDR, resulting in 3 times as much total overhead.
But there seems to a problem (perhaps a bug) with INRIA's
code, since INRIA has a much lower delivery ratio,
and a much larger number of LSAs out of sync than MDR.

Richard

---

From: Emmanuel Baccelli <[email-masked]>
Date: Fri, 09 Feb 2007 11:56:42 +0100

Dear Richard,

Your simulation results are comparing apples and oranges. MPR-OSPF 
synchronizes each link that is advertized in LSAs so that routing loops 
are avoided, and advertizes enough links so that shortest paths can be 
derived. On the other hand, MDR provides much different link and path 
properties.

For this reason, the quick overhead comparison you are making is not 
relevant.

Moreover, we think it is futile to elaborate on your simulation results 
since we've been looking at your code and it is not apparent that it 
corresponds to what is described in the MDR draft.

Emmanuel