Struktura danych + algorytm do przechowywania plików IPV - skuteczne wyszukiwanie w prefiksach

Question

Szukam struktury danych dla IPV4. Co powinien przechowywać? Prefiks (baza + maska) -> np 85.23.0.0/16

bazowy = 85.23.0.0 -> 32 nieco unsigned

maski = 16 AKA 255.255.0.0 -> 8 bitów unsigned char

Więc min gospodarz jest 85.23.0.0 i max gospodarz jest 85.23.255.255 (wiem, że powinno być .0.1 i .255.254 w normalnym przypadku, ale chcę, aby go uprościć)

Najważniejsze, że wymaga to prędkość wyszukiwania adresu IP w przechowywanych prefiksach. Na przykład daję niepodpisaną int (32bit) i muszę powiedzieć, czy jest tam, czy nie.

piszę w C++, więc mogę używać STL

Teraz jest on przechowywany w zbiorze STL (parach + maska) i szukam jeden po drugim, więc jest to rodzaj O (n) (Bez to jest prawdopodobnie drzewo BST, więc przechodzenie przez niego może być wolniejsze niż O (n))

Podsumowując: Nie potrzebuję wydajnego sposobu na przechowywanie IPV4, potrzebuję skutecznego sposobu na wyszukanie go w niektórych struktura danych. Struktura danych nie będzie przechowywać portu, rodziny itp. Przechowywany będzie PREFIX (baza + maska).

A ja szukam struktury danych + pewien algorytm wyszukiwania.

Answer 1

Dlaczego nie używać std: unordered_map? Powinien być między O (1) i O (n), lub możesz użyć std: map, jeśli chcesz mieć stałą wydajność O (log n) (jeśli NAPRAWDĘ interesujesz się wydajnością tylko w fazie wyszukiwania). Dopóki twoje zbiory danych nie są duże, możesz zauważyć, że nie ma znaczącej różnicy.

Answer 2

Ta metoda działa tylko dla zakresu masek 1-31. Aby dokonać szybkiego wyszukiwania binarny dla pełnego zakresu (0-32) powinieneś przechowywać maskę i adres wewnątrz 64-bitowej liczby całkowitej (ex. Jak ten std::vector<unsigned long long> networkAddrs(bases.size()); ... networkAddrs[i] = (bases[i] << 32) + masks[i];)

pomocą prostych własności adresu sieciowego, który można przechowywać Maska wewnątrz nieużywanych bitów adresu sieciowego pozwala na proste przechowywanie maski i bazy wewnątrz pojedynczej 32-bitowej liczby całkowitej, sortowanie ich wektorów i wyszukiwanie binarne. Coś takiego:

#include <iostream> 
#include <string> 
#include <vector> 
#include <algorithm> 
#include <cmath> 

unsigned int insertMask(unsigned int ip, unsigned int mask) 
{ 
    unsigned int longMask = (~0) << (32-mask); 
    unsigned int netAdd = (ip & longMask) + (1 << (31-mask)); 
    return netAdd; 
} 

bool isInNetwork(std::vector<unsigned int>& nAs, unsigned int ip, unsigned int mask) 
{ 
    unsigned int netAdd = insertMask(ip, mask); 
    auto pos = std::lower_bound(nAs.begin(), nAs.end(), netAdd); 
    return pos != nAs.end() && *pos == netAdd; 
} 

int main() 
{ 

    std::vector<unsigned int> bases { 
     (192u<<24)+(168<<16)+(0<<8)+(0) 
     ,190u<<24 
     ,191u<<24 
     ,192u<<24 
     ,193u<<24 
     ,194u<<24 
     ,195u<<24 
     ,196u<<24 
    }; 

    std::vector<unsigned int> masks {24,24,24,24,24,16,8,4}; 

    std::vector<unsigned int> networkAddrs(bases.size()); 

    for(int i=0; i<bases.size(); i++) 
    { 
     networkAddrs[i] = insertMask(bases[i], masks[i]); 
    } 

    std::sort (networkAddrs.begin(), networkAddrs.end()); 

    unsigned int ip_addr = (192u<<24)+(168<<16)+(0<<8)+(17); 
    unsigned int mask = 24; 

    if(isInNetwork(networkAddrs, ip_addr, mask)) 
    std::cout << "TRUE"; 
    else 
    std::cout << "FALSE"; 

    std::cout << '\n'; 

} 

EDIT: zmieniłem metodę maski kodu jako takiego:

dla IP XXX.XXX.YYY.YYY/16
0b XXXXXXXX XXXXXXXX 10000000 00000000

dla ip (XXX.XXX.0xXY.YYY/12)
0b XXXXXXXX XXXXXXXX XXXX1000 00000000

Answer 3

Możesz sprawdzić papieru DXR 'Ku Miliardzie Routing Lookups na sekundę w Oprogramowanie' z 2012 roku:

http://info.iet.unipi.it/~luigi/papers/20120601-dxr.pdf

Przedstawiono DXR, system odnośników w oparciu o przekształcania dużych tablic routingu w zwartych struktur odnośników, które łatwo dopasować do hierarchii pamięci podręcznej nowoczesnych procesorów.

Nasza transformacja destyluje rzeczywistą migawkę BGP z 427 000 prefiksami IPv4 i 213 odrębnymi następnymi przeskokami w strukturę zużywającą tylko 782 kilobajty, mniej niż 2 bajty na prefiks. Eksperymenty pokazują, że odpowiedni algorytm wyszukiwania skaluje się liniowo z liczbą rdzeni procesora: działa na 8-rdzeniowym rdzeniu procesora, co daje średnią przepustowość 840 milionów wyszukiwań na sekundę dla jednolicie losowych kluczy IPv4.

Podczas prosicie „nie trzeba skuteczny sposób na przechowywanie IPv4”, kompaktowe przechowywanie pomoże w wykonywaniu odnośnika, ponieważ pamięć jest bardzo powolny i cache procesora jest szybszy (wariant memory wall komputera memory hierarchy). Więcej zwartej reprezentacji ma mniej braków z pamięci podręcznej L3 do pamięci i może być szybsze.

DXR ma bardzo dobrą prędkość (na 3,6 GHz AMD FX-8150 z DDR3 pamięci 1866MHz):

losowych kluczy wyszukiwania (sytuacja najgorszy przypadek) D18R idzie od 117 milionów wyszukiwań na sekundę (MLPS) na pojedynczym rdzeniu, do 840 Mlps przy wszystkich 8 rdzeniach aktywnych. ... W zależności od konfiguracji i modelu zapytania, DXR uzyskuje od 50 do 250 milionów wyszukiwań na sekundę na 1 rdzeniu

117 ml/s na 3,6 GHz to około 30 cpu na każdy odnośnik; Opóźnienie dostępu do pamięci DDR3 1866MHz to więcej niż 9-10 ns lub 32-36 procesorów, aby uzyskać pierwsze bajty z pamięci do kontrolera pamięci, gdy rząd DRAM jest otwarty (zazwyczaj może nie być - otwiera się również wolny wiersz). Potrzebny jest dodatkowy czas na odczyt pełnej linii pamięci podręcznej i trochę więcej czasu na przekazanie tej linii pamięci podręcznej do L3, L2, L1, rejestrów. Pełne opóźnienie pamięci może wynosić close to 100 ns (cykle 360 ​​cpu)

Answer 4

Można użyć drzewa CritBit. Są dość proste, ale istnieje również wiele wariantów open-source. Jest to drzewo z możliwością przeszukiwania, które korzysta z dzielenia prefiksów, więc wszystkie wartości o tym samym prefiksie są przechowywane w tym samym drzewie podrzędnym. W zależności od implementacji współdzielenie prefiksów może być również użyte w celu zmniejszenia wymagań dotyczących miejsca, ponieważ przechowujesz prefiks tylko raz, a nie dla każdego wpisu.