Open Shortest Path (OSPF)                                    E. Baccelli
Internet-Draft                                                P. Jacquet
Expires: August 10, 2008
Intended status: Experimental                                  D. Nguyen
Expires: January 11, 2009                                          INRIA
                                                              T. Clausen
                                        LIX, Ecole Polytechnique, France
                                                        February 7,
                                                           July 10, 2008

                 OSPF MPR Extension for Ad Hoc Networks
                      draft-ietf-ospf-manet-mpr-00
                      draft-ietf-ospf-manet-mpr-01

Status of this This Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/ietf/1id-abstracts.txt.

   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html.

   This Internet-Draft will expire on August 10, 2008.

Copyright Notice

   Copyright (C) The IETF Trust (2008). January 11, 2009.

Abstract

   This document specifies an OSPFv3 interface type tailored for mobile
   ad hoc networks.  This interface type is derived from the broadcast
   interface type, enhanced with and denoted the "OSPFv3 MANET techniques based on multi-point
   relaying (MPR). interface type".

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  4  3
   3.  Applicability Statement  . . . . . . . . . . . . . . . . . . .  6  5
     3.1.  MANET Characteristics  . . . . . . . . . . . . . . . . . .  5
     3.2.  OSPFv3 MANET Interface Characteristics . . . . . . . . . .  5
   4.  Protocol Overview and Functionning Functioning  . . . . . . . . . . . . . .  7  6
     4.1.  Efficient Flooding with MPR  . using MPRs  . . . . . . . . . . . . . .  7  6
     4.2.  MPR Topology Reduction . . . . . . . . . . . . . . . . . .  7  6
     4.3.  Multicast Transmissions of Protocol Packets  . . . . . . .  7  6
     4.4.  MPR Adjacency Reduction  . . . . . . . . . . . . . . . . .  8  7
   5.  Protocol Details . . . . . . . . . . . . . . . . . . . . . . .  9  7
     5.1.  Data Structures  . . . . . . . . . . . . . . . . . . . . .  9
     5.2.  Hello Protocol  7
       5.1.1.  N: Symmetric 1-hop Neighbor Set  . . . . . . . . . . .  7
       5.1.2.  N2: Symmetric strict 2-hop Neighbor Set  . . . . . . .  8
       5.1.3.  Flooding-MPR set . . . . 11
       5.2.1.  Flooding MPR Selection . . . . . . . . . . . . . . .  8
       5.1.4.  Flooding-MPR-selector set  . 11
       5.2.2.  Flooding MPR Selection Signalling in HELLO Packets . . 11
       5.2.3.  Neighbor Ordering in HELLO Packets . . . . . . . . . . 11
       5.2.4.  Metric Signalling in HELLO Packets .  8
       5.1.5.  Path-MPR set . . . . . . . . . 12
       5.2.5.  Path MPR Selection . . . . . . . . . . . .  9
       5.1.6.  Path-MPR-selector set  . . . . . . 12
       5.2.6.  Path MPR Selection Signalling in HELLO Packets . . . . 12
       5.2.7.  Hello Packet Processing . . . . . .  9
       5.1.7.  MPR-selector set . . . . . . . . . 12
     5.3.  Adjacencies . . . . . . . . . . 10
       5.1.8.  MPR set  . . . . . . . . . . . . . 13
       5.3.1.  Protocol Packets over 2-WAY Links . . . . . . . . . . 13
       5.3.2.  Adjacency Conservation 10
     5.2.  Hello Protocol . . . . . . . . . . . . . . . . 14
     5.4.  Link State Advertisements . . . . . . 10
       5.2.1.  Flooding-MPR Selection . . . . . . . . . . 14
       5.4.1.  LSA Flooding . . . . . . 10
       5.2.2.  Flooding-MPR Selection Signalling - FMPR TLV . . . . . 11
       5.2.3.  Neighbor Ordering  . . . . . . . . . . 14
       5.4.2.  Link State Acknowlements . . . . . . . . 11
       5.2.4.  Metric Signalling - METRIC TLV and PMPR TLV  . . . . . 11
       5.2.5.  Path-MPR Selection . . 15
   6.  Security Considerations . . . . . . . . . . . . . . . . 12
       5.2.6.  Path-MPR Selection Signalling - PMPR TLV . . . 17
   7.  IANA Considerations . . . . 12
       5.2.7.  Hello Packet Processing  . . . . . . . . . . . . . . . 12
     5.3.  Adjacencies  . . 18
   8.  References . . . . . . . . . . . . . . . . . . . . . 13
       5.3.1.  Packets over 2-Way Links . . . . . 22
     8.1.  Normative References . . . . . . . . . . 13
       5.3.2.  Adjacency Conservation . . . . . . . . . 22
     8.2.  Informative References . . . . . . . 13
     5.4.  Link State Advertisements  . . . . . . . . . . . 22
   Appendix A. . . . . . 13
       5.4.1.  LSA Flooding MPR . . . . . . . . . . . . . . . . . . . . . 14
       5.4.2.  Link State Acknowledgments . . . . . . . . . . . . . . 15
     5.5.  Hybrid Routers . . . . . . . . . . . . . . . . . . . . . . 16
     5.6.  Synch Routers  . . . . . . . . . . . . . . . . . . . . . . 17
     5.7.  Routing Table Computation  . . . . . . . . . . . . . . . . 17
   6.  Packet Formats . . . . . . . . . . . . . . . . . . . . . . . . 17
     6.1.  Flooding-MPR Selection Heuristic TLV . . . . . . . . . . 23
   Appendix B.  Path MPR . . . . . . 18
     6.2.  Metric Information TLV . . . . . . . . . . . . . . . . . . 18
     6.3.  Path-MPR Selection Heuristic TLV . . . . . . . . . . . . 25
   Contributors . . . . . . 20
   7.  Security Considerations  . . . . . . . . . . . . . . . . . . . 23
   8.  IANA Considerations  . . 27
   Authors' Addresses . . . . . . . . . . . . . . . . . . . 23
   9.  References . . . . . 28
   Intellectual Property and Copyright Statements . . . . . . . . . . 29

1.  Introduction

   This document specifies an extension of OSPFv3 [2] adapted to MANETs
   [6], based on mechanisms providing:

   - Flooding reduction:  a mechanism reducing the number of
      (re)transmissions during floods.

   - Topology reduction:  a mechanism reducing the number and the size
      of LSAs, by advertizing only a subset of the existing links.

   - Adjacency reduction:  a mechanism reducing the database
      synchronization overhead by bringing . . . . . . . . . . . 23
     9.1.  Normative References . . . . . . . . . . . . . . . . . . . 23
     9.2.  Informative References . . . . . . . . . . . . . . . . . . 24
   Appendix A.  Flooding MPR Selection Heuristic  . . . . . . . . . . 24
   Appendix B.  Path MPR Selection Heuristic  . . . . . . . . . . . . 25
   Appendix C.  Contributors  . . . . . . . . . . . . . . . . . . . . 27
   Appendix D.  Acknowledgments . . . . . . . . . . . . . . . . . . . 27

1.  Introduction

   This document specifies an extension of OSPFv3 [RFC2740] adapted to
   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 LSAs are decreased.

   Adjacency reduction:  adjacencies are brought up only selected adjacencies. with a subset
      of neighbors, for lower database synchronization overhead.

   These mechanisms are based on multipoint relaying relays (MPR), a technique
   developed in OLSR, the proactive routing solution standardized in
   MANET [5] [7]. OLSR [RFC3626].

   The extension specified in this document integrates into the OSPF
   framework by defining an OSPF interface type: the OSPFv3 MANET interface. interface type.  While this
   extension enables OSPF OSPFv3 to function efficiently on mobile ad hoc
   networks, operation of OSPF OSPFv3 on other types of interfaces or
   networks
   networks, or in areas without OSPFv3 MANET interfaces, remains
   unaltered, whether there are MANET interfaces in the area or not.

2.  Terminology

   The keywords 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 [3].

   Additionally, this
   [RFC2119].

   This document uses traditional OSPF terminology as defined in [1] [2], [RFC2328] and
   [RFC2740], LLS terminology as defined in [4], as well as [RFC4813], and introduces
   the following terms: terminology to the OSPF nomenclature:

   OSPFv3 MANET interface  - the OSPF OSPFv3 interface type for MANETs, as
      specified in this document.

   Additionally, the following terms are used in this document:

   MANET router -  a router which has only OSPFv3 MANET interface(s).

   Wired router -  a router which only has OSPF interface(s) only OSPFv3 interface of types
      other than MANET. OSPFv3 MANET interfaces.

   Hybrid router -  a router which has OSPF OSPFv3 interfaces of several
      types, including at least one of the OSPFv3 MANET interface type.

   Neighbor -  a router, reachable through an OSPF OSPFv3 interface (of any
      type).

   MANET neighbor -  a neighbor, reachable through an OSPF interface of
      type MANET. 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 neighbor of the considered router.

   Neighborhood  - the set formed by the symmetric neighbors 1-hop
      neighbor of the
      considered this 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 which brings up adjacencies with all of its
      MANET neighbors.

   Flooding MPR set

   Flooding-MPR -  A router which is selected by its symmetric 1-hop
      neighbor, router X, to retransmit all broadcast protocol packets
      that it receives from router X, provided that that broadcast
      protocol packet is not a duplicate, and that the subset hop limit field
      of symmetric neighbors the protocol packet is greater than one.

   Path-MPR -  A router, which is selected as
      flooding MPR by this router.

   Flooding MPR selector set  - a symmetric 1-hop
      neighbor, X, as being on the subset shortest path from a router in the
      symmetric strict 2-hop neighborhood of router X and to the router
      X.

   Multipoint Relay (MPR) -  A router which is selected by its symmetric neighbors that
      have
      1-hop neighbor as either Flooding-MPR or as Path-MPR, or as both.

   Flooding-MPR Selector -  A router which has selected this its symmetric
      1-hop neighbor, router X, as flooding MPR. one of its Flooding-MPRs is a
      Flooding-MPR selector of router X.

   Path MPR set Selector - the subset of symmetric neighbors  A router which has selected its symmetric 1-hop
      neighbor, router X, as path
      MPR by this router.

   Path MPR one of its Path-MPRs is a Path-MPR selector set  - the subset
      of symmetric neighbors that have
      selected this router as path MPR. X.

   MPR (selector) set Selector - the union  A router which has selected its symmetric 1-hop
      neighbor, router X, as either one of the flooding MPR (selector) set
      and the path (selector) its Flooding-MPRs or as one
      of its Path-MPRs or as both is an MPR set selector of this router. router X.

3.  Applicability Statement

   Characteristics

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

3.1.  MANET Characteristics

   MANETs include [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 "half-broadcast"
   capabilities [9], i.e., interference issues between
   neighbors.

   Moreover, MANETs often exhibit "semi-broadcast" properties: a router
   R that makes a transmission on within a MANET can only assume that
   transmission to be received by a subset of the total number of
   routers attached within that MANET: if two routers, R1 and R2, each make a
   transmission, each of these transmissions is not guaranteed to be
   received by the same subset of routers within the MANET
   will hear - and this transmission.  In particular, these
   even if each of R1 and R2 can mutually receive transmissions from the
   other.

   These characteristics are not compatible incompatible with several traditional OSPF OSPFv3
   mechanisms,
   including some reducing the amount of including, but not limited to, existing mechanisms for
   control traffic, traffic reduction, such as flooding reduction, topology
   reduction and adjacency reduction (e.g.  Designated Router).  However, OSPF's efficient operation over MANETs
   relies on drastic control traffic reduction, as wireless links
   generally feature bandwidth scarcity and interference issues.

   The

3.2.  OSPFv3 MANET Interface Characteristics

   An interface of the OSPFv3 MANET interface type enables OSPF operation on mobile ad hoc
   networks, by providing specific flooding reduction, topology
   reduction and adjacency reduction mechanisms adapted is the point of
   attachment of an OSPFv3 router to a network which may have MANET
   characteristics.  These mechanisms are derived from solutions
   standardized by the MANET working group.  However, while MANET
   standards address optimized ad hoc routing solutions for truely
   mobile enviromnents, OSPF's extension for ad hoc networks addresses
   less mobile scenarios, that possibly include parts  That is, an interface of the network
   that are fixed, using solely the traditional OSPF framework.

4.  Protocol Overview and Functionning

   This document specifies an OSPFv3 MANET interface
   type tailored for mobile
   ad hoc networks: is able to accommodate the MANET interface.

   The characteristics described in
   Section 3.1.  An OSPFv3 MANET interface makes use type is not prescribing a set
   of flooding reduction, topology behaviors or expectations that the network is required to have,
   but rather is setting 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 as described in Section 3.1).  As such, the
   OSPFv3 MANET interface type is a generalization of other OSPFv3
   interface types; for example a protocol operating correctly over an
   OSPFv3 MANET interface would also operate correctly over an OSPFv3
   broadcast interface (whereas the inverse would not necessarily be
   true).

   Efficient OSPFv3 operation over MANETs relies on control traffic
   reduction, and using mechanisms appropriate for semi-broadcast.

   The OSPFv3 MANET interface type, defined in this document, integrates
   support for networks with MANET characteristics into the OSPFv3
   framework by integrating mechanisms (flooding reduction, topology
   reduction and adjacency reduction) derived from solutions
   standardized by the MANET working group.

4.  Protocol Overview and Functioning

   The OSPFv3 MANET interface type, defined in this specification, makes
   use of flooding reduction, topology reduction mechanisms and adjacency
   reduction, all based on multipoint relaying (MPR), (MPR) - a technique
   derived from OLSR [5] [7], the proactive
   routing solution [RFC3626], as standardized in MANET. the MANET working group.
   Moreover, multicast transmissions of protocol packets are used as
   much as possible.

4.1.  Efficient Flooding with MPR using MPRs

   OSPFv3 MANET interfaces use a flooding reduction mechanism called denoted
   MPR
   flooding, flooding [MPR], whereby only some a subset of MANET neighbors (those
   selected as
   flooding-MPR) are responsible for retransmitting a routing packet
   flooded over Flooding-MPR) participate in a MANET interface. flooding operation.  This mechanism drastically
   reduces the number of (re)transmissions during necessary for a flooding procedures,
   operation [MPR-analysis], while
   still providing a natural high retaining resilience to transmission
   errors (inherent to the use of when using wireless links), and obsolete two-hop
   neighbor information (frequently caused by the mobility of the
   routers). routers)
   [MPR-robustness].

4.2.  MPR Topology Reduction

   OSPFv3 MANET interfaces use a topology reduction mechanism called denoted
   MPR topology reduction, whereby only necessary wireless links to MANET
   neighbors (those concerned identified by path-MPR selection, Path-MPR selection as belonging to
   shortest paths) are listed included in LSAs.  Routers in a MANET routers
   periodically generate and flood Router-LSAs describing their
   selection of wireless such links to (current) MANET neighbors their Path-MPRs.  Such links are reported
   as point-to-point links.  This
   mechanism greatly reduces the size of LSAs originated by
   routers on a MANET
   routers, [MPR-topology], while still keeping OSPF's traditional retaining classic OSPF
   properties: optimal paths using synchronized adjacencies.

4.3.  Multicast Transmissions of Protocol Packets

   In order to reduce the overhead, multicast is used as much as
   possible for protocol packet transmissions over

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

4.4.  MPR Adjacency Reduction

   Furthermore,

   Adjacencies over OSPFv3 MANET routers may form adjacencies interfaces are required to be formed
   only with a subset of
   their MANET the neighbors (instead of all of them).  However, no that OSPFv3 MANET interface.
   No Designated Router or Backup Designated Router is are elected on an OSPF
   MANET.  Instead, most
   OSPFv3 MANET routers bring up interface.  Rather, adjacencies are brought up over an
   OSPFv3 MANET interface only with
   their MPR MPRs and MPR selectors, while Selectors.  Only some
   select MANET routers in the MANET (called Synch routers) must 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 only. adjacencies.

5.  Protocol Details

   This section complements [RFC2740] and specifies the information that
   must be maintained, processed and transmitted by routers which
   operate one or more OSPFv3 MANET and hybrid routers, and
   complements RFC 2740 [2]. interfaces.

5.1.  Data Structures

   In addition to the values used in RFC 2740 [2], [RFC2740], the type field in the
   interface data structure can take a new value, "MANET".  Furthermore,
   and in addition to the protocol structures defined by RFC 2740 [2], MANET
   and hybrid [RFC2740],
   routers which operate one or more MANET interfaces make use of the
   data structures described below.

      N :

      the

5.1.1.  N: Symmetric 1-hop Neighbor Set

   The Symmetric 1-hop Neighbor Set records router IDs of the set of
   symmetric 1-hop neighbors of the router.  More precisely, N lists records
   tuples of the form form:

                    (1_HOP_SYM_id,
      1_HOP_SYM_time). 1_HOP_SYM_id 1_HOP_SYM_time)

   where:

   1_HOP_SYM_id:  is the router ID of the symmetric
      neighbor. 1_HOP_SYM_time 1-hop neighbor of
      this router.

   1_HOP_SYM_time:  specifies the time, at which the tuple expires and
      MUST be removed from the set.

      N2 :

      the router IDs of

5.1.2.  N2: Symmetric strict 2-hop Neighbor Set

   The Symmetric strict 2-hop Neighbor Set records links between routers
   in the set of symmetric 1-hop neighbors of and these routers that
      are in N, symmetric 1-hop
   neighbors, excluding:

   (i)    the router performing the computation

   (ii)   all routers in N.

   More precisely, N2 lists records tuples of the form form:

               (2_HOP_SYM_id, 1_HOP_SYM_id, 2_HOP_SYM_time). 2_HOP_SYM_id 2_HOP_SYM_time)

   where:

   2_HOP_SYM_id:  is the router ID of a symmetric 2-hops strict 2-hop neighbor. 1_HOP_SYM_id

   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

   2_HOP_SYM_time:  specifies the time, at which the tuple expires and
      MUST be removed from the set.

5.1.3.  Flooding-MPR set:

      the set

   The Flooding-MPR set records router IDs of a subset of the routers
   listed in N, selected such that through this subset, each router
   listed in N2 is
      reachable.  These neighbors are said to have been "selected as
      flooding MPR" reachable in 2 hops by the this router.  More precisely,
   the Flooding-MPR set
      lists records tuples of the form form:

                    (Flooding_MPR_id, Flooding_MPR_time).
      Flooding_MPR_id Flooding_MPR_time)

   where:

   Flooding_MPR_id:  is the router ID of the symmetric 1-hop neighbor of
      this router, selected as flooding MPR.  Flooding_MPR_time Flooding-MPR.

   Flooding_MPR_time:  specifies the time, at which the tuple expires
      and MUST be removed from the set.  For
      details about MPR selection, see

   Flooding-MPR selection is detailed in Section 5.2. 5.2.1.

5.1.4.  Flooding-MPR-selector set:

      the set

   The Flooding-MPR-selector set records router IDs of the set of
   symmetric 1-hop neighbors of this router that have selected the this
   router as flooding MPR. Flooding-MPR.  More precisely, the Flooding-MPR-selector
   set lists records tuples of the form form:

           (Flooding_MPR_SELECTOR_id,
      Flooding_MPR_SELECTOR_time).  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 the this router as flooding Flooding-
      MPR.  Flooding_MPR_SELECTOR_time

   Flooding_MPR_SELECTOR_time:  specifies the time at which the tuple
      expires and MUST be removed from the set.  For
      details about Flooding MPR selection, see

   Flooding-MPR selection is detailed in Section 5.2. 5.2.1.

5.1.5.  Path-MPR set:

      the set

   The Path-MPR set records router IDs of a subset of the routers listed
   in N that provide shortest paths from the members of N2 to the router.  These
      neighbors are said to have been "selected as path MPR" by the this
   router.  More precisely, the Path-MPR set lists records tuples of the form form:

                   (Path_MPR_id, Path_MPR_time).  Path_MPR_id Path_MPR_time)

   where:

   Path_MPR_id:  is the router ID of the symmetric 1-hop neighbor of
      this router, that is selected as path MPR.  Path_MPR_time Path-MPR.

   Path_MPR_time:  specifies the time at which the tuple expires and
      MUST be removed from the set.  For details about path MPR selection, see

   Path-MPR selection is detailed in Section 5.2. 5.2.5.

5.1.6.  Path-MPR-selector set :

      the

   The Path-MPR-selector set records router IDs of the set of symmetric
   1-hop neighbors that have selected the this router as path MPR. Path-MPR.  More
   precisely, the Path-MPR-selector set
      lists records tuples of the form form:

                    (Path_MPR_SELECTOR_id,
      Path_MPR_SELECTOR_time).  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 the this router as path MPR.
      Path_MPR_SELECTOR_time Path-MPR.

   Path_MPR_SELECTOR_time:  specifies the time at which the tuple
      expires and MUST be removed from the set.  For details about path
      MPR selection, see

   Path-MPR selection is detailed in Section 5.2. 5.2.5.

5.1.7.  MPR-selector set

   The MPR-Selector Set is the union of the Flooding-MPR-selector set
   and the Path-MPR-selector set.

5.1.8.  MPR set

   The MPR set is the union of the Flooding-MPR set and the Path-MPR
   set.

5.2.  Hello Protocol

   On OSPFv3 MANET interfaces, packets are sent, received and processed
   as defined by RFC 2740 [2] in [RFC2740] and RFC 2328 [1], with the following
   additions [RFC2328], augmented for MPR selection as described
   detailed in this section.

   All additional signaling for OSPFv3 MANET interfaces is through
   inclusion of TLVs within an LLS block [RFC4813], appended to Hello
   packets.  If an LLS block is not already present, an LLS block MUST
   be created and appended to the Hello packets.

   Hello packets sent over an OSPFv3 MANET interface MUST have the L bit
   of the OSPF Options field set, as per [RFC4813], indicating the
   presence of an LLS block.

   Flooding-MPR selection is signaled using TLVs of the type FMPR, Path-
   MPRs using TLVs of the type PMPR and metrics using TLVs of the type
   METRIC.  The layout and internal structure of these TLVs is detailed
   in Section 6.

5.2.1.  Flooding MPR  Flooding-MPR Selection

   The objective of flooding MPR 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 Flooding-MPR "coverage criterion".  The
   flooding MPR
   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 OSPF HELLO
   OSPFv3 Hello packets.

   Flooding MPRs

   Flooding-MPRs are computed by each router which operates at least one
   OSPFv3 MANET or hybrid router. interface.  The smaller the flooding MPR Flooding-MPR set is, the
   lower the overhead will be.  However, while it is not essential that
   the flooding MPR Flooding-MPR set is minimal, it is essential that all 2-hop neighbors can the "coverage criterion" MUST be reached
   through
   satisfied by the selected flooding MPR routers.  A router MUST select Flooding-MPR set.

   The willingness of a
   flooding MPR set such that any 2-hop neighbor is covered by at least
   one flooding MPR router.

   Flooding MPR selection priority may router to act as Flooding-MPR MAY be
   taken into consideration by a heuristic for Flooding-MPR selection.
   An example heuristic taking willingness into account is given to neighbor routers in
   descending order of their willingness to flood traffic on behalf of
   other routers.
   Appendix A gives a heuristic for flooding MPR
   selection. A.

5.2.2.  Flooding MPR  Flooding-MPR Selection Signalling in HELLO Packets - FMPR TLV

   A router that has selected flooding MPRs among its neighbors MUST signal this selection through appending LLS information (TLV type 3)
   at the end of its HELLO packets as described Flooding-MPRs set to its neighbors, through
   including a FMPR TLV in Section 7.  This
   information generated Hello packets.  Inclusion of this
   FMPR TLV signals the list of symmetric 1-hop neighbors that the
   sending router has selected as
   flooding MPR, and Flooding-MPR, as well as the
   willingness of the sending router to be flooding
   traffic on behalf of elected Flooding-MPR by other
   routers.

5.2.3.  Neighbor Ordering in HELLO Packets

   Neighbors listed in the HELLO Hello packets sent over OSPFv3 MANET
   interfaces MUST be listed such that symmetric 1-hop neighbors are
   listed before all other neighbors.  Moreover,  Additionally, symmetric 1-hop
   neighbors selected as flooding MPR Flooding-MPRs MUST be listed before all other
   symmetric 1-hop neighbors.

   This specific ordering
   corresponds with LLS information (TLV type 3) appended to the HELLO
   packet, as described in Section 7. allows correct interpretation of an included FMPR TLV.

5.2.4.  Metric Signalling in HELLO Packets

   HELLO - METRIC TLV and PMPR TLV

   Hello packets sent over OSPFv3 MANET interfaces MUST advertize advertise the
   costs of links towards ALL its the symmetric MANET neighbors. neighbors of the
   sending router.  If the sending router has
   several more than one OSPFv3 MANET
   interfaces, links to ALL the symmetric MANET neigbors neighbors over ALL the
   OSPFv3 MANET interfaces of the that router MUST have their costs
   listed.

   Link costs are signalled along Hello packets by appending LLS blocks
   at the end of these packets.
   advertised.

   The costs of the links from between the router
   towards and each of this routers
   MANET neighbor neighbors on the OSPFv3 MANET interface over which is sent the Hello
   packet is sent MUST be specified using the type 4 TLV described in
   Section 7. signaled through including METRIC TLVs.

   Moreover, the lowest cost from each MANET neighbor towards the router
   (regardless of over which interface) MUST be specified using the type 5 TLV described in Section 7. through
   including a PMPR TLV.  Note that the lowest cost MAY can be over a non-MANET an
   interface which is not an OSPFv3 MANET interface.

5.2.5.  Path MPR  Path-MPR Selection

   Using the LLS metric information included in HELLO packets, a MANET

   A router which has one or more OSPFv3 MANET interface(s) MUST identify select
   a subset of its links to neighbors Path-MPR set such that are on shortest paths with respect to the metric in use.  This mechanism is
   called Path MPR selection.  Appendix B gives a heuristic for path MPR
   selection.

   Hybrid
   use from routers MUST select ALL their MANET in N2 and hybrid neighbors to this router have as
   path MPRs.  MANET intermediate
   routers MAY select a subset of MANET neighbors (if any) only routers which are selected as
   path MPR.  However a MANET router MUST ensure that Path-MPR by this
   router.  A heuristic for each element
   of N or N2 that Path-MPR selection is not given in the path MPR set, there exists a shortest
   path that goes from this element to the router through a neighbor
   selected as path MPR (unless the shortest path is only one hop, of
   course). Appendix B

5.2.6.  Path MPR  Path-MPR Selection Signalling in HELLO Packets - PMPR TLV

   A router that has selected path MPRs among its neighbors MUST signal
   this selection through appended LLS information (TLV type 5) at the
   end of its HELLO packets as described Path-MPR set to its neighbors, through
   including a PMPR TLV in Section 7.  This information
   signals the 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 has selected as path MPR.
   Neighbors listed router.  These IDs
   MUST be included in the PMPR TLV type 5 MUST be listed such that in the order as given below:

   1.  Neighbors which are both adjacent
   neighbors AND are listed before other neighbors.  Moreover, neighbors selected as path MPR MUST be listed before other adjacent neighbors.

5.2.7.  Hello Packet Processing

   In addition to Path-MPR
       for any OSPFv3 MANET interface of the processing specified by RFC 2740 [2], N and N2
   MUST be updated when received HELLO packets signal changes in router generating the
   neighborhood of a Hello
       packet.

   2.  Neighbors which are adjacent over any OSPFv3 MANET interface.  The flooding MPR set and interface of
       the path
   MPR set router generating the Hello packet.

   3.  Symmetric 1-hop neighbors on any OSPFv3 MANET interface of the
       router generating the Hello packet, which have not been
       previously included in this PMPR TLV.

   The list of neighbor IDs is followed by a list of costs for the links
   from these neighbors and to the router generating the Hello packet
   containing this PMPR TLV, as detailed in Section 5.2.4.

5.2.7.  Hello Packet Processing

   In addition to the processing specified in [RFC2740], N and N2 MUST
   be updated when received Hello packets indicate changes to the
   neighborhood of an OSPFv3 MANET interface.  The Flooding-MPR set and
   the Path-MPR set MUST then be recomputed if when either of N or N2 have has
   changed.

   Moreover, the flooding MPR Flooding-MPR selector set and the path MPR Path-MPR selector set
   MUST be updated upon receipt of a HELLO Hello packet containing LLS
   information signalling change indicating changes in the list of neighbors that has
   selected the router as MPR.

5.3.  Adjacencies

   When adjacencies

   Adjacencies are brought up between OSPFv3 MANET and hybrid neighbors,
   procedure goes on interfaces as defined
   described in RFC 2740 [2] [RFC2740] and RFC 2328 [1]. [RFC2328].  However, in order to further reduce
   the control traffic overhead on over the wireless medium, OSPFv3 MANET routers interfaces, a
   router which has one or more such OSPFv3 MANET interface(s) MAY bring
   up adjacencies with a only subset of their its MANET or hybrid neighbors.

   Over a an OSPFv3 MANET interface, a router MUST bring up adjacencies
   with the all MANET neighbors it has which are included in its MPR set and its
   MPR Selector set.

   Some routers (called synch routers) MUST bring up adjacencies with
   other MANET neighbors as well.  Other routers  A router MAY bring up adjacencies with MANET neighbors other than MPRs and MPR selectors, MANET
   neighbors, at the expense of more synchronisation additional synchronization overhead.  The proposed
   heuristic for routers to decide whether they are

5.3.1.  Packets over 2-Way Links

   When a synch router is as
   follows:

   o does not form a MANET router decides it is full adjacency with a synch router if and only if MANET neighbor,
   the state of that neighbor does not progress beyond 2-Way (as defined
   in [RFC2328]).  A router has can send protocol packets, such as LSAs, to
   a higher ID than any other ID present MANET neighbor in Hello packets
      or Router-LSAs it has received from other reachable routers in the
      area.

   Other algorithms are possible.  However, algorithms MUST ensure that
   if there are no hybrid routers in the MANET, at least one router in
   the MANET selects itself as synch router.  Moreover, a MANET router
   that selects itself as synch router MUST signal this by setting the S
   bit in the TLV type 5 appended to the Hello packets it generates, as
   described in Section 7.

5.3.1.  Protocol Packets over 2-WAY Links

   When a router does not form a FULL adjacency with a MANET neighbor,
   the state does not progress beyond 2-WAY (as defined in RFC 2740 [2]
   and RFC 2328 [1]).  A MANET interface MAY send routing protocol
   packets while in 2-WAY 2-Way state.  Therefore, any routing protocol packet received from
   a symmetric MANET neighbor MUST be processed.  Similar to

   As with the OSPF broadcast interface [1], [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 SPT will be
   over adjacencies.

5.3.2.  Adjacency Conservation

   Adjacencies are torn down as defined in RFC 2740 [2] and RFC 2328
   [1].  This means that when 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 this that neighbor is kept,
   unless it is no longer 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
   which
   cease ceases to list the this router as being adjacent (see
   Section 5.2.3), the state of this that neighbor MUST be changed to (i) 2-WAY
   2-Way if the neighbor is not in the MPR set or the MPR selector set,
   or (ii) ExStart if the neighbor is in the MPR set or the MPR selector
   set, or if the neighbor or the router itself is a synch router.

5.4.  Link State Advertisements

   The

   Routers generate Router-LSAs originated by a hybrid router list adjacencies over
   interfaces other than MANET as specifed periodically, using the format specified
   in RFC 2740 [2] and RFC 2328
   [1].  Hybrid [RFC2740] and [RFC2328].

   Routers which have one or more OSPFv3 MANET routers interface(s) MUST list include
   the following links in the Router-LSAs that they
   originate the generate:

   o  links to all neighbors that are in the Path-MPR set; AND

   o  links to all neighbors that are in their Path MPR set
   and their Path MPR the Path-MPR Selector set.

   Routers which have one or more OSPFv3 MANET routers interface(s) MAY list
   other links they have through those OSPFv3 MANET interfaces, to at the
   expense of more overhead.

   Hybrid and MANET

   In addition, routers which have one or more OSPFv3 MANET interface(s)
   MUST flood generate updated Router-LSAs when either of the following
   occurs:

   o  a new adjacency has been brought up up, reflecting a change in the
      MPR set (or
   the MPR Selector set), and when set;

   o  a neighbor formerly listed in
   originated LSAs is no longer new adjacency has been brought up, reflecting a change in the
      MPR Selector set;

   o  a formerly adjacent and advertised neighbor ceases to be adjacent.

5.4.1.  LSA Flooding

   LSUpdates

   Link State Updates received on an interface of a type other than
   OSPFv3 MANET interfaces are processed and flooded as specified in [1] according to
   [RFC2328] and [2], [RFC2740], over every interface.  If an LSUpdate a Link State
   Update was received on a an OSPFv3 MANET interface, it is processed as follows, with regards to flooded LSAs.
   follows:

   1.  Consistency checks are made performed on the received packet, as specified
       in [1] and [2], before being handed packet according
       to the procedure described in
       the following steps, [RFC2328] and [RFC2740], and the Link State Update packet is
       thus associated with a particular neighbor and a particular area.

   2.  If the LSU Link State Update was received from a router other than a
       symmetric 1-hop neighbor, the LSUpdate Link State Update MUST be discarded
       without further processing.

   3.  Otherwise, for each LSA contained in LSUpdates Link State Updates received on
       over an OSPFv3 MANET interfaces, the following steps replace
       steps 1 to 5 of section 13.3 of [1]. [RFC2328].

       1.  If there exists an LSA exists in the Link State Database, with the same
           Link State ID, LS Type and Advertizing Advertising Router values as the
           received LSA, and if the received LSA is not newer (see
           section 13.1 of [1]) [RFC2328]), then the received LSA MUST not NOT be
           processed EXCEPT for acknowledgement acknowledgment as described in section
           5.4.
           Section 5.4.2.

       2.  Otherwise, the LSA MUST be attributed a scope according to
           its type, as specified in section 3.5 of [2]. [RFC2740].

       3.  If the scope of the LSA is link local or reserved, the LSA
           MUST not 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
              below.

           -

           +  Otherwise, the LSA MUST be flooded on all the OSPFv3
              interfaces of the router according to the default flooding
              algorithm described below. in Section 5.4.1.1.

5.4.1.1.  Default LSA Flooding Algorithm

   The default LSA flooding algorithm is then the following: as follows:

   1.  The LSA MUST be installed in the Link State Database.

   2.  The Age of the LSA is MUST be increased by InfTransDelay.

   3.  The LSA is flooded MUST be retransmitted over all OSPFv3 interfaces of type types
       other than MANET. OSPFv3 MANET Interface.

   4.  If the sender sending OSPFv3 interface address is an interface address of an
       flooding MPR a Flooding-MPR selector of
       this router, then the LSA MUST also be retransmitted out 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 MANET dynamic topologies: LSA updating may need to be more frequent in
   MANET parts of the an OSPF network than in traditional other parts of the an OSPF
   network.

5.4.2.  Link State Acknowlements Acknowledgments

   When a router receives an LSA on a over an OSPFv3 MANET interface, the
   router MUST proceed to acknowledge the LSA as follows 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 database Link State Database (i.e. the LSA
       has already been received and processed) processed), then the router MUST
       send an acknowledgement 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 database: 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
           acknowledgement.
           acknowledgment.

       2.  Otherwise, if the router decides to not retransmit the LSA
           (as part of the flooding procedure), the router MUST send an
           acknowledgement
           acknowledgment for this LSA on all OSPFv3 MANET interfaces,
           to the multicast address all_SPF_Routers.

   If a router sends an LSA on a an OSPFv3 MANET interface, it expects
   acknowledgements
   acknowledgments (explicit or implicit) from each all adjacent neighbors.
   In the case where the router did not originate the LSA (i.e. relays generate, but simply relays, the LSA),
   LSA, then the router MUST only expect acknowledgements 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, the then that router retransmits MUST
   retransmit the LSA.

   If, due to efficient the MPR flooding procedure decision, 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 acknowledgements acknowledgments of
   that 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 acklnowledged acknowledged the LSA, then the router
   retransmits MUST
   retransmit the LSA.

   Note that it may be beneficial to aggregate several acknowledgements acknowledgments
   in the same transmission, taking advantage of multicasting. native multicasting (if
   available).  A timer wait MAY thus be used before any acknowledgement transmission in
   order to avoid multiple OSPF acknowledgement transmissions.

   Additional acknowledgment
   transmission.

   Additionally, jitter delay in [RFC5148] on packet (re)transmission may MAY be used
   in order to increase the opportunities to bundle several packets
   together per transmission (which provides a reduction in the number
   of overall transmissions, and therefore the number of collisions over
   the wireless media).

6.  Security Considerations

   This document does currently not specify security considerations.

7.  IANA Considerations

   This document defines the new TLV types below, each transmission.

5.5.  Hybrid Routers

   In addition to be allocated by
   IANA.

   OSPF packets sent by MANET the operations described in Section 5.2, Section 5.3
   and Section 5.4, hybrid routers MUST:

   o  select ALL their MANET and hybrid neighbors as Path-MPRs.

   o  list adjacencies over OSPFv3 interfaces of types other than OSPFv3
      MANET interface, as specified in [RFC2740] 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  bring up adjacencies with ALL MANET neighbors

   A proposed heuristics for selection of Sync routers is as follows:

   o  A router which has a MANET interface and an ID that is higher than
      the ID of all of its current neighbors, and whose ID is higher
      than any other ID present in Router-LSAs currently in its link
      state Link State Database selects itself as synch router.

   Other heuristics are possible, however any heuristic for selecting
   Synch routers MUST ensure the presence of at least one sync or hybrid
   router in the network.

5.7.  Routing Table Computation

   When routing table (re)computation occurs, in addition to the
   processing of the Link State Database defined in [RFC2740] and
   [RFC2328], routers which have one or more MANET interfaces MAY
   include links between themselves and MANET neighbors that are in
   state 2-Way or higher (as data and protocol packets may be sent,
   received and processed over these links too).

6.  Packet Formats

   OSPFv3 packets are formated as defined by RFC2740 [2] [RFC2740] and RFC2328 [1].  The [RFC2328].  Additional
   LLS extension [4] signaling [RFC4813] is used in HELLO packets sent over OSPFv3
   MANET interfaces, as follows.

   The Hello packets sent over an OSPF MANET interface have the L bit
   set.  An LLS datablock containing flooding MPR selection information detailed in this section.

   This specification uses network byte order (most significant octet
   first) for all fields.

6.1.  Flooding-MPR Selection TLV

   A TLV of Type FMPR is appended to these Hello messages.  The 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. |    # MPR      |    Reserved   |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

              Figure 1: Flooding-MPR Advertisement TLV (FMPR)

   where:

   Willingness -  is an 8 bit unsigned integer field which 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 which specifies
      the number of symmetric 1-hop neighbors, listed first among the
      neighbors in a HELLO packet.

   # MPR -  is an 8 bit unsigned integer field which specifies the
      number of neighbors selected as MPR.  These MPRs are listed first
      among the symmetric 1-hop neighbors on this OSPFv3 MANET interface
      in a HELLO packet.

   Reserved -  is an 8 bit field which SHOULD be cleared ('0') on
      transmission and SHOULD be ignored on reception.

6.2.  Metric Information TLV

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

     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        |           Length              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |         Reserved          |U|R|           Cost 0              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |           Cost 1              |           Cost 2              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    :                                                               :
    :                                                               :
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |           Cost n              |            Padding            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

               Figure 2: Metric  Advertisement TLV (METRIC).

   where:

   Reserved -  is a 14 bit field which 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), set ('1') if the costs advertised are reverse (i.e.
      the costs of the links from the neighbors to the router).

   U -  is a binary flag, cleared ('0') if each the cost for each link
      from the sending router and to each advertised neighbor is
      explicitly included (shown in Figure 3), set ('1') if a single
      metric value is included which applies to all links (shown in
      Figure 4).

   Cost n -  is an 8 bit unsigned integer field which specifics the cost
      of the link, in the direction as specified by the R flag, between
      this router and the neighbor listed at the n-th position in the
      Hello packet, when counting from the beginning of the Hello packet
      and with the first neighbor being at position 0.

   Padding -  is a 16 bit field which SHOULD be cleared ('0') on
      transmission and SHOULD be ignored on reception.  Padding is
      included in order that the TLV is 32bit aligned.  Padding MUST be
      included when the TLV contains an even number of Cost fields, and
      MUST NOT be included otherwise.

     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        |           Length              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |         Reserved          |0|R|           Cost 0              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |           Cost 1              |           Cost 2              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

    Figure 3: Metric  Advertisement TLV (METRIC) example with explicit
    individual link costs (U=0) and an odd number of Type 3 is defined as
   the flooding MPR selection TLV type shown in Fig. 1. 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=3            Type=METRIC        |           Length              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |  Willingness  | # Sym. Neigh. |    # MPR      |         Reserved          |1|R|           Cost                |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                 Fig. 1 : Flooding MPR advertisement (TLV type 3)

      Willingness

      This field specifies the willingness of the router to flood link
      state information on behalf of other routers.  It can be set to
      any integer value from 1 to 6.  By default, a router SHOULD
      advertise a willingness of WILL_DEFAULT = 3.

      # Sym. Neigh.

      Number of symmetric neighbors, listed first among the neighbors in
      a HELLO packet.

      # MPR

      Number of neighbors, listed first among the symmetric neighbors on
      this interface in

    Figure 4: Metric  Advertisement TLV (METRIC) example with a HELLO packet, that are selected by the router
      as flooding MPR.

      Reserved

      This 8 bits long field is set to 0 by the sender single
           and ignored by
      the receiver.

   An LLS datablock containing metric information is also appended to
   Hello messages over MANET interfaces.  The uniform link cost (U=1) (and, hence, no padding).

6.3.  Path-MPR Selection TLV

   A TLV of Type 4 FMPR is defined
   as the metric TLV type for signaling Path-MPR selection, shown
   in Fig. 2. 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=4            Type=PMPR          |           Length              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |  # Adj. Neigh |   # Path-MPR  |        Reserved            |R|           Cost 1           |U|S|
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                           Neighbor ID                         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                           Neighbor ID                         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    :                                                               :
    :                                                               :
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |             Cost 2 0            |            Cost 3 1             |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    :                                                               :
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                 Fig. 2
    : metric advertisement (TLV type 4)

      Reserved

      This 15 bits long field                                                               :
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |             Cost n            |            Padding            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                Figure 5: Path-MPR Advertisement TLV (PMPR)

   # Adj.  Neigh. -  is set to 0 by an 8 bit unsigned integer field which specifies
      the sender and ignored by number of neighbors, starting from the receiver.

      R first Neighbor ID in
      the TLV, that are adjacent MANET neighbors.

   # Path-MPR -  is an 8 bit

      This unsigned integer field which specifies the
      number of MANET neighbors, starting from the first Neighbor ID,
      that are selected as Path-MPRs.

   Reserved -  is an 14 bit field which SHOULD be cleared ('0') on
      transmission and SHOULD be ignored on reception.

   S -  is set to 0 a binary flag, cleared ('0') if the costs advertized router brings up
      adjacencies only with neighbors in its MPR set and MPR selector
      set as per Section 5.3, set ('1') if the TLV are direct
      costs (i.e. the costs of router brings up
      adjacencies with all neighbors as a Synch router -- as per
      Section 5.6.

   U -  is a binary flag, cleared ('0') if the links cost for each link from
      each advertised neighbor in the router PMPR TLV and to the
      neighbors).  If this bit sending router
      is explicitly included (as shown in Figure 6), set ('1') if a
      single metric value is included which applies to 1, the costs advertized all links (as
      shown in Figure 7).

   Neighbor ID -  is a 32 bit field which specifies the
      TLV are reverse costs (i.e. the costs router ID of the links from the
      neighbors to the router). a
      MANET neighbor.

   Cost n

      The -  is a 16 bit unsigned integer field which specifies the cost
      of the link in the direction FROM the nth listed advertised
      neighbor in the PMPR and towards this router.  A default value of
      0xFFFF (i.e. infinity) MUST be advertised, unless information
      received via HELLO packets from the neighbor listed specifies otherwise,
      in n-th position 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 which SHOULD be cleared ('0') on
      transmission and SHOULD be ignored on reception.  Padding is
      included in order that the Hello packet.

   In addition to metric and flooding MPR TLVs, HELLO packets contain an
   appended path MPR selection TLV defined as is 32bit aligned.  Padding MUST be
      included when the TLV type 5 shown below
   in Fig. 3. contains an odd number of Cost fields, and
      MUST NOT be included otherwise.

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |            Type=5            Type=PMPR          |           Length              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |  # Adj. Neigh |   # Path MPR Path-MPR  |        Reserved             |S|           |0|S|
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                           Neighbor ID                         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                           Neighbor ID                         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    :                                                               :
    :                                                               :
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |             Cost 1            |            Cost 2             |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    :                            .......                            :
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                 Fig. 3 : path MPR advertisement (TLV type 5)

      # Adj. Neigh

      Number of neighbors, listed first in the TLV, that are adjacent
      MANET neighbors.

      # Path MPR

      Number of blocks neighbors listed first among the adjacent MANET
      neighbors, that are selected as path MPRs by the router.

      Reserved

      This field is 15 bits long and must be set to 0 to be in
      compliance with this specification.

      S bit

      This bit is set to 1 if the router decides it is a synch router.
      Otherwise it is set to 0.

      Neighbor ID

      This field specifies the router ID of a MANET neighbor.
    |            Cost n-1           |            Cost n

      This field specifies the cost of the link going from the neighbor             |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Figure 6: Path-MPR Advertisement TLV (PMPR) with explicit individual
       link costs (U=0) and an even number of Cost fields (hence, no
                                 padding).

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |            Type=5             |           Length              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |  # Adj. Neigh |   # Path-MPR  |        Reserved           |1|S|
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                           Neighbor ID                         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                           Neighbor ID                         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |             Cost              |            Padding            |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   Figure 7: Path-MPR Advertisement TLV (PMPR) with ID listed in n-th position in this TLV, towards the router.
      By default it is set to 0xFFFF (maximal value, i.e. infinity),
      unless information received via HELLO packets from the neighbor
      specifies otherwise.  If a neighbor is reachable through several
      interfaces at the same time, the advertized single and uniform
                link cost is set to the
      minimum (U=1) (hence, padding included).

7.  Security Considerations

   This document does currently not specify security considerations.

8.  IANA Considerations

   This document defines three LLS TLVs, allocation of type values for
   which are requested from the costs over these different interfaces.

8. LLS TLV type registry defined [RFC4813].

                 +----------+------------+--------------+
                 | Mnemonic | Type Value | Name         |
                 +----------+------------+--------------+
                 |   FMPR   |     tbd    | Flooding-MPR |
                 |  METRIC  |     tbd    | Metric       |
                 |   MMPR   |     tbd    | Path-MPR     |
                 +----------+------------+--------------+

                     Table 1: LLS TLV Type Assignments

9.  References

8.1.

9.1.  Normative References

   [1]

   [RFC2119]         Bradner, S., "Key words for use in RFCs to Indicate
                     Requirement Levels", RFC 2119, BCP 14, March 1997.

   [RFC2328]         Moy, J., "OSPF version 2", RFC 2328, 1998.

   [2]

   [RFC2740]         Moy, J., Coltun, R., and D. Ferguson, "OSPF for
                     IPv6", RFC 2740, 1999.

   [3]   Bradner, S., "Key words for use in RFCs to Indicate Requirement
         Levels", RFC 2119, 1997.

   [4]

   [RFC4813]         Zinin, A., Friedman, B., Roy, A., Nguyen, L., and
                     D. Yeung, "OSPF Link Local Signaling", draft-nguyen-ospf-lls-04 (work in
         progress), 2004.

8.2. RFC 4813,
                     2007.

9.2.  Informative References

   [5]   Clausen, T. and P. Jacquet, "The Optimized Link State Routing
         Protocol", RFC 3626, October 2003.

   [6]

   [RFC2501]         Macker, J. and S. Corson, "MANET Routing Protocol
                     Performance Issues and Evaluation Considerations",
                     RFC 2501, January 1999.

   [7]   OLSRv2, Design Team., "OLSR version 2",
         draft-ietf-manet-olsrv2-02 (work

   [RFC3626]         Clausen, T. and P. Jacquet, "The Optimized Link
                     State Routing Protocol", RFC 3626, October 2003.

   [RFC5148]         Adamson, B., Dearlove, C., and T. Clausen, "Jitter
                     Considerations in MANETs", RFC 5148, 2008.

   [MPR]             Qayyum, A., Viennot, L., and A. Laouiti,,
                     "Multipoint Relaying for Flooding Broadcast
                     Messages in progress), June 2006.

   [8] Mobile Wireless Networks", Proceedings
                     of HICSS , 2002.

   [MPR-robustness]  Adjih, C., Baccelli, E., Clausen,, T., and P.
                     Jacquet,, "On the Robustness and Stability of
                     Connected  Dominated Sets", INRIA Research
                     Report RR-5609, 2005.

   [MPR-analysis]    Ngyuen, D. and P. Minet, "Analysis of MPR Selection
                     in the OLSR Protocol", 2nd Int. Workshop on
                     Performance Analysis and Enhancement of Wireless
                     Networks , 2007.

   [9]   Macker, J., Chakeres, I., and T. Clausen, "Mobile Ad hoc
         Network Architecture", ID draft-ietf-autoconf-manetarch,
         February 2007.

   [10]  Adamson, B., Dearlove, C.,

   [MPR-topology]    Baccelli, E., Clausen,, T., and T. Clausen, "Jitter
         Considerations P. Jacquet,,
                     "Partial Topology in MANETs", ID draft-ietf-manet-jitter,
         June 2007. an MPR-based Solution for
                     Wireless OSPF on Mobile Ad Hoc Networks", INRIA
                     Research Report RR-5619, 2005.

Appendix A.  Flooding MPR Selection Heuristic

   The following specifies a proposed heuristic for selection of
   flooding MPRs.  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), defined as the number of neighbors of router y, EXCLUDING all
   the members of N 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, for all routers in N.

   2.  Add to the flooding MPR set those routers in N, which are the
       only routers to provide reachability to a router in N2.  For
       example, if router b in N2 can be reached only through a router a
       in N, then add router a to the flooding MPR set.  Remove the
       routers from N2 which are now covered by a router in the flooding
       MPR set.

   3.  While there exist routers in N2 which are not covered by at least
       one router in the flooding MPR set:

       1.  For each router in N, calculate the reachability, i.e. the
           number of routers in N2 which are not yet covered by at least
           one router in the flooding MPR set, and which are through
           this 1-hop neighbor;

       2.  Select as a flooding MPR the neighbor with highest
           willingness among the routers in N with non-zero
           reachability.  In case of a tie among routers with same
           willingness the router which provides reachability to the
           maximum number of routers in N2.  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 which are now covered by
           a router in the flooding MPR set.

   4.  As an optimization, process each router, y, in the flooding MPR
       set in increasing order of willingness.  If all routers in N2 are
       still covered by at least one router in the flooding MPR set
       excluding router y, then router y MAY be removed from the
       flooding MPR set.

   Other algorithms, as well as improvements over this algorithm, are
   possible.  Different routers may use different algorithms
   independently.  The only requirement is that the algorithm used by a
   given router MUST provide the router with an MPR set that fulfills
   the MPR 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 selection of path
   MPRs.  It constructs 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:

      - The router where the computation is done will be called A.

      - For a router B neighbor of A, cost(A,B) is the cost of the path
      through the direct link, from A to B, and this is an entry in the
      router cost matrix defined below.

      - For a router C in the neighborhood or 2-hop neighborhood of A,
      dist(C,A) is the cost of the shortest path from C to A and this is
      an entry in the router distance vector defined below.

   The cost matrix is populated with the values of the costs of links
   originating from router A (available locally) and by 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 advertized 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 advertized by the Hello packets from B, and respectively,
       the cost (C,B) is set to the value advertised in Hello packets
       from C.

   4.  The coefficients of the cost matrix, cost(B,C) for a link that
       connects a neighbor B to a 2-hop neighbor C is obtained via the
       Hello packets received from router B. In this case cost(B,C) and
       cost(C,B) are respectively set to the values advertized by router
       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 and N2' instead of N2.  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, a MANET router MUST ensure that for each
   element of N or N2 that is not in the path MPR set, there exists a
   shortest path that goes from this element to the router through a
   neighbor selected as path MPR (unless the shortest path is only one
   hop).

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 for his
   reviewing of this document.

Authors' Addresses

   Emmanuel Baccelli
   INRIA

   Phone: +33 1 69 33 55 11
   Email:
   EMail: Emmanuel.Baccelli@inria.fr
   URI:   http://www.emmanuelbaccelli.org/

   Philippe Jacquet
   INRIA

   Phone: +33 1 3963 5263
   Email:
   EMail: Philippe.Jacquet@inria.fr
   Dang-Quan Nguyen
   INRIA

   Phone: +33 1 3963 5511
   Email:
   EMail: Dang-Quan.Nguyen@inria.fr

   Thomas Heide Clausen
   LIX, Ecole Polytechnique, France

   Phone: +33 6 6058 9349
   Email:
   EMail: T.Clausen@computer.org
   URI:   http://www.lix.polytechnique.fr/Labo/Thomas.Clausen/   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.

Acknowledgment

   Funding for the RFC Editor function is provided by the IETF
   Administrative Support Activity (IASA).