Subject: [Ospf-manet] Min-cost LSAs for multiple interfaces

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

All,

There has been some discussion that the min-cost LSA algorithm
of OSPF-MDR does not apply to multiple interfaces that include
non-MANET interfaces, i.e., does not provide min-hop paths
between any two routers in an area that includes both MANET
and non-MANET interfaces. To address this concern, I have
extended the min-cost LSA algorithm to multiple interfaces,
and a rough draft of the description is given below.

A simple but inefficient solution would be to simply require
a router with multiple interfaces to include all routable
neighbors in its LSA.  This would be inefficient because
it could result in several MANET routers providing redundant
paths between a non-MANET router and another MANET router.

The main change in extending the algorithm to multiple interfaces
is to determine whether any two (MANET or non-MANET) neighbors
are neighbors of each other (via a MANET or non-MANET interface).
For MANET neighbors, the algorithm still uses 2-hop neighbor
information from Hellos. But to allow non-MANET neighbors, the
algorithm also uses router-LSAs and network-LSAs to determine
whether two neighbors are neighbors of each other, and to
determine the cost of the link between them.

Richard

C.  Min-Cost LSA Algorithm

This section describes the algorithm for determining which neighbors
to include in the router-LSA when LSAFullness is 1 or 2 (min-cost LSAs).
The algorithm assumes that a router may have multiple interfaces, at least
one of which is a MANET interface.
The input to this algorithm includes, for each MANET interface,
the set of routable neighbors and the the Reported Neighbor List (RNL)
for each bidirectional neighbor on the interface.
The input also includes the router-LSA originated by each bidirectional
neighbor (on any interface), and the network-LSA for each transit
broadcast or NBMA network to which any such neighbor is attached.

The output of the algorithm is the set of advertised neighbors to
be included in the router-LSA, for each MANET interface.
The min-cost LSA algorithm must be run to possibly originate a
new router-LSA whenever any of the following events occurs:

o  The set of routable neighbors changes.
o  The Reported Neighbor List or Report2Hop changes for a neighbor.
o  A new router-LSA originated by a neighbor is received.

If LSAFullness = 1, then the min-cost LSA algorithm ensures
that the router-LSAs (of the router and its neighbors) provide
at least one shortest path between each pair of neighbors
(including neighbors on non-MANET interfaces).
If LSAFullness = 2, then the algorithm ensures that the router-LSAs
provide at least two shortest paths between each pair of neighbors.
Although it is straightforward to extend the algorithm to
provide three or more paths, the algorithm is described only
for one or two paths.  If more than two paths are desired,
then it is probably better to use full LSAs.

The min-cost LSA algorithm may also use metric information that
may be advertised in Hellos.  If this option is used, then each router
will advertise the cost to each routable neighbor in Hello packets via
an LLS TLV. (The format for advertising this information will
be described in a future version of this draft.)
If this option is used, then shortest paths that are calculated
based on min-cost LSAs will have minimum cost in all cases,
without any conditions on the metrics.

If this option is not used (i.e., metric information is not
included in Hellos), then minimum-cost paths will still be
calculated if the metrics for all neighbors on the same interface
are equal, and min-hop paths will be calculated if all metrics
in the network are equal.

For convenience, in the following description, the term "neighbor"
will refer to a neighbor on any interface that is
bidirectional (in state 2-Way or greater).
Also, node i will denote the router doing the calculation.
To perform the min-cost LSA algorithm, the following steps are performed.

(1) Create the neighbor connectivity matrix NCM for each MANET interface,
as described in Section 5.1.  Create the multiple-interface neighbor
connectivity matrix MNCM as follows.  MNCM(j,k) is set to 1 if NCM(j,k)
equals 1 for any MANET interface.  MNCM(j,k) is also set to 1 if j
appears in k's router-LSA and k appears in j's router-LSA.
MNCM(j,k) is also set to 1 if j and k are both attached
to the same transit broadcast or NBMA network, and the network-LSA
for that transit network exists and includes both j and k.
Otherwise, MNCM(j,k) is set to 0.

(2) Create the Hello cost matrix HCM as follows.  For each pair j, k
of routers such that j is a neighbor, and k is either a neighbor
or node i itself:

(a) If j and k are neighbors of each other (based on MNCM):
If router j is reporting neighbor metrics in its Hellos (this is optional),
then set HCM(j,k) to the metric reported by router j to its neighbor k;
otherwise set HCM(j,k) = 0.  We assume that routers with multiple
interfaces do not report metrics in Hellos. (The reporting of metrics
in Hellos may be extended to multiple interfaces in a future version
of this draft.)

(b) If j and k are not neighbors of each other (MNCM(j,k) = 0),
set HCM(j,k) to LSInfinity.

(3) Create the LSA cost matrix LCM as follows. Initialize LCM(j,k)
to LSInfinity for each pair of neighbors j and k. For each
neighbor j:

(a) Find the router-LSA originated by neighbor j. If the LSA
does not exist in the database, examine the next neighbor.

(b) For each point-to-point connection described in the router-LSA,
set LCM(j,k) to the metric for the connection, where k is the
neighbor advertised for the connection. If the router-LSA contains
multiple connections to k via different interfaces, set LCM(j,k)
to the smallest metric for these connections.

(c) If the router-LSA for j indicates that j is attached to
a transit broadcast or NBMA network, with metric M, and the
network-LSA for this network exists and includes k, set LCM(j,k)
to M.  If j is attached to multiple such networks that include k,
set LCM(j,k) to the smallest such metric.

(4) Initialize the set of advertised neighbors to include all neighbors
in the Full state. Let metric(i,j) denote the router's own metric to
each neighbor j.  If j is a neighbor on multiple interfaces, let
metric(i,j) be the smallest such metric.

(5) For each pair j, k of routable neighbors (which may or may
not be neighbors of each other):

(a) Find the neighbor u with the minimum value of HCM(j,u) + LCM(u,k),
if such a neighbor exists such that this sum is less than HCM(j,k).
(Note that HCM(j,k) = LSInfinity if j and k are not neighbors
of each other.)
If multiple neighbors achieve this minimum value, choose the one
that maximizes (MDR Level, RtrPri, RID).

(b) If the router itself (node i) is currently advertising neighbor
k in its router-LSA:  If either HCM(j,i) + metric(i,k) <
HCM(j,u) + LCM(u,k), or HCM(j,i) + metric(i,k) = HCM(j,u) + LCM(u,k)
and the router itself has a larger value of (MDR Level, RtrPri, RID)
than neighbor u, or if u does not exist and
HCM(j,i) + metric(i,k) < HCM(j,k), add k to the set of advertised
neighbors (k will continue to be advertised).

(c) Else (the router is not currently advertising neighbor k):
If HCM(j,i) + metric(i,k) < HCM(j,u) + LCM(u,k),
or if u does not exist and HCM(j,i) + metric(i,k) < HCM(j,k),
add k to the set of advertised neighbors.

If the option of providing two paths between each pair of neighbors
is elected (LSAFullness = 2), then the following step 6
is performed instead of step 5 above.

(6) For each pair j, k of routable neighbors (which may or may not
be neighbors of each other):

(a) Choose neighbor u as in step 5(a). Let v be the neighbor, excluding
node u (if it exists), with the minimum value of HCM(j,v) + LCM(v,k),
if such a neighbor exists such that this sum is less than LSInfinity.
If multiple neighbors achieve this minimum value, choose the one
that maximizes (MDR Level, RtrPri, RID).

(b) If the router itself (node i) is currently advertising neighbor
k in its router-LSA:  If either HCM(j,i) + metric(i,k) <
HCM(j,v) + LCM(v,k), or HCM(j,i) + metric(i,k) = HCM(j,v) + LCM(v,k)
and the router itself has a larger value of (MDR Level, RtrPri, RID)
than neighbor v, or if v does not exist and
HCM(j,i) + metric(i,k) < LSInfinity, add k to the set of advertised
neighbors (k will continue to be advertised).

(c) Else (the router is not currently advertising neighbor k):
If HCM(j,i) + metric(i,k) < HCM(j,v) + LCM(v,k),
or if v does not exist and HCM(j,i) + metric(i,k) < LSInfinity,
add k to the set of advertised neighbors.

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

---

From: Philippe Jacquet <[email-masked]>
Date: Tue, 14 Feb 2006 10:22:13 +0100

Richard,

You try to remedy to the problem of the shortest path in MDR. Your last 
fix with hybrid nodes is now closer to MPRs. You probably know the MPR 
property that tells that the minimal set of links needed to be known by 
a node to compute the shortest path to any other node is

1. the direct neighbourhood of the node

2. the MPR links of the other nodes

Therefore whatever you try to minimize the number of advertised links, 
advertizing the MPR links is a kind of minimum.

As we mentionned earlier the optimization on hybrid nodes is just 
equivalent to indirectly compute the MPR through hybrid nodes by knowing 
information about their non-MANET neighbors. Anyhow it means that one 
must interleave information obtained from non-MANET neighbors which may 
affect classic OSPF functionality. If the hybrid node is isolated (which 
may be the case frequently) then it will be equivalent to select the 
whole wireless neighbor of the hybrid nodes since all neighbor will 
select this hybrid node as MPR (therefore one needs not interleave with 
classic OSPF). If some hybrid nodes are close enough, then one can 
factor some common wireless nodes but this will need the interleave. But 
this is just an application of MPRs.

Clearly the MPR concept is a natural extension of OSPF and is well 
proven in MANET.

Philippe

---

From: Richard Ogier <[email-masked]>
Date: Tue, 14 Feb 2006 08:48:25 -0800

Philippe,

Philippe Jacquet wrote:

> Richard,
>
> You try to remedy to the problem of the shortest path in MDR. Your 
> last fix with hybrid nodes is now closer to MPRs. You probably know 
> the MPR property that tells that the minimal set of links needed to be 
> known by a node to compute the shortest path to any other node is 

The purpose of my message was simply to extend the min-cost LSA algorithm to
multiple interfaces in a straightforward maner.  I was not even thinking 
of MPRs.
It would be more important for you to address the issues of performance when
trying to use MPRs to extend OSPF, such as my recent simulation results 
that showed
that using MPR adjacencies can result in 13 times as many new 
 adjacencies per second
as 1-connected MDRs in a 100 node network.  More comments below.

> equivalent to indirectly compute the MPR through hybrid nodes by 
> knowing information about their non-MANET neighbors. Anyhow it means 
> that one must interleave information obtained from non-MANET neighbors 
> which may affect classic OSPF functionality. If the hybrid node is 
> isolated (which may be the case frequently) then it will be equivalent 
> to select the whole wireless neighbor of the hybrid nodes since all 
> neighbor will select this hybrid node as MPR (therefore one needs not 
> interleave with classic OSPF). 

The nice thing about min-cost LSAs is that the router itself (not the 
neighbors - MPR selectors) decides which
neighbors to include in its router-LSA, based on neighbors' LSAs. 
 Therefore this extends in a straightforward
manner to allow non-MANET neighbors.  Other advantages have been 
discussed, such as my message
posted 1/17/2006.

> If some hybrid nodes are close enough, then one can factor some common 
> wireless nodes but this will need the interleave. But this is just an 
> application of MPRs.

The min-cost LSA algorithm for multiple interfaces does this automatically.
But I don't think this is an important issue.  Performance is more 
important.

> Clearly the MPR concept is a natural extension of OSPF and is well 

This is not clear to me.  MDRs of course generalize the DR of an OSPF 
broadcast network.
(In fact, in a fully connected MANET, the selected MDR is the same 
router that would
be selected by OSPF's DR election algorithm.)  And OSPF-MDR reduces the 
number of
adjacencies in a manner similar to the way OSPF reduces adjacencies in a 
broadcast network.

Anyway, if you want to show that using MPRs is a good way to extend 
OSPF, then I would
like to see how it performs in detailed simulations, such as GTNetS.
However, based on my simulation results, using MPR adjacencies
will result in much more overhead than using MDRs.

Richard

---

From: Philippe Jacquet <[email-masked]>
Date: Wed, 15 Feb 2006 18:27:28 +0100

Richard,

Did you simulate your min-cost LSA? Added to MDR links, they surely 
generate much larger overhead rate than MPRs.

Best regards,

Philippe

Richard Ogier wrote:

>> the MPR property that tells that the minimal set of links needed to 
>> be known by a node to compute the shortest path to any other node is 
>
>
>
> multiple interfaces in a straightforward maner.  I was not even 
> thinking of MPRs.
> trying to use MPRs to extend OSPF, such as my recent simulation 
> results that showed
>> Therefore whatever you try to minimize the number of advertised 
>> links, advertizing the MPR links is a kind of minimum.
>
>
>>
>> that one must interleave information obtained from non-MANET 
>> neighbors which may affect classic OSPF functionality. If the hybrid 
>> node is isolated (which may be the case frequently) then it will be 
>> equivalent to select the whole wireless neighbor of the hybrid nodes 
>> since all neighbor will select this hybrid node as MPR (therefore one 
>> needs not interleave with classic OSPF). 
>
>
>
>> If some hybrid nodes are close enough, then one can factor some 
>> common wireless nodes but this will need the interleave. But this is 
>> just an application of MPRs.
>
>
>
> be selected by OSPF's DR election algorithm.)  And OSPF-MDR reduces 
> the number of
> adjacencies in a manner similar to the way OSPF reduces adjacencies in 
> a broadcast network.
>

---

From: Richard Ogier <[email-masked]>
Date: Thu, 16 Feb 2006 15:00:08 -0800

All,

I want to discuss the importance of partial-topology LSAs
and present some preliminary simulation results.
I think that most of us agree that partial-topology LSAs
are important for scalability, but I also think it is
appropriate to consider them now, for the following reasons:

o  To achieve scalability to networks of 100 nodes or more, it is
necessary to use both partial-topology LSAs and partial-topology
adjacencies, as shown in Boeing's tech report and to be further
shown in simulation results to be presented soon.

o  Full topology LSAs generate so much overhead that they make it
impossible to evaluate the core flooding mechanism in larger
networks.  Note that the *same* core flooding mechanism is
used, whether partial or full-topology LSAs are used.

o  OSPF-MDR has had partial-topology LSAs for about a year now,
and Smart Peering (SP) also uses partial-topology LSAs when only
synchronized adjacencies are included in LSAs, i.e., when
unsynchronized adjacencies (UnsynchAdj) are not enabled.

Regarding this last point, OR/SP without UnsynchAdj uses "minimal"
LSAs that include only synchronized neighbors.  Similarly, the
minimal LSA option of OSPF-MDR also includes only synchronized
neighbors in LSAs.

I believe that the MPRs and synchronized adjacencies (and therefore
the core flooding mechanism) depend only on the synchronized neighbors
in LSAs, and are therefore independent of whether LSAs contain any
unsynchronized neighbors in addition to the required synchronized
neighbors.  Therefore, we can evaluate the core flooding mechanism
without using full-topology LSAs, thus allowing evaluation in
larger networks.

Since OR/SA without UnsynchAdj uses "minimal" LSAs that do not provide
min-hop paths, it is possible to add a subset of unsynchronized
neighbors to LSAs in order to provide shorter paths, e.g.,
min-hop paths.  (In fact, this is what the the min-cost LSA algorithm
of OSPF-MDR does.)  Adding additional neighbors to the LSA results
in some additional overhead.  Therefore, using "minimal" LSAs
results in the minimum overhead of any choice of LSAs which
include the required synchronized neighbors.

I was curious to see what this minimum overhead is for OR/SA
without UnsynchAdj, and to compare it to the overhead for
OSPF-MDR with minimal LSAs and min-cost LSAs.

(Note, however, that OR/SA without UnsynchAdj allows only
synchronized neighbors to be selected as a next hop in SPF, unlike
OSPF-MDR which allows any routable neighbor as a next hop.
Therefore, although it is fair to compare the overhead, it would
not be fair to compare path length or delivery ratio.)

Before presenting simulation results, I want to mention that
Phil determined the reason for the incorrect results I posted
on Monday: The MinLSInterval parameter can be overwritten if a
"make clean" is not performed. This explains why the average
time between originating LSAs was less than 5 sec.  I will rerun
the simulations and post the corrected results next week.

The simulation results presented below are only for one scenario
which I consider challenging: 100 nodes with range = 250.
(Grid size is 500.)  Additional simulations will be performed soon.
For OR/SP, I used the parameter values recommended by Cisco:
RxmtInterval=9 AckInterval=500 PushbackInterval=7000.

The following table summarizes the results, comparing total overhead,
average number of adjacencies per node, and adjacency change rate.
(Delivery ratio is also included.)
Detailed results are given at the end of this message.

                           Overhead   Adj/node  Adj changes/node/s  Del.
    ratio
                          
    --------------------------------------------------
    MDR w/ minimal LSAs     277.22 kbps   2.57        0.03          0.960
    MDR w/ min-cost LSAs    352.35 kbps   2.60        0.03          0.962
    OR/SP w/o UnsynchAdj   1023.54 kbps   9.21        0.12          0.944

Richard

--------------------------------------------------
1-connected MDR, minimal LSAs:

./random_waypoint_manet-opt wireless_interface=2 wireless_flooding=2 
HelloInterval=2 DeadInterval=6 RxmtInterval=7 AckInterval=1000 
BackupWaitInterval=500 AdjConnectivity=1 LSAFullness=0 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      14375380      127.78
LSAck       |   53268       5099488       45.33
LSR         |     369         19440        0.17
DBDESC      |    8587       8132240       72.29
LSU         |   14208       3561000       31.65
  LSUfld    |      9396       2723620       24.21
  LSUuni    |      4812        837380        7.44
    LSUcol  |          12          5532        0.05
    LSUrxmt |        4379        755596        6.72
    LSUdbex |         372         65932        0.59
    LSUstale|          49         10320        0.09
            |
Total       |  121432      31187548      277.22

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 62.43
OSPF 2way_neighbor_changes/node/sec: 1.07
avg_sec/OSPF 2way neighbor_life: 128.49
OSPF adjacencies/node: 2.57
OSPF adjacency_changes/node/sec: 0.03
avg_LSAsOutSync: 0.09
Secs per router-LSA origination:  49.29

Flooding Statistics
--------------------------------------------------
relaysel/node: 3.95
avg_sec/relaysel_life: 52.07
suppressed_LSAs: 153170
relay_flood_LSAs: 11147
nonrelay_flood_LSAs: 741

User Traffic Analysis
--------------------------------------------------
UDP sends: 8897 pkts, 604996 bytes
UDP receives: 8545 pkts, 581060 bytes
UDP forwards: 3724 pkts, 253232 bytes

Delivery Ratio:  0.960
--------------------------------------------------

1-connected MDR, min-cost LSAs:

./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
--------------------------------------------------

OR/SP without UnsynchAdj:

./random_waypoint_manet-opt wireless_interface=2 wireless_flooding=1 
HelloInterval=2 DeadInterval=6 RxmtInterval=9 AckInterval=500 
PushbackInterval=7000 SmartPeering 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      15190308      135.02
LSAck       |  109189      13656964      121.40
LSR         |    3408        284604        2.53
DBDESC      |   34387      33660996      299.21
LSU         |  151591      52355320      465.38
  LSUfld    |    120178      41551084      369.34
  LSUuni    |     31413      10804236       96.04
    LSUcol  |         232        137796        1.22
    LSUrxmt |       25448       7578112       67.36
    LSUdbex |        4086       2629968       23.38
    LSUstale|        1647        458360        4.07
            |
Total       |  343575     115148192     1023.54

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 62.11
OSPF 2way_neighbor_changes/node/sec: 1.25
avg_sec/OSPF 2way neighbor_life: 107.59
OSPF adjacencies/node: 9.21
OSPF adjacency_changes/node/sec: 0.12
avg_LSAsOutSync: 0.88
Secs per router-LSA origination:  14.48
Route changes/node/sec:  18.30
Accumulated adjacencies/node:  -6.52

Flooding Statistics
--------------------------------------------------
relaysel/node: 4.46
avg_sec/relaysel_life: 49.25
suppressed_LSAs: 443347
relay_flood_LSAs: 148455
nonrelay_flood_LSAs: 36480

User Traffic Analysis
--------------------------------------------------
UDP sends: 8897 pkts, 604996 bytes
UDP receives: 8396 pkts, 570928 bytes
UDP forwards: 13461 pkts, 915348 bytes

Delivery Ratio:  0.944

---

From: "Joe Macker" <[email-masked]>
Date: Fri, 17 Feb 2006 16:47:55 -0500

Richard:

First off I agree that partial topology LSAs are very important for first
order scaling properties as shown in the Boeing report. This is probably
enough of an argument in my opinion for the MANET-OSPF work and meets our
initial design goals.

Regarding the generalization of scaling of full LSAs other methods of
extending MPRs (and MDRs or any CDS algorithm) to provide hybrid fuzzy
sighted link state have been done in the past and this shows good overhead
scaling properties.  This even holds true for full LSAs.

Macker J.P., J. Dean "A Study of Link State Flooding Optimizations for
Scalable Wireless Networks", in IEEE Milcom 2003 Proceedings, Oct 2003.

This is based on previous BBN work but we combined the use of CDS algorithms
in our previous study. At the time we happened to have MPR now we have
ECDS,etc as well.

I am not suggesting this as a MANET-OSPF solution right now. Just that for
large scaling there are likely complementary engineering approaches that can
be taken and may even allow full LSA use if some reason that makes sense.  I
see this as complementary as it may help partial or full link state LSAs.

Cheers,
Joe

>-----Original Message-----
>From: [email-masked] 
>[mailto:[email-masked]] On Behalf Of Richard Ogier
>Sent: Thursday, February 16, 2006 6:00 PM
>To: [email-masked]
>Subject: [Ospf-manet] Partial-topology LSAs
>
>All,
>
>I want to discuss the importance of partial-topology LSAs and 
>present some preliminary simulation results.
>I think that most of us agree that partial-topology LSAs are 
>important for scalability, but I also think it is appropriate 
>to consider them now, for the following reasons:
>
>o  To achieve scalability to networks of 100 nodes or more, it 
>is necessary to use both partial-topology LSAs and 
>partial-topology adjacencies, as shown in Boeing's tech report 
>and to be further shown in simulation results to be presented soon.
>
>o  Full topology LSAs generate so much overhead that they make 
>it impossible to evaluate the core flooding mechanism in 
>larger networks.  Note that the *same* core flooding mechanism 
>is used, whether partial or full-topology LSAs are used.
>
>o  OSPF-MDR has had partial-topology LSAs for about a year 
>now, and Smart Peering (SP) also uses partial-topology LSAs 
>when only synchronized adjacencies are included in LSAs, i.e., 
>when unsynchronized adjacencies (UnsynchAdj) are not enabled.
>
>I believe that the MPRs and synchronized adjacencies (and 
>therefore the core flooding mechanism) depend only on the 
>synchronized neighbors in LSAs, and are therefore independent 
>of whether LSAs contain any unsynchronized neighbors in 
>addition to the required synchronized neighbors.  Therefore, 
>we can evaluate the core flooding mechanism without using 
>full-topology LSAs, thus allowing evaluation in larger networks.
>
>Since OR/SA without UnsynchAdj uses "minimal" LSAs that do not 
>provide min-hop paths, it is possible to add a subset of 
>unsynchronized neighbors to LSAs in order to provide shorter 
>paths, e.g., min-hop paths.  (In fact, this is what the the 
>min-cost LSA algorithm of OSPF-MDR does.)  Adding additional 
>neighbors to the LSA results in some additional overhead.  
>Therefore, using "minimal" LSAs results in the minimum 
>overhead of any choice of LSAs which include the required 
>synchronized neighbors.
>
>synchronized neighbors to be selected as a next hop in SPF, 
>unlike OSPF-MDR which allows any routable neighbor as a next hop.
>Therefore, although it is fair to compare the overhead, it 
>would not be fair to compare path length or delivery ratio.)
>
>time between originating LSAs was less than 5 sec.  I will 
>rerun the simulations and post the corrected results next week.
>
>The simulation results presented below are only for one 
>scenario which I consider challenging: 100 nodes with range = 250.
>The following table summarizes the results, comparing total 
>overhead, average number of adjacencies per node, and 
>adjacency change rate.
>BackupWaitInterval=500 AdjConnectivity=1 LSAFullness=0 
>num_nodes=100 radio_range=250 velocity=10 start_time=1800 
>stop_time=2700
>
>Average neighbor density (neighbors/# of nodes):  0.63 Average 
>neighbor changes/time (changes/sec/node): 0.46
>
>OSPFv3 Statistics
>           | Packets          Bytes         Kbps
>OSPF 2way_neighbor_changes/node/sec: 1.07 avg_sec/OSPF 2way 
>neighbor_life: 128.49 OSPF adjacencies/node: 2.57 OSPF 
>adjacency_changes/node/sec: 0.03
>avg_LSAsOutSync: 0.09
>BackupWaitInterval=500 AdjConnectivity=1 LSAFullness=1 
>num_nodes=100 radio_range=250 velocity=10 start_time=1800 
>stop_time=2700
>
>Average neighbor density (neighbors/# of nodes):  0.63 Average 
>neighbor changes/time (changes/sec/node): 0.46
>
>OSPFv3 Statistics
>           | Packets          Bytes         Kbps
>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
>PushbackInterval=7000 SmartPeering num_nodes=100 
>Average neighbor density (neighbors/# of nodes):  0.63 Average 
>neighbor changes/time (changes/sec/node): 0.46
>
>OSPFv3 Statistics
>           | Packets          Bytes         Kbps
>OSPF 2way_neighbor_changes/node/sec: 1.25 avg_sec/OSPF 2way 
>neighbor_life: 107.59 OSPF adjacencies/node: 9.21 OSPF 
>adjacency_changes/node/sec: 0.12
>avg_LSAsOutSync: 0.88

---

From: Richard Ogier <[email-masked]>
Date: Fri, 17 Feb 2006 15:45:32 -0800

Joe,

I think FSLS routing assumes periodic flooding rather than
reliable flooding, although one could argue that in highly mobile
dense network, OSPF ends up flooding every MinLSInterval anyway,
so one could use different values of MinLSInterval for different
flooding ranges.  If FSLS were used in OSPF, a router would
intentionally be out of sync with a neighbor for some interval
(because the neighbor exceeds some hop count from the originator
of the LSA), which seems contrary to OSPF which always tries
to synchronize databases with adjacent neighbors.

I think it is possible to add FSLS and other enhancements to OSPF-MANET
later, but I think we should focus on the core flooding protocol now.
One reason to consider partial-topology LSAs now is so that the
core flooding protocol can be evaluated in larger networks.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Tue, 21 Feb 2006 08:29:26 -0800

All,

Using the updated code for OR/SA, I reran my simulation
comparing OR/SA without unsynchronized adjacencies (UnsynchAdj)
to OSPF-MDR with minimal LSAs in a 100 node network.
(Refer to my original message with the same subject
for the purpose/relevance of this experiment.)
Recall that OR/SP without UnsynchAdj uses "minimal" LSAs
that include only synchronized neighbors, similar to
the minimal LSA option of OSPF-MDR, and that the
core flooding mechanism is not affected by including
only synchronized neighbors in LSAs.

(Again, note that OR/SA without UnsynchAdj allows only

The simulation for MDR with minimal LSAs took 71 minutes,
compared to 382 minutes for OR/SP.  One possible reason is
that all non-MPRs are backups and therefore must process
the pushback list whenever an LSA or LS Ack is received.

The following table summarizes the results, comparing total overhead,
average number of adjacencies per node, and adjacency change rate.
(Delivery ratio is also included.) Results are given for both the
previous version and the updated version of OR/SP.  Detailed results
for the updated version of OR/SP are given at the end of this message.

                         Overhead   Adj/node  Adj changes/node/s  del_ratio
                         --------------------------------------------------
    MDR w/ minimal LSAs     277.22 kbps   2.57        0.03          0.960
    MDR w/ min-cost LSAs    352.35 kbps   2.60        0.03          0.962
    OR/SP w/o UnsynchAdj   1023.54 kbps   9.21        0.12          0.944
    OR/SP w/o UnsynchAdj    856.17 kbps   9.81        0.12          0.955
    (updated version)

The overhead of OR/SP has improved significantly, but is still much
larger than MDR even with min-cost LSAs.  However, the already large
number of adjacencies has increased a little.
The biggest component of the OR/SA overhead is DD overhead, which
is 302.15 kbps, more than 4 times the DD overhead of 72.29 for MDR.
Since differential Hellos could be used to reduce the Hello
overhead, it is interesting to compare the overhead excluding
Hello overhead.  For OR/SP this is 856.17 - 135.37 = 720.80
and for MDR with minimal LSAs this is 277.22 - 127.78 = 149.44.

Out of curiosity, I also compared the new statistic,
LSA hopcount / LSA installs.  This was 2.36 for OR/SP and
2.66 for MDR.  This means that flooding path length is better for
OR/SP.  I expected this, since OR/SP has almost 4 times as many
adjacencies as MDR, which helps to reduce flooding path length.

Richard

New results for OR/SP:

OSPFv3 Statistics
           | Packets          Bytes         Kbps
----------------------------------------------------
Hello       |   45000      15228800      135.37
LSAck       |  125841      16526656      146.90
LSR         |    1759        101364        0.90
DBDESC      |   34778      33991804      302.15
LSU         |   98418      30470684      270.85
  LSUfld    |     77410      24420244      217.07
  LSUuni    |     21008       6050440       53.78
    LSUcol  |          69         41524        0.37
    LSUrxmt |       18692       5348748       47.54
    LSUdbex |        1732        528752        4.70
    LSUstale|         515        131416        1.17
            |
Total       |  305796      96319308      856.17

OSPF Network Characteristics
--------------------------------------------------
OSPF 2way_neighbors/node: 62.18
OSPF 2way_neighbor_changes/node/sec: 1.20
avg_sec/OSPF 2way neighbor_life: 112.57
OSPF adjacencies/node: 9.81
OSPF adjacency_changes/node/sec: 0.12
avg_LSAsOutSync: 0.15
Secs per router-LSA origination:  14.06
Router-LSA hopcount/Router-LSA installs:  2.36
Route changes/node/sec:  18.33
Accumulated adjacencies/node:  -5.95

Flooding Statistics
--------------------------------------------------
relaysel/node: 4.65
avg_sec/relaysel_life: 49.16
suppressed_LSAs: 571518
relay_flood_LSAs: 63103
nonrelay_flood_LSAs: 33201

User Traffic Analysis
--------------------------------------------------
UDP sends: 8897 pkts, 604996 bytes
UDP receives: 8493 pkts, 577524 bytes
UDP forwards: 12484 pkts, 848912 bytes

Delivery Ratio:  0.955
---------------------------------------------------