Combinatorial problem solving method by allocating resources

There is a class of combinatorial problems that cannot be solved even on modern personal computers. You can use various means of working with high-performance computing, such as supercomputers and cloud services for working with them. However, in some situations, this approach is impractical for scientific computing due to its high cost, low scalability, and limited access. The main goal of this work is the development and study of one of the methods for solving such problems, based on the distribution of available computing resources. For this purpose, a utility that implements this method was developed. It is a client application of a distributed computing network. Network interaction is provided by building an overlay peer-to-peer (P2P) network. P2P architecture is software implemented using UDP. To test the resulting utility, we chose the task of forming user groups for distributing channel flows when building streaming television of the «VUD model». ViewUpload Decoupling-scheme (VUD), which strictly decouples data to what peer uploads and what it personally views. It’s based on the split of downloaded user data streams into two types: the stream of the chosen TV channel, and the stream (one or more) of the other TV channel, exclusively to deliver it to other users. For the VUD model, there is a probabilistic model of data exchange between users in a homogeneous and heterogeneous in terms of the user distribution speed of a P2P network, which allows the analysis of the basic service quality indicator in streaming networks - the probability of the state of universal transmission. The calculation of this probability involves the multiple use of combinatorial formulas and, by its algorithmic complexity, belongs to the NP class problems. As a result of the research, information was collected on the efficiency of the resource allocation method for solving combinatorial problems, the possibilities of expanding the subject area were considered, and a trial version of the distributed computing peer-to-peer network was constructed. The main goal of this work is to develop a method for solving such problems. For this, a resource allocation model was built for two different computation algorithms. During the research the parameters of the model were refined and the current version of the program was developed. According to the results of the program test, data on the effectiveness of each of the algorithms were obtained and their comparative analysis was conducted. Copyright © 2019 for the individual papers by the papers’ authors.

Conference proceedings
  • 1 Department of Information Technologies, Peoples’ Friendship University of Russia (RUDN University), 6 Miklukho-Maklaya str., Moscow, 117198, Russian Federation
Combinatorial problems; complexity
Date of creation
Date of change
Short link

Other records