draft-ietf-ospf-manet-mpr-03.txt   draft-ietf-ospf-manet-mpr-04.txt 
Open Shortest Path (OSPF) E. Baccelli Open Shortest Path (OSPF) E. Baccelli
Internet-Draft P. Jacquet Internet-Draft P. Jacquet
Intended status: Experimental INRIA Intended status: Experimental INRIA
Expires: May 22, 2009 D. Nguyen Expires: July 21, 2009 D. Nguyen
CRC CRC
T. Clausen T. Clausen
LIX, Ecole Polytechnique, France LIX, Ecole Polytechnique, France
November 18, 2008 January 17, 2009
OSPF MPR Extension for Ad Hoc Networks OSPF MPR Extension for Ad Hoc Networks
draft-ietf-ospf-manet-mpr-03 draft-ietf-ospf-manet-mpr-04
Status of This Memo Status of This Memo
By submitting this Internet-Draft, each author represents that any This Internet-Draft is submitted to IETF in full conformance with the
applicable patent or other IPR claims of which he or she is aware provisions of BCP 78 and BCP 79.
have been or will be disclosed, and any of which he or she becomes
aware will be disclosed, in accordance with Section 6 of BCP 79.
Internet-Drafts are working documents of the Internet Engineering 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.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
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 May 22, 2009. This Internet-Draft will expire on July 21, 2009.
Copyright Notice
Copyright (c) 2009 IETF Trust and the persons identified as the
document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect
to this document.
Abstract 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 . . . . . . . . . . . . . . . . . . . . . . . . . 4
2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 3 2. Terminology . . . . . . . . . . . . . . . . . . . . . . . . . 4
3. Applicability Statement . . . . . . . . . . . . . . . . . . . 5 3. Applicability Statement . . . . . . . . . . . . . . . . . . . 6
3.1. MANET Characteristics . . . . . . . . . . . . . . . . . . 5 3.1. MANET Characteristics . . . . . . . . . . . . . . . . . . 6
3.2. OSPFv3 MANET Interface Characteristics . . . . . . . . . . 5 3.2. OSPFv3 MANET Interface Characteristics . . . . . . . . . . 6
4. Protocol Overview and Functioning . . . . . . . . . . . . . . 6 4. Protocol Overview and Functioning . . . . . . . . . . . . . . 7
4.1. Efficient Flooding using MPRs . . . . . . . . . . . . . . 6 4.1. Efficient Flooding using MPRs . . . . . . . . . . . . . . 7
4.2. MPR Topology Reduction . . . . . . . . . . . . . . . . . . 6 4.2. MPR Topology Reduction . . . . . . . . . . . . . . . . . . 7
4.3. Multicast Transmissions of Protocol Packets . . . . . . . 6 4.3. Multicast Transmissions of Protocol Packets . . . . . . . 7
4.4. MPR Adjacency Reduction . . . . . . . . . . . . . . . . . 7 4.4. MPR Adjacency Reduction . . . . . . . . . . . . . . . . . 8
5. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 7 5. Protocol Details . . . . . . . . . . . . . . . . . . . . . . . 8
5.1. Data Structures . . . . . . . . . . . . . . . . . . . . . 7 5.1. Data Structures . . . . . . . . . . . . . . . . . . . . . 8
5.1.1. N: Symmetric 1-hop Neighbor Set . . . . . . . . . . . 7 5.1.1. N(i): Symmetric 1-hop Neighbor Set . . . . . . . . . . 8
5.1.2. N2: Symmetric strict 2-hop Neighbor Set . . . . . . . 8 5.1.2. N2(i): Symmetric strict 2-hop Neighbor Set . . . . . . 9
5.1.3. Flooding-MPR set . . . . . . . . . . . . . . . . . . . 8 5.1.3. Flooding-MPR set . . . . . . . . . . . . . . . . . . . 9
5.1.4. Flooding-MPR-selector set . . . . . . . . . . . . . . 9 5.1.4. Flooding-MPR-selector set . . . . . . . . . . . . . . 10
5.1.5. Path-MPR set . . . . . . . . . . . . . . . . . . . . . 9 5.1.5. Path-MPR set . . . . . . . . . . . . . . . . . . . . . 10
5.1.6. Path-MPR-selector set . . . . . . . . . . . . . . . . 9 5.1.6. Path-MPR-selector set . . . . . . . . . . . . . . . . 11
5.1.7. MPR set . . . . . . . . . . . . . . . . . . . . . . . 10 5.1.7. MPR set . . . . . . . . . . . . . . . . . . . . . . . 11
5.1.8. MPR-selector set . . . . . . . . . . . . . . . . . . . 10 5.1.8. MPR-selector set . . . . . . . . . . . . . . . . . . . 11
5.2. Hello Protocol . . . . . . . . . . . . . . . . . . . . . . 10 5.2. Hello Protocol . . . . . . . . . . . . . . . . . . . . . . 11
5.2.1. Flooding-MPR Selection . . . . . . . . . . . . . . . . 11 5.2.1. Flooding-MPR Selection . . . . . . . . . . . . . . . . 12
5.2.2. Flooding-MPR Selection Signaling - FMPR TLV . . . . . 11 5.2.2. Flooding-MPR Selection Signaling - FMPR TLV . . . . . 12
5.2.3. Neighbor Ordering . . . . . . . . . . . . . . . . . . 11 5.2.3. Neighbor Ordering . . . . . . . . . . . . . . . . . . 12
5.2.4. Metric Signaling - METRIC TLV and PMPR TLV . . . . . . 12 5.2.4. Metric Signaling - METRIC-MPR TLV and PMPR TLV . . . . 13
5.2.5. Path-MPR Selection . . . . . . . . . . . . . . . . . . 12 5.2.5. Path-MPR Selection . . . . . . . . . . . . . . . . . . 13
5.2.6. Path-MPR Selection Signaling - PMPR TLV . . . . . . . 12 5.2.6. Path-MPR Selection Signaling - PMPR TLV . . . . . . . 13
5.2.7. Hello Packet Processing . . . . . . . . . . . . . . . 13 5.2.7. Hello Packet Processing . . . . . . . . . . . . . . . 14
5.3. Adjacencies . . . . . . . . . . . . . . . . . . . . . . . 13 5.3. Adjacencies . . . . . . . . . . . . . . . . . . . . . . . 14
5.3.1. Packets over 2-Way Links . . . . . . . . . . . . . . . 14 5.3.1. Packets over 2-Way Links . . . . . . . . . . . . . . . 15
5.3.2. Adjacency Conservation . . . . . . . . . . . . . . . . 14 5.3.2. Adjacency Conservation . . . . . . . . . . . . . . . . 15
5.4. Link State Advertisements . . . . . . . . . . . . . . . . 14 5.4. Link State Advertisements . . . . . . . . . . . . . . . . 15
5.4.1. LSA Flooding . . . . . . . . . . . . . . . . . . . . . 15 5.4.1. LSA Flooding . . . . . . . . . . . . . . . . . . . . . 16
5.4.2. Link State Acknowledgments . . . . . . . . . . . . . . 16 5.4.2. Link State Acknowledgments . . . . . . . . . . . . . . 17
5.5. Hybrid Routers . . . . . . . . . . . . . . . . . . . . . . 17 5.5. Hybrid Routers . . . . . . . . . . . . . . . . . . . . . . 18
5.6. Synch Routers . . . . . . . . . . . . . . . . . . . . . . 18 5.6. Synch Routers . . . . . . . . . . . . . . . . . . . . . . 19
5.7. Routing Table Computation . . . . . . . . . . . . . . . . 18 5.7. Routing Table Computation . . . . . . . . . . . . . . . . 19
6. Packet Formats . . . . . . . . . . . . . . . . . . . . . . . . 18 6. Packet Formats . . . . . . . . . . . . . . . . . . . . . . . . 19
6.1. Flooding-MPR TLV . . . . . . . . . . . . . . . . . . . . 18 6.1. Flooding-MPR TLV . . . . . . . . . . . . . . . . . . . . 20
6.2. Metric TLV . . . . . . . . . . . . . . . . . . . . . . . 19 6.2. Metric-MPR TLV . . . . . . . . . . . . . . . . . . . . . . 20
6.3. Path-MPR TLV . . . . . . . . . . . . . . . . . . . . . . 21 6.3. Path-MPR TLV . . . . . . . . . . . . . . . . . . . . . . 22
7. Security Considerations . . . . . . . . . . . . . . . . . . . 24 7. Security Considerations . . . . . . . . . . . . . . . . . . . 25
8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 25 8. IANA Considerations . . . . . . . . . . . . . . . . . . . . . 26
9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 26 9. References . . . . . . . . . . . . . . . . . . . . . . . . . . 27
9.1. Normative References . . . . . . . . . . . . . . . . . . . 26 9.1. Normative References . . . . . . . . . . . . . . . . . . . 27
9.2. Informative References . . . . . . . . . . . . . . . . . . 26 9.2. Informative References . . . . . . . . . . . . . . . . . . 27
Appendix A. Flooding-MPR Selection Heuristic . . . . . . . . . . 27 Appendix A. Flooding-MPR Selection Heuristic . . . . . . . . . . 28
Appendix B. Path-MPR Selection Heuristic . . . . . . . . . . . . 28 Appendix B. Path-MPR Selection Heuristic . . . . . . . . . . . . 29
Appendix C. Contributors . . . . . . . . . . . . . . . . . . . . 29 Appendix C. Contributors . . . . . . . . . . . . . . . . . . . . 30
Appendix D. Acknowledgments . . . . . . . . . . . . . . . . . . . 30 Appendix D. Acknowledgments . . . . . . . . . . . . . . . . . . . 30
1. Introduction 1. Introduction
This document specifies an extension of OSPFv3 [RFC5340] 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.
skipping to change at page 5, line 20 skipping to change at page 6, line 20
properties. 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, i.e. that
R that makes a transmission within a MANET can only assume that a router R that makes a transmission within a MANET can only assume
transmission to be received by a subset of the total number of 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 routers within that MANET. Further, if two routers, R1 and R2, each
transmission, each of these transmissions is not guaranteed to be make a transmission, each of these transmissions is not guaranteed to
received by the same subset of routers within the MANET - and this 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 even if each of R1 and R2 can mutually receive transmissions from
each 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
skipping to change at page 7, line 36 skipping to change at page 8, line 36
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 [RFC5340], 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 [RFC5340], 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(i): Symmetric 1-hop Neighbor Set
The Symmetric 1-hop Neighbor set records router IDs of the set of The Symmetric 1-hop Neighbor set N(i) records router IDs of the set
symmetric 1-hop neighbors of the router. There is one Symmetric of symmetric 1-hop neighbors of the router on interface i. More
1-hop Neighbor set per MANET interface. More precisely, N records precisely, N(i) 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 over the interface i.
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 For convenience throughout this document, N will denote the union of
all N(i) sets, for all MANET interfaces on the router.
The Symmetric strict 2-hop Neighbor set records links between routers 5.1.2. N2(i): Symmetric strict 2-hop Neighbor Set
in N and their symmetric 1-hop neighbors, excluding:
The Symmetric strict 2-hop Neighbor set N2(i) records links between
routers in N(i) and their symmetric 1-hop neighbors, excluding:
(i) the router performing the computation, (i) the router performing the computation,
(ii) all routers in N. (ii) all routers in N(i).
There is one Symmetric strict 2-hop Neighbor set per MANET interface. More precisely, N2(i) 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.
For convenience throughout this document, N2 will denote the union of
all N2(i) sets, for all MANET interfaces on the router.
5.1.3. Flooding-MPR set 5.1.3. Flooding-MPR set
The Flooding-MPR set records router IDs of a subset of the routers The Flooding-MPR set on interface i records router IDs of a subset of
listed in N, selected such that through this subset, each router the routers listed in N(i), selected such that through this subset,
listed in N2 is reachable in 2 hops by this router. There is one each router listed in N2(i) is reachable in 2 hops by this router.
Flooding-MPR set per MANET interface. More precisely, the Flooding- There is one Flooding-MPR set per MANET interface. More precisely,
MPR set records tuples of the form: 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 and Flooding_MPR_time: specifies the time at which the tuple expires 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 on interface i records router IDs of
symmetric 1-hop neighbors of this router that have selected this the set of symmetric 1-hop neighbors of this router on interface i
router as Flooding-MPR. There is one Flooding-MPR-selector set per that have selected this router as Flooding-MPR. There is one
MANET interface. More precisely, the Flooding-MPR-selector set Flooding-MPR-selector set per MANET interface. More precisely, the
records tuples of the form: 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 neighbor of this router, that has selected this router as
Flooding-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 routers in N over any MANET The Path-MPR set records router IDs of routers in N, that provide
interface, that provide shortest paths from routers in N2 (over any shortest paths from routers in N2 and to this router. There is one
MANET interface) to this router. There is one Path-MPR set per Path-MPR set per router. More precisely, the Path-MPR set records
router. More precisely, the Path-MPR set records tuples of the form: 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, 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.
skipping to change at page 10, line 48 skipping to change at page 12, line 9
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.
This document defines and employs the following TLVs in Hello packets This document defines and employs the following TLVs in Hello packets
sent over OSPFv3 MANET interfaces: sent over OSPFv3 MANET interfaces:
FMPR - signaling Flooding-MPR selection; FMPR - signaling Flooding-MPR selection;
PMPR - signaling Path-MPR selection; PMPR - signaling Path-MPR selection;
METRIC - signaling metrics. METRIC-MPR - signaling metrics.
The layout and internal structure of these TLVs is detailed in The layout and internal structure of these TLVs is detailed in
Section 6. 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
skipping to change at page 11, line 43 skipping to change at page 13, line 4
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. The FMPR TLV structure is detailed in Section 6.1. 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 included in the order as given below: interfaces MUST be included in the order as given below:
1. symmetric 1-hop neighbors which are selected as Flooding-MPRs; 1. symmetric 1-hop neighbors which are selected as Flooding-MPRs;
2. other symmetric 1-hop neighbors; 2. other symmetric 1-hop neighbors;
3. other 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 Signaling - METRIC TLV and PMPR TLV 5.2.4. Metric Signaling - METRIC-MPR 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 its MANET The costs of the links between the router and each of its MANET
neighbors on the OSPFv3 MANET interface over which the Hello packet neighbors on the OSPFv3 MANET interface over which the Hello packet
is sent MUST be signaled through including METRIC TLVs. The METRIC is sent MUST be signaled through including METRIC-MPR TLVs. The
TLV structure is detailed in Section 6.2. METRIC-MPR 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 in the (regardless of over which interface) MUST be specified in the
included 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 from among routers in N. Routers in the Path-MPR set a Path-MPR set from among routers in N. Routers in the Path-MPR set
skipping to change at page 13, line 12 skipping to change at page 14, line 18
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. The PMPR TLV containing this PMPR TLV, as detailed in Section 5.2.4. The PMPR TLV
structure is detailed in Section 6.3. 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 [RFC5340], 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. In particular, if a neighborhood of an OSPFv3 MANET interface i. In particular, if a
received Hello packet signals that a tuple in N (or N2) is to be received Hello packet signals that a tuple in N (or N2) is to be
deleted, the deletion is done immediately, without waiting for the deleted, the deletion is done immediately, without waiting for the
tuple to expire. Note that N2 records not only 2-hop neighbors tuple to expire. Note that N2 records not only 2-hop neighbors
listed in received Hellos, but also 2-hop neighbors listed in the listed in received Hellos, but also 2-hop neighbors listed in the
appended PMPR TLVs. appended PMPR TLVs.
The Flooding-MPR set and the Path-MPR set MUST then be recomputed The Flooding-MPR set MUST be recomputed when either of N(i) or N2(i)
when either of N or N2 has changed. Moreover, the Path-MPR set MUST has changed. The Path-MPR set MUST be recomputed when either of N or
be recomputed if appended LLS information signals change with respect N2 has changed. Moreover, the Path-MPR set MUST be recomputed if
to one or more link cost(s). appended LLS information signals change with respect to one or more
link cost(s).
The Flooding-MPR selector set and the Path-MPR selector set MUST be The Flooding-MPR selector set and the Path-MPR selector set MUST be
updated upon receipt of a Hello packet containing LLS information updated upon receipt of a Hello packet containing LLS information
indicating changes in the list of neighbors that has selected the indicating changes in the list of neighbors that has selected the
router as MPR. router as MPR.
If a Hello with the S bit set is received on a OSPFv3 MANET interface If a Hello with the S bit set is received on a OSPFv3 MANET interface
of a router, from a non-adjacent neighbor, the router MUST transition of a router, from a non-adjacent neighbor, the router MUST transition
this neighbor's state to ExStart. this neighbor's state to ExStart.
skipping to change at page 19, line 34 skipping to change at page 20, line 39
the number of symmetric 1-hop neighbors. These symmetric 1-hop the number of symmetric 1-hop neighbors. These symmetric 1-hop
neighbors are listed first among the neighbors in a Hello packet. neighbors are listed first among the neighbors in a Hello packet.
# Flood 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 Flooding-MPR. These Flooding-MPRs number of neighbors selected as Flooding-MPR. These Flooding-MPRs
are listed first among the symmetric 1-hop neighbors. are listed first among the symmetric 1-hop neighbors.
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 TLV 6.2. Metric-MPR TLV
A TLV of Type METRIC is defined for signaling costs of links to A TLV of Type METRIC-MPR 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-MPR | 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 TLV (METRIC). Figure 2: Metric TLV (METRIC-MPR).
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).
skipping to change at page 21, line 8 skipping to change at page 22, line 8
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.
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-MPR | Length |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Reserved |0|R| Cost 0 | | Reserved |0|R| Cost 0 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Cost 1 | Cost 2 | | Cost 1 | Cost 2 |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 3: Metric Advertisement TLV (METRIC) example with explicit Figure 3: Metric Advertisement TLV (METRIC-MPR) example with
individual link costs (U=0) and an odd number of Costs (and, hence, explicit individual link costs (U=0) and an odd number of Costs (and,
no padding). 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=METRIC | Length | | Type=METRIC-MPR | 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-MPR) example with a
and uniform link cost (U=1) (and, hence, no padding). single and uniform link cost (U=1) (and, hence, no padding).
6.3. Path-MPR TLV 6.3. Path-MPR TLV
A TLV of Type PMPR 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
skipping to change at page 24, line 32 skipping to change at page 25, line 32
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
| Cost n-1 | Cost n | | Cost n-1 | Cost n |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
Figure 6: Path-MPR TLV (PMPR) with explicit individual link costs Figure 6: Path-MPR TLV (PMPR) with explicit individual link costs
(U=0) and an even number of Cost fields (hence, no padding). (U=0) and an even number of Cost fields (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=PMPR | 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 TLV (PMPR) with a single and uniform link cost Figure 7: Path-MPR TLV (PMPR) with a single and uniform link cost
(U=1) (hence, padding included). (U=1) (hence, padding included).
7. Security Considerations 7. Security Considerations
[RFC4593] describes generic threats to routing protocols, whose [RFC4593] describes generic threats to routing protocols, whose
applicability to OSPFv3 [RFC5340] is not altered by the presence of applicability to OSPFv3 [RFC5340] is not altered by the presence of
OSPFv3 MANET interfaces. As such, the OSPFv3 MANET interface type OSPFv3 MANET interfaces. As such, the OSPFv3 MANET interface type
does not introduce new security threats to [RFC5340]. does not introduce new security threats to [RFC5340].
However, the use of a wireless medium use and the lack of However, the use of a wireless medium and the lack of infrastructure,
infrastructure, as enabled by the use of the OSPFv3 MANET interface as enabled by the use of the OSPFv3 MANET interface type, may render
type, may render some of the attacks described in [RFC4593] easier to some of the attacks described in [RFC4593] easier to undertake.
undertake.
For example, control traffic sniffing and control traffic analysis For example, control traffic sniffing and control traffic analysis
are simpler tasks with wireless than with wires, as it is sufficient are simpler tasks with wireless than with wires, as it is sufficient
to be somewhere within radio range in order to "listen" to wireless to be somewhere within radio range in order to "listen" to wireless
traffic. Inconspicuous wiretapping of the right cable(s) is not traffic. Inconspicuous wiretapping of the right cable(s) is not
necessary. necessary.
In a similar fashion, physical signal interference is also a simpler In a similar fashion, physical signal interference is also a simpler
task with wireless than with wires, as it is sufficient to emit from 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 somewhere within radio range in order to be able to disrupt the
skipping to change at page 25, line 44 skipping to change at page 26, line 43
more dynamic nature of MANET topologies may decrease the consequence more dynamic nature of MANET topologies may decrease the consequence
period, as harmful information (or lack of information) will tend to period, as harmful information (or lack of information) will tend to
be replaced quicker by legitimate information. be replaced quicker by legitimate information.
8. IANA Considerations 8. IANA Considerations
This document defines three LLS TLVs, for which allocation of type This document defines three LLS TLVs, for which allocation of type
values are requested from the LLS TLV type registry defined in values are requested from the LLS TLV type registry defined in
[RFC4813]. [RFC4813].
+----------+------------+--------------+ +------------+------------+--------------+
| Mnemonic | Type Value | Name | | Mnemonic | Type Value | Name |
+----------+------------+--------------+ +------------+------------+--------------+
| FMPR | tbd | Flooding-MPR | | FMPR | tbd | Flooding-MPR |
| METRIC | tbd | Metric | | METRIC-MPR | tbd | Metric-MPR |
| PMPR | 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.
skipping to change at page 27, line 11 skipping to change at page 28, line 11
Topology in an MPR-based Solution for Wireless OSPF Topology in an MPR-based Solution for Wireless OSPF
on Mobile Ad Hoc Networks", INRIA Research on Mobile Ad Hoc Networks", INRIA Research
Report RR-5619, 2005. Report RR-5619, 2005.
[RFC4593] Barbir, A., Murphy, S., and Y. Yang, "Generic [RFC4593] Barbir, A., Murphy, S., and Y. Yang, "Generic
Threats to Routing Protocols", RFC 4593, 2006. Threats to Routing Protocols", RFC 4593, 2006.
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 on interface i. It constructs a Flooding-MPR set that
router to reach routers in the 2-hop neighborhood through relaying by enables a router to reach routers in the 2-hop neighborhood through
one Flooding-MPR router. relaying by 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(i), defined as the number of neighbors of router Y, EXCLUDING
the members of N and EXCLUDING the router performing the computation. all the members of N(i) and EXCLUDING the router performing the
The proposed heuristic can then be described as follows. Begin with computation. The proposed heuristic can then be described as
an empty Flooding-MPR set. Then: follows. Begin with an empty Flooding-MPR set. Then:
1. Calculate D(Y), where Y is a member of N, for all routers in N. 1. Calculate D(Y), where Y is a member of N(i), for all routers in
N(i).
2. Add to the Flooding-MPR set those routers in N, which are the 2. Add to the Flooding-MPR set those routers in N(i), which are the
only routers to provide reachability to a router in N2. For only routers to provide reachability to a router in N2(i). For
example, if router B in N2 can be reached only through a router A example, if router B in N2(i) can be reached only through a
in N, then add router A to the Flooding-MPR set. Remove the router A in N(i), then add router A to the Flooding-MPR set.
routers from N2 which are now covered by a router in the Remove the routers from N2(i) which are now covered by a router
Flooding-MPR set. in the Flooding-MPR set.
3. While there exist routers in N2 which are not covered by at least 3. While there exist routers in N2(i) which are not covered by at
one router in the Flooding-MPR set: least 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(i), calculate the reachability, i.e. the
number of routers in N2 which are not yet covered by at least number of routers in N2(i) which are not yet covered by at
one router in the Flooding-MPR set, and which are reachable least one router in the Flooding-MPR set, and which are
through this 1-hop neighbor; reachable 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(i) with non-zero
reachability. In case of a tie among routers with same reachability. In case of a tie among routers with same
willingness, select the router which provides reachability to willingness, select the router which provides reachability to
the maximum number of routers in N2. In case of another tie the maximum number of routers in N2(i). In case of another
between routers also providing the same amount of tie 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(i) which are now covered
a router in the Flooding-MPR set. by a router in the Flooding-MPR set.
4. As an optimization, consider in increasing order of willingness 4. As an optimization, consider in increasing order of willingness
each router Y in the Flooding-MPR set: if all routers in N2 are each router Y in the Flooding-MPR set: if all routers in N2(i)
still covered by at least one router in the Flooding-MPR set when are still covered by at least one router in the Flooding-MPR set
excluding router Y, then router Y MAY be removed from the when 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. However, the algorithm used MUST provide the router independently. However, the algorithm used MUST provide the router
with a Flooding-MPR set that fulfills the flooding coverage with a Flooding-MPR set that fulfills the flooding coverage
criterion, i.e. it MUST select a Flooding-MPR set such that any 2-hop criterion, i.e. it MUST select a Flooding-MPR set such that any 2-hop
neighbor is covered by at least one Flooding-MPR router. neighbor is covered by at least one Flooding-MPR router.
Appendix B. Path-MPR Selection Heuristic Appendix B. Path-MPR Selection Heuristic
skipping to change at page 29, line 27 skipping to change at page 30, line 28
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(i) and N2' instead of N2(i). The resulting MPR
the Path-MPR set. set is 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, the algorithm used MUST provide the router independently. However, the algorithm used MUST provide the router
with a Path-MPR set that fulfills the path coverage criterion, i.e. with a Path-MPR set that fulfills the path coverage criterion, i.e.
it MUST select a Path-MPR set such that for any element of N or N2 it MUST select a Path-MPR set such that for any element of N or N2
that is not in the Path-MPR set, there exists a shortest path that 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 goes from this element to the router through a neighbor selected as
Path-MPR (unless the shortest path is only one hop). 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, Ulrich The authors would like to thank Juan Antonio Cordero Fuertes, Ulrich
Herberg and Richard Ogier for reviewing this document. Herberg and Richard Ogier for reviewing this document.
skipping to change at page 31, line 4 skipping to change at line 1368
Phone: +1-613-949-8216 Phone: +1-613-949-8216
EMail: dang.nguyen@crc.ca 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
Copyright (C) The IETF Trust (2008).
This document is subject to the rights, licenses and restrictions
contained in BCP 78, and except as set forth therein, the authors
retain all their rights.
This document and the information contained herein are provided on an
"AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Intellectual Property
The IETF takes no position regarding the validity or scope of any
Intellectual Property Rights or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; nor does it represent that it has
made any independent effort to identify any such rights. Information
on the procedures with respect to rights in RFC documents can be
found in BCP 78 and BCP 79.
Copies of IPR disclosures made to the IETF Secretariat and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementers or users of this
specification can be obtained from the IETF on-line IPR repository at
http://www.ietf.org/ipr.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights that may cover technology that may be required to implement
this standard. Please address the information to the IETF at
ietf-ipr@ietf.org.
 End of changes. 51 change blocks. 
154 lines changed or deleted 163 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/