Re: [Ospf-wireless-design] Simulation needed: CDS vs. Overlapping Relays

[Richard Ogier <[e-mail]>]

All,

I have a better understanding the following point made by Madhavi
and have some additional comments.

>- While the persistent mode will mitigate the effect of toggling
>CDS sets, it seems that it will still lead to the 'hokey-pokey'
>effect (term coined by Acee).  That is, a node can keep
>putting itself in the set and removing itself from the set (based
>on connectivity, overlap, and redundancy).  Each time, the adjacencies
>need to be either torn down...or brought back up, which is a nontrivial
>effort and overhead in terms of database exchange.  Even if database
>exchange is optimized, it is still wasted and unnecessary effort.
>


I agree that if the Essential/MPN CDS algorithm is used,
so that all neighbors of a DR/BDR are adjacent
(as in legacy OSPF), then it would be inefficient
to simply do a database exchange with all neighbors as
in legacy OSPF. That is why I suggested the enhancement
(Section 9) in which a new DR *multicasts* a DD packet(s) to all
neighbors, and each neighbor acknowledges the DD packet(s) with
a DD packet that describes only LSAs that the DR does not have
(if any).  (If necessary, the DR can retransmit the DD packet,
either as a unicast or as a multicast, as explained in my draft.)

Using the persistent version of the CDS algorithm will make
this happen less often, so simulations are needed to see
whether this enhancement is really needed in this case.
However, it seems foolish to do it the inefficient way!

In Cisco's solution, it seems that all neighbors are adjacent,
so database exchange is performed whenever any router gets
a new neighbor.  This can also be done with the CDS approach,
if it results in less overhead.  Again, simulations are needed
to see if this helps. (Note that partial topology LSAs can
still be used, since a router can still include only (Backup)
Dependent Neighbors in its LSA.)

>- The hokey-pokey effect will not arise in Overlapping Relays since the
>selector node will not change the relay set, and allow an Overlapping
>Relay to stay an Overlapping relay as long as coverage is not
>compromised.
>

I now see the difference you are talking about. You are saying
that each MPR can be persisent, which is different from saying
that each CDS node (DR) can be persistent. However, since
Dependent Neighbors are equivalent to MPR selectors (if the
ANP CDS algorithm is used) it is possible to make Dependent
Neighbors persistent in the CDS approach, which would then
be equivalent to making MPRs persistent.
I.e., a Dependent Neighbor remains a Dependent Neighbor as long
as possible. (It is easy to modify my draft to do this.)
(For background, a node is in the CDS if and only if it has at
least one Dependent Neighbor.)

Since Dependent Neighbors must be adjacent, this might help
reduce the rate at which adjacencies must be established.
However, it will also cause a problem, whether applied to Dependent
Neighbors or to MPRs, which was mentioned before on this list.
It will make MPRs less correlated among different nodes
(since we cannot select MPRs based on router ID in order to
maximize agreement and thus reduce the total number of nodes
that are MPR of some neighbor), which may result in each LSA
being relayed by a larger number of MPRs.
That is why I decided to make CDS nodes persistent, instead
of Dependent Neighbors.  However, the other way can also be
compared in simulations.

I was thinking that, if MPRs are used, then it is only necessary
to form adjacencies between each node and its MPRs. This works
for Dependent Neighbors in the CDS approach, but unfortunately
it does not work for MPRs because the MPRs selected by different
nodes are not coordinated in the way that Dependent Neighbors are
in the CDS approach, as shown in the following example.

       1
     /   \
    3-----4
     \   /
       2


Suppose MPRs are used, with the following selection:
Node 1 selects node 3 as MPR
Node 2 selects node 4 as MPR
Then if we form adjacencies between each node and its MPRs,
then the adjacent pairs will be [1,3] and [2,4].
These two adjacencies do not connect nodes 1 and 2,
which are therefore not guaranteed to be synchronized.

Now suppose a CDS is used, and that all nodes have the same RtrPri.
Since node 4 has a larger ID than its neighbors, it will select
itself as a DR, and all neighbors will be Dependent Neighbors.
Therefore, the adjacent pairs will be [4,1], [4,2], and [4,3],
which connects all nodes in the network.

Another advantage of the CDS approach that I recently pointed
out is that only *partial* 2-hop neighbor information is
needed with the CDS approach. This can be illustrated with the
same example above. Node 4 is the only node with Dependent
Neighbors, so in the partial 2-hop neighbor approach, it is the
only node that needs to advertise this set of neighbors to its
neighbors.  Once node 3 has this 2-hop neighbor information
from node 4, it knows that node 4 will select itself as a CDS node
to act as a relay between nodes 1 and 2, and node 3 does not have
to advertise any of its neighbors to its neighbors.

HOWEVER, in my draft, it is important that each node advertise
not only its Dependent Neighbors in Hellos, but also its
Backup Dependent Neighbors, for robustness. So any simulation
that evaluates the use of partial 2-hop neighbor information
must include Backup Dependent Neighbors.

A simple way to look at this, if the Essential/MPN CDS algorithm
is used, so that all neighbors of each DR are Dependent and all
neighbors of each BDR are Backup Dependent, is that only
DR and BDR routers need to send full Hellos periodically,
and the other routers only need to send differential Hellos to
discover neighbors.

Regards,
Richard


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