Алгоритм

1. определение адресов соседних узлов: новые узлы рассылают приветствие (HELLO-сообщения), соседние узлы сообщают свои адреса

происходит при помощи рассылки HELLO-запросов

2. измерение метрики линий или времени передачи данных до соседних узлов

происходит в результате рассылки эхо-сообщений

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

4. рассылка пакетов всем узлам сети (flooding)

5. подсчет маршрутов на основе полученной от других узлов информации

Широковещательная маршрутизация

(англ.broadcast routing) 

Терминология

unicast— 1:1multicast— 1:nbroadcast— 1:* (1:all)

Простые методы

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

• flooding: слишком много повторяющихся пакетов

Multidestination Routing

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

Многоадресная рассылка

англ.multicast routing

Алгоритм связующего дерева

англ.spanning tree 

Описание

Связующее дерево (Spanning tree): граф, не содержащий петель. Связующее дерево известно всем узлам. В соответствии с этим каждый узел рассылает копии пакетов

Reverse path forwarding (Reverse path flooding)

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

Reverse path broadcast

В отличие от Reverse path forwarding пакеты отправляются только по линиям, по которым другие узлы принимают данные

Shortest Path Routing

Описание

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

Алгоритм

Наименьшее расстояние от A до D

1. узел A помечается как рассматриваемый

2. присвоить всем соседним узлам значение с дистанцией до рассматриваемого узла B(2,A), G(6,A) и добавить их в список кандидатов

3. выбрать из списка кандидатов узел с наименьшей дистанцией B(2,A)

4. пометить этот узел как рассматриваемый и добавить его в дерево

5. перейти к пункту 2

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

+простота +хорошие результаты при постоянной топологии сети и нагрузке

Неадаптивные

Flow-Based Routing

Описание

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

40