draft-ietf-ospf-manet-mpr-00.txt   draft-ietf-ospf-manet-mpr-01.txt 
Open Shortest Path (OSPF) E. Baccelli Open Shortest Path (OSPF) E. Baccelli
Internet-Draft P. Jacquet Internet-Draft P. Jacquet
Expires: August 10, 2008 D. Nguyen Intended status: Experimental D. Nguyen
INRIA Expires: January 11, 2009 INRIA
T. Clausen T. Clausen
LIX, Ecole Polytechnique, France LIX, Ecole Polytechnique, France
February 7, 2008 July 10, 2008
OSPF MPR Extension for Ad Hoc Networks OSPF MPR Extension for Ad Hoc Networks
draft-ietf-ospf-manet-mpr-00 draft-ietf-ospf-manet-mpr-01
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
other groups may also distribute working documents as Internet- other groups may also distribute working documents as Internet-
Drafts. Drafts.
skipping to change at page 1, line 37 skipping to change at page 1, line 37
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 August 10, 2008. This Internet-Draft will expire on January 11, 2009.
Copyright Notice
Copyright (C) The IETF Trust (2008).
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, enhanced with MANET techniques based on multi-point interface type, and denoted the "OSPFv3 MANET interface type".
relaying (MPR).
Table of Contents Table of Contents
1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . 3
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3
3. Applicability Statement . . . . . . . . . . . . . . . . . . . 6 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 5
4. Protocol Overview and Functionning . . . . . . . . . . . . . . 7 3.1. MANET Characteristics . . . . . . . . . . . . . . . . . . 5
4.1. Efficient Flooding with MPR . . . . . . . . . . . . . . . 7 3.2. OSPFv3 MANET Interface Characteristics . . . . . . . . . . 5
4.2. MPR Topology Reduction . . . . . . . . . . . . . . . . . . 7 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 6
4.3. Multicast Transmissions of Protocol Packets . . . . . . . 7 4.1. Efficient Flooding using MPRs . . . . . . . . . . . . . . 6
4.4. MPR Adjacency Reduction . . . . . . . . . . . . . . . . . 8 4.2. MPR Topology Reduction . . . . . . . . . . . . . . . . . . 6
5. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 9 4.3. Multicast Transmissions of Protocol Packets . . . . . . . 6
5.1. Data Structures . . . . . . . . . . . . . . . . . . . . . 9 4.4. MPR Adjacency Reduction . . . . . . . . . . . . . . . . . 7
5.2. Hello Protocol . . . . . . . . . . . . . . . . . . . . . . 11 5. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 7
5.2.1. Flooding MPR Selection . . . . . . . . . . . . . . . . 11 5.1. Data Structures . . . . . . . . . . . . . . . . . . . . . 7
5.2.2. Flooding MPR Selection Signalling in HELLO Packets . . 11 5.1.1. N: Symmetric 1-hop Neighbor Set . . . . . . . . . . . 7
5.2.3. Neighbor Ordering in HELLO Packets . . . . . . . . . . 11 5.1.2. N2: Symmetric strict 2-hop Neighbor Set . . . . . . . 8
5.2.4. Metric Signalling in HELLO Packets . . . . . . . . . . 12 5.1.3. Flooding-MPR set . . . . . . . . . . . . . . . . . . . 8
5.2.5. Path MPR Selection . . . . . . . . . . . . . . . . . . 12 5.1.4. Flooding-MPR-selector set . . . . . . . . . . . . . . 8
5.2.6. Path MPR Selection Signalling in HELLO Packets . . . . 12 5.1.5. Path-MPR set . . . . . . . . . . . . . . . . . . . . . 9
5.1.6. Path-MPR-selector set . . . . . . . . . . . . . . . . 9
5.1.7. MPR-selector set . . . . . . . . . . . . . . . . . . . 10
5.1.8. MPR set . . . . . . . . . . . . . . . . . . . . . . . 10
5.2. Hello Protocol . . . . . . . . . . . . . . . . . . . . . . 10
5.2.1. Flooding-MPR Selection . . . . . . . . . . . . . . . . 10
5.2.2. Flooding-MPR Selection Signalling - FMPR TLV . . . . . 11
5.2.3. Neighbor Ordering . . . . . . . . . . . . . . . . . . 11
5.2.4. Metric Signalling - METRIC TLV and PMPR TLV . . . . . 11
5.2.5. Path-MPR Selection . . . . . . . . . . . . . . . . . . 12
5.2.6. Path-MPR Selection Signalling - PMPR TLV . . . . . . . 12
5.2.7. Hello Packet Processing . . . . . . . . . . . . . . . 12 5.2.7. Hello Packet Processing . . . . . . . . . . . . . . . 12
5.3. Adjacencies . . . . . . . . . . . . . . . . . . . . . . . 13 5.3. Adjacencies . . . . . . . . . . . . . . . . . . . . . . . 13
5.3.1. Protocol Packets over 2-WAY Links . . . . . . . . . . 13 5.3.1. Packets over 2-Way Links . . . . . . . . . . . . . . . 13
5.3.2. Adjacency Conservation . . . . . . . . . . . . . . . . 14 5.3.2. Adjacency Conservation . . . . . . . . . . . . . . . . 13
5.4. Link State Advertisements . . . . . . . . . . . . . . . . 14 5.4. Link State Advertisements . . . . . . . . . . . . . . . . 13
5.4.1. LSA Flooding . . . . . . . . . . . . . . . . . . . . . 14 5.4.1. LSA Flooding . . . . . . . . . . . . . . . . . . . . . 14
5.4.2. Link State Acknowlements . . . . . . . . . . . . . . . 15 5.4.2. Link State Acknowledgments . . . . . . . . . . . . . . 15
6. Security Considerations . . . . . . . . . . . . . . . . . . . 17 5.5. Hybrid Routers . . . . . . . . . . . . . . . . . . . . . . 16
7. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 18 5.6. Synch Routers . . . . . . . . . . . . . . . . . . . . . . 17
8. References . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5.7. Routing Table Computation . . . . . . . . . . . . . . . . 17
8.1. Normative References . . . . . . . . . . . . . . . . . . . 22 6. Packet Formats . . . . . . . . . . . . . . . . . . . . . . . . 17
8.2. Informative References . . . . . . . . . . . . . . . . . . 22 6.1. Flooding-MPR Selection TLV . . . . . . . . . . . . . . . . 18
Appendix A. Flooding MPR Selection Heuristic . . . . . . . . . . 23 6.2. Metric Information TLV . . . . . . . . . . . . . . . . . . 18
6.3. Path-MPR Selection TLV . . . . . . . . . . . . . . . . . . 20
7. Security Considerations . . . . . . . . . . . . . . . . . . . 23
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 23
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 23
9.1. Normative References . . . . . . . . . . . . . . . . . . . 23
9.2. Informative References . . . . . . . . . . . . . . . . . . 24
Appendix A. Flooding MPR Selection Heuristic . . . . . . . . . . 24
Appendix B. Path MPR Selection Heuristic . . . . . . . . . . . . 25 Appendix B. Path MPR Selection Heuristic . . . . . . . . . . . . 25
Contributors . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 Appendix C. Contributors . . . . . . . . . . . . . . . . . . . . 27
Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . . . 28 Appendix D. Acknowledgments . . . . . . . . . . . . . . . . . . . 27
Intellectual Property and Copyright Statements . . . . . . . . . . 29
1. Introduction 1. Introduction
This document specifies an extension of OSPFv3 [2] adapted to MANETs This document specifies an extension of OSPFv3 [RFC2740] adapted to
[6], based on mechanisms providing: MANETs [RFC2501], and based on mechanisms providing:
- Flooding reduction: a mechanism reducing the number of Flooding reduction: only a subset of all routers will be involved in
(re)transmissions during floods. (re)transmissions during a flooding operation.
- Topology reduction: a mechanism reducing the number and the size Topology reduction: only a subset of links are advertised, hence
of LSAs, by advertizing only a subset of the existing links. both the number and the size of LSAs are decreased.
- Adjacency reduction: a mechanism reducing the database Adjacency reduction: adjacencies are brought up only with a subset
synchronization overhead by bringing up only selected adjacencies. of neighbors, for lower database synchronization overhead.
These mechanisms are based on multipoint relaying (MPR), a technique These mechanisms are based on multipoint relays (MPR), a technique
developed in OLSR, the proactive routing solution standardized in developed in OLSR [RFC3626].
MANET [5] [7].
The extension specified in this document integrates the OSPF The extension specified in this document integrates into the OSPF
framework by defining an OSPF interface type: the MANET interface. framework by defining the OSPFv3 MANET interface type. While this
While this extension enables OSPF to function efficiently on mobile extension enables OSPFv3 to function efficiently on mobile ad hoc
ad hoc networks, operation of OSPF on other types of interfaces or networks, operation of OSPFv3 on other types of interfaces or
networks remains unaltered, whether there are MANET interfaces in the networks, or in areas without OSPFv3 MANET interfaces, remains
area or not. unaltered, whether there are MANET interfaces in the area or not.
2. Terminology 2. Terminology
The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
"SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
document are to be interpreted as described in RFC2119 [3]. "OPTIONAL" in this document are to be interpreted as described in
[RFC2119].
Additionally, this document uses traditional OSPF terminology as This document uses OSPF terminology as defined in [RFC2328] and
defined in [1] [2], LLS terminology as defined in [4], as well as the [RFC2740], LLS terminology as defined in [RFC4813], and introduces
following terms: the following terminology to the OSPF nomenclature:
MANET interface - the OSPF interface type for MANETs, specified in OSPFv3 MANET interface - the OSPFv3 interface type for MANETs, as
this document. specified in this document.
MANET router - a router which has only MANET interface(s). Additionally, the following terms are used in this document:
Wired router - a router which only has OSPF interface(s) of types MANET router - a router which has only OSPFv3 MANET interface(s).
other than MANET.
Hybrid router - a router which has OSPF interfaces of several types, Wired router - a router which has only OSPFv3 interface of types
including the MANET type. other than OSPFv3 MANET interfaces.
Neighbor - a router, reachable through an OSPF interface (of any Hybrid router - a router which has OSPFv3 interfaces of several
type). types, including at least one of the OSPFv3 MANET interface type.
MANET neighbor - a neighbor, reachable through an OSPF interface of Neighbor - a router, reachable through an OSPFv3 interface (of any
type MANET. type).
Symmetric neighbor - a neighbor, in a state greater than or equal to MANET neighbor - a neighbor, reachable through an OSPFv3 MANET
2-Way (through an interface of any type). interface.
Symmetric 2-hop neighbor - a symmetric neighbor of a symmetric Symmetric 1-hop neighbor - a neighbor, in a state greater than or
neighbor, which is not a neighbor of the considered router. equal to 2-Way (through an interface of any type).
Neighborhood - the set formed by the symmetric neighbors of the Symmetric strict 2-hop neighbor - a symmetric 1-hop neighbor of a
considered router. symmetric 1-hop neighbor, which is not itself a symmetric 1-hop
neighbor of this router.
2-hop neighborhood - the set formed by all the symmetric 2-hop Symmetric strict 2-hop neighborhood - the set formed by all the
neighbors of the considered router. symmetric strict 2-hop neighbors of the considered router.
Synch router - a router which brings up adjacencies with all its Synch router - a router which brings up adjacencies with all of its
MANET neighbors. MANET neighbors.
Flooding MPR set - the subset of symmetric neighbors selected as Flooding-MPR - A router which is selected by its symmetric 1-hop
flooding MPR by this router. neighbor, router X, to retransmit all broadcast protocol packets
that it receives from router X, provided that that broadcast
protocol packet is not a duplicate, and that the hop limit field
of the protocol packet is greater than one.
Flooding MPR selector set - the subset of symmetric neighbors that Path-MPR - A router, which is selected by a symmetric 1-hop
have selected this router as flooding MPR. neighbor, X, as being on the shortest path from a router in the
symmetric strict 2-hop neighborhood of router X and to the router
X.
Path MPR set - the subset of symmetric neighbors selected as path Multipoint Relay (MPR) - A router which is selected by its symmetric
MPR by this router. 1-hop neighbor as either Flooding-MPR or as Path-MPR, or as both.
Path MPR selector set - the subset of symmetric neighbors that have Flooding-MPR Selector - A router which has selected its symmetric
selected this router as path MPR. 1-hop neighbor, router X, as one of its Flooding-MPRs is a
Flooding-MPR selector of router X.
MPR (selector) set - the union of the flooding MPR (selector) set Path MPR Selector - A router which has selected its symmetric 1-hop
and the path (selector) MPR set of this router. neighbor, router X, as one of its Path-MPRs is a Path-MPR selector
of router X.
MPR Selector - A router which has selected its symmetric 1-hop
neighbor, router X, as either one of its Flooding-MPRs or as one
of its Path-MPRs or as both is an MPR selector of router X.
3. Applicability Statement 3. Applicability Statement
Characteristics of MANETs include mobility and "half-broadcast" The OSPFv3 MANET interface type, defined in this specification,
capabilities [9], i.e., a router that makes a transmission on a MANET allows OSPFv3 to be deployed within an area where parts of that area
can only assume that a subset of the routers attached to the MANET is a mobile ad hoc network (MANET) with moderate mobility properties.
will hear this transmission. In particular, these characteristics
are not compatible with several traditional OSPF mechanisms,
including some reducing the amount of control traffic, such as
flooding reduction, topology reduction and adjacency reduction (e.g.
Designated Router). However, OSPF's efficient operation over MANETs
relies on drastic control traffic reduction, as wireless links
generally feature bandwidth scarcity and interference issues.
The MANET interface type enables OSPF operation on mobile ad hoc 3.1. MANET Characteristics
networks, by providing specific flooding reduction, topology
reduction and adjacency reduction mechanisms adapted to MANET
characteristics. These mechanisms are derived from solutions
standardized by the MANET working group. However, while MANET
standards address optimized ad hoc routing solutions for truely
mobile enviromnents, OSPF's extension for ad hoc networks addresses
less mobile scenarios, that possibly include parts of the network
that are fixed, using solely the traditional OSPF framework.
4. Protocol Overview and Functionning MANETs [RFC2501] are networks in which a dynamic network topology is
a frequently expected condition, often due to router mobility and/or
to varying quality of wireless links - the latter of which also
generally entails bandwidth scarcity and interference issues between
neighbors.
This document specifies an OSPFv3 interface type tailored for mobile Moreover, MANETs often exhibit "semi-broadcast" properties: a router
ad hoc networks: the MANET interface. R that makes a transmission within a MANET can only assume that
transmission to be received by a subset of the total number of
routers within that MANET: if two routers, R1 and R2, each make a
transmission, each of these transmissions is not guaranteed to be
received by the same subset of routers within the MANET - and this
even if each of R1 and R2 can mutually receive transmissions from the
other.
The MANET interface makes use of flooding reduction, topology These characteristics are incompatible with several OSPFv3
reduction and adjacency reduction mechanisms based on multipoint mechanisms, including, but not limited to, existing mechanisms for
relaying (MPR), a technique derived from OLSR [5] [7], the proactive control traffic reduction, such as flooding reduction, topology
routing solution standardized in MANET. reduction and adjacency reduction (e.g. Designated Router).
4.1. Efficient Flooding with MPR 3.2. OSPFv3 MANET Interface Characteristics
MANET interfaces use a flooding reduction mechanism called MPR An interface of the OSPFv3 MANET interface type is the point of
flooding, whereby only some MANET neighbors (those selected as attachment of an OSPFv3 router to a network which may have MANET
flooding-MPR) are responsible for retransmitting a routing packet characteristics. That is, an interface of the OSPFv3 MANET interface
flooded over a MANET interface. This mechanism drastically reduces type is able to accommodate the MANET characteristics described in
the number of (re)transmissions during flooding procedures, while Section 3.1. An OSPFv3 MANET interface type is not prescribing a set
still providing a natural high resilience to transmission errors of behaviors or expectations that the network is required to have,
(inherent to the use of wireless links), and obsolete two-hop but rather is setting operating conditions under which protocols on
neighbor information (frequently caused by the mobility of the an interface towards that network must be able to function (i.e. the
routers). protocols are required to be able to operate correctly when faced
with the characteristics as described in Section 3.1). As such, the
OSPFv3 MANET interface type is a generalization of other OSPFv3
interface types; for example a protocol operating correctly over an
OSPFv3 MANET interface would also operate correctly over an OSPFv3
broadcast interface (whereas the inverse would not necessarily be
true).
Efficient OSPFv3 operation over MANETs relies on control traffic
reduction, and using mechanisms appropriate for semi-broadcast.
The OSPFv3 MANET interface type, defined in this document, integrates
support for networks with MANET characteristics into the OSPFv3
framework by integrating mechanisms (flooding reduction, topology
reduction and adjacency reduction) derived from solutions
standardized by the MANET working group.
4. Protocol Overview and Functioning
The OSPFv3 MANET interface type, defined in this specification, makes
use of flooding reduction, topology reduction and adjacency
reduction, all based on multipoint relaying (MPR) - a technique
derived from [RFC3626], as standardized in the MANET working group.
Moreover, multicast transmissions of protocol packets are used as
much as possible.
4.1. Efficient Flooding using MPRs
OSPFv3 MANET interfaces use a flooding reduction mechanism denoted
MPR flooding [MPR], whereby only a subset of MANET neighbors (those
selected as Flooding-MPR) participate in a flooding operation. This
reduces the number of (re)transmissions necessary for a flooding
operation [MPR-analysis], while retaining resilience to transmission
errors (inherent when using wireless links), and obsolete two-hop
neighbor information (frequently caused by mobility of routers)
[MPR-robustness].
4.2. MPR Topology Reduction 4.2. MPR Topology Reduction
MANET interfaces use a topology reduction mechanism called MPR OSPFv3 MANET interfaces use a topology reduction mechanism denoted
topology reduction, whereby only necessary wireless links to MANET MPR topology reduction, whereby only necessary links to MANET
neighbors (those concerned by path-MPR selection, as belonging to neighbors (those identified by Path-MPR selection as belonging to
shortest paths) are listed in LSAs. MANET routers periodically shortest paths) are included in LSAs. Routers in a MANET
generate and flood Router-LSAs describing their selection of wireless periodically generate and flood Router-LSAs describing their
links to (current) MANET neighbors as point-to-point links. This selection of such links to their Path-MPRs. Such links are reported
mechanism greatly reduces the size of LSAs originated by MANET as point-to-point links. This reduces the size of LSAs originated by
routers, while still keeping OSPF's traditional properties: optimal routers on a MANET [MPR-topology], while retaining classic OSPF
paths using synchronized adjacencies. properties: optimal paths using synchronized adjacencies.
4.3. Multicast Transmissions of Protocol Packets 4.3. Multicast Transmissions of Protocol Packets
In order to reduce the overhead, multicast is used as much as OSPFv3 MANET interfaces employ multicast transmissions, when
possible for protocol packet transmissions over MANET interfaces, possible, thereby taking advantage of inherent broadcast capabilities
taking advantage of broadcast capabilities of the wireless medium of the medium, if present (with wireless interfaces, this can often
[9]. In particular, LSA acknowledgements are sent via multicast over be the case [RFC2501]). In particular, LSA acknowledgments are sent
these interfaces, and retransmissions over the same interfaces are via multicast over these interfaces, and retransmissions over the
considered as implicit acknowledgements. Intelligent jitter same interfaces are considered as implicit acknowledgments. Jitter
management delaying packets' (re)transmissions may also be used to management, such as delaying packet (re)transmission, can be employed
increase the chance to bundle several packets in a single in order to allow several packets to be bundled into a single
transmission, or to avoid superfluous retransmissions due to packet transmission, which may avoid superfluous retransmissions due to
collisions (see [10]). packet collisions [RFC5148].
4.4. MPR Adjacency Reduction 4.4. MPR Adjacency Reduction
Furthermore, MANET routers may form adjacencies with a subset of Adjacencies over OSPFv3 MANET interfaces are required to be formed
their MANET neighbors (instead of all of them). However, no only with a subset of the neighbors of that OSPFv3 MANET interface.
Designated Router or Backup Designated Router is elected on an OSPF No Designated Router or Backup Designated Router are elected on an
MANET. Instead, most MANET routers bring up adjacencies only with OSPFv3 MANET interface. Rather, adjacencies are brought up over an
their MPR and MPR selectors, while some select MANET routers (called OSPFv3 MANET interface only with MPRs and MPR Selectors. Only some
Synch routers) must bring up adjacencies with all their MANET select routers in the MANET (called Synch routers) bring up
neighbors. This reduces the amount of control traffic needed for adjacencies with all their MANET neighbors. This reduces the amount
database synchronization, while ensuring that LSAs still describe of control traffic needed for database synchronization, while
synchronized adjacencies only. ensuring that LSAs still describe only synchronized adjacencies.
5. Protocol Details 5. Protocol Details
This section specifies the information that must be maintained, This section complements [RFC2740] and specifies the information that
processed and transmitted by MANET and hybrid routers, and must be maintained, processed and transmitted by routers which
complements RFC 2740 [2]. operate one or more OSPFv3 MANET interfaces.
5.1. Data Structures 5.1. Data Structures
In addition to the values used in RFC 2740 [2], the type field in the In addition to the values used in [RFC2740], 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,
in addition to the protocol structures defined by RFC 2740 [2], MANET and in addition to the protocol structures defined by [RFC2740],
and hybrid routers make use of the data structures described below. routers which operate one or more MANET interfaces make use of the
data structures described below.
N : 5.1.1. N: Symmetric 1-hop Neighbor Set
the router IDs of the set of symmetric neighbors of the router. The Symmetric 1-hop Neighbor Set records router IDs of the set of
More precisely, N lists tuples of the form (1_HOP_SYM_id, symmetric 1-hop neighbors of the router. More precisely, N records
1_HOP_SYM_time). 1_HOP_SYM_id is the router ID of the symmetric tuples of the form:
neighbor. 1_HOP_SYM_time specifies the time, at which the tuple
expires and MUST be removed from the set.
N2 : (1_HOP_SYM_id, 1_HOP_SYM_time)
the router IDs of the set of symmetric neighbors of routers that where:
are in N, excluding:
1_HOP_SYM_id: is the router ID of the symmetric 1-hop neighbor of
this router.
1_HOP_SYM_time: specifies the time, at which the tuple expires and
MUST be removed from the set.
5.1.2. N2: Symmetric strict 2-hop Neighbor Set
The Symmetric strict 2-hop Neighbor Set records links between routers
in the symmetric 1-hop neighbors and these routers symmetric 1-hop
neighbors, excluding:
(i) the router performing the computation (i) the router performing the computation
(ii) all routers in N. (ii) all routers in N.
More precisely, N2 lists tuples of the form (2_HOP_SYM_id, More precisely, N2 records tuples of the form:
1_HOP_SYM_id, 2_HOP_SYM_time). 2_HOP_SYM_id is the router ID of a
symmetric 2-hops neighbor. 1_HOP_SYM_id is the router ID of the (2_HOP_SYM_id, 1_HOP_SYM_id, 2_HOP_SYM_time)
symmetric neighbor through which the 2-hop neighbor can be
reached. 2_HOP_SYM_time specifies the time, at which the tuple where:
2_HOP_SYM_id: is the router ID of a symmetric strict 2-hop neighbor.
1_HOP_SYM_id: is the router ID of the symmetric 1-hop neighbor of
this router through which the symmetric strict 2-hop neighbor can
be reached.
2_HOP_SYM_time: specifies the time, at which the tuple expires and
MUST be removed from the set.
5.1.3. Flooding-MPR set
The Flooding-MPR set records router IDs of a subset of the routers
listed in N, selected such that through this subset, each router
listed in N2 is reachable in 2 hops by this router. More precisely,
the Flooding-MPR set records tuples of the form:
(Flooding_MPR_id, Flooding_MPR_time)
where:
Flooding_MPR_id: is the router ID of the symmetric 1-hop neighbor of
this router, selected as Flooding-MPR.
Flooding_MPR_time: specifies the time, at which the tuple expires
and MUST be removed from the set.
Flooding-MPR selection is detailed in Section 5.2.1.
5.1.4. Flooding-MPR-selector set
The Flooding-MPR-selector set records router IDs of the set of
symmetric 1-hop neighbors of this router that have selected this
router as Flooding-MPR. More precisely, the Flooding-MPR-selector
set records tuples of the form:
(Flooding_MPR_SELECTOR_id, Flooding_MPR_SELECTOR_time)
where:
Flooding_MPR_SELECTOR_id: is the router ID of the symmetric 1-hop
neighbor of this router that has selected this router as Flooding-
MPR.
Flooding_MPR_SELECTOR_time: specifies the time at which the tuple
expires and MUST be removed from the set. expires and MUST be removed from the set.
Flooding-MPR set: Flooding-MPR selection is detailed in Section 5.2.1.
the router IDs of a subset of the routers listed in N, selected 5.1.5. Path-MPR set
such that through this subset, each router listed in N2 is
reachable. These neighbors are said to have been "selected as
flooding MPR" by the router. More precisely, the Flooding-MPR set
lists tuples of the form (Flooding_MPR_id, Flooding_MPR_time).
Flooding_MPR_id is the router ID of the symmetric neighbor
selected as flooding MPR. Flooding_MPR_time specifies the time,
at which the tuple expires and MUST be removed from the set. For
details about MPR selection, see Section 5.2.
Flooding-MPR-selector set: The Path-MPR set records router IDs of a subset of the routers listed
in N that provide shortest paths from the members of N2 to this
router. More precisely, the Path-MPR set records tuples of the form:
the router IDs of the set of neighbors that have selected the (Path_MPR_id, Path_MPR_time)
router as flooding MPR. More precisely, the Flooding-MPR-selector
set lists tuples of the form (Flooding_MPR_SELECTOR_id,
Flooding_MPR_SELECTOR_time). Flooding_MPR_SELECTOR_id is the
router ID of the symmetric neighbor that has selected the router
as flooding MPR. Flooding_MPR_SELECTOR_time specifies the time at
which the tuple expires and MUST be removed from the set. For
details about Flooding MPR selection, see Section 5.2.
Path-MPR set: where:
the router IDs of a subset of the routers listed in N that provide Path_MPR_id: is the router ID of the symmetric 1-hop neighbor of
shortest paths from the members of N2 to the router. These this router, that is selected as Path-MPR.
neighbors are said to have been "selected as path MPR" by the
router. More precisely, the Path-MPR set lists tuples of the form
(Path_MPR_id, Path_MPR_time). Path_MPR_id is the router ID of the
symmetric neighbor selected as path MPR. Path_MPR_time specifies
the time at which the tuple expires and MUST be removed from the
set. For details about path MPR selection, see Section 5.2.
Path-MPR-selector set : Path_MPR_time: specifies the time at which the tuple expires and
MUST be removed from the set.
the router IDs of the set of neighbors that have selected the Path-MPR selection is detailed in Section 5.2.5.
router as path MPR. More precisely, the Path-MPR-selector set
lists tuples of the form (Path_MPR_SELECTOR_id, 5.1.6. Path-MPR-selector set
Path_MPR_SELECTOR_time). Path_MPR_SELECTOR_id is the router ID of
the symmetric neighbor that has selected the router as path MPR. The Path-MPR-selector set records router IDs of the set of symmetric
Path_MPR_SELECTOR_time specifies the time at which the tuple 1-hop neighbors that have selected this router as Path-MPR. More
expires and MUST be removed from the set. For details about path precisely, the Path-MPR-selector set records tuples of the form:
MPR selection, see Section 5.2.
(Path_MPR_SELECTOR_id, Path_MPR_SELECTOR_time)
where:
Path_MPR_SELECTOR_id: is the router ID of the symmetric 1-hop
neighbor of this router that has selected this router as Path-MPR.
Path_MPR_SELECTOR_time: specifies the time at which the tuple
expires and MUST be removed from the set.
Path-MPR selection is detailed in Section 5.2.5.
5.1.7. MPR-selector set
The MPR-Selector Set is the union of the Flooding-MPR-selector set
and the Path-MPR-selector set.
5.1.8. MPR set
The MPR set is the union of the Flooding-MPR set and the Path-MPR
set.
5.2. Hello Protocol 5.2. Hello Protocol
On MANET interfaces, packets are sent, received and processed as On OSPFv3 MANET interfaces, packets are sent, received and processed
defined by RFC 2740 [2] and RFC 2328 [1], with the following as defined in [RFC2740] and [RFC2328], augmented for MPR selection as
additions for MPR selection as described in this section. detailed in this section.
5.2.1. Flooding MPR Selection All additional signaling for OSPFv3 MANET interfaces is through
inclusion of TLVs within an LLS block [RFC4813], appended to Hello
packets. If an LLS block is not already present, an LLS block MUST
be created and appended to the Hello packets.
The objective of flooding MPR selection is for a router to select a Hello packets sent over an OSPFv3 MANET interface MUST have the L bit
of the OSPF Options field set, as per [RFC4813], indicating the
presence of an LLS block.
Flooding-MPR selection is signaled using TLVs of the type FMPR, Path-
MPRs using TLVs of the type PMPR and metrics using TLVs of the type
METRIC. The layout and internal structure of these TLVs is detailed
in Section 6.
5.2.1. Flooding-MPR Selection
The objective of Flooding-MPR selection is for a router to select a
subset of its neighbors such that a packet, retransmitted by these 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 Flooding-MPR set of a router is computed such that, for each OSPFv3
interface, it satisfies this criterion. The information required to MANET interface, it satisfies this criterion. The information
perform this calculation (i.e. link sensing and neighborhood required to perform this calculation (i.e. link sensing and
information) is acquired through periodic exchange of OSPF HELLO neighborhood information) is acquired through periodic exchange of
packets. OSPFv3 Hello packets.
Flooding MPRs are computed by each MANET or hybrid router. The Flooding-MPRs are computed by each router which operates at least one
smaller the flooding MPR set is, the lower the overhead will be. OSPFv3 MANET interface. The smaller the Flooding-MPR set is, the
However, while it is not essential that the flooding MPR set is lower the overhead will be. However, while it is not essential that
minimal, it is essential that all 2-hop neighbors can be reached the Flooding-MPR set is minimal, the "coverage criterion" MUST be
through the selected flooding MPR routers. A router MUST select a satisfied by the selected Flooding-MPR set.
flooding MPR set such that any 2-hop neighbor is covered by at least
one flooding MPR router.
Flooding MPR selection priority may be given to neighbor routers in The willingness of a neighbor router to act as Flooding-MPR MAY be
descending order of their willingness to flood traffic on behalf of taken into consideration by a heuristic for Flooding-MPR selection.
other routers. Appendix A gives a heuristic for flooding MPR An example heuristic taking willingness into account is given in
selection. Appendix A.
5.2.2. Flooding MPR Selection Signalling in HELLO Packets 5.2.2. Flooding-MPR Selection Signalling - FMPR TLV
A router that has selected flooding MPRs among its neighbors MUST A router MUST signal its Flooding-MPRs set to its neighbors, through
signal this selection through appending LLS information (TLV type 3) including a FMPR TLV in generated Hello packets. Inclusion of this
at the end of its HELLO packets as described in Section 7. This FMPR TLV signals the list of symmetric 1-hop neighbors that the
information signals the list of neighbors the router has selected as sending router has selected as Flooding-MPR, as well as the
flooding MPR, and the willingness of the router to be flooding willingness of the sending router to be elected Flooding-MPR by other
traffic on behalf of other routers. routers.
5.2.3. Neighbor Ordering in HELLO Packets 5.2.3. Neighbor Ordering
Neighbors listed in the HELLO packets sent over MANET interfaces MUST Neighbors listed in the Hello packets sent over OSPFv3 MANET
be listed such that symmetric neighbors are listed before other interfaces MUST be listed such that symmetric 1-hop neighbors are
neighbors. Moreover, neighbors selected as flooding MPR MUST be listed before all other neighbors. Additionally, symmetric 1-hop
listed before other symmetric neighbors. This specific ordering neighbors selected as Flooding-MPRs MUST be listed before all other
corresponds with LLS information (TLV type 3) appended to the HELLO symmetric 1-hop neighbors.
packet, as described in Section 7.
5.2.4. Metric Signalling in HELLO Packets This ordering allows correct interpretation of an included FMPR TLV.
HELLO packets sent over MANET interfaces MUST advertize the costs of 5.2.4. Metric Signalling - METRIC TLV and PMPR TLV
links towards ALL its symmetric MANET neighbors. If the router has
several MANET interfaces, links to ALL the symmetric MANET neigbors
over ALL the MANET interfaces of the router MUST have their costs
listed.
Link costs are signalled along Hello packets by appending LLS blocks Hello packets sent over OSPFv3 MANET interfaces MUST advertise the
at the end of these packets. The costs of the links from the router costs of links towards ALL the symmetric MANET neighbors of the
towards each MANET neighbor on the interface over which is sent the sending router. If the sending router has more than one OSPFv3 MANET
Hello packet MUST be specified using the type 4 TLV described in interfaces, links to ALL the symmetric MANET neighbors over ALL the
Section 7. Moreover, the lowest cost from each MANET neighbor OSPFv3 MANET interfaces of that router MUST have their costs
towards the router (regardless over which interface) MUST be advertised.
specified using the type 5 TLV described in Section 7. Note that the
lowest cost MAY be over a non-MANET interface.
5.2.5. Path MPR Selection The costs of the links between the router and each of this routers
MANET neighbors on the OSPFv3 MANET interface over which the Hello
packet is sent MUST be signaled through including METRIC TLVs.
Using the LLS metric information included in HELLO packets, a MANET Moreover, the lowest cost from each MANET neighbor towards the router
router MUST identify a subset of its links to neighbors that are on (regardless of over which interface) MUST be specified through
shortest paths with respect to the metric in use. This mechanism is including a PMPR TLV. Note that the lowest cost can be over an
called Path MPR selection. Appendix B gives a heuristic for path MPR interface which is not an OSPFv3 MANET interface.
selection.
Hybrid routers MUST select ALL their MANET and hybrid neighbors as 5.2.5. Path-MPR Selection
path MPRs. MANET routers MAY select a subset of MANET neighbors as
path MPR. However a MANET router MUST ensure that for each element
of N or N2 that is not in the path MPR set, there exists a shortest
path that goes from this element to the router through a neighbor
selected as path MPR (unless the shortest path is only one hop, of
course).
5.2.6. Path MPR Selection Signalling in HELLO Packets 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
use from routers in N2 and to this router have as intermediate
routers (if any) only routers which are selected as Path-MPR by this
router. A heuristic for Path-MPR selection is given in Appendix B
A router that has selected path MPRs among its neighbors MUST signal 5.2.6. Path-MPR Selection Signalling - PMPR TLV
this selection through appended LLS information (TLV type 5) at the
end of its HELLO packets as described in Section 7. This information A router MUST signal its Path-MPR set to its neighbors, through
signals the list of neighbors the router has selected as path MPR. including a PMPR TLV in generated Hello packets.
Neighbors listed in the TLV type 5 MUST be listed such that adjacent
neighbors are listed before other neighbors. Moreover, neighbors A PMPR TLV MUST contain a list of IDs of all symmetric 1-hop
selected as path MPR MUST be listed before other adjacent neighbors. neighbors of all OSPFv3 MANET interfaces of the router. These IDs
MUST be included in the PMPR TLV in the order as given below:
1. Neighbors which are both adjacent AND are selected as Path-MPR
for any OSPFv3 MANET interface of the router generating the Hello
packet.
2. Neighbors which are adjacent over any OSPFv3 MANET interface of
the router generating the Hello packet.
3. Symmetric 1-hop neighbors on any OSPFv3 MANET interface of the
router generating the Hello packet, which have not been
previously included in this PMPR TLV.
The list of neighbor IDs is followed by a list of costs for the links
from these neighbors and to the router generating the Hello packet
containing this PMPR TLV, as detailed in Section 5.2.4.
5.2.7. Hello Packet Processing 5.2.7. Hello Packet Processing
In addition to the processing specified by RFC 2740 [2], N and N2 In addition to the processing specified in [RFC2740], N and N2 MUST
MUST be updated when received HELLO packets signal changes in the be updated when received Hello packets indicate changes to the
neighborhood of a MANET interface. The flooding MPR set and the path neighborhood of an OSPFv3 MANET interface. The Flooding-MPR set and
MPR set MUST then be recomputed if N or N2 have changed. the Path-MPR set MUST then be recomputed when either of N or N2 has
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 signalling change 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
When adjacencies are brought up between MANET and hybrid neighbors, Adjacencies are brought up between OSPFv3 MANET interfaces as
procedure goes on as defined in RFC 2740 [2] and RFC 2328 [1]. described in [RFC2740] and [RFC2328]. However, in order to reduce
However, in order to further reduce the control traffic overhead on the control traffic overhead over the OSPFv3 MANET interfaces, a
the wireless medium, MANET routers MAY bring up adjacencies with a router which has one or more such OSPFv3 MANET interface(s) MAY bring
subset of their MANET or hybrid neighbors. up adjacencies with only subset of its MANET neighbors.
Over a MANET interface, a router MUST bring up adjacencies with the Over an OSPFv3 MANET interface, a router MUST bring up adjacencies
neighbors it has included in its MPR set and its MPR Selector set. 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
neighbors, at the expense of additional synchronization overhead.
Some routers (called synch routers) MUST bring up adjacencies with 5.3.1. Packets over 2-Way Links
other MANET neighbors as well. Other routers MAY bring up
adjacencies with MANET neighbors other than MPRs and MPR selectors,
at the expense of more synchronisation overhead. The proposed
heuristic for routers to decide whether they are a synch router is as
follows:
o a MANET router decides it is a synch router if and only if the When a router does not form a full adjacency with a MANET neighbor,
router has a higher ID than any other ID present in Hello packets the state of that neighbor does not progress beyond 2-Way (as defined
or Router-LSAs it has received from other reachable routers in the in [RFC2328]). A router can send protocol packets, such as LSAs, to
area. a MANET neighbor in 2-Way state. Therefore, any packet received from
a symmetric MANET neighbor MUST be processed.
Other algorithms are possible. However, algorithms MUST ensure that As with the OSPF broadcast interface [RFC2328], the next hop in the
if there are no hybrid routers in the MANET, at least one router in forwarding table MAY be a neighbor that is not adjacent. However,
the MANET selects itself as synch router. Moreover, a MANET router when a data packet has travelled beyond its first hop, the MPR
that selects itself as synch router MUST signal this by setting the S selection process guarantees that subsequent hops in the SPT will be
bit in the TLV type 5 appended to the Hello packets it generates, as over adjacencies.
described in Section 7.
5.3.1. Protocol Packets over 2-WAY Links 5.3.2. Adjacency Conservation
When a router does not form a FULL adjacency with a MANET neighbor, Adjacencies are torn down according to [RFC2328]. When the MPR set
the state does not progress beyond 2-WAY (as defined in RFC 2740 [2] or MPR selector set is updated (due to changes in the neighborhood),
and RFC 2328 [1]). A MANET interface MAY send routing protocol and when a neighbor was formerly, but is no longer, in the MPR set or
packets while in 2-WAY state. the MPR selector set, then the adjacency with that neighbor is kept,
unless the change causes the neighbor to cease being a symmetric
1-hop neighbor.
Therefore, any routing protocol packet received from a symmetric When a router receives Hello packets from a symmetric 1-hop neighbor
MANET neighbor MUST be processed. Similar to the OSPF broadcast which ceases to list this router as being adjacent (see
interface [1], the next hop in the forwarding table MAY be a neighbor Section 5.2.3), the state of that neighbor MUST be changed to (i)
that is not adjacent. However, when a data packet has travelled 2-Way if the neighbor is not in the MPR set or the MPR selector set,
beyond its first hop, the MPR selection process guarantees that or (ii) ExStart if the neighbor is in the MPR set or the MPR selector
subsequent hops in the SPT will be over adjacencies. set, or if the neighbor or the router itself is a synch router.
5.3.2. Adjacency Conservation 5.4. Link State Advertisements
Adjacencies are torn down as defined in RFC 2740 [2] and RFC 2328 Routers generate Router-LSAs periodically, using the format specified
[1]. This means that when the MPR set or MPR selector set is updated in [RFC2740] and [RFC2328].
(due to changes in the neighborhood), and when a neighbor was
formerly, but is no longer, in the MPR set or the MPR selector set,
the adjacency with this neighbor is kept, unless it is no longer a
symmetric neighbor.
When a router receives Hello packets from a symmetric neighbor which Routers which have one or more OSPFv3 MANET interface(s) MUST include
cease to list the router as being adjacent (see Section 5.2.3), the the following links in the Router-LSAs that they generate:
state of this neighbor MUST be changed to (i) 2-WAY if the neighbor
is not in the MPR set or the MPR selector set, or (ii) ExStart if the
neighbor is in the MPR set or the MPR selector set, or if the
neighbor or the router itself is a synch router.
5.4. Link State Advertisements o links to all neighbors that are in the Path-MPR set; AND
The Router-LSAs originated by a hybrid router list adjacencies over o links to all neighbors that are in the Path-MPR Selector set.
interfaces other than MANET as specifed in RFC 2740 [2] and RFC 2328
[1]. Hybrid and MANET routers MUST list in the Router-LSAs they
originate the links to the neighbors that are in their Path MPR set
and their Path MPR Selector set. MANET routers MAY list other links
they have through MANET interfaces, to the expense of more overhead.
Hybrid and MANET routers MUST flood updated Router-LSAs when a new Routers which have one or more OSPFv3 MANET interface(s) MAY list
adjacency has been brought up reflecting change in the MPR set (or other links they have through those OSPFv3 MANET interfaces, at the
the MPR Selector set), and when a neighbor formerly listed in expense of more overhead.
originated LSAs is no longer adjacent.
In addition, routers which have one or more OSPFv3 MANET interface(s)
MUST generate updated Router-LSAs when either of the following
occurs:
o a new adjacency has been brought up, reflecting a change in the
MPR set;
o a new adjacency has been brought up, reflecting a change in the
MPR Selector set;
o a formerly adjacent and advertised neighbor ceases to be adjacent.
5.4.1. LSA Flooding 5.4.1. LSA Flooding
LSUpdates received on an interface of a type other than MANET are Link State Updates received on an interface of a type other than
processed and flooded as specified in [1] and [2], over every OSPFv3 MANET interfaces are processed and flooded according to
interface. If an LSUpdate was received on a MANET interface, it is [RFC2328] and [RFC2740], over every interface. If a Link State
processed as follows, with regards to flooded LSAs. Update was received on an OSPFv3 MANET interface, it is processed as
follows:
1. Consistency checks are made on the received packet, as specified 1. Consistency checks are performed on the received packet according
in [1] and [2], before being handed to the procedure described in to [RFC2328] and [RFC2740], and the Link State Update packet is
the following steps, and the Link State Update packet is thus thus associated with a particular neighbor and a particular area.
associated with a particular neighbor and a particular area.
2. If the LSU was received from a router other than a symmetric 2. If the Link State Update was received from a router other than a
neighbor, the LSUpdate MUST be discarded without further symmetric 1-hop neighbor, the Link State Update MUST be discarded
processing. Otherwise, for each LSA contained in LSUpdates without further processing.
received on MANET interfaces, the following steps replace steps 1
to 5 of section 13.3 of [1].
1. If there exists an LSA in the Link State Database, with the 3. Otherwise, for each LSA contained in Link State Updates received
same Link State ID, LS Type and Advertizing Router values as over an OSPFv3 MANET interfaces, the following steps replace
the received LSA, and the received LSA is not newer (see steps 1 to 5 of section 13.3 of [RFC2328].
section 13.1 of [1]) then the received LSA MUST not be
processed EXCEPT for acknowledgement as described in section 1. If an LSA exists in the Link State Database, with the same
5.4. Link State ID, LS Type and Advertising Router values as the
received LSA, and if the received LSA is not newer (see
section 13.1 of [RFC2328]), then the received LSA MUST NOT be
processed EXCEPT for acknowledgment as described in
Section 5.4.2.
2. Otherwise, the LSA MUST be attributed a scope according to 2. Otherwise, the LSA MUST be attributed a scope according to
its type, as specified in section 3.5 of [2]. its type, as specified in section 3.5 of [RFC2740].
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 interfaces of the router in that area flooded on all the OSPFv3 interfaces of the router in that
according to the default flooding algorithm described below. area according to the default flooding algorithm described
below.
- Otherwise, the LSA MUST be flooded on all the interfaces of + Otherwise, the LSA MUST be flooded on all the OSPFv3
the router according to the default flooding algorithm interfaces of the router according to the default flooding
described below. algorithm described in Section 5.4.1.1.
The default flooding algorithm is then the following: 5.4.1.1. Default LSA Flooding Algorithm
The default LSA flooding algorithm is as follows:
1. The LSA MUST be installed in the Link State Database. 1. The LSA MUST be installed in the Link State Database.
2. The Age of the LSA is increased by InfTransDelay. 2. The Age of the LSA MUST be increased by InfTransDelay.
3. The LSA is flooded over all interfaces of type other than MANET. 3. The LSA MUST be retransmitted over all OSPFv3 interfaces of types
other than OSPFv3 MANET Interface.
4. If the sender interface address is an interface address of an 4. If the sending OSPFv3 interface is a Flooding-MPR selector of
flooding MPR selector of this router, the LSA MUST also be this router, then the LSA MUST also be retransmitted over all
retransmitted out all MANET interfaces concerned by the scope, OSPFv3 MANET interfaces concerned by the scope, with the
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 MANET dynamic topologies: LSA updating may need to be more to dynamic topologies: LSA updating may need to be more frequent in
frequent in MANET parts of the OSPF network than in traditional parts MANET parts of an OSPF network than in other parts of an OSPF
of the OSPF network. network.
5.4.2. Link State Acknowlements 5.4.2. Link State Acknowledgments
When a router receives an LSA over an OSPFv3 MANET interface, the
router MUST proceed to acknowledge the LSA as follows:
When a router receives an LSA on a MANET interface, the router MUST
proceed to acknowledge the LSA as follows
1. If the LSA was not received from an adjacent neighbor, the router 1. If the LSA was not received from an adjacent neighbor, the router
MUST NOT acknowledge it. MUST NOT acknowledge it.
2. Otherwise, if the LSA was received from an adjacent neighbor if 2. Otherwise, if the LSA was received from an adjacent neighbor and
the LSA is already in the database (i.e. the LSA has already been if the LSA is already in the Link State Database (i.e. the LSA
received and processed) the router MUST send an acknowledgement has already been received and processed), then the router MUST
for this LSA on all MANET interfaces, to the multicast address send an acknowledgment for this LSA on all OSPFv3 MANET
all_SPF_Routers. interfaces, to the multicast address all_SPF_Routers.
3. Otherwise, if the LSA is not already in the 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
acknowledgement. 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
acknowledgement for this LSA on all MANET interfaces, to the acknowledgment for this LSA on all OSPFv3 MANET interfaces,
multicast address all_SPF_Routers. to the multicast address all_SPF_Routers.
If a router sends an LSA on a MANET interface, it expects If a router sends an LSA on an OSPFv3 MANET interface, it expects
acknowledgements (explicit or implicit) from each adjacent neighbors. acknowledgments (explicit or implicit) from all adjacent neighbors.
In the case where the router did not originate the LSA (i.e. relays In the case where the router did not generate, but simply relays, the
the LSA), the router MUST only expect acknowledgements (explicit or LSA, then the router MUST expect acknowledgments (explicit or
implicit) 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, the router retransmits the neighbor has not acknowledged the LSA, then that router MUST
LSA. retransmit the LSA.
If, due to efficient flooding procedure decision, a router decides to If, due to the MPR flooding reduction mechanism employed for LSA
not relay an LSA, the router MUST still expect acknowledgements of Flooding as described in Section 5.4.1, a router decides to not relay
that LSA (explicit or implicit) from adjacent neighbors that have not an LSA, the router MUST still expect acknowledgments of this LSA
(explicit or implicit) from adjacent neighbors that have not
previously acknowledged this LSA. If a router detects that some previously acknowledged this LSA. If a router detects that some
adjacent neighbor has not acklnowledged the LSA, the router adjacent neighbor has not acknowledged the LSA, then the router MUST
retransmits the LSA. retransmit the LSA.
Note that it may be beneficial to aggregate several acknowledgements Note that it may be beneficial to aggregate several acknowledgments
in the same transmission, taking advantage of multicasting. A timer in the same transmission, taking advantage of native multicasting (if
wait MAY thus be used before any acknowledgement transmission in available). A timer wait MAY thus be used before any acknowledgment
order to avoid multiple OSPF acknowledgement transmissions. transmission.
Additional jitter delay in packet (re)transmission may be used in Additionally, jitter [RFC5148] on packet (re)transmission MAY be used
order to increase the opportunities to bundle several packets in order to increase the opportunities to bundle several packets
together per transmission (which provides a reduction in the number together in each transmission.
of overall transmissions, and therefore the number of collisions over
the wireless media).
6. Security Considerations 5.5. Hybrid Routers
This document does currently not specify security considerations. In addition to the operations described in Section 5.2, Section 5.3
and Section 5.4, hybrid routers MUST:
7. IANA Considerations o select ALL their MANET and hybrid neighbors as Path-MPRs.
This document defines the new TLV types below, to be allocated by o list adjacencies over OSPFv3 interfaces of types other than OSPFv3
IANA. MANET interface, as specified in [RFC2740] and [RFC2328], in
generated Router-LSAs.
OSPF packets sent by MANET and hybrid routers are formated as defined 5.6. Synch Routers
by RFC2740 [2] and RFC2328 [1]. The LLS extension [4] is used in
HELLO packets sent over MANET interfaces, as follows.
The Hello packets sent over an OSPF MANET interface have the L bit In a network with no hybrid routers, at least one Synch router MUST
set. An LLS datablock containing flooding MPR selection information be selected. A Synch router MUST:
is appended to these Hello messages. The TLV of Type 3 is defined as
the flooding MPR selection TLV type shown in Fig. 1. o set the S bit in the PMPR TLV appended to the Hello packets it
generates; AND
o bring up adjacencies with ALL MANET neighbors
A proposed heuristics for selection of Sync routers is as follows:
o A router which has a MANET interface and an ID that is higher than
the ID of all of its current neighbors, and whose ID is higher
than any other ID present in Router-LSAs currently in its link
state Link State Database selects itself as synch router.
Other heuristics are possible, however any heuristic for selecting
Synch routers MUST ensure the presence of at least one sync or hybrid
router in the network.
5.7. Routing Table Computation
When routing table (re)computation occurs, in addition to the
processing of the Link State Database defined in [RFC2740] and
[RFC2328], routers which have one or more MANET interfaces MAY
include links between themselves and MANET neighbors that are in
state 2-Way or higher (as data and protocol packets may be sent,
received and processed over these links too).
6. Packet Formats
OSPFv3 packets are as defined by [RFC2740] and [RFC2328]. Additional
LLS signaling [RFC4813] is used in HELLO packets sent over OSPFv3
MANET interfaces, as detailed in this section.
This specification uses network byte order (most significant octet
first) for all fields.
6.1. Flooding-MPR Selection TLV
A TLV of Type FMPR is defined for signaling Flooding-MPR selection,
shown in Figure 1.
0 1 2 3 0 1 2 3
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=3 | Length | | Type=FMPR | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Willingness | # Sym. Neigh. | # MPR | Reserved | | Willingness | # Sym. Neigh. | # MPR | Reserved |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Fig. 1 : Flooding MPR advertisement (TLV type 3) Figure 1: Flooding-MPR Advertisement TLV (FMPR)
Willingness
This field specifies the willingness of the router to flood link
state information on behalf of other routers. It can be set to
any integer value from 1 to 6. By default, a router SHOULD
advertise a willingness of WILL_DEFAULT = 3.
# Sym. Neigh. where:
Number of symmetric neighbors, listed first among the neighbors in Willingness - is an 8 bit unsigned integer field which specifies the
a HELLO packet. willingness of the router to flood link state information on
behalf of other routers. It can be set to any integer value from
1 to 6. By default, a router SHOULD advertise a willingness of
WILL_DEFAULT = 3.
# MPR # Sym. Neigh. - is an 8 bit unsigned integer field which specifies
the number of symmetric 1-hop neighbors, listed first among the
neighbors in a HELLO packet.
Number of neighbors, listed first among the symmetric neighbors on # MPR - is an 8 bit unsigned integer field which specifies the
this interface in a HELLO packet, that are selected by the router number of neighbors selected as MPR. These MPRs are listed first
as flooding MPR. among the symmetric 1-hop neighbors on this OSPFv3 MANET interface
in a HELLO packet.
Reserved Reserved - is an 8 bit field which SHOULD be cleared ('0') on
transmission and SHOULD be ignored on reception.
This 8 bits long field is set to 0 by the sender and ignored by 6.2. Metric Information TLV
the receiver.
An LLS datablock containing metric information is also appended to A TLV of Type METRIC is defined for advertising costs of links to
Hello messages over MANET interfaces. The TLV of Type 4 is defined neighbors, shown in Figure 2.
as the metric TLV type shown in Fig. 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=4 | Length | | Type=METRIC | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved |R| Cost 1 | | Reserved |U|R| Cost 0 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Cost 2 | Cost 3 | | Cost 1 | Cost 2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: : : :
: :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Cost n | Padding |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Fig. 2 : metric advertisement (TLV type 4) Figure 2: Metric Advertisement TLV (METRIC).
Reserved where:
This 15 bits long field is set to 0 by the sender and ignored by Reserved - is a 14 bit field which SHOULD be cleared ('0') on
the receiver. transmission and SHOULD be ignored on reception.
R bit R - is a binary flag, cleared ('0') if the costs advertised in the
TLV are direct (i.e. the costs of the links from the router to the
neighbors), set ('1') if the costs advertised are reverse (i.e.
the costs of the links from the neighbors to the router).
This bit is set to 0 if the costs advertized in the TLV are direct U - is a binary flag, cleared ('0') if each the cost for each link
costs (i.e. the costs of the links from the router to the from the sending router and to each advertised neighbor is
neighbors). If this bit is set to 1, the costs advertized in the explicitly included (shown in Figure 3), set ('1') if a single
TLV are reverse costs (i.e. the costs of the links from the metric value is included which applies to all links (shown in
neighbors to the router). Figure 4).
Cost n Cost n - is an 8 bit unsigned integer field which specifics the cost
of the link, in the direction as specified by the R flag, between
this router and the neighbor listed at the n-th position in the
Hello packet, when counting from the beginning of the Hello packet
and with the first neighbor being at position 0.
The cost of the link towards the neighbor listed in n-th position Padding - is a 16 bit field which SHOULD be cleared ('0') on
in the Hello packet. transmission and SHOULD be ignored on reception. Padding is
included in order that the TLV is 32bit aligned. Padding MUST be
included when the TLV contains an even number of Cost fields, and
MUST NOT be included otherwise.
In addition to metric and flooding MPR TLVs, HELLO packets contain an 0 1 2 3
appended path MPR selection TLV defined as the TLV type 5 shown below 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
in Fig. 3. +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type=METRIC | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved |0|R| Cost 0 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Cost 1 | Cost 2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3: Metric Advertisement TLV (METRIC) example with explicit
individual link costs (U=0) and an odd number of Costs (and, hence,
no padding).
0 1 2 3 0 1 2 3
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=METRIC | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| # Adj. Neigh | # Path MPR | Reserved |S| | Reserved |1|R| Cost |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 4: Metric Advertisement TLV (METRIC) example with a single
and uniform link cost (U=1) (and, hence, no padding).
6.3. Path-MPR Selection TLV
A TLV of Type FMPR is defined for signaling Path-MPR selection, shown
in Figure 1, as well as the link cost associated with these Path-
MPRs.
0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type=PMPR | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| # Adj. Neigh | # Path-MPR | Reserved |U|S|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor ID | | Neighbor ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor ID | | Neighbor ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: : : :
: : : :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Cost 1 | Cost 2 | | Cost 0 | Cost 1 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: : : :
: :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Cost n | Padding |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Fig. 3 : path MPR advertisement (TLV type 5) Figure 5: Path-MPR Advertisement TLV (PMPR)
# Adj. Neigh # Adj. Neigh. - is an 8 bit unsigned integer field which specifies
the number of neighbors, starting from the first Neighbor ID in
the TLV, that are adjacent MANET neighbors.
Number of neighbors, listed first in the TLV, that are adjacent # Path-MPR - is an 8 bit unsigned integer field which specifies the
MANET neighbors. number of MANET neighbors, starting from the first Neighbor ID,
that are selected as Path-MPRs.
# Path MPR Reserved - is an 14 bit field which SHOULD be cleared ('0') on
transmission and SHOULD be ignored on reception.
Number of blocks neighbors listed first among the adjacent MANET S - is a binary flag, cleared ('0') if the router brings up
neighbors, that are selected as path MPRs by the router. adjacencies only with neighbors in its MPR set and MPR selector
set as per Section 5.3, set ('1') if the router brings up
adjacencies with all neighbors as a Synch router -- as per
Section 5.6.
Reserved U - is a binary flag, cleared ('0') if the cost for each link from
each advertised neighbor in the PMPR TLV and to the sending router
is explicitly included (as shown in Figure 6), set ('1') if a
single metric value is included which applies to all links (as
shown in Figure 7).
This field is 15 bits long and must be set to 0 to be in Neighbor ID - is a 32 bit field which specifies the router ID of a
compliance with this specification. MANET neighbor.
S bit Cost n - is a 16 bit unsigned integer field which specifies the cost
of the link in the direction FROM the nth listed advertised
neighbor in the PMPR and towards this router. A default value of
0xFFFF (i.e. infinity) MUST be advertised, unless information
received via HELLO packets from the neighbor specifies otherwise,
in which case the received information MUST be advertised. If a
neighbor is reachable via more than one interface, the cost
advertised MUST be the minimum of the costs by which that neighbor
can be reached.
This bit is set to 1 if the router decides it is a synch router. Padding - is a 16 bit field which SHOULD be cleared ('0') on
Otherwise it is set to 0. transmission and SHOULD be ignored on reception. Padding is
included in order that the TLV is 32bit aligned. Padding MUST be
included when the TLV contains an odd number of Cost fields, and
MUST NOT be included otherwise.
Neighbor ID 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type=PMPR | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| # Adj. Neigh | # Path-MPR | Reserved |0|S|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: :
: :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Cost 1 | Cost 2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
: ....... :
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Cost n-1 | Cost n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This field specifies the router ID of a MANET neighbor. Figure 6: Path-MPR Advertisement TLV (PMPR) with explicit individual
link costs (U=0) and an even number of Cost fields (hence, no
padding).
Cost n 0 1 2 3
0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Type=5 | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| # Adj. Neigh | # Path-MPR | Reserved |1|S|
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Neighbor ID |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Cost | Padding |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
This field specifies the cost of the link going from the neighbor Figure 7: Path-MPR Advertisement TLV (PMPR) with a single and uniform
with ID listed in n-th position in this TLV, towards the router. link cost (U=1) (hence, padding included).
By default it is set to 0xFFFF (maximal value, i.e. infinity),
unless information received via HELLO packets from the neighbor
specifies otherwise. If a neighbor is reachable through several
interfaces at the same time, the advertized cost is set to the
minimum of the costs over these different interfaces.
8. References 7. Security Considerations
8.1. Normative References This document does currently not specify security considerations.
[1] Moy, J., "OSPF version 2", RFC 2328, 1998. 8. IANA Considerations
[2] Moy, J., Coltun, R., and D. Ferguson, "OSPF for IPv6", This document defines three LLS TLVs, allocation of type values for
RFC 2740, 1999. which are requested from the LLS TLV type registry defined [RFC4813].
[3] Bradner, S., "Key words for use in RFCs to Indicate Requirement +----------+------------+--------------+
Levels", RFC 2119, 1997. | Mnemonic | Type Value | Name |
+----------+------------+--------------+
| FMPR | tbd | Flooding-MPR |
| METRIC | tbd | Metric |
| MMPR | tbd | Path-MPR |
+----------+------------+--------------+
[4] Zinin, A., Friedman, B., Roy, A., Nguyen, L., and D. Yeung, Table 1: LLS TLV Type Assignments
"OSPF Link Local Signaling", draft-nguyen-ospf-lls-04 (work in
progress), 2004.
8.2. Informative References 9. References
[5] Clausen, T. and P. Jacquet, "The Optimized Link State Routing 9.1. Normative References
Protocol", RFC 3626, October 2003.
[6] Macker, J. and S. Corson, "MANET Routing Protocol Performance [RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Issues and Evaluation Considerations", RFC 2501, January 1999. Requirement Levels", RFC 2119, BCP 14, March 1997.
[7] OLSRv2, Design Team., "OLSR version 2", [RFC2328] Moy, J., "OSPF version 2", RFC 2328, 1998.
draft-ietf-manet-olsrv2-02 (work in progress), June 2006.
[8] Ngyuen, D. and P. Minet, "Analysis of MPR Selection in the OLSR [RFC2740] Moy, J., Coltun, R., and D. Ferguson, "OSPF for
Protocol", 2nd Int. Workshop on Performance Analysis and IPv6", RFC 2740, 1999.
Enhancement of Wireless Networks , 2007.
[9] Macker, J., Chakeres, I., and T. Clausen, "Mobile Ad hoc [RFC4813] Zinin, A., Friedman, B., Roy, A., Nguyen, L., and
Network Architecture", ID draft-ietf-autoconf-manetarch, D. Yeung, "OSPF Link Local Signaling", RFC 4813,
February 2007. 2007.
[10] Adamson, B., Dearlove, C., and T. Clausen, "Jitter 9.2. Informative References
Considerations in MANETs", ID draft-ietf-manet-jitter,
June 2007. [RFC2501] Macker, J. and S. Corson, "MANET Routing Protocol
Performance Issues and Evaluation Considerations",
RFC 2501, January 1999.
[RFC3626] Clausen, T. and P. Jacquet, "The Optimized Link
State Routing Protocol", RFC 3626, October 2003.
[RFC5148] Adamson, B., Dearlove, C., and T. Clausen, "Jitter
Considerations in MANETs", RFC 5148, 2008.
[MPR] Qayyum, A., Viennot, L., and A. Laouiti,,
"Multipoint Relaying for Flooding Broadcast
Messages in Mobile Wireless Networks", Proceedings
of HICSS , 2002.
[MPR-robustness] Adjih, C., Baccelli, E., Clausen,, T., and P.
Jacquet,, "On the Robustness and Stability of
Connected Dominated Sets", INRIA Research
Report RR-5609, 2005.
[MPR-analysis] Ngyuen, D. and P. Minet, "Analysis of MPR Selection
in the OLSR Protocol", 2nd Int. Workshop on
Performance Analysis and Enhancement of Wireless
Networks , 2007.
[MPR-topology] Baccelli, E., Clausen,, T., and P. Jacquet,,
"Partial Topology in an MPR-based Solution for
Wireless OSPF on Mobile Ad Hoc Networks", INRIA
Research Report RR-5619, 2005.
Appendix A. Flooding MPR Selection Heuristic 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
skipping to change at page 25, line 33 skipping to change at page 26, line 27
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 neighbor. The reverse cost for this link, cost(B,A), a symmetric 1-hop neighbor. The reverse cost for this link,
is set at the value received in Hello packets from router B. If cost(B,A), is set at the value received in Hello packets from
router B is reachable through several interfaces at the same router B. If router B is reachable through several interfaces at
time, cost(B,A) is set as the minimum cost advertized by router B the same time, cost(B,A) is set as the minimum cost advertized by
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 advertized 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
skipping to change at page 27, line 5 skipping to change at page 27, line 25
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, a MANET router MUST ensure that for each
element of N or N2 that is not in the path MPR set, there exists a element of N or N2 that is not in the path MPR set, there exists a
shortest path that goes from this element to the router through a shortest path that goes from this element to the router through a
neighbor selected as path MPR (unless the shortest path is only one neighbor selected as path MPR (unless the shortest path is only one
hop). hop).
Contributors Appendix C. Contributors
The authors thank Cedric Adjih, Acee Lindem, Padma Pillay-Esnault and The authors would like to thank Cedric Adjih, Acee Lindem, Padma
Laurent Viennot for their contributions to this document. Pillay-Esnault and Laurent Viennot for their contributions to this
document.
Appendix D. Acknowledgments
The authors would like to thank Juan Antonio Cordero Fuertes for his
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/
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 INRIA
Phone: +33 1 3963 5511 Phone: +33 1 3963 5511
Email: Dang-Quan.Nguyen@inria.fr EMail: Dang-Quan.Nguyen@inria.fr
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.lix.polytechnique.fr/Labo/Thomas.Clausen/ URI: http://www.thomasclausen.org/
Full Copyright Statement Full Copyright Statement
Copyright (C) The IETF Trust (2008). Copyright (C) The IETF Trust (2008).
This document is subject to the rights, licenses and restrictions This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors contained in BCP 78, and except as set forth therein, the authors
retain all their rights. retain all their rights.
This document and the information contained herein are provided on an This document and the information contained herein are provided on an
skipping to change at page 29, line 44 skipping to change at line 1302
attempt made to obtain a general license or permission for the use of attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr. http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at this standard. Please address the information to the IETF at
ietf-ipr@ietf.org. ietf-ipr@ietf.org.
Acknowledgment
Funding for the RFC Editor function is provided by the IETF
Administrative Support Activity (IASA).
 End of changes. 184 change blocks. 
539 lines changed or deleted 835 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/