Changes between Version 79 and Version 80 of NetDB/NextBackend


Ignore:
Timestamp:
Jun 4, 2013 10:23:01 PM (6 years ago)
Author:
hottuna
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • NetDB/NextBackend

    v79 v80  
    8989
    9090=== 1: Implement Kademlia ===
    91 A full implementation of Kademlia will be used as a base for further enhancements.
     91A full implementation of Kademlia will be used as a base for further enhancements. Every non-NATed router should be a participant in the new DHT issues surrounding small DHTs and nodes electing to become a DHT
    9292
    9393 * Investigate the i2p.zzz.kademlia implementation
     
    126126[[BR]]
    127127
     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 ==
     135Stores should ideally always be performed using Random Recursion to increase the spread of nodes that contain the inserted data.
     136
     137Iterative 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 ===
     152Recursion can be used to slow DOS the network.
     153
     154==== Metric 1 ====
     155Each 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.
     156This is what is used by R5N.
     157
     158==== Metric 2 ====
     159A Hops-travelled counter, ''h,,travelled,,'', can be used. The recursion can be terminated using ''h,,travelled,,'' ≤ 2*''T''.
     160
     161Estimated 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 ===
     170Estimated Buckets entries = 2^''b''^log2^''b''^(''N'') <=> ''N'' = (2^''b''^)^bucket_entries*pow(2,-''b'')^ [[BR]]
     171rand_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 ===
     175In 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 ====
     180For recursive stores a replication factor has to be calculated for each node on the path of recursion.
     181
     182r,,local_recursion,, = 1 + (''r''-1) / (''T'' + (''r''-1)/''h''), where ''T'' = log2^''b''^(''N'') and h represents the hops travelled.
     183Recursion is stopped when h < 2*''T''. 2*''T'' was chosen to compensate for inaccuracies in determining ''T''.
     184
     185
     186== Unresolved issues ==
     187
     188===
    128189The three lookup mechanisms could be used in either sequential failover mode, hybrid mode and parallel mode. [[BR]]
    129190 * Sequential failover mode would would produce the lowest possible network load, while still maintaining the reliability of Random Recursive lookups. However, the lookup speed will suffer if failovers are needed.
     
    131192 * Parallel mode would increase network load considerably, but provide the fastest possible lookup times at all times.
    132193
    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
    190195=== ''k''-bucket building for recursive lookups ===
    191196''k''-buckets need to be continually updated.