Fastest ip address searching method/implementation

[Jonathan]

I am hoping that someone more experienced than myself can point me towards
what might be the fastest data lookup method to use for storing ip
addresses. My situation is that I will need to maintain a list of perhaps 50
ip addresses to be used in a packet sniffing application. For each packet
that goes through the application (which will be monitoring all traffic
through a switch), I need to see if an entry for the source ip of that
packet already exists in the list, and if not, add it.

My ip list is not going to be too large (perhaps 50-100 items at a time),
but I am going to be constantly searching the list every time a packet is
received, which could be an incredible burden if doing a simple linear
search on a linked list.

What would be the best possible implementation for my situation? A binary
search (slightly faster), a hash table which hashes the ip as a 32 bit
integer or a string, anything else?

Thanks in advance!
Jonathan Halterman

 

[Florian Weimer]

I am hoping that someone more experienced than myself can point me towards
what might be the fastest data lookup method to use for storing ip
addresses. My situation is that I will need to maintain a list of perhaps 50
ip addresses to be used in a packet sniffing application. For each packet
that goes through the application (which will be monitoring all traffic
through a switch), I need to see if an entry for the source ip of that
packet already exists in the list, and if not, add it.

A hash table should be pretty fast, especially if the list of
addresses is essentially constant and not controlled by external
input.

If the address list is highly dynamic, the industry standard seems to
be balanced trees.

 

[Victor Bazarov]

I am hoping that someone more experienced than myself can point me towards
what might be the fastest data lookup method to use for storing ip
addresses. My situation is that I will need to maintain a list of perhaps 50
ip addresses to be used in a packet sniffing application. For each packet
that goes through the application (which will be monitoring all traffic
through a switch), I need to see if an entry for the source ip of that
packet already exists in the list, and if not, add it.

My ip list is not going to be too large (perhaps 50-100 items at a time),
but I am going to be constantly searching the list every time a packet is
received, which could be an incredible burden if doing a simple linear
search on a linked list.

What would be the best possible implementation for my situation? A binary
search (slightly faster), a hash table which hashes the ip as a 32 bit
integer or a string, anything else?

Sorry, I don't see a C++ language question here. Perhaps you need to
visit "comp.programming" newsgroup for general sorting/search algorithm
help...

 

[Jack Klein]

I am hoping that someone more experienced than myself can point me towards
what might be the fastest data lookup method to use for storing ip
addresses. My situation is that I will need to maintain a list of perhaps 50
ip addresses to be used in a packet sniffing application. For each packet
that goes through the application (which will be monitoring all traffic
through a switch), I need to see if an entry for the source ip of that
packet already exists in the list, and if not, add it.

My ip list is not going to be too large (perhaps 50-100 items at a time),
but I am going to be constantly searching the list every time a packet is
received, which could be an incredible burden if doing a simple linear
search on a linked list.

What would be the best possible implementation for my situation? A binary
search (slightly faster), a hash table which hashes the ip as a 32 bit
integer or a string, anything else?

Thanks in advance!
Jonathan Halterman

I realize that this is really an algorithm, not a C++ question, but
stop and think -- why in the world would you want hash ip addresses to
32 bit integer types? By definition, an IPV4 address is actually
nothing but an unsigned 32-bit integer type. Dotted-quad notation is
just a convenience. Every single IPV4 address can be, rather quickly,
converted directly to an unsigned long, and every unique IP address
will result in a different unsigned long.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++ ftp://snurse-l.org/pub/acllc-c++/faq

 

[Thomas Matthews]

I am hoping that someone more experienced than myself can point me towards
what might be the fastest data lookup method to use for storing ip
addresses. My situation is that I will need to maintain a list of perhaps 50
ip addresses to be used in a packet sniffing application. For each packet
that goes through the application (which will be monitoring all traffic
through a switch), I need to see if an entry for the source ip of that
packet already exists in the list, and if not, add it.

My ip list is not going to be too large (perhaps 50-100 items at a time),
but I am going to be constantly searching the list every time a packet is
received, which could be an incredible burden if doing a simple linear
search on a linked list.

What would be the best possible implementation for my situation? A binary
search (slightly faster), a hash table which hashes the ip as a 32 bit
integer or a string, anything else?

Thanks in advance!
Jonathan Halterman

As others have stated, here are some fast data structures:
1. Vector / array, if you have the memory (use IP address as index).
2. Hash table.
3. std::map (a.k.a binary tree).

Using Jack's method of representing the IP address as an unsigned
long will require only one of the above structures.

Representing it as 4 8-bit byte values (unsigned char) will
require more data structures, however, it allows one easier
classification, if you need it.

--
Thomas Matthews

C++ newsgroup welcome message:
http://www.slack.net/~shiva/welcome.txt
C++ Faq: http://www.parashift.com/c++-faq-lite
C Faq: http://www.eskimo.com/~scs/c-faq/top.html
alt.comp.lang.learn.c-c++ faq:
http://www.raos.demon.uk/acllc-c++/faq.html
Other sites:
http://www.josuttis.com -- C++ STL Library book
http://www.sgi.com/tech/stl -- Standard Template Library

 

[Gianni Mariani]

I am hoping that someone more experienced than myself can point me towards
what might be the fastest data lookup method to use for storing ip
addresses. My situation is that I will need to maintain a list of perhaps 50
ip addresses to be used in a packet sniffing application. For each packet
that goes through the application (which will be monitoring all traffic
through a switch), I need to see if an entry for the source ip of that
packet already exists in the list, and if not, add it.

My ip list is not going to be too large (perhaps 50-100 items at a time),
but I am going to be constantly searching the list every time a packet is
received, which could be an incredible burden if doing a simple linear
search on a linked list.

What would be the best possible implementation for my situation? A binary
search (slightly faster), a hash table which hashes the ip as a 32 bit
integer or a string, anything else?

"the fastest" method for lookup will probably be a hash but you will
have issues with growing the hash table.

You could create a performance test class where you test various
containers and see which ones does best.

see:
http://www.sgi.com/tech/stl/hash_map.html

 

[Kelsey Bjarnason]

Sorry, I don't see a C++ language question here. Perhaps you need to
visit "comp.programming" newsgroup for general sorting/search algorithm
help...

Dunno... I thought I saw one. In essence, "Is there a C++ mechanism for
storing and retrieving keyed data efficiently?"

std::map, for example, might do the trick.