Alocação de Recursos para Redes Virtuais com Seleção de Método de Resolução via Aprendizado de Máquina

  • Samuel Moreira Abreu Araújo Universidade Federal de Minas Gerais
  • Fernanda Sumika Hojo de Souza Universidade Federal de São João del-Rei
  • Geraldo Robson Mateus Universidade Federal de Minas Gerais

Resumo


A alocação de recursos é um problema NP-difícil, presente no Mapeamento de Redes Virtuais (VNE) e na Virtualização de Funções de Rede (NFV). Nesse contexto, um ponto pouco explorado na literatura é relacionado a quando se deve aplicar um método de resolução heurístico ou exato. Tanto para o VNE, quanto para o NFV, normalmente a literatura indica um tratamento heurístico devido à complexidade do problema e à elevada dimensão dos dados. Entretanto, em experimentos preliminares, percebe-se que em alguns momentos um tratamento exato pode ser aplicado em um tempo praticável. Foi notado que esses eventos não se tratam de casualidades, mas decorrem de várias condições relacionadas ao Substrato de Rede (SN) residual e às demandas de rede requisitadas. A abordagem proposta neste artigo é baseada na aplicação de técnicas de Aprendizado de Máquina (AM) para alocação de recursos em rede, e tem como objetivo prever em quais situações se pode preterir uma abordagem heurística em prol de uma exata. Para tal, foi adotado o VNE e duas abordagens da literatura. As simulações realizadas mostram que o tratamento com AM melhora a taxa de aceitação e a receita de mapeamento em relação à heurística, e reduz o tempo de processamento em relação à abordagem exata.

Palavras-chave: Virtualização de Redes, Alocação de Recursos, Aprendizado de Máquina

Referências

Amaldi, E., Coniglio, S., Koster, A., and Tieves, M. (2016). On the computational complexity of the virtual network embedding problem. Electronic Notes in Discrete Mathematics, 52:213–220.

Amaral, P., Dinis, J., Pinto, P., Bernardo, L., Tavares, J., and Mamede, H. S. (2016). Machine learning in software defined networks: Data collection and traffic classification. In 2016 IEEE 24th International Conference on Network Protocols (ICNP), pages 1–5.

Araújo, S., Souza, F. S., and Mateus, G. R. (2019). Abordagens exata e heurística para o mapeamento de redes virtuais. In Anais Estendidos do XXXVII Simpósio Brasileiro de Redes de Computadores e Sistemas Distribuídos, pages 153–160, Porto Alegre, RS, Brasil. SBC.

Araújo, S. M. A., de Souza, F. S. H., and Mateus, G. R. (2018). Virtual network embedding in multi-domain environments with energy efficiency concepts. In 2018 International Conference on Information Networking (ICOIN), pages 205–210.

Beikta, C., Gzpek, D., Ula, A., and Lokman, E. (2017). Secure virtual network embedding with flexible bandwidth-based revenue maximization. Comput. Netw., 121(C):89–99.

Blenk, A., Kalmbach, P., van der Smagt, P., and Kellerer, W. (2016). Boost online virtual network embedding: Using neural networks for admission control. In 2016 12th International Conference on Network and Service Management (CNSM), pages 10–18.

Cheng, R. . and Chang, C. . (1997). Neural-network connection-admission control for atm networks. IEE Proceedings - Communications, 144(2):93–98.

Chowdhury, N. M. M. K., Rahman, M. R., and Boutaba, R. (2009). Virtual network embedding with coordinated node and link mapping. In IEEE INFOCOM 2009, pages 783–791.

Cohen, R., Lewin-Eytan, L., Naor, J. S., and Raz, D. (2015). Near optimal placement of virtual network functions. In 2015 IEEE Conference on Computer Communications (INFOCOM), pages 1346–1354.

Fischer, A., Botero, J. F., Beck, M. T., de Meer, H., and Hesselbach, X. (2013). Virtual Network Embedding: A Survey. IEEE Communications Surveys Tutorials, 15(4):1888–1906.

Laghrissi, A. and Taleb, T. (2018). A Survey on the Placement of Virtual Resources and Virtual Network Functions. IEEE Communications Surveys Tutorials, pages 1–1.

Luizelli, M. C., Bays, L. R., Buriol, L. S., Barcellos, M. P., and Gaspary, L. P. (2015). Piecing together the NFV provisioning puzzle: Efficient placement and chaining of virtual network functions. In 2015 IFIP/IEEE International Symposium on Integrated Network Management (IM), pages 98–106.

Nokia (2016). White paper: Dynamic end-to-end network slicing for 5g. [online] available at https://resources.ext.nokia.com/asset/200339.

Powers, D. and Ailab (2011). Evaluation: From precision, recall and f-measure to roc, informedness, markedness correlation. J. Mach. Learn. Technol, 2:2229–3981.

Shi, R., Zhang, J., Chu, W., Bao, Q., Jin, X., Gong, C., Zhu, Q., Yu, C., and Rosenberg, S. (2015). Mdp and machine learning-based cost-optimization of dynamic resource allocation for network function virtualization. In 2015 IEEE International Conference on Services Computing, pages 65–73.

Souza, B. A., Mateus, G. R., and de Souza, F. S. (2018). Compact and extended formulations for the virtual network embedding problem. Electronic Notes in Discrete Mathematics, 64:205 – 214. 8th International Network Optimization Conference - INOC 2017.

Waxman, B. M. (1988). Routing of multipoint connections. IEEE Journal on Selected Areas in Communications, 6(9):1617–1622.

Xie, J., Yu, F. R., Huang, T., Xie, R., Liu, J., Wang, C., and Liu, Y. (2019). A survey of machine learning techniques applied to software defined networking (sdn): Research issues and challenges. IEEE Communications Surveys Tutorials, 21(1):393–430.

Zhao, Y., Li, Y., Zhang, X., Geng, G., Zhang, W., and Sun, Y. (2019). A survey of networking applications applying the software defined networking concept based on machine learning. IEEE Access, 7:95397–95417.
Publicado
07/12/2020
ARAÚJO, Samuel Moreira Abreu; SOUZA, Fernanda Sumika Hojo de ; MATEUS, Geraldo Robson. Alocação de Recursos para Redes Virtuais com Seleção de Método de Resolução via Aprendizado de Máquina. In: SIMPÓSIO BRASILEIRO DE REDES DE COMPUTADORES E SISTEMAS DISTRIBUÍDOS (SBRC), 38. , 2020, Rio de Janeiro. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 2020 . p. 211-224. ISSN 2177-9384. DOI: https://doi.org/10.5753/sbrc.2020.12284.