idnits 2.17.1 draft-ogier-ospf-manet-mdr-mpr-comparison-04.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- No issues found here. Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- No issues found here. Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the IETF Trust and authors Copyright Line does not match the current year -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (September 3, 2010) is 4955 days in the past. Is this intentional? Checking references for intended status: Informational ---------------------------------------------------------------------------- No issues found here. Summary: 0 errors (**), 0 flaws (~~), 1 warning (==), 2 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 OSPF Working Group R. Ogier 3 Internet-Draft SRI International 4 Intended status: Informational September 3, 2010 5 Expires: March 7, 2011 7 Comparison of OSPF-MDR and OSPF-MPR 8 draft-ogier-ospf-manet-mdr-mpr-comparison-04.txt 10 Status of this Memo 12 This Internet-Draft is submitted to IETF in full conformance with the 13 provisions of BCP 78 and BCP 79. 15 Internet-Drafts are working documents of the Internet Engineering 16 Task Force (IETF), its areas, and its working groups. Note that 17 other groups may also distribute working documents as Internet- 18 Drafts. 20 Internet-Drafts are draft documents valid for a maximum of six months 21 and may be updated, replaced, or obsoleted by other documents at any 22 time. It is inappropriate to use Internet-Drafts as reference 23 material or to cite them other than as "work in progress." 25 The list of current Internet-Drafts can be accessed at 26 http://www.ietf.org/1id-abstracts.html 27 The list of Internet-Draft Shadow Directories can be accessed at 28 http://www.ietf.org/shadow.html 30 Copyright Notice 32 Copyright (c) 2010 IETF Trust and the persons identified as the 33 document authors. All rights reserved. 35 This document is subject to BCP 78 and the IETF Trust's Legal 36 Provisions Relating to IETF Documents 37 (http://trustee.ietf.org/license-info) in effect on the date of 38 publication of this document. Please review these documents 39 carefully, as they describe your rights and restrictions with respect 40 to this document. 42 Abstract 44 This document presents a comparison of two proposed MANET extensions 45 of OSPF: OSPF-MDR and OSPF-MPR. It includes a qualitative 46 comparison, which discusses the different design choices and how they 47 can affect performance and scalability, and a simulation comparison. 49 Table of Contents 51 1 Introduction ................................................. 3 52 2 Brief Overview of OSPF-MDR ................................... 4 53 3 Brief Overview of OSPF-MPR ................................... 4 54 4 Qualitative Comparison ....................................... 5 55 4.1 Adjacency Reduction .......................................... 5 56 4.2 Backup Relays ................................................ 5 57 4.3 MPR Flooding versus MDR/CDS Flooding ......................... 5 58 4.4 Router-LSAs .................................................. 6 59 4.5 Inclusion of Non-adjacent Neighbors in LSAs .................. 7 60 4.6 OSPF-MPR's Synch Router ...................................... 8 61 5 Simulation Results ........................................... 8 62 5.1 Results for Dense Networks .................................. 9 63 5.2 Results for Sparser Networks ................................ 10 64 5.3 Effect of External LSAs ..................................... 11 65 6 Conclusions ................................................. 12 66 7 Security Considerations ..................................... 13 67 8 IANA Considerations ......................................... 13 68 9 Informative References ...................................... 13 69 A Instructions for Running Simulations ........................ 13 70 A.1 Running OSPF-MDR Simulations ................................ 13 71 A.2 Running OSPF-MPR Simulations ................................ 14 72 Author's Address ............................................ 14 74 1. Introduction 76 This document presents a comparison of two proposed MANET extensions 77 of OSPF: OSPF-MDR [OSPF-MDR] and OSPF-MPR [OSPF-MPR]. It includes a 78 simulation comparison and a qualitative comparison that discusses the 79 different design choices and how they can affect performance and 80 scalability. The conclusions of this document can be summarized as 81 follows: 83 o Simulations show that OSPF-MPR forms a much larger number of new 84 adjacencies per second than OSPF-MDR in large mobile networks 85 when both protocols use adjacency reduction. In a scenario with 86 100 nodes, OSPF-MPR formed about 12 times as many adjacencies as 87 OSPF-MDR, resulting in about 11 times as much overhead from 88 Database Description (DD) packets. Overhead from DD packets can 89 be very substantial if there is a large number of 90 inter-area-prefix-LSAs or AS-external-LSAs. 92 o OSPF-MDR with adjacency reduction and min-cost LSAs generates 93 much less overhead and is much more scalable than OSPF-MPR 94 (see simulation results). For example, OSPF-MDR with min-cost 95 LSAs generates less overhead with 160 nodes than OSPF-MPR 96 generates with 100 nodes. OSPF-MDR with minimal LSAs (which 97 OSPF-MPR does not provide) generates less overhead with 200 98 nodes than OSPF-MPR generates with 80 nodes. 100 o OSPF-MDR is more flexible than OSPF-MPR. For example, OSPF-MDR 101 provides two LSA options that OSPF-MPR does not provide: 103 (1) Minimal LSAs, which allow scalability to 200 nodes while 104 providing routing along nearly shortest paths. 105 (2) Full-topology LSAs with adjacency reduction, which allows 106 full-topology LSAs with lower overhead. OSPF-MPR does not 107 provide this option since it only advertises adjacent 108 neighbors in LSAs. 110 o OSPF-MPR does not provide any backup flooding; thus flooding of 111 LSAs can be delayed while MPRs are being updated. 113 o OSPF-MPR uses MPR flooding while OSPF-MDR uses MDR/CDS flooding. 114 MPRs are source-dependent and neighbor-selected, while MDRs 115 are source-independent and self-selected. Each method has 116 advantages, so it is important to compare the whole protocols 117 rather than compare MPR versus MDR flooding in isolation. 119 o In OSPF-MPR, the router with the largest Router ID is given an 120 unfair burden, since as a "synch router" it must form an adjacency 121 with each of its neighbors. This is true regardless of its router 122 priority. (OSPF-MDR uses router priority when selecting MDRs.) 124 o In OSPF-MPR, the first hop of a route need not be synchronized or 125 adjacent, and therefore can be far from synchronized. OSPF-MDR 126 requires that every hop of a route be fully adjacent or routable, 127 which ensures some degree of synchronization. 129 o OSPF-MPR does not provide differential Hellos. 131 OSPF-MDR is compared to another proposed MANET extension of OSPF 132 [OSPF-OR] in another document. Additional resources for OSPF-MDR, 133 including implementation code, simulation code, and slide 134 presentations, can be found at http://manet-routing.org. 136 2. Brief Overview of OSPF-MDR 138 OSPF-MDR [OSPF-MDR] is based on the selection of generalized 139 designated routers, called MANET designated routers (MDRs), which 140 form a connected dominating set (CDS). MDRs achieve scalability in 141 MANETs similar to the way DRs achieve scalability in broadcast 142 networks: 144 o MDRs have primary responsibility for flooding LSAs. Backup MDRs 145 provide backup flooding when MDRs temporarily fail. 147 o MDRs allow the number of adjacencies to be dramatically reduced, 148 by requiring adjacencies to be formed only between MDR/BMDR 149 routers and their neighbors. 151 Each router decides whether it is an MDR, BMDR, or neither based on 152 2-hop neighbor information obtained from modified Hello packets 153 received from neighbors. Optionally, differential Hellos can be 154 used, which reduce overhead by reporting only changes in neighbor 155 states. 157 In OSPF-MDR, the contents of router-LSAs is flexible. Either partial- 158 topology or full-topology LSAs can be used, either with or without 159 adjacency reduction. Partial-topology LSAs can be used to reduce the 160 size and origination frequency of LSAs while still providing 161 shortest-path routing. OSPF-MDR also allows the option of "minimal 162 LSAs", which minimizes overhead while providing nearly shortest-path 163 routing. 165 3. Brief Overview of OSPF-MPR 167 OSPF-MPR [OSPF-MPR] is based on multipoint relays (MPRs) and "path 168 MPRs". Path MPRs are similarly to MPRs except that link costs are 169 used in their selection. MPRs are used for flooding LSAs, and path 170 MPRs are used for constructing router-LSAs that provide shortest-path 171 routing. The router-LSA originated by each router must advertise all 172 neighbors that are either path MPRs or path MPR selectors. 174 In OSPF-MPR, each router must become adjacent with each MPR and MPR 175 selector. In addition, at least one "synch router" must be selected, 176 which must become adjacent with all of its MANET neighbors. 178 4. Qualitative Comparison 180 4.1. Adjacency Reduction 182 A major difference between OSPF-MDR and OSPF-MPR is that the latter 183 protocol, by requiring each router to form an adjacency with each MPR 184 and MPR selector, results in a much larger number of adjacencies and, 185 more importantly, a much larger number of new adjacency formations 186 per second. This is important because each adjacency formation 187 incurs a significant amount of overhead due to database exchange. The 188 simulation results presented below for 100 nodes indicate that the 189 rate of new adjacencies for OSPF-MPR is about 12 times that of OSPF- 190 MDR, resulting in about 11 times as much overhead from Database 191 Description (DD) packets. 193 In fact, the number of adjacency changes per node per second does not 194 increase with the number of nodes for OSPF-MDR, but increases 195 linearly with the number of nodes for OSPF-MPR. 197 4.2. Backup Relays 199 OSPF-MDR provides Backup MDRs, which perform backup flooding while 200 MDRs are being updated following topology changes, thus providing 201 robustness by allowing LSAs to be flooded with minimum delay even 202 when link failures occur. 204 In contrast, OSPF-MPR does not provide backup relays or backup 205 flooding; as a result, the flooding of LSAs can be delayed while MPRs 206 are being updated following topology changes. This is one possible 207 reason for the lower delivery ratio observed for OSPF-MPR in 208 simulations. 210 Although redundant MPRs can be selected, this would not provide 211 backup flooding but would provide redundant flooding and would result 212 in a larger number of adjacencies, resulting in substantially more 213 overhead. 215 4.3. MPR Flooding versus MDR/CDS Flooding 217 MPRs are source-dependent: each router selects its own MPRs, and the 218 set of relays that flood a given LSA depends on the origin of the 219 LSA. In contrast, MDRs are source-independent, similar to Designated 220 Routers. 222 Considered in isolation (independently of the rest of the protocol) 223 MPR flooding has some advantages over CDS flooding. The main 224 advantages are that MPR flooding always results in flooding over 225 minimum-hop paths, and on average MPR flooding requires fewer 226 transmissions to flood a given LSA. 228 However, MDRs are better suited for adjacency reduction, just as DRs 229 are well suited for minimizing the number of adjacencies in OSPF. 230 This is because adjacencies are source-independent, like MDRs. Since 231 MPRs are source-dependent, requiring each router to form an adjacency 232 with each neighbor that is an MPR or MPR selector results in a much 233 larger number of adjacencies, as shown in the simulation results. 235 Another difference is that MPRs are neighbor-selected while MDRs are 236 self-selected. As a result, MDRs recover faster from topology 237 changes, since MPR selection requires an additional step to inform 238 the neighbor that it has been selected as an MPR. This is another 239 possible reason for the lower delivery ratio observed for OSPF-MPR in 240 simulations. 242 When comparing the protocols, it is important to compare the whole 243 protocols, rather than compare techniques such as MPR versus MDR 244 flooding in isolation. That is why detailed simulations are more 245 useful than simplified analysis. 247 4.4. Router-LSAs 249 Both OSPF-MDR and OSPF-MPR provide partial-topology LSAs that provide 250 shortest-path routing, but they use different methods as discussed 251 below. However, OSPF-MDR is more flexible in that it provides two 252 LSA options that OSPF-MPR does not provide: 254 o OSPF-MDR provides the option of minimal LSAs, which allow 255 scalability to 200 nodes while providing routing along nearly 256 shortest paths. OSPF-MPR does not provide such an option. 258 o OSPF-MDR provides the option of full-topology LSAs with adjacency 259 reduction, which allows full-topology LSAs with reduced overhead. 260 OSPF-MDR does not provide this option, since it allows only 261 adjacent neighbors in LSAs. 263 In both OSPF-MPR and OSPF-MDR, each router advertises the link 264 metrics to all neighbors (unless all link metrics are 1) in Hellos, 265 which is necessary to provide shortest-path routing based on link 266 metrics. However, because the selection of path MPRs requires 267 knowledge of the link metric from 2-hop neighbors to 1-hop neighbors, 268 in OSPF-MPR each router must advertise (in Hellos) both the link 269 metrics *to* all neighbors and the link metrics *from* all neighbors, 270 resulting in more overhead. 272 OSPF-MPR provides partial-topology LSAs that provide shortest-path 273 routing by having each router advertise in its router-LSA all 274 neighbors that are either path MPRs or path MPR selectors. OSPF-MDR 275 achieves the same goal by having each router construct a min-cost 276 LSA, which advertises a set of neighbors sufficient to ensure that a 277 min-cost path exists from each neighbor to each other neighbor. For 278 the same reason that self-selected MDRs recover more quickly from 279 topology changes than neighbor-selected MPRs (as discussed above), 280 min-cost LSAs also recover more quickly than LSAs based on path MPRs, 281 as illustrated in the example below. 283 1 284 / \ 285 / \ 286 2 --- 3 287 \ / 288 \ / 289 4 291 All link costs are 1 in this example, so path MPRs are the same as 292 MPRs. In OSPF-MPR, assume nodes 1 and 4 select node 3 to be an MPR; 293 then node 3's LSA includes neighbors 1 and 4, and node 2's LSA is 294 empty. In OSPF-MDR, assume that node 3 is the only MDR and that node 295 3's LSA includes neighbors 1 and 4. Then node 2's LSA includes only 296 node 3 (since 2 must select 3 as parent and the parent is always 297 included in the LSA). 299 Suppose the link between nodes 1 and 3 fails, and that this is first 300 detected by node 1. 302 In OSPF-MDR, node 2 will learn of the failure via a Hello sent by 303 node 1, and will immediately add neighbors 1 and 4 to its LSA (to 304 provide a min-cost path between neighbors 1 and 4). The maximum 305 delay is 1 * HelloInterval. 307 In OSPF-MPR, node 1 will immediately select node 2 as an MPR and 308 advertise this selection in its next Hello, so node 2 will add 309 neighbor 1 to its LSA within 1 * HelloInterval. However, it will 310 take longer before node 2 adds neighbor 4 to its LSA. Node 4 must 311 first learn about the link failure, which can take 2 * HelloInterval 312 (since node 1 first detected the failure and node 4 is 2 hops from 313 node 1). Then node 4 selects node 2 as an MPR and advertises this 314 selection in its next Hello, so node 2 will add neighbor 4 to its LSA 315 within 3 * HelloInterval. (If node 2 first detected the link 316 failure, then the delay would be 2 * HelloInterval.) 318 Thus, although the min-cost LSAs of OSPF-MDR may be slightly larger 319 than LSAs based on path MPRs, they are also more robust since the 320 LSAs are updated more quickly following link failures. 322 4.5. Inclusion of Non-adjacent Neighbors in LSAs 324 In OSPF-MPR, only fully adjacent (synchronized) neighbors can be 325 advertised in LSAs. However, the first hop of a route is not 326 required to be an adjacent neighbor and can be far from synchronized. 328 In OSPF-MDR, only fully adjacent neighbors and routable neighbors can 329 be used as next hops or be advertised in LSAs. Thus, OSPF-MDR 330 requires that every hop of a route be fully adjacent or routable, 331 thus ensuring some degree of synchronization. (A neighbor being 332 routable implies that there exists, or recently existed, a path of 333 full adjacencies from the router to the neighbor.) 335 4.6. OSPF-MPR's Synch Router 337 In OSPF-MPR, the router with the largest Router ID is given an unfair 338 burden, since as a "synch router" it must form an adjacency with each 339 of its neighbors. This is true regardless of its router priority. 340 In contrast, OSPF-MDR uses router priority when selecting MDRs. 341 (Router priority can be changed dynamically so that the burden of 342 being an MDR can be shared among all routers.) 344 5. Simulation Results 346 This section presents simulation results that compare the performance 347 of OSPF-MDR and OSPF-MPR, using the GTNetS OSPFv3 MANET simulator. 348 The results for OSPF-MDR were obtained using the GTNetS simulator 349 with OSPF-MDR version 1.01, available at 350 http://hipserver.mct.phantomworks.org/ietf/ospf. The results for 351 OSPF-MPR were obtained using GTNetS code that was modified by INRIA 352 to implement OSPF-MPR. This code was announced on January 23, 2007 353 on the OSPF mailing list. Instructions for downloading this code and 354 running the simulations presented here are given in Appendix A. 356 The following scenario parameter values were used: radio range = 250 357 m and 200 m, grid length = 500 m, wireless alpha = 0.5, (maximum) 358 velocity = 10 m/s, pause time = 0, packet rate = 10 pkts/s, packet 359 size = 40 bytes, random seed = 8, start time (for gathering 360 statistics) = 1800 s. The stop time was 3600 s for up to 80 nodes 361 and 2700 s for more than 80 nodes. The source and destination are 362 selected randomly for each generated UDP packet. The simulated MAC 363 protocol is 802.11b. 365 The following protocol parameter values were used for both protocols: 366 HelloInterval = 2 s, DeadInterval = 6 s, RxmtInterval = 7 s, 367 MinLSInterval = 5 s, MinLSArrival = 1 s. AckInterval was 1 s for 368 OSPF-MDR and 500 msec for OSPF-MPR. (The results for OSPF-MPR do not 369 change significantly if 1 s is used for AckInterval.) Differential 370 hellos were used in OSPF-MDR. (OSPF-MPR does not support 371 differential Hellos.) All other parameters of OSPF-MDR were set to 372 their default values. Both protocols used the database exchange 373 optimization of [RFC5243]. 375 The following three protocol configurations were compared: (1) OSPF- 376 MDR with uniconnected adjacencies and minimal LSAs, (2) OSPF-MDR with 377 uniconnected adjacencies and min-cost LSAs, and (3) OSPF-MPR with 378 adjacency reduction and MPR-based LSAs. As mentioned above, OSPF-MPR 379 does not provide an option for minimal LSAs (which provide suboptimal 380 routing with reduced overhead). 382 5.1. Results for Dense Networks 384 The results for the three configurations with range equal to 250 m 385 are shown in Tables 1, 2, and 3, respectively. The tables show the 386 results for total OSPF overhead in kb/s, the overhead for DD packets, 387 the average number of fully adjacent neighbors per node, the number 388 of changes in the set of fully adjacent neighbors per node per 389 second, the delivery ratio for UDP packets, and the average number of 390 hops traveled by UDP packets that reach their destination. (The code 391 for OSPF-MPR did not provide the number of hops.) 393 The results show that OSPF-MPR had a much lower delivery ratio than 394 OSPF-MDR, e.g., only 89.1% versus 96.8% for 40 nodes. Possible 395 reasons for this were mentioned in Section 4. 397 OSPF-MDR generated much less overhead than OSPF-MPR, especially in 398 large networks. For 100 nodes, OSPF-MPR's overhead is about 3 times 399 that of OSPF-MDR with min-cost LSAs, and 6.5 times that of OSPF-MDR 400 with minimal LSAs. OSPF-MDR with min-cost LSAs has less overhead 401 with 160 nodes than OSPF-MPR has with only 100 nodes. 403 Although OSPF-MPR does not provide minimal LSAs, the results show the 404 scalability advantage that OSPF-MDR can achieve using minimal LSAs. 405 For example, OSPF-MDR with minimal LSAs generated about the same 406 amount of overhead with 200 nodes as OSPF-MPR generated with only 80 407 nodes. 409 For 100 nodes, OSPF-MPR formed about 12 times as many adjacencies per 410 second as OSPF-MDR, resulting in about 11 times as much overhead from 411 DD packets. As discussed in Section 5.3, overhead from DD packets 412 can be very substantial if there is a large number of inter-area- 413 prefix-LSAs or AS-external-LSAs. 415 Number of nodes 40 80 120 160 200 416 ---------------------------------------------------------------- 417 OSPF overhead (kb/s) 41.65 132.88 246.31 418.96 637.45 418 DD overhead (kb/s) 8.12 34.48 64.53 120.70 210.33 419 Adjacencies/node 2.32 2.26 2.25 2.32 2.13 420 Adj changes/node/sec 0.036 0.040 0.032 0.035 0.039 421 Delivery ratio 0.968 0.953 0.962 0.956 0.951 422 Avg no. hops 1.387 1.412 1.407 1.430 1.411 424 Table 1. Results for OSPF-MDR with minimal LSAs for range 250 m. 426 Number of nodes 40 60 80 100 120 160 427 -------------------------------------------------------------------- 428 OSPF overhead (kb/s) 74.17 175.31 248.55 354.60 479.17 795.73 429 DD overhead (kb/s) 8.14 23.50 35.00 42.66 76.01 121.42 430 Adjacencies/node 2.44 2.45 2.28 2.17 2.34 2.28 431 Adj changes/node/sec 0.037 0.047 0.040 0.029 0.037 0.035 432 Delivery ratio 0.968 0.954 0.958 0.957 0.956 0.953 433 Avg no. hops 1.348 1.389 1.368 1.411 1.361 1.386 435 Table 2. Results for OSPF-MDR with min-cost LSAs for range 250 m. 437 Number of nodes 40 60 80 100 438 --------------------------------------------------------------- 439 OSPF Overhead (kbps) 121.16 346.42 627.84 1097.31 440 DD overhead (kbps) 29.64 121.00 239.79 463.87 (10.9 x MDR) 441 Adjacencies/node 16.60 23.55 29.40 33.45 442 Adj changes/node/sec 0.14 0.25 0.28 0.36 (12.4 x MDR) 443 Delivery ratio 0.891 0.875 0.882 0.876 445 Table 3. Results for OSPF-MPR for range 250 m. 447 5.2. Results for Sparser Networks 449 Tables 4 through 6 show the results for OSPF-MDR and OSPF-MPR with 450 the same configurations as above, but with the range equal to 200 m. 451 The trend is similar to the results for range 250 m. Again, OSPF-MDR 452 had a much better delivery ratio and generated much less overhead 453 than OSPF-MPR, especially in large networks. 455 For 100 nodes, OSPF-MPR's overhead is about 3 times that of OSPF-MDR 456 with min-cost LSAs, and about 6.7 times that of OSPF-MDR with minimal 457 LSAs (which OSPF-MPR does not provide). 459 OSPF-MDR with min-cost LSAs has less overhead with 160 nodes than 460 OSPF-MPR has with only 100 nodes. OSPF-MDR with minimal LSAs has 461 less overhead with 200 nodes than OSPF-MPR has with only 80 nodes. 463 For 100 nodes, OSPF-MPR formed 9.5 times as many adjacencies per 464 second as OSPF-MDR, resulting in 10.2 times as much overhead from DD 465 packets. As discussed in the next subsection, overhead from DD 466 packets can be very substantial if there is a large number of inter- 467 area-prefix-LSAs or AS-external-LSAs. 469 Number of nodes 40 80 120 160 200 470 ---------------------------------------------------------------- 471 OSPF overhead (kb/s) 63.62 195.24 346.86 573.22 824.56 472 DD overhead (kb/s) 15.81 60.20 112.90 202.58 316.00 473 Adjacencies/node 2.60 2.50 2.39 2.36 2.24 474 Adj changes/node/sec 0.069 0.068 0.055 0.058 0.057 475 Delivery ratio 0.927 0.907 0.907 0.904 0.902 476 Avg no. hops 1.714 1.743 1.727 1.758 1.747 478 Table 4. Results for OSPF-MDR with minimal LSAs for range 200 m. 480 Number of nodes 40 60 80 100 120 160 481 ------------------------------------------------------------------- 482 OSPF overhead (kb/s) 123.45 286.40 415.69 597.50 788.87 1309.78 483 DD overhead (kb/s) 15.04 44.60 62.20 81.45 120.05 213.63 484 Adjacencies/node 2.53 2.72 2.58 2.32 2.37 2.41 485 Adj changes/node/sec 0.065 0.085 0.068 0.055 0.057 0.060 486 Delivery ratio 0.919 0.897 0.900 0.898 0.895 0.892 487 Avg no. hops 1.628 1.666 1.632 1.683 1.608 1.641 489 Table 5. Results for OSPF-MDR with min-cost LSAs for range 200 m. 491 Number of nodes 40 60 80 100 492 --------------------------------------------------------------- 493 OSPF Overhead (kbps) 178.02 500.55 970.53 1762.71 494 DD overhead (kbps) 47.75 180.34 398.49 831.15 (10.2 x MDR) 495 Adjacencies/node 16.33 23.16 29.61 32.22 496 Adj changes/node/sec 0.21 0.34 0.42 0.52 (9.5 x MDR) 497 Delivery ratio 0.837 0.804 0.790 0.730 499 Table 6. Results for OSPF-MPR for range 200 m. 501 5.3. Effect of External LSAs 503 The above simulation results are for a single area, and they assume 504 there are no LSAs originating from outside the area, such as inter- 505 area-prefix-LSAs or AS-external LSAs. If such LSAs existed, they 506 would add to the database exchange overhead even if they are static 507 (never change). We can estimate this additional overhead, using the 508 results for the adjacency change rate when adjacency reduction is 509 used. First, since only half of the adjacency changes are adjacency 510 formations (the other half being adjacency eliminations), we must 511 divide the adjacency change rate by 2. Since the database exchange 512 optimization of [RFC5243] is used, each LSA is listed in a DD packet 513 by only one of the two neighbors forming the adjacency. Therefore, 514 we must again divide by 2. Since a separate inter-area-prefix-LSA is 515 required for each prefix, and each LSA header is 20 bytes, the amount 516 of additional overhead required for M such prefixes when there are N 517 nodes is 519 (M * N * adjacency change rate / 4) * 20 bytes/s 521 Applying this formula to the results in Tables 2 and 3 for 100 nodes, 522 the additional overhead for OSPF-MDR with min-cost LSAs is (M * 120 * 523 .029 / 4) * 20 = 17.4*M bytes/s, and the additional overhead for 524 OSPF-MPR is (M * 120 * .36 / 4) * 20 = 216*M bytes/s. For example, 525 if there are 1000 external prefixes, then the additional overhead for 526 OSPF-MDR is about 17,400 bytes/s or 139.2 kb/s, and the additional 527 overhead for OSPF-MPR is about 216,000 bytes/s or 1,728 kb/s. Thus, 528 OSPF-MDR is also much more scalable than OSPF-MPR with respect to the 529 number of external prefixes, because of its smaller adjacency change 530 rate. 532 6. Conclusions 534 OSPF-MDR is much more scalable than OSPF-MPR, achieving good 535 performance in mobile networks with 200 nodes using minimal LSAs, and 536 160 nodes using min-cost LSAs (which provide shortest-path routing). 537 OSPF-MDR with min-cost LSAs generated less overhead with 160 nodes 538 than OSPF-MPR generated with 100 nodes, using adjacency reduction. 539 OSPF-MDR also achieved a much better delivery ratio than OSPF-MPR, 540 and consistently performed better than OSPF-MPR in all scenarios 541 considered. 543 OSPF-MPR forms a much larger number of new adjacencies per second 544 than OSPF-MDR in large mobile networks when both protocols use 545 adjacency reduction. In a scenario with 100 nodes and range 250 m, 546 OSPF-MPR formed about 12 times as many adjacencies as OSPF-MDR, 547 resulting in about 11 times as much overhead from Database 548 Description (DD) packets. Overhead from DD packets can be very 549 substantial if there is a large number of inter-area-prefix-LSAs or 550 AS-external-LSAs. As a result, OSPF-MDR is also much more scalable 551 than OSPF-MPR with respect to the number of external prefixes. 553 OSPF-MDR is also more flexible than OSPF-MPR and has other 554 advantages, as summarized in Section 1. For example, OSPF-MDR 555 provides two LSA options that OSPF-MPR does not provide: minimal LSAs 556 (which allow greater scalability while providing routing along nearly 557 shortest paths) and full-topology LSAs with adjacency reduction 558 (which allow full-topology LSAs with reduced overhead). In addition, 559 OSPF-MPR puts an unfair burden on the router with the largest Router 560 ID, since as a "synch router" it must form an adjacency with each of 561 its neighbors. 563 Additional resources for OSPF-MDR, including high quality 564 implementation and simulation code, can be found at http://www.manet- 565 routing.org. 567 7. Security Considerations 569 This document does not raise any new security concerns. 571 8. IANA Considerations 573 This document has no actions for IANA. 575 9. Informative References 577 [OSPF-MDR] Ogier, R. and P. Spagnolo, "Mobile Ad Hoc Network (MANET) 578 Extension of OSPF Using Connected Dominating Set (CDS) 579 Flooding", RFC 5614, August 2009. 581 [OSPF-MPR] Baccelli, E., P. Jacquet, D. Nguyen, and T. Clausen, "OSPF 582 Multipoint Relay (MPR) Extension for Ad Hoc Networks", RFC 5449, 583 February 2009. 585 [OSPF-OR] Roy, A. (Ed.) and M. Chandra (Ed.), "Extensions to OSPF to 586 Support Mobile Ad Hoc Networking", RFC 5820, March 2010. 588 [RFC5243] Ogier, R., "OSPF Database Exchange Summary List 589 Optimization", RFC 5243, May 2008. 591 A. Instructions for Running Simulations 593 A.1. Running OSPF-MDR Simulations 595 The results for OSPF-MDR were obtained using the GTNetS simulator 596 with OSPF-MDR version 1.01, available at 597 http://hipserver.mct.phantomworks.org/ietf/ospf. 599 The command used for 40 nodes, radio range 250, min-cost LSAs, and 600 uniconnected adjacencies is as follows: 602 ./random_waypoint_manet-opt seed=8 num_nodes=40 pktrate=10 \ 603 velocity=10 pause_time=0 radio_range=250 alpha=0.5 \ 604 HelloInterval=2 RxmtInterval=7 DeadInterval=6 AckInterval=1000 \ 605 BackupWaitInterval=500 TwoHopRefresh=3 AdjConnectivity=1 \ 606 LSAFullness=1 diff_hellos start_time=1800 stop_time=3600 608 For the different scenarios, num_nodes varied from from 40 to 200; 609 radio_range was 200 and 250; LSAFullness was 0 for minimal LSAs and 1 610 for min-cost LSAs; stop_time was set to 2700 when num_nodes was 100 611 or larger. 613 A.2. Running OSPF-MPR Simulations 615 The results for OSPF-MPR were obtained using GTNetS code that was 616 modified by INRIA to implement OSPF-MPR. This code was announced on 617 January 23, 2007 on the OSPF mailing list. A link for this code is 618 given in the slide presentation "Comparison of Three MANET Extensions 619 of OSPF", available at www.manet-routing.org. 621 The command used for 40 nodes, radio range 250, and adjacency 622 reduction is as follows: 624 ./random_waypoint_manet-opt seed=8 num_nodes=40 pktrate=10 \ 625 wireless_interface=2 wireless_flooding=1 TopoReduc alpha=0.5 \ 626 velocity=10 pause_time=0 radio_range=250 HelloInterval=2 \ 627 RxmtInterval=7 DeadInterval=6 PushbackInterval=3500 \ 628 AckInterval=500 MinLSInterval=5 start_time=1800 stop_time=3600 630 For the different scenarios, num_nodes varied from from 40 to 100; 631 radio_range was 200 and 250; stop_time was set to 2700 when num_nodes 632 was 100 or larger. 634 Author's Address 636 Richard G. Ogier 637 Email: rich.ogier@earthlink.net