On the Kendall’s Classification

Abstract

The features of the existing classification of queuing systems are considered, its disadvantages are shown. Only the laws of time intervals distribution between neighboring requests and time intervals for processing requests are used as the main flows characteristics. The main disadvantage is the lack of information about the correlation and cross-correlation flows properties. It is shown that flows that have the same distribution laws but different correlation properties can form queues where values differ by several orders of magnitude. Flows controlled by the Markov chain and, in particular, examples of hyperexponential flows classification are considered. It is shown that this kind of flows can have the same probability distribution laws for time intervals between neighboring requests, but significantly different queue sizes caused by the difference in the flows correlation properties. Another disadvantage of the Kendall’s classification is inability to classify systems by the nature of changes in the input load.

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

  1. Kendall D.G. Some Problems in the theory of queues // Journal of Royal Statistical Society. 1951. Vol. 13. No 2. P. 151-173.
  2. Тарасов В.Н. Исследование системы со сдвинутыми гиперэрланговским и экспоненциальным распределениями // Инфокоммуникационные технологии. 2020. Т. 18. No 1. С. 27-31. DOI: https://doi.org/10.18469/ikt.2020.18.1.04.
  3. Лихтциндер Б.Я. Интервальный метод анализа мультисервисного трафика сетей доступа // Электросвязь. 2015. No 12. С. 52-54.
  4. Лихтциндер Б.Я. Трафик мультисервисных сетей доступа (интервальный анализ и проектирование). М.: Горячая линия - Телеком, 2018. 290 с.
  5. Вишневский В.М., Дудин А.Н. Системы массового обслуживания с коррелированными входными потоками и их применение для моделирования телекоммуникационных сетей // Автоматика и телемеханика. 2017. No 8. С. 3-59.
  6. Основы моделирования сложных систем / под общ. ред. И.В. Кузьмина. Киев: Вища школа, 1981. 360 с.
  7. Степанов С.Н. Теория телетрафика. Концепции, модели, приложения. М.: Горячая линия - Телеком, 2015. 808 с.
  8. Башарин Г.П. Лекции по математической теории телетрафика. М.: Изд. РУДН, 2009. 342 с
  9. Клейнрок Л. Теория массового обслуживания / пер. с англ. под ред. В.И. Неймана. М.: Машиностроение, 1979. 344 с.
  10. Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. М.: Ком-Книга, 2005. 400 с.

Statistics

Views

Abstract: 253

PDF (Russian): 41

Dimensions

Article Metrics

Metrics Loading ...

PlumX


Copyright (c) 2020 Likhttsinder B.Y.

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

This website uses cookies

You consent to our cookies if you continue to use our website.

About Cookies