Маршрутизация, термины, алгоритм Дейкстры (LS)

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

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

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

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

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

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

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

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

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

Алгоритмы:

Основанный на состоянии линии (Link State, Дейкстры):

В 3 С 5

2 5

3

А 2 1 F

1 2

D E

c(i,j) - стоимость линии от i до j

D(V) - стоимость пути от источника до адресата V - минимальная стоимость известная на пути от А до V.

p(V) - предпоследний узел на кратчайшем пути до V

N - мн-во узлов для которых известны пути.

1.Инициализация

N={A}; для всех V: если V смежный с А, то D(V) = C(a,V), p(V)=A) иначе D(v)=бесконечность

2. цикл пока все узлы не войдут в N

W не принадлежит N т.ч. D(w) min

добавляем w и N, обновить D(V), для всех V смежных с w

D(V) = min(D(V), D(W)+C(W,V))

конец цикла

N	D(B), p(B)	D(C), p(C)	D(D), p(D)	D(E), p(E)	D(F), p(F)
A	2,A	5,A	1,A	INF	INF
A,D	2,A	4,D	1,A	2,D	INF
A,D,E	2,A	3,E	1,A	2,D	4,E
A,D,E,B	2,A	3,E	1,A	2,D	4,E

бесконечным не будет. завершится за конечное число шагов.

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

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

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