RFC 5614
Mobile Ad Hoc Network (MANET) Extension of OSPF Using Connected Dominating Set (CDS) Flooding
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.
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).
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).
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.
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.
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.
.......................................... . 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
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
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)
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 addressA.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
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.
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.
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.
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
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
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.
(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.
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
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
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 LSAsAuthors' 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