Subject: [Ospf-wireless-design] Advantages of aligning adjacencies with relays

From: Richard Ogier <[email-masked]>
Date: Sun, 06 Nov 2005 21:37:29 -0800

All,

As has been discussed, using Smart Peering results in adjacencies
that are not aligned with relays (MPRs or MDRs).
Of course, in a OSPF broadcast network, adjacencies are aligned
with the (Backup) DR, and perhaps there is a good reason for this.
So I have been thinking about possible advantages of keeping
this property of OSPF so that at least one endpoint of each
adjacency is a relay.  Here are some possible advantages.

1. Alignment helps take advantage of implicit ACKs.
If a flooding relay (MDR) has several adjacent neighbors,
then these neighbors can treat an LSA flooded by the relay
as an implicit ACK.  If Smart Peering is used with MPRs,
then in general an MPR has only a few adjacent neighbors (same
as any router), so only a few neighbors can treat a flooded
LSA as an implicit ACK.

2. Alignment helps take advantage of explicit multicast ACKs.
Every router must ACK every LSA explicitly or implicitly, so this
advantage refers to sending an explicit multicast ACK in response
to a duplicate LSA received as a unicast.  By requiring adjacencies
to be aligned with MDRs, a single multicast ACK sent by an MDR will
inform several (adjacent) neighbors that the LSA has been received,
thus suppressing a larger number of possible retransmissions than
if adjacencies were not aligned with MDRs.

3. Extendability to non-ackable LSAs (i.e., periodic flooding).
By having a fixed set of nodes responsible for flooding LSAs
(independently of the advertising router) and maintaining
synchronization with neighbors, it is easier to implement
options such as non-ackable LSAs (described in Appendix D of
the MDR draft), by having each MDR flood each LSA periodically
until a new instance has been received.  There are probably other
advantages to having a source-independent set of relays.

4. Here is an example that shows it can take longer for an LSA
to reach all routers if adjacencies are not alighed with relays.

1
|
|
2 --- 3
|     |
|     |
4 --- 5

In this example, nodes 2 and 3 are relays (MDRs or MPRs)
and all neighbor pairs are adjacent except for (2,4).
In particular, (4,5) is an adjacent pair even though
neither 4 nor 5 is a relay.
(I am making a general point so am not assuming that Backup
MDRs/MPRs are used.)
Suppose that node 1 floods an LSA and relay 2 forwards it.
Suppose nodes 3 and 4 do not hear 2's flood.
Then node 2 will retransmit the LSA to node 3 after 5 seconds,
but will NOT retransmit the LSA to node 4 (not adjacent).
Suppose node 3 receives the retransmitted LSA and relays it.
If node 5 does not receive it the first time, node 3 will
retransmit it after 5 seconds.  Now, since node 5 is not a relay
it does not immediately flood the LSA, but will retransmit it
to node 4 (adjacent) after 5 seconds.  This example shows that it can
take much longer for the LSA to reach node 4 than if adjacencies
were aligned with relays, so that the pair (2,4) is adjacent.

Richard

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

---

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

I would like to go into more depth regarding the following advantage
of having a set of relays (MDRs) that are responsible for forwarding
all LSAs (independent of the originator) and for maintaining
synchronization with neighbors.

 > Extendability to non-ackable LSAs (i.e., periodic flooding).
 > (independently of the originator) and maintaining
 > until a new instance has been received.

One might argue that MPRs can be used for periodic flooding
of LSAs, as in OLSR.  But let's take a closer look at this
in the context of OSPF. To accomplish periodic flooding using
MPRs, the originator (advertising router) must periodically
flood its router-LSA (e.g., every 5 seconds) whether or not
the LSA changes.  Let's first suppose that the LSA sequence number
is incremented only when the LSA changes.  Then an MPR that
receives a periodically flooded LSA from an MPR selector, which
is not a new LSA (has the same sequence number as the database copy),
must still flood the LSA for this to work.  But this is contrary to
OSPF, in which a received LSA is forwarded only if it is a new
instance, and it is not clear what the forwarding rule should be
if the same MPR receives the same LSA from another MPR selector
1 second later, or 5 seconds later, etc.

Now suppose that the LSA sequence number is incremented (by
the originator) with each periodic flood, whether or not
the LSA has changed.  This is also contrary to OSPF, and will
cause unnecessary flooding of the LSA over non-MANET
interfaces that are in the same OSPF area.

Now consider the periodic flooding method (using non-ackable LSAs)
proposed in the MDR draft.  As in OSPF, the originator increments the
LSA sequence number only when the LSA actually changes.
As in OSPF, a received LSA is forwarded only if it is a new instance.
The only difference regards local retransmissions: each MDR periodically
multicasts each LSA until a new instance of the LSA is received.
(If topology changes are frequent, the new instance will often be
received before the old instance is multicast a second time.)

This method does not work with MPRs because each MPR is responsible
for forwarding only LSAs received from its MPR selectors, and
it is not clear what to do when the set of MPR selectors changes
without receiving a new instance of the LSA.

This is just one example of how the use of source-independent MDRs
makes the design more extensible (and more compatible with OSPF).

I will mention here another advantage of the fact that OSPF-MDR
treats a MANET as a generalized OSPF broadcast network.
This allows OSPF-MDR to treat an OSPF broadcast network as
a special case of a MANET, at least for the purpose of flooding
LSAs between a broadcast interface and a MANET interface.
This is described in Section 8.1.2 of the MDR draft.

Richard