2009-06-25 23 views
10

Biorąc pod uwagę lista ACL 10 mld IPv4 waha się w CIDR notiation lub między dwoma adresami IP:indeksowane wahała algorytm wyszukiwania dla adresów IP

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

Co jest sprawna algorytm wyszukiwania/indeksowania do testowania, że ​​dany adres IP spełnia krytyka jednego lub więcej zakresów ACL?

Pozwala przyjąć, że większość definicji zakresu ACL obejmuje dużą liczbę bloków klasy C.

Indeksowanie punktów za pomocą tablic haszujących jest łatwe, ale spróbuj, ponieważ nie byłbym w stanie wymyślić rozsądnej metody wykrywania, które punkty są objęte dużą listą "linii".

Miałem pewne przemyślenia, takie jak indeksowanie podpowiedzi na pewnym poziomie szczegółowości - na przykład, wstępne obliczenia na poziomie klasy C dla każdej listy ACL, która obejmowała ten punkt, ale tabela byłaby zbyt duża. Lub pewnego rodzaju drzewo KD dynamicznie ustawić poziomy szczegółowości.

Miałem również na myśli, że być może istnieją algorytmy wykrywania kolizji, które mogą rozwiązać ten problem.

Jakieś wskazówki lub wskazówki we właściwym kierunku?

Odpowiedz

2

Możesz spojrzeć na Interval tree, aby znaleźć wszystkie interwały, które pokrywają się z dowolnym interwałem lub punktem.

Dla nienakładających się zakresów adresów IP, można użyć b-drzewa lub kompaktowych prób, takich jak Judy arrays (64-bits) do indeksowania i wyszukiwania (Przechowuj początek-ip jako klucz, a końcowy adres jako wartość).

3

prostego Radix Tree która została wykorzystana w longest prefix match wyszukiwań trasy Internet, mogą być skalowane do przechowywania węzły, które reprezentują większe podsieci CIDR, które pokrywają inne mniejsze. Najdłuższe wyszukiwanie dopasowań przetnie te węzły, które również zostaną wybrane, aby uzyskać cały zestaw podsieci CIDR, które pasują do adresu IP.

Teraz, aby utrzymywać zakresy IP w tym samym drzewie, możemy convert each range into a set of CIDR subnets. Można to zawsze zrobić, chociaż zestaw może mieć wiele podsieci (a nawet niektóre adresy IP hosta - czyli adresy CIDR typu IP/32).

3

Masz 10 miliardów reguł, aby dopasować 4 miliardy możliwych adresów?

Stwórz tabelę z 4 miliardami adresów. Dla każdej z 10 miliardów zasad "maluj" adresy, których dotyczy, wykonując coś sensownego, gdy dwie lub więcej reguł dotyczy tego samego adresu.

Powiązane problemy