Модели и алгоритмы обеспечения доступности в корпоративной программно-определяемой телекоммуникационной сети

Во введении обосновывается актуальность темы диссертации. Формули-
руются цель и задачи исследований.
В главе 1 анализируются методы обеспечения доступности в КТС, уточ-
няются задачи исследования. КТС включает несколько подсетей, выделяемых для изоляции трафика, сетевое оборудование (коммутаторы, маршрутизаторы, межсетевые экраны, точки беспроводного доступа), VPN каналы, канал до- ступа в Интернет, сервера, рабочие станции, включая мобильные устройства. Топология (схема связей) такой сети неизменяемая. Если применяются техно- логии SDN, то эта схема взаимодействия виртуализированных устройств будет постоянно перестраиваться, сохраняя при этом функции сегментирования и
туннелирования.
Математическую модель КПТС представим в виде графа: G = {U, V}, где
U = { 1, 2, … , } – множество узлов (виртуализированных на уровне South- bound сетевых устройств SDN, например, Open vSwitch), V = { } – множество
ребер – линий связи (ЛС) ε {1,0 }, , = 1, , . Веса ребер – показатели доступ-
ностиЛС(узлаui относительноузлаuj)0≤ ≤1, =1.Еслиiиjнесо- единены друг с другом ( = 0), то в связной сети имеется, как минимум, один канал связи (КС) между uj и ui.
Под доступностью сети ( ) будем понимать вероятность того, что при заданной топологии сети определенные характеристики (сетевая связность, пропускная способность и т.д.) будут поддерживаться на заданном уровне. По- казатель доступности КС, образованного между двумя узлами и, представляю- щего собой последовательное соединение ЛС узлов от истока к стоку опреде-
лим выражением КС = ∏ , где – показатели доступности линий ε[ , ]
связи на пути от до . Если имеется несколько КС от до , то опре-
делим усреднением: = ∑ εZ(∏ ε[ , ] )/Z , где – КС с номером из
множества Z каналов; – показатели доступностей линий связи в канале от i –го до – го узла.
Определим диапазон показателя доступности выполняемой задачи с за- данным качеством А( ) ≤ ( ) ≤ А( ) , здесь А( ) – минимально допустимый показатель доступности, А( ) – максимально возможный для данной сети. Введем показатель идеальной доступности сети ∗( ), когда все КС доступны с вероятностью 1.
Алгоритм определения интегрального показателя доступности сети
Шаг 1. Строим матрицу смежности =‖ ‖, , =1.. ,где = 1,если = 1,иначе = 0.
Шаг 2. С помощью модифицированного алгоритма Флойда-Уоршелла находим множества каналов связи между каждыми двумя узлами uj и ui:
= { , , … , }. Здесь – мощности множеств . 12
Шаг 3. Вычислим показатели доступности всех КС между каждыми двумя
uiиuj.Получиммножествапоказателей: ( )={ ( ), ( ),…, ( )}. 1 2
Шаг 4. Найдем соответственно минимальный ̂( ) , и максимальный ̂( ) показатели доступности среди всех пар узлов.
Шаг 5. При помощи способа, предложенного Ю.М. Монаховым и др., ос- нованном на вычислении расстояния Колмогорова для двух функций, опреде- ляем интегральный показатель доступности (ИПД) сети в виде ( ) = 1( ̂( ) , ∗( )), ( ) = 2( ̂( ) , ∗( )), где f1 и f2 – функционалы, используемые в обозначенном подходе. Конец алгоритма.
Глава 2 содержит разработку алгоритмов оптимизации интегрального показателя доступности КПТС. Описывается порядок и условия проведенных экспериментов и анализ результатов.
Представим КПТС как систему. Элементами системы являются маршру- тизирующее и коммутирующее оборудование и программируемые связи между ними. Функция системы – множество алгоритмов построения связей между этими элементами, которые зависят от решаемой задачи и состояния внешней среды. Состоянием внешней среды будем определять текущие значения пока- зателей доступности элементов КПТС. Рассмотрим процесс реализации задачи средствами КПТС. Пусть в начальный момент времени имеем структуру связей (топологию), которая была сформирована вручную администратором КПТС или была «запомнена» по окончанию предыдущего решения данной задачи
( 0). В процессе выполнения текущей задачи меняются значения , , = 1,
за счет динамической маршрутизации (изменяемой маршрутной матрицы), и, соответственно, структуры связей. Можно представить, что за время решения задачи топология сети изменяется по закону ( 0, 1…, , … , ), где принад- лежит полному множеству структур (  ). Кроме того, обладает обяза- тельным свойством связности, т.е. всегда имеются пути между элементами, за- действованными в данный момент.
Постановка задачи: Требуется на каждом k-м шаге выполнения задачи синтезировать такую топологию  , при которой ИПД сети элементов, участвующих в ее выполнении, принимает максимальное значение
Для повышения доступности сети предлагается два подхода:
(
зировать топологию КПТС для достижения максимума ИПД; (2) повысить по-
1) оптими-
казатель доступности каналов связи
управления потоком.

за счет применения нового алгоритма


( ) → , при этом должно быть обязательно обеспечен минимально до-
пустимый показатель доступности.
Введем ограничение. Общее количество связей в не должно превы-
шать количество связей в 0. Данное ограничение обосновывается следующим: можно предположить, что добавление связей вплоть до получения полносвяз- ного графа повысит ( ), что подтверждается расчетом и экспериментами, од- нако здесь не учитывается резкое возрастание нагрузки на контроллер, ограни- чения памяти коммутаторов TCAM, и прочие эффекты, оказывающие негатив- ное влияние на доступность каналов связи. Кроме того, согласно инструкциям фирм-разработчиков максимальное количество связей ограничивается.
Алгоритм оптимизации топологии КПТС по критерию максимума интегрального показателя доступности
Дано 0 – начальная топология, – количество элементов, – количе- ство связей между ними на начальный период выполнения задачи.
Шаг 1. = 0.
Шаг 2. Получить текущие значения ( 0).
Шаг 3. По алгоритму определения ИПД сети рассчитать верхнее и нижнее граничные значения ИПД начальной топологии ( ( 0)) и А( ( 0)) .
Шаг 4. Получить остовное дерево графа ( 0) последовательно исклю- чая связи из 0. Если таких деревьев несколько, то запомнить структуру с максимальным ИПД сети, при этом минимальный ИПД должен быть не меньше, чем А( ( 0)) , количество связей . Положить = ( ( )).
Шаг 5. Для потенциально возможных несуществующих ( − ) связей выполнить: последовательно добавлять в связи между каждыми двумя не связанными друг с другом элементами, получая новые структуры
(1), (2),…, каждый раз проверяя значение ИПД. Запомнить структуру
( ) , при которой текущее значение ( ( ) ) максимально, при этом мини- мальный ИПД должен быть не меньше, чем А( ( 0)) .
Шаг 6. = + 1. Если задача не выполнена, то = ( ), = ( ( )), перейти к шагу 2, иначе конец алгоритма.
Для экспериментального исследования разработанного алгоритма создан стенд в среде Mininet, позволяющий формировать произвольные топологии
SDN, осуществлять маршрутизацию потоков трафика на базе контроллера ONOS, а также производить расчет показателей доступности.
На рисунке 1 представлена схема КПТС, смоделированной на стенде. Данная схема состоит следующих элементов: OpenFlow контроллер (ONOS), 100 оконечных устройств пользователей (PC 1-100), 15 коммутаторов (as1-6, bs1-5, cs1-4), 3 маршрутизатора (ar1-2, br1-2, cr1-2) и линий связи между ними.
Рис. 1. Модель КПТС в среде Mininet.
Создано программное обеспечение на языке Java, позволяющее реализо- вывать все шаги разработанного алгоритма. Эксперименты заключались в сле- дующем: с помощью Mininet генерировались топологии сети как подмножество узлов и связей, приведенных на рис. 1, для решения выбранной задачи (решае- мая задача – типовые приложения для работы с электронным документооборо- том на предприятии, охватывающая взаимодействие не менее 50% оконечных устройств пользователей). Запускаются процессы обмена сообщениями между узлами сети, имитирующие действующую сетевую нагрузку. С помощью раз- работанного скрипта определяются время отклика узлов относительно друг друга. На базе усреднений данных процессов определяются показатели средней доступности узлов (по 250 раз время отклика сравнивается с директивным). Та- ким образом формируется текущая матрица доступности. Если решение задачи требует нескольких этапов, то процедура эксперимента повторяется.
Далее реализуются процедуры алгоритма оптимизации топологии КПТС
по критерию максимума интегрального показателя доступности. Шаг за шагом изменяется топология, меняются ИПД А( ( )) и ( ( )) . Результи- рующая топология с максимальными интегральными показателями доступно- сти (оптимальная топология) для одного из экспериментов приведена на рис. 2 (здесь а) – ( ( 0)) = 0,71, А( ( 0)) = 0,7; б) – ( ( )) = 0,83, А( ( )) = 0,71).
а) б)
Рис. 2. Графы начальной и оптимальной топологий.
Эксперименты проводились с варьированием начальной топологии и каж- дый раз находилась оптимальная топология. ИПД зависел в основном от теку- щей нагрузки сети и варьировался в диапазоне от 0,6 до 0,8, при этом выигрыш
А(G)m
0,92
0,87
0,82
0,77
0,72
0,67 А_макс_2 0,62
А_мин_2
А_мин_1
0,57 0,52 0,47
А_макс_1
Х
Рис. 3. График зависимости доступности сети от коли- чества связей между устройствами.
по сравнению с исходным достигал 10-15%. Исследо- валась зависимость выиг- рыша интегрального пока- зателя доступности от коли- чества связей между устройствами. Результаты исследования представлены на рис. 3. Наибольший эф- фект разработанный алго- ритм показывает, когда при решении задачи задейство- вано много узлов.
20 29 38 47 56 65 74 83 92
101 110 119 128 137 146 155 164 173 182 191 200 209

В главе 3 предлагается метод повышения доступности канала связи КПТС. Предлагается алгоритм планирования очередей передачи данных на ос- нове приоритизации, который позволяет оптимизировать использование про- пускной способности.
Одним из эффективных способов повышения доступности в КПТС явля- ется внедрение технологии QoS. Использование алгоритмов приоритизации и контроля трафика (ПКТ) позволяет отделять трафик функционирующих серви- сов из общего потока и обеспечивать гарантированную полосу пропускания для них. Конфигурирование данных алгоритмов производится на основании выде- ления части КС для различных типов трафика. Однако, такое распределение не учитывает особенности проходящего трафика и не гарантирует обеспечение доступности трафика, чувствительного к задержкам канала. Тем самым, до- ступность сервиса понижается, что ведет к потенциальной угрозе безопасности системы. Данную проблему возможно решить путем разработки алгоритмов ПКТ, позволяющих оптимально распределять трафик, проходящий через КС, с целью повышения доступности определенных типов трафика.
Выявление параметров оптимизации. Исследования показывают прямую зависимость отклика сервиса от используемого алгоритма планирования очере- дей. Популярностью пользуется иерархический алгоритм «текущего ведра» (Hierarchical Token Bucket – HTB), подразумевающий разделение полосы про- пускания для определенных типов потока в отдельные классы, каждый из ко- торых имеет свою собственную полосу пропускания. Алгоритм выстраивает данные классы в виде дерева.
На экспериментальной установке (рис. 4) было проведено исследование типовой конфигурации HTB в различных режимах нагрузки. Целью экспери- мента являлось определение ключевых аспектов, влияющих на обеспечение низ- кой задержки передачи пакетов при различной интенсивности входящего по- тока. Исходя из результатов анализа, были предложены следующие направления оптимизации параметров, влияющих на задержку передачи пакетов: контроль интенсивности входящего потока, динамическое изменение пропускной способ- ности канала относительно входящей интенсивности, оптимизация предоставле- ния полосы для классов трафика относительно входящей интенсивности.
14
Рис. 4. Схема экспериментальной КСПД
Входные данные алгоритма. Под- ход подразумевает классификацию сете- вого трафика по определенным призна- кам, таким как: IP-адрес узла назначения, узла источника, используемый порт узла назначения, узла источника, реализуе- мый протокол передачи данных. Каж- дому классу трафика определяется прио- ритет в соответствии с соглашением о ка- честве обслуживания (SLA). Для каждого класса определяется директивное время
задержки в очереди на ожидание передачи сетевым оборудованием. Каждый класс имеет свою очередь накопления пакетов. Выпуск пакетов в передающую очередь осуществляется со скоростью, рассчитанной на основании директивного времени и алгоритма планирования использования пропускной способности.
Опишем это множествами: классов трафика = { 1 , … , }, где b – ко- личество классов, соответственно задается множество приоритетов класса: = { 0 , … , −1 }, чем меньше значение , тем выше приоритет; скоростей потока пакетов для каждого класса Sp= { 1, … , }, ∑ =1 ≤ _ , где _ – максимальная пропускная способность интерфейса; множеством ди- рективного времени обработки пакетов для каждого класса обр= { обр1,…, обр }, соответственно интенсивности обслуживания пакетов = 1/ обр ; допустимых задержек в очередях для классов Del= { 1, … , }; ин- тенсивностей входящего трафика пакетов λ= { 1, … , }.
Алгоритм определяет одну очередь передачи для пакетов различных клас- сов. Из очередей классов пакеты выходят с интенсивностью меньшей или равной . Пакеты попадают в очередь последовательно в соответствии с приоритетами.
Алгоритм планирования очередей передачи данных
Шаг 1. Ввод исходных данных: ={ 1,…, }, ={ 0,…, −1}, обр = { обр1, … , обр }, _ , _ , MTU, Sp = { 1, … , }, = { 1,…, }.
Шаг 2. Поставить соответствие номеров классов приоритетам – 0 = 0,…, −1 = −1.
Шаг 3. Если условие ∑ −1 ≤ _ выполняется, то переход к
шагу 4, иначе устанавливаем текущее значение времени обработки пакета для каждого класса в минимально допустимое время обработки: ∗ = _ , = 0, … , ( − 1).
Шаг 4. Определяем суммарное количество токенов, которое в дальней- шем будем распределять по классам – = _ /( × 8).
Далее производится распределение токенов по классам (полосы пропус- кания выпускающей очереди) таким образом, что более приоритетный класс забирает 2/3 доступных токенов (полосы пропускания), каждый следующий по приоритету класс занимает 2/3 полосы оставшейся после предыдущего по при- оритету класса и так далее до последнего класса, который занимает оставшуюся полосу. = 0
Шаг 5. Количество токенов для -го класса, (. ) − целая часть. = ( ×23)+1,если ( ×23)
> ( × 23) , × 23 , если ( × 23) = × 23 .
Шаг 6. Время обработки пакетов -го класса ∗ = (8 × )/( _ × ).
Шаг 7. Если ∗ ≤ обр (меньше директивного), то ∗ =1/ ∗; = + 1; Если < (остались классы), то переход к шагу 5, иначе если = 0 (не остались токены), то конец алгоритма; иначе конец алгоритма. иначе если ∗ ≥ _ , то = + 1, = − 1, если = 0 (не остались токены), то конец алгоритма; иначе переход к шагу 6; иначе (токенов для -го класса слишком много) = −1, = +1,переходкшагу6; Если интенсивность входного потока в более приоритетном классе ниже выходной пороговой интенсивности, то следующий по приоритету класс может произвести повышение пороговой выходной интенсивности (при сохранении ∑ =1 ≤ _ ). Право повышения пороговой выходной интенсивности переходит ниже стоящим по приоритету классам. =0 Если интенсивность потока пакетов больше пороговой интенсивности потока, то пакеты начинают отбрасываться для уравнивания интенсивности по- тока до пороговой интенсивности. Повышение или понижении интенсивности пакетов определяется в результате работы алгоритма планирования использо- вания пропускной способности посредством перераспределения токенов HTB. Алгоритм поддержки низкоприоритетных сервисов Шаг 1. Ввод: , , обр, _ , _ , MTU, Sp , λ. Шаг 2. 0 = 0, ... , −1 = −1. Шаг 3. Если ∑ −1 ≤ _ , то переход к шагу 4, иначе ∗ = =0 _ , = 0, ... , ( − 1). Шаг 4. = _ /( × 8). Шаг 5. = × 2/3 Шаг 6. ∗ = (8 × )/( _ × ). Шаг7.Если ∗ ≤ обр ,то ∗ =1/ ∗; = +1;если < ,то-кшагу5, иначе если = 0, то конец алгоритма; иначе = 0, переход к шагу 8; иначе если ∗ ≥ _ , то = + 1, = − 1, если = 0, то конец алгоритма; иначе переход к шагу 6; иначе = − 1, = + 1, переход к шагу 6; Шаг 8. Если > ∗ (Проверка соответствия интенсивности обслужива- ния интенсивности входящего потока пакетов, т.е. имеется возможность увели- чить полосу передачи для -го класса), то = + 1, = − 1, пе- реход к шагу 6; иначе = + 1; если < (остались классы), то переход к шагу 8, иначе конец алгоритма. Для проверки эффективности разработанных алгоритмов было произве- дено имитационное моделирование их работы в среде AnyLogic в сравнении с работой алгоритма HTB в типовой конфигурации. Состав моделируемой си- стемы (рис. 5): очереди передачи пакетов с приоритетами 0 и 1; очередь пере- дачи пакетов в среду передачи сигнала; планировщик распределения использо- вания очереди передачи пакетов в среду для очередей с приоритетами. Задава- лись следующие ограничения: интенсивность пакетов в очередь передачи паке- тов в среду передачи не может превышать значение max_rate; время обработки пакетов в очереди передачи пакетов в среду передачи всегда составляет min_de- lay; буфер очередей с приоритетами ограничен значением, равным 100 пакетам. В рамках тестирова- ния разработанного алго- ритма было произведено сравнение задержек пере- дачи пакетов каждой оче- реди при одинаковых нагрузках на канал оче- реди классов. Проводи- лось 5 тестовых съемов за- держки передачи пакетов. Режимы тестирования представлены в таблице 1. Рис. 5. Схема имитационной модели в AnyLogic Таблица 1. Режимы тестирования моделей алгоритмов Режим 1 2 3 4 Интенсивность очереди 1 (пакет/мс) 0,48 0,48 20,825 Интенсивность очереди 2 (пакет/мс) Количество замеров 0,857 180 0,857 180 100 180 62,4 180 Результат сравнительного тестирования позволяет сделать вывод, что разработанный алгоритм планирования очередей передачи данных показывает более низкие суммарные значения задержки для различных классов трафика, тем самым обеспечивая доступность сервисов в обоих классах. Соответ- ственно, он позволяет оптимизировать использование пропускной способности и обеспечивать минимально возможную задержку для приоритетных классов. На рис. 6, а изображен график работы алгоритмов в режиме 1. При низкой интенсивности входящего потока оба алгоритма обеспечивают низкую за- держку обработки пакетов. Однако для низкоприоритетной очереди HTB за- держка выше приоритетного класса, это обусловлено последовательностью права передачи пакетов на основании приоритета. На рис. 6, б представлен гра- фик работы алгоритмов в режиме 2. HTB произвел выделение полосы для при- оритетного класса и тем самым занял большую часть ресурсов сети, поэтому задержка во втором классе начала расти. Разработанный алгоритм в свою оче- редь определил, что интенсивность потока низкоприоритетного класса низкая, тем самым можно обеспечивать низкую задержку для обоих классов, оставаясь в директивном времени. б) Рис. 6. Графики работы алгоритмов в режимах 1 (а) и 2 (б) 1 — очередь с приоритетом 0 (модификация НТВ); 2 — очередь с приоритетом 1 (модификация НТВ); 3 — очередь с приоритетом 0 (НТВ); 4 — очередь с приоритетом 1 (НТВ). а) б) Рис. 7. Результаты тестирования моделей в режимах 3 (а) и 4 (б) 1 — очередь с приорите- том 0 (модификация НТВ); 2 — очередь с приоритетом 1 (модификация НТВ); 3 — очередь с приоритетом 0 (НТВ); 4 — очередь с приоритетом 1 (НТВ). На рис. 7, а представлен график работы алгоритмов в режиме 3. HTB определил низкую активность высокоприоритетного класса и позволяет низ- а) коприоритетному классу использовать больше полосы. Разработанный алго- ритм, в свою очередь, определил необходимое количество полосы для высоко- приоритетного класса, чтобы выдавать пакеты с минимальной задержкой, а оставшуюся часть определил для низкоприоритетного. На рис. 7, б приведен график работы алгоритмов в режиме 4. Нагрузка на систему равняется 1, то есть это предел обработки пакетов без потерь. HTB сохраняет заданную полосу для высокоприоритетного класса, не снижая его задержки, притом задержка низ- коприоритетного класса сильно возросла. Разработанный алгоритм производит расчет оптимального распределе- ния полосы в пределах нагрузки на систему таким образом, чтобы обеспечить среднюю минимальную задержку для обоих классов. Но поскольку классы имеют разные приоритеты, задержка для высокоприоритетного класса опреде- ляется ниже. К тому же, интенсивность потока заявок высокоприоритетного класса ниже, чем у низкоприоритетного, и приоритетный класс получает 100% необходимой полосы, а низкоприоритетный только ту часть, которая осталась. Поэтому мы наблюдаем возрастание задержки для низкоприоритетного класса. Основные результаты диссертационного исследования: 1. Проанализированы существующие решения задачи повышения дос- тупности КПТС и ее компонентов, а также методики оценки показателей дос- тупности. Выявлены ограничения, препятствующие достижению высокой дос- тупности. Сформулирована задача оптимизации доступности при существую- щих ограничениях по вычислительной мощности контроллеров, ёмкости па- мяти и буфера для управления множеством виртуализированных узлов и мно- жеством ЛС. Обоснована методика оценки показателя доступности сети и КС. 2. Создан экспериментальный стенд в среде Mininet, позволяющий фор- мировать произвольные топологии SDN, осуществлять маршрутизацию пото- ков трафика, а также производить расчет показателей доступности. Экспери- менты позволили выявить существенные факторы воздействия на топологию в SDN с высокой доступностью. Выявлена зависимость влияния связей между устройствами и количеством устройств в сетевой топологии на ИПД сети. 3. Разработан алгоритм оптимизации топологии КПТС, основанный на последовательной реконфигурации топологии сетевых средств коммутации и маршрутизации по критерию максимума ИПД, что позволяет подстраивать то- пологию КПТС под изменяющиеся внешние условия и решаемую задачу. Экс- периментальные исследования показали: оптимальная топология находилась каждый раз при многократном изменении начальной топологии; ИПД зависел в основном от текущей нагрузки сети и варьировался в диапазоне от 0,6 до 0,8, при этом выигрыш по сравнению с исходной топологией достигал 15%, а в ряде случаев до 22%. Наибольший эффект разработанный алгоритм показывает, ко- гда при решении задачи задействовано много узлов. 4. Разработан алгоритм планирования очередей передачи данных на ос- нове модификации известного подхода «маркерное ведро» (HTB). Алгоритм позволяет обеспечивать минимально возможную задержку для приоритетных классов поддерживаемых сервисов, оптимизируя использование пропускной способности. Выявлены факторы, влияющие на задержку передачи пакетов в HTB и позволяющих выполнять оптимальное планирование: контроль интен- сивности входящего потока пакетов, динамическое изменение пропускной спо- собности канала относительно входящей интенсивности, оптимизация предо- ставления полосы для классов трафика относительно входящей интенсивности. 5. Разработан алгоритм поддержки низкоприоритетных сервисов в усло- виях сильного доминирования высокоприоритетных сервисов, основанный на перераспределении токенов управления потоком, что позволяет обеспечить принцип справедливости в отношении всех сервисов, работающих в КПТС. 6. Для проверки эффективности разработанных алгоритмов было произ- ведено имитационное моделирование их работы в среде AnyLogic в сравнении с работой алгоритма HTB в типовой конфигурации. Результаты выявили, что разработанные алгоритмы показывают более низкие суммарные значения за- держки для различных классов трафика, тем самым обеспечивая высокую до- ступность сервисов. Соответственно, предложенные алгоритмы позволяют оп- тимизировать использование пропускной способности и обеспечивать мини- мально возможную задержку для приоритетных классов трафика.