Optimización de la búsqueda de las rutas disyuntas desde un nodo fuente hacia el conjunto de nodos sumideros en una red multicast unisesión solucionable con Network Coding

Abstract

La finalidad de este proyecto es optimizar el algoritmo presentado en la tesis “Códigos de Red Aplicados sobre Múltiples Flujos de Datos en Transmisión Multicast” para el cálculo de las rutas disyuntas desde un nodo fuente hacia un conjunto de nodos sumideros; utilizando como entrada grafos de comunicaciones dirigidos, acíclicos, con capacidad de enlace máxima 1 y con un único nodo fuente desde el cual se enviarán los paquetes de red. Este algoritmo es el encargado de realizar el cálculo de los grafos unicast unisesión de flujo máximo, los cuales permiten reducir el tiempo de ejecución del programa y a su vez lograr una mejora en la calidad del servicio de internet prestado a los usuarios. Cabe destacar que este proyecto tiene como objetivo implementar algoritmos aptos en un ambiente teórico, no en un contexto real, dado que únicamente se realizarán simulaciones de distintas distribuciones de red en canales de transmisión ideales sin retardo ni ruido. La solución propuesta consta de 3 módulos: Programación dinámica para el cálculo de los nodos predecesores y sucesores de un nodo dado, utilizando una matriz construida con este propósito. Expansión de los caminos con base en lo calculado. Obtención de todos los caminos del nodo fuente a cada nodo sumidero. Al comparar los resultados obtenidos con el algoritmo previamente desarrollado y los obtenidos por el algoritmo propuesto notamos que la solución generada coincide. Además, se esperaba como resultado final observar una mejora en cuanto a la eficiencia del algoritmo; por lo tanto se realizaron las pruebas pertinentes para verificar la velocidad de ejecución en segundos de los módulos creados. Se evidenció que el algoritmo propuesto presenta una gran mejoría con relación al previamente desarrollado, siendo desde 3 veces hasta 78 veces más rápido para los distintos casos de prueba utilizados.

The purpose of this project is to optimize the algorithm presented in the thesis titled "Network Codes Applied over Multiple Data Flows in Multicast Transmission" for the calculation of the dissected routes from a source node to a set of sink nodes; using acyclic directed communications graphs as input, with a maximum link capacity of 1 and with a single source node from which network packets will be sent. This algorithm is in charge of calculating the unicast unisession maximum flow graphs, which allow the reduction of the program’s execution time and, at the same time, to achieve an improvement in the quality of the Internet service provided to users. It should be noted that this project aims to implement suitable algorithms in a theoretical environment, not in a real context, since only simulations of different network distributions will be made in ideal transmission channels without delay or noise. The proposed solution consists of 3 modules: Dynamic programming for the calculation of the predecessor and successor nodes of a given node, using a matrix built for this purpose. Expansion of paths based on the calculated ones. Obtaining all the paths from the source node to each sink node. When comparing the results obtained with the previously developed algorithm and those obtained by the proposed algorithm we notice that the solution generated coincides. In addition, the final result was expected to be an improvement in the efficiency of the algorithm; therefore the relevant tests were carried out to verify the execution speed in seconds of the created modules. It was evidenced that the proposed algorithm presents a great improvement in relation to the previously developed one, being from 3 times to 78 times faster for the different test cases used.