26. Маршрутизация, алгоритм Беллмана-Форда (dv).

Для того чтобы переместить пакеты от хоста-отпарвителя к хосту-получателя, сетевой уровень должен определить путьилимаршрутследования пакетов. Этим занимаетсяпротокол маршрутизациисетевого уровня. Хост напрямую подключен к одному из маршрутихзаторов -маршрутизатор по умолчанию(первого ретрансляционного участка). Задача выбора пути от источника к приемнику сводится к выбору пути пакета от маршрутизатора-источника к маршрутизатору-приемнику -алгоритм маршрутизации. Алгоритм находит «оптимальный» путь (с минимальной стоимостью).Рассмотрим граф: узлы - маршрутизаторы, дуги - линии связи. Каждой линии связи соответствует некоторое значение, представляющее «стоимость» пересылке пакета по этой линии.

Протоколы: общедоступные: RIP,BGP,OSPF; частный:EIGRP.

Глобальный алгоритм маршрутизациинаходит путь с наименьшей стоимостью от отправителя до получателя с помощью инф о сети. Особенность: обладает полной инф о топологии сети и стоимости линий.

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

Алгоритмы: статические и динамические

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

Динамическийзапускается либо периодически, либо в ответ на изменение топологии или стоимости линий (по протоколу).

Может быть смесь.

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

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

Децентрализованный алгоритм (Беллмана-форда, дистанционно векторной маршрутизации): основан на рассылке сообщений (при изменении стоимости пути (событие: пришло сообщение от кого-то или изменение стоимости известной линии связи)), асинхронный (управляется событиями), нет явного критерия остановки (после какой-то итерации строка не изменится, новое сообщение посылаться не будет), не требует знания всей конструкции сети.

Алгоритм: y- 2 -x- 1 -z- 7 -y

1. Инициализация: в таблице бесконечности дл диагональных (.) известные длины пути D^X(*,V) =INF,D^X(V,V) =C(X,V). Для всех адресатовmin_WD(Y,W).

2. Ожидание события: (пока не придет сообщение, изменение стоимости линии связи)

а. Если изменилась стоимость С(X,V) наd=> меняется стоимость в таблице. Для всех адресатовyD^X(Y,V) +=dтаблица обновляется. Если появился новыйmin=> рассылка всем соседям

б. Если обновление - новое значение от соседа wадресатy. ОбновлениеD^X(Y,V) =C(X,V) +newval. Если получается новоеminзначение, то рассылка всем соседям.

3. Снова ждет пока что-нибудь не случится.

D^X	Y	Z		D^X	Y	Z
Y	2	INF		Y	2	8
Z	INF	7		Z	3	7
D^Y	X	Z		D^Y	X	Z
X	2	INF		X	2	8
Z	INF	1		Z	9	1
D^Z	X	Y		D^Z	X	Y
X	7	INF		X	7	3
Y	INF	1		Y	9	1

На 3 шаге обновлений нет

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

Сравнение: 1) скорость схождения: Д: не > NБФ =INF; 2) живучесть (устойчивость к ошибкам) БФ ниже чем у Д; 3) сложность сообщений.

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