Skip to content

Santiago Villanueva PFC

Author: Santiago Villanueva Puig Tutor: Xavier Hesselbach Title: Contribution to the Virtual Network Embedding problem using a new Paths Algebra strategy.


Network virtualization presents the necessary characteristics to become the technology for the
future Internet architecture, as allows the running of multiple virtual networks using a shared
substrate network. These virtual network are grouped in different demands, that would be the
demands of the clients. At the same time, these consist of a virtual network with virtual resources
demands -basically process capacity (CPU) and bandwith (BW)-, to be fulfilled by the resources
from the substrate network.
The main problem of embedding virtual networks in a substrate network is the main resource
allocation challenge in network virtualization and is usually referred to as the virtual network
embedding problem or VNE problem. This process can be divided in two stages: node mapping
and link mapping, although it can be solved coordinately in one stage. A new mathematical multiconstraint
routing framework for linear and non-linear metrics called “paths algebra” is proposed
for the second stage, already providing good results thanks to its flexibility of functioning and
capacity to include linear and non-linear parameters.
This thesis suggests an improvement of this paths algebra-based strategy consisting of a coordinated
mapping of nodes and links. This strategy is based on a ranking made by the bi-directional
pair of nodes of the substrate network, ordered by the available resources of each pair of nodes,
called New Paths Algebra.
The main objective of the New Paths Algebra will be to offer better results than the ones
of the original paths algebra without the coordinated mapping of nodes and links. Simulations
regarding both algorithms will be done: the way to proceed will consist of doing simulations
for the same scenarios from both algorithms. These will be quite big scenarios, and the virtual
network requests will be increasingly loaded.
In order to achieve the objectives proposed, more substrate network topologies and the metrics
based in centralities derived from them will be studied. Using these metrics, it is intended to create
a new one that will show another centrality measure of a node: if it would be better to be a passage
node or a terminal node. Moreover, one last question that will be taken into account is how the
topology can improve the New Paths Algebra algorithm.