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

На практике чаще всего (особенно в АТМ-сетях) приходится решать задачу оптимального распределения потоков данных в ТКС, когда передача пакетов данных ведется не по одному, а по нескольким маршрутам одновременно. При этом информацию о текущем состоянии ТКС целесообразно хранить в локальных БД и БЗ. Рассмотрим модели таких БД и БЗ на примере распределенных таблиц и карт маршрутизации.

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

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

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

Пусть узлы графа G(A,R,W), определяющего структуру и параметры ТКС, упорядочены, т.е. A={a_i}^N_i=1. Для каждого узла графа упорядочим множество его соседних узлов. С этой целью введем индексное множество:

I={i_j|(a_i,a_j)} ÎR}, (4.3.1)

где i_j порядковый номер узла ,a_j как соседа узла a_i

Распределяющей таблицей маршрутизации (РТМ) узла a_i назовем отображение

. (4.3.2)

Здесь r – число соседних узлов узла a_i, a_j – узел-получатель, x – интенсивность суммарного потока к узлу-получателю a_j.

При использовании РТМ узла a_i поток данных к узлу-получателю a_j будет разбиваться на множество потоков к соседям узла a_i, причем интенсивность этих потоков, согласно (4.3.2), будет равна x·δ_k(x).

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

Если в РТМ распределение потоков не зависит от их интенсивностей, т.е. для любых справедливы соотношения

при всех k,

то такие таблицы будем называть статическими РТМ (СРТМ), а РКМ, определяемую множеством таких таблиц, – статической РКМ (СРКМ).

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

Заметим, что РКМ для каждой пары узлов “источник-получатель” распределяет поток по некоторому набору маршрутов. При этом если маршрут, по которому протекает поток, конечен, то в силу (4.3.2) он будет заканчиваться в узле-получателе.

Таким образом, маршрутом распределения потока x₁ >0, определяемым РКМ для узла-источника и узла-получателя , является любая последовательность узлов , удовлетворяющая следующим соотношениям:

(4.3.3)

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