4

我有一个包含近 200'000 个网络地址类型的 postgres 数据库。我想检测某些子网是否重叠，例如，检测 123.0.0.0/16、123.2.0.0/24 和 123.3.4.128/30 并报告它们。

我已经在使用很多 python 脚本和 netaddr 库。

考虑到条目的数量，检测重叠的最佳方法/算法是什么？

我很确定有比将每个条目与整个数据库进行比较更好的方法。

4

2 回答 2

5

我认为以下应该是一种相当有效的方法：

import netaddr
import bisect

def subnets_overlap(subnets):
    # ranges will be a sorted list of alternating start and end addresses
    ranges = []
    for subnet in subnets:
        # find indices to insert start and end addresses
        first = bisect.bisect_left(ranges, subnet.first)
        last = bisect.bisect_right(ranges, subnet.last)
        # check the overlap conditions and return if one is met
        if first != last or first % 2 == 1:
            return True
        ranges[first:first] = [subnet.first, subnet.last]
    return False

例子：

>>> subnets_overlap([netaddr.IPNetwork('1.0.0.0/24'), netaddr.IPNetwork('1.0.0.252/30')])
True
>>> subnets_overlap([netaddr.IPNetwork('1.0.0.0/24'), netaddr.IPNetwork('1.0.1.0/24')])
False
于 2013-09-23T22:37:55.243 回答
1 
import sys
import ipaddr
from pprint import pprint

from netaddr import IPNetwork, IPAddress
matching_subent=[]
def cidrsOverlap(cidr0):
    subnets_list = [IPNetwork('123.0.0.0/16'),
                    IPNetwork('123.2.0.0/24'), 
                    IPNetwork('123.132.0.0/20'),
                    IPNetwork('123.142.0.0/20')]
    flag = False
    for subnet in subnets_list:
        if (subnet.first <= cidr0.last and subnet.last >= cidr0.last): 
            matching_subent.append(subnet)


    print "Matching subnets for given %s are %s" %(cidr0, matching_subent)
    pprint(subnets_list) 

cidrsOverlap(IPNetwork(sys.argv[1]))
于 2016-10-18T09:50:41.663 回答