Компьютерная сеть кажется инженером клубком кабелей, свитчей и конфигурационных файлов, но математик видит в ней строгий объект: множество вершин, множество ребер и набор весов. Маршрутизатор это узел, канал связи это ребро, метрика канала это вес. Все, что происходит дальше, от выбора пути пакета до диагностики обрыва, описывается алгоритмами, которым уже полвека, а порой и двести лет. Дейкстра считает кратчайшие пути внутри OSPF, поиск в ширину объясняет поведение широковещательных рассылок, остовные деревья спасают Ethernet от штормов, а степенная структура интернета диктует архитектуру BGP. Тот, кто понимает сеть как граф, перестает заучивать протоколы и начинает их предсказывать.
Как сеть превращается в граф с весами
Формализация начинается с простого присвоения. Каждое активное устройство становится вершиной, каждый линк между устройствами становится ребром. Линку приписывается вес, и тут инженерия встречается с вкусовщиной: весом может быть пропускная способность, где гигабитный канал дешевле стомегабитного, может быть задержка, измеренная в миллисекундах, может быть денежная стоимость аренды канала у провайдера, а может быть чисто административное число, которое сетевик выставил руками, чтобы сдвинуть трафик с проблемного участка. В OSPF вес по умолчанию считается как опорная полоса, деленная на полосу интерфейса, и потому десятигигабитный порт получает метрику в десять раз ниже гигабитного.
Ключевое свойство модели в том, что маршрут пакета выбирается не по географии, а по ребрам с минимальной суммой весов: два офиса в одном здании порой обмениваются трафиком через соседний город, если так дешевле по метрике. Граф бывает и ориентированным: асимметричные линки и односторонние фильтры делают вес AB отличным от BA, и диагностика теряет надежду на симметрию.
Дейкстра внутри OSPF и почему линк-стейт знает всю карту
OSPF построен на прямом применении алгоритма Дейкстры, придуманного в 1956 году за несколько минут размышлений в кафе. Протокол принадлежит к классу link-state: каждый маршрутизатор рассылает всем соседям в области описание своих собственных линков, и эти объявления собираются в единую базу топологии, одинаковую у всех участников области. Когда база собрана, каждый маршрутизатор самостоятельно запускает Дейкстру, ставя себя корнем, и вычисляет дерево кратчайших путей до всех остальных вершин.
Сам алгоритм работает жадно. Все вершины получают бесконечную стоимость, корень получает ноль. Из множества еще не обработанных вершин выбирается та, у которой текущая стоимость минимальна, она объявляется финальной, и ее соседям предлагается расслабление: если путь до соседа через текущую вершину дешевле известного, стоимость обновляется. Пока множество не опустело, алгоритм повторяет выбор минимума. Гарантия корректности держится на том, что веса неотрицательны, что в сетях выполняется всегда. Сложность с очередью с приоритетом близка к O((V + E) log V), и для области из сотен маршрутизаторов пересчет занимает миллисекунды, что и позволяет OSPF сходиться за доли секунды после падения линка.
Механизм надежного распространения объявлений с подтверждениями и последовательными номерами делает расхождение баз кратковременным, поэтому вся область вскоре видит одну и ту же карту. За это платят памятью и процессором, и очень большие сети режут на области, превращая граф в иерархию на стыках.
Distance-vector, RIP и болезнь бесконечного счета
Класс distance-vector, чьим типичным представителем стал RIP, устроен принципиально иначе. Маршрутизатор не знает граф, он знает только вектор: до каждой сети такое-то расстояние через такого-то соседа. Периодически соседи обмениваются полными таблицами, и каждый верит чужим цифрам на слово. Это сравнимо с населенным пунктом, где никто не видел карту, но каждый знает расстояние до соседних деревень и пересказывает дальше лучшее из услышанного.
Проблема возвращается при обрыве. Сосед еще держит в таблице маршрут до отвалившейся сети и честно сообщает его остальным с чуть большей метрикой. Те обновляют записи, отвечают тем же, метрики растут по кругу, и счет уходит к бесконечности, отсюда и название count to infinity. RIP спасается грубо: метрика ограничена пятнадцатью хопами, шестнадцать считается недоступностью, бесконечность конечна, но сходимость растягивается на минуты. Два приема смягчают болезнь. Split horizon запрещает объявлять маршрут обратно тому соседу, от которого он узнан, а poisoned reverse вообще возвращает его с бесконечной метрикой. Полной победы над петлей не бывает, потому что знания о графе у векторного протокола нет. Сравнение с OSPF читерское: кто видит всю карту, мгновенно понимает, какое ребро выпало, а кто слушает слухи, опровергает их долгим взаимным переглядыванием.
BGP как path-vector и граф со степенной толщиной
Между автономными системами интернет маршрутизируется протоколом BGP, и его принято называть path-vector. Разница с RIP в том, что анонс несет не число, а весь пройденный путь из номеров автономных систем. Петля ловится тривиально: если система видит собственный номер в пути, маршрут отбрасывается. За счет пути BGP избегает бесконечного счета, но за счет того же пути выбор маршрута перестает быть оптимизацией метрики и становится политикой: локальное предпочтение, длина пути, коммерческие договоренности, community-метки. Граф автономных систем упорно отказывается быть случайным.
Измерения показывают, что распределение степеней вершин в графе интернета близко к степенному закону: масса систем имеет горстку связей, а крошечная элита крупных транзитников держит тысячи пиринговых сессий. Такая структура называется безмасштабной, и у нее горько-сладкое свойство: случайные отказы ее почти не трогают, но адресный удар по хабу раскалывает граф на части, ведь хабы стоят на большинстве кратчайших путей. Отсюда и размер глобальной таблицы BGP, переваливший за девятьсот тысяч префиксов: память маршрутизатора хранит не граф, а результат выбора для каждой точки назначения.
TTL как страж от циклов и фокус с tracert
Интернет не доверяет своей маршрутизации до конца, потому у каждого IPv4-пакета есть поле TTL, а у IPv6 его наследник Hop Limit. Каждый маршрутизатор обязан уменьшить счетчик на единицу, а увидев ноль, уничтожить пакет. Это прямое следствие теоремы о петлях в графе: если маршрутизация временно сходится через цикл, пакет не обречен кружить вечно, счетчик гарантирует его смерть за конечное число шагов. Стартовое значение обычно шестьдесят четыре или сто двадцать восемь, что на два порядка больше реального диаметра интернета.
Из этого защитного механизма инженеры выжали диагностический инструмент. Утилита tracert в Windows и traceroute в Unix работают так:
- Отправляется проба с TTL равным единице, первый маршрутизатор обнуляет счетчик и возвращает ICMP Time Exceeded, раскрывая свой адрес.
- Отправляется проба с TTL равным двум, и тот же трюк удается уже на втором маршрутизаторе пути.
- Тройка, четверка и дальше выстраивают цепочку ответов, пока очередная прога не достигнет цели и не получит от нее обычный ответ.
- По времени каждого ответа вычисляется задержка до каждого промежуточного хопа, и карта пути всплывает прямо в терминале.
Побочный эффект практически важен: звездочки вместо адресов означают не тайну, а маршрутизатор, который не генерирует или фильтрует ICMP, а внезапный скачок задержки между соседними строками часто указывает на перегруженный линк или смену транзитника. Тот же tracert показывает и асимметрию графа: обратный путь не обязан повторять прямой.
LLTD и карта сети, которую рисует Windows
Примером графового мышления в самой операционной системе служит функция Карта сети в старых версиях Windows, построенная на протоколе LLTD. Протокол уровня канала работает через два компонента: маппер шлет в локальный сегмент запрос обнаружения, а ответчики на устройствах отвечают сведениями о себе и своих соседях. Собранные ответы склеиваются в граф соседства, и пользователь видит схему: компьютеры соединены со свитчем, свитч с роутером, роутер с выходом наружу. LLTD даже достраивает невидимые ребра по косвенным уликам через эхо и интерфейсные дескрипторы. Классический пример, что сетевой граф можно попросить нарисовать самого себя, пригодился при диагностике домашних топологий, где рисовать схему вручную не хотел никто.
BFS и широковещание как обход в ширину
Поиск в ширину в чистом виде в маршрутизации встречается редко, зато широковещательное распространение кадров устроено ровно как BFS. Кадр приходит на порт, свитч рассылает его на все остальные порты, соседние свитчи повторяют эстафету, и сообщение добирается до всех вершин подграфа уровень за уровнем. ARP-запрос проводит такой обход ради одного адреса, а радиус обхода в Ethernet ограничен только доменом широковещания. Пока граф ацикличен, BFS безобиден: каждую вершину волна достигает по кратчайшему по числу ребер пути, и волна затухает.
В графе с циклом волна не затухает никогда. Кадр приходит в свитч по одному ребру кольца, выходит по второму, возвращается по кольцу с другой стороны, рассылается опять, копии плодятся экспоненциально, и домен тонет в широковещательном шторме за секунды. Таймера жизни на втором уровне нет, надеяться не на кого.
STP и минимальный остов как спасение от шторма
Spanning Tree Protocol решает задачу из учебника: дан связный граф, нужно выбрать подмножество ребер, соединяющее все вершины без циклов, то есть остовное дерево. Свитчи выбирают корневой мост по наименьшему идентификатору, затем каждый некорневой мост выбирает корневой порт, дающий кратчайший путь к корню, а на каждый сегмент назначается designated-порт. Все порты, не попавшие в дерево, блокируются для пересылки данных. Получившийся остов гарантированно ацикличен, и BFS-широковещание перестает быть смертельным. Если линк падает, протокол за десятки секунд, а в быстрой версии RSTP за доли секунды пересчитывает дерево и разблокирует запасные ребра.
Формально метрика здесь не вес, а стоимость пути до корня, потому дерево не всегда минимально по сумме весов классического Краскала или Прима, но дух задачи тот же самый. Практическое следствие задевает кошелек: заблокированные резервные линки простаивают, и потому в крупных сетях второй уровень ужимают зонтиками агрегации линков, VLAN-разбиением деревьев или вовсе заменяют на маршрутизацию до самого доступа.
Центральность, артикуляционные точки и цена одного маршрутизатора
Теория графов дает сетевику формальный словарь для разговора об узких местах. Центральность по посредничеству измеряет, через какие вершины проходит больше всего кратчайших путей, и маршрутизатор с высокой посреднической центральностью нагружен сильнее соседей ровно настолько, насколько он нужен чужому трафику. Артикуляционная точка строже: это вершина, удаление которой распиливает граф на несколько компонент связности. Единственный маршрутизатор между двумя корпусами завода является артикуляционной точкой, и его отказ не ухудшает связность, а отменяет ее целиком. Мосты в графе, ребра без альтернативного обхода, ведут себя так же на уровне линков.
Вывод для проектирования прямой: связность графа должна быть не меньше двух и по вершинам, и по ребрам там, где недопустимы отказы, а узкие места нужно искать до аварии алгоритмом поиска точек сочленения за линейное время, а не после аварии методом перезвона. Измерение центральности вообще стоит делать рутиной, потому что плановое обслуживание самого центрального узла требует не просто окна, а подготовленного обходного плана.
ECMP и Clos как практическая экономика графа
Когда модель графа построена и веса выставлены, из нее течет экономика. Если до назначения существуют два пути с одинаковой стоимостью, протокол не обязан выбирать любимца. Equal-cost multi-path складывает оба маршрута в таблицу, и потоки раскладываются по путям хешированием кортежа адресов и портов. Два гигабитных линка превращаются в два гигабита полезной полосы без покупки десятигигабитного порта, а отказ одного из них сводится к перекладке половины потоков за время сходимости. Цена приятная: хеш-раскладка порой кладет слона и муравья на одно ребро, и горячие потоки балансируются неровно, но это чинится тонкой настройкой без смены архитектуры.
Иерархическое дерево в датацентре упиралось в корень, который становился самой дорогой артикуляционной точкой на свете. Ответом стала топология Кло, пришедшая из телефонных коммутаторов пятидесятых: ярусы дешевых одинаковых коммутаторов, где каждый leaf соединен с каждым spine. Между двумя серверами возникает множество равных путей, и ECMP расстилает по ним трафик так равномерно, что переподписка превращается в статистическое недоразумение. Добавление мощности становится делением ребер: докупил spine-коммутаторов, получил новые параллельные пути, полоса выросла линейно. Отказ одного spine стоит лишь долю путей, и устойчивость достигается геометрией графа, а не филигранной инструкцией.
Взгляд на сеть как на граф окупается на каждом уровне стека: OSPF считает Дейкстрой, BGP опасается петель через путь, STP строит остов, TTL караулит от циклов, а датацентр раскладывает трафик по Кло. Математика здесь не украшение витрины, а рабочий станок, на котором вытачивается каждый маршрут.