CODEWITHSUNDEEP
sqlpostgresqlipsubnet
Arash Outadi
Arash Outadi

Reputation: 456

Find list/ranges of available IP addresses within subnet efficiently

I'm trying to determine what the next available IP address is given a subnet (Basically a beginning IPv4 address and an ending IPv4 address) and a addresses table which contains the already assigned IPv4 addresses.

A simplified schema of the table:

CREATE TABLE addresses (
    address INET NOT NULL,
    -- OTHER INFORMATION ASSOCIATED WITH IP ADDRESSES --
);

The current implementation generates all possible IP addresses within the subnet and returns those NOT in the addresses table.

For example, given a subnet with a start IP of '192.0.0.0' and end IP of '192.0.0.255' the query would look like this:

SELECT * 
FROM (
  SELECT i + '0.0.0.0' :: inet as generated_address
  from generate_series('192.0.0.0' :: inet - '0.0.0.0' :: inet,
                       '192.0.0.255' :: inet - '0.0.0.0' :: inet) as i) as iprange
                       WHERE generated_address NOT IN (SELECT address FROM addresses);

This works correctly, but the issue is that is that for subnet masks of /12 and lower it begins to slow, and does not finish for subnet mask of /8 at all.

I'm trying to determine alternative methods for finding the Next Available IP addresses.
Furthermore, it would be ideal if I could return a list of available IP addresses or a list of ranges (That represent the gaps of available IP addresses between the unavailable ones).

There seem to some good answers related to this question on this post but I'm finding it difficult to understand the answers in that post and translating them to my situation in postgres (As I am fairly new to it).

DATA

I'm not totally sure what the data will look like but the 3 scenarios for how the addresses table is filled are the following:

  1. Sparse (Very little IP addresses assigned)
  2. Choppy (Half of subnet filled but with lots of gaps between)
  3. Dense (Most IP addresses taken)

The worst case is likely scenario 3, as it would involve looking at all the records.

I've provided a simple DB Fiddle that demonstrates the scenario.

Upvotes: 1

Views: 1397

Answers (1)

Arash Outadi
Arash Outadi

Reputation: 456

I have managed to come up with something like this:

WITH gaps (start_ip, end_ip) as 
(
   SELECT
      address + 1 AS start_ip,
      next_address - 1 AS end_ip 
   FROM
      (
         SELECT
            address,
            LEAD(address) OVER (
         ORDER BY
            address) AS next_address 
         FROM
            addresses 
         where
            and address >= '192.0.0.0' :: INET -- Start Address
            and address <= '192.0.255.255' :: INET -- End Address
      )
      AS gaps 
   WHERE
      gaps.address + 1 <> gaps.next_address
)
SELECT
   generate_series(start_ip - '0.0.0.0' :: INET, end_ip - '0.0.0.0' :: INET) + '0.0.0.0'::INET as address 
FROM
   gaps

Again most of it is essentially a translation from answers in this post but I thought it still might help others to have it here.

The general idea is to look for "gaps" in the addresses table (Already assigned addresses in here) which means that everything in between is "free". If the next_address from LEAD is only 1 greater than the current address that means that the next address is occupied and there is no gap. Here is a DBFiddle

I'm still looking for more efficient solutions, especially in situation when the addresses table is very dense or full, the worst case is if only the last IP address in the subnet is free...

Upvotes: 1

Related Questions