Exact and Heuristic Approaches to Virtual Network Mapping

• Samuel M. A. Araújo UFMG
• Geraldo R. Mateus UFMG
• Fernanda S. H. de Souza UFSJ

DOI: https://doi.org/10.5753/ctd.2019.6335

Abstract

Network virtualization is a technique that allows the emulation of multiple virtual networks (VNs) together on the same physical network structure (SN). This technique induces benefits inherent to freedom of network protocols rigidity, in addition, promote the new web technologies development. Define which physical devices set will host the virtual networks is a problem belongs to the NP-hard class and known as Virtual Network Embedding (VNE). Unlike the current literature, this work was singled out because it presented different exact and heuristic approaches for the resolution of VNE, operating in environments composed of one or more network domains. Moreover, the approaches developed can serve the different VNs demands characteristics, working on online, periodic and offline processing models. Beyond that, was introduced the application of the heuristic approach in an online and multidomain context, through the control of a network orchestrator. A comparative study of three distinct orchestration models was made, with: (i) total knowledge, (ii) partial knowledge and (iii) without knowledge of the internal physical network infrastructure of the domains. At the end of the paper, the different proposed approaches behaviors were contrasted and discussed using four different objectives: (i) load balancing, (ii) energy consumption, (iii) service providers' profit, and (iv) messages exchanged between different domains.

Keywords: Optimization, Network Virtualization, Virtual Network Embedding, Multi-domain networks, Metaheuristic, Integer Linear Programming

References

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.

Dalla-Costa, A. G., Schimuneck, M. A. K., Wickboldt, J. A., Both, C. B., Gaspary, L. P., and Granville, L. Z. (2017). NFV em Redes 5G: Avaliando o Desempenho de Composição de Funções Virtualizadas via Maestro. Anais do XXXVSBRC, 35.

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.

Houidi, I., Louati, W., Ameur, W. B., and Zeghlache, D. (2011). Virtual network provisioning across multiple substrate networks. Computer Networks, 55(4):1011 – 1023. Special Issue on Architectures and Protocols for the Future Internet.

Zhu, Y. and Ammar, M. (2006). Algorithms for Assigning Substrate Network Resources to Virtual Network Components. In Proceedings IEEE INFOCOM 2006. 25TH IEEE International Conference on Computer Communications, pages 1–12.