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