Subject: Re: [Ospf-wireless-design] Synchronization requirement for including a neighbor in LSA

From: Richard Ogier <[email-masked]>
Date: Thu, 14 Jul 2005 12:58:40 -0700

All,

Here is a preview of the section on originating LSAs in the upcoming draft
draft-ogier-manet-ospf-extension-04 to be submitted this week.
Since there was some doubt about whether non-adjacent neighbors should
be advertised in LSAs, the section provides some motiviation for this.

Richard

---------------------
9. Originating LSAs

Unlike the DR of an OSPF broadcast network, an MDR does not
originate a network-LSA, since a network-LSA cannot
be used to describe the general topology of a MANET.
Instead, each router advertises a subset of its MANET neighbors
as point-to-point links in its router-LSA.
The choice of which neighbors to advertise is flexible, and is
determined by the configurable parameter LSAFullness.

As a minimum requirement, each router must advertise all of
its fully adjacent neighbors in its router-LSA. This minimum
choice corresponds to LSAFullness = 0, and
results in the minimum amount of LSA flooding overhead, but
does not provide routing along shortest paths.

Therefore, to allow routers to calculate shortest paths,
without requiring every pair of neighboring routers along the
shortest paths to be adjacent (which would be inefficient
due to requiring a large number of adjacencies), a router-LSA
may also advertise non-adjacent neighbors that satisfy a
synchronization condition described below.

To motivate this, we note that OSPF already allows a non-adjacent
neighbor to be a next hop, if both the router and the neighbor belong
to the same broadcast network (and are both adjacent to the DR).
A network-LSA for a broadcast network (which includes all routers
attached to the network) implies that any router attached to the network
can forward packets directly to any other router attached to the
network (which is why the distance from the network to all attached
routers is zero in the graph representing the link-state database).

Since a network-LSA cannot be used to describe the general topology of
a MANET, the only way to advertise non-adjacent neighbors that
can used as next hops, is to include them in the router-LSA.
However, to ensure that such neighbors are sufficiently synchronized,
only "routable" neighbors are allowed to be included in LSAs,
and to be used as next hops in the SPF calculation.

9.1. Routable Neighbors

A neighbor is defined to be routable if either it is in state FULL,
or it is bidirectional (in state 2-Way or greater) and the SPF
calculation has produced a route to the neighbor.
This condition implies that there exists (or recently existed)
a path of full adjacencies from the router to the routable neighbor.
The idea is that, since a routable neighbor can be reached through
an acceptable path, it makes sense to take a "shortcut" and
forward packets directly to the routable neighbor.

This requirement does not guarantee perfect synchronization, but
simulations have shown that it performs well in mobile networks.
This requirement avoids, for example, forwarding packets to a new
neighbor that is poorly synchronized because it was not reachable
before it became a neighbor.

The single-bit neighbor variable Routable indicates whether the
neighbor is routable. This variable is initially 0, and is updated
as follows when the state of the neighbor changes or the SPF calculation
finds a route to the neighbor:

(1) If the state of the neighbor changes from less than 2-Way to 2-Way
or greater, and there exists a route to the neighbor, Routable is
set to 1 for the neighbor.

(2) If the state of the neighbor changes to FULL, Routable is
set to 1 for the neighbor.

(3) If a route to the neighbor has been calculated, and the state of
the neighbor is 2-Way or greater, Routable is set to 1 for the neighbor.

(4) If the state of the neighbor changes from 2-Way or greater, to
less than 2-Way, Routable is set to 0 for the neighbor.

9.2. Partial and Full Topology LSAs

The choice of which MANET neighbors to include in the router-LSA
is flexible, subject only to the following requirements:

(1) A router MUST include all FULL neighbors in its router-LSA.
(2) A router MUST NOT include any non-routable neighbors in its LSA.

Thus, a minimum LSA includes only FULL neighbors, corresponding to
LSAFullness = 0. At the other extreme, a router may include
all routable neighbors in its router-LSA, corresponding
to LSAFullness = 3 (full-topology LSAs).
Between these two extremes, a router may include any subset of routable
neighbors in its router-LSA, as long as all FULL neighbors are included.
It is not necessary for different routers to make the same choice;
the different choices are interoperable because each router-LSA
must include all FULL neighbors, which allows the SPF
calculation to find routes to all reachable routers.

A new router-LSA is originated whenever an event occurs that causes
the contents of the LSA to change (which depends on the choice
of the LSA contents). However, as stated in RFC 2328, Section 12.4,
two instances of the same LSA may not be originated within the time
period MinLSInterval. This may require that the generation of the next
instance be delayed by up to MinLSInterval.
When a new LSA is originated, it is installed in the database
as described in Section 13.2 of RFC 2328, which may cause
the routing table to be recalculated. The new LSA is also flooded
as described in Section 8 of this document.

This document specifies two additional choices for partial-topology LSAs,
which provide shorter paths than minimal LSAs, but generate
substantially less overhead than full-topology LSAs.

Min-Hop LSAs (LSAFullness = 1)

Each router decides which MANET neighbors to include in its router-LSA
by looking at the router-LSAs originated by its neighbors, and including
in its router-LSA the minimum set of neighbors necessary to provide a 2-hop
path (in each direction) between each pair of neighbors that are not
neighbors of each other. If another neighbor is already providing such
a path between a given pair of neighbors, then the router includes the
pair of neighbors in its LSA only if it can provide a lower cost path.
The details of this algorithm are given in Appendix C.

MDR Full LSAs (LSAFullness = 2)

Each (Backup) MDR originates a full LSA (which includes all routable
neighbors), while each MDR Other originates a minimum LSA (which
includes only FULL neighbors). If a router has multiple MANET
interfaces, its LSA includes all routable neighbors on the interfaces
for which it is a (Backup) MDR, and includes only FULL neighbors on its
other interfaces. When a router changes its MDR Level
from MDR Other to (Backup) MDR on a given interface, it originates
a new LSA.
This choice provides routing along nearly min-hop paths, and typically
results in less flooding overhead than min-hop LSAs.

A variation of MDR Full LSAs is possible, in which some MDR Other
routers also select themselves to originate full LSAs, based
on 2-hop neighbor information.
A heuristic can be used for such a selection that results in routes
that are arbitrarily close to minimum cost on average. Such
a heuristic may be described in a future version of this draft.

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