Priority Preemptive Queues - Transient State Models

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

Warianty tytułu

PL

Wydajność mechanizmu protekcji segmentowej w sieci GMPLS

• Języki publikacji: EN

Abstrakty

EN

The article presents a diffusion approximation model applied to investigate the behaviour of priority queues. 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 vary 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 the network of queues. Here, we apply the diffusion approximation formalism to study transient and steady-state behaviour of G/G/1 and G/G/1/N priority preemptive models. The models can be easily converted to nonpreemptive queueing discipline. Also the introduction of self-similar traffic is possible. The models may be useful in performance evaluation of mechanisms to differentiate the quality of service e.g. in WiMAX, metro networks, etc.

PL

Artykuł przedstawia kolejkowy model systemu z obsługą priorytetową. Wykorzystano w nim metodę aproksymacji dyfuzyjnej, która pozwala na przyjęcie bardziej ogólnych założeń niż jest to możliwe w przypadku dokładnych analitycznych modeli teorii kolejek. Rozwiązując równania dyfuzji aproksymujące liczbę klientów w kolejce każdego poziomu priorytetowego, możemy w naturalny sposób opisywać stany nieustalone kolejki, co jest istotne przy modelowaniu pracy sieci komputerowych, w których natężenie transmisji ulega ciągłym zmianom. Można też wprowadzić do modelu ogólne rozkłady odstępów czasu między nadejściami klientów oraz ogólne rozkładu czasów obsługi. Wykorzystanie aproksymacji dyfuzyjnej umożliwia też uwzględnienie w modelu samopodobnego (o długoterminowej autokorelacji) natężenia strumienia wejściowego. Model pojedynczego stanowiska jest łatwo rozszerzalny na sieć podobnych stanowisk. Przedstawione rezultaty dotyczą stanowisk typu G/G/1 i G/G/1/N z regulaminem priorytetowym przerywalnym (bezwzględnym), tzn. obsługa jest przerywana w momencie nadejścia klienta o wyższym priorytecie i kontynuowana w chwili, gdy w systemie nie ma już klientów wyższego priorytetu. Model może być rozszerzony na przypadek systemu z priorytetami nieprzerywalnymi. Wyniki mogą być przydatne w analizie różnicujących jakość usług mechanizmów szeregowania pakietów, np. w ruterach protokołu IP, w sieciach typu WiMAX, w elementach dostępowych lektroniczno-optycznych sieci metropolitalnych.

Słowa kluczowe

EN

diffusion approximation; priority models; performance evaluation

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

Twórcy

autor

Czachórski T.

autor

Nycz T.

autor

Pekergin F.

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

Bibliografia

• [1] T. Atmaca, T. Czachórski, F. Pekergin, “A Diusion Model of the Dynamic Effects of Closed-Loop Feedback Control Mechanisms in ATM Networks”, 3rd IFIP Workshop on Performance Modelling and Evaluation of ATM Networks, Ilkley, UK, 4-7th July 1995.
• [2] R.P. Cox, H.D. Miller, “The Theory of Stochastic Processes”, Chapman and Hall, London (1965).
• [3] 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.
• [4] T. Czachórski, F. Pekergin, “Transient diusion analysis of cell losses and ATM multiplexer behaviour under correlated trac”, 5th IFIPWorkshop on Performance Modelling and Evaluation of ATM Networks, Ilkley, UK, 21-23 july 1997.
• [5] T. Czachórski, K. Grochla, F. Pekergin, “’Stability and Dynamics of TCPNCR(DCR) Protocol”, LNCS no. 4396, Wireless Systems and Mobility in Next Generation Internet, Springer-Verlag 2007.
• [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] D. Iglehart, “Weak Convergence in Queueing Theory”, Advances in Applied Probability, vol. 5, pp. 570-594, 1973.
• [9] K.N. Jaiswal, “Priority Queues”, Academic Press, New York 1968.
• [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] S.S. Lavenberg, “’Computer Performance Modeling Handbook”, Academic Press, New York 1983.
• [13] G.F. Newell, “Applications of Queueing Theory”, Chapman and Hall, London 1971.
• [14] H. Stehfest, “Algorithm 368: Numeric inversion of Laplace transform”, Comm. of ACM, vol. 13, no. 1, p. 47-49 (1970).