Subject: Re: [Ospf-manet] Adjacency Reduction??

From: Richard Ogier <[email-masked]>
Date: Mon, 13 Feb 2006 08:13:54 -0800

All,

Since there has been some discussion about whether adjacency reduction
is needed, I would like to explain why I think it is essential,
and present a few simulation results to support this.

We seem to be in agreement that partial-topology LSAs are desirable,
and most of us seem to agree that partial-topology adjacencies are
also desirable.  As shown in Boeing's technical report
http://hipserver.mct.phantomworks.org/ietf/ospf/
and also in my simulation results below, BOTH partial-topology LSAs
and partial-topology adjacencies are needed to achieve scalability, e.g.,
to 100 nodes.  If full-topology adjacencies were used, bandwidth would
be consumed by unnecessary overhead, and we would not be able to support
as many nodes as with partial-topology adjacencies.

We can support 100 nodes and more, and I know there are a lot of
clients and users that would like to have this scalability.  A lot of
people will be disappointed if we give them something that will perform
well only in smaller networks.  Let's not disappoint them.

Using the GTNetS code, I ran some simulations with 100 nodes to
compare OSPF-MDR with partial-topology LSAs and partial-topology
adjacencies, to OSPF-MDR with partial-topology LSAs and full-topology
adjacencies.  We know that using partial-topology LSAs and adjacencies
is scalable, so the question is whether using full-topology adjacencies
and partial-topology LSAs is also scalable (to 100 nodes).

For partial-topology LSAs, I used MDR full LSAs (only MDRs and BMDRs
originate full LSAs), since this was easy to implement with both
1-connected and full-topology adjacencies.

I used two ranges: 250 and 125 meters (the grid is 500 meters).
Node velocity was 10 m/s. The parameters and detailed results
are given at the end of this message.
For the dense case, simulation took about 2 hours with 1-connected
adjacencies and about 10 hours with full-topology adjacencies
(which by itself indicates something).  For the sparse case, the
simulation took about 4 hours with 1-connected adjacencies and
about 24 hours with full-topology adjacencies.

    Results for 100 nodes with range = 250:
                                             Overhead       Delivery Ratio
                                             -----------    --------------
    Partial LSAs, 1-connected adjacencies:    402.41 kbps    0.961
    Partial LSAs, full adjacencies:          9306.42 kbps    0.481

    Results for 100 nodes with range = 125:
                                             Overhead       Delivery Ratio
                                             -----------    --------------
    Partial LSAs, 1-connected adjacencies:   1200.66 kbps    0.760
    Partial LSAs, full adjacencies:          4473.03 kbps    0.718

As these results show, it is not just a matter of full-topology
adjacencies causing a little more overhead.  For range = 250,
they cause about 23 times as much overhead and reduce delivery
ratio by 50% by consuming almost all of the bandwidth.
For the sparse case, they cause 3.73 times as much overhead.
Although the delivery ratio was not affected as much in the sparse case,
the increased overhead clearly reduces the available bandwidth
substantially, so with heavier traffic loads we would see a larger
drop in delivery ratio.

But full-topology adjacencies may be appropriate in some cases,
such as for very sparse networks.  To support this, we can add
an option to OSPF-MDR to use full-topology adjacencies.
This should satisfy the both the people who prefer to use
full-topology adjacencies, and the people who want a scalable
solution.

Richard

P.S.  Someone might ask "What's so special about 100 nodes?".
Nothing, except that it is a nice round number and happens
to be a challenging but achievable goal.  I ran a simulation
with 150 nodes in which OSPF-MDR peformed well, with slightly
lower delivery ratio (0.933), but larger networks take
longer to simulate.

--------------------------------------------------
100 nodes, range = 250, 1-connected adjacencies, MDR full LSAs:

./random_waypoint_manet-opt wireless_interface=2 wireless_flooding=2 
HelloInterval=2 DeadInterval=6 RxmtInterval=7 AckInterval=500 
BackupWaitInterval=500 AdjConnectivity=1 LSAFullness=2 num_nodes=100 
radio_range=250 velocity=10 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.63
Average neighbor changes/time (changes/sec/node): 0.46

OSPFv3 Statistics
           | Packets          Bytes         Kbps
----------------------------------------------------
Hello       |   45000      14370476      127.74
LSAck       |  104580       8939440       79.46
LSR         |     547         28632        0.25
DBDESC      |    8877       8314516       73.91
LSU         |   21220      13618220      121.05
  LSUfld    |     16799      12576972      111.80
  LSUuni    |      4421       1041248        9.26
    LSUcol  |          19         18756        0.17
    LSUrxmt |        3757        735032        6.53
    LSUdbex |         510        207756        1.85
    LSUstale|         135         79704        0.71
            |
Total       |  180224      45271284      402.41

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 62.39
OSPF 2way_neighbor_changes/node/sec: 1.08
avg_sec/OSPF 2way neighbor_life: 126.08
OSPF adjacencies/node: 2.55
OSPF adjacency_changes/node/sec: 0.03
avg_LSAsOutSync: 0.11
Secs per router-LSA origination:  29.28
Route changes/node/sec:  5.23
Accumulated adjacencies/node:  -0.33

Flooding Statistics
--------------------------------------------------
relaysel/node: 3.84
avg_sec/relaysel_life: 47.85
suppressed_LSAs: 253521
relay_flood_LSAs: 17433
nonrelay_flood_LSAs: 1368

User Traffic Analysis
--------------------------------------------------
UDP sends: 8897 pkts, 604996 bytes
UDP receives: 8549 pkts, 581332 bytes
UDP forwards: 3752 pkts, 255136 bytes

Delivery Ratio:  0.961
--------------------------------------------------
100 nodes, range = 250, full-topology adjacencies, MDR full LSAs:

./random_waypoint_manet-opt wireless_interface=2 wireless_flooding=2 
HelloInterval=2 DeadInterval=6 RxmtInterval=7 AckInterval=500 
BackupWaitInterval=500 AdjConnectivity=1 LSAFullness=2 num_nodes=100 
radio_range=250 velocity=10 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.63
Average neighbor changes/time (changes/sec/node): 0.46

OSPFv3 Statistics
           | Packets          Bytes         Kbps
----------------------------------------------------
Hello       |   45000      11165648       99.25
LSAck       |  241089      21770444      193.52
LSR         |    4560        268956        2.39
DBDESC      |  591342     354025868     3146.90
LSU         |  931729     659741444     5864.37
  LSUfld    |    342912     224109584     1992.09
  LSUuni    |    588817     435631860     3872.28
    LSUcol  |       93975     113384096     1007.86
    LSUrxmt |      122152     111016072      986.81
    LSUdbex |        3532       2105956       18.72
    LSUstale|      369158     209125736     1858.90
            |
Total       | 1813720    1046972360     9306.42

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 31.21
OSPF 2way_neighbor_changes/node/sec: 6.19
avg_sec/OSPF 2way neighbor_life: 10.13
OSPF adjacencies/node: 2.14
OSPF adjacency_changes/node/sec: 0.22
avg_LSAsOutSync: 0.09
Secs per router-LSA origination:  0.57
Route changes/node/sec:  98.59
Accumulated adjacencies/node:  -1.14

Flooding Statistics
--------------------------------------------------
relaysel/node: 30.29
avg_sec/relaysel_life: 9.34
suppressed_LSAs: 234527
relay_flood_LSAs: 646841
nonrelay_flood_LSAs: 83396

User Traffic Analysis
--------------------------------------------------
UDP sends: 8897 pkts, 604996 bytes
UDP receives: 4277 pkts, 290836 bytes
UDP forwards: 6099 pkts, 414732 bytes

Delivery Ratio:  0.481
--------------------------------------------------
100 nodes, range = 125, full-topology adjacencies, MDR full LSAs:

./random_waypoint_manet-opt wireless_interface=2 wireless_flooding=2 
HelloInterval=2 DeadInterval=6 RxmtInterval=7 AckInterval=500 
BackupWaitInterval=500 AdjConnectivity=1 LSAFullness=2 num_nodes=100 
radio_range=125 velocity=10 start_time=1800 stop_time=2700

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

OSPFv3 Statistics
           | Packets          Bytes         Kbps
----------------------------------------------------
Hello       |   45000       6897500       61.31
LSAck       |  118017      18207312      161.84
LSR         |    1399         86172        0.77
DBDESC      |   38511      37099124      329.77
LSU         |  144814      72783884      646.97
  LSUfld    |    126734      68701988      610.68
  LSUuni    |     18080       4081896       36.28
    LSUcol  |         171        101700        0.90
    LSUrxmt |       15955       3190888       28.36
    LSUdbex |        1487        628172        5.58
    LSUstale|         467        161136        1.43
            |
Total       |  347741     135073992     1200.66

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 20.74
OSPF 2way_neighbor_changes/node/sec: 0.90
avg_sec/OSPF 2way neighbor_life: 48.34
OSPF adjacencies/node: 3.28
OSPF adjacency_changes/node/sec: 0.11
avg_LSAsOutSync: 0.12
Secs per router-LSA origination:  9.07
Route changes/node/sec:  39.39
Accumulated adjacencies/node:  -0.52

Flooding Statistics
--------------------------------------------------
relaysel/node: 5.05
avg_sec/relaysel_life: 22.13
suppressed_LSAs: 676909
relay_flood_LSAs: 232499
nonrelay_flood_LSAs: 18934

User Traffic Analysis
--------------------------------------------------
UDP sends: 8897 pkts, 604996 bytes
UDP receives: 6760 pkts, 459680 bytes
UDP forwards: 12043 pkts, 818924 bytes

Delivery Ratio:  0.760

--------------------------------------------------
100 nodes, range = 125, full-topology adjacencies, MDR full LSAs:

./random_waypoint_manet-opt wireless_interface=2 wireless_flooding=2 
HelloInterval=2 DeadInterval=6 RxmtInterval=7 AckInterval=500 
BackupWaitInterval=500 AdjConnectivity=1 LSAFullness=2 num_nodes=100 
radio_range=125 velocity=10 start_time=1800 stop_time=2700

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

OSPFv3 Statistics
           | Packets          Bytes         Kbps
----------------------------------------------------
Hello       |   45000       6784852       60.31
LSAck       |  138167      30668892      272.61
LSR         |   17153        948036        8.43
DBDESC      |  334947     316902572     2816.91
LSU         |  319318     147911400     1314.77
  LSUfld    |    229184     123960028     1101.87
  LSUuni    |     90134      23951372      212.90
    LSUcol  |        1792        903068        8.03
    LSUrxmt |       61242      14335316      127.43
    LSUdbex |       16602       5766420       51.26
    LSUstale|       10498       2946568       26.19
            |
Total       |  854585     503215752     4473.03

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 19.94
OSPF 2way_neighbor_changes/node/sec: 1.30
avg_sec/OSPF 2way neighbor_life: 31.69
OSPF adjacencies/node: 15.29
OSPF adjacency_changes/node/sec: 0.86
avg_LSAsOutSync: 0.16
Secs per router-LSA origination:  5.05
Route changes/node/sec:  132.94
Accumulated adjacencies/node:  -1.26

Flooding Statistics
--------------------------------------------------
relaysel/node: 5.53
avg_sec/relaysel_life: 16.22
suppressed_LSAs: 1224189
relay_flood_LSAs: 477818
nonrelay_flood_LSAs: 74578

User Traffic Analysis
--------------------------------------------------
UDP sends: 8897 pkts, 604996 bytes
UDP receives: 6390 pkts, 434520 bytes
UDP forwards: 11308 pkts, 768944 bytes

Delivery Ratio:  0.718
--------------------------------------------------

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

---

From: Richard Ogier <[email-masked]>
Date: Tue, 14 Feb 2006 07:50:52 -0800

All,

Tom and Phil informed me that there is possibly a bug in the GTNetS code
that affected the simulation results I posted yesterday for full-topology
adjacencies, for 100 nodes and range = 250.
The "Secs per router-LSA origination" was 0.57 for this case, which should
not happen because MinLSInterval is 5.

> Results for 100 nodes with range = 250:

Hopefully, the bug will be found soon so the simulation can be rerun.
I did not make any change to the code that could cause such a bug.
The diff for my changes are given below, in case someone else wants to
run the same simulation.

Richard

diff ospf6d_orig/ospf6_intra.c ospf6d/ospf6_intra.c
279c279,283
<                       on->state != OSPF6_NEIGHBOR_FULL)
---
 >                       //on->state != OSPF6_NEIGHBOR_FULL)
 >                    // FULL_ADJ_PARTIAL_LSA
 >                       (on->state != OSPF6_NEIGHBOR_FULL ||
 >                        on->mdr_level < OSPF6_BMDR))
 >
diff ospf6d_orig/ospf6_neighbor.c ospf6d/ospf6_neighbor.c
529a530
 >       return 1; // For full-topology adjacencies with 
partial-topology LSAs

---

From: Richard Ogier <[email-masked]>
Date: Mon, 20 Feb 2006 16:42:17 -0800

All,

I reran the simulations comparing partial vs. full-topology
adjacencies when partial-topology LSAs are used.
This time I performed "make clean" before compiling, since
not doing this can cause errors such as MinLSInterval being
overwritten.

These simulations use MDR full LSAs for both partial-topology
and full-topology adjacencies. (The exact choice of partial
topology LSAs was not important for the purpose of this
experiment, but MDR full LSAs were easy to implement in a
consistent manner for both partial-topology and full-topology
adjacencies.)  With MDR full LSAs, each MDR/BMDR includes all
Full neighbors when full-topology adjacencies are used,
and each MDR/BMDR includes all routable neighbors when
partial-topology adjacencies are used.  Also, the next hop
calculated by SPF can be any routable neighbor when partial
topology adjacencies are used, but must be Full (synchronized)
when full topology adjacencies are used (i.e., the concept
of routable or unsychronized neighbors is not needed if
full adjacencies are used.)

The results are summarized below, with detailed results
given at the end of this message. I ran two scenarios:
100 nodes with range = 250 and range = 125.
This time, the longest simulation (full-topology adjacencies)
took about 9 hours to run, and the shortest simulation
(partial-topology adjacencies) took less than 2 hours.

    Results for 100 nodes with range = 250:
                                      Overhead       Delivery Ratio
                                      -----------    --------------
    Partial LSAs, 1-connected adj:    384.65 kbps    0.959
    Partial LSAs, full adj:          6515.54 kbps    0.081

    Results for 100 nodes with range = 125:
                                     Overhead       Delivery Ratio
                                     -----------    --------------
    Partial LSAs, 1-connected adj:   1175.73 kbps    0.758
    Partial LSAs, full adj:          4244.74 kbps    0.749

The general conclusion is the same as before: full-topology adjacencies
result in much more overhead, and are not even feasible in the
dense case.  For range = 250, they cause about 17 times as much
overhead and reduce delivery ratio to about 8% by consuming almost
all of the bandwidth.
For the sparse case, they cause 3.6 times as much overhead.
Although the delivery ratio was not affected as much in the sparse case,
the increased overhead clearly reduces the available bandwidth
substantially, so with heavier traffic loads we would see a larger
drop in delivery ratio.

For the dense case, the detailed results below indicate that the
huge overhead with full adjacencies made it impossible to select
MDRs and adjacencies corrrectly, with only 3.42 adjacencies per
node (compared to 62 neighbors) and 26.74 MDR neighbors per node
(compared to only 3.94 with 1-connected adjacencies).
This explains the larger flooding overhead obtained with
full adjacencies.

Richard

./random_waypoint_manet-opt wireless_interface=2 wireless_flooding=2 
HelloInterval=2 DeadInterval=6 RxmtInterval=7 AckInterval=1000 
BackupWaitInterval=500 AdjConnectivity=1 LSAFullness=2 num_nodes=100 
radio_range=250 velocity=10 start_time=1800 stop_time=2700

OSPFv3 Statistics
           | Packets          Bytes         Kbps
----------------------------------------------------
Hello       |   45000      14375172      127.78
LSAck       |   64424       7303224       64.92
LSR         |     569         29532        0.26
DBDESC      |    8407       7870740       69.96
LSU         |   20488      13694360      121.73
  LSUfld    |     16726      12891032      114.59
  LSUuni    |      3762        803328        7.14
    LSUcol  |          10          8492        0.08
    LSUrxmt |        3229        570012        5.07
    LSUdbex |         481        190592        1.69
    LSUstale|          42         34232        0.30
            |
Total       |  138888      43273028      384.65

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 62.43
OSPF 2way_neighbor_changes/node/sec: 1.07
avg_sec/OSPF 2way neighbor_life: 127.60
OSPF adjacencies/node: 2.42
OSPF adjacency_changes/node/sec: 0.02
avg_LSAsOutSync: 0.11
Secs per router-LSA origination:  29.62
Route changes/node/sec:  5.19
Accumulated adjacencies/node:  -0.19

Flooding Statistics
--------------------------------------------------
relaysel/node: 3.94
avg_sec/relaysel_life: 50.92
suppressed_LSAs: 245283
relay_flood_LSAs: 17304
nonrelay_flood_LSAs: 1231

User Traffic Analysis
--------------------------------------------------
UDP sends: 8897 pkts, 604996 bytes
UDP receives: 8533 pkts, 580244 bytes
UDP forwards: 3714 pkts, 252552 bytes

Delivery Ratio:  0.959

./random_waypoint_manet-opt wireless_interface=2 wireless_flooding=2 
HelloInterval=2 DeadInterval=6 RxmtInterval=7 AckInterval=1000 
BackupWaitInterval=500 AdjConnectivity=1 LSAFullness=2 num_nodes=100 
radio_range=250 velocity=10 start_time=1800 stop_time=2700

OSPFv3 Statistics
           | Packets          Bytes         Kbps
----------------------------------------------------
Hello       |   45000      11496188      102.19
LSAck       |  261271      31056156      276.05
LSR         |    3517        218064        1.94
DBDESC      |  639525     402460804     3577.43
LSU         |  942532     287767132     2557.93
  LSUfld    |    295434      80044364      711.51
  LSUuni    |    647098     207722768     1846.42
    LSUcol  |       66466      44218788      393.06
    LSUrxmt |      140490      45953680      408.48
    LSUdbex |        2813        721932        6.42
    LSUstale|      437329     116828368     1038.47
            |
Total       | 1891845     732998344     6515.54

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 34.07
OSPF 2way_neighbor_changes/node/sec: 6.20
avg_sec/OSPF 2way neighbor_life: 11.06
OSPF adjacencies/node: 3.42
OSPF adjacency_changes/node/sec: 0.32
avg_LSAsOutSync: 0.06
Secs per router-LSA origination:  7.00
Route changes/node/sec:  6.55
Accumulated adjacencies/node:  -0.95

Flooding Statistics
--------------------------------------------------
relaysel/node: 26.74
avg_sec/relaysel_life: 8.67
suppressed_LSAs: 321200
relay_flood_LSAs: 442272
nonrelay_flood_LSAs: 89839

User Traffic Analysis
--------------------------------------------------
UDP sends: 8897 pkts, 604996 bytes
UDP receives: 724 pkts, 49232 bytes
UDP forwards: 730 pkts, 49640 bytes

Delivery Ratio:  0.081

--------------------------------------------------
100 nodes, range = 125, 1-connected adjacencies, MDR full LSAs:

./random_waypoint_manet-opt wireless_interface=2 wireless_flooding=2 
HelloInterval=2 DeadInterval=6 RxmtInterval=7 AckInterval=1000 
BackupWaitInterval=500 AdjConnectivity=1 LSAFullness=2 num_nodes=100 
radio_range=125 velocity=10 start_time=1800 stop_time=2700

OSPFv3 Statistics
           | Packets          Bytes         Kbps
----------------------------------------------------
Hello       |   45000       6899292       61.33
LSAck       |   68747      16434752      146.09
LSR         |    1340         84108        0.75
DBDESC      |   37114      35743120      317.72
LSU         |  144700      73108884      649.86
  LSUfld    |    128044      69554436      618.26
  LSUuni    |     16656       3554448       31.60
    LSUcol  |         144         77540        0.69
    LSUrxmt |       14653       2730692       24.27
    LSUdbex |        1405        589712        5.24
    LSUstale|         454        156504        1.39
            |
Total       |  296901     132270156     1175.73

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 20.73
OSPF 2way_neighbor_changes/node/sec: 0.89
avg_sec/OSPF 2way neighbor_life: 48.53
OSPF adjacencies/node: 3.28
OSPF adjacency_changes/node/sec: 0.11
avg_LSAsOutSync: 0.13
Secs per router-LSA origination:  9.06
Route changes/node/sec:  40.31
Accumulated adjacencies/node:  -0.83

Flooding Statistics
--------------------------------------------------
relaysel/node: 5.06
avg_sec/relaysel_life: 22.41
suppressed_LSAs: 684633
relay_flood_LSAs: 235230
nonrelay_flood_LSAs: 19874

User Traffic Analysis
--------------------------------------------------
UDP sends: 8897 pkts, 604996 bytes
UDP receives: 6744 pkts, 458592 bytes
UDP forwards: 11986 pkts, 815048 bytes

Delivery Ratio:  0.758

./random_waypoint_manet-opt wireless_interface=2 wireless_flooding=2 
HelloInterval=2 DeadInterval=6 RxmtInterval=7 AckInterval=1000 
BackupWaitInterval=500 AdjConnectivity=1 LSAFullness=2 num_nodes=100 
radio_range=125 velocity=10 start_time=1800 stop_time=2700

OSPFv3 Statistics
           | Packets          Bytes         Kbps
----------------------------------------------------
Hello       |   45000       6765840       60.14
LSAck       |  108853      24559668      218.31
LSR         |   13127        708996        6.30
DBDESC      |  338111     319843964     2843.06
LSU         |  379842     125655024     1116.93
  LSUfld    |    188050      81459824      724.09
  LSUuni    |    191792      44195200      392.85
    LSUcol  |        5063       2342364       20.82
    LSUrxmt |      157896      33947044      301.75
    LSUdbex |       12677       3818744       33.94
    LSUstale|       16156       4087048       36.33
            |
Total       |  884933     477533492     4244.74

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 19.76
OSPF 2way_neighbor_changes/node/sec: 1.34
avg_sec/OSPF 2way neighbor_life: 30.44
OSPF adjacencies/node: 14.84
OSPF adjacency_changes/node/sec: 0.85
avg_LSAsOutSync: 0.11
Secs per router-LSA origination:  7.12
Route changes/node/sec:  90.93
Accumulated adjacencies/node:  -0.58

Flooding Statistics
--------------------------------------------------
relaysel/node: 5.61
avg_sec/relaysel_life: 15.52
suppressed_LSAs: 870237
relay_flood_LSAs: 345020
nonrelay_flood_LSAs: 56567

User Traffic Analysis
--------------------------------------------------
UDP sends: 8897 pkts, 604996 bytes
UDP receives: 6660 pkts, 452880 bytes
UDP forwards: 14987 pkts, 1019116 bytes

Delivery Ratio:  0.749