Subject: [manet] CDS robustness research repport

From: Philippe Jacquet <[email-masked]>
Date: Thu, 04 Aug 2005 16:14:01 +0200

Hello,

This is the reference of the research repport I talked about during the 
WG presentation about simple manet flooding.

  RR-5609 - On the robustness and stability of Connected Dominating Sets

Adjih, Cédric 
<http://indexation.inria.fr/search/public?_q=corporate%2Ftree%3ATop%2FAttributes%2FAuthors%2F%22Adjih%2CC%C3%A9dric%22&_vn=RRRT&xslt=liste> 
- Baccelli, Emmanuel 
<http://indexation.inria.fr/search/public?_q=corporate%2Ftree%3ATop%2FAttributes%2FAuthors%2F%22Baccelli%2CEmmanuel%22&_vn=RRRT&xslt=liste> 
- Clausen, Thomas 
<http://indexation.inria.fr/search/public?_q=corporate%2Ftree%3ATop%2FAttributes%2FAuthors%2F%22Clausen%2CThomas%22&_vn=RRRT&xslt=liste> 
- Jacquet, Philippe 
<http://indexation.inria.fr/search/public?_q=corporate%2Ftree%3ATop%2FAttributes%2FAuthors%2F%22Jacquet%2CPhilippe%22&_vn=RRRT&xslt=liste>

available on.

http://www.inria.fr/rrrt/rr-5609.html

It seems from this study that the MPR-CDS described in smurf draft would 
provide a good compromise between robustness and easiness of use (no 
need of last hop identification) for flooding non specific datas.

Regards,
Philippe

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: Richard Ogier <[email-masked]>
Date: Sun, 28 Aug 2005 22:15:24 -0700

Philippe Jacquet wrote:

> Hello,
>
> This is the reference of the research repport I talked about during 
> the WG presentation about simple manet flooding.
>

> It seems from this study that the MPR-CDS described in smurf draft 
> would provide a good compromise between robustness and easiness of use 
> (no need of last hop identification) for flooding non specific datas.
>
> Regards,
> Philippe
>
Philippe,

I had doubts regarding your simulation results in [RR-5609],
Section 4 (Resilience to transmission errors), so I ran
some simulations comparing your MPR-based CDS (off-line pruning)
to the self-selected CDS based on MDRs (MANET Designated Routers)
described in the OSPF-MDR draft:

http://www.ietf.org/internet-drafts/draft-ogier-manet-ospf-extension-04.txt

I used the default value of 3 for MDRConstraint for the
MDR selection algorithm.
I think that when MDRConstraint = infinity, this algorithm is
equivalent to the "rule k" that you used for the self-selected CDS.
Letting MDRConstraint = 3 gives a slightly larger CDS with
a better stretch factor.

Also, your description of the "rule k" method is not quite
correct.  The condition
"the set S(A) is not a dominating set of the neighborhood of A"
should be
"the set S(A) is not a connected dominating set of the neighborhood of A".

I will assume this is just a typo, and that you used the correct
rule in your simulations (unless I am told otherwise).

After presenting my simulation results below, and discussing some
advantages and disadvantages, I describe a way for the MPR-based CDS
to be incorporated into the OSPF-MDR extension, so that OSPF-MDR can
be compared (via GTNetS simulations) using a self-selected CDS versus
the MPR-based CDS.

I used the following model to obtain the simulation results below.
100 nodes were placed randomly in a unit square.
I used a transmission radius of 0.5 and 0.25.
Figure 4 in your report [RR-5609] used 0.25 (equivalent to using
a 4x4 square).

Simulation results for performance with unreliable links.

For radius = .50
                                   Receive Probability
CDS Method     Avg CDS Size   0.5   0.6   0.7   0.8   0.9  1.0
-------------------------------------------------------------
MPR-based CDS     7.23       .767  .862  .926  .964  .987  1.00
MDR-based CDS     8.26       .738  .846  .919  .963  .986  1.00
Difference in prob.          .029  .016  .007  .001  .001  0.00

For radius = 0.50, there is a significant difference of 2.9% when
p = 0.5, but when p is 0.8 or greater the difference is insignificant.

For radius = .25
                                   Receive Probability
CDS Method     Avg CDS Size   0.5   0.6   0.7   0.8   0.9  1.0
-------------------------------------------------------------
MPR-based CDS     28.87      .676  .820  .910  .961  .987  1.00
MDR-based CDS     29.43      .573  .752  .875  .949  .985  1.00
Difference in prob.          .103  .068  .035  .012  .002  0.00

For radius = 0.25, there is a significant different of 10.3% when
p = 0.5, and 6.8% when p = 0.6, but when p is 0.8 or greater
the difference is small.

Since the MDR-based (self-selected) CDS (with MDRConstraint = 3)
is slightly larger than the MPR-based CDS, I conclude that
the MPR-based CDS is indeed significantly more robust than
the MDR-based CDS when the receive probability is 0.7 or less
for radius = .25, and when the receive probability is 0.5 or less
for radius = .50.

The reason seems to be that the MPR-based CDS has a smaller
stretch factor, since the use of MPRs guarantees that, for
each node, each neighbor can be reached from the min ID neighbor
in at most 2 hops via a CDS node.  (It may take 3 hops for the
MDR-based CDS, which corresponds to MDRConstraint = 3.)
For radius = 0.25, the average stretch factor is 1.13 for
the MDR-based CDS and 1.08 for the MPR-based CDS.

But this increased robustness comes at a cost, i.e., there
are tradeoffs.  First of all, with the MDR-based CDS, the
decision of whether a given node X is a CDS node (i.e., an MDR)
depends only on which pairs of neighbors of node X
are neighbors of each other - this is actually less than
2-hop neighbor information, and allows faster response to
topology changes.

With the MPR-based CDS, the decision of whether a given node X
is a CDS node depends on MORE than the 2-hop neighbor information
for node X.  It depends on the 2-hop neighbor information for
all neighbors of node X, which implies it actually depends on
3-hop neighbor information (with respect to node X).
This could result in slower response to topology changes.

There are other disadvantages, of using MPRs, e.g., having
to select and report MPRs to neighbors adds complexity and
overhead.  Therefore, using MPRs to select the CDS would be
justified only if it improves performance overall.
Detailed simulations, such as the GTNetS simulations done
by Boeing, should be performed to compare these two approaches.

To this end, I will now describe how the MPR-based CDS can be
incorporated into the OSPF-MDR extension.
Assume that the "off-line self-pruning strategy" in [RR-5609]
is used, so that each router knows whether or not it is a CDS node,
which is called an MDR.  In addition, we need Backup MDRs, which
can be selected similarly based on Backup MPRs (which must also be
selected and reported to neighbors.)

Now that MDRs and Backup MDRs are selected, the flooding
procedure in the OSPF-MDR draft can be used.
(Note that the flooding procedure in the draft, excluding
retransmissions, is independent of adjacencies.  But LSA
retransmissions depend on which neighbors are adjacent.)

What remains is how to choose which neighbors to become
adjacent with.  The OSPF-MDR draft uses the notion of
"dependent" neighbors to decide this.  But this can
be simplified by assuming that all neighbors are dependent.
(There exists a more complex solution that may result in fewer
adjacencies, but I'm not sure we want to consider this.)
This implies, for the option of uniconnected adjacencies, that each
MDR becomes adjacent with each MDR neighbor, and each non-MDR selects
an MDR neighbor to become adjacent with.
For the option of biconnected adjacencies, each (Backup) MDR becomes
adjacent with each (Backup) MDR neighbor, and each Other node
becomes adjacent with two neighbors that are (Backup) MDRs.

One question is whether this will result in too many adjacencies,
especially when the biconnected adjacency option is used with
the MPR-based CDS.  The performance of this variation of OSPF-MDR
can be compared with the version described in the OSPF-MDR draft,
which is already implemented in GTNetS.

Regards,
Richard