Усовершенствование алгоритма маршрутизации с балансировкой нагрузки по путям неравнозначной стоимости для протокола EIGRP

Размещено на http://www.allbest.ru/

УДК 623.618:519.686

усовершенствование алгоритма маршрутизации с балансировкой нагрузки по путям неравнозначной стоимости для протокола eigrp

А.В. Снегуров¹, В.Х. Чакрян²

Харьковский национальный университет радиоэлектроники, Харьков



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

Ключевые слова: EIGRP, метрика, динамическая маршрутизация, перегрузка канала, балансировка трафика по путям не равнозначной стоимости, DoS атака.

А.В. Снігуров, В.Х. Чакрян

В статті наводиться аналіз можливих умов, які можуть привести до перенавантаження одного з каналів звя'зку при балансуванні трафіку за шляхами нерівнозначної вартості протоколом динамічної маршрутизації EIGRP. Також в роботі проводиться приклад топології телекомунікаційної мережі, в якій може виникнути перенавантаження каналу звя'зку, можливі шляхи вирішення даної проблеми з використанням як допоміжних функцій протоколу EIGRP, так і, запропоновані авторами методом балансування трафіку.

Ключові слова: EIGRP, метрика, динамічна маршрутизація, перевантаження каналу, балансування навантаження за шляхами не рівнозначної вартості, DoS атака.

Unequal cost load balancing algorithm improvement for eigrp protocol.

A.V. Snigurov, V.K. Chakrian

In this paper it's analyzed the possible conditions that could lead to link overload during unequal cost load balancing when using dynamic routing protocol EIGRP. Also in this paper it's proposed an example of the telecommunication network topology where the link overload could exist and the possible solutions of this problem using the standard capabilities of EIGRP protocol and using the method of load balancing proposed by the authors.

Key words: EIGRP, metrics, dynamic routing, link overload, unequal cost load balancing, DoS attacks.



Введение

Балансировка трафика является стандартной функцией программного обеспечения маршрутизации и доступно на всех платформах маршрутизаторов. Эта функция является неотъемлемой частью процесса пересылки пакетов в маршрутизаторе и включается автоматически, если в таблице маршрутизации есть несколько путей до адресата. Распределение трафика основано на стандартных протоколах маршрутизации, таких как: RIP, IGRP, EIGRP, OSPF или осуществляется на основе статически настроенных маршрутов и механизмов пересылки пакетов. Распределение нагрузки позволяет маршрутизатору использовать несколько путей до адресата при передаче пакетов. Особенно важна балансировка нагрузки в условиях резкого увеличения трафика через маршрутизаторы при DDoS-атаке на конечные ресурсы.

Протокол EIGRP обладает уникальным свойством балансировки нагрузки по путям неравнозначной стоимости (англ. «Unequal Cost Load Balancing»). В отличие от протокола OSPF, который может производить балансировку нагрузки лишь по путям с одинаковым значением метрики, EIGRP может разделять трафик между путями пропорционально метрики каждого из них.

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



I. Возникновение отказа в обслуживании вследствие некорректного распределения пакетов по каналам связи при балансировке нагрузки

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

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

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

Рисунок 1 - Пример топологии сети с иллюстрацией проблемы при неравнозначной балансировке нагрузки в динамическом протоколе маршрутизации EIGRP

Для того чтобы более подробно разобраться в балансировке нагрузки, сперва следует рассмотреть общую формулу расчета метрики протокола EIGRP (1) [1]:



, (1)

где - наименьшее значение взвешенного показателя пропускной способности в маршруте ; - наибольшая загрузка одного из каналов связи в маршруте ; - суммарная задержка пакетов в маршруте ; - наименьшая надежность одного из каналов связи в маршруте ; , - все возможные маршруты в заданной сети при передачи информации между узлами , при . Коэффициенты позволяют учитывать в метрике вышеуказанные параметры. По умолчанию в стандартном алгоритме, описанном Cisco, данные коэффициенты имеют следующие значения: и .

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

Расчет взвешенной пропускной способности (1) производится следующим образом:

, (2)

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

Для расчета суммарной задержки маршрута используется следующая формула:

, (3)

где - сумма задержек пакетов каждого из каналов связи, входящих в маршрут при передаче информации между - узлом отправителем и - узлом получателем.

Для выбранной топологии (рис. 1) в маршруте наименьшая пропускная способность одного из каналов связи равна 1 Гб/с, в - 800 Мбит/с, соответственно:

,

.

Изначально маршрутизаторы используют стандартную величину задержки пакетов для каждого из портов в зависимости от технологии передачи данных и пропускной способности. К примеру, в маршрутизаторах компании Cisco стандартная задержка для FastEthernet порта составляет 10 мкс, а для GigabitEthernet 1 мкс. Также в данной топологии задержка в каналах связи между узлами выбрана равной 10 мкс, а задержка между и - 1 мкс. Соответственно:

,

.

При и , метрика приобретает следующий вид:



. (4)

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

,

.

В стандартной ситуации, без использования балансировки нагрузки, маршрутизатор выберет маршрут с меньшей метрикой . Для того, чтобы EIGRP смог производить балансировку нагрузки необходимо, чтобы оставшиеся маршруты (с метрикой меньшей, чем у лучшего маршрута), стали запасными.

Протокол EIGRP обладает специальной процедурой для выбора запасных маршрутов и для того, чтобы в ней разобраться, необходимо ввести несколько новых понятий:

- текущее расстояние (англ. «Feasible Distance») - это метрика определенного маршрута (к примеру: ) от заданного маршрутизатора (к примеру: ), до сети назначения (к примеру: ).

- заявленное расстояние (англ. «Reported Distance») - это метрика определенного маршрута (к примеру: ) полученная от соседа заданного маршрутизатора, через которого проходит этот маршрут (в данном случае для маршрутизатора и маршрута таким соседом является ) до сети назначения (к примеру: ).

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

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

.

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

Рисунок 2 - Метрики, необходимые для принятия решения о соблюдении условия правдоподобия на маршрутизаторе

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

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

, (5)

где - это пропорция количества пакетов, которое будет передано по данному маршруту при балансировке нагрузки, ; - параметр расхождения, ; - это максимальная метрика одного из маршрутов до заданной сети, которые принимают участие в балансировке трафика (в топологии на рис. 1 ). При этом, максимальное количество маршрутов, по которым EIGRP может балансировать трафик равно 16.

По умолчанию . Администратор может его изменить в пределах . Данный параметр указывает, насколько метрика запасных маршрутов может быть больше по сравнению с минимальной эталонной метрикой (в топологии на рис. 1 ). Если метрика маршрута попадает под выполнения условия - то маршрут будет выбран для балансировки трафика.

Предполагаем, что на маршрутизаторе активирована балансировка нагрузки по путям неравнозначной стоимости в настройках протокола EIGRP командой: traffic-share balanced [2].

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

Для того чтобы избежать подобных явлений, будем считать, что администратор активировал тип балансировки нагрузки по пакетам на интерфейсах маршрутизатора командой: ip load-sharing per-packet. Исходя из формулы (5):

,

.

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

R1# show ip route 100.100.100.0

Routing entry for 100.100.100.0/24

Known via "eigrp 1", distance 90, metric 3328, type internal

………

* 10.0.0.2, from 10.0.0.2, 00:01:14 ago, via Serial0/0/0

Route metric is 3328, traffic share count is 1

………

10.0.0.6, from 10.0.0.6, 00:00:31 ago, via Serial0/0/1

Route metric is 6144, traffic share count is 1

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

В условиях нехватки пропускной способности, динамической протокол маршрутизации не имеет возможности передавать пакеты, которые поддерживают EIGRP соседство. Это приведет к разрыву соседства между маршрутизаторами и , соответственно, к отсутствию балансировки нагрузки. Подобные исследования приведены в статье [4]. Такая ситуация приведет к тому, что весь трафик будет передаваться по маршруту , что приведет и к его перегрузке. Помимо проблем с загрузкой каналов связи возникает и дополнительная нагрузка на центральный процессор маршрутизатора , так как задействуется DUAL алгоритм протокола EIGRP при восстановлении соседства с .

Возможными путями решения данной проблемы являются:

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

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

3. Использование трафик шейпинг и трафик полисинг для ограничения входящего потока от к маршрутизатору до 1,6 Гбит/с.

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

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

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

канал связь балансировка протокол

Из формулы (1) видно, что метрика протокола EIGRP может учитывать загруженность каналов связи маршрута, в случае активации коэффициента . Таким образом, при формула расчет метрики приобретает следующий вид:

, (8)

в маршрутизаторах Cisco . Таким образом, рассчитывается по следующей формуле:

, (9)

где - поток трафика в маршруте , ; - наименьшая пропускная способность одного из каналов связи в маршруте при передаче информации между узлами , .

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

Таблица 1 - результаты моделирования процесса балансировки трафика по путям неэквивалентной стоимости с учетом загрузки каналов связи маршрута в формуле расчета метрики EIGRP

Метрика маршрута	Метрика маршрута	Загруженность маршрута	Загруженность маршрута	Поток трафика в маршруте	Поток трафика в маршруте	Общий поток трафика на входе в сеть
3338	6156	6	7	25	25	50
3338	6156	15	19	60	60	120
3339	6157	24	30	95	95	190
3339	6158	33	41	130	130	260
3339	6159	42	52	165	165	330
3340	6159	51	63	200	200	400
3340	6160	59	74	235	235	470
3341	6162	68	86	270	270	540
3342	6163	77	97	305	305	610
3343	6164	86	108	340	340	680
3343	6166	95	119	375	375	750
3344	6168	104	130	410	410	820
3345	6170	113	141	445	445	890
3347	6173	122	153	480	480	960
3348	6177	131	164	515	515	1030
3350	6181	140	175	550	550	1100
3351	6187	149	186	585	585	1170
3354	6196	158	197	620	620	1240
3356	6208	167	208	655	655	1310
3359	6227	175	219	690	690	1380
3363	6266	184	231	725	725	1450
3368	6363	193	242	760	760	1520
3375	7168	202	253	795	795	1590
3229	6212	255	211	1106	553	1660
3399	9216	220	255	865	865	1730
5888	6257	255	229	1200	600	1800

Как видно из табл. 1 распределение потока трафика по маршрутам происходит равномерно, это связано с тем, что метрики и не изменяются настолько, чтобы изменить целочисленные показатели распределения пакетов по маршрутам и на маршрутизаторе .

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

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

III Метод балансировки трафика путем нахождения наибольшего общего делителя между пропускными способностями каналов связи балансирующего узла

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

1. Ввести математическое ограничение пропорционального распределения пакетов по каналам связи:

I. Записать пропускные способности всех каналов связи, которые будут использованы при балансировке трафика

II. Найти наибольший общий делитель чисел из пункта I.

, (6)

где - пропускная способность канала связи [Мбит/с] при том, что - маршрутизатор, который осуществляет балансировку, - каналы связи -го маршрутизатора, которые принимают участие в балансировке нагрузки; НОД - операция поиска наибольшего общего делителя; - результат НОД операции на каждом из -шагов для -го маршрутизатора, соответственно - конечный ответ, то есть наибольший общий делитель. Операция НОД может быть реализована и, как Евклидовым алгоритмом, так и методом разложения на простые множители.

Количество пакетов, которое следует передавать по определенному каналу связи, предлагается рассчитывать по следующей формуле:

, (7)

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

Вследствие применения формулы (7) к маршрутизатору в топологии на рис. 1 получаются следующие результаты:

,

,

.

Исходя из, приведенного в 4 пункте, алгоритма следует, что по первому каналу связи маршрутизатор будет отправлять каждые 5 пакетов, в тоже время по второму каналу связи он будет отправлять 4 пакета. Таким образом, даже при нагрузке 1,8 Гбит/с маршрутизатор сможет без перегрузок распределить трафик пропорционально по каналам связи.

Одной из проблем данного подхода может стать возможность того, что пропускные способности каналов связи на маршрутизаторе, который принимает решение о балансировке нагрузки, будут достаточно большими, однако один из каналов связи в середине маршрута может иметь меньшую пропускную способность. К примеру, подобная ситуация могла бы возникнуть, в случае, если в топологии на рис. 1 канал связи между и имел бы пропускную способность 1 ГБ/с, а канал связи между и - 800 Мбит/с. В таком случае:

,

,

.

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

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



Выводы

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

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



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

1. Wallace K. CCNP Routing and Switching ROUTE 300-101 Official Cert Guide. - Cisco Press, 2014.

2. “How Does Unequal Cost Path Load Balancing (Variance) Work in IGRP and EIGRP?” - Электронный ресурс - техническая заметка на сайте компании Cisco, 03 июля 2009 г. - Режим доступа - http://www.cisco.com/c/en/us/support/docs/ip/enhanced-interior-gateway-routing-protocol-eigrp/13677-19.html

3. “Cisco Express Forwarding Overview” - Электронный ресурс - техническая заметка на сайте компании Cisco, - Режим доступа - http://www.cisco.com/c/en/us/support/docs/ip/enhanced-interior-gateway-routing-protocol-eigrp/13677-19.html

4. Adomnicгi C. Routing protocols behaviour under bandwidth limitation //Proceedings of International Conference on Information and Computer Networks. - 2012. - Т. 27. - С. 52-57.

5. Anvitha Prabhu, Shashank Singh, and Shridhar Dhodapkar “CEF Polarization” - Электронный ресурс - техническая заметка на сайте компании Cisco, 26 июля 2013 г. - Режим доступа - http://www.cisco.com/c/en/us/support/docs/ip/express-forwarding-cef/116376-technote-cef-00.html



Рецензент: д-р тех. наук, проф. А.В. Лемешко, Харьковский национальный университет радиоэлектроники, Харьков.

Автор: СНЕГУРОВ Аркадий Владиславович

Харьковский национальный университет радиоэлектроники, Харьков, кандидат технических наук, доцент, доцент кафедры телекоммуникационных систем.

Раб. тел. - (057) 702-10-67, E-Mail - arksn@rambler.ru

Автор: ЧАКРЯН Вадим Хазарович

Харьковский национальный университет радиоэлектроники, Харьков, аспирант кафедры телекоммуникационных систем.

Тел. - (093)-866-35-89, E-Mail - vadym.chakrian@gmail.com

Удосконалення алгоритму маршрутизації з балансуванням навантаження за шляхами нервінозначної вартості для протоколу EIGRP.

Размещено на Allbest.ru

...