Subject: [Ospf-wireless-design] new material to review and discuss

From: "Henderson, Thomas R" <[email-masked]>
Date: Wed, 13 Oct 2004 08:41:15 -0700

All,
I have attached a revised version of the wireless design team
document.  I am trying to use this to document agreements and
discussion points raised in the drafts and the mailing lists.

In particular, I have added a section 1.2 that lists the items
that the group agrees upon.  Can people please review this
section and see whether there is any objection to removing
the "pending" status to any of these topics? (I will interpret
silence on the list as acquiescence).

If we can move past those items, the next topic I would like
to focus on is the flooding discussion-- in particular, the
issue of MPR vs. CDS that has never been resolved adequately
in my opinion.  Please read Section 3.2 carefully, as it has
been substantially rewritten, and let the list know of your
agreements and disagreements to what is written there.

Thanks,
Tom
_______________________________________________
Ospf-wireless-design mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design

---

From: "Acee Lindem" <[email-masked]>
Date: Fri, 22 Oct 2004 12:20:43 -0400

Tom, 

Can we schedule a OSPF wireless design update for the Washington 
IETF? What I think would be good would be a presentation on the
attached document with ample time for WG questions. 

Did anybody else have anything relevant to the OSPF wireless effort that
they wanted to present in Washington? I've had a lot going on lately
and realized today that time is running short. 

Thanks,
Acee

----- Original Message ----- 
From: "Henderson, Thomas R" <[email-masked]>
To: <[email-masked]>
Sent: Wednesday, October 13, 2004 11:41 AM
Subject: [Ospf-wireless-design] new material to review and discuss

All,

Thanks,
Tom

--------------------------------------------------------------------------------

---

From: Richard <[email-masked]>
Date: Wed, 27 Oct 2004 00:00:45 -0700

Thomas,

Please see my comments below for Section 3.2 of your document
draft-manet-ospf-design-team-00-pre2
Overall, it is very good.

First I want to comment on your sentence:

>    MPRs are also sometimes referred to as source-dependent CDS, while
>    the use of the term CDS typically means source-independent CDS.

I'm glad you clarified this. So the main issue is whether we want
the relays to be source-dependent or source-independent. Actually,
there are different ways of defining a CDS in terms of MPRs,
depending on the forwarding rule. (E.g., does an MPR forward any
packet that was received from an MPR selector, or only if the
first neighbor that transmitted the packet is an MPR selector,
or only if the min ID neighbor that transmitted the packet is
an MPR selector, etc.)  

> 3.2.1.2  Self-selected MPRs
>
>    Regarding whether MPRs are self-selected versus selected by the
>    originators themselves, the tradeoff seems to be some increase in
>    complexity (i.e., processing steps) to self-select them, versus a
>    need to use extra fields in Hello or other messages to notify a
>    neighbor that it has been selected.  However, it may require that
>    OSPF Hellos be modified to provide two-hop information anyway.  For
>    example, consider if each node provided its two-hop neighbor
>    information to all of its one hop neighbors.  Rather than the node
>    running the MPR selection algorithm and notifying the selected one
>    hop neighbor, each neighbor could run the algorithm on the node's
>    behalf, and decide whether it would have been selected by the node.
>    But the current OSPF Hello only provides one-hop neighbor information
>    for the sending node.

Actually, the OSPF Hello does not even provide one-hop neighbor
information, since it does not say whether each neighbor is 2-way.
As in Cisco's protocol and in TBRPF, each node can inform its neighbors
of all of its 2-way neighbors in its self-originated LSA.
In that way, each node learns about all of its neighbors' neighbors
(2-hop neighbors).
It would be unnecessarily bandwidth consuming for each node to
report all of its 2-hop neighbors (which would result in each node
knowing its 3-hop neighbors).

>
>
>    A minimum-ID algorithm described in [9] requires O(m^4) computation
>    when run as a self-selecting algorithm rather than O(m^2) or O(m)
>    using the MPR selector approach.  However, it has also been pointed

A min-ID self-selecting algorithm exists which requires only
O(n^3) using the Floyd-Warshall algorithm to compute shortest paths
from each neighbor to each other neighbor, where n is the number
of neighbors. I don't think this is too large.  Another such algorithm
requires only O(n^2) computations by computing shortest paths from each
neighbor to only the min-ID neighbor.

>
>    out by Ogier that, analogous to including the selected DR in Hello
>    messages, it may be useful to announce whether a node has selected
>    itself as an MPR for one of its neighbors, to reduce the frequency of
>    MPR changes.
>
> 3.2.1.3  Cisco Overlapping Relays
>
>    As described in [4], the proposed "overlapping relays" algorithm is
>    based on the OLSR MPR algorithm, with the following optimization.
>    Neighbors that are selected as what OLSR would call MPRs are called
>    "active" overlapping relays, and all other neighbors are "non-active"
>    overlapping relays, with respect to a given two-hop neighbor of the
>
>
>
> Henderson (ed.)          Expires April 13, 2005                 [Page 9]
> 
> Internet-Draft      Summary of MANET OSPF Proposals         October 2004
>
>
>    message originator.  The active relays behave like OLSR MPRs, but the
>    non-active relays of message originator monitor whether the two-hop
>    neighbor in fact acknowledged the transmission.  If no ack is
>    received, then one of the non-active relays will attempt to
>    retransmit the message, based on some time interval and jitter to
>    avoid all non-active relays from attempting to recover the loss at
>    the same time.
>
>    Other than this reliability optimization, it seems that the proposed
>    Cisco approach inherits the properties described above regarding
>    OLSR-style MPRs.  As presently defined, it also incurs a delay in
>    notifying a neighbor that it has become active (the so-called
>    "opt-in" method above), but this is mitigated by the protection
>    offered by non-active neighbors, so all that might happen is a slight
>    increase in flooding delay.
>
> 3.2.1.4  CDS algorithms
>
>    At the end of Section 6 of [5], Richard Ogier argues that CDS may be
>    preferable to MPR for OSPF, since it more naturally fits with the
>    concept of OSPF DR with fewer changes needed to OSPF packets, and
>    because it offers opportunities to optimize database synchronization
>    techniques.
>
>    Specifically, some researchers (e.g., [10]) have shown simulation
>    results that show smaller size relay node sets when using CDS,
>    although in the author's opinion, this evidence may be
>    scenario-dependent and does not strongly favor one or the other.  It
>    has been argued that CDS algorithms are potentially simpler as well,
>    since the decision to forward is not based on the originator of the
>    previous transmission.  CDS may not forward along min-hop paths from
>    the message originator, although the difference in path length is
>    probably only one hop, if at all, and methods may exist to allow
>    min-hop flooding (e.g., [10]).
>
>    If a node is self-selecting itself as a CDS, it most likely does so
>    with an assumption that neighbors are running the identical or
>    similar algorithm (in much the same way that the distributed
>    computation of Dijkstra's algorithm requires that all nodes
>    consistently apply it).  In a MANET environment, some nodes may not
>    be as willing to select themselves as CDS, due to issues such as
>    energy reserve.  Richard Ogier suggested in [5] that the Router
>    Priority field may be used to indicate "willingness" to relay traffic
>    and become a CDS node, but there is no specific description of how
>    this might work.  Likewise, it is not clear how sensitive a CDS
>    self-selection algorithm would be to neighbors using consistent
>    algorithms, and hence, how easy it would be to evolve the heuristics
>    in an incremental deployment scenario.

OSPF requires all nodes to run the same shortest-path algorithm,
so requiring all nodes to run the same CDS algorithm
is consistent with OSPF's philosophy.

>
>
>
>
> Henderson (ed.)          Expires April 13, 2005                [Page 10]
> 
> Internet-Draft      Summary of MANET OSPF Proposals         October 2004
>
>
>    Related to the issue of knowing the ROS is the issue of optimized
>    database synchronization.  Another benefit of CDS or MPRs that know
>    their ROS is that these "special nodes" can take responsibility for
>    synchronization, much as an existing OSPF DR, rather than requiring
>    pair-wise synchronization between nodes.
>
>    Although there are several heuristics for CDS construction that have
>    been proposed, one interesting one presented by INRIA (in [9]) can be
>    used to transform the set of MPRs into a CDS, if the nodes have some
>    agreed-upon knowledge of the total-order of the network (such as
>    increasing router ID).  Ogier has done some simulation evaluation of
>    this algorithm in [10] and shown simulation results that it performs
>    worse than an algorithm based on two-hop neighbor information.

I also want to point out that MPR selection involves *more* than
2-hop neighbor information, since each node computes its MPRs
based on 2-hop neighbor information and then informs its
neighbors of its MPR selection (so the selection of an MPR
may depend on information about nodes that are 3 hops from
the MPR itself).  The CDS algorithms that I am considering
depend only on 2-hop neighbor information.
Also, having to first compute MPRs and then inform neighbors of the
selection results in slower response to topology changes.

>
>
> 3.2.1.5  Summary
>
>    In the past, there has been simulation evidence presented that
>    favored MPRs over CDS, and vice versa, in terms of bandwidth
>    efficiency.  In the absence of better data, it is the author's
>    opinion that, from the standpoint of bandwidth efficiency, MPRs
>    versus CDS will not make a whole lot of difference, especially when
>    metrics like robustness are considered that might favor some
>    redundancy in transmissions anyway.  Both techniques seek to minimize
>    as much as possible the number of transmissions required to
>    disseminate the information, and different scenarios will yield
>    different winners, but in most cases, the differences seem to be a
>    few percent.  Instead, the design decision should probably be driven
>    by which mechanism fits best (is least disruptive) to the existing
>    OSPF implementation.
>
>    There have been arguments put forward, principally by Richard Ogier,
>    that CDS-based flooding is a better fit for OSPF than is MPR-based,
>    because CDS selection algorithms do not necessarily require changes
>    to OSPF message formats, because CDS is analogous to Designated
>    Router, because they may have simpler construction algorithms (for
>    this point, the author has not seen any proof), and because the fact
>    that a CDS does not care about the originator of a message, which may
>    help if the database synchronization procedures are ever optimized
>    for a MANET.  Therefore, in the author's opinion, despite not having
>    a concrete CDS-based proposal on the table, the OSPF MANET design
>    team should consider this issue more carefully.
>
> 3.2.2  Discussion of reliability
>
>    It seems to the author that the decision to focus on reliable
>    mechanisms first is non-contentious.  The author has suggested
>    partiality to mechanisms that allow the introduction of a periodic,
>    non-acked LSA dissemination mode in the future.
>
>
>
> Henderson (ed.)          Expires April 13, 2005                [Page 11]
> 
> Internet-Draft      Summary of MANET OSPF Proposals         October 2004
>
>
>    Richard Ogier has proposed that unreliable (periodic) operation may
>    be a hybrid option of an overall reliable mechanism.  A Boeing
>    simulation study described in [7] suggested that it may be difficult
>    to correctly estimate the need to be in one mode or another.  Since
>    that time, Richard Ogier has revised his proposal in this regard, as
>    discussed in Section 5 of [5].  Richard's current proposal is not
>    based on receiver suppression of ACKs but instead is sender-based and
>    suggests setting a new option bit in the header to make the LSA
>    "non-ackable" within the wireless domain whenever new LSAs are being
>    generated fast enough (i.e., close to MinLSInterval), with hysteresis
>    applied to avoid flapping between modes.
>
>    Baker suggested the use of next-hop reflooding as an implicit ACK in
>    [1], although Ogier pointed out that this only applied to nodes in
>    the relay set; non-relay nodes still have to ACK.
>
>    In Section 6 of [5], Richard Ogier suggests a reliable flooding
>    technique based on modification of Database Description (DD) packets.
>    It calls for special nodes (either CDS nodes or MPR nodes) to
>    periodically broadcast headers of all the LSAs for which it is

It should be clarified that these LSAs headers are contained within
DD packets that are broadcast to all neighbors periodically (similar
to the sequence numbers packets of IS-IS).

>
>    responsible for forwarding, and for all other nodes to broadcast a DD
>    packet with the header of its own router LSA.  This is in contrast to
>    unreliable flooding of the LSAs themselves.  Nodes that detect a
>    missing LSA can still use the LSR to request it, after some backoff
>    time.  This is analogous to IS-IS Complete Sequence Number (CSN)
>    packets [11].  The technique is in contrast to the OLSR-like approach
>    in the Boeing proposal, which periodically refloods all LSAs.
>    Variations of this approach are possible and discussed by Richard
>    Ogier, such as repeating the original LSA transmission multiple
>    times, or CDS redundancy.  INRIA also proposed such a mechanism of
>    periodic informational database signature broadcasts in [6].
>
>    Last, it should be pointed out (as Richard has) that the selection of
>    RNS sets is not completely independent of the decision whether LSA
>    dissemination is reliable or periodic.  A purely OLSR-style MPR RNS
>    is susceptible to some lost packets when used in a reliable mode,
>    unless non-relay nodes are used as backups, as is proposed for the
>    Cisco overlapping relays technique.
>
> 3.3  Neighbor discovery and synchronization
>
>    This section discusses the process of neighbor discovery, adjacency
>    forming, and database synchronization.
>
>    In a MANET, the number of neighbors can become large, causing
>    quadratic scaling problems.  Fred Baker suggests in [1] that the
>    number of adjacencies might be reduced.  More recently, the proposal
>    by Cisco advocates the use of differential or incremental Hellos
>
>
>
> Henderson (ed.)          Expires April 13, 2005                [Page 12]
> 
> Internet-Draft      Summary of MANET OSPF Proposals         October 2004
>
>
>    (also suggested by the MANET TBRPF protocol).  Some simulations
>    conducted by Boeing and discussed in [7] suggest that differential
>    Hellos contribute second-order savings in bandwidth, but the benefits
>    might actually be larger than those described by Boeing when the
>    network is very dense.  One potential benefit of differential Hellos
>    is that the Hello transmissions can be aperiodic.
>
>    For the same reason that differential Hellos might be useful, so too
>    might a reduction in the number of neighbors with which a MANET node
>    becomes adjacent.  OSPF does this already for broadcast interfaces.
>    Fred Baker in [1] suggested that nodes might want to limit the number
>    of neighbors.  Richard Ogier in [5] also suggested that if there are
>    special nodes such as Multipoint Relays (MPRs) and Connected
>    Dominating Sets (CDS) in the network, that non-relay nodes might want
>    to synchronize only with these relay nodes (Ogier redefined the
>    concept of adjacency in this context).  When using unreliable
>    flooding as in [3], no database synchronization occurs; nodes do not
>    progress past state 2-Way on a MANET interface.

It would be good to point out what happens if the periodic DD packet
method is used for reliable flooding. In this case (similar to IS-IS),
a new neighbor of a CDS node (or MPR) will receive the periodic
DD packets and send a LS Request if the CDS node has a more
recent LSA.  This is similar to Clausen's proposal (both
are inspired by IS-IS) but is simpler and closer to OSPF.

Regards,
Richard

>
>
>    Taking the synchronization process a step further, Thomas Clausen and
>    INRIA suggested in [6] that a much more compact representation of
>    OSPF databases than an enumeration of LSA headers might be possible
>    using signatures (hashes) of parts of the OSPF database.  For
>    example, nodes could compare top-level signatures of their database,
>    and only if they differed would additional signatures start to be
>    compared, until the discrepancy was narrowed down.  The draft
>    describes an algorithm called Tunstall Splitting to generate prefix
>    signatures of different parts of the database, which can be further
>    segregated by age of the LSAs.

---

From: Joe Macker <[email-masked]>
Date: Fri, 22 Oct 2004 13:41:11 -0400

> agreements and disagreements to what is written there.

Tom:

Sorry I'm jumping ahead here, but in preparation for discussion of MPR 
vs.CDS, I'd like to clarify a few issues, especially the terminology.

MPR is a heuristic algorithm that forms a "source specific" CDS.  So it 
is a CDS algorithm. So are we talking about "other" CDS algorithms like 
Wu and Li have proposed,etc. I just want to get the terminology straight 
so I know what we are talking about.  For example, are we talking about 
a shared tree CDS algorithms, different election heuristics for 
forwarding sets, dynamic robustness issues, complexity tradeoffs...

There are existing empirical and analytical studies that we can look at 
and discuss.

-joe