Diffusion model of parallel servers - transient state analysis

• Autorzy: Czachórski T. , Fourneau J.-M. , Nycz T. , Pekergin F.

Warianty tytułu

PL

Analiza stanów nieustalonych w pracy równoległych stanowisk obsługi - wykorzystanie aproksymacji dyfuzyjnej

• Języki publikacji: EN

Abstrakty

EN

The article presents a diffusion approximation model of a G/GN/N station – N parallel servers without queueing. Diffusion approximation allows us to include in queueing models fairly general assumptions. First of all it gives us a tool to consider in a natural way transient states of queues, which is very rare in classical queueing models. Then we may consider input streams with general interarrival time distributions and servers with general service time distributions. Single server models may be easily incorporated into a network of queues. Here, we apply the diffusion approximation formalism to study transient behaviour of G/G/N/N station and use it to construct a model of a typical call centre and to study the sliding window mechanism, a popular Call Admission Control (CAC) algorithm.

PL

Artykuł przedstawia model stacji obsługi typu G/G/N/N – a więc stacji zawierającej N równoległych kanałów obsługi, bez możliwości tworzenia kolejki, ze strumieniem wejściowym o dowolnym rozkładzie odstępów czasu pomiędzy nadejściem kolejnych klientów i z dowolnym rozkładem czasów obsługi. Zastosowanie metody aproksymacji dyfuzyjnej pozwala na opis zarówno stanów ustalonych, jak i nieustalonych (co jest niewykonalne przy zastosowaniu dokładnych klasycznych metod teorii kolejek) pracy takiego stanowiska. Dokładność metody jest oceniona przy użyciu dwu przykładów numerycznych, gdzie wyniki aproksymacji są porównane z wynikami symulacji. Symulacja stanów nieustalonych oznacza powtórzenie wiele tysięcy razy symulowanego przebiegu i uśrednienie wszystkich uzyskanych trajektorii. Opracowany model pojedynczego stanowiska może być łatwo rozwinięty do sieci o dowolnej topologii zawierającej stanowiska stanowiska G/G/N/N oraz G/G/1/N. Przykłady numeryczne pokazują też możliwości zastosowania modeli: jeden z przykładów odnosi się do modelowania centrów obsługi telefonicznej, a drugi przedstawia model działania mechanizmu przesuwnego okna – znanego algorytmu kontroli liczby pakietów wchodzących do sieci.

Słowa kluczowe

EN

diffusion approximation; priority queues

• Wydawca: Instytut Informatyki Teoretycznej i Stosowanej Polskiej Akademii Nauk
• Czasopismo: Theoretical and Applied Informatics
• Rocznik: 2008
• Tom: Vol. 20, No. 3
• Strony: 179--198
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Czachórski T.

autor

Fourneau J.-M.

autor

Nycz T.

autor

Pekergin F.

• IITiS PAN, 44-100 Gliwice, ul. Bałtycka 5

Bibliografia

• [1] R. P. Cox, H. D. Miller, The Theory of Stochastic Processes, Chapman and Hall, London 1965.
• [2] T. Czachórski, A method to solve diusion equation with instantaneous return processes acting as boundary conditions, Bulletin of Polish Academy of Sciences, Technical Sciences vol. 41 (1993), no. 4.
• [3] T. Czachórski, F. Pekergin, A diusion approximation model of an electronicoptical node Proc. of 2nd European Performance and Engineering Workshop, EPEW 05, Versailles, 1-3 September 2005, LNCS no. 3670, pp. 187-199, Springer Verlag 2005.
• [4] T. Czachórski, K. Grochla, F. Pekergin, Diusion approximation model for the distribution of packet travel time at sensor networks LNCS no. 5122, 2008. (Title:Wireless Systems and Mobility in Next Generation Internet)
• [5] N. Gans, G. Koole, A. Mandelbaum A, Telephone Call Centers Tutorial, Review, and Research Prospects, Manufacturing & Service Operations Management, Vol. 5, pp. 79-141, 2003.
• [6] E. Gelenbe, On Approximate Computer Systems Models, J. ACM, vol. 22, no. 2, (1975).
• [7] 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.
• [8] L. V. Green, P. J. Kolesar, W. Whitt, Coping with Time-Varying Demand when Setting Stang Requirements for a Service System. Production and Operations Management (POMS), vol. 16, No. 1, pp. 13-39, 2007,
• [9] D. Iglehart, Weak Convergence in Queueing Theory, Advances in Applied Probability, vol. 5, pp. 570-594, 1973.
• [10] L. Kleinrock, Queueing Systems, vol. I: Theory, vol. II: Computer Applications, Wiley, New York 1975, 1976.
• [11] H. Kobayashi, Modeling and Analysis: An Introduction to System Performance Evaluation Methodology, Addison Wesley, Reading, Massachusetts 1978.
• [12] G. F. Newell, Applications of Queueing Theory, Chapman and Hall, London 1971.
• [13] H. Stehfest, Algorithm 368: Numeric inversion of Laplace transform, Comm. of ACM, vol. 13, no. 1, p. 47-49 (1970).
• [14] W. Whitt, A Diusion approximation for the G/G/n/m Queue, Operations Research, Vol. 52, no. 6, pp. 922-941, 2004.