Mobile Ad Hoc and OSPF Working Groups R. Ogier Internet-Draft SRI International November 19, 2003 Alternative Designs for OSPF Extensions for Mobile Ad Hoc Networks draft-ogier-manet-ospf-extension-00.txt Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC 2026. 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." Abstract This draft discusses alternative candidate techniques for the design of an an extension of OSPF to support mobile ad-hoc network (manet) interfaces. Several design decisions need to be made before such an extension can be specified, including (1) defining the set of relay nodes used for flooding LSAs, (2) defining the set of LSAs that each node is responsible for relaying/reporting, and (3) defining the mechanism used to efficiently deliver each LSA to all nodes. Ogier, et al. Expires May 19, 2004 [Page 1] Internet-Draft OSPF Extensions for Manets November 2003 1. Introduction The document [Baker03] provides a good statement of the goals and issues that need to be addressed to extend OSPF [OSPF] to work well in a network that contains both traditional interfaces (e.g., Ethernet and point-to- point) and mobile ad-hoc network (manet) interfaces. This draft discusses alternative protocol designs and techniques for such an extension, which appear promising for satisfying the goals stated in [Baker03]. Several decisions need to be made regarding the design of a proactive protocol, before we can write a detailed specification. Some of these decisions may require further discussions, analysis, and/or simulations before the final choice is made. In particular, we need to: - Define the set of relay nodes, or relay node set (RNS), used for flooding each LSA. The RNS may or may not depend on the originator of the LSA. Examples include multipoint relays (MPRs), which can be selected in different ways; a connected dominating set (CDS); and the non-leaf nodes of a min-hop spanning tree rooted at the originator. - Define the set of LSAs (or originators) that each relay node is responsible for relaying/reporting. To ensure reliable delivery to all nodes, it is important for a node to know exactly what LSAs it is responsible for reporting to existing and new neighbors. (This is not the case when the decision to forward an LSA is based only on the previous hop and not the originator.) - Define the mechanism used to efficiently deliver each LSA to all nodes. Should unreliable or reliable flooding be used? If reliable flooding is used, what mechanism should be used? (The OSPF mechanism based on ACKs and database exchange with each new neighbor generates too much control traffic.) 2. Defining the Relay Node Set The relay node set (RNS) may or may not depend on the originator of the LSA being relayed. An example of an origin-independent RNS is a connected dominating set (CDS), i.e., a connected subset of nodes such that every node in the network is a neighbor of at least one node in the subset. Two examples of an origin-dependent RNS are MPRs and the non-leaf nodes of a min-hop tree rooted at the originator. These three choices, and variations of them, are discussed in the following subsections. Ogier, et al. Expires May 19, 2004 [Page 2] Internet-Draft OSPF Extensions for Manets November 2003 2.1 Connected Dominating Set A dominating set is a subset of nodes, called dominators, such that each node is a neighbor of at least one dominator. In a connected dominating set (CDS), these nodes form a connected graph, which allows them to be used for efficient flooding, especially if the number of nodes in the CDS is small. To flood an LSA, it is only necessary for each node of a CDS to broadcast the LSA to its neighbors. The nodes of a CDS have also been called "overlapping relays". Several algorithms have been proposed for constructing a small CDS, e.g., [Das97][Kozat01][Wu01][Lin03b]. A simple algorithm for constructing a relatively small CDS can be based on 2-hop topology information, e.g. [Wu01][Lin03b]. However, this draft does not intend to recommend or survey candidate CDS algorithms, but rather to discuss the possibility of using a CDS to flood LSAs in a manet extension of OSPF. One advantage of using a CDS for flooding LSAs is that it is a simple solution, and each node is responsible for relaying all LSAs originating from routers in the same area (since a CDS is an origin- independent RNS). A CDS node is a natural generalization of a Designated Router (DR): for example, adjacencies can be formed between each CDS node and its neighbors. Using a CDS also allows OSPF Hello packets to be used without modification. The DR field can be used to identify a CDS node, which can be the sending node itself. The Router Priority (used for electing a DR in OSPF), can be used to indicate the priority for selecting the router to be in the CDS. A possible disadvantage of using a CDS as the RNS, compared to either MPRs or a min-hop tree rooted at each origin, is that a min-hop path between two given nodes may not exist that uses only nodes of the CDS as intermediate nodes. I.e., the shortest route between two nodes may have to use non-RNS nodes as relays. However, this is not necessarily a disadvantage in OSPF, since each node knows the full topology and thus can compute the shortest path to all other nodes in the same area. I.e., there is no disadvantage if the CDS is used only for flooding and not for selecting routes. 2.2 Originator-Based Min-Hop Trees The RNS for a given LSA can consist of the non-leaf nodes of a min- hop tree rooted at the LSA originator. We discuss two ways that a node can learn that it is such a non-leaf node, and then discuss an approximate method that is equivalent to selecting MPRs. Ogier, et al. Expires May 19, 2004 [Page 3] Internet-Draft OSPF Extensions for Manets November 2003 In one such method, each node computes its next-hop, or parent, on a min-hop path to each originator u, and informs its parent of this decision. All nodes compute the min-hop paths consistently by using minimum node ID to break ties. A parent determines that it is a non- leaf node if it has no children. This method was used in the original, full-topology version of TBRPF [Bellur99]. The main drawback of this method is that the reporting of parents generates a large amount of control traffic. It is possible to avoid the overhead of reporting parents, by having each node i compute the min-hop paths from each neighbor j to each originator u. If the path from neighbor j to originator u goes through node i, then node j is a child, and node i is a non-leaf of the tree rooted at node u. The main drawback of this method is that it requires additional processing, but this may be acceptable with today's faster processors. This processing can be reduced, at the expense of some redundancy, by having each node compute only the min-hop paths from each neighbor to each other neighbor, as is done in TBRPF [Ogier03] and other protocols [Wu01][Lin03a]. Some of these protocols [Lin03a] use node degree, instead of or in addition to node ID, to break ties, which can reduce the number of relays. A node i then determines that it is a non-leaf (i.e., in the RNS) for originator u, if the computed path from some neighbor k to the next-hop p(u) on the min-hop path to u goes through node i. The above method actually involves a method for computing MPRs. If node i determines that the min-hop path from some neighbor k to another neighbor j goes through node i, then it can be said that node i is an MPR of neighbor j, or equivalently, that neighbor j is an MPR source of node i. In this method, MPRs select themselves, unlike other methods [Spagnolo03] in which each node selects a subset of its neighbors as MPRs. 2.3 Multipoint Relays A set of multipoint relays (MPRs) for node i is defined to be a subset of the 1-hop neighbors of node i that covers all 2-hop neighbors of node i, i.e., each 2-hop neighbor is a neighbor of at least one of the MPRs. As discussed above, there are different ways to compute MPRs. For example, a node can select itself as an MPR, or can select a subset of its neighbors as MPRs. If node i is an MPR of node j, we say that node j is an MPR source (or selector) of node i. There are also different ways in which MPRs can be used to flood Ogier, et al. Expires May 19, 2004 [Page 4] Internet-Draft OSPF Extensions for Manets November 2003 LSAs. For example, a node can decide to forward only LSAs that are received from an MPR source (as in [Spagnolo03]). Alternatively, a node can decide to forward an LSA only if the next hop p(u) on the min-hop path to the originator u is an MPR source. The latter method has the advantage that the set of LSAs (or originators) that an MPR is responsible for forwarding is well-defined, which, as discussed in Section 3, is important for achieving reliable flooding. The latter method may also result in a smaller relay node set (RNS), thus reducing the number of transmissions required for flooding, although simulations are needed to verify this. Simulations are also needed to determine whether MPRs should select themselves or be selected by neighbors. These simulations should not only consider the size of the resulting RNS, but should also consider the overhead required for reporting the selected MPRs, and the time required to select a new MPR following a link breakage. If MPRs select themselves, then it is not necessary to report MPRs in Hello messages, thus reducing overhead. Also, faster recovery from link breakages is possible if MPRs select themselves. Finally, reference [Lin03] describes a modification of OLSR in which MPRs select themselves, and shows by simulations that this method results in a smaller RNS. In fact, MPRs can be considered analogous to the Designated Router (DR) of OSPF. In OSPF, DRs select themselves. (The node with the lexicographically largest value of (router priority, router ID) selects itself as DR, unless another node has already selected itself as DR.) Thus, if MPRs are used in an extension of OSPF, it would be natural for MPRs to also select themselves. The reason why OSPF includes the selected DR in Hello messages is so that another node does not select itself as DR if a DR already exists, thus reducing the frequency of DR changes. Something similar can be done to reduce the frequency of MPR changes, assuming that MPRs select themselves. Since an node is an MPR with respect to some neighbor (the MPR source), each node can advertise its MPR sources, and this information can be used by each neighbor to avoid selecting itself as an MPR for a given MPR source if it the existing MPRs that it knows about are sufficient. (For example, this could be a modification of the algorithm described in [Lin03] in which MPRs select themselves.) However, it may not be important to reduce the frequency of MPR changes, if the protocol is designed so that MPR changes do not generate much additional control traffic. This is the case if the protocol uses either unreliable, periodic flooding of LSAs, or the reliable flooding mechanism proposed in Section 6. Therefore, if MPRs select themselves (or if a CDS is used for flooding), then it Ogier, et al. Expires May 19, 2004 [Page 5] Internet-Draft OSPF Extensions for Manets November 2003 may not be necessary for Hello message to advertise MPRs or MPR sources. 3. Defining the Set of LSAs That Each Node Relays The reliable flooding mechanism proposed in the next section requires each node to know the set of LSAs (or originators) that it is responsible for relaying/reporting to existing and new neighbors. This will be called the reported originator set (ROS). This knowledge is required for reliable flooding. For example, if two nodes become neighbors, it is important to know what topology information each node must report to the other node. If a CDS is used for the RNS, then each CDS node is responsible for reporting all LSAs originating from the same area. However, if MPRs are used, then each MPR node is only responsible for reporting LSAs originating from a subset of the nodes in the area. In the OSPF extension proposed in [Spagnolo03], each node does not explicitly know exactly what LSAs it is responsible for relaying, i.e., each node does not know its ROS. Instead, an LSA is forwarded only if it was received from an MPR selector, regardless of the LSA originator. Exact knowledge of the ROS is not required, since their extension uses unreliable, periodic flooding. (We note that a node can keep track of the originators for LSAs that were recently forwarded, but this may be inaccurate and outdated since flooding is unreliable and recent topology changes may not be reflected.) If MPRs are used for flooding, a node can compute its ROS as follows. A node u belong to ROS if and only if the next hop on the lexicographic min-hop path (from the local node) to node u is an MPR source. By "lexicographic" we mean that node ID is used to break ties when multiple min-hop paths exist. Lexicographic min-hop paths are required so that all nodes compute the paths consistently. Note that these paths are used for the purpose of computing the ROS, and it is not necessary to use them for routing packets. If originator-based min-hop trees are used for flooding, then a node u belongs to the ROS if and only if the local node is a non-leaf node of the min-hop tree rooted at node u. 4. Reliable vs. Unreliable Flooding One decision to make is whether to use unreliable, periodic flooding of LSAs, as proposed in [Spagnolo03]. As discussed in [Baker03], it is a waste of resource to repeatedly flood an LSA to nodes that have already received it. On the other hand, it has not yet been proven that reliable flooding can result in better performance in highly Ogier, et al. Expires May 19, 2004 [Page 6] Internet-Draft OSPF Extensions for Manets November 2003 dynamic, dense networks. If unreliable, periodic flooding is used, then the period must be relatively small, so that an LSA not received on the first try will have a high probability of being received within a reasonable delay. However, a small period will result in a large amount of control traffic. One argument for using unreliable, periodic flooding in manets is as follows. If a node has 100 neighbors, and node mobility is moderate, then there is a good chance that at least one neighbor will be lost within any 10-second interval. Therefore, it will be necessary to generate an LSA every 10 seconds anyway. Of course, this argument is not valid if a node has less than 10 neighbors and nodes are slow moving or stationary. Therefore, it would be useful to use a reliable flooding mechanism at least in these cases, and perhaps switch to unreliable, periodic flooding only when the average number of neighbor changes per second is above some threshold. Section 5 describes a simple way to dynamically switch between reliable and unreliable flooding in OSPF. However, the above argument for using unreliable, periodic flooding in manets also becomes invalid if differential LSAs are allowed, which report only the *changes* in the LSA. Thus, if a node loses one of its 100 neighbors, it only needs to report the loss of one neighbor in a differential LSA (instead of the full LSA which includes all neighbors). Full LSAs can also be transmitted periodically with a relatively large period as in OSPF, for added robustness. The reliable flooding mechanism described in the next section allows the use of differential LSAs as an option. 5. Hybrid Reliable/Unreliable Flooding in OSPF The OSPF flooding process uses ACKs to deliver each transmitted LSA reliably to all adjacent neighbors. ACKs can be delayed and aggregated, so that that a single ACK packet can be sent to acknowledge several LSAs received from different neighbors. This section describes a simple method that allows the ACKs for a given LSA to be suppressed when new instances of the LSA are generated frequently. In such cases, ACKs are not necessary (as explained below), and thus bandwidth can be saved by suppressing them. As suggested in [Baker02], we assume that each neighbor on a manet interface is represented as a point-to-point link within a router LSA. Thus, a new instance of the router LSA, with a larger sequence Ogier, et al. Expires May 19, 2004 [Page 7] Internet-Draft OSPF Extensions for Manets November 2003 number, is originated when a neighbor changes state. If at least one neighbor changes state every MinLSInterval (equal to 5 seconds in OSPF), then the router will originate and flood a new LSA every 5 seconds. Clearly, in this case, it should not be necessary for any router to send an ACK in response to such an LSA, since a new instance of the LSA will be received approximately every 5 seconds. We first describe what happens in OSPF when ACKs are suppressed, and then we describe how a node can decide whether or not to suppress ACKs for a given LSA. In OSPF, if a router transmits an LSA but does not receive an ACK from all neighbors, the router will retransmit the current instance of the LSA every RxmtInterval seconds, until a new instance of the LSA is received. (In OSPF, a retransmitted LSA is unicast to each neighbor that did not ACK, but as discussed below, the LSA should be broadcast to all neighbors if no ACK was received from any neighbor.) For this discussion, we will assume that RxmtInterval is larger than MinLSInterval (5 seconds), so that if a new instance of the LSA is received in about 5 seconds, it will be transmitted before the previous instance of the LSA is retransmitted. (If the new instance is not received due to unreliable links, the old instance will still be retransmitted after RxmtInterval.) Therefore, if ACKs are suppressed for a given LSA, then each instance of the LSA will be flooded repeatedly and unreliably. When a new instance is originated, the new instance will be flooded instead of the old instance. This works, and shows that ACKs can be suppressed in OSPF for LSAs that are updated frequently. A router can decide to suppress ACKs for a given LSA if a new instance of the LSA (with a larger sequence number) is usually received every RxmtInterval seconds (e.g., 5-10 seconds). An exponential moving average of the time between LSA updates, or of the number of LSA updates during the last RxmtInterval seconds, can be maintained for each LSA. Two thresholds can be defined to employ hysteresis in deciding whether to suppress ACKs for a given LSA. We now discuss the question of whether retransmitted LSAs should be broadcast or unicast on manet interfaces. If neighbors are not suppressing ACKs, then broadcasting results in ACKs from all neighbors, even neighbors that already sent an ACK for the same LSA. Therefore, if an ACK has been received from all neighbors except one, then the retransmitted LSA should be unicast to that one neighbor. At the other extreme, if no neighbor has ACKed (whether or not neighbors are suppressing ACKs), then the retransmitted LSA should be broadcast to all neighbors. Therefore, the decision of whether to unicast or broadcast the transmitted LSA should depend on the number Ogier, et al. Expires May 19, 2004 [Page 8] Internet-Draft OSPF Extensions for Manets November 2003 of neighbors that did not ACK. Because an LSA is usually much larger than an LSA ACK, a good rule might be to broadcast the retransmitted LSA if at least two neighbors did not ACK. (This will always be the case if at least two neighbors are suppressing ACKs.) 6. Defining a Reliable Flooding Mechanism 6.1 Reliable Flooding in OSPF OSPF uses a reliable flooding mechanism that uses ACKs to deliver an LSA reliably to all adjacent neighbors, and employs a Database Exchange Process to ensure that two routers that become neighbors have synchronized databases (and become "fully adjacent"). Both the ACKs and the Database Exchange Process generate a substantial amount of control traffic, so a more efficient mechanism for reliable flooding is needed for manets. One improvement, suggested in [Baker02], is to use implicit ACKs, so that a received LSA is implicitly ACKed if/when this LSA is forwarded. However, this method would only apply to nodes in the relay node set, which should include only a small percentage of all nodes. All non-relay nodes would still be required to send an explicit ACK. It is also possible to use NACKs instead of ACKs. This would reduce the ACK/NACK traffic assuming most neighbors receive each transmitted Link State Update packet (containing LSAs), but it would also require *all* neighbors to receive each transmitted Link State Update packet, including neighbors that have already received the LSAs from another relay. Also, ACKs or NACKs used in conjunction with MPRs are not sufficient to provide reliable flooding, since some nodes may fail to receive some LSAs if the MPR selection changes in response to link breakages. An additional database exchange would be needed not only with new neighbors, but also when a node becomes an MPR. 6.2 Reliable Flooding Using Periodic Database Description Packets This section proposes a reliable flooding mechanism for OSPF on manet interfaces. In this mechanism, each relay node (e.g., CDS node) transmits each LSA instance only once, unless some neighbor does not receive the LSA. Duplicate detection of LSAs is done as in OSPF, based on the LSA sequence number in the database. This mechanism uses only packet types already defined in OSPF. In the OSPF Database Exchange Process, two nodes that become neighbors first send Database Description (DD) Packets to each other, Ogier, et al. Expires May 19, 2004 [Page 9] Internet-Draft OSPF Extensions for Manets November 2003 to allow each node to determine what LSAs it needs (if any) from the other node. A DD packet does not contain LSAs, but only LSA headers, where each LSA header identifies the instance of the LSA via the LS sequence number. Sending DD packets reliably to each new neighbor can generate a lot of control traffic in manets, where typically a node will have at least one new neighbor every few seconds. A better approach in such networks is to periodically broadcast a set of DD packets on each manet interface (unreliably). This technique is used in IS-IS, in which the designated router of a broadcast network periodically broadcasts a set of Complete Sequence Numbers (CSN) packets [RFC1142], which perform essentially the same function as DD packets. We therefore propose to borrow a technique from IS-IS, and fit it into the framework of OSPF. An alternative approach would be to design an extension to IS-IS instead of OSPF. If a CDS is used to relay LSAs, then each CDS node periodically broadcasts (on all manet interfaces) a complete set of DD packets that contains the headers of all LSAs originating from the same area. However, if MPRs are used to relay LSAs, then each MPR periodically broadcasts a partial set of DD packets that contains only the headers of LSAs originating from the reported originator set (ROS). In addition, each non-CDS router (which originates its own router LSA when a neighbor changes state) periodically broadcasts (on all manet interfaces) a DD packet that includes the header of the current instance of its own router LSA. This ensures the reliable delivery of the router LSA to all neighbors, including CDS neighbors which will relay the LSA. Note that if unreliable, periodic flooding is used, each relay node would periodically broadcast all LSAs (not just LSA headers) originating from nodes in the ROS. In general, LSAs are much larger than LSA headers. For example, an LSA that describes 100 neighbors will have at least 1200 bytes for IPv4 (although some compression is possible for manets), compared to an LSA header which is only 20 bytes. Thus, the proposed method generates much less control traffic than unreliable, periodic flooding, at least when topology changes are not frequent. The proposed periodic transmission of DD packets serves two purposes: - The reliable delivery of LSAs to neighbors. - The exchange of LSAs between new neighbors. In either case, if a router receives a DD packet from a neighbor that includes an LSA header with a larger sequence number than the Ogier, et al. Expires May 19, 2004 [Page 10] Internet-Draft OSPF Extensions for Manets November 2003 corresponding LSA in the router's database (which indicates that the neighbor is relaying or originating a more recent instance of the LSA), then the router requests the LSA via Link State Request packet (as in OSPF). This can happen either because the router missed a previous transmission of the LSA (due to an unreliable link), or because the router recently became a neighbor of a CDS node, or because a neighbor recently became a CDS node. Note that it is possible for a router to receive a given LSA from more than one neighbor, e.g., if it has more than one CDS neighbor. In this case, the router only needs to request the LSA from one of the neighbors (e.g., the one that it has selected as its dominator). In summary, a router can receive a particular LSA from any neighbor that includes the LSA in a Link State Update packet, and can request the LSA from any neighbor that includes the LSA header in periodic DD packets. On manet interfaces, DD and Link State Update packets are always broadcast to all neighbors (assuming this method is used), while LS Request packets are always unicast to a single neighbor. A node does not respond immediately to each Link State Request packet, but waits for some time (e.g., based on a periodic timer) and then sends a Link State Update packet that may contain LSAs in response to several Link State Requests from different neighbors. Thus, responses to Link State Requests are aggregated in order to to reduce control traffic. 6.3 Reducing the Number of Link State Requests One might argue that a lot of LS Request packets will be sent on manet interfaces, due to failed transmissions, resulting in a lot of control traffic. (Note however that having each neighbor acknowledge each LSA would generate much more control traffic.) One factor that mitigates this is that a node can receive the same LSA from different neighbors, thus increasing the probability that it will receive a given LSA without having to send a LS Request. This can be ensured by selecting the CDS redundantly, so that each node is a neighbor of at least two CDS nodes. The Backup DR field of the OSPF Hello packet can be used to identify a redundant CDS node. The number of LS Requests can also be reduced by using multiple transmissions, i.e., when a node transmits an Link State Update packet, it can transmit it multiple times, to increase the probability that all neighbors receive it. The number of such retransmissions can depend on the recent history of LS Requests received from neighbors. Ogier, et al. Expires May 19, 2004 [Page 11] Internet-Draft OSPF Extensions for Manets November 2003 6.4 Differential LSAs As discussed in Section 4, control traffic can be reduced by using differential LSAs, which report only differences (new links, lost links, and metric changes) between the current instance and a previous instance of an LSA, instead of reporting the entire LSA. For example, if a node has 100 neighbors and loses one of them, it would be wasteful to generate a full LSA with 99 neighbor IDs, when the loss could be reported in a differential LSA containing a single neighbor ID. A differential LSA includes two LS sequence numbers sn1 < sn2, instead of one, with the following meaning. Assuming you have an instance of the LSA whose sequence number is at least sn1 but less than sn2, then incorporating the changes in this LSA will give you the correct LSA with sequence number sn2. The checksum in the differential LSA is the checksum for the entire LSA with sequence number sn2. The LS Request packet is also modified to include an LS sequence number for each requested LSA, indicating that the sending node has the instance of the LSA with this sequence number. If a node receives a LS Request for the same LSA from different neighbors, but with different sequence numbers, the node will respond by broadcasting a differential LSA with sn1 equal to the minimum of the requested sequence numbers, or by transmitting a full LSA if the node does not have sufficient information to generate a differential LSA. To generate a differential LSA, a node must store additional sequence number information for each link of the LSA, or must store differential LSAs that it recently transmitted. At a minimum, each node should store each transmitted differential LSA at least until it transmits its next few periodic Database Description packets, so that it can send a differential LSA in response to LS Requests. The exact specification for using differential LSAs requires some additional work. However, it is clear that their use can reduce the amount of control traffic, although simulations are needed to determine how much improvement can be achieved. Also note that the use of differential LSAs can be optional. 6.5 Adjacencies In OSPF, an adjacency is formed between two nodes connected by a point-to-point link, and between each DR or Backup DR and each of its neighbors. In OSPF, adjacent neighbors perform a database exchange to synchronize their databases. When this exchange is complete, the neighbors are said to be "fully adjacent". Ogier, et al. Expires May 19, 2004 [Page 12] Internet-Draft OSPF Extensions for Manets November 2003 This section proposes a modified definition of fully adjacent for links between a CDS node and its neighbors. In OSPF, the database exchange between two adjacent nodes is symmetric, i.e., each node ensures that it has the same instance of each LSA that is in the other node's database. However, this requires that both nodes, including non-CDS nodes, transmit a complete set of DD packets. To reduce overhead due to unnecessary DD packets, we propose that only CDS nodes transmit a complete set of DD packets. Non-CDS nodes can transmit a short DD packet that includes only the header of the node's own router LSA. This is proposed whether DD packets are sent periodically as described above, or whether DD packets are sent only to newly adjacent neighbors (which would be the case if LSA ACKs are used). Thus, a link (i,j) between a non-CDS node i and a CDS node j is defined to be fully adjacent if node i has the same instance of each LSA that is in node j's database. For the CDS node j to consider the reverse link (j,i) to be fully adjacent, node j only needs to have the current instance of the router LSA originated by the non-CDS node i. Thus, for manet interfaces, an adjacency between a CDS node and a non-CDS node is asymmetric, which makes sense, since only the CDS nodes are responsible for forwarding LSAs. In OSPF, a link must be fully adjacent before it is advertised in an LSA. It may be beneficial to also require this for manet interfaces, but this requires further investigation. 7. Conclusions Alternative candidate techniques were discussed for extending OSPF to support manet interfaces. Although recommendations were made in favor of some of these techniques, additional discussions, analysis, and/or simulations are needed before deciding which methods to include in the final design. If it is an important goal to minimize the changes to OSPF, then it may be preferable to use a CDS instead of MPRs, since a CDS node is a natural generalization of a designated router, and the OSPF Hello packet can be used without modification, except that the DR field is used to identify a CDS node. Thus, in a simple extension of OSPF, adjacencies can be formed between each CDS node and each of its neighbors. In such a simple extension, reliable flooding can be performed either using the periodic broadcast of Database Description packets as described in Section 6.2, or using ACKs as in OSPF. In the latter case, ACKs can be suppressed as described in Section 5 when new instances of an LSA are generated frequently. Ogier, et al. Expires May 19, 2004 [Page 13] Internet-Draft OSPF Extensions for Manets November 2003 References [Baker02] F. Baker. "An Outsider's View of MANET", Internet-Draft (work in progress), draft-baker-manet-review-01.txt, March 2002. [Baker03] F. Baker et al. "Problem Statement for OSPF Extensions for Mobile Ad Hoc Routing, Internet-Draft (work in progress), September 2003. [Bellur99] B. Bellur and R. Ogier. "A Reliable, Efficient Topology Broadcast Protocol for Dynamic Networks", Proc. IEEE INFOCOM, March 1999. [Das97] B. Das and V. Bhargavan, "Routing in ad-hoc networks using minimum connected dominating sets," Proc. IEEE International Conference on Communications, vol. 1, pp. 376-380, 1997. [Kozat01] U.C. Kozat, G. Kondylis, B. Ryu, M.K. Marina. "Virtual dynamic backbone for mobile ad hoc networks," Proc. IEEE International Conference on Communications (ICC), vol. 1, pp. 250-255, 2001. [Lin03a] T. Lin, S.F. Midkiff, and J.S. Park. "A Framework for Wireless Ad Hoc Routing Protocols", IEEE WCNC, March 2003. [Lin03b] T. Lin, S. F. Midkiff, and J. S. Park. "Approximation Algorithms for Minimal Connected Dominating Sets and Application with Routing protocol in Wireless Ad Hoc Network," IEEE International Performance Computing and Communications Conference (IPCCC), pp. 157-164, 2003. [Ogier03] R. Ogier, F. Templin, and M. Lewis. "Topology Dissemination Based on Reverse Path Forwarding", Internet-Draft (work in progress), draft-ietf-manet-tbrpf-11.txt, October 2003. [OSPF] J. Moy. "OSPF Version 2", RFC 2328, April 1998. [RFC1142] D. Oran. "OSI IS-IS Intra-Domain Routing Protocol", RFC 1142, February 1990. [Spagnolo03] J. Ahrenholz, T. Henderson, P. Spagnolo, E. Baccelli, T. Clausen, and P. Jacquet. "OSPFv2 Wireless Interface Type", Internet-Draft (work in progress), draft-spagnolo-manet-ospf- wireless-interface-00, October 2003. [Wu01] J. Wu and H. Li. "A Dominating-Set-Based Routing Scheme in Ad Hoc Wireless Networks", Telecommunication Systems, Vol. 18, pp. 31-36, 2001. Ogier, et al. Expires May 19, 2004 [Page 14] Internet-Draft OSPF Extensions for Manets November 2003 Authors' Addresses Richard G. Ogier SRI International 333 Ravenswood Ave. Menlo Park, CA 94025 USA Phone: +1 650 859-4216 Fax: +1 650 859-4812 EMail: ogier@erg.sri.com Ogier, et al. Expires May 19, 2004 [Page 15]