Subject: [manet] (no subject)

From: Kan Cai <[email-masked]>
Date: Thu, 26 Feb 2004 14:02:31 -0800 (PST)

Hi, all:

> Now, the *efficient* CDS used in the INRIA report is defined as follows.
> A node decides that it is in the connected dominating set if:
> Rule 1: the node has a smaller ID than all its neighbors,
> Rule 2: or it is an MPR of its neighbor with the smallest ID.

> This is certainly an efficient way to make the forwarding rule
> independent of the previous hop, but it does not provide
> min-hop paths (using only CDS nodes as intermediate nodes)
> and therefore is probably not very useful for route discovery
> in AODV.  Maybe I am wrong about this.

> Also, the INRIA report considers two methods for selecting MPRs:
> the greedy algorithm (as in OLSR), and the min ID algorithm.
> The min ID algorithm allows nodes to select themselves
> as MPRs (similar to TBRPF), and therefore has some advantages,
> although it results in more transmissions (and a larger CDS).

> In summary, maybe a combination of the methods discussed above
> is a good solution, but I am still looking for a better solution.

Forgive me if I am off topic. I read INRIA report, however I am just
wondering why constructing a CDS has to deal with MPR. Using unit-disk
graph can easily choose dominators according to some metrics such as node
ID or node degree. And then we can connect these dominators together so
that they can build up a CDS across the network. It has been theoretically
proven that you can set up such a CDS with an linear approximation ratio
to the optimal graph (see the message-optimal cds paper in mobihoc02).

My simulation based on Glomosim shows pretty good result, although I
mainly focus on unicast in the reduced backbone. However, as long as the
backbone connectivity is good and can cover all the nodes in the network,
broadcast should be good too, or is it?

best regards,
ken

_______________________________________________
manet mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/manet

---

From: "Tao Lin" <[email-masked]>
Date: Thu, 26 Feb 2004 17:18:28 -0500

Hi all,

I have the same feeling too.  There are two ways to choose CDS nodes, either
nodes chosen by neighbors (like MPR in OLSR) or chosen by themselves (such
as many other CDS algorithms proposed in the literature).  In other words, a
CDS does not have to be associated with MPRs.  Therefore, I would suggest,
as Richard pointed out before, we should keep our options open and try to
compare different approaches.

Thanks,
 Tao Lin
 ECE Dept.
 Virginia Tech

---

From: Richard Ogier <[email-masked]>
Date: Thu, 26 Feb 2004 16:06:27 -0800

Yes, I agree that you do not need MPRs to compute a CDS.
The advantage of MPRs is that they are an efficient way to
flood along min-hop paths from the originator.
A CDS does not flood along min-hop paths from every possible
originator, unless it is a very large CDS.
Some protocols (like OLSR) work better with MPRs.
But MPRs are not the best choice in all cases. So is there
a single solution that works well for all applications?
Or maybe we should use MPRs for some applications and
only a CDS (not based on MPRs) for other applications.
As Tao says, we should keep our options open and compare
different approaches.

While I'm here, I want to mention another benefit of using
min ID instead of the greedy algorithm (as in OLSR)
for computing MPRs. The greedy algorithm results in fewer
MPRs, but these MPRs are close to the boundary of the
reception range, and are therefore more likely to be
unstable due to mobility. Using min ID results in more MPRs,
but they are more likely to be stable.  Stability of MPRs is
important for a number of reasons that I won't go into now
(but clearly it is more likely for flooded packets to be
lost if MPRs are changing during flooding).

Regards,
Richard

---

From: "Tao Lin" <[email-masked]>
Date: Thu, 26 Feb 2004 19:48:32 -0500

Besides Richard's comments, another issue I would like to point out  is that
using MPRs as CDS nodes may result in increasing loads for MPRs nodes.
Since in OLSR, MPRs nodes have special roles in forwarding control messages
AND forwarding user messages.  It is highly possible that these nodes will
have more transmission and receiving events that other nodes, which may
result in higher possibility of packet collisions and more power
consumptions in these nodes, especially when the network load is heavy.  On
the contrary, a CDS that does not depend on those nodes that are chosen to
forward user application packets might avoid this potential heavier load
problem.  I think this topic might be of interest.

Thanks,

  Tao Lin
  ECE Dept.
  Virginia Tech

---

From: Justin Lipman <[email-masked]>
Date: Fri, 27 Feb 2004 12:53:44 +1100

Hi Richard,

> lost if MPRs are changing during flooding).

Really very good point. Sorry, I dont mean to push my own work, but Utility 
Based flooding (UBF) allows this to be achieved quite easily as well as 
including where necessary any other factors such as a node's internal battery 
power etc.

Kind regards,
Justin

-- 
Research Associate
Smart Internet Technology Cooperative Research Centre
http://www.titr.uow.edu.au/~justin

---

From: Kan Cai <[email-masked]>
Date: Thu, 26 Feb 2004 18:23:41 -0800 (PST)

> originator, unless it is a very large CDS.

I agree that MPR is flooding along min-hop paths from the originator. But
I am not sure how much this advantage it can get compared to CDS. The only
extra transmission CDS requires is to ask the src node to forward the
message to its dominator, thats it. Then the dominator handles broadcasts
in the network. So if I am right,  the real advantage of MPR on this
aspect is just one less transmission.

Another issue here is in CDS, only dominators need to rebroadcast if
necessary, while MPR perhaps requires all MPR nodes need to do this.
Certainly, in MPR CDS, you can ask the nodes selected by rule 1) to do the
broadcast.

Correct me if I am wrong, thanks.

regards,
ken