ANALYSIS OF GENERAL QUEUING SYSTEM WITH SELECTS FUNCTIONS

Abstract

Delay and jitter are very important parameters that determine the quality of service of multiservice networks. They are of particular importance in networks with multimedia stream processing. In this paper, we consider the G/M/1 queue system and the problem of estimating jitter in this system. The paper presents an analytical model for estimating jitter delay when a network load changes. The results of an analytical model for estimating jitter delay in packet transmission are analyzed. An estimate of the packet delay in the simulation model was obtained depending on the network load for various variants of random distribution of time intervals between packets. A technique for estimating jitter in a simulation model was proposed where streams with exponential packet length distribution and exponential, Pareto and Weibull distributions of time intervals between packets, used as examples of random distribution, were processed. A comparison of the results of simulation modeling and analytical estimation of jitter is given.

Full Text

Введение Современные сети связи отличаются многообразием услуг, и в связи с этим большим количеством протоколов и технологий, используемых для обеспечения данных услуг. Основной задачей в разработке существующих IP-сетей является интеграция и поддержка широкого спектра приложений и сервисов, объединяющих голос, данные, потоковое вещание и VoD. Различные типы носителей, обменивающиеся этими приложениями, имеют разные требования в отношении полосы пропускания, задержки, джиттера и надежности. Важной задачей является обеспечение качества услуг. При этом следует учесть, что для различных приложений требования к параметрам качества услуг различны. Традиционно в качестве параметров, которые определяют уровень качества обслуживания, используют задержку, джиттер и вероятность потерь пакетов. Для современных мультимедийных приложений наибольшее значение имеет задержка и её вариация или джиттер. Данный параметр оказывает серьезное влияние на качество обслуживания трафика приложений реального времени. К таким приложениям относят в первую очередь IPTV, видеоконференции, VoD, VoIP. В настоящее время джиттер задержки остается одним из важнейших параметров качества обслуживания. Например, оценка джиттера и управление джиттером могут способствовать уменьшению вероятности переполнения буфера, что приводит к потерям пакетов, когда приложение не принимает пакеты в течение некоторого времени. Исследование джиттера как важного параметра, характеризующего поведение трафика, является весьма важной задачей. Определим джиттер как , (1) где - время передачи -го пакета. Отметим, что в [1] под джиттером понимают среднюю абсолютную вариацию задержки, а в [2] джиттер определяется как изменение задержки в потоке от некоторого минимального значения. Проблема оценки джиттера рассматривается во многих работах. Например, в [3] предложены методы оценки джиттера в тандемной очереди. Как правило, в качестве математической модели системы используют систему M/M/1, то есть предполагается марковская модель поступления и обслуживания заявок. Такую модель трафика можно считать справедливой, например, на уровне агрегации трафика мультисервисной сети. Для большинства потоков данная модель является слишком упрощенной [4-6]. Чаще приходится иметь дело с потоками обладающими свойствами самоподобия. При этом для параметров трафика, таких как интервалы времени между пакетами и длительности пакетов, характерны распределения с тяжелыми хвостами, и наличие корреляционных связей. Поэтому современные системы, обрабатывающие непуассоновский трафик, лучше описываются моделями G/G/1 (G/G/n). В [11] приведены решения по оценке джиттера для некоторых непуассоновских потоков, где исследуется влияние длинных пакетов на задержку коротких пакетов в современных телекоммуникационных сетях с коммутацией пакетов. В [8-10] приведена оценка сквозного джиттера общего потока при интенсивном и малоинтенсивном движении (данная тема нашла развитие в [13-14] при анализе задержки пакетов). В [12] приведены некоторые примеры расчета джиттера задержки пакетов трафика при обработке в различных системах массового обслуживания в одиночной очереди. Рассмотрены особенности подходов к определению джиттера в системе G/G/1, причем статистические особенности современного трафика в основном характеризуются распределениями Парето и Вейбулла. Представляет интерес расширить спектр используемых распределений с тяжелыми хвостами при анализе джиттера, провести моделирование процессов обработки IP-трафика для различных моделей и дать аналитическую оценку джиттера передачи пакетов при обработке трафика в системе G/M/1. Имитационное моделирование в программе ns2 В качестве среды для имитационного моделирования используется программа ns2. Данная программа позволяет реализовать большой набор моделей трафика с широким диапазоном распределений. Кроме того, имеется возможность моделирования обработки трафика, зарегистрированного на реальной сети. Модель обработки трафика реализована согласно схеме, рисунок 1. Рисунок 1. Схема моделирования в ns2 Исследуемый трафик описывается моделью G/M/1, где интервалы времени между пакетами описываются следующими распределениями: экспоненциальное, Парето, Вейбулла. В рамках данной модели также обрабатывался трафик, снятый на реальной сети оператора связи [7], интервалы времени между пакетами которого, описывались распределением Dagym. В качестве модуля имитационной модели транспортного уровня выбран UDP, что позволяет передавать пакеты без повторных передач в случае потери и без подтверждений. Пример 1. Экспоненциальное распределение интервалов времени между пакетами. В данном примере моделируется очередь типа M/M/1. Функция экспоненциального распределения имеет вид , (2) где - параметр распределения, в нашем случае это интенсивность поступления пакетов; - непрерывная случайная величина. В программе ns2 данная модель трафика задается следующим кодом: set udp [new Agent/UDP] $ns attach-agent $s2 $udp set rng1 [new RNG] $rng1 seed 1 set arrival_t [new RandomVariable/Exponential] $arrival_t use-rng $rng1 $arrival_t set avg_ 10 $arrival_t set shape_ 1 set rng2 [new RNG] $rng2 seed 1 set pktSize [new RandomVariable/Exponential] $pktSize use-rng $rng2 $pktSize set avg_ 10 $pktSize set shape_ 1 set null [new Agent/Null] $ns attach-agent $dest $null $ns connect $udp $null Результат имитационного моделирования при обработке трафика модели M/M/1 представлен на рисунке 2. Рисунок 2. Результаты имитационного моделирования системы M/M/1 Пример 2. Модель трафика с распределением Парето интервалов времени между пакетами. Такую систему можно обозначить как P/M/1. Распределение Парето имеет вид , (3) где - параметр формы; - масштабный параметр. Система P/M/1 смоделирована аналогично подходу, реализованному в [6]. Параметры моделирования: , . В программе ns2 случайные величины с распределением Парето задаются следующим кодом: set udp [new Agent/UDP] $ns attach-agent $s2 $udp set rng1 [new RNG] $rng1 seed 1 set arrival_t [new RandomVariable/Pareto] $arrival_t use-rng $rng1 $arrival_t set avg_ 10 $arrival_t set shape_ 2 При обработке трафика с распределением Парето для интервалов времени между пакетами изменение джиттера в зависимости от нагрузки показано на рисунке 3. Рисунок 3. Результаты имитационного моделирования системы P/M/1 Можно заметить, что с увеличением нагрузки джиттер незначительно уменьшается. Пример 3. Модель трафика с распределением Вейбулла для интервалов времени между пакетами. Такую систему можно обозначить как W/M/1. Распределение Вейбулла есть , (4) где - параметр формы, - масштабный параметр. Для распределения Вейбулла были рассмотрены два набора параметров: 1) , ; 2) , (при , распределение Вейбулла вырождается в экспоненциальное). Полученные результаты не имеют заметных различий, поэтому на рисунке 4 представлены результаты только для , . Рисунок 4. Результаты имитационного моделирования системы W/M/1 В данном случае наблюдаем заметный рост джиттера при увеличении нагрузки. Пример 4. Трафик, зарегистрированный на реальной сети. Данный поток задается в ns2 следующим образом: set udp1 [new Agent/UDP] $ns attach-agent $s2 $udp1 set ss_file2 [new Application/Traffic/Trace] set trace2 [new Tracefile] $trace2 filename iptv.dat $ss_file2 attach-tracefile $trace2 $ss_file2 attach-agent $udp1 set null1 [new Agent/Null] $ns attach-agent $dest2 $null1 $ns connect $udp2 $null1 Как было указано выше, интервалы времени между пакетами для данного трафика лучше всего аппроксимируются распределением Dagym, которое имеет вид , (5) где и - параметры формы; - масштабный коэффициент; - параметр сдвига. Рисунок 5. Результаты имитационного моделирования обработки реального трафика Область определения функции с параметрами ; ; ; . На рисунке 5 показано изменение джиттера задержки пакетов реального трафика в процессе имитационного моделирования. Начальные выбросы характеризуются неустановившимся режимом в начале работы системы (переходным режимом). В установившемся режиме также наблюдается сильное изменение задержки, а, следовательно, и джиттера. Анализируя данные рисунка 5 можно заметить корреляцию поведения задержки и джиттера. Рисунок 6. Изменение джиттера задержки пакетов в зависимости от загрузки сети для реального трафика Dagym Результаты исследования реального трафика (когда в качестве произвольного распределения выступает распределение Dagym) показаны на рисунке 6. Рисунок 7. Изменение задержки пакетов в зависимости от загрузки сети Кроме того, в процессе эксперимента была оценена задержка для всех рассмотренных случаев. На рисунке 7 представлены результаты по задержке при имитационном моделировании исследуемых потоков. Обратим внимание, что при снижении нагрузки задержка обращается в ноль, а при увеличении нагрузки возрастает, и при задержка стремится к ∞. В тоже время поведение джиттера сильно отличается от поведения задержки. Можно заметить, что в случае обработки всех рассмотренных типов трафика джиттер не обращается в ноль при , и не становится бесконечным при Аналитическая оценка джиттера задержки передачи пакетов для различных типов трафика Для построения аналитических оценок джиттера при экспоненциальном распределении длительности пакетов воспользуемся результатом, приведенным в [12], при этом джиттер определяется согласно [2] по формуле (1). Для среднего значения джиттера справедливо (6) где функция плотности вероятности (ФПВ) для интервалов времени между пакетами; ФПВ времени обслуживания; - ФПВ времени передачи. Для системы G/M/1 (6) примет вид , (7) где - преобразование Лапласа ФПВ распределения - интервалов времени между пакетами, , (8) - скорость передачи пакета, определяемая как , где - параметр нагрузки, имеющий в данном изложении смысл вероятности ожидания и определяемый как , - интенсивность обслуживания пакетов. Как было показано выше, в качестве примеров произвольного распределения были рассмотрены экспоненциальное, Парето, Вейбулла. Произведем оценку джиттера в системе G/M/1 для выбранных распределений. Пример 5. Экспоненциальное распределение для времени между поступлениями пакетов соответствует ФПВ вида , (9) где . Преобразования Лапласа в этом случае (10) и для джиттера из (7) можно получить . (11) На рисунке 8 показано изменение джиттера в зависимости от нагрузки в случае обработки трафика в системе M/M/1. Пример 6. Распределение Парето. Для этого случая в [12] оценка джиттера производится с учетом того, что преобразование Лапласа имеет вид (12) где - интегральная показательная функция. Подстановка (12) в (7) дает результат [12], представленный в графическом виде на рисунке 8. Рисунок 8. Изменение джиттера задержки пакетов в зависимости от загрузки сети при аналитическом моделировании Пример 7. Распределение Вейбулла. Для из (4) запишем согласно (8) (13) Аналогично проведенному в первом разделе эксперименту рассмотрим три набора параметров распределения Вейбулла. Получим при ; : ; (14) при ; ; (15) при ; . (16) Изменение параметра , как и в случае имитационного моделирования, не приводит к какому-либо заметному изменению значения джиттера. Поэтому на рисунке 8 приведена только одна зависимость: при , Проанализируем полученные результаты. В работе рассмотрено две модели трафика, где интервалы времени между пакетами описываются распределениями с тяжелыми хвостами, это распределения Парето и Вейбулла. Сравнение результатов оценки джиттера при данных распределениях представляет определенный интерес. Анализируя зависимости, представленные на рисунках 3; 4 и 8, можно заметить, что в системе P/M/1 джиттер уменьшается с увеличением нагрузки, тогда как в системе W/M/1 с увеличением нагрузки джиттер растет. И, хотя в отличие от задержки при джиттер не стремится к бесконечности, его поведение кардинально отличается от поведения при других распределениях. Причину данного эффекта можно найти, проанализировав законы распределения случайных величин Парето и Вейбулла. В случае распределения Парето дисперсия случайной величины имеет вид , и при выбранном наборе параметров , дисперсия случайной величины будет стремиться к бесконечности. Для распределения Вейбулла дисперсия где - гамма-функция, при выбранных будет конечной величиной [16]. Следует учесть, что распределение Парето предполагает, что вероятность случайной величины, а в нашем случае это интервалы времени между пакетами, имеет наибольшее значение в области малых значений. Следовательно, в области малых значений интервалов времени будут сосредоточены высокие скорости потока, и как следствие увеличится размер очереди при обработке и задержка. Большая задержка, связанная в основном с увеличением времени ожидания в очереди, как правило, для всех пакетов одинакова. В целом это приводит к снижению изменения задержки, то есть джиттера. В случае распределения Вейбулла наибольшую вероятность будут иметь интервалы времени между пакетами, лежащие в области более высоких значений по сравнению с распределением Парето, что в сравнении уменьшает скорость потока. В тоже время распределение Вейбулла - это распределение с тяжелым хвостом, что по сравнению с распределением Парето увеличивает долю больших и малых интервалов времени. Можно предположить, что это вызовет эффект сильной неравномерности загрузки сетевых узлов, что приведет к большому разбросу значений задержки, и как следствие к увеличению джиттера. Заключение В работе предложены методы оценки джиттера для системы очередей G/M/1. В качестве примеров произвольного распределения интервалов времени между пакетами использованы экспоненциальное, Парето и Вейбулла распределения. Предложена методика оценки джиттера с использованием имитационной модели, при реализации которой использовались указанные распределения. По результатам имитационного моделирования сделаны следующие выводы. 1. Увеличение загрузки сети в системе M/M/1 не оказывает серьезного влияния на джиттер. 2. В системе очередей P/M/1 джиттер уменьшается при загрузке до 0,6 и незначительно увеличивается при дальнейшем росте загрузки. 3. В системе очередей W/M/1 джиттер с увеличением загрузки сети увеличивается, но не обращается в бесконечность. Данные результаты в целом согласуются с аналитической оценкой джиттера. Следует заметить, что при этом наблюдается некоторое отклонение результатов имитационного моделирования от аналитических результатов. Это может быть вызвано несколькими причинами, главная из которых видится в отсутствии учета корреляционных свойств потоков и характеристик сетевого канала в аналитической модели. Это весьма важная задача, сопряженная с определенными трудностями, которая требует дальнейшего исследования. Кроме того, важной перспективной задачей является анализ поведение джиттера при обработке трафика в модели очереди G/G/1.
×

About the authors

Marina Anatolievna Buranova

Povolzhskiy State University of Telecommunications and Informatics

Email: buranova-ma@psuti.ru

Vyacheslav Grigorievich Kartashevskiy

Povolzhskiy State University of Telecommunications and Informatics

Email: kartashevskiy-vg@psuti.ru

References

  1. Demichelis C., Chimento P. IP Packet Delay Variation Metric for IP Performance Metrics (IPPM). Institution IETF, RFC 33934. - 2000. - 21 p. doi: 10.17487/RFC3393.
  2. Internet protocol data communication service IP packet transfer and availability performance parameters. ITU-T Recommendation Y.1540. - 2002. - 33 p. // URL: https://www.itu.int/rec/T-REC-I.380-199902-S/en (д.о. 10.07.2018).
  3. Le Gall P. The theory of networks of single server queues and the tandem queue model // Journal of Applied Mathematics and Stochastic Analysis. - 1997. - Vol. 10 (4). - P. 363-381.
  4. Шелухин О.И., Тенякшев A.M., Осин А.В. Фрактальные процессы в телекоммуникациях. - М.: Радиотехника, 2003. - 480 с.
  5. Буранова М.А. Исследование статистических характеристик самоподобного телекоммуникационного трафика // Инфокоммуникационные технологии. - 2012. - Т. 10. - № 4. - С. 35-40.
  6. Downey A. Lognormal and Pareto distributions in the Internet // Computer Communications. - 2005. - Vol. 28, No 7. - P. 790-801.
  7. Специальная радиосвязь. Развитие и модернизация оборудования и объектов. Под. ред. А.Л. Бузова, С.А. Букашкина. - М.: Радиотехника, 2017. - 448 с.
  8. Le Gall P. Single server queuing networks with varying service times and renewal input // Journal of Applied Mathematics and Stochastic Analysis. - 2000. - Vol. 13(4). - P. 429-450. doi: 10.1155/S1048953300000368.
  9. Dahmouni H., Girard A., Sanso B. An analytical model for jitter in IP networks. // Annals of telecommunications. - 2012. - Vol. 67. - Issue 1-2. - P. 81-90. doi: 10.1007/s12243-011-0254-y.
  10. Matragi W., Bisdikian C., Sohraby K. Jitter calculus in ATM networks: single node case // Proc. IEEE INFOCOM’ 94, Toronto, 1994. - P. 232-241. doi: 10.1109/infcom.1994.337612.
  11. Matragi W., Sohraby K., Bisdikian C. Jitter calculus in ATM networks: multiple node case // IEEE/ACM Trans Netw5. - 1997. - P. 122-133. doi: 10.1109/infcom.1994.337611.
  12. Goldstein A., Yanovsky G. Traffic Engineering in MPLS Tunnels// International Conference on «Next Generation Teletraffic and Wired/Wireless Advanced Networking (NEW2AN'04)». February 02-06, 2004. - Р. 200-202.
  13. Dbira H., Girard A., Sanso B. Calculation of packet jitter for non-poisson traffic // Annals of telecommunications. - 2016. - Vol. 71. - Issue 5-6. - P. 223-237. doi: 10.1007/s12243-016-0492-0.
  14. Гольдштейн А. В. Механизм эффективного туннелирования в сети MPLS // Вестник связи. - 2004. - № 2. - С. 48-54.
  15. Kartashevskii V.G., Kireeva N.V., Buranova, M.A., Chupakhina, L.R. Study of queuing system G/G/1 with an arbitrary distribution of time parameter system // 2nd International Scientific-Practical Conference Problems of Infocommunications Science and Technology, PIC S and T 2015 - Conference Proceedings. - 2015. - P. 145-148. doi: 10.1109/infocommst.2015.7357297.
  16. Kartashevskii V.G., Buranova M.A. Analysis of Packet Jitter in Multiservice Network // 5th International Scientific-Practical Conference Problems of Infocommunications Science and Technology, PIC S and T 2018 doi: Conference Proceedings. - 2018.

Statistics

Views

Abstract: 63

PDF (Russian): 35

Dimensions

Article Metrics

Metrics Loading ...

PlumX


Copyright (c) 2019 Buranova M.A., Kartashevskiy V.G.

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