[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/01/08 06:31:42

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

Log message:
        Issues related to DHT routing

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/research_problems
diff -u gzz/Documentation/misc/hemppah-progradu/research_problems:1.13 
gzz/Documentation/misc/hemppah-progradu/research_problems:1.14
--- gzz/Documentation/misc/hemppah-progradu/research_problems:1.13      Thu Dec 
19 05:35:00 2002
+++ gzz/Documentation/misc/hemppah-progradu/research_problems   Wed Jan  8 
06:31:42 2003
@@ -10,9 +10,20 @@
 +scalable (10^9 users, 10^14 data items)
 +robust
 +little network traffic
--own resources are mapped into the network
+-own resources are mapped into the network (not necessary!!)
 -keyword/fuzzy search not possible yet
--hotspots
+-routing/query hotspots
+-ASSUME THAT ALL NODES HAVE IDENTICAL CABABILITIES! However, in real life, p2p 
enviroment is extremely heterogeneous!
+
+Open questions related to DHTs and routing:
+1) Which one is more important: short path length or overhead associated with 
keeping routing tables updated, e.g. number of state updates whenever 
join/leave occurs
+ (number of neighbors)
+2) Are we able to achieve reasonably pathlenghts with less neigbors (Viceroy) ?
+3) How big is the difference between optimal path length and worst case path 
length ?
+4) How difficult is to recover from total routing mislead and the cost of it ?
+5) Can we choose better neighbors by using network latencies instead of 
closeness of IDs in the ID space ? What are the effects doing so ?
+6) Can we choose IDs (globally) based on the geographical location/distance ? 
Is there a working model for doing so ?
+7) How do we should work with node heterogeneity; how big changes have to be 
made to existing algorithms for better support to heterogeneity ?
 
 -DHTs require O(log n) hops to reach arbitrary destinations, assuming that 
each node maintains 
 information about O(log n) nodes
@@ -366,7 +377,7 @@
 Please notice: In this approach, DHT doesn't store the actual block, only the 
values for locating the data from the system
 
        Req. 1:
-       -each node maintains a local stack based data structure (urn-5 name -> 
most recent local block ID) for every urn-5 names
+       -each node maintains a local hash-table based data structure (urn-5 
name -> most recent local block ID) for every urn-5 names
        which node hosts. The most recent block is topmost --> we don't have to 
check all blocks and their urn-5 associations to get the most recent
        Req. 2:
        -all urn-5 name mappings are stored as <key, value[ ]>, where the key 
is urn-5 name's hash and value is a record containing
@@ -429,7 +440,7 @@
 Please notice: In this approach, DHT doesn't store the actual block, only the 
values for locating the data from the system
 
        Req. 1:
-       -each node maintains a local stack based data structure (urn-5 name -> 
most recent local block ID) for every urn-5 names
+       -each node maintains a local hash-table based data structure (urn-5 
name -> most recent local block ID) for every urn-5 names
        which node hosts. The most recent block is topmost --> we don't have to 
check all blocks and their urn-5 associations to get the most recent
        Req. 2:
        -all urn-5 name mappings are stored as <key, value[ ]>, where the key 
is urn-5 name's hash and value is a record containing