OSPF/MANET Working Groups R. Ogier Internet-Draft February 27, 2006 Expires: August 27, 2006 Advantages of OSPF-MDR draft-ogier-ospf-mdr-position-00.txt Status of this Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of 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 This Internet-Draft will expire on August 27, 2006. Copyright Notice Copyright (C) The Internet Society (2006). Abstract This document summarizes and discusses the advantages of OSPF-MDR, a proposed extension of OSPF that supports the MANET interface type. Ogier Expires August 27, 2006 [Page 1] Internet-Draft Advantages of OSPF-MDR February 2006 1. Introduction OSPF-MDR [OSPF-MDR] is an extension of OSPF that supports the new MANET interface type, in addition to the interface types already supported by OSPF. OSPF-MDR performs flooding along a connected dominating set (CDS), consisting of MANET Designated Routers (MDRs) and Backup MDRs, which generalize the notion of the Designated Router (DR) and Backup DR to multihop wireless networks. To reduce the number of adjacencies, in OSPF-MDR only a subset of neighbor pairs (links) form adjacencies, which are selected to ensure the set of adjacencies (called the adjacency subgraph) is connected and spans all routers. This is accomplished by ensuring that the MDRs together with the adjacencies between them form a connected backbone, and by having each non-MDR router form an adjacency with at least one MDR neighbor (its parent). The configurable parameter AdjConnectivity can be set to 1 or 2, which ensures the adjacency subgraph is connected or biconnected, respectively. The purpose of this draft is to summarize and discuss the advantages of OSPF-MDR. To help understand the approach, Section 2 gives a brief overview, which includes motivation and rationale for some of the design choices. Section 3 then summarizes some of the advantages of OSPF-MDR, and Section 4 provides a qualitative comparison of OSPF- MDR to Overlapping Relays (OR) [Chandra] with Smart Peering (SP) [Roy]. Section 5 presents some simulation results showing the robustness of OSPF-MDR, and Section 6 presents some simulation results showing that adjacency reduction is necessary for scalability. Section 7 discusses proposals to use multipoint relays (MPRs), Section 8 presents a simulation comparison to OR/SP in a mobile network with 100 nodes, and Section 9 presents conclusions. 2. Overview This section provides a brief overview of OSPF-MDR, and includes motivation and rationale for some of the design choices. OSPF-MDR was motivated by the desire to extend OSPF to support MANETs, while keeping the same design philosophy as OSPF and using techniques that are similar to those of OSPF. For example, OSPF reduces overhead in a broadcast network by electing a Designated Router (DR) and Backup DR, and by having two neighboring routers form an adjacency only if one of them is the DR or Backup DR. This idea can be generalized to a multihop wireless network by forming a spanning tree, with the edges of the tree being the adjacencies and the interior (non-leaf) nodes of the tree being the generalized DRs, called MANET Designated Routers (MDRs). Ogier Expires August 27, 2006 [Page 2] Internet-Draft Advantages of OSPF-MDR February 2006 To provide better robustness and fast response to topology changes, it was decided that a router should decide whether it is an MDR based only on 2-hop neighbor information that can be obtained from neighbors' Hellos (similar to OSPF). The resulting set of adjacencies therefore does not always form a tree globally, but appears to be a tree locally. Similarly, the Backup DR can be generalized to Backup MDRs (BMDRs), to provide robustness through biconnected redundancy. The set of MDRs forms a connected dominating set (CDS), and the set of MDRs and BMDRs forms a biconnected dominating set. The following subsection summarizes how MDRs, BMDRs, and adjacencies are selected. 2.1. Selection of MDRs, BMDRs, Parents, and Adjacencies The selection of MDRs can be summarized as follows. Let Rmax denote the neighbor with the lexicographically largest value of (MDR Level, RtrPri, RID), where MDR Level is 2 for an MDR, 1 for a BMDR, and 0 for an MDR Other. Then a router selects itself as an MDR unless each neighbor can be reached from Rmax in at most k hops via neighbors that have a larger value of (MDR Level, RtrPri, RID) than the router itself. (k is the parameter MDRConstraint, whose default value is 3.) Similarly, a router that does not select itself as an MDR will select itself as a BMDR unless each neighbor can be reached from Rmax via two node-disjoint paths, using as intermediate hops only neighbors that have a larger value of (MDR Level, RtrPri, RID) than the router itself. When a router selects itself as an MDR, it also decides which MDR neighbors it should become adjacent with, to ensure that the set of MDRs and the adjacencies between them form a connected backbone. Each non-MDR router selects and becomes adjacent with an MDR neighbor called its parent, thus ensuring that all routers are connected to the MDR backbone. If the option of biconnected adjacencies is used (AdjConnectivity = 2), then additional adjacencies are selected to ensure that the set of MDRs and BMDRs, and the adjacencies between them, form a biconnected backbone. In this case, each MDR Other selects and becomes adjacent with an MDR/BMDR neighbor called its backup parent, in addition to its MDR parent. OSPF-MDR will also provide the option of full-topology adjacencies. A router that selects this option will always form an adjacency with each bidirectional neighbor that also selects this option. Prioritizing routers according to (MDR Level, RtrPri, RID) allows Ogier Expires August 27, 2006 [Page 3] Internet-Draft Advantages of OSPF-MDR February 2006 neighboring routers to agree on which routers should become an MDR, and gives higher priority to existing MDRs, which increases the lifetime of MDRs and the adjacencies between them. In addition, parents are selected to be existing adjacent neighbors whenever possible, to avoid forming new adjacencies unless necessary. Once a neighbor becomes adjacent, it remain adjacent as long as the neighbor is bidirectional and either the neighbor or the router itself is an MDR or BMDR (similar to OSPF). The above rules reduce the rate at which new adjacencies are formed, which is important since database exchange must be performed whenever a new adjacency is formed. Prioritizing routers according to (MDR Level, RtrPri, RID) not only increases the lifetime of MDRs and adjacencies, but also achieves consistency with the DR election algorithm, which gives highest priority to existing DRs. As a result, when applied to a fully connected MANET, the MDR selection algorithm and the DR election algorithm both select the same two routers as DR/MDR and BDR/BMDR. (The MDR section algorithm also selects a second BMDR so that the MDR/BMDR backbone is biconnected.) 2.2. Flooding Procedure When an MDR receives a new LSA on a MANET interface, it immediately floods the LSA back out the receiving interface (unless it can be determined that such flooding is unnecessary). When a Backup MDR receives a new LSA on a MANET interface, it waits a short interval (BackupWaitInterval), and then floods the LSA only if there exists a neighbor that is not covered by another neighbor from which the LSA has been received. MDR Other routers never flood LSAs back out the receiving interface. To exploit the broadcast nature of MANETs, a new LSA is processed (and possibly forwarded) if it is received from any neighbor in state 2-Way or greater. The flooding procedure also avoids redundant forwarding of LSAs when multiple interfaces exist. 2.3. Link State Acknowledgments All Link State Acks are multicast. An LSA is acknowledged if it is a new LSA, or if it is a duplicate LSA received as a unicast. (A duplicate LSA received as multicast is not acknowledged.) An LSA that is flooded back out the same interface is treated as an implicit Ack. Link State Acks may be delayed up to AckInterval seconds to allow coalescing multiple Acks in the same packet. The only exception is that (Backup) MDRs send a multicast Ack immediately when a duplicate LSA is received as a unicast, in order to prevent additional retransmissions. Only Acks from adjacent neighbors are processed, and retransmitted LSAs are sent (via unicast) only to Ogier Expires August 27, 2006 [Page 4] Internet-Draft Advantages of OSPF-MDR February 2006 adjacent neighbors. 2.4. Routable Neighbors A MANET neighbor is defined to be routable if its state is Full, or if the SPF calculation has produced a route to the neighbor and the neighbor satisfies a flexible quality condition. Only routable MANET neighbors can be used as next hops in the SPF calculation, and can be included in the router-LSA originated by the router. The idea is that if the SPF calculation has produced a route to the neighbor, then it makes sense to take a "shortcut" and forward packets directly to the neighbor. Note that OSPF already allows a non-adjacent neighbor to be used as a next hop, if both routers are fully adjacent to the DR of a broadcast network. The routability condition is a generalization of this condition to MANETs. The network-LSA of an OSPF broadcast network implies that a router can use a non-adjacent neighbor as a next hop. But a network-LSA cannot describe the general topology of a MANET, making it necessary to explicitly include non-adjacent neighbors in the router-LSA. Allowing only adjacent neighbors in LSAs would either result in suboptimal paths or would require a large number of adjacencies (see Section X). 2.5. Partial and Full Topology LSAs Each router advertises a subset of its routable neighbors as point- to-point connections in its router-LSA. The choice of which neighbors to advertise is flexible, and is determined by the configurable parameter LSAFullness. As a minimum requirement, each router must advertise all of its fully adjacent neighbors in its router-LSA. This minimum choice corresponds to LSAFullness = 0. This choice results in the minimum amount of LSA flooding overhead, but does not provide routing along shortest paths. Setting LSAFullness to 1 or 2 results in min-cost LSAs, which provide min-hop routing, and can provide min-cost routing under certain assumptions. Each router decides which neighbors to include in its router-LSA by looking at the router-LSAs originated by its neighbors, and including in its LSA the minimum set of neighbors necessary to provide a shortest path (if LSAFullness = 1) or two shortest paths (if LSAFullness = 2) between each pair of neighbors. Setting LSAFullness to 3 results in MDR full LSAs. Each (Backup) MDR originates a full LSA that includes all routable neighbors, while each MDR Other originates minimal LSAs. This choice provides routing along nearly min-hop paths. Ogier Expires August 27, 2006 [Page 5] Internet-Draft Advantages of OSPF-MDR February 2006 If LSAFullness = 4, then each router originates a full LSA, which includes all routable neighbors. The above LSA options are interoperable with each other, since they all require the router-LSA to include all fully adjacent neighbors. 2.6. Hello Protocol Hellos are used both for neighbor discovery and for advertising the set of bidirectional neighbors (in state 2-Way or greater), to be used by neighbors to learn 2-hop neighbor information. Differential Hellos are sent every HelloInterval seconds, except when full Hellos are sent, which happens every 2HopRefresh Hellos. The default values for HelloInterval and 2HopRefresh are 2 seconds and 3 Hellos, respectively. Differential Hellos are used to reduce overhead and to allow Hellos to be sent more frequently, for faster reaction to topology changes. Full Hellos are sent less frequently to ensure that all neighbors have current 2-hop neighbor information. The use of differential Hellos allows HelloInterval to be smaller (e.g. 1 second) while making 2HopRefresh larger (e.g. every 6th Hello), without a significant increase in overhead, allowing faster response to topology changes in a highly mobile network. 3. Summary of Advantages of OSPF-MDR One of the advantages of OSPF-MDR is that it keeps the same design philosophy as OSPF, and uses similar techniques for achieving efficiency, scalability, and robustness. Simulations show that this approach does indeed achieve good efficiency, scalability, and robustness in MANETs. The following bullets summarize some of the similarities of OSPF-MDR to OSPF: o The MDR selection algorithm generalizes the DR election algorithm of OSPF, in that both select the same two routers as DR/MDR and Backup DR/MDR in a fully connected MANET. o Both OSPF and OSPF-MDR reduce the number of adjacencies by having each DR/MDR Other form adjacencies with two (Backup) DR/MDR neighbors. In both cases, these two neighbors are advertised in the DR and BDR fields of each Hello. o OSPF-MDR uses the same interface states as OSPF, with the "DR" and "Backup" states implying that the router is an MDR or Backup MDR. o In both OSPF and OSPF-MDR, the choice of DR/MDRs and adjacencies depends only on information obtained from Hellos, and the flooding mechanism is independent of the contents of LSA. Ogier Expires August 27, 2006 [Page 6] Internet-Draft Advantages of OSPF-MDR February 2006 o OSPF (in a broadcast network) and OSPF-MDR both allow a non- adjacent neighbor to be used as a next hop, and both originate LSAs (network-LSA for OSPF) that imply that a router can use a non-adjacent neighbor as a next hop. (Due to the general topology of MANETs, a MANET router must explicitly include non-adjacent neighbors in its router-LSA.) OSPF uses the network-LSA to avoid the n^2 LSA overhead that would otherwise be required if every router of a broadcast network advertised all of its neighbors in its router-LSA. Since a network- LSA cannot be used to describe the general topology of a MANET, the only way to achieve similar scalability in a MANET is to use partial- topology LSAs. The use of min-cost LSAs (described in the overview) allows this scalability while providing min-hop routing (and in some cases min-cost routing). One advantage of min-cost LSAs is that the contents of the LSAs are independent of the flooding mechanism, unlike MPR-based LSAs as discussed in Section 7. 4. Qualitative Comparison of OSPF-MDR to OR/SP This section summarizes some of the qualitative advantages of OSPF- MDR compared to OR/SP. Just as one of the advantages of OSPF-MDR is its similarity to OSPF, one of the disadvantages of OR/SP is its dissimilarity from OSPF. Such a dissimilarity might be justified if it results in improved performance, but simulations do not show such a performance advantage. While OSPF-MDR reduces the number of adjacencies in a manner similar to OSPF (by generalizing the DR/BDR to multihop networks), OR/SP takes a very different approach, which requires the use of modified LSAs to indicate which links are synchronized versus unsynchronized. (OR/SP uses the concept of routable neighbors, first introduced in OSPF-MDR, to allow unsynchronized, non-adjacent neighbors to be included in LSAs.) MPRs are then selecting within the subgraph consisting of synchronized links. This approach has several disadvantages in addition to its dissimilarity from OSPF: o The OR/SP approach requires the modification of router-LSAs, unlike OSPF-MDR. o The selection of adjacencies and relays is not independent of LSAs, unlike OSPF and OSPF-MDR. The flooding mechanism of OSPF- MDR is therefore more modular. o The selection of adjacencies and relays can depend on more than 2-hop neighbor information, thus causing the selection of adjacent neighbors (and thus relays) to be affected by topology changes Ogier Expires August 27, 2006 [Page 7] Internet-Draft Advantages of OSPF-MDR February 2006 that occur several hops away. o The use of router-LSAs can result in slower response to topology changes due to MinLSInterval. The smaller size of Hellos, especially if differential Hellos are used, allows HelloInterval to be smaller than MinLSInterval. MinLSInterval cannot simply be made smaller, since this would result in much more overhead in a dense, mobile network. o Simulations show that this approach results in a larger number of adjacencies than OSPF-MDR (see Section 8). Although OR/SP uses MPRs, the MPRs that it uses are restricted to the subgraph consisting of adjacent, synchronized neighbors. The resulting MPRs therefore do not have the nice properties of MPRs that INRIA has been claiming. In particular, the resulting MPRs do not provide min-hop paths, i.e., they do not achieve a stretch factor of 1, for either routing or flooding. Another disadvantage of the OR approach (with or without smart peering), is the large number of backup ORs (called non-active ORs in [Chandra]). Essentially any neighbor that is not an OR can be a backup OR, in contrast to OSPF-MDR, in which Backup MDRs are selected to provide biconnected coverage. Allowing any neighbor to be a backup relay can limit scalability. (Although jitter is used to try to prevent several backup ORs from forwarding the same LSA, this cannot be completely prevented in dense networks due to MAC delays.) One indication that there are too many backup ORs is evident in Boeing's simulation results of July 2005 [Boeing-Site] (Figure 4.2b), in which the OR approach results in about 3 times as many backup floods as relay floods. Cisco has recently recommended using the parameter values PushbackInterval = 7000 ms and RxmtInterval = 9 seconds, which greatly reduces the number of backup floods (considering that the GTNetS code uses 100% jitter for PushbackInterval). This larger value of PushbackInterval represents a signifcant change since it is not compliant with the last version of the OR draft [Chandra], which requires PushbackInterval to be less than 1/2 RxmtInterval. In contrast, the recommended value of BackupWaitInterval in OSPF-MDR is 500 ms, which provides fast backup flooding while MDRs are being updated. Another advantage of OSPF-MDR is that 2-hop neighbor information is learned from Hellos instead of from LSAs. Not only does this allow faster response to topology changes due to MinLSInterval (as discussed above), but it is also necessary in order to build partial- topology LSAs that provide min-hop routing. For these reasons, OSPF- MDR has used Hellos for 2-hop neighbor information from the beginning. Cisco has stated that they may use Hellos to advertise Ogier Expires August 27, 2006 [Page 8] Internet-Draft Advantages of OSPF-MDR February 2006 2-hop neighbor information, for partial-topology LSAs, but this has not yet been implemented or evaluated. Besides the need to advertise 2-hop neighbor information and Hellos, and the increasing of PushbackInterval to a larger value than was allowed in the last OR draft, there are other indications that the OR proposal is not yet stable. For example, it has recently been decided that ORs (i.e., MPRs) must be synchronized neighbors. However, it is still not clear whether backup ORs must be synchronized. In contrast, the changes to OSPF-MDR in the last year have been relatively minor. 5. Robustness of OSPF-MDR It is valid to ask whether the use of adjacency reduction, i.e., partial-topology adjacencies, results in less robustness than full- topology adjacencies. Although this may be an issue when OSPF-MDR uses uniconnected adjacencies (AdjConnectivity = 1), simulations show that using biconnected adjacencies (AdjConnectivity = 2) achieves the same or better delivery ratio as when full-topology adjacencies are used. Therefore, biconnected adjacencies appear to provide adequate robustness. Uniconnected adjacencies are provided as an option to support larger networks, where the additional overhead required for biconnected adjacencies may worsen performance. This section presents simulation results comparing three modes of OSPF-MDR: (1) full-topology adjacencies and LSAs, (2) uniconnected adjacencies with min-cost LSAs, and (3) biconnected adjacencies with min-cost LSAs. These modes correspond to LSAFullness = 0, 1, and 2, respectively. More extensive simulation results will be presented by Boeing [Boeing-Site]. The GTNetS code was used to simulate two 50-node scenarios, one with range = 250 m (dense) and one with range = 125 m (sparse). A square grid was used with length 500 m, and the maximum node speed was 10 m/s. Detailed results and parameter values are given in the appendix of [Ogier06b]. The following two tables gives the overhead and delivery ratio for the three modes of OSPF-MDR, first for the dense network and then for the sparse network. Results for 50 nodes and range 250 m: Protocol Mode Overhead Delivery Ratio ------------- ----------- ------------- Full-topology adj and LSAs 860.46 kbps 0.956 Uniconnected adj, min-cost LSAs 117.36 kbps 0.954 Biconnected adj, min-cost LSAs 160.09 kbps 0.968 Ogier Expires August 27, 2006 [Page 9] Internet-Draft Advantages of OSPF-MDR February 2006 Results for 50 nodes and range 125 m: Protocol Mode Overhead Delivery Ratio ------------- ----------- ------------- Full-topology adj and LSAs 690.33 kbps 0.731 Uniconnected adj, min-cost LSAs 271.72 kbps 0.734 Biconnected adj, min-cost LSAs 431.15 kbps 0.746 The above results show that uniconnected adjacencies achieve about the same delivery ratio as the full-topology mode, while biconnected adjacencies achieve a significantly better delivery ratio. There are three possible reasons why biconnected adjacencies with min-cost LSAs achieve a better delivery ratio than the full-topology mode: (1) the lower overhead means more bandwidth is available for data traffic, (2) the use of routable neighbors means one does not have to wait for database synchronization when a new link comes up, and (3) min-cost LSAs represent the topology more accurately, since they are originated less often than full LSAs and therefore are not delayed as often due to MinLSInterval. 6. Need for Adjacency Reduction It has been suggested that using partial-topology LSAs with full- topology adjacencies might achieve better robustness without creating too much overhead. To test this, I used GTNetS to compare full- topology adjacencies to uniconnected adjacencies, in both cases using MDR full LSAs (since MDR full LSAs were easy to implement in a consistent manner for both partial-topology and full-topology adjacencies). The results are summarized below for 100 nodes, with range equal to 250 m (dense) and 125 m (sparse). A square grid was used with width 500m, and maximum node speed was 10 m/s. Detailed results and parameter values are given in the appendix of [Ogier06b]. Results for 100 nodes with range 250 m: Protocol Mode Overhead Delivery Ratio ------------- ----------- -------------- Partial LSAs, 1-connected adj: 384.65 kbps 0.959 Partial LSAs, full adj: 6515.54 kbps 0.081 Results for 100 nodes with range 125 m: Protocol Mode Overhead Delivery Ratio ------------- ----------- -------------- Partial LSAs, 1-connected adj: 1175.73 kbps 0.758 Partial LSAs, full adj: 4244.74 kbps 0.749 These results show that full-topology adjacencies result in much more overhead, thus preventing scalability. For range 250 m, full- topology adjacencies caused about 17 times as much overhead and Ogier Expires August 27, 2006 [Page 10] Internet-Draft Advantages of OSPF-MDR February 2006 reduced delivery ratio from 95.9% to 8.1% by consuming almost all of the bandwidth. To achieve scalability, it is necessary to use *both* partial-topology adjacencies and partial-topology LSAs. 7. Proposals to Use MPRs Philippe Jacquet of INRIA has suggested that MPRs should be used for flooding and for selection of adjacencies (see Jacquet's posts to [OSPF-MANET] starting 12/5/2005), because MPR flooding has some desirable properties and is more mature than the CDS approach. For example, MPRs achieve flooding along min-hop paths, i.e., they achieve a stretch factor of 1. INRIA proposes that each router should become adjacent (synchronized) with its selected MPRs and its MPR selectors. In addition, to ensure the adjacency subgraph is connected, one router must become adjacent with all of its neighbors. However, nobody has bothered to implement this solution in GTNetS to compare to the other approaches. Cisco considered this solution briefly but decided instead to go with smart peering (see post to [OSPF-MANET] on 12/12/2005). The main problem with the approach of forming an adjacency with each MPR neighbor is that it results in a very large rate of new adjacencies, as shown by simulation results that I posted to [OSPF- MANET] on 2/8/2006. These results show that in a dense 100-node network (with range equal to 0.5 times the width of the square grid), using MPRs result in 13.3 times as many new adjacencies per second as 1-conected MDRs. (A GTNetS simulation shows that the DD overhead for 1-connected MDRs in this scenario is 76.75 kbps, which implies a DD overhead of 13.3 * 76.75 = 1,020 kbps for MPRs.) The reason is that MPRs must change frequently in order to maintain the stretch factor of 1. The much smaller rate of new adjacencies is an important advantage of OSPF-MDR. Even if the approach is used in which each router forms an adjacency with each MPR neighbor, the first hop of a path based on MPRs need not be an MPR or MPR selector and therefore may not be synchronized. Therefore, some method of ensuring the neighbor is indirectly synchronized (e.g., routable neighbors) would still be needed. The remainder of this section will discuss other possible uses of MPRs. Cisco uses MPRs in their OR/SP proposal, in which MPRs are called ORs. However, the MPRs used by OR/SP are restricted to the subgraph consisting of adjacent, synchronized neighbors (as mentioned above). Therefore, these MPRs are not the same ones that INRIA is promoting. For example, they do not achieve a stretch factor of 1. Therefore, the desirable properties that INRIA claims for MPRs may not apply to the MPRs used in OR/SP. However, since OR/SP is Ogier Expires August 27, 2006 [Page 11] Internet-Draft Advantages of OSPF-MDR February 2006 implemented in GTNetS, a direct comparison can be made between OR/SP and OSPF-MDR. Another use of MPRs is to define a CDS based on MPRs, and use this MPR-based CDS for flooding [INRIA02]. In fact, an extension of OSPF- MDR has recently been proposed [Ogier06a] which allows the option of using MPRs to select the MDRs (thus forming an MPR-based CDS). This has not yet been implemented in GTNetS, but abstract simulations indicate that this results in a higher rate of new adjacencies. Additional studies can be performed to determine whether the use of this option will improve performance sufficiently to justify the additional complexity of having to select and advertise MPRs. MPR-based LSAs are also possible, but this has several disadvantages compared to the min-cost LSAs of OSPF-MDR (see my post to [OSPF- MANET] on 1/9/2006). For example, min-cost LSAs are independent of the flooding mechanism, whereas MPR-based LSAs are not, so if one wanted to provide min-cost routing with respect to a metric, the contents of router-LSAs could not be selected independently of MPRs. In summary, no MPR-based extension of OSPF has yet been shown to perform better than OSPF-MDR in a detailed simulation environment such as GTNetS. (Boeing is conducting a simulation comparison between OSPF-MDR and OR/SP and will present results soon.) OSPF-MDR can allow the option of using an MPR-based CDS, but this adds complexity and is likely to result in increased overhead. OSPF-MDR performs well using only MDRs (which generalize the DR of OSPF), so to keep the extension as simple as possible, it may be best not to introduce MPRs. 8. Simulation Comparison to OR/SP This section presents some limited simulation results comparing OSPF- MDR to OR/SP in mobile networks with 100 nodes. A more extensive simulation comparison will be reported by Boeing [Boeing-Site]. To allow simulation of networks with 100 nodes, partial-topology LSAs were used for both OSPF-MDR and OR/SP. For OR/SP, unsynchronized adjacencies (UnsynchAdj) were not enabled, which results in "minimal" LSAs that include only synchronized neighbors. (This does not affect the core flooding mechanism, which depends only on the synchronized neighbors that are included in LSAs.) The use of OR/SP with minimal LSAs provides a lower bound Therefore, using "minimal" LSAs results in the minimum overhead of any choice of LSAs which include the required synchronized neighbors. This is the minimum overhead required to provide minimal (suboptimal) routing. Ogier Expires August 27, 2006 [Page 12] Internet-Draft Advantages of OSPF-MDR February 2006 I was curious to see what this minimum overhead is for OR/SP without UnsynchAdj, and to compare it to the overhead for OSPF-MDR with minimal LSAs and min-cost LSAs. (Note, however, that OR/SP without UnsynchAdj allows only synchronized neighbors to be selected as a next hop in SPF, unlike OSPF-MDR which allows any routable neighbor as a next hop. Therefore, although it is fair to compare the overhead, it would not be fair to compare path length or delivery ratio.) The simulation results presented below are only for one challenging scenario: 100 nodes with range 250 and maximum node speed 10 m/s. For OR/SP, I used the parameter values recommended by Cisco: RxmtInterval=9 AckInterval=500 PushbackInterval=7000. The following table summarizes the results, comparing total overhead, average number of adjacencies per node, and adjacency change rate. (Delivery ratio is also included but should not be compared.) Detailed results and parameter values are given in the appendix of [Ogier06b]. Overhead Adj/node Adj changes/node/s Ratio ---------------------------------------------- MDR w/ minimal LSAs 277.22 kbps 2.57 0.03 0.960 MDR w/ min-cost LSAs 352.35 kbps 2.60 0.03 0.962 OR/SP w/o UnsynchAdj 856.17 kbps 9.81 0.12 0.955 These results show that the minimal (lower bound) overhead for OR/SP is more than three times as large as as the minimal overhead for OSPF-MDR, and is more than twice as large as the overhead of OSPF-MDR using min-cost LSAs. Also, the number of adjacencies and the rate of new adjacencies is almost four times as large for OR/SP than for OSPF-MDR, which contributes to the larger overhead. 9. Conclusion OSPF-MDR extends OSPF to MANETs in a natural way, keeping the same design philosophy as OSPF, and using similar techniques to achieve scalability and robustness, by generalizing the notion of a DR and Backup DR. Simulations show that this approach also results in excellent performance, and can scale to more than 100 nodes. Unless another approach can be shown to perform significantly better than OSPF-MDR, this approach appears to be the best choice for extending OSPF to support MANETs. Ogier Expires August 27, 2006 [Page 13] Internet-Draft Advantages of OSPF-MDR February 2006 References [OSPF-MDR] R. Ogier and P. Spagnolo. "MANET Extension of OSPF using CDS Flooding", draft-ogier-manet-ospf-extension-06.txt (work in progress), December 2005. [Ogier06a] R. Ogier. "Extension of OSPF-MDR to Allow Option of Using MPRs", draft-ogier-manet-ospf-mdr-ext-00.txt (work in progress), January 2006. [Ogier06b] R. Ogier. "Advantages of OSPF-MDR (with details)", http://home.earthlink.net/~ogier. [Boeing-Site] Boeing's OSPF MANET website. http://hipserver.mct.phantomworks.org/ietf/ospf/ [OSPF-MANET] IETF mailing list archive for OSPF-MANET. http://www1.ietf.org/mail-archive/web/ospf- manet/current/index.html [Chandra] M. Chandra. "Extensions to OSPF to Support Mobile Ad Hoc Networking", draft-chandra-ospf-manet-ext-03.txt (work in progress), April 2005. [Roy] A. Roy (ed). "Adjacency Reduction in OSPF using SPT Reachability", draft-roy-ospf-smart-peering-01.txt (work in progress), November 2005. Author's Address Richard G. Ogier Email: rich.ogier@earthlink.net Disclaimer of Validity This document and the information contained herein are provided on an "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. Copyright Statement Copyright (C) The Internet Society (2006). This document is subject to the rights, licenses and restrictions contained in BCP 78, and except as set forth therein, the authors retain all their rights. Ogier Expires August 27, 2006 [Page 14]