ALGORITMO DE EMPAREJAMIENTO DE PREFIJO.

Un dispositivo (100) para el emparejamiento de una corriente de entrada (101) respecto a signaturas predefinidas,

que comprende: una tabla (105) de búsqueda para almacenar información de prefijo de las signaturas predefinidas en una pluralidad de entradas de tabla; un circuito lógico (103) acoplado a la tabla (105) de búsqueda para acceder a un número predeterminado de entradas en la tabla de búsqueda de acuerdo con una porción de la corriente de entrada; caracterizado por: una memoria intermedia (107) de entrada de tabla acoplada al circuito lógico (103) para almacenar valores temporales de entrada de tabla del número predeterminado de entradas de tabla, en el que cada valor temporal de entrada de tabla contiene bits de posición y bits de longitud, estando los bits de longitud capacitados para determinar los valores de entrada de tabla asociados a la determinación de emparejamiento posible, y siendo un bit de posición predeterminado de cada valor temporal asociado de entrada de tabla comprobado para realizar una determinación de emparejamiento posible

Algoritmo de emparejamiento de prefijo.

CAMPO DE LA INVENCIÓN La presente invención se refiere a estructuras y sistemas de redes informáticas, y en particular a operaciones de emparejamiento de patrones que utilizan un algoritmo de emparejamiento de prefijo implementado en aplicaciones de procesamiento en red que necesitan emparejamiento de contenido o filtraje de contenido.

ANTECEDENTES DE LA INVENCIÓN Los sistemas informáticos operan actualmente en un entorno de conectividad casi ubicua si están vinculados a Internet y a redes, o si están conectados por medio de tecnología inalámbrica. Mientras que la disponibilidad de siempre en comunicación ha creado incontables nuevas oportunidades para compartir negocios e información basados en webs, también se ha producido un incremento en la frecuencia de los intentos de infracción de la seguridad de la red, o ataques de hackers, realizados para acceder a la información confidencial o interferir de otro modo con las comunicaciones en la red.

Dada la importancia de proteger la información y los servicios, existe una gran cantidad de trabajo de la colectividad de seguridad. Recientemente, ha surgido una cantidad de aplicaciones dirigidas a detectar y frustrar los ataques en la red, incluyendo antivirus de filtraje de contenidos, cortafuegos, detección/prevención de intrusión y protección de red. En el centro de la casi totalidad de los modernos sistemas de seguridad en red se encuentra un algoritmo de emparejamiento de patrones, donde un patrón incluye una cadena de contenido de signatura que se ha de emparejar. En la operación de emparejamiento de patrones, el tráfico en paquetes que pasa se compara con una librería que contiene patrones almacenados de tráfico de paquetes sospechosos, amenazantes o peligrosos. En caso de que encuentre un emparejamiento entre un tráfico de paquetes seleccionado y una entrada patrón de la librería, se puede emitir una alerta o alarma, y además el tráfico de paquetes de emparejamiento puede ser capturado antes de que se produzca algún daño. Además de la implementación en aplicaciones de seguridad de red, el emparejamiento de patrones se utiliza también en enrutamiento de protocolo de Internet (IP) donde cada paquete que atraviesa el enrutador es recuperado para hallar el destino de IP.

Desafortunadamente, comprobar cada byte de cada tráfico de paquetes para ver si se empareja con alguno de un conjunto de diez mil patrones requiere importantes recursos de procesamiento, tanto en términos de cantidad de tiempo para procesar un paquete, como de cantidad de memoria necesaria. Adicionalmente, debido a que la tasa de flujo de paquetes se ha incrementado con el tiempo, el emparejamiento de patrones debe operar a una velocidad de un gigabit por segundo (Gbps) con el fin de no restringir el caudal de paquetes. Para direccionar estas cuestiones, el motor de emparejamiento de cadena de signatura está diseñado de modo que incluye un motor de emparejamiento de prefijos y un motor de emparejamiento exacto. El motor de emparejamiento de prefijos examina el prefijo del paquete de tráfico frente a una tabla de búsqueda de prefijo precompilada, y actúa como preprocesador para filtrar la mayor parte de los tráficos de paquetes. Solamente aquellos tráficos de paquetes en los que se encuentra que sus prefijos se emparejan con un prefijo predefinido en la tabla de búsqueda de prefijo, son inspeccionados adicionalmente en el motor de emparejamiento exacto. Puesto que el motor de emparejamiento exacto se pone en marcha raramente, el caudal global de paquetes ha aumentado considerablemente.

Aunque el algoritmo de emparejamiento de prefijo proporciona una solución para mejorar el rendimiento, la actual tecnología de emparejamiento de prefijos no puede aún ofrecer un comportamiento, un rendimiento, una escalabilidad y una flexibilidad satisfactorios. Por ejemplo, el emparejamiento de prefijo simple comprueba el prefijo de un paquete de tráfico frente a todos los prefijos almacenados en la tabla de búsqueda de prefijo. Cuando el número de cadenas de signatura alcanza varios miles, el comportamiento del emparejamiento de prefijo simple se degradará significativamente debido a la enorme cantidad de tiempo de procesamiento y afectará negativamente al rendimiento. También, cuando la longitud de la signatura más corta es relativamente pequeña, el emparejamiento de prefijo simple demostrará un incremento de falsos positivos y en consecuencia el motor de emparejamiento exacto se pondrá en marcha frecuentemente. Como resultado, el motor de emparejamiento de prefijo falla en cuanto a contribuir a un aumento del rendimiento.

La solicitud internacional WO 2005/017708 A2 se refiere a un método y un aparato basados en filtros de Bloom para detectar signaturas predefinidas en la carga útil de un paquete de red. El aparato comprende un motor de emparejamiento de prefijo para almacenar información de prefijos de las signaturas predefinidas en una pluralidad de entradas de tabla de una tabla de búsqueda, buscar un número predeterminado de entradas de tabla para encontrar un emparejamiento posible de la corriente de entrada respecto a las signaturas predefinidas, y un motor de emparejamiento exacto acoplado al motor de emparejamiento de prefijo para recopilar la información de prefijo asociada al emparejamiento posible y realizar una determinación de emparejamiento exacto en base a la información de prefijo recopilada. El artículo “Emparejamiento de Patrón de Paquete de una Tasa de Gigabit Utilizando TCAM”, Fang Yu et al., Procedimientos de la 12ª Conferencia Internacional IEEE de Protocolos de Red (ICNP04) , 5 de Octubre de 2004, se refiere a un método para emparejar una corriente de entrada respecto a

signaturas predefinidas que comprende almacenar información de prefijo de las signaturas predefinidas en una pluralidad de entradas de tabla de una tabla de búsqueda, acceder a un número predeterminado de entradas de tabla de acuerdo con una porción de la corriente de entrada, y realizar un determinación de emparejamiento posible en base a los valores de entrada de tabla en una Memoria Direccionable de Contenido Ternario (TCAM) . El método divulgado se basa en la capacidad de la TCAM para almacenar uno de tres estados.

SUMARIO DE LA INVENCIÓN Por consiguiente, la presente invención proporciona un algoritmo de emparejamiento de prefijo que hace que la determinación de emparejamiento de prefijo sea más efectiva y eficiente. Un ejemplo de motor de emparejamiento de prefijo comprende una tabla de búsqueda, un circuito lógico y una memoria intermedia de entrada de tabla. La tabla de búsqueda almacena información de prefijo de signaturas predefinidas. El circuito lógico está acoplado a la tabla de búsqueda para acceder a un número predeterminado de entradas de tabla de la tabla de búsqueda de acuerdo con una porción de una corriente de entrada. La memoria intermedia de entrada de tabla está acoplada al circuito lógico para almacenar valores de entrada de tabla temporales del número predeterminado de entradas de tabla. Cada entrada de tabla temporal contiene bits de posición y bits de longitud, estando los bits de longitud capacitados para determinar los valores de entrada de tabla asociados a la determinación de emparejamiento posible, y siendo un bit de posición predeterminado de cada valor temporal de entrada de tabla asociado comprobado para llevar a cabo una determinación de emparejamiento posible.

BREVE DESCRIPCIÓN DE LOS DIBUJOS Las ventajas de la presente invención se pondrán de manifiesto a partir de la descripción detallada que sigue de realizaciones ejemplares de la misma, cuya descripción deberá ser considerada junto con los dibujos que se acompañan, en los que:

La Figura 1 es un diagrama de bloques de un motor de emparejamiento de prefijos de acuerdo con una realización de la presente invención; La Figura 2 es una estructura de la tabla de búsqueda de prefijo de la Figura 1, de acuerdo con una realización de la presente invención; La Figura 3 es una estructura de datos de una entrada de tabla de la tabla de búsqueda de prefijo de acuerdo con una realización de la presente invención; La Figura 4 es un diagrama de tiempos del motor de emparejamiento de prefijo de la Figura 1, de acuerdo con una realización de la presente invención; La Figura 5 es una tabla que ilustra la condición de emparejamiento de prefijo.

DESCRIPCIÓN DETALLADA DE LA INVENCIÓN Ahora se hará referencia detallada a las realizaciones de la presente invención. Aunque la invención será descrita junto con las realizaciones, se comprenderá que no se pretende limitar la invención... [Seguir leyendo]

1. Un dispositivo (100) para el emparejamiento de una corriente de entrada (101) respecto a signaturas predefinidas, que comprende:

una tabla (105) de búsqueda para almacenar información de prefijo de las signaturas predefinidas en una pluralidad de entradas de tabla; un circuito lógico (103) acoplado a la tabla (105) de búsqueda para acceder a un número predeterminado de entradas en la tabla de búsqueda de acuerdo con una porción de la corriente de entrada; caracterizado por: una memoria intermedia (107) de entrada de tabla acoplada al circuito lógico (103) para almacenar valores temporales de entrada de tabla del número predeterminado de entradas de tabla, en el que cada valor temporal de entrada de tabla contiene bits de posición y bits de longitud, estando los bits de longitud capacitados para determinar los valores de entrada de tabla asociados a la determinación de emparejamiento posible, y siendo un bit de posición predeterminado de cada valor temporal asociado de entrada de tabla comprobado para realizar una determinación de emparejamiento posible.

2. El dispositivo de la reivindicación 1, que comprende además un bloque (109) de salida acoplado al circuito lógico (103) , para recopilar información de prefijo indicada por los valores temporales de entrada de tabla cuando se encuentra el emparejamiento posible, en el que el dispositivo está adaptado para dirigir además la información de prefijo indicada por los valores temporales de entrada de tabla a un motor de emparejamiento exacto para el emparejamiento exacto de signatura.

3. El dispositivo de la reivindicación 1, en el que la pluralidad de entradas de tabla en la tabla (105) de búsqueda son índices organizados, y los índices (ABC, BCD, CDE, DEF, EFG, FGH) de la pluralidad de entradas de tabla corresponden a prefijos de las signaturas predefinidas.

4. El dispositivo de la reivindicación 1, en el que la tabla (105) de búsqueda corresponde a una memoria rápida precompilada.

5. El dispositivo de la reivindicación 1, en el que la tabla de búsqueda incluye la función hash.

6. El dispositivo de la reivindicación 1, en el que el dispositivo (100) está adaptado para dividir la porción de la corriente (101) de entrada en un número predeterminado de cadenas adyacentes solapantes, en el que el número predeterminado de cadenas adyacentes solapantes corresponde a índices (ABC, BCD, CDE, DEF, EFG, FGH) del número predeterminado de entradas de tabla.

7. El dispositivo de la reivindicación 1, en el que el dispositivo (101) está adaptado de tal modo que el acceso al número predeterminado de entradas de tabla se realiza en ciclos de reloj consecutivos.

8. El dispositivo de la reivindicación 1, en el que cada entrada de tabla en la tabla de búsqueda comprende un segmento de posición, un segmento de longitud y un segmento de dirección, en el que el bit N del segmento de posición indica si el índice de la entrada de tabla corresponde con la posición N de una de las signaturas predefinidas, el segmento de longitud almacena la longitud de la signatura predefinida más corta cuyo prefijo corresponde al índice de la entrada de tabla, y el segmento de dirección almacena la dirección de una lista de signaturas predefinidas cuyo prefijo corresponde al índice de la entrada de tabla.

9. El dispositivo de la reivindicación 1, en el que el circuito lógico (103) está adaptado para encontrar el emparejamiento posible cuando los valores temporales de entrada de tabla cumplen una condición predeterminada.

10. El dispositivo de la reivindicación 1, en el que el dispositivo de emparejamiento (100) se implementa en una matriz de puerta programable en campo (FPGA) o en un circuito integrado de aplicación específica (ASIC) .

11. Un método para el emparejamiento de una corriente de entrada (101) respecto a signaturas predefinidas, que comprende: almacenar información de prefijo de las signaturas predefinidas en una pluralidad de entradas de tabla; acceder a un número predeterminado de entradas de tabla de acuerdo con una porción de la corriente de entrada; caracterizado por almacenar valores temporales de entrada de tabla del número predeterminado de entradas de tabla, en el que cada valor temporal de entrada de tabla contiene bits de posición y bits de longitud; comprobar los bits de longitud para determinar los valores temporales de entrada de tabla asociados a una determinación de emparejamiento posible, y comprobar un bit de posición predeterminado de cada entrada temporal de tabla asociada para realizar una determinación de emparejamiento posible.

12. El método de la reivindicación 11, que comprende además realizar una función hash sobre la información de prefijo de las signaturas predeterminadas.

13. El método de la reivindicación 11, en el que se accede al número predeterminado de entradas de tabla en ciclos de reloj consecutivos.

14. El método de la reivindicación 11, que comprende además dirigir la información de prefijo indicada por los valores temporales de entrada de tabla a un motor de emparejamiento exacto; y realizar una determinación de emparejamiento exacto en base a la información de prefijo recibida en el motor de emparejamiento exacto.

15. El método de la reivindicación 11, que comprende además indexar la pluralidad de entradas de tabla mediante prefijos de las signaturas predefinidas.

16. El método de la reivindicación 11, que comprende además dividir la porción de la corriente de entrada en un número predeterminado de cadenas adyacentes solapantes, en el que el número predeterminado de cadenas adyacentes solapantes corresponde a índices del número predeterminado de entradas de tabla.

17. El método de la reivindicación 11, en el que el emparejamiento posible se encuentra cuando los valores temporales de entrada de tabla cumplen una condición predeterminada.

18. El método de la reivindicación 11, en el que cada valor temporal de entrada de tabla contiene bits de posición, bits de longitud y bits de dirección.

19. El método de la reivindicación 11, en el que la etapa de realización de una determinación de emparejamiento posible comprende además: determinar valores temporales de entrada de tabla asociados a la determinación de emparejamiento posible; y comprobar un bit de posición predeterminado de cada valor temporal asociado de entrada de tabla para realizar una determinación de emparejamiento posible.

20. Un sistema para el emparejamiento de una corriente de entrada (101) respecto a signaturas predefinidas, que comprende:

un motor (100) de emparejamiento de prefijo, que incluye: una tabla (105) de búsqueda para almacenar información de prefijo de las signaturas predefinidas en una pluralidad de entradas de tabla; un circuito lógico (103) acoplado a la tabla de búsqueda para acceder a un número predeterminado de entradas en la tabla de búsqueda de acuerdo con una porción de la corriente de entrada; caracterizado por: una memoria intermedia (107) de entrada de tabla acoplada al circuito lógico para almacenar valores temporales de entrada de tabla del número predeterminado de entradas de tabla, en el que: cada valor temporal de entrada de tabla contiene bits de posición y bits de longitud, estando los bits de longitud capacitados para determinar los valores de entrada de tabla asociados a la determinación de emparejamiento posible y siendo un bit de posición predeterminado de cada valor temporal asociado de entrada de tabla comprobado para realizar una determinación de emparejamiento posible, y un motor de emparejamiento exacto acoplado al motor de emparejamiento de prefijo para recopilar la información de prefijo asociada al emparejamiento posible y que realiza una determinación de emparejamiento exacto en base a la información de prefijo recopilada.

21. El sistema de la reivindicación 20, en el que dicho motor (100) de emparejamiento de prefijo está adaptado para organizar el indexado de la pluralidad de entradas de tabla, estando además dicho motor de emparejamiento de prefijo adaptado para dividir una porción de la corriente de entrada en un número predeterminado de cadenas adyacentes solapantes, en el que los índices del número predeterminado de entradas de tabla corresponde al número predeterminado de cadenas adyacentes solapantes.

22. El sistema de la reivindicación 20, en el que el sistema está adaptado para poner en marcha el motor de emparejamiento exacto solamente si se encuentra el emparejamiento posible en el motor de emparejamiento de prefijo.

23. El sistema de la reivindicación 20, en el que el motor (100) de emparejamiento de prefijo está implementado en una matriz de puerta programable en campo o en un circuito integrado de aplicación específica.

24. El sistema de la reivindicación 20, en el que el motor de emparejamiento exacto es operable con un algoritmo de emparejamiento exacto arbitrario.