Mobile Ad Hoc and OSPF Working Groups R. Ogier Internet-Draft January 11, 2005 MANET Extension of OSPF using CDS Flooding draft-ogier-manet-ospf-extension-02.txt Status of this Memo This document is an Internet-Draft and is subject to all provisions of section 3 of RFC 3667. 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 become aware will be disclosed, in accordance with RFC 3668. 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/ietf/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 July 11, 2005. Copyright Notice Copyright (C) The Internet Society (2005). Abstract This document describes and evaluates a family of interoperable flooding methods for mobile ad-hoc networks, which use a distributed algorithm for computing a connected dominating set (CDS) based on 2-hop neighbor information. The different methods are interoperable because the CDS computed by each method contains a "minimal" CDS, which is computed by the most efficient of the described methods. Simulations are presented to compare the different methods with respect to CDS size and average stretch factor. This document also describes how the proposed CDS algorithms can be used to achieve reliable flooding of LSAs in OSPF. In this context, the CDS nodes generalize the concept of a Designated Router to a multi-hop network. Ogier Expires July 11, 2005 [Page 1] Internet-Draft MANET Extension of OSPF January 2005 1. Introduction Flooding is useful in mobile ad-hoc networks for the dissemination of topology information (in link-state routing protocols) and other information, and for route discovery (in reactive routing protocols). Because mobile networks typically have less bandwidth than wired networks, an efficient flooding mechanism is needed, in which only a relatively small subset of nodes forward a given flooded packet. Once choice for such a subset of nodes is a connected dominating set (CDS). This document presents distributed CDS algorithms in which each node decides whether it is in the CDS based on 2-hop neighbor information. This allows fast reaction to topology changes, since the decision to be in the CDS does not depend on information that must be propagated across the network. We present a family of distributed CDS algorithms, which are related and interoperable since the CDS computed by each algorithm contains a minimal CDS, called the Essential CDS, which is computed by the most efficient of the distributed algorithms. Thus, a CDS will be obtained as long as each node runs any algorithm in the family. More generally, any CDS algorithm can be used as long as it results in the node selecting itself whenever it belongs to the Essential CDS. The two performance measures that we consider are CDS size and stretch factor, defined as the average length of a min-hop path between a source and a destination using only CDS nodes as intermediate nodes, divided by the average min-hop path length using any nodes. As we show using simulations, some of the CDS algorithms achieve a smaller stretch factor at the cost of a larger CDS. A small stretch factor (close to 1) is desirable because each flooded packet travels fewer hops on average. In addition, a small stretch factor is beneficial if the CDS is used for unicast routing, i.e., if unicast routes are constrained to use only CDS nodes as intermediate nodes. This would be the case if only links adjacent to CDS nodes are disseminated in LSAs, as described in Section 5. Thus, a small stretch factor allows overhead to be reduced dramatically by allowing the dissemination of a relatively small portion of the full topology. This document also describes how the proposed CDS methods can be used to achieve reliable flooding of LSAs in OSPF. In this context, the CDS nodes generalize the concept of a Designated Router (DR) to MANETs, and the proposed CDS selection algorithms generalize OSPF's algorithm for selecting a DR and Backup DR. Therefore, we extend the term "Designated Router" to refer to a CDS node, and thus a MANET can Ogier Expires July 11, 2005 [Page 2] Internet-Draft MANET Extension of OSPF January 2005 have several DRs. Much of the functionality of a DR in legacy OSPF [RFC2328, RFC2740] remains the same for a generalized DR. For example, adjacencies are formed only between each DR/Backup DR and its neighbors, and only DRs (and possibly Backup DRs) forward LSAs in the flooding process. Each CDS algorithm has a persistent and a non-persistent version. In the persistent versions, each (generalized) DR remains a DR until the existence of higher priority neighboring DRs make it redundant, as in legacy OSPF. In the non-persistent versions, DRs are recalculated whenever the 2-hop neighborhood changes, regardless of which nodes are currently DRs. The persistent versions have the advantage that DRs do not change as often, and are therefore recommended for reliable flooding, since an adjacency must be formed (with database synchronization) between each new DR and some or all of its neighbors. The non-persistent versions are useful for periodic, unreliable flooding, which does not require database synchronization. To obtain the 2-hop neighbor information required for DR selection in MANETs, this document recommends modifying OSPF Hello packets to indicate which neighbors are 2-way versus 1-way. In addition, overhead can be reduced significantly by using differential Hellos, which report only changes in neighbor status. An adaptation of the differential Hellos of TBRPF [RFC3684] can be used for this purpose. Section 2 summarizes the features of the solution proposed in this document. Section 3 discusses the relative benefits of CDS flooding versus MPR flooding. Section 4 describes the proposed family of CDS algorithms. Section 5 specifies which neighbors should be adjacent, and which should be included in LSAs. Section 6 describes the flooding procedure, and Sections 7 and 8 describe the procedures for retransmitting LSAs and sending Link State acknowledgments, respectively. Section 9 proposes three enhancements for reducing overhead, and Section 10 presents simulation results comparing different algorithms in the proposed family of CDS algorithms. 2. Summary of Features of the Proposed Solution The following bullets summarize the main features of the solution presented in this document: - The document presents a family of interoperable CDS algorithms, which allow a tradeoff between path optimality and CDS size. Simulation results are presented to show this tradeoff. - The CDS algorithms are based only on 2-hop neighbor information, to provide fast convergence following topology changes. Ogier Expires July 11, 2005 [Page 3] Internet-Draft MANET Extension of OSPF January 2005 - The CDS algorithms are interoperable because the CDS computed by each algorithm contains a minimal, source-independent CDS called the "Essential" CDS. The Essential CDS can be computed in O(d^2) time, where d is the number of neighbors. - The Essential CDS is very scalable, as shown by the simulation results in Section 10. In a 300 node network with average degree 64 and diameter 5, the Essential CDS consists of only 23 (8%) of the nodes on average. - The Essential CDS provides a minimal, source-independent set of relays for flooding LSAs (or other flooded packets). The flooding procedure also allows source-dependent flooding (using previous-hop information) as an option, if it is desired to flood packets along min-hop paths. - For improved CDS stability, each algorithm in the family has a "persistent" version, in which a router in the CDS remains in the CDS until it becomes redundant. - Generalizes the OSPF concept of a Designated Router (DR) and Backup DR to MANETs. The set of DRs forms a CDS, and the set of DRs and Backup DRs forms a biconnected CDS for robustness. When applied to a broadcast network, the persistent version of each algorithm computes the same DR and Backup DR as OSPF. - Adjacencies are formed only between CDS nodes (DRs and Backup DRs) and their neighbors, as in legacy OSPF. - Provides a flexible choice of which neighbors to include in LSAs, from a minimum set of neighbors adjacent to DRs and Backup DRs, to the full network topology. 3. Comparison of CDS and MPR Flooding Two flooding approaches being considered for mobile ad-hoc networks are multipoint relays (MPRs) and a connected dominating set (CDS). The main difference is that MPRs are directional, so that the set of MPRs that forward a given flooded packet depends on the originating node, whereas if a CDS is used, then all CDS nodes forward each flooded packet. In addition, flooding via MPRs results in each packet following a min-hop path, whereas a CDS need not provide min- hop paths. In the discussion below, for MPR flooding we assume that each node selects a subset of its neighbors to be MPRs based on 2-hop neighbor information, as in [RFC3626]. Thus CDS nodes are "self selected" Ogier Expires July 11, 2005 [Page 4] Internet-Draft MANET Extension of OSPF January 2005 whereas MPRs are "neighbor selected". It is also possible for MPRs to be self selected, and for CDS nodes to be determined based on neighbor-selected MPRs as in [Adjih02]. In the solution presented in this document, each node that selects itself as a CDS node also selects a set of "dependent" neighbors, which are analogous to MPR selectors. Thus, we present a flexible solution that includes both self-selected (source-independent) CDS nodes and self-selected MPRs in a unified manner. CDS-based flooding has the following advantages when compared to (neighbor-selected) MPR-based flooding: - A node need not know the previous hop of a flooded packet in deciding whether to forward it. - The previous-hop independence also simplifies reliable flooding, since a CDS clearly defines the set of nodes that are responsible for relaying LSAs and performing database synchronization with neighbors. - In the above sense, a CDS node is a natural generalization of OSPF's Designated Router to multi-hop networks. - Each node decides whether it is in the CDS based only on 2-hop neighbor information, allowing faster recovery from link failures than if each node must inform its neighbors of the selection (as with MPRs). - A CDS need not (but can) provide min-hop paths (unlike MPRs), and therefore can trade off path optimality to reduce the number of nodes that relay each flooded packet. - A CDS node can determine not only the previous-hop neighbors that depend on it for relaying LSAs, but also the next-hop neighbors that must receive the LSAs. This is important for reliable flooding, since an ACK must be received from each such next-hop neighbor. Since MPRs provide min-hop paths and are neighbor selected, they provide the following advantage: - If min-hop paths are required, MPRs may result in a smaller number of transmissions, since the neighbor selection of MPRs makes it easier to identify and eliminate redundant MPRs. Ogier Expires July 11, 2005 [Page 5] Internet-Draft MANET Extension of OSPF January 2005 4. Proposed Family of CDS Algorithms In this section, we describe a family of distributed CDS algorithms based on 2-hop neighbor information, which can be obtained from Hellos that are modified to indicate which neighbors are 2-way. The algorithms are first presented assuming each node has a single MANET interface; the extension to multiple interfaces is described in Section 4.4. By 2-hop neighbor information, we mean that each node knows the set (denoted N) of its 2-way (1-hop) neighbors and, for each 2-way neighbor j, the set (denoted N_j) of node j's 2-way neighbors. In addition, we assume that each node knows the Router Priority (RtrPri) and Router ID (RID) of each of its neighbors, as in legacy OSPF. These values will be used by the CDS algorithms in a way that generalizes OSPF's algorithms for selecting a Designated Router. As noted above, the term Designated Router (DR) will be used to mean a CDS node, thus generalizing the OSPF concept of a DR. Similarly, the term Backup DR (BDR) will be used to denote a redundant CDS node, in a way that generalizes the OSPF concept of a Backup DR. When we say that the pair (RtrPri, RID) is larger for node i than for node j, we mean that the pair for node i is lexicographically greater than the pair for node j, i.e., either the RtrPri is larger for node i than for node j, or the RtrPri is the same for both nodes and the RID is larger for node i than for node j. We note that a node can select its Router Priority based on any criteria, including the following: - node degree: higher priority for larger degree - neighbor stability (average lifetime of neighbors): higher priority for higher stability - bandwidth capacity of node: higher priority for higher bandwidth - battery life: low priority if battery life is low - willingness to be a relay The simulation results presented in Section 10 will compare the CDS algorithms when RtrPri is equal to node degree, versus using the same RtrPri for all nodes. For each CDS algorithm, we first describe the non-persistent version of the algorithm, in which each node runs the algorithm to decide whether to select itself as a DR (or a Backup DR) whenever a change Ogier Expires July 11, 2005 [Page 6] Internet-Draft MANET Extension of OSPF January 2005 occurs to its 2-hop neighborhood, independent of the current DR status of itself or its neighbors. We then describe how to modify the algorithm to obtain its persistent version, in which a DR continues to be a DR until it becomes redundant due to the existence of neighboring DR's with larger values of (RtrPri, RID). 4.1 The Essential CDS Algorithm We first describe the Essential CDS algorithm, which computes the smallest CDS (called the Essential CDS) of the algorithms to be presented. The CDS computed by each of the other algorithms presented in this document will contain the Essential CDS. the Essential CDS MUST select itself as a DR. In the following description, node i denotes the node performing the calculation. Essential CDS Algorithm (Non-Persistent Version) Phase 1 (DR Selection) 1.1. If node i has a larger value of (RtrPri, RID) than any of its neighbors, then node i selects itself as a DR. 1.2. Else, let j be the neighbor of node i that has the largest value of (RtrPri, RID). If there exists a path (with one or more hops, based on node i's 2-hop neighbor information) from node j to each other neighbor of node i, using only intermediate nodes that are neighbors of node i and that have a larger value of (RtrPri, RID) than node i, then node i does not select itself as a DR; otherwise node i selects itself as a DR. Phase 2 (Backup DR Selection) 2. If node i does not select itself as a DR in Phase 1, and if there exist two node-disjoint paths from node j to each other neighbor of node i, using only intermediate nodes that are neighbors of node i and that have a larger value of (RtrPri, RID) than node i, then node i does not select itself as a Backup DR; otherwise node i selects itself as a Backup DR. The selected DRs have two purposes: (1) to provide a minimal set of relays for flooding LSAs, and (2) to provide a minimal set of adjacencies for routing (not necessarily along min-hop paths). The selected Backup DRs also have two purposes: (1) to provide backup relays to retransmit flooded LSAs when flooding by DRs does not succeed, and (2) to provide additional adjacencies for routing, which provide redundant routes. If Backup DRs are not desired, then Ogier Expires July 11, 2005 [Page 7] Internet-Draft MANET Extension of OSPF January 2005 Phase 2 can be omitted. The set of DRs computed by Phase 1 forms a CDS, and the union of the DRs and Backup DRs computed in both phases forms a redundant CDS with the following properties: each non-CDS node will have at least two neighbors in the CDS, and the graph consisting of all links adjacent to CDS nodes will be biconnected. Note that there may be fewer Backup DRs than DRs, since the DRs themselves may already provide some redundancy. The persistent version of the above algorithm is similar to the non- persistent version given above, except that existing DRs are given higher priority than existing Backup DRs, which are given higher priority than other nodes. To describe the persistent version concisely, we introduce the variable DRLevel, which is equal to 2 if the node is a DR, 1 if the node is a Backup DR, and 0 otherwise. The persistent version of the above algorithm is obtained simply by replacing each occurrence of (RtrPri, RID) with (DRLevel, RtrPri, RID). Thus, a node that is currently a DR is given the highest priority for remaining a DR. The persistent version of the Essential CDS algorithm is a true generalization of OSPF's algorithm for selecting a DR and Backup DR. That is, in a single-hop network (where every node is a neighbor of every other node), both algorithms will select the same nodes as DR and Backup DR. This is a desirable property, since we are extending OSPF. Note that in the above CDS algorithm (and the others presented below), intermediate nodes are required to be neighbors of node i. With 2-hop neighbor information, it is possible to drop this requirement (and allow nodes that are two hops away to be intermediate nodes), to potentially obtain a smaller CDS. However, this would require node i to know the Router Priority of each 2-hop neighbor, which could be achieved by modifying Hellos to include the Router Priority of each neighbor. This can also result in slower response to topology changes, since it may take longer to realize that a 2-hop neighbor is no longer a DR. Finally, simulation results indicate that dropping this requirement reduces the average CDS size only slightly. The Essential CDS algorithm can be implemented in O(d^2) time, where d is the number of neighbors. Step 1.2 can be implemented using a breadth-first-search (BFS) algorithm to compute min-hop paths from node j to all other neighbor of node i, modified to allow a node as an intermediate node only if its value of (RtrPri, RID) [or (DRLevel, RtrPri, RID) for the persistent version] is larger than that of node i. Ogier Expires July 11, 2005 [Page 8] Internet-Draft MANET Extension of OSPF January 2005 The BFS algorithm for Step 1.2 of the non-persistent version is as follows. The algorithm uses a FIFO queue so that all nodes 1 hop from node j are processed first, then 2 hops, etc. When the BFS algorithm terminates hops(u), for each neighbor node u of node i, will be equal to the minimum number of hops from node j to node u, using only intermediate nodes that are neighbors of node i and that have a larger value of (RtrPri, RID) than node i. a. Set hops(u) = infinity for all neighbors u other than j. b. Set hops(j) = 0. c. Add node j to the queue. d. While the queue is nonempty: Remove the node at the head of the queue; call it node u. For each neighbor v of node u that is a neighbor of node i: If hops(u) + 1 < hops(v), then set hops(v) = hops(u) + 1, and set pred(v) = u. If node u has a larger value of (RtrPri, RID) than node i, then add node u to the tail of the queue. e. If hops(u) is finite for all neighbors u of node i, then node i does not select itself as a DR; otherwise, node i selects itself as a DR. Phase 2 of the algorithm can be implemented using a modification of the algorithm [Suurballe84] to find disjoint paths. However, the following algorithm is simpler, although it it imposes a more restrictive condition on the two disjoint paths (that they both have the same length) and therefore may result in a larger number of BDRs. (Note that such an algorithm is compliant with the specification, since a node that would be a BDR using the Essential CDS algorithm will also be a BDR using this algorithm.) a. Let node j and d(u) be as computed in Phase 1. b. Set BDR_flag = 0. c. For each node u that is a neighbor of node i and is *not* a neighbor of j: If there exist two neighbors v and w of node u that are neighbors of node i, have a larger value of (RtrPri, RID) than node i, and satisfy d(v) = d(w) = d(u) - 1, then do nothing; otherwise, set BDR_flag = 1. d. For each node u that is a neighbor of node i and *is* a neighbor of j: If there exists a neighbor v of node u that is a neighbor of node i, and has a larger value of (RtrPri, RID) than node i, then do nothing; otherwise, set BDR_flag = 1. e. If BDR_flag = 1, node i selects itself as a BDR. Step d above ensures that BDRs not only provide alternate relays to reach 2-hop neighbors of node j, but also to reach 1-hop neighbors Ogier Expires July 11, 2005 [Page 9] Internet-Draft MANET Extension of OSPF January 2005 of node j, which is important since the link from node j to such a neighbor can break. The Essential CDS algorithm computes a minimal CDS (the DRs) and a minimal redundant (biconnected) CDS (the DRs and BDRs). However, it may be desirable to use a CDS algorithm that computes a larger CDS, for example, to obtain a CDS that achieves a smaller stretch factor (defined above). Such an algorithm will be interoperable with the Essential CDS algorithm as long as it computes a CDS that contains the Essential CDS, i.e., as long as each node that is in the Essential CDS selects itself as a DR. Thus, to ensure interoperability, each node in the Essential CDS MUST select itself as a DR. However, a node that is not in the Essential CDS MAY select itself as DR. The next section describes two subfamilies of distributed CDS algorithms, each of which computes a CDS that contains the Essential CDS. As shown in simulations results presented below, some of these algorithms achieve a smaller stretch factor at the cost of a larger CDS. 4.2. Max-Priority-Neighbor (MPN) CDS Algorithm Family In the Essential CDS algorithm, node i selects itself as a DR if it cannot find a path from the neighbor j with maximum value of (RtrPri, RID) to each other neighbor, using only intermediate nodes with a larger value of (RtrPri, RID) than node i. The MPN CDS algorithm family is similar, but requires that each such path be at most h1 hops long, where the parameter h1 is an integer greater than or equal to 2. By choosing h1 to be small, a larger CDS is obtained, but hopefully the CDS has a smaller stretch factor and can thus be used to provide shorter paths. The MPN CDS algorithm uses a second parameter h2 for computing Backup DRs in Phase 2. Phase 2 requires that there exist two disjoint paths from neighbor j to each other neighbor, with each path having at most h2 hops. It is possible for h2 to be either larger or smaller than h1. The MPN CDS algorithm with parameters h1 and h2 will be denoted MPN(h1, h2). MPN(h1, h2) CDS Algorithm (Non-Persistent Version) Phase 1 (DR Selection) 1.1. If node i has a larger value of (RtrPri, RID) than any of its neighbors, then node i selects itself as a DR. 1.2. Else, let j denote the neighbor of node i that has the largest Ogier Expires July 11, 2005 [Page 10] Internet-Draft MANET Extension of OSPF January 2005 value of (RtrPri, RID). If there exists a path with at most h1 hops (based on node i's 2-hop neighbor information) from node j to each other neighbor of node i, using only intermediate nodes that are neighbors of node i and that have a larger value of (RtrPri, RID) than node i, then node i does not select itself as a DR; otherwise node i selects itself as a DR. Phase 2 (Backup DR Selection) 2. If node i does not select itself as a DR in Phase 1, and if there exist two node-disjoint paths from node j to each other neighbor of node i, each with at most h2 hops, using only intermediate nodes that are neighbors of node i and that have a larger value of (RtrPri, RID) than node i, then node i does not select itself as a Backup DR; otherwise node i selects itself as a Backup DR. As with the Essential CDS algorithm, the persistent version of the MPN algorithm can be obtained simply by replacing each occurrence of (RtrPri, RID) with (DRLevel, RtrPri, RID). It is clear that the CDS computed by the MPN algorithm contains the CDS computed by the Essential CDS algorithm, since if Phase 1 of the MPN algorithm does not result in node i selecting itself as a DR, then a path exists between node j and each other neighbor of node i, and thus Phase 1 of the Essential CDS algorithm will not result in node i selecting itself as a DR. The MPN CDS algorithm can be implemented in O(d^2) time. The implementation is the same as that described for the Essential CDS algorithm, the only difference being that the computed distances d(u), for each neighbor u, must be at most h1 for Phase 1, and at most h2 for Phase 2, for node i not to select itself as a DR (Phase 1) or BDR (Phase 2). 4.3. All-Neighbor-Pairs (ANP) CDS Algorithm Family The ANP CDS algorithm family is similar to the MPN CDS algorithm family, with the same parameters h1 and h2, but the requirements imposed on the existence of paths from the neighbor j (with maximum value of (RtrPri, RID)) to all other neighbors, are now imposed on the existence of paths from *every* neighbor of node i to all other neighbors. As a result, the CDS computed by ANP(h1, h2) contains (and is usually larger than) the CDS computed by MPN(h1, h2). Although ANP computes a larger CDS than MPN, the benefit is that it is more likely to have a smaller stretch factor. In fact, if either h1 = 2 or h2 = 2, then ANP is guaranteed to achieve a stretch factor of 1, i.e., the CDS consisting of DRs and BDRs will provide min-hop paths between any pair of nodes. Selecting h1 = 3 and h2 = 2 Ogier Expires July 11, 2005 [Page 11] Internet-Draft MANET Extension of OSPF January 2005 results in a relatively small set of DRs (resulting in a small flooding overhead), while providing min-hop paths via the adjacencies induced by the BDRs. Each node running the ANP algorithm maintains a list of Dependent Neighbors. The use of Dependent Neighbors is described in Sections 5 and 6. For the Essential CDS and MPN CDS algorithms, all neighbors are Dependent Neighbors. ANP(h1, h2) CDS Algorithm (Non-Persistent Version) Phase 1 (DR Selection) 1.1. If node i has a larger value of (RtrPri, RID) than any of its neighbors, then node i selects itself as a DR, adds all neighbors to the list of Dependent Neighbors, and exits. 1.2. Initialize the list of Dependent Neighbors to be empty. For each neighbor node j, if there exists a path with at most h1 hops (based on node i's 2-hop neighbor information) from neighbor j to each other neighbor of node i, using only intermediate nodes that are neighbors of node i and that have a larger value of (RtrPri, RID) than node i, then do not add node j to the list of Dependent Neighbors; otherwise, add node j to the list. 1.3. If the list of Dependent Neighbors is not empty, then node i selects itself as a DR. Phase 2 (Backup DR Selection) 2. If node i does not select itself as a DR in Phase 1, then perform the following steps: 2.1. Initialize the list of Dependent Neighbors to be empty. For each neighbor node j, if there exist two node-disjoint paths from neighbor j to each other neighbor of node i, each with at most h2 hops, using only intermediate nodes that are neighbors of node i and that have a larger value of (RtrPri, RID) than node i, then do not add node j to the list of Dependent Neighbors; otherwise, add node j to the list. 2.2. If the list of Dependent Neighbors is not empty, then node i selects itself as a Backup DR. As with the MPN algorithm, the persistent version of the ANP algorithm can be obtained simply by replacing each occurrence of (RtrPri, RID) with (DRLevel, RtrPri, RID). Ogier Expires July 11, 2005 [Page 12] Internet-Draft MANET Extension of OSPF January 2005 The ANP CDS algorithm can be implemented in O(d^3) time. The implementation is the same as for the MPN algorithm, except that BFS must be run for each neighbor of node i, instead of a single neighbor. Note that O(d^2) time is required just to cycle through all neighbors' neighbors. Given this and the fact that processor speeds are much faster than when RFC 2328 was first published, a time complexity of O(d^3) is quite reasonable, especially since the real bottleneck for MANETs is bandwidth, not processing. Also, note that the ANP algorithm is optional. The following important relationship exists between the set of DRs computed by ANP and MPN (for the same value of h1): A router is selected as a DR by the MPN algorithm if and only if either it has a larger (RtrPri, RID) than all of its neighbors, or the neighbor node j with the largest value of (RtrPri, RID) is selected as a Dependent Neighbor by the ANP algorithm. As a result, a node that runs the ANP algorithm can quickly determine whether it belongs to the smaller CDS computed by the MPN algorithm, and can choose to relay LSAs only if it belongs to the smaller CDS (thus reducing overhead). 4.4. Multiple Interfaces The above descriptions of the CDS algorithms assume that each router has a single MANET interface. If a router has multiple MANET interfaces, each router sends and receives Hellos (modified to specify which neighbors are 2-way) on each interface. Using the 2-hop neighbor information obtained from Hellos received on all interfaces, node i constructs the set N_j of neighbors of each neighbor node j, via any interface that is common to both nodes i and j. The above CDS algorithms are then applied using this 2-hop neighbor information based on all interfaces. If a MANET router also has one or more non-MANET interfaces, then the router MAY also use 2-hop neighbor information obtained from LSAs originating from neighboring routers attached to its non-MANET interfaces. For example, if two neighboring MANET routers are also attached to the same broadcast network, then it may not be necessary for both routers to forward LSAs from the MANET to the broadcast network, and vice versa. (Note that we are assuming the MANET and the broadcast network belong to the same area.) 4.5. Relation of the Proposed CDS Algorithms to Other Algorithms In TBRPF [RFC3684], the set of all nodes that have at least one "reported neighbor" (and therefore forward link-state updates originating from other nodes) is a CDS, which is the same as the CDS computed by Phase 1 of the ANP algorithm with h1 = 2 and RtrPri the same for all nodes. Ogier Expires July 11, 2005 [Page 13] Internet-Draft MANET Extension of OSPF January 2005 Phase 1 of the ANP algorithm with h1 = 2 is also equivalent to the CDS algorithm of [Lin03] if RtrPri is equal to the node degree, except that the latter algorithm includes a second phase in which a node removes itself from the CDS if its neighbors are covered and connected by its CDS neighbors with larger IDs (or smaller IDs in this document, since we give preference to larger ID routers). However, we do not recommend this second phase for the following reasons: (1) simulations show that it results in only a slightly smaller CDS, at most one node smaller in a network of 100 nodes; (2) it can reduce robustness, since a new router that should replace an old router in the CDS must first wait until it knows the old router is no longer in the CDS, possibly resulting in an interval during which no CDS router exists; and (3) the resulting CDS is not deterministic/predictable, because it depends on the order in which nodes perform the second phase. We also note that the persistent versions of our CDS algorithms already take into consideration which neighbors are in the CDS, and therefore cannot benefit from such a second phase. Phase 1 of the MPN algorithm with h1 = 2 and RtrPri the same for all nodes is similar to the MPR-based CDS algorithm in [Adjih02] using the min-ID algorithm for computing MPRs. The main difference is that the MPN algorithm does not compute neighbor-selected MPRs. (However, one can say that the MPN algorithm determines whether the neighbor j with maximum (RtrPri, RID) would select node i as an MPR.) 5. Adjacencies and LSAs Adjacencies are formed only between DR/BDR routers and their neighbors, as in legacy OSPF. Thus, adjacencies are not allowed between two DR_Other (non-DR/BDR) routers. However, if the ANP CDS algorithm is used, a DR/BDR router need not be adjacent to all of its neighbors. The minimum requirement is that a router must form an adjacency with each dependent neighbor. If the Essential CDS or MPN CDS algorithm is used, all neighbors of each DR and BDR are dependent. But if the ANP CDS algorithm is used, only a subset of neighbors are dependent. It is possible for router B to be a dependent neighbor of router A, even if router A is not a dependent neighbor of router B. Thus, an adjacency must be formed between two routers if either of them is a dependent neighbor of the other. Thus, if router A selects router B as a dependent neighbor, and B is not yet adjacent, then router A should start the database exchange process with router B. Since router B may not be aware that the two routers should become adjacent, router A should be the master and start sending Database Ogier Expires July 11, 2005 [Page 14] Internet-Draft MANET Extension of OSPF January 2005 Description (DD) packets. (Modifications for reducing the overhead of the exchange process are proposed in Section 9.) Once an adjacency is formed, there are two possibilities for when to tear it down: 1. Once formed, an adjacency between two routers A and B continues as long as either router is a DR or BDR, and bidirectional communication exists between them. 2. Once formed, an adjacency between two routers A and B continues as long as either router is a dependent neighbor of the other router. This choice requires that each router know which neighbors have selected it to be dependent, which can be achieved by modifying Hellos to specify which neighbors are dependent. Another question is which neighbors to include in the Router LSA originated by a MANET router. Each such neighbor is represented as a Type 1 link (point-to-point) in the Router LSA. As with adjacencies, the minimum requirement is that a router must include all dependent neighbors in its LSA. Since DR_Other routers have no dependent neighbors, this implies that the LSA originated by such a router can be empty (contain no neighbors), thus reducing overhead significantly. (Such a router will still have adjacencies with neighboring DRs and BDRs, which can be used to construct the shortest-path tree.) However, a better choice may be to include all adjacent neighbors in the LSA, in which case the LSA originated by a DR_Other router will include only DR and BDR neighbors. In addition, a router MAY include any non-adjacent, bidirectional neighbors in its LSA. For example, in the full topology case, every router includes all of its bidirectional neighbors in its LSA. The above choices, along with the choices for the CDS algorithm, allows much flexibility. Interoperability is ensured even if different routers make different choices, as long as the minimum requirements are satisfied. Some examples of possible choices are as follows: 1. Select DRs and BDRs using MPN with h1 = h2 = 3. Each DR/BDR router forms adjacencies with all neighbors. Each router includes all neighbors in its LSA (full topology). 2. Select DRs and BDRs using ANP with h1 = h2 = 3. Each DR/BDR router forms adjacencies with all neighbors. Each router includes only adjacent neighbors in its LSA. The resulting routes will be very close to min-hop as hown Ogier Expires July 11, 2005 [Page 15] Internet-Draft MANET Extension of OSPF January 2005 by the simulation results presented in Section 10. 3. Select DRs and BDRs using ANP with h1 = 3 and h2 = 2. Each DR/BDR router forms adjacencies only with dependent neighbors. Each router includes only adjacent neighbors in its LSA. This provides min-hop routing because h2 = 2. 4. Same as 3, but use h1 = 2 and h2 = 2 or 3. This will not only provide min-hop routing (because h1 = 2), but will also result in flooding along min-hop paths, if the optional step (b) of the flooding procedure below is used. 6. Flooding Procedure This section describes the flooding procedure. Much of the procedure is the same as described in Section 13 of RFC 2328, so we focus on the differences. The processing of received LSAs is the same as in Section 13 of RFC 2328, Steps (1) through (8), except that a router MUST process an LSA received from any 2-way neighbor (not just from adjacent neighbors in Exchange state or higher), in order to take advantage of multicast transmissions to reduce the number of retransmissions. On MANET interfaces, LSU packets that do not contain retransmitted LSAs are always multicast to AllSPFRouters. The procedure for forwarding LSAs is as in Section 13.3 of RFC 2328, with the following modifications. Replace Step 1c with the following: If the new LSA, or an ACK for the new LSA, was received from this neighbor, examine the next neighbor. Remove Steps 3 and 4, and replace Step 5 with the Forwarding Procedure below, which requires the following definition: A DR is called an "Essential DR" if it has a larger value of (RtrPri, RID) than all of its neighbors, or if the neighbor with maximum (RtrPri, RID) is a Dependent Neighbor. If the persistent version of a CDS algorithm is used, then (DRLevel, RtrPri, RID) is used instead of (RtrPri, RID). If the Essential CDS or MPN CDS algorithm is used, then all neighbors are dependent, so a DR is always Essential in this case. Forwarding Procedure (a) If the router is an Essential DR, then the new LSA MUST be flooded out the minimum ID interface corresponding to each adjacent router from which the new LSA, or an ACK for the new Ogier Expires July 11, 2005 [Page 16] Internet-Draft MANET Extension of OSPF January 2005 LSA, has not been received, and that is not a neighbor (based on 2-hop neighbor information) of the router from which the new LSA was received. (b) Else, if the router is a DR and the neighbor from which the new LSA was received is a dependent neighbor, then the new LSA MAY be flooded out the minimum ID interface corresponding to each adjacent router from which the new LSA, or an ACK for the new LSA, has not been received, and that is not a neighbor (based on 2-hop neighbor information) of the router from which the new LSA was received. (c) Else, if the router is a Backup DR, the new LSA may be forwarded after some delay, as described below. Note that duplicate LSAs are not forwarded; a new LSA is considered for forwarding only the first time it is received. Step (a) of the Flooding Rule ensures that the LSA is forwarded by all nodes in the Essential CDS, regardless of which optional CDS algorithm is used, and regardless of the order in which nodes transmit a given LSA. The optional step (b) can be used to reduce the flooding delay, at the cost of some additional overhead. If the ANP algorithm is used with h1 = 2, then Step (b) ensures that LSAs are flooded along min-hop paths. One of the duties of a Backup DR is to forward a new LSA when one its neighboring DRs fails to transmit the LSA. A Backup DR does not immediately forward a new LSA, but forwards it after waiting a specified amount of time (less than RxmtInterval), if at that time the set of neighbors from which it has received the new LSA does not cover all of its adjacent neighbors (based on its 2-hop neighbor information obtained from Hellos). A Backup DR is analogous to a "non-active overlapping relay" in Cisco's proposed solution [Chandra04], and the timer PushbackInterval from their draft can be used for determining how long a Backup DR waits before forwarding a new LSA. 7. Retransmitting LSAs LSAs are retransmitted according to Section 13.6 of RFC 2328. As in legacy OSPF, LSAs are retransmitted only to adjacent routers. Thus, since the proposed solution does not allow an adjacency to be formed between two DR_Other routers, a DR_Other router never retransmits an LSA to another DR_Other router (only to a DR or BDR router as in legacy OSPF). As in OSPF, retransmitted LSAs are unicast, but see Section 9.2 for a proposed modification that allows retransmitted Ogier Expires July 11, 2005 [Page 17] Internet-Draft MANET Extension of OSPF January 2005 LSAs to be multicast. One advantage of allowing only DR and BDR routers to retransmit LSAs to DR_Other routers is that DR and BDR routers can group together several retransmitted LSAs into the same LSU packet, thus reducing overhead. In particular, if a DR_Other router originates an LSA, it only needs to retransmit its LSA to DR and BDR neighbors. 8. Link State Acknowledgments As proposed in [Chandra04], all Link State Acknowledgments (LS ACKs) are multicast, a duplicate received LSA is not acknowledged unless it is a unicast retransmission, and each router maintains a database of all recently received LS ACKs. As in legacy OSPF, a forwarded LSA is treated as an implicit ACK, and multiple delayed ACKs may be bundled into a single packet. As in legacy OSPF, LS ACKs are processed only by adjacent neighbors. Therefore, since we do not allow two DR_Other routers to be adjacent, an ACK sent by a DR_Other router will be processed only by DR and BDR routers (as in legacy OSPF). Thus, ACKs and retransmitted LSAs are sent only between adjacent routers. Retransmitted LSAs are sent only to adjacent routers from which an explicit or implicit ACK has not been received. 9. Proposed Enhancements We propose three enhancements which can be used to reduce overhead. 9.1. More Efficient Database Exchange When a router becomes a DR or BDR, it must form adjacencies with some or all of its neighbors, which can consume a lot of bandwidth in dense networks, since a complete set of Database Description (DD) packets is unicast to and from each neighbor in legacy OSPF. Two modifications can be used to significantly reduce the overhead of this exchange. First, it is not necessary for the slave to send a complete set of DD packets; it is sufficient for the slave to include in its DD packet(s) only LSA headers that are more recent or are not included in the DD packets sent by the master. To accomplish this, the slave does not include any LSA headers in its DD packets until the master has sent its last DD packet (indicated by the "more" bit being 0), so that it knows which LSA headers to include in its DD packets to the master. The second modification is for a new DR/BDR that has decided to form Ogier Expires July 11, 2005 [Page 18] Internet-Draft MANET Extension of OSPF January 2005 adjacencies with all of its neighbors (which is the case if the Essential CDS or MPN CDS algorithm is used). Just as a router transmits LSAs as multicasts, and then retransmits them as unicasts when necessary, a new DR or BDR can first send a complete set of DD packets as multicasts, and then retransmit them as unicasts when necessary. To make this work, the new DR or BDR should be the master, and all of its neighbors should be slaves. When such a slave sees a multicast DD packet from a 2-way neighbor that is not yet fully adjacent, it replies by unicasting a (possibly empty) DD packet having the same DD sequence number. In the ideal case (where all nodes are already synchronized and no retransmissions are needed) the master will multicast a complete set of DD packets, and its neighbors (that are not yet fully adjacent) will respond by sending only empty DD packets, thus saving a lot of overhead. If the master multicasts a DD packet but does not receive an acknowledgment (i.e., a possibly empty DD packet with the same sequence number) from some neighbor that is not yet fully adjacent, then the master retransmits the DD packet as a unicast. Alternatively, retransmitted DD packets can be multicast instead of unicast, using the same idea as described below for multicasting retransmitted LSAs. A new TLV would be defined to list the neighbors that must acknowledge the DD packet. 9.2. Multicasting Retransmitted LSAs If a router must retransmit a given LSA to several neighbors, it would be more efficient to retransmit the LSA as a multicast. However, since each router acknowledges a multicast LSA only the first time it is received, a modification is needed to ensure that the intended recipients acknowledge the retransmitted LSA. This can be accomplished by defining a new TLV that provides a list of the neighbors that must acknowledge the LSA. If the LSA must be retransmitted again, the neighbors from which an ACK has been received are removed from the list. This idea was proposed several years ago by the MANET working group. 9.3. Non-Ackable LSAs In a highly mobile network, it is possible that a router almost always originates a new LSA every MinLSInterval seconds. In this case, it should not be necessary to send ACKs for such an LSA, or to retransmit such an LSA as a unicast. In this case, the originator of an LSA MAY indicate that the LSA is "non-ackable" via a new option bit. For example, the originator can use an exponential moving average to determine that a new LSA is originated every MinLSInterval seconds with probability greater than 90 percent. (Simulations are needed to determine the best threshold.) Ogier Expires July 11, 2005 [Page 19] Internet-Draft MANET Extension of OSPF January 2005 A non-ackable LSA is never ACKed, nor is it ever retransmitted as a unicast. However, the originating router and each Essential DR (as defined in Section 6) must periodically retransmit a non-ackable LSA as a multicast. The retransmission period should be slightly larger than MinLSInterval (e.g., MinLSInterval + 1) so that a new instance of the LSA is usually received before the previous one is retransmitted. In addition, non-ackable LSAs need not be described in DD packets. 10. Simulation Comparison of CDS Algorithms This section compares five algorithms from the family of CDS algorithms presented in Section 4: Essential CDS, MPN (h1 = 3), ANP (h1 = 3), MPN (h1 = 2), ANP (h1 = 3). Only DRs (not Backup DRs) are computed, and only the non-persistent version of each algorithm is considered. Each algorithm is compared with RtrPri the same for all nodes, and with RtrPri equal to the node degree. The algorithms are compared with respect to average CDS size (number of DRs) and average stretch factor (defined in the Introduction). For each experiment, each algorithm was run on 100 randomly generated graphs, with the CDS size and stretch factor averaged over these graphs. The number of nodes ranges from 50 to 300, with the nodes randomly placed in a unit square. Two values were used for the transmission radius: 0.3 and 0.5. The average diameter of the graph is about 5 for radius 0.3, and about 3 for radius 0.5. For 100 nodes, the average degree was 21.38 for radius 0.3 and 48.04 for radius 0.5. Table 1 gives the average CDS sizes and Table 2 gives the average stretch factor, for a radius of 0.3. Tables 3 and 4 give the results for a radius of 0.5. We note that ANP with h1 = 2, and RtrPri equal to the node degree, is equivalent to the CDS algorithm in [Lin03], except that we omit the second phase (which resulted in at most one less CDS node in a network of 100 nodes). As expected, the most scalable of the CDS algorithms is the Essential CDS algorithm, whose CDS size increased only slightly, from 20.36 to 23.26, when the number of nodes was increased from 100 to 300, for radius 0.3. In contrast, Lin's algorithm resulted in a CDS size that increased from 49.58 to 167.94 when the number of nodes was increased from 100 to 300. For 300 nodes, Lin's algorithm selected about 56% of the nodes, while the Essential CDS algorithm selected about 8% of the nodes. Surprisingly, the Essential CDS algorithm performed better *without* using node degree when the number of nodes was greater than 100. As expected, the average stretch factor is smaller for ANP than for Ogier Expires July 11, 2005 [Page 20] Internet-Draft MANET Extension of OSPF January 2005 MPN (for the same value of h1), and is smaller with h1 = 2 than with h1 = 3. It is interesting that using node degree always results in a smaller stretch factor. Of course, the stretch factor for ANP with h1 = 2 is always 1, since this algorithm provides flooding along min- hop paths. The choice of which algorithm to use depends on what stretch factor is considered acceptable. For example, if one wanted to obtain the smallest CDS that has a stretch factor less than 1.05 in a 200 node network, then the best choice would be ANP with h1 = 3 and RtrPri equal to node degree. Note that all of these algorithms are interoperable since the CDS computed by each algorithm contains the Essential CDS. Therefore, different routers MAY use different algorithms from the proposed family of CDS algorithms. Number of Nodes -------------------------------------------------- Algorithm RtrPri 50 100 200 300 -------------------------------------------------- Essential 1 17.50 20.36 22.14 23.26 Essential degree 13.79 18.66 27.42 33.14 -------------------------------------------------- MPN (h1=3) 1 18.03 21.32 23.35 24.50 MPN (h1=3) degree 13.84 18.74 27.49 34.21 -------------------------------------------------- ANP (h1=3) 1 18.53 23.70 26.70 28.26 ANP (h1=3) degree 14.52 20.26 28.79 35.50 -------------------------------------------------- MPN (h1=2) 1 22.96 35.01 48.31 57.96 MPN (h1=2) degree 15.25 24.03 37.55 48.67 --------------------------------------------------- ANP (h1=2) 1 30.41 62.69 128.73 194.71 ANP (h1=2) degree 23.67 49.58 108.15 167.94 --------------------------------------------------- Table 1. Average CDS size for radius 0.3 Ogier Expires July 11, 2005 [Page 21] Internet-Draft MANET Extension of OSPF January 2005 Number of Nodes -------------------------------------------------- Algorithm RtrPri 50 100 200 300 -------------------------------------------------- Essential 1 1.108 1.167 1.188 1.191 Essential degree 1.046 1.071 1.070 1.072 -------------------------------------------------- MPN (h1=3) 1 1.087 1.137 1.158 1.165 MPN (h1=3) degree 1.044 1.067 1.068 1.071 -------------------------------------------------- ANP (h1=3) 1 1.062 1.098 1.119 1.126 ANP (h1=3) degree 1.034 1.032 1.036 1.060 -------------------------------------------------- MPN (h1=2) 1 1.034 1.044 1.053 1.054 MPN (h1=2) degree 1.027 1.032 1.036 1.037 --------------------------------------------------- ANP (h1=2) 1 1.000 1.000 1.000 1.000 ANP (h1=2) degree 1.000 1.000 1.000 1.000 --------------------------------------------------- Table 2. Average stretch factor for radius 0.3 Number of Nodes -------------------------------------------------- Algorithm RtrPri 50 100 200 300 -------------------------------------------------- Essential 1 7.02 7.59 8.21 8.46 Essential degree 5.14 8.03 13.47 18.54 -------------------------------------------------- MPN (h1=3) 1 7.19 7.76 8.41 8.69 MPN (h1=3) degree 5.14 8.03 13.47 18.54 -------------------------------------------------- ANP (h1=3) 1 7.55 8.44 9.36 9.60 ANP (h1=3) degree 5.16 8.03 13.47 18.54 -------------------------------------------------- MPN (h1=2) 1 10.37 12.53 15.32 16.21 MPN (h1=2) degree 5.14 8.03 13.47 18.54 --------------------------------------------------- ANP (h1=2) 1 19.32 36.03 64.37 91.56 ANP (h1=2) degree 11.77 22.80 43.81 64.95 --------------------------------------------------- Table 3. Average CDS size for radius 0.5 Ogier Expires July 11, 2005 [Page 22] Internet-Draft MANET Extension of OSPF January 2005 Number of Nodes -------------------------------------------------- Algorithm RtrPri 50 100 200 300 -------------------------------------------------- Essential 1 1.088 1.091 1.093 1.091 Essential degree 1.017 1.016 1.013 1.012 -------------------------------------------------- MPN (h1=3) 1 1.079 1.083 1.083 1.081 MPN (h1=3) degree 1.017 1.016 1.013 1.012 -------------------------------------------------- ANP (h1=3) 1 1.061 1.065 1.063 1.063 ANP (h1=3) degree 1.016 1.016 1.013 1.012 -------------------------------------------------- MPN (h1=2) 1 1.033 1.034 1.035 1.036 MPN (h1=2) degree 1.017 1.016 1.013 1.012 --------------------------------------------------- ANP (h1=2) 1 1.000 1.000 1.000 1.000 ANP (h1=2) degree 1.000 1.000 1.000 1.000 --------------------------------------------------- Table 4. Average stretch factor for radius 0.5 References [Adjih02] C. Adjih, P. Jacquet, and L. Viennot. "Computing connected dominated sets with multipoint relays", INRIA research report No. 4597, October 2002. [Chandra04] M.W. Chandra, Editor. "Extensions to OSPF to Support Mobile Ad Hoc Networking", Internet-Draft (work in progress), draft-chandra-ospf-manet-ext-02.txt, October 2004. [Lin03] T. Lin, S.F. Midkiff, and J.S. Park. "A Framework for Wireless Ad Hoc Routing Protocols", IEEE WCNC, March 2003. [RFC2328] J. Moy. "OSPF Version 2", RFC 2328, April 1998. [RFC2740] R. Coltun, D. Ferguson, and J. Moy. "OSPF for IPv6", RFC 2740, December 1999. [RFC3626] T. Clausen, P. Jacquet (ed). "Optimized Link State Routing Protocol (OLSR)", RFC 3626, October 2003. [RFC3684] R. Ogier, F. Templin, and M. Lewis. "Topology Dissemination Based on Reverse Path Forwarding", RFC 3684, February 2004. Ogier Expires July 11, 2005 [Page 23] Internet-Draft MANET Extension of OSPF January 2005 [Suurballe84] J.W. Suurballe and R.E. Tarjan. "A Quick Method for Finding Shortest Pairs of Disjoint Paths", Networks, Vol. 14, pp. 325-336. 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 (2005). 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 July 11, 2005 [Page 24]