Шукаємо вільні 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'ів.

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

Треба розкуркулити першопрохідців Інтернет?

/>
/>


<input type=«radio» id=«vv73020»
class=«radio js-field-data»
name=«variant[]»
value=«73020» />
Так
<input type=«radio» id=«vv73022»
class=«radio js-field-data»
name=«variant[]»
value=«73022» />
Немає

Проголосувало 72 людини. Утрималося-10 чоловік.


Тільки зареєстровані користувачі можуть брати участь в опитуванні. Увійдіть, будь ласка.


Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.