CN-121984919-A - Multistage CDN flow scheduling method based on linear constraint

CN121984919ACN 121984919 ACN121984919 ACN 121984919ACN-121984919-A

Abstract

The invention relates to the technical field of computer networks and discloses a multi-stage CDN flow scheduling method based on linear constraint, which comprises the following steps of receiving a local DNS (Domain name System) resolved access request to form a scheduling instance to be optimized; the method comprises the steps of judging complexity of a scheduling instance, determining an applicable scheduling category, establishing a performance upper limit model related to server hardware resources, introducing functional linear constraint, carrying out fine setting on Big-M parameters related to the constraint, obtaining server cluster information, server information, quality constraint information and region hijacking information, carrying out joint solution on the performance upper limit model and the functional constraint, determining a target cache node IP address meeting all constraint conditions, feeding back to a local DNS, and completing response and scheduling on an access request. According to the invention, through the multistage scheduling framework and the refined Big-M parameter setting, the computing efficiency and the resource utilization precision of CDN scheduling in a complex network environment are improved.

Inventors

ZOU YIFEI
LI YIJUN
WU XINGZE
QI SENMAO
LIN GUANGZHENG
ZHU ZHIXIONG
YAO JIAYUE

Assignees

凌川峰(贵州)信息技术有限公司
山东大学

Dates

Publication Date: 20260505
Application Date: 20251229

Claims (10)

1. A multi-stage CDN flow scheduling method based on linear constraint is applied to a CDN center server and is characterized by comprising the following steps: step 1, receiving and converging an access request analyzed by a local DNS to form a scheduling instance to be optimized; step 2, complexity judgment is carried out on the scheduling instance, a multi-level scheduling framework is adopted based on the judgment result, and then an applicable scheduling category is determined for each access request, wherein the scheduling category defines a range of the cache nodes which can be allocated by the access request; Step 3, based on the scheduling category of each access request and the corresponding cache node range determined in the step 2, establishing a performance upper limit model related to server hardware resources, wherein the model simultaneously considers the CPU and IO resource consumption characteristics of different service coverage types; Step 4, further introducing functional linear constraint on the basis of the performance upper limit model established in the step 3, and carrying out fine setting on Big-M parameters related to constraint in the modeling process, wherein the functional linear constraint comprises at least one of multi-operator regional constraint for avoiding network hijacking, cold coverage association constraint for controlling back source cost, fixed flow load constraint for avoiding service jitter and trans-provincial flow limit constraint for meeting operator requirements; And 5, acquiring server cluster information, server information, quality constraint information and region hijacking information, carrying out joint solution on the performance upper limit model and the functional constraint established in the step 3 and the step 4, determining the IP address of the target cache node meeting all constraint conditions, and feeding back the IP address to a local DNS to finish response and scheduling of the access request.
2. The multi-stage CDN traffic scheduling method based on linear constraints of claim 1, wherein the specific method of step 2 is as follows: firstly, judging the complexity of a scheduling instance based on a pre-trained classification model; When the classification result is 'simple', directly adopting a linear programming model to carry out flow scheduling; when the classification result is 'complex', a hierarchical scheduling mechanism is started, the whole problem is disassembled into a plurality of sub-problems, and the sub-problems are optimized step by step to reduce the solving complexity and obtain a feasible solution in a limited time.
3. The multi-level CDN traffic scheduling method based on linear constraints of claim 2 wherein the hierarchical scheduling mechanism comprises: dividing the overall scheduling problem into a plurality of sub-problems according to the traffic scale or constraint complexity; scheduling local or small-scale traffic preferentially in the first layer of sub-problems to obtain an initial feasible solution; Gradually expanding the scheduling range in the subsequent hierarchy, and incorporating unallocated traffic or residual constraint into optimization to form a step-by-step solving process; And solving in each layer by adopting a heuristic or linear programming method, and taking the solution of the upper layer as the input of the lower layer so as to ensure the feasibility and optimality of the global solution.
4. The multi-level CDN traffic scheduling method based on linear constraints of claim 1, wherein in step 3, the upper performance limit model includes: Definition Cover At the server The actual flow rate is as follows: ; Wherein, the Is a Cover Offloading to a server Is the first of (2) A bit binary share; CPU constraints: ; IO constraint: ; Wherein, the 、 Respectively representing CPU and IO consumption coefficients corresponding to the Cover type; 、 Respectively represent cache nodes Upper limit of CPU and IO capacities, N is the set of Cover, and M is the set of servers.
5. The multi-level CDN traffic scheduling method based on linear constraints of claim 1, wherein in step4, the multi-operator regional constraints are as follows: for each Cover Setting ternary decision variables Respectively represents the use of an intra-provincial server, the use of an extra-provincial server and the access of other operator servers, and satisfies uniqueness: ; To arbitrarily allocate share variables There is , wherein, Represent Cover Offloading to a server Is the first of (2) A bit binary share; representing the maximum value of the Big-M parameter; ; if Cover In hijacking area, then the minimum traffic granularity: ; Otherwise, there are: ; Wherein, the Respectively the available province inside, province outside, other operators and all server sets, Represent Cover In the first place Traffic requests at various times.
6. The multi-level CDN traffic scheduling method based on linear constraints of claim 1, wherein in step 4, the cold coverage association constraints are as follows: Introducing intermediate variables Represent Cover Whether or not at the server Unloading is carried out, and the following conditions are satisfied: ; ; Wherein, the Indicating whether the Cover n applies for the server m A portion flow rate; representing the maximum value of the Big-M parameter; for the cold coverage association constraint, it is expressed as for the cold coverage set Imposing an associated server upper bound: ; Wherein, the The set of all the cold-overlays, Is a Cover Upper limit of server mounted.
7. The multi-stage CDN traffic scheduling method based on linear constraint of claim 1, wherein in step 4, the fixed traffic load constraint is as follows: Definition Cover For server cluster Is occupied by the flow: ; Wherein, the Is a Cover Offloading to a server Is the first of (2) A bit binary share; is the set of servers contained by server cluster o; For low-scalability traffic aggregation LCS and allowed server cluster sets thereof Upper limit of the ratio is applied: ; Wherein, the For a server cluster Is used for the running-up line of the car, For the Cover n in the server cluster Is a duty cycle threshold of (c).
8. The multi-stage CDN traffic scheduling method based on linear constraint of claim 1, wherein in step 4, cross-provincial traffic restriction constraint is implemented with an objective function term: defining intra-provincial traffic duty cycle terms within a server cluster: ; Wherein, the Representing a collection of servers in the same area as the Cover, Is a Cover Offloading to a server Is the first of (2) A bit binary share; is the set of servers contained by server cluster o; setting an objective function: ; Wherein, the An intra-provincial traffic proportion threshold specified for the operator, In order to limit the weight across the provincial traffic, , Is an indicator variable of whether the server is running high, Represent Cover For server cluster Is occupied by the flow of the gas; for a complete set of target variables that the linear model needs to solve for, the variables Is that Represents the traffic granularity of service n to server m, variable Representation of Representing the hijacking policy of the cover n, variables Representation of Represents the number of divisions of the server m by the cover n, and the variable u represents Representing the occupancy of the server m by the cover n.
9. The multi-stage CDN traffic scheduling method based on linear constraint as recited in claim 8, wherein in step 4, the method for performing fine setting on Big-M parameters related to the constraint is as follows: for multi-operator regional constraints, the following are satisfied: ; For variables And Is satisfied: ; ; Wherein the variables are Is a variable Indicating variable of (1), if Not 0, then the variables Nor 0, otherwise 0, for indicating Cover Whether or not to occupy the server ; A preset constant determined based on the upper limit of the number of loadable IPs of the cache nodes, wherein M1 is larger than 1; For variables Sum variable Is satisfied: ; ; For variables And variable(s) Is satisfied: ; ; Wherein, the The flow of the rule line, the flow of the high-speed line and the minimum value for the server, Representing the traffic request of the Cover n, Representing the set of Cover, b representing the number of bits of the binary share, Represent Cover A collection of server clusters that can be scheduled.
10. A computer readable medium, characterized in that it stores a computer program, which, when read and run by a processor, implements the method according to any of claims 1-9.

Description

Multistage CDN flow scheduling method based on linear constraint Technical Field The invention relates to the technical field of computer networks, in particular to a multistage CDN flow scheduling method based on linear constraint. Background With the rapid development of mobile applications, online video, cloud games, and other highly concurrent services, CDNs (content delivery networks) have become a key infrastructure for guaranteeing network quality of service. The core challenge is how to realize the reduction of the flow cost and the improvement of the scheduling efficiency while ensuring the user experience. In the prior art, researchers have attempted to solve CDN traffic scheduling problems through linear programming modeling. For example, patent "a method and apparatus for CDN traffic scheduling based on linear programming with optimal cost" (CN 119030926 a) proposes to characterize DNS uniformity constraint by using binary decomposition technique, and to ensure uniform traffic distribution among IP addresses by decomposing traffic variable and IP quantity variable and establishing linear constraint. The scheme makes progress in solving the nonlinear problem caused by the random return of the IP address of the DNS system, and improves the resolvability and the calculation efficiency of the model. However, when the existing scheme faces a large-scale complex network environment, it is often difficult to consider dynamic consumption of hardware resources under different service characteristics and diversified industry supervision constraints, so that solving efficiency of a scheduling model under a complex service scene is low, resource utilization precision is insufficient, scheduling strategies lack flexibility, and global optimization of cost and service quality is difficult to achieve. . Therefore, a new CDN traffic optimization method is needed, on the basis of inheriting the existing DNS uniformity modeling results, more comprehensive functional linear constraint is introduced, and the Cover characteristics and server CPU/IO resource modeling are combined, and meanwhile, an intelligent classification and hierarchical scheduling framework is assisted, so that the solution efficiency, cost optimization and service quality guarantee are both considered. Disclosure of Invention In order to solve the technical problems, the invention provides a multi-stage CDN flow scheduling method based on linear constraint, so as to achieve the purposes of realizing efficient scheduling, reducing cost and improving service quality while meeting complex constraint. In order to achieve the above purpose, the technical scheme of the invention is as follows: a multi-stage CDN flow scheduling method based on linear constraint is applied to a CDN center server and comprises the following steps: step 1, receiving and converging an access request analyzed by a local DNS to form a scheduling instance to be optimized; step 2, complexity judgment is carried out on the scheduling instance, a multi-level scheduling framework is adopted based on the judgment result, and then an applicable scheduling category is determined for each access request, wherein the scheduling category defines a range of the cache nodes which can be allocated by the access request; Step 3, based on the scheduling category of each access request and the corresponding cache node range determined in the step 2, establishing a performance upper limit model related to server hardware resources, wherein the model simultaneously considers the CPU and IO resource consumption characteristics of different service coverage types; Step 4, further introducing functional linear constraint on the basis of the performance upper limit model established in the step 3, and carrying out fine setting on Big-M parameters related to constraint in the modeling process, wherein the functional linear constraint comprises at least one of multi-operator regional constraint for avoiding network hijacking, cold coverage association constraint for controlling back source cost, fixed flow load constraint for avoiding service jitter and trans-provincial flow limit constraint for meeting operator requirements; And 5, acquiring server cluster information, server information, quality constraint information and region hijacking information, carrying out joint solution on the performance upper limit model and the functional constraint established in the step 3 and the step 4, determining the IP address of the target cache node meeting all constraint conditions, and feeding back the IP address to a local DNS to finish response and scheduling of the access request. In the above scheme, the specific method of step 2 is as follows: firstly, judging the complexity of a scheduling instance based on a pre-trained classification model; When the classification result is 'simple', directly adopting a linear programming model to carry out flow scheduling; when the classification result is 'complex