Algoritmos y aceleradores hardware para estimación de entropía de flujos en redes de datos.
| dc.contributor.advisor | Figueroa Toro, Miguel Ernesto | es |
| dc.contributor.advisor | Hernández Rivas, Cecilia | es |
| dc.contributor.author | Fernández Jiménez, Yaime | es |
| dc.date.accessioned | 2025-09-15T13:55:19Z | |
| dc.date.available | 2025-09-15T13:55:19Z | |
| dc.date.issued | 2025 | |
| dc.description | Tesis presentada para optar al grado de Doctor/a en Ciencias de la Ingeniería con mención en Ingeniería Eléctrica. | es |
| dc.description.abstract | La entropía empírica de Shannon se emplea en la monitorización y clasificación del tráfico de red, con aplicaciones en la detección de anomalías y la gestión de recursos. En enlaces de red modernos, el cálculo de la entropía debe considerar que los datos se generan en streaming, de forma continua a altas velocidades. Además, en muchas aplicaciones los datos recientes adquieren mayor relevancia. Por ello, se utiliza el modelo de ventana deslizante que mantiene actualizadas las mediciones y refleja tendencias actuales del tráfico, pero implica el desafío adicional de eliminar de forma continua los datos obsoletos. Los aceleradores hardware basados en FPGA pueden alcanzar un alto rendimiento en estos escenarios a altas velocidades, explotando el paralelismo inherente del algoritmo con baja latencia y consumo energético. Sin embargo, estas plataformas tienen recursos de memoria interna limitados. Por lo que se requiere el diseño de algoritmos de estimación de entropía que puedan ser mapeados eficientemente a arquitecturas hardware, con bajo uso de memoria y alto paralelismo para maximizar su rendimiento. En este trabajo se proponen dos algoritmos para estimar la entropía empírica de Shannon de flujos de red, utilizando las frecuencias de los top-K, y asumiendo una distribución estadística para el resto. El primero realiza la estimación en intervalos de tiempo discreto y el segundo en ventanas de tiempo deslizantes. Ambos algoritmos fueron implementados en hardware utilizando sketches para la estimación de frecuencias y cardinalidad. Los sketches son estructuras de datos probabilísticas que implementan algoritmos de streaming que permiten operaciones en línea, ofrecen un alto grado de paralelismo y hacen un uso eficiente del espacio disponible. Además, se implementaron arreglos de colas de prioridad aproximadas para almacenar los flujos de mayor frecuencia; estas estructuras son altamente paralelizables y eficientes en el uso de memoria. Ambos algoritmos se evaluaron en trazas de red reales. El primer algoritmo muestra en intervalos con hasta 50 millones de flujos, un error relativo promedio de 0,69% en la estimación de la entropía empírica. El algoritmo utiliza más de tres órdenes de magnitud menos de memoria que un método exacto de cálculo de entropía. El acelerador hardware implementado en un FPGA Virtex UltraScale+ XCU280 opera a una velocidad de línea de más de 200 Gbps y una latencia de estimación de 16 μs. Los resultados del segundo algoritmo, en ventanas de 60s y deslizamiento 6s, con hasta 2 millones de flujos por ventana, muestran errores relativos promedio menores al 0.45% con una desviación estándar de 0.14 %. El algoritmo utiliza la mitad de la memoria y alcanza errores menores que replicar el primer algoritmo en cada ventana. El acelerador hardware implementado en un FPGA Virtex XCU55 UltraScale+ opera a una velocidad de línea de más de 158 Gbps. | es |
| dc.description.campus | Concepción | es |
| dc.description.departamento | Departamento de Ingeniería Eléctrica | es |
| dc.description.facultad | Facultad de Ingeniería | es |
| dc.description.sponsorship | ANID, Beca de Doctorado Nacional N°21191612 | es |
| dc.description.sponsorship | ANID, Proyecto N°1220960, "Hardware accelerator for network traffic monitoring on the data plane." | en |
| dc.description.sponsorship | ANID, Proyecto N°11240971, "Scalable sketch-based algorithms for comparative genomics." | en |
| dc.identifier.doi | https://doi.org/10.29393/TDUdeC-55FY1AA55 | |
| dc.identifier.uri | https://repositorio.udec.cl/handle/11594/13068 | |
| dc.language.iso | es | es |
| dc.publisher | Universidad de Concepción | es |
| dc.rights | CC BY-NC-ND 4.0 DEED Attribution-NonCommercial-NoDerivs 4.0 International | en |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/4.0/ | |
| dc.subject | Algoritmos | es |
| dc.subject | Hardware de computadores | es |
| dc.subject | Entropía (Teoría de la información) | es |
| dc.subject | Procesamiento de datos | es |
| dc.subject.ods | INDUSTRIA, innovación, infraestructura | es |
| dc.title | Algoritmos y aceleradores hardware para estimación de entropía de flujos en redes de datos. | es |
| dc.type | Thesis | en |