Это перевод предрелизного блог-поста одного из разработчиков сети Yggdrasil, в котором он попытался дать расширенное объяснение изменений, которые коснутся сети после релиза 0.5.

На мой взгляд, изменения достаточно интересные и вдохновляющие. Ждём с нетерпением. Клиент под Android, я уже начал дорабатывать под эти изменения, сборки уже тестируются энтузиастами русскоязычного сообщества.

Но, хватит вступительных слов, предоставляю речь Arceliar:

Введение

Поскольку скоро выйдет версия 0.5.0, кажется, сейчас самое время объяснить, над чем мы работали последние пару лет. Хотя в целом мы вполне довольны версией 0.4.X, в этой конструкции есть несколько проблем, которые могут привести к тому, что сеть будет вести себя не так, как нам нравится. Целью этой публикации в блоге является краткий обзор того, как работает версия 0.4, объяснение проблем, связанных с этим подходом, и описание изменений, которые мы внесли в версию 0.5, чтобы попытаться их решить.

Текущее состояние

Схема маршрутизации версии 0.4.X состоит из трех основных компонентов:

1. Маршрутизация на основе DHT, используемая для отправки трафика, когда маршрут к месту назначения неизвестен.

2. Жадная схема маршрутизации в виде дерева, используемая для маршрутизации трафика в DHT и «поиск пути» для исходной маршрутизации.

3. Схема исходной маршрутизации, которая кодирует путь, найденный в древовидном пространстве, в заголовках пакетов, поэтому трафик может идти по более прямому маршруту, чем тот, который предлагает DHT (и продолжать работу, пока состояние дерева меняется).

Жизненный цикл соединения проходит через эти три этапа последовательно. Во время первоначального обмена ключами путь к месту назначения неизвестен, поэтому трафик маршрутизируется через DHT. Когда узлы получают трафик, пришедший через DHT, они инициируют поиск пути, чтобы найти более эффективный маршрут через древовидное пространство. Когда поиск пути завершается, они переключаются на маршрутизацию источника (source routing), которая инкапсулирует пакет, маршрутизируемый по DHT, внутри пакета, маршрутизируемого источником. Если пакет, отправленный источником, когда-либо заходит в тупик, заголовок маршрутизации источника удаляется и маршрутизация завершается через DHT. Получение этого маршрутизируемого пакета DHT запускает поиск пути в фоновом режиме, чтобы найти новый путь.

В целом, эта конструкция работает хорошо. Узлы могут начать взаимодействие (в нашем случае отправлять трафик обмена ключами) до того, как потребуется искать какие-либо маршруты, и все изящно откатится назад. Для обнаружения поврежденных путей не требуется никакого дополнительного трафика, поскольку резервный вариант DHT заботится о сигнализации о пропаже пути.

Проблемы

Хотя у меня нет никаких опасений по поводу общего дизайна версии 0.4, у всех отдельных компонентов есть проблемы.

Прежде всего, дизайн DHT, использованный в версии 0.4, масштабируется не так хорошо, как мы надеялись. Узлам необходимо отслеживать не только пути к своим соседям по пространству ключей, но и любые такие пути, проходящие через свой узел. Это означает, что некоторая часть узлов оказывается в положении, когда она помнит большой процент всех путей через свой узел. Это приводит к высоким затратам памяти и потенциально большому трафику. Использование трафика DHT в сети версии 0.4 относительно невелико, поскольку DHT преимущественно представляет собой жесткое состояние, но все попытки создать более безопасный DHT привели к проектам с мягким состоянием, при которых затраты трафика могут стать значительными. Без защиты DHT останется уязвимым для некоторых атак (или будет вести себя плохо при наличии неправильно настроенных узлов, таких как случайные узлы anycast). Более коварной проблемой является время конвергенции DHT: в худшем случае для конвергенции требуется O(n) шагов, и у нас есть веские основания полагать, что в некоторых типичных юзкейсах это происходит. Кроме того, конструкция с жестким состоянием требовала активного мониторинга каждого пир-соединения, чтобы быстро обнаружить, когда канал не работает. Это приводит к гораздо большему количеству трафика между узлами в простое, чем нам хотелось бы видеть.

Во-вторых, дерево может создавать противоречивые представления о сети, в зависимости от того, на информацию какого узла обращает внимание узел. Это приводит к «колебаниям» (flapping), когда неродительское соединение рвётся, поскольку узлы имеют тенденцию переключаться на нового родителя, который использовал то же самое (теперь неработающее) соединение, но у которого еще не было времени объявить о разрыве соединения. Таким образом, узлы имеют тенденцию переключаться со своего родительского узла на альтернативный, а затем обратно на исходный родительский, когда альтернатива в конечном итоге сообщает о той же ошибке. Это колебание приводит к колебанию узлов по всему дереву (всех дочерних), что может каскадно распространяться по сети. В версии 0.4 существуют механизмы, позволяющие регулировать скорость изменений, но это временное решение основной проблемы в дизайне.

Наконец, маршрутизация от источника (source routing) в принципе хороша, а вот формат пакета, который мы для этого использовали, — нет. Злоумышленнику слишком легко вставить несколько избыточных хопов для создания (конечного) цикла, что может привести к потере пропускной способности на целевом наборе узлов.

Изменения

В дизайн Иггдрасиль было внесено немало изменений, направленных на борьбу с вышеперечисленными проблемами. Новые подходы не обязательно соответствуют тому, как мы хотим, чтобы сеть функционировала в долгосрочной перспективе, а, скорее, являются альтернативами, которые мы хотели бы протестировать, чтобы лучше изучить пространство возможных решений. Вообще говоря, они не ориентированы на пользователя, за исключением некоторых изменений в информации, доступной в yggdrasilctl API.

Поиск путей

Наиболее значительным изменением является удаление схемы маршрутизации на основе DHT, которая использовалась для первоначальной настройки маршрутов через древовидное пространство. Теперь мы используем более простой протокол поиска YggIP/key->coord, который напоминает поиск ARP/NDP в широковещательной сети Ethernet (но без широковещательного трафика через всю сеть). Узлы отслеживают, какие узлы доступны по линку в дереве (то есть родительский и дочерние узлы), а также фильтр Блума ключей всех узлов, доступных по этому соединению (с усеченными ключами до частей, используемых в /64, чтобы обеспечить поиск IP/префиксов). Пакет поиска, полученный по линку из дерева, пересылается на любой другой линк дерева, у которого пункт назначения находится в фильтре Блума.

Несмотря на недостатки этого подхода, он имеет ряд преимуществ. Во-первых, случайные конфигурации anycast (с использованием одного и того же ключа от нескольких узлов) не нарушают какие-либо общесетевые структуры данных, а просто приводят к тому, что поисковый трафик поступает на более чем один узел. Последующие шаги, как правило, завершаются неудачей (поиск маршрута, обмен ключами и т. д.), но это не наносит побочного ущерба остальной части сети. Во-вторых, для этого требуется очень мало трафика для обслуживания в режиме ожидания и требуется только константное количество состояний для каждого узла. Это означает, что узлы в ядре сети не несут ответственности за поддержание состояния чего-либо, кроме своего непосредственного окружения, и не перегружены трафиком DHT в простое, исходящим от удаленных узлов. Аналогично, узлам на периферии сети не нужно отправлять регулярный трафик поддержки активности DHT, что может помочь с использованием трафика и энергопотреблением на мобильных устройствах. В-третьих, эта структура сходится асинхронно и во времени, пропорциональном глубине дерева, а не последовательно и во времени, пропорциональном размеру сети, поэтому можно избежать очень плохого времени сходимости DHT для наихудшего сценария.

Основным недостатком этого подхода является то, что фильтры Блума могут и будут генерировать ложные срабатывания по мере заполнения. На практике мы ожидаем, что фильтры в «ядре» сети насыщаются, когда каждый узел оказывается доступным по любому пути. Это, в свою очередь, означает, что маршрут узла к «ядру» сети (обычно через родительский узел) возьмет на себя роль «маршрута по умолчанию» и будет получать копию каждого запроса, отправленного узлом. Мы ожидаем, что поисковый трафик достигнет ядра сети, будет эффективно действовать как широковещательный трафик внутри ядра, а затем будет отсеиваться фильтрами Блума по мере приближения к краям (так что узел с краю сети вряд ли получит какой-либо трафик, который для него не предназначен). Короче говоря, узлы в ядре будут меньше использовать память и меньше трафика в простое, но активное использование сети будет потреблять больше трафика. Еще неизвестно, является ли это выгодным компромиссом.

Просто чтобы подвести некоторые итоги: мы используем 8192-битные фильтры Блума с 8 хеш-функциями. Если есть узел, который действует как шлюз в подсети с 200 узлами, то вероятность ложных срабатываний составляет примерно 1 на миллион (то есть мы ожидаем, что сети потребуется около миллиона узлов, прежде чем шлюз увидит какой-либо ложноположительный поисковый трафик [lookup traffic]). Большая часть трафика поиска является правильным вплоть до шлюза в подсети из 500 узлов в сети с 1 миллионом узлов.

Таким образом, на практике большинство узлов не должны видеть сколько-нибудь значимого количества ложных срабатываний, если только они не действуют как шлюз в очень большую подсеть (или не находятся в сети, на много порядков превышающей текущую сеть версии 0.4). В нашей нынешней сети несколько узлов могут оказаться в «ядерном» регионе, где они получают ложноположительный поисковый трафик от большинства поисков. Мы надеемся, что это по-прежнему предпочтительнее постоянного трафика DHT в простое, и потенциально очень высоких требований к памяти.

CRDT-дерево

Раньше расположение каждого узла в дереве проверялось цепочкой подписей (ссылками на родительский узел) от узла обратно к корню. Это может привести к несоответствиям, когда разные узлы имеют взаимно несовместимые представления об одном и том же предке (например, узел A говорит, что родитель P имеет прародителя G, но узел B говорит, что тот же родитель P имеет прародителя G'), что усложняет выбор родителя в ответ на изменения в состояние сети. Чтобы решить эту проблему, мы разбили информацию дерева на отдельную информацию для каждого линка, которая передается между узлами и объединяется в структуру CRDT. Это заставляет узлы иметь локально согласованное представление о сети, что предотвращает ненужные «колебания» в некоторых случаях, когда маршрут узла к корню нарушен. Это также уменьшает объем информации, которая должна быть отправлена по сети, поскольку узлу не нужно отправлять информацию обратно партнеру, если он знает, что партнер уже видел ее.

Жадная маршрутизация

Маршрутизация от источника (source routing из версии 0.4) была удалена в пользу жадной маршрутизации (greedy routing, как это было сделано в версии 0.3.X). В стабильной сети это не влияет на маршрут, по которому проходят пакеты, а только на то, как принимается решение о выборе этого маршрута. Возможно, в будущем мы вернемся к подходу с маршрутизацией от источника, но подход, использованный в версии 0.4, имел некоторые проблемы, которые необходимо было решить в первую очередь. Маршрутизация источника — это хорошая оптимизация производительности, если ее можно выполнить безопасно, но это не является явной целью данного проекта. Хотя у меня есть идеи, как это сделать, в краткосрочной перспективе это не является приоритетом. Поскольку схема маршрутизации от источника, предположительно, по-прежнему будет зависеть от жадной маршрутизации для поиска пути, я думаю, что в этом выпуске полезно сосредоточиться на стресс-тестировании части сети с жадной маршрутизацией и оставить маршрутизацию от источника на тот случай, когда другие части стека станут ближе к стабильному состоянию.

Keep-alive для каждого узла удалён

Мы больше не спамим по пир-линкам пакеты с keep-alive каждые несколько секунд. Вместо этого при отправке трафика нам требуется подтверждение в течение нескольких секунд (если только отправленный нами трафик не был подтверждением). Это означает, что мы не так быстро обнаруживаем сбои канала в простое (нам нужно дождаться пользовательского трафика или трафика протокола, чтобы использовать соединение), но это должно снизить потребление трафика в режиме ожидания (и, вероятно, снизить энергопотребление на мобильных устройствах). Обратите внимание, что это отличается, например, от собственных механизмов поддержки активности TCP, которые остаются включенными (TCP Keep-alive).

Новые возможности

В версии 0.5 также добавлено несколько новых функций. Теперь можно ограничить пиринг с помощью аргумента ?password=X в строках Listen и Peers (и в конфигурации мультикаста). Это требует, чтобы узлы согласовали пароль, прежде чем они начнут пиринг. Обратите внимание, что это не позволяет обеспечить сетевую изоляцию: узлы по-прежнему могут взаимодействовать с остальной частью сети, если захотят, а доступ по-прежнему транзитивен. Это упрощает ограничение круга лиц, которые могут автоматически подключаться внутри подсети, или настройку публичного пира, не разрешая подключения всем, кто его может найти. Также есть поддержка quic:// соединений. Пиринг через QUIC будет использовать только один поток трафика, поэтому его семантика во многом аналогична пирингу через TCP/TLS, но он может быть полезен в тех случаях, когда UDP-пакетам легче пройти через NAT или брандмауэр. Обычно мы ожидаем, что он будет работать хуже, чем TCP/TLS, поэтому не рекомендуем использовать его, когда в нем нет необходимости.

Итоги

Если не считать непредвиденных задержек, Yggdrasil v0.5 должен выйти в течение следующих нескольких недель. Мы надеемся, что мы решили наиболее важные проблемы со стабильностью и масштабированием в версии 0.4 и значительно сократили объем памяти и потребление трафика в режиме ожидания для некоторых узлов. Некоторые аспекты нового дизайна радикально отличаются от версии 0.4, поэтому еще неизвестно, насколько хорошо эти изменения будут работать в реальном мире. Предварительные тесты (и большое количество симуляций) вселяют в нас оптимизм в отношении того, что версия 0.5 даст нам стабильную основу для дальнейшего развития, пока мы изучаем любые ограничения этого нового подхода и работаем над неизбежным изменением дизайна для версии 0.6.