Subject: RE: [Ospf-wireless-design] notes from our recent IETF meeting

From: "Henderson, Thomas R" <[email-masked]>
Date: Thu, 18 Nov 2004 19:31:51 -0800

Richard, thanks for your feedback.  

> -----Original Message-----
> From: Richard Ogier [mailto:[email-masked]]
> Sent: Thursday, November 18, 2004 3:51 PM
> To: Henderson, Thomas R
> Cc: [email-masked]; [email-masked]; Emmanuel Baccelli;
> [email-masked]
> Subject: Re: [Ospf-wireless-design] notes from our recent IETF meeting
> 
> >
> Perhaps a better reference for relevant CDS algorithms is the 
> following, 
> which also describes a few (not necessarily new) CDS 
> algorithms that do 
> not require computing MPRs:
> 
>   C. Adjih, P. Jacquet, and L. Viennot. "Computing connected
>   dominated sets with multipoint relays", INRIA research
>   report No. 4597, October 2002.
> 
> I assume you are talking about Tao Lin's paper, reference [9] of
> http://www.ietf.org/internet-drafts/draft-spagnolo-manet-ospf-
> design-00.txt

Yes.

> It is not clear from the description in the paper whether the CDS is 
> source-independent (in the description, the choice seems to depend on 
> the "sender node"). 

I think that the section in that paper is poorly worded (there is a typo
s/j/k in the description).  It probably should read something like
"For each potential sender node, when a node i...".

Anyway, the way we interpreted it and implemented it, the decision
on whether a node is a CDS is made based on the two-hop info only,
and not on the source of the LSA.

> If it is indeed source-indepenent, then 
> it appears 
> to be the same as one of the CDS algorithms in the INRIA 
> report, except 
> that maximizing node degree is used as an additional 
> objective 

Yes.

> (which I 
> found not to work well, since it favors nodes that are close to the 
> center of a given cluster, and also results in a less stable CDS). A 
> similar CDS algorithm can be found in the following paper:  
> J. Wu and H. 
> Li. "A Dominating-Set-Based Routing Scheme in Ad Hoc Wireless 
> Networks", 
> Telecommunication Systems, Vol. 18, pp. 31-36, 2001.

My recollection is that the variation on Wu/Li that Lin introduced
was in fact this maximizing node degree step, with the argument
being that it results in smaller CDS.  But it is intuitive that
the smaller CDS might be less stable.

We did not try to make the Lin CDS more stable in our previous
work by delaying updates (we immediately changed the CDS if the 
neighbor information changed).

> 
> I plan to describe and present simulation results for a few CDS 
> algorithms based on 2-hop neighbor information, including two 
> from the 
> above INRIA report and some improved variations.

That would be good.  We are preparing some simulation code as well
and would like to include the best candidate algorithms.

> 
> Another issue is whether existing CDS nodes should remain in the CDS 
> whenever possible (to maximize stability), just as a DR in 
> OSPF remains 
> a DR whenever possible. This is especially important if 
> adjacencies are 
> formed only between CDS nodes and their neighbors (so that a new CDS 
> node must form adjacencies with all of its neighbors).

Stability is one of the properties that we would like to consider.

Tom

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