Changes between Version 71 and Version 72 of NetDB/NextBackend


Ignore:
Timestamp:
Jun 4, 2013 8:21:36 AM (6 years ago)
Author:
hottuna
Comment:

Legend:

Unmodified
Added
Removed
Modified
  • NetDB/NextBackend

    v71 v72  
    121121[[BR]]
    122122
    123 
    124123=== Recursion ===
    125124''r'' STOREs are initiated at the originator node. Every node should forward r,,local_recursion,, STORE request.
    126125
    127126
    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]]
    169127
    170128== How ==
     
    192150 * Implement random recursive lookups
    193151
     152
     153
     154== Implementation details ==
     155=== End of Recursion ===
     156Recursion can be used to slow DOS the network.
     157
     158==== Metric 1 ====
     159Each 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.
     160This is what is used by R5N.
     161
     162==== Metric 2 ====
     163A Hops-travelled counter, ''h,,travelled,,'', can be used. The recursion can be terminated using ''h,,travelled,,'' ≤ 2*''T''.
     164
     165Estimated 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 ===
     174Estimated Buckets entries = 2^b^log2^b^(N) <=> N = (2^b^)^bucket_entries*pow(2,-b)^ [[BR]]
     175rand_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 ===
     179In 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 ====
     184For recursive stores a replication factor has to be calculated for each node on the path of recursion.
     185
     186r,,local_recursion,, = 1 + (''r''-1) / (''T'' + (''r''-1)/''h''), where ''T'' = log2^b^(N) and h represents the hops travelled.
     187Recursion is stopped when h < 2*T. 2*T to compensate for inaccuracies in determining T.
    194188
    195189
     
    203197
    204198However '''Source: Direct Mode''' may provide an excellent DDOS attack vector if the originator address is not verified.
     199
     200
     201=== ''Key''-rotation ===
     202''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.
     203
     204It is only interesting if the time it takes for malicious Eclipse-nodes to integrate into the DHT is significant.
     205nodes_needed_for_eclipse = (60/key_rot_interval)*eclipse_integration_time*attackers_per_eclipse[[BR]]
     206nodes_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]]
     207
    205208
    206209=== !Performance/Memory trade-of for ''b'' ===