Subject: [Ospf-manet] new software snapshot

From: "Henderson, Thomas R" <[email-masked]>
Date: Mon, 6 Feb 2006 17:24:52 -0800

We've posted a new snapshot of the simulator (and corresponding quagga
implementation patch) at the following URL:
http://hipserver.mct.phantomworks.org/ietf/ospf/

I've posted some release notes below.  We are going to continue to work
on adding Pratik's proposed changes to the simulator in the meantime,
and will release that as soon as available.  I'll send a separate mail
later this week describing our near-term simulation plans.  We're
putting this snapshot out now for the benefit of those who might want to
experiment with it themselves.

Tom and Phil

RELEASE NOTES: OSPF MANET version 0.8 (February 1, 2006)

Changes to the MANET code since 0.7 release (Oct. 25, 2005):

Quagga 0.98.5
-------------
We have upgraded the code base from Quagga 0.98.4 to 0.98.5

Overlapping Relays and Smart Peering
------------------------------------

1. Added changes to the Smart Peering code provided by Stan Ratliff
   from Cisco.  Code added by Stan is noted in the code.  The largest
   change was to add an additional SPF calculation that is performed
   only over synchronized adjacencies.
2. Section 4.4 of the SP draft was previously not implemented.  It has 
   now been implemented with the method where flooding is not performed 
   over non-adjacent links.  Therefore, the MPR selection algorithm only

   uses adjacent links for one and 2-hop neighbors.
3. Bug fix:  Router-LSAs were not being originated as often as necessary

   because routeability of unsynchronized adjacencies was being checked 
   against the unsynchronized spf table.  The synchronized (adjacencies 
   only) spf table is now used to determine when a router-LSA should be 
   originated.
4. Bug fix:  The synchronized spf table (spf_table_sync) was being built

   using links in its own router-LSA that were unsynchronized.  The SPF 
   calculation was changed to use only synchronized links when the 
   synchronized SPF table is calculated.
5. Bug fix:  Each time an LSA was installed with ospf6_spf_install() the

   neighbors were checked for routeability and adjacencies where
updated.  
   However, it was found that this method was not working because the
SPF 
   was not being run prior to checking for routeability.  Therefore, the
   routeability check and the adjacency update was moved to after each
   SPF calculation.
6. Optimization:  If a new router-LSA is originated due to a neighbor
down 
   event then the router-LSA is not flooded until after any necessary 
   adjacencies are formed or the minLSInterval has passed.  This
corrects 
   the possible problem that a neighbor down event causes an LSA flood,
but 
   then the OSPF router has to wait MinLSInterval before announcing any
new 
   adjacencies (formed from previously unsynchronized neighbors).

MANET Designated Routers
------------------------

1. Bug fix:  In the MDR protocol,
   if an adjacency forms between nodes A and B, and then node A
   drops B because of the inactivity timer and then receives
   a Hello from B, while node B never drops A, then node A may
   not bring the adjacency back up.  The reason has to do with
   the neighbor variable dependent_selector, which node A will
   set to 0 when it loses node B.  To fix this, a Dependent Neighbor
   List (DNL) TLV is used.  The DNL TLV is included in each Hello, along
   with the RNL, so a router always knows whether a neighbor considers
   the router to be dependent.
2. The backup dependent neighbors are no longer selected, since there
   is no longer any reason to distinguish between them and dependent
   neighbors. Related to this, need_adjacency()is greatly simplified
   and no longer depends on AdjConnectivity.  Instead dependent
neighbors
   depend on AdjConnectivity, and only neighboring MDR/BMDRs that should
   be adjacent are now dependent. (This is analogous to parents, since
   parents are also MDR/BMDR neighbors that should be adjacent.) 

3. For equal comparison with Overlapping Relays and Smart Peering, 
   adjacencies are never torn down.

New statistics
--------------
- Sec/Router-LSA Origination/Node:  The number of seconds that a router
waits
before reoriginating its router-LSA.
- Route changes/node/sec: We are now printing out the number of times a
route changes per node per second, as observed in the forwarding table,
to get a sense of route stability of the various approaches.
- Accumulated adjacencies/node:  We are printing the number of
adjacencies that 
are accumlated per node from the start of statitics gathering to the end
of
the simulation.  A negative value indicates that there are fewer
adjacencies
at the end of the simulation than at the start of the statisics
gathering.

New scripts for random_waypoint_manet directory
----------------------------------------

1. comp_density_or.pl:  This script runs random_waypoint_manet with
Overlapping
   Relays (OR)s and varies the radio range and number of nodes.  The
results 
   provide information on the performance of ORs with varying density.

2. comp_density_mdr.pl:  This script runs random_waypoint_manet with
MANET 
   Designated Routers (MDR)s and varies the radio range and number of
nodes.
   The results provide information on the performance of MDRs with
varying 
   density. 

3. comp_mdr_or-sp.pl:  This script runs random_waypoint_manet and
compares:
   1. MDRs with uniconnected adjacencies and full LSAs  
   2. MDRs with biconnected adjacencies and min-cost LSAs  
   3. ORs with smart peering and full LSAs. 

NOTE:  Script 1 and 2 attempt to recreate the scenarios shown by
       Stan Ratliff at IETF-64 OSPF WG meeting.  

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

---

From: Richard Ogier <[email-masked]>
Date: Wed, 08 Feb 2006 09:19:58 -0800

All,

I ran one case from the script file, which attempts to
recreate the simulations that Stan presented at the last
IETF meeting.  I ran 50 nodes with range = 200.
This time the results are quite different!

For OR/SP the overhead is 1117.68 kbps and the delivery ratio is 0.819.
For MDR, the overhead is 530.30 kbps and the delivery ratio is 0.826.

 From a message posted 12/15/2005:
Richard wrote:

 > I think this is a significant advantage of OSPF-MDR.  The pruning is 
straightforward
 > and is similar to what OSPF does in a broadcast network.  I.e., it is 
based
 > on the requirement that each adjacency must have an MDR or BMDR as 
one endpoint.

Acee wrote:

 >> I agree that pruning is more simpler and more intuitive than with 
smart peering.  However,
 >> what matters the most are the other metrics (overhead, delivery 
ratio, stretch factor) in
 >> the various mobility scenarios.

I agree.  But OSPF-MDR is pretty much the same as it was almost a year ago,
and so far I have not seen any proposal that performs better than it.
Maybe you are implying that Cisco (or someone) will eventually find a better
solution?

Richard

---

From: Richard Ogier <[email-masked]>
Date: Thu, 09 Feb 2006 18:06:08 -0800

I used the new GTNetS code to simulate OSPF-MDR with 100 nodes and
range = 250, using 1-connected adjacencies and min-cost LSAs.
I probably should be more patient in reporting results, but I am excited
about these results and maybe it will get others to try out the simulation
software.  The statistics output is shown below.  I like the overhead and
delivery ratio.  It would be nice to compare this to OR/SP, but they do not
yet have partial-topology LSAs.

This simulation took about 2 hours to run.  Note the values of the 
parameters
RxmtInterval, BackupWaitInterval, and AckInterval, which are the preferred
values for OSPF-MDR.  Note that the biggest contributor to overhead is 
Hello packets
(full Hellos were used), but differential Hellos can be used to reduce this.

Richard

./random_waypoint_manet-opt wireless_interface=2 wireless_flooding=2 
HelloInterval=2 DeadInterval=6 RxmtInterval=7 AckInterval=1000 
BackupWaitInterval=500 AdjConnectivity=1 LSAFullness=1 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      14372984      127.76
LSAck       |   69004       9851264       87.57
LSR         |     375         21060        0.19
DBDESC      |    9095       8633920       76.75
LSU         |   26405       6760080       60.09
  LSUfld    |     19279       5240508       46.58
  LSUuni    |      7126       1519572       13.51
    LSUcol  |          39         17776        0.16
    LSUrxmt |        6565       1384588       12.31
    LSUdbex |         374         89744        0.80
    LSUstale|         148         27464        0.24
            |
Total       |  149879      39639308      352.35

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 62.40
OSPF 2way_neighbor_changes/node/sec: 1.08
avg_sec/OSPF 2way neighbor_life: 126.44
OSPF adjacencies/node: 2.60
OSPF adjacency_changes/node/sec: 0.03
avg_LSAsOutSync: 0.10
Secs per router-LSA origination:  20.59

Flooding Statistics
--------------------------------------------------
relaysel/node: 3.87
avg_sec/relaysel_life: 47.65
suppressed_LSAs: 358601
relay_flood_LSAs: 25239
nonrelay_flood_LSAs: 1751

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

Delivery Ratio:  0.962
--------------------------------------------------