tech-invite   World Map     

IETF     RFCs     Groups     SIP     ABNFs    |    3GPP     Specs     Gloss.     Arch.     IMS     UICC    |    Misc.    |    search     info

RFC 5614

Experimental
Pages: 71
Top     in Index     Prev     Next
in Group Index     Prev in Group     Next in Group     Group: OSPF

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

Part 1 of 4, p. 1 to 17
None       Next RFC Part

Updated by:    7038


Top       ToC       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.

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       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       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       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       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       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       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       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       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       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       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       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       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       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       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       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 RFC Part