Subject: [Ospf-manet] OSPF extension for MANETs

From: Emmanuel Baccelli <[email-masked]>
Date: Mon, 27 Feb 2006 15:08:30 +0100

Hi all,

as discussed, here is a contribution to OSPF extension for MANETs, 
incorporating MPR mechanisms for flooding overhead reduction and 
adjacency reduction.

Emmanuel

Open Shortest Path (OSPF)                                    E. Baccelli
Internet-Draft                                       HITACHI Labs Europe
Expires: August 31, 2006                                      T. Clausen
                                        LIX, Ecole Polytechnique, France
                                                              P. Jacquet
                                                 Project Hipercom, INRIA
                                                       February 27, 2006

                 OSPF MPR Extension for Ad Hoc Networks
                     draft-baccelli-ospf-mpr-ext-00

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 August 31, 2006.

Copyright Notice

   Copyright (C) The Internet Society (2006).

Abstract

   This draft describes an OSPF extension taylored for MANETs.  This
   extension leverages the techniques that were developed by the IETF
   MANET working group.  No currently existing OSPF interface type
   corresponds to MANET characteristics, therefore this extension
   consists in the design of an OSPF interface type, called the OSPF

Baccelli, et al.         Expires August 31, 2006                [Page 1]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

   wireless interface.  OSPF's functionning over the wireless interface
   is inspired from its functionning on broadcast interfaces, which,
   combined with MPR mechanisms from the MANET working group, provides
   for OSPF efficient operation over MANETs.

Table of Contents

   1.  Introduction . . . . . . . . . . . . . . . . . . . . . . . . .  3
   2.  Terminology  . . . . . . . . . . . . . . . . . . . . . . . . .  4
   3.  Applicability Statement  . . . . . . . . . . . . . . . . . . .  5
   4.  Protocol Overview and Functioning  . . . . . . . . . . . . . .  6
   5.  Protocol Details . . . . . . . . . . . . . . . . . . . . . . .  8
     5.1   MPR Selection over OSPF Wireless Interfaces  . . . . . . .  8
       5.1.1   MPR Selection Heuristics . . . . . . . . . . . . . . .  9
       5.1.2   MPR Selection Signalling . . . . . . . . . . . . . . . 10
       5.1.3   MPR Selection Information Repositories . . . . . . . . 11
     5.2   Adjacencies over OSPF Wireless Interfaces  . . . . . . . . 12
     5.3   Flooding Operation over OSPF Wireless Interfaces . . . . . 12
     5.4   Acknowledging over OSPF Wireless Interface . . . . . . . . 14
   6.  Interaction with Other OSPF Interface Types  . . . . . . . . . 17
   7.  Security Considerations  . . . . . . . . . . . . . . . . . . . 18
   8.  IANA Considerations  . . . . . . . . . . . . . . . . . . . . . 19
       Authors' Addresses . . . . . . . . . . . . . . . . . . . . . . 19
   A.  Usage of Link Local Signaling  . . . . . . . . . . . . . . . . 20
     A.1   MPR Selection Signalling with LLS  . . . . . . . . . . . . 21
   B.  References . . . . . . . . . . . . . . . . . . . . . . . . . . 23
   C.  Contributors . . . . . . . . . . . . . . . . . . . . . . . . . 24
       Intellectual Property and Copyright Statements . . . . . . . . 25

Baccelli, et al.         Expires August 31, 2006                [Page 2]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

1.  Introduction

   Mobile Ad hoc Networks (MANETs [3]) have attracted considerable
   attention over the last decade, both in academic and industrial envi-
   ronments.  MANETs were initially designed as networks isolated from
   the Internet (at most, MANETs would be connected via a gateway), and
   the main challenge was that of providing efficient routing within
   these networks, as the new characterics (such as the dynamic topol-
   ogy) implied by ad hoc connectivity made traditional solutions inap-
   propriate.  MANET routing solutions have been the subject of
   intensive attention from the IETF in the recent years, and have been
   exten- sively experimented in various scenarii including actual
   deployments.

   In order to integrate MANET routing with other Internet routing, this
   document specifies a wireless extension for OSPFv3 enabling router ad
   hoc mobility.  In order to guarantee full compatibility with legacy
   OSPF, a natural solution is to base this extension the proactive
   MANET routing approach, since OSPF is itself proactive.  This draft
   therefore introduces a wireless extension for OSPF inspired from the
   proactive MANET routing protocol OLSR [1] [2].  This document speci-
   fies a new OSPF interface, taylored for wireless ad hoc networks: the
   OSPF wireless interface type.

Baccelli, et al.         Expires August 31, 2006                [Page 3]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

2.  Terminology

   The keywords "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
   "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
   document are to be interpreted as described in RFC2119.

   Additionally, this document uses the following terminology:

   o  Node: a device, capable of routing.

   o  Wireless Interface: the OSPF interface type for MANETs, speci-
      fied in this document.

   o  Wireless Node: a node which has only wireless interface(s).

   o  Wired Node: a node which has only traditional OSPF inter- face(s).

   o  Hybrid Node: a node which has both traditional and wireless
      interfaces.

   o  Wireless Neighbor: a neighbor, reachable through a wireless
      interface.

   o  Symmetric Neighbor: a neighbor, in a state greater than or equal
      to ExStart or 2-Way.

   o  Neighborhood of a Node: the set formed by the nodes to which this
      node has a link.

   o  2-Hop Neighborhood of a Node: the set formed by the union of the
      neighborhoods of the neighbors of this node (excluding this node
      itself, and its neighborhood).

   o  Synch Node: a node which brings up adjacencies with all its
      wireless neighbors.

Baccelli, et al.         Expires August 31, 2006                [Page 4]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

3.  Applicability Statement

   This draft describes an extension of the OSPFv3 routing protocol for
   ad hoc networks.  An interface type is designed, adapted to this spe-
   cific network type.  While this extension enables OSPF to function
   efficiently on MANETs, it does not change in any way the functionning
   of OSPF on other types of interfaces or networks.

   The OSPF wireless interface type enables OSPF operation over mobile
   wireless networks, that may partition of merge depending on the
   dynamic topology of routers.

Baccelli, et al.         Expires August 31, 2006                [Page 5]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

4.  Protocol Overview and Functioning

   This section describes an extension to OSPFv3 for MANETs, inspired by
   techniques from OLSR [1] [2].  The wireless interface type, described
   in this document captures the specific characteristics of MANETs,
   sporting "half-broadcast" capabilities (i.e. a node that makes a
   transmission on a MANET can only assume that a subset of the nodes
   attached to the MANET will hear this transmission).

   The OSPF wireless interface's functionning is inspired from how OSPF
   functions on broadcast interfaces, which, combined with MPR mecha-
   nisms, provides for OSPF operation over MANETs.  OSPF operation on
   wireless interace pursues the same goals as on broadcast interfaces:
   reduce the number of superflueous adjacencies, and reduce the number
   of superfluous retransmission of routing packets.

   However, these goals are reached using modified mechanisms with
   regards to flooding, adjacency formation and acknowledging opera-
   tions.  These modifications are effective only in wireless ad hoc
   parts of the OSPF network and does not impact in any way other parts
   of the OSPF network.  OSPF operation remains thus unaltered over
   other types of OSPF interfaces, whether there are OSPF wireless
   interfaces in the network, or not.

   Similarly to OSPF functionning on broadcast networks, nodes will only
   form adjacencies with a subset of its wireless neighbors.  However,
   no Designated Router or Backup Designated Router are elected on an
   OSPF MANET.  Instead, adjacencies are simply formed between MPR and
   MPR Selectors, and only some select nodes (called Synch nodes) bring
   up adjacencies with all their wireless neighbors.  Doing this greatly
   reduces the amount of control traffic needed for OSPF to function,
   while keeping OSPF's traditional properties: robust routing and opti-
   mal paths using synchronized adjacencies.

   Wireless and hybrid nodes periodically generate and flood Router-LSAs
   describing their adjacencies with their wireless neighbors.  Wireless
   adjacencies are advertized as point-to-point links to (current) wire-
   less neighbors.

   Wireless interfaces also enforce efficient flooding.  The goal is the
   same as on broadcast interfaces: to reduce the number of superfluous
   retransmissions.  However the implementation of this semantic on OSPF
   wireless interfaces differs from that on OSPF broadcast interfaces:
   over wireless interfaces, MPR flooding is enforced, i.e. only some
   wireless neighbors (those selected as MPR) are responsible for
   retransmitting a routing packet flooded over a wireless interface.
   MPR flooding is an essential feature for OSPF to function correctly
   in a wireless ad hoc environment.  This technique provides a natural

Baccelli, et al.         Expires August 31, 2006                [Page 6]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

   high resilience to transmission errors (inherent to the use of wire-
   less links), and obsolete two-hop neighbor information (frequently
   caused by the mobility of the nodes).

   Finally, in order to further reduce the number of transmissions over
   wireless interfaces, LSA acknowledgements are sent via multicast over
   these interfaces, and retransmissions over the same interfaces are
   considered as implicit acknowledgements.  Intelligent jitter manage-
   ment delaying packets' (re)transmissions may be used to increase the
   chance to bundle several packets in a single transmission, or to
   avoid superfluous retransmissions.

   The following sections detail these specific mechanisms.

Baccelli, et al.         Expires August 31, 2006                [Page 7]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

5.  Protocol Details

   Each hybrid or wireless node MUST select a subset of its wireless
   neighbors as MPR, and MUST signal MPR selection to its wireless
   neighbors.  Section 5.1 describes MPR selection and signalling in
   details.

   MPR selection is used to determine wether or not to become adjacent
   with a 2-Way neighbor.  MPR selection is also used to determine
   wether or not to retransmit a neighbor node's broadcasts.  This
   technique, inherited from the proactive MANET routing protocol OLSR
   [1], drasti- cally reduces control traffic overhead.

   Adjacency formation is detailed in Section 5.2, before Section 5.3
   details LSA flooding over wireless interfaces, and Section 5.4
   describes how LSA acknowledgement is managed over wireless inter-
   faces.

5.1  MPR Selection over OSPF Wireless Interfaces

   The objective of MPR selection is for a node to select a subset of
   its neighbors such that a packet, retransmitted by these selected
   neighbors, will be received by all nodes 2 hops away.  This property
   is called the MPR coverage criterion.  The MPR set of a node is com-
   puted such that, for each interface, it satisfies this criterion.
   The information required to perform this calculation (i.e. link
   sensing and neighborhood information) is acquired through the
   periodic exchange of OSPF HELLO packets.

   MPRs are computed per wireless interface, by each wireless or hybrid
   node.  The union of the MPR sets of each wireless interface of a node
   make up the MPR set for this node.

   While it is not essential that the MPR set is minimal, it is essen-
   tial that all 2-hop neighbors can be reached through the selected MPR
   nodes.  A node SHOULD select an MPR set such that any 2-hop neighbor
   is covered by at least one MPR node.

   Keeping the MPR set small ensures that the overhead of the protocol
   is kept at a minimum.  However, the MPR set can coincide with the
   entire neighbor set.

   MPR selection priority may be given to neighbor nodes in descending
   order of their willingness to be forwarding traffic on behalf of
   other nodes.

Baccelli, et al.         Expires August 31, 2006                [Page 8]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

5.1.1  MPR Selection Heuristics

   The following specifies a proposed heuristic for selection of MPRs.
   It constructs an MPR-set that enables a node to reach nodes in the
   2-hop neighborhood through relaying by one MPR node.  The heuristic
   should be applied per interface, I. The MPR set for a node is the
   union of the MPR sets found for each interface.  The following termi-
   nology will be used in describing the heuristics:

              Neighbor of an interface:

                    A node is a "neighbor of an interface" if the interface
                    (on the local node) has a link to any one interface of
                    the neighbor node.

             N:
                    N is the set of symmetric neighbors of the node
                    (i.e. neighbors in a state greater than or equal to
                    ExStart or 2-Way), which are neighbor of the
                    interface I.

             N2:
                    The set symmetric neighbors of nodes in N
                    (i.e. 2-hop neighbors), excluding:

                     (i)   the node performing the computation

                     (ii)  all the nodes in N.

             MPR set of an interface I:

                    A (sub)set of the neighbors selected such that
                    through these selected nodes, all the 2-hop neighbors
                    (that are in N2 for interface I) are reachable.

             D(y):
                    The degree of a 1-hop neighbor node y (where y is a
                    member of N), is defined as the number of
                    neighbors of node y, EXCLUDING all the members of N
                    and EXCLUDING the node performing the computation.

   The proposed heuristic can then be described as follows, for each
   wireless interface:

Baccelli, et al.         Expires August 31, 2006                [Page 9]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

           1    Calculate D(y), where y is a member of N, for all nodes
                in N.

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

           3    While there exist nodes in N2 which are not covered by at
                least one node in the MPR set:

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

                3.2  Select as a MPR the neighbor with highest
                     willingness among the nodes in N with non-zero
                     reachability. In case of a tie among nodes with
                     same willingness the node which provides
                     reachability to the maximum number of nodes in N2.
                     In case of another tie between nodes
                     also providing the same amount of reachability,
                     select as MPR the node whose D(y) is greater. Remove
                     the nodes from N2 which are now covered by a node in
                     the MPR set.

           4    A node's MPR set is generated from the union of the MPR
                sets for each interface. As an optimization, process each
                node, y, in the MPR set in increasing order of
                willingness. If all nodes in N2 are still covered by at
                least one node in the MPR set excluding node y, then
                node y MAY be removed from the MPR set.

   Other algorithms, as well as improvements over this algorithm, are
   possible.  Different nodes may use different algorithms
   independently.  The only requirement is that the algorithm used by a
   given node MUST provide the node with an MPR set that fulfills the
   MPR coverage cri- terion.

5.1.2  MPR Selection Signalling

   A node that has selected MPRs among its neighbors MUST signal this
   selection through appending LLS information at the end of its HELLO
   packets as described in Appendix A.  This information signals the
   list of neighbors the node has selected as MPR, and the willingness

Baccelli, et al.         Expires August 31, 2006               [Page 10]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

   of the node to be forwarding traffic on behalf of other nodes.

   Moreover, neighbors listed in the HELLO packets sent over wireless
   interfaces MUST be listed in a specific order: symmetric neighbors
   (i.e. in a state greater than or equal to ExStart or 2-Way) MUST be
   listed first.  The number of symmetric neighbors is also signalled in
   the LLS information appended to the HELLO packet, as described in
   Appendix A.  Any neighbor that is not symmetric (i.e. in a state
   lower than ExStart or 2-Way) MUST be listed after ALL symmetric
   neighbors.

5.1.3  MPR Selection Information Repositories

   Each wireless or hybrid node also maintains a set called the "Wire-
   less 2-Hop Neighbors Set".  This set keeps information about a node's
   symmetric neighbors two hops away.  The set lists tuples
   (2_HOP_SYM_addr, 1_HOP_SYM_addr, LOCAL_if, 2_HOP_SYM_time).
   2_HOP_SYM_addr is the address of a symmetric neighbor 2-hops away.
   1_HOP_SYM_addr is the address of the symmetric neighbor through which
   the 2-hop neighbor can be reached.  LOCAL_if is the address of the
   local interface of the node, through which the 1-hop neighbor can be
   reached. 2_HOP_SYM_time specifies the time at which the tuple expires
   and *MUST* be removed from the set.

   Each wireless or hybrid node maintains a set called the "Wireless
   Neighbors Set".  This set keeps information about a node's symmetric
   neighbors two hops away.  The set lists tuples (1_HOP_SYM_addr,
   LOCAL_if, 1_HOP_SYM_time). 1_HOP_SYM_addr is the address of a symmet-
   ric neighbor of the node.  LOCAL_if is the address of the local
   inter- face of the node, through which the neighbor can be reached.
   1_HOP_SYM_time specifies the time at which the tuple expires and
   *MUST* be removed from the set.

   The wireless neighbors and 2-hop neighbors sets are updated when
   received HELLO packets signal changes in the neighborhood.

   In addition, each wireless or hybrid node maintains a set called the
   "MPR Set".  This set lists the addresses of the neighbors selected as
   MPR by the node.  The MPR set is updated by the algorithm described
   in Section 5.1.1, which is used as soon as the node detects a change
   in its wireless neighbors, or 2-hop neighbors sets.  At the end of
   this procedure new MPRs may be added to the set, and formerly
   selected nodes are removed from the set.

   Similarly, each wireless or hybrid node also maintains a set called
   the "MPR Selector Set".  This set lists tuples (MPRS_addr,
   MPRS_time), describing the neighbors which have selected this node as
   a MPR.  MPRS_addr is the address of a neighbor, which has selected

Baccelli, et al.         Expires August 31, 2006               [Page 11]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

   this node as MPR.  MPRS_time specifies the time at which the tuple
   expires and *MUST* be removed from the set.  The MPR set is updated
   upon receipt of LLS information in which the recipient is listed as
   MPR by the originator of the LLS information.

5.2  Adjacencies over OSPF Wireless Interfaces

   In order to reduce the control traffic overhead on the wireless
   medium, nodes do not bring up adjacencies with all their wireless
   neighbors.  This is similar to broadcast interfaces, over which a
   node forms adjacencies only with the Designated Router and the Backup
   Designated Router.

   Over a wireless interface, a node brings up adjacencies only with the
   neighbors it has included in its MPR set and its MPR Selector set.
   However, some nodes (called synch nodes) bring up adjacencies with
   all their wireless neighbors.  This ensures that the adjacencies over
   the whole OSPF network contain the shortest paths, even with not all
   adjacencies being formed (see [8] [10]).  A node decides it is a
   synch node if and only if:

   o  the node is a hybrid node, OR

   o  the node is a wireless node that has the highest willingness in
      its neighborhood (in case of ties, the node that also has the
      greatest Router ID is elected).

   When a node does not form an adjacency with a wireless neighbor, the
   state of this neighbor will be 2-Way (instead of FULL, for an adja-
   cent neighbor).  Contrary to other types of interfaces, over a wire-
   less interface routing packets may also be sent over 2-Way links.

   Therefore, any routing packet received from a wireless neighbor in a
   state greater than or equal to ExStart or 2-Way MUST be processed.
   Similarly to the broadcast interface, the next hop in the forwarding
   table may be a neighbor that is not adjacent.  However, when a packet
   is further than its first hop, the MPR selection process guarantees
   that the next hop in the SPT will be over an adjacency.

5.3  Flooding Operation over OSPF Wireless Interfaces

   Flooding operation is modified over wireless interfaces.  However,
   note that flooding runs unaltered over all other types of OSPF inter-
   faces.  If an LSU was received on an interface of a type other than
   wireless, its processing and the flooding procedure go on as speci-
   fied in [4] and [6], over every interface (wireless or not).  If an
   LSU was received on a wireless interface, it is processed as follows,
   with regards to flooded LSAs.

Baccelli, et al.         Expires August 31, 2006               [Page 12]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

   Note that, as specified in [4] and [6], consistency checks have been
   made on the received packet before being handed to the modified
   flooding procedure described in the following, and the Link State
   Update packet has thus been associated with a particular neighbor and
   a particular area.

   The principle is that a node A will consider flooding retransmission
   of an LSA it has received on a wireless interface from a neighbor B
   only if node B has signalled an MPR set including node A. If this is
   not the case, node A will suppress its wireless retransmission of
   LSAs flooded by node B (since its retransmissions are superfluous).
   The following details the exact changes to the usual OSPFv3 specifi-
   cations (i.e. section 13.3 of [4] and section 3.5 of [6]) for flood-
   ing decisions on wireless interfaces.

   If the LSU was not received from a neighbor in a state greater than
   or equal to ExStart or 2-Way, the LSU MUST be discarded without fur-
   ther processing.  Else, for each LSA contained in LSUs received on
   wireless interfaces, the following steps replace steps 1 to 5 of sec-
   tion 13.3 of [4].

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

           2    Otherwise, the LSA MUST be forwarded according
                to the scope of the LSA type (see section 3.5 of [6]).

           3    Flooding scope condition:

                3.1  If the scope of the LSA is link local or reserved,
                     the LSA MUST not be forwarded on any interface.

                3.2  Otherwise:

                     3.2.1 If the scope of the LSA is the area, the
                           LSA MUST be forwarded on all the interfaces
                           of the node in that area according to
                           the default forwarding algorithm described
                           below.

                     3.2.2
                          Otherwise, the LSA MUST be forwarded
                          on all the interfaces of the node according
                          to the default forwarding algorithm
                          described below.

Baccelli, et al.         Expires August 31, 2006               [Page 13]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

   The default forwarding algorithm is then the following:

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

           2    The Age of the LSA is increased by InfTransDelay.

           3    The LSA is flooded over all non-wireless interfaces.

           4    If the sender interface address is an interface address of
                an MPR selector of this node, the LSA MUST also be
                retransmitted out all wireless 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 fre-
   quent in MANET parts of the OSPF network than in traditional parts of
   the OSPF network.

5.4  Acknowledging over OSPF Wireless Interface

   When a node receives an LSA on a wireless interface, the node MUST
   proceed to acknowledge the LSA as follows

Baccelli, et al.         Expires August 31, 2006               [Page 14]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

           1    If the LSA is already in the database
                (i.e. the LSA has already been received)
                and it is received from a non-adjacent neighbor,
                the node MUST NOT acknowledge it.

           2    If the LSA is already in the database
                (i.e. the LSA has already been received)
                and it is received from an adjacent neighbor,
                the node MUST send an acknowledgement for
                this LSA on all wireless interfaces, to the
                multicast address all_SPF_Routers.

           3    If the LSA is not already in the database
                (i.e. the LSA has not already been received)
                and it decides to retransmit it
                (as part of the flooding procedure), the
                node MUST NOT acknowledge it, as this
                retransmission will be considered as an
                implicit acknowledgement.

           4    If the LSA is not already in the database
                (i.e. the LSA has not already been received)
                and it decides to not retransmit
                it (as part of the flooding procedure),
                the node MUST send an acknowledgement for
                this LSA on all wireless interfaces, to the
                multicast address all_SPF_Routers.

   If a node sends an LSA on a wireless interface, it expects
   acknowledgements (explicit or implicit) from each adjacent neighbors.
   In the case where the node did not originate the LSA (i.e. relays the
   LSA), the node MUST only expect acknowledgements (explicit or
   implicit) from adjacent neighbors that have not previously
   acknowledged this LSA.  If a node detects that some adjacent neighbor
   has not acknowledged the LSA, the node retransmits the LSA.

   If, due to efficient flooding procedure decision, a node decides to
   not relay an LSA, the node MUST still expect acknowledgements of that
   LSA (explicit or implicit) from adjacent neighbors that have not
   previously acknowledged this LSA.  If a node detects that some
   adjacent neighbor has not aclnowledged the LSA, the node retransmits
   the LSA.

   Note that it may be beneficial to aggregate several acknowledgements
   in the same transmission (taking advantage of the multicasting).  A
   timer wait MAY thus be used before any acknowledgement transmission
   in order to to avoid superfluous retransmissions.

Baccelli, et al.         Expires August 31, 2006               [Page 15]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

   Additional jitter delay in packet (re)transmission 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).

Baccelli, et al.         Expires August 31, 2006               [Page 16]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

6.  Interaction with Other OSPF Interface Types

   OSPF operation remains unaltered over other types of OSPF interfaces,
   wether there are OSPF wireless interfaces in the network, or not.
   The difference in flooding, adjacency formation and acknowledging
   opera- tions described above is effective only in wireless ad hoc
   parts of the OSPF network and does not impact in any way on other
   parts of the OSPF network.

   In wireless ad hoc parts of the OSPF network, routing is performed
   over synchronized adjacencies, as in usual OSPF.  This way, the same
   properties of robusteness (shortest and loop-free paths) are still
   garanteed throughout the whole OSPF network wether there are OSPF
   wireless interfaces in the network, or not.

Baccelli, et al.         Expires August 31, 2006               [Page 17]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

7.  Security Considerations

   This document does currently not specify security considerations.

Baccelli, et al.         Expires August 31, 2006               [Page 18]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

8.  IANA Considerations

   This document does currently not specify IANA considerations.

Authors' Addresses

   Emmanuel Baccelli
   HITACHI Labs Europe

   Phone: +33 1 69 33 55 11
   Email: [email-masked]

   Thomas Heide Clausen
   LIX, Ecole Polytechnique, France

   Phone: +33 6 6058 9349
   Email: [email-masked]
   URI:   http://www.lix.polytechnique.fr/Labo/Thomas.Clausen/

   Philippe Jacquet
   Project Hipercom, INRIA

   Phone: +33 1 3963 5263
   Email: [email-masked]

Baccelli, et al.         Expires August 31, 2006               [Page 19]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

Appendix A.  Usage of Link Local Signaling

   Nodes may set a flag, called L (L for LLS), in the OSPFv3 packets
   Options field (see [6]) which indicates that the packet contains LLS
   data block (see [14]).

   With LLS, nodes may append a data block containing arbitrary informa-
   tion at the end of OSPFv3 packets.  The length of the data block is
   not included in the OSPFv3 packet length field, but is included in
   the IP packet length, as shown below.

                  +---------------------+ --
                ^ | IPv6 Header         | ^
                | | Length = X+Y+Z      | | Z = IPv6 Header Length
                | |                     | v
                | +---------------------+ --
                | | OSPFv3 Header       | ^
                | | Length = X          | |
           IP   | |.....................| | X = OSPF Packet Length
         Packet | |                     | |
                | | OSPFv3 Data         | |
                | |                     | v
                | +---------------------+ --
                | |                     | ^
                | |  LLS Data Block     | | Y = LLS Data Block Length
                V |                     | v
                  +---------------------+

                  Fig. 1 : OSPFv3 and LLS data block in an IPv6 Packet

   In order to provision for different uses of the LLS, the type length
   value (TLV) format is used for the LLS datablock, as shown below in
   Fig. 2 and Fig. 3.  An LLS header (checksum and length of the LLS
   dat- ablock) is followed by a number of TLV blocks.

         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
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |            Checksum           |       LLS Data Length         |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                                                               |
        |                           TLV Blocks                          |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Baccelli, et al.         Expires August 31, 2006               [Page 20]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

                          Fig. 2 : LLS datablock header

         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             |            Length               |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                                                               |
        |                           Value                               |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                          Fig. 3 : TLV Block format

Appendix A.1  MPR Selection Signalling with LLS

   The Hello packets sent over an OSPF wireless interface have the L bit
   set.  An LLS datablock containing MPR selection information is
   appended to these Hello messages.  The TLV of Type 0 is defined as
   the MPR selection TLV type shown in Fig. 4.

         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=0             |           Length              |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |  Willingness  | # Sym. Neigh. |          Reserved             |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
        |                                                               |
        :                                                               :
        |             Addresses of Neighbors Selected as MPR            |
        +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                             Fig. 4 : MPR selection TLV

Baccelli, et al.         Expires August 31, 2006               [Page 21]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

      Willingness:

      This field specifies the willingness of a node to carry and forward
      traffic for other nodes.  It can be set to any integer value from 1
      to 6. By default, a node SHOULD advertise a willingness of
      WILL_DEFAULT = 3.

      # Sym. Neigh. :

      Number of symmetric neighbors, i.e. the number of neighbors, listed
      first in the HELLO packet, that are in a state greater than or equal
      to ExStart or 2-Way. These neighbors are then considered in MPR
      selection mechanisms.

      Reserved:

      This field must be set to "000000000000000000000" to be in compliance
      with this specification.

      Addresses of Neighbors Selected as MPR:

      Concatenation of successive IPv6 addresses of neighbors selected as
      MPR by the node.

Baccelli, et al.         Expires August 31, 2006               [Page 22]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

Appendix B.  References

   [1] T. Clausen, P. Jacquet, RFC 3626: Optimized Link State Routing Pro-
        tocol. 2003.

   [2] OLSRv2 Design Team, Optimized Link State Routing Protocol version 2,
        Internet Draft draft-ietf-manet-olsrv2-00, July 2005.

   [3] S. Corson, J. Macker, RFC 2501: Mobile Ad hoc Networking (MANET),
        Routing Protocol Performance Issues and Evaluation Considerations,
        1999.

   [4] J. Moy, RFC 2328: OSPF version 2, 1998.

   [5] J. Moy, OSPF, Anatomy of an Internet Routing Protocol, Addison-Wes-
        ley, 1998.

   [6] R. Coltun, D. Ferguson, J. Moy, RFC 2740: OSPF for IPv6, 1999.

   [7] E. Baccelli, T. Clausen, P. Jacquet, Ad-hoc and Internet Conver-
        gence: Adapting OSPF-style Database Exchanges for Ad-hoc Networks,
        Proceedings of the Conference on Performance Modelling and Evalua-
        tion of Heterogeneous Networks (HET-NETs), Oct. 2004.

   [8] A. Qayyum, L. Viennot, A. Laouiti, Multipoint Relaying: An Efficient
        Technique for Flooding in Mobile Wireless Networks, INRIA Research
        Report RR-3898, March 2000.

   [9] C. Adjih, P. Jacquet, L. Viennot, Computing Connected Dominating
        Sets with Multipoint Relays, INRIA Research Report RR-4597, 2002.

   [10] P. Jacquet, A. Laouiti, P. Minet, L. Viennot, Performance Evalua-
        tion of Multipoint Relaying in Mobile Ad Hoc Networks, Proceedings
        of the Networking International Conference, 2002.

   [11] J. Ahrenholz, E. Baccelli, T. Clausen, T. Henderson, P. Jacquet, P.
        Spagnolo, OSPFv2 Wireless Interface Type, Internet Draft draft-
        spagnolo-manet-ospf-wireless-interface-01.txt, May 2004.

   [12]  R. Ogier, MANET Extension of OSPF using CDS Flooding, Internet
        Draft draft-ogier-manet-ospf-extension-05, 2005.

   [13] M. Chandra et al. Extensions to OSPF to Support Mobile Ad Hoc Net-
        working, Internet Draft draft-chandra-ospf-manet-ext-03, 2005.

   [14] A. Zinin, B. Friedman, A. Roy, L. Nguyen, D. Yeung, OSPF Link Local
        Signaling, Internet Draft draft-nguyen-ospf-lls-04, 2004.

Baccelli, et al.         Expires August 31, 2006               [Page 23]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

Appendix C.  Contributors

      Cedric Adjih,
      Project HIPERCOM,
      INRIA Rocquencourt,
      BP 105,
      78153 Le Chesnay Cedex, France,
      Phone: +33 1 3963 5263,
      Email: [email-masked]

      Laurent Viennot,
      Project Gyroweb,
      INRIA Rocquencourt,
      BP 105,
      78153 Le Chesnay Cedex, France,
      Phone: +33 1 3963 5263,
      Email: [email-masked]

Baccelli, et al.         Expires August 31, 2006               [Page 24]

Internet-Draft        OSPF MPR Extension for MANET         February 2006

Intellectual Property Statement

   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
   [email-masked].

Disclaimer of Validity

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

Copyright Statement

   Copyright (C) The Internet Society (2006).  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.

Acknowledgment

   Funding for the RFC Editor function is currently provided by the
   Internet Society.

Baccelli, et al.         Expires August 31, 2006               [Page 25]

_______________________________________________
Ospf-manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ospf-manet

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Mon, 27 Feb 2006 15:09:17 -0800

Emmanuel,
I had a few questions and comments on your new draft.  

If I understand correctly, in general, routers make MPR decisions based
on 2-hop information in Hellos, and then form adjacencies with those
1-hop neighboring routers that are MPRs or MPR selectors.  The exception
to this rule is that some routers form adjacencies with all of their
one-hop neighbors (so-called hybrid nodes and those nodes with the
highest willingness/Router ID in their (two-hop?) neighborhood).  

Please correct me if I am wrong about the following details:
- Decisions to reflood occur based on whether the router is selected as
an MPR for the router that made the previous transmission, regardless of
whether an adjacency exists between the two routers at that time
(usually, there will be an adjacency between the two routers, but it may
be that the adjacency is not yet brought up).  The router need only be
in a state of ExStart or 2-Way or greater, with respect to the previous
flooding hop, to continue with reflooding.
- However, regardless of the reflooding decision, a router will put the
LSA on the retransmission list of all of its adjacent neighbors that
haven't yet acked it (there may be, for performance optimization, an ack
cache of previously acked LSAs that can be exploited).
- (the need to send) acknowledgments is based on whether the previous
hop router is adjacent
- All of a router's adjacencies are advertised as links in the
Router-LSA, but no links are advertised to routers that are
non-adjacent.

So if I can summarize the above, if I were to take the core Overlapping
Relays flooding proposal, disable pushback retransmissions, learn the
2-hop neighborhood via Hellos instead of LSAs, and form adjacencies only
with MPRs and selectors, I would have something very similar to your
draft?

A few more questions:

- you recommend that MinLSArrival (and I suppose also, MinLSInterval) be
changed for MANETs.  However, these are architectural constants, and I
wonder what the possible negative interoperability consequences might be
if these constants are changed, for LSAs that leave the MANET subnet.

- do you have an implementation of this?  Do you have any performance
results that you plan to share prior to the IETF meeting?

Thanks,
Tom

> -----Original Message-----
> From: Emmanuel Baccelli [mailto:[email-masked]] 
> Sent: Monday, February 27, 2006 6:18 AM
> To: [email-masked]
> Subject: [Ospf-manet] OSPF extension for MANETs
> 
> 
> Hi all,
> 
> http://www.lix.polytechnique.fr/~baccelli/MPR-OSPF/draft-bacce
> lli-ospf-mpr-ext.txt
> 
> Emmanuel
>