Changes between Version 75 and Version 76 of NetDB/NextBackend


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

--

Legend:

Unmodified
Added
Removed
Modified
  • NetDB/NextBackend

    v75 v76  
    11= 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.
    33
    44'''Resilience:''' Our current !FloodFill system is susceptible to attacks.
     
    2020
    2121== 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.
     22DHTs 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.
    2323
    2424[[BR]]
    2525|| '''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.* ||
    3030[[BR]]
    3131
    3232* Kademlia is less susceptible to eclipse attacks.
    3333  "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]]
    3535
    3636[[BR]]
     
    121121[[BR]]
    122122|| '''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 ||
    126126[[BR]]
    127127
     
    142142[[BR]]
    143143|| '''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 ||
    147147[[BR]]
    148148
     
    162162A Hops-travelled counter, ''h,,travelled,,'', can be used. The recursion can be terminated using ''h,,travelled,,'' ≤ 2*''T''.
    163163
    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.
     164Estimated 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.
    166166
    167167==== 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.
    169169
    170170
    171171
    172172=== 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].
     173Estimated Buckets entries = 2^''b''^log2^''b''^(''N'') <=> ''N'' = (2^''b''^)^bucket_entries*pow(2,-''b'')^ [[BR]]
     174rand_path_length = log2^''b''^(''N''), which is the average number of steps needed to go anywhere in the network [4].
    175175
    176176
     
    178178In 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.
    179179
    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.
    181181
    182182==== Recursive Replication factor ====
    183183For recursive stores a replication factor has to be calculated for each node on the path of recursion.
    184184
    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.
     185r,,local_recursion,, = 1 + (''r''-1) / (''T'' + (''r''-1)/''h''), where ''T'' = log2^''b''^(''N'') and h represents the hops travelled.
     186Recursion is stopped when h < 2*''T''. 2*''T'' was chosen to compensate for inaccuracies in determining ''T''.
    187187
    188188