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

в 12:36, , рубрики: BGP, full-view, IANA, IPv4, IPv6, конец IPv4, маршрутизация, Сетевые технологии

Все мы знаем что 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'ов.

image
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.

image

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

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 года, то получим следующую картину.

image

Свободные префиксы 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 пришлось отказаться, слишком много адресов. Все получаемые дампы я положил рядом со скриптом который вычисляет пробелы в списке префиксов, зову всех попробовать повторить мои расчёты. А пока с завистью смотрим на первопроходцев, которым уж точно не грозит нехватка адресов, не в ближайшем будущем. Опрос соответствующий:

Автор: Loiqig

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js