Изобрести протокол

Прошлая глава кончилась испорченной фразой: пакеты теряются и приходят вразнобой — как файл приходит целым? Сеть на этот вопрос не отвечает, ей разрешено терять. Отвечать будут концы, отправитель и получатель, и для этого им нужен договор — протокол. Мы изобретём его сами, ход за ходом, не заглядывая в готовый: каждый ход будет чинить то, что сломалось на предыдущем, а канал — придумывать новые способы всё испортить.

Условия переговоров

Нам понадобится канал, похожий на сеть, но с ручками, которые можно подкрутить. Он есть в песочнице — модуль cs.netsim. Объект Link — канал между отправителем и получателем: link.send(пакет) отправляет пакет, а список link.arrived показывает, что пришло на другой конец и в каком порядке. Время в канале условное и считается в кругах туда-обратно: пакет идёт в одну сторону полкруга плюс случайная задержка. Параметры канала: loss — доля потерь, dup — доля дублей, jitter — разброс задержки, из-за которого пакеты обгоняют друг друга. Отправим фразу по букве.

Буква «Р» пропала, «Ы» пришла дважды, несколько букв поменялись местами. Повторите опыт с другим seed — случай будет другим, а беда та же. Вот правила игры. Канал может потерять любой пакет, в любую сторону, задублировать его, задержать так, что его обгонят следующие. Испортить содержимое он не может: мы считаем, что контрольные суммы из прошлой главы ловят порчу, а испорченный пакет выбрасывается — то есть порча превращается в потерю. Нам разрешены две вещи: дописывать в пакеты что угодно и договориться, что делает каждый конец, получив пакет или не получив его.

Ход первый: номера

Самое очевидное — пронумеровать пакеты. Номер в каждом пакете называют номером последовательности. Получатель раскладывает данные по номерам, а не по порядку прихода.

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

Ход второй: расписка и будильник

Договоримся так: на каждый пакет получатель отвечает распиской — «пакет номер такой-то получен». Такой ответ называют подтверждением, по-английски ACK. Отправив пакет, отправитель заводит будильник. Пришла расписка — переходит к следующему пакету. Будильник прозвенел раньше — значит, пропал либо пакет, либо расписка, и пакет надо отправить снова. Таймер, по которому отправитель решает, что пора повторить, называют таймаутом повтора. Протокол, где отправитель ждёт расписку за каждый пакет, прежде чем слать следующий, так и называется: «отправь и жди», stop-and-wait.

Получателя в модуле уже научили этим правилам: с параметром receiver="ack" он ждёт пакеты вида (номер, данные), отдаёт программе данные строго по порядку, каждый кусок один раз, и на каждый полученный пакет отвечает ("ack", номер). А отправитель получает ответы методом link.wait(): он ждёт ответ и возвращает его, а если будильник прозвенел раньше, возвращает None. Вот два отправителя. Первый, доверчивый, считает любую пришедшую расписку подтверждением своего пакета. Второй, внимательный, проверяет номер.

Доверчивый донёс три буквы. Задержки в этом канале бывают больше будильника, а расписки иногда дублируются. Отправитель повторил пакет, а потом к нему пришли две расписки за него: одна за оригинал, запоздавшая, другая за копию. Первую он принял, перешёл к следующему пакету — и вторую расписку, старую, принял за подтверждение нового. Если новый пакет при этом пропал, отправитель об этом уже не узнает: он думает, что всё дошло, и идёт дальше, а получатель стоит на дыре и не принимает ничего после неё. Внимательный отправитель передал всё, но заплатил за это: 84 отправки на 36 букв и больше ста кругов туда-обратно.

Один бит работает, только пока в пути не больше одного пакета и пакеты не обгоняют друг друга. В нашем канале обгоны бывают, поэтому номера у нас полные: 0, 1, 2 и дальше. Включайте механизмы по одному и смотрите, что каждый чинит, а что ломается без него.

Своего отправителя «отправь и жди» вы напишете в задаче «Отправь и жди»: в её тестах канал теряет, дублирует и задерживает так, что доверчивость не проходит.

Сколько ждать

Когда должен звенеть будильник? Слишком рано — и отправитель шлёт копии пакетов, которые ещё не успели дойти, и засоряет канал. Слишком поздно — и после каждой потери канал простаивает. Правильный срок — чуть больше обычного времени туда и обратно. Но это время разное для разных собеседников (через стол — микросекунды, через океан — сотня миллисекунд) и меняется на ходу, когда растут очереди. Поэтому TCP измеряет его по распискам и держит две величины: сглаженное среднее $\bar R$ и сглаженный разброс $D$. Каждый новый замер $R$ сдвигает их на долю расстояния до себя:

$$D \leftarrow \tfrac{3}{4} D + \tfrac{1}{4}\,|R - \bar R|, \qquad \bar R \leftarrow \tfrac{7}{8}\bar R + \tfrac{1}{8}R, \qquad \text{таймаут} = \bar R + 4D.$$

Разброс в формулу добавил в 1988 году Ван Якобсон; до остальных его исправлений мы дойдём в разделе о перегрузке. Прежний стандарт велел брать среднее, умноженное на постоянный множитель от 1,3 до 2, и при скачущих задержках такой будильник то и дело звенел раньше времени. А если будильник всё-таки прозвенел, следующий срок удваивается: возможно, сеть перегружена, и торопить её повторами не стоит.

Ход третий: не ждать каждой расписки

Протокол работает, но посчитаем его скорость. За один круг туда и обратно отправитель передаёт один пакет. От Москвы до Нью-Йорка круг длится около ста миллисекунд, пакет — 1500 байт. Значит, «отправь и жди» передаёт 15 килобайт в секунду, 120 килобит, — и неважно, гигабитный канал или нет: всё остальное время канал простаивает, пока отправитель ждёт расписку.

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

Проверим на канале без потерь, как время передачи тысячи пакетов зависит от окна. Пакет выходит в канал за сотую долю круга, так что канал пропускает сто пакетов за круг. Будильник здесь не звенит ни разу, но он в коде есть: при потере отправитель вернётся к первому неподтверждённому пакету и повторит всё, что было в окне.

Каждое удвоение окна вдвое сокращает время — пока окно не дорастает до ста. Дальше рост прекращается: канал и так занят до отказа, лишние пакеты только ждут очереди на отправку. Число, на котором это происходит, — сколько данных помещается «в проводе» за один круг, пропускная способность, умноженная на время туда и обратно. Его называют произведением пропускной способности на задержку. Для гигабита в секунду и ста миллисекунд это 12,5 мегабайта: столько данных должно быть в пути, чтобы канал не простаивал. Оконному отправителю такая скорость доступна, «отправь и жди» — никогда.

Окно упирается не только в канал, но и в получателя. Если он не успевает разбирать данные — программа на той стороне занята, — его буфер переполнится, и всё новое придётся выбрасывать. Поэтому получатель в каждой расписке сообщает, сколько у него осталось свободного места, а отправитель не держит в пути больше. Это управление потоком. В заголовке TCP под размер окна отвели 16 бит, и окно не могло превышать 64 килобайт. Для гигабита через океан этого почти в двести раз меньше, чем надо, поэтому в 1992 году вышло расширение RFC 1323 — его авторы называли такие сети «длинными толстыми трубами»: окно можно умножать на степень двойки, вплоть до гигабайта. В песочнице оно включено: мы увидим это, когда будем расспрашивать ядро о живом соединении.

С окном потери обходятся дороже. Наш отправитель после потери повторяет всё окно, хотя дошло почти всё, — такую схему называют «вернуться на N». Аккуратнее другая схема: получатель складывает пришедшие не по порядку пакеты в буфер и сообщает, каких кусков не хватает, а отправитель повторяет только их. В TCP это выборочные подтверждения, SACK.

Что мы изобрели

Номера, расписки с номерами, будильник по измеренному времени, окно, управление потоком — всё это вместе и есть TCP, протокол управления передачей. Отличий от нашего изобретения немного. TCP нумерует байты: номер в сегменте — это номер его первого байта в потоке. Расписка в TCP накопительная: «жду байт номер такой-то» означает, что всё до него дошло, поэтому потеря одной расписки ничего не портит — следующая её перекрывает. И программа видит не пакеты, а непрерывный поток байтов, как в файле или трубе из главы 36, только этот поток идёт между машинами.

Осталось одно, чего в нашем изобретении не было: знакомство. Прежде чем передавать данные, TCP устанавливает соединение — обменивается тремя сегментами. Клиент отправляет SYN («хочу соединиться, мои номера начинаются с x»), сервер отвечает SYN-ACK («согласен, твой x получил, мои номера начинаются с y»), клиент подтверждает: ACK («твой y получил»). Это тройное рукопожатие. Три сегмента — наименьшее число, после которого каждая сторона знает, что её слышат и что она слышит собеседника. Начальные номера выбирают случайно. Иначе запоздавший сегмент от прошлого соединения между теми же портами мог бы прийти в новое и попасть в чужие данные, а злоумышленник мог бы подделать сегменты, угадав номера.

Прощаются тоже по правилам: каждая сторона отправляет FIN («я больше не пишу») и получает на него расписку. А тот, кто закрыл первым, ещё некоторое время помнит закрытое соединение — состояние TIME_WAIT, — чтобы бродячие копии последних сегментов успели умереть, не попав в новое соединение с теми же номерами портов. Это состояние мы скоро застанем в таблице ядра.

Надёжность нужна не всегда. Видеозвонку пакет, пришедший через секунду, уже бесполезен: картинка ушла вперёд. Повтор только задержит следующие кадры. Поэтому рядом с TCP живёт UDP — протокол внутреннего конверта из прошлой главы: порты, длина, контрольная сумма, и больше ничего. На UDP работают видеозвонки, сетевые игры и DNS, где запрос и ответ помещаются в один пакет и проще переспросить, чем устанавливать соединение. А если надёжность всё-таки нужна, но по-своему, её строят поверх UDP сами — так устроен протокол QUIC, на котором сегодня ходит заметная часть веба.

Настоящий TCP в песочнице

Хватит моделей. В песочнице нет выхода в интернет, но петля работает, и на ней можно запустить TCP ядра Linux: сервер и клиент в одной программе. Сначала разница между двумя транспортами. Отправим три слова по UDP и три по TCP.

UDP отдал три датаграммы по отдельности, TCP — одну склеенную строку. Это не ошибка, а суть потока: TCP обещает доставить байты по порядку, но не обещает сохранить границы между отправками. Один recv может вернуть половину отправленного, а может — три отправки сразу. Если программе нужны отдельные сообщения, разделять их — её забота: переводом строки, длиной в начале сообщения. Это первая ошибка почти каждого, кто пишет сетевую программу, и на ней построена задача «Эхо».

Сервер в этой ячейке устроен по общей схеме. bind привязывает сокет к адресу и порту, listen объявляет, что он принимает соединения, а accept ждёт клиента и на каждое соединение выдаёт новый сокет. Слушающий сокет остаётся слушать, а разговор с каждым клиентом идёт через свой. Теперь подсмотрим за рукопожатием. Сами сегменты в песочнице не поймать — для этого нужны права, которых у нас нет, — но ядро ведёт счётчики и таблицу соединений, и их можно прочесть в /proc.

Ровно три сегмента — SYN, SYN-ACK и ACK: обе стороны соединения живут в одном ядре, поэтому счётчик видит все три. Номера портов в таблице записаны шестнадцатеричными числами, функция переводит их в обычные. Сервер слушает свой порт, а у клиента порт случайный: его выбрало ядро из диапазона для временных портов, в песочнице это 32768–60999. После рукопожатия у каждой стороны своя строка ESTABLISHED. Клиент закрыл — он ждёт прощания собеседника (FIN_WAIT2), а сервер узнал о закрытии и ждёт, когда закроет и его программа (CLOSE_WAIT). Когда закрыли оба, сервер забыл соединение сразу, а клиент держит его в TIME_WAIT. Linux держит его там минуту.

Теперь две ошибки, которые встречает каждый, кто работает с сетью.

Обе ошибки вызывает один и тот же сегмент — RST, «сброс». В первом случае на SYN ответило ядро сервера: на этом порту никого нет. Так выглядит «в соединении отказано»: машина доступна, но программа не запущена или слушает другой порт. Во втором программа на той стороне закрыла сокет, не прощаясь, — так бывает, когда она упала или её остановили, — и ядро сбросило соединение: «соединение сброшено собеседником». Третья частая ошибка, «время ожидания истекло», означает, что не ответил вообще никто: пакеты теряются по дороге, машина выключена или их молча выбрасывает сетевой экран. По тексту ошибки видно, где искать: в программе, на машине или в сети.

Напоследок — сервер на много собеседников. Каждого он обслуживает в отдельном потоке из главы 39: пока один клиент молчит, другие не ждут. Общих данных у потоков здесь нет, так что гонок из той главы не будет.

Октябрь 1986: все правы, а сеть стоит

Наш протокол вежлив с получателем, но не думает о сети. А сеть — это общие очереди у маршрутизаторов из прошлой главы.

Механизм коллапса виден, если сложить два факта. Маршрутизатор с переполненной очередью выбрасывает пакеты. Отправитель, не дождавшись расписки, повторяет пакет — и отправляет его в ту же переполненную очередь. Каждый отправитель по отдельности ведёт себя правильно: он не знает, что пакет выброшен из-за давки, и упорно пытается его доставить. Но вместе они добавляют нагрузку именно тогда, когда её надо убавлять. Очереди растут, задержки растут, будильники звенят раньше, чем приходят расписки, и по сети идут копии пакетов, которые и так дошли бы. Полезных байтов становится всё меньше, хотя провода загружены полностью. Это коллапс перегрузки, и он страшен тем, что сам себя поддерживает.

Лекарство Якобсона — сделать потерю сигналом. Если пакет пропал, вероятнее всего, где-то на пути переполнена очередь, и отправитель должен сбавить скорость. Для этого у отправителя появляется второе окно, окно перегрузки: сколько пакетов он решается держать в сети. В пути — не больше меньшего из двух окон: того, что разрешил получатель, и того, что выдержит сеть. А окно перегрузки отправитель подбирает сам, по простому правилу:

• каждый круг туда и обратно без потерь — окно больше на один пакет;
• потеря — окно вдвое меньше.

Правило называют AIMD: прибавлять понемногу, а убавлять во много раз. Окно ползёт вверх, нащупывая, сколько выдержит сеть, натыкается на потерю, падает вдвое и снова ползёт. На графике получается пила. А чтобы новое соединение не ползло к нужной скорости слишком долго, в начале окно удваивается каждый круг — этот разгон, как ни странно, назвали медленным стартом: медленным по сравнению с тем, чтобы выпустить в сеть всё окно получателя сразу, как делали до 1988 года.

У правила «плюс один, пополам» есть второе достоинство: поток не только находит предел сети, но и делится ею с соседями. Пусть два потока делят канал на сто пакетов за круг, и первый успел разогнаться до семидесяти, когда второй только начал. Сравним AIMD с правилом, которое и прибавляет, и убавляет понемногу.

При AIMD разрыв между потоками тает: прибавляют они одинаково, а при каждой потере больший теряет больше, и разница между ними каждый раз уменьшается вдвое. Через полторы сотни кругов они делят канал почти поровну. При AIAD прибавка и убыль одинаковы для обоих, разница между окнами не меняется никогда, и первый поток навсегда остаётся впереди на те же 65 пакетов — в среднем вшестеро быстрее второго. В 1989 году Дах-Мин Чиу и Радж Джайн доказали, что из простых правил такого вида только AIMD приводит к справедливому дележу и полной загрузке канала с любого начального положения.

Последняя ручка в виджете показывает слабость AIMD: поток с длинным кругом туда-обратно прибавляет реже и получает меньше. Сегодня в Linux по умолчанию работает CUBIC (с 2006 года): его окно после потери растёт по кубической кривой, быстро возвращаясь к прежнему уровню. Google в 2016 году предложил BBR, который ориентируется не на потери, а на измеренные задержку и скорость. Но принцип у всех один: сеть общая, и каждый отправитель сам сбавляет скорость, когда она перегружена. А вот что ядро песочницы знает о своём соединении.

Алгоритм — CUBIC. Время туда и обратно по петле — обычно десяток-другой микросекунд, а будильник всё равно около 200 миллисекунд: Linux не ставит его короче, даже если сеть быстрее, чтобы не повторять пакеты зря. Окно перегрузки после десяти мегабайт — от пятнадцати до двадцати пяти сегментов, но сегмент на петле огромный, почти 64 килобайта. От запуска к запуску числа немного меняются. Две последние строки — настройки ядра: расширение окна из RFC 1323 и выборочные подтверждения включены.

Адреса кончились

Осталась последняя часть заголовка — адреса. Адрес IPv4 — 32 бита, всего $2^{32}$, чуть меньше 4,3 миллиарда. В 1981 году, когда вышел стандарт IP, это казалось неисчерпаемым запасом. Людей на Земле сейчас больше восьми миллиардов, и у многих по телефону, ноутбуку и телевизору.

Чтобы понять, как интернет без них обходится, начнём с того, как адреса делят. Мы уже знаем, что адрес состоит из двух частей: первые биты — сеть, остальные — машина в ней. Где проходит граница, говорит длина префикса — /26 — или, по-старому, маска: 32 бита, где на месте сети единицы, а на месте машины нули. Адрес сети — это адрес, в котором биты машины обнулены, а последний адрес, со всеми единицами, — широковещательный, «всем в подсети». Оба заняты, поэтому машин в подсети на два меньше, чем адресов. Всё считается битовыми операциями из главы 28.

В последней строке то же самое считает стандартный модуль ipaddress: в рабочей программе считайте им, а битами — чтобы понимать, что он делает. Длину префикса можно выбрать любую: до 1993 года адреса раздавали только тремя размерами — классами A, B и C, по 16 миллионов, 65 тысяч и 256 адресов, — и фирме, которой нужно было две тысячи адресов, приходилось давать 65 тысяч. Бесклассовая адресация CIDR с префиксами любой длины замедлила расход адресов и рост таблиц маршрутизации. Поиграйте с маской сами.

Один адрес на всю квартиру

Узнайте адрес своего домашнего компьютера: почти наверняка он начинается с 192.168 или с 10. Это частные адреса: в 1996 году стандарт RFC 1918 отвёл три диапазона — 10.0.0.0/8, 172.16.0.0/12 и 192.168.0.0/16 — для внутренних сетей. Ими может пользоваться кто угодно у себя дома, и в миллионах квартир есть свой 192.168.1.23. В интернете такие адреса ничего не значат.

И всё же пакет из прошлой главы дошёл с такого адреса до сервера, а ответ вернулся обратно. Помог NAT — подмена адресов. Домашний роутер, выпуская пакет наружу, заменяет в нём частный адрес отправителя на свой единственный внешний, а порт отправителя — на свободный номер из своих, и записывает пару в таблицу: «мой порт 61022 — это 192.168.1.23, порт 50000». Ответ приходит на 61022, роутер находит строку и возвращает пакет ноутбуку, подменив адрес обратно. Это та подмена, которую вы видели в путешествии пакета в прошлой главе. Предложили NAT в 1994 году как временную меру, пока не придумают что-то получше, а он стал повсеместным.

У NAT есть следствие, которое вы, возможно, встречали. Снаружи к компьютеру в домашней сети не подключишься: пакет, пришедший на роутер без соответствующей строки в таблице, некуда отдать. Поэтому для домашнего сервера в роутере вручную «пробрасывают порт», а видеозвонки и игры устраивают хитрые обходы. Нередко и сам провайдер прячет тысячи абонентов за одним своим адресом, и NAT получается двойным.

Вылечить нехватку могут только длинные адреса. В IPv6 адрес занимает 128 бит: $2^{128} \approx 3{,}4 \cdot 10^{38}$, по $8 \cdot 10^{28}$ адресов на каждый адрес IPv4. Их пишут восемью группами шестнадцатеричных цифр через двоеточие, а длинные серии нулей сокращают: петля, наш 127.0.0.1, в IPv6 — ::1. В песочнице она тоже работает.

Переход на IPv6 идёт медленно, потому что работает старое: NAT, частные адреса, вторичный рынок, на котором адреса IPv4 продают и сдают в аренду. Но идёт. По статистике Google, 28 марта 2026 года, в субботу, доля его пользователей, приходящих по IPv6, впервые перевалила за половину. Пока так бывает только по выходным, а в будни доля держится около 46–47 %: по-видимому, дома IPv6 встречается чаще, чем в офисных сетях.

Задачи

Три задачи — по трём этажам главы: протокол над моделью канала, сервер на TCP ядра и план адресов для офиса.

Напишите send_file(chunks, link) — отправителя по схеме «отправь и жди». chunks — список кусков файла (любых значений), link — канал Link из модуля cs.netsim с получателем receiver="ack": он принимает пакеты (номер, кусок) с номерами 0, 1, 2…, отдаёт куски программе по порядку и по одному разу, а на полученный пакет отвечает ("ack", номер). Пакет, пришедший раньше своей очереди, он выбрасывает и повторяет расписку за последний принятый. link.send(packet) отправляет пакет, link.wait() возвращает очередной ответ или None, если будильник прозвенел раньше. Канал в тестах теряет пакеты и расписки, дублирует их и задерживает так, что расписка может прийти после будильника. Получатель должен собрать исходный список без искажений, а отправитель — не слать лишнего: в канале без потерь — ровно одну отправку на кусок.

Сначала будильник: если wait() вернул None, пакет или расписка пропали, и пакет надо отправить снова. Повторять, пока расписка не придёт.

Теперь номер расписки. Сравните ответ с ("ack", seq): запоздавшая расписка за прошлый кусок — не повод переходить к следующему. Но и не повод отправлять пакет снова: она пришла поздно, а ваша, возможно, уже в пути. Дождитесь следующего ответа.

Три исхода ожидания — три ветки: своя расписка, тишина, чужая расписка. Чужую нельзя считать своей (так ломается доверчивый отправитель из главы) и нельзя считать тишиной: если на каждую запоздавшую расписку отвечать повтором, повторы порождают новые расписки, те опаздывают и порождают новые повторы — маленький коллапс перегрузки на одном соединении. Получателю номера нужны, чтобы не принять повтор за новый кусок, — поэтому в тесте с одинаковыми кусками подряд не помогут никакие сравнения содержимого.

В горах эхо возвращает слова задом наперёд — по крайней мере, в этой задаче. Напишите serve(server): функция получает слушающий TCP-сокет и обслуживает подключающихся клиентов вечно. Клиент присылает строки текста в UTF-8, каждая кончается переводом строки \n. На каждую полученную строку сервер отвечает ею же задом наперёд, тоже с \n в конце: на "ау\n" — "уа\n". Клиенты подключаются одновременно, и, пока один молчит, остальные не должны ждать. Тесты запускают serve в отдельном потоке и подключаются к нему обычными сокетами по петле.

Заготовка ошибается трижды. Она переворачивает всё, что вернул recv, — а это может быть полстроки или три строки сразу, вместе с \n. Копите полученные байты в буфере и отрезайте от него целые строки по \n.

Вторая ошибка: decode() куска, который кончился посередине буквы. «П» в UTF-8 — два байта, и кусок может их разрезать. Делите на строки байты, а декодируйте целую строку: байт \n в UTF-8 никогда не встречается внутри многобайтовой буквы — вспомните главу 28.

Третья: handle(conn) в том же потоке, что accept, — пока он обслуживает первого клиента, второй ждёт. Запускайте handle в отдельном потоке, как в ячейке «эхо.py».

Буфер и разбиение по разделителю — то, что делает с потоком любой сетевой протокол: HTTP из следующей главы читает заголовки так же, до пустой строки. Python умеет делать это и сам: conn.makefile("r", encoding="utf-8") превращает сокет в файл, и строки из него читаются обычным for line in f — с тем же буфером внутри. А поток на каждого клиента — самый простой способ обслуживать многих одновременно; когда клиентов десятки тысяч, переходят на один поток с циклом событий, как в asyncio из главы 37.

Офису выделили блок адресов, например "10.0.0.0/24", и в нём надо нарезать по подсети каждому отделу. Напишите plan(block, sizes): sizes — сколько машин в каждом отделе, ответ — список подсетей в том же порядке, по строке вида "10.0.0.128/26" на отдел, или None, если отделы в блок не помещаются. Правила такие. В подсети из $2^k$ адресов машинам достаётся $2^k - 2$: первый адрес — адрес сети, последний — широковещательный; самая маленькая подсеть — из четырёх адресов. Каждому отделу — самая маленькая подходящая подсеть. Раздавайте подсети с начала блока подряд, от больших отделов к меньшим, а отделы одного размера — в порядке списка. Например, plan("10.0.0.0/24", [50, 20, 100, 2]) — это ["10.0.0.128/26", "10.0.0.192/27", "10.0.0.0/25", "10.0.0.224/30"].

Заготовка забывает два служебных адреса: отделу из 64 машин не хватит подсети /26, в ней машин 62. И не проверяет, поместилось ли всё в блок: конец блока — начало плюс $2^{32 - \text{длина}}$.

Почему от больших к меньшим? Подсеть из $2^k$ адресов должна начинаться с адреса, кратного $2^k$, иначе её не записать префиксом. Если раздавать по порядку, после подсети на 4 адреса подсеть на 128 начнётся с адреса 4, а так нельзя. Когда идёшь от больших к меньшим, каждый следующий кусок начинается с кратного своему размеру сам собой.

Отсортируйте номера отделов: sorted(range(len(sizes)), key=lambda i: -sizes[i]) — сортировка в Python устойчивая, и равные отделы останутся в порядке списка. Ответ складывайте в список нужной длины по этим номерам.

Это жадный алгоритм из главы 23, и здесь он точен: размеры — степени двойки, поэтому, раздавая от больших к меньшим, мы не оставляем дыр и выравнивание получается само. Если всё влезает хоть как-то, влезает и так. Сетевые инженеры называют такой план VLSM — маски переменной длины — и делают его при каждой новой площадке. Модуль ipaddress умеет то же по частям: ip_network("10.0.0.0/24").subnets(new_prefix=26) режет сеть на подсети /26.

Куда дальше

Теперь любые две программы могут надёжно обмениваться байтами, если знают адрес и порт друг друга. Но вы никогда не вводите в браузере адрес вида 198.51.100.10 и порт 443. Вы набираете имя.

Номер порта песочница знает из справочника /etc/services, а имя превратить в адрес не может: Temporary failure in name resolution, «временный сбой при разрешении имени». Её отрезали от интернета, а значит, и от службы, которая отвечает на вопрос «какой адрес у legost.in». Кто отвечает на него у вас? Вы набираете legost.in и жмёте Enter. Что происходит до того, как появится эта страница: какие пакеты уходят, в каком порядке, сколько миллисекунд занимает каждый шаг? Об этом — следующая глава, и смотреть мы будем на страницу, которую вы сейчас читаете.