# DDS: A Delay-Based Differentiated Service Virtual Network Embedding Algorithm
## 4 Proposed Algorithm
### Two Stage Embedding Sub-Algorithm  
In this section, we propose a node mapping algorithm based on greedy strategy, which considers both node resource value and node resource balance. For ease of understanding, Algorithms 1 and 2 give the pseudocode of the algorithms. We measure nodes value and sort the virtual nodes and substrate nodes in non-increasing order. Simply considering node resources is not conducive to the success of link mapping in the next stage, and adjacent link resources should be additionally considered when measuring the node resources' value, which helps to improve the success rate of link mapping. When sorting nodes, we comprehensively consider node computing resources, node storage resources, and adjacent link resources and expand them based on the article [18], defining the resource value of nodes as follows:  
\[NRV(n_{i}^{s})=(R_{c}(n_{i}^{s})+R_{s}(n_{i}^{s}))\times\sum_{l_{s}\in L_{s}(n_ {i}^{s})}R_{b}(l_{s}), \tag{11}\]  
where \(L_{s}(n_{i}^{s})\) represents the set of all substrate links set adjacent to node \(n_{i}^{s}\). Figure 1: Flow Chart of VNE Algorithm. In addition, considering that the virtual node has different node resource requirements, it may lead to the excessive use of a certain resource. Due to the Cask Effect, it is difficult to satisfy the demands of other nodes which affects the success rate of embedding. In order to solve this problem, the load consumption balance of the two resources should also be considered. Define the node computing resource demand balance as follows:  
\[RB_{c}=R_{c}(n_{i}^{s})/c(n_{j}^{v}), \tag{12}\]  
Similarly, the node storage resource demand balance is:  
\[RB_{s}=R_{s}(n_{i}^{s})/s(n_{j}^{v}), \tag{13}\]  
The resource demand balance reflects the relationship between the remaining resources of the substrate node and the virtual node demand. The substrate node with the closest \(RB_{c}\) and \(RB_{s}\) should be selected first to avoid the imbalance of resource consumption and help to accommodate more virtual network requests. Figure 2 gives a typical example. The numbers in the circles represent the available computing and storage resources, the numbers over the links represent the available bandwidth, and the numbers in the hexagon represent the computing and storage requirements. When selecting the substrate node for virtual node a, the \(NRV\) of A is \((20+40)\times(10+20+10)=2400\), and the \(NRV\) of B is \((30+30)\times(10+20+10)=2400\). Obviously, if A is selected for embedding, A can no longer provide services for subsequent virtual networks due to the exhaustion of computing resources, even though the available storage resource of A is still abundant. After combining the balance factor, the \(nodeVal\) of A is \(2400\div(2\div 1)=1200\), and the \(nodeVal\) of B is \(2400\div(1.5\div 1.5)=2400\). B is selected for embedding. In this case, both A and B can continue to provide services for the subsequent virtual networks. In link mapping, some algorithms assume support for path splitting, which means that when a single substrate path cannot satisfy the virtual links' requirements, a virtual link is allowed to be allocated to multiple substrate paths. Although path splitting can improve the utilization of the substrate links, it will cause some additional burdens, such as the switch needing to reorganize packets, the additional delay caused by multiple links, and the additional flow table resource used to save flow rules in SDN. Therefore, path splitting is not considered in this paper. When the node mapping is over, the virtual link mapping is transformed into a resource-constrained shortest path solution problem between fixed nodes. Algorithm 3 describes our link mapping algorithm.