On disadvantages of the classification of Queuing system

Abstract

The features of the existing classification of queuing systems are considered, its disadvantages are shown. The main disadvantage is the lack of information about the correlation and cross-correlation properties of flows. The disadvantage of Kendall's designations is also the lack of the possibility of classifying systems by the nature of the change in the input load.

Full Text

Введение

Существует множество моделей систем массового обслуживания (СМО). Для них были разработаны различные принципы классификации. Более пятидесяти лет назад была предложена классификация Д. Кендалла [1], основанная всего на трех символах. Для описания СМО использовалась запись следующего вида:

$A/B/n$.

Первый символ определяет характер входящего потока заявок. Распределение длительности обслуживания заявок идентифицируется вторым символом. Величина n указывает на количество обслуживающих приборов. В дальнейшем, указанная классификация была модифицирована отечественным ученым Г.П. Башариным [2], и включает следующую последовательность символов:

$A/B/S,K,N,f,z$,

где A – закон распределения промежутков между вызовами входящего потока;

B – закон распределения времени обслуживания вызовов;

S – структура коммутационной системы;

K – максимальное состояние системы;

N – число источников нагрузки;

f – приоритетность обслуживания;

z – число мест для ожидания.

Если символы K, N, z в обозначении модели отсутствуют, то они по умолчанию не ограничены. Первые два символа A и B могут характеризовать следующие законы распределения: М – показательное; D – равномерной плотности (постоянное); G – произвольное (general). Если вместо символа S изображен символ V, то коммутационная система однозвенная полнодоступная. Отсутствие символа f означает, что постановка вызовов в очередь и выборка вызовов из очереди на обслуживание осуществляется без приоритетов

Однако, указанные классификации имеют один общий недостаток. Все рассматриваемые в них случайные величины считаются взаимно независимыми и не коррелированными. Учитываются только законы распределения вероятностей.

Корреляция

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

Вместе с тем, обозначения, учитывающие корреляционные свойства потоков в рассмотренной выше системе классификации, отсутствуют и потоки заявок характеризуются исключительно законами распределения интервалов между соседними заявками. (Подразумевается, что заявки являются независимыми и корреляция в потоке отсутствует). Нами было неоднократно показано, что наличие положительной корреляции в потоке заявок приводит к возникновению больших очередей, по сравнению с потоками, имеющими аналогичное распределение вероятностей интервалов времени между соседними заявками, при отсутствии корреляционной зависимости [3].

Взаимная корреляция

Классификация Кендалла четко разделяет случайные величины, характеризующие входной поток заявок (параметр А) и случайные величины, характеризующие производительность системы массового обслуживания (параметр В), считая их взаимно независимыми. В реальных сетях с пакетной коммутацией это далеко не так. Параметр В учитывает время обработки пакета  в СМО, которое зависит не только от ее производительности, но и от размеров самого пакета, относящихся к характеристикам входного потока.

Следовательно, между указанными случайными величинами имеется весьма жесткая взаимная корреляционная связь, что противоречит ограничениям, принятым в классификации Кендалла. Наличие двух взаимно коррелированных случайных величин, одна из которых характеризует свойства входного потока, а другая – свойства СМО, существенно усложняет анализ таких систем. Стремление заменить две взаимно коррелированные случайные величины одной случайной величиной привело к созданию интервальных методов анализа процессов образования очередей в СМО [3].

В качестве такой случайной величины предлагается ввести интервальный коэффициент загрузки $m_i$, который представляет числа заявок, поступающих в систему в течение времени ${\tau }_i$ обработки одной заявки. Указанная случайная величина полностью характеризует процесс образования очередей, а ее математическое ожидание в точности равно коэффициенту загрузки СМО $\overline{m_i}=\rho$. Эта величина все чаще используется при анализе телекоммуникационного трафика [4]. Такой подход, потребует объединения первых двух позиций классификации Кендалла и введения соответствующих новых обозначений.

Заключение

В последние годы мы все чаше являемся свидетелями изменений и дополнений, вносимых специалистами в существующую классификацию Кендалла-Башарина и, по-видимому, назрела необходимость в ее модернизации.