Titulo Estágio
Algorithms for the Disjoint Virtual Network Embedding Problem
Áreas de especialidade
Comunicações, Serviços e Infraestruturas
Sistemas Inteligentes
Local do Estágio
Departamento de Engenharia Informática, Polo II - Pinhal de Marrocos 3030-290 Coimbra
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). The problem of allocating several VN into the substrate network is known as the Virtual Network Embedding (VNE) [2], 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 [3]. 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.
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] 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.
[3] 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.
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 LCT group. A workplace will be provided as well as the required computational resources.
Observações
Advisors: Noé Godinho (noe@dei.uc.pt) and David Abreu (dabreu@dei.uc.pt).
Orientador
Noé Godinho / David Abreu
noe@dei.uc.pt 📩