Информатика и выч. техника \ Сетевое программное обеспечение

Методы локальной пользовательской маршрутизации, страница 2

Получатель

Смежный

2

2

3

4

4

4

5

4

6

4

Получено решение (маршрутная таблица) для узла с номером 1. Эта таблица расчитывается для каждого узла отдельно. Алгоритм может быть реализован самостоятельно каждым узлом. Недостатком является необходимость информации о стоимости всех каналов сети.

Подход Форда-Фолкирсона

Каждому узлу пристваивается метка (N, D(v)), где D(v) – текущая величина минимального расстояния от узла v до получателя (узел 1), и N – смежный с v узел, через который достигнуто это минимальное расстояние.

Шаг0. Строим таблицу, где первый столбец – номер итерации, остальные – номера узлов. Формируем первую строку: (1, l(v, 1)) для узлов v, которые смежны с узлом 1. Для узлов, несмежных с 1 (·,µ).

Шаг k (k = 1,2,…). Пересчет строки таблицы.

Алгоритм заканчивает работу, если в текущей итерации не была изменена ни одны метка.

Пример:
1

2

3

4

5

6

0

(1,0)

( ,µ)

( ,µ)

( ,µ)

( ,µ)

( ,µ)

1

(1,0)

(1,2)

(1,5)

(1,1)

(4,2)

(5,4)

2

(1,0)

(1,2)

(5,3)

(1,1)

(4,2)

(5,4)

3

(1,0)

(1,2)

(5,3)

(1,1)

(4,2)

(5,4)
Скачать файл