Open Shortest Path (OSPF) E. Baccelli Internet-Draft P. Jacquet Intended status: Experimental INRIA Expires: May 22, 2009 D. Nguyen CRC T. Clausen LIX, Ecole Polytechnique, France November 18, 2008 OSPF MPR Extension for Ad Hoc Networks draft-ietf-ospf-manet-mpr-03 Status of This Memo By submitting this Internet-Draft, each author represents that any applicable patent or other IPR claims of which he or she is aware have been or will be disclosed, and any of which he or she becomes aware will be disclosed, in accordance with Section 6 of BCP 79. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt. The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. This Internet-Draft will expire on May 22, 2009. Abstract This document specifies an OSPFv3 interface type tailored for mobile ad hoc networks. This interface type is derived from the broadcast interface type, and denoted the "OSPFv3 MANET interface type". Table of Contents 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 Baccelli, et al. Expires May 22, 2009 [Page 1] Internet-Draft OSPF MPR Extension for MANET November 2008 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 5 3.1. MANET Characteristics . . . . . . . . . . . . . . . . . . 5 3.2. OSPFv3 MANET Interface Characteristics . . . . . . . . . . 5 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 6 4.1. Efficient Flooding using MPRs . . . . . . . . . . . . . . 6 4.2. MPR Topology Reduction . . . . . . . . . . . . . . . . . . 6 4.3. Multicast Transmissions of Protocol Packets . . . . . . . 6 4.4. MPR Adjacency Reduction . . . . . . . . . . . . . . . . . 7 5. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 7 5.1. Data Structures . . . . . . . . . . . . . . . . . . . . . 7 5.1.1. N: Symmetric 1-hop Neighbor Set . . . . . . . . . . . 7 5.1.2. N2: Symmetric strict 2-hop Neighbor Set . . . . . . . 8 5.1.3. Flooding-MPR set . . . . . . . . . . . . . . . . . . . 8 5.1.4. Flooding-MPR-selector set . . . . . . . . . . . . . . 9 5.1.5. Path-MPR set . . . . . . . . . . . . . . . . . . . . . 9 5.1.6. Path-MPR-selector set . . . . . . . . . . . . . . . . 9 5.1.7. MPR set . . . . . . . . . . . . . . . . . . . . . . . 10 5.1.8. MPR-selector set . . . . . . . . . . . . . . . . . . . 10 5.2. Hello Protocol . . . . . . . . . . . . . . . . . . . . . . 10 5.2.1. Flooding-MPR Selection . . . . . . . . . . . . . . . . 11 5.2.2. Flooding-MPR Selection Signaling - FMPR TLV . . . . . 11 5.2.3. Neighbor Ordering . . . . . . . . . . . . . . . . . . 11 5.2.4. Metric Signaling - METRIC TLV and PMPR TLV . . . . . . 12 5.2.5. Path-MPR Selection . . . . . . . . . . . . . . . . . . 12 5.2.6. Path-MPR Selection Signaling - PMPR TLV . . . . . . . 12 5.2.7. Hello Packet Processing . . . . . . . . . . . . . . . 13 5.3. Adjacencies . . . . . . . . . . . . . . . . . . . . . . . 13 5.3.1. Packets over 2-Way Links . . . . . . . . . . . . . . . 14 5.3.2. Adjacency Conservation . . . . . . . . . . . . . . . . 14 5.4. Link State Advertisements . . . . . . . . . . . . . . . . 14 5.4.1. LSA Flooding . . . . . . . . . . . . . . . . . . . . . 15 5.4.2. Link State Acknowledgments . . . . . . . . . . . . . . 16 5.5. Hybrid Routers . . . . . . . . . . . . . . . . . . . . . . 17 5.6. Synch Routers . . . . . . . . . . . . . . . . . . . . . . 18 5.7. Routing Table Computation . . . . . . . . . . . . . . . . 18 6. Packet Formats . . . . . . . . . . . . . . . . . . . . . . . . 18 6.1. Flooding-MPR TLV . . . . . . . . . . . . . . . . . . . . 18 6.2. Metric TLV . . . . . . . . . . . . . . . . . . . . . . . 19 6.3. Path-MPR TLV . . . . . . . . . . . . . . . . . . . . . . 21 7. Security Considerations . . . . . . . . . . . . . . . . . . . 24 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 25 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 26 9.1. Normative References . . . . . . . . . . . . . . . . . . . 26 9.2. Informative References . . . . . . . . . . . . . . . . . . 26 Appendix A. Flooding-MPR Selection Heuristic . . . . . . . . . . 27 Appendix B. Path-MPR Selection Heuristic . . . . . . . . . . . . 28 Appendix C. Contributors . . . . . . . . . . . . . . . . . . . . 29 Appendix D. Acknowledgments . . . . . . . . . . . . . . . . . . . 30 Baccelli, et al. Expires May 22, 2009 [Page 2] Internet-Draft OSPF MPR Extension for MANET November 2008 1. Introduction This document specifies an extension of OSPFv3 [RFC5340] adapted to MANETs [RFC2501], and based on mechanisms providing: Flooding reduction: only a subset of all routers will be involved in (re)transmissions during a flooding operation. Topology reduction: only a subset of links are advertised, hence both the number and the size of LSAs are decreased. Adjacency reduction: adjacencies are brought up only with a subset of neighbors, for lower database synchronization overhead. These mechanisms are based on multipoint relays (MPR), a technique developed in OLSR [RFC3626]. The extension specified in this document integrates into the OSPF framework by defining the OSPFv3 MANET interface type. While this extension enables OSPFv3 to function efficiently on mobile ad hoc networks, operation of OSPFv3 on other types of interfaces or networks, or in areas without OSPFv3 MANET interfaces, remains unaltered. 2. Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. This document uses OSPF terminology as defined in [RFC2328] and [RFC5340], LLS terminology as defined in [RFC4813], and introduces the following terminology to the OSPF nomenclature: OSPFv3 MANET interface - the OSPFv3 interface type for MANETs, as specified in this document. Additionally, the following terms are used in this document: MANET router - a router which has only OSPFv3 MANET interface(s). Wired router - a router which has only OSPFv3 interface of types other than OSPFv3 MANET interfaces. Baccelli, et al. Expires May 22, 2009 [Page 3] Internet-Draft OSPF MPR Extension for MANET November 2008 Hybrid router - a router which has OSPFv3 interfaces of several types, including at least one of the OSPFv3 MANET interface type. Neighbor - a router, reachable through an OSPFv3 interface (of any type). MANET neighbor - a neighbor, reachable through an OSPFv3 MANET interface. Symmetric 1-hop neighbor - a neighbor, in a state greater than or equal to 2-Way (through an interface of any type). Symmetric strict 2-hop neighbor - a symmetric 1-hop neighbor of a symmetric 1-hop neighbor, which is not itself a symmetric 1-hop neighbor of this router. Symmetric strict 2-hop neighborhood - the set formed by all the symmetric strict 2-hop neighbors of the considered router. Synch router - a router which brings up adjacencies with all of its MANET neighbors. Flooding-MPR - A router which is selected by its symmetric 1-hop neighbor, router X, to retransmit all broadcast protocol packets that it receives from router X, provided that that broadcast protocol packet is not a duplicate, and that the hop limit field of the protocol packet is greater than one. Path-MPR - A router, which is selected by a symmetric 1-hop neighbor, X, as being on the shortest path from a router in the symmetric strict 2-hop neighborhood of router X and to the router X. Multipoint Relay (MPR) - A router which is selected by its symmetric 1-hop neighbor as either Flooding-MPR or as Path-MPR, or as both. Flooding-MPR Selector - A router which has selected its symmetric 1-hop neighbor, router X, as one of its Flooding-MPRs is a Flooding-MPR selector of router X. Path-MPR Selector - A router which has selected its symmetric 1-hop neighbor, router X, as one of its Path-MPRs is a Path-MPR selector of router X. MPR Selector - A router which has selected its symmetric 1-hop neighbor, router X, as either one of its Flooding-MPRs or as one of its Path-MPRs or as both is an MPR selector of router X. Baccelli, et al. Expires May 22, 2009 [Page 4] Internet-Draft OSPF MPR Extension for MANET November 2008 3. Applicability Statement The OSPFv3 MANET interface type, defined in this specification, allows OSPFv3 to be deployed within an area where parts of that area are a mobile ad hoc network (MANET) with moderate mobility properties. 3.1. MANET Characteristics MANETs [RFC2501] are networks in which a dynamic network topology is a frequently expected condition, often due to router mobility and/or to varying quality of wireless links - the latter of which also generally entails bandwidth scarcity and interference issues between neighbors. Moreover, MANETs often exhibit "semi-broadcast" properties: a router R that makes a transmission within a MANET can only assume that transmission to be received by a subset of the total number of routers within that MANET: if two routers, R1 and R2, each make a transmission, each of these transmissions is not guaranteed to be received by the same subset of routers within the MANET - and this even if each of R1 and R2 can mutually receive transmissions from each other. These characteristics are incompatible with several OSPFv3 mechanisms, including, but not limited to, existing mechanisms for control traffic reduction, such as flooding reduction, topology reduction and adjacency reduction (e.g. Designated Router). 3.2. OSPFv3 MANET Interface Characteristics An interface of the OSPFv3 MANET interface type is the point of attachment of an OSPFv3 router to a network which may have MANET characteristics. That is, an interface of the OSPFv3 MANET interface type is able to accommodate the MANET characteristics described in Section 3.1. An OSPFv3 MANET interface type is not prescribing a set of behaviors or expectations that the network is required to have. Rather, it is describing operating conditions under which protocols on an interface towards that network must be able to function (i.e. the protocols are required to be able to operate correctly when faced with the characteristics as described in Section 3.1). As such, the OSPFv3 MANET interface type is a generalization of other OSPFv3 interface types; for example a protocol operating correctly over an OSPFv3 MANET interface would also operate correctly over an OSPFv3 broadcast interface (whereas the inverse would not necessarily be true). Efficient OSPFv3 operation over MANETs relies on control traffic Baccelli, et al. Expires May 22, 2009 [Page 5] Internet-Draft OSPF MPR Extension for MANET November 2008 reduction, and using mechanisms appropriate for semi-broadcast. The OSPFv3 MANET interface type, defined in this document, allows networks with MANET characteristics into the OSPFv3 framework by integrating mechanisms (flooding reduction, topology reduction and adjacency reduction) derived from solutions standardized by the MANET working group. 4. Protocol Overview and Functioning The OSPFv3 MANET interface type, defined in this specification, makes use of flooding reduction, topology reduction and adjacency reduction, all based on multipoint relaying (MPR) - a technique derived from [RFC3626], as standardized in the MANET working group. Multicast transmissions of protocol packets are used when possible. 4.1. Efficient Flooding using MPRs OSPFv3 MANET interfaces use a flooding reduction mechanism denoted MPR flooding [MPR], whereby only a subset of MANET neighbors (those selected as Flooding-MPR) participate in a flooding operation. This reduces the number of (re)transmissions necessary for a flooding operation [MPR-analysis], while retaining resilience to transmission errors (inherent when using wireless links), and obsolete two-hop neighbor information (e.g. as caused by router mobility) [MPR-robustness]. 4.2. MPR Topology Reduction OSPFv3 MANET interfaces use a topology reduction mechanism denoted MPR topology reduction, whereby only necessary links to MANET neighbors (those identified by Path-MPR selection as belonging to shortest paths) are included in LSAs. Routers in a MANET periodically generate and flood Router-LSAs describing their selection of such links to their Path-MPRs. Such links are reported as point-to-point links. This reduces the size of LSAs originated by routers on a MANET [MPR-topology], while retaining classic OSPF properties: optimal paths using synchronized adjacencies (if synchronized paths are preferred over non-synchronized paths of equal cost). 4.3. Multicast Transmissions of Protocol Packets OSPFv3 MANET interfaces employ multicast transmissions, when possible, thereby taking advantage of inherent broadcast capabilities of the medium, if present (with wireless interfaces, this can often be the case [RFC2501]). In particular, LSA acknowledgments are sent via multicast over these interfaces, and retransmissions over the same interfaces are considered as implicit acknowledgments. Jitter Baccelli, et al. Expires May 22, 2009 [Page 6] Internet-Draft OSPF MPR Extension for MANET November 2008 management, such as delaying packet (re)transmission, can be employed in order to allow several packets to be bundled into a single transmission, which may avoid superfluous retransmissions due to packet collisions [RFC5148]. 4.4. MPR Adjacency Reduction Adjacencies over OSPFv3 MANET interfaces are required to be formed only with a subset of the neighbors of that OSPFv3 MANET interface. No Designated Router or Backup Designated Router are elected on an OSPFv3 MANET interface. Rather, adjacencies are brought up over an OSPFv3 MANET interface only with MPRs and MPR Selectors. Only a small subset of routers in the MANET (called Synch routers) are required to bring up adjacencies with all their MANET neighbors. This reduces the amount of control traffic needed for database synchronization, while ensuring that LSAs still describe only synchronized adjacencies. 5. Protocol Details This section complements [RFC5340] and specifies the information that must be maintained, processed and transmitted by routers which operate one or more OSPFv3 MANET interfaces. 5.1. Data Structures In addition to the values used in [RFC5340], the type field in the interface data structure can take a new value, "MANET". Furthermore, and in addition to the protocol structures defined by [RFC5340], routers which operate one or more MANET interfaces make use of the data structures described below. 5.1.1. N: Symmetric 1-hop Neighbor Set The Symmetric 1-hop Neighbor set records router IDs of the set of symmetric 1-hop neighbors of the router. There is one Symmetric 1-hop Neighbor set per MANET interface. More precisely, N records tuples of the form: (1_HOP_SYM_id, 1_HOP_SYM_time) where: 1_HOP_SYM_id: is the router ID of the symmetric 1-hop neighbor of this router. Baccelli, et al. Expires May 22, 2009 [Page 7] Internet-Draft OSPF MPR Extension for MANET November 2008 1_HOP_SYM_time: specifies the time at which the tuple expires and MUST be removed from the set. 5.1.2. N2: Symmetric strict 2-hop Neighbor Set The Symmetric strict 2-hop Neighbor set records links between routers in N and their symmetric 1-hop neighbors, excluding: (i) the router performing the computation, (ii) all routers in N. There is one Symmetric strict 2-hop Neighbor set per MANET interface. More precisely, N2 records tuples of the form: (2_HOP_SYM_id, 1_HOP_SYM_id, 2_HOP_SYM_time) where: 2_HOP_SYM_id: is the router ID of a symmetric strict 2-hop neighbor. 1_HOP_SYM_id: is the router ID of the symmetric 1-hop neighbor of this router through which the symmetric strict 2-hop neighbor can be reached. 2_HOP_SYM_time: specifies the time at which the tuple expires and MUST be removed from the set. 5.1.3. Flooding-MPR set The Flooding-MPR set records router IDs of a subset of the routers listed in N, selected such that through this subset, each router listed in N2 is reachable in 2 hops by this router. There is one Flooding-MPR set per MANET interface. More precisely, the Flooding- MPR set records tuples of the form: (Flooding_MPR_id, Flooding_MPR_time) where: Flooding_MPR_id: is the router ID of the symmetric 1-hop neighbor of this router, selected as Flooding-MPR. Flooding_MPR_time: specifies the time at which the tuple expires and MUST be removed from the set. Flooding-MPR selection is detailed in Section 5.2.1. Baccelli, et al. Expires May 22, 2009 [Page 8] Internet-Draft OSPF MPR Extension for MANET November 2008 5.1.4. Flooding-MPR-selector set The Flooding-MPR-selector set records router IDs of the set of symmetric 1-hop neighbors of this router that have selected this router as Flooding-MPR. There is one Flooding-MPR-selector set per MANET interface. More precisely, the Flooding-MPR-selector set records tuples of the form: (Flooding_MPR_SELECTOR_id, Flooding_MPR_SELECTOR_time) where: Flooding_MPR_SELECTOR_id: is the router ID of the symmetric 1-hop neighbor of this router, that has selected this router as Flooding-MPR. Flooding_MPR_SELECTOR_time: specifies the time at which the tuple expires and MUST be removed from the set. Flooding-MPR selection is detailed in Section 5.2.1. 5.1.5. Path-MPR set The Path-MPR set records router IDs of routers in N over any MANET interface, that provide shortest paths from routers in N2 (over any MANET interface) to this router. There is one Path-MPR set per router. More precisely, the Path-MPR set records tuples of the form: (Path_MPR_id, Path_MPR_time) where: Path_MPR_id: is the router ID of the symmetric 1-hop neighbor of this router, selected as Path-MPR. Path_MPR_time: specifies the time at which the tuple expires and MUST be removed from the set. Path-MPR selection is detailed in Section 5.2.5. 5.1.6. Path-MPR-selector set The Path-MPR-selector set records router IDs of the set of symmetric 1-hop neighbors over any MANET interface that have selected this router as Path-MPR. There is one Path-MPR-selector set per router. More precisely, the Path-MPR-selector set records tuples of the form: (Path_MPR_SELECTOR_id, Path_MPR_SELECTOR_time) Baccelli, et al. Expires May 22, 2009 [Page 9] Internet-Draft OSPF MPR Extension for MANET November 2008 where: Path_MPR_SELECTOR_id: is the router ID of the symmetric 1-hop neighbor of this router, that has selected this router as Path- MPR. Path_MPR_SELECTOR_time: specifies the time at which the tuple expires and MUST be removed from the set. Path-MPR selection is detailed in Section 5.2.5. 5.1.7. MPR set The MPR set is the union of the Flooding-MPR set(s) and the Path-MPR set. There is one MPR set per router. 5.1.8. MPR-selector set The MPR-Selector Set is the union of the Flooding-MPR-selector set(s) and the Path-MPR-selector set. There is one MPR-selector set per router. 5.2. Hello Protocol On OSPFv3 MANET interfaces, packets are sent, received and processed as defined in [RFC5340] and [RFC2328], augmented for MPR selection as detailed in this section. All additional signaling for OSPFv3 MANET interfaces is done through inclusion of TLVs within an LLS block [RFC4813], appended to Hello packets. If an LLS block is not already present, an LLS block MUST be created and appended to the Hello packets. Hello packets sent over an OSPFv3 MANET interface MUST have the L bit of the OSPF Options field set, as per [RFC4813], indicating the presence of an LLS block. This document defines and employs the following TLVs in Hello packets sent over OSPFv3 MANET interfaces: FMPR - signaling Flooding-MPR selection; PMPR - signaling Path-MPR selection; METRIC - signaling metrics. The layout and internal structure of these TLVs is detailed in Section 6. Baccelli, et al. Expires May 22, 2009 [Page 10] Internet-Draft OSPF MPR Extension for MANET November 2008 5.2.1. Flooding-MPR Selection The objective of Flooding-MPR selection is for a router to select a subset of its neighbors such that a packet, retransmitted by these selected neighbors, will be received by all routers 2 hops away. This property is called the Flooding-MPR "coverage criterion". The Flooding-MPR set of a router is computed such that, for each OSPFv3 MANET interface, it satisfies this criterion. The information required to perform this calculation (i.e. link sensing and neighborhood information) is acquired through periodic exchange of OSPFv3 Hello packets. Flooding-MPRs are computed by each router which operates at least one OSPFv3 MANET interface. The smaller the Flooding-MPR set is, the lower the overhead will be. However, while it is not essential that the Flooding-MPR set is minimal, the "coverage criterion" MUST be satisfied by the selected Flooding-MPR set. The willingness of a neighbor router to act as Flooding-MPR MAY be taken into consideration by a heuristic for Flooding-MPR selection. An example heuristic taking willingness into account is given in Appendix A. 5.2.2. Flooding-MPR Selection Signaling - FMPR TLV A router MUST signal its Flooding-MPRs set to its neighbors, through including an FMPR TLV in generated Hello packets. Inclusion of this FMPR TLV signals the list of symmetric 1-hop neighbors that the sending router has selected as Flooding-MPR, as well as the willingness of the sending router to be elected Flooding-MPR by other routers. The FMPR TLV structure is detailed in Section 6.1. 5.2.3. Neighbor Ordering Neighbors listed in the Hello packets sent over OSPFv3 MANET interfaces MUST be included in the order as given below: 1. symmetric 1-hop neighbors which are selected as Flooding-MPRs; 2. other symmetric 1-hop neighbors; 3. other 1-hop neighbors. This ordering allows correct interpretation of an included FMPR TLV. Baccelli, et al. Expires May 22, 2009 [Page 11] Internet-Draft OSPF MPR Extension for MANET November 2008 5.2.4. Metric Signaling - METRIC TLV and PMPR TLV Hello packets sent over OSPFv3 MANET interfaces MUST advertise the costs of links towards ALL the symmetric MANET neighbors of the sending router. If the sending router has more than one OSPFv3 MANET interfaces, links to ALL the symmetric MANET neighbors over ALL the OSPFv3 MANET interfaces of that router MUST have their costs advertised. The costs of the links between the router and each of its MANET neighbors on the OSPFv3 MANET interface over which the Hello packet is sent MUST be signaled through including METRIC TLVs. The METRIC TLV structure is detailed in Section 6.2. Moreover, the lowest cost from each MANET neighbor towards the router (regardless of over which interface) MUST be specified in the included PMPR TLV. Note that the lowest cost can be over an interface which is not an OSPFv3 MANET interface. 5.2.5. Path-MPR Selection A router which has one or more OSPFv3 MANET interface(s) MUST select a Path-MPR set from among routers in N. Routers in the Path-MPR set of a router are those which take part in the shortest (with respect to the metrics used) path from routers in N2 and to this router. A heuristic for Path-MPR selection is given in Appendix B. 5.2.6. Path-MPR Selection Signaling - PMPR TLV A router MUST signal its Path-MPR set to its neighbors, through including a PMPR TLV in generated Hello packets. A PMPR TLV MUST contain a list of IDs of all symmetric 1-hop neighbors of all OSPFv3 MANET interfaces of the router. These IDs MUST be included in the PMPR TLV in the order as given below: 1. Neighbors which are both adjacent AND are selected as Path-MPR for any OSPFv3 MANET interface of the router generating the Hello packet. 2. Neighbors which are adjacent over any OSPFv3 MANET interface of the router generating the Hello packet. 3. Symmetric 1-hop neighbors on any OSPFv3 MANET interface of the router generating the Hello packet, which have not been previously included in this PMPR TLV. The list of neighbor IDs is followed by a list of costs for the links Baccelli, et al. Expires May 22, 2009 [Page 12] Internet-Draft OSPF MPR Extension for MANET November 2008 from these neighbors and to the router generating the Hello packet containing this PMPR TLV, as detailed in Section 5.2.4. The PMPR TLV structure is detailed in Section 6.3. 5.2.7. Hello Packet Processing In addition to the processing specified in [RFC5340], N and N2 MUST be updated when received Hello packets indicate changes to the neighborhood of an OSPFv3 MANET interface. In particular, if a received Hello packet signals that a tuple in N (or N2) is to be deleted, the deletion is done immediately, without waiting for the tuple to expire. Note that N2 records not only 2-hop neighbors listed in received Hellos, but also 2-hop neighbors listed in the appended PMPR TLVs. The Flooding-MPR set and the Path-MPR set MUST then be recomputed when either of N or N2 has changed. Moreover, the Path-MPR set MUST be recomputed if appended LLS information signals change with respect to one or more link cost(s). The Flooding-MPR selector set and the Path-MPR selector set MUST be updated upon receipt of a Hello packet containing LLS information indicating changes in the list of neighbors that has selected the router as MPR. If a Hello with the S bit set is received on a OSPFv3 MANET interface of a router, from a non-adjacent neighbor, the router MUST transition this neighbor's state to ExStart. 5.3. Adjacencies Adjacencies are brought up between OSPFv3 MANET interfaces as described in [RFC5340] and [RFC2328]. However, in order to reduce the control traffic overhead over the OSPFv3 MANET interfaces, a router which has one or more such OSPFv3 MANET interface(s) MAY bring up adjacencies with only subset of its MANET neighbors. Over an OSPFv3 MANET interface, a router MUST bring up adjacencies with all MANET neighbors which are included in its MPR set and its MPR Selector set; this ensures that beyond the first hop, routes use synchronized links (if synchronized paths are preferred over non- synchronized paths of equal cost). A router MAY bring up adjacencies with other MANET neighbors, at the expense of additional synchronization overhead. Baccelli, et al. Expires May 22, 2009 [Page 13] Internet-Draft OSPF MPR Extension for MANET November 2008 5.3.1. Packets over 2-Way Links When a router does not form a full adjacency with a MANET neighbor, the state of that neighbor does not progress beyond 2-Way (as defined in [RFC2328]). A router can send protocol packets, such as LSAs, to a MANET neighbor in 2-Way state. Therefore, any packet received from a symmetric MANET neighbor MUST be processed. As with the OSPF broadcast interface [RFC2328], the next hop in the forwarding table MAY be a neighbor that is not adjacent. However, when a data packet has travelled beyond its first hop, the MPR selection process guarantees that subsequent hops in the SPT will be over adjacencies (if synchronized paths are preferred over non- synchronized paths of equal cost). 5.3.2. Adjacency Conservation Adjacencies are torn down according to [RFC2328]. When the MPR set or MPR selector set is updated (due to changes in the neighborhood), and when a neighbor was formerly, but is no longer, in the MPR set or the MPR selector set, then the adjacency with that neighbor is kept, unless the change causes the neighbor to cease being a symmetric 1-hop neighbor. When a router receives Hello packets from a symmetric 1-hop neighbor which ceases to list this router as being adjacent (see Section 5.2.6), the state of that neighbor MUST be changed to (i) 2-Way if the neighbor is not in the MPR set or the MPR selector set, or (ii) ExStart if the neighbor is in the MPR set or the MPR selector set, or if the neighbor or the router itself is a Synch router. 5.4. Link State Advertisements Routers generate Router-LSAs periodically, using the format specified in [RFC5340] and [RFC2328]. Routers which have one or more OSPFv3 MANET interface(s) MUST include the following links in the Router-LSAs that they generate: o links to all neighbors that are in the Path-MPR set; AND o links to all neighbors that are in the Path-MPR Selector set. Routers which have one or more OSPFv3 MANET interface(s) MAY list other links they have through those OSPFv3 MANET interfaces, at the expense of larger LSAs. In addition, routers which have one or more OSPFv3 MANET interface(s) Baccelli, et al. Expires May 22, 2009 [Page 14] Internet-Draft OSPF MPR Extension for MANET November 2008 MUST generate updated Router-LSAs when either of the following occurs: o a new adjacency has been brought up, reflecting a change in the MPR set; o a new adjacency has been brought up, reflecting a change in the MPR Selector set; o a formerly adjacent and advertised neighbor ceases to be adjacent; o the cost of a link to (or from) an advertised neighbor has changed. 5.4.1. LSA Flooding An originated LSA is flooded according to [RFC5340], out all interfaces concerned by the scope of this LSA. Link State Updates received on an interface of a type other than OSPFv3 MANET interface are processed and flooded according to [RFC2328] and [RFC5340], over every interface. If a Link State Update was received on an OSPFv3 MANET interface, it is processed as follows: 1. Consistency checks are performed on the received packet according to [RFC2328] and [RFC5340], and the Link State Update packet is thus associated with a particular neighbor and a particular area. 2. If the Link State Update was received from a router other than a symmetric 1-hop neighbor, the Link State Update MUST be discarded without further processing. 3. Otherwise, for each LSA contained in Link State Updates received over an OSPFv3 MANET interface, the following steps replace steps 1 to 5 of section 13.3 of [RFC2328]. 1. If an LSA exists in the Link State Database, with the same Link State ID, LS Type and Advertising Router values as the received LSA, and if the received LSA is not newer (see section 13.1 of [RFC2328]), then the received LSA MUST NOT be processed, except for acknowledgment as described in Section 5.4.2. 2. Otherwise, the LSA MUST be attributed a scope according to its type, as specified in section 3.5 of [RFC5340]. Baccelli, et al. Expires May 22, 2009 [Page 15] Internet-Draft OSPF MPR Extension for MANET November 2008 3. If the scope of the LSA is link local or reserved, the LSA MUST NOT be flooded on any interface. 4. Otherwise: + If the scope of the LSA is the area, the LSA MUST be flooded on all the OSPFv3 interfaces of the router in that area according to the default flooding algorithm described in Section 5.4.1.1. + Otherwise, the LSA MUST be flooded on all the OSPFv3 interfaces of the router according to the default flooding algorithm described in Section 5.4.1.1. 5.4.1.1. Default LSA Flooding Algorithm The default LSA flooding algorithm is as follows: 1. The LSA MUST be installed in the Link State Database. 2. The Age of the LSA MUST be increased by InfTransDelay. 3. The LSA MUST be retransmitted over all OSPFv3 interfaces of types other than OSPFv3 MANET interface. 4. If the sending OSPFv3 interface is a Flooding-MPR selector of this router, then the LSA MUST also be retransmitted over all OSPFv3 MANET interfaces concerned by the scope, with the multicast address all_SPF_Routers. Note that MinLSArrival SHOULD be set to a value that is appropriate to dynamic topologies: LSA updating may need to be more frequent in MANET parts of an OSPF network than in other parts of an OSPF network. 5.4.2. Link State Acknowledgments When a router receives an LSA over an OSPFv3 MANET interface, the router MUST proceed to acknowledge the LSA as follows: 1. If the LSA was not received from an adjacent neighbor, the router MUST NOT acknowledge it. 2. Otherwise, if the LSA was received from an adjacent neighbor and if the LSA is already in the Link State Database (i.e. the LSA has already been received and processed), then the router MUST send an acknowledgment for this LSA on all OSPFv3 MANET interfaces, to the multicast address all_SPF_Routers. Baccelli, et al. Expires May 22, 2009 [Page 16] Internet-Draft OSPF MPR Extension for MANET November 2008 3. Otherwise, if the LSA is not already in the Link State Database: 1. If the router decides to retransmit the LSA (as part of the flooding procedure), the router MUST NOT acknowledge it, as this retransmission will be considered as an implicit acknowledgment. 2. Otherwise, if the router decides to not retransmit the LSA (as part of the flooding procedure), the router MUST send an explicit acknowledgment for this LSA on all OSPFv3 MANET interfaces, to the multicast address all_SPF_Routers. If a router sends an LSA on an OSPFv3 MANET interface, it expects acknowledgments (explicit or implicit) from all adjacent neighbors. In the case where the router did not generate, but simply relays, the LSA, then the router MUST expect acknowledgments (explicit or implicit) only from adjacent neighbors that have not previously acknowledged this LSA. If a router detects that some adjacent neighbor has not acknowledged the LSA, then that router MUST retransmit the LSA. If, due to the MPR flooding reduction mechanism employed for LSA Flooding as described in Section 5.4.1, a router decides to not relay an LSA, the router MUST still expect acknowledgments of this LSA (explicit or implicit) from adjacent neighbors that have not previously acknowledged this LSA. If a router detects that some adjacent neighbor has not acknowledged the LSA, then the router MUST retransmit the LSA. Note that it may be beneficial to aggregate several acknowledgments in the same transmission, taking advantage of native multicasting (if available). A timer wait MAY thus be used before any acknowledgment transmission. Additionally, jitter [RFC5148] on packet (re)transmission MAY be used in order to increase the opportunities to bundle several packets together in each transmission. 5.5. Hybrid Routers In addition to the operations described in Section 5.2, Section 5.3 and Section 5.4, hybrid routers MUST: o select ALL their MANET neighbors as Path-MPRs. o list adjacencies over OSPFv3 interfaces of types other than OSPFv3 MANET interface, as specified in [RFC5340] and [RFC2328], in generated Router-LSAs. Baccelli, et al. Expires May 22, 2009 [Page 17] Internet-Draft OSPF MPR Extension for MANET November 2008 5.6. Synch Routers In a network with no hybrid routers, at least one Synch router MUST be selected. A Synch router MUST: o set the S bit in the PMPR TLV appended to the Hello packets it generates; AND o become adjacent with ALL MANET neighbors. A proposed heuristic for selection of Sync routers is as follows: o A router which has a MANET interface and an ID that is higher than the ID of all of its current neighbors, and whose ID is higher than any other ID present in Router-LSAs currently in its Link State Database selects itself as Synch router. Other heuristics are possible, however any heuristic for selecting Synch routers MUST ensure the presence of at least one sync or hybrid router in the network. 5.7. Routing Table Computation When routing table (re)computation occurs, in addition to the processing of the Link State Database defined in [RFC5340] and [RFC2328], routers which have one or more MANET interfaces MUST take into account links between themselves and MANET neighbors that are in state 2-Way or higher (as data and protocol packets may be sent, received and processed over these links too). Thus, the connectivity matrix used to compute routes MUST reflect links between the root and all its neighbors in state 2-Way and higher, as well as links described in the Link State Database. 6. Packet Formats OSPFv3 packets are as defined by [RFC5340] and [RFC2328]. Additional LLS signaling [RFC4813] is used in Hello packets sent over OSPFv3 MANET interfaces, as detailed in this section. This specification uses network byte order (most significant octet first) for all fields. 6.1. Flooding-MPR TLV A TLV of Type FMPR is defined for signaling Flooding-MPR selection, shown in Figure 1. Baccelli, et al. Expires May 22, 2009 [Page 18] Internet-Draft OSPF MPR Extension for MANET November 2008 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type=FMPR | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Willingness | # Sym. Neigh. | # Flood MPR | Reserved | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 1: Flooding-MPR TLV (FMPR) where: Willingness - is an 8 bit unsigned integer field which specifies the willingness of the router to flood link state information on behalf of other routers. It can be set to any integer value from 1 to 6. By default, a router SHOULD advertise a willingness of WILL_DEFAULT = 3. # Sym. Neigh. - is an 8 bit unsigned integer field which specifies the number of symmetric 1-hop neighbors. These symmetric 1-hop neighbors are listed first among the neighbors in a Hello packet. # Flood MPR - is an 8 bit unsigned integer field which specifies the number of neighbors selected as Flooding-MPR. These Flooding-MPRs are listed first among the symmetric 1-hop neighbors. Reserved - is an 8 bit field which SHOULD be cleared ('0') on transmission and SHOULD be ignored on reception. 6.2. Metric TLV A TLV of Type METRIC is defined for signaling costs of links to neighbors, shown in Figure 2. Baccelli, et al. Expires May 22, 2009 [Page 19] Internet-Draft OSPF MPR Extension for MANET November 2008 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type=METRIC | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved |U|R| Cost 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Cost 1 | Cost 2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Cost n | Padding | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 2: Metric TLV (METRIC). where: Reserved - is a 14 bit field which SHOULD be cleared ('0') on transmission and SHOULD be ignored on reception. R - is a binary flag, cleared ('0') if the costs advertised in the TLV are direct (i.e. the costs of the links from the router to the neighbors), set ('1') if the costs advertised are reverse (i.e. the costs of the links from the neighbors to the router). U - is a binary flag, cleared ('0') if each the cost for each link from the sending router and to each advertised neighbor is explicitly included (shown in Figure 3), set ('1') if a single metric value is included which applies to all links (shown in Figure 4). Cost n - is an 8 bit unsigned integer field which specifies the cost of the link, in the direction specified by the R flag, between this router and the neighbor listed at the n-th position in the Hello packet, when counting from the beginning of the Hello packet and with the first neighbor being at position 0. Padding - is a 16 bit field which SHOULD be cleared ('0') on transmission and SHOULD be ignored on reception. Padding is included in order that the TLV is 32bit aligned. Padding MUST be included when the TLV contains an even number of Cost fields, and MUST NOT be included otherwise. Baccelli, et al. Expires May 22, 2009 [Page 20] Internet-Draft OSPF MPR Extension for MANET November 2008 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type=METRIC | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved |0|R| Cost 0 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Cost 1 | Cost 2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 3: Metric Advertisement TLV (METRIC) example with explicit individual link costs (U=0) and an odd number of Costs (and, hence, no padding). 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type=METRIC | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Reserved |1|R| Cost | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 4: Metric Advertisement TLV (METRIC) example with a single and uniform link cost (U=1) (and, hence, no padding). 6.3. Path-MPR TLV A TLV of Type PMPR is defined for signaling Path-MPR selection, shown in Figure 1, as well as the link cost associated with these Path- MPRs. Baccelli, et al. Expires May 22, 2009 [Page 21] Internet-Draft OSPF MPR Extension for MANET November 2008 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type=PMPR | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | # Sym Neigh | # Adj. Neigh | # Path-MPR | Reserved |U|S| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Cost 0 | Cost 1 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Cost n | Padding | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 5: Path-MPR TLV (PMPR) # Sym Neigh. - is an 8 bit unsigned integer field which specifies the number of symmetric 1-hop MANET neighbors of all OSPFv3 MANET interfaces of the router, listed in the PMPR TLV. # Adj. Neigh. - is an 8 bit unsigned integer field which specifies the number of adjacent neighbors. These adjacent neighbors are listed first among the symmetric 1-hop MANET neighbors of all OSPFv3 MANET interface of the router in the PMPR TLV. # Path-MPR - is an 8 bit unsigned integer field which specifies the number of MANET neighbors selected as Path-MPR. These Path-MPRs are listed first among the adjacent MANET neighbors in the PMPR TLV. Reserved - is a 6 bit field which SHOULD be cleared ('0') on transmission and SHOULD be ignored on reception. S - is a binary flag, cleared ('0') if the router brings up adjacencies only with neighbors in its MPR set and MPR selector set as per Section 5.3, set ('1') if the router brings up adjacencies with all MANET neighbors as a Synch router -- as per Section 5.6. Baccelli, et al. Expires May 22, 2009 [Page 22] Internet-Draft OSPF MPR Extension for MANET November 2008 U - is a binary flag, cleared ('0') if the cost for each link from each advertised neighbor in the PMPR TLV and to the sending router is explicitly included (as shown in Figure 6), set ('1') if a single metric value is included which applies to all links (as shown in Figure 7). Neighbor ID - is a 32 bit field which specifies the router ID of a symmetric 1-hop neighbor of an OSPFv3 MANET interface of the router. Cost n - is a 16 bit unsigned integer field which specifies the cost of the link in the direction from the nth listed advertised neighbor in the PMPR TLV and towards this router. A default value of 0xFFFF (i.e. infinity) MUST be advertised, unless information received via Hello packets from the neighbor specifies otherwise, in which case the received information MUST be advertised. If a neighbor is reachable via more than one interface, the cost advertised MUST be the minimum of the costs by which that neighbor can be reached. Padding - is a 16 bit field which SHOULD be cleared ('0') on transmission and SHOULD be ignored on reception. Padding is included in order that the PMPR TLV is 32bit aligned. Padding MUST be included when the TLV contains an odd number of Cost fields, and MUST NOT be included otherwise. Baccelli, et al. Expires May 22, 2009 [Page 23] Internet-Draft OSPF MPR Extension for MANET November 2008 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type=PMPR | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | # Adj. Neigh | # Path-MPR | Reserved |0|S| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : : : : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Cost 1 | Cost 2 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ : ....... : +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Cost n-1 | Cost n | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 6: Path-MPR TLV (PMPR) with explicit individual link costs (U=0) and an even number of Cost fields (hence, no padding). 0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Type=5 | Length | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | # Adj. Neigh | # Path-MPR | Reserved |1|S| +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Neighbor ID | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Cost | Padding | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 7: Path-MPR TLV (PMPR) with a single and uniform link cost (U=1) (hence, padding included). 7. Security Considerations [RFC4593] describes generic threats to routing protocols, whose applicability to OSPFv3 [RFC5340] is not altered by the presence of OSPFv3 MANET interfaces. As such, the OSPFv3 MANET interface type does not introduce new security threats to [RFC5340]. Baccelli, et al. Expires May 22, 2009 [Page 24] Internet-Draft OSPF MPR Extension for MANET November 2008 However, the use of a wireless medium use and the lack of infrastructure, as enabled by the use of the OSPFv3 MANET interface type, may render some of the attacks described in [RFC4593] easier to undertake. For example, control traffic sniffing and control traffic analysis are simpler tasks with wireless than with wires, as it is sufficient to be somewhere within radio range in order to "listen" to wireless traffic. Inconspicuous wiretapping of the right cable(s) is not necessary. In a similar fashion, physical signal interference is also a simpler task with wireless than with wires, as it is sufficient to emit from somewhere within radio range in order to be able to disrupt the communication medium. No complex wire connection is required. Other types of interference (including not forwarding packets), spoofing, and different types of falsification or overloading (as described in [RFC4593]) are also threats to which routers using OSPFv3 MANET interfaces may be subject. In these cases, the lack of pre-determined infrastructure or authority, enabled by the use of OSPFv3 MANET interfaces, may facilitate such attacks by making it easier to forge legitimacy. Moreover, the consequence zone of a given threat, and its consequence period (as defined in [RFC4593]), may also be slightly altered over the wireless medium, compared to the same threat over wired networks. Indeed, mobility and the fact that radio range spans "further" than a mere cable may expand the consequence zone in some cases, while the more dynamic nature of MANET topologies may decrease the consequence period, as harmful information (or lack of information) will tend to be replaced quicker by legitimate information. 8. IANA Considerations This document defines three LLS TLVs, for which allocation of type values are requested from the LLS TLV type registry defined in [RFC4813]. +----------+------------+--------------+ | Mnemonic | Type Value | Name | +----------+------------+--------------+ | FMPR | tbd | Flooding-MPR | | METRIC | tbd | Metric | | PMPR | tbd | Path-MPR | +----------+------------+--------------+ Table 1: LLS TLV Type Assignments Baccelli, et al. Expires May 22, 2009 [Page 25] Internet-Draft OSPF MPR Extension for MANET November 2008 9. References 9.1. Normative References [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate Requirement Levels", RFC 2119, BCP 14, March 1997. [RFC2328] Moy, J., "OSPF version 2", RFC 2328, 1998. [RFC5340] Moy, J., Coltun, R., Ferguson, D., and A. Lindem, "OSPF for IPv6", RFC 5340, 2008. [RFC4813] Zinin, A., Friedman, B., Roy, A., Nguyen, L., and D. Yeung, "OSPF Link Local Signaling", RFC 4813, 2007. 9.2. Informative References [RFC2501] Macker, J. and S. Corson, "MANET Routing Protocol Performance Issues and Evaluation Considerations", RFC 2501, January 1999. [RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link State Routing Protocol", RFC 3626, October 2003. [RFC5148] Adamson, B., Dearlove, C., and T. Clausen, "Jitter Considerations in MANETs", RFC 5148, 2008. [MPR] Qayyum, A., Viennot, L., and A. Laouiti,, "Multipoint Relaying for Flooding Broadcast Messages in Mobile Wireless Networks", Proceedings of HICSS , 2002. [MPR-robustness] Adjih, C., Baccelli, E., Clausen, T., and P. Jacquet, "On the Robustness and Stability of Connected Dominated Sets", INRIA Research Report RR-5609, 2005. [MPR-analysis] Ngyuen, D. and P. Minet, "Analysis of MPR Selection in the OLSR Protocol", 2nd Int. Workshop on Performance Analysis and Enhancement of Wireless Networks , 2007. [MPR-topology] Baccelli, E., Clausen, T., and P. Jacquet, "Partial Topology in an MPR-based Solution for Wireless OSPF on Mobile Ad Hoc Networks", INRIA Research Report RR-5619, 2005. Baccelli, et al. Expires May 22, 2009 [Page 26] Internet-Draft OSPF MPR Extension for MANET November 2008 [RFC4593] Barbir, A., Murphy, S., and Y. Yang, "Generic Threats to Routing Protocols", RFC 4593, 2006. Appendix A. Flooding-MPR Selection Heuristic The following specifies a proposed heuristic for selection of Flooding-MPRs. It constructs a Flooding-MPR set that enables a router to reach routers in the 2-hop neighborhood through relaying by one Flooding-MPR router. The following terminology will be used in describing the heuristics: D(Y) is the degree of a 1-hop neighbor, router Y (where Y is a member of N), defined as the number of neighbors of router Y, EXCLUDING all the members of N and EXCLUDING the router performing the computation. The proposed heuristic can then be described as follows. Begin with an empty Flooding-MPR set. Then: 1. Calculate D(Y), where Y is a member of N, for all routers in N. 2. Add to the Flooding-MPR set those routers in N, which are the only routers to provide reachability to a router in N2. For example, if router B in N2 can be reached only through a router A in N, then add router A to the Flooding-MPR set. Remove the routers from N2 which are now covered by a router in the Flooding-MPR set. 3. While there exist routers in N2 which are not covered by at least one router in the Flooding-MPR set: 1. For each router in N, calculate the reachability, i.e. the number of routers in N2 which are not yet covered by at least one router in the Flooding-MPR set, and which are reachable through this 1-hop neighbor; 2. Select as a Flooding-MPR the neighbor with highest willingness among the routers in N with non-zero reachability. In case of a tie among routers with same willingness, select the router which provides reachability to the maximum number of routers in N2. In case of another tie between routers also providing the same amount of reachability, select as Flooding-MPR the router whose D(Y) is greater. Remove the routers from N2 which are now covered by a router in the Flooding-MPR set. 4. As an optimization, consider in increasing order of willingness each router Y in the Flooding-MPR set: if all routers in N2 are still covered by at least one router in the Flooding-MPR set when excluding router Y, then router Y MAY be removed from the Baccelli, et al. Expires May 22, 2009 [Page 27] Internet-Draft OSPF MPR Extension for MANET November 2008 Flooding-MPR set. Other algorithms, as well as improvements over this algorithm, are possible. Different routers may use different algorithms independently. However, the algorithm used MUST provide the router with a Flooding-MPR set that fulfills the flooding coverage criterion, i.e. it MUST select a Flooding-MPR set such that any 2-hop neighbor is covered by at least one Flooding-MPR router. Appendix B. Path-MPR Selection Heuristic The following specifies a proposed heuristic for calculating a Path- MPR set that enables a router to reach routers in the 2-hop neighborhood through shortest paths via routers in its Path-MPR set. The following terminology will be used for describing this heuristic: A - The router performing the Path-MPR set calculation. B, C, D, .... - Other routers in the network. cost(A, B) - The cost of the path through the direct link, from A to B. dist(C, A) - The cost of the shortest path from C to A. A cost matrix is populated with the values of the costs of links originating from router A (available locally) and by values listed in Hello packets received from neighbor routers. More precisely, the cost matrix is populated as follows: 1. The coefficients of the cost matrix are set by default to 0xFFFF (maximal value, i.e. infinity). 2. The coefficient cost(A,B) of the cost matrix for a link from router A to a neighbor B (the direct cost for this link) is set to the minimum cost over all interfaces that feature router B as a symmetric 1-hop neighbor. The reverse cost for this link, cost(B,A), is set at the value received in Hello packets from router B. If router B is reachable through several interfaces at the same time, cost(B,A) is set as the minimum cost advertised by router B for its links towards router A. 3. The coefficients of the cost matrix concerning the link between two neighbors of A, routers C and B, are populated at the reception of their Hello packets. The cost (B,C) is set to the value advertised by the Hello packets from B, and respectively, the cost (C,B) is set to the value advertised in Hello packets from C. Baccelli, et al. Expires May 22, 2009 [Page 28] Internet-Draft OSPF MPR Extension for MANET November 2008 4. The coefficients of the cost matrix, cost(B,C) for a link that connects a neighbor B to a 2-hop neighbor C is obtained via the Hello packets received from router B. In this case cost(B,C) and cost(C,B) are respectively set to the values advertised by router B for the direct cost and reverse cost for node C. Once the cost matrix is populated, the proposed heuristic can then be described as follows. Begin with an empty Path-MPR set. Then: 1. Using the cost matrix and the Dijkstra algorithm, compute the router distance vector, i.e. the shortest distance for each pair (X,A) where X is in N or N2 minimizing the sum of the cost of the path between X and A. 2. Compute N' as the subset of N made of the elements X such that cost(X,A)=dist(X,A). 3. Compute N2' as the subset of N and N2 made of the elements Y that do not belong to N' and such that there exist X in N' such cost(Y,X)+cost(X,A)=dist(Y,A). 4. Compute the MPR selection algorithm presented in Appendix A with N' instead of N and N2' instead of N2. The resulting MPR set is the Path-MPR set. Other algorithms, as well as improvements over this algorithm, are possible. Different routers may use different algorithms independently. However, the algorithm used MUST provide the router with a Path-MPR set that fulfills the path coverage criterion, i.e. it MUST select a Path-MPR set such that for any element of N or N2 that is not in the Path-MPR set, there exists a shortest path that goes from this element to the router through a neighbor selected as Path-MPR (unless the shortest path is only one hop). If the router has multiple MANET interfaces, the above last 4 steps and the path coverage criterion are altered as follows: replace N with the union of all N sets, and replace N2 with the union of all N2 sets. Appendix C. Contributors The authors would like to thank Cedric Adjih, Acee Lindem, Padma Pillay-Esnault and Laurent Viennot for their contributions to this document. Baccelli, et al. Expires May 22, 2009 [Page 29] Internet-Draft OSPF MPR Extension for MANET November 2008 Appendix D. Acknowledgments The authors would like to thank Juan Antonio Cordero Fuertes, Ulrich Herberg and Richard Ogier for reviewing this document. Authors' Addresses Emmanuel Baccelli INRIA Phone: +33 1 69 33 55 11 EMail: Emmanuel.Baccelli@inria.fr URI: http://www.emmanuelbaccelli.org/ Philippe Jacquet INRIA Phone: +33 1 3963 5263 EMail: Philippe.Jacquet@inria.fr Dang-Quan Nguyen CRC Phone: +1-613-949-8216 EMail: dang.nguyen@crc.ca Thomas Heide Clausen LIX, Ecole Polytechnique, France Phone: +33 6 6058 9349 EMail: T.Clausen@computer.org URI: http://www.thomasclausen.org/ Baccelli, et al. Expires May 22, 2009 [Page 30] Internet-Draft OSPF MPR Extension for MANET November 2008 Full Copyright Statement Copyright (C) The IETF Trust (2008). 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. 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, THE IETF TRUST 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. Intellectual Property The IETF takes no position regarding the validity or scope of any Intellectual Property Rights or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; nor does it represent that it has made any independent effort to identify any such rights. Information on the procedures with respect to rights in RFC documents can be found in BCP 78 and BCP 79. Copies of IPR disclosures made to the IETF Secretariat and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementers or users of this specification can be obtained from the IETF on-line IPR repository at http://www.ietf.org/ipr. The IETF invites any interested party to bring to its attention any copyrights, patents or patent applications, or other proprietary rights that may cover technology that may be required to implement this standard. Please address the information to the IETF at ietf-ipr@ietf.org. Baccelli, et al. Expires May 22, 2009 [Page 31]