Subject: Re: [manet] CDS robustness research repport

From: Philippe Jacquet <[email-masked]>
Date: Tue, 06 Sep 2005 14:35:53 +0200

Dear Richard,

The scheme  is based on two-hop advertizement. If two-hop information is 
distorted or delayed, then it impacts on flooding performances. It turns 
out from the simulations and theory that for the same two-hop 
information distortions, the MPR based flooding remains more performant 
than the self-selected CDS.

We are not using persistence in SMURF, but MPR should fit well OSPF 
since it is resilient to perturbation. Emmanuel Baccelli wrote a 
research repport (http://www.inria.fr/rrrt/rr-5619.html ) where he shows 
that MPR flooding of MPR based CDS limited adjencies seems to best fit 
the wireless OSPF constraints. But this belongs more to OSPF WG  
discussion.

Best regards,
Philippe

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

---

From: Richard Ogier <[email-masked]>
Date: Thu, 08 Sep 2005 08:05:03 -0700

Philippe,

I'm not disagreeing with you, but I want to state
my point more precisely.

The decision of whether node X is in an MPR-based CDS
can depend on the existence of a link (u,v)
where v is 3 hops from X (or 2 hops from an MPR
selector of X).

The decision of whether node X is in a self-selected CDS
depends only on the existence of links (u,v) where
both u and v are at most 1 hop from X.

For an MPR-based CDS, the failure of the link (u,v)
mentioned above might first be detected by node v,
which can be 3 hops from X.
For a self-selected CDS, both u and v are at most 1 hop from X,
so node X is quickly informed of any relevant link failure.

I am not sure whether your simulations differentiated between
node u or node v detecting the failure. In any case, more
detailed simulations (such as GTNetS) should be performed,
to compare the two methods when applied to the OSPF-MDR
extension. As I mentioned before, this can be done by
modifying the existing GTNetS code for OSPF-MDR, so that
MDRs are selected based on MPRs.

Regarding the report rr-5619, it suggests forming adjacencies
only between MPRs and their selectors. This has been tried,
but results in many more adjacencies than in OSPF-MDR.
(Also, it does not ensure the adjacency graph is connected
without some other constraints.)

Regards,
Richard

Philippe Jacquet wrote:

> Dear Richard,
>
> The scheme  is based on two-hop advertizement. If two-hop information 
> is distorted or delayed, then it impacts on flooding performances. It 
> turns out from the simulations and theory that for the same two-hop 
> information distortions, the MPR based flooding remains more 
> performant than the self-selected CDS.
>
> research repport (http://www.inria.fr/rrrt/rr-5619.html ) where he 
> shows that MPR flooding of MPR based CDS limited adjencies seems to 
> best fit the wireless OSPF constraints. But this belongs more to OSPF 
> WG  discussion.
>
> Best regards,
> Philippe
>

---

From: Philippe Jacquet <[email-masked]>
Date: Tue, 13 Sep 2005 14:21:31 +0200

Dear Richard,

I see your point but I am not sure that this will significantly improve 
the self-selected CDS inherent unstabilities. Even if you were updating 
your two-hop neighbourhood two time faster than in a MPR based scheme, 
simulations show that you will still suffer much more unstabilities. In 
fact to keep self-selected CDS stable you eventually need to implement a 
very heavy and event-driven reactive two-hop monitoring mechanism that 
is not really needed for the MPR scheme. The later should support a much 
slower two-hop update (for example through basic periodic LSA) without 
significant alteration of the performance, resulting in lighter overhead.

Regards,
Philippe

---

From: Philippe Jacquet <[email-masked]>
Date: Mon, 19 Sep 2005 10:20:58 +0200

Dear Richard,

I am surprised by your estimate about the number of adjencies: my 
simulations show a very important improvement in overhead (in a 2x2 
suare). This makes around 2 or 3 links advertized by nodes.
…………………………………….<>
number of nodes: full adjencies MPR adjacencies
…………………………………….

50 1100 113
60 1566 152
70 2322 192
80 3204 206
90 5068 239
100 5290 301
110 5386 319
120 6698 365
130 8232 404
140 9678 436
150 10316 490
…………………………………………….
We mentionned MPR selector adjacencies since it is near optimal if one 
wants to stick to really shortest path (Shortest Path First;-). It 
considerably reduces the overhead compared to full topology 
advertizement as shown in the research report. In fact it is OLSR;-) <>I 
agree that you can gain some significant overhead by reducing (but not 
by an order of magnitude) the adjacencies, but you must not forget that 
at the same time you increase the stretch factor. The later leads to an 
effective overhead that is proportional to the data traffic. A stretch 
factor of 10 % reduces the useful capacity of 10 %. Or equivalently 
introduces an overhead equivalent to 10% of the data traffic, which may 
be larger than the total control traffic overhead.

I don't know how far MPR links can be adpated to OSPF adjacencies. In 
the research repport we stress that flooding and adjacencies may be two 
separate issues, as we did in OLSR. For example MPR flooding together 
with MPR-CDS adjacencies may be among the best compromises between 
control traffic performance and robustness (excluding overhead due to 
route stretch).

Regards,
Philippe

---

From: Richard Ogier <[email-masked]>
Date: Wed, 21 Sep 2005 09:08:20 -0700

Philippe,

> suare). This makes around 2 or 3 links advertized by nodes.

For 100 nodes, you get about 3 times as many adjacencies as nodes.
Note that in OSPF, an adjacency is bidirectional, so it is really
6 times if you count both directions (but I will count a bidirectional
adjacency as a single adjacency).

OSPF-MDR with *biconnected* adjacencies has about 2 times as many
adjacencies as nodes.  OSPF-MDR with *uniconnected* adjacencies
(a better comparison since you are not trying to achieve a biconnected
adjacency graph for robustness) has even fewer adjacencies, which
approaches 1 times the number of nodes in dense networks.

There is also the issue of adjacency stability, i.e., how long
adjacencies last.  This is important since OSPF does a database
exchange whenever a new adjacency is formed. You need to
use a different MPR selection algorithm to achieve stability,
which would likely result in a larger number of MPRs.

Regarding stretch factor, which you mention below, OSPF-MDR does
not require data packets to be routed along adjacencies, i.e.,
a data packet can be forwarded to a non-adjacent neighbor.
The min-cost LSAs described in the OSPF-MDR draft provide
shortest-path routing in which the shortest paths are not
restricted to adjacencies.

Regards,
Richard

> advertizement as shown in the research report. In fact it is OLSR;-) 
> <>I agree that you can gain some significant overhead by reducing (but 
> not by an order of magnitude) the adjacencies, but you must not forget 
> that at the same time you increase the stretch factor. The later leads 
> to an effective overhead that is proportional to the data traffic. A 
> stretch factor of 10 % reduces the useful capacity of 10 %. Or 
> equivalently introduces an overhead equivalent to 10% of the data 
> traffic, which may be larger than the total control traffic overhead.
>
> the research repport we stress that flooding and adjacencies may be 
> two separate issues, as we did in OLSR. For example MPR flooding 
> together with MPR-CDS adjacencies may be among the best compromises 
> between control traffic performance and robustness (excluding overhead 
> due to route stretch).
>
> Regards,
> Philippe
>
>
> Richard Ogier wrote:
>
>>
>>