Algoritmo y acelerador hardware para la estimación de cuantiles en propiedades de flujos de red.
Loading...
Date
2025
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción
Abstract
La medición y análisis del tráfico de datos es fundamental para la gestión y seguridad de redes de datos, ya que nos permite detectar e identificar elementos o eventos que no coinciden con el comportamiento típico, llamados anomalías. Estas anomalías nos ayudan a detectar posibles fallas o ataques. Una red de datos puede ser modelada por conexiones entre dos puntos llamadas flujos. Al analizar la distribución de ciertas propiedades de estos flujos, tales como el número de paquetes (denominado como frecuencia en la literatura) o la cantidad de bytes útiles enviados (payload), podemos detectar anomalías en el corto y largo plazo. Estas distribuciones pueden ser caracterizadas usando cuantiles, donde el cuantil de un elemento es la fracción de elementos del conjunto que son menores o iguales a este. No obstante, para poder tomar acciones correctivas oportunamente, el análisis de esta distribución debe realizarse de manera rápida y en línea. Dado los grandes volúmenes de tráfico y la velocidad de los enlaces modernos, esto es costoso computacionalmente, por lo que un procesador de propósito general es insuficiente para abordar el problema y utilizar aceleradores hardware se vuelve una opción atractiva. Sin embargo, estos dispositivos poseen una cantidad de memoria interna reducida, lo que hace imposible calcular en línea el valor exacto de estos cuantiles para trazas de tamaño típico en redes de alta velocidad, ya que implica almacenar las frecuencias para cada flujo. Como una forma de abordar este problema, se han propuesto estructuras de datos probabilísticas, llamadas sketches, que permiten estimar propiedades de grandes volúmenes de datos, tales como los cuantiles, con una eficiencia espacial alta. Sin embargo, dado que ciertas propiedades de los flujos, tales como la frecuencia, se acumulan a través de múltiples paquetes, éstas deben actualizarse en el sketch cada vez que llega un nuevo paquete. Los algoritmos que permiten trabajar con este modelo asumen un universo (el rango al que pueden pertenecer los elementos insertados) fijo y el espacio utilizado depende del tamaño de este universo, por lo que utilizarlos se vuelve poco conveniente. Por otra parte, se puede utilizar un sketch de estimación de frecuencia que permita acumular el número de paquetes por flujo y realizar el análisis de cuantiles sobre esta información. No obstante, estimar la frecuencia de todos los flujos mediante este sketch no es compatible con las restricciones de memoria ya que requeriría almacenar el identificador de cada flujo en la traza.
En trabajos recientes, se ha demostrado que, almacenando únicamente la frecuencia de los flujos más grandes, es posible aproximar la distribución de la frecuencia del resto de los flujos mediante suposiciones respecto a su distribución estadística [1]. En este trabajo, proponemos un algoritmo de estimación de cuantiles que combina un sketch de estimación de frecuencia junto con otras estructuras de datos para estimar la frecuencia de los flujos más grandes. Usando estas frecuencias, estimamos los parámetros de una distribución estadística de tipo power-law que describe la frecuencia del resto de los flujos. Usando esta aproximación y las frecuencias reales de los top-𝐾, se responden dos tipos de consultas de cuantiles: (i) Dado un valor de cuantil, determinar la frecuencia que se encuentra en ese cuantil. (ii) Dada una frecuencia, encontrar el cuantil en el que ésta se encuentra. Adicionalmente, presentamos la arquitectura de un acelerador hardware que implementa este algoritmo sobre un dispositivo FPGA.
El algoritmo propuesto responde consultas sobre 9 trazas de CAIDA [2] con un error absoluto promedio entre 0.0004% y 0.0122% para consultas de cuantil dado un valor de frecuencia y un error absoluto promedio entre 0.43 y 2.09 cuentas para consultas de frecuencia dado un valor de cuantil. La arquitectura propuesta fue implementada en un FPGA AMD XCU280 UltraScale+, alcanzando una frecuencia máxima de 392MHz en el procesamiento de paquetes. El acelerador puede recibir un nuevo paquete en cada ciclo de reloj, soportando una tasa de recepción de peor caso de 200Gbps. Por otro lado, la latencia máxima de consulta es de 38.5 𝜇𝑠 para consultas de frecuencia dado un valor de cuantil y 4.2 𝜇𝑠 para consultas de cuantil dado un valor de frecuencia.
Description
Tesis presentada para optar al grado de Magíster en Ciencias de la Ingeniería con mención en Ingeniería Eléctrica.
Keywords
Procesamiento de datos, Redes de computadores, Algoritmos computacionales