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

This html diff was produced by rfcdiff 1.35. The latest version is available from http://tools.ietf.org/tools/rfcdiff/