Effects of Interference on Wireless Mesh Networks: Pathologies and a
Preliminary Solution Yi Li, Lili Qiu and Yin Zhang (UT Austin),
Ratul Mahajan (Microsoft Research), and Zifei Zhong, Gaurav
Deshpande and Eric Rozner (UT Austin)

Summary: The paper presented some routing and path selection pathologies for
wireless networks.


1. He showed that a BAD,GOOD  topology is better than GOOD,BAD topology.
2. ETX ignore sender side interference
3. Usually path cost is computed simply as the sum of cost of links on
it, which is not always true.

They presented a new scheme that addresses these pathologies. They use
a model based flow rate computation.  They capture interference
dependencies using an approximate conflict graph --- in this graph,
the cliques cannot talk at a time.  Further the rates are adapted to
address pathology 1.

Q & A.

Q: You are coupling routing and flow control.  This might work only
if we know apriory what rate people want to send.

A: There is evidence that there is a lot of temporal stability in
rates, especially for aggregate traffic.

Q: Is it distributed.

A:  It is distributed in the sense the the ETX/OSPF sense, but the
question is that how big a network we can support for the state

Q: How would the Clique constraint in your work relate to something like the
Maximal Independent set constraints. 

A: We have models now that correct for that.

Q: Finding maximal independent sets is NP-complete.

A: We have an "engineering" solution that as long as we find enough
cliques, and that seems to be sufficient for most cases.

Q: How do you compute the cliques?
A: The presenter explained the heuristics, that are detailed in the paper.

Q: What is the efficiency loss when you use such heuristics.

A: The efficiency loss from imperfect max scheduling comes out to
be about 15%. 

Q: What do the numbers look for TCP.

A: We have not run TCP experiments.  But, the aggregation of TCP means that it
tries to exceed the cliff and backs off, loosing some of the efficiency gains. 
Results showed about 200% improvement.