📄 dht protocol.mht
字号:
From: <由 Microsoft Internet Explorer 5 保存>
Subject: BitTorrent.org ? For Developers ? DHT Protocol
Date: Mon, 23 Apr 2007 11:47:57 +0800
MIME-Version: 1.0
Content-Type: multipart/related;
type="text/html";
boundary="----=_NextPart_000_0000_01C7859D.3C5B8920"
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.3028
This is a multi-part message in MIME format.
------=_NextPart_000_0000_01C7859D.3C5B8920
Content-Type: text/html;
charset="utf-8"
Content-Transfer-Encoding: quoted-printable
Content-Location: http://www.bittorrent.org/Draft_DHT_protocol.html
=EF=BB=BF<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<?xml version=3D"1.0" encoding=3D"utf-8"?><HTML lang=3Den =
xml:lang=3D"en"=20
xmlns=3D"http://www.w3.org/1999/xhtml"><HEAD><TITLE>BitTorrent.org =
=C2=BB For Developers =C2=BB DHT Protocol</TITLE>
<META http-equiv=3DContent-type content=3D"text/html; =
charset=3Dutf-8"><LINK=20
media=3Dscreen href=3D"http://www.bittorrent.org/css/screen.css" =
type=3Dtext/css=20
rel=3Dstylesheet>
<META content=3D"MSHTML 6.00.2900.3059" name=3DGENERATOR></HEAD>
<BODY id=3Dwww-bittorrent-org>
<DIV class=3Dclear id=3Dupper>
<DIV id=3Dwrap>
<DIV id=3Dheader>
<H1><A=20
href=3D"http://www.bittorrent.org/index.html">BitTorrent<SPAN>.org</A></H=
1></DIV>
<DIV id=3Dnav>
<UL>
<LI><A href=3D"http://www.bittorrent.org/index.html">Home</A>=20
<LI><A href=3D"http://www.bittorrent.org/introduction.html">For =
Users</A>=20
<LI><SPAN>For Developers</SPAN> <!-- <li><a =
href=3D"./blog.html">Blog</a></li> --><!-- <li><a =
href=3D"./donate.html">Donate!</a></li> --></LI></UL></DIV><!-- ### =
Begin Content ### -->
<DIV id=3Dsecond>
<H2>DHT Protocol</H2>
<H3>From BitTorrentDev</H3>
<P>BitTorrent uses a "distributed sloppy hash table" (DHT) for storing =
peer=20
contact information for "trackerless" torrents. In effect, each peer =
becomes a=20
tracker. The protocol is based on Kademila and is implemented over =
UDP.</P>
<P>Please note the terminology used in this document to avoid confusion. =
A=20
"peer" is a client/server listening on a TCP port that implements the =
BitTorrent=20
protocol. A "node" is a client/server listening on a UDP port =
implementing the=20
distributed hash table protocol. The DHT is composed of nodes and stores =
the=20
location of peers. BitTorrent clients include a DHT node, which is used =
to=20
contact other nodes in the DHT to get the location of peers to download =
from=20
using the BitTorrent protocol.</P>
<H3>Contents</H3>
<UL>
<LI><A =
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#Overview">1=20
Overview</A>=20
<LI><A=20
=
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#Routing_Table">=
2=20
Routing Table</A>=20
<LI><A=20
=
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#BitTorrent_Prot=
ocol_Extension">3=20
BitTorrent Protocol Extension</A>=20
<LI><A=20
=
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#Torrent_File_Ex=
tensions">4=20
Torrent File Extensions</A>=20
<LI><A=20
=
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#KRPC_Protocol">=
5 KRPC=20
Protocol</A>=20
<UL>
<LI><A=20
=
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#Contact_Encodin=
g">5.1=20
Contact Encoding</A>=20
<LI><A =
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#Queries">5.2=20
Queries</A>=20
<LI><A=20
=
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#Responses">5.3 =
Responses</A>=20
<LI><A =
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#Errors">5.4=20
Errors</A>=20
<UL>
<LI><A=20
=
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#Example_Error_P=
ackets">5.4.1=20
Example Error Packets</A> </LI></UL></LI></UL>
<LI><A =
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#DHT_Queries">6 =
DHT Queries</A>=20
<UL>
<LI><A =
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#ping">6.1=20
ping</A>=20
<UL>
<LI><A=20
=
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#example_packets=
">6.1.1=20
Example Packets</A> </LI></UL>
<LI><A=20
=
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#find_node">6.2 =
find_node</A>=20
<UL>
<LI><A=20
=
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#example_packets=
_2">6.2.1=20
Example Packets</A> </LI></UL>
<LI><A=20
=
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#get_peers">6.3 =
get_peers</A>=20
<UL>
<LI><A=20
=
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#example_packets=
_3">6.3.1=20
Example Packets</A> </LI></UL>
<LI><A=20
=
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#announce_peer">=
6.4=20
announce_peer</A>=20
<UL>
<LI><A=20
=
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#example_packets=
_4">6.4.1=20
Example Packets</A> </LI></UL></LI></UL>
<LI><A =
href=3D"http://www.bittorrent.org/Draft_DHT_protocol.html#Footnotes">7=20
Footnotes</A> </LI></UL><A name=3DOverview></A>
<H3>Overview</H3>
<P>Each node has a globally unique identifier known as the "node ID." =
Node IDs=20
are chosen at random from the same 160-bit space as BitTorrent =
infohashes. A=20
"distance metric" is used to compare two node IDs or a node ID and an =
infohash=20
for "closeness." Nodes must maintain a routing table containing the =
contact=20
information for a small number of other nodes. The routing table becomes =
more=20
detailed as IDs get closer to the node's own ID. Nodes know about many =
other=20
nodes in the DHT that have IDs that are "close" to their own but have =
only a=20
handful of contacts with IDs that are very far away from their own.</P>
<P>In Kademlia, the distance metric is XOR and the result is interpreted =
as an=20
unsigned integer. distance(A,B) =3D |A =E2=8A=97 B| Smaller values are =
closer.</P>
<P>When a node wants to find peers for a torrent, it uses the distance =
metric to=20
compare the infohash of the torrent with the IDs of the nodes in its own =
routing=20
table. It then contacts the nodes it knows about with IDs closest to the =
infohash and asks them for the contact information of peers currently=20
downloading the torrent. If a contacted node knows about peers for the =
torrent,=20
the peer contact information is returned with the response. Otherwise, =
the=20
contacted node must respond with the contact information of the nodes in =
its=20
routing table that are closest to the infohash of the torrent. The =
original node=20
iteratively queries nodes that are closer to the target infohash until =
it cannot=20
find any closer nodes. After the search is exhausted, the client then =
inserts=20
the peer contact information for itself onto the responding nodes with =
IDs=20
closest to the infohash of the torrent.</P>
<P>The return value for a query for peers includes an opaque value known =
as the=20
"token." For a node to announce that its controlling peer is downloading =
a=20
torrent, it must present the token received from the same queried node =
in a=20
recent query for peers. When a node attempts to "announce" a torrent, =
the=20
queried node checks the token against the querying node's IP address. =
This is to=20
prevent malicious hosts from signing up other hosts for torrents. Since =
the=20
token is merely returned by the querying node to the same node it =
received the=20
token from, the implementation is not defined. Tokens must be accepted =
for a=20
reasonable amount of time after they have been distributed. The =
BitTorrent=20
implementation uses the SHA1 hash of the IP address concatenated onto a =
secret=20
that changes every five minutes and tokens up to ten minutes old are=20
accepted.</P><A name=3DRouting_Table></A>
<H3>Routing Table</H3>
<P>Every node maintains a routing table of known good nodes. The nodes =
in the=20
routing table are used as starting points for queries in the DHT. Nodes =
from the=20
routing table are returned in response to queries from other nodes.</P>
<P>Not all nodes that we learn about are equal. Some are "good" and some =
are=20
not. Many nodes using the DHT are able to send queries and receive =
responses,=20
but are not able to respond to queries from other nodes. It is important =
that=20
each node's routing table must contain only known good nodes. A good =
node is a=20
node has responded to one of our queries within the last 15 minutes. A =
node is=20
also good if it has ever responded to one of our queries and has sent us =
a query=20
within the last 15 minutes. After 15 minutes of inactivity, a node =
becomes=20
questionable. Nodes become bad when they fail to respond to multiple =
queries in=20
a row. Nodes that we know are good are given priority over nodes with =
unknown=20
status.</P>
<P>The routing table covers the entire node ID space from 0 to =
2<SUP>160</SUP>.=20
The routing table is subdivided into "buckets" that each cover a portion =
of the=20
space. An empty table has one bucket with an ID space range of min=3D0,=20
max=3D2<SUP>160</SUP>. When a node with ID "N" is inserted into the =
table, it is=20
placed within the bucket that has min <=3D N < max. An empty table =
has only=20
one bucket so any node must fit within it. Each bucket can only hold K =
nodes,=20
currently eight, before becoming "full." When a bucket is full of known =
good=20
nodes, no more nodes may be added unless our own node ID falls within =
the range=20
of the bucket. In that case, the bucket is replaced by two new buckets =
each with=20
half the range of the old bucket and the nodes from the old bucket are=20
distributed among the two new ones. For a new table with only one =
bucket, the=20
full bucket is always split into two new buckets covering the ranges=20
0..2<SUP>159</SUP> and 2<SUP>159</SUP>..2<SUP>160</SUP>.</P>
<P>When the bucket is full of good nodes, the new node is simply =
discarded. If=20
any nodes in the bucket are known to have become bad, then one is =
replaced by=20
the new node. If there are any questionable nodes in the bucket have not =
been=20
seen in the last 15 minutes, the least recently seen node is pinged. If =
the=20
pinged node responds then the next least recently seen questionable node =
is=20
pinged until one fails to respond or all of the nodes in the bucket are =
known to=20
be good. If a node in the bucket fails to respond to a ping, it is =
suggested to=20
try once more before discarding the node and replacing it with a new =
good node.=20
In this way, the table fills with stable long running nodes.</P>
<P>Each bucket should maintain a "last changed" property to indicate how =
"fresh"=20
the contents are. When a node in a bucket is pinged and it responds, or =
a node=20
is added to a bucket, or a node in a bucket is replaced with another =
node, the=20
bucket's last changed property should be updated. Buckets that have not =
been=20
changed in 15 minutes should be "refreshed." This is done by picking a =
random ID=20
in the range of the bucket and performing a find_nodes search on it. =
Nodes that=20
are able to receive queries from other nodes usually do not need to =
refresh=20
buckets often. Nodes that are not able to receive queries from other =
nodes=20
usually will need to refresh all buckets periodically to ensure there =
are good=20
nodes in their table when the DHT is needed. </P>
<P>Upon inserting the first node into it's routing table and when =
starting up=20
thereafter, the node should attempt to find the closest nodes in the DHT =
to=20
itself. It does this by issuing find_node messages to closer and closer =
nodes=20
until it cannot find any closer. The routing table should be saved =
between=20
invocations of the client software.</P><A=20
name=3DBitTorrent_Protocol_Extension></A>
<H3>BitTorrent Protocol Extension</H3>
<P>The BitTorrent protocol has been extended to exchange node UDP port =
numbers=20
between peers that are introduced by a tracker. In this way, clients can =
get=20
their routing tables seeded automatically through the download of =
regular=20
torrents. Newly installed clients who attempt to download a trackerless =
torrent=20
on the first try will not have any nodes in their routing table and will =
need=20
the contacts included in the torrent file.</P>
<P>Peers supporting the DHT set the last bit of the 8-byte reserved =
flags=20
exchanged in the BitTorrent protocol handshake. Peer receiving a =
handshake=20
indicating the remote peer supports the DHT should send a PORT message. =
It=20
begins with byte 0x09 and has a two byte payload containing the UDP port =
of the=20
DHT node in network byte order. Peers that receive this message should =
attempt=20
to ping the node on the received port and IP address of the remote peer. =
If a=20
response to the ping is recieved, the node should attempt to insert the =
new=20
contact information into their routing table according to the usual =
rules.</P><A=20
name=3DTorrent_File_Extensions></A>
<H3>Torrent File Extensions</H3>
<P>A trackerless torrent dictionary does not have an "announce" key. =
Instead, a=20
trackerless torrent has a "nodes" key. This key should be set to the K =
closest=20
nodes in the torrent generating client's routing table. Alternatively, =
the key=20
could be set to a known good node such as one operated by the person =
generating=20
the torrent. Please do not automatically add "router.bittorrent.com" to =
torrent=20
files or automatically add this node to clients routing tables.</P>
<P><CODE>nodes =3D [["<host>", <port>], ["<host>",=20
<port>], ...] nodes =3D [["127.0.0.1", 6881], ["your.router.node", =
4804]]</CODE></P><A name=3DKRPC_Protocol></A>
<H3>KRPC Protocol</H3>
<P>The KRPC protocol is a simple RPC mechanism consisting of bencoded=20
dictionaries sent over UDP. A single query packet is sent out and a =
single=20
packet is sent in response. There is no retry. There are three message =
types:=20
query, response, and error. For the DHT protocol, there are four =
queries: ping,=20
find_node, get_peers, and announce_peer.</P>
<P>A KRPC message is a single dictionary with two keys common to every =
message=20
and additional keys depending on the type of message. Every message has =
a key=20
"t" with a single character string value representing a transaction ID. =
This=20
transaction ID is generated by the querying node and is echoed in the =
response,=20
so responses may be correlated with multiple queries to the same node. =
The other=20
key contained in every KRPC message is "y" with a single character value =
describing the type of message. The value of the "y" key is one of "q" =
for=20
query, "r" for response, or "e" for error.</P><A =
name=3DContact_Encoding></A>
<H4>Contact Encoding</H4>
<P>Contact information for peers is encoded as a 6-byte string. Also =
known as=20
"Compact IP-address/port info" the 4-byte IP address is in network byte =
order=20
with the 2 byte port in network byte order concatenated onto the =
end.</P>
<P>Contact information for nodes is encoded as a 26-byte string. Also =
known as=20
"Compact node info" the 20-byte Node ID in network byte order has the =
compact=20
IP-address/port info concatenated to the end.</P><A name=3DQueries></A>
<H4>Queries</H4>
<P>Queries, or KRPC message dictionaries with a "y" value of "q", =
contain two=20
additional keys; "q" and "a". Key "q" has a string value containing the =
method=20
name of the query. Key "a" has a dictionary value containing named =
arguments to=20
the query.</P><A name=3DResponses></A>
<H4>Responses</H4>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -