1 Introduction
-
We study the problem of reliable mapping for VN requests with location constraints in edge-of-things computing.
-
We propose the model and design an efficient algorithm for the studied problem.
-
We conduct extensive simulations to evaluate the performance of our proposed algorithms.
2 Problem statement and formulation
2.1 Virtual network request
2.2 Physical network in edge-of-things computing
2.3 Reliable virtual network provisioning
2.3.1 Given
2.3.2 Mapping constraints
2.3.3 Precondition
2.3.4 Problem
2.4 Problem formulation
2.4.1 Residual resources
2.4.2 Objective
3 Algorithm design
3.1 Step 1: successively map all the simultaneously arriving VNs onto the physical network of edge-of-things computing
3.2 Step 2: when all the virtual nodes are mapped, generate a new virtual network according to the mapping results
3.3 Step 3: enhance the newly generated virtual network
3.4 Step 4: map the extra backup links and nodes
GG-SMVNM Algorithm |
---|
Input: A physical network G
S
= (N
S
, L
S
); the arrived VN requests VN0, VN1…VNX. |
Output: A survivable mapping solution considering the location constraints of virtual nodes. |
Step 1: Map the VNs that are arriving simultaneously. The geographic locations constraints of the virtual node must be considered while mapping the VNs, and we should map the virtual nodes that belong to different VNs to the same substrate node. Step 2: Update the resources of the physical network. Compute the remaining recourses of physical nodes and links and calculate the costs of mapping multiple VNs. Step 3: Generate a new virtual network based on the mapping results. 3.1) Traverse the nodes of the physical network and record the amount of resources allocated to virtual nodes. Add the virtual nodes to the set of virtual nodes from the new VN, and the capacity demand of these virtual nodes are the amount of recourses on corresponding physical nodes. Take the geographic locations of the corresponding physical nodes as the location constraints of the newly generated virtual nodes. 3.2) Traverse the routing table of the physical network. If the IDs of the corresponding substrate nodes of the virtual nodes in the set mentioned in 3.1 match the routing table, then there is a virtual link between these two virtual nodes. Step 4: Map the backup nodes and links of the enhanced newly generated VN. Traverse every backup node that needs to be mapped in descending order of resource demands and map the backup nodes and corresponding links onto the physical network. 4.1) Traverse the physical network nodes and compute the mapping costs of backup nodes and corresponding links. 4.2) Select a physical node with the minimum costs. Map the backup node onto it and map the corresponding backup links. 4.3) Update the resources and record the remaining capacities of the physical nodes and links. Step 5: Compute the mapping cost of backup nodes and links. |
GG-SVNM Algorithm |
---|
Input: A physical network G
S
= (N
S
, L
S
), a virtual network request G
V
= (N
V
, L
V
). |
Output: A survivable mapping solution considering the location constraints of virtual nodes. |
Step 1: Calculate CMS
i
for each physical node. Step 2: Map the original virtual network. The location constraints must be satisfied while mapping the virtual nodes. Step 3: Update the resources of the physical network. Calculate the remaining capacities of the physical nodes and links after mapping the original virtual network. Compute the total mapping costs of all virtual links and nodes from the original virtual network. Step 4: Map the backup links and nodes. 4.1) Traverse all physical nodes. Then compute the mapping costs of the backup virtual nodes and relevant backup links. a) Compute the mapping costs of backup links corresponding to backup nodes. b) Compute the mapping costs of backup nodes. c) Calculate the reduced costs brought on by the other virtual nodes in CMS
i
. 4.2) Select the physical node with minimum mapping costs. Then map the backup node onto it and map the corresponding backup links. 4.3) Update the resources. Calculate the available resources for the links and nodes on the physical network. Step 5: Calculate the mapping costs of backup nodes and backup links. |