[Ospf-manet] Simulation results for MPR adjacency reduction

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
Ospf-manet@ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-manet