Detección y medida en tiempo real de flujos de elementos frecuentes en grandes poblaciones,

escalable y sintonizable.Un "método" para la detección y medida de elementos frecuentes (que aparecen más veces que un determinado umbral en una población de elementos potencialmente muy grande, como pueden ser "registros" en una base de datos, o "paquetes" en redes de conmutación de paquetes. El método combina muestreo y el uso de funciones resumen (hash). Permite la detección de elementos frecuentes con alta probabilidad, en tiempo real, con tiempo de proceso reducido y determinista y con bajos requerimientos de memoria. En particular, requiere un número de contadores inferior e independiente al número de elementos distintos presentes en la población. Estas características permiten su aplicación en entornos de bases de datos y en redes de alta velocidad donde es interesante detectar y medir grandes flujos de tráfico en tiempo real

Detección y medida en tiempo real de flujos de elementos frecuentes en grandes poblaciones, escalable y sintonizable.

Sector de la técnica

De manera general, esta invención se encuadra en el ámbito del análisis de grandes volúmenes de datos. Por ejemplo, en el contexto de bases de datos, donde suele interesar identificar aquellos elementos (registros) que aparecen con más frecuencia que un determinado umbral, ya sea en términos absolutos (p.e. que aparecen más de T veces) o que una cierta fracción del total (p.e. que constituyen más de un porcentaje z del total).

Se encuadra también en el contexto de redes de datos de alta velocidad, donde suele ser conveniente, para su gestión y monitorización, la medida del tráfico "por flujos". El descubrimiento de dichos flujos, así como su medida es útil para aplicaciones como balanceo de carga, ingeniería de tráfico o tarificación. Sin embargo, la medida de todos los flujos presentes en un enlace es hoy en día costosa debido al potencialmente elevado número de flujos. Por este motivo suele interesar detectar o descubrir aquellos flujos (entendidos como grupos de paquetes con alguna característica en común) cuyo tamaño exceda un determinado umbral.

De manera general, la presente invención es aplicable en cualquier ámbito donde, de una población elevada de elementos, pueda interesar descubrir y medir/contar aquellos elementos que aparecen más veces que un determinado umbral.

Estado de la técnica

La medida del tráfico "por flujos" proporciona un compromiso razonable entre la cantidad de datos a adquirir/analizar/almacenar y el nivel de información obtenido. Se entiende por flujo un conjunto de elementos, en este caso paquetes, con alguna característica en común. La medida por flujos consiste en identificar y medir dichos conjuntos o flujos, reportando las características que los identifican y su tamaño. Qué características deben tener en común los paquetes para ser considerados del mismo flujo es lo que se denomina "definición de flujo" y es totalmente flexible. Por ejemplo, puede definirse un flujo como todos los paquetes que utilizan el mismo protocolo de transporte y van destinados a la misma dirección (p.e. dirección IP).

Dada una definición de flujo, cada flujo queda identificado por los valores que en éste toman las propiedades especificadas en la definición. Por ejemplo, para la definición de flujo anterior, todos los paquetes destinados a la dirección IP 192.1.4.5 que utilizan el protocolo TCP, formarían un flujo cuyo identificador de flujo (FID) seria el (192.1.4.5, TCP).

Para identificar y medir los distintos flujos existentes en un enlace (en un intervalo de tiempo determinado), la solución directa del problema consiste en examinar cada uno de los paquetes, descubrir a qué flujo pertenecen (su identificador) y contar la cantidad de bytes de cada flujo como la suma de los tamaños de los paquetes observados. Esta solución requiere mantener tantos contadores como flujos haya.

En redes de alta velocidad, esta solución es poco escalable, compleja y cara por los siguientes motivos:

1. Un método para detectar y medir flujos de elementos frecuentes en grandes poblaciones de elementos (donde por flujo se entiende una colección de elementos que tienen ciertas características en común) que comprende las cuatro etapas siguientes:

(a) muestrear elementos mediante un bloque (B1) de muestreo que: 1) selecciona cada uno de los elementos de la población a estudiar con una probabilidad p; y 2) no procesa los elementos no seleccionados;

(b) almacenar en un buffer información sobre los elementos muestreados. Dicha información (S_h) está compuesta por el identificador del flujo (FID) al que pertenecen los elementos, el número de muestras tomadas y una marca temporal de tiempo de llegada de la información (t_stamp);

(c) leer la información del buffer mediante un bloque (B2), que extrae los S_h del buffer y comprueba si existe, en la lista de entradas (E2), alguna cuyo identificador FID coincida con aquél contenido en el S_h que se ha extraído. Cada elemento de la lista de entradas (E2) contiene el identificador de un flujo (FID), un contador y dos marcas temporales (una indicando el tiempo de generación de entrada para el flujo, y otra el último instante de su actualización);

(d) procesar la información del buffer mediante un bloque (E1) compuesto por m vectores de b contadores cada uno (m*b posiciones que denominamos c_xy, donde x indica un vector e y un contador de dicho vector). Esta etapa se caracteriza por:

- en el caso de que exista una entrada (en la etapa (c)) con idéntico identificador al indicado en el S_h, actualizar dicha entrada (incrementando su contador y guardando la segunda marca temporal, a parir de la información contenida en el S_h).

- si no existe ninguna entrada en la etapa (c) con identificador igual al del S_h:

1) aplicar m funciones resumen al FID indicado en el S_h (bloque B3), y utilizar los m valores o números resultantes (h₁ (FID), ... h_m (FID), comprendidos entre 1 y b) para seleccionar un contador en cada uno de los m vectores del siguiente modo: el valor 1≤qh₁(FID)≤qb se usará como Indice para seleccionar uno de los b contadores del vector 1; el valor 1≤qh₂(FID)≤qb se usará como Indice para seleccionar uno de los b contadores del vector 2; y así con los m valores obtenidos.

2) calcular el mínimo de los contadores seleccionados por dichos índices, c_min (bloque B4).

3) si la suma de c_min y el valor numérico contenido en el S_h es igual o superior a un umbral d, crear una entrada en la lista de entradas con FID igual al del S_h (etapa (c)). De lo contrario, actualizar los contadores seleccionados en función del valor de c_min y del valor numérico contenido en el S_h.

2. Un método según la reivindicación 1 caracterizado porque la probabilidad mencionada en la etapa (a) se calcula como el cociente entre un umbral de muestras d y un umbral de t amaño de flujo V_c (es decir p=d/V_c) donde V_c es inferior o igual al volumen a partir del cual un flujo se considera como grande.

3. Un método según la reivindicación 1 caracterizado porque, si elementos del mismo flujo (con el mismo FID) llegan agrupados a la etapa (a):

a) puede determinar qué elementos del grupo serán seleccionados en lugar de procesar cada uno de ellos por separado.

b) puede procesar los elementos seleccionados como uno único, almacenando su FID, el número de elementos seleccionados y el t_stamp en un único elemento de síntesis S_h.

c) y porque no requiere almacenar los elementos muestreados una vez que el elemento de síntesis S_h ha sido creado.

4. Un método según la reivindicación 1 caracterizado porque, en la etapa (b), la información de los elementos muestreados y que es sintetizada en un S_h puede almacenarse en un buffer o bien ser descartada, en el caso en que dicho buffer esté lleno.