TRAFFIC AND QUEUE FRACTALITY IN QUEUING SYSTEMS

Full Text

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

About the authors

Igor Anatoljevich Blatov

Povolzhskiy State University of Telecommunications and Informatics

Email: blatow@mail.ru

Boris Yakovlevich Likhtsinder

Povolzhskiy State University of Telecommunications and Informatics

Email: lixt@psati.ru

References

Supplementary files