Многопотоковая маршрутизация в динамических ТКС

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

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

Сформулируем задачу K-потоковой маршрутизации при K³2.

Рассмотрим вновь графовую модель ТКС

G=G(A, R, W), (3.6.1)

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

Будем говорить, что два маршрута пересекаются, если они имеют общие вершины, отличные от начальной и конечной.

Пусть выбраны два узла - узел-источник, а - узел-получатель. Необходимо проложить K непересекающихся маршрутов из s в d, таких, что их суммарная стоимость наименьшая из всех возможных вариантов.

Введем необходимые обозначения. Пусть все несамопересекающиеся маршруты из s в d проиндексированы. Обозначим i -й маршрут из s в d как i_sd, а его стоимость – как w(i_sd). Если i -й и j -й маршруты не пересекаются, то будем обозначать этот факт следующим образом: .

Определим все возможные множества из K непересекающихся маршрутов из s в d в виде

(3.6.2)

Зададим над этими множествами функционал Q вида

. (3.6.3)

Тогда задача К-потоковой оптимальной маршрутизации сводится к оптимизации функционала (3.6.3), т.е.

, (3.6.4)

при ограничениях (3.6.2)

Сформулируем критерий существования решения оптимизационной задачи (3.6.4).

Для этого введем два определения. Пусть на графе G(A,R,W) заданы узел-источник s и узел-получатель d. Тогда минимальным разрезом графа G для пары узлов (s,d) называется минимальное число однонаправленных дуг, при исключении которых из графа G, не останется ни одного маршрута из s в d. Тогда минимальный разрез равен | L_sd |.

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

Приведем теорему Форда-Филкерсона о связи минимального разреза и максимального потока [5].

Теорема 3.6.1: Для любой сети с одним источником (узлом TKC, не имеющим входящих рёбер) и стоком (узлом ТКС, не имеющим исходящих рёбер) величина максимального потока от источника к стоку равна величине минимального разреза граф G.

На базе теоремы 3.6.1 можно определить критерий существования решения для задачи K-потоковой маршрутизации следующим образом.

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

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

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

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

Таким образом, утверждение 1) равносильно тому, что V_sd=l, а это равносильно утверждению 2). Тем самым, теорема 3.6.2 доказана.