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

From: "Madhavi W. Chandra" <[email-masked]>
Date: Thu, 3 Feb 2005 17:51:55 -0500

Hi All,

I've read Richard's paper on CDS algorithms, and I must say
that it is very well written and insightful! We have some
comments/thoughts that I'd like to bring to light.  I'll bring
these up, so that others can ponder on them also.  However, I
think that we (DT) need to do simulations to really understand
and compare the behavior of the CDS algorithms and Overlapping
Relays.  It wouldn't be fruitful to embark on a theoretical
debate without the simulations.

How can we work as a DT to have Richard's models and Boeing's models
on the same simulation platform...maybe Richard's models can be ported
to the GTnetS simulation engine that Tom released?  This would be very
helpful in running simulations to compare CDS and Overlapping
relays.  Of course, we would need to validate the simulation models
to ensure that they faithfully represent the algorithms before we
can confidently use them as decision tools.

I've included the comments at the end of this email.

Thanks,
Madhavi

Comments on CDS paper:

- It seems that the response time (convergence time) of CDS algorithms
is not faster than Overlapping Relays.  Rather, it seems that
Overlapping Relays are no worse...and in fact, they may be better since
a Hello can be sent immediately after the Overlapping Relay set changes.
Even removing the optimization of sending a Hello early for Overlapping
Relays, both algorithms react only after Hello time. For example,

   - Overlapping Relays: Overlapping Relay set is learned in Hello.
                         Overlapping Relays perform immediately.

   - CDS:   Neighbor changes learned in Hello.
            CDS Computation
            CDS nodes bring up adjacencies
            CDS set performs

So, both rely on Hello time, and it seems that the latency after Hello
time is less for Overlapping Relays since there is no computation and
potentially establishing multiple additional adjacencies.

- A Hello packet can be sent early in both algorithms to reduce the
response time.  In the case of Overlapping relays, the early Hello
will indicate a changed relay set.  In the case of CDS algorithms,
a Hello can also be sent earlier so that neighbor changes and necessary
parameters can be learned earlier.  But, they are both different
performance/overhead hits.  Meaning, in CDS algorithms, it would
require ALL nodes to send a Hello immediately after ANY neighbor
changes...which is much more overhead than sending a Hello early if
the Overlapping relay set changes.

- It seems that tieing the control plane and data plane together will
have an impact on the latency imposed on the data forwarding.  Meaning,
when the CDS set changes, the new DR's need to bring up multiple
adjacencies before being able to reliably forward data traffic.  This
will impact packet delivery ratios. We're also wondering about the
implications on burdening the same set of nodes with control and
data traffic, e.g., power.  It may be desirable to use a larger
set of links (maybe all) for data plane, while keeping the smaller
set of CDS links for the control plane.

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

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

- We need to look at Packet Delivery Ratio and Network Throughput
(measure combined data and control traffic), and also look at the
tradeoff between complexity and convergence time.

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

---

From: Richard Ogier <[email-masked]>
Date: Thu, 03 Feb 2005 20:32:57 -0800

Hi Madhavi,

Thanks for your comments.  Please see my response below.

>debate without the simulations.
Yes, I agree.  Theoretical debates can be misleading.
I think that Tom's group is planning to implement some
of the algorithms from my draft in the GTnetS simulation.
I can also help with this.

>can confidently use them as decision tools.
Right. It is easy to make a given method look bad by not
implementing it in the best way, e.g., using the wrong
parameters.  Also, it is important to compare the methods
in larger networks (e.g., 100 nodes or more), since scalability
is clearly a desirable attribute.

>a Hello can be sent immediately after the Overlapping Relay set changes.
If a Hello is sent immediately after the overlapping relay set changes,
that would make the response time the same for both methods (although
it would require additional overhead for the extra Hello),
since it would avoid the additional delay of having to inform the
neighbor that it is an overlapping relay (which is avoided in a
CDS algorithm in which a node selects itself as a relay).
Or am I missing something?

There are a lot of features in my draft that reduce overhead in
highly mobile, dense networks, such as not requiring all routers
to originate full LSAs whenever one (of possibly 100) neighbors
changes state.  In fact, a new advantage added to my draft is
that nodes do not even have to advertise their full neighbor
set to their neighbors (either in Hellos or LSAs).  This is
called "partial 2-hop neighbor information".  If each node
has n = 100 neighbors, and therefore includes 100 neighbors in
either an LSA or Hello, this creates n^2 = 10,000 router IDs
of overhead. My draft avoids this.

I think it is worthwhile understanding why partial 2-hop
neighbor information is more easily done with a CDS
algorithm than with MPRs (overlapping relays).
However, I will leave this to a future discussion.

>                         Overlapping Relays perform immediately.
Why did you leave out the following?
    2-hop neighbor information learned in LSA originated by neighbor
    Overlapping relays computed based on new information
    Overlapping relays reported in Hello (same Hello as your first step)

The first step actually could take MinLSInterval = 5 seconds, since that
is the time between LSA originations if neighbor changes are frequent.

>            CDS nodes bring up adjacencies

A CDS node (DR or Backup DR) can be used for flooding before a
full adjacency is formed, as in legacy OSPF.
Adjacencies are not an issue anyway, since either my solution
or your solution could operate with or without adjacencies.
In your case, adjacencies could be formed between each router
and its MPRs.

>potentially establishing multiple additional adjacencies.
No computation? The most efficient CDS algorithm in my draft
requires O(n^2) time, the same as the time required to compute MPRs.

>the Overlapping relay set changes.

Again, you are ignoring how 2-hop neighbor information is learned
in your solution (via LSAs). Sending a Hello early in the case
of a CDS algorithm would be for the purpose of learning 2-hop
neighbor information faster. In your solution, this information
is learned via full LSAs, which are much bigger than differential
Hellos. I guess you are assuming LSAs are sent anyway and therefore
come for free. My draft does not assume that. But if we do assume
that full LSAs are originated (which is a lot of overhead in a
highly mobile, dense network), then we cannot ignore the possible
MinLSInterval delay in obtaining 2-hop neighbor information.

Anyway, if differential Hellos are used (as described in
my draft), then they can be sent every 1 or 2 seconds, so there
would not be much need to send an early Hello.

>set of CDS links for the control plane.

Regarding your first point on latency, that is why adjacencies
are also established between Backup DRs and neighbors, to provide
redundant routes that are ready to be used if the topology changes.
Of course, it is also possible to use all links for
data traffic, and my draft allows this.  A larger metric could
be assigned to links that go to DRs (to avoid them).
However, flooding all possible links in LSAs may be too much
overhead, so it is good to allow the other options.

Regarding your point about burdening the same set of nodes
with an unfair share of power consumption, the RtrPri
can be reduced after a node has been a DR/BDR for
some interval of time, so that another node will take
its place, and the burden is shared.

>Relay to stay an Overlapping relay as long as coverage is not

There is an equivalence between MPRs (overlapping relays) and CDS
nodes, the main difference being whether they are neighbor-selected
or self-selected. Otherwise, the set of relays can be exactly the
same, for example, if priority is given to the largest Router ID.
Thus, the hokey-pokey effect should be the same for both methods:
in either case, a "persistent" version can allow an MPR or DR to
remain an MPR or DR for "as long as coverage is not compromised".

Regarding the formation of adjacencies, as I said above, either
solution can operate with or without adjacencies, so it is just
a matter of deciding whether or not it helps performance to form
full adjacencies. Simulations can help to answer this question.
Even without optimizing database exchange (as proposed in
Section 9 of my draft), the simulation results presented in
draft-spagnolo-manet-ospf-design-00.txt
showed that the overhead due to adjacency forming is minimal.

Most importantly, I agree with your following point. :-)

>It wouldn't be fruitful to embark on a theoretical

Regards,
Richard

---

From: Richard Ogier <[email-masked]>
Date: Fri, 04 Feb 2005 09:30:39 -0800

Madhavi,

I would like to add a few more comments for clarification.

Your comparison of neighbor selected MPRs (overlapping relays) vs.
self-selected CDS nodes (DRs/BDRs) is not really a comparison
of MPRs vs. CDS nodes. The differences you noted were mostly
due to the fact that your MPR solution uses LSAs to learn
2-hop neighbor information, and my CDS solution uses Hellos
to learn 2-hop neighbor information. My solution could easily
use LSAs to learn 2-hop neighbor information, in which case
the advantages of MPRs that you noted disappear.

I decided to use Hellos instead of LSAs to learn 2-hop neighbor
information for the following reasons:

- To learn full 2-hop neighbor information with LSAs requires
  that full LSAs must be originated and flooded, which can
  result in a huge amount of overhead in a highly mobile,
  dense network. It would be nice to at least have the option
  of not requiring full topology LSAs.

- Although it is possible to use LSAs that advertise only partial
  topology (Dependent Neighbors) when the CDS solution is used,
  and to use these partial LSAs for learning 2-hop neighbor
  information, this would require sending originated LSAs
  reliably to all neighbors (which is avoided in my draft).
  Because LSAs are not differential, and because of the
  MinLSInterval delay between LSAs (which can be significant
  when neighbor changes are frequent), using differential
  Hellos seems to require less overhead and to react more
  quickly to topology changes.

You also noted some differences due to the fact that
my CDS solution forms full adjacencies between DRs
and their neighbors. However, full adjacencies do not
need to be formed (simulations will help decide this),
and they are no more necessary for the CDS solution
than for the MPR solution.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Sat, 05 Feb 2005 11:19:11 -0800

All,

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

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

>Relay to stay an Overlapping relay as long as coverage is not

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

---

From: Richard Ogier <[email-masked]>
Date: Tue, 15 Feb 2005 16:53:08 -0800

All,

> exchange is optimized, it is still wasted and unnecessary effort.

To test this hypothesis, I ran some mobile simulations.
I used the same model as the simulation results in my
draft, except that a random direction was generated for
each node at the start of the simulation, and each node was
moved 1/10 of the transmission radius each second (fast mobility),
reflecting off the boundaries of the unit square.
Each simulation was run for 500 seconds.

I used the rule that I recently posted for selecting adjacent
neighbors as part of the Essential CDS algorithm (so not all
neighbors of a DR/BDR are adjacent). For computing BDRs, I
used the Suurballe-Tarjan algorithm for computing disjoint paths,
which runs in O(d^2) time, where d is the degree.
The resulting set of DR/BDR nodes and the associated adjacencies forms
a biconnected subraph, which provides robustness to topology changes.
(BTW, if you want to simulate this, I can give you my code.)

I did not use the persistent version of the CDS algorithm,
since it did not perform any better than the non-persistent
version. Some persistence is already achieved by giving priority
to nodes with larger ID, and by not using degree (which can change
frequently). (I plan to remove the persistent version from my draft.)
However, I tried a variation in which an adjacency is torn down only
if the link breaks or neither endpoint of the link is a DR or BDR
(Table 2 below).

I measured the following statistics: average number of DRs,
average number of BDRs, average number of adjacencies induced
by DRs, average total number of adjacencies (from DRs and BDRs),
average total number of edges (equal to the number of adjacencies
in Cisco's solution), and the rates at which new adjacencies
and new edges were formed.

The results are given in the two tables below.  Of course, the
number of edges is always much larger than the number of
adjacencies, especially for dense networks,  For 300 nodes
and a radius of 0.5 (in a unit square), the number of edges
is about 36 times the number of adjacencies. However, since several
adjacencies can form when a new DR or BDR is selected (as Madhavi
pointed out), the rate of new edges is only about 9 times
the rate of new adjacencies in this case. :-)

In general, the number of edges increases quadratically with
the number of nodes, whereas the number of adjacencies increases
approximately linearly with the number of nodes.
This implies that the CDS approach is more scalable than
the approach of forming adjacencies with all neighbors.
(Of course, that is why legacy OSPF uses the DR/BDR approach.)
Am I missing something?  Does Cisco really take the approach
of forming adjacencies with all neighbors?

Table 2 gives the results for a variation in which an adjacency
is torn down only if the link breaks or neither endpoint of the
link is a DR or BDR. (Normally an adjacency is torn down when
neither endpoint is a dependent neighbor of the other endpoint.)
This variation reduces the rate of new adjacencies by roughly 30
percent, but increases the average number of adjacencies by
roughly 60 percent. It is not clear whether this is beneficial,
since adjacencies require some overhead to maintain (i.e.
LSA retransmissions and acks), so detailed simulations are
needed.

                                        Number of Nodes
     -------------------------------------------------------------
     Radius  Measure              50      100      200       300
     -------------------------------------------------------------
      0.3    Avg # DRs           17.65    20.74    23.45     22.85
             Avg # BDRs          13.39    15.47    15.54     16.45
             Avg # DR adj.       79.18   176.11   375.35    567.05
             Avg # total adj.   111.50   242.44   491.59    736.84
             Avg # edges        260.63  1055.91  4287.15   9623.68
             Ratio edges/adj      2.34     4.36     8.72     13.06
             New adj rate        24.30    59.47   128.44    189.79
             New edge rate       18.21    72.28   293.55    659.18
             Ratio edge/adj rate  0.75     1.22     2.29      3.47
     -------------------------------------------------------------
      0.5    Avg # DRs            7.12     7.77     9.14      8.43
             Avg # BDRs           5.68     6.16     6.13      6.22
             Avg # DR adj.       75.12   154.23   326.90    474.94
             Avg # total adj.   104.30   207.36   421.90    605.56
             Avg # edges        592.67  2384.30  9617.78  21646.11
             Ratio #edges/#adj    5.68    11.50    22.80     35.75
             New adj rate        23.07    47.56    96.74    136.48
             New edge rate       34.17   138.25   553.70   1245.35
             Ratio edge/adj rate  1.48     2.91     5.72      9.12
     -------------------------------------------------------------

          Table 1.  Average numbers of DRs, BDRs, and adjacencies
                    for Essential CDS algorithm using S-T algorithm
                    for BDR selection, compared to average number
                    of edges in the graph.

                                        Number of Nodes
     -------------------------------------------------------------
     Radius  Measure              50      100      200       300
     -------------------------------------------------------------
      0.3    Avg # DRs           17.65    20.74    23.45     22.85
             Avg # BDRs          13.39    15.47    15.54     16.45
             Avg # DR adj.      103.01   239.59   538.90    818.78
             Avg # total adj.   165.34   393.17   868.42   1314.54
             Avg # edges        260.63  1055.91  4287.15   9623.68
             Ratio edges/adj      1.58     2.69     4.94      7.32
             New adj rate        16.50    42.64    93.39    139.07
             New edge rate       18.21    72.28   293.55    659.18
             Ratio edge/adj rate  1.10     1.69     3.14      4.74
     -------------------------------------------------------------
      0.5    Avg # DRs            7.12     7.77     9.14      8.43
             Avg # BDRs           5.68     6.16     6.13      6.22
             Avg # DR adj.       99.53   209.59   462.65    662.36
             Avg # total adj.   171.66   356.47   759.23   1099.20
             Avg # edges        592.67  2384.30  9617.78  21646.11
             Ratio #edges/#adj    3.45     6.69    12.67     19.69
             New adj rate        15.75    33.84    70.89     98.06
             New edge rate       34.17   138.25   553.70   1245.35
             Ratio edge/adj rate  2.17     4.09     7.81     12.70
     -------------------------------------------------------------

          Table 2.  Same as Table 1, except that an adjacency is torn
                    down only if the link breaks or neither endpoint
                    of the link is DR or BDR.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Fri, 18 Feb 2005 13:17:47 -0800

All,

In my last message I presented some results for the rate at which
new adjacencies are formed, and mentioned that the persistent
version of the algorithm does not help. It turns out that the
persistent version does help if the following change is made:
Each non-DR/BDR node selects two DR/BDR neighbors (called "parents")
to be adjacent with: one must be a DR and the other can be a DR or BDR.
A node keeps the same parents as long as they are still neighbors
and are still DR/BDR (persistence).

This change reduced the rate of new adjacencies dramatically.
For example, I previously said that for a 300 node network,
the rate of new adjacencies was about 1/9 the rate of new edges.
This has decreased to about 1/24. I am excited about these results!
I will include the results for all cases in my updated draft,
but here are the results for this case:

N = 300
conn_radius = 0.500000
Avg degree = 144.307427
Avg num DRs = 8.118000
Avg num BDRs = 5.566000
Avg num adj = 595.686
Avg num edges = 21646.114
Ratio num edges / num adj = 36.338
Avg rate of new adj = 51.324 (per second)
Avg rate of new edges = 1245.35 (per second)
Ratio new edge rate / new adj = 24.26

Since the ratio of the rate of new edges to the rate of new adjacencies
is about 24, and the ratio of the number of edges to the number
of adjacencies is about 36, this implies that the average life
of an adjacency is about 0.67 times the life of an edge.
But this shorter life time is greatly outweighed by the
fact that only about 3% of edges are adjacencies!

Richard