IP address accounting system

In our practice, we quite often have to deal with the problem of rational distribution of blocks of IP addresses. The distribution of addresses between thousands of customers is a rather difficult task. In this article we would like to share our own experience in solving it.

A bit about the principles of IP addressing

Before talking about the problems of dividing the address space, we recall the basic principles of IPv4 addressing. An IPv4 address is a set of 32 bits (ones and zeros). It’s quite difficult for a person to read and remember a binary IP address. Therefore, 32 bits are divided into four bytes - the so-called octets. To facilitate understanding, all octets are written in decimal form. Each IPv4 address consists of two parts: the first identifies the network, and the second the node on the network. Such addressing is called hierarchical: the first part of the address identifies the entire network in which all unique addresses are located. Routers only need to know the path to each network, and not the location of individual nodes.

So that the nodes can determine where the network part is located, and where is the node address, a subnet mask is used. The subnet mask is assigned to the host at the same time as the IP address. It is a 32-bit set in which the units correspond to the network part and the zeros to the host address. Today, the recording of IP addresses in the so-called prefix or CIDR notation is widespread. The mask in such an entry is indicated as a number after the slash. For example, the mask 255.255.255.0 in binary form will look like this: 11111111.11111111.11111111.00000000. The number of units is 24, and the mask is written as / 24.

Manual highlighting issues

In many organizations, the allocation of IP addresses is carried out manually, without the use of any specialized software tools. Manual allocation sooner or later leads to confusion with addressing. Firstly, manual allocation inevitably leads to fragmentation: clients are provided with many small subnets, which makes it impossible to allocate a larger subnet.

Secondly, the need to allocate subnets of different sizes also leads to various difficulties. As an example of a possible problem situation, we can cite the case when the client is allocated a subnet / 27 or / 28, from which the / 29 block has already been allocated. Is it possible to somehow automate the process of allocating addresses in order to avoid errors at all? Reflecting on this issue, we found our solution that works great thanks to good visualization.

Spanning Tree and Free Subnet Table

To search for free subnets, we use the interval tree. With it, you can find intervals that intersect with a given interval or point. The IP address can be represented as a decimal number, so that we can easily determine the boundaries of the pool and present all occupied subnets as segments in a large interval.

The free subnet search algorithm can be described as follows. Suppose a client asks for a / 27 subnet. First you need to make sure that the existing pool is larger than this subnet. If it is smaller, then you will either need to take another pool, or inform the client about the lack of free subnets of the required size. If the pool is larger than the requested subnet in size, then we begin to move from the beginning of the pool in segments the size of the desired subnet (its size is 2 ^ (32-x), where x is the subnet prefix).

Using the previously constructed interval tree, we can quickly determine whether the client's subnet overlaps, represented as an interval, by the previously allocated subnets. The subnet 127.0.0.0/27 in our example overlaps one dedicated / 29 subnet. Then the interval is taken, following it - 127.0.0.32/27. We check it for intersection with others, and it turns out to be free. After that, it is provided to the client and marked as busy. All information about free subnets is visually displayed in the form of the following table (green indicates free subnets, blue indicates busy ones, and gray indicates subnets that contain already occupied smaller subnets and therefore cannot be used):



To speed up the search for a free subnet in large pools, you can cycle through the interval from different sides. However, in this case, the extent of fragmentation will be larger, and there may be problems with the allocation of large subnets. If we find an intersection with a larger subnet (compared to the requested client), then we can start the next step of the cycle from its end, since there are still no free subnets inside this interval.

Conclusion

Our proposed IP address allocation solution makes address space management easier and, more importantly, more efficient.

Of course, it cannot be considered ideal. The question of rational and efficient allocation of address space remains open. It would be interesting to hear from you comments and suggestions for improving our approach, as well as familiarize yourself with other options for solving the described problem.

Readers who are not able to comment on posts on Habré are welcome to our blog .