Open Collections

UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Interference mitigation and detection in wifi networks under congestion Cai, Kan 2015

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata


24-ubc_2015_september_cai_kan.pdf [ 1.4MB ]
JSON: 24-1.0166312.json
JSON-LD: 24-1.0166312-ld.json
RDF/XML (Pretty): 24-1.0166312-rdf.xml
RDF/JSON: 24-1.0166312-rdf.json
Turtle: 24-1.0166312-turtle.txt
N-Triples: 24-1.0166312-rdf-ntriples.txt
Original Record: 24-1.0166312-source.json
Full Text

Full Text

Interference Mitigation and Detection in WiFiNetworks Under CongestionbyKan CaiB. Eng., Northeastern University, 1998M. Sc., The University of British Columbia, 2004A THESIS SUBMITTED IN PARTIAL FULFILLMENTOF THE REQUIREMENTS FOR THE DEGREE OFDoctor of PhilosophyinTHE FACULTY OF GRADUATE AND POSTDOCTORALSTUDIES(Computer Science)The University of British Columbia(Vancouver)June 2015c© Kan Cai, 2015AbstractIn IEEE 802.11, nodes regulate access to the airspace they share in a decentral-ized fashion using CSMA/CA. The goal of this approach is to share the commonairspace fairly and efficiently without requiring centralized channel administrationor direct coordination among peer nodes. However, it is well known that stronginterference, as consequence of this de-centralized coordination scheme, can leadto extremely unfair network bandwidth allocation between competing devices.Interference detection and mitigation has posed great challenges. The cause ofinterference is complicated, involving many networking factors such as topologyand traffic, and the interference relationship changes all the time. This thesisaddresses these challenges by proposing a throttling based interference mitigationsystem (Shaper) and an online passive interference detection system (VOID). Themain contribution of this thesis is to point out the correlated relationship betweeninterference and congestion.First, this thesis provides a more thorough analysis on the impact of nodetopology, traffic type and signal strength on wireless performance. We came upwith 9 UDP models and 10 TCP models just for two competing flow scenarios.The outcome of wireless interference can get harder to predict, however, as weintroduce more factors into the interference model such as more competing nodes,sending rate, signal propagation model, etc.On the other hand, this thesis identifies the immediate cause to the unfair band-width distribution under interference: 802.11 network congestion. We observedand explained that all competing devices are able to perform well regardless ofiitopology or traffic class, as long as there is sufficiently more bandwidth thanthe aggregate throughput demands. Therefore, we propose to trade the aggre-gate throughput to mitigate the impact of interference and prove its effectivenessthrough simulation and emulation.Finally, the key to successful addressing the interference is an accurate and fastinterference detection mechanism and this thesis proposes such a system calledVOID. It deploys the correlation between congestion and interference to inferthe interference relationship from the ip-layer throughput variations. It is fast,accurate and more importantly, very easy to deploy in existing WiFi networks.iiiPrefaceI conducted my research work presented in this thesis in collaboration with myPh.D. supervisor Michael J. Feeley. The thesis content is mostly based on thefollowing four published papers, in which I am the primary contributor on boththe design and evaluation:• Kan Cai and Michael J. Feeley and Brendan Cully and Sharath J. George.Understanding Performance for Two 802.11 Competing Flows. In Proceed-ings of the 4th IEEE International Conference on Mobile Adhoc and SensorSystems (MASS). Pages 1-11. 2007.• Kan Cai and Michael Blackstock and Reza Lotun and Michael J. Feeleyand Charles Krasic and Junfang Wang. Wireless unfairness: alleviate MACcongestion first! in Proceedings of the 2nd ACM Workshop on WirelessNetwork Testbeds, Experimental Evaluation and Characterization (WIN-TECH). Pages 43-50. 2007.• Kan Cai and Junfang Wang and Reza Lotun and Michael J. Feeley andMichael Blackstock and Charles Krasic. A wired router can eliminate 802.11unfairness, but it’s hard. In Proceedings of the 9th Workshop on MobileComputing Systems and Applications (HotMobile). Pages 49-54. 2008.• Kan Cai and Michael Blackstock and Michael J. Feeley and Charles Krasic.Non-intrusive, dynamic interference detection for 802.11 networks. In Pro-ceedings of the 9th ACM SIGCOMM Conference on Internet Measurement(IMC). Pages 377-283. 2009.ivMuch of the original text of the above publications has transitioned into thisthesis, and therefore some of the sentences and paragraphs were co-authored bythe collaborators listed above. Chapter 4 also presents our recent evaluation resultson interference detection in live networks, which has not yet been published.vTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiGlossary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xiiiAcknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xvi1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Issues: Wireless Interference and Unfairness . . . . . . . . . . . . 11.2 Challenges . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.4 Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.5 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . 92 Interference Impact Analysis . . . . . . . . . . . . . . . . . . . . . . 112.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122.2 Modelling Methodology . . . . . . . . . . . . . . . . . . . . . . 15vi2.2.1 Model Parameters . . . . . . . . . . . . . . . . . . . . . . 152.2.2 Performance Characteristics . . . . . . . . . . . . . . . . 172.2.3 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . 172.3 802.11g Models . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.3.1 UDP Models . . . . . . . . . . . . . . . . . . . . . . . . . 182.3.2 TCP Models . . . . . . . . . . . . . . . . . . . . . . . . . 242.4 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272.4.1 Example Scenarios . . . . . . . . . . . . . . . . . . . . . 292.4.2 Relationship to UDP/TCP Models . . . . . . . . . . . . . . 292.4.3 Simulation . . . . . . . . . . . . . . . . . . . . . . . . . . 302.4.4 Testbed Experiments . . . . . . . . . . . . . . . . . . . . 342.4.5 Sensing Range . . . . . . . . . . . . . . . . . . . . . . . 402.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413 Achieve Fairness by Congestion Reduction . . . . . . . . . . . . . . 423.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433.1.1 Motivation: A Cross-Layer Solution to Unfairness . . . . . 443.1.2 Contributions . . . . . . . . . . . . . . . . . . . . . . . . 453.2 Proposed Solution . . . . . . . . . . . . . . . . . . . . . . . . . . 463.2.1 Assumptions . . . . . . . . . . . . . . . . . . . . . . . . 463.2.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . 463.2.3 The Details: A Two-Component Scheme . . . . . . . . . . 473.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483.3.1 Testbed and Traffic Set-up . . . . . . . . . . . . . . . . . 483.3.2 The Topologies . . . . . . . . . . . . . . . . . . . . . . . 493.3.3 Effectiveness of Shaper . . . . . . . . . . . . . . . . . . . 503.3.4 Impacts of Throttling . . . . . . . . . . . . . . . . . . . . 533.3.5 Impacts of Fair Queuing . . . . . . . . . . . . . . . . . . 533.3.6 Prototype Implementation . . . . . . . . . . . . . . . . . 563.3.7 The Trade-Offs . . . . . . . . . . . . . . . . . . . . . . . 583.4 Challenge: Interference Detection . . . . . . . . . . . . . . . . . 60vii3.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614 Passive Interference Detection Using Online Traffic . . . . . . . . . 634.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644.2 Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664.2.1 Interference Patterns Under Congestion . . . . . . . . . . 674.2.2 Statistical Methods . . . . . . . . . . . . . . . . . . . . . 684.3 Limitations of VOID . . . . . . . . . . . . . . . . . . . . . . . . . 714.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . 734.5 Evaluation in Emulab Testbed . . . . . . . . . . . . . . . . . . . 744.5.1 Emulab Experiment Settings . . . . . . . . . . . . . . . . 744.5.2 Testbed Experiments . . . . . . . . . . . . . . . . . . . . 764.6 Evaluation in Live UBC WiFi Networks . . . . . . . . . . . . . . 814.6.1 False Positives . . . . . . . . . . . . . . . . . . . . . . . 864.6.2 False Negatives . . . . . . . . . . . . . . . . . . . . . . . 914.6.3 Discussion on Trade-Offs . . . . . . . . . . . . . . . . . . 974.7 Interference in Live Networks . . . . . . . . . . . . . . . . . . . . 994.7.1 Interference Hourly Trend . . . . . . . . . . . . . . . . . 1004.7.2 Interference Map . . . . . . . . . . . . . . . . . . . . . . 1034.7.3 Interference Groups and Duration . . . . . . . . . . . . . 1034.7.4 Traffic Burstiness and Class . . . . . . . . . . . . . . . . 1044.7.5 Scalability . . . . . . . . . . . . . . . . . . . . . . . . . . 1054.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1075 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1085.1 Interference Analysis . . . . . . . . . . . . . . . . . . . . . . . . 1085.2 Interference Mitigation Approaches . . . . . . . . . . . . . . . . 1105.3 Interference Correlation . . . . . . . . . . . . . . . . . . . . . . . 1125.4 Recent WiFi Interference Research Work . . . . . . . . . . . . . . 1145.4.1 Interference Analysis . . . . . . . . . . . . . . . . . . . . 1145.4.2 Interference Mitigation . . . . . . . . . . . . . . . . . . . 115viii6 Conclusion and Future Work . . . . . . . . . . . . . . . . . . . . . . 1196.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1196.1.1 Contribution . . . . . . . . . . . . . . . . . . . . . . . . . 1216.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124ixList of TablesTable 4.1 An Example Showing that Correlation Coefficient is Ineffec-tive in Detecting Interferers for a Victim Node in Many-InterfererScenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69Table 4.2 Results of Hidden-Terminal Topology . . . . . . . . . . . . . 77Table 4.3 Results of Exposed-Terminal Topology . . . . . . . . . . . . . 77Table 4.4 MLR Coefficients β for Flow 1 . . . . . . . . . . . . . . . . . 78Table 4.5 A Step-by-Step Illustration of the Forward Selection Process. . 79Table 4.6 False-Negative Analysis on a Testbed in Highrise . . . . . . . . 91Table 4.7 False-Negative Analysis in Live Networks . . . . . . . . . . . 96xList of FiguresFigure 1.1 Two Problematic Topologies . . . . . . . . . . . . . . . . . . 3Figure 2.1 Two Competing Flows . . . . . . . . . . . . . . . . . . . . . 14Figure 2.2 Models for UDP Fows . . . . . . . . . . . . . . . . . . . . . . 20Figure 2.3 Legend for Models . . . . . . . . . . . . . . . . . . . . . . . 20Figure 2.4 Models for TCP Flows . . . . . . . . . . . . . . . . . . . . . 24Figure 2.5 Model Transition in Two Scenarios . . . . . . . . . . . . . . . 28Figure 2.6 UDP Performance in Simulations . . . . . . . . . . . . . . . . 32Figure 2.7 TCP Performance in Simulations . . . . . . . . . . . . . . . . 33Figure 2.8 Performance of Snapshots . . . . . . . . . . . . . . . . . . . 37Figure 2.9 State Transition Experiment . . . . . . . . . . . . . . . . . . 39Figure 3.1 The Effectiveness of Shaper . . . . . . . . . . . . . . . . . . 51Figure 3.2 The Impact of Throttling, Fair Queuing and Channel Condi-tion on Unfairness in Hidden Terminal Topolgies . . . . . . . 55Figure 3.3 The Impact of Shaper on TCP RTT . . . . . . . . . . . . . . . 59Figure 4.1 Interference Pattern between the Interfering Node and the VictimNode. On the Left, the Victim Node’s Throughput Decreases as theInterfering Node’s Throughput Increases. On the Right, the VictimNode’s Throughput Increases as The Interfering Node’s ThroughputDecreases. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67Figure 4.2 The Emulab Wireless Testbed at Utah . . . . . . . . . . . . . 75xiFigure 4.3 Throughput of 7 Mutually Competing Flows. . . . . . . . . . . . 78Figure 4.4 Physical Pair-Wise Interference Map . . . . . . . . . . . . . . 80Figure 4.5 Dynamic Interference Map . . . . . . . . . . . . . . . . . . . 82Figure 4.6 Weekly Trend . . . . . . . . . . . . . . . . . . . . . . . . . . 85Figure 4.7 Channel Distribution in Highrise and LSC . . . . . . . . . . . 87Figure 4.8 Impact of R2 on VOID Accuracy, VTBR Is Kept at 0.5. . . . . 90Figure 4.9 Impact of VTBR on VOID Accuracy, R2 Is Kept at 0.01. . . . 93Figure 4.10 Closest Distance Distribution from a Detected TB and False-Negative TB to Its Nearby Detected TB. Note that Neighbor-ing TBs Are 30 Seconds Apart. . . . . . . . . . . . . . . . . . 98Figure 4.11 Average Throughput and Interference Detection Hourly Trends 102Figure 4.12 The Interference Map in Highrise. . . . . . . . . . . . . . . . 104Figure 4.13 Duration CDF in LSC and Highrise . . . . . . . . . . . . . . 106xiiGlossaryAIMD Additive Increase Multiplicative DecreaseVOID Wireless Online Interference DetectorIEEE Institute of Electrical and Electronics EngineersCSMA/CA Carrier Sense Multiple Access with Collision AvoidanceAP Access PointMIMO Multiple Input and Multiple OutputMLR Multiple Linear RegressionNAV Network Allocation VectorWLAN Wireless Local Area NetworkingTCP Transmission Control ProtocolIP Internet ProtocolUDP User Datagram ProtocolTR Transmission RangeSR Sensing RangeOR Out of RangexiiiDIFS Distributed Inter-Frame SpaceEIFS Extended Inter-Frame SpacePLCP Physical Layer Convergence ProtocolMAC Media Access ControlACK AcknowledgeOFDM Orthogonal Frequency Division MultiplexingFIFO First In First OutSFQ Stochastic Fairness QueueingRED Random Early DetectionHTB Hierarchical Token BucketRTT Round Trip TimeSNMP Simple Network Management ProtocolCC Correlation CoefficientRF Radio FrequencyLSC Life Sciences CenterWCS Wireless Control SystemFPR False Positive RatioFNR False Negative RatioVTBR Valid Time Bucket RatioCRC Cyclic Redundancy CheckxivCTS Clear-To-SendPISD Proportional Increase Synchronized multiplicative DecreaseIAC Interference Alignment and CancellationMUBF Multi-user BeamformingSINR Signal to Interference and Noise RatioxvAcknowledgmentsFirst of all, I would like to say a big thank you to my supervisor Mike Feeley. Heis not only a brilliant researcher, but also a great friend. He always motivates meand challenges my ideas with high standards, while at the same time provides megreat freedom to explore the research area that intrigues me most. Without hiscontinuous encouragement and patience, I would not be able to finish this thesis 5years after starting my job at Google.I also would like to thank my supervisor committee members: Norm Hutchin-son, Alan Wagner and Charles Krasic. They are always there offering their ideasand advice at different stages of my work. I have never hesitated to bounce myidea of them during my research. It is my privilege to work with such great re-searchers.I’d like to thank the UBC NSS folks for their support and feedback. In particu-lar, I would like to thank Mike Blackstock being my research buddy and personalfriend. I appreciate his new research perspectives, and his willingness to listenand discuss any crazy ideas of mine.Also, big thanks to my parents, Ping Wu and Minli Cai, to my sister, Lei Wu,for their belief and faith in me even when myself is skeptical.Finally, and mostly importantly, I would like to thank my wife, Junfang Wang,for her unconditional love, endless encouragement and endurance, and for com-pleting me with a family. I love you!I would like to dedicate this thesis to my son, Raymond Cai, who is just oneyear old now yet has already opened a new world to me. I look forward to manyxviyears ahead together with you.xviiChapter 1Introduction1.1 Issues: Wireless Interference and UnfairnessWireless communication has seen rapid advances with millions of IEEE 802.11devices widely deployed [18]. The reason for this popularity is mainly three fold.First, the frequency band WiFi devices operate at is unregulated and thus the pro-duction and deployment cost is lower than the other wireless technologies. Sec-ond, 802.11 conveniently allows users to be mobile while being connected to theInternet anywhere at anytime. Furthermore, 802.11 mesh networks can extend theInternet coverage in places where wired connections are expensive to provide orhard to set up. Finally, it provides satisfactory bandwidth to meet the throughputdemands of most applications. As 802.11 popularity grows, the challenge will beto continue to deliver this second benefit as device density and throughput demandincreases.Unfortunately, the performance of 802.11 is unpredictable. In a dynamic net-work where users come and go and signal interference and packet collisions be-tween competing devices persist, the amount of bandwidth a device actually re-ceives depends on the constantly changing environmental factors such as nodetopology and channel conditions. In networks where hidden terminals and ex-posed terminals exist, some devices can be starved by the others for long periods1of time [30, 31, 40, 50]. As mobile computing becomes increasingly importantin our daily lives, it is more critical to provide a reasonable degree of fairness forbandwidth distribution between competing 802.11 devices.The wireless interference problem and the unfairness problem are fundamentalto 802.11’s decentralized, signal-based airspace arbitration mechanism using aCSMA/CA and random back-off protocol. Nodes with packets to send engage inan uncoordinated competition for channel access by delaying transmission untilsenders see clear air and by backing-off and re-transmitting when collisions occur.This approach works well with only one Access Point (AP) in the network — theAP acts as the only arbitrator for packet scheduling and can ensure fair networkingaccess time for all its associated devices.However, the 802.11 protocol is not designed to support multiple autonomoussystems that operate together: in a network where multiple APS co-exist and haveincomplete and inconsistent channel conditions, the signal sensing alone can notensure a fair competition for airspace [40]. We illustrate this problem in Figure 1.1with the two infamous node topologies: the hidden-terminal and exposed-terminaltopologies.Both of these problematic scenarios can result in severe unfair bandwidth al-location [30, 31]. In the hidden-terminal scenario, signals sent by one sender canbe corrupted by another, but not vice versa. We can see from Figure 1.1a that thesenders of the two flows, S1 and S2, cannot sense each other but S1’s signal isstrong enough to corrupt S2’s signal at its receiver R2. Therefore, when S1 andS2 transmit at the same time, S2’s transmission will fail while S1’s will succeed.In the exposed-terminal scenario, a sender is exposed to many other senders.Therefore, even if it does not experience any packet loss itself, it will lose its fairshare because it is forced to relinquish the airspace more often than others. Wecan see from Figure 1.1b that the three senders do not corrupt each other’s signals.However, S2 is positioned between S1 and S3 and can sense both of their signals,and thus it is not able to transmit when either S1 or S3 is transmitting. When flows1 and 3 transmit at full speed, the sender S2 will hardly detect any idle airspace2R2S2R1S1(a) Hidden TerminalsR1S1R2 R3S2 S3(b) Exposed TerminalsFigure 1.1: Two Problematic Topologiesfor its own transmissions.In addition to node topology, various environmental factors, sending rate andsignal strength, for example, can all affect the outcome of bandwidth allocationfor wireless devices. But as long as the aggregate throughput demand does not ex-ceed the 802.11 network capacity, the wireless unfairness problem will not occur.The reason is that the winning devices only use a fraction of the available band-width and the remaining bandwidth is still sufficient to meet the disadvantageddevices’ needs. The consequence of wireless devices competing in unsaturatedWiFi networks is an increase in latency for the losing devices. Even if packets arecorrupted, the TCP and 802.11 retransmission mechanisms are able to recover thedropped packets when the airspace is idle. However, when the winning devices be-come more active, airspace becomes congested and retransmissions are no longereffective at salvaging packages. The disadvantaged devices can be completely de-prived of any bandwidth by the nearby competing devices for a significantly longtime.Unfortunately, 802.11 network congestion is already quite common in wire-less networks. Henderson et. al. [55] have shown that wireless users use bandwidth-greedy applications just as they would on wired connections. As the capacity ofthe network backbone that connects an AP to the Internet increases to Gigabit3ethernet, congestion is even more likely to occur on the last-hop wireless links.Collected traces have shown that, even in well planned wireless networks such ashotels [83] and university buildings [41], wireless users often suffer from perfor-mance degradation caused by packet collisions. To be presented in Chapter 4, ourinterference analysis in UBC shows that interference happens often in live enter-prise wireless networks, and lasts 10 minutes on average when it occurs. As thelikelihood of 802.11 network congestion continues to grow, the wireless conges-tion and unfairness problems will get worse.Many approaches have been proposed to mitigate interference in 802.11 net-works. For example, the RTS/CTS packet exchange of 802.11 was designed toresolve the hidden terminal problem by sharing the transmission schedule amongpotential interfering neighbors. However, it is not used in practice as it requiresto transmit two additional control packets without any payload, which can leadto bandwidth inefficiency in the absence of hidden terminals. Furthermore, RT-S/CTS packets cannot be used to address the exposed terminal problem. There-fore, the interference mitigation problem is mostly addressed by systems runningon top of 802.11, which must identify and change the interference relationship inthe network.Two most common solutions for example are power adaptation and channelhopping. Both alleviate interference by changing the underlying node topology tobreak the interference relationship between the dominating devices and the victimones. In this thesis we present another approach in which aggregate throughputis constrained to eliminate congestion. As we have discussed above, as long as802.11 network congestion does not occur, the impact of signal interference canbe remedied by TCP and 802.11 packet salvage schemes. In the next section, wewill discuss the challenges these proposals have to address to remain effective inpractice.41.2 ChallengesTo effectively mitigate interference in live 802.11 networks, a system needs to ad-dress the following three challenges. First, it is hard to identify the cause of theinterference from a large number of possible candidates: problematic topology,signal strength fluctuation, traffic burstiness, even non-802.11 devices such as mi-crowaves, cell phones, etc. Many of the proposed solutions, MIMO in 802.11n [12],channel hopping [20, 33, 53], power adaptation [20, 33], for example, can help incertain scenarios, but have their limitations in environments where node densityand mobility is high.Second, one prerequisite of any interference mitigation systems is to correctlyidentify the underlying interference relationship among wireless devices. Only ifthe set of interfering devices are detected can these systems select the right targetsfor channel hopping, channel switching or traffic throttling. However, prior workin pair-wise interference measurements have shown that it takes many hours toderive an interference map even in a static environment consisting of only tensof wireless devices [74]. On the other hand, the interference relationship changesfrequently in live networks. The wireless network is inherently dynamic due tonode mobility and traffic variation, and it is difficult for an interference mitigationsystem to adapt to this changing environment.Finally, to be easily deployed in existing 802.11 networks, these interferencemitigation systems need to be effective with little cooperation from the wire-less end-user devices. These end-user devices are running different firmware anddrivers, and they are usually out of the control of the networking administrators.Therefore, the effectiveness of an interference mitigation system will be limited inreality if it requires firmware updates or protocol redesign to all wireless clients.1.3 MotivationsThis thesis is motivated by our earlier discussion on the correlation between in-terference and congestion in Section 1.1, and aims to come up with an effective5and practical interference mitigation system by addressing the above three chal-lenges in live networks. We know that whether a wireless device can achieve itsfair share of the network bandwidth depends not only on environmental factorssuch as node topology, channel conditions, traffic class, etc., but also on the levelof network congestion. The impact of interference on throughput and fairnessis limited as long as congestion does not occur — the package salvage schemesof the Transmission Control Protocol (TCP) and 802.11 layers can efficiently re-schedule packets for the disadvantaged devices when airspace is idle. Therefore, ifwe can prevent congestion from happening in 802.11 networks, we could actuallymitigate the impact of interference in the network.In Chapter 3, we conducted an experiment that demonstrates the correlationbetween wireless unfairness and airspace congestion. We set up the hidden-terminal topology as illustrated in Figure 1.1a with two 801.11G APs and two802.11G laptops, each laptop is associated with one AP. We streamed both long-term TCP flows to the laptops with Mxtraf (a traffic generator, as part of theQStream project [7]) as fast as possible. Both flows, however, went through acentral router where we can throttle the aggregate throughput of both flows. Westarted with 10M bps aggregate throughput and then increase by 2M bps everyminute, and track both the aggregate throughput and the bandwidth share of eachflow. We observed that even though flow 2 is obviously the losing flow in thishidden-terminal topology, it can still achieve its fair bandwidth share until theaggregate throughput reaches 20M bps – both flows split the bandwidth 50-50.However, as the aggregate throughput continues to grow to 24M bps, the winningflow (i.e., flow 1) was able to finally starve the losing flow (i.e., flow 2) com-pletely.In brief, the key of our observation is that there exists strong correlation be-tween 802.11 network congestion and wireless unfairness: as long as there is suf-ficient airspace bandwidth for the losing flows to recover from their packet lossescaused by interference, the competing devices can still meet their throughput de-mands to achieve wireless fairness. When airspace is not congested, interference6still exists but its impact is low. Severe interference problems such as throughputstarvation will occur if and only if the aggregated throughput exceeds the availablebandwidth capability.Therefore, we are motivated to leverage this correlation to trade the overallthroughput for interference reduction and better fairness. Our evaluation showsthat fairness can be achieved once we throttle the aggregated throughput to 15-20% below the available bandwidth capacity. The advantage of this approach isthat it makes no assumptions on the underlying node topology or channel con-ditions, thus it can be effective in various scenarios. Moreover, traffic throttlingtakes place at the IP layer and requires no changes to the end-user devices or APS,making it easy to be deployed in existing 802.11 networks.Finally, we exploit the property of interference under congestion to address therelated challenge of distinguishing interference relationship. As described earlier,this information is required to deploy interference mitigation strategies, throttlingin our case, in wireless networks. Fortunately, when the airspace is fully saturated,the throughput that a disadvantaged node can achieve is mostly determined byits surrounding competing devices: when its neighbors’ throughput goes up, itsown will go down, and vice versa. An interference analysis system can thus trackthroughput variations in the network and identify the set of interfering devices if ithas observed enough throughput-change correlations among them. This approachagain does not require any cooperation from end-user devices and uses only theIP-layer throughput information collected from central routers.1.4 ThesisIn this thesis, we describe our interference detection and mitigation system thatexploits the correlation between interference and congestion in centralized 802.11networks. It consists of two subsystems. One is called Shaper, designed to tradethroughput for fairness by throttling aggregated throughput at central routers. Theother is called called VOID, which infers interference relationships from correlatedthroughput variations monitored at the central router.7Our system is effective because it is capable of addressing all the three chal-lenges discussed in Section 1.2. It throttles throughput at the IP layer, preventingcongestion from occurring in the first place and thus limiting the impact of inter-ference in the network. It tracks the throughput variations at the wired networkto correlate interference relationships among wireless devices. We show in Chap-ter 4 that this approach is not only accurate but also quick to converge, takingonly seconds to minutes. Finally, our approach makes no assumptions about theunderlying node topology or channel conditions and does not require cooperationfrom end-user devices.In particular, this thesis makes the following contributions in each of the re-spective chapters:Chapter 2: Interference Impact Analysis: Whether a wireless device canachieve its fair share of the network bandwidth depends on the node topology,channel condition, traffic class, and other environmental factors. To better un-derstand how interference can impact the performance of wireless devices, wesimulated two competing wireless flows in hundreds of scenarios by varying threeenvironmental factors: node topology, traffic class and signal strength. Thesescenarios are categorized into 9 UDP models and 10 TCP models based on thedifferences in throughput and fairness. These results also demonstrated that theinterference relationship is very complicated in 802.11 networks, where a slightchange in one of the networking settings can completely change the outcome ofthroughput for a wireless device. Therefore, many of the previously proposedapproaches designed to address interference by adjusting one network parame-ter: power adaptation or channel hopping, for example, cannot stay effective incontinuously changing WiFi networks.Chapter 3: Achieve Fairness by Congestion Reduction: Congestion in802.11 networks is the immediate cause of unfair bandwidth allocation, and there-fore reducing the congestion level is the key to achieving fairness in WiFi net-works. Our experiments clearly demonstrate the correlation between congestionand unfairness, and in Chapter 3, we introduce a system called Shaper that en-8sures fair bandwidth distribution to competing devices by throttling their aggre-gate throughput at a central router that all traffic goes through. Unlike the otherinterference mitigation systems, Shaper is a cross-layer approach that only usesIP-layer information, and therefore it can stay effective in almost all scenariosregardless of the cause of interference. We not only prove the effectiveness ofShaper in our testbed environment, but also provide an in-depth discussion of sys-tem design, implementation, and challenges to deploy Shaper in large and centralwireless networks.Chapter 4: Passive Interference Detection Using Online Traffic: The keyto make Shaper (or any interference mitigation system) effective is to detect in-terference when it occurs. Moreover, such an interference detection system hasto be adaptive, fast, accurate, and require no modifications to the end-user de-vices or APs. VOID is such a system that meets all these requirements. It looksfor throughput variation patterns in the wired networking traces: one’s throughputgoes up while the other’s goes down, to correlate interference relationships using aMultiple Linear Regression (MLR) model. It only needs information readily avail-able from the IP-layer at a central router, and therefore can be easily deployed inany centralized WiFi networks. It is fast, able to converge to an interference mapwithin seconds, and thus can quickly adapt to environment changes. It is also ac-curate; our testbed and live network experiments show that it is able to accuratelyidentify the truly interfering devices from many candidates included for analysis.1.5 Thesis OrganizationChapter 2 provides a thorough background and analysis on how WiFi devicescould interfere with each other. We vary the node topology, traffic type and linkstate to illustrate how they affect the bandwidth allocation between competingflows and why. Chapter 3 concentrates on the correlation between 802.11 networkcongestion and wireless unfairness, and demonstrates that we can trade aggregatebandwidth utilization for fairness. We also discuss the challenges to deploy sucha system in existing WiFi networks. One of the biggest challenges, interference9detection, is addressed in Chapter 4. We proposed VOID to infer interference fromthroughput variations in the wired trace. Chapter 5 discusses the related work oninterference detection and mitigation and finally Chapter 6 concludes the thesisand discusses the future research directions.10Chapter 2Interference Impact AnalysisAs this thesis intends to detect and mitigate interference in 802.11 networks, itis critical to first understand how interference can affect devices’ performance invarious scenarios. Most of the previous interference analysis work focuses mainlyon the impact of problematic topologies exemplified by the hidden-terminal andexposed-terminal scenarios, and assumes the other environmental factors remainunchanged.In reality, however, an interference relationship is more complicated than sim-ple topology categorization. As we later demonstrate in this chapter, even if thetopology stays unchanged, the wireless devices can perform significantly differ-ently if the traffic type or channel condition changes. To deploy the proper inter-ference mitigation approach for a poorly performing wireless client in one sce-nario, we need to understand the direct underlying environmental factor that isadversely affecting its performance: is the poor performance because of poor sig-nal strength or high sending rate? Is the problem happening at the packet sendingside or the receiving side? To help answer these questions, we provide a more de-tailed analysis on the impact of interference on 802.11 flows and provide concretesuggestions to improve the performance of devices in different scenarios.In this chapter, we consider both TCP and UDP flows and a comprehensive setof node topologies with two competing flows. These two-flow scenarios are the11basic building blocks of any network topology, and previous works [50, 73] haveshown that they can be used to evaluate the collision probability for a transmitterand to predict the interference effects in more complex scenarios. We vary thesetwo-flow topologies to consider all combinations of the following four node-to-node interactions: (1) nodes unable to read or sense each other, (2) nodes able tosense each other but not able to read each other’s packets and nodes able to com-municate with (3) weak and with (4) strong signal. We evaluate all possible casesthrough simulation and show that the cases can be reduced to 9 UDP and 10 TCPmodels with similar efficiency/fairness characteristics. We also validate our sim-ulation results with experiments conducted in a laboratory testbed. These moredetailed models improve on previous work such as hidden-/exposed-terminal cat-egorization and are thus better suited as a basis for adaptive techniques to improveperformance in 802.11 multi-hop Wireless Local Area Networking (WLAN).The content of this chapter is mostly based on our previous paper [35]. Westart by giving an introduction in Section 2.1. Section 2.2 introduces the method-ology that we use to model all different interference scenarios. In Section 2.3, wedescribe the 9 UDP and 10 TCP models for two 802.11G competing flows in greatdetail. Then, Section 2.4 provides both the simulation and testbed results to provethe accuracy of our models. Finally Section 4.8 summarizes this chapter.2.1 IntroductionAs we discussed in Chapter 1, in IEEE 802.11, nodes regulate access to theairspace they share in a decentralized fashion using Carrier Sense Multiple Ac-cess with Collision Avoidance (CSMA/CA) and random backoff protocols. Nodeswith packets to send engage in an uncoordinated competition for channel accessby delaying transmission until sender and receiver see clear air and by backing-offand re-transmitting when collisions occur. The goal of this approach is to sharethe common airspace fairly and efficiently without requiring centralized channeladministration or direct coordination among peer nodes.Unfortunately, in congested environments things often do not go according12to plan. It has been shown that the protocol often exhibits unpredicted perfor-mance degradation [31, 62] and unfair channel allocation [30, 31, 40] due to thenode topology and other environmental factors. This performance of 802.11 issurprisingly not well understood and the complexity of the environment and thedecentralized nature of the protocol make understanding elusive. Nevertheless, as802.11 popularity grows, congestion increases and emerging applications such asmedia streaming place new demands on network performance predictability, thereis a growing need for a deeper understanding of how 802.11 deals with congestedtraffic in practice [55].The early understanding of 802.11 was that sending nodes are confronted withtwo types of potentially competing nodes: hidden- and exposed-terminals [31].The issue for the protocol is that the sender decides when to send, but it is thechannel conditions at the receiver that determine successful delivery. Nodes hid-den from the sender can cause corruption, and nodes exposed to the sender buthidden from the receiver may not. Chen et al. [40] extended this basic model toobserve that sender-receiver node pairs can have incomplete or inconsistent viewsof network topology. They argue that incomplete information leads to networkinefficiency while inconsistent information leads to unfairness. They do not show,however, what network conditions lead to one or the other of these problems.The best attempt we know of to describe the conditions that lead to ineffi-ciency and unfairness is by Garetto et. al. [50]. They model the behavior of aset of four nodes consisting of two competing UDP flows. They model node in-teraction as a binary condition on each node pair indicating whether the pair iswithin transmission range of each other. Their approach leads to 16 topologies,which they classify into one of the four categories based on similar performancecharacteristics.This chapter provides a new model of two-flow competition that extends thisearlier work in three ways. First, we model traffic that can be sensed but not read.We show that typically at least 42% of the traffic a node senses is too weak tobe read. The difference between readable and unreadable competing traffic is the13S2S1R1 R2(a) Senders Can Read EachOther; Fair Bandwidth AllocationS2S1R1 R2(b) Senders Can Sense EachOther; Flow 2 WinsS2S1R1 R2(c) Senders Cannot Sense EachOther; Flow 1 WinsFigure 2.1: Two Competing Flowsamount of time the sender waits before attempting to send again. The importanceof this difference can be seen in the example in Figure 2.1, in which two 802.11flows are either fair or unbalanced toward one or the other depending only onwhether the two senders can read, sense or not sense each other’s packets.Second, we model both UDP and TCP traffic. The key difference between UDPand TCP is that TCP has a counter flow of transport-level ACK messages. We showthat the presence of this counter flow is important to understanding the behaviorof wireless congestion.Finally, we consider flows where sender and receiver are close enough that theflow is resilient to noise generated by the competing flow.14In all, we characterize the two-competing flow scenario using 19 802.11gmodels (9 UDP and 10 TCP) that predict network performance based only ontopology. We validate our models using simulation and experimentation in a labtestbed.2.2 Modelling MethodologyOur work takes an approach based on simulation and experimentation. We firstdevised a set of node-topology parameters and node-performance characteristics.We then simulated every combination of topologies characterized by these param-eters and grouped them by common performance characteristics. Finally, we usedtestbed experiments to validate topologies whose performance differed from pre-vious work or which constituted interesting inflection points in the performance-parameter space. This section describes these parameters, characteristics and ourassumptions.2.2.1 Model ParametersWe consider three parameters in our model. The first is link state. A two-flowscenario consists of four nodes with six links between them. Two of these linksare between the sender and receiver of each of the two flows, which are assumedto be in transmission range. The other four links — between senders, betweenreceivers, and between sender and receiver of different flows — can have one ofthree possible link states: out of range, in sense-range only, and in transmissionrange. The other two parameters are traffic type and flow robustness. Taken to-gether these three parameters and their possible values yield a total of 648 distinctnetwork/traffic-type topologies.1 The remainder of this section describes thesethree parameters in more detail.13 link states; 4 inter-flow links; 2 traffic type; 2 interference levels. The number of scenariosis 34 ∗2∗22 = 648.15Tri-State Link There are three states between any pair of nodes depending on thetransmission power, carrier sensing threshold and background noise: (1) Trans-mission Range (TR), in which a node can clearly receive a packet from the othernode; (2) Sensing Range (SR), in which a node can only sense the signal from theother node, but is not able to capture its packet correctly; (3) Out of Range (OR),in which a node cannot sense any signal from the other node at all.Receiving a packet or sensing a packet has different impacts on the length ofdelay before a node sends its next packet. When a node is in transmission range ofanother node, it is able to set its Network Allocation Vector (NAV) correctly andthen use Distributed Inter-Frame Space (DIFS) to contend for the airspace withthe others. When it senses a packet whose payload it can not decode, however, itfollows a different approach.If the packet is sent by a 802.11g (or 802.11a) node that uses the standardOrthogonal Frequency Division Multiplexing (OFDM) modulation scheme, thenthe sensing node is unlikely to decode the Physical Layer Convergence Protocol(PLCP) header if it cannot decode the payload. This is because part of the PLCPheader, the SERVICE field, is also encoded by the higher-rate modulation that thepayload uses. When a node fails to decode the PLCP header, it still uses DIFS toschedule its next packet after it cannot sense any airspace activity. Thus, becausethe NAV was not properly set up, if the sensed traffic is actually a MAC data packet,this sensing node might not back off long enough to avoid interference to thereturning MAC ACK packet.Traffic Type We investigate the performance of two traffic types in all the topolo-gies: (1) UDP traffic (2) TCP traffic. The key difference between UDP and TCP isthat TCP flows consist of two sub flows, i.e., the TCP-DATA subflow and the TCP-ACK subflow.Flow Robustness The distance between a flow’s sender and receiver also playsan important role in a noisy environment. If the nodes are close enough, the signal16strength at the receiver is strong enough that the flow is resilient to most noise,while a distant sender provides a weak signal that is vulnerable to noise. Weexamine two points along this signal-strength continuum using the interference-level parameter which takes on two possible values: (1) Interference-Susceptibleand (2) Interference-Immune.2.2.2 Performance CharacteristicsWe classified the simulation results according to two qualitative performance met-rics: fairness and communication efficiency. The first metric has three values: fairor unfair with one or the other of the flows dominating. The other metric classifiesinterference between the flows by indicating whether there is interference and, ifso, which packets conflict: data packets send by flow senders, ACK packets sentby flow receivers or one type from each flow.2.2.3 AssumptionsFinally, we make three important simplifying assumptions. First, we assume thatlink conditions are symmetric; that is node A has the same view of B’s traffic thatB has of A’s traffic.Second, we restrict our analysis to two flows under the belief that pair-wiseinterference is common enough to warrant isolated study and under the hope thatthese results will provide a building block for analysis of more complex topologiessuch as mesh networks [50].Third, we assume that nodes out of sensing range do not interfere with eachother’s traffic. This assumption is built into common network simulators and ap-proximates expected behavior. However, at higher sending rates, the assumptiondoes not hold, though it is likely rate-adaption schemes incorporated on most802.11 adaptors would lower sending rate if faced with significant interference,even from an otherwise invisible node. Experiments conducted in our testbed in-dicate that at a low sending rate of 6 Mbps (802.11g), any signal above -70 dBmwould not be vulnerable to noise from a node that could not be sensed.172.3 802.11g ModelsWe simulated each of the 648 802.11g scenarios characterized by our model;details of the simulation are presented in Section 2.4.3. As explained in para-graph 2.2.1, we assume in these scenarios a sensing node is not able to decode thePLCP header of the sensed packet and thus will not use EIFS to schedule its nexttransmission. By grouping performance-similar topologies together, we derive 9UDP and 10 TCP models.2.3.1 UDP ModelsWe begin with the models for two competing UDP flows. Figure 2.2 providesa graphical representation of each model and its legend is shown in Figure 2.3.Note that symmetric sense means that either two senders can at least sense theother receiver or neither does. There is no difference for a sender when it capturesa MAC ACK packet or just senses the ACK — in either case, it will use DIFS tocontend for the airspace after the MAC-ACK transmission finishes.Base Cases.We begin with four initial models that exclude the possibilities that two sendersare in sensing range and that a flow is robust to interference. These models areessentially the same as the four models of Garetto et. al.UM1: Independent For completeness we begin with the trivial model in whichtwo flows that are sufficiently distant from each other that neither flow affects theother.UM2: Senders TR In this model the senders of each flow can read each other’spackets. In this case, there is no interference between two flows and thus band-width is evenly divided regardless of the nature of other node relationships (receiver-receiver and sender-receiver) or signal strength (weak- or strong-signal links).18S2S1R2R1(a) Independent (Fair, No In-terference)S1R1 R2S2(b) Senders TR (Fair, No Inter-ference)S1R1 R2S2US(c) Sym, Senders OR (Fair,Data-Data Collides)S2S1R2R1(d) Asym, Senders OR (Unfair,Flow 1 Wins)S1R1 R2S2US(e) Sym, Senders SR (Fair,Data/MAC-ACK Collides)S2S1R2R1(f) Asym, Senders SR (Unfair,Flow 2 Wins)19S2S1R2R1(g) 1 Robust, Senders Not TR(Unfair, Flow 1 Wins)S2S1R2R1(h) 2 robust, Asym Senders notTR (Unfair, Flow 2 Wins)S2S1R2R1US(i) 2 Robust, Sym Senders NotTR (Fair)Figure 2.2: Models for UDP FowsTR, SR or OR LinkTATSUSWeak TR LinkTR or SR LinkStrong or Weak TR LinkStrong TR LinkSR LinkSR or OR LinkTopology Symmetry (TCP) Topology Asymmetry (TCP)Symmetric Sense (UDP)Figure 2.3: Legend for Models20UM3: Symmetric Sense, Senders OR Two models are needed to capture the be-haviour when sending nodes are out of range. The first model covers the casewhere the ability of a sender to sense the receiver of the other flow is symmet-ric. In this case, bandwidth is evenly distributed to the two flows, but aggregatebandwidth is reduced due to congestion-caused packet loss.There are two types of packet loss. First, in the case where receivers can sensethe senders of the other flow, then data packets from two senders can collide.Second, in the case where receivers cannot sense the senders of the other flow buttwo receivers are in sense range, then a DATA packet sent by one flow’s sender cancollide with a MAC-ACK packet sent by the other flow’s receiver.UM4: Asymmetric Sense, Senders OR The next model covers the case wheresending nodes are out of range and the sense relationship between flows is asym-metric. In this case, bandwidth allocation unfairly favors the flow whose senderis able to sense the other flow. The reason this flow gets more bandwidth is thatwhen both senders send DATA packets at the same time, the packets sent to thereceiver of the losing flow will be garbled but the other receiver sees only thepackets from its sender.Sensing Unreadable Traffic.We now consider two new models in which senders can sense each other’s packetsbut can not read them: one symmetric and one asymmetric.UM5: Symmetric Sense, Senders SR When the topology is symmetric, similar toUM2, the two flows receive a fair bandwidth allocation. Unlike the earlier model,however, the fact that senders can only sense means that DATA packets can garbleMAC-ACK packets from the other flow.UM6: Asymmetric Sense, Senders SR The next model is similar to UM4, wherea sender’s ability to sense the other flow is asymmetric, but now senders are in21sense-only range of each other. As in UM4, this model leads to unfair bandwidthallocation, but now with the other flow — the flow who’s sender does not sensethe other flow — winning.The difference between this model and UM4 is that senders can sense eachother and so they do not send at the same time. They can not read each other’spackets, however, and so they do not back off long enough to avoid overlappingwith the MAC-ACK packet sent by the other flow’s receiver. The asymmetry shownin Figure 2.2f indicates that the MAC-ACK packets of flow 1 are more likely tobe garbled since sender 2 cannot sense receiver 1 at all, thus giving flow 2 theadvantage.Robust Flows.We now consider the three models in which one or both flows are robust to anynoise.UM7: One Robust Flow If only one flow is robust, it dominates the other flowwhenever senders are not in transmission range.UM8: Two Robust Flows, Asymmetric If both flows are robust, senders are notin transmission range and the sense relationship between sender and receiver ofdifferent flows is asymmetric, then the flow whose sender senses the other receiveris dominated. This flow is disadvantaged because the sender avoids sending DATApackets when the other flow’s receiver is sending MAC-ACK packets, even thoughthe robustness of the two flows means that collisions will not occur.UM9: Two Robust Flows, Symmetric When the topology is symmetric, band-width is shared equally between the two robust flows.22S2S1R2R1(a) Independent (Fair, No In-terference)S2S1R2R1(b) All SR/TR Links (Fair, Lit-tle Interference)S2S1R2R1At Least 1 OR LinkTS(c) Not All SR/TR Links, Sym(Fair, Interference)S2S1R2R1TA(d) Asym, Senders OR (Unfair,TCP Data-Data Collides)S2S1R2R1(e) Asym, Sender Receiver OROnly (Unfair, TCP Data-ACK Col-lides)S2S1R2R1(f) Asym, Receivers OR Only,Senders SR (Unfair, EIFS Impacts)23S2S1R2R1TA(g) Asym, Receivers OR,Senders TR (Unfair, TCP ACK-ACK Collides)S2S1R2R1(h) Robust, All TR Links (Fair,No Interference)S2S1R2R1Not All TR Links(i) 1 Robust, Not All TR Links(Unfair, The Robust Flow Wins)S2S1R2R1(j) 2 Robust, One Sender-Receiver Link Only (Unfair)Figure 2.4: Models for TCP Flows2.3.2 TCP ModelsModeling TCP is more complex due to the fact that each TCP flow consists of twosub-flows: DATA packets sent from sender to receiver and TCP-ACK packets sentfrom receiver to sender. TCP-ACK packets differ from MAC-ACK packets in theway that they are initiated. MAC-ACK packets follow reception of a DATA packetafter a bound interval, but TCP-ACK packets are simply data packets to the MAClayer and are thus sent only when the channel is sensed to be clear. This differencechanges the notion of cross-flow symmetry from that of UDP. Unlike UDP, TCP24flows are considered to be asymmetric when senders of both flows can sense theother flow’s receiver, but one is in transmission range of the receiver and the otheris in sense-only range.We will first introduce the three fair models in this section. We then presentfour unfair models based on their different causes, followed by three other modelsthat consider robust flows.Fair Models.There are three TCP models that result in fair network bandwidth allocation.TM1: Independent Again, for completeness, we begin with the trivial modelin which two flows that are sufficiently distant from each other that neither flowaffects the other.TM2: All SR/TR Links Model TM2 requires that all pairs of nodes are at least insensing range. In this model, two flows also experience little interference. This isbecause, considering any two TCP subflows in this model, they fit in either modelUM2 or model UM5, which both result in a fair network allocation.TM3: Incomplete and Symmetric When not all pairs of nodes are connected,two TCP flows can still achieve fairness as long as the topology is symmetric.However, if at least two nodes are out of sensing range, there is a good chancethat their packets will collide.It is worth pointing out that TCP treats transmission failure as signal of net-work congestion and consequently reduces its sending rate. This behaviour isoften considered as not desirable as wireless links are usually lossy, but it indeedalleviates the problems of congestion and signal interference. For example, givena symmetric topology in which the link between the sender of flow 1 and senderof flow 2 is not present, interference causes the collective UDP throughput to dropby 38%, while TCP flows suffer only 6% degradation.25Unfair Models.All asymmetric topologies except those all-sensing cases result in unfair networkallocation. There are four cases.TM4: Asymmetric, Senders OR When the senders are out of range, the mainproblem is collision between the two TCP-DATA subflows. The flow whose senderhas less topology information loses. For example, if sender 1 and receiver 2 areout of range, then flow 1 loses just as in the hidden-terminal case for UDP flows.TM5: Asymmetric,Sender-Receiver OR Only When the only link missing is thelink between the TCP sender of flow 1 and TCP receiver of flow 2, most packetcollisions are TCP-DATA/TCP-ACK collisions. Flow 2 wins in this model be-cause sending a TCP-ACK packet usually takes less time than sending a TCP-DATApacket. Therefore, when such collisions occur in the airspace, the probability ofsuccessfully retransmitting an ACK packet is higher than that of a DATA packet.TM6: Asymmetric, Receivers OR Only, Senders SR When the only link missingis the link between the two receivers, the only possible cause of asymmetry iswhen sender 1 and receiver 2 are in transmission range, but sender 2 and receiver1 are in sensing-only range.In this case, both flows suffer from TCP-ACK/TCP-ACK collisions. Accordingto the 802.11 protocol, when such collisions occur, both TCP senders use EIFSto schedule the next transmission unless they can capture a packet clearly in theairspace. Therefore, in this model, the flow whose TCP sender can clearly capturethe packet sent by the TCP receiver of the other flow wins.TM7: Asymmetric,Receivers OR, Senders TR If senders are within transmissionrange, EIFS no longer affects the fairness because the two TCP senders can resetEIFS to DIFS for each other.This model is similar to model TM4 except that its fairness is determined by26the worst TCP receiver not sender; the flow whose TCP receiver has less topol-ogy information than the other TCP receiver loses. For example, if sender 1 andreceiver 2 are out of range, then flow 2 loses.Robust Flows.We now consider three models in which one or both flows are robust to any inter-ference.TM8: One Robust Flow, All TR Links If flow 1 is the only robust flow but allfour nodes are within transmission range, the network bandwidth can be still fairlyallocated since every node has the complete knowledge of network topology andtraffic.TM9: One Robust Flow, Not All TR Links If not all nodes are within transmis-sion range of each other then packet collisions will occur. Flow 1 is not affectedbecause of its strong signal strength while flow 2 has to back off and retransmit.Thus, flow 1 always wins.TM10: Two Robust Flows, One Sender-Receiver Link Only When both flowsare immune to interference, there is only one unfair topology, i.e., when the TCPsender of flow 1 and the TCP receiver of flow 2 are connected. In this case shownin Figure 2.3j, flow 1 loses because sender 1 senses receiver 2’s signal and thuscannot send as fast as sender 2.2.4 EvaluationWe simulate all 648 scenarios using Glomosim [102]. To further ensure that thesimulator is trustworthy, we also set up a controlled testbed that consists of fourwireless nodes to study the interesting scenarios.27S1 R1 S2 R2Moving Direction of Flow 2(a) Initial Setting of Example Scenario 1S1 R1Moving Direction of Flow 2R2 S2(b) Initial Setting of Example Scenario2S2S1R2R10 mState 1UM2, TM2S2S1R2R1S2S1R2R1S2S1R2R1S2S1R2R1S2S1R2R1S2S1R2R1State 2 State 3 State 4 State 5 State 6 State 7UM1, TM1Sender−Sender Distance99 m 251 m1 m 50 m 300 m 349 mUM2, TM2 UM5, TM2 UM5, TM2 UM6, TM5 UM4, TM4(c) State Transition of Example 1S2S1R2R1S2S1R2R1S2S1R2R1S2S1R2R1S2S1R2R1S2S1R2R1S2S1R2R1State 2 State 3 State 4 State 5 State 6 State 7UM1, TM1Sender−Sender DistanceState 1148 m 300 m50 m 99 m 349 m 398 m49 mUM2, TM2 UM5, TM2 UM5, TM2 UM3, TM3UM5, TM2 UM3, TM3(d) State Transition of Example 2Figure 2.5: Model Transition in Two Scenarios28For ease of exposition, we do not provide detailed results of the simulation.Instead, we present the results from the following two example scenarios that arecapable of capturing behaviours of all the weak-link models but TM6 and TM7.2.4.1 Example ScenariosThe four nodes are initially placed as illustrated in Figure 2.5a and Figure 2.5b,ensuring that all pairs of nodes are within transmission range. The only differencebetween these two examples is the placement of nodes S2 and R2. The nodes offlow 2 then gradually move away from flow 1, which weakens the signal strengthbetween these two flows. This causes three links, i.e., (S1, S2), (S1, R2) and(R1, R2), to experience all three link states as the distance increases. We can seefrom Figure 2.5c and 2.5d that each example involves 7 state transitions until theycompletely move out each other’s radio range.2.4.2 Relationship to UDP/TCP ModelsAccording to the model definitions in Section 2.3, we can convert the state transi-tions we simulate into model transitions as shown in Figure 2.5c and 2.5d.Note that, due to their symmetric topologies, all states of scenario 2 belong tomodels that result in fair network allocations. We can therefore predict that thetwo flows can achieve the same throughput even though they might suffer frominefficiency problems caused by signal interference in some of the states.Scenario 1, on the other hand, suffers not only from signal interference but alsofrom unfairness problems in its 5th and 6th states. The topologies of its 2nd and3rd states are also asymmetric. However, the flows will evenly split the networkbandwidth according to the models they fall into.We can thus predict that, if both flows are UDP flows in scenario 1, flow 1wins in the state 5 and then loses in state 6 according to the analyses given inSection 2.3.1. If both flows are TCP flows, flow 2 wins in both states as explainedin Section SimulationThe Simulator.Glomosim [102] is a scalable simulator. But its physical settings are based solelyon 802.11b and are not able to reflect the changes that have been incorporatedinto the 802.11g protocol. We thus implement a new physical layer based onthe 802.11g specification [10] that includes changes such as transmission rates,duration of physical preambles, minimum CWnd size, signal extension duration,etc. We have also verified its accuracy by comparing our simulation results ofone flow, either TCP or UDP, against that collected from our testbed using 802.11gcards; they are closely matched. We also ensure that Glomosim accurately models802.11g’s sensing behaviour as described in Section 2.2.1.The transmission rate is set to the highest rate 54 Mbps in our simulations. TheMAC-layer ACKs are sent at the 24Mbps rate, modelled after the Ralink drivers inour testbed. The minimum receiving signal strength is set to -58 dBm and sensingsignal strength -76 dBm, corresponding to 50 meters and 300 meters in the two-way propagation model. The minimum signal-to-noise ratio is set to 18 dBm(receiving signal strength - sensing signal strength) so that nodes out of sensingrange are also out of interference range. It is worth noting that, since our modelonly assumes three link states, our choices of distances of transmission range andsensing range are rather arbitrary. Each simulation lasts 900 seconds and repeats10 times with different seeds.Simulation Results.The simulation shows that UDP and TCP performance differs significantly as seenby comparing Figure 2.6 and Figure 2.7. This results confirm the importance ofmodeling TCP separately from UDP.Similarly, an example of the importance of distinguishing sensed traffic thatcan be read from that cannot is seen in scenario 1 by comparing states 2, 5 and 6.Performance of these states varies significantly, but the only key difference in their30topologies is the state of the link between the two sending nodes. The previousmodels that assume that all sensed traffic is readable would have mispredicted theperformance of state 5.UDP Flows.We present the mean values of two UDP flows’ throughputs in Figure 2.6; thestandard deviations are low and thus not shown.Scenario 1 We can see from Figure 2.6a that, in the first scenario, two flows firstsplit the network bandwidth evenly and then experience unfairness as the distancebetween them increases: flow 1 wins at first and then loses. This is exactly whatour models have explained and predicted.Scenario 2 We can see from Figure 2.6b that two flows fairly share the networkbandwidth throughout all the states in scenario 2 even if interference occurs. Thisis expected because all the topologies shown in Figure 2.5d are symmetric andthus fall into models that promise fairness.TCP Flows.The TCP performance results are presented in Figure 2.7. Flow 2 wins in scenario1 when interference starts to occur while both flows achieve fairness throughoutscenario 2.Scenario 1 When the distance between the senders is less than 250 meters, all thenodes are within sensing range and therefore all topologies belong to model TM2,in which the two flows share the network bandwidth fairly and also cause littleinterference. Beyond 250 meters, sender 1 and receiver 2 move out of sensingrange. The topology belongs to model TM5 and thus, unlike the correspondingUDP scenario, flow 1 loses this time because the major collisions between sender 1and receiver 2 are due to TCP-DATAs and TCP-ACKs. When the distance increases310 100 200 300 4000  102030Distance (m)Throughput (Mbps)Flow 1Flow 2(a) 802.11g, Example 150 150 250 350 4500102030Distance (m)Throughput (Mbps)Flow 1Flow 2(b) 802.11g, Example 2Figure 2.6: UDP Performance in Simulations320 100 200 300 4000  102030Distance (m)Throughput (Mbps) Flow 1Flow 2(a) 802.11g, Example 150 150 250 350 4500  102030Distance (m)Throughput (Mbps) Flow 1Flow 2(b) 802.11g, Example 2Figure 2.7: TCP Performance in Simulations33to beyond 300 meters, the two TCP senders move out of sensing range and thusthe performance of flow 1 drops due to the TCP DATA-DATA collisions at receiver1.Scenario 2 Two flows fairly share the network throughout all topologies in sce-nario 2. As in the UDP scenarios, after the two senders move beyond 300 metersapart, the impact of interference starts to show. However, the performance penalty,compared to that of UDP flows, is much less, because TCP’s sending rate is regu-lated by its ACKs. Lowering the sending rate can significantly alleviate congestionand thus reduce packet collisions. On the flip side, the performance of a TCP flowfluctuates due to its congestion avoidance scheme; the standard deviation can beas high as 800Kbps and starvations lasting for seconds are not rare.2.4.4 Testbed ExperimentsWe set up a controlled testbed to verify the simulation results. The testbed consistsof 4 desktop computers. Each desktop is equipped with one LinkSys WMP54Gcard that uses the Ralink 2560 chipset. Our testbed is running FreeBSD 6.1 Re-lease. Our experiment is conducted in a 8m X 8m room. We use altered antennasto attenuate signal strength, and change the link state by adjusting transmission-power settings.We confirm the link state settings (i.e., TR, SR or OR) before each experimentby letting two nodes broadcast messages with the same SSID. The two nodes areout of sensing range if they are able to transmit at full speed. Otherwise, if theytransmit about half as fast but are not able to receive any messages, the link is insensing state.We set up snapshots of interesting topologies from the simulation using ourtestbed. All experiments were conducted late at night to minimize the impact ofextraneous interference. The transmitting rate was fixed at 54Mbps. Each runlasted 15 minutes and the autorate function was disabled so that topology doesnot change during the runs.340 150 300 450 600 750 9000102030Time (s)Throughput (Mbps)Flow 1Flow 2(a) UDP, Snapshot 10 150 300 450 600 750 9000102030Time (s)Throughput (Mbps) Flow 1Flow 2(b) TCP, Snapshot 1350 150 300 450 600 750 9000102030Time (s)Throughput (Mbps)Flow 1Flow 2(c) UDP, Snapshot 20 150 300 450 600 750 9000102030Time (s)Throughput (Mbps) Flow 1Flow 2(d) TCP, Snapshot 2360 150 300 450 600 750 90051015202530Time (s)Throughput (Mbps) Flow 1Flow 2(e) UDP, Snapshot 30 150 300 450 600 750 9000102030Time (s)Throughput (Mbps) Flow 1Flow 2(f) TCP, Snapshot 3Figure 2.8: Performance of Snapshots37In this section, we report the results from three snapshots that correspond thethe main inflection points in the simulation graphs from the previous section. Wethen show a state transition scenario using our testbed to illustrate the impact oflink-state changes on flow performance in real networks. We repeat 3 runs ineach setting and the mean values are reported. The biggest standard deviation isobserved in fair TCP scenario, 1.4Mbps out of 7.4Mbps.Snapshots.We set up the following three snapshots and show the testbed results in Figure 2.8:snapshot 1 — state 5 in Figure 2.5c; snapshot 2 — state 6 in Figure 2.5c; andsnapshot 3 — state 5 in Figure 2.5d.Comparing the testbed results against the simulation results shown in Fig-ure 2.6 and Figure 2.7, we can see that they match closely, though the performanceof TCP flows fluctuate more in the testbed. The testbed results also closely followthe predictions of our models.State Transition.Figure 2.9a illustrates a transition experiment. The link between S1 and R2 isinitially in the sensing state. We then gradually reduce their transmission power,and eventually put them out of sensing range. Note that this scenario actuallycorresponds to the transition of State 6 from Figure 2.5c to Figure 2.5d.We observe the impact of this transition and report the throughput changes ofboth flows in Figure 2.9b and Figure 2.9c respectively. It is not surprisingly thatthis transition favors flow 2. The initial topology belong to model UM5, in whichflow 1 dominates because it garbles most of flow 2’s packet at receiver R2. AsS1’s signal strength attenuates, the noise at R2 is reduced. Thus, the performanceof flow 2 gradually improves and that of flow 1 declines. The final state is asymmetric topology belonging to model UM3, in which both flows equally splitthe network bandwidth. It is worth noting that our testbed can monitor thesegradual link-state changes that simulators such as Glomosim fail to catch. Not38S2S1R2R1S2S1R2R1(a) State Transition (RSSI: -72dBm→ -78dBm)0 150 300 450 600 750 9000102030Time (s)Throughput (Mbps)RSSI: −78RSSI: −76RSSI: −74RSSI: −72(b) Flow 10 150 300 450 600 750 9000102030Time (s)Throughput (Mbps) RSSI: −78RSSI: −76RSSI: −74RSSI: −72(c) Flow 2Figure 2.9: State Transition Experiment39shown in there, TCP follows the same trends and our testbed witnesses that aswell.2.4.5 Sensing RangeFinally, we conducted a different set of experiments to understand how frequentlynodes sense traffic that is too weak for them to read. The difficulty in collect-ing this information experimentally is that 802.11 CSMA/CA is implemented infirmware and we cannot directly determine when a wireless adaptor is sensingtraffic.We thus used an indirect approach to measure sense-only traffic. We config-ured a machine with two Dlink DWL-G520 wireless adaptors using the Atheroschipset. One card is used to sense traffic by sending 1-byte messages at roughly2-second intervals. We carefully measure the latency of each packet send to de-termine whether the adaptor sensed traffic and thus backed off at least once beforesending the probe packet.The other card operates in the monitor mode to passively capture all trafficreadable by the card, regardless of its destination address. We carefully log thestart and end time of every packet received by the card and correlate these timeswith the log generated by the first card. If we see that a probe packet was delayedat a time when the second card was not receiving a packet, then we conclude thatthis backoff is due to traffic that can be sensed but not read (in sense-only range).We collected two 48-hour traces in two university labs in two buildings. Weconservatively set the backoff-delay threshold to 350 µs — the longest possible802.11g first-try back-off time without any optimization — 50 µs + 15 * 20 µs;the average delay in our traces is around 120 µs. We consider delays longer thanthis threshold to indicate that a packet was sensed or captured. The trace files showan average of 75% of the delays are due to sensing instead of packet receiving.Even in the worst hour in our trace, at least 42% of the backoffs are due to signalsensing. Among the entire data collected delays as large as 9.6 ms were observed,during which 18 packets were received.402.5 SummaryIn this chapter, we analyzed the scenarios of two competing flows and provided 19concrete models that predict the performance and fairness based on node topolo-gies, traffic type and channel conditions. In particular, these models consideredthree factors absent from previous work: (1) sensing state, (2) TCP flows and (3)weak or strong signals. We also validated our models via both simulations andreal experiments in a testbed and the results show that they are accurate.More importantly, our analysis demonstrates the dynamic nature of interfer-ence in 802.11 networks, where a slight change in the environment can completelychange a device’s performance. There are already 628 scenarios and 19 modelswhen considering merely three network settings for two competing flows. Thereare still many other factors left out of our analysis since the analysis space willgrow exponentially as more variants, such as rate adaptation and more wirelessflows, are included for consideration. This interference complexity indicates thatalleviating interference by adjusting just one environment setting will not work inall circumstances.In the next chapter, we investigate the wireless interference problem from lay-ers above the link layer, i.e., the TCP and IP layers. We show that network conges-tion is the immediate cause of severe interference and unfair bandwidth allocation.We then develop a strategy that mitigates WiFi interference by limiting IP-layercongestion.41Chapter 3Achieve Fairness by CongestionReductionIn Chapter 2, we showed that the wireless interference in live networks is complexand is hard to resolve in the physical or link layer alone. In this chapter, wepropose a cross-layer approach called Shaper that uses TCP and a central router toachieve a fair bandwidth allocation among competing 802.11 devices.The key idea of Shaper is to trade bandwidth for fairness by throttling through-put at a central router for the involved devices when the unfair bandwidth distribu-tion problem is detected. As we discussed in Chapter 1, the impact of interferenceis limited as long as there is bandwidth available for TCP and 802.11 to retransmitand salvage the dropped packets. Only when all bandwidth has been used, dodisadvantaged devices experience severe performance degradation, even sufferingfrom bandwidth starvation in the worst scenarios.Therefore, a promising solution is to use a shared, central router on the wirednetwork to which all potentially interfering access points are connected, and torestrict the aggregate bandwidth delivered to these devices to prevent 802.11 net-work congestion from happening in the first place. This method mitigates in-terference by allowing 802.11 to schedule virtually every packet delivered intothe wireless network, in effect using the wired router instead of 802.11 to dis-42tribute bandwidth among competing flows. Another important advantage of thisapproach is that it can be easily deployed in existing network management sys-tems, requiring no change to the end-user devices or access points.This chapter discusses the above idea in detail and is mostly based on ourprevious two papers [34, 36]. It starts with an introduction of our motivationand contributions in Section 3.1. Then we propose our throttling solution in Sec-tion 3.2. Section 3.3 presents the evaluation results in our testbed, proving Shaperis effective in dealing with wireless unfairness in a variety of scenarios. The mainchallenge of Shaper, interference detection, is discussed in Section 3.4, and finallywe will summarize this chapter in Section IntroductionIn the last chapter, we showed that wireless unfairness can easily occur in 802.11networks. The culprits of this unfairness problem are twofold. First, the 802.11protocol is not designed to support the cooperation of multiple autonomous sys-tems. Whether a wireless device achieves its fair share of the network dependson the topology, channel conditions and other environmental factors. Let us con-sider the two well-known scenarios described previously, the hidden and exposed-terminal topologies, as shown in Figure 1.1. In the hidden-terminal scenario, sig-nals sent by one sender can be corrupted by another, but not vice versa. In theexposed-terminal scenario, a sender is exposed to many other senders. Even if itdoes not experience any packet loss itself, it loses its fair share because it is forcedto relinquish the airspace more often than the other wireless senders.The second culprit and the immediate cause of this unfairness problem is con-gestion in 802.11 networks. Severe unfairness occurs only when more packetsare pushed into the network than 802.11 can handle. In hidden-terminal scenar-ios, when the aggregate traffic load exceeds the 802.11 capacity and dominatingflows request more bandwidth than their fair share, network utilization is so highthat there is not enough bandwidth in the airspace for losing flows to recoverfrom packet loss using TCP or MAC-layer retransmissions. Similarly, in exposed-43terminal scenarios, the exposed terminal is not given fair airspace access to sendits packets. Frequent packet losses and long delays cause the TCP sender in a los-ing flow to push fewer packets into the network, at which point the flow is doomedto lose its fair network share to others.Wireless networks are getting more congested than ever. Hundreds of millionsof APs and 802.11-enabled laptops have been sold worldwide [18, 22]. Wirelesstraffic has also grown faster than the substantial increases in bandwidth. Previousresearch [55] has shown that wireless users use bandwidth-greedy applicationsjust as they would on wired connections. As the capacity of the network backbonethat connects APs to the Internet increases to Gigabit ethernet, congestion is evenmore likely to occur on the last-hop wireless links. Collected traces have shownthat, even in well planned wireless networks such as hotels [83] and universitybuildings [41], wireless users often suffer from performance degradation causedby packet collisions. As the congestion problems increase, unfairness is morelikely to happen.3.1.1 Motivation: A Cross-Layer Solution to UnfairnessThe correlation between 802.11 network congestion and unfair bandwidth dis-tribution leads us to a surprisingly simple cross-layer solution to addressing theunfairness problem: throttle traffic above the 802.11 MAC layer, at an upstreamrouter. We argue that as long as fewer packets are pushed into the airspace than802.11’s capacity can handle, standard TCP and fair queuing will together allow802.11 to achieve fairness.This cross-layer approach is effective because throttling the aggregated through-put below the network capacity slows winning flows and thus grants losing flowsthe extra airspace they need to deliver packets and recover from packet loss. Suc-cessfully delivered packets in turn open up the TCP sending window for a losingflow. Consequently, a losing flow is now able to push more packets to its receiver.Packets from all flows are queued at the upstream router and are treated equallyby the fair queue management mechanism. This feed-back loop continues until a44max-min fairness is achieved between flows.The key idea of our approach is to prevent 802.11 from making bandwidthallocation decisions. We limit the number of packets pushed to the shared airspaceso that the access points are able to deliver/receive all of them. The bandwidthallocation decision across multiple AP domains is thus designated to the upperlayers at the router.3.1.2 ContributionsThe contributions of this chapter are as follows. First, we highlight the oftenneglected fact that MAC-layer congestion has to be dealt with before addressingunfairness in 802.11 wireless networks. We provide a prototype solution, calledShaper, that ensures fairness by throttling traffic at upstream routers. An interest-ing aspect of this solution is that it can address a challenging wireless problem bymanipulating the traffic over the wired backbone.Second, we show how to address the unfairness problem across multiple ac-cess point domains in a large and cooperative wireless network, where a central-ized router can control the in and out traffic limits for wireless devices. Wirelessnetworks deployed in hotels, airports, business enterprises and university cam-puses all fit this model. Instead of designing new MAC/physical protocols [43, 84,90], introducing complex wireless fair queuing algorithms [68, 72, 80] or adapta-tion schemes [43, 95], Shaper makes adjustments at the network layer using theoff-the-shelf traffic regulating and fair queuing shemes and requiring no modifi-cations to 802.11. It is thus easier to deploy.Finally, we present an in-depth discussion of the system design and challenge.We have already implemented a prototype and used our testbed to verify thatour approach is indeed an effective solution to the wireless unfairness problemregardless of the topology.453.2 Proposed SolutionWe argue in this thesis that standard 802.11, TCP and a fair queue are enoughto provide fairness even under unfavorable network conditions as long as we canprevent wireless congestion from happening. This section describes this idea inmore detail.3.2.1 AssumptionsWe make three assumptions in Shaper. Shaper is designed for use in centrallyadministrated networks such as large-scale campus wireless networks and othercooperative networks, and thus we assume Shaper has control over the centralrouter to which all of the APs connect. We also assume that the Shaper has accessto some global information, including AP association lists, physical AP positions,etc.We consider only the traffic delivered to or received from the Internet, includ-ing both down-link and up-link traffic. Shaper resides in a router and needs to seeall of the traffic. If the two end hosts of the same flow are in the same subnet, arouter does not see the traffic and thus shaping will not occur. Finally, we onlyconsider TCP traffic, the dominant traffic on the Internet. Traffic throttling has noimpact on UDP senders.3.2.2 OverviewGiven the above assumptions, when Shaper detects that the distribution of networkbandwidth is unfair, it will regulate the in and out traffic limits for those APs usingthe shared edge router they are connected to. This throttling scheme must meettwo requirements. First, it must guarantee that the aggregate throughput does notexceed the network capacity. Second, it should slow the dominating flows so thatthe relinquished bandwidth can be assigned to the starved flows.As an initial test of our approach, we repeated the hidden terminal experimentshown in Figure 1.1. This time, we set up a simple traffic shaping rule at the46router connecting S1 to R1, which throttles S1’s throughput to a maximum of 10Mbps. With this simple change, the two flows evenly split the network bandwidth,averaging 10 Mbps each, instead of the initial 19 Mbps to 1 Mbps split.This result shows that, using our approach, shaping traffic at layer 3 can be aneffective solution to wireless unfairness between TCP flows. The obvious tradeoffis that network utilization and round-trip latency may suffer.3.2.3 The Details: A Two-Component SchemeThe shaping procedure consists of two components to ensure that the losing de-vices can deliver as many packets as the others: throttling and fair queuing.ThrottlingThe first component is to throttle the throughput below the aggregate network ca-pacity in a neighbourhood in order to reduce the chance of simultaneous mediaaccess. Once Shaper detects that unfairness is occurring in a neighbourhood con-sisting of two or more APs, it needs only to throttle the aggregate throughput of theaccess points in that area, not specific flows or end-user devices. This is effectivesince each access point is the central point in its domain; each packet sent in theWLAN is either sent to or from an AP.QueuingThrottling traffic for specific access points is not enough to address unfairnesssince it alone does not define how bandwidth is distributed between flows. Ifthe throttled network load remains high and packet loss remains possible due tointerference or network level congestion, then competition between flows willcontinue to lead to unfairness in favor of the winning flows.One approach to solve this is to throttle only the dominating flows. But, thiswould require Shaper to identify which dominating flows are causing problemsto the losing ones. Moreover, tracking over hundreds of thousands of flows ina large-scale network raises scalability concerns. By contrast the fair queuing47approach requires no per-flow analysis or flow management.Fair Queue. Fair queue management algorithms such as RED [47] and SFQ [70]can provide statistical fairness on a per-flow basis with low overhead. For ex-ample, if the aggregated throughput is throttled down to B Mbps and there are Nflows routing through the router, then each flow will be granted a throughput of BNMbps if needed. Our prototype uses SFQ.Non-Overflow FIFO Queue. Configuring a FIFO queue to never overflow can alsoguarantee per-flow fairness. If there are no dropped packets, the TCP window fora sender will continue to grow until it is capped by the sending/receiving buffersize or the bandwidth-delay product. At this point each TCP flow becomes ACKpaced and has a full window size of packets in flight queued at the router. Fairnessis thus achieved. However, a non-overflow queue is not practical since it requiresa queue large enough to buffer all in-flight packets. Furthermore, if the channelconditions cause some flows to drop more packets than the others, then FIFO isnot able to achieve perfect fairness either.3.3 EvaluationWe have set up a controlled 10-node testbed to verify the effectiveness of ourprototypes, and we present the results in this section.3.3.1 Testbed and Traffic Set-upOur testbed consists of six desktops, three LinkSys APs and one router in an 8mx 8m room. Each desktop is equipped with either a Ralink or Atheros-chipsetwireless card. We use altered antennas to attenuate signal strength, and changethe network topology by adjusting transmission-power settings. The desktopsrun Linux kernel with high-resolution timers enabled; the system clockfrequency is set to 1000 Hz, and the APs run OpenWRT. The transmitting rate48is fixed at 54 Mbps. The autorate function is disabled so that topology does notchange during the runs.We use Mxtraf (part of the QStream project [7]) to generate long-term TCPflows between pairs of desktops. In each flow, exactly one desktop, the Mxtrafclient, is connected to an 802.11 AP and the Mxtraf server continuously pushesTCP packets to the client as fast as TCP allows. All traffic is configured to berouted through the sole router in the testbed. The throughput of each flow ismeasured at the IP level reported by Mxtraf.We use up to three competing flows in these experiments. However, it is worthnoting that the effectiveness of Shaper is independent of the number of flows. Itdepends only on the correlation between 802.11 network congestion and unfair-ness. Therefore, the traffic Shaper should remain an effective approach in address-ing unfairness for many-flow scenarios.3.3.2 The TopologiesWe use the testbed to set up the two unfair topologies shown in Figure 1.1 for eval-uation. Shaper helps the losing flow to achieve fair throughput in both cases byalleviating the congestion level in the airspace. Since the impact of throttling andfair queueing on fairness in both scenarios are the same, we will focus only on thehidden terminal topology to present our evaluation results. However, demonstra-tion of the impact of Shaper on the exposed terminal scenario is posted online.1We confirm the topology and link state settings before each experiment byletting two nodes broadcast messages with the same SSID. Since we do not havedirect access to the device firmware, we infer link state using the following heuris-tics. The two nodes are out of sensing range if they are able to transmit at fullspeed. Otherwise, if they transmit about half as fast but are not able to receive anymessages, the link is in sensing state. When two senders send at full speed, wevalidate that one sender causes interference to the other receiver by checking thethroughput information and the number of retransmissions of the other flow.1∼kcai/threeAPs shaping.html49All experiments are repeated three times in our controlled testbed and are alsoconducted late at night to minimize the impact of extraneous interference. Thedifference between runs is found to be low and so only the median values arereported. The results shown in the figures have been smoothed over one-secondperiods.3.3.3 Effectiveness of ShaperThe effectiveness of our shaping approach is illustrated in Figure 3.1. This ex-periment consists of three one-minute phases. The first (losing) flow starts asthe only flow in phase one. A second (winning) flow starts in the second phase(at 60 seconds) when the two flows begin to compete with each other for theairspace. At this point, the network bandwidth distribution is decided by the802.11 and TCP protocols. In phase 3, Shaper starts to throttle the aggregatedbandwidth down to 16 Mbps. For these experiments, Shaper uses HierarchicalToken Bucket (HTB) [4] for traffic throttling and deploys SFQ for queue manage-ment. HTB burst is set to 0; no other change is made.We can see from Figure 3.1a that the first flow achieves 20 Mbps throughputalone. However, immediately after the second (winning) flow starts, the first (los-ing) flow’s throughput drops to around 1-2 Mbps. Recall that this unfairness isdue to the asymmetric topology where the winning flow can corrupt the losingflow and not vice versa. At certain times in phase 2, the losing flow is com-pletely starved, i.e., its TCP sender is forced to delay its transmission using theTCP-layer exponential back-off timer. The winning flow, on the other hand, takesall the bandwidth: it achieves a throughput of 18.5 Mbps on average. This band-width disparity shows that 802.11 and TCP are not able to guarantee fairness whennearby wireless flows from different AP domains compete.Figure 3.1a also shows that Shaper is effective in addressing unfairness. Assoon as we enable Shaper, the two flows split the bandwidth nearly 50-50. Thethroughput of the losing flow is increased from 1 Mbps to nearly 8 Mbps. Notethat the aggregate throughput is limited by the Shaper to 16 Mbps. This trade-off500 60 120 1800510152025Time (S)Throughput (Mbps)  Winning flowLosing flowAgg. ThroughputStart the winning flowStart the Shaper(a) The Impact of Shaper on Throughput0 20 40 60 80 100 120 140 160 18001020304050607080Time (S)TCP Sending CWnd Size (K bytes)  Winning flowLosing flow(b) The Impact of Shaper on TCP Sending CwndFigure 3.1: The Effectiveness of Shaper51between network utilization and fairness will be discussed later in Section 3.3.7.Figure 3.1b illustrates how this works. The sending windows of both flows arecapped by the bandwidth-delay product, at 54 Kbytes and 71 Kbytes respectively.The difference in window size is due to the TCP window auto-tuning feature inthe kernel [46, 85]. When the losing flow is the only flow using the airspace, itssender is able to keep a window size well above 40 Kbytes, and thus it has enoughpackets to saturate the pipe to its receiver. Note that the losing flow has quite alossy wireless channel. Even if the 802.11 and TCP retransmission schemes canquickly recover from packet loss, its TCP window is reduced every time a TCPpacket is lost.In phase 2, the losing flow’s window size is cut down to 1-3 Kbytes, aboutthe size of only one or two packets. This is because the winning flow’s packetshave saturated the shared airspace, causing the losing flow’s packets to be droppedall the time. This constant packet loss in turn causes the losing flow to halve itssending window until it reaches the minimum window size (i.e. one packet), whenthe TCP exponential back-off kicks in. This window reduction, backoff scheme isdesigned to avoid network congestion at routers in wired networks, however, itwill not help the losing flow in the face of wireless packet loss. In fact it causesthe losing flow’s performance to drop even more. The winning flow’s sender istransmitting at full speed with a full-size window — we can see a clear ack-pacedpattern for it.Shaper limits the number of packets that can be pushed into the shared airspacebelow the 802.11 capacity. It also uses fair queuing to further cut the winningflow’s throughput by ensuring the losing flow is de-queued fairly at the router.With the extra unused airspace, the losing flow is more likely to recover frompacket losses using MAC and TCP-layer retransmissions. We can see from Fig-ure 3.1b that increasingly successful packet deliveries allows the losing flow’sretransmission window to increase 15 fold. In this run, it is worth noting thatShaper also makes the winning flow experience more packet losses due to in-creasing noise from the losing flow; its sender, however, can easily recover these52packet drops to keep the sending window high.3.3.4 Impacts of ThrottlingWe have claimed in this chapter that the aggregate throughput has to be throttledbelow the network capacity (24 Mbps for TCP flows in our testbed) in order tomake Shaper effective. In this section, we validate this assertion. Shaper beginswith an aggregated throughput of 10 Mbps for these two flows, and then graduallyincreases the cap by 2 Mbps per minute to 24 Mbps.We can see from Figure 3.2a that Shaper is able to distribute the aggregatedbandwidth evenly between these two flows as long as the aggregated bandwidth isunder 20 Mbps, almost 85% of the best throughput that 802.11g can offer to oneTCP flow. If Shaper allows the aggregate throughput to grow beyond that point, thewinning flow has more packets to send and thus is more likely to corrupt the losingflow’s packets. As soon as TCP and MAC retransmissions fail to recover thosepacket losses over the wireless link, the losing flow will suffer from a significantperformance drop. Figure 3.2a shows that the losing flow gets roughly one thirdof of the 20-Mbps aggregated throughput, and is almost shut out after that.3.3.5 Impacts of Fair QueuingWe’ve also argued that using a fair queue is necessary in order to provide betterfairness between flows when packet loss remains possible. In this section weexamine how the throttler performs without fair queuing.We repeat the hidden-terminal experiment with both both SFQ and FIFO queu-ing. The experiment is repeated in two environments: in one, two flows havesimilar channel conditions where the probabilities that the two flows drop packetsdue to background noise or propagation errors are almost the same. We calcu-late the probability by counting the number of TCP-layer retransmissions for bothflows when they are the only flow in the network. In the other, the losing flowexperiences a more lossy channel than the winning flow. The losing flow alonecan sustain 20-Mbps throughput in both cases though. No queue overflow occurs.530 60 120 180 240 300 360 420 4800510152025Time (S)Throughput (Mbps)  Winning flowLosing flowAgg. Throughput(a) When Using SFQ Queueing Scheme, Two Competing Flows That Have Similar Channel Con-ditions Can Achieve Perfect Fairness Until Airspace Is Congested.0 60 120 180 240 300 360 420 4800510152025Time (S)Throughput (Mbps)  Winning flowLosing flowAgg. Throughput(b) When Using FIFO Queueing Scheme, Two Competing Flows That Have Similar Channel Con-ditions Can Achieve Fairness Until Airspace Is Congested.540 60 120 180 240 300 360 420 4800510152025Time (S)Throughput (Mbps)  Winning flowLosing flowAgg. Throughput(c) When Using SFQ Queueing Scheme, The Losing Flow That Has Worse Channel ConditionsCan Still Achieve Fairness When Competing With The Winning Flow Until Airspace Is Congested.0 60 120 180 240 300 360 420 4800510152025Time (S)Throughput (Mbps)  Winning flowLosing flowAgg. Throughput(d) When Using FIFO Queueing Scheme, The Losing Flow That Has Worse Channel ConditionsCan No Longer Achieve Fairness When Competing With The Winning Flow. But It Still BenefitsFrom Throttling by Reaching A Higher Throughput Than It Would Have Before Congestion Occurs.Figure 3.2: The Impact of Throttling, Fair Queuing and Channel Conditionon Unfairness in Hidden Terminal Topolgies55The results are shown in Figure 3.2.We observe two obvious differences between SFQ and FIFO. First, with FIFO,flow throughput fluctuates significantly more than with the fair queue. Second,FIFO does not ensure fairness among the flows while SFQ does. We can see fromFigure 3.2b that FIFO is capable of ensuring fairness when competing flows facesimilar channel conditions. However, when channel conditions differ, for examplewhen one flow has a more lossy channel than the other, FIFO is unable to keep thelosing flow from suffering unfairly. This effect is shown in Figure 3.1d. The twoflows can achieve 5.85 Mbps (std. 1.03) and 3.58 Mbps (std. 0.75) throughputrespectively when the cap on the aggregated throughput is 10 Mbps. But whenthe cap increases to 18 Mbps, the throughput difference between these two flowsdoubles although the losing flow’s throughput is also increased to 6.18 Mbps (std.1.44). Beyond that point, the losing flow’s throughput starts to drop and fairnessdeteriorates.The reason behind this imperfect fairness is that, when the losing flow dropsmore packets than the winning flow due to increasingly lossy channel conditions,its sender will reduce its sending rate. The FIFO queue thus always contains morepackets from the winning flow, and thus delivers more of its packets to the wirelessnetwork. On the other hand, the fair queue mechanism divides the throughputbetween flows regardless of the proportion of their packets queued at the router,as long as no queue is empty. Therefore, increased packet loss does not change thelosing flow’s packet injection rate, which ensures both flows continue to receivefair access to the wireless network.3.3.6 Prototype ImplementationShaper is a three-stage, adaptive control system consisting of three functional sub-systems: monitor, diagnoser and throttler. The monitor sub-system continuouslymonitors the health of the wireless network and collects traces and statistics for thediagnoser. Based on information from the monitor, the diagnoser infers whethernetwork congestion and unfairness have occurred. If so, it instructs the throttler56to shape the traffic of the affected access points. We have implemented two pro-totypes of Shaper running on a wireless testbed.In the first prototype, a wireless end-user device passively monitors the net-work when it experiences poor performance, indicated by low throughput, fre-quent 802.11 retransmissions or high latency. During the monitoring period, itcaptures any packet in the air and records the MAC addresses in the packet header.Then, the device piggybacks these MAC addresses in a “help” message. Thismessage is sent to its access point which in turn forwards it to the backend router.Having received such a message, the router uses the global client-AP associationlist to determine a list of access points with which the reported devices are asso-ciated. Then it uses the throughput accounting tools such as the netfilter/iptablesaccount extension to examine the throughput of these access points. If the ag-gregate throughput is at the network capacity and there exists uneven bandwidthdistribution, then the shaping action will take place.The second prototype implements the router-does-it-all model. We record thethroughput of each access point at the router using the ip account iptable mod-ule [5]. We have also programmed a kernel netfilter module and an iptable exten-sion that implement two monitoring functions at the router. One is to count thenumber of TCP retransmissions for each access point. When forwarding a packetfor a flow, the router uses the sequence number to infer whether a packet deliv-ery or a reception has failed over wireless. The second is to track the round-triplatency between the router and an end-user wireless device, an indication of busyairspace. When these metrics together with throughput division between devicesindicate an unfair network bandwidth allocation, then Shaper will start throttlingthe traffic.A demonstration of both prototypes are available online.2 Note that we assumestatic interference relationship in both prototype implementations. Accurate inter-ference correlation is however a critical challenge in live wireless networks where2 Prototype 1:∼kcai/client ask for help.htmlPrototype 2:∼kcai/router does all.html57interference relationship is consistently changing. We will detail and address thischallenge in Chapter The Trade-OffsThe trade-off that our approach makes is between network utilization, latency andfairness.Overall Network Utilization TradeoffWe have already seen from Figure 3.2 that Shaper can provide fairness only whenthe network utilization is under 20 Mbps in our testbed. Beyond that point, eventhough network utilization continues to increase, fairness can no longer be pre-served. In fact, this throttling limit is largely decided by the channel conditions ofthe losing flow, i.e., how much extra bandwidth the losing flow needs to salvagefrom the dropped packets to sustain its “fair” bandwidth share. In our controlledtestbed, this throttling limit is tuned between 16 Mbps and 20 Mbps.However, it is worth noting that if packet loss of the losing flow is due tobad channel conditions (e.g., weak signal to the background noise) instead ofairspace competition, then throttling other devices’ throughput will not improveits performance. In this case, throttling will only reduce the overall network utilitybecause it harms the performance of winning flows without helping the losingflows. The implementation of Shaper should be aware of this pitfall.Note that when devices are running at different rates, there is a difference be-tween time fairness [90] and throughput fairness. The time fairness allows thecompeting devices to equally share the channel access time, while the throughputfairness guarantees that they will achieve the same throughput. The difference be-tween these two fairness schemes is due to the fact that a wireless device runningat a lower rate will take much longer time to send a packet than one using a higherrate. Therefore, achieving a throughput fairness enables the slower devices to oc-cupy much longer channel access time than the others, resulting in significant lossin overall network utility. Therefore, in our opinion, time fairness is the fairness580 60 120 180 240 300 360 420 4800100200300400500600Time (S)TCP RTT (ms)  051015202530Throttled Rate (Mbps)Strong flow TCP RTTWeak flow TCP RTTWired−part TCP RTT Throttled RateFigure 3.3: The Impact of Shaper on TCP RTTthat Shaper should try to achieve [89]. Implementing such a time fairness system,however, is out of the scope of this thesis.TCP RTT TradeoffThrottling the throughput at the router can delay the time packets being injectedinto the wireless network and thus has an adverse impact on the network latency.In this section, we conduct an experiment to evaluate the impact of Shaper onthe TCP Round Trip Time (RTT). This experiment consists of 40 TCP flows: 20flows from the winning devices and 20 from the losing devices. All traffic is sentthrough the router and an extra 50ms delay is added to simulate cross-continenttraffic.59In the first run, we remove the wireless links from the routing paths, and dis-able Shaper. The resulting RTT is used as a baseline metric — the best RTT thatcan be achieved when 40 flows send at full speed without shaping and SFQ. Inthe second run, we enable the SFQ Shaper and add the wireless links back to mea-sure the new RTT values. The results of both tests are presented in Figure 3.3. Notshown there is that Shaper helps the flows to achieve fairness when the aggregatedthroughput is below 20 Mbps.We can see from Figure 3.3 that Shaper does impose a RTT penalty: comparedto the baseline RTTs, throttling the aggregated throughput down to 10 Mbps resultsin 60-ms (std. 22ms) and 63-ms (std. 25ms) increases in RTT for both flows. Thisis not surprising since slowing the rate that the router drains its queue will causeadditional queue delay to the flows. It is worth noting that the weak flows sufferfrom high end-to-end latency when unfairness occurs as well. This substantialincrease in RTT, much higher than Shaper’s latency overhead, is caused by thefrequent wireless retransmissions, when the highly-loaded network stops Shaperand 802.11 from working.3.4 Challenge: Interference DetectionOne critical challenge remains for Shaper to be effective in large 802.11 networks:it must determine which nodes are mutually interfering so that it can shape all ofthem as an unit to deliver fairness to all of them.The problem of identifying mutually interfering devices has drawn a lot of at-tention from the research community [74, 77, 82]. However, most of the priorwork has considered research testbeds - statically configured networks wherenodes are immobile and traffic is constant. Even with these simplifying assump-tions, inferring interference relationships between devices is not trivial. The com-mon approach relies on an explicit measurement phase. Each device is asked tobroadcast/unicast in turn [77, 82] (or a pair of nodes to send packet simultane-ously [74]). Other nodes passively listen to the traffic to obtain RSSI/SNR valuesof all the other nodes in the network, used for later interference level analysis60and clustering. This approach requires not only careful synchronization betweendevices but also a shut-down period of regular network traffic.For the deployment of Shaper, these techniques cannot be applied for a num-ber of reasons. Shaper does not have control of the end-user devices to havethem send packets. Moreover, network dynamics can change the interference re-lationship between devices rapidly. Finally, we believe it is unlikely that users oradministrators will find it acceptable to periodically shut out the network activityin an existing wireless network.Our interference detection system uses online user traffic for interference cor-relation. Doing so has three advantages. First, it is able to adapt to environmentchanges such as node mobility or traffic variations. For example, even if a pairof devices are within interference range, Shaper needs to throttle their traffic onlywhen their total throughput demand exceeds the 802.11 network capacity. Second,it does not require control of the end-user devices and thus is easy to be deployedin real networks. Finally, this approach does not require an in-field offline mea-surements, which can last hours even days to complete.We have come up with such a passive interference detection system calledWireless Online Interference Detector (VOID), to be described in Chapter 4.3.5 SummaryThe 802.11 protocol is not designed to support the cooperation between multipleautonomous systems. One of the unfortunate consequences of wireless interfer-ence is that the shared airspace resource can be unfairly distributed to competingdevices.In this chapter, we emphasize that congestion in 802.11 networks is the im-mediate cause of throughput unfairness. Based on this correlation, we argue thatstandard TCP and fair queuing together are sufficient to address unfairness, aslong as we can prevent network congestion. A detailed analysis has been pro-vided. Compared to alternative approaches, our approach is easier to deploy sinceno changes are required on access points or client devices.61We have used a testbed to validate that this cross-layer approach is indeed ef-fective. We show that, even in the worst scenarios such as hidden-terminal andexposed-terminal topologies, throttling the aggregate throughput below the con-gestion level can allocate bandwidth evenly between all competing devices. Wealso evaluate the effectiveness of different queuing schemes on wireless fairness.62Chapter 4Passive Interference Detection UsingOnline TrafficAs discussed in Chapter 3, knowing which devices interfere is the first step tominimizing interference, improving efficiency and delivering quality networkingperformance to all competing devices. This knowledge of interference relation-ship, however, is extremely difficult to obtain without either taking a running net-work offline for measurements or having client hosts monitor and report airspaceanomalies, something typically outside the control of network administrators.In this chapter we describe a novel technique we have developed to revealwireless-network interference relationships by examining the network traffic ata wired router that connects wireless domains to the Internet. This approach,which we call Wireless Online Interference Detector (VOID), searches for corre-lated throughput changes where traffic from one node causes a throughput drop atother nodes in its radio range. By doing so, VOID is able to identify each node’sinterference neighbors using a single set of performance data collected from awired-network router.We can see from Figure 3.2 that the throughputs of the interfering devices areobviously correlated under congestion. That is, when network is saturated, anincrease in one device’s throughput indicates a throughput decrease for the other63competing devices. VOID explores this adverse correlation in devices’ throughputsto identify the interfering devices under congestion.The crux of VOID is a statistical correlation engine using Multiple Linear Re-gression (MLR). The input to this statistical engine is the throughput measure-ments collected from the central router and the output from the statistical engineis a list of interference sets, indicating which and to what extent certain devicesare interfering.In this chapter, we describe this passive online interference detection systemin detail and show that VOID is able to accurately correlate interfering devices to-gether and effectively discriminate interfering devices from non-interfering ones.The content in this chapter is mostly based on our prior VOID paper [37]. In Sec-tion 4.6, we present our experiment results using live traces collected from UBCwireless network.We start this chapter with an introduction of the general motivation behindVOID in Section 4.1, and describe its methodology in Section 4.2. The limitationsof VOID are discussed in Section 4.3. We then present our evaluation results inEmulab and UBC WiFi networks in Section 4.5 and Section 4.6 respectively. InSection 4.7, we present the interference relationships and patterns we found in thelive networks. Finally, we summarize in Section IntroductionThe prerequisite for many interference mitigation systems, including Shaper, tobe effective is to be able to answer the following question: given a device thatis experiencing significant performance degradation, which nearby devices are itscurrent interferers? The state-of-the-art approach to estimate interference rela-tionships is to take the network temporarily offline and to inject synthetic trafficfor interference measurements [69, 73, 74, 77, 82]. Each node in turn sends uni-cast or broadcast packets into the airspace while other nodes record informationsuch as signal strength and packet delivery ratios. These measurements are thenused to seed various interference models [69, 77, 82] to predict network perfor-64mance at run-time. The PIE work [88] instructs the access points to record thetime and successful transmission rate when they transmit packets, and uses thisinformation to infer which transmitters are mutually interfering. It is an onlineapproach using only the live traffic, however, it still requires driver modicationand cooperation from both APs and mobile clients.In this chapter, we present VOID (Wireless Online Interference Detector), anapproach that utilizes statistical methods to recognize the interference patternsfrom online per-node throughput summaries taken from upstream wired routers.It requires no network profiling. Its methodology is based on the observation that,when the airspace is congested, changes in a victim node’s throughput are moretightly related to its interferers than to other irrelevant devices. The pattern is thata victim node sends more when its interferers send less and vice versa.VOID requires only information available at the wired network, needing nei-ther cooperation from the end-user devices nor modifications to the access points.Moreover, since the core of VOID is a statistical interference correlation enginebased on multiple regression, which can detect multiple interferers to a victimnode in just one measurement round, VOID is capable of producing an interfer-ence map in real time. The complexity of its MLR engine is O(K2N) where Nis the total devices considered and K is the number of throughput samples. Weshow in our evaluation that, in the worst scenario, VOID is capable of identifyingthe interfering devices from 100 candidates within 100 seconds. While in livenetworks, it usually only takes less than a second.All these benefits are derived from the key difference between VOID and otherapproaches: VOID does not directly measure the impact of RF characteristics oninterference in a given network, rather it statistically infers interference relation-ships by measuring throughput changes in the upper network layer.However, note that VOID is not designed to produce the static physical-layerinterference map as the offline approaches do. Rather, its goal is to find the culpritsof throughput degradation for a victim device at a given time. Even when a staticinterference map indicates that it is possible for a device to interfere with a victim,65VOID does not necessarily flag it as long as it is not currently causing the dropin performance for the victim (when it is not sending data, for example). Theinterference map VOID produces is dynamic; it depends on the current networktopology or traffic profile, and is almost always a subset of the static interferencemap.We have evaluated VOID in two different settings: One in the Emulab wirelesstestbed [94], the other in the 802.11 network in two UBC buildings, one academicand one residential. In Emulab where the underlying interference relationship ispre-determined, we set up a variety of controlled multi-hop, multi-flow scenariosto evaluate the effectiveness and accuracy of VOID. In the UBC buildings, weevaluate how frequently interference occurs in live settings with real traffic. Oneproblem with this real workload is that we do not know the ground truth againstwhich our results should be compared. As we discuss in Section 4.6, we overcomethis methodological challenge using a complement of techniques that estimate theground truth in various ways.Our evaluation results show that VOID is indeed effective, managing to cor-rectly cluster interfering devices in all topologies we set up in Emulab. Moreimportantly, VOID is able to detect hundreds of interfering pairs in each buildingduring a week span, and more than 97% of the detected interfering devices operateon the same channel.4.2 MethodologyVOID uses a statistical method called Multiple Linear Regression (MLR) to cor-relate interfering devices by recognizing the interference patterns (throughputchanges) from the wired logs collected at the central routers. In this section, wedescribe its methodology in detail.66Goodput change for an interfering nodeGoodput change for a victim node(a) Pattern 1 (b) Pattern 2Figure 4.1: Interference Pattern between the Interfering Node and the VictimNode. On the Left, the Victim Node’s Throughput Decreases as the Interfer-ing Node’s Throughput Increases. On the Right, the Victim Node’s Through-put Increases as The Interfering Node’s Throughput Decreases.4.2.1 Interference Patterns Under CongestionThe causes of signal interference can be quite complex to analyze in real networks,since they depend on transmission power, signal propagation, node topology, en-vironment layout or even time of day. But in Chapter 3, we demonstrate thatthe changes of underlying interference relationships can be reflected in changesto network throughput. Given a victim node and its interferers, these interferencepatterns are: as the interferers’ throughputs increase, the victim’s decreases and onthe other hand, when the interferers’ throughputs decrease, the victim’s increases,as illustrated in Figure 4.1.VOID exploits this correlation to infer interference relationship by searchingfor these patterns in the wired trace. Note, however, that these patterns only occurwhen the wireless network is congested since the throughput of the victim nodewill not drop as long as the overall network traffic does not exceed the networkcapacity. On the other hand, when the network is not completely congested, theMAC-layer and TCP packet recovery schemes are capable of salvaging droppedpackets themselves.In this section, we first give an overview of the statistical model VOID uses67and then discuss its limitations when being deployed in real settings.4.2.2 Statistical MethodsIn VOID, we assume interference relationships are linear, that is, the throughputthat the victim node can achieve is approximately linearly related to the (negative)throughputs of its interferers. When adding a new interferer into the network, itsthroughput will cause an additional degradation in the victim node’s throughputin the presence of other existing interferers.Note that this linear interference model is not intended to exactly model theMAC-layer interference relationship — MAC-layer retransmission, exponential back-off and interference summarization could lead to a much more complicated model.Rather, this linear model is a simplified interference estimation over a series of IP-layer throughput-change samples.One-Interferer ScenariosLet us take one victim node and one interferer for analysis. If the victim node cansense the interferer’s signal, then it has to back off while the interferer is transmit-ting. On the other hand, if the interferer is a hidden terminal to the victim node,then the victim’s packets will be corrupted by the interferer’s signal. In either case,the MAC-layer interference can be modeled by the correlated throughput changesat the upper IP layer. The linear regression engine is thus used to search for thesethroughput-change patterns in the trace and use them to measure, on average inthe given time window, how much damage each of the interferers has caused tothe victim node’s throughput. If due to any reason that two devices’ throughputchanges do not seem to be coordinated, then they will not identified as interferingeven if they do.Therefore, in these simple one-interferer scenarios, Correlation Coefficient(CC) can be used to calculate the degree of correlation between two devices’throughputs. The CC value (ρ) can take on any values in the range [-1, +1],where a value close to +1 imples strong positive linear correlation, a value close68ρ1,2 ρ1,3 ρ1,4 ρ1,5 ρ1,6 ρ1,70.019 0.035 -0.004 -0.013 -0.37 -0.29Table 4.1: An Example Showing that Correlation Coefficient is Ineffectivein Detecting Interferers for a Victim Node in Many-Interferer Scenariosto 0 implies no linear correlation, and a value close −1 implies strong negativelinear correlation, i.e., interference. Our evaluation in typical two-flow hidden-and exposed-terminal scenarios has shown that a strong interferer can result in acorrelation-coefficient value below -0.9.Interference relationships in real networks can be, however, quite complex.A victim node will be under the influence of many interferers, and interferersthemselves can be affected by other nearby interferers. The impact of a specificinterferer on the victim node might be hidden from the pair-wise observationsused in calculating the CC value.To demonstrate this problem, we conducted an seven-flow experiment in whichall flows mutually interfere with each other. These flows were all streaming withUDP traffic, ensuring that the airspace was saturated. Table 4.1 presents the corre-lation coefficient values between flow 1 and the other six flows. The interferencerelationship between flows is not obvious between any pair of devices.The correlation coefficient is unable to detect interference since it only checkstwo devices at a time. In a typical environment where the throughput of one deviceis related to many others, we must resort to a more expensive statistical method,Multiple Linear Regression (MLR), to take into account the simultaneous effect ofseveral interferers.Many-Interferer ScenariosTo identify the effect of k potential interferers (I1, I2, . . . , Ik) on a victim node (V ),we assume a linear relationship between their throughput values. If we let thethroughputs of the interferers be (x1,x2, . . . ,xk) and that of the victim node be y,69this linear relationship is expressed in Equation 4.1. We sample these variables ntimes and feed the values into Equation 4.1 to estimate the coefficients β . Eachsample may also introduce independent error ε , a variable assumed with meanzero and constant variance.yi = β0 +β1x1i +β2x2i + . . .+βkxki + εi (i = 1, . . . ,n) (4.1)β0 indicates the throughput the victim node would achieve if all the otherinterferers are idle, while βi suggests the additional impact of potential interfererIi on the victim node’s throughput when other interferers’ throughputs are heldconstant.If Ii is currently interfering with a victim node (i.e., Ii is a true interferer), thenβi should be a negative number. If βi is close to 0 or a positive number, then Ii maybe a false interferer. A positive number indicates that Ii may in fact be helping thevictim node by reducing the throughputs of other interferers.Solving Multiple Regression. Solving multiple regression is to estimate the coef-ficient values to best-fit the sampled data. It is convenient to express Equation 4.1in matrix notation as shown below.y = Xβ + ε (4.2)where,y =y1y2...yn, X =1 x11 . . . xk11 x12 . . . xk2.........1 x1n . . . xkn, β =β0β1...βk, ε =ε1ε2...εn.The least squares estimator βˆ for the regression coefficients in β isβˆ = (XT X)−1XT y (4.3)70where βˆ is calculated to minimize the residual sum of squares, SSres.SSres =n∑i=1(yi−X βˆ )2 (4.4)Determining The Best Fit. The coefficient of determination, R2, measures howwell a regress model fits the sampled data. It is a value between 0 and 1; the highervalue R2 is, the better the data fits our linear model. In VOID, for example, whenR2 equals 0.9, this suggests 90% of the victim node’s throughput change (y) canbe explained by changes in the potential interferers’ throughputs (X).R2 =∑ni=1(yi− y¯)2−SSres∑ni=1(yi− y¯)2 (4.5)where y¯ = ∑ni=1 yin .Detecting Interferers. The interferers included in the initial multiple regressionmodel are only the candidates; the resulting regression model might contain falseinterferers that contribute little or nothing to the victim’s throughput variation.We use forward selection to select the most significant interferer to add to theregression model one at a time, until it no longer improves the model coefficientof determination R2 by adding any more interferer (in other words, the residualsum of squares cannot be reduced any more).4.3 Limitations of VOIDIn contrast to the other RF/MAC models introduced in prior work [69, 77, 82], ourinterference model is much simpler. This simplicity comes from the fact that ourmodel aims to detect the interference between a potential interferer and a victimnode, while the prior models are designed to accurately predict the throughputof every device under interference. Because of this difference in goals, the other71models must capture the details of the MAC layer and radio layer characteristics.VOID, on the other hand, examines only wired-network throughput changes.As a result, VOID can only detect interference between nodes when (a) theirtraffic has congested the network, (b) the interfering node is currently able tohave a significant impact on the victim node and (c) the victim node is able topromptly respond to the changes in the interferer’s throughput. Each of thesethree limitations is described below.No Congestion in 802.11 networks. Throughput-change interference patternsonly occur when the wireless network is congested. Previous work [34] has shownthat the average throughput of the victim node will not drop as long as the demandfrom both devices does not exceed the network capacity. This is because, whenthe airspace is not completely congested, the MAC-layer and TCP packet recoveryschemes are capable of salvaging dropped packets themselves. The victim nodecan use the airspace when interfering nodes are idle.Therefore, VOID is unable to correlate interference in non-congested scenar-ios. However, it is less interesting to correlate interference in those scenarios sinceinterferers have no real impact on the performance of the victim node.Insignificant Interferer Under Congestion. Even in a congested environment, therelationship between an interferer and the victim node can still be obscured if itscurrent impact is not significant compared to that of others in a given time window.For example, consider a victim node A that could be affected by two interferers Band C. If B is transmitting at full speed while C does not have much traffic to sendright now, the current throughput degradation of A will be caused (mostly) by B.While C would interfere more if it were sending more data, it is currently not asignificant source of interference for A and will not be identified by VOID.In this way, VOID can only detect the significant interferers to a victim giventhe current traffic profile, not a complete interference map. However, given an-other window, when the throughput of C increases, VOID will identify C since its72impact on A has become detectable in the trace.Delay in Response. VOID relies on the prompt response of the victim node tochanges in the interferer’s throughput. In most cases, this will be the case – avictim’s throughput will quickly increase with less interference, and decrease withmore, however, in some scenarios, it may take a much longer time for a victimnode to make use of free network capacity; the longest MAC-layer back-off timefor a 802.11b sender is about 21 ms (1024 * 20 + 50 µs). To take this time intoconsideration, the sampling period should be long enough to detect the responsefrom the victim nodes.Note that a TCP sender could have been put into TCP starvation due to continu-ous MAC-layer packet losses. In this scenario, the TCP sender is not attempting tosend any packet for tens of seconds or minutes. Since VOID cannot observe trafficfor the starved devices at the router, it is not able to correlate the set of interferers.We believe this is not a problem with VOID, but rather a problem with TCP [71],however, solving this problem is out of VOID’s scope.UDP Traffic. VOID presumes the IP-layer throughput sampled at the router isan indicator of MAC-layer goodput over the wireless links. This assumption isobviously not always true for UDP traffic.4.4 ImplementationVOID is implemented with a pipeline consisting of three subsystems: trace collec-tion, throughput analysis and interference correlation. In a small network, tracecollection can be simply done using network tools such as tcpdump [9]. In a largenetwork, on the other hand, trace collection overhead can be unloaded from therouter using passive port mirroring1 to transfer traffic along a parallel data planeto a dedicated trace collection machine.1 mirroring73The throughput analysis subsystem needs to produce a time series of through-put stats for all devices observed in the trace. We use WyPy [67], an online trafficanalysis tool, to break the captured trace into small time buckets and then aggre-gate the throughput per device in each bucket. WyPy is able to quickly output thethroughput series — it takes less than half a second to analyze a one-second tracecollected in all our testbed scenarios and live UBC wireless network. The through-put time series is then fed into the interference correlation subsystem, which usesSciPy [8] to implement the multiple linear regression engine to detect the interfer-ers from all candidate devices.4.5 Evaluation in Emulab TestbedIn this section, we evaluate VOID’s effectiveness using the Emulab wireless testbedat Utah University [94]. We control the interference map in this environment toevaluate if the multiple regression engine of VOID is effective in determining theset of interferers to a victim node, and if it is able to adapt to network dynamics.4.5.1 Emulab Experiment SettingsThe testbed consists of a total of 72 wireless nodes spreading over two floors inthe Merrill Engineering Building. We conduct most of our experiments on twoclusters, the 36-node pc-600 cluster on the third floor and the 13-node pc-3000wcluster on the fourth floor as highlighted in Figure 4.2. The 36 nodes in the pc-600 cluster are deployed in one 300cm x 224cm grid. All nodes in the grid areable to communicate with each other; in other words, they all interfere. On theother hand, the 13 pc-3000w nodes are deployed in a 360 m x 100 m floor; anynode takes at most five hops to reach any other node in the cluster. For reference,we call the pc-600 cluster the “single-hop cluster” and the pc-300w cluster the“multi-hop cluster”.In each experiment, the wireless nodes are grouped into AP-client pairs. Thesepairs are selected to build various interference topologies. Each wireless node is74Figure 4.2: The Emulab Wireless Testbed at Utah75equipped with at least one Atheros card with AR5212 chipset, running the Mad-Wifi driver [6]. In all scenarios, the transmission power is set to minimum, thetransmitting rate is fixed at 36 Mbps and the autorate function is disabled so thata topology does not change during an experiment.We use the D-ITG [1] traffic generator to set up 5-minute TCP flows betweena server and the wireless clients. Unless stated otherwise, each flow generates anaverage traffic demand of 22 Mbps. This high throughput demand is set to ensurethat 802.11 network congestion does occur. All traffic is configured to be routedthrough the sole router in the testbed. We use ipt account netfilter kernelmodule [5] to log the throughput information of all the flows at the router everysecond. VOID’s MLR engine runs over a 5-minute-window trace, providing 300points per device per time window.4.5.2 Testbed ExperimentsThe testbed experiments are conducted to answer the following three key ques-tions: (1) Is VOID able to extract the pair-wise interference relationships in com-plicated many-to-many interference scenarios? (2) Is VOID able to discriminatetrue interferers from the false ones? (3) Is VOID able to adapt to network dynam-ics?Typical Two-Competing-Flow TopologiesIn the experiments described in this section, we consider only two competingflows. In the hidden terminal scenario, four nodes are chosen from the pc-3000wcluster so that the victim flow can only achieve 1 Mbps throughput while theinterfering flow achieve a throughput over 20 Mbps. In the exposed terminalscenario, the two wireless flows are chosen from the pc-600 cluster and they splitthe bandwidth 50-50.Hidden Terminals. The results from the hidden-terminal experiment are shownin Table 4.2. The coefficient value β0 (-0.88) indicates that the interference level76β R2[−0.882.1e+07]0.90Table 4.2: Results of Hidden-Terminal Topologyβ R2[−1.032.55e+07]0.85Table 4.3: Results of Exposed-Terminal Topologybetween these two flows are strong. The β1 with a value of 2.1e+07 indicates thatthe victim node could have achieved a good throughput of 21 Mbps if it was theonly flow in the network. The R2 indicates that the interferer contributes 90% inthe victim node’s throughput degradation.Exposed Terminals. As expected, the results shown in Table 4.3 from the exposed-terminal experiment tell us the same story: the victim flow is strongly interfered bythe other interferer in the experiment, even the victim flow in this setting achievesa much better (10 times more) throughput than that in the hidden-terminal case.Note that, even though we fix the rate to 36Mbps, the flows in the pc600 clustercan achieve a throughput of 25 Mbps, in contrast to the flows in the pc3000wcluster can only achieve a throughput of 21 Mbps. This difference is reflected bythe parameter β1 in both settings.Many-Interferer ScenariosWe conduct this experiment in the single-hop cluster in which seven wireless flows(14 wireless devices) mutually interfere. We can see from Figure 4.3 that the in-terference relationship among these seven flows is quite complicated — checkingany pair of flows reveals only a weak interference relationship between them. For77Figure 4.3: Throughput of 7 Mutually Competing Flows.β1,2 β1,3 β1,4 β1,5 β1,6 β1,7 R2-0.78 -0.82 -0.75 -0.86 -0.88 -0.85 0.96Table 4.4: MLR Coefficients β for Flow 1example, if we check flow 1 and flow 2 only, the correlation between them is only0.019 and R2 is only at 0.08. However, the interference model’s significance (R2)increases when more and more interfering flows are added for consideration. Inthe final model in which all the seven flows are taken into account together, theβ values in Table 4.4 suggest that all the other six flows are interferers to flow1. The coefficient β1,2 is now -0.78, indicating a strong interference relationshipbetween flow 1 and 2. The R2 of the final regression reaches to 0.96, means 96%of the variation in flow 1’s throughput can be explained by the throughput changesof the other six competing flows.78Round # Potential Interferers β R2 Interferer Selected1F2 -0.88 0.97F2F3 0.002 5.7∗ e−4F4 -0.010 4.0∗ e−52F2,F3[−0.85−0.02]0.89NoneF2,F4[−0.87−0.12]0.9Table 4.5: A Step-by-Step Illustration of the Forward Selection Process.Finding The InterferersIn this section, we evaluate whether VOID’s repeated forward selection process iseffective in filtering the irrelevant active devices from interference clustering.We select three groups of wireless flows. The first group includes two flows,F1 and F2, from the single-hop cluster; the other two groups contain only one floweach, F3 (pcwf12 → pcwf14) and F4 (pcwf3 → pcwf5), selected from themulti-hop cluster. There is no interference between groups. The two flows in themulti-hop cluster do not interfere with the two flows in the single-hop cluster.We keep all these four flows running at full speed. The two irrelevant flowsare able to transmit at 20M bps each while the two interfering flows can only sendat 10M bps. The step-by-step forward selection procedure for F1 is illustrated inTable 4.5. The first round of VOID runs regression on each of the possible inter-fering flows against flow F1. The results of the three pair regressions show that F2is the most significant interferer among the three. We can see from Table 4.5 thatR2 of model F1 and F2 reaches 0.97, while R2 of the other two models are at leastthree degrees of magnitude lower. Therefore, F2 will be selected to be included inthe final interference model.In the second round of the forward selection process as described in Sec-tion 4.2.2, the algorithm considers adding more devices into the interference model.There are two possible three-candidate models by including either F3 or F4 into79S1 S2 S3 S4 S5Figure 4.4: Physical Pair-Wise Interference Mapthe two-interferer model. But as illustrated in Table 4.5, adding more interfererinto the regression actually results in less accurate models. The R2 of the modelincluding F3 drops by 0.08 while that of the model including F4 drops by 0.07.VOID therefore will not include any additional device into the final interferencemodel, and conclude that only F2 is the only interfering flow to F1.Dynamic Interference MapsIn this section we demonstrate the VOID’s ability to adapt to network changessuch as traffic variations. We select five flows (pcwf12 → pcwf14, pcwf9→ pcwf17, pcwf7→ pcwf8, pcwf7→ pcwf11, pcwf3→ pcwf5) fromthe multi-hop cluster and conduct pair-wise experiments to measure the pair-wiseinterference relationship. The full (static) interference map is shown in Figure 4.4as a reference. Each arrow in the figure indicates the existence of interference andits direction. Note that the two flows in the middle F2 and F3 are affected by allthe other flows.We start from a completely congested network and then gradually reduce thethroughput demands of the flows. Figure 4.5 illustrates three interference mapsthat are completely different, due to the changing traffic profiles. These maps,80however, are all subsets of the underlying physical pair-wise interference map.In a completely congested environment, the bandwidth allocation is 20 Mbps,0.5 Mbps, 0.5 Mbps, 20 Mbps and 12 Mbps, for these five flows respectively.Given this traffic profile, the interference between F2 and F3 is not significant andthus cannot be detected by VOID. We can see from Figure 4.5a that these flowsare grouped into two clusters in the final interference map: F1 is the main culpritfor F2’s throughput degradation while F4 and F5 dominate F3.We then reduce the average throughput demand of each flow to 8 Mbps foreach flow. The three dominating flows F1, F4 and F5 do not experience any bottle-necks in this scenario; the bandwidth available to them is greater than what theyneed; these flows do not appear to be affected by any other flows. However, theydo impose interference of 24 Mbps in total on F2 and F3, the two flows that cannotmeet their throughput demands.Finally, we reduce the individual throughput demand to 4 Mbps. Now whetherF2 can achieve its throughput demand depends largely on F3 and vice versa. There-fore, only the throughput of this pair of nodes has the interference patterns thatVOID looks for.4.6 Evaluation in Live UBC WiFi NetworksWe are able to evaluate VOID’s effectiveness using UBC campus wireless networksand, in the section, we present the evaluation results with live traffic. UBC wirelessnetwork consists of more than 1700 APS running with Cisco equipment and soft-ware. We chose two representative buildings for our analysis. One is UBC High-rise — a residential building was built in the ’s that does not provide wired Internetaccess. It is, however, covered by 27 APs, all 14 floors but one are equipped withtwo APs. Another building is a newly-built research center, Life Sciences Cen-ter (LSC). It is the largest academic building in UBC, consisting of five floors andcovered by 40 APs. These wireless APs are already carefully placed and operateon overlapped channels on both 2.4G and 5G band to minimize the interferencein the network. Moreover, the Cisco Wireless Control System (WCS) deploys the81S1 S2 S3 S4 S5−0.84−0.74−0.32−0.42−0.64−1.3−1.61(a) Interference Map in a Congested Environment. The β Values below -1 Are Due ToMAC-Layer Retransmissions.S1 S2 S3 S4 S5−0.52−0.62−0.64−0.87−0.94−0.75−0.47−0.79(b) Interference Map in a Medium-Congested EnvironmentS1 S2 S3 S4 S5−0.97−0.80(c) Interference Map in a Low-Congested EnvironmentFigure 4.5: Dynamic Interference Map82CleanAir technology that can make automatic channel adjustments to optimizewireless coverage around the interference, including those from non-WiFi devicessuch as microwaves or wireless phones.We captured one-week wireless traffic from each of the two buildings at thecentral controllers. The traces were collected in Highrise from Mar. 22, 2009to Mar. 28, 2009, and those in LSC were collected from Apr. 13, 2009 to Apr.19, 2009. These traces were later anonymized. Note that the traffic captured isonly what the controllers see on the wire (i.e., traffic between the controllers andthe wireless APS), it does not capture any last-hop wireless traffic on the air suchas 802.11 ACK, beacons, etc. The internal wireless traffic such as a file transferbetween two clients within the same building are also not captured. In these twoweek monitoring period, we were able to capture 1.06 billion packets in Highriseand 0.65 billion packets in LSC.In addition to capturing the traces from the central controllers, we also pulleda stream of the SNMP data from server, including wireless clients’ MAC addresses,channels and their associated APS. This information is not used by VOID, but weuse this information for our false-positive and false-negative analysis and inter-ference map correlation. For instance, we can determine if two devices found tobe interfering are operating on the same channel. The SNMP polling frequency isthrottled at once every 10 minutes as negotiated with the UBC wireless networkmanagement group to not cause any performance issue during peak hours.Figure 4.6 illustrates the weekly throughput and active-device trend in High-rise and LSC. The trends in both buildings clearly follow a diurnal cycle: LSChas a higher network usage during the day while Highrise sees its traffic peak atnight. It is easily understood as LSC is a research building where there are moreactivities during the day time while Highrise is a residential building where peo-ple leave home for work for the day and come back home at night. Based onthis information, we conduct most of our experiments in Highrise during the 6-hour peak hours from 6:00 PM to 11:59 PM and from 10:00 AM to 5:59 PM inLSC. Note that in both buildings, the aggregated throughput peak is usually below8303/22 03/23 03/24 03/25 03/26 03/27 03/28 03/29Throughput Trend from Mar. 22, 2009 to Mar. 28, 2009)010 Mbps20 Mbps30 Mbps40 Mbps50 MbpsThroughputWeekly Throughput Trend(a) Highrise Throughput03/22 03/23 03/24 03/25 03/26 03/27 03/28 03/29Active Device Trend from Mar. 22, 2009 to Mar. 28, 2009)01020304050DevicesWeekly Active Devices Trend(b) Highrise Active Devices8404/13 04/14 04/15 04/16 04/17 04/18 04/19 04/20Throughput Trend from Apr. 13, 2009 to Apr. 19, 2009)010 Mbps20 Mbps30 Mbps40 MbpsThroughputWeekly Throughput Trend(c) LSC Throughput04/13 04/14 04/15 04/16 04/17 04/18 04/19 04/20Active Device Trend from Apr. 13, 2009 to Apr. 19, 2009)0102030405060DevicesWeekly Active Devices Trend(d) LSC Active DevicesFigure 4.6: Weekly Trend8540Mbps and the number of active devices are below 50, the coverage of 27 and 40APs should be able to provide enough network capacity for this traffic demand inboth buildings. Therefore, we expect to see only localized interference between afew pairs of devices.The challenge to evaluate VOID in this live network is that, unlike the con-trolled evaluation we conducted in the testbed, we do not know the underlyinginterference topology in these networks. Therefore, it is difficult to answer thefollowing two questions:• False positives: How many devices are incorrectly labeled as interfering?• False negatives: How many interfering devices are not detected?4.6.1 False PositivesWe use channel information to infer which pairs of de‘vices detected by VOIDare accurate. The one-week wireless client channel distribution is illustrated inFigure 4.7, from which we can see that the majority of wireless clients in bothbuildings operated on channels 1, 6 and 11, and only a small subset were operatingon the 5G frequency band. The channels are more evenly distributed in LSC thanin Highrise, nevertheless there are hundreds of clients on each of the three 2.4Gchannels.Assuming devices operating on orthogonal channels do not interfere, if a pairof devices are found as interfering but are operating on orthogonal channels, thenthis detection is counted as a mistake against VOID. Otherwise, if they operate onthe same channel, then we treat this pair as true interfering candidate.We use False Positive Ratio (FPR) to evaluate VOID’s accuracy, as defined bythe ratio of orthogonal-channel interference detections to the total detections. Themore accurate VOID is, the more interference found by VOID should be on thesame channel and thus the false positive ratio should be lower. Note that some ofthese same-channel interferences detected by VOID could also be false positivesand thus the FPR can be higher in reality than what we estimated. Although it is8603/22/200903/23/200903/24/200903/25/200903/26/200903/27/200903/28/20090100200300400500Unique ClientsChannel 1Channel 6Channel 11Channel 36Channel 56Channel 64Channel 149Channel 161(a) Highrise04/13/200904/14/200904/15/200904/16/200904/17/200904/18/200904/19/20090100200300400500600Unique ClientsChannel 1Channel 6Channel 11Channel 149Channel 161(b) LSCFigure 4.7: Channel Distribution in Highrise and LSC87impossible for us to get the real FPR number due to lack of underlying accurateinterfering map, we confirmed in Section 4.7.2 that more than 99% of the detectedsame-channel interferences occur between devices within close proximity.We use two heuristics, R2 and VTBR, to differentiate the true interferers fromthe false ones. First, as in the experiments conducted in Emulab, we require atleast a minimum value of R2 to ensure the candidate device is a significant in-terferer to the victim device. However, R2 value alone is not sufficient due tothe burstiness of traffic characteristics in live networks. As we later show in Fig-ure 4.9, with our default R2 value of 0.01, more than 66% of the interfering devicesbeing detected were still on orthogonal channels. Therefore, we have to deploy thesecond heuristic, called Valid Time Bucket Ratio (VTBR). VOID divides the two-minute time window into eight time buckets, and runs regression on all these timebuckets. Only if the devices show consistent interference in these time buckets,VOID will treat them as true interferers.The impacts of these two heuristics on FPR are now demonstrated in Figure 4.8and Figure 4.9 respectively. When the R2 and VTBR values are low, R2 at 0.002or VTBR at 0.1, for example, the same-channel interference ratio is below 50%.These values indicate that more than 50% of the detected interferences are wrong,as the correlated devices operate on the orthogonal channels. However, the same-channel interference ratio grows as we increase R2 and VTBR values. In the firstexperiment, we keep VTBR at 0.5 and increase R2 from 0.002 to 0.01, resulting thesame-channel interference ratio in Highrise to increase from 47% to 98% and thatin LSC from 60% to 95%. In the second experiment, we vary the VTBR from 0.1to 0.5 while keeping R2 at 0.01 and the same-channel interference ratio increasesby 57% in Highrise and 47% in LSC, as shown in Figure 4.9.We keep R2 at 0.01 and VTBR at 0.5 for interference correlation to ensureVOID accuracy. With this configuration, VOID is able to keep the same channelinterference ratio under 5% in both buildings, indicating a small number of falsepositives. On the other hand, this brings up the next question: how often doesVOID miss the opportunity to detect an interference by using this R2 and VTBR880.002 0.004 0.006 0.008 0.01R^2 (Confidence)020004000600080001000012000140001600018000Interference casesTotal interfering cases detectedSame channel interfering case detected(a) Interference Cases in Highrise0.002 0.004 0.006 0.008 0.01R^2 (Confidence) Interfering RatioSame channel interference ratio(b) Same-Channel Interference Ratio in Highrise890.002 0.004 0.006 0.008 0.01R^2 (Confidence)0200040006000800010000Interference casesTotal interfering cases detectedSame channel interfering case detected(c) Interference Cases in LSC0.002 0.004 0.006 0.008 0.01R^2 (Confidence) Interfering RatioSame channel interference ratio(d) Same-Channel Interference Ratio in LSCFigure 4.8: Impact of R2 on VOID Accuracy, VTBR Is Kept at 0.5.90Reason PercentageTestbed Pairin HighriseInactive 1.5%Orthogonal Channels 0.0%Topology Change 0.0%Other Interferers 17.5%Bursty Traffic 1.0%No Congestion 2.9%Interference Detected 73.7%Unknown (False Negatives) 3.4%Table 4.6: False-Negative Analysis on a Testbed in Highrisesetting?4.6.2 False NegativesTo determine VOID’s false negative rate accurately requires knowing the groundtruth about when devices actually interfere with each other. Unfortunately this sortof information is difficult to collect from live networks, which is of course a keymotivation for our work. As a result, we performed the following two experimentsto approximate a false-negative evaluation for this data.Testbed EvaluationWe first created a controlled, testbed experiment on the twelfth floor of the High-rise building. We placed two devices within interference range of each other,operating on the same channel, and we streamed TCP traffic to both. The band-width demand of these two streams was sufficient to congest the wireless networkthe two devices shared. The stream traffic to these two devices lasted for 6 hoursfrom 18:00 to 23:59 on Apr. 2nd 2009, forcing them to compete for airspace witheach other and with other nearby wireless clients.We analyzed all 720 time buckets during these six hours and classify them intothe eight categories listed in Table 4.6. We can see that VOID was able to detect910.1 0.2 0.3 0.4 0.5Valid TB Ratio05000100001500020000250003000035000Interference casesTotal interfering cases detectedSame channel interfering case detected(a) Interference Cases in Highrise0.1 0.2 0.3 0.4 0.5Valid TB Ratio0. Interfering RatioSame channel interference ratio(b) Same-Channel Interference Ratio in Highrise920.1 0.2 0.3 0.4 0.5Valid TB Ratio020004000600080001000012000140001600018000Interference casesTotal interfering cases detectedSame channel interfering case detected(c) Interference Cases in LSC0.1 0.2 0.3 0.4 0.5Valid TB Ratio0. Interfering RatioSame channel interference ratio(d) Same-Channel Interference Ratio in LSCFigure 4.9: Impact of VTBR on VOID Accuracy, R2 Is Kept at 0.01.93interference in the testbed 73.7% of the time. 17.5% of the interference is maskedby the live traffic sent by other Highrise residents’ WiFi devices. We found fivesuch external wireless devices, associated with three different APS operating onthe same channel on floor 9 and floor 12, and during these time buckets, the inter-fering testbed pair were only able to send half of their streaming traffic. There arealso times when the pair are not sending any/enough traffic due to either streamingsoftware crashes or TCP congestion control.The false-negative ratio for the two controlled nodes was 3.4% in this experi-ment. In many ways this setting represents a best-case scenario for VOID, becausenode proximity meant that the nodes were consistent strong interferers and be-cause the constant TCP stream ensured that data-rate fluctuations seen by VOIDwere mostly due to interference and not traffic variation.Consistency AnalysisTo get a better handle on additional false negatives that might occur in uncon-trolled environments such as those captured by our UBC wireless traces, we de-vised an indirect false-negative approximation that measures the consistency ofVOID’s detection algorithm.In this experiment we track all node pairs that VOID detects as interfering atleast three times at any point during the trace. We then classify the activity ofthese node pairs for the full trace duration to conservatively identify intervals inwhich VOID may have failed to detect interference between them. This analysisembeds two conservative assumptions for these node pairs. First we assume thatthe initial VOID detection is accurate, which is likely since VOID has relativelyfew false positives; if it is not, we over count false negatives. Second we assumedetected node pairs are potential interferers for the entire duration of the trace,which may not be true due to node mobility or changes in transmission rate, poweradaptation, or channel conditions etc. The only parameters that we know areoperating channel and access-point association. Of course, a limitation of thisapproach is that it will not count false negatives for node pairs VOID has never94detected as interfering.We examined seven days of trace data collected from the active periods ofHighrise (i.e., 18:00 to 23:59) and LSC (i.e., 10:00 to 18:00) and identified 25interfering pairs in the Highrise trace and 35 in the LSC trace. We treat these pairsas true interfering devices, and look for cases where VOID fails to correlate themwhen it should. For example, if one of the pair is not sending any traffic, then itis obviously that they indeed do not interfere during that time. We list the full listof causes below. Whenever we cannot find explanations for an undetected caseusing any of the known reasons, we treat it as a false negative. In other words,this experiment is designed to bucket all undetected cases into two classes. One isthe known interference undetected cases where we known there is no interference(no traffic, for example) or VOID is incapable of detecting interference (traffic islow, for example). The other is the unknown interference undetected cases andwe assume all of them are false negatives and are counted against VOID. We usethe following categories:• Inactive: One or both devices were not sending any traffic.• Orthogonal Channels: Devices were operated on non-interfering, orthog-onal channels.• Topology Change: Devices switched off to different APS; topology changeaffected the underlying interference relationship.• Other Interferers: Devices were found to interfere with other devices, asan interfering device can be masked by other significant interferers.• No Congestion: Devices are sending a lower total throughput than the min-imal throughput when they were found interfering, so the network is likelynot congested.• Bursty Traffic: Devices were not sending longer enough traffic, i.e., nomore than one-minute traffic in each two-minute time bucket, to providesufficient samples to VOID for analysis.95Pairs ReasonPercentage of Time BucketsMean (Std.) MedianHighrise 25Inactive 60.5% (22.6%) 61.9%Orthogonal Channels 12.3% (19.5%) 3.9%Topology Change 1.0% (4.0%) 0.0%Other Interferers 2.4% (5.1%) 0.4%Bursty Traffic 1.3% (1.8%) 0.4%No Congestion 18.7% (15.5%) 10.4%Interference Detected 3.0% (7.6%) 1.3%Unknown (False Negatives) 1.0% (1.9%) 0.0%LSC 35Inactive 79.3% (15.1%) 82.7%Orthogonal Channels 10.2% (10.4%) 6.7%Topology Change 1.1% (1.6%) 0.0%Other Interferers 2.4% (3.6%) 0.2%Bursty Traffic 0.4% (1.0%) 0.1%No Congestion 4.1% (4.5%) 2.3%Interference Detected 1.8% (2.7%) 0.9%Unknown (False Negatives) 0.7% (1.6%) 0.0%Table 4.7: False-Negative Analysis in Live NetworksThe analysis results are summarized in Table 4.7. We can see that the top threereasons when the pairs were not identified as interfering are (1) one of the devicesis inactive (2) they are operating on orthogonal non-interfering channels and (3)there is no congestion. These three causes together account for more than 90%of the cases when interference is not detected. It is also noteworthy that the no-congestion and bursty time buckets are not exclusive; in fact, more than 90% ofthe no-congestion time buckets are also bursty-traffic buckets. Finally, there are1% and 0.7% un-explained time buckets in each building when VOID is unable todetect interference.We define False Negative Ratio (FNR) as the ratio of false negatives to the totalpossible interferences (the time interference is detected + the false negatives), and96it is 25% and 28% in Highrise and LSC respectively.2 These numbers suggest thatVOID might have missed one out of four interferences in these live networks.4.6.3 Discussion on Trade-OffsTrade-Off between False Negatives and False PositivesIt is possible to improve this false negative number by relaxing two of VOID’skey parameters: R2 and VTBR. The previous experiments used values of 0.01 forR2 and 0.5 for VTBR; lowering either of these numbers increases the number ofinterference cases that VOID reports and thus potentially decreases the number offalse negatives.To investigate the impact of changes to these two parameters, we re-ran theexperiments with settings of 0.002 for R2 and 0.1 for VTBR. With these settings,the analysis described above reported a 10% false negative ratio; down from 25%.However, as we can see from Figure 4.8 and Figure 4.9, this change also increasesthe false positive ratio from 3% to more than 50%.Therefore, the network administrators need to understand the costs of falsepositives and false negatives before making a trade-off between them. The cost offalse positives is to falsely identify a group of devices as interfering. The impacton Shaper is to throttle these devices unnecessarily, and reduce the overall 802.11network capacity. The cost of false negatives is to unsuccessfully identify theinterfering devices to a victim device and thus it can continuously suffer frompoor performance, even bandwidth starvation.In our experiments, we tune the settings in favor of low false positives sothat the throttling (i.e, Shaper) can be enabled with high confidence. In environ-ment where network administrators are more concerned about fairness and poorperforming devices, they could tune the settings in favor of low false negativesinstead. Furthermore, when deployed in real networks, VOID can be run with dif-ferent settings in parallel and provide network administrators with different sets of2FNRHighrise =1%1%+4% ;FNRLSC =0.7%0.7%+1.8%970 20 40 60 80 100TB distance0%20%40%60%80%100%PDFHighrise detected-to-detected TB distanceHighrise undetected-to-detected TB distanceLSC detected-to-detected TB distanceLSC undetected-to-detected TB distanceFigure 4.10: Closest Distance Distribution from a Detected TB and False-Negative TB to Its Nearby Detected TB. Note that Neighboring TBsAre 30 Seconds Apart.interfering devices and associated false-positive and -negative values. This work,however, is left for future work.Trade-Off between Long-Lived and Short-Lived InterferenceAnother approach that may reduce the number of false negatives is to focus onlyon long-lived interference, ignoring false negatives that occur for only transientperiods. This approach is motivated by the observation that long-lived interferenceis more costly than transient problems and is more amenable to repair.To examine the impact of this approach on false negatives, we computed thetime distance between each false negative our original analysis detected to itsclosest successful detection. The results are illustrated in Figure 4.10. We can seethat time distance in both buildings follow a similar pattern: 95% of the interfer-98ence detections are immediately adjacent to another successful detection, whilethe false-negatives are a little farther from the nearby detections. However, half ofthe false-negatives are within 3 minutes of a detection, and three quarters of themare within 10 minutes.And so for this dataset, an operator concerned with congestion periods of noless than three minutes would see the algorithm miss only 12%, as half of thefalse negatives would have been close enough to a positive indication to not mat-ter. Similarly, in cases where the minimum interference interval of interest is 10minutes, the algorithm has a false-negative rate of only 7%.Depending on how an interference mitigation system uses the interference mapproduced by VOID, VOID could be configured to treat the detected pairs as inter-fering for a longer period once they are detected. Take Shaper for example, itcan make effective use of VOID to trigger traffic shaping for a period of 3 to 10minutes, where VOID’s false negative ratio is lower. The reasons that Shaper cantolerate these longer interference periods are two fold. First, since the false posi-tive rate of VOID is as low as 3%, Shaper has high confidence that it is throttlingthe correct pairs as instructed by VOID. Second, short-lived interference problemswill typically resolve themselves quickly, so Shaper need to kick in only when in-terference is persistent. Moreover, VOID is more likely to miss interference closeto nearby positive detections. Therefore, to be certain to address long-lasting in-terference in the network, it is preferable to keep traffic throttling running for arelatively longer period once Shaper is triggered.4.7 Interference in Live NetworksIn this section, we summarize what we observed and learned from the real networktraces and the detected live interferences. In particular:• Interference occurs more often when network traffic is high, indicating thatVOID is able to detect interference when congestion occurs.• Interference occurs between devices close-by – 99% of the interference de-99tections in Highrise happened between APS 3-floors apart and 66% of themare between devices associated with the same AP.• Interferences detected last for 10 minutes on average, the longest interfer-ence lasts a few hours.• VOID detected interference 2686 times in Highrise and 2139 times in LSC,most of which are pair-wise interferences. But VOID has found interferencesincluding up to 5 devices.• The real traffic is very bursty: more than 60% of the device activities lastless than 1 second. Only 0.45% of device activities last more than 1 minute,but they contribute to more than 80% of the overall network throughput.4.7.1 Interference Hourly TrendFigure 4.11 illustrates the correlation between throughput and interference in High-rise and LSC: Figure 4.7a and Figure 4.10c show the hourly mean-throughputvariations in these two buildings over the five weekdays3 and Figure 4.7b andFigure 4.10d represent the average interference detections in every hour.We can clearly see from Figure 4.11 that the interference trend in both build-ings follows the throughput variation closely: VOID is able to detect more inter-ferences when traffic is high and less when traffic is low. In Highrise, the majorityof interferences are detected at night after 5PM; while almost all interferencesin LSC are detected between noon to 8PM. This difference is because that High-rise is a residential building where activity is higher at night when people are athome while LSC is a academic building where the activity happens mostly dur-ing the day time. This correlation between throughput and interference detectionindicates that VOID is more likely to find interference when network is more con-gested, and it is effective in both environments.303/23/2009 to 03/27/2009 in Highrise and 04/13/2009 to 04/17/2009 in LSC.1001 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24Hour0510152025Throughput (Mbps)(a) Highrise Throughput1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24Hour020406080100120140160180Interference cases(b) Highrise1011 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24Hour0510152025Throughput (Mbps)(c) LSC Throughput1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24Hour050100150200250300350400Interference cases(d) LSCFigure 4.11: Average Throughput and Interference Detection Hourly Trends1024.7.2 Interference MapWe use the interferences detected by VOID to understand the interference relation-ships between APS in Highrise. We chose Highrise instead of LSC in this exper-iment because the AP placement in Highrise is more strict and organized in LSCdue to space constraints, and therefore the AP interference in Highrise is mostlydetermined by floor distance. In Highrise, each floor is equiped with two APS(except the first floor) along the elevator wall. In LSC, there are around 10 APSon each floor and thus the interference map is really a 3D map, and interferencedistance (hops) is harder to generalize.We analyzed the total 1621 same-channel multiple-device interferences de-tected by VOID in Highrise from Mar. 22, 2009 to Mar. 28, 2009. We correlatedthe APS to which these detected devices are associated and in total there are 2686pair-wise AP interference cases were identified. Figure 4.12 shows that 99.1%of the interferences occurred between two APS that are fewer than 3 floors apart.This result is not surprising that APS should be less likely to interfere if they arefarther away. Note that 2068 out of the 2686 interferences occurred on the samefloor and 1769 of them are the same-AP interferences.4.7.3 Interference Groups and DurationVOID has detected a total of 150 interference pairs and 2686 occurrences in High-rise, and 126 interfering pairs and 2139 occurrences in LSC. On average, each pairis found to be interfering 18 times in Highrise and 17 times in LSC, which is about10 minutes in length. We also found that the longest interference in Highrise lasts9 hours and that in LSC lasts around 2 hours.Finally, even though the majority of interference cases in these live networksare pair-wise only, there are still 381 and 303 three-device interference cases, 15and 89 four-device cases in Highrise and LSC respectively. VOID has even detectedfive-device interfering cases for 10 times in LSC.1030 2 4 6 8 10 12Floor distance0. CDFSame-AP Interference RatioFigure 4.12: The Interference Map in Highrise.4.7.4 Traffic Burstiness and ClassIn our earlier false positive analysis in Section 4.6.1, we show that setting VTBRat 0.5 is necessary to achieve a false positive ratio less than 5%. This setting,however, excludes devices with traffic burst shorter than a minute out of our inter-ference analysis. In this section, we investigate how much traffic and devices areaffected by this filter.We present two cumulative distributions in Figure 4.13: the probability dis-tributions of devices’ activity duration and their corresponding total throughput.These statistics are extracted from a total of 3.6 million of device transmissions(1.85 million in Highrise and 1.76 million in LSC) over the 5-weekday traces.We can see from Figure 4.13 that the devices’ transmission durations range fromless than 1 second to as long as almost 27 hours in both buildings and they fol-low the similar pattern: more than 60% of devices’ activities, shown as the blue104lines in Figure 4.13a and Figure 4.13b, last less than 1-second. Only 0.45% ofthe activity durations in Highrise and 0.35% in LSC are longer than 60 seconds.However, these longer than 60-second activities contribute to more than 85% oftotal network traffic in Highrise and 78% of that in LSC. We finally looked intothe traffic class in both buildings, and found that 75% of the flows in LSC and 65%in Highrise operate on the unassigned and dynamic ports. The second largest traf-fic is HTTP/HTTPS traffic: 15% in LSC and 22% in Highrise, followed by DNS,MSNP and ICMP protocols.This data shows that even though VOID has only selected a small set of devicesin the network for correlation, it is still quite useful in UBC live networks since ithas included the majority of traffic for interference analysis. In fact, VOID is de-signed to operate only when network is saturated, excluding most inactive devicesis not going to impact its effectiveness in practice.4.7.5 ScalabilityGiven k interferers and n throughput samples (n > k), the upper-bound complexityfor solving one MLR regression is O(n3). The formula to solve multiple regressionis βˆ = (XT X)−1XT y, bounded by the Gaussian elimination procedure used toinvert a matrix. We use hotshot [3] to profile a scenario where the numbersof interferers and samples are set to 100 and 2400 (all the throughput points)respectively. In this scenario, VOID takes 0.05 seconds to solve one regression onan Intel Xeon 1.6GHz machine.The time for VOID to converge is also determined by the total number of re-gressions needed to remove all the false interferers from the model. In a typicalwireless campus network we can expect a list of 100 potential devices (5 nearbyAPS working on the same channel with 20 associated clients each) where 90% ofthem are false interferers. VOID then needs 50 seconds to run 1000 regressionsto identify these 10 interferers. In the live Highrise and LSC buildings, the num-ber of active devices included for regression is only about 20 and the majority ispair-wise interference, so VOID needs only one tenths of a second to converge.105100101102103104105Active Duration (seconds) CDFThroughput CDF(a) Highrise Duration CDF100101102103104105Active Duration (seconds) CDFThroughput CDF(b) LSC Duration CDFFigure 4.13: Duration CDF in LSC and Highrise1064.8 ConclusionIn this chapter, we propose an online, passive interference detection approach forenterprise wireless networks called VOID. It takes in throughput traces collectedfrom a central router and outputs a list of interferers to a victim node. The salientfeatures of VOID are that it uses online traces for analysis and that it is fast enoughto track interference relationship changes in real time. We have conducted a va-riety of experiments on the Emulab wireless testbed and the live wireless UBCnetworks, and the results have shown that VOID is able to accurately and quicklydetect the true interfering devices in changing environments.107Chapter 5Related WorkMy thesis is inspired by many of the prior research work. This section provides anoverview of the related work on interference analysis, mitigation and diagnosis.5.1 Interference AnalysisThe performance woes of 802.11 competing flows, i.e., inefficiency and unfair-ness, are fundamentally caused by the protocol design. 802.11 an autonomousprotocol that wireless devices operate using the CSMA/CA protocol. A sendersenses airspace activity before transmitting a packet – the sender will only starttransmission if the airspace is idle and backs off otherwise. However, as weshowed in Chapter 2, when competing flows span over multiple sensing ranges,CSMA/CA is no longer effective: Senders can be out of range so that their trans-missions can still collide or one sender can compete with more devices than theothers.Prior studies have identified one main culprit: problematic topologies. Oneattempt is to distinguish between hidden-terminal and exposed-terminal topolo-gies [30, 31, 62]. Chen et. al. further points out the importance of incompletechannel status assessment and inconsistent channel status [40]. Incomplete chan-nel information leads to packet collisions; inconsistent channel information leads108to unfair channel sharing. These categorizations are both correct, however, theyare not specific enough to help wireless devices to adapt to continuously changingenvironments.Jian also point out that sensing range is not the same as transmission rangeand Additive Increase Multiplicative Decrease (AIMD) of 802.11 cannot achieveMAC-layer fairness in various settings [60]. They propose a new rate control pro-tocol, called Proportional Increase Synchronized multiplicative Decrease (PISD),to achieve fairness in 802.11 networks. The key idea is two fold: one is to enablethe victim nodes to jam the airspace so that all devices, including the winningdevices, will back off synchronously; the other is to assign weighted fairness fordifferent MAC flows so that they have different additive increase rate to achievethe fairness an administrator desires.There have also been several analysis works [32, 54, 64, 104] on 802.11 MACDCF protocol performance including throughput, delay, queue performance, etc.These models are, however, mostly analytical rooted at the Markov Chain modelproposed by Bianchi [32]. The work from Kim et al. [64] is based on a fluidmodel. Our models, on the other hand, follow a more experimental methodologyto examine the fairness and performance issues when competition occurs.If we consider only two sending nodes, there are only two possible ways thatthey can interfere with each other: (1) receiving interference and (2) carrier sens-ing interference [73]. Receiving interference occurs when two senders are out ofradio range of each other, but one sender’s packets are corrupted at the receiverby another sender’s signals; carrier sensing interference happens when the vic-tim node is able to sense the interfering node’s signal so that it cannot send whenthe interferer is transmitting. These pair-wise sender/receiver interference modelsare the building blocks needed to estimate the interference level between multipleinterfering nodes and the victim node [69, 77, 82].The work from Garetto et. al. [50] analyzes 16 two-competing-flow topolo-gies, and categorizes them into four interference models. In Chapter 2, we ex-tended their work to show that, in addition to node topology, signal strength and109traffic type can also impact the way devices interfere with each other. We investi-gate 698 scenarios and propose 16 more models, and it is impossible to enumerateall possible interference cases even for only two competing flows — the numberof scenarios continues to grow exponentially as we include more environmentalparameters into the model.5.2 Interference Mitigation ApproachesIEEE 802.11 standards board committees continue to develop new 802.11 proto-cols to provide better network performance to wireless users. The MIMO tech-nology [79] deployed in IEEE 802.11n [12] takes advantage of multi-path sig-nal propagation and CRC encoding to correct corrupted signal at a receiver. The802.11k standard [11] associates a wireless station with a weaker-signal but under-utilized AP if the strongest-signal AP has already been over subscribed. These pro-tocols however suffer from the same interference issue when airspace is alreadysaturated. Note that 802.11ad [16] standard can operate on the unlicensed 60 GHzfrequency band and deliver data transfer rates up to 7Gbps. However, its effectivebandwidth can be significantly reduced when operating with legacy 802.11 de-vices. Given that there are already hundreds of millions of legacy 802.11 devicessold worldwide, 802.11 network congestion problem is expected to continue forquite some time.Researchers have proposed different solutions to alleviate the impact of wire-less interference. Self-adaptation in 802.11 networks has drawn a lot of attentionto improve performance for 802.11 devices. Some have investigated physical car-rier sensing in detail [45, 57, 97, 98, 103]. Their intention is to adjust or disablecarrier sensing function so as to maximize spatial reuse and avoid packet colli-sions. The other adaptation mechanisms include altering the MAC backoff dura-tions [90, 92], enabling RTS/CTS virtual carrier sensing [40, 61], switching fromsender-initiate mode to receiver-initiate mode [40, 48], and adapting the trans-mission rate and time scheduling [63, 84]. These approaches, however, requirechanges made to the driver or firmware, which is hard to implement and adopt.110Also, most of the present-day 802.11 devices lower their sending rate whenexperiencing poor performance. This is because lowering the rate can increasethe transmission range so that the interfering nodes are more likely to sense/cap-ture its packets and consequently back off. Also, packets sent at lower rate aremore robust to interference or noise. However, previous work has also shown thatlowering the sending rate results in significantly low network utilization [89] and,in certain cases, can even make the unfairness problem worse [95].Improving network performance and fairness for cooperative wireless LANshas attracted a lot of research attention. Some require all the wireless devices tocommunicate with each other (or with a master node) to come up with a globallyconsistent schedule for each device to access the network [2, 65, 91, 92]. Someuse load-balancing schemes that shuffle wireless users between different accesspoints according to the changing network and traffic condition [25, 27]. Otherslimit the number of clients associated with each AP to avoid network congestionfrom happening in the first place [11, 27, 59].The CENTAUR work from Shrivastava et al. [87] treats downlink traffic anduplink traffic differently in enterprise WLANS. It uses a centralized scheduling ap-proach, called DET, to handle all downlink hidden and exposed terminal packets,and uses 802.11 for all other packets including uplink and other non hidden orexposed terminal downlink packets. When DET detects the possibility of a hid-den terminal conflict, it delays the transmission of some packets to avoid collisionand packet loss. For an exposed terminal conflict, DET introduces an approachcalled packet staggering to keep these packets in sync to be transmitted simulta-neously. CENTAUR requires significant changes to APS to keep them in sync andto construct the interference map using micro-probing [21].Comparing to all above approaches, Shaper emphasizes the correlation be-tween 802.11 network congestion and unfairness, and points out that a much eas-ier way to address unfairness is to alleviate congestion, requiring no modificationsto either APS or end-user WiFi devices. Note that our Shaper does not intend tocompete with any of the above proposals but could co-exist to address WLAN111problems together.Traffic limiting has been proposed to address many different problems in theliterature. Gambiroza et. al. [49] propose to use rate limiting in order to achieveper-TAP (Transit Access Points) fairness between long-hop flows and short-hopones in multi-hop wireless mesh networks. Portole´s et. al. [76] use shaping toavoid a disconnecting/de-associating station from causing undesirable impact onthe other devices within the same network. Chiasserini et. al. [44] also suggest toregulate bluetooth traffic to improve performance for 802.11 flows. Our Shaper,on the other hand, is designed to address unfairness caused by asymmetric topolo-gies or inequitable channel conditions between competing devices in WLANs,especially when these devices are associated with different access points.5.3 Interference CorrelationTo effectively mitigate interference in the network, the first step is to understandthe interference relationship between the devices quickly and accurately. Manyprior researchers have proposed to automate problem diagnosis in 802.11 net-works [19, 24, 38, 41, 42, 52, 58, 69, 86]. These systems are designed to detectnetwork anomalies such as rogue APs, association and authentication failures andsignal interference using network statistics collected from distributed sniffers.DAIR [24, 39], WiFiProfiler [38], MOJO [86] and [19] require cooperationfrom wireless clients. In most of these systems, the clients and APs collect net-work statistics and send them to a central point for problem diagnosis. WiFiPro-filer enables mobile clients to exchange sensing information and help each otherin an ad-hoc way.Unlike these systems, Jigsaw [41, 42] and WIT [69] deploy dedicated monitorsnear the APs, with the goal to systematically capture all the link-layer packets inthe airspace. These systems (as well as MOJO [86]) the merge all the tracesto generate a single unified picture of network activity. This time-synchronized,detailed trace allows these systems to diagnose implicit physical layer anomaliessuch as hidden-terminal topologies and the capture effect. These systems require112networking administrators to set up dedicated monitoring nodes throughout thenetwork, doubling the deployment and maintenance cost.The studies from Padhye and Woo [74, 96] have demonstrated that interfer-ence and conflict maps based on real measurements are more accurate than thosebased on theoretical RF models [56]. In the measurement phase, the interfer-ence level between pairwise devices is calculated by instructing each device (or apair of nodes) to broadcast or unicast messages in turn, while keeping the othernodes observing. Dragos¸ Niculescu has shown that the network performance incomplex-traffic and multiple-sender scenarios can be predictable using these sim-ple, low complexity pairwise measurements [73].Conducting these measurements, on the other hand, is quite time consuming.Therefore, some prior work [69, 77, 82] has proposed to combine together thebest part of both approaches together — real measurements and theoretical in-terference models. This approach uses measurements to accurately capture theRF characteristics of a given wireless network. The measurement results are thenused to seed a variety of interference models such as RSSI/PDR [82], 802.11 statemachine [69] or Markov chains [77] to predict run-time performance given trafficinput.Researchers have also proposed to use online traffic to generate the conflictgraph for a network [88, 93]. The conflict graph work [93] requires each sender tomaintain a local conflict table, updated by the feedback (packet delivery probabil-ity) from its receiver. This table is then exchanged among senders. If the conflicttable suggests that a sender does not experience poor packet delivery ratio whilesending simultaneously with another sender, in a typical exposed terminal topol-ogy for example, then it should ignore the other sender’s signals to improve theoverall network utilization.Ahmed et al. proposed a technique called micro-probing [21] to constructan interference map without taking the network offline. The access points useMAC-layer CTS-to-self or ACK packets to silence the airspace before initializingan interference measurement. The interference analysis is carried out quickly,113taking under 20 seconds to complete in a 20-node network. However, this airspacesilence approach is not very effective in a real network due to two reasons. One,not all WiFi devices have properly implemented the 802.11 standard. Second,some devices could have failed to decode the silencing packets.The later PIE work [88] instructs the access points to record the time andsuccessful transmission rate when they transmit packets, and report this informa-tion to the central controller. The controller then uses this information to inferwhich transmitters are mutually interfering. Their approach, however, still re-quires driver/protocol modification and cooperation from both APS and mobileclients.5.4 Recent WiFi Interference Research Work5.4.1 Interference AnalysisWe continuously observe the evolution of WiFi standards over the last few yearsto provide very high link bitrates. The 802.11ac WiFi standard [17], for example,promises a bitrate of up to 1.3Gbps. The significant theoretical performance im-provement is largely due to two factors: (1) denser modulation type and codingrate techniques and (2) Multiple Input and Multiple Output (MIMO) that multipliesthe capacity of a radio link using multiple transmit and receive antennas.However, Bharadia [28] point out that users often do not realize theseperformance improvement in practice, experiencing raw speeds that are one to twoorders of magnitude less than the advertised speeds. They identify two causes:propagation loss and MIMO rank degradation. They show that wireless devicesat the edge in a home experience SNRs between 0-6dB, leading to a 4x bitratereduction. Furthermore, they show that in many indoor and urban scenarios, thereis only a single strong path exists between an AP and a client, and the rest areweak or non-existent, thus rendering MIMO useless.Recent work [75] collects wireless performance traces from 30 homes in Chicagofor a period of 6 months for performance measurement and analysis. Their results114show that around 8% of clients experience poor performance for greater than 10%of their active periods. They also show that in a dense deployment of privateAPS, high airtime utilization from neighboring APS was the major cause of perfor-mance degradation while low performance due to weak signal strengths were moreprevalent in a centralized home deployment. They also show most of the trafficis short-lived and thus hidden-terminal interference can occur intermittently. Butlong-term stream traffic such as Netflix can lead to long term hidden-terminal in-terference, as long as 87 minutes. Note that these findings nicely matches ourfindings in UBC campus networks as described in Section 4.7.Finally, studies in 2010 have shown that non-WiFi interference sources aremajor problems for 802.11 networks [13, 14] — the highpower interferers likebaby monitors and cordless phones can cause 802.11n networks to experience acomplete loss of connectivity. Customer survey from Cisco [15] revealed that RFinterference is the top issue causing wireless network performance problems, andabout 50% of the interference is from non-WiFi interference sources.5.4.2 Interference MitigationRecent researches take advantage of recent technological advances, specificallyInterference Alignment and Cancellation (IAC), beamforming and wider spec-trum, to mitigate interference for 802.11 devices. In this section, we discuss recentinterference mitigation systems utilizing these key ideas.Interference Alignment and CancellationA MIMO sender cannot send more packets concurrently to its receiver than thenumber of receiving antennas. Otherwise, the receiver will not be able to decodethese concurrent transmissions apart from each other. IAC [51] is proposed to im-prove network throughput by enabling even more concurrent transmissions. IACrequires the senders to align their transmissions in a special way so that all theinterfering packets to a receiver is aligned, and thus the receiver is able to decodeone packet successfully. Then the receiver will send the decoded packet to the115other receivers so that they can perform interference cancellation to subtract theeffect of the known packet from the signals they received to decode the remainingpackets. With this approach, 802.11 network throughput is no longer bounded bythe number of antennas. Recent work [66] extends IAC work by enabling MIMOdevices to compete for airspace without central coordination, even in the presenceof ongoing transmissions, using multi-dimensional carrier sense on orthogonalchannels. Bharadia et. al. [29] introduce full duplex ratios that use novel analogand digital cancellation techniques to cancel the self interference to the receivernoise floor. This approach ensures no degradation to the received signal and there-fore a radio can now send and receive signals simultaneously.Recent work from Bansal et. al. [26] proposes a system called Symphony, apacket recovery architecture that encourages collisions among transmitters, andutilizes the unused capacity in the backbone to transmit recovered data packetsand coordinate the efficient recovery of collided packets. It does not require eachdevice to have multiple antennas, but it does require APS are all connected overethernet and able to receive decoded packets from each other for interference can-cellation. BBN [105] takes advantages of the high density of APS in a single do-main and requires a subset of APS to retransmit the received signals (not packets)wirelessly to nullify the interference at other APS. Once any packet is successfullydecoded, the packet will be transmitted to other APS via ethernet. Both Symphonyand BBN are designed for up-link transmission only.Multi-user BeamformingMulti-user Beamforming (MUBF) [99] is designed to serve many users simulta-neously. It multiplies each individual data stream by its appropriate beamform-ing weight vector, aggregates the resulting streams to one, and then transmits thesummed streams in parallel using an antenna array. The weight vectors are cho-sen carefully based on independently fading channel conditions to the receivers sothat mutual interference among different streams is reduced (or even eliminated)at each receiver. Recent work [23] demonstrates that MUBF performs very well116even for small-sized mobile devices even with high mobility and limited power.The authors also show that, to make a tradeoff between power and throughput, anoptimal number of active antennas (or an optimal beamforming vector size) canbe chosen based on the channel conditions and throughput demands. An adaptivealgorithm, called BeamAdapt, is proposed to iteratively adjust the beamformingsize at each sender solely based on the SINR at its own receiver.Rahul et. al. [78] present a system, called Jointed Multi-user Beamforming(JMB), which enables independent APS to beamform their signals and commu-nicate with their clients on the same channel as if they were one large MIMOtransmitter. The challenge, however, is to synchronize the phases of multiple APSin a distributed manner so that, at each client, the signals intended for the otherclients can cancel each other out. JMB uses a simple approach by choosing oneAP as a lead and using its phase as a reference to align the phases of all other APSin the network.Recent work from Yu et. al. [100] propose a system called CoaCa to com-bat inter-cell interference in 802.11ac-based multi-user MIMO networks. It is atwo-step approach that utilizes both interference cancellation and beamformingtechnologies. The first step is to let each AP and client optimize the use of itsantennas for either data communication or inter-cell interference cancellation, tomaximize the total number of deliverable streams in the network. Once the ac-tive antennas are determined and channel conditions are overheard, each node canobtain enough channel knowledge to optimize its beamforming weights.Spectrum ManagementThe new 802.11 standards support wider channel width (spectrum) for higherthroughput. IEEE 802.11n [12] supports up to 40 MHz channels and IEEE 802.11ac[17] further increases the channel width to 160 MHz. However, wider channelsare more susceptible to interference in reality, and thus bandwidth/spectrum man-agement needs to be dynamic and adaptive.Rayanchu et. al. [81] have shown that spectrum allocation needs to take into117account the interference parameters like carrier sensing, hidden terminals etc.,which depend on the combinations of frequencies and channel widths used, aswell as the specifics of topology and traffic demand. They also develop a mod-eling framework to efficiently compute the conflict graph for an N node networkwith k bitrates employing flexible channelization using only O(N.k) empiricalmeasurements. Finally, a central controller assigns the center frequencies andwidths to the APS on the fly, depending on the actual traffic demand. Recent workfrom Yun et. al. [101] further improves the above system by enabling spectrumadaptation on a per-frame basis and allowing an AP to transmit multiple framessimultaneously.118Chapter 6Conclusion and Future WorkIn this thesis, I present our research results on interference analysis, mitigation anddetection. This section concludes our approaches and contributions, and providespossible future research directions.6.1 ConclusionInterference is omnipresent in 802.11 networks, and it is already well known thatstrong interference can lead to severe performance degradation and extreme un-fairness for wireless devices. The cause is tied with the fundamental design of802.11 protocol. The CSMA/CA scheme allows each sender to make its own de-cision on when to access the network locally, requiring no arbitrators for coordi-nation. However, these individual decisions together might result in non-optimalbandwidth utilization and distribution especially in multi-hop networks where lo-cal sensing might miss transmissions out of its range. This thesis aims to under-stand the cause of interference better, detect interference quicker and easier, andmitigate its impact in enterprise wireless networks.Chapter 2 investigates the cause and impact of wireless interference in moredimensions. In addition to topology, we consider sensing link state, traffic typeand signal strength in our models, and in our evaluations, we show that slight119changes in one of the parameters can completely change the throughput outcome.We simulate all 648 possible two-flow scenarios by enumerating all possible com-bination of these three parameters, and propose 19 models based on the bandwidthutilization and fairness. Our experiments also manifest that these models are ac-curate enough to predict the performance for two competing flows in a testbedenvironment. On the other hand, while adding these new parameters providesmore insights on how wireless devices perform in live networks, it becomes clearthat the complexity of interference grows exponentially as one takes into accountmore environmental factors. Chapter 2 has already considered 648 scenarios, andwe have intentionally left out factors such as sending rate, signal propagationmodel, more competing flows, to simplify our analysis. Therefore focusing andaddressing just one network parameter might not work very well in reality.In Chapter 3, we focus on the cross-layer interactions between the networklayer and the MAC layer. The key observation is that wireless unfairness occursonly when competing devices attempt to send more traffic than the 802.11 networkcapacity. The experiment demonstrates that, even in the worse topology suchas the hidden terminal scenario, as long as the aggregate throughput does notexceed 85% of the network capacity (e.g., 20Mbps out of 24Mbps in our testbed),both flows can always achieve fair bandwidth allocation. Therefore, we proposea system called Shaper that throttles the aggregate throughput of the interferingdevices in favor of better fairness. The idea is that TCP and fair queuing algorithmssuch as SFQ can slow down the sending rate of the winning flows, and allow thelosing flows to salvage the dropped packets using TCP or MAC retransmissions.Finally, to identify which devices are interfering in the network, we proposean online, passive interference detection system called VOID in Chapter 4. Unlikemany previous work that requires in-field measurements, VOID identifies inter-ference relationships by correlating the throughput variations at the central wiredrouter. This interference detection scheme works in congested networks wherethe throughputs of interfering devices are adversely correlated, i.e., when one’sgoes up, the others’ go down. We demonstrate the effectiveness of VOID in both a120controlled testbed (Emulab) and live wireless networks in UBC. In both environ-ments, VOID is able to detect the true interfering devices and filter out the falseones.6.1.1 ContributionThe main contribution of my thesis is to understand and exploit the correlationbetween congestion and interference. We realize that the impact of interference,i.e., performance degradation and unfair bandwidth allocation, becomes worsewhen airspace is congested. If there is some bandwidth unused, the TCP and MAClayer retransmission mechanisms are still able to help the disadvantaged devicesto recover their packet losses. However, as soon as 802.11 network congestionoccurs, they are no longer effective. Also, under congestion, the throughputs ofinterfering devices follow a very clear pattern – the throughput of one flow isadversely correlated to that of the others.Based on these observations, we propose two systems called Shaper and VOID.They aim to detect interference and mitigate its impact in enterprise wireless net-works. Shaper throttles the aggregated throughput in the central router to tradeoverall throughput for better fairness, while VOID monitors the throughput varia-tion at the router to infer interference relationships in the airspace.6.2 Future WorkThere are several future directions that the ideas in this thesis could be taken. Itwill be very interesting to deploy VOID and Shaper in live wireless networks. Also,we have to use heuristics such as channel information to infer VOID’s accuracy inChapter 4, it will be interesting to run VOID where monitoring systems such asJigSaw [41] is available so that we can have the real underlying interference mapfor the reference.Another possibility for future work is to automatically determine the tradeoffbetween throughput and fairness. One of the parameters that affects the throt-121tling limit is the channel conditions of the losing flows; the worse their channelconditions are, the lower the throttling upper bound will be for perfect fairness.To one extreme, if one losing flow experiences many packet losses even withoutcompeting flows, then throttling is not going to be of any use but to reduce theoverall network utility. The implementation of Shaper should be aware of this pit-fall. What Shaper might do is to throttle only the winning flows to their fair shareinstead of trying to achieve perfect fairness, for better overall network utilization.In addition, a cost function can be used to increase the cost of throttling as theaggregated throughput declines.Similarly, one of the issues that Shaper needs to consider in real deploymentis what fairness it should achieve in a given wireless network. As we explainedearlier, the way Shaper works is to stop congestion in the last hop and thus avoidthe 802.11 protocol from making bandwidth-allocation decision. Thus, if all thedevices run at the same rate, then a max-min fairness should be achieved, thanksto the TCP protocol. However, unlike the wired links using fixed rate for packettransmission, the wireless devices are likely to operate at different rates depend-ing on various channel conditions they face, even if they associate with the sameaccess point. When devices are running at different rates, there exists a big dif-ference between time fairness and throughput fairness [90]. The time fairnessallows the competing devices to equally share the channel access time, while thethroughput fairness guarantees that they will achieve the same throughput. Thedifference between these two fairness schemes is due to the fact that a wirelessdevice running at a lower rate will take much longer time to send a packet thanthose using a higher rate. Therefore, to achieve a throughput fairness will enablethe slower devices to occupy much longer channel access time than the others,resulting in significant loss in overall network utility.Finally, the most interesting and challenging future work is to integrate VOIDand Shaper for online interference diagnosis and mitigation. It should be a con-tinuous feedback pipeline consisting of four subsystems: (1) trace collection (2)throughput aggregation (3) VOID and (4) Shaper. As we discussed in Section 4.4,122we use port mirroring techniques to copy live traffic to another switch port fortrace capture so that it will not impair the central routers’ performance when serv-ing live traffic. We then use WyPy [67] to aggregate the throughput stats for alldevices seen in the trace and feed the throughput time series to VOID for interfer-ence correlation. Once the set of interferers are identified, Shaper will be notifiedto throttle the aggregated throughput for the affected devices.The latency of this pipeline is mostly determined by throughput aggregationand interference correlation, i.e., the WyPy and VOID subsystems. The trace cap-ture and traffic throttling are both almost instantaneous. On the other hand, in ourlive UBC networks, WyPy takes about 10 seconds to generate the throughput timeseries for a 2-minute trace while VOID can take up to 60 seconds to converge sinceit has to run multiple regressions on each of the candidate devices. The end-to-endlatency of this pipeline is, therefore, at most 60 seconds.We were able to run the first three subsystems using UBC live traces — wecaptured 2-minute traces and fed that to WyPy and VOID to correlate interfer-ers. Unfortunately the permission was not granted to run Shaper on UBC centralrouters. Nevertheless, we were able to generate the online interferer set for thetwo campus buildings every minute. This latency can be further greatly reducedby running all these regressions against each candidate in parallel. In the future,we would like to evaluate effectiveness of VOID and Shaper when they operatetogether.123Bibliography[1] D-itg traffic generator. URL →pages 76[2] Packet scheduling and qos for wireless networks. URL → pages 111[3] hotshot – high performance logging profiler. URL → pages 105[4] Hierarchical token bucket. URL∼devik/qos/htb/. →pages 50[5] ipt account netfilter module. URL account/. → pages57, 76[6] Madwifi. URL → pages 76[7] Qstream. URL → pages6, 49[8] Scipy. URL → pages 74[9] Tcpdump and libpcap. URL → pages 73[10] The institute of electrical and electronics engineers, ieee std 802.11g -2003 — ammendment to ieee std 802.11, 1999 edition (reaff 2003), 2003.→ pages 30[11] The institute of electrical and electronics engineers, ieee std 802.11k -2008 — amendment 1: Radio resource measurement of wireless lans.,2008. → pages 110, 111124[12] The institute of electrical and electronics engineers, ieee std 802.11n -2009 — ammendment 5: Enhancements for higher throughput., 2009. →pages 5, 110, 117[13] Evaluating interference in wireless lans: Recommended practice, 2010.URL interference in wireless lans.html. → pages 115[14] Understanding the effects of radio frequency (rf) interference on wlanperformance and security, 2010. URL → pages115[15] Wireless rf interference customer survey results, 2010. URL RF interference survey.pdf. → pages 115[16] The institute of electrical and electronics engineers, ieee std 802.11ad -2012 — amendment 3: Enhancements for very high throughput in the 60ghz band., 2012. → pages 110[17] The institute of electrical and electronics engineers, ieee std 802.11ac -2013 —amendment 4: Enhancements for very high throughput foroperation in bands below 6 ghz., 2013. → pages 114, 117[18] More than 120 million wi-fi chipsets shipped in 2005, last known valid in2006. URL →pages 1, 44[19] A. Adya, P. Bahl, R. Chandra, and L. Qiu. Architecture and techniques fordiagnosing faults in ieee 802.11 infrastructure networks. In Proceedingsof the annual international conference on Mobile computing andnetworking (MobiCom), 2004. → pages 112[20] N. Ahmed and S. Keshav. Smarta: a self-managing architecture for thinaccess points. 2006. → pages 5[21] N. Ahmed, U. Ismail, S. Keshav, and K. Papagiannaki. Online estimationof rf interference. 2008. → pages 111, 113125[22] A. Akella, G. Judd, S. Seshan, and P. Steenkiste. Self-management inchaotic wireless deployments. In Proceedings of the annual internationalconference on Mobile computing and networking (MobiCom), 2005. →pages 44[23] E. Aryafar, N. Anand, T. Salonidis, and E. W. Knightly. Design andexperimental evaluation of multi-user beamforming in wireless lans. InProceedings of the annual international conference on Mobile computingand networking (MobiCom), 2010. → pages 116[24] P. Bahl, J. Padhye, L. Ravindranath, M. Singh, A. Wolman, and B. Zill.Dair: A framework for managing enterprise wireless networks usingdesktop infrastructure. In ACM Workshop on Hot Topics in Networks(HotNets), 2005. → pages 112[25] A. Balachandran, P. Bahl, and G. M. Voelker. Hot-spot congestion reliefand service guarantees in public-area wireless networks. SIGCOMMComput. Commun. Rev., 32(1), 2002. → pages 111[26] T. Bansal, B. Chen, P. Sinha, and K. Srinivasan. Symphony: Cooperativepacket recovery over the wired backbone in enterprise wlans. InProceedings of the annual international conference on Mobile computingand networking (MobiCom), 2013. → pages 116[27] Y. Bejerano, S.-J. Han, and L. E. Li. Fairness and load balancing inwireless lans using association control. In Proceedings of the annualinternational conference on Mobile computing and networking(MobiCom), 2004. → pages 111[28] D. Bharadia and S. Katti. Fastforward: Fast and constructive full duplexrelays. In Proceedings of the conference on Applications, technologies,architectures, and protocols for computer communications (SIGCOMM),2014. → pages 114[29] D. Bharadia, E. McMilin, and S. Katti. Full duplex radios. In Proceedingsof the conference on Applications, technologies, architectures, andprotocols for computer communications (SIGCOMM), 2013. → pages 116[30] V. Bharghavan. Performance evaluation of algorithms for wirelessmedium access. In In Proceedings of IEEE Performance andDependability Symposium, 1998. → pages 2, 13, 108126[31] V. Bharghavan, A. Demers, S. Shenker, and L. Zhang. Macaw: A mediaaccess protocol for wireless lans. In Proceedings of the conference onApplications, technologies, architectures, and protocols for computercommunications (SIGCOMM), 1994. → pages 2, 13, 108[32] G. Bianchi. Performance analysis of the ieee 802.11 distributedcoordination function. IEEE Journal on Selected Areas inCommunications, 18(3), 2000. → pages 109[33] I. Broustis, K. Papagiannaki, S. V. Krishnamurthy, M. Faloutsos, andV. Mhatre. Mdg: measurement-driven guidelines for 802.11 wlan design.In Proceedings of the annual international conference on Mobilecomputing and networking (MobiCom), 2007. → pages 5[34] K. Cai, M. Blackstock, R. Lotun, M. J. Feeley, C. Krasic, and J. Wang.Wireless unfairness: alleviate mac congestion first! In Proceedings of thesecond ACM international workshop on Wireless network testbeds,experimental evaluation and characterization, 2007. → pages 43, 72[35] K. Cai, M. Feeley, and B. Cully. Understanding performance for two802.11 competing flows. In Proceedings of IEEE InternationalConference on Mobile Adhoc and Sensor Systems, 2007. → pages 12[36] K. Cai, J. Wang, R. Lotun, M. J. Feeley, M. Blackstock, and C. Krasic. Awired router can eliminate 802.11 unfairness, but it’s hard. In Proceedingsof the 9th workshop on Mobile computing systems and applications, 2008.→ pages 43[37] K. Cai, M. Blackstock, M. J. Feeley, and C. Krasic. Non-intrusive,dynamic interference detection for 802.11 networks. In Proceedings of theInternet Measurement Conference on Internet Measurement Conference(IMC), 2009. → pages 64[38] R. Chandra, V. N. Padmanabhan, and M. Zhang. Wifiprofiler: cooperativediagnosis in wireless lans. In Proceedings of The InternationalConference on Mobile Systems, Applications, and Services (MobiSys),2006. → pages 112[39] R. Chandra, J. Padhye, A. Wolman, and B. Zill. A location-basedmanagement system for enterprise wireless lans. In Proceedings of The127USENIX Symposium on Networked Systems Design and Implementation(NSDI), 2007. → pages 112[40] C.-C. Chen, , C. cheng Chen, and H. Luo. The case for heterogeneouswireless macs. In ACM Workshop on Hot Topics in Networks (HotNets),2005. → pages 2, 13, 108, 110[41] Y.-C. Cheng, J. Bellardo, P. Benko, A. C. Snoeren, G. M. Voelker, andS. Savage. Jigsaw: solving the puzzle of enterprise 802.11 analysis. InProceedings of the conference on Applications, technologies,architectures, and protocols for computer communications (SIGCOMM),2006. → pages 4, 44, 112, 121[42] Y.-C. Cheng, M. Afanasyev, P. Verkaik, P. Benko¨, J. Chiang, A. C.Snoeren, S. Savage, and G. M. Voelker. Automating cross-layer diagnosisof enterprise wireless networks. In Proceedings of the conference onApplications, technologies, architectures, and protocols for computercommunications (SIGCOMM), 2007. → pages 112[43] C. cheng Chen, E. Seo, H. Kim, and H. Luo. Self-learning collisionavoidance for wireless networks. In Proceedings of the IEEEInternational Conference on Computer Communications (INFOCOM),2006. → pages 45[44] C. F. Chiasserini and R. R. Rao. Performance of ieee 802.11 wlans in abluetooth environment. In Proceedings of IEEE Wireless Communicationsand Networking Conference, 2000. → pages 112[45] J. Deng, B. Liang, and P. K. Varshney. Tuning the carrier sensing range ofieee 802.11 mac. In Proceedings of IEEE Global CommunicationsConference (GLOBECOM), 2004. → pages 110[46] M. Fisk and W. chun Feng. Dynamic right-sizing in tcp. In Proceedings ofthe Los Alamos Computer Science Institute Symposium, 2001. → pages 52[47] S. Floyd and V. Jacobson. Random early detection gateways forcongestion avoidance. IEEE/ACM Trans. Netw., 1(4), 1993. → pages 48[48] F.Talucci, M.Gerla, and L.Fratta. Macabi (maca by invitation): A receiveroriented access protocol for wireless multiple networks. In Proceedings of128The IEEE International Symposium on Personal, Indoor and MobileRadio Communications (PIMRC), 1997. → pages 110[49] V. Gambiroza, B. Sadeghi, and E. W. Knightly. End-to-end performanceand fairness in multihop wireless backhaul networks. In Proceedings ofthe annual international conference on Mobile computing and networking(MobiCom), 2004. → pages 112[50] M. Garetto, J. Shi, and E. W. Knightly. Modeling media access inembedded two-flow topologies of multi-hop wireless networks. InProceedings of the annual international conference on Mobile computingand networking (MobiCom), 2005. → pages 2, 12, 13, 17, 109[51] S. Gollakota, S. D. Perli, and D. Katabi. Interference alignment andcancellation. In Proceedings of the conference on Applications,technologies, architectures, and protocols for computer communications(SIGCOMM), 2009. → pages 115[52] S. Gopal and D. Raychaudhuri. Experimental evaluation of the tcpsimultaneous-send problem in 802.11 wireless local area networks. InProceeding of the ACM SIGCOMM workshop on Experimentalapproaches to wireless network design and analysis (EWIND), 2005. →pages 112[53] R. Gummadi, D. Wetherall, B. Greenstein, and S. Seshan. Understandingand mitigating the impact of rf interference on 802.11 networks. InProceedings of the conference on Applications, technologies,architectures, and protocols for computer communications (SIGCOMM),2007. → pages 5[54] N. Gupta and P. R. Kuman. A performance analysis of the 802.11 wirelesslan medium access control. Communications in Information and Systems,4(4), 2004. → pages 109[55] T. Henderson, D. Kotz, and I. Abyzov. The changing usage of a maturecampus-wide wireless network. In Proceedings of the annualinternational conference on Mobile computing and networking(MobiCom), New York, NY, USA, 2004. → pages 3, 13, 44[56] K. Jain, J. Padhye, V. N. Padmanabhan, and L. Qiu. Impact of interferenceon multi-hop wireless network performance. In Proceedings of the annual129international conference on Mobile computing and networking(MobiCom), 2003. → pages 113[57] K. Jamieson, B. Hull, A. Miu, and H. Balakrishnan. Understanding thereal-world performance of carrier sense. In Proceeding of the ACMSIGCOMM workshop on Experimental approaches to wireless networkdesign and analysis (EWIND), 2005. → pages 110[58] A. P. Jardosh, K. N. Ramachandran, K. C. Almeroth, and E. M.Belding-Royer. Understanding link-layer behavior in highly congestedieee 802.11b wireless networks. In Proceeding of the ACM SIGCOMMworkshop on Experimental approaches to wireless network design andanalysis (EWIND), 2005. → pages 112[59] A. P. Jardosh, K. Mittal, K. N. Ramachandran, E. M. Belding, and K. C.Almeroth. Iqu: Practical queue-based user association management forwlans. In Proceedings of the annual international conference on Mobilecomputing and networking (MobiCom), 2006. → pages 111[60] Y. Jian, M. Zhang, and S. Chen. Achieving mac-layer fairness in csma/canetworks. IEEE/ACM Transactions on Networking (TON), 19(5):1472–1484, 2011. → pages 109[61] H.-J. Ju, I. Rubin, and Y.-C. Kuan. An adaptive rts/cts control mechanismfor ieee 802.11 mac protocol. In Proceedings of The Vehicular TechnologyConference, 2003. → pages 110[62] P. Karn. Maca: A new channel access method for packet radio. InProceedings of Computer Networking Conference, 1990. → pages 13, 108[63] H. Kim and J. C. Hou. Improving protocol capacity with model-basedframe scheduling in ieee 802.11-operated wlans. In Proceedings of theannual international conference on Mobile computing and networking(MobiCom), 2003. → pages 110[64] H. Kim and J. C. Hou. A fast simulation framework for ieee802.11-operated wireless lans. In Proceedings of the InternationalConference on Measurements and Modeling of Computer Systems(SIGMETRICS), 2004. → pages 109130[65] R. R. Kompella, S. Ramabhadran, I. Ramani, and A. C. Snoeren.Cooperative packet scheduling via pipelining in 802.11 wireless networks.In Proceeding of the ACM SIGCOMM workshop on Experimentalapproaches to wireless network design and analysis (EWIND), 2005. →pages 111[66] K. C.-J. Lin, S. Gollakota, and D. Katabi. Random access heterogeneousmimo networks. In Proceedings of the conference on Applications,technologies, architectures, and protocols for computer communications(SIGCOMM), 2011. → pages 116[67] R. Lotun. wypy : an extensible, online interference detection tool forwireless networks. M.Sc. Thesis, University of British Columbia, 2008. →pages 74, 123[68] S. Lu, V. Bharghavan, and R. Srikant. Fair scheduling in wireless packetnetworks. In Proceedings of the conference on Applications, technologies,architectures, and protocols for computer communications (SIGCOMM),1997. → pages 45[69] R. Mahajan, M. Rodrig, D. Wetherall, and J. Zahorjan. Analyzing themac-level behavior of wireless networks in the wild. In Proceedings of theconference on Applications, technologies, architectures, and protocols forcomputer communications (SIGCOMM), 2006. → pages 64, 71, 109, 112,113[70] P. McKenney. Stochastic fairness queuing. In Proceedings of the IEEEInternational Conference on Computer Communications (INFOCOM),1990. → pages 48[71] A. Mondal and A. Kuzmanovic. Removing exponential backoff from tcp.In ACM SIGCOMM Computer Communication Review, 2008. → pages 73[72] T. Nandagopal, S. Lu, and V. Bharghavan. A unified architecture for thedesign and evaluation of wireless fair queueing algorithms. InProceedings of the annual international conference on Mobile computingand networking (MobiCom), 1998. → pages 45[73] D. Niculescu. Interference map for 802.11 networks. In Proceedings ofthe Internet Measurement Conference on Internet MeasurementConference (IMC), 2007. → pages 12, 64, 109, 113131[74] J. Padhye, S. Agarwal, V. N. Padmanabhan, L. Qiu, A. Rao, and B. Zill.Estimation of link interference in static multi-hop wireless networks. InProceedings of the Internet Measurement Conference on InternetMeasurement Conference (IMC), 2005. → pages 5, 60, 64, 113[75] A. Patro, S. Govindan, and S. Banerjee. Observing home wirelessexperience through wifi aps. In Proceedings of the annual internationalconference on Mobile computing and networking (MobiCom), 2013. →pages 114[76] M. Portole´s, Z. Zhong, and S. Choi. Ieee 802.11 downlink traffic shapingscheme for multi-user service enhancement. In Proceedings of The IEEEInternational Symposium on Personal, Indoor and Mobile RadioCommunications (PIMRC), 2003. → pages 112[77] L. Qiu, Y. Zhang, F. Wang, M. K. Han, and R. Mahajan. A general modelof wireless interference. In Proceedings of the annual internationalconference on Mobile computing and networking (MobiCom), 2007. →pages 60, 64, 71, 109, 113[78] H. S. Rahul, S. Kumar, and D. Katabi. Jmb: Scaling wireless capacitywith user demands. In Proceedings of the conference on Applications,technologies, architectures, and protocols for computer communications(SIGCOMM), 2012. → pages 117[79] G. Raleigh and J. Cioffi. Spatio-temporal coding for wirelesscommunication. IEEE Transactions on Communications, 46(3):357–366,1998. → pages 110[80] P. Ramanathan and P. Agrawal. Adapting packet fair queueing algorithmsto wireless networks. In Proceedings of the annual internationalconference on Mobile computing and networking (MobiCom), 1998. →pages 45[81] S. Rayanchu, V. Shrivastava, S. Banerjee, and R. Chandra. Fluid:Improving throughputs in enterprise wireless lans through flexiblechannelization. In Proceedings of the annual international conference onMobile computing and networking (MobiCom), 2011. → pages 117[82] C. Reis, R. Mahajan, M. Rodrig, D. Wetherall, and J. Zahorjan.Measurement-based models of delivery and interference in static wireless132networks. In Proceedings of the conference on Applications, technologies,architectures, and protocols for computer communications (SIGCOMM),2006. → pages 60, 64, 71, 109, 113[83] M. Rodrig, C. Reis, R. Mahajan, D. Wetherall, and J. Zahorjan.Measurement-based characterization of 802.11 in a hotspot setting. InProceeding of the ACM SIGCOMM workshop on Experimentalapproaches to wireless network design and analysis (EWIND), 2005. →pages 4, 44[84] B. Sadeghi, V. Kanodia, A. Sabharwal, and E. Knightly. Opportunisticmedia sccess for multirate ad hoc networks. In Proceedings of the annualinternational conference on Mobile computing and networking(MobiCom), 2002. → pages 45, 110[85] J. Semke, J. Mahdavi, and M. Mathis. Automatic tcp buffer tuning. InProceedings of the conference on Applications, technologies,architectures, and protocols for computer communications (SIGCOMM),1998. → pages 52[86] A. Sheth, C. Doerr, D. Grunwald, R. Han, and D. Sicker. Mojo: adistributed physical layer anomaly detection system for 802.11 wlans. InProceedings of The International Conference on Mobile Systems,Applications, and Services (MobiSys), 2006. → pages 112[87] V. Shrivastava, N. Ahmed, S. Rayanchu, S. Banerjee, S. Keshav,K. Papagiannaki, and A. Mishra. Centaur: realizing the full potential ofcentralized wlans through a hybrid data path. In Proceedings of the annualinternational conference on Mobile computing and networking(MobiCom), 2009. → pages 111[88] V. Shrivastava, S. Rayanchu, S. Banerjee, and K. Papagiannaki. Pie in thesky: online passive interference estimation for enterprise wlans. InProceedings of The USENIX Symposium on Networked Systems Designand Implementation (NSDI), 2011. → pages 65, 113, 114[89] G. Tan and J. Guttag. Time-based fairness improves performance inmulti-rate wlans. In Proceedings of the annual conference on USENIXAnnual Technical Conference, 2004. → pages 59, 111133[90] G. Tan and J. Guttag. Long-term time-share guarantees are necessary forwireless lans. In Proceedings of the 11th workshop on ACM SIGOPSEuropean workshop, 2004. → pages 45, 58, 110, 122[91] L. Tassiulas and S. Sarkar. Maxmin fair scheduling in wireless networks.In Proceedings of the IEEE International Conference on ComputerCommunications (INFOCOM), 2002. → pages 111[92] N. H. Vaidya, P. Bahl, and S. Gupta. Distributed fair scheduling in awireless lan. In Proceedings of the annual international conference onMobile computing and networking (MobiCom), 2000. → pages 110, 111[93] M. Vutukuru, K. Jamieson, and H. Balakrishnan. Harnessing exposedterminals in wireless networks. In Proceedings of The USENIXSymposium on Networked Systems Design and Implementation (NSDI),2008. → pages 113[94] B. White, J. Lepreau, L. Stoller, R. Ricci, S. Guruprasad, M. Newbold,M. Hibler, C. Barb, and A. Joglekar. An integrated experimentalenvironment for distributed systems and networks. In Proceedings of theUSENIX Symposium on Operating Systems Design and Implementation(OSDI), 2002. → pages 66, 74[95] S. H. Y. Wong, S. Lu, H. Yang, and V. Bharghavan. Robust rate adaptationfor 802.11 wireless networks. In Proceedings of the annual internationalconference on Mobile computing and networking (MobiCom), 2006. →pages 45, 111[96] A. Woo, T. Tong, and D. Culler. Taming the underlying challenges ofreliable multihop routing in sensor networks. In Proceedings of The ACMConference on Embedded Networked Sensor Systems, 2003. → pages 113[97] K. Xu, M. Gerla, and S. Bae. How effective is the ieee 802.11 rts/ctshandshake in ad hoc networks. In Proceedings of IEEE GlobalCommunications Conference (GLOBECOM), 2002. → pages 110[98] X. Yang and N. H. Vaidya. On the physical carrier sense in wirelessad-hoc networks. In Proceedings of the IEEE International Conference onComputer Communications (INFOCOM), 2005. → pages 110134[99] T. Yoo and A. Goldsmith. On the optimality of multiantenna broadcastscheduling using zero-forcing beamforming. IEEE Journal on SelectedAreas in Communications, 24:528–541, 2006. → pages 116[100] H. Yu, O. Bejarano, and L. Zhong. Combating inter-cell interference in802.11ac-based multi-user mimo networks. In Proceedings of the annualinternational conference on Mobile computing and networking(MobiCom), 2014. → pages 117[101] S. Yun, D. Kim, and L. Qiu. Fine-grained spectrum adaptation in wifinetworks. In Proceedings of the annual international conference onMobile computing and networking (MobiCom), 2013. → pages 118[102] X. Zeng, R. Bagrodia, and M. Gerla. Glomosim: A library for parallelsimulation of large-scale wireless networks. In in Workshop on Paralleland Distributed Simulation, 1998. → pages 27, 30[103] H. Zhai and Y. Fang. Physical carrier sensing and spatial reuse inmultirate and multihop wireless ad hoc networks. In Proceedings of theIEEE International Conference on Computer Communications(INFOCOM), 2006. → pages 110[104] H. Zhai, Y. Kwon, and Y. Fang. Performance analysis of ieee 802.11 macprotocols in wireless lans. Wireless Communications and MobileComputing, Special Issue on Emerging WLAN Technologies andApplications, 4, 2004. → pages 109[105] W. Zhou, T. Bansal, P. Sinha, and K. Srinivasan. Bbn: Throughput scalingin dense enterprise wlans with bind beamforming and nulling. InProceedings of the annual international conference on Mobile computingand networking (MobiCom), 2014. → pages 116135


Citation Scheme:


Citations by CSL (citeproc-js)

Usage Statistics



Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            async >
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:


Related Items