NETWORK BURST LOAD EVACUATION METHOD FOR EDGE SERVERS

Abstract

The present invention discloses a network burst load evacuation method for edge servers, which takes a time and average penalty function of all tasks performed by the edge system as a minimum optimization goal. This method not only takes into account the fairness of all users in the system, but also ensures that the unloading tasks of all users in the system can be completed in a relatively shortest time, and a new quantitative measure is proposed for improving user QoS response. In the implementation process of the algorithm in the present invention, a particle swarm algorithm is used to solve an optimal target of the system, This algorithm has a fast execution speed and high efficiency, and is especially suitable for a scene of an edge computing network system, so that when a sudden load occurs, an edge computing network system can respond in a very short time and complete the evacuation of the load, which greatly improves the fault tolerance and stability of the edge network environment.

Claims

1. A network burst load evacuation method for edge servers, comprising the following steps: (1) detecting an edge server with overloaded network tasks in a target area, and for any overloaded edge server, determining a task set Ω that the server needs to evacuate; (2) enumerating all feasible load evacuation strategies, and for any load evacuation strategy, determining a task index of each edge server in the area after the strategy is adopted; (3) establishing an objective function L used to evaluate the implementation effect of each load evacuation strategy as follows; $\begin{array}{c}L=\max \left(a_1,a_2,.Math.,a_N\right)+\frac{{.Math.}_{i=1}^N{U}_i}{N}\\ a_i=t_{mig}^i+t_{\mathrm{wt}}^i+t_{exe}^i\\ s.t.{.Math.}_{p=1}^{N_j}{v}_{\mathrm{ram}}^p\le r_{\mathrm{ram}}^j\\ \text{}{.Math.}_{p=1}^{N_j}{v}_{\mathrm{storage}}^p\le r_{\mathrm{storage}}^j\end{array}$ wherein: N is the number of tasks in the task set Ω, a.sub.i is the time taken to complete the execution of an i-th task in the set Ω, U.sub.i=c(a.sub.i−t.sub.d), and c is a given penalty coefficient, t.sub.d.sup.i is a preset time limit for the completion of the i-th task in the set Ω, t.sub.mig.sup.i is the time consumed by the i-th task in the set Ω during a migration process, t.sub.wt.sup.i is the queuing time of the i-th task in the set Ω for waiting to be executed in a task queue thereof after migrating to a target server, t.sub.exe.sup.i is the time consumed by the execution of the i-th task in the set Ω after migrating to the target server, N.sub.j is the number of tasks received by an j-th edge server in the target area, r.sub.ram.sup.j is the amount of available memory resources of the j-th edge server in the target area, and v.sub.ram.sup.p is the amount of memory resources occupied by a p-th task in the evacuation tasks received by the j-th edge server in the target area, r.sub.storage.sup.j is the amount of available storage resources of the j-th edge server in the target area, and v.sub.storage.sup.p is the amount of storage resources occupied by the p-th task in the evacuation tasks received by the j-th edge server in the target area; (4) according to the above objective function L, using a hybrid particle swarm algorithm to optimize the solution to determine an optimal load evacuation strategy; the specific implementation process of the step (4) is as follows: first, generating a particle swarm according to all feasible load evacuation strategies, wherein the scale of the particle swarm is K, and K is the number of all feasible load evacuation strategies, each particle in the particle swarm corresponds to a set of load evacuation strategies; a k-th particle in the particle swarm can be expressed as (X.sub.k, L.sub.k), X.sub.k=(x.sub.1, x.sub.2, . . . , x.sub.M), L.sub.k is an objective function value of the load evacuation strategy corresponding to the k-th particle, x; is an evacuation task queue received by the j-th edge server in the target area, k is a natural number and 1≤k≤K; before a first round of iteration, the particle with a smallest objective function value in the current particle swarm is regarded as a global optimal particle (X.sub.g, L.sub.g) and a local optimal particle in the first round; then, performing multiple rounds of iterative operations, wherein for a t-th round of iteration, the specific operation process is as follows: (4.1) making each particle in the current particle swarm cross with the global optimal particle once, and for the k-th particle (X.sub.k, L.sub.k) in the particle swarm, making the particle swarm cross with the global optimal particle (X.sub.g, L.sub.g) to obtain a new particle (X.sub.k.sup.1, 1.sup.i.sub.k); (4.2) making the new particle obtained in the step (4.1) cross with the local optimal particle (X.sub.k.sup.t, C.sub.k.sup.t) in the t-th round once, and for the new particle (X.sub.k.sup.1, L.sub.k.sup.1), making the new particle cross with the local optimal particle (X.sub.k.sup.t, L.sub.k.sup.t) in the t-th round to obtain a new particle (X.sub.k.sup.2, L.sub.k.sup.2), and t is a natural number greater than 0; (4.3) performing multiple mutations on the new particle obtained in the step (4.2), and for the new particle (X.sub.k.sup.2, L.sub.k.sup.2), randomly selecting a mutation scheme from the three mutation schemes BY1˜BY3 and mutating the mutation scheme multiple times to obtain a new particle (X.sub.k.sup.3, L.sub.k.sup.3); (4.4) if it is judged that L.sub.k.sup.3−L.sub.k<e, replacing the k-th particle (X.sub.k, L.sub.k) in the current particle swarm with the new particle (X.sub.k.sup.3, L.sub.k.sup.3); if L.sub.k.sup.3<L.sub.k.sup.t, taking the new particle (X.sub.k.sup.3, L.sub.k.sup.3) as a t+1-th round local optimal particle (X.sub.k.sup.t+1, L.sub.k.sup.t+1), otherwise making the t-th round local optimal particle (X.sub.k.sup.t, L.sub.k.sup.t) as the t+1-th round local optimal particle (X.sub.k.sup.t+1, L.sub.k.sup.t+1); (4.5) updating the global optimal particle (X.sub.g, L.sub.g), that is, making the particle with the smallest objective function value in the current particle swarm as the global optimal particle (X.sub.g, L.sub.g), thus completing the current iteration; finally, after completing multiple rounds of iterations, outputting the global optimal particle (X.sub.g, L.sub.g) as the optimal load evacuation strategy.

2. The network burst load evacuation method according to claim 1, wherein, each load evacuation strategy comprises a decision matrix I and an execution order matrix O, and the size of each of the two matrices is N×M, and N is the number of tasks in the task set Ω, M is the number of the edge servers in the target area, the element value I.sub.ij of an i-th row and a j-th column in the decision matrix I is 0 or 1, and I.sub.ij=1 indicates that the i-th task in the set Ω is executed on the j-th edge server in the target area, otherwise I.sub.ij=0; the element value O.sub.ij of the i-th row and the j-th column in the execution order matrix O is a positive integer, and specific value thereof indicates a sequence number in the evacuation task queue received by the j-th edge server in the target area for the i-th task in the set Ω, wherein the smaller the sequence number is, the earlier it is executed, and if O.sub.ij=0, it means that the i-th task in the set Ω is not executed on the j-th edge server in the target area, both i and j are a natural number and 1≤i≤N, 1≤j≤M.

3. The network burst load evacuation method according to claim 1, wherein, the specific implementation mode that two particles are crossed is as follows: first randomly selecting a particle (X.sub.q, L.sub.q) from the two particles, X.sub.q=(x.sub.1, x.sub.2, . . . , x.sub.M), L.sub.q being an objective function value of the load evacuation strategy corresponding to the particle; for the particle (X.sub.q, L.sub.q), randomly selecting N/2 tasks from an evacuation task queue x.sub.1˜x.sub.M thereof, so that these tasks continue to be in an original evacuation task queue and the execution order remains unchanged; for the remaining N/2 tasks, adjusting the load evacuation policy corresponding to the particle (X.sub.q, L.sub.q), so that the evacuation task queues in the two particles and the execution orders in the queues of these tasks are consistent, thus obtaining new particles.

4. The network burst load evacuation method according to claim 1, wherein, the specific implementation mode of the variation scheme BY1 is as follows: for a certain particle (X.sub.q, L.sub.q), X.sub.q=(x.sub.1, x.sub.2, . . . , x.sub.M), L.sub.q is the objective function value of the load evacuation strategy corresponding to the particle, randomly selecting an evacuation task queue from evacuation task queue x.sub.1˜x.sub.M thereof, and then randomly selecting two tasks from the queue to exchange positions.

5. The network burst load evacuation method according to claim 1, wherein, the specific implementation mode of the variation scheme BY2 is as follows: for a certain particle (X.sub.q, L.sub.q), X.sub.q=(x.sub.1, x.sub.2, . . . , x.sub.M), L.sub.q is the objective function value of the load evacuation strategy corresponding to the particle, randomly selecting two evacuation task queues from evacuation task queue x.sub.1˜x.sub.M thereof, and then randomly selecting one task from each of the two queues to exchange positions.

6. The network burst load evacuation method according to claim 1, wherein, the specific implementation mode of the variation scheme BY3 is as follows: for a certain particle (X.sub.q, L.sub.q), X.sub.q=(x.sub.1, x.sub.2, . . . , x.sub.M), L.sub.q is the objective function value of the load evacuation strategy corresponding to the particle, randomly selecting two evacuation task queue A and B from evacuation task queue x.sub.1˜x.sub.M thereof, randomly selecting a task a from the queue A, and randomly selecting a task b from the queue B, and then deleting the task a from the queue A and inserting the task a into the next position of task b in the queue B.

7. The network burst load evacuation method according to claim 1, wherein, for new particles generated after crossover and mutation operations, it is necessary to ensure that the following constraints are met; ${.Math.}_{p=1}^{N_j}{v}_{\mathrm{ram}}^p\le r_{\mathrm{ram}}^j$ ${.Math.}_{p=1}^{N_j}{v}_{\mathrm{storage}}^p\le r_{\mathrm{storage}}^j.$

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0030] FIG. 1 is a schematic diagram of the architecture of a node load evacuation scheduling system for an edge computing network according to the present invention.

[0031] FIG. 2 is a schematic diagram of task migration for a particle crossover operation.

[0032] FIG. 3 is a schematic diagram of task migration for a particle mutation operation.

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0033] In order to describe the present invention more specifically, the technical solutions of the present invention will be described in detail below with reference to the accompanying drawings and specific embodiments.

[0034] The architecture of a node load evacuation scheduling system for an edge computing network of the present invention is shown in FIG. 1, which mainly comprises two parts: an edge server node and a central controller.

[0035] Edge server response nodes: a task buffer pool is used to cache all tasks transferred from other servers to this server, wherein a task migration module controls link switching between different servers during a task migration process in the entire network, and transfers a task passing through this server to a correct link, so as to realize the migration of tasks in the network; an edge server status detection module is used to then upload the resource status of each server to a central controller; an edge server request receiving module is used to respond to requests transmitted by a user, and transmit the request information to the central controller, and monitor in real-time the occurrence of no-load emergencies in the edge servers.

[0036] Network link status nodes: collecting the load of each link in the network in real time, detecting the transmission progress of load tasks in the network, and transmitting this information to a central control node in real time as a decision basis for a central control node.

[0037] Central decision control node: by utilizing a control module based on a hybrid particle algorithm, evacuating the load according to the status and link conditions of each edge server node in the network to make a scheduling strategy.

[0038] The present invention provides corresponding load evacuation strategies for some edge servers in which load emergencies occur in the edge network, and is a decision method for migrating the load flow of a single server to the server to which it is connected to perform load balancing. First, establishing a file for each task in the load burst, and preparing for decision-making of the basic data on the edge computing network. For the i-th task, it contains three dimensions of resource requirements, v.sub.cycle.sup.i, v.sub.ram.sup.i, v.sub.storage.sup.i respectively represent the number of CPU cycles required for the completion of each task, the ram resources and storage resources required for the task to execute on the edge server. Each edge server has three technical indicators: r.sub.freq.sup.j represents the CPU execution rate of a j-th edge server, in cycle/slot, r.sub.ram.sup.j represents the available ram resources of the j-th edge server, and r.sub.storage.sup.j represents the available storage resources of the j-th edge server.

[0039] For the task transmission link between each edge server, using L.sub.mm′ to represent the task transmission link that connects a m-th and m′-th edge servers. If L.sub.mm′=1, it represents that there is a link connection between these two servers, otherwise, L.sub.mm′=0 represents that there is no link between them. L.sub.j=[L.sub.j,1, L.sub.j,2, . . . , L.sub.j,|M|], L.sub.i,j, ∈{0,1} represents the link status between the j-th edge server and all M servers in the network, R.sub.j,j′ represents the number of tasks that can be transmitted in one time slot, and P.sub.j,j′ represents the maximum number of transmission tasks allowed by the link in the task time slot.

[0040] The load task execution time of the edge server is calculated in the following ways t.sub.exe.sup.i:

[00003]$t_{exe}^i=\frac{v_{cycle}^i}{r_{\mathrm{freq}}^j}$

wherein, each task of the burst load can be migrated to a different server for execution, and the total number of execution time slots of i tasks is obtained by dividing the number of CPU cycles v.sub.cycle.sup.i required to complete the execution of the i-th task in the burst tasks in the edge server network by the CPU processing speed r.sub.freq.sup.j of the j-th edge server where it is located.

[0041] During the execution of each task, the following constraints must be met. For each unit time slot, this task can only be executed on one edge server, and the task cannot be divided into smaller tasks in this system.

[0042] A burst of load may block on a burst-loaded edge server, and tasks are queued for the server's final response; while when a task is migrated to a server in the edge network, it is first placed in a task cache. After waiting for the tasks in the edge server to be executed, the tasks in the cache are uniformly loaded into the edge server for execution, so each task still spends part of its time waiting in the cache. For these two pieces of waiting time, the i-th task can express its waiting state by the following formula:

t.sub.wt.sup.i=t.sub.burst.sup.i+t.sub.cache.sup.i

wherein, t.sub.wt.sup.i comprises two parts: the delay t.sub.burst.sup.i generated by task i when a burst load occurs represents the time interval from the moment when the task i is generated on the blocked server until the moment when the task leaves the server, and the delay t.sub.cache.sup.i in the server's cache queue in the transfer process of task i represents the time interval from the moment when the task i is transferred to the transferred server's cache queue until the moment when the task is started to be executed by that server.

[0043] In the edge computing network, when a sudden load event occurs on an edge server, the edge computing network system has a central decision-making function, which can quickly schedule the available server resources in the entire network and evacuate the sudden load, that is, transferring to other edge servers for load balancing. In this scheduling strategy, the process of transferring tasks from one server to another is called task migration. The purpose of the task migration is to make the delay of the final return result of the task greatly reduced. The migration time consumed by task i in the network can be obtained by the following formula:

t.sub.mig.sup.i=v.sub.size.sup.i/l.sub.jj′

wherein, v.sub.size.sup.i represents the data size of the task i, l.sub.jj′ represents the task transmission rate (in bit/slot) between the overloaded server j and another edge server j′ in the edge network; only one task can be transmitted per transmission, and after the task is transmitted, the link is allowed to transmit the next task.

[0044] During the migration process, each task i needs to be performed between two edge servers that already have established a transmission link. When a task is migrated, it cannot be further divided into small tasks or transmitted over multiple links. The task migration process is always continuous and uninterrupted. Once a task is successfully transferred to an edge server, it immediately enters the task cache queue of the edge server, waits until the next step for execution; one edge server can only execute one task, and the tasks are executed in the order in which they are migrated to the edge server.

[0045] Aiming at the problem of sudden load evacuation and balancing in the edge computing network environment, the present invention adopts the load evacuation and balancing method for the edge server network of the hybrid particle swarm algorithm, and combines the task transmission path in the edge server link and the server into a particle swarm. The link arrangement and server execution in the evacuation strategy are selected as a single particle in the particle swarm.

[0046] First, according to the information obtained by the calculation, the objective function of evacuating the load of the edge server network is calculated:

[00004]$\begin{array}{c}\underset{I_{ij},S_{ij}}{\min }\left[\max \left(A\right)+1/N\underset{i\in N}{.Math.}{U}_i\right]\\ s.t.\underset{i\in Nj}{.Math.}{v}_{\mathrm{ram}}^i\le r_{\mathrm{ram}}^j\\ \underset{i\in Nj}{.Math.}{v}_{\mathrm{storage}}^i\le r_{\mathrm{storage}}^j\\ \mathrm{where}{t}_{mig}^i+t_{\mathrm{wt}}^i+t_{exe}^i=a_i\end{array}$

wherein, A={a.sub.1, a.sub.2, . . . , a.sub.n}, i∈N, a.sub.i is the time taken to complete the execution of the i-th task, N is the number of tasks that need to be evacuated in the overloaded server, N.sub.j represents a set of evacuation tasks received by the j-th server; I.sub.ij represents a decision with which the i-th task is executed on the j-th edge server, I.sub.ij=1 represents that the task i is executed on the edge server j, otherwise I.sub.ij=0; S.sub.ij represents the execution sequence number of the i-th task on the j-th edge server, S.sub.ij∈N.sup.+, wherein N.sup.+ is a positive integer, and the task i is not executed on the edge server j, then O.sub.ij=0; the value of U.sub.i is proportional to the difference between the completion time of executing the i-th task and the completion time limit of executing the task, defining U.sub.i=c(a.sub.i−t.sub.d.sup.i), c is a penalty parameter, t.sub.d.sup.i is a preset time limit for the completion of the task i; if the actual execution time a.sub.i of the task is greater than t.sub.d.sup.i, we consider that the execution time of the task has timed out; otherwise, the execution of the task i has been completed ahead of time; this functional function of U.sub.i calculates the quantified value of the degree of early completion or overtime completion of the task. In the process of multi-objective optimization, we hope that the mean of U.sub.i and total task evacuation time are as small as possible.

[0047] Initialization stage: generating an initial solution of the particle swarm, because each edge server has tasks to be executed, so assuming that the set of task indices on each edge server is tskvr.sub.m={1,2,3,4 . . . , N.sub.m}, wherein N.sub.m represents the last task index on the m-th server, an initial solution O.sub.0={tskvr.sub.1,tskvr.sub.2 . . . , tskvr.sub.M} of a particle swarm is composed of M tskvr.sub.m. Setting the number of iterations T and a threshold “e” for local solution update in an algorithm iteration process, which means that the solution obtained after cross-mutation deteriorates to a certain extent and this group of solutions are accepted.

[0048] The specific operation of the particle swarm algorithm is: firstly generating a set of feasible solutions, the number of which is D, and obtaining the optimal solution among the current feasible solutions. Its optimal solution and objective function value are (X.sub.g, C.sub.g), wherein X=(x.sub.1, x.sub.2, . . . , x.sub.n, . . . , x.sub.N) is this group of solutions and represents an ordered set of all task indices, and recording (X.sub.k, C.sub.k) of all particles, assuming that (X.sub.k.sup.t, C.sub.k.sup.t) is the optimal solution and objective function value in each round of iteration, initializing (X.sub.k.sup.1, C.sub.k.sup.1)=(X.sub.g, C.sub.g).

[0049] Iterating T times for the following process:

[0050] taking t=1

[0051] Operating for D times (k=1 to D):

[0052] First, performing a cross operation between X.sub.k and X.sub.g to obtain the solution and the objective function value (X.sub.k.sup.1, C.sub.k.sup.1);

[0053] Then, performing a cross operation between X.sub.k.sup.1 and X.sub.k.sup.t to obtain the solution and the objective function value (X.sub.k.sup.2, C.sub.k.sup.2);

[0054] Finally, for (X.sub.k.sup.2, C.sub.k.sup.2), a random selection of a mutation scheme is performed b times to obtain the solution and the objective function value (X.sub.k.sup.3, C.sub.k.sup.3).

[0055] If C.sub.k.sup.3−C.sub.k<e, then the solution of the current particle and the value of the objective function are updated (X.sub.k, C.sub.k)=(X.sub.k.sup.3, C.sub.k.sup.3), otherwise (X.sub.k, C.sub.k) is unchanged.

[0056] If C.sub.k.sup.3<C.sub.k.sup.t, then (X.sub.k.sup.t+1, C.sub.k.sup.t+1)=(X.sub.k.sup.3, C.sub.k.sup.3), otherwise (X.sub.k.sup.t+1, C.sub.k.sup.t+1)=(X.sub.k.sup.t, C.sub.k.sup.t).

[0057] t=t+1

[0058] Taking (X.sub.g, C.sub.g)=(argmin.sub.k∈D C.sub.k, C.sub.k)

[0059] The specific implementation method of the crossover operation is: setting the two sets of solutions as X.sub.1, X.sub.2, randomly selecting a set of solutions, assuming that the solutions are X.sub.1, if N is the total number of tasks, then randomly selecting

[00005]$.Math.\frac{N}{2}.Math.$

tasks in X.sub.1 and the execution order in the server where they are located remains unchanged, and the remaining

[00006]$N-.Math.\frac{N}{2}.Math.$

tasks correspond to the positions of the servers where the

[00007]$N-.Math.\frac{N}{2}.Math.$

tasks in the solution X.sub.2 are located, and the task positions in the X.sub.1 are transformed to obtain a new X.sub.1, which is defined as X.sub.0.

[0060] As shown in FIG. 2, the two groups of solutions are the black tasks in X.sub.1, X.sub.2 which belong to the tasks that require cross-operation, and the remaining gray tasks represent tasks that do not perform cross-operation.

[0061] If the order of task 1 in X.sub.2 is 3, then first transforming task 1 to the position of the order of 3 in server 2 in X.sub.1; the order of task 4 in server 1 in X.sub.2 is 2, then transforming task 4 in X.sub.1 to the position of the order of 2 in the server; the order of task 8 in server 3 in X.sub.2 is 4, then transforming task 8 in X.sub.1 to the position of the order of 4 in the server 3; remaining task 11 unchanged because the positions in the two sets of solutions are the same; the order of task 18 in server 3 in X.sub.2 is 6, then transforming task 18 in X.sub.1 to the position of the order of 6 in the server 3.

[0062] In the above crossover operations, the constraints must be satisfied:

[00008]$s.t.\underset{i\in \mathrm{Nj}}{.Math.}{v}_{\mathrm{ram}}^i\le r_{\mathrm{ram}}^j$$\underset{i\in \mathrm{Nj}}{.Math.}{v}_{\mathrm{storage}}^i\le r_{\mathrm{storage}}^j$

wherein, i represents the task index, j represents the edge server index; if during the crossover process, when the task obtained from the X.sub.2 is placed on the server corresponding to X.sub.1, if the above relational expression is not satisfied, then the task being exchanged in X.sub.1 will remain unchanged, that is, the server where the task is located remains unchanged, and the order of task in the server where the task is located remains unchanged, and then continuing to perform the crossover operation of subsequent tasks.

[0063] The specific implementation modes of the mutation operation are classified into three cases:

[0064] The first case is to randomly select a set of edge server task combinations tskvr.sub.k, randomly select two of the tasks, and exchange their positions. As shown in FIG. 3, the solid line exchanges positions between task 1 and task 2.

[0065] The second case is to randomly select a task combination tskvr.sub.k and tskvr.sub.k+1 of two different edge servers, and randomly select the two tasks in tskvr.sub.k and tskvr.sub.k+1 to exchange positions. As shown in FIG. 3, the dotted line exchanges positions of tasks 4 and 9 in tskvr.sub.1 and tskvr.sub.2.

[0066] The third case is to randomly select a task combination tskvr.sub.k and tskvr.sub.k+1 of two different edge servers, randomly select the two tasks in tskvr.sub.k and tskvr.sub.k+1 respectively, and insert the former task into the position of the latter task. As shown in FIG. 3, the solid line with circles removes task 5 in tskvr.sub.1 from the set tskvr.sub.i and then inserts it into a position after task 14 in tskvr.sub.3.

[0067] In any one of the above crossover operations, the constraints must be satisfied:

[00009]$s.t.\underset{i\in \mathrm{Nj}}{.Math.}{v}_{\mathrm{ram}}^i\le r_{\mathrm{ram}}^j$$\underset{i\in \mathrm{Nj}}{.Math.}{v}_{\mathrm{storage}}^i\le r_{\mathrm{storage}}^j$

wherein, i represents the task index, j represents the edge server index; if the above constraints are not satisfied after the mutation operation, then stopping the mutation operation, re-randomizing one of the three mutation operations, and implementing a new mutation operation until the constraints are met.

[0068] The above description of the embodiments is for the convenience of those of ordinary skill in the art to understand and apply the present invention. It will be apparent to those skilled in the art that various modifications to the above-described embodiments can be readily made, and the general principles described herein can be applied to other embodiments without inventive effort. Therefore, the present invention is not limited to the above-mentioned embodiments, and improvements and modifications made by those skilled in the art according to the disclosure of the present invention should all fall within the protection scope of the present invention.