Koorde - Koorde

В пиринговый сети, Koorde это Распределенная хеш-таблица (DHT) система на основе Аккорд DHT и График де Брюйна (Последовательность де Брюйна ). Унаследовав простоту Chord, Коорде встречает O (log n) переходов на узел (где n - количество узлов в DHT) и O (log n / log log n) переходов на запрос поиска с O (log n) соседями. на узел.

Концепция Chord основана на широком диапазоне идентификаторов (например, 2 ^ 160) в структуре кольца, где идентификатор может обозначать как узел, так и данные. Узел-наследник отвечает за весь диапазон идентификаторов между собой и своим предшественником.

Графики де Брейна

Трехмерный граф де Брейна

Коорде основан на Аккорде, но также и на График Де Брёйна (Последовательность де Брюйна В d-мерном графе де Брейна имеется 2d узлы, каждый из которых имеет уникальный d-битовый идентификатор. Узел с ID i подключен к узлам 2i по модулю 2d и 2i + 1 по модулю 2d. Благодаря этому свойству алгоритм маршрутизации может выполнять маршрутизацию к любому пункту назначения в d переходах путем последовательного «сдвига» битов идентификатора пункта назначения, но только если размеры расстояния между модулем 1d и 3d равны.

Маршрутизация сообщения от узла m к узлу k выполняется путем взятия числа m и сдвига битов k по одному до тех пор, пока число не будет заменено на k. Каждый сдвиг соответствует переходу маршрутизации к следующему промежуточному адресу; переход действителен, потому что соседи каждого узла - это два возможных результата сдвига 0 или 1 на его собственный адрес. Из-за структуры графов де Брейна, когда последний бит k был сдвинут, запрос будет в узле k. Узел k отвечает, существует ли ключ k.

Пример маршрутизации

Пример того, как Koorde выполняет маршрутизацию от узла 2 к узлу 6 с использованием трехмерного двоичного графа.

Например, когда сообщение необходимо перенаправить от узла «2» (который равен «010») на «6» (который равен «110»), шаги следующие:

Шаг 1) Узел №2 направляет сообщение узлу №5 (используя его соединение с 2i + 1 mod8), сдвигает биты влево и помещает «1» в качестве самого младшего бита (правая сторона).

Шаг 2) Узел № 5 направляет сообщение к Узлу № 3 (используя его подключение к 2i + 1 mod8), сдвигает биты влево и помещает «1» в качестве самого младшего бита (правая сторона).

Шаг 3) Узел №3 направляет сообщение узлу №6 (используя его подключение к 2i mod8), сдвигает биты влево и помещает «0» в качестве самого младшего бита (правая сторона).

Непостоянная степень Корде

Алгоритм поиска Коорде.

D-мерность де Брюйна может быть обобщена на базу k, и в этом случае узел i соединен с узлами k * i + j по модулю kd, 0 ≤ j

Рекомендации

  • «Интернет-алгоритмы» Грега Плэкстона, осень 2003 г .: [1]
  • "Koorde: Простая оптимальная по степени распределенная хеш-таблица" М. Франса Каашука и Дэвида Р. Каргера: [2]
  • Описание Chord и Koorde: [3]