Efficiently detect overlapping networks

Question

I know how to detect overlapping networks. There are two ways to do this: by using netaddr's "IPNetwork in IPNetwork" or ipaddress's "overlaps" method. The question is how to find overlapping networks in array in most efficient way.

At the moment, I use this code:

networks = {
    IPNetwork('10.1.0.0/24'): 'net2',
    IPNetwork('10.0.0.0/8'): 'net1',
    IPNetwork('10.0.0.0/16'): 'net3',
    IPNetwork('10.0.0.0/24'): 'net4',
    IPNetwork('192.168.0.0/16'): 'net5',
    IPNetwork('192.168.0.0/23'): 'net6',
    IPNetwork('192.168.1.0/24'): 'net7',
    IPNetwork('172.16.0.0/12'): 'net8'
}

net = sorted([key for key in networks.keys()])
for pi in range(0, len(net)-1):
    for si in range(pi+1, len(net)):
        if net[si] in net[pi]:
            print(f'{net[si]} ({networks[net[si]]}) overlaps with '
                  f'{net[pi]} ({networks[net[pi]]})')

It does the job, but uses many iterations (e.g. for 8 entries there are 7+6+5+... = 28 comparisons) and I'm looking for a more efficient way.

Answer 1

I recently had to solve this problem in firewalld.

You can achieve O(n) detection by presorting the networks ahead of time. Python sorts networks first by network bits (ip address) and then by netmask. This plus address normalization done by IPv4Network means that overlapping entries will be adjacent in the sorted list.

The detection is then done by comparing adjacent items:

from ipaddress import IPv4Network

networks = {
    IPv4Network('10.1.0.0/24'): 'net2',
    IPv4Network('10.0.0.0/8'): 'net1',
    IPv4Network('10.0.0.0/16'): 'net3',
    IPv4Network('10.0.0.0/24'): 'net4',
    IPv4Network('192.168.0.0/16'): 'net5',
    IPv4Network('192.168.0.0/23'): 'net6',
    IPv4Network('192.168.1.0/24'): 'net7',
    IPv4Network('172.16.0.0/12'): 'net8'
}

networks_list = sorted(networks.keys())

prev_network = networks_list.pop(0)
for current_network in networks_list:
    if prev_network.overlaps(current_network):
        print("Network {} overlaps {}".format(prev_network, current_network))
    prev_network = current_network

Results:

Network 10.0.0.0/8 overlaps 10.0.0.0/16
Network 10.0.0.0/16 overlaps 10.0.0.0/24
Network 192.168.0.0/16 overlaps 192.168.0.0/23
Network 192.168.0.0/23 overlaps 192.168.1.0/24