Ищем свободные IPv4 в BGP full-view

Все мы знаем что IPv4 адреса уже закончились и не один раз. Совсем недавно это была достаточно популярная для обсуждения тема в том числе и на Habrаhabr: строили планы и прогнозы, подсчитывали убытки. На дворе 2016 год, но IPv4 по прежнему в строю.

21 Апреля RIPE NCC опубликовал коротенькую техническую новость про то самое исчерпание IPv4 адресов. Собственно смысл новости — обновился график показывающий текущее положение со свободными адресами у RIPE которых осталось у него в распоряжении почти на полный блок /8. У APNIC только половина /8. Вероятно, жёсткая политика распределения адресов делает своё дело и этот самый последний /8 RIR'ы будут тянуть очень долго.

Но всё это относится к «бумажным» адресам. А сколько реальных адресов доступно для маршрутизации в Интернет? Точнее сколько адресов из возможных для маршрутизации в Интернет не используется. Чтобы это посчитать мы воспользуемся уникальным живым свидетелем — таблицей маршрутизации BGP.

Далее немного технических деталей как посчитать и результаты этого расчёта.

BGP full-view содержит все доступные для маршрутизации адреса, на текущий момент около 600000 префиксов. Таблица с адресами выглядит примерно так:

*  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

нам для расчётов нужны только сами префиксы (первый столбец).

Префиксы отсортированы по возрастанию, причём более короткий префикс той же сети будет всегда впереди длинного. Это нам очень упростит поиск пробелов в таблице, так как возможны только 3 ситуации:

1. Один префикс включает другой (первый включает второй, но не наоборот), или они равны;
2. Префиксы суммируются в один с более короткой маской;
3. Префиксы идут подряд, но не суммируются.

Во всех остальных случаях между префиксами дырка, нам то её и надо записать.

Я не стал искать готовые решения, возможно, то же самое можно было сделать используя ipaddress. В моей реализации применяется стек в качестве основного рабочего инструмента:

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)

Код целиком можно забрать на Github.

Полученный на входе префикс сравнивается с тем что в стеке на предмет выполнения одного из 3-х вышеперечисленных условий:

1. Если префиксы суммируются то выполняем суммирование и продолжаем движение ко дну стека, сравнивая уже суммированный префикс с новым взятым с вершины в надежде, что он опять может быть суммируется;
2. Если префикс из стека включает в себя префикс на входе, то переходим к следующему префиксу со входа, возвращая проверяемый префикс на вершину стека;
3. Если префиксы идут друг за другом и маска префикса со входа длиннее того что взят из стека, то кладём новый префикс на вершину (в дальнейшем он может быть просуммирован с другими префиксами со входа). Если маска короче или равна, то нет смысла держать весь предыдущий стек, так как в любом случае все дальнейшие проверки будут только с новым префиксом. Стек очищаем, поступившее значение кладём на вершину.

Если ничего этого не происходит, то вычисляем начальный и конечный адрес промежутка для удобства преобразуем в префиксную нотацию.

Осталось только взять BPG full-view. Можно было бы воспользоваться ближайшим BGP маршрутизатором находящимся под рукой, но такая возможность есть далеко не у всех. Поэтому возьмём данные отсюда www.routeviews.org — хороший исследовательский, академический ресурс. Сам архив с данными в котором собраны таблицы маршрутизации Интернет за солидный промежуток времени находится здесь archive.routeviews.org/oix-route-views. Я выбрал файл за 20 Апреля.

Таблица слегка зашумлёна адресами из частного адресного пространства и адресами /32. Поэтому всё было отфильтровано до префикса /24 (что соответствует практическим реалиям), были убраны повторные префиксы. Ничего специально для этого не придумывалось — использовались инструменты grep и uniq. Это был самый долгий процесс минут на 10.

В результате исходная таблица содержит 628105 префиксов, больше половины из них 344704 приходится на /24. На мой взгляд хороший показатель нехватки адресов, так как вследствие дефицита происходит дробление адресного пространства. 8697 префикса не находятся в управлении RIR и принадлежат организациям получившим их до момента образования RIR. Самый короткий анонсируемый префикс /8 всего их в таблице 16, 13 из которых опять же не находятся в ведении RIR'ов.


_{LEGACY — адреса не находящиеся в административном управлении RIR'ов.}

Исходные данные

	TOTAL	ARIN	RIPE	APNIC	AFRINIC	LACNIC	LEGACY
/24	344704	120580	81055	92632	8293	35894	6250
/23	61168	20135	17563	13976	1373	7332	789
/22	72588	24472	19366	17587	1799	8803	561
/21	44409	11721	13596	11143	1376	6250	323
/20	40035	13363	8312	12006	712	5320	322
/19	27055	7140	6929	7131	540	5222	93
/18	13300	3868	3114	4229	558	1465	66
/17	7928	2431	2145	2235	257	810	50
/16	13212	5563	2600	3894	315	660	180
/15	1804	502	557	506	56	156	27
/14	1052	280	276	295	58	135	8
/12	516	123	121	233	31	5	3
/11	269	96	50	101	17	2	3
/10	36	13	9	14	0	0	0
/9	13	4	0	0	0	0	9
/8	16	2	0	1	0	0	13
/7	0	0	0	0	0	0	0
Всего:	628105	210293	155693	165983	15385	72054	8697

Таблица маршрутизации содержит пересекающиеся префиксы. Для того чтобы выудить какие-то данные надо углубляться дальше. Делать мы этого не будем, гораздо интереснее посчитать сколько адресов не маршрутизируется.

Выполняем наш скрипт и получаем результат. Так как перед этим из исходной таблицы были вычищены префиксы из частного адресного пространства и некоторые специальные адреса они опять появились, но уже в таблице немаршрутизируемых (что подтверждает правильность работы программы). Вычищаем их ещё раз. Нет смысла их брать во внимание — скорее всего они никогда не будем использоваться для маршрутизации. Мельком обращаем внимание на блок 240.0.0.0/4 где законсервировано 1/16 всех адресов.

Из того адресного пространства что осталось не маршрутизируется в общей сумме 79 блоков по /8. На ARIN приходится 39, на APNIC 12, на RIPE 7. Фактически из этого можно построить второй Интернет. Напомним, что RIPE рапортует всего об одном нераспределённом блоке /8.

Свободные префиксы

	TOTAL	ARIN	RIPE	APNIC	AFRINIC	LACNIC	LEGACY
/24	27358	14225	6213	5287	401	1211	21
/23	18763	10260	4159	3419	257	648	20
/22	15170	7469	3618	3363	221	479	20
/21	8366	4533	1684	1650	139	336	24
/20	5312	3081	819	1069	74	236	33
/19	3355	2011	426	701	56	136	25
/18	1959	1254	181	397	31	76	20
/17	1194	750	127	241	22	43	11
/16	1907	1405	168	251	24	47	12
/15	586	381	69	106	11	7	12
/14	193	114	20	38	8	2	11
/12	70	31	9	17	6	0	7
/11	40	19	1	9	2	0	9
/10	16	4	1	4	1	0	6
/9	8	1	0	0	0	0	7
/8	10	1	0	0	1	0	8
/7	1	0	0	0	0	0	1

Свободные префиксы приведённые к /24

	TOTAL	ARIN	RIPE	APNIC	AFRINIC	LACNIC	LEGACY	ADMINBY
/24	27358	14225	6213	5287	401	1211	21	9439
/23	37526	20520	8318	6838	514	1296	40	13748
/22	60680	29876	14472	13452	884	1916	80	21836
/21	66928	36264	13472	13200	1112	2688	192	27104
/20	84992	49296	13104	17104	1184	3776	528	37792
/19	107360	64352	13632	22432	1792	4352	800	53760
/18	125376	80256	11584	25408	1984	4864	1280	73024
/17	152832	96000	16256	30848	2816	5504	1408	97664
/16	488192	359680	43008	64256	6144	12032	3072	396800
/15	300032	195072	35328	54272	5632	3584	6144	229888
/14	197632	116736	20480	38912	8192	2048	11264	130048
/12	143360	63488	18432	34816	12288	0	14336	94208
/11	163840	77824	4096	36864	8192	0	36864	81920
/10	131072	32768	8192	32768	8192	0	49152	57344
/9	131072	16384	0	0	0	0	114688	16384
/8	327680	32768	0	0	32768	0	262144	32768
/7	65536	0	0	0	0	0	65536	0
Всего:	2611468	1285509	226587	396457	92095	43271	567549	1373727
Всего блоков по /8	79,70	39,23	6,91	12,10	2,81	1,32	17,32	41,92

_{ADMINBY — согласно IANA имеют статус LEGACY, но назначены какому либо их RIR (Administered by RIR)}

Самый большой немаршрутизируемый блок от 28.0.0.0 до 30.255.255.255. Принадлежит двум организациям судя по этому документу DSI-North и Defense Information Systems Agency.

Стоит отметить что адресные блоки находящиеся в административном управлении RIR могли им достаться уже по факту. Например, блок 7.0.0.0/8 администрируемый ARIN целиком принадлежит DoD Network Information Center если судить по whois ARIN и не маршрутизируется. Всего количество адресов в подобных блоках соответствует, примерно, 42 адресным пространствам с префиксом /8.

Интересно наблюдать, что иногда в сплошном блоке, например, 13.128.0.0/9 или 29.0.0.0/8 присутствуют распределённые inetnum и route объекты, но всё равно глобально не видится ничего.

В некоторых случаях компания обладает большим непрерывным блоком, например, 2.0.0.0/12, но видимо по причине ненадобности анонсирует только часть этого блока. Получаются пробелы в 2.7.0.0/16 и 2.15.0.0/16. Может быть мелочь, но именно /16 является пиковым по свободным адресам.

Если немного посмотреть назад и взять данные за 20 Апреля 2011 года, то получим следующую картину.

Свободные префиксы 2011 год

	TOTAL	ARIN	RIPE	APNIC	AFRINIC	LACNIC	LEGACY
/24	19270	10418	4089	3725	246	789	3
/23	14019	7864	2978	2435	189	547	6
/22	10221	5683	2251	1634	183	459	11
/21	6728	3637	1533	1090	104	356	8
/20	4899	2625	903	853	63	430	25
/19	3068	1751	485	554	52	210	16
/18	1876	1165	221	330	39	106	15
/17	1186	710	148	224	20	73	11
/16	2069	1503	179	309	14	54	10
/15	672	424	65	147	9	18	9
/14	280	147	22	80	8	14	9
/12	129	54	11	41	8	9	6
/11	73	30	7	22	4	3	7
/10	27	9	4	7	1	1	5
/9	17	3	3	3	1	2	5
/8	16	3	2	0	1	2	8
/7	2	1	0	0	0	0	1

Свободные префиксы приведённые к /24 2011 год

	TOTAL	ARIN	RIPE	APNIC	AFRINIC	LACNIC	LEGACY	ADMINBY
/24	19270	10418	4089	3725	246	789	3	6335
/23	28038	15728	5956	4870	378	1094	12	9642
/22	40884	22732	9004	6536	732	1836	44	14232
/21	53824	29096	12264	8720	832	2848	64	19240
/20	78384	42000	14448	13648	1008	6880	400	29760
/19	98176	56032	15520	17728	1664	6720	512	43776
/18	120064	74560	14144	21120	2496	6784	960	64192
/17	151808	90880	18944	28672	2560	9344	1408	86272
/16	529664	384768	45824	79104	3584	13824	2560	436480
/15	344064	217088	33280	75264	4608	9216	4608	250368
/14	286720	150528	22528	81920	8192	14336	9216	171008
/12	264192	110592	22528	83968	16384	18432	12288	135168
/11	299008	122880	28672	90112	16384	12288	28672	135168
/10	221184	73728	32768	57344	8192	8192	40960	65536
/9	278528	49152	49152	49152	16384	32768	81920	65536
/8	524288	98304	65536	0	32768	65536	262144	131072
/7	131072	65536	0	0	0	0	65536	0
Всего:	3469168	1614022	394657	621883	116412	210887	511307	1663785
Всего блоков по /8	105,87	49,26	12,04	18,98	3,55	6,44	15,60	50,77

Адресов было побольше, почти 1/3 от всех. За это время все RIR'ы потратили адреса кто-то не так много, некоторые очень много, как LACNIC, но в целом от 1/3 до половины. Видно что не администрируемые напрямую RIR адреса как были так и остались практически в полном составе. Наоборот, часть адресов освободилась. Получается, что на заре становления Интернет была распределена пятая часть всех адресов которые до сих пор никак не используются. Точнее они могут могут быть использованы где-то локально, но в нашей действительности BGP Интернет доступа к ним не существует.

Я никак не ожидал что так много адресов не видно в BGP full-view. Кому-то их выделили очень много, но что их вообще не используют. Меня конечно это смутило и я стал искать где ошибся. Ошибся я серьёзно и неоднократно, но после всех исправлений конечный результат не сильно изменился. Может быть я не всё нашёл или неправильно считаю. В конце концов я проверил все блоки соответствующие AFRINIC вручную на предмет наличия в таблице маршрутизации на своих BGP маршрутизаторах и убедился, как минимум, в этом случае считается верно.

От первоначальной задумки сопоставить свободные блоки в таблице маршрутизации с базами RIR пришлось отказаться, слишком много адресов. Все получаемые дампы я положил рядом со скриптом который вычисляет пробелы в списке префиксов, зову всех попробовать повторить мои расчёты. А пока с завистью смотрим на первопроходцев, которым уж точно не грозит нехватка адресов, не в ближайшем будущем. Опрос соответствующий: