Estudi y análisi de VNE mitjançant tècniques de Path Algebra incloent paràmetres no linials i amb mètriques que permitin millorar els paràmetres de bondat (acceptance Ratio, cost, revenue i cost/revenue)

[ANGLÈS] 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.

[CASTELLÀ] 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.

[CATALÀ] La virtualització de xarxes presenta les característiques necessàries per convertir-se en el futur de l'arquitectura d'Internet en permetre el funcionament de múltiples xarxes virtuals compartides per una sola xarxa física/substrat. Aquestes xarxes virtuals són agrupades en diferents demandes, que vindrien a ser les demandes dels clients. A la vegada, aquestes consisteixen en una xarxa virtual amb unes certes demandes de recursos virtuals -bàsicament, capacitat de processament (CPU) i ample de banda (BW). Aquestes demandes han de ser acomplertes pels recursos de la xarxa física. El problema principal per a la virtualització de xarxes recau en el mapeig d'aquestes xarxes virtuals, l'anomenat virtual network embedding problem. Aquest procés (VNE) pot dividir-se en dues fases: el mapeig de nodes i el mapeig d'enllaços, encara que també és possible resoldre'l coordinadament en una sola fase. Un nou algoritme matemàtic d'enrutament anomenat paths algebra (o àlgebra de camins) és proposat per a la realització de la segona fase. Aquest algoritme permet múltiples restriccions i ja presenta bons resultats gràcies a la seva flexibilitat de funcionament i capacitat per incloure paràmetres lineals i no-lineals. Aquesta tesi suggereix una millora de l'estratègia basada en l'àlgebra de camins a partir del mapeig coordinat de nodes i enllaços. Aquesta estratègia proposa, per a la fase del mapeig de nodes, un rànquing fet a partir de parells de nodes bidireccionals de la xarxa substrat, ordenats per recursos disponibles en cada moment, anomenada New Paths Algebra. L'objectiu principal del New Paths Algebra serà oferir uns millors resultats dels obtinguts amb el paths algebra original, sense el mapeig coordinat de nodes i enllaços. Es faran simulacions per a ambdós algoritmes: la manera de procedir consistirà a fer les mateixes simulacions per als mateixos escenaris amb els dos algoritmes. Aquests escenaris seran prou grans, i la càrrega de les demandes de xarxes virtuals serà incrementada a poc a poc. Per tal d'aconseguir els objectius proposats, també s'estudiaran altres topologies per a xarxes substrat i les mètriques basades en la centralitat que es derivin d'elles. Utilitzant aquestes mètriques, es proposa crear una de nova que mostri si un node és més convenient de ser node de passatge o terminal (inici/final). Finalment, també serà tingut en compte com les condicions topològiques poden millorar l'algoritme del New Paths Algebra. Nota: Està prevista una publicació amb els resultats més destacables d'aquesta tesi. Per això, un primer borrador és adjuntat com a annex del treball.