Subject: RE: [Ospf-manet] Re: evaluation plan for OSPF MANET

From: "Henderson, Thomas R" <[email-masked]>
Date: Mon, 5 Dec 2005 11:11:00 -0800

Philippe, comments inline below:

> -----Original Message-----
> From: Philippe Jacquet [mailto:[email-masked]] 
> Sent: Monday, December 05, 2005 6:19 AM
> To: [email-masked]
> Subject: [Ospf-manet] Re: evaluation plan for OSPF MANET
> 
> Dear all,
> 
> I tend to agree with Tom. We should find the most robust and 
> performant solution. And in case of equal performance one 
> should favor the solution that has the largest maturity and 
> broad support from the community. With this respect MPR 
> flooding seems to be the most robust and mature. 

Please clarify whether you mean MPR flooding as designed for OLSR or
Overlapping Relays flooding for OSPF (which I would argue is at roughly
the same maturity level as the MDR proposal, and possibly slightly less
so since there are still some lingering questions about how it works, as
recent discussions have highlighted).

I believe that the distinction between OLSR and OSPF is important here.
The studies that your group has provided (such as INRIA report 5609) are
done in the context of unreliable (OLSR-like) flooding.  In OSPF,
flooding is reliable and performed along adjacencies, and the design of
OSPF drives the network towards database synchronization.  The tradeoff
of interest (applicable to both the MDR approach and the Overlapping
Relays approach) is between speed of convergence and overhead reduction,
since in both cases there are backup relays and retransmissions along
adjacencies that will lead to recovery from transmission errors and
stale neighborhood information.

Indirectly, we have been measuring control plane convergence by looking
at data plane delivery ratios and path lengths.  Some more direct
measure of convergence might be preferable to settle debates like this;
on the other hand, users care most about these data plane metrics, and
it could be argued that an OSPF control plane convergence metric is less
relevant to user needs, although it might expose more directly what is
going on.

> 
> However one should be careful with the concept of wireless 
> adjacencies and how it will be exported outside the wireless 
> portion. Clearly we will need to keep the wireless OSPF in 
> the right track with  respect to regular OSPF.
> 

Can you provide more detail on what you mean here?  Are you talking
about the "U" bit that is proposed in LSAs as part of the Overlapping
Relays advertisements?  Or synchronized neighbors that are reported as
adjacencies in the router-LSAs?  Or something else?

Thanks,
Tom

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

---

From: Philippe Jacquet <[email-masked]>
Date: Tue, 06 Dec 2005 17:18:12 +0100

Dear Tom, dear Richard,

In both proposals the wireless flooding is based on a primary flooding 
mechanism and a backup mechanism to insure reliability. IMO the proposal 
whose primary mechanism is MPR should be considered as more mature since 
MPR has been deeply investigated. The primary flooding performance and 
robustness is certainly a key factor. Bad performance would affect 
delays and overhead because the backup activation has a certain cost.

Regarding adjacencies, I mean that one should avoid advertizing 
adjacencies that are not synchronized, inside wired network portions, 
for example advertizing links such as those contained in "min-cost LSA", 
or those advertised with “U-bit”. I am not making distinctions on 
specific proposals here. An ideal objective might be that a wired node 
could compute the shortest path to a mobile node based only on 
synchronized links. Of course this can be a debatable issue.

Best regards,
Philippe

---

From: Richard Ogier <[email-masked]>
Date: Sun, 11 Dec 2005 10:32:45 -0800

Philippe Jacquet wrote:

> mechanism and a backup mechanism to insure reliability. IMO the 
> proposal whose primary mechanism is MPR should be considered as more 
> mature since MPR has been deeply investigated. The primary flooding 
> performance and robustness is certainly a key factor. Bad performance 
> would affect delays and overhead because the backup activation has a 
> certain cost. 

Dear Philippe,

We can divide the OSPF flooding process into three mechanisms:
primary flooding, backup flooding, and adjacencies (which includes
unicast retransmissions and database exchange).  You are
claiming that whichever method is best for primary flooding is also
best for the overall flooding process.
In this message, I will discuss why this is not true, and why your
simulation results in RR-5609 do not tell the whole story even for
primary flooding.
I agree that MPRs and an MPR-based CDS have some advantages
over a self-selected CDS, but they also have some disadvantages
which your simulation do not seem to show.
Since your simulation models are not described precisely,
it is difficult to figure out why.

As Tom pointed out, source-independent MDRs are better suited
for adjacencies.  This is because adjacencies are source-independent
by nature, unlike MPRs, so it is easy to prune adjacencies based on
MDRs and BMDRs (as OSPF already does, based on DRs and BDRs.)
Also, it is important to make adjacencies as stable as possible
(to reduce the rate of new adjacencies), so it is important
to select relays persistently (not considered in your simulations).
This will likely increase the number of MPRs.

Below (under the title "Dependence of Backup Flooding"), I will point
out why primary flooding cannot be considered independently of backup
flooding, although I am sure that you already realize you cannot
simply assume they are independent.

First, one of the reasons that I chose self-selected MDRs instead
of neighbor-selected MPRs is for robustness.  The relay (MDR or MPR)
is the node performing the important action (flooding), so it is
important that a given node be able to quickly decide whether or not
it should be a relay - therefore it is best to base this decision only
on 2-hop neighbor information WITH RESPECT TO OF THE POTENITAL RELAY.
This is a tradeoff because it can result in a larger number of relays
and/or a larger stretch factor (depending on the parameter
MDRConstraint in the MDR draft), but basing the decision only
on the neighbors' neighbors is nice because it allows faster
response to topology changes.  (At the end of this message,
I will give a specific example that shows this.)

It is possible to achieve a similar CDS size and stretch factor with
the MDR-based CDS as with the MPR-based CDS, by including all
MDR neighhors in Hellos (similar to including MPRs in Hellos)
and setting MDRConstraint = 2, but for robustness and simplicity
I prefer to not to add this information to Hellos.
(Including MDR neighbors in Hellos allows fewer MDRs to be selected,
by telling each router which 2-hop neighbors are MDRs.)

As you know, with MPRs, a node decides to become an MPR because
a neighbor selected it as an MPR, and the neighbor makes this
decision based on Hellos received from the neighbor's neighbors.
So there is already an extra hop involved, compared to MDRs.
Moreover, with MDRs, a node decides whether it is an MDR based
only on which pairs of its neighbors are neighbors of each other,
so this decision is independent of any 2-hop neighbor!
In contrast, a router i might be selected as MPR by a neighbor j,
which in turn bases its decision on a link (k,m) from a neighbor k
to a 2-hop neighbor m, where m could be 3-hops from node i!

I am not sure why your simulations do not reflect this, but
I suspect that your models are not accurate or detailed
enough to reflect the factors that make MDRs more robust.
This should be investigated, perhaps by performing additional
simulations.  Here are a few suggestions for making the
simulation models more realistic:

1. Assume that Hellos are sent periodically (the Hello interval can
be varied) and never early, and that each Hello reports its 2-way
neighbors and selected MPRs.

2. Model the fact that when a link fails, one endpoint usually
detects the failure before the other endpoint.
Although the difference could be as much as RouterDeadInterval,
I would be happy if the difference is simply the time between
the next Hello (after the failure) at node i and the next Hello
at node j, when the link (i,j) fails. INRIA's simulations might
already do this, but I can't be sure.  It might also help
to model asymmetric links, by assigning a slightly different
range for each node, e.g., the range of a given node can be
selected randomly between 225 m and 275 m (instead of 250 m).

3. With MDRs, a link (j,k) between two neighbors will be considered
to be down in both directions if either j or k reports the link down
in a Hello. (So this needs to be modeled in simulations.)

Also, the parameter MDRConstraint can be set to 2 (instead of 3),
which results in a CDS that has a smaller stretch factor at the
cost of being larger.  Recall that I pointed out the one
reason for the improved reliability of the MPR-based CDS: it
has a smaller stretch factor than the SI-CDS you used.
Using MDRConstraint = 2 will give a smaller stretch factor.
(This does not increase overhead significantly in the GTNetS
simulations, because it reduces the amount of overhead from
backup flooding and/or retransmissions.)

Dependence of Backup Flooding

Now, I will explain why the MDRs are better suited than MPRs
for backup flooding.  Thus, I would expect the performance
of MDRs + Backup MDRs to be at least as good as MPRs + Backup MPRs.
In the MDR algorithm, a router selects itself as an MDR if (roughly)
there do not exist higher "priority" neighbors (which are already
MDRs or will become MDRs) that provide paths between all pairs
of neighbors.  (By "priority", I mean (MDR Level, RtrPri, RID).)
Therefore, when a router receives a flooded LSA from some neighbor,
it knows which of its neighbors should flood the LSA to cover all
of the router's neighbors.  (This is not true with MPRs.)
Therefore, with MDRs, a router can act as a backup and flood the
LSA (after a random wait time) if not all neighbors are covered
by neighbors that transmitted the LSA.
MPRs can try to do the same thing, but this will result in
some backup flooding even if all neighbors are covered by MPRs
(since some of these MPRs are not neighbors of the router).
Note that the above mechanism is intentionally independent of ACKs.

The result is that there will likely be more backup floods for MPRs.
Although the OR draft does not use the above method for backup
flooding, a similar dependence is evident in Boeing's simulation
results, in which there are about 3 times as many backup floods as
primary floods for ORs, but far fewer for MDRs.

In summary, it is not sufficient to evaluate only the primary flooding
mechanism.  The solution needs to be evaluated as a whole.

Richard

P.S. Here is a simple example that shows how it can take MPRs 3 times
as long as MDRs to recover from a link failure.

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

Assume Hellos are sent every 2 seconds.
Compute the worst case delay assuming that Hellos are not missed.
Node 2 is an MPR for node 1.
Node 4 detects the failure of the link between 4 and 2 at time 0,
and indicates this failure in its next Hello at time 2 (worst case).
Nodes 2 and 3 learn about the link failure at time 2 (from the Hello,
assuming that 2 can still hear Hellos from 4).
If MDRs are used, node 3 will select itself as an MDR at time 2.
If MPRs are used, node 2 will report the failure of link (2,4)
at time 4 in a Hello, and node 1 will select node 3 as the
new MPR at time 4, and will report this in a Hello at time 6.
So it can 3 times as long with MPRs as with MDRs, before node 3
becomes an active relay.

Philippe, Can you explain why your simulation results do not
reflect this sort of behavior?  E.g., how are your models
different from the above?  For example, maybe you are assuming
there is zero delay in reporting MPRs once they are selected.
And maybe you are assuming both endpoints of a link detect
a failure at the same time.