Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The widespread availability of 802.11-based hardware has made it the premier choice of both researchers and practitioners for developing new wireless networks and applications. However, the ever increasing set of demands posed by these applications is stretching the 802.11 MAC protocol beyond its intended capabilities. For example, 802.11 provides no control over allocation of resources, and the default allocation policy is ill-suited for heterogeneous environments and multi-hop networks. Fairness problems are further exacerbated in multi-hop networks due to link asymmetry and hidden terminals. In this paper, we take a first step towards addressing these problems without replacing the MAC layer by presenting the design and the implementation of an Overlay MAC Layer (OML), that works on top of the 802.11 MAC layer. OML uses loosely-synchronized clocks to divide the time in to equal size slots, and employs a distributed algorithm to allocate these slots among competing nodes. We have implemented OML in both a simulator and on a wireless testbed using the Click modular router. Our evaluation shows that OML can not only provide better flexibility but also improve the fairness, throughput and predictability of 802.11 networks.

REFERENCES

• 1: AiroPeek NX - Wireless Network Protocol Analyzer. http://www.wildpackets.com/.
• 2: Ethereal - Network Protocol Analyzer. http://www.ethereal.com/.
• 3: MadWifi. http://madwifi.sourceforge.net/.
• 4: MIT grid project. http://www.pods.lcs.mit.edu/grid/.
• 5: MIT roofnet. http://www.pdos.lcs.mit.edu/roofnet/.
• 6: Netgear. http://www.netgear.com/.
• 7: The Qualnet Simulator from Scalable Networks Inc. http://www.scalable-networks.com/.
• 8: David Andersen , Hari Balakrishnan , Frans Kaashoek , Robert Morris, Resilient overlay networks, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 9: Suman Banerjee , Bobby Bhattacharjee , Christopher Kommareddy, Scalable application layer multicast, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 10: Lichun Bao , J. J. Garcia-Luna-Aceves, Hybrid Channel Access Scheduling in Ad Hoc Networks, Proceedings of the 10th IEEE International Conference on Network Protocols, p.46-57, November 12-15, 2002
• 11: Lichun Bao , J. J. Garcia-Luna-Aceves, Distributed dynamic channel access scheduling for ad hoc networks, Journal of Parallel and Distributed Computing, v.63 n.1, p.3-14, January 2003 [doi>10.1016/S0743-7315(02)00039-4]
• 12: V. Bharghavan, S. Lu, and T. Nandagopal. Fair queueing in wireless networks: Issues and approaches. IEEE Personal Communications Magazine, 1999.
• 13: S. Biswas and R. Morris. Opportunistic routing in multihop wireless networks. In HOTNETS, 2003.
• 14: D.-M. Chiu , R. Jain, Analysis of the increase and decrease algorithms for congestion avoidance in computer networks, Computer Networks and ISDN Systems, v.17 n.1, p.1-14, June 10, 1989 [doi>10.1016/0169-7552(89)90019-6]
• 15: Yang-hua Chu , Sanjay G. Rao , Hui Zhang, A case for end system multicast (keynote address), Proceedings of the 2000 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.1-12, June 18-21, 2000, Santa Clara, California, United States
• 16: I. Cidon , M. Sidi, Distributed Assignment Algorithms for Multihop Packet Radio Networks, IEEE Transactions on Computers, v.38 n.10, p.1353-1361, October 1989 [doi>10.1109/12.35830]
• 17: Wireless networking reference - community wiress/rooftop systems. http://www.practicallynetworked.com/.
• 18: Douglas S. J. De Couto , Daniel Aguayo , John Bicket , Robert Morris, A high-throughput path metric for multi-hop wireless routing, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.939000]
• 19: A. Demers , S. Keshav , S. Shenker, Analysis and simulation of a fair queueing algorithm, Symposium proceedings on Communications architectures & protocols, p.1-12, September 25-27, 1989, Austin, Texas, United States
• 20: Richard Draves , Jitendra Padhye , Brian Zill, Comparison of routing metrics for static multi-hop wireless networks, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 21: Jeremy Elson , Deborah Estrin, Time Synchronization for Wireless Sensor Networks, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.186, April 23-27, 2001
• 22: Violeta Gambiroza , Bahareh Sadeghi , Edward W. Knightly, End-to-end performance and fairness in multihop wireless backhaul networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023749]
• 23: M. Heusse, F. Rousseau, G. Berger-Sabbatel, and A. Duda. Performance anomaly of 802.11b. In INFOCOM, San Francisco, USA, March-April 2003.
• 24: Kamal Jain , Jitendra Padhye , Venkata N. Padmanabhan , Lili Qiu, Impact of interference on multi-hop wireless network performance, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938993]
• 25: David B. Johnson , David A. Maltz , Josh Broch, DSR: the dynamic source routing protocol for multihop wireless ad hoc networks, Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 26: Eddie Kohler , Robert Morris , Benjie Chen , John Jannotti , M. Frans Kaashoek, The click modular router, ACM Transactions on Computer Systems (TOCS), v.18 n.3, p.263-297, Aug. 2000 [doi>10.1145/354871.354874]
• 27: L. M. S. C. of the IEEE Computer Society. Wireless LAN medium access control (MAC) and physical layer (PHY) specifications. IEEE Standard 802.11, 1999.
• 28: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 29: C. Perkins. Ad hoc On demand Distance Vector (AODV) routing. IETF Internet Draft, 1997.
• 30: L. Pond and V. Li. A distributed time-slot assignment protocol for mobile multi-hop broadcast packet radio networks. In MILCOM, 1999.
• 31: B. Raman and K. Chebrolu. Revisiting MAC design for an 802.11-based mesh network. In HOTNETS, 2004.
• 32: A. Rao and I. Stoica. An overlay MAC layer for 802.11 networks. Technical Report UCB//CSD-04-1317, University of California, Berkeley, 2004.
• 33: Kay Römer, Time synchronization in ad hoc networks, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501436.501440]
• 34: B. Sadeghi , V. Kanodia , A. Sabharwal , E. Knightly, Opportunistic media sccess for multirate ad hoc networks, Proceedings of the 8th annual international conference on Mobile computing and networking, September 23-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570645.570650]
• 35: Ulrich Schmid , Klaus Schossmaier, Interval-based Clock Synchronization, Real-Time Systems, v.12 n.2, p.173-228, March 1997 [doi>10.1023/A:1007957901560]
• 36: Ion Stoica , Daniel Adkins , Shelley Zhuang , Scott Shenker , Sonesh Surana, Internet indirection infrastructure, Proceedings of the 2002 conference on Applications, technologies, architectures, and protocols for computer communications, August 19-23, 2002, Pittsburgh, Pennsylvania, USA
• 37: C. A. Waldspurger and W. E. Weihl. Lottery scheduling: Flexible proportional-share resource management. In Operating Systems Design and Implementation, pages 1--11, 1994.
• 38: Y. Yi and S. Shakkottai. Hop-by-hop congestion control over a wireless multi-hop network. In INFOCOM, 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.5 Local and Wide-Area Networks
          Subjects: Access schemes

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.6 Simulation Output Analysis

General Terms:
Design, Management