How to find remaining IP space in a CIDR

[micruzz82]

Hi Sean

I just wanted to present another idea I was looking into which was to find out all the remaining IP space available, if IP allocation was randomly done. This code uses breadth first search and is able to provide the information required. If this is also possible with ipaddress-go then it would be a really good addition.

#!/usr/bin/env python3.4

import ipaddress
import argparse
import queue

def get_available_subnets(main, taken):
    # we assume no subnets are available intially
    available = []
    q = queue.Queue()
    # add first node for expansion in the BFS process
    q.put(main)

    while q.qsize() > 0:
        subnet = q.get()
        for taken_subnet in taken:
            if taken_subnet.compare_networks(subnet) == 0:
                # found matching subnet in taken, stop expanding
                print("similar: %s and %s" % (subnet, taken_subnet))
                break
            if taken_subnet.overlaps(subnet):
                # still has overlaps somewhere in children, keep expanding
                print("overlaps: %s and %s" % (subnet, taken_subnet))
                for sub_subnet in subnet.subnets():
                    q.put(sub_subnet)
                break
        else:
            # no overlaps with taken - this subnet is entirely available
            available.append(subnet)

    return available

if "__main__" == __name__:
    parser = argparse.ArgumentParser()
    parser.add_argument('-m', '--m', help='main subnet to check', required=True)
    parser.add_argument('-t', '--taken', nargs='+', help='taken subnets', required=True)
    args = parser.parse_args()

    taken = [ipaddress.IPv4Network(subnet) for subnet in args.taken]
    main = ipaddress.IPv4Network(args.m)
    available = get_available_subnets(main, taken)

    print("Available IP space:")
    for avl in available:
        print(ipaddress.ip_network(avl))

Output:

python script.py -m 10.255.255.0/24 -t 10.255.255.192/26 10.255.255.128/30

overlaps: 10.255.255.0/24 and 10.255.255.192/26
overlaps: 10.255.255.128/25 and 10.255.255.192/26
overlaps: 10.255.255.128/26 and 10.255.255.128/30
similar: 10.255.255.192/26 and 10.255.255.192/26
overlaps: 10.255.255.128/27 and 10.255.255.128/30
overlaps: 10.255.255.128/28 and 10.255.255.128/30
overlaps: 10.255.255.128/29 and 10.255.255.128/30
similar: 10.255.255.128/30 and 10.255.255.128/30

Available IP space:
10.255.255.0/25
10.255.255.160/27
10.255.255.144/28
10.255.255.136/29
10.255.255.132/30

Any help on how to work out a similar code would be much appreciated.

[micruzz82]

Addressed by https://github.com/seancfoley/ipaddress-go/issues/1#issuecomment-1243046683

[seancfoley]

The following code works identically and produces identical output to your python code, except for the fact I am hard-coding the command-line args rather than using go's "flags" package:

package main

import (
    "fmt"
    "github.com/seancfoley/ipaddress-go/ipaddr"
)

func main() {
    taken := []*ipaddr.IPAddress{addr("10.255.255.192/26"), addr("10.255.255.128/30")}
    main := addr("10.255.255.0/24")
    available := get_available_subnets(main, taken)
    fmt.Println("\nAvailable IP space:")
    for _, avl := range available {
        fmt.Println(avl)
    }
}

func get_available_subnets(mainSubnet *ipaddr.IPAddress, taken []*ipaddr.IPAddress) []*ipaddr.IPAddress {
    var available, q []*ipaddr.IPAddress
    q = append(q, mainSubnet)
    matched := false
    for len(q) > 0 {
        subnet := q[0]
        q = q[1:]
        for _, taken_subnet := range taken {
            if matched = subnet.Equal(taken_subnet); matched {
                // found matching subnet in taken, stop expanding
                fmt.Printf("similar: %s and %s\n", subnet, taken_subnet)
                break
            }
            if matched = subnet.Contains(taken_subnet); matched {
                // still has overlaps somewhere in children, keep expanding
                fmt.Printf("overlaps: %s and %s\n", subnet, taken_subnet)
                iter := subnet.AdjustPrefixLen(1).PrefixBlockIterator()
                for iter.HasNext() {
                    sub_subnet := iter.Next()
                    q = append(q, sub_subnet)
                }
                break
            }
        }
        if !matched {
            // no overlaps with taken - this subnet is entirely available
            available = append(available, subnet)
        }
    }
    return available
}

func addr(addrStr string) *ipaddr.IPAddress {
    return ipaddr.NewIPAddressString(addrStr).GetAddress()
}