tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Gloss.     Arch.     IMS     UICC    |    Misc.    |    search     info

RFC 5614

 
 
 

Mobile Ad Hoc Network (MANET) Extension of OSPF Using Connected Dominating Set (CDS) Flooding

Part 3 of 4, p. 32 to 51
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 32 
7.  Adjacency Maintenance

   Adjacency forming and eliminating on non-MANET interfaces remain
   unchanged.  Adjacency maintenance on a MANET interface requires
   changes to transitions in the neighbor state machine ([RFC2328],
   Section 10.3), to deciding whether to become adjacent ([RFC2328],

Top      Up      ToC       Page 33 
   Section 10.4), sending of DD packets ([RFC2328], Section 10.8), and
   receiving of DD packets ([RFC2328], Section 10.6).  The specification
   below relates to the MANET interface only.

   If full-topology adjacencies are used (AdjConnectivity = 0), the
   router forms an adjacency with each bidirectional neighbor.  If
   adjacency reduction is used (AdjConnectivity is 1 or 2), the router
   forms adjacencies with a subset of its neighbors, according to the
   rules specified in Section 7.2.

   An adjacency maintenance decision is made when any of the following
   four events occur between a router and its neighbor.  The decision is
   made by executing the neighbor event AdjOK?.

      (1) The neighbor state changes from Init to 2-Way.

      (2) The MDR Level changes for the neighbor or for the router
          itself.

      (3) The neighbor is selected to be the (Backup) Parent.

      (4) The neighbor selects the router to be its (Backup) Parent.

7.1.  Changes to Neighbor State Machine

   The following specifies new transitions in the neighbor state
   machine.

    State(s):  Down
       Event:  HelloReceived
   New state:  Depends on action routine.

      Action:  If the neighbor acceptance condition is satisfied (see
               Section 4.3), the neighbor state transitions to Init and
               the Inactivity Timer is started.  Otherwise, the neighbor
               remains in the Down state.


    State(s):  Init
       Event:  2-WayReceived
   New state:  2-Way

      Action:  Transition to neighbor state 2-Way.

    State(s):  2-Way
       Event:  AdjOK?
   New state:  Depends on action routine.

Top      Up      ToC       Page 34 
      Action:  Determine whether an adjacency should be formed with the
               neighboring router (see Section 7.2).  If not, the
               neighbor state remains at 2-Way and no further action is
               taken.

               Otherwise, the neighbor state changes to ExStart, and the
               following actions are performed.  If the neighbor has a
               larger Router ID than the router's own ID, and the
               received packet is a DD packet with the initialize (I),
               more (M), and master (MS) bits set, then execute the
               event NegotiationDone, which causes the state to
               transition to Exchange.

               Otherwise (negotiation is not complete), the router
               increments the DD sequence number in the neighbor data
               structure.  If this is the first time that an adjacency
               has been attempted, the DD sequence number should be
               assigned a unique value (like the time of day clock).  It
               then declares itself master (sets the master/slave bit to
               master), and starts sending Database Description packets,
               with the initialize (I), more (M), and master (MS) bits
               set, the MDR-DD TLV included in an LLS, and the L bit
               set.  This Database Description packet should be
               otherwise empty.  This Database Description packet should
               be retransmitted at intervals of RxmtInterval until the
               next state is entered (see [RFC2328], Section 10.8).


    State(s):  ExStart or greater
       Event:  AdjOK?
   New state:  Depends on action routine.

      Action:  Determine whether the neighboring router should still be
               adjacent (see Section 7.3).  If yes, there is no state
               change and no further action is necessary.  Otherwise,
               the (possibly partially formed) adjacency must be
               destroyed.  The neighbor state transitions to 2-Way.  The
               Link state retransmission list, Database summary list,
               and Link state request list are cleared of LSAs.

7.2.  Whether to Become Adjacent

   The following defines the method to determine if an adjacency should
   be formed between neighbors in state 2-Way.  The following procedure
   does not depend on whether AdjConnectivity is 1 or 2, but the
   selection of Dependent Neighbors (by the MDR selection algorithm)
   depends on AdjConnectivity.

Top      Up      ToC       Page 35 
   If adjacency reduction is not used (AdjConnectivity = 0), then an
   adjacency is formed with each neighbor in state 2-Way.  Otherwise, an
   adjacency is formed with a neighbor in state 2-Way if any of the
   following conditions is true:

   (1) The router is a (Backup) MDR and the neighbor is a (Backup) MDR
       and is either a Dependent Neighbor or a Dependent Selector.

   (2) The neighbor is a (Backup) MDR and is the router's (Backup)
       Parent.

   (3) The router is a (Backup) MDR and the neighbor is a child.

   (4) The neighbor's A-bit is 1, indicating that the neighbor is using
       full-topology adjacencies.

   Otherwise, an adjacency is not established and the neighbor remains
   in state 2-Way.

7.3.  Whether to Eliminate an Adjacency

   The following defines the method to determine if an existing
   adjacency should be eliminated.  An existing adjacency is maintained
   if any of the following is true:

   (1) The router is an MDR or Backup MDR.

   (2) The neighbor is an MDR or Backup MDR.

   (3) The neighbor's A-bit is 1, indicating that the neighbor is using
       full-topology adjacencies.

   Otherwise, the adjacency MAY be eliminated.

7.4.  Sending Database Description Packets

   Sending a DD packet on a MANET interface is the same as [RFC5340],
   Section 4.2.1.2, and [RFC2328], Section 10.8, with the following
   additions to paragraph 3 of Section 10.8.

   If the neighbor state is ExStart, the standard initialization packet
   is sent with an MDR-DD TLV appended using LLS, and the L bit is set
   in the DD packet's option field.  The format for the MDR-DD TLV is
   specified in Section A.2.4.  The DR and Backup DR fields of the MDR-
   DD TLV are set exactly the same as the DR and Backup DR fields of a
   Hello sent on the same interface.

Top      Up      ToC       Page 36 
7.5.  Receiving Database Description Packets

   Processing a DD packet received on a MANET interface is the same as
   [RFC2328], Section 10.6, except for the changes described in this
   section.  The following additional steps are performed before
   processing the packet based on neighbor state in paragraph 3 of
   Section 10.6.

   o  If the DD packet's L bit is set in the options field and an MDR-DD
      TLV is appended, then the MDR-DD TLV is processed as follows.

      (1) If the DR field is equal to the neighbor's Router ID:

          (a) Set the MDR Level of the neighbor to MDR.

          (b) Set the neighbor's Dependent Selector variable to 1.

      (2) Else if the Backup DR field is equal to the neighbor's Router
          ID:

          (a) Set the MDR Level of the neighbor to Backup MDR.

          (b) Set the neighbor's Dependent Selector variable to 1.

      (3) Else:

          (a) Set the MDR Level of the neighbor to MDR Other.

          (b) Set the neighbor's Dependent Neighbor variable to 0.

      (4) If the DR or Backup DR field is equal to the router's own
          Router ID, set the neighbor's Child variable to 1; otherwise,
          set it to 0.

   o  If the neighbor state is Init, the neighbor event 2-WayReceived is
      executed.

   o  If the MDR Level of the neighbor changed, the neighbor state
      machine is scheduled with the event AdjOK?.

   o  If the neighbor's Child status has changed from 0 to 1, the
      neighbor state machine is scheduled with the event AdjOK?.

   o  If the neighbor's neighbor state changed from less than 2-Way to
      2-Way or greater, the neighbor state machine is scheduled with the
      event AdjOK?.

Top      Up      ToC       Page 37 
   In addition, the Database Exchange optimization described in
   [RFC5243] SHOULD be performed as follows.  If the router accepts a
   received DD packet as the next in sequence, the following additional
   step should be performed for each LSA listed in the DD packet
   (whether the router is master or slave).  If the Database summary
   list contains an instance of the LSA that is the same as or less
   recent than the listed LSA, the LSA is removed from the Database
   summary list.  This avoids listing the LSA in a DD packet sent to the
   neighbor, when the neighbor already has an instance of the LSA that
   is the same or more recent.  This optimization reduces overhead due
   to DD packets by approximately 50% in large networks.

8.  Flooding Procedure

   This section specifies the changes to [RFC2328], Section 13, for
   routers that support OSPF-MDR.  The first part of Section 13 (before
   Section 13.1) is the same except for the following three changes.

   o  To exploit the broadcast nature of MANETs, if the Link State
      Update (LSU) packet was received on a MANET interface, then the
      packet is dropped without further processing only if the sending
      neighbor is in a lesser state than 2-Way.  Otherwise, the LSU
      packet is processed as described in this section.

   o  If the received LSA is the same instance as the database copy, the
      following actions are performed in addition to Step 7.  For each
      MANET interface for which a BackupWait Neighbor List exists for
      the LSA (see Section 8.1):

      (a) Remove the sending neighbor from the BackupWait Neighbor List
          if it belongs to the list.

      (b) For each neighbor on the receiving interface that belongs to
          the BNS for the sending neighbor, remove the neighbor from the
          BackupWait Neighbor List if it belongs to the list.

   o  Step 8, which handles the case in which the database copy of the
      LSA is more recent than the received LSA, is modified as follows.
      If the sending neighbor is in a lesser state than Exchange, then
      the router does not send the LSA back to the sending neighbor.

   There are no changes to Sections 13.1, 13.2, or 13.4.  The following
   subsections describe the changes to Sections 13.3 (Next step in the
   flooding procedure), 13.5 (Sending Link State Acknowledgments), 13.6
   (Retransmitting LSAs), and 13.7 (Receiving Link State
   Acknowledgments) of [RFC2328].

Top      Up      ToC       Page 38 
8.1.  LSA Forwarding Procedure

   When a new LSA is received, Steps 1 through 5 of [RFC2328], Section
   13.3, are performed without modification for each eligible (outgoing)
   interface that is not of type MANET.  This section specifies the
   modified steps that must be performed for each eligible MANET
   interface.  The eligible interfaces depend on the LSA's flooding
   scope as described in [RFC5340], Section 4.5.2.  Whenever an LSA is
   flooded out a MANET interface, it is included in an LSU packet that
   is sent to the multicast address AllSPFRouters.  (Retransmitted LSAs
   are always unicast, as specified in Section 8.3.)

   Step 1 of [RFC2328], Section 13.3, is performed for each eligible
   MANET interface with the following modification, so that the new LSA
   is placed on the Link State retransmission list for each appropriate
   adjacent neighbor.  Step 1c is replaced with the following action, so
   that the LSA is not placed on the retransmission list for a neighbor
   that has already acknowledged the LSA.

   o  If the new LSA was received from this neighbor, or a Link State
      Acknowledgment (LS Ack) for the new LSA has already been received
      from this neighbor, examine the next neighbor.

   To determine whether an Ack for the new LSA has been received from
   the neighbor, the router maintains an Acked LSA List for each
   adjacent neighbor, as described in Section 8.4.  When a new LSA is
   received, the Acked LSA List for each neighbor, on each MANET
   interface, should be updated by removing any LS Ack that is for an
   older instance of the LSA than the one received.

   The following description will use the notion of a "covered"
   neighbor.  A neighbor k is defined to be covered if the LSA was sent
   as a multicast by a MANET neighbor j, and neighbor k belongs to the
   Bidirectional Neighbor Set (BNS) for neighbor j.  A neighbor k is
   also defined to be covered if the LSA was sent to the multicast
   address AllSPFRouters by a neighbor j on a broadcast interface on
   which both j and k are neighbors.  (Note that j must be the DR or
   Backup DR for the broadcast network, since only these routers may
   send LSAs to AllSPFRouters on a broadcast network.)

   The following steps must be performed for each eligible MANET
   interface, to determine whether the new LSA should be forwarded on
   the interface.

   (2) If every bidirectional neighbor on the interface satisfies at
       least one of the following three conditions, examine the next
       interface (the LSA is not flooded out this interface).

Top      Up      ToC       Page 39 
      (a) The LSA was received from the neighbor.

      (b) The LSA was received on a MANET or broadcast interface and the
          neighbor is covered (defined above).

      (c) An Ack for the LSA has been received from the neighbor.

          Condition (c) MAY be omitted (thus ignoring Acks) in order to
          simplify this step.  Note that the above conditions do not
          assume the outgoing interface is the same as the receiving
          interface.

   (3) If the LSA was received on this interface, and the router is an
       MDR Other for this interface, examine the next interface (the LSA
       is not flooded out this interface).

   (4) If the LSA was received on this interface, and the router is a
       Backup MDR or a non-flooding MDR for this interface, then the
       router waits BackupWaitInterval before deciding whether to flood
       the LSA.  To accomplish this, the router creates a BackupWait
       Neighbor List for the LSA, which initially includes every
       bidirectional neighbor on this interface that does not satisfy
       any of the conditions in Step 2.  A single-shot BackupWait Timer
       associated with the LSA is started, which is set to expire after
       BackupWaitInterval seconds plus a small amount of random jitter.
       (The actions performed when the BackupWait Timer expires are
       described below in Section 8.1.2.)  Examine the next interface
       (the LSA is not yet flooded out this interface).

   (5) If the router is a flooding MDR for this interface, or if the LSA
       was originated by the router itself, then the LSA is flooded out
       the interface (whether or not the LSA was received on this
       interface) and the next interface is examined.

   (6) If the LSA was received on a MANET or broadcast interface that is
       different from this (outgoing) interface, then the following two
       steps SHOULD be performed to avoid redundant flooding.

      (a) If the router has a larger value of (RtrPri, MDR Level, RID)
          on the outgoing interface than every covered neighbor (defined
          above) that is a neighbor on BOTH the receiving and outgoing
          interfaces (or if no such neighbor exists), then the LSA is
          flooded out the interface and the next interface is examined.

      (b) Else, the router waits BackupWaitInterval before deciding
          whether to flood the LSA on the interface, by performing the
          actions in Step 4 for a Backup MDR (whether or not the router
          is a Backup MDR on this interface).  A separate BackupWait

Top      Up      ToC       Page 40 
          Neighbor List is created for each MANET interface, but only
          one BackupWait Timer is associated with the LSA.  Examine the
          next interface (the LSA is not yet flooded out this
          interface).

   (7) If this step is reached, the LSA is flooded out the interface.

8.1.1.  Note on Step 6 of LSA Forwarding Procedure

   Performing the optional Step 6 can greatly reduce flooding overhead
   if the LSA was received on a MANET or broadcast interface.  For
   example, assume that the LSA was received from the DR of a broadcast
   network that includes 100 routers, and 50 of the routers (not
   including the DR) are also attached to a MANET.  Assume that these 50
   routers are neighbors of each other in the MANET and that each has a
   neighbor in the MANET that is not attached to the broadcast network
   (and is therefore not covered).  Then by performing Step 6 of the LSA
   forwarding procedure, the number of routers that forward the LSA from
   the broadcast network to the MANET is reduced from 50 to just 1
   (assuming that at most 1 of the 50 routers is an MDR).

8.1.2.  BackupWait Timer Expiration

   If the BackupWait Timer for an LSA expires, then the following steps
   are performed for each (MANET) interface for which a BackupWait
   Neighbor List exists for the LSA.

   (1) If the BackupWait Neighbor List for the interface contains at
       least one router that is currently a bidirectional neighbor, the
       following actions are performed.

      (a) The LSA is flooded out the interface.

      (b) If the LSA is on the Ack List for the interface (i.e., is
          scheduled to be included in a delayed Link State
          Acknowledgment packet), then the router SHOULD remove the LSA
          from the Ack List, since the flooded LSA will be treated as an
          implicit Ack.

      (c) If the LSA is on the Link State retransmission list for any
          neighbor, the retransmission SHOULD be rescheduled to occur
          after RxmtInterval seconds.

   (2) The BackupWait Neighbor List is then deleted (whether or not the
       LSA is flooded).

Top      Up      ToC       Page 41 
8.2.  Sending Link State Acknowledgments

   This section describes the procedure for sending Link State
   Acknowledgments (LS Acks) on MANET interfaces.  Section 13.5 of
   [RFC2328] remains unchanged for non-MANET interfaces, but does not
   apply to MANET interfaces.  To minimize overhead due to LS Acks, and
   to take advantage of the broadcast nature of MANETs, all LS Ack
   packets sent on a MANET interface are multicast using the IP address
   AllSPFRouters.  In addition, duplicate LSAs received as a multicast
   are not acknowledged.

   When a router receives an LSA, it must decide whether to send a
   delayed Ack, an immediate Ack, or no Ack.  The interface parameter
   AckInterval is the interval between LS Ack packets when only delayed
   Acks need to be sent.  A delayed Ack SHOULD be delayed by at least
   (RxmtInterval - AckInterval - 0.5) seconds and at most (RxmtInterval
   - 0.5) seconds after the LSA instance being acknowledged was first
   received.  If AckInterval and RxmtInterval are equal to their default
   values of 1 and 7 seconds, respectively, this reduces Ack traffic by
   increasing the chance that a new instance of the LSA will be received
   before the delayed Ack is sent.  An immediate Ack is sent immediately
   in a multicast LS Ack packet, which may also include delayed Acks
   that were scheduled to be sent.

   The decision whether to send a delayed or immediate Ack depends on
   whether the received LSA is new (i.e., is more recent than the
   database copy) or a duplicate (the same instance as the database
   copy), and on whether the LSA was received as a multicast or a
   unicast (which indicates a retransmitted LSA).  The following rules
   are used to make this decision.

   (1) If the received LSA is new, a delayed Ack is sent on each MANET
       interface associated with the area, unless the LSA is flooded out
       the interface.

   (2) If the LSA is a duplicate and was received as a multicast, the
       LSA is not acknowledged.

   (3) If the LSA is a duplicate and was received as a unicast:

       (a) If the router is an MDR, or AdjConnectivity = 2 and the
           router is a Backup MDR, or AdjConnectivity = 0, then an
           immediate Ack is sent out the receiving interface.

       (b) Otherwise, a delayed Ack is sent out the receiving interface.

Top      Up      ToC       Page 42 
   The reason that (Backup) MDRs send an immediate Ack when a
   retransmitted LSA is received is to try to prevent other adjacent
   neighbors from retransmitting the LSA, since (Backup) MDRs usually
   have a large number of adjacent neighbors.  MDR Other routers do not
   send an immediate Ack (unless AdjConnectivity = 0) because they have
   fewer adjacent neighbors, and so the potential benefit does not
   justify the additional overhead resulting from sending immediate
   Acks.

8.3.  Retransmitting LSAs

   LSAs are retransmitted according to Section 13.6 of [RFC2328].  Thus,
   LSAs are retransmitted only to adjacent routers.  Therefore, since
   OSPF-MDR does not allow an adjacency to be formed between two MDR
   Other routers, an MDR Other never retransmits an LSA to another MDR
   Other, only to its Parents, which are (Backup) MDRs.

   Retransmitted LSAs are included in LSU packets that are unicast
   directly to an adjacent neighbor that did not acknowledge the LSA
   (explicitly or implicitly).  The length of time between
   retransmissions is given by the configurable interface parameter
   RxmtInterval, whose default is 7 seconds for a MANET interface.  To
   reduce overhead, several retransmitted LSAs should be included in a
   single LSU packet whenever possible.

8.4.  Receiving Link State Acknowledgments

   A Link State Acknowledgment (LS Ack) packet that is received from an
   adjacent neighbor (in state Exchange or greater) is processed as
   described in Section 13.7 of [RFC2328], with the additional steps
   described in this section.  An LS Ack packet that is received from a
   neighbor in a lesser state than Exchange is discarded.

   Each router maintains an Acked LSA List for each adjacent neighbor,
   to keep track of any LSA instances the neighbor has acknowledged but
   that the router itself has NOT yet received.  This is necessary
   because (unlike [RFC2328]) each router acknowledges an LSA only the
   first time it is received as a multicast.

   If the neighbor from which the LS Ack packet was received is in state
   Exchange or greater, then the following steps are performed for each
   LS Ack in the received LS Ack packet:

   (1) If the router does not have a database copy of the LSA being
       acknowledged, or has a database copy that is less recent than the
       one being acknowledged, the LS Ack is added to the Acked LSA List
       for the sending neighbor.

Top      Up      ToC       Page 43 
   (2) If the router has a database copy of the LSA being acknowledged,
       which is the same as the instance being acknowledged, then the
       following action is performed.  For each MANET interface for
       which a BackupWait Neighbor List exists for the LSA (see Section
       8.1), remove the sending neighbor from the BackupWait Neighbor
       List if it belongs to the list.

9.  Router-LSAs

   Unlike the DR of an OSPF broadcast network, an MDR does not originate
   a network-LSA, since a network-LSA cannot be used to describe the
   general topology of a MANET.  Instead, each router advertises a
   subset of its MANET neighbors as point-to-point links in its router-
   LSA.  The choice of which MANET neighbors to include in the router-
   LSA is flexible.  Whether or not adjacency reduction is used, the
   router can originate either partial-topology or full-topology LSAs.

   If adjacency reduction is used (AdjConnectivity is 1 or 2), then as a
   minimum requirement each router must advertise a minimum set of
   "backbone" neighbors in its router-LSA.  This minimum choice
   corresponds to LSAFullness = 0, and results in the minimum amount of
   LSA flooding overhead, but does not provide routing along shortest
   paths.

   Therefore, to allow routers to calculate shortest paths, without
   requiring every pair of neighboring routers along the shortest paths
   to be adjacent (which would be inefficient due to requiring a large
   number of adjacencies), a router-LSA may also advertise non-adjacent
   neighbors that satisfy a synchronization condition described below.

   To motivate this, we note that OSPF already allows a non-adjacent
   neighbor to be a next hop, if both the router and the neighbor belong
   to the same broadcast network (and are both adjacent to the DR).  A
   network-LSA for a broadcast network (which includes all routers
   attached to the network) implies that any router attached to the
   network can forward packets directly to any other router attached to
   the network (which is why the distance from the network to all
   attached routers is zero in the graph representing the link-state
   database).

   Since a network-LSA cannot be used to describe the general topology
   of a MANET, the only way to advertise non-adjacent neighbors that can
   be used as next hops is to include them in the router-LSA.  However,
   to ensure that such neighbors are sufficiently synchronized, only
   "routable" neighbors are allowed to be included in LSAs, and to be
   used as next hops in the SPF calculation.

Top      Up      ToC       Page 44 
9.1.  Routable Neighbors

   If adjacency reduction is used, a bidirectional MANET neighbor
   becomes routable if the SPF calculation has found a route to the
   neighbor and the neighbor satisfies the routable neighbor quality
   condition (defined below).  Since only routable and Full neighbors
   are advertised in router-LSAs, and since adjacencies are selected to
   form a connected spanning subgraph, this definition implies that
   there exists, or recently existed, a path of full adjacencies from
   the router to the routable neighbor.  The idea is that, since a
   routable neighbor can be reached through an acceptable path, it makes
   sense to take a "shortcut" and forward packets directly to the
   routable neighbor.

   This requirement does not guarantee perfect synchronization, but
   simulations have shown that it performs well in mobile networks.
   This requirement avoids, for example, forwarding packets to a new
   neighbor that is poorly synchronized because it was not reachable
   before it became a neighbor.

   To avoid selecting poor-quality neighbors as routable neighbors, a
   neighbor that is selected as a routable neighbor must satisfy the
   routable neighbor quality condition.  By default, this condition is
   that the neighbor's BNS must include the router itself (indicating
   that the neighbor agrees the connection is bidirectional).
   Optionally, a router may impose a stricter condition.  For example, a
   router may require that two Hellos have been received from the
   neighbor that (explicitly or implicitly) indicate that the neighbor's
   BNS includes the router itself.

   The single-bit neighbor variable Routable indicates whether the
   neighbor is routable, and is initially set to 0.  If adjacency
   reduction is used, Routable is updated as follows when the state of
   the neighbor changes, or the SPF calculation finds a route to the
   neighbor, or a Hello is received that affects the routable neighbor
   quality condition.

   (1) If Routable is 0 for the neighbor, the state of the neighbor is
       2-Way or greater, there exists a route to the neighbor, and the
       routable neighbor quality condition (defined above) is satisfied,
       then Routable is set to 1 for the neighbor.

   (2) If Routable is 1 for the neighbor and the state of the neighbor
       is less than 2-Way, Routable is set to 0 for the neighbor.

   If adjacency reduction is not used (AdjConnectivity = 0), then
   routable neighbors are not computed and the set of routable neighbors
   remains empty.

Top      Up      ToC       Page 45 
9.2.  Backbone Neighbors

   The flexible choice for the router-LSA is made possible by defining
   two types of neighbors that are included in the router-LSA: backbone
   neighbors and Selected Advertised Neighbors.

   If adjacency reduction is used, a bidirectional neighbor is defined
   to be a backbone neighbor if and only if it satisfies the condition
   for becoming adjacent (see Section 7.2).  If adjacency reduction is
   not used (AdjConnectivity = 0), a bidirectional neighbor is a
   backbone neighbor if and only if the neighbor's A-bit is 0
   (indicating that the neighbor is using adjacency reduction).  This
   definition allows the interoperation between routers that use
   adjacency reduction and routers that do not.

   If adjacency reduction is used, then a router MUST include in its
   router-LSA all Full neighbors and all routable backbone neighbors.  A
   minimal LSA, corresponding to LSAFullness = 0, includes only these
   neighbors.  This choice guarantees connectivity, but does not ensure
   shortest paths.  However, this choice is useful in large networks to
   achieve maximum scalability.

9.3.  Selected Advertised Neighbors

   To allow flexibility while ensuring that router-LSAs are symmetric
   (i.e., router i advertises a link to router j if and only if router j
   advertises a link to router i), each router maintains a Selected
   Advertised Neighbor set (SANS), which consists of MANET neighbors
   that the router has selected to advertise in its router-LSA, not
   including backbone neighbors.  Since the SANS does not include
   backbone neighbors (and thus Dependent Neighbors), the SANS and DNS
   are disjoint.  Both of these neighbor sets are advertised in Hellos.

   If LSAFullness is 0 (minimal LSAs), then the SANS is empty.  At the
   other extreme, if LSAFullness is 4 (full-topology LSAs), the SANS
   includes all bidirectional MANET neighbors except backbone neighbors.
   In between these two extremes, a router that is using adjacency
   reduction may select any subset of bidirectional non-backbone
   neighbors as its SANS.  The resulting router-LSA is constructed as
   specified in Section 9.4.

   Since a router that is not using adjacency reduction typically has no
   backbone neighbors (unless it has neighbors that are using adjacency
   reduction), to ensure connectivity, such a router must choose its
   SANS to contain the SANS corresponding to LSAFullness = 1.  Thus, if
   AdjConnectivity is 0 (no adjacency reduction), then LSAFullness must
   be 1, 2, or 4.

Top      Up      ToC       Page 46 
   If LSAFullness is 1, the router originates min-cost LSAs, which are
   partial-topology LSAs that (when flooded) provide each router with
   sufficient information to calculate a shortest (minimum-cost) path to
   each destination.  Appendix C describes the algorithm for selecting
   the neighbors to include in the SANS that results in min-cost LSAs.
   The input to this algorithm includes information obtained from Hellos
   received from each MANET neighbor, including the neighbor's
   Bidirectional Neighbor Set (BNS), Dependent Neighbor Set (DNS),
   Selected Advertised Neighbor Set (SANS), and the Metric TLV.  The
   Metric TLV, specified in Section A.2.5, is appended to each Hello
   (unless all link costs are 1) to advertise the link cost to each
   bidirectional neighbor.

   If LSAFullness is 2, the SANS must be selected to be a superset of
   the SANS corresponding to LSAFullness = 1.  This choice provides
   shortest-path routing while allowing the router to advertise
   additional neighbors to provide redundant routes.

   If LSAFullness is 3, each MDR originates a full-topology LSA (which
   includes all Full and routable neighbors), while each non-MDR router
   originates a minimal LSA.  If the router has multiple MANET
   interfaces, the router-LSA includes all Full and routable neighbors
   on each interface for which it is an MDR, and advertises only Full
   neighbors and routable backbone neighbors on its other interfaces.
   This choice provides routing along nearly shortest paths with
   relatively low overhead.

   Although this document specifies a few choices of the SANS, which
   correspond to different values of LSAFullness, it is important to
   note that other choices are possible.  In addition, it is not
   necessary for different routers to choose the same value of
   LSAFullness.  The different choices are interoperable because they
   all require the router-LSA to include a minimum set of neighbors, and
   because the construction of the router-LSA (described below) ensures
   that the router-LSAs originated by different routers are consistent.

9.4.  Originating Router-LSAs

   When a new router-LSA is originated, it includes a point-to-point
   (type 1) link for each MANET neighbor that is advertised.  The set of
   neighbors to be advertised is determined as follows.  If adjacency
   reduction is used, the router advertises all Full neighbors, and
   advertises each routable neighbor j that satisfies any of the
   following three conditions.  If adjacency reduction is not used
   (AdjConnectivity = 0), the router advertises each Full neighbor j
   that satisfies any of the following three conditions.

   (1) The router's SANS (for any interface) includes j.

Top      Up      ToC       Page 47 
   (2) Neighbor j's SANS includes the router (to ensure symmetry).

   (3) Neighbor j is a backbone neighbor.

   Note that backbone neighbors and neighbors in the SANS need not be
   routable or Full, but only routable and Full neighbors may be
   included in the router-LSA.  This is done so that the SANS, which is
   advertised in Hellos, does not depend on routability.

   The events that cause a new router-LSA to be originated are the same
   as in [RFC2328] and [RFC5340] except that a MANET neighbor changing
   to/from the Full state does not always cause a new router-LSA to be
   originated.  Instead, a new router-LSA is originated whenever a
   change occurs that causes any of the following three conditions to
   occur:

   o  There exists a MANET neighbor j that satisfies the above
      conditions for inclusion in the router-LSA, but is not included in
      the current router-LSA.

   o  The current router-LSA includes a MANET neighbor that is no longer
      bidirectional.

   o  The link metric has changed for a MANET neighbor that is included
      in the current router-LSA.

   The above conditions may be checked periodically just before sending
   each Hello, instead of checking them every time one of the neighbor
   sets changes.  The following implementation was found to work well.
   Just before sending each Hello, and whenever a bidirectional neighbor
   transitions to less than 2-Way, the router runs the MDR selection
   algorithm; updates its adjacencies, routable neighbors, and Selected
   Advertised Neighbors; then checks the above conditions to see if a
   new router-LSA should be originated.  In addition, if a neighbor
   becomes bidirectional or Full, the router updates its routable
   neighbors and checks the above conditions.

10.  Calculating the Routing Table

   The routing table calculation is the same as specified in [RFC2328],
   except for the following changes to Section 16.1 (Calculating the
   shortest-path tree for an area).  If full-topology adjacencies and
   full-topology LSAs are used (AdjConnectivity = 0 and LSAFullness =
   4), there is no change to Section 16.1.

   If adjacency reduction is used (AdjConnectivity is 1 or 2), then
   Section 16.1 is modified as follows.  Recall from Section 9 that a
   router can use any routable neighbor as a next hop to a destination,

Top      Up      ToC       Page 48 
   whether or not the neighbor is advertised in the router-LSA.  This is
   accomplished by modifying Step 2 so that the router-LSA associated
   with the root vertex is replaced with a dummy router-LSA that
   includes links to all Full neighbors and all routable MANET
   neighbors.  In addition, Step 2b (checking for a link from W back to
   V) MUST be skipped when V is the root vertex and W is a routable
   MANET neighbor.  However, Step 2b must still be executed when V is
   not the root vertex, to ensure compatibility with OSPFv3.

   If LSAFullness is 0 (minimal LSAs), then the calculated paths need
   not be shortest paths.  In this case, the path actually taken by a
   packet can be shorter than the calculated path, since intermediate
   routers may have routable neighbors that are not advertised in any
   router-LSA.

   If full-topology adjacencies and partial-topology LSAs are used, then
   Section 16.1 is modified as follows.  Step 2 is modified so that the
   router-LSA associated with the root vertex is replaced with a dummy
   router-LSA that includes links to all Full neighbors.  In addition,
   Step 2b MUST be skipped when V is the root vertex and W is a Full
   MANET neighbor.  (This is necessary since the neighbor's router-LSA
   need not contain a link back to the router.)

   If adjacency reduction is used with partial-topology LSAs, then the
   set of routable neighbors can change without causing the contents of
   the router-LSA to change.  This could happen, for example, if a
   routable neighbor that was not included in the router-LSA transitions
   to the Down or Init state.  Therefore, if the set of routable
   neighbors changes, the shortest-path tree must be recalculated, even
   if the router-LSA does not change.

   After the shortest-path tree and routing table are calculated, the
   set of routable neighbors must be updated, since a route to a non-
   routable neighbor may have been discovered.  If the set of routable
   neighbors changes, then the shortest-path tree and routing table must
   be calculated a second time.  The second calculation will not change
   the set of routable neighbors again, so two calculations are
   sufficient.  If the set of routable neighbors is updated periodically
   every HelloInterval seconds, then it is not necessary to update the
   set of routable neighbors immediately after the routing table is
   updated.

Top      Up      ToC       Page 49 
11.  Security Considerations

   As with OSPFv3 [RFC5340], OSPF-MDR can use the IPv6 Authentication
   Header (AH) [RFC4302] and/or the IPv6 Encapsulation Security Payload
   (ESP) [RFC4303] to provide authentication, integrity, and/or
   confidentiality.  The use of AH and ESP for OSPFv3 is described in
   [RFC4552].

   Generic threats to routing protocols are described and categorized in
   [RFC4593].  The mechanisms described in [RFC4552] provide protection
   against many of these threats, but not all of them.  In particular,
   as mentioned in [RFC5340], these mechanisms do not provide protection
   against compromised, malfunctioning, or misconfigured routers (also
   called Byzantine routers); this is true for both OSPFv3 and OSPF-MDR.

   The extension of OSPFv3 to include MANET routers does not introduce
   any new security threats.  However, the use of a wireless medium and
   lack of infrastructure, inherent with MANET routers, may render some
   of the attacks described in [RFC4593] easier to mount.  Depending on
   the network context, these increased vulnerabilities may increase the
   need to provide authentication, integrity, and/or confidentiality, as
   well as anti-replay service.

   For example, sniffing of routing information and traffic analysis are
   easier tasks with wireless routers than with wired routers, since the
   attacker only needs to be within the radio range of a router.  The
   use of confidentiality (encryption) provides protection against
   sniffing but not traffic analysis.

   Similarly, interference attacks are also easier to mount against
   MANET routers due to their wireless nature.  Such attacks can be
   mounted even if OSPF packets are protected by authentication and
   confidentiality, e.g., by transmitting noise or replaying outdated
   OSPF packets.  As discussed below, an anti-replay service (provided
   by both ESP and AH) can be used to protect against the latter attack.

   The following threat actions are also easier with MANET routers:
   spoofing (assuming the identify of a legitimate router),
   falsification (sending false routing information), and overloading
   (sending or triggering an excessive amount of routing updates).
   These attacks are only possible if authentication is not used, or the
   attacker takes control of a router or is able to forge legitimacy
   (e.g., by discovering the cryptographic key).

   [RFC4552] mandates the use of manual keying when current IPsec
   protocols are used with OSPFv3.  Routers are required to use manually
   configured keys with the same security association (SA) parameters
   for both inbound and outbound traffic.  For MANET routers, this

Top      Up      ToC       Page 50 
   implies that all routers attached to the same MANET must use the same
   key for multicasting packets.  This is required in order to achieve
   scalability and feasibility, as explained in [RFC4552].  Future
   specifications can explore the use of automated key management
   protocols that may be suitable for MANETs.

   As discussed in [RFC4552], the use of manual keys can increase
   vulnerability.  For example, manual keys are usually long lived, thus
   giving an attacker more time to discover the keys.  In addition, the
   use of the same key on all routers attached to the same MANET leaves
   all routers insecure against impersonation attacks if any one of the
   routers is compromised.

   Although [RFC4302] and [RFC4303] state that implementations of AH and
   ESP SHOULD NOT provide anti-replay service in conjunction with SAs
   that are manually keyed, it is important to note that such service is
   allowed if the sequence number counter at the sender is correctly
   maintained across local reboots until the key is replaced.
   Therefore, it may be possible for MANET routers to make use of the
   anti-replay service provided by AH and ESP.

   When an OSPF routing domain includes both MANET networks and fixed
   networks, the frequency of OSPF updates either due to actual topology
   changes or malfeasance could result in instability in the fixed
   networks.  In situations where this is a concern, it is recommended
   that the border routers segregate the MANET networks from the fixed
   networks with either separate OSPF areas or, in cases where legacy
   routers are very sensitive to OSPF update frequency, separate OSPF
   instances.  With separate OSPF areas, the 5-second MinLSInterval will
   dampen the frequency of changes originated in the MANET networks.
   Additionally, OSPF ranges can be configured to aggregate prefixes for
   the areas supporting MANET networks.  With separate OSPF instances,
   more conservative local policies can be employed to limit the volume
   of updates emanating from the MANET networks.

12.  IANA Considerations

   This document defines three new LLS TLV types: MDR-Hello TLV (14),
   MDR-Metric TLV (16), and MDR-DD TLV (15) (see Section A.2).

Top      Up      ToC       Page 51 
13.  Acknowledgments

   Thanks to Aniket Desai for helpful discussions and comments,
   including the suggestion that Router Priority should come before MDR
   Level in the lexicographical comparison of (RtrPri, MDR Level, RID)
   when selecting MDRs and BMDRs, and that the MDR calculation should be
   repeated if it causes the MDR Level to change.  Thanks also to Tom
   Henderson, Acee Lindem, and Emmanuel Baccelli for helpful discussions
   and comments.

14.  Normative References

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

   [RFC2328]   Moy, J., "OSPF Version 2", STD 54, RFC 2328, April 1998.

   [RFC4302]   Kent, S., "IP Authentication Header", RFC 4302, December
               2005.

   [RFC4303]   Kent, S., "IP Encapsulating Security Payload (ESP)", RFC
               4303, December 2005.

   [RFC4552]   Gupta, M. and N. Melam, "Authentication/Confidentiality
               for OSPFv3", RFC 4552, June 2006.

   [RFC5243]   Ogier, R., "OSPF Database Exchange Summary List
               Optimization", RFC 5243, May 2008.

   [RFC5340]   Coltun, R., Ferguson, D., Moy, J., and A. Lindem, "OSPF
               for IPv6", RFC 5340, July 2008.

   [RFC5613]   Zinin, A., Roy, A.,  Nguyen, L., Friedman, B., and D.
               Yeung, "OSPF Link-Local Signaling", RFC 5613, August
               2009.

15.  Informative References

   [Lawler]    Lawler, E., "Combinatorial Optimization: Networks and
               Matroids", Holt, Rinehart, and Winston, New York, 1976.

   [Suurballe] Suurballe, J.W. and R.E. Tarjan, "A Quick Method for
               Finding Shortest Pairs of Disjoint Paths", Networks, Vol.
               14, pp. 325-336, 1984.

   [RFC4593]   Barbir, A., Murphy, S., and Y. Yang, "Generic Threats to
               Routing Protocols", RFC 4593, October 2006.


Next RFC Part