Latency-Aware Virtual Network Embedding using Clusters for Green Fog Computing

Virtual Network Embedding (VNE) is a strategy of selecting and allocating resources from the underlying substrate network to demands of Virtual Network Requests (VNRs). We formulate a Latency-Aware Virtual Network Embedding (LA-VNE) optimization problem for minimizing the total cost (energy spent on both transmission and computation) while satisfying the latency demand of applications. As the LA-VNE problem is complex, we propose a heuristic algorithm called the Clustered Network Embedding (CNE) algorithm. Our algorithm groups Fog Nodes (FNs) into multiple clusters based on their parameters, and preliminarily evaluates network performance in terms of cost and latency by embedding VNRs into these clusters prior to the actual embedding. Our simulation results show that the CNE algorithm has near-optimal performance in small networks, and shows a clear improvement over the general Particle Swarm Optimization (PSO) algorithm in terms of energy cost (29% lower) and acceptance ratio (7 percentage points higher) in large networks under high computation load. It is also quicker in finding solutions (38% lower execution time).