Distributed parallel algorithms for online virtual network embedding applications

• Published in: International journal of communication systems 2023-01, Vol.36 (1), p.n/a
• Main Authors: Lu, Qiao, Nguyen, Khoa, Huang, Changcheng
• Format: Article
• Language: English
• Subjects: 5G network; Algorithms; distributed parallel algorithm; Embedding; Genetic algorithms; Integer programming; Internet of Things; Linear programming; metaheuristic; Network latency; network virtualization; parallel genetic algorithm; Run time (computers); Substrates; Virtual networks
• ISSN: 1074-5351; 1099-1131
• DOI: 10.1002/dac.4325

Summary Network virtualization (NV) has ubiquitously emerged as an indispensable attribute to enable the success of the forthcoming virtualized networks (eg, 5G network and smart Internet of Things [IoT]). Virtual network embedding (VNE) is the major challenge in NV that allows multiple heterogeneous virtual networks (VNs) to simultaneously coexist on a shared substrate infrastructure. A great number of VNE algorithms have been proposed, but over the past decades, most of them are only targeting for VNE node mapping. In this paper, we propose two distributed parallel genetic algorithms, which are based on two versions of crossover and mutation schemes, for online VN link embedding problems with low latency and high efficiency. Furthermore, we conduct a time analysis on the executing time of independently distributed parallel computing machines in details. This comprehensive analysis validates the parallel computing scalability on an identical number of predefined parallel machines. Extensive simulations have shown that our proposed algorithms can achieve better performance than integer linear programming (ILP)–based solutions while meeting the stringent time requirements for online VN embedding applications. Our proposed algorithms yield superior performance in running time with 32.78% up to 1727.8% faster than existing popular VNE algorithms. Additionally, the theoretical analysis indicates that the execution time can be reduced to logarithmic times by applying proposed distributed parallel algorithms. In this paper, we effectively employ parallel computing on genetic algorithms to deal with VNE link mapping problems by exploiting distributed machines. Such new‐fashioned deployment is not only boosting up GA itself to reduce the operation time but also increasing a chance to find the optimal solution as guided by a fitness function that minimizes hop count while improving load balancing.