[Docs] [txt|pdf] [Tracker] [WG] [Email] [Diff1] [Diff2] [Nits]

Versions: 00 01 02 03 04 RFC 5449

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


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

Status of 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 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, and denoted the "OSPFv3 MANET interface type".

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  3
   3.  Applicability Statement  . . . . . . . . . . . . . . . . . . .  5



Baccelli, et al.        Expires January 11, 2009                [Page 1]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


     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  . . . . . . .  6
     4.4.  MPR Adjacency Reduction  . . . . . . . . . . . . . . . . .  7
   5.  Protocol Details . . . . . . . . . . . . . . . . . . . . . . .  7
     5.1.  Data Structures  . . . . . . . . . . . . . . . . . . . . .  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 . . . . . . . . . . . . . . . . . . .  8
       5.1.4.  Flooding-MPR-selector set  . . . . . . . . . . . . . .  8
       5.1.5.  Path-MPR set . . . . . . . . . . . . . . . . . . . . .  9
       5.1.6.  Path-MPR-selector set  . . . . . . . . . . . . . . . .  9
       5.1.7.  MPR-selector set . . . . . . . . . . . . . . . . . . . 10
       5.1.8.  MPR set  . . . . . . . . . . . . . . . . . . . . . . . 10
     5.2.  Hello Protocol . . . . . . . . . . . . . . . . . . . . . . 10
       5.2.1.  Flooding-MPR Selection . . . . . . . . . . . . . . . . 10
       5.2.2.  Flooding-MPR Selection Signalling - FMPR TLV . . . . . 11
       5.2.3.  Neighbor Ordering  . . . . . . . . . . . . . . . . . . 11
       5.2.4.  Metric Signalling - METRIC TLV and PMPR TLV  . . . . . 11
       5.2.5.  Path-MPR Selection . . . . . . . . . . . . . . . . . . 12
       5.2.6.  Path-MPR Selection Signalling - PMPR TLV . . . . . . . 12
       5.2.7.  Hello Packet Processing  . . . . . . . . . . . . . . . 12
     5.3.  Adjacencies  . . . . . . . . . . . . . . . . . . . . . . . 13
       5.3.1.  Packets over 2-Way Links . . . . . . . . . . . . . . . 13
       5.3.2.  Adjacency Conservation . . . . . . . . . . . . . . . . 13
     5.4.  Link State Advertisements  . . . . . . . . . . . . . . . . 13
       5.4.1.  LSA Flooding . . . . . . . . . . . . . . . . . . . . . 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 TLV . . . . . . . . . . . . . . . . 18
     6.2.  Metric Information TLV . . . . . . . . . . . . . . . . . . 18
     6.3.  Path-MPR Selection TLV . . . . . . . . . . . . . . . . . . 20
   7.  Security Considerations  . . . . . . . . . . . . . . . . . . . 23
   8.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 23
   9.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 23
     9.1.  Normative References . . . . . . . . . . . . . . . . . . . 23
     9.2.  Informative References . . . . . . . . . . . . . . . . . . 24
   Appendix A.  Flooding MPR Selection Heuristic  . . . . . . . . . . 24
   Appendix B.  Path MPR Selection Heuristic  . . . . . . . . . . . . 25
   Appendix C.  Contributors  . . . . . . . . . . . . . . . . . . . . 27
   Appendix D.  Acknowledgments . . . . . . . . . . . . . . . . . . . 27




Baccelli, et al.        Expires January 11, 2009                [Page 2]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


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 with a subset
      of neighbors, for lower database synchronization overhead.

   These mechanisms are based on multipoint relays (MPR), a technique
   developed in 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, whether there are MANET interfaces in the area or not.

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
   [RFC2740], LLS terminology as defined in [RFC4813], and introduces
   the following terminology to the OSPF nomenclature:

   OSPFv3 MANET interface  - the 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 has only OSPFv3 interface of types
      other than OSPFv3 MANET interfaces.







Baccelli, et al.        Expires January 11, 2009                [Page 3]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


   Hybrid router -  a router which 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 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 -  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 hop limit field
      of the protocol packet is greater than one.

   Path-MPR -  A router, which 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 and to the router
      X.

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

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

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

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




Baccelli, et al.        Expires January 11, 2009                [Page 4]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


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
   is 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: 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: if two routers, R1 and R2, each make a
   transmission, each of these transmissions is not guaranteed to be
   received by the same subset of routers within the MANET - and this
   even if each of R1 and R2 can mutually receive transmissions from the
   other.

   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 which 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 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.



Baccelli, et al.        Expires January 11, 2009                [Page 5]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


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

4.  Protocol Overview and Functioning

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

4.1.  Efficient Flooding using MPRs

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

4.2.  MPR Topology Reduction

   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.

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



Baccelli, et al.        Expires January 11, 2009                [Page 6]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


   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 some
   select routers in the MANET (called Synch routers) 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 [RFC2740] and specifies the information that
   must be maintained, processed and transmitted by routers which
   operate one or more OSPFv3 MANET interfaces.

5.1.  Data Structures

   In addition to the values used in [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 [RFC2740],
   routers which operate one or more MANET interfaces make use of the
   data structures described below.

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 records
   tuples of the form:

                    (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.

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







Baccelli, et al.        Expires January 11, 2009                [Page 7]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


5.1.2.  N2: Symmetric strict 2-hop Neighbor Set

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

   (i)    the router performing the computation

   (ii)   all routers in N.

   More precisely, N2 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.

5.1.3.  Flooding-MPR set

   The Flooding-MPR set records router IDs of a subset of the routers
   listed in N, selected such that through this subset, each router
   listed in N2 is reachable in 2 hops by this router.  More precisely,
   the Flooding-MPR set records tuples of the form:

                    (Flooding_MPR_id, Flooding_MPR_time)

   where:

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

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

   Flooding-MPR selection is detailed in Section 5.2.1.

5.1.4.  Flooding-MPR-selector set

   The Flooding-MPR-selector set records router IDs of the set of
   symmetric 1-hop neighbors of this router that have selected this



Baccelli, et al.        Expires January 11, 2009                [Page 8]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


   router as Flooding-MPR.  More precisely, the Flooding-MPR-selector
   set records tuples of the form:

           (Flooding_MPR_SELECTOR_id, Flooding_MPR_SELECTOR_time)

   where:

   Flooding_MPR_SELECTOR_id:  is the router ID of the symmetric 1-hop
      neighbor of this router that has selected this router as Flooding-
      MPR.

   Flooding_MPR_SELECTOR_time:  specifies the time at which the tuple
      expires and MUST be removed from the set.

   Flooding-MPR selection is detailed in Section 5.2.1.

5.1.5.  Path-MPR set

   The Path-MPR set records router IDs of a subset of the routers listed
   in N that provide shortest paths from the members of N2 to this
   router.  More precisely, the Path-MPR set records tuples of the form:

                   (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:  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 that have selected this router as Path-MPR.  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 Path-MPR.





Baccelli, et al.        Expires January 11, 2009                [Page 9]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


   Path_MPR_SELECTOR_time:  specifies the time at which the tuple
      expires and MUST be removed from the set.

   Path-MPR selection is detailed in Section 5.2.5.

5.1.7.  MPR-selector set

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

5.1.8.  MPR set

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

5.2.  Hello Protocol

   On OSPFv3 MANET interfaces, packets are sent, received and processed
   as defined in [RFC2740] and [RFC2328], augmented for MPR selection as
   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 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 which operates at least one



Baccelli, et al.        Expires January 11, 2009               [Page 10]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


   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 taking willingness into account is given in
   Appendix A.

5.2.2.  Flooding-MPR Selection Signalling - FMPR TLV

   A router MUST signal its Flooding-MPRs set to its neighbors, through
   including a 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-MPR, as well as the
   willingness of the sending router to be elected Flooding-MPR by other
   routers.

5.2.3.  Neighbor Ordering

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

   This ordering allows correct interpretation of an included FMPR TLV.

5.2.4.  Metric Signalling - METRIC 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
   interfaces, 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 this routers
   MANET neighbors on the OSPFv3 MANET interface over which the Hello
   packet is sent MUST be signaled through including METRIC TLVs.

   Moreover, the lowest cost from each MANET neighbor towards the router
   (regardless of over which interface) MUST be specified through
   including a PMPR TLV.  Note that the lowest cost can be over an
   interface which is not an OSPFv3 MANET interface.





Baccelli, et al.        Expires January 11, 2009               [Page 11]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


5.2.5.  Path-MPR Selection

   A router which has one or more OSPFv3 MANET interface(s) MUST select
   a Path-MPR set such that shortest paths with respect to the metric in
   use from routers in N2 and to this router have as intermediate
   routers (if any) only routers which are selected as Path-MPR by this
   router.  A heuristic for Path-MPR selection is given in Appendix B

5.2.6.  Path-MPR Selection Signalling - PMPR TLV

   A router MUST signal its Path-MPR set to its neighbors, through
   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:

   1.  Neighbors which are both adjacent AND are selected as Path-MPR
       for any OSPFv3 MANET interface of the router generating the Hello
       packet.

   2.  Neighbors which are adjacent over any OSPFv3 MANET interface of
       the router generating the Hello packet.

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

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

5.2.7.  Hello Packet Processing

   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 when either of N or N2 has
   changed.

   Moreover, 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.







Baccelli, et al.        Expires January 11, 2009               [Page 12]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


5.3.  Adjacencies

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

   Over an OSPFv3 MANET interface, a router MUST bring up adjacencies
   with all MANET neighbors which are included in its MPR set and its
   MPR Selector set.  A router MAY bring up adjacencies with other MANET
   neighbors, at the expense of additional synchronization overhead.

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 SPT will be
   over adjacencies.

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
   which ceases to list this router as being adjacent (see
   Section 5.2.3), the state of that neighbor MUST be changed to (i)
   2-Way if the neighbor is not in the MPR set or the MPR selector set,
   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

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




Baccelli, et al.        Expires January 11, 2009               [Page 13]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


   Routers which have one or more OSPFv3 MANET interface(s) 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 which have one or more OSPFv3 MANET interface(s) MAY list
   other links they have through those OSPFv3 MANET interfaces, at the
   expense of more overhead.

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

   o  a new adjacency has been brought up, reflecting a change in the
      MPR set;

   o  a new adjacency has been brought up, reflecting a change in the
      MPR Selector set;

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

5.4.1.  LSA Flooding

   Link State Updates received on an interface of a type other than
   OSPFv3 MANET interfaces are processed and flooded according to
   [RFC2328] and [RFC2740], 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 [RFC2740], 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 interfaces, the following steps replace
       steps 1 to 5 of section 13.3 of [RFC2328].

       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



Baccelli, et al.        Expires January 11, 2009               [Page 14]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


           Section 5.4.2.

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

       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
              below.

           +  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.

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.




Baccelli, et al.        Expires January 11, 2009               [Page 15]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


   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
           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.

   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:



Baccelli, et al.        Expires January 11, 2009               [Page 16]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


   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 as defined by [RFC2740] and [RFC2328].  Additional
   LLS signaling [RFC4813] is used in HELLO packets sent over OSPFv3
   MANET interfaces, as detailed in this section.

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







Baccelli, et al.        Expires January 11, 2009               [Page 17]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


6.1.  Flooding-MPR Selection TLV

   A TLV of Type FMPR is defined for signaling Flooding-MPR selection,
   shown in Figure 1.

     0                   1                   2                   3
     0 1 2 3 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.












Baccelli, et al.        Expires January 11, 2009               [Page 18]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


     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.







Baccelli, et al.        Expires January 11, 2009               [Page 19]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


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

    Figure 4: Metric  Advertisement TLV (METRIC) example with a single
           and uniform link cost (U=1) (and, hence, no padding).

6.3.  Path-MPR Selection TLV

   A TLV of Type FMPR is defined for signaling Path-MPR selection, shown
   in Figure 1, as well as the link cost associated with these Path-
   MPRs.




















Baccelli, et al.        Expires January 11, 2009               [Page 20]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


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

                Figure 5: Path-MPR Advertisement TLV (PMPR)

   # Adj.  Neigh. -  is an 8 bit unsigned integer field which specifies
      the number of neighbors, starting from the first Neighbor ID in
      the TLV, that are adjacent MANET neighbors.

   # Path-MPR -  is an 8 bit 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 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, set ('1') if the 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 cost for each link from
      each advertised neighbor in the PMPR TLV and to the sending router
      is explicitly included (as shown in Figure 6), set ('1') if a
      single metric value is included which applies to all links (as
      shown in Figure 7).





Baccelli, et al.        Expires January 11, 2009               [Page 21]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


   Neighbor ID -  is a 32 bit field which specifies the router ID of a
      MANET neighbor.

   Cost n -  is a 16 bit unsigned integer field which specifies the cost
      of the link in the direction FROM the nth listed advertised
      neighbor in the PMPR and towards this router.  A default value of
      0xFFFF (i.e. infinity) MUST be advertised, unless information
      received via HELLO packets from the neighbor specifies otherwise,
      in which case the received information MUST be advertised.  If a
      neighbor is reachable via more than one interface, the cost
      advertised MUST be the minimum of the costs by which that neighbor
      can be reached.

   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 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=PMPR          |           Length              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |  # Adj. Neigh |   # Path-MPR  |        Reserved           |0|S|
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                           Neighbor ID                         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                           Neighbor ID                         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    :                                                               :
    :                                                               :
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |             Cost 1            |            Cost 2             |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    :                            .......                            :
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |            Cost n-1           |            Cost n             |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

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







Baccelli, et al.        Expires January 11, 2009               [Page 22]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


     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 a single and uniform
                link cost (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 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

9.1.  Normative References

   [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.

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




Baccelli, et al.        Expires January 11, 2009               [Page 23]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


   [RFC4813]         Zinin, A., Friedman, B., Roy, A., Nguyen, L., and
                     D. Yeung, "OSPF Link Local Signaling", RFC 4813,
                     2007.

9.2.  Informative References

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

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

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

   [MPR]             Qayyum, A., Viennot, L., and A. Laouiti,,
                     "Multipoint Relaying for Flooding Broadcast
                     Messages in Mobile Wireless Networks", Proceedings
                     of HICSS , 2002.

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

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

   [MPR-topology]    Baccelli, E., Clausen,, T., and P. Jacquet,,
                     "Partial Topology in an MPR-based Solution for
                     Wireless OSPF on Mobile Ad Hoc Networks", INRIA
                     Research Report RR-5619, 2005.

Appendix A.  Flooding MPR Selection Heuristic

   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



Baccelli, et al.        Expires January 11, 2009               [Page 24]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


   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



Baccelli, et al.        Expires January 11, 2009               [Page 25]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


   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



Baccelli, et al.        Expires January 11, 2009               [Page 26]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


       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: Emmanuel.Baccelli@inria.fr
   URI:   http://www.emmanuelbaccelli.org/


   Philippe Jacquet
   INRIA

   Phone: +33 1 3963 5263
   EMail: Philippe.Jacquet@inria.fr




Baccelli, et al.        Expires January 11, 2009               [Page 27]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


   Dang-Quan Nguyen
   INRIA

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


   Thomas Heide Clausen
   LIX, Ecole Polytechnique, France

   Phone: +33 6 6058 9349
   EMail: T.Clausen@computer.org
   URI:   http://www.thomasclausen.org/






































Baccelli, et al.        Expires January 11, 2009               [Page 28]

Internet-Draft        OSPF MPR Extension for MANET             July 2008


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.












Baccelli, et al.        Expires January 11, 2009               [Page 29]


Html markup produced by rfcmarkup 1.109, available from https://tools.ietf.org/tools/rfcmarkup/