troubleshooting Question

how to do IP prefix matching efficiently in Python?

Avatar of summer_soccer
summer_soccer asked on
6 Comments1 Solution2808 ViewsLast Modified:
I asked a similar question previously, and got some answers from Mish. I got to implement code as suggested in the link Mish provided, but I found it is very inefficient. My code is attached.

The basic idea is, first I read in all prefixes into a list. There are about 300k such prefixes. Then for each IP address, I need to do a sequential comparison with all such 300k prefixes to find a match. This can take a long time. Further, because I want the longest matching prefix, I cannot stop in the middle when a match is found, because it might not be the longest matching prefix.

I have found an package pysubnettree-0.11 on the Internet, but it requires root privilege to get installed. My code will run on multiple hosts without root privilege.

Does anybody have any ideas how to resolve this problem? Many thanks!
# convert an IP address from its dotted-quad format to its 
    # 32 binary digit representation 
    def ip2bin(self, ip): 
        b = "" 
        inQuads = ip.split(".")
        outQuads = 4
        for q in inQuads:
            if q != "":
                b += self.dec2bin(int(q),8)
                outQuads -= 1
        while outQuads > 0:
            b += "00000000"
            outQuads -= 1
        return b
    # convert a decimal number to binary representation
    # if d is specified, left-pad the binary number with 0s to that length
    def dec2bin(self, n,d=None):
        s = ""
        while n>0:
            if n&1:
                s = "1"+s
                s = "0"+s
            n >>= 1
        if d is not None:
            while len(s)<d:
                s = "0"+s
        if s == "": s = "0"
        return s
    def match_ip_prefix(self, ip, prefix):
        #print 'the prefix is ', prefix
        #print 'the ip is ', ip
        parts = prefix.split("/")
        baseIP = self.ip2bin(parts[0])
        subnet = int(parts[1])
        # Python string-slicing weirdness:
        # "myString"[:-1] -> "myStrin" but "myString"[:0] -> "" 
        if subnet == 32: 
            if self.ip2bin(ip) == baseIP:
                return True
                return False
        # for any other size subnet, print a list of IP addresses by concatenating 
        # the prefix with each of the suffixes in the subnet 
            ipPrefix = baseIP[:-(32-subnet)] 
            ipinbin = self.ip2bin(ip) 
            partip = ipinbin[:-(32-subnet)] 
            #print 'partIP is ', partip, 'ipPrefix is ', ipPrefix 
            if ipPrefix == partip: 
                #print 'they match' 
                return True 
                #print 'they do not match' 
                return False
Join the community to see this answer!
Join our exclusive community to see this answer & millions of others.
Unlock 1 Answer and 6 Comments.
Join the Community
Learn from the best

Network and collaborate with thousands of CTOs, CISOs, and IT Pros rooting for you and your success.

Andrew Hancock - VMware vExpert
See if this solution works for you by signing up for a 7 day free trial.
Unlock 1 Answer and 6 Comments.
Try for 7 days

”The time we save is the biggest benefit of E-E to our team. What could take multiple guys 2 hours or more each to find is accessed in around 15 minutes on Experts Exchange.

-Mike Kapnisakis, Warner Bros