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

From: Emmanuel Baccelli <[email-masked]>
Date: Wed, 10 Jan 2007 02:05:24 +0100

Dear all,

here is a report containing the GTNetS simulation results for the 
MPR-OSPF code : 
http://self.d.free.fr/MPR-OSPF/mpr-ospf-simulations-report.pdf

Regards,
Emmanuel

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

---

From: Richard Ogier <[email-masked]>
Date: Wed, 10 Jan 2007 09:59:08 -0800

I wonder how your results would change with the following two
bugs corrected:

1. An LSA was originated only when a neighbor goes to/from Full
(same as for OR), but with MPR-based LSA reduction, an LSA should be
originated whenever the set of MPRs or the set of MPR selectors
changes.

2. In the SPF calculation, the backlink check was not done for
MPR-based LSA reduction.  The backlink must always be checked
for compatibility with OSPFv3 (i.e., the link from node w back to
node v must exist).

With the first bug fixed, I would expect more LSA overhead.
With the second bug fixed, I noticed that delivery ratio is
significantly lower.  However, fixing the first bug
might help increase the delivery ratio.

Anyway, at some point in the future, I expect that the proposed
OSPF extensions will be compared in a fair manner.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Thu, 11 Jan 2007 15:17:49 -0800

> http://self.d.free.fr/MPR-OSPF/mpr-ospf-simulations-report.pdf
Your report compares the following:
1. OR with no adjacency reduction and with full LSAs.
2. Same as 1, but retransmitted LSAs are multicast.
3. Same as 2, but with MPR LSA reduction.

The bugs I mentioned apply mostly to LSA reduction.
Your results show that 2 results in significantly less overhead than 1,
i.e., that it helps to multicast retransmitted LSAs when full-topology
adjacencies are used (no adjacency reduction).
That is an interesting result, but the technique of multicasting
retransmitted LSAs can be applied to any approach, including MDRs.
So it says nothing about the MPR approach versus the MDR approach.
Also, your results do not consider adjacency reduction.  In particular,
it is not clear that multicasting retransmitted LSAs is beneficial
when adjacency reduction is used.
To answer this question for MDR, I plan to run simulations with
multicast retransmitted LSAs, with and without adjacency reduction.
As I mentioned in my post two days ago, this technique can easily
be allowed as an option if it is found to improve performance in some
scenarios.

Also, since any method for LSA reduction can be used with any of
the proposed extensions, your results for MPR LSA reduction
do not say anything about the MPR approach versus the MDR approach.
At some point, I would like to compare min-cost LSAs with MPR-based
LSAs for MDR.

Richard

---

From: Emmanuel Baccelli <[email-masked]>
Date: Fri, 12 Jan 2007 16:07:52 +0100

Hi Richard,

We are happy to see that you join the consensus to push the 3 current 
proposals to experimental status. That way the community will gather 
experience by mixing the various mechanisms for flooding reduction, 
topology reduction and adjacency reduction.

We agree that multicast decreases the impact of adjacency reduction. It 
is one of the factors that enables MPR-OSPF to perform that well while 
keeping strict OSPF adjacency mechanisms.

Regards,
Emmanuel

---

From: Richard Ogier <[email-masked]>
Date: Thu, 18 Jan 2007 14:46:26 -0800

> We agree that multicast decreases the impact of adjacency reduction. 
> It is one of the factors that enables MPR-OSPF to perform that well 
> while keeping strict OSPF adjacency mechanisms.
>
> Regards,
> Emmanuel 

Emmanuel,

(I have been away from my email for the last week.)
It's amazing how you twist my words to conclude that I have joined
"consensus" to push the 3 current proposals to experimental status.
This twisting of words is one reason why I do NOT want to engage
in arguments with INRIA for the next year or so.  Another reason
is that you are trying to avoid a fair comparison, which is why I
had to work hard to write code for your MPR-based adjacency
reduction.

My points were that your main contributions - MPR-based LSA reduction
and multicast retransmitted LSAs - do not by themselves constitute an
OSPF extension, but are techniques that can be applied to either ORs
or MDRs (and it is not yet clear that either provides any significant 
advantage for MDR).  Also, your MPR-based adjacency reduction is
simply not scalable, as was clearly shown in my simulations.
I am currently running simulations for 80 and 100 nodes to
add to my previous simulation results.

Some may say that INRIA's solution is "good enough" to become
an experimental WG draft, but I disagree with that because
it does not scale to dense 100-node networks, as do
the other solutions, and INRIA has not shown that it scales
to such networks.  If you can show that it scales as well
(or almost as well) as the other two solutions, then I
would agree that it can be advanced to experimental.
But I don't think this is possible without major changes.

And this leads to the problem that Joe Macker warned about
at the last meeting, i.e., we want to avoid major changes
to the drafts once they become experimental WG drafts.
Otherwise, we may never converge.  Since your solution is
not currently as scalable as the other solutions, maybe
you are planning to later to modify it later to make it
more scalable, e.g., by using the database signature
exchange mechanism.  As Joe Macker advised, we want to
avoid making such major changes later.  Therefore,
any major changes should be made BEFORE your draft is
advanced to experimental, and simulations should
be run to compare the finalized version to the other
proposals.  (On the other hand, using the database
signature method might have the disadvantage of being
too much of a change from legacy OSPFv3, but that is
a different issue.)

In summary, once you have finalized your draft (so that
no major changes will be necessary), then let's compare
it to the other two solutions.  If it is almost as
scalable as MDR, then I would have no objection to
your draft becoming an experimental WG draft.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Fri, 19 Jan 2007 07:56:16 -0800

All,

I ran simulations for 80 nodes, to add to my previous
GTNetS simulation results for 20, 40, and 60 nodes.
I used the same code that I used before.
INRIA's protocol used MPR-based LSA reduction and MPR-based
adjacency reduction (but retransmitted LSAs were not multicast).
MDR used 1-connected adjacencies and min-cost LSAs.
The same trend continued, with INRIA generating 15 times as much
DD overhead as MDR, and 5 times as much total overhead as MDR.
LS Ack overhead (not shown below) was 204.24 kbps for INRIA
and 75.14 kbps for MDR.
Note that using multicast retransmitted LSAs will not affect
DD overhead, and may increase LS Ack overhead (since every
adjacent neighbor must Ack each multicast LSA).
Parameters were given with my previous results.

Summary of results:

MDR                       20 nodes  40 nodes  60 nodes  80 nodes
---                       --------  --------  --------  --------
Total Overhead (kbps)      21.52     79.08     164.32   271.00
LSU overhead (kbps)         5.21     18.05      33.67    50.56
DD overhead (kbps)          4.08     18.54      36.28    60.88
Adjacencies/node            3.30      3.02      2.88      2.84
Adj changes/node/sec        0.04      0.04      0.04      0.04
Delivery ratio              0.966     0.951     0.953    0.949

INRIA                     20 nodes  40 nodes  60 nodes  80 nodes
-----                     --------  --------  --------  --------
Total Overhead (kbps)      48.20    234.12     588.43  1357.45 (5xMDR)
LSU overhead (kbps)        10.32     40.08      72.33   127.56
DD overhead (kbps)         18.40    119.92     352.89   934.31 (15xMDR)
Adjacencies/node            8.58     15.93      21.93    25.12
Adj changes/node/sec        0.15      0.27       0.36     0.53 (13xMDR)
Delivery ratio              0.918     0.924      0.920   0.912

Richard