OSPF Working Group R. Ogier
Internet-Draft SRI International
Intended status: Informational September 21, 2008
Expires: March 2009
Comparison of OSPF-MDR and OSPF-OR
draft-ogier-ospf-manet-mdr-or-comparison-00.txt
Status of this Memo
By submitting this Internet-Draft, each author represents that any
applicable patent or other IPR claims of which he or she is aware
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of 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) The IETF Trust (2008).
Abstract
This document presents a comparison of two proposed MANET extensions
of OSPF: OSPF-MDR and OSPF-OR. It includes a simulation comparison
and a qualitative comparison, which discusses the different design
choices and how they can affect performance and scalability.
Ogier Expires March 2009 [Page 1]
Internet-Draft MANET Extension of OSPF September 2008
Table of Contents
1 Introduction ................................................. 3
2 Brief Overview of OSPF-MDR ................................... 3
3 Brief Overview of OSPF-OR .................................... 4
4 Qualitative Comparison ....................................... 5
4.1 Adjacency Reduction .......................................... 5
4.2 Backup Relays ................................................ 6
4.3 OSPF-OR Requires a New Bit in the Router-LSA ................. 6
4.4 OSPF-OR Does Not Provide Scalable Shortest-Path Routing ...... 6
4.5 Using Hellos versus LSAs for 2-Hop Neighbor Information ...... 7
4.6 Fundamental Limitation of using MPRs with Smart Peering ...... 8
4.7 Complexity ................................................... 8
5 Simulation Results ........................................... 9
5.1 Comparison Using Partial-Topology LSAs ...................... 9
5.2 Effect of External LSAs ..................................... 13
5.3 Comparison Using Full-Topology LSAs and Adjacency Reduction . 13
5.4 Comparison Using Full-Topology LSAs Without Adjacency
Reduction ................................................... 15
6 Conclusions ................................................. 18
7 Security Considerations ..................................... 19
8 IANA Considerations ......................................... 19
9 Informative References ...................................... 19
A Instructions for Running Simulations ........................ 20
A.1 Running OSPF-MDR Simulations ................................ 20
A.2 Running OSPF-OR Simulations ................................. 20
Author's Address ............................................ 21
Intellectual Property and Copyright Statements .............. 22
Ogier Expires March 2009 [Page 2]
Internet-Draft MANET Extension of OSPF September 2008
1. Introduction
This document presents a comparison of two proposed MANET extensions
of OSPF: OSPF-MDR [OSPF-MDR] and OSPF-OR [OSPF-OR]. 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 OSPF-MDR provides an option for partial-topology LSAs that
provides routing along shortest (minimum-cost) paths, and is
scalable to at least 160 nodes. OSPF-OR does not provide such an
option, and therefore does not provide a scalable solution for
shortest-path routing.
o OSPF-OR requires a modification to the router-LSA packet format
when adjacency reduction is used, whereas OSPF-MDR does not.
o Simulations show that OSPF-OR 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
120 nodes, OSPF-OR forms 5.6 times as many adjacencies as
OSPF-MDR, resulting in 5.8 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-OR has a much larger number of backup relays (called non-
active ORs) than OSPF-MDR, which results in greater overhead
in large, dense networks due to redundant backup flooding.
o When both protocols use adjacency reduction and minimal LSAs
(which provide suboptimal routing), simulations show that OSPF-MDR
generates much less overhead and is much more scalable than
OSPF-OR, achieving good performance in mobile networks with up to
200 nodes. In dense, mobile networks, OSPF-MDR generates less
overhead with 200 nodes than OSPF-OR generates with 100 nodes.
o When both protocols use full-topology LSAs with adjacency
reduction, OSPF-MDR still generates significantly less overhead
than OSPF-OR with 40 or more nodes, even if OSPF-OR is modified
to omit backup flooding.
o When both protocols use full-topology LSAs without adjacency
reduction, OSPF-MDR performs about the same as OSPF-OR when
OSPF-OR is modified to omit backup flooding.
2. Brief Overview of OSPF-MDR
OSPF-MDR [OSPF-MDR] is based on the selection of generalized
Ogier Expires March 2009 [Page 3]
Internet-Draft MANET Extension of OSPF September 2008
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-OR
OSPF-OR [OSPF-OR] is based on overlapping relays (OR), which are used
to flood LSAs. An OR for a particular router is simply a neighbor
that has an adjacent neighbor. Each router selects a subset of its
ORs, called active ORs, using 2-hop neighbor information obtained
from router-LSAs originated by neighbors. Active ORs are selected to
cover all 2-hop neighbors in the adjacency graph, and are equivalent
to multipoint relays (MPRs). They are used for initial flooding of
LSAs, similar to OLSR [RFC3626] and OSPF-MPR [OSPF-MPR]. Any OR that
is not active (not an MPR) is called a non-active OR, and provides
backup flooding by flooding a received LSA after PushbackInterval
seconds if the LSA, or an ack for the LSA, has not been received by
all adjacent neighbors.
To allow scalability, OSPF-OR has an option called "smart peering",
which reduces the number of adjacencies [Roy06]. If smart peering is
used, the router does not form an adjacency with a neighbor if there
already exists a path of fully adjacent links from the router to the
neighbor. Router-LSAs can include both fully adjacent (synchronized)
neighbors and unsynchronized neighbors. If only synchronized
neighbors are advertised in router-LSAs, then routing is suboptimal.
Any unsynchronized neighbor that is advertised in the router-LSA must
be indicated by setting the U-bit, which is a previously unused bit
Ogier Expires March 2009 [Page 4]
Internet-Draft MANET Extension of OSPF September 2008
in the link description. The SPF calculation must be run twice, once
allowing only synchronized links (to determine which neighbors should
be adjacent, and once allowing all links (to compute routes).
OSPF-OR with smart peering (denoted OR/SP) allows some or all
unsynchronized neighbors to be advertised in the router-LSA.
However, it does not specify an algorithm to construct a partial-
topology LSA that provides shortest-path routing, unlike OSPF-MDR and
OSPF-MPR. (As discussed below, the methods of OSPF-MDR and OSPF-MPR
cannot be used in OSPF-OR to provide shortest-path routing without
changing packet formats or introducing a new LLS TLV.) Therefore,
only two LSA choices are specified in OSPF-OR: minimal LSAs that
advertise only synchronized neighbors, and full-topology LSAs that
advertise all bidirectional neighbors.
We note that the MPRs (active ORs) selected by OR/SP do not provide
flooding along min-hop paths, unlike OSPF-MPR, since they are
restricted to be adjacent neighbors, and must cover all 2-hop
neighbor in the adjacency graph, which is a subgraph of the full
topology graph.
Like OSPF-MDR, OSPF-OR also provides the option of using differential
Hellos, but uses a different method for constructing differential
Hellos. Unlike OSPF-MDR, OSPF-OR uses router-LSAs, not Hellos, to
obtain 2-hop neighbor information.
4. Qualitative Comparison
4.1. Adjacency Reduction
Even though OR/SP attempts to minimize the number of adjacencies that
are formed, it still results in a much larger number of adjacencies,
and a much larger number of adjacencies formations per second, than
OSPF-MDR in large, dense networks. The number of adjacencies is
important because, in both OR/SP and OSPF-MDR, all fully adjacent
neighbors must be advertised in partial-topology LSAs (when adjacency
reduction is used). The number of adjacency formations per second is
important because each adjacency formation incurs a significant
amount of overhead due to database exchange. This overhead is
proportional to the number of LSAs, and can be very substantial if
there is a large number of inter-area-prefix-LSAs or AS-external-
LSAs.
The simulation results presented below for 120 nodes show that the
rate of new adjacencies for OR/SP is 5.6 times that of OSPF-MDR,
resulting in 5.8 times as much overhead from Database Description
(DD) packets. The results for 120 nodes also show that the average
number of adjacencies for OR/SP is 4.6 times that of OSPF-MDR,
resulting in much larger LSA overhead when minimal LSAs are used. As
a result, OSPF-MDR generates less overhead with 200 nodes than OR/SP
Ogier Expires March 2009 [Page 5]
Internet-Draft MANET Extension of OSPF September 2008
generates with 100 nodes, showing that OSPF-MDR is much more
scalable.
4.2. Backup Relays
OSPF-MDR and OSPF-OR both provide backup relays, called Backup MDRs
and non-active ORs, respectively. These backup relays perform backup
flooding while MDRs or ORs are being updated following topology
changes, thus providing robustness by allowing LSAs to be flooded
with minimum delay even when link failures occur.
An important difference is that in OSPF-OR, the number of backup
relays can be very large in dense network, since each OR that is not
active (not an MPR) is a backup relay. Although non-active ORs use
random jitter to try to avoid having several non-active ORs flood the
same LSA, the number of such redundant floods becomes quite
significant in large, dense networks, contributing to the larger
overhead observed for OSPF-OR in the simulation results presented
below.
In OSPF-MDR, a minimum number of Backup MDRs are selected to provide
biconnected coverage, so that each router is a neighbor of at least
two (Backup) MDRs. Biconnected coverage provides sufficient
robustness while achieving scalability. Unlike the non-active ORs of
OSPF-OR, the number of Backup MDRs does not increase as the number of
neighbors (density) increases.
4.3. OSPF-OR Requires a New Bit in the Router-LSA
OSPF-OR requires a new bit, called the Unsynchronized bit (U-bit), in
the link description of the router-LSA. The U-bit must be set for
each advertised link corresponding to an unsynchronized neighbor. In
addition, a new LSA must be originated even if the only change to the
LSA is that an unsynchronized neighbor becomes synchronized (to
change the U-bit to zero).
This change to the router-LSA format does not appear to cause
significant problems. However, there might be a better use for the 8
unused bits of the link descriptor in the router-LSA of OSPFv3.
Therefore, a solution that avoids modifying the router-LSA, while
performing at least as well, would be preferable. OSPF-MDR is such a
solution.
4.4. OSPF-OR Does Not Provide Scalable Shortest-Path Routing
As mentioned above, OSPF-OR specifies only two choices for router-
LSAs when smart peering is used: minimal LSAs that advertise only
fully adjacent (synchronized) neighbors, and full-topology LSAs that
advertise all bidirectional neighbors.
In order to provide a scalable solution for shortest-path routing, it
Ogier Expires March 2009 [Page 6]
Internet-Draft MANET Extension of OSPF September 2008
is necessary to provide a choice for partial-topology LSAs that
provide routing along shortest (minimum-cost) paths. OSPF-MDR
achieves this goal with its min-cost LSAs, which perform well in
mobile networks with up to 160 nodes (see the simulation results
below). Although OSPF-OR can be modified to use min-cost LSAs, this
would require a packet format change or a new LLS TLV. It would also
require a change to the SPF calculation to remove the requirement
that the first link on a path be in the router's Router-LSA, and that
the reverse of such a link be in the neighbor's Router-LSA.
OSPF-MPR also provides partial-topology LSAs based on "path MPRs",
which provide routing along shortest paths. However, the MPRs
selected by OSPF-OR do not provide shortest paths when smart peering
is used, since they are confined to the adjacency subgraph. OSPF-OR
can also be modified to use partial-topology LSAs based on path MPRs,
but this would also require a packet format change or a new LLS TLV
to indicate path MPRs, and a change to the SPF calculation as
mentioned above.
In addition, OSPF-MDR allows partial-topology LSAs to be used with
full-topology adjacencies. OSPF-OR does not allow this, since it
requires each router to advertise all fully adjacent neighbors in its
router-LSA.
4.5. Using Hellos versus LSAs for 2-Hop Neighbor Information
OSPF-MDR selects MDRs using information about each neighbor's
neighbors obtained from modified Hello packets received from each
neighbor. In contrast, OSPF-OR selects MPRs using similar
information obtained from the router-LSA originated by each neighbor.
If OSPF-OR uses smart peering (OR/SP), then such information is not
full 2-hop information, but is restricted to 2-hop neighbors on the
reduced adjacency graph, and MPRs are restricted to the reduced
adjacency graph. (Section 4.6 discusses a fundamental limitation of
selecting MPRs that are restricted to a reduced adjacency graph).
An important advantage of using Hellos to obtain 2-hop neighbor
information is that they provide *full* 2-hop neighbor information
even when partial-topology LSAs are used. Such information is
required for the construction of partial-topology router-LSAs that
provide shortest-path routing, as OSPF-MDR provides with its min-cost
LSAs.
Another possible advantage of using Hellos to obtain 2-hop neighbor
information is that Hellos are much smaller than full-topology LSAs,
especially if differential Hellos are used. Although it is
reasonable to send differential Hellos every 1 or 2 seconds, sending
full-topology LSAs that often would generate an excessive amount of
overhead in a dense, mobile network. Therefore, it is reasonable to
use 5 seconds for MinLSInterval as specified in RFC 2328, resulting
in a possible 5 second delay to update MPRs when a topology change
Ogier Expires March 2009 [Page 7]
Internet-Draft MANET Extension of OSPF September 2008
occurs.
4.6. Fundamental Limitation of using MPRs with Smart Peering
If OSPF-OR with smart peering succeeded in selecting the minimum
number of adjacencies, which would form a tree with n-1 links, then
every adjacent neighbor that is not a leaf of the adjacency tree
would have to be an MPR (since it provides the only 2-hop path to
some 2-hop neighbor on the tree). Unless the adjacency tree has a
large number of leaves and very few interior nodes (which is the case
with OSPF-MDR, since each interior node is an MDR), this will result
in a large number of transmissions to flood each LSA. However, smart
peering results in far more than the minimum number of adjacencies
(as shown in the simulation results), which therefore avoids the
above problem at the expense of additional overhead resulting from
having to form a larger number of adjacencies. The MDR/CDS approach
avoids this tradeoff by minimizing the number of interior nodes
(MDRs) as well as selecting nearly the minimum number of adjacencies.
This explains why OSPF-MDR can scale to 200 nodes, unlike OSPF-OR,
which generates more overhead with 100 nodes than OSPF-MDR generates
with 200 nodes (as shown in the simulation results).
The above limitation is illustrated by a 50-node example in the slide
presentation "Comparison of Three MANET Extensions of OSPF",
available at http://www.manet-routing.org.
4.7. Complexity
The OSPF-MDR draft is significantly longer than the OSPF-OR draft,
but the additional length is justified because it provides more
features, more options, and better performance/scalability, as
discussed in this section.
The calculation of relays (MDRs or MPRs) has about the same
complexity in both drafts, with both algorithms requiring O(d^2) time
where d is the number of neighbors.
As discussed above, OSPF-OR considers any non-active OR to be a
backup relay, which does not require additional computation.
However, this results in a large number of backup relays, which
increases overhead and limits scalability as discussed above. OSPF-
MDR can similarly consider any non-MDR to be a backup relay, but
provides the option of selecting Backup MDRs more intelligently, to
provide biconnected coverage while achieving scalability. The
algorithm for selecting Backup MDRs also runs in O(d^2), and an
optional, simplified version of the algorithm is also specified.
OSPF-MDR provides the option of biconnected adjacencies, which may
improve robustness in some scenarios. OSPF-OR does not specify an
algorithm for biconnected adjacencies.
Ogier Expires March 2009 [Page 8]
Internet-Draft MANET Extension of OSPF September 2008
OSPF-OR with smart peering requires that two different SPF
calculations be performed: one allowing only synchronized links and
one allowing both synchronized and unsynchronized links. OSPF-MDR
does not distinguish between synchronized and unsynchronized links in
the SPF calculation.
As mentioned above, OSPF-MDR provides partial-topology LSAs that
provide routing along shortest paths, which OSPF-OR does not provide.
Thus, OSPF-OR does not provide a scalable solution for shortest-path
routing, which is a very important capability. In addition, OSPF-MDR
allows partial-topology LSAs to be used with full-topology
adjacencies, unlike OSPF-OR.
5. Simulation Results
This section presents simulation results that compare the performance
of OSPF-MDR and OSPF-OR, 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-OR were obtained using the same GTNetS code used for the
MILCOM'06 paper [MILCOM06] by Spagnolo and Henderson, modified to use
the database exchange optimization of [RFC5243] (since OSPF-MDR uses
this optimization). Instructions for downloading this code and
running the simulations presented here are given in Appendix A. (The
OSPF-MDR code used for the MILCOM'06 paper is not compliant with the
current version of the OSPF-MDR draft, and contains some bugs that
have been fixed in version 1.01.)
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 = 1 s.
Differential hellos were used in both protocols. For OSPF-OR,
PushbackInterval was set to 3 s, since the draft specifies that it
must be less than 1/2 RxmtInterval. All other parameters of OSPF-MDR
were set to their default values.
5.1. Comparison Using Partial-Topology LSAs
The first set of experiments focused on scalability, and thus used
partial-topology LSAs and adjacency reduction. The following three
Ogier Expires March 2009 [Page 9]
Internet-Draft MANET Extension of OSPF September 2008
protocol configurations were compared: (1) OSPF-MDR with uniconnected
adjacencies and minimal LSAs, (2) OSPF-OR with smart peering (OR/SP)
and minimal LSAs, and (3) OSPF-MDR with uniconnected adjacencies and
min-cost LSAs. As mentioned above, OSPF-OR does not provide an
option for partial-topology LSAs that provides shortest-path routing.
5.1.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.
OSPF-MDR generated much less overhead than OR/SP, especially in large
networks. For 120 nodes, OR/SP generated about 6.5 times as much
overhead as OSPF-MDR. OSPF-MDR generated less overhead for 200 nodes
than OR/SP generated for 100 nodes.
For 120 nodes, OR/SP formed 5.6 times as many adjacencies per second
as OSPF-MDR, resulting in 5.8 times as much overhead from DD packets.
As shown in Section 5.2, overhead from DD packets can be very
substantial if there is a large number of inter-area-prefix-LSAs or
AS-external-LSAs.
The delivery ratio is significantly larger for OSPF-MDR, especially
in larger networks (.960 versus .941 for 100 nodes, and .962 versus
.935 for 120 nodes). The average number of hops is larger for OR/SP
because, unlike OSPF-MDR, it does not allow a neighbor to be a next
hop unless it is advertised in the router-LSA. (The specification
for OR/SP can be modified to allow this, but this is an indication
that OR/SP is not yet stable.)
Differential Hellos were used in both protocols, and OSPF-MDR was
found to generate about half as much overhead from Hello packets as
OR/SP in large networks, indicating that the differential Hello
method of OSPF-MDR is more efficient.
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 March 2009 [Page 10]
Internet-Draft MANET Extension of OSPF September 2008
Number of nodes 40 60 80 100 120
---------------------------------------------------------------
OSPF Overhead (kb/s) 90.09 238.12 521.90 916.83 1615.57
DD overhead (kb/s) 12.92 41.75 98.69 183.51 376.82
Adjacencies/node 6.81 7.31 9.17 10.04 10.42
Adj changes/node/sec 0.06 0.09 0.11 0.14 0.18
Delivery ratio 0.961 0.945 0.940 0.941 0.935
Avg no. hops 2.282 2.361 2.358 2.386 2.452
Table 2. Results for OR/SP with minimal LSAs for range 250 m.
As shown in Table 3, OSPF-MDR with min-cost LSAs still generated much
less overhead than OR/SP with minimal LSAs. In fact, OSPF-MDR with
min-cost LSAs generated less overhead for 160 nodes than OR/SP with
minimal LSAs generated for 100 nodes.
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 3. Results for OSPF-MDR with min-cost LSAs for range 250 m.
Backup flooding generates a substantial amount of additional overhead
in OR/SP. Table 4 shows the results for OR/SP if it were modified to
omit backup flooding. (Backup flooding is required in the
specification.) With this modification, OR/SP still generated about
4.3 times as much overhead as OSPF-MDR with 120 nodes; and OSPF-MDR
generated much less overhead with 200 nodes than OR/SP generated with
120 nodes (when both protocols use minimal LSAs).
Number of nodes 40 60 80 100 120
-----------------------------------------------------------------
OSPF Overhead (kb/s) 74.58 191.13 357.62 617.45 1049.29
Delivery ratio 0.962 0.942 0.942 0.935 0.935
Avg no. hops 2.236 2.341 2.360 2.462 2.393
Table 4. Results for OR/SP with minimal LSAs, modified to omit
backup flooding, for range 250 m.
5.1.2. Results for Sparser Networks
Tables 5 through 8 show the results for OSPF-MDR and OR/SP 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
generated much less overhead than OR/SP, especially in large
networks. For 120 nodes, OR/SP generated about 6.4 times as much
Ogier Expires March 2009 [Page 11]
Internet-Draft MANET Extension of OSPF September 2008
overhead as OSPF-MDR. OSPF-MDR generated less overhead with 200
nodes than OR/SP generated with 100 nodes.
As shown in Table 7, OSPF-MDR with min-cost LSAs still generated much
less overhead than OR/SP with minimal LSAs.
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 5. Results for OSPF-MDR with minimal LSAs for range 200 m.
Number of nodes 40 60 80 100 120
---------------------------------------------------------------
OSPF Overhead (kb/s) 124.17 340.41 674.56 1138.24 2230.07
DD overhead (kb/s) 22.93 74.70 153.28 284.64 657.07
Adjacencies/node 5.25 6.22 7.36 7.69 8.56
Adj changes/node/sec 0.10 0.15 0.17 0.19 0.28
Delivery ratio 0.908 0.865 0.875 0.872 0.870
Avg no. hops 2.863 2.799 2.753 2.843 2.827
Table 6. Results for OR/SP 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 7. Results for OSPF-MDR with min-cost LSAs for range 200 m.
Table 8 shows the results for OR/SP if it were modified to omit
backup flooding. Even with this modification, OR/SP still generates
much more overhead with 120 nodes than OSPF-MDR generates with 200
nodes (when both protocols use minimal LSAs).
Ogier Expires March 2009 [Page 12]
Internet-Draft MANET Extension of OSPF September 2008
Number of nodes 40 60 80 100 120
-----------------------------------------------------------------
OSPF Overhead (kb/s) 104.68 258.88 480.48 811.72 1379.50
Delivery ratio 0.892 0.870 0.881 0.874 0.872
Avg no. hops 2.730 2.747 2.760 2.860 2.769
Table 8. Results for OR/SP with minimal LSAs, modified to omit
backup flooding, for range 200 m.
5.2. 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
nodes is
(M * N * adjacency change rate / 4) * 20 bytes/s
Applying this formula to the results in Tables 1 and 2 for 120 nodes,
the additional overhead for OSPF-MDR with min-cost LSAs is (M * 120 *
.032 / 4) * 20 = 19.2*M bytes/s, and the additional overhead for
OSPF-OR is (M * 120 * .18 / 4) * 20 = 108*M bytes/s. For example, if
there are 1000 external prefixes, then the additional overhead for
OSPF-MDR is about 19,200 bytes/s or 153.6 kb/s, and the additional
overhead for OSPF-OR is about 108,000 bytes/s or 864 kb/s. Thus,
OSPF-MDR is also much more scalable than OSPF-OR with respect to the
number of external prefixes, because of its smaller adjacency change
rate.
5.3. Comparison Using Full-Topology LSAs and Adjacency Reduction
5.3.1. Results for Dense Networks
Tables 9 and 10 show the results for OSPF-MDR and OR/SP with the same
configurations as above except that both protocols use full-topology
LSAs. For 80 nodes, OR/SP generated almost twice as much overhead as
OSPF-MDR.
Table 11 shows the results for OR/SP if it were modified to omit
backup flooding. Even without backup flooding, OR/SP generated 42%
Ogier Expires March 2009 [Page 13]
Internet-Draft MANET Extension of OSPF September 2008
more overhead than OSPF-MDR for 80 nodes.
The average number of hops is about 3% larger for OSPF-MDR because
the implementation imposes an optional stricter condition on a new
neighbor before its state can change from Down to Init or greater, as
specified in Section 4.3 of [OSPF-MDR]. This condition requires two
consecutive Hellos to be received from a new neighbor. When this
stricter condition is removed, the average number of hops for OSPF-
MDR is within 1% of that for OR/SP.
Number of nodes 20 40 60 80
--------------------------------------------------------
OSPF overhead (kb/s) 37.76 162.17 447.00 889.97
DD overhead (kb/s) 2.07 3.39 24.63 35.46
Adjacencies/node 2.42 2.38 2.45 2.31
Adj changes/node/sec 0.032 0.037 0.050 0.040
Delivery ratio 0.968 0.962 0.952 0.953
Avg no. hops 1.427 1.337 1.379 1.362
Table 9. Results for OSPF-MDR with full LSAs for range 250 m.
Number of nodes 20 40 60 80
--------------------------------------------------------
OSPF overhead (kb/s) 52.88 308.24 843.46 1762.99
DD overhead (kb/s) 2.63 14.34 47.20 111.01
Adjacencies/node 4.23 6.83 7.22 8.58
Adj changes/node/sec 0.04 0.07 0.10 0.12
Delivery ratio 0.962 0.960 0.947 0.945
Avg no. hops 1.380 1.300 1.339 1.321
Table 10. Results for OR/SP with full LSAs for range 250 m.
Number of nodes 20 40 60 80
--------------------------------------------------------
OSPF overhead (kb/s) 41.19 240.53 621.49 1268.07
Delivery ratio 0.960 0.961 0.948 0.949
Avg no. hops 1.380 1.302 1.338 1.323
Table 11. Results for OR/SP with full LSAs, modified to omit
backup flooding, for range 250 m.
5.3.2. Results for Sparser Networks
Tables 12 and 13 show the results for OSPF-MDR and OR/SP with the
same configurations as above (using full-topology LSAs), but with the
range equal to 200 m. For 80 nodes, OR/SP generated 92% more
overhead than OSPF-MDR. In addition, the delivery ratio is about 2%
higher for OSPF-MDR than for OR/SP.
Ogier Expires March 2009 [Page 14]
Internet-Draft MANET Extension of OSPF September 2008
Again, the average number of hops is slightly larger for OSPF-MDR
because the implementation imposes an optional stricter condition on
a new neighbor before its state can change from Down to Init or
greater.
Table 14 shows the results for OR/SP if it were modified to omit
backup flooding. Even without backup flooding, OR/SP generated about
30% more overhead than OSPF-MDR for 80 nodes.
Number of nodes 20 40 60 80
--------------------------------------------------------
OSPF overhead (kb/s) 45.39 200.55 542.98 1013.44
DD overhead (kb/s) 4.82 15.45 42.24 64.05
Adjacencies/node 2.76 2.60 2.74 2.53
Adj changes/node/sec 0.069 0.066 0.081 0.071
Delivery ratio 0.924 0.919 0.904 0.897
Avg no. hops 1.779 1.611 1.656 1.616
Table 12. Results for OSPF-MDR with full LSAs for range 200 m.
Number of nodes 20 40 60 80
--------------------------------------------------------
OSPF overhead (kb/s) 59.66 341.25 920.92 1945.31
DD overhead (kb/s) 4.59 23.94 76.85 178.59
Adjacencies/node 3.81 5.47 6.34 7.24
Adj changes/node/sec 0.07 0.11 0.14 0.18
Delivery ratio 0.905 0.907 0.876 0.874
Avg no. hops 1.666 1.518 1.552 1.522
Table 13. Results for OR/SP with full LSAs for range 200 m.
Number of nodes 20 40 60 80
--------------------------------------------------------
OSPF overhead (kb/s) 42.86 241.16 647.75 1311.61
Delivery ratio 0.910 0.901 0.881 0.877
Avg no. hops 1.682 1.515 1.555 1.525
Table 14. Results for OR/SP with full LSAs, modified to omit
backup flooding, for range 200 m.
5.4. Comparison Using Full-Topology LSAs Without Adjacency Reduction
Although OSPF-MDR allows the option of using full-topology
adjacencies (i.e., not using adjacency reduction), this option is not
recommended, especially in dense networks, because it generates a
large amount of unnecessary overhead by forming a large number of
unnecessary adjacencies. (For the same reason, OSPF does not form
adjacencies between all pairs of routers attached to a broadcast
network.) However, some users may decide not to use adjacency
Ogier Expires March 2009 [Page 15]
Internet-Draft MANET Extension of OSPF September 2008
reduction in sparse networks. Therefore, results for full-topology
adjacencies are presented with the range equal to 200 m and 150 m.
In this set of experiments, OSPF-MDR did not impose the optional
stricter condition that requires two consecutive Hellos to be
received from a new neighbor before its state can change to Init or
greater. This allows the average number of hops traveled by UDP
packets to be compared on a fair basis. (Instructions for modifying
the code to omit this stricter condition are given in the appendix.)
In addition to overhead, delivery ratio, and average number of hops
traveled by UDP packets, the results also include the average end-to-
end delay for UDP packets and the average number of LSAs requested by
a router during database exchange. The latter measure indicates how
well routers maintain synchronized databases.
5.4.1. Results for Radio Range 200 m
Tables 15 through 17 show the results for full-topology LSAs and no
adjacency reduction, for range 200 m. Table 15 shows the results for
OSPF-MDR, and Tables 16 and 17 show the results for OSPF-OR with and
without backup flooding, respectively. The performance of OSPF-MDR
is close to that of OSPF-OR without backup flooding. However, OSPF-
OR with backup flooding generates significantly more overhead than
OSPF-MDR. For 60 nodes, OSPF-OR with backup flooding generates about
70% more overhead than OSPF-MDR, and has a significantly larger
average end-to-end delay for UDP packets due to congestion.
The average number of LSAs requested by a router during database
synchronization is significantly larger for OSPF-OR than for OSPF-
MDR, showing that OSPF-MDR does a better job of maintaining
synchronized databases. As shown in Table 17, the average number of
requested LSAs becomes even larger for OSPF-OR when backup flooding
is not used.
Number of nodes 20 40 60
----------------------------------------------
OSPF overhead (kb/s) 68.35 400.58 1282.05
Delivery ratio 0.924 0.920 0.900
Avg no. hops 1.778 1.608 1.695
Avg delay (msec) 13.41 16.94 46.78
Avg # LSAs requested 0.61 0.51 0.59
Table 15. Results for OSPF-MDR with full LSAs and no adjacency
reduction, for range 200 m.
Ogier Expires March 2009 [Page 16]
Internet-Draft MANET Extension of OSPF September 2008
Number of nodes 20 40 60
-----------------------------------------------
OSPF overhead (kb/s) 84.58 593.01 2188.44
Delivery ratio 0.927 0.920 0.900
Avg no. hops 1.795 1.619 1.738
Avg delay (msec) 13.36 17.09 65.49
Avg # LSAs requested 0.83 0.73 0.74
Table 16. Results for OSPF-OR with full LSAs and no adjacency
reduction, for range 200 m.
Number of nodes 20 40 60
-----------------------------------------------
OSPF overhead (kb/s) 65.87 405.50 1323.53
Delivery ratio 0.925 0.924 0.903
Avg no. hops 1.794 1.619 1.718
Avg delay (msec) 13.09 16.64 50.69
Avg # LSAs requested 1.12 0.93 0.88
Table 17. Results for OSPF-OR with full LSAs and no adjacency
reduction, modified to omit backup flooding, for range 200.
5.4.2. Results for Radio Range 150 m
Tables 18 through 20 show the results for full-topology LSAs and no
adjacency reduction, for range 150 m. Again, the performance of
OSPF-MDR is close to that of OSPF-OR without backup flooding, and
OSPF-OR with backup flooding generates significantly more overhead
than OSPF-MDR.
Number of nodes 20 40 60
----------------------------------------------
OSPF overhead (kb/s) 52.29 350.72 1020.73
Delivery ratio 0.772 0.834 0.802
Avg no. hops 2.365 2.024 2.090
Avg delay (msec) 19.25 19.91 34.09
Avg # LSAs requested 1.06 0.581 0.54
Table 18. Results for OSPF-MDR with full LSAs and no adjacency
reduction, for range 150 m.
Ogier Expires March 2009 [Page 17]
Internet-Draft MANET Extension of OSPF September 2008
Number of nodes 20 40 60
-----------------------------------------------
OSPF overhead (kb/s) 61.34 479.43 1513.51
Delivery ratio 0.752 0.838 0.799
Avg no. hops 2.354 2.046 2.102
Avg delay (msec) 17.70 20.04 35.40
Avg # LSAs requested 1.56 0.81 0.68
Table 19. Results for OSPF-OR with full LSAs and no adjacency
reduction, for range 150 m.
Number of nodes 20 40 60
-----------------------------------------------
OSPF overhead (kb/s) 51.30 352.85 1039.89
Delivery ratio 0.755 0.840 0.808
Avg no. hops 2.355 2.044 2.107
Avg delay (msec) 18.02 19.12 31.73
Avg # LSAs requested 1.89 1.06 0.81
Table 20. Results for OSPF-OR with full LSAs and no adjacency
reduction, modified to omit backup flooding, for range 150.
6. Conclusions
OSPF-MDR is much more scalable than OSPF-OR, 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-OR does not provide partial-topology LSAs that provide shortest-
path routing. When both protocols use minimal LSAs, OSPF-OR
generates more overhead with 100 nodes than OSPF-MDR generates with
200 nodes. If OSPF-OR is modified to omit backup flooding, it still
generates much more overhead with 120 nodes than OSPF-MDR generates
with 200 nodes.
When both protocols use full-topology LSAs with adjacency reduction,
OSPF-OR still generates significantly more overhead than OSPF-MDR
with 40 or more nodes, even if OSPF-OR is modified to omit backup
flooding.
When both protocols use full-topology LSAs and full-topology
adjacencies (no adjacency reduction), OSPF-OR generates about the
same amount of overhead as OSPF-MDR when backup flooding is omitted,
but generates significantly more overhead than OSPF-MDR with 40 or
more nodes when backup flooding is used.
OSPF-OR did not perform significantly better than OSPF-MDR in any of
the scenarios considered.
OSPF-MDR is also much more scalable than OSPF-OR with respect to the
Ogier Expires March 2009 [Page 18]
Internet-Draft MANET Extension of OSPF September 2008
number of external prefixes, because it forms a much smaller number
of new adjacencies per second. (For 120 nodes, OSPF-OR with smart
peering forms about 5.6 times as many new adjacencies as OSPF-MDR.)
Such prefixes add to the database exchange overhead even if they are
static (never change).
We tested one implementation of OSPF-OR, using parameters that are
the same as for OSPF-MDR when possible, and that are compliant with
the OSPF-OR draft. It may be possible to improve the performance of
OSPF-OR by modifying the code, but the best available code was used
that is compliant with the draft. One such modification was tested
by omitting backup flooding to reduce overhead, but the resulting
overhead was still significantly larger than for OSPF-MDR except in
small networks and when both protocols use full-topology LSAs without
adjacency reduction.
Even if performance can be improved to be close to that of OSPF-MDR,
OSPF-OR does not provide a scalable solution for shortest-path
routing (using partial-topology LSAs), and modifying OSPF-OR to
provide this important capability would require major changes to the
specification.
Although the OSPF-MDR draft is significantly longer than the OSPF-OR
draft, the additional length is justified because it provides more
options and capabilities, in addition to achieving better performance
and scalability.
Additional information and resources for OSPF-MDR can be found at
http://www.manet-routing.org.
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
[MILCOM06] Spagnolo, P.A. and T.R. Henderson, "Comparison of Proposed
OSPF MANET Extensions", Proc. IEEE MILCOM 2006, October 2006.
[OSPF-MDR] Ogier, R. and P. Spagnolo, "MANET Extension of OSPF using
CDS Flooding", draft-ietf-ospf-manet-mdr-02.txt (work in
progress), June 2008.
[OSPF-MPR] Baccelli, E., P. Jacquet, D. Nguyen, and T. Clausen, "OSPF
MPR Extension for Ad Hoc Networks", draft-ietf-ospf-manet-
mpr-01.txt (work in progress), July 2008.
Ogier Expires March 2009 [Page 19]
Internet-Draft MANET Extension of OSPF September 2008
[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.
[RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State
Routing Protocol", RFC 3626, October 2003.
[RFC5243] Ogier, R., "OSPF Database Exchange Summary List
Optimization", RFC 5243, May 2008.
[Roy06] Roy, A. (ed.), "Adjacency Reduction in OSPF using SPT
Reachability", draft-roy-ospf-smart-peering-01.txt (work in
progress), November 2005.
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 20 nodes, radio range 250, min-cost LSAs, and
uniconnected adjacencies is as follows:
./random_waypoint_manet-opt seed=8 num_nodes=20 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 20 to 200;
radio_range was 150, 200, and 250; LSAFullness was 0 for minimal
LSAs, 1 for min-cost LSAs, and 4 for full LSAs; AdjConnectivity was 1
for uniconnected adjacencies and 0 for full-topology adjacencies;
stop_time was set to 2700 when num_nodes was 100 or larger.
A.2. Running OSPF-OR Simulations
The results for OSPF-OR were obtained using the GTNetS code that was
used for the paper [MILCOM06]. 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 OSPF-MDR code contained in
this code is not compliant with the current version of the OSPF-MDR
draft and contains some bugs.)
To activate the database exchange optimization of RFC 5243, uncomment
the following line in Makefile in the gtnets-milcom06 directory:
CFLAGS += -DOSPF6_MANET_MDR_FLOOD_DD
Ogier Expires March 2009 [Page 20]
Internet-Draft MANET Extension of OSPF September 2008
The command used for 40 nodes, radio range 250, using smart peering
and minimal LSAs, is as follows:
./random_waypoint_manet-opt seed=8 num_nodes=40 pktrate=10 \
wireless_interface=2 wireless_flooding=1 velocity=10 pause_time=0 \
radio_range=250 alpha=0.5 HelloInterval=2 RxmtInterval=7 \
DeadInterval=6 PushbackInterval=3000 AckInterval=1000 \
MinLSInterval=5 SmartPeering diff_hellos \
start_time=1800 stop_time=3600
For the different scenarios, num_nodes varied from from 20 to 120;
radio_range was 150, 200, and 250; stop_time was set to 2700 when
num_nodes was 100 or larger. To use full-topology LSAs (including
unsynchronized neighbors) with smart peering, the argument
"UnsynchAdj" is added. To use full-topology adjacencies, the
arguments "SmartPeering" and "UnsynchAdj" are both omitted.
For the scenarios in which backup flooding was omitted, the code was
modified by commenting out the following line in the function
ospf6_flood_interface_mpr() in the file ospf6_flood.c (and
recompiling):
ospf6_pushback_lsa_add(lsa, on);
Author's Address
Richard G. Ogier
Email: rich.ogier@earthlink.net
Ogier Expires March 2009 [Page 21]
Internet-Draft MANET Extension of OSPF September 2008
Intellectual Property Statement
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at ietf-
ipr@ietf.org.
Disclaimer of Validity
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Copyright Statement
Copyright (C) The IETF Trust (2008). This document is subject to the
rights, licenses and restrictions contained in BCP 78, and except as
set forth therein, the authors retain all their rights.
Acknowledgment
Funding for the RFC Editor function is currently provided by the
Internet Society.
Ogier Expires March 2009 [Page 22]