From mailman-bounces@ietf.org  Sat Jan  1 05:14:08 2005
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id FAA05234
	for <ospf-wireless-design-archive@ietf.org>; Sat, 1 Jan 2005 05:14:08 -0500 (EST)
Received: from megatron.ietf.org ([132.151.6.71])
	by ietf-mx.ietf.org with esmtp (Exim 4.33)
	id 1CkgSe-0006Ls-O6
	for ospf-wireless-design-archive@ietf.org; Sat, 01 Jan 2005 05:26:17 -0500
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32)
	id 1Ckg41-0001V9-I4
	for ospf-wireless-design-archive@ietf.org; Sat, 01 Jan 2005 05:00:49 -0500
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-Transfer-Encoding: 7bit
Subject: lists.ietf.org mailing list memberships reminder
From: mailman-owner@ietf.org
To: ospf-wireless-design-archive@ietf.org
X-No-Archive: yes
Message-ID: <mailman.645.1104573616.4100.mailman@lists.ietf.org>
Date: Sat, 01 Jan 2005 05:00:16 -0500
Precedence: bulk
X-BeenThere: mailman@lists.ietf.org
X-Mailman-Version: 2.1.5
List-Id: Mailman site list <mailman.lists.ietf.org>
X-List-Administrivia: yes
Sender: mailman-bounces@ietf.org
Errors-To: mailman-bounces@ietf.org
X-Spam-Score: 0.3 (/)
X-Scan-Signature: 3e15cc4fdc61d7bce84032741d11c8e5
Content-Transfer-Encoding: 7bit

This is a reminder, sent out once a month, about your lists.ietf.org
mailing list memberships.  It includes your subscription info and how
to use it to change it or unsubscribe from a list.

You can visit the URLs to change your membership status or
configuration, including unsubscribing, setting digest-style delivery
or disabling delivery altogether (e.g., for a vacation), and so on.

In addition to the URL interfaces, you can also use email to make such
changes.  For more info, send a message to the '-request' address of
the list (for example, mailman-request@lists.ietf.org) containing just
the word 'help' in the message body, and an email message will be sent
to you with instructions.

**********************************************************************

NOTE WELL:

Any submission to the IETF intended by the Contributor for publication
as all or part of an IETF Internet-Draft or RFC and any statement made
within the context of an IETF activity is considered an "IETF
Contribution". Such statements include oral statements in IETF
sessions, as well as written and electronic communications made at any
time or place, which are addressed to:

o the IETF plenary session, o any IETF working group or portion
thereof, o the IESG, or any member thereof on behalf of the IESG, o
the IAB or any member thereof on behalf of the IAB, o any IETF mailing
list, including the IETF list itself, any working group
  or design team list, or any other list functioning under IETF
auspices,
o the RFC Editor or the Internet-Drafts function

All IETF Contributions are subject to the rules of RFC 3667 and RFC
3668.

Statements made outside of an IETF session, mailing list or other
function, that are clearly not intended to be input to an IETF
activity, group or function, are not IETF Contributions in the context
of this notice.

Please consult RFC 3667 for details.

*******************************************************************************


If you have questions, problems, comments, etc, send them to
mailman-owner@lists.ietf.org.  Thanks!

Passwords for ospf-wireless-design-archive@ietf.org:

List                                     Password // URL
----                                     --------  
ospf-wireless-design@lists.ietf.org      uxefev    
https://www1.ietf.org/mailman/options/ospf-wireless-design/ospf-wireless-design-archive%40ietf.org


From ospf-wireless-design-bounces@ietf.org  Tue Jan  4 14:26:28 2005
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id OAA10195;
	Tue, 4 Jan 2005 14:26:28 -0500 (EST)
Received: from megatron.ietf.org ([132.151.6.71])
	by ietf-mx.ietf.org with esmtp (Exim 4.33)
	id 1CluWV-00053Y-D1; Tue, 04 Jan 2005 14:39:20 -0500
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32)
	id 1CluCr-0005Qj-Qc; Tue, 04 Jan 2005 14:19:01 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32) id 1CluBU-0004ZY-18
	for ospf-wireless-design@megatron.ietf.org;
	Tue, 04 Jan 2005 14:17:36 -0500
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id OAA09534
	for <ospf-wireless-design@ietf.org>;
	Tue, 4 Jan 2005 14:17:34 -0500 (EST)
Received: from web52609.mail.yahoo.com ([206.190.39.147])
	by ietf-mx.ietf.org with smtp (Exim 4.33) id 1CluNg-0004sG-TY
	for ospf-wireless-design@ietf.org; Tue, 04 Jan 2005 14:30:26 -0500
Received: (qmail 83028 invoked by uid 60001); 4 Jan 2005 19:16:51 -0000
Message-ID: <20050104191651.83026.qmail@web52609.mail.yahoo.com>
Received: from [130.113.23.188] by web52609.mail.yahoo.com via HTTP;
	Tue, 04 Jan 2005 14:16:51 EST
Date: Tue, 4 Jan 2005 14:16:51 -0500 (EST)
From: Tao Lin <tlin_mcmaster@yahoo.ca>
Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper
To: Richard Ogier <rich.ogier@earthlink.net>, Abhay Roy <akr@cisco.com>
In-Reply-To: <41CAEBFE.2080703@earthlink.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Spam-Score: 0.0 (/)
X-Scan-Signature: ccfb4541e989aa743998098cd315d0fd
Cc: ospf-wireless-design@ietf.org
X-BeenThere: ospf-wireless-design@lists.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: OSPF Wireless Design Team  <ospf-wireless-design.lists.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <https://www1.ietf.org/mailman/private/ospf-wireless-design>
List-Post: <mailto:ospf-wireless-design@lists.ietf.org>
List-Help: <mailto:ospf-wireless-design-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=subscribe>
Sender: ospf-wireless-design-bounces@ietf.org
Errors-To: ospf-wireless-design-bounces@ietf.org
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 93df555cbdbcdae9621e5b95d44b301e

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 <rich.ogier@earthlink.net> 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" <mchandra@cisco.com>
> 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
> >> Ospf-wireless-design@lists.ietf.org
> >>
>
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> >>
> >
> > _______________________________________________
> > Ospf-wireless-design mailing list
> > Ospf-wireless-design@lists.ietf.org
> >
>
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> >
> 
> 
>  

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

_______________________________________________
Ospf-wireless-design mailing list
Ospf-wireless-design@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design


From ospf-wireless-design-bounces@ietf.org  Wed Jan  5 13:15:04 2005
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA27351;
	Wed, 5 Jan 2005 13:15:04 -0500 (EST)
Received: from megatron.ietf.org ([132.151.6.71])
	by ietf-mx.ietf.org with esmtp (Exim 4.33)
	id 1CmFt8-0007Qk-Vc; Wed, 05 Jan 2005 13:28:10 -0500
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32)
	id 1CmFbb-0003Sj-4U; Wed, 05 Jan 2005 13:09:59 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32) id 1CmFYn-0002t6-Kl
	for ospf-wireless-design@megatron.ietf.org;
	Wed, 05 Jan 2005 13:07:05 -0500
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id NAA26567
	for <ospf-wireless-design@ietf.org>;
	Wed, 5 Jan 2005 13:07:02 -0500 (EST)
Received: from sj-iport-3-in.cisco.com ([171.71.176.72]
	helo=sj-iport-3.cisco.com) by ietf-mx.ietf.org with esmtp (Exim 4.33)
	id 1CmFlK-0006hP-Lf
	for ospf-wireless-design@ietf.org; Wed, 05 Jan 2005 13:20:08 -0500
Received: from sj-core-5.cisco.com (171.71.177.238)
	by sj-iport-3.cisco.com with ESMTP; 05 Jan 2005 11:17:21 +0000
X-BrightmailFiltered: true
X-Brightmail-Tracker: AAAAAA==
Received: from mira-sjc5-b.cisco.com (IDENT:mirapoint@mira-sjc5-b.cisco.com
	[171.71.163.14])
	by sj-core-5.cisco.com (8.12.10/8.12.6) with ESMTP id j05I6Qjw009602;
	Wed, 5 Jan 2005 10:06:27 -0800 (PST)
Received: from irp-view9.cisco.com (irp-view9.cisco.com [171.70.65.147])
	by mira-sjc5-b.cisco.com (MOS 3.4.5-GR) with ESMTP id BAJ43574;
	Wed, 5 Jan 2005 10:06:26 -0800 (PST)
Date: Wed, 5 Jan 2005 10:06:25 -0800 (PST)
From: Abhay Roy <akr@cisco.com>
To: Richard Ogier <rich.ogier@earthlink.net>
Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper
In-Reply-To: <41CAEBFE.2080703@earthlink.net>
Message-ID: <Pine.GSO.4.58.0501050922050.25191@irp-view9.cisco.com>
References: <20041221180547.47390.qmail@web52601.mail.yahoo.com>
	<Pine.GSO.4.61.0412221214050.20350@irp-view9.cisco.com>
	<41CAEBFE.2080703@earthlink.net>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 2a76bcd37b1c8a21336eb0a1ea6bbf48
Cc: ospf-wireless-design@ietf.org
X-BeenThere: ospf-wireless-design@lists.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: OSPF Wireless Design Team  <ospf-wireless-design.lists.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <https://www1.ietf.org/mailman/private/ospf-wireless-design>
List-Post: <mailto:ospf-wireless-design@lists.ietf.org>
List-Help: <mailto:ospf-wireless-design-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=subscribe>
Sender: ospf-wireless-design-bounces@ietf.org
Errors-To: ospf-wireless-design-bounces@ietf.org
X-Spam-Score: 0.0 (/)
X-Scan-Signature: ded6070f7eed56e10c4f4d0d5043d9c7

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:

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

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

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
> > 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" <mchandra@cisco.com> 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
> >> Ospf-wireless-design@lists.ietf.org
> >> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> >>
> >
> > _______________________________________________
> > Ospf-wireless-design mailing list
> > Ospf-wireless-design@lists.ietf.org
> > https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> >
>

_______________________________________________
Ospf-wireless-design mailing list
Ospf-wireless-design@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design


From ospf-wireless-design-bounces@ietf.org  Thu Jan  6 17:07:50 2005
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA29459;
	Thu, 6 Jan 2005 17:07:50 -0500 (EST)
Received: from megatron.ietf.org ([132.151.6.71])
	by ietf-mx.ietf.org with esmtp (Exim 4.33)
	id 1Cmg0E-00059A-FX; Thu, 06 Jan 2005 17:21:10 -0500
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32)
	id 1CmfhJ-0005vJ-07; Thu, 06 Jan 2005 17:01:37 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32) id 1CmeAn-0001UG-Ug
	for ospf-wireless-design@megatron.ietf.org;
	Thu, 06 Jan 2005 15:23:59 -0500
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA13233
	for <ospf-wireless-design@ietf.org>;
	Thu, 6 Jan 2005 15:23:56 -0500 (EST)
Received: from cecom6.monmouth.army.mil ([134.80.0.9])
	by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CmeNd-0007eR-TH
	for ospf-wireless-design@ietf.org; Thu, 06 Jan 2005 15:37:14 -0500
Received: from MONM226.nae.ds.army.mil (mailsw2.monmouth.army.mil
	[134.80.5.41])
	by cecom6.monmouth.army.mil (8.12.11/8.12.11) with ESMTP id
	j06KNPm7013524 for <ospf-wireless-design@ietf.org>;
	Thu, 6 Jan 2005 15:23:25 -0500 (EST)
Received: from SWGM6.nae.ds.army.mil (unverified) by MONM226.nae.ds.army.mil
	(Content Technologies SMTPRS 4.3.12) with ESMTP id
	<T6e55076e2586500529b88@MONM226.nae.ds.army.mil> for
	<ospf-wireless-design@ietf.org>; Thu, 6 Jan 2005 15:22:32 -0500
Received: by swgm6.monmouth.army.mil with Internet Mail Service (5.5.2656.59)
	id <Y8HWMKKV>; Thu, 6 Jan 2005 15:22:32 -0500
Message-ID: <D2AA47A6FB2C1A48AF0526440C0F245C83A362@monm207.nae.ds.army.mil>
From: "Green, David B RDECOM CERDEC STCD SRI" <Dave.B.Green@us.army.mil>
Subject: RE: FW: [Ospf-wireless-design] Tao Lin paper
Date: Thu, 6 Jan 2005 15:22:29 -0500 
MIME-Version: 1.0
X-Mailer: Internet Mail Service (5.5.2656.59)
Content-Type: text/plain;
	charset="iso-8859-1"
X-Spam-Score: 0.0 (/)
X-Scan-Signature: a4a24b484706be629f915bfb1a3e4771
X-Mailman-Approved-At: Thu, 06 Jan 2005 17:01:35 -0500
Cc: ospf-wireless-design@ietf.org
X-BeenThere: ospf-wireless-design@lists.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: OSPF Wireless Design Team  <ospf-wireless-design.lists.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <https://www1.ietf.org/mailman/private/ospf-wireless-design>
List-Post: <mailto:ospf-wireless-design@lists.ietf.org>
List-Help: <mailto:ospf-wireless-design-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=subscribe>
Sender: ospf-wireless-design-bounces@ietf.org
Errors-To: ospf-wireless-design-bounces@ietf.org
X-Spam-Score: 0.0 (/)
X-Scan-Signature: b84f8c8fba0e1389e5eb998b64078964

Roy,
To expound on the "other constraints" you mentioned in this statement:
"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."

As a note, in a tradeoff between computational power vs. number of transmissions 
necessary to flood routing information, I think you will find using computational power to pre-determine the optimal path is cheap when compared to the cost of extra transmissions on most radios. Throughput, low delay, and transmission power costs are at premium in most actual MANET nodes. If it takes an order of magnitude longer to compute an optimal path in a CPU, the delay and power costs will generally be far cheaper than the cost 
of an extra transmission on the network. We recently modeled data compression as a tradeoff 
in CPU time vs. transmission time in JTRS-type radios and found the transmission cost (delay & power consumption)  for a single extra transmission was several order's of magnitude higher than the CPU cost to reduce the number of transmissions. 

Transmission cost for each radio datagram must factor:

IP Header 
UDP or TCP Header   
Security Header  
Radio Network Header 
Radio Link Layer Header  
Modem Framing 
CRC  FEC 
Waveform Framing  
Power Amp Tuning Time
Synchronization Probe Overhead   
Channel Acquisition (RTS/CTS)   
Frame Acknowledge (ACK)
Average Contention Interval  

OPNET does have the ability to model CPU usage so we compared CPU time costs to the cost of the number of data transmissions on the network and found a several orders of magnitude delta for data compression in some cases. As a caveat - our compression time performance was linear with respect to the data set size while path algorithms are exponential or logarithmic to the number of nodes in the data set. However, I think you will still have a large tradeoff delta between computation costs vs. transmission costs. 

David Green 
CERDEC Site Manager
SRI International
Office: (732) 532-6715
Mobile: (732) 693-6500

-----Original Message-----
From: Abhay Roy [mailto:akr@cisco.com]
Sent: Wednesday, January 05, 2005 1:06 PM
To: Richard Ogier
Cc: ospf-wireless-design@ietf.org
Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper


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:

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

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

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
> > 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" <mchandra@cisco.com> 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
> >> Ospf-wireless-design@lists.ietf.org
> >> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> >>
> >
> > _______________________________________________
> > Ospf-wireless-design mailing list
> > Ospf-wireless-design@lists.ietf.org
> > https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> >
>

_______________________________________________
Ospf-wireless-design mailing list
Ospf-wireless-design@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design

_______________________________________________
Ospf-wireless-design mailing list
Ospf-wireless-design@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design


From ospf-wireless-design-bounces@ietf.org  Thu Jan  6 21:36:56 2005
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id VAA19731;
	Thu, 6 Jan 2005 21:36:56 -0500 (EST)
Received: from megatron.ietf.org ([132.151.6.71])
	by ietf-mx.ietf.org with esmtp (Exim 4.33)
	id 1CmkCg-0006xc-An; Thu, 06 Jan 2005 21:50:18 -0500
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32)
	id 1Cmjv3-0008Ru-SU; Thu, 06 Jan 2005 21:32:05 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32) id 1Cmjs5-0007Cs-6T
	for ospf-wireless-design@megatron.ietf.org;
	Thu, 06 Jan 2005 21:29:01 -0500
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id VAA19307
	for <ospf-wireless-design@ietf.org>;
	Thu, 6 Jan 2005 21:28:59 -0500 (EST)
Received: from slb-smtpout-01.boeing.com ([130.76.64.48])
	by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1Cmk4x-0006jT-Hz
	for ospf-wireless-design@ietf.org; Thu, 06 Jan 2005 21:42:21 -0500
Received: from stl-av-01.boeing.com ([192.76.190.6])
	by slb-smtpout-01.boeing.com (8.9.2.MG.10092003/8.8.5-M2) with ESMTP id
	SAA01260; Thu, 6 Jan 2005 18:28:19 -0800 (PST)
Received: from XCH-NWBH-02.nw.nos.boeing.com (localhost [127.0.0.1])
	by stl-av-01.boeing.com (8.11.3/8.11.3/MBS-AV-LDAP-01) with ESMTP id
	j072SJs05449; Thu, 6 Jan 2005 20:28:19 -0600 (CST)
Received: from XCH-NW-27.nw.nos.boeing.com ([192.48.4.101]) by
	XCH-NWBH-02.nw.nos.boeing.com with Microsoft SMTPSVC(6.0.3790.0); 
	Thu, 6 Jan 2005 18:28:20 -0800
X-MimeOLE: Produced By Microsoft Exchange V6.0.6603.0
content-class: urn:content-classes:message
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Date: Thu, 6 Jan 2005 18:28:20 -0800
Message-ID: <6938661A6EDA8A4EA8D1419BCE46F24C040609B8@xch-nw-27.nw.nos.boeing.com>
Thread-Topic: FW: [Ospf-wireless-design] Tao Lin paper
Thread-Index: AcT0PZehzE6Y27KpRf+5eVkrpqri1QAIKtTA
From: "Henderson, Thomas R" <thomas.r.henderson@boeing.com>
To: <ospf-wireless-design@ietf.org>
X-OriginalArrivalTime: 07 Jan 2005 02:28:20.0511 (UTC)
	FILETIME=[8DBB32F0:01C4F460]
X-Spam-Score: 0.0 (/)
X-Scan-Signature: a7d6aff76b15f3f56fcb94490e1052e4
Content-Transfer-Encoding: quoted-printable
Subject: [Ospf-wireless-design] OSPF MANET simulator
X-BeenThere: ospf-wireless-design@lists.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: OSPF Wireless Design Team  <ospf-wireless-design.lists.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <https://www1.ietf.org/mailman/private/ospf-wireless-design>
List-Post: <mailto:ospf-wireless-design@lists.ietf.org>
List-Help: <mailto:ospf-wireless-design-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=subscribe>
Sender: ospf-wireless-design-bounces@ietf.org
Errors-To: ospf-wireless-design-bounces@ietf.org
X-Spam-Score: 0.0 (/)
X-Scan-Signature: c1c65599517f9ac32519d043c37c5336
Content-Transfer-Encoding: quoted-printable

All,
I mentioned at the last IETF that we have been working on a simulator
for evaluating alternative solutions for OSPF MANET.  We've made
our current snapshot of the simulator available at the following
URL:
http://hipserver.mct.phantomworks.org/ietf/ospf/

This is a free, open-source simulator that we have obtained
approval to share with the IETF OSPF MANET design team.  We have
striven to create thorough documentation for this simulator, in
the hopes that anyone else on the design team who wants to kick
the tires themselves on these various proposals, double check
the simulation results, or extend it themselves, can do so
freely and without purchasing a license.  It runs on Linux
(probably Solaris too, although we haven't tried) and probably
can run on Windows too if you install cygwin. =20

In a nutshell, it is based on both the Georgia Tech Network
Simulator and the quagga open source routing daemon.  It=20
has the following features:

- a port of the quagga ospf6d routing daemon to simulation
space (it is OSPFv3, but running over an IPv4 simulation
substrate by means of internal NATting within the node)

- can be compiled to run as a quagga implementation, for
those people interested in actual experiments

- provides a multicast-capable Point-to-Multipoint interface
for use as a performance baseline

- implements draft-chandra-ospf-manet-ext-01.txt

- (more to come)

I encourage people to download the documentation and/or code
and have a look.  We have put some preliminary results in
Chapter 7 of the documentation, and will have more to say about
them in a later message.

Tom
=20

_______________________________________________
Ospf-wireless-design mailing list
Ospf-wireless-design@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design


From ospf-wireless-design-bounces@ietf.org  Fri Jan  7 12:33:41 2005
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA00393;
	Fri, 7 Jan 2005 12:33:41 -0500 (EST)
Received: from megatron.ietf.org ([132.151.6.71])
	by ietf-mx.ietf.org with esmtp (Exim 4.33)
	id 1CmyCd-0000Sp-NI; Fri, 07 Jan 2005 12:47:12 -0500
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32)
	id 1Cmxvs-0002QT-Km; Fri, 07 Jan 2005 12:29:52 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32) id 1Cmxnd-0007eK-7V
	for ospf-wireless-design@megatron.ietf.org;
	Fri, 07 Jan 2005 12:21:21 -0500
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA29197
	for <ospf-wireless-design@ietf.org>;
	Fri, 7 Jan 2005 12:21:18 -0500 (EST)
Received: from pop-a065b10.pas.sa.earthlink.net ([207.217.121.170])
	by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1Cmy0e-0007hG-GF
	for ospf-wireless-design@ietf.org; Fri, 07 Jan 2005 12:34:49 -0500
Received: from dialup-4.246.254.76.dial1.sanjose1.level3.net ([4.246.254.76]
	helo=earthlink.net)
	by pop-a065b10.pas.sa.earthlink.net with esmtp (Exim 3.33 #1)
	id 1CmxnY-0006lx-00; Fri, 07 Jan 2005 09:21:17 -0800
Message-ID: <41DEC50B.2080305@earthlink.net>
Date: Fri, 07 Jan 2005 09:21:15 -0800
From: Richard Ogier <rich.ogier@earthlink.net>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US;
	rv:0.9.4) Gecko/20011128 Netscape6/6.2.1 (emach0202)
X-Accept-Language: en-us
MIME-Version: 1.0
To: Abhay Roy <akr@cisco.com>, ospf-wireless-design@ietf.org
Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper
References: <Pine.GSO.4.58.0501052107020.28588@irp-view9.cisco.com>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 2.9 (++)
X-Scan-Signature: 2b2ad76aced9b1d558e34a970a85c027
Content-Transfer-Encoding: 7bit
X-BeenThere: ospf-wireless-design@lists.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: OSPF Wireless Design Team  <ospf-wireless-design.lists.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <https://www1.ietf.org/mailman/private/ospf-wireless-design>
List-Post: <mailto:ospf-wireless-design@lists.ietf.org>
List-Help: <mailto:ospf-wireless-design-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=subscribe>
Sender: ospf-wireless-design-bounces@ietf.org
Errors-To: ospf-wireless-design-bounces@ietf.org
X-Spam-Score: 2.9 (++)
X-Scan-Signature: dd7e0c3fd18d19cffdd4de99a114001d
Content-Transfer-Encoding: 7bit

Roy,

Please see my comments and answers below.
Many of your questions will be answered in more detail
in the draft I will be submitting in a few days.

Abhay Roy wrote:

>
>
>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.
>
In the algorithm I describe below, node i is doing computation
from the perspective of only one neighbor, the one with maximum
value of (RtrPri, RID).

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

Yes, the CDS computed by each algorithms in my draft is SI.
A CDS is just a set of nodes.  If different CDS's are computed
for different sources, then that should be made clear.
I have not seen an algorithm that explicitly computes a SD-CDS.
For example, if we are talking about the set of nodes that transmit
a given LSA using MPRs, then this set is SD, but is also
dependent on the order in which a node receives LSAs, so the CDS
is not explicitly computed in advance.

Perhaps a more important distinction is whether the relays
(whether CDS or MPR) select themselves, or are selected
by neighbors.

>
>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.
>
My new draft will cover this. But in my draft, backup CDS nodes are
computed in advance, and are selected to provide biconnectivity.
My draft will give more details, but I will include a summary of
features at the end of this message.

>
>
>Some questions inline..
>
>On 12/23/04-0800 at 8:02am, Richard Ogier writes:
>
>>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.
>>
>
>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.
>
The CDS algorithm described in my email, and the ones in my draft
that result in the smallest CDS, require only O(d^2) time,
where d is the number of neighbors.
It is not possible to do beter then this, since it requires
this much time just to process all neighbors' Hellos.
Dijkstra also requires more time than this, since d^2 < d*n = m,
where n is the number of nodes and m is the number of edges.
Also, consider how many orders of magnitude faster today's
procesors compared to the 80s, when Dijkstra was first used
in OSPF.  My draft also proposes an optional CDS algorithm
that runs in O(n^3) time, but even this should be acceptable,
since the bottleneck in MANETs is bandwidth, not processing.

>It might be 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.
>
First of all, consider the DR selection algorithm of OSPF.
It requires that all nodes in the broadcast network agree
that the router with maximum (RtrPri, RID) should be the DR
(unless there is already an existing DR). The algorithms
in my draft also give preference for routers with the largest
value of (RtrPri, RID), and in fact they generalize OSPF's
DR selection algorithm. So, the use of a SI-CDS is quite
consistent with the philosophy of OSPF.
Morever, you will see in my draft that there is a lot of
flexibility possible, given the preference for such routers.

(Obviously, we don't need to allow each router to run
any algorithm it wants.)

However, MPRs have a serious limitation that is
illustrated by my example. MPRs must be selected to
provide flooding along min-hop paths.
They cannot trade off path optimality to reduce
the size of the relay set.

>>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.
>>
>
>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"?
>
I really want to use the term DR here, because is generalizes
the OSPF concept of a DR.  Consider a 1-hop MANET network, which
is equivalent to a wireless broadcast network  In such a network,
the CDS algorithms I propose will select the same DR and
Backup DR as OSPF would in a broadcast network.

>
>
>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.
>
This will become clear in my draft. RtrPri can depend on node degree,
or neighbor stability, or willingness to relay, etc.

>
>
>Also this step seems arbitrary in electing a relay v/s say "If I
>have a higher degree than any of my neighbors".
>
I guess I just answered this above, since RtrPri can depend on degree.
I would rather not insist that all nodes choose RtrPri in the same way,
to allow flexibility while ensuring interoperability. Besides,
some CDS algorithms perform better when node degree is not used.

>>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.
>
No, just a single (modified) SPF rooted at the single neighbor j.
That is how I get O(d^2).

Here is a summary of features from my draft to be submitted in
a few days:

  - The document presents a family of interoperable CDS algorithms,
    which allow a tradeoff between path optimality and CDS size.
    Simulation results are presented to show this tradeoff.

  - The CDS algorithms are based only on 2-hop neighbor information,
    to provide fast convergence following topology changes.

  - The CDS algorithms are interoperable because the CDS computed by
    each algorithm contains a minimal, source-independent CDS called
    the "Essential" CDS. The Essential CDS can be computed in O(d^2)
    time, where d is the number of neighbors.

  - The Essential CDS is very scalable, as shown by the simulation
    results in Section 10. In a 300 node network with average degree
    64 and diameter 5, the Essential CDS consists of only 23 (8%) of
    the nodes on average.

  - The Essential CDS provides a minimal, source-independent set
    of relays for flooding LSAs (or other flooded packets).
    The flooding procedure also allows source-dependent flooding
    (using previous-hop information) as an option, if it is desired
    to flood packets along min-hop paths.

  - For improved CDS stability, each algorithm in the family has a
    "persistent" version, in which a router in the CDS remains in
    the CDS until it becomes redundant.

  - Generalizes the OSPF concept of a Designated Router (DR) and
    Backup DR to MANETs. The set of DRs forms a CDS, and the set of
    DRs and Backup DRs forms a biconnected CDS for robustness.
    When applied to a broadcast network, the persistent version of
    each algorithm computes the same DR and Backup DR as OSPF.

  - Adjacencies are formed only between CDS nodes (DRs and Backup DRs)
    and their neighbors, as in legacy OSPF.

  - Provides a flexible choice of which neighbors to include in LSAs,
    from a minimum set of neighbors adjacent to DRs and Backup DRs,
    to the full network topology.

Regards,
Richard

>
>
>Regards,
>-Roy-
>



_______________________________________________
Ospf-wireless-design mailing list
Ospf-wireless-design@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design


From ospf-wireless-design-bounces@ietf.org  Wed Jan 12 12:47:18 2005
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA01538;
	Wed, 12 Jan 2005 12:47:18 -0500 (EST)
Received: from megatron.ietf.org ([132.151.6.71])
	by ietf-mx.ietf.org with esmtp (Exim 4.33)
	id 1Comob-0003B1-2u; Wed, 12 Jan 2005 13:01:53 -0500
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32)
	id 1ComSQ-0004pO-97; Wed, 12 Jan 2005 12:38:58 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32) id 1ComS3-0004cO-6c
	for ospf-wireless-design@megatron.ietf.org;
	Wed, 12 Jan 2005 12:38:35 -0500
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA01058
	for <ospf-wireless-design@ietf.org>;
	Wed, 12 Jan 2005 12:38:32 -0500 (EST)
Received: from pop-a065b10.pas.sa.earthlink.net ([207.217.121.170])
	by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1Comg5-0002zn-Vp
	for ospf-wireless-design@ietf.org; Wed, 12 Jan 2005 12:53:07 -0500
Received: from dialup-4.243.131.28.dial1.sanfrancisco1.level3.net
	([4.243.131.28] helo=earthlink.net)
	by pop-a065b10.pas.sa.earthlink.net with esmtp (Exim 3.33 #1)
	id 1ComRq-0004Q9-00; Wed, 12 Jan 2005 09:38:23 -0800
Message-ID: <41E56087.8050800@earthlink.net>
Date: Wed, 12 Jan 2005 09:38:15 -0800
From: Richard Ogier <rich.ogier@earthlink.net>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US;
	rv:0.9.4) Gecko/20011128 Netscape6/6.2.1 (emach0202)
X-Accept-Language: en-us
MIME-Version: 1.0
To: Tao Lin <tlin_mcmaster@yahoo.ca>
Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper
References: <20050104191651.83026.qmail@web52609.mail.yahoo.com>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 2.9 (++)
X-Scan-Signature: e178fd6cb61ffb6940cd878e7fea8606
Content-Transfer-Encoding: 7bit
Cc: ospf-wireless-design@ietf.org
X-BeenThere: ospf-wireless-design@lists.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: OSPF Wireless Design Team  <ospf-wireless-design.lists.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <https://www1.ietf.org/mailman/private/ospf-wireless-design>
List-Post: <mailto:ospf-wireless-design@lists.ietf.org>
List-Help: <mailto:ospf-wireless-design-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=subscribe>
Sender: ospf-wireless-design-bounces@ietf.org
Errors-To: ospf-wireless-design-bounces@ietf.org
X-Spam-Score: 2.9 (++)
X-Scan-Signature: 27ec2ff0f5c3b18b49c722f4f1748838
Content-Transfer-Encoding: 7bit

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


Tao Lin wrote:

>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 <rich.ogier@earthlink.net> 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" <mchandra@cisco.com>
>>>>
>>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
>>>>Ospf-wireless-design@lists.ietf.org
>>>>
>https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
>
>>>_______________________________________________
>>>Ospf-wireless-design mailing list
>>>Ospf-wireless-design@lists.ietf.org
>>>
>https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
>
>>
>> 
>>
>
>______________________________________________________________________ 
>Post your free ad now! http://personals.yahoo.ca
>



_______________________________________________
Ospf-wireless-design mailing list
Ospf-wireless-design@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design


From ospf-wireless-design-bounces@ietf.org  Wed Jan 12 15:34:54 2005
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA12098;
	Wed, 12 Jan 2005 15:34:53 -0500 (EST)
Received: from megatron.ietf.org ([132.151.6.71])
	by ietf-mx.ietf.org with esmtp (Exim 4.33)
	id 1CopQm-0006RQ-VD; Wed, 12 Jan 2005 15:49:29 -0500
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32)
	id 1CopBb-0007oR-6w; Wed, 12 Jan 2005 15:33:47 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32) id 1Cop7W-0005Rq-V0
	for ospf-wireless-design@megatron.ietf.org;
	Wed, 12 Jan 2005 15:29:37 -0500
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA11749
	for <ospf-wireless-design@ietf.org>;
	Wed, 12 Jan 2005 15:29:33 -0500 (EST)
Received: from web52605.mail.yahoo.com ([206.190.39.143])
	by ietf-mx.ietf.org with smtp (Exim 4.33) id 1CopLZ-0006Lw-8D
	for ospf-wireless-design@ietf.org; Wed, 12 Jan 2005 15:44:08 -0500
Received: (qmail 75053 invoked by uid 60001); 12 Jan 2005 20:29:00 -0000
Message-ID: <20050112202900.75051.qmail@web52605.mail.yahoo.com>
Received: from [130.113.23.188] by web52605.mail.yahoo.com via HTTP;
	Wed, 12 Jan 2005 15:29:00 EST
Date: Wed, 12 Jan 2005 15:29:00 -0500 (EST)
From: Tao Lin <tlin_mcmaster@yahoo.ca>
Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper
To: Richard Ogier <rich.ogier@earthlink.net>
In-Reply-To: <41E56087.8050800@earthlink.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 72dbfff5c6b8ad2b1b727c13be042129
Cc: ospf-wireless-design@ietf.org
X-BeenThere: ospf-wireless-design@lists.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: OSPF Wireless Design Team  <ospf-wireless-design.lists.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <https://www1.ietf.org/mailman/private/ospf-wireless-design>
List-Post: <mailto:ospf-wireless-design@lists.ietf.org>
List-Help: <mailto:ospf-wireless-design-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=subscribe>
Sender: ospf-wireless-design-bounces@ietf.org
Errors-To: ospf-wireless-design-bounces@ietf.org
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 1e467ff145ef391eb7b594ef62b8301f

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

 --- Richard Ogier <rich.ogier@earthlink.net> wrote: 
> 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
> 
> 
> Tao Lin wrote:
> 
> >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 <rich.ogier@earthlink.net>
> 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
> 
=== message truncated === 

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

_______________________________________________
Ospf-wireless-design mailing list
Ospf-wireless-design@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design


From ospf-wireless-design-bounces@ietf.org  Wed Jan 12 20:22:05 2005
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id UAA06811;
	Wed, 12 Jan 2005 20:22:05 -0500 (EST)
Received: from megatron.ietf.org ([132.151.6.71])
	by ietf-mx.ietf.org with esmtp (Exim 4.33)
	id 1Cotuh-0005d6-T1; Wed, 12 Jan 2005 20:36:43 -0500
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32)
	id 1CotfU-00059J-0A; Wed, 12 Jan 2005 20:20:56 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32) id 1CotcE-0004FZ-Hy
	for ospf-wireless-design@megatron.ietf.org;
	Wed, 12 Jan 2005 20:17:34 -0500
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id UAA06577
	for <ospf-wireless-design@ietf.org>;
	Wed, 12 Jan 2005 20:17:33 -0500 (EST)
Received: from pop-a065b10.pas.sa.earthlink.net ([207.217.121.170])
	by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CotqJ-0005YT-Cv
	for ospf-wireless-design@ietf.org; Wed, 12 Jan 2005 20:32:10 -0500
Received: from dialup-4.243.137.9.dial1.sanfrancisco1.level3.net
	([4.243.137.9] helo=earthlink.net)
	by pop-a065b10.pas.sa.earthlink.net with esmtp (Exim 3.33 #1)
	id 1Cotc7-0003A9-00; Wed, 12 Jan 2005 17:17:27 -0800
Message-ID: <41E5CC1A.2060905@earthlink.net>
Date: Wed, 12 Jan 2005 17:17:14 -0800
From: Richard Ogier <rich.ogier@earthlink.net>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US;
	rv:0.9.4) Gecko/20011128 Netscape6/6.2.1 (emach0202)
X-Accept-Language: en-us
MIME-Version: 1.0
To: Tao Lin <tlin_mcmaster@yahoo.ca>
Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper
References: <20050112202900.75051.qmail@web52605.mail.yahoo.com>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.1 (/)
X-Scan-Signature: 410b68b37343617c6913e76d02180b14
Content-Transfer-Encoding: 7bit
Cc: ospf-wireless-design@ietf.org
X-BeenThere: ospf-wireless-design@lists.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: OSPF Wireless Design Team  <ospf-wireless-design.lists.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <https://www1.ietf.org/mailman/private/ospf-wireless-design>
List-Post: <mailto:ospf-wireless-design@lists.ietf.org>
List-Help: <mailto:ospf-wireless-design-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=subscribe>
Sender: ospf-wireless-design-bounces@ietf.org
Errors-To: ospf-wireless-design-bounces@ietf.org
X-Spam-Score: 0.1 (/)
X-Scan-Signature: 83867a50fd8f547996ccdaf89af24437
Content-Transfer-Encoding: 7bit

Hi Tao,

Tao Lin wrote:

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

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

>
>
>  Tao
>
> --- Richard Ogier <rich.ogier@earthlink.net> wrote: 
>
>>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
>>
>>
>>Tao Lin wrote:
>>
>>>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 <rich.ogier@earthlink.net>
>>>
>>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
>>>>
>=== message truncated === 
>
>______________________________________________________________________ 
>Post your free ad now! http://personals.yahoo.ca
>



_______________________________________________
Ospf-wireless-design mailing list
Ospf-wireless-design@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design


From ospf-wireless-design-bounces@ietf.org  Fri Jan 14 00:38:02 2005
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id AAA28767;
	Fri, 14 Jan 2005 00:38:02 -0500 (EST)
Received: from megatron.ietf.org ([132.151.6.71])
	by ietf-mx.ietf.org with esmtp (Exim 4.33)
	id 1CpKOD-0002YG-VD; Fri, 14 Jan 2005 00:52:57 -0500
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32)
	id 1CpK66-0003uL-Fq; Fri, 14 Jan 2005 00:34:10 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32) id 1CpK3D-0002vk-NT
	for ospf-wireless-design@megatron.ietf.org;
	Fri, 14 Jan 2005 00:31:11 -0500
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id AAA28331
	for <ospf-wireless-design@ietf.org>;
	Fri, 14 Jan 2005 00:31:07 -0500 (EST)
Received: from stl-smtpout-01.boeing.com ([130.76.96.56])
	by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CpKHX-0002NY-94
	for ospf-wireless-design@ietf.org; Fri, 14 Jan 2005 00:46:02 -0500
Received: from blv-av-01.boeing.com ([192.42.227.216])
	by stl-smtpout-01.boeing.com (8.9.2.MG.10092003/8.8.5-M2) with ESMTP id
	XAA20165; Thu, 13 Jan 2005 23:30:28 -0600 (CST)
Received: from xch-nwbh-01.nw.nos.boeing.com (localhost [127.0.0.1])
	by blv-av-01.boeing.com (8.11.3/8.11.3/MBS-AV-LDAP-01) with ESMTP id
	j0E5URP12094; Thu, 13 Jan 2005 21:30:27 -0800 (PST)
Received: from XCH-NW-27.nw.nos.boeing.com ([192.48.4.101]) by
	xch-nwbh-01.nw.nos.boeing.com with Microsoft SMTPSVC(6.0.3790.0); 
	Thu, 13 Jan 2005 21:30:18 -0800
X-MimeOLE: Produced By Microsoft Exchange V6.0.6603.0
content-class: urn:content-classes:message
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Subject: RE: FW: [Ospf-wireless-design] Tao Lin paper
Date: Thu, 13 Jan 2005 21:30:18 -0800
Message-ID: <6938661A6EDA8A4EA8D1419BCE46F24C040609CB@xch-nw-27.nw.nos.boeing.com>
Thread-Topic: FW: [Ospf-wireless-design] Tao Lin paper
Thread-Index: AcT4zsqna5IoTIODSb+78qU5gBRdnwBJ9a+Q
From: "Henderson, Thomas R" <thomas.r.henderson@boeing.com>
To: "Richard Ogier" <rich.ogier@earthlink.net>,
        "Tao Lin" <tlin_mcmaster@yahoo.ca>
X-OriginalArrivalTime: 14 Jan 2005 05:30:18.0874 (UTC)
	FILETIME=[22796DA0:01C4F9FA]
X-Spam-Score: 0.0 (/)
X-Scan-Signature: fb6060cb60c0cea16e3f7219e40a0a81
Content-Transfer-Encoding: quoted-printable
Cc: ospf-wireless-design@ietf.org
X-BeenThere: ospf-wireless-design@lists.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: OSPF Wireless Design Team  <ospf-wireless-design.lists.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <https://www1.ietf.org/mailman/private/ospf-wireless-design>
List-Post: <mailto:ospf-wireless-design@lists.ietf.org>
List-Help: <mailto:ospf-wireless-design-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=subscribe>
Sender: ospf-wireless-design-bounces@ietf.org
Errors-To: ospf-wireless-design-bounces@ietf.org
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 6cca30437e2d04f45110f2ff8dc1b1d5
Content-Transfer-Encoding: quoted-printable



> -----Original Message-----
> From: Richard Ogier [mailto:rich.ogier@earthlink.net]
> Sent: Wednesday, January 12, 2005 9:38 AM
> To: Tao Lin
> Cc: ospf-wireless-design@ietf.org
> Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper
>=20
>=20
> Tao,
>=20
> This morning, I looked at your CDS algorithm in
>=20
>      T. Lin, S.F. Midkiff, and J.S. Park. "A Framework for
>      Wireless Ad Hoc Routing Protocols", IEEE WCNC, March 2003.
>=20
> 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:
>=20
>   "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."
>=20
> 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.)
>=20
> 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.

This has been our assumption as well.  In the paper, it states:
"Here we propose a modified OLSR that can build one copy of
the connected dominating set as the RNS for the network."

Consequently, in that paper, we took the description:=20
"When a node i has a neighboring node that is
not covered by the sender node j, node i checks whether there
is a common neighbor between i and j, say node x, that covers
that neighbor. Node i rebroadcasts the message if node x does
not exist or if x has a smaller degree."=20
to mean that one iterates across all such possible sender nodes j
(and the node relays all messages if, for at least one such
sender node j, the condition holds true).

In our previous simulation draft (back in June) we used the
following pseudocode:

foreach neighbor j {
  cover_list =3D all of my neighbors that j does not cover
  if (cover_list =3D=3D NULL) {
    next neighbor
  } =20
  foreach router k in cover_list {
    search for common neighbor between myself and j that covers k
    if such neighbor exists with larger degree, or with equal degree and =
larger ID {
      I am in CDS
      break
    }
  } =20
}
=20

_______________________________________________
Ospf-wireless-design mailing list
Ospf-wireless-design@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design


From ospf-wireless-design-bounces@ietf.org  Fri Jan 14 12:24:39 2005
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA29727;
	Fri, 14 Jan 2005 12:24:39 -0500 (EST)
Received: from megatron.ietf.org ([132.151.6.71])
	by ietf-mx.ietf.org with esmtp (Exim 4.33)
	id 1CpVQB-0007uR-OQ; Fri, 14 Jan 2005 12:39:40 -0500
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32)
	id 1CpV7J-0002tn-BP; Fri, 14 Jan 2005 12:20:09 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32) id 1CpUvz-0005iJ-G3
	for ospf-wireless-design@megatron.ietf.org;
	Fri, 14 Jan 2005 12:08:27 -0500
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id MAA28880
	for <ospf-wireless-design@ietf.org>;
	Fri, 14 Jan 2005 12:08:25 -0500 (EST)
Received: from pop-a065c28.pas.sa.earthlink.net ([207.217.121.205])
	by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CpVAS-0007bJ-PZ
	for ospf-wireless-design@ietf.org; Fri, 14 Jan 2005 12:23:25 -0500
Received: from dialup-4.243.137.45.dial1.sanfrancisco1.level3.net
	([4.243.137.45] helo=earthlink.net)
	by pop-a065c28.pas.sa.earthlink.net with esmtp (Exim 3.33 #1)
	id 1CpUvt-0003s9-00; Fri, 14 Jan 2005 09:08:22 -0800
Message-ID: <41E7FC66.70208@earthlink.net>
Date: Fri, 14 Jan 2005 09:07:50 -0800
From: Richard Ogier <rich.ogier@earthlink.net>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US;
	rv:0.9.4) Gecko/20011128 Netscape6/6.2.1 (emach0202)
X-Accept-Language: en-us
MIME-Version: 1.0
To: "Henderson, Thomas R" <thomas.r.henderson@boeing.com>
Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper
References: <6938661A6EDA8A4EA8D1419BCE46F24C040609CB@xch-nw-27.nw.nos.boeing.com>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 2.9 (++)
X-Scan-Signature: 6e922792024732fb1bb6f346e63517e4
Content-Transfer-Encoding: 7bit
Cc: ospf-wireless-design@ietf.org
X-BeenThere: ospf-wireless-design@lists.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: OSPF Wireless Design Team  <ospf-wireless-design.lists.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <https://www1.ietf.org/mailman/private/ospf-wireless-design>
List-Post: <mailto:ospf-wireless-design@lists.ietf.org>
List-Help: <mailto:ospf-wireless-design-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=subscribe>
Sender: ospf-wireless-design-bounces@ietf.org
Errors-To: ospf-wireless-design-bounces@ietf.org
X-Spam-Score: 2.9 (++)
X-Scan-Signature: 9a2be21919e71dc6faef12b370c4ecf5
Content-Transfer-Encoding: 7bit

Please see my comment below.

Henderson, Thomas R wrote:

>>-----Original Message-----
>>From: Richard Ogier [mailto:rich.ogier@earthlink.net]
>>Sent: Wednesday, January 12, 2005 9:38 AM
>>To: Tao Lin
>>Cc: ospf-wireless-design@ietf.org
>>Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper
>>
>>
>>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.
>>
>
>This has been our assumption as well.  In the paper, it states:
>"Here we propose a modified OLSR that can build one copy of
>the connected dominating set as the RNS for the network."
>
>Consequently, in that paper, we took the description: 
>"When a node i has a neighboring node that is
>not covered by the sender node j, node i checks whether there
>is a common neighbor between i and j, say node x, that covers
>that neighbor. Node i rebroadcasts the message if node x does
>not exist or if x has a smaller degree." 
>to mean that one iterates across all such possible sender nodes j
>(and the node relays all messages if, for at least one such
>sender node j, the condition holds true).
>
>In our previous simulation draft (back in June) we used the
>following pseudocode:
>
>foreach neighbor j {
>  cover_list = all of my neighbors that j does not cover
>  if (cover_list == NULL) {
>    next neighbor
>  }  
>  foreach router k in cover_list {
>    search for common neighbor between myself and j that covers k
>    if such neighbor exists with larger degree, or with equal degree and larger ID {
>      I am in CDS
>      break
>    }
>  }  
>}
>
Actually, the calculation needs to be done in advance
for all neighbors, to be prepared for an LSA that is
received from any neighbor. Therefore Phase 1 of Lin's
algorithm is still the same as Phase 1 of the ANP algorithm
(in my draft) with h1 = 2 and RtrPri equal to node degree.
However, only step (b) of my Forwarding Procedure is used,
so that a new LSA is forwarded only if it is received from
a Dependent Neighbor (analogous to an MPR Selector).

It would be inefficient for *all* nodes in this large SI-CDS
(calculated by ANP with h1 = 2) to forward a given LSA.

While I'm here, I would like to point out a mistake in my draft
that I will correct in the next update. In the ANP CDS algorithm,
instead of a router being either a DR or a BDR (or neither),
it is possible for a router to be a DR for one (dependent) neighbor,
and also a BDR for another (dependent) neighbor. (This is not a
problem for the Essential CDS and MPN algorithms, since only one
neighbor is considered.) Therefore, I will modify the ANP algorithm
to allow this, by introducing the term "Backup Dependent Neighbor".
Of course, this would be analogous to a "Backup MPR Selector"
(a neighbor that has selected the router as a "Backup MPR",
although this latter term cannot be found by a Google search).

Richard


_______________________________________________
Ospf-wireless-design mailing list
Ospf-wireless-design@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design


From ospf-wireless-design-bounces@ietf.org  Fri Jan 21 16:17:03 2005
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id QAA20535;
	Fri, 21 Jan 2005 16:17:03 -0500 (EST)
Received: from megatron.ietf.org ([132.151.6.71])
	by ietf-mx.ietf.org with esmtp (Exim 4.33)
	id 1Cs6PN-0000wg-To; Fri, 21 Jan 2005 16:33:35 -0500
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32)
	id 1Cs5pn-00089x-Qx; Fri, 21 Jan 2005 15:56:47 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32) id 1Cs5nl-0006ox-UN
	for ospf-wireless-design@megatron.ietf.org;
	Fri, 21 Jan 2005 15:54:41 -0500
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id PAA18284
	for <ospf-wireless-design@ietf.org>;
	Fri, 21 Jan 2005 15:54:40 -0500 (EST)
Received: from rtp-iport-1.cisco.com ([64.102.122.148])
	by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1Cs63h-0008Tl-46
	for ospf-wireless-design@ietf.org; Fri, 21 Jan 2005 16:11:11 -0500
Received: from rtp-core-1.cisco.com (64.102.124.12)
	by rtp-iport-1.cisco.com with ESMTP; 21 Jan 2005 16:02:03 -0500
X-BrightmailFiltered: true
X-Brightmail-Tracker: AAAAAA==
Received: from fruitpie.cisco.com (IDENT:mirapoint@fruitpie.cisco.com
	[64.102.16.27])
	by rtp-core-1.cisco.com (8.12.10/8.12.6) with ESMTP id j0LKs7W0028967
	for <ospf-wireless-design@ietf.org>;
	Fri, 21 Jan 2005 15:54:07 -0500 (EST)
Received: from [10.82.240.219] (rtp-vpn2-219.cisco.com [10.82.240.219])
	by fruitpie.cisco.com (MOS 3.4.6-GR) with ESMTP id BET52637;
	Fri, 21 Jan 2005 12:54:06 -0800 (PST)
Message-ID: <41F16BEE.3050903@cisco.com>
Date: Fri, 21 Jan 2005 15:54:06 -0500
From: Acee Lindem <acee@cisco.com>
User-Agent: Mozilla Thunderbird 0.9 (Windows/20041103)
X-Accept-Language: en-us, en
MIME-Version: 1.0
To: ospf-wireless-design@ietf.org
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 0.0 (/)
X-Scan-Signature: d17f825e43c9aed4fd65b7edddddec89
Content-Transfer-Encoding: 7bit
Subject: [Ospf-wireless-design] Limiting Flooding Optimization Options to
	the Current Proposals 
X-BeenThere: ospf-wireless-design@lists.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: OSPF Wireless Design Team  <ospf-wireless-design.lists.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <https://www1.ietf.org/mailman/private/ospf-wireless-design>
List-Post: <mailto:ospf-wireless-design@lists.ietf.org>
List-Help: <mailto:ospf-wireless-design-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=subscribe>
Sender: ospf-wireless-design-bounces@ietf.org
Errors-To: ospf-wireless-design-bounces@ietf.org
X-Spam-Score: 0.0 (/)
X-Scan-Signature: cf4fa59384e76e63313391b70cd0dd25
Content-Transfer-Encoding: 7bit

Now that we have at least a couple flooding optimizations proposals 
(depending
on how you count them) on the table. I'd like to propose that we limit 
ourselves to these.
This is not to say that the ones proposed cannot be tweaked. Any 
objections or anybody
ready to make an alternate submission? I think we need to do this in 
order to make progress.

Thanks,
Acee

_______________________________________________
Ospf-wireless-design mailing list
Ospf-wireless-design@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design


From ospf-wireless-design-bounces@ietf.org  Fri Jan 21 20:41:40 2005
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id UAA13719;
	Fri, 21 Jan 2005 20:41:40 -0500 (EST)
Received: from megatron.ietf.org ([132.151.6.71])
	by ietf-mx.ietf.org with esmtp (Exim 4.33)
	id 1CsAXV-0000Pb-CQ; Fri, 21 Jan 2005 20:58:13 -0500
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32)
	id 1CsAGK-0002FZ-He; Fri, 21 Jan 2005 20:40:28 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32) id 1CsAAh-0001BQ-8D
	for ospf-wireless-design@megatron.ietf.org;
	Fri, 21 Jan 2005 20:34:39 -0500
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id UAA13396
	for <ospf-wireless-design@ietf.org>;
	Fri, 21 Jan 2005 20:34:36 -0500 (EST)
Received: from blv-smtpout-01.boeing.com ([130.76.32.69])
	by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CsAQe-0000Gb-Qq
	for ospf-wireless-design@ietf.org; Fri, 21 Jan 2005 20:51:10 -0500
Received: from blv-av-01.boeing.com ([192.42.227.216])
	by blv-smtpout-01.boeing.com (8.9.2.MG.10092003/8.8.5-M2) with ESMTP id
	RAA07870; Fri, 21 Jan 2005 17:34:01 -0800 (PST)
Received: from xch-nwbh-01.nw.nos.boeing.com (localhost [127.0.0.1])
	by blv-av-01.boeing.com (8.11.3/8.11.3/MBS-AV-LDAP-01) with ESMTP id
	j0M1Y0U13745; Fri, 21 Jan 2005 17:34:00 -0800 (PST)
Received: from XCH-NW-27.nw.nos.boeing.com ([192.48.4.101]) by
	xch-nwbh-01.nw.nos.boeing.com with Microsoft SMTPSVC(6.0.3790.0); 
	Fri, 21 Jan 2005 17:33:51 -0800
X-MimeOLE: Produced By Microsoft Exchange V6.0.6603.0
content-class: urn:content-classes:message
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: quoted-printable
Subject: RE: [Ospf-wireless-design] Limiting Flooding Optimization Options
	tothe Current Proposals 
Date: Fri, 21 Jan 2005 17:33:50 -0800
Message-ID: <6938661A6EDA8A4EA8D1419BCE46F24C040609F2@xch-nw-27.nw.nos.boeing.com>
Thread-Topic: [Ospf-wireless-design] Limiting Flooding Optimization Options
	tothe Current Proposals 
Thread-Index: AcUAAwOCfcuHIiXQQuKNuCyGgeZiyQAHhXyA
From: "Henderson, Thomas R" <thomas.r.henderson@boeing.com>
To: "Acee Lindem" <acee@cisco.com>, <ospf-wireless-design@ietf.org>
X-OriginalArrivalTime: 22 Jan 2005 01:33:51.0265 (UTC)
	FILETIME=[6D4E1910:01C50022]
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 69a74e02bbee44ab4f8eafdbcedd94a1
Content-Transfer-Encoding: quoted-printable
X-BeenThere: ospf-wireless-design@lists.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: OSPF Wireless Design Team  <ospf-wireless-design.lists.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <https://www1.ietf.org/mailman/private/ospf-wireless-design>
List-Post: <mailto:ospf-wireless-design@lists.ietf.org>
List-Help: <mailto:ospf-wireless-design-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=subscribe>
Sender: ospf-wireless-design-bounces@ietf.org
Errors-To: ospf-wireless-design-bounces@ietf.org
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 9ed51c9d1356100bce94f1ae4ec616a9
Content-Transfer-Encoding: quoted-printable

Since I am not aware of another proposal that might be forthcoming, and =
the existing proposals seem to span the popular space for these =
algorithms, I support focusing on the draft-chandra and draft-ogier =
proposals. =20

At least, I can say from our end that we have been actively exploring =
the draft-chandra approach, and plan to next look at the draft-ogier =
approach carefully.

I am curious to ask the rest of the design team-- has anyone had a close =
look at our implementation of draft-chandra and the simulation =
environment?  Are people ready to have some discussion on this topic?  =
Although I think that more work remains to be done before forming =
conclusions, I'm starting to form some opinions.

Tom

> -----Original Message-----
> From: Acee Lindem [mailto:acee@cisco.com]=20
> Sent: Friday, January 21, 2005 12:54 PM
> To: ospf-wireless-design@ietf.org
> Subject: [Ospf-wireless-design] Limiting Flooding=20
> Optimization Options tothe Current Proposals=20
>=20
>=20
> Now that we have at least a couple flooding optimizations proposals=20
> (depending
> on how you count them) on the table. I'd like to propose that=20
> we limit=20
> ourselves to these.
> This is not to say that the ones proposed cannot be tweaked. Any=20
> objections or anybody
> ready to make an alternate submission? I think we need to do this in=20
> order to make progress.
>=20
> Thanks,
> Acee
>=20

_______________________________________________
Ospf-wireless-design mailing list
Ospf-wireless-design@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design


From ospf-wireless-design-bounces@ietf.org  Tue Jan 25 17:59:11 2005
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA22413;
	Tue, 25 Jan 2005 17:59:11 -0500 (EST)
Received: from megatron.ietf.org ([132.151.6.71])
	by ietf-mx.ietf.org with esmtp (Exim 4.33)
	id 1CtZvI-0005n7-5S; Tue, 25 Jan 2005 18:16:36 -0500
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32)
	id 1CtZca-0001iW-7W; Tue, 25 Jan 2005 17:57:16 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32) id 1CtZQ1-00089l-Oj
	for ospf-wireless-design@megatron.ietf.org;
	Tue, 25 Jan 2005 17:44:17 -0500
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id RAA21608
	for <ospf-wireless-design@ietf.org>;
	Tue, 25 Jan 2005 17:44:15 -0500 (EST)
Received: from stl-smtpout-01.boeing.com ([130.76.96.56])
	by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CtZgp-0005OF-0W
	for ospf-wireless-design@ietf.org; Tue, 25 Jan 2005 18:01:39 -0500
Received: from blv-av-01.boeing.com ([192.42.227.216])
	by stl-smtpout-01.boeing.com (8.9.2.MG.10092003/8.8.5-M2) with ESMTP id
	QAA09039; Tue, 25 Jan 2005 16:43:41 -0600 (CST)
Received: from xch-nwbh-01.nw.nos.boeing.com (localhost [127.0.0.1])
	by blv-av-01.boeing.com (8.11.3/8.11.3/MBS-AV-LDAP-01) with ESMTP id
	j0PMheU18579; Tue, 25 Jan 2005 14:43:40 -0800 (PST)
Received: from XCH-NW-28.nw.nos.boeing.com ([192.48.4.102]) by
	xch-nwbh-01.nw.nos.boeing.com with Microsoft SMTPSVC(6.0.3790.0); 
	Tue, 25 Jan 2005 14:43:39 -0800
X-MimeOLE: Produced By Microsoft Exchange V6.0.6603.0
content-class: urn:content-classes:message
MIME-Version: 1.0
Content-Type: text/plain;
	charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
Subject: RE: FW: [Ospf-wireless-design] Tao Lin paper
Date: Tue, 25 Jan 2005 14:43:39 -0800
Message-ID: <3BFEACE361F5BF429DD1DA593E3A7C0904CC6ABB@xch-nw-28.nw.nos.boeing.com>
Thread-Topic: FW: [Ospf-wireless-design] Tao Lin paper
Thread-Index: AcTpDJh+zvyrq/vKSJaSFhzhhCI46AaHVP/g
From: "Spagnolo, Phillip A" <phillip.a.spagnolo@boeing.com>
To: "Richard Ogier" <rich.ogier@earthlink.net>
X-OriginalArrivalTime: 25 Jan 2005 22:43:39.0553 (UTC)
	FILETIME=[504D8110:01C5032F]
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 963faf56c3a5b6715f0b71b66181e01a
Content-Transfer-Encoding: quoted-printable
Cc: ospf-wireless-design@ietf.org
X-BeenThere: ospf-wireless-design@lists.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: OSPF Wireless Design Team  <ospf-wireless-design.lists.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <https://www1.ietf.org/mailman/private/ospf-wireless-design>
List-Post: <mailto:ospf-wireless-design@lists.ietf.org>
List-Help: <mailto:ospf-wireless-design-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=subscribe>
Sender: ospf-wireless-design-bounces@ietf.org
Errors-To: ospf-wireless-design-bounces@ietf.org
X-Spam-Score: 0.0 (/)
X-Scan-Signature: 43317e64100dd4d87214c51822b582d1
Content-Transfer-Encoding: quoted-printable

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

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 =3D =
RtrPri.


2nd Example edges=3DRtrPri.
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? =20
 =20
Thanks,
Phil


> -----Original Message-----
> From: Richard Ogier [mailto:rich.ogier@earthlink.net]=20
> Sent: Thursday, December 23, 2004 8:02 AM
> To: Abhay Roy
> Cc: ospf-wireless-design@ietf.org
> Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper
>=20
>=20
> Hi Roy,
>=20
> Here is an example where MPRs result in 3 times
> as many transmissions as a SI-CDS.
>=20
>     5
>  /  |  \
> 1-- 6-- 3
> |   |   |
> 2-- 7-- 4
>  \  | /
>     8
>=20
> 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.
>=20
> 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.
>=20
> 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.
>=20
> Minimal CDS Algorithm
>=20
> 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.
>=20
> Happy Holidays!
> Richard
>=20
>=20
> Abhay Roy wrote:
>=20
> > Hi Tao,
> >
> > It's good to hear from you first hand on this topic. What may be=20
> > useful to further this discussion is an example or two,=20
> where we can=20
> > demostrate that the improved algorithm comes up with a=20
> smaller set. In=20
> > my mind, it's still very fuzzy how this happens ;)
> >
> > Also, since we are going to be doing simulations under Tom's GTNetS=20
> > 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" <mchandra@cisco.com> 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
> >>>
> >>
> >>
> >>
> >>=20
> ______________________________________________________________________
> >> Post your free ad now! http://personals.yahoo.ca
> >>
> >> _______________________________________________
> >> Ospf-wireless-design mailing list
> >> Ospf-wireless-design@lists.ietf.org
> >> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> >>
> >
> > _______________________________________________
> > Ospf-wireless-design mailing list
> > Ospf-wireless-design@lists.ietf.org
> > https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
> >
>=20
>=20
>=20
> _______________________________________________
> Ospf-wireless-design mailing list
> Ospf-wireless-design@lists.ietf.org
> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
>=20

_______________________________________________
Ospf-wireless-design mailing list
Ospf-wireless-design@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design


From ospf-wireless-design-bounces@ietf.org  Tue Jan 25 18:33:09 2005
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA25693;
	Tue, 25 Jan 2005 18:33:09 -0500 (EST)
Received: from megatron.ietf.org ([132.151.6.71])
	by ietf-mx.ietf.org with esmtp (Exim 4.33)
	id 1CtaSA-0006kc-FC; Tue, 25 Jan 2005 18:50:34 -0500
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32)
	id 1Cta2T-0007cL-I7; Tue, 25 Jan 2005 18:24:01 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32) id 1CtZy8-0005N5-Q3
	for ospf-wireless-design@megatron.ietf.org;
	Tue, 25 Jan 2005 18:19:32 -0500
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA24552
	for <ospf-wireless-design@ietf.org>;
	Tue, 25 Jan 2005 18:19:29 -0500 (EST)
Received: from pop-a065d10.pas.sa.earthlink.net ([207.217.121.251])
	by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CtaEv-0006KV-3e
	for ospf-wireless-design@ietf.org; Tue, 25 Jan 2005 18:36:54 -0500
Received: from dialup-4.243.134.144.dial1.sanfrancisco1.level3.net
	([4.243.134.144] helo=earthlink.net)
	by pop-a065d10.pas.sa.earthlink.net with esmtp (Exim 3.33 #1)
	id 1CtZxs-0002BF-00; Tue, 25 Jan 2005 15:19:16 -0800
Message-ID: <41F6D3F4.4090202@earthlink.net>
Date: Tue, 25 Jan 2005 15:19:16 -0800
From: Richard Ogier <rich.ogier@earthlink.net>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US;
	rv:0.9.4) Gecko/20011128 Netscape6/6.2.1 (emach0202)
X-Accept-Language: en-us
MIME-Version: 1.0
To: "Spagnolo, Phillip A" <phillip.a.spagnolo@boeing.com>
Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper
References: <3BFEACE361F5BF429DD1DA593E3A7C0904CC6ABB@xch-nw-28.nw.nos.boeing.com>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 2.9 (++)
X-Scan-Signature: e367d58950869b6582535ddf5a673488
Content-Transfer-Encoding: 7bit
Cc: ospf-wireless-design@ietf.org
X-BeenThere: ospf-wireless-design@lists.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: OSPF Wireless Design Team  <ospf-wireless-design.lists.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <https://www1.ietf.org/mailman/private/ospf-wireless-design>
List-Post: <mailto:ospf-wireless-design@lists.ietf.org>
List-Help: <mailto:ospf-wireless-design-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=subscribe>
Sender: ospf-wireless-design-bounces@ietf.org
Errors-To: ospf-wireless-design-bounces@ietf.org
X-Spam-Score: 2.9 (++)
X-Scan-Signature: bcd240e64c427d3d3617cfc704e7fd7f
Content-Transfer-Encoding: 7bit

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

Spagnolo, Phillip A wrote:

>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:rich.ogier@earthlink.net] 
>>Sent: Thursday, December 23, 2004 8:02 AM
>>To: Abhay Roy
>>Cc: ospf-wireless-design@ietf.org
>>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" <mchandra@cisco.com> 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
>>>>Ospf-wireless-design@lists.ietf.org
>>>>https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
>>>>
>>>_______________________________________________
>>>Ospf-wireless-design mailing list
>>>Ospf-wireless-design@lists.ietf.org
>>>https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
>>>
>>
>>
>>_______________________________________________
>>Ospf-wireless-design mailing list
>>Ospf-wireless-design@lists.ietf.org
>>https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
>>
>



_______________________________________________
Ospf-wireless-design mailing list
Ospf-wireless-design@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design


From ospf-wireless-design-bounces@ietf.org  Tue Jan 25 18:36:09 2005
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA26012;
	Tue, 25 Jan 2005 18:36:09 -0500 (EST)
Received: from megatron.ietf.org ([132.151.6.71])
	by ietf-mx.ietf.org with esmtp (Exim 4.33)
	id 1CtaV3-0006qr-Od; Tue, 25 Jan 2005 18:53:34 -0500
Received: from localhost.localdomain ([127.0.0.1] helo=megatron.ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32)
	id 1Cta2d-0007ns-MM; Tue, 25 Jan 2005 18:24:11 -0500
Received: from odin.ietf.org ([132.151.1.176] helo=ietf.org)
	by megatron.ietf.org with esmtp (Exim 4.32) id 1Cta1e-0007Ig-1V
	for ospf-wireless-design@megatron.ietf.org;
	Tue, 25 Jan 2005 18:23:11 -0500
Received: from ietf-mx.ietf.org (ietf-mx.ietf.org [132.151.6.1])
	by ietf.org (8.9.1a/8.9.1a) with ESMTP id SAA24897
	for <ospf-wireless-design@ietf.org>;
	Tue, 25 Jan 2005 18:23:07 -0500 (EST)
Received: from pop-a065d10.pas.sa.earthlink.net ([207.217.121.251])
	by ietf-mx.ietf.org with esmtp (Exim 4.33) id 1CtaIM-0006Rt-TD
	for ospf-wireless-design@ietf.org; Tue, 25 Jan 2005 18:40:32 -0500
Received: from dialup-4.243.134.144.dial1.sanfrancisco1.level3.net
	([4.243.134.144] helo=earthlink.net)
	by pop-a065d10.pas.sa.earthlink.net with esmtp (Exim 3.33 #1)
	id 1Cta1T-0003CZ-00; Tue, 25 Jan 2005 15:22:59 -0800
Message-ID: <41F6D4D3.7040606@earthlink.net>
Date: Tue, 25 Jan 2005 15:22:59 -0800
From: Richard Ogier <rich.ogier@earthlink.net>
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US;
	rv:0.9.4) Gecko/20011128 Netscape6/6.2.1 (emach0202)
X-Accept-Language: en-us
MIME-Version: 1.0
To: "Spagnolo, Phillip A" <phillip.a.spagnolo@boeing.com>
Subject: Re: FW: [Ospf-wireless-design] Tao Lin paper
References: <3BFEACE361F5BF429DD1DA593E3A7C0904CC6ABB@xch-nw-28.nw.nos.boeing.com>
	<41F6D3F4.4090202@earthlink.net>
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit
X-Spam-Score: 2.9 (++)
X-Scan-Signature: 72dbfff5c6b8ad2b1b727c13be042129
Content-Transfer-Encoding: 7bit
Cc: ospf-wireless-design@ietf.org
X-BeenThere: ospf-wireless-design@lists.ietf.org
X-Mailman-Version: 2.1.5
Precedence: list
List-Id: OSPF Wireless Design Team  <ospf-wireless-design.lists.ietf.org>
List-Unsubscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=unsubscribe>
List-Archive: <https://www1.ietf.org/mailman/private/ospf-wireless-design>
List-Post: <mailto:ospf-wireless-design@lists.ietf.org>
List-Help: <mailto:ospf-wireless-design-request@lists.ietf.org?subject=help>
List-Subscribe: <https://www1.ietf.org/mailman/listinfo/ospf-wireless-design>, 
	<mailto:ospf-wireless-design-request@lists.ietf.org?subject=subscribe>
Sender: ospf-wireless-design-bounces@ietf.org
Errors-To: ospf-wireless-design-bounces@ietf.org
X-Spam-Score: 2.9 (++)
X-Scan-Signature: 1e467ff145ef391eb7b594ef62b8301f
Content-Transfer-Encoding: 7bit

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:

> 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
>
> Spagnolo, Phillip A wrote:
>
>> 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:rich.ogier@earthlink.net] Sent: 
>>> Thursday, December 23, 2004 8:02 AM
>>> To: Abhay Roy
>>> Cc: ospf-wireless-design@ietf.org
>>> 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" <mchandra@cisco.com> 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
>>>>> Ospf-wireless-design@lists.ietf.org
>>>>> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
>>>>>
>>>> _______________________________________________
>>>> Ospf-wireless-design mailing list
>>>> Ospf-wireless-design@lists.ietf.org
>>>> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
>>>>
>>>
>>>
>>> _______________________________________________
>>> Ospf-wireless-design mailing list
>>> Ospf-wireless-design@lists.ietf.org
>>> https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
>>>
>>
>
>



_______________________________________________
Ospf-wireless-design mailing list
Ospf-wireless-design@lists.ietf.org
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design


