Параметрическое исследование системы с модулем активного управления трафиком

Полный текст

1. Введение В компьютерных сетях, в которых основным транспортным протоколом выступает протокол TCP [1], большой интерес представляет изучение характеристик технических систем управления трафиком, в частности, маршрутизаторов с модулем активного управления очередью поступающего в него потока данных. В качестве алгоритма активного управления очередью в таких системах обычно выступает один из алгоритмов типа RED (Random Early Detection) [2, 3]. Алгоритм RED [2] использует экспоненциально взвешенное скользящее среднее значение длины очереди �ˆ в качестве фактора, определяющего вероятность отбрасывания пакета �(�ˆ): ⎧0, 0 < �ˆ ::: �min, ⎪ ⎨ ⎪ �(�ˆ) = �ˆ - �min ⎪⎪ max min �max, �min < �ˆ ::: �max, (1) � - � ⎩1, �ˆ > �max. Здесь �min и �max - пороговые значения средневзвешенного значения длины очереди, �max - максимальный уровень сброса пакетов. По мере роста �ˆ растёт вероятность отбрасывания пакетов �(�ˆ) (см. (1)). Совокупность особенностей функционирования транспортного протокола TCP и алгоритма управления приводит к возникновению автоколебательного режима таких параметров системы, как средний размер окна протокола TCP и средний размер очереди пакетов в управляющем модуле, что негативным образом сказывается на показателях качества обслуживания сети [4-6]. Причиной перехода системы в автоколебательный режим может быть неудачный выбор параметров алгоритма управления. В частности, для классического алгоритма управления RED на данный момент не предложено чётких критериев выбора пороговых значений �min и �max, гарантирующих отсутствие перехода системы в автоколебательный режим. Но можно попытаться выявить зоны возникновения автоколебательного режима системы и проанализировать параметры автоколебаний. В данной работе предложено описание методики параметрического исследования модели с управлением на основе метода Крылова-Боголюбова [7], известного также как метод гармонической линеаризации [8]. В качестве математически формализованной модели системы с управлением по алгоритму RED в данной работе рассмотрена непрерывная модель, аналогичная преложенным в работах [9-14], с упрощающими предположениями: модель записана в моментах, при этом использована только фаза избежания перегрузок протокола TCP Reno и сброс пакетов при получении 3-х последовательных подтверждений ACK протокола TCP Reno: ⎧ ⎪�˙ (�) = ⎪ ⎪ ⎨ 1 � (�, �) - � (�)� (� - � (�, �)) 2� (� - � (�, �)) �(� - � (�, �)); �˙ (�) = � (�) ⎪ � (�, �) ⎪ �(�) - �; (2) ⎪⎩ ˆ˙ ˆ �(�) = -�� ��(�) + �� ��(�). � � Здесь использованы следующие обозначения: � - средний размер окна протокола TCP; � - среднее значение размера очереди; �ˆ - экспоненциально-взвешенное скользящее среднее (EWMA) среднего размера очереди; � - интенсивность обслуживания очереди; � - полное время двойного оборота; � = �� + � , где �� - время двойного оборота свободной сети (без учёта задержек в оборудовании); � - время нахождения пакета в очереди; � - количество сессий TCP; � - функция сброса пакетов, �� - весовой коэффициент, определяемый алгоритмом EWMA (0 < �� < 1). Схема исследований предложена на рис. 1. Пределы интегрирования Исходная система ОДУ Параметрические портреты Код для численного решения Решение Линеаризация при помощи SymPy Генерация кода с учетом стационарных программой на языке Julia Линеаризированная система ОДУ решений Рис. 1. План исследования 274 Вестник РУДН. Серия МИФ. Т. 26, № 3, 2018. С. 272-284 В соответствии со схемой исследований для нахождения параметров автоколебаний систему обыкновенных дифференциальных уравнений (2) необходимо сначала линеаризовать. При этом следует учесть, что при стандартной линеаризации теряется колебательная структура системы [4]. В качестве альтернативы предлагается использовать так называемый метод гармонической линеаризации, краткое описание которого приведено в разделе 2, а более подробное и в применении к системе с управлением по алгоритму RED- в работах [15-17]. При проведении гармонической линеаризации возникает целое семейство моделей. В частности, после линеаризации исходная система (2) распадается на несколько частей (см. рис. 2). Linear RED Delay Рис. 2. Схема линеаризованной системы В разделе 3 демонстрируется применение метода гармонической линеаризации для модели с управлением по алгоритму RED с целью получения коэффициентов гармонической линеаризации, используемых затем в системе компьютерной алгебры для получения семейства моделей с помощью пакета SymPy (см. раздел 4). В дальнейшем также с помощью системы компьютерной алгебры для каждой подмодели были получены наборы файлов на языке Julia, используя которые и задавая разные значения параметров, можно получить параметрический портрет автоколебаний (см. раздел 5). Следует заметить, что вычисления надо произвести для всех подмоделей, хотя решение будет существовать только для одной подмодели. На заключительном этапе следует провести верификацию полученных результатов. Для этого предложено использовать систему имитационного моделирования NS2 [18] (см. раздел 6). 2. Метод гармонической линеаризации Метод гармонической линеаризации был предложен Н. Н. Боголюбовым, Н. М. Крыловым [7] и Г. Найквистом [8]. Содержание этого метода сводится к отделению так называемых «медленных» переменных системы от «быстрых». Гармоническилинеаризованная система зависит от амплитуд и частот периодических процессов. Это является существенным отличием гармонической линеаризации от обычного способа линеаризации, приводящего к чисто линейным выражениям, что позволяет исследовать основные свойства нелинейных систем. Метод гармонической линеаризации применяется для систем определённой структуры. Система состоит из линейного �� и нелинейного ��� звеньев, заданных функцией �(�). Обычно рассматривают статический нелинейный элемент. На вход нелинейного элемента подаются свободные гармонические колебания: �(�) = �0 + �˜ := �0 + � sin(��). (3) На выходе нелинейного элемента ��� получается периодический сигнал, который можно разложить в ряд Фурье: � = �0 2 ∞ + ∑︁ (�� sin(���) + �� cos(���)) , (4) �=1 Велиева Т. Р. Параметрическое исследование системы с модулем активного . . . 275 где коэффициенты ряда Фурье имеют следующий вид: 2� 1 ∫︁ 2� 1 ∫︁ �0 = � 0 �(�0 + � sin(��))d(��); �� = � �(�0 + � sin(��)) sin(���)d(��), � = 1, ∞; 0 2� (5) 1 ∫︁ �� = � 0 �(�0 + � sin(��)) cos(���)d(��), � = 1, ∞. Линейный элемент представляет собой фильтр низких частот, то есть при увеличении � линейные элементы подавляют высшие гармоники. Для сигнала после нелинейного элемента можно записать: � = �0 + �˜ ≈ κ0(�, �, �0) + [κ(�, �, �0) + iκ′(�, �, �0)]�˜, (6) где κ0 - постоянная составляющая, κ и κ′ - коэффициенты гармонической линеаризации: 1 κ0(�, �, �0) = 2� 2� ∫︁ �(�0 + � sin(��))d(��); 0 2� �1 1 ∫︁ κ(�, �, �0) = = � �� 0 �(�0 + � sin(��)) sin(��)d(��); (7) 2� �1 1 ∫︁ κ′(�, �, �0) = � = �� 0 �(�0 + � sin(��)) cos(��)d(��). В дополнение к (6) записав � = �0 + �˜ = (�0 + �˜)��(�), � = �0 + �˜ = �(�) - (�0 + �˜), (8) можно получить уравнение гармонической линеаризации: [︂ ⃒ ⃒ �0 + ��(�)⃒ ⃒�=0 ]︂ κ0(�, �, �0) + + [1 + ��(κ(�, �, �0) + iκ′(�, �, �0))]�˜ = �(�) := �0(�) + �˜(�), (9) которое можно разделить на постоянную и гармоническую составляющие: [︂ ⃒ ⃒ �0 + ��(�)⃒ ⃒�=0 ]︂ κ0(�, �, �0) = �0(�), (10) [1 + ��(κ(�, �, �0) + iκ′(�, �, �0))]�˜ = �˜(�). При изучении автоколебательного режима предполагается, что внешний сигнал отсутствует (� = 0). 276 Вестник РУДН. Серия МИФ. Т. 26, № 3, 2018. С. 272-284 3. Гармоническая линеаризация модели с управлением по алгоритму RED В работах [15-17] проведена линеаризация модели с управлением по алгоритму RED и получено следующее выражение для функции ��: � �� �4� 3 ��(�) = - 2�(��� + i�)(i�� � + 1) � (︁i�� 2� - i��� � + 2� )︁ . (11) Линеаризованная функция сброса �RED имеет вид, приведённый на рис. 3. f (x) pmax Qmax - Qmin x Qmin Qmax Рис. 3. Линеаризованная функция сброса �RED Вычислим коэффициенты гармонической линеаризации κ0(�, �, �0), κ(�, �, �0) и κ′(�, �, �0) (7) для статической нелинейности �RED: 1 κ0(�, �, �0) = 2� 2� 2� ∫︁ �RED(�0 + � sin(��))d(��); 0 1 ∫︁ κ(�, �, �0) = �� 0 �RED(�0 + � sin(��)) sin(��)d(��); (12) 1 κ′(�, �, �0) = �� 2� ∫︁ �RED(�0 + � sin(��)) cos(��)d(��). 0 В зависимости от соотношений между порогами �min, �max, сдвигом �0 и амплитудой � возможно получить разные приделы интегрирования. Приведём несколько примеров графического метода нахождения пределов интегрирования (см. рис. 4) в зависимости от соотношений между постоянным сдвигом �0, амплитудой �, порогами �min и �max. Для примера рассмотрим случай, когда �min < �0 < �max, �0 -� > �min, �0 + � > �max. Тогда получим: 1 �max �max 2� ∫︁ ∫︁ κ0(�, �0) = 2� � max - �min 0 d(��) + �-�max d(��) = 1 �max = 2� �max - �min [2�max + �]; (13) Велиева Т. Р. Параметрическое исследование системы с модулем активного . . . 277 ⎡ �max 2� ⎤ 1 �max ∫︁ ∫︁ κ(�, �0) = �� � max - �min ⎣ 0 sin(��)d(��) + � -�max sin(��)d(��)⎦ = = 1 �max [︃ ⃒�max (- cos(��))⃒ ⃒2� + (- cos(��))⃒ ]︃ ; (14) ⃒ �� �max - �min ⃒0 ⃒ ⃒�- �max ⎡ �max 2� ⎤ 1 �max ∫︁ ∫︁ κ′(�, �0) = �� � max - �min ⎣ 0 cos(��)d(��) + �-�max cos(��)d(��)⎦ = = 1 �max [︃ ⃒�max sin(��)⃒ ⃒2� + sin(��)⃒ ]︃ . (15) ⃒ �� �max - �min ⃒0 ⃒ ⃒�- �max Найдём значения пределов интегрирования: �max - �0 √︂ (�max - �0)2 �0 + � sin �max = �max, sin �max = � ; cos �max = 1 - �2 . (16) pmax min min max max min max max min + min 2 min 2 max 2 2 min + max 2 max Рис. 4. Границы интегрирования Таким образом, из (13)-(15) с учётом (16) получим: �max [︂ (︂�max - �0 )︂ ]︂ κ0(�, �0) = 2� (� max - �min) 2 asin � √︃ + � ; 2 2�max (�max - �0) (17) κ(�, �0) = -�� (� max 1 - § �min) �2 ; κ′(�, �0) = 0. Полученные коэффициенты гармонической линеаризации в дальнейшем можно использовать для генерации кода программы с помощью системы компьютерной алгебры. 278 Вестник РУДН. Серия МИФ. Т. 26, № 3, 2018. С. 272-284 4. О программной реализации модели с управлением по алгоритму RED Программная реализация модели с управлением по алгоритму RED проводилась в два этапа. На первом этапе была задействована система компьютерной алгебры с пакетом SymPy. С помощью этой системы проведена вся трудоёмкая обработка полученных формул. Затем результирующие выражения были использованы как для генерации программ численных расчётов, так и при переносе формул в текст научных работ. Наиболее подходящей для поставленных в этой работе задач системой символьных вычислений является SymPy [19]. SymPy подходит нам по следующим причинам: § в качестве интерактивной оболочки удобно использовать блокнот Jupyter, являющийся компонентом системы iPython [20], реализующей идеологию REPL; § язык Python фактически используется как соединительный язык, своего рода язык-клей, который позволяет интегрировать между собой разные программные продукты; кроме того, в рамках библиотеки SciPy [21] поддерживается большое число выходных форматов; § выходные данные SymPy возможно естественным образом передать для численных расчётов в библиотеку NumPy [22] и разные языки программирования. В качестве языка для вычислений был выбран язык Julia [23]. Этот язык имеет ряд интересных особенностей, в частности он позиционируется как современная реинкарнация языка FORTRAN. Он поддерживает одновременно и этап прототипирования, и написание конечной версии программы. Фрагменты разработанного программного кода для расчёта нелинейной передаточной функции ���, выделения её действительной и мнимой частей, перехода после линеаризации исходной модели к ��, а также перехода к программному коду на языке Julia для последующих численных расчётов приведены в работе [24]. 5. Параметрическое исследование системы на возникновение автоколебаний В качестве иллюстрации определения зоны возникновения автоколебаний приведём конкретный пример. Зададим следующие параметры для модели с управлением по алгоритму RED: количество сессий TCP � = 60, время двойного оборота �� = 0, 5 с, значения порогов �min = 75 пакетов и �max = 150 пакетов, максимальный уровень сброса �max = 0, 1, вестовой коэффициент EWMA �� = 0, 002. Построив параметрический портрет (см. рис. 5), получим, что точкой перехода в автоколебательный режим является значение интенсивности обслуживания �� = 15 Mbps, т.е. при � � �� система будет находиться в автоколебательном режиме. 0.64 Hz 15 Mbps C 145 packages ν A Рис. 5. Параметрический портрет Велиева Т. Р. Параметрическое исследование системы с модулем активного . . . 279 6. Верификация результатов Использование натурного эксперимента сопряжено определёнными трудностями. Реальное оборудование не всегда бывает в наличии. Использование виртуального стенда связано с высокими требованиями к компьютерному оборудованию [12]. Кроме того, поскольку моделирование происходит в реальном времени, то весь процесс является крайне длительным. Для экономии ресурсов и времени обычно используют средства имитационного моделирования. Пакет ns2 [18, 25] является средством имитационного моделирования сетевых протоколов и создавался как эталонное средство моделирования. Поэтому его зачастую используют как альтернативу натурному эксперименту. Для имитационного эксперимента использована так называемая «гантельная» топология (см. рис. 6), в которой дополнительные сессии TCP эмитируются путём добавления дополнительных источников (см. рис. 7). 95 49 81 119 83 17 79 29 37 87 33 45 21 107 35 67 99 59 1 27 85 43 115 109 93 121 9 71 73 89 TCP source 1 42 62 16 86 22 90 60 4 28 58 68 48 6 14 112 108 70 103 23 3 63 97 113 69 101 77 7 51 5 11 47 39 111 31 ... 18 78 104 34 120 40 56 46 52 66 76 0 114 92 74 15 61 13 41 57 117 25 65 75 55 53 105 91 Router Router TCP Receiver 94 100 24 106 30 10 72 2 116 54 36 88 96 12 32 26 84 TCP source N 110 82 118 64 80 102 50 8 20 98 44 Рис. 6. Гантельная топология 38 Рис. 7. Визуализация моделирования системы Программа для ns2 пишется на языке TCL [26, 27]. Фрагменты программного кода ns2 для исследуемой модели, а также фрагменты кода на языке Julia [23], отвечающего за построение спектрального портрета автоколебательного режима на основе алгоритма быстрого преобразования Фурье [28] были представлены в работе [29]. На рис. 8 и 9 показано поведение средней длины очереди при интенсивности обслуживания � = 5 МБит/с и � = 20 МБит/с. Во втором случае явно видно наличие автоколебательного режима. Теоретически полученные характеристики этого режима: частота автоколебаний � = 0.6 Гц, амплитуда колебаний � = 150 пакетов. Queue Avg Length [pkt] 200 180 160 140 120 100 80 60 40 20 0 0 2 4 6 8 10 12 14 16 18 20 Queue Avg Length [pkt] 180 160 140 120 100 80 60 40 20 0 0 2 4 6 8 10 12 14 16 18 20 t [s] t [s] Рис. 8. Поведение средней длины очереди при интенсивности обслуживания � = 5 МБит/с Рис. 9. Поведение средней длины очереди при интенсивности обслуживания � = 20 МБит/с 280 Вестник РУДН. Серия МИФ. Т. 26, № 3, 2018. С. 272-284 При спектральном исследовании результатов имитационного эксперимента получены следующие характеристики: частота автоколебаний � = 0.5 Гц, амплитуда колебаний � = 169 пакетов (см. рис. 10 и рис. 11). Как видно, теоретические и экспериментальные значения весьма близки. 300 Queue Length [pkt] 250 200 150 100 50 0 0.0 2.5 5.0 7.5 10.0 12.5 15.0 17.5 20.0 Time [s] 175 Queue Length [pkt] 150 125 100 75 50 25 0 1000 750 500 250 0 250 500 750 1000 Frequency [Hz] Рис. 10. Поведение мгновенной длины очереди при интенсивности обслуживания � = 20 МБит/с Рис. 11. Спектр автоколебаний мгновенной длины очереди при интенсивности обслуживания � = 20 МБит/с Таким образом, наш программный комплекс может служить целям верификации теоретических исследований по возникновению автоколебательного режима в системах с управлением. 7. Заключение В данной работе проведено параметрическое исследование системы с модулем активного управления трафиком по алгоритму типа RED. Предложена методика параметрического исследования модели с управлением. Для демонстрации применения методики для систем с заданными параметрами алгоритма управления разработан программный комплекс для аналитических и численных вычислений. Верификация теоретических результатов проведена в системе имитационного моделирования NS2. Показана близость теоретических и экспериментальных значений.

Об авторах

Татьяна Рефатовна Велиева

Российский университет дружбы народов

Автор, ответственный за переписку.
Email: velieva_tr@rudn.university

аспирант кафедры прикладной информатики и теории вероятностей РУДН

ул. Миклухо-Маклая, д. 6, Москва, Россия, 117198

Список литературы