Балансировка потоков данных в программно-конфигурируемых компьютерных сетях

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

В данной работе основное внимание будет сосредоточено на сравнительном анализе модуля TE (Traffic Engineering, TE), работающего с маршрутами, вычисленными с помощью алгоритма Йена и балансировки нагрузки, включающей в себя три коэффициента: a, β, γ, дающих больше возможностей управления нагрузкой, и основанной на работе алгоритма парных перестановок маршрутов.
В рамках научного проекта решены следующие задачи:
-Разработан алгоритм многопутевой адаптивной маршрутизации в программно-конфигурируемых сетях;
-Разработано программное обеспечение многопутевой адаптивной маршрутизации в программно-конфигурируемых сетях;
-Разработан алгоритм балансировки нагрузки в программно-конфигурируемых сетях;
-Разработано программное обеспечение балансировки нагрузки в программно-конфигурируемых сетях.
Основное внимание сосредоточено на таких аспектах, как:
-Построение множества оптимальных и резервных маршрутов в соответствии с показателем качества обслуживания;
-Балансировка нагрузки по найденным маршрутам;
-Оптимизация процесса балансировки нагрузки в соответствии с показателями вариации маршрута и требуемого значения джиттера.

Современные протоколы динамической маршрутизации, такие как OSPF и IS-IS позволяют обойти сильно загруженные каналы связи, чтобы улучшить качество обслуживания  сетевых сервисов и приложений. Протоколы многопутевой маршрутизации, как правило, используют в своей работе алгоритм k-кратчайших путей с вычислительной сложностью построения оптимальных и резервных маршрутов O(N³). Многопутевая маршрутизация позволяет сбалансировать нагрузку на сеть путем распределения сетевого трафика по резервным маршрутам. Кроме того, многопутевая маршрутизация позволяет быстро реагировать как на возможные всплески нагрузки в каналах связи, так и на возможные динамические изменения в структуре сети, например, отказы узлов и линий связи в сети.

В рамках научного исследования разработано математическое и программное обеспечение многопутевой адаптивной маршрутизации и балансировки нагрузки трафика на различных топологий в программно-конфигурируемых сетях. Программное обеспечение разработано с помощью языка программирования C# с использованием платформы .NET Framework 4.5.

Разработка эффективных методов и алгоритмов адаптивной многопутевой маршрутизации позволяет повысить на 30% быстродействие передачи данных по сравнению с алгоритмом Йена и технологией Traffic Engeneering при обновлении маршрутной информации в программно-конфигурируемых сетях. Оптимизация использования ресурсов сетевой инфраструктуры происходит за счет использования методов, производящих пересчеты необходимой информации не для всей сетевой топологии, а только для того участка сетевой инфраструктуры, где произошло изменение данных канала связи. Разработка методов и алгоритмов балансировки нагрузки позволяет оптимизировать нагрузку на каналы связи в сети и обеспечить требуемые показатели по качеству обслуживания сетевого трафика. Уникальностью предлагаемой технологии является разрабатываемое программное обеспечение адаптивной многопутевой маршрутизации и балансировки нагрузки, позволяющее промоделировать работу методов и алгоритмов многопутевой адаптивной маршрутизации и балансировки нагрузки на любой реально-существующей топологии.

Анализ полученных результатов показывает, что применение предложенной модели по сравнению с классическим подходом Traffic Engineering позволяет балансировать нагрузку не только между смежными интерфейсами, но и проложенными маршрутами за счет контроля над параметрами a, β, γ, (a – коэффицент балансировки нагрузки, β – отклонение длины минимального маршрута от длины максимального маршрута, γ – отклонение метрики канала, находящемся в минимальном маршруте, от метрики канала, находящемся в максимальном маршруте, которые состоят в отношении парного перехода). С добавлением двух новых коэффициентов (β и γ) появляется дополнительная возможность контроля работы алгоритма: большая часть загруженных каналов и, следовательно, маршрутов в компьютерной сети будут сбалансированы (разгружены), тогда как в случае классического подхода, возможно, будет только уменьшена метрика максимально-загруженного канала в маршруте, а отклонение от длины оптимального маршрута изменится незначительно.

На основании полученных результатов можно сделать следующие выводы: после введения двух коэффициентов β и γ со значением 0.7, отклонение длины максимального маршрута от оптимального маршрута сразу же уменьшилось на 5%.  При a большем или равным 0.8 классический метод перестает срабатывать, т.к. загрузка всех каналов связи в топологии находится в пределах указанного значения коэффициента, следовательно, отклонение от длины оптимального маршрута остается прежним.

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

При установке коэффициента a больше 0.8,  разрешается загрузка каналов связи более чем на 80%, и алгоритм балансировки нагрузки выравнивает почти все маршруты, отклонение длины которых будет стремиться к 0. К сожалению, данное действие не оставляет в каналах связи дополнительного резерва, тем самым увеличивая шансы потерь пакетов данных и вероятность отказа данных каналов. Поэтому можно сделать вывод о том, что желательно варьировать коэффициент a от 0.7 до 0.8, так как дальнейшее увеличение a не существенно повлияет на результаты работы алгоритма балансировки нагрузки. Коэффициенты β и γ позволяют выравнивать длины смежных маршрутов и веса смежных каналов соответственно, поэтому их следует устанавливать в пределах от 0.8 до 0.9, что будет приводить к оптимальному срабатыванию алгоритма балансировки нагрузки. При устремлении всех коэффициентов  a, β, γ  к 1 отклонение от длины оптимального маршрута будет стремиться к 0, но для этого потребуется больше вычислительных ресурсов, и не во всех топологиях данное действие необходимо выполнять.

1. Вишневский В. М. Теоретические основы построения компьютерных сетей. Москва: Техносфера. 2003. 512 с.
2. Yong Liu, A. L. Narasimha, A. Reddy, “Fast Rerouting Scheme for OSPF/IS-IS Networks”, ICCCN, Oct. 2004.
3. A. Sridharan, R. Gu´erin, and C. Diot, “Achieving Near-optimal Traffic Engineering Solutions for Current OSPF/IS-IS Networks,” in IEEE/ACM Trans. Netw., vol. 13, 2005, pp. 234-247.
4. Перепелкин Д. А. Математическая модель многопутевой адаптивной маршрутизации с балансировкой неоднородной нагрузки в условиях динамических подключений узлов и линий связи в телекоммуникационных сетях. Москва: Радиотехника. 2015. № 5. С. 46-54.
5. Перепелкин Д. А. Модель отказоустойчивой многопутевой адаптивной маршрутизации с балансировкой неоднородной нагрузки в сетях связи. Москва: Радиотехника. 2015. № 11. С. 40-47.

In modern computer networks loading and bandwidth of communication links are optimized for providing high-quality service of network traffic, new services and technologies. As a rule, for this task the protocols of dynamic routing based on Dijkstra’s algorithm are used. Protocols of multipath routing for ensuring reliability and accuracy of the provided information allow to divide critical traffic and to execute load balancing along several routes at the same time. The purpose of the work is development and research of the improved multipath adaptive routing model in computer networks with load balancing. In this work we focused on indicator of jitter optimization between the paved paths and a deviation value of reserve routes from an optimal route. Comparison and estimation of the offered algorithm with some existing approaches (Yen’s algorithm), and also modeling and analysis on various topologies of computer networks have been carried out.