Формально это означает, что если справедливы утверждения вида

(7.35)

и в графе G(A, R\L_sf, W) не существует маршрута из s в f,

то минимальный разрез графа G равен | L_sf |.

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

Определение 7.2. Максимальным потоком из узла s в узел f ТКС называется максимальная мощность потока, которая может передаваться из s в f по графу G с учётом заданных пропускных способностей (весов) рёбер (каналов связи).

Обозначим значение такого максимального потока через V_sf.

Приведём для удобства дальнейших рассуждений известную теорему Форда-Филкерсона о связи минимального разреза и максимального потока [19].

Теорема 7 .1. Для любой ТКС с одним узлом-источником (т.е. узлом s, не имеющим входящих рёбер) и узлом-приёмником (т.е. узлом f, не имеющим исходящих рёбер) величина максимального потока от узла-источника к узлу-получателю равна величине минимального разреза.

Основываясь на этой теореме, можно сформулировать критерий К-потоковой маршрутизации в виде следующей теоремы.

Теорема 7.2. Пусть задан граф ТКС G = (A, R, W) и на нём определены два узла: узел-источник s и узел-получатель d. Тогда следующие два утверждения равносильны:

1) Пара узлов (s, f) является l -связной и не является (l+1) -связной.

2) Минимальный разрез графа G для пары (s, f) равен l.

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

Поскольку пропускные способности всех рёбер равны 1, то максимальный поток через каждый маршрут из s в f тоже равен 1. Заметим, что максимальный поток из s в d равен максимальному числу непересекающихся маршрутов из s в f, т.е. значению связности в графе G(A, R, W) для пары узлов (s, f).

Таким образом, утверждение 1) равносильно тому, что V_sf =l.

C другой стороны, это утверждение равносильно 2). Тем самым теорема 7.2 доказана.

7.5.6. Алгоритм 2-потоковой маршрутизации и его оптимизация

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

Рассмотрим этот алгоритм подробнее.

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

Таким образом, алгоритм 2-потоковой маршрутизации можно описать следующим образом [69].

Для каждого узла-получателя a_i нужно выполнить следующие операции:

1) Определить множество всех узлов S₁(a_i), которые имеют с ним прямую связь;

2) Определить множество маршрутов R(a_i) из всех узлов ТКС к узлу a_i;

3) Проверить, существуют ли среди узлов из S₁(a_i) двунаправленные каналы связи и выбрать один из таких каналов как альтернативную связь для адресата a_i;

4) Сохранить a_i и взаимосвязанные узлы, объединённые каналом альтернативной связи, в списке O2-узлов и удалить их из S₁(a_i);

5) Проверить, связаны ли оставшиеся узлы из S₁(a_i) с одним из узлов, уже содержащимся в . Если результат положительный, то добавить соответствующий канал связи к R(a_i) и переместить узел от S₁(a_i) к ;

6) Повторять шаг 5, пока все узлы не будут удалены из S₁(a_i);

7) Проверить каждый из оставшихся узлов в графе G, которые еще не являются частью , имеет ли он связи с двумя узлами в . Если результат положительный, то добавить соответствующие каналы связи к R(a_i), а этот узел к ;

8) Повторять шаг 6, пока все узлы сети (кроме узла-получателя) не будут содержаться в .

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

Для обеспечения работоспособности описанного алгоритма необходимо выполнение следующего «триангуляционного» условия:

каждый узел a_i должен «формировать треугольник» связей с каждым из своих соседних узлов.

Это означает, что если для узла a_i есть соседний узел a_k (), то существует такой соседний узел a_j, что справедливы соотношения

и .

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

При определении оптимального альтернативного маршрута необходимо внести в предложенный алгоритм следующие изменения:

1) На втором шаге алгоритма в качестве множества R(a_i) выбрать дерево кратчайших маршрутов к узлу a_i от всех остальных узлов ТКС;

2) На третьем шаге алгоритма в качестве двунаправленного канала связи выбрать двунаправленный канал связи как оптимальный «в среднем», т.е. канал, минимальный по сумме стоимостей в каждом направлении;

3) На пятом шаге алгоритма выбирать узлы, которые связаны с каналом связи наименьшей стоимости;

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

7.5.7. Методы централизованной и децентрализованной К-потоковой маршрутизации

Основными недостатками однопотоковой маршрутизации пакетов данных в динамических ТКС с переменной структурой являются следующие её особенности:

– неисправность или отказ хотя бы одного узла или канала связи ТКС, через которые проходит оптимальный или допустимый маршрут передачи пакетов данных, требуют трудоёмкого перепланирования (пересчёта) оптимального маршрута (или его части) с учётом неисправных узлов или каналов связи ТКС;

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

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

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

Для преодоления трудностей, связанных с указанными недостатками, целесообразно использовать многопотоковую маршрутизацию. При этом планируется и одновременно используется не один (например, оптимальный) маршрут передачи пакетов данных, а К³ 2 маршрутов.

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

При централизованной многопотоковой маршрутизации осуществляется априорное планирование К³ 2 оптимальных или субоптимальных маршрутов по имеющейся фиксированной или обновлённой информации о состоянии ТКС.

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

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

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

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

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