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

From: "Henderson, Thomas R" <[email-masked]>
Date: Fri, 29 Oct 2004 13:37:34 -0700

Does anyone have a conflict meeting on Tuesday PM?  I have
conflicts on Tuesday AM.

The routing related agenda on Tuesday PM seems to be:
IP over Cable Data Network WG
Routing Protocol Security Requirements WG
(OPS) Global Routing Operations WG
Protocol Independent Multicast WG

For those who will be at the IETF meeting, please chime in if 
you would like to schedule around any of the above.  

Tom

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

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Fri, 29 Oct 2004 18:51:33 -0700

Catching up on a few of these mails...

> -----Original Message-----
> From: Thomas Heide Clausen [mailto:[email-masked]] 
> Sent: Friday, October 22, 2004 4:18 PM
> To: Henderson, Thomas R
> Cc: Acee Lindem; [email-masked]
> Subject: RE: [Ospf-wireless-design] new material to review and discuss
> 
>> 
> Just one brief comment here: I disagree with the terminology 
> chosen. MPRs do
> form a CDS -- indeed the MPR algorithm is an instance of a 
> CDS algorithm. As
> such, it doesn't make much sense to chose between them. I'd 
> suggest that we,
> rather than "chose between them" consider which features we 
> need -- and then
> pick an algorithm that fits (notice, I did write "pick", not 
> "develop" -- for a
> reason).
> 

If we pick from what is available, what is the pool from which
we are picking?

I think that one criteria is that we look for algorithms that
operate in a distributed fashion (i.e., don't require a global
knowledge of all nodes to pick the relay node set).

In the source-dependent CDS realm, that includes MPRs (and 
Cisco adaptation of that) and TBRPF-like approaches (others?)

In the source-independent CDS realm, I'm aware of the following
distributed approaches:

- the approach by Wu and Li, improved upon by Lin

- the approach described by Adjih (INRIA), which transforms a
set of MPRs into a set of SI-CDS

-  the virtual dynamic backbone algorithm (Kozat et al.)

Are there others?  

Tom

---

From: "Henderson, Thomas R" <[email-masked]>
Date: Fri, 29 Oct 2004 19:03:03 -0700

see responses inline

> From: Richard [mailto:[email-masked]] 
> Sent: Wednesday, October 27, 2004 12:01 AM
> To: Henderson, Thomas R
> Cc: [email-masked]
> Subject: Re: [Ospf-wireless-design] new material to review and discuss
> 
> 
> 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.)  
> 

agreed, these are possible variations.

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

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

OK.

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

OK, thanks.  When I take a next cut at that section, I will fold in
those comments.

Tom