Search

CN-121984882-A - Edge micro-service deployment method based on key service identification and risk constraint

CN121984882ACN 121984882 ACN121984882 ACN 121984882ACN-121984882-A

Abstract

The application belongs to the technical field of micro-service deployment, and provides an edge micro-service deployment method based on key service identification and risk constraint, which comprises the following steps: firstly intelligently identifying and tracing to form a key service chain, generating a backup and disjoint path library for the key service chain, secondly evaluating path risks, introducing opportunistic constraints based on condition on risk value to limit tail overload risks of shared backup bandwidth, then constructing a two-stage optimization model, firstly optimizing the key chain risks, secondly optimizing the whole risks, finally solving a mixed integer planning model through a column generation algorithm, and outputting a joint scheme of primary and backup instance deployment, path selection and bandwidth configuration. The application precisely identifies the low-frequency high-risk key service chain, and controls the tail overload risk of the shared backup by using the opportunity constraint of the dangerous value, thereby obviously improving the overall utilization efficiency of the edge resources while ensuring the reliability of the key service.

Inventors

  • HU SHIHONG
  • YANG HAORAN
  • QU ZHIHAO
  • YE BAOLIU

Assignees

  • 河海大学

Dates

Publication Date
20260505
Application Date
20260114

Claims (10)

  1. 1. An edge micro-service deployment method based on key service identification and risk constraint is characterized by comprising the following steps: s1, constructing a service dependence directed acyclic graph of a target application, evaluating each micro service in the directed acyclic graph according to a preset service criticality index, and transmitting a key label to an upstream service along a dependence directed edge to form a key service chain set needing to be preferentially ensured; S2, based on the key service chain set, under the condition that deployment constraint rules, node CPU capacity constraint and link bandwidth capacity constraint are met, candidate deployment nodes of key micro service active and standby examples are determined to form an active and standby example endpoint pairing set; S3, carrying out time delay and reliability evaluation on each main and standby path pair in the main and standby path pair candidate library, estimating path time delays of the main path and the standby path based on an end-to-end time delay model, calculating a time-limited service success rate of the corresponding main and standby path pair under a time delay constraint condition by combining a node reliability model related to node loads and a link reliability model related to link connection duration, and defining a risk measure of the main and standby path pair based on the time-limited service success rate; S4, establishing a shared backup bandwidth pool on each link of a physical network based on the bandwidth requirement of the backup path in the main-backup path pair candidate library and the risk measurement of the main-backup path pair, designing the shared backup bandwidth coefficient of each link as a self-adaptive function of the link load, introducing opportunity constraint based on the condition on risk value, carrying out linear modeling and limitation on the tail risk of the backup bandwidth occupation exceeding the upper limit of the shared backup pool, and ensuring that the bandwidth overload amount does not exceed a given threshold value under a preset confidence level to form a risk constraint condition of the shared backup bandwidth; s5, on the basis of the risk constraint of the shared backup bandwidth, setting up a two-stage deployment optimization model by taking deployment selection of a main instance and a backup instance of a key micro service, selection of a main and backup path pair and a shared backup bandwidth coefficient as decision variables, wherein the first stage takes the sum of main and backup path pair risk metrics of each key service chain in a minimum key service chain set as a target; S6, uniformly expressing the two-stage deployment optimization model as a mixed integer programming main problem comprising node CPU capacity constraint, link main path bandwidth capacity constraint, shared backup bandwidth pool capacity constraint, main and backup path interior point disjoint constraint, end-to-end delay constraint and opportunity constraint based on condition risk value, constructing a corresponding path pricing sub-problem, generating a new main and backup path opposite list by adopting an interior point disjoint double-path search algorithm on a physical network topology after the main problem opposite variable weighting is introduced, and carrying out iterative solution between the main problem and the path pricing sub-problem by a list generation algorithm until a preset convergence condition is met, and outputting a deployment scheme of a key micro service main instance and a backup instance, a main and backup path selection scheme and a shared backup bandwidth configuration scheme.
  2. 2. The method according to claim 1, wherein the service criticality index SCI in step S1 is obtained by means of weighted summation: ; Wherein the method comprises the steps of An Quanying loudness representing microservice m, Is a tight time delay, Is the availability SLO, To call the frequency, Weight for failure penalty 0, When service criticality index Service m is marked as a critical micro-service, And sorting the SCI values of all the micro services in the actual scene according to descending order, and taking the quantile value corresponding to the preset proportion as a sorting threshold value for the service criticality sorting threshold value.
  3. 3. The method according to claim 2, wherein the deployment constraint rule in step S2 specifically comprises: Constraint C 1 that the key micro-service main instance is only allowed to be deployed on the edge node set N edge , constraint C 2 that the key micro-service main instance configures at least one backup instance, and the main instance and the backup instance are not co-located and are in different fault domains; constraint C 5 endpoint pairing and consistency constraints, specifically: constraint C 51 endpoint pairing uniqueness, record the candidate endpoint pairing set in step S2 as Representing all path pairs between the node u and the node v, and recording decision variables as Representing the dependence of u→v for each microservice, pairing sets at all candidate endpoints Allowing selection of only a unique set of endpoint pairs I.e. corresponding decision variables =1: ; Constraint C 52 -path and endpoint consistency-record Representing a set of candidate path pairs Representing a path pair selected between node u and node v, once the endpoint pair is selected for the candidate endpoint in step S2 I.e. decision variables =1, Then the set of candidate path pairs corresponding to that endpoint pair must and only be obtained from A path pair r, i.e., the selection state of the path must be consistent with the endpoint pairing variables: ; ; Node CPU capacity constraint C 3 in step S2: ; Wherein, the As a binary decision variable, representing whether the primary and backup instance b of the micro service m is placed on the node n, and taking a value of 1 if and only if the instance b of the micro service m is deployed on the node n, and taking a value of 0 if not; for the required CPU, the constraint formulation is for any physical node in the edge network The sum of the computing resources consumed by all the micro service instances it carries must not exceed the upper limit of the physical CPU capacity of the node itself ; The link bandwidth capacity constraint C4 in the step S2: ; Wherein, the Representing the maximum transmission bandwidth capacity of the physical link e, f representing one service data flow in the network, i.e. the corresponding micro-service A dependent transmission request; a binary routing decision variable, which takes a value of 1 if and only if the transmission path of the data stream f passes through the link e, and 0 if not; Representing the bandwidth requirements of the data stream f; representing the set of data flows that all may pass through link e, the constraint formulation for any physical link in the edge network The sum of the bandwidths occupied by all the service data streams transmitted over the link must not exceed the upper physical bandwidth limit of the link 。
  4. 4. A method according to claim 3, wherein the active-standby path in step S2 is required to guarantee that all intermediate forwarding nodes except the start point and the end point on the path do not intersect with the candidate pool: ; Wherein, the For a set of active-standby path pairs Path pair Wherein p represents a main path, q represents a backup path; And (3) with Representing the set of internal nodes for path p and path q, respectively, the formulation shows that the primary path and the backup path do not go through any identical intermediate nodes in the physical topology.
  5. 5. The method according to claim 4, wherein the end-to-end delay model in step S3 is an end-to-end delay of path p The method is specifically represented as follows: ; Wherein, the Queuing delay for propagation and forwarding delay The method is obtained by adopting piecewise linear convex upper bound approximation, and specifically comprises the following steps: Selecting k arrival rate breakpoints And its corresponding queuing delay function value Introducing convex combination coefficients For queuing delay Setting constraint C 6 : ; and the end-to-end delay of path p To meet corresponding service dependencies Is limited by the upper delay limit: ; Wherein, the Relying on for service Is a delay upper bound of (2).
  6. 6. The method according to claim 5, wherein the calculating the time-limited service success rate of the corresponding active-standby path pair under the time-delay constraint condition in the step S3, and defining the risk measure of the active-standby path pair based on the time-limited service success rate, specifically includes: The node reliability modeling is: ; Wherein, therein The load is node n; The basic fault coefficient is related to the hardware constitution of the node; for controlling the degree of steepness of the decrease in reliability with load; Indicating that node n is at the current load level Instantaneous reliability under; link reliability modeling is: ; Wherein, the Indicating the average failure arrival rate of the link, For the duration of the link e connection, Indicating that link e has a duration of continuous connection of Probability of no interruption during the period; For the main path p, it is time-delay constrained The success rate is as follows: ; Similarly, backup path q is constrained in time delay The success rate is as follows: ; wherein the former item Maintaining the probability of link-through for the link during transmission of data, the latter term The probability that the path still works normally under the load of the intermediate node is given; ensuring that only paths meeting the end-to-end delay requirement are considered valid paths; for the main and standby path pairs The probability of successfully providing service consists of two parts of successful main path or failed main path but successfully switched to backup path, and the two cases are connected in parallel to obtain the integral time-limited service success rate as follows: ; wherein, record For primary and standby parallel connection limit a time service success rate; the probability of failure of the main path is the precondition for triggering the backup mechanism; the timeliness probability of the backup switching, namely the probability that switching operation is completed in the remaining time window and service timeout is not caused; For the probability of shared resource availability, as the backup bandwidth adopts a sharing mechanism, when a plurality of concurrent faults occur in the network, the reserved bandwidth can be preempted, and the parameter represents the probability that when the backup needs to be started, the link actually has idle bandwidth available for use; based on the time-limited service success rate, to convert the reliability maximization problem into a linear programming problem which is easy to solve, carrying out negative logarithmic transformation on the success rate, and defining path pairs Risk measures of (a) are: ; wherein, record Representing the risk cost of the path pair r, which is non-negative in value, and converting the maximized reliability product into the sum of minimized risk values through logarithmic transformation.
  7. 7. The method according to claim 6, wherein the step S4 specifically comprises: Establishing a shared backup bandwidth pool on a physical link e, and setting the upper limit of the shared backup bandwidth pool as Wherein For the total bandwidth of link e, The self-adaptive sharing coefficient is set according to the link load state; for backup concurrency triggering scenario s=1, 2..s, defining the overload of scenario S downlink e as backup occupancy Deterministic bandwidth occupancy for primary path and normal traffic is The overload is defined as follows: ; Wherein, the Deterministic bandwidth occupancy for the main path and normal traffic, Is the sum of the bandwidth requirements of all triggered backup paths on the link under scenario s; Applying a tail risk constraint based on a conditional risk value to the shared backup bandwidth pool, the tail risk constraint C 7 comprising: C 7-1 opportunity constraint that limiting backup concurrency trigger causes overload event, i.e. overload, of physical link Not exceeding a preset overload probability threshold ; C 7-2 Tail overload constraint at preset confidence level Down, introducing auxiliary variables of link e And (3) with For overload amount The conditions of (2) impose the following linear constraints on risk value: ; Wherein, the , , The auxiliary variables are linearized for the conditional risk value.
  8. 8. The method according to claim 7, wherein the two-stage deployment optimization model in step S5 has two-stage optimization objectives, specifically: the first stage of optimization objective is to minimize the sum of the main and standby path pair risk metrics of each key service chain in the key service chain set, specifically expressed as: ; Wherein, the A set of key microservice dependent edges identified in step S1; representing a minimum accumulated risk of the calculated set of key service chains; the second stage of optimization target is to minimize the sum of the main and standby path pair risk metrics of all service chains of the system, and the sum is specifically expressed as: At the position of Under constraint, minimize: ; where k is a slack coefficient representing the final deployment risk of allowing critical services Theory compared with the first stage There is a controlled float.
  9. 9. The method according to claim 8, wherein the mixed integer programming master problem in step S6 is specifically expressed as: ; Where E represents the set of all microservices dependencies of the whole system.
  10. 10. The method according to claim 9, wherein the iterative process of the column generation algorithm in step S6 is specifically as follows: ; Wherein, the , , , The link primary instance capacity constraint pair price, the backup instance capacity constraint pair price, the node capacity constraint pair price and the unique dependence pair price, Incremental node resource requirements caused by selecting a path r at n; Based on , , The objective of the path pricing sub-problem is to find two paths with disjoint inner points for a given source-destination node pair on the dual weighted graph to form a candidate path pair r, and to simplify the cost of the path pair Negative; in each iteration, the current main problem is solved firstly, then the dual price obtained by solving the main problem is utilized to solve the path pricing sub-problem, if the simplifying cost is found And (3) adding the new path pair as a new column into a candidate column set of the main problem, and starting a new iteration, wherein the iteration process is continuously performed until the path pair with the reduced cost cannot be found or a preset iteration upper limit is reached, and a final joint deployment scheme is obtained.

Description

Edge micro-service deployment method based on key service identification and risk constraint Technical Field The application belongs to the technical field of micro-service deployment, and particularly relates to an edge micro-service deployment method based on key service identification and risk constraint. Background In the edge computing environment, the micro-service deployment needs to meet the requirements of low time delay, high reliability and efficient resource utilization. The existing method generally performs instance placement and route optimization based on service call frequency, time delay urgency or simple reliability index, and commonly adopts a shared backup mechanism to reduce resource reservation. However, the current method cannot effectively identify low-frequency high-risk critical services, and the shared backup mechanism lacks systematic constraint on tail risks in extreme concurrency scenes, so that the problems of insufficient guarantee of critical services and difficulty in considering the utilization rate and reliability of backup resources are caused. Disclosure of Invention The embodiment of the application provides an edge micro-service deployment method based on key service identification and risk constraint, which can solve the problems that the low-frequency high-risk key service cannot be effectively identified in the current method, and the shared backup mechanism lacks systematic constraint on the tail risk in an extreme concurrency scene, so that the key service is insufficient in guarantee, and the utilization rate and reliability of backup resources are difficult to consider. The embodiment of the application provides a method for deploying edge micro-services based on key service identification and risk constraint, which comprises the following steps of S1, constructing a service dependence directed acyclic graph of target application, evaluating each micro-service in the directed acyclic graph according to a preset service criticality index, transmitting key labels to upstream services along the dependence directed edge to form a key service chain set needing to be preferentially ensured, S2, determining candidate deployment nodes of key micro-service main-standby examples to form a main-standby example endpoint pairing set under the condition of meeting deployment constraint rules and node CPU capacity constraint and link bandwidth capacity constraint based on the key service chain set, searching and generating at least one group of main-standby path pairs in a physical network topology aiming at each main-standby example endpoint pairing, setting main-standby path and standby path to meet internal point disjoint constraint on intermediate nodes except a starting point and a terminal point to form a main-standby path pair candidate library, S3, The method comprises the steps of evaluating the time delay and reliability of each main and standby path pair in a candidate library of the main and standby path pairs, estimating the path time delay of the main and standby paths based on an end-to-end time delay model, combining a node reliability model related to node load and a link reliability model related to link connection time length, calculating a time-limited service success rate of the corresponding main and standby path pair under a time delay constraint condition, defining a risk measure of the main and standby path pairs based on the time-limited service success rate, S4, establishing a shared backup bandwidth pool on each link of a physical network based on the bandwidth requirement of the backup path and the risk measure of the main and standby path pairs in the candidate library of the main and standby path pairs, designing the shared backup bandwidth coefficient of each link as a self-adaptive function of the link load, introducing an opportunity constraint based on the condition in the risk value, linearizing and limiting the tail risk of the backup bandwidth occupation exceeding the upper limit of the shared backup pool, ensuring that the bandwidth overload exceeds a given threshold under a preset confidence level, forming a risk constraint condition of the shared backup bandwidth, S5, On the basis of the risk constraint of the shared backup bandwidth, a two-stage deployment optimization model is constructed by taking deployment selection of key micro service main instances and backup instances, selection of main and backup path pairs and shared backup bandwidth coefficients as decision variables, wherein the first stage takes the sum of main and backup path pair risk metrics of each key service chain in a minimized key service chain set as a target, the second stage takes the sum of main and backup path pair risk metrics of all service chains of a minimized system as a target, and S6, the two-stage deployment optimization model is uniformly expressed to contain node CPU capacity constraint, link main path bandwidth capacity constraint, shared back