Основные обозначения и определения

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

Множество узлов ТКС будем обозначать Nodes.

Множество пользовательских пакетов данных будем обозначать UserPackets.

Множество узлов-получателей пакета p Î UserPackets обозначим через addressee(p) Ì Nodes.

Если для некоторого подмножества пакетов SingleAddressee Ì UserPackets множество адресатов может состоять только из одного элемента adr, будем обозначать его addressee(p) Î Nodes (полагая, что такое обозначение не вызовет каких-либо недоразумений).

Множество каналов связи ТКС будем обозначать Links.

Все каналы связи ТКС рассматриваются как однонаправленные. Поэтому двунаправленный канал связи ТКС представляется парой каналов связи разной направленности.

Узел-источник и узел-приёмник канала связи l Î Links будем обозначать соответственно source(l) Î Nodes и dest(l) Î Nodes.

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

1) Графовая модель ТКС не содержит петель, т.е.

" l Î Links source(l) ¹ dest(l). (9.7)

2) Пара узлов ТКС соединяется в одном направлении ровно одним каналом связи, т.е.

" l₁, l₂ Î Links l₁ ¹ l₂ Þ Ø (source(l₁) = source(l₂) Ù dest(l₁) = dest(l₂)). (9.8)

Множество каналов связи, выходящих из узла ТКС n Î Nodes, обозначим следующим образом

Outlinks (n) = { l Î Links | source(l) = n }. (9.9)

Под соседями узла n Î Nodes понимается множество узлов ТКС, удовлетворяющее следующему соотношению

Neighbours (n) = { x Î Nodes | $ l Î OutLinks (n) dest(l) = x }. (9.10)

Под “расстоянием” от узла s Î Nodes до узла d Î Nodes будем понимать время, затрачиваемое пакетом p Î UserPackets на прохождение пути от s до d.

Как правило, узлы TKC располагают лишь оценкой “расстояния” до других узлов сети. Для получения этой оценки узел TKC использует время, которое затратили пакеты на прохождение по сети и пытается прогнозировать значение этой величины на некоторый промежуток времени вперёд.

Ряд алгоритмов маршрутизации требует, чтобы узел ТКС n Î Nodes хранил таблицу маршрутизации, т.е. таблицу, в которой для каждого узла ТКС x Î Nodes указано, по какому исходящему каналу связи следует посылать пакеты данных, адресованные x:

Таблицу маршрутизации будем обозначать RouteTable (n): Nodes à Outlinks (n) È null.

Если для некоторого узла-адресата неизвестно, по какому каналу связи посылать адресованные ему пакеты данных, то в таблице для него хранится нулевой указатель (null).

Под маршрутизацией пакета данных p узлом n Î Nodes с использованием таблицы машрутизации RouteTable (n) будем понимать следующую процедуру:

Если addressee(p) = n, то это значит, что пакет достиг своего адресата и далее его маршрутизировать не нужно.

В противном случае, когда RouteTable (n)(addressee(p)) ¹ null, нужно переслать пакет p по исходящему каналу связи RouteTable (n)(addressee(p)) Î Outlinks (n).

В случае, когда RouteTable (n)(addressee(p)) = null, нужнозапустить процедуру обработки пакета, для которого неизвестно, по какому каналу связи ТКС его маршрутизировать дальше.