Re: FW: [Ospf-wireless-design] Tao Lin paper

[Tao Lin <[e-mail]>]

Hi Roy,

All these CDS algorithms we are investigating here are
approximation algorithms.  In other words, they have
their best cases and worst cases.  When we compare
them, we are comparing their average performances with
simulations.  Therefore, you might write a simple
program to find out examples that one algorithm
generates smaller CDSs than the other easily. 
Otherwise, we should be able to prove that one
algorithm is always better than the other.  (I am not
convenient to write codes right now.)  

ps. I was unable to check emails so I didn't reply
promptly.  Sorry about that.

  Tao

 --- Richard Ogier <[e-mail]> wrote: 
> 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" <[e-mail]>
> 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
> >> [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
> >
> 
> 
>  

______________________________________________________________________ 
Post your free ad now! http://personals.yahoo.ca

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