Основы маршрутизации:
Определение пути занимается протокол маршрутизации. Задачи выбора пути пакета сводится к задачи от маршрутизатора источника к маршрутизатору приемника.
Алгоритм маршрутизации: находим оптимальный путь от маршрутизатора источника к маршрутизатору приемника для заданого множества маршрутизации и линий соединяющих их.
Если рассматривать сеть как граф то узлы графа это маршрутизаторы, а ребра графа- это физические линии связи.
Стоимость зависит от физической длинны линии, скорости передачи по линии и др.
При рассмотрение сети в виде графа для определения маршрута с минимальной стоимостью, необходимо найти последовательность линий такую что:
-первая линия соединена с источником. –последняя линия соединена с адресатом. –для всех i-линий с номерами i и i-1 соединены с одним и тем же узлом. –для пути с минимальной стоимостью сумма стоимостей всех линий пути является минимальной, по всем возможным путям.
Все маршруты можно разбить на 2 класса: 1.Глобальный класс. 2.Детерцентрализованный класс (вычисление пути происходит итерационным, распределенным образом).
Алгоритм Дейкстры вычисляет путь с наименьшей стоимостью. Алгоритм циклический.
D(v)-стоимость пути от узла источника до узла адресата V минимальная на данной итерации.
P(v)-предыдущий узел на текущем пути с наименьшей стоимостью от источника до узла V.
N-множество узлов для которых на данной итерации известны пути с наименьшей стоимостью.
1 этап инициализации N=
