Неадаптивные алгоритмы

Описание

не принимают во внимание текущее состояние сети, все маршруты рассчитываются до начала использования сети. Они в свою очередь подразделяются на алгоритмы, учитывающие топологию сети (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, то он знает так же, что он может достичь любой маршрутизатор і через X за X_i+m.

Плюсы и минусы

+самоорганизация +относительно простая реализация -плохая конвергенция («сходимость») -сложности при расширении сети

Пример

При использовании алгоритма возникают проблемы при отключении одного из узлов от сети — проблема «Count to Infinity» (счет до бесконечности).

Предотвращение: Split Horizont Algorithm — «не говори мне то, что я сказал тебе»

Маршрутизация по состоянию канала

англ.Link state routing

Описание

Алгоритм, относящийся к адаптивным алгоритмам и основанный на анализе состояния связей. Его можно представить как: «расскажи миру о том, кто твои соседи». Сначала узел знает только своих соседей и метрику связей, соединяющих его с ними. В процессе обмена информацией с соседними узлами узел получает информацию о топологии сети, при этом обменивается только информацией о происшедших изменениях. В результате каждый узел знает всю топологию сети. Впервые был применен в ARPANETв 1979 году и пришёл на смену дистанционно-векторному алгоритму. Причинами перехода служили:

• рост пропускной способности каналов и отсутствие её учета в дистанционно-векторном алгоритме

• медленность дистанционно-векторного алгоритма, вызванная «счетом до бесконечности»