[go: up one dir, main page]
More Web Proxy on the site http://driver.im/
Skip to main content
Springer Nature Link
Log in

Diffusion Approximation as a Modelling Tool

  • Chapter
Network Performance Engineering

Part of the book series: Lecture Notes in Computer Science ((LNCCN,volume 5233))

Abstract

Diffusion theory is already a vast domain of knowledge. This tutorial lecture does not cover all results; it presents in a coherent way an approach we have adopted and used in analysis of a series of models concerning evoluation of some traffic control mechanisms in computer, especially ATM, networks. Diffusion approximation is presented from engineer’s point of view, stressing its utility and commenting numerical problems of its implementation. Diffusion approximation is a method to model the behavior of a single queueing station or a network of stations. It allows one to include in the model general sevice times, general (also correlated) input streams and to investigate transient states, which, in presence of bursty streams (e.g. of multimedia transfers) in modern networks, are of interest.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
GBP 19.95
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
GBP 93.50
Price includes VAT (United Kingdom)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Atmaca, T., Czachórski, T., Pekergin, F.: A Diffusion Model of the Dynamic Effects of Closed-Loop Feedback Control Mechanisms in ATM Networks. In: 3rd IFIP Workshop on Performance Modelling and Evaluation of ATM Networks, Ilkley, UK, July 4-7 (1995); rozszerzona wersja w. Archiwum Informatyki Teoretycznej i Stosowanej (1), 41–56 (1999)

    Google Scholar 

  2. Burke, P.J.: The Output of a Queueing System. Operations Research 4(6), 699–704

    Google Scholar 

  3. Cox, R.P., Miller, H.D.: The Theory of Stochastic Processes. Chapman and Hall, London (1965)

    MATH  Google Scholar 

  4. Czachórski, T.: A Multiqueue Approximate Computer Performance Model with Priority Scheduling and System Overhead. Podstawy Sterowania 10(3), 223–240 (1980)

    MathSciNet  MATH  Google Scholar 

  5. Czachórski, T.: A diffusion process with instantaneous jumps back and some its applications. Archiwum Informatyki Teoretycznej i Stosowanej 20(1-2), 27–46

    Google Scholar 

  6. Czachórski, T., Fourneau, J.M., Pekergin, F.: Diffusion Model of the Push-Out Buffer Management Policy. In: IEEE INFOCOM 1992, The Conference on Computer Communications, Florence (1992)

    Google Scholar 

  7. Czachórski, T.: A method to solve diffusion equation with instantaneous return processes acting as boundary conditions. Bulletin of Polish Academy of Sciences, Technical Sciences 41(4) (1993)

    Google Scholar 

  8. Czachórski, T., Fourneau, J.M., Pekergin, F.: Diffusion model of an ATM Network Node. Bulletin of Polish Academy of Sciences, Technical Sciences 41(4) (1993)

    Google Scholar 

  9. Czachórski, T., Fourneau, J.M., Pekergin, F.: Diffusion Models to Study Nonstationary Traffic and Cell Loss in ATM Networks. In: ACM 2nd Workshop on ATM Networks, Bradford (July 1994)

    Google Scholar 

  10. Czachórski, T., Fourneau, J.M., Kloul, L.: Diffusion Approximation to Study the Flow Synchronization in ATM Networks. In: ACM 3rd Workshop on ATM Networks, Bradford (July 1995)

    Google Scholar 

  11. Czachórski, T., Fourneau, J.M., Pekergin, F.: The dynamics of cell flow and cell losses in ATM networks. Bulletin of Polish Academy of Sciences, Technical Sciences 43(4) (1995)

    Google Scholar 

  12. Czachórski, T., Pekergin, F.: Diffusion Models of Leaky Bucket and Partial Buffer Sharing Policy: A Transient Analysis. In: 4th IFIP Workshop on Performance Modelling and Evaluation of ATM Networks, Ilkley (1996); also in: Kouvatsos, D.: ATM Networks, Performance Modelling and Analysis. Chapman and Hall, London (1997)

    Google Scholar 

  13. Czachórski, T., Atmaca, T., Fourneau, J.-M., Kloul, L., Pekergin, F.: Switch queues – diffusion models (in polisch). Zeszyty Naukowe Politechniki /Sl/askiej, seria Informatyka (32) (1997)

    Google Scholar 

  14. Czachórski, T., Pekergin, F.: Transient diffusion analysis of cell losses and ATM multiplexer behaviour under correlated traffic. In: 5th IFIP Workshop on Performance Modelling and Evaluation of ATM Networks, Ilkley, UK, July 21-23 (1997)

    Google Scholar 

  15. Czachórski, T., Pastuszka, M., Pekergin, F.: A tool to model network transient states with the use of diffusion approximation. In: Performance Tools 1998, Palma de Mallorca, Hiszpania, wrzesie/n (1998)

    Google Scholar 

  16. Czachórski, T., Jedrus, S., Pastuszka, M., Pekergin, F.: Diffusion approximation and its numerical problems in implementation of computer network models. Archiwum Informatyki Teoretycznej i Stosowanej (1), 41–56 (1999)

    Google Scholar 

  17. Czachórski, T., Fourneau, J.-M., Kloul, L.: Diffusion Method Applied to a Handoff Queueing Scheme. Archiwum Informatyki Teoretycznej i Stosowanej (1), 41–56 (1999)

    Google Scholar 

  18. Czachórski, T., Pekergin, F.: Probabilistic Routing for Time-dependent Traffic: Analysis with the Diffusion and Fluid Approximations. In: IFIP ATM Workshop, Antwerp (1999)

    Google Scholar 

  19. Czachórski, T., Pekergin, F.: Modelling the time-dependent flows of virtual connections in ATM networks. Bulletin of Polish Academy of Sciences, Techical Sciences 48(4), 619–628 (2000)

    MATH  Google Scholar 

  20. Czachórski, T., Fourneau, J.-M., Jȩdruś, S., Pekergin, F.: Transient State Analysis in Cellular Networks: the use of Diffusion Approximation. In: QNETS 2000, Ilkley (2000)

    Google Scholar 

  21. Czachórski, T., Grochla, K., Pekergin, F.: Stability and dynamics of TCP-NCR(DCR) protocol in presence of UDP flows. In: García-Vidal, J., Cerdà-Alabern, L. (eds.) Euro-NGI 2007. LNCS, vol. 4396, pp. 241–254. Springer, Heidelberg (2007)

    Chapter  Google Scholar 

  22. Czachórski, T., Grochla, K., Pekergin, F.: Un modèle d’approximation de diffusion pour la distribution du temps d’acheminement des paquets dans les réseaux de senseurs. In: Proc. of CFIP 2008, Les Arcs, Mars 25-28 (2008), Proceedings, edition electronique, http://hal.archives-ouvertes.fr/CFIP2008

  23. Czachórski, T., Fourneau, J.-M., Nycz, T., Pekergin, F.: Diffusion approximation model of multiserver stations with losses. In: Proc. of Third International Workshop on Practical Applications of Stochastic Modelling PASM 2008, Palma de Mallorca, September 23 (2008); To appear also as an issue of Elsevier’s ENTCS (Electronic Notes in Theoretical Computer Science)

    Google Scholar 

  24. Czachórski, T., Nycz, T., Pekergin, F.: Transient states of priority queues – a diffusion approximation study. In: Proc. of The Fifth Advanced International Conference on Telecommunications AICT 2009, Venice, Mestre, Italy, May 24-28 (2009)

    Google Scholar 

  25. Czachórski, T., Grochla, K., Nycz, T., Pekergin, F.: A diffusion approximation model for wireless networks based on IEEE 802.11 standard submitted to COMCOM Special Journal Issue on Heterogeneous Networks: Traffic Engineering and Performance Evaluation of Computer Communications

    Google Scholar 

  26. Duda, A.: Diffusion Approximations for Time-Dependent Queueing Systems. IEEE J. on Selected Areas in Communications SAC-4(6) (September 1986)

    Google Scholar 

  27. Feller, W.: The parabolic differential equations and the associated semigroups of transformations. Annales Mathematicae 55, 468–519 (1952)

    Article  MathSciNet  MATH  Google Scholar 

  28. Feller, W.: Diffusion processes in one dimension. Transactions of American Mathematical Society 77, 1–31 (1954)

    Article  MathSciNet  MATH  Google Scholar 

  29. Filipiak, J., Pach, A.R.: Selection of Coefficients for a Diffusion-Equation Model of Multi-Server Queue. In: PERFORMANCE 1984, Proc. of The 10th International Symposium on Computer Performance. North Holland, Amsterdam (1984)

    Google Scholar 

  30. Gaver, D.P.: Observing stochastic processes, and approximate transform inversion. Operations Research 14(3), 444–459 (1966)

    Article  MathSciNet  Google Scholar 

  31. Gaver, D.P.: Diffusion Approximations and Models for Certain Congestion Problems. Journal of Applied Probability 5, 607–623 (1968)

    Article  MathSciNet  MATH  Google Scholar 

  32. Gelenbe, E.: On Approximate Computer Systems Models. J. ACM 22(2) (1975)

    Google Scholar 

  33. Gelenbe, E., Pujolle, G.: The Behaviour of a Single Queue in a General Queueing Network. Acta Informatica 7(fasc. 2), 123–136 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  34. Gelenbe, E.: A non-Markovian diffusion model and its application to the approximation of queueing system behaviour, IRIA Rapport de Recherche no. 158 (1976)

    Google Scholar 

  35. Gelenbe, E.: Probabilistic models of computer systems. Part II. Acta Informatica 12, 285–303 (1979)

    Article  MathSciNet  Google Scholar 

  36. Gelenbe, E., Labetoulle, J., Marie, R., Metivier, M., Pujolle, G., Stewart, W.: Réseaux de files d’attente – modélisation et traitement numérique, Editions Hommes et Techniques, Paris (1980)

    Google Scholar 

  37. Gelenbe, E., Mang, X., Feng, Y.: A diffusion cell loss estimate for ATM with multiclass bursty traffic. In: Kouvatsos, D.D. (ed.) Performance Modelling and Evaluation of ATM Networks, vol. 2. Chapman and Hall, London (1996)

    Google Scholar 

  38. Gelenbe, E., Mang, X., Önvural, R.: Diffusion based statistical call admission control in ATM. Performance Evaluation 27-28, 411–436 (1996)

    Article  MATH  Google Scholar 

  39. Halachmi, B., Franta, W.R.: A Diffusion Approximation to the Multi-Server Queue. Management Sci. 24(5), 522–529 (1978)

    Article  MATH  Google Scholar 

  40. Heffes, H., Lucantoni, D.M.: A Markov modulated characterization of packetized voice and data traffic and related statistical multiplexer parformance. IEEE J. SAC SAC-4(6), 856–867 (1986)

    Google Scholar 

  41. Heyman, D.P.: An Approximation for the Busy Period of the M/G/1 Queue Using a Diffusion Model. J. of Applied Probility 11, 159–169 (1974)

    Article  MathSciNet  MATH  Google Scholar 

  42. Iglehart, D., Whitt, W.: Multiple Channel Queues in Heavy Traffic, Part I-III. Advances in Applied Probability 2, 150–177, 355–369 (1970)

    Article  MathSciNet  MATH  Google Scholar 

  43. Iglehart, D.: Weak Convergence in Queueing Theory. Advances in Applied Probability 5, 570–594 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  44. Jouaber, B., Atmaca, T., Pastuszka, M., Czachórski, T.: Modelling the Sliding window Mechanism. In: The IEEE International Conference on Communications, ICC 1998, Atlanta, Georgia, USA, czerwiec 7-11, pp. 1749–1753 (1998)

    Google Scholar 

  45. Jouaber, B., Atmaca, T., Pastuszka, M., Czachórski, T.: A multi-barrier diffusion model to study performances of a packet-to-cell interface, art. S48.5, Session: Special applications in ATM Network Management. In: International Conference on Telecommunications ICT 1998, Porto Carras, Greece, czerwiec 22-25 (1998)

    Google Scholar 

  46. Kimura, T.: Diffusion Approximation for an M/G/m Queue. Operations Research 31(2), 304–321 (1983)

    Article  MathSciNet  MATH  Google Scholar 

  47. Kleinrock, L.: Queueing Systems. Theory, vol. I. Computer Applications, vol. II. Wiley, New York (1975, 1976)

    MATH  Google Scholar 

  48. Kobayashi, H.: Application of the diffusion approximation to queueing networks, Part 1: Equilibrium queue distributions. J. ACM 21(2), 316–328 (1974); Part 2: Nonequilibrium distributions and applications to queueing modeling. J. ACM 21(3), 459–469 (1974)

    Article  MATH  Google Scholar 

  49. Kobayashi, H.: Modeling and Analysis: An Introduction to System Performance Evaluation Methodology. Addison Wesley, Reading (1978)

    MATH  Google Scholar 

  50. Kobayashi, H., Ren, Q.: A Diffusion Approximation Analysis of an ATM Statistical Multiplexer with Multiple Types of Traffic, Part I: Equilibrium State Solutions. In: Proc. of IEEE International Conf. on Communications, ICC 1993, Geneva, Switzerland, May 23-26, pp. 1047–1053 (1993)

    Google Scholar 

  51. Kulkarni, L.A.: Transient behaviour of queueing systems with correlated traffic. Performance Evaluation 27-28, 117–146 (1996)

    Article  MATH  Google Scholar 

  52. Lee, D.-S., Li, S.-Q.: Transient analysis of multi-sever queues with Markov-modulated Poisson arrivals and overload control. Performance Evaluation 16, 49–66 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  53. Maglaris, B., Anastassiou, D., Sen, P., Karlsson, G., Rubins, J.: Performance models of statistical multiplexing in packet video communications. IEEE Trans. on Communications 36(7), 834–844 (1988)

    Article  Google Scholar 

  54. Newell, G.F.: Queues with time-dependent rates, Part I: The transition through saturation. J. Appl. Prob. 5, 436-451 (1968); Part II: The maximum queue and return to equilibrium, 579–590 (1968); Part III: A mild rush hour, 591–606 (1968)

    MATH  Google Scholar 

  55. Newell, G.F.: Applications of Queueing Theory. Chapman and Hall, London (1971)

    MATH  Google Scholar 

  56. Pastuszka, M.: Modelling transient states in computer networks with the use of diffusion approximation (in polish), Ph.D. Thesis, Silesian Technical University (Politechnika Ślaska), Gliwice (1999)

    Google Scholar 

  57. Reiser, M., Kobayashi, H.: Accuracy of the Diffusion Approximation for Some Queueing Systems. IBM J. of Res. Develop. 18, 110–124 (1974)

    Article  MATH  Google Scholar 

  58. Sharma, S., Tipper, D.: Approximate models for the Study of Nonstationary Queues and Their Applications to Communication Networks. In: Proc. of IEEE International Conf. on Communications, ICC 1993, Geneva, Switzerland, May 23-26, pp. 352–358 (1993)

    Google Scholar 

  59. Stehfest, H.: Algorithm 368: Numeric inversion of Laplace transform. Comm. of ACM 13(1), 47–49 (1970)

    Article  Google Scholar 

  60. Veillon, F.: Algorithm 486: Numerical Inversion of Laplace Transform. Comm. of ACM 17(10), 587–589 (1974); also: Veillon, F.: Quelques méthodes nouvelles pour le calcul numérique de la transformé inverse de Laplace, Th. Univ. de Grenoble (1972)

    Article  Google Scholar 

  61. Zwingler, D.: Handbook of Differential Equations, pp. 623–627. Academic Press, Boston (1989)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Theoretical and Applied Informatics, Polish Academy of Sciences, Baltycka 5, 44–100, Gliwice, Poland

    Tadeusz Czachórski

  2. LIPN, Université Paris-Nord, 93430, Villetaneuse, France

    Ferhan Pekergin

Authors
  1. Tadeusz Czachórski
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ferhan Pekergin
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. School of Computing, Informatics and Media, University of Bradford, Richmond Road, BD7 1DP, Bradford, UK

    Demetres D. Kouvatsos

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Czachórski, T., Pekergin, F. (2011). Diffusion Approximation as a Modelling Tool. In: Kouvatsos, D.D. (eds) Network Performance Engineering. Lecture Notes in Computer Science, vol 5233. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02742-0_20

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-02742-0_20

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-02741-3

  • Online ISBN: 978-3-642-02742-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation