indexado osciló algoritmo de búsqueda de direcciones IP

Question

Dada una lista ACL con 10 mil millones de IPv4 rangos en notiation CIDR o entre dos direcciones IP:

x.x.x.x/y 
x.x.x.x - y.y.y.y 

¿Qué es un algoritmo de búsqueda/indexación eficiente para la prueba de que una determinada dirección IP se reúne la critera de uno o más rangos de ACL?

Supongamos que la mayoría de las definiciones de rango de ACL abarcan una gran cantidad de bloques de clase C.

Los puntos de indexación a través de tablas hash son fáciles, pero inténtalo ya que podría no haber sido capaz de encontrar un método razonable para detectar qué puntos están cubiertos por una gran lista de "líneas".

Tuve algunas ideas, como indicios de indexación con un cierto nivel de detalle, digamos pre-cálculo en el nivel de clase C cada ACL que cubría ese punto pero la tabla sería demasiado grande ... O algún tipo de árbol KD dinámicamente establecer niveles de detalle.

También pensé que quizás existen algoritmos de detección de colisiones que pueden solucionar esto.

¿Algún consejo o sugerencia en la dirección correcta?

Answer 1

Puede consultar el Interval tree para encontrar todos los intervalos que se superponen con cualquier intervalo o punto determinado.

Para intervalos de IP no superpuestos, puede usar un b-tree o intentos compactos como Judy arrays (64-bits) para indexar y buscar (Guarde el start-ip como clave y el end-ip como valor).

Answer 2

El simple Radix Tree que se ha utilizado en las búsquedas de rutas de Internet longest prefix match, se puede escalar para mantener los nodos que representan las subredes CIDR más grandes que se superponen a otras más pequeñas. Una búsqueda de coincidencia más larga recorrerá estos nodos, que también se seleccionarán para obtener el conjunto completo de subredes CIDR que coinciden con una dirección IP.

Ahora, para mantener los rangos de IP en el mismo árbol, podemos convert each range into a set of CIDR subnets. Esto se puede hacer siempre, aunque el conjunto puede tener muchas subredes (e incluso algunas direcciones IP host, es decir, direcciones CIDR tipo IP/32).

Answer 3

¿Tiene 10 mil millones de reglas para unir 4 mil millones de direcciones posibles?

Haga una tabla de 4 mil millones de direcciones. Para cada una de las 10 mil millones de reglas, 'pinta' las direcciones a las que se aplica, haciendo algo sensato cuando dos o más reglas se aplican a la misma dirección.