Algoritmos paralelos para sketches de cardinalidad y cuentas.

Abstract

El trabajo exploró el uso de algoritmos de streaming en el contexto de tráficos de red, estimándose la entropía de esta ya que es una medida que sirve para detectar ataques de red. Se implementaron algoritmos de streaming con sketches para la estimación de frecuencias y entropía de trazas de red, con el propósito de mejorar el tiempo de ejecución, el uso de memoria, y/o la precisión en la estimación. Se utilizan sketches ya que los streams de datos son muy grandes, y no es factible guardar en memoria la frecuencia de cada elemento del stream. La solución actual utiliza el sketch CountMin-CU junto a colas de prioridad de tamaño estático (que descartan los elementos menos frecuentes cuando la estructura esta llena y se inserta un nuevo elemento), para la estimación de frecuencias, junto al sketch HyperLogLog, para la estimación de la cardinalidad, para así en conjunto estimar la entropía. Se probó utilizar una modificación que extiende el algoritmo HyperLogLog, permitiendo calcular el histograma de frecuencias de una muestra del stream de datos, para estimar la entropía total y la contribución a la entropía de los elementos descartados por las colas de prioridad asociadas al sketch CountMin-CU. Se propuso también utilizar múltiples sketches CountMin-CU o TowerSketch-CU en conjunto con el sketch HyperLogLog para estimar la entropía. Nuestra implementación del sketch HyperLogLog fue modificada para reducir el uso de memoria en un 33 %. Se encontró que el algoritmo que extiende el sketch HyperLogLog guarda una muestra relativamente representativa del stream de datos, pero que la estimación de la entropía mediante el uso de esta muestra da malos resultados. Se encontró que no hay diferencias en la estimación de la entropía mediante el uso de uno o múltiples sketches CountMin-CU o TowerSketch-CU. Sin embargo, el uso de múltiples sketches CountMin-CU o TowerSketch-CU permite la lectura paralela de las trazas de red mediante OpenMP. Se probó también el algoritmo HyperLogLogLog, una modificación al algoritmo HyperLogLog que reduce el uso de memoria. Se encontró que no reduce el uso de memoria más que nuestra implementación del sketch Hyper-LogLog. Nuestros resultados indican que implementar el algoritmo utilizando múltiples sketches en una arquitectura con múltiples pipelines (equivalentes a hebras de CPU) reduciría el tiempo de ejecución.