NET·VI Сети Глава 41 из 65
Один день из жизни пакета
Биография двух байтов: как буквы «LO» рождаются в программе, одеваются в конверты уровней, ищут дорогу по таблицам маршрутизаторов, стоят в очередях, иногда гибнут и всё-таки доходят. По дороге — первое сообщение ARPANET 1969 года, сеть Пола Бэрана, которая держится, даже когда выходит из строя половина узлов, и голубь Уинстон, обогнавший интернет.
Сети
- 41 Сети вы здесь
- 42 TCP/IP
- 43 Веб
- 44 Распределённые
Опирается на: 36 · Экскурсия по живой системе 28 · Всё есть биты
Что вы унесёте из главы
- понимать, из чего складывается задержка и скорость сети: распространение, передача, очередь — и прикидывать, сколько идёт файл
- читать сеть по уровням: какой заголовок добавляет каждый уровень и какое устройство какой конверт открывает
- находить маршрут по таблице с префиксами и понимать, где и почему теряются пакеты
Копия «Истории игрушек 2» на домашнем компьютере Гэлин Сусман, резервная копия «одна далеко» из правила 3-2-1, git push — всё, чем кончилась прошлая глава, держится на том, что данные умеют переезжать с машины на машину. А у двух машин нет ни общей памяти, ни общего диска: между ними только провод или радиоволна, а то и десяток посредников по дороге. Как они обмениваются данными? Начнём с самого маленького обмена, какой бывает. Программа ниже отправляет две буквы другой программе на той же машине, а потом спрашивает у ядра, сколько байт прошло через сетевую «петлю» — внутренний провод, которым машина соединена сама с собой.
Буквы дошли, но счёт не сходится: отправили два байта, а через петлю прошло тридцать. Откуда ещё двадцать восемь и почему счётчик называет всё это одним «пакетом»? Ответив на эти два вопроса, мы поймём, как устроена сеть. Лишние байты — одежда, в которой данные путешествуют, а пакет — единица путешествия.
Программа выше говорит с сетью через сокет — «розетку», которую ядро выдаёт программе так же, как открытый файл из главы 36: это тоже файловый дескриптор, только байты из него уходят в сеть. Адрес 127.0.0.1 означает «эта же машина». Подробно с сокетами мы будем работать в следующей главе, а здесь проследим за одним пакетом. Эта глава — его биография: рождение, одежда, дорога, очереди, опасности и прибытие. И начинается она, как положено биографии, с предков.
Предисловие: две буквы 1969 года
Наша ячейка повторила тот вечер в миниатюре: те же две буквы, только путь короче — от программы до программы на одной машине. По-английски lo — старинное «вот», «се». Сеть начала с полуслова. Но чтобы понять, почему два байта в 1969 году путешествовали именно так, в отдельных конвертах, через машины-посредники, надо вернуться ещё на десять лет назад и посмотреть, как была устроена единственная большая сеть того времени — телефонная.
Предки: провод на двоих
Когда в 1960 году человек звонил по телефону, станция соединяла его провод с проводом собеседника: телефонистка втыкала штекер, позже то же делали реле. На время разговора между ними возникала сплошная цепь, и она принадлежала только им двоим, даже если оба молчали. Так устроена коммутация каналов. Для голоса она хороша: звук идёт непрерывно, без задержек и пауз.
Компьютерам она подходит плохо. Человек за терминалом печатает букву, думает, читает ответ, и линия почти всё время простаивает, хотя больше никто ею воспользоваться не может. А соединять каждую машину с каждой отдельным проводом безнадёжно: у $n$ машин $\frac{n(n-1)}{2}$ пар — та же сумма, что в главе 13. Для тысячи машин это почти полмиллиона проводов, для миллиарда — полмиллиарда миллиардов. Нужна сеть, где один провод служит многим, а машины связаны через посредников.
Решение похоже на почту. Письмо не требует сквозного провода до адресата: его опускают в ящик, сортировочный узел смотрит на адрес и отправляет дальше, следующий узел — ещё дальше. Компьютерное сообщение режут на куски, к каждому прикрепляют адрес, и узлы сети передают куски от одного к другому: каждый дожидается куска до последнего бита, смотрит на адрес и отправляет его соседу, который ближе к цели. Кусок с адресом называют пакетом, а такой способ — коммутацией пакетов. Провод между узлами делят все: пока вы молчите, по нему идут чужие пакеты.
Часто пишут, что интернет построили, чтобы пережить ядерную войну. Это не так: руководитель ARPA Чарльз Херцфельд прямо возражал против этой легенды. ARPANET делали для того, чтобы исследователи из разных университетов могли пользоваться чужими дорогими компьютерами, не уезжая из дома. Но устройство она получила от Бэрана и Дэвиса: пакеты, узлы-посредники и много путей вместо одного.
Проверим расчёт Бэрана сами. Вот три сети по 49 узлов: звезда с центром, решётка, где у каждого узла четыре соседа, и решётка с диагоналями — восемь соседей. Выключим случайную долю узлов и обходом в ширину из главы 19 найдём самую большую группу уцелевших, которые ещё могут связаться друг с другом.
У звезды среднее выглядит прилично, но худший опыт выдаёт её характер: два процента. Когда выходит из строя центр, каждый уцелевший узел остаётся один, и не важно, сколько их уцелело. Решётка с четырьмя соседями переносит потерю десятой части узлов почти без последствий, а при потере половины распадается на острова. С восемью соседями даже при потере трети узлов в одной группе остаются 99 % уцелевших. В этом и состояло открытие Бэрана: сеть из ненадёжных узлов становится прочной, если путей в ней с запасом. Теперь выключайте узлы сами.
У распределённой сети есть цена: путь пакета нигде не записан заранее, и каждый узел должен сам решать, куда отправить пакет дальше. До этих решений мы дойдём, когда пакет выйдет в дорогу, а пока он ещё не одет.
Одежда: конверт в конверте
Вернёмся к тридцати байтам. Наши две буквы лежат в самом центре, а вокруг них два конверта, вложенные один в другой. Внутренний, восемь байт, надписала та часть ядра, которая отвечает за доставку конкретной программе: на нём номер порта отправителя и номер порта получателя — по ним ядро на той стороне поймёт, какой программе отдать буквы. Наружный, двадцать байт, надписала часть ядра, отвечающая за доставку конкретной машине: адрес отправителя, адрес получателя, сколько ещё маршрутизаторов пакету можно пройти и что лежит внутри. Соберём эти тридцать байт сами — модулем struct, который укладывает числа в байты по описанию формата.
Ровно тридцать. Строка формата "!BBHHHBBH4s4s" — опись полей: B — один байт, H — два, 4s — четыре байта как есть, а восклицательный знак в начале требует сетевой порядок байтов, старший байт первым. Это тот же порядок «старшим байтом вперёд», что в главе 28, и все протоколы интернета договорились о нём, чтобы машины с разным устройством памяти понимали друг друга. Поэтому длина 30 видна в заголовке как 00 1e, а 7f 00 00 01 в конце — это 127.0.0.1, по байту на число. Последняя строка показывает, как получатель проверяет, не испортился ли заголовок в дороге: это контрольная сумма из главы 40, одна из самых простых, и сумма заголовка вместе с записанной в него контрольной даёт ноль. Испортись один бит — ноль не получится, и пакет выбросят.
Каждый конверт — результат отдельного договора: в каком порядке поля, сколько в них байт, что делать с полученным. Такой договор называют протоколом. Наш внутренний конверт — протокол UDP, наружный — IP, протокол интернета. А вне петли, на проводе или в эфире, понадобился бы ещё один конверт снаружи: кадр Ethernet или Wi-Fi со своими адресами, чтобы пакет дошёл хотя бы до соседнего устройства. Протоколы сложены слоями, и каждый слой решает одну задачу, полагаясь на слой под ним и ничего не зная о слоях над ним. Такую стопку называют стеком протоколов. В интернете в нём пять уровней.
- Физический — как бит превращается в сигнал: напряжение в медной паре, вспышку света в стекле, радиоволну. Здесь нет конвертов, только сигналы.
- Канальный — доставка до соседа, с которым вы делите один провод или один эфир: Ethernet, Wi-Fi. Его адреса известны только в пределах одной сети.
- Сетевой — доставка через весь мир, от машины к машине через цепочку посредников: протокол IP, адреса вида 127.0.0.1.
- Транспортный — доставка нужной программе на машине: UDP или TCP, номера портов.
- Прикладной — то, что программы говорят друг другу: веб-страницы, почта, наше «LO».
Отправитель вкладывает данные в конверты сверху вниз, получатель вскрывает снизу вверх, и каждый уровень на той стороне читает тот заголовок, который надписал его двойник у отправителя. Посредники в пути вскрывают не всё. Устройство, которое соединяет компьютеры одной сети, читает только канальный конверт. Маршрутизатор открывает ещё и сетевой, чтобы узнать адрес назначения, а транспортный и данные, как правило, не трогает. Проводите пакет от ноутбука до сервера и следите, что меняется на каждом шаге.
Если вы встречали в учебниках семь уровней, а не пять, — это модель OSI, которую международные комитеты разрабатывали в конце 1970-х как общий стандарт. Интернет вырос на более простой схеме, но названия уровней и их номера из OSI прижились: «третий уровень» у сетевых инженеров — сетевой, «седьмой» — прикладной.
Первый шаг: соседи по эфиру
Самый первый шаг пакета — до соседнего устройства: от ноутбука до домашнего роутера по радио или от компьютера до коммутатора по кабелю. Здесь работает канальный уровень, и у него своя история.
Когда эфир общий, возникает вопрос вежливости: двое заговорят одновременно, и сигналы смешаются в шум. Правило Ethernet похоже на разговор за столом. Прежде чем говорить, послушай, не говорит ли кто-то. Если двое всё-таки начали вместе, оба замечают столкновение, замолкают и ждут случайное время. Столкнулись снова — ждут случайное время из вдвое большего промежутка, и так далее. Случайность разводит говорящих, а удвоение промежутка спасает, когда желающих много. Это правило называют CSMA/CD, «множественный доступ с контролем несущей и обнаружением столкновений».
У каждой сетевой карты есть свой адрес, зашитый на заводе, — MAC-адрес, 48 бит, их пишут шестью парами шестнадцатеричных цифр, например a4:5e:60:d1:27:0b. Кадр Ethernet — канальный конверт — начинается с адреса получателя и адреса отправителя, потом два байта говорят, что внутри (08 00 — пакет IP), потом сами данные и в конце четыре байта контрольной суммы. Данных в одном кадре не больше 1500 байт — отсюда предел размера пакета, который называют MTU. И не меньше 46: слишком короткий кадр не успел бы «заметить» столкновение, поэтому наше «LO», выйди оно за пределы петли, дополнили бы нулями до положенной длины.
Сегодня проводной Ethernet почти не знает столкновений: каждый компьютер подключён своим кабелем к коммутатору, который передаёт кадр только туда, где сидит получатель, и в обе стороны одновременно. А вот в радиоэфире Wi-Fi (первый стандарт IEEE 802.11 вышел в 1997 году) столкновения остались, и заметить их там труднее: передатчик глохнет от собственного сигнала и чужой не слышит. Поэтому Wi-Fi столкновений старается избегать — ждёт паузу и случайную добавку — и подтверждает каждый кадр. Не пришло подтверждение — кадр повторяется. Эфир теряет много, и, если бы Wi-Fi не повторял кадры сам, пакеты пропадали бы в первом же метре пути.
MAC-адрес нужен, чтобы пройти один шаг, — до соседа в той же сети. На каждом новом участке пути пакет получает новый канальный конверт с новыми адресами, а старый выбрасывается. Чтобы пройти весь путь, нужен адрес другого рода, который понимает весь мир.
Перекрёстки: адрес и маршрут
Такой адрес — IP-адрес: 32 бита, их пишут четырьмя байтами через точку, как 127.0.0.1 в нашем конверте. Устройство, которое стоит на перекрёстке нескольких сетей и пересылает пакеты из одной в другую, называют маршрутизатором. Получив пакет, маршрутизатор читает адрес назначения и решает, в какой из своих выходов его отправить. Но адресов четыре миллиарда, и помнить каждый он не может.
Выручает то же, что выручает почту. Почтальону в Новосибирске не нужно знать все улицы Москвы: письмо с надписью «Москва» он отправляет в московский поезд, а дальше разберутся. IP-адрес устроен так же: первые биты обозначают сеть, следующие — подсеть внутри неё, последние — саму машину. Маршрутизатор хранит только начала адресов, префиксы: «всё, что начинается с 10, — направо». Префикс записывают как адрес и число бит через косую черту: 10.0.0.0/8 — все адреса, у которых первые 8 бит такие же, как у 10.0.0.0, то есть все от 10.0.0.0 до 10.255.255.255. Список таких строк с указанием, куда отправлять, — таблица маршрутизации.
Префиксы вкладываются друг в друга, и адрес часто подходит под несколько строк. Тогда побеждает самый длинный подходящий префикс: он самый точный. Это как адрес на конверте: «Россия» подходит, «Москва» подходит, но решает «Тверская, 7». А строка 0.0.0.0/0 — префикс нулевой длины, который подходит к любому адресу, — работает как «всё остальное — провайдеру». Её называют маршрутом по умолчанию.
Функция matches сравнивает только первые биты: сдвиг вправо на $32 - \text{длина}$ отбрасывает хвост, который относится к машине, а не к сети. Для /0 сдвиг равен 32, и от любого адреса остаётся ноль, поэтому маршрут по умолчанию подходит всем. Наша функция перебирает всю таблицу, а у маршрутизаторов на границах больших сетей в таблице больше миллиона префиксов IPv4 — столько насчитал сайт CIDR Report в октябре 2026 года, — и пакетов в секунду миллионы. Перебор не годится. Как искать быстрее, вы придумаете в задаче «Самый длинный префикс». Одна подсказка у вас под рукой: таблица маршрутов самой песочницы.
Ядро Linux хранит таблицу маршрутов в боре из главы 27, только буквы в нём — биты адреса: развилка 127.0.0.0/8, под ней 127.0.0.0/31 и листья. Каждый путь от корня задаёт префикс, и самый длинный подходящий находится спуском по дереву: число шагов зависит от длины адреса, а не от того, сколько строк в таблице. А ещё вывод выдаёт тайну песочницы: в её таблице только петля 127.0.0.0/8 и ни одного маршрута наружу, даже по умолчанию. Поэтому пакет, который хочет выйти в мир, ядро даже не принимает: Network is unreachable, «сеть недоступна». Так курс и отгораживает ваш код от интернета. Адреса 203.0.113.x, кстати, никому не принадлежат: их отвели для примеров в документации, как и 198.51.100.x.
Откуда берутся таблицы
Никто не вписывает миллион строк руками. Маршрутизаторы составляют таблицы сами, переговариваясь с соседями, и делают это двумя способами, которые вы уже знаете по главе 24. В первом каждый маршрутизатор рассылает всем, с кем он соединён и сколько стоит каждая связь. Собрав эти сообщения, каждый знает карту всей сети и сам считает кратчайшие пути до всех остальных алгоритмом Дейкстры. Так работает протокол OSPF внутри больших сетей. Во втором маршрутизатор знает только соседей и регулярно сообщает им: «до такой-то сети мне столько-то шагов». Сосед прибавляет единицу и, если путь через вас короче, переписывает свою строку. Это алгоритм Беллмана — Форда, только релаксацию рёбер выполняют сотни машин, каждая у себя. Между сетями разных компаний действует протокол BGP, где решают не только километры, но и договоры: через чью сеть провайдер согласен возить чужие пакеты.
Пока таблицы обновляются, они бывают несогласованными: A считает, что путь лежит через B, а B — что через A, и пакет начинает ходить по кругу. Чтобы он не кружил вечно, в сетевом конверте есть поле TTL, «время жизни». Каждый маршрутизатор уменьшает его на единицу, а пакет с нулём выбрасывает и отправляет отправителю короткое служебное сообщение протокола ICMP: «время истекло». В нашем конверте TTL было 64 — столько ставит по умолчанию Linux. На этом построена программа traceroute, которую Ван Якобсон написал в 1987 году: она отправляет пакеты с TTL 1, 2, 3… и по тому, кто присылает «время истекло», выясняет, через какие маршрутизаторы идёт путь. Якобсона мы встретим и в следующей главе.
Час пик: очередь у выхода
Маршрутизатор принимает пакеты с нескольких входов, а отправляет каждый в один выход. Что, если в выход, который передаёт сто мегабит в секунду, прямо сейчас хотят сто двадцать? Лишнее приходится где-то держать. У каждого выхода есть буфер — очередь из главы 15, чаще всего на кольцевом буфере, — и пакеты стоят в ней, пока выход занят. А если очередь полна, новому пакету места нет, и маршрутизатор его выбрасывает, никому не сообщая.
Как растёт очередь, изучал Леонард Клейнрок, в чьей лаборатории Клайн потом набирал «LO». Его диссертация, защищённая в MIT в 1963 году, называлась «Задержка сообщений в сетях связи с хранением», и строилась она на теории очередей. Её основной вывод проверим опытом. Пусть отправка одного пакета в выход занимает единицу времени, а пакеты приходят случайно, в среднем $\rho$ штук за единицу: $\rho$ — это загрузка выхода, от нуля до единицы. Сколько пакет в среднем стоит в очереди?
Пока выход загружен наполовину, пакет ждёт в среднем полвремени отправки — почти незаметно. На 80 % — две единицы, на 90 % — четыре с половиной, на 95 % — около девяти. Ожидание растёт не пропорционально загрузке, а как $\frac{1}{1-\rho}$: последние проценты загрузки обходятся дороже всех предыдущих вместе. Формула в последнем столбце — частный случай формулы Поллачека — Хинчина для очереди, в которую заявки приходят случайно, а обслуживаются за одинаковое время. На 99 % опыт расходится с формулой: очередь раскачивается так медленно, что даже двухсот тысяч пакетов мало, чтобы среднее успело установиться. Тот же закон вы видели в пробках: дорога, загруженная на 70 %, едет, а на 95 % стоит, хотя машин всего на треть больше.
Когда загрузка выше ста процентов, никакой буфер не спасает: очередь растёт, пока не заполнится, и дальше маршрутизатор выбрасывает лишнее. Большой буфер только отодвигает этот момент и превращает очередь в долгое ожидание: пакет, стоящий двухсотым, ждёт двести отправок. Опасность описывали ещё в 1985 году, а всеобщее внимание она привлекла в 2010–2011 годах, когда выяснилось, что многие домашние роутеры и модемы держат огромные буферы и при закачке большого файла задержка в такой сети вырастает до секунд. Джим Геттис, который это расследовал, назвал явление bufferbloat, «раздутые буферы». Если видеозвонок начинает отставать, как только кто-то дома скачивает игру, — это оно.
Гибель и двойник
Здесь биография нашего пакета может оборваться. Он пришёл к выходу, где очередь полна, и маршрутизатор его выбросил. Пакеты гибнут и иначе: помехи портят биты в радиоэфире, и проверка контрольной суммы бракует кадр; маршрутизатор перезагружается; TTL доходит до нуля. И почти всегда — молча. Сеть IP ничего не гарантирует: она старается доставить, но пакет может пропасть, прийти дважды или обогнать отправленного раньше, если тот пошёл другим путём или застрял в очереди. Такую доставку называют доставкой по возможности.
Можно было бы сделать надёжной саму сеть: пусть каждый маршрутизатор проверяет и повторяет. Против этого есть довод, который в 1981 году сформулировали Джером Зальцер, Дэвид Рид и Дэвид Кларк и назвали сквозным принципом. Гарантировать доставку от начала до конца может только тот, кто стоит на концах: ведь пакет может пропасть и после последнего маршрутизатора, и в памяти самого получателя. Значит, концам всё равно придётся проверять и переспрашивать, и раз так, то сеть посередине лучше оставить простой и быстрой. Исключения бывают, когда проверка на месте сильно дешевле: Wi-Fi повторяет кадры сам, потому что эфир теряет слишком много. Но последнее слово всегда за концами.
Так у нашего пакета появляется двойник. Отправитель не дождётся ответа, решит, что пакет пропал, и пошлёт его копию. Как он поймёт, что пора, сколько ждать и что делать, если оригинал всё-таки дойдёт вслед за копией, — это вопрос, ради которого придумали протокол TCP, и вся следующая глава.
Время в пути
Допустим, нашему пакету повезло. Сколько он идёт? Сначала измерим самый короткий путь из возможных — до самого себя. В песочнице нет утилиты ping, но её можно написать: ping отправляет служебное сообщение ICMP «эхо-запрос», а ядро на той стороне отвечает «эхо-ответом» с теми же данными.
Несколько микросекунд туда и обратно, и почти всё это время — работа ядра: системные вызовы, копирование байтов, переключение между отправителем и получателем. Расстояния здесь нет. В сети между городами к этому добавляется физика. Свет в оптоволокне идёт примерно на треть медленнее, чем в пустоте, — около 200 000 километров в секунду, и быстрее сигнал не пойдёт ни при каких деньгах.
Это нижняя граница, по прямой. Кабели прямо не идут, да и расстояние — лишь одно из слагаемых. Время пакета в пути складывается из четырёх частей:
- распространение — расстояние, делённое на скорость сигнала: от неё не уйти;
- передача — размер пакета, делённый на скорость канала: 1500 байт по каналу в 100 мегабит в секунду выходят в провод за 0,12 миллисекунды;
- очередь — сколько пакет простоял в буферах, от нуля до секунд;
- обработка — сколько маршрутизатор думал, куда его отправить: обычно микросекунды.
В «Если такт — секунда» из главы 34 пакет через океан и обратно шёл шестнадцать лет. Этот срок дало первое слагаемое, распространение. А когда реклама обещает «интернет 500 мегабит», она говорит о другом — о том, сколько данных канал пропускает за секунду. Это пропускная способность, и пакет от неё быстрее не становится, зато одновременно можно отправить больше пакетов. Шоссе из десяти полос не сокращает дорогу от Москвы до Петербурга, но пропускает больше машин. Задержка — время, через которое придёт первый бит, пропускная способность — как быстро после этого пойдут остальные. Скорость канала меряют в битах, а файлы — в байтах: 500 мегабит в секунду — это 62,5 мегабайта.
Между задержкой и пропускной способностью есть ещё одна связь, и она объясняет, почему сеть режет данные на маленькие пакеты. Узел пересылает пакет дальше только после того, как принял его целиком. Если передавать мегабайт одним куском через пять узлов, каждый будет ждать, пока к нему придёт весь мегабайт. А пакеты идут конвейером: пока второй узел передаёт дальше первый пакет, первый уже передаёт второй.
Целиком мегабайт через пятнадцать каналов идёт двенадцать секунд, пакетами — 0,82: каждый лишний канал добавляет не время всего сообщения, а время одного пакета. Это та же прачечная-конвейер, что в процессоре из главы 35. Формула в функции packets упрощённая: она не учитывает распространение, заголовки и то, что последний пакет обычно короче. Точный подсчёт — в задаче «Сколько идёт файл».
Голубь против канала
Если пропускная способность и задержка — разные вещи, у них могут быть разные чемпионы. Это проверили в Южной Африке.
2009 год, Южная Африка. Нужно переправить 4 гигабайта на 80 километров. Соревнуются домашний канал ADSL и почтовый голубь с картой памяти на лапке. Кто доставит раньше?
Голубь, и с огромным отрывом: когда данные с его карты уже скачали, по каналу ушло около 4 % файла.
По этим цифрам можно оценить канал: 4 % от 4 гигабайт за 7617 секунд — меньше 200 килобит в секунду. А голубь «передал» 32 миллиарда бит за то же время: 4,2 мегабита в секунду, в двадцать пять раз быстрее. Но попробуйте отправить голубем один пинг. Задержка у голубя — час, у канала — доли секунды. Эндрю Таненбаум, автор классического учебника по сетям, сформулировал это так: «Никогда не недооценивайте пропускную способность универсала, набитого магнитными лентами и несущегося по шоссе». Где проходит граница, найдите сами: выберите объём данных, расстояние и канал.
Голубь — шутка лишь отчасти. Облачные компании принимают данные клиентов на дисках, присланных грузовиком или почтой, когда речь о сотнях терабайт: по каналу такие объёмы шли бы месяцами. А вот для разговора, игры или пинга решает задержка, и тут любой провод выигрывает у любой птицы.
Прибытие
Последний маршрутизатор отдал пакет в сеть, где живёт получатель, канальный уровень довёз его до сетевой карты, ядро проверило контрольную сумму IP-заголовка и увидело в нём свой адрес. Пакет дома. Но на машине работают десятки программ, и каждая ждёт своё. Кому отдать две буквы? Тут вскрывается транспортный конверт, и решает в нём одно число — порт. Программа, которая ждёт данных, заранее просит у ядра номер порта — так делал bind в самой первой ячейке, — и ядро отдаёт ей всё, что приходит на этот номер. Адрес машины похож на адрес дома, порт — на номер квартиры.
Два пакета пришли на один адрес и разошлись по разным программам — по номерам портов. А последний пакет пришёл туда, где никто не ждёт. Ядро не стало молча его выбрасывать: оно отправило назад служебное сообщение ICMP «порт недоступен», и ядро отправителя превратило его в ошибку Connection refused, «в соединении отказано». Номера портов, которые вы видите в выводе, ядро выбирает само из свободных, если программа попросила порт 0. А у известных служб номера постоянные: веб-сервер ждёт на 80 (и на 443 для защищённых соединений), почтовый — на 25.
За один день наши две буквы родились в программе, получили транспортный конверт с номерами портов, сетевой — с адресами и TTL, канальный — с адресами сетевых карт; на каждом шаге канальный конверт меняли на новый, а TTL уменьшали; они стояли в очередях, рисковали погибнуть при переполнении буфера и наконец попали к программе, которая их ждала. Миллионы таких биографий проживаются каждую секунду, и ни один узел сети не знает всей картины: никто не главный, каждый лишь передаёт пакет соседу, который ближе к цели. Это первый кусок ответа на шестой большой вопрос курса — как миллиарды компьютеров работают вместе без главного. Остальные куски — в следующих трёх главах.
Задачи
Три задачи — по трём ремёслам сетевого уровня: найти маршрут, посчитать время, нарезать и собрать. В каждой есть большой вход с ограничением времени.
Напишите класс Router. Конструктор получает таблицу маршрутизации — список пар (префикс, куда), где префикс записан как "10.1.0.0/16". Метод route(address) получает адрес вида "10.1.2.77" и возвращает «куда» из строки с самым длинным подходящим префиксом или None, если не подходит ни одна. Префикс подходит, если первые биты адреса — столько, сколько указано после косой черты, — совпадают с теми же битами записанной сети; биты после длины в записи могут быть любыми, так что "10.1.2.3/16" означает то же, что "10.1.0.0/16". Длина префикса — любая от 0 до 32, одинаковых префиксов в таблице нет. Тесты строят таблицу на сто тысяч маршрутов и спрашивают сто тысяч адресов: на всё вместе — четыре секунды.
Заготовка сравнивает строки, а префикс — это биты числа. «10.1.2» — начало строки «10.1.20.5», но 2 и 20 — разные байты. А "10.0.0.0".rstrip(".0") вообще даёт "1". Переведите адрес в 32-битное число, как to_int в главе, и сравнивайте числа, сдвинутые вправо на $32 - \text{длина}$.
Перебор всей таблицы для каждого адреса — сто тысяч на сто тысяч, десять миллиардов сравнений. Но различных длин префикса всего 33. Заведите для каждой длины словарь «первые биты → куда»: проверить, есть ли подходящий префикс длины 24, — один поиск в словаре по ключу x >> 8.
Перебирайте длины от самой большой к самой маленькой и возвращайте первую находку: она и есть самый длинный префикс. Длины, которых в таблице нет, можно не проверять.
Поиск адреса стоит не больше 33 обращений к словарю, сколько бы маршрутов ни было в таблице, — $O(1)$ по числу маршрутов, хеш-таблицы из главы 16 работают на маршрутизатор. Сдвиг вправо отбрасывает биты машины, поэтому и лишние биты в записи префикса, и маршрут по умолчанию /0 (сдвиг на 32 даёт ноль у любого адреса) обрабатываются сами. Маршрутизаторы в жизни идут другим путём: ядро Linux хранит таблицу в сжатом двоичном боре, а железные маршрутизаторы — в особой памяти, которая сравнивает адрес со всеми строками одновременно, за один такт.
Файл размером size байт идёт от источника к получателю через цепочку из hops одинаковых каналов: источник → маршрутизатор → … → получатель. Каждый канал передаёт rate бит в секунду, а сигнал идёт по нему delay секунд. Файл режут на пакеты по 1460 байт данных (последний может быть короче), и к каждому пакету добавляется 40 байт заголовков. Источник выпускает пакеты друг за другом без пауз; каждый маршрутизатор начинает передавать пакет дальше, только когда принял его целиком, и передаёт пакеты в том порядке, в каком они пришли. Напишите transfer_time(size, rate, hops, delay) — через сколько секунд после начала передачи последний бит файла дойдёт до получателя. Размер не меньше одного байта.
Начните с одного пакета. Он выходит в первый канал за (данные + 40) · 8 / rate секунд, потом delay секунд идёт по проводу, и на следующем узле всё повторяется. Через hops каналов — hops раз одно и то же.
Теперь много пакетов. Нарисуйте на бумаге таблицу: строки — пакеты, столбцы — каналы, в клетке — когда пакет закончил выходить в этот канал. Пакет может начать выходить в канал, когда (а) сам пришёл на узел целиком и (б) канал освободился от предыдущего пакета. Это готовая программа: два вложенных цикла и max.
Если хотите формулу: все каналы одинаковые, поэтому полные пакеты выходят из источника и приходят к получателю с шагом в одно время передачи. Последний, короткий пакет на каждом узле ждёт, пока канал освободится после предпоследнего.
Предпоследний пакет выходит из источника к моменту $(n-1)\,t$, где $t$ — время передачи полного пакета, и дальше на каждом из $H - 1$ следующих каналов задерживается на $t + d$. Последний пакет короче и приходит на каждый узел раньше, чем освобождается канал, поэтому идёт за предпоследним вплотную и добавляет к его времени только свою передачу $t'$ и последний провод $d$. Получается $(n-1)\,t + (H-1)(t+d) + t' + d$. Решение двумя циклами по таблице «пакет × канал» тоже верное и укладывается в лимит. В тесте «Москва — Нью-Йорк» любопытны порядки величин: при гигабите в секунду мегабайт идёт около 46 мс, при ста мегабитах — около 120 мс. Ускорение канала вдесятеро не ускорило доставку вдесятеро: 37,5 мс из них — свет в стекле, которому не прикажешь.
Когда пакет не пролезает в канал с меньшим MTU, протокол IPv4 режет его на фрагменты, и каждый идёт дальше сам по себе. У каждого фрагмента свой IP-заголовок на 20 байт; данные фрагмента вместе с заголовком не должны превышать MTU. Смещение куска от начала данных записывается в заголовок в единицах по 8 байт — поэтому у всех кусков, кроме последнего, длина обязана быть кратна 8. Флаг «есть ещё» поднят у всех фрагментов, кроме последнего.
Напишите две функции. fragment(data, mtu) возвращает список троек (offset, more, chunk): смещение в восьмёрках байт, флаг «есть ещё» и байты куска; кусков должно быть как можно меньше. Пустые данные — один фрагмент (0, False, b""). reassemble(fragments) получает тройки в любом порядке, возможно с повторами, и возвращает собранные байты или None, если какого-то куска не хватает. MTU не меньше 28.
Возьмите классический пример: 3980 байт данных, MTU 1500. Рядом с заголовком помещается 1480 байт, 1480 кратно 8 — получаются куски 1480, 1480 и 1020 со смещениями 0, 185 и 370. А при MTU 576 помещается 556, и это не кратно 8: брать придётся 552.
Для сборки не нужно сортировать тройки: положите куски в словарь «смещение в байтах → кусок». Длину целого знает последний фрагмент, у которого more ложно: его смещение плюс его длина. Потом идите от нуля: кусок, который начинается там, где кончилось собранное, — следующий.
Словарь сразу решает две проблемы: порядок прихода не важен, а повтор перезаписывает тот же кусок. Сборка останавливается на первой дыре — и тут видна слабость фрагментации: потерялся один фрагмент из десяти, и весь пакет пропал, хотя девять кусков дошли. Получатель не может попросить недостающий кусок, он может только выбросить остальные. Поэтому современные системы стараются вовсе не фрагментировать: заранее узнают наименьший MTU на пути, а в IPv6 маршрутизаторы пакеты по дороге не режут никогда. Как собирать данные надёжно, переспрашивая пропавшее, расскажет следующая глава.
Куда дальше
Нашему пакету повезло. Теперь пусть программа отправляет уже не два байта, а файл в мегабайт, порезанный на семьсот пакетов, и сеть ведёт себя так, как ей разрешено: один пакет выбросила переполненная очередь, две пары пошли разными путями и пришли в обратном порядке, один маршрутизатор отправил дважды.
Так выглядит текст, если склеивать всё, что пришло. Пакеты теряются и приходят вразнобой. Как файл приходит целым? Сеть ответа не даст: ей разрешено терять. Отвечать придётся концам — отправителю и получателю, — и для этого им нужно договориться о правилах переговоров через ненадёжного посредника. Такой договор можно изобрести самому, шаг за шагом, и в конце обнаружить, что изобрёл TCP. Этим займёмся в следующей главе.