Analyzing the MAC-level behavior of wireless networks in the wild

ABSTRACT

We present Wit, a non-intrusive tool that builds on passive monitoring to analyze the detailed MAC-level behavior of operational wireless networks. Wit uses three processing steps to construct an enhanced trace of system activity. First, a robust merging procedure combines the necessarily incomplete views from multiple, independent monitors into a single, more complete trace of wireless activity. Next, a novel inference engine based on formal language methods reconstructs packets that were not captured by any monitor and determines whether each packet was received by its destination. Finally, Wit derives network performance measures from this enhanced trace; we show how to estimate the number of stations competing for the medium. We assess Wit with a mix of real traces and simulation tests. We find that merging and inference both significantly enhance the originally captured trace. We apply Wit to multi-monitor traces from a live network to show how it facilitates 802.11 MAC analyses that would otherwise be difficult or rely on less accurate heuristics.

REFERENCES

• 1: IEEE Std. 802.11i - Amendment 6: Medium access control security enhancements, 2004.
• 2: Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 3: Aditya Akella , Jeffrey Pang , Bruce Maggs , Srinivasan Seshan , Anees Shaikh, A comparison of overlay routing and multihoming route control, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 4: Anand Balachandran , Geoffrey M. Voelker , Paramvir Bahl , P. Venkat Rangan, Characterizing user behavior and network performance in a public wireless LAN, Proceedings of the 2002 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 15-19, 2002, Marina Del Rey, California
• 5: Magdalena Balazinska , Paul Castro, Characterizing mobility and network usage in a corporate wireless local-area network, Proceedings of the 1st international conference on Mobile systems, applications and services, p.303-316, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066127]
• 6: Yu-Chung Cheng , John Bellardo , Péter Benkö , Alex C. Snoeren , Geoffrey M. Voelker , Stefan Savage, Jigsaw: solving the puzzle of enterprise 802.11 analysis, Proceedings of the 2006 conference on Applications, technologies, architectures, and protocols for computer communications, September 11-15, 2006, Pisa, Italy
• 7: F. Chinchilla, M. Lindsey, and M. Papadopouli. Analysis of wireless information locality and association patterns in a campus. In INFOCOM, 2004.
• 8: Tristan Henderson , David Kotz , Ilya Abyzov, The changing usage of a mature campus-wide wireless network, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023739]
• 9: Martin Heusse , Franck Rousseau , Romaric Guillier , Andrzej Duda, Idle sense: an optimal access method for high throughput and fairness in rate diverse wireless LANs, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 10: Kyle Jamieson , Bret Hull , Allen Miu , Hari Balakrishnan, Understanding the real-world performance of carrier sense, Proceeding of the 2005 ACM SIGCOMM workshop on Experimental approaches to wireless network design and analysis, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080148.1080160]
• 11: A. Jardosh, K. Ramachandran, K. Almeroth, and E. Belding-Royer. Understanding congestion in IEEE 802.11b wireless networks. In IMC, 2005.
• 12: David Kotz , Calvin Newport , Robert S. Gray , Jason Liu , Yougu Yuan , Chip Elliott, Experimental evaluation of wireless simulation assumptions, Proceedings of the 7th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, October 04-06, 2004, Venice, Italy [doi>10.1145/1023663.1023679]
• 13: Craig Labovitz , Abha Ahuja , Abhijit Bose , Farnam Jahanian, Delayed Internet routing convergence, Proceedings of the conference on Applications, Technologies, Architectures, and Protocols for Computer Communication, p.175-187, August 28-September 01, 2000, Stockholm, Sweden
• 14: D. Lee , A. N. Netravali , K. K. Sabnani , B. Sugla , A. John, Passive testing and applications to network management, Proceedings of the 1997 International Conference on Network Protocols (ICNP '97), p.113, October 28-31, 1997
• 15: Stefan Mangold , Zhun Zhong , Guido R. Hiertz , Bernhard Walke, IEEE 802.11e/802.11k wireless LAN: spectrum awareness for distributed resource sharing: Research Articles, Wireless Communications & Mobile Computing, v.4 n.8, p.881-902, December 2004 [doi>10.1002/wcm.v4:8]
• 16: Allen Miu , Hari Balakrishnan , Can Emre Koksal, Improving loss resilience with multi-radio diversity in wireless networks, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080832]
• 17: Vern Paxson, Automated packet trace analysis of TCP implementations, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.167-179, September 14-18, 1997, Cannes, France
• 18: Vern Paxson, End-to-end routing behavior in the Internet, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.25-38, August 28-30, 1996, Palo Alto, California, United States
• 19: Qualnet network simulator by Scalable Network Technologies. http://www.qualnet.com.
• 20: I. Ramani and S. Savage. Syncscan: Practical fast handoff for 802.11 infrastructure netwroks. In INFOCOM, 2005.
• 21: Maya Rodrig , Charles Reis , Ratul Mahajan , David Wetherall , John Zahorjan, Measurement-based characterization of 802.11 in a hotspot setting, Proceeding of the 2005 ACM SIGCOMM workshop on Experimental approaches to wireless network design and analysis, August 22-22, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080148.1080150]
• 22: Stefan Savage , Andy Collins , Eric Hoffman , John Snell , Thomas Anderson, The end-to-end effects of Internet path selection, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.289-299, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 23: D. Schwab and R. Bunt. Characterising the use of a campus wireless network. In INFOCOM, 2004.
• 24: Neil Spring , Ratul Mahajan , David Wetherall, Measuring ISP topologies with rocketfuel, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 25: G. Tan and J. Guttag. The 802. 11 MAC protocol leads to inefficient equilibria. In INFOCOM, 2005.
• 26: Diane Tang , Mary Baker, Analysis of a local-area wireless network, Proceedings of the 6th annual international conference on Mobile computing and networking, p.1-10, August 06-11, 2000, Boston, Massachusetts, United States [doi>10.1145/345910.345912]
• 27: Jihwang Yeo , Moustafa Youssef , Ashok Agrawala, A framework for wireless LAN monitoring and its applications, Proceedings of the 2004 ACM workshop on Wireless security, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1023646.1023660]
• 28: Yin Zhang , Lee Breslau , Vern Paxson , Scott Shenker, On the characteristics and origins of internet flow rates, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 29: Jerry Zhao , Ramesh Govindan, Understanding packet delivery performance in dense wireless sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958493]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

General Terms:
Measurement, Performance

Keywords:
802.11 MAC, measurement tool, passive monitoring