10.14489/vkit.2017.04.pp.003-007

DOI: 10.14489/vkit.2017.04.pp.003-007

Алиев Т. И.
РАСПРЕДЕЛЕНИЕ ПРИОРИТЕТОВ В СИСТЕМАХ С КОМБИНИРОВАННЫМИ ОГРАНИЧЕНИЯМИ
(c. 3-7)

Аннотация. Рассмотрена задача распределения приоритетов при наличии комбинированных ограничений на времена пребывания в системе запросов разных классов. Приведено ее решение в классе дисциплин обслуживания со смешанными приоритетами. Предложен алгоритм распределения приоритетов, обеспечивающий выполнение заданных ограничений при минимальной производительности системы.

Ключевые слова: приоритет; дисциплина обслуживания; время пребывания; комбинированные ограничения; производительность.

Aliev T. I.
PRIORITIES ASSIGNMENT IN QUEUEING SYSTEMS WITH COMPOUND CONSTRAINTS
(pp. 3-7)

Abstract. In data processing systems and in telecommunications the quality of service requirements may be specified as inequality constraints on either average sojourn time or the probability that sojourn time exceeds a predefined value. In general, a set of compound constraints may be used: some classes have constraints on average values, other classes have probabilistic constraints. To satisfy given constraints one has to correctly assign requests priorities by means of a mixed-priorities matrix which allows to configure mutual priorities for requests of the following types: preemptive, non-preemptive or FCFS (First-Come, First-Served). Such systems are modeled using a queuing system with a single server and an unlimited queue size in which several kinds of requests are processed by the server at a given rate. The optimization problem is formulated as follows: find a mixed priorities service discipline for which sojourn time constraints are satisfied provided that the server performance is minimized. The proposed solution is based on analytical models which use the first and the second moments of the sojourn time of requests in the system, and is carried out in two phases. At the first phase the problem is reduced to the problem of priorities assignment in systems with constraints on average sojourn time. To do it, probabilistic time constraints are converted to average time constraints using the assumption that sojourn time is exponentially distributed. At the second phase, the service discipline (found during the first phase) is checked to satisfy probabilistic constraints in order to account for possibly non-exponentially distributed sojourn time. If the coefficient of variation of requests sojourn time is greater than one, the first phase results are refined using two-moments distribution approximation of sojourn time. The two-phase hyper-exponential distribution is used for the approximation purposes. The proposed algorithm of priorities assignment ensures the desired quality of service for the system provided that server performance is minimized.

Keywords: Priority; Service discipline; Sojourn time; Compound constraints; Device performance.

+ - Информация об авторах (About the Authors) Click to collapse

Рус

Т. И. Алиев (Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики, Санкт-Петербург, Россия) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

Eng

T. I. Aliev (Saint-Petersburg National Research University of Information Technologies, Mechanics and Optics, Saint-Petersburg, Russia) E-mail: Этот e-mail адрес защищен от спам-ботов, для его просмотра у Вас должен быть включен Javascript

+ - Библиографический список (References) Click to collapse

Рус

1. Липаев В. В., Колин К. К., Серебровский Л. А. Математическое обеспечение управляющих ЦВМ. М.: Сов. радио, 1972. 528 с.
2. Алиев Т. И. Проектирование систем с приоритетами // Изв. вузов. Приборостроение. 2014. Т. 57, № 4. С. 30 – 35.
3. Bogatyrev V. A., Bogatyrev A. V. Functional Reliability of a Real-Time Redundant Computational Process in Cluster Architecture Systems // Automatic Control and Computer Sciences. 2015. V. 49, № 1. P. 46 – 56.
4. Aliev T. I., Nikulsky I. Y., Pyattaev V. O. Modeling of Packet Switching Network with Relative Prioritization for Different Traffic Types // The 10th Intern. Conf. on Advanced Communication Technology (ICACT – 2008). Phoenix, Park, Korea. 17 – 20 Feb. 2008. Phoenix. 2008. P. 2174 – 2176.
5. Алиев Т. И., Муравьева Л. А. Система с динамически изменяющимися смешанными приоритетами и ненадежным прибором // Автоматика и телемеханика. 1988. № 7. С. 99 – 107.
6. Богатырев В. А., Голубев И. Ю. Оптимальная диспетчеризация в распределенных вычислительных системах с объединением узлов в кластеры // Вестник компьютерных и информационных технологий. 2013. № 8. С. 36 – 40.
7. Вишневский В. М. Теоретические основы проектирования компьютерных сетей. М.: Техносфера, 2003. 512 с.
8. Алиев Т. И., Муравьева-Витковская Л. А. Приоритетные стратегии управления трафиком в мультисервисных компьютерных сетях // Изв. вузов. Приборостроение. 2011. Т. 54, № 6. С. 44 – 48.
9. Алиев Т. И., Махаревс Э. Дисциплины обслуживания на основе матрицы приоритетов // Научно-технический вестник информационных технологий, механики и оптики. 2014. № 6. С. 91 – 97.
10. Алиев Т. И. Аппроксимация вероятностных распределений в моделях массового обслуживания // Научно-технический вестник информационных технологий, механики и оптики. 2013. № 2(84). С. 88 – 93.

Eng

1. Lipaev V. V., Kolin K. K., Serebrovskii L. A. (1972). Mathematical support of computer controllers. Moscow: Sovetskoe radio. [in Russian language]
2. Aliev T. I. (2014). Designing the systems with priorities. Izvestiia vuzov. Priborostroenie, 57(4), pp. 30 - 35. [in Russian language]
3. Bogatyrev V. A., Bogatyrev A. V. (2015). Functional reliability of a real-time redundant computational process in cluster architecture systems. Automatic Control and Computer Sciences, 49(1), pp. 46-56. doi: 10.3103/S0146411615010022
4. Aliev T. I., Nikulsky I. Y., Pyattaev V. O. (2008). Modeling of packet switching network with relative prioritization for different traffic types. The 10th Intern. Conf. on Advanced Communication Technology (ICACT – 2008). Phoenix, Park, Korea. 17 – 20 Feb. Phoenix. 2008, pp. 2174-2176. doi: 10.1109/icact.2008.4494220
5. Aliev T. I., Murav'eva L. A. (1988). A system with dynamically changing mixed priorities and an unreliable device. Avtomatika i telemekhanika, (7), pp. 99-107. [in Russian language]
6. Bogatyrev V. A., Golubev I. Iu. (2013). Optimal dispatch in distributed computing systems with union of nodes in clusters. Vestnik komp'iuternykh i informatsionnykh tekhnologii, (8), pp. 36-40. [in Russian language]
7. Vishnevskii V. M. (2003). The theoretical foundations of computer networks design. Moscow: Tekhnosfera. [in Russian language]
8. Aliev T. I., Murav'eva-Vitkovskaia L. A. (2011). Priority strategies for traffic management in multiservice computer networks. Izvestiia vuzov. Priborostroenie, 54(6), pp. 44-48. [in Russian language]
9. Aliev T. I., Makharevs E. (2014). Service disciplines based on the priority matrix. Nauchno-tekhnicheskii vestnik informatsionnykh tekhnologii, mekhaniki i optiki, (6), pp. 91-97. [in Russian language]
10. Aliev T. I. (2013). Approximation of probability distributions in queuing models. Nauchno-tekhnicheskii vestnik informatsionnykh tekhnologii, mekhaniki i optiki, 84(2), pp. 88-93. [in Russian language]

+ - Заказать электронную версию статьи (Purchase digital version of a single article) Click to collapse

Рус

Статью можно приобрести в электронном виде (PDF формат).

Стоимость статьи 350 руб. (в том числе НДС 18%). После оформления заказа, в течение нескольких дней, на указанный вами e-mail придут счет и квитанция для оплаты в банке.

После поступления денег на счет издательства, вам будет выслан электронный вариант статьи.

Для заказа скопируйте doi статьи:

10.14489/vkit.2017.04.pp.003-007

и заполните ФОРМУ

Отправляя форму вы даете согласие на обработку персональных данных.

Eng

This article is available in electronic format (PDF).

The cost of a single article is 350 rubles. (including VAT 18%). After you place an order within a few days, you will receive following documents to your specified e-mail: account on payment and receipt to pay in the bank.

After depositing your payment on our bank account we send you file of the article by e-mail.

To order articles please copy the article doi:

10.14489/vkit.2017.04.pp.003-007

and fill out the FORM