Диссертация (1137145), страница 5
Текст из файла (страница 5)
9. Псевдо код алгоритма маршрутизации поискового сообщения при поиске ключа.1.1.5 ПримененияРазличныереализацииDHTиспользуютсядляпостроенияраспределенных индексов и поисковых машин (YaCy), распределенныхфайловых систем,торрент-трэкеровфайлообменных сетей, реализации распределенных[Loewenstern,Norbeg,2008],облачныхсервисов,например, CloudSNAP [R. Mondéjar, 2011], систем корпоративногокэширования CoDeeN [CoDeeN, 2003].Разберём более подробно, как используется DHT в реализациираспределённого torrent-трэкера Mainline DHT1.1.5.1 Распределенный torrent-трэкер Mainline DHTTorrent – файлообменный p2p протокол позволяющий пирам (клиентам)соединяться друг с другом и обмениваться сегментами файлов безнепосредственного участия какого-либо центрального сервера.
Однакооригинальная версия протокола требовала наличия в сети трэкера специализированного сервера координирующего работу клиентов попротоколу HTTP. Каждый раз перед началом скачивания клиент долженбыл подсоединиться к трэкеру по адресу, указанному в торрент-файле подключом "announce", сообщить ему свой адрес и хэш-сумму торрент-файла,на что в ответ клиент получал адреса других пиров, скачивающих или27раздающих этот же файл, после чего пиры начинали непосредственноевзаимодействие с друг другом.Распределенный торрент-трэкер имеет тоже назначение, что и обычныйторрент-трэкер,нофункциональностьегораспределенамеждумножеством узлов.
Распределённый трэкер использующих DHT былвпервые реализован в торрент-клиенте Azureus версии 2.3.0.0 в мае 2005года.Mainline DHT - это распределенные торрент-трэкер реализованныйкомпанией Bittorent Inc. использующий протокол Kademlia.Программа Bit-Torrent клиент, которую использует пользователь,содержит модуль торрент пира (пир - клиент-сервер, слушающий TCP портиреализующийBitTorrentпротокол),атакжефункциональностьраспределенного торрент-рэкера.
Пользователь может выбрать включитьили выключить распределенный трэкер. При включении на машинепользователя запускается узел DHT и ему присваивается 160-битныйуникальный идентификатор. Для коммуникации DHT узел использует UDPпротокол.Торрент файл содержит информацию о раздаче, название, списокфайлов, а также контрольные суммы сегментов раздаваемых файлов. Вкачестве ключей для DHT используются 160-битные хэши SHA-1 отторрент-файлов, называемых инфохэшами (infohash). В качестве значениясвязанного с каждым ключом (инфохэшем) в DHT сохраняется списокпиров раздающих или скачивающих файлы описанных в торрент-файле откоторого был вычислен данный инфохэш.Каждый узел DHT хранит информацию, связанную с инфохэшами длякоторых его идентификатор является одним из k-ближайших узлов поXOR-метрике.Когда клиент хочет найти пиры для торрент-файла, используя XORметрику, он сравнивает с инфохэшем торрент-файла идентификаторыизвестных ему узлов DHT из своей таблицы маршрутизации.
Далее он28спрашивает k-ближайших,есть ли у них информация о пирах дляторрента. Если нет, то опрашиваемые узлы сообщают клиенту kближайших узлов к искомому инфохэшу из известных им. Из них сновавыбираются k-ближайших и процесс продолжается итеративно до тех пор,покаэтовозможно.Послеостановкипоискаклиентразмещаетинформацию о себе на k-ближайших узлах относительно искомоготоррент-файла.1.1.5.2 Расширение протокола BitTorrentСтандартныйBitTorrentпротоколбылрасширенвозможностьюобмениваться UDP портами DHT узлов. Таким образом, клиенты получиливозможность заполнять таблицу маршрутизации, осуществляя обычнуюзагрузку.
Клиенты, которые только что были установлены и намеренысделать загрузку без трэкера, изначально не знают ни одного DHT узла ипоэтому берут адреса узлов из торрент-файла.Клиенты, поддерживающие DHT, выставляют последний бит из 8зарезервированныхбайтоввприветственномсообщенииторрентпротокола. Пир, получивший такое сообщение, если он поддерживаетDHT, должен в ответном сообщении указать номер порта. Пир, которомусообщили номер порта, делает пинг по этому порту.
Если ответ на пингполучен, то узел вставляет информацию о новом контакте в таблицумаршрутизации согласно алгоритму Kademlia.1.1.5.3 Расширение торрент-файлаБезтрэкерный (не привязанный к трэкеру) торрент-файл не имеет записис ключом "announce". Вместо этого в нём есть запись с ключом "nodes"содержащая адреса DHT узлов k-ближайших к инфохэшу данного торрентфайла, либо адреса DHT узлов начиная с которых ближайшие к инфокэшумогутбытьnodes=найдены.[["<host>",Запись<port>],29имеетследующий["<host>",формат:<port>],...]Запись для двух узлов могла бы выглядеть следующим образом:nodes = [["127.0.0.1", 6881], ["your.router.node", 4804]]1.1.5.4 KRPC протоколПротокол KRPC служит для реализации RPC механизма.
Он состоит изсловарей, посылаемых по UPD протоколу в формате "bencode" (bencode формат кодирования, используемый протоколом торрент). Запросы иответы осуществляются одиночными пакетами без повторной отправки.Используется 3 типа сообщений: запрос, ответ и ошибка. Для DHTпротокола существуют 4 вида запроса: ping, find_node, get_peers иannounce_peer.Сообщение KRPC – это единичный словарь с двумя ключами общимидля всех сообщений и дополнительными записями, зависящими от типасообщения. Каждое сообщение имеет ключ "t" со строковым значением,котороеобозначаетидентификатортранзакции.Идентификатортранзакции генерируется запрашивающим узлом и должно присутствоватьв ответном сообщении.
Идентификатор транзакции кодируется какдвоичное число из двух байтов. Другой ключ общий для всех сообщений это ключ "y". С ним связанно значение длиной в один символ,обозначающее тип сообщения. Соответственно, "q" - запрос, "r" - ответ, изначение "e" обозначает ошибку.Контактная информация о пирах кодируется в виде 6-ти байтовойстроки. Первые 4 байта - это IP-адрес, последние 2 байта - номер порта.Для контактной информации о DHT узлах используется строка из 26байтов.
Первые 20 байт кодируют идентификатор узла, далее 4 байта – IPадрес и последние 2 байта кодируют порт.Запросные сообщения с ключом "y"и значением "q" содержат двадополнительных ключа; "q" и "a". С "q" связанна строка интерпретируемаякак название запрашиваемого метода. С ключомименованные аргументы, представленные в виде словаря.30"a" связанныОтветные сообщения с ключом "y" и значением "r" содержатдополнительный ключ "r".
С ним связанно значение в виде словаряимеющее смысл возвращаемых именованных значений в результатевыполнение метода.Сообщения об ошибке c ключом "y" и значением "e" имеют одиндополнительный ключ "e". С ним связанно значение в виде списка из двухэлементов. Первый элемент - число обозначающее код ошибки; второе это строка сообщения об ошибке.1.1.5.5 Распределенная система доменных именЛюбое устройство, подключенное к сети Интернет, идентифицируетсяуникальным сетевым адресом, представляющим собой 32 или 128-битноедвоичное число, традиционно записываемое в виде последовательностидесятичных или шестнадцатеричных чисел.
Несмотря на то, чтомаршрутизация данных в Интернете осуществляется на основе сетевыхадресов устройств, для человека гораздо легче запомнить буквенное, частоосмысленное имя, чем набор цифр сетевого адреса. Доменные именаиграют важную роль в функционировании Интернета, так как поисклюбого сетевого устройства, подключенного к сети Интернет, обычноначинается с его имени.Система доменных имен (англ. Domain Name System сокр. DNS)представляет собой огромную, иерархическую, распределенную базуданных, позволяющую по имени устройства находить его IP-адрес.Несмотря на весь успех, у DNS имеется ряд недостатков. Самыйочевидный недостаток - это то, что для администрирования DNSнеобходима глубокая экспертиза.
В книге по использованию DNS серверов[Albitz & Liu, 1998] на основе BIND, авторы отмечают, что большая частьпроблем DNS связанна с неправильным конфигурированием серверов.Другим недостатком DNS являются её уязвимость к DoS-атакам (от англ.Denial of Service - отказ обслуживания) [Douligeris C., Mitrokotsa A., 2004]31и неравномерное распределение нагрузки; так в работе [Jung, Sit,Balakrishnan, & Morris, 2001] было показано, что более 18% DNS трафикаприходится на корневые серверы. С целью решить эти проблемы в работах[Jung, Sit, Balakrishnan, & Morris, 2001], [Ramasubramanian & Sirer, 2004]был предложены новые варианты реализации DNS основанные DHT.Использование DHTдляреализации DNSобуславливаетсятремясвойствами DHT; это – самоорганизуемость, сбалансированность иотказоустойчивость.В системах альтернативных DNS записи о ресурсах помещаются в DHTна основании ключей, которым соответствуют хэш-значения, вычисленныеалгоритмомSHA-1отимениресурса.Дляподдержанияфункциональности поиска имени ресурса по его IP-адресу, в DHT так жепомещаются записи с ключом вычисленным алгоритмом SHA-1 от IPадреса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
