2.3.2. Каталог узлов и оптимальных маршрутов для статических ткс

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

Для поиска оптимального маршрута в статических ТКС можно использовать, например, алгоритм Дейкстры [3,4] или алгоритм Беллмана-Форда [17].

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

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

Для каждого узла ТКС сформируем локальные БД в виде таблиц оптимальных маршрутов. Назовём эти БД каталогами узлов. Построим общую матрицу оптимальных маршрутов и назовём её центральным каталогом маршрутов. Для примера рассмотрим ТКС с N=5 узлами и двухсторонними связями и весами w_ij, граф которой изображен на рис.2.3.1.

a₁

a₂

a₃

a₄

a₅

1

1

3

1

1

3

3

6

2

3

8

5

2

1

3

2

Рис.2.3.1. Граф ТКС с 5 узлами и двухсторонними связями с весами

Тогда центральный каталог маршрутов будет иметь вид, представленный на рис. 2.3.2., а каталоги узлов будут представлены табличными БД, изображёнными на рис.2.3.3.

получатель\источник	a1	a2	a3	a4	a5
a1	--	a1	a5	a1	a4
a2	a2	--	a5	a2	a4
a3	a4	a3	--	a5	a3
a4	a4	a4	a5	--	a4
a5	a4	a4	a5	a5	--

Рис. 2.3.2. Центральный каталог маршрутов

Каталог узла a2
получатель	следующий узел
a1	a1
a3	a3
a4	a4
a4	a4

Каталог узла a1
получатель	следующий узел
a2	a2
a3	a4
a4	a4
a5	a4

Каталог узла a4
получатель	следующий узел
A1	a1
A2	a2
A3	a5
A5	a5

Каталог узла a5
получатель	следующий узел
a1	a4
a2	a4
a3	a3
a4	a4

Каталог узла a3
получатель	следующий узел
a1	a5
a2	a5
a4	a5
a5	a5

Рис.2.3.3. Каталоги узлов ТКС при оптимальной статической маршрутизации