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

From: "Madhavi W. Chandra" <[email-masked]>
Date: Thu, 4 Nov 2004 12:06:14 -0500

Hi All,

Catching up on emails...

<snip>

> > > 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).
> 
> agreed. 
> > 
> > >
> > >
> > >    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.
> 
> agreed.  thanks for pointing that out.
> 
> 
> > >
> > >    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.
> 
> I agree that CDS is consistent with OSPF-- the question is whether the 
> possibility for evolving the heuristics in an incremental fashion is
> worth anything.
> 
> >
> > >    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.
> 
> Yes, but the node doing the selection relies on two hop info,
> right?  That is the main point, I think.  But then there is the
> extra step of notifying.  I think you are pointing out that the
> CDS algorithm relies on two hop info, but there is no "next step"
> of notifying a node as in MPRs.

I'll throw out there...

When we started our design of overlapping relays, we started with
a self-elected set that did not 'notify' its peers of its self-election.
Our thinking at the time was that a node is in the best position to
know who it can reach at the time of flooding....and thus, whether 
it should further a flood.  It was a local decision and not conveyed
to other nodes.

However, we realized that the performance of such 
undeterministic behavior is very dependent on the network behaving
'ideally'.  Convergence can be delayed, excessive transmissons can
result, and more importantly, flooding can be compromised.

Going down that road led us to our current overlapping relays
mechanism...in which nodes select their overlapping relays, and
convey such elections to the peers.

Since the DT is meeting in IETF, maybe this can be discussed further
then.

-Madhavi

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

---

From: Joe Macker <[email-masked]>
Date: Thu, 04 Nov 2004 14:30:57 -0500

>>>is consistent with OSPF's philosophy.
 
Are you assuming by the above, the link state is limited to or only initiated by the relay set nodes?

Unless I am misinterpreting the context, the CDS selection specifics (whether source specific or not) and the routing algorithm can be orthogonal.

It is true that sometimes they are tied together as in "partial link state variant of OLSR" in an attempt to reduce control overhead.
In other methods, already prototyped and tested, LS updates are produced by all nodes and the CDS-based forwarding is used for efficient flooding only. In this case, the routing can route around the CDS as needed.

We could argue about the scalability vs. robustness tradeoffs but both approaches are possible.