Subject: [Ospf-manet] Simulation results for MPR adjacency reduction

From: Richard Ogier <[email-masked]>
Date: Tue, 02 Jan 2007 12:55:42 -0800

All,

Since I was curious about the performance of INRIA's solution
with MPR adjacency reduction (in addition to MPR LSA reduction),
I decided to modify the GTNetS code (the version INRIA released)
to implement this, and run some simulations.
The GTNetS code I used can be downloaded at:
http://home.earthlink.net/~ogier/ospf6d_mpr_adj.tar.gz

I include only the directory ospf6d, since everything else is the
same as INRIA's release, except that the following line should
be uncommented in the Makefile so that MDR can also be run:
CFLAGS    += -DOSPF6_MANET_MDR_FLOOD

The results below give an idea of how MPR-based adjacencies perform
based on INRIA's current draft specification.
INRIA can probably improve the performance, e.g., by selecting
MPRs more persistently, but until that happens, I wanted to see
how it performs based on the current specification.

The results for 20, 40, and 60 nodes are summarized below, followed by
a summary of the code changes.  Detailed results for 60 nodes and
the parameters values are are given at the end of this message.
For INRIA's solution (which is a modification of OR), I used the
parameter values recommended by the Cisco OR/SP team and used in
Boeing's simulations.
As in OR/SP, for both INRIA and MDR, an adjacency is never torn down
as long as the neighbor is bidirectional, to reduce the rate at which
new adjacencies are formed.

Results for MDR with 1-connected adjacencies and min-cost LSAs:
                          20 nodes  40 nodes  60 nodes
                          --------  --------  --------
Total Overhead (kbps)      21.52     79.08     164.32
LSU overhead (kbps)         5.21     18.05      33.67        
DD overhead (kbps)          4.08     18.54      36.28
Adjacencies/node            3.30      3.02      2.88
Adj changes/node/sec        0.04      0.04      0.04
Delivery ratio              0.966     0.951     0.953

Results for MPR-based LSAs and adjacency reduction:
                          20 nodes  40 nodes  60 nodes
                          --------  --------  --------
Total Overhead (kbps)      48.20    234.12     588.43
LSU overhead (kbps)        10.32     40.08      72.33
DD overhead (kbps)         18.40    119.92     352.89
Adjacencies/node            8.58     15.93      21.93
Adj changes/node/sec        0.15      0.27       0.36
Delivery ratio              0.918     0.924      0.920

Notice that adjacency changes/node/sec stays constant at .04 for MDR,
but increases approximately linearly for INRIA.  This clearly shows
that MPR adjacency reduction is not scalable.  The DD overhead is
4.5 times greater for INRIA for 20 nodes, 6.5 times greater for 40
nodes, and 9.7 times greater for 60 nodes (notice the trend).
Also notice that for INRIA the DD overhead becomes much greater than
LSU overhead for 60 nodes, but for MDR the DD overhead is about
the same as the LSU overhead for 20, 40, and 60 nodes.

The delivery ratio is significantly greater for MDR than for INRIA.
This could be partly due to the lower path/LSA stability of INRIA,
since MPRs are not selected persistently (while min-cost LSAs
are designed to be persistent), and partly due to the delay in
updating MPRs following a link failure (as has been discussed).

Code changes:

I found the following bugs in INRIA's code:

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.  This problem went away with MPR-based adjacency
reduction, since a neighbor becomes Full only after it
becomes an MPR or MPR selector (or the router or neighbor
is a sync node).

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). (Let me know if this has somehow changed.)

3. The code was written so that OSPF6_MANET_MDR_FLOOD and
OSPF6_MANET_MPR_TOPO_REDUC could not both be defined, i.e.,
the code had to be compiled separately for the two protocols.

Summary of changes:

1. The code was fixed so that OSPF6_MANET_MDR_FLOOD and
OSPF6_MANET_MPR_TOPO_REDUC can both be defined, without the
code for one protocol interfering with the other protocol.

2. The backlink check is always done.

3. The code now does MPR adjacency reduction, as follows:
(a) need_adjacency() was modified so that an adjacency is needed only
    if the neighbor is an MPR or MPR selector, or the router or
    neighbor is a sync node.
(b) A node determines that it is a sync node if it has a larger RID
    than all neighbors.  This is updated whenever the set of neighbors
    changes, and is indicated in Hellos by setting the DR field equal
    to the router's own RID. (A detail not specified in the draft.)
(c) Adjacencies are updated whenever the set of MPRs or MPR
    selectors changes, and whenever the set of neighbors changes.
(d) MPRs are no longer required to be Full neighbors, and 2-hop
    neighbors are no longer required to be Full neighbors of 1-hop
    neighbors.

Note that the modified code cannot run MPR LSA reduction
without MPR adjacency reduction, since that would require
even more work :-).

Richard

--------------------------------------
Detailed results for MDR for 60 nodes:

./random_waypoint_manet-opt seed=8 num_nodes=60 pktrate=10 
wireless_interface=2 wireless_flooding=2 velocity=10 radio_range=250 
alpha=0.5 pause_time=40 HelloInterval=2 RxmtInterval=7 DeadInterval=6 
AckInterval=1000 BackupWaitInterval=500 TwoHopRefresh=3 
AdjConnectivity=1 LSAFullness=1 start_time=1800 stop_time=2700

Neighbor statistics (at physical layer):
--------------------------------------------------
Number of nodes: 60
Neighbor threshold distance (m): 250.00
Average neighbor density (neighbors/# of nodes):  0.63
Average neighbor changes/time (changes/sec/node): 0.30

OSPFv3 Statistics
           | Packets          Bytes         Kbps
----------------------------------------------------
Hello       |   27000       5849812       52.00
LSAck       |   38145       4753120       42.25
LSR         |     246         13128        0.12
DBDESC      |    4911       4081624       36.28
LSU         |   18728       3787764       33.67
  LSUfld    |     15147       3078988       27.37
  LSUuni    |      3581        708776        6.30
    LSUcol  |           7          3704        0.03
    LSUrxmt |        3307        655336        5.83
    LSUdbex |         243         44928        0.40
    LSUstale|          24          4808        0.04
            |
Total       |   89030      18485448      164.32

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 37.15
OSPF 2way_neighbor_changes/node/sec: 0.66
avg_sec/OSPF 2way neighbor_life: 121.12
OSPF adjacencies/node: 2.88
OSPF adjacency_changes/node/sec: 0.04
avg_LSAsOutSync: 0.12
Secs per router-LSA origination:  15.81
Router-LSA hopcount/Router-LSA installs:  2.61
Route changes/node/sec:  4.54
Accumulated adjacencies/node:  -0.10

Flooding Statistics
--------------------------------------------------
relaysel/node: 3.70
avg_sec/relaysel_life: 44.23
suppressed_LSAs: 165040
relay_flood_LSAs: 19259
nonrelay_flood_LSAs: 958

Topology Reduction Statistics
--------------------------------------------------
Advertized neighbors: 20752
Total FULL neighbors: 113259

User Traffic Analysis
--------------------------------------------------
UDP sends: 8951 pkts, 608668 bytes
UDP receives: 8529 pkts, 579972 bytes
UDP forwards: 3748 pkts, 254864 bytes

Delivery Ratio:  0.953

------------------------------------------
Detailed results for INRIA for 60 nodes:

./random_waypoint_manet-opt seed=8 num_nodes=60 pktrate=10 
wireless_interface=2 wireless_flooding=1 velocity=10 radio_range=250 
HelloInterval=2 RxmtInterval=9 DeadInterval=6 PushbackInterval=7000 
AckInterval=500 MinLSInterval=5 velocity=10 start_time=1800 
stop_time=2700 TopoReduc

Neighbor statistics (at physical layer):
--------------------------------------------------
Number of nodes: 60
Neighbor threshold distance (m): 250.00
Average neighbor density (neighbors/# of nodes):  0.63
Average neighbor changes/time (changes/sec/node): 0.30

OSPFv3 Statistics
           | Packets          Bytes         Kbps
----------------------------------------------------
Hello       |   27000       6109348       54.31
LSAck       |   85432      12017232      106.82
LSR         |    4147        234588        2.09
DBDESC      |   51672      39700376      352.89
LSU         |   61758       8137020       72.33
  LSUfld    |     50603       6587356       58.55
  LSUuni    |     11155       1549664       13.77
    LSUcol  |         112         27252        0.24
    LSUrxmt |        4953        502816        4.47
    LSUdbex |        3929        795020        7.07
    LSUstale|        2161        224576        2.00
            |
Total       |  230009      66198564      588.43

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 37.06
OSPF 2way_neighbor_changes/node/sec: 0.71
avg_sec/OSPF 2way neighbor_life: 111.63
OSPF adjacencies/node: 21.93
OSPF adjacency_changes/node/sec: 0.36
avg_LSAsOutSync: 0.27
Secs per router-LSA origination:  5.66
Router-LSA hopcount/Router-LSA installs:  2.15
Route changes/node/sec:  13.33
Accumulated adjacencies/node:  0.57

Flooding Statistics
--------------------------------------------------
relaysel/node: 2.87
avg_sec/relaysel_life: 12.06
suppressed_LSAs: 439557
relay_flood_LSAs: 34974
nonrelay_flood_LSAs: 24216

Topology Reduction Statistics
--------------------------------------------------
Advertized neighbors: 37634
Total FULL neighbors: 357653

User Traffic Analysis
--------------------------------------------------
UDP sends: 8951 pkts, 608668 bytes
UDP receives: 8237 pkts, 560116 bytes
UDP forwards: 3105 pkts, 211140 bytes

Delivery Ratio:  0.920
-----------------------

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

---

From: Emmanuel Baccelli <[email-masked]>
Date: Mon, 08 Jan 2007 15:07:03 +0100

Dear Richard, all,

Happy new year to you and yours. Thanks for your contribution to the 
MPR-OSPF code. We already knew that the MPR-OSPF draft is simple to 
understand and to implement, but you were really very fast. Congratulations.

However, we did not find exactly the same results as the ones you 
mentionned, we will release soon the results we got. In particular our 
simulation results show that MPR-based topology reduction and multicast 
outperforms MDR and OR performance reported by Boeing at the IETF.

Here is an update to the MPR-OSPF code that implements multicast 
transmissions http://ndquan.free.fr/GTNetS/gtnets-LSAreduc-Mcast.tar.bz2
The use of multicast is now implemented in addition to MPR topology 
reduction, which provides a simple and robust solution ensuring that 
while the overhead is drastically reduced, every advertized link is 
still symmetric and synchronized.

The available code for MPR-OSPF actually outperforms both OR and MDR
(full LSA) simulated with the same parameters, based on the reports of 
Boeing that were presented at the IETF. We will release
a report about these results soon. This confirms that topology reduction 
on its own is very efficient, apparently more than adjacency reduction.

We would nevertheless like to stress the fact that the simulation 
scenarios and parameters that are used in the Boeing reports are quite 
restrictive. In particular, we think the values of parameters such as 
Retransmit time and min LSA interval are not in tune at all with high 
mobility, and that the 2x2 scenario with almost mesh connectivity is too 
specific. We think that it is essential to simulate other scenarios and 
other parameters.

Concerning bugs in the code, we also found some of them that we want to 
share with you: for instance, it seems that an old Ack can somehow 
replace a newer Ack in the database and therefore create problems 
regarding retransmissions. Did you notice such a behaviour? We had to 
fix this. We have moreover fixed the bug you have mentionned concerning 
the conflicting flags OSPF6_MANET_MDR_FLOOD and 
OSPF6_MANET_MPR_TOPO_REDUC that can now be compiled together.

Regards,
Emmanuel

---

From: Richard Ogier <[email-masked]>
Date: Tue, 09 Jan 2007 08:00:00 -0800

Emmanuel,

For MDR, the number of adjacency changes/node/sec is constant
as the number of nodes increases.  I.e., the number of
synchronizations per second is linear in the the number of nodes.
This is not true for MPR adjacencies (as my results show), and I don't
think it is possible as long as each router must become adjacent with
each of its MPRs and MPR selectors.
Let me know if you are somehow avoiding this consequence.

Maybe your results look OK for certain scenarios with a limited
number of nodes, but how scalable is your solution?
For example, how does it perform in dense networks with 100
or more nodes?

Regarding multicasting retransmitted LSAs, you are simply requiring
that every transmitted or retransmitted LSA be be Acked by every
adjacent neighbor.  This technique can be applied to any of the
proposals, including MDR.
One of the rules the design team discussed (more than a year ago)
for a fair simulation comparison is the following:
If a technique is used by protocol A, then it should also be used
by protocol B if it improves performance for that protocol.

Note that retransmitting LSAs as multicasts was considered in
version 00 of the MDR draft.  It was later removed partly to
minimize changes to OSPF and partly because it did not appear
to reduce overhead much when adjacency reduction is used.
However, it can easily be allowed as an option if it is found
to improve performance in some scenarios.

I noticed that your code still does not do the backlink check
in the SPF calculation when OSPF6_MANET_HELLO_OSPF_MPR
is defined (this also affects the MDR code).  Do you understand why
this is not compatible with OSPFv3?  For example, a MANET router could
have a non-MANET neighbor, which performs the backlink check and
therefore does not compute the shortest-path tree based on the same
topology, possibly resulting in routing loops.
In addition, an adjacency is not fully synchronized until the state
is Full at BOTH endpoints.

I took a quick look at the bug you mentioned where an old Ack can
replace a newer Ack.  I think you are correct, since in the
function ospf6_store_mack(), if an Ack already exists in the
mack list (even if it is newer), the sequence number of the
stored Ack is set to the sequence number of the received Ack,
even if the received Ack is older.

Richard

Emmanuel Baccelli wrote:

> simulation results show that MPR-based topology reduction and 
> multicast outperforms MDR and OR performance reported by Boeing at the 
> IETF.
>
> a report about these results soon. This confirms that topology 
> reduction on its own is very efficient, apparently more than adjacency 
> reduction.
>
> mobility, and that the 2x2 scenario with almost mesh connectivity is 
> too specific. We think that it is essential to simulate other 
> scenarios and other parameters.
>
> Concerning bugs in the code, we also found some of them that we want 
> to share with you: for instance, it seems that an old Ack can somehow 
> fix this. We have moreover fixed the bug you have mentionned 
> concerning the conflicting flags OSPF6_MANET_MDR_FLOOD and