Estimación de cuantiles en acelerador hardware usando sketch KLL±.
Loading...
Date
2025
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción
Abstract
El rápido crecimiento de Internet ha conllevado a un aumento en el volumen de datos que se generan, haciendo el monitoreo de tráfico un aspecto importante para la seguridad en redes. Una de las métricas que caracteriza el tráfico es el cálculo de cuantiles, la cual permite identificar pa trones y anomalías en la distribución de los datos. Sin embargo, las altas velocidades de las redes actuales, la necesidad de procesamiento de grandes volúmenes de datos en tiempo real, donde los datos más recientes son importantes para predecir el comportamiento de la red representa desafíos significativos. Ante tales desafíos, restringir el análisis a una ventana de observación permite re ducir la complejidad de las soluciones y priorizar el monitoreo de los datos más recientes. Esto motivo la implementación de un algoritmo de cálculo de cuantiles en un acelerador hardware ba sado en FPGA (Field Programmable Gate Array) que es capaz procesar un flujo de paquetes de forma continua, pero la memoria interna del acelerador limita la cantidad de datos que puede pro cesar. Frente a esta problemática, utilizar algoritmos basados en sketches, los cuales son estructuras probabilísticas las cuales utilizan un espacio de memoria reducida para estimar una propiedad con una cota de error, resulta en una solución atractiva.
Este trabajo presenta el diseño e implementación de un acelerador hardware basado en FPGA para la estimación de cuantiles, utilizando el algoritmo KLL± presentado por Zhao et al. [1], un sketch que admite tanto inserciones como eliminaciones, permitiendo se ajuste al comportamiento de una ventana deslizante. Se realizó la implementación de la arquitectura en una tarjeta de desa rrollo Alveo U280, obteniendo un uso de memoria de 0.6 kB (kilo bytes). Se validó el diseño con trazas de red reales (MAWILab y CAIDA), logrando un error de estimación menor al 0.1% y una frecuencia de operación de 219 MHz, equivalente a una tasa de 112 Gbps (Gigabits por segundo). Los resultados demuestran que el acelerador cumple con los requisitos de precisión ante el número de paquetes para el cual fue diseñado.
The rapid growth of the Internet has led to an increase in the volume of generated data, making traffic monitoring an important aspect of network security. One of the metrics used to characterize traffic is quantile computation, which helps identify patterns and anomalies in data distribution. However, the high speeds of modern networks and the need to process large volumes of data in real time—where the most recent data is crucial for predicting network behavior pose significant challenges. Given these challenges, restricting the analysis to an observation window helps reduce the complexity of solutions and prioritize monitoring the most recent data. This mo tivated the implementation of a quantile computation algorithm on an FPGA (Field-Programmable Gate Array)-based hardware accelerator capable of processing a continuous packet stream. How ever, the accelerator's internal memory limits the amount of data it can process. To address this issue, using sketch-based algorithms probabilistic structures that employ reduced memory space to estimate a property with a bounded error provides an attractive solution. This work presents the design and implementation of an FPGA-based hardware accelerator for quantile estimation, using the KLL± algorithm proposed by Zhao et al. [1], a sketch that sup ports both insertions and deletions, allowing it to adapt to a sliding window behavior. The archi tecture was implemented on an Alveo U280 development board, achieving a memory usage of 0.6 kB (kilobytes). The design was validated using real network traces (MAWILab and CAIDA), achieving an estimation error of less than 0.1% and an operating frequency of 219 MHz, equivalent to a throughput of 112 Gbps (Gigabits per second). The results demonstrate that the accelerator meets precision requirements for the intended number of packets.
The rapid growth of the Internet has led to an increase in the volume of generated data, making traffic monitoring an important aspect of network security. One of the metrics used to characterize traffic is quantile computation, which helps identify patterns and anomalies in data distribution. However, the high speeds of modern networks and the need to process large volumes of data in real time—where the most recent data is crucial for predicting network behavior pose significant challenges. Given these challenges, restricting the analysis to an observation window helps reduce the complexity of solutions and prioritize monitoring the most recent data. This mo tivated the implementation of a quantile computation algorithm on an FPGA (Field-Programmable Gate Array)-based hardware accelerator capable of processing a continuous packet stream. How ever, the accelerator's internal memory limits the amount of data it can process. To address this issue, using sketch-based algorithms probabilistic structures that employ reduced memory space to estimate a property with a bounded error provides an attractive solution. This work presents the design and implementation of an FPGA-based hardware accelerator for quantile estimation, using the KLL± algorithm proposed by Zhao et al. [1], a sketch that sup ports both insertions and deletions, allowing it to adapt to a sliding window behavior. The archi tecture was implemented on an Alveo U280 development board, achieving a memory usage of 0.6 kB (kilobytes). The design was validated using real network traces (MAWILab and CAIDA), achieving an estimation error of less than 0.1% and an operating frequency of 219 MHz, equivalent to a throughput of 112 Gbps (Gigabits per second). The results demonstrate that the accelerator meets precision requirements for the intended number of packets.
Description
Tesis presentada para optar al título de Ingeniero/a Civil Electrónico/a.
Keywords
Procesamiento de datos en línea, Algoritmos computacionales, Electrónica Equipos y accesorios