QUEUE SIZE DETECTION BASED ON COVARIANCE FUNCTION OF DEMAND NUMBER

Full Text

Введение Анализу потоков трафика современных мультисервисных сетей связи посвящено большое число публикаций. Недавно, вышла в свет фундаментальная работа [1], посвященная указанной тематике. Однако, вопросы анализа причин возникновения перегрузок и очередей в системах массового обслуживания, моделирующих обработку мультисервисного трафика появляются снова и снова. Одним из таких вопросов является установление влияния корреляционных связей, между заявками потока, на размеры очередей в системах обслуживания [4; 6; 10]. Разработанные автором интервальные методы анализа очередей [2-3; 8] позволили произвести обобщение известной формулы Хинчина-Поллячека [7; 9], пригодной только для анализа очередей пуассоновских потоков и, на основе аппроксимации, определить коэффициенты, характеризующие потоки заявок общего вида. В статье анализируется стационарный, ординарный рекуррентный поток заявок, удовлетворяющий условиям эргодичности. Уравнение баланса Рассмотрим интервал времени (начиная с момента ), на котором сохраняется стационарность потока и происходит достаточно большое число событий. Параметр средней интенсивности на указанном интервале времени определяется как Разделим интервал на последовательно расположенных промежутков времени В течение каждого промежутка времени в системе полностью обрабатывается одна заявка. Число заявок, поступившее в течение -го промежутка времени , обозначим через , а число обработанных заявок за это время - равно 1, если заявки имелись в системе, и равно 0, если заявки отсутствовали. Обозначим эту переменную через . Процесс образования очередей носит циклический характер. В течение пассивной части циклов очередь отсутствует и процессор, обрабатывающий заявки, простаивает. Допустим, что в нулевой момент времени очередь отсутствовала. Тогда, общее число заявок, находящееся в очереди к концу -го промежутка времени (1) где Величина (2) представляет собой приращение очереди на -oм промежутке времени. Формирование очередей На любом промежутке времени имеется очередь, размером , поступившая с предыдущего промежутка времени и одновременно поступает заявок, которые становятся в очередь. Суммарная очередь на промежутке времени определяется соотношением (1), а приращение очереди на указанном промежутке определяется (2). Однако, появление дополнительных заявок на создаст дополнительные приращения очереди и на последующих промежутках времени. Эти заявки поступят на обработку лишь после того, как обработаются все ранее поступивших заявок, находящихся в очереди. Обработка всех ранее поступивших заявок будет происходить в течение промежутков времени причем, на каждом последующем промежутке времени будет обрабатываться по одной заявке, и при отсутствии поступления новых заявок, очередь будет уменьшаться каждый раз на единицу. Суммарное число заявок, которое будут находиться в очередях, в результате прихода заявок от очереди на промежуток определится суммой арифметической прогрессии - это площадь элементов треугольника, со сторонами : В результате прихода заявок на промежутке образуется очередь . Суммарное число заявок, которое будут находиться в очередях, после образования этой очереди, также определится суммой арифметической прогрессии - это площадь элементов треугольника, со сторонами : Указанные площади треугольников представляют объемы недовыполненных работ по обслуживанию заявок. Приращение недовыполненной работы, возникающее на промежутках времени определяется разностью: На рис. 1 в качестве примера показаны размеры очередей. На промежутке очередь составляла 4 заявки, а на промежутке после прихода заявок, и ухода на обработку одной заявки, очередь заявок. Площадь треугольника заявок, площадь треугольника заявок. Приращение площади на указанном промежутке времени составляет заявок. Рис. 1. Пример образования очередей Если коэффициент загрузки меньше единицы, то в системе наблюдается устойчивый процесс образования очередей, заключающийся в том, что на интервале анализа все заявки успевают обработаться, и сумма всех приращений равна нулю, т.е. случайная величина является центрированной и ее математическое ожидание . Не трудно показать, что ; После подстановки и усреднения окончательно, имеем (3) Это соотношение, обобщающее известную формулу Хинчина-Поллячека [7], было ранее получено автором непосредственно через уравнение баланса, однако приведенный здесь вывод лучше отражает физическую сущность процесса образования очередей в системах массового обслуживания. Проанализируем на всех промежутках времени интервала анализа Очевидно, что, в соответствии с (1) имеет место , где значение Следовательно Значение ковариации Нетрудно показать, что первая сумма представляет собой где - дисперсия чисел заявок на промежутках Поменяв порядок суммирования во втором слагаемом, убеждаемся в том, что оно представляет собой удвоенную сумму ковариационных коэффициентов чисел заявок на указанных промежутках времени: Здесь - ковариационный коэффициент чисел заявок при сдвиге на интервалов Учитывая, что а также, что с увеличением сдвига корреляционные связи ослабевают и проявляются только в пределах интервала корреляции [2], суммирование может производиться не по всему интервалу а лишь в пределах интервала корреляции: где - ковариационный коэффициент чисел заявок, при сдвиге на интервалов Подставляя в (3), получим окончательно (4) Аналогичное соотношение, полученное автором другим способом, приведено в [5]. Функция ковариации Рассмотренные в настоящей работе выводы позволяют лучше понять физический смысл выражения, образующего числитель обобщенной формулы Хинчина-Поллячека. Учитывая, что дисперсия - ковариационный коэффициент при нулевом сдвиге можно утверждать, что числитель представляет сумму ковариационных коэффициентов, взятую в пределах интервала корреляции чисел заявок, и характеризует переменную составляющую мощности потока. Рис. 2. Функция ковариации числа заявок для реального потока видеотрафика В качестве примера на рис. 2 показана функция ковариации числа заявок для реального потока видеотрафика при коэффициенте загрузки На приведенном графике видно значение дисперсии На рис. 3 показан график суммарной (интегральной) удвоенной функции ковариационных коэффициентов, из которого следует, что она достигает при значениях = 140 своего максимума 240. Указанное максимальное значение и определяет значение числителя в обобщенной формуле Хинчина-Поллячека. Рис. 3. График удвоенной суммарной функции ковариационных коэффициентов На рис. 4 показана зависимость среднего размера очереди рассматриваемого видеотрафика, от коэффициента загрузки Из данного графика следует, что средний размер очереди при коэффициенте загрузки = 0,5 находится в тех же пределах, что и полученное ранее максимальное значение суммарной функции ковариационных коэффициентов: знаменатель в (4) при равен 1. Рис. 4. Зависимость среднего размера очереди видеотрафика, от коэффициента загрузки Заключение Приведенные результаты и примеры подтверждают сделанные ранее [4; 6] выводы о существенном влиянии корреляционных связей между заявками, представляющими пакеты или кадры трафика, на эффективность мультисервисных сетей связи. Максимальное значение интеграла от ковариационной функции числа заявок на интервалах обслуживания одной заявки, при заданном коэффициенте загрузки, полностью определяет средний размер очереди в одноприборной системе массового обслуживания. Максимальное значение ковариационной функции находится путем интегрирования в пределах интервала корреляции анализируемого потока.

About the authors

Boris Yakovlevich Likhttsinder

Povolzhskiy State University of Telecommunications and Informatics

Email: lixt@psati.ru

References

Supplementary files