Алгоритмы маршрутизации применяются для определения наилучшего пути пакетов от источника к приёмнику и являются основой любого протокола маршрутизации. Для формулирования алгоритмов маршрутизации сеть рассматривается как граф. При этом маршрутизаторы являются узлами, а физические линии между маршрутизаторами — рёбрами соответствующего графа. Каждой грани графа присваивается определённое число — стоимость, зависящая от физической длины линии, скорости передачи данных по линии или стоимости линии.
Классификация Алгоритмы маршрутизации можно разделить на: адаптивные и неадаптивные глобальные и децентрализованные статические и динамические
Требования точность простота надёжность стабильность справедливость оптимальность
Типы алгоритмов
Адаптивные алгоритмы
Описание принимают во внимание состояние линии
Плюсы и минусы +уменьшение среднего времени нахождения пакета в сети
+возможность динамической адаптации к состоянию сети -необходимо постоянно пересчитывать таблицы маршрутизации
Централизированные
Описание адаптивный централизированный алгоритм
Плюсы и минусы +RCC (Routing Control Center) обладает всей информацией о состоянии сети, что позволяет принимать оптимальные решения +узлы освобождены от подсчета таблиц маршрутизации -низкая надежность -узлы получают таблицы маршрутизации в различное время -концентрация трафика возле RCC
Изолированные
Описание Узел извлекает информацию из полученных пакетов.
Плюсы и минусы +нет перегрузок -медленная адаптация к состоянию сети (время конвергенции)
Распределённые
Описание дистанционно-векторный алгоритм, link state routing
Плюсы и минусы +лучшая адаптация -перегрузки
Неадаптивные алгоритмы
Описание не принимают во внимание текущее состояние сети, все маршруты рассчитываются до начала использования сети. Они в свою очередь подразделяются на алгоритмы, учитывающие топологию сети (spanning tree, flow based routing) и не учитывающие (flooding).
Плюсы и минусы +простота +хорошие результаты при неизменной топологии и нагрузке -невозможность реагирования на изменения -низкая скорость в неоднородных сетях
Примеры Shortest Path Flow based Flooding
Адаптивные алгоритмы
Централизированный
Адаптивный централизированный алгоритм ()
Описание В сети существует так называемый центр маршрутизации (Routing Control Center, RCC), который получает информацию от всех узлов об их соседних узлах, длине очереди и загрузке линии. В функции RCC входит сбор информации, подсчет оптимальных маршрутов для каждого узла, составление таблиц маршрутизации и рассылка их узлам.
Плюсы и минусы +RCC обладает всей информацией и может создавать «идеальные» маршруты +узлы освобождены от необходимости расчета таблиц маршрутизации -низкая надежность -время от времени требуется перерасчет таблиц маршрутизации -некорректная работа при разделенных сетях -IS получают информации в различное время -концентрация трафика возле RCC
Изолированный
Backward learning
Описание Каждый узел берет только нужную информацию из полученных пакетов. Таким образом, каждый узел знает отправителя пакетов и количество хопов, которые этот пакет прошёл. Затем происходит сравнение с данными в таблице маршрутизации, и если у полученного пакета меньшее количество хопов, то происходит обновление таблицы.
Плюсы и минусы +легкость реализации -проблемы при изменении топологии и нагрузки -не происходит обмен данными о маршрутизации между узлами
Распределённый
Дистанционно-векторный алгоритм ()
Описание Также известен как Distributed Bellman-Ford Routing или Ford Fulkerson Algorithm. Данный алгоритм является распределённым, итерационным и асинхронным. Его можно представить как: «расскажи своим соседям, как выглядит мир». Каждый узел ведёт таблицу маршрутизации с одной записью для каждого маршрутизатора подсети. Таблица представляет собой вектор, содержащий 2 компонента: выбранную линию и дистанцию. Узел оценивает дистанцию (количество хопов, задержку или длину очереди) до каждого соседа и рассылает её своим соседям, которые в свою очередь выполняют то же самое. В результате полученной информации каждый узел заново подсчитывает таблицу маршрутизации. Применяется в протоколе маршрутизации RIP. Впервые был применен в ARPANET.
Алгоритм Предположим, что таблица только что была получена от соседа X, причём Xi является предположением X о том, сколько длится путь до маршрутизатора i. Если маршрутизатор знает, что передача данных до X длится m, то он знает так же, что он может достичь любой маршрутизатор і через X за Xi+m.
Плюсы и минусы +самоорганизация +относительно простая реализация -плохая конвергенция («сходимость») -сложности при расширении сети
Пример При использовании алгоритма возникают проблемы при отключении одного из узлов от сети — проблема «Count to Infinity» (счет до бесконечности).
Предотвращение: Split Horizont Algorithm — «не говори мне то, что я сказал тебе»
Маршрутизация по состоянию канала
Описание Алгоритм, относящийся к адаптивным алгоритмам и основанный на анализе состояния связей. Его можно представить как: «расскажи миру о том, кто твои соседи». Сначала узел знает только своих соседей и метрику связей, соединяющих его с ними. В процессе обмена информацией с соседними узлами узел получает информацию о топологии сети, при этом обменивается только информацией о происшедших изменениях. В результате каждый узел знает всю топологию сети. Впервые был применен в ARPANET в 1979 году и пришёл на смену дистанционно-векторному алгоритму. Причинами перехода служили: рост пропускной способности каналов и отсутствие её учёта в дистанционно-векторном алгоритме медленность дистанционно-векторного алгоритма, вызванная «счетом до бесконечности»
Алгоритм определение адресов соседних узлов: новые узлы рассылают приветствие (HELLO-сообщения), соседние узлы сообщают свои адреса происходит при помощи рассылки HELLO-запросов измерение метрики линий или времени передачи данных до соседних узлов происходит в результате рассылки эхо-сообщений организация собранных данных в пакет, содержащий личный адрес, порядковый номер (для избежания повторений), возраст (для отброса устаревшей информации), дистанцию рассылка пакетов всем узлам сети (flooding) подсчет маршрутов на основе полученной от других узлов информации
Широковещательная маршрутизация ()
Терминология unicast — 1:1 multicast — 1:n broadcast — 1:* (1:all)
Простые методы индивидуальная отправка пакетов каждому получателю, что предъявляет определенные требования к сети, излишняя трата полосы пропускания, отправитель должен знать всех получателей flooding: слишком много повторяющихся пакетов
Multidestination Routing Каждый пакет содержит список всех целей. Каждый узел создает для каждого исходящего соединения копию пакета, которая содержит только адреса тех узлов, которые достижимы через это соединение.
Многоадресная рассылка
Алгоритм связующего дерева
Описание Связующее дерево (Spanning tree): граф, не содержащий петель. Связующее дерево известно всем узлам. В соответствии с этим каждый узел рассылает копии пакетов
Reverse path forwarding (Reverse path flooding) Алгоритм является самым простым и неадаптивным вариантом. Каждый полученный пакет пересылается по всем линиям, за исключением той, через которую он был получен. При этом только отправитель должен знать все связующее дерево. Алгоритм: Каждый маршрутизатор знает путь, который он должен использовать для unicast-пакетов. При получении пакета проверяется, был ли пакет получен по линии, которая обычно используется для 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 40 50 100 0.195 DF 24 25 1000 0.117 EH 26 50 41.67 0.127 FG 1 100 10.1 0.005 GH 7 62.5 18.02 0.034 DG 7 62.5 18.02 0.034 подсчет общей задержки Toverall = ∑Ti•Wi Получаем: Toverall=162.531msec. Так как полученное значение слишком велико, то его можно уменьшить за счет замены пути с самой большой задержкой DF(Ti, max = 1000msec) на путь D->G->F
Flooding (алгоритм «затопления») Является самым простым алгоритмом маршрутизации для распространения информации по сети. При получении пакета каждый узел пересылает его соседним узлам за исключением того, от которого пришёл пакет.
Данный алгоритм обладает низкой эффективностью из-за повышенной загрузки сети.
Для улучшения эффективности алгоритма используются следующие способы:
Hop counter. В этом случае к каждому пакету прибавляется счетчик хопов. Отправитель устанавливает этот счетчик и каждый узел сети, который его пересылает, уменьшает этот счетчик на 1.
Flooding with Acknowledge («затопление с подтверждениями»). Одной из проблем простого алгоритма «затопления» является то, что отправитель не знает о том, достиг ли пакет всех узлов сети. Каждый из узлов сети отправляет подтверждение о получении, если он получил подтверждение от всех узлов, которым он отправлял пакеты.
Unique resend. Каждая станция запоминает пересланные пакеты и не посылает их ещё раз. Данный метод оптимизации очень продуктивен в сетях с топологией, отличной от дерева
Другие алгоритмы
Multipath Routing
Описание