indicizzato variava algoritmo di ricerca per indirizzi IP

Question

Dato un elenco ACL con 10 miliardi di IPv4 gamme in CIDR notiation o tra due indirizzi IP:

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

Che cos'è un algoritmo di ricerca/indicizzazione efficiente per la prova che un determinato indirizzo IP incontra la critica di uno o più intervalli ACL?

Supponiamo che la maggior parte delle definizioni di intervallo ACL coprano un numero elevato di blocchi di classe C.

I punti di indicizzazione tramite tabelle hash sono facili ma si può provare perché non sono riuscito a trovare un metodo ragionevole per rilevare quali punti sono coperti da un ampio elenco di "linee".

Alcuni pensieri come indizi di indicizzazione a un determinato livello di dettaglio - ad esempio pre-computing a livello di classe C ogni ACL che copriva quel punto ma il tavolo sarebbe troppo grande .. O una sorta di albero KD a dinamicamente impostare livelli di dettaglio.

Si è anche pensato che forse esistono algoritmi di rilevamento delle collisioni che possono risolvere questo problema.

Eventuali suggerimenti o indicazioni nella giusta direzione?

Answer 1

È possibile esaminare Interval tree per trovare tutti gli intervalli che si sovrappongono a un dato intervallo o punto.

Per intervalli IP non sovrapposti, è possibile utilizzare un b-tree o un tentativo compatto come Judy arrays (64-bits) per l'indicizzazione e la ricerca (Memorizza l'IP iniziale come chiave e l'ip finale come valore).

Answer 2

Il semplice Radix Tree che è stato utilizzato nelle ricerche di route Internet longest prefix match, può essere ridimensionato per contenere nodi che rappresentano le subnet CIDR più grandi che si sovrappongono ad altre più piccole. Una ricerca di corrispondenze più lunga attraverserà questi nodi che saranno anche selezionati per ottenere l'intero set di sottoreti CIDR che corrispondono a un indirizzo IP.

Ora, per mantenere gli intervalli IP nello stesso albero, possiamo convert each range into a set of CIDR subnets. Questo può sempre essere fatto sebbene il set possa avere molte sottoreti (e anche alcuni IP host - cioè indirizzi CIDR di tipo IP/32).

Answer 3

Hai 10 miliardi di regole per abbinare 4 miliardi di indirizzi possibili?

Creare una tabella di 4 miliardi di indirizzi. Per ognuna delle 10 miliardi di regole, "dipingi" gli indirizzi a cui si applica, facendo qualcosa di ragionevole quando due o più regole si applicano allo stesso indirizzo.