[Docs] [txt|pdf] [Tracker] [WG] [Email] [Nits]

Versions: 00 01 02 03 04 05 RFC 5614

Network Working Group                                         R. Ogier
Internet-Draft                                       SRI International
Intended status: Experimental                              P. Spagnolo
Expires: August 17, 2008                                        Boeing
                                                     February 17, 2008


               MANET Extension of OSPF using CDS Flooding
                    draft-ietf-ospf-manet-mdr-00.txt

Status of this Memo

   By submitting this Internet-Draft, each author represents that any
   applicable patent or other IPR claims of which he or she is aware
   have been or will be disclosed, and any of which he or she becomes
   aware will be disclosed, in accordance with Section 6 of BCP 79.

   Internet-Drafts are working documents of the Internet Engineering
   Task Force (IETF), its areas, and its working groups.  Note that
   other groups may also distribute working documents as Internet-
   Drafts.

   Internet-Drafts are draft documents valid for a maximum of six months
   and may be updated, replaced, or obsoleted by other documents at any
   time.  It is inappropriate to use Internet-Drafts as reference
   material or to cite them other than as "work in progress."

   The list of current Internet-Drafts can be accessed at
   http://www.ietf.org/1id-abstracts.html
   The list of Internet-Draft Shadow Directories can be accessed at
   http://www.ietf.org/shadow.html

   This Internet-Draft will expire on August 17, 2008.

Copyright Notice

   Copyright (C) The IETF Trust (2008).

Abstract

   This document specifies an extension of OSPF for IPv6 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



Ogier & Spagnolo         Expires August 17, 2008                [Page 1]

Internet-Draft           MANET Extension of OSPF           February 2008


   is used in which only (Backup) MDRs flood new 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.


Table of Contents

   1    Introduction ................................................. 4
   1.1  Terminology .................................................. 5
   2    Overview ..................................................... 7
   2.1  Selection of MDRs, BMDRs, Parents, and Adjacencies ........... 7
   2.2  Flooding Procedure ........................................... 9
   2.3  Link State Acknowledgments ................................... 9
   2.4  Routable Neighbors ........................................... 9
   2.5  Partial and Full Topology LSAs .............................. 10
   2.6  Hello Protocol .............................................. 11
   3    Interface and Neighbor Data Structures ...................... 11
   3.1  Changes to Interface Data Structure ......................... 11
   3.2  New Configurable Interface Parameters ....................... 12
   3.3  Changes to Neighbor Data Structure .......................... 14
   4    Hello Protocol .............................................. 16
   4.1  Sending Hello Packets ....................................... 16
   4.2  Receiving Hello Packets ..................................... 19
   4.3  Neighbor Acceptance Condition ............................... 22
   5    MDR Selection Algorithm ..................................... 23
   5.1  Phase 1: Creating the Neighbor Connectivity Matrix .......... 25
   5.2  Phase 2: MDR Selection ...................................... 25
   5.3  Phase 3: Backup MDR Selection ............................... 27
   5.4  Phase 4: Selection of the (Backup) MDR Parent ............... 27
   5.5  Phase 5: Optional Selection of Non-Flooding MDRs ............ 28
   6    Interface State Machine ..................................... 28
   6.1  Interface states ............................................ 28
   6.2  Events that cause interface state changes ................... 29
   6.3  Changes to Interface State Machine .......................... 29
   7    Adjacency Maintenance ....................................... 30
   7.1  Changes to Neighbor State Machine ........................... 31
   7.2  Whether to Become Adjacent .................................. 32
   7.3  Whether to Eliminate an Adjacency ........................... 33
   7.4  Sending Database Description Packets ........................ 33
   7.5  Receiving Database Description Packets ...................... 33



Ogier & Spagnolo         Expires August 17, 2008                [Page 2]

Internet-Draft           MANET Extension of OSPF           February 2008


   8    Flooding Procedure .......................................... 34
   8.1  LSA Forwarding Procedure .................................... 35
   8.2  Sending Link State Acknowledgments .......................... 38
   8.3  Retransmitting LSAs ......................................... 39
   8.4  Receiving Link State Acknowledgments ........................ 39
   9    Originating LSAs ............................................ 40
   9.1  Routable Neighbors .......................................... 41
   9.2  Partial and Full Topology LSAs .............................. 42
   10   Calculating the Routing Table ............................... 44
   11   Security Considerations ..................................... 45
   12   IANA Considerations ......................................... 45
   13   Acknowledgments ............................................. 45
   14   Normative References ........................................ 45
   15   Informative References ...................................... 46
   A    Packet Formats .............................................. 46
   A.1  Options Field ............................................... 46
   A.2  Link-Local Signaling ........................................ 46
   A.3  Hello Packet DR and Backup DR Fields ........................ 51
   A.4  LSA Formats and Examples .................................... 51
   B    Detailed Algorithms for MDR/BMDR Selection .................. 55
   B.1  Detailed Algorithm for Step 2.4 (MDR Selection) ............. 55
   B.2  Detailed Algorithm for Step 3.2 (BMDR Selection) ............ 56
   C    Min-Cost LSA Algorithm ...................................... 58
   D    Non-Ackable LSAs for Periodic Flooding ...................... 62
        Authors Addresses ........................................... 62
        Intellectual Property and Copyright Statements .............. 63

























Ogier & Spagnolo         Expires August 17, 2008                [Page 3]

Internet-Draft           MANET Extension of OSPF           February 2008


1.  Introduction

   This document specifies an extension of OSPF for IPv6 [RFC2328,
   RFC2740], 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.  This extension is also
   applicable to non-mobile mesh networks using layer-3 routing.
   Existing OSPF interface types do not perform adequately in such
   environments, 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.

   An OSPF implementation that is extended with this MANET interface
   type does not preclude the use of any existing interface types, and
   is fully compatible with a legacy OSPF implementation.  MANET
   networks are represented externally as Point-to-Multipoint networks,
   although the design borrows concepts used by the OSPF broadcast
   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.  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],
   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



Ogier & Spagnolo         Expires August 17, 2008                [Page 4]

Internet-Draft           MANET Extension of OSPF           February 2008


   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 what to include in router-LSAs, and
   Section 10 describes changes in the calculation of the routing table.

   The appendix specifies 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, and a proposed option that uses "non-ackable" LSAs to
   provide periodic flooding that reduces overhead in highly mobile
   networks.

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 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, which takes advantage of
      the broadcast capability.

   MANET Router
      An OSPF router that has at least one MANET interface.

   Differential Hello
      A Hello packet that reduces the overhead of sending full Hellos,
      by including only the Router IDs of neighbors whose state changed
      recently.





Ogier & Spagnolo         Expires August 17, 2008                [Page 5]

Internet-Draft           MANET Extension of OSPF           February 2008


   2-Hop Neighbor Information
      Information that 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)
      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 the broadcast network.

   Backup MANET Designated Router (Backup MDR or BMDR)
      One of a set of routers responsible for providing backup flooding
      when neighboring MDRs fail, and for determining the set of
      adjacencies that must be formed.  The set of MDRs and Backup MDRs
      forms a biconnected dominating set.  The Backup MDR is a
      generalization of the Backup DR found in the broadcast network.

   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.

   (Backup) MDR Parent
      Each Backup MDR and MDR Other selects a Parent, which will be a
      neighboring MDR if one exists.  If the option of biconnected
      adjacencies is chosen, then each MDR Other also selects a Backup
      Parent, which will be a neighboring MDR/BMDR if one exists that is
      not the Parent.  Each router forms an adjacency with its Parent
      and its Backup Parent (if it exists).

   Bidirectional Neighbor
      A neighboring router whose neighbor state is 2-Way or greater.
      The set of such neighbors is called the Bidirectional Neighbor Set
      (BNS).

   Routable Neighbor
      A bidirectional MANET neighbor becomes routable if its state is
      Full, or 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 MANET neighbors can be used
      as next hops in the SPF calculation, and can be included in LSAs
      originated by the router.

   Non-flooding MDR
      An MDR that does not immediately flood received LSAs back out the
      receiving interface.  Some MDRs may declare themselves non-



Ogier & Spagnolo         Expires August 17, 2008                [Page 6]

Internet-Draft           MANET Extension of OSPF           February 2008


      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 neighbor's
   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.

   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



Ogier & Spagnolo         Expires August 17, 2008                [Page 7]

Internet-Draft           MANET Extension of OSPF           February 2008


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

   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.






Ogier & Spagnolo         Expires August 17, 2008                [Page 8]

Internet-Draft           MANET Extension of OSPF           February 2008


2.2.  Flooding Procedure

   When an MDR receives a new LSA on a MANET interface, it immediately
   floods the LSA back out the receiving interface unless it can be
   determined that such flooding is unnecessary.  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 up to AckInterval seconds to allow coalescing multiple
   acknowlegments 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.  All fully adjacent neighbors are routable, but
   some neighbors for which a full adjacency does not exist may be
   routable if other criteria are met.

   A MANET neighbor becomes routable if its state is Full, or if it is
   bidirectional and the SPF calculation has produced a route to the



Ogier & Spagnolo         Expires August 17, 2008                [Page 9]

Internet-Draft           MANET Extension of OSPF           February 2008


   neighbor.  (A flexible quality condition may also be required.)  Only
   routable MANET 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 paths or would require a large number of adjacencies.

2.5.  Partial and Full Topology LSAs

   This specification allows routers to originate both full-topology
   LSAs, which advertise links to all routable 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 routable neighbors as point-
   to-point connections in its router-LSA.  The choice of which
   neighbors to advertise is flexible, and is determined by the
   configurable parameter LSAFullness.  As a minimum requirement, each
   router must advertise a minimum set of "backbone" neighbors in its
   router-LSA.  This minimum choice corresponds to LSAFullness = 0.
   This choice results in the minimum amount of LSA flooding overhead,
   but does not provide routing along shortest paths.  At the other
   extreme, if LSAFullness = 4, then each router originates a full LSA,
   which includes all routable neighbors.

   Setting LSAFullness to 1 or 2 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.  If LSAFullness =
   2, then redundant paths are provided, to increase robustness and/or
   allow multiple equal-cost routes to each destination.

   Setting LSAFullness to 3 results in MDR full LSAs.  Each (Backup) MDR
   originates a full LSA that includes all routable neighbors, while
   each MDR Other originates minimal LSAs.  This choice does not provide
   routing along shortest paths, but simulations have shown that it



Ogier & Spagnolo         Expires August 17, 2008               [Page 10]

Internet-Draft           MANET Extension of OSPF           February 2008


   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.2.3) ensures that the router-LSAs originated by different routers
   are consistent.

2.6.  Modified 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).

   Differential Hellos are sent every HelloInterval seconds, except when
   full Hellos are sent, which happens once every 2HopRefresh Hellos.
   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 RFC 2328.

   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,



Ogier & Spagnolo         Expires August 17, 2008               [Page 11]

Internet-Draft           MANET Extension of OSPF           February 2008


      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.

   MDR Parent
      Each non-MDR router selects an MDR Parent, as described in Section
      5.4.  The MDR Parent will be a neighboring MDR, if one exists.
      The MDR Parent is initialized to 0.0.0.0, indicating the lack of
      an MDR Parent.  A non-MDR router includes the Router ID of its MDR
      Parent in the DR field of each Hello sent on the interface.

   Backup MDR Parent
      If the option of biconnected adjacencies is chosen, then each MDR
      Other selects a Backup MDR Parent, as described in Section 5.4.
      The Backup MDR Parent will be a neighboring MDR/BMDR, if one
      exists that is not the MDR Parent.  The Backup MDR Parent is
      initialized to 0.0.0.0, indicating the lack of a Backup MDR
      Parent.  An MDR Other includes the Router ID of its Backup MDR
      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 Hello TLV.  The HSN is
      incremented by 1 every time a (differential or full) Hello 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.



Ogier & Spagnolo         Expires August 17, 2008               [Page 12]

Internet-Draft           MANET Extension of OSPF           February 2008


   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 increases robustness by providing a biconnected adjacency subgraph,
   and setting AdjConnectivity to 0 results in full-topology
   adjacencies.

   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. The default value of 3 results in nearly
      the minimum number of MDRs. The optional 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.  Default
      value is 0.5 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 value 2
      providing redundant paths.  The value 3 results in (Backup) MDRs
      originating full LSAs and other routers originating minimal LSAs.
      The value 4 results in all routers originating full LSAs.  The
      default value is 1.

   AckInterval
      The maximum number of seconds that an acknowledgment may be held



Ogier & Spagnolo         Expires August 17, 2008               [Page 13]

Internet-Draft           MANET Extension of OSPF           February 2008


      before it is multicast so that acknowledgments may be coalesced.
      The default value is 2 seconds.

   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 Hello TLV of the last Hello received
      from the neighbor.  This bit is 1 if the neighbor 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 TLV in a DD packet received from the neighbor.

   Neighbor's MDR Parent
      The neighbor's choice for MDR Parent, obtained from the DR field
      of the last Hello packet received from the neighbor or from the
      MDR TLV in a DD packet received from the neighbor.





Ogier & Spagnolo         Expires August 17, 2008               [Page 14]

Internet-Draft           MANET Extension of OSPF           February 2008


   Neighbor's Backup MDR Parent
      The neighbor's choice for Backup MDR Parent, obtained from the
      Backup DR field of the last Hello packet received from the
      neighbor or from the MDR 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) MDR 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.
      Dependent Neighbors become adjacent.  The set of all Dependent
      Neighbors is called the Dependent Neighbor Set (DNS).

   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. The set of all Selected Advertised Neighbors
      is called the Selected Advertised Neighbor Set (SANS).  The SANS
      consists of neighbors that the router has selected to be included
      in the router-LSA, along with other neighbors that are required to
      be included.

   Routable
      A single-bit variable equal to 1 if the neighbor is routable. A
      neighbor is routable if either its state is Full, or the routing
      table includes a route to the neighbor.  Only routable neighbors
      are included in the router-LSA and are allowed as next hops in the
      routing table.

   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.





Ogier & Spagnolo         Expires August 17, 2008               [Page 15]

Internet-Draft           MANET Extension of OSPF           February 2008


   Neighbor's Link Metrics
      The link metric for each of the neighbor's bidirectional
      neighbors, obtained from the Metric TLV appended to each Hello.

4.  Hello Protocol

   The MANET interface utilizes Hellos for neighbor discovery and for
   enabling neighbors to learn 2-hop neighbor information.  The protocol
   is flexible because it allows the use of full or differential Hellos.
   Full Hellos list all neighbors in state Init or above, as in OSPFv3,
   whereas differential Hellos list only neighbors whose status as a
   bidirectional neighbor, Dependent Neighbor, or Selected Advertised
   Neighbor has recently changed.  Differential Hellos are used to
   reduce overhead, and they allow Hellos to be sent more frequently
   (for faster reaction to topology changes).  If differential Hellos
   are used, full Hellos are sent less frequently to ensure that all
   neighbors have current 2-hop neighbor information.

4.1.  Sending Hello Packets

   Hello packets are sent according to [RFC2740] Section 3.2.1.1 and
   [RFC2328] Section 9.5 with the following MANET specific
   specifications beginning after paragraph 3 of Section 9.5.  The Hello
   packet format is defined in [RFC2740] A.3.2, except for the ordering
   of the Neighbor IDs and the meaning of the DR and Backup DR fields as
   described below.

   Similar to [RFC2328], the DR and Backup DR fields indicate whether
   the router is an MDR or Backup MDR.  If the router is an MDR, then
   the DR field is the router's own Router ID, and if the router is a
   Backup MDR, then the Backup DR field is the router's own Router ID.
   These fields are also used to advertise the router's MDR Parent and
   Backup MDR Parent, as specified in Section A.3 and Section 5.4.

   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.  If 2HopRefresh is set to 1, then all
   Hellos are full (the default).

   The neighbor IDs included in the body of each Hello are divided into
   the following five disjoint lists of neighbors (some of which may be
   empty), and must appear in the following order:

   List 1. Neighbors whose state recently changed to Down (included
           only in differential Hellos).
   List 2. Neighbors in state Init.
   List 3. Dependent Neighbors.



Ogier & Spagnolo         Expires August 17, 2008               [Page 16]

Internet-Draft           MANET Extension of OSPF           February 2008


   List 4. Selected Advertised Neighbors.
   List 5. Unselected bidirectional neighbors, defined as bidirectional
           neighbors that are neither Dependent nor Selected Advertised
           Neighbors.

   Note that all neighbors in Lists 3 through 5 are bidirectional
   neighbors.  These lists are used to update the neighbor's
   Bidirectional Neighbor Set (BNS), Dependent Neighbor Set (DNS), and
   Selected Advertised Neighbor Set (SANS) when a Hello is received.

   Note that the above five lists are disjoint, so each neighbor can
   appear in at most one list.  Also note that some or all of the five
   lists can be empty.

   Link-local signaling (LLS) is used to append up to two TLVs to each
   MANET Hello packet.  The format for LLS is given in Section A.2.  The
   Hello TLV is appended to each (full or differential) MANET Hello
   packet.  It indicates whether the Hello is full or differential, and
   gives the Hello Sequence Number (HSN) and the number of neighbor IDs
   in each of Lists 1 through 4 defined above.  The size of List 5 is
   then implied by the packet length field of the Hello.  The format of
   the Hello TLV is given in Section A.2.3.

   In both full and differential Hellos, the appended Hello TLV is built
   as follows.

   o  The Sequence Number field is set to the current HSN for the
      interface; the HSN is then incremented.

   o  The D-bit of the Hello TLV is set to 1 for a differential Hello
      and 0 for a full Hello.

   o  The A-bit of the Hello TLV is set to 1 if AdjConnectivity is 0
      (the router is not using adjacency reduction); otherwise it is set
      to 0.

   o  The N1, N2, N3, and N4 fields are set to the number of neighbor
      IDs in the body of the Hello that are in List 1, List 2, List 3,
      and List 4, respectively.  (N1 is always zero in a full Hello.)

   If LSAFullness is 1 or 2, a Metric TLV is appended to each MANET
   Hello packet.  It advertises link costs to neighbors, to allow the
   selection of neighbors to include in partial-topology LSAs.  The
   format of the Metric TLV is given in Section A.2.5.  The I bit of the
   Metric TLV can be set to 0 or 1.  If the I bit is set to 0, then the
   Metric TLV does not contain neighbor IDs, and contains the metric for
   each bidirectional neighbor listed in the (full or differential)
   Hello, in the same order.  If the I bit is set to 1, then the Metric



Ogier & Spagnolo         Expires August 17, 2008               [Page 17]

Internet-Draft           MANET Extension of OSPF           February 2008


   TLV includes the neighbor ID and metric for each bidirectional
   neighbor listed in the Hello whose metric is not equal to the Default
   Metric field of the TLV.

   The I bit should be chosen to minimize the size of the Metric TLV.
   This can be achieved by choosing the the I bit to be 1 if and only if
   the number of bidirectional neighbors listed in the Hello whose
   metric differs from the Default Metric field is less than 1/3 of the
   total number of bidirectional neighbors listed in the Hello.

   For example, if all neighbors have the same metric, then the I bit
   should be set to 1, with the Default Metric equal to this metric,
   avoiding the need to include neighbor IDs and corresponding metrics
   in the TLV.  At the other extreme, if all neighbors have different
   metrics, then the I bit should be set to 0 to avoid listing the same
   neighbor IDs in both the body of the Hello and the Metric TLV.

   In both full and differential Hello packets, the L bit is set in the
   Hello's option field to indicate LLS.

4.1.1.  Full Hello Packet

   In a full Hello, the neighbor ID list includes all neighbors in state
   Init or higher, in the order described above.  The Hello TLV is built
   as described above, and if LSAFullness is 1 or 2, the Metric TLV is
   built as specified in Section A.2.5.

4.1.2.  Differential Hello Packet

   In a differential Hello, the five neighbor ID lists defined in
   Section 4.1 are populated as follows:

   List 1 includes all neighbors in state Down that transitioned to this
   state within the last HelloRepeatCount Hellos.

   List 2 includes all neighbors in state Init that transitioned to this
   state within the last HelloRepeatCount Hellos.

   List 3 includes all Dependent Neighbors that became Dependent within
   the last HelloRepeatCount Hellos.

   List 4 includes all Selected Advertised Neighbors that became
   Selected Advertised Neighbors within the last HelloRepeatCount
   Hellos.

   List 5 includes all unselected bidirectional neighbors (defined in
   Section 4.1) that became unselected bidirectional neighbors within
   the last HelloRepeatCount Hellos.



Ogier & Spagnolo         Expires August 17, 2008               [Page 18]

Internet-Draft           MANET Extension of OSPF           February 2008


   In addition, if a Metric TLV is appended to the Hello, then each
   bidirectional neighbor whose link metric changed within the last
   HelloRepeatCount Hellos must also be included in the body of the
   Hello (in the appropriate list).

4.2.  Receiving Hello Packets

   A Hello packet received on a MANET interface is processed as
   described in [RFC2740] Section 3.2.2.1 and the first two paragraphs
   of [RFC2328] Section 10.5, followed by the processing specified
   below.

   The source of a received Hello packet is identified by the Router ID
   found in the Hello's OSPF packet header.  If a matching neighbor
   cannot be found in the interface's data structure, one is created
   with the Neighbor ID set to the Router ID found in the OSPF packet
   header, the state initialized to Down, all MANET-specific neighbor
   variables (specified in Section 3.3) initialized to zero, and the
   neighbor's DNS, SANS, and BNS initialized to empty sets.

   The neighbor structure's Router Priority is set to the value of the
   corresponding field in the received Hello packet.  The Neighbor's MDR
   Parent is set to the value of the DR field, and the Neighbor's Backup
   MDR Parent is set to the value of the Backup DR field.

   Now the rest of the Hello Packet is examined, generating events to be
   given to the neighbor and interface state machines.  These state
   machines are specified either to be executed or scheduled (see
   [RFC2328] Section 4.4 "Tasking support").  For example, by specifying
   below that the neighbor state machine be executed in line, several
   neighbor state transitions may be affected by a single received
   Hello.

   o  If the L bit in the options field is not set, then an error has
      occurred and the Hello is discarded.

   o  If the LLS contains a Hello TLV, the neighbor state machine is
      executed with the event HelloReceived.  Otherwise, an error has
      occurred and the Hello is discarded.

   o  The Hello Sequence Number and the A-bit in the Hello TLV are
      copied to the neighbor's data structure.

   o  The DR and Backup DR fields are processed as follows.

      (1) If the DR field is equal to the neighbor's Router ID,
          set the neighbor's MDR Level to MDR.




Ogier & Spagnolo         Expires August 17, 2008               [Page 19]

Internet-Draft           MANET Extension of OSPF           February 2008


      (2) Else if the Backup DR field is equal to the neighbor's
          Router ID, set the neighbor's MDR Level to Backup MDR.

      (3) Else, set the neighbor's MDR Level to MDR Other.

      (4) If the DR or Backup DR field is equal to the router's own
          Router ID, the neighbor's Child variable is set to 1;
          otherwise it is set to zero.

   The neighbor ID list of the Hello is divided as follows into the five
   lists defined in Section 4.1, where N1, N2, N3, and N4 are obtained
   from the corresponding fields of the Hello TLV.  List 1 is defined to
   be the first N1 neighbor IDs, List 2 is defined to be the next N2
   neighbor IDs, List 3 is defined to be the next N3 neighbor IDs, List
   4 is defined to be the next N4 neighbor IDs, and List 5 is defined to
   be the remaining neighbor IDs in the Hello.

   Further processing of the Hello depends on whether it is full or
   differential, which is indicated by the value of the D-bit of the
   Hello TLV.

4.2.1.  Full Hello Packet

   If the received Hello is full (the D-bit of the Hello TLV is 0), the
   following steps are performed:

   o  If the N1 field of the Hello TLV is not zero, then an error has
      occurred and the Hello is discarded.  Otherwise, set FullHelloRcvd
      to 1.

   o  In the neighbor structure, modify the neighbor's DNS to equal the
      set of neighbor IDs in the Hello's List 3, modify the neighbor's
      SANS to equal the set of neighbor IDs in the Hello's List 4, and
      modify the neighbor's BNS to equal the set of neighbor IDs in the
      union of Lists 3, 4, and 5.

   o  If the router itself appears in the Hello's neighbor ID list, the
      neighbor state machine is executed with the event 2-WayReceived
      after the Hello is processed.  Otherwise, the neighbor state
      machine is executed with the event 1-WayReceived after the Hello
      is processed.

4.2.2.  Differential Hello Packet

   If the received Hello is differential (the D-bit of the Hello TLV is
   1), the following steps are performed:

   (1) For each neighbor ID in List 1 or List 2 of the Hello:



Ogier & Spagnolo         Expires August 17, 2008               [Page 20]

Internet-Draft           MANET Extension of OSPF           February 2008


       o  Remove the neighbor ID from the neighbor's DNS, SANS,
          and BNS, if it belongs to the neighbor set.

   (2) For each neighbor ID in List 3 of the Hello:

       o  Add the neighbor ID to the neighbor's DNS and BNS, if it
          does not belong to the neighbor set.

       o  Remove the neighbor ID from the neighbor's SANS, if it
          belongs to the neighbor set.

   (3) For each neighbor ID in List 4 of the Hello:

       o  Add the neighbor ID to the neighbor's SANS and BNS, if it
          does not belong to the neighbor set.

       o  Remove the neighbor ID from the neighbor's DNS, if it
          belongs to the neighbor set.

   (4) For each neighbor ID in List 5 of the Hello:

       o  Add the neighbor ID to the neighbor's BNS, if it does not
          belong to the neighbor set.

       o  Remove the neighbor ID from the neighbor's DNS and SANS, if
          it belongs to the neighbor set.

   (5) If the router's own RID appears in List 1, execute the neighbor
       state machine with the event 1-WayReceived after the Hello is
       processed.

   (6) If the router's own RID appears in List 2, 3, 4, or 5, execute
       the neighbor state machine with the event 2-WayReceived after
       the Hello is processed.

   (7) If the router's own RID does not appear in the Hello's neighbor
       ID list, and the neighbor state is 2-Way or greater, and the
       Hello Sequence Number is less than or equal to the previous
       sequence number plus HelloRepeatCount, then the neighbor state
       machine is executed with the event 2-WayReceived after the Hello
       is processed (the state does not change).

   (8) If 2-WayReceived is not executed, then 1-WayReceived is executed
       after the Hello is processed.

4.2.3.  Additional Processing for Both Hello Types

   The following applies to both full and differential Hellos.



Ogier & Spagnolo         Expires August 17, 2008               [Page 21]

Internet-Draft           MANET Extension of OSPF           February 2008


   If the router itself appears in the neighbor's DNS, the neighbor's
   Dependent Selector variable is set to 1; otherwise it is set to 0.

   The receiving interface's MDRNeighborChange variable is set to 1 if
   any of the following changes occurred as a result of processing the
   Hello:

   o  The neighbor's state changed from less than 2-Way to 2-Way or
      greater, or vice versa.

   o  The neighbor is bidirectional and any of the following neighbor
      variables has changed: MDR Level, Router Priority, FullHelloRcvd,
      and Bidirected Neighbor Set (BNS).

   The neighbor state machine is scheduled with the event AdjOK?  if any
   of the following changes occurred as a result of processing the
   Hello:

   o  The neighbor's state changed from less than 2-Way to 2-Way or
      greater.

   o  The neighbor is bidirectional and its MDR Level has changed, or
      its Child variable or Dependent Selector variable has changed from
      0 to 1.

   If the LLS contains a Metric TLV, it is processed by updating the
   neighbor's link metrics according to the format of the Metric TLV
   specified in Section A.2.5.

   If LSAFullness is 1 or 2 (partial-topology LSAs), then the min-cost
   LSA algorithm (Appendix C) is executed and a new router-LSA is
   possibly originated as specified in Section 9.2.3 if any of the
   following changes occurred as a result of processing the Hello:

   o  The neighbor's state changed from less than 2-Way to 2-Way or
      greater, or vice versa.

   o  The neighbor is bidirectional and any of the following neighbor
      variables has changed: MDR Level, Router Priority, FullHelloRcvd,
      DNS, SANS, BNS, and MDR Parent(s).

   o  Any of the neighbor's link metrics has changed as a result of
      processing the Metric TLV.

4.3.  Neighbor Acceptance Condition

   In wireless networks, a single Hello can be received from a neighbor
   with which a poor connection exists, e.g., because the neighbor is



Ogier & Spagnolo         Expires August 17, 2008               [Page 22]

Internet-Draft           MANET Extension of OSPF           February 2008


   almost out of range.  To avoid accepting poor quality neighbors, and
   to employ hysteresis, a router may require that a stricter condition
   be satisfied before changing the state of a MANET neighbor from Down
   to Init or greater.  This condition is called the "neighbor
   acceptance condition", which by default is the reception of a single
   Hello or DD packet.  For example, the neighbor acceptance condition
   may require that 2 consecutive Hellos be received from a neighbor
   before changing the neighbor's state from Down to Init.  Other
   possible conditions include the reception of 3 consecutive Hellos, or
   the reception of 2 of the last 3 Hellos.  The neighbor acceptance
   condition may also impose thresholds on other measurements such as
   received signal strength.

   The neighbor state transition for state Down and event HelloReceived
   is thus modified (see Section 7.1) to depend on the neighbor
   acceptance condition.


5.  MDR Selection Algorithm

   This section describes the MDR selection algorithm, which determines
   determines whether the router is an MDR, Backup MDR, or MDR Other on
   a given interface.  The algorithm also selects the Dependent
   Neighbors and the (Backup) MDR Parent, which are used to decide which
   neighbors should become adjacent (see Section 7).

   The MDR selection algorithm is executed just before sending a Hello
   if the MDRNeighborChange bit is set for the interface; the bit is
   then cleared.  To simplify the implementation, the MDR selection
   algorithm MAY be executed just before sending each Hello, to avoid
   having to determine when the MDRNeighborChange bit should be set.
   After running the MDR selection algorithm, the AdjOK? event may be
   invoked for some or all neighbors as specified in Section 7.

   The purpose of the MDRs is to provide a minimal set of relays for
   flooding LSAs, and the purpose of the Backup MDRs is to provide
   backup relays to flood LSAs when flooding by MDRs does not succeed.
   The set of MDRs forms a CDS, and the set of (Backup) MDRs forms a
   biconnected CDS.  Note that there may be fewer Backup MDRs than MDRs,
   since the MDRs themselves may already provide some redundancy.

   Each MDR becomes adjacent with a subset of MDR neighbors called
   Dependent Neighbors, forming a connected backbone.  Each non-MDR
   router connects to this backbone by selecting and becoming adjacent
   with an MDR neighbor called its MDR Parent.

   If AdjConnectivity = 2, then each (Backup) MDR becomes adjacent with
   additional (Backup) MDR neighbors to form a biconnected backbone, and



Ogier & Spagnolo         Expires August 17, 2008               [Page 23]

Internet-Draft           MANET Extension of OSPF           February 2008


   each MDR Other selects and becomes adjacent with a second (Backup)
   MDR neighbor called its Backup MDR Parent, thus becoming connected to
   the backbone via two adjacencies.

   The MDR selection algorithm is a distributed CDS algorithm that uses
   2-hop neighbor information obtained from Hellos.  More specifically,
   it uses as inputs the set of bidirectional neighbors (in state 2-Way
   or greater), the triplet (MDR Level, Router Priority, Router ID) for
   each such neighbor and for the router itself, and the neighbor
   variables Bidirectional Neighbor Set (BNS) and FullHelloRcvd for each
   such neighbor.  The MDR selection algorithm can be implemented in
   O(d^2) time, where d is the number of neighbors.

   The above triplet will be abbreviated as (RtrPri, MDR Level, RID).
   The triplet (RtrPri, MDR Level, RID) is said to be larger for Router
   A than for Router B if the triplet for Router A is lexicographically
   greater than the triplet for Router B.  Routers that have larger
   values of this triplet are preferred for selection as an MDR. The
   algorithm therefore prefers routers that are already MDRs, resulting
   in a longer average MDR lifetime.

   The MDR selection algorithm consists of five phases, the last of
   which is optional.  Phase 1 creates the neighbor connectivity matrix,
   which determines which pairs of neighbors are neighbors of each
   other.  Phase 2 decides whether the calculating router is an MDR, and
   which MDR neighbors are Dependent.  Phase 3 decides whether the
   calculating router is a Backup MDR and, if AdjConnectivity = 2, which
   additional MDR/BMDR neighbors are Dependent.  Phase 4 selects the MDR
   Parent and Backup MDR Parent.

   The algorithm simplifies considerably if AdjConnectivity is 0 (full-
   topology adjacencies).  In this case, Phase 4 (parent selection) is
   not executed, and the set of Dependent Neighbors is empty.  Also,
   Phase 3 (BMDR selection) is not required if AdjConnectivity is 0 or
   1.  However, Phase 3 MUST be executed if AdjConnectivity is 2, and
   SHOULD be executed if AdjConnectivity is 0 or 1, since BMDRs improve
   robustness by providing backup flooding.

   A router that has selected itself as an MDR in Phase 2 MAY execute
   Phase 5 to possibly declare itself a non-flooding MDR.  A non-
   flooding MDR is the same as a flooding MDR except that it does not
   immediately flood received LSAs back out the receiving interface,
   because it has determined that neighboring MDRs exist that will
   ensure all neighbors are covered.  Instead, a non-flooding MDR
   performs backup flooding just like a BMDR.  A non-flooding MDR
   maintains its MDR level (rather than being demoted to a BMDR) in
   order to maximize the stability of adjacencies.  (The decision to
   form an adjacency does not depend on whether an MDR is non-flooding.)



Ogier & Spagnolo         Expires August 17, 2008               [Page 24]

Internet-Draft           MANET Extension of OSPF           February 2008


   By having MDRs declare themselves to be non-flooding when possible,
   flooding overhead is reduced.  The resulting overhead reduction can
   be dramatic for certain regular topologies, but has been found to be
   about 15% for random topologies.

   For convenience, in the following description, the term "bi-neighbor"
   will be used as an abbreviation for "bidirectional neighbor".

5.1.  Phase 1: Creating the Neighbor Connectivity Matrix

   The neighbor connectivity matrix (NCM) assigns a value of 0 or 1 for
   each pair of bi-neighbors, depending on the Bidirectional Neighbor
   Set (BNS) and the value of FullHelloRcvd for each neighbor.  NCM is a
   symmetric matrix that defines a topology graph for the set of bi-
   neighbors.  A value of 1 for a given pair of neighbors indicates that
   the neighbors are assumed to be bi-neighbors of each other in the MDR
   selection algorithm.  Letting i denote the router itself, NCM(i,j)
   and NCM(j,i) are set to 1 for each bi-neighbor j.  The value of the
   matrix is set as follows for each pair of bi-neighbors j and k.

   (1.1) If FullHelloRcvd is 1 for both neighbors j and k: NCM(j,k) =
         NCM(k,j) is 1 only if j belongs to the BNS of neighbor k and k
         belongs to the BNS of neighbor j.

   (1.2) If FullHelloRcvd is 1 for neighbor j and is 0 for neighbor k:
         NCM(j,k) = NCM(k,j) is 1 only if k belongs to the BNS of
         neighbor j.

   (1.3) If FullHelloRcvd is 0 for both neighbors j and k: NCM(j,k) =
         NCM(k,j) = 0.

   In step 1.1 above, two neighbors are considered to be bi-neighbors of
   each other only if they both agree that the other router is a bi-
   neighbor.  This provides faster response to the failure of a link
   between two neighbors, since it is likely that one router will detect
   the failure before the other router. In step 1.2 above, only neighbor
   j has reported its full BNS, so neighbor j is believed in deciding
   whether j and k are bi-neighbors of each other.  As Step 1.3
   indicates, two neighbors are assumed not to be bi-neighbors of each
   other if neither neighbor has reported its full BNS.

5.2.  Phase 2: MDR Selection

   Phase 2 depends on the parameter MDRConstraint, which affects the
   number of MDRs selected. The default value of 3 results in nearly the
   minimum number of MDRs, while the value 2 results in a larger number
   of MDRs.  If AdjConnectivity = 0 (full-topology adjacencies), then
   the following steps are modified in that Dependent Neighbors are not



Ogier & Spagnolo         Expires August 17, 2008               [Page 25]

Internet-Draft           MANET Extension of OSPF           February 2008


   selected.

   (2.1) The set of Dependent Neighbors is initialized to be empty.

   (2.2) If the router has a larger value of (RtrPri, MDR Level, RID)
         than all of its bi-neighbors, the router selects itself as an
         MDR, selects all of its MDR bi-neighbors as Dependent
         Neighbors, and if AdjConnectivity = 2, selects all of its BMDR
         bi-neighbors as Dependent Neighbors.  Else, proceed to Step
         2.3.

   (2.3) Let Rmax be the bi-neighbor with the largest value of (RtrPri,
         MDR Level, RID).

   (2.4) Using NCM to determine the connectivity of bi-neighbors,
         compute the minimum number of hops, denoted hops(u), from Rmax
         to each other bi-neighbor u, using only intermediate nodes that
         are bi-neighbors with a larger value of (RtrPri, MDR Level,
         RID) than the router itself. If no such path from Rmax to u
         exists, then hops(u) equals infinity. (See Appendix B for a
         detailed algorithm using breadth-first search.)

   (2.5) If hops(u) is at most MDRConstraint for each bi-neighbor u, the
         router selects no Dependent Neighbors, and sets its MDR Level
         as follows: If the MDR Level is currently MDR, then it is
         changed to BMDR if Phase 3 will be executed and to MDR Other if
         Phase 3 will not be executed.  Otherwise, the MDR Level is not
         changed.

   (2.6) Else, the router sets its MDR Level to MDR and selects the
         following neighbors as Dependent Neighbors: Rmax, each MDR bi-
         neighbor u such that hops(u) is greater than MDRConstraint, and
         if AdjConnectivity = 2, each BMDR bi-neighbor u such that
         hops(u) is greater than MDRConstraint.

   (2.7) If steps 2.1 through 2.6 resulted in the MDR Level changing to
         BMDR, or to MDR with AdjConnectivity equal to 1 or 2, then
         execute steps 2.1 through 2.6 again.  (This is necessary
         because the change in MDR Level can cause the set of Dependent
         Neighbors and the BFS tree to change.)

   Step 2.4 can be implemented using a breadth-first search (BFS)
   algorithm to compute min-hop paths from node Rmax to all other bi-
   neighbors, modified to allow a node as an intermediate node only if
   its value of (RtrPri, MDR Level, RID) is larger than that of the
   router itself.  A detailed description of this algorithm, which runs
   in O(d^2) time, is given in Appendix B.




Ogier & Spagnolo         Expires August 17, 2008               [Page 26]

Internet-Draft           MANET Extension of OSPF           February 2008


5.3.  Phase 3: Backup MDR Selection

   (3.1) If the MDR Level is MDR (after running Phase 2) and
         AdjConnectivity is not 2, then proceed to Phase 4.  (If the MDR
         Level is MDR and AdjConnectivity = 2, then Phase 3 may select
         additional Dependent Neighbors to create a biconnected
         backbone.)

   (3.2) Using NCM to determine the connectivity of bi-neighbors,
         determine whether or not there exist two node-disjoint paths
         from Rmax to each other bi-neighbor u, using only intermediate
         nodes that are bi-neighbors with a larger value of (RtrPri, MDR
         Level, RID) than the router itself.  (See Appendix B for a
         detailed algorithm.)

   (3.3) If there exist two such node-disjoint paths from Rmax to each
         other bi-neighbor u, then the router selects no additional
         Dependent Neighbors and sets its MDR Level to MDR Other.

   (3.4) Else, the router sets its MDR Level to Backup MDR unless it
         already selected itself as an MDR in Phase 2, and if
         AdjConnectivity = 2, adds each of the following neighbors to
         the set of Dependent Neighbors: Rmax, and each MDR/BMDR bi-
         neighbor u such that step 3.2 did not find two node-disjoint
         paths from Rmax to u.

   (3.5) If steps 3.1 through 3.4 resulted in the MDR Level changing
         from MDR Other to BMDR, then run Phases 2 and 3 again.  (This
         is necessary because running Phase 2 again can cause the MDR
         Level to change to MDR.)

   Step 3.2 can be implemented in O(d^2) time using the algorithm given
   in Appendix B.  A simpler approximate algorithm is also given, which
   results in a larger number of BMDRs.

5.4.  Phase 4: Selection of the (Backup) MDR Parent

   Each BMDR and MDR Other selects (for each MANET interface) a Parent,
   which will be a neighboring MDR if one exists.  If AdjConnectivity =
   2, then each MDR Other also selects a Backup Parent, which will be a
   neighboring MDR/BMDR if one exists that is not the Parent.  Each
   router forms an adjacency with its Parent and its Backup Parent (if
   it exists).

   For a given MANET interface, let Rmax denote the router with the
   largest value of (RtrPri, MDR Level, RID) among all bidirectional
   neighbors, if such a neighbor exists that has a larger value of
   (RtrPri, MDR Level, RID) than the router itself.  Otherwise, Rmax is



Ogier & Spagnolo         Expires August 17, 2008               [Page 27]

Internet-Draft           MANET Extension of OSPF           February 2008


   null.

   If the calculating router has selected itself as an MDR, then the
   Parent is equal to the router itself, and the Backup Parent is Rmax.
   If the router has selected itself as a BMDR, then the Backup Parent
   is equal to the router itself.

   If the router is a BMDR or MDR Other, the Parent is selected to be
   any adjacent neighbor that is an MDR, if such a neighbor exists.  If
   no adjacent MDR neighbor exists, then the Parent is selected to be
   Rmax.  (By giving preference to neighbors that are already adjacent,
   the formation of a new adjacency is avoided when possible.)

   If AdjConnectivity = 2 and the calculating router is an MDR Other,
   then the Backup Parent is selected to be any adjacent neighbor that
   is an MDR or BMDR, other than the selected Parent, if such a neighbor
   exists.  If no such neighbor exists, then the Backup Parent is
   selected to be the bidirectional neighbor, excluding the selected
   Parent, with the largest value of (RtrPri, MDR Level, RID).

5.5.  Phase 5: Optional Selection of Non-Flooding MDRs

   A router that has selected itself as an MDR MAY execute the following
   steps to possibly declare itself a non-flooding MDR.  An MDR that
   does not execute the following steps is by default a flooding MDR.

   (5.1) If the router has a larger value of (RtrPri, MDR Level, RID)
   than all of its bi-neighbors, the router is a flooding MDR.  Else,
   proceed to Step 5.2.

   (5.2) Let Rmax be the bi-neighbor that has the largest value of
   (RtrPri, MDR Level, RID).

   (5.3) Using NCM to determine the connectivity of bi-neighbors,
   compute the minimum number of hops, denoted hops(u), from Rmax to
   each other bi-neighbor u, using only intermediate nodes that are MDR
   bi-neighbors with a smaller value of (RtrPri, RID) than the router
   itself. (This can be done using BFS as in Step 2.4).

   (5.4) If hops(u) is at most MDRConstraint for each bi-neighbor u,
   then the router is a non-flooding MDR.  Else, it is a flooding MDR.


6.  Interface State Machine

6.1.  Interface states

   No new states are defined for a MANET interface.  However, the DR and



Ogier & Spagnolo         Expires August 17, 2008               [Page 28]

Internet-Draft           MANET Extension of OSPF           February 2008


   Backup states now imply that the router is an MDR or Backup MDR,
   respectively.  The following modified definitions apply to MANET
   interfaces:

   Waiting
      In this state, the router learns neighbor information from the
      Hello packets it receives, but is not allowed to run the MDR
      selection algorithm until it transitions out of the Waiting state
      (when the Wait Timer expires).  This prevents unnecessary changes
      in the MDR selection resulting from incomplete neighbor
      information.  The length of the Wait Timer is 2HopRefresh *
      HelloInterval seconds (the interval between full Hellos).

   DR Other
      The router has run the MDR selection algorithm and determined that
      it is not an MDR or a Backup MDR.

   Backup
      The router has selected itself as a Backup MDR.

   DR
      The router has selected itself as an MDR.

6.2.  Events that cause interface state changes

   All interface events defined in RFC 2328, Section 9.2 apply to MANET
   interfaces, except for BackupSeen and NeighborChange.  BackupSeen is
   never invoked for a MANET interface (since seeing a Backup MDR does
   not imply that the router itself cannot also be an MDR or Backup
   MDR).

   The event NeighborChange is replaced with the new interface variable
   MDRNeighborChange, which indicates that the MDR selection algorithm
   must be executed due to a change in neighbor information (see Section
   4.2.3).

6.3.  Changes to Interface State Machine

   This section describes the changes to the interface state machine for
   a MANET interface.  The two state transitions specified below are for
   state-event pairs that are described in RFC 2328, but have modified
   action descriptions because MDRs are selected instead of DRs.  The
   state transition in RFC 2328 for the event NeighborChange is omitted;
   instead the new interface variable MDRNeighborChange is used to
   indicate when the MDR selection algorithm needs to be executed. The
   state transition for the event BackupSeen does not apply to MANET
   interfaces, since this event is never invoked for a MANET interface.
   The interface state transitions for the events Loopback and UnloopInd



Ogier & Spagnolo         Expires August 17, 2008               [Page 29]

Internet-Draft           MANET Extension of OSPF           February 2008


   are unchanged from RFC 2328.

       State:  Down
       Event:  InterfaceUp
   New state:  Depends on action routine.

      Action:  Start the interval Hello Timer, enabling the periodic
               sending of Hello packets out the interface. If the router
               is not eligible to become an MDR (Router Priority is 0),
               the state transitions to DR Other.  Otherwise, the state
               transitions to Waiting and the single shot Wait Timer is
               started.


       State:  Waiting
       Event:  WaitTimer
   New state:  Depends on action routine.

      Action:  Run the MDR selection algorithm, which may result in a
               change to the router's MDR Level, Dependent Neighbors,
               and (Backup) MDR Parent. As a result of this calculation,
               the new interface state will be DR Other, Backup, or DR.
               As a result of these changes, the AdjOK? neighbor event
               may be invoked for some or all neighbors.  (See
               Section 7.)


7.  Adjacency Maintenance

   Adjacency forming and eliminating on non-MANET interfaces remain
   unchanged.  Adjacency maintenance on a MANET interface requires
   changes to transitions in the neighbor state machine ([RFC2328]
   Section 10.3), to deciding whether to become adjacent ([RFC2328]
   Section 10.4), sending of DD packets ([RFC2328] Section 10.8), and
   receiving of DD packets ([RFC2328] Section 10.6).  The specification
   below relates to the MANET interface only.

   Adjacencies are established with some subset of the router's
   neighbors.  Each (Backup) MDR forms adjacencies with a subset of its
   (Backup) MDR neighbors to form a biconnected backbone, and each MDR
   Other forms adjacencies with two selected (Backup) MDR neighbors
   called "parents", thus providing a biconnected subgraph of
   adjacencies.

   An adjacency maintenance decision is made when any of the following
   four events occur between a router and its neighbor.  The decision is
   made by executing the neighbor event AdjOK?.




Ogier & Spagnolo         Expires August 17, 2008               [Page 30]

Internet-Draft           MANET Extension of OSPF           February 2008


   (1) The neighbor state changes from Init to 2-Way.
   (2) The MDR Level changes for the neighbor or for the router itself.
   (3) The neighbor is selected to be the (Backup) MDR Parent.
   (4) The neighbor selects the router to be its (Backup) MDR Parent.

7.1.  Changes to Neighbor State Machine

   The following specifies new transitions in the neighbor state
   machine.

    State(s):  Down
       Event:  HelloReceived
   New state:  Depends on action routine.

      Action:  If the neighbor acceptance condition is satisfied (see
               Section 4.3), the neighbor state transitions to Init and
               the Inactivity Timer is started.  Otherwise, the neighbor
               remains in the Down state.


    State(s):  Init
       Event:  2-WayReceived
   New state:  2-Way

      Action:  Transition to neighbor state 2-Way.


    State(s):  2-Way
       Event:  AdjOK?
   New state:  Depends on action routine.

      Action:  Determine whether an adjacency should be formed with the
               neighboring router (see Section 7.2).  If not, the
               neighbor state remains at 2-Way and no further action is
               taken.

               Otherwise, the neighbor state changes to ExStart, and the
               following actions are performed.  If the neighbor has a
               larger Router ID than the router's own ID, and the
               received packet is a DD packet with the initialize (I),
               more (M), and master (MS) bits set, then execute the
               event NegotiationDone, which causes the state to
               transition to Exchange.

               Otherwise (negotiation is not complete), the router
               increments the DD sequence number in the neighbor data
               structure.  If this is the first time that an adjacency
               has been attempted, the DD sequence number should be



Ogier & Spagnolo         Expires August 17, 2008               [Page 31]

Internet-Draft           MANET Extension of OSPF           February 2008


               assigned a unique value (like the time of day clock).  It
               then declares itself master (sets the master/slave bit to
               master), and starts sending Database Description Packets,
               with the initialize (I), more (M) and master (MS) bits
               set, the MDR TLV included in an LLS, and the L bit set.
               This Database Description Packet should be otherwise
               empty.  This Database Description Packet should be
               retransmitted at intervals of RxmtInterval until the next
               state is entered (see [RFC2328] Section 10.8).


    State(s):  ExStart or greater
       Event:  AdjOK?
   New state:  Depends on action routine.

      Action:  Determine whether the neighboring router should still be
               adjacent (see Section 7.3).  If yes, there is no state
               change and no further action is necessary.  Otherwise,
               the (possibly partially formed) adjacency must be
               destroyed.  The neighbor state transitions to 2-Way.  The
               Link state retransmission list, Database summary list,
               and Link state request list are cleared of LSAs.

7.2.  Whether to Become Adjacent

   The following defines the method to determine if an adjacency should
   be formed between neighbors in state 2-Way.  The following procedure
   does not depend on whether AdjConnectivity is 1 or 2, but the
   selection of Dependent Neighbors (by the MDR selection algorithm)
   depends on AdjConnectivity.

   If adjacency reduction is not used (AdjConnectivity is 0), then an
   adjacency is formed with each neighbor in state 2-Way.  Otherwise an
   adjacency is formed with a neighbor in state 2-Way if any of the
   following conditions is true:

   (1) The router is a (Backup) MDR and the neighbor is a (Backup)
       MDR and is either a Dependent Neighbor or a Dependent Selector.

   (2) The router is a (Backup) MDR and the neighbor is a child.

   (3) The neighbor is a (Backup) MDR and is the router's (Backup)
       Parent.

   (4) The neighbor is not using adjacency reduction, as indicated
       by the A-bit of the Hello TLV appended to the last Hello
       received from the neighbor.




Ogier & Spagnolo         Expires August 17, 2008               [Page 32]

Internet-Draft           MANET Extension of OSPF           February 2008


   Otherwise, an adjacency is not established and the neighbor remains
   in state 2-Way.

7.3.  Whether to Eliminate an Adjacency

   The following defines the method to determine if an adjacency should
   be eliminated between neighbors in a state greater than 2-way.  An
   adjacency is maintained if one of the following is true.

   (1) The router is an MDR.
   (2) The router is a Backup MDR.
   (3) The neighbor is an MDR.
   (4) The neighbor is a Backup MDR.

   Otherwise, the adjacency MAY be eliminated.

7.4  Sending Database Description Packets

   Sending a DD packet on a MANET interface is the same as [RFC2740]
   Section 3.2.1.2 and [RFC2328] Section 10.8 with the following
   additions to paragraph 3 of Section 10.8.

   If the neighbor state is ExStart, the standard initialization packet
   is sent with an MDR TLV appended using LLS, and the L bit is set in
   the DD packet's option field.  The DR and Backup DR fields of the MDR
   TLV are set exactly the same as the DR and Backup DR fields of a
   Hello sent on the same interface, as specified in Section A.3.

7.5.  Receiving Database Description Packets

   Processing a DD packet received on a MANET interface is the same as
   [RFC2328] Section 10.6, except for the changes described in this
   section.  The following additional steps are performed before
   processing the packet based on neighbor state in paragraph 3 of
   Section 10.6.

   o  If the DD packet's L bit is set in the options field and an MDR
      TLV is appended, then the MDR TLV is processed as follows.

      (1) If the DR field is equal to the neighhor's Router ID,
          (a) Set the MDR Level of the neighbor to MDR.
          (b) Set the neighbor's Dependent Selector variable to 1.

      (2) Else if the Backup DR field is equal to the neighbor's
          Router ID,
          (a) Set the MDR Level of the neighbor to Backup MDR.
          (b) Set the neighbor's Dependent Selector variable to 1.




Ogier & Spagnolo         Expires August 17, 2008               [Page 33]

Internet-Draft           MANET Extension of OSPF           February 2008


      (3) Else,
          (a) Set the MDR Level of the neighbor to MDR Other.
          (b) Set the neighbor's Dependent Selector variable to 0.

      (4) If the DR or Backup DR field is equal to the router's own
          Router ID, the neighbor's Child variable is set to 1,
          otherwise it is zero.

   o  If the neighbor state is Init, the neighbor event 2-WayReceived is
      executed.

   o  If the MDR Level of the neighbor changed, the neighbor state
      machine is scheduled with the event AdjOK?.

   o  If the neighbor's Child status has changed from 0 to 1, the
      neighbor state machine is scheduled with the event AdjOK?.

   o  If the neighbor's neighbor state changed from less than 2-Way to
      2-Way or greater, the neighbor state machine is scheduled with the
      event AdjOK?.

   In addition, if the router accepts a received DD packet and processes
   its contents, then the following action SHOULD be performed for each
   LSA listed in the DD packet (whether the router is master or slave).
   If the router has an instance of the LSA in the Database summary list
   for the neighbor, which is the same or less recent than the LSA
   listed in the packet, then the LSA is removed from the Database
   summary list.  This avoids including the LSA in a DD packet sent to
   the neighbor, when the neighbor already has an instance of the LSA
   that is the same or more recent.  This optimization reduces overhead
   due to DD packets by approximately 50% in large networks.


8.  Flooding Procedure

   This section specifies the changes to RFC 2328, Section 13 for
   routers that support OSPF-MDR.  The first part of Section 13 (before
   Section 13.1) is the same except for the following three changes.

   o  To exploit the broadcast nature of MANETs, if the Link State
      Update (LSU) packet was received on a MANET interface, then the
      packet is dropped without further processing only if the sending
      neighbor is in a lesser state than 2-Way. Otherwise, the LSU
      packet is processed as described in this section.

   o  If the received LSA is the same instance as the database copy, the
      following actions are performed in addition to step 7.  For each
      MANET interface for which a BackupWait Neighbor Set exists for the



Ogier & Spagnolo         Expires August 17, 2008               [Page 34]

Internet-Draft           MANET Extension of OSPF           February 2008


      LSA (see Section 8.1):

      (a) Remove the sending neighbor from the BackupWait Neighbor list
          if it belongs to the list.
      (b) For each neighbor on the receiving interface that belongs
          to the BNS for the sending neighbor, remove the neighbor
          from the BackupWait Neighbor list if it belongs to the list.

   o  Step 8, which handles the case in which the database copy of the
      LSA is more recent than the received LSA, is modified as follows.
      If the sending neighbor is in a lesser state than Exchange, then
      the router does not send the LSA back to the sending neighbor.

   There are no changes to Sections 13.1, 13.2, or 13.4.  The following
   subsections describe the changes to Sections 13.3 (Next step in the
   flooding procedure), 13.5 (Sending Link State Acknowledgments), 13.6
   (Retransmitting LSAs), and 13.7 (Receiving Link State
   Acknowledgments) of RFC 2328.

8.1.  LSA Forwarding Procedure

   Step 1 of [RFC2328], Section 13.3 should be performed, with the
   following change, so that the new LSA is placed on the Link State
   retransmission list for each appropriate adjacent neighbor.  Step
   1(c) is replaced with the following action, so that the LSA is not
   placed on the retransmission list for a neighbor that has already
   acknowledged the LSA.

   o  If the new LSA was received from this neighbor, or a link state
      acknowledgment (LS Ack) for the new LSA has already been received
      from this neighbor, examine the next neighbor.

   To determine whether an Ack for the new LSA has been received from
   the neighbor, the router maintains an Acked LSA List for each
   adjacent neighbor, as described in Section 8.4.  When a new LSA is
   received, the Acked LSA List for each neighbor, on each MANET
   interface, should be updated by removing any LS Ack that is for an
   older instance of the LSA than the one received.

   The following description will use the notion of a "covered"
   neighbor.  A neighbor k is defined to be covered if the LSA was sent
   as a multicast by a MANET neighbor j, and neighbor k belongs to the
   Bidirectional Neighbor Set (BNS) for neighbor j.  A neighbor k is
   also defined to be covered if the LSA was sent to the multicast
   address AllSPFRouters by a neighbor j on a broadcast interface on
   which both j and k are neighbors.  (Note that j must be the DR or
   Backup DR for the broadcast network, since only these routers may
   send LSAs to AllSPFRouters on a broadcast network.)



Ogier & Spagnolo         Expires August 17, 2008               [Page 35]

Internet-Draft           MANET Extension of OSPF           February 2008


   Steps 2 through 5 of [RFC2328], Section 13.3 are unchanged if the
   outgoing interface (on which the LSA may be forwarded) is not of type
   MANET.  If the outgoing interface is of type MANET, then steps 2
   through 5 are replaced with the following steps, to determine whether
   the LSA should be forwarded on each eligible MANET interface.

   (2) If either of the following two conditions is satisfied for every
       bidirectional neighbor on the interface, examine the next
       interface (the LSA is not flooded out this interface).

       (a) The LSA or an Ack for the LSA has been received from the
           neighbor (over any interface).

       (b) The LSA was received on a MANET or broadcast interface, and
           the neighbor is covered (defined above).

       Note that the above two conditions do not assume the outgoing
       interface is the same as the receiving interface.

   (3) If the LSA was received on this interface, and the router is an
       MDR Other for this interface, examine the next interface (the LSA
       is not flooded out this interface).

   (4) If the LSA was received on this interface, and the router is a
       Backup MDR or a non-flooding MDR for this interface, then the
       router waits BackupWaitInterval before deciding whether to flood
       the LSA.  To accomplish this, the router creates a BackupWait
       Neighbor List for the LSA, which initially includes every
       bidirectional neighbor on this interface that fails to satisfy
       both conditions (a) and (b) in step 2.  A single shot BackupWait
       Timer associated with the LSA is started, which is set to expire
       after BackupWaitInterval seconds plus a small amount of random
       jitter.  (The actions performed when the BackupWait Timer expires
       are described below in Section 8.1.2.)  Examine the next
       interface (the LSA is not immediately flooded out this
       interface).

   (5) If the router is a flooding MDR for this interface, or if the LSA
       was originated by the router itself, then the LSA is flooded out
       the interface (whether or not the LSA was received on this
       interface).  The LSA is included in an LSU packet which is
       multicast out the interface using the destination IP address
       AllSPFRouters.

   (6) If the LSA was received on a MANET or broadcast interface that is
       different from this (outgoing) interface, then the following two
       steps SHOULD be performed to avoid redundant flooding.




Ogier & Spagnolo         Expires August 17, 2008               [Page 36]

Internet-Draft           MANET Extension of OSPF           February 2008


       (a) If the router has a larger value of (RtrPri, MDR Level, RID)
           on the outgoing interface than every covered neighbor
           (defined above) that is a neighbor on BOTH the receiving and
           outgoing interfaces (or if no such neighbor exists), then the
           LSA is flooded out the interface.

       (b) Else, the router waits BackupWaitInterval before deciding
           whether to flood the LSA on the interface, by performing the
           actions in step 4 for a Backup MDR (whether or not the router
           is a Backup MDR on this interface).  A separate BackupWait
           Neighbor List is created for each interface, but only one
           BackupWait Timer is associated with the LSA.  Examine the
           next interface (the LSA is not immediately flooded out this
           interface).

   (7) If the optional step 6 is not performed, then the LSA is flooded
       out the interface.  The LSA is included in an LSU packet which is
       multicast out the interface using the destination IP address
       AllSPFRouters.

8.1.1. Note on Step 6 of LSA Forwarding Procedure

   Performing the optional Step 6 can greatly reduce flooding overhead
   if the LSA was received on a MANET or broadcast interface.  For
   example, assume the LSA was received from the DR of a broadcast
   network that includes 100 routers, and 50 of the routers (not
   including the DR) are also attached to a MANET.  Assume that these 50
   routers are neighbors of each other in the MANET, and that each has a
   neighbor in the MANET that is not attached to the broadcast network
   (and is therefore not covered).  Then by performing Step 6 of the LSA
   forwarding procedure, the number of routers that forward the LSA from
   the broadcast network to the MANET is reduced from 50 to just 1
   (assuming that at most one of the 50 routers is an MDR).

8.1.2. BackupWait Timer Expiration

   If the BackupWait Timer for an LSA expires, then the following steps
   are performed for each (MANET) interface for which a BackupWait
   Neighbor List exists for the LSA.

   (1) If the BackupWait Neighbor List for the interface contains at
       least one router that is currently a bidirectional neighbor, the
       following actions are performed.

       (a) The LSA is flooded out the interface.

       (b) If the LSA is on the Ack List for the interface (i.e., is
           scheduled to be included in a delayed Link State



Ogier & Spagnolo         Expires August 17, 2008               [Page 37]

Internet-Draft           MANET Extension of OSPF           February 2008


           Acknowledgment packet), then the router SHOULD remove the LSA
           from the Ack List, since the flooded LSA will be treated as
           an implicit Ack.

       (c) If the LSA is on the Link State retransmission list for any
           neighbor, the retransmission SHOULD be rescheduled (if
           necessary) so that it does not occur within AckInterval plus
           propagation delays.

   (2) The BackupWait Neighbor list is then deleted (whether or not the
       LSA is flooded).

8.2.  Sending Link State Acknowledgments

   This section describes the procedure for sending Link State
   Acknowledgments (LS Acks) on MANET interfaces. Section 13.5 of RFC
   2328 remains unchanged for non-MANET interfaces, but does not apply
   to MANET interfaces.  To minimize overhead due to LS Acks, and to
   take advantage of the broadcast nature of MANETs, all LS Ack packets
   sent on a MANET interface are multicast using the IP address
   AllSPFRouters.  In addition, duplicate LSAs received as a multicast
   are not acknowledged.

   When a router receives an LSA, it must decide whether to send a
   delayed Ack, an immediate Ack, or no Ack.  (However, a non-ackable
   LSA is never acknowledged, as described in Appendix D.)  A delayed
   Ack may be delayed for up to AckInterval seconds, and allows several
   LS Acks to be grouped into a single multicast LS Ack packet.  An
   immediate Ack is also sent in a multicast LS Ack packet, and may
   include other LS Acks that were scheduled to be sent as delayed Acks.
   The decision depends on whether the received LSA is new (i.e., is
   more recent than the database copy) or a duplicate (the same instance
   as the database copy), and on whether the LSA was received as a
   multicast or a unicast (which indicates a retransmitted LSA).  The
   following rules are used to make this decision.

   (1) If the received LSA is new, a delayed Ack is sent on each
       MANET interface associated with the area, unless the LSA is
       flooded out the interface.

   (2) If the LSA is a duplicate and was received as a multicast,
       the LSA is not acknowledged.

   (3) If the LSA is a duplicate and was received as a unicast:

       (a) If the router is an MDR, or AdjConnectivity = 2 and the
           router is a Backup MDR, or AdjConnectivity = 0, then an
           immediate Ack is sent out the receiving interface.



Ogier & Spagnolo         Expires August 17, 2008               [Page 38]

Internet-Draft           MANET Extension of OSPF           February 2008


       (b) Otherwise, a delayed Ack is sent out the receiving
           interface.

   The reason that (Backup) MDRs send an immediate Ack when a
   retransmitted LSA is received, is to try to prevent other adjacent
   neighbors from retransmitting the LSA, since (Backup) MDRs usually
   have a large number of adjacent neighbors.  MDR Other routers do not
   send an immediate Ack (unless AdjConnectivity = 0) because they have
   fewer adjacent neighbors, and so the potential benefit does not
   justify the additional overhead resulting from sending immediate
   Acks.

8.3.  Retransmitting LSAs

   LSAs are retransmitted according to Section 13.6 of RFC 2328.  Thus,
   LSAs are retransmitted only to adjacent routers.  Therefore, since
   OSPF-MDR does not allow an adjacency to be formed between two MDR
   Other routers, an MDR Other never retransmits an LSA to another MDR
   Other, only to its parents, which are (Backup) MDRs.

   Retransmitted LSAs are included in LSU packets that are sent directly
   to an adjacent neighbor that did not acknowledge the LSA (explicitly
   or implicitly). The length of time between retransmissions is given
   by the configurable interface parameter RxmtInterval, whose default
   is 7 seconds for a MANET interface.  To reduce overhead, several
   retransmitted LSAs should be included in a single LSU packet whenever
   possible.

8.4.  Receiving Link State Acknowledgments

   A Link State Acknowledgment (LS Ack) packet that is received from an
   adjacent neighbor (in state Exchange or greater) is processed as
   described in Section 13.7 of RFC 2328, with the additional steps
   described in this section. An LS Ack packet that is received from a
   neighbor in a lesser state than Exchange is discarded.

   Each router maintains an Acked LSA List for each adjacent neighbor,
   to keep track of any LSA instances the neighbor has acknowledged, but
   which the router itself has NOT yet received.  This is necessary
   because (unlike RFC 2328) each router acknowledges an LSA only the
   first time it is received as a multicast.

   If the neighbor from which the LS Ack packet was received is in state
   Exchange or greater, then the following steps are performed for each
   LS Ack in the received LS Ack packet:

   (1) If the router does not have a database copy of the LSA being
       acknowledged, or has a database copy which is less recent than



Ogier & Spagnolo         Expires August 17, 2008               [Page 39]

Internet-Draft           MANET Extension of OSPF           February 2008


       the one being acknowledged, the LS Ack is added to the Acked LSA
       List for the sending neighbor.

   (2) If the router has a database copy of the LSA being acknowledged,
       which is the same as the instance being acknowledged, then the
       following action is performed. For each MANET interface for which
       a BackupWait Neighbor List exists for the LSA (see Section 8.1),
       remove the sending neighbor from the BackupWait Neighbor list if
       it belongs to the list.


9.  Originating LSAs

   Unlike the DR of an OSPF broadcast network, an MDR does not originate
   a network-LSA, since a network-LSA cannot be used to describe the
   general topology of a MANET.  Instead, each 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, and is
   determined by the configurable parameter LSAFullness.

   If adjacency reduction is used (AdjConnectivity is 1 or 2), then as a
   minimum requirement each router must advertise a minimum set of
   "backbone" neighbors in its router-LSA.  This minimum choice
   corresponds to LSAFullness = 0, and results in the minimum amount of
   LSA flooding overhead, but does not provide routing along shortest
   paths.

   Therefore, to allow routers to calculate shortest paths, without
   requiring every pair of neighboring routers along the shortest paths
   to be adjacent (which would be inefficient due to requiring a large
   number of adjacencies), a router-LSA may also advertise non-adjacent
   neighbors that satisfy a synchronization condition described below.

   To motivate this, we note that OSPF already allows a non-adjacent
   neighbor to be a next hop, if both the router and the neighbor belong
   to the same broadcast network (and are both adjacent to the DR).  A
   network-LSA for a broadcast network (which includes all routers
   attached to the network) implies that any router attached to the
   network can forward packets directly to any other router attached to
   the network (which is why the distance from the network to all
   attached routers is zero in the graph representing the link-state
   database).

   Since a network-LSA cannot be used to describe the general topology
   of a MANET, the only way to advertise non-adjacent neighbors that can
   be used as next hops, is to include them in the router-LSA.  However,
   to ensure that such neighbors are sufficiently synchronized, only
   "routable" neighbors are allowed to be included in LSAs, and to be



Ogier & Spagnolo         Expires August 17, 2008               [Page 40]

Internet-Draft           MANET Extension of OSPF           February 2008


   used as next hops in the SPF calculation.

9.1.  Routable Neighbors

   A bidirectional MANET neighbor becomes routable if its state is Full,
   or if the SPF calculation has produced a route to the neighbor and
   the neighbor satisfies the routable neighbor quality condition
   (defined below).  Since only routable neighbors are advertised in
   router-LSAs, and since adjacencies are selected to form a connected
   spanning subgraph, this definition implies that there exists, or
   recently existed, a path of full adjacencies from the router to the
   routable neighbor.  The idea is that, since a routable neighbor can
   be reached through an acceptable path, it makes sense to take a
   "shortcut" and forward packets directly to the routable neighbor.

   This requirement does not guarantee perfect synchronization, but
   simulations have shown that it performs well in mobile networks.
   This requirement avoids, for example, forwarding packets to a new
   neighbor that is poorly synchronized because it was not reachable
   before it became a neighbor.

   To avoid selecting poor quality neighbors as routable neighbors, a
   neighbor that is selected as a routable neighbor must satisfy the
   routable neighbor quality condition.  By default, this condition is
   that the neighbor's BNS must include the router itself (indicating
   that the neighbor agrees the connection is bidirectional).
   Optionally, a router may impose a stricter condition.  For example, a
   router may require that two Hellos have been received from the
   neighbor that (explicitly or implicitly) indicate that the neighbor's
   BNS includes the router itself.

   The single-bit neighbor variable Routable indicates whether the
   neighbor is routable, and is initially set to 0.  If adjacency
   reduction is used, Routable is updated as follows when the state of
   the neighbor changes, or the SPF calculation finds a route to the
   neighbor, or a Hello is received that affects the routable neighbor
   quality condition.

   (1) If Routable is 0 for the neighbor and the state of the neighbor
       changes to Full, Routable is set to 1 for the neighbor.

   (2) If Routable is 0 for the neighbor, the state of the neighbor is
       2-Way or greater, there exists a route to the neighbor, and the
       routable neighbor quality condition (defined above) is satisfied,
       then Routable is set to 1 for the neighbor.

   (3) If Routable is 1 for the neighbor and the state of the neighbor
       is less than 2-Way, Routable is set to 0 for the neighbor.



Ogier & Spagnolo         Expires August 17, 2008               [Page 41]

Internet-Draft           MANET Extension of OSPF           February 2008


       If adjacency reduction is not used (AdjConnectivity = 0), then a
       neighbor is defined to be routable if and only if its state is
       Full.

9.2. Partial and Full-Topology LSAs

   The choice of which MANET neighbors to include in the router-LSA is
   flexible.  Whether or not adjacency reduction is used, the router can
   originate either partial-topology or full-topology LSAs.  This
   flexibility is made possible by defining two types of neighbors that
   are included in the router-LSA: backbone neighbors and selected
   advertised neighbors.

9.2.1. Backbone Neighbors and Selected Advertised Neighbors

   A backbone neighbor is defined to be a bidirectional neighbor that is
   a Dependent Neighbor, Dependent Selector, (Backup) Parent, or child.
   If adjacency reduction is not used (AdjConnectivity = 0), then the
   set of backbone neighbors is empty (since there are no dependent
   neighbors or parents).

   If adjacency reduction is used, then a router MUST include in its
   router-LSA all backbone neighbors that are routable.  A minimum LSA,
   corresponding to LSAFullness = 0, includes only these neighbors.
   This choice guarantees connectivity, but does not provide shortest
   paths.  However, it may be useful in large networks to achieve
   maximum scalability.  If adjacency reduction is not used, then
   LSAFullness MUST NOT be 0, since in this case the set of backbone
   neighbors is empty.

   To allow flexibility while ensuring that LSAs are symmetric (i.e.,
   router i advertises a link to router j if and only if router j
   advertises a link to router i), each router maintains a selected
   advertised neighbor list (SANS), which consists of MANET neighbors
   that the router has selected to advertise in its router-LSA, not
   including backbone neighbors.  Since the SANS does not include
   Dependent Neighbors, the lists SANS and DNS are disjoint.  (Note that
   both lists are advertised in Hellos.)

   If LSAFullness = 0, then the SANS is empty, since only backbone
   neighbors are included in the router-LSA.  At the other extreme, a
   full-topology LSA, corresponding to LSAFullness = 4, includes all
   routable neighbors.  In this case, the SANS includes all
   bidirectional MANET neighbors except backbone neighbors.  Note that
   backbone neighbors and neighbors in the SANS need not be routable,
   but only routable neighbors may be included in the router-LSA.  (This
   is done so that the SANS, which is advertised in Hellos, does not
   depend on routability.)



Ogier & Spagnolo         Expires August 17, 2008               [Page 42]

Internet-Draft           MANET Extension of OSPF           February 2008


9.2.2. Choice of LSAFullness

   LSAFullness affects the contents of the router-LSA by determining the
   neighbors to include in the SANS.  The choices of SANS corresponding
   to the extreme cases of LSAFullness equal to 0 and 4 were described
   above.

   If LSAFullness is 1 or 2, the router originates min-cost LSAs, which
   are partial-topology LSAs that (when flooded) provide each router
   with sufficient information to calculate at least one shortest
   (minimum-cost) path to each destination.  If LSAFullness is 2, then
   additional MANET neighbors are also included in the router-LSA to
   provide redundant routes.

   Appendix C describes the algorithm for selecting the neighbors to
   include in the SANS that results in min-cost LSAs.  The input to this
   algorithm includes information obtained from Hellos received from
   each MANET neighbor, including the Bidirectional Neighbor List (BNS),
   Dependent Neighbor Set (DNS), Selected Advertised Neighbor List
   (SANS), and the Metric TLV.  The Metric TLV, specified in Section
   A.2.2.8, is included in each Hello and advertises the link cost to
   each bidirectional neighbor.  To minimize overhead, it allows the
   option of advertising only a single metric for the interface (equal
   to the link cost to each neighbor).

   If LSAFullness is 3, each (Backup) MDR originates a full LSA (which
   includes all routable neighbors), while each MDR Other originates a
   minimum LSA (which includes only routable backbone neighbors).  If a
   router has multiple MANET interfaces, its LSA includes all routable
   neighbors on the interfaces for which it is a (Backup) MDR, and
   includes only routable backbone neighbors on its other interfaces.
   When a router changes its MDR Level from MDR Other to (Backup) MDR on
   a given interface, it must originate a new LSA.  This choice provides
   routing along nearly shortest paths with relatively low overhead.

   It is not necessary for different routers to choose the same value of
   LSAFullness; the different choices are interoperable because they all
   require the router-LSA to include a minimum set of neighbors, and
   because the construction of the router-LSA (described below) ensures
   that the router-LSAs originated by different routers are consistent.

9.2.3. Construction of the Router-LSA

   When a new router-LSA is originated, it includes a point-to-point
   (type 1) link for each MANET neighbor j that is routable and
   satisfies at least one of the following three conditions:

   (1) The router's SANS (for any interface) includes j.



Ogier & Spagnolo         Expires August 17, 2008               [Page 43]

Internet-Draft           MANET Extension of OSPF           February 2008


   (2) Neighbor j's SANS includes the router (to ensure symmetry).

   (3) Neighbor j is a backbone neighbor.

   Note that if adjacency reduction is not used (AdjConnectivity = 0),
   then the set of backbone neighbors is empty, and a MANET neighbor is
   routable if and only if it is in the Full state.  Also note that
   neighbors in the SANS need not be routable, but only routable
   neighbors are included in the router-LSA.

   A new router-LSA is originated if any of the events specified in
   Section 12.4 of [RFC2328] occurs, except that event (4), i.e., one of
   the neighboring routers changes to/from the FULL state, does not
   apply to MANET neighbors.  For MANET neighbors, event (4) is replaced
   with the following two events:

   o  There exists a routable MANET neighbor j that satisfies one of the
      above three conditions, but is not included in the current router-
      LSA.

   o  The current router-LSA includes a MANET neighbor that is no longer
      routable.

   If AdjConnectivity = 0 and LSAFullness = 4 (full LSAs), then since
   only Full neighbors are routable and the SANS includes all
   bidirectional neighbors in this case, the above two events are
   equivalent to one of the neighboring routers changing to/from the
   Full state.


10.  Calculating the Routing Table

   The routing table calculation is the same as specified in RFC 2328,
   except for the following change to Section 16.1 (Calculating the
   shortest-path tree for an area).

   Recall from Section 9 that a router can use any routable neighbor as
   a next hop to a destination.  However, unless LSAFullness = 4 (full-
   topology LSAs), the router-LSA originated by the router usually does
   not include all routable neighbors.  Therefore, the shortest-path
   tree calculation described in Section 16.1 of RFC 2328 must be
   modified to allow any routable neighbor on a MANET interface to be
   used as a next hop.  This is accomplished by modifying step 2 so that
   the router-LSA associated with the root vertex (i.e., the router
   doing the calculation) is augmented to include all routable neighbors
   on each MANET interface. In addition, step 2b (checking for a link
   from W back to V) must be skipped when V is the root vertex and W is
   a routable MANET neighbor whose state is less than Full.  However,



Ogier & Spagnolo         Expires August 17, 2008               [Page 44]

Internet-Draft           MANET Extension of OSPF           February 2008


   step 2b MUST be executed when W is in state Full and when V is not
   the root vertex, to ensure that Full neighbors are synchronized in
   both directions, and to ensure compatibility with OSPFv3.

   Note that, if LSAFullness is less than 4, then the set of routable
   neighbors can change without causing the contents of the router-LSA
   to change.  This could happen, for example, if a routable neighbor
   that was not included in the router-LSA transitions to the Down or
   Init state.  Therefore, if the set of routable neighbors changes, the
   shortest-path tree must be recalculated even if the router-LSA does
   not change.

   After the shortest-path tree and routable table are calculated, the
   set of routable neighbors must be updated, since a route to a non-
   routable neighbor may have been discovered.  If the set of routable
   neighbors changes, then the shortest-path tree and routing table must
   be calculated a second time.  The second calculation will not change
   the set of routable neighbors again, so two calculations are
   sufficient.


11. Security Considerations

   This document proposes an extension of OSPFv3 and can use the same
   IPv6 security mechanisms as OSPFv3.  Hence, this document does not
   raise any new security concerns.

12. IANA Considerations

   This document defines three new LLS TLV types (see Section A.2) to be
   allocated by IANA.

13. Acknowledgments

   Thanks to Aniket Desai for helpful discussions and comments,
   including the suggestion that Router Priority should come before MDR
   Level in the lexicographical comparison of (RtrPri, MDR Level, RID)
   when selecting MDRs and BMDRs, and that the MDR calculation should be
   repeated if it causes the MDR Level to change.  Thanks also to Tom
   Henderson for helpful discussions and comments.


14.  Normative References

   [RFC2328] J. Moy. "OSPF Version 2", RFC 2328, April 1998.

   [RFC2740] R. Coltun, D. Ferguson, and J. Moy. "OSPF for IPv6", RFC
        2740, December 1999.



Ogier & Spagnolo         Expires August 17, 2008               [Page 45]

Internet-Draft           MANET Extension of OSPF           February 2008


   [LLS] A. Zinin, A. Roy, L. Nguyen, B. Friedman, and D. Young, "OSPF
        Link-local Signaling", draft-ietf-ospf-lls-03.txt (work in
        progress), August 2007.

   [RFC2119]  Bradner, S., "Key words for use in RFC's to Indicate
        Requirement Levels", RFC 2119, March 1997.

15.  Informative References

   [Lawler] E. Lawler. "Combinatorial Optimization: Networks and
        Matroids", Holt, Rinehart, and Winston, New York, 1976.

   [Suurballe] J.W. Suurballe and R.E. Tarjan. "A Quick Method for
        Finding Shortest Pairs of Disjoint Paths", Networks, Vol. 14,
        pp. 325-336, 1984.


A.  Packet Formats

A.1.  Options Field

   A new bit, called L (for LLS) is introduced to OSPFv3 Options field
   (see Figure A.1). The mask for the bit is 0x200.  Routers set the L
   bit in Hello and DD packets to indicate that the packet contains LLS
   data block.  Routers set the L bit in a self-originated router-LSA to
   indicate that the LSA is non-ackable.

        0                   1                   2
        0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5  6 7 8  9  0  1  2  3
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+-+-+--+--+--+--+--+--+
       | | | | | | | | | | | | | | |L|AF|*|*|DC| R| N|MC| E|V6|
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+-+-+--+--+--+--+--+--+

                    Figure A.1: The Options field


A.2.  Link-Local Signaling

   Link-local signaling (LLS) [LLS] describes an extension to OSPFv2 and
   OSPFv3 which allows the exchange of arbitrary data using existing,
   standard OSPF packet types.  Here we use LLS for OSPFv3, which is
   accomplished by adding an LLS data block at the end of the OSPFv3
   packet.

   The IPv6 header length includes the total length of the OSPFv3
   header, OSPFv3 data, and LLS data, but the OSPFv3 header does not
   contain the LLS data length in its length field.  The IPv6 packet
   format is depicted in Figure A.2 below.



Ogier & Spagnolo         Expires August 17, 2008               [Page 46]

Internet-Draft           MANET Extension of OSPF           February 2008


                   +---------------------+ --
                   | IPv6 Header         | ^
                   | Length = HL+X+Y     | | Header Length = HL
                   |                     | v
                   +---------------------+ --
                   | OSPFv3 Header       | ^
                   | Length = X          | |
                   |.....................| | X
                   |                     | |
                   | OSPFv3 Data         | |
                   |                     | v
                   +---------------------+ --
                   |                     | ^
                   |  LLS Data           | | Y
                   |                     | v
                   +---------------------+ --

               Figure A.2: Attaching LLS Data Block

   The LLS data block may be attached to OSPFv3 Hello and Database
   Description (DD) packets.  The data included in the LLS block
   attached to a Hello packet may be used for dynamic signaling, since
   Hello packets may be sent at any moment in time. However, delivery of
   LLS data in Hello packets is not guaranteed. The data sent with DD
   packets is guaranteed to be delivered as part of the adjacency
   forming process.

A.2.1 LLS Data Block

   The data block used for link-local signaling is formatted as
   described below (see Figure A.3).

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |            Checksum           |       LLS Data Length         |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    |                           LLS TLVs                            |
    .                                                               .
    .                                                               .
    .                                                               .
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                  Figure A.3: Format of LLS Data Block

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




Ogier & Spagnolo         Expires August 17, 2008               [Page 47]

Internet-Draft           MANET Extension of OSPF           February 2008


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

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

A.2.2 LLS TLV Format

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

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

     0                   1                   2                   3
     0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |            Type               |           Length              |
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
    |                                                               |
    .                                                               .
    .                             Value                             .
    .                                                               .
    +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
                          Figure A.4: Format of LLS TLVs

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

A.2.3 Hello TLV

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








Ogier & Spagnolo         Expires August 17, 2008               [Page 48]

Internet-Draft           MANET Extension of OSPF           February 2008


    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+
   |            Type               |           Length              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |    Hello Sequence Number      |          Reserved         |A|D|
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      N1       |      N2       |      N3       |      N4       |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   o  Type: Set to 14.
   o  Length: Set to 8.
   o  Hello Sequence Number: A circular two octet unsigned integer
      indicating the current HSN for the transmitting interface.  The
      HSN for the interface MUST be incremented by 1 every time a
      (differential or full) Hello is sent on the interface.
   o  Reserved: Set to 0.  Reserved for future use.
   o  A (1 bit): Set to 1 if AdjConnectivity is 0, otherwise set to 0.
   o  D (1 bit): Set to 1 for a differential Hello and 0 for a full
      Hello.
   o  N1 (8 bits): The number of neighbors listed in the Hello that
      are in state Down.  N1 is zero if the the Hello is not
      differential.
   o  N2 (8 bits): The number of neighbors listed in the Hello that
      are in state Init.
   o  N3 (8 bits): The number of neighbors listed in the Hello that
      are Dependent.
   o  N4 (8 bits): The number of neighbors listed in the Hello that
      are Selected Advertised Neighbors.

A.2.4 MDR TLV

   A new TLV is defined which includes the same two Router IDs that are
   included in the DR and Backup DR fields of a Hello sent by the
   router.  This TLV is used in conjunction with a Database Description
   packet, and is used to indicate the router's MDR Level and selected
   parent(s).

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+
   |            Type               |           Length              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+
   |                               DR                              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+
   |                           Backup DR                           |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+--+--+-+-+-+-+-+-+-+-+-+-+-+-+




Ogier & Spagnolo         Expires August 17, 2008               [Page 49]

Internet-Draft           MANET Extension of OSPF           February 2008


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

A.2.5 Metric TLV

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

    0                   1                   2                   3
    0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |            Type               |           Length              |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |      Default Metric           |        Reserved             |I|
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        Neighbor ID (1)                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                        Neighbor ID (2)                        |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                             ...                               |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |         Metric (1)            |        Metric (2)             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |           ...
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

   o  Type: Set to 16.
   o  Length: Set to 4 + 6*N if the I bit is 1, and to 4 + 2*N if the I
      bit is 0, where N is the number of neighbors included in the TLV.
   o  Default Metric: If the I bit is 1, this is the link metric that
      applies to every bidirectional neighbor listed in the body of
      the Hello whose RID is not listed in the Metric TLV.
   o  Neighbor ID: If the I bit is 1, the RID is listed for each
      bidirectional neighbor (Lists 3 through 5 as defined in
      Section 4.1) in the body of the Hello whose link metric is not



Ogier & Spagnolo         Expires August 17, 2008               [Page 50]

Internet-Draft           MANET Extension of OSPF           February 2008


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

A.3.  Hello Packet DR and Backup DR Fields

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

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

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

A.4.  LSA Formats and Examples

   LSA formats are specified in [RFC2740] Section 3.4.3.  Figure A.5
   below gives an example network map for a MANET in a single area.

   o  Four MANET nodes RT1, RT2, RT3, and RT4 are in area 1.
   o  RT1's MANET interface has links to RT2 and RT3's MANET interfaces.
   o  RT2's MANET interface has links to RT1 and RT3's MANET interfaces.
   o  RT3's MANET interface has links to RT1, RT2, and RT3's MANET
      interfaces.
   o  RT4's MANET interface has a link to RT3's MANET interface.
   o  RT1 and RT2 have stub networks attached on broadcast interfaces.
   o  RT3 has a transit network attached on a broadcast interface.


















Ogier & Spagnolo         Expires August 17, 2008               [Page 51]

Internet-Draft           MANET Extension of OSPF           February 2008


    ..........................................
    .                                  Area 1.
    .     +                                  .
    .     |                                  .
    .     | 2+---+1                       1+---+
    .  N1 |--|RT1|-----+               +---|RT4|----
    .     |  +---+     |             /    +---+
    .     |            |            /       .
    .     +            |     N3    /        .
    .                  |          /         .
    .     +            |         /          .
    .     |            |        /           .
    .     | 2+---+1    |       /            .
    .  N2 |--|RT2|-----+-------+             .
    .     |  +---+             |1            .
    .     |                  +---+           .
    .     |                  |RT3|----------------
    .     +                  +---+           .
    .                          |2            .
    .                   +------------+       .
    .                      |1   N4           .
    .                    +---+               .
    .                    |RT5|               .
    .                    +---+               .
    ..........................................

   Figure A.5: Area 1 with IP addresses shown


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

   Table 1: IPv6 link prefixes for sample network















Ogier & Spagnolo         Expires August 17, 2008               [Page 52]

Internet-Draft           MANET Extension of OSPF           February 2008


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

          Table 2: IPv6 link prefixes for sample network

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

    Table 3: OSPF Interface IDs and link-local addresses

A.4.1 Router-LSAs

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












Ogier & Spagnolo         Expires August 17, 2008               [Page 53]

Internet-Draft           MANET Extension of OSPF           February 2008


   RT3's router-LSA

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

A.4.2 Link-LSAs

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

   RT3's Link-LSA for its MANET interface

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






Ogier & Spagnolo         Expires August 17, 2008               [Page 54]

Internet-Draft           MANET Extension of OSPF           February 2008


A.4.3 Intra-Area-Prefix-LSAs

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

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

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


B.  Detailed Algorithms for MDR/BMDR Selection

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

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

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

   The following algorithm performs Step 2.4 of the MDR selection
   algorithm, and assumes that Phase 1 and Steps 2.1 through 2.3 have
   been performed, so that the neighbor connectivity matrix NCM has been
   computed, and Rmax is the bi-neighbor with the (lexicographically)
   largest value of (RtrPri, MDR Level, RID).  The BFS algorithm uses a
   FIFO queue so that all nodes 1 hop from node Rmax are processed



Ogier & Spagnolo         Expires August 17, 2008               [Page 55]

Internet-Draft           MANET Extension of OSPF           February 2008


   first, then 2 hops, etc.  When the BFS algorithm terminates, hops(u),
   for each bi-neighbor node u of node i, will be equal to the minimum
   number of hops from node Rmax to node u, using only intermediate
   nodes that are bi-neighbors of node i and that have a larger value of
   (RtrPri, MDR Level, RID) than node i.  The algorithm also computes,
   for each node u, the tree parent p(u) and the second node r(u) on the
   tree path from Rmax to u, which will be used in Step 3.2

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

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

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

B.2.  Detailed Algorithm for Step 3.2 (BMDR Selection)

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

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

   The algorithm described below uses the following output of Phase 2:



Ogier & Spagnolo         Expires August 17, 2008               [Page 56]

Internet-Draft           MANET Extension of OSPF           February 2008


   the tree parent p(u) of each node (which defines the BFS tree
   computed in Phase 2), and the second node r(u) on the tree path from
   Rmax to u.

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

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

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

   The algorithm consists of the following two steps.

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

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

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




Ogier & Spagnolo         Expires August 17, 2008               [Page 57]

Internet-Draft           MANET Extension of OSPF           February 2008


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

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

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


C.  Min-Cost LSA Algorithm

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

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

   The output of the algorithm is the router's SANS for each MANET
   interface.  The SANS is used to determine the contents of the router-
   LSA as described in Section 9.2.3.  The min-cost LSA algorithm must
   be run to update the SANS (and possibly originate a new router-LSA)
   whenever any of the following events occurs:

   o  The state or routability of a neighbor changes.
   o  A Hello received from a neighbor indicates a change in its
      MDR Level, Router Priority, FullHelloRcvd, BNS, DNS, SANS,
      MDR Parent(s), or link metrics.
   o  An LSA originated by a non-MANET neighbor is received.



Ogier & Spagnolo         Expires August 17, 2008               [Page 58]

Internet-Draft           MANET Extension of OSPF           February 2008


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

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

   (1) Create the neighbor connectivity matrix (NCM) for each MANET
       interface, as described in Section 5.1.  Create the multiple-
       interface neighbor connectivity matrix MNCM as follows.  For each
       bi-neighbor j, set MNCM(i,j) = MNCM(j,i) = 1.  For each pair j, k
       of MANET bi-neighbors, set MNCM(j,k) = 1 if NCM(j,k) equals 1 for
       any MANET interface.  For each pair j, k of non-MANET bi-
       neighbors, set MNCM(j,k) = 1 if the link-state database indicates
       that a direct link exists between j and k.  Otherwise, set
       MNCM(j,k) = 0.  (Note that a given router can be a neighbor on
       both a MANET interface and a non-MANET interface.)

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

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

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

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

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

       For each pair j, k of MANET bi-neighbors, BNM(j,k) is set to 1 if
       j and k are backbone neighbors of each other on a candidate MANET
       interface.  That is, BNM(j,k) is set to 1 if, for any candidate



Ogier & Spagnolo         Expires August 17, 2008               [Page 59]

Internet-Draft           MANET Extension of OSPF           February 2008


       MANET interface, NCM(j,k) = 1 and either of the following
       conditions is satisfied:

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

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

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

   (4) Create the selected advertised neighbor matrix (SANM) as follows.
       For each pair j, k of routers such that each of j and k is a bi-
       neighbor or router i itself, SANM(j,k) is set to 1 if, for any
       candidate MANET interface, NCM(j,k) = 1 and k is included in j's
       SANS.  Otherwise, SANM(j,k) is set to 0.  Note that SANM(i,k) is
       set to 1 if k is currently a selected advertised neighbor.

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

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

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

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

       (d) This step is optional, but SHOULD be performed in order to
           remove redundant advertised neighbors.  If SANM(i,j) = 0,
           i.e., j is not currently a selected advertised neighbor, then
           proceed to step (e).

           Otherwise, for each bi-neighbor k (on any interface) such



Ogier & Spagnolo         Expires August 17, 2008               [Page 60]

Internet-Draft           MANET Extension of OSPF           February 2008


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

           o  BNM(u,j) = 1,
           o  SANM(j,u) > SANM(j,i), or
           o  SANM(j,u) = SANM(j,i), SANM(u,j) = 1, and
              (RtrPri(u), MDR_Level(u), RID(u)) is lexicographically
              less than (RtrPri(i), MDR_Level(i), RID(i)).

           If for each such bi-neighbor k, there exists such a bi-
           neighbor u, then do not select j, skip step (e), and continue
           to the next neighbor j.

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

           o  BNM(u,j) = 1, or
           o  (SANM(j,u), SANM(u,j), RtrPri(u), MDR_Level(u), RID(u))
              is lexicographically greater than
              (SANM(j,i), SANM(i,j), RtrPri(i), MDR_Level(i), RID(i)).

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

   (6) For each MANET interface I, update the SANS to equal the set of
       all bi-neighbors j such that new_sel_adv(j) = 1 and I is the
       preferred interface for j.  If LSAFullness = 2, the SANS SHOULD
       also include other bidirectional neighbors to provide redundant
       routes.

   (7)  With the SANS updated, a new router-LSA may need to be
       originated as described in Section 9.2.3.

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

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




Ogier & Spagnolo         Expires August 17, 2008               [Page 61]

Internet-Draft           MANET Extension of OSPF           February 2008


D.  Non-Ackable LSAs for Periodic Flooding

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

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


Authors' Addresses

   Richard G. Ogier
   SRI International
   Email: rich.ogier@earthlink.net, richard.ogier@sri.com

   Phil Spagnolo
   Boeing Phantom Works
   Email: phillip.a.spagnolo@boeing.com










Ogier & Spagnolo         Expires August 17, 2008               [Page 62]

Internet-Draft           MANET Extension of OSPF           February 2008


Intellectual Property Statement

   The IETF takes no position regarding the validity or scope of any
   Intellectual Property Rights or other rights that might be claimed to
   pertain to the implementation or use of the technology described in
   this document or the extent to which any license under such rights
   might or might not be available; nor does it represent that it has
   made any independent effort to identify any such rights.  Information
   on the procedures with respect to rights in RFC documents can be
   found in BCP 78 and BCP 79.

   Copies of IPR disclosures made to the IETF Secretariat and any
   assurances of licenses to be made available, or the result of an
   attempt made to obtain a general license or permission for the use of
   such proprietary rights by implementers or users of this
   specification can be obtained from the IETF on-line IPR repository at
   http://www.ietf.org/ipr.

   The IETF invites any interested party to bring to its attention any
   copyrights, patents or patent applications, or other proprietary
   rights that may cover technology that may be required to implement
   this standard.  Please address the information to the IETF at ietf-
   ipr@ietf.org.

Disclaimer of Validity

   This document and the information contained herein are provided on an
   "AS IS" basis and THE CONTRIBUTOR, THE ORGANIZATION HE/SHE REPRESENTS
   OR IS SPONSORED BY (IF ANY), THE INTERNET SOCIETY, THE IETF TRUST AND
   THE INTERNET ENGINEERING TASK FORCE DISCLAIM ALL WARRANTIES, EXPRESS
   OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF
   THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED
   WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

Copyright Statement

   Copyright (C) The IETF Trust (2008). This document is subject to the
   rights, licenses and restrictions contained in BCP 78, and except as
   set forth therein, the authors retain all their rights.

Acknowledgment

   Funding for the RFC Editor function is currently provided by the
   Internet Society.







Ogier & Spagnolo         Expires August 17, 2008               [Page 63]


Html markup produced by rfcmarkup 1.109, available from https://tools.ietf.org/tools/rfcmarkup/