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

[Richard Ogier <rich.ogier at earthlink.net>]

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
Ospf-manet at ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-manet