Skip to content Skip to sidebar Skip to footer

How To Efficiently Check If A Given Ip Address Belong To An Ip Subnetwork In Python?

I have a set of about 200,000 IP Addresses and 10,000 subnets of the form(1.1.1.1/24). For every IP Address I need to check whether it belongs to one of these subnets, but since it

Solution 1:

Okay, So sorting takes O(nlogn), In case of 13,000,000 you end up doing O(13000000log(13000000)). Then You are iterating over 200000 IP and doing binary search O(logn) on that sorted list on 13000000. I sincerely doubt that's best solution. I suggest you use map

from netaddr import IPNetwork, IPAddress
l_ip_address = map(IPAddress, list_of_ip_address)
l_ip_subnet = map(IPNetwork, list_of_subnets)

ifany(x in y for x in l_ip_address for y in l_ip_subnet):
    print"FOUND"

Solution 2:

This is probably not the best possible solution, but I'd suggest using a set rather than a list. Sets are optimized for checking if any given value is present in the set, so you're replacing your binary search with a single operation. Instead of:

ip_list = list(set(ip_list))

just do:

ip_set = set(ip_list)

and then the other part of your code becomes:

for ip in myIPList:  # myIPList is the list of 200,000 IPsif ip in ip_set:
        print('The ip is present')

Edit: and to make things a bit more memory-efficient you can skip creating an intermediate list as well:

ip_set = set()
for ipMasked in ipsubnets: 
    ip_set.update([str(ip) for ip in IPNetwork(ipMasked)])

Solution 3:

Your IP address in in a subnet if N leading bits of that address match N leading bits of one of the N-bit subnets. So, start by making a list of empty sets. Encode each subnet as a 32-bit integer with the trailing bits masked out. For example, 1.2.3.4/23 equals (0x01020304 & 0xfffffe00) equals 0x01020200. Add this number to the 23rd set in the list, ie subnets[23]. Continue for all the subnets.

To see if an IP address is in your subnets, encode the IP address in the same way as a 32-bit number ipaddr and then (something like, untested code)

for N inrange( 32, 0, -1)
    mask = ( 0xffffffff >> (32-N) ) << (32-N)
    if (ipaddr & mask) in subnets[N] :
        # have found ipaddr in one of our subnetsbreak# or do whatever...else# have not found  ipaddr

Looking up a number in a set at worst O(log N) where N in the number of elements in the set. This code does it at most 32 times for the worst case of an ip address that is not in the sets of subnets. If the majority of the addresses are expected to be present, there's an optimisation to test the sets with the most elemnnts first. That might be

for N in( 24, 16, 8, 29, 23, 28, 27, 26, 25, 22, 15, 21 ... )

or you could calculate the optimal sequence at runtime.

Post a Comment for "How To Efficiently Check If A Given Ip Address Belong To An Ip Subnetwork In Python?"