Subject: [Ospf-manet] Re: Regarding OSPF MDR

From: Richard Ogier <[email-masked]>
Date: Mon, 05 Mar 2007 08:45:23 -0800

All,

I ran some simulations using the modified min-cost LSA algorithm
that is described in the updated MDR draft
draft-ogier-manet-ospf-extension-09.txt (submitted yesterday).

I announced plans to modify the min-cost LSA algorithm a few months
ago, so this update is not in response to Philippe's recent comments
regarding the old version.  However, the new min-cost LSA algorithm
does address some of Philippe's recent comments, for example:

o  Neighbor advertisements are symmetric: if a neighbor j advertises
   router i, then router i advertises neighbor j.

o  The updated min-cost LSA algorithm uses only information from
   Hellos received from neighbors, and no longer uses LSAs
   from neighboring routers.  There is nothing wrong with using
   LSAs, except that using both Hellos and LSAs adds complexity,
   so this was done to keep the algorithm simple.

o  All links have the same cost; no penalty is added to the cost
   of links to neighbors that are not fully synchronized.
   This is not really a change, since routers still have the option
   of adding such as penalty, but I wanted to avoid any possible
   claims of unfairness.

One criticism that Philippe might still have is that the algorithm
requires O(d^3) time if run from scratch.
However, it requires only O(d^2) time for a single topology
change, so I think this is acceptable, since a router rarely
needs to run the algorithm from scratch.

I am still open to the possibility of using LSA reduction
based on the "path-MPR" approach, since this can indeed reduce
the size of LSAs as Philippe claims.  However, based on the
results for delivery ratio presented below, my main concern
is that the path-MPR approach might not be as robust (possible
reasons are given below).

For the simulations, I used INRIA's GTNetS code with MPR LSA reduction
and MPR adjacency reduction.  I used the following parameters for both
INRIA and MDR, to agree with INRIA's report.  Both protocols also used
the database exchange summary list optimization.

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

As I mentioned previously, in INRIA's code, only the router with
the largest RID in the network is a synch router. This does not agree
with draft-baccelli-ospf-mpr-ext-02.txt, which says a router is a synch
router if it has the largest (willingness, RID) in its neighborhood.

The updated ospf6d directory and Makefile for OSPF-MDR can be found at
home.earthlink.net/~ogier/ospf6d_mdr.tar.gz
home.earthlink.net/~ogier/Makefile
(All CFLAGS involving MPRs are commented out in the Makefile, since
they might interfere with the operation of OSPF-MDR.)

I ran simulations with 40, 60, 80, and 100 nodes, with range = 250 m.
The results are summarized below, and detailed results for 100
nodes are given at the end of the message.

MDR                       40 nodes  60 nodes  80 nodes  100 nodes
---                       --------  --------  --------  --------
Total Overhead (kbps)     114.45    235.20    397.86    611.34
LSU overhead (kbps)        38.42     67.78    106.46    149.76
LS Ack overhead (kbps)     37.09     91.62    157.23    266.15
DD overhead (kbps)         10.06     21.14     39.37     57.58
Adjacencies/node            2.67      2.92      2.87      2.38
Adj changes/node/sec        0.04      0.04      0.05      0.04
Avg LSAs out of sync        0.81      0.69      0.43      0.43
Delivery ratio              0.931     0.934     0.936     0.934

INRIA                     40 nodes  60 nodes  80 nodes  100 nodes
-----                     --------  --------  --------  --------
Total Overhead (kbps)     160.80    369.07    670.03   1174.08
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 (9 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 9.34 times that of MDR,
resulting in almost 2 times as much total overhead.
Also, INRIA's solution has a much lower delivery ratio
(.844 versus .934 for 100 nodes).  I don't know if this
is a bug, but if not, my best guess is that this results from a
combination of advertising barely enough links (no redundancy)
and a longer delay to update LSAs following a link failure
(due to the delay required to update and report MPRs as has
been discussed).  So, even though OSPF-MDR advertises more neighbors
in LSAs, maybe these larger LSAs are necessary for robustness.

The overhead for unicast LSUs is very low for MDR (13.65 kbps
for 100 nodes), indicating that it will not help much to use
multicast LSA retransmissions in MDR.

In large networks, MDR's largest overhead component is LS Ack
overhead, but this will be reduced to 0 if the non-ackable LSA
option is used, at the cost of some additional multicast LSU
transmissions.  I plan to experiment with this option.

Richard

------------------------------
Detailed results for 100 nodes

MDR:

./random_waypoint_manet-opt seed=1 num_nodes=100 pktrate=10 
wireless_interface=2 wireless_flooding=2 velocity=16 radio_range=250 
pause_time=1 HelloInterval=2 RxmtInterval=7 DeadInterval=6 
AckInterval=2000 BackupWaitInterval=500 TwoHopRefresh=3 
AdjConnectivity=1 LSAFullness=1 start_time=1800 stop_time=2700

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

OSPFv3 Statistics
           | Packets          Bytes         Kbps
----------------------------------------------------
Hello       |   45000      15462092      137.44
LSAck       |   43579      29941584      266.15
LSR         |     664         46104        0.41
DBDESC      |    9130       6478252       57.58
LSU         |   53945      16848024      149.76
  LSUfld    |     47795      15312504      136.11
  LSUuni    |      6150       1535520       13.65
    LSUcol  |          38         15236        0.14
    LSUrxmt |        5234       1205800       10.72
    LSUdbex |         693        275356        2.45
    LSUstale|         185         39128        0.35
            |
Total       |  152318      68776056      611.34

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 64.35
OSPF 2way_neighbor_changes/node/sec: 1.37
avg_sec/OSPF 2way neighbor_life: 102.29
OSPF adjacencies/node: 2.38
OSPF adjacency_changes/node/sec: 0.04
avg_LSAsOutSync: 0.43
Secs per router-LSA origination:  5.62
Router-LSA hopcount/Router-LSA installs:  2.33
Route changes/node/sec:  54.98
Accumulated adjacencies/node:  0.08

Flooding Statistics
--------------------------------------------------
relaysel/node: 3.61
avg_sec/relaysel_life: 44.42
suppressed_LSAs: 1413794
relay_flood_LSAs: 91878
nonrelay_flood_LSAs: 5151

Topology Reduction Statistics
--------------------------------------------------
Advertized neighbors: 112786
Total FULL neighbors: 1002857

User Traffic Analysis
--------------------------------------------------
UDP sends: 8897 pkts, 604996 bytes
UDP receives: 8311 pkts, 565148 bytes
UDP forwards: 3191 pkts, 216988 bytes

Delivery Ratio:  0.934
--------------------------------------------------

INRIA:

./random_waypoint_manet-opt seed=1 num_nodes=100 pktrate=10 
wireless_interface=2 wireless_flooding=1 TopoReduc velocity=16 
pause_time=1 radio_range=250 HelloInterval=2 RxmtInterval=7 
DeadInterval=6 PushbackInterval=3500 AckInterval=500 MinLSInterval=5 
start_time=1800 stop_time=2700

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

OSPFv3 Statistics
           | Packets          Bytes         Kbps
----------------------------------------------------
Hello       |   45000      15352104      136.46
LSAck       |  111118      33088368      294.12
LSR         |   38618       3180936       28.27
DBDESC      |   77256      60519168      537.95
LSU         |  102987      19943140      177.27
  LSUfld    |     40608       5252344       46.69
  LSUuni    |     62379      14690796      130.58
    LSUcol  |          20          6344        0.06
    LSUrxmt |           0             0        0.00
    LSUdbex |       38402      12007948      106.74
    LSUstale|       23957       2676504       23.79
            |
Total       |  374979     132083716     1174.08

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 65.42
OSPF 2way_neighbor_changes/node/sec: 0.87
avg_sec/OSPF 2way neighbor_life: 163.41
OSPF adjacencies/node: 31.78
OSPF adjacency_changes/node/sec: 0.42
avg_LSAsOutSync: 1.66
Secs per router-LSA origination:  5.46
Router-LSA hopcount/Router-LSA installs:  1.92
Route changes/node/sec:  20.26
Accumulated adjacencies/node:  5.17
Sync Node changes: 0.00

Flooding Statistics
--------------------------------------------------
relaysel/node: 1.99
avg_sec/relaysel_life: 7.08
suppressed_LSAs: 0
relay_flood_LSAs: 44823
nonrelay_flood_LSAs: 0
relay_flood_LSAs retransmissions: 4905

Neighborhood Statistics
--------------------------------------------------
Hello received: 2617968
Inactivity calls: 35125

Topology Reduction Statistics
--------------------------------------------------
Advertized neighbors: 51408
Total FULL neighbors: 1099248

User Traffic Analysis
--------------------------------------------------
UDP sends: 8897 pkts, 604996 bytes
UDP receives: 7510 pkts, 510680 bytes
UDP forwards: 2183 pkts, 148444 bytes

Delivery Ratio:  0.844
--------------------------------------------------

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