Fastest ip address searching method/implementation

Discussion in 'C++' started by Jonathan, Nov 26, 2003.

  1. Jonathan

    Jonathan Guest

    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
     
    Jonathan, Nov 26, 2003
    #1
    1. Advertising

  2. "Jonathan" <> 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.
     
    Florian Weimer, Nov 26, 2003
    #2
    1. Advertising

  3. "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?


    Sorry, I don't see a C++ language question here. Perhaps you need to
    visit "comp.programming" newsgroup for general sorting/search algorithm
    help...
     
    Victor Bazarov, Nov 26, 2003
    #3
  4. Jonathan

    Jack Klein Guest

    On Wed, 26 Nov 2003 13:49:54 -0800, "Jonathan" <> 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
     
    Jack Klein, Nov 27, 2003
    #4
  5. 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
     
    Thomas Matthews, Nov 27, 2003
    #5
  6. 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
     
    Gianni Mariani, Nov 28, 2003
    #6
  7. On Wed, 26 Nov 2003 22:14:29 +0000, Victor Bazarov wrote:

    > "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?

    >
    > 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.
     
    Kelsey Bjarnason, Nov 29, 2003
    #7
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. yee young han
    Replies:
    2
    Views:
    503
    Jerry Coffin
    May 22, 2005
  2. samuraisam
    Replies:
    4
    Views:
    1,073
    Carl Friedrich Bolz
    Feb 20, 2008
  3. SETT Programming Contest
    Replies:
    18
    Views:
    643
    Ben Pfaff
    Jun 5, 2008
  4. Marcel Müller

    Re: Fastest way to byte address ints?

    Marcel Müller, Mar 4, 2010, in forum: C++
    Replies:
    2
    Views:
    353
    James Kanze
    Mar 5, 2010
  5. Joshua Maurice

    Re: Fastest way to byte address ints?

    Joshua Maurice, Mar 5, 2010, in forum: C++
    Replies:
    0
    Views:
    430
    Joshua Maurice
    Mar 5, 2010
Loading...

Share This Page