tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Glossaries     Architecture     IMS     UICC    |    search     info

RFC 5614

 
 
 

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

Part 4 of 4, p. 52 to 71
Prev RFC Part

 


prevText      Top      Up      ToC       Page 52 
Appendix A.  Packet Formats

A.1.  Options Field

   The L bit of the OSPF options field is used for link-local signaling,
   as described in [RFC5613].  Routers set the L bit in Hello and DD
   packets to indicate that the packet contains an LLS data block.
   Routers set the L bit in a self-originated router-LSA to indicate
   that the LSA is non-ackable.

A.2.  Link-Local Signaling

   OSPF-MDR uses link-local signaling [RFC5613] to append the MDR-Hello
   TLV and MDR-Metric TLV to Hello packets, and to append the MDR-DD TLV
   to Database Description packets.  Link-local signaling is an
   extension of OSPFv2 and OSPFv3 that allows the exchange of arbitrary
   data using existing OSPF packet types.  Here we use LLS for OSPFv3,
   which is accomplished by adding an LLS data block at the end of the
   OSPFv3 packet.  The OSPF packet length field does not include the
   length of the LLS data block, but the IPv6 packet length does include
   this length.

A.2.1.  LLS Data Block

   The data block used for link-local signaling is formatted as
   described below in Figure A.1.

        0                   1                   2                   3
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |            Checksum           |       LLS Data Length         |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                                                               |
       |                           LLS TLVs                            |
       .                                                               .
       .                                                               .
       .                                                               .
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

                     Figure A.1: Format of LLS Data Block

   The Checksum field contains the standard IP checksum of the entire
   contents of the LLS block.

   The 16-bit LLS Data Length field contains the length (in 32-bit
   words) of the LLS block including the header and payload.
   Implementations should not use the Length field in the IPv6 packet
   header to determine the length of the LLS data block.

Top      Up      ToC       Page 53 
   The rest of the block contains a set of Type/Length/Value (TLV)
   triplets as described in the following section.  All TLVs must be
   32-bit aligned (with padding if necessary).

A.2.2.  LLS TLV Format

   The contents of the LLS data block are constructed using TLVs.  See
   Figure A.2 for the TLV format.

   The Type field contains the TLV ID, which is unique for each type of
   TLV.  The Length field contains the length of the Value field (in
   bytes) that is variable and contains arbitrary data.

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

                        Figure A.2: Format of LLS TLVs

   Note that TLVs are always padded to a 32-bit boundary, but padding
   bytes are not included in the TLV Length field (though they are
   included in the LLS Data Length field of the LLS block header).  All
   unknown TLVs MUST be silently ignored.

A.2.3.  MDR-Hello TLV

   The MDR-Hello TLV is appended to each MANET Hello using LLS.  It
   includes the current Hello sequence number (HSN) for the transmitting
   interface and the number of neighbors of each type that are listed in
   the body of the Hello (see Section 4.1).  It also indicates whether
   the Hello is differential (via the D-bit), and whether the router is
   using full-topology adjacencies (via the A-bit).

Top      Up      ToC       Page 54 
       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              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |    Hello Sequence Number      |          Reserved         |A|D|
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |      N1       |      N2       |      N3       |      N4       |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   o  Type: Set to 14.

   o  Length: Set to 8.

   o  Hello Sequence Number: A circular two-octet unsigned integer
      indicating the current HSN for the transmitting interface.  The
      HSN for the interface is incremented by 1 (modulo 2^16) every time
      a (differential or full) Hello is sent on the interface.

   o  Reserved: Set to 0.  Reserved for future use.

   o  A (1 bit): Set to 1 if AdjConnectivity is 0; otherwise, set to 0.

   o  D (1 bit): Set to 1 for a differential Hello and 0 for a full
      Hello.

   o  N1 (8 bits): The number of neighbors listed in the Hello that are
      in state Down.  N1 is zero if the Hello is not differential.

   o  N2 (8 bits): The number of neighbors listed in the Hello that are
      in state Init.

   o  N3 (8 bits): The number of neighbors listed in the Hello that are
      Dependent.

   o  N4 (8 bits): The number of neighbors listed in the Hello that are
      Selected Advertised Neighbors.

A.2.4.  MDR-DD TLV

   When a Database Description packet is sent to a neighbor in state
   ExStart, an MDR-DD TLV is appended to the packet using LLS.  It
   includes the same two Router IDs that are included in the DR and
   Backup DR fields of a Hello sent by the router, and is used to
   indicate the router's MDR Level and Parent(s).

Top      Up      ToC       Page 55 
       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              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+
      |                               DR                              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+
      |                           Backup DR                           |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+

   o  Type: Set to 15.

   o  Length: Set to 8.

   o  DR: The same Router ID that is included in the DR field of a Hello
      sent by the router (see Section A.3).

   o  Backup DR: The same Router ID that is included in the Backup DR
      field of a Hello sent by the router (see Section A.3).

A.2.5.  MDR-Metric TLV

   If LSAFullness is 1 or 2, an MDR-Metric TLV must be appended to each
   MANET Hello packet using LLS, unless all link metrics are 1.  This
   TLV advertises the link metric for each bidirectional neighbor listed
   in the body of the Hello.  At a minimum, this TLV advertises a single
   default metric.  If the I bit is set, the Router ID and link metric
   are included for each bidirectional neighbor listed in the body of
   the Hello whose link metric is not equal to the default metric.  This
   option reduces overhead when all neighbors have the same link metric,
   or only a few neighbors have a link metric that differs from the
   default metric.  If the I bit is zero, the link metric is included
   for each bidirectional neighbor that is listed in the body of the
   Hello and the neighbor RIDs are omitted from the TLV.

Top      Up      ToC       Page 56 
       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              |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |      Default Metric           |        Reserved             |I|
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                        Neighbor ID (1)                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                        Neighbor ID (2)                        |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |                             ...                               |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |         Metric (1)            |        Metric (2)             |
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
      |           ...
      +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   o  Type: Set to 16.

   o  Length: Set to 4 + 6*N if the I bit is 1, and to 4 + 2*N if the I
      bit is 0, where N is the number of neighbors included in the TLV.

   o  Default Metric: If the I bit is 1, this is the link metric that
      applies to every bidirectional neighbor listed in the body of the
      Hello whose RID is not listed in the Metric TLV.

   o  Neighbor ID: If the I bit is 1, the RID is listed for each
      bidirectional neighbor (Lists 3 through 5 as defined in Section
      4.1) in the body of the Hello whose link metric is not equal to
      the default metric.  Omitted if the I bit is 0.

   o  Metric: Link metric for each bidirectional neighbor, listed in the
      same order as the Neighbor IDs in the TLV if the I bit is 1, and
      in the same order as the Neighbor IDs of bidirectional neighbors
      (Lists 3 through 5 as defined in Section 4.1) in the body of the
      Hello if the I bit is 0.

Top      Up      ToC       Page 57 
A.3.  Hello Packet DR and Backup DR Fields

   The Designated Router (DR) and Backup DR fields of a Hello packet are
   set as follows:

   o  DR:  This field is the router's Parent, or is 0.0.0.0 if the
      Parent is null.  The Parent of an MDR is always the router's own
      RID.

   o  Backup DR:  This field is the router's Backup Parent, or is
      0.0.0.0 if the Backup Parent is null.  The Backup Parent of a BMDR
      is always the router's own RID.

A.4.  LSA Formats and Examples

   LSA formats are specified in [RFC5340], Section 4.4.  Figure A.3
   below gives an example network map for a MANET in a single area.

   o  Four MANET routers RT1, RT2, RT3, and RT4 are in area 1.

   o  RT1's MANET interface has links to RT2 and RT3's MANET interfaces.

   o  RT2's MANET interface has links to RT1 and RT3's MANET interfaces.

   o  RT3's MANET interface has links to RT1, RT2, and RT3's MANET
      interfaces.

   o  RT4's MANET interface has a link to RT3's MANET interface.

   o  RT1 and RT2 have stub networks attached on broadcast interfaces.

   o  RT3 has a transit network attached on a broadcast interface.

Top      Up      ToC       Page 58 
       ..........................................
       .                                  Area 1.
       .     +                                  .
       .     |                                  .
       .     |  2+---+1                      1+---+
       .  N1 |---|RT1|----+               +---|RT4|----
       .     |   +---+    |\             /    +---+
       .     |            | \           /       .
       .     +            |  \   N3    /        .
       .                  |   \       /         .
       .     +            |    \     /          .
       .     |            |     \   /           .
       .     |  2+---+1   |      \ /            .
       .  N2 |---|RT2|----+-------+             .
       .     |   +---+            |1            .
       .     |                  +---+           .
       .     |                  |RT3|----------------
       .     +                  +---+           .
       .                          |2            .
       .                   +------------+       .
       .                      |1   N4           .
       .                    +---+               .
       .                    |RT5|               .
       .                    +---+               .
       ..........................................

       Figure A.3: Area 1 with IP Addresses Shown


      Network   IPv6 prefix
      -----------------------------------
      N1        5f00:0000:c001:0200::/56
      N2        5f00:0000:c001:0300::/56
      N4        5f00:0000:c001:0400::/56

      Table 1: IPv6 link prefixes for sample network

Top      Up      ToC       Page 59 
      Router     interface   Interface ID  IPv6 global unicast prefix
      -----------------------------------------------------------
      RT1      LOOPBACK      0             5f00:0001::/64
               to N3         1             n/a
               to N1         2             5f00:0000:c001:0200::RT1/56
      RT2      LOOPBACK      0             5f00:0002::/64
               to N3         1             n/a
               to N2         2             5f00:0000:c001:0300::RT2/56
      RT3      LOOPBACK      0             5f00:0003::/64
               to N3         1             n/a
               to N4         2             5f00:0000:c001:0400::RT3/56
      RT4      LOOPBACK      0             5f00:0004::/64
               to N3         1             n/a
      RT5      to N4         1             5f00:0000:c001:0400::RT5/56

      Table 2: IPv6 link prefixes for sample network


      Router   interface   Interface ID   link-local address
      -------------------------------------------------------
      RT1      LOOPBACK    0              n/a
               to N1       1              fe80:0001::RT1
               to N3       2              fe80:0002::RT1
      RT2      LOOPBACK    0              n/a
               to N2       1              fe80:0001::RT2
               to N3       2              fe80:0002::RT2
      RT3      LOOPBACK    0              n/a
               to N3       1              fe80:0001::RT3
               to N4       2              fe80:0002::RT3
      RT4      LOOPBACK    0              n/a
               to N3       1              fe80:0001::RT4
      RT5      to N4       1              fe80:0002::RT5

      Table 3: OSPF interface IDs and link-local addresses

Top      Up      ToC       Page 60 
A.4.1.  Router-LSAs

   As an example, consider the router-LSA that node RT3 would originate.
   The node consists of one MANET, one broadcast, and one loopback
   interface.

   RT3's router-LSA

   LS age = DoNotAge+0              ;newly originated
   LS type = 0x2001                 ;router-LSA
   Link State ID = 0                ;first fragment
   Advertising Router = 192.1.1.3   ;RT3's Router ID
   bit E = 0                        ;not an AS boundary router
   bit B = 1                        ;area border router
   Options = (V6-bit|E-bit|R-bit)
     Type = 1                        ;p2p link to RT1
     Metric = 1                      ;cost to RT1
     Interface ID = 1                ;Interface ID
     Neighbor Interface ID = 1       ;Interface ID
     Neighbor Router ID = 192.1.1.1  ;RT1's Router ID
     Type = 1                        ;p2p link to RT2
     Metric = 1                      ;cost to RT2
     Interface ID = 1                ;Interface ID
     Neighbor Interface ID = 1       ;Interface ID
     Neighbor Router ID = 192.1.1.2  ;RT2's Router ID
     Type = 1                        ;p2p link to RT4
     Metric = 1                      ;cost to RT4
     Interface ID = 1                ;Interface ID
     Neighbor Interface ID = 1       ;Interface ID
     Neighbor Router ID = 192.1.1.4  ;RT4's Router ID
     Type = 2                        ;connects to N4
     Metric = 1                      ;cost to N4
     Interface ID = 2                ;RT3's Interface ID
     Neighbor Interface ID = 1       ;RT5's Interface ID (elected DR)
     Neighbor Router ID = 192.1.1.5  ;RT5's Router ID  (elected DR)

Top      Up      ToC       Page 61 
A.4.2.  Link-LSAs

   Consider the link-LSA that RT3 would originate for its MANET
   interface.

   RT3's link-LSA for its MANET interface

   LS age = DoNotAge+0              ;newly originated
   LS type = 0x0008                 ;Link-LSA
   Link State ID = 1                ;Interface ID
   Advertising Router = 192.1.1.3   ;RT3's Router ID
   RtrPri = 1                       ;default priority
   Options = (V6-bit|E-bit|R-bit)
   Link-local Interface Address = fe80:0001::RT3
   # prefixes = 0                   ;no global unicast address

A.4.3.  Intra-Area-Prefix-LSAs

   A MANET node originates an intra-area-prefix-LSA to advertise its own
   prefixes, and those of its attached networks or stub links.  As an
   example, consider the intra-area-prefix-LSA that RT3 will build.

   RT2's intra-area-prefix-LSA for its own prefixes

   LS age = DoNotAge+0              ;newly originated
   LS type = 0x2009                 ;intra-area-prefix-LSA
   Link State ID = 177              ;or something
   Advertising Router = 192.1.1.3   ;RT3's Router ID
   # prefixes = 2
   Referenced LS type = 0x2001      ;router-LSA reference
   Referenced Link State ID = 0     ;always 0 for router-LSA reference
   Referenced Advertising Router = 192.1.1.3 ;RT2's Router ID
     PrefixLength = 64               ;prefix on RT3's LOOPBACK
     PrefixOptions = 0
     Metric = 0                      ;cost of RT3's LOOPBACK
     Address Prefix = 5f00:0003::/64
     PrefixLength = 56               ;prefix on RT3's interface 2
     PrefixOptions = 0
     Metric = 1                      ;cost of RT3's interface 2
     Address Prefix = 5f00:0000:c001:0400::RT3/56    ;pad

Top      Up      ToC       Page 62 
Appendix B.  Detailed Algorithms for MDR/BMDR Selection

   This section provides detailed algorithms for Step 2.4 of Phase 2
   (MDR selection) and Step 3.2 of Phase 3 (BMDR selection) of the MDR
   selection algorithm described in Section 5.  Step 2.4 uses a breadth-
   first search (BFS) algorithm, and Step 3.2 uses an efficient
   algorithm for finding pairs of node-disjoint paths from Rmax to all
   other neighbors.  Both algorithms run in O(d^2) time, where d is the
   number of neighbors.

   For convenience, in the following description, the term "bi-neighbor"
   will be used as an abbreviation for "bidirectional neighbor".  Also,
   node i denotes the router performing the calculation.

B.1.  Detailed Algorithm for Step 2.4 (MDR Selection)

   The following algorithm performs Step 2.4 of the MDR selection
   algorithm, and assumes that Phase 1 and Steps 2.1 through 2.3 have
   been performed, so that the neighbor connectivity matrix NCM has been
   computed and Rmax is the bi-neighbor with the (lexicographically)
   largest value of (RtrPri, MDR Level, RID).  The BFS algorithm uses a
   FIFO queue so that all nodes 1 hop from node Rmax are processed
   first, then 2 hops, etc.  When the BFS algorithm terminates, hops(u),
   for each bi-neighbor node u of node i, will be equal to the minimum
   number of hops from node Rmax to node u, using only intermediate
   nodes that are bi-neighbors of node i and that have a larger value of
   (RtrPri, MDR Level, RID) than node i.  The algorithm also computes,
   for each node u, the tree parent p(u) and the second node r(u) on the
   tree path from Rmax to u, which will be used in Step 3.2.

   (a)  Compute a matrix of link costs c(u,v) for each pair of bi-
        neighbors u and v as follows: If node u has a larger value of
        (RtrPri, MDR Level, RID) than node i, and NCM(u,v) = 1, then set
        c(u,v) to 1.  Otherwise, set c(u,v) to infinity.  (Note that the
        matrix NCM(u,v) is symmetric, but the matrix c(u,v) is not.)

   (b)  Set hops(u) = infinity for all bi-neighbors u other than Rmax,
        and set hops(Rmax) = 0.  Initially, p(u) is undefined for each
        neighbor u.  For each bi-neighbor u such that c(Rmax,u) = 1, set
        r(u) = u; for all other u, r(u) is initially undefined.  Add
        node Rmax to the FIFO queue.

   (c)  While the FIFO queue is nonempty:  Remove the node at the head
        of the queue; call it node u.  For each bi-neighbor v of node i
        such that c(u,v) = 1:
          If hops(v) > hops(u) + 1, then set hops(v) = hops(u) + 1, set
          p(v) = u, set r(v) = r(u) if hops(v) > 1, and add node v to
          the tail of the queue.

Top      Up      ToC       Page 63 
B.2.  Detailed Algorithm for Step 3.2 (BMDR Selection)

   Step 3.2 of the MDR selection algorithm requires the router to
   determine whether there exist two node-disjoint paths from Rmax to
   each other bi-neighbor u, via bi-neighbors that have a larger value
   of (RtrPri, MDR Level, RID) than the router itself.  This information
   is needed to determine whether the router should select itself as a
   BMDR.

   It is possible to determine separately for each bi-neighbor u whether
   there exist two node-disjoint paths from Rmax to u, using the well-
   known augmenting path algorithm [Lawler] that runs in O(n^2) time,
   but this must be done for all bi-neighbors u, thus requiring a total
   run time of O(n^3).  The algorithm described below makes the same
   determination simultaneously for all bi-neighbors u, achieving a much
   faster total run time of O(n^2).  The algorithm is a simplified
   variation of the Suurballe-Tarjan algorithm [Suurballe] for finding
   pairs of disjoint paths.

   The algorithm described below uses the following output of Phase 2:
   the tree parent p(u) of each node (which defines the BFS tree
   computed in Phase 2), and the second node r(u) on the tree path from
   Rmax to u.

   The algorithm uses the following concepts.  For any node u on the BFS
   tree other than Rmax, we define g(u) to be the first labeled node on
   the reverse tree path from u to Rmax, if such a labeled node exists
   other than Rmax.  (The reverse tree path consists of u, p(u),
   p(p(u)), ..., Rmax.)  If no such labeled node exists, then g(u) is
   defined to be r(u).  In particular, if u is labeled then g(u) = u.
   Note that g(u) either must be labeled or must be a neighbor of Rmax.

   For any node k that either is labeled or is a neighbor of Rmax, we
   define the unlabeled subtree rooted at k, denoted S(k), to be the set
   of nodes u such that g(u) = k.  Thus, S(k) includes node k itself and
   the set of unlabeled nodes downstream of k on the BFS tree that can
   be reached without going through any labeled nodes.  This set can be
   obtained in linear time using a depth-first search starting at node
   k, and using labeled nodes to indicate the boundaries of the search.
   Note that g(u) and S(k) are not maintained as variables in the
   algorithm given below, but simply refer to the definitions given
   above.

   The BMDR algorithm maintains a set B, which is initially empty.  A
   node u is added to B when it is known that two node-disjoint paths
   exist from Rmax to u via nodes that have a larger value of (RtrPri,
   MDR Level, RID) than the router itself.  When the algorithm
   terminates, B consists of all nodes that have this property.

Top      Up      ToC       Page 64 
   The algorithm consists of the following two steps.

   (a) Mark Rmax as labeled.  For each pair of nodes u, v on the BFS
       tree other than Rmax such that r(u) is not equal to r(v) (i.e., u
       and v have different second nodes), NCM(u,v) = 1, and node u has
       a greater value of (RtrPri, MDR level, RID) than the router
       itself, add v to B.  (Clearly there are two disjoint paths from
       Rmax to v.)

   (b) While there exists a node in B that is not labeled, do the
       following.  Choose any node k in B that is not labeled, and let j
       = g(k).  Now mark k as labeled. (This creates a new unlabeled
       subtree S(k), and makes S(j) smaller by removing S(k) from it.)
       For each pair of nodes u, v such that u is in S(k), v is in S(j),
       and NCM(u,v) = 1:

       o  If u has a larger value of (RtrPri, MDR level, RID) than the
          router itself, and v is not in B, then add v to B.

       o  If v has a larger value of (RtrPri, MDR level, RID) than the
          router itself, and u is not in B, then add u to B.

   A simplified version of the algorithm MAY be performed by omitting
   step (b).  However, the simplified algorithm will result in more
   BMDRs, and is not recommended if AdjConnectivity = 2 since it will
   result in more adjacencies.

   The above algorithm can be executed in O(n^2) time, where n is the
   number of neighbors.  Step (a) clearly requires O(n^2) time since it
   considers all pairs of nodes u and v.  Step (b) also requires O(n^2)
   time because each pair of nodes is considered at most once.  This is
   because labeling nodes divides unlabeled subtrees into smaller
   unlabeled subtrees, and a given pair u, v is considered only the
   first time u and v belong to different unlabeled subtrees.

Top      Up      ToC       Page 65 
Appendix C.  Min-Cost LSA Algorithm

   This section describes the algorithm for determining which MANET
   neighbors to include in the router-LSA when LSAFullness is 1.  The
   min-cost LSA algorithm ensures that the link-state database provides
   sufficient information to calculate at least one shortest (minimum-
   cost) path to each destination.  The algorithm assumes that a router
   may have multiple interfaces, at least one of which is a MANET
   interface.  The algorithm becomes significantly simpler if the router
   has only a single (MANET) interface.

   The input to this algorithm includes information obtained from Hellos
   received from each neighbor on each MANET interface, including the
   neighbor's Bidirectional Neighbor Set (BNS), Dependent Neighbor Set
   (DNS), Selected Advertised Neighbor Set (SANS), and link metrics.
   The input also includes the link-state database if the router has a
   non-MANET interface.

   The output of the algorithm is the router's SANS for each MANET
   interface.  The SANS is used to construct the router-LSA as described
   in Section 9.4.  The min-cost LSA algorithm must be run to update the
   SANS (and possibly originate a new router-LSA) either periodically
   just before sending each Hello, or whenever any of the following
   events occurs:

   o  The state or routability of a neighbor changes.

   o  A Hello received from a neighbor indicates a change in its MDR
      Level, Router Priority, FullHelloRcvd, BNS, DNS, SANS, Parent(s),
      or link metrics.

   o  An LSA originated by a non-MANET neighbor is received.

   Although the algorithm described below runs in O(d^3) time, where d
   is the number of neighbors, an incremental version for a single
   topology change runs in O(d^2) time, as discussed following the
   algorithm description.

   For convenience, in the following description, the term "bi-neighbor"
   will be used as an abbreviation for "bidirectional neighbor".  Also,
   router i will denote the router doing the calculation.  To perform
   the min-cost LSA algorithm, the following steps are performed.

   (1) Create the neighbor connectivity matrix (NCM) for each MANET
       interface, as described in Section 5.1.  Create the multiple-
       interface neighbor connectivity matrix MNCM as follows.  For each
       bi-neighbor j, set MNCM(i,j) = MNCM(j,i) = 1.  For each pair j, k
       of MANET bi-neighbors, set MNCM(j,k) = 1 if NCM(j,k) equals 1 for

Top      Up      ToC       Page 66 
       any MANET interface.  For each pair j, k of non-MANET bi-
       neighbors, set MNCM(j,k) = 1 if the link-state database indicates
       that a direct link exists between j and k.  Otherwise, set
       MNCM(j,k) = 0.  (Note that a given router can be a neighbor on
       both a MANET interface and a non-MANET interface.)

   (2) Create the inter-neighbor cost matrix (COST) as follows.  For
       each pair j, k of routers such that each of j and k is a bi-
       neighbor or router i itself:

       (a) If MNCM(j,k) = 1, set COST(j,k) to the metric of the link
           from j to k obtained from j's Hellos (for a MANET interface),
           or from the link-state database (for a non-MANET interface).
           If there are multiple links from j to k (via multiple
           interfaces), COST(j,k) is set to the minimum cost of these
           links.

       (b) Otherwise, set COST(j,k) to LSInfinity.

   (3) Create the backbone neighbor matrix (BNM) as follows.  BNM
       indicates which pairs of MANET bi-neighbors are backbone
       neighbors of each other, as defined in Section 9.2.1.  If
       adjacency reduction is not used (AdjConnectivity = 0), set all
       entries of BNM to zero and proceed to Step 4.

       In the following, if a link exists from router j to router k on
       more than one interface, we consider only interfaces for which
       the cost from j to k equals COST(j,k); such interfaces will be
       called "candidate" interfaces.

       For each pair j, k of MANET bi-neighbors, BNM(j,k) is set to 1 if
       j and k are backbone neighbors of each other on a candidate MANET
       interface.  That is, BNM(j,k) is set to 1 if, for any candidate
       MANET interface, NCM(j,k) = 1 and either of the following
       conditions is satisfied:

       (a) Router k is included in j's DNS or router j is included in
           k's DNS.

       (b) Router j is the (Backup) Parent of router k or router k is
           the (Backup) Parent of router j.

       Otherwise, BNM(j,k) is set to 0.

   (4) Create the Selected Advertised Neighbor Matrix (SANM) as follows.
       For each pair j, k of routers such that each of j and k is a bi-
       neighbor or router i itself, SANM(j,k) is set to 1 if, for any

Top      Up      ToC       Page 67 
       candidate MANET interface, NCM(j,k) = 1 and k is included in j's
       SANS.  Otherwise, SANM(j,k) is set to 0.  Note that SANM(i,k) is
       set to 1 if k is currently a Selected Advertised Neighbor.

   (5) Compute the new set of Selected Advertised Neighbors as follows.
       For each MANET bi-neighbor j, initialize the bit variable
       new_sel_adv(j) to 0. (This bit will be set to 1 if j is
       selected.)  For each MANET bi-neighbor j:

       (a) If j is a bi-neighbor on more than one interface, consider
           only candidate interfaces (for which the cost to j is
           minimum).  If one of the candidate interfaces is a non-MANET
           interface, examine the next neighbor (j is not selected since
           it will be advertised anyway).

       (b) If adjacency reduction is used, and one of the candidate
           interfaces is a MANET interface on which j is a backbone
           neighbor (see Section 9.2), examine the next neighbor (j is
           not selected since it will be advertised anyway).

       (c) Otherwise, if there is more than one candidate MANET
           interface, select the "preferred" interface by using the
           following preference rules in the given order: an interface
           is preferred if (1) router i's SANS for that interface
           already includes j, (2) router i's Router Priority is larger
           on that interface, and (3) router i's MDR Level is larger on
           that interface.

       (d) For each bi-neighbor k (on any interface) such that COST(k,j)
           > COST(k,i) + COST(i,j), determine whether there exists
           another bi-neighbor u such that either COST(k,u) + COST(u,j)
           < COST(k,i) + COST(i,j), or COST(k,u) + COST(u,j) = COST(k,i)
           + COST(i,j) and either of the following conditions is true:

           o  BNM(u,j) = 1, or

           o  (SANM(j,u), SANM(u,j), RtrPri(u), RID(u)) is
              lexicographically greater than (SANM(j,i), SANM(i,j),
              RtrPri(i), RID(i)).

       If for some such bi-neighbor k, there does not exist such a bi-
       neighbor u, then set new_sel_adv(j) = 1.

   (6) For each MANET interface I, update the SANS to equal the set of
       all bi-neighbors j such that new_sel_adv(j) = 1 and I is the
       preferred interface for j.

Top      Up      ToC       Page 68 
   (7) With the SANS updated, a new router-LSA may need to be originated
       as described in Section 9.4.

   The lexicographical comparison of Step 5d gives preference to links
   that are already advertised, in order to improve LSA stability.

   The above algorithm can be run in O(d^2) time if a single link change
   occurs.  For example, if link (x,y) fails where x and y are neighbors
   of router i, and either SANS(x,y) = 1 or BNM(x,y) = 1, then Step 5
   need only be performed for pairs j, k such that either j or k is
   equal to x or y.

Appendix D.  Non-Ackable LSAs for Periodic Flooding

   In a highly mobile network, it is possible that a router almost
   always originates a new router-LSA every MinLSInterval seconds.  In
   this case, it should not be necessary to send Acks for such an LSA,
   or to retransmit such an LSA as a unicast, or to describe such an LSA
   in a DD packet.  In this case, the originator of an LSA MAY indicate
   that the router-LSA is "non-ackable" by setting the L bit in the
   options field of the LSA (see Section A.1).  For example, a router
   can originate non-ackable LSAs if it determines (e.g., based on an
   exponential moving average) that a new LSA is originated every
   MinLSInterval seconds at least 90 percent of the time. (Simulations
   can be used to determine the best threshold.)

   A non-ackable LSA is never acknowledged, nor is it ever retransmitted
   as a unicast or described in a DD packet, thus saving substantial
   overhead.  However, the originating router must periodically
   retransmit the current instance of its router-LSA as a multicast
   (until it originates a new LSA, which will usually happen before the
   previous instance is retransmitted), and each MDR must periodically
   retransmit each non-ackable LSA as a multicast (until it receives a
   new instance of the LSA, which will usually happen before the
   previous instance is retransmitted).  For this option to work,
   RxmtInterval must be larger than MinLSInterval so that a new instance
   of the LSA is usually received before the previous one is
   retransmitted.  Note that the reception of a retransmitted
   (duplicate) LSA does not result in immediate forwarding of the LSA;
   only a new LSA (with a larger sequence number) may be forwarded
   immediately, according to the flooding procedure of Section 8.

Top      Up      ToC       Page 69 
Appendix E.  Simulation Results

   This section presents simulation results that predict the performance
   of OSPF-MDR for up to 160 nodes with min-cost LSAs and up to 200
   nodes with minimal LSAs.  The results were obtained using the GTNetS
   simulator with OSPF-MDR version 1.01, available at
   http://hipserver.mct.phantomworks.org/ietf/ospf.

   The following scenario parameter values were used: radio range = 200
   m and 250 m, grid length = 500 m, wireless alpha = 0.5, (maximum)
   velocity = 10 m/s, pause time = 0, packet rate = 10 pkts/s, packet
   size = 40 bytes, random seed = 8, start time (for gathering
   statistics) = 1800 s.  The stop time was 3600 s for up to 80 nodes
   and 2700 s for more than 80 nodes.  The source and destination are
   selected randomly for each generated UDP packet.  The simulated MAC
   protocol is 802.11b.

   Tables 4 and 6 show the results for the default configuration of
   OSPF-MDR, except that differential Hellos were used (2HopRefresh = 3)
   since they are recommended when the number of neighbors is large.
   Tables 5 and 7 show the results for the same configuration except
   that minimal LSAs were used instead of min-cost LSAs.  The tables
   show the results for total OSPF overhead in kb/s, the total number of
   OSPF packets per second, the delivery ratio for UDP packets, and the
   average number of hops traveled by UDP packets that reach their
   destination.

   Tables 5 and 7 for minimal LSAs also show the following statistics:
   the average number of bidirectional neighbors per node, the average
   number of fully adjacent neighbors per node, the number of changes in
   the set of bidirectional neighbors per node per second, and the
   number of changes in the set of fully adjacent neighbors per node per
   second.  These statistics do not change significantly when min-cost
   LSAs are used instead of minimal LSAs.

   The results show that OSPF-MDR achieves good performance for up to at
   least 160 nodes when min-cost LSAs are used, and up to at least 200
   nodes when minimal LSAs are used.  Also, the results for the number
   of hops show that the routes obtained with minimal LSAs are only 2.3%
   to 4.5% longer than with min-cost LSAs when the range is 250 m, and
   3.5% to 7.4% longer when the range is 200 m.

   The results also show that the number of adjacencies per node and the
   number of adjacency changes per node per second do not increase as
   the number of nodes increases, and are dramatically smaller than the
   number of neighbors per node and the number of neighbor changes per
   node per second, respectively.  These factors contribute to the low
   overhead achieved by OSPF-MDR.  For example, the results in Table 5

Top      Up      ToC       Page 70 
   imply that with 200 nodes and range 250 m, there are 2.136/.039 = 55
   times as many adjacency formations with full-topology adjacencies as
   with uniconnected adjacencies.  Additional simulation results for
   OSPF-MDR can be found at http://www.manet-routing.org.

                                      Number of nodes
                        20     40     60     80    100    120    160
   ------------------------------------------------------------------
   OSPF kb/s           27.1   74.2  175.3  248.6  354.6  479.2  795.7
   OSPF pkts/s         29.9   69.2  122.9  163.7  210.3  257.2  357.7
   Delivery ratio      .970   .968   .954   .958   .957   .956   .953
   Avg no. hops       1.433  1.348  1.389  1.368  1.411  1.361  1.386

   Table 4: Results for range 250 m with min-cost LSAs


                                      Number of nodes
                        20     40     60     80    120    160    200
   ------------------------------------------------------------------
   OSPF kb/s           15.5   41.6   91.0  132.9  246.3  419.0  637.4
   OSPF pkts/sec       18.8   42.5   78.6  102.8  166.8  245.6  321.0
   Delivery ratio      .968   .968   .951   .953   .962   .956   .951
   Avg no. hops       1.466  1.387  1.433  1.412  1.407  1.430  1.411
   Avg no. nbrs/node  11.38  25.82  36.30  50.13  75.87  98.65 125.59
   Avg no. adjs/node   2.60   2.32   2.38   2.26   2.25   2.32   2.13
   Nbr changes/node/s  .173   .372   .575   .752  1.223  1.654  2.136
   Adj changes/node/s  .035   .036   .046   .040   .032   .035   .039

   Table 5: Results for range 250 m with minimal LSAs


                                      Number of nodes
                        20     40     60     80    100    120    160
   ------------------------------------------------------------------
   OSPF kb/s           40.5  123.4  286.5  415.7  597.5  788.9 1309.8
   OSPF pkts/s         37.6   83.9  135.1  168.6  205.4  247.7  352.3
   Delivery ratio      .926   .919   .897   .900   .898   .895   .892
   Avg no. hops       1.790  1.628  1.666  1.632  1.683  1.608  1.641

   Table 6: Results for range 200 m with min-cost LSAs

Top      Up      ToC       Page 71 
                                      Number of nodes
                        20     40     60     80    120    160    200
   ------------------------------------------------------------------
   OSPF kb/s           24.0   63.6  140.6  195.2  346.9  573.2  824.6
   OSPF pkts/sec       26.4   58.8  108.3  138.8  215.2  311.3  401.3
   Delivery ratio      .930   .927   .897   .907   .907   .904   .902
   Avg no. hops       1.853  1.714  1.771  1.743  1.727  1.758  1.747
   Avg no. nbrs/node   7.64  18.12  25.27  35.29  52.99  68.13  86.74
   Avg no. adjs/node   2.78   2.60   2.70   2.50   2.39   2.36   2.24
   Nbr changes/node/s  .199   .482   .702   .959  1.525  2.017  2.611
   Adj changes/node/s  .068   .069   .081   .068   .055   .058   .057

   Table 7: Results for range 200 m with minimal LSAs

Authors' Addresses

   Richard G. Ogier
   SRI International

   EMail: rich.ogier@earthlink.net or rich.ogier@gmail.com


   Phil Spagnolo
   Boeing Phantom Works

   EMail: phillipspagnolo@gmail.com