Selfl ike traffi c of multiservice communication networks: myths and reality


Cite item

Full Text

Abstract

The article considers the possibilities of using self-similar process models for traffi c service systems analysis in multiservice communication networks. The queuing system analytical models are widely used when studying communication network traffi c. However, it is impossible to apply the Poisson fl ow models for the analytical study of modern multi-service packet-switched net-works. Requests in such networks are strongly correlated, and even non-Poisson request interval probability distributions lead to signifi cant errors when analyzing queues if their correlation prop-erties are not accounted for. Furthermore, self-similar processes that refl ect long-term correlation dependencies in the multiservice network traffi c cannot be used for a network traffi c analysis due to the complexity of the model.

Full Text

Для исследования и оптимизации сетей связи широко применяются модели систем массового обслуживания (СМО). Основным объектом исследования СМО является взаимодействие двух компонентов: это некоторый ресурс и множество заявок на удовлетворение потребности в указанным ресурсе. Ограниченность ресурса и случайный характер поступления заявок приводят к возникновению задержек или отказов в удовлетворении ресурсом. На начальном этапе проектирования сетей связи, когда широко использовалась технология коммутации каналов, в качестве модели потока заявок, поступающих в узел связи, рассматривалась модель пуассоновского потока с экспоненциальным законом распределения длительностей временных интервалов между поступлениями соседних заявок. Аналогичное распределение предполагалось и для интервалов времени обслуживания заявок. Все поступающие заявки считались взаимно независимыми, так же, как и интервалы времени их обработки. Потоки заявок на телефонные соединения (заявок на канальный ресурс) являлись суперпозицией множества независимых потоков, поступающих от отдельных пользователей. Известно [1], что подобная суперпозиция при большом числе независимых потоков сходится к стационарному пуассоновскому потоку. Поэтому пуассоновская модель трафика была вполне оправданной. При переходе к телекоммуникационным сетям, основанным на технологиях пакетной коммутации, на начальных этапах также использовались предположения о пуассоновском характере потоков заявок и экспоненциальном характере распределения времени их обработки. Однако практика показала, что такие предположения совершенно не согласуются с действительностью и в некоторых случаях приводят к возникновению ошибок, превышающих тысячи процентов [3]. Особенно проявляются указанные несоответствия в телекоммуникационных сетях доступа, в которых программно-аппаратные средства используются для совместной передачи сравнительно небольшого количества совершенно разнородных потоков речевой, мультимедийной информации и передачи данных. В силу большой разнородности, потоки в таких сетях имеют существенно неравномерный характер и сильно коррелированы. Предположение о взаимной независимости поступающих потоков не выполняется, а взаимная зависимость пакетов сохраняется даже для далеко расположенных друг от друга интервалов времени. Учет корреляции Вся классическая теория СМО основана на предположении о взаимной независимости поступающих заявок. Даже известная классификация Кендалла [8] не предусматривает возможности учета корреляционных свойств исследуемых потоков, а учитывает лишь законы распределения соответствующих вероятностей. Существует ряд работ, рассматривающих различные законы распределения вероятностей интервалов между соседними заявками, непуассоновские распределения вероятностей чисел заявок на некотором временном интервале и ряд других. Однако все они предполагают взаимную независимость поступающих заявок. Если же указанные заявки взаимно коррелированы, то даже при экспоненциальном распределении интервалов времени между соседними заявками очереди таких заявок в СМО могут во много раз превышать очереди, создаваемые пуассоновским потоком, при одинаковых интенсивностях поступления заявок и одинаковых коэффициентах загрузки. В качестве примера рассмотрим реализацию простейшего стационарного потока заявок с экспоненциальным распределением интервалов времени между соседними заявками на длительном промежутке времени T [4]. Сгруппируем интерT [4]. Сгруппируем интерT валы заявок таким образом, чтобы наиболее короткие интервалы оказались в начальной части промежутка времени Т, а наиболее длинные окаТ, а наиболее длинные окаТ зались в его конечной части. Естественно, что распределение временных интервалов между заявками во вновь полученном потоке не изменится и останется экспоненциальным. Однако новый поток уже не будет пуассоновский, поскольку мы искусственно ввели в него дополнительную корреляционную зависимость. Средний размер очереди для такого потока будет во много раз превышать значения, полученные по формуле Хинчина - Полачека для пуассоновского потока. На рисунке 1 отображены зависимости средних размеров очередей для пуассоновского потока и того же потока с корректированными интервалами между заявками. Этот пример показывает, что при заданном времени обслуживания знание закона распределения вероятностей, далеко не полностью определяет размер очередей, получающихся при обработке заявок в СМО. Большое (а часто определяющее) влияние на размеры очередей оказывают корреляционные свойства потоков. Наиболее ранними исследованиями корреляционных свойств потоков заявок в СМО, повидимому, можно считать работы [5; 6], в которых рассматривается так называемый индекс дисперсии, учитывающий либо корреляционные свойства входных потоков, либо корреляционные свойства интервалов обработки заявок и не учитывающий их взаимную корреляцию. В последние годы появляются работы [7; 8], где также не учитываются взаимные корреляционные свойства. Однако, поскольку интервалы времени обработки заявок могут сильно зависеть от заявок входного потока, пренебрегать их взаимной корреляцией нельзя. Почти одновременно с [5; 6] была опубликована работа [9] автора этой статьи, где приводится соотношение, обобщающее формулу Хинчина - Полачека и учитывающее взаимные корреляционные свойства стационарных потоков заявок общего вида. Интервальный метод анализа Одним из перспективных, на наш взгляд, направлений изучения пакетного трафика является интервальный метод [4], позволяющий заменить анализ интервалов времени между соседними за Рисунок 1. Зависимости средних размеров очередей для пуассоновского потока (нижний график) и того же потока с коррелированными интервалами между заявками (верхний график)явками и интервалов времени обработки заявок анализом одной случайной величины - числом заявок, поступающих в течение последовательных интервалов времени обработки заявок. В [10; 11] показано, что дисперсия и корреляционные свойства указанной случайной величины при заданной загрузке полностью характеризуют средний размер очереди в системах СМО. Рассмотрим стационарный и ординарный входной поток заявок. Заявки поступают в моменты времени . it Разместим на оси времени последовательные интервалы , iτ соответствующие интервалам времени обработки каждой из заявок. Числа заявок, поступающих в течение каждого из интервалов времени i τ представляют собою анализируемую случайную переменную ( ). im τ Обозначим () m τ - математическое ожидание, () mD τ - дисперсию указанной случайной величины. Если λ - это средняя интенсивность потока заявок, а τ - математическое ожидание времени обслуживания, то ρ=λτ - это коэффициент загрузки одноканальной СМО. Нетрудно показать, что для любого потока заявок справедливо равенство ( ) .m τ =ρ Процесс образования очередей в указанной СМО определялся уравнением баланса 1 ( ) ( ) ( ) ( ), i i i i qqm - τ = τ + τ -δ τ (1) где ( ) 0 ,i δτ= если 1( ) ( ) 0, - τ = τ = ii mq ( ) 1 δτ= i в противном случае. Здесь () iq τ - размер очереди на интервале . iτ Значения ( ) 0 i δτ= возникают на тех интервалах времени, когда на текущем интервале заявки не поступают, а на предыдущем интервале отсутствует очередь. В течение интервалов, когда ( ) 0, i δτ= обработка заявок в процессоре не происходит и система простаивает. Случайная величина () i δτ имеет математическое ожидание, равное коэффициенту загрузки : ρ ( ) ( ) . ii m δ τ = τ =ρ (2) Следовательно, величина ( ) ( ) iim τ -δ τ является центрированной. На основании (1) для среднего числа заявок, находящихся в очереди ( ), ρq нами было получено соотношение, обобщаю щее известную формулу Хинчина - Полачека и справедливое для стационарных потоков общего вида, в том числе и для самоподобного потока: 1 ( ) 2 ( ) ( , )] () 2(1 ) 2 . i m m m k D D r k q ∞ -δ = ρ + ρ ρ ρ ρ= - -ρ ∑ (3) Здесь (,) im rk -δ ρ - нормированная корреляционная функция потока заявок ( ) ( ) iim ρ -δ ρ при заданном значении коэффициента загрузки ρ и сдвиге на k интервалов, а k интервалов, а k () mD ρ - дисперсия указанного потока. На рисунке 2 показана зависимость дисперсии от коэффициента загрузки для видеотрафика (нижний график) и зависимость числителя формулы (3), обусловленная наличием корреляционных связей в потоке видеотрафика (верхний график). Разница впечатляет. Эксперименты показали, что для большинства видов трафика мультисервисных сетей доступа значения второго члена числителя в формуле (3), обусловленного наличием корреляционных связей в потоке, существенно превышают значения дисперсии, и пренебрегать ими нельзя. Самоподобный трафик Измерения на реальных компьютерных сетях и измерения потоков в пакетных сетях передачи данных показали, что передаваемый в них трафик имеет свойства самоподобного случайного процесса. Анализу самоподобных процессов телетрафика посвящено множество публикаций. На качественном уровне самоподобие проявляется в том, что имеется медленно убывающая зависимость между величинами трафика в разные моменты времени, а также в том, что трафик носит пачечный характер. Эти пачки выглядят статистически подобными в различных масштабах интервалов времени [14]. Одной из фундаментальных отечественных работ в указанном направлении является работа [12], определения которой мы рассмотрим Рисунок 2. Зависимость дисперсии и числителя формулы (3) от коэффициента загрузки для видеотрафика применительно к анализируемому нами случайному процессу. Рассматриваемый процесс () im τ 0,iN = является стационарным и дискретным по времен и , τ которое необходимо для обработки одной заявки. Обозначим через () ikm - τ элемент, сдвинутый на k интервалов τ по отношению к ( ). im τ Значение корреляционной функции (корреляционный коэффициент) при сдвиге на k интервалов τ обозначим через ( , ) [ ( ) ( )][ ( ) ( )].m i ik k m m m m - µ τ = τ - τ τ - τ Очевидно, что дисперсия ( ) (0, ) mmD τ =µ τ - это корреляционный коэффициент при нулевом сдвиге () 0.k = Нормированная корреляционная функция: (,) ( , ) . () m m m krk D µρ ρ= ρ Согласно определениям, принятым в литературе [13], статистический процесс () im τ называется самоподобным, с параметром самоподобия H, (где H, (где H ,5 1) 0, H << если ему соответствует корреляционная функция 2 2 2 ( , ) [( 1) 2 ( 1) ]. H H H m r k k k k τ = + - + - (4) Процесс с указанной корреляционной функцией демонстрирует долговременную зависимость, если коэффициент H, называемый параметром Херста, удовлетворяет условию 0,5 1. H << В этом случае 2(1 ) lim ( , ) lim ( , ) , ïðèmm H r k r k Ck kk -β ττ = → →∞ (5) где 21() - Hβ= - коэффициент, меняющийся в пределах 0 1, <β< а С - некоторая медленно меС - некоторая медленно меС няющаяся функция. Нетрудно показать, что при отсутствии корреляции 0,5, =H и нормированная корреляционная функция убывает пропорционально первой степени увеличения коэффициента сдвига k. Для самоподобных процессов убывание корреляционной функции происходит намного медленнее. Поскольку (,) m k µτ является корреляционной функцией центрированного процесса, значения медленно меняющейся функции С близки к нулю. Если выполняется соотношение 0,5 1, H << то самоподобный процесс обладает свойством долговременной зависимости. Из (5) следует, что величина (,) m rk τ убывает по степенному закону. Это означает, что корреляционная функция является не суммируемой, и ряд, образованный ее последовательными значениями, расходится: 1 ( , ).m k rk ∞ = ρ∑ (6) Но в формуле (3) сумма корреляционных коэффициентов в числителе является конечной, и, следовательно, поток заявок, образующих очередь, не может считаться самоподобным. В чем же здесь противоречие? В принятых выше рассуждениях считалось, что случайная величина, образующая самоподобный поток, центрируется с помощью вычитания ее математического ожидания. В действительности, разностная переменная ( ) ( ) iim τ δ τ - центрируется путем вычитания из () im τ случайной величины ( ). i δτ При этом реальная случайная величина ( ), im τ представляющая числа заявок, поступающих в течение интервалов обслуживания одной заявки, имеет математическое ожидание ()im τ = () 1. i δτ=ρ< Поскольку величина () i δτ может принимать только единичные или нулевые значения, на интервалах, где ( ) 0, δτ= i заявки и очереди в системе полностью отсутствуют, и ее дальнейшее поведение не зависит от предыдущих значений ( ).im τ Таким образом, с целью анализа очередей, создаваемых в СМО самоподобными процессами, необходимо учитывать, что корреляционные свойства процесса, с точки зрения образования очередей, определяются разностной переменной ( ) ( ), iim τ δ τ - которая не удовлетворяет свойствам самоподобия. Долговременная корреляционная зависимость () im τ компенсируется корреляционной зависимостью величины ( ). i δτ Процесс, соответствующий указанной переменной, имеет временные интервалы, на которых () im τ = ( ) 0,i = δ τ = прерывающие корреляционную связь между предыдущими и последующими частями очереди. Следовательно, ни о какой долговременной зависимости здесь говорить не приходится. Она компенсируется и длится лишь в течение активной части каждого цикла образования очереди. Это еще раз подтверждает, что самоподобный трафик, имеющий долговременную корреляционную зависимость, при обработке в СМО указанную зависимость теряет, соотношение (6) не выполняется, и сумма сходится к некоторой постоянной величине С: 1 ( , ) .im k r k C -δ = ρ=∑ Именно значения указанной величины с учетом того, что , λτ=ρ определяют средний размер очереди по обобщенной формуле (1). На свойства разностной величины, аналогичной [ ( ) ( )], iim τ δ τ - обращал внимание еще Л. Клейнрок в [2], указывая, что эта случайная величина полностью определяет характер очередей в СМО. Итак, суммарный поток заявок, образующих очередь в СМО, учитывающий заявки, покидающие очередь, не удовлетворяет требованиям самоподобия даже в тех случаях, когда поток входных заявок этим требованиям удовлетворяет. Именно указанное отличие является одной из причин недостаточной эффективности применения модели самоподобного трафика при анализе очередей и задержек в СМО. Сложность модели самоподобного трафика Второй причиной недостаточной эффективности применения модели самоподобного трафика является ее сложность. В середине прошлого столетия появилось множество работ, посвященных анализу самоподобных процессов. Однако в указанных работах такие процессы рассматривались в отрыве от их анализа в составе СМО и не привели к существенным практическим результатам. Причины этого факта изложены в прекрасном обзоре [13]. Главный недостаток модели самоподобных потоков с точки зрения их использования при аналитическом моделировании процессов передачи информации в телекоммуникационных сетях состоит в том, что самоподобный поток сам по себе является достаточно сложным объектом. «Поэтому аналитическое исследование не только самого потока, но и СМО, в которую он поступает, является мало реальным» [13]. С этим выводом трудно не согласиться. Заключение Отсутствие весомых практических результатов подтверждает малую реальность аналитического исследования СМО с самоподобными входными потоками и ставит под сомнение миф о преимуществах модели самоподобных процессов при анализе трафика телекоммуникационных сетей.
×

About the authors

B. Ya Likhttcinder

References

  1. Степанов С.Н. Теория телетрафика. Концепции, модели, приложения. М.: Горячая линияТелеком, 2015. 808 с.
  2. Клейнрок Л. Вычислительные системы с очередями / под ред. Б.С. Цыбакова; пер. с англ. М.: Мир, 1979. 600 с.
  3. Лихтциндер Б.Я. Интервальный метод анализа мультисервисного трафика сетей доступа // Электросвязь. 2015. № 12. С. 52-54.
  4. Лихтциндер Б.Я. Трафик мультисервисных сетей доступа (интервальный анализ и проектирование). М.: Горячая линия - Телеком, 2018. 290 с.
  5. Mean waiting time approximations in the G/G/1 queue / D.L. Jagerman [et al.] // Queueing Systems. 2004. Vol. 46. P. 481-506.
  6. Balcioglu B., Jagerman D.L., Altiok T. Approximate mean waiting time in a GI/D/1 queue with autocorrelated times to failures // IIE Trasactions. 2007. № 39 (10). P. 985-996.
  7. Карташевский И.В, Сапрыкин А.В. Обработка коррелированного трафика в узле сети типа G/G/1 // Радиотехника. 2017. № 10. С. 119-125.
  8. Карташевский И.В. Модель трафика для программно-конфигурируемых сетей // Радиотехника. 2016. № 6. C. 124-129.
  9. Лихтциндер Б.Я. О некоторых обобщениях формулы Хинчина - Полачека // Инфокоммуникационные технологии. 2007. Т. 5. № 4. С. 253-258.
  10. Лихтциндер Б.Я. Корреляционные свойства длин очередей в системах массового обслуживания с потоками общего вида // Инфокоммуникационные технологии. 2015. Т. 13. № 3. С. 276-280.
  11. Лихтциндер Б.Я. Корреляционные связи в пачечных потоках систем массового обслуживания // Телекоммуникации. 2015. № 9. С. 8-12.
  12. Шелухин О.И., Тенякшев А.М., Осин А.В. Фрактальные процессы в телекоммуникациях / под ред. О.И. Шелухина. М.: Радиотехника, 2003. 480 с.
  13. Вишневский В.М., Дудин А.Н. Системы массового обслуживания с коррелированными входными потоками и их применение для моделирования телекоммуникационных сетей // Автоматика и телемеханика. 2017. № 8. С. 3-59.
  14. Цыбаков Б.С. Модель телетрафика на основе самоподобного случайного процесса // Радио техника. 1999. № 5. C. 24-31.

Copyright (c) 2019 Likhttcinder 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