Аналитическая модель буферной памяти OpenFlow коммутатора программно управляемой сети SDN

Введение. Программируемые сети SDN и протокол управления сетевыми устройствами OpenFlow создавались для повышения автоматизации управления современными компьютерными сетями и поддержки заданного качества облачных сервисов, то есть для задач, решаемых путем динамического перераспределения сетевых ресурсов между пользователями. Один из основных элементов программно управляемых сетей — коммутатор потоков OpenFlow, а его важнейшая часть — буферная память. Используя внутренний программный конвейер, коммутатор распределяет и балансирует нагрузки между каналами сетевой структуры. Так достигается гибкость централизованного управления ресурсами сети.

Оценка количественных характеристик функционирования сетей включает выявление вероятностно-временных особенностей узлов коммутации. Для этого широко используются методы теории массового обслуживания (ТМО), которые лишь приближенно определяют и моделируют процессы в коммутаторе OpenFlow и его буферной памяти. Это ведет к получению заниженных, не реалистичных характеристик проектируемых сетевых устройств, перегрузке буферной памяти коммутаторов и потере сетевых пакетов. Для устранения проблемы предлагается иной подход к моделированию. Цель представленной работы — создание и исследование аналитической модели буферной памяти OpenFlow коммутатора программно управляемой сети SDN с использованием усовершенствованных методов ТМО. Для достижения цели используется аппарат дискретного преобразования Лапласа-Стилтьеса (ПЛС), учитываются статистические характеристики потоков пакетов и пропускная способность каналов связи при заданной вероятности потерь пакетов. Подобная математическая модель на основе классической ТМО описана в [1], но она не устраняет проблемы, которые возникают из-за приближенного описания сетевых процессов.

В научной литературе предлагаются конструктивные решения для совершенствования элементов сетей передачи данных, что говорит о важности и актуальности решаемой научно-технической задачи. Моделям OpenFlow коммутаторов программно управляемых сетей SDN посвящены работы Рагхава С.С., Баскакова А.Е., Волкова А.С., Филиппова И.А., Никишина К.И., Гурина Е.И., Тихоненко О.М., Горбунова А.В., Лебедева А.В., Самуйлова К.Е., Шалимова И.А. и др. В [2] приводится достаточно полный обзор сетевых решений, основанных главным образом на классической ТМО. Исследуются системы конечной пропускной способности с рекуррентным входным потоком, марковским процессом обслуживания и накопителями бесконечного объема. Методы моделирования базируются на замене рекуррентных потоков заявок простейшими. Зависимость объема требований от времени обслуживания предполагается заданной, или ею пренебрегают. Вероятность потерь пакетов принимается пренебрежимо малой. В подобных моделях, как правило, используется не всегда верное утверждение, что потоки пакетов теряются, если занят весь объем буферной памяти. Предполагается также неограниченный суммарный объем памяти и вполне определенный характер связи между объемом сообщений и временем обслуживания. В большинстве публикаций отсутствуют конечные выражения, позволяющие анализировать качество обслуживания коммутатора с учетом особенностей распределения буферной памяти, показателями потерь и нагрузки. В этих случаях авторы пользуются численными методами готовых программных пакетов.

Научная новизна представленного исследования заключается в усовершенствовании классических методов ТМО, обеспечивающих исследование систем с произвольно распределенными функциями поступления и обслуживания заявок. Практическая значимость результатов работы подтверждается двумя факторами. Во-первых, создается аналитическая модель буферной памяти коммутатора OpenFlow сети SDN, обеспечивающая достаточно точное ее исследование. Во-вторых, открывается возможность выбора альтернативных вариантов построения на этапе проектирования. Результативность предлагаемой модели оценивается при моделировании. Полученные показатели качества позволяют оценить эффективность коммутатора OpenFlow сети SDN.

Материалы и методы. Входной поток пакетов сети SDN поступает на коммутатор OpenFlow, который извлекает метаданные, проверяет их на соответствие записям в адресных таблицах и формирует направление передачи. Сетевая операционная система контроллера SDN распределяет пакеты по потокам, которые конфигурирует классификатор OpenFlow. Коммутатор OpenFlow объединяет множество таблиц потоков, управляемых центральным контроллером с помощью инструкций и пересылки пакетов. Контроллер SDN периодически меняет свои записи о структуре сети, нагрузке, используемых ресурсах, резерве. В соответствии с этим он устанавливает правила пересылки для всех поступивших потоков, последовательно распределяет их по выходным OpenFlow портам коммутатора, устанавливает новые параметры действий и выполняет потоковую рассылку или передачу обратно в сеть. При этом задействуется программный конвейер коммутатора в виде последовательных таблиц потоков.

Пакеты, не идентифицированные в таблицах потоков, передаются на другой порт коммутатора или пересылаются контроллеру для изменения полей. SDN-контроллер формирует выходные порты коммутатора, адресные таблицы, а также классификаторы потоков данных [3].

Вопросам управления сетевыми устройствами уделяется большое внимание, есть готовые конструктивные решения. Несмотря на это, создаются новые эффективные методы и протоколы управления сетевой нагрузкой, постоянно дорабатываются протоколы управления сетями. Небольшой срок опытной эксплуатации сетей SDN и отсутствие систематизированных результатов тестирования коммутационного оборудования на платформе OpenFlow вызывают необходимость дальнейших исследований с применением аналитических и имитационных моделей.

Таким образом, структурную схему коммутатора можно представить в виде системы массового обслуживания (СМО) c ограниченным объемом памяти. На ее вход поступает поток пакетов с произвольными законами распределения числа и объемов требований. Режим работы такой системы будет стационарным, если среднее число требований, поступающих за единицу времени, не превышает максимально возможной скорости их обслуживания. При этом одна из важнейших задач — определение средних значений и дисперсии общего объема буферной памяти коммутатора, а также объемов памяти для построения таблиц потоков [4]. Предположим, что на входе высокопроизводительного центрального управляющего сервера нет очередей потоков пакетов. В этом случае функционирование коммутатора в стационарном режиме можно описать аппаратом систем массового обслуживания с преобразованиями Лапласа-Стилтьеса. Распределение и обработка данных с помощью программного конвейера моделируется как многофазный случайный процесс [5].

Усовершенствованный метод ТМО, используемый в данной работе, позволяет формировать модели многих реальных систем, в том числе коммутационных. Можно обоснованно предположить, что есть стационарные характеристики подобных систем, и параметры входного потока пакетов не влияют на очередность и время его обслуживания. Считаем также, что каждый поток характеризуется некоторым случайным количеством пакетов, т.е. его объем принимает только положительные дискретные значения, и это с большой долей вероятности отражает реальную ситуацию.

Конвейер адресации коммутатора состоит из одной или нескольких последовательно соединенных таблиц адресации. Входной сетевой трафик, описываемый произвольным законом распределения, поступает на конвейер и последовательно обрабатывается k таблицами адресации.

Предполагается, что время обработки запросов каждой таблицей случайно и подчиняется экспоненциальному закону. Сумма времен всех пройденных этапов обработки формирует итоговое распределение времени обслуживания (распределение Эрланга k-го порядка). Известно, что поток Эрланга k-го порядка с параметрами (µ, r) можно представить в виде суммы r случайных потоков с параметрами μ_i, а характеристики рассматриваемой системы можно получить из характеристик составляющих ее элементов [6]. Тогда стационарные вероятности p(i₁,…, i_r) рассматриваемой системы:

Структура набора записей коммутатора приведена на рис. 1.

Упрощенная структура OpenFlow коммутатора представлена на рис. 2.

Временные интервалы между пакетами случайны. Входной поток является марковским, но время его обслуживания не подчиняется экспоненциальному распределению, т.е. анализируемый процесс обработки входных потоков содержит марковскую составляющую. Значит, данную систему можно исследовать с помощью математического аппарата полумарковских процессов [7], а функция распределения временных интервалов нахождения процесса в состоянии i будет произвольно распределенной случайной величиной [8]. Такому же распределению подчиняются промежутки между моментами окончания обслуживания и очередными моментами поступления запросов на обслуживание. Считаем также, что случайные потоки пакетов, определяемые функцией распределения Эрланга, поступают по m каналам с интенсивностями

Для системы M/G/1/n преобразование Лапласа-Стилтьеса функции распределения объема обслуживаемого пакета R(x):

Здесь g_i > 0 — время задержки приема пакета по i-му каналу, f — параметр распределения, s — комплексный параметр преобразования Лапласа-Стилтьеса. В данном выражении он выполняет функцию множителя в показателе экспоненты и позволяет находить моменты распределения случайной величины любой степени.

Среднее значение и дисперсия:

где ρ_i — загрузка входного канала,

Тогда ПЛС объема потока пакетов:

Средние значения и дисперсия:

Считаем, что вероятность потерь потока пакетов [9]:

где

L(x) = 1 – e^–fx — функция распределения (ФР) объема потока пакетов;

D(x) = p(δ < x) — ФР суммарного объема потока пакетов δ.

Моменты ФР R(x):

где φ₁ = 1/f — средний объем потока пакетов; δ₁, δ₂ — моменты суммарного объема потока пакетов.

Нахождение явного вида ФР D(x) не представляется возможным. В [10] показано, что при проведении расчетов эту функцию можно достаточно точно аппроксимировать выражением:

Здесь

 — неполная гамма-функция;

p₀ — вероятность отсутствия запросов на обслуживание; Γ(p) = γ(p, ∞) — гамма-функция; p и g — параметры, определяемые из условия равенства соответствующих моментов объема памяти коммутатора:

Числовые значения ФР D(x) получены путем имитационного моделирования с использованием стандартных численных методов, которые позволили свести решение задачи к выполнению конечного количества арифметических действий. Итоги имитационного моделирования практически совпадают с результатами аналитического моделирования, описанного в данной статье, что говорит о достоверности разработанной модели.

При формировании сетевых потоков выполняются перечисленные ниже действия [11].

1. Идентификация потока пакетов трафика.
2. Определение принадлежности пакета к формируемому потоку.
3. Формирование сетевых потоков пакетов или передача неидентифицированного пакета управляющему контроллеру.

Функция распределения времени обслуживания входного потока пакетов B(t) = p + (1 – p)(1 – e^pt), а ее ПЛС [12]:

Среднее значение времени обслуживания:

Если загрузка системы ρ = aβ₁ = a(1 – p)/p, то ПЛС времени ожидания обслуживания:

Тогда среднее значение времени ожидания:

Изображение имеет вид рациональной дроби (A_n(p))/(B_n(p)). P₁, P₂, …, P_n — корни кратности r₁, r₂, …, r_n, причем r₁ + r₂ + ⋯ + r_n = m и

.

Значит, оригинал можно найти по формуле [13]:

При простых корнях знаменателя P₁, P₂,…, P_n:

Обращение ПЛС функции W(q) определяется соотношением:

Функция распределения случайной величины V имеет вид:

Для случая

среднее значение стационарного времени ожидания:

Среднее значение стационарного времени обслуживания:

Данные случайные величины аппроксимированы ФР

.

Здесь

,

Γ(p) = γ(p,∞),

p₀ — стационарная вероятность отсутствия требований:

Очевидно, что фазы передачи выходящих из коммутатора сетевых пакетов можно описать графом (рис. 3) [14].

Из [15] известна вероятность нахождения системы M/M/m/n в состоянии p_k:

Здесь ρ = λ/μ — нагрузка.

Соответственно, вероятность состояния p_m+s:

Тогда интенсивность выходного потока:

Согласно [16], с учетом потерянных пакетов интенсивность выходного потока:

Время пребывания пакетов в системе:

Время ожидания пакетов в очереди:

Время обслуживания:

Представленные выражения дают возможность получить основные характеристики коммутатора OpenFlow. В этом случае принимаются во внимание обработка и управление потоками пакетов, а также взаимодействие с центральным сетевым контроллером. При этом буферная память считается общим, динамически распределяемым ресурсом и определяется с учетом ограничений на долю потерянных пакетов при заданной вероятности потерь. Допустимые ограничения модели:

• произвольное распределение зависимости между объемом потоков данных и временем их обслуживания;
• предполагаемая дискретность распределения структуры информационных потоков.

Результаты исследования. Итак, в рамках данного исследования разработана модель коммутатора OpenFlow для расчета и оценки его буферной памяти. С использованием математического аппарата полумарковских процессов и преобразований Лапласа-Стилтьеса задаются:

• вероятность потери потоков пакетов;
• их статистические характеристики;
• пропускная способность вычислительных устройств.

Обработка потоков пакетов состоит из множества независимых последовательных фаз, и время обслуживания на них распределено экспоненциально. Поэтому в основу предлагаемой модели положена процедура многофазного обслуживания, при которой время обслуживания определяется распределением Эрланга n-го порядка, а моменты функций распределения находятся преобразованием Лапласа-Стилтьеса.

В таблицах 1, 2 представлены результаты аналитического моделирования объема буферной памяти коммутатора и зависимости среднего времени ожидания обслуживания от загрузки. В данном случае она увеличивается от 0,1 до 0,9. Объем памяти коммутатора измеряется числом средних объемов входных потоков пакетов.

Результаты имитационного моделирования получены при использовании самоподобного сетевого трафика, описываемого распределением Парето с параметром 1,5. Если загрузка системы менее 50 %, то полученные при имитационном моделировании характеристики для системы P/G/1 незначительно отклоняются от средних показателей, полученных при аналитическом моделировании. При загрузке более 50 % значения увеличиваются в нескольких раз. Показатели резко возрастают с загрузкой коммутатора до 70 % и кратно увеличиваются, если этот уровень превышается.

Обсуждение. Результаты данной научной работы получены при условии независимости функции распределения интенсивности потока пакетов от обрабатывающей их фазы, а также постоянного характера объема потока пакетов. Только в этом случае будет справедлив итог преобразования Лапласа-Стилтьеса для объема памяти коммутатора.

Основной недостаток результатов заключается в том, что полученные оценки достоверны только на уровне частных распределений. Модель сетевого коммутатора OpenFlow построена в предположении использования общей динамически распределяемой буферной памяти, а рассматриваемые фазы обработки потоков заявок считаются независимыми, поэтому итоги исследования можно использовать только при равенстве времени:

• ввода потока пакетов в память коммутатора;
• его вывода в канал связи.

Такие условия следует считать допустимыми, учитывая возможности современных средств обработки и передачи данных.

Результаты моделирования, приведенные в таблицах 1 и 2, получены с учетом заданных характеристик потерь и текущей сетевой загрузки. При невысокой загрузке очереди не переполняются, пакеты не теряются, сохраняются линейные зависимости. При средней, а тем более высокой загрузке процессы обработки сетевых потоков пакетов описываются уже нелинейными зависимостями. Причина расхождения результатов аналитического и имитационного моделирования — взрывообразный характер самоподобного сетевого трафика и достаточно приближенный характер его описания распределением Парето.

Очевидно, что целесообразность применения предложенной модели определяется текущей загруженностью коммутатора. Данную модель можно использовать в проектировании сетевых элементов программно конфигурируемых сетей для анализа их устойчивости при различных информационных воздействиях.

Итоги представленного исследования при загрузке до 50 % практически совпадают с результатами, полученными в рамках классических методов теории массового обслуживания [5]. Критические потери входных потоков пакетов начинаются при загрузке коммутатора 50 %. Дальнейшее увеличение загрузки не предусматривается, следовательно, не оцениваются ни поведение, ни устойчивость системы при более высокой загрузке.

Уровень работоспособности предложенной модели соответствует известным результатам имитационного моделирования с использованием самоподобного сетевого трафика, описываемым распределением Парето.

Заключение

1. Построена аналитическая модель буферной памяти OpenFlow коммутатора программно управляемой сети SDN, предназначенная для определения:

• средних значений и дисперсии общего объема буферной памяти коммутатора;
• объемов памяти для построения таблиц потоков адресации.

2. Получены аналитические выражения для определения следующих характеристик качества обслуживания коммутатора программно конфигурируемой сети:

• интенсивность выходного потока пакетов с учетом потерь;
• время пребывания пакетов в системе;
• время ожидания пакетов в очереди;
• время обслуживания;
• зависимость объема буферной памяти и среднего времени ожидания обслуживания от загрузки.

3. Работоспособность модели подтвердило сравнение результатов аналитического и имитационного моделирования при изменении загрузки коммутатора от 0,1 до 0,9.

4. Модель позволяет без использования физического оборудования тестировать сети SDN для обоснования параметров коммутатора с учетом его окружения.

Предполагается, что следующая статья, посвященная разработке модели функционирования коммутатора SDN, будет учитывать потоки заявок как из внешней сети, так и от управляющего контроллера (сервера).