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

From: Tao Lin <[email-masked]>
Date: Tue, 4 Jan 2005 14:16:51 -0500 (EST)

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 <[email-masked]> 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" <[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

______________________________________________________________________ 
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

---

From: Abhay Roy <[email-masked]>
Date: Wed, 5 Jan 2005 10:06:25 -0800 (PST)

Richard,

Thanks for the example. One of the confusions I have had is when
we call it SI-CDS. It's still source dependent, it's just that
nodes are doing computation from every one of it's neighbor's
perspective.

Are there really any source independent CDS algo's? In my mind
that will be something where a node elects itself as an Active
relay irrespective of where the source of flood comes from. The
algo you describe below does seem to fall in that category. If
yes, we should perhaps use different terminology (SD-CDS /
SI-CDS?) to distinguish them.

One other thing which we have not discussed much is, how to adapt
these CDS algo's to work with reliable flooding. Note that we have
agreed to focus only on reliable flooding right now. The proposal
we made has a notion of non-active relay. In short, if you are not
active, you assume to be non-active and using PushbackInterval's
try to suppress flooding if someone else is already doing it.

We can use the same notion with CDS algo's and assume that the
rest of the nodes are non-active, but do become active if needed.

Some questions inline..

On 12/23/04-0800 at 8:02am, Richard Ogier writes:

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

Agree. I am curious to see how this works with various mobility
scenario's and reliable flooding constraints.

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

So far from what I have seen, the SI-CDS algo's need at least an
order of magnitude higher computational power. It might to useful
to quantify that for a reasonable size network. Also there are
other constraints (e.g. all nodes are assumed to be running same
algo) which may make it prohibitive in deployments.

> I plan to submit a draft next week that
> presents a family of CDS algorithms, including the one below,
> 1. If node i has a larger value of (RtrPri, RID) than any of its

Do you really mean DR here? We are working with an assumption that
the MANET interface is a p2mp interface, so no DR/BDR election.
Maybe you mean elects itself as "active"?

If I have 2 nodes with (100, 1.1.1.1) and (10, 2.2.2.2), which one
is larger? I guess I don't understand the need for RtrPri above.

Also this step seems arbitrary in electing a relay v/s say "If I
have a higher degree than any of my neighbors".

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

This almost sounds like we have to run a constrained SPF rooted at
j for each of neighbors of i.

Regards,
-Roy-

> 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
> > 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-
> >
> >> 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,
> >> This is because the information it requires is the
> >> minimized information set (which is also included in
> >> 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
> >> 'independently' as other source-dependent algorithms.
> >>
> >> Have a great day!
> >>
> >>   Tao
> >>
> >> --- "Madhavi W. Chandra" <[email-masked]> wrote:
> >>
> >>> 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

---

From: Richard Ogier <[email-masked]>
Date: Wed, 12 Jan 2005 09:38:15 -0800

Tao,

This morning, I looked at your CDS algorithm in

     T. Lin, S.F. Midkiff, and J.S. Park. "A Framework for
     Wireless Ad Hoc Routing Protocols", IEEE WCNC, March 2003.

and also looked at the
Updated Local Ripple Algorithm for Minimal CDS (ULRCDS)
in your Dissertation.  I compared Figure 3 in the above paper
to Figure 4.5 in your Dissertation, and conclude that the CDS
algorithm in the above paper is the same as ULRCDS.
(Correct me if I am wrong.)
This implies that the following sentence in your paper actually
means you are considering a *single* sender node:

  "When a node i has a neighboring node that is
   not covered by the sender node k, node i checks whether there
   is a common neighbor between i and j, say node x, that covers
   that neighbor."

Therefore, the algorithm you compared in simulations is actually
source-dependent. (I realize that in your dissertation it is not
really source dependent because you assume that certain nodes
initiate a control message that is propagated multiple hops,
but your paper does not mention such a control message.)

I, and also Tom Henderson (I think), have been interpreting your CDS
algorithm to be source-independent, and have been assuming that you
consider *all* neighbors as a possible sending node.
As a result, my new draft incorrectly states that my algorithm
ANP with h1 = 2 and RtrPri equal to node degree is equivalent
to your algorithm. (I will correct this in the next update.)
Also, the simulation results presented in Tom Henderson's
draft might not reflect the source-dependent
flooding that you used in your paper.

Tao and Tom, Plese correct me if I am wrong.

Regards,
Richard

---

From: Tao Lin <[email-masked]>
Date: Wed, 12 Jan 2005 15:29:00 -0500 (EST)

Hi Richard,

You are correct, these two algorithms are the same and
it IS a SD-CDS algorithm.  The final CDS algorithm
used in my dissertation is also a SD-CDS algorithm
except that there is no additional control messages
needed between neighbors.

Thank you for pointing it out.

I have a comment on the CDS algorithm efficiency (the
average size of CDSs it can generate).   A good CDS
algorithm may generate very small size of sets of
nodes for a connected network.  However, in practical,
this may not be the only metric to measure these
algorithms.  For example, in a wireless network,
broadcast messages may lost due to packet collisions
or other reasons.  Therefore, smaller size of CDS may
not always be the best for flooding in wireless
networks.  In other words, smaller size of CDS may not
be robust enough to handle broadcast lost events in
poor wireless environments.  A certain level of
redundancy may be needed in that case.  One should
balance the efficiency of CDS algorithms and the
redundancy.  Just my 2 cents.

  Tao

> >>>>If a CDS algorithms only requires that all nodes
=== message truncated ===

---

From: Richard Ogier <[email-masked]>
Date: Wed, 12 Jan 2005 17:17:14 -0800

Hi Tao,

>redundancy.  Just my 2 cents.

Yes, I agree. This may be especially true for best effort flooding,
but it may also help for reliable flooding, since it may reduce the
delay and overhead due to retransmissions. The Backup DRs in my
draft provide redundancy, in that the set of DRs and Backup DRs
form a biconnected CDS. I think it is better to provide
guaranteed redundancy in this way, than to simply
choose an algorithm that happens to give a larger CDS (which
will not guarantee biconnectivity, for example).
On the other hand, in some situations it may be preferable to
use a (larger) CDS that provides min-hop paths, while in other
situations, it may be important to use a very small, scalable CDS.
That's why my draft presents a variety of interoperable CDS
algorithms, some of which are similar to ones you and others
have developed. The only requirement is that a router MUST
select itself as a DR (or BDR) if the Essential CDS algorithm
selects it as a DR (or BDR).  
To allow scalability, I don't think we should require more than
this. Depending on the situation, a larger CDS MAY be used.

OSPF already provides biconnected redundancy by requiring
both a DR and BDR, so we should certainly provide biconnected
redundancy for flooding in MANETs.

Richard

>>>All these CDS algorithms we are investigating here
>>>
>>are
>>
>>>approximation algorithms.  In other words, they
>>>
>>have
>>
>>>them, we are comparing their average performances
>>>
>>with
>>
>>>algorithm is always better than the other.  (I am
>>>
>>not
>>
>>>--- Richard Ogier <[email-masked]>
>>>
>>wrote: 
>>
>>>>Hi Roy,
>>>>
>>>>The MPRs that forward LSAs from node 5 are {1, 6,
>>>>
>>3,
>>
>>>>2, 7, 4}.
>>>>But even if the SI-CDS were the same size as the
>>>>
>>MPR
>>
>>>>set,
>>>>such as faster convergence. I plan to submit a
>>>>
>>draft
>>
>>>>next week that
>>>>hops, based on node i's 2-hop neighbor
>>>>
>>information)
>>
>>>>from node j to
>>>
>>>>that have a larger value of (RtrPri, RID) than
>>>>
>>node
>>
>>>>i,
>>>>>useful to further this discussion is an example
>>>>>
>>or
>>
>>>>two, where we can 
>>>>
>>>>>my mind, it's still very fuzzy how this happens
>>>>>
>>;)
>>