50 UDC 519.179.1:654 Two-criteria Problem On Hypergraphs For Estimating Data Transmission Quality On P2P Networks Anastasia V. Demidova* , Soltan I. Salpagarov† , Alexander S. Pankratov† * Department of Applied Probability and Informatics, Peoples’ Friendship University of Russia (RUDN University), 6 Miklukho-Maklaya str., Moscow, 117198, Russian Federation † Department of Information Technologies Peoples’ Friendship University of Russia (RUDN University) 6 Miklukho-Maklaya str., Moscow, 117198, Russian Federation Email: demidova-av@rudn.ru, salpagarov_si@pfur.ru, pankratov_as@pfur.ru The relevance of this research is dictated by the fact that for video transmission modern networks have very high requirements for both building and maintaining a network infrastruc- ture, and analyzing issues of uninterrupted delivery of content. The video stream is the basic type of streaming data in peer-to-peer networks. To improve the quality of streaming data services, various schemes for organizing the structure of a superimposed peer-to-peer network are used. Probabilistic statements of the problem that determine the quality of construction of a peer-to-peer network is known. For example, the probability of universal transmission, in which unpopular channels, along with popular channels, are also available for viewing by network users with a certain probability. In our work, a discrete two-criteria formulation of this problem for estimating data trans- mission quality is considered. Three finite sets are determined. The set of internet users, for example, viewers of internet television channels. The set of internet television channels and the set of streams into which streaming data can be distributed. Every internet user watches a channel and several streams are assigned to it for transmission. There are user-uploaded data streams into two types: a stream for own viewing corresponding to the television chan- nel it is viewing, and a stream (one or several) of another television channel, exclusively for distribution to other users. A relationship of the following kind is constructed: the user watches some channel and distributes the streams for other channels. The theory of hyper- graphs makes it possible to show in the systemic unity the ordered types of relations such as the edge of hypergraph. Each edge is assigned two indicators - weights, which mean such indi- cators of quality of service as coefficient loss of data packets and playback delay. Each edge constrains three vertices. Vertices of edge - users, channels and streams accordingly. The re- sult of this assignment of flows to users should be to improve the level of performance of the broadcasting system, in particular, to reduce both the packet data rate loss and the playback delay. The mathematical model is described in the language of the theory of hypergraphs in a two criteria formulation. Two criteria have the type MINMAX, which allow simultaneously to take into account the efficiency indicators loss of data packets and playback delay. Key words and phrases: combinations on hypergraphs, peer-to-peer networks, distri- bution of streaming data flows, pocket loss, delay, multicriteria optimization. Copyright © 2018 for the individual papers by the papers’ authors. Copying permitted for private and academic purposes. This volume is published and copyrighted by its editors. In: K. E. Samouylov, L. A. Sevastianov, D. S. Kulyabov (eds.): Selected Papers of the 1st Workshop (Summer Session) in the framework of the Conference “Information and Telecommunication Technologies and Mathematical Modeling of High-Tech Systems”, Tampere, Finland, 20–23 August, 2018, published at http://ceur-ws.org Demidova Anastasia V., Salpagarov Soltan I., Pankratov Alexander S. 51 1. Introduction In many areas of human activity, P2P (peer-to-peer) networks are currently used. First of all, they are used for data exchange and transmission of streaming content. The total traffic generated by peer-to-peer networks is more than half of all Internet traffic. If we consider a streaming multimedia system, in particular, streaming video, then a whole series of large-scale P2P file sharing systems was introduced to transmit streaming video around the world [1]. There are many television channels are viewed simultaneously by a large number of users. A number of studies are devoted to the analysis of performance indicators of peer-to-peer video streaming networks. Various methods of research are used, such as the construction and analysis of analytical models, which use the apparatus of the theory of exponential queuing networks [2–4]. The are several peer-to-peer video streaming networks schemes which are widely used [2]. One of them is the mechanism of data exchange by the system of isolated channels P2P. Studies related to response time and waiting time are known [3, 4]. Along with the advantages, in the case of a small number of users the organization of data exchange in this scheme has some disadvantages, in particular, low quality of unpopular channels, loss of data packets and playback delay of viewed channels. These disadvantages are suggested to solve by the view-upload decoupling system [2]. The operation of the view-upload decoupling model is based on the separation of user-uploaded data streams into two types: a stream for own viewing corresponding to the television channel it is viewing, and a stream (one or several) of another television channel, exclusively for distribution to other users. As a rule, the latter are streams of television channels with low popularity, the forced distribution of which ensures the stability of the multi-channel system. Known the upload bandwidth is unequal distribution among different channels, which implies that some channels have satisfactory streaming qualities with surplus resources, while others suffer poor streaming qualities due to resource deficit [5, 6]. In [7, 8] shows letting the channels with surplus bandwidth help those with deficit bandwidth. The view-upload decoupling mechanism clearly separates what the user is downloading and viewing, thereby the stability of the multi-channel system and the ability to share resources between channels achieve. Each user is assigned to one or more channels, regardless of what the user is viewing. The user downloads and sends to other users all the data of the channels assigned to him. Thus, own distribution group for each channel is created. The view-upload decoupling scheme requires sending additional signaling information, because now the user have to download data not only to his group, but also to users outside of it, i.e. those users who want to view the channel assigned to it. The purpose of this study is to build a mathematical model for efficient organization of the distribution of data flows between users of P2P networks for the view-upload decoupling scheme. Using this model, it will be possible to find solutions to the problem in which both the packet data rate loss and the playback delay will be minimal. 2. Main section The meaningful statement of the problem is formulated as follows. Each user 𝑢𝑖 in a set of users receiving the service 𝑢𝑖 ∈ 𝑈 , where receives streams 𝑓 in a set of threads to which channels can be allocated 𝑓 ∈ 𝐹 of the channel 𝑐 in a set of channels available to the user 𝑐 ∈ 𝐶 from users 𝑢𝑗 ∈ 𝑈 , and 𝑢𝑖 ∩ 𝑢𝑗 = ∅. The result of this distribution of channel flows between users should be an increase in the level of performance of the broadcasting system, in particular, the quality of service of unpopular channels should not be much worse than the quality of service of channels that are more popular in which both the packet data rate loss and the playback delay will be minimal. A hypergraph 𝐺 = (𝑉, 𝐸) is a pair of sets (𝑉, 𝐸). Where 𝑉 is represented by a finite non-empty set, and 𝐸 is a family of subsets consisting of the set 𝑉 . 𝑉 = {𝑣} is the set of vertices of the hypergraph, and 𝐸 = {𝑒} is the set of its edges [9]. Pair of vertices 𝑣1 and 𝑣2 are adjacent if they belong to one edge 𝑒, 𝑣1 ∈ 𝑒, 𝑣2 ∈ 𝑒. The number of vertices 52 ITTMM-WSS—2018 in an edge is called the degree of this edge. If the degree of each edge is equal to 𝑙, then such a hypergraph is called 𝑙-homogeneous. If two edges have common vertices, they are called adjacent. A combination in the graph 𝐺 is a subset of the set of edges 𝐸 in which each pair of edges is non-adjacent. A hypergraph 𝐺 = (𝑉, 𝐸) is said to be 𝑙-partite if the set of its vertices 𝑉 is divided into parts (subsets) 𝑉𝑠 , 𝑠 = 1, 𝑙 so that two conditions are satisfied: every pair of vertices of one part is not adjacent; for every edge 𝑒 ∈ 𝐸 every pair of vertices 𝑣1 , 𝑣2 ∈ 𝑒 belongs to different parts [10]. If every edge 𝑒 ∈ 𝐸 is incident to one vertex from each parts 𝑉𝑠 , 𝑠 = 1, 𝑙, such a hypergraph 𝐺 = (𝑉1 , 𝑉2 , . . . , 𝑉𝑙 , 𝐸) is called complete 𝑙-partite hypergraph. If to each edge 𝑒 ∈ 𝐸 of a hypergraph 𝐺 a sequence of numbers 𝑤𝑣 (𝑒) > 0, 𝑣 = 1, 2, . . . , 𝑚 is associated, then it is called 𝑚-weighted. A hypergraph is called 𝑙-weighted if each of its edges is 𝑙-weighted [11, 12]. The mathematical model considered in this paper is based on a 3-partite 3-homogeneous hypergraph 𝐺 = (𝑉, 𝐸) = (𝑉1 , 𝑉2 , 𝑉3 , 𝐸), which is constructed as follows. Vertexes of the first partite 𝑣 ∈ 𝑉1 , uniquely correspond to the elements of a set of users 𝑈 . Each vertex 𝑣 ∈ 𝑉1 corresponding to the user 𝑢 ∈ 𝑈 . Each vertex of the second partite 𝑣 ∈ 𝑉2 uniquely corresponds to some element from the set of threads 𝐹 . Vertexes of the third partite 𝑣 ∈ 𝑉3 uniquely correspond to the elements of the set of channels 𝐶. To construct a set of edges 𝐸 = 𝑒 all possible triples of vertexes consider (𝑣1 , 𝑣2 , 𝑣3 ) so that 𝑣1 ∈ 𝑉1 , 𝑣2 ∈ 𝑉2 , 𝑣3 ∈ 𝑉3 . Any such triple is called acceptable, if the user 𝑣1 has an opportunity to stream data thread 𝑣2 of the channel 𝑣3 . The set of all edges 𝐸 = 𝑒 is defined as the set of all acceptable triples 𝑒 = (𝑣1 , 𝑣2 , 𝑣3 ), 𝑣𝑖 = 𝑉𝑖 , 𝑖 = (1, 3). In the problem under consideration for a hypergraph 𝐺 = (𝑉1 , 𝑉2 , 𝑉3 , 𝐸) the following conditions are fulfilled. In each edge 𝑒 = (𝑣1 , 𝑣2 , 𝑣3 ) ∈ 𝐸 a pair of vertexes 𝑣1 , 𝑣3 , which are called terminal vertexes for the edge, is allocated. Vertexes 𝑣 ∈ 𝑉2 are internal, and the set 𝑉2 is consisted of nonempty pairwise disjoint sets 𝑉2 (𝑣3 ), 𝑣3 ∈ 𝑉3 , and each element 𝑣 ∈ 𝑉2 (𝑣3 ) uniquely corresponds to some thread 𝑓 ∈ 𝐹 . Terminal vertexes 𝑣3 ∈ 𝑉3𝑍 are hanging vertexes (power 1); For each vertex 𝑣 from 𝑉1 the number 𝑚(𝑣) is indicated. The number 𝑚(𝑣) is a parameter of the following ∑︀ condition: A star with center at the vertex 𝑣 ∈ 𝑉1 has a power 𝑟(𝑣) = 𝑚(𝑣) and 𝑣∈𝑉1 𝑚(𝑣) = |𝑉3 |. Let us set 𝑋 = 𝑋(𝐺) = 𝑥 as the acceptable solutions set of the problem of covering the hypergraph 𝐺 by pairwise disjoint edges. Each edge 𝑒 ∈ 𝐸 of the hypergraph 𝐺 = (𝑉1 , 𝑉2 , 𝑉3 , 𝐸) has two weights 𝑤1 (𝑒), 𝑤2 (𝑒), where 𝑤1 (𝑒) = 𝑓1 (𝑣1 , 𝑣2 , 𝑣3 ) is loss of data packets when a user 𝑣1 ∈ 𝑉1 is watching of the channel 𝑣3 ∈ 𝑉3 , for the transmission of which the stream 𝑣2 ∈ 𝑉2 was used, 𝑤2 (𝑒) = 𝑓2 (𝑣1 , 𝑣2 , 𝑣3 ) the delay in the same case of the edge 𝑒 ∈ 𝐸. The quality of the acceptable solutions of this problem 𝑥 ∈ 𝑋 is estimated using the vector objective function 𝐹 (𝑥) = (𝐹1 (𝑥), 𝐹2 (𝑥)), (1) with type MINMAX 𝐹𝑖 (𝑥) = max 𝑤𝑖 (𝑒) → min, 𝑖 = 1, 2, (2) where 𝐹1 (𝑥) is the expected level of loss of data packets in the given solution 𝑥; 𝐹2 (𝑥) is change the delay in the given solution 𝑥. As an example, the following situation was considered. There are four channels 𝐶 = (𝑐1 , 𝑐2 , 𝑐3 , 𝑐4 ) in the system. As a result of the preliminary analysis of the channels, threads 𝐹 = (𝑓1 , 𝑓2 , 𝑓3 , 𝑓4 ) are separated between users. The system will have four users 𝑈 = {𝑢1 , 𝑢2 , 𝑢3 , 𝑢4 }. Let us describe the process of constructing a hypergraph 𝐺 = {𝑉1 , 𝑉2 , 𝑉3 , 𝐸} (see Fig. 1). Partits of the hypergraph are as follows 𝑉1 = {𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 }, 𝑉1 = {𝑣5 , 𝑣6 , 𝑣7 , 𝑣8 } and 𝑉3 = {𝑣9 , 𝑣10 , 𝑣11 , 𝑣12 } . Partite 𝑉2 is put in a one-to-one correspondence to the set 𝐹 . We construct the set of edges and are weights 𝑤1 (𝑒), 𝑤2 (𝑒). These sets are represented in the Tab. 1. Demidova Anastasia V., Salpagarov Soltan I., Pankratov Alexander S. 53 Figure 1. Hypergraph 𝐺 = {𝑉1 , 𝑉2 , 𝑉3 , 𝐸} Table 1 The acceptable solutions set Alternatives 𝑒 𝑤1 (𝑒) 𝑤2 (𝑒) {𝑣1 , 𝑣5 , 𝑣9 } 0, 336 0, 126 {𝑣1 , 𝑣6 , 𝑣9 } 0, 298 0, 112 {𝑣1 , 𝑣5 , 𝑣10 } 0, 305 0, 114 {𝑣2 , 𝑣6 , 𝑣9 } 0, 294 0, 11 {𝑣2 , 𝑣5 , 𝑣10 } 0, 3 0, 112 {𝑣2 , 𝑣6 , 𝑣10 } 0, 25 0, 094 {𝑣3 , 𝑣7 , 𝑣11 } 0, 15 0, 056 {𝑣3 , 𝑣8 , 𝑣11 } 0, 1 0, 037 {𝑣3 , 𝑣7 , 𝑣12 } 0, 195 0, 073 {𝑣4 , 𝑣8 , 𝑣11 } 0, 11 0, 041 {𝑣4 , 𝑣7 , 𝑣12 } 0, 18 0, 068 {𝑣4 , 𝑣8 , 𝑣12 } 0, 14 0, 052 The set of solutions 𝑥 and are criteria 𝐹1 (𝑒), 𝐹2 (𝑒) presented in the Tab. 2. Let us represent all the acceptable solutions set elements 𝑋 = 𝑥 of the problem Tab.2. Mathematical modeling of real problems often leads to multi-criteria statements, for which the concept of ”optimal solution” is absent. In conditions of multicriteria, it becomes necessary to search for a set of alternatives instead of the optimum [13]. Among various productions of vector problems in the article [14] let us consider a multicriterial problem in which the quality of admissible solutions 𝑥 ∈ 𝑋 is estimated by the vector objective function (1) with criteria of the types (2). 54 ITTMM-WSS—2018 Table 2 The set of solutions 𝑥 and criteria 𝐹1 (𝑥) and 𝐹2 (𝑥) Solutions 𝑥 𝐹1 (𝑥) 𝐹2 (𝑥) 𝑥1 0.358 0.245 𝑥2 0.358 0.245 𝑥3 0.358 0.245 𝑥4 0.307 0.249 𝑥5 0.307 0.249 𝑥6 0.307 0.249 𝑥7 0.358 0.247 𝑥8 0.358 0.247 𝑥9 0.358 0.247 Vector objective function (1)–(2) determines Pareto set in the acceptable solutions set 𝑋. Pareto set consists of Pareto optima 𝑥 ̃︀ [15]. In the case if the same vector objective function in value the solutions 𝑥′ , 𝑥′′ ∈ 𝑋 are considered as equivalent, from the Pareto set 𝑋 the full set of alternatives 𝑋 0 is accolated [16, 17]. Subset 𝑋 0 ⊆ 𝑋 ̃︀ is called the full set of alternatives, if it has the minimum power ̃︀ where 𝐹 (𝑋 * ) = {𝐹 (𝑥) : 𝑥 ∈ 𝑋 * }∀𝑋 * ⊆ 𝑋, so full set of |𝑋 0 | and 𝐹 (𝑋 0 ) = 𝐹 (𝑋), alternatives 𝑋 is the maximum system of vector-incomparable Pareto optima 𝑋, 0 ̃︀ 𝑋 0 ⊆ ̃︀ For our example 𝑋 0 = {𝑥1 , 𝑥4 }. The most expedient solution is selected from the 𝑋. 𝑋 0 using the procedures of the theory of choice and decision making [18]. 3. Conclusions One of the problems with streaming video in real time is to provide an acceptable quality of viewing for broadcasting under the conditions of intensive loading of channels between users. As the result of the work, a multi-criteria hypergraph model was constructed, which solved the problem of efficient distribution of data threads between users of P2P net-works for the view-upload decoupling scheme. This model allows us to find solutions to the problem of loss of data packets and delay in playback. For this case the solution of the problem of optimizing the process of distribution of flows and minimization loss of data packets and playback delays in peer-to-peer video streaming networks using concepts and objects of thetheory of hypergraphs is described. The application of this theory in combination withthe elements of the theory of multicriteria optimization makes it possible to take into account in the systemic unity a complex organization of internal interrelations of the elements of the problems under consideration. Examples of successful application of this approach can serve a number of problems solved by the authors and their colleagues invarious subject areas [19]. Analysis of the effect of network load from sources on the characteristics of the network makes it possible to select the parameters of network nodes, such as the bandwidth of channels and the speed of transmission of streams. It is known that the network works effectively when each of its resources is significantly loaded. On the one hand, we must strive to improve the quality of traffic, on the other, we must try to maximize the load of all network resources in order to improve the quality indicators. In the following studies, the authors plan to take a closer look at these network parameters. Demidova Anastasia V., Salpagarov Soltan I., Pankratov Alexander S. 55 Acknowledgments The publication has been prepared with the support of the "RUDN University Program 5-100" References 1. PPLive. URL: http://www.pptv.com/ 2. D. Wu, Y. Liu, K. Ross. Queuing Network Models for Multi-Channel P2P Live Streaming Systems, IEEE INFOCOM (2009) 73–81. 3. E. S. Sopin, A. V. Gorbunova, Y. V. Gaidamaka, E. R. Zaripova, Analysis of Cumu- lative Distribution Function of the Response Time in Cloud Computing Systems with Dynamic Scaling, Automatic Control and Computer Sciences, 52 (2018) 60–66. doi:10.3103/S0146411618010066 4. Y. Gaidamaka, E. Zaripova, Comparison of polling disciplines when analyzing waiting time for signaling message processing at SIP-server, Communications in Computer and Information Science, 564 (2015) 358–372. doi:10.1007/978331925861430 5. X. Hei, C. Liang, J. Liang, Y. Liu, and K. W. Ross, A measurement study of a large-scale P2P IPTV system, IEEE Trans. Multimedia 9 (8) (2007) 1672–1687. 6. X. Hei, Y. Liu, and K. Ross, Inferring network-wide quality in P2P Live streaming systems, IEEE J. Sel. Areas Commun. 25 (9) (2007) 1640–1654. 7. M. Zhang, Q. Zhang, and S. Yang, Understanding the power of pull-based streaming protocol: Can we do better? IEEE J. Sel. Areas Commun. 25 (9) (2007) 1678–1694. 8. R. Kumar, Y. Liu, and K. Ross, Stochastic fluid theory for P2P streaming systems, in Proc. IEEE INFOCOM, Anchorage, AK, May 2007, pp. 919–927. 9. C. Berge, Graphs and Hypergraphs, North-Holland, 1973 528 p. 10. C. Berge, Hypergraphs: combinatorics of finite sets. North-Holland, 1989 267 p. 11. K. Thulasiraman and M. Swamy, Graphs: Theory and Algorithms, John Wiley & Sons, New York, 1992 480 p. 12. A. Bretto, Hypergraph Theory, Mathematical Engineering, Springer, Heidelberg, 2013, 136 p. doi:10.1007/978-3-319-00080-0 13. S. Chung, H. Hamacher, F. Maffioli and K. Murty, Note on combinatorial optimiza- tion with max-linear objective functions, Discrete Applied Mathematics 42 (2–3) (1993) 139–145. doi:10.1016/0166-218X(93)90043-N 14. D. Luc, Theory of vector optimization, volume 319 of Lecture Notes in Economics and Mathematical Systems, Springer Verlag, Berlin (1989) pp.173. doi:10.1007/978- 3-642-50280-4 15. A. Warburton, Quasiconcave vector maximization: Connectedness of the sets of Pareto-optimal and weak Pareto-optimal alternatives, Journal of Optimization Theory and Applications, 40 (4) (1983) 537–557. doi:10.1007/BF00933970 16. Y. Sawaragi, H. Nakayama and T. Tanino, Theory of Multiobjective Optimization. Academic Press, Orlando, FL., 1985, 311 p. 17. V. A. Emelichev, V. A. Perepelica, Complexity of discrete multicriterial problems, Discrete Mathematics and Applications 4 (2) (1994) 89–117. doi:10.1515/dma.1994. 4.2.89 18. C. H. Papadimitriou and K. Steglitz, Combinatorial optimization: Algorithms and Complexity, Prentice Hall, New York, 1982, 496 p. 19. S. I. Salpagarov, Yu. D. Isaev, An optimization model of distribution of P2P-TV data streams on hypergraphs, CEUR Workshop Proceedings 2064 (2017) 130–135.