Маршрутизация, термины, алгоритм Дейкстры (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 свободный канал, позволяет избежать очередей, может применяться в сетях АТМ) Телефонные алгоритмы коммутированных каналов: канал на кратчайшем, если занят - найти в обход.