Введение
Постановка задачи
Простейшее решение
Создание топологии
Организация широковещательной рассылки
Теоретический базис
Chord
Kademlia
CAN
Сравнительный анализ

Введение

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

Файлообменные системы, блокчейн, многопользовательские игры, мультимедиа-сервисы, распределённые вычисления — всё это примеры технологий, основанных на одноранговых сетях. Популярность подобных решений обусловлена рядом их характерных особенностей.

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

Саморегулирование. в сети отсутствует выделенный управляющий компонент, работоспособность сети поддерживается на базе соглашений между участниками. В качестве примера можно привести системы блокчейна, работоспособность которых гарантируется обязательствами участников сети соблюдать правила консенсуса;

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

Распределение нагрузки. Если в централизованной сети добавление каждого нового участника увеличивает нагрузку на сервер, то в децентрализованной системе каждый узел может выступать одновременно и потребителем, и поставщиком информации. Благодаря этому масштабирование сети не ограничивается производительностью отдельных компонентов — ресурсы увеличиваются по мере роста числа участников.

Дешевизна. Сеть строится на базе простых и недорогих программно-аппаратных компонентов общего назначения; нет необходимости в мощных вычислительных ресурсах.

Простота развертывания. Любой пользователь может присоединиться к сети с помощью достаточно простых операций, нет необходимости в специальных процедурах настройки. 

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

Стержнем, объединяющим разнородных участников в единую сеть, является возможность обмена информацией между ними. В клиент-серверных системах сетевое взаимодействие организовано достаточно тривиально: все компоненты подключены к центральному узлу — серверу, через который осуществляется передача данных от источников к получателям. В децентрализованных системах ситуация принципиально иная: отсутствует единый коммуникационный центр, и все участники взаимодействуют напрямую друг с другом. Именно поэтому организация сетевого взаимодействия в таких системах представляет собой гораздо более сложную и нетривиальную задачу.

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

Постановка задачи

Имеется одноранговая сеть, состоящая из множества узлов. Узлы обмениваются сообщениями между собой. Требуется:

1)  Реализовать адресную рассылку, т. е. обеспечить доставку сообщения от узла-отправителя к узлу-получателю;

2)  Реализовать широковещательную рассылку, т. е. обеспечить доставку сообщения от узла-отправителя ко всем узлам в сети.

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

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

В нашем описании идентификаторы мы будем представлять в виде чисел. Это упрощает понимание алгоритмов, но не меняет их сути, поскольку при переходе от чисел к набору байт логика работы алгоритма не изменяется.

Следующим компонентом исходных данных является допущение, что IP-адреса узлов нам известны. Способы их получения могут различаться. Например, в системе могут использоваться специальные серверы, хранящие и обновляющие информацию о текущем составе участников сети, их идентификаторах и IP-адресах. Также возможен запрос этой информации у одного из уже подключённых узлов. Ещё один подход — широковещательный запрос, в ответ на который узлы передают свои данные. Зачастую применяется процедура bootstrap: возвращается информация об узлах, ближайших к запрашиваемому, и запрос рекурсивно распространяется дальше к полученным адресатам.

Останавливаться на этих механизмах подробно мы не будем — тема объёмна и заслуживает отдельного рассмотрения. В рамках текущего материала будем исходить из предположения, что каждый узел располагает всей необходимой информацией.

Узлы с их идентификаторами образуют оверлейную сеть, которая работает поверх сети на базе IP адресов. Когда узел с идентификатором 1 пересылает сообщение узлу с идентификатором 2, он должен передать сообщение в IP адрес, соответстующий узлу с идентификатором 2. Таким образом, каждый узел должен хранить идентификаторы узлов, активных в данный момент в сети, и их IP-адреса.

 Итак, как нам обеспечить коммуникацию между узлами?

Простейшее решение

Простейшее решение заключается в том, чтобы организовать подключение всех узлов друг с другом.  В этом случае узел, отправляющий сообщение, по идентификатору получателя находит его IP-адрес и осуществляет пересылку по этому адресу.

Для маленьких сетей указанная схема вполне рабочая, но для больших сетей она не подойдет. Соединения между узлами в этом случае образуют полный граф (Рисунок 1), число ребер (т. е. число подключений) которого рассчитывается по формуле C = N (N – 1) / 2, где N – количество узлов. При увеличении количества узлов число связей между ними растет в геометрической прогрессии: так, например, если для 100 узлов требуется 4950 подключений, то для 1000 узлов необходимое число подключений возрастает до 499500.

Создание топологии

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

1. Как выбрать число C, т. е. максимальное число подключений для каждого узла? Ведь при увеличении этого значения растет общее количество устанавливаемых соединений. Как определить оптимальное значение?

2. Как изменять конфигурацию при добавлении/удалении какого-нибудь из узлов? В глобальной сети подобные ситуации возникают постоянно: кто-то из узлов завершает работу, кто-то, наоборот, подключается к сети. В этом случае строгое следование правилам подключения ближайших узлов приводит к неоптимальной топологии. Так, например, в примере на Рисунок 2 при отключении узла 5 узел 10 подключается к узлу 3, хотя ему лучше было бы подключиться к узлу 1 – в этом случае число промежуточных узлов будет одинаково для всех маршрутов. Другими словами, все маршруты имели бы одинаковую длину. 

Организация широковещательной рассылки

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

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

Рассмотрим пример топологии, изображенный на Рисунок 3. Узел 1 передает сообщения своим ближайшим соседям 3 и 5; узел 3 передает сообщение ближайшему соседу 7; узел 7 передает сообщение соседям 5 и 10, узел 5 получит это же сообщение от узла 10. Узел 5 пересылает полученные сообщения узлу 1. Таким образом, узел 5 получит одно и то же сообщение 2 раза, и передаст их узлу-отправителю 1, поскольку этот узел является для него ближайшим.

Как видно, узлы должны распознавать дублирующиеся сообщения и прекращать их дальнейшую пересылку — иначе сообщения будут бесконечно циркулировать по замкнутым контурам. В приведённом примере узел 1 не должен передавать полученные сообщения узлу 3.

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

Каким образом можно назначать уникальные признаки? Например, каждому сообщению можно присваивать уникальный номер, который в совокупности с идентификатором узла формирует уникальный идентификатор сообщения. Также можно использовать хэш-сумму содержимого, либо назначать специфические атрибуты, присущие данной сети. 

В теории все выглядит неплохо, но на практике рассмотренный алгоритм имеет множество проблем. Сеть наводняется дубликатами; счетчики сообщений могут переполняться; хэш-суммы могут давать коллизии; хранение базы данных полученных идентификаторов требует дополнительной памяти; поиск идентификатора при получении сообщения занимает много времени; отсутствуют чёткие критерии, когда можно удалять записи из базы; множество других подводных камней. Как результат, решение не работоспособно.

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

Другим способом организации широковещательной рассылки является так называемая «рассылка по запросу». Узел, инициирующий рассылку, сначала направляет уведомления соседним узлам. Эти уведомления содержат уникальные признаки данных, подлежащих передаче. Получив уведомление, узлы проверяют, поступали ли такие данные ранее. Если нет — они отправляют запрос обратно инициатору, чтобы получить соответствующую информацию. После получения данных узлы уведомляют своих соседей о наличии новых сведений. Процесс повторяется до тех пор, пока все участники сети не получат нужные данные. Поскольку уведомления имеют небольшой размер, их дублирование не приводит к заметным накладным расходам.

Описанный механизм доказал свою работоспособность — он применялся в ранних реализациях одноранговых сетей. Однако у него есть ряд недостатков:

• сложный протокол обмена между узлами;

• низкая скорость распространения информации из-за большого количества сообщений «запрос – ответ»;

• невозможность полного устранения дубликатов: одни и те же данные могут многократно пересылаться по повторяющимся маршрутам;

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

Как видим, организация широковещательной рассылки представляет собой далеко не тривиальную задачу.

Теоретический базис

Проблемы, связанные с построением эффективных способов маршрутизации в P2P сетях, стимулировали многочисленные исследования в этой области. Первые решения начали появляться в 2001 году, и с тех пор интерес к теме не ослабевает. Несмотря на обширное разнообразие разработанных алгоритмов, различия между ними сводятся к двум основным аспектам: как строится топология сети, и как осуществляется ее обход.

Далее мы рассмотрим три классических алгоритма: Chord, Kademlia, и CAN, использующих соответственно кольцевую, древовидную и пространственно-многомерную топологии. Выбор этих алгоритмов обусловлен рядом факторов:

1)  Они наглядно иллюстрируют фундаментальные принципы и подходы к решению задачи маршрутизации;

2)  Хотя Chord и CAN были предложены в 2001 году, а Kademlia — в 2002-м, они по-прежнему сохраняют актуальность и применяются в реальных системах;

3)  Большинство последующих разработанных решений опираются на модификации этих алгоритмов либо комбинируют заложенные в них идеи. 

Chord

Идея, лежащая в основе Chord (академическое описание здесь), очень проста. Множество узлов упорядочивается по возрастанию их идентификаторов. Каждый узел устанавливает соединение с последующим в списке, а последний узел — с первым. Таким образом формируется кольцевая топология (Рисунок 4), в которой идентификатор следующего узла всегда больше идентификатора предыдущего. Для построения маршрута каждый узел последовательно передаёт сообщение своему последователю, пока оно не достигнет адресата. При добавлении нового узла в сеть или при выходе одного из узлов, его предшественник перенаправляет соединение на ближайшего последователя, тем самым восстанавливая кольцевую структуру.

Очевидно, что маршрутизация по такой схеме будет осуществляться очень медленно. В худшем случае количество шагов составляет O(N), где N – количество узлов. Для оптимизации требуется сократить число промежуточных узлов в маршруте, для чего Chord предлагает использовать finger table (адаптированный перевод звучит как «таблица указателей», или «таблица ссылок»).

Указанная таблица формируется следующим образом. Пусть m – количество бит в идентификаторе узла. Каждый узел с номером n формирует таблицу размерности m, ячейки таблицы заполняются по формуле entry (i) = (n + 2^i) mod 2^m. Каждая таблица ячейки указывает на узел, находящийся на расстоянии, в два раза превышающий расстояние от предыдущего узла. Если узел с таким номером отсутствует в сети, то в ячейку таблицы записывается узел, ближайший от требуемого (Рисунок 5).

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

Теперь рассмотрим, как в Chord организуется широковещательная рассылка. Узел-инициатор отправляет сообщение всем узлам из своей маршрутной таблицы. Получившие сообщение узлы повторяют это процесс в соответствии с своими таблицами. Таким образом, все узлы получат сообщение за m шагов (напомним, здесь m – это количество бит в идентификаторе узла).

Однако записи в маршрутных таблицах различных узлов могут ссылаться на одни и те же узлы, что приводит к появлению дубликатов. Для их исключения применяется следующая стратегия: каждое сообщение содержит дополнительное поле, называемое limit. Это поле ограничивает множество узлов, которым следует пересылать сообщение. Значение limit при пересылке сообщения соответствующему узлу из таблицы равно записи в следующей ячейке этой таблицы.

Поясним сказанное на примере. Представим, что у нас идентификатор узла имеет размерность 3, т. е. максимальное количество узлов в системе будет 8 (Рисунок 6). Предположим, что узел 1 является инициатором широковещательной рассылки. В его маршрутной таблице находятся узлы 2, 3, и 5, которым он будет рассылать это сообщение. Узел-инициатор видит, что при пересылке сообщения узлу 2 следующая запись в маршрутной таблице является узлом 3. Это значение, т. е. “limit” (обозначен как D3), пересылается узлу 2. Узел 2 видит, что лимит полученного сообщения равен 3, т. е. узел 2 должен переслать полученные сообщения тем узлам, номера которых меньше полученного лимита. Таких узлов в маршрутной таблице нет, поэтому узел 2 дальнейшей рассылки не производит.

Исходя из своей маршрутной таблицы, узел 1 также пересылает сообщение узлу 3. Следующая запись в маршрутной таблице для этого узла будет 5, этот лимит вместе с сообщением высылается узлу 3 (D5). Узел 3 видит, что в его таблице есть узлы меньше, чем полученный лимит (это узел 4). Следовательно, он осуществляет пересылку данному узлу.

Узел 1 также пересылает сообщение узлу 5, здесь запись в маршрутной таблице отсутствует, значит, в соответствии с кольцевой топологией последователем узла 5 является узел 1 (т. е. сам отправитель). Это значение как лимит отправляется вместе с сообщением. Описанный процесс итеративно повторяется всеми узлами, и широковещательная рассылка заканчивается в среднем за log N шагов (точное значение зависит от того, насколько близко количество узлов соответствует степени 2).

Kademlia

Рассмотрим другой популярный алгоритм маршрутизации — Kademlia (академическое описание здесь), который опирается на топологию в виде дерева. Также, как и в Chord, узлы в Kademlia упорядочиваются по расстоянию между ними. Однако расстоянием здесь служит не арифметическая разность между значениями идентификаторов узлов, а величина близости идентификаторов друг к другу. Мерой близости идентификатора выступает операция «исключающее или» между узлами.

Все пространство ключей разбивается в группы, которые называются бакетами. Емкость каждого очередного бакета в два раза больше предыдущего, в бакете хранится диапазон ключей с расстояниями от 2 в степени i до 2 в степени i+1. Таким образом, у нас образуется дерево ключей (Рисунок 7). Узел, подключающийся к сети, должен установить подключение с произвольным узлом из каждого непустого бакета.

При передаче сообщения узел сначала определяет, в каком бакете находится адресат, и пересылает сообщение одному из множества узлов требуемого бакета, с которыми установлено соединение. Получивший сообщение узел повторяет процесс в своей структуре ключей. Этот итеративный процесс продолжается до тех пор, пока сообщение не достигнет целевого узла. Теоретическая оценка длины маршрута приближается к log (N).

Важно отметить, что дерево — это всего лишь графическое представление структуры, на практике нет необходимости строить его явным образом. При передаче достаточно определить нужный бакет и выбрать из него произвольный узел для дальнейшей пересылки.

Теперь рассмотрим, как в Kademlia осуществляется широковещательная рассылка. Узел- инициатор выбирает по одному узлу из каждого бакета и высылает ему сообщение (Рисунок 8). Сообщению присваивается параметр «высота», равный текущему количеству бакетов в дереве. Получившие сообщение узлы повторяют процесс для своих бакетов, уменьшая передаваемое значение высоты на единицу меньше, чем полученная. Процесс продолжается, пока высота не станет равной нулю

Особенностью алгоритма является тот факт, что, в отличие от Chord, маршрут сообщения в Kademlia не детерминирован: каждый узел в маршруте должен выбрать один узел из соответствующего бакета, но выбор конкретного узла осуществляется случайным образом. Эта особенность введена с целью повышения устойчивости к атакам типа «отказ в обслуживании».

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

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

CAN

Рассмотрим еще один, на мой взгляд, самый необычный алгоритм маршрутизации, Content-Addressable Network (аббревиатура CAN, академическое описание здесь). Он строится по топологии многоразмерной декартовой системы координат, отображенной на тор соответствующей размерности. Эта координатная система является виртуальной и не связана с какой-либо физической пространственной системой.

Формирование такой системы можно представить следующим образом. Двумерное пространство образует плоскость, причем каждому измерению соответствует своя отдельная плоскость. Если скруглить эти плоскости, а получившиеся окружности соединить вдоль центральной оси, то получится d-мерный тор (Рисунок 9). На Рисунок 10 показан тор в разрезе.

В дальнейшем, для упрощения и наглядности, мы будем использовать двумерную систему координат, однако следует помнить, что описанная топология масштабируется на свернутое пространство произвольной размерности d.

Идентификаторы узлов отображаются на точки в координатном пространстве. Каждый узел владеет отдельной зоной в координатном пространстве, и в пределах этой зоны он знает о своих соседях, расположенных в других зонах. В d-мерном координатном пространстве зоны считаются соседними, если они имеют общую координату вдоль одной размерности и смежные координаты по всем остальным. Так, в двумерной системе координат, изображенной на Рисунок 11, зона 4 имеет соседей 3, 1, 5, 7, поскольку эти узлы имеют одну общую сторону по оси X либо Y  и смежную сторону по какой-либо из других осей. Зона 8 не является соседней, поскольку не имеет общей стороны с узлом 4.

Возникает вопрос: как отобразить идентификатор узла на точки d-мерного пространства? В общем случае это осуществляется с помощью специальной хэш-функции, которая для заданного идентификатора узла возвращает уникальный набор координат. На практике часто используют простой, но эффективный алгоритм разделения: n-битовое представление идентификатора узла делится на отрезки равной длины, количество которых равно d. Набор бит в каждом отрезке представляет собой i-ю координату (Рисунок 12). 

Маршрутизация в сети CAN осуществляется с помощью жадного алгоритма: на каждом шаге ищется соседняя зона с координатами, ближайшими к узлу-получателю, и сообщение передается в соответствующую зону (Рисунок 13). Поскольку соседних зон может быть несколько, то в сети CAN существует множество альтернативных маршрутов, что повышает надежность сети. Теоретическая оценка скорости маршрутизации соответствует N в степени 1/d.

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

При подключении новых узлов соответствующие зоны делятся; при отключении — объединяются, и объединённой зоной начинает управлять оставшийся узел (Рисунок 14). При этом реконфигурация затрагивает только изменяющиеся зоны, так как именно в них меняется состав соседей. Остальные зоны сети остаются неизменными, т.е. реконфигурация затрагивает только локальный участок в сети.

Далее рассмотрим, как в CAN осуществляется широковещательная рассылка. В отличие от предыдущих алгоритмов, где она реализуется естественным образом с использованием тех же принципов, что и адресная передача, в CAN процесс оказывается значительно более сложным. Долгое время не удавалось разработать надежный механизм, обеспечивающий быструю рассылку без дубликатов. Хотя CAN был предложен ещё в 2001 году, по-настоящему эффективный алгоритм широковещательной рвссылки появился только в 2013 году. Рассмотрим его работу.

Узел-отправитель сообщения рассылает его по всем направлениях. Узел, который получает сообщение вдоль размерности i в направлении dir, передает сообщение по следующим правилам:

1)  всем остальным размерностям от 1 до i-1;

2)  вдоль размерности i в направлении dir.

На Рисунок 15 показан процесс маршрутизации для двухмерной системы координат. Узел-отправитель (обозначен серым цветом) инициирует рассылку, отправляя сообщение в соседние зоны по всем направлениям: влево, вправо и вверх. Узел D, получив сообщение по размерности 2 в восходящем направлении, пересылает его соседним узлам по оставшимся размерностям (в данном случае по размерности 1 в соседнюю зону Z), а также соседям по восходящей траектории (в зоны C и E).

В описанной схеме возможны дубликаты сообщений. В нашем примере узел Z получит одно и то же сообщение от узлов F и D. Для предотвращения дубликатов применяется угловой критерий: узел передаёт сообщение соседней зоне только в том случае, если его собственная зона прилегает к нижнему углу соответстующей соседней зоны. Так, на  Рисунок 16 узел F передаёт сообщение узлу Z, поскольку его зона в направлении передачи граничит с нижним углом зоны Z. В то же время узел D не передаёт сообщение узлу Z, так как не соприкасается с нижним углом его зоны.

В описанной схеме при применении углового критерия удаётся устранить дубликаты лишь вдоль одной размерности. Иными словами, когда сообщение передаётся узлам по размерностям 1…i–1, угловой критерий допустим только для первой размерности. Для остальных применять его нельзя, иначе рассылка будет работать некорректно. В результате дубликаты всё равно возникают.

Так, на Рисунок 16 узел D, получив сообщение по размерности 2, применяет угловой критерий к узлу Z, а затем передаёт сообщение по оставшейся размерности 1 узлу E. В свою очередь, узел C, получив сообщение от D, также пересылает его узлу E, поскольку угловой критерий в этом случае допускает передачу.

Для устранения дубликатов вдоль остальных размерностей вводится пространственное ограничение — набор фиксированных значений по каждой размерности, произвольно выбранных из координат узла-инициатора. Этот набор определяет гиперплоскость размерности d; при передаче по одной из размерностей формируется ограничение размерности d-1, и так далее. На последней размерности гиперплоскость превращается в прямую, и сообщение передаётся только тем узлам, чьи зоны эта прямая пересекает в заданном направлении.

Таким образом, при получении сообщения вдоль размерности k, узел пересылает его по той же размерности только в одном направлении. К остальным размерностям применяются следующие правила:

1) для узлов размерностей 1…k -1 сообщение передаются только тем узлам, зоны которых пересекают пространственное ограничение на соответствующей размерности;

2) для узлов размерностей k+1…d сообщение передается только тем узлам, которые удовлетворяют угловому критерию.

Рисунок 17 иллюстрирует алгоритм для двумерной сети (d = 2). Инициатор задаёт единственное пространственное ограничение по размерности 1, выбрав значение 10 (нижний правый угол). Узел D, получив сообщение, передаёт его узлу C, поскольку прямая пространственного ограничения пересекает его зону. В то же время сообщение не передаётся узлу E, так как его зона не пересекается с этой прямой.

Указанные принципы применимы к сети любой размерности. Так, на Рисунок 18 представлена трёхмерная сеть. Узел-отправитель пересылает сообщение вдоль третьей размерности только тем узлам, чьи зоны пересекают заданную плоскость. В этой плоскости задача сводится к предыдущему примеру, показанному на Рисунок 17: используется пространственное ограничение по размерности 1 и двумерный угловой критерий. Затем, при передаче сообщения вдоль размерности 1, применяется уже трёхмерный угловой критерий. 

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

Сравнительный анализ

Какой дизайн выбрать для децентрализованной системы? Однозначного ответа на этот вопрос не существует. Рассмотренные алгоритмы основаны на принципиально разных подходах и демонстрируют различное поведение в зависимости от особенности работы сети. Этой теме посвящено множество фундаментальных научных работ; заинтересованным читателям можно порекомендовать, например, сравнительноее исследование. Тем не менее, в рамках нашей статьи мы постараемся провести качественный анализ, выявляя сильные и слабые стороны каждого алгоритма.

Критерии оценки представлены в таблице ниже.

Сложность реализации. Мы все видели, насколько прост Chord с точки зрения идеи и насколько более сложной оказывается реализация CAN. Kademlia занимает промежуточное положение: её концепции интуитивны, но реализация требует большей проработки, чем в Chord.

Детерминированность маршрута. Характеризует степень предсказуемости пути, по которому проходят сообщения. В Chord маршрут строго детерминирован. В Kademlia он потенциально недетерминирован: выбор соседнего узла зависит от актуального состояния таблиц и может варьироваться. В CAN все зависит от реализации: при наличии нескольких альтернативных направлений можно задать правило выбора ближайшей зоны — в этом случае маршрут станет детерминированным.

Устойчивость к churn. Термин churn подразумевает стабильность работы сети при частом входе-выходе узлов. Сhord в этом плане демонстрирует наименьшую стабильность — при входе-выходе узлов ему требуется перенастройка топологии и обновление finger table таблиц. Kademlia показывает высокую устойчивость — ее таблицы обновляются только в тех узлах, которые непосредственно взаимодействуют с подключившимся или отключившимся узлом. CAN в этом плане занимает промежуточное положение — при выходе узла требуется локальная перестройка топологии у его соседей, а при входе нового узла необходимо знание топологии всей сети для определения соседней зоны.

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

Объем памяти. В Chord размер маршрутной таблицы фиксирован: каждая запись содержит только идентификатор соответствующего узла. В Kademlia маршрутизаторы хранят идентификаторы узлов в k-бакетах, охватывающих разные диапазоны XOR-расстояний. Общее число записей может превышать число соседей. В CAN хранится информация лишь о соседних зонах и соответствующих узлах, что делает требования к памяти весьма умеренными.

Адаптивность. Подразумевается возможность настройки алгоритма для оптимизации его работы под конкретную систему. Chord в этом отношении наименее гибок — возможности параметрической настройки практически отсутствуют. В Kademlia адаптация ограничена изменением размера бакетов, параметров запроса и стратегий выбора соседей. CAN предлагает множество конфигурационных параметров: выбор размерности пространства, критерии выбора направления маршрута, правила локального обновления и другие — что делает его более гибким и настраиваемым.

Приведённые критерии не охватывают всех возможных аспектов — выбор архитектуры может зависеть от множества дополнительных факторов. Тем не менее, они способны служить надёжной отправной точкой при проектировании децентрализованной системы.

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