Исследование эргодических неоднородных ресурсных сетей с «жадными» вершинами

Автор(ы): Чаплинская Н.В.

Выпуск: 93

Рубрика: Сетевые модели в управлении

Год: 2021

Библиография: Чаплинская Н.В. Исследование эргодических неоднородных ресурсных сетей с «жадными» вершинами // Управление большими системами. Выпуск 93. М.: ИПУ РАН, 2021. С.5-50. DOI: https://doi.org/10.25728/ubs.2021.93.1

Дата опубликования: 30.09.2021

Ключевые слова: графовая динамическая пороговая модель, ресурсная сеть, модель "жадных" вершин, топология эргодических неоднородных сетей

Аннотация: Рассмотрена модификация графовой пороговой динамической модели "ресурсная сеть" -- "ресурсная сеть с жадными вершинами". На каждом такте дискретного времени вершины графа передают друг другу ресурс по ребрам с~ограниченными пропускными способностями, причем сначала передают имеющийся ресурс в собственные петли, а затем остаток ресурса распределяют в исходящие ребра по правилам стандартной ресурсной сети (пропорционально пропускным способностям с учетом их ограничения). Рассмотрена топология эргодической неоднородной ресурсной сети с "жадными" вершинами -- сеть описывается сильно связным ориентированным графом. Показано, что при значениях суммарного ресурса, не превосходящих суммы пропускных способностей всех петель, сеть с "жадными" вершинами останавливается, что невозможно для стандартной эргодической ресурсной сети и обуславливается наличием модифицированных петель; исследуется характер остановки сети. Для значений суммарного ресурса, превышающих суммы пропускных способностей всех петель, доказывается, что с определенного момента времени сеть будет функционировать эквивалентно соответствующей стандартной ресурсной сети.

Author(s): Chaplinskaya N.

Article title: Research of ergodic heterogeneous "greedy-vertices" resource networks

Issue: 93

Year: 2021

Keywords: graph dynamic threshold model, resource net, "greedy-vertices" model, topology of ergodic heterogeneous networks

Abstract: A modification of the graph threshold dynamic model "resource network" -- "resource network with greedy vertices" is considered. At each discrete-time moment, the vertices of the graph transfer the resource to each other through the edges with limited throughputs. First they transfer the available resource to their own loops, and then the rest of the resource is distributed to the outgoing edges according to the rules of the standard resource network (in proportion to the throughputs taking into account their limitations). The topology of an ergodic heterogeneous resource network with "greedy" vertices is considered -- the network is described by a strongly connected directed graph. It is shown that when the values of the total resource are not larger than the sum of the throughputs of all loops, the network with "greedy" vertices stops, which is impossible for a standard ergodic resource network and is caused by the existence of modified loops; the nature of the network stop is investigated. For the values of the total resource that are larger than the sum of the throughputs of all loops, it is proved that from a certain time moment the network will function equivalently to the corresponding standard resource network.