Fastest ip address searching method/implementation

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

re: Fastest ip address searching method/implementation

"Jonathan" <nospam@aol.com> writes:
[color=blue]
> 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.[/color]

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.

re: Fastest ip address searching method/implementation

"Jonathan" <nospam@aol.com> wrote...[color=blue]
> 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[/color]
50[color=blue]
> 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?[/color]

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

re: Fastest ip address searching method/implementation

On Wed, 26 Nov 2003 13:49:54 -0800, "Jonathan" <nospam@aol.com> wrote
in comp.lang.c++:
[color=blue]
> 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[/color]

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

re: Fastest ip address searching method/implementation

Jonathan wrote:[color=blue]
> 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
>
>[/color]

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

re: Fastest ip address searching method/implementation

Jonathan wrote:[color=blue]
> 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?[/color]

"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

re: Fastest ip address searching method/implementation

On Wed, 26 Nov 2003 22:14:29 +0000, Victor Bazarov wrote:
[color=blue]
> "Jonathan" <nospam@aol.com> wrote...[color=green]
>> 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[/color]
> 50[color=green]
>> 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?[/color]
>
> Sorry, I don't see a C++ language question here. Perhaps you need to
> visit "comp.programming" newsgroup for general sorting/search algorithm
> help...[/color]


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.