Queuing analysis of multi-hop CSMA/CA wireless networks handling many traffic flows

ABSTRACT

In this paper a semi-analytical model for the evaluation of the queuing performance in CSMA-CA multi-hop wireless networks with arbitrary topology is proposed. The intrinsic fairness of single-hop wireless networks can be used to model the network as a processor sharing system with multiple queues, one for each node, and a fair scheduling regime. In the multi-hop scenario, the queuing performance depends on the access protocol, the network topology and the traffic profiles on all links. In a previous paper a model is introduced which allows the calculation of the saturation throughput of nodes in multi-hop CSMA-CA networks with RTS/CTS enabled access. A simplified version of the method is used to estimate the resources of the servers in a many-sources large deviations analysis of a queuing system with multiple coupled servers. The queuing performance of wireless networks can be evaluated by mapping the different servers to the nodes in the network. The cumulative complementary distribution function of the buffer occupation of a node for different topologies is calculated by a novel method and compared to the results of an event-driven simulation with the same settings. A good fit between the semi-analytical model and the simulation is obtained.

REFERENCES

• 1: IEEE 802.11-1999 (R2003), Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications, 1999 Ed. (Reaff. 2003), June 2003.
• 2: IEEE 802.11b-1999, Supplement to Part 11: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) specifications: Higher speed Physical Layer Extension in the 2.4 GHz Band, 1999.
• 3: G. Bianchi. Performance Analysis of the IEEE 802.11 Distributed Coordination Function. IEEE Journal on Selected Areas in Communications, 18(3):535--547, March 2000.
• 4: R. Boorstyn, A. Kershenbaum, B. Maglaris, and V. Sahin. Throughput Analysis in Multihop CSMA Packet Radio Networks. IEEE Trans. on Communications, 35(3):267--274, March 1987.
• 5: J. Brazio, and F. Tobagi. Theoretical Aspects in Throughput Analysis of Multihop Packet Radio Networks. in Proc. IEEE ICC '84, The Netherlands, June 1984.
• 6: W. Press, S. Teukolsky, W. Vetterling, and B. Flannery. Numerical Recipes (Third Edition). Cambridge University Press, 2007.
• 7: M. Garetto, T. Salonidis, and E. Knightly. Modeling Per-flow Throughput and Capturing Starvation in CSMA Multi-hop Wireless Networks. In Proc. IEEE INFOCOM, Spain, 2006.
• 8: B. Lauwens, B. Scheers, and A. Van de Capelle, Buffer Occupation Probability of Trace-Driven Background Streams in Hybrid Simulation. In Proc. IEEE ICC '07, Scotland, June 2007.
• 9: B. Lauwens, B. Scheers, J. Potemans, and A. Van de Capelle, Hybrid Simulation of a FIFO Queuing System with Trace-Driven Background Traffic. In Proc. Valuetools 2007, France, October 2007.
• 10: B. Lauwens, B. Scheers, and A. Van de Capelle, Throughput Analysis of Multi-Hop CSMA/CA Wireless Networks. Submitted IEEE WCNC, USA, April 2008.
• 11: A. Kumar, E. Altman, D. Miorandi, and M. Goyal. New insights from a fixed point analysis of single cell IEEE 802.11 WLANs. In Proc. IEEE INFOCOM, USA, March 2005.
• 12: X. Wang, and K. Kar. Throughput Modeling and Fairness Issues in CSMA/CA Based Ad-Hoc Networks. In Proc. IEEE INFOCOM, USA, March 2005.
• 13: A. Ganesh, N. O'Conell, and D. Wischik. Big queues. Springer, 2004.
• 14: N. Likhanov, and R. Mazumdar. Cell Loss Asymptotics in Buffers fed with Large Number of Independent Stationary Sources. In Proc. IEEE INFOCOM, USA, 1998.
• 15: S. Delas, R. Mazumdar, and C. Rosenberg. Cell Loss in Priority Systems handling Many Sources. IEEE INFOCOM, USA, March 1999.
• 16: C. Courcoubetis, and R. Weber. Buffer Overflow Asymptotics for a Switch handling Many Traffic Sources. Journal of Applied Probability, 33:886--903, 1996.
• 17: The internet traffic archive. http://ita.ee.Ibl.gov/.
• 18: Nlanr: network & measurement analysis. http://pma.nlanr.net/.
• 19: N. Bleistein, and R. Handelsman. Asymptotic Expansions of Integrals. Dover Publications, 1986
• 20: P. Spelucci. DONLP: A SQP method for general nonlinear programs using only equality constrained subproblems. http://plato.la.asu.edu/donlp2.html/.
• 21: M. Powell. TOLMIN: A Fortran Package for Linearly Constrained Optimization Calculation. DAMTP, 1989/NA2, 1989.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS