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

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

Full description

Autores:
Lozano Villalba, Camila
Angulo Madrid, Eduardo 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/8453
Acceso en línea:
http://hdl.handle.net/10584/8453
Palabra clave:
Network Coding
Multicast
Máximo Flujo
Programación Dinámica
Network Coding
Multicast
Max Flow
Dynamic Programming
Rights
License
Universidad del Norte
Description
Summary: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.