OSPF Working Group R. Ogier Internet-Draft SRI International Intended status: Informational September 2, 2009 Expires: March 6, 2010 Comparison of OSPF-MDR and OSPF-OR draft-ogier-ospf-manet-mdr-or-comparison-02.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 in effect on the date of publication of this document (http://trustee.ietf.org/license-info). 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 March 6, 2010 [Page 1] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 2] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 3] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 4] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 5] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 6] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 7] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 8] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 9] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 10] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 11] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 12] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 13] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 14] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 15] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 16] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 17] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 18] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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, "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. Ogier Expires March 6, 2010 [Page 19] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 2009 [OSPF-OR] Roy, A. (Ed.) and M. Chandra (Ed.), "Extensions to OSPF to Support Mobile Ad Hoc Networking", draft-ietf-ospf-manet- or-02.txt (work in progress), July 2009. [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State Routing Protocol", RFC 3626, October 2003. [RFC5243] Ogier, R., "OSPF Database Exchange Summary List Optimization", RFC 5243, May 2008. [Roy06] Roy, A. (ed.), "Adjacency Reduction in OSPF using SPT Reachability", draft-roy-ospf-smart-peering-01.txt (work in progress), November 2005. A. Instructions for Running Simulations A.1. Running OSPF-MDR Simulations The results for OSPF-MDR were obtained using the GTNetS simulator with OSPF-MDR version 1.01, available at http://hipserver.mct.phantomworks.org/ietf/ospf. The command used for 20 nodes, radio range 250, min-cost LSAs, and uniconnected adjacencies is as follows: ./random_waypoint_manet-opt seed=8 num_nodes=20 pktrate=10 \ velocity=10 pause_time=0 radio_range=250 alpha=0.5 \ HelloInterval=2 RxmtInterval=7 DeadInterval=6 AckInterval=1000 \ BackupWaitInterval=500 TwoHopRefresh=3 AdjConnectivity=1 \ LSAFullness=1 diff_hellos start_time=1800 stop_time=3600 For the different scenarios, num_nodes varied from from 20 to 200; radio_range was 150, 200, and 250; LSAFullness was 0 for minimal LSAs, 1 for min-cost LSAs, and 4 for full LSAs; AdjConnectivity was 1 for uniconnected adjacencies and 0 for full-topology adjacencies; stop_time was set to 2700 when num_nodes was 100 or larger. A.2. Running OSPF-OR Simulations The results for OSPF-OR were obtained using the GTNetS code that was used for the paper [MILCOM06]. A link for this code is given in the slide presentation "Comparison of Three MANET Extensions of OSPF", available at www.manet-routing.org. (The OSPF-MDR code contained in this code is not compliant with the current version of the OSPF-MDR draft and contains some bugs.) To activate the database exchange optimization of RFC 5243, uncomment the following line in Makefile in the gtnets-milcom06 directory: CFLAGS += -DOSPF6_MANET_MDR_FLOOD_DD Ogier Expires March 6, 2010 [Page 20] Internet-Draft Comparison of OSPF-MDR and OSPF-OR September 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 March 6, 2010 [Page 21]