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 infrastructure, 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 transmission quality is considered. Three nfiite 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 channel 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 hypergraphs 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 indicators of quality of service as coeficient loss of data packets and playback delay. Each edge constrains three vertices. Vertices of edge - users, channels and streams accordingly. The result 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 eficiency indicators loss of data packets and playback delay.
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
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 trafic generated by peer-to-peer networks is more than half of all Internet
trafic. 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 [
The are several peer-to-peer video streaming networks schemes which are widely
used [
Known the upload bandwidth is unequal distribution among diferent channels, which
implies that some channels have satisfactory streaming qualities with surplus resources,
while others sufer poor streaming qualities due to resource deficit [
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 eficient 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.
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 [
a sequence
= ( 1, 2, . . . , , ) is
of numbers ( ) > 0,
= 1, 2, . . . ,
is associated, then it is called -weighted. A
∈
hypergraph is called -weighted if each of its edges is -weighted [
The mathematical model considered in this paper is based on a 3-partite 3-homogeneous hypergraph the first partite
= (, vertex ∈ 1 corresponding to the user ∈ . Each vertex of the second partite ∈ 2 ∈ 1, uniquely correspond to the elements of a set of users . Each uniquely corresponds to some element from the set of threads . Vertexes of the third partite a set of edges to stream data thread 2 of the channel 3. The set of all edges 2 ∈ 2, 3 ∈ 3. Any such triple is called acceptable, if the user 1 has an opportunity = is defined as the ∈ 3 uniquely correspond to the elements of the set of channels . To construct = all possible triples of vertexes consider ( 1, 2, 3) so that 1 ∈ 1, ) = ( 1, 2, 3, ), which is constructed as follows. Vertexes of set of all acceptable triples = ( 1, 2, 3), = , = (1, 3).
In the problem under consideration for a hypergraph conditions are fulfilled. In each edge are called terminal vertexes for the edge, is allocated. Vertexes = ( 1, 2, 3) ∈ = ( 1, 2, 3, ) the following a pair of vertexes 1, 3, which ∈ 2 are internal, and element 3 ∈ 3 the set 2 is consisted of nonempty pairwise disjoint sets 2( 3), 3 ∈ 3, and each ∈ 2( 3) uniquely corresponds to some thread ∈ . Terminal vertexes 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
Let us set the hypergraph ∈ 1 has a power ( ) = ( ) and ∑︀ ( ) = | 3|. = ( ) = as the acceptable solutions set of the problem of covering 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 The quality of the acceptable solutions of this problem ∈ is estimated using the ∈ 1 ∈ of the edge
∈ . vector objective function with type MINMAX
( ) = ( 1( ), 2( )), ( ) = max ( ) → min, = 1, 2, (1) (2) is change the delay in the given solution . where 1( ) is the expected level of loss of data packets in the given solution ; 2( )
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} . of edges and are weights 1( ), 2( ). These sets are represented in the Tab. 1.
Partite 2 is put in a one-to-one correspondence to the set . We construct the set
The set of solutions and criteria 1( ) and 2( )
⊆ ̃︀ is called the full set of alternatives, if it has the minimum power
|
0| and ( 0) = ( ︀̃ ), where ( *) = { ( ) :
∈ *}∀ * ⊆ , so full set of
alternatives 0 is the maximum system of vector-incomparable Pareto optima ,̃︀
0 using the procedures of the theory of choice and decision making [
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 eficient 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 [
Analysis of the efect 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 efectively when each of its resources is significantly loaded. On the one hand, we must strive to improve the quality of trafic, 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.
The publication has been prepared with the support of the "RUDN University Program 5-100"