Полностью децентрализованные сети - Компьютерные сети

DHT (Distributed hash table) -- децентрализованная распределенная система для объединения большого количества постоянно исчезающих и появляющихся узлов и эффективной передачи сообщений между ними. Она использует 160-битные хэши для идентификации узлов, файлов и имен файлов (ключевых слов). Каждый узел содержит информацию о месторасположении файлов с хешами, близкими к его хешу.

Kad

Сеть Kad -- это реализация DHT. Узлы, файлы и имена файлов (ключевые слова) кодируются алгоритмом SHA-1 160-битными числами. Если узел хочет расшарить файл, он обрабатывает его, получая хэш, который идентифицирует этот файл в сети. Затем узел ищет несколько узлов, ID которых близки к хэшу файла и его имени (размеры хешей файлов и узлов совпадают, расстояние вычисляется применением операции XOR к хешам). На эти узлы отдается информация об адресе узла, на котором хранится файл.

Поиск в Kad

В соответствии с хешами узлы можно разместить в двоичном дереве.

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

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

Другие приложения P2P-сетей

    - мобильный P2P; - распределенные вычисления SETI@home; - совместное работа ( Groove ); - Skype.

Похожие статьи




Полностью децентрализованные сети - Компьютерные сети

Предыдущая | Следующая