Acelerador hardware para estimación de cuantiles en tráfico de redes.

Abstract

Las propiedades estadísticas del tráfico, tales como los cuantiles, entre los cuales se encuentran la mediana y el percentil 99, y la función de distribución acumulativa, nos ayudan a entender la distribución del tráfico y detectar anomalías a corto y largo plazo. Sin embargo, calcular de manera exacta el valor de estas propiedades es costoso en términos de espacio y tiempo. Particularmente, en el caso de los percentiles distintos de 0 y 100, es imposible encontrar una solución exacta en una pasada sin almacenar todos los datos. Utilizar un acelerador hardware basado en arreglos de lógica programable (FPGA, del inglés Field Programmable Gate Array) nos permite enfrentar la necesidad de procesar un stream de paquetes a alta velocidad y producir resultados con baja latencia. Sin embargo, la memoria interna disponible en estos dispositivos es limitada, por lo que almacenar todos los elementos no es una opción viable. Para responder a este problema, se han propuesto algoritmos basados en sketches: estructuras probabilísticas compactas que utilizan un espacio de memoria sublineal para estimar una propiedad con una cota de error predeterminada. Este trabajo presenta la arquitectura de un acelerador hardware para la estimación de cuantiles usando un algoritmo basado en sketches. La arquitectura propuesta se basa en la estructura general del sketch KLL presentado por Karnin et al. [1]. Implementamos la arquitectura en una tarjeta de desarrollo Xilinx Alveo U55C, la cual contiene un FPGA Virtex™ XCU55 UltraScale+, obteniendo un tiempo de ejecución total por lo menos 35 veces menor que el tiempo de ejecución total de la implementación en software del algoritmo modificado, y una aceleración mínima de 37 veces en cuanto al tiempo de inserción de elementos al sketch. El acelerador puede operar a una frecuencia de reloj de máxima 325.2 MHz, lo que equivale a una tasa mínima de 166 Gbps (gigabits por segundo). Mostramos empíricamente que las estimaciones mantienen una buena precisión, respetando las cotas de error cuando el número de paquetes de la traza es lo suficientemente parecido al número de elementos para el que dimensionamos el sketch.

Statistical properties of traffic, like quantiles (e.g. the median, the 99th percentile) and the cumulative distribution function (CDF), can help us better understand the distribution of network traffic and detect short-term and long-term anomalies. However, computing the exact value of these properties is expensive both in execution time and storing space. In particular, it is impossible to find the exact value of a percentile different from 0 and 100 in a one-pass fashion without storing the totality of incoming elements. Using a hardware accelerator based on Field Programmable Gate Arrays (FPGA) allows us to face the challenge of processing a stream of packets at high-speed while producing results with low latency. Nevertheless, the internal memory available in these devices is highly limited, so storing all elements is not feasible. To respond to this problem, numerous algorithms using sketches (compact probabilistic data structures with sublineal memory usage that allow us to estimate the value of a property with a pre-determined error bound) have been proposed. This work presents the architecture of a hardware accelerator for quantile estimation using a sketch-based algorithm. The proposed architecture is inspired by the general structure of the KLL sketch presented by Karnin et al. [1]. We implement this architecture on a Xilinx Alveo U55C board, which features a Virtex™ XCU55 UltraScale+ FPGA, obtaining a total execution time at least 35 times shorter than the total execution time of the software implementation of the modified algorithm. Also, we obtain a minimal speed up of 37 times in element insertion time. The accelerator can opérate at a maximum clock frequency of 325.2 MHz, which translates to a minimal line-rate of 166 Gbps (gigabits per second). We show empirically that the estimations maintain a good precision, staying within the error bounds when the number of packets of the trace is sufficiently close to the number of packets used to calculate the parameters of the sketch.