[en] 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 multi-constraint 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. Note: It is planned a publication with the most important results of this thesis. Because of this, a first draft is attached as an annex of the work.

[es] La virtualización de redes presenta las características necesarias para convertirse en el futuro de la arquitectura de Internet, al permitir el funcionamiento de múltiples redes virtuales compartidas por una sola red física/sustrato. Estas redes virtuales son agrupadas en diferentes demandas, que vendrían a ser las demandas de los clientes. A su vez, éstas consisten en una red virtual con unas ciertas demandas de recursos virtuales -básicamente, capacidad de procesamiento (CPU) y ancho de banda (BW). Estas demandas tienen que ser cumplidas por los recursos de la red física. El problema principal para la virtualización de redes recae en el mapeo de estas redes virtuales, el llamado virtual network embedding problem. Este proceso (VNE) puede dividirse en dos fases: el mapeo de nodos y el mapeo de enlaces, aunque también es posible resolverlo coordinadamente en una sola fase. Un nuevo algoritmo matemático de enrutamiento llamado paths algebra (o álgebra de caminos) es propuesto para la realización de la segunda fase. Este algoritmo permite múltiples restricciones y ya presenta buenos resultados gracias a su flexibilidad de funcionamiento y capacidad para incluir parámetros lineales y no-lineales. Esta tesis sugiere una mejora de la estrategia basada en el álgebra de caminos a partir del mapeo coordinado de nodos y enlaces. Esta estrategia propone, para la fase del mapeo de nodos, una clasificación hecho a partir de pares de nodos bidireccionales de la red de sustrato ordenados por recursos disponibles en cada momento, llamada New Paths Algebra. El objetivo principal del New Paths Algebra será ofrecer unos mejores resultados de los obtenidos con el paths algebra original, sin el mapeo coordinado de nodos y enlaces. Se harán simulaciones para los dos algoritmos: la manera de proceder consistirá en correr las mismas simulaciones para los mismos escenarios con los dos algoritmos. Estos escenarios serán suficientemente grandes, y la carga de las demandas de redes virtuales será incrementada poco a poco. A fin de conseguir los objetivos propuestos, también se estudiarián otras topologías para redes sustrato y las métricas que se deriven de ellas. Utilizando estas métricas, se propone crear una nueva que muestre si un nodo es más conveniente de actuar como nodo de pasaje o como terminal (inicio/final). Finalmente, también será tenido en cuenta cómo las condiciones topológicas pueden mejorar el algoritmo del New Paths Algebra. Nota: Está prevista una publicación con los resultados más destacables de esta tesis. Debido a esto, un primer borrador es adjuntado como anexo del trabajo.