Subject: Re: [Ospf-manet] Update to OSPF-MDR draft

From: Richard Ogier <[email-masked]>
Date: Tue, 03 Jan 2006 15:56:14 -0800

Philippe,

Philippe Jacquet wrote:

 > Dear Richard,
 >
 > I understand that you delay processing time of min-cost LSA on
 > subsequent LSA reception. O(n^2) processing time is on per LSA
 > reception (looking at advertized neighbour pairs). This will end in
 > O(n^3) since n neighbor LSAs would need to be received (min cost path
 > are not through CDS). But the calculation will converge at a much
 > slower pace and will create more overhead over the network (heavier
 > LSA's sent all over the network). Slow convergence is not good if link
 > costs frequently change due to mobility. With MPR you can compute and
 > advertize the min-cost information with no delay because of the
 > central position of the MPR selector and also reduce the number of
 > advertized links.

On average, the processing time is O(n^2), not O(n^3).
There are 3 nested loops:

1. For each neighbor LSA:  O(n)
2. For each neighbor j in the LSA:  O(1) on average
3. For each other neighbor k:  O(n)

So it is O(n^2) on average. The second loop is O(1) essentially
because the number of MPRs per node is O(1) on average.
If you mean that the above calculation must be done whenever
a new LSA is received, that is not true since a new LSA cannot
be originated more than once per MinLSInterval.

Also, I want to remind people that there are several other advantages
of min-cost LSAs. (See my previous emails.)  One advantage is that, if
metrics are used, then the number of MPRs can increase. (I gave an example
in which 10 MPRs were required instead of one MPR.)  Another advantage is
that min-cost LSAs are decoupled from the flooding mechanism.

 > I think that you more or less agree that MPR primary flooding is more
 > robust than MDR flooding (but maybe I misinterpreted your points). But
 > you make the point that what matters is the performance of the whole
 > system: primary flooding plus backup flooding.

The statement "MPR primary flooding is more robust than MDR flooding"
is vague, so I will try to be more precise.
I want to focus on the MPR-based CDS, since I believe that a
source-independent CDS approach is preferable when dealing with
source-independent adjacencies.

Also, in the MDR draft, the set of MDRs (i.e., the CDS) depends
on the parameter MDRConstraint (MDRC).
For example MDRC = 3 means that each neighbor of the calculating
node can be reached from the neighbor Rmax in 3 hops using MDRs
as intermediate hops.  (Rmax is the neighbor with maximum value
of (MDR Level, RtrPri, RID).)

The SI-CDS algorithm that you used is equivalent to assuming that
MDRC = infinity.  This results in a stretch factor that is
larger than for the MPR-based CDS.  There other factors which can
affect performance, such as whether you select MPRs to be persistent.
But in general here is what I believe:

First of all, I think that the reliability differences that you
obtained are mainly due to the different stretch factors.
This is because on average it takes more hops to reach each destination
if the stretch factor is larger, and the reliability is the product
of the reliabilies for all hops.  I noticed that you used sparse
graphs in your simulations, which magnifies the difference in reliability.

For MDRC = infinity, the MDR-based CDS has a larger stretch factor
than the MPR-based CDS, and has roughly the same number of nodes
(assuming MPRs are selected persistently).

For MDRC = 2, the MDR-based CDS has about the same stretch factor
as the MPR-based CDS, but has more nodes.  The reason it has more
nodes is because MPRs are selected by neighbors (i.e., they are
not self-selected), which allows them to see all the possible
neighbors (MPRs) that can be used to reach each 2-hop neighbor.
(For example, a potential MDR i might not know that there is already
an MDR 2 hops away that can be used to provide a path between two
neighbors of node i, although the MDR algorithm can be modified to
take such information into account.)
The MPR selector has a view of its complete 2-hop neighborhood,
as you mention, which puts it in a better position to avoid
redundant MPRs.

However, the larger number of MDRs has benefits in terms of
robustness and reliability.
I suspect that for MDRC = 2, the reliability of the MDR-based
CDS will be at least as good as the MPR-based CDS.
Also, as I explained, MDRs allow a simple backup mechanism that
ensures that each neighbor is covered by some node that sent the LSA.

MDRs select themselves completely independently of 2-hop neighbors
(or any links to/from 2-hop neighbors), which makes them robust
to any error or delays in such information.
It also means that recovery should be faster, since they
depend only on 1-hop neighbors and the links between them.
(I gave an example that showed how MPR selection can result
in a larger delay before the new MPR knows it is an MPR.)

The MPR-based CDS also has a disadvantage when you want to select
a set of adjacencies that spans the network.
The resulting CDS is less stable than a CDS based on self-selected
MDRs, regardless of what tricks you use to make MPRs stable.
This is due to the requirement that MPRs must be selected to
cover all 2-hop neighbors, i.e., that MPRs must provide min-hop
paths.  When MDRC > 2, MDRs provide a more stable CDS than
MPRs, because they need not be selected to provide min-hop
paths (between Rmax and each neighbor k). I have run simulations
that show this.  Therefore, adjacencies based on an MPR-based CDS
will be less stable than adjacencies based on self-selected MDRs.

Now, consider what Cisco is doing.  From what Acee has said, they
plan to confine MPRs to be adjacent neighbors, where adjacencies
have been selected to span the network (but not to provide
min-hop paths). The resulting MPRs are thus aligned with adjacencies
(which is good), but they do NOT provide min-hop paths, nor do
they cover all 2-hop neighbors. (They only cover all 2-hop neighbors
in the adjacency subgraph.)  Therefore, the resulting MPRs will
have a larger stretch factor than your MPRs, and thus they
will not achieve the same reliability as in your simulations.

 > To my opinion I think natural that if the primary flooding works
 > better, then the whole system should work better because the LSA
 > delivery delays would be shorter and the backup flooding would fire
 > less frequently.

As I discussed above, it may not be this simple, due to the dependencies
between the different parts of the protocol.

 >
 > But you say that MDR should be better suited for back-up than MPR.
 > This is a strong statement but I don't see well how it is founded. For
 > example you say that  the members of the MDR-CDS that are neighbors to
 > a given router should cover the router neighborhood, facilitating
 > backup operations. But this does not suffice, since you don't know if
 > your neighbor has actually received the LSA, if the links are
 > unreliable.

Knowing whether a neighbor received the LSA requires ACKs (explicit
or implicit).  Both mechanisms can use ACKs.  My point is that
MDRs allow another mechanism to improve reliability that is
independent of ACKs.  This helps to minimize retransmissions,
which is important since retransmissions are unicast in OSPF.

 > Furthermore I don't think this is true: as with MPR a
 > node's neighborhood will be covered by non neighbor CDS members. A CDS
 > that obeys to the rule (CDS intersect N(a))  is a CDS of N(a) for all
 > nodes a in the network will be very likely a very redundant CDS. On
 > the other hand the MPRs have some redundancy that is naturally
 > activated when some links fail but is not when flooding succeeds in
 > shortest path, as illustrated by simulation.

I don't think your simulations showed the *reason* for the better
reliability of MPRs.  As I stated above, it may simply be because of
the better stretch factor (fewer hops to reach destinations).
This advantage is lost if MPRs are confined to partial-topology
adjacencies.  Also, the "naturally activated" redundancy of MPRs
might help, but this may only help to compensate for the disadvantage I
mentioned: that an MPR does not forward an LSA unless the first
reception of the LSA is from an MPR selector (which may fail), even if
the LSA is received from another neighbor.

In summary, there are advantages and drawbacks of both approaches.
Therefore we need to compare the approaches by evaluating the
complete solutions, not by analyzing parts of the solution
in isolation.  If you want to determine which of two horses
runs faster, it is better to measure how fast they run, rather
than analyze their body parts.

Richard

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

---

From: Philippe Jacquet <[email-masked]>
Date: Mon, 09 Jan 2006 10:40:31 +0100

Dear Richard,

I wish you a happy new year.

I don’t think your analogy with horse is most appropriate. In passing, I 
wonder how like would be a horse designed by a standardization 
committee;-). I am still confused by your points. Since you are working 
in collaboration with Boeing, I would rather use an analogy with 
airplane design;-). You simply want to replace the engines of an 
airplane which flies and flies well (OSPF with MPR) with new engines 
(MDR) which are less reliable and less performant, depending on how you 
play with your MDRConstraint parameter. You claim that the difference 
won’t be visible when the airplane will fly in average conditions and 
the effect will be buried in the mass of other effects. I don’t think it 
is a safe way for design.

<>Coming back to your min-cost LSA argument, it is known for long that 
listing the pair of nodes for which a given node is within the shortest 
path is O(n^3). Exactly O(nxm) where m is the number of edges. Computing 
the shortest path from a given node to other nodes is O(m). Therefore 
MPR is less costly in computation than min-cost links. In your example 
you assume that the network is stable and that the LSA are already very 
small. But at the beginning all the LSAs will be full and computations 
will still be O(n^3) and will converge slowly. This is not appropriate 
if the network frequently changes. Furthermore it seems that if you have 
LSA that are still 50% of full LSAs which is not that small, then the 
cost should still be O(n^3). <>

I don’t understand why you don’t suggest the computation, still in 
O(n^3) but faster because off-line, that you proposed in TBRPF. Anyway 
the cost with MPR will be much smaller and lead to smaller LSA’s. In 
your example you show that using metric in MPR computation will lead to 
more MPRs than with min-hop metric, that we all know, but the number of 
min-cost MPRs will still be smaller than the min-cost links computed 
your way (since the MPR selector has the central position).

Best wishes,
Philippe

---

From: Richard Ogier <[email-masked]>
Date: Mon, 09 Jan 2006 15:08:16 -0800

Philippe,

Best wishes for a happy new year.
Please see my comments below.

Philippe Jacquet wrote:

> I don’t think your analogy with horse is most appropriate. In passing, 
> I wonder how like would be a horse designed by a standardization 
> committee;-). I am still confused by your points. Since you are 
> working in collaboration with Boeing, I would rather use an analogy 
> with airplane design;-). You simply want to replace the engines of an 
> (MDR) which are less reliable and less performant, depending on how 
> you play with your MDRConstraint parameter. You claim that the 
> difference won’t be visible when the airplane will fly in average 
> conditions and the effect will be buried in the mass of other effects. 
> I don’t think it is a safe way for design.

Even with an airplane, there are dependencies between the engines and 
the other
parts such as the wings. Anyway, your argument does not consider that 
simulations
(in GTNetS) will be used to evaluate the whole solutions before they are 
deployed,
so one does not have to guess that MPRs work better than MDRs in an OSPF 
extension,
which could be a dangerous guess with all of the dependencies that are 
difficult
to analyze.

> listing the pair of nodes for which a given node is within the 
> shortest path is O(n^3). Exactly O(nxm) where m is the number of 
> edges. Computing the shortest path from a given node to other nodes is 
> O(m). Therefore MPR is less costly in computation than min-cost links. 
> In your example you assume that the network is stable and that the LSA 
> are already very small. But at the beginning all the LSAs will be full 
> and computations will still be O(n^3) and will converge slowly. This 
> is not appropriate if the network frequently changes. Furthermore it 
> seems that if you have LSA that are still 50% of full LSAs which is 
> not that small, then the cost should still be O(n^3). <> 

First of all, I want to point out that the value of the discussion on 
LSAs is
questionable, since our focus should be on the flooding protocol, not 
the LSAs.
But it is still of interest to me.

I don't agree that in the beginning all LSAs will be full. This might be 
true if
all nodes start at exactly the same time, but even in this unlikely event,
the LSAs will quickly be pruned, since a router will immediately remove 
neighbors
from its LSA if a higher priority neighbor - i.e., a neighbor with a 
larger value
of (MDR Level, RtrPri, RID) - provides routes to those neighbors in its LSA.
Therefore, I don't think convergence will be slow as you claim (even if this
unlikely event occurs). But here is a more likely scenario in a dense 
network.
When a router starts up, it will find that its neighbor with the largest
value of (MDR Level, RtrPri, RID) will have an LSA that includes most of
its neighbors, and all neighbor pairs will be connected via a few neighbor
LSAs.  I believe that, on average, the total number of links in all neighbor
LSAs is O(n), or O(1) links per LSA.  This agrees with Boeing's simulation
results, which show that the use of min-cost LSAs results in an LSA overhead
that increases approximately linearly in the number of nodes.
Therefore, your example of 50% of full LSAs is way off.
(However, this is possible in an extremely mobile case in which half
of the neighbors are lost every MinLSInterval, which I guess is your point,
but in such a case routing would be difficult anyway, and full LSAs would
provide better robustness.)

In general, I agree that you will get larger LSAs than with MPR-based LSAs,
but there are also drawbacks which have been discussed (also see below).

> O(n^3) but faster because off-line, that you proposed in TBRPF.

To clarify, TBRPF does NOT use min-cost LSAs, but uses a similar 
computation to decide
which parts of the source tree to advertise.  The computation will be 
faster with
min-cost LSAs, since LSAs are smaller on average (as discussed above and 
verified
in simulations).

> Anyway the cost with MPR will be much smaller and lead to smaller 
> LSA’s. In your example you show that using metric in MPR computation 
> will lead to more MPRs than with min-hop metric, that we all know, but 
> the number of min-cost MPRs will still be smaller than the min-cost 
> links computed your way (since the MPR selector has the central 
> position). 

Yes, but the difference is that MPRs are used for flooding, whereas 
min-cost LSAs
are independent of the flooding mechanism!  So, in using metrics with 
MPRs, you
increase the number of MPRs and your flooding overhead.  This is an 
important
advantage of min-cost LSAs.  As a reminder, I will again list some 
advantages
of min-cost LSAs over MPR-based LSAs.

1. Min-cost LSAs are decoupled from selection of flooding relays.
2. Min-cost LSAs depend only on neighbors' LSAs and 2-hop neighbor
  information, and does not have to wait for neighbors to select
  MPRs (which depends on the neighbors' 2-hop information).
  This allows faster response to topology changes.
3. Including metrics in Hellos does not allow MPRs to provide
  true min-cost paths, unless Hellos also include the metrics
  of the reverse links, which requires additional overhead and delay.
4. Providing redundant paths requires selecting and advertising
  redundant MPRs, whereas min-cost LSAs can provide redundant paths
  without exchanging any additional information.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Mon, 09 Jan 2006 17:43:18 -0800

Philippe,

I made an error that I would like to correct (below).

 > provide better robustness.)

It turns out that this is true ONLY if all routers originate LSAs at the
same time. However, this should NOT happen in OSPF, since RFC 2328, 
Section 4.4
states that routers should use random timers to avoid synchronization of
routing packets. In particular, in an extremely mobile network, each router
will originate an LSA every MinLSInterval, but (in a good implementation)
different routers will originate LSAs at different times.
Thus, the first router i that originates a new LSA following a topology 
change
will modify its LSA and possibly add a new neighbor k to its LSA.
The neighbors of router i will then see that k has been added to its LSA,
and will thus not redundantly add k to their respective LSAs.
As a result, the average number of neighbors per LSA will remain O(1)
and the processing time will be O(n^2), even in this highly mobile scenario,
under the assumption that different routers originate LSAs at different 
times.
Hopefully, we can finally agree on this.

You might argue that multiple routers will still originate a new LSA
in response to a single link failure, when mobility is slow enough so
that MinLSInterval is not an issue, but in this case a single link failure
will at most cause one neighbor k to be added to each router's LSA.
Also, even this can be avoided by having each router wait a small
random delay before originating a new LSA.

Richard

---

From: Philippe Jacquet <[email-masked]>
Date: Mon, 16 Jan 2006 22:10:40 +0100

Dear Richard,

I agree that it is important to distinguish between flooding and link 
advertisement. OLSR is doing that by allowing an advertised set larger 
than the MPR selector set. But since with OSPF one must synchronize on 
all advertised links and that flooding should be done on synchronized 
links, the advertisement of MPR links should be a good compromise on the 
performance plan (shortest path to destination)  and on the overhead 
plan (smaller than your min-cost LSA). Of course LSA can indicate metric 
on MPR links and additional min-cost MPR can be added as well.

Best regards,
Philippe

Richard Ogier wrote:

>> <>Coming back to your min-cost LSA argument, it is known for long 
>> that listing the pair of nodes for which a given node is within the 
>> edges. Computing the shortest path from a given node to other nodes 
>> is O(m). Therefore MPR is less costly in computation than min-cost 
>> links. In your example you assume that the network is stable and that 
>> the LSA are already very small. But at the beginning all the LSAs 
>> will be full and computations will still be O(n^3) and will converge 
>> slowly. This is not appropriate if the network frequently changes. 
>> Furthermore it seems that if you have LSA that are still 50% of full 
>> LSAs which is not that small, then the cost should still be O(n^3). <>
>>
> Thus, the first router i that originates a new LSA following a 
> topology change
> under the assumption that different routers originate LSAs at 
> different times.

---

From: Richard Ogier <[email-masked]>
Date: Tue, 17 Jan 2006 08:29:32 -0800

Philippe,

Philippe Jacquet wrote:

> links, the advertisement of MPR links should be a good compromise on 
> the performance plan (shortest path to destination)  and on the 
> overhead plan (smaller than your min-cost LSA). Of course LSA can 
> indicate metric on MPR links and additional min-cost MPR can be added 
> as well.

First of all, as has been discussed, it is not necessary to synchronize
(directly) on all advertised links in an OSPF extension.
Therefore, there is no need to compromise by using MPR-based LSAs.
(Also, as has been discussed, synchronizing on all MPR links would
result in much more overhead than necessary, and none of the
proposed designs do this, although Cisco has proposed selecting
MPRs on a reduced set of adjacencies, but these do not provide
min-hop paths.)

When comparing the size of min-cost LSAs to MPR-based LSAs,
for fairness you need to consider LSA stability, since
the greedy algorithm you are using for MPRs does not result
in stable LSAs.  An algorithm that selects MPRs persistently
would result in a larger number of MPRs.

The larger number of neighbors in min-cost LSAs is directly
related to increased robustness, as the following example
shows, and the number can be reduced simply by allowing
LSAs from 2-hop neighbors to be used.

       1
      /|\
     / | \
    2  3  4
     \ | /
      \|/
       5

In the above example, if node 4 includes neighbors 1 and 5 in its
min-cost LSA, then node 3 would not include these neighbors in its LSA,
but node 2 would include them, assuming that LSAs from 2-hop neighbors
are not used to construct min-cost LSAs.  As a result, if the link
from 1 to 4 fails, then node 1 immediately has an alternate path
to node 5 via node 2.  If MPR-based LSAs are used, then nodes 1 and 5
might select node 4 as MPR, so only node 4 would include 1 and 5 in its
LSA.  Then, if the link from 1 to 4 fails, consider all the steps that
must be taken before node 1 knows it has a path to node 5 via node 2.
(Let's not assume that node 1 can use 2-hop neighbor info for routing,
since OSPF does not do this.)
Node 5 would have to learn about the failure of the link from 1 to 4,
then node 5 would have to inform node 3 that it has been selected
as an MPR, then node 3 would have to originate a new LSA that includes
node 5, so that node 1 knows it can reach node 5 via node 3.

Now consider a variation of min-cost LSAs in which each node uses
LSAs from 2-hop neighbors.  If node 4 includes neighbors 1 and 5 in its
min-cost LSA, then nodes 2 and 3 would not include these neighbors
in their LSAs (since node 4 is a 2-hop neighbor of 2 and 3).
Now, if the link from 1 to 4 fails, then node 3 would quickly
learn about this failure and would add nodes 1 and 5 to its LSA.
This is actually faster than with MPR-based LSAs (in which node
5 had to learn about the failure and select 3 as a new MPR).

Richard

>>> links. In your example you assume that the network is stable and 
>>> that the LSA are already very small. But at the beginning all the 
>>> LSAs will be full and computations will still be O(n^3) and will 
>>> converge slowly. This is not appropriate if the network frequently 
>>> changes. Furthermore it seems that if you have LSA that are still 
>>> 50% of full LSAs which is not that small, then the cost should still 
>>> be O(n^3). <>
>>>

---

From: Richard Ogier <[email-masked]>
Date: Tue, 17 Jan 2006 10:59:58 -0800

The graph for my example was not quite right.
Nodes 2 and 4 should be neighbors of node 3
(but not neighbors of each other).
Here is the corrected graph.

      1
     /|\
    / | \
   2--3--4
    \ | /
     \|/
      5

Richard

Richard Ogier wrote:

>> advertisement. OLSR is doing that by allowing an advertised set 
>> larger than the MPR selector set. But since with OSPF one must 
>> synchronize on all advertised links and that flooding should be done 
>> on synchronized links, the advertisement of MPR links should be a 
>> good compromise on the performance plan (shortest path to 
>> destination)  and on the overhead plan (smaller than your min-cost 
>> LSA). Of course LSA can indicate metric on MPR links and additional 
>> min-cost MPR can be added as well.
>
>
>
>>>> 50% of full LSAs which is not that small, then the cost should 
>>>> still be O(n^3). <>
>>>>

---

From: Philippe Jacquet <[email-masked]>
Date: Mon, 23 Jan 2006 14:36:10 +0100

Dear Richard,

I am sure that there are very good reasons why OSPF needs that 
advertized links be synchronized. If you don’t do so then this will be a 
strong exception to the fact that wired OSPF should not be affected by 
the wireless extension, since wired nodes would receive non-synchronized 
link advertizements.

I agree that synchronizing links may create overhead when the network is 
changing fast. It means that wireless OSPF networks will not be allowed 
to change as fast as MANETs may do, but I understood that this 
restriction was already in the spec of wireless OSPF (you already 
acknowledged that fast speed was out of spec). By the way, we have shown 
that MPR links will generate a number of synchronizations that is 
similar to your bi-connected CDS, and in theory not more than two or 
three times a minimal tree CDS (but the later has a tremendously larger 
stretch). MPR links have the advantage to generate no stretch at all, 
since positive stretch is an overhead proportional to data traffic

If synchronization is the main problem gainst fast moving extensions, 
then the solution will be less in a further reduction of the number of 
synchronized links (we are close to minimal), than in a reducion of the 
overhead of each synchronization process, where there is plenty room for 
optimization. For example, a signature based database check and exchange 
could be used, as we suggested in [1], [2] (log n cost for one isolated 
mismatch instead of full cost n scanning). You also have suggested 
something close in an old presentation. Optimizing database exchange 
could be a further topic added to manet-ospf when the need for fast 
changing wireless OSPF will be expressed. MPR based advertisement and 
flooding is nevertheless a good provision even for potentially fast 
moving wireless OSPF.

Best regards,
Philippe

[1] *OSPF Database Exchange and Reliable Synchronization in Mobile Ad 
Hoc Networks, Proceedings of WNET 2004
self.d.free.fr/cv/publications/WNET_2004.pdf

[2] http://www.watersprings.org/pub/id/draft-clausen-manet-ospf-dbx-00.txt

---

From: Richard Ogier <[email-masked]>
Date: Mon, 23 Jan 2006 09:58:19 -0800

Phlippe,

I forgot to mention that using MPR links as the set of adjacencies
does not even work!  (This has been mentioned before.)
One such example is a fully connected network, which has no MPRs,
but there are many other examples.  This discussion is going in circles.
We have two candidate solutions (OSPF-MDR and Overlapping Relays with
Smart Peering) that do work, so the focus should be to compare these
two solutions.  Simulation results comparing these two solutions should
be available before the next meeting, so I look forward to seeing those
results.

Maybe MPRs are useful for MANETs, but that does not necessarily mean
they are the best way to extend OSPF.

Richard

Philippe Jacquet wrote:

> advertized links be synchronized. If you don’t do so then this will be 
> a strong exception to the fact that wired OSPF should not be affected 
> by the wireless extension, since wired nodes would receive 
> non-synchronized link advertizements.
>
> I agree that synchronizing links may create overhead when the network 
> is changing fast. It means that wireless OSPF networks will not be 
> allowed to change as fast as MANETs may do, but I understood that this 
> acknowledged that fast speed was out of spec). By the way, we have 
> shown that MPR links will generate a number of synchronizations that 
> is similar to your bi-connected CDS, and in theory not more than two 
> or three times a minimal tree CDS (but the later has a tremendously 
> larger stretch). MPR links have the advantage to generate no stretch 
> at all, since positive stretch is an overhead proportional to data 
> traffic
>
> synchronized links (we are close to minimal), than in a reducion of 
> the overhead of each synchronization process, where there is plenty 
> room for optimization. For example, a signature based database check 
> and exchange could be used, as we suggested in [1], [2] (log n cost 
> for one isolated mismatch instead of full cost n scanning). You also 
> have suggested something close in an old presentation. Optimizing 
> database exchange could be a further topic added to manet-ospf when 
> the need for fast changing wireless OSPF will be expressed. MPR based 
> advertisement and flooding is nevertheless a good provision even for 
> potentially fast moving wireless OSPF.
>
> Best regards,
> Philippe
>
> [2] 
> http://www.watersprings.org/pub/id/draft-clausen-manet-ospf-dbx-00.txt
>
>
> Richard Ogier wrote:
>
>> Philippe,
>>
>> Philippe Jacquet wrote:
>>
>>> Dear Richard,
>>>
>>>
>>>
>>> I agree that it is important to distinguish between flooding and 
>>> link advertisement. OLSR is doing that by allowing an advertised set 
>>>>> that listing the pair of nodes for which a given node is within 
>>>>> the shortest path is O(n^3). Exactly O(nxm) where m is the number 
>>>>> of edges. Computing the shortest path from a given node to other 
>>>>> nodes is O(m). Therefore MPR is less costly in computation than 
>>>>> min-cost links. In your example you assume that the network is 
>>>>> stable and that the LSA are already very small. But at the 
>>>>> beginning all the LSAs will be full and computations will still be 
>>>>> O(n^3) and will converge slowly. This is not appropriate if the 
>>>>> network frequently changes. Furthermore it seems that if you have 
>>>>> LSA that are still 50% of full LSAs which is not that small, then 
>>>>> the cost should still be O(n^3). <>
>>>>>

---

From: Emmanuel Baccelli <[email-masked]>
Date: Wed, 25 Jan 2006 11:10:10 +0100

> they are the best way to extend OSPF.

Richard,

you have mentionned this full mesh counter-example several times. 
However, it is not
appropriate in that if the topology is a simple full mesh, routing is 
not even needed.
You talk about other counter-examples, it may be interesting for us to 
know about these other
examples. Maybe these are indeed appropriate?

Moreover, you again consider an isolated wireless OSPF, which is not 
more than a manet.
In this case, synchronization is not really needed. On the other hand, 
if we consider the OSPF network
to be connected to the Internet, and to contain both traditional OSPF 
nodes and MANET-OSPF
nodes (I assume this is still the main case we are addressing in this 
design team) synchronization
is then important. I think that in this architecture, it is more 
appropriate to use MPR adjacencies,
with hybrid nodes (nodes that feature both MANET interfaces and 
traditional interfaces)
advertising their whole neighbourhood, making the set of MPR links a 
single connected component.
This also provides shortest paths from any wired node to any wireless 
node (while it is not the case with MDR).

Emmanuel

---

From: Richard Ogier <[email-masked]>
Date: Mon, 30 Jan 2006 14:12:02 -0800

Emmanuel,

Please see my response below.

> examples. Maybe these are indeed appropriate?

I presented some examples on the wireless design team list
on 10/27/2005, so I assumed you already saw them.
Anyway, here are some examples for those who did not see
my previous post.

      1
     / \
    2   3
     \ /
      4

In the above example, it is possible that 1 and 2 select each
other as MPRs, and that 3 and 4 select each other as MPRs.
So the adjacences would be [1,2] and [3,4], which does not
form a connected subgraph.

Someone might argue that a node can break ties by selecting
the node with largest ID as MPR (although this might not
be true if you want to select MPRs persistently).
There are plently of examples where this does not help,
such as the following:

      1
     / \
    2---3
     \ /
      4

In this example, nodes 1 and 4 both select node 3 as MPR,
so node 2 has no adjacencies.

Of course, there are many other examples where the set of
MPR links does not form a connected subgraph.
It may be possible to select MPRs carefully and to add
some additional adjacencies to ensure the adjacency
subgraph is connected and spanning, but you need to
specify the algorithm and show how it performs.

You say that routing is not needed in a fully connected MANET.
That is like saying OSPF does not need to support broadcast networks
because routing is not needed within a broadcast network. :-)
An OSPF area can contain multiple MANET and non-MANET interfaces,
so you still need to route from one network to another,
even if the network happens to be a fully connected MANET.

Also, the nature of a MANET is that we cannot predict its topology,
so some MANETs might happen to be fully connected (perhaps for a short
time).  A large MANET could also become temporarily partitioned, and
one of its connected components might happen to be fully connected.
So it would not be good to propose a solution that fails when
the MANET happens to be fully connected.

But that is not a concern, because the two solutions that
we are considering both work in a fully connected network!
So I am not sure why we are even arguing about this.

Richard

---

From: Emmanuel Baccelli <[email-masked]>
Date: Tue, 31 Jan 2006 13:57:33 +0100

Richard,

If I am not mistaken, the examples you are considering are again pure 
MANETs (nodes with only OSPF-MANET interfaces, no connection to the 
Internet). In this case, MPR flooding and topology is proven to work 
very well (see OLSR), why do we need anything else than the solution 
designed by the MANET working group?

What differs in this design from pure MANET scenarii is that we want to 
consider the case where at least one node in the OSPF network is 
connected to the Internet via an (OSPF) interface of a type other than 
OSPF-MANET. We therefore consider the interaction between MANET-OSPF and 
traditional OSPF infrastructure.

In this case the MPR approach works very well too, with the additional 
rule that I have mentionned several times in my previous posts: hybrid 
nodes (nodes that feature at least two interfaces, one of the type 
OSPF-MANET, and one of another type) advertize their whole 
neighbourhood, and not just their MPR selectors. This simple rule makes 
the set of advertized links into a single connected component. 

Thus, in the example below that you mentionned, if one of the nodes 
features a connection to the Internet, it will advertize its whole 
neighborhood and this is enough to have a connected set of advertized 
links. For example, let's assume (as you do in your example) that 1 and 
2 chose each other as MPR and so did 3 and 4, and say 1 is connected to 
the Internet. Then 1 will not only advertize it's MPR selector link to 
2, but in fact all its links (and therefore also its link to 3). Thus 
the set of advertized links is indeed connected (link 2-1, link 1-3, 
link 3-4).

   1
   / \
  2   3
   \ /
    4

Of course, the "connected" property stays even if a node other than 1 
(may it be 2, 3 or 4) is connected to the Internet. And the same goes 
for the other examples you have mentionned.

Moreover, this method presents a significant advantage over MDR, as I 
have already mentionned in my previous posts. MPRs obviously provides 
the shortest paths between wireless nodes inside a MANET-OSPF 
(sub)network, but MPRs also provides the shortest paths from any wired 
node (in a traditional part of the OSPF network) to any wireless 
MANET-OSPF node. On the other hand, with MDR, such a path from a wired 
node to a wireless node may suffer some route stretching.

Emmanuel

>> In this case, synchronization is not really needed. On the other 
>> hand, if we consider the OSPF network

---

From: Richard Ogier <[email-masked]>
Date: Tue, 31 Jan 2006 13:22:29 -0800

Emmanuel,

> designed by the MANET working group?

The statement "MPR flooding and topology is proven to work very well" 
depends on
the context.  Has it been proven to perform well in the context of an 
OSPF extension?
If so, then we should be able to code it in GTNetS and compare it with 
OSPF-MDR.
I have run some simulations that show that requiring all MPR links to be 
adjacencies
results in a much larger rate of new adjacencies than OSPF-MDR, and I 
did all I could
to make MPR links as stable as possible. (I posted those result on the 
OSPF wireless
design list on 10/31/05.)

If you want to use MPRs, then a better approach would be to use 
OSPF-MDR, and select the
MDRs based on MPRs (i.e., use an MPR-based CDS).  Such a solution is 
described in

http://www.ietf.org/internet-drafts/draft-ogier-manet-ospf-mdr-ext-00.txt

However, I also ran some simulations that show this too results in a 
larger rate of
new adjacencies than OSPR-MDR.  Still, the fact that OSPF-MDR allows the 
option of
using MPRs is evidence that it is flexible and extensible.
(More comments below.)

>
>
> What differs in this design from pure MANET scenarii is that we want 
> to consider the case where at least one node in the OSPF network is 
> OSPF-MANET. We therefore consider the interaction between MANET-OSPF 
> and traditional OSPF infrastructure.
>
> neighbourhood, and not just their MPR selectors. This simple rule 
> makes the set of advertized links into a single connected component. 

That is true.  And if you didn't have a hybrid node, you can still have 
a node
advertise its whole neighborhood (and become adjacent with all of its 
neighbors)
if it has a larger (RtrPri, RID) than all of its neighbors.  The latter 
is what
I simulated, and resulted in a large rate of new adjacencies.  This will 
work,
but my simulations indicate it will generate much more overhead than 
OSPF-MDR.

Richard

> links. For example, let's assume (as you do in your example) that 1 
> and 2 chose each other as MPR and so did 3 and 4, and say 1 is 
> connected to the Internet. Then 1 will not only advertize it's MPR 
> selector link to 2, but in fact all its links (and therefore also its 
> link to 3). Thus the set of advertized links is indeed connected (link 
> 2-1, link 1-3, link 3-4).
>
>    1
>   / \
>  2   3
>   \ /
>    4
>

>>> to be connected to the Internet, and to contain both traditional 
>>> OSPF nodes and MANET-OSPF
>>> nodes (I assume this is still the main case we are addressing in 
>>> this design team) synchronization
>>> This also provides shortest paths from any wired node to any 
>>> wireless node (while it is not the case with MDR).
>>>
>>> Emmanuel
>>>