Анализ показателей функционирования RED-подобных алгоритмов с помощью систем массового обслуживания

Данная работа посвящена анализу показателей функционирования RED (Random Early Detection) подобных алгоритмов с помощью систем массового обслуживания, а именно с помощью системы массового обслуживания с обобщённым обновлением и с помощью систем, в которых входящий поток (пуассоновский процесс, например) управляется внешним марковским процессом. Даётся определение обобщённого обновления, приводится краткий обзор. Более подробно внимание уделяется системе, в которой реализованы пороговый механизм и механизм обобщённого обновления, позволяющие регулировать количество поступивших в систему пакетов (заявок или запросов) путём вероятностного сброса в зависимости от соотношения некоторого управляющего параметра (обычно это экспо-ненциально взвешенная средняя длина очереди) с заданными пороговыми значениями. Для этой модели получены аналитические выражения стационарного распределения числа пакетов в системе, стационарные вероятности потери или дальнейшей передачи поступивших в систему пакетов, а также такие стационарные временные характеристики как распределение времени пребывания пакетов в системе, среднее время и дисперсия времени пребывания пакетов в системе. Проведён численный анализ полученных характеристик. Кроме того, в работе приведён обзор других математических моделей для исследования алгоритмов управления очередью, в частности с помощью систем массового обслуживания с MMPP (Markov Modulated Poisson Process) входящим потоком, а также его дискретным аналогом - MMBP (Markov Modulated Bernoulli Process) входящим процессом, либо с помощью жидкостных моделей.

The analysis of RED-like algorithms with the help of queuing systems

This work is devoted to the analysis of the performance of RED (Random Early Detection) like algorithms by using such methods and algorithms of queuing theory as general renovation mechanism (the definition and brief overview are given) and Markov Modulated Poisson Process theory. The attention is paid to the queueing system in which a threshold mechanism and the general renovation mechanism. The implementation of threshold and general renovation mechanisms allow to adjust the number of packets in the system by dropping (resetting) the packets from the queue depending on the ratio of a certain control parameter (usually, this is an exponentially weighted average queue length) with specified thresholds. In contrast to standard RED-like systems, a possible reset occurs not at the time of arriving of the next packets in the system, but at the time of the end of service on the device (server) and the control parameter is the current queue length. Analytical expressions for the stationary distribution of the number of packets in the system, the stationary probability of a packet to be lost (dropped from the queue) or to be transmitted are obtained. Also stationary time characteristics such as the sojourn time distribution, the average sojourn time and the variance of the sojourn time of packets in the system are obtained within the framework of the mathematical model. A numerical analysis of the characteristics obtained was carried out. In addition, the paper provides an overview of other mathematical models for the study of queue management algorithms, in particular, queuing systems with MMPP (Markov Modulated Poisson Process) incoming flow and its discrete analog - MMBP (Markov Modulated Bernoulli Process) incoming process, either fluid models.