OPTIMIZATION PROBLEM OF FLOW DISTRIBUTION ON FREE-ORIENTED GRAPHS

Abstract

 The object of research is the processes of digital stream transmission in software-defined telecommunications transport networks (SDN), which provide flexible traffic management and network resource optimization. The subject of the study is methods and algorithmic approaches to the optimal distribution of digital flows on free-oriented graphs using the principles of maximum flow and minimum transit. The paper proposes a modified iterative algorithm (MIA) for solving the problem of optimizing digital flows in software-defined networks (SDN). The algorithm is based on the principles of minimum transit and maximum flow on free-oriented graphs. A description of the software implementation in Python is provided, which allows for automating the process of calculating bandwidth and traffic distribution. The algorithm provides simultaneous calculation of the maximum possible flow between poles S and T and optimal distribution of this flow between alternative ST paths with a minimum number of intermediate vertices, implementing the principle of minimum transit in combination with the principle of maximum flow. The source data uses a normalized ST graph in which the vertices V_n are numbered with natural numbers from 1 to N, and the edges P_k are numbered from 1 to K; vertex V₁ is interpreted as source S, and the vertex with the largest number is interpreted as sink T. The graph structure is specified by the text file graph.txt, where the first line lists all vertices, and the second line lists non-empty edges with their weights in triples (i, j, w). Based on this data, the algorithm builds an internal network model and sequentially performs three main blocks: 1) reading and validating the input graph, 2) iterative search for ST paths of fixed length with recursive updating of residual capacities, 3) calculation of the global maximum flow f_max and formation of a residual matrix that clearly reflects the use of network resources after the MIA has run.