Calculate number of available subnets in given network

Question

I have following issue in calculating the number of available subnets (or hosts) in network. For example the main subnet is /24 (255.255.255.0) which contains two /25 (255.255.255.128) or four /26 (255.255.255.192).

So if the one node is already being used there will be only one /25 or only 3 times /26. Then how should I calculate the number of available subnets. In other words how to get the number and type of remainders. I want to perform this algorithm in PHP.

Answer 1

I used python to solve this problem (all code is attached, entire script in the end), but I'm sure similar libraries for the solution exist for PHP. Since this is old and no solutions were posted, I'm guessing any solution (in this case, the Python solution) is better than no solution.

The script consists of two function, one calculates the available subnets within a "main" subnets using BFS, and the other creates a pdf drawing using graphviz.

The algorithm I used is a very simple BFS. It basically starts from the top subnet ("main", /24) and finds out if any of the used ("taken") subnets overlap/match with it. If any of them does, the algorithm queues it's "children" (/25) to be checked in the same process. If the algorithm hits a subnet that has no "taken" children it is marked as "available". If it hits a subnet that exactly matches a "taken" it is marked as "taken". In any other case the iteration continues.

The drawing process for the visualization is identical.

Here is the script description (argparse-generated):

usage: script.py [-h] -m M -t TAKEN [TAKEN ...] -o OUTPUT

optional arguments:
  -h, --help            show this help message and exit
  -m M, --m M           main subnet to check
  -t TAKEN [TAKEN ...], --taken TAKEN [TAKEN ...]
                        taken subnets
  -o OUTPUT, --output OUTPUT
                        graphviz output file name (.pdf)

Running the script using your parameters:

subnet_script.py -m 255.255.255.0/24 -t 255.255.255.192/26 -o test

Gives these results:

Doing something a little more interesting like:

script.py -m 255.255.255.0/24 -t 255.255.255.192/26 255.255.255.128/30 -o test

Gives these results:

I've used the ipaddress, queue and graphviz (for python) modules, as well as argparse to make the script nicer to use.

The first function:

def get_available_subnets_set(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 set(available)

The second function draws the results using graphviz in a similar manner:

def make_subnet_graph(main, taken_subnets, available_subnets, filename):

    g = graphviz.Graph()
    q = queue.Queue()
    q.put(main)
    g.node(str(main))

    while q.qsize() > 0:
        subnet = q.get()
        for sub_subnet in subnet.subnets():
            if sub_subnet in available_subnets:
                # draw as available (green)
                g.node(str(sub_subnet), _attributes={"color": "green"})
                g.edge(str(sub_subnet), str(subnet))
                continue
            if sub_subnet in taken_subnets:
                # draw as taken (red)
                g.node(str(sub_subnet), _attributes={"color": "red"})
                g.edge(str(sub_subnet), str(subnet))
                continue

            # has mixed type subnets (taken / available) - go deeper
            g.node(str(sub_subnet))
            g.edge(str(sub_subnet), str(subnet))
            q.put(sub_subnet)

    # write file
    g.render(filename)

The entire thing together with argparse:

#!/usr/bin/env python3.4

import ipaddress
import argparse
import queue
import graphviz


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

def make_subnet_graph(main, taken_subnets, available_subnets, filename):

    g = graphviz.Graph()
    q = queue.Queue()
    q.put(main)
    g.node(str(main))

    while q.qsize() > 0:
        subnet = q.get()
        for sub_subnet in subnet.subnets():
            if sub_subnet in available_subnets:
                # draw as available (green)
                g.node(str(sub_subnet), _attributes={"color": "green"})
                g.edge(str(sub_subnet), str(subnet))
                continue
            if sub_subnet in taken_subnets:
                # draw as taken (red)
                g.node(str(sub_subnet), _attributes={"color": "red"})
                g.edge(str(sub_subnet), str(subnet))
                continue

            # has mixed type subnets (taken / available) - go deeper
            g.node(str(sub_subnet))
            g.edge(str(sub_subnet), str(subnet))
            q.put(sub_subnet)

    # write file
    g.render(filename)


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)
    parser.add_argument('-o', '--output', help='graphviz output file name (.pdf)', required=True)
    args = parser.parse_args()

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

    make_subnet_graph(main, taken, available, args.output)