IP Addressing System

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

A little about the principles of IP addressing

Before we talk about the problems of dividing the address space, recall the basic principles of IPv4-addressing. An IPv4 address is a collection of 32 bits (ones and zeros). It is 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 one identifies the network, and the second the node in the network. Such an addressing is called hierarchical: the first part of the address identifies the entire network in which all the unique addresses are located. Routers need to know only the path to each network, and not the location of individual nodes.
')
In order for the nodes to determine where the network part is located, and where the node address is, a subnet mask is used. A subnet mask is assigned to a node at the same time as an IP address. It is a set of 32 bits in which the units correspond to the network part, and zeros to the node address. Today, the recording of IP addresses in the so-called prefix or CIDR notation has become widespread. The mask in such a record is indicated as a number after a 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 problems

In many organizations, the allocation of IP-addresses is carried out manually, without the use of any specialized software. Manual allocation sooner or later leads to confusion with addressing. First, 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, there is a case when the client is assigned a / 27 or / 28 subnet, from which / 29 is already allocated. Is it possible to somehow automate the process of allocating addresses in order to avoid errors at all? Reflecting on this issue, we have found our solution, which works perfectly thanks to good visualization.

Interval tree and table of free subnets

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

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

Using the previously constructed interval tree, we can quickly determine whether the subnet that is needed by the client, represented as an interval, overlaps the previously selected subnets. The subnet 127.0.0.0/27 in our example overlaps one selected subnet / 29. Then the interval following it is taken - 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 clearly displayed in the following table (green shows free subnets, blue ones are occupied, and gray ones are subnets that contain smaller subnets already occupied 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 scale of fragmentation will be larger, and problems may arise with the allocation of large subnets. If we find an intersection with a larger subnet (compared to the one requested by the client), then we can start the next step of the cycle from its end, since there are still no free subnets within this interval.

Conclusion

Our proposed solution for the allocation of IP-addresses makes the management of the address space more simple and, importantly, more rational.

Of course, it cannot be considered ideal. The question of the 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 to get acquainted with other solutions to the described problem.

Readers who are not able to comment on posts on Habré, we invite to our blog .