Критерии коммуникабельности и методы статической маршрутизации информационных потоков

5.1. Простые таблицы и карты маршрутизации и их представление в распределённых базах данных и знаний

Пусть ТКС задана орграфом G(A, R, W). Назовём простой таблицей маршрутизации τ _i узлаотображение множества узлов A ТКС на множество соседей узла a_i, т.е.

(5.1)

С каждым узлом ТКС свяжем локальную БД и локальную БЗ маршрутизации. БД определяется как результат отображения τ _i (т.е. набором пар узлов из A_i × τ _i (A_i)), а БЗ - как само отображение τ _i. Это позволяет учитывать в БЗ дополнительные характеристики ТКС, такие как топология сети, стоимости каналов связи и т.д.

Таблицы маршрутизации, реализованные в локальных БД узлов ТКС, могут строиться с помощью БЗ в соответствии с некоторым критерием оптимальности (например, минимизация суммарной стоимости маршрута) на основе экспертных или иных решающих правил (тогда множество параметров, учитываемых при выборе маршрута, может быть расширено) или задаваться напрямую администратором сети. Примером таких таблиц могут служить простые таблицы стандартного вида [4, 11].

Пусть для каждого узла ТКС задана простая таблица маршрутизации. Назовём множество таких таблиц простой картой маршрутизации(ПКМ). Формально карту маршрутизации можно представить в виде

. (5.2)

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

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

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

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

В обоих случаях управление прокладкой маршрута ведётся следующим образом: фиксируется узел-получатель данных f и для него от узла-источника s последовательными отображениями строится последовательность узлов ТКС вида

s=a₀, a₁, a₂, …, a_k=f, (5.3)

таких, что для любого i =1, 2, …, k справедливо соотношение

τ _i-1(f)=a_i.

5.2. Критерий коммуникабельности, основанный на корректности простой карты маршрутизации

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

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

Теорема 5.1. Карта маршрутизации ТКС корректна, т.е. для любого узла-источника данных s и любого узла-получателя данных f из множества A узлов ТКС существует последовательность узлов вида (5.3) такая, что

для всех i=1, 2, …, k, (5.4)

тогда и только тогда, когда для любого узла и для любого разбиения множества A на непустые подмножества A₁ и A₂, такие, что, найдутся узлы и, для которых справедливо соотношение

τ ₁(f)=a₂. (5.5)

Для доказательства теоремы 5.1 сначала покажем, что из второго утверждения следует первое. Зафиксируем узел-получатель. Рассмотрим любое разбиение множества узлов на подмножества A₁ и A₂, где. Возьмём любой узел из подмножества A₁ и обозначим его через s. Тогда существует последовательность узлов вида (5.3)такая, что для любого i=1, 2,..., k верно, что τ _i-1(f)=a_i. Так как узел-источник, а узел-получатель, то существует такой индекс j, что

, и τ _j-1(f)=a_j. (5.6)

Таким образом, требуемая импликация доказана.

Покажем теперь справедливость обратной импликации, т.е. докажем, что из первого утверждения теоремы следует второе. Зафиксируем узлы. Разобьём множество узлов A на подмножества A₁⁽⁰⁾ и A₂⁽⁰⁾, причём A₂⁽⁰⁾ ={ f }. Тогда существует такой узел, что τ ₁(f)=f. Если, то разобьём множество A на подмножества A₁⁽¹⁾ и A₂⁽¹⁾, где A₂⁽¹⁾ ={ f, a₁ }. Тогда существует такой узел, что. Если, то продолжим построение последовательности узлов до тех пор, пока не получим a_k=s. Заметим, что для всех подмножеств A₂⁽ⁱ⁾ верно, что из любого узла этих подмножеств существует маршрут до узла-получателя f, определяемый таблицами маршрутизации ТКС. Поскольку, то между узлом-источником s и узлом-получателем f существует маршрут, определяемый таблицами маршрутизации. Следовательно, обратная импликация также справедлива.

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

Важно отметить, что таблицы маршрутизации определяют только один маршрут между узлом-источником s и узлом-получателем f. В противном случае существовали бы такие таблицы t_i Î T и узел a Î A, для которых справедливы соотношения

, (5.7)

что противоречит определению простых таблиц маршрутизации для узлов ТКС.

5.3. Критерий существования и метод построения оптимальных маршрутов с помощью простых карт маршрутизации

Для каждого узла ТКС зададим функционал оценки стоимостей маршрутов до остальных узлов ТКСв виде

, (5.8)

где w_j – стоимости звеньев (каналов связи), образующих маршрут из a_i в a_k.

Заметим, что при неполноте информации о текущем состоянии ТКС, доступной узлу a_i (например, в динамически изменяющихся ТКС), значение функционала может не совпадать с точным значением стоимости маршрута. В таких случаях обычно используются адаптивные методы, оценивающие значение функционала стоимости маршрута [29, 69].

Пусть таблицы маршрутизации строятся следующим образом

(5.9)

где функции ρ _i вычисляются по следующей формуле

. (5.10)

Такие таблицы будем называть оптимальными таблицами маршрутизации. Они представляют для каждого узла TKC оптимальную локальную БД маршрутизации.

Множество таких таблиц определяет оптимальную карту маршрутизации и реализующую её оптимальную глобальную БД маршрутизации ТКС.

Теорема 5.2. Маршруты, определяемые по формулам (5.9) и (5.10), являются оптимальными, в том смысле, что функционал (5.8), оценивающий их стоимость, принимает на этих маршрутах минимальное значение, т.е.

ρ _i(f)=K_opt(a_i, f)) = min K(a_i, f). (5.11)

Для доказательства этой теоремы прежде всего заметим [69], что второе утверждение напрямую следует из описанного метода построения оптимальных таблиц маршрутизации по формулам (5.9) и (5.10).

Докажем теперь первое утверждение теоремы по индукции, а именно: если n-звенные маршруты, построенные по формулам (5.9) и (5.10), оптимальны, то (n+1)-звенные маршруты, построенные по этим же формулам, также будут оптимальны.

База: n=0.

Так как стоимость маршрута неотрицательна, а стоимость всех 0-звенных маршрутов равна 0, то для n=0 доказываемое утверждение верно.

Индукционный переход: n → n+1.

Рассмотрим (n+1)-звенный маршрут P₀⁽ⁿ⁺¹⁾(s, f) от заданного узла-источника s к фиксированному узлу-получателю f, определяемый оптимальными таблицами маршрутизации, в виде

. (5.12)

Стоимость этого маршрута равна ρ _s(f) = K(s, f). Так как маршруты P₀⁽ⁿ⁾ оптимальны, а функционалы ρ _i соответствуют их стоимостям, то из формул (5.9) и (5.10) следует, что

. (5.13)

Таким образом, стоимость (n+1)-звенного маршрута, определённого по оптимальным таблицам маршрутизации является минимальной из всех возможных. Это значит, что маршрут P₀⁽ⁿ⁺¹⁾(s, f) оптимален для любых узлов –источников и узлов-получателей.

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

5.4. Распределяющие таблицы и карты маршрутизации

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

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

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

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

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

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

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

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

, (5.15)

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

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

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

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

при всех k,

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

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

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

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

5.5. Критерий корректности статических распределяющих карт маршрутизации и его матричное представление

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

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

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

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

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

Теорема 5.3. доказана. По существу она определяет критерий корректности СРКМ в терминах структуры допустимых маршрутов.

Рассмотрим теперь матричную интерпретацию корректности СРКМ. Пусть в графе G(A, R, W) имеется N узлов, т.е.. Расширим СРКМ следующим образом:

. (5.18)

Зафиксируем узел-получатель a_j и построим матрицу следующего вида:

. (5.19)

Из (5.15) и (5.18) следует, что сумма элементов матрицы (5.19) в каждой строке, кроме j-й, равна единице, а в j-й строке все элементы нулевые. Так как в графе G(A, R, W) нет дуг вида (a_i, a_i), то из (5.14) и (5.18) следует, что все диагональные элементы матрицы (5.19) будут нулевыми.

Теорема 5.4. СРКМ корректна тогда и только тогда, когда для любых и справедливо следующее соотношение:

(5.20)

Докажем сначала необходимость. Пусть СРКМ корректна. Зафиксируем узел-получатель. Рассмотрим элементы матриц вида

. (5.21)

Рассуждая по аналогии с анализом коммуникационных возможностей ТКС по её матрице смежностей, можно утверждать, что если, то существует l -звенный маршрут из узла в a_j через, прокладываемый СРКМ. Таким образом, если предположить, что уравнение (5.20) не выполняется, т.е. для некоторого узла верно, что, то существует циклический маршрут из a_i в a_j. Однако в таком случае из теоремы 5.3. следует, что СРКМ не корректна, что противоречит условию. Это означает, что требование (5.20) должно выполняться.

Докажем теперь достаточность. Пусть для рассматриваемой СРКМ выполняется уравнение (5.18). Это означает, что маршруты, определяемые СРКМ и состоящие не более, чем из (N-1) звеньев, будут ациклическими. Так как любой конечный маршрут в графе с N узлами будет не более, чем (N-1)-звенным, а любой цикл маршрута, определяемого СРКМ, не может проходить через узел-получатель, т.е. тоже будет не более, чем (N-1)-звенным, то из (5.20) следует, что все маршруты, определяемые СРКМ будут ациклическими.

Таким образом, из теоремы 5.3. следует, что СРКМ будет корректна.

Теорема 5.4. доказана. По существу она определяет критерий корректности СРКМ в матричных терминах уравнения “корректности” (5.20).

В заключение рассмотрим очень важное свойство матриц вида (5.19) для корректных СРКМ. Зафиксируем узел-получатель и запустим из каждого узла в a_j поток с соответствующей интенсивностью x_i. Из (5.17) и (5.21) следует, что для того, чтобы определить, с какой интенсивностью совокупность этих потоков проходит через узлы ТКС, достаточно рассмотреть соответствующие элементы следующего вектора “интенсивностей” [69]

. (5.22)