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...

Full description

Autores:
Conrado Amaranto, Carlos Andrés
Acevedo Rodríguez, Pedro David
Tipo de recurso:
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
Rights
License
Universidad del Norte
Description
Summary: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.