[Gzz-commits] gzz/Documentation/misc/hemppah-progradu researc...

[Hermanni Hyytiälä]

CVSROOT:        /cvsroot/gzz
Module name:    gzz
Changes by:     Hermanni Hyytiälä <address@hidden>      03/02/05 08:39:24

Modified files:
        Documentation/misc/hemppah-progradu: research_problems 

Log message:
        Difference table + DHTs' tree idea

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/research_problems.diff?tr1=1.43&tr2=1.44&r1=text&r2=text

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/research_problems
diff -u gzz/Documentation/misc/hemppah-progradu/research_problems:1.43 
gzz/Documentation/misc/hemppah-progradu/research_problems:1.44
--- gzz/Documentation/misc/hemppah-progradu/research_problems:1.43      Wed Feb 
 5 07:51:44 2003
+++ gzz/Documentation/misc/hemppah-progradu/research_problems   Wed Feb  5 
08:39:24 2003
@@ -48,6 +48,10 @@
 -Example applications: CFS \cite{dabek01widearea}, PAST 
\cite{rowstron01storage}, Oceanstore \cite{kubiatowicz00oceanstore}
 -data distribution approaches (like in Squirrel \cite{iyer02squirrel}): home 
node approach and directory approach
 -CFS splits files into blocks (<50Kb), PAST distributed whole files
+-the basic idea behind many DHTs is the fact that they perform operations in a 
binary-like tree
+-more space/node --> the search arity is higher --> k is higher in k-ary trees
+-DHTs' performance efficiency is derived from these tree based operations 
(e.g. split to half the previous scope)
+
 
 *Update*
 -Viceroy system achieves O(log n) hops with only O(1) neighbors
@@ -159,7 +163,17 @@
 
 Summary
 
-This summary table is far from complete (and from total truth)
+Following figures has to be done:
+
+1) application level overlay vs. network level overlay
+2) Overview of structured overlay network
+3) Overview of basic gnutella network
+4) Overview of gnutella network with some improvements (super nodes and 
clusters)
+5) Figure presenting k-ary tree (--> log n efficiency)
+
+Include following tables:
+
+1) Summary table:
 
 Protocol:              Insert/Delete   Space           Search                  
# of network connections
 Chord:                         O(log^2 n)      O(log n)        O(log n)        
        2(log n)
@@ -179,6 +193,24 @@
 PeerNet 4):            O(log n)        O(log n)        O(log n)                
O(log n)
 Kelips:                        *****           O(sqrt(n))      O(1)            
        n/sqrt(n) + c*(sqrt(n)-1) + 'Total number of files'/sqrt(n)
 Freenet:               O(1)            O(1)            O(n)                    
??
+
+
+2) Difference table for approaches:
+
+                                 DHT                           Broadcast
+Queries:                         Controlled                    uncontrolled
+A way for performing queries:    Exact keys                    Keywords
+Query traffic:                   O(1)/O(log n)                 O(n)/O(n^2)
+Will find the data item ?:       Yes                           Not necessarily
+Overlay's structure:             Controlled and structured     Uncontrolled 
and ad hoc
+Max. number of nodes ?:                  Billions                      Millions
+Data placement:                          Not local                     Local
+Support for heterogeneiy:        No                            Yes
+Support for locality:            Partial                       No
+Possibilty for routing hotspots:  Yes                          No
+Design/Implementation complexity: High                         Low
+
+
 
 * = In Kademlia, there is no action required when nodes leaves the system