Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

Storing and searching sets of IP address ranges

by acferen (Sexton)
on Jul 06, 2010 at 21:00 UTC ( #848317=perlquestion: print w/replies, xml ) Need Help??

acferen has asked for the wisdom of the Perl Monks concerning the following question:

My goal is to efficiently determine if an IP address is in a set.

The simplistic implementation would be a hash of IP addresses, but that can consume way too much memory. If, for example, I put a single Class A (/8 block) in the hash there would need to contain 16,777,214 entries.

I considered Set::IntSpan::Fast, Array::IntSpan, and Array::IntSpan::IP, but none of these work for IPv6 addresses.

Is there a module I missed that has functionality equivalent to IntSpan that will work with packed IP addresses (v4 and v6)? An alternate approach I haven't considered? Or do I need to get busy writing this module?

Thanks,
-Andrew

  • Comment on Storing and searching sets of IP address ranges

Replies are listed 'Best First'.
Re: Storing and searching sets of IP address ranges
by ikegami (Patriarch) on Jul 06, 2010 at 21:56 UTC
    IP6 addresses are 128-bit numbers. Perl can't represent those natively, which is the only reason Array::IntSpan (and thus Array::IntSpan::Fields) won't do. However, it could easily be modified by work with strings such as the packed representation of an ip4/ip6 address (by switching numerical operators <, ==, etc with string operators lt, eq, etc).
      On the other hand, who says we have to use native numbers!
      use strict; use warnings; use Array::IntSpan qw( ); use Math::BigInt qw( ); use Socket qw( AF_INET6 inet_pton ); sub ip6_to_num { return Math::BigInt->new( '0x' . unpack 'H32', inet_pton AF_INET6, $_[0] ); } my $span = Array::IntSpan->new( [ ip6_to_num('2001:0db8:85a3:0000:0000:0000:0000:0000'), ip6_to_num('2001:0db8:85a3:ffff:ffff:ffff:ffff:ffff'), 'Some Network', ] ); for my $addr (qw( 2001:db8:85a3::8a2e:370:7334 2001:dc8:85a3::8a2e:370:7334 )) { my $network = $span->lookup(ip6_to_num($addr)); printf("Address %s is %s\n", $addr, $network ? "present in $network" : 'absent', ); }
      Address 2001:db8:85a3::8a2e:370:7334 is present in Some Network Address 2001:dc8:85a3::8a2e:370:7334 is absent
        I like this as a quick way to get something working, but I think I may ultimately need to go with your first suggestion and change the operators. I already have IP addresses as 4/16 byte entities so changing the operators will save [un]pack calls for each lookup.

        Thanks,
        -Andrew

Re: Storing and searching sets of IP address ranges
by hexcoder (Deacon) on Jul 06, 2010 at 22:21 UTC
    If each entry of the set is a nonoverlapping range of IP addresses, i would keep them in a sorted list of ranges.
    A given ip address can be found by bisecting on the start of each range followed by a check that the address is smaller or equal to its highest value.

    If you want to use strings for IP addresses, bitwise string operators may be of help if you need to mask out the subnet with the netmask value for the range.

Re: Storing and searching sets of IP address ranges
by FloydATC (Deacon) on Jul 07, 2010 at 06:07 UTC
    It might be helpful to know a little bit more about the intended use.
    • Will you be keeping track of seemingly random addresses and ranges, or a list of networks with known netmasks? (e.g. ones associated with your organization)
    • How many entries are we talking about; a few, thousands or millions?
    • Will the database be used mostly for searches/lookups or will there be a lot of insert/delete operations?
    • Will you be using range exceptions such as "A..Z except P-Q"?
    If you know the netmasks then it seems to me that you could simplyfy the matching greatly by using bitwise operations and not a range based approach like spanning.

    -- Time flies when you don't know what you're doing

      The address will probably have some order, but may not have a known netmask.

      Probably less than 100's of entries per set.

      This will be overwhelmingly for lookups very few insert/delete operations. There will likely be 1000s of lookups per second.

      At present exceptions like your example would simply be two ranges A..O and R..Z.

      -Andrew

Re: Storing and searching sets of IP address ranges
by DrHyde (Prior) on Jul 08, 2010 at 10:24 UTC

    You want Net::CIDR, specifically the cidrlookup function. Pass it an address and a (list of) CIDR blocks and it'll tell you whether the address is in any of the blocks.

    If your address range doesn't match a single CIDR block, (eg it's 192.168.32.45 to 192.168.255.255) then you can use the range2cidr function to generate the appropriate list of CIDR blocks.

    It should work for both IPv4 and IPv6.

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://848317]
Approved by Corion
Front-paged by Corion
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (3)
As of 2022-12-05 02:24 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found

    Notices?