The problem of distribution and merging of discrete correspondence flows in individual zones of a hierarchical communication network

Abstract

The article is devoted to the study of the subproblem of distribution and merging of correspondence flows in separate zones of the backbone network, which arises when solving the general problem of optimizing the hierarchical structure of a multicommodity communication network with discrete flows and parameters. In a multicommodity network, each node can exchange correspondence (products, goods, cargo, messages) with other nodes. Correspondence is characterized by a source node, a drain node and a value, which for transport networks is given by the number of packaged goods in a package of a unified size, and for data transmission networks – by the number of bytes, kilobytes, etc. In the backbone network, all correspondence is transported in vehicles in transport units of a given size (capacity, volume) or transmitted via communication channels. The size of a transport block is measured by the number of units of correspondence that fit into it (for example, 40 packaged goods, 100 gigabytes). All trunk nodes are sorting centers in which correspondence is first sorted by destination addresses (nodes) and then packed as consolidated correspondence into transport blocks. Since the size of individual correspondence is much smaller than the size of the transport block, they can be combined (packed) with correspondence with other destination addresses several times and in different nodes during sorting. There are three levels of hierarchy in the network – backbone, zonal and internal and four types of nodes – trunk nodes of the first, second and third types, forming the backbone and zonal levels of the network and nodes of the fourth type, which are subordinate to each trunk node and form internal levels of the network. Node types differ from each other in functionality. The main task of the study is to develop a mathematical model and algorithms for solving the subproblem of optimizing the distribution and merging (sorting) of correspondence flows at the zonal levels of the network. It is shown that it can be formulated as a linear programming problem with a block structure of constraints and the Danzig-Wolf decomposition method and other methods of integer programming can be used to solve it. To solve the problem on real networks, approximate algorithms based on the construction of the shortest paths are proposed.

Prombles in programming 2024; 2-3: 53-61