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

From: "Henderson, Thomas R" <[email-masked]>
Date: Thu, 13 Jan 2005 21:30:18 -0800

> -----Original Message-----
> From: Richard Ogier [mailto:[email-masked]]
> Sent: Wednesday, January 12, 2005 9:38 AM
> To: Tao Lin
> Cc: [email-masked]
> 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
    }
  }  
}

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

---

From: Richard Ogier <[email-masked]>
Date: Fri, 14 Jan 2005 09:07:50 -0800

Please see my comment below.

>    if such neighbor exists with larger degree, or with equal degree and larger ID {
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