Журнал вычислительной математики и математической физики, 2019, T. 59, № 9, стр. 1626-1638

1. ВВЕДЕНИЕ

Изучаются предельные функциональные возможности многопродуктовой сети и их изменения при повреждениях сетевых элементов. В начальный момент для каждой пары различных вершин вычисляется предельно-допустимый независимый информационный поток и определяется минимальный разрез, разделяющий соответствующую пару вершин. После удаления из сети всех ребер найденного минимального разреза вновь определяются максимально-возможные потоки для всех остальных пар вершин и сравниваются с их исходными значениями. Рассматриваются структурные повреждения – минимальные разрезы трех основных типов (см. разд. 3), для которых рассчитываются две группы количественных характеристик последствий каждого структурного повреждения: доля разделенных пар и уменьшение максимально-возможных потоков по неразорванным информационным направлениям (см. разд. 4). Указанные характеристики агрегируются в показатели подверженности информационных направлений влиянию структурных повреждений и с их помощью осуществляется двухкритериальное ранжирование всех пар вершин (см. разд. 5). Полученные оценки ущерба позволяют также ранжировать структурные повреждения (см. разд. 6). В целом предложенный подход дает способ наглядного и быстрого анализа уязвимости многопользовательской сетевой системы по отношению к удалению из графа сети наборов ребер, образующих разрез, для разрезов разного типа. Введенные понятия проиллюстрированы на модельном примере сети связи и управления (см. разд. 7).

2. МНОГОПРОДУКТОВАЯ МОДЕЛЬ

Рассмотрим математическую запись модели передачи многопродуктового (МП-) потока в сети с многими источниками и стоками [1]. МП-сеть $\left\langle {V,R,P} \right\rangle $ задается множествами:

– вершин (узлов) сети $V = \{ {{v}_{1}},{{v}_{2}},...,{{v}_{n}}\} $;

– ребер $R = \{ {{r}_{1}},{{r}_{2}},...,{{r}_{e}}\} \subset V \times V$ физического графа $G(d) = \left\langle {V,R} \right\rangle $ сети с пропускной способностью, равной вектору $d$, компоненты которого ${{d}_{k}}$ ограничивают суммарные потоки по ребру ${{r}_{k}}$, $k = 1,2, \ldots ,e$; считается, что граф $G(d)$ без петель и сдвоенных ребер;

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

Для упрощения обозначений предположим, что все физические ребра – неориентированные. При этом для определения потоков по ребрам графа $G(d)$ назовем прямым направление от вершины с меньшим номером к вершине с большим и каждое ребро ${{r}_{k}}$ физического графа сети будем представлять двумя ориентированными дугами с номерами $k$ и $k + e$ для прямого и обратного направлений соответственно. (В случае ориентированного ребра физического графа формально можно полагать нулевым поток по дуге, направленной противоположно ориентации ребра.) Для любой вершины ${{v}_{j}} \in V$ обозначим через $S({{v}_{j}})$ множество индексов выходящих из нее дуг,

а через $T({{v}_{j}})$ множество индексов входящих дуг:

Для каждой $i$-й тяготеющей пары ${{p}_{i}}$ введем обозначение ${{p}_{i}} = ({{v}_{{{{s}_{i}}}}},{{v}_{{{{t}_{i}}}}})$, где вершина ${{v}_{{{{s}_{i}}}}}$ называется источником, а ${{v}_{{{{t}_{i}}}}}$ – стоком $i$-го вида продукта и/или информационного потока (для сетей связи и управления). Вершины источник и сток определяются согласно ориентации дуги логического графа сети.

Структура МП-сети может быть представлена также с помощью матрицы $A = \{ {{a}_{{kj}}}\} $ инциденций “дуги-вершины” физического графа сети $G(d)$ размера ($2e \times n$),

и матрицы связей логического графа сети: $B = \{ {{b}_{{ij}}}\} $ размера $m \times n$.

Введем матричную переменную $x = \{ {{x}_{{ik}}}\} $ размерности $m \times 2e$. Каждый элемент ${{x}_{{ik}}}$ обозначает количество продукта $i$-го вида ($i$-го информационного потока) по ребру ${{r}_{k}} \in R$ в прямом направлении для $k \leqslant e$ или по ребру ${{r}_{{k - e}}} \in R$ в обратном направлении, если $k > e$. Все ${{x}_{{ik}}} \geqslant 0$. Кроме неотрицательности, для возможных значений переменной $x$ должны выполняться условия сохранения потока каждого вида, т.е. $\forall v \in V$ имеем

Значение ${{z}_{i}} \geqslant 0$ равно величине входного потока, который пропускается по сети от источника к стоку i-й тяготеющей пары при распределении потоков ${{x}_{{ik}}}$ по физическим ребрам сети. Так что на ребрах графа $G(d)$ МП-сети потоки не смешиваются (но, тем не менее, подчиняются единым ограничениям). В матричной форме для $z = z(x)$ получаем систему уравнений Здесь и далее нижний индекс у матрицы указывает на соответствующую вектор-строку данной матрицы. Таким образом, зависимость $z(x)$ линейна.

Каждому ребру ${{r}_{k}} \in R$ физического графа $G(d)$ МП-сети приписано число ${{d}_{k}}$, названное пропускной способностью ребра ${{r}_{k}}$ и измеряемое в условных единицах потоков, для передачи которых предназначена данная сеть. Тем самым, различные виды потоков должны измеряться в сопоставимых единицах. Как правило, речь идет об однотипных потоках, которые различаются лишь адресатами, но не являются взаимозаменяемыми, например, пассажиропотоки или потоки частной корреспонденции (а не денежные потоки или “письма счастья”). Компоненты вектора $d = ({{d}_{1}},{{d}_{2}},...,{{d}_{e}})$ известны, фиксированы и неотрицательны. В начальный момент они предполагаются строго положительными, но далее с помощью придания им нулевых значений удобно моделировать разрушение, т.е. исключение из графа сети, соответствующих ребер. Вектор $d$ задает следующие ограничения-неравенства на распределение потоков в сети:

Ограничения (2.2) линейны и совместно с ограничениями (2.1) задают многогранник возможных распределений потоков

а также множество достижимых векторов МП-потока

При использовании МП-модели для анализа сетевых систем определяется вектор величин потоков, которые удается одновременно передать между заданными парами вершин логического графа. Обычно, всем дугам логического графа приписаны числа ${{f}_{i}}$ и исследуется возможность пропускать набор потоков величины ${{f}_{i}}$ для тяготеющих пар ${{p}_{i}} \in P$. Данная работа посвящена задаче априорного ранжирования тяготеющих пар сети по подверженности влиянию структурных повреждений ее физического графа. Поэтому будем рассматривать полный граф тяготений. Тогда потенциально имеется $m = n(n - 1)$ информационных направлений, или тяготеющих пар. Также не будем вводить требований ${{f}_{i}}$ на передачу потока, рассуждая в терминах максимально достижимых величин.

3. КРИТИЧЕСКИЕ СТРУКТУРНЫЕ ПОВРЕЖДЕНИЯ

Структурное повреждение сети определяется подмножеством ее физических ребер, пропускная способность которых полагается равной нулю. Для спецификации конкретного структурного повреждения введем идентификатор $w$ и каждое повреждение $w$ будем задавать списком индексов $I(w)$ исключаемых из $R$ (разрушенных) ребер. Обозначив через $d(w)$ вектор пропускной способности ребер после повреждения $w$, получим $I(w) = \{ k\,|\,{{d}_{k}}(w) = 0,\;{{r}_{k}} \in R\} $. Введем также параметр $\mu (w) = \left| {I(w)} \right|$ мощности повреждения $w$ как общего числа поврежденных ребер. Считаем, что структурное повреждение $w$ является критически опасным, если при удалении набора ребер $\{ {{r}_{k}}{\kern 1pt} |{\kern 1pt} k \in I(w)\} $ максимально возможный поток хотя бы по одному информационному направлению оказывается равным нулю, т.е. в множестве (2.4) с $d = d(w)$ не найдется вектора со всеми положительными компонентами. Тем самым, критически опасные структурные повреждения (далее – КрОС-повреждения) соответствуют разрезам [2], разделяющим хотя бы одну пару вершин в сети. Ниже рассмотрим в определенном смысле минимальные такие повреждения.

Представим гипотетическую ситуацию, когда все ресурсы сети задействованы для передачи единственного потока между выделенной парой вершин ${{p}_{i}} \in P$, а для всех остальных потоки полагаются равными нулю. Указанный способ управления сетью будем называть монопольным режимом передачи потока ${{z}_{i}}$. Максимальный поток, который можно передать для фиксированной тяготеющей пары в монопольном режиме, является решением стандартной, в данном случае однопродуктовой [3], задачи о максимальном потоке.

Задача 1. Найти

Из структуры ограничений (2.1), (2.2) видно, что значение максимума в задаче 1 не изменится, если оставить в сети лишь один вид продукта: выбрать $P = \{ {{p}_{i}}\} $ или же добавить условие

Поэтому поток величины $z_{i}^{0}$ будем называть максимальным потоком для $i$-й тяготеющей пары, передаваемым в монопольном режиме, далее – МРМ-потоком, и предполагать, что $z_{i}^{0} > 0$ $\forall {{p}_{i}} \in P$ в исходной МП-сети.

МРМ-потоку $z_{i}^{0}$ в задаче 1 сопоставлен, по крайней мере, один минимальный разрез [3] (далее – МРМ-разрез), поиск которого эффективно осуществляется теми же методами потокового программирования совместно с решением задачи 1. Пусть $w = h(i)$ – соответствующее КрОС-повреждение МП-сети. По теореме Форда–Фалкерсона суммарная пропускная способность ребер из множества $\{ {{r}_{k}} \in R\,|\,k \in I(h(i))\} $ равна МРМ-потоку $z_{i}^{0}$, а одновременное удаление из физического графа сети этого множества ребер разделяет (по разным связным компонентам графа $G$) пару вершин ${{p}_{i}} = ({{{v}}_{{{{s}_{i}}}}},{{{v}}_{{{{t}_{i}}}}}) \in P$ и обнуляет МРМ-поток $z_{i}^{0}$. Обозначим через $H(i) = \{ {{h}_{1}}(i),{{h}_{2}}(i), \ldots \} $ – множество таких МРМ-разрезов, относящихся к МРМ-потоку $z_{i}^{0}$.

Последовательно для каждой пары вершин ${{p}_{i}} \in P$ решим задачу 1, вычислим значения $z_{i}^{0}$ для $i = \overline {1,m} $ и сформируем множество

Разрезы из $H{\kern 1pt} *$ будем называть КрОС-повреждениями первого типа.

Теперь в исходном физическом графе сети формально положим пропускную способность всех ребер равной единице и найдем поочередно для каждой пары ${{p}_{i}} \in P$ максимальный поток $z_{i}^{1}$ из решения задачи типа 1, но для случая $d = {\mathbf{1}}$, где ${\mathbf{1}}$ есть $e$-мерный вектор из единиц.

Задача 2. Найти

В данном случае $z_{i}^{1}$ совпадает с минимально возможным числом ребер у разрезов для тяготеющей пары ${{p}_{i}} \in P$. Обозначим соответствующее КрОС-повреждение через $w = q(i)$, тогда $z_{i}^{1} = \mu (q(i)) = \left| {I(q(i))} \right|$, где $I(q(i))$ – список номеров ребер, образующих данный разрез, $\mu (q(i))$ – мощность повреждения. С учетом неединственности введем $Q(i) = \{ {{q}_{1}}(i),{{q}_{2}}(i), \ldots \} $ – множество разрезов минимальной мощности для информационного направления ${{p}_{i}} \in P$.

После решения цепочки задач 2 построим $Q(i)$, $i = 1,2, \ldots ,m$, и составим из них множество

При удалении из графа $G(d)$ всех ребер $\{ {{r}_{k}} \in R\,|\,k \in I(q(i))\} $ для такого разреза, где $q(i) \in Q{\kern 1pt} *$, соответствующая пара вершин ${{p}_{i}} = ({{v}_{{{{s}_{i}}}}},{{v}_{{{{t}_{i}}}}}) \in P$ оказывается разделена, а максимальный поток $z_{i}^{0}$, как и $z_{i}^{1}$, становится равным нулю. Минимальные разрезы из $Q{\kern 1pt} *$ будем называть КрОС-повреждениями второго типа.

КрОС-повреждение третьего типа возникает при удалении всех ребер, инцидентных какой-либо вершине $v \in V$. При этом разделенными оказываются, как минимум, те пары ${{p}_{i}}$, для которых ${{v}_{{{{s}_{i}}}}}$ или ${{v}_{{{{t}_{i}}}}}$ совпадает с $v$, т.е. не менее $2(n - 1)$ информационных направлений, независимо от мощности разреза. Введем по определению: $U{\kern 1pt} * = \{ u(1),u(2), \ldots ,u(n)\} $ – множество повреждений третьего типа, где $I(u(j)) = S({{v}_{j}}) \cup T({{v}_{j}})$ – список номеров $k$ ребер ${{r}_{k}} \in R$ инцидентных вершине ${{v}_{j}}$. КрОС-повреждения из $U{\kern 1pt} *$ будем также называть вершинными. Как правило (если степень вершины больше 1), вершинные повреждения не являются МРМ-разрезами.

Рассмотрим объединение множеств $H{\kern 1pt} {\text{*}} \cup Q{\kern 1pt} {\text{*}} \cup U{\kern 1pt} {\text{*}}$ КрОС-повреждений первого, второго и третьего типов. В объединенном множестве могут содержаться разрезы с одинаковыми наборами ребер. Исключим из объединения $H{\kern 1pt} {\text{*}} \cup Q{\kern 1pt} {\text{*}} \cup U{\kern 1pt} {\text{*}}$ повторные разрезы, тогда оставшиеся сформируют множество КрОС-повреждений $W = \{ {{w}_{1}},{{w}_{2}}, \ldots ,{{w}_{c}}\} $, для которого каждый элемент $I(w)$ состоит из уникального набора индексов, не совпадающего ни с одним другим $I(w')$ при $w \ne w'$. Здесь и далее $c$ – результирующее число элементов в $W$. Перейдем к анализу последствий для сети от удаления рассматриваемых наборов ребер, заданных КрОС-повреждениями из $W$.

4. АНАЛИЗ И ОЦЕНКИ ПОВРЕЖДЕНИЙ

Возьмем произвольное КрОС-повреждение $w \in W$. На первом шаге вычислим общее число информационных направлений – пар вершин ${{p}_{i}} = ({{v}_{{{{s}_{i}}}}},{{v}_{{{{t}_{i}}}}}) \in P$, для которых МРМ-поток окажется равным 0 после данного повреждения. Для этого введем умозрительную характеристику $g(w)$ длины ребер графа $G(d)$ (не имеющую отношения к физической длине линий связи моделируемой сетевой системы), зависящую от $w$:

где $e$ – число ребер физического графа сети.

Задача 3. Для заданного вектора $g(w)$ найти кратчайшие пути в графе $G(d)$ между всеми парами вершин ${{p}_{i}} = ({{v}_{{{{s}_{i}}}}},{{v}_{{{{t}_{i}}}}}) \in P$, т.е. сформировать множество $L(w) = \{ {{l}_{1}}(w),{{l}_{2}}(w), \ldots ,{{l}_{m}}(w)\} $, где ${{l}_{i}}(w)$ – кратчайший путь соединения для ${{p}_{i}} \in P$ в графе $G(d)$ с длинами ребер $g(w)$ при КрОС-повреждении $w \in W$.

Введем ${{P}^{ - }}(w) = \{ {{p}_{i}} \in P\,|\,{{l}_{i}}(w) \geqslant 2e\} $ – множество пар вершин, для которых длина кратчайшего пути их соединения не меньше $2e$ в графе $G(d)$ с $g(w)$. Соответственно определим функции-индикаторы для каждого информационного направления

По ним для данного КрОС-повреждения $w \in W$ подсчитаем число и долю

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

На втором шаге проанализируем изменения величин МРМ-потоков для тех информационных направлений, по которым сохранилась возможность передачи потока в поврежденной сети. Обозначим через ${{P}^{ + }}(w)$ множество $P{\backslash }{{P}^{ - }}(w) = \{ {{p}_{i}} \in P\,|\,{{l}_{i}}(w) < 2e\} $ – тяготеющих пар, для которых при решении задачи 3 длина кратчайшего пути соединения оказалась меньше $2e$, т.е. существует возможность “обойти” поврежденные ребра. Заметим, что, если тяготеющая пара ${{p}_{i}} = ({{v}_{{{{s}_{i}}}}},{{v}_{{{{t}_{i}}}}}) \in {{P}^{ + }}(w)$, то и для противоположного направления . Таким образом, любое множество ${{P}^{ + }}(w)$ и ${{P}^{ - }}(w)$ состоит из четного числа элементов. Теперь для тяготеющих пар ${{p}_{i}} \in {{P}^{ + }}(w)$ рассчитаем изменения их МРМ-потоков при удалении из графа $G(d)$ всех ребер, относящихся к рассматриваемому КрОС-повреждению $w \in W$. Будем поочередно для каждой пары вершин ${{p}_{i}} = ({{v}_{{{{s}_{i}}}}},{{v}_{{{{t}_{i}}}}}) \in {{P}^{ + }}(w)$ решать следующую задачу типа 1.

Задача 4. Найти

где ${{d}_{k}}(w) = 0$ для всех $k \in I(w)$, а для остальных $k$ сохраняется ${{d}_{k}}(w) = {{d}_{k}}$.

Оптимальное решение задачи 4 определяет значение МРМ-потока для пары вершин ${{p}_{i}} = ({{v}_{{{{s}_{i}}}}},{{v}_{{{{t}_{i}}}}}) \in {{P}^{ + }}(w)$ при удалении из физического графа сети всех ребер, заданных КрОС-повреждением $w$. Укажем, что для ${{p}_{i}} \in {{P}^{ - }}(w)$ максимум в задаче 4 равен нулю по определению, а для остальных пар вершин (из ${{P}^{ + }}(w)$) этот максимум больше 0 в силу решения задачи 3. Поэтому, последовательно решив всю цепочку задач 4 для ${{p}_{i}} \in {{P}^{ + }}(w)$, можем сформировать для сравнения вектор из значений МРМ-потоков: $\bar {z}(w) = (z_{1}^{0}(w),z_{2}^{0}(w), \ldots ,z_{m}^{0}(w))$ при КрОС-повреждении $w \in W$ графа $G(d)$ сети. Отметим, что в общем случае .

Выше, в разд. 3, при решении задачи 1 были получены значения $z_{i}^{0}$ МРМ-потоков в исходной, неповрежденной сети. Вычислим оценки ущерба – изменения значений МРМ-потоков после повреждения $w$ для каждой тяготеющей пары ${{p}_{i}} \in {{P}^{ + }}(w)$ (неразделенной повреждением):

Следуя подходу [4], для набора значений $\{ {{\chi }_{i}}(w){\kern 1pt} |{\kern 1pt} {{p}_{i}} \in {{P}^{ + }}(w)\} $ определим величину $\chi (w)$ медианы ущерба. А именно, найдем такое число $\chi (w)$, что оно делит множество тяготеющих пар из ${{P}^{ + }}(w)$ на две, по возможности, равные части: в половине случаев значения ${{\chi }_{i}}(w) \leqslant \chi (w)$, а в другой половине случаев ${{\chi }_{i}}(w) > \chi (w)$.

Например, если все ${{\chi }_{i}}(w)$ различны, то выстроив их по порядку возрастания, можно выбрать с учетом четности числа элементов в ${{P}^{ + }}(w)$ в качестве медианы максимальное значение в первой половине. Обозначим через ${{P}^{ + }}{\kern 1pt} {\text{*}}(w) = \{ {{p}_{i}} \in {{P}^{ + }}(w)\,|\,{{\chi }_{i}}(w) \leqslant \chi (w)\} $ множество, состоящее из всех тяготеющих пар, для которых ущерб не больше медианы, и ${{P}^{ \pm }}(w) = \{ {{p}_{i}} \in {{P}^{ + }}(w)\,|\,{{\chi }_{i}}(w) > \chi (w)\} $ – множество, состоящее из таких пар вершин, для которых ущерб больше медианы. В ситуации совпадения ряда ${{\chi }_{i}}(w)$ выберем $\chi (w)$ так, чтобы $\left| {{{P}^{ \pm }}(w)} \right| \leqslant \left| {{{P}^{ + }}{\kern 1pt} {\text{*}}(w)} \right|$ при минимальной разнице в числе элементов двух множеств. Поскольку речь идет лишь о тяготеющих парах, не разделяемых разрезом $w$, то будем далее говорить о величине $\chi (w)$ как о медиане неполного ущерба.

Введем и вычислим функцию-индикатор

По построению и из определения следует, что доля тяготеющих пар в множестве ${{P}^{ \pm }}(w)$ по отношению ко всем тяготеющим парам:

Решения цепочек задач 1, 3, 4 для КрОС-повреждений позволяют получить сравнительные данные о последствиях любого повреждения $w \in W$. Пара чисел (значений параметров) $\left\langle {\rho (w),\chi (w)} \right\rangle $ в агрегированном виде описывает изменения функциональных возможностей сетевой системы после КрОС-повреждения $w$. Так, $\rho (w)$ – доля пар вершин с нулевым МРМ-потоком. Соответственно $1 - \rho (w)$ – доля оставшихся пар, медиана ущерба для них составляет $\chi (w)$, т.е. примерно у половины этих тяготеющих пар ${{p}_{i}}$ ущерб ${{\chi }_{i}}(w)$ превышает значение $\chi (w)$ медианы, и не меньше доля таких информационных направлений, для которых ущерб ограничивается величиной $\chi (w)$. Следовательно, КрОС-повреждение $w$ разбивает все множество тяготеющих пар в пропорции $\left\langle {\rho (w),(1 - \rho (w)){\text{/}}2,(1 - \rho (w)){\text{/}}2} \right\rangle $, если удается построить точную медиану, либо

если $\left| {{{P}^{ \pm }}(w)} \right| < \left| {{{P}^{ + }}{\kern 1pt} {\text{*}}(w)} \right|$, например, когда больше половины тяготеющих пар имеет нулевой ущерб от $w$ (так что все они оказались в ${{P}^{ + }}{\kern 1pt} {\text{*}}(w)$).

5. АНАЛИЗ УЯЗВИМОСТИ ДЛЯ ПОЛЬЗОВАТЕЛЕЙ СЕТИ

Наборы значений МРМ-потоков по всем информационным направлениям при каждом КрОС-повреждении характеризуют возможности сетевой системы до и после повреждения. Проанализируем изменения векторов МРМ-потоков на классе КрОС-повреждений $w$ из множества $W$. С этой целью для любой пары вершин ${{p}_{i}}$ определим, в какое подмножество она будет включена после произвольного КрОС-повреждения. Вычислим все значения индикаторных функций ${{\xi }_{i}}(w)$ и ${{\phi }_{i}}(w)$ для $w \in W$.

Подсчитаем

т.е. долю $w \in W$, при которых МРМ-поток по $i$-му информационному направлению окажется равным нулю. Введем ${{W}^{ + }}(i) = \{ w \in W\,|\,{{p}_{i}} \in {{P}^{ + }}(w)\} $ – множество таких повреждений из $W$, что $z_{i}^{0}(w) > 0$, т.е. возможна передача потока по $i$-му информационному направлению. Определим т.е. долю КрOС-повреждений из ${{W}^{ + }}(i)$, при которых ущерб от потери (неполной) МРМ-потока для тяготеющей пары ${{p}_{i}} \in P$ окажется больше значения соответствующей данному повреждению медианы неполного ущерба. На основе значений ${{\rho }_{i}}(W)$ и ${{i}_{i}}(W)$, найденных для всех тяготеющих пар, построим набор точек на плоскости с указанными координатами (см. фиг. 1). Каждой паре ${{p}_{i}} \in P$ сопоставлена одна точка (${{\rho }_{i}}(W)$, ${{\varphi }_{i}}(W)$). При одинаковых координатах точки могут совпадать.

Точки на фиг. 1, которые находятся “в относительной близости” от северо-восточной границы выпуклой оболочки построенных точек, соответствуют парам вершин сети, наиболее уязвимым по отношению к КрОС-повреждениям $w \in W$ различных типов (отмечены звездочкой). При удалении из сети множеств ребер для соответствующих разрезов потоки по отмеченным информационным направлениям чаще (в большем числе случаев) оказываются равными нулю или имеют неполный ущерб, превышающий медианные значения.

Рассмотрение в составе $W$ минимальных (в том или ином смысле) КрОС-повреждений делает полученные оценки более информативными в силу ожидаемости подобных повреждений. При этом вычислительный поиск учитываемых разрезов оказывается довольно простым – предполагает решение однопродуктовых задач высокоэффективными методами потокового программирования. Число подобных задач полиномиально зависит от числа вершин сети, и весь анализ получается ненамного сложнее, чем проделанный в [4] для однопродуктовых сетей.

В данной постановке, когда принимаются во внимание все возможные информационные направления, найденные показатели фактически характеризуют свойства физического графа $G(d)$ МП-сети: насколько его структура обусловливает уязвимость связи между конкретными парами вершин. Это позволяет на практике ставить задачи построения новых физических ребер с целью укрепления связей. Понятно, что чем ближе граф $G(d)$ к полному, тем больше возможностей передачи МП-потока в сети (в том числе “обходными путями”), но добавление новых ребер всегда требует дополнительных затрат. Значит, важно заранее выявить наиболее подверженные влиянию КрОС-повреждений информационные направления. Наглядную основу для принятия решений в данном вопросе предоставляет фиг. 1 (см. пример ее построения для модельной сети связи и управления в разд. 7).

6. ЗАДАЧА ЗА ПРОТИВНИКА

Обсудим теперь игровую постановку задачи анализа уязвимости МП-сети в контексте модели “оборона против нападения” [5], где условного противника считаем разрушающим ребра физического графа сети. В постановках разд. 4 мощность повреждения фигурировала лишь косвенно – в рамках отбора исследуемых повреждений при формировании $W$. При этом сразу рассматривались в определенном смысле “экономные” повреждения, соответствующие минимальным разрезам, когда с меньшими параметрами нельзя было разделить выбранную тяготеющую пару. В границах $W$ все $w$ считались равнозначными, и оценивалось их влияние независимо от мощности $\mu (w)$. В задаче за противника неправильно не учитывать число разрушаемых ребер. В общем случае можно также учитывать физическую длину, пропускную способность, близость расположения ребер в КрОС-повреждении. Укажем еще статью [6], где введен параметр стоимости удаления каждого ребра и решается двухкритериальная задача за противника по критериям минимизации стоимости повреждения и МРМ-потока в поврежденной сети (повреждения, хотя и структурные, но в основном не относятся к критически опасным). Однако далее для сохранения логики настоящей статьи ограничимся лишь параметром мощности повреждения и теми характеристиками, которые уже были определены в разд. 3, 4.

Наиболее просто для сравнения стратегий противника построить по ним двумерное множество точек, аналогичное изображенному на фиг. 2, отложив для каждого $w \in W$ на координатных осях $\mu (w)$ – мощность (число ребер) повреждения и $\sigma (w)$ – общее число информационных направлений (в данном случае пар вершин), для которых МРМ-потоки оказываются равными нулю после повреждения $w$.

Повреждения $w{\kern 1pt} {\text{*}} \in W$, на которых достигаются максимальные значения $\sigma (w)$ при “сравнительно малых” значениях $\mu (w)$ – небольшом числе ребер в соответствующем $w$ разрезе – играют существенную роль для стороны “обороны” при планировании мер по противодействию разрушительным атакам “противника” на системы связи и управления. Аналогичные рисунки могут быть построены и для каждого типа повреждения отдельно, что позволит сравнивать между собой различные КрОС-повреждения одного типа.

Здесь отметим, что КрОС-повреждения из множества $U{\kern 1pt} {\text{*}}$ отличаются от элементов $H{\kern 1pt} {\text{*}} \cup Q{\kern 1pt} {\text{*}}$. Они сразу разделяют большое число (не меньше $2(n - 1)$) тяготеющих пар, а их мощность можно определить не степенью соответствующей вершины, но к примеру, положить равной 1, поскольку при удалении одной вершины из физического графа сети все инцидентные ей ребра этого графа автоматически оказываются нефункционирующими (как бы повисая в воздухе). Чтобы формально отличить при этом концевые вершины от транзитных, значимых и для потоков других видов продуктов, предложим следующее.

При определении относительных показателей ущерба $\rho (u)$ и $\delta (u)$ можно вычитать из знаменателя число информационных направлений, напрямую связанных с удаленной вершиной, и использовать

Это позволит также более адекватно проводить сравнение последствий от $u \in U{\kern 1pt} {\text{*}}$ с остальными $w \in H{\kern 1pt} {\text{*}} \cup Q{\kern 1pt} {\text{*}}$. Тем не менее для упрощения построений в рассматриваемом ниже примере остановимся на исходной постановке разд. 5.

7. ПРИМЕР РАСЧЕТА ХАРАКТЕРИСТИК УЯЗВИМОСТИ

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

Вершины сети с индексами 7–10 однотипны и не различаются при анализе, обозначим их общим индексом $g$. Аналогично 1-ю и 2-ю вершины пометим индексом $j$, а к 3-й и 5-й отнесем обозначение $y$. Указанные индексы будем также использовать со штрихами. Нетрудно видеть, что до повреждений (для левого графа с фиг. 3) МРМ-потоки $z_{i}^{0} = 1$ для всех тех ${{p}_{i}}$, в состав которых входят вершины с индексами $g$, обозначим через $D$ множество этих тяготеющих пар. Кроме того, $z_{i}^{0} = 3$ для ${{p}_{i}} = ({{v}_{6}},{{v}_{4}})$. МРМ-потоки $z_{i}^{0} = 2$ для всех остальных ${{p}_{i}}$, в состав которых входят вершины с индексами $y$, обозначим их множество через $Y$, и для оставшихся тяготеющих пар (т.е. для отвечающих за связи вершин с индексами $j$ между собой или с ${{v}_{6}}$, ${{v}_{4}}$), обозначаемых далее через $J$.

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

Ясно, что для ${{p}_{i}} \in D$ МРМ-разрез состоит из единственного ребра $({{r}_{6}},{{r}_{g}})$, инцидентного $g$-й вершине, и совпадает с $u(g)$, полученным отделением этой вершины. Для ${{p}_{i}} \in J$, не относящихся к ${{v}_{4}}$, МРМ-разрезы состоят из пары ребер, выбираемой из тройки $({{r}_{6}},{{r}_{1}}),\;({{r}_{6}},{{r}_{2}})$ и $({{r}_{2}},{{r}_{1}})$, два из трех таких разрезов совпадают с $u(j)$. Для направлений ${{p}_{i}} = ({{v}_{j}},{{v}_{4}})$ МРМ-разрезы тоже должны содержать по два ребра. Но так как вершину ${{v}_{4}}$ нельзя отделить от ${{v}_{6}}$ (через которую проходит ее связь с ${{v}_{j}}$) менее, чем тремя ребрами, то набор разрезов для ${{p}_{i}} = ({{v}_{1}},{{v}_{4}})$ состоит из двух уже встречавшихся пар ребер: $\{ ({{r}_{6}},{{r}_{1}}),({{r}_{6}},{{r}_{2}})\} $ и $\{ ({{r}_{6}},{{r}_{1}}),({{r}_{1}},{{r}_{2}})\} = u(1)$, – разделяющих $({{v}_{6}},{{v}_{1}})$, и аналогично для ${{p}_{i}} = ({{v}_{2}},{{v}_{4}})$. Любой МРМ-разрез для ${{p}_{i}} = ({{v}_{6}},{{v}_{4}})$ ожидаемо содержит 3 ребра и может быть получен как с помощью отделения 4-й вершины – $u(4)$, так и путем удаления иных троек ребер, например $({{r}_{6}},{{r}_{3}}),({{r}_{6}},{{r}_{4}})$ и $({{r}_{6}},{{r}_{5}})$. В свою очередь МРМ-разрезами для ${{p}_{i}} \in Y$ (тяготеющих пар, включающих ${{v}_{y}}$) могут быть только $u(y)$, поскольку все другие разрезы для этих информационных направлений содержат более двух ребер физического графа сети.

Таким образом, $W = U{\kern 1pt} {\text{*}} \cup \{ ({{r}_{6}},{{r}_{1}}),({{r}_{6}},{{r}_{2}})\} $ $ \cup \;\{ ({{r}_{6}},{{r}_{3}}),({{r}_{6}},{{r}_{5}}),({{r}_{6}},{{r}_{4}})\} $ $ \cup \;\{ ({{r}_{6}},{{r}_{3}}),({{r}_{4}},{{r}_{5}}),({{r}_{6}},{{r}_{4}})\} \cup $ $ \cup {\kern 1pt} \;\{ ({{r}_{4}},{{r}_{3}}),({{r}_{6}},{{r}_{5}}),({{r}_{6}},{{r}_{4}})\} $ и состоит из 14 разрезов. Из них 4 последних находятся лишь в $H{\kern 1pt} {\text{*}} = Q{\kern 1pt} {\text{*}}$, т.е. не будут учтены при анализе уязвимости по отношению к удалению вершин [7].

Самым мощным КрОС-повреждением из $W$ является $u(6)$ (для него $\mu (u(6)) = 9$). Оно приводит к сети справа на фиг. 3, для которой могут быть переданы потоки лишь 4 тяготеющих пар (или по 8 информационным направлениям, если считать туда и обратно) из 45. Центральные вершины отнесены к критически значимым и в [7]. Понятно, что это повреждение будет парето-оптимальным [5] в задаче за противника из разд. 6 и даст правую верхнюю точку на фиг. 2, если его построить для графа с фиг. 3. Отметим, что МРМ-поток для всех сохранившихся тяготений уменьшился вдвое. Так что значение неполного ущерба (см. разд. 4) равно 0.5 и той же величине в данном случае равна медиана неполного ущерба для КрОС-повреждения $u(6)$ из $W$. Поэтому ${{P}^{ \pm }}(u(6))$ – пустое множество.

Также паретовскими будут 12-е и 11-е КрОС-повреждения в $W$, являющиеся подмножествами разреза $u(6)$ с мощностями 3 и 2 соответственно. При их удалении не нарушаются связи для 24 или 29 тяготеющих пар, причем для 21 или 28 из них ущерба не будет. Неполный ущерб в последнем случае возникает для ${{p}_{i}} = ({{v}_{1}},{{v}_{2}})$ при КрОС-повреждении ${{w}_{{11}}} = \{ ({{r}_{6}},{{r}_{1}}),({{r}_{6}},{{r}_{2}})\} $. Этот ущерб тоже равен 0.5, но уже больше медианы, поскольку она теперь равна 0 (много пар с нулевым ущербом). При КрОС-повреждении ${{w}_{{12}}}$ для трех ${{p}_{i}}$ из $Y$, для которых сохранилась связь, получается все тот же неполный ущерб 0.5, больший медианы. В итоге все ${{p}_{i}}$ с ненулевым неполным ущербом входят в ${{P}^{ \pm }}(w)$ для $w = {{w}_{{12}}}$ или ${{w}_{{11}}}$. Таким образом, “невершинные” МРМ-разрезы играют существенную роль при анализе уязвимости МП-сети (даже при отсутствии явно выраженных ребер-мостов в ее физическом графе).

Вершинное КрОС-повреждение $u(4)$, имеющее мощность 3 (как и ${{w}_{{12}}}$), оставляет неразделенными 36 тяготеющих пар и потому не будет давать эффективную точку на фиг. 2 (доминируется МРМ-разрезом ${{w}_{{12}}}$). Аналогично для вершинных повреждений $u(3),\;u(5)$, а также для $u(1)$ и $u(2)$, которые доминируются еще и ${{w}_{{11}}}$. Для каждого $u(1)$–$u(5)$ много ${{p}_{i}}$ с нулевым неполным ущербом, так что и медиана неполного ущерба для указанных КрОС-повреждений будет нулем.

Промежуточное положение между $u(4)$ и ${{w}_{{11}}}$ занимают МРМ-разрезы ${{w}_{{13}}}$ и ${{w}_{{14}}}$. Обладая мощностью 3, они разделяют меньшее число пар, чем ${{w}_{{12}}}$, но большее, чем $u(4)$, и сохраняют возможность связи для 29 тяготеющих пар (как МРМ-разрез ${{w}_{{11}}}$, имеющий меньшую мощность). Поэтому указанные разрезы будут доминируемыми по Парето (нестрого) МРМ-разрезами ${{w}_{{11}}}$ и ${{w}_{{12}}}$. Каждому из них (${{w}_{{13}}}$ и ${{w}_{{14}}}$) соответствует одна ${{p}_{i}}$ с ненулевым неполным ущербом. Поскольку разрезы симметричны, то для определенности рассмотрим ${{w}_{{14}}}$. Для него такой ${{p}_{i}}$ оказывается $({{v}_{4}},{{v}_{5}})$, ее ущерб составляет 0.5, что больше медианы, равной нулю.

Осталось проанализировать МРМ-разрезы $u(7)$–$u(10)$, имеющие единичную мощность и входящие в множество ребер $u(6)$. Они все являются паретовскими (рекордными по критерию $\mu $), хотя разделяют наименьшее число тяготеющих пар (те же 9, что и $u(1)$– $u(5)$, рассмотренные выше). На фиг. 2 (если его построить для графа с фиг. 3) они бы все слились в одну крайнюю слева точку. Следует подчеркнуть, что на фиг. 2 звездочкой выделены не только паретовские точки, но и точки Слейтера [5], которые в общем случае тоже могут заинтересовать исследователя, характеризуя ожидаемые КрОС-повреждения. Однако для рассматриваемого примера слейтеровскими оказываются все разрезы из $W$. Это связано с достаточно простой структурой модельного графа с фиг. 3 (реальные сети состоят из большего числа разнообразных компонент), а также с унификацией пропускной способности для всех ребер (принятой в примере лишь для наглядности структурных зависимостей).

Более интересным для указанного примера выглядит фиг. 1, хотя и здесь (в силу тривиальности медианы для всех $w \in W$) наблюдается небогатое разнообразие значений. Построим их на фиг. 4. Начнем с ${{p}_{i}} \in D$. Каждую тяготеющую пару ${{p}_{i}} = ({{v}_{6}},{{v}_{g}})$ разделяют такие КрОС-повреждения из $W,$ как $u(g)$ и $u(6)$, пару ${{p}_{i}} = ({{v}_{g}},v_{g}^{'}) - u(g),u(g')$ и $u(6)$, для пар ${{p}_{i}} = ({{v}_{g}},{{v}_{j}})$ к $u(g),u(j)$ и $u(6)$ добавится ${{w}_{{11}}}$, а для пар ${{p}_{i}} = ({{v}_{g}},{{v}_{y}})$ к $u(g),\;u(y)$ и $u(6)$ добавятся ${{w}_{{12}}}$ и ${{w}_{{13}}}$ или ${{w}_{{14}}}$. Максимальное (для ${{p}_{i}} \in D$) число 6 разрезов из 14, образующих $W,$ будет разделять каждую пару ${{p}_{i}} = ({{v}_{g}},{{v}_{4}})$, это МРМ-разрезы ${{w}_{{12}}}$–${{w}_{{14}}}$ и вершинные разрезы $u(g),\;u(4)$ и $u(6)$. Получим ${{\rho }_{i}}(W)$, равные 1/7, 3/14, 2/7, 5/14 и 3/7 соответственно. Для всех этих случаев ${{\varphi }_{i}}(W) = 0$, поскольку повреждения, не направленные против ${{p}_{i}}$ из $D$, не снижают ее МРМ-поток, равный 1. Наименее уязвимыми оказались четыре пары $({{v}_{6}},{{v}_{g}})$ – левая точка на горизонтальной оси фиг. 4 (для удобства в скобках рядом с точками приведено число тяготеющих пар, им соответствующих).

Для ${{p}_{i}} \in Y$ приходим к следующему. Обе тяготеющие пары ${{p}_{i}} = ({{v}_{6}},{{v}_{y}})$ разделяются четырьмя КрОС-повреждениями $u(y),\;u(6),\;{{w}_{{12}}}$ и ${{w}_{{13}}}$ или ${{w}_{{14}}}$. Пару ${{p}_{i}} = ({{v}_{y}},v_{y}^{'})$ разделяют $u(y),\;u(y'),\;{{w}_{{13}}}$ и ${{w}_{{14}}}$. Для пар ${{p}_{i}} = ({{v}_{y}},{{v}_{j}})$ к вершинным $u(y),\;u(j)$ и $u(6)$ добавятся МРМ-разрезы ${{w}_{{11}}},\;{{w}_{{12}}}$ и либо ${{w}_{{13}}},$ либо ${{w}_{{14}}}$, а для пар ${{p}_{i}} = ({{v}_{4}},{{v}_{y}})$ к $u(4)$ и $u(y)$ добавится ${{w}_{{13}}}$ или ${{w}_{{14}}}$. Получим ${{\rho }_{i}}(W)$, равные 2/7, 2/7, 3/7, 3/14 соответственно. Для первых двух пар их МРМ-потоки снижает вдвое не разделяющий их МРМ-разрез ${{w}_{{14}}}$ или ${{w}_{{13}}}$, а еще $u(4)$, так что $\left| {{{W}^{ + }}(i)} \right| = 10$ и ${{\varphi }_{i}}(W) = 0.2$, поскольку, когда неполный ущерб ненулевой, он больше медианы для всех $w$, кроме $u(6)$ (см. выше). МРМ-поток для $({{v}_{3}},{{v}_{5}})$ снижается без разрыва связи при повреждениях $u(6),\;{{w}_{{12}}}$ и $u(4)$. Однако показатель ${{\varphi }_{i}}(W)$ для этого направления равен 0.2, а не 0.3, так как для повреждения $u(6)$ медиана равна 0.5 и рассчитанный ущерб не превосходит медианы. Для случая ${{p}_{i}} = ({{v}_{y}},{{v}_{j}})$ к уменьшению МРМ-потока вдвое приводят те же два повреждения, что и в первом случае, но еще и $u(v_{j}^{'})$, причем $\left| {{{W}^{ + }}(i)} \right| = 8$, поэтому ${{\varphi }_{i}}(W) = 3{\text{/}}8$. Для обеих последних тяготеющих пар неполный ущерб возникает от $u(6),\;{{w}_{{12}}}$ и либо от ${{w}_{{14}}}$, либо от ${{w}_{{13}}}$, итого ${{\varphi }_{i}}(W) = 2{\text{/}}11$ (так как для них $\left| {{{W}^{ + }}(i)} \right| = 11$).

Для тяготеющей пары $({{v}_{1}},{{v}_{2}})$ разделяющими являются $u(1)$ и $u(2)$, а $u(6)$ и ${{w}_{{11}}}$ приводят к неполному ущербу. Это дает для нее показатель ${{\rho }_{i}}(W)$, равный 1/7, и показатель ${{\varphi }_{i}}(W)$, равный 1/12. Для еще двух ${{p}_{i}} = ({{v}_{6}},{{v}_{j}})$ в $J$ разделяющими повреждениями будут $u(6),\;u(j)$ и ${{w}_{{11}}}$, а неполный ущерб (снижение вдвое) вызывает $u(j')$. Отсюда ${{\rho }_{i}}(W) = 3{\text{/}}14$ и ${{\varphi }_{i}}(W) = 1{\text{/}}11$. Для каждой из оставшихся в $J$ двух ${{p}_{i}} = ({{v}_{4}},{{v}_{j}})$ разделяющими повреждениями будут $u(6),\;u(j),\;u(4)$ и ${{w}_{{11}}}$–${{w}_{{14}}}$, а неполный ущерб (снижение вдвое) все так же вызывает лишь $u(j')$. Получаем ${{\rho }_{i}}(W) = 1{\text{/}}2$ при ${{\varphi }_{i}}(W) = 1{\text{/}}7$.

И, наконец, направление $({{v}_{4}},{{v}_{6}})$ разделяют $u(6),\;u(4),\;{{w}_{{12}}} - {{w}_{{14}}}$, т.е. значение ${{\rho }_{i}}(W)$ для него равно 5/14. Повреждения $u(3)$ и $u(5)$ для этой тяготеющей пары приводят к сокращению МРМ-потока на треть. (В наборе $W$ нет разреза, дающего ей больший неполный ущерб.) Но поскольку медиана неполного ущерба для этих вершинных повреждений равна нулю, то показатель ${{\varphi }_{i}}(W)$ равен 2/9. Последняя пара имеет одни из самых плохих характеристик уязвимости. Хуже нее лишь показатели для четырех пар ${{p}_{i}} = ({{v}_{y}},{{v}_{j}})$, точка для которых отмечена звездочкой на фиг. 4, соответствующем фиг. 1 для сети с фиг. 3. Это значит, что связь для них надо усиливать в первую очередь. Еще одна отмеченная звездочкой критическая точка сопоставлена двум ${{p}_{i}} = ({{v}_{4}},{{v}_{j}})$ с максимальным значением ${{\rho }_{i}}(W) = 1{\text{/}}2$, хотя и при не самых больших величинах ${{\varphi }_{i}}(W) = 1{\text{/}}7$ неполного ущерба.

Полученный результат демонстрирует отличие предложенного в данной статье подхода к анализу уязвимости от традиционных. На фиг. 4, где речь идет не о наиболее влияющих на сетевые связи повреждениях, как на фиг. 2, а о наиболее уязвимых информационных направлениях, как на фиг. 1, вторым по порядку таким направлением оказалось $({{v}_{4}},{{v}_{6}})$, не только соединенное напрямую ребром сети (в отличие от $(v_{g}^{'},{{v}_{g}})$, например), но и имеющее два обходных пути соединения, причем реберно-независимых. И вообще, самые уязвимые тяготеющие пары соединяют вершины, имеющие степень выше 1. Это обусловлено именно принятой концепцией анализа: исследовать подверженность тяготеющей пары влиянию возмущений, направленных не только против нее непосредственно. Идея состоит в том, чтобы в предположении равных шансов на любое повреждение из $W$ определить информационные направления, наиболее часто разделяемые или получающие наибольший ущерб связи без разделения.

Указанная идея несомненно может усложняться путем введения различных весов для разных КрОС-повреждений или путем расширения $W$, в частности рассмотрения комбинаций элементов $w$ (для этого в разд. 6 вводится их ранжирование). Однако в чистом виде суть предложения – в учете самых простых (одновершинных или минимальных однопродуктовых) разрезов. Задача поиска минимального МП-разреза не ставится, так как учет его влияния косвенно предполагает информированность условного противника (разрушающего сеть) о структуре тяготений, что представляется слишком нарочитым. В итоге удается ограничиться постановками лишь полиномиально-разрешимых задач, число которых определяется мощностью рассматриваемого множества повреждений и квадратично зависит от числа вершин в графе сети, и при этом дать информативные оценки способности физического графа МП-сети обеспечивать ее логические связи.

8. ЗАКЛЮЧЕНИЕ

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

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

Вместе с тем с учетом второго направления принимаем во внимание не все виды структурных повреждений, а наиболее экономные и эффективные для разрушения связей в сети способы. Прежде всего к ним относятся введенные в работе КрОС-повреждения, т.е. разрезы в графе $G(d)$ сети. Далее среди разрезов выбираются минимальные как по числу ребер, так и по их пропускной способности, и к ним добавляются разрезы, отделяющие по одной вершине сети. Устойчивость логической связи по отношению к множеству указанных разрезов, когда разрез не нацелен прямо против нее, и предлагается считать показателем, обратным уязвимости. Рассмотрены две содержательно различающиеся характеристики уязвимости и для векторов их значений определяется граница Парето, выявляющая наиболее уязвимые тяготеющие пары. Отметим, что в отличие от [16] здесь не ставится задача поиска разреза, разделяющего сразу все тяготеющие пары.

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