Комплекс программ статической маршрутизации с построением матрицы кратчайших путей

Узел ТКС n Î Nodes, который работает по алгоритму статической маршрутизации с построением матрицы кратчайших путей, хранит таблицу маршрутизации RouteTable (n).

Таблица маршрутизации загружается в узел ТКС перед началом его работы и не изменяется с течением времени. Для маршрутизации пакетов данных используется стандартная процедура маршрутизации, основанная на обработке таблицы маршрутизации (которая была описана в предыдущем параграфе).

Для вычисления матрицы кратчайших путей можно воспользоваться алгоритмами Дейкстры или Уоршолла-Флойда

На вход алгоритма подается ориентированный взвешенный граф G = (V, E), где каждая вершина соответствует узлу связи ТКС, а дуга – каналу связи. В качестве стоимости дуг берется задержка времени в соответствующем канале связи ТКС. Кроме того, на вход алгоритма подается узел r, для которой будет строиться дерево кратчайших путей.

В алгоритме с каждым узлом ТКС ассоциируются следующие данные:

1. w – длина кратчайшего известного пути до этого узла из корня;

2. p – предыдущий узел на кратчайшем известном до этого узла пути;

3. f – флаг, указывающий на принадлежность вершины к списку «закрытых»узлов, т.е. узлов, для которых уже найден оптимальный путь.

Перед началом работы алгоритма полагаем

w (r) = 0, f (r) = true для всех v Î V - r w (v) = +¥, p (v) = null, f (v) = false. (9.11)

Переменной c_i обозначим текущий узел ТКС на i -том шаге. До тех пор, пока c_i ¹ 0, повторяем следующие шаги:

1) Для " u Î V: $e = (c_i, u) Î E обновляем w_i+1 (u) и p_{i +1}(u) следующим образом:

w_i+1 (u) = min(w_i (u), w_i (c_i) + l (e)), (9.12)

где l (e) – стоимость ребра e;

2) Определяем

p_{i +1}(u) = (9.13)

f_i+1 (c_i) = true. (9.14)

Далее определим

, (9.15)

где Open_i+1 = { u Î V | f_i+1 (u) = false }, (9.16)

Когда c_i = 0, загружаем в узел r таблицу маршрутизации p.