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

From: Richard Ogier <[email-masked]>
Date: Fri, 09 Dec 2005 14:08:35 -0800

An update to the OSPF-MDR draft can be found here:
http://www.ietf.org/internet-drafts/draft-ogier-manet-ospf-extension-06.txt

The changes are as follows:

   o  The min-cost LSA algorithm has been modified to improve its
      efficiency, by requiring each router to include in its router-LSA
      only neighbors to which (and not from which) a path is required.
      This reduces the number of neighbors that are included in each
      router-LSA by about 50%.
   o  The min-cost LSA algorithm has been extended to allow the option
      of providing redundant paths.
   o  The min-cost LSA algorithm has been extended to allow the option
      of using metric information advertised in Hellos, allowing min-
      cost paths to be calculated in all cases, without any conditions
      on the metrics.

The importance of providing min-cost or min-hop routes has recently
been discussed, so I thought it was important to update the min-cost
LSA algorithm to describe our recent improvements.  The algorithm
allows the option of advertising neighbor metrics in Hellos, which
allows min-cost routes to be calculated in all cases (with no
constraints on the metrics).  Without this option, the algorithm
still provides min-hop routes if all metrics are equal, and min-cost
routes if the metric is the same for all neighbors at a given node.
The reason we added the option of including metrics in Hellos
is so that min-cost routes can always be provided (if desired)
without having to flood full-topology LSAs. The increased overhead
of including neighbor metrics in Hellos will typically be much less
than the increased overhead of flooding full-topology LSAs.

This method is actually useful even if MPRs are used for flooding
(since it is independent of the flooding mechanism).

Although it has been noted that MPRs can be used to provide min-hop
routes (by including the MPR selectors in the router-LSA),
MPRs have the following limitation which prevents them from providing
min-cost routes. Suppose node i selects neighbor j as an MPR to reach
2-hop neighbor k. Then to provide min-cost routes (with arbitrary
metrics), node i would have to know the cost of the link from k to j;
therefore it would not be sufficient for each router to advertise the
cost to each neighbor in its Hellos.  (This is one of a number
of drawbacks resulting from the fact that the MPR selector cannot
directly see the 2-hop neighbor that must be covered.)

Although MPRs could be used to provide min-cost routing if the metric
is the same for all neighbors at a given node (by giving higher
priority to neighbors with smaller metrics when selecting MPRs),
this puts another constraint on MPRs which will affect the number
of required MPRs and the ability to select MPRs persistently.
Also, it would require redundant MPRs to be selected and advertised
if one wanted to provide redundant routes.  (It is possible to
select two sets of MPRs, one for flooding and one for LSAs, but
that adds complexity.)

Richard

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

---

From: Philippe Jacquet <[email-masked]>
Date: Sun, 11 Dec 2005 17:54:13 +0100

Dear Richard,

There is no problem to implement metrics via MPRs, and knowing the 
metric of the two-hop links is not a problem. Indeed OLSRv2 already 
implements this feature via extended tlv’s in the hello messages and 
this does not add significant overhead. In passing you must also be 
aware that link metric may not be necessary symmetric with respect to 
emitter and receiver and the measurement of such metric will necessitate 
specific local exchanges between neighbors.

It seems that your min-cost LSAs have some paternities in SRI’s TBRPF 
draft. In this case you already know that the number of selected 
neighbors will be much larger than those obtained with MPR selected on 
the same metric. Of course the metric MPRs will be not the same as the 
min-hop MPR. However this is again important to minimize their number 
since you have to synchronize with these extra nodes.

Nevertheless you must be aware that differentiated metrics in wireless 
networks are difficult to manage, because links are not isolated and 
affect each other on several hops. Indeed the neighbour links tends to 
have the same metric and a min-hop route is very often the best choice 
(because it reduces the overall load).

Now if you really want to exploit differentiated metrics then you must 
take into account that a route may affect the bandwidth of any of its 
links several times (via the neighbour links, the two-hop neighbour 
links, etc), and current min-cost path calculation generally don’t take 
this into account.

Probably the most pertinent metric protocol would be to affect to each 
link the bandwidth of the emitter node and the node queueing delay.

Best regards,
Philippe

---

From: Philippe Jacquet <[email-masked]>
Date: Sun, 11 Dec 2005 18:13:16 +0100

Dear Richard,

I have run some simulations on min-cost LSA. If it is similar to TBRPF 
like algorithm then it is very heavy, it runs in O(n^3), I guess. If I 
remember, in the min-hop metric, it is strictly equivalent to select 
MPRs in the inverse order of their priority but since it is done at 
other end of the link it costs O(n^3) computation time. I obtain the 
following results in a 2x2 square:

nodes number, MPR links

10             10.50

20             32.72

30             57.56

40             84.14

50             114.56

60             143.88

70             178.64

80             211.04

90            241.80

100         273.90

node number min_cost links (min hop)

10        11.84

20:         47.52

30:         95.26

40:         150.98

50:         210.00

60:         275.80

70:         351.92

80:         421.82

90:         505.84

100:         577.52

Therefore the min-cost links tends to be twice the number of MPR links 
in a dense network.

Best regards,
Philippe

---

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

Philippe,

First of all, the min-cost LSA algorithm can be run in O(n^2) time. This is
because, for each neighbor, the algorithm only needs to consider existing
neighbor LSAs that include this neighbor. As your simulations imply, there
is only a constant number of such LSAs per neighbor! This is one of the
reasons I decided to make use of neighbor LSAs, instead of relying entirely
on metrics from Hellos.

Second, I do not mind that min-cost LSAs are larger than MPR-based LSAs.
Both are much smaller than full LSAs, and the additional links provide
more robustness. Also, as I have repeatedly pointed out (also see my
next email), there is an additional delay in waiting for MPRs to be
updated and reported.

Third, if you want to provide redundant (disjoint) paths, then you will
have to select and report redundant MPRs. If metrics change, you will
have to update MPRs more frequently, thus affecting the stability
of MPRs which may be important if adjacencies are based on MPRs.
If you use any metric other than the min-hop metric, you will not
be able to eliminate as many redundant MPRs, since you must provide
a min-cost path (not just a min-hop path) to each 2-hop neighbor.
In general, it is good to separate the construction of LSAs from
the selection of flooding relays.

Fourth, do MPR links provide a min-cost path to a 1-hop neighbor,
if the min-cost path to the neighbor is 2 or more hops?
Min-cost LSAs will do this.

> implements this feature via extended tlv's in the hello messages and 
> emitter and receiver and the measurement of such metric will 
> necessitate specific local exchanges between neighbors. 

Of course I am aware that link metrics may not be symmetric.
That is why I pointed out that MPR links cannot provide min-cost routing
based on only knowing the metrics of links (j,k) where j is a neighbor.
The MPR selector must also know the metric of the reverse link (k,j)
where k may be a 2-hop neighbor. Are you saying that OLSR also advertises
the metrics of the reverse links in Hellos? Of course, that requires
additional overhead and causes additional delays.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Sun, 11 Dec 2005 19:47:53 -0800

Philippe,

I forgot to mention another reason why the min-cost LSA algorithm
uses neighbor LSAs (instead of using only 2-hop neighbor information
from Hellos).  In addition to reducing the running time to O(n^2),
it provides stability/persistence of LSAs.  When a router is already
advertising a given neighbor k in its LSA, it has a higher
priority for continuing to advertise neighbor k.  The only reason
it would stop advertising neighbor k is if another neighbor can
provide a lower cost path to k (from some other neighbor).

MPRs can also be selected persistently (and they should be if
adjacencies depend on MPRs, even via an MPR-based CDS).
However, if MPRs are selected to be persistent, or are based on
a metric other than min-hop, then the number of MPRs will be larger.
(Have you run simulations for this case?)
The reason is that the greedy heuristic is not as effective since
MPRs can no longer be selected based only on the number of 2-hop
neighbors that are covered.

The example below shows that the number of MPRs can be much larger
when they must be selected to provide min-cost paths.  This is one
of the reasons why it is better to decouple the construction of LSAs
from the selection of MPRs for flooding (as with min-cost LSAs).

Example:  Node x has the ten neighbors y_1,..., y_10.
Each node y_k has the ten neighbors z_1,..., z_10.
The metric between node x and each node y_k is 1.
The metric between y_k and z_j is 1 if k = j, but is 2
if k is not equal to j.

If all metrics were 1, then node x would have a single MPR,
e.g., y_1, which would cover all nodes z_1,..., z_10.

But if MPRs must be selected to provide min-cost paths using
the above metrics, then node x must select all ten neighbors
y_1,..., y_10 as MPRs, to provide a path of cost 2 to each
node z_1,..., z_10.

So, it is best to decouple the LSAs from the selection of flooding
relays.  In summary, I prefer min-cost LSAs over MPR-based LSAs for
the following reasons:

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: Tue, 13 Dec 2005 10:27:36 -0800

Philippe,

Another important metric, besides the number of links, is the
frequency that the LSA changes, since in OSPF a new LSA is
originated when its contents change. (I realize that your
experience is mainly with OLSR and not OSPF.)
Your simulations do not show this metric, and the MPR algorithm
you are using does not attempt to select MPRs persistently,
whereas the min-cost LSA algorithm keeps existing links
as long as they provide min-cost paths.

If you select MPRs persistently, e.g., by giving priority to
existing MPRs, then the number of MPRs will be larger, closer
to the number obtained with the min-cost LSA algorithm.

So, considering the advantages of min-cost LSAs over MPR-based
LSAs (listed below), I don't think one can conclude that
MPR-based LSAs are better than min-cost LSAs.
One might even conclude just the opposite.

This (and the fact that the different mechanisms of a protool
are inter-dependent) shows that we need to evaluate the protocol
as a whole (using realistic models and scenarios), as others
have said.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Fri, 16 Dec 2005 10:18:21 -0800

Philippe,

Since you want to evaluate MPRs versus MDRs by themselves
(independently of backup relays), I thought of another
advantage of a source-independent CDS (i.e., MDRs).

One of the properties of MPRs is that the LSA is forwarded
immediately only if the *first* neighbor from which it is
received is an MPR selector.  If, due to unreliable links,
the router does not hear the transmission from the MPR
selector, but receives the LSA from another neighbor
that is not an MPR selector, then the LSA is not forwarded.
In contrast, an MDR does not care which neighbor the LSA
was received from, so it will forward the LSA regardless
of which neighbor it was received from.
This seems to provide better robustness to unreliable links.

In fact, there are situations in which MPRs (without backups)
simply fail, even if links are reliable (or if ACKs and
retransmissions are used to ensure all neighbors receive
each transmitted LSA).  The following example shows this:

             8
            / \
           /   \
    4 --- 5 --- 6 --- 7
      \   | \ / |    /
       \  |  /  |   /
        \ | / \ |  /
         \|/   \| /
          2 --- 3
           \   /
            \ /
             1

Node 1 originates an LSA.
Node 2 selects 6 as MPR to reach 7 and 8.
Node 3 selects 5 as MPR to reach 4 and 8.
It is possible that node 5 receives the LSA first from node 2
(which did not select node 5 as MPR)
and that node 6 receives the LSA first from node 3
(which did not select node 6 as MPR).
For example, this can occur if node 2 transmits the LSA before
node 3, but node 6 does not receive this transmission (but
perhaps receives a later retransmission).
Therefore, in this example, neither node 5 nor node 6
will flood the LSA, so node 8 will never receive the LSA.

There are ways to fix this, but this can add complexity
and overhead.  One simple way to fix it is to use the
CDS obtained by pruning MPRs (in which case a CDS node will
forward the LSA regardless of which neighbor the LSA is first
received from).  This shows another advantage of the CDS
approach (whether or not the CDS is based on MPRs).

Richard

P.S. Another difference between self-selected MDRs
and neighbor-selected MPRs (which I have mentioned before)
is that, since MDRs depend only on 2-hop neighbor information
with respect to the relay itself (not with respect to neighbors
of the relay as with MPRs), each non-MDR router has the property
that each of its neighbors should be covered by a neighboring MDR.
Thus, a non-MDR (e.g., a backup MDR) can decide to flood a received
LSA after a small delay (BackupWaitInterval) if there exists a
neighbor that is not covered by some neighbor that flooded the LSA
(independently of ACKs).  MPRs do not have this property, since
a non-MPR (for a given node X) may not have any neighbor that
is an MPR (for node X).  Thus, backup MPRs cannot flood based on
which neighbors have been covered, but can flood/retransmit based
on ACKs.  With partial-topology adjacencies, it is not clear
whether the backup MPR should multicast the LSA, or unicast
the LSA only to adjacent neighbors from which an ACK was not
received (as a BDR does in OSPF).  If a neighbor sent an ACK but
the backup MPR did not receive the ACK, then multicasting the LSA
would not do any good, since the neighbor will not ACK the LSA
again unless it is received as a unicast.
(With MDRs, it is clear that a backup MDR should multicast the
LSA if some neighbor was not covered, since we are not even
talking about ACKs. This never occurs in OSPF because in
a broadcast network all neighbors are always covered!)

---

From: Philippe Jacquet <[email-masked]>
Date: Mon, 19 Dec 2005 18:53:26 +0100

Dear Richard,

I was in Thailand for AINTEC the last week and had only very limited 
connection to internet (close to none), sorry! You answered me with five 
email on the mailing list and I am a kind of confused. I'll try to give 
short answers, but we should probably resume this discussion after new 
year (my vacations start tomorrow).

I saw several issues  in your long emails that address the following 
points :

1. the performance of flooding mechanisms, how MPRs and MDRs differ

2. the cost of your min-cost LSA.

I will try to sort out my comments on point 1. I will address point 2 in 
a separate email.

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.

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. 

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

Regards,
Philippe

---

From: Philippe Jacquet <[email-masked]>
Date: Tue, 20 Dec 2005 11:33:41 +0100

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.

Sorry, I can only give a short answer. I will resume the discussion 
after new year.

Please have a merry Christmas and a happy new year.

Best regards,
Philippe

Richard Ogier wrote:

>> I have run some simulations on min-cost LSA. If it is similar to 
>> TBRPF like algorithm then it is very heavy, it runs in O(n^3), I 
>> guess. If I remember, in the min-hop metric, it is strictly 
>> equivalent to select MPRs in the inverse order of their priority but 
>> since it is done at other end of the link it costs O(n^3) computation 
>> time. I obtain the following results in a 2x2 square:
>>
>> nodes number, MPR links
>>
>> 10 10.50
>>
>> 20 32.72
>>
>> 30 57.56
>>
>> 40 84.14
>>
>> 50 114.56
>>
>> 60 143.88
>>
>> 70 178.64
>>
>> 80 211.04
>>
>> 90 241.80
>>
>> 100 273.90
>>
>> Therefore the min-cost links tends to be twice the number of MPR 
>> links in a dense network.
>>
>> Best regards,
>> Philippe
>>
>> Richard Ogier wrote:
>>