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

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

Выпуск: 89

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

Год: 2021

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

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

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

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

Author(s): Zhilyakova L., Chaplinskaya N.

Article title: Research of complete homogeneous "greedy-vertices" resource networks

Issue: 89

Year: 2021

Keywords: resource net, "greedy-vertices" model, graph dynamic threshold model

Abstract: The modification of the graph dynamic model "resource network" – "resource network with greedy vertices" is described. In this model, the graph vertices at each discrete-time moment exchange resources through the edges with limited throughput, first passing the available resource to themselves via the loop and then distributing the remaining resource to adjacent vertices according to the "standard" resource network rules. These are two rules with threshold switching: if the vertex resource exceeds the total throughput of all its outgoing edges, it gives away the full throughput to each edge; otherwise, it gives the entire available resource, distributing it in proportion to the throughputs of the outgoing edges. The process of functioning of a complete homogeneous resource network with "greedy" vertices at different values of total resource and different initial states is investigated. Possible network states are described; a non-standard state – the shutdown of the network has been identified. Two total resource thresholds, separating zones of different network behavior, have been found: the first threshold divides the zones of "insufficient" and "sufficient" resources, the second divides the zones of "sufficient small" and "sufficient large" resources. For each zone the functioning of the network is described and the asymptotic states and flows are investigated. The examples demonstrating numerical experiments are given for all typical situations.