[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-MPR
            draft-ogier-ospf-manet-mdr-mpr-comparison-01.txt

Status of this Memo

   This Internet-Draft is submitted to IETF in full conformance with the
   provisions of BCP 78 and BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/1id-abstracts.html
   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html

Copyright Notice

   Copyright (c) 2009 IETF Trust and the persons identified as the
   document authors.  All rights reserved.

   This document is subject to BCP 78 and the IETF Trust's Legal
   Provisions Relating to IETF Documents
   (http://trustee.ietf.org/license-info) in effect on the date of
   publication of this document.  Please review these documents
   carefully, as they describe your rights and restrictions with respect
   to this document.

Abstract

   This document presents a comparison of two proposed MANET extensions
   of OSPF: OSPF-MDR and OSPF-MPR.  It includes a qualitative
   comparison, which discusses the different design choices and how they
   can affect performance and scalability, and a simulation comparison.








Ogier                    Expires September 2009                 [Page 1]


Internet-Draft           MANET Extension of OSPF              March 2009


Table of Contents

   1    Introduction ................................................. 3
   2    Brief Overview of OSPF-MDR ................................... 4
   3    Brief Overview of OSPF-MPR ................................... 4
   4    Qualitative Comparison ....................................... 5
   4.1  Adjacency Reduction .......................................... 5
   4.2  Backup Relays ................................................ 5
   4.3  MPR Flooding versus MDR/CDS Flooding ......................... 5
   4.4  Router-LSAs .................................................. 6
   4.5  Inclusion of Non-adjacent Neighbors in LSAs .................. 7
   4.6  OSPF-MPR's Synch Router ...................................... 8
   5    Simulation Results ........................................... 8
   5.1  Results for Dense Networks ..................................  9
   5.2  Results for Sparser Networks ................................ 10
   5.3  Effect of External LSAs ..................................... 11
   6    Conclusions ................................................. 12
   7    Security Considerations ..................................... 13
   8    IANA Considerations ......................................... 13
   9    Informative References ...................................... 13
   A    Instructions for Running Simulations ........................ 13
   A.1  Running OSPF-MDR Simulations ................................ 13
   A.2  Running OSPF-MPR Simulations ................................ 14
        Author's Address ............................................ 14






























Ogier                    Expires September 2009                 [Page 2]


Internet-Draft           MANET Extension of OSPF              March 2009


1.  Introduction

   This document presents a comparison of two proposed MANET extensions
   of OSPF: OSPF-MDR [OSPF-MDR] and OSPF-MPR [OSPF-MPR].  It includes a
   simulation comparison and a qualitative comparison that discusses the
   different design choices and how they can affect performance and
   scalability.  The conclusions of this document can be summarized as
   follows:

   o  Simulations show that OSPF-MPR forms a much larger number of new
      adjacencies per second than OSPF-MDR in large mobile networks
      when both protocols use adjacency reduction.  In a scenario with
      100 nodes, OSPF-MPR formed about 12 times as many adjacencies as
      OSPF-MDR, resulting in about 11 times as much overhead from
      Database Description (DD) packets.  Overhead from DD packets can
      be very substantial if there is a large number of
      inter-area-prefix-LSAs or AS-external-LSAs.

   o  OSPF-MDR with adjacency reduction and min-cost LSAs generates
      much less overhead and is much more scalable than OSPF-MPR
      (see simulation results).  For example, OSPF-MDR with min-cost
      LSAs generates less overhead with 160 nodes than OSPF-MPR
      generates with 100 nodes.  OSPF-MDR with minimal LSAs (which
      OSPF-MPR does not provide) generates less overhead with 200
      nodes than OSPF-MPR generates with 80 nodes.

   o  OSPF-MDR is more flexible than OSPF-MPR.  For example, OSPF-MDR
      provides two LSA options that OSPF-MPR does not provide:

      (1) Minimal LSAs, which allow scalability to 200 nodes while
          providing routing along nearly shortest paths.
      (2) Full-topology LSAs with adjacency reduction, which allows
          full-topology LSAs with lower overhead.  OSPF-MPR does not
          provide this option since it only advertises adjacent
          neighbors in LSAs.

   o  OSPF-MPR does not provide any backup flooding; thus flooding of
      LSAs can be delayed while MPRs are being updated.

   o  OSPF-MPR uses MPR flooding while OSPF-MDR uses MDR/CDS flooding.
      MPRs are source-dependent and neighbor-selected, while MDRs
      are source-independent and self-selected.  Each method has
      advantages, so it is important to compare the whole protocols
      rather than compare MPR versus MDR flooding in isolation.

   o  In OSPF-MPR, the router with the largest Router ID is given an
      unfair burden, since as a "synch router" it must form an adjacency
      with each of its neighbors.  This is true regardless of its router
      priority.  (OSPF-MDR uses router priority when selecting MDRs.)

   o  In OSPF-MPR, the first hop of a route need not be synchronized or



Ogier                    Expires September 2009                 [Page 3]


Internet-Draft           MANET Extension of OSPF              March 2009


      adjacent, and therefore can be far from synchronized.  OSPF-MDR
      requires that every hop of a route be fully adjacent or routable,
      which ensures some degree of synchronization.

   o  OSPF-MPR does not provide differential Hellos.

   OSPF-MDR is compared to another proposed MANET extension of OSPF
   [OSPF-OR] in another document.  Additional resources for OSPF-MDR,
   including implementation code, simulation code, and slide
   presentations, can be found at http://manet-routing.org.

2.  Brief Overview of OSPF-MDR

   OSPF-MDR [OSPF-MDR] is based on the selection of generalized
   designated routers, called MANET designated routers (MDRs), which
   form a connected dominating set (CDS).  MDRs achieve scalability in
   MANETs similar to the way DRs achieve scalability in broadcast
   networks:

   o  MDRs have primary responsibility for flooding LSAs. Backup MDRs
      provide backup flooding when MDRs temporarily fail.

   o  MDRs allow the number of adjacencies to be dramatically reduced,
      by requiring adjacencies to be formed only between MDR/BMDR
      routers and their neighbors.

   Each router decides whether it is an MDR, BMDR, or neither based on
   2-hop neighbor information obtained from modified Hello packets
   received from neighbors.  Optionally, differential Hellos can be
   used, which reduce overhead by reporting only changes in neighbor
   states.

   In OSPF-MDR, the contents of router-LSAs is flexible. Either partial-
   topology or full-topology LSAs can be used, either with or without
   adjacency reduction.  Partial-topology LSAs can be used to reduce the
   size and origination frequency of LSAs while still providing
   shortest-path routing.  OSPF-MDR also allows the option of "minimal
   LSAs", which minimizes overhead while providing nearly shortest-path
   routing.


3.  Brief Overview of OSPF-MPR

   OSPF-MPR [OSPF-MPR] is based on multipoint relays (MPRs) and "path
   MPRs".  Path MPRs are similarly to MPRs except that link costs are
   used in their selection.  MPRs are used for flooding LSAs, and path
   MPRs are used for constructing router-LSAs that provide shortest-path
   routing.  The router-LSA originated by each router must advertise all
   neighbors that are either path MPRs or path MPR selectors.

   In OSPF-MPR, each router must become adjacent with each MPR and MPR



Ogier                    Expires September 2009                 [Page 4]


Internet-Draft           MANET Extension of OSPF              March 2009


   selector.  In addition, at least one "synch router" must be selected,
   which must become adjacent with all of its MANET neighbors.


4.  Qualitative Comparison

4.1.  Adjacency Reduction

   A major difference between OSPF-MDR and OSPF-MPR is that the latter
   protocol, by requiring each router to form an adjacency with each MPR
   and MPR selector, results in a much larger number of adjacencies and,
   more importantly, a much larger number of new adjacency formations
   per second.  This is important because each adjacency formation
   incurs a significant amount of overhead due to database exchange. The
   simulation results presented below for 100 nodes indicate that the
   rate of new adjacencies for OSPF-MPR is about 12 times that of OSPF-
   MDR, resulting in about 11 times as much overhead from Database
   Description (DD) packets.

   In fact, the number of adjacency changes per node per second does not
   increase with the number of nodes for OSPF-MDR, but increases
   linearly with the number of nodes for OSPF-MPR.

4.2.  Backup Relays

   OSPF-MDR provides Backup MDRs, which perform backup flooding while
   MDRs are being updated following topology changes, thus providing
   robustness by allowing LSAs to be flooded with minimum delay even
   when link failures occur.

   In contrast, OSPF-MPR does not provide backup relays or backup
   flooding; as a result, the flooding of LSAs can be delayed while MPRs
   are being updated following topology changes.  This is one possible
   reason for the lower delivery ratio observed for OSPF-MPR in
   simulations.

   Although redundant MPRs can be selected, this would not provide
   backup flooding but would provide redundant flooding and would result
   in a larger number of adjacencies, resulting in substantially more
   overhead.

4.3.  MPR Flooding versus MDR/CDS Flooding

   MPRs are source-dependent: each router selects its own MPRs, and the
   set of relays that flood a given LSA depends on the origin of the
   LSA.  In contrast, MDRs are source-independent, similar to Designated
   Routers.

   Considered in isolation (independently of the rest of the protocol)
   MPR flooding has some advantages over CDS flooding.  The main
   advantages are that MPR flooding always results in flooding over



Ogier                    Expires September 2009                 [Page 5]


Internet-Draft           MANET Extension of OSPF              March 2009


   minimum-hop paths, and on average MPR flooding requires fewer
   transmissions to flood a given LSA.

   However, MDRs are better suited for adjacency reduction, just as DRs
   are well suited for minimizing the number of adjacencies in OSPF.
   This is because adjacencies are source-independent, like MDRs.  Since
   MPRs are source-dependent, requiring each router to form an adjacency
   with each neighbor that is an MPR or MPR selector results in a much
   larger number of adjacencies, as shown in the simulation results.

   Another difference is that MPRs are neighbor-selected while MDRs are
   self-selected.  As a result, MDRs recover faster from topology
   changes, since MPR selection requires an additional step to inform
   the neighbor that it has been selected as an MPR.  This is another
   possible reason for the lower delivery ratio observed for OSPF-MPR in
   simulations.

   When comparing the protocols, it is important to compare the whole
   protocols, rather than compare techniques such as MPR versus MDR
   flooding in isolation.  That is why detailed simulations are more
   useful than simplified analysis.

4.4.  Router-LSAs

   Both OSPF-MDR and OSPF-MPR provide partial-topology LSAs that provide
   shortest-path routing, but they use different methods as discussed
   below.  However, OSPF-MDR is more flexible in that it provides two
   LSA options that OSPF-MPR does not provide:

   o  OSPF-MDR provides the option of minimal LSAs, which allow
      scalability to 200 nodes while providing routing along nearly
      shortest paths.  OSPF-MPR does not provide such an option.

   o  OSPF-MDR provides the option of full-topology LSAs with adjacency
      reduction, which allows full-topology LSAs with reduced overhead.
      OSPF-MDR does not provide this option, since it allows only
      adjacent neighbors in LSAs.

   In both OSPF-MPR and OSPF-MDR, each router advertises the link
   metrics to all neighbors (unless all link metrics are 1) in Hellos,
   which is necessary to provide shortest-path routing based on link
   metrics.  However, because the selection of path MPRs requires
   knowledge of the link metric from 2-hop neighbors to 1-hop neighbors,
   in OSPF-MPR each router must advertise (in Hellos) both the link
   metrics *to* all neighbors and the link metrics *from* all neighbors,
   resulting in more overhead.

   OSPF-MPR provides partial-topology LSAs that provide shortest-path
   routing by having each router advertise in its router-LSA all
   neighbors that are either path MPRs or path MPR selectors.  OSPF-MDR
   achieves the same goal by having each router construct a min-cost



Ogier                    Expires September 2009                 [Page 6]


Internet-Draft           MANET Extension of OSPF              March 2009


   LSA, which advertises a set of neighbors sufficient to ensure that a
   min-cost path exists from each neighbor to each other neighbor.  For
   the same reason that self-selected MDRs recover more quickly from
   topology changes than neighbor-selected MPRs (as discussed above),
   min-cost LSAs also recover more quickly than LSAs based on path MPRs,
   as illustrated in the example below.

       1
      / \
     /   \
    2 --- 3
     \   /
      \ /
       4

   All link costs are 1 in this example, so path MPRs are the same as
   MPRs.  In OSPF-MPR, assume nodes 1 and 4 select node 3 to be an MPR;
   then node 3's LSA includes neighbors 1 and 4, and node 2's LSA is
   empty.  In OSPF-MDR, assume that node 3 is the only MDR and that node
   3's LSA includes neighbors 1 and 4.  Then node 2's LSA includes only
   node 3 (since 2 must select 3 as parent and the parent is always
   included in the LSA).

   Suppose the link between nodes 1 and 3 fails, and that this is first
   detected by node 1.

   In OSPF-MDR, node 2 will learn of the failure via a Hello sent by
   node 1, and will immediately add neighbors 1 and 4 to its LSA (to
   provide a min-cost path between neighbors 1 and 4).  The maximum
   delay is 1 * HelloInterval.

   In OSPF-MPR, node 1 will immediately select node 2 as an MPR and
   advertise this selection in its next Hello, so node 2 will add
   neighbor 1 to its LSA within 1 * HelloInterval.  However, it will
   take longer before node 2 adds neighbor 4 to its LSA.  Node 4 must
   first learn about the link failure, which can take 2 * HelloInterval
   (since node 1 first detected the failure and node 4 is 2 hops from
   node 1). Then node 4 selects node 2 as an MPR and advertises this
   selection in its next Hello, so node 2 will add neighbor 4 to its LSA
   within 3 * HelloInterval.  (If node 2 first detected the link
   failure, then the delay would be 2 * HelloInterval.)

   Thus, although the min-cost LSAs of OSPF-MDR may be slightly larger
   than LSAs based on path MPRs, they are also more robust since the
   LSAs are updated more quickly following link failures.

4.5.  Inclusion of Non-adjacent Neighbors in LSAs

   In OSPF-MPR, only fully adjacent (synchronized) neighbors can be
   advertised in LSAs.  However, the first hop of a route is not
   required to be an adjacent neighbor and can be far from synchronized.



Ogier                    Expires September 2009                 [Page 7]


Internet-Draft           MANET Extension of OSPF              March 2009


   In OSPF-MDR, only fully adjacent neighbors and routable neighbors can
   be used as next hops or be advertised in LSAs.  Thus, OSPF-MDR
   requires that every hop of a route be fully adjacent or routable,
   thus ensuring some degree of synchronization.  (A neighbor being
   routable implies that there exists, or recently existed, a path of
   full adjacencies from the router to the neighbor.)

4.6.  OSPF-MPR's Synch Router

   In OSPF-MPR, the router with the largest Router ID is given an unfair
   burden, since as a "synch router" it must form an adjacency with each
   of its neighbors.  This is true regardless of its router priority.
   In contrast, OSPF-MDR uses router priority when selecting MDRs.
   (Router priority can be changed dynamically so that the burden of
   being an MDR can be shared among all routers.)


5.  Simulation Results

   This section presents simulation results that compare the performance
   of OSPF-MDR and OSPF-MPR, using the GTNetS OSPFv3 MANET simulator.
   The results for OSPF-MDR were obtained using the GTNetS simulator
   with OSPF-MDR version 1.01, available at
   http://hipserver.mct.phantomworks.org/ietf/ospf.  The results for
   OSPF-MPR were obtained using GTNetS code that was modified by INRIA
   to implement OSPF-MPR.  This code was announced on January 23, 2007
   on the OSPF mailing list.  Instructions for downloading this code and
   running the simulations presented here are given in Appendix A.

   The following scenario parameter values were used: radio range = 250
   m and 200 m, grid length = 500 m, wireless alpha = 0.5, (maximum)
   velocity = 10 m/s, pause time = 0, packet rate = 10 pkts/s, packet
   size = 40 bytes, random seed = 8, start time (for gathering
   statistics) = 1800 s.  The stop time was 3600 s for up to 80 nodes
   and 2700 s for more than 80 nodes.  The source and destination are
   selected randomly for each generated UDP packet.  The simulated MAC
   protocol is 802.11b.

   The following protocol parameter values were used for both protocols:
   HelloInterval = 2 s, DeadInterval = 6 s, RxmtInterval = 7 s,
   MinLSInterval = 5 s, MinLSArrival = 1 s.  AckInterval was 1 s for
   OSPF-MDR and 500 msec for OSPF-MPR.  (The results for OSPF-MPR do not
   change significantly if 1 s is used for AckInterval.)  Differential
   hellos were used in OSPF-MDR.  (OSPF-MPR does not support
   differential Hellos.)  All other parameters of OSPF-MDR were set to
   their default values.  Both protocols used the database exchange
   optimization of [RFC5243].

   The following three protocol configurations were compared: (1) OSPF-
   MDR with uniconnected adjacencies and minimal LSAs, (2) OSPF-MDR with
   uniconnected adjacencies and min-cost LSAs, and (3) OSPF-MPR with



Ogier                    Expires September 2009                 [Page 8]


Internet-Draft           MANET Extension of OSPF              March 2009


   adjacency reduction and MPR-based LSAs.  As mentioned above, OSPF-MPR
   does not provide an option for minimal LSAs (which provide suboptimal
   routing with reduced overhead).

5.1.  Results for Dense Networks

   The results for the three configurations with range equal to 250 m
   are shown in Tables 1, 2, and 3, respectively.  The tables show the
   results for total OSPF overhead in kb/s, the overhead for DD packets,
   the average number of fully adjacent neighbors per node, the number
   of changes in the set of fully adjacent neighbors per node per
   second, the delivery ratio for UDP packets, and the average number of
   hops traveled by UDP packets that reach their destination.  (The code
   for OSPF-MPR did not provide the number of hops.)

   The results show that OSPF-MPR had a much lower delivery ratio than
   OSPF-MDR, e.g., only 89.1% versus 96.8% for 40 nodes.  Possible
   reasons for this were mentioned in Section 4.

   OSPF-MDR generated much less overhead than OSPF-MPR, especially in
   large networks.  For 100 nodes, OSPF-MPR's overhead is about 3 times
   that of OSPF-MDR with min-cost LSAs, and 6.5 times that of OSPF-MDR
   with minimal LSAs.  OSPF-MDR with min-cost LSAs has less overhead
   with 160 nodes than OSPF-MPR has with only 100 nodes.

   Although OSPF-MPR does not provide minimal LSAs, the results show the
   scalability advantage that OSPF-MDR can achieve using minimal LSAs.
   For example, OSPF-MDR with minimal LSAs generated about the same
   amount of overhead with 200 nodes as OSPF-MPR generated with only 80
   nodes.

   For 100 nodes, OSPF-MPR formed about 12 times as many adjacencies per
   second as OSPF-MDR, resulting in about 11 times as much overhead from
   DD packets.  As discussed in Section 5.3, overhead from DD packets
   can be very substantial if there is a large number of inter-area-
   prefix-LSAs or AS-external-LSAs.


   Number of nodes         40       80      120      160      200
   ----------------------------------------------------------------
   OSPF overhead (kb/s)  41.65   132.88   246.31   418.96   637.45
   DD overhead (kb/s)     8.12    34.48    64.53   120.70   210.33
   Adjacencies/node       2.32     2.26     2.25     2.32     2.13
   Adj changes/node/sec   0.036    0.040    0.032    0.035    0.039
   Delivery ratio         0.968    0.953    0.962    0.956    0.951
   Avg no. hops           1.387    1.412    1.407    1.430    1.411

   Table 1. Results for OSPF-MDR with minimal LSAs for range 250 m.






Ogier                    Expires September 2009                 [Page 9]


Internet-Draft           MANET Extension of OSPF              March 2009


   Number of nodes         40      60      80     100     120     160
   --------------------------------------------------------------------
   OSPF overhead (kb/s)  74.17  175.31  248.55  354.60  479.17  795.73
   DD overhead (kb/s)     8.14   23.50   35.00   42.66   76.01  121.42
   Adjacencies/node       2.44    2.45    2.28    2.17    2.34    2.28
   Adj changes/node/sec   0.037   0.047   0.040   0.029   0.037   0.035
   Delivery ratio         0.968   0.954   0.958   0.957   0.956   0.953
   Avg no. hops           1.348   1.389   1.368   1.411   1.361   1.386

   Table 2. Results for OSPF-MDR with min-cost LSAs for range 250 m.


   Number of nodes         40      60      80     100
   ---------------------------------------------------------------
   OSPF Overhead (kbps) 121.16  346.42  627.84  1097.31
   DD overhead (kbps)    29.64  121.00  239.79   463.87 (10.9 x MDR)
   Adjacencies/node      16.60   23.55   29.40    33.45
   Adj changes/node/sec   0.14    0.25    0.28     0.36 (12.4 x MDR)
   Delivery ratio         0.891   0.875   0.882    0.876

   Table 3. Results for OSPF-MPR for range 250 m.


5.2.  Results for Sparser Networks

   Tables 4 through 6 show the results for OSPF-MDR and OSPF-MPR with
   the same configurations as above, but with the range equal to 200 m.
   The trend is similar to the results for range 250 m.  Again, OSPF-MDR
   had a much better delivery ratio and generated much less overhead
   than OSPF-MPR, especially in large networks.

   For 100 nodes, OSPF-MPR's overhead is about 3 times that of OSPF-MDR
   with min-cost LSAs, and about 6.7 times that of OSPF-MDR with minimal
   LSAs (which OSPF-MPR does not provide).

   OSPF-MDR with min-cost LSAs has less overhead with 160 nodes than
   OSPF-MPR has with only 100 nodes.  OSPF-MDR with minimal LSAs has
   less overhead with 200 nodes than OSPF-MPR has with only 80 nodes.

   For 100 nodes, OSPF-MPR formed 9.5 times as many adjacencies per
   second as OSPF-MDR, resulting in 10.2 times as much overhead from DD
   packets.  As discussed in the next subsection, overhead from DD
   packets can be very substantial if there is a large number of inter-
   area-prefix-LSAs or AS-external-LSAs.










Ogier                    Expires September 2009                [Page 10]


Internet-Draft           MANET Extension of OSPF              March 2009


   Number of nodes         40       80      120      160      200
   ----------------------------------------------------------------
   OSPF overhead (kb/s)  63.62   195.24   346.86   573.22   824.56
   DD overhead (kb/s)    15.81    60.20   112.90   202.58   316.00
   Adjacencies/node       2.60     2.50     2.39     2.36     2.24
   Adj changes/node/sec   0.069    0.068    0.055    0.058    0.057
   Delivery ratio         0.927    0.907    0.907    0.904    0.902
   Avg no. hops           1.714    1.743    1.727    1.758    1.747

   Table 4. Results for OSPF-MDR with minimal LSAs for range 200 m.


   Number of nodes         40      60      80     100     120     160
   -------------------------------------------------------------------
   OSPF overhead (kb/s) 123.45  286.40  415.69  597.50  788.87 1309.78
   DD overhead (kb/s)    15.04   44.60   62.20   81.45  120.05  213.63
   Adjacencies/node       2.53    2.72    2.58    2.32    2.37    2.41
   Adj changes/node/sec   0.065   0.085   0.068   0.055   0.057   0.060
   Delivery ratio         0.919   0.897   0.900   0.898   0.895   0.892
   Avg no. hops           1.628   1.666   1.632   1.683   1.608   1.641

   Table 5. Results for OSPF-MDR with min-cost LSAs for range 200 m.


   Number of nodes         40      60      80     100
   ---------------------------------------------------------------
   OSPF Overhead (kbps) 178.02  500.55  970.53  1762.71
   DD overhead (kbps)    47.75  180.34  398.49   831.15 (10.2 x MDR)
   Adjacencies/node      16.33   23.16   29.61    32.22
   Adj changes/node/sec   0.21    0.34    0.42     0.52 (9.5 x MDR)
   Delivery ratio         0.837   0.804   0.790    0.730

   Table 6. Results for OSPF-MPR for range 200 m.


5.3.  Effect of External LSAs

   The above simulation results are for a single area, and they assume
   there are no LSAs originating from outside the area, such as inter-
   area-prefix-LSAs or AS-external LSAs.  If such LSAs existed, they
   would add to the database exchange overhead even if they are static
   (never change).  We can estimate this additional overhead, using the
   results for the adjacency change rate when adjacency reduction is
   used.  First, since only half of the adjacency changes are adjacency
   formations (the other half being adjacency eliminations), we must
   divide the adjacency change rate by 2.  Since the database exchange
   optimization of [RFC5243] is used, each LSA is listed in a DD packet
   by only one of the two neighbors forming the adjacency.  Therefore,
   we must again divide by 2.  Since a separate inter-area-prefix-LSA is
   required for each prefix, and each LSA header is 20 bytes, the amount
   of additional overhead required for M such prefixes when there are N



Ogier                    Expires September 2009                [Page 11]


Internet-Draft           MANET Extension of OSPF              March 2009


   nodes is

   (M * N * adjacency change rate / 4) * 20 bytes/s

   Applying this formula to the results in Tables 2 and 3 for 100 nodes,
   the additional overhead for OSPF-MDR with min-cost LSAs is (M * 120 *
   .029 / 4) * 20 = 17.4*M bytes/s, and the additional overhead for
   OSPF-MPR is (M * 120 * .36 / 4) * 20 = 216*M bytes/s.  For example,
   if there are 1000 external prefixes, then the additional overhead for
   OSPF-MDR is about 17,400 bytes/s or 139.2 kb/s, and the additional
   overhead for OSPF-MPR is about 216,000 bytes/s or 1,728 kb/s.  Thus,
   OSPF-MDR is also much more scalable than OSPF-MPR with respect to the
   number of external prefixes, because of its smaller adjacency change
   rate.


6.  Conclusions

   OSPF-MDR is much more scalable than OSPF-MPR, achieving good
   performance in mobile networks with 200 nodes using minimal LSAs, and
   160 nodes using min-cost LSAs (which provide shortest-path routing).
   OSPF-MDR with min-cost LSAs generated less overhead with 160 nodes
   than OSPF-MPR generated with 100 nodes, using adjacency reduction.
   OSPF-MDR also achieved a much better delivery ratio than OSPF-MPR,
   and consistently performed better than OSPF-MPR in all scenarios
   considered.

   OSPF-MPR forms a much larger number of new adjacencies per second
   than OSPF-MDR in large mobile networks when both protocols use
   adjacency reduction.  In a scenario with 100 nodes and range 250 m,
   OSPF-MPR formed about 12 times as many adjacencies as OSPF-MDR,
   resulting in about 11 times as much overhead from Database
   Description (DD) packets.  Overhead from DD packets can be very
   substantial if there is a large number of inter-area-prefix-LSAs or
   AS-external-LSAs.  As a result, OSPF-MDR is also much more scalable
   than OSPF-MPR with respect to the number of external prefixes.

   OSPF-MDR is also more flexible than OSPF-MPR and has other
   advantages, as summarized in Section 1.  For example, OSPF-MDR
   provides two LSA options that OSPF-MPR does not provide: minimal LSAs
   (which allow greater scalability while providing routing along nearly
   shortest paths) and full-topology LSAs with adjacency reduction
   (which allow full-topology LSAs with reduced overhead).  In addition,
   OSPF-MPR puts an unfair burden on the router with the largest Router
   ID, since as a "synch router" it must form an adjacency with each of
   its neighbors.

   Additional resources for OSPF-MDR, including high quality
   implementation and simulation code, can be found at http://www.manet-
   routing.org.




Ogier                    Expires September 2009                [Page 12]


Internet-Draft           MANET Extension of OSPF              March 2009


7.  Security Considerations

   This document does not raise any new security concerns.

8.  IANA Considerations

   This document has no actions for IANA.

9.  Informative References

   [OSPF-MDR] Ogier, R. and P. Spagnolo, "MANET Extension of OSPF using
        CDS Flooding", draft-ietf-ospf-manet-mdr-05.txt (work in
        progress), January 2009.

   [OSPF-MPR] Baccelli, E., P. Jacquet, D. Nguyen, and T. Clausen, "OSPF
        Multipoint Relay (MPR) Extension for Ad Hoc Networks", RFC 5449,
        February 2009.

   [OSPF-OR] Chandra, M. (ed.) and A. Roy (ed.), "Extensions to OSPF to
        Support Mobile Ad Hoc Networking", draft-ietf-ospf-manet-
        or-01.txt (work in progress), September 2008.

   [RFC5243] Ogier, R., "OSPF Database Exchange Summary List
        Optimization", RFC 5243, May 2008.

A.  Instructions for Running Simulations

A.1.  Running OSPF-MDR Simulations

   The results for OSPF-MDR were obtained using the GTNetS simulator
   with OSPF-MDR version 1.01, available at
   http://hipserver.mct.phantomworks.org/ietf/ospf.

   The command used for 40 nodes, radio range 250, min-cost LSAs, and
   uniconnected adjacencies is as follows:

   ./random_waypoint_manet-opt seed=8 num_nodes=40 pktrate=10 \
     velocity=10 pause_time=0 radio_range=250 alpha=0.5 \
     HelloInterval=2 RxmtInterval=7 DeadInterval=6 AckInterval=1000 \
     BackupWaitInterval=500 TwoHopRefresh=3 AdjConnectivity=1 \
     LSAFullness=1 diff_hellos start_time=1800 stop_time=3600

   For the different scenarios, num_nodes varied from from 40 to 200;
   radio_range was 200 and 250; LSAFullness was 0 for minimal LSAs and 1
   for min-cost LSAs; stop_time was set to 2700 when num_nodes was 100
   or larger.

A.2.  Running OSPF-MPR Simulations

   The results for OSPF-MPR were obtained using GTNetS code that was
   modified by INRIA to implement OSPF-MPR.  This code was announced on



Ogier                    Expires September 2009                [Page 13]


Internet-Draft           MANET Extension of OSPF              March 2009


   January 23, 2007 on the OSPF mailing list.  A link for this code is
   given in the slide presentation "Comparison of Three MANET Extensions
   of OSPF", available at www.manet-routing.org.

   The command used for 40 nodes, radio range 250, and adjacency
   reduction is as follows:

   ./random_waypoint_manet-opt seed=8 num_nodes=40 pktrate=10 \
    wireless_interface=2 wireless_flooding=1 TopoReduc alpha=0.5 \
    velocity=10 pause_time=0 radio_range=250 HelloInterval=2 \
    RxmtInterval=7 DeadInterval=6 PushbackInterval=3500 \
    AckInterval=500 MinLSInterval=5 start_time=1800 stop_time=3600

  For the different scenarios, num_nodes varied from from 40 to 100;
  radio_range was 200 and 250; stop_time was set to 2700 when num_nodes
  was 100 or larger.

Author's Address

   Richard G. Ogier
   Email: rich.ogier@earthlink.net

































Ogier                    Expires September 2009                [Page 14]


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