By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
443,889 Members | 1,373 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 443,889 IT Pros & Developers. It's quick & easy.

Fastest ip address searching method/implementation

P: n/a
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
Jul 22 '05 #1
Share this Question
Share on Google+
6 Replies


P: n/a
"Jonathan" <no****@aol.com> writes:
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.
Jul 22 '05 #2

P: n/a
"Jonathan" <no****@aol.com> wrote...
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...
Jul 22 '05 #3

P: n/a
On Wed, 26 Nov 2003 13:49:54 -0800, "Jonathan" <no****@aol.com> wrote
in comp.lang.c++:
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
Jul 22 '05 #4

P: n/a
Jonathan wrote:
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

Jul 22 '05 #5

P: n/a
Jonathan wrote:
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

Jul 22 '05 #6

P: n/a
On Wed, 26 Nov 2003 22:14:29 +0000, Victor Bazarov wrote:
"Jonathan" <no****@aol.com> wrote...
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...

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.
Jul 22 '05 #7

This discussion thread is closed

Replies have been disabled for this discussion.