Subject: Re: [Ospf-wireless-design] some comparative results

From: "Henderson, Thomas R" <[email-masked]>
Date: Fri, 20 May 2005 12:45:57 -0700

Richard, responses inline below 

> -----Original Message-----
> From: Richard Ogier [mailto:[email-masked]]
> Sent: Friday, May 20, 2005 10:58 AM
> To: Henderson, Thomas R
> Cc: [email-masked]
> Subject: Re: [Ospf-wireless-design] some comparative results
> 
> Tom,
> 
> I read the simulation comparison report and have several comments.
> 
> I am happy that these results confirm my belief that the MDR/BMDR 
> approach with biconnected adjacencies is efficient, scalable, and 
> robust. I was planning to add some robustness enhancements (in 
> response to some comments at the last IETF meeting that the approach 
> might not be robust), but it turns out that the biconnected backbone 
> provides sufficient robustness, so such enhancements were not 
> necessary.
> 
> This approach achieves efficiency and robustness in multi-hop wireless

> networks in the same way that the DR/BDR achieves efficiency and 
> robustness in OSPF broadcast networks: by reducing the set of nodes 
> that forward each LSA, by reducing the number of adjacencies, and by 
> providing biconnected redundancy. In my view, this approach works well

> because OSPF was designed well, and generalizes nicely to multi-hop 
> wireless networks.
> 
> My favorite graph is Figure 10.4(a), which shows the overhead as a 
> function of the number of nodes with full adjacencies and partial 
> adjacencies.  With full adjacencies, the graph grows guadratically, 
> and with biconnected adjacencies it is almost linear. I did a 
> quadratic extrapolation to estimate what the overhead would be for 
> more than 50 nodes. I also ran a 60-node simulation with biconnected 
> adjacencies to see how accurate the estimate is, and obtained an 
> overhead that is within 0.5% of the extrapolated value. Here are the 
> overhead values in kbps that I obtained for full and partial 
> adjacencies (results for 50 nodes are from simulations):
> 
>       Extrapolated overhead in kbps
> -------------------------------------------
> number of nodes       50    60    70    80
> -------------------------------------------
> full adjacencies     1750  3543  6040  9240
> biconnected           213   277   341   405
> -------------------------------------------
> 
> For 80 nodes, full adjacencies generate 9.24 Mbps of overhead!
> This is more than 20 times the overhead of 405 kbps generated by 
> biconnected adjacencies. So for 80 nodes, it is not even feasible to 
> use full adjacencies if the MAC data rate is 11 Mbps, but it is 
> feasible to use biconnected adjacencies even if the MAC data rate is 2

> Mbps.

Yes, I think that you are capturing the correct trend.  The actual
results for full adjacencies may diverge from this extrapolation,
but only because they will end up trashing the network when the
overhead gets to the 4-5 Mbps range (as can be seen from the
point-to-multipoint results for 50 nodes in Figure 10.2).

> 
> Therefore, I think we should be able to agree on the following
> conclusion: For the number of nodes that we wish to support, it is 
> simply not feasible to use full adjacencies.
> 
> One might consider reducing the overhead by using partial LSAs (e.g., 
> including only MPR selectors in LSAs) while still using full 
> adjacencies. However, this does not reduce the DD packet overhead, 
> which is still quadratic and will dominate the overhead when the 
> number of nodes is large.
> 
> Comparison of Overhead with Full Adjacencies
> 
> Section 10.2.1 observes that both approaches yield about the same 
> overhead, but the MDR approach has much less flooding overhead and 
> much more retransmission overhead than the OR approach. In particular,

> about 60% of the LSUs were unicast transmissions for MDR.
> 
> One possible reason for this is that MDR is not optimized for full 
> adjacencies. For biconnected adjacencies, with 20 nodes, only about 
> 22% of the LSUs were unicast retransmissions.
> Since full adjacencies are not even feasible (as concluded above), it 
> would not make sense to optimize MDR for full adjacencies.
> For full adjacencies, it might help to set BackupWaitInterval to be 
> larger than AckInterval (same as PushbackInterval).

In thinking about this, I agree that BackupWaitInterval should be
comparable to PushbackInterval.  The way it was configured (based
on the defaults you provided), backups may be firing before the
Ack has a chance to be received.  This might account for the large
number of retransmissions.  We will rerun these cases with
BackupWaitInterval equal to PushbackInterval and see what happens.

But I don't understand why you are limiting this to full adjacencies
only, unless you are trying to trade off some unnecessary
retransmissions to achieve faster LSA dissemination in the partial
topology case.

> 
> Size of Relay Set (relays per node)
> 
> I don't think you are correctly comparing the relay node set for the 
> two approaches.  It is not easy to compare these two, since MPRs are 
> source-dependent and MDRs are source-independent.
> For MPRs, you are counting the average number of MPRs selected by a 
> node.  For MDRs, you are counting the average number of MDR neighbors 
> a node has. (Note that a node can have neighbors that are MPRs for 
> other nodes, which is part of the reason why these are not easy to 
> compare.)
> 
> What I would like to know is the size of the "relay node set", i.e., 
> the set of relays that forward a given LSA given that all 
> transmissions are successful and no backup relays are needed.  For 
> MDRs, this is typically the set of of all MDRs (which is your measure,

> multiplied by the number of nodes, divided by the average node 
> degree). For MPRs, this depends on other factors, so it is not 
> proportional to your measure.  You can measure this by disabling all 
> backup relays and counting the number of LSA relay floods.
> (Although you do count the number of LSA relay floods, this might not 
> be a good measure of the size of the relay node set, since the large 
> number of non-relay floods with OR might suppress flooding by relays.)

> It would be interesting to correctly compare the relay node set for 
> MPRs versus MDRs.
> 

I don't know if I agree that we incorrectly compared them.  I understand
how you would like to count them, and for MDRs, that makes sense.
However, it seems to be quite an intricate computation for MPRs.  

But, maybe we should not rely on this metric (which is hard to get some
kind of meaningful apples-to-apples comparison by the very nature of
these flooding algorithms).  Aren't we really trying to estimate how
efficient the aggregate relay node set is in flooding, and indirectly
trying to estimate it by computing relay node set sizes?  Instead, what
if we just directly measured how many LSA "relays" occurred in a
simulation (throwing out retransmissions and backup transmissions)?

> Route Quality
> 
> Figure 10.5(f) shows that route quality is better using full LSAs than

> using min-hop LSAs, when biconnected adjacencies are used.
> However, I would like to point out that min-hop LSAs with biconnected 
> adjacencies provide better route quality than full LSAs with full 
> adjacencies, as can be seen by comparing this figure to Figure 
> 10.4(f).

This result in Figure 10.4(f) was a bit puzzling to us.  It is the one
graph that we have a hard time justifying with intuition.  Why should
an approach that limits topology (limits the amount of information)
result in better route quality?

> 
> Also, your measure of route quality can be misleading.
> It divides the number of receives by the number of forwards.
> But the number of forwards does not include the first forward by the 
> source. You do explain this measure correctly, but it would better to 
> use a measure that is proportional to the number of hops taken by a 
> packet, so that the stretch factor is more apparent.
> 
> Since your data might not supply the average number of hops taken by 
> each received packet, a similar measure would be the number of 
> receives plus the number of forwards, divided by the number of 
> receives.
> This measure can be obtained by your measure using the formula y = 1/x

> + 1, where x is your measure.
> 
> For example, the graph in Figure 10.5(f) indicates that the route 
> quality for full LSAs is about 2.6, compared to about
> 2.4 for min-hop LSAs.
> Thus, one might divide 2.6 by 2.4 and conclude that paths are 8.3% 
> longer using min-hop LSAs.
> 
> Using the formula y = 1/x + 1, the average path length for full LSAs 
> is 1.385, and the average path length for min-hop LSAs is 1.417.
> Thus, min-hop LSAs results in paths that are only 2.2% longer.
> This is less significant than 8.3%, and is an expected result due to 
> the delay in reacting to topology changes. Your report seems to imply 
> that this difference is significant, but does not quantify it.

I agree that we could come up with a different statistic here-- your
transformation is not affecting the result but just the magnitude of
the difference.  I agree that average path length seems more natural.

One subtle point that can cause some discrepancy (mentioned in the text)
is that, if the data packets used for computing path length are not
identical in the two runs, there can be some skew in the results (for
example, a data packet that takes a long circuitous path in one case may
be dropped in another, but the former case is penalized in the measure
of
its route quality, even though it successfully delivered a challenging
packet).  We have some scripts that can be used to throw out all
received
packets that do not match in two given simulation runs, but it requires
running full trace files and doing some post processing, so we did not
take it for these results.  I don't think it matters that much in the
results, based on looking at a sample of these path lengths, but we
should probably double check in the future.

> 
> I have one last comment on terminology. When Acee asked us to use 
> something other than DR/BDR for the SICDS approach, he mentioned 
> MDR/BMDR as one suggestion. I have been using BMDR for Backup MDR, but

> the comparison report uses MBDR and M(B)DR.
> Can we agree to use BMDR for Backup MDR?  I would rather call it a 
> Backup MDR, than a MANET BDR.
> 
Agreed.

Tom

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

---

From: Richard Ogier <[email-masked]>
Date: Fri, 20 May 2005 16:10:36 -0700

Tom,   A few responses below.

>retransmissions to achieve faster LSA dissemination in the partial

Actually, I'm not even sure setting BackupWaitInterval to be larger
than AckInterval will help much in the full adjacency case.
It might help more if the BMDR floods the LSA after (the larger)
BackupWaitInterval whenever some adjacent neighbor has not ACKed.
This would increase the number of backup relay floods (and hopefully
decrease the number of retransmissions), whereas just increasing
BackupWaitInterval would decrease the number of backup relay floods
(which is already small).

For partial adjacencies, as you say, I am trying to achieve faster
LSA dissemination. I want the flooding procedure to be independent
of the retransmission procedure (as much as possible), so waiting for
a possible ACK is not an important objective - covering all neighbors
is the main objective.  This independence is also important for the
non-ackable LSA option, i.e., for unreliable flooding without ACKs.
I still plan to experiment with the non-ackable option,
to see how it reduces overhead in large, highly mobile networks.

But practically, BackupWaitInterval should be set to whatever gives
the best performance, and I did not see any improvement with a larger
value of this parameter. It may reduce overhead a little, but may
also increase the number of out-of-sync LSAs.

>simulation (throwing out retransmissions and backup transmissions)?

I mentioned this above, but it might be simpler than I thought.
Each MPR or MDR forwards a new LSA the first time it is received,
unless the sending router covers all neighbors (which is
not very likely). So it might just be a matter of counting the
number of LSA relays. If this is the case, then Figure 10.2(b)
implies that the relay node set is larger for MDR. However, I
don't know the number of nodes for this graph.  I recall from
my simple simulations that the relay node set tends to be slightly
smaller with MPRs than with MDRs, but of course MDRs have other
advantages, so this measure by itself is of limited value.

>result in better route quality?

My guess is that with full adjacencies, a neighbor cannot be
included in an LSA until database exchange is finished, whereas
with partial adjacencies a new neighbor can be added to the LSA
more quickly.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Sun, 22 May 2005 08:21:31 -0700

Tom and all,

Since you have decided to compare the two approaches with full
adjacencies (even though I never optimized or even tested
MDR for full adjacencies), I have made a new change to MDR for
full adjacencies.  One of the recent changes to MDR is to
have a MDR/BMDR send a multicast ACK immediately when it receives
a duplicate, unicast LSA. This is because MDRs/BMDRs have more
adjacent neighbors than other nodes, so sending the ACK immediately
helps to prevent additional retransmissions from other adjacent
neighbors. When full adjacencies are used, *all* nodes have a large
number of adjacent neighbors, so it makes sense to have all nodes
send a multicast ACK immediately in this case.

I also made two other changes, which apply whether partial or
full adjacencies are used: I set BackupWaitInterval = 2000 msec,
and since this is a more significant delay, when a Backup MDR
floods an LSA, the retransmit time is reset for any LSA waiting
to be retransmitted (to any adjacent neighbor).
(Resetting the retransmit time was previously suggested by Phil,
but I did not include it before because BackupWaitInterval was
only 1000 msec, so it would not make much difference.)

With these 3 changes, I ran a simulation with 40 nodes and full
adjacencies, using the same parameters as in the simulation report.
For MDR, the overhead decreased to 613.83. This is about 15% less than
the overhead of 718.42 that I obtained for OR with full adjacencies.
(50 nodes with full adjacencies runs too slowly on my computer, but
I would like to see the results for 50 nodes.)

I also implemented a database exchange optimization which is proposed
in my draft, in which a router (either the master or slave) does not
include in its DD packets an LSA header if it knows the neighbor
has the same or newer instance of the LSA (based on DD packets
received from the neighbor). This is done simply by removing the LSA
from the summary list when the same or newer LSA is received in a
DD packet. This reduces the DD overhead by almost 50%, without
affecting the delivery ratio.
(This change was not included in the full adjacency simulation
discussed above.)

With the above 4 changes, I ran simulations for MDR with biconnected
adjacencies and with (B)MDR full LSAs.
This should be the same scenario as in Figure 10.4(a) of the report.
I ran simulations for 20 to 70 nodes. The overhead was linear
for 50, 60, and 70 nodes, so I extrapolated the overhead up to
300 nodes in the following table:

Nodes Overhead (kbps)
---------------------
20     36.53
30     70.05
40    124.33
50    166.14
60    237.08
70    305.11
80    374.61 (extrapolated)
90    444.11
100   513.61
150   861.11
200   1208.61
250   1556.11
300   1903.61

Based on these results, if the MAC data rate is 11 Mbps, then OSPF-MDR
should be able to support up to 300 nodes, for the density and mobility
parameters assumed in these simulations.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Sun, 22 May 2005 09:04:04 -0700

Tom,

One more comment on comparing the relay node sets.
Note that the greedy algorithm used to select MPRs uses information
related to node degree (i.e., the number of 2-hop neighbors covered
by a given neighbor) to minimize the number of MPRs. The drawback
of this is that MPRs are not persistent. If MPRs were selected in
a persistent manner, then there would be more of them, and
the relay node set would be larger. Thus, it is not fair to
compare the relay node set sizes for persistent MDRs and
non-persistent MPRs. (Of course, MDRs need to be persistent for
partial adjacencies, to maximize the adjacency lifetime.)

My simple simulations showed that the number of MDRs is smaller
if node degree is used (without persistence), for less than
100 nodes.  But for more than 100 nodes, using node degree
results in more MDRs (probably because they are concentrated
near the center of the node cluster).

If MPRs or MDRs are used for unreliable flooding (as the MANET WG is
doing), then it may not be important to use persistent MPRs/MDRs, so
MPRs may result in a smaller flooding overhead than MDRs in this case.
However, as has been discussed, MDRs converge more quickly following
link failures (because they are self-selected), which may result in
a better delivery ratio. MPRs can also be used for reliable flooding,
using other reliability mechanisms that do not require OSPF-type
adjacencies, or using a CDS that is based on MPRs. But it remains
to be seen whether MPR-based reliable flooding can be done as
efficiently as the MDR approach.

Richard