TRAFFIC AND QUEUE FRACTALITY IN QUEUING SYSTEMS

Abstract


Traffic in modern multiservice networks is usually correlated, therefore, the methods of classic theory do not work properly. In this paper the results of simulation and comparative analysis of traffic correlation influence for a fractal requests ceiling and requests flow in a case of real multiservice telecommunication networks are given. We examine Pollaczek-Khinchine formula generalization for an average queue length of stationary requests flow with a random correlation as well as opportunities for its application. It’s shown that a real random value of requests number that is proceed at the interval of one request service has an expectation value lesser than 1. It is shown that a process of queueing has passive time intervals that interrupt a correlation link with previous and following process parts. It is shown that correlation dependencies between separate queues values spread only at intervals of employment of queuing network for self-similar processes that have an infinitely big correlation interval.

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

  1. Клейнрок, Л. Вычислительные системы с очередями: пер. с англ. / Л. Клейнрок. - М.: Мир, 1979. - Т.2.- 600 с.
  2. Шелухин, О.И. Фрактальные процессы в телекоммуникациях / О.И. Шелухин, A.M. Тенякшев, А.В. Осин; под ред. О.И. Шелухина. - М.: Радиотехника, 2003. - 480 с.
  3. Степанов, С.Н. Теория телетрафика. Концепции, модели, приложения / С.Н. Степанов. - М.: Горячая линия-Телеком, 2015. - 808 с.
  4. Лихтциндер, Б.Я. Интервальный метод анализа трафика мультисервисных сетей / Б.Я. Лихтциндер // Модели инфокоммуникационных систем: разработка и применение. Приложение к журналу Инфокоммуникационные технологии. - 2011. - Вып. 8. - С. 104-152.
  5. Лихтциндер, Б.Я. Интервальный метод анализа трафика мультисервисных сетей доступа / Б.Я. Лихтциндер. - Самара: ПГУТИ, 2015. - 121 с.
  6. Блатов, И.А. Об оценке длин очередей в СМО с произвольной корреляцией / И.А. Блатов, Б.Я. Лихтциндер // Информационные технологии и нанотехнологии (ИТНТ-2018). - Самара, 24-27 апреля 2018 г.
  7. Zheng, F.U. A new method for the Pollaczek-Khinchin formula / F.U. Zheng, J. Wang // ICIC express letters. Part B, Applications: an international journal of research and surveys. 2015. V.6. - P. 1619-1624.
  8. Huang, L. Generalized pollaczek-khinchin formula for markov channels Communications / L. Huang, T.T. Lee // IEEE Transactions on. - 2013. - V.61. - №.8. - P. 3530-3540. doi: 10.1109/TCOMM.2013.061913.120712
  9. Huang, L. Generalized Pollaczek-khinchin Formula for Queueing Systems with Markov Modulated Services Rates: diss. / L. Huang. - The Chinese University of Hong Kong. - 2013.

Statistics

Views

Abstract - 26

PDF (Russian) - 1

Cited-By


Article Metrics

Metrics Loading ...

PlumX

Dimensions


Copyright (c) 2018 Blatov I.A., Likhtsinder 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