Search code examples
javanetwork-programmingroutescidr

Find Free Prefixes within a CIDR netblock

I'm trying to figure out a way to determine "free prefixes" within a CIDR netblock given the netblock and a list of assignments from within it.

For example:

let netblock = 10.0.0.0/22

let assignments = { 10.0.0.0/24, 10.0.1.0/24 }

What would be the most computationally efficient way of figuring out the "free" netblocks from within 10.0.0.0/22? I need to output 10.0.2.0/23 for the above example.

I've tried researching and have mostly come up empty. The only way that comes to my mind (probably due to my inexperience with network programming) is:

  1. CIDR -> list of IPs expansion
  2. Match on the common IPs and remove them from the list
  3. Convert the modified list back to the CIDR notation.

This however sounds fairly inefficient (I would call it the "bruteforce" approach).

I'm fine with a general algorithm, it doesn't have to be a Java specific answer.

Thank you! :)

Solution

  • Given an address x/y, when you subtract it from a set of addresses, what you have left is the addresses in the set a/y, where a < x, and the addresses in the set b/y, where b > x

    So in your example, that leaves 10.0.1-3.0/24 when you subtract 10.0.0.0/24 from 10.0.0.0/22.

    There are no addresses x/24 in 10.0.0.0/22 where x < 10.0.0.0. The addresses y/24 in 10.0.0.0/22 where y > 10.0.0.0 are 10.0.1.0/24, 10.0.2.0/24, and 10.0.3.0/24, or 10.0.1-3.0/24.

    Another way to look at it: you are removing all addresses whose first 24 bits are 10.0.0

    So that leaves all addresses whose first 24 bits are bigger, and all addresses whose first 24 bits are smaller. Each of those can be expressed as a range.

    Just repeat this process iteratively.