# DDS: A Delay-Based Differentiated Service Virtual Network Embedding Algorithm
## 4 Proposed Algorithm
### ILP Sub-Algorithm  
This section introduces a constrained integer linear programming algorithm that we use to solve delay-sensitive virtual network requests. The algorithm first calculates the candidate node set and the candidate link set to reduce the scale of the ILP solution and then calculates the optimal solution of the embedding under the objective function. Algorithm 4 describes the selection process of candidate sets. D in Line 2 represents the location constraints of the virtual network. We assume that the position of the node is defined by coordinates \((x,y)\). Equation (14) defines the distance between nodes. \[\text{dist}(n_{j}^{v},n_{i}^{s})= \sqrt{\left(x_{j}^{v}-x_{i}^{s}\right)^{2}+\left(y_{j}^{v}-y_{i}^ {s}\right)^{2}}, \tag{14}\]  
Figure 2: An example of virtual node mapping. The candidate node set should be selected within the distance constraints and satisfy the computing and storage requirements of virtual nodes. When constructing the candidate link set, for each virtual link, select the substrate links whose bandwidth and delay between the substrate candidate nodes corresponding to both ends nodes of the link satisfy the constraints and add them to candidate link set, to reduce the calculation scale. The next integer linear programming algorithm seeks the best embedding scheme from the candidate sets. The ILP model is described as follows:  
1. Variables  
\[x_{i}^{j}=\left\{ \begin{array}{ll}1,\text{ if }n_{j}^{v}\text{ is mapped into }n_{i}^{s}\\ 0,\text{ else}\end{array} \right., \tag{15}\]  
\[y_{mn}^{pq}=\left\{ \begin{array}{ll}1,\text{ if }l_{pq}^{v}\text{ is mapped into }l_{mn}^{s}\\ 0,\text{ else}\end{array} \right., \tag{16}\]  
2. Restrictions  
(1) virtual node constraints  
Equation (17) is designed to ensure that each virtual node maps to only one substrate node. \[\forall n_{j}^{v}\in N_{v},\ \sum_{n_{i}^{v}\in N_{v}}x_{i}^{j}=1, \tag{17}\]  
(2) substrate node constraints  
Equation (18) aims to ensure that each substrate node can only accept the mapping of one virtual node from the same virtual network. \[\forall n_{i}^{s}\in N_{s},\ \sum_{n_{j}^{v}\in N_{v}}x_{i}^{j}\leq 1, \tag{18}\]  
(3) virtual link constraints  
Equation (19) is meant to ensure that each virtual link is allocated to one substrate path, and that the path endpoint corresponds to the substrate node selected by the virtual link endpoint. \[\forall l_{pq}^{v}\in L_{V},\ \forall n_{m}^{s}\in N_{s},\ \sum_{n_{n}^{s}\in N _{s}}y_{mn}^{pq}-y_{nm}^{pq}=x_{m}^{p}-x_{n}^{p}, \tag{19}\]  
(4) Node resource constraints  
The chosen substrate node must satisfy the computing and storage requirements of the virtual node, as defined in Equations (20) and (21). \[\forall n_{i}^{s}\in N_{s},\ \sum_{n_{j}^{v}\in N_{v}}x_{i}^{j}\cdot c(n_{j}^{v}) \leq R_{c}(n_{i}^{s}), \tag{20}\]\[\forall n_{i}^{s}\in N_{s},\ \sum_{n_{j}^{s}\in N_{p}}x_{i}^{j}\cdot s(n_{j}^{v}) \leq R_{s}(n_{i}^{s}), \tag{21}\]  
(5) link bandwidth constraints  
The chosen substrate link must be able to provide sufficient bandwidth to satisfy the bandwidth requirements of the virtual link, as defined in Equation (22). \[\forall l_{mn}^{s}\in L_{v},\ \sum_{l_{pq}^{s}\in L_{v}}y_{mn}^{pq}\cdot b(l_{pq}^{v}) \leq R_{b}(l_{mn}^{s}), \tag{22}\]  
(6) link propagation delay constraints  
Equation (23) is designed to ensure that the delay of the chosen substrate link \(delay(l_{mn}^{s})\) does not exceed the propagation delay limit of the virtual link \(delay(l_{pq}^{v})\). \[\forall l_{pq}^{v}\in L_{v},\ \sum_{l_{mn}^{s}\in L_{v}}y_{mn}^{pq}\cdot delay(l_{ mn}^{s})\leq delay(l_{pq}^{v}), \tag{23}\]  
3. objective  
\[\min:\sum_{l_{pq}^{s}\in L_{v}}\sum_{l_{mn}^{s}\in L_{s}}(y_{mn}^{pq}\cdot b( l_{pq}^{v})+y_{mn}^{pq}\cdot delay(l_{mn}^{s})), \tag{24}\]  
For a virtual network embedding request, the substrate node resources cost of different embedding strategies is the same, but due to different substrate paths chosen by different embedding strategies, the link resources cost is different.