Titulo Estágio
Tackling the Disjoint Virtual Network Embedding Problem
Áreas de especialidade
Sistemas Inteligentes
Comunicações, Serviços e Infraestruturas
Local do Estágio
CISUC
Enquadramento
Network Virtualization is a tool that allows the usage of the same physical (or substrate) resources by several users and enables heterogeneity of devices in the network [1]. The aim is to combine network hardware and resources into a network software module, a Virtual Network (VN) (also called Service Function Chains (SFC) if the VN has a specific order of execution and service types [2]). The problem of allocating several VN into the substrate network is known as the Virtual Network Embedding (VNE) [3], which considers one or more metrics to optimise and the associated resource constraints.
In realistic environments, an important factor is reliability (or survivability) of the network. If a failure occurs on the substrate network, it is necessary to ensure a transparent transition of the users’ resources. A usual approach is to create a backup (or disjoint) VN that has the least common substrate nodes and edges between the main VN and the backup.
For well-known problems, such as the shortest path, there are several approaches that ensure reliability of the network. One example is to consider that each edge has one or more colours, and the goal is to find two paths that minimize the number of overlapping colours [4]. This can be applied into the VNE problem by considering that each edge on the substrate network has a unique colour and each virtual edge contain the colours associated to the substrate edges. One approach to solve this problem is to use exact algorithms, such as Branch-and-Bound.
This work will focus on developing a Branch-and-Bound algorithm by researching branching techniques and bounds to improve pruning of solutions to solve the Disjoint VNE problem. The student is expected to analyse the Impact of different substrate networks and VNs in a number of scenarios. Realistic services from immersive media environments and other types of enviroments will be considered to validate the proposed approach [5].
References:
[1] R. Mijumbi, J. Serrat, J. Gorricho, N. Bouten, F. De Turck and R. Boutaba, "Network Function Virtualization: State-of-the-Art and Research Challenges," in IEEE Communications Surveys & Tutorials, vol. 18, no. 1, pp. 236-262, Firstquarter 2016, doi: 10.1109/COMST.2015.2477041.
[2] D. Bhamare, R. Jain, M. Samaka, and A. Erbad, ‘A survey on service function chaining’, Journal of Network and Computer Applications, vol. 75, pp. 138–155, Nov. 2016, doi: 10.1016/j.jnca.2016.09.001.
[3] A. Fischer, J. F. Botero, M. T. Beck, H. de Meer and X. Hesselbach, "Virtual Network Embedding: A Survey," in IEEE Communications Surveys & Tutorials, vol. 15, no. 4, pp. 1888-1906, Fourth Quarter 2013, doi: 10.1109/SURV.2013.013013.00155.
[4] S. Yuan, S. Varma and J. P. Jue, "Minimum-color path problems for reliability in mesh networks," Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies., 2005, pp. 2658-2669 vol. 4, doi: 10.1109/INFCOM.2005.1498549.
[5] D. You et al., ‘Fog Computing as an Enabler for Immersive Media: Service Scenarios and Research Opportunities’, IEEE Access, vol. 7, pp. 65797–65810, 2019, doi: 10.1109/ACCESS.2019.2917291.
Objetivo
The goal of this work is to develop a Branch-and-Bound approach to solve the Disjoint Virtual Network Embedding problem by minimising the number of overlapping colours in the infrastructure, while considering resource constraints. For the experimental analysis, different network topologies, VNs, and scenarios will be used. If time allows, a bi-objective version of the problem can be considered.
Plano de Trabalhos - Semestre 1
• Literature review of Branch-and-Bound and the Virtual Network Embedding problem
• Development of upper and lower bounds
• Preliminary experimental evaluation
• Writing of the intermediate report
Plano de Trabalhos - Semestre 2
• Development of Branch-and-Bound for the Disjoint Virtual Network Embedding problem
• Experimental evaluation
• Study of the bi-objective version
• Writing of the final report
Condições
The work is to be executed at the laboratories of the CISUC’s NCS group. A workplace will be provided as well as the required computational resources.
Orientador
Noé Godinho
noe@dei.uc.pt 📩