[Docs] [txt|pdf] [Tracker] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04

OSPF Working Group                                            R. Ogier
Internet-Draft                                       SRI International
Intended status: Informational                           March 8, 2009
Expires: September 2009

                   Comparison of OSPF-MDR and OSPF-OR
            draft-ogier-ospf-manet-mdr-or-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-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 September 2009                 [Page 1]


Internet-Draft           MANET Extension of OSPF              March 2009


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



























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-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 September 2009                 [Page 3]


Internet-Draft           MANET Extension of OSPF              March 2009


   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 September 2009                 [Page 4]


Internet-Draft           MANET Extension of OSPF              March 2009


   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 September 2009                 [Page 5]


Internet-Draft           MANET Extension of OSPF              March 2009


   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 September 2009                 [Page 6]


Internet-Draft           MANET Extension of OSPF              March 2009


   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 September 2009                 [Page 7]


Internet-Draft           MANET Extension of OSPF              March 2009


   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 September 2009                 [Page 8]


Internet-Draft           MANET Extension of OSPF              March 2009


   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 September 2009                 [Page 9]


Internet-Draft           MANET Extension of OSPF              March 2009


   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 September 2009                [Page 10]


Internet-Draft           MANET Extension of OSPF              March 2009


   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 September 2009                [Page 11]


Internet-Draft           MANET Extension of OSPF              March 2009


   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 September 2009                [Page 12]


Internet-Draft           MANET Extension of OSPF              March 2009


   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 September 2009                [Page 13]


Internet-Draft           MANET Extension of OSPF              March 2009


   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 September 2009                [Page 14]


Internet-Draft           MANET Extension of OSPF              March 2009


   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 September 2009                [Page 15]


Internet-Draft           MANET Extension of OSPF              March 2009


   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 September 2009                [Page 16]


Internet-Draft           MANET Extension of OSPF              March 2009


   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 September 2009                [Page 17]


Internet-Draft           MANET Extension of OSPF              March 2009


   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 September 2009                [Page 18]


Internet-Draft           MANET Extension of OSPF              March 2009


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



Ogier                    Expires September 2009                [Page 19]


Internet-Draft           MANET Extension of OSPF              March 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.

   [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 September 2009                [Page 20]


Internet-Draft           MANET Extension of OSPF              March 2009


   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 September 2009                [Page 21]


Html markup produced by rfcmarkup 1.122, available from https://tools.ietf.org/tools/rfcmarkup/