diff options
author | irungentoo <irungentoo@gmail.com> | 2013-06-25 17:16:45 -0400 |
---|---|---|
committer | irungentoo <irungentoo@gmail.com> | 2013-06-25 17:16:45 -0400 |
commit | 1837745d96f98827c0fb4f0db920cd29c20260c0 (patch) | |
tree | 6518bb0360462022a4e9209d95cd31666001f453 /docs/DHT.txt | |
parent | adc9c64fe61db1614ece1164db670af3efbf9073 (diff) |
Fixed one possible bug in the DHT and added a basic TODO list.
Fixed a possible segfault which could have been cause by handling an
empty packet.
Diffstat (limited to 'docs/DHT.txt')
-rw-r--r-- | docs/DHT.txt | 87 |
1 files changed, 87 insertions, 0 deletions
diff --git a/docs/DHT.txt b/docs/DHT.txt new file mode 100644 index 00000000..486aa38c --- /dev/null +++ b/docs/DHT.txt | |||
@@ -0,0 +1,87 @@ | |||
1 | DHT protocol: | ||
2 | Follows pretty much the principle of the torrent DHT: http://www.bittorrent.org/beps/bep_0005.html (READ IT) | ||
3 | |||
4 | But: | ||
5 | Vastly simplified packet format. | ||
6 | |||
7 | Boostrapping: | ||
8 | The first time you install the client we bootstrap it with a node on our servers.(bandwidth should not be a problem as the client only needs to be sent one reply.) | ||
9 | |||
10 | |||
11 | Basics (All the numbers here are just guesses and are probably not optimal values): | ||
12 | |||
13 | client list: A list of node ids closest (mathematically see bittorrent doc) to ours matched with ip addresses + port number corresponding to that id and a timestamp containing the time or time since the client was successfully pinged. | ||
14 | |||
15 | "friends" list: A list containing the node_ids of all our "friends" or clients we want to connect to. | ||
16 | Also contains the ip addresses + port + node_ids + timestamp(of last ping like in the client list) of the 8 clients closest (mathematically see bittorrent doc) to each "friend" | ||
17 | |||
18 | Two pinged lists: | ||
19 | -One for storing a list of ips along with their ping_ids and a timestamp for the ping requests | ||
20 | -One for storing a list of ips along with their ping_ids and a timestamp for the get nodes requests | ||
21 | Entries in the pinged lists expire after 5 seconds. | ||
22 | If one of the lists becomes full, the expire rate reduces itself one second or the new ping takes the place of the oldest one. | ||
23 | |||
24 | |||
25 | Entries in client list and "friends" list expire after 300 seconds without ping response. | ||
26 | Each client stores a maximum of 32 entries in its client list. | ||
27 | Each client in the client list and "friends" list is pinged every 60 seconds. | ||
28 | Each client in the client list and "friends" list has a timestamp which denote the last time it was successfully pinged. | ||
29 | If the corresponding clients timestamp is more than 130 seconds old it is considered bad. | ||
30 | Send a get nodes request every 20 seconds to a random good node for each "friend" in our "friends" list. | ||
31 | Send a get nodes request every 20 seconds to a random good node in the client list. | ||
32 | |||
33 | |||
34 | When a client receives any request from another: | ||
35 | -Respond to the request | ||
36 | -Ping request is replied to with with a ping response containing the same ping_id | ||
37 | -Get nodes request is replied with a send nodes reply containing the same ping_id and the good nodes from the client list and/or the "friends" list that are closest to the requested_node_id | ||
38 | |||
39 | -If the requesting client is not in the client list: | ||
40 | -If there are no bad clients in the list and the list is full: | ||
41 | -If the id of the other client is closer (mathematically see bittorrent doc) than at least one of the clients in the list or our "friends" list: | ||
42 | -Send a ping request to the client. | ||
43 | -if not forget about the client. | ||
44 | |||
45 | -If there are bad clients and/or the list isn't full: | ||
46 | -Send a ping request to the client | ||
47 | |||
48 | When a client receives a response: | ||
49 | -Ping response | ||
50 | -If the node was previously pinged with a matching ping_id (check in the corresponding pinged list.) | ||
51 | -If the node is in the client list the matching client's timestamp is set to current time. | ||
52 | -If the node is in the "friends" list the matching client's timestamp is set to current time for every occurrence. | ||
53 | -If the node is not in the client list: | ||
54 | -If the list isn't full, add it to the list. | ||
55 | -If the list is full, the furthest away (mathematically see bittorrent doc) bad client is replaced by the new one. | ||
56 | -If the list is filled with good nodes replace the furthest client with it only if it is closer than the replaced node. | ||
57 | -for each friend in the "friends" list: | ||
58 | -If that friend's client list isn't full, add that client to it | ||
59 | -If that friend's client list contains bad clients, replace the furthest one with that client. | ||
60 | -If that friend's client list contains only good clients | ||
61 | -If the client is closer to the friend than one of the other clients, it replaces the farthest one | ||
62 | -If not, nothing happens. | ||
63 | |||
64 | -Send nodes | ||
65 | -If the ping_id matches what we sent previously (check in the corresponding pinged list.): | ||
66 | -Each node in the response is pinged. | ||
67 | |||
68 | |||
69 | |||
70 | |||
71 | |||
72 | Protocol: | ||
73 | |||
74 | Node format: [char array (node_id), length=32 bytes][ip (in network byte order), length=4 bytes][port (in network byte order), length=2 bytes][Padding , length=2 bytes] | ||
75 | |||
76 | Valid queries and Responses: | ||
77 | |||
78 | Ping(Request and response): [byte with value: 00 for request, 01 for response][random 4 byte (ping_id)][char array (client node_id), length=32 bytes] | ||
79 | ping_id = a random integer, the response must contain the exact same number as the request | ||
80 | |||
81 | |||
82 | Get nodes (Request): | ||
83 | Packet contents: [byte with value: 02][random 4 byte (ping_id)][char array (client node_id), length=32 bytes][char array: requested_node_id (node_id of which we want the ip), length=32 bytes] | ||
84 | Valid replies: a send_nodes packet | ||
85 | |||
86 | Send_nodes (response): [byte with value: 03][random 4 byte (ping_id)][char array (client node_id), length=32 bytes][Nodes in node format, length=40 * (number of nodes (maximum of 8 nodes)) bytes] | ||
87 | ex: 03[Node][Node][Node] \ No newline at end of file | ||