Método para obtener los grafos unicast de máximo flujo con rutas disyuntas desde el nodo fuente hacia cada uno de los nodos sumideros en una red multicast que sirva a un sistema basado en network coding
Method for obtaining maximum flow unicast graphs with disjoints paths from the source node to each of the sink nodes in a multicast network that serves a network coding based system
Autor
Conrado Amaranto, Carlos Andrés
Acevedo Rodríguez, Pedro David
Fecha
2019-12-04Resumen
El objetivo principal de este proyecto es establecer una mejora en el tiempo de ejecución para uno de los componentes del algoritmo propuesto en la tesis doctoral “Códigos de Red Aplicados sobre Múltiples Flujos de Datos en Transmisión Multicast”. En el cual, se calcula los grafos unicast de máximo flujo individual de una red de comunicaciones con múltiples nodos sumideros y un solo nodo fuente. Lo que permite establecer, fundamentado en el paradigma de Network Coding, una solución al problema de Multicast para el reenvió y enrutamiento de paquetes dentro de una topología de red, con el fin de brindar una mejor calidad de servicio. Obteniendo una disminución de los tiempos de respuesta y aumentando la recepción de la información en el internet. Cabe recalcar, que el planteamiento de este proyecto está basado en una propuesta teórica, partiendo de una simulación de distribuciones de redes ideal, con canales de trasmisión que no presentan retardo ni ruido.
Teniendo en cuenta lo planteado anteriormente, y estableciendo como entrada todos los caminos posibles de un nodo fuente a cada uno de los nodos sumideros, se delimitó la solución propuesta, que se sintetiza en la construcción del arreglo denominado Matriz de adyacencia de caminos. En este se determina la frecuencia de las rutas posibles con el fin de identificar los caminos disyuntos, es decir, que no repitan nodos para poder determinar el máximo flujo individual mediante un algoritmo greedy propuesto.
Con respecto a las pruebas, se definió un algoritmo generador de DAG’s (Directed Acyclic Graph), el cual crea grafos aleatorios, para poder contar con un mayor número de datos para las comparaciones. En general, se probó con un total 1200 grafos, en los que se contempla una reducción al tiempo de ejecución en una tasa promedio del 20%, y hasta del 90% para algunos casos atípicos, en contraste al algoritmo previo o algoritmo por colisiones. The main objective of this project is to establish an improvement in the execution time for one of the components of the algorithm proposed in the doctoral thesis "Network Codes Applied on Multiple Data Flows in Multicast Transmission". In which the unicast graphs of maximum individual flow of a communications network with multiple sink nodes and a single source node are calculated. This allows establishing, based on the Network Coding paradigm, a solution to Multicast's problem for forwarding and routing packets within a network topology, in order to provide a better quality of service. Obtaining a decrease in response times and increasing the reception of information on the Internet. It should be noted that the approach of this project is based on a theoretical proposal, starting from a simulation of ideal network distributions, with transmission channels that have no delay or noise.
Taking into account the above, and establishing as input all possible paths from a source node to each of the sink nodes, the proposed solution was defined, which is synthesized in the construction of the arrangement called Matrix adjacency of roads. This determines the frequency of possible routes in order to identify dissected roads, i.e., that do not repeat nodes in order to determine the maximum individual flow by means of a proposed greedy algorithm.
With respect to the tests, an algorithm generating DAG's (Directed Acyclic Graph) was defined, which creates random graphs, in order to have a greater number of data for comparisons. In general, a total of 1200 graphs were tested, in which a reduction in execution time of an average rate of 20%, and up to 90% for some atypical cases, in contrast to the previous algorithm or algorithm of collisions.
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) -
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
Lozano Villalba, Camila; Angulo Madrid, Eduardo David (Barranquilla, Universidad del Norte, 2019, 2019-05-28)