Компьютерную сеть можно лишить сразу нескольких каналов связи, но данные всё равно доберутся до получателя, если оборудование умеет правильно выбирать обходные пути. Исследователи Маттиас Бентерт и Штефан Шмид выяснили, при каком устройстве сети можно гарантировать доставку информации при любых обрывах соединений, пока сохраняется хотя бы один рабочий маршрут. Учёные обнаружили всего четыре сетевые структуры, которые мешают добиться абсолютной отказоустойчивости, и тем самым решили математическую задачу, остававшуюся открытой с 2012 года.
Когда человек смотрит фильм онлайн, отправляет сообщение или открывает сайт, информация путешествует по сети в виде небольших пакетов. На пути к получателю каждый пакет проходит через множество маршрутизаторов, которые решают, куда направить его дальше. Если очередной канал связи перестаёт работать, оборудование пытается найти обходной путь.
Самым очевидным решением было бы пересчитывать все маршруты после каждого сбоя. Однако в большой сети подобные вычисления могут занимать несколько секунд, тогда как маршрутизатору приходится принимать решения за доли миллисекунды. Поэтому исследователи рассматривают способ, при котором устройство опирается только на доступную ему информацию: адрес получателя, канал, по которому поступил пакет, и состояние собственных соединений.
Проблема в том, что маршрутизатор не знает, какие соединения оборвались в других частях сети и где пакет успел побывать. Из-за этого данные могут попасть в петлю и начать бесконечно перемещаться между одними и теми же устройствами, хотя дорога к получателю остаётся открытой.
Чтобы выяснить, при каких условиях возникают подобные ловушки, Бентерт и Шмид обратились к теории графов. Математики представили сеть в виде точек, обозначающих маршрутизаторы, и линий между ними. Удаляя отдельные точки и линии или объединяя соседние узлы, можно свести сложную сеть к более простым схемам и изучить её фундаментальные свойства.
В 2020 году исследователи нашли две простые сетевые конфигурации, для которых невозможно составить универсальные правила перенаправления пакетов. Бентерт обнаружил ещё две и вместе со Шмидом математически доказал, что других минимальных препятствий для абсолютной отказоустойчивости в рассматриваемой модели не существует.
Для сетей, в которых отсутствуют все четыре проблемные структуры, учёные разработали алгоритм, напоминающий известный способ выхода из лабиринта: на каждом перекрёстке нужно придерживаться правой стороны. Маршрутизаторы получают заранее составленные списки соединений и выбирают следующее направление в установленном порядке, пропуская неработающие каналы. Авторы также предложили быстрый способ определить, позволяет ли устройство конкретной сети добиться абсолютной отказоустойчивости.
Самым неожиданным оказался вывод о резервных соединениях. Обычно дополнительные каналы повышают надёжность связи, однако чем больше путей соединяют разные узлы, тем выше вероятность обнаружить одну из четырёх проблемных структур. Получается, что даже густая сеть с множеством запасных маршрутов может иметь принципиальные ограничения, которые невозможно устранить простой настройкой локальных правил пересылки пакетов.
Пока работа остаётся теоретической: учёные не учитывали скорость доставки информации и загруженность каналов, от которых напрямую зависит качество связи в реальных сетях. Теперь исследователи планируют проверить, изменится ли ситуация, если каждый пакет сможет запоминать несколько последних посещённых узлов. Возможно, даже небольшой объём дополнительной информации позволит гарантировать доставку данных в гораздо большем числе сетей.
