Acelerador hardware para la estimación de entropía empírica mediante sketches.
Loading...
Date
2021
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Universidad de Concepción.
Abstract
Los enfoques basados en entropía para la detección de anomalías son atractivos, ya que propor cionan información más detallada que el análisis de volumen de tráfico tradicional. Sin embargo,
el cálculo de la entropía empírica exacta en un gran conjunto de datos puede ser costoso en uti lización de memoria, debido a que su cómputo requiere almacenar el número de ocurrencias de
todos los elementos distintos observados en el flujo. Un alto uso de memoria reduce el desem peño de los aceleradores hardware, que son necesarios para estimar la entropía en redes de alta
velocidad. Una solución práctica es, entonces, relajar la restricción de un cálculo exacto.
En este trabajo, presentamos dos métodos probabilísticos basados en sketches para aproximar
la entropía empírica de un gran conjunto de datos en procesamiento en tiempo real, con uso
de espacio de memoria sublineal. Los sketches son estructuras de datos que utilizan espacio
sublineal donde el uso de memoria crece de forma sublineal con los datos de entrada. Cuando
el tamaño de la memoria utilizada es menor que la entrada, la pérdida de precisión es inevi table y conduce a resultados probabilísticos. Sin embargo, los algoritmos basados en sketches
proporcionan aproximaciones con resultados de alta calidad. El primer enfoque consiste en es timar la entropía empírica de un flujo de datos, considerando los elementos top-K, o sea los
K elementos más frecuentes. El segundo y principal enfoque de nuestro trabajo, consiste en
aproximar la estimación de la entropía empírica no solo tomando la parte del flujo de datos que
corresponde a los K elementos más frecuentes, sino también tomando la parte del flujo de datos
que corresponde a los elementos menos frecuentes.
Los dos enfoques han sido implementados en un sistema en chip (System on chip, SoC) Zynq UltraScale de Xilinx. Para el primer enfoque, los resultados experimentales del diseño de hardwa re en una FPGA Xilinx Zynq UltraScale+MPSoC ZCU102 (Field Programmable Gate Array),
muestran que el sistema funciona a una frecuencia de reloj de 354 MHz y puede funcionar con
una velocidad de red de 181 Gigabits por segundo (Gbps). Para el segundo y principal enfoque,
los resultados experimentales en una arquitectura de propósito especial implementada en un
FPGA ZCU104 de ultraescala Xilinx Zynq, muestran que el sistema alcanza un rendimiento
de un paquete por ciclo a 400 MHz, lo que le permite operar a velocidades de red de hasta
204 Gbps.
Description
Tesis para optar al grado de Magíster en Ciencias de la Ingeniería con mención en Ingeniería Eléctrica.
Keywords
Entropía (Teoría de la Información), Algoritmos Computacionales