MANET and OSPF Working Groups Internet-Draft R. Ogier Expires: January 19, 2005 July 19, 2004 Alternative Designs for OSPF Extensions for Mobile Ad Hoc Networks draft-ogier-manet-ospf-extension-01.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 (flood) each LSA to all nodes. Ogier Expires January 19, 2005 [Page 1] Internet-Draft OSPF Extensions for Manets July 2004 1. Introduction The document [Baker03] provides a good statement of the goals and issues that need to be addressed to extend OSPF [RFC2328] 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 Expires January 19, 2005 [Page 2] Internet-Draft OSPF Extensions for Manets July 2004 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][Adjih02]. A simple algorithm for constructing a relatively small CDS can be based on 2-hop neighbor information, e.g. [Wu01][Lin03b]. 2-hop neighbor information can be obtained from the LSAs originated from all neighbors, as is done in [Chandra04] and TBRPF [RFC3684]. It is also possible to obtain 2-hop neighbor information by modifying Hello packets to distinguish between 1-way and 2-way neighbors, as proposed in [Ahrenholz04]. Reference [Adjih02] presents and evaluates CDS algorithms that require the computation of MPRs; these algorithms are actually based on 3-hop neighbor information, since a node uses 2-hop neighbor information to select MPRs, and each node decides whether it is in the CDS based on the MPR selection of its neighbors. 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 Ogier Expires January 19, 2005 [Page 3] Internet-Draft OSPF Extensions for Manets July 2004 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. 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 [RFC3684] 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 [Ahrenholz04] 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 Ogier Expires January 19, 2005 [Page 4] Internet-Draft OSPF Extensions for Manets July 2004 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 LSAs. For example, a node can decide to forward only LSAs that are received from an MPR source (as in [Ahrenholz04]). 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 Ogier Expires January 19, 2005 [Page 5] Internet-Draft OSPF Extensions for Manets July 2004 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 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 [Ahrenholz04], 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 Ogier Expires January 19, 2005 [Page 6] Internet-Draft OSPF Extensions for Manets July 2004 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 [Ahrenholz04]. 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 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 Section 6 allows the use of differential LSAs as an option. 5. Hybrid Reliable/Unreliable Flooding in OSPF OSPF uses reliable flooding to disseminate LSAs. ACKs are used 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.) As suggested in [Baker02], we assume that each neighbor Ogier Expires January 19, 2005 [Page 7] Internet-Draft OSPF Extensions for Manets July 2004 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 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 to flood each LSA instance reliably, since a new instance of the LSA will be received approximately every 5 seconds. This section describes a simple method that allows the originator of an LSA to dynamically decide whether each instance of the LSA is flooded reliably ("reliable mode") or unreliably ("unreliable mode"), depending on how frequently the LSA is changing. (We discuss below how to measure this.) The originator accomplishes this by setting a new option bit that indicates whether the LSA is "ackable" (in reliable mode) or "non-ackable" (in unreliable mode). An ackable LSA must be flooded reliably (using ACKs) as in OSPF. A non-ackable LSA is never ACKed, and the same instance is never retransmitted. In unreliable mode, a new instance of a non-ackable LSA is originated every MinLSInterval seconds. When switching from unreliable to reliable mode, an ackable LSA must be originated whether or not any change has occurred since the last (unreliable) LSA instance. (As discussed below, hysteresis should be used to avoid frequent switching between the two modes.) The advantage of unreliable mode is that we avoid the overhead due to ACKs and retransmitted LSAs. An originator should use unreliable mode only if LSAs would be generated almost every MinLSInterval anyway (i.e., the network is highly mobile), so that less overhead is generated in unreliable mode than in reliable mode. To reduce overhead further, it is possible to use a period larger than MinLSInterval in unreliable mode (call this PeriodicLSInterval), although this would slow down the dissemination of topology information and thus slow down the network's reaction to topology changes when mobility is high (exactly when we need a fast response time). However, this may be necessary if the overhead is too large for the network to handle. For this reason, the reliable flooding method of Section 6 may be a better solution (since it avoids both ACKs and periodic flooding). As mentioned above, unreliable mode should be used for a given LSA only if it generates less overhead than reliable mode, which will be the case if a change to the LSA almost always occurs every MinLSInterval (or PeriodicLSInterval) seconds. To make this decision, the originator can maintain an exponential moving average (EMA) that estimates the probability that the LSA will change within MinLSInterval seconds, based on how often this has occurred in the Ogier Expires January 19, 2005 [Page 8] Internet-Draft OSPF Extensions for Manets July 2004 recent past. Other measurements could instead be used, such as an EMA that measures the average number of neighbor changes per MinLSInterval, or the average time between neighbors changes. If the originator is in reliable mode, it transitions to unreliable mode if the EMA goes above some threshold. If the originator is in unreliable mode, it transitions to reliable mode if the EMA goes below a possibly different threshold. To avoid frequent switching between the two modes, hysteresis should be employed, e.g., by choosing the second threshold to be smaller than the first one. Simulations can be used to evaluate alternative mechanisms for deciding whether to use reliable or unreliable mode. In [Spagnolo04], a mechanism is described and evaluated in which the originator decides dynamically whether to send a given LSA on an event-driven basis (as in OSPF) or on a periodic basis (where the period could be greater than MinLSInterval). This mechanism assumes that all LSAs are ackable and therefore uses only reliable flooding, but saves overhead by sending LSAs less frequently (periodically) when neighbor changes are frequent. Instead of using an EMA, the method *predicts* whether a neighbor change will occur soon, thus allowing an LSA to be sent earlier (on an event-driven basis) if no additional neighbor changes are predicted to occur within the next period. Prediction is clearly helpful, e.g., for reducing the LSA latency (by allowing an LSA to be sent earlier if no additional neighbor changes are predicted). However, simulations are needed to determine whether the use of prediction will significantly improve the performance of the hybrid reliable/unreliable flooding method described above. 6. Defining a Reliable Flooding Mechanism 6.1 Reliable Flooding in OSPF In addition to using ACKs for the reliable flooding of LSAs, OSPF 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. Ogier Expires January 19, 2005 [Page 9] Internet-Draft OSPF Extensions for Manets July 2004 Also, ACKs 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. The OSPF extension proposed in [Chandra04] overcomes this problem by requiring even non-MPR nodes to forward LSAs when necessary. However, such techniques add complexity and involve significant changes to OSPF. 6.2 Reliable Flooding Using Periodic Database Description Packets This section proposes a reliable flooding mechanism for OSPF on manet interfaces, which reduces overhead by avoiding the use of LS ACKs. 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, 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). (The ROS for MPR flooding is defined in Section 3.) 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 Ogier Expires January 19, 2005 [Page 10] Internet-Draft OSPF Extensions for Manets July 2004 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 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 a Link State Request packet (as in OSPF). (We note that such a request for an LSA is equivalent to a NACK, which informs the neighbor that the LSA has not been received.) 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 Ogier Expires January 19, 2005 [Page 11] Internet-Draft OSPF Extensions for Manets July 2004 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. 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. TBRPF [RFC3684] uses both differential Hello messages and differential LSAs to reduce overhead in highly mobile networks. Differential (or incremental) Hello packets are also used in the OSPF extension for manets proposed in [Chandra04]. 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. Ogier Expires January 19, 2005 [Page 12] Internet-Draft OSPF Extensions for Manets July 2004 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". 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 Ogier Expires January 19, 2005 [Page 13] Internet-Draft OSPF Extensions for Manets July 2004 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, hybrid reliable/unreliable flooding can be used as described in Section 5, to reduce overhead by not requiring reliable flooding when LSAs are updated frequently. 8. Summary of Changes Changes from version 00 to version 01: - The hybrid reliable/unreliable mechanism (Section 5) has been modified so that the *originator* decides dynamically whether a given LSA should be flooded reliably or unreliably. (Version 00 described a method in which each receiver decides whether to suppress ACKs for a given LSA based on how frequently the LSA is being updated.) - Text has been added for the following added references: [Spagnolo04], [Chandra04], [RFC3684], and [Adjih02]. Ogier Expires January 19, 2005 [Page 14] Internet-Draft OSPF Extensions for Manets July 2004 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. [RFC3684] R. Ogier, F. Templin, and M. Lewis. "Topology Dissemination Based on Reverse Path Forwarding", RFC 3684, February 2004. [RFC2328] J. Moy. "OSPF Version 2", RFC 2328, April 1998. [RFC1142] D. Oran. "OSI IS-IS Intra-Domain Routing Protocol", RFC 1142, February 1990. [Ahrenholz04] 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-01, May 2004. [Spagnolo04] P. Spagnolo, T. Henderson, and G. Pei. "Design Considerations for a Wireless OSPF Interace", Internet-Draft (work in progress), draft-spagnolo-manet-ospf-design-00.txt, April 2004. Ogier Expires January 19, 2005 [Page 15] Internet-Draft OSPF Extensions for Manets July 2004 [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. [Chandra04] M.W. Chandra, Editor. "Extensions to OSPF to Support Mobile Ad Hoc Networking", Internet-Draft (work in progress), draft-chandra-ospf-manet-ext-00.txt, February 2004. [Adjih02] C. Adjih, P. Jacquet, and L. Viennot. "Computing connected dominated sets with multipoint relays", INRIA research report No. 4597, October 2002. Author's Address Richard G. Ogier EMail: rich.ogier@earthlink.net Ogier Expires January 19, 2005 [Page 16]