wilfblog

The Problem

For the purpose of this article we will be using private IP address ranges from RFC 1918, reserved for internal networks. Specifically, we will be finding IP ranges within the range 192.168.0.0/16. As we are using PostgreSQL, we can take advantage of its CIDR datatype, which enables the use of special operators to find networks that are within certain ranges. We need to know which entries in the database represent assignable blocks, so we have a boolean field that can be used to control whether a block is available. Finally, we also need to be able to specify the purpose of the networks, so we have a "type" column. So the table structure is as follows:

database=# \d networks;
                                Table "public.networks"
   Column   |         Type          |                     Modifiers
------------+-----------------------+-------------------------------------------
 net        | cidr                  | not null
 name       | text                  |
 type       | text                  |
 assignable | boolean               | default false

Within the range 192.168.0.0/16, there are two smaller blocks that are available for use, 192.168.0.0/24 and 192.168.1.0/24. These are stored in the database as assignable blocks:

 database=# select net, name, type, assignable from networks 
where type = 'TEST' and assignable = true order by net;
      net       |     name      | type | assignable
----------------+---------------+------+------------
 192.168.0.0/24 | Test block #2 | TEST | t
 192.168.1.0/24 | Test block #1 | TEST | t
(2 rows)

Finally, within the 192.168.0.0/24 block, there are 2 existing assignments, which we cannot clash with when assigning new blocks:

database=# select net, name, type, assignable from networks 
where net << '192.168.0.0/24' order by net;
       net       |      name       | type | assignable
-----------------+-----------------+------+------------
 192.168.0.8/29  | Test Assignment |      | f
 192.168.0.32/28 | Test Assignment |      | f
(2 rows)

Now suppose we have a request for a new /29 block, i.e. a block of 8 IP addresses. A person can easily see that the first available space is 192.168.0.0/29, which is followed by the existing block 192.168.8.0/29, then there is another gap at 192.168.0.16/29, then 192.168.24.0/29. But how, for example, is a program to know that there is not an existing assignment at 192.168.0.4/30, which would preclude the use of 192.168.0.0/29? We also need to consider the valid starting points for a network, which are multiples of the network size. For example, 192.168.0.64/26 is a valid assignment of 64 IP addresses, but 192.168.0.32/26 is not.

This is where PHP comes in. And without further ado, you can see the code here. This makes use of the excellent ez_sql database access class by Justin Vincent, which I highly recommend. As you can see, the function findNetworks takes the network type, the required network size, and optionally the quantity of assignments required as its input. It will then return an array containing the first IP address (starting point) of each place where it is possible to assign the required block. The input ($params argument) is an array containing as its first element, an array of the arguments required for the function. This rather strange arrangement is to allow the function to be called as an XML-RPC method, as described later.

How it Works

The basic theory of operation is very simple. First, the script queries the database for the available source blocks of the required type, and puts the results in the $sourceBlocks array. It then goes through each of these in turn using a foreach() loop. Within each source block, it does another database query to get an array of the existing assignments in the database, which are stored in $existingBlocks. It then steps up through the valid starting points in muliples of the block size requested, using a while loop, while the starting point is within the source block being looked at. As you can see, the IP addresses are converted to integers using the ip2long() function, which makes it possible to do normal mathematical functions on IP addresses and means that the code will work on any subnet size.

At all times when a possible starting point to assign the block (the $candidateNet) is being checked, the starting point of the next existing assignment is known (as $existingNetworkIP). If the end of the candidate block is lower than $existingNetworkIP, then there must be a space in the database. For example, if the candidate is 192.168.0.0, which ends at 192.168.0.7 ($size = 8), and the next assigned block starts at 192.168.0.8, then a vacant space has been found.

If, however, this is not the case, then $candidateNet is incremented in multiples of the block size until the end of the existing assignment has been passed. The $existingBlocks array is then also incremented using the next() function, so that $existingBlock is always equal to or higher than the next candidate to be checked. The loop then continues until the desired quantity of assignments or the end of the source blocks has been reached.

Sample Usage - an XML-RPC Client/Server

Next we have a pair of very simple scripts which will allow you to query your IP database from anywhere, using XML-RPC. A good introduction to XML-RPC web services can be found in this devshed.com article. Firstly, the server script, written in PHP. In order to run this, you need to compile PHP with the option '--with-xmlrpc'. You then simply need to serve the script with Apache. Secondly, a very simple client script written in Python. This uses the xmlrpclib library, which should be installed as a standard part of your Python installation.

Finally, if you wish to download all the files, you can find an archive here. Hopefully, if you have read this far, you will find this code useful, so please leave a comment to let me know about it!