Вычислительная и имитационная модели системы с управлением на Modelica

Полный текст

1. Введение При моделировании сложных систем возникает проблема выбора модельного подхода. Приведём следующий пример. Пусть имеется система управления посредством алгоритма случайного раннего обнаружения (Random Early Detection, RED) [1] потоком трафика, передаваемого по протоколу TCP (Transmission Control Protocol). В такой системе можно выделить следующие особенности. Во-первых, модель передачи данных по протоколу TCP можно описывать как в дискретно-событийной парадигме (как это реализовано в эталонном средстве имитационного моделирования сетевых протоколов ns-2 [2, 3], но в этом случае возникает проблема масштабируемости системы), так и с использованием непрерывного подхода (представление потока данных как потока жидкости [4, 5], в этом случае усложняется математическая модель системы). Во-вторых, модель модуля активного управления TCP-подобным трафиком может быть представлена особого вида функцией, зависящей от типа RED-алгоритма Статья поступила в редакцию 17 ноября 2018 г. (функция может быть кусочно непрерывной с разрывами первого рода, иметь различные параметры, влияющие на её вид и т.п.) [1, 6-8], т.е. тоже встаёт вопрос о выборе способа моделирования. В-третьих, модель взаимодействия входящего TCP-потока и маршрутизатора, обрабатывающего поток по алгоритму типа RED, может иметь ряд ограничений, затрудняющих её исследование в рамках только одного подхода - непрерывного или дискретного. Таким образом, встаёт проблема моделирования как протокола TCP и управляющего модуля по отдельности, так и их взаимодействия. Кроме того, необходимо выбрать адекватную методику моделирования [9-11]. Для решения проблемы дискретного и непрерывного подходов при моделировании сложных систем предлагается использовать гибридный подход [12-17]. В качестве программного средства моделирования предлагается использовать язык Modelica [18, 19], а конкретно его реализацию OpenModelica. Язык Modelica [18, 19] разработан некоммерческой организацией Modelica. Также эта ассоциация разрабатывает свободную стандартную библиотеку для этого языка. Modelica поддерживает непрерывную и гибридную (непрерывно-дискретную) парадигмы. Впрочем, чисто дискретные элементы в языке тоже присутствуют. Структура работы следующая. В разделе 2 приводятся аргументы в пользу применения гибридного подхода к моделированию сложных систем. Затем в разделе 3 рассматривается идеология построения имитационной модели функционирования протокола TCP на языке Modelica. Показано, что по описанию в соответствии со стандартом можно получить имитационную модель функционирования данного протокола на языке Modelica. В следующем разделе 4 продемонстрированы возможности языка Modelica для численного моделирования гибридной по структуре системы взаимодействия входящего TCP-потока и маршрутизатора, обрабатывающего поток по алгоритму типа RED. В заключении делается вывод о применимости гибридного подхода к задачам моделирования сетевых протоколов. 2. Гибридный подход к моделированию Гибридный подход к моделированию систем [12-16] позволяет учесть как непрерывный, так и дискретный аспекты поведения моделируемого объекта. Гибридность поведения моделируемой системы может проявляться по разному: § взаимодействие объекта, описываемого непрерывной моделью, с объектом, описываемым дискретной моделью (пример - система автоматического управления, в которой модель объекта управления является непрерывной, а модель устройства управления - дискретной); § изменение состава моделируемой системы (пример - системы с переменным числом компонентов); § скачкообразные качественные изменения состояний непрерывной модели объекта (в качестве дискретных событий выступают моменты качественного изменения поведения непрерывной модели). При гибридном подходе к моделированию акцент можно делать или на дискретности исходной системы и учитывать длительность входных и выходных действий, или на непрерывности исходной системы с допущением наличия мгновенных событий наряду с длительными по времени. Рассмотрим второй случай и будем добавлять к существующей динамической модели дискретные элементы. В качестве таких элементов могут выступать: § начальные условия или скачкообразное изменение параметров системы в правой части дифференциального уравнения; § число уравнений, описывающих поведение динамической системы; § форма правых частей дифференциальных уравнений. В рамках гибридной модели естественным образом можно представить как индикаторные функции, так и дифференциальные включения, так как скачкообразное изменение параметров можно представить как изменение начальных условий в модифицированной системе дифференциальных уравнений. Этот приём позволяет заменить систему с изменяющейся правой частью на систему с постоянной правой частью, но изменяющимися начальными условиями. Например, система d� = �(�, �, �), � = d� {︂�1, � ∈ X1, �2, � ∈ X2, (1) в которой � - кусочно-постоянный параметр, может быть представлена в виде ⎧d� ⎪⎨ d� = �(�, �, �), с начальными условиями ⎪⎩ d� = 0 d� {︂�(0) = �1, � ∈ X1, �(0) = �2, � ∈ X2. (2) (3) Такой приём возможно применить при моделировании поведения протокола TCP и механизма RED в разных состояниях. 3. Имитационное моделирование функционирования протокола TCP на языке Modelica Обычно функционирование сетевых протоколов формулируется в форме дискретнособытийного описания. Рассмотрим идеологию построения имитационной модели функционирования протокола TCP на языке Modelica. Есть несколько стандартов протокола TCP, отличающихся реализацией механизма скользящего окна, применяемого для управления перегрузками в сетях передачи данных. В данной работе будем моделировать протокол TCP Reno [20, 21], поскольку именно на нём базировалась оригинальная модель [22-25], используемая в наших исследованиях в качестве базовой. Особенностью протокола TCP Reno является зависимость изменения размера окна перегрузки (Congestion Window, CWND) от той или иной фазы механизма управления перегрузками. Всего таких фаз четыре: медленный старт, предотвращение перегрузок, быстрое восстановление, тайм-аут. Работа алгоритма предотвращения перегрузок в TCP описывается в RFC 5681 [21]. В фазе медленного старта окно перегрузки растёт линейно ���� = ����+1 в случае прихода на источник сообщения, что оправленный пакет доставлен (Acknowledge, ACK). Первоначальный размер окна перегрузки (Minimum Segment Size, MSS) может принимать значение 1, 2 или 10 сегментов. Сообщения о доставке отправляются приёмником для каждого пакета. Для упрощения можно предположить, что по истечении времени двойного оборота (Round-Trip Time, RTT) источник получает сразу все подтверждения о доставке отправленных пакетов. В этом случае можно считать, что по истечении времени двойного оборота происходит удвоение размера окна перегрузки. Переход в фазу предотвращения перегрузки происходит при достижении размером окна TCP определённого размера. Меняется и схема изменения размера окна - для каждого подтверждения ACK окно перегрузки увеличивается на величину 1/����. Это эквивалентно увеличению окна на один пакет за время двойного оборота. Переход в фазу быстрого восстановления происходит при получении сообщения типа тройного дублирования подтверждения (Triple Duplicate ACK, TD ACK). В этой фазе размер окна уменьшается в 2 раза ���� → ����/2. Фаза тайм-аут (Timeout, TO) возникает, когда источник не получает подтверждения о доставке пакета в течение заданного времени. В этом случае размер окна перегрузки устанавливается в начальное значение и протокол переходит в фазу медленного старта. Важную роль в работе протокола TCP играет таймер повторной передачи (Retransmission timer ). Значение этого таймера инициализируется при отправке сегмента данных. Подтверждение о доставке отправленного сегмента должно быть получено до срабатывания таймера. Иначе отправка сегмента данных должна быть повторена. При этом значение таймера остаётся постоянным в фазах медленного старта и избежания перегрузок, а в фазах быстрого восстановления и тайм-аута таймер будет линейно уменьшаться с течением времени. Опишем переходы между состояниями TCP. Переменная ssth используется для перехода от первоначальной фазы медленного старта протокола TCP к фазе предотвращения перегрузки. Инициализация этой переменной происходит при открытии соединения протокола TCP путём задания максимально возможного размера окна передачи. Собственно переход от фазы медленного старта к фазе предотвращения перегрузок происходит при достижении cwnd заданного размера ssth. При потере пакетов происходит переход либо в состояние быстрого восстановления, либо в состояние тайм-аута. Данный переход мы моделируем эмпирически в зависимости от порогового размера окна (timeout_th) [26]. Аналогично из состояния избежания перегрузки можно перейти либо в состояние быстрого восстановления, либо в состояние тайм-аута. По истечении времени повторной передачи из состояния быстрого восстановления мы переходим в состояние избежания перегрузок, а из состояния тайм-аута в состояние медленного старта. На основе описания переходов между фазами протокола TCP можно построить UML-диаграмму (рис. 1). Slow start do/cwnd + 1 [cwnd >= ssth] Congestion Avoidance drop [cwnd >= timeout_th] drop [cwnd < timeout_th] [retr_timer < 0] do/cwnd + 1/cwnd [retr_timer < 0] drop [cwnd >= timeout_th] drop [cwnd < timeout_th] Fast Recovery do/ssth=cwnd/2, cwnd=ssth Timeout do/cwnd=1, ssth=cwnd/2 Рис. 1. Диаграмма состояний TCP Полученную диаграмму можно преобразовать в программу на языке Modelica. Приведём фрагмент листинга (листинг 1), полностью соответствующий описанию в стандарте переходов между фазами протокола TCP. Листинг 1: Алгоритм перехода состояний для протокола TCP algorithm state := TCPState. slow Start ; when edge ( drop_ delay ) and w >= timeout_ th and ( state == TCPState. slow Start or state == TCPState. congest Avoid ) then state := TCPState. fast Recov ; elsewhen w >= ssth and state == TCPState. slow Start then state := TCPState. congest Avoid ; elsewhen edge ( drop_ delay ) and w < timeout_ th and ( state == TCPState. slow Start or state == TCPState. congest Avoid ) then state := TCPState. time Out ; elsewhen retr_ timer < 0 and state == TCPState. fast Recov then state := TCPState. congest Avoid ; elsewhen retr_ timer < 0 and state == TCPState. time Out then state := TCPState. slow Start ; end when ; Также на языке Modelica запишем уравнения изменения размера окна передачи протокола TCP (также в соответствии с описанием, приведённом в стандарте) (листинг 2). Листинг 2: Изменение окна в протоколе TCP // Fast Recovery when ( pre ( state ) == TCPState. slow Start or pre ( state ) == TCPState. congest Avoid ) and state == TCPState. fast Recov then reinit ( retr_ timer, o. RTT ); reinit ( ssth, w / 2) ; reinit ( w, w / 2) ; end when ; // Timeout when ( pre ( state ) == TCPState. slow Start or pre ( state ) == TCPState. congest Avoid ) and state == TCPState. time Out then reinit ( retr_ timer, RTO ); reinit ( ssth, w / 2) ; reinit ( w, 1) ; end when ; Таким образом, мы продемонстрировали возможности языка Modelica по моделированию дискретных моделей. Фактически, дословно следуя тексту стандарта, описывающего функционирование протокола TCP, мы получили имитационную модель протокола. 4. Численное моделирование системы с управлением средствами языка Modelica В работах [23, 24] в формализме стохастических дифференциальных уравнений с пуассоновским процессом построена модель взаимодействия входящего TCP-потока и маршрутизатора, обрабатывающего поток по алгоритму типа RED. Модель имеет вид системы обыкновенных дифференциальных уравнений. Фактически на эту систему накладывается ряд ограничений, которые затрудняют исследование данной модели в рамках непрерывного подхода, однако эти ограничения вполне укладываются в гибридный подход. Математически систему процесса передачи трафика c регулируемой алгоритмом типа RED динамической интенсивностью потока можно представить в виде следующих трёх уравнений: ⎧ ⎪�˙ (�) = 1 (�max - � ) - � (�) � (� - � (�)) �(� - � (�)), ⎪ � (�) ⎪ ⎪ ⎧�(�)� (�) 2 � (� - � (�)) ⎨ ⎪⎨ ⎪ �˙ (�) = � (�) - �, �(�) > 0, (4) ⎪ ⎪ ⎪ ⎪ ⎪ ˆ˙ (︂�(�)� (�) ⎪⎩max � (�) ˆ )︂ - �, 0 , �(�) = 0, ⎩�(�) = �� ��(�) + �� ��(�). В этой системе � (�) обозначает среднее значение размера TCP окна (измеряется в пакетах), через �(�) обозначено среднее значение длины очереди (также измеряется в пакетах), через �ˆ(�) - экспоненциально взвешенное скользящее среднее значение длины очереди. Кроме того, введены параметры системы: � - интенсивность обработки пакетов в очереди маршрутизатора, �(�) - число TCP-сессий, � (�) - время двойного оборота (Round Trip Time, сек). Элемент (�max - � ) является функцией Хэвисайда и ограничивает рост окна (см. листинг 3). function wAdd Листинг 3: Ограничение роста окна input Real wIn ; input Real wmax ; input Real T; output Real wOut ; algorithm wOut := if no Event ( wIn > wmax ) then 0 else 1 / T; end wAdd ; Тогда уравнение для изменения окна запишется в следующем виде (листинг 4). equation Листинг 4: Уравнение для изменения окна der ( w) = wAdd ( w, wmax, T ) w * delay ( w,T ) / (2 * delay ( T,T )) * delay ( p,T ); Оператор der задаёт производную по времени, а оператор delay задаёт запаздывание. При этом заметим, что моделирование запаздывания (особенно функционального) при непрерывном подходе представляет крайне нетривиальную задачу. Алгоритм изменения мгновенной длины очереди представлен в листинге 5. Листинг 5: Алгоритм изменения мгновенной длины очереди algorithm q1 := N * w / T C; qOut := if no Event ( q + q1 > 0) then q1 else q; Тогда дифференциальное уравнение для мгновенной длины очереди имеет крайне простой вид (листинг 6). Листинг 6: Уравнение для изменения мгновенной длины очереди equation der ( q) = qAdd ( pre ( q), w, T, C, N ); Непосредственно за управление по алгоритму RED [1] отвечает функция сброса пакета �, значения которой лежат в интервале [0, 1]: ⎧0, 0 � �ˆ < �min, ⎪ � = ⎪⎨ �ˆ - �min ⎪⎪ max min �max, �min � �ˆ � �max, (5) � - � ⎩1, �ˆ > �max. Как мы видим, функция сброса - кусочная и разрывная. Всё это также затрудняет использование непрерывного подхода. В гибридном подходе функция сброса задаётся единственным атомарным оператором (см. листинг 7). Листинг 7: Функция сброса RED p = if ( q_ avg < thmin * R ) then 0.0 elseif ( q_ avg > thmax * R ) then 1.0 else ( q_ avg thmin * R) * pmax / ( thmax * R thmin * R); Здесь через � обозначен размер буфера, поскольку значения порогов нормированы на единицу. Получившаяся программа компактна и имеет крайне простой вид. В чисто непрерывном подходе результирующая программа была излишне громоздкой. 8 7 6 5 4 3 2 1 0 0 50 100 Результаты вычислений можно представить в виде графиков. Как пример, приведём график поведения мгновенной длины очереди (рис. 2) и соответствующий фазовый портрет (в координатах � и �) (рис. 3) Queue [packet] Window [packet] 300 250 200 150 100 50 0 0 20 40 60 80 100 Time [s] Рис. 2. График мгновенной длины очереди 150 200 250 300 Queue [packet] Рис. 3. Фазовый портрет mbox 5. Заключение Авторы преследовали своей целью продемонстрировать применимость гибридного подхода для задач моделирования сетевых протоколов. Сетевые протоколы обычно описываются на основе дискретно-событийного подхода. Однако использование дискретного подхода при моделировании зачастую приводит к недостаточной масштабируемости модели. В то же время применение непрерывного подхода приводит к излишнему усложнению модели. Причём большое количество ограничений при непрерывном подходе не входят непосредственно в математическое описание модели, а присутствует в виде дополнительного семантического материала. Кроме того, гибридный подход может применяться как при аналитическом, так и при имитационном моделировании. Впрочем, как можно видеть из листингов, дискретный подход в рамках гибридного подхода носит всё-таки подчинённый характер. Поэтому и код для имитационной модели (где превалирует дискретное описание) выглядит более громоздким, чем код для вычислительной модели (где превалирует непрерывный подход, а дискретный подход носит вспомогательный характер). Таким образом, рассмотренный в статье гибридный (непрерывно-дискретный) подход к моделированию представляется нам на данном этапе наиболее адекватным для решения задач моделирования сетевых протоколов. К сожалению, данный подход недостаточно активно применяется исследователями, хотя и реализован в ряде систем компьютерного моделирования.

Об авторах

Анна Мария Юрьевна Апреутесей

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

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

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

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

Анна Васильевна Завозина

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

Email: miphj@rudn.university

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

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

Анна Владиславовна Королькова

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

Email: miphj@rudn.university

доцент, кандидат физико-математических наук, доцент кафедры прикладной информатики и теории вероятностей РУДН

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

Дмитрий Сергеевич Кулябов

Российский университет дружбы народов; Объединённый институт ядерных исследований

Email: miphj@rudn.university

доцент, доктор физико-математических наук, доцент кафедры прикладной информатики и теории вероятностей РУДН

ул. Миклухо-Маклая, д. 6, Москва, Россия, 117198; ул. Жолио-Кюри, д. 6, г. Дубна, Московская область, Россия, 141980

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