# DDS: A Delay-Based Differentiated Service Virtual Network Embedding Algorithm
## 2 Related Work  
In order to solve the NP-hard problem of VNE, scholars have proposed many heuristic-based algorithms. According to the relationship between node mapping and link mapping, these can be divided into one-stage embedding algorithms and two-stage embedding algorithms. The one-stage algorithm embeds virtual nodes and virtual links at the same time. [PERSON]. [17] proposed a subgraph isomorphism detection algorithm which splits the VNR into subgraphs and embeds nodes and links at the same time, but this will lead to a lot of backtracking. [PERSON] et al. [18] proposed a classic heuristic two-stage algorithm that has been used so far. Nodes are sorted according to the CPU and the total adjacent link bandwidth, and nodes in the virtual network are greedily mapped to the substrate nodes. [PERSON] introduces the concept of path splitting. In the next stage, links are mapped by the k-shortest path algorithm [27] or the multi-community flow (MCF) algorithm [28]. This algorithm had a profound impact on the research of virtual network mapping algorithms. Ref. [29] effectively reduces the virtual network request rejection rate through path splitting. Ref. [19], considering node degree, and [20], considering time window, are variants of [18]. Inspired by the Google PageRank algorithm, [PERSON]. [21] applies a Markov random walk model to rank nodes according to resources and topological attributes. The link mapping method is similar to [18]. However, these algorithms only consider the node capacity and link bandwidth and do not consider the complexity of network resources in the actual network, so they cannot be extended to practical network applications. [PERSON] et al. [11; 12] used MIP for mathematical modeling in the VNE problem for the first time, and relaxed integer constraints to obtain linear programming. They proposed two node-embedding algorithms: deterministic rounding and random rounding. When the solution of node embedding is feasible, the MCF or shortest path algorithm is used to embed virtual links. [PERSON] [13] proposed an algorithm to solve VNE using ILP with the goal of minimizing resource consumption and load balancing, adding node distance and link propagation delay constraints, but it is not described in detail in the paper. As far as we know, pure ILP has high computational complexity. [PERSON] [14] proposed an ILP algorithm based on candidate assistance, which reduces the computational complexity of linear programming by adding location and delay constraints to limit the range of solutions, enabling linear programming to be applied in medium-scaled networks. [PERSON]. [22] proposed a three-dimensional virtual network embedding model based on computing, storage, and bandwidth resources. Compared with the previous VNE model that only considers node computing resources and link bandwidth resources, this model is closer to the real network attributes, such as SDN flow table resources and ICN node content cache, all need to occupy node storage resources. In addition, considering some services with QoS requirements, such as telemedicine, online game, Internet of Vehicles, industrial Internet remote control, and other delay-sensitive services, link delay should also be considered as a network attribute in the model. [PERSON]. [30] combined with the novel neural network of the graph convolution network, proposed a virtual network embedding algorithm based on deep reinforcement learning. Ref. [31] introduces simulated annealing into the particle swarm optimization algorithm to solve the VNE problem and proposes a particle initialization allocation strategy for the shortcomings of the particle swarm optimization algorithm in initializing particles' positions. Ref. [32] formulated the VNE problem as multi-objective integer linear programming and designed an algorithm based on an artificial immune system to solve this problem. Compared with exact solutions and heuristic solutions, meta-heuristic solutions are not the mainstream of VNE research [3].