Известия РАН. Теория и системы управления, 2020, № 5, стр. 106-115

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

Оценка последствий конкретного разрушения производится по двум критериям: число разъединенных пар источник-приемник и/или уменьшение пропускной способности каналов связи между всеми корреспондентами. Величина ущерба для каждой пары вычисляется как разность максимальных значений потока в исходной и поврежденной сети [1]. Расчеты по указанным критериям позволяют получить представительные векторные оценки, с помощью которых можно выделить наиболее опасные разрушающие воздействия.

Вычислительные эксперименты проводились для сетей с различными структурными особенностями. Для всех сетей сформированы соответствующие многопараметрические диаграммы, позволяющие сравнивать критически опасные повреждения с недоминируемыми векторными оценками ущерба.

Предложенный метод можно рассматривать как один из подходов к решению классической задачи исследования операций “оборона против нападения” [2–5]. Полученные диаграммы позволяют “обороняющейся стороне” в условиях неопределенности сравнивать возможные потери при разрушении ребер минимальных и вершинных разрезов.

Вершинные разрезы изучаются при поиске критически важных элементов (узлов) сети в [6–8], с использованием различных векторных критериев – в [9, 10]. При анализе уязвимости кластерных конгломератов обычно проводится агрегированная оценка потерь суммарного предельно-допустимого потока из центрального узла ко всем остальным [11, 12].

В последние годы возрос интерес к более предметному и комплексному анализу уязвимости сложных взаимосвязанных сетевых систем различного назначения, функционирующих как единое территориально-распределенное образование [13–15]. В [14] прослеживается эволюция моделей исследования уязвимости, отмечается необходимость специального анализа влияния человеческого фактора, а также террористических действий и/или спланированных хакерских атак. В [16] рассматривается влияние природных катастроф на региональные сети связи, в [17, 18] предлагаются технические решения по управлению сетевым трафиком в условиях чрезвычайных ситуаций, охватывающих большие территории. В [19] приводится одна из возможных классификаций различных повреждающих воздействий на сетевые информационные системы. В [20–23] основное внимание уделяется изучению уязвимости сетевых распределенных систем топливно-энергетического комплекса. Далее в данной работе предлагается вычислительная схема, использующая методы многокритериального анализа и потокового программирования, которая может быть применена при анализе уязвимости сетевых систем различного назначения [24, 25].

1. Математическая модель. Для анализа последствий повреждений многопользовательской сетевой системы связи и управления используется модель передачи многопродуктового (МП) потока. Граф сети G(d) без петель и сдвоенных ребер задается множествами $\left\langle {V,R} \right\rangle $: узлов (вершин графа) сети $V = \{ {{v}_{1}},{{v}_{2}},...,{{v}_{n}},...,{{v}_{N}}\} $; неориентированных ребер $R = \{ {{r}_{1}},{{r}_{2}},...,{{r}_{k}},...,{{r}_{E}}\} \subset V \times V$.

Пусть ребро r_k соединяет узлы с номерами ${{n}_{k}},{{j}_{k}}$, ${{r}_{k}} = ({{v}_{{{{n}_{k}}}}},{{v}_{{{{j}_{k}}}}}) = ({{n}_{k}},{{j}_{k}})$. Для описания направления передачи потоков по сети каждому ребру r_k, $k = \overline {1,E} $, ставятся в соответствие две ориентированные дуги u_k, ${{u}_{{k + E}}}$, прямого и обратного направления из множества направленных дуг U = = $\{ {{u}_{1}},{{u}_{2}},...,{{u}_{k}},...,{{u}_{{2E}}}\} $ графа сети $G(d)$, ${{r}_{k}} \Leftrightarrow \{ {{u}_{k}},{{u}_{{k + E}}}\} $. Обозначим через $K({{v}_{n}})$ множество номеров ребер ${{r}_{k}} \in R$, инцидентных вершине ${{v}_{n}}$:

$S({{v}_{n}})$ – множество номеров исходящих дуг, по которым поток покидает узел ${{v}_{n}}$; $T({{v}_{n}})$ – множество номеров входящих дуг, по которым поток поступает в узел ${{v}_{n}}$.

Множества $S({{v}_{n}})$, $T({{{v}}_{n}})$ однозначно определяются следующей процедурой. Пусть некоторое ребро ${{r}_{k}} \in R$ соединяет вершины с номерами $n$ и $j$, такими, что $n < j$. Тогда ориентированная дуга ${{u}_{k}} = ({{v}_{n}},{{v}_{j}})$ считается исходящей из вершины ${{v}_{n}}$ и ее номер k заносится в множество $S({{v}_{n}})$, а ориентированная дуга ${{u}_{{k + E}}} = ({{v}_{j}},{{v}_{n}})$ – входящей для ${{v}_{n}}$ и ее номер $k + E$ помещается в список $T({{v}_{n}})$. Соответственно дуга u_k является входящей для ${{v}_{j}}$ и ее номер k попадает в $T({{v}_{j}})$, а дуга ${{u}_{{k + E}}}$ – исходящей и номер $k + E$ заносится в список $S({{v}_{j}})$ исходящих дуг.

В рамках модели предполагается, что между любой парой узлов передаются различные потоки, например, происходят телефонные разговоры или двигаются пассажиропотоки между станциями метро. Пара узлов-корреспондентов ${{p}_{m}}$ определяется упорядоченной парой вершин ${{p}_{m}} = ({{v}_{{{{s}_{m}}}}},{{v}_{{{{t}_{m}}}}})$, где вершина с номером ${{s}_{m}}$ называется источником, а с номером ${{t}_{m}}$ – стоком или приемником потока m-го вида. В настоящей работе в сети из N узлов рассматривалось $M = N(N - 1)$ независимых, невзаимозаменяемых и равноправных потоков различных видов, которые передаются между узлами-корреспондентами из множества $P = \{ {{p}_{1}},{{p}_{2}},...,{{p}_{M}}\} \subset V \times V$. Величины указанных потоков считаются функциональными характеристиками сети. В ходе вычислительных экспериментов изучаются изменения предельно-возможных потоков для каждой пары ${{p}_{m}}$ при разрушении ребер сети.

Пусть ${{x}_{{mk}}}$ – величина потока m-го вида, который передается в МП-сети по ребру ${{r}_{k}}$, ${{x}_{{mk}}} \geqslant 0$, $m = \overline {1,M} $, $k = \overline {1,E} $. Каждому ребру ${{r}_{k}} \in R$ приписывается число ${{d}_{k}}$, определяющее предельно-допустимый поток, который можно пропустить через ${{r}_{k}}$ в обоих направлениях. В исходной сети компоненты вектора пропускных способностей – $d = ({{d}_{1}},{{d}_{2}},...,{{d}_{k}},...,{{d}_{E}})$ – наперед заданные положительные числа ${{d}_{k}} > 0$. Вектором $d$ определяются следующие ограничения на потоки, передаваемые по ребру ${{r}_{k}}$:

Обозначим через ${{z}_{m}}$, ${{z}_{m}} \geqslant 0$, величину потока m-го вида, который поступает в сеть в узле с номером ${{s}_{m}}$ и покидает ее из узла с номером ${{t}_{m}}$.

Во всех узлах ${{v}_{n}} \in V$, $n = \overline {1,N} $, сети для всех видов потоков должны выполняться условия сохранения потоков:

Величина ${{z}_{m}}$ равна входящему потоку m-го вида, который пропускается от источника к стоку пары ${{p}_{m}}$ при распределении потоков ${{x}_{{mi}}}$ по дугам сети.

Ограничения (1.1), (1.2) задают множество достижимых векторов потоков $z = ({{z}_{1}},{{z}_{2}},...,{{z}_{m}}$, ..., z_M):

при передаче в МП-сети для всех пар ${{p}_{m}} \in P$.

В настоящей работе анализируются результаты вычислительных экспериментов и изучаются оценки изменения максимальных величин потоков для всех возможных пар узлов $M = N(N - 1)$ при структурных повреждениях ребер сети.

2. Формирование множества структурных повреждений. Рассмотрим некоторую произвольную пару узлов-корреспондентов ${{p}_{m}} \in P$ и определим максимально возможный поток, который можно передать в сети $G(d)$ из вершины с номером ${{s}_{m}}$ в вершину с номером ${{t}_{m}}$ без учета всех остальных потоков.

Задача 1. При некотором фиксированном m найти максимальный поток из узла с номером ${{s}_{m}}$ в узел с номером ${{t}_{m}}$:

Согласно [1], каждому максимальному значению $z_{m}^{0}$ соответствует некоторый набор ребер – минимальный разрез ${{R}_{m}}$, ${{R}_{m}} \subset R$. Множество номеров ребер, образующих разрез ${{R}_{m}}$, обозначим

где ${{R}_{m}}$ – минимальное подмножество ребер, таких, что при удалении их из сети максимальный поток из ${{v}_{{{{s}_{m}}}}}$ в ${{v}_{{{{t}_{m}}}}}$ становится равным нулю, а вершины с номерами ${{s}_{m}}$ и ${{t}_{m}}$ оказываются в разных связных компонентах графа сети $G(d)$. Последовательно для всех ${{p}_{m}} \in P$, $m = \overline {1,M} $, решаются цепочки задач 1 и формируется вектор максимальных потоков

Вектору ${{z}^{0}}$ ставится в соответствие множество

номеров ребер, найденных при решении последовательности задач 1 для всех ${{p}_{m}} \in P$.

Для дальнейшего формирования множества повреждений рассматривается следующая модифицированная сеть. В графе сети G(d) пропускная способность всех ребер полагается равной единице:

полученный граф сети обозначается G(1), а соответствующее множество достижимых потоков – Z(x, 1):

Для G(1) определяется максимальный поток для всех пар ${{p}_{m}} \in P$ как решение следующей задачи максимизации.

Задача 2. Для некоторой фиксированной пары ${{p}_{m}} \in P$ найти максимальный поток

Величина $z_{m}^{1}$ равна числу ребер в минимальном разрезе $R_{m}^{1}$ для максимального целочисленного потока из вершины с номером ${{s}_{m}}$ в вершину с номером t_m, $z_{m}^{1} = {\text{|}}R_{m}^{1}{\text{|}}$. Обозначим через

список номеров ребер, при удалении которых максимальный поток из вершины с номером ${{s}_{m}}$ в вершину с номером t_m становится равным нулю.

По аналогии с множеством $H( \cdot )$ строится множество

номеров ребер, входящих в минимальные разрезы, найденные при решении задачи 2 для всех ${{p}_{m}} \in P$, $m = \overline {1,M} $, в сети $G(1)$.

Рассмотрим подмножество

номеров ребер, инцидентных вершине ${{v}_{n}}$, и сформируем множество состоящее из списков номеров ребер, инцидентных каждой вершине сети.

Для проведения вычислительного эксперимента и анализа возможных повреждений формируется множество уникальных повреждений сети

согласно следующей процедуре. В множествах $H( \cdot )$, $Q( \cdot )$, $Y( \cdot )$ могут содержаться одинаковые элементы. Тождественным спискам номеров ребер $h( \cdot ),\;q( \cdot ),\;y( \cdot )$ ставится в соответствие единственный элемент w_l – список номеров ребер для совпадающих $h( \cdot ),q( \cdot )$ или $y( \cdot )$:

3. Оценки повреждений. При проведении вычислительных экспериментов при некотором повреждении w_l пропускная способность ребер сети $G(d(l))$ задается следующим образом:

В поврежденной сети $G(d\left\langle l \right\rangle )$ для всех ${{p}_{m}} \in P$, последовательно для каждого $m = \overline {1,M} $ определяется возможный максимальный поток.

Задача 3. При некоторых заданных $l$ и $m$ найти:

Задача 3 решается последовательно для всех ${{p}_{m}}$, ${{p}_{m}} \in P$, и всех ${{w}_{l}} \in W$. На основе найденных $z_{m}^{0}(l)$, $m = \overline {1,M} $, $l = \overline {1,L} $, вычисляются индикаторные показатели:

Для каждого ${{w}_{l}} \in W$ рассчитывается

– доля от общего числа пар узлов P, для которых максимальный поток становится равен нулю при данном повреждении w_l.

Для всех $m = \overline {1,M} $, $l = \overline {1,L} $, таких, что $z_{m}^{0}(l) > 0$, и наперед заданного значения γ вычисляется индикаторная функция

Значения параметра γ задаются априори в диапазоне $0 < \gamma < 1$. Индикатор $\eta (m,l,\gamma ) = 1$, если максимальный поток $z_{m}^{0}(l)$ для пары ${{p}_{m}}$ при повреждении w_l  оказывается не больше критического значения γ.

При заданном γ для некоторого повреждения ${{w}_{l}} \in W$ и $z_{m}^{0}(l) > 0$ вычисляется

равная доле от общего числа пар узлов $P$, для которых максимальный поток становится меньше или равен критическому значению при повреждении ${{w}_{l}} \in W$. На основе значений $(\mu (l),\psi (l,\gamma ))$ для всех повреждений ${{w}_{l}} \in W$ строятся диаграммы, которые позволяют оценить влияние каждого разрушающего воздействия на потоки между всеми источниками и приемниками. Недоминируемые значения на внешней границе диаграмм дают возможность выделить наиболее “опасные” повреждения, которые разрывают связь между наибольшим числом пар узлов и/или приводят к критически опасному уменьшению потоков ниже допустимых показателей.

4. Вычислительный эксперимент. Вычислительный эксперимент проводился на моделях сетевых систем, представленных на рис. 1, 2 (на рис. 1 – базовая, на рис. 2 слева – рокадная, справа – фронтальная). В каждой из сетей 69 узлов. Пропускные способности ребер выбирались случайным образом из отрезка [900, 999] и совпадают для всех сетей. Пропускная способность каждого из двух дополнительных ребер на рис. 2 равна 900.

Для формирования множества критически опасных повреждений $W$ было найдено порядка 10⁴ минимальных разрезов, из которых чуть более 10² разрезов вошло в $W$ (около 1%). Для целей анализа и отображения структурных повреждений на диаграммах каждому ${{w}_{l}} \in W$ ставится в соответствие “ маска” – тройка индикаторов $str({{w}_{l}}) = (a,b,c)$, значения которых определяются следующим образом:

a = 1, если повреждение ${{w}_{l}}$ совпадает с одним или более списком $h(j)$ в $H( \cdot )$, a = 0 – в противном случае;

b = 1, если список ${{w}_{l}}$ встречается в множестве $Q( \cdot )$ хотя бы один раз, b = 0 – в противном случае;

c = 1, если ${{w}_{l}}$ идентичен одному или более элементам в $Y( \cdot )$, c = 0 – в противном случае.

Для базовой сети (рис. 1) в множество $W$ было включено всего 125 различных повреждений. В табл. 1 для базовой сети представлены: семь возможных записей строк-индикаторов, соответствующее число повреждений и обозначение последних на диаграммах.

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

На рис. 3 представлены диаграммы $(\mu ,\psi )$ для базовой сети при $\gamma = 0.6$ и 0.5. “Жирные точки” у восточного края диаграмм определяют недоминируемые повреждения, разделяющие максимальное число пар-корреспондентов (значение $\mu $ = 1/48 по оси абсцисс). Маска (0, 1, 0) соответствует разрезам в сети с графом $G(1)$ при ${{d}_{k}} = 1$, $k = \overline {1,E} $. Согласно табл. 2, существует четыре различных недоминируемых разрушения ${{w}_{l}}$, приводящих к одинаковому ущербу.

На диаграммах для базовой сети (рис. 3) недоминируемые повреждения с максимальными значениями $\psi $ отмечены “треугольниками”. Указанные разрушения возникают при удалении вершины ${{v}_{2}}$, а точнее – инцидентных ей ребер. Таким образом удаление вершины приводит к заметному ухудшению качества связи, уменьшению пропускной способности, хотя не сильно влияет на связность графа сети. На диаграммах “треугольники” расположены ближе к оси ординат и имеют бóльшие значения $\psi $. В табл. 3 приводится максимальное число пар-корреспондентов с различными нарушениями связи для двух недоминируемых разрушений при $\gamma $ = 0.6.

Недоминируемые разрушения базовой сети с указанными масками приводят к повреждениям, ущерб от которых различается более чем в 4 раза. Недоминируемый разрез в сети с единичной пропускной способностью ребер разъединяет половину пар, но только у 7% оставшихся величина потока снижается ниже критического значения $\gamma $ = 0.6. Наихудший вершинный разрез – удаление вершины ${{v}_{2}}$ – разъединяет менее 9% пар, качество связи становится ниже допустимого у 25% пар.

Недоминируемые повреждения для базовой сети при γ = 0.6 лежат в северо-восточной части диаграммы на рис. 3 слева и обозначены кольцами и жирной точкой. Маска (1, 0, 0) соответствует минимальным разрезам из множества $H( \cdot )$. На рис. 3 справа для базовой сети и γ = 0.5 повреждения с недоминируемыми значениями ущерба и масками (0, 1, 0), (0, 0, 1) обозначены жирной точкой и остались в северо-восточной части диаграммы, а все кольца переместились в ее внутреннюю часть. Дело в том, что значение γ = 0.5 задает более жесткие ограничения на величины сохранившихся потоков, но не влияет на число разрывов для линий связи. В результате значения $\psi $ уменьшаются, $\mu $ – остается неизменным, а рассматриваемое повреждение перестает быть недоминируемым. На рис. 4 на графе базовой сети отмечены все ребра, входящие хотя бы в одно повреждение из табл. 3.

Базовая сеть и сети с рис. 2 имеют совпадающие множества узлов и пар-корреспондентов. Диаграммы оценки повреждений для сетей с добавленными ребрами приведены на рис. 5, 6. Добавление двух дополнительных ребер увеличивает число возможных путей соединения и максимальные потоки для большого числа корреспондентов. В табл. 4 помещены число разъединенных пар и число пар, для которых максимально возможные потоки оказываются ниже критического значения $\gamma $. Все величины приводятся для двух недоминируемых повреждений, при которых достигается либо максимум числа разъединенных пар (самая восточная точка на диаграммах), либо максимум числа пар, для которых максимальной поток ниже $\gamma $ (самая северная точка на диаграммах).

Анализ табл. 4 показывает, что базовая сеть более уязвима, поскольку при особо опасных разрушениях большее число корреспондентов (6%) оказываются разъединенными по сравнению с фронтальной и рокадной сетями. Наилучший показатель у рокадной сети – наименьший по ущербу. Полученный результат закономерен, поскольку шесть центральных ребер рокадной сети, инцидентных узлу ${{v}_{0}}$, затрудняют разделение графа сети на две связанные компоненты. В рокадной сети после повреждений также поддерживается более высокое качество связи – потери потоков меньше. Последнее связано с более мощным транзитным узлом ${{v}_{0}}$, который усилен двумя дополнительными ребрами. На диаграммах с рис. 5, 6 видно (и анализ табл. 4 это подтверждает), что разрушение минимального разреза из множеств $H( \cdot )$ или $Q( \cdot )$ влечет за собой более серьезные нарушения функционирования сети. Наличие всего двух дополнительных ребер в рокадной сети (по сравнению с базовой) позволяет снизить максимальное число разъединенных пар на 12%, однако не влияет на ухудшение качества связи. Действительно, при разрушении соответствующих вершинных разрезов падение потоков практически одинаково как в базовой, так и в рокадной сетях (см. табл. 4).

Заключение. При проведении вычислительных экспериментов используются алгоритмы потокового программирования. На первом этапе для каждой пары узлов решается задача поиска максимального потока и минимального разреза. Верхняя оценка числа операций для решения этой задачи составляет $O({{N}^{5}})$: всего пар узлов $O({{N}^{2}})$, а для определения максимального потока достаточно $O({{N}^{3}})$ [26]. На базе полученных минимальных разрезов формируется множество повреждений W, верхняя оценка числа элементов в котором $O({{N}^{2}})$. Для каждого повреждения ${{w}_{l}}$ вновь определяются максимальные потоки для всех пар узлов. Результирующая верхняя оценка вычислительных затрат полиномиально зависит от числа узлов в сети и составляет не более $O({{N}^{7}})$.

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