From 4bfd864f10b68b71482b35c818559068ef8d5797 Mon Sep 17 00:00:00 2001 From: Thomas Voss Date: Wed, 27 Nov 2024 20:54:24 +0100 Subject: doc: Add RFC documents --- doc/rfc/rfc5449.txt | 1739 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1739 insertions(+) create mode 100644 doc/rfc/rfc5449.txt (limited to 'doc/rfc/rfc5449.txt') diff --git a/doc/rfc/rfc5449.txt b/doc/rfc/rfc5449.txt new file mode 100644 index 0000000..0791425 --- /dev/null +++ b/doc/rfc/rfc5449.txt @@ -0,0 +1,1739 @@ + + + + + + +Network Working Group E. Baccelli +Request for Comments: 5449 P. Jacquet +Category: Experimental INRIA + D. Nguyen + CRC + T. Clausen + LIX, Ecole Polytechnique + February 2009 + + + OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks + +Status of This Memo + + This memo defines an Experimental Protocol for the Internet + community. It does not specify an Internet standard of any kind. + Discussion and suggestions for improvement are requested. + Distribution of this memo is unlimited. + +Copyright Notice + + Copyright (c) 2009 IETF Trust and the persons identified as the + document authors. All rights reserved. + + This document is subject to BCP 78 and the IETF Trust's Legal + Provisions Relating to IETF Documents (http://trustee.ietf.org/ + license-info) in effect on the date of publication of this document. + Please review these documents carefully, as they describe your rights + and restrictions with respect to this document. + +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 is denoted the "OSPFv3 MANET interface type". + + + + + + + + + + + + + + + + +Baccelli, et al. Experimental [Page 1] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + +Table of Contents + + 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 + 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 + 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 . . . . . . . 7 + 4.4. MPR Adjacency-Reduction . . . . . . . . . . . . . . . . . 7 + 5. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 7 + 5.1. Data Structures . . . . . . . . . . . . . . . . . . . . . 7 + 5.1.1. N(i): Symmetric 1-Hop Neighbor Set . . . . . . . . . . 7 + 5.1.2. N2(i): 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 . . . . . . . . . . . . . . . . 10 + 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 . . . . . . . . . . . . . . . . . . 12 + 5.2.4. Metric Signaling - METRIC-MPR 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 . . . . . . . . . . . . . . 17 + 5.5. Hybrid Routers . . . . . . . . . . . . . . . . . . . . . . 18 + 5.6. Synch Routers . . . . . . . . . . . . . . . . . . . . . . 18 + 5.7. Routing Table Computation . . . . . . . . . . . . . . . . 18 + 6. Packet Formats . . . . . . . . . . . . . . . . . . . . . . . . 19 + 6.1. Flooding-MPR TLV . . . . . . . . . . . . . . . . . . . . 19 + 6.2. Metric-MPR TLV . . . . . . . . . . . . . . . . . . . . . . 19 + 6.3. Path-MPR TLV . . . . . . . . . . . . . . . . . . . . . . . 22 + 7. Security Considerations . . . . . . . . . . . . . . . . . . . 24 + 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 25 + 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 26 + 9.1. Normative References . . . . . . . . . . . . . . . . . . . 26 + 9.2. Informative References . . . . . . . . . . . . . . . . . . 26 + + + +Baccelli, et al. Experimental [Page 2] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + Appendix A. Flooding-MPR Selection Heuristic . . . . . . . . . . 28 + Appendix B. Path-MPR Selection Heuristic . . . . . . . . . . . . 29 + Appendix C. Contributors . . . . . . . . . . . . . . . . . . . . 30 + Appendix D. Acknowledgments . . . . . . . . . . . . . . . . . . . 30 + +1. Introduction + + This document specifies an extension of OSPFv3 [RFC5340] that is + adapted to mobile ad hoc networks (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 Link State Advertisements (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 the Optimized Link State Routing Protocol (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], and Link-Local Signaling (LLS) terminology as defined in + [RFC4813]; it introduces the following terminology to the OSPF + nomenclature: + + OSPFv3 MANET interface - the OSPFv3 interface type for MANETs, as + specified in this document. + + + + + +Baccelli, et al. Experimental [Page 3] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + Additionally, the following terms are used in this document: + + MANET router - a router that has only OSPFv3 MANET interfaces. + + Wired router - a router that has only OSPFv3 interface of types + other than OSPFv3 MANET interfaces. + + Hybrid router - a router that 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 the considered 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 that brings up adjacencies with all of its + MANET neighbors. + + Flooding-MPR - a router that is selected by its symmetric 1-hop + neighbor, router X, to retransmit all broadcast protocol packets + that it receives from router X, provided that the 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 that 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 to router X. + + Multipoint relay (MPR) - a router that is selected by its symmetric + 1-hop neighbor as either a Flooding-MPR, a Path-MPR, or both. + + Flooding-MPR-selector - a router that has selected its symmetric + 1-hop neighbor, router X, as one of its Flooding-MPRs is a + Flooding-MPR-selector of router X. + + + + + + +Baccelli, et al. Experimental [Page 4] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + Path-MPR-selector - a router that 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 that has selected its symmetric 1-hop + neighbor, router X, as either one of its Flooding-MPRs, one of its + Path-MPRs, or both is an MPR-selector of router X. + +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, i.e., 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. Further, if two routers, R1 and R2, each + make a transmission, neither of these transmissions is guaranteed to + be received by the same subset of routers within the MANET -- even if + 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 that 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 satisfy. + 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 described in Section 3.1). As such, the + + + +Baccelli, et al. Experimental [Page 5] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + 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 + reduction and on 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 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 against + transmission errors (inherent when using wireless links) and against + 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). + + + + + +Baccelli, et al. Experimental [Page 6] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + +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 + 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 that + 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 that operate one or more MANET interfaces make use of the + data structures described below. + +5.1.1. N(i): Symmetric 1-Hop Neighbor Set + + The Symmetric 1-hop Neighbor set N(i) records router IDs of the set + of symmetric 1-hop neighbors of the router on interface i. More + precisely, N(i) records tuples of the form: + + + + + + +Baccelli, et al. Experimental [Page 7] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + (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 over interface i. + + 1_HOP_SYM_time: specifies the time at which the tuple expires and + MUST be removed from the set. + + For convenience throughout this document, N will denote the union of + all N(i) sets for all MANET interfaces on the router. + +5.1.2. N2(i): Symmetric Strict 2-Hop Neighbor Set + + The Symmetric strict 2-hop Neighbor set N2(i) records links between + routers in N(i) and their symmetric 1-hop neighbors, excluding: + + (i) the router performing the computation, and + + (ii) all routers in N(i). + + More precisely, N2(i) 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. + + For convenience throughout this document, N2 will denote the union of + all N2(i) sets for all MANET interfaces on the router. + +5.1.3. Flooding-MPR Set + + The Flooding-MPR set on interface i records router IDs of a subset of + the routers listed in N(i), selected such that, through this subset, + each router listed in N2(i) 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: + + + + +Baccelli, et al. Experimental [Page 8] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + (Flooding_MPR_id, Flooding_MPR_time) + + where: + + Flooding_MPR_id: is the router ID of the symmetric 1-hop neighbor of + this router that is 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. + +5.1.4. Flooding-MPR-Selector Set + + The Flooding-MPR-selector set on interface i records router IDs of + the set of symmetric 1-hop neighbors of this router on interface i + that have selected this router as their 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 its + 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 that provide + shortest paths from routers in N2 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. + + + + + +Baccelli, et al. Experimental [Page 9] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + 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 their 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) + + where: + + Path_MPR_SELECTOR_id: is the router ID of the symmetric 1-hop + neighbor of this router that has selected this router as its 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], and 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], which is appended to + Hello packets. If an LLS block is not already present, an LLS block + MUST be created and appended to the Hello packets. + + + + +Baccelli, et al. Experimental [Page 10] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + 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-MPR - signaling metrics. + + The layout and internal structure of these TLVs is detailed in + Section 6. + +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 that 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 that takes 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 by + 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-MPRs, 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. + + + + +Baccelli, et al. Experimental [Page 11] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + +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 that 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. + +5.2.4. Metric Signaling - METRIC-MPR 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 + interface, 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 by including METRIC-MPR TLVs. The METRIC- + MPR 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 that is not an OSPFv3 MANET interface. + +5.2.5. Path-MPR Selection + + A router that has one or more OSPFv3 MANET interfaces MUST select a + Path-MPR set from among routers in N. Routers in the Path-MPR set of + a router are those that take part in the shortest (with respect to + the metrics used) path from routers in N2 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 by 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: + + + +Baccelli, et al. Experimental [Page 12] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + 1. Neighbors that are both adjacent AND selected as Path-MPR for any + OSPFv3 MANET interface of the router generating the Hello packet. + + 2. Neighbors that 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 that have not been previously + included in this PMPR TLV. + + The list of neighbor IDs is followed by a list of costs for the links + from these neighbors 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 i. 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 MUST be recomputed when either of N(i) or N2(i) + has changed. The Path-MPR set MUST 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 costs. + + 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 an 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 that has one or more such OSPFv3 MANET interfaces MAY bring up + adjacencies with only a subset of its MANET neighbors. + + + +Baccelli, et al. Experimental [Page 13] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + Over an OSPFv3 MANET interface, a router MUST bring up adjacencies + with all MANET neighbors that 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. + +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 shortest + path tree (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 + that ceases to list this router as being adjacent (see + Section 5.2.6), the state of that neighbor MUST be changed to: + + 1. 2-Way if the neighbor is not in the MPR set or MPR-selector set, + or + + 2. ExStart if either the neighbor is in the MPR set or MPR-selector + set, or 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]. + + + + + +Baccelli, et al. Experimental [Page 14] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + Routers that have one or more OSPFv3 MANET interfaces 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 that have one or more OSPFv3 MANET interfaces MAY list other + links they have through those OSPFv3 MANET interfaces, at the expense + of larger LSAs. + + In addition, routers that have one or more OSPFv3 MANET interfaces + MUST generate updated Router-LSAs when either of the following + occurs: + + o a new adjacency has been brought up, reflecting a change in the + Path-MPR set; + + o a new adjacency has been brought up, reflecting a change in the + Path-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]. + + + +Baccelli, et al. Experimental [Page 15] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + (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]. + + (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. + + + + + + + +Baccelli, et al. Experimental [Page 16] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + +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. + + 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. + + + + +Baccelli, et al. Experimental [Page 17] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + 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. + +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 that 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 Synch 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 that 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. + + + + +Baccelli, et al. Experimental [Page 18] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + +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. + + 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 that 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 that 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 that 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 that SHOULD be cleared ('0') on + transmission and SHOULD be ignored on reception. + +6.2. Metric-MPR TLV + + A TLV of Type METRIC-MPR is defined for signaling costs of links to + neighbors, shown in Figure 2. + + + + +Baccelli, et al. Experimental [Page 19] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + 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-MPR | Length | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Reserved |U|R| Cost 0 | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Cost 1 | Cost 2 | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + : : + : : + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Cost n | Padding | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Figure 2: Metric TLV (METRIC-MPR) + + where: + + Reserved - is a 14-bit field that 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), or set ('1') if the costs advertised are reverse + (i.e., the costs of the links from the neighbors to the router). + By default, R is cleared ('0'). + + U - is a binary flag, cleared ('0') if the cost for each link from + the sending router and to each advertised neighbor is explicitly + included (shown in Figure 3), or set ('1') if a single metric + value is included that applies to all links (shown in Figure 4). + + Cost n - is an 8-bit unsigned integer field that 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 that SHOULD be cleared ('0') on + transmission and SHOULD be ignored on reception. Padding is + included in order that the TLV is 32-bit aligned. Padding MUST be + included when the TLV contains an even number of Cost fields and + MUST NOT be included otherwise. + + + + + + + +Baccelli, et al. Experimental [Page 20] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + 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-MPR | Length | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Reserved |0|R| Cost 0 | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Cost 1 | Cost 2 | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Figure 3: Metric Advertisement TLV (METRIC-MPR) 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-MPR | Length | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | Reserved |1|R| Cost | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + + Figure 4: Metric Advertisement TLV (METRIC-MPR) example with a single + and uniform link cost (U=1) (and, hence, no padding). + + + + + + + + + + + + + + + + + + + + + + + + + + + +Baccelli, et al. Experimental [Page 21] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + +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. + + 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 that 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 that specifies + the number of adjacent neighbors. These adjacent neighbors are + listed first among the symmetric 1-hop MANET neighbors of all + OSPFv3 MANET interfaces of the router in the PMPR TLV. + + # Path-MPR - is an 8-bit unsigned integer field that 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 that SHOULD be cleared ('0') on + transmission and SHOULD be ignored on reception. + + + + + +Baccelli, et al. Experimental [Page 22] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + 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), or set ('1') if a + single metric value is included that applies to all links (as + shown in Figure 7). + + 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, or set ('1') if the router brings up + adjacencies with all MANET neighbors as a Synch router, as per + Section 5.6. + + Neighbor ID - is a 32-bit field that 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 that specifies the cost + of the link in the direction from the n-th 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 that SHOULD be cleared ('0') on + transmission and SHOULD be ignored on reception. Padding is + included in order that the PMPR TLV is 32-bit aligned. Padding + MUST be included when the TLV contains an odd number of Cost + fields and MUST NOT be included otherwise. + + + + + + + + + + + + + + + + + + + + +Baccelli, et al. Experimental [Page 23] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + 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 |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=PMPR | Length | + +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ + | # Sym Neigh | # 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. Experimental [Page 24] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + However, the use of a wireless medium 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 + predetermined 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; meanwhile, + 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 type values have been + allocated from the LLS TLV type registry defined in [RFC4813]. + + +------------+------------+--------------+ + | Mnemonic | Type Value | Name | + +------------+------------+--------------+ + | FMPR | 3 | Flooding-MPR | + | METRIC-MPR | 4 | Metric-MPR | + | PMPR | 5 | Path-MPR | + +------------+------------+--------------+ + + Table 1: LLS TLV Type Assignments + + + + + +Baccelli, et al. Experimental [Page 25] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + +9. References + +9.1. Normative References + + [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate + Requirement Levels", BCP 14, RFC 2119, March 1997. + + [RFC2328] Moy, J., "OSPF Version 2", STD 54, RFC 2328, + April 1998. + + [RFC4813] Friedman, B., Nguyen, L., Roy, A., Yeung, D., and + A. Zinin, "OSPF Link-Local Signaling", RFC 4813, + March 2007. + + [RFC5340] Coltun, R., Ferguson, D., Moy, J., and A. Lindem, + "OSPF for IPv6", RFC 5340, July 2008. + +9.2. Informative References + + [MPR] Qayyum, A., Viennot, L., and A. Laouiti, + "Multipoint Relaying for Flooding Broadcast + Messages in Mobile Wireless Networks", Proceedings + of HICSS , 2002. + + [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-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-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. + + [RFC2501] Corson, S. and J. Macker, "Mobile Ad hoc Networking + (MANET): Routing Protocol Performance Issues and + Evaluation Considerations", RFC 2501, + February 1999. + + [RFC3626] Clausen, T. and P. Jacquet, "Optimized Link State + Routing Protocol (OLSR)", RFC 3626, October 2003. + + + + + +Baccelli, et al. Experimental [Page 26] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + [RFC4593] Barbir, A., Murphy, S., and Y. Yang, "Generic + Threats to Routing Protocols", RFC 4593, + October 2006. + + [RFC5148] Clausen, T., Dearlove, C., and B. Adamson, "Jitter + Considerations in Mobile Ad Hoc Networks (MANETs)", + RFC 5148, February 2008. + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +Baccelli, et al. Experimental [Page 27] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + +Appendix A. Flooding-MPR Selection Heuristic + + The following specifies a proposed heuristic for selection of + Flooding-MPRs on interface i. 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(i), defined as the number of neighbors of router Y, EXCLUDING + all the members of N(i) 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(i), for all routers in + N(i). + + 2. Add to the Flooding-MPR set those routers in N(i) that are the + only routers to provide reachability to a router in N2(i). For + example, if router B in N2(i) can be reached only through a + router A in N(i), then add router A to the Flooding-MPR set. + Remove the routers from N2(i) that are now covered by a router in + the Flooding-MPR set. + + 3. While there exist routers in N2(i) that are not covered by at + least one router in the Flooding-MPR set: + + 1. For each router in N(i), calculate the reachability, i.e., + the number of routers in N2(i) that are not yet covered by at + least one router in the Flooding-MPR set, and that are + reachable through this 1-hop neighbor; + + 2. Select as a Flooding-MPR the neighbor with the highest + willingness among the routers in N(i) with non-zero + reachability. In case of a tie among routers with the same + willingness, select the router that provides reachability to + the maximum number of routers in N2(i). 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(i) that 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(i) + 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 + Flooding-MPR set. + + + + +Baccelli, et al. Experimental [Page 28] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + 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 with 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. Experimental [Page 29] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + + 4. The coefficients cost(B,C) of the cost matrix for a link that + connects a neighbor B to a 2-hop neighbor C are 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(i) and N2' instead of N2(i). 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). + +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. + +Appendix D. Acknowledgments + + The authors would like to thank Juan Antonio Cordero Fuertes, Ulrich + Herberg, and Richard Ogier for reviewing this document. + + + + + + + +Baccelli, et al. Experimental [Page 30] + +RFC 5449 OSPF MPR Extension for MANET February 2009 + + +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 + + Phone: +33 6 6058 9349 + EMail: T.Clausen@computer.org + URI: http://www.thomasclausen.org/ + + + + + + + + + + + + + + + + + + + + + +Baccelli, et al. Experimental [Page 31] + -- cgit v1.2.3