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

[Tao Lin <[e-mail]>]

Hi All,

I didn't register in the OSPF-wireless-design email
list so I think I missed previous discussions.  Based
on Madhavi's email, I would like to share some of my
quick thought.

The willingness is the same in that paper and the MPR
sets are minimized since MPR_Coverage=1.

Finding a small CDS for a connected network is an NP
problem.  Therefore, people proposed approximation
algorithms to find small CDSs.  Generally, the more
complicated the algorithm is, the smaller size of CDS
it can get.  The MPR selection algorithm in OLSR
requires O(n), here n is the node degree.  And the
algorithm I proposed at least requires O(n^2).  So
this causes the difference.  If the number of
neighbors is a huge number, then the MPR algorithm can
run faster than O(n^2) algorithms.  However, the size
of a connected wireless network over one wireless
channel is limited.  So there is no big difference
between the algorithm in my paper and the MPR
algorithm introduced by OLSR.

Source dependent CDS algorithms usually need to
exchange some kind of decisions so that all
neighboring nodes will decide to be in the final CDS
or not.  For example, in the MPR algorithm proposed by
OLSR, nodes select MPR sets first and exchange their
MPR sets with neighbors.  After that, a node becomes a
CDS node if its MPRS is non-empty.  So, there is a
delay in this decision making procedure.  On the other
hand, those source independent CDS algorithms in which
nodes make decisions by themselves do not have this
delay.  Thus, when the network topology changes, a
routing protocol running over a source dependent
algorithm requires longer converge time than the one
running over a source independent algorithm.

Corret me if what I said is wrong and welcome more
discussions.

  Tao

 --- "Henderson, Thomas R"
<[e-mail]> wrote: 
> I have forwarded this to Tao Lin, who has agreed to
> participate
> in our discussions on this topic.  
> 
> -----Original Message-----
> From: Madhavi W. Chandra [mailto:[e-mail]]
> Sent: Monday, December 20, 2004 10:21 AM
> To: [e-mail]
> Subject: [Ospf-wireless-design] Tao Lin paper
>
> Hi All,
> 
> I'm hoping one of you can shed some light on the Tao
> Lin paper,
> section III-D.
> 
> In this paper, I'm assuming that the Willingness
> parameter for
> MPRs is the same, so it doesn't come into play in
> the MPR
> computation.  And as the paper says, MPR_Coverage=1,
> so there are
> no redundant relays in the set.
> 
> But, why is the 'modified' OLSR set so much smaller
> than the 
> MPR set?   Put another way, which nodes would be
> included in the
> MPR set that wouldn't be included in the
> modified-OLSR set, especially
> since the MPR set does an overall pruning at the end
> of its 
> selection algorithm.
> 
> Thanks!
> -Madhavi
> 
> 
> 
> _______________________________________________
> Ospf-wireless-design mailing list
> [e-mail]
>
https://www1.ietf.org/mailman/listinfo/ospf-wireless-design
>  

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

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