Алгоритмы балансировки в сети OSPF

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

Введение

Протокол маршрутизации OSPF представляет собой протокол внутренней маршрутизации, работающий на технологии отслеживания состояния канала. Под «протоколом внутренней маршрутизации», имеется в виду, что OSPF представляет собой протокол, используемый в контексте набора сетей и маршрутизаторов, обменивающихся служебными сведениями о маршрутах через общий протокол маршрутизации [1]. Набор сетей и маршрутизаторов, работающих с одним форматом протокола маршрутизации формируют так называемую автономную систему (AC). В протоколах состояния каналов, каждый маршрутизатор АС формирует базу данных (базу данных состояния каналов), содержащий информацию для определения топологии АС [1].

Цель

Исследование алгоритмов, которые гарантировали бы распределение нагрузки в сетях под протоколом OSPF, выявления их недостатков и преимуществ при моделировании. Цель этой работы направлена на изучение поведения планируемой адаптивной стратегии маршрутизации OSPF, которая опиралась бы на оценку пропускной способности и состояния каналов.

Функционирование OSPF в рамках АС

Топология АС может быть определена путем запуска протокола Hello. Периодические обмены Hello-пакетами позволяют установить и поддерживать соседские отношений между двумя маршрутизаторами AС. Непосредственным преимуществом является быстрое обнаружение любого отказа канала, позволяет быстро устранить последствия отказа для всей сети.

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

Граф смежности AС описывает потоки пакетов протокола маршрутизации и говоря более конкретно рассылает сообщение LSU (Link State Update) по всей AС. Сообщениями LSU посылают обновления в базе данных состояния канала. Каждый LSU несет в себе набор LSA (Link State Advertisement).

Состояние интерфейса (или канала маршрутизатора) определяется с идентификацией маршрутизатору через его LSA, что предоставляет следующую информацию: тип канала, маска сети или адрес интерфейса IP, ID соседнего маршрутизатора и соответствующую стоимость канала.

Все маршрутизаторы в AС имеют одну и ту же базу данных состояния канала. Локальный статус конкретного маршрутизатора зарегистрирован в базе данных, то есть его интерфейсы и достижимые соседние роутеры. Каждый маршрутизатор сообщает о своем локальный статус в AС рассылая сообщения (flooding) во все направления, чтобы локальная база состояний каналов оставалась актуальной. Каждый маршрутизатор ищет кратчайший маршрут от всех маршрутизаторов с использованием алгоритма Дейкстры [2]. Каждый строит свое дерево маршрутизации, установив себя, как корень дерева. После чего имея построенный кратчайший путь к графу, таблица маршрутизации может быть быстро использована.

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

Алгоритм адаптивной балансировки через оценку эффективной пропускной способности

Этот адаптивный алгоритм маршрутизации [3] имеет две цели: оценка стоимости канала и создание «политики для принятия решения об обновлении стоимости канала». Для первой цели все стоимости, которые будут использоваться в будущем кратчайшем или лучшем периоде обновления путей вычисляются на основе предварительной информации о нагрузке каналов (трафика). В то же время для второй, расходы анализируются таким образом, чтобы решение по обновлению расходов могло быть принято окончательно.

Предложенный адаптивный алгоритм маршрутизации был промоделирован в среде OPNET Modeler. Обновления расходов ссылок на основе эффективных оценок пропускной способности осуществляются для каждого активного интерфейса маршрутизатора. Рисунок 1 показывает события, связанные с маршрутизацией и потоком информации среди соответствующих активных интерфейсов маршрутизатора, модули оценки пропускной способности и традиционный модуль OSPF. Стрелки обозначают возникновения событий и считывания данных.

Рис. 1. Алгоритм адаптивного балансирование на основе пропускной способности

Для каждого активного интерфейса маршрутизатора, существует соответствующий модуль оценки пропускной способности. Соответствие между модулем оценки и интерфейсом устанавливается через номер интерфейса {0, 1,..., N}. Каждый раз, когда пакет поступает на вход интерфейса маршрутизатора, информация, такая как время доставки и размер пакета предоставляется соответствующему модулю оценки пропускной способности. Каждый модуль оценки пропускной способности должен сохранять эту информацию. Оценка пропускной способности выполняется периодически запланированным интервалом (Bandwidth Estimation Period — BEP). Каждый модуль оценки пропускной способности вычисляет пропускную способность, необходимую трафика, передаваемого через соответствующий интерфейс в течение времени [t — ВЕР, t], отталкиваясь от информации, такой как размер буфера, необходимая скорость потерь канала и сохранен расчет трафика, где Т текущее время и BEP, отрезок времени, на котором расчеты трафика следует собирать и использовать для оценки полосы пропускания.

В зависимости от текущей оценки пропускной способности, стоимость канала, соответствующая рассматриваемого интерфейса маршрутизатора определяется по формуле [3]:

                                                                                           (1)

где С_i,t — стоимость, соответствует канала i во время t; BE_{(t-BEP, t)} — оценка эффективной пропускной способности за период; CTi — общая пропускная способность канала i.

Хотелось бы обратить внимание, что новая стоимость ссылки рассчитывается сразу после эффективной оценки пропускной способности. Обновленная стоимость рассчитывается периодически каждый BEP период времени. Новая стоимость ссылки затем передается в модуль OSPF, вместе с соответствующим номером интерфейса. Эти сообщения передаются между группой модулей эффективной оценки пропускной способности (соответствующие каждого интерфейса маршрутизатора) и модулем OSPF.

С получением эффективной оценки пропускной способности вычисляем новую стоимость ссылки на каждом интерфейсе маршрутизатора каждый BEP период. Выполняем это независимо среди интерфейсов маршрутизатора. Модуль OSPF получает новые стоимости независимо от модуля оценки пропускной способности за каждый BEP период.

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

Состояние каждого интерфейса маршрутизаторов распространяется по сети с помощью особенного типа LSA. LSA маршрутизатора несут информацию о стоимости всех активных интерфейсов маршрутизатора. Если изменение стоимости, по крайней мере, одного интерфейса подтверждается, то сообщение с обновлениями отправляются в сеть и все интерфейсы маршрутизаторов будут иметь их обновленную стоимость. Это обновление осуществляется через базу данных состояния каналов обновляя стоимость на интерфейсах и из-за распространения LSU в сеть. Наконец, после получения этих LSU, все остальные узлы обновят свою базу данных состояний каналов, периодически используется для повторного перестроения таблицы маршрутизации.

Процедура «Политики для принятия решения об обновлении стоимости канала» предложена в работе [3] состоит из следующих управляющих механизмов: минимум затрат, максимальный лимит для вариации стоимости ссылки и минимальный лимит для обновления стоимости канала.

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

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

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

Следует также обратить внимание на то, что принятие процедуры «политики принятия решения об обновлении стоимости канала» является обязательным для того, чтобы наложить ограничения на уровне колебаний стоимости ссылки, свести к минимуму частоту обновления стоимости канала и таким образом сократить нагрузку трафика в сети связанного с перестройкой таблиц маршрутизации.

Среда моделирования для оценки предлагаемой адаптивной стратегии маршрутизации OSPF приведены на рисунке 2 на примере конкретной сети.

Каждый канал в этой тестовой сети, настроен под Frame Relay, 4,0 Мбит и каждый узел использует FIFO (First-In-First-Out) стеки с буфером 70 Кбайт в каждый выходной интерфейс. Трафик, подаваемого в сеть определяется следующей информацией: время начала передачи IP пакетов и остановки, среднее время между пакетами (среднее время дельта) и средний размеров пакетов.

Рис. 2. Пример сети

Для испытаний были выбраны пять характеристик трафика (а именно S1, S2, S3, S4 и S5). Для каждой спецификации, поток трафика идет от узлов слева к узлам справа. Для целей сравнения производительности, среди этих спецификаций характеристик трафика мы поддерживаем общие значения параметров трафика в начале и во время остановки, а затем постепенно увеличиваем интенсивность трафика. Поэтому упорядочим последовательности: S1, S2, S3, S4, S5 по убыванию среднего значения времени дельта. В таблице 1 приведены принятые значения параметров трафика для спецификации S1 для каждой из этих пар источник — назначение.

Таблица 1

Параметры трафика для каждой пары

№	Время начала	Время остановки	Среднее дельта время	Средний размер (байт)
1	200	1500	2800	600
2	700	2300	900	200
3	2000	3600	1500	350
4	400	1200	1700	300
5	800	1000	2600	450
6	1400	3600	1800	600

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

Таблица 2

Среднее время дельта

№	Среднее время дельта для каждого сценария
	S1	S2	S3	S4	S5
1	2800	2600	2500	2400	2300
2	900	800	700	650	500
3	1500	1300	1100	1000	950
4	1700	1600	1500	1300	1200
5	2600	2400	2300	2200	2000
6	1800	1700	1650	1600	1400

Предложенные адаптивная и традиционная стратегии маршрутизации OSPF [1] были смоделированы и испытаны в том же сетевой среде с одинаковой технической характеристики трафика. Таким образом было получено два графика для каждого сценария. На рисунке 3 показано, как средняя пропускная способность сети развивается с точки зрения продолжительности времени моделирования.

Рис. 3. График результата моделирования

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

Рисунок 4 показывает, как задержка передачи сети меняется в зависимости от интенсивности входящего трафика и влияние стратегии маршрутизации. Для сценария S1 с низкой интенсивностью трафика предлагаемый адаптивный механизм маршрутизации предлагает только немного меньшую среднюю задержку, чем метод без адаптивного регулирования. Однако, когда интенсивность трафика становится выше, как в случае сценариев S2. S3, S4 и S5, то разница измеренной средней задержки между двумя типами стратегий маршрутизации становится очевидной, подтверждающей преимущество адаптивных средств маршрутизации.

Рис. 4. Средняя задержка для сценария S1

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

Таблица 3

Задержка для сценариев

Средняя задержка
Сценарий трафика	Традиционная стратегия	Адаптивная стратегия
1	0. 165754	0. 040759
2	2. 107570	0. 146827
3	2. 208358	0. 11. 5827
4	2. 291846	0. 132146
5	3. 179885	0. 219044

Рис. 5. Средние потери для сценария S1

Для всех сценариев был получен аналогичный результат. Но согласно рисунку 5 адаптивная стратегия предлагает высокие показатели по потере пакетов в сценарии S1. Аналогично для S2 и низкие показатели в сценариях S3, S4 и S5, чем традиционные средства маршрутизации.

Алгоритм адаптивной и распределенной балансировки в сети OSPF

Мы предполагаем согласно [6], что w_l веса канала фиксированные. Для каждой пары вход-выход , обозначим множество кратчайших путей от узла s_k к узлу t_k по отношению к весам связей w_l.

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

В момент времени t_n, после получения информации у(n) по всем измеренных нагрузок, узел i регулирует отношения распределения трафика для всех узлов назначения t следующим образом [6]:

1. Расчет стоимости Dp(y(n)) для каждого пути.

2. Найти путь с максимальной стоимостью, т. е. Dq(y(n)) = max Dp(y(n)) и снижение коэффициент разделения для первого звена (i, j) этого пути, таким образом:

                                                                                      (2)

3. Выбрать другой путь  случайным образом и увеличить коэффициент деления его первого звена (i, k) следующим образом:

                                                                                    (3)

4. Для всех других допустимых следующих хопов j, сохранить старое соотношение распределения:

                                                                                                           (4)

Алгоритм [6] является итеративным и работает следующим образом. Тест сети (в том числе узлов n, ссылки l, пары вход-выход k, и путей р), веса канала w_l и требований к трафику d_k исправляют сначала. Каждая пара вход-выход сначала выделена до кратчайших путей с относительно исправленными весами ссылки w_l. Если существует несколько кратчайших путей, движение сначала разделяют поровну в каждом узле.

На каждой итерации n, измеренные веса канала у_l(n), вызванные отношениями распределения  рассчитываются следующим образом. Сначала определяется для каждой пары вход-выход k, вызванные отношениями распределения , для каждого пути :

                                                                                                   (5)

Тогда измеренные веса канала у_l(n) определяются как:

                                                                             (6)

где e_k(n) являются независимыми переменными подчиненными Гауссову распределению и описывают случайные флуктуации трафика во время периода измерения n.

Для испытания используются две разных сети (рисунок 6):

1. 10 узлов, 52 каналы, 72 пары вход — выход;

2. 20 узлов, 102 канала, 380 пар вход -выход.

Рис. 6. Две сети для испытаний. Максимальное использование канала в зависимости от числа итераций

Испытуемые сети являются случайными сетями, генерируемыми механизмом, описанным в [7].

Используем три различных сценария трафика. В первом (рисунок 7) из них случайные колебания трафика во временной шкале измерений игнорируются, учитывая параметр флуктуаций. Во втором эти случайные флуктуации учитываются с помощью параметра флуктуаций. В третьем сценарии, рассмотрим колебания трафика в более длительных временных масштабах, позволяя требованиям к трафику резко меняться три раза в течение периода оценки (после 500, 1000 и 1500 итераций, соответственно).

Приведены результаты адаптивного алгоритма по сравнению с

1.      «ECMP»: стандартная политика, где трафик распределяется в равной степени.

2.      «Неоптимальная»: оптимальное значение ограничено задачей оптимизации [6].

3.      «Оптимальная»: оптимальное значение [6] статической задачи балансировки нагрузки.

Сценарий без флуктуаций трафика показывает, что производительность адаптивного алгоритма приближается к суб-оптимальному значения и повышает производительность заметно по сравнению со стандартным алгоритмом распределения. Небольшой размер шага в алгоритме гарантирует, что флуктуации незначительны. Время конвергенции в сети с 20-узлов (около 200 итераций) только два раза больше, чем в сети с 10-узлов (около 100 итераций), несмотря на огромный рост в сложности сети.

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

В сценарии при колебании трафика в более длительный временной период видим, что адаптивный алгоритм реагирует на изменения и предоставляет результат, близкий к неоптимальному значению в сети с 10-узлов и близко к оптимальному значению в сети с 20-узлов.

Оптимизация весов каналов в долгосрочной перспективе повышает производительность сети. В сети с 20-узлов также удельные веса обеспечивают хороший результат. Объясняется тем, что в сети с 10-узлов, число коротких, связанных с весами звеньев ссылки 116 тогда, как их 153 в случае оптимальных весов каналов. Таким образом, число параметров больше, в последнем случае, а также результаты лучше. В сети с 20-узлов, соответствующее число кратчайших путей является 782 и 785. Результаты очень близки.

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

Основная идея [9] для использования нечеткой логики в адаптивной маршрутизации на основе OSPF заключается в том, что она успешно применяется в различных системах, где человеческого опыта недостаточно для точного определения условий для работы системы, и представляет собой основу для принятия решений по эксплуатации, то есть набор из параметров системы [8]. Процесс расчета новых весов выполняется в три этапа следующим образом:

1.       Процесс, в котором входные переменные должны превратить в нечеткие множества с помощью функции принадлежности.

2.       Расчет стоимости исходного нечеткого множества с помощью базовых правил.

3.       Процесс, в котором исходное нечеткое множество превращается в числовое значение.

На рисунке 7 показаны функции принадлежности нечетких множеств, связанных со сроком набор нагрузки каналов. На рисунке 8 показаны параметры, связанные со сроком потери пакетов.

Рис. 7. Функции принадлежности для погрузки на канале

Рис. 8. Функции принадлежности для потерь пакетов

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

Функции принадлежности нечетких множеств для коэффициента изменения веса приведены на рисунке 9. Новое значение веса линии рассчитывается на основе предыдущего, сначала полученного коэффициента изменения веса на основе нечетких функций принадлежности, как показано на рисунке 9. С такими определенными функциями коэффициент может иметь значение в интервале 0,9–1,1. После расчета, коэффициент умножается с предыдущим значением веса, округляется до целого числа, и результат является новым весом канала. По этому принципу минимальное значение веса может быть 5.

Рис. 9. Функции принадлежности для веса канала

В адаптивной модели, абсолютное количество новой веса ограничивается в 1,5 раза большее значение от номинального веса канала. Номинальный вес канала определена в [1]. Это ограничение было введено, чтобы избежать сетевых колебаний, вызванных резким увеличением веса на определенном канале.

Упомянутая адаптивная модель [9] маршрутизации протестирована на симуляторе ns2. Промоделированы две сети с 8 узлами и 11 каналами и 20 узлами и 26 каналами.

Поведение адаптивной модели было проверено на различных уровнях нагрузки в сети, на таких, как требования к трафику в диапазоне от 0 % до в среднем 35 % от общей емкости сгенерированной сети. Верхний предел имеет уровень, что приводит к большим потерям IP пакетов в сети, то есть, когда топология сети и планируемые мощности неправильно рассчитаны по отношению к требованиям. Соответственно, ни регулярный протокол OSPF, ни адаптивная модель не может обеспечить распределение трафика в сети для того, чтобы резко сократить потери. Эта ситуация встречается довольно часто, когда некоторые каналы достигают нагрузки выше 25 % [9].

Диаграмма на рисунке 10 показывает стоимость погрузки для чистой работы топологии с 8 узлов в зависимости от нагрузки на сеть. Функция затрат приводится в [9].

Рис. 10. Стоимость погрузки для сети с 8 узлами

График показывает, что адаптивная модель дает значительно лучшие результаты, чем OSPF маршрутизация, для сетевых нагрузок в 25 %. Это предел, при котором все каналы загружаются на менее 2/3 мощности при использовании OSPF маршрутизации.

Другой параметр, который имеет большое значение для оценки качества адаптивной модели, является потеря IP пакетов в определенный период времени. График на рисунке 11 показывает суммированные данные для всей сети и для OSPF маршрутизации, и для исследуемой адаптивной модели.

Рис. 11. Потери пакетов для сети с 8 узлами

На рисунке 11 видно, что в отличие от OSPF маршрутизации, когда потери становятся существенными с 25 % загрузки сети, при использовании адаптивной модели потери становятся существенными только с более 30 % нагрузки на сеть. Таким образом было достигнуто улучшение почти на 20 %, т. е. процент, на котором граница проявлений сетевых IP потерь изменяется относительно сетевой нагрузки. Аналогичные результаты достигаются в сети на 20 узлов.

На рисунке 12 показано потери IP трафика в адаптивной модели для сети на 20 узлов, измеренные между каждыми двумя изменениями параметров стоимости. Ниже приведены графики для различной нагрузки на сеть.

Рис. 12. Потери в определенные промежутки времени до достижения равновесия

Что касается сетевых нагрузок ниже 18 %, то потери пакетов отсутствуют. Данные показывают нагрузку на 18 % — 22 %. Хотя состояние конвергентности достигается в 10 –20 шагов, график показывает, что уровень потерь IP пакетов стабилизируется примерно уже через 6 или 7 шагов. Также заметно, что сразу же после активации адаптивного механизма уровень потерь значительно снижается по отношению к первому интервалу, где распределение осуществляется на основе исходных параметров OSPF стоимости каналов связи. Таким образом, можно сделать вывод, что использование адаптивных моделей приводит к улучшению с точки зрения сокращения потерь, но последующие изменения в стоимости каналов после шестого или седьмого шага не имеют практического и значительного эффекта. Если цель адаптивного использования модели является устранение или снижение потерь IP пакетов, то на основании результатов, показанных на рисунке 12 модифицированная адаптивная модель может быть сформирована для реализации этой цели, и колебания IP трафика будут значительно уменьшены в сети.

Цель этих поправок направлена ​​на то, чтобы избежать частых изменений стоимости до сих пор имеет больше преимуществ перед выборочным применением адаптивного механизма с целью сокращения потерь IP пакетов. В начале, разрешенные потери установлены в 0. На первом этапе, в котором появляются потери IP трафика, параметр разрешенных потерь установлен в 0,01 % от общего трафика, проходящего через канал за один интервал.

Рис. 13. Потери с использованием модифицированной модели

Рисунок 13 изображает потери с использованием адаптивной модели и без изменений так же, как и для стандартной OSPF маршрутизации.

Потери при реализации модифицированной адаптивной модели намного меньше, чем при использовании OSPF маршрутизации, так же, как в адаптивной модели без изменений. Однако, основное преимущество модифицированной модели можно увидеть на рисунке 14.

Рис. 14. Эффект от применения модифицированной модели

Рисунок 14 показывает отношение количества шагов к нагрузке на сеть(суммарно 30 шагов). Число изменений в модифицированной модели гораздо ниже, а значит, и колебания в сетевом трафике также ниже.

Выводы: Вадаптивном алгоритме через оценку пропускной способности, чтобы подтвердить подход, предложенный в [3], качество сети оценивалась экспериментально путем моделирования с точки зрения средней пропускной способности сети, задержки передачи пакетов и скорости потери пакетов. С целью сравнения, традиционный метод маршрутизации OSPF [10] было принято, как эталон. Было подтверждено, что адаптивная стратегия маршрутизации принимает лучшие решения, чем при эталонном OSPF. Этот результат был интуитивно ожидаемым в связи с тем, что адаптивный алгоритм маршрутизации может лучше распределить нагрузку трафика среди сетевых соединений. Непосредственным следствием этого факта является высокая пропускная способность сети, сохраняется даже при высокой интенсивности трафика. При первом же взгляде, можно сделать вывод, что главным недостатком адаптивной стратегии маршрутизации является большая задержка за счет дополнительной нагрузки, известного как сообщение об обновлении стоимости канала. На первый взгляд может показаться странным, что существует такой случай, когда нагрузка сетевого трафика небольшая, например, для сценария S1, и где эталонная модель выигрывает в адаптивной. Однако для больших нагрузок трафика в случае сценариев S2, S3, S4 и S5, адаптивная маршрутизация превосходит в значительной степени традиционную OSPF низкой задержкой передачи пакетов. Иными словами, дополнительная задержка, сформированная для сообщений, имеет незначительное влияние, по сравнению с введенными альтернативными маршрутами. Наконец, по темпам потерь пакетов использование адаптивной стратегии маршрутизации становится еще более полезным, когда в сети преобладают потоки с высокой скоростью. То есть за счет альтернативных путей можно избежать коллизий, а следовательно и потерь пакетов.

Если сравнивать этот алгоритм [3] без модификаций с другими [6] и [9], то несмотря на свою более простую математическую модель и неэффективность при малых нагрузках на сеть, алгоритм охватывает более параметров качества обслуживания и гарантирует большее использование сетевых ресурсов (в сравнению с [6]).

В алгоритме адаптивной и распределенной балансировки [6] определяющей особенностью является использование функций задачи оптимизации (неоптимальной или суб-оптимальной) и функции статической задачи балансировки нагрузки (оптимальной). Использование этих задач позволяет сформировать критерии и более гибко рассчитать параметры для изменения весовых коэффициентов канала.

В модифицированном алгоритме динамической балансировки на основе нечеткой логики [9] используются функции принадлежности, что позволяет получить наиболее оптимальный результат, основанный на предварительной сборке и результатах. В работе предлагается модификация, целью которой является уменьшение количества и частоты изменений стоимости каналов, что позволяет избежать резких колебаний трафика, но модификация не привела к существенным улучшениям показателей качества (рисунок 13), однако существенно уменьшило количество изменений коэффициентов стоимости каналов (рисунок 14).

Задача OSPF [10] маршрутизации относится к NP-сложным задачам. Предложенные алгоритмы показывают возможность создания таких алгоритмов, которые позволяли бы адаптивно и динамично управлять трафиком в сети и достичь стабильности и конвергентности в наиболее короткий промежуток времени, высокого уровня использования сетевых ресурсов со снижением нагрузки на отдельные каналы и уменьшением потери пакетов.

Литература:

1.      J. Moy. Ascend Communications, Inc. April 1998. OSPF Version 2, [Электронный ресурс], режим доступа к журналу, http://www. ietf. org/rfc/rfc2328. txt.

2.      D. E. Comer. Network interconnection with TCP IP — Principles. Protocols and Architecture // Volume L Editora Campus. — 1998.

3.      T. B. Pereira, L. L. Ling An adaptive OSPF routing strategy based on bandwidth estimation // Revista da Sociedade Brasileira de Telecornunicacoes. — 2003. — Vol. 18 № 1.

4.      A. Shaikh, I. Rexford, KG Shin Evaluating the Impact of Stale Link State on Quality — of — Service Routing // IEEEACM Transactions on Networking. — 2001. — Vol. 9, № 2.

5.      A. Shaikh, I. Rexford, KG Shin Dynamics of Quality — of — Service Routing with Inaccurate Link — State Information // University of Michigan Technical Report — 1997.

6.      R. Susitaival and S. Aalto Adaptive load balancing with OSPF // Networking Laboratory, Helsinki University of Technology. — 2004.

7.      C. Villamizar OSPF Optimized Multipath(OSPF-OMP), February 1999, [Электронный ресурс], режим доступа к журналу, http://tools. ietf. org/html/draft-ietf-ospf-omp-02.

8.      R. Yager, D. Filev Essentials of Fuzzy Modeling and Control. — John Wiley & Sons, 1994.

9.      N. Borovina, S. Kreso OSPF — based model of adaptive routing and possibility for stable network operations // 5th WSEAS Int.Conf. on Applied Informatics and Communication. — 2005.

10.  Томас М. Т. Структура и реализация сетей на основе протокола OSPF. — М.: Издательский дом " Вильяме ", 2004. — 816 С.