А. Route Table и Route Distance

Таблица маршрутизации в начальный момент времени для каждого узла ТКС содержит только null. Поэтому сначала маршрутизатор не знает, по какому каналу связи ТКС посылать пакеты, предназначенные не ему.

Вектор оценок расстояний до всех узлов подсети RouteDistance (n) в начальный момент времени заполнен +¥.

В определённые моменты времени маршрутизатор (например, через каждые 10 минут) производит обновление своей таблицы маршрутизации и вместе с ней вектора оценок расстояний до остальных узлов подсети.

Узел n Î Nodes, используя таблицы состояния каналов связи LinkState (n, m), формирует графовую модель ТКС, в которой ребру, соединяющему вершины подсети – маршрутизаторы s, d Î Nodes, приписывается вес LinkState (n, s)(d). Далее маршрутизатор вычисляет кратчайшие пути (маршруты) до всех узлов подсети ТКС, используя, например, алгоритм Дейкстры.

Под путём на графе понимается последовательность вершин вида

route(n, x) = (route(n, x) ₀, route(n, x) ₁, …, route(n, x) _N) route(n, x) _i Î Nodes (9.22)

для которой выполняются следующие условия:

route(n, x) ₀ = n route(n, x) _N = x, (9.23)

" i = 0, …, N-1 $ l Î Outlinks (route(n, x) _i): dest(l) = route(n, x) _i+1. (9.24)

За оценку расстояния до узла x Î Nodes принимается длина кратчайшего пути до x, а именно:

RouteDistance (n)(x) . (9.25)

В таблицу маршрутизации записывается канал связи, который соединяет n с первым узлом на кратчайшем пути, т.е.

RouteTable (n)(x) l: l Î Outlinks (n) dest(l) = route(n, x) ₁. (9.26)

Выходной канал связи ТКС, по которому следует посылать пакеты данных, определяется с использованием таблицы маршрутизации.

В. Таблица NeighbourDistance

Эта таблица обновляется по такому же алгоритму, как и алгоритм, используемый в алгоритме дистанционно-векторной маршрутизации с асинхронным обновлением оценок расстояний.

С. Таблица LinkState

Каждый узел ТКС через определённые промежутки времени рассылает всем узлам сети пакеты состояния линий (link-state packet).

Пакет состояния линий LinkStatePacket (n) узла n содержит адрес отправителя пакета (т.е. n), его вектор оценок расстояний до узлов-соседей NeighbourDistance (n) и поле «возраст пакета».

Поле «возраст пакета» необходимо для того, маршрутизатор мог определить, какой пакет состояния каналов связи содержит более свежую (обновлённую) информацию.

Пакеты состояния каналов связи распространяются методом заливки, согласно которому узел, приняв пакет, рассылает его дубликаты (реплики) по всем выходящим каналам связи (за исключением того входного канала, по которому он пришёл).

Маршрутизатор n Î Nodes, получив пакет LinkStatePacket (m), m Î Nodes, определяет на основании поля «возраст пакета», является ли пришедший пакет более “молодым” (обновлённым). Если это так, то из него извлекается вектор оценок расстояний от узла m до узлов-соседей NeighbourDistance (m) и этот вектор записывается в таблицу

LinkState (n, m) NeighbourDistance (m). (9.27)