necesita un algoritmo para colapsar rangos de netblock en listas de rangos de superconjuntos

Question

¡Mi matemática fu me está fallando! Necesito una forma eficiente de reducir los rangos de red a superconjuntos, p. si la lista de entrada de rangos de IP:

• 1.1.1.1 a 2.2.2.5
• 1.1.1.2 a 2.2.2.4
• 10.5.5.5 a 155.5.5.5
• 10.5.5.6 a 10,5. 5,7

quiero devolver los siguientes rangos:

• 1.1.1.1 a 2.2.2.5
• 10.5.5.5 155.5.5.5 a

Nota: las listas de entrada no están ordenados (a pesar de que podría ser?). La forma ingenua de hacerlo es verificar cada rango en la lista para ver si el rango de entrada x es un subconjunto, y si es así, NO inserte el rango x. Sin embargo, siempre que inserte un nuevo rango, podría tratarse de un superconjunto de rangos existentes, por lo que debe verificar los rangos existentes para ver si se pueden contraer (p. Ej., Eliminarlos de mi lista).

Answer 1

Lo que necesita hacer es simplemente verificar los rangos de superposición. Si dos rangos se superponen, se fusionan en un solo rango. Los rangos se superponen si el lado derecho de un rango es mayor que el lado izquierdo de otro.

Answer 2

Muy bien, a mi compañero de trabajo se le ocurrió esta respuesta, que creo que es bastante excelente. Déjame saber si hay cuestiones:

• Solicitar rangos de IPs correspondientes por StartingIP
• Para cada fila "x" para insertar:
  • Si hay una fila anterior "y" en la lista , ir a buscar:
    • Si x e y son contiguos, se extienden y al de x EndingIP
    • Porque si x.StartingIP < = y.StartingIP y x.EndingIP> y.EndingIP, y se extienden a x.EndingIP
    • Porque si x es un subconjunto de Y, no hacer nada
    • lo demás, crear una nueva gama
  • lo demás, crear una nueva gama y se insertan en la lista

Answer 3

Este es una unión de computación de segmentos. Un algoritmo óptimo (en O (nlog (n))) consiste en hacer lo siguiente:

2. ordenar todos los puntos finales (puntos inicial y final) en una lista L (cada punto extremo debe saber el segmento al que pertenece). Si un punto final es igual a un punto de inicio, el punto de partida se debe considerar más pequeño que el enpoint.
3. pasan por la lista ordenada L de izquierda a derecha y mantener el número LE-RE, donde LE es el número de puntos finales que dejan que ya han pasado, y RE es el número de puntos finales adecuados que ya has pasado.
4. cada vez LE-RE llega a cero, se encuentra al final de una unión de segmentos conectada, y sabe que la unión de los segmentos que ha visto antes (desde el retorno anterior a cero) es un superconjunto.
5. si también mantuvo el mínimo y máximo, entre cada vuelta a cero, tiene los límites del superconjunto.

Al final, obtiene una lista ordenada de superconjuntos disjuntos. Aún así, dos superconjuntos A y B pueden estar adyacentes (el punto final de A está justo antes del punto de inicio de B). Si desea fusionar A y B, puede hacerlo mediante un simple paso de posprocesamiento o modificando levemente el paso 3: cuando LE-RE llegue a cero, lo consideraría el final de un superconjunto solo si el siguiente elemento en L no es el sucesor directo de su elemento actual.

Answer 4

Sabe que puede convertir fácilmente direcciones IPv4 a números enteros (números int32), ¿verdad? Trabajar con números enteros es mucho más fácil. Entonces, básicamente, cada dirección es un número en el rango de 0 a 2^32. Cada rango tiene un número de inicio y un número final. Su ejemplo

1.1.1.1 to 2.2.2.5 
1.1.1.2 to 2.2.2.4 

se puede escribir como

16,843,009 to 33,686,021 
16,843,010 to 33,686,020 

Así que es bastante fácil de ver si uno está dentro del rango de otro rango. Un rango es completamente dentro de la otra gama si se da la siguiente condición

startIP2 >= startIP1 && startIP2 <= endIP1 && 
endIP1 >= startIP1 && endIP2 <= endIP1 

En ese caso el rango startIP2-endIP2 está completamente dentro de startIP1-endIP1. Si solo la primera línea es verdadera, entonces startIP2 está dentro del rango de inicioIP1-endIP1, pero el final está más allá del rango. Si solo la segunda línea es verdadera, el endIP está dentro del rango, pero el IP de inicio está más allá del rango. En ese caso, si solo una línea es verdadera, necesita expandir el rango al principio o al final. Si ambas líneas son falsas, los rangos son completamente disjuntos, en ese caso son dos rangos completamente independientes.