QUEUEING DISCIPLINES BASED ON PRIORITY MATRIX
Read the full article
Article in Russian
The paper deals with queueing disciplines for demands of general type in queueing systems with multivendor load. A priority matrix is proposed to be used for the purpose of mathematical description of such disciplines, which represents the priority type (preemptive priority, not preemptive priority or no priority) between any two demands classes. Having an intuitive and simple way of priority assignment, such description gives mathematical dependencies of system operation characteristics on its parameters. Requirements for priority matrix construction are formulated and the notion of canonical priority matrix is given. It is shown that not every matrix, constructed in accordance with such requirements, is correct. The notion of incorrect priority matrix is illustrated by an example, and it is shown that such matrixes do not ensure any unambiguousness and determinacy in design of algorithm, which realizes corresponding queueing discipline. Rules governing construction of correct matrixes are given for canonical priority matrixes. Residence time for demands of different classes in system, which is the sum of waiting time and service time, is considered as one of the most important characteristics. By introducing extra event method Laplace transforms for these characteristics are obtained, and mathematical dependencies are derived on their basis for calculation of two first moments for corresponding characteristics of demands queueing.
Keywords: queueing system, queueing discipline, mixed priorities, priority matrix, canonical priority matrix, correct and incorrect priority matrix
1. Olifer V.G., Olifer N.A. Komp'yuternye Seti. Printsipy, Tekhnologii, Protokoly [Computer Networks. Principles, Technologies, Protocols]. 3rd ed. St. Petersburg, Piter Publ., 2006, 944 p.
2. Aliev T.I., Nikulsky I.Y., Pyattaev V.O. Modeling of packet switching network with relative prioritization for different traffic types. Proc. 10th International Conference on Advanced Communication Technology, ICACT-2008. Phoenix Park, South Korea, 2008, art. 4494220, pp. 2174–2176. doi: 10.1109/ICACT.2008.4494220
3. Bogatyrev V.A. An interval signal method of dynamic interrupt handling with load balancing. Automatic Control and Computer Sciences, 2000, vol. 34, no. 6, pp. 51–57.
4. Bogatyrev V.A. On interconnection control in redundancy of local network buses with limited availability. Engineering Simulation, 1999, vol. 16, no. 4, pp. 463–469.
5. Vishnevskii V.M., Semenova O.V. Sistemy Pollinga: Teoriya i Primenenie v Shirokopolosnykh Besprovodnykh Setyakh [Polling System: Theory and Applications in Broadband Wireless Networks]. Moscow, Tekhnosfera Publ., 2007, 312 p.
6. Muravyeva-Vitkovskaya L.A. Obespechenie kachestva obsluzhivaniya v mul'tiservisnykh komp'yuternykh setyakh za schet prioritetnogo upravleniya [Priority-based mechanisms of service quality provision in multiservice computer networks]. Izv. vuzov. Priborostroenie, 2012, vol. 55, no. 10, pp. 64–68.
7. Aliev T.I. Proektirovanie sistem s prioritetami [Design of systems with priorities].Izv. vuzov. Priborostroenie, 2014, vol. 57, no. 4, pp. 30–35.
8. Aliev T.I., Muravyeva L.A. System with dynamically varying mixed priorities and an unreliable server. Automation and Remote Control, 1988, vol. 49, no. 7, pp. 897–903.
9. Alfa A.S. Matrix-geometric solution of discrete time MAP/PH/1 priority queue. Naval Research Logistics, 1998, vol. 45, no. 1, pp. 23–50.
10.Osnovy Teorii Vychislitel'nykh Sistem[Foundations of the Theory of Computing Systems]. Ed. S.A. Maiorov. Moscow, Vysshaya Shkola Publ., 1978, 408 p.
11.Gol'dshtein B.S. Ob optimal'nom prioritetnom obsluzhivanii v programmnom obespechenii EATS [On optimal priority service software EATS]. In Sistemy Upravleniya Setyami [Network Management Systems]. Moscow, Nauka Publ., 1980, pp. 73–78.
12.Zhao J.-A., Li B., Cao X.-R., Ahmad I. A matrix-analytic solution for the DBMAP/PH/1 priority queue. Queueing Systems, 2006, vol. 53, no. 3, pp. 127–145.
13.Klimov G.P. Stokhasticheskie Sistemy Obsluzhivaniya [Stochastic Service System]. Moscow, Nauka Publ., 1966, 242 p.
14.Aliev T.I. Approksimatsiya veroyatnostnykh raspredelenii v modelyakh massovogo obsluzhivaniya [Approximation of probability distributions in queueing models]. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2013, no. 2 (84), pp. 88–93.
15.Kleinrock L. Queueing Systems. NY, Wiley, 1975, 448 p.