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 2 of 4, p. 17 to 32
Prev RFC Part       Next RFC Part

 


prevText      Top      Up      ToC       Page 17 
4.  Hello Protocol

   The MANET interface utilizes Hellos for neighbor discovery and for
   enabling neighbors to learn 2-hop neighbor information.  The protocol
   is flexible because it allows the use of full or differential Hellos.
   Full Hellos list all neighbors on the interface that are in state
   Init or greater, as in OSPFv3, whereas differential Hellos list only
   neighbors whose status as a bidirectional neighbor, Dependent
   Neighbor, or Selected Advertised Neighbor has recently changed.
   Differential Hellos are used to reduce overhead, and they allow
   Hellos to be sent more frequently (for faster reaction to topology
   changes).  If differential Hellos are used, full Hellos are sent less
   frequently to ensure that all neighbors have current 2-hop neighbor
   information.

4.1.  Sending Hello Packets

   Hello packets are sent according to [RFC5340], Section 4.2.1.1, and
   [RFC2328], Section 9.5, with the following MANET-specific
   specifications beginning after paragraph 3 of Section 9.5.  The Hello
   packet format is defined in [RFC5340], Section A.3.2, except for the
   ordering of the Neighbor IDs and the meaning of the DR and Backup DR
   fields as described below.

   Similar to [RFC2328], the DR and Backup DR fields indicate whether
   the router is an MDR or Backup MDR.  If the router is an MDR, then
   the DR field is the router's own Router ID, and if the router is a
   Backup MDR, then the Backup DR field is the router's own Router ID.
   These fields are also used to advertise the router's Parent and
   Backup Parent, as specified in Section A.3 and Section 5.4.

Top      Up      ToC       Page 18 
   Hellos are sent every HelloInterval seconds.  Full Hellos are sent
   every 2HopRefresh Hellos, and differential Hellos are sent at all
   other times.  For example, if 2HopRefresh is equal to 3, then every
   third Hello is a full Hello.  If 2HopRefresh is set to 1, then all
   Hellos are full (the default).

   The neighbor IDs included in the body of each Hello are divided into
   the following five disjoint lists of neighbors (some of which may be
   empty), and must appear in the following order:

   List 1. Neighbors whose state recently changed to Down (included only
           in differential Hellos).

   List 2. Neighbors in state Init.

   List 3. Dependent Neighbors.

   List 4. Selected Advertised Neighbors.

   List 5. Unselected bidirectional neighbors, defined as bidirectional
           neighbors that are neither Dependent nor Selected Advertised
           Neighbors.

   Note that all neighbors in Lists 3 through 5 are bidirectional
   neighbors.  These lists are used to update the neighbor's
   Bidirectional Neighbor Set (BNS), Dependent Neighbor Set (DNS), and
   Selected Advertised Neighbor Set (SANS) when a Hello is received.

   Note that the above five lists are disjoint, so each neighbor can
   appear in at most one list.  Also note that some or all of the five
   lists can be empty.

   Link-local signaling (LLS) is used to append up to two TLVs to each
   MANET Hello packet.  The format for LLS is given in Section A.2.  The
   MDR-Hello TLV is appended to each (full or differential) MANET Hello
   packet.  It indicates whether the Hello is full or differential, and
   gives the Hello Sequence Number (HSN) and the number of neighbor IDs
   in each of Lists 1 through 4 defined above.  The size of List 5 is
   then implied by the packet length field of the Hello.  The format of
   the MDR-Hello TLV is given in Section A.2.3.

   In both full and differential Hellos, the appended MDR-Hello TLV is
   built as follows.

   o  The Sequence Number field is set to the current HSN for the
      interface; the HSN is then incremented (modulo 2^16).

Top      Up      ToC       Page 19 
   o  The D-bit of the MDR-Hello TLV is set to 1 for a differential
      Hello and 0 for a full Hello.

   o  The A-bit of the MDR-Hello TLV is set to 1 if AdjConnectivity is 0
      (the router is using full-topology adjacencies); otherwise, it is
      set to 0.

   o  The N1, N2, N3, and N4 fields are set to the number of neighbor
      IDs in the body of the Hello that are in List 1, List 2, List 3,
      and List 4, respectively.  (N1 is always zero in a full Hello.)

   The MDR-Metric TLV (or Metric TLV) advertises the link cost to each
   bidirectional neighbor on the interface, to allow the selection of
   neighbors to include in partial-topology LSAs.  If LSAFullness is 1
   or 2, a Metric TLV must be appended to each MANET Hello packet unless
   all link costs are 1.  The format of the Metric TLV is given in
   Section A.2.5.  The I bit of the Metric TLV can be set to 0 or 1.  If
   the I bit is set to 0, then the Metric TLV does not contain neighbor
   IDs, and contains the metric for each bidirectional neighbor listed
   in the (full or differential) Hello, in the same order.  If the I bit
   is set to 1, then the Metric TLV includes the neighbor ID and metric
   for each bidirectional neighbor listed in the Hello whose metric is
   not equal to the Default Metric field of the TLV.

   The I bit should be chosen to minimize the size of the Metric TLV.
   This can be achieved by choosing the I bit to be 1 if and only if the
   number of bidirectional neighbors listed in the Hello whose metric
   differs from the Default Metric field is less than 1/3 of the total
   number of bidirectional neighbors listed in the Hello.

   For example, if all neighbors have the same metric, then the I bit
   should be set to 1, with the Default Metric equal to this metric,
   avoiding the need to include neighbor IDs and corresponding metrics
   in the TLV.  At the other extreme, if all neighbors have different
   metrics, then the I bit should be set to 0 to avoid listing the same
   neighbor IDs in both the body of the Hello and the Metric TLV.

   In both full and differential Hello packets, the L bit is set in the
   Hello's option field to indicate LLS.

4.1.1.  Full Hello Packet

   In a full Hello, the neighbor ID list includes all neighbors on the
   interface that are in state Init or greater, in the order described
   above.  The MDR-Hello TLV is built as described above.  If a Metric
   TLV is appended, it is built as specified in Section A.2.5.

Top      Up      ToC       Page 20 
4.1.2.  Differential Hello Packet

   In a differential Hello, the five neighbor ID lists defined in
   Section 4.1 are populated as follows:

   List 1 includes each neighbor in state Down that has not yet been
   included in HelloRepeatCount Hellos since transitioning to this
   state.

   List 2 includes each neighbor in state Init that has not yet been
   included in HelloRepeatCount Hellos since transitioning to this
   state.

   List 3 includes each Dependent Neighbor that has not yet been
   included in HelloRepeatCount Hellos since becoming a Dependent
   Neighbor.

   List 4 includes each Selected Advertised Neighbor that has not yet
   been included in HelloRepeatCount Hellos since becoming a Selected
   Advertised Neighbor.

   List 5 includes each unselected bidirectional neighbor (defined in
   Section 4.1) that has not yet been included in HelloRepeatCount
   Hellos since becoming an unselected bidirectional neighbor.

   In addition, a bidirectional neighbor must be included (in the
   appropriate list) if the neighbor's BNS does not include the router
   (indicating that the neighbor does not consider the router to be
   bidirectional).

   If a Metric TLV is appended to the Hello, then a bidirectional
   neighbor must be included (in the appropriate list) if it has not yet
   been included in HelloRepeatCount Hellos since its metric last
   changed.

4.2.  Receiving Hello Packets

   A Hello packet received on a MANET interface is processed as
   described in [RFC5340], Section 4.2.2.1, and the first two paragraphs
   of [RFC2328], Section 10.5, followed by the processing specified
   below.

   The source of a received Hello packet is identified by the Router ID
   found in the Hello's OSPF packet header.  If a matching neighbor
   cannot be found in the interface's data structure, one is created

Top      Up      ToC       Page 21 
   with the Neighbor ID set to the Router ID found in the OSPF packet
   header, the state initialized to Down, all MANET-specific neighbor
   variables (specified in Section 3.3) initialized to zero, and the
   neighbor's DNS, SANS, and BNS initialized to empty sets.

   The neighbor structure's Router Priority is set to the value of the
   corresponding field in the received Hello packet.  The Neighbor's
   Parent is set to the value of the DR field, and the Neighbor's Backup
   Parent is set to the value of the Backup DR field.

   Now the rest of the Hello Packet is examined, generating events to be
   given to the neighbor and interface state machines.  These state
   machines are specified to be either executed or scheduled (see
   [RFC2328], Section 4.4, "Tasking support").  For example, by
   specifying below that the neighbor state machine be executed in line,
   several neighbor state transitions may be affected by a single
   received Hello.

   o  If the L bit in the options field is not set, then an error has
      occurred and the Hello is discarded.

   o  If the LLS contains an MDR-Hello TLV, the neighbor state machine
      is executed with the event HelloReceived.  Otherwise, an error has
      occurred and the Hello is discarded.

   o  The Hello Sequence Number and the A-bit in the MDR-Hello TLV are
      copied to the neighbor's data structure.

   o  The DR and Backup DR fields are processed as follows.

      (1) If the DR field is equal to the neighbor's Router ID, set the
          neighbor's MDR Level to MDR.

      (2) Else if the Backup DR field is equal to the neighbor's Router
          ID, set the neighbor's MDR Level to Backup MDR.

      (3) Else, set the neighbor's MDR Level to MDR Other and set the
          neighbor's Dependent Neighbor variable to 0.  (Only MDR/BMDR
          neighbors can be Dependent.)

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

   The neighbor ID list of the Hello is divided as follows into the five
   lists defined in Section 4.1, where N1, N2, N3, and N4 are obtained
   from the corresponding fields of the MDR-Hello TLV.  List 1 is
   defined to be the first N1 neighbor IDs, List 2 is defined to be the

Top      Up      ToC       Page 22 
   next N2 neighbor IDs, List 3 is defined to be the next N3 neighbor
   IDs, List 4 is defined to be the next N4 neighbor IDs, and List 5 is
   defined to be the remaining neighbor IDs in the Hello.

   Further processing of the Hello depends on whether it is full or
   differential, which is indicated by the value of the D-bit of the
   MDR-Hello TLV.

4.2.1.  Full Hello Packet

   If the received Hello is full (the D-bit of the MDR-Hello TLV is 0),
   the following steps are performed:

   o  If the N1 field of the MDR-Hello TLV is not zero, then an error
      has occurred and the Hello is discarded.  Otherwise, set
      FullHelloRcvd to 1.

   o  In the neighbor structure, modify the neighbor's DNS to equal the
      set of neighbor IDs in the Hello's List 3, modify the neighbor's
      SANS to equal the set of neighbor IDs in the Hello's List 4, and
      modify the neighbor's BNS to equal the set of neighbor IDs in the
      union of Lists 3, 4, and 5.

   o  If the router itself appears in the Hello's neighbor ID list, the
      neighbor state machine is executed with the event 2-WayReceived
      after the Hello is processed.  Otherwise, the neighbor state
      machine is executed with the event 1-WayReceived after the Hello
      is processed.

4.2.2.  Differential Hello Packet

   If the received Hello is differential (the D-bit of the MDR-Hello TLV
   is 1), the following steps are performed:

   (1) For each neighbor ID in List 1 or List 2 of the Hello:

       o  Remove the neighbor ID from the neighbor's DNS, SANS, and BNS,
          if it belongs to the neighbor set.

   (2) For each neighbor ID in List 3 of the Hello:

       o  Add the neighbor ID to the neighbor's DNS and BNS, if it does
          not belong to the neighbor set.

       o  Remove the neighbor ID from the neighbor's SANS, if it belongs
          to the neighbor set.

   (3) For each neighbor ID in List 4 of the Hello:

Top      Up      ToC       Page 23 
       o  Add the neighbor ID to the neighbor's SANS and BNS, if it does
          not belong to the neighbor set.

       o  Remove the neighbor ID from the neighbor's DNS, if it belongs
          to the neighbor set.

   (4) For each neighbor ID in List 5 of the Hello:

       o  Add the neighbor ID to the neighbor's BNS, if it does not
          belong to the neighbor set.

       o  Remove the neighbor ID from the neighbor's DNS and SANS, if it
          belongs to the neighbor set.

   (5) If the router's own RID appears in List 1, execute the neighbor
       state machine with the event 1-WayReceived after the Hello is
       processed.

   (6) If the router's own RID appears in List 2, 3, 4, or 5, execute
       the neighbor state machine with the event 2-WayReceived after the
       Hello is processed.

   (7) If the router's own RID does not appear in the Hello's neighbor
       ID list, and the neighbor state is 2-Way or greater, and the
       Hello Sequence Number is less than or equal to the previous
       sequence number plus HelloRepeatCount, then the neighbor state
       machine is executed with the event 2-WayReceived after the Hello
       is processed (the state does not change).

   (8) If 2-WayReceived is not executed, then 1-WayReceived is executed
       after the Hello is processed.

4.2.3.  Additional Processing for Both Hello Types

   The following applies to both full and differential Hellos.

   If the router itself belongs to the neighbor's DNS, the neighbor's
   Dependent Selector variable is set to 1; otherwise, it is set to 0.

   The receiving interface's MDRNeighborChange variable is set to 1 if
   any of the following changes occurred as a result of processing the
   Hello:

   o  The neighbor's state changed from less than 2-Way to 2-Way or
      greater, or vice versa.

Top      Up      ToC       Page 24 
   o  The neighbor is bidirectional and any of the following neighbor
      variables has changed: MDR Level, Router Priority, FullHelloRcvd,
      and Bidirectional Neighbor Set (BNS).

   The neighbor state machine is scheduled with the event AdjOK?  if any
   of the following changes occurred as a result of processing the
   Hello:

   o  The neighbor's state changed from less than 2-Way to 2-Way or
      greater.

   o  The neighbor is bidirectional and its MDR Level has changed, or
      its Child variable or Dependent Selector variable has changed from
      0 to 1.

   If the LLS contains a Metric TLV, it is processed by updating the
   neighbor's link metrics according to the format of the Metric TLV
   specified in Section A.2.5.  If the LLS does not contain a Metric TLV
   and LSAFullness is 1 or 2, the metric for each of the neighbor's
   links is set to 1.

4.3.  Neighbor Acceptance Condition

   In wireless networks, a single Hello can be received from a neighbor
   with which a poor connection exists, e.g., because the neighbor is
   almost out of range.  To avoid accepting poor-quality neighbors, and
   to employ hysteresis, a router may require that a stricter condition
   be satisfied before changing the state of a MANET neighbor from Down
   to Init or greater.  This condition is called the "neighbor
   acceptance condition", which by default is the reception of a single
   Hello or DD packet.  For example, the neighbor acceptance condition
   may require that 2 consecutive Hellos be received from a neighbor
   before changing the neighbor's state from Down to Init.  Other
   possible conditions include the reception of 3 consecutive Hellos, or
   the reception of 2 of the last 3 Hellos.  The neighbor acceptance
   condition may also impose thresholds on other measurements such as
   received signal strength.

   The neighbor state transition for state Down and event HelloReceived
   is thus modified (see Section 7.1) to depend on the neighbor
   acceptance condition.

Top      Up      ToC       Page 25 
5.  MDR Selection Algorithm

   This section describes the MDR selection algorithm, which is run for
   each MANET interface to determine whether the router is an MDR,
   Backup MDR, or MDR Other for that interface.  The algorithm also
   selects the Dependent Neighbors and the (Backup) Parent, which are
   used to decide which neighbors should become adjacent (see Section
   7.2).

   The MDR selection algorithm must be executed just before sending a
   Hello if the MDRNeighborChange bit is set for the interface.  The
   algorithm SHOULD also be executed whenever a bidirectional neighbor
   transitions to less than 2-Way, and MAY be executed at other times
   when the MDRNeighborChange bit is set.  The bit is cleared after the
   algorithm is executed.

   To simplify the implementation, the MDR selection algorithm MAY be
   executed periodically just before sending each Hello, to avoid having
   to determine when the MDRNeighborChange bit should be set.  After
   running the MDR selection algorithm, the AdjOK? event may be invoked
   for some or all neighbors as specified in Section 7.

   The purpose of the MDRs is to provide a minimal set of relays for
   flooding LSAs, and the purpose of the Backup MDRs is to provide
   backup relays to flood LSAs when flooding by MDRs does not succeed.
   The set of MDRs forms a CDS, and the set of MDRs and Backup MDRs
   forms a biconnected CDS (if the network itself is biconnected).

   Each MDR selects and becomes adjacent with a subset of its MDR
   neighbors, called Dependent Neighbors, forming a connected backbone.
   Each non-MDR router connects to this backbone by selecting and
   becoming adjacent with an MDR neighbor called its Parent.  Each MDR
   selects itself as Parent, to inform neighbors that it is an MDR.

   If AdjConnectivity = 2, then each (Backup) MDR selects and becomes
   adjacent with additional (Backup) MDR neighbors to form a biconnected
   backbone, and each MDR Other selects and becomes adjacent with a
   second (Backup) MDR neighbor called its Backup Parent, thus becoming
   connected to the backbone via two adjacencies.  Each BMDR selects
   itself as Backup Parent, to inform neighbors that it is a BMDR.

   The MDR selection algorithm is a distributed CDS algorithm that uses
   2-hop neighbor information obtained from Hellos.  More specifically,
   it uses as inputs the set of bidirectional neighbors (in state 2-Way
   or greater), the triplet (Router Priority, MDR Level, Router ID) for
   each such neighbor and for the router itself, and the neighbor

Top      Up      ToC       Page 26 
   variables Bidirectional Neighbor Set (BNS) and FullHelloRcvd for each
   such neighbor.  The MDR selection algorithm can be implemented in
   O(d^2) time, where d is the number of neighbors.

   The above triplet will be abbreviated as (RtrPri, MDR Level, RID).
   The triplet (RtrPri, MDR Level, RID) is said to be larger for Router
   A than for Router B if the triplet for Router A is lexicographically
   greater than the triplet for Router B.  Routers that have larger
   values of this triplet are preferred for selection as an MDR.  The
   algorithm therefore prefers routers that are already MDRs, resulting
   in a longer average MDR lifetime.

   The MDR selection algorithm consists of five phases, the last of
   which is optional.  Phase 1 creates the neighbor connectivity matrix
   for the interface, which determines which pairs of neighbors are
   neighbors of each other.  Phase 2 decides whether the calculating
   router is an MDR, and which MDR neighbors are Dependent.  Phase 3
   decides whether the calculating router is a Backup MDR and, if
   AdjConnectivity = 2, which additional MDR/BMDR neighbors are
   Dependent.  Phase 4 selects the Parent and Backup Parent.

   The algorithm simplifies considerably if AdjConnectivity is 0 (full-
   topology adjacencies).  In this case, the set of Dependent Neighbors
   is empty and MDR Other routers need not select Parents.  Also, Phase
   3 (BMDR selection) is not required if AdjConnectivity is 0 or 1.
   However, Phase 3 MUST be executed if AdjConnectivity is 2, and SHOULD
   be executed if AdjConnectivity is 0 or 1, since BMDRs improve
   robustness by providing backup flooding.

   A router that has selected itself as an MDR in Phase 2 MAY execute
   Phase 5 to possibly declare itself a non-flooding MDR.  A non-
   flooding MDR is the same as a flooding MDR except that it does not
   automatically flood received LSAs back out the receiving interface,
   because it has determined that neighboring MDRs are sufficient to
   flood the LSA to all neighbors.  Instead, a non-flooding MDR performs
   backup flooding just like a BMDR.  A non-flooding MDR maintains its
   MDR level (rather than being demoted to a BMDR) in order to maximize
   the stability of adjacencies.  (The decision to form an adjacency
   does not depend on whether an MDR is non-flooding.)  By having MDRs
   declare themselves to be non-flooding when possible, flooding
   overhead is reduced.  The resulting reduction in flooding overhead
   can be dramatic for certain regular topologies, but has been found to
   be less than 15% for random topologies.

   The following subsections describe the MDR selection algorithm, which
   is applied independently to each MANET interface.  For convenience,
   the term "bi-neighbor" will be used as an abbreviation for
   "bidirectional neighbor".

Top      Up      ToC       Page 27 
5.1.  Phase 1: Creating the Neighbor Connectivity Matrix

   Phase 1 creates the neighbor connectivity matrix (NCM) for the
   interface.  The NCM is a symmetric matrix that defines a topology
   graph for the set of bi-neighbors on the interface.  The NCM assigns
   a value of 0 or 1 for each pair of bi-neighbors; a value of 1
   indicates that the neighbors are assumed to be bi-neighbors of each
   other in the MDR selection algorithm.  Letting i denote the router
   itself, NCM(i,j) and NCM(j,i) are set to 1 for each bi-neighbor j.
   The value of the matrix is set as follows for each pair of bi-
   neighbors j and k on the interface.

   (1.1) If FullHelloRcvd is 1 for both neighbors j and k: NCM(j,k) =
         NCM(k,j) is 1 only if j belongs to the BNS of neighbor k and k
         belongs to the BNS of neighbor j.

   (1.2) If FullHelloRcvd is 1 for neighbor j and is 0 for neighbor k:
         NCM(j,k) = NCM(k,j) is 1 only if k belongs to the BNS of
         neighbor j.

   (1.3) If FullHelloRcvd is 0 for both neighbors j and k: NCM(j,k) =
         NCM(k,j) = 0.

   In Step 1.1 above, two neighbors are considered to be bi-neighbors of
   each other only if they both agree that the other router is a bi-
   neighbor.  This provides faster response to the failure of a link
   between two neighbors, since it is likely that one router will detect
   the failure before the other router.  In Step 1.2 above, only
   neighbor j has reported its full BNS, so neighbor j is believed in
   deciding whether j and k are bi-neighbors of each other.  As Step 1.3
   indicates, two neighbors are assumed not to be bi-neighbors of each
   other if neither neighbor has reported its full BNS.

5.2.  Phase 2: MDR Selection

   Phase 2 depends on the parameter MDRConstraint, which affects the
   number of MDRs selected.  The default value of 3 results in nearly
   the minimum number of MDRs, while the value 2 results in a larger
   number of MDRs.  If AdjConnectivity = 0 (full-topology adjacencies),
   then the following steps are modified in that Dependent Neighbors are
   not selected.

   (2.1) The set of Dependent Neighbors is initialized to be empty.

Top      Up      ToC       Page 28 
   (2.2) If the router has a larger value of (RtrPri, MDR Level, RID)
         than all of its bi-neighbors, the router selects itself as an
         MDR; selects all of its MDR bi-neighbors as Dependent
         Neighbors; if AdjConnectivity = 2, selects all of its BMDR bi-
         neighbors as Dependent Neighbors; then proceeds to Phase 4.

   (2.3) Let Rmax be the bi-neighbor with the largest value of (RtrPri,
         MDR Level, RID).

   (2.4) Using NCM to determine the connectivity of bi-neighbors,
         compute the minimum number of hops, denoted hops(u), from Rmax
         to each other bi-neighbor u, using only intermediate nodes that
         are bi-neighbors with a larger value of (RtrPri, MDR Level,
         RID) than the router itself.  If no such path from Rmax to u
         exists, then hops(u) equals infinity. (See Appendix B for a
         detailed algorithm using breadth-first search.)

   (2.5) If hops(u) is at most MDRConstraint for each bi-neighbor u, the
         router selects no Dependent Neighbors, and sets its MDR Level
         as follows: If the MDR Level is currently MDR, then it is
         changed to BMDR if Phase 3 will be executed and to MDR Other if
         Phase 3 will not be executed.  Otherwise, the MDR Level is not
         changed.

   (2.6) Else, the router sets its MDR Level to MDR and selects the
         following neighbors as Dependent Neighbors: Rmax if it is an
         MDR or BMDR; each MDR bi-neighbor u such that hops(u) is
         greater than MDRConstraint; and if AdjConnectivity = 2, each
         BMDR bi-neighbor u such that hops(u) is greater than
         MDRConstraint.

   (2.7) If steps 2.1 through 2.6 resulted in the MDR Level changing to
         BMDR, or to MDR with AdjConnectivity equal to 1 or 2, then
         execute steps 2.1 through 2.6 again.  (This is necessary
         because the change in MDR Level can cause the set of Dependent
         Neighbors and the BFS tree to change.)  This step is not
         required if the MDR selection algorithm is executed
         periodically.

   Step 2.4 can be implemented using a breadth-first search (BFS)
   algorithm to compute min-hop paths from Rmax to all other bi-
   neighbors, modified to allow a bi-neighbor to be an intermediate node
   only if its value of (RtrPri, MDR Level, RID) is larger than that of
   the router itself.  A detailed description of this algorithm, which
   runs in O(d^2) time, is given in Appendix B.

Top      Up      ToC       Page 29 
5.3.  Phase 3: Backup MDR Selection

   (3.1) If the MDR Level is MDR (after running Phase 2) and
         AdjConnectivity is not 2, then proceed to Phase 4.  (If the MDR
         Level is MDR and AdjConnectivity = 2, then Phase 3 may select
         additional Dependent Neighbors to create a biconnected
         backbone.)

   (3.2) Using NCM to determine the connectivity of bi-neighbors,
         determine whether or not there exist two node-disjoint paths
         from Rmax to each other bi-neighbor u, using only intermediate
         nodes that are bi-neighbors with a larger value of (RtrPri, MDR
         Level, RID) than the router itself.  (See Appendix B for a
         detailed algorithm.)

   (3.3) If there exist two such node-disjoint paths from Rmax to each
         other bi-neighbor u, then the router selects no additional
         Dependent Neighbors and sets its MDR Level to MDR Other.

   (3.4) Else, the router sets its MDR Level to Backup MDR unless it
         already selected itself as an MDR in Phase 2, and if
         AdjConnectivity = 2, adds each of the following neighbors to
         the set of Dependent Neighbors: Rmax if it is an MDR or BMDR,
         and each MDR/BMDR bi-neighbor u such that Step 3.2 did not find
         two node-disjoint paths from Rmax to u.

   (3.5) If steps 3.1 through 3.4 resulted in the MDR Level changing
         from MDR Other to BMDR, then run Phases 2 and 3 again.  (This
         is necessary because running Phase 2 again can cause the MDR
         Level to change to MDR.)  This step is not required if the MDR
         selection algorithm is executed periodically.

   Step 3.2 can be implemented in O(d^2) time using the algorithm given
   in Appendix B.  A simplified version of the algorithm is also
   specified, which results in a larger number of BMDRs.

5.4.  Phase 4: Parent Selection

   Each router selects a Parent for each MANET interface.  The Parent of
   a non-MDR router will be a neighboring MDR if one exists.  If the
   option of biconnected adjacencies is chosen, then each MDR Other
   selects a Backup Parent, which will be a neighboring MDR/BMDR if one
   exists that is not the Parent.  The Parent of an MDR is always the
   router itself, and the Backup Parent of a BMDR is always the router
   itself.

Top      Up      ToC       Page 30 
   The (Backup) Parent is advertised in the (Backup) DR field of each
   Hello sent on the interface.  As specified in Section 7.2, each
   router forms an adjacency with its Parent and Backup Parent if it
   exists and is a neighboring MDR/BMDR.

   For a given MANET interface, let Rmax denote the router with the
   largest value of (RtrPri, MDR Level, RID) among all bidirectional
   neighbors, if such a neighbor exists that has a larger value of
   (RtrPri, MDR Level, RID) than the router itself.  Otherwise, Rmax is
   null.

   If the calculating router has selected itself as an MDR, then the
   Parent is equal to the router itself, and the Backup Parent is Rmax.
   (The latter design choice was made because it results in slightly
   better performance than choosing no Backup Parent.)  If the router
   has selected itself as a BMDR, then the Backup Parent is equal to the
   router itself.

   If the calculating router is a BMDR or MDR Other, the Parent is
   selected to be any adjacent neighbor that is an MDR, if such a
   neighbor exists.  If no adjacent MDR neighbor exists, then the Parent
   is selected to be Rmax.  By giving preference to neighbors that are
   already adjacent, the formation of a new adjacency is avoided when
   possible.  Note that the Parent can be a non-MDR neighbor temporarily
   when no MDR neighbor exists.  (This design choice was also made for
   performance reasons.)

   If AdjConnectivity = 2 and the calculating router is an MDR Other,
   then the Backup Parent is selected to be any adjacent neighbor that
   is an MDR or BMDR, other than the Parent selected in the previous
   paragraph, if such a neighbor exists.  If no such adjacent neighbor
   exists, then the Backup Parent is selected to be the bidirectional
   neighbor, excluding the selected Parent, with the largest value of
   (RtrPri, MDR Level, RID), if such a neighbor exists.  Otherwise, the
   Backup Parent is null.

5.5.  Phase 5: Optional Selection of Non-Flooding MDRs

   A router that has selected itself as an MDR MAY execute the following
   steps to possibly declare itself a non-flooding MDR.  An MDR that
   does not execute the following steps is by default a flooding MDR.

   (5.1) If the router has a larger value of (RtrPri, MDR Level, RID)
         than all of its bi-neighbors, the router is a flooding MDR.
         Else, proceed to Step 5.2.

   (5.2) Let Rmax be the bi-neighbor that has the largest value of
         (RtrPri, MDR Level, RID).

Top      Up      ToC       Page 31 
   (5.3) Using NCM to determine the connectivity of bi-neighbors,
         compute the minimum number of hops, denoted hops(u), from Rmax
         to each other bi-neighbor u, using only intermediate nodes that
         are MDR bi-neighbors with a smaller value of (RtrPri, RID) than
         the router itself. (This can be done using BFS as in Step 2.4).

   (5.4) If hops(u) is at most MDRConstraint for each bi-neighbor u,
         then the router is a non-flooding MDR.  Else, it is a flooding
         MDR.

6.  Interface State Machine

6.1.  Interface States

   No new states are defined for a MANET interface.  However, the DR and
   Backup states now imply that the router is an MDR or Backup MDR,
   respectively.  The following modified definitions apply to MANET
   interfaces:

   Waiting
      In this state, the router learns neighbor information from the
      Hello packets it receives, but is not allowed to run the MDR
      selection algorithm until it transitions out of the Waiting state
      (when the Wait Timer expires).  This prevents unnecessary changes
      in the MDR selection resulting from incomplete neighbor
      information.  The length of the Wait Timer is 2HopRefresh *
      HelloInterval seconds (the interval between full Hellos).

   DR Other
      The router has run the MDR selection algorithm and determined that
      it is not an MDR or a Backup MDR.

   Backup
      The router has selected itself as a Backup MDR.

   DR
      The router has selected itself as an MDR.

6.2.  Events that Cause Interface State Changes

   All interface events defined in [RFC2328], Section 9.2, apply to
   MANET interfaces, except for BackupSeen and NeighborChange.
   BackupSeen is never invoked for a MANET interface (since seeing a
   Backup MDR does not imply that the router itself cannot also be an
   MDR or Backup MDR).

Top      Up      ToC       Page 32 
   The event NeighborChange is replaced with the new interface variable
   MDRNeighborChange, which indicates that the MDR selection algorithm
   must be executed due to a change in neighbor information (see Section
   4.2.3).

6.3.  Changes to Interface State Machine

   This section describes the changes to the interface state machine for
   a MANET interface.  The two state transitions specified below are for
   state-event pairs that are described in [RFC2328], but have modified
   action descriptions because MDRs are selected instead of DRs.  The
   state transition in [RFC2328] for the event NeighborChange is
   omitted; instead, the new interface variable MDRNeighborChange is
   used to indicate when the MDR selection algorithm needs to be
   executed.  The state transition for the event BackupSeen does not
   apply to MANET interfaces, since this event is never invoked for a
   MANET interface.  The interface state transitions for the events
   Loopback and UnloopInd are unchanged from [RFC2328].

       State:  Down
       Event:  InterfaceUp
   New state:  Depends on action routine.

      Action:  Start the interval Hello Timer, enabling the periodic
               sending of Hello packets out the interface.  The state
               transitions to Waiting and the single shot Wait Timer
               is started.


       State:  Waiting
       Event:  WaitTimer
   New state:  Depends on action routine.

      Action:  Run the MDR selection algorithm, which may result in a
               change to the router's MDR Level, Dependent Neighbors,
               and (Backup) Parent.  As a result of this calculation,
               the new interface state will be DR Other, Backup, or DR.

               As a result of these changes, the AdjOK? neighbor event
               may be invoked for some or all neighbors.  (See
               Section 7.)



(page 32 continued on part 3)

Next RFC Part