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
id REPOUNORT2_96513b0aa9cd11cb12ed967e3525f2f1
oai_identifier_str oai:manglar.uninorte.edu.co:10584/8453
network_acronym_str REPOUNORT2
network_name_str Repositorio Uninorte
repository_id_str
dc.title.es_ES.fl_str_mv 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
dc.title.en_US.fl_str_mv 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
title 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
spellingShingle 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
Network Coding
Multicast
Máximo Flujo
Programación Dinámica
Network Coding
Multicast
Max Flow
Dynamic Programming
title_short 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
title_full 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
title_fullStr 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
title_full_unstemmed 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
title_sort 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
dc.creator.fl_str_mv Lozano Villalba, Camila
Angulo Madrid, Eduardo David
dc.contributor.advisor.none.fl_str_mv Márquez Díaz, Jose Duvan
dc.contributor.author.none.fl_str_mv Lozano Villalba, Camila
Angulo Madrid, Eduardo David
dc.subject.es_ES.fl_str_mv Network Coding
Multicast
Máximo Flujo
Programación Dinámica
topic Network Coding
Multicast
Máximo Flujo
Programación Dinámica
Network Coding
Multicast
Max Flow
Dynamic Programming
dc.subject.en_US.fl_str_mv Network Coding
Multicast
Max Flow
Dynamic Programming
description 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.
publishDate 2019
dc.date.accessioned.none.fl_str_mv 2019-05-30T17:41:20Z
dc.date.available.none.fl_str_mv 2019-05-30T17:41:20Z
dc.date.issued.none.fl_str_mv 2019-05-28
dc.type.es_ES.fl_str_mv article
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_6501
dc.identifier.uri.none.fl_str_mv http://hdl.handle.net/10584/8453
url http://hdl.handle.net/10584/8453
dc.language.iso.es_ES.fl_str_mv spa
language spa
dc.rights.es_ES.fl_str_mv Universidad del Norte
dc.rights.coar.fl_str_mv http://purl.org/coar/access_right/c_abf2
rights_invalid_str_mv Universidad del Norte
http://purl.org/coar/access_right/c_abf2
dc.publisher.es_ES.fl_str_mv Barranquilla, Universidad del Norte, 2019
institution Universidad del Norte
bitstream.url.fl_str_mv http://172.16.14.36:8080/bitstream/10584/8453/1/Diagrama%20de%20Soluci%c3%b3n%20PF%20-%20Espa%c3%b1ol.png
http://172.16.14.36:8080/bitstream/10584/8453/2/Diagrama%20de%20Soluci%c3%b3n%20PF%20-%20Ingl%c3%a9s.png
http://172.16.14.36:8080/bitstream/10584/8453/3/Diagrama%20de%20Soluci%c3%b3n%20PF%20-%20Espa%c3%b1ol.pdf
http://172.16.14.36:8080/bitstream/10584/8453/4/Diagrama%20de%20Soluci%c3%b3n%20PF%20-%20Ingl%c3%a9s.pdf
http://172.16.14.36:8080/bitstream/10584/8453/5/license.txt
bitstream.checksum.fl_str_mv 133d07fe76d04e0b211c9845bd9aeb8d
4be8258f2c1cbd4cfafb5a647d9e201a
35d3e3b44e0abd0ddb12f208244a62bc
133466613729408e625bf3316ca0df9e
8a4605be74aa9ea9d79846c1fba20a33
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
MD5
MD5
MD5
repository.name.fl_str_mv Repositorio Digital de la Universidad del Norte
repository.mail.fl_str_mv mauribe@uninorte.edu.co
_version_ 1812183107709698048
spelling Márquez Díaz, Jose DuvanLozano Villalba, CamilaAngulo Madrid, Eduardo David2019-05-30T17:41:20Z2019-05-30T17:41:20Z2019-05-28http://hdl.handle.net/10584/8453La 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.spaBarranquilla, Universidad del Norte, 2019Universidad del Nortehttp://purl.org/coar/access_right/c_abf2Network CodingMulticastMáximo FlujoProgramación DinámicaNetwork CodingMulticastMax FlowDynamic ProgrammingOptimizació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 CodingOptimization 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 networkarticlehttp://purl.org/coar/resource_type/c_6501ORIGINALDiagrama de Solución PF - Español.pngDiagrama de Solución PF - Español.pngDiagrama de la solución en españolimage/png194825http://172.16.14.36:8080/bitstream/10584/8453/1/Diagrama%20de%20Soluci%c3%b3n%20PF%20-%20Espa%c3%b1ol.png133d07fe76d04e0b211c9845bd9aeb8dMD51Diagrama de Solución PF - Inglés.pngDiagrama de Solución PF - Inglés.pngSolution Diagram in Englishimage/png168680http://172.16.14.36:8080/bitstream/10584/8453/2/Diagrama%20de%20Soluci%c3%b3n%20PF%20-%20Ingl%c3%a9s.png4be8258f2c1cbd4cfafb5a647d9e201aMD52Diagrama de Solución PF - Español.pdfDiagrama de Solución PF - Español.pdfDiagrama de la solución en españolapplication/pdf168166http://172.16.14.36:8080/bitstream/10584/8453/3/Diagrama%20de%20Soluci%c3%b3n%20PF%20-%20Espa%c3%b1ol.pdf35d3e3b44e0abd0ddb12f208244a62bcMD53Diagrama de Solución PF - Inglés.pdfDiagrama de Solución PF - Inglés.pdfSolution Diagram in Englishapplication/pdf188631http://172.16.14.36:8080/bitstream/10584/8453/4/Diagrama%20de%20Soluci%c3%b3n%20PF%20-%20Ingl%c3%a9s.pdf133466613729408e625bf3316ca0df9eMD54LICENSElicense.txtlicense.txttext/plain; charset=utf-81748http://172.16.14.36:8080/bitstream/10584/8453/5/license.txt8a4605be74aa9ea9d79846c1fba20a33MD5510584/8453oai:172.16.14.36:10584/84532019-05-30 12:41:20.449Repositorio Digital de la Universidad del Nortemauribe@uninorte.edu.co