ANALYSIS OF GENERAL QUEUING SYSTEM WITH SELECTS FUNCTIONS

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

Supplementary files