We are looking for free IPv4 in BGP full-view

We all know that IPv4 addresses have already ended and more than once . Most recently, this was quite a popular topic for discussion, including on Habrahabr : they made plans and forecasts , counted losses . In the yard in 2016, but IPv4 is still in service.

On April 21, the RIPE NCC published a brief technical news about the very exhaustion of IPv4 addresses. Actually, the meaning of the news is that the graph has been updated showing the current position with free addresses from which RIPE is left at its disposal almost on the full block / 8. APNIC only has half / 8. Probably, the rigid address distribution policy is doing its job and this latest / 8 RIRs will drag on for a very long time.

But all this refers to the "paper" addresses. And how many real addresses are available for routing to the Internet? More precisely, how many addresses possible for routing to the Internet is not used. To calculate this, we will use a unique live witness - the BGP routing table.
')
Further, some technical details on how to calculate the results of this calculation.

BGP full-view contains all the addresses available for routing, currently about 600,000 prefixes. The table with addresses looks like this:

 * 1.1.8.0/24 216.221.157.162 0 0 0 40191 3257 4134 i
 * 1.1.8.0/24 147.28.7.2 0 0 0 3130 1239 4134 i
 * 1.1.8.0/24 185.44.116.1 0 0 0 47872 3356 4134 i
 * 1.1.8.0/24 80.91.255.137 0 0 0 1299 4134 i
 * 1.1.16.0/20 80.241.176.31 0 0 0 20771 47872 286 49597 i
 * 1.1.16.0/20 185.44.116.1 0 0 0 47872 286 49597 i
 * 1.1.16.0/20 134.222.87.1 750 0 0 286 49597 i
 * 1.1.20.0/24 85.114.0.217 0 0 0 8492 9304 18046 133948 e
 * 1.1.20.0/24 185.44.116.1 0 0 0 47872 9304 18046 133948 i

for calculations we need only the prefixes themselves (the first column).

The prefixes are sorted in ascending order, and the shorter prefix of the same network will always be ahead of the long one. This will greatly simplify the search for spaces in the table, since only 3 situations are possible:

1. One prefix includes the other (the first includes the second, but not vice versa), or they are equal;
2. Prefixes are summed to one with a shorter mask;
3. Prefixes are consecutive, but not cumulative.

In all other cases, there is a hole between the prefixes, and then we need to write it down.

I did not begin to look for ready-made solutions, perhaps the same could be done using ipaddress . In my implementation, the stack is used as the main working tool:

for line in fileinput.input(): prefix = ipv4num(line) while len(ipstack): cur_prefix = ipstack.pop() sum_prefix = netsum(cur_prefix, prefix) if sum_prefix[0]: prefix = sum_prefix continue elif issubnet(cur_prefix, prefix): prefix = cur_prefix break elif isseq(cur_prefix, prefix): if prefix[1] <= cur_prefix[1]: ipstack[:] = [] break else: ipstack.append(cur_prefix) break else: for gapprefix, mask in subnets(cur_prefix[0] + ipaddrcount(cur_prefix[1]), prefix[0]): print "{}/{}".format(numipv4(gapprefix), mask) ipstack[:] = [] break ipstack.append(prefix) 

The whole code can be picked up on Github .

The prefix received at the input is compared with the fact that it is on the stack to fulfill one of the 3 conditions listed above:

1. If the prefixes are summed up then we perform the summation and continue moving to the bottom of the stack, comparing the already summed prefix with the new one taken from the top in the hope that it can again be summed up;
2. If the prefix from the stack includes the prefix at the input, then go to the next prefix from the input, returning the prefix to be checked to the top of the stack;
3. If the prefixes follow each other and the prefix mask from the input is longer than the one taken from the stack, then put the new prefix on the top (later it can be summed up with other prefixes from the input). If the mask is shorter or equal, it makes no sense to keep the entire previous stack, since in any case all further checks will be only with the new prefix. The stack is cleared, the incoming value is put on top.

If none of this happens, then we calculate the starting and ending address of the gap for convenience, convert it into prefix notation.

It remains only to take BPG full-view. It would be possible to use the nearest BGP router at hand, but not everyone has this opportunity. Therefore, take the data from here www.routeviews.org - a good research, academic resource. The archive itself with data in which the Internet routing tables are collected for a considerable period of time is located here archive.routeviews.org/oix-route-views . I selected the file for April 20th .

The table is slightly noisy with addresses from a private address space and / 32 addresses. Therefore, everything was filtered to the prefix / 24 (which corresponds to practical realities), repeated prefixes were removed. Nothing special was invented for this - the grep and uniq tools were used. It was the longest 10 minute process.

As a result, the source table contains 628,105 prefixes, more than half of them 344,704 falls on / 24. In my opinion, a good indicator of the shortage of addresses, since due to a shortage, the address space is fragmented. 8697 prefixes are not under the control of the RIR and belong to the organizations that received them until the formation of the RIR. The shortest announced prefix / 8 of them in total in Table 16, 13 of which, again, are not under the authority of the RIRs.


_{LEGACY - addresses not under the administration of the RIRs.}


The routing table contains overlapping prefixes. In order to get some data you need to go further. We will not do this, it is much more interesting to count how many addresses are not routed.

We execute our script and get the result. Since before this, the prefixes from the private address space were cleaned from the source table and some special addresses appeared again, but not in the table already non-routable (which confirms the correctness of the program's operation). We clean them again. It makes no sense to take them into account - most likely they will never be used for routing. For a moment we pay attention to the block 240.0.0.0/4 where 1/16 of all addresses is mothballed.

From the address space that is left is not routed in a total of 79 blocks by / 8. ARIN accounts for 39, for APNIC 12, for RIPE 7. In fact, a second Internet can be built from this. Recall that RIPE reports only one unallocated block / 8.





The largest non-routable block is from 28.0.0.0 to 30.255.255.255 . It belongs to two organizations according to this document DSI-North and Defense Information Systems Agency .

It is worth noting that the address blocks that are under the administrative control of the RIR could have come to them in fact. For example, the 7.0.0.0/8 block administered by ARIN is wholly owned by the DoD Network Information Center as judged by whois ARIN and is not routed. The total number of addresses in such blocks corresponds to approximately 42 address spaces with the / 8 prefix.

It is interesting to observe that sometimes in a solid block, for example, 13.128.0.0/9 or 29.0.0.0/8, there are objects distributed inetnum and route, but still there is nothing globally seen.

In some cases, the company has a large continuous block, for example, 2.0.0.0/12 , but apparently due to the uselessness it announces only a part of this block. Spaces are obtained in 2.7.0.0/16 and 2.15.0.0/16 . It may be a trifle, but precisely / 16 is the peak at the free addresses.

If you look back a little and take the data for April 20, 2011 , we get the following picture.





There were more addresses, almost 1/3 of them. During this time, all the RIRs spent the addresses of someone not so much, some very many, like LACNIC, but in general from 1/3 to half. It can be seen that the non-directly administered RIR addresses have remained almost in full strength. On the contrary, some of the addresses were freed. It turns out that at the dawn of the development of the Internet, one-fifth of all addresses were distributed that are still not used. More precisely, they can be used somewhere locally, but in our reality BGP Internet access does not exist.

I didn’t expect so many addresses to be seen in BGP full-view. Someone allocated them a lot, but that they are not used at all. Of course, I was embarrassed and I began to look for where I was wrong. I was mistaken seriously and repeatedly, but after all corrections the final result did not change much. Maybe I did not find everything or think wrongly. In the end, I checked all the blocks corresponding to AFRINIC manually for the presence in the routing table of my BGP routers and made sure, at least, in this case it’s considered true.

From the original idea to compare the free blocks in the routing table with the RIR databases had to be abandoned, too many addresses. I put all the received dumps next to the script that calculates spaces in the list of prefixes, calling everyone to try to repeat my calculations. In the meantime, we look with envy at the pioneers who are certainly not facing a shortage of addresses, not in the near future. The survey is relevant: