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

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

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

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

При создании, развитии и эксплуатации телекоммуникационных систем в настоящее время используются потоковые модели [4]. В частности, указанные модели применяются для поиска стратегий управления и построения диспетчерских правил распределения потоков, нагрузок и ресурсов в многопользовательских сетях [5, 6]. В русле исследований по разработке SPLIT-методов [7–10] лежат представленные в разд. 2–4 алгоритмические схемы выравнивания нагрузок и получения уравнительных распределений межузловых потоков по различным маршрутам. В статье используются процедуры поиска всех кратчайших путей с полиномиальными оценками вычислительных затрат [11].

1. Математическая модель. Для описания многопользовательской сетевой системы связи воспользуемся следующей математической записью модели передачи многопродуктового потока. Сеть $G$ задается множествами $\langle V,\;R,\;U,P\rangle $: узлов (вершин) сети $V = \{ {{v}_{1}},{{v}_{2}},...,{{v}_{n}},...,{{v}_{N}}\} $; неориентированных ребер $R = \{ {{r}_{1}},{{r}_{2}},...,{{r}_{k}},...,{{r}_{E}}\} $; ориентированных дуг $U = \{ {{u}_{1}},{{u}_{2}},...,{{u}_{k}},...,{{u}_{{2E}}}\} $; пар узлов-корреспондентов $P = \{ {{p}_{1}},{{p}_{2}},...,{{p}_{M}}\} $. Предполагается, что в сети отсутствуют петли и сдвоенные ребра.

Ребро ${{r}_{k}} \in R$ соединяет смежные вершины ${{v}_{{{{n}_{k}}}}}$, ${{v}_{{{{j}_{k}}}}}$. Каждому ребру ${{r}_{k}}$ ставятся в соответствие две ориентированные дуги ${{u}_{k}}$, ${{u}_{{k + E}}}$ из множества U.  Дуги $\{ {{u}_{k}},{{u}_{{k + E}}}\} $ определяют прямое и обратное направления передачи потока по ребру ${{r}_{k}}$ между концевыми вершинами ${{v}_{{{{n}_{k}}}}}$, ${{v}_{{{{j}_{k}}}}}$.

В многопользовательской сети $G$ рассматривается $M = N(N - 1)$ независимых, невзаимозаменяемых и равноправных межузловых потоков различных видов. Каждой паре узлов-корреспондентов ${{p}_{m}}$ из множества $P$ соответствуют: вершина-источник с номером ${{s}_{m}}$, из ${{s}_{m}}$ входной поток m-го вида поступает в сеть; вершина-приемник с номером ${{t}_{m}}$, из ${{t}_{m}}$ поток m-го вида покидает сеть. Обозначим через ${{z}_{m}}$ величину межузлового потока $m$-го вида, поступающего в сеть через узел с номером ${{s}_{m}}$ и покидающего сеть из узла с номером ${{t}_{m}}$; ${{x}_{{mk}}}$, ${{x}_{{m(k + E)}}}$ – поток m-го вида, который передается по дугам ${{u}_{k}}$ и ${{u}_{{k + E}}}$, согласно направлению передачи, ${{x}_{{mk}}} \geqslant 0$, ${{x}_{{m(k + E)}}} \geqslant 0$, $m = \overline {1,M} $, $k = \overline {1,E} $; $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}}$ в ${{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}})$.

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

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

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

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

Для каждой пары узлов-корреспондентов ${{p}_{m}} \in P$, для некоторого допустимого межузлового потока ${{\tilde {z}}_{m}}$ и соответствующих дуговых потоков ${{\tilde {x}}_{{mk}}}$, $k = \overline {1,2E} $, величина

характеризует результирующую межузловую нагрузку (далее RI-нагрузку, от английского resulting internodal load) на сеть при передаче межузлового потока величины ${{\tilde {z}}_{m}}$ из узла-источника ${{s}_{m}}$ в узел-приемник ${{t}_{m}}$. Величина ${{\tilde {y}}_{m}}$ показывает, какая суммарная пропускная способность сети потребуется для передачи дуговых потоков ${{\tilde {x}}_{{mk}}}$. В рамках модели отношение RI-нагрузки и межузлового потока можно трактовать как удельные затраты ресурсов сети при передаче единичного потока $m$-го вида между узлами ${{s}_{m}}$ и ${{t}_{m}}$ при дуговых потоках ${{\tilde {x}}_{{mi}}}$. Величины отвечают межузловому потоку при единичной RI-нагрузке для ${{p}_{m}}$.

Вводится величина

характеризующая реберную суммарную загрузку (РС-загрузку) k-го ребра при одновременной передаче всех межузловых потоков ${{\tilde {z}}_{m}}$ и дуговых потоков $\tilde {x}_{{mk}}^{0}$, $k = \overline {1,2E} $.

2. Распределение межузловых потоков по кратчайшим маршрутам. Для оценки минимальных удельных затрат для различных уравнительных стратегий управления использовалась SRSF-процедура (от английского shortest routes for split flow – кратчайшие маршруты при расщеплении потока). SRSF-процедура позволяет распределять межузловые потоки по маршрутам, состоящим из минимального числа ребер. В данной работе SRSF-процедура применялась для получения предельных загрузок сети при последовательном поэтапном уравнительном распределении межузловых потоков и нагрузок.

Для каждой пары узлов ${{p}_{m}} = ({{s}_{m}},{{t}_{m}})$ в сети $G(1)$ формируется набор ${{H}_{m}}(1)$ всех кратчайших путей [11], которые далее используются как маршруты передачи $m$-го вида потока:

где $h_{m}^{j}(1)$ – список номеров дуг в $j$-м кратчайшем пути в сети $G(1)$ между узлами ${{s}_{m}}$ и ${{t}_{m}}$; ${{\mu }_{m}}(1)$ – число ребер в кратчайшем маршруте $h_{m}^{j}(1)$, а ${{J}_{m}}(1)$ – число кратчайших маршрутов для $m$-й пары.

Для оценки величин “расщепленного” потока для каждой пары ${{p}_{m}} \in P$ по всем маршрутам из ${{H}_{m}}(1)$ передается единичный межузловой поток ${{z}_{m}}$ и подсчитываются значения индикаторной функции:

Вычисляются дуговые потоки для пары ${{p}_{m}}$:

Величина межузлового потока (далее SRS-потока) $z_{m}^{0}(1)$ между узлами ${{s}_{m}}$ и ${{t}_{m}}$ определяется по формулам (1.1) и (2.1). Рассчитывается нормирующий коэффициент

Находятся дуговые потоки:

при передаче которых по ребрам сети межузловой поток из узла ${{s}_{m}}$ в узел ${{t}_{m}}$ равен единице.

На основе маршрутов и дуговых потоков $x_{{mk}}^{0}$ последовательно определяется распределение совместно допустимых межузловых потоков. Подсчитываются остаточные пропускные способности и формируется сеть для проведения следующей итерации. За конечное число итераций, не превосходящее общего количества ребер сети, вычисляются межузловые потоки, при одновременной передаче которых полностью используется пропускная способность всех ребер сети.

При проведении вычислительных экспериментов на первом шаге (t = 1) SRSF-процедуры для сети $G(1)$ пропускная способность ${{d}_{k}}(1)$ каждого ребра ${{r}_{k}} \in R$ полагается равной пропускной способности исходной сети, а его длина – единице:

На основе SRS-потока $z_{a}^{0}(1)$ по формуле (2.2) определяются нормирующие коэффициенты $\omega _{m}^{0}(1)$, $m = \overline {1,M} $. На втором этапе указанные коэффициенты используются для поиска текущих совместно допустимых квот на передачу потоков одновременно между всеми парами p_m, $m = \overline {1,M} $.

Задача 1. Найти $\alpha {\kern 1pt} {\text{*}}(1) = \mathop {\max }\limits_\alpha \alpha $

На основании $\alpha {\kern 1pt} {\text{*}}(1)$ для всех пар ${{p}_{m}} \in P,$ $m = \overline {1,M} $, и всех дуг ${{u}_{k}}$, $k \in {{H}_{m}}(1)$, вычисляются дуговые и межузловые потоки:

Таким образом каждой паре корреспондентов на данном этапе выделяется одна и та же квота α*(1) на передачу допустимого потока при заданных кратчайших маршрутах соединения. Решение задачи 1 позволяет получить уравнительное распределение квот на одновременную передачу межузловых потоков различных видов и соответствующие нагрузки, численно равные $y_{m}^{*}(1)$, $m = \overline {1,M} $.

При фиксированных дуговых потоках подсчитывается остаточная пропускная способность всех ребер в сети $G(2)$:

Для следующей итерации ($t \geqslant 2$) текущая длина каждого ребра ${{r}_{k}}$ для сети $G(2)$ определяется по следующему правилу:

На первом этапе шага $t$ ($t \geqslant 2$) в сети $G(t)$ при текущих ${{l}_{k}}(t)$ для каждой пары узлов ${{p}_{a}} \in P$ определяется длина ${{L}_{a}}(t)$ кратчайшего маршрута:

Если длина ${{L}_{a}}(t) \geqslant {{N}^{2}}$, то для пары ${{p}_{a}}$ не существует пути соединения в сети $G(t)$ и текущее значение SRS-потока полагается равным нулю:

Если же длина ${{L}_{a}}(t) < {{N}^{2}}$, то для пары p_a строится множество ${{H}_{a}}(t)$ всех кратчайших маршрутов и, согласно SRSF-процедуре, вычисляются текущий SRS-поток $z_{a}^{0}(t)$, дуговые потоки $x_{{ak}}^{0}(t),$ $x_{{a(k + E)}}^{0}(t)$ для дуг ${{u}_{k}}$, $k \in {{H}_{a}}(t)$, а также коэффициенты:

а из решения задачи 2 определяется величина текущей квоты α*(t).

Задача 2. Найти $\alpha {\kern 1pt} {\text{*}}(t) = \mathop {\max }\limits_\alpha \alpha $

На основании решения задачи 2 на шаге $t$ ($t \geqslant 2$) находятся: текущие допустимые значения межузловых потоков, которые могут передаваться в сети $G(t)$ одновременно для всех пар ${{p}_{m}} \in P$:

На заключительном этапе текущего шага $t$ ($t \geqslant 2$) для каждого ребра сети вычисляется остаточная пропускная способность сети $G(t + 1)$:

и осуществляется проверка следующих условий.

Если после завершения очередного шага $t$ окажется, что хотя бы для одного ребра ${{r}_{k}} \in R$ остаточная пропускная способность ${{d}_{k}}(t + 1) > 0$, то формируется новая сеть $G(t + 1)$ и производится переход к следующей итерации.

Если же ${{d}_{k}}(t + 1) = 0$ для всех $k = \overline {1,E} $, то происходит останов, поскольку все пропускные способности ребер исчерпаны и сеть полностью загружена. Финальная итерация обозначается через T.

Результирующие межузловые и реберные потоки для каждой пары ${{p}_{m}}$, $m = \overline {1,M} $, обозначаются через $z_{m}^{*}({\mathbf{T}}),\;y_{m}^{*}({\mathbf{T}})$ и соответственно равны:

Удельные затраты $w_{m}^{*}({\mathbf{T}})$ при передаче межузловых потоков одновременно по всем маршрутам ${{H}_{m}}(1),{{H}_{m}}(2),...,{{H}_{m}}(T)$:

Для анализа результатов вычислительных экспериментов формируется несколько массивов данных. Множество пар-корреспондентов P разбивается на два непересекающихся подмножества: смежных пар узлов-корреспондентов ${{P}_{ + }}$, расположенных в концевых вершинах ребра ${{r}_{k}}$, $k = \overline {1,E} $, и ${{P}_{ - }}$ – несмежных пар, кратчайший маршрут соединения для которых содержит более одного ребра:

На каждой итерации $t = \overline {1,T} $ формируются массивы расчетных данных по следующему правилу:

если ${{p}_{m}} \in {{P}_{ + }}$, то $z_{m}^{*}(t),\;y_{m}^{*}(t),\;w_{m}^{*}(t)$ помещаются в массивы ${\mathbf{Z}}_{ + }^{*}(t)$, ${\mathbf{Y}}_{ + }^{*}(t)$, ${\mathbf{W}}_{ + }^{*}(t)$;

если ${{p}_{m}} \in {{P}_{ - }}$, то $z_{m}^{*}(t),\;y_{m}^{*}(t),\;w_{m}^{*}(t)$ попадают в ${\mathbf{Z}}_{ - }^{*}(t)$, ${\mathbf{Y}}_{ - }^{*}(t)$, ${\mathbf{W}}_{ - }^{*}(t)$.

3. Предельное уравнительное распределение межузловых нагрузок. Для оценки допустимых межузловых потоков при предельных распределениях межузловых нагрузок для всех пар узлов ${{p}_{m}} \in P$ также использовалась SRSF-процедура, подробно описанная в разд. 2. На первом этапе определяются реберные загрузки для $m = \overline {1,M} $ и $k = \overline {1,E} $ при передаче единичных потоков по каждому кратчайшему маршруту из ${{H}_{m}}(t)$, $m = \overline {1,M} $. Для каждой пары ${{p}_{m}} \in P$ вычисляются нагрузки:

нормирующие коэффициенты: при которых при передаче соответствующего межузлового потока по всем маршрутам ${{H}_{m}}(t)$, $m = \overline {1,M} $, результирующие межузловые нагрузки $y_{m}^{0} = \theta _{m}^{0}(t)y_{m}^{0}(t)$ будут равны единице.

При выполнении текущего шага $t$ SRSF-процедуры в сети $G(t)$ при найденных значениях ${{d}_{k}}(t)$ и ${{l}_{k}}(t)$ для каждой пары ${{p}_{a}} \in P$ находится набор кратчайших маршрутов ${{H}_{a}}(t)$.

На основе величины $y_{a}^{0}(t)$ при передаче межузлового SRSF-потока $z_{a}^{0}(t)$ по всем кратчайшим маршрутам из ${{H}_{a}}(t)$ по формуле (3.1) вычисляются нормирующие коэффициенты $\theta _{a}^{0}(t)$, которые далее используются для поиска равных нагрузок при передаче соответствующих межузловых потоков одновременно между всеми парами ${{p}_{a}} \in P$.

Задача 3. Найти $\beta {\kern 1pt} *(t) = \mathop {\max }\limits_{\beta > 0} \beta $

Решение задачи 3 $\beta {\kern 1pt} *(t)$ определяет текущие совместно допустимые значения дуговых потоков и реберных нагрузок:

Решение задачи 3 позволяет на шаге $t$ получить уравнительное распределение нагрузки. Обозначим через $z_{m}^{\Delta }(y_{m}^{{**}}(t))$ межузловые потоки, которые, согласно (1.1), соответствуют дуговым потокам $x_{{mk}}^{{**}}(t)$ и нагрузкам $y_{m}^{{**}}(t) = \beta {\kern 1pt} {\text{*}}(t)$.

Далее вычисляется остаточная пропускная способность ребер в сети $G(t + 1)$:

После завершения очередного шага $t$ осуществляется проверка условий:

если окажется, что хотя бы для одного ребра ${{r}_{k}} \in R$ величина остаточной пропускной способности ${{d}_{k}}(t + 1) > 0$, то формируется новая сеть $G(t + 1)$, определяется длина ребер для $G(t + 1)$:

и производится переход к следующей итерации;

если же ${{d}_{k}}(t + 1) = 0$ для всех $k = \overline {1,E} $, то происходит останов, поскольку все пропускные способности ребер исчерпаны и сеть полностью загружена.

Финальная итерация обозначается через T. Как и в разд. 2, для каждого $t$ вычисляются: результирующие значения межузловых потоков для каждой пары ${{p}_{m}}$:

суммарные реберные нагрузки, которые соответствуют предельному распределению пропускной способности ребер сети: удельные затраты $w_{m}^{{**}}(t)$ при передаче межузловых потоков по всем маршрутам ${{H}_{m}}( \cdot )$:

В ходе экспериментов все полученные данные заносятся в массивы по следующему правилу:

если ${{p}_{m}} \in {{P}_{ + }}$, то $z_{m}^{{**}}(t),\;y_{m}^{{**}}(t),\;w_{m}^{{**}}(t)$ помещаются в массивы ${\mathbf{Z}}_{ + }^{{**}}(t)$, ${\mathbf{Y}}_{ + }^{{**}}(t)$, ${\mathbf{W}}_{ + }^{{**}}(t)$;

если ${{p}_{m}} \in {{P}_{ - }}$, то $z_{m}^{{**}}(t),\;y_{m}^{{**}}(t),\;w_{m}^{{**}}(t)$ попадают в ${\mathbf{Z}}_{ - }^{{**}}(t)$, ${\mathbf{Y}}_{ - }^{{**}}(t)$, ${\mathbf{W}}_{ - }^{{**}}(t)$.

4. Вычислительный эксперимент. Вычислительные эксперименты проводились на моделях сетевых систем, представленных на рис. 1, 2 (базовая и кольцевая сети соответственно). В каждой сети имеется 69 узлов. Пропускные способности ребер ${{d}_{k}}$ выбираются случайным образом из отрезка [900, 999] и совпадают для ребер, присутствующих в обеих сетях. В кольцевой сети пропускная способность каждого из добавленных ребер равна 900. В ходе эксперимента проводилась нормировка, и суммарная пропускная способность в обеих сетях была одинакова:

На рис. 3, 4 представлены диаграммы, позволяющие в ходе вычислительного эксперимента проследить динамику изменения остаточной пропускной способности. На каждой итерации вычисляется $\eta (t)$ – доля ребер сети, для которых остаточная пропускная способность ${{d}_{k}}(t)$ оказывается равной нулю, т.е. ${{d}_{k}}(t) = 0$. На рис. 3, 4 по горизонтальной оси откладываются значения $\eta (t)$, а по вертикальной оси – $\pi (t)$ – доля пар узлов, для которых на шаге t в сети $G(t)$ нет пути соединения и поэтому их SRS-поток $z_{m}^{0}(t)$ равен нулю. Из диаграммы с рис. 3 следует, что при полном использовании пропускной способности 20% ребер для более чем 80% пар-корреспондентов в сети нет пути соединения уже после 10 итерации. Набор из 15 ребер, пропускная способность которых после 10-й итерации использована полностью, можно рассматривать как “узкое место” при одновременной передаче “почти равных” межузловых потоков для 4000 пар-корреспондентов.

Диаграммы на рис. 5, 6 позволяют проанализировать отклонения или “нарушение” уравнительного правила распределения. Точки на диаграммах соответствуют значению нормы векторов-потоков в пространстве $\mathcal{Z}({\mathbf{d}})$ допустимых значений компонент вектора межузловых потоков:

Для каждого распределения $z_{m}^{*}(t)$, $m = \overline {1,M} $, вычисляется сумма потоков $\zeta (t)$ и среднее значение $\lambda {\kern 1pt} {\text{*(}}t)$:

Формируется вектор ${\mathbf{\vec {l}}}(\lambda {\kern 1pt} {\text{*}}(t))$, все компоненты которого равны среднему значению $\lambda {\kern 1pt} {\text{*}}(t)$, т.е.

Для указанного вектора ${\mathbf{\vec {l}}}(\lambda {\kern 1pt} {\text{*}}(t))$ вычисляются норма

и отклонение

На диаграммах рис. 5, 6 значения $\gamma (t)$ откладываются по вертикальной оси, а значения ${\text{dev}}({\mathbf{\vec {z}}}{\kern 1pt} {\text{*}}(t))$ – по горизонтальной. Формально полученные величины можно рассматривать как оценки отклонения межузловых потоков $z_{m}^{*}(t)$ от некоторых “средних” значений $\lambda (t)$ при заданной общей сумме $\zeta (t)$. Расстояние между точками на вертикальной оси показывает, как меняется общая сумма межузловых потоков при переходе к следующей итерации.

По построению диаграмм на рис. 5, 6 отклонение ${\text{dev}}({\mathbf{\vec {z}}}{\kern 1pt} {\text{*}}(t))$ в множестве $\mathcal{Z}({\mathbf{d}})$ – кратчайшее расстояние между точками, заданными векторами ${\mathbf{\vec {l}}}(\lambda {\kern 1pt} {\text{*}}(t))$ и ${\mathbf{\vec {z}}}{\kern 1pt} {\text{*}}(t)$. Вектор-луч ${\mathbf{\vec {l}}}(\lambda {\kern 1pt} {\text{*}}( \cdot ))$ является геометрическим местом точек векторов-распределений равных межузловых потоков. На рис 5, 6 расстояние от начала координат численно равно ${\text{||}}{\mathbf{\vec {z}}}{\kern 1pt} {\text{*}}(t){\text{||}}$, что соответствует “длине” вектора ${\mathbf{\vec {z}}}{\kern 1pt} {\text{*}}(t)$ в $\mathcal{Z}({\mathbf{d}})$.

Геометрическая интерпретация рис. 5, 6 и использование диаграмм рис. 3, 4 упрощает пошаговый анализ результатов выполнения SRSF-процедуры. На начальных итерациях связность сети $G(t)$ начинает нарушаться, поскольку остаточная пропускная способность некоторых ребер становится равной нулю. При этом уклонение $z_{m}^{*}(t)$ от луча ${\mathbf{\vec {l}}}(\lambda {\kern 1pt} {\text{*}}(t))$ – пошагового уравнительного распределения, не превышает 500 единиц. На некотором шаге $\tau $ сеть $G(\tau )$ распадается на фрагменты (подсети), и остаточная пропускная способность ребер $d(\tau )$ распределяется среди пар узлов, лежащих внутри указанных подсетей. Поскольку останов SRSF-процедуры происходит при полной загрузке всех пропускных способностей, то межузловые потоки $z_{m}^{*}(T)$ для смежных пар могут быть очень большими. Таким образом результирующее отклонение ${\text{dev}}({\mathbf{\vec {z}}}{\kern 1pt} {\text{*}}(T))$ может быть значительным, что и подтверждают диаграммы с рис. 5, 6.

На рис. 7, 8 представлены диаграммы, позволяющие проследить изменение остаточной пропускной способности в процессе выполнения пошаговой уравнительной SRSF-процедуры. Для наглядности так же, как и на рис. 5, 6, по горизонтальной оси последовательно откладываются значения ${\text{dev}}({\mathbf{\vec {z}}}{\kern 1pt} {\text{*}}(t))$, по вертикальной – значения

Величина $\rho (\tau )$ равна доле исходного ресурса – суммарной пропускной способности сети $G(\tau )$, который потребовался для одновременной передачи межузловых потоков $z_{m}^{*}(\tau )$, $m = \overline {1,M} $.

Из диаграмм рис. 7, 8 следует, что на начальных итерациях SRSF-процедуры распределяется 60% ресурсов. Плотность точек на рис. 5–8 при значениях ${\text{dev}}({\mathbf{\vec {z}}}{\kern 1pt} *(t)) \leqslant 500$ свидетельствует, что на каждой из этих итераций распределяются незначительные ресурсы (величины пропускной способности). Когда остаточная пропускная способность оказывается меньше 20% от исходной, то сеть распадается на несколько несвязанных между собой фрагментов и оставшиеся ресурсы распределяются за несколько итераций в основном между смежными парами узлов. Таким образом при выполнении SRSF-процедуры останов происходит в точке с координатами ${\mathbf{z}}{\kern 1pt} {\text{*}}(T)$, отстоящей на значительном удалении от луча ${\mathbf{\vec {l}}}(\lambda )$ – условной биссектрисы множества $\mathcal{Z}({\mathbf{d}})$.

Заключение. Как было отмечено во Введении, формально SRSF-процедура является схемой решения лексикографически упорядоченной последовательности задач поиска максимина при распределении межузловых потоков. Фактически SRSF-процедура используется как элемент динамической модели для поэтапного анализа изменения загрузки ребер сети, выявления “узких мест” сети при монотонном увеличении межузловых потоков. Уравнительные правила распределения на каждом шаге позволяют получать текущие оценки минимальных удельных затрат ресурсов.

Последовательный анализ результатов вычислительных экспериментов показал, что уже на первых итерациях 20% ребер оказываются полностью загружены, используется более 60% ресурсов сети и достигаются почти равные значения межузловых потоков для 80% пар узлов. Указанные значения остаются неизменными до конца эксперимента. Полученные наборы полностью загруженных ребер являются “узким местом” сети и практически совпадают при различных уравнительных правилах распределения ресурсов. Достигнутые значения медиан представляют собой ключевой показатель при оценке функционирования многопользовательской сети в стационарном режиме при одновременной совместной передаче межузловых потоков для всех пар-корреспондентов.