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

[Acee Lindem <[e-mail]>]

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:

> 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: [e-mail]
>
>
>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
>[e-mail]
>https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
>  
>

_______________________________________________
Ospf-wireless-design mailing list
[e-mail]
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design