Когда узлу необходимо найти пиров для торрента, он использует «расстояния», сравнивая хеш торрента (infohash) с идентификаторами узлов («node ID») из своей таблицы маршрутизации. Затем он соединяется с известными ему узлами, идентификаторы которых более близки к хешу торрента, и запрашивает у них контактную информацию о пирах, участвующих в данный момент в файлообмене этого торрента. Если узлу, с которым установлена связь, известно о пирах для этого торрента, то в его ответе будет возвращена контактная информация о них. В противном случае, в своем ответе, узел должен вернуть контактную информацию о наиболее «близких» к хешу торрента узлах, из своей таблицы маршрутизации. Далее наш узел циклично опрашивает все более «близкие» к хешу торрента узлы, до тех пор пока не будут найдены все самые «близкие» узлы. После того, как ресурсы поиска исчерпаны, клиент рассылает свою контактную информацию всем ответившим пирам, идентификаторы которых наиболее «близки» к хешу торрента.

Когда узел запрашивает информацию о пирах для торрента, в ответ ему также приходит секретное значение «token». Если наш узел впоследствии решит проинформировать узел, к которому обращался ранее, о том что «мы» участвуем в файлообмене по запрашиваемому торренту, наш узел должен будет вернуть обратно этот «token». В свою очередь узел который предоставил «token», проверяет его используя IP нашего узла. Это позволяет предотвратит регистрацию торрентов «на имя» других узлов. Время, в течении которого возвращенный «token» всё ещё будет считаться «валидным», настоящим руководством точно не регламентируется. Token'ы должны приниматься обратно лишь в течении некоторого приемлемого количества времени. Реализация в BitTorrent использует хеш SHA1 от IP адреса и некоторого секретного значения, которое изменяется каждые 5 минут; принимаются token’ы, которым не более 10 минут.

Таблица Маршрутизации.

Каждый узел поддерживает у себя таблицу маршрутизации, состоящую из других известных «актуальных» узлов. Узлы этой таблицы используются при первых запросах в DHT. Также, узлы из таблицы возвращаются в ответ на поисковые запросы от других узлов.

Не все узлы, которые есть в таблице маршрутизации, одинаковы. Некоторые из них «актуальные», другие же нет. Многие узлы в DHT способны посылать и принимать запросы, но не все способны отвечать на запросы других узлов. Очень важно, чтобы таблицы маршрутизации всех узлов содержали только известные «актуальные» узлы. «Актуальным» узлом считается тот, который ответил хотя бы на один из наших запросов за последние 15 минут. Так же к «актуальным» относятся узлы, которые хотя бы раз отвечали на наши запросы, и при этом посылали нам хотя бы один запрос в течении последних 15-ти минут. После 15 минут отсутствия активности, узел переходит в разряд «сомнительных». Узел становится «не актуальным» в случае если он не отвечает на несколько запросов подряд. Узлы со статусом «актуальный» имеют более высокий приоритет.

Таблица маршрутизации содержит ID (идентификаторы) узлов, которые принадлежат диапазону значений от 0 до 2^160 (2 в степени 160). Таблица маршрутизации поделена на «блоки», каждый из которых покрывает часть из исходного диапазона значений. Для каждого блока определены min и max, определяющие минимальное и максимальное значение ID, которое может в нем храниться. Пустая таблица содержит всего один блок, включающий все возможные значения ID, где min=0 и max =2^160. Когда узел с ID равным N вставляется в таблицу маршрутизации, он помещается в блок для которого выполняется условие min <= N < max. Так как пустая таблица содержит только один блок, то в нее может быть помещен и любой ID. Каждый блок может содержать максимум К узлов, в текущей реализации К=8. Блок с К узлами считается «заполненным». Если блок «заполнен» и содержит только «актуальные» узлы, то ни один узел больше не может быть в него добавлен. Исключение составляет наш собственный ID, если он попадает в диапазон значений этого блока. В случае необходимости текущий блок заменяется двумя новыми, каждый из которых делит диапазон значений исходного блока пополам. Соответственно ID из старого блока распределяются между этими двумя новыми блоками. Например для таблицы с одним блоком, «заполненный» блок будет разделен на два новых с диапазонами значений: от 0 до 2^159 и от 2^159 до 2^160.

Когда блок заполнен «актуальными» узлами, то новый узел просто отбрасывается. Если какие-либо узлы в блоке становятся «не актуальны», то один из них заменяется на новый узел. Если в блоке есть «сомнительные» узлы, с которыми не было связи в течении последних 15-ти минут, то производиться попытка пропинговать наименее активный из них (связь с которым была наиболее давно). Если такой узел отвечает, то пингуется следующий «сомнительный» и наименее активный узел. И так до тех пор, пока один из них не ответит или все узлы в блоке не станут «актуальными». Если узел в блоке не отвечает на пинг, то допускается сделать ещё одну попытку перед исключением этого узла и заменой его на новый «актуальный» узел. Таким образом, таблица заполняется стабильно работающими узлами.

Каждый блок должен содержать свойство «last changed», показывающее, насколько устарело содержимое. Это свойство должно обновляться: когда узел в блоке пингуется и отвечает, происходит добавление нового узла в блок, узел в блоке заменяется другим узлом. Блоки, которые не изменялись в течении последних 15-ти минут, должны быть обновлены. Это делается посредством выбора случайного ID в пределах блока и применением к нему функции поиска find_nodes. Узлам, которые способны принимать запросы от других узлов, обычно не требуется часто обновлять блоки. Узлам же, которые не способны принимать запросы от других узлов (например находящимся за NAT), обычно требуется периодически обновлять все блоки, чтобы при использовании DHT, гарантировать наличие в их таблице «актуальных» узлов. 

После помещения первого узла в его же таблицу маршрутизации и затем во время запуска узел должен попытаться найти в DHT ближайшие к себе узлы. Это делается путем выдачи сообщений find_node к все более и более близким узлам до тех пор, пока он будет не в состоянии найти какой-либо более близкий. Между запусками клиентской программы таблица маршрутизации должна сохраняться.

Дополнение к протоколу BitTorrent.

Протокол BitTorrent был дополнен для того, чтобы производить обмен номерами UDP-портов узлов между теми пирами, которые предоставил трекер. Таким образом клиенты могут автоматически осуществить сидирование своих таблиц маршрутизации посредством периодической загрузки торрентов. Недавно установленные клиенты, которые пытаются загрузить бестрекерный торрент в первый раз, не будут иметь каких-либо узлов в своей таблице маршрутизации и будут нуждаться в контактах, включённых в торрент-файл.

В BitTorrent используется «рукопожатие» после которого идут 8 зарезервированных байт для расширений. Пиры, поддерживающие DHT, выставляют последний бит этих 8-ми байт. Пир, получающий при установлении связи подтверждение, что удалённый пир поддерживает DHT, должен отправить сообщение PORT. Оно начинается с байта 0x09 и последующих двух байт, содержащих UDP-порт DHT узла, в сетевом порядке байтов (big-endian). Пиры, которые получают это сообщение, должны попытаться осуществить пингование узла на полученный порт и IP-адрес удалённого пира. Если получен ответ на пинг, то узел должен попытаться вставить новую контактную информацию в свою таблицу маршрутизации по обычным правилам.

Расширения торрент-файлов.

В словаре торрентов, не использующих трекер, нет ключа «announce». Вместо этого, у таких торрентов имеется ключ «nodes» (узлы). Этот ключ должен быть установлен на K ближайших узлов из таблицы маршрутизации клиента, создающего торрент. Также ключ может быть установлен на известный действующий узел. Например, на узел управляемый человеком, создавшим торрент. Пожалуйста, не добавляйте автоматически "router.bittorrent.com" в торрент-файлы или таблицы маршрутизации клиентов.

nodes = [["<адрес хоста>", <номер порта>], ["<адрес порта>", <номер порта>], ...] 

nodes = [["127.0.0.1", 6881], ["узел.вашего.роутера", 4804]]

Протокол KRPC.

Протокол KRPC представляет собой простой RPC-механизм, который состоит из закодированных словарей, пересылаемых через UDP. В запросе и в ответе на запрос производится отсылка одного пакета. Повторных попыток нет. Имеется три типа сообщений: query, response и error. Для протокола DHT существуют четыре типа запросов: ping, find_node, get_peers и announce_peer.

KRPC-сообщение – это один словарь с двумя ключами, общими для каждого сообщения, и дополнительными ключами, зависящими от типа сообщения. Каждое сообщение содержит ключ «t» — строка, представляющая собой ID операции (транзакции). Данный ID операции генерируется запрашивающим узлом и возвращается в виде эхо-ответа. Таким образом, ответы могут быть сопоставлены нескольким разным запросам к одному и тому же узлу. В каждом KRPC сообщении также содержится ключ «y» — строка, описывающая тип сообщения. Ключ «y» может принимать следующие значения: «q» – для запроса, «r» – для ответа, «e» – для ошибки.

Кодирование связи.

Контактная информация пиров кодируется в виде 6-байтной строки. Она также известна как «Информация в компактном виде о IP-адресе/порте» и представляет собой IP-адрес в виде 4 байтов (big-endian) вместе с 2-мя байтами порта (big-endian), расположенными в конце.

Контактная информация узлов кодируется в виде 26-байтной строки. Она также известна как «Информация в компактном виде об узле» и представляет собой ID узла в виде 20 байтов (big-endian) вместе с «информацией в компактном виде о IP-адресе/порте», расположенной в конце.

Запросы.

Словари KRPC-сообщений со значением «q» ключа «y». Содержат два дополнительных ключа: «q» и «a». Ключ «q» — строка, содержащая название метода этого запроса. Ключ «a» — словарь, содержащий именованные аргументы к запросу.

Ответы.

Словари KRPC-сообщений со значением «r» ключа «y». Содержат один дополнительный ключ «r». Ключ «r» — словарь, содержащий именованные возвращаемые значения. Сообщения-ответы отсылаются после успешного завершения запроса.

Ошибки.

Словари KRPC-сообщений со значением «e» ключа «y». Содержат один дополнительный ключ «e». Ключ «e» — список. Первым элементом является целое число, представляющее собой код ошибки. Вторым элементом является строка, содержащая сообщение ошибки. Ошибки отсылаются если запрос не может быть выполнен. Следующая таблица описывает возможные коды ошибок:

Код Описание.

201 Общая ошибка

202 Ошибка сервера

203 Ошибка протокола, к примеру, неправильно сформированный пакет, неверные аргументы или недопустимый token

204 Метод неизвестен

Пакеты с примерами ошибок

общая ошибка = {"t":"aa", "y":"e", "e":[201, "A Generic Error Ocurred"]}

в кодированном виде = d1:eli201e23:A Generic Error Ocurrede1:t2:aa1:y1:ee

Запросы DHT.

Во всех запросах имеется ключ «id» и значение, содержащее ID запрашивающего узла. Во всех ответах имеется ключ «id» и значение, содержащее ID отвечающего узла.

ping

Наиболее элементарным запросом является пинг. «q» = «ping». В пинг-запросе имеется один аргумент: «id» — 20-байтная строка (big-endian), содержащая ID узла отправителя. В правильном ответе на пинг содержится лишь один ключ «id», содержащий ID отвечающего узла.

аргументы: {"id" : "<id запрашивающих узлов>"}

ответ: {"id" : "<id ответивших узлов>"}

Примеры пакетов.

Запрос ping = {"t":"aa", "y":"q", "q":"ping", "a":{"id":"abcdefghij0123456789"}}

в кодированном виде = d1:ad2:id20:abcdefghij0123456789e1:q4:ping1:t2:aa1:y1:qe

Ответ = {"t":"aa", "y":"r", "r": {"id":"mnopqrstuvwxyz123456"}}

в кодированном виде = d1:rd2:id20:mnopqrstuvwxyz123456e1:t2:aa1:y1:re

find_node

«Find node» используется для поиска контактной информации об узле, давшего свой ID. «q» = «find_node». В запросе find_node имеется два аргумента: «id» — содержит ID запрашивающего узла, и «target» — содержит ID узла, который собственно и ищет запрашивающий узел. Когда узел получает запрос find_node, он должен ответить ключом «nodes» и строкой, содержащей «информацию в компактном виде об узле» для искомого узла или для K (как правило равно 8-ми) ближайших к искомому «актуальных» узлов из своей таблицы маршрутизации.

аргументы: {"id" : "<ID запрашивающего узла>", "target" : "<ID искомого узла>"}

ответ: {"id" : "<ID отвечающего узла>", "nodes" : "<compact node info>"}

Примеры пакетов:

запрос find_node = {"t" : "aa", "y" : "q", "q" : "find_node", "a" : {"id" : "abcdefghij0123456789", "target" : "mnopqrstuvwxyz123456"}}

в кодированном виде = d1:ad2:id20:abcdefghij01234567896:target20:mnopqrstuvwxyz123456e1:q9:find_node1:t2:aa1:y1:qe

ответ = {"t" : "aa", "y" : "r", "r" : {"id":"0123456789abcdefghij", "nodes" : "def456..."}}

в кодированном виде = d1:rd2:id20:0123456789abcdefghij5:nodes9:def456...e1:t2:aa1:y1:re

get_peers

«Get peers» связано с полем «infohash» торрента. «q» = «get_peers». В запросе get_peers имеется два аргумента: «id» — содержит ID запрашивающего узла, и «info_hash» — содержит значение «infohash» торрента. Если у опрошенного узла имеются пиры для данного «infohash», то они возвращаются в ключе «values» в виде списка строк, содержащих «информацию в компактном формате об узлах». Если же у опрошенного узла нет пиров для данного «infohash», то он возвращается ключ «nodes», содержащий K ближайших, к предоставленному в запросе «infohash», узлов из своей таблицы маршрутизации. В обоих случаях ключ «token» также включается в возвращаемое значение. Значение «token» является необходимым аргументом для будущего запроса «announce_peer».

аргументы: {"id" : "<ID запрашивающего узла>", "info_hash": "<20-ти байтный infohash искомого торрента>"}

ответ: {"id" : "<ID отвечающего узла>", "token" : "<Секретный token>", "values" : ["<Информация о пире №1>", "<Информация о пире №2>"]}

или: {"id" : "<ID отвечающего узла>", "token" :"<Секретный token>", "nodes" : "<информация в компактном формате об узле>"}

Примеры пакетов:

запрос get_peers = {"t" : "aa", "y" : "q", "q" : "get_peers", "a" : {"id" : "abcdefghij0123456789", "info_hash" : "mnopqrstuvwxyz123456"}}

в кодированном виде = d1:ad2:id20:abcdefghij01234567899:info_hash20:mnopqrstuvwxyz123456e1:q9:get_peers1:t2:aa1:y1:qe

ответ, содержащий пиров = {"t" : "aa", "y" : "r", "r" : {"id" : "abcdefghij0123456789", "token" : "aoeusnth", "values" : ["axje.u", "idhtnm"]}}

в кодированном виде = d1:rd2:id20:abcdefghij01234567895:token8:aoeusnth6:valuesl15:axje.uidhtnmbrlee1:ti0e1:y1:re

ответ, содержащий ближайшие узлы = {'t' : 0, 'y' : 'r', 'r' : {'id' : 'abcdefghij0123456789', 'token' : 'aoeusnth', 'nodes' : 'def456...'}}

в кодированном виде = d1:rd2:id20:abcdefghij01234567895:nodes9:def456...5:token8:aoeusnthe1:ti0e1:y1:re

announce_peer

Этим сообщением узел анонсирует что он участвует в файлообмене по указанному торренту. Сообщение announce_peer имеет 4 аргумента:«id» — содержит ID запрашивающего узла, «info_hash» — содержит «infohash» торрента, «port» — содержит номер порта в виде целого числа и «token», полученный в ответе на предыдущий запрос get_peers. Опрошенный узел обязан проверить, что «token» был ранее отправлен на тот же самый IP-адрес, что и принадлежащий запрашивающему узлу. Затем опрошенный узел должен сохранить предоставленные IP-адрес и номер порта в своём хранилище контактной информации пиров, связав их с соответствующим «infohash».

аргументы: {"id" : "<ID запрашивающего узла>", "info_hash" : "<20-ти байтный infohash>", "port" : <номер порта>, "token" : "<Секретный token>"}

ответ: {"id" : "<ID отвечающего узла>"}

Примеры пакетов:

запрос announce_peers = {"t" : "aa", "y" : "q", "q" : "announce_peer", "a" : {"id" : "abcdefghij0123456789", "info_hash" : "mnopqrstuvwxyz123456", "port" : 6881, "token" : "aoeusnth"}}

в кодированном виде =

d1:ad2:id20:abcdefghij01234567899:info_hash20:mnopqrstuvwxyz1234564:porti6881e5:token8:aoeusnthe1:q13:announce_peer1:t2:aa1:y1:qe

ответ = {"t" : "aa", "y" : "r", "r" : {"id" : "mnopqrstuvwxyz123456"}}

в кодированном виде = d1:rd2:id20:mnopqrstuvwxyz123456e1:t2:aa1:y1:re

Сноски.

1. "Kademlia: A Peer-to-peer Information System Based on the XOR Metric",
Petar Maymounkov и David Mazieres, IPTPS 2002. http://www.cs.rice.edu/Conferences/IPTPS02/109.pdf

2. Чтобы получить уникальный ID — пользуйтесь SHA1 и обеспечивайте приемлемый уровень энтропии.