Алгоритмы маршрутизации
Алгоритмы маршрутизации применяются для определения оптимального пути пакетов от источника к приемнику и являются основой любого протокола маршрутизации. Для формулирования алгоритмов маршрутизации сеть рассматривается как граф. При этом маршрутизаторы являются узлами, а физические линии между маршрутизаторами — ребрами соответствующего графа. Каждой грани графа присваивается определенное число — стоимость, зависящяя от физической длины линии, скорости передачи данных по линии или финансовой стоимости линии.
Классификация[править | править код]
Алгоритмы маршрутизации можно разделить на:
- адаптивные и неадаптивные
- глобальные и децентрализованные
- статические и динамические
Требования[править | править код]
- точность
- простота
- надежность
- стабильность
- справедливость
- оптимальность
Типы алгоритмов[править | править код]
Адаптивные алгоритмы[править | править код]
Описание[править | править код]
принимают во внимание актуальное состояние линии
Плюсы и минусы[править | править код]
+возможность адаптации к актуальному состоянию сети
-необходимо постоянно пересчитывать таблицы маршрутизации
Централизированные[править | править код]
Описание[править | править код]
адаптивный централизированный алгоритм
Плюсы и минусы[править | править код]
+RCC обладает всей информацией о состоянии сети, что позволяет принимать оптимальные решения
+узлы освобождены от подсчета таблиц маршрутизации
-низкая надежность
-узлы получают таблицы маршрутизации в различное время
-концентрация трафика возле RCC
Изолированные[править | править код]
Описание[править | править код]
Узел извлекает информацию из полученных пакетов.
Плюсы и минусы[править | править код]
+нет перегрузок
-медленная адаптация к актуальному состоянию сети (время конвергенции)
Распределенные[править | править код]
Описание[править | править код]
дистанционно-векторный алгоритм, link state routing
Плюсы и минусы[править | править код]
+лучшая адаптация
-перегрузки
Неадаптивные алгоритмы[править | править код]
Описание[править | править код]
не принимают во внимание актуальное состояние сети, все маршруты рассчитываются до начала использования сети. Они в свою очередь подразделяются на алгоритмы, учитывающие топологию сети (spanning tree, flow based routing) и не учитывающие (flooding).
Плюсы и минусы[править | править код]
+простота
+хорошие результаты при неизменной топологии и нагрузке
-невозможность реагирования на изменения
-низкая скорость в неоднородных сетях
Примеры[править | править код]
- Shortest Path
- Flow based
- Flooding
Адаптивные алгоритмы[править | править код]
Централизированный[править | править код]
Адаптивный централизированный алгоритм[править | править код]
(англ. adaptive centralized routing)
Описание[править | править код]
В сети существует так называемый Routing Control Center (RCC), который получает информацию от всех узлов об их соседних узлах, актуальную длину очереди и загрузки линии. В функции RCC входит сбор информации, подсчет оптимальных маршрутов для каждого узла, составление таблиц маршрутизации и рассылка их узлам.
Плюсы и минусы[править | править код]
+RCC обладает всей информацией и может создавать «идеальные» маршруты
+узлы освобождены от необходимости расчета таблиц маршрутизации
-низкая надежность
-время от времени требуется перерасчет таблиц маршрутизации
-некорректная работа при разделенных сетях
-IS получают информации в различное время
-концентрация трафика возле RCC
Изолированный[править | править код]
Backward learning[править | править код]
Описание[править | править код]
Каждый узел берет только нужную информацию из полученных пакетов. Таким образом, каждый узел знает отправителя пакетов и количество хопов, которые этот пакет прошел. Затем происходит сравнение с данными в таблице маршрутизации, и если у полученного пакета меньшее количество хопов, то происходит обновление таблицы.
Плюсы и минусы[править | править код]
+легкость реализации
-проблемы при изменении топологии и нагрузки
-не происходит обмен данными о маршрутизации между узлами
Распределенный[править | править код]
Дистанционно-векторный алгоритм[править | править код]
(англ. distance vector routing)
Описание[править | править код]
Также известен как Distributed Bellman-Ford Routing или Ford Fulkerson Algorithm. Данный алгоритм является распределенным, итерационным и асинхронным. Его можно представить как: «расскажи своим соседям, как выглядит мир». Каждый узел ведет таблицу маршрутизации с одной записью для каждого маршрутизатора подсети. Таблица представляет собой вектор, содержащий 2 компонента: выбранную линию и дистанцию. Узел оценивает дистанцию (количество хопов, задержку или длину очереди) до каждого соседа и рассылает ее своим соседям, которые в свою очередь выполняют то же самое. В результате полученной информации каждый узел заново подсчитывает таблицу маршрутизации. Применяется в протоколе маршрутизации RIP. Впервые был применен в ARPANET.
Алгоритм[править | править код]
Предположим, что таблица только что была получена от соседа X, причем Xi является предположением X о том, сколько длится путь до маршрутизатора i. Если маршрутизатор знает, что передача данных до X длится m, то он знает так же, что он может достичь любой маршрутизатор i через X за Xi+m.
Плюсы и минусы[править | править код]
+самоорганизация
+относительно простая реализация
-плохая конвергенция
-сложности при расширении сети
Пример[править | править код]
При использовании алгоритма возникают проблемы при отключении одного из узлов от сети — проблема «Count to Infinity» (счет до бесконечности).
Предотвращение: Split Horizon Algorithm — «не говори мне то, что я сказал тебе»
Алгоритм состояния канала[править | править код]
англ. Link state routing
Описание[править | править код]
Алгоритм, относящийся к адаптивным алгоритмам и основанный на состоянии связей. Его можно представить как: «расскажи миру о том, кто твои соседи». Сначала узел знает только своих соседей и стоимости связей, соединяющих его с ними. В процессе обмена информацией с соседними узлами узел получает информацию о топологии сети, при этом обменивается только информация о происшедших изменениях. В результате каждый узел знает всю топологию сети. Впервые был применен в ARPANET в 1979 году и пришел на смену дистанционно-векторному алгоритму. Причинами перехода служили:
- рост пропускной способности каналов и отсутствие ее учета в дистанционно-векторном алгоритме
- медленность дистанционно-векторного алгоритма, вызванная «счетом до бесконечности»
Алгоритм[править | править код]
- определение адресов соседних узлов: новые узлы рассылают приветствие (HELLO-сообщения), соседние узлы сообщают свои адреса
- происходит при помощи рассылки HELLO-запросов
- измерение стоимости линий или времeни передачи данных до соседних узлов
- происходит в результате рассылки эхо-сообщений
- происходит в результате рассылки эхо-сообщений
- организация собранных данных в пакет, содержащий личный адрес, sequence number (для избежания повторений), age (для отброса устаревшей информации), дистанцию
- рассылка пакетов всем узлам сети (flooding)
- подсчет маршрутов на основе полученной от других узлов информации
Широковещательная маршрутизация[править | править код]
(англ. broadcast routing)
Терминология[править | править код]
unicast — 1:1
multicast — 1:n
broadcast — 1:всем
Простые методы[править | править код]
- индивидуальная отправка пакетов каждому получателю, что предъявляет определенные требования к сети, излишняя трата полосы пропускания, отправитель должен знать всех получателей
- flooding: слишком много повторяющихся пакетов
Multidestatination Routing[править | править код]
Каждый пакет содержит список всех целей. Каждый узел создает для каждого исходящего соединения копию пакета, которая содержит только адреса тех узлов, которые достижимы через это соединение.
Многоадресная рассылка[править | править код]
англ. multicast routing
Алгоритм связующего дерева[править | править код]
англ. spanning tree
Описание[править | править код]
Связующее дерево (Spanning tree): дерево, не содержащее петель. Связующее дерево известно всем узлам. В соответствии с этим каждый узел рассылает копии пакетов
Reverse path forwarding (Reverse path flooding)[править | править код]
Алгоритм является самым простым и неадаптивным вариантом. Каждый полученный пакет пересылается по всем линиям, за исключением той, через которую он был получен. При этом только отправитель должен знать все связующее дерево. Алгоритм: Каждый маршрутизатор знает путь, который он должен использовать для unicast-пакетов. При получении пакета проверяется, был ли пакет получен по линии, которая обычно используется и пересылается по всем линиям, за исключением той, через которую он был получен. В противном случае пакет отбрасывается.
Reverse path broadcast[править | править код]
В отличии от Reverse path forwarding пакеты отправляются только по линиям, по которым другие узлы принимают данные
Неадаптивные[править | править код]
Shortest Path Routing[править | править код]
Описание[править | править код]
Данный алгоритм подсчитывает наименьший маршрут от корня дерева до узлов. Смысл заключается в создании пучка узлов Q, для которых уже был определен оптимальный маршрут. Оператор генерирует таблицы маршрутизации, которые загружаются при его инициализации и более не изменяются. Основывается на алгоритме Дейкстры.
Алгоритм[править | править код]
Наименьшее расстояние от A до D
- узел A помечается как рассматриваемый
- присвоить всем соседним узлам значение с дистанцией до рассматриваемого узла B(2,A), G(6,A) и добавить их в список кандидатов
- выбрать из списка кандидатов узел с наименьшей дистанцией B(2,A)
- пометить этот узел как рассматриваемый и добавить его в дерево
- перейти к пункту 2
Плюсы и минусы[править | править код]
+простота
+хорошие результаты при постоянной топологии сети и нагрузке
Flow-Based Routing[править | править код]
Описание[править | править код]
Данный алгоритм является одним из неадаптивных алгоритмов. Он учитывает не только дистанцию между маршрутизаторами, но и загрузку сети. Полезен для нахождения маршрута для больших дистанций с большими задержками в доставке пакетов
Пример[править | править код]
Дан граф для capacity и матрица трафика
- Подсчет загрузки каждой линии
- взять одно из ребер графа
- найти, где оно встречается в таблице
- сложить все скорости из таблицы для этого ребра
Line | λi (packts/sec) |
---|---|
AB | 3(AB) + 7(ABC) + 7(BAD) + 4(BAF) + 3(BADG) =24 |
AD | 4(AD) + 2(ADE) + 2(ADG) + 5(ADEH) + 7(BAD) + 3(BADG) = 23 |
AF | 5(AF) + 4(BAF) = 9 |
BC | 7(ABC) + 3(BC) + 4(BCH) = 14 |
BE | 3(BE) = 3 |
CE | 7(CED) + 5(CE) + 3(CEDF) = 15 |
CH | 4(BCH) + 5(CHG) + 3(CH) = 12 |
DE | 2(ADE) + 5(ADEH) + 7(CED) + 3(CEDF) + 2(DE)+ 9(DEH) + 3(EDF)+ 9(FDEH) = 40 |
DF | 3(CEDF)+ 9(DF) + 3(EDF)+ 9(FDEH) = 24 |
EH | 5(ADEH)+ 9(DEH)+ 1(EHG)+ 2(EH) + 9(FDEH) = 26 |
FG | 1(FG) = 1 |
GH | 1(GH) + 1(EHG) + 5(CHG) = 7 |
DG | 2(ADG) + 3(BADG) + 2(DG) = 7 |
- подсчет задержки для каждого графа по формуле Ti = 1/(μCi-λi).
Line | λi (packts/sec) | μCi (packts/sec) | Ti (msec) |
---|---|---|---|
AB | 24 | 50 | 38.46 |
AD | 23 | 50 | 37.04 |
AF | 9 | 37.5 | 35.09 |
BC | 14 | 25 | 90.91 |
BE | 3 | 50 | 21.28 |
CE | 15 | 75 | 16.67 |
CH | 12 | 50 | 26.32 |
DE | 40 | 50 | 100 |
DF | 24 | 25 | 1000 |
EH | 26 | 50 | 41.67 |
FG | 1 | 100 | 10.1 |
GH | 7 | 62.5 | 18.02 |
DG | 7 | 62.5 | 18.02 |
- Подсчет стоимости каждого ребра по формуле: Wi = λi/∑λi.
Line | λi (packts/sec) | μCi (packts/sec) | Ti (msec) | Wi |
---|---|---|---|---|
AB | 24 | 50 | 38.46 | 0.117 |
AD | 23 | 50 | 37.04 | 0.112 |
AF | 9 | 37.5 | 35.09 | 0.044 |
BC | 14 | 25 | 90.91 | 0.068 |
BE | 3 | 50 | 21.28 | 0.015 |
CE | 15 | 75 | 16.67 | 0.073 |
CH | 12 | 50 | 26.32 | 0.059 |
DE | bgcolor="#F9 |