summaryrefslogtreecommitdiff
path: root/doc/rfc/rfc5449.txt
diff options
context:
space:
mode:
Diffstat (limited to 'doc/rfc/rfc5449.txt')
-rw-r--r--doc/rfc/rfc5449.txt1739
1 files changed, 1739 insertions, 0 deletions
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]
+