On the Kendall’s Classification

Full Text

Существует множество моделей систем массового обслуживания (СМО) [9; 10]. Для них были разработаны различные принципы классификации. Более пятидесяти лет назад была предложена классификация Д. Кендалла [1], основанная всего на трех символах. Для описания СМО использовалась запись следующего вида: / /. ABn Первый символ определяет характер входящего потока заявок. Распределение длительности обслуживания заявок идентифицируется вторым символом. Величина n указывает на количество обслуживающих приборов. В дальнейшем указанная классификация была модифицирована отечественным ученым Г.П. Башариным и включает следующую последовательность символов: / /, ABS K, N, f, z, где A - закон распределения промежутков между вызовами входящего потока; B - закон распределения времени обслуживания вызовов; S - структура коммутационной системы; K - максимальное состояние системы; N - число источников нагрузки; f - приоритетность обслуживания; z - число мест для ожидания. Если символы K, N, z в обозначении модели отсутствуют, то они по умолчанию не ограничены. Первые два символа A и B могут характеризовать следующие законы распределения: М - показательное; D - равномерной плотности (постоянное); G - произвольное (general). Если вместо символа S изображен символ V, то коммутационная система однозвенная полнодоступная. Отсутствие символа f означает, что постановка вызовов в очередь и выборка вызовов из очереди на обслуживание осуществляются без приоритетов [2]. В связи с использованием иных законов распределений на позициях первых двух символов были введены другие обозначения законов распределений: 2 H - гиперэкспоненциальное распределение второго порядка (заменив цифру 2 буквой k, можно говорить об этом же законе, но k-го порядка); WG - распределение Вейбулла - Гнеденко; U - равномерное распределение на некотором интервале [a, b]; k E - распределение Эрланга k-го порядка. Размещение этого символа в позиции А указывает на то, что распределение длительности интервалов между моментами поступления заявок в СМО подчиняется закону Эрланга k-го порядка. Если символ k E находится в позиции В, то длительность обслуживания заявок распределена по этому же закону. Для неординарных потоков общего вида часто применяется обозначение () , k G где h - число заявок в одной группе. Необходимость учета видоизменения уже имеющихся законов распределений привела к появлению дополнительных обозначений. Так, например, в работе [3] для систем со сдвинутыми распределениями вводятся обозначения 2 HE- и . M- Подобных дополнений в классификацию может быть введено великое множество. Однако указанные классификации имеют один общий недостаток. Все рассматриваемые в них случайные величины считаются взаимно независимыми и некоррелированными. Учитываются только законы распределения вероятностей. Учет корреляции Исследования телекоммуникационных сетей с коммутацией пакетов показали, что потоки пакетов в таких сетях существенно отличаются от пуассоновских и носят явно выраженный пачечный характер. Пачечность потоков свидетельствует о значительной корреляционной зависимости между поступающими пакетами, и пренебрегать корреляционными свойствами такого трафика уже нельзя. Вместе с тем обозначения, учитывающие корреляционные свойства потоков, в рассмотренной выше системе классификации отсутствуют, и потоки заявок характеризуются исключительно законами распределения интервалов между соседними заявками. Подразумевается, что заявки являются независимыми и корреляция в потоке отсутствует. Нами было неоднократно показано, что наличие положительной корреляции в потоке заявок приводит к возникновению больших очередей по сравнению с потоками, имеющими аналогичное распределение вероятностей интервалов времени между соседними заявками при отсутствии корреляционной зависимости [4; 5]. Так, в частности, если в пуассоновском потоке, который по определению имеет экспоненциальное распределение интервалов между соседними заявками, путем перестановки произвести группирование коротких интервалов, распределение вероятностей не изменится и останется экспоненциальным, но среднее значение очереди при их обработке в СМО может возрасти в тысячу раз. По существующей классификации поток, имеющий экспоненциальное распределение интервалов между соседними заявками, обозначается буквой M (при этом подразумевается, что заявки в потоке независимы, и, следовательно, он является пуассоновским). Не оговаривая наличия в потоке корреляционной зависимости и отражая только распределение вероятностей, невозможно дать характеристику потока с точки зрения его обработки в СМО. Наличие корреляционной зависимости в потоках заявок иногда в существующей классификации учитывается косвенно. Например, символ D, как уже было отмечено выше, характеризует высоко коррелированный равномерный поток, а символ k E - распределение Эрланга k-го порядка. Такой поток получается путем удаления из пуассоновского потока подряд 1 () k - заявки, что вносит в него отрицательную корреляционную зависимость. Эта зависимость приводит к уменьшению вариабельности потока по сравнению с пуассоновским. Реальный пакетный трафик в телекоммуникационных сетях, наоборот, имеет высокую пачечность и, следовательно, высокий коэффициент вариации. Поэтому распределение Эрланга вряд ли возможно использовать в качестве аналитических моделей трафика телекоммуникационных сетей с пакетной коммутацией. Потоки, управляемые цепью Маркова Стремление повысить вариабельность потоков и учесть наличие корреляционных свойств привело к созданию целого ряда моделей потоков, управляемых цепью Маркова, или МС-потоков (Markov Chain) [6]. Вначале это были потоки, в которых интервалы поступления стационарных пуассоновских потоков чередовались с интервалами, длины которых распределены по экспоненциальному закону, где поток полностью отсутствовал (IPP - Interrupted Poisson Proсess). Развитием указанного типа моделей потоков стали SPP (Switched Poisson Process) - модели потоков, в которых интервалы стационарного пуассоновского потока одной интенсивности чередовались с интервалами такого потока другой интенсивности. Допустив возможность появления нескольких потоков с различными интенсивностями, пришли к MMPP (Markov Modulated Poisson Process)-потокам и к их развитию - BMAP (Batch Markovian Arrival Process) - групповым потокам. Наличие большого числа потоков различного вида, несомненно, затрудняет их символьное обозначение в классификации Кендалла, тем более что в различных источниках некоторые одинаковые потоки имеют различные названия. Так, например, некоторые различные SPP-потоки носят название «Потоки с гиперэкспоненциальными распределениями вероятностей» [7]. Гиперэкспоненциальные распределения Рассмотрим формирование и обозначения потоков, в которых интервалы времени между соседними заявками характеризуются гиперэкспоненциальными распределениями [7]. Гиперэкспоненциальное распределение второго порядка в классификации принято обозначать символом 2 . H Временные интервалы ϑ между соседними заявками такого потока описываются экспоненциальными распределениями с параметрами 1 l и 2 . l Функция такого распределения вероятностей имеет вид 12 11 () ( ) . F pe p e -l ϑ -l ϑ ϑ= - - - (1) Гиперэкспоненциальный поток второго порядка имеет две чередующиеся во времени фазы, причем в течение каждой из фаз в потоке может находиться не более одной заявки. Предполагается, что выбор очередной фазы производится независимо с вероятностями p и 1 () p - соответственно. Алгоритм генерации гиперэкспоненциального потока может быть следующим. Вначале независимо, с соответствующей вероятностью, выбираем номер очередной фазы, а затем, согласно экспоненциальному распределению выбранной фазы, определяется длительность временного интервала между соседними заявками. Полученный таким образом поток заявок будет полностью удовлетворять распределению интервалов (1). Теперь введем дополнительную корреляционную зависимость, заключающуюся в том, что в течение каждой фазы будет последовательно генерироваться не по одной, а по n заявок с интервалами, соответствующими экспоненциальному распределению данной фазы. Длительность прохождения каждой фазы возрастет в n раз, но вероятности наступления фаз останутся неизменными. Закон распределения интервалов между соседними заявками также не изменится. Таким образом, сгенерированный новый поток полностью соответствует распределению (1) Однако размеры очередей при обработке такого потока в СМО будут существенно различны. Следовательно, одного распределения вероятностей для полной характеристики потока 1 l недостаточно. Учет числа заявок n, генерируемых подряд может осуществляться введением символа 2 () . n H На рисунке показаны зависимости средних размеров очередей для двух потоков, полностью удовлетворяющих распределению вероятностей (1). Оба потока имеют одинаковые значения 1 1 l= и 2 10, l= однако для первого потока число заявок в течение одной фазы выбрано 1 n = (нижняя кривая), а для второго потока число заявок в течение одной фазы выбрано 100 n = (верхняя кривая). Оба потока имеют одинаковую функцию распределения вероятностей интервалов времени между соседними заявками: 1 10 1 05 1 05 ()(, )(,) . Fe e -ϑ - ϑ ϑ= - - - Разница в значениях очередей впечатляет и убеждает в необходимости отражения в классификации Кендалла корреляционных свойств входных потоков. Рисунок. Зависимости средних размеров очередей для двух потоков Взаимная корреляция Классификация Кендалла четко разделяет случайные величины, характеризующие входной поток заявок (параметр А), и случайные величины, характеризующие производительность системы массового обслуживания (параметр В), считая их взаимно независимыми. В реальных сетях с пакетной коммутацией это далеко не так. Параметр В учитывает время обработки пакета t в СМО, которое зависит не только от ее производительности, но и от размеров самого пакета, от- носящихся к характеристикам входного потока. Следовательно, между указанными случайными величинами имеется весьма жесткая взаимная корреляционная связь, что противоречит ограничениям, принятым в классификации Кендалла. Наличие двух взаимно коррелированных случайных величин, одна из которых характеризует свойства входного потока, а другая - свойства СМО, существенно усложняет анализ таких систем. Стремление заменить две взаимно коррелированные случайные величины одной случайной величиной привело к созданию интервальных методов анализа процессов образования очередей в СМО [5]. В качестве такой случайной величины предлагается ввести интервальный коэффициент загрузки mi, который представляет числа заявок, поступающих в систему в течение времени i t обработки одной заявки. Указанная случайная величина полностью характеризует процесс образования очередей, а ее математическое ожидание в точности равно коэффициенту загрузки СМО i m = r [4]. Эта величина все чаще используется при анализе телекоммуникационного трафика [8]. Такой подход потребует объединения первых двух позиций классификации Кендалла и введения соответствующих новых обозначений. Заключение В последние годы мы все чаще являемся свидетелями изменений и дополнений, вносимых специалистами в существующую классификацию Кендалла - Башарина, и, по-видимому, назрела необходимость в ее модернизации.

About the authors

B. Ya Likhttsinder

Povolzhskiy State University of Telecommunications and Informatics

Email: lixt@psuti.ru
Samara, Russian Federation

References

Supplementary files