Inverse and Direct Maxflow Problem Study on the Free-Oriented ST-Planar Network Graph

Abstract

The issues of data flow optimization in telecommunication networks are considered. The analyses of the problem state of art shows the primarily utilization of logistic Maxflow model on ST-planar directed network graph with predetermined fixed metric. Concluded, that conventional logistic Maxflow model is not adequate to modern telecoms with flexibly reconfigured channels. Introduced the concept of the free-oriented network graph as an enhanced math-model for digital flows simulation. The inverse and direct Maxflow tasks are formulated on the normalised free-oriented ST-planar network graph, and the properties of the graph obtained as functions of vertices number. The direct Maxflow task is studied in tensor form, and the algorithm of test-sequences generation for the inverse Maxflow task is constructed. The inverse Maxflow problem has been analyzed as a discrete optimization task on the Pontryagin maximum principle with two necessary extremum conditions. Related computation algorithm is built with polynomial complexity. Unlike the known approaches, proposed method is relevant to data flow optimization in the software defined networks with dynamically reconfigurable channels. Along with the maximal flow, the flow distribution over the network structure provided. The formalism of the direct Maxflow task can be used for testing the algorithms of inverse Maxflow task solutions, and generation the training sequences for machine learning in AI models