Vertical Parallelization of Differential Evolution Heuristic for Network Slicing in 5G Scenarios
Resumo
The 5G mobile network is based on a virtualized infrastructure and offers a virtual network (VN) creation service considering many new scenarios arising from the 5G vision. The diversity of scenarios and the instantiation of VN on-demand induce pressure on the virtual network embedding (VNE). VNE is the mapping of virtual nodes and links to real nodes and links obeying the QoS parameters present in the VN request and available resources. Since this is an optimization and NP-Hard problem, multiple efforts have been made to create VNE algorithms. Considering such efforts, this work presents: (i) a fitness function regarding multiobjective optimization; and (ii) a Parallel Differential Evolution (PDE) approach to face the VNE. We designed the PDE due to the lack of viable parallel solutions in the 5G scenario. We compared our approaches with different versions of Greedy, Stress, and Genetic Algorithms, totaling ten approaches. The results demonstrate that DE and its parallel version obtained a higher number of mapped requisitions. Also, the parallel performance decreases the execution time in certain conditions; in a favorable scenario, the parallel version obtains up 21.04% of runtime reduction.Referências
5G PPP Architecture Working Group (2016). View on 5G Architecture. White paper, (July).
5GPPP (2019). View on 5G Architecture. Technical Report June, 5GPPP.
Cao, H., Yang, L., Liu, Z., and Wu, M. (2016). Exact solutions of VNE: A survey. China Communications, 13(6):48–62.
Chen, L., Abdellatif, S., Simo Tegueu, A. F., and Gayraud, T. (2019). Embedding and re-embedding of virtual links in software-defined multi-radio multi-channel multi-hop wireless networks. Computer Communications, 145(July):161–175.
Fischer, A., Botero, J. F., Beck, M. T., De Meer, H., and Hesselbach, X. (2013). Virtual network embedding: A survey. IEEE Communications Surveys and Tutorials, 15(4).
Gomes, R., Vieira, D., and Franklin de Castro, M. (2021). Differential evolution for vne-5g scenarios. In 2021 11th IFIP International Conference on New Technologies, Mobility and Security (NTMS), pages 1–6.
Han, B., Lianghai, J., and Schotten, H. D. (2018). Slice as an Evolutionary Service: Genetic Optimization for Inter-Slice Resource Management in 5G Networks. IEEE Access, 6(c):33137–33147.
Nguyen, K., Lu, Q., and Huang, C. (2020). Efficient virtual network embedding with node ranking and intelligent link mapping. In 2020 IEEE 9th International Conference on Cloud Networking (CloudNet), pages 1–5. IEEE.
Nguyen, K. T. and Huang, C. (2019). An intelligent parallel algorithm for online virtual network embedding. In 2019 International Conference on Computer, Information and Telecommunication Systems (CITS), pages 1–5. IEEE.
Qin, Z., Denker, G., Giannelli, C., Bellavista, P., and Venkatasubramanian, N. (2014). A software defined networking architecture for the internet-of-things. IEEE/IFIP NOMS 2014.
Salimifard, K. and Bigharaz, S. (2020). The multicommodity network flow problem: state of the art classification, applications, and solution methods. Operational Research, pages 1–47.
Tasoulis, D., Pavlidis, N., Plagianakos, V., and Vrahatis, M. (2004). Parallel differential evolution. In Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No.04TH8753), volume 2, pages 2023–2029 Vol.2.
Vassilaras, S., Gkatzikis, L., Liakopoulos, N., Stiakogiannakis, I. N., Qi, M., Shi, L., Liu, L., Debbah, M., and Paschos, G. S. (2017). The Algorithmic Aspects of Network Slicing. IEEE Communications Magazine, 55(8):112–119.
Wu, H., Zhou, F., Chen, Y., and Zhang, R. (2020). On Virtual Network Embedding: Paths and Cycles. IEEE Transactions on Network and Service Management, 4537(c):1–14.
Yu, M., Yi, Y., Rexford, J., and Chiang, M. (2008). Rethinking virtual network embedding: Substrate support for path splitting and migration. Computer Communication Review, 38(2):19–29.
Zhou, Z., Chang, X., Yang, Y., and Li, L. (2016). Resource-Aware virtual network parallel embedding based on genetic algorithm. Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings, 0:81–86.
Zhu, Y. and Ammar, M. (2006). Algorithms for assigning substrate network resources to virtual network components. Proceedings - IEEE INFOCOM.
5GPPP (2019). View on 5G Architecture. Technical Report June, 5GPPP.
Cao, H., Yang, L., Liu, Z., and Wu, M. (2016). Exact solutions of VNE: A survey. China Communications, 13(6):48–62.
Chen, L., Abdellatif, S., Simo Tegueu, A. F., and Gayraud, T. (2019). Embedding and re-embedding of virtual links in software-defined multi-radio multi-channel multi-hop wireless networks. Computer Communications, 145(July):161–175.
Fischer, A., Botero, J. F., Beck, M. T., De Meer, H., and Hesselbach, X. (2013). Virtual network embedding: A survey. IEEE Communications Surveys and Tutorials, 15(4).
Gomes, R., Vieira, D., and Franklin de Castro, M. (2021). Differential evolution for vne-5g scenarios. In 2021 11th IFIP International Conference on New Technologies, Mobility and Security (NTMS), pages 1–6.
Han, B., Lianghai, J., and Schotten, H. D. (2018). Slice as an Evolutionary Service: Genetic Optimization for Inter-Slice Resource Management in 5G Networks. IEEE Access, 6(c):33137–33147.
Nguyen, K., Lu, Q., and Huang, C. (2020). Efficient virtual network embedding with node ranking and intelligent link mapping. In 2020 IEEE 9th International Conference on Cloud Networking (CloudNet), pages 1–5. IEEE.
Nguyen, K. T. and Huang, C. (2019). An intelligent parallel algorithm for online virtual network embedding. In 2019 International Conference on Computer, Information and Telecommunication Systems (CITS), pages 1–5. IEEE.
Qin, Z., Denker, G., Giannelli, C., Bellavista, P., and Venkatasubramanian, N. (2014). A software defined networking architecture for the internet-of-things. IEEE/IFIP NOMS 2014.
Salimifard, K. and Bigharaz, S. (2020). The multicommodity network flow problem: state of the art classification, applications, and solution methods. Operational Research, pages 1–47.
Tasoulis, D., Pavlidis, N., Plagianakos, V., and Vrahatis, M. (2004). Parallel differential evolution. In Proceedings of the 2004 Congress on Evolutionary Computation (IEEE Cat. No.04TH8753), volume 2, pages 2023–2029 Vol.2.
Vassilaras, S., Gkatzikis, L., Liakopoulos, N., Stiakogiannakis, I. N., Qi, M., Shi, L., Liu, L., Debbah, M., and Paschos, G. S. (2017). The Algorithmic Aspects of Network Slicing. IEEE Communications Magazine, 55(8):112–119.
Wu, H., Zhou, F., Chen, Y., and Zhang, R. (2020). On Virtual Network Embedding: Paths and Cycles. IEEE Transactions on Network and Service Management, 4537(c):1–14.
Yu, M., Yi, Y., Rexford, J., and Chiang, M. (2008). Rethinking virtual network embedding: Substrate support for path splitting and migration. Computer Communication Review, 38(2):19–29.
Zhou, Z., Chang, X., Yang, Y., and Li, L. (2016). Resource-Aware virtual network parallel embedding based on genetic algorithm. Parallel and Distributed Computing, Applications and Technologies, PDCAT Proceedings, 0:81–86.
Zhu, Y. and Ammar, M. (2006). Algorithms for assigning substrate network resources to virtual network components. Proceedings - IEEE INFOCOM.
Publicado
23/05/2022
Como Citar
GOMES, Rayner; VIEIRA, Dario; CASTRO, Miguel Franklin de.
Vertical Parallelization of Differential Evolution Heuristic for Network Slicing in 5G Scenarios. In: SIMPÓSIO BRASILEIRO DE REDES DE COMPUTADORES E SISTEMAS DISTRIBUÍDOS (SBRC), 40. , 2022, Fortaleza.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 308-321.
ISSN 2177-9384.
DOI: https://doi.org/10.5753/sbrc.2022.222314.
