128 | | == End of Recursion == |
129 | | Recursion can be used to slow DOS the network. |
130 | | |
131 | | === Metric 1 === |
132 | | Each node in the path of the recursion will stop forwarding the query if it is closer to the ''key'' than any node in its routing table. |
133 | | This is what is used by R5N. |
134 | | |
135 | | === Metric 2 === |
136 | | A Hops-travelled counter, ''h,,travelled,,'', can be used. The recursion can be terminated using ''h,,travelled,,'' ≤ 2*''T''. |
137 | | |
138 | | Estimated Buckets entries = 2^b^log2^b^(N) <=> N = (2^b^)^bucket_entries*pow(2,-b)^ [[BR]] |
139 | | ''T'' = log2^b^(N), which is the average number of steps needed to go anywhere in the network. |
140 | | |
141 | | === Metric 1 && 2 === |
142 | | "(''h'' > ''T'' && closest) || (''h'' > 4''T'') right now (4''T'' or 3''T'' or 2''T'', not sure); that way, the random walk (''h'' <= ''T'') doesn't terminate at a local min by accident." -- C. Grothoff [4] |
143 | | |
144 | | |
145 | | |
146 | | == Length of Random path == |
147 | | Estimated Buckets entries = 2^b^log2^b^(N) <=> N = (2^b^)^bucket_entries*pow(2,-b)^ [[BR]] |
148 | | rand_path_length = log2^b^(N), which is the average number of steps needed to go anywhere in the network [4]. |
149 | | |
150 | | |
151 | | == Replication factor == |
152 | | In standard kad, ''k'' is used as the replication factor, or how many STORE request that will be sent by the originator. The replication factor, henceforth ''r'' is a trade-of between FIND_VALUE performance and the cost of STORE. Since no data is permanent in the NetDB a relatively high replication factor should be acceptable. |
153 | | |
154 | | ''r'' is determined by, ''r'' = (N/c)^1/2^, where c is a constant describing the number of nodes with direct TCP/UDP connection to this node. For our purposes a value for c would be chosen. |
155 | | |
156 | | === Recursive Replication factor === |
157 | | For recursive stores a replication factor has to be calculated for each node on the path of recursion. |
158 | | |
159 | | r,,local_recursion,, = 1 + (''r''-1) / (''T'' + (''r''-1)/''h''), where ''T'' = log2^b^(N) and h represents the hops travelled. |
160 | | Recursion is stopped when h < 2*T. 2*T to compensate for inaccuracies in determining T. |
161 | | |
162 | | |
163 | | == ''Key''-rotation == |
164 | | ''Key''-rotation might be an interesting idea in the form of hash(dest+low_res_timestamp). It may help out against eclipse attacks if the results of the UCSB paper [9] holds up. This will have to verified before any implementation of it is meaningful. |
165 | | |
166 | | It is only interesting if the time it takes for malicious Eclipse-nodes to integrate into the DHT is significant. |
167 | | nodes_needed_for_eclipse = (60/key_rot_interval)*eclipse_integration_time*attackers_per_eclipse[[BR]] |
168 | | nodes_needed_for_eclipse = (60/10)*24*20 = 2880. A key rotation interval of 10 minutes is chosen, the time it takes to integrate a new malicious node into the DHT is guessed to be 24hrs and finally 20 attackers per destination is what was used in the UCSB paper [9] to Eclipse a ''key''.[[BR]] |
| 152 | |
| 153 | |
| 154 | == Implementation details == |
| 155 | === End of Recursion === |
| 156 | Recursion can be used to slow DOS the network. |
| 157 | |
| 158 | ==== Metric 1 ==== |
| 159 | Each node in the path of the recursion will stop forwarding the query if it is closer to the ''key'' than any node in its routing table. |
| 160 | This is what is used by R5N. |
| 161 | |
| 162 | ==== Metric 2 ==== |
| 163 | A Hops-travelled counter, ''h,,travelled,,'', can be used. The recursion can be terminated using ''h,,travelled,,'' ≤ 2*''T''. |
| 164 | |
| 165 | Estimated Buckets entries = 2^b^log2^b^(N) <=> N = (2^b^)^bucket_entries*pow(2,-b)^ [[BR]] |
| 166 | ''T'' = log2^b^(N), which is the average number of steps needed to go anywhere in the network. |
| 167 | |
| 168 | ==== Metric 1 && 2 ==== |
| 169 | "(''h'' > ''T'' && closest) || (''h'' > 4''T'') right now (4''T'' or 3''T'' or 2''T'', not sure); that way, the random walk (''h'' <= ''T'') doesn't terminate at a local min by accident." -- C. Grothoff [4] |
| 170 | |
| 171 | |
| 172 | |
| 173 | === Length of Random path === |
| 174 | Estimated Buckets entries = 2^b^log2^b^(N) <=> N = (2^b^)^bucket_entries*pow(2,-b)^ [[BR]] |
| 175 | rand_path_length = log2^b^(N), which is the average number of steps needed to go anywhere in the network [4]. |
| 176 | |
| 177 | |
| 178 | === Replication factor === |
| 179 | In standard kad, ''k'' is used as the replication factor, or how many STORE request that will be sent by the originator. The replication factor, henceforth ''r'' is a trade-of between FIND_VALUE performance and the cost of STORE. Since no data is permanent in the NetDB a relatively high replication factor should be acceptable. |
| 180 | |
| 181 | ''r'' is determined by, ''r'' = (N/c)^1/2^, where c is a constant describing the number of nodes with direct TCP/UDP connection to this node. For our purposes a value for c would be chosen. |
| 182 | |
| 183 | ==== Recursive Replication factor ==== |
| 184 | For recursive stores a replication factor has to be calculated for each node on the path of recursion. |
| 185 | |
| 186 | r,,local_recursion,, = 1 + (''r''-1) / (''T'' + (''r''-1)/''h''), where ''T'' = log2^b^(N) and h represents the hops travelled. |
| 187 | Recursion is stopped when h < 2*T. 2*T to compensate for inaccuracies in determining T. |