Patent ID: 11936758
Assignee: NANJING UNIVERSITY OF AERONAUTICS AND ASTRONAUTICS
Field: Digital communication (Electrical engineering)
Classification: CPC H  G  Y | IPC G  H

Claim 0:
1. An efficient parallelization and deployment method of a multi-objective service function chain based on a CPU+DPU platform, comprising the following steps:
(1) constructing a heterogeneous computing architecture for solving a multi-objective deployment problem, wherein the heterogeneous computing architecture comprises an orchestrator responsible for management and coordination, and a server based on a CPU+DPU structure;
(2) converting serial SFCs into parallel SFCs by an SFC parallel strategy according to the independence among VNFs, and accordingly solving an SFC parallel problem;
wherein an objective function of the SFC parallel problem is to minimize additional resource consumption and delay caused by copying and merging of the data packet:

min(αC+βΔd), wherein α and β respectively represent weight coefficients of the additional resource consumption and delay,, C
  =
  
   
    
     ∑
      
    
    
     μ
     =
     1
    
    
     
      ❘
      "\[LeftBracketingBar]"
     
     R
     
      ❘
      "\[RightBracketingBar]"
     
    
   
   ⁢
   
    
     ∑
      
    
    
     ∀
     
      B
      ∈
      
       r
       μ
      
     
    
   
   ⁢
   6
   ⁢
   4
   ×
   
    
     
      Φ
      B
     
     -
     1
    
    U, represents the additional resource consumption caused by the copying and merging of the data packet,, Δ
   ⁢
   d
  
  =
  
   
    
     ∑
      
    
    
     μ
     =
     1
    
    
     
      ❘
      "\[LeftBracketingBar]"
     
     R
     
      ❘
      "\[RightBracketingBar]"
     
    
   
   ⁢
   3
   ⁢
   0
   ×
   
    
     v
     μ
    
    
     1
     ⁢
     
      0
      9, represents the additional delay caused by the copying and merging of the data packet, R represents one group of SFC requests in a network, rμ represents a μth SFC request, B is one group of parallel branches, ΦB represents the parallelism degree of the B, U represents the size of the data packet, and Vμ is the data quantity of the μth SFC in the requests R;
an objective of the SFC parallel strategy is to identify a VNF in the chain according to a dependency relationship among the VNFs to find all chains executable in parallel;
wherein the SFC parallel strategy comprises: dividing the VNFs into two types of monitors and shapers, wherein the monitors are responsible for monitoring a flow rate without any modification, the shapers are used for processing and modifying the flow rate, and a specific algorithm process is as follows:
21) initializing a branch chain set B, a main chain S and a monitor set M;
22) traversing rμ: in a case that fiμ∈rμ is monitor, firstly initializing a branch chain b∈B, then adding fiμ into b and M; and in a case that fiμ∈rμ is shaper, adding fiμ into a main chain S, at this time, searching monitor on which fiμ depends on in M, for each such monitor, for example, k∈M, having a branch chain that takes k as an end point at present, then pointing k to fiμ so as to extend the branch chain to take fiμ as an end point, and removing k from M;
23) Invoking a path search algorithm to find all path sets PATH executable in parallel; and
24) Returning to the branch chain set B, the main chain S and the path set PATH;

(3) for a situation that a plurality of SFCs arrive at the same time at a certain moment, adopting a VNF topological order algorithm, deploying the VNFs according to a topological order obtained by the algorithm, and reducing the delay in connection with the sharing and scaling characteristics of the VNFs,
wherein the VNF topological order algorithm is used for constructing a VNF topological order for the plurality of SFCs and deploying the VNFs according to the ordering to reduce the delay;
a specific process of the VNF topological order algorithm is as follows:
31) Initializing f as a source node;
32) Traversing a request set R arriving at the same time, invoking the SFC parallel strategy to obtain the branch chain set B, the main chain S and the path set PATH, evaluating a path with a maximum delay in all the paths according to the path set PATH, and adding the path into a set C;
33) traversing C, and creating a directed weighted graph graph=(F, ω), F being a set of VNFs, and ω being a weight between edges;
34) Invoking a minimum feedback arc set algorithm to solve a minimum feedback arc set of the graph, and verifying whether the solved topological order meets the dependency relationship of the VNFs among different chains, returning to the topological order in a case that the solved topological order meets the dependency relationship of the VNFs among different chains, otherwise, returning to False;

(4) adopting a DPU processing strategy for a service request with a high real-time requirement, wherein the DPU processing strategy is used for processing computing tasks comprising network protocol processing, data encryption and decryption and data compression to save a CPU computing resource and reduce the delay;
in a case that there is a high-priority request in the request set that arrives at a certain moment, determining whether there is a VNF responsible for the data processing task in the request, using DPU for rapid processing in a case that there is a VNF responsible for the data processing task in the request, and using CPU for processing in a case that there is no VNF responsible for the data processing task in the request;
(5) proposing an SFC heterogeneous deployment algorithm based on deep reinforcement learning, wherein the heterogeneous algorithm is capable of completing deployment of the SFC respectively according to the number and situation of the requests arriving at different moments,
according to the number and situation of the requests arriving at different moments, the SFC heterogeneous deployment algorithm based on deep reinforcement learning adopts different strategies respectively for processing, comprising: performing a parallel strategy, a VNF topological order strategy and a DPU processing strategy to achieve the deployment of the SFC, and
a specific operation of deploying the SFC in step (5) is as follows:
51) Deleting a timeout request by a system first, dividing the arrived requests R by a priority judgment apparatus according to real-time performance, dividing the request with high real-time performance into a high-priority R_high, and dividing the requests with low real-time performance into a low-priority R_low;
52) initializing a time slot τ;
53) According to the numbers of R_high and R_low, determining which strategy to be adopted to process the SFC;
54) Constructing and training a neural network model, taking a status of a current physical network and a characteristic of the request being processed as an input, and outputting a deployment strategy of each VNF through the computation of the neural network; and
55) Updating the network status.