OSPF Working Group R. Ogier
Internet-Draft SRI International
Intended status: Informational March 8, 2009
Expires: September 2009
Comparison of OSPF-MDR and OSPF-MPR
draft-ogier-ospf-manet-mdr-mpr-comparison-01.txt
Status of this Memo
This Internet-Draft is submitted to IETF in full conformance with the
provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress."
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/1id-abstracts.html
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html
Copyright Notice
Copyright (c) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document.
Abstract
This document presents a comparison of two proposed MANET extensions
of OSPF: OSPF-MDR and OSPF-MPR. It includes a qualitative
comparison, which discusses the different design choices and how they
can affect performance and scalability, and a simulation comparison.
Ogier Expires September 2009 [Page 1]
Internet-Draft MANET Extension of OSPF March 2009
Table of Contents
1 Introduction ................................................. 3
2 Brief Overview of OSPF-MDR ................................... 4
3 Brief Overview of OSPF-MPR ................................... 4
4 Qualitative Comparison ....................................... 5
4.1 Adjacency Reduction .......................................... 5
4.2 Backup Relays ................................................ 5
4.3 MPR Flooding versus MDR/CDS Flooding ......................... 5
4.4 Router-LSAs .................................................. 6
4.5 Inclusion of Non-adjacent Neighbors in LSAs .................. 7
4.6 OSPF-MPR's Synch Router ...................................... 8
5 Simulation Results ........................................... 8
5.1 Results for Dense Networks .................................. 9
5.2 Results for Sparser Networks ................................ 10
5.3 Effect of External LSAs ..................................... 11
6 Conclusions ................................................. 12
7 Security Considerations ..................................... 13
8 IANA Considerations ......................................... 13
9 Informative References ...................................... 13
A Instructions for Running Simulations ........................ 13
A.1 Running OSPF-MDR Simulations ................................ 13
A.2 Running OSPF-MPR Simulations ................................ 14
Author's Address ............................................ 14
Ogier Expires September 2009 [Page 2]
Internet-Draft MANET Extension of OSPF March 2009
1. Introduction
This document presents a comparison of two proposed MANET extensions
of OSPF: OSPF-MDR [OSPF-MDR] and OSPF-MPR [OSPF-MPR]. It includes a
simulation comparison and a qualitative comparison that discusses the
different design choices and how they can affect performance and
scalability. The conclusions of this document can be summarized as
follows:
o Simulations show that OSPF-MPR forms a much larger number of new
adjacencies per second than OSPF-MDR in large mobile networks
when both protocols use adjacency reduction. In a scenario with
100 nodes, OSPF-MPR formed about 12 times as many adjacencies as
OSPF-MDR, resulting in about 11 times as much overhead from
Database Description (DD) packets. Overhead from DD packets can
be very substantial if there is a large number of
inter-area-prefix-LSAs or AS-external-LSAs.
o OSPF-MDR with adjacency reduction and min-cost LSAs generates
much less overhead and is much more scalable than OSPF-MPR
(see simulation results). For example, OSPF-MDR with min-cost
LSAs generates less overhead with 160 nodes than OSPF-MPR
generates with 100 nodes. OSPF-MDR with minimal LSAs (which
OSPF-MPR does not provide) generates less overhead with 200
nodes than OSPF-MPR generates with 80 nodes.
o OSPF-MDR is more flexible than OSPF-MPR. For example, OSPF-MDR
provides two LSA options that OSPF-MPR does not provide:
(1) Minimal LSAs, which allow scalability to 200 nodes while
providing routing along nearly shortest paths.
(2) Full-topology LSAs with adjacency reduction, which allows
full-topology LSAs with lower overhead. OSPF-MPR does not
provide this option since it only advertises adjacent
neighbors in LSAs.
o OSPF-MPR does not provide any backup flooding; thus flooding of
LSAs can be delayed while MPRs are being updated.
o OSPF-MPR uses MPR flooding while OSPF-MDR uses MDR/CDS flooding.
MPRs are source-dependent and neighbor-selected, while MDRs
are source-independent and self-selected. Each method has
advantages, so it is important to compare the whole protocols
rather than compare MPR versus MDR flooding in isolation.
o In OSPF-MPR, the router with the largest Router ID is given an
unfair burden, since as a "synch router" it must form an adjacency
with each of its neighbors. This is true regardless of its router
priority. (OSPF-MDR uses router priority when selecting MDRs.)
o In OSPF-MPR, the first hop of a route need not be synchronized or
Ogier Expires September 2009 [Page 3]
Internet-Draft MANET Extension of OSPF March 2009
adjacent, and therefore can be far from synchronized. OSPF-MDR
requires that every hop of a route be fully adjacent or routable,
which ensures some degree of synchronization.
o OSPF-MPR does not provide differential Hellos.
OSPF-MDR is compared to another proposed MANET extension of OSPF
[OSPF-OR] in another document. Additional resources for OSPF-MDR,
including implementation code, simulation code, and slide
presentations, can be found at http://manet-routing.org.
2. Brief Overview of OSPF-MDR
OSPF-MDR [OSPF-MDR] is based on the selection of generalized
designated routers, called MANET designated routers (MDRs), which
form a connected dominating set (CDS). MDRs achieve scalability in
MANETs similar to the way DRs achieve scalability in broadcast
networks:
o MDRs have primary responsibility for flooding LSAs. Backup MDRs
provide backup flooding when MDRs temporarily fail.
o MDRs allow the number of adjacencies to be dramatically reduced,
by requiring adjacencies to be formed only between MDR/BMDR
routers and their neighbors.
Each router decides whether it is an MDR, BMDR, or neither based on
2-hop neighbor information obtained from modified Hello packets
received from neighbors. Optionally, differential Hellos can be
used, which reduce overhead by reporting only changes in neighbor
states.
In OSPF-MDR, the contents of router-LSAs is flexible. Either partial-
topology or full-topology LSAs can be used, either with or without
adjacency reduction. Partial-topology LSAs can be used to reduce the
size and origination frequency of LSAs while still providing
shortest-path routing. OSPF-MDR also allows the option of "minimal
LSAs", which minimizes overhead while providing nearly shortest-path
routing.
3. Brief Overview of OSPF-MPR
OSPF-MPR [OSPF-MPR] is based on multipoint relays (MPRs) and "path
MPRs". Path MPRs are similarly to MPRs except that link costs are
used in their selection. MPRs are used for flooding LSAs, and path
MPRs are used for constructing router-LSAs that provide shortest-path
routing. The router-LSA originated by each router must advertise all
neighbors that are either path MPRs or path MPR selectors.
In OSPF-MPR, each router must become adjacent with each MPR and MPR
Ogier Expires September 2009 [Page 4]
Internet-Draft MANET Extension of OSPF March 2009
selector. In addition, at least one "synch router" must be selected,
which must become adjacent with all of its MANET neighbors.
4. Qualitative Comparison
4.1. Adjacency Reduction
A major difference between OSPF-MDR and OSPF-MPR is that the latter
protocol, by requiring each router to form an adjacency with each MPR
and MPR selector, results in a much larger number of adjacencies and,
more importantly, a much larger number of new adjacency formations
per second. This is important because each adjacency formation
incurs a significant amount of overhead due to database exchange. The
simulation results presented below for 100 nodes indicate that the
rate of new adjacencies for OSPF-MPR is about 12 times that of OSPF-
MDR, resulting in about 11 times as much overhead from Database
Description (DD) packets.
In fact, the number of adjacency changes per node per second does not
increase with the number of nodes for OSPF-MDR, but increases
linearly with the number of nodes for OSPF-MPR.
4.2. Backup Relays
OSPF-MDR provides Backup MDRs, which perform backup flooding while
MDRs are being updated following topology changes, thus providing
robustness by allowing LSAs to be flooded with minimum delay even
when link failures occur.
In contrast, OSPF-MPR does not provide backup relays or backup
flooding; as a result, the flooding of LSAs can be delayed while MPRs
are being updated following topology changes. This is one possible
reason for the lower delivery ratio observed for OSPF-MPR in
simulations.
Although redundant MPRs can be selected, this would not provide
backup flooding but would provide redundant flooding and would result
in a larger number of adjacencies, resulting in substantially more
overhead.
4.3. MPR Flooding versus MDR/CDS Flooding
MPRs are source-dependent: each router selects its own MPRs, and the
set of relays that flood a given LSA depends on the origin of the
LSA. In contrast, MDRs are source-independent, similar to Designated
Routers.
Considered in isolation (independently of the rest of the protocol)
MPR flooding has some advantages over CDS flooding. The main
advantages are that MPR flooding always results in flooding over
Ogier Expires September 2009 [Page 5]
Internet-Draft MANET Extension of OSPF March 2009
minimum-hop paths, and on average MPR flooding requires fewer
transmissions to flood a given LSA.
However, MDRs are better suited for adjacency reduction, just as DRs
are well suited for minimizing the number of adjacencies in OSPF.
This is because adjacencies are source-independent, like MDRs. Since
MPRs are source-dependent, requiring each router to form an adjacency
with each neighbor that is an MPR or MPR selector results in a much
larger number of adjacencies, as shown in the simulation results.
Another difference is that MPRs are neighbor-selected while MDRs are
self-selected. As a result, MDRs recover faster from topology
changes, since MPR selection requires an additional step to inform
the neighbor that it has been selected as an MPR. This is another
possible reason for the lower delivery ratio observed for OSPF-MPR in
simulations.
When comparing the protocols, it is important to compare the whole
protocols, rather than compare techniques such as MPR versus MDR
flooding in isolation. That is why detailed simulations are more
useful than simplified analysis.
4.4. Router-LSAs
Both OSPF-MDR and OSPF-MPR provide partial-topology LSAs that provide
shortest-path routing, but they use different methods as discussed
below. However, OSPF-MDR is more flexible in that it provides two
LSA options that OSPF-MPR does not provide:
o OSPF-MDR provides the option of minimal LSAs, which allow
scalability to 200 nodes while providing routing along nearly
shortest paths. OSPF-MPR does not provide such an option.
o OSPF-MDR provides the option of full-topology LSAs with adjacency
reduction, which allows full-topology LSAs with reduced overhead.
OSPF-MDR does not provide this option, since it allows only
adjacent neighbors in LSAs.
In both OSPF-MPR and OSPF-MDR, each router advertises the link
metrics to all neighbors (unless all link metrics are 1) in Hellos,
which is necessary to provide shortest-path routing based on link
metrics. However, because the selection of path MPRs requires
knowledge of the link metric from 2-hop neighbors to 1-hop neighbors,
in OSPF-MPR each router must advertise (in Hellos) both the link
metrics *to* all neighbors and the link metrics *from* all neighbors,
resulting in more overhead.
OSPF-MPR provides partial-topology LSAs that provide shortest-path
routing by having each router advertise in its router-LSA all
neighbors that are either path MPRs or path MPR selectors. OSPF-MDR
achieves the same goal by having each router construct a min-cost
Ogier Expires September 2009 [Page 6]
Internet-Draft MANET Extension of OSPF March 2009
LSA, which advertises a set of neighbors sufficient to ensure that a
min-cost path exists from each neighbor to each other neighbor. For
the same reason that self-selected MDRs recover more quickly from
topology changes than neighbor-selected MPRs (as discussed above),
min-cost LSAs also recover more quickly than LSAs based on path MPRs,
as illustrated in the example below.
1
/ \
/ \
2 --- 3
\ /
\ /
4
All link costs are 1 in this example, so path MPRs are the same as
MPRs. In OSPF-MPR, assume nodes 1 and 4 select node 3 to be an MPR;
then node 3's LSA includes neighbors 1 and 4, and node 2's LSA is
empty. In OSPF-MDR, assume that node 3 is the only MDR and that node
3's LSA includes neighbors 1 and 4. Then node 2's LSA includes only
node 3 (since 2 must select 3 as parent and the parent is always
included in the LSA).
Suppose the link between nodes 1 and 3 fails, and that this is first
detected by node 1.
In OSPF-MDR, node 2 will learn of the failure via a Hello sent by
node 1, and will immediately add neighbors 1 and 4 to its LSA (to
provide a min-cost path between neighbors 1 and 4). The maximum
delay is 1 * HelloInterval.
In OSPF-MPR, node 1 will immediately select node 2 as an MPR and
advertise this selection in its next Hello, so node 2 will add
neighbor 1 to its LSA within 1 * HelloInterval. However, it will
take longer before node 2 adds neighbor 4 to its LSA. Node 4 must
first learn about the link failure, which can take 2 * HelloInterval
(since node 1 first detected the failure and node 4 is 2 hops from
node 1). Then node 4 selects node 2 as an MPR and advertises this
selection in its next Hello, so node 2 will add neighbor 4 to its LSA
within 3 * HelloInterval. (If node 2 first detected the link
failure, then the delay would be 2 * HelloInterval.)
Thus, although the min-cost LSAs of OSPF-MDR may be slightly larger
than LSAs based on path MPRs, they are also more robust since the
LSAs are updated more quickly following link failures.
4.5. Inclusion of Non-adjacent Neighbors in LSAs
In OSPF-MPR, only fully adjacent (synchronized) neighbors can be
advertised in LSAs. However, the first hop of a route is not
required to be an adjacent neighbor and can be far from synchronized.
Ogier Expires September 2009 [Page 7]
Internet-Draft MANET Extension of OSPF March 2009
In OSPF-MDR, only fully adjacent neighbors and routable neighbors can
be used as next hops or be advertised in LSAs. Thus, OSPF-MDR
requires that every hop of a route be fully adjacent or routable,
thus ensuring some degree of synchronization. (A neighbor being
routable implies that there exists, or recently existed, a path of
full adjacencies from the router to the neighbor.)
4.6. OSPF-MPR's Synch Router
In OSPF-MPR, the router with the largest Router ID is given an unfair
burden, since as a "synch router" it must form an adjacency with each
of its neighbors. This is true regardless of its router priority.
In contrast, OSPF-MDR uses router priority when selecting MDRs.
(Router priority can be changed dynamically so that the burden of
being an MDR can be shared among all routers.)
5. Simulation Results
This section presents simulation results that compare the performance
of OSPF-MDR and OSPF-MPR, using the GTNetS OSPFv3 MANET simulator.
The results for OSPF-MDR were obtained using the GTNetS simulator
with OSPF-MDR version 1.01, available at
http://hipserver.mct.phantomworks.org/ietf/ospf. The results for
OSPF-MPR were obtained using GTNetS code that was modified by INRIA
to implement OSPF-MPR. This code was announced on January 23, 2007
on the OSPF mailing list. Instructions for downloading this code and
running the simulations presented here are given in Appendix A.
The following scenario parameter values were used: radio range = 250
m and 200 m, grid length = 500 m, wireless alpha = 0.5, (maximum)
velocity = 10 m/s, pause time = 0, packet rate = 10 pkts/s, packet
size = 40 bytes, random seed = 8, start time (for gathering
statistics) = 1800 s. The stop time was 3600 s for up to 80 nodes
and 2700 s for more than 80 nodes. The source and destination are
selected randomly for each generated UDP packet. The simulated MAC
protocol is 802.11b.
The following protocol parameter values were used for both protocols:
HelloInterval = 2 s, DeadInterval = 6 s, RxmtInterval = 7 s,
MinLSInterval = 5 s, MinLSArrival = 1 s. AckInterval was 1 s for
OSPF-MDR and 500 msec for OSPF-MPR. (The results for OSPF-MPR do not
change significantly if 1 s is used for AckInterval.) Differential
hellos were used in OSPF-MDR. (OSPF-MPR does not support
differential Hellos.) All other parameters of OSPF-MDR were set to
their default values. Both protocols used the database exchange
optimization of [RFC5243].
The following three protocol configurations were compared: (1) OSPF-
MDR with uniconnected adjacencies and minimal LSAs, (2) OSPF-MDR with
uniconnected adjacencies and min-cost LSAs, and (3) OSPF-MPR with
Ogier Expires September 2009 [Page 8]
Internet-Draft MANET Extension of OSPF March 2009
adjacency reduction and MPR-based LSAs. As mentioned above, OSPF-MPR
does not provide an option for minimal LSAs (which provide suboptimal
routing with reduced overhead).
5.1. Results for Dense Networks
The results for the three configurations with range equal to 250 m
are shown in Tables 1, 2, and 3, respectively. The tables show the
results for total OSPF overhead in kb/s, the overhead for DD packets,
the average number of fully adjacent neighbors per node, the number
of changes in the set of fully adjacent neighbors per node per
second, the delivery ratio for UDP packets, and the average number of
hops traveled by UDP packets that reach their destination. (The code
for OSPF-MPR did not provide the number of hops.)
The results show that OSPF-MPR had a much lower delivery ratio than
OSPF-MDR, e.g., only 89.1% versus 96.8% for 40 nodes. Possible
reasons for this were mentioned in Section 4.
OSPF-MDR generated much less overhead than OSPF-MPR, especially in
large networks. For 100 nodes, OSPF-MPR's overhead is about 3 times
that of OSPF-MDR with min-cost LSAs, and 6.5 times that of OSPF-MDR
with minimal LSAs. OSPF-MDR with min-cost LSAs has less overhead
with 160 nodes than OSPF-MPR has with only 100 nodes.
Although OSPF-MPR does not provide minimal LSAs, the results show the
scalability advantage that OSPF-MDR can achieve using minimal LSAs.
For example, OSPF-MDR with minimal LSAs generated about the same
amount of overhead with 200 nodes as OSPF-MPR generated with only 80
nodes.
For 100 nodes, OSPF-MPR formed about 12 times as many adjacencies per
second as OSPF-MDR, resulting in about 11 times as much overhead from
DD packets. As discussed in Section 5.3, overhead from DD packets
can be very substantial if there is a large number of inter-area-
prefix-LSAs or AS-external-LSAs.
Number of nodes 40 80 120 160 200
----------------------------------------------------------------
OSPF overhead (kb/s) 41.65 132.88 246.31 418.96 637.45
DD overhead (kb/s) 8.12 34.48 64.53 120.70 210.33
Adjacencies/node 2.32 2.26 2.25 2.32 2.13
Adj changes/node/sec 0.036 0.040 0.032 0.035 0.039
Delivery ratio 0.968 0.953 0.962 0.956 0.951
Avg no. hops 1.387 1.412 1.407 1.430 1.411
Table 1. Results for OSPF-MDR with minimal LSAs for range 250 m.
Ogier Expires September 2009 [Page 9]
Internet-Draft MANET Extension of OSPF March 2009
Number of nodes 40 60 80 100 120 160
--------------------------------------------------------------------
OSPF overhead (kb/s) 74.17 175.31 248.55 354.60 479.17 795.73
DD overhead (kb/s) 8.14 23.50 35.00 42.66 76.01 121.42
Adjacencies/node 2.44 2.45 2.28 2.17 2.34 2.28
Adj changes/node/sec 0.037 0.047 0.040 0.029 0.037 0.035
Delivery ratio 0.968 0.954 0.958 0.957 0.956 0.953
Avg no. hops 1.348 1.389 1.368 1.411 1.361 1.386
Table 2. Results for OSPF-MDR with min-cost LSAs for range 250 m.
Number of nodes 40 60 80 100
---------------------------------------------------------------
OSPF Overhead (kbps) 121.16 346.42 627.84 1097.31
DD overhead (kbps) 29.64 121.00 239.79 463.87 (10.9 x MDR)
Adjacencies/node 16.60 23.55 29.40 33.45
Adj changes/node/sec 0.14 0.25 0.28 0.36 (12.4 x MDR)
Delivery ratio 0.891 0.875 0.882 0.876
Table 3. Results for OSPF-MPR for range 250 m.
5.2. Results for Sparser Networks
Tables 4 through 6 show the results for OSPF-MDR and OSPF-MPR with
the same configurations as above, but with the range equal to 200 m.
The trend is similar to the results for range 250 m. Again, OSPF-MDR
had a much better delivery ratio and generated much less overhead
than OSPF-MPR, especially in large networks.
For 100 nodes, OSPF-MPR's overhead is about 3 times that of OSPF-MDR
with min-cost LSAs, and about 6.7 times that of OSPF-MDR with minimal
LSAs (which OSPF-MPR does not provide).
OSPF-MDR with min-cost LSAs has less overhead with 160 nodes than
OSPF-MPR has with only 100 nodes. OSPF-MDR with minimal LSAs has
less overhead with 200 nodes than OSPF-MPR has with only 80 nodes.
For 100 nodes, OSPF-MPR formed 9.5 times as many adjacencies per
second as OSPF-MDR, resulting in 10.2 times as much overhead from DD
packets. As discussed in the next subsection, overhead from DD
packets can be very substantial if there is a large number of inter-
area-prefix-LSAs or AS-external-LSAs.
Ogier Expires September 2009 [Page 10]
Internet-Draft MANET Extension of OSPF March 2009
Number of nodes 40 80 120 160 200
----------------------------------------------------------------
OSPF overhead (kb/s) 63.62 195.24 346.86 573.22 824.56
DD overhead (kb/s) 15.81 60.20 112.90 202.58 316.00
Adjacencies/node 2.60 2.50 2.39 2.36 2.24
Adj changes/node/sec 0.069 0.068 0.055 0.058 0.057
Delivery ratio 0.927 0.907 0.907 0.904 0.902
Avg no. hops 1.714 1.743 1.727 1.758 1.747
Table 4. Results for OSPF-MDR with minimal LSAs for range 200 m.
Number of nodes 40 60 80 100 120 160
-------------------------------------------------------------------
OSPF overhead (kb/s) 123.45 286.40 415.69 597.50 788.87 1309.78
DD overhead (kb/s) 15.04 44.60 62.20 81.45 120.05 213.63
Adjacencies/node 2.53 2.72 2.58 2.32 2.37 2.41
Adj changes/node/sec 0.065 0.085 0.068 0.055 0.057 0.060
Delivery ratio 0.919 0.897 0.900 0.898 0.895 0.892
Avg no. hops 1.628 1.666 1.632 1.683 1.608 1.641
Table 5. Results for OSPF-MDR with min-cost LSAs for range 200 m.
Number of nodes 40 60 80 100
---------------------------------------------------------------
OSPF Overhead (kbps) 178.02 500.55 970.53 1762.71
DD overhead (kbps) 47.75 180.34 398.49 831.15 (10.2 x MDR)
Adjacencies/node 16.33 23.16 29.61 32.22
Adj changes/node/sec 0.21 0.34 0.42 0.52 (9.5 x MDR)
Delivery ratio 0.837 0.804 0.790 0.730
Table 6. Results for OSPF-MPR for range 200 m.
5.3. Effect of External LSAs
The above simulation results are for a single area, and they assume
there are no LSAs originating from outside the area, such as inter-
area-prefix-LSAs or AS-external LSAs. If such LSAs existed, they
would add to the database exchange overhead even if they are static
(never change). We can estimate this additional overhead, using the
results for the adjacency change rate when adjacency reduction is
used. First, since only half of the adjacency changes are adjacency
formations (the other half being adjacency eliminations), we must
divide the adjacency change rate by 2. Since the database exchange
optimization of [RFC5243] is used, each LSA is listed in a DD packet
by only one of the two neighbors forming the adjacency. Therefore,
we must again divide by 2. Since a separate inter-area-prefix-LSA is
required for each prefix, and each LSA header is 20 bytes, the amount
of additional overhead required for M such prefixes when there are N
Ogier Expires September 2009 [Page 11]
Internet-Draft MANET Extension of OSPF March 2009
nodes is
(M * N * adjacency change rate / 4) * 20 bytes/s
Applying this formula to the results in Tables 2 and 3 for 100 nodes,
the additional overhead for OSPF-MDR with min-cost LSAs is (M * 120 *
.029 / 4) * 20 = 17.4*M bytes/s, and the additional overhead for
OSPF-MPR is (M * 120 * .36 / 4) * 20 = 216*M bytes/s. For example,
if there are 1000 external prefixes, then the additional overhead for
OSPF-MDR is about 17,400 bytes/s or 139.2 kb/s, and the additional
overhead for OSPF-MPR is about 216,000 bytes/s or 1,728 kb/s. Thus,
OSPF-MDR is also much more scalable than OSPF-MPR with respect to the
number of external prefixes, because of its smaller adjacency change
rate.
6. Conclusions
OSPF-MDR is much more scalable than OSPF-MPR, achieving good
performance in mobile networks with 200 nodes using minimal LSAs, and
160 nodes using min-cost LSAs (which provide shortest-path routing).
OSPF-MDR with min-cost LSAs generated less overhead with 160 nodes
than OSPF-MPR generated with 100 nodes, using adjacency reduction.
OSPF-MDR also achieved a much better delivery ratio than OSPF-MPR,
and consistently performed better than OSPF-MPR in all scenarios
considered.
OSPF-MPR forms a much larger number of new adjacencies per second
than OSPF-MDR in large mobile networks when both protocols use
adjacency reduction. In a scenario with 100 nodes and range 250 m,
OSPF-MPR formed about 12 times as many adjacencies as OSPF-MDR,
resulting in about 11 times as much overhead from Database
Description (DD) packets. Overhead from DD packets can be very
substantial if there is a large number of inter-area-prefix-LSAs or
AS-external-LSAs. As a result, OSPF-MDR is also much more scalable
than OSPF-MPR with respect to the number of external prefixes.
OSPF-MDR is also more flexible than OSPF-MPR and has other
advantages, as summarized in Section 1. For example, OSPF-MDR
provides two LSA options that OSPF-MPR does not provide: minimal LSAs
(which allow greater scalability while providing routing along nearly
shortest paths) and full-topology LSAs with adjacency reduction
(which allow full-topology LSAs with reduced overhead). In addition,
OSPF-MPR puts an unfair burden on the router with the largest Router
ID, since as a "synch router" it must form an adjacency with each of
its neighbors.
Additional resources for OSPF-MDR, including high quality
implementation and simulation code, can be found at http://www.manet-
routing.org.
Ogier Expires September 2009 [Page 12]
Internet-Draft MANET Extension of OSPF March 2009
7. Security Considerations
This document does not raise any new security concerns.
8. IANA Considerations
This document has no actions for IANA.
9. Informative References
[OSPF-MDR] Ogier, R. and P. Spagnolo, "MANET Extension of OSPF using
CDS Flooding", draft-ietf-ospf-manet-mdr-05.txt (work in
progress), January 2009.
[OSPF-MPR] Baccelli, E., P. Jacquet, D. Nguyen, and T. Clausen, "OSPF
Multipoint Relay (MPR) Extension for Ad Hoc Networks", RFC 5449,
February 2009.
[OSPF-OR] Chandra, M. (ed.) and A. Roy (ed.), "Extensions to OSPF to
Support Mobile Ad Hoc Networking", draft-ietf-ospf-manet-
or-01.txt (work in progress), September 2008.
[RFC5243] Ogier, R., "OSPF Database Exchange Summary List
Optimization", RFC 5243, May 2008.
A. Instructions for Running Simulations
A.1. Running OSPF-MDR Simulations
The results for OSPF-MDR were obtained using the GTNetS simulator
with OSPF-MDR version 1.01, available at
http://hipserver.mct.phantomworks.org/ietf/ospf.
The command used for 40 nodes, radio range 250, min-cost LSAs, and
uniconnected adjacencies is as follows:
./random_waypoint_manet-opt seed=8 num_nodes=40 pktrate=10 \
velocity=10 pause_time=0 radio_range=250 alpha=0.5 \
HelloInterval=2 RxmtInterval=7 DeadInterval=6 AckInterval=1000 \
BackupWaitInterval=500 TwoHopRefresh=3 AdjConnectivity=1 \
LSAFullness=1 diff_hellos start_time=1800 stop_time=3600
For the different scenarios, num_nodes varied from from 40 to 200;
radio_range was 200 and 250; LSAFullness was 0 for minimal LSAs and 1
for min-cost LSAs; stop_time was set to 2700 when num_nodes was 100
or larger.
A.2. Running OSPF-MPR Simulations
The results for OSPF-MPR were obtained using GTNetS code that was
modified by INRIA to implement OSPF-MPR. This code was announced on
Ogier Expires September 2009 [Page 13]
Internet-Draft MANET Extension of OSPF March 2009
January 23, 2007 on the OSPF mailing list. A link for this code is
given in the slide presentation "Comparison of Three MANET Extensions
of OSPF", available at www.manet-routing.org.
The command used for 40 nodes, radio range 250, and adjacency
reduction is as follows:
./random_waypoint_manet-opt seed=8 num_nodes=40 pktrate=10 \
wireless_interface=2 wireless_flooding=1 TopoReduc alpha=0.5 \
velocity=10 pause_time=0 radio_range=250 HelloInterval=2 \
RxmtInterval=7 DeadInterval=6 PushbackInterval=3500 \
AckInterval=500 MinLSInterval=5 start_time=1800 stop_time=3600
For the different scenarios, num_nodes varied from from 40 to 100;
radio_range was 200 and 250; stop_time was set to 2700 when num_nodes
was 100 or larger.
Author's Address
Richard G. Ogier
Email: rich.ogier@earthlink.net
Ogier Expires September 2009 [Page 14]