OSPF Working Group R. Ogier Internet-Draft SRI International Intended status: Informational March 4, 2010 Expires: September 5, 2010 Comparison of OSPF-MDR and OSPF-MPR draft-ogier-ospf-manet-mdr-mpr-comparison-03.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) 2010 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 5, 2010 [Page 1] Internet-Draft Comparison of OSPF-MDR and OSPF-MPR March 2010 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 5, 2010 [Page 2] Internet-Draft Comparison of OSPF-MDR and OSPF-MPR March 2010 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 5, 2010 [Page 3] Internet-Draft Comparison of OSPF-MDR and OSPF-MPR March 2010 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 5, 2010 [Page 4] Internet-Draft Comparison of OSPF-MDR and OSPF-MPR March 2010 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 5, 2010 [Page 5] Internet-Draft Comparison of OSPF-MDR and OSPF-MPR March 2010 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 5, 2010 [Page 6] Internet-Draft Comparison of OSPF-MDR and OSPF-MPR March 2010 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 5, 2010 [Page 7] Internet-Draft Comparison of OSPF-MDR and OSPF-MPR March 2010 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 5, 2010 [Page 8] Internet-Draft Comparison of OSPF-MDR and OSPF-MPR March 2010 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 5, 2010 [Page 9] Internet-Draft Comparison of OSPF-MDR and OSPF-MPR March 2010 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 5, 2010 [Page 10] Internet-Draft Comparison of OSPF-MDR and OSPF-MPR March 2010 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 5, 2010 [Page 11] Internet-Draft Comparison of OSPF-MDR and OSPF-MPR March 2010 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 5, 2010 [Page 12] Internet-Draft Comparison of OSPF-MDR and OSPF-MPR March 2010 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, "Mobile Ad Hoc Network (MANET) Extension of OSPF Using Connected Dominating Set (CDS) Flooding", RFC 5614, August 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] Roy, A. (Ed.) and M. Chandra (Ed.), "Extensions to OSPF to Support Mobile Ad Hoc Networking", draft-ietf-ospf-manet- or-03.txt (work in progress), January 2010. [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 5, 2010 [Page 13] Internet-Draft Comparison of OSPF-MDR and OSPF-MPR March 2010 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 5, 2010 [Page 14]