Subject: [Ospf-wireless-design] Update to draft-ogier-manet-ospf-extension

From: Richard Ogier <[email-masked]>
Date: Thu, 03 Feb 2005 11:25:34 -0800

All,

An update to my draft is attached. The main changes are
summarized below. I will submit the final version before
the meeting deadline (February 21). Comments are welcome.

Richard

   Changes from version 02 to version 03:

   - A flexible Hello protocol is presented that allows routers to
     send either full or differential Hellos, in which either full or
     partial 2-hop neighbor information is advertised periodically.
     Partial information consists of (Backup) Dependent Neighbors.

   - The ANP CDS algorithm has been modified to allow the possibility
     that a router can be a DR of one neighbor and a Backup DR of
     another neighbor. To allow this, the algorithm now distinguishes
     between Dependent Neighbors and Backup Dependent Neighbors.

   - The flooding procedure (Section 6) has also been modified to
     distinguish between Dependent and Backup Dependent Neighbors.

   - The ANP CDS algorithm has been modified to allow a (Backup) DR
     to declare all of its neighbors to be (Backup) Dependent,
     thus making all neighbors adjacent (which is always the case
     in the other CDS algorithms).

   - The rule for forming adjacencies has been modified so that an
     adjacency is formed between two routers if and only if one of
     the routers is a (Backup) Dependent Neighbor of the other one.
     Since Hellos advertise (Backup) Dependent Neighbors, each router
     knows which neighbors it should become adjacent with.

Mobile Ad Hoc and OSPF Working Groups                         R. Ogier
Internet-Draft                                        February 3, 2005

               MANET Extension of OSPF using CDS Flooding
                draft-ogier-manet-ospf-extension-03pre.txt

Status of this Memo

   This document is an Internet-Draft and is subject to all provisions
   of section 3 of RFC 3667.  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 become aware will be disclosed, in accordance with
   RFC 3668.

   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/ietf/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 3, 2005.

   Copyright (C) The Internet Society (2005).

Abstract

   This document describes and evaluates a family of interoperable
   flooding methods for mobile ad-hoc networks, which use a distributed
   algorithm for computing a connected dominating set (CDS) based on
   2-hop neighbor information. The different methods are interoperable
   because the CDS computed by each method contains a "minimal" CDS,
   which is computed by the most efficient of the described methods.
   Simulations are presented to compare the different methods with
   respect to CDS size and average stretch factor.  This document also
   describes how the proposed CDS algorithms can be used to achieve
   reliable flooding of LSAs in OSPF. In this context, the CDS nodes
   generalize the concept of a Designated Router to a multi-hop network.

Ogier                    Expires August 3, 2005                 [Page 1]

Internet-Draft           MANET Extension of OSPF           February 2005

1. Introduction

   Flooding is useful in mobile ad-hoc networks for the dissemination of
   topology information (in link-state routing protocols) and other
   information, and for route discovery (in reactive routing protocols).
   Because mobile networks typically have less bandwidth than wired
   networks, an efficient flooding mechanism is needed, in which only a
   relatively small subset of nodes forward a given flooded packet. Once
   choice for such a subset of nodes is a connected dominating set
   (CDS).

   This document presents distributed CDS algorithms in which each node
   decides whether it is in the CDS based on 2-hop neighbor information.
   This allows fast reaction to topology changes, since the decision to
   be in the CDS does not depend on information that must be propagated
   across the network.

   We present a family of distributed CDS algorithms, which are related
   and interoperable since the CDS computed by each algorithm contains a
   minimal CDS, called the Essential CDS, which is computed by the most
   efficient of the distributed algorithms. Thus, a CDS will be obtained
   as long as each node runs any algorithm in the family.  More
   generally, any CDS algorithm can be used as long as it results in the
   node selecting itself whenever it belongs to the Essential CDS.

   The two performance measures that we consider are CDS size and
   stretch factor, defined as the average length of a min-hop path
   between a source and a destination using only CDS nodes as
   intermediate nodes, divided by the average min-hop path length using
   any nodes. As we show using simulations, some of the CDS algorithms
   achieve a smaller stretch factor at the cost of a larger CDS. A small
   stretch factor (close to 1) is desirable because each flooded packet
   travels fewer hops on average.

   In addition, a small stretch factor is beneficial if the CDS is used
   for unicast routing, i.e., if unicast routes are constrained to use
   only CDS nodes as intermediate nodes.  This would be the case if only
   links adjacent to CDS nodes are disseminated in LSAs, as described in
   Section 5. Thus, a small stretch factor allows overhead to be reduced
   dramatically by allowing the dissemination of a relatively small
   portion of the full topology.

   This document also describes how the proposed CDS methods can be used
   to achieve reliable flooding of LSAs in OSPF. In this context, the
   CDS nodes generalize the concept of a Designated Router (DR) to
   MANETs, and the proposed CDS selection algorithms generalize OSPF’s
   algorithm for selecting a DR and Backup DR.  Therefore, we extend the
   term "Designated Router" to refer to a CDS node, and thus a MANET can

Ogier                    Expires August 3, 2005                 [Page 2]

Internet-Draft           MANET Extension of OSPF           February 2005

   have several DRs. Much of the functionality of a DR in legacy OSPF
   [RFC2328, RFC2740] remains the same for a generalized DR. For
   example, adjacencies are formed only between each DR/Backup DR and
   its neighbors, and only DRs (and possibly Backup DRs) forward LSAs in
   the flooding process.

   Each CDS algorithm has a persistent and a non-persistent version.  In
   the persistent versions, each (generalized) DR remains a DR until the
   existence of higher priority neighboring DRs make it redundant, as in
   legacy OSPF.  In the non-persistent versions, DRs are recalculated
   whenever the 2-hop neighborhood changes, regardless of which nodes
   are currently DRs.  The persistent versions have the advantage that
   DRs do not change as often, and are therefore recommended for
   reliable flooding, since an adjacency must be formed (with database
   synchronization) between each new DR and some or all of its
   neighbors.  The non-persistent versions are useful for periodic,
   unreliable flooding, which does not require database synchronization.

   The 2-hop neighbor information required for DR selection is obtained
   from Hello packets. Section 10 describes a differential Hello
   protocol in which either partial or full 2-hop neighbor information
   is advertised in Hellos.  One of the advantages of the proposed
   solution is that only partial 2-hop neighbor information is required,
   thus reducing overhead.

   Section 2 summarizes the features of the solution proposed in this
   document. Section 3 discusses the relative benefits of CDS flooding
   versus MPR flooding. Section 4 describes the proposed family of CDS
   algorithms. Section 5 specifies which neighbors should be adjacent,
   and which should be included in LSAs.  Section 6 describes the
   flooding procedure, and Sections 7 and 8 describe the procedures for
   retransmitting LSAs and sending Link State acknowledgments,
   respectively.  Section 9 proposes three enhancements for reducing
   overhead, including more efficient database exchange, multicasting
   retransmitted LSAs, and non-ackable LSAs.  Section 10 describes the
   differential Hello protocol, and Section 11 presents simulation
   results comparing different algorithms in the proposed family of CDS
   algorithms.

2. Summary of Features of the Proposed Solution

   The following bullets summarize the main features of the solution
   presented in this document:

   - The document presents a family of interoperable CDS algorithms,
     which allow a tradeoff between path optimality and CDS size.
     Simulation results are presented to show this tradeoff.

Ogier                    Expires August 3, 2005                 [Page 3]

Internet-Draft           MANET Extension of OSPF           February 2005

   - The CDS algorithms are based only on 2-hop neighbor information,
     to provide fast convergence following topology changes.

   - The CDS algorithms are interoperable because the CDS computed by
     each algorithm contains a minimal, source-independent CDS called
     the "Essential" CDS. The Essential CDS can be computed in O(d^2)
     time, where d is the number of neighbors.

   - The Essential CDS is very scalable, as shown by the simulation
     results in Section 11. In a 300 node network with average degree
     64 and diameter 5, the Essential CDS consists of only 23 (8%) of
     the nodes on average.

   - The Essential CDS provides a minimal, source-independent set
     of relays for flooding LSAs (or other flooded packets).
     The flooding procedure also allows source-dependent flooding
     (using previous-hop information) as an option, if it is desired
     to flood packets along min-hop paths.

   - For improved CDS stability, each algorithm in the family has a
     "persistent" version, in which a router in the CDS remains in
     the CDS until it becomes redundant.

   - Generalizes the OSPF concept of a Designated Router (DR) and
     Backup DR to MANETs. The set of DRs forms a CDS, and the set of
     DRs and Backup DRs forms a biconnected CDS for robustness.
     When applied to a broadcast network, the persistent version of
     each algorithm computes the same DR and Backup DR as OSPF.

   - Adjacencies are formed only between CDS nodes (DRs and Backup DRs)
     and their neighbors, as in legacy OSPF.

   - Provides a flexible choice of which neighbors to include in LSAs,
     from a minimum set of neighbors adjacent to DRs and Backup DRs,
     to the full network topology.

   - A flexible Hello protocol is presented that allows routers to send
     either full or differential Hellos, in which either full or partial
     2-hop neighbor information is advertised.

3. Comparison of CDS and MPR Flooding

   Two flooding approaches being considered for mobile ad-hoc networks
   are multipoint relays (MPRs) and a connected dominating set (CDS).
   The main difference is that MPRs are directional, so that the set of
   MPRs that forward a given flooded packet depends on the originating
   node, whereas if a CDS is used, then all CDS nodes forward each

Ogier                    Expires August 3, 2005                 [Page 4]

Internet-Draft           MANET Extension of OSPF           February 2005

   flooded packet.  In addition, flooding via MPRs results in each
   packet following a min-hop path, whereas a CDS need not provide min-
   hop paths.

   In the discussion below, for MPR flooding we assume that each node
   selects a subset of its neighbors to be MPRs based on 2-hop neighbor
   information, as in [RFC3626].  Thus CDS nodes are "self selected"
   whereas MPRs are "neighbor selected".  It is also possible for MPRs
   to be self selected, and for CDS nodes to be determined based on
   neighbor-selected MPRs as in [Adjih02].

   In the solution presented in this document, each node that selects
   itself as a CDS node also selects a set of "dependent" neighbors,
   which are analogous to MPR selectors. Thus, we present a flexible
   solution that includes both self-selected (source-independent) CDS
   nodes and self-selected MPRs in a unified manner.

   CDS-based flooding has the following advantages when compared to
   (neighbor-selected) MPR-based flooding:

   - A node need not know the previous hop of a flooded packet in
     deciding whether to forward it.

   - The previous-hop independence also simplifies reliable flooding,
     since a CDS clearly defines the set of nodes that are responsible
     for relaying LSAs and performing database synchronization with
     neighbors.

   - In the above sense, a CDS node is a natural generalization of
     OSPF’s Designated Router to multi-hop networks.

   - Each node decides whether it is in the CDS based only on 2-hop
     neighbor information, allowing faster recovery from link
     failures than if each node must inform its neighbors of the
     selection (as with MPRs).

   - While existing MPR selection algorithms require full 2-hop neighbor
     information, CDS selection depends only on partial 2-hop neighbor
     information which is determined naturally as part of the CDS
     algorithm.

   - A CDS need not (but can) provide min-hop paths (unlike MPRs),
     and therefore can trade off path optimality to reduce the number
     of nodes that relay each flooded packet.

   - A CDS node can determine not only the previous-hop neighbors
     that depend on it for relaying LSAs, but also the next-hop
     neighbors that must receive the LSAs. This is important for

Ogier                    Expires August 3, 2005                 [Page 5]

Internet-Draft           MANET Extension of OSPF           February 2005

     reliable flooding, since an ACK must be received from each
     such next-hop neighbor.

   Since MPRs provide min-hop paths and are neighbor selected, they
   provide the following advantage:

   - If min-hop paths are required, MPRs may result in a smaller
     number of transmissions, since the neighbor selection of MPRs
     makes it easier to identify and eliminate redundant MPRs.

4. Proposed Family of CDS Algorithms

   In this section, we describe a family of distributed CDS algorithms
   based on 2-hop neighbor information, which is obtained from Hellos as
   described in Section 10.  The algorithms are first presented assuming
   each node has a single MANET interface; the extension to multiple
   interfaces is described in Section 4.4.

   By 2-hop neighbor information, we mean that each node knows the set
   (denoted N) of its 2-way (1-hop) neighbors and, for each 2-way
   neighbor j, the set (denoted N_j) of node j’s 2-way neighbors.  In
   addition, we assume that each node knows the Router Priority (RtrPri)
   and Router ID (RID) of each of its neighbors, as in legacy OSPF.
   These values will be used by the CDS algorithms in a way that
   generalizes OSPF’s algorithms for selecting a Designated Router.  As
   noted above, the term Designated Router (DR) will be used to mean a
   CDS node, thus generalizing the OSPF concept of a DR.  Similarly, the
   term Backup DR (BDR) will be used to denote a redundant CDS node, in
   a way that generalizes the OSPF concept of a Backup DR.

   When we say that the pair (RtrPri, RID) is larger for node i than for
   node j, we mean that the pair for node i is lexicographically greater
   than the pair for node j, i.e., either the RtrPri is larger for node
   i than for node j, or the RtrPri is the same for both nodes and the
   RID is larger for node i than for node j.

   We note that a node can select its Router Priority based on any
   criteria, including the following:

   - node degree: higher priority for larger degree

   - neighbor stability (average lifetime of neighbors): higher
     priority for higher stability

   - bandwidth capacity of node: higher priority for higher bandwidth

   - battery life: low priority if battery life is low

Ogier                    Expires August 3, 2005                 [Page 6]

Internet-Draft           MANET Extension of OSPF           February 2005

   - willingness to be a relay

   The simulation results presented in Section 11 will compare the CDS
   algorithms when RtrPri is equal to node degree, versus using the same
   RtrPri for all nodes.

   For each CDS algorithm, we first describe the non-persistent version
   of the algorithm, in which each node runs the algorithm to decide
   whether to select itself as a DR (or a Backup DR) whenever a change
   occurs to its 2-hop neighborhood, independent of the current DR
   status of itself or its neighbors.  We then describe how to modify
   the algorithm to obtain its persistent version, in which a DR
   continues to be a DR until it becomes redundant due to the existence
   of neighboring DRs with larger values of (RtrPri, RID).

4.1 The Essential CDS Algorithm

    We first describe the Essential CDS algorithm, which computes the
    smallest CDS (called the Essential CDS) of the algorithms to be
    presented.  The CDS computed by each of the other algorithms
    presented in this document will contain the Essential CDS.  In the
    following description, node i denotes the node performing the
    calculation.

    Essential CDS Algorithm (Non-Persistent Version)

    Phase 1 (DR Selection)

    1.1. If node i has a larger value of (RtrPri, RID) than any of its
         neighbors, then node i selects itself as a DR.

    1.2. Else, let j be the neighbor of node i that has the largest
         value of (RtrPri, RID). If there exists a path (with one or
         more hops, based on node i’s 2-hop neighbor information) from
         node j to each other neighbor of node i, using only
         intermediate nodes that are neighbors of node i and that have
         a larger value of (RtrPri, RID) than node i, then node i does
         not select itself as a DR; otherwise node i selects itself as
         a DR.

    Phase 2 (Backup DR Selection)

    2. If node i does not select itself as a DR in Phase 1, and if
       there exist two node-disjoint paths from node j to each other
       neighbor of node i, using only intermediate nodes that are
       neighbors of node i and that have a larger value of (RtrPri, RID)
       than node i, then node i does not select itself as a Backup DR;
       otherwise node i selects itself as a Backup DR.

Ogier                    Expires August 3, 2005                 [Page 7]

Internet-Draft           MANET Extension of OSPF           February 2005

    The selected DRs have two purposes: (1) to provide a minimal set of
    relays for flooding LSAs, and (2) to provide a minimal set of
    adjacencies for routing (not necessarily along min-hop paths).

    The selected Backup DRs also have two purposes: (1) to provide
    backup relays to retransmit flooded LSAs when flooding by DRs does
    not succeed, and (2) to provide additional adjacencies for routing,
    which provide redundant routes.  If Backup DRs are not desired, then
    Phase 2 can be omitted.

    The set of DRs computed by Phase 1 forms a CDS, and the union of the
    DRs and Backup DRs computed in both phases forms a redundant CDS
    with the following properties: each non-CDS node will have at least
    two neighbors in the CDS, and the graph consisting of all links
    adjacent to CDS nodes will be biconnected.  Note that there may be
    fewer Backup DRs than DRs, since the DRs themselves may already
    provide some redundancy.

    The persistent version of the above algorithm is similar to the non-
    persistent version given above, except that existing DRs are given
    higher priority than existing Backup DRs, which are given higher
    priority than other nodes. To describe the persistent version
    concisely, we introduce the variable DRLevel, which is equal to 2 if
    the node is a DR, 1 if the node is a Backup DR, and 0 otherwise.
    The persistent version of the above algorithm is obtained simply by
    replacing each occurrence of (RtrPri, RID) with (DRLevel, RtrPri,
    RID).  Thus, a node that is currently a DR is given the highest
    priority for remaining a DR.

    The persistent version of the Essential CDS algorithm is a true
    generalization of OSPF’s algorithm for selecting a DR and Backup DR.
    That is, in a single-hop network (where every node is a neighbor of
    every other node), both algorithms will select the same nodes as DR
    and Backup DR. This is a desirable property, since we are extending
    OSPF.

    Note that in the above CDS algorithm (and the others presented
    below), intermediate nodes are required to be neighbors of node i.
    With 2-hop neighbor information, it is possible to drop this
    requirement (and allow nodes that are two hops away to be
    intermediate nodes), to potentially obtain a smaller CDS. However,
    this would require node i to know the Router Priority of each 2-hop
    neighbor, which could be achieved by modifying Hellos to include the
    Router Priority of each neighbor.  This can also result in slower
    response to topology changes, since it may take longer to realize
    that a 2-hop neighbor is no longer a DR. Finally, simulation results
    indicate that dropping this requirement reduces the average CDS size
    only slightly.

Ogier                    Expires August 3, 2005                 [Page 8]

Internet-Draft           MANET Extension of OSPF           February 2005

    The Essential CDS algorithm can be implemented in O(d^2) time, where
    d is the number of neighbors. Step 1.2 can be implemented using a
    breadth-first-search (BFS) algorithm to compute min-hop paths from
    node j to all other neighbor of node i, modified to allow a node as
    an intermediate node only if its value of (RtrPri, RID) [or
    (DRLevel, RtrPri, RID) for the persistent version] is larger than
    that of node i.

    The BFS algorithm for Step 1.2 of the non-persistent version is as
    follows. The algorithm uses a FIFO queue so that all nodes 1 hop
    from node j are processed first, then 2 hops, etc. When the BFS
    algorithm terminates, hops(u), for each neighbor node u of node i,
    will be equal to the minimum number of hops from node j to node u,
    using only intermediate nodes that are neighbors of node i and that
    have a larger value of (RtrPri, RID) than node i.

      a. Set hops(u) = infinity for all neighbors u other than j.
      b. Set hops(j) = 0.
      c. Add node j to the queue.
      d. While the queue is nonempty:
         Remove the node at the head of the queue; call it node u.
         For each neighbor v of node u that is a neighbor of node i:
           If hops(u) + 1 < hops(v), then set hops(v) = hops(u) + 1,
           and set pred(v) = u.
           If node u has a larger value of (RtrPri, RID) than node i,
           then add node u to the tail of the queue.
      e. If hops(u) is finite for all neighbors u of node i, then
         node i does not select itself as a DR; otherwise, node i
         selects itself as a DR.

    Phase 2 of the algorithm can be implemented using a modification of
    the algorithm [Suurballe84] to find disjoint paths. However, the
    following algorithm is simpler, although it it imposes a more
    restrictive condition on the two disjoint paths (that they both have
    the same length) and therefore may result in a larger number of
    BDRs.  (Note that such an algorithm is compliant with the
    specification, since a node that would be a BDR using the Essential
    CDS algorithm will also be a BDR using this algorithm.)

      a. Let node j and d(u) be as computed in Phase 1.
      b. Set BDR_flag = 0.
      c. For each node u that is a neighbor of node i and is *not*
         a neighbor of j:
         If there exist two neighbors v and w of node u that are
         neighbors of node i, have a larger value of (RtrPri, RID) than
         node i, and satisfy d(v) = d(w) = d(u) - 1, then do nothing;
         otherwise, set BDR_flag = 1.
      d. For each node u that is a neighbor of node i and *is* a

Ogier                    Expires August 3, 2005                 [Page 9]

Internet-Draft           MANET Extension of OSPF           February 2005

         neighbor of j:
         If there exists a neighbor v of node u that is a neighbor of
         node i, and has a larger value of (RtrPri, RID) than node i,
         then do nothing; otherwise, set BDR_flag = 1.
      e. If BDR_flag = 1, node i selects itself as a BDR.

    Step d above ensures that BDRs not only provide alternate relays to
    reach 2-hop neighbors of node j, but also to reach 1-hop neighbors
    of node j, which is important since the link from node j to such a
    neighbor can break.

    The Essential CDS algorithm computes a minimal CDS (the DRs) and a
    minimal redundant (biconnected) CDS (the DRs and BDRs).  However, it
    may be desirable to use a CDS algorithm that computes a larger CDS,
    for example, to obtain a CDS that achieves a smaller stretch factor
    (defined above).  Such an algorithm will be interoperable with the
    Essential CDS algorithm as long as it computes a CDS that contains
    the Essential CDS, i.e., as long as each node that is in the
    Essential CDS selects itself as a DR. Thus, to ensure
    interoperability, each node in the Essential CDS MUST select itself
    as a DR. However, a node that is not in the Essential CDS MAY select
    itself as DR.

    The next section describes two subfamilies of distributed CDS
    algorithms, each of which computes a CDS that contains the Essential
    CDS.  As shown in simulations results presented below, some of these
    algorithms achieve a smaller stretch factor at the cost of a larger
    CDS.

4.2. Max-Priority-Neighbor (MPN) CDS Algorithm Family

    In the Essential CDS algorithm, node i selects itself as a DR if it
    cannot find a path from the neighbor j with maximum value of
    (RtrPri, RID) to each other neighbor, using only intermediate nodes
    with a larger value of (RtrPri, RID) than node i.  The MPN CDS
    algorithm family is similar, but requires that each such path be at
    most h1 hops long, where the parameter h1 is an integer greater than
    or equal to 2. By choosing h1 to be small, a larger CDS is obtained,
    but hopefully the CDS has a smaller stretch factor and can thus be
    used to provide shorter paths.

    The MPN CDS algorithm uses a second parameter h2 for computing
    Backup DRs in Phase 2. Phase 2 requires that there exist two
    disjoint paths from neighbor j to each other neighbor, with each
    path having at most h2 hops.  It is possible for h2 to be either
    larger or smaller than h1.  The MPN CDS algorithm with parameters h1
    and h2 will be denoted MPN(h1, h2).

Ogier                    Expires August 3, 2005                [Page 10]

Internet-Draft           MANET Extension of OSPF           February 2005

    MPN(h1, h2) CDS Algorithm (Non-Persistent Version)

    Phase 1 (DR Selection)

    1.1. If node i has a larger value of (RtrPri, RID) than any of
         its neighbors, then node i selects itself as a DR.

    1.2. Else, let j denote the neighbor of node i that has the largest
         value of (RtrPri, RID). If there exists a path with at most h1
         hops (based on node i’s 2-hop neighbor information) from node j
         to each other neighbor of node i, using only intermediate nodes
         that are neighbors of node i and that have a larger value of
         (RtrPri, RID) than node i, then node i does not select itself
         as a DR; otherwise node i selects itself as a DR.

    Phase 2 (Backup DR Selection)

    2. If node i does not select itself as a DR in Phase 1, and if
       there exist two node-disjoint paths from node j to each other
       neighbor of node i, each with at most h2 hops, using only
       intermediate nodes that are neighbors of node i and that have
       a larger value of (RtrPri, RID) than node i, then node i does
       not select itself as a Backup DR; otherwise node i selects
       itself as a Backup DR.

    As with the Essential CDS algorithm, the persistent version of the
    MPN algorithm can be obtained simply by replacing each occurrence of
    (RtrPri, RID) with (DRLevel, RtrPri, RID).  It is clear that the CDS
    computed by the MPN algorithm contains the CDS computed by the
    Essential CDS algorithm, since if Phase 1 of the MPN algorithm does
    not result in node i selecting itself as a DR, then a path exists
    between node j and each other neighbor of node i, and thus Phase 1
    of the Essential CDS algorithm will not result in node i selecting
    itself as a DR.  The Essential CDS algorithm is equivalent to the
    MPN algorithm with h1 and h2 equal to infinity.

    The MPN CDS algorithm can be implemented in O(d^2) time.  The
    implementation is the same as that described for the Essential CDS
    algorithm, the only difference being that the computed distances
    d(u), for each neighbor u, must be at most h1 for Phase 1, and at
    most h2 for Phase 2, for node i not to select itself as a DR (Phase
    1) or BDR (Phase 2).

4.3. All-Neighbor-Pairs (ANP) CDS Algorithm Family

    The ANP CDS algorithm family is similar to the MPN CDS algorithm
    family, with the same parameters h1 and h2, but the requirements
    imposed on the existence of paths from the neighbor j (with maximum

Ogier                    Expires August 3, 2005                [Page 11]

Internet-Draft           MANET Extension of OSPF           February 2005

    value of (RtrPri, RID)) to all other neighbors, are now imposed on
    the existence of paths from *every* neighbor of node i to all other
    neighbors. As a result, the CDS computed by ANP(h1, h2) contains
    (and is usually larger than) the CDS computed by MPN(h1, h2).
    Although ANP computes a larger CDS than MPN, the benefit is that it
    is more likely to have a smaller stretch factor. In fact, if either
    h1 = 2 or h2 = 2, then ANP is guaranteed to achieve a stretch factor
    of 1, i.e., the CDS consisting of DRs and BDRs will provide min-hop
    paths between any pair of nodes.  Selecting h1 = 3 and h2 = 2
    results in a relatively small set of DRs (resulting in a small
    flooding overhead), while providing min-hop paths via the
    adjacencies induced by the BDRs.

    Each node running the ANP algorithm maintains a list of Dependent
    Neighbors and a list of Backup Dependent Neighbors.  The use of
    (Backup) Dependent Neighbors is described in Sections 5 and 6.  For
    the Essential CDS and MPN CDS algorithms, all neighbors of a DR are
    Dependent Neighbors, and all neighbors of a BDR are Backup Dependent
    Neighbors.

    A node running the ANP algorithm is called a DR if it has at least
    one Dependent Neighbor, and a BDR if it has at least one Backup
    Dependent Neighbor.  Since a node can have both a Dependent Neighbor
    and a Backup Dependent Neighbor, a node can be both a DR and a BDR.
    However, a neighbor that is Dependent cannot also be Backup
    Dependent.  Also, a node cannot be both an Essential DR and an
    Essential BDR (defined in Section 6).

    ANP(h1, h2) CDS Algorithm (Non-Persistent Version)

    Phase 1 (DR Selection)

    1.1. If node i has a larger value of (RtrPri, RID) than any of its
         neighbors, then node i selects itself as a DR, adds all
         neighbors to the list of Dependent Neighbors, and exits.

    1.2. Initialize the list of Dependent Neighbors to be empty.
         For each neighbor node j, if there exists a path with at
         most h1 hops (based on node i’s 2-hop neighbor information)
         from neighbor j to each other neighbor of node i,
         using only intermediate nodes that are neighbors of node i
         and that have a larger value of (RtrPri, RID) than node i,
         then do not add node j to the list of Dependent Neighbors;
         otherwise, add node j to the list.

    1.3. If the list of Dependent Neighbors is not empty, then node i
         selects itself as a DR. In this case, node i MAY include all
         neighbors in the list of Dependent Neighbors (not recommended

Ogier                    Expires August 3, 2005                [Page 12]

Internet-Draft           MANET Extension of OSPF           February 2005

         if h1 = 2).

    Phase 2 (Backup DR Selection)

    2.1. Initialize the list of Dependent Neighbors to be empty.
         For each neighbor node j that was not selected as a Dependent
         Neighbor in Phase 1, if there exist two node-disjoint
         paths from neighbor j to each other neighbor of node i, each
         with at most h2 hops, using only intermediate nodes that are
         neighbors of node i and that have a larger value of
         (RtrPri, RID) than node i, then do not add node j to the list
         of Backup Dependent Neighbors; otherwise, add node j to the
         list.

    2.2. If the list of Backup Dependent Neighbors is not empty, then
         node i selects itself as a Backup DR. In this case, node i MAY
         include all neighbors in the list of Backup Dependent Neighbors
         (not recommended if h2 = 2).

    As with the MPN algorithm, the persistent version of the ANP
    algorithm can be obtained simply by replacing each occurrence of
    (RtrPri, RID) with (DRLevel, RtrPri, RID).

    The ANP CDS algorithm can be implemented in O(d^3) time.  The
    implementation is the same as for the MPN algorithm, except that BFS
    must be run for each neighbor of node i, instead of a single
    neighbor.  Note that O(d^2) time is required just to cycle through
    all neighbors’ neighbors. Given this and the fact that processor
    speeds are much faster than when OSPF was first used in the 1980s, a
    time complexity of O(d^3) is quite reasonable, especially since the
    real bottleneck for MANETs is bandwidth, not processing. Also, note
    that the ANP algorithm is optional.

    The following important relationship exists between the set of DRs
    computed by ANP and MPN (for the same value of h1): A router is
    selected as a DR by the MPN algorithm if and only if either it has a
    larger (RtrPri, RID) than all of its neighbors, or the neighbor node
    j with the largest value of (RtrPri, RID) is selected as a Dependent
    Neighbor by the ANP algorithm.  (Such a router is called an
    Essential DR, as defined in Section 6.)  As a result, a node that
    runs the ANP algorithm can quickly determine whether it belongs to
    the smaller CDS computed by the MPN algorithm, and can choose to
    relay LSAs only if it belongs to the smaller CDS (thus reducing
    overhead).

Ogier                    Expires August 3, 2005                [Page 13]

Internet-Draft           MANET Extension of OSPF           February 2005

4.4. Multiple Interfaces

    The above descriptions of the CDS algorithms assume that each
    router has a single MANET interface. If a router has multiple MANET
    interfaces, each router sends and receives Hellos (as described in
    Section 10) on each interface. Using the 2-hop neighbor information
    obtained from Hellos received on all interfaces, node i constructs
    the set N_j of neighbors of each neighbor node j, via any interface
    that is common to both nodes i and j.  The above CDS algorithms are
    then applied using this 2-hop neighbor information based on all
    interfaces.

    If a MANET router also has one or more non-MANET interfaces, then
    the router MAY also use 2-hop neighbor information obtained from
    LSAs originating from neighboring routers attached to its non-MANET
    interfaces. For example, if two neighboring MANET routers are also
    attached to the same broadcast network, then it may not be necessary
    for both routers to forward LSAs from the MANET to the broadcast
    network, and vice versa. (Note that we are assuming the MANET and
    the broadcast network belong to the same area.)

4.5. Relation of the Proposed CDS Algorithms to Other Algorithms

    In TBRPF [RFC3684], the set of all nodes that have at least one
    "reported neighbor" (and therefore forward link-state updates
    originating from other nodes) is a CDS, which is the same as the CDS
    computed by Phase 1 of the ANP algorithm with h1 = 2 and RtrPri the
    same for all nodes.

    Phase 1 of the ANP algorithm with h1 = 2 is also equivalent to Phase
    1 of the CDS algorithm of [Lin03] if RtrPri is equal to the node
    degree. However, the simulations presented in [Lin03] assume that a
    flooded packet is forwarded only if it is received from the
    equivalent of a Dependent Neighbor, as in step (b) of the forwarding
    procedure given in Section 6 of this document.

    Phase 1 of the MPN algorithm with h1 = 2 and RtrPri the same for all
    nodes is similar to the MPR-based CDS algorithm in [Adjih02] using
    the min-ID algorithm for computing MPRs. The main difference is that
    the MPN algorithm does not compute neighbor-selected MPRs.
    (However, one can say that the MPN algorithm determines whether the
    neighbor j with maximum (RtrPri, RID) would select node i as an
    MPR.)

Ogier                    Expires August 3, 2005                [Page 14]

Internet-Draft           MANET Extension of OSPF           February 2005

5. Adjacencies and LSAs

   Adjacencies are formed only between DR/BDR routers and their
   neighbors, as in legacy OSPF. Thus, adjacencies are not allowed
   between two DR_Other (non-DR/BDR) routers. However, if the ANP CDS
   algorithm is used, a DR/BDR router need not be adjacent to all of its
   neighbors. The requirement is that a router must form an adjacency
   with each (Backup) Dependent Neighbor.  If the Essential CDS or MPN
   CDS algorithm is used, then all neighbors of each DR/BDR router are
   (Backup) Dependent. But this may not be true if the ANP algorithm is
   used (although the ANP algorithm allows this as an option).

   It is possible for router B to be a Dependent Neighbor of router A,
   even if router A is not a Dependent Neighbor of router B. Thus, an
   adjacency must be formed between two routers if either of them is a
   (backup) Dependent Neighbor of the other.  A router knows which
   neighbors have selected it as a (Backup) Dependent Neighbor, since
   this information is advertised in Hello packets as described in
   Section 10.  Once formed, an adjacency between two routers A and B
   continues as long as either router is a Dependent Neighbor of the
   other router.

   Another question is which neighbors to include in the Router LSA
   originated by a MANET router.  Each such neighbor is represented as a
   Type 1 link (point-to-point) in the Router LSA.  The minimum
   requirement is that a router must include all (Backup) Dependent
   Neighbors in its LSA.  Since DR_Other routers have no Dependent
   Neighbors, this implies that the LSA originated by such a router can
   be empty (contain no neighbors), thus reducing overhead
   significantly.  (Such a router will still have adjacencies with
   neighboring DRs and BDRs, which can be used to construct the
   shortest-path tree.)  However, a better choice may be to include all
   adjacent neighbors in the LSA, in which case the LSA originated by a
   DR_Other router will include only DR and BDR neighbors.

   In addition, a router MAY include any non-adjacent, bidirectional
   neighbors in its LSA. For example, in the full topology case, every
   router includes all of its bidirectional neighbors in its LSA.

   The above choices, along with the choices for the CDS algorithm,
   allows much flexibility. Interoperability is ensured even if
   different routers make different choices, as long as the minimum
   requirements are satisfied. Some examples of possible choices are as
   follows:

   1. Select DRs and BDRs using MPN with h1 = h2 = 3. Each DR/BDR
      router forms adjacencies with all neighbors. Each router
      includes all neighbors in its LSA (full topology).

Ogier                    Expires August 3, 2005                [Page 15]

Internet-Draft           MANET Extension of OSPF           February 2005

   2. Select DRs and BDRs using ANP with h1 = h2 = 3.
      Each DR/BDR router forms adjacencies with all neighbors.
      Each router includes only adjacent neighbors in its LSA.
      The resulting routes will be very close to min-hop as shown
      by the simulation results presented in Section 11.

   3. Select DRs and BDRs using ANP with h1 = 3 and h2 = 2. Each
      DR/BDR router forms adjacencies only with Dependent Neighbors.
      Each router includes only adjacent neighbors in its LSA.
      This provides min-hop routing because h2 = 2.

   4. Same as 3, but use h1 = 2 and h2 = 2. This will not only
      provide min-hop routing (because h1 = 2), but will also
      result in flooding along min-hop paths, if the optional step (b)
      of the flooding procedure below is used.

6. Flooding Procedure

   This section describes the flooding procedure.  Much of the procedure
   is the same as described in Section 13 of RFC 2328, so we focus on
   the differences.

   The processing of received LSAs is the same as in Section 13 of RFC
   2328, Steps (1) through (8), except that a router MUST process an LSA
   received from any 2-way neighbor (not just from adjacent neighbors in
   Exchange state or higher), in order to take advantage of multicast
   transmissions to reduce the number of retransmissions.

   On MANET interfaces, LSU packets that do not contain retransmitted
   LSAs are always multicast to AllSPFRouters.

   The procedure for forwarding LSAs is as in Section 13.3 of RFC 2328,
   with the following modifications.  Replace Step 1c with the
   following: If the new LSA, or an ACK for the new LSA, was received
   from this neighbor, examine the next neighbor.  Remove Steps 3 and 4,
   and replace Step 5 with the Forwarding Procedure below, which
   requires the following definition:

   A DR is called an Essential DR if it has a larger value of (RtrPri,
   RID) than all of its neighbors, or if the neighbor with maximum
   (RtrPri, RID) is a Dependent Neighbor.  A BDR is called an Essential
   BDR if the neighbor with maximum (RtrPri, RID) is a Backup Dependent
   Neighbor.  If the persistent version of a CDS algorithm is used, then
   (DRLevel, RtrPri, RID) is used instead of (RtrPri, RID).  If the
   Essential CDS or MPN CDS algorithm is used, then all neighbors of a
   (Backup) DR are (Backup) Dependent, so a (Backup) DR is always
   Essential in this case.

Ogier                    Expires August 3, 2005                [Page 16]

Internet-Draft           MANET Extension of OSPF           February 2005

   Forwarding Procedure

   (a) If the router is an Essential DR, then the new LSA MUST be
       flooded out the minimum ID interface corresponding to each
       adjacent router from which the new LSA has not been received,
       and that is not a neighbor (based on 2-hop neighbor information)
       of the router from which the new LSA was received.

   (b) Else, if the router is a DR and the neighbor from which the new
       LSA was received is a Dependent Neighbor, then the new LSA MAY
       be flooded out the minimum ID interface corresponding to each
       adjacent router from which the new LSA has not been received,
       and that is not a neighbor (based on 2-hop neighbor information)
       of the router from which the new LSA was received.

   (c) If the router is an Essential BDR, then the router waits
       BackupWaitInterval seconds after receiving the new LSA.
       After this interval, the new LSA MUST be flooded out the
       minimum ID interface corresponding to each adjacent router
       from which the new LSA has not been received, and that is
       not a neighbor (based on 2-hop neighbor information) of
       any router from which the new LSA was received.

   (d) Else, if the router is a BDR and the neighbor from which the
       new LSA was received is a Backup Dependent Neighbor, then the
       router waits BackupWaitInterval seconds after receiving the new
       LSA. After this Interval, the new LSA MAY be flooded out the
       minimum ID interface corresponding to each adjacent router
       from which the new LSA has not been received, and that is
       not a neighbor (based on 2-hop neighbor information) of
       any router from which the new LSA was received.

   Note that duplicate LSAs are not forwarded; a new LSA is considered
   for forwarding only the first time it is received.  Step (a) of the
   Flooding Rule ensures that the LSA is forwarded by all nodes in the
   Essential CDS, regardless of which optional CDS algorithm is used,
   and regardless of the order in which nodes transmit a given LSA.  The
   optional step (b) can be used to reduce the flooding delay, at the
   cost of some additional overhead. If the ANP algorithm is used with
   h1 = 2, then Step (b) ensures that LSAs are flooded along min-hop
   paths.

   One of the duties of a BDR is to forward a new LSA when one its
   neighboring DRs fails to transmit the LSA.  Step (c) requires an
   Essential BDR to forward the new LSA after a small delay
   (BackupWaitInterval) if the neighbors that are known to have
   transmitted the new LSA do not cover all adjacent neighbors.
   BackupWaitInterval must be less than RxmtInterval, to avoid

Ogier                    Expires August 3, 2005                [Page 17]

Internet-Draft           MANET Extension of OSPF           February 2005

   unnecessary retransmissions.  The optional step (d) is similar to the
   optional step (b), but for a BDR instead of a DR.

   A Backup DR is analogous to a "non-active overlapping relay" in
   Cisco’s proposed solution [Chandra04], and the parameter
   BackupWaitInterval is equivalent to PushbackInterval in their draft.

7. Retransmitting LSAs

   LSAs are retransmitted according to Section 13.6 of RFC 2328.  As in
   legacy OSPF, LSAs are retransmitted only to adjacent routers.  Thus,
   since the proposed solution does not allow an adjacency to be formed
   between two DR_Other routers, a DR_Other router never retransmits an
   LSA to another DR_Other router (only to a DR or BDR router as in
   legacy OSPF). As in OSPF, retransmitted LSAs are unicast, but see
   Section 9.2 for a proposed modification that allows retransmitted
   LSAs to be multicast.

   One advantage of allowing only DR and BDR routers to retransmit LSAs
   to DR_Other routers is that DR and BDR routers can group together
   several retransmitted LSAs into the same LSU packet, thus reducing
   overhead. In particular, if a DR_Other router originates an LSA, it
   only needs to retransmit its LSA to DR and BDR neighbors.

8. Link State Acknowledgments

   As proposed in [Chandra04], all Link State Acknowledgments (LS ACKs)
   are multicast, a duplicate received LSA is not acknowledged unless it
   is a unicast retransmission, and each router maintains a database of
   all recently received LS ACKs.  As in legacy OSPF, a forwarded LSA is
   treated as an implicit ACK, and multiple delayed ACKs may be bundled
   into a single packet.

   As in legacy OSPF, LS ACKs are processed only by adjacent neighbors.
   Therefore, since we do not allow two DR_Other routers to be adjacent,
   an ACK sent by a DR_Other router will be processed only by DR and BDR
   routers (as in legacy OSPF).  Thus, ACKs and retransmitted LSAs are
   sent only between adjacent routers. Retransmitted LSAs are sent only
   to adjacent routers from which an explicit or implicit ACK has not
   been received.

9. Proposed Enhancements

   We propose three enhancements which can be used to reduce overhead:
   more efficient database exchange, multicasting retransmitted LSAs,

Ogier                    Expires August 3, 2005                [Page 18]

Internet-Draft           MANET Extension of OSPF           February 2005

   and non-ackable LSAs.

9.1. More Efficient Database Exchange

    When a router becomes a DR or BDR, it must form adjacencies with
    some or all of its neighbors, which can consume a lot of bandwidth
    in dense networks, since a complete set of Database Description (DD)
    packets is unicast to and from each neighbor in legacy OSPF.  Two
    modifications can be used to significantly reduce the overhead of
    this exchange. First, it is not necessary for the slave to send a
    complete set of DD packets; it is sufficient for the slave to
    include in its DD packet(s) only LSA headers that are more recent or
    are not included in the DD packets sent by the master.  To
    accomplish this, the slave does not include any LSA headers in its
    DD packets until the master has sent its last DD packet (indicated
    by the "more" bit being 0), so that it knows which LSA headers to
    include in its DD packets to the master.

    The second modification is for a new DR/BDR that has decided to form
    adjacencies with all of its neighbors (which is the case if the
    Essential CDS or MPN CDS algorithm is used).  Just as a router
    transmits LSAs as multicasts, and then retransmits them as unicasts
    when necessary, a new DR or BDR can first send a complete set of DD
    packets as multicasts, and then retransmit them as unicasts when
    necessary. To make this work, the new DR or BDR should be the
    master, and all of its neighbors should be slaves.  When such a
    slave sees a multicast DD packet from a 2-Way neighbor that is not
    yet fully adjacent, it replies by unicasting a (possibly empty) DD
    packet having the same DD sequence number.  In the ideal case (where
    all nodes are already synchronized and no retransmissions are
    needed) the master will multicast a complete set of DD packets, and
    its neighbors (that are not yet fully adjacent) will respond by
    sending only empty DD packets, thus saving a lot of overhead.  If
    the master multicasts a DD packet but does not receive an
    acknowledgment (i.e., a possibly empty DD packet with the same
    sequence number) from some neighbor that is not yet fully adjacent,
    then the master retransmits the DD packet as a unicast.

    Alternatively, retransmitted DD packets can be multicast instead of
    unicast, using the same idea as described below for multicasting
    retransmitted LSAs. A new TLV would be defined to list the neighbors
    that must acknowledge the DD packet.

9.2. Multicasting Retransmitted LSAs

    If a router must retransmit a given LSA to several neighbors, it
    would be more efficient to retransmit the LSA as a multicast.
    However, since each router acknowledges a multicast LSA only the

Ogier                    Expires August 3, 2005                [Page 19]

Internet-Draft           MANET Extension of OSPF           February 2005

    first time it is received, a modification is needed to ensure that
    the intended recipients acknowledge the retransmitted LSA.  This can
    be accomplished by defining a new TLV that provides a list of the
    neighbors that must acknowledge the LSA.  If the LSA must be
    retransmitted again, the neighbors from which an ACK has been
    received are removed from the list. This idea was proposed several
    years ago by the MANET working group.

9.3. Non-Ackable LSAs

    In a highly mobile network, it is possible that a router almost
    always originates a new 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. In this case, the originator of
    an LSA MAY indicate that the LSA is "non-ackable" via a new option
    bit. For example, the originator can use an exponential moving
    average to determine that a new LSA is originated every
    MinLSInterval seconds with probability greater than 90 percent.
    (Simulations are needed to determine the best threshold.)

    A non-ackable LSA is never ACKed, nor is it ever retransmitted as a
    unicast. However, the originating router and each Essential DR (as
    defined in Section 6) must periodically retransmit a non-ackable LSA
    as a multicast. The retransmission period 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 forwarding procedure of Section 6.  In
    addition, non-ackable LSAs need not be described in DD packets.

10. Differential Hello Protocol

   Hellos are used both for neighbor discovery and for obtaining 2-hop
   neighbor information. Although it is possible to obtain 2-hop
   neighbor information from LSAs originated by neighbors, we choose to
   use Hellos for this purpose, for the following reasons:

   - The content of LSAs, and the the flooding of LSAs, depend on which
     neighbors are adjacent, and 2-hop neighbor information is needed
     before a router can decide which neighbors should be adjacent.

   - 2-hop information can be different from that obtainable from LSAs.
     For example, LSAs may report only partial topology, whereas a node
     may report all of its (2-way) neighbors to provide full 2-hop
     neighbor information.

Ogier                    Expires August 3, 2005                [Page 20]

Internet-Draft           MANET Extension of OSPF           February 2005

   - By making the flooding protocol independent of LSAs, it can be
     used in MANET applications other than OSPF.

   One of the advantages of the proposed method (versus using neighbor-
   selected MPRs) is that full 2-hop neighbor information is not
   required. In fact, it is only necessary for each router to keep all
   neighbors informed of its (Backup) Dependent Neighbors.  This can
   reduce overhead dramatically in a highly mobile, dense network.

   The Hello protocol described below is flexible in that a router can
   send full Hellos that provide full 2-hop neighbor information, or can
   send differential Hellos and provide only *partial* 2-hop neighbor
   information by periodically including a list of its Dependent
   Neighbors in a Hello (to reduce overhead).  It can also send
   differential Hellos and provide *full* 2-hop neighbor information by
   periodically sending a full Hello.  This latter approach reduces
   overhead by sending full Hellos less frequently (e.g., every 10
   seconds), while sending differential Hellos more frequently (e.g.,
   every 2 seconds) to allow faster response to topology changes.

10.1. Full Hellos

    We first describe the contents of a full Hello packet, which depends
    on the state of each neighbor (Down, Init, 2-Way, etc. as in legacy
    OSPF), and on whether each neighbor is Dependent. (A neighbor in
    state 2-Way or higher may or may not be Dependent.)  A full Hello
    contains three lists of Router IDs, which are formatted as TLVs:

    - Heard Neighbor List (HNL): Includes all neighbors in state
      Init or higher that are not included in the Dependent Neighbor
      List or the Non-Dependent Neighbor List.

    - Dependent Neighbor List (DNL): Includes all Dependent and
      Backup Dependent neighbors. (Such neighbors are in state 2-Way
      or higher.)

    - Non-Dependent Neighbor List (NDNL): Includes all neighbors
      in state 2-Way or higher that are not (Backup) Dependent.

    Note that a full Hello includes the Router ID of each neighbor that
    is in state Init or higher, as does a Hello in legacy OSPF.  A
    router that chooses not to send differential Hellos must send a full
    Hello every HelloInterval seconds.

10.2. Differential Hellos

    A differential Hello includes neighbors whose status has recently
    changed, and also includes a full Dependent Neighbor List

Ogier                    Expires August 3, 2005                [Page 21]

Internet-Draft           MANET Extension of OSPF           February 2005

    periodically, at least once every 2HopRefresh seconds (typically
    equal to a few Hello intervals).  If the router chooses to report
    full 2-hop neighbor information, indicated by the parameter
    Full2HopNbrInfo being equal to 1, then a full Non-Dependent Neighbor
    List must also be included in a Hello every 2HopRefresh seconds.
    (Alternatively, a full Hello may be sent every 2HopRefresh seconds.)

    In a differential Hello, the HNL, DNL, and NDNL lists can be partial
    or full, indicated by an option bit.  In addition to these lists, a
    differential Hello may also include the following list:

    - Lost Neighbor List (LNL): Includes neighbors that recently
      transitioned to the Down state.

    Whenever the status of a neighbor changes (as defined below), the
    neighbor is included in the appropriate list of the next
    RouterDeadCount (typically 3) Hellos, or until the status changes
    again. Each Hello contains a Hello Sequence Number (HSN), which is
    incremented with each Hello sent on a given interface.  This allows
    a router to determine whether it has missed RouterDeadCount
    consecutive Hellos sent by a neighbor, and thus may have missed a
    status change reported by the neighbor, as described in the section
    on receiving Hellos.

    The status changes that are reported in Hellos, and the
    corresponding list in which the neighbor is included, are as
    follows:

    - The neighbor state changes to Down: Lost Neighbor List.

    - The neighbor state changes to Init: Heard Neighbor List

    - The neighbor becomes Dependent: Dependent Neighbor List

    - The neighbor state changes to 2-Way (or higher) and the neighbor
      is not (Backup) Dependent: Heard Neighbor List if Full2HopNbrInfo
      is 0; otherwise Non-Dependent Neighbor List.

    - The neighbor changes from (Backup) Dependent to non-dependent, but
      is still 2-Way (or higher): Heard Neighbor List if Full2HopNbrInfo
      is 0; otherwise Non-Dependent Neighbor List.

    Note that a neighbor that is included in a differential Hello
    appears in the same list as it would in a full Hello, except that if
    Full2HopNbrInfo is 0, then a non-dependent neighbor appears in the
    Heard list instead of the Non-Dependent list. (The latter list is
    never included in a Hello if Full2HopNbrInfo is 0.)

Ogier                    Expires August 3, 2005                [Page 22]

Internet-Draft           MANET Extension of OSPF           February 2005

    Note that if the state of a neighbor changes from Down to Init (and
    the neighbor is therefore included in the next 3 Hellos), and the
    state of the neighbor later changes to 2-Way, then the neighbor must
    again be included in 3 consecutive Hellos (assuming RouterDeadCount
    is 3).  This is to ensure that the neighbor will either see itself
    in one of the Hellos, or will declare the sending router Down after
    missing 3 Hellos.

    There is one exception to the above rule.  If the state of a
    neighbor changes from Down to Init (and the neighbor is therefore
    included in the next 3 Hellos), and the state changes to 2-Way
    before the fourth Hello is sent, then the neighbor need not be
    included in additional Hellos (since the neighbor must have received
    one of the 3 Hellos that included the neighbor, or will declare the
    sending router Down).

10.3. Receiving Hellos

    A received Hello is processed first to update the state of the
    sending neighbor, and then to update the 2-hop neighbor information.
    The neighbor state can be affected by the following events related
    to received Hellos:

    SufficientHellosReceived
      A Hello has been received from the neighbor. To ensure good link
      quality, and to employ hysteresis, a stricter condition may be
      imposed, such as requiring that two consecutive Hellos have been
      received.

    2-WayReceived
       Router sees itself in any list of the neighbor’s Hello
       packet except for the Lost Neighbors list.

    1-WayReceived
       Router sees itself in the Lost Neighbors list of the neighbor’s
       Hello packet, or does not see itself in any list of a full
       Hello packet.

    InsufficientHellosReceived
       A Hello has been received whose sequence number indicates that
       the last RouterDeadCount Hellos were missed. To ensure good
       link quality, other criteria may be used, such as missing k of
       the last n Hellos (for some k and n). However, this event MUST
       occur whenever the last RouterDeadCount Hellos were missed.

    InactivityTimer
       No Hello has been received from the neighbor for
       RouterDeadInterval, which must be at least RouterDeadCount

Ogier                    Expires August 3, 2005                [Page 23]

Internet-Draft           MANET Extension of OSPF           February 2005

       times HelloInterval.

    These events cause the following neighbor state changes, which in
    turn may affect the contents of future Hello packets as described
    above.

      Event                        Old State(s)    New State
      ------------------------     ------------    ---------
      SufficientHellosReceived     Down             Init

      2-WayReceived                Init             2-Way

      1-WayReceived                2-Way or higher  Init

      InsufficientHellosReceived   Init or higher   Down

      InactivityTimer              Init or higher   Down

10.4. Processing a Hello for 2-hop Neighbor Information

    Each router maintains, for each neighbor j in state Init or higher,
    a list DN_j of (Backup) Dependent neighbors reported by node j, and
    a list NDN_j of non-dependent neighbors reported by node j. (The
    latter list will be empty if node j is not reporting full 2-hop
    neighbor information.)  The union of these two lists is N_j, the
    list of all neighbors reported by node j.  The list N_j for all
    neighbors j that are in state 2-Way or higher constitutes the 2-hop
    neighbor information, which is used by the CDS algorithm.

    If partial 2-hop neighbor information is used, it is possible that
    two neighbors j and k are such that j is in N_k but k is not in N_j.
    Therefore, when computing paths between neighbors in the CDS
    algorithms, a bidirectional link is assumed to exist between two
    neighbors j and k if *either* j is in N_k or k is in N_j.

    If a Hello that contains a full DNL (respectively, NDNL) is received
    from neighbor j, then the router simply stores the list in its
    database as DN_j (respectively, NDN_j), replacing the old database
    copy.

    If a Hello that contains a partial DNL (respectively, NDNL) is
    received from neighbor j, then the router adds the Router IDs in the
    received list to DN_j (respectively, NDN_j).

    A router is deleted from DN_j (respectively, NDN_j) if it appears in
    any list other than the DNL (respectively, NDNL) in a Hello received
    from neighbor j.  This provides fast reporting of deleted 2-hop

Ogier                    Expires August 3, 2005                [Page 24]

Internet-Draft           MANET Extension of OSPF           February 2005

    neighbor information in differential Hellos.  (Note that a given
    router can appear in at most one list in a Hello.)

10.5. Comparison to Other Differential Hello Protocols

    The proposed Hello protocol differs in several ways from three
    existing Hello protocols that also use differential Hellos: TBRPF
    [RFC3684], OLSR [RFC3626], and Cisco’s proposed OSPF extension
    [Chandra04].

    First, TBRPF and Cisco’s protocol do not use Hellos to advertise
    2-hop neighbor information, although OLSR does.  However, OLSR
    advertises full 2-hop neighbor information and is not easily
    modified to advertise only partial 2-hop neighbor information, since
    all neighbors must be included in a Hello periodically. (Note that
    the proposed Hello protocol works even if the router has no
    Dependent Neighbors and therefore reports no 2-hop neighbor
    information.)  In fact, OLSR requires full 2-hop neighbor
    information for the selection of MPRs, whereas the proposed protocol
    requires only partial 2-hop neighbor information for the selection
    of (Backup) DRs and (Backup) Dependent Neighbors.

    Also, Cisco’s protocol requires that a node unicast a Hello request
    message to a neighbor from which a Hello was missed.  In highly
    mobile, dense networks, Hello requests can occur frequently, thus
    generating a large amount of overhead.  The proposed Hello protocol
    avoids the use of a Hello request by reporting each neighbor state
    change a few (RouterDeadCount) times.

11. Simulation Comparison of CDS Algorithms

   This section compares five algorithms from the family of CDS
   algorithms presented in Section 4: Essential CDS, MPN (h1 = 3), ANP
   (h1 = 3), MPN (h1 = 2), ANP (h1 = 3). Only DRs (not Backup DRs) are
   computed, and only the non-persistent version of each algorithm is
   considered. Each algorithm is compared with RtrPri the same for all
   nodes, and with RtrPri equal to the node degree.  The algorithms are
   compared with respect to average CDS size (number of DRs) and average
   stretch factor (defined in the Introduction).

   For each experiment, each algorithm was run on 100 randomly generated
   graphs, with the CDS size and stretch factor averaged over these
   graphs.  The number of nodes ranges from 50 to 300, with the nodes
   randomly placed in a unit square. Two values were used for the
   transmission radius: 0.3 and 0.5. The average diameter of the graph
   is about 5 for radius 0.3, and about 3 for radius 0.5. For 100 nodes,
   the average degree was 21.38 for radius 0.3 and 48.04 for radius 0.5.

Ogier                    Expires August 3, 2005                [Page 25]

Internet-Draft           MANET Extension of OSPF           February 2005

   Table 1 gives the average CDS sizes and Table 2 gives the average
   stretch factor, for a radius of 0.3. Tables 3 and 4 give the results
   for a radius of 0.5.

   As expected, the most scalable of the CDS algorithms is the Essential
   CDS algorithm, whose CDS size increased only slightly, from 20.36 to
   23.26, when the number of nodes was increased from 100 to 300, for
   radius 0.3.  In contrast, ANP with h1 = 2 and RtrPri equal to the
   node degree, resulted in a CDS size that increased from 49.58 to
   167.94 when the number of nodes was increased from 100 to 300.  For
   300 nodes, this algorithm selected about 56% of the nodes, while the
   Essential CDS algorithm selected about 8% of the nodes.  However,
   note that the forwarding procedure of Section 6 results in only a
   subset of the CDS nodes forwarding a given LSA, if the ANP algorithm
   is used.

   Surprisingly, the Essential CDS algorithm, and all CDS algorithms
   with h1 = 3, gave a smaller CDS *without* using node degree, when the
   number of nodes was greater than 100.  Thus, the most scalable
   algorithms do not use node degree.  Another advantage of not using
   node degree is that it results in a more stable CDS in a mobile
   network (since the node degree changes as the topology changes).

   As expected, the average stretch factor is smaller for ANP than for
   MPN (for the same value of h1), and is smaller with h1 = 2 than with
   h1 = 3.  It is interesting that using node degree always results in a
   smaller stretch factor.  Of course, the stretch factor for ANP with
   h1 = 2 is always 1, since this algorithm provides flooding along min-
   hop paths.

   The choice of which algorithm to use depends on what stretch factor
   is considered acceptable.  For example, if one wishes to obtain the
   smallest CDS that has a stretch factor less than 1.05 in a 200 node
   network, then the best choice would be ANP with h1 = 3 and RtrPri
   equal to node degree.  Note that all of these algorithms are
   interoperable since the CDS computed by each algorithm contains the
   Essential CDS. Therefore, different routers MAY use different
   algorithms from the proposed family of CDS algorithms.

Ogier                    Expires August 3, 2005                [Page 26]

Internet-Draft           MANET Extension of OSPF           February 2005

                                      Number of Nodes
           --------------------------------------------------
           Algorithm   RtrPri    50     100     200     300
           --------------------------------------------------
           Essential     1      17.50   20.36   22.14   23.26
           Essential   degree   13.79   18.66   27.42   33.14
           --------------------------------------------------
           MPN (h1=3)    1      18.03   21.32   23.35   24.50
           MPN (h1=3)  degree   13.84   18.74   27.49   34.21
           --------------------------------------------------
           ANP (h1=3)    1      18.53   23.70   26.70   28.26
           ANP (h1=3)  degree   14.52   20.26   28.79   35.50
           --------------------------------------------------
           MPN (h1=2)    1      22.96   35.01   48.31   57.96
           MPN (h1=2)  degree   15.25   24.03   37.55   48.67
           ---------------------------------------------------
           ANP (h1=2)    1      30.41   62.69  128.73  194.71
           ANP (h1=2)  degree   23.67   49.58  108.15  167.94
        ---------------------------------------------------

                Table 1.  Average CDS size for radius 0.3

                                      Number of Nodes
           --------------------------------------------------
           Algorithm   RtrPri    50     100     200     300
           --------------------------------------------------
           Essential     1      1.108   1.167   1.188   1.191
           Essential   degree   1.046   1.071   1.070   1.072
           --------------------------------------------------
           MPN (h1=3)    1      1.087   1.137   1.158   1.165
           MPN (h1=3)  degree   1.044   1.067   1.068   1.071
           --------------------------------------------------
           ANP (h1=3)    1      1.062   1.098   1.119   1.126
           ANP (h1=3)  degree   1.034   1.032   1.036   1.060
           --------------------------------------------------
           MPN (h1=2)    1      1.034   1.044   1.053   1.054
           MPN (h1=2)  degree   1.027   1.032   1.036   1.037
           ---------------------------------------------------
           ANP (h1=2)    1      1.000   1.000   1.000   1.000
           ANP (h1=2)  degree   1.000   1.000   1.000   1.000
           ---------------------------------------------------

             Table 2.  Average stretch factor for radius 0.3

Ogier                    Expires August 3, 2005                [Page 27]

Internet-Draft           MANET Extension of OSPF           February 2005

                                      Number of Nodes
           --------------------------------------------------
           Algorithm   RtrPri    50     100     200     300
           --------------------------------------------------
           Essential     1       7.02    7.59    8.21    8.46
           Essential   degree    5.14    8.03   13.47   18.54
           --------------------------------------------------
           MPN (h1=3)    1       7.19    7.76    8.41    8.69
           MPN (h1=3)  degree    5.14    8.03   13.47   18.54
           --------------------------------------------------
           ANP (h1=3)    1       7.55    8.44    9.36    9.60
           ANP (h1=3)  degree    5.16    8.03   13.47   18.54
           --------------------------------------------------
           MPN (h1=2)    1      10.37   12.53   15.32   16.21
           MPN (h1=2)  degree    5.14    8.03   13.47   18.54
           ---------------------------------------------------
           ANP (h1=2)    1      19.32   36.03   64.37   91.56
           ANP (h1=2)  degree   11.77   22.80   43.81   64.95
           ---------------------------------------------------

                Table 3.  Average CDS size for radius 0.5

                                      Number of Nodes
           --------------------------------------------------
           Algorithm   RtrPri    50     100     200     300
           --------------------------------------------------
           Essential     1      1.088   1.091   1.093   1.091
           Essential   degree   1.017   1.016   1.013   1.012
           --------------------------------------------------
           MPN (h1=3)    1      1.079   1.083   1.083   1.081
           MPN (h1=3)  degree   1.017   1.016   1.013   1.012
           --------------------------------------------------
           ANP (h1=3)    1      1.061   1.065   1.063   1.063
           ANP (h1=3)  degree   1.016   1.016   1.013   1.012
           --------------------------------------------------
           MPN (h1=2)    1      1.033   1.034   1.035   1.036
           MPN (h1=2)  degree   1.017   1.016   1.013   1.012
           ---------------------------------------------------
           ANP (h1=2)    1      1.000   1.000   1.000   1.000
           ANP (h1=2)  degree   1.000   1.000   1.000   1.000
           ---------------------------------------------------

             Table 4.  Average stretch factor for radius 0.5

Ogier                    Expires August 3, 2005                [Page 28]

Internet-Draft           MANET Extension of OSPF           February 2005

12. Major Changes

   Changes from version 02 to version 03:

   - A flexible Hello protocol is presented that allows routers to
     send either full or differential Hellos, in which either full or
     partial 2-hop neighbor information is advertised periodically.
     Partial information consists of (Backup) Dependent Neighbors.

   - The ANP CDS algorithm has been modified to allow the possibility
     that a router can be a DR of one neighbor and a Backup DR of
     another neighbor. To allow this, the algorithm now distinguishes
     between Dependent Neighbors and Backup Dependent Neighbors.

   - The flooding procedure (Section 6) has also been modified to
     distinguish between Dependent and Backup Dependent Neighbors.

   - The ANP CDS algorithm has been modified to allow a (Backup) DR
     to declare all of its neighbors to be (Backup) Dependent,
     thus making all neighbors adjacent (which is always the case
     in the other CDS algorithms).

   - The rule for forming adjacencies has been modified so that an
     adjacency is formed between two routers if and only if one of
     the routers is a (Backup) Dependent Neighbor of the other one.
     Since Hellos advertise (Backup) Dependent Neighbors, each router
     knows which neighbors it should become adjacent with.

References

   [Adjih02] C. Adjih, P. Jacquet, and L. Viennot. "Computing connected
        dominated sets with multipoint relays", INRIA research report
        No. 4597, October 2002.

   [Chandra04] M.W. Chandra, Editor. "Extensions to OSPF to Support
        Mobile Ad Hoc Networking", Internet-Draft (work in progress),
        draft-chandra-ospf-manet-ext-02.txt, October 2004.

   [Lin03] T. Lin, S.F. Midkiff, and J.S. Park. "A Framework for
        Wireless Ad Hoc Routing Protocols", IEEE WCNC, March 2003.

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

   [RFC3626] T. Clausen, P. Jacquet (ed). "Optimized Link State Routing

Ogier                    Expires August 3, 2005                [Page 29]

Internet-Draft           MANET Extension of OSPF           February 2005

        Protocol (OLSR)", RFC 3626, October 2003.

   [RFC3684] R. Ogier, F. Templin, and M. Lewis. "Topology Dissemination
        Based on Reverse Path Forwarding", RFC 3684, February 2004.

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

Author’s Address

   Richard G. Ogier
   EMail: [email-masked]

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 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 Internet Society (2005). 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.

Ogier                    Expires August 3, 2005                [Page 30]
_______________________________________________
Ospf-wireless-design mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design

---

From: Acee Lindem <[email-masked]>
Date: Fri, 04 Feb 2005 00:26:57 -0500

Hi Richard,
Could you add some details on the actual protocol encoding
changes you envision (either inline or in an appendix). It doesn't
have to be WG last call quality just precise enough so someone
could code it for a simulation. You can LLS or backward compatible
mechanisms.

Thanks,
Acee

Richard Ogier wrote:

>------------------------------------------------------------------------
>
>
>
>
>------------------------------------------------------------------------
>

---

From: Richard Ogier <[email-masked]>
Date: Fri, 04 Feb 2005 11:08:07 -0800

Hi Acee,

I can provide more details, but probably not before
the meeting deadline.  I know that Tom Henderson and
his group are implementing some of the algorithms in
my draft in GTNetS, to compare them with the overlapping
relay solution.  The description in my draft should be
enough for them to implement it, although they will have
to fill in some details.  If their simulation results
show that my solution is promising, then I can work
further on the draft, to provide more details, etc.
However, I hope this would be a team effort, i.e.,
that other team members (such as Boeing) would
help write a complete specification of whatever
solution we decide on.

Richard