jeudi 30 juin 2016

Data structure + algorithm for ipv4 storage - efficient searching in prefixes


I am searching for Data Structure for IPV4. What should it store? Prefix: (base + mask) --> for example 85.23.0.0/16

base = 85.23.0.0 -> 32 bit unsigned

mask = 16 AKA 255.255.0.0 -> char 8 bit unsigned

So min host is 85.23.0.0 and max host is 85.23.255.255 (I know that it should be .0.1 and .255.254 in normal case but I want to simplify it)

The main thing that I require is speed of searching IP in stored prefixes. For example I give unsigned int (32bit) and I need to tell whether it is there or no.

I am writing in C++ so I can use STL

Now it is stored in STL set (pair base + mask) and I am searching one by one, so it is sort of O(n) (Excluding that is it probably BST tree, so walking through the it might be slower than O(n))

To sum up: I don't need efficient way to store IPV4, I need an efficient way to SEARCH it in some data structure. And the data structure won't store port or family type etc. It will store PREFIX (base + mask).

And the I am searching for data structure + some algorithm of searching.


Aucun commentaire:

Enregistrer un commentaire