Шнуры

В одноранговых сетях Koorde представляет собой систему распределенной хэш-таблицы (DHT), основанную на Chord DHT и графе Де Брейна ( последовательность Де Брейна ). Унаследовав простоту Chord, Koorde выполняет $O (log n)$ переходов на узел (где $n$ — количество узлов в DHT), и ⁠ $O\left({\frac {\log n}{\log(\log n)}}\right)$ ⁠ переходов на запрос поиска с $O (log n)$ соседями на узел.

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

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

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

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

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

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

Узел 2 направляет сообщение Узлу 5 (используя его соединение с $2 i + 1 mod 8$ ), сдвигает биты влево и помещает 1 как самый младший бит (правая сторона).
Узел 5 направляет сообщение Узлу 3 (используя его соединение с $2 i + 1 mod 8$ ), сдвигает биты влево и помещает 1 как самый младший бит (правая сторона).
Узел 3 направляет сообщение узлу 6 (используя его соединение с $2 i mod 8$ ), сдвигает биты влево и помещает 0 как самый младший бит (правая сторона).

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

-мерная диаграмма $d$ де Брёйна может быть обобщена до базы $k$ , и в этом случае узел $i$ соединяется с узлами $k • i + j mod kd$ , $0 \leq j < k$ . Диаметр ( уменьшается до $Θ log k n)$ . Узел Koorde $i$ поддерживает указатели на $k$ последовательных узлов, начиная с предшественника $k • i mod kd$ . Каждый шаг маршрутизации де Брейна можно эмулировать с ожидаемым постоянным количеством сообщений, поэтому в маршрутизации используется $O (log k n)$ ожидаемых переходов. Для $k = Θ(log n)$ мы получаем $Θ(log n)$ степень и ⁠ $\Theta \left({\frac {\log n}{\log(\log n)}}\right)$ ⁠ диаметр.

Алгоритм поиска

function n.lookup(k, shift, i)
{
    if k ∈ (n, s]
        return (s);
    else if i ∈ (n, s]
        return p.lookup(k, shift << 1, i ∘ topBit(shift));
    else
        return s.lookup(k, shift, i);
}

Псевдокод для алгоритма поиска Коорде в узле n:

k это ключ
I — воображаемый узел Де Брейна
p является ссылкой на предшественника 2n
s является ссылкой на преемника n

Ссылки

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