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
Optimization of the search of the dissected routes from a source node to the set of sink nodes in a solvable with Network Coding unisession multicast network
Autor
Lozano Villalba, Camila
Angulo Madrid, Eduardo David
Fecha
2019-05-28Resumen
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.
Colecciones a las que pertenece
Ítems relacionados
Mostrando ítems relacionados por Título, autor o materia.
-
Propuesta algorítmica de enrutamiento y configuración de paquetes en una red multicast de flujo máximo 2 usando Network Coding.
Soto Cobos, Yesid Fernando; Torres Chamorro, Néstor Alejandro (Barranquilla, Universidad del Norte, 2016, 2017-11-20) -
Propuesta algorítmica de enrutamiento y configuración de paquetes en una red multicast de flujo máximo 2 usando Network Coding.
Soto Cobos, Yesid Fernando; Torres Chamorro, Néstor Alejandro (Barranquilla, Universidad del Norte, 2016, 2016-11-17) -
Simulación en NS3 de una red multicasting con flujo máximo mayor o igual que 2 utilizando Network Coding con un número máximo de 6 paquetes
Valle Herrera, Sebastian; Falco Pastrana, Melanis (Barranquilla, Universidad del Norte, 2017, 2017-06-01)