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

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.

• Autores: Conrado Amaranto, Carlos Andrés; Acevedo Rodríguez, Pedro David
• Fecha de publicación: 2019
• Institución: Universidad del Norte
• Repositorio: Repositorio Uninorte
• Idioma: spa
• OAI Identifier: oai:manglar.uninorte.edu.co:10584/8776
• Acceso en línea: http://hdl.handle.net/10584/8776
• Palabra clave: Network Coding; Grafos Unicast; Máximo flujo; Problema multicast; DAG; Sumidero; Network Coding; Maximum flow; Multicast problem; Sink; DAG
• License: Universidad del Norte