3.2. Основные алгоритмы динамической маршрутизации

3.2.1. Алгоритм Беллмана-Форда и его модификации

Алгоритм Беллмана-Форда является распределенным алгоритмом оптимальной маршрутизации потоков данных в ТКС. Он предназначен для вычисления оптимальных маршрутов передачи пакетов данных от данного узла-источника к остальным узлам-приёмникам ТКС с фиксированной динамикой [6,17].

Алгоритм выполняется итеративно в каждом узле ТКС. На каждой итерации алгоритма вычисляются оптимальные маршруты передачи пакетов данных от узла-источника до остальных узлов ТКС, причем число составляющих их ребер не превосходит номер итерации. Это означает, что на первом шаге алгоритма будут определяться оптимальные 1-звенные маршруты, на втором шаге – оптимальные 2-звенные маршруты, на третьем шаге – оптимальные 3-звенные маршруты и т.д.

Рассмотрим описание работы алгоритма для конкретного узла ТКС.

Введём следующие обозначения:

G(s,f,w) – ориентированный граф ТКС;

– узел-источник;

– стоимость ребра , причём:

w(i,i)=0; , если узлы i и j не соединены;

, если узлы i и j соединены;

h – номер итерации, определяющий число звеньев рассматриваемых маршрутов;

L_h(j,v) – стоимость оптимального маршрута от узла j до узла v, содержащего не более h рёбер (каналов связи).

Требуется построить оптимальные маршруты от узла-источника s₀ до остальных узлов ТКС и вычислить их стоимости.

Работа алгоритма:

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

для всех ;

L_h(s₀, s₀)=0 для всех h;

2. Итерация.

Для каждого узла вычисляем величину

. (3.2.1)

Новый маршрут до узла v получается из оптимального маршрута от узла j до узла v, на котором достигается минимум функционала и ребра (s₀, j). При этом старый маршрут до узла v выбрасывается.

На каждой итерации для каждого узла-приемника v алгоритм сравнивает стоимости возможных (h+1)-звенных маршрутов от s₀ до v со стоимостью маршрута, установленного в конце предыдущей итерации. Если предыдущий, более короткий маршрут (с меньшим числом ребер), имеет меньшую стоимость, он сохраняется на новой итерации. В противном случае определяется новый (h+1)-звенный маршрут от s₀ до v. Этот маршрут состоит из h-звенного маршрута от s₀ до некоторого узла j, определенного на предыдущей итерации, и ребра (j,v).

Для статических (фиксированных) ТКС с N узлами работа алгоритма заканчивается после N-1 итерации.

Для динамических ТКС с изменяющимися стоимостями (весами) каналов связи и топологией работа алгоритма ведется непрерывно.

В процессе работы алгоритма, как видно из формулы (3.2.1), на каждой итерации узлу-источнику достаточно информации о стоимостях (весах) каналов связи до его соседей и информации об оптимальных маршрутах от соседей до остальных узлов. Поэтому динамическая модификация работы алгоритма выглядит следующим образом: на каждой итерации каждый узел ТКС обменивается информацией о текущих оптимальных маршрутах со своими соседями, а также “отслеживает” изменения стоимостей (весов) исходящих из него каналов связи. После этого алгоритм пересчитывает стоимости и обновляет множество оптимальных маршрутов до остальных узлов согласно формуле (3.2.1).

Алгоритм Беллмана-Форда имеет вычислительную сложность O(N³), где N – число узлов в сети.