Tech-invite3GPPspaceIETF RFCsSIP
93929190898887868584838281807978777675747372717069686766656463626160595857565554535251504948474645444342414039383736353433323130292827262524232221201918171615141312111009080706050403020100
in Index   Prev   Next

RFC 5614

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

Pages: 71
Experimental
Updated by:  7038
Part 1 of 4 – Pages 1 to 17
None   None   Next

Top   ToC   RFC5614 - Page 1
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) Flooding

Abstract

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.
Top   ToC   RFC5614 - Page 2
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
Top   ToC   RFC5614 - Page 3
   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
Top   ToC   RFC5614 - Page 4

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.
Top   ToC   RFC5614 - Page 5
   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.
Top   ToC   RFC5614 - Page 6
   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.
Top   ToC   RFC5614 - Page 7
   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.
Top   ToC   RFC5614 - Page 8

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.
Top   ToC   RFC5614 - Page 9
   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.
Top   ToC   RFC5614 - Page 10

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.
Top   ToC   RFC5614 - Page 11

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.
Top   ToC   RFC5614 - Page 12

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
Top   ToC   RFC5614 - Page 13
      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
Top   ToC   RFC5614 - Page 14
   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.
Top   ToC   RFC5614 - Page 15
   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.
Top   ToC   RFC5614 - Page 16
   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.
Top   ToC   RFC5614 - Page 17
   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)

Next Section