Resource Allocation for Virtual Networks with Resolution Method Selection via Machine Learning

• Samuel Moreira Abreu Araújo Federal University of Minas Gerais
• Fernanda Sumika Hojo de Souza Federal University of Sao Joao del-Rei
• Geraldo Robson Mateus Federal University of Minas Gerais

DOI: https://doi.org/10.5753/sbrc.2020.12284

Abstract

The network resource allocation is considered an NP-hard problem, present in Virtual Network Embedding (VNE) and the Virtual Network Function (NFV). In this context, a little-explored question in the literature is related to when to apply an exact or heuristic resolution method. For both VNE and NFV, the literature usually suggests a heuristic treatment, considered the complexity and the high dimension of the data. However, in preliminary experiments, it is possible to observe that occasionally, the exact treatment can be applied in a practicable time. It is inferred that these events are not casual; they come from several conditions related to the residual Network Substrate (SN) and the network demands requested. The approach proposed in this paper is based on the application of the Machine Learning (ML) technics in order to allocate the network resources and aims to predict the situations in which the exact approach could supersede the heuristic. For this purpose, the VNE and both approaches of the literature were used. The simulations performed showed that ML treatment increases the acceptance ratio and revenue in comparison with the heuristic, and reduces the processing time in comparison with the exact approach.

Keywords: Network Virtualization, Resource Allocation, Machine learning

References

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.