# DDS: A Delay-Based Differentiated Service Virtual Network Embedding Algorithm
## 1 Introduction  
With the rise of various new network services and applications, the demands of users for the network show a diversified trend. However, deploying new businesses under the traditional network architecture requires not only redeployment of hardware but also consensus among device providers, which is difficult to cope given the diverse, customized, and differentiated applications. The proposal of network virtualization is to overcome the impasse of the Internet [1]. As one of the important technologies for promoting current network innovation [2], network virtualization has been actively applied in many research testbeds and projects [3], such as CABO [4], 4 WARD [5], and G-Lab [6]. Through network virtualization, multiple isolated networks can be virtualized in the shared underlying network infrastructure. Each virtual network can customize the network structure or run different network protocols according to business requirements. Different users can use their network resources independently without interfering with each other, thereby improving the utilization of network resources, satisfying the diverse demands of users, and realizing an elastic network. In network virtualization, the Internet service providers (ISPs) in traditional networks are divided into infrastructure providers (InPs) and service providers (SPs). This decoupling method that separates resources and services is more flexible. InPs are responsible for providing underlying infrastructure and managing underlying network resources. SPs rent physical resources from InPs, build and operate virtual networks, and offer services through virtual networks. Embedding the requests of SPs onto underlying infrastructure depends on efficient embedding algorithms. The software defined network (SDN) [7] proposed by Professor [PERSON] of Stanford University in the United States realizes the separation of forwarding and control. The centralized control plane can flexibly program the network and easily obtain a global view, which provides a natural advantage for the realization of network virtualization. Facing the diversified and personalized network requirements, [PERSON] [8] proposed a full-dimensional defined polymorphic smart network architecture. In the polymorphic network environment, the resource requirements of diversified services are different. Specifically, in the substrate network, this is manifested as competition for the same resources between different networks--in other words, how to effectively allocate the substrate network resources to virtual network requests and satisfy the constraints of nodes and links at the same time. This problem is called virtual network embedding (VNE) and is one of the key problems of network virtualization. The definition of node constraint is that the resource requirements of the virtual node must not exceed the physical resources of the mapped entity node. The definition of link constraint is that the resource requirements of the virtual link must not exceed the physical resources of the mapped entity link. VNE aims to provide an optimal resource allocation scheme for each virtual network, which proves to be an NP-hard problem [9]. In the existing research, the solutions to VNE problems can be divided into three categories [10], namely exact solutions, heuristic solutions, and meta-heuristic solutions. The exact solution method is used in [11; 12; 13; 14] to solve the VNE problem. The exact solution uses mixed integer programming (MIP) or integer linear programming (ILP) to establish a mathematical model, which is commonly solved by solution software such as GLPK [15] and CPLEX [16]. However, the computational complexity of the exact solution increases exponentially with the expansion of the network scale. In contrast, heuristic solutions can solve the virtual network embedding scheme in a shorter time, but the mapping results are approximate optimal solutions. Some typical studies [17; 18; 19; 20; 21; 22] focus on designing different heuristic algorithms to obtain better embedding solutions.