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

Все мы знаем что IPv4 адреса уже закончились ^[1] и не один раз ^[2]. Совсем недавно это была достаточно популярная для обсуждения тема в том числе и на Habrаhabr ^[3]: строили планы ^[4] и прогнозы ^[5], подсчитывали убытки ^[6]. На дворе 2016 год, но IPv4 по прежнему в строю.

21 Апреля RIPE NCC опубликовал коротенькую техническую новость ^[7] про то самое исчерпание IPv4 адресов. Собственно смысл новости — обновился график ^[8] показывающий текущее положение со свободными адресами у RIPE которых осталось у него в распоряжении почти на полный блок /8. У APNIC ^[9] только половина /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 ^[10]. В моей реализации применяется стек в качестве основного рабочего инструмента:

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 ^[11].

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Автор: Loiqig

Источник ^[23]