Subject: RE: [Ospf-wireless-design] OSPF Flooding and Higher Mobility

From: "Henderson, Thomas R" <[email-masked]>
Date: Fri, 4 Nov 2005 16:24:38 -0800

> -----Original Message-----
> From: Acee Lindem [mailto:[email-masked]] 
> Sent: Friday, November 04, 2005 2:40 PM
> To: Henderson, Thomas R
> Cc: [email-masked]
> Subject: Re: [Ospf-wireless-design] OSPF Flooding and Higher Mobility
> 
> Henderson, Thomas R wrote:
> 
> >Acee, first, thanks for providing this information and 
> (eventually) the 
> >code.
> >
> >  
> >
> >>MPRs have the following improvements over the base provided with 
> >>GTNetS:
> >>
> >>     - Smart Peering is fixed to avoid instability by 
> running a second
> >>       SPF to determine if a potential peer is available via a real
> >>       adjacency or unsynchronized adjacency. The adjacency is only 
> >>suppressed
> >>       in the case of connectivity to the SPT via real adjacencies. 
> >>This
> >>       is discussed in the Boeing report but wasn't implemented.
> >>
> >>    
> >>
> >
> >One potential problem that I foresee with this method is that, as 
> >connectivity conditions change in the network, one has to go 
> back and 
> >re-evaluate whether previous decisions to suppress the formation of 
> >adjacencies are still valid.  Are you addressing this issue somehow, 
> >and if so, how?
> >  
> >
> Actually, we are not doing any adjacency pruning. While the 
> discussion has not subsided on this issue my hope would be 
> that any MPR based solution would use the relay state as a 
> parameter for adjacency reduction. However, heretofore this 
> concept has not been fully developed.
> 

Regardless of pruning, do you agree that there is a potential problem of
making a decision to suppress an adjacency but having to later
re-evaluate it (because the path via real adjacencies disappears)?  It
almost seems to me to require (in the extreme) a recheck of all
unsynchronized adjacent neighbors when any topology changes in the
network, or to log some side information, per suppressed adjacency, that
the suppressed adjacency is dependent on certain other full adjacencies
to stay up.

Further, if you are not doing pruning, I'd be curious to understand
whether simulations suggest that there is overhead growth over time as
adjacencies accumulate.  But I think you are saying above that you would
like to do pruning but haven't figured out the details yet.

Tom

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

---

From: Acee Lindem <[email-masked]>
Date: Sun, 06 Nov 2005 21:04:36 -0500

Hi Tom,

See answers inline.

Henderson, Thomas R wrote:

>re-evaluate it (because the path via real adjacencies disappears)? 
>
I believe we handle this case.

> It

We do not this. In the little I've thought about, it almost seems like 
it would pretty
complex.

>like to do pruning but haven't figured out the details yet.
Right - we don't do pruning and over time adjacencies could accumulate 
dependent on the
nature of the topology changes. What is interesting about the results is 
the fact that the overhead
comparisons are significantly different when a lower velocity/pause time 
scenarios are
examined.  This is despite that that smart peering may not be the 
optimal  adjacency  reduction
mechanism.

Thanks,
Acee

---

From: Richard Ogier <[email-masked]>
Date: Sun, 06 Nov 2005 18:31:25 -0800

Acee,

Can you answer my questions below?

Thanks,
Richard

> In the simulations for Smart Peering, what neighbors were included in
> the router-LSAs?  If only adjacent neighbors were included,
> then that could explain the lower overhead obtained for Smart Peering,
> and would also result in highly suboptimal paths
> (much longer than shortest paths).  That is why simulation
> results are not very meaningful unless other measures such
> as average path length and delivery ratio are also presented.
> (The average path length can be obtained from the numbers of UDP
> packets sent/forwarded/received, but I did not see those numbers.)
>
> Also, since Cisco is running SPF twice, once for real adjacencies
> and once for all acceptable links, I would like to know how
> a router knows which non-local links are real adjacencies.
> Does the LSA somehow indicate this?  Is a different Link State ID
> used for real adjacenies versus non-adjacencies?

---

From: Acee Lindem <[email-masked]>
Date: Mon, 07 Nov 2005 18:54:22 -0500

Hi Richard,

See below.

>> packets sent/forwarded/received, but I did not see those numbers.)
All routable neighbor are advertised.

>> Does the LSA somehow indicate this?  
>
A U bit is defined in the unused 8 bits in the LSA link.

>> Is a different Link State ID
Nope.

Thanks,
Acee

---

From: Richard Ogier <[email-masked]>
Date: Mon, 07 Nov 2005 16:08:22 -0800

Acee,

Thanks for your answers.  I was about to send out the following
related message.

I took a closer look at Cisco's simulation results.  Below are the
UDP sends/receives/forwards for 50 nodes, for MDRs and for MPRs.
The most important thing to notice is that the number of UDP forwards
for MPRs is MUCH larger than for MDRs, even though the number of UDP
receives is slightly larger for MDRs.
For example, for 160m, the number of UDP forwards is 3.75 times as
large for MPRs.  This means that the paths computed for MPRs are
much longer than those computed for MDRs.

MDR 50 nodes
------------
Stat/Radio Range        100m    120m    140m    160m    180m    200m
----------------                --------------------------------------------
UDP sends (pkts)        8927    8964    8927    8927    8927    8964
UDP receives (pkts)        4076    5697    6205    6803    7360    7767
UDP Forwards (pkts)        12185    9968    9038    7498    6310    5047

MPR 50 nodes
------------
Stat/Radio Range        100m    120m    140m    160m    180m    200m
----------------                --------------------------------------------
UDP sends (pkts)        8927    8927    8927    8927    8927    8927
UDP receives (pkts)        3446    4839    5697    6262    6964    7436
UDP Forwards (pkts)        40694    30503    26808    28110    22401    
10627

I'm not sure why there is such a big difference in path length,
but it probably means that MDR is advertising more neighbors
in LSAs than MPR. (Maybe MPR is advertising only adjacent neighbors?)
It would be better to compare the two methods using comparable
LSAs that both provide min-hop paths.

In any case, because of the much longer paths obtained with the MPR
method, not much can be concluded from the results.
Also, as Phil pointed out, the number of LSAs out of sync
is much greater for MPRs, which needs to be investigated.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Tue, 08 Nov 2005 08:39:37 -0800

All,

I ran MDR with 1-connected adjacencies on the 50 node scenario
that Cisco used with radio rage = 200 and velocity = 16.
(Cisco used biconnected adjacencies for MDR, which was not a fair
comparison.)
The results are shown below for three choices of LSAFullness:
0 for Minimum LSAs, 2 for MDR Full LSAs, and 3 for Full LSAs.

The resulting delivery ratios were .834, .839, and .849 for MDR,
compared to .833 for MPRs in the same scenario, so delivery ratios
are comparable.

The resulting UDP forwards were 6265, 6255, and 5487 for MDR,
compared to 10627 for MPRs, so much longer paths were obtained
with MPRs.

The resulting total overheads were 177.59, 257.33, and 500.61
(the last one is for Full LSAs) compared to 457.24 for MPRs.

Although MDR with Full LSAs resulted in more overhead than MPRs,
the other two choices of LSAs performed better than MPRs in
all of the above metrics.  The most notable result is the very
long paths produced by MPRs, which is probably caused by a bug.

The detailed results for MDR are given below.

Another point is that Cisco considered very sparse networks
(e.g., radio range = 100m), which frequently partition.
Such networks necessarily have a very low delivery ratio
(e.g., 38%) due to partitions, so I am not sure how important
such scenarios are to us.

Richard

-------------------------------------------------
Results for AdjConn = 1 and LSAFullness = 0:

./random_waypoint_manet-opt wireless_interface=2 wireless_flooding=2 
diff_hellos persistent_mdr HelloInterval=2 RxmtInterval=5 DeadInterval=6 
BackupWaitInterval=2000 AckInterval=1800 MinLSInterval=5 velocity=16 
RouterDeadCount=3 TwoHopRefresh=6 AdjConnectivity=1 LSAFullness=0 
num_nodes=50 start_time=1800 stop_time=2700 radio_range=200

Neighbor statistics (at physical layer):
--------------------------------------------------
Number of nodes: 50
Neighbor threshold distance (m): 200.00
Average neighbor density (neighbors/# of nodes):  0.45
Average neighbor changes/time (changes/sec/node): 0.40

OSPFv3 Statistics
           | Packets          Bytes         Kbps
----------------------------------------------------
Hello       |   22500       2413204       21.45
LSAck       |   20640       3205360       28.49
LSR         |     913         50520        0.45
DBDESC      |   12385       8838596       78.57
LSU         |   29246       5471504       48.64
  LSUfld    |     20401       3782740       33.62
  LSUuni    |      8845       1688764       15.01
    LSUcol  |         122         41344        0.37
    LSUrxmt |        7361       1401920       12.46
    LSUdbex |         876        156828        1.39
    LSUstale|         486         88672        0.79
            |
Total       |   85684      19979184      177.59

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 21.43
OSPF 2way_neighbor_changes/node/sec: 0.72
avg_sec/OSPF 2way neighbor_life: 62.39
OSPF adjacencies/node: 2.80
OSPF adjacency_changes/node/sec: 0.11
avg_LSAsOutSync: 0.21

Flooding Statistics
--------------------------------------------------
relaysel/node: 4.13
avg_sec/relaysel_life: 22.15
suppressed_LSAs: 115555
relay_flood_LSAs: 26708
nonrelay_flood_LSAs: 1489

User Traffic Analysis
--------------------------------------------------
UDP sends: 8927 pkts, 607036 bytes
UDP receives: 7446 pkts, 506328 bytes
UDP forwards: 6265 pkts, 426020 bytes

Delivery Ratio:  0.834
----------------------
----------------------
Results for AdjConn = 1 and LSAFullness = 2:

./random_waypoint_manet-opt wireless_interface=2 wireless_flooding=2 
diff_hellos persistent_mdr HelloInterval=2 RxmtInterval=5 DeadInterval=6 
BackupWaitInterval=2000 AckInterval=1800 MinLSInterval=5 velocity=16 
RouterDeadCount=3 TwoHopRefresh=6 AdjConnectivity=1 LSAFullness=2 
num_nodes=50 start_time=1800 stop_time=2700 radio_range=200

Neighbor statistics (at physical layer):
--------------------------------------------------
Number of nodes: 50
Neighbor threshold distance (m): 200.00
Average neighbor density (neighbors/# of nodes):  0.45
Average neighbor changes/time (changes/sec/node): 0.40

OSPFv3 Statistics
           | Packets          Bytes         Kbps
----------------------------------------------------
Hello       |   22500       2413904       21.46
LSAck       |   21322       4053592       36.03
LSR         |    1021         59340        0.53
DBDESC      |   12285       8778188       78.03
LSU         |   35642      13644084      121.28
  LSUfld    |     26785      10614172       94.35
  LSUuni    |      8857       3029912       26.93
    LSUcol  |         169        107900        0.96
    LSUrxmt |        6861       2250452       20.00
    LSUdbex |        1024        383024        3.40
    LSUstale|         803        288536        2.56
            |
Total       |   92770      28949108      257.33

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 21.41
OSPF 2way_neighbor_changes/node/sec: 0.72
avg_sec/OSPF 2way neighbor_life: 61.95
OSPF adjacencies/node: 2.83
OSPF adjacency_changes/node/sec: 0.11
avg_LSAsOutSync: 0.28

Flooding Statistics
--------------------------------------------------
relaysel/node: 4.17
avg_sec/relaysel_life: 21.73
suppressed_LSAs: 157782
relay_flood_LSAs: 36598
nonrelay_flood_LSAs: 1973

User Traffic Analysis
--------------------------------------------------
UDP sends: 8927 pkts, 607036 bytes
UDP receives: 7489 pkts, 509252 bytes
UDP forwards: 6255 pkts, 425340 bytes

Delivery Ratio:  0.839
----------------------
----------------------
Results for AdjConn = 1 and LSAFullness = 3:

./random_waypoint_manet-opt wireless_interface=2 wireless_flooding=2 
diff_hellos persistent_mdr HelloInterval=2 RxmtInterval=5 DeadInterval=6 
BackupWaitInterval=2000 AckInterval=1800 MinLSInterval=5 velocity=16 
RouterDeadCount=3 TwoHopRefresh=6 AdjConnectivity=1 LSAFullness=3 
num_nodes=50 start_time=1800 stop_time=2700 radio_range=200

Neighbor statistics (at physical layer):
--------------------------------------------------
Number of nodes: 50
Neighbor threshold distance (m): 200.00
Average neighbor density (neighbors/# of nodes):  0.45
Average neighbor changes/time (changes/sec/node): 0.40

OSPFv3 Statistics
           | Packets          Bytes         Kbps
----------------------------------------------------
Hello       |   22500       2416260       21.48
LSAck       |   23129       7721964       68.64
LSR         |    1226         80736        0.72
DBDESC      |   12324       8813560       78.34
LSU         |   57816      37286656      331.44
  LSUfld    |     47926      31242564      277.71
  LSUuni    |      9890       6044092       53.73
    LSUcol  |         312        307032        2.73
    LSUrxmt |        6646       3961992       35.22
    LSUdbex |        1458       1045684        9.29
    LSUstale|        1474        729384        6.48
            |
Total       |  116995      56319176      500.61

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 21.39
OSPF 2way_neighbor_changes/node/sec: 0.73
avg_sec/OSPF 2way neighbor_life: 61.35
OSPF adjacencies/node: 2.83
OSPF adjacency_changes/node/sec: 0.11
avg_LSAsOutSync: 0.47

Flooding Statistics
--------------------------------------------------
relaysel/node: 4.12
avg_sec/relaysel_life: 22.41
suppressed_LSAs: 339546
relay_flood_LSAs: 78496
nonrelay_flood_LSAs: 4173

User Traffic Analysis
--------------------------------------------------
UDP sends: 8927 pkts, 607036 bytes
UDP receives: 7580 pkts, 515440 bytes
UDP forwards: 5487 pkts, 373116 bytes

Delivery Ratio:  0.849

---

From: Abhay Roy <[email-masked]>
Date: Wed, 23 Nov 2005 10:39:41 -0800 (PST)

I have updated the smart peering draft with the "unsynchronized 
adjacencies" details. This is what Stan Ratliff implemented in 
GTNetS and shared some results at OSPF WG meeting.

I have attached a copy with this message.

Regards,
-Roy-