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

From: "Henderson, Thomas R" <[email-masked]>
Date: Mon, 16 May 2005 08:00:04 -0700

All,
This list has been quiet for a while, but I'd like to restart our
discussions.  We have been busy developing and experimenting with models
of both OSPF MANET proposals, and have some initial results to share
with the group.  For starters, please look at the attached document.  We
also have a fuller set of documentation, more results, and the source
code itself that is available to the design team.

Please remember that we are chartered to do the following work as
requested by Acee last year:

> The design team will: 
> 
>         1. Evaluate the proposals in the existing drafts. 
>         2. Determine which of these (or others) are best to 
> meet the initial
>             requirements (Given the work scope discussed on the OSPF 
>             mailing list). 
>         3. Report your concensus to the OSPF and MANET WGs.

I think that we have the tools in hand to do this work, and some
interesting data to look at, so please make this work a priority so that
we can meet our goal of reporting back to the WG by the Paris meeting.

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 10:58:23 -0700

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.

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

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.

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

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

Richard

---

From: "Joe Macker" <[email-masked]>
Date: Fri, 20 May 2005 16:27:33 -0400

Richard:

FYI, we have also implemented and modeled a separate version of MDR from the
Boeing models.
Its working in ns2 and in real code as an alternative to MPRs in SMF MANET.
It holds up well under some mobile scenarios of 30 nodes we have been
examining as does MPR.

Also as mentioned, we have an model comparing the size of relay sets of MPR
vs. MDR.
As you say it's a little more difficult to calculate this for MPRs.
I'll see if we have some results we can share on this point.

As you point out, I think the adjacency reduction is a key factor for
MANET-OSPF consideration.

-joe
> -----Original Message-----
> From: [email-masked] 
> [mailto:[email-masked]] On 
> Behalf Of Richard Ogier
> Sent: Friday, May 20, 2005 1:58 PM
> To: Henderson, Thomas R
> Cc: [email-masked]
> Subject: Re: [Ospf-wireless-design] some comparative results
> 
> Tom,
> 
> 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):
> 
> 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.
> 
> 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.
> 
> 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.
> 
> Since full adjacencies are not even feasible (as concluded 
> above), it would not make sense to optimize MDR for full adjacencies.
> 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.
> 
> 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).
> 
> 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.
> 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.
> 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.
>