OSPF and Mobile Ad Hoc Networks Working Groups R. Ogier Internet-Draft February 21, 2005 MANET Extension of OSPF using CDS Flooding draft-ogier-manet-ospf-extension-03.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 August 21, 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 August 21, 2005 [Page 1] Internet-Draft MANET Extension of OSPF February 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 August 21, 2005 [Page 2] Internet-Draft MANET Extension of OSPF February 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. The 2-hop neighbor information required for DR selection is obtained from Hello packets. Section 10 describes a differential Hello protocol in which either partial or full 2-hop neighbor information is advertised in Hellos. One of the advantages of the proposed solution is that only partial 2-hop neighbor information is required, thus reducing overhead. 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, including more efficient database exchange, multicasting retransmitted LSAs, and non-ackable LSAs. Section 10 describes the differential Hello protocol, and Section 11 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. Ogier Expires August 21, 2005 [Page 3] Internet-Draft MANET Extension of OSPF February 2005 - The CDS algorithms are based only on 2-hop neighbor information, to provide fast convergence following topology changes. - 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 11. 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. - A flexible Hello protocol is presented that allows routers to send either full or differential Hellos, in which either full or partial 2-hop neighbor information is advertised. 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 Ogier Expires August 21, 2005 [Page 4] Internet-Draft MANET Extension of OSPF February 2005 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" 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). - While existing MPR selection algorithms require full 2-hop neighbor information, CDS selection depends only on partial 2-hop neighbor information which is determined naturally as part of the CDS algorithm. - 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 Ogier Expires August 21, 2005 [Page 5] Internet-Draft MANET Extension of OSPF February 2005 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. 4. Proposed Family of CDS Algorithms In this section, we describe a family of distributed CDS algorithms based on 2-hop neighbor information, which is obtained from Hellos as described in Section 10. 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 Ogier Expires August 21, 2005 [Page 6] Internet-Draft MANET Extension of OSPF February 2005 - willingness to be a relay - a router that has been a DR or BDR for a certain amount of time can reduce its Router Priority, so that the burden of being a DR/BDR can be shared among all routers. The simulation results presented in Section 11 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 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 DRs 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. In the following description, node i denotes the node performing the calculation. Each node running the algorithm maintains a list of Dependent Neighbors and a list of Backup Dependent Neighbors, whose use will be described in Sections 5 and 6. 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, selects all of its neighbors as Dependent Neighbors, and exits. 1.2. Else, let s 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 s to each other neighbor u 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. 1.3. Else, node i selects itself as a DR, and selects the following nodes as Dependent Neighbors: node s, and each neighbor u Ogier Expires August 21, 2005 [Page 7] Internet-Draft MANET Extension of OSPF February 2005 such that a path from s to u was not found in step 1.2. Phase 2 (Backup DR Selection) 2.1. If node i does not select itself as a DR in Phase 1, and if there exist two node-disjoint paths from node s to each other neighbor u 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. 2.2. Else, node i selects itself as a Backup DR, and selects the following nodes as Backup Dependent Neighbors: node s, and each neighbor u such that two node-disjoint paths from node s to node u was not found in step 2.2. The purpose of the DRs is to provide a minimal set of relays for flooding LSAs, and the purpose of the Dependent Neighbors is to provide a set of adjacencies for maintaining database synchronization. The purpose of the Backup DRs is to provide backup relays to retransmit flooded LSAs when flooding by DRs does not succeed, and the purpose of Backup Dependent Neighbors is to provide redundant adjacencies for robustness, and to allow a Backup DR to quickly take over the role of a DR in response to topology changes. The set of DRs computed by Phase 1 forms a CDS (called the Essential CDS) and the subgraph consisting of all links between DRs and their Dependent Neighbors is connected and spans all nodes in the network. Ideally, this subgraph would be a tree with n-1 edges, but since each node uses only 2-hop neighbor information, it will typically have more than n-1 edges. 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 subgraph consisting of all links between CDS nodes and their (Backup) Dependent Neighbors 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. Ogier Expires August 21, 2005 [Page 8] Internet-Draft MANET Extension of OSPF February 2005 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 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 s 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. Phase 2 of the algorithm can be implemented using a modification of the algorithm [Suurballe84] to find the node-disjoint paths. A detailed description of this algorithm, which runs in O(d^2) time, is given in the Appendix. The Appendix also describes an alternative algorithm for Phase 2, which is simpler but results in a larger number of BDRs. 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, a router MUST select itself as a DR if it would do so with the Essential CDS algorithm, and a router MUST select itself as a DR or BDR if it would select itself as a BDR with the Essential CDS algorithm. However, a node MAY select itself as a DR even if it would not do so with the Essential CDS algorithm. The next section describes two subfamilies of distributed CDS algorithms, each of which computes a CDS that contains the Essential CDS. As shown in simulation results presented in Section 11, 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 Ogier Expires August 21, 2005 [Page 9] Internet-Draft MANET Extension of OSPF February 2005 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, and selects all of its neighbors as Dependent Neighbors. 1.2. Else, let s be the neighbor of node i that has the largest 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 s to each other neighbor u 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. 1.3. Else, node i selects itself as a DR, and selects the following nodes as Dependent Neighbors: node s, and each neighbor u such that step 1.2 did not find a path from s to u with at most h1 hops. Phase 2 (Backup DR Selection) 2.1. If node i does not select itself as a DR in Phase 1, and if there exist two node-disjoint paths from node s to each other neighbor u 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. 2.2. Else, node i selects itself as a Backup DR, and selects the following nodes as Backup Dependent Neighbors: node s, and each neighbor u such that step 2.1 did not find two node-disjoint paths from s to u with at most h2 hops. As with the Essential CDS algorithm, the persistent version of the MPN algorithm can be obtained simply by replacing each occurrence of Ogier Expires August 21, 2005 [Page 10] Internet-Draft MANET Extension of OSPF February 2005 (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 Essential CDS algorithm is equivalent to the MPN algorithm with h1 and h2 equal to infinity. 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 hop distance 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 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. A node running the ANP algorithm is called a DR if it has at least one Dependent Neighbor, and a BDR if it is not a DR and has at least one Backup Dependent Neighbor. Unlike the Essential CDS and MPN CDS algorithms, a DR can have both Dependent Neighbors and Backup Dependent Neighbors, i.e., a DR can act as a BDR for some neighbors. However, a neighbor that is Dependent cannot also be Backup Dependent. 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 Ogier Expires August 21, 2005 [Page 11] Internet-Draft MANET Extension of OSPF February 2005 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.1. Initialize the list of Dependent Neighbors to be empty. For each neighbor node j that was not selected as a Dependent Neighbor in Phase 1, 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 Backup Dependent Neighbors; otherwise, add node j to the list. 2.2. If node i did not select itself as a DR in Phase 1, and the list of Backup 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). In Sections 5 and 6, we will need the concept of a Min-Hop Dependent Neighbor, which is defined in terms of the ANP algorithm, as follows. A neighbor j is called a Min-Hop Dependent Neighbor (MHDN) if node j would be be selected as a Dependent Neighbor by Phase 1 of the ANP algorithm with h1 = 2. Similarly, a neighbor j is called a Backup MHDN if node j would be selected as a Backup Dependent Neighbor by Phase 2 of the ANP algorithm with h2 = 2. This definition holds whether or not node i is a DR/BDR, and whether or not node i is using the ANP algorithm for DR/BDR selection. The concept of a Min-Hop Dependent Neighbor can be used as an option to provide flooding along min-hop paths (see Section 6) and/or to define a partial topology that provides min-hop path routing (see Section 5). Ogier Expires August 21, 2005 [Page 12] Internet-Draft MANET Extension of OSPF February 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 OSPF was first used in the 1980s, 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 (as described in Section 10) 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 Ogier Expires August 21, 2005 [Page 13] Internet-Draft MANET Extension of OSPF February 2005 computed by Phase 1 of the ANP algorithm with h1 = 2 and RtrPri the same for all nodes. Phase 1 of the ANP algorithm with h1 = 2 is also equivalent to Phase 1 of the CDS algorithm of [Lin03] if RtrPri is equal to the node degree. However, the simulations presented in [Lin03] assume that a flooded packet is forwarded only if it is received from the equivalent of a Dependent Neighbor, as in step (b) of the forwarding procedure given in Section 6 of this document. 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 each DR/BDR router and its (Backup) Dependent Neighbors (similar to legacy OSPF). Note that an adjacency is not formed with a (Backup) Min-Hop Dependent Neighbor (defined in Section 4.3), unless it also happens to be a (Backup) Dependent Router. 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 (Backup) Dependent Neighbor of the other. A router knows which neighbors have selected it as a (Backup) Dependent Neighbor, since this information is advertised in Hello packets as described in Section 10. Once formed, an adjacency between two routers A and B continues as long as either router is a Dependent Neighbor of the other router. An enhancement was recently discovered which greatly reduces the rate at which new adjacencies are formed in a highly mobile, dense network, especially when the persistent version of the Essential CDS algorithm is used. (See the simulation results in Section 11.) In this enhancement, each DR_Other router selects two DR/BDR neighbors called "parents", one of which must be a DR, and forms adjacencies only with its two parents, keeping the same parents as long as both are DR/BDR neighbors and one of them is a DR (persistence). Each DR_Other router reports its two selected DR/BDR neighbors in the DR and BDR fields of each Hello (as in legacy OSPF). This enhancement will be described in detail in a future revision of this document. Ogier Expires August 21, 2005 [Page 14] Internet-Draft MANET Extension of OSPF February 2005 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. The minimum requirement is that a router must include all fully adjacent neighbors in its LSA. This minimum requirement will provide a path to every reachable destination node, but it will usually not be a shortest path. A 2-Way neighbor j is considered to be "synchronized" if the neighbor j is fully adjacent, or if a path to node j has been calculated from the link-state database, which implies that there exists (or recently existed) a path to node j via fully adjacent links. A router may include any synchronized neighbor in in its Router LSA. For example, a router may choose to include all synchronized neighbors in its Router LSA (full topology), although this may result in a large amount of overhead. Another choice is for a router to include all Min-Hop Dependent Neighbors in its LSA, which will allow min-hop paths to be computed. If Backup Min-Hop Dependent Neighbors are also included, then two disjoint min-hop paths to each destination can be computed (if such paths exist). 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 the Essential CDS algorithm, or using MPN with h1 = h2 = 3. Each router includes all neighbors in its LSA (full topology). 2. Same as 1, but each router includes only (Backup) Min-Hop Dependent Neighbors in its LSA. This is probably the most efficient way to provide min-hop routing. 3. Select DRs and BDRs using ANP with h1 = h2 = 3. Each DR/BDR router includes all neighbors in its LSA. The resulting routes will be very close to min-hop as shown by the simulation results presented in Section 11. 4. Select DRs and BDRs using ANP with h1 = 3 and h2 = 2. Each router includes only adjacent neighbors in its LSA. This provides min-hop routing because h2 = 2. 5. Same as 4, but use h1 = 2 and h2 = 2. This will not only provide min-hop routing, but will also result in flooding along Ogier Expires August 21, 2005 [Page 15] Internet-Draft MANET Extension of OSPF February 2005 min-hop paths. However, this choice will result in a large number of adjacencies and will therefore generate a large amount of overhead. 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. This procedure uses the concept of a Min-Hop Dependent Router (defined in Section 4.3) to provide the option of flooding along min-hop paths. Forwarding Procedure (a) If the router is a DR, then the new LSA MUST be flooded out an interface associated with each Dependent Neighbor from which 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. (b) Else, if the neighbor from which the new LSA was received is a Min-Hop Dependent Neighbor, then the new LSA MAY be flooded out an interface associated with each Min-Hop Dependent Neighbor from which 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) If the router is a BDR, then the router waits BackupWaitInterval seconds after receiving the new LSA. After this interval, the new LSA MUST be flooded out an interface associated with each Backup Dependent Neighbor from which the new LSA has not been received, and that is Ogier Expires August 21, 2005 [Page 16] Internet-Draft MANET Extension of OSPF February 2005 not a neighbor (based on 2-hop neighbor information) of any router from which the new LSA was received. (d) Else, if the neighbor from which the new LSA was received is a Backup Min-Hop Dependent Neighbor, then the router waits BackupWaitInterval seconds after receiving the new LSA. After this Interval, the new LSA MAY be flooded out an interface associated with each Backup Min-Hop Dependent Neighbor from which the new LSA has not been received, and that is not a neighbor (based on 2-hop neighbor information) of any router from which the new LSA was received. 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 DRs, 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, by ensuring that LSAs are flooded along min-hop paths. One of the duties of a BDR is to forward a new LSA when one its neighboring DRs fails to transmit the LSA. Step (c) requires a BDR to forward the new LSA after a small delay (BackupWaitInterval) if the neighbors that are known to have transmitted the new LSA do not cover all Backup Dependent Neighbors. BackupWaitInterval must be less than RxmtInterval, to avoid unnecessary retransmissions. The optional step (d) is similar to the optional step (b), but for a BDR instead of a DR. A Backup DR is analogous to a "non-active overlapping relay" in [Chandra04], and the parameter BackupWaitInterval is equivalent to PushbackInterval in their draft. 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 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 Ogier Expires August 21, 2005 [Page 17] Internet-Draft MANET Extension of OSPF February 2005 overhead. In particular, if a DR_Other router originates an LSA, it only needs to retransmit its LSA to DR and BDR neighbors. To reduce unnecessary retransmissions, a DR_Other router never retransmits an LSA that it did not originally transmit as a broadcast. This is done only by DR/BDR routers, and only to (Backup) Dependent Neighbors. However, since it is possible for a DR_Other to become a DR or BDR, a DR_Other does put received new LSAs on the link state retransmission list for each adjacent neighbor. If the DR_Other router becomes a DR or BDR, then it will retransmit all LSAs in the retransmission list for any (Backup) Dependent Neighbor. 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: more efficient database exchange, multicasting retransmitted LSAs, and non-ackable LSAs. 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 Ogier Expires August 21, 2005 [Page 18] Internet-Draft MANET Extension of OSPF February 2005 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 adjacencies with several of its neighbors. 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 DR/BDR 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 Ogier Expires August 21, 2005 [Page 19] Internet-Draft MANET Extension of OSPF February 2005 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.) A non-ackable LSA is never ACKed, nor is it ever retransmitted as a unicast. However, the originating router and each DR 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. Note that the reception of a retransmitted (duplicate) LSA does not result in immediate forwarding of the LSA; only a new LSA (with a larger sequence number) may be forwarded immediately, according to the forwarding procedure of Section 6. In addition, non-ackable LSAs need not be described in DD packets. 10. Differential Hello Protocol Hellos are used both for neighbor discovery and for obtaining 2-hop neighbor information. Although it is possible to obtain 2-hop neighbor information from LSAs originated by neighbors, we choose to use Hellos for this purpose, for the following reasons: - The content of LSAs, and the the flooding of LSAs, depend on which neighbors are adjacent, and 2-hop neighbor information is needed before a router can decide which neighbors should be adjacent. - 2-hop information can be different from that obtainable from LSAs. For example, LSAs may report only partial topology, whereas a node may report all of its (2-way) neighbors to provide full 2-hop neighbor information. - By making the flooding protocol independent of LSAs, it can be used in MANET applications other than OSPF. One of the advantages of the proposed method (versus using neighbor- selected MPRs) is that full 2-hop neighbor information is not required. In fact, it is only necessary for each router to keep all neighbors informed of its (Backup) Dependent Neighbors. This can reduce overhead dramatically in a highly mobile, dense network. The Hello protocol described below is flexible in that a router can send full Hellos that provide full 2-hop neighbor information, or can send differential Hellos and provide only *partial* 2-hop neighbor information by periodically including a list of its Dependent Ogier Expires August 21, 2005 [Page 20] Internet-Draft MANET Extension of OSPF February 2005 Neighbors in a Hello (to reduce overhead). Since only DR/BDR routers have Dependent Neighbors, it is also possible to simply have DR/BDR routers send full Hellos, and have other routers send only differential Hellos. Alternatively, each router can send differential Hellos and provide *full* 2-hop neighbor information by periodically sending a full Hello. This latter approach reduces overhead by sending full Hellos less frequently (e.g., every 10 seconds), while sending differential Hellos more frequently (e.g., every 2 seconds) to allow faster response to topology changes. 10.1. Full Hellos We first describe the contents of a full Hello packet, which depends on the state of each neighbor (Down, Init, 2-Way, etc. as in legacy OSPF), and on whether each neighbor is Dependent. (A neighbor in state 2-Way or higher may or may not be Dependent.) A full Hello contains three lists of Router IDs, which are formatted as TLVs: - Heard Neighbor List (HNL): Includes all neighbors in state Init or higher that are not included in the Dependent Neighbor List or the Non-Dependent Neighbor List. - Dependent Neighbor List (DNL): Includes all Dependent and Backup Dependent neighbors. (Such neighbors are in state 2-Way or higher.) - Non-Dependent Neighbor List (NDNL): Includes all neighbors in state 2-Way or higher that are not (Backup) Dependent. Note that a full Hello includes the Router ID of each neighbor that is in state Init or higher, as does a Hello in legacy OSPF. A router that chooses not to send differential Hellos must send a full Hello every HelloInterval seconds. 10.2. Differential Hellos A differential Hello includes neighbors whose status has recently changed, and also includes a full Dependent Neighbor List periodically, at least once every 2HopRefresh seconds (typically equal to a few Hello intervals). If the router chooses to report full 2-hop neighbor information, indicated by the parameter Full2HopNbrInfo being equal to 1, then a full Non-Dependent Neighbor List must also be included in a Hello every 2HopRefresh seconds. (Alternatively, a full Hello may be sent every 2HopRefresh seconds.) In a differential Hello, the HNL, DNL, and NDNL lists can be partial Ogier Expires August 21, 2005 [Page 21] Internet-Draft MANET Extension of OSPF February 2005 or full, indicated by an option bit. In addition to these lists, a differential Hello may also include the following list: - Lost Neighbor List (LNL): Includes neighbors that recently transitioned to the Down state. Whenever the status of a neighbor changes (as defined below), the neighbor is included in the appropriate list of the next RouterDeadCount (typically 3) Hellos, or until the status changes again. Each Hello contains a Hello Sequence Number (HSN), which is incremented with each Hello sent on a given interface. This allows a router to determine whether it has missed RouterDeadCount consecutive Hellos sent by a neighbor, and thus may have missed a status change reported by the neighbor, as described in the section on receiving Hellos. The status changes that are reported in Hellos, and the corresponding list in which the neighbor is included, are as follows: - The neighbor state changes to Down: Lost Neighbor List. - The neighbor state changes to Init: Heard Neighbor List - The neighbor becomes Dependent: Dependent Neighbor List - The neighbor state changes to 2-Way (or higher) and the neighbor is not (Backup) Dependent: Heard Neighbor List if Full2HopNbrInfo is 0; otherwise Non-Dependent Neighbor List. - The neighbor changes from (Backup) Dependent to non-dependent, but is still 2-Way (or higher): Heard Neighbor List if Full2HopNbrInfo is 0; otherwise Non-Dependent Neighbor List. Note that a neighbor that is included in a differential Hello appears in the same list as it would in a full Hello, except that if Full2HopNbrInfo is 0, then a non-dependent neighbor appears in the Heard list instead of the Non-Dependent list. (The latter list is never included in a Hello if Full2HopNbrInfo is 0.) Note that if the state of a neighbor changes from Down to Init (and the neighbor is therefore included in the next 3 Hellos), and the state of the neighbor later changes to 2-Way, then the neighbor must again be included in 3 consecutive Hellos (assuming RouterDeadCount is 3). This is to ensure that the neighbor will either see itself in one of the Hellos, or will declare the sending router Down after missing 3 Hellos. Ogier Expires August 21, 2005 [Page 22] Internet-Draft MANET Extension of OSPF February 2005 There is one exception to the above rule. If the state of a neighbor changes from Down to Init (and the neighbor is therefore included in the next 3 Hellos), and the state changes to 2-Way before the fourth Hello is sent, then the neighbor need not be included in additional Hellos (since the neighbor must have received one of the 3 Hellos that included the neighbor, or will declare the sending router Down). 10.3. Receiving Hellos A received Hello is processed first to update the state of the sending neighbor, and then to update the 2-hop neighbor information. The neighbor state can be affected by the following events related to received Hellos: SufficientHellosReceived A Hello has been received from the neighbor. To ensure good link quality, and to employ hysteresis, a stricter condition may be imposed, such as requiring that two consecutive Hellos have been received. 2-WayReceived Router sees itself in any list of the neighbor's Hello packet except for the Lost Neighbors list. 1-WayReceived Router sees itself in the Lost Neighbors list of the neighbor's Hello packet, or does not see itself in any list of a full Hello packet. InsufficientHellosReceived A Hello has been received whose sequence number indicates that the last RouterDeadCount Hellos were missed. To ensure good link quality, other criteria may be used, such as missing k of the last n Hellos (for some k and n). However, this event MUST occur whenever the last RouterDeadCount Hellos were missed. InactivityTimer No Hello has been received from the neighbor for RouterDeadInterval, which must be at least RouterDeadCount times HelloInterval. These events cause the following neighbor state changes, which in turn may affect the contents of future Hello packets as described above. Ogier Expires August 21, 2005 [Page 23] Internet-Draft MANET Extension of OSPF February 2005 Event Old State(s) New State ------------------------ ------------ --------- SufficientHellosReceived Down Init 2-WayReceived Init 2-Way 1-WayReceived 2-Way or higher Init InsufficientHellosReceived Init or higher Down InactivityTimer Init or higher Down 10.4. Processing a Hello for 2-hop Neighbor Information Each router maintains, for each neighbor j in state Init or higher, a list DN_j of (Backup) Dependent neighbors reported by node j, and a list NDN_j of non-dependent neighbors reported by node j. (The latter list will be empty if node j is not reporting full 2-hop neighbor information.) The union of these two lists is N_j, the list of all neighbors reported by node j. The list N_j for all neighbors j that are in state 2-Way or higher constitutes the 2-hop neighbor information, which is used by the CDS algorithm. If partial 2-hop neighbor information is used, it is possible that two neighbors j and k are such that j is in N_k but k is not in N_j. Therefore, when computing paths between neighbors in the CDS algorithms, a bidirectional link is assumed to exist between two neighbors j and k if *either* j is in N_k or k is in N_j. If a Hello that contains a full DNL (respectively, NDNL) is received from neighbor j, then the router simply stores the list in its database as DN_j (respectively, NDN_j), replacing the old database copy. If a Hello that contains a partial DNL (respectively, NDNL) is received from neighbor j, then the router adds the Router IDs in the received list to DN_j (respectively, NDN_j). A router is deleted from DN_j (respectively, NDN_j) if it appears in any list other than the DNL (respectively, NDNL) in a Hello received from neighbor j. This provides fast reporting of deleted 2-hop neighbor information in differential Hellos. (Note that a given router can appear in at most one list in a Hello.) 10.5. Comparison to Other Differential Hello Protocols The proposed Hello protocol differs in several ways from three existing Hello protocols that also use differential Hellos: TBRPF [RFC3684], OLSR [RFC3626], and Cisco's proposed OSPF extension [Chandra04]. Ogier Expires August 21, 2005 [Page 24] Internet-Draft MANET Extension of OSPF February 2005 First, TBRPF and Cisco's protocol do not use Hellos to advertise 2-hop neighbor information, although OLSR does. However, OLSR advertises full 2-hop neighbor information and is not easily modified to advertise only partial 2-hop neighbor information, since all neighbors must be included in a Hello periodically. (Note that the proposed Hello protocol works even if the router has no Dependent Neighbors and therefore reports no 2-hop neighbor information.) In fact, OLSR requires full 2-hop neighbor information for the selection of MPRs, whereas the proposed protocol requires only partial 2-hop neighbor information for the selection of (Backup) DRs and (Backup) Dependent Neighbors. Also, Cisco's protocol requires that a node unicast a Hello request message to a neighbor from which a Hello was missed. In highly mobile, dense networks, Hello requests can occur frequently, thus generating a large amount of overhead. The proposed Hello protocol avoids the use of a Hello request by reporting each neighbor state change a few (RouterDeadCount) times. 11. Simulation Evaluation of CDS Algorithms This section compares and evaluates different algorithms from the family of CDS algorithms presented in Section 4. The first subsection compares the CDS size and stretch factor for five algorithms in the family. Since these measures depend only on the current topology, the algorithms are performed on randomly generated static topologies. The next subsection evaluates the performance of the Essential CDS algorithm in mobile networks, and includes results for the average number of adjacencies and the average rate at which new adjacencies are formed. 11.1. Comparison of CDS Size and Stretch Factor 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. 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 Ogier Expires August 21, 2005 [Page 25] Internet-Draft MANET Extension of OSPF February 2005 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. 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, ANP with h1 = 2 and RtrPri equal to the node degree, 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, this algorithm selected about 56% of the nodes, while the Essential CDS algorithm selected about 8% of the nodes. Surprisingly, the Essential CDS algorithm, and all CDS algorithms with h1 = 3, gave a smaller CDS *without* using node degree, when the number of nodes was greater than 100. Thus, the most scalable algorithms do not use node degree. Another advantage of not using node degree is that it results in a more stable CDS in a mobile network (since the node degree changes as the topology changes). As expected, the average stretch factor is smaller for ANP than for 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 wishes 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. Ogier Expires August 21, 2005 [Page 26] Internet-Draft MANET Extension of OSPF February 2005 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 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 Ogier Expires August 21, 2005 [Page 27] Internet-Draft MANET Extension of OSPF February 2005 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 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 Ogier Expires August 21, 2005 [Page 28] Internet-Draft MANET Extension of OSPF February 2005 11.2. Evaluation of the Essential CDS Algorithm in Mobile Networks The Essential CDS algorithm (with RtrPri the same for all nodes, and using the Suurballe-Tarjan algorithm for BDR selection) was evaluated in a mobile network, to determine the rate at which adjacencies are formed. This is an important measure, since database exchange must be performed whenever a new adjacency is formed. The number of adjacencies is also important, since database synchronization must be maintained across each adjacency via retransmitted LSAs and ACKs. In a broadcast network, legacy OSPF selects one DR and one BDR, and forms 2n-3 adjacencies, where n is the number of nodes. The Essential CDS algorithm forms exactly the same number of adjacencies in a fully connected (single hop) network, and typically forms about 2n adjacencies in a dense network. The network model is the same as in the previous subsection, except that a random direction is initially selected for each node, and each node moves (in its selected direction) by 1/10 of the transmission radius each second (fast mobility). When a node hits a side of the unit square, it reflects off the boundary as in billiards. Table 5 shows the results for the non-persistent version of the algorithm, and Table 6 shows the results for the persistent version, in which each non-DR/BDR node selects two DR/BDR neighbors called "parents" (described in Section 5) and forms adjacencies with its two parents, keeping the same parents as long as both are DR/BDR neighbors and one of them is a DR. The tables show the following statistics: average number of DRs, average number of BDRs, average number of adjacencies (an adjacency between two nodes is counted only once), average number of edges (which would be the number of adjacencies in a solution that requires each router to form adjacencies with all neighbors), and the ratio of these last two measures. Also included are the number of adjacencies formed per second, the number of edges (2-way communications) established per second, and the ratio of these last two measures. The average number of DRs and BDRs is about the same as for the random static topologies used in the previous subsection, since these depend only on the current topology. This is also true for the persistent version of the algorithm, since using (DRLevel, RID) to select DRs and BDRs is statistically the same as using only RID. The results show that the number of edges (and the rate at which new edges are established) increases quadratically with the number of Ogier Expires August 21, 2005 [Page 29] Internet-Draft MANET Extension of OSPF February 2005 nodes, whereas the number of adjacencies with the CDS algorithm (and the rate at which new adjacencies are formed) increases linearly with the number of nodes. Therefore, the CDS algorithm is more scalable than a solution that requires each router to form adjacencies with all neighbors. Using the persistent version greatly reduces the rate at which new adjacencies are formed. For example, in the case of 300 nodes and radius 0.5, the rate of new adjacencies was about 1/9 the rate of new edges with the non-persistent version, but this ratio decreased to about 1/24 with the persistent version. In this case, the number of adjacencies is about 1/36 times the number of edges. This implies that the average life of an adjacency is about 2/3 times the average life of an edge. But this shorter life is greatly outweighed by the fact that only about 3% of edges are adjacencies! Number of Nodes ------------------------------------------------------------- Radius Measure 50 100 200 300 ------------------------------------------------------------- 0.3 Avg # DRs 17.65 20.74 23.45 22.85 Avg # BDRs 13.39 15.47 15.54 16.45 Avg # adj 111.50 242.44 491.59 736.84 Avg # edges 260.63 1055.91 4287.15 9623.68 Ratio edges/adj 2.34 4.36 8.72 13.06 New adj rate 24.30 59.47 128.44 189.79 New edge rate 18.21 72.28 293.55 659.18 Ratio edge/adj rate 0.75 1.22 2.29 3.47 ------------------------------------------------------------- 0.5 Avg # DRs 7.12 7.77 9.14 8.43 Avg # BDRs 5.68 6.16 6.13 6.22 Avg # adj 104.30 207.36 421.90 605.56 Avg # edges 592.67 2384.30 9617.78 21646.11 Ratio edges/adj 5.68 11.50 22.80 35.75 New adj rate 23.07 47.56 96.74 136.48 New edge rate 34.17 138.25 553.70 1245.35 Ratio edge/adj rate 1.48 2.91 5.72 9.12 ------------------------------------------------------------- Table 5. Results for the non-persistent version of the Essential CDS algorithm in mobile networks. Ogier Expires August 21, 2005 [Page 30] Internet-Draft MANET Extension of OSPF February 2005 Number of Nodes ------------------------------------------------------------- Radius Measure 50 100 200 300 ------------------------------------------------------------- 0.3 Avg # DRs 17.26 20.16 22.36 22.02 Avg # BDRs 12.36 13.72 14.17 14.59 Avg # adj 101.44 203.35 402.10 601.64 Avg # edges 260.63 1055.91 4287.15 9623.68 Ratio edges/adj 2.57 5.19 10.66 16.00 New adj rate 18.37 30.77 49.78 66.50 New edge rate 18.21 72.28 293.55 659.18 Ratio edge/adj rate 0.99 2.35 5.90 9.91 ------------------------------------------------------------- 0.5 Avg # DRs 6.99 7.63 8.74 8.12 Avg # BDRs 5.08 5.43 5.35 5.57 Avg # adj 97.11 196.57 395.73 595.69 Avg # edges 592.67 2384.30 9617.78 21646.11 Ratio edges/adj 6.10 12.13 24.30 36.34 New adj rate 11.05 19.91 36.48 51.32 New edge rate 34.17 138.25 553.70 1245.35 Ratio edge/adj rate 3.09 6.95 15.18 24.26 ------------------------------------------------------------- Table 6. Results for the persistent version of the Essential CDS algorithm in mobile networks. The simple algorithm for computing BDRs (described in the Appendix) was also tried, for comparison to the Suurballe-Tarjan algorithm. The simple algorithm resulted in a larger number of BDRs in all cases, ranging from about 14% larger for 50 nodes and radius 0.3, to about 32% larger for 300 nodes and the same radius. The Suurballe- Tarjan algorithm is also fairly simple, and also runs in O(d^2) time, so it is the preferred algorithm. 12. Major Changes Changes from version 02 to version 03: - A flexible Hello protocol is presented that allows routers to send either full or differential Hellos, in which either full or partial 2-hop neighbor information is advertised periodically. Partial information consists of (Backup) Dependent Neighbors. - The rule for forming adjacencies has been modified so that an adjacency is formed between two routers if and only if one of the routers is a (Backup) Dependent Neighbor of the other one. Since Hellos advertise (Backup) Dependent Neighbors, each router Ogier Expires August 21, 2005 [Page 31] Internet-Draft MANET Extension of OSPF February 2005 knows which neighbors it should become adjacent with. - The Essential CDS algorithm has been modified so that a DR declares only a subset of its neighbors to be dependent and thus adjacent, thus reducing the number of adjacencies. - The CDS algorithm and the flooding procedure have been modified to distinguish between Dependent Neighbors and Backup Dependent Neighbors. - The concept of Min-Hop Dependent Neighbors has been introduced, to provide the option of flooding along min-hop paths, and to define a partial topology that provides min-hop path routing. - A new synchronization condition is defined as a requirement for neighbors that can be included in LSAs. - New simulation results for mobile networks are presented. 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. [Suurballe84] J.W. Suurballe and R.E. Tarjan. "A Quick Method for Finding Shortest Pairs of Disjoint Paths", Networks, Vol. 14, pp. 325-336. Ogier Expires August 21, 2005 [Page 32] Internet-Draft MANET Extension of OSPF February 2005 A.1. Detailed Pseudocode for the Essential CDS Algorithm The following detailed description of the Essential CDS Algorithm uses a breadth-first search (BFS) algorithm for Phase 1, and uses a variation of the Suurballe-Tarjan algorithm [Suurballe84] for finding pairs of node-disjoint paths in Phase 2. This algorithm runs in O(d^2) time, where d is the number of neighbors. A alternative algorithm for Phase 2, which is simpler but results in a larger number of BDRs, is given at the end of this section. The following describes the non-persistent version of the algorithm; the persistent version is obtained simply by replacing each occurrence of (RtrPri, RID) with (DRLevel, RtrPri, RID). In the following description, node i denotes the node performing the calculation. The BFS algorithm in Phase 1 uses a FIFO queue so that all nodes 1 hop from node s 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 s 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. Also, parent(u) will be equal to the parent of node u on the BFS tree, which is used in Phase 2. 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, and selects all of its neighbors as Dependent Neighbors. Else, proceed to step 1.2. 1.2. Compute a matrix of link costs c(u,v) for each pair of neighbors u and v as follows: If node u has a larger value of (RtrPri, RID) than node i, and node v is known to be a neighbor of node u, then set c(u,v) to 1. Otherwise, set c(u,v) to infinity. 1.3. Let s be the neighbor of node i that has the largest value of (RtrPri, RID). 1.4. Set hops(u) = infinity for all neighbors u other than s, and set hops(s) = 0. Initially, parent(u) is undefined for each neighbor u. Add node s to the FIFO queue. 1.5. While the queue is nonempty: Remove the node at the head of the queue; call it node u. For each neighbor v of node i such that c(u,v) = 1: If hops(v) > hops(u) + 1, then set hops(v) = hops(u) + 1, Ogier Expires August 21, 2005 [Page 33] Internet-Draft MANET Extension of OSPF February 2005 set parent(v) = u, and add node v to the tail of the queue. 1.6. If hops(u) is finite for all neighbors u of node i, then node i does not select itself as a DR. 1.7. Else, node i selects itself as a DR, and selects node s and each neighbor u with hops(u) = infinity to be Dependent Neighbors. Phase 2 (Backup DR Selection) If node i does not select itself as a DR, then the following steps are performed. 2.1. Compute a matrix of link costs c2(u,v) for each pair of neighbors u and v as follows: If c(u,v) is infinity, then set c2(u,v) to infinity. Otherwise set c2(u,v) = 1 + hops(u) - hops(v). 2.2. Set hops2(u) = infinity for all neighbors u other than s, and set hop2(s) = 0. Initially, all neighbors u are unlabeled. 2.3. Label node s. This divides the BFS tree (defined by the parents selected in Phase 1) into smaller unlabeled subtrees, one for each child of node s. For each pair u, v of nodes belonging to different subtrees: If hops2(v) > c2(u,v), then set hops2(v) = c2(u,v). 2.4. While there exists an unlabeled node with a finite value of hops2: 2.4.1. Let node k be the unlabeled node with the minimum value of hops2, and label node k. This divides the unlabeled subtree containing k into smaller unlabeled subtrees, one subtree (called the parent subtree) containing the parent of k if it exists and is unlabeled, and one subtree (called a child subtree) for each unlabeled child of node k. If the parent of k does not exist or is labeled, then continue with the next iteration of step 2.4. 2.4.2. For each node u in the parent subtree: If hops2(u) > hops2(k) + c2(k,u), set hop2(u) = hops2(k) + c2(k,u). For each node v in one of the child subtrees: If hop2(v) > hops2(k) + c2(u,v), set hop2(v) = hops2(k) + c2(u,v). If hop2(u) > hops2(k) + c2(v,u), set hop2(u) = hops2(k) + c2(v,u). Ogier Expires August 21, 2005 [Page 34] Internet-Draft MANET Extension of OSPF February 2005 2.5. If hops2(u) is finite for all neighbors u of node i, then node i does not select itself as a BDR. 2.6. Otherwise, node i selects itself as a BDR, and selects node s and each neighbor u with hops2(u) = infinity to be Dependent Neighbors. When Phase 2 terminates, hops2(u), if finite, will be equal to the total number of hops in both disjoint paths from s to u, minus 2 * hops(u). Thus, if hops2(u) = 0, then both disjoint paths have the same length hops(u). We do not give the procedure for constructing the disjoint paths themselves, since this is not required for the CDS algorithm. We note that in step 2.4.2, the nodes of each unlabeled subtree can be found using a depth-first search (DFS), starting from the root of the subtree, and using labeled nodes to define the boundary of the subtree. The tree structure is defined by the values of parent(u) computed in Phase 1, which can be used to define a list of children for each node. The algorithm runs in O(d^2) time, since each pair of nodes (u,v) is considered only once in step 2.4.2. We next describe an alternative algorithm for Phase 2, which is simpler but typically results in a larger number of BDRs, since it imposes a more restrictive condition on the disjoint paths, i.e., the second path is not allowed to use any intermediate nodes of the BFS tree computed in Phase 1. Alternative Algorithm for Phase 2 2.1. Compute a matrix of link costs c2(u,v) for each pair of neighbors u and v as follows: If c(u,v) is infinity, or if u is an intermediate node of the BFS tree computed in Phase 1 (i.e., is not s and is the parent of some other node), then set c2(u,v) to infinity. Otherwise set c2(u,v) = 1. 2.2. Run BFS to compute min-hop paths from node s to the other neighbors of node i, using the link costs c2(u,v). Let hops2(u) equal the number of hops in the resulting min-hop path from s to u, or infinity if no finite cost path exists. 2.3. Note that step 2.2 does not compute disjoint paths to neighbors of node s. For each neighbor u of node i that is a neighbor of node s: If there exists another neighbor v of node i that is a neighbor of both nodes s and u, and has a larger value of (RtrPri, RID) than node i, then set hops2(u) = 2; else set hops2(u) = infinity. Ogier Expires August 21, 2005 [Page 35] Internet-Draft MANET Extension of OSPF February 2005 2.4. If hops2(u) is finite for all neighbors u of node i, then node i does not select itself as a BDR. 2.5. Otherwise, node i selects itself as a BDR, and selects node s and each neighbor u with hops2(u) = infinity to be Dependent Neighbors. 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 August 21, 2005 [Page 36]