Changes between Version 75 and Version 76 of NetDB/NextBackend
 Timestamp:
 Jun 4, 2013 8:50:05 AM (6 years ago)
Legend:
 Unmodified
 Added
 Removed
 Modified

NetDB/NextBackend
v75 v76 1 1 = Why? = 2 '''Scalability:''' Currently we lack O(log( n)) lookup scalabilty if more !FloodFill nodes than the local NetDB contains exist.2 '''Scalability:''' Currently we lack O(log(''N'')) lookup scalabilty if more !FloodFill nodes than the local NetDB contains exist. 3 3 4 4 '''Resilience:''' Our current !FloodFill system is susceptible to attacks. … … 20 20 21 21 == DHTs == 22 DHTs are a good alternative due to O(log n) lookup time and a unlimited search horizon. But have serious issues when it comes to being robust against attacks.22 DHTs are a good alternative due to O(log(''N'')) lookup time and a unlimited search horizon. But have serious issues when it comes to being robust against attacks. 23 23 24 24 [[BR]] 25 25  '''Name'''  '''Search horizon*'''  '''Lookup steps'''  '''Mutable data'''  '''Comments'''  26  Kademlia  Unlimited  O(log2^ b^(n)) [2]**  No  Is susceptible to Sybil and Eclipse attacks.* 27  Freenet  Unlimited  O(log2( n)) [3]No  Is vulnerable to swap algorithm attacks, which wreak load balancing. [4] 28  Chord  Unlimited  O(log2( n)*0.5)[8]  No Is highly susceptible to Sybil and Eclipse attacks.* 29  Pastry  Unlimited  O(log2^ b^(n))[7]  No Is highly susceptible to Sybil and Eclipse attacks.* 26  Kademlia  Unlimited  O(log2^''b''^(''N'')) [2]**  No  Is susceptible to Sybil and Eclipse attacks.*  27  Freenet  Unlimited  O(log2(''N'')) [3]No  Is vulnerable to swap algorithm attacks, which wreak load balancing. [4]  28  Chord  Unlimited  O(log2(''N'')*0.5)[8]  No Is highly susceptible to Sybil and Eclipse attacks.*  29  Pastry  Unlimited  O(log2^''b''^(''N''))[7]  No Is highly susceptible to Sybil and Eclipse attacks.*  30 30 [[BR]] 31 31 32 32 * Kademlia is less susceptible to eclipse attacks. 33 33 "For one thing, it is difficult to affect the routing tables of a Kademlia node, as each node tends to keep only highly available peers in its routing table. This increases the required costs for an attacker to convince honest nodes to link to the compromised nodes. Similarly, Kademlia uses iterative routing, exploring multiple nodes at each step, making routing less dependent on specific nodes and thus less vulnerable to attacks." [1] [[BR]] 34 ** Kademlia lookups can be optimized by enlarging how many bits of IDs, b, that are considered for each bucket. With b > 1 lookup steps would be decreased from O(log2( n)) to O(log2^b^(n)) but the number of buckets would be increased to an expected 2^b^log2^b^(n). [2] [[BR]]34 ** Kademlia lookups can be optimized by enlarging how many bits of IDs, b, that are considered for each bucket. With b > 1 lookup steps would be decreased from O(log2(''N'')) to O(log2^''b''^(''N'')) but the number of buckets would be increased to an expected 2^''b''^log2^''b''^(''N''). [2] [[BR]] 35 35 36 36 [[BR]] … … 121 121 [[BR]] 122 122  '''Method'''  '''Lookup time (avg.)'''  '''Reliability'''  123  Recursive  (log2^ b^(n) + 1)*RTT/2  Low 124  Iterative  log2^ b^(n)*RTT  Medium 125  Random Recursive  ( log2^b^(n) + rand+ 1)*RTT/2  High 123  Recursive  (log2^''b''^(''N'') + 1)*RTT/2  Low  124  Iterative  log2^''b''^(''N'')*RTT  Medium  125  Random Recursive  (2*log2^''b''^(''N'') + 1)*RTT/2  High  126 126 [[BR]] 127 127 … … 142 142 [[BR]] 143 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 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 147 [[BR]] 148 148 … … 162 162 A Hopstravelled counter, ''h,,travelled,,'', can be used. The recursion can be terminated using ''h,,travelled,,'' ≤ 2*''T''. 163 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.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 166 167 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 [4]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 169 170 170 171 171 172 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].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 175 176 176 … … 178 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 tradeof 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 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.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 181 182 182 ==== Recursive Replication factor ==== 183 183 For recursive stores a replication factor has to be calculated for each node on the path of recursion. 184 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 to compensate for inaccuracies in determining T.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 187 188 188