RFC 5614
Mobile Ad Hoc Network (MANET) Extension of OSPF Using Connected Dominating Set (CDS) Flooding
Network Working Group R. Ogier Request for Comments: 5614 SRI International Category: Experimental P. Spagnolo Boeing August 2009 Mobile Ad Hoc Network (MANET) Extension of OSPF Using Connected Dominating Set (CDS) FloodingAbstract
This document specifies an extension of OSPFv3 to support mobile ad hoc networks (MANETs). The extension, called OSPF-MDR, is designed as a new OSPF interface type for MANETs. OSPF-MDR is based on the selection of a subset of MANET routers, consisting of MANET Designated Routers (MDRs) and Backup MDRs. The MDRs form a connected dominating set (CDS), and the MDRs and Backup MDRs together form a biconnected CDS for robustness. This CDS is exploited in two ways. First, to reduce flooding overhead, an optimized flooding procedure is used in which only (Backup) MDRs flood new link state advertisements (LSAs) back out the receiving interface; reliable flooding is ensured by retransmitting LSAs along adjacencies. Second, adjacencies are formed only between (Backup) MDRs and a subset of their neighbors, allowing for much better scaling in dense networks. The CDS is constructed using 2-hop neighbor information provided in a Hello protocol extension. The Hello protocol is further optimized by allowing differential Hellos that report only changes in neighbor states. Options are specified for originating router-LSAs that provide full or partial topology information, allowing overhead to be reduced by advertising less topology information. Status of This Memo This memo defines an Experimental Protocol for the Internet community. It does not specify an Internet standard of any kind. Discussion and suggestions for improvement are requested. Distribution of this memo is unlimited.
Copyright Notice Copyright (c) 2009 IETF Trust and the persons identified as the document authors. All rights reserved. This document is subject to BCP 78 and the IETF Trust's Legal Provisions Relating to IETF Documents in effect on the date of publication of this document (http://trustee.ietf.org/license-info). Please review these documents carefully, as they describe your rights and restrictions with respect to this document. This document may contain material from IETF Documents or IETF Contributions published or made publicly available before November 10, 2008. The person(s) controlling the copyright in some of this material may not have granted the IETF Trust the right to allow modifications of such material outside the IETF Standards Process. Without obtaining an adequate license from the person(s) controlling the copyright in such materials, this document may not be modified outside the IETF Standards Process, and derivative works of it may not be created outside the IETF Standards Process, except to format it for publication as an RFC or to translate it into languages other than English.Table of Contents
1. Introduction ....................................................4 1.1. Terminology ................................................5 2. Overview ........................................................7 2.1. Selection of MDRs, BMDRs, Parents, and Adjacencies .........8 2.2. Flooding Procedure .........................................9 2.3. Link State Acknowledgments ................................10 2.4. Routable Neighbors ........................................10 2.5. Partial and Full Topology LSAs ............................11 2.6. Hello Protocol ............................................12 3. Interface and Neighbor Data Structures .........................12 3.1. Changes to Interface Data Structure .......................12 3.2. New Configurable Interface Parameters .....................13 3.3. Changes to Neighbor Data Structure ........................15 4. Hello Protocol .................................................17 4.1. Sending Hello Packets .....................................17 4.2. Receiving Hello Packets ...................................20 4.3. Neighbor Acceptance Condition .............................24 5. MDR Selection Algorithm ........................................25 5.1. Phase 1: Creating the Neighbor Connectivity Matrix ........27 5.2. Phase 2: MDR Selection ....................................27 5.3. Phase 3: Backup MDR Selection .............................29 5.4. Phase 4: Parent Selection .................................29 5.5. Phase 5: Optional Selection of Non-Flooding MDRs ..........30
6. Interface State Machine ........................................31 6.1. Interface States ..........................................31 6.2. Events that Cause Interface State Changes .................31 6.3. Changes to Interface State Machine ........................32 7. Adjacency Maintenance ..........................................32 7.1. Changes to Neighbor State Machine .........................33 7.2. Whether to Become Adjacent ................................34 7.3. Whether to Eliminate an Adjacency .........................35 7.4. Sending Database Description Packets ......................35 7.5. Receiving Database Description Packets ....................36 8. Flooding Procedure .............................................37 8.1. LSA Forwarding Procedure ..................................38 8.2. Sending Link State Acknowledgments ........................41 8.3. Retransmitting LSAs .......................................42 8.4. Receiving Link State Acknowledgments ......................42 9. Router-LSAs ....................................................43 9.1. Routable Neighbors ........................................44 9.2. Backbone Neighbors ........................................45 9.3. Selected Advertised Neighbors .............................45 9.4. Originating Router-LSAs ...................................46 10. Calculating the Routing Table .................................47 11. Security Considerations .......................................49 12. IANA Considerations ...........................................50 13. Acknowledgments ...............................................51 14. Normative References ..........................................51 15. Informative References ........................................51 Appendix A. Packet Formats .......................................52 A.1. Options Field ............................................52 A.2. Link-Local Signaling .....................................52 A.3. Hello Packet DR and Backup DR Fields .....................57 A.4. LSA Formats and Examples .................................57 Appendix B. Detailed Algorithms for MDR/BMDR Selection ...........62 B.1. Detailed Algorithm for Step 2.4 (MDR Selection) ..........62 B.2. Detailed Algorithm for Step 3.2 (BMDR Selection) .........63 Appendix C. Min-Cost LSA Algorithm ...............................65 Appendix D. Non-Ackable LSAs for Periodic Flooding ...............68 Appendix E. Simulation Results ...................................69
1. Introduction
This document specifies an extension of OSPFv3 [RFC5340] to support a new interface type for mobile ad hoc networks (MANETs), i.e., for broadcast-capable, multihop wireless networks in which routers and hosts can be mobile. Note that OSPFv3 is specified by describing the modifications to OSPFv2 [RFC2328]. This MANET extension of OSPFv3 is also applicable to non-mobile mesh networks using layer-3 routing. This extension does not preclude the use of any existing OSPF interface types, and is fully compatible with legacy OSPFv3 implementations. Existing OSPF interface types do not perform adequately in MANETs, due to scaling issues regarding the flooding protocol operation, inability of the Designated Router election protocol to converge in all scenarios, and large numbers of adjacencies when using a point- to-multipoint interface type. The approach taken is to generalize the concept of an OSPF Designated Router (DR) and Backup DR to multihop wireless networks, in order to reduce overhead by reducing the number of routers that must flood new LSAs and reducing the number of adjacencies. The generalized (Backup) Designated Routers are called (Backup) MANET Designated Routers (MDRs). The MDRs form a connected dominating set (CDS), and the MDRs and Backup MDRs together form a biconnected CDS for robustness (if the network itself is biconnected). By definition, each router in the MANET either belongs to the CDS or is one hop away from it. A distributed algorithm is used to select and dynamically maintain the biconnected CDS. Adjacencies are established only between (Backup) MDRs and a subset of their neighbors, thus resulting in a dramatic reduction in the number of adjacencies in dense networks, compared to the approach of forming adjacencies between all neighbor pairs. The OSPF extension is called OSPF-MDR. Hello packets are modified, using OSPF link-local signaling (LLS; see [RFC5613]), for two purposes: to provide neighbors with 2-hop neighbor information that is required by the MDR selection algorithm, and to allow differential Hellos that report only changes in neighbor states. Differential Hellos can be sent more frequently without a significant increase in overhead, in order to respond more quickly to topology changes. Each MANET router advertises a subset of its MANET neighbors as point-to-point links in its router-LSA. The choice of which neighbors to advertise is flexible, allowing overhead to be reduced by advertising less topology information. Options are specified for originating router-LSAs that provide full or partial topology information.
This document is organized as follows. Section 2 presents an overview of OSPF-MDR, Section 3 presents the new interface and neighbor data items that are required for the extension, Section 4 describes the Hello protocol, including procedures for maintaining the 2-hop neighbor information, Section 5 describes the MDR selection algorithm, Section 6 describes changes to the Interface state machine, Section 7 describes the procedures for forming adjacencies and deciding which neighbors should become adjacent, Section 8 describes the flooding procedure, Section 9 specifies the requirements and options for the contents of router-LSAs, and Section 10 describes changes in the calculation of the routing table. The appendices specify packet formats, detailed algorithms for the MDR selection algorithm, an algorithm for the selection of a subset of neighbors to advertise in the router-LSA to provide shortest-path routing, a proposed option that uses non-ackable LSAs to provide periodic flooding without the overhead of Link State Acknowledgments, and simulation results that predict the performance of OSPF-MDR in mobile networks with up to 200 nodes. Additional information and resources for OSPF-MDR can be found at http://www.manet-routing.org.1.1. Terminology
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in [RFC2119]. In addition, this document uses the following terms: MANET Interface A MANET Interface is a new OSPF interface type that supports broadcast-capable, multihop wireless networks. Two neighboring routers on a MANET interface may not be able to communicate directly with each other. A neighboring router on a MANET interface is called a MANET neighbor. MANET neighbors are discovered dynamically using a modification of OSPF's Hello protocol. MANET Router A MANET Router is an OSPF router that has at least one MANET interface. Differential Hello A Differential Hello is a Hello packet that reduces the overhead of sending full Hellos, by including only the Router IDs of neighbors whose state changed recently.
2-Hop Neighbor Information
This information specifies the bidirectional neighbors of each
neighbor. The modified Hello protocol provides each MANET router
with 2-hop neighbor information, which is used for selecting MDRs
and Backup MDRs.
MANET Designated Router (MDR)
A MANET Designated Router is one of a set of routers responsible
for flooding new LSAs, and for determining the set of adjacencies
that must be formed. The set of MDRs forms a connected dominating
set and is a generalization of the DR found in broadcast networks.
Each router runs the MDR selection algorithm for each MANET
interface, to decide whether the router is an MDR, Backup MDR, or
neither for that interface.
Backup MANET Designated Router (Backup MDR or BMDR)
A Backup MANET Designated Router is one of a set of routers
responsible for providing backup flooding when neighboring MDRs
fail. The set of MDRs and Backup MDRs forms a biconnected
dominating set. The Backup MDR is a generalization of the Backup
DR found in broadcast networks.
MDR Other
A router is an MDR Other for a particular MANET interface if it is
neither an MDR nor a Backup MDR for that interface.
Parent
Each router selects a Parent for each MANET interface. The Parent
of a non-MDR router will be a neighboring MDR if one exists. The
Parent of an MDR is always the router itself. Each non-MDR router
becomes adjacent with its Parent. The Router ID of the Parent is
advertised in the DR field of each Hello sent on the interface.
Backup Parent
If the option of biconnected adjacencies is chosen, then each MDR
Other selects a Backup Parent, which will be a neighboring MDR or
BMDR if one exists that is not the Parent. The Backup Parent of a
BMDR is always the router itself. Each MDR Other becomes adjacent
with its Backup Parent if it exists. The Router ID of the Backup
Parent is advertised in the Backup DR field of each Hello sent on
the interface.
Bidirectional Neighbor
A bidirectional neighbor is a neighboring router whose neighbor
state is 2-Way or greater.
Routable Neighbor
A bidirectional MANET neighbor becomes routable if the SPF
calculation has produced a route to the neighbor and the neighbor
satisfies a quality condition. Once a neighbor becomes routable,
it remains routable as long as it remains bidirectional. Only
routable and Full neighbors can be used as next hops in the SPF
calculation, and can be included in the router-LSA originated by
the router.
Non-Flooding MDR
A non-flooding MDR is an MDR that does not automatically flood
received LSAs back out the receiving interface, but performs
backup flooding like a BMDR. Some MDRs may declare themselves
non-flooding in order to reduce flooding overhead.
2. Overview
This section provides an overview of OSPF-MDR, including motivation
and rationale for some of the design choices.
OSPF-MDR was motivated by the desire to extend OSPF to support
MANETs, while keeping the same design philosophy as OSPF and using
techniques that are similar to those of OSPF. For example, OSPF
reduces overhead in a broadcast network by electing a Designated
Router (DR) and Backup DR, and by having two neighboring routers form
an adjacency only if one of them is the DR or Backup DR. This idea
can be generalized to a multihop wireless network by forming a
spanning tree, with the edges of the tree being the adjacencies and
the interior (non-leaf) nodes of the tree being the generalized DRs,
called MANET Designated Routers (MDRs).
To provide better robustness and fast response to topology changes,
it was decided that a router should decide whether it is an MDR based
only on local information that can be obtained from neighbors'
Hellos. The resulting set of adjacencies therefore does not always
form a tree globally, but appears to be a tree locally. Similarly,
the Backup DR can be generalized to Backup MDRs (BMDRs), to provide
robustness through biconnected redundancy. The set of MDRs forms a
connected dominating set (CDS), and the set of MDRs and BMDRs forms a
biconnected dominating set (if the network itself is biconnected).
The following subsections provide an overview of each of the main
features of OSPF-MDR, starting with a summary of how MDRs, BMDRs, and
adjacencies are selected.
2.1. Selection of MDRs, BMDRs, Parents, and Adjacencies
The MDR selection algorithm is distributed; each router selects itself as an MDR, BMDR, or other router (called an "MDR Other") based on information about its one-hop neighborhood, which is obtained from Hello packets received from neighbors. Routers are ordered lexicographically based on the tuple (RtrPri, MDR Level, RID), where RtrPri is the Router Priority, MDR Level represents the current state of the router (2 for an MDR, 1 for a BMDR, and 0 for an MDR Other), and RID is the Router ID. Routers with lexicographically larger values of (RtrPri, MDR Level, RID) are given preference for becoming MDRs. The MDR selection algorithm can be summarized as follows. If the router itself has a larger value of (RtrPri, MDR Level, RID) than all of its neighbors, it selects itself as an MDR. Otherwise, let Rmax denote the neighbor with the largest value of (RtrPri, MDR Level, RID). The router then selects itself as an MDR unless each neighbor can be reached from Rmax in at most k hops via neighbors that have a larger value of (RtrPri, MDR Level, RID) than the router itself, where k is the parameter MDRConstraint, whose default value is 3. This parameter serves to control the density of the MDR set, since the MDR set need not be strictly minimal. Similarly, a router that does not select itself as an MDR will select itself as a BMDR unless each neighbor can be reached from Rmax via two node-disjoint paths, using as intermediate hops only neighbors that have a larger value of (RtrPri, MDR Level, RID) than the router itself. When a router selects itself as an MDR, it also decides which MDR neighbors it should become adjacent with, to ensure that the set of MDRs and the adjacencies between them form a connected backbone. Each non-MDR router selects and becomes adjacent with an MDR neighbor called its Parent, thus ensuring that all routers are connected to the MDR backbone. If the option of biconnected adjacencies is chosen (AdjConnectivity = 2), then additional adjacencies are selected to ensure that the set of MDRs and BMDRs, and the adjacencies between them, form a biconnected backbone. In this case, each MDR Other selects and becomes adjacent with an MDR/BMDR neighbor called its Backup Parent, in addition to its Parent.
OSPF-MDR also provides the option of full-topology adjacencies (AdjConnectivity = 0). If this option is selected, then each router forms an adjacency with each bidirectional neighbor. Although BMDR selection is optional if AdjConnectivity is 0 or 1, it is recommended since BMDRs improve robustness by providing backup flooding. Prioritizing routers according to (RtrPri, MDR Level, RID) allows neighboring routers to agree on which routers should become an MDR, and gives higher priority to existing MDRs, which increases the lifetime of MDRs and the adjacencies between them. In addition, Parents are selected to be existing adjacent neighbors whenever possible, to avoid forming new adjacencies unless necessary. Once a neighbor becomes adjacent, it remains adjacent as long as the neighbor is bidirectional and either the neighbor or the router itself is an MDR or BMDR (similar to OSPF). The above rules reduce the rate at which new adjacencies are formed, which is important since database exchange must be performed whenever a new adjacency is formed.2.2. Flooding Procedure
When an MDR receives a new link state advertisement (LSA) on a MANET interface, it floods the LSA back out the receiving interface unless it can be determined that such flooding is unnecessary (as specified in Section 8.1). The router MAY delay the flooding of the LSA by a small random amount of time (e.g., less than 100 ms). The delayed flooding is useful for coalescing multiple LSAs in the same Link State Update packet, and it can reduce the possibility of a collision in case multiple MDRs received the same LSA at the same time. However, such collisions are usually avoided with wireless MAC protocols. When a Backup MDR receives a new LSA on a MANET interface, it waits a short interval (BackupWaitInterval), and then floods the LSA only if it has a neighbor that did not flood or acknowledge the LSA and is not known to be a neighbor of another neighbor (of the Backup MDR) that flooded the LSA. MDR Other routers never flood LSAs back out the receiving interface. To exploit the broadcast nature of MANETs, a new LSA is processed (and possibly forwarded) if it is received from any neighbor in state 2-Way or greater. The flooding procedure also avoids redundant forwarding of LSAs when multiple interfaces exist.
2.3. Link State Acknowledgments
All Link State Acknowledgment packets are multicast. An LSA is acknowledged if it is a new LSA, or if it is a duplicate LSA received as a unicast. (A duplicate LSA received as multicast is not acknowledged.) An LSA that is flooded back out the same interface is treated as an implicit acknowledgment. Link State Acknowledgments may be delayed to allow coalescing multiple acknowledgments in the same packet. The only exception is that (Backup) MDRs send a multicast Link State Acknowledgment immediately when a duplicate LSA is received as a unicast, in order to prevent additional retransmissions. Only Link State Acknowledgments from adjacent neighbors are processed, and retransmitted LSAs are sent (via unicast) only to adjacent neighbors.2.4. Routable Neighbors
In OSPF, a neighbor must typically be fully adjacent (in state Full) for it to be used in the SPF calculation. An exception exists for an OSPF broadcast network, to avoid requiring all pairs of routers in such a network to form adjacencies, which would generate a large amount of overhead. In such a network, a router can use a non- adjacent neighbor as a next hop as long as both routers are fully adjacent with the Designated Router. We define this neighbor relationship as a "routable neighbor" and extend its usage to the MANET interface type. A MANET neighbor becomes routable if it is bidirectional and the SPF calculation has produced a route to the neighbor. (A flexible quality condition may also be required.) Only routable and Full neighbors can be used as next hops in the SPF calculation, and can be included in the router-LSA originated by the router. The idea is that if the SPF calculation has produced a route to the neighbor, then it makes sense to take a "shortcut" and forward packets directly to the neighbor. The routability condition is a generalization of the way that neighbors on broadcast networks are treated in the SPF calculation. The network-LSA of an OSPF broadcast network implies that a router can use a non-adjacent neighbor as a next hop. But a network-LSA cannot describe the general topology of a MANET, making it necessary to explicitly include non-adjacent neighbors in the router-LSA. Allowing only adjacent neighbors in LSAs would either result in suboptimal routes or require a large number of adjacencies.
2.5. Partial and Full Topology LSAs
OSPF-MDR allows routers to originate both full-topology LSAs, which advertise links to all routable and Full neighbors, and partial- topology LSAs, which advertise only a subset of such links. In a dense network, partial-topology LSAs are typically much smaller than full-topology LSAs, thus achieving better scalability. Each router advertises a subset of its neighbors as point-to-point links in its router-LSA. The choice of which neighbors to advertise is flexible. As a minimum requirement, each router must advertise a minimum set of "backbone" neighbors in its router-LSA. An LSA that includes only this minimum set of neighbors is called a minimal LSA and corresponds to LSAFullness = 0. This choice results in the minimum amount of LSA flooding overhead, but does not ensure routing along shortest paths. However, it is useful for achieving scalability to networks with a large number of nodes. At the other extreme, if LSAFullness = 4, then the router originates a full-topology LSA, which includes all routable and Full neighbors. Setting LSAFullness to 1 results in min-cost LSAs, which provide routing along shortest (minimum-cost) paths. Each router decides which neighbors to include in its router-LSA based on 2-hop neighbor information obtained from its neighbors' Hellos. Each router includes in its LSA the minimum set of neighbors necessary to provide a shortest path between each pair of its neighbors. Setting LSAFullness to 2 also provides shortest-path routing, but allows the router to advertise additional neighbors to provide redundant routes. Setting LSAFullness to 3 results in MDR full LSAs, causing each MDR to originate a full-topology LSA while other routers originate minimal LSAs. This choice does not provide routing along shortest paths, but simulations have shown that it provides routing along nearly shortest paths with relatively low overhead. The above LSA options are interoperable with each other, because they all require the router-LSA to include a minimum set of neighbors, and because the construction of the router-LSA (described in Section 9.4) ensures that the router-LSAs originated by different routers are consistent. Routing along shortest paths is provided if and only if every router selects LSAFullness to be 1, 2, or 4.
2.6. Hello Protocol
OSPF-MDR uses the same Hello format as OSPFv3, but appends additional information to Hello packets using link-local signaling (LLS), in order to indicate the set of bidirectional neighbors and other information that is used by the MDR selection algorithm and the min- cost LSA algorithm. In addition to full Hellos, which include the same set of neighbor IDs as OSPFv3 Hellos, OSPF-MDR allows the use of differential Hellos, which include only the IDs of neighbors whose state (or other information) has recently changed (within the last HelloRepeatCount Hellos). 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. The default value of 2HopRefresh is 1; i.e., the default is to send only full Hellos. The default value for HelloInterval is 2 seconds. Differential Hellos are used to reduce overhead and to allow Hellos to be sent more frequently, for faster reaction to topology changes.3. Interface and Neighbor Data Structures
3.1. Changes to Interface Data Structure
The following modified or new data items are required for the Interface Data Structure of a MANET interface: Type A router that implements this extension can have one or more interfaces of type MANET, in addition to the OSPF interface types defined in [RFC2328]. State The possible states for a MANET interface are the same as for a broadcast interface. However, the DR and Backup states now imply that the router is an MDR or Backup MDR, respectively. MDR Level The MDR Level is equal to MDR (value 2) if the router is an MDR, Backup MDR (value 1) if the router is a Backup MDR, and MDR Other (value 0) otherwise. The MDR Level is used by the MDR selection algorithm. Parent The Parent replaces the Designated Router (DR) data item of OSPF. Each router selects a Parent as described in Section 5.4. The Parent of an MDR is the router itself, and the Parent of a non-MDR
router will be a neighboring MDR, if one exists. The Parent is
initialized to 0.0.0.0, indicating the lack of a Parent. Each
router advertises the Router ID of its Parent in the DR field of
each Hello sent on the interface.
Backup Parent
The Backup Parent replaces the Backup Designated Router data item
of OSPF. The Backup Parent of a BMDR is the router itself. 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 Backup Parent
is initialized to 0.0.0.0, indicating the lack of a Backup Parent.
Each router advertises the Router ID of its Backup Parent in the
Backup DR field of each Hello sent on the interface.
Router Priority
An 8-bit unsigned integer. A router with a larger Router Priority
is more likely to be selected as an MDR. The Router Priority for
a MANET interface can be changed dynamically based on any
criteria, including bandwidth capacity, willingness to be a relay
(which can depend on battery life, for example), number of
neighbors (degree), and neighbor stability. A router that has
been a (Backup) MDR for a certain amount of time can reduce its
Router Priority so that the burden of being a (Backup) MDR can be
shared among all routers. If the Router Priority for a MANET
interface is changed, then the interface variable
MDRNeighborChange must be set.
Hello Sequence Number (HSN)
The 16-bit sequence number carried by the MDR-Hello TLV. The HSN
is incremented by 1 (modulo 2^16) every time a Hello packet is
sent on the interface.
MDRNeighborChange
A single-bit variable set to 1 if a neighbor change has occurred
that requires the MDR selection algorithm to be executed.
3.2. New Configurable Interface Parameters
The following new configurable interface parameters are required for
a MANET interface. The default values for HelloInterval,
RouterDeadInterval, and RxmtInterval for a MANET interface are 2, 6,
and 7 seconds, respectively.
The default configuration for OSPF-MDR uses uniconnected adjacencies
(AdjConnectivity = 1) and partial-topology LSAs that provide
shortest-path routing (LSAFullness = 1). This is the most scalable
configuration that provides shortest-path routing. Other
configurations may be preferable in special circumstances. For example, setting LSAFullness to 4 provides full-topology LSAs, and setting LSAFullness to 0 provides minimal LSAs that minimize overhead but do not ensure shortest-path routing. Setting AdjConnectivity to 2 may improve robustness by providing a biconnected adjacency subgraph, and setting AdjConnectivity to 0 results in full-topology adjacencies. All possible configurations of the new interface parameters are functional, except that if AdjConnectivity is 0 (full-topology adjacencies), then LSAFullness must be 1, 2, or 4 (see Section 9.3). Differential Hellos should be used to reduce the size of Hello packets when the average number of neighbors is large (e.g., greater than 50). Differential Hellos are obtained by setting the parameter 2HopRefresh to an integer greater than 1, with the recommended value being 3. Good performance in simulated mobile networks with up to 160 nodes has been obtained using the default configuration with differential Hellos. Good performance in simulated mobile networks with up to 200 nodes has been obtained using the same configuration except with minimal LSAs (LSAFullness = 0). Simulation results are presented in Appendix E. Although all routers should preferably choose the same values for the new configurable interface parameters, this is not required. OSPF- MDR was carefully designed so that correct interoperation is achieved even if each router sets these parameters independently of the other routers. AdjConnectivity If equal to the default value of 1, then the set of adjacencies forms a (uni)connected graph. If equal to the optional value of 2, then the set of adjacencies forms a biconnected graph. If AdjConnectivity is 0, then adjacency reduction is not used; i.e., the router becomes adjacent with all of its neighbors. MDRConstraint A parameter of the MDR selection algorithm, which affects the number of MDRs selected and must be an integer greater than or equal to 2. The default value of 3 results in nearly the minimum number of MDRs. Values larger than 3 result in slightly fewer MDRs, and the value 2 results in a larger number of MDRs. BackupWaitInterval The number of seconds that a Backup MDR must wait after receiving a new LSA before it decides whether to flood the LSA. The default value is 0.5 second.
AckInterval
The interval between Link State Acknowledgment packets when only
delayed acknowledgments need to be sent. AckInterval MUST be less
than RxmtInterval, and SHOULD NOT be larger than 1 second. The
default value is 1 second.
LSAFullness
Determines which neighbors a router should advertise in its
router-LSA. The value 0 results in minimal LSAs that include only
"backbone" neighbors. The values 1 and 2 result in partial-
topology LSAs that provide shortest-path routing, with the value 2
providing redundant routes. The value 3 results in MDRs
originating full-topology LSAs and other routers originating
minimal LSAs. The value 4 results in all routers originating
full-topology LSAs. The default value is 1.
2HopRefresh
One out of every 2HopRefresh Hellos sent on the interface must be
a full Hello. All other Hellos are differential. The default
value is 1; i.e., the default is to send only full Hellos. If
differential Hellos are used, the recommended value of 2HopRefresh
is 3.
HelloRepeatCount
The number of consecutive Hellos in which a neighbor must be
included when its state changes, if differential Hellos are used.
This parameter must be set to 3.
3.3. Changes to Neighbor Data Structure
The neighbor states are the same as for OSPF. However, the data for
a MANET neighbor that has transitioned to the Down state must be
maintained for at least HelloInterval * HelloRepeatCount seconds, to
allow the state change to be reported in differential Hellos. The
following new data items are required for the Neighbor Data Structure
of a neighbor on a MANET interface.
Neighbor Hello Sequence Number (NHSN)
The Hello sequence number contained in the last Hello received
from the neighbor.
A-bit
The A-bit copied from the MDR-Hello TLV of the last Hello received
from the neighbor. This bit is 1 if the neighbor is using full-
topology adjacencies, i.e., is not using adjacency reduction.
FullHelloRcvd
A single-bit variable equal to 1 if a full Hello has been received
from the neighbor.
Neighbor's MDR Level
The MDR Level of the neighbor, based on the DR and Backup DR
fields of the last Hello packet received from the neighbor or from
the MDR-DD TLV in a Database Description (DD) packet received from
the neighbor.
Neighbor's Parent
The neighbor's choice for Parent, obtained from the DR field of
the last Hello packet received from the neighbor or from the MDR-
DD TLV in a DD packet received from the neighbor.
Neighbor's Backup Parent
The neighbor's choice for Backup Parent, obtained from the Backup
DR field of the last Hello packet received from the neighbor or
from the MDR-DD TLV in a DD packet received from the neighbor.
Child
A single-bit variable equal to 1 if the neighbor is a child, i.e.,
if the neighbor has selected the router as a (Backup) Parent.
Dependent Neighbor
A single-bit variable equal to 1 if the neighbor is a Dependent
Neighbor, which is decided by the MDR selection algorithm. Each
MDR/BMDR router becomes adjacent with its Dependent Neighbors
(which are also MDR/BMDR routers) to form a connected backbone.
The set of all Dependent Neighbors on a MANET interface is called
the Dependent Neighbor Set (DNS) for the interface.
Dependent Selector
A single-bit variable equal to 1 if the neighbor has selected the
router to be dependent.
Selected Advertised Neighbor (SAN)
A single-bit variable equal to 1 if the neighbor is a Selected
Advertised Neighbor. Selected Advertised Neighbors are neighbors
that the router has selected to be included in the router-LSA,
along with other neighbors that are required to be included. The
set of all Selected Advertised Neighbors on a MANET interface is
called the Selected Advertised Neighbor Set (SANS) for the
interface.
Routable
A single-bit variable equal to 1 if the neighbor is routable.
Neighbor's Bidirectional Neighbor Set (BNS)
The neighbor's set of bidirectional neighbors, which is updated
when a Hello is received from the neighbor.
Neighbor's Dependent Neighbor Set (DNS)
The neighbor's set of Dependent Neighbors, which is updated when a
Hello is received from the neighbor.
Neighbor's Selected Advertised Neighbor Set (SANS)
The neighbor's set of Selected Advertised Neighbors, which is
updated when a Hello is received from the neighbor.
Neighbor's Link Metrics
The link metric for each of the neighbor's bidirectional
neighbors, obtained from the Metric TLV appended to Hello packets.
(page 17 continued on part 2)
