Цикл: Найти W, не входящий в N, такой что D(W) минимальна. Добавить W к N. Обновить D(v) для всех v смежных с W и не входящих в N: D(v)=min(D(v), D(W), D(W,v)). По всем узлам в N.
Алгоритм дистанционно-векторной марштуризации является распределенным, итерационным и асинхронным. Процесс продолжается пока соединенные узлы не перестают обмениваться информацией. Асинхронный поскольку не требует, чтобы все узлы работали в жесткой взаимосвязи. Каждый узел имеет свою таблицу расстояний, строка для адресата и столбец для каждого ближайшего соседа. Dx(y,z)=C(x,z)+minw(Dz(y,w)).
Каждый узел должен знать наименьшую стоимость каждого пути от каждого соседа до каждого адресата. Как только узел вычисляет новую стоимость он должен сообщить каждому из своих соседей.
Алгоритм инициализация: Для всех всех смежных узлов V: Dx(*,v)=бесконечности // *-любой узел. Dx(v,v)=C(x,v). Для всех адресатов Y- послать minwD(y,W) каждому соседу.
Цикл:
Ждать(пока не изменится стоимость ЛС с соседом v или пока не будет получено обновление от соседа v). Если (стоимость C(x,v) изменилась на d) /*изменение стоимости путей ко всем адресам через соседа v на величину d*/ /*d-может быть как положительным так и отрицательным*/ Для всех адресов Y: Dx(y,v)= Dx(y,v)+d. Иначе если (получено обновление от v адресат Y) /* изменение кратчайшего пути от v до Y */ /* Узел v послал новое значение minwDY (Y,W), назовем его newVal */ для одного адресата y: Dx(Y,v)=C(x,v)+ newVal . Если получим новое значение minwDX (Y,W) для Y послать новое значение minwDX (Y,W) всем соседям. Конец цикла.
30. Алгоритмы маршрутизации. Сравнение алгоритмов маршрутизации.
Основы маршрутизации:
Определение пути занимается протокол маршрутизации. Задачи выбора пути пакета сводится к задачи от маршрутизатора источника к маршрутизатору приемника.
Алгоритм маршрутизации: находим оптимальный путь от маршрутизатора источника к маршрутизатору приемника для заданого множества маршрутизации и линий соединяющих их.
Если рассматривать сеть как граф то узлы графа это маршрутизаторы, а ребра графа- это физические линии связи.
Стоимость зависит от физической длинны линии, скорости передачи по линии и др.
При рассмотрение сети в виде графа для определения маршрута с минимальной стоимостью, необходимо найти последовательность линий такую что:
-первая линия соединена с источником. –последняя линия соединена с адресатом. –для всех i-линий с номерами i и i-1 соединены с одним и тем же узлом. –для пути с минимальной стоимостью сумма стоимостей всех линий пути является минимальной, по всем возможным путям.
Все маршруты можно разбить на 2 класса: 1.Глобальный класс. 2.Детерцентрализованный класс (вычисление пути происходит итерационным, распределенным образом).
Алгоритм Дейкстры вычисляет путь с наименьшей стоимостью. Алгоритм циклический.
D(v)-стоимость пути от узла источника до узла адресата V минимальная на данной итерации.
P(v)-предыдущий узел на текущем пути с наименьшей стоимостью от источника до узла V.
N-множество узлов для которых на данной итерации известны пути с наименьшей стоимостью.
1 этап инициализации N=
