CN109981334A - A kind of live streaming nerve of a covering Cost Optimization Approach with deferred constraint - Google Patents

Abstract

The invention discloses a method for optimizing the cost of a live broadcast overlay network with delay constraints. Aiming at the problem that the current overlay network optimization method fails to consider the scheduling delay of server nodes, which makes it difficult to apply to the actual production environment, this method incorporates the propagation delay of the link and the scheduling delay of the node into the constraints for cost optimization. The method steps specifically include parameter initialization, complete graph generation, joint modeling of multi-stream models, variable relaxation and concave programming, optimal solution rounding, and bandwidth fine-tuning. The method can greatly reduce the bandwidth cost of the overlay network system within the specified delay constraint, and has good applicability.

Description

A Cost Optimization Method for Live Overlay Network with Delay Constraints

technical field

The invention belongs to the field of computer networks, and relates to a cost optimization method for a live coverage network with delay constraints, and more specifically, to a coverage method that incorporates link bandwidth prices, link propagation delays and node scheduling delays into constraints Network construction method.

Background technique

At present, live video is transmitted and distributed through the overlay network system. The overlay network consists of node servers and source node servers in different regions. For convenience of description below, the node server is called a node, and the source node server is called a source node. The source node distributes live video stream data to nodes in different regions, and then nodes in different regions distribute the data to user terminals in corresponding regions. Compared with users directly pulling live video stream data from the source node, data distribution through the overlay network can effectively reduce the distribution pressure on the source node and the transmission delay of video stream data.

The cost of deploying an overlay network system mainly comes from the link bandwidth cost between different nodes. When the link bandwidth is larger, the data transmission delay between nodes is lower, but the bandwidth cost of the system is correspondingly higher. How to reduce the bandwidth cost as much as possible within a certain delay constraint is a hot issue in the industry. In recent years, many researchers have done a lot of research on the problem of resource allocation optimization of overlay networks, and have made great progress in some specific application fields. However, in order to simplify the problem, most of the work only considers the propagation delay of the transmission link and ignores the scheduling delay of the node in the data transmission delay. This simplification goes against the real-life situation, making the algorithm less executable and unable to be truly applied to the actual production environment.

To sum up, it can be seen that the current cost optimization algorithm of overlay network still has certain shortcomings and room for improvement.

SUMMARY OF THE INVENTION

In order to solve the above problems, the present invention proposes a cost optimization method for live coverage network with delay constraints. The method innovatively takes both the propagation delay of the link and the scheduling delay of the node into consideration for the construction of the overlay network.

In the cost optimization method provided by the present invention, the overlay network parameters are firstly initialized; then the assignment maximization process is performed on the infeasible path, and the overlay network topology graph becomes a directed complete graph at this time; and then the transmission delay and the scheduling delay are comprehensively considered. , and jointly model the overlay network; when the model is constructed, the model variables are the flow variables and bandwidth values of the link. Among them, the flow variable is an integer variable of 0-1, and the bandwidth value is a non-negative real number variable; the model is solved using the variable relaxation method and the sequential quadratic programming method, and the obtained flow variable solution and bandwidth numerical solution are both fractional solutions, At this time, the solution is not yet feasible; in order to make the solution feasible, the fractional solution of the flow variable needs to be rounded; finally, due to the rounding of the flow variable solution, the original bandwidth numerical solution does not necessarily meet the constraints, and the bandwidth needs to be rounded. The numerical solution is iteratively processed until the delay constraint is satisfied.

Description of drawings

FIG. 1 is a flow chart of a method for optimizing the cost of a live coverage network with delay constraints according to the present invention.

Detailed ways

In order to make the objectives, technical solutions and advantages of the present invention clearer, the present invention will be further described in detail below with reference to the accompanying drawings and embodiments. It should be understood that the specific embodiments described herein are only used to explain the present invention, but not to limit the present invention.

Specific steps are as follows:

A. The parameters are initialized and the topology map is generated.

Specifically, the initialized overlay network node set is V, and the edge set is E. The links in E are all feasible links between nodes. The parameters of each node i are: the set of live channels N _i subscribed by the node, the scheduling delay of the node The parameters of each feasible link <i,j> are: propagation delay The link code rate τ _ij , the link bandwidth b _ij and the cost function C _ij (b _ij ), C _ij (b _ij ) are concave functions. The set of live channels deployed on the overlay network is N. Each live channel n has a parameter: channel bit rate τ ⁽ⁿ⁾ . The maximum total delay constraint for the overlay network is D. The kth flow variable of the nth channel of the link <i,j> is The destination node is node k. The total flow variable of the nth channel of link <i,j> is

B. Complete graph generation, assigning the maximum cost and propagation delay to the parameters related to the infeasible path. The overlay network topology graph becomes a directed complete graph.

Specifically, for the infeasible link <i,j>, set its propagation delay to infinity, that is Set its cost function as an infinite constant, ie C _ij (b _ij )=+∞, and then add it to the edge set E in step A. At this time, E is a directed complete graph, that is, E=V×V.

C. Joint modeling of multi-stream models, which comprehensively considers scheduling delay and propagation delay.

Specifically, the multi-stream constraints are first constructed according to the multi-stream model definition:

Among them, when node i is the source node, θ is 1; when i is the destination node, θ is -1; when i is another node, θ is 0. By constructing a multi-stream model, it can be guaranteed that the generated overlay network topology map is a tree-based multi-channel mesh map.

Calculate the current code rate t _ij of each link <i,j>, the current code rate of the link cannot exceed the bandwidth b _ij of the link. Therefore, we get the constraints:

Now we jointly model the propagation delay of the link and the scheduling delay of the node. Let the size of the video stream data transmission field be L, and the scheduling delay of node i is Then the calculation formula of the scheduling delay of node i is as follows:

where Ch(i) is the child node of node i, and P ⁽ⁿ⁾ is the set of nodes subscribed to by channel n.

Let the propagation delay of link <i,j> be Then the total delay of the kth flow is the sum of the propagation delays of the links it traverses plus the sum of the scheduling delays of the nodes it traverses, and we get the following constraints:

Finally, we define that the link bandwidth cost is obtained by the cost function C _ij (b _ij ) in step A. The function C _ij (b _ij ) is a concave function about the bandwidth b _ij , and the marginal cost decreases as the bandwidth increases. The cost of the overlay network is the sum of the bandwidth costs of all links, namely:

The mathematical model composed of the above constraints and cost function is an integer model, and we will solve the cost optimization according to this model next.

D. Variable relaxation and concave programming to optimize and solve the model.

Specifically, in the model constructed by step C, and All are integers, which are not easy to solve. We relax the above two variables and constrain the remove, that is becomes a real number in the range [0,1]. Therefore, the integer programming model obtained in step C is converted into a continuous concave programming model. We solve this model using a sequential quadratic programming method. be denoted as (flow variable), (total flow variable), b _ij * (bandwidth).

E. The optimal solution is rounded.

Specifically, the solution obtained by step D and Possibly a fraction rather than an integer. Therefore, it is necessary to use the "rounding" operation to convert the above two variables into integers. For the k-th flow path of the n-th live channel, we start from the destination node j of the flow path and round up the flow variable. Node j has multiple input flow variables, we select the largest input flow variable and set it to 1, and other input flow variables are set to 0. Set the other end node i of the link represented by the maximum flow variable as the parent node of node j, that is where P ^kn (j) is the parent node of the kth stream of node j with respect to the nth channel. Then we use the equivalent operation to process the input stream variable of node i. Iterates continuously until the source node is processed. At this time all are integer solutions. Finally, we use the formula come right Round up.

F. Bandwidth fine-tuning, adjust the bandwidth of the link that does not meet the constraints to make it meet the constraints. Specifically, the "rounding" operation in step E may cause the link bandwidth value to no longer satisfy the constraint. Therefore the link bandwidth needs to be increased to meet the constraints. For the kth flow that does not meet the delay constraint, iteratively increases all link bandwidth values in the flow path at a rate of 10% until the flow delay meets the constraint.

The present invention aims to propose a method for optimizing the cost of live coverage network with constraints, and its features and advantages are:

The topology of the overlay network is constructed by the multi-flow model, and then the propagation delay of the transmission link and the scheduling delay of the transmission node are incorporated into the constraints. The model is optimally solved using variable relaxation and concave programming methods under the condition that the delay constraints are satisfied. The solution value is then rounded and scaled by fine-tuning operations. Through this method, the obtained solution can be guaranteed to be a feasible solution, and a low-cost live coverage network scheme can be provided under a certain total delay constraint.

The method for optimizing the cost of a live overlay network with delay constraints provided by the embodiments of the present invention has been described above in detail. In this paper, specific examples are used to illustrate the principles and implementations of the present invention. The descriptions of the above embodiments are only for help. Understand the method of the present invention and its core idea; at the same time, for those skilled in the art, according to the idea of the present invention, there will be changes in the specific implementation and application scope. In summary, the content of this specification does not It should be understood as a limitation of the present invention.

Claims (4)

1. a method for optimizing the cost of live broadcast overlay network with delay constraint, is characterized in that comprising the following steps: A. The parameters are initialized to generate the basic topology structure of the overlay network; B. Complete graph generation, processing infeasible paths to make the overlay network a completely directed graph; C. Joint modeling of multi-stream models, modeling the live coverage network based on the multi-stream model, and the constructed coverage network is an integer programming model; D. Variable relaxation and concave programming, relax the variables, and then use the sequential quadratic programming method to solve; E. The optimal solution is rounded, and the solution obtained in step D is rounded; F. Bandwidth fine-tuning, iteratively increasing the bandwidth solution to meet delay constraints. 2. a kind of live coverage network cost optimization method with delay constraint as claimed in claim 1, is characterized in that, in described step B, processing the infeasible path is specifically to set the cost and delay of this link as Infinity, and then access the original topological graph, so that the topological structure of the overlay network is a directed complete graph. 3. a kind of live overlay network cost optimization method with delay constraint as claimed in claim 1, is characterized in that, in described step C, in the overlay network is carried out modeling process, has merged the propagation delay and transmission of transmission link The scheduling delay of the node, the joint constraint modeling of the above propagation delay and scheduling delay. 4. The method for optimizing the cost of a live coverage network with delay constraint according to claim 1, wherein in the step F, iteratively increasing the bandwidth solution is specifically: to the flow path bandwidth that does not satisfy the delay constraint , increase by 10% each time, then check whether the delay constraint is satisfied, if not, continue to increase until the constraint is satisfied.