Технологии поиска данных в одноранговых сетях, построенных на основе распределенных хеш-таблиц
Проведен анализ архитектуры одноранговых сетей, построенных на основе распределенных хэш-таблиц, а также введены метрики для сравнения алгоритмов поиска с целью определения оптимального. Здійснено аналіз архітектури однорангових мереж, побудованих на основі розподілених хеш-таблиць, та введено метри...
Збережено в:
| Опубліковано в: : | Управляющие системы и машины |
|---|---|
| Дата: | 2016 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2016
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/113321 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Технологии поиска данных в одноранговых сетях, построенных на основе распределенных хеш-таблиц / А.В. Сергеев // Управляющие системы и машины. — 2016. — № 2. — С. 41-47. — Бібліогр.: 9 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859731720560967680 |
|---|---|
| author | Сергеев, А.В. |
| author_facet | Сергеев, А.В. |
| citation_txt | Технологии поиска данных в одноранговых сетях, построенных на основе распределенных хеш-таблиц / А.В. Сергеев // Управляющие системы и машины. — 2016. — № 2. — С. 41-47. — Бібліогр.: 9 назв. — рос. |
| collection | DSpace DC |
| container_title | Управляющие системы и машины |
| description | Проведен анализ архитектуры одноранговых сетей, построенных на основе распределенных хэш-таблиц, а также введены метрики для сравнения алгоритмов поиска с целью определения оптимального.
Здійснено аналіз архітектури однорангових мереж, побудованих на основі розподілених хеш-таблиць, та введено метрики для порівняння алгоритмів пошуку з метою визначення оптимального.
Introduction. The necessity of the large data sets processing, increasing the scalability and fault tolerance lead to the development of peer-to-peer networks, that require, unlike client-server architecture, the use of complex algorithms for data search. Thus, it is necessary to determine a peer-to-peer network with the optimal search algorithm according to the certain criteria. Purpose. The purpose of this paper is to analyze the constructed peer-to-peer networks based on distributed hash tables and to determine the optimal network according to some metrics. Methods. To determine the optimal system we have introduced the set of metrics, which correspond to the set of criteria’s which are critical to the systems comparison. The set of criteria’s is as follows: the number of steps in the search algorithm, the operation of calculating the «distance» between the elements of the network, and practical implementation of the system. Next, the criteria are ranked by importance and to each criterion there is a certain coefficient (weight) which is assigned so that the more important criterion strongly influences on the result than the less important. The linear convolution has been calculated for each system and the best system is the one which has the minimal result. Results. According to the result of calculations, the optimal search criteria is proved by Kademlia system, primarily due to the unique metric of distance between elements of the network. Conclusion. Analysis and comparison of peer-to-peer networks constructed on the basis of distributed hash tables, shows that, despite the fact that each of them is able to solve the problem of scalability and fault tolerance, the optimum system is Kademlia.
|
| first_indexed | 2025-12-01T13:54:43Z |
| format | Article |
| fulltext |
УСиМ, 2016, № 2 41
УДК 004.75
А.В. Сергеев
Технологии поиска данных в одноранговых сетях, построенных на основе
распределенных хеш-таблиц
Проведен анализ архитектуры одноранговых сетей, построенных на основе распределенных хэш-таблиц, а также введены мет-
рики для сравнения алгоритмов поиска с целью определения оптимального.
Ключевые слова: децентрализованные сети, одноранговые сети, распределенная хеш-таблица.
Здійснено аналіз архітектури однорангових мереж, побудованих на основі розподілених хеш-таблиць, та введено метрики для
порівняння алгоритмів пошуку з метою визначення оптимального.
Ключові слова: децентралізовані мережі, однорангові мережі, розподілена хеш-таблця.
Введение. Интенсивное увеличение объемов
интернет-трафика и количества пользователей
как в глобальных, так и в локальных сетях при-
вело к выявлению недостатков классической
клиент-серверной архитектуры, основной при-
чиной которых есть узкое место (bottleneck)
таких сетей – наличие единственного цен-
трального сервера. Это приводит к вопросам,
связанным со слабой масштабируемостью (спо-
собностью системы справляться с увеличением
нагрузки путем добавления новых элементов)
и отказоустойчивостью (способностью сохра-
нять работоспособность при отказе одного или
нескольких компонентов сети). Решением этих
проблем есть использование децентрализован-
ных сетей, функционирование которых не тре-
бует привязки к одному постоянному серверу.
Исходя из того, что каждый компьютер мо-
жет быть как сервером, так и клиентом, исполь-
зование такой модели приводит к тому, что лю-
бой новый элемент сети может быть присоеди-
нен без перестройки существующей архитекту-
ры. Отсутствие единого центрального элемента
значительно повышает надежность сети путем
того, что при отказе ее части сохраняется рабо-
тоспособность системы до тех пор, пока функ-
ционирует хотя бы один элемент.
Децентрализованные сети широко применя-
ются в файлообменных (mTorrent, Gnutella,
EDonkey), мультимедийных (SopCast, AceStre-
am), финансовых (Bitcoin, Litecoin) и других сер-
висах. Теоретические подходы построения де-
централизованных сетей и алгоритмы организа-
ции поиска в них рассматривались в работах
Alireza Naghizadeh (2014), Tahereh Yourdkhani
(2014), Ciprian Dobre (2011), Florin Pop (2011),
Moni Naor (2003), Udi Wieder (2003), Gennadiy
Porev (2010) и других.
Постановка проблемы
Основной практической задачей в децентра-
лизованных сетях есть поиск информации поль-
зователем. При этом необходимо обеспечивать
выполнение двух основных требований: реле-
вантности, т.е. меры соответствия результатов
поиска ожиданиям пользователя, и оптимизации
затрат ресурсов. Таким образом, появляется
проблема выбора алгоритма поиска, соответст-
вующего необходимым критериям эффективно-
сти. Учитывая их дифференциацию в зависимо-
сти от выполняемых задач, необходимо выде-
лить ряд характеристик для проведения срав-
нительного анализа. Цель этой статьи – иссле-
дование признаков эффективности децентра-
лизованных сетей и определение алгоритмов,
оптимальных для организации поиска по набо-
ру критериев.
Для выполнения поставленной задачи необ-
ходимо определить основные характеристики
децентрализованных сетей, влияющих на эф-
фективный поиск данных и организации обме-
на ими.
Применение распределенных хеш-таблиц
для построения одноранговых сетей
Для децентрализованных (одноранговых –
P2P) сетей характерно то, что каждый узел
равноправный по отношению к другим. В та-
кой сети любой элемент есть как клиентом, так
и сервером. К преимуществам такой системы
можно отнести:
42 УСиМ, 2016, № 2
масштабируемость – независимость от ко-
личества узлов в сети;
отказоустойчивость – сеть продолжит ра-
ботать при отказе отдельных узлов, что есть
прямым следствием отсутствия центрального
сервера.
Кроме приведенных примеров в одноранго-
вых системах, можно отнести одну из популяр-
ных систем мгновенной отправки сообщений
Skype версии 2012 года.
Для повышения эффективности Р2Р можно
использовать распределенные хэш-таблицы [1]
(Distributed Hash Table – DHT). Хеш-таблица –
это структура данных, которая реализует ин-
терфейс ассоциативного массива и позволяет
хранить пары ключ–значение и выполнять
следующие операции: добавление новой пары
к массиву, поиск элемента по ключу и удале-
ния элемента из массива. Преимущество такой
структуры данных то, что каждая операция
выполняется за время не более чем O(N), где
N-размер хеш-таблицы. Распределенная хеш-
таблица (DHT) представляет собой класс сис-
тем, реализующих сервис, и работает подобно
хеш-таблице. Таким образом, каждый узел в
сети может рационально искать значение, ас-
социированное с данным ключом. Обычно клю-
чом выступает некоторая хэш-функция, т.е.
функция, преобразующая массив произволь-
ной длины в битовую последовательность фик-
сированной длины по определенному алгорит-
му, зависящая от данных. Наиболее известная
реализация DHT – BitTorrent.
Каждый элемент сети имеет свой иденти-
фикатор в некотором бинарном ключевом про-
странстве, определяемый случайным образом.
Обычно его длина составляет 128 или 160 бит.
Хранение файлов в сети происходит сле-
дующим образом. Сначала каждому элементу
сети ставится в соответствие некоторый уни-
кальный бинарный идентификатор. Каждый
файл, который распределяется, также имеет
свой идентификатор, причем он есть значени-
ем хеш-функции от названия файла. Обычно,
для хеширования используется алгоритм SHA1,
который заключается в функции сжатия. На
вход этой функции подается блок текста дли-
ной в 512 байт, а также результат прошлого
шага алгоритма. На выходе получаются значе-
ния всех хеш-блоков до этого момента. Иско-
мой хеш-функцией есть исходное значение по-
следнего блока.
С учетом организации аппаратной структу-
ры Р2Р эффективность ее функционирования
определяется взаимным расположением эле-
ментов по определенной заранее некой метри-
кой близости. Таким образом, оптимизация ее
работы может быть достигнута путем приме-
нения различных алгоритмов поиска. На сего-
дня существует несколько систем с индивиду-
альными алгоритмами поиска, использование
которых обоснованно теоретически или прак-
тически, поэтому их характеристики будут со-
ставлять базу этого исследования.
Анализ характеристик одноранговых сис-
тем, созданных на основе DHT
●DistHash
Оверлейная сеть – иерархическая структура,
состоящая из трех уровней [1]. На первом нахо-
дятся так называемые агенты (agents), которые
связаны с RAgents (хранят не только локальные,
но и метаданные), на втором уровне и вместе со
своими агентами, в свою очередь, объединяются
в кластер на высшем уровне. RAgents – (супер-
агенты, супер-узлы) выбираются из множества
агентов случайным образом, осуществляя управ-
ление определенным их набором Модальность
сбора элементов в кластер определяется про-
странственным положением каждого элемента
и набором определенных метрик.
Топология сети базируется на предположе-
нии, что уже существует несколько кластеров,
из которых новый агент может получить ин-
формацию (сетевой адрес и порт подключения)
о списке существующих RAgents. После этого
элемент пытается найти ближайшего RAgent, к
которому он может подключиться. В этом слу-
чае таким RAgent будет тот, который выбран
не только по критериям сети и пространствен-
ному положению, но и с учетом количества
агентов в нескольких ближайших RAgents.
Агент подсоединяется к ближайшему RAgent, у
которого будет наименьшее количество уже
присоединенных агентов.
УСиМ, 2016, № 2 43
Необходимо оптимально распределить коли-
чество агентов и RAgents. При слишком боль-
шом количестве агентов, в сравнении с количе-
ством RAgents, каталог метаданных станет слиш-
ком большим и, соответственно, операции на
нем будут занимать больше времени. С другой
стороны, если количество агентов мало, то ко-
личество запросов к системе с целью доступа к
данным будет выше. Для решения этой пробле-
мы количество RAgents увеличивается и умень-
шается в соответствии с ростом или уменьшени-
ем количества агентов. Данное распределение
происходит на уровне кластера. Когда количест-
во агентов, присоединенных к RAgent, превыша-
ет некоторое лимит, новый RAgent выбирается
из списка агентов с помощью алгоритма голосо-
вания [3] и кластер разделяется на два. Остав-
шиеся агенты распределяются между двумя
RAgents (вместе с метаданными). В противном
случае (малое количество агентов) кластер унич-
тожается при слиянии его агентов с агентами
другого кластера.
Каждый агент обслуживает копии несколь-
ких объектов данных. Для согласования между
копиями данных, каждый объект имеет вла-
дельца – агента, который имеет право его из-
менять. Каталог метаданных имеет структуру
хеш-таблицы, т.е. представляет собой ассоциа-
тивную структуру, где каждому ключу ставит-
ся в соответствие какое-то значение (данные, в
нашем случае). Значение имеет структуру связ-
ного списка. Каждый объект имеет уникаль-
ный идентификатор, каждое значение имеет
ссылки на связный список идентификаторов
агентов, причем первый в списке идентифика-
тор принадлежит хозяину объекта. Внутри ко-
пии объекты также хранятся в виде хеш-
таблицы, где ключом есть идентификатор, а
значением объект. Чтобы найти соответству-
ющую информацию, запрос поступит сначала
в RAgent и только потом к агенту, у которого
находится необходимый объект.
Алгоритм поиска данных состоит из не-
скольких шагов. Сначала RAgent, с которым
соединен агент, что ищет данные (клиент), на-
правляет запрос с определенным критерием
поиска. После этого каждый RAgent предос-
тавляет ответ со списком объектов, удовлетво-
ряющих условиям поиска. На следующем эта-
пе изначальный RAgent соединяет полученные
списки со своим списком таким образом, что-
бы в конечном списке не было объектов с оди-
наковыми идентификаторами. После этого по-
лученный список отправляется к клиенту.
Сложность алгоритма определяется по фор-
муле:
),4( LogLPRMS
где R – количество RAgents, M – количество
ключей в каталоге метаданных, P – количество
объектов, подходящих под критерии поиска, L –
количество объектов, обслуживаемых агентом.
Chord
Каждый элемент системы хранит таблицу, в
которой находятся IP адреса элементов, нахо-
дящихся на «расстоянии» 2n, где n – натураль-
ное от его ID [4]. При попытке найти данные с
ключом k элемент направляет запрос к элемен-
ту со своей таблицы, у которого ID наиболь-
ший, но не превышает k. Построение таблицы
на основе степени двойки обеспечивает то, что
элемент может всегда направить запрос по
крайней мере половине от оставшихся ID, близ-
ких k, При этом количество запросов стремит-
ся к O(LogN), где N – количество элементов
сети.
Основной акцент в построении системы
ставится на надежность и корректность поис-
ка. Алгоритм обеспечивает корректный поиск,
используя список потомков: каждый элемент
сохраняет IP – адрес некоторого количества
последующих элементов сразу после того как
запрос попал в их ключевое пространство. Это
позволяет запросу инкрементально двигаться по
пространству ключей, даже если многие эле-
менты из таблицы уже исчезли или вышли из
строя. Единственным случаем, когда алгоритм
не может гарантированно найти потомка – это
тот, в котором все потомки исчезнут одновре-
менно, до того как элемент успеет обновить
свой список.
Добавление элемента в систему начинается
с запроса этого элемента к некоторому элемен-
ту сети с просьбой вычислить его ID. Это нуж-
но для того, чтобы новый элемент корректно
44 УСиМ, 2016, № 2
присоединился к системе и позволил роди-
тельским элементам обновить их списки по-
томков. Параллельно с этим, все элементы
системы обновляют свои таблицы на фоновом
уровне. Новый элемент должен узнать: будут
ли данные с ним ассоциированы, а связь по-
томков обеспечит то, что ключи могут быть
взяты у потомков нового элемента.
CAN
Для реализации DHT система использует
многомерную (d – количество измерений) де-
картову систему координат [5]. Пространство
разбивается на d – мерные прямоугольники,
называемые зонами. Каждый элемент системы
отвечает за определенную зону и, наоборот,
каждый участник однозначно определяется в
пределах своей зоны. Ключ привязан к точке
пространства и хранится у элемента, который
обслуживает зону, где находится эта точка.
Каждый элемент сохраняет таблицу маршру-
тизации с координатами всех соседей элемен-
та. Элементы считаются соседними, если их зо-
ны разделяют 1d мерную гиперплоскость.
Операция поиска реализована пересылкой за-
проса по пути, который представляет собой наи-
более близкую к прямой линии траекторию в
координатном пространстве, связывающей иска-
теля с элементом, хранящим искомый ключ. По-
сле получения запроса, элемент отправляет его
участнику, ближайшему к элементу, хранящему
ключ, и разрывает с ним связь. Каждый элемент
обслуживает O(d) состояний, сложность поиска
составляет
1
( ),dO dN что близко к
1
( ),dO N так
как обычно d << N [6].
Чтобы присоединиться к сети, новый эле-
мент сначала выбирает случайную точку P в
координатном пространстве и просит уже су-
ществующий элемент найти участника n, кото-
рый отвечает за зону, где находится эта точка.
Элемент n разбивает свою зону на две и пере-
кладывает ответственность за одну из полу-
ченных зон на нового участника. Новый эле-
мент может легко инициализировать свою таб-
лицу маршрутизации, так как все его соседи,
кроме самого элемента n, есть и соседями n.
После присоединения, элемент представляет
информацию о себе своим соседям, для того
чтобы они обновили свои таблицы. При выхо-
де элемента из сети его зона передается одно-
му из его соседей.
Pastry
Данная система подробно описана в работе
[7]. Каждый элемент сети n поддерживает не-
который набор из L (L-набор) элементов сис-
темы, который состоит из | |
2
L , близких к n, но
не превышающих его и | |
2
L близких, однако
меньших, чем n элементов. Корректность всей
системы зависит только от корректности дан-
ного набора.
Для оптимизации алгоритма поиска система
поддерживает таблицу маршрутизации указа-
телей к другим элементам, распределенным в
ключевом пространстве. Процесс поиска вы-
глядит следующим образом. Если искомый
ключ покрывается L-набором n, то запрос пе-
ресылается к нему. Как правило, это не выпол-
няется до тех пор, пока запрос не войдет в зону
ключевого пространства, достаточно близкую
к ключу. В этом случае запрос приходит к эле-
менту из таблицы маршрутизации, у которого
общий с ключом бинарный префикс длиннее,
чем у n. В случае когда такой элемента найти
не удается, запрос переходит к элементу, у ко-
торого общий префикс с ключом не короче,
чем у n, а ID арифметически ближе к ключу
[5]. Этот элемент точно находится в L-наборе
n, кроме случая, когда запрос уже дошел до
элемента, у которого ID арифметически бли-
жайший к ключу. Если таблица маршрутиза-
ции корректна, то сложность алгоритма поиска
будет рассчитываться, как NLog b2 , где N– ко-
личество участников в сети, b – алгоритмичес-
кий параметр, который обычно равен четырем.
При присоединении к сети новый элемент
должен создать свою таблицу маршрутизации, а
также уведомить других участников о своем су-
ществовании. Предполагается, что новому эле-
менту сначала известно о ближайшем элементе в
системе, согласно метрике, которая уже есть ее
частью. Такой элемент может быть определен
автоматически, например использованием IP-
УСиМ, 2016, № 2 45
мультикаст, или может быть получен админист-
ратором сети с помощью внешних каналов. Вы-
ход элементов из системы может происходить
без предупреждения. Для замены участника его
сосед в ключевом пространстве связывается с
элементом, у которого самый большой ID со
стороны исчезнувшего элемента, и запрашивает
его L-набор. Этот набор частично перекрывает
набор текущего элемента, но в нем также хра-
нятся участники, там не представленные. Среди
этих элементов выбирается один (предваритель-
но убедившись, что он еще в сети) и присоеди-
няется к L-набору. Таким образом, процедура
гарантирует, что каждый элемент может восста-
новить свой L-набор, кроме случая, когда одно-
временно исчезли из сети не менее
2
|| L эле-
ментов со смежными ID. Но благодаря разнооб-
разию (географической, ресурсной и т.д.) этих
элементов такая вероятность достаточно низкая,
даже для небольших значений L. Данная система
применяется в таких сервисах как Past и Scribe.
Kademlia
Алгоритм в данной системе [8] состоит в ис-
пользовании рекурсии, с помощью которой эле-
мент находит необходимое значение в сети за
приемлемое время и с задействованием рацио-
нального количества запросов к другим элемен-
там сети. Алгоритм базируется на расчете рас-
стояния между узлами в сети, который опреде-
ляется как результат операции XOR между уни-
кальными 160-битными идентификаторами эле-
ментов сети. Эффективность алгоритма заклю-
чается в том, что каждый элемент сети должен
обмениваться информацией только с )(LogNO
участников, где N – общее количество элементов
сети, т.е. при изменении их количества не нужно
будет перестраивать всю сеть.
Преимущества алгоритма – следствие исполь-
зования именно упомянутой метрики. XOR есть
симметричной операцией и позволяет участни-
кам сети получать запросы от элемента, который
находится у них в таблице маршрутизации. В
отличие от других алгоритмов, это позволяет
получать полезную маршрутную информацию
сразу от запросов. Более того, асимметрия при-
водит к усложнению изменения таблицы марш-
рутизации.
В алгоритме предполагается, что элементы
составляют листья бинарного дерева, в котором
позиция каждого элемента определяется как крат-
чайший уникальный префикс его идентификато-
ра. Для каждого элемента происходит разбиение
бинарного дерева на набор последовательных
низших поддеревьев, которые не включают в се-
бя данный элемент. Высшее поддерево состоит
из половины бинарного дерева, в котором нет
элемента. Следующее поддерево состоит из по-
ловины остатка дерева, не включая элемент и т.д.
Алгоритм поиска представлено следующей
процедурой. После нахождения хэш-функции от
файла, проводится операция их распределения
по следующему алгоритму: рассчитывается опе-
рация ХОR между идентификатором каждого
элемента сети и хэш-функцией каждого файла.
Соответствующий файл будет привязано к тому
элементу, для которого результат вышеупомяну-
той функции будет минимальным. Таким обра-
зом, алгоритм поиска файла в сети сводится к
нахождению элемента, к которому он привязан.
Поиск файла произвольным элементом сети
представляет собой рекурсивную процедуру, ко-
торая базируется на расчете вышеупомянутой
метрики, между ключом файла (который извес-
тен) и идентификаторами соседних к элементу
участников. Поиск продолжается до тех пор, по-
ка либо информация не будет найдена, либо не
закончатся участники сети. Сложность алгорит-
ма является логарифмической, т.е. увеличение
количества элементов сети вдвое приводит к
увеличению шагов алгоритма на один.
Эффективность этого алгоритма проверено
эмпирически через использование в таких сис-
темах как eMule, I2P, RevConnect и др.
Определение оптимального алгоритма
поиска
Для определения оптимального алгоритма
поиска необходимо провести сравнительный
анализ по ряду критериев, т.е. решить много-
критериальную задачу. Она может быть фор-
мализована следующим образом:
1( ,..., ) minnZ f x x ,
где x1, , xn – характеристики алгоритма.
46 УСиМ, 2016, № 2
Очевидно, что совокупность критериев не
может быть полной, но можно выделить груп-
пу критических признаков. Прежде всего, это
количество шагов алгоритма, т.е. количество
запросов, необходимых для нахождения нуж-
ной информации; расстояние между элемента-
ми, т.е. некоторая численная метрика, опреде-
ляющая относительное расположение узлов в
сети; практическая реализация системы. Исхо-
дя из этих метрик и будем оценивать эффек-
тивность алгоритмов.
Для сравнения сложности различных алго-
ритмов, обоснуем отношение предпочтения.
Так, очевидно, что логарифмическая функция
O(LogN) описывает меньшее количество ша-
гов, чем полиномиальная
1
( )dO N . Функция
)4( LogLPRM зависит от количества объек-
тов данных (L) так, если RM относительно ма-
ло, то сложность алгоритма описывается лога-
рифмической зависимостью. В противном слу-
чае следует учитывать все компоненты. Таким
образом, эта функция может описывать широ-
кий диапазон сложности. Примем, что
)()4( LogNOLogLPRM .
Т а б л и ц а 1. Сравнительная характеристика алгоритмов по
основным критериям
Количество ша-
гов алгоритма
Операция нахожде-
ния расстояния
между элементами
Практическая
реализация
DistHash (4 )RM P LogL Арифметическая
разность –
Chord ( )O LogN Арифметическая
разность –
CAN
1
d( )O N
Арифметическая
разность –
Pastry ( )O LogN
Длина одинаковой
последовательности
префиксных битов
+
Kademlia ( )O LogN XOR +
Таким образом, отношение предпочтения
выглядит следующим образом:
1
(4 ) ( ) ( )dRM P LogL O N O LogN .
Для введения количественных оценок про-
ранжируем значения критериев для алгорит-
мов, исходя из того, что:
1. x1 min, где x1 – количество шагов ал-
горитма, т.е. чем меньше шагов будет задейство-
вано, тем быстрее будет найдена информация.
2. x2 2x – операция нахождения расстояния
между элементами. Этот критерий субъективен,
так как только в алгоритме Kademlia процедура
симметрична, что дает некоторую информацию
о расстоянии. Поэтому предположим, что вид
отношение предпочтения:
2( ) 2( )DistHash Chordx x 2( ) 2( ) 2( )CAN Pastry Kademliax x x .
3. x3 – практическая реализация алгоритма,
результат представлен булевым значением: 1 –
в случае существующий реализации и 2 – в
случае отсутствующей.
Так как функция Z min, то чем меньше
значение метрики параметра, тем лучше. Нужно
принимать во внимание тот факт, что критерии
не равнозначны и поэтому необходимо проран-
жировать параметры по важности (метод про-
стого ранжирования [9]). Эти значения будут ко-
эффициентами (весами) при оценке критериев.
Т а б л и ц а 2. Ранжирование критериев по важности
x1 x2 x3
3 2 1
Дадим оценку каждого критерия для каждой
системы:
Т а б л и ц а 3. Сравнение алгоритмов по каждому из критериев
x1 x2 x3
DistHash 3 2 2
Chord 1 2 2
CAN 2 2 2
Pastry 1 2 1
Kademlia 1 1 1
Теперь можно оценить эффективность каж-
дого алгоритма по формуле:
3
1i
ii kxZ ,
где xi – определенный критерий, а ki – соответ-
ствующий показатель веса.
После расчета функции для каждой системы
получаем: ZDistHash = 15; ZChord = 9; ZCAN = 12;
ZPastry = 8; ZKademlia = 6;. Таким образом, функция
Z достигает минимума для алгоритма Kademlia,
который и есть оптимальным при сравнении по
этим критериям.
Заключение. Рассмотрено понятие децентра-
лизованных сетей, выделены преимущества та-
ких сетей перед клиент-серверной архитектурой.
Сделан обзор и проведено сравнение систем и
УСиМ, 2016, № 2 47
алгоритмов поиска данных в этих системах, соз-
данных на основе распределенных хеш-таблиц.
Описан ряд систем, построенных на основе
распределенных хеш-таблиц, для которых раз-
работаны алгоритмы поиска данных. Следует
отметить, что все рассмотренные алгоритмы
достаточно эффективны, но при этом Chord,
Pastry и Kademlia имеют минимальную лога-
рифмическую сложность. Преимуществом Kade-
mlia есть симметричная метрика XOR для на-
хождения расстояния между узлами сети, ко-
торая значительно упрощает построение табли-
цы маршрутизации и способна предоставлять
некоторую информацию, что выгодно отлича-
ет данную метрику от метрик, применяемых в
других системах.
Таким образом, несмотря на то что для ре-
шения большинства существующих проблем
клиент-серверной архитектуры можно исполь-
зовать любую из систем, проанализированных
в статье, сравнение по нескольким критериям
указывает на то, что оптимальной системой
является Kademlia.
1. Порєв Г.В. Методи та засоби побудови iнформацiй-
них технологiй на основi територiально розосеред-
жених сервiс-орiєнтованих однорангових мереж:
Дис. д-ра техн. наук. – К., 2013. – 397 с.
2. Florin Pop, Valentin Cristea. DistHash: A robust P2P
DHT-based system for replicated objects Ciprian Dob-
re. – Bucharest, Romania, May 26–29, 2009. – 1. –
P. 453-460.
3. Hardekopf B., Kwiat K., Upadhyaya S. A Decentralized
Voting Algorithm for Increasing Dependability in Dis-
tributed Systems. – 5th World MultiConference on
Systemic // Cybernetics and Informatics (SCI2001),
2001. – Р. 3–5.
4. Chord: A scalable peer-to-peer lookup protocol for
internet applications / I. Stoica, R. Morris, D. Karger et
al. // IEEE/ACM Transactions on Networking. – 2003. –
11, N 1. – P. 17–32.
5. A scalable content-addressable network / S. Ratnasamy,
P. Francis, M. Handley et al. // Proc. of ACM SIGCOMM.
– San Diego, CA (Aug. 2001). Р. 162–168.
6. Looking up data in p2p systems / H. Balakrishnan,
M. Kaashoek, D. Karger et al. // Comm. ACM 46,2
(Feb. 2003).
7. Rowstron A., Druschel P. Pastry: Scalable, distributed
object location and routing for large-scale peer-to-peer
systems // Proc. of the 18th IFIP/ACM Int’l Conf. on
Distributed Systems Platforms (Nov. 2001). – P. 3–13.
8. Maymounkov P., Mazieres D. Kademlia: A Peer-to-
Peer Information System Based on the XOR Metric //
IPTPS 2002, 7-8 March 2002. – P. 2–9.
9. Гнатієнко Г.М., Снитюк В.Є. Експертні технології
прийняття рішень. – К.: Маклаут, 2008. – 444 с.
Поступила 14.12.2015
E-mail: a.serhieiev@gmail.com
© А.В. Сергеев, 2016
UDC 004.75
A.V. Serhieiev
The Technologies of the Data Retrieval in Peer-to-Peer Networks Constructed on the Basis of the
Distributed Hash Tables
Keywords: decentralized networks, ad hoc networks, distributed hash table.
Introduction. The necessity of the large data sets processing, increasing the scalability and fault tolerance lead to the develop-
ment of peer-to-peer networks, that require, unlike client-server architecture, the use of complex algorithms for data search. Thus, it
is necessary to determine a peer-to-peer network with the optimal search algorithm according to the certain criteria.
Purpose. The purpose of this paper is to analyze the constructed peer-to-peer networks based on distributed hash tables
and to determine the optimal network according to some metrics.
Methods. To determine the optimal system we have introduced the set of metrics, which correspond to the set of criteria’s
which are critical to the systems comparison. The set of criteria’s is as follows: the number of steps in the search algorithm, the op-
eration of calculating the «distance» between the elements of the network, and practical implementation of the system. Next, the
criteria are ranked by importance and to each criterion there is a certain coefficient (weight) which is assigned so that the more im-
portant criterion strongly influences on the result than the less important. The linear convolution has been calculated for each system
and the best system is the one which has the minimal result.
Results. According to the result of calculations, the optimal search criteria is proved by Kademlia system, primarily due
to the unique metric of distance between elements of the network.
Conclusion. Analysis and comparison of peer-to-peer networks constructed on the basis of distributed hash tables, shows that,
despite the fact that each of them is able to solve the problem of scalability and fault tolerance, the optimum system is Kademlia.
<<
/ASCII85EncodePages false
/AllowTransparency false
/AutoPositionEPSFiles true
/AutoRotatePages /None
/Binding /Left
/CalGrayProfile (Dot Gain 20%)
/CalRGBProfile (sRGB IEC61966-2.1)
/CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2)
/sRGBProfile (sRGB IEC61966-2.1)
/CannotEmbedFontPolicy /Error
/CompatibilityLevel 1.4
/CompressObjects /Tags
/CompressPages true
/ConvertImagesToIndexed true
/PassThroughJPEGImages true
/CreateJobTicket false
/DefaultRenderingIntent /Default
/DetectBlends true
/DetectCurves 0.0000
/ColorConversionStrategy /CMYK
/DoThumbnails false
/EmbedAllFonts true
/EmbedOpenType false
/ParseICCProfilesInComments true
/EmbedJobOptions true
/DSCReportingLevel 0
/EmitDSCWarnings false
/EndPage -1
/ImageMemory 1048576
/LockDistillerParams false
/MaxSubsetPct 100
/Optimize true
/OPM 1
/ParseDSCComments true
/ParseDSCCommentsForDocInfo true
/PreserveCopyPage true
/PreserveDICMYKValues true
/PreserveEPSInfo true
/PreserveFlatness true
/PreserveHalftoneInfo false
/PreserveOPIComments true
/PreserveOverprintSettings true
/StartPage 1
/SubsetFonts true
/TransferFunctionInfo /Apply
/UCRandBGInfo /Preserve
/UsePrologue false
/ColorSettingsFile ()
/AlwaysEmbed [ true
]
/NeverEmbed [ true
]
/AntiAliasColorImages false
/CropColorImages true
/ColorImageMinResolution 300
/ColorImageMinResolutionPolicy /OK
/DownsampleColorImages true
/ColorImageDownsampleType /Bicubic
/ColorImageResolution 300
/ColorImageDepth -1
/ColorImageMinDownsampleDepth 1
/ColorImageDownsampleThreshold 1.50000
/EncodeColorImages true
/ColorImageFilter /DCTEncode
/AutoFilterColorImages true
/ColorImageAutoFilterStrategy /JPEG
/ColorACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/ColorImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000ColorACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000ColorImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasGrayImages false
/CropGrayImages true
/GrayImageMinResolution 300
/GrayImageMinResolutionPolicy /OK
/DownsampleGrayImages true
/GrayImageDownsampleType /Bicubic
/GrayImageResolution 300
/GrayImageDepth -1
/GrayImageMinDownsampleDepth 2
/GrayImageDownsampleThreshold 1.50000
/EncodeGrayImages true
/GrayImageFilter /DCTEncode
/AutoFilterGrayImages true
/GrayImageAutoFilterStrategy /JPEG
/GrayACSImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/GrayImageDict <<
/QFactor 0.15
/HSamples [1 1 1 1] /VSamples [1 1 1 1]
>>
/JPEG2000GrayACSImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/JPEG2000GrayImageDict <<
/TileWidth 256
/TileHeight 256
/Quality 30
>>
/AntiAliasMonoImages false
/CropMonoImages true
/MonoImageMinResolution 1200
/MonoImageMinResolutionPolicy /OK
/DownsampleMonoImages true
/MonoImageDownsampleType /Bicubic
/MonoImageResolution 1200
/MonoImageDepth -1
/MonoImageDownsampleThreshold 1.50000
/EncodeMonoImages true
/MonoImageFilter /CCITTFaxEncode
/MonoImageDict <<
/K -1
>>
/AllowPSXObjects false
/CheckCompliance [
/None
]
/PDFX1aCheck false
/PDFX3Check false
/PDFXCompliantPDFOnly false
/PDFXNoTrimBoxError true
/PDFXTrimBoxToMediaBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXSetBleedBoxToMediaBox true
/PDFXBleedBoxToTrimBoxOffset [
0.00000
0.00000
0.00000
0.00000
]
/PDFXOutputIntentProfile ()
/PDFXOutputConditionIdentifier ()
/PDFXOutputCondition ()
/PDFXRegistryName ()
/PDFXTrapped /False
/CreateJDFFile false
/Description <<
/ARA <FEFF06270633062A062E062F0645002006470630064700200627064406250639062F0627062F0627062A002006440625064606340627062100200648062B062706260642002000410064006F00620065002000500044004600200645062A064806270641064206290020064406440637062806270639062900200641064A00200627064406450637062706280639002006300627062A0020062F0631062C0627062A002006270644062C0648062F0629002006270644063906270644064A0629061B0020064A06450643064600200641062A062D00200648062B0627062606420020005000440046002006270644064506460634062306290020062806270633062A062E062F062706450020004100630072006F0062006100740020064800410064006F006200650020005200650061006400650072002006250635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E0635062F0627063100200035002E0030002006480627064406250635062F062706310627062A0020062706440623062D062F062B002E>
/BGR <FEFF04180437043f043e043b043704320430043904420435002004420435043704380020043d0430044104420440043e0439043a0438002c00200437043000200434043000200441044a0437043404300432043004420435002000410064006f00620065002000500044004600200434043e043a0443043c0435043d04420438002c0020043c0430043a04410438043c0430043b043d043e0020043f044004380433043e04340435043d04380020043704300020043204380441043e043a043e043a0430044704350441044204320435043d0020043f04350447043004420020043704300020043f044004350434043f0435044704300442043d04300020043f043e04340433043e0442043e0432043a0430002e002000200421044a04370434043004340435043d043804420435002000500044004600200434043e043a0443043c0435043d044204380020043c043e0433043004420020043404300020044104350020043e0442043204300440044f0442002004410020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200441043b0435043404320430044904380020043204350440044104380438002e>
/CHS <FEFF4f7f75288fd94e9b8bbe5b9a521b5efa7684002000410064006f006200650020005000440046002065876863900275284e8e9ad88d2891cf76845370524d53705237300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c676562535f00521b5efa768400200050004400460020658768633002>
/CHT <FEFF4f7f752890194e9b8a2d7f6e5efa7acb7684002000410064006f006200650020005000440046002065874ef69069752865bc9ad854c18cea76845370524d5370523786557406300260a853ef4ee54f7f75280020004100630072006f0062006100740020548c002000410064006f00620065002000520065006100640065007200200035002e003000204ee553ca66f49ad87248672c4f86958b555f5df25efa7acb76840020005000440046002065874ef63002>
/CZE <FEFF005400610074006f0020006e006100730074006100760065006e00ed00200070006f0075017e0069006a007400650020006b0020007600790074007600e101590065006e00ed00200064006f006b0075006d0065006e0074016f002000410064006f006200650020005000440046002c0020006b00740065007200e90020007300650020006e0065006a006c00e90070006500200068006f006400ed002000700072006f0020006b00760061006c00690074006e00ed0020007400690073006b00200061002000700072006500700072006500730073002e002000200056007900740076006f01590065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f007400650076015900ed007400200076002000700072006f006700720061006d0065006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076011b006a016100ed00630068002e>
/DAN <FEFF004200720075006700200069006e0064007300740069006c006c0069006e006700650072006e0065002000740069006c0020006100740020006f007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400650072002c0020006400650072002000620065006400730074002000650067006e006500720020007300690067002000740069006c002000700072006500700072006500730073002d007500640073006b007200690076006e0069006e00670020006100660020006800f8006a0020006b00760061006c0069007400650074002e0020004400650020006f007000720065007400740065006400650020005000440046002d0064006f006b0075006d0065006e0074006500720020006b0061006e002000e50062006e00650073002000690020004100630072006f00620061007400200065006c006c006500720020004100630072006f006200610074002000520065006100640065007200200035002e00300020006f00670020006e0079006500720065002e>
/DEU <FEFF00560065007200770065006e00640065006e0020005300690065002000640069006500730065002000450069006e007300740065006c006c0075006e00670065006e0020007a0075006d002000450072007300740065006c006c0065006e00200076006f006e002000410064006f006200650020005000440046002d0044006f006b0075006d0065006e00740065006e002c00200076006f006e002000640065006e0065006e002000530069006500200068006f006300680077006500720074006900670065002000500072006500700072006500730073002d0044007200750063006b0065002000650072007a0065007500670065006e0020006d00f60063006800740065006e002e002000450072007300740065006c006c007400650020005000440046002d0044006f006b0075006d0065006e007400650020006b00f6006e006e0065006e0020006d006900740020004100630072006f00620061007400200075006e0064002000410064006f00620065002000520065006100640065007200200035002e00300020006f0064006500720020006800f600680065007200200067006500f600660066006e00650074002000770065007200640065006e002e>
/ESP <FEFF005500740069006c0069006300650020006500730074006100200063006f006e0066006900670075007200610063006900f3006e0020007000610072006100200063007200650061007200200064006f00630075006d0065006e0074006f00730020005000440046002000640065002000410064006f0062006500200061006400650063007500610064006f00730020007000610072006100200069006d0070007200650073006900f3006e0020007000720065002d0065006400690074006f007200690061006c00200064006500200061006c00740061002000630061006c0069006400610064002e002000530065002000700075006500640065006e00200061006200720069007200200064006f00630075006d0065006e0074006f00730020005000440046002000630072006500610064006f007300200063006f006e0020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e003000200079002000760065007200730069006f006e0065007300200070006f00730074006500720069006f007200650073002e>
/ETI <FEFF004b00610073007500740061006700650020006e0065006900640020007300e4007400740065006900640020006b00760061006c006900740065006500740073006500200074007200fc006b006900650065006c007300650020007000720069006e00740069006d0069007300650020006a0061006f006b007300200073006f00620069006c0069006b0065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740069006400650020006c006f006f006d006900730065006b0073002e00200020004c006f006f0064007500640020005000440046002d0064006f006b0075006d0065006e00740065002000730061006100740065002000610076006100640061002000700072006f006700720061006d006d006900640065006700610020004100630072006f0062006100740020006e0069006e0067002000410064006f00620065002000520065006100640065007200200035002e00300020006a00610020007500750065006d006100740065002000760065007200730069006f006f006e00690064006500670061002e000d000a>
/FRA <FEFF005500740069006c006900730065007a00200063006500730020006f007000740069006f006e00730020006100660069006e00200064006500200063007200e900650072002000640065007300200064006f00630075006d0065006e00740073002000410064006f00620065002000500044004600200070006f0075007200200075006e00650020007100750061006c0069007400e90020006400270069006d007000720065007300730069006f006e00200070007200e9007000720065007300730065002e0020004c0065007300200064006f00630075006d0065006e00740073002000500044004600200063007200e900e90073002000700065007500760065006e0074002000ea0074007200650020006f007500760065007200740073002000640061006e00730020004100630072006f006200610074002c002000610069006e00730069002000710075002700410064006f00620065002000520065006100640065007200200035002e0030002000650074002000760065007200730069006f006e007300200075006c007400e90072006900650075007200650073002e>
/GRE <FEFF03a703c103b703c303b903bc03bf03c003bf03b903ae03c303c403b5002003b103c503c403ad03c2002003c403b903c2002003c103c503b803bc03af03c303b503b903c2002003b303b903b1002003bd03b1002003b403b703bc03b903bf03c503c103b303ae03c303b503c403b5002003ad03b303b303c103b103c603b1002000410064006f006200650020005000440046002003c003bf03c5002003b503af03bd03b103b9002003ba03b103c42019002003b503be03bf03c703ae03bd002003ba03b103c403ac03bb03bb03b703bb03b1002003b303b903b1002003c003c103bf002d03b503ba03c403c503c003c903c403b903ba03ad03c2002003b503c103b303b103c303af03b503c2002003c503c803b703bb03ae03c2002003c003bf03b903cc03c403b703c403b103c2002e0020002003a403b10020005000440046002003ad03b303b303c103b103c603b1002003c003bf03c5002003ad03c703b503c403b5002003b403b703bc03b903bf03c503c103b303ae03c303b503b9002003bc03c003bf03c103bf03cd03bd002003bd03b1002003b103bd03bf03b903c703c403bf03cd03bd002003bc03b5002003c403bf0020004100630072006f006200610074002c002003c403bf002000410064006f00620065002000520065006100640065007200200035002e0030002003ba03b103b9002003bc03b503c403b103b303b503bd03ad03c303c403b503c103b503c2002003b503ba03b403cc03c303b503b903c2002e>
/HEB <FEFF05D405E905EA05DE05E905D5002005D105D405D205D305E805D505EA002005D005DC05D4002005DB05D305D9002005DC05D905E605D505E8002005DE05E105DE05DB05D9002000410064006F006200650020005000440046002005D405DE05D505EA05D005DE05D905DD002005DC05D405D305E405E105EA002005E705D305DD002D05D305E405D505E1002005D005D905DB05D505EA05D905EA002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E05D005DE05D905DD002005DC002D005000440046002F0058002D0033002C002005E205D905D905E005D5002005D105DE05D305E805D905DA002005DC05DE05E905EA05DE05E9002005E905DC0020004100630072006F006200610074002E002005DE05E105DE05DB05D90020005000440046002005E905E005D505E605E805D5002005E005D905EA05E005D905DD002005DC05E405EA05D905D705D4002005D105D005DE05E605E205D505EA0020004100630072006F006200610074002005D5002D00410064006F00620065002000520065006100640065007200200035002E0030002005D505D205E805E105D005D505EA002005DE05EA05E705D305DE05D505EA002005D905D505EA05E8002E>
/HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.)
/HUN <FEFF004b0069007600e1006c00f30020006d0069006e0151007300e9006701710020006e0079006f006d00640061006900200065006c0151006b00e90073007a00ed007401510020006e0079006f006d00740061007400e100730068006f007a0020006c006500670069006e006b00e1006200620020006d0065006700660065006c0065006c0151002000410064006f00620065002000500044004600200064006f006b0075006d0065006e00740075006d006f006b0061007400200065007a0065006b006b0065006c0020006100200062006500e1006c006c00ed007400e10073006f006b006b0061006c0020006b00e90073007a00ed0074006800650074002e0020002000410020006c00e90074007200650068006f007a006f00740074002000500044004600200064006f006b0075006d0065006e00740075006d006f006b00200061007a0020004100630072006f006200610074002000e9007300200061007a002000410064006f00620065002000520065006100640065007200200035002e0030002c0020007600610067007900200061007a002000610074007400f3006c0020006b00e9007301510062006200690020007600650072007a006900f3006b006b0061006c0020006e00790069007400680061007400f3006b0020006d00650067002e>
/ITA <FEFF005500740069006c0069007a007a006100720065002000710075006500730074006500200069006d0070006f007300740061007a0069006f006e00690020007000650072002000630072006500610072006500200064006f00630075006d0065006e00740069002000410064006f00620065002000500044004600200070006900f900200061006400610074007400690020006100200075006e00610020007000720065007300740061006d0070006100200064006900200061006c007400610020007100750061006c0069007400e0002e0020004900200064006f00630075006d0065006e007400690020005000440046002000630072006500610074006900200070006f00730073006f006e006f0020006500730073006500720065002000610070006500720074006900200063006f006e0020004100630072006f00620061007400200065002000410064006f00620065002000520065006100640065007200200035002e003000200065002000760065007200730069006f006e006900200073007500630063006500730073006900760065002e>
/JPN <FEFF9ad854c18cea306a30d730ea30d730ec30b951fa529b7528002000410064006f0062006500200050004400460020658766f8306e4f5c6210306b4f7f75283057307e305930023053306e8a2d5b9a30674f5c62103055308c305f0020005000440046002030d530a130a430eb306f3001004100630072006f0062006100740020304a30883073002000410064006f00620065002000520065006100640065007200200035002e003000204ee5964d3067958b304f30533068304c3067304d307e305930023053306e8a2d5b9a306b306f30d530a930f330c8306e57cb30818fbc307f304c5fc59808306730593002>
/KOR <FEFFc7740020c124c815c7440020c0acc6a9d558c5ec0020ace0d488c9c80020c2dcd5d80020c778c1c4c5d00020ac00c7a50020c801d569d55c002000410064006f0062006500200050004400460020bb38c11cb97c0020c791c131d569b2c8b2e4002e0020c774b807ac8c0020c791c131b41c00200050004400460020bb38c11cb2940020004100630072006f0062006100740020bc0f002000410064006f00620065002000520065006100640065007200200035002e00300020c774c0c1c5d0c11c0020c5f40020c2180020c788c2b5b2c8b2e4002e>
/LTH <FEFF004e006100750064006f006b0069007400650020016100690075006f007300200070006100720061006d006500740072007500730020006e006f0072011700640061006d00690020006b0075007200740069002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b00750072006900650020006c0061006200690061007500730069006100690020007000720069007400610069006b007900740069002000610075006b01610074006f00730020006b006f006b007900620117007300200070006100720065006e006700740069006e00690061006d00200073007000610075007300640069006e0069006d00750069002e0020002000530075006b0075007200740069002000500044004600200064006f006b0075006d0065006e007400610069002000670061006c006900200062016b007400690020006100740069006400610072006f006d00690020004100630072006f006200610074002000690072002000410064006f00620065002000520065006100640065007200200035002e0030002000610072002000760117006c00650073006e0117006d00690073002000760065007200730069006a006f006d00690073002e>
/LVI <FEFF0049007a006d0061006e0074006f006a00690065007400200161006f00730020006900650073007400610074012b006a0075006d00750073002c0020006c0061006900200076006500690064006f00740075002000410064006f00620065002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006100730020006900720020012b00700061016100690020007000690065006d01130072006f00740069002000610075006700730074006100730020006b00760061006c0069007401010074006500730020007000690072006d007300690065007300700069006501610061006e006100730020006400720075006b00610069002e00200049007a0076006500690064006f006a006900650074002000500044004600200064006f006b0075006d0065006e007400750073002c0020006b006f002000760061007200200061007400760113007200740020006100720020004100630072006f00620061007400200075006e002000410064006f00620065002000520065006100640065007200200035002e0030002c0020006b0101002000610072012b00200074006f0020006a00610075006e0101006b0101006d002000760065007200730069006a0101006d002e>
/NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.)
/NOR <FEFF004200720075006b00200064006900730073006500200069006e006e007300740069006c006c0069006e00670065006e0065002000740069006c002000e50020006f0070007000720065007400740065002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e00740065007200200073006f006d00200065007200200062006500730074002000650067006e0065007400200066006f00720020006600f80072007400720079006b006b0073007500740073006b00720069006600740020006100760020006800f800790020006b00760061006c0069007400650074002e0020005000440046002d0064006f006b0075006d0065006e00740065006e00650020006b0061006e002000e50070006e00650073002000690020004100630072006f00620061007400200065006c006c00650072002000410064006f00620065002000520065006100640065007200200035002e003000200065006c006c00650072002000730065006e006500720065002e>
/POL <FEFF0055007300740061007700690065006e0069006100200064006f002000740077006f0072007a0065006e0069006100200064006f006b0075006d0065006e007400f300770020005000440046002000700072007a0065007a006e00610063007a006f006e00790063006800200064006f002000770079006400720075006b00f30077002000770020007700790073006f006b00690065006a0020006a0061006b006f015b00630069002e002000200044006f006b0075006d0065006e0074007900200050004400460020006d006f017c006e00610020006f007400770069006500720061010700200077002000700072006f006700720061006d006900650020004100630072006f00620061007400200069002000410064006f00620065002000520065006100640065007200200035002e0030002000690020006e006f00770073007a0079006d002e>
/PTB <FEFF005500740069006c0069007a006500200065007300730061007300200063006f006e00660069006700750072006100e700f50065007300200064006500200066006f0072006d00610020006100200063007200690061007200200064006f00630075006d0065006e0074006f0073002000410064006f0062006500200050004400460020006d00610069007300200061006400650071007500610064006f00730020007000610072006100200070007200e9002d0069006d0070007200650073007300f50065007300200064006500200061006c007400610020007100750061006c00690064006100640065002e0020004f007300200064006f00630075006d0065006e0074006f00730020005000440046002000630072006900610064006f007300200070006f00640065006d0020007300650072002000610062006500720074006f007300200063006f006d0020006f0020004100630072006f006200610074002000650020006f002000410064006f00620065002000520065006100640065007200200035002e0030002000650020007600650072007300f50065007300200070006f00730074006500720069006f007200650073002e>
/RUM <FEFF005500740069006c0069007a00610163006900200061006300650073007400650020007300650074010300720069002000700065006e007400720075002000610020006300720065006100200064006f00630075006d0065006e00740065002000410064006f006200650020005000440046002000610064006500630076006100740065002000700065006e0074007200750020007400690070010300720069007200650061002000700072006500700072006500730073002000640065002000630061006c006900740061007400650020007300750070006500720069006f006100720103002e002000200044006f00630075006d0065006e00740065006c00650020005000440046002000630072006500610074006500200070006f00740020006600690020006400650073006300680069007300650020006300750020004100630072006f006200610074002c002000410064006f00620065002000520065006100640065007200200035002e00300020015f00690020007600650072007300690075006e0069006c006500200075006c0074006500720069006f006100720065002e>
/RUS <FEFF04180441043f043e043b044c04370443043904420435002004340430043d043d044b04350020043d0430044104420440043e0439043a043800200434043b044f00200441043e043704340430043d0438044f00200434043e043a0443043c0435043d0442043e0432002000410064006f006200650020005000440046002c0020043c0430043a04410438043c0430043b044c043d043e0020043f043e04340445043e0434044f04490438044500200434043b044f00200432044b0441043e043a043e043a0430044704350441044204320435043d043d043e0433043e00200434043e043f0435044704300442043d043e0433043e00200432044b0432043e04340430002e002000200421043e043704340430043d043d044b04350020005000440046002d0434043e043a0443043c0435043d0442044b0020043c043e0436043d043e0020043e0442043a0440044b043204300442044c002004410020043f043e043c043e0449044c044e0020004100630072006f00620061007400200438002000410064006f00620065002000520065006100640065007200200035002e00300020043800200431043e043b043504350020043f043e04370434043d043804450020043204350440044104380439002e>
/SKY <FEFF0054006900650074006f0020006e006100730074006100760065006e0069006100200070006f0075017e0069007400650020006e00610020007600790074007600e100720061006e0069006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b0074006f007200e90020007300610020006e0061006a006c0065007001610069006500200068006f0064006900610020006e00610020006b00760061006c00690074006e00fa00200074006c0061010d00200061002000700072006500700072006500730073002e00200056007900740076006f00720065006e00e900200064006f006b0075006d0065006e007400790020005000440046002000620075006400650020006d006f017e006e00e90020006f00740076006f00720069016500200076002000700072006f006700720061006d006f006300680020004100630072006f00620061007400200061002000410064006f00620065002000520065006100640065007200200035002e0030002000610020006e006f0076016100ed00630068002e>
/SLV <FEFF005400650020006e006100730074006100760069007400760065002000750070006f0072006100620069007400650020007a00610020007500730074007600610072006a0061006e006a006500200064006f006b0075006d0065006e0074006f0076002000410064006f006200650020005000440046002c0020006b006900200073006f0020006e0061006a007000720069006d00650072006e0065006a016100690020007a00610020006b0061006b006f0076006f00730074006e006f0020007400690073006b0061006e006a00650020007300200070007200690070007200610076006f0020006e00610020007400690073006b002e00200020005500730074007600610072006a0065006e006500200064006f006b0075006d0065006e0074006500200050004400460020006a00650020006d006f0067006f010d00650020006f0064007000720065007400690020007a0020004100630072006f00620061007400200069006e002000410064006f00620065002000520065006100640065007200200035002e003000200069006e0020006e006f00760065006a01610069006d002e>
/SUO <FEFF004b00e40079007400e40020006e00e40069007400e4002000610073006500740075006b007300690061002c0020006b0075006e0020006c0075006f00740020006c00e400680069006e006e00e4002000760061006100740069007600610061006e0020007000610069006e006100740075006b00730065006e002000760061006c006d0069007300740065006c00750074007900f6006800f6006e00200073006f00700069007600690061002000410064006f0062006500200050004400460020002d0064006f006b0075006d0065006e007400740065006a0061002e0020004c0075006f0064007500740020005000440046002d0064006f006b0075006d0065006e00740069007400200076006f0069006400610061006e0020006100760061007400610020004100630072006f0062006100740069006c006c00610020006a0061002000410064006f00620065002000520065006100640065007200200035002e0030003a006c006c00610020006a006100200075007500640065006d006d0069006c006c0061002e>
/SVE <FEFF0041006e007600e4006e00640020006400650020006800e4007200200069006e0073007400e4006c006c006e0069006e006700610072006e00610020006f006d002000640075002000760069006c006c00200073006b006100700061002000410064006f006200650020005000440046002d0064006f006b0075006d0065006e007400200073006f006d002000e400720020006c00e4006d0070006c0069006700610020006600f60072002000700072006500700072006500730073002d007500740073006b00720069006600740020006d006500640020006800f600670020006b00760061006c0069007400650074002e002000200053006b006100700061006400650020005000440046002d0064006f006b0075006d0065006e00740020006b0061006e002000f600700070006e00610073002000690020004100630072006f0062006100740020006f00630068002000410064006f00620065002000520065006100640065007200200035002e00300020006f00630068002000730065006e006100720065002e>
/TUR <FEFF005900fc006b00730065006b0020006b0061006c006900740065006c0069002000f6006e002000790061007a006401310072006d00610020006200610073006b013100730131006e006100200065006e0020006900790069002000750079006100620069006c006500630065006b002000410064006f006200650020005000440046002000620065006c00670065006c0065007200690020006f006c0075015f007400750072006d0061006b0020006900e70069006e00200062007500200061007900610072006c0061007201310020006b0075006c006c0061006e0131006e002e00200020004f006c0075015f0074007500720075006c0061006e0020005000440046002000620065006c00670065006c0065007200690020004100630072006f006200610074002000760065002000410064006f00620065002000520065006100640065007200200035002e003000200076006500200073006f006e0072006100730131006e00640061006b00690020007300fc007200fc006d006c00650072006c00650020006100e70131006c006100620069006c00690072002e>
/UKR <FEFF04120438043a043e0440043804410442043e043204430439044204350020044604560020043f043004400430043c043504420440043800200434043b044f0020044104420432043e04400435043d043d044f00200434043e043a0443043c0435043d044204560432002000410064006f006200650020005000440046002c0020044f043a04560020043d04300439043a04400430044904350020043f045604340445043e0434044f0442044c00200434043b044f0020043204380441043e043a043e044f043a04560441043d043e0433043e0020043f0435044004350434043404400443043a043e0432043e0433043e0020043404400443043a0443002e00200020042104420432043e04400435043d045600200434043e043a0443043c0435043d0442043800200050004400460020043c043e0436043d04300020043204560434043a0440043804420438002004430020004100630072006f006200610074002004420430002000410064006f00620065002000520065006100640065007200200035002e0030002004300431043e0020043f04560437043d04560448043e04570020043204350440044104560457002e>
/ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.)
>>
/Namespace [
(Adobe)
(Common)
(1.0)
]
/OtherNamespaces [
<<
/AsReaderSpreads false
/CropImagesToFrames true
/ErrorControl /WarnAndContinue
/FlattenerIgnoreSpreadOverrides false
/IncludeGuidesGrids false
/IncludeNonPrinting false
/IncludeSlug false
/Namespace [
(Adobe)
(InDesign)
(4.0)
]
/OmitPlacedBitmaps false
/OmitPlacedEPS false
/OmitPlacedPDF false
/SimulateOverprint /Legacy
>>
<<
/AddBleedMarks false
/AddColorBars false
/AddCropMarks false
/AddPageInfo false
/AddRegMarks false
/ConvertColors /ConvertToCMYK
/DestinationProfileName ()
/DestinationProfileSelector /DocumentCMYK
/Downsample16BitImages true
/FlattenerPreset <<
/PresetSelector /MediumResolution
>>
/FormElements false
/GenerateStructure false
/IncludeBookmarks false
/IncludeHyperlinks false
/IncludeInteractive false
/IncludeLayers false
/IncludeProfiles false
/MultimediaHandling /UseObjectSettings
/Namespace [
(Adobe)
(CreativeSuite)
(2.0)
]
/PDFXOutputIntentProfileSelector /DocumentCMYK
/PreserveEditing true
/UntaggedCMYKHandling /LeaveUntagged
/UntaggedRGBHandling /UseDocumentProfile
/UseDocumentBleed false
>>
]
>> setdistillerparams
<<
/HWResolution [2400 2400]
/PageSize [612.000 792.000]
>> setpagedevice
|
| id | nasplib_isofts_kiev_ua-123456789-113321 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0130-5395 |
| language | Russian |
| last_indexed | 2025-12-01T13:54:43Z |
| publishDate | 2016 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Сергеев, А.В. 2017-02-06T15:00:21Z 2017-02-06T15:00:21Z 2016 Технологии поиска данных в одноранговых сетях, построенных на основе распределенных хеш-таблиц / А.В. Сергеев // Управляющие системы и машины. — 2016. — № 2. — С. 41-47. — Бібліогр.: 9 назв. — рос. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/113321 004.75 Проведен анализ архитектуры одноранговых сетей, построенных на основе распределенных хэш-таблиц, а также введены метрики для сравнения алгоритмов поиска с целью определения оптимального. Здійснено аналіз архітектури однорангових мереж, побудованих на основі розподілених хеш-таблиць, та введено метрики для порівняння алгоритмів пошуку з метою визначення оптимального. Introduction. The necessity of the large data sets processing, increasing the scalability and fault tolerance lead to the development of peer-to-peer networks, that require, unlike client-server architecture, the use of complex algorithms for data search. Thus, it is necessary to determine a peer-to-peer network with the optimal search algorithm according to the certain criteria. Purpose. The purpose of this paper is to analyze the constructed peer-to-peer networks based on distributed hash tables and to determine the optimal network according to some metrics. Methods. To determine the optimal system we have introduced the set of metrics, which correspond to the set of criteria’s which are critical to the systems comparison. The set of criteria’s is as follows: the number of steps in the search algorithm, the operation of calculating the «distance» between the elements of the network, and practical implementation of the system. Next, the criteria are ranked by importance and to each criterion there is a certain coefficient (weight) which is assigned so that the more important criterion strongly influences on the result than the less important. The linear convolution has been calculated for each system and the best system is the one which has the minimal result. Results. According to the result of calculations, the optimal search criteria is proved by Kademlia system, primarily due to the unique metric of distance between elements of the network. Conclusion. Analysis and comparison of peer-to-peer networks constructed on the basis of distributed hash tables, shows that, despite the fact that each of them is able to solve the problem of scalability and fault tolerance, the optimum system is Kademlia. ru Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Методы и средства обработки данных и знаний Технологии поиска данных в одноранговых сетях, построенных на основе распределенных хеш-таблиц Технології пошуку даних в тимчасових мережах, побудованих на основі розподілених хеш-таблиць The Technologies of the Data Retrieval in Peer-to-Peer Networks Constructed on the Basis of the Distributed Hash Tables Article published earlier |
| spellingShingle | Технологии поиска данных в одноранговых сетях, построенных на основе распределенных хеш-таблиц Сергеев, А.В. Методы и средства обработки данных и знаний |
| title | Технологии поиска данных в одноранговых сетях, построенных на основе распределенных хеш-таблиц |
| title_alt | Технології пошуку даних в тимчасових мережах, побудованих на основі розподілених хеш-таблиць The Technologies of the Data Retrieval in Peer-to-Peer Networks Constructed on the Basis of the Distributed Hash Tables |
| title_full | Технологии поиска данных в одноранговых сетях, построенных на основе распределенных хеш-таблиц |
| title_fullStr | Технологии поиска данных в одноранговых сетях, построенных на основе распределенных хеш-таблиц |
| title_full_unstemmed | Технологии поиска данных в одноранговых сетях, построенных на основе распределенных хеш-таблиц |
| title_short | Технологии поиска данных в одноранговых сетях, построенных на основе распределенных хеш-таблиц |
| title_sort | технологии поиска данных в одноранговых сетях, построенных на основе распределенных хеш-таблиц |
| topic | Методы и средства обработки данных и знаний |
| topic_facet | Методы и средства обработки данных и знаний |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/113321 |
| work_keys_str_mv | AT sergeevav tehnologiipoiskadannyhvodnorangovyhsetâhpostroennyhnaosnoveraspredelennyhheštablic AT sergeevav tehnologíípošukudanihvtimčasovihmerežahpobudovanihnaosnovírozpodílenihheštablicʹ AT sergeevav thetechnologiesofthedataretrievalinpeertopeernetworksconstructedonthebasisofthedistributedhashtables |