GENWiki

Premier IT Outsourcing and Support Services within the UK

User Tools

Site Tools


rfc:rfc5449

Network Working Group E. Baccelli Request for Comments: 5449 P. Jacquet Category: Experimental INRIA

                                                             D. Nguyen
                                                                   CRC
                                                            T. Clausen
                                              LIX, Ecole Polytechnique
                                                         February 2009
     OSPF Multipoint Relay (MPR) Extension for Ad Hoc Networks

Status of This Memo

 This memo defines an Experimental Protocol for the Internet
 community.  It does not specify an Internet standard of any kind.
 Discussion and suggestions for improvement are requested.
 Distribution of this memo is unlimited.

Copyright Notice

 Copyright (c) 2009 IETF Trust and the persons identified as the
 document authors.  All rights reserved.
 This document is subject to BCP 78 and the IETF Trust's Legal
 Provisions Relating to IETF Documents (http://trustee.ietf.org/
 license-info) in effect on the date of publication of this document.
 Please review these documents carefully, as they describe your rights
 and restrictions with respect to this document.

Abstract

 This document specifies an OSPFv3 interface type tailored for mobile
 ad hoc networks.  This interface type is derived from the broadcast
 interface type, and is denoted the "OSPFv3 MANET interface type".

Baccelli, et al. Experimental [Page 1] RFC 5449 OSPF MPR Extension for MANET February 2009

Table of Contents

 1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
 2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  3
 3.  Applicability Statement  . . . . . . . . . . . . . . . . . . .  5
   3.1.  MANET Characteristics  . . . . . . . . . . . . . . . . . .  5
   3.2.  OSPFv3 MANET Interface Characteristics . . . . . . . . . .  5
 4.  Protocol Overview and Functioning  . . . . . . . . . . . . . .  6
   4.1.  Efficient Flooding Using MPRs  . . . . . . . . . . . . . .  6
   4.2.  MPR Topology-Reduction . . . . . . . . . . . . . . . . . .  6
   4.3.  Multicast Transmissions of Protocol Packets  . . . . . . .  7
   4.4.  MPR Adjacency-Reduction  . . . . . . . . . . . . . . . . .  7
 5.  Protocol Details . . . . . . . . . . . . . . . . . . . . . . .  7
   5.1.  Data Structures  . . . . . . . . . . . . . . . . . . . . .  7
     5.1.1.  N(i): Symmetric 1-Hop Neighbor Set . . . . . . . . . .  7
     5.1.2.  N2(i): Symmetric Strict 2-Hop Neighbor Set . . . . . .  8
     5.1.3.  Flooding-MPR Set . . . . . . . . . . . . . . . . . . .  8
     5.1.4.  Flooding-MPR-Selector Set  . . . . . . . . . . . . . .  9
     5.1.5.  Path-MPR Set . . . . . . . . . . . . . . . . . . . . .  9
     5.1.6.  Path-MPR-Selector Set  . . . . . . . . . . . . . . . . 10
     5.1.7.  MPR Set  . . . . . . . . . . . . . . . . . . . . . . . 10
     5.1.8.  MPR-Selector Set . . . . . . . . . . . . . . . . . . . 10
   5.2.  Hello Protocol . . . . . . . . . . . . . . . . . . . . . . 10
     5.2.1.  Flooding-MPR Selection . . . . . . . . . . . . . . . . 11
     5.2.2.  Flooding-MPR Selection Signaling - FMPR TLV  . . . . . 11
     5.2.3.  Neighbor Ordering  . . . . . . . . . . . . . . . . . . 12
     5.2.4.  Metric Signaling - METRIC-MPR TLV and PMPR TLV . . . . 12
     5.2.5.  Path-MPR Selection . . . . . . . . . . . . . . . . . . 12
     5.2.6.  Path-MPR Selection Signaling - PMPR TLV  . . . . . . . 12
     5.2.7.  Hello Packet Processing  . . . . . . . . . . . . . . . 13
   5.3.  Adjacencies  . . . . . . . . . . . . . . . . . . . . . . . 13
     5.3.1.  Packets over 2-Way Links . . . . . . . . . . . . . . . 14
     5.3.2.  Adjacency Conservation . . . . . . . . . . . . . . . . 14
   5.4.  Link State Advertisements  . . . . . . . . . . . . . . . . 14
     5.4.1.  LSA Flooding . . . . . . . . . . . . . . . . . . . . . 15
     5.4.2.  Link State Acknowledgments . . . . . . . . . . . . . . 17
   5.5.  Hybrid Routers . . . . . . . . . . . . . . . . . . . . . . 18
   5.6.  Synch Routers  . . . . . . . . . . . . . . . . . . . . . . 18
   5.7.  Routing Table Computation  . . . . . . . . . . . . . . . . 18
 6.  Packet Formats . . . . . . . . . . . . . . . . . . . . . . . . 19
   6.1.  Flooding-MPR  TLV  . . . . . . . . . . . . . . . . . . . . 19
   6.2.  Metric-MPR TLV . . . . . . . . . . . . . . . . . . . . . . 19
   6.3.  Path-MPR TLV . . . . . . . . . . . . . . . . . . . . . . . 22
 7.  Security Considerations  . . . . . . . . . . . . . . . . . . . 24
 8.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 25
 9.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 26
   9.1.  Normative References . . . . . . . . . . . . . . . . . . . 26
   9.2.  Informative References . . . . . . . . . . . . . . . . . . 26

Baccelli, et al. Experimental [Page 2] RFC 5449 OSPF MPR Extension for MANET February 2009

 Appendix A.  Flooding-MPR Selection Heuristic  . . . . . . . . . . 28
 Appendix B.  Path-MPR Selection Heuristic  . . . . . . . . . . . . 29
 Appendix C.  Contributors  . . . . . . . . . . . . . . . . . . . . 30
 Appendix D.  Acknowledgments . . . . . . . . . . . . . . . . . . . 30

1. Introduction

 This document specifies an extension of OSPFv3 [RFC5340] that is
 adapted to mobile ad hoc networks (MANETs) [RFC2501] and based on
 mechanisms providing:
 Flooding-reduction:  only a subset of all routers will be involved in
    (re)transmissions during a flooding operation.
 Topology-reduction:  only a subset of links are advertised, hence
    both the number and the size of Link State Advertisements (LSAs)
    are decreased.
 Adjacency-reduction:  adjacencies are brought up only with a subset
    of neighbors for lower database synchronization overhead.
 These mechanisms are based on multipoint relays (MPR), a technique
 developed in the Optimized Link State Routing Protocol (OLSR)
 [RFC3626].
 The extension specified in this document integrates into the OSPF
 framework by defining the OSPFv3 MANET interface type.  While this
 extension enables OSPFv3 to function efficiently on mobile ad hoc
 networks, operation of OSPFv3 on other types of interfaces or
 networks, or in areas without OSPFv3 MANET interfaces, remains
 unaltered.

2. Terminology

 The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
 "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and
 "OPTIONAL" in this document are to be interpreted as described in
 [RFC2119].
 This document uses OSPF terminology as defined in [RFC2328] and
 [RFC5340], and Link-Local Signaling (LLS) terminology as defined in
 [RFC4813]; it introduces the following terminology to the OSPF
 nomenclature:
 OSPFv3 MANET interface  - the OSPFv3 interface type for MANETs, as
    specified in this document.

Baccelli, et al. Experimental [Page 3] RFC 5449 OSPF MPR Extension for MANET February 2009

 Additionally, the following terms are used in this document:
 MANET router -  a router that has only OSPFv3 MANET interfaces.
 Wired router -  a router that has only OSPFv3 interface of types
    other than OSPFv3 MANET interfaces.
 Hybrid router -  a router that has OSPFv3 interfaces of several
    types, including at least one of the OSPFv3 MANET interface type.
 Neighbor -  a router, reachable through an OSPFv3 interface (of any
    type).
 MANET neighbor -  a neighbor, reachable through an OSPFv3 MANET
    interface.
 Symmetric 1-hop neighbor -  a neighbor, in a state greater than or
    equal to 2-Way (through an interface of any type).
 Symmetric strict 2-hop neighbor -  a symmetric 1-hop neighbor of a
    symmetric 1-hop neighbor, which is not itself a symmetric 1-hop
    neighbor of the considered router.
 Symmetric strict 2-hop neighborhood -  the set formed by all the
    symmetric strict 2-hop neighbors of the considered router.
 Synch router -  a router that brings up adjacencies with all of its
    MANET neighbors.
 Flooding-MPR -  a router that is selected by its symmetric 1-hop
    neighbor, router X, to retransmit all broadcast protocol packets
    that it receives from router X, provided that the broadcast
    protocol packet is not a duplicate and that the Hop Limit field of
    the protocol packet is greater than one.
 Path-MPR -  a router that is selected by a symmetric 1-hop neighbor,
    X, as being on the shortest path from a router in the symmetric
    strict 2-hop neighborhood of router X to router X.
 Multipoint relay (MPR) -  a router that is selected by its symmetric
    1-hop neighbor as either a Flooding-MPR, a Path-MPR, or both.
 Flooding-MPR-selector -  a router that has selected its symmetric
    1-hop neighbor, router X, as one of its Flooding-MPRs is a
    Flooding-MPR-selector of router X.

Baccelli, et al. Experimental [Page 4] RFC 5449 OSPF MPR Extension for MANET February 2009

 Path-MPR-selector -  a router that has selected its symmetric 1-hop
    neighbor, router X, as one of its Path-MPRs is a Path-MPR selector
    of router X.
 MPR-selector -  a router that has selected its symmetric 1-hop
    neighbor, router X, as either one of its Flooding-MPRs, one of its
    Path-MPRs, or both is an MPR-selector of router X.

3. Applicability Statement

 The OSPFv3 MANET interface type, defined in this specification,
 allows OSPFv3 to be deployed within an area where parts of that area
 are a mobile ad hoc network (MANET) with moderate mobility
 properties.

3.1. MANET Characteristics

 MANETs [RFC2501] are networks in which a dynamic network topology is
 a frequently expected condition, often due to router mobility and/or
 to varying quality of wireless links -- the latter of which also
 generally entails bandwidth scarcity and interference issues between
 neighbors.
 Moreover, MANETs often exhibit "semi-broadcast" properties, i.e., a
 router R that makes a transmission within a MANET can only assume
 that transmission to be received by a subset of the total number of
 routers within that MANET.  Further, if two routers, R1 and R2, each
 make a transmission, neither of these transmissions is guaranteed to
 be received by the same subset of routers within the MANET -- even if
 R1 and R2 can mutually receive transmissions from each other.
 These characteristics are incompatible with several OSPFv3
 mechanisms, including, but not limited to, existing mechanisms for
 control-traffic reduction, such as flooding-reduction, topology-
 reduction, and adjacency-reduction (e.g., Designated Router).

3.2. OSPFv3 MANET Interface Characteristics

 An interface of the OSPFv3 MANET interface type is the point of
 attachment of an OSPFv3 router to a network that may have MANET
 characteristics.  That is, an interface of the OSPFv3 MANET interface
 type is able to accommodate the MANET characteristics described in
 Section 3.1.  An OSPFv3 MANET interface type is not prescribing a set
 of behaviors or expectations that the network is required to satisfy.
 Rather, it is describing operating conditions under which protocols
 on an interface towards that network must be able to function (i.e.,
 the protocols are required to be able to operate correctly when faced
 with the characteristics described in Section 3.1).  As such, the

Baccelli, et al. Experimental [Page 5] RFC 5449 OSPF MPR Extension for MANET February 2009

 OSPFv3 MANET interface type is a generalization of other OSPFv3
 interface types; for example, a protocol operating correctly over an
 OSPFv3 MANET interface would also operate correctly over an OSPFv3
 broadcast interface (whereas the inverse would not necessarily be
 true).
 Efficient OSPFv3 operation over MANETs relies on control-traffic
 reduction and on using mechanisms appropriate for semi-broadcast.
 The OSPFv3 MANET interface type, defined in this document, allows
 networks with MANET characteristics into the OSPFv3 framework by
 integrating mechanisms (flooding-reduction, topology-reduction, and
 adjacency-reduction) derived from solutions standardized by the MANET
 working group.

4. Protocol Overview and Functioning

 The OSPFv3 MANET interface type, defined in this specification, makes
 use of flooding-reduction, topology-reduction, and adjacency-
 reduction, all based on MPR, a technique derived from [RFC3626], as
 standardized in the MANET working group.  Multicast transmissions of
 protocol packets are used when possible.

4.1. Efficient Flooding Using MPRs

 OSPFv3 MANET interfaces use a flooding-reduction mechanism, denoted
 MPR flooding [MPR], whereby only a subset of MANET neighbors (those
 selected as Flooding-MPR) participate in a flooding operation.  This
 reduces the number of (re)transmissions necessary for a flooding
 operation [MPR-analysis], while retaining resilience against
 transmission errors (inherent when using wireless links) and against
 obsolete two-hop neighbor information (e.g., as caused by router
 mobility) [MPR-robustness].

4.2. MPR Topology-Reduction

 OSPFv3 MANET interfaces use a topology-reduction mechanism, denoted
 MPR topology-reduction, whereby only necessary links to MANET
 neighbors (those identified by Path-MPR selection as belonging to
 shortest paths) are included in LSAs.  Routers in a MANET
 periodically generate and flood Router-LSAs describing their
 selection of such links to their Path-MPRs.  Such links are reported
 as point-to-point links.  This reduces the size of LSAs originated by
 routers on a MANET [MPR-topology], while retaining classic OSPF
 properties: optimal paths using synchronized adjacencies (if
 synchronized paths are preferred over non-synchronized paths of equal
 cost).

Baccelli, et al. Experimental [Page 6] RFC 5449 OSPF MPR Extension for MANET February 2009

4.3. Multicast Transmissions of Protocol Packets

 OSPFv3 MANET interfaces employ multicast transmissions when possible,
 thereby taking advantage of inherent broadcast capabilities of the
 medium, if present (with wireless interfaces, this can often be the
 case [RFC2501]).  In particular, LSA acknowledgments are sent via
 multicast over these interfaces, and retransmissions over the same
 interfaces are considered as implicit acknowledgments.  Jitter
 management, such as delaying packet (re)transmission, can be employed
 in order to allow several packets to be bundled into a single
 transmission, which may avoid superfluous retransmissions due to
 packet collisions [RFC5148].

4.4. MPR Adjacency-Reduction

 Adjacencies over OSPFv3 MANET interfaces are required to be formed
 only with a subset of the neighbors of that OSPFv3 MANET interface.
 No Designated Router or Backup Designated Router are elected on an
 OSPFv3 MANET interface.  Rather, adjacencies are brought up over an
 OSPFv3 MANET interface only with MPRs and MPR selectors.  Only a
 small subset of routers in the MANET (called Synch routers) are
 required to bring up adjacencies with all their MANET neighbors.
 This reduces the amount of control traffic needed for database
 synchronization, while ensuring that LSAs still describe only
 synchronized adjacencies.

5. Protocol Details

 This section complements [RFC5340] and specifies the information that
 must be maintained, processed, and transmitted by routers that
 operate one or more OSPFv3 MANET interfaces.

5.1. Data Structures

 In addition to the values used in [RFC5340], the Type field in the
 interface data structure can take a new value, "MANET".  Furthermore,
 and in addition to the protocol structures defined by [RFC5340],
 routers that operate one or more MANET interfaces make use of the
 data structures described below.

5.1.1. N(i): Symmetric 1-Hop Neighbor Set

 The Symmetric 1-hop Neighbor set N(i) records router IDs of the set
 of symmetric 1-hop neighbors of the router on interface i.  More
 precisely, N(i) records tuples of the form:

Baccelli, et al. Experimental [Page 7] RFC 5449 OSPF MPR Extension for MANET February 2009

                 (1_HOP_SYM_id, 1_HOP_SYM_time)
 where:
 1_HOP_SYM_id:  is the router ID of the symmetric 1-hop neighbor of
    this router over interface i.
 1_HOP_SYM_time:  specifies the time at which the tuple expires and
    MUST be removed from the set.
 For convenience throughout this document, N will denote the union of
 all N(i) sets for all MANET interfaces on the router.

5.1.2. N2(i): Symmetric Strict 2-Hop Neighbor Set

 The Symmetric strict 2-hop Neighbor set N2(i) records links between
 routers in N(i) and their symmetric 1-hop neighbors, excluding:
 (i)    the router performing the computation, and
 (ii)   all routers in N(i).
 More precisely, N2(i) records tuples of the form:
             (2_HOP_SYM_id, 1_HOP_SYM_id, 2_HOP_SYM_time)
 where:
 2_HOP_SYM_id:  is the router ID of a symmetric strict 2-hop neighbor.
 1_HOP_SYM_id:  is the router ID of the symmetric 1-hop neighbor of
    this router through which the symmetric strict 2-hop neighbor can
    be reached.
 2_HOP_SYM_time:  specifies the time at which the tuple expires and
    MUST be removed from the set.
 For convenience throughout this document, N2 will denote the union of
 all N2(i) sets for all MANET interfaces on the router.

5.1.3. Flooding-MPR Set

 The Flooding-MPR set on interface i records router IDs of a subset of
 the routers listed in N(i), selected such that, through this subset,
 each router listed in N2(i) is reachable in 2 hops by this router.
 There is one Flooding-MPR set per MANET interface.  More precisely,
 the Flooding-MPR set records tuples of the form:

Baccelli, et al. Experimental [Page 8] RFC 5449 OSPF MPR Extension for MANET February 2009

                  (Flooding_MPR_id, Flooding_MPR_time)
 where:
 Flooding_MPR_id:  is the router ID of the symmetric 1-hop neighbor of
    this router that is selected as Flooding-MPR.
 Flooding_MPR_time:  specifies the time at which the tuple expires and
    MUST be removed from the set.
 Flooding-MPR selection is detailed in Section 5.2.1.

5.1.4. Flooding-MPR-Selector Set

 The Flooding-MPR-selector set on interface i records router IDs of
 the set of symmetric 1-hop neighbors of this router on interface i
 that have selected this router as their Flooding-MPR.  There is one
 Flooding-MPR-selector set per MANET interface.  More precisely, the
 Flooding-MPR-selector set records tuples of the form:
        (Flooding_MPR_SELECTOR_id, Flooding_MPR_SELECTOR_time)
 where:
 Flooding_MPR_SELECTOR_id:  is the router ID of the symmetric 1-hop
    neighbor of this router, that has selected this router as its
    Flooding-MPR.
 Flooding_MPR_SELECTOR_time:  specifies the time at which the tuple
    expires and MUST be removed from the set.
 Flooding-MPR selection is detailed in Section 5.2.1.

5.1.5. Path-MPR Set

 The Path-MPR set records router IDs of routers in N that provide
 shortest paths from routers in N2 to this router.  There is one Path-
 MPR set per router.  More precisely, the Path-MPR set records tuples
 of the form:
                   (Path_MPR_id, Path_MPR_time)
 where:
 Path_MPR_id:  is the router ID of the symmetric 1-hop neighbor of
    this router, selected as Path-MPR.

Baccelli, et al. Experimental [Page 9] RFC 5449 OSPF MPR Extension for MANET February 2009

 Path_MPR_time:  specifies the time at which the tuple expires and
    MUST be removed from the set.
 Path-MPR selection is detailed in Section 5.2.5.

5.1.6. Path-MPR-Selector Set

 The Path-MPR-selector set records router IDs of the set of symmetric
 1-hop neighbors over any MANET interface that have selected this
 router as their Path-MPR.  There is one Path-MPR-selector set per
 router.  More precisely, the Path-MPR-selector set records tuples of
 the form:
        (Path_MPR_SELECTOR_id, Path_MPR_SELECTOR_time)
 where:
 Path_MPR_SELECTOR_id:  is the router ID of the symmetric 1-hop
    neighbor of this router that has selected this router as its Path-
    MPR.
 Path_MPR_SELECTOR_time:  specifies the time at which the tuple
    expires and MUST be removed from the set.
 Path-MPR selection is detailed in Section 5.2.5.

5.1.7. MPR Set

 The MPR set is the union of the Flooding-MPR set(s) and the Path-MPR
 set.  There is one MPR set per router.

5.1.8. MPR-Selector Set

 The MPR-selector set is the union of the Flooding-MPR-selector set(s)
 and the Path-MPR-selector set.  There is one MPR-selector set per
 router.

5.2. Hello Protocol

 On OSPFv3 MANET interfaces, packets are sent, received, and processed
 as defined in [RFC5340] and [RFC2328], and augmented for MPR
 selection as detailed in this section.
 All additional signaling for OSPFv3 MANET interfaces is done through
 inclusion of TLVs within an LLS block [RFC4813], which is appended to
 Hello packets.  If an LLS block is not already present, an LLS block
 MUST be created and appended to the Hello packets.

Baccelli, et al. Experimental [Page 10] RFC 5449 OSPF MPR Extension for MANET February 2009

 Hello packets sent over an OSPFv3 MANET interface MUST have the L bit
 of the OSPF Options field set, as per [RFC4813], indicating the
 presence of an LLS block.
 This document defines and employs the following TLVs in Hello packets
 sent over OSPFv3 MANET interfaces:
 FMPR -  signaling Flooding-MPR selection;
 PMPR -  signaling Path-MPR selection;
 METRIC-MPR -  signaling metrics.
 The layout and internal structure of these TLVs is detailed in
 Section 6.

5.2.1. Flooding-MPR Selection

 The objective of Flooding-MPR selection is for a router to select a
 subset of its neighbors such that a packet, retransmitted by these
 selected neighbors, will be received by all routers 2 hops away.
 This property is called the Flooding-MPR "coverage criterion".  The
 Flooding-MPR set of a router is computed such that, for each OSPFv3
 MANET interface, it satisfies this criterion.  The information
 required to perform this calculation (i.e., link sensing and
 neighborhood information) is acquired through periodic exchange of
 OSPFv3 Hello packets.
 Flooding-MPRs are computed by each router that operates at least one
 OSPFv3 MANET interface.  The smaller the Flooding-MPR set is, the
 lower the overhead will be.  However, while it is not essential that
 the Flooding-MPR set is minimal, the "coverage criterion" MUST be
 satisfied by the selected Flooding-MPR set.
 The willingness of a neighbor router to act as Flooding-MPR MAY be
 taken into consideration by a heuristic for Flooding-MPR selection.
 An example heuristic that takes willingness into account is given in
 Appendix A.

5.2.2. Flooding-MPR Selection Signaling - FMPR TLV

 A router MUST signal its Flooding-MPRs set to its neighbors by
 including an FMPR TLV in generated Hello packets.  Inclusion of this
 FMPR TLV signals the list of symmetric 1-hop neighbors that the
 sending router has selected as Flooding-MPRs, as well as the
 willingness of the sending router to be elected Flooding-MPR by other
 routers.  The FMPR TLV structure is detailed in Section 6.1.

Baccelli, et al. Experimental [Page 11] RFC 5449 OSPF MPR Extension for MANET February 2009

5.2.3. Neighbor Ordering

 Neighbors listed in the Hello packets sent over OSPFv3 MANET
 interfaces MUST be included in the order as given below:
 1.  symmetric 1-hop neighbors that are selected as Flooding-MPRs;
 2.  other symmetric 1-hop neighbors;
 3.  other 1-hop neighbors.
 This ordering allows correct interpretation of an included FMPR TLV.

5.2.4. Metric Signaling - METRIC-MPR TLV and PMPR TLV

 Hello packets sent over OSPFv3 MANET interfaces MUST advertise the
 costs of links towards ALL the symmetric MANET neighbors of the
 sending router.  If the sending router has more than one OSPFv3 MANET
 interface, links to ALL the symmetric MANET neighbors over ALL the
 OSPFv3 MANET interfaces of that router MUST have their costs
 advertised.
 The costs of the links between the router and each of its MANET
 neighbors on the OSPFv3 MANET interface over which the Hello packet
 is sent MUST be signaled by including METRIC-MPR TLVs.  The METRIC-
 MPR TLV structure is detailed in Section 6.2.
 Moreover, the lowest cost from each MANET neighbor towards the router
 (regardless of over which interface) MUST be specified in the
 included PMPR TLV.  Note that the lowest cost can be over an
 interface that is not an OSPFv3 MANET interface.

5.2.5. Path-MPR Selection

 A router that has one or more OSPFv3 MANET interfaces MUST select a
 Path-MPR set from among routers in N.  Routers in the Path-MPR set of
 a router are those that take part in the shortest (with respect to
 the metrics used) path from routers in N2 to this router.  A
 heuristic for Path-MPR selection is given in Appendix B.

5.2.6. Path-MPR Selection Signaling - PMPR TLV

 A router MUST signal its Path-MPR set to its neighbors by including a
 PMPR TLV in generated Hello packets.
 A PMPR TLV MUST contain a list of IDs of all symmetric 1-hop
 neighbors of all OSPFv3 MANET interfaces of the router.  These IDs
 MUST be included in the PMPR TLV in the order as given below:

Baccelli, et al. Experimental [Page 12] RFC 5449 OSPF MPR Extension for MANET February 2009

 1.  Neighbors that are both adjacent AND selected as Path-MPR for any
     OSPFv3 MANET interface of the router generating the Hello packet.
 2.  Neighbors that are adjacent over any OSPFv3 MANET interface of
     the router generating the Hello packet.
 3.  Symmetric 1-hop neighbors on any OSPFv3 MANET interface of the
     router generating the Hello packet that have not been previously
     included in this PMPR TLV.
 The list of neighbor IDs is followed by a list of costs for the links
 from these neighbors to the router generating the Hello packet
 containing this PMPR TLV, as detailed in Section 5.2.4.  The PMPR TLV
 structure is detailed in Section 6.3.

5.2.7. Hello Packet Processing

 In addition to the processing specified in [RFC5340], N and N2 MUST
 be updated when received Hello packets indicate changes to the
 neighborhood of an OSPFv3 MANET interface i.  In particular, if a
 received Hello packet signals that a tuple in N (or N2) is to be
 deleted, the deletion is done immediately, without waiting for the
 tuple to expire.  Note that N2 records not only 2-hop neighbors
 listed in received Hellos but also 2-hop neighbors listed in the
 appended PMPR TLVs.
 The Flooding-MPR set MUST be recomputed when either of N(i) or N2(i)
 has changed.  The Path-MPR set MUST be recomputed when either of N or
 N2 has changed.  Moreover, the Path-MPR set MUST be recomputed if
 appended LLS information signals change with respect to one or more
 link costs.
 The Flooding-MPR-selector set and the Path-MPR-selector set MUST be
 updated upon receipt of a Hello packet containing LLS information
 indicating changes in the list of neighbors that has selected the
 router as MPR.
 If a Hello with the S bit set is received on an OSPFv3 MANET
 interface of a router, from a non-adjacent neighbor, the router MUST
 transition this neighbor's state to ExStart.

5.3. Adjacencies

 Adjacencies are brought up between OSPFv3 MANET interfaces as
 described in [RFC5340] and [RFC2328].  However, in order to reduce
 the control-traffic overhead over the OSPFv3 MANET interfaces, a
 router that has one or more such OSPFv3 MANET interfaces MAY bring up
 adjacencies with only a subset of its MANET neighbors.

Baccelli, et al. Experimental [Page 13] RFC 5449 OSPF MPR Extension for MANET February 2009

 Over an OSPFv3 MANET interface, a router MUST bring up adjacencies
 with all MANET neighbors that are included in its MPR set and its
 MPR-selector set; this ensures that, beyond the first hop, routes use
 synchronized links (if synchronized paths are preferred over non-
 synchronized paths of equal cost).  A router MAY bring up adjacencies
 with other MANET neighbors, at the expense of additional
 synchronization overhead.

5.3.1. Packets over 2-Way Links

 When a router does not form a full adjacency with a MANET neighbor,
 the state of that neighbor does not progress beyond 2-Way (as defined
 in [RFC2328]).  A router can send protocol packets, such as LSAs, to
 a MANET neighbor in 2-Way state.  Therefore, any packet received from
 a symmetric MANET neighbor MUST be processed.
 As with the OSPF broadcast interface [RFC2328], the next hop in the
 forwarding table MAY be a neighbor that is not adjacent.  However,
 when a data packet has travelled beyond its first hop, the MPR-
 selection process guarantees that subsequent hops in the shortest
 path tree (SPT) will be over adjacencies (if synchronized paths are
 preferred over non-synchronized paths of equal cost).

5.3.2. Adjacency Conservation

 Adjacencies are torn down according to [RFC2328].  When the MPR set
 or MPR-selector set is updated (due to changes in the neighborhood),
 and when a neighbor was formerly, but is no longer, in the MPR set or
 the MPR-selector set, then the adjacency with that neighbor is kept
 unless the change causes the neighbor to cease being a symmetric
 1-hop neighbor.
 When a router receives Hello packets from a symmetric 1-hop neighbor
 that ceases to list this router as being adjacent (see
 Section 5.2.6), the state of that neighbor MUST be changed to:
 1.  2-Way if the neighbor is not in the MPR set or MPR-selector set,
     or
 2.  ExStart if either the neighbor is in the MPR set or MPR-selector
     set, or the neighbor or the router itself is a Synch router.

5.4. Link State Advertisements

 Routers generate Router-LSAs periodically, using the format specified
 in [RFC5340] and [RFC2328].

Baccelli, et al. Experimental [Page 14] RFC 5449 OSPF MPR Extension for MANET February 2009

 Routers that have one or more OSPFv3 MANET interfaces MUST include
 the following links in the Router-LSAs that they generate:
 o  links to all neighbors that are in the Path-MPR set, AND
 o  links to all neighbors that are in the Path-MPR-selector set.
 Routers that have one or more OSPFv3 MANET interfaces MAY list other
 links they have through those OSPFv3 MANET interfaces, at the expense
 of larger LSAs.
 In addition, routers that have one or more OSPFv3 MANET interfaces
 MUST generate updated Router-LSAs when either of the following
 occurs:
 o  a new adjacency has been brought up, reflecting a change in the
    Path-MPR set;
 o  a new adjacency has been brought up, reflecting a change in the
    Path-MPR-selector set;
 o  a formerly adjacent and advertised neighbor ceases to be adjacent;
 o  the cost of a link to (or from) an advertised neighbor has
    changed.

5.4.1. LSA Flooding

 An originated LSA is flooded, according to [RFC5340], out all
 interfaces concerned by the scope of this LSA.
 Link State Updates received on an interface of a type other than
 OSPFv3 MANET interface are processed and flooded according to
 [RFC2328] and [RFC5340], over every interface.  If a Link State
 Update was received on an OSPFv3 MANET interface, it is processed as
 follows:
 1.  Consistency checks are performed on the received packet according
     to [RFC2328] and [RFC5340], and the Link State Update packet is
     thus associated with a particular neighbor and a particular area.
 2.  If the Link State Update was received from a router other than a
     symmetric 1-hop neighbor, the Link State Update MUST be discarded
     without further processing.
 3.  Otherwise, for each LSA contained in Link State Updates received
     over an OSPFv3 MANET interface, the following steps replace steps
     1 to 5 of Section 13.3 of [RFC2328].

Baccelli, et al. Experimental [Page 15] RFC 5449 OSPF MPR Extension for MANET February 2009

     (1)  If an LSA exists in the Link State Database, with the same
          Link State ID, LS Type, and Advertising Router values as the
          received LSA, and if the received LSA is not newer (see
          Section 13.1 of [RFC2328]), then the received LSA MUST NOT
          be processed, except for acknowledgment as described in
          Section 5.4.2.
     (2)  Otherwise, the LSA MUST be attributed a scope according to
          its type, as specified in Section 3.5 of [RFC5340].
     (3)  If the scope of the LSA is link local or reserved, the LSA
          MUST NOT be flooded on any interface.
     (4)  Otherwise:
          +  If the scope of the LSA is the area, the LSA MUST be
             flooded on all the OSPFv3 interfaces of the router in
             that area, according to the default flooding algorithm
             described in Section 5.4.1.1.
          +  Otherwise, the LSA MUST be flooded on all the OSPFv3
             interfaces of the router according to the default
             flooding algorithm described in Section 5.4.1.1.

5.4.1.1. Default LSA Flooding Algorithm

 The default LSA flooding algorithm is as follows:
 1.  The LSA MUST be installed in the Link State Database.
 2.  The Age of the LSA MUST be increased by InfTransDelay.
 3.  The LSA MUST be retransmitted over all OSPFv3 interfaces of types
     other than OSPFv3 MANET interface.
 4.  If the sending OSPFv3 interface is a Flooding-MPR-selector of
     this router, then the LSA MUST also be retransmitted over all
     OSPFv3 MANET interfaces concerned by the scope, with the
     multicast address all_SPF_Routers.
 Note that MinLSArrival SHOULD be set to a value that is appropriate
 to dynamic topologies: LSA updating may need to be more frequent in
 MANET parts of an OSPF network than in other parts of an OSPF
 network.

Baccelli, et al. Experimental [Page 16] RFC 5449 OSPF MPR Extension for MANET February 2009

5.4.2. Link State Acknowledgments

 When a router receives an LSA over an OSPFv3 MANET interface, the
 router MUST proceed to acknowledge the LSA as follows:
 1.  If the LSA was not received from an adjacent neighbor, the router
     MUST NOT acknowledge it.
 2.  Otherwise, if the LSA was received from an adjacent neighbor and
     if the LSA is already in the Link State Database (i.e., the LSA
     has already been received and processed), then the router MUST
     send an acknowledgment for this LSA on all OSPFv3 MANET
     interfaces to the multicast address all_SPF_Routers.
 3.  Otherwise, if the LSA is not already in the Link State Database:
     1.  If the router decides to retransmit the LSA (as part of the
         flooding procedure), the router MUST NOT acknowledge it, as
         this retransmission will be considered as an implicit
         acknowledgment.
     2.  Otherwise, if the router decides to not retransmit the LSA
         (as part of the flooding procedure), the router MUST send an
         explicit acknowledgment for this LSA on all OSPFv3 MANET
         interfaces to the multicast address all_SPF_Routers.
 If a router sends an LSA on an OSPFv3 MANET interface, it expects
 acknowledgments (explicit or implicit) from all adjacent neighbors.
 In the case where the router did not generate, but simply relays, the
 LSA, then the router MUST expect acknowledgments (explicit or
 implicit) only from adjacent neighbors that have not previously
 acknowledged this LSA.  If a router detects that some adjacent
 neighbor has not acknowledged the LSA, then that router MUST
 retransmit the LSA.
 If, due to the MPR flooding-reduction mechanism employed for LSA
 flooding as described in Section 5.4.1, a router decides to not relay
 an LSA, the router MUST still expect acknowledgments of this LSA
 (explicit or implicit) from adjacent neighbors that have not
 previously acknowledged this LSA.  If a router detects that some
 adjacent neighbor has not acknowledged the LSA, then the router MUST
 retransmit the LSA.
 Note that it may be beneficial to aggregate several acknowledgments
 in the same transmission, taking advantage of native multicasting (if
 available).  A timer wait MAY thus be used before any acknowledgment
 transmission.

Baccelli, et al. Experimental [Page 17] RFC 5449 OSPF MPR Extension for MANET February 2009

 Additionally, jitter [RFC5148] on packet (re)transmission MAY be used
 in order to increase the opportunities to bundle several packets
 together in each transmission.

5.5. Hybrid Routers

 In addition to the operations described in Section 5.2, Section 5.3
 and Section 5.4, Hybrid routers MUST:
 o  select ALL their MANET neighbors as Path-MPRs.
 o  list adjacencies over OSPFv3 interfaces of types other than OSPFv3
    MANET interface, as specified in [RFC5340] and [RFC2328], in
    generated Router-LSAs.

5.6. Synch Routers

 In a network with no Hybrid routers, at least one Synch router MUST
 be selected.  A Synch router MUST:
 o  set the S bit in the PMPR TLV appended to the Hello packets it
    generates, AND
 o  become adjacent with ALL MANET neighbors.
 A proposed heuristic for selection of Sync routers is as follows:
 o  A router that has a MANET interface and an ID that is higher than
    the ID of all of its current neighbors, and whose ID is higher
    than any other ID present in Router-LSAs currently in its Link
    State Database selects itself as Synch router.
 Other heuristics are possible; however, any heuristic for selecting
 Synch routers MUST ensure the presence of at least one Synch or
 Hybrid router in the network.

5.7. Routing Table Computation

 When routing table (re)computation occurs, in addition to the
 processing of the Link State Database defined in [RFC5340] and
 [RFC2328], routers that have one or more MANET interfaces MUST take
 into account links between themselves and MANET neighbors that are in
 state 2-Way or higher (as data and protocol packets may be sent,
 received, and processed over these links too).  Thus, the
 connectivity matrix used to compute routes MUST reflect links between
 the root and all its neighbors in state 2-Way and higher, as well as
 links described in the Link State Database.

Baccelli, et al. Experimental [Page 18] RFC 5449 OSPF MPR Extension for MANET February 2009

6. Packet Formats

 OSPFv3 packets are as defined by [RFC5340] and [RFC2328].  Additional
 LLS signaling [RFC4813] is used in Hello packets sent over OSPFv3
 MANET interfaces, as detailed in this section.
 This specification uses network byte order (most significant octet
 first) for all fields.

6.1. Flooding-MPR TLV

 A TLV of Type FMPR is defined for signaling Flooding-MPR selection,
 shown in Figure 1.
   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |            Type=FMPR          |           Length              |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |  Willingness  | # Sym. Neigh. |  # Flood MPR  |    Reserved   |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                   Figure 1: Flooding-MPR TLV (FMPR)
 where:
 Willingness -  is an 8-bit unsigned integer field that specifies the
    willingness of the router to flood link-state information on
    behalf of other routers.  It can be set to any integer value from
    1 to 6.  By default, a router SHOULD advertise a willingness of
    WILL_DEFAULT = 3.
 # Sym.  Neigh. -  is an 8-bit unsigned integer field that specifies
    the number of symmetric 1-hop neighbors.  These symmetric 1-hop
    neighbors are listed first among the neighbors in a Hello packet.
 # Flood MPR -  is an 8-bit unsigned integer field that specifies the
    number of neighbors selected as Flooding-MPR.  These Flooding-MPRs
    are listed first among the symmetric 1-hop neighbors.
 Reserved -  is an 8-bit field that SHOULD be cleared ('0') on
    transmission and SHOULD be ignored on reception.

6.2. Metric-MPR TLV

 A TLV of Type METRIC-MPR is defined for signaling costs of links to
 neighbors, shown in Figure 2.

Baccelli, et al. Experimental [Page 19] RFC 5449 OSPF MPR Extension for MANET February 2009

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |        Type=METRIC-MPR        |           Length              |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |         Reserved          |U|R|           Cost 0              |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |           Cost 1              |           Cost 2              |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  :                                                               :
  :                                                               :
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |           Cost n              |            Padding            |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                   Figure 2: Metric TLV (METRIC-MPR)
 where:
 Reserved -  is a 14-bit field that SHOULD be cleared ('0') on
    transmission and SHOULD be ignored on reception.
 R -  is a binary flag, cleared ('0') if the costs advertised in the
    TLV are direct (i.e., the costs of the links from the router to
    the neighbors), or set ('1') if the costs advertised are reverse
    (i.e., the costs of the links from the neighbors to the router).
    By default, R is cleared ('0').
 U -  is a binary flag, cleared ('0') if the cost for each link from
    the sending router and to each advertised neighbor is explicitly
    included (shown in Figure 3), or set ('1') if a single metric
    value is included that applies to all links (shown in Figure 4).
 Cost n -  is an 8-bit unsigned integer field that specifies the cost
    of the link, in the direction specified by the R flag, between
    this router and the neighbor listed at the n-th position in the
    Hello packet when counting from the beginning of the Hello packet
    and with the first neighbor being at position 0.
 Padding -  is a 16-bit field that SHOULD be cleared ('0') on
    transmission and SHOULD be ignored on reception.  Padding is
    included in order that the TLV is 32-bit aligned.  Padding MUST be
    included when the TLV contains an even number of Cost fields and
    MUST NOT be included otherwise.

Baccelli, et al. Experimental [Page 20] RFC 5449 OSPF MPR Extension for MANET February 2009

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |        Type=METRIC-MPR        |           Length              |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |         Reserved          |0|R|           Cost 0              |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |           Cost 1              |           Cost 2              |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 Figure 3: Metric Advertisement TLV (METRIC-MPR) example with explicit
  individual link costs (U=0) and an odd number of Costs (and, hence,
                             no padding).
   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |        Type=METRIC-MPR        |           Length              |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |         Reserved          |1|R|           Cost                |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 Figure 4: Metric Advertisement TLV (METRIC-MPR) example with a single
         and uniform link cost (U=1) (and, hence, no padding).

Baccelli, et al. Experimental [Page 21] RFC 5449 OSPF MPR Extension for MANET February 2009

6.3. Path-MPR TLV

 A TLV of Type PMPR is defined for signaling Path-MPR selection, shown
 in Figure 1, as well as the link cost associated with these Path-
 MPRs.
   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |            Type=PMPR          |           Length              |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |  # Sym Neigh  |  # Adj. Neigh |   # Path-MPR  | Reserved  |U|S|
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |                           Neighbor ID                         |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |                           Neighbor ID                         |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  :                                                               :
  :                                                               :
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |             Cost 0            |            Cost 1             |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  :                                                               :
  :                                                               :
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |             Cost n            |            Padding            |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                     Figure 5: Path-MPR TLV (PMPR)
 # Sym Neigh. -  is an 8-bit unsigned integer field that specifies the
    number of symmetric 1-hop MANET neighbors of all OSPFv3 MANET
    interfaces of the router, listed in the PMPR TLV.
 # Adj.  Neigh. -  is an 8-bit unsigned integer field that specifies
    the number of adjacent neighbors.  These adjacent neighbors are
    listed first among the symmetric 1-hop MANET neighbors of all
    OSPFv3 MANET interfaces of the router in the PMPR TLV.
 # Path-MPR -  is an 8-bit unsigned integer field that specifies the
    number of MANET neighbors selected as Path-MPR.  These Path-MPRs
    are listed first among the adjacent MANET neighbors in the PMPR
    TLV.
 Reserved -  is a 6-bit field that SHOULD be cleared ('0') on
    transmission and SHOULD be ignored on reception.

Baccelli, et al. Experimental [Page 22] RFC 5449 OSPF MPR Extension for MANET February 2009

 U -  is a binary flag, cleared ('0') if the cost for each link from
    each advertised neighbor in the PMPR TLV and to the sending router
    is explicitly included (as shown in Figure 6), or set ('1') if a
    single metric value is included that applies to all links (as
    shown in Figure 7).
 S -  is a binary flag, cleared ('0') if the router brings up
    adjacencies only with neighbors in its MPR set and MPR-selector
    set, as per Section 5.3, or set ('1') if the router brings up
    adjacencies with all MANET neighbors as a Synch router, as per
    Section 5.6.
 Neighbor ID -  is a 32-bit field that specifies the router ID of a
    symmetric 1-hop neighbor of an OSPFv3 MANET interface of the
    router.
 Cost n -  is a 16-bit unsigned integer field that specifies the cost
    of the link in the direction from the n-th listed advertised
    neighbor in the PMPR TLV and towards this router.  A default value
    of 0xFFFF (i.e., infinity) MUST be advertised unless information
    received via Hello packets from the neighbor specifies otherwise,
    in which case the received information MUST be advertised.  If a
    neighbor is reachable via more than one interface, the cost
    advertised MUST be the minimum of the costs by which that neighbor
    can be reached.
 Padding -  is a 16-bit field that SHOULD be cleared ('0') on
    transmission and SHOULD be ignored on reception.  Padding is
    included in order that the PMPR TLV is 32-bit aligned.  Padding
    MUST be included when the TLV contains an odd number of Cost
    fields and MUST NOT be included otherwise.

Baccelli, et al. Experimental [Page 23] RFC 5449 OSPF MPR Extension for MANET February 2009

   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |            Type=PMPR          |           Length              |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |  # Sym Neigh  |  # Adj. Neigh |   # Path-MPR  | Reserved  |0|S|
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |                           Neighbor ID                         |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |                           Neighbor ID                         |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  :                                                               :
  :                                                               :
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |             Cost 1            |            Cost 2             |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  :                            .......                            :
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |            Cost n-1           |            Cost n             |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   Figure 6: Path-MPR TLV (PMPR) with explicit individual link costs
     (U=0) and an even number of Cost fields (hence, no padding).
   0                   1                   2                   3
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |         Type=PMPR             |           Length              |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |  # Sym Neigh  |  # Adj. Neigh |   # Path-MPR  | Reserved  |1|S|
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |                           Neighbor ID                         |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |                           Neighbor ID                         |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
  |             Cost              |            Padding            |
  +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   Figure 7: Path-MPR TLV (PMPR) with a single and uniform link cost
                   (U=1) (hence, padding included).

7. Security Considerations

 [RFC4593] describes generic threats to routing protocols, whose
 applicability to OSPFv3 [RFC5340] is not altered by the presence of
 OSPFv3 MANET interfaces.  As such, the OSPFv3 MANET interface type
 does not introduce new security threats to [RFC5340].

Baccelli, et al. Experimental [Page 24] RFC 5449 OSPF MPR Extension for MANET February 2009

 However, the use of a wireless medium and the lack of infrastructure,
 as enabled by the use of the OSPFv3 MANET interface type, may render
 some of the attacks described in [RFC4593] easier to undertake.
 For example, control-traffic sniffing and control-traffic analysis
 are simpler tasks with wireless than with wires, as it is sufficient
 to be somewhere within radio range in order to "listen" to wireless
 traffic.  Inconspicuous wiretapping of the right cable(s) is not
 necessary.
 In a similar fashion, physical signal interference is also a simpler
 task with wireless than with wires, as it is sufficient to emit from
 somewhere within radio range in order to be able to disrupt the
 communication medium.  No complex wire connection is required.
 Other types of interference (including not forwarding packets),
 spoofing, and different types of falsification or overloading (as
 described in [RFC4593]) are also threats to which routers using
 OSPFv3 MANET interfaces may be subject.  In these cases, the lack of
 predetermined infrastructure or authority, enabled by the use of
 OSPFv3 MANET interfaces, may facilitate such attacks by making it
 easier to forge legitimacy.
 Moreover, the consequence zone of a given threat, and its consequence
 period (as defined in [RFC4593]), may also be slightly altered over
 the wireless medium, compared to the same threat over wired networks.
 Indeed, mobility and the fact that radio range spans "further" than a
 mere cable may expand the consequence zone in some cases; meanwhile,
 the more dynamic nature of MANET topologies may decrease the
 consequence period, as harmful information (or lack of information)
 will tend to be replaced quicker by legitimate information.

8. IANA Considerations

 This document defines three LLS TLVs, for which type values have been
 allocated from the LLS TLV type registry defined in [RFC4813].
              +------------+------------+--------------+
              |  Mnemonic  | Type Value | Name         |
              +------------+------------+--------------+
              |    FMPR    |      3     | Flooding-MPR |
              | METRIC-MPR |      4     | Metric-MPR   |
              |    PMPR    |      5     | Path-MPR     |
              +------------+------------+--------------+
                   Table 1: LLS TLV Type Assignments

Baccelli, et al. Experimental [Page 25] RFC 5449 OSPF MPR Extension for MANET February 2009

9. References

9.1. Normative References

 [RFC2119]         Bradner, S., "Key words for use in RFCs to Indicate
                   Requirement Levels", BCP 14, RFC 2119, March 1997.
 [RFC2328]         Moy, J., "OSPF Version 2", STD 54, RFC 2328,
                   April 1998.
 [RFC4813]         Friedman, B., Nguyen, L., Roy, A., Yeung, D., and
                   A. Zinin, "OSPF Link-Local Signaling", RFC 4813,
                   March 2007.
 [RFC5340]         Coltun, R., Ferguson, D., Moy, J., and A. Lindem,
                   "OSPF for IPv6", RFC 5340, July 2008.

9.2. Informative References

 [MPR]             Qayyum, A., Viennot, L., and A. Laouiti,
                   "Multipoint Relaying for Flooding Broadcast
                   Messages in Mobile Wireless Networks", Proceedings
                   of HICSS , 2002.
 [MPR-analysis]    Ngyuen, D. and P. Minet, "Analysis of MPR Selection
                   in the OLSR Protocol", 2nd Int. Workshop on
                   Performance Analysis and Enhancement of
                   Wireless Networks, 2007.
 [MPR-robustness]  Adjih, C., Baccelli, E., Clausen, T., and P.
                   Jacquet, "On the Robustness and Stability of
                   Connected Dominated Sets", INRIA Research
                   Report RR-5609, 2005.
 [MPR-topology]    Baccelli, E., Clausen, T., and P. Jacquet, "Partial
                   Topology in an MPR-based Solution for Wireless OSPF
                   on Mobile Ad Hoc Networks", INRIA Research
                   Report RR-5619, 2005.
 [RFC2501]         Corson, S. and J. Macker, "Mobile Ad hoc Networking
                   (MANET): Routing Protocol Performance Issues and
                   Evaluation Considerations", RFC 2501,
                   February 1999.
 [RFC3626]         Clausen, T. and P. Jacquet, "Optimized Link State
                   Routing Protocol (OLSR)", RFC 3626, October 2003.

Baccelli, et al. Experimental [Page 26] RFC 5449 OSPF MPR Extension for MANET February 2009

 [RFC4593]         Barbir, A., Murphy, S., and Y. Yang, "Generic
                   Threats to Routing Protocols", RFC 4593,
                   October 2006.
 [RFC5148]         Clausen, T., Dearlove, C., and B. Adamson, "Jitter
                   Considerations in Mobile Ad Hoc Networks (MANETs)",
                   RFC 5148, February 2008.

Baccelli, et al. Experimental [Page 27] RFC 5449 OSPF MPR Extension for MANET February 2009

Appendix A. Flooding-MPR Selection Heuristic

 The following specifies a proposed heuristic for selection of
 Flooding-MPRs on interface i.  It constructs a Flooding-MPR set that
 enables a router to reach routers in the 2-hop neighborhood through
 relaying by one Flooding-MPR router.
 The following terminology will be used in describing the heuristics:
 D(Y) is the degree of a 1-hop neighbor, router Y (where Y is a member
 of N(i), defined as the number of neighbors of router Y, EXCLUDING
 all the members of N(i) and EXCLUDING the router performing the
 computation.  The proposed heuristic can then be described as
 follows.  Begin with an empty Flooding-MPR set.  Then:
 1.  Calculate D(Y), where Y is a member of N(i), for all routers in
     N(i).
 2.  Add to the Flooding-MPR set those routers in N(i) that are the
     only routers to provide reachability to a router in N2(i).  For
     example, if router B in N2(i) can be reached only through a
     router A in N(i), then add router A to the Flooding-MPR set.
     Remove the routers from N2(i) that are now covered by a router in
     the Flooding-MPR set.
 3.  While there exist routers in N2(i) that are not covered by at
     least one router in the Flooding-MPR set:
     1.  For each router in N(i), calculate the reachability, i.e.,
         the number of routers in N2(i) that are not yet covered by at
         least one router in the Flooding-MPR set, and that are
         reachable through this 1-hop neighbor;
     2.  Select as a Flooding-MPR the neighbor with the highest
         willingness among the routers in N(i) with non-zero
         reachability.  In case of a tie among routers with the same
         willingness, select the router that provides reachability to
         the maximum number of routers in N2(i).  In case of another
         tie between routers also providing the same amount of
         reachability, select as Flooding-MPR the router whose D(Y) is
         greater.  Remove the routers from N2(i) that are now covered
         by a router in the Flooding-MPR set.
 4.  As an optimization, consider in increasing order of willingness
     each router Y in the Flooding-MPR set: if all routers in N2(i)
     are still covered by at least one router in the Flooding-MPR set
     when excluding router Y, then router Y MAY be removed from the
     Flooding-MPR set.

Baccelli, et al. Experimental [Page 28] RFC 5449 OSPF MPR Extension for MANET February 2009

 Other algorithms, as well as improvements over this algorithm, are
 possible.  Different routers may use different algorithms
 independently.  However, the algorithm used MUST provide the router
 with a Flooding-MPR set that fulfills the flooding coverage
 criterion, i.e., it MUST select a Flooding-MPR set such that any
 2-hop neighbor is covered by at least one Flooding-MPR router.

Appendix B. Path-MPR Selection Heuristic

 The following specifies a proposed heuristic for calculating a Path-
 MPR set that enables a router to reach routers in the 2-hop
 neighborhood through shortest paths via routers in its Path-MPR set.
 The following terminology will be used for describing this heuristic:
 A -  The router performing the Path-MPR set calculation.
 B, C, D, .... -  Other routers in the network.
 cost(A,B) -  The cost of the path through the direct link, from A to
    B.
 dist(C,A) -  The cost of the shortest path from C to A.
 A cost matrix is populated with the values of the costs of links
 originating from router A (available locally) and with values listed
 in Hello packets received from neighbor routers.  More precisely, the
 cost matrix is populated as follows:
 1.  The coefficients of the cost matrix are set by default to 0xFFFF
     (maximal value, i.e., infinity).
 2.  The coefficient cost(A,B) of the cost matrix for a link from
     router A to a neighbor B (the direct cost for this link) is set
     to the minimum cost over all interfaces that feature router B as
     a symmetric 1-hop neighbor.  The reverse cost for this link,
     cost(B,A), is set at the value received in Hello packets from
     router B.  If router B is reachable through several interfaces at
     the same time, cost(B,A) is set as the minimum cost advertised by
     router B for its links towards router A.
 3.  The coefficients of the cost matrix concerning the link between
     two neighbors of A, routers C and B, are populated at the
     reception of their Hello packets.  The cost(B,C) is set to the
     value advertised by the Hello packets from B, and, respectively,
     the cost(C,B) is set to the value advertised in Hello packets
     from C.

Baccelli, et al. Experimental [Page 29] RFC 5449 OSPF MPR Extension for MANET February 2009

 4.  The coefficients cost(B,C) of the cost matrix for a link that
     connects a neighbor B to a 2-hop neighbor C are obtained via the
     Hello packets received from router B.  In this case, cost(B,C)
     and cost(C,B) are respectively set to the values advertised by
     router B for the direct cost and reverse cost for node C.
 Once the cost matrix is populated, the proposed heuristic can then be
 described as follows.  Begin with an empty Path-MPR set.  Then:
 1.  Using the cost matrix and the Dijkstra algorithm, compute the
     router distance vector, i.e., the shortest distance for each pair
     (X,A) where X is in N or N2 minimizing the sum of the cost of the
     path between X and A.
 2.  Compute N' as the subset of N made of the elements X such that
     cost(X,A)=dist(X,A).
 3.  Compute N2' as the subset of N and N2 made of the elements Y that
     do not belong to N' and such that there exist X in N' such
     cost(Y,X)+cost(X,A)=dist(Y,A).
 4.  Compute the MPR selection algorithm presented in Appendix A with
     N' instead of N(i) and N2' instead of N2(i).  The resulting MPR
     set is the Path-MPR set.
 Other algorithms, as well as improvements over this algorithm, are
 possible.  Different routers may use different algorithms
 independently.  However, the algorithm used MUST provide the router
 with a Path-MPR set that fulfills the path coverage criterion, i.e.,
 it MUST select a Path-MPR set such that for any element of N or N2
 that is not in the Path-MPR set, there exists a shortest path that
 goes from this element to the router through a neighbor selected as
 Path-MPR (unless the shortest path is only one hop).

Appendix C. Contributors

 The authors would like to thank Cedric Adjih, Acee Lindem, Padma
 Pillay-Esnault, and Laurent Viennot for their contributions to this
 document.

Appendix D. Acknowledgments

 The authors would like to thank Juan Antonio Cordero Fuertes, Ulrich
 Herberg, and Richard Ogier for reviewing this document.

Baccelli, et al. Experimental [Page 30] RFC 5449 OSPF MPR Extension for MANET February 2009

Authors' Addresses

 Emmanuel Baccelli
 INRIA
 Phone: +33 1 69 33 55 11
 EMail: Emmanuel.Baccelli@inria.fr
 URI:   http://www.emmanuelbaccelli.org/
 Philippe Jacquet
 INRIA
 Phone: +33 1 3963 5263
 EMail: Philippe.Jacquet@inria.fr
 Dang-Quan Nguyen
 CRC
 Phone: +1-613-949-8216
 EMail: dang.nguyen@crc.ca
 Thomas Heide Clausen
 LIX, Ecole Polytechnique
 Phone: +33 6 6058 9349
 EMail: T.Clausen@computer.org
 URI:   http://www.thomasclausen.org/

Baccelli, et al. Experimental [Page 31]

/data/webs/external/dokuwiki/data/pages/rfc/rfc5449.txt · Last modified: 2009/02/09 23:14 by 127.0.0.1

Donate Powered by PHP Valid HTML5 Valid CSS Driven by DokuWiki