| 128 | |
| 129 | |
| 130 | === Recursion === |
| 131 | ''r'' FIND_VALUEs are initiated at the originator node. Every node should forward r,,local_recursion,, FIND_VALUEs requests. |
| 132 | |
| 133 | |
| 134 | == Store == |
| 135 | Stores should ideally always be performed using Random Recursion to increase the spread of nodes that contain the inserted data. |
| 136 | |
| 137 | Iterative and Recursive STORE queries are possible, however they both have limited spread of inserted data. Additionally the benefits of non-random Recursive STOREs would be insertion speed. Something that likely isn't a very important factor. |
| 138 | |
| 139 | [[BR]] |
| 140 | || '''Method''' || '''Store time''' || '''Spread''' || |
| 141 | || Recursive || (log2^''b''^(''N'') + 1)*RTT/2 || Low || |
| 142 | || Iterative || log2^''b''^(''N'')*RTT || Medium || |
| 143 | || Random Recursive || (log2^''b''^(''N'') + rand + 1)*RTT/2 || High || |
| 144 | [[BR]] |
| 145 | |
| 146 | === Recursion === |
| 147 | ''r'' STOREs are initiated at the originator node. Every node should forward r,,local_recursion,, STORE request. |
| 148 | |
| 149 | |
| 150 | == Implementation details == |
| 151 | === End of Recursion === |
| 152 | Recursion can be used to slow DOS the network. |
| 153 | |
| 154 | ==== Metric 1 ==== |
| 155 | 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. |
| 156 | This is what is used by R5N. |
| 157 | |
| 158 | ==== Metric 2 ==== |
| 159 | A Hops-travelled counter, ''h,,travelled,,'', can be used. The recursion can be terminated using ''h,,travelled,,'' ≤ 2*''T''. |
| 160 | |
| 161 | Estimated Buckets entries = 2^''b''^log2^''b''^(''N'') <=> ''N'' = (2^''b''^)^bucket_entries*pow(2,-''b'')^ [[BR]] |
| 162 | ''T'' = log2^''b''^(''N''), which is the average number of steps needed to go anywhere in the network. |
| 163 | |
| 164 | ==== Metric 1 && 2 ==== |
| 165 | "(''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 regarding R5N implementation. |
| 166 | |
| 167 | |
| 168 | |
| 169 | === Length of Random path === |
| 170 | Estimated Buckets entries = 2^''b''^log2^''b''^(''N'') <=> ''N'' = (2^''b''^)^bucket_entries*pow(2,-''b'')^ [[BR]] |
| 171 | rand_path_length = log2^''b''^(''N''), which is the average number of steps needed to go anywhere in the network [4]. |
| 172 | |
| 173 | |
| 174 | === Replication factor === |
| 175 | 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. |
| 176 | |
| 177 | ''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. |
| 178 | |
| 179 | ==== Recursive Replication factor ==== |
| 180 | For recursive stores a replication factor has to be calculated for each node on the path of recursion. |
| 181 | |
| 182 | r,,local_recursion,, = 1 + (''r''-1) / (''T'' + (''r''-1)/''h''), where ''T'' = log2^''b''^(''N'') and h represents the hops travelled. |
| 183 | Recursion is stopped when h < 2*''T''. 2*''T'' was chosen to compensate for inaccuracies in determining ''T''. |
| 184 | |
| 185 | |
| 186 | == Unresolved issues == |
| 187 | |
| 188 | === |
133 | | === Recursion === |
134 | | ''r'' FIND_VALUEs are initiated at the originator node. Every node should forward r,,local_recursion,, FIND_VALUEs requests. |
135 | | |
136 | | |
137 | | == Store == |
138 | | Stores should ideally always be performed using Random Recursion to increase the spread of nodes that contain the inserted data. |
139 | | |
140 | | Iterative and Recursive STORE queries are possible, however they both have limited spread of inserted data. Additionally the benefits of non-random Recursive STOREs would be insertion speed. Something that likely isn't a very important factor. |
141 | | |
142 | | [[BR]] |
143 | | || '''Method''' || '''Store time''' || '''Spread''' || |
144 | | || Recursive || (log2^''b''^(''N'') + 1)*RTT/2 || Low || |
145 | | || Iterative || log2^''b''^(''N'')*RTT || Medium || |
146 | | || Random Recursive || (log2^''b''^(''N'') + rand + 1)*RTT/2 || High || |
147 | | [[BR]] |
148 | | |
149 | | === Recursion === |
150 | | ''r'' STOREs are initiated at the originator node. Every node should forward r,,local_recursion,, STORE request. |
151 | | |
152 | | |
153 | | == Implementation details == |
154 | | === End of Recursion === |
155 | | Recursion can be used to slow DOS the network. |
156 | | |
157 | | ==== Metric 1 ==== |
158 | | 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. |
159 | | This is what is used by R5N. |
160 | | |
161 | | ==== Metric 2 ==== |
162 | | A Hops-travelled counter, ''h,,travelled,,'', can be used. The recursion can be terminated using ''h,,travelled,,'' ≤ 2*''T''. |
163 | | |
164 | | Estimated Buckets entries = 2^''b''^log2^''b''^(''N'') <=> ''N'' = (2^''b''^)^bucket_entries*pow(2,-''b'')^ [[BR]] |
165 | | ''T'' = log2^''b''^(''N''), which is the average number of steps needed to go anywhere in the network. |
166 | | |
167 | | ==== Metric 1 && 2 ==== |
168 | | "(''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 regarding R5N implementation. |
169 | | |
170 | | |
171 | | |
172 | | === Length of Random path === |
173 | | Estimated Buckets entries = 2^''b''^log2^''b''^(''N'') <=> ''N'' = (2^''b''^)^bucket_entries*pow(2,-''b'')^ [[BR]] |
174 | | rand_path_length = log2^''b''^(''N''), which is the average number of steps needed to go anywhere in the network [4]. |
175 | | |
176 | | |
177 | | === Replication factor === |
178 | | 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. |
179 | | |
180 | | ''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. |
181 | | |
182 | | ==== Recursive Replication factor ==== |
183 | | For recursive stores a replication factor has to be calculated for each node on the path of recursion. |
184 | | |
185 | | r,,local_recursion,, = 1 + (''r''-1) / (''T'' + (''r''-1)/''h''), where ''T'' = log2^''b''^(''N'') and h represents the hops travelled. |
186 | | Recursion is stopped when h < 2*''T''. 2*''T'' was chosen to compensate for inaccuracies in determining ''T''. |
187 | | |
188 | | |
189 | | == Unresolved issues == |
| 194 | |