Subject: RE: FW: [Ospf-wireless-design] Tao Lin paper

From: "Spagnolo, Phillip A" <[email-masked]>
Date: Tue, 25 Jan 2005 14:43:39 -0800

Richard,

In your draft,
<http://www.ietf.org/internet-drafts/draft-ogier-manet-ospf-extension-02
.txt>, Section 4.1 states the following rules for an essential SI-CDS.  

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.

These rules are same as the rules in your message bellow.  Except, you
add the quoted statement:  ... using only intermediate nodes "that are
neighbors of node i and" that have a larger value of (RtrPri, RID) than
node i ...

This change seems to increase the size of the CDS somewhat
substantially.  In the example in your message below, nodes 1, 2, 3, 4,
6, and 7 would be DRs versus 6 and 7 before.  I am using edges = RtrPri.

2nd Example edges=RtrPri.
With the draft algorithm, all nodes are DRs.
With the algorithm below, nodes (4, 5, 9, 1, 8, 10) are DRs.

7-- 4-- 11
|   |   |
5-- 9-- 3
 \  |  /
    1
  / | \
 2  6  8
  \ | /
   10

Why did you choose to add the "intermediate node must be a neighbor of
i"?  Does this statement affect the order in which the algorithm runs?  
  
Thanks,
Phil

> -----Original Message-----
> From: Richard Ogier [mailto:[email-masked]] 
> Sent: Thursday, December 23, 2004 8:02 AM
> To: Abhay Roy
> Cc: [email-masked]
> Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper
> 
> 
> Hi Roy,
> 
> Here is an example where MPRs result in 3 times
> as many transmissions as a SI-CDS.
> 
>     5
>  /  |  \
> 1-- 6-- 3
> |   |   |
> 2-- 7-- 4
>  \  | /
>     8
> 
> Node 5 is the source.
> The MPRs that forward LSAs from node 5 are {1, 6, 3, 2, 7, 4}.
> The SI-CDS is {6, 7}, obtained using the algorithm below
> which runs in O(d^2) time using a modified BFS algorithm,
> where d is the number of neighbors.
> 
> The drawback of MPRs in this case is that they are required to provide
> min-hop paths, whereas a SI-CDS does not have this requirement.
> Of course, this is a special example, and simulations will tell us
> what happens on average.
> 
> But even if the SI-CDS were the same size as the MPR set,
> I would favor the SI-CDS because of several other advantages,
> such as faster convergence. I plan to submit a draft next week that
> presents a family of CDS algorithms, including the one below,
> along with some simulation results.
> 
> Minimal CDS Algorithm
> 
> 1. If node i has a larger value of (RtrPri, RID) than any of its
> neighbors, then node i selects itself as a DR.
> 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 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.
> 
> Happy Holidays!
> Richard
> 
> 
> Abhay Roy wrote:
> 
> > Hi Tao,
> >
> > It's good to hear from you first hand on this topic. What may be 
> > useful to further this discussion is an example or two, 
> where we can 
> > demostrate that the improved algorithm comes up with a 
> smaller set. In 
> > my mind, it's still very fuzzy how this happens ;)
> >
> > Also, since we are going to be doing simulations under Tom's GTNetS 
> > tool, we will need to include Tao's algorithm in there.
> >
> > Regards,
> > -Roy-
> >
> > On 12/21/04-0500 at 1:05pm, Tao Lin writes:
> >
> >> Hi Madhavi,
> >>
> >> Just one comment on the paragraph in your email (see
> >> below).
> >>
> >> If a CDS algorithms only requires that all nodes are
> >> broadcasting their neighbor lists to their neighbors,
> >> we can 99.99% sure that all nodes work 'ideally'.
> >> This is because the information it requires is the
> >> minimized information set (which is also included in
> >> the information required for source dependent CDS
> >> algorithms).  If this cannot be guaranteed, those
> >> source dependent algorithms will also fail.
> >> Furthermore, even if somehow a hello message is lost,
> >> neighboring nodes can recover from that lost at the
> >> next hello time.
> >>
> >> Therefore, the source-independent algorithm using only
> >> 2-hop neighbor information can work at least as
> >> 'independently' as other source-dependent algorithms.
> >>
> >> Have a great day!
> >>
> >>   Tao
> >>
> >> --- "Madhavi W. Chandra" <[email-masked]> wrote:
> >>
> >>> On another note, is it fair to say that a
> >>> source-independent CDS
> >>> algorithm is actually more *dependent* on all of the
> >>> nodes behaving
> >>> 'ideally'...running the same selection algorithm,
> >>> agreeing on their
> >>> IDs, etc....whereas a source-dependent overlapping
> >>> relays/MPR
> >>> algorithm is more flexible?
> >>>
> >>> Regards,
> >>> Madhavi
> >>>
> >>
> >>
> >>
> >> 
> ______________________________________________________________________
> >> Post your free ad now! http://personals.yahoo.ca
> >>
> >> _______________________________________________
> >> Ospf-wireless-design mailing list
> >> [email-masked]
> >> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> >>
> >
> > _______________________________________________
> > Ospf-wireless-design mailing list
> > [email-masked]
> > https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> >
> 
> 
> 
> _______________________________________________
> Ospf-wireless-design mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> 

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

---

From: Richard Ogier <[email-masked]>
Date: Tue, 25 Jan 2005 15:19:16 -0800

Hi Phil,

The answer is given in the following paragraph from page 8 of my draft:

    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.

It is true that this affects the CDS size substantially in the special
example that I gave, but simulations show that it only affects the CDS
size slightly on average. Another reason to require the intermediate
nodes to be neighbors is that this allows a Backup DR to know whether a
DR neighbor transmitted a given LSA. In general, it improves robustness.

The other way can still be considered, and compared in simulations.
But based on my simulations and the robustness arguments above, my
guess is that it is better to require intermediate nodes to be
2-hop neighbors.

Richard

---

From: Richard Ogier <[email-masked]>
Date: Tue, 25 Jan 2005 15:22:59 -0800

Correction to my last paragraph:

The other way can still be considered, and compared in simulations.
But based on my simulations and the robustness arguments above, my
guess is that it is better to require intermediate nodes to be neighbors.

Richard

Richard Ogier wrote:

>>> From: Richard Ogier [mailto:[email-masked]] Sent: 
>>> Thursday, December 23, 2004 8:02 AM
>>> To: Abhay Roy