Modeling the IEE 802.11 networks MAC layer using diffusion approximation

• Autorzy: Czachórski T. , Grochla K. , Nycz T. , Pekergin F.

Warianty tytułu

PL

Aproksymacja dyfuzyjna w modelowaniu dostępu do łącza w sieciach bezprzewodowych zgodnych ze standardem IEEE 802.11

• Języki publikacji: EN

Abstrakty

EN

The article presents an analytical model of wireless networks using the IEEE 802.11 protocol to access the transport medium. The model allows to determine such key factors of the quality of service as transmission delays and losses. The model is based on diffusion approximation approach whichwas proposed three decades ago to model wired networks. We show that it can be adapted to take into consideration the input streams with general interarrival time distributions and servers with general service time distributions. The diffusion approximation has been chosen because of fairly general assumptions of models based on it, hard to be represented in Markov models. A queueing network model can have an arbitrary topology, the intensity of transmitted flows can be represented by non-Poisson (even selfsimilar) streams, the service times at nodes can be defined by general distributions. These assumptions are important: because of the CSMA/CA algorithm, the overall times needed to sent a packet are far from being exponentially distributed and therefore the flows between nodes are non-Poisson. Diffusion approximation allows us also to analyse the of transient behaviour of a network when traffic intensity is changing with time.

PL

Przedstawiono model analityczny sieci bezprzewodowej, w której dostęp do łącza jest zgodny ze standardem IEEE 802.11. Model pozwala wyznaczyć podstawowe dla oceny efektywności pracy sieci parametry, takie jak opóźnienie transmisji i prawdopodobieństwo straty przesyłanych pakietów. Model wykorzystuje metodę aproksymacji dyfuzyjnej, jedną z metod tworzenia kolejkowych modeli sieci komputerowych, stosowaną od ponad trzydziestu lat w modelowaniu sieci przewodowych. Z punktu widzenia teorii kolejek, do zalet aproksymacji dyfuzyjnej nalezą: możliwość analizy stanów nieustalonych, a więc opisu zachowania się kolejek przy zmiennych w czasie natężeniach transmitowanych strumieni danych, uwzględnienie w opisie stanowisk dowolnych rozkładów między nadchodzącymi zadaniami i dowolnych czasów ich obsługi, opis dowolnych topologii sieci stanowisk obsługi. Są to cechy modelu bardzo pożądane także przy opisie sieci bezprzewodowych, gdzie w wyniku stosowania w standardzie IEEE 802.11 algorytmu CSMA/CA rywalizacyjnego dostępu do łącza, transmitowane strumienie danych odbiegają mocno od strumieni Poissona, a przesyły charakteryzują się zmiennym natężeniem. Artykuł pokazuje, jak rywalizacyjny algorytm dostępu do łącza wpływa na wartość średnią i wariancję czasu obsługi uwzględniane w modelu dyfuzyjnym, a następnie na parametry przesyłanych strumieni danych.

Słowa kluczowe

EN

diffusion approximation; Queueing network models; Distributed coordination function; CSMA/CA; IEEE 802.11 protocol

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2009
• Tom: Vol. 21, No. 3-4
• Strony: 205--223
• Opis fizyczny: Bibliogr. 28 poz., rys.

Twórcy

autor

Czachórski T.

autor

Grochla K.

autor

Nycz T.

autor

Pekergin F.

• Institute of Computer Science Silesian Technical University,

Bibliografia

• 1. A. Banchs, A. Azcorra, C. García, R. Cuevas: Applications and Challenges of the 802.11e EDCA Mechanism: An Experimental Study, IEEE Network, July/August 2005, pp. 52-58.
• 2. G. Bianchi: Performance Analysis of the IEEE 802.11 Distributed Coordination Function, IEEE J. on Selected Areas in Communications, vol. 18, no. 3, March 2000, pp. 535-547.
• 3. P.J. Burke: The Output of a Queueing System, Operations Research, vol. 4, no. 6, pp. 699-704.
• 4. G. R. Cantieni, Q. Ni, Ch. Barakat, T. Turletti: Performance analysis under finite load and improvements for multirate 802.11, Computer Communications 28 (2005) pp. 1095-1109.
• 5. R. P. Cox, H. D. Miller, The Theory of Stochastic Processes, Chapman and Hall, London (1965).
• 6. T. Czachórski: A Method to Solve Diffusion Equation with Instantaneous Return Processes Acting as Boundary Conditions, Bulletin of Polish Academy of Sciences, vol. 41 no. 4, 1993.
• 7. T. Czachórski, J. M. Fourneau, F. Pekergin: Diffusion Model of an ATM Network Node, Bulletin of Polish Academy of Sciences, vol. 41 no. 4, 1993.
• 8. T. Czachórski, J.-M. Fourneau, T. Nycz, F. Pekergin: Diffusion approximation model of multiserver stations with losses, (Electronic Notes in Theoretical Computer Science). Vol. 232, March 2009, pp. 125-143.
• 9. T. Czachórski, T. Nycz, F. Pekergin: Transient states of priority queues – a diffusion approximation study, Proc. of 2009 Fifth Advanced International Conference on Telecommunications (AICT 2009), Venice, Italy, 24-28 May 2009.
• 10. T. Czachórski, K. Grochla, F. Pekergin: Diffusion approximation model for the distribution of packet travel time at sensor networks, a chapter in a book: Traffic and Performance Engineering for Heterogeneous Networks, edited by D. Kouvatsos, River Publishers, 2009.
• 11. W. Feller: An introduction to probability theory and applications, Vol. 1, pp. 287-301, Wiley, 3rd edition, 1968, New York.
• 12. E. Gelenbe: On Approximate Computer Systems Models, J. ACM, vol. 22, no. 2, 1975.
• 13. E. Gelenbe, G. Pujolle: The Behaviour of a Single Queue in a General Queueing Network, Acta Informatica, Vol. 7, Fasc. 2, pp.123-136, 1976.
• 14. E. Gelenbe: Probabilistic models of computer systems. Part II, Acta Informatica, vol. 12, pp. 285-303, 1979.
• 15. T-S. Ho, K.C. Chen: Performance Analysis of IEEE 802.11 CSMA/CA Medium Access Control Protocol, pp. 407-411, 1996.
• 16. D. Iglehart, W. Whitt: Multiple Channel Queues in Heavy Traffic, Part I-III, Advances in Applied Probability, vol. 2, pp. 150-177, 355-369, 1970.
• 17. D. Iglehart: Weak Convergence in Queueing Theory, Advances in Applied Probability, vol. 5, pp. 570-594, 1973.
• 18. L. Kleinrock: Queueing Systems, vol. I: Theory, vol. II: Computer Applications Wiley, New York 1975, 1976.
• 19. H. Kobayashi: Application of the diffusion approximation to queueing networks, Part 1: Equilibrium queue distributions, J.ACM, vol. 21, no. 2, pp. 316-328, Part 2: Nonequilibrium distributions and applications to queueing modeling, J.ACM, vol. 21, no. 3, pp. 459-469, 1974.
• 20. H. Kobayashi: Modeling and Analysis: An Introduction to System Performance Evaluation Methodology, Addison Wesley, Reading, Mass. 1978.
• 21. H. Kobayashi, Q. Ren: A Diffusion Approximation Analysis of an ATM Statistical Multiplexer with Multiple Types of Traffic, Part I: Equilibrium State Solutions, Proc. of IEEE International Conf. on Communications, ICC ’93, pp. 1047-1053, May 23-26, 1993, Geneva, Switzerland.
• 22. D. Malone, K. Duffy, D. Leith: Modeling the 802.11 Distributed Coordination Function in Nonsaturated Heterogeneous Conditions, IEEE/ACM Transactions on Networking, vol. 15, no. 1, February 2007, pp. 159-172.
• 23. G. F. Newell: Queues with time-dependent rates, Part I: The transition through saturation; Part II: The maximum queue and return to equilibrium;, Part III: A mild rush hour, J. Appl. Prob. vol. 5, pp. 436-451, 579-590, 591-606. 1968.
• 24. G. F. Newell: Applications of Queueing Theory, Chapman and Hall, London 1971.
• 25. OMNET ++ site: http://www.omnetpp.org/
• 26. M.F. Uddin, Ch. Assi: Joint routing and scheduling for multi-hop wireless mesh networks with variable-width channel allocation.
• 27. L. Yun, L. Ke-ping, Z.Wei-Liang,W. Chong-Gang, Analyzing the Channel Access Delay of IEEE 802.11 DCF, Globecom 2005, pp. 2997-3001.
• 28.E. Ziouva, T. Antonakopoulos: CSMA/CA performance under high traffic conditions, throughput and delay analysis, Computer Communications, vol. 25, 2002, pp. 313-321.